Mercurial > paraspace
diff paraspace/dex_deptracker.py @ 25:670167ed06bb
test dex_deptracker._link_dependencies()
author | Thinker K.F. Li <thinker@codemud.net> |
---|---|
date | Tue, 07 Jun 2011 00:21:17 +0800 |
parents | a57ec6a76fe3 |
children | b30a0d29a62f |
line wrap: on
line diff
--- a/paraspace/dex_deptracker.py Thu Jun 02 21:50:49 2011 +0800 +++ b/paraspace/dex_deptracker.py Tue Jun 07 00:21:17 2011 +0800 @@ -6,12 +6,44 @@ dexfile.switch) -def _dig_clazz(name_path, clazz, dex_types): - deps = {} +def _resolve_name_path(name_path): + obj = dexfile + parent = None + for name in name_path.split('.'): + if isinstance(parent, dexfile.array) and obj == list: + # array.items.<num> + obj = parent.child_type + parent = list + continue + + parent = obj + if isinstance(parent, dexfile.switch): + key = eval(name) + obj = parent.map[key] + continue + + if isinstance(parent, dexfile.array) and name == 'items': + obj = list + continue + + if isinstance(parent, dexfile.cond) and name == 'value': + obj = obj.child_type + continue + + obj = getattr(parent, name) + pass + return obj, parent + + +def _find_dep_decls_from_clazz(name_path, clazz, dex_types): + dep_decls = {} for attr in dir(clazz): namelist = [name_path, attr] + # + # Find dependency + # digged_flag = False value_type = getattr(clazz, attr) @@ -20,6 +52,7 @@ issubclass(value_type, _nest_types)): if isinstance(value_type, dexfile.array): namelist.append('items') + namelist.append('*') value_type = value_type.child_type elif isinstance(value_type, dexfile.cond): namelist.append('value') @@ -29,9 +62,15 @@ if child_type in dex_types.values(): continue child_name_path = '.'.join(namelist) + '.' + repr(key) - child_deps = \ - _dig_clazz(child_name_path, child_type, dex_types) - deps.update(child_deps) + child_dep_decls = \ + _find_dep_decls_from_clazz(child_name_path, + child_type, + dex_types) + + if child_dep_decls: + raise ValueError, \ + 'can not depend on elements of a switch (%s)' \ + % (child_name_path) pass digged_flag = True break @@ -39,28 +78,81 @@ if digged_flag: continue - + + # + # Record dependency + # if isinstance(value_type, dexfile.depend): from_name = '.'.join(namelist) if isinstance(value_type, dexfile.depend_off): depend_name = value_type.depend_on - deps[from_name] = (dexfile.depend_off, depend_name) + dep_decls[from_name] = (dexfile.depend_off, depend_name) elif isinstance(value_type, dexfile.depend_off_rel): depend_name = value_type.depend_on relative_to = value_type.relative_to - deps[from_name] = (dexfile.depend_off_rel, + dep_decls[from_name] = (dexfile.depend_off_rel, depend_name, relative_to) elif isinstance(value_type, dexfile.depend_idx): depend_name = value_type.depend_on - deps[from_name] = (dexfile.depend_idx, depend_name) + dep_decls[from_name] = (dexfile.depend_idx, depend_name) pass pass pass - return deps + return dep_decls + + +def _dex_tree_get_child(obj, child_name): + if isinstance(obj, list): + idx = int(child_name) + return obj[idx] + + if isinstance(obj, dexfile.switch): + assert obj.map[eval(child_name)] == obj.child_type + return obj.value + + return getattr(obj, child_name) -def all_dex_types(): +def _dex_tree_set_child(obj, child_name, value): + if isinstance(obj, list): + idx = int(child_name) + obj[idx] = value + elif isinstance(obj, dexfile.switch): + assert obj.map[eval(child_name)] == obj.child_type + obj.value = value + else: + setattr(obj, child_name, value) + pass + pass + + +def _travel_dex_relocatable(root_obj, parents=[]): + stk = [(root_obj, parents, root_obj.__class__.__name__)] + + while stk: + obj, parents, obj_name = stk.pop(0) + yield (obj, parents, obj_name) + + if isinstance(obj, list): + children = [(value, parents + [obj], obj_name + '.' + repr(idx)) + for idx, value in enumerate(obj)] + stk.extend(children) + continue + + if not isinstance(obj, dexfile.relocatable): + continue + + child_parents = parents + [obj] + children = [(_dex_tree_get_child(obj, child_name), + child_parents, obj_name + '.' + child_name) + for child_name in obj.children()] + stk.extend(children) + pass + pass + + +def _all_dex_types(): dex_types = dict([(name, value) for name, value in dexfile.__dict__.items() if name.startswith('_DEX_')]) @@ -68,30 +160,264 @@ return dex_types -def collect_dependencies(): - dex_types = all_dex_types() +def collect_all_dep_decls(): + dex_types = _all_dex_types() - all_deps = {} + all_dep_decls = {} for name_path, clazz in dex_types.items(): - deps = _dig_clazz(name_path, clazz, dex_types) - all_deps.update(deps) + dep_decls = _find_dep_decls_from_clazz(name_path, clazz, dex_types) + all_dep_decls.update(dep_decls) + pass + + return all_dep_decls + + +class _uid_marker(dexfile.relocatable): + uid_seq = 0 + back_type = None + + def __init__(self, back_type, name_path): + self.back_type = back_type + self.name_path = name_path pass - return all_deps + def parse(self, parent, data, off): + value = self.back_type.parse(parent, data, off) + try: + value.data_uid = _uid_marker.uid_seq + except AttributeError: + raise AttributeError, \ + 'can not depend on non-instance (%s)' % (self.name_path) + _uid_marker.uid_seq = _uid_marker.uid_seq + 1 + + return value + + def sizeof(self, value): + sz = self.back_type.sizeof(value) + return sz + + def compute_size(self, back_obj): + self.back_type.compute_size(back_obj) + pass + + def to_str(self, back_obj): + return self.back_type.to_str(back_obj) + + def link_prepare(self, obj, name_path, parents, markers_info): + try: + id_item_map = markers_info[name_path] + except KeyError: + id_item_map = {} + markers_info[name_path] = id_item_map + pass + assert obj.data_uid not in id_item_map + id_item_map[obj.data_uid] = obj + pass + + def __getattr__(self, name): + return getattr(self.back_type, name) + + def __call__(self, *args, **kws): + return self.back_type(*args, **kws) + pass -def _install_uid_marker(all_deps): - for from_path, dep in all_deps.items(): - dep_type = dep[0] - if issubclass(dep_type, dexfile.depend_off): - # install offset marker +class _offset_marker(_uid_marker): + def parse(self, parent, data, off): + super(_offset_marker, self).parse(parent, data, off) + + value = self.back_type.parse(parent, data, off) + value.data_offset = off + return value + + def link_prepare(self, obj, name_path, parents, markers_info): + try: + id_item_map = markers_info[name_path] + except KeyError: + id_item_map = {} + markers_info[name_path] = id_item_map pass - # install uid marker + assert obj.data_offset not in id_item_map + id_item_map[obj.data_offset] = obj pass pass -def _link_dependencies(): +class _rel_offset_marker(_offset_marker): + def link_prepare(self, obj, name_path, parents, markers_info): + rev_parents = list(parents) + rev_parents.reverse() + + for parent in rev_parents: + rel_marker_info = getattr(parent, 'rel_marker_info', {}) + items = getattr(parent, name_path, []) + items.append(obj) + pass + pass + + @staticmethod + def find_depon(name_path, parents): + rev_parents = list(parents) + rev_parents.reverse() + + for parent in rev_parents: + try: + rel_marker_info = parent.rel_marker_info + except: + continue + if name_path in rel_marker_info: + depons = rel_marker_info[name_path] + assert len(depons) == 1 + depon = depons[0] + return depon + pass + + raise RuntimeError, 'can not find relative offset depend' + pass + + +class _idx_marker(_uid_marker): + def parse(self, parent, data, off): + assert isinstance(self.back_type, dexfile.array) + array = self.back_type.parse(parent, data, off) + for item in array.items: + item.data_uid = _uid_marker.uid_seq + _uid_marker.uid_seq = _uid_marker.uid_seq + 1 + pass + return array + + def link_prepare(self, obj, name_path, parents, markers_info): + pass + pass + + +def _install_offset_marker(name_path): + obj, parent = _resolve_name_path(name_path) + marker = _offset_marker(obj, name_path) + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, marker) + pass + + +def _install_rel_offset_marker(name_path): + obj, parent = _resolve_name_path(name_path) + marker = _rel_offset_marker(obj, name_path) + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, marker) + pass + + +def _install_uid_marker(name_path): + obj, parent = _resolve_name_path(name_path) + marker = _uid_marker(obj, name_path) + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, marker) + pass + + +def _install_idx_marker(name_path): + obj, parent = _resolve_name_path(name_path) + marker = _idx_marker(obj, name_path) + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, marker) + pass + + +def _install_markers(all_dep_decls): + all_markers = set() + + for from_path, dep in all_dep_decls.items(): + dep_type = dep[0] + if issubclass(dep_type, dexfile.depend_off_rel): + name_path1 = dep[1] + if name_path1 not in all_markers: + all_markers.add(name_path1) + _install_rel_offset_marker(name_path1) + pass + + name_path2 = dep[2] + if name_path2 not in all_markers: + all_markers.add(name_path2) + _install_rel_offset_marker(name_path2) + pass + pass + elif dep_type == dexfile.depend_off: + name_path = dep[1] + if name_path not in all_markers: + all_markers.add(name_path) + _install_offset_marker(name_path) + pass + pass + elif dep_type == dexfile.depend_idx: + name_path = dep[1] + if name_path not in all_markers: + all_markers.add(name_path) + _install_idx_marker(name_path) + pass + pass + else: + raise TypeError, 'Invalid type of depend %s' % (repr(dep_type)) + pass + pass + + +def _link_dependencies(root_obj, all_dep_decls): + markers_info = {} + depon_src_map = {} + for dep_src, depon in all_dep_decls.items(): + for tgt in depon[1:]: + markers_info[tgt] = {} + depon_src_map[depon] = dep_src + pass + pass + + # + # Collect marked objects + # + for obj, parents, name_path in \ + _travel_dex_relocatable(root_obj): + if name_path not in markers_info: + continue + + marker, dummy_parent = _resolve_name_path(name_path) + marker.link_prepare(obj, name_path, parents, markers_info) + pass + + # + # Link depend source to marked target + # + for obj, parents, name_path in \ + _travel_dex_relocatable(root_obj): + if name_path not in all_dep_decls: + continue + + rev_parents = list(parents) + rev_parents.reverse() + + dep = all_dep_decls[name_path] + dep_type = dep[0] + if isinstance(dep_type, dexfile.depend_off_rel): + depon1 = _rel_offset_marker.find_depon(dep[1]) + depon2 = _rel_offset_marker.find_depon(dep[2]) + + parent = parents[-1] + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, (depon1, depon2)) + elif isinstance(dep_type, dexfile.depend_off): + depon_name_path = dep[1] + depon = markers_info[depon_name_path] + parent = parents[-1] + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, depon) + elif isinstance(dep_type, dexfile.depend_idx): + depon_name_path = dep[1] + depon = markers_info[depon_name_path] + parent = parents[-1] + name = name_path.split('.')[-1] + _dex_tree_set_child(parent, name, depon) + else: + raise TypeError, 'invalid depend type %s' % (repr(dep_type)) + pass pass @@ -100,9 +426,9 @@ if __name__ == '__main__': - dex = dexfile.DEXFile.open('../data/testdata1.dex') + dex = dexfile.DEXFile.open('data/testdata1.dex') import pprint print print 'Dependencies' - pprint.pprint(collect_dependencies()) + pprint.pprint(collect_all_dep_decls())