Mercurial > paraspace
view paraspace/dex_deptracker.py @ 26:b30a0d29a62f
Debugging _travel_dex_type
author | Thinker K.F. Li <thinker@codemud.net> |
---|---|
date | Tue, 07 Jun 2011 15:02:42 +0800 |
parents | 670167ed06bb |
children | 15cb829ac442 |
line wrap: on
line source
from paraspace import dexfile _nest_types = (dexfile.array, dexfile.cond, dexfile.switch) 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 _travel_dex_type(clazz, name_path): if isinstance(clazz, _marker): clazz = clazz.back_type pass travel_queue = [(getattr(clazz, attr_name), name_path + '.' + attr_name) for attr_name in dir(clazz) if not attr_name.startswith('_')] while travel_queue: attr, name_path = travel_queue.pop(0) yield attr, name_path if isinstance(attr, _marker): # # transparent. Enqueue back_type with the same name again. # child = attr.back_type travel_queue.append((child, name_path)) continue if isinstance(attr, _nest_types): if isinstance(attr, dexfile.array): child_name = name_path + '.items.*' child = attr.child_type travel_queue.append((child, child_name)) elif isinstance(attr, dexfile.cond): child_name = name_path + '.value' child = attr.child_type travel_queue.append((child, child_name)) elif isinstance(attr, dexfile.switch): for key in attr.map.keys(): child_name = name_path + '.' + repr(key) child = attr.map[key] travel_queue.append((child, child_name)) pass pass pass pass pass def _find_dep_decls_from_clazz(name_path, clazz, dex_types): # XXX: implements the loop with _travel_dex_type() dep_decls = {} for attr in dir(clazz): namelist = [name_path, attr] # # Find dependency # digged_flag = False value_type = getattr(clazz, attr) while isinstance(value_type, _nest_types) or \ (type(value_type) == type and 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') value_type = value_type.child_type elif isinstance(value_type, dexfile.switch): for key, child_type in value_type.map.items(): if child_type in dex_types.values(): continue child_name_path = '.'.join(namelist) + '.' + repr(key) 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 pass 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 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 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 dep_decls[from_name] = (dexfile.depend_idx, depend_name) pass pass pass 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 _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__)] def make_travel_info(obj, obj_name, child_name): child_parents = parents + [obj] child_obj = _dex_tree_get_child(obj, child_name) if isinstance(child_obj, dexfile.composite): child_path = child_obj.__class__.__name__ else: child_path = obj_name + '.' + child_name pass return (child_obj, child_parents, child_path) while stk: obj, parents, obj_name = stk.pop(0) yield (obj, parents, obj_name) if isinstance(obj, list): children = [make_travel_info(obj, obj_name, repr(idx)) for idx in range(len(obj))] stk.extend(children) continue if not isinstance(obj, dexfile.relocatable): continue children = [make_travel_info(obj, 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_')]) dex_types['DEXFile'] = dexfile.DEXFile return dex_types def collect_all_dep_decls(): dex_types = _all_dex_types() all_dep_decls = {} for name_path, clazz in dex_types.items(): dep_decls = _find_dep_decls_from_clazz(name_path, clazz, dex_types) all_dep_decls.update(dep_decls) pass return all_dep_decls class _marker(dexfile.relocatable): back_type = None pass class _uid_marker(_marker): uid_seq = 0 def __init__(self, back_type, name_path): self.back_type = back_type self.name_path = name_path pass 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 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 assert obj.data_offset not in id_item_map id_item_map[obj.data_offset] = obj pass pass 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 _patch_dex_type_markers(all_dep_decls): import itertools marked_types = dict([(marker.back_type, name) for name, marker in _all_dex_types().items() if isinstance(marker, _marker)]) travel_iters = [_travel_dex_type(dex_type, name_path) for name_path, dex_type in _all_dex_types().items()] marked_type_refs = [(name_path, marked_types[attr]) for attr, name_path in itertools.chain(*travel_iters) if type(attr) == type and issubclass(attr, dexfile.composite) and attr in marked_types] print marked_type_refs def patch_ref(name_path, depon_path): depon, depon_parent = _resolve_name_path(depon_path) path_elms = name_path.split('.') parent_path = '.'.join(path_elms[:-1]) parent, grand = _resolve_name_path(parent_path) if isinstance(grand, _nest_types): if isinstance(grand, (dexfile.array, dexfile.cond)): grand.child_type = depon elif isinstance(grand, dexfile.switch): key = eval(path_elms[-1]) grand.map[key] = depon else: raise RuntimeError, 'should not be here' pass else: name = path_elms[-1] setattr(parent, name, depon) pass pass for name_path, depon_path in marked_type_refs: patch_ref(name_path, depon_path) 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): print name_path 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 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 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 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 def _sync_dependencies(): pass if __name__ == '__main__': dex = dexfile.DEXFile.open('data/testdata1.dex') import pprint print print 'Dependencies' pprint.pprint(collect_all_dep_decls())