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())