path: root/dexlib2/src/main/java/com/android/tools/smali/dexlib2/analysis/ClassProto.java

/*
 * Copyright 2013, Google LLC
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google LLC nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package com.android.tools.smali.dexlib2.analysis;

import com.android.tools.smali.dexlib2.AccessFlags;
import com.android.tools.smali.dexlib2.HiddenApiRestriction;
import com.android.tools.smali.dexlib2.analysis.util.MemoizingSupplier;
import com.android.tools.smali.dexlib2.analysis.util.TypeProtoUtils;
import com.android.tools.smali.dexlib2.base.reference.BaseMethodReference;
import com.android.tools.smali.dexlib2.iface.Annotation;
import com.android.tools.smali.dexlib2.iface.ClassDef;
import com.android.tools.smali.dexlib2.iface.Field;
import com.android.tools.smali.dexlib2.iface.Method;
import com.android.tools.smali.dexlib2.iface.MethodImplementation;
import com.android.tools.smali.dexlib2.iface.MethodParameter;
import com.android.tools.smali.dexlib2.iface.reference.FieldReference;
import com.android.tools.smali.dexlib2.iface.reference.MethodReference;
import com.android.tools.smali.dexlib2.util.AlignmentUtils;
import com.android.tools.smali.dexlib2.util.MethodUtil;
import com.android.tools.smali.util.ExceptionWithContext;
import com.android.tools.smali.util.IteratorUtils;
import com.android.tools.smali.util.SparseArray;
import com.android.tools.smali.util.StringUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.function.Supplier;
import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.util.Map.Entry;
import java.util.function.Predicate;

/**
 * A class "prototype". This contains things like the interfaces, the superclass, the vtable and the instance fields
 * and their offsets.
 */
public class ClassProto implements TypeProto {
    private static final byte REFERENCE = 0;
    private static final byte WIDE = 1;
    private static final byte OTHER = 2;

    @Nonnull protected final ClassPath classPath;
    @Nonnull protected final String type;

    protected boolean vtableFullyResolved = true;
    protected boolean interfacesFullyResolved = true;

    protected Set<String> unresolvedInterfaces = null;

    public ClassProto(@Nonnull ClassPath classPath, @Nonnull String type) {
        if (type.charAt(0) != 'L') {
            throw new ExceptionWithContext("Cannot construct ClassProto for non reference type: %s", type);
        }
        this.classPath = classPath;
        this.type = type;
    }

    @Override public String toString() { return type; }
    @Nonnull @Override public ClassPath getClassPath() { return classPath; }
    @Nonnull @Override public String getType() { return type; }

    @Nonnull
    public ClassDef getClassDef() {
        return classDefSupplier.get();
    }


    @Nonnull private final Supplier<ClassDef> classDefSupplier = MemoizingSupplier.memoize(new Supplier<ClassDef>() {
        @Override public ClassDef get() {
            return classPath.getClassDef(type);
        }
    });

    /**
     * Returns true if this class is an interface.
     *
     * If this class is not defined, then this will throw an UnresolvedClassException
     *
     * @return True if this class is an interface
     */
    public boolean isInterface() {
        ClassDef classDef = getClassDef();
        return (classDef.getAccessFlags() & AccessFlags.INTERFACE.getValue()) != 0;
    }

    /**
     * Returns the set of interfaces that this class implements as a Map<String, ClassDef>.
     *
     * The ClassDef value will be present only for the interfaces that this class directly implements (including any
     * interfaces transitively implemented), but not for any interfaces that are only implemented by a superclass of
     * this class
     *
     * For any interfaces that are only implemented by a superclass (or the class itself, if the class is an interface),
     * the value will be null.
     *
     * If any interface couldn't be resolved, then the interfacesFullyResolved field will be set to false upon return.
     *
     * @return the set of interfaces that this class implements as a Map<String, ClassDef>.
     */
    @Nonnull
    protected LinkedHashMap<String, ClassDef> getInterfaces() {
        if (!classPath.isArt() || classPath.oatVersion < 72) {
            return preDefaultMethodInterfaceSupplier.get();
        } else {
            return postDefaultMethodInterfaceSupplier.get();
        }
    }

    /**
     * This calculates the interfaces in the order required for vtable generation for dalvik and pre-default method ART
     */
    @Nonnull
    private final Supplier<LinkedHashMap<String, ClassDef>> preDefaultMethodInterfaceSupplier =
            MemoizingSupplier.memoize(new Supplier<LinkedHashMap<String, ClassDef>>() {
                @Override public LinkedHashMap<String, ClassDef> get() {
                    Set<String> unresolvedInterfaces = new HashSet<>(0);
                    LinkedHashMap<String, ClassDef> interfaces = new LinkedHashMap<>();

                    try {
                        for (String interfaceType: getClassDef().getInterfaces()) {
                            if (!interfaces.containsKey(interfaceType)) {
                                ClassDef interfaceDef;
                                try {
                                    interfaceDef = classPath.getClassDef(interfaceType);
                                    interfaces.put(interfaceType, interfaceDef);
                                } catch (UnresolvedClassException ex) {
                                    interfaces.put(interfaceType, null);
                                    unresolvedInterfaces.add(interfaceType);
                                    interfacesFullyResolved = false;
                                }

                                ClassProto interfaceProto = (ClassProto) classPath.getClass(interfaceType);
                                for (String superInterface: interfaceProto.getInterfaces().keySet()) {
                                    if (!interfaces.containsKey(superInterface)) {
                                        interfaces.put(superInterface,
                                                interfaceProto.getInterfaces().get(superInterface));
                                    }
                                }
                                if (!interfaceProto.interfacesFullyResolved) {
                                    unresolvedInterfaces.addAll(interfaceProto.getUnresolvedInterfaces());
                                    interfacesFullyResolved = false;
                                }
                            }
                        }
                    } catch (UnresolvedClassException ex) {
                        interfaces.put(type, null);
                        unresolvedInterfaces.add(type);
                        interfacesFullyResolved = false;
                    }

                    // now add self and super class interfaces, required for common super class lookup
                    // we don't really need ClassDef's for that, so let's just use null

                    if (isInterface() && !interfaces.containsKey(getType())) {
                        interfaces.put(getType(), null);
                    }

                    String superclass = getSuperclass();
                    try {
                        if (superclass != null) {
                            ClassProto superclassProto = (ClassProto) classPath.getClass(superclass);
                            for (String superclassInterface: superclassProto.getInterfaces().keySet()) {
                                if (!interfaces.containsKey(superclassInterface)) {
                                    interfaces.put(superclassInterface, null);
                                }
                            }
                            if (!superclassProto.interfacesFullyResolved) {
                                unresolvedInterfaces.addAll(superclassProto.getUnresolvedInterfaces());
                                interfacesFullyResolved = false;
                            }
                        }
                    } catch (UnresolvedClassException ex) {
                        unresolvedInterfaces.add(superclass);
                        interfacesFullyResolved = false;
                    }

                    if (unresolvedInterfaces.size() > 0) {
                        ClassProto.this.unresolvedInterfaces = unresolvedInterfaces;
                    }

                    return interfaces;
                }
            });

    /**
     * This calculates the interfaces in the order required for vtable generation for post-default method ART
     */
    @Nonnull
    private final Supplier<LinkedHashMap<String, ClassDef>> postDefaultMethodInterfaceSupplier =
            MemoizingSupplier.memoize(new Supplier<LinkedHashMap<String, ClassDef>>() {
                @Override public LinkedHashMap<String, ClassDef> get() {
                    Set<String> unresolvedInterfaces = new HashSet<String>(0);
                    LinkedHashMap<String, ClassDef> interfaces = new LinkedHashMap<>();

                    String superclass = getSuperclass();
                    if (superclass != null) {
                        ClassProto superclassProto = (ClassProto) classPath.getClass(superclass);
                        for (String superclassInterface: superclassProto.getInterfaces().keySet()) {
                            interfaces.put(superclassInterface, null);
                        }
                        if (!superclassProto.interfacesFullyResolved) {
                            unresolvedInterfaces.addAll(superclassProto.getUnresolvedInterfaces());
                            interfacesFullyResolved = false;
                        }
                    }

                    try {
                        for (String interfaceType: getClassDef().getInterfaces()) {
                            if (!interfaces.containsKey(interfaceType)) {
                                ClassProto interfaceProto = (ClassProto)classPath.getClass(interfaceType);
                                try {
                                    for (Entry<String, ClassDef> entry: interfaceProto.getInterfaces().entrySet()) {
                                        if (!interfaces.containsKey(entry.getKey())) {
                                            interfaces.put(entry.getKey(), entry.getValue());
                                        }
                                    }
                                } catch (UnresolvedClassException ex) {
                                    interfaces.put(interfaceType, null);
                                    unresolvedInterfaces.add(interfaceType);
                                    interfacesFullyResolved = false;
                                }
                                if (!interfaceProto.interfacesFullyResolved) {
                                    unresolvedInterfaces.addAll(interfaceProto.getUnresolvedInterfaces());
                                    interfacesFullyResolved = false;
                                }
                                try {
                                    ClassDef interfaceDef = classPath.getClassDef(interfaceType);
                                    interfaces.put(interfaceType, interfaceDef);
                                } catch (UnresolvedClassException ex) {
                                    interfaces.put(interfaceType, null);
                                    unresolvedInterfaces.add(interfaceType);
                                    interfacesFullyResolved = false;
                                }
                            }
                        }
                    } catch (UnresolvedClassException ex) {
                        interfaces.put(type, null);
                        unresolvedInterfaces.add(type);
                        interfacesFullyResolved = false;
                    }

                    if (unresolvedInterfaces.size() > 0) {
                        ClassProto.this.unresolvedInterfaces = unresolvedInterfaces;
                    }

                    return interfaces;
                }
            });

    @Nonnull
    protected Set<String> getUnresolvedInterfaces() {
        if (unresolvedInterfaces == null) {
            return Collections.emptySet();
        }
        return unresolvedInterfaces;
    }

    /**
     * Gets the interfaces directly implemented by this class, or the interfaces they transitively implement.
     *
     * This does not include any interfaces that are only implemented by a superclass
     *
     * @return An iterables of ClassDefs representing the directly or transitively implemented interfaces
     * @throws UnresolvedClassException if interfaces could not be fully resolved
     */
    @Nonnull
    protected Iterable<ClassDef> getDirectInterfaces() {
        Iterable<ClassDef> directInterfaces = IteratorUtils.filter(getInterfaces().values(), new Predicate<ClassDef>() {
            @Override public boolean test(@Nullable ClassDef input) {
                return input != null;
            }
        });

        if (!interfacesFullyResolved) {
            throw new UnresolvedClassException("Interfaces for class %s not fully resolved: %s", getType(),
                    StringUtils.join(getUnresolvedInterfaces(), ","));
        }

        return directInterfaces;
    }

    /**
     * Checks if this class implements the given interface.
     *
     * If the interfaces of this class cannot be fully resolved then this
     * method will either return true or throw an UnresolvedClassException
     *
     * @param iface The interface to check for
     * @return true if this class implements the given interface, otherwise false
     * @throws UnresolvedClassException if the interfaces for this class could not be fully resolved, and the interface
     * is not one of the interfaces that were successfully resolved
     */
    @Override
    public boolean implementsInterface(@Nonnull String iface) {
        if (getInterfaces().containsKey(iface)) {
            return true;
        }
        if (!interfacesFullyResolved) {
            throw new UnresolvedClassException("Interfaces for class %s not fully resolved", getType());
        }
        return false;
    }

    @Nullable @Override
    public String getSuperclass() {
        return getClassDef().getSuperclass();
    }

    /**
     * This is a helper method for getCommonSuperclass
     *
     * It checks if this class is an interface, and if so, if other implements it.
     *
     * If this class is undefined, we go ahead and check if it is listed in other's interfaces. If not, we throw an
     * UndefinedClassException
     *
     * If the interfaces of other cannot be fully resolved, we check the interfaces that can be resolved. If not found,
     * we throw an UndefinedClassException
     *
     * @param other The class to check the interfaces of
     * @return true if this class is an interface (or is undefined) other implements this class
     *
     */
    private boolean checkInterface(@Nonnull ClassProto other) {
        boolean isResolved = true;
        boolean isInterface = true;
        try {
            isInterface = isInterface();
        } catch (UnresolvedClassException ex) {
            isResolved = false;
            // if we don't know if this class is an interface or not,
            // we can still try to call other.implementsInterface(this)
        }
        if (isInterface) {
            try {
                if (other.implementsInterface(getType())) {
                    return true;
                }
            } catch (UnresolvedClassException ex) {
                // There are 2 possibilities here, depending on whether we were able to resolve this class.
                // 1. If this class is resolved, then we know it is an interface class. The other class either
                //    isn't defined, or its interfaces couldn't be fully resolved.
                //    In this case, we throw an UnresolvedClassException
                // 2. If this class is not resolved, we had tried to call implementsInterface anyway. We don't
                //    know for sure if this class is an interface or not. We return false, and let processing
                //    continue in getCommonSuperclass
                if (isResolved) {
                    throw ex;
                }
            }
        }
        return false;
    }

    @Override @Nonnull
    public TypeProto getCommonSuperclass(@Nonnull TypeProto other) {
        // use the other type's more specific implementation
        if (!(other instanceof ClassProto)) {
            return other.getCommonSuperclass(this);
        }

        if (this == other || getType().equals(other.getType())) {
            return this;
        }

        if (this.getType().equals("Ljava/lang/Object;")) {
            return this;
        }

        if (other.getType().equals("Ljava/lang/Object;")) {
            return other;
        }

        boolean gotException = false;
        try {
            if (checkInterface((ClassProto)other)) {
                return this;
            }
        } catch (UnresolvedClassException ex) {
            gotException = true;
        }

        try {
            if (((ClassProto)other).checkInterface(this)) {
                return other;
            }
        } catch (UnresolvedClassException ex) {
            gotException = true;
        }
        if (gotException) {
            return classPath.getUnknownClass();
        }

        List<TypeProto> thisChain = new ArrayList<>();
        thisChain.add(this);
        IteratorUtils.addAll(thisChain, TypeProtoUtils.getSuperclassChain(this).iterator());

        List<TypeProto> otherChain = new ArrayList<>();
        otherChain.add(other);
        IteratorUtils.addAll(otherChain, TypeProtoUtils.getSuperclassChain(other).iterator());

        // reverse them, so that the first entry is either Ljava/lang/Object; or Ujava/lang/Object;
        Collections.reverse(thisChain);
        Collections.reverse(otherChain);

        for (int i=Math.min(thisChain.size(), otherChain.size())-1; i>=0; i--) {
            TypeProto typeProto = thisChain.get(i);
            if (typeProto.getType().equals(otherChain.get(i).getType())) {
                return typeProto;
            }
        }

        return classPath.getUnknownClass();
    }

    @Override
    @Nullable
    public FieldReference getFieldByOffset(int fieldOffset) {
        if (getInstanceFields().size() == 0) {
            return null;
        }
        return getInstanceFields().get(fieldOffset);
    }

    @Override
    @Nullable
    public Method getMethodByVtableIndex(int vtableIndex) {
        List<Method> vtable = getVtable();
        if (vtableIndex < 0 || vtableIndex >= vtable.size()) {
            return null;
        }

        return vtable.get(vtableIndex);
    }

    public int findMethodIndexInVtable(@Nonnull MethodReference method) {
        return findMethodIndexInVtable(getVtable(), method);
    }

    private int findMethodIndexInVtable(@Nonnull List<Method> vtable, MethodReference method) {
        for (int i=0; i<vtable.size(); i++) {
            Method candidate = vtable.get(i);
            if (MethodUtil.methodSignaturesMatch(candidate, method)) {
                if (!classPath.shouldCheckPackagePrivateAccess() ||
                        AnalyzedMethodUtil.canAccess(this, candidate, true, false, false)) {
                    return i;
                }
            }
        }
        return -1;
    }

    private int findMethodIndexInVtableReverse(@Nonnull List<Method> vtable, MethodReference method) {
        for (int i=vtable.size() - 1; i>=0; i--) {
            Method candidate = vtable.get(i);
            if (MethodUtil.methodSignaturesMatch(candidate, method)) {
                if (!classPath.shouldCheckPackagePrivateAccess() ||
                        AnalyzedMethodUtil.canAccess(this, candidate, true, false, false)) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Nonnull public SparseArray<FieldReference> getInstanceFields() {
        if (classPath.isArt()) {
            return artInstanceFieldsSupplier.get();
        } else {
            return dalvikInstanceFieldsSupplier.get();
        }
    }

    @Nonnull private final Supplier<SparseArray<FieldReference>> dalvikInstanceFieldsSupplier =
            MemoizingSupplier.memoize(new Supplier<SparseArray<FieldReference>>() {
                @Override public SparseArray<FieldReference> get() {
                    //This is a bit of an "involved" operation. We need to follow the same algorithm that dalvik uses to
                    //arrange fields, so that we end up with the same field offsets (which is needed for deodexing).
                    //See mydroid/dalvik/vm/oo/Class.c - computeFieldOffsets()

                    ArrayList<Field> fields = getSortedInstanceFields(getClassDef());
                    final int fieldCount = fields.size();
                    //the "type" for each field in fields. 0=reference,1=wide,2=other
                    byte[] fieldTypes = new byte[fields.size()];
                    for (int i=0; i<fieldCount; i++) {
                        fieldTypes[i] = getFieldType(fields.get(i));
                    }

                    //The first operation is to move all of the reference fields to the front. To do this, find the first
                    //non-reference field, then find the last reference field, swap them and repeat
                    int back = fields.size() - 1;
                    int front;
                    for (front = 0; front<fieldCount; front++) {
                        if (fieldTypes[front] != REFERENCE) {
                            while (back > front) {
                                if (fieldTypes[back] == REFERENCE) {
                                    swap(fieldTypes, fields, front, back--);
                                    break;
                                }
                                back--;
                            }
                        }

                        if (fieldTypes[front] != REFERENCE) {
                            break;
                        }
                    }

                    int startFieldOffset = 8;
                    String superclassType = getSuperclass();
                    ClassProto superclass = null;
                    if (superclassType != null) {
                        superclass = (ClassProto) classPath.getClass(superclassType);
                        startFieldOffset = superclass.getNextFieldOffset();
                    }

                    int fieldIndexMod;
                    if ((startFieldOffset % 8) == 0) {
                        fieldIndexMod = 0;
                    } else {
                        fieldIndexMod = 1;
                    }

                    //next, we need to group all the wide fields after the reference fields. But the wide fields have to be
                    //8-byte aligned. If we're on an odd field index, we need to insert a 32-bit field. If the next field
                    //is already a 32-bit field, use that. Otherwise, find the first 32-bit field from the end and swap it in.
                    //If there are no 32-bit fields, do nothing for now. We'll add padding when calculating the field offsets
                    if (front < fieldCount && (front % 2) != fieldIndexMod) {
                        if (fieldTypes[front] == WIDE) {
                            //we need to swap in a 32-bit field, so the wide fields will be correctly aligned
                            back = fieldCount - 1;
                            while (back > front) {
                                if (fieldTypes[back] == OTHER) {
                                    swap(fieldTypes, fields, front++, back);
                                    break;
                                }
                                back--;
                            }
                        } else {
                            //there's already a 32-bit field here that we can use
                            front++;
                        }
                    }

                    //do the swap thing for wide fields
                    back = fieldCount - 1;
                    for (; front<fieldCount; front++) {
                        if (fieldTypes[front] != WIDE) {
                            while (back > front) {
                                if (fieldTypes[back] == WIDE) {
                                    swap(fieldTypes, fields, front, back--);
                                    break;
                                }
                                back--;
                            }
                        }

                        if (fieldTypes[front] != WIDE) {
                            break;
                        }
                    }

                    SparseArray<FieldReference> superFields;
                    if (superclass != null) {
                        superFields = superclass.getInstanceFields();
                    } else {
                        superFields = new SparseArray<FieldReference>();
                    }
                    int superFieldCount = superFields.size();

                    //now the fields are in the correct order. Add them to the SparseArray and lookup, and calculate the offsets
                    int totalFieldCount = superFieldCount + fieldCount;
                    SparseArray<FieldReference> instanceFields = new SparseArray<FieldReference>(totalFieldCount);

                    int fieldOffset;

                    if (superclass != null && superFieldCount > 0) {
                        for (int i=0; i<superFieldCount; i++) {
                            instanceFields.append(superFields.keyAt(i), superFields.valueAt(i));
                        }

                        fieldOffset = instanceFields.keyAt(superFieldCount-1);

                        FieldReference lastSuperField = superFields.valueAt(superFieldCount-1);
                        char fieldType = lastSuperField.getType().charAt(0);
                        if (fieldType == 'J' || fieldType == 'D') {
                            fieldOffset += 8;
                        } else {
                            fieldOffset += 4;
                        }
                    } else {
                        //the field values start at 8 bytes into the DataObject dalvik structure
                        fieldOffset = 8;
                    }

                    boolean gotDouble = false;
                    for (int i=0; i<fieldCount; i++) {
                        FieldReference field = fields.get(i);

                        //add padding to align the wide fields, if needed
                        if (fieldTypes[i] == WIDE && !gotDouble) {
                            if (fieldOffset % 8 != 0) {
                                assert fieldOffset % 8 == 4;
                                fieldOffset += 4;
                            }
                            gotDouble = true;
                        }

                        instanceFields.append(fieldOffset, field);
                        if (fieldTypes[i] == WIDE) {
                            fieldOffset += 8;
                        } else {
                            fieldOffset += 4;
                        }
                    }

                    return instanceFields;
                }

                @Nonnull
                private ArrayList<Field> getSortedInstanceFields(@Nonnull ClassDef classDef) {
                    ArrayList<Field> fields = (ArrayList<Field>)IteratorUtils.toList(classDef.getInstanceFields());
                    Collections.sort(fields);
                    return fields;
                }

                private void swap(byte[] fieldTypes, List<Field> fields, int position1, int position2) {
                    byte tempType = fieldTypes[position1];
                    fieldTypes[position1] = fieldTypes[position2];
                    fieldTypes[position2] = tempType;

                    Field tempField = fields.set(position1, fields.get(position2));
                    fields.set(position2, tempField);
                }
            });

    private static abstract class FieldGap implements Comparable<FieldGap> {
        public final int offset;
        public final int size;

        public static FieldGap newFieldGap(int offset, int size, int oatVersion) {
            if (oatVersion >= 67) {
                return new FieldGap(offset, size) {
                    @Override public int compareTo(@Nonnull FieldGap o) {
                        int result = Integer.compare(o.size, size);
                        if (result != 0) {
                            return result;
                        }
                        return Integer.compare(offset, o.offset);
                    }
                };
            } else {
                return new FieldGap(offset, size) {
                    @Override public int compareTo(@Nonnull FieldGap o) {
                        int result = Integer.compare(size, o.size);
                        if (result != 0) {
                            return result;
                        }
                        return Integer.compare(o.offset, offset);
                    }
                };
            }
        }

        private FieldGap(int offset, int size) {
            this.offset = offset;
            this.size = size;
        }
    }

    @Nonnull private final Supplier<SparseArray<FieldReference>> artInstanceFieldsSupplier =
            MemoizingSupplier.memoize(new Supplier<SparseArray<FieldReference>>() {

                @Override public SparseArray<FieldReference> get() {
                    // We need to follow the same algorithm that art uses to arrange fields, so that we end up with the
                    // same field offsets, which is needed for deodexing.
                    // See LinkFields() in art/runtime/class_linker.cc

                    PriorityQueue<FieldGap> gaps = new PriorityQueue<FieldGap>();

                    SparseArray<FieldReference> linkedFields = new SparseArray<FieldReference>();
                    ArrayList<Field> fields = getSortedInstanceFields(getClassDef());

                    int fieldOffset = 0;
                    String superclassType = getSuperclass();
                    if (superclassType != null) {
                        // TODO: what to do if superclass doesn't exist?
                        ClassProto superclass = (ClassProto) classPath.getClass(superclassType);
                        SparseArray<FieldReference> superFields = superclass.getInstanceFields();
                        FieldReference field = null;
                        int lastOffset = 0;
                        for (int i=0; i<superFields.size(); i++) {
                            int offset = superFields.keyAt(i);
                            field = superFields.valueAt(i);
                            linkedFields.put(offset, field);
                            lastOffset = offset;
                        }
                        if (field != null) {
                            fieldOffset = lastOffset + getFieldSize(field);
                        }
                    }

                    for (Field field: fields) {
                        int fieldSize = getFieldSize(field);

                        if (!AlignmentUtils.isAligned(fieldOffset, fieldSize)) {
                            int oldOffset = fieldOffset;
                            fieldOffset = AlignmentUtils.alignOffset(fieldOffset, fieldSize);
                            addFieldGap(oldOffset, fieldOffset, gaps);
                        }

                        FieldGap gap = gaps.peek();
                        if (gap != null && gap.size >= fieldSize) {
                            gaps.poll();
                            linkedFields.put(gap.offset, field);
                            if (gap.size > fieldSize) {
                                addFieldGap(gap.offset + fieldSize, gap.offset + gap.size, gaps);
                            }
                        } else {
                            linkedFields.append(fieldOffset, field);
                            fieldOffset += fieldSize;
                        }
                    }

                    return linkedFields;
                }

                private void addFieldGap(int gapStart, int gapEnd, @Nonnull PriorityQueue<FieldGap> gaps) {
                    int offset = gapStart;

                    while (offset < gapEnd) {
                        int remaining = gapEnd - offset;

                        if ((remaining >= 4) && (offset % 4 == 0)) {
                            gaps.add(FieldGap.newFieldGap(offset, 4, classPath.oatVersion));
                            offset += 4;
                        } else if (remaining >= 2 && (offset % 2 == 0)) {
                            gaps.add(FieldGap.newFieldGap(offset, 2, classPath.oatVersion));
                            offset += 2;
                        } else {
                            gaps.add(FieldGap.newFieldGap(offset, 1, classPath.oatVersion));
                            offset += 1;
                        }
                    }
                }

                @Nonnull
                private ArrayList<Field> getSortedInstanceFields(@Nonnull ClassDef classDef) {
                    ArrayList<Field> fields = (ArrayList<Field>)IteratorUtils.toList(classDef.getInstanceFields());
                    Collections.sort(fields, new Comparator<Field>() {
                        @Override public int compare(Field field1, Field field2) {
                            int result = Integer.compare(getFieldSortOrder(field1), getFieldSortOrder(field2));
                            if (result != 0) {
                                return result;
                            }

                            result = field1.getName().compareTo(field2.getName());
                            if (result != 0) {
                                return result;
                            }
                            return field1.getType().compareTo(field2.getType());
                        }
                    });
                    return fields;
                }

                private int getFieldSortOrder(@Nonnull FieldReference field) {
                    // The sort order is based on type size (except references are first), and then based on the
                    // enum value of the primitive type for types of equal size. See: Primitive::Type enum
                    // in art/runtime/primitive.h
                    switch (field.getType().charAt(0)) {
                        /* reference */
                        case '[':
                        case 'L':
                            return 0;
                        /* 64 bit */
                        case 'J':
                            return 1;
                        case 'D':
                            return 2;
                        /* 32 bit */
                        case 'I':
                            return 3;
                        case 'F':
                            return 4;
                        /* 16 bit */
                        case 'C':
                            return 5;
                        case 'S':
                            return 6;
                        /* 8 bit */
                        case 'Z':
                            return 7;
                        case 'B':
                            return 8;
                    }
                    throw new ExceptionWithContext("Invalid field type: %s", field.getType());
                }

                private int getFieldSize(@Nonnull FieldReference field) {
                    return getTypeSize(field.getType().charAt(0));
                }
            });

    private int getNextFieldOffset() {
        SparseArray<FieldReference> instanceFields = getInstanceFields();
        if (instanceFields.size() == 0) {
            return classPath.isArt() ? 0 : 8;
        }

        int lastItemIndex = instanceFields.size()-1;
        int fieldOffset = instanceFields.keyAt(lastItemIndex);
        FieldReference lastField = instanceFields.valueAt(lastItemIndex);

        if (classPath.isArt()) {
            return fieldOffset + getTypeSize(lastField.getType().charAt(0));
        } else {
            switch (lastField.getType().charAt(0)) {
                case 'J':
                case 'D':
                    return fieldOffset + 8;
                default:
                    return fieldOffset + 4;
            }
        }
    }

    private static int getTypeSize(char type) {
        switch (type) {
            case 'J':
            case 'D':
                return 8;
            case '[':
            case 'L':
            case 'I':
            case 'F':
                return 4;
            case 'C':
            case 'S':
                return 2;
            case 'B':
            case 'Z':
                return 1;
        }
        throw new ExceptionWithContext("Invalid type: %s", type);
    }

    @Nonnull public List<Method> getVtable() {
        if (!classPath.isArt() || classPath.oatVersion < 72) {
            return preDefaultMethodVtableSupplier.get();
        } else if (classPath.oatVersion < 87) {
            return buggyPostDefaultMethodVtableSupplier.get();
        } else {
            return postDefaultMethodVtableSupplier.get();
        }
    }

    //TODO: check the case when we have a package private method that overrides an interface method
    @Nonnull private final Supplier<List<Method>> preDefaultMethodVtableSupplier = MemoizingSupplier.memoize(new Supplier<List<Method>>() {
        @Override public List<Method> get() {
            List<Method> vtable = new ArrayList<>();

            //copy the virtual methods from the superclass
            String superclassType;
            try {
                superclassType = getSuperclass();
            } catch (UnresolvedClassException ex) {
                vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable());
                vtableFullyResolved = false;
                return vtable;
            }

            if (superclassType != null) {
                ClassProto superclass = (ClassProto) classPath.getClass(superclassType);
                vtable.addAll(superclass.getVtable());

                // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by this
                // class should start, so we just propagate what we can from the parent and hope for the best.
                if (!superclass.vtableFullyResolved) {
                    vtableFullyResolved = false;
                    return vtable;
                }
            }

            //iterate over the virtual methods in the current class, and only add them when we don't already have the
            //method (i.e. if it was implemented by the superclass)
            if (!isInterface()) {
                addToVtable(getClassDef().getVirtualMethods(), vtable, true, true);

                // We use the current class for any vtable method references that we add, rather than the interface, so
                // we don't end up trying to call invoke-virtual using an interface, which will fail verification
                Iterable<ClassDef> interfaces = getDirectInterfaces();
                for (ClassDef interfaceDef: interfaces) {
                    List<Method> interfaceMethods = new ArrayList<>();
                    for (Method interfaceMethod: interfaceDef.getVirtualMethods()) {
                        interfaceMethods.add(new ReparentedMethod(interfaceMethod, type));
                    }
                    addToVtable(interfaceMethods, vtable, false, true);
                }
            }
            return vtable;
        }
    });

    /**
     * This is the vtable supplier for a version of art that had buggy vtable calculation logic. In some cases it can
     * produce multiple vtable entries for a given virtual method. This supplier duplicates this buggy logic in order to
     * generate an identical vtable
     */
    @Nonnull private final Supplier<List<Method>> buggyPostDefaultMethodVtableSupplier = MemoizingSupplier.memoize(new Supplier<List<Method>>() {
        @Override public List<Method> get() {
            List<Method> vtable = new ArrayList<>();

            //copy the virtual methods from the superclass
            String superclassType;
            try {
                superclassType = getSuperclass();
            } catch (UnresolvedClassException ex) {
                vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable());
                vtableFullyResolved = false;
                return vtable;
            }

            if (superclassType != null) {
                ClassProto superclass = (ClassProto) classPath.getClass(superclassType);
                vtable.addAll(superclass.getVtable());

                // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by
                // this class should start, so we just propagate what we can from the parent and hope for the best.
                if (!superclass.vtableFullyResolved) {
                    vtableFullyResolved = false;
                    return vtable;
                }
            }

            //iterate over the virtual methods in the current class, and only add them when we don't already have the
            //method (i.e. if it was implemented by the superclass)
            if (!isInterface()) {
                addToVtable(getClassDef().getVirtualMethods(), vtable, true, true);

                List<String> interfaces = new ArrayList<>(getInterfaces().keySet());

                List<Method> defaultMethods = new ArrayList<>();
                List<Method> defaultConflictMethods = new ArrayList<>();
                List<Method> mirandaMethods = new ArrayList<>();

                final HashMap<MethodReference, Integer> methodOrder = new HashMap<>();

                for (int i=interfaces.size()-1; i>=0; i--) {
                    String interfaceType = interfaces.get(i);
                    ClassDef interfaceDef = classPath.getClassDef(interfaceType);

                    for (Method interfaceMethod : interfaceDef.getVirtualMethods()) {

                        int vtableIndex = findMethodIndexInVtableReverse(vtable, interfaceMethod);
                        Method oldVtableMethod = null;
                        if (vtableIndex >= 0) {
                            oldVtableMethod = vtable.get(vtableIndex);
                        }

                        for (int j=0; j<vtable.size(); j++) {
                            Method candidate = vtable.get(j);
                            if (MethodUtil.methodSignaturesMatch(candidate, interfaceMethod)) {
                                if (!classPath.shouldCheckPackagePrivateAccess() ||
                                        AnalyzedMethodUtil.canAccess(ClassProto.this, candidate, true, false, false)) {
                                    if (interfaceMethodOverrides(interfaceMethod, candidate)) {
                                        vtable.set(j, interfaceMethod);
                                    }
                                }
                            }
                        }

                        if (vtableIndex >= 0) {
                            if (!isOverridableByDefaultMethod(vtable.get(vtableIndex))) {
                                continue;
                            }
                        }

                        int defaultMethodIndex = findMethodIndexInVtable(defaultMethods, interfaceMethod);

                        if (defaultMethodIndex >= 0) {
                            if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) {
                                ClassProto existingInterface = (ClassProto)classPath.getClass(
                                        defaultMethods.get(defaultMethodIndex).getDefiningClass());
                                if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) {
                                    Method removedMethod = defaultMethods.remove(defaultMethodIndex);
                                    defaultConflictMethods.add(removedMethod);
                                }
                            }
                            continue;
                        }

                        int defaultConflictMethodIndex = findMethodIndexInVtable(
                                defaultConflictMethods, interfaceMethod);
                        if (defaultConflictMethodIndex >= 0) {
                            // There's already a matching method in the conflict list, we don't need to do
                            // anything else
                            continue;
                        }

                        int mirandaMethodIndex = findMethodIndexInVtable(mirandaMethods, interfaceMethod);

                        if (mirandaMethodIndex >= 0) {
                            if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) {

                                ClassProto existingInterface = (ClassProto)classPath.getClass(
                                        mirandaMethods.get(mirandaMethodIndex).getDefiningClass());
                                if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) {
                                    Method oldMethod = mirandaMethods.remove(mirandaMethodIndex);
                                    int methodOrderValue = methodOrder.get(oldMethod);
                                    methodOrder.put(interfaceMethod, methodOrderValue);
                                    defaultMethods.add(interfaceMethod);
                                }
                            }
                            continue;
                        }

                        if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) {
                            if (oldVtableMethod != null) {
                                if (!interfaceMethodOverrides(interfaceMethod, oldVtableMethod)) {
                                    continue;
                                }
                            }
                            defaultMethods.add(interfaceMethod);
                            methodOrder.put(interfaceMethod, methodOrder.size());
                        } else {
                            // TODO: do we need to check interfaceMethodOverrides here?
                            if (oldVtableMethod == null) {
                                mirandaMethods.add(interfaceMethod);
                                methodOrder.put(interfaceMethod, methodOrder.size());
                            }
                        }
                    }
                }

                Comparator<MethodReference> comparator = new Comparator<MethodReference>() {
                    @Override public int compare(MethodReference o1, MethodReference o2) {
                        return Integer.compare(methodOrder.get(o1), methodOrder.get(o2));
                    }
                };

                // The methods should be in the same order within each list as they were iterated over.
                // They can be misordered if, e.g. a method was originally added to the default list, but then moved
                // to the conflict list.
                Collections.sort(mirandaMethods, comparator);
                Collections.sort(defaultMethods, comparator);
                Collections.sort(defaultConflictMethods, comparator);

                vtable.addAll(mirandaMethods);
                vtable.addAll(defaultMethods);
                vtable.addAll(defaultConflictMethods);
            }
            return vtable;
        }
    });

    @Nonnull private final Supplier<List<Method>> postDefaultMethodVtableSupplier = MemoizingSupplier.memoize(new Supplier<List<Method>>() {
        @Override public List<Method> get() {
            List<Method> vtable = new ArrayList<>();

            //copy the virtual methods from the superclass
            String superclassType;
            try {
                superclassType = getSuperclass();
            } catch (UnresolvedClassException ex) {
                vtable.addAll(((ClassProto)classPath.getClass("Ljava/lang/Object;")).getVtable());
                vtableFullyResolved = false;
                return vtable;
            }

            if (superclassType != null) {
                ClassProto superclass = (ClassProto) classPath.getClass(superclassType);
                vtable.addAll(superclass.getVtable());

                // if the superclass's vtable wasn't fully resolved, then we can't know where the new methods added by
                // this class should start, so we just propagate what we can from the parent and hope for the best.
                if (!superclass.vtableFullyResolved) {
                    vtableFullyResolved = false;
                    return vtable;
                }
            }

            //iterate over the virtual methods in the current class, and only add them when we don't already have the
            //method (i.e. if it was implemented by the superclass)
            if (!isInterface()) {
                addToVtable(getClassDef().getVirtualMethods(), vtable, true, true);

                List<ClassDef> interfaces = IteratorUtils.toList(getDirectInterfaces());
                Collections.reverse(interfaces);

                List<Method> defaultMethods = new ArrayList<>();
                List<Method> defaultConflictMethods = new ArrayList<>();
                List<Method> mirandaMethods = new ArrayList<>();

                final HashMap<MethodReference, Integer> methodOrder = new HashMap<>();

                for (ClassDef interfaceDef: interfaces) {
                    for (Method interfaceMethod : interfaceDef.getVirtualMethods()) {

                        int vtableIndex = findMethodIndexInVtable(vtable, interfaceMethod);

                        if (vtableIndex >= 0) {
                            if (interfaceMethodOverrides(interfaceMethod, vtable.get(vtableIndex))) {
                                vtable.set(vtableIndex, interfaceMethod);
                            }
                        } else {
                            int defaultMethodIndex = findMethodIndexInVtable(defaultMethods, interfaceMethod);

                            if (defaultMethodIndex >= 0) {
                                if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) {
                                    ClassProto existingInterface = (ClassProto)classPath.getClass(
                                            defaultMethods.get(defaultMethodIndex).getDefiningClass());
                                    if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) {
                                        Method removedMethod = defaultMethods.remove(defaultMethodIndex);
                                        defaultConflictMethods.add(removedMethod);
                                    }
                                }
                                continue;
                            }

                            int defaultConflictMethodIndex = findMethodIndexInVtable(
                                    defaultConflictMethods, interfaceMethod);
                            if (defaultConflictMethodIndex >= 0) {
                                // There's already a matching method in the conflict list, we don't need to do
                                // anything else
                                continue;
                            }

                            int mirandaMethodIndex = findMethodIndexInVtable(mirandaMethods, interfaceMethod);

                            if (mirandaMethodIndex >= 0) {
                                if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) {

                                    ClassProto existingInterface = (ClassProto)classPath.getClass(
                                            mirandaMethods.get(mirandaMethodIndex).getDefiningClass());
                                    if (!existingInterface.implementsInterface(interfaceMethod.getDefiningClass())) {
                                        Method oldMethod = mirandaMethods.remove(mirandaMethodIndex);
                                        int methodOrderValue = methodOrder.get(oldMethod);
                                        methodOrder.put(interfaceMethod, methodOrderValue);
                                        defaultMethods.add(interfaceMethod);
                                    }
                                }
                                continue;
                            }

                            if (!AccessFlags.ABSTRACT.isSet(interfaceMethod.getAccessFlags())) {
                                defaultMethods.add(interfaceMethod);
                                methodOrder.put(interfaceMethod, methodOrder.size());
                            } else {
                                mirandaMethods.add(interfaceMethod);
                                methodOrder.put(interfaceMethod, methodOrder.size());
                            }
                        }
                    }
                }

                Comparator<MethodReference> comparator = new Comparator<MethodReference>() {
                    @Override public int compare(MethodReference o1, MethodReference o2) {
                        return Integer.compare(methodOrder.get(o1), methodOrder.get(o2));
                    }
                };

                // The methods should be in the same order within each list as they were iterated over.
                // They can be misordered if, e.g. a method was originally added to the default list, but then moved
                // to the conflict list.
                Collections.sort(defaultMethods, comparator);
                Collections.sort(defaultConflictMethods, comparator);
                Collections.sort(mirandaMethods, comparator);
                addToVtable(defaultMethods, vtable, false, false);
                addToVtable(defaultConflictMethods, vtable, false, false);
                addToVtable(mirandaMethods, vtable, false, false);
            }
            return vtable;
        }
    });

    private void addToVtable(@Nonnull Iterable<? extends Method> localMethods, @Nonnull List<Method> vtable,
                             boolean replaceExisting, boolean sort) {
        if (sort) {
            ArrayList<Method> methods = (ArrayList<Method>)IteratorUtils.toList(localMethods);
            Collections.sort(methods);
            localMethods = methods;
        }

        for (Method virtualMethod: localMethods) {
            int vtableIndex = findMethodIndexInVtable(vtable, virtualMethod);

            if (vtableIndex >= 0) {
                if (replaceExisting) {
                    vtable.set(vtableIndex, virtualMethod);
                }
            } else {
                // we didn't find an equivalent method, so add it as a new entry
                vtable.add(virtualMethod);
            }
        }
    }

    private static byte getFieldType(@Nonnull FieldReference field) {
        switch (field.getType().charAt(0)) {
            case '[':
            case 'L':
                return 0; //REFERENCE
            case 'J':
            case 'D':
                return 1; //WIDE
            default:
                return 2; //OTHER
        }
    }

    private boolean isOverridableByDefaultMethod(@Nonnull Method method) {
        ClassProto classProto = (ClassProto)classPath.getClass(method.getDefiningClass());
        return classProto.isInterface();
    }

    /**
     * Checks if the interface method overrides the virtual or interface method2
     * @param method A Method from an interface
     * @param method2 A Method from an interface or a class
     * @return true if the interface method overrides the virtual or interface method2
     */
    private boolean interfaceMethodOverrides(@Nonnull Method method, @Nonnull Method method2) {
        ClassProto classProto = (ClassProto)classPath.getClass(method2.getDefiningClass());

        if (classProto.isInterface()) {
            ClassProto targetClassProto = (ClassProto)classPath.getClass(method.getDefiningClass());
            return targetClassProto.implementsInterface(method2.getDefiningClass());
        } else {
            return false;
        }
    }

    static class ReparentedMethod extends BaseMethodReference implements Method {
        private final Method method;
        private final String definingClass;

        public ReparentedMethod(Method method, String definingClass) {
            this.method = method;
            this.definingClass = definingClass;
        }

        @Nonnull @Override public String getDefiningClass() {
            return definingClass;
        }

        @Nonnull @Override public String getName() {
            return method.getName();
        }

        @Nonnull @Override public List<? extends CharSequence> getParameterTypes() {
            return method.getParameterTypes();
        }

        @Nonnull @Override public String getReturnType() {
            return method.getReturnType();
        }

        @Nonnull @Override public List<? extends MethodParameter> getParameters() {
            return method.getParameters();
        }

        @Override public int getAccessFlags() {
            return method.getAccessFlags();
        }

        @Nonnull @Override public Set<? extends Annotation> getAnnotations() {
            return method.getAnnotations();
        }

        @Nonnull @Override public Set<HiddenApiRestriction> getHiddenApiRestrictions() {
            return method.getHiddenApiRestrictions();
        }

        @Nullable @Override public MethodImplementation getImplementation() {
            return method.getImplementation();
        }
    }
}