# HG changeset patch # User Thinker K.F. Li # Date 1312814051 -28800 # Node ID 650244dcdd820667855752e30e89156e52948969 # Parent ff6f869273b783f9ea25a8456e1ffba2b7625982 Sort arrays in rules requested by dalvik diff -r ff6f869273b7 -r 650244dcdd82 paraspace/dex_deptracker.py --- a/paraspace/dex_deptracker.py Mon Aug 08 17:26:05 2011 +0800 +++ b/paraspace/dex_deptracker.py Mon Aug 08 22:34:11 2011 +0800 @@ -785,6 +785,27 @@ return depon_dep_map +## \brief Make sorted arrays being sorted. +# +# Some array in a DEXFile must be sorted in some kind of rule. They +# are typed by \ref array_sorted, the type of a sorted array. Child +# type of a sorted array must implement __cmp__ method to define the +# rule. +# +# This function must be applied on a DEXFile_linked before calling +# restore_dependencies(). +# +def dex_sort_sorted_arrays(dex): + assert isinstance(dex, dexfile.DEXFile_linked) + + for obj, parents, name_path in _travel_dex_relocatable(dex): + if isinstance(obj, dexfile.array_sorted): + obj.items.sort() + pass + pass + pass + + ## \brief Update offset for all relocatable of a DEXFile. # # Update offset of instances of \ref _dex_type. diff -r ff6f869273b7 -r 650244dcdd82 paraspace/dexfile.py --- a/paraspace/dexfile.py Mon Aug 08 17:26:05 2011 +0800 +++ b/paraspace/dexfile.py Mon Aug 08 22:34:11 2011 +0800 @@ -558,7 +558,7 @@ def parse_nitem(self, parent, data, off, nitem): moff = man_off(off) - obj = array(self.count_name, self.child_type) + obj = self.__class__(self.count_name, self.child_type) def parse(): item = obj.child_type.parse(parent, data, moff()) @@ -591,6 +591,10 @@ pass +class array_sorted(array): + pass + + class composite(relocatable): child_names = None @@ -986,6 +990,13 @@ stringDataOff = depend_off('_DEX_StringDataItem')(uint32) child_names = ('stringDataOff',) + + def __cmp__(self, other): + assert isinstance(other, _DEX_StringId) + assert isinstance(self.stringDataOff, _DEX_StringDataItem) + assert isinstance(other.stringDataOff, _DEX_StringDataItem) + + return cmp(self.stringDataOff.data.data, other.stringDataOff.data.data) pass @@ -993,6 +1004,13 @@ descriptorIdx = depend_idx('DEXFile.stringIds')(uint32) child_names = ('descriptorIdx',) + + def __cmp__(self, other): + assert isinstance(other, _DEX_TypeId) + assert isinstance(self.descriptorIdx, _DEX_StringId) + assert isinstance(other.descriptorIdx, _DEX_StringId) + + return cmp(self.descriptorIdx, other.descriptorIdx) pass @@ -1006,6 +1024,33 @@ child_names = 'shortyIdx returnTypeIdx parametersOff ' \ 'parametersOffRef'.split() + + ## \brief Compare two linked _DEX_ProtoId instances. + def __cmp__(self, other): + assert isinstance(other, _DEX_ProtoId) + assert isinstance(self.returnTypeIdx, _DEX_TypeId) + assert isinstance(other.returnTypeIdx, _DEX_TypeId) + + r = cmp(self.returnTypeIdx, other.returnTypeIdx) + if r != 0: + return r + if not self.parametersOffRef.is_true: + return -1 + if not other.parametersOffRef.is_true: + return 1 + + tlist0 = self.parametersOffRef.value.typeItems.items + tlist1 = other.parametersOffRef.value.typeItems.items + for param0, param1 in map(None, tlist0, tlist1): + if not (param0 and param1): + break + + r = cmp(param0.typeIdx, param1.typeIdx) + if r != 0: + return r + pass + + return cmp(len(tlist0), len(tlist1)) pass @@ -1015,6 +1060,20 @@ nameIdx = depend_idx('DEXFile.stringIds')(uint32) child_names = 'classIdx typeIdx nameIdx'.split() + + def __cmp__(self, other): + assert isinstance(other, _DEX_FieldId) + assert isinstance(self.classIdx, _DEX_TypeId) + assert isinstance(other.classIdx, _DEX_TypeId) + + r = cmp(self.classIdx, other.classIdx) + if r != 0: + return r + r = cmp(self.nameIdx, other.nameIdx) + if r != 0: + return r + r = cmp(self.typeIdx, other.typeIdx) + return r pass @@ -1024,6 +1083,20 @@ nameIdx = depend_idx('DEXFile.stringIds')(uint32) child_names = 'classIdx protoIdx nameIdx'.split() + + def __cmp__(self, other): + assert isinstance(other, _DEX_MethodId) + assert isinstance(self.classIdx, _DEX_TypeId) + assert isinstance(other.classIdx, _DEX_TypeId) + + r = cmp(self.classIdx, other.classIdx) + if r != 0: + return r + r = cmp(self.nameIdx, other.nameIdx) + if r != 0: + return r + r = cmp(self.typeIdx, other.protoIdx) + return r pass @@ -1216,6 +1289,13 @@ 'annotationsOff'))) child_names = 'fieldIdx annotationsOff annotationsOffRef'.split() + + def __cmp__(self, other): + assert isinstance(other, _DEX_FieldAnnotationsItem) + assert isinstance(self.fieldIdx, _DEX_FieldId) + assert isinstance(other.fieldIdx, _DEX_FieldId) + + return cmp(self.fieldIdx, other.fieldIdx) pass @@ -1228,6 +1308,13 @@ 'annotationsOff'))) child_names = 'methodIdx annotationsOff annotationsOffRef'.split() + + def __cmp__(self, other): + assert isinstance(other, _DEX_MethodAnnotationsItem) + assert isinstance(self.methodIdx, _DEX_MethodId) + assert isinstance(other.methodIdx, _DEX_MethodId) + + return cmp(self.methodIdx, other.methodIdx) pass @@ -1240,6 +1327,13 @@ 'annotationsOff'))) child_names = 'methodIdx annotationsOff annotationsOffRef'.split() + + def __cmp__(self, other): + assert isinstance(other, _DEX_ParameterAnnotationsItem) + assert isinstance(self.methodIdx, _DEX_MethodId) + assert isinstance(other.methodIdx, _DEX_MethodId) + + return cmp(self.methodIdx, other.methodIdx) pass @@ -1254,10 +1348,12 @@ methodsSize = uint32 parametersSize = uint32 - fieldAnnotationsItems = array('fieldsSize', _DEX_FieldAnnotationsItem) - methodAnnotationsItems = array('methodsSize', _DEX_MethodAnnotationsItem) - parameterAnnotationsItems = array('parametersSize', - _DEX_ParameterAnnotationsItem) + fieldAnnotationsItems = array_sorted('fieldsSize', + _DEX_FieldAnnotationsItem) + methodAnnotationsItems = array_sorted('methodsSize', + _DEX_MethodAnnotationsItem) + parameterAnnotationsItems = array_sorted('parametersSize', + _DEX_ParameterAnnotationsItem) child_names = 'classAnnotationsOff classAnnotationsOffRef ' \ 'fieldsSize methodsSize ' \ @@ -1346,6 +1442,13 @@ nameIdx = depend_idx('DEXFile.stringIds')(uleb128) child_names = 'nameIdx valueType value'.split() + + def __cmp__(self, other): + assert isinstance(other, _DEX_AnnotationMember) + assert isinstance(self.nameIdx, _DEX_StringId) + assert isinstance(other.nameIdx, _DEX_StringId) + + return cmp(self.nameIdx, other.nameIdx) pass @@ -1359,13 +1462,20 @@ class _DEX_AnnotationItem_novisibility(composite): typeIdx = depend_idx('DEXFile.typeIds')(uleb128) size = uleb128 - members = array('size', _DEX_AnnotationMember) + members = array_sorted('size', _DEX_AnnotationMember) child_names = 'typeIdx size members'.split() kDexVisibilityBuild = 0x00 kDexVisibilityRuntime = 0x01 kDexVisibilitySystem = 0x02 + + def __cmp__(self, other): + assert isinstance(other, _DEX_AnnotationItem_novisibility) + assert isinstance(self.typeIdx, _DEX_TypeId) + assert isinstance(other.typeIdx, _DEX_TypeId) + + return cmp(self.typeIdx, other.typeIdx) pass @@ -1631,18 +1741,18 @@ data = None header = _DEX_header maps = _DEX_MapItemBlock - stringIds = array(None, _DEX_StringId) - typeIds = array(None, _DEX_TypeId) - protoIds = array(None, _DEX_ProtoId) - fieldIds = array(None, _DEX_FieldId) - methodIds = array(None, _DEX_MethodId) + stringIds = array_sorted(None, _DEX_StringId) + typeIds = array_sorted(None, _DEX_TypeId) + protoIds = array_sorted(None, _DEX_ProtoId) + fieldIds = array_sorted(None, _DEX_FieldId) + methodIds = array_sorted(None, _DEX_MethodId) classDefs = array(None, _DEX_ClassDef) classDatas = array(None, _DEX_ClassData) typeLists = array(None, _DEX_TypeList_align) codeItems = array(None, _DEX_Code) annotationSetItems = array(None, _DEX_AnnotationSetItem) annotationsDirectoryItems = array(None, _DEX_AnnotationsDirectoryItem) - annotationItems = array(None, _DEX_AnnotationItem) + annotationItems = array_sorted(None, _DEX_AnnotationItem) encodedArrayItems = array(None, _DEX_EncodedArrayItem) debugInfoItems = array(None, _DEX_DebugInfoItem) stringDataItems = array(None, _DEX_StringDataItem) diff -r ff6f869273b7 -r 650244dcdd82 paraspace/tests/dex_deptracker_test.py --- a/paraspace/tests/dex_deptracker_test.py Mon Aug 08 17:26:05 2011 +0800 +++ b/paraspace/tests/dex_deptracker_test.py Mon Aug 08 22:34:11 2011 +0800 @@ -189,3 +189,31 @@ assert linked_sz == (unlinked_sz + 4) pass + + +def dex_sort_sorted_arrays_test(): + from paraspace.dex_deptracker import dex_sort_sorted_arrays + + _install_dexfile_4_deptracker() + + srcdir = os.path.dirname(__file__) + srcroot = os.path.join(srcdir, '..', '..') + datadir = os.path.join(srcroot, 'data') + helloworld_path = os.path.join(datadir, 'helloworld.dex') + + decls = prepare_dep_decls() + + hello_dex = dexfile.DEXFile.open(helloworld_path) + hello_linked = \ + dexfile.DEXFile_linked.build_dependencies(hello_dex, decls) + + first = hello_linked.typeIds.items[0] + last = hello_linked.typeIds.items[-1] + hello_linked.typeIds.items[0] = last + hello_linked.typeIds.items[-1] = first + + dex_sort_sorted_arrays(hello_linked) + + assert hello_linked.typeIds.items[0] == first + assert hello_linked.typeIds.items[-1] == last + pass