def _relocatable_children(obj):
    from paraspace.dex_deptracker import _dex_tree_get_child
    from paraspace.dexfile import relocatable, array

    if isinstance(obj, array):
        rel_children = [('items.' + str(idx), value)
                        for idx, value in enumerate(obj.items)
                        if isinstance(value, relocatable)]
        return rel_children
    
    attrs = obj.children()
    attr_value_pairs = [(attr, _dex_tree_get_child(obj, attr))
                        for attr in attrs]
    rel_children = [(attr, value) for attr, value in attr_value_pairs
                    if isinstance(value, relocatable)]
    return rel_children


## \brief Travel relocatable descendants.
#
# \param cloner is the function to return a clone.
# \param adjuster is called to adjust the clone.
# \param visit_log is a dictionary to keep clones.
#
def _travel_desc_relocatable(obj, worker, visit_log):
    if id(obj) in visit_log:
        return visit_log[id(obj)]

    result = worker(obj)
    visit_log[id(obj)] = result
    
    rel_children = _relocatable_children(obj)
    for attr, value in rel_children:
        _travel_desc_relocatable(value, worker, visit_log)
        pass
    pass


## \brief Return name string of a linked class definition item.
def classdef_name(classdef):
    return classdef.classIdx.descriptorIdx.stringDataOff.data


## \brief Return a map that map type of a object to the list of a DEXFile.
def dex_type_2_array_attr_map():
    global dex_type_2_array_attr_map
    from paraspace.dexfile import DEXFile, array
    from paraspace.dex_deptracker import _marker

    def skip_marker_type(clazz):
        while isinstance(clazz, _marker):
            clazz = clazz.back_type
            pass
        return clazz
    
    attr_values = [(attr, skip_marker_type(getattr(DEXFile, attr)))
                   for attr in dir(DEXFile)]
    array_attrs = [(skip_marker_type(value.child_type), attr)
                   for attr, value in attr_values
                   if isinstance(value, array)]
    type_2_attr = dict(array_attrs)
    
    dex_type_2_array_attr_map = lambda: type_2_attr
    
    return type_2_attr


_saved_dex_type_2_array_attr_map = dex_type_2_array_attr_map


## \brief Append a object to appropriate list of a DEXFile object.
#
# Skip the object if found no appropriate list.
#
def dex_append_obj_list(dex, obj):
    from paraspace.dex_deptracker import _dex_tree_get_child
    from paraspace.dex_deptracker import _dex_tree_set_child
    from paraspace.dexfile import _DEX_TypeList, _DEX_TypeList_align
    from paraspace.dexfile import array_sorted

    ret_obj = obj
    if isinstance(obj, _DEX_TypeList):
        wrapper = _DEX_TypeList_align()
        wrapper.value = obj
        obj = wrapper
        pass

    type_2_attr = dex_type_2_array_attr_map()
    try:
        attr = type_2_attr[obj.__class__]
    except KeyError:
        return

    array = getattr(dex, attr)
    
    if isinstance(array, array_sorted):
        if obj in array.items:
            idx = array.items.index(obj)
            obj = array.items[idx]
            if isinstance(obj, _DEX_TypeList_align):
                return obj.value
            return obj
        pass

    array.items.append(obj)
    
    count_name = array.count_name
    if count_name:
        count = _dex_tree_get_child(dex, count_name)
        _dex_tree_set_child(dex, count_name, count + 1)
        pass

    return ret_obj


## \brief Clone a composite object.
#
# \param dex is the DEXFile that the composite object is cloning for.
# \param comobj is composite object that is cloning.
#
def _clone_composite(dex, comobj):
    from copy import copy
    from paraspace.dexfile import _DEX_StringDataItem, _DEX_StringId
    from paraspace.dexfile import _DEX_TypeId
    from paraspace.dex_deptracker import _dex_tree_set_child
    from paraspace.dex_deptracker import _dex_tree_get_child
    
    visit_log = {}
    
    def cloner(obj):
        clone = copy(obj)
        return clone

    def relink_dependencies(clone):
        rel_children = _relocatable_children(clone)
        for attr, value in rel_children:
            clone_value = visit_log[id(value)]
            _dex_tree_set_child(clone, attr, clone_value)
            pass
        pass

    def merge_unique_strdata():
        strdatas = [(obj_id, obj)
                    for obj_id, obj in visit_log.items()
                    if isinstance(obj, _DEX_StringDataItem)]
        dex_str_2_strdata = dict([(strdata.data.data, strdata)
                                  for strdata in dex.stringDataItems.items])
        for obj_id, strdata in strdatas:
            if strdata.data.data in dex_str_2_strdata:
                visit_log[obj_id] = dex_str_2_strdata[strdata.data.data]
            else:
                dex_append_obj_list(dex, strdata)
                pass
            pass
        pass

    def merge_unique_strid():
        strids = [(obj_id, obj)
                  for obj_id, obj in visit_log.items()
                  if isinstance(obj, _DEX_StringId)]
        
        for obj_id, strid in strids:
            relink_dependencies(strid)
            pass

        strdata_2_strid = dict([(strid.stringDataOff, strid)
                                for strid in dex.stringIds.items])
        for obj_id, strid in strids:
            if strid.stringDataOff in strdata_2_strid:
                visit_log[obj_id] = strdata_2_strid[strid.stringDataOff]
            else:
                dex_append_obj_list(dex, strid)
                pass
            pass
        pass

    def merge_unique_typeid():
        typeids = [(obj_id, obj)
                   for obj_id, obj in visit_log.items()
                   if isinstance(obj, _DEX_TypeId)]
        
        for obj_id, typeid in typeids:
            relink_dependencies(typeid)
            pass

        strid_2_typeid = dict([(typeid.descriptorIdx, typeid)
                               for typeid in dex.typeIds.items])
        for obj_id, typeid in typeids:
            if typeid.descriptorIdx in strid_2_typeid:
                visit_log[obj_id] = strid_2_typeid[typeid.descriptorIdx]
            else:
                dex_append_obj_list(dex, typeid)
                pass
            pass
        pass

    _travel_desc_relocatable(comobj, cloner, visit_log)

    merge_unique_strdata()
    merge_unique_strid()
    merge_unique_typeid()
    
    relink_list = []
    for key, obj in visit_log.items():
        if isinstance(obj, (_DEX_StringDataItem,
                            _DEX_StringId,
                            _DEX_TypeId)):
            continue
        r = dex_append_obj_list(dex, obj)
        if r and r is not obj:
            visit_log[key] = r
        else:
            relink_list.append(obj)
            pass
        pass
    
    for obj in relink_list:
        if isinstance(obj, (_DEX_StringDataItem,
                            _DEX_StringId,
                            _DEX_TypeId)):
            continue
        relink_dependencies(obj)
        pass
    
    clone = visit_log[id(comobj)]
    return clone


## \brief Clone a class definition item
#
# \param dex is the DEXFile that clazz is cloning for.
# \param clazz is the class definition item that is cloning.
# \return the cloning _DEX_ClassDef.
#
def _clone_classdef(dex, clazz):
    from paraspace.dexfile import DEXFile_linked, _DEX_ClassDef
    
    def has_classdef(clazz):
        classname = DEXFile_linked.get_classdef_name(clazz)
        try:
            dex.find_class_name(classname)
        except ValueError:
            return False
        return True

    assert isinstance(clazz, _DEX_ClassDef)

    if has_classdef(clazz):
        raise RuntimeError, \
            'clone a class \'%s\'that is already in the DEXFile' % \
            classdef_name(clazz)
    
    clone = _clone_composite(dex, clazz)
    return clone


## \brief Clone a class definition and insert into a DEXFile.
#
# This function clone a class definition from a linked DEXFile and
# insert it into another one.
#
# \param dex is a DEXFile_linked to insert the clone.
# \param class_def is a class definition going to be cloned.
#
def dexfile_insert_class(dex, classdef):
    clone = _clone_classdef(dex, classdef)
    return clone


## \brief Collect info of classes mentioned by the code of given class.
def _find_class_relative(dex, classdef):
    def classify_typeids_defined(dex, typeids):
        classdefs = []
        undef_typeids = []
        for typeid in typeids:
            try:
                classdef = dex.find_class_typeid(typeid)
            except ValueError:
                undef_typeids.append(typeid)
            else:
                classdefs.append(classdef)
                pass
            pass
        return classdefs, undef_typeids

    typeidxs, stridxs = \
        collect_typeidxs_stridxs_mentioned_by_class(dex, classdef)
    typeids = [dex.find_typeid_idx(typeidx)
               for typeidx in typeidxs]
    strids = [dex.find_strid_idx(idx) for idx in stridxs]
    
    classdefs, typeids = classify_typeids_defined(dex, typeids)
    
    return classdefs, typeids, strids


def dexfile_insert_classdefs(dex_dst, dex_src, classdefs):
    clones = [dexfile_insert_class(dex_dst, classdef)
              for classdef in classdefs]
    return clones


## \brief Insert _DEX_StringId into another DEX.
def dexfile_insert_stringid(dex_dst, dex_src, strid):
    clone = _clone_composite(dex_dst, strid)
    return clone


## \brief Insert _DEX_StringIds into another DEX.
def dexfile_insert_stringids(dex_dst, dex_src, strids):
    clones = [dexfile_insert_stringid(dex_dst, dex_src, strid)
              for strid in strids]
    return clones


## \brief Clone and insert a _DEX_TypeId to another DEXFile_linked.
#
# \param dex_dst is a DEXFile_linked where the cloning one is inserted.
# \param dex_src is a DEXFile_linked where the cloned one is from.
# \param typeid is a _DEX_TypeId that is cloned.
# \return the cloning _DEX_TypeId.
#
def dexfile_insert_or_merge_typeid(dex_dst, dex_src, typeid):
    from paraspace.dexfile import _DEX_TypeId, DEXFile_linked, _DEX_MethodId
    
    assert isinstance(typeid, _DEX_TypeId)
    
    def typeid_not_in_dst(typeid):
        typename = DEXFile_linked.get_typeid_name(typeid)
        try:
            dex_dst.find_typeid_name(typename)
        except ValueError:
            return True
        return False
    
    if typeid_not_in_dst(typeid):
        cloning = _clone_composite(dex_dst, typeid)
        
        methodids = dex_src.find_methodids_typeid(dex_src, typeid)
        for methodid in methodids:
            _clone_composite(dex_dst, methodid)
            pass
        pass
    else:
        typename = DEXFile_linked.get_typeid_name(typeid)
        cloning = dex_dst.find_typeid_name(typename)
        
        methodids = dex_src.find_methodids_typeid(typeid)
        for methodid in methodids:
            methodname = DEXFile_linked.get_methodid_name(methodid)
            try:
                dex_dst.find_methodid_name_proto(methodname, methodid.protoIdx,
                                                 cloning)
            except ValueError:
                cloning_methodid = _clone_composite(dex_dst, methodid)
                pass
            pass
    
    return cloning


## \brief Clone and insert a list of _DEX_TypeId objects to a DEXFile_linked.
def dexfile_insert_or_merge_typeids(dex_dst, dex_src, typeids):
    clones = [dexfile_insert_or_merge_typeid(dex_dst, dex_src, typeid)
              for typeid in typeids]
    return clones


## \brief Collects relative type IDs and classes definition for given class.
def collect_classdefs_relative(dex, classdefs):
    rel_classdefs = set(classdefs)
    rel_typeids = set()
    rel_strids = set()
    
    classdef_queue = list(classdefs)
    while classdef_queue:
        cur_classdef = classdef_queue.pop(0)
        
        classdefs, typeids, strids = _find_class_relative(dex, cur_classdef)
        rel_typeids.update(typeids)
        new_classdefs = list(set(classdefs) - rel_classdefs)
        classdef_queue = classdef_queue + new_classdefs
        rel_classdefs.update(new_classdefs)
        rel_strids.update(strids)
        pass
    return rel_classdefs, rel_typeids, rel_strids


## \brief Clone and insert given and relative classes into another DEXFile.
#
# \param dex_dst is a DEXFile_linked where the class will be inserted.
# \param dex_src is a DEXFile_linked where the cloned class is from.
# \param classdef is a _DEX_ClassDef that will be cloned.
# \return a vector of a list of classdefs and a list of typeids.
#
def dexfile_insert_classdefs_relative(dex_dst, dex_src, classdefs):
    from paraspace.dexfile import DEXFile_linked
    
    def classdef_not_in_dst(classdef):
        classname = DEXFile_linked.get_classdef_name(classdef)
        try:
            dex_dst.find_class_name(classname)
        except ValueError:
            return True
        return False

    relative_classdefs, relative_typeids, relative_strids = \
        collect_classdefs_relative(dex_src, classdefs)
    
    for classdef in relative_classdefs:
        if classdef_not_in_dst(classdef):
            continue
        raise ValueError, '%s is already in DEX %s: can not insert it' % \
            (repr(classdef), repr(dex_dst))
    
    cloning_classdefs = \
        dexfile_insert_classdefs(dex_dst, dex_src, relative_classdefs)
    cloning_typeids = \
        dexfile_insert_or_merge_typeids(dex_dst, dex_src, relative_typeids)
    cloning_strids = \
        dexfile_insert_stringids(dex_dst, dex_src, relative_strids)

    return cloning_classdefs, cloning_typeids, cloning_strids


## \brief Redirect types, methods and strings for the code of given method.
def method_redirect_indices(dex, method, typeidxs_redir, methods_redir,
                            stridxs_redir):
    from paraspace.dalvik_opcodes import decode_insn_blk, all_opcodes
    from paraspace.dalvik_opcodes import encode_opcode_vectors
    from paraspace.dexfile import DEXFile_linked
    
    if not method.codeOffRef.is_true:
        return
    
    code = method.codeOffRef.value
    insns_blk = code.insns.data
    op_vectors = decode_insn_blk(insns_blk)

    def redirect(opcode, args):
        if opcode == all_opcodes.OP_NEW_INSTANCE:
            typeidx = args[1]
            if typeidx in typeidxs_redir:
                to_type = typeidxs_redir[typeidx]
                return opcode, (args[0], to_type)
            pass
        elif opcode in (all_opcodes.OP_INVOKE_DIRECT,
                        all_opcodes.OP_INVOKE_VIRTUAL,
                        all_opcodes.OP_INVOKE_SUPER,
                        all_opcodes.OP_INVOKE_STATIC,
                        all_opcodes.OP_INVOKE_INTERFACE):
            methodidx = args[2]
            if methodidx not in methods_redir:
                return opcode, args
            
            return opcode, (args[0], args[1], methods_redir[methodidx],
                            args[3], args[4], args[5], args[6])
        elif opcode in (all_opcodes.OP_INVOKE_VIRTUAL_RANGE,
                        all_opcodes.OP_INVOKE_DIRECT_RANGE,
                        all_opcodes.OP_INVOKE_SUPER_RANGE,
                        all_opcodes.OP_INVOKE_STATIC_RANGE,
                        all_opcodes.OP_INVOKE_INTERFACE_RANGE):
            methodidx = args[1]
            if methodidx not in methods_redir:
                return opcode, args
            
            return opcode, (args[0], methods_redir[methodidx], args[2])
        elif opcode == all_opcodes.OP_CONST_STRING:
            stridx = args[1]
            if stridx not in stridxs_redir:
                return opcode, args

            return opcode, (args[0], stridxs_redir[stridx])
        return opcode, args
    
    new_op_vectors = [redirect(opcode, args) for opcode, args in op_vectors]
    new_insns_blk = encode_opcode_vectors(new_op_vectors) 
    
    code.insns.data = new_insns_blk
    pass


## \brief Make a map for methods from source type ID to ones from desinate.
def make_redir_classes_methods_map(dex_src, typeid_src,
                                   dex_dst, typeid_dst):
    from paraspace.dexfile import DEXFile_linked
    
    methods_src = [(idx, methodid)
                   for idx, methodid in enumerate(dex_src.methodIds.items)
                   if methodid.classIdx == typeid_src]
    
    def make_map_methodid(methodid_src):
        name = DEXFile_linked.get_methodid_name(methodid_src)
        proto = methodid_src.protoIdx
        try:
            methodid_dst = \
                dex_dst.find_methodid_name_proto(name, proto, typeid_dst)
        except ValueError:
            return -1
        methodidx_dst = dex_dst.get_idx_methodid(methodid_dst)
        return methodidx_dst
    
    methods_map = [(methodidx_src, make_map_methodid(methodid_src))
                   for methodidx_src, methodid_src in methods_src]
    methods_map = [(methodidx_src, methodidx_dst)
                   for methodidx_src, methodidx_dst in methods_map
                   if methodidx_dst != -1]
    methods_map = dict(methods_map)
    return methods_map


## \brief Redirect types and methods mentioned in the code of a class.
#
# For code of given class definition, Every mentions of types and
# methods are rewrote to types and methods according typeidxs_redir and
# methods_redir respectively.
#
# \param dex is a DEXFile_linked.
# \param classdef is a class definition.
# \param typeidxs_redir is a map of types.
# \param stridxs_redir is a map of strings.
# \param methods_redir is a map of methods.
#
def class_redirect_indices(dex, classdef, typeidxs_redir, methods_redir,
                           stridxs_redir):
    if not classdef.classDataOffRef.is_true:
        return
    
    classdata = classdef.classDataOffRef.value
    for method in classdata.directMethods.items:
        method_redirect_indices(dex, method, typeidxs_redir, methods_redir,
                                stridxs_redir)
        pass
    for method in classdata.virtualMethods.items:
        method_redirect_indices(dex, method, typeidxs_redir, methods_redir,
                                stridxs_redir)
        pass
    pass


## \brief Make a map to map methods from source types to destinate types.
#
# This function create a map to map methods from source types to
# methods from destinate types in \ref typeidxs_redir.
#
# \param dex_src is a DEXFile_linked that owns source types.
# \param dex_dst is a DEXFile_linked that owns destinate types.
# \param typeidxs_redir is a map of type indices for redirecting types.
# \return a map of method indices.
#
def make_methodidxs_redir_map(dex_src, dex_dst, typeidxs_redir):
    methods_map = {}
    for typeidx_src, typeidx_dst in typeidxs_redir.items():
        typeid_src = dex_src.find_typeid_idx(typeidx_src)
        typeid_dst = dex_dst.find_typeid_idx(typeidx_dst)
        class_methods_map =  make_redir_classes_methods_map(dex_src,
                                                            typeid_src,
                                                            dex_dst,
                                                            typeid_dst)
        methods_map.update(class_methods_map)
        pass
    return methods_map


## \brief Make a map to map string indices from source to destinate DEX.
#
# \param dex_src is soruce of the mapping.
# \param dex_dst is destination of the mapping.
# \param classdefs is _DEX_ClassDefs from dex_src.
# \return a mapping for string indices.
#
def make_stridxs_redir_map(dex_src, dex_dst):
    stridxs_map = {}
    for idx, strid in enumerate(dex_src.stringIds.items):
        try:
            tgt_idx = dex_dst.stringIds.items.index(strid)
        except ValueError:
            continue
        stridxs_map[idx] = tgt_idx
        pass
    return stridxs_map


## \biref Redirect types of all code in given DEXFile_linked.
def dexfile_redirect_indices(dex, typeidxs_redir, methods_redir, stridxs_redir,
                             excludes=set([])):
    for classdef in dex.classDefs.items:
        typeid = classdef.classIdx
        idx = dex.get_idx_typeid(typeid)
        if idx in excludes:
            continue
        class_redirect_indices(dex, classdef, typeidxs_redir, methods_redir,
                               stridxs_redir)
        pass
    pass


## \brief Redirect types for code of types specified by given indices.
def dexfile_redirect_indices_typeidxs(dex, typeidxs_redir, methodidxs_redir,
                                      stridxs_redir, typeidxs):
    typeidxs = set(typeidxs)
    for classdef in dex.classDefs.items:
        typeid = classdef.classIdx
        idx = dex.get_idx_typeid(typeid)
        if idx not in typeidxs:
            continue
        class_redirect_indices(dex, classdef, typeidxs_redir,
                               methodidxs_redir, stridxs_redir)
        pass
    pass


## \brief Collect all type and string indices mentioned in the method code.
#
# \param method is a \ref _DEX_Method.
# \return a list of type indices mentioned in the code.
#
def collect_typeidxs_stridxs_in_method(dex, method):
    from paraspace.dexfile import _DEX_Method, DEXFile_linked
    from paraspace.dalvik_opcodes import decode_insn_blk, all_opcodes
    from itertools import chain
    
    assert isinstance(method, _DEX_Method)

    def get_typeidx_methodidx(methodidx):
        methodid = dex.find_methodid_idx(methodidx)
        method_typeid = methodid.classIdx
        method_typeidx = dex.get_idx_typeid(method_typeid)
        return method_typeidx

    def collect_types_in_op_vector(op_vector):
        code, args = op_vector
        
        if code == all_opcodes.OP_NEW_INSTANCE:
            return args[1]
        
        if code in (all_opcodes.OP_INVOKE_DIRECT,
                    all_opcodes.OP_INVOKE_VIRTUAL,
                    all_opcodes.OP_INVOKE_SUPER,
                    all_opcodes.OP_INVOKE_STATIC,
                    all_opcodes.OP_INVOKE_INTERFACE):
            methodidx = args[2]
            method_typeidx = get_typeidx_methodidx(methodidx)
            return method_typeidx

        if code in (all_opcodes.OP_INVOKE_VIRTUAL_RANGE,
                    all_opcodes.OP_INVOKE_DIRECT_RANGE,
                    all_opcodes.OP_INVOKE_SUPER_RANGE,
                    all_opcodes.OP_INVOKE_STATIC_RANGE,
                    all_opcodes.OP_INVOKE_INTERFACE_RANGE):
            methodidx = args[1]
            method_typeidx = get_typeidx_methodidx(methodidx)
            return method_typeidx

        return None

    def collect_strings_in_op_vector(op_vector):
        code, args = op_vector
        if code == all_opcodes.OP_CONST_STRING:
            stridx = args[1]
            return stridx
        
        return None

    code_blk = DEXFile_linked.get_code_block_method(method)
    op_vectors = decode_insn_blk(code_blk)
    types_insns = [collect_types_in_op_vector(op_vector)
                   for op_vector in op_vectors]
    typeidxs = [idx for idx in types_insns if idx is not None]

    strs_insns = [collect_strings_in_op_vector(op_vectors)
                  for op_vectors in op_vectors]
    stridxs = [idx for idx in strs_insns if idx is not None]
    
    return typeidxs, stridxs


## \brief Collect all type and string indices mentioned by the class code.
def collect_typeidxs_stridxs_mentioned_by_class(dex, classdef):
    from paraspace.dexfile import DEXFile_linked

    assert isinstance(dex, DEXFile_linked)
    
    typeidxs = set()
    stridxs = set()
    methods = DEXFile_linked.get_methods_classdef(classdef)
    for method in methods:
        method_typeidxs, method_stridxs = \
            collect_typeidxs_stridxs_in_method(dex, method)
        typeidxs.update(method_typeidxs)
        stridxs.update(method_stridxs)
        pass
    
    return list(typeidxs), list(stridxs)


## \brief Make a mapping for type indices of injection.
def make_typeidxs_map_after_injection(dex_dst, dex_src,
                                      relative_classdefs,
                                      relative_typeids):
    from paraspace.dexfile import DEXFile_linked
    
    def map_src_dst_typeid(typeid):
        idx_src = dex_src.get_idx_typeid(typeid)
        typename = DEXFile_linked.get_typeid_name(typeid)
        typeid_dst = dex_dst.find_typeid_name(typename)
        idx_dst = dex_dst.get_idx_typeid(typeid_dst)
        dex_dst.find_typeid_idx(idx_dst)
        return idx_src, idx_dst

    def map_src_dst_classdef(classdef):
        typeid = classdef.classIdx
        idx_src, idx_dst = map_src_dst_typeid(typeid)
        return idx_src, idx_dst
    
    typeidxs_classdefs = [map_src_dst_classdef(classdef)
                          for classdef in relative_classdefs]
    typeidxs_typeids = [map_src_dst_typeid(typeid)
                        for typeid in relative_typeids]
    typeidxs_map = dict(typeidxs_classdefs + typeidxs_typeids)
    return typeidxs_map


## \brief Redirect code for methods of injected classes.
def redirect_injected_code(dex_dst, dex_src, classdefs):
    relative_classdefs, relative_typeids, relative_strids = \
        collect_classdefs_relative(dex_src, classdefs)
    
    typeidxs_redir = \
        make_typeidxs_map_after_injection(dex_dst, dex_src, \
                                              relative_classdefs, \
                                              relative_typeids)
    methodidxs_redir = \
        make_methodidxs_redir_map(dex_src, dex_dst, typeidxs_redir)

    stridxs_redir = \
        make_stridxs_redir_map(dex_src, dex_dst)
    
    dexfile_redirect_indices_typeidxs(dex_dst, typeidxs_redir,
                                      methodidxs_redir,
                                      stridxs_redir,
                                      typeidxs_redir.values())
    pass


## \brief Inject classes and relative information to a DEX file.
#
# \param dex_dst is a DEXFile_linked where to inject classes.
# \param dex_src is a DEXFile_linked where the class is from.
# \param classdefs is a list of _DEX_ClassDef instances from \ref dex_src.
# \return a list of _DEX_ClassDef instances for injection.
#
def inject_classdefs(dex_dst, dex_src, classdefs):
    from paraspace.dexfile import DEXFile_linked
    
    assert isinstance(classdefs, (list, tuple))
    assert isinstance(dex_dst, DEXFile_linked)
    assert isinstance(dex_src, DEXFile_linked)

    injected_classdefs, injected_typeids, injected_strids = \
        dexfile_insert_classdefs_relative(dex_dst, dex_src, classdefs)
    redirect_injected_code(dex_dst, dex_src, classdefs)
    return injected_classdefs


## \brief Redirect all references of given class and its methods.
#
# Redirect all references of given class and its methods to target class.
#
def redirect_type(dex, src_classname, tgt_classname, exclude_classnames):
    src_typeid = dex.find_typeid_name(src_classname)
    src_typeidx = dex.get_idx_typeid(src_typeid)
    tgt_typeid = dex.find_typeid_name(tgt_classname)
    tgt_typeidx = dex.get_idx_typeid(tgt_typeid)
    typeidxs_redir = {src_typeidx: tgt_typeidx}
    
    methodidxs_redir = \
        make_methodidxs_redir_map(dex, dex, typeidxs_redir)

    stridxs_redir = {}
    
    ex_typeids = [dex.find_typeid_name(name)
                   for name in exclude_classnames]
    ex_typeidxs = [dex.get_idx_typeid(typeid)
                   for typeid in ex_typeids]
    dexfile_redirect_indices(dex, typeidxs_redir, methodidxs_redir,
                             stridxs_redir, excludes=ex_typeidxs)
    pass


## \brief Inject and redirect a _DEX_ClassDef from one linked to another.
#
# The _DEX_ClassDef given by inj_classname would be inserted to dst_linked,
# and redirect all invoking of type, given by redir_classname, to
# the injected one.
#
def inject_redir_no_restore(src_linked, inj_classname,
                            dst_linked, redir_classname, decls):
    inj_classdef = src_linked.find_class_name(inj_classname)
    injected_classdefs = inject_classdefs(dst_linked, src_linked,
                                          [inj_classdef])
    excludes = [dst_linked.get_classdef_name(classdef)
                for classdef in injected_classdefs]
    redirect_type(dst_linked, redir_classname, inj_classname, excludes)
    pass


## \brief Make indices map for typeid and methodid.
#
# It is used to create indices maps for typeid and methodid after
# changing order.  For example, after sorting sorted array after an
# injection, this function create maps for remapping indices mentioned
# in the code.
# 
def _make_idx_map(saved_typeids, saved_methodids, saved_strids,
                  new_typeids, new_methodids, new_strids):
    methodidxs_map = dict([(idx, new_methodids.index(methodid))
                           for idx, methodid in enumerate(saved_methodids)])
    typeidxs_map = dict([(idx, new_typeids.index(typeid))
                         for idx, typeid in enumerate(saved_typeids)])
    stridxs_map = dict([(idx, new_strids.index(strid))
                        for idx, strid in enumerate(saved_strids)])
    
    return typeidxs_map, methodidxs_map, stridxs_map


## \brief Sort sorted arrays and remapping indices for code blocks.
#
# Since sorting changes the order of sorted arrays, code blocks should
# be updated by remapping indices, typeid indices and methodid indices.
#
def dex_sort_sorted_arrays_consistent(dex_linked):
    from paraspace.dex_deptracker import dex_sort_sorted_arrays
    
    saved_typeids = list(dex_linked.typeIds.items)
    saved_methodids = list(dex_linked.methodIds.items)
    saved_strids = list(dex_linked.stringIds.items)
    
    dex_sort_sorted_arrays(dex_linked)

    new_typeids = dex_linked.typeIds.items
    new_methodids = dex_linked.methodIds.items
    new_strids = dex_linked.stringIds.items
    typeidxs_map, methodidxs_map, stridxs_map = \
        _make_idx_map(saved_typeids, saved_methodids, saved_strids, \
                          new_typeids, new_methodids, new_strids)
    
    dexfile_redirect_indices(dex_linked, typeidxs_map, methodidxs_map,
                             stridxs_map)
    pass


## \brief Inject and redirect a _DEX_ClassDef from one linked to another.
#
# The _DEX_ClassDef given by inj_classname would be inserted to dst_linked,
# and redirect all invoking of type, given by redir_classname, to
# the injected one.
#
def inject_redir(src_linked, inj_classname,
                 dst_linked, redir_classname, decls):
    from paraspace.dex_deptracker import restore_dependencies
    
    inject_redir_no_restore(src_linked, inj_classname,
                            dst_linked, redir_classname, decls)
    dex_sort_sorted_arrays_consistent(dst_linked)
    restore_dependencies(dst_linked, decls)
    pass