tools/dexfuzz/src/dexfuzz/program/IdCreator.java

/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package dexfuzz.program;

import dexfuzz.Log;
import dexfuzz.rawdex.FieldIdItem;
import dexfuzz.rawdex.MethodIdItem;
import dexfuzz.rawdex.Offset;
import dexfuzz.rawdex.Offsettable;
import dexfuzz.rawdex.ProtoIdItem;
import dexfuzz.rawdex.RawDexFile;
import dexfuzz.rawdex.RawDexObject.IndexUpdateKind;
import dexfuzz.rawdex.StringDataItem;
import dexfuzz.rawdex.StringIdItem;
import dexfuzz.rawdex.TypeIdItem;
import dexfuzz.rawdex.TypeItem;
import dexfuzz.rawdex.TypeList;

import java.util.ArrayList;
import java.util.List;

/**
 * Responsible for the finding and creation of TypeIds, MethodIds, FieldIds, and StringIds,
 * during mutation.
 */
public class IdCreator {
  private RawDexFile rawDexFile;

  public IdCreator(RawDexFile rawDexFile) {
    this.rawDexFile = rawDexFile;
  }

  private int findProtoIdInsertionPoint(String signature) {
    int returnTypeIdx = findTypeId(convertSignatureToReturnType(signature));
    String[] parameterListStrings = convertSignatureToParameterList(signature);
    TypeList parameterList = null;
    if (parameterListStrings.length > 0) {
      parameterList = findTypeList(parameterListStrings);
    }

    if (returnTypeIdx < 0) {
      Log.errorAndQuit("Did not create necessary return type before finding insertion "
          + "point for new proto!");
    }

    if (parameterListStrings.length > 0 && parameterList == null) {
      Log.errorAndQuit("Did not create necessary parameter list before finding insertion "
          + "point for new proto!");
    }

    int protoIdIdx = 0;
    for (ProtoIdItem protoId : rawDexFile.protoIds) {
      if (returnTypeIdx < protoId.returnTypeIdx) {
        break;
      }
      if (returnTypeIdx == protoId.returnTypeIdx
          && parameterListStrings.length == 0) {
        break;
      }
      if (returnTypeIdx == protoId.returnTypeIdx
          && parameterListStrings.length > 0
          && protoId.parametersOff.pointsToSomething()
          && parameterList.comesBefore(
              (TypeList) protoId.parametersOff.getPointedToItem())) {
        break;
      }
      protoIdIdx++;
    }
    return protoIdIdx;
  }

  private int findMethodIdInsertionPoint(String className, String methodName, String signature) {
    int classIdx = findTypeId(className);
    int nameIdx = findString(methodName);
    int protoIdx = findProtoId(signature);

    if (classIdx < 0 || nameIdx < 0 || protoIdx < 0) {
      Log.errorAndQuit("Did not create necessary class, name or proto strings before finding "
          + " insertion point for new method!");
    }

    int methodIdIdx = 0;
    for (MethodIdItem methodId : rawDexFile.methodIds) {
      if (classIdx < methodId.classIdx) {
        break;
      }
      if (classIdx == methodId.classIdx && nameIdx < methodId.nameIdx) {
        break;
      }
      if (classIdx == methodId.classIdx && nameIdx == methodId.nameIdx
          && protoIdx < methodId.protoIdx) {
        break;
      }
      methodIdIdx++;
    }
    return methodIdIdx;
  }

  private int findTypeIdInsertionPoint(String className) {
    int descriptorIdx = findString(className);

    if (descriptorIdx < 0) {
      Log.errorAndQuit("Did not create necessary descriptor string before finding "
          + " insertion point for new type!");
    }

    int typeIdIdx = 0;
    for (TypeIdItem typeId : rawDexFile.typeIds) {
      if (descriptorIdx < typeId.descriptorIdx) {
        break;
      }
      typeIdIdx++;
    }
    return typeIdIdx;
  }

  private int findStringDataInsertionPoint(String string) {
    int stringDataIdx = 0;
    for (StringDataItem stringData : rawDexFile.stringDatas) {
      if (stringData.getSize() > 0 && stringData.getString().compareTo(string) >= 0) {
        break;
      }
      stringDataIdx++;
    }
    return stringDataIdx;
  }

  private int findFieldIdInsertionPoint(String className, String typeName, String fieldName) {
    int classIdx = findTypeId(className);
    int typeIdx = findTypeId(typeName);
    int nameIdx = findString(fieldName);

    if (classIdx < 0 || typeIdx < 0 || nameIdx < 0) {
      Log.errorAndQuit("Did not create necessary class, type or name strings before finding "
          + " insertion point for new field!");
    }

    int fieldIdIdx = 0;
    for (FieldIdItem fieldId : rawDexFile.fieldIds) {
      if (classIdx < fieldId.classIdx) {
        break;
      }
      if (classIdx == fieldId.classIdx && nameIdx < fieldId.nameIdx) {
        break;
      }
      if (classIdx == fieldId.classIdx && nameIdx == fieldId.nameIdx
          && typeIdx < fieldId.typeIdx) {
        break;
      }
      fieldIdIdx++;
    }
    return fieldIdIdx;
  }

  private int createMethodId(String className, String methodName, String signature) {
    if (rawDexFile.methodIds.size() >= 65536) {
      Log.errorAndQuit("Referenced too many methods for the DEX file.");
    }

    // Search for (or create) the prototype.
    int protoIdx = findOrCreateProtoId(signature);

    // Search for (or create) the owning class.
    // NB: findOrCreateProtoId could create new types, so this must come
    //     after it!
    int typeIdIdx = findOrCreateTypeId(className);

    // Search for (or create) the string representing the method name.
    // NB: findOrCreateProtoId/TypeId could create new strings, so this must come
    //     after them!
    int methodNameStringIdx = findOrCreateString(methodName);

    // Create MethodIdItem.
    MethodIdItem newMethodId = new MethodIdItem();
    newMethodId.classIdx = (short) typeIdIdx;
    newMethodId.protoIdx = (short) protoIdx;
    newMethodId.nameIdx = methodNameStringIdx;

    // MethodIds must be ordered.
    int newMethodIdIdx = findMethodIdInsertionPoint(className, methodName, signature);

    rawDexFile.methodIds.add(newMethodIdIdx, newMethodId);

    // Insert into OffsetTracker.
    if (newMethodIdIdx == 0) {
      rawDexFile.getOffsetTracker()
        .insertNewOffsettableAsFirstOfType(newMethodId, rawDexFile);
    } else {
      MethodIdItem prevMethodId = rawDexFile.methodIds.get(newMethodIdIdx - 1);
      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newMethodId, prevMethodId);
    }

    Log.info(String.format("Created new MethodIdItem for %s %s %s, index: 0x%04x",
        className, methodName, signature, newMethodIdIdx));

    // Now that we've potentially moved a lot of method IDs along, all references
    // to them need to be updated.
    rawDexFile.incrementIndex(IndexUpdateKind.METHOD_ID, newMethodIdIdx);

    // All done, return the index for the new method.
    return newMethodIdIdx;
  }

  private int findMethodId(String className, String methodName, String signature) {
    int classIdx = findTypeId(className);
    if (classIdx == -1) {
      return -1;
    }
    int nameIdx = findString(methodName);
    if (nameIdx == -1) {
      return -1;
    }
    int protoIdx = findProtoId(signature);
    if (nameIdx == -1) {
      return -1;
    }

    int methodIdIdx = 0;
    for (MethodIdItem methodId : rawDexFile.methodIds) {
      if (classIdx == methodId.classIdx
          && nameIdx == methodId.nameIdx
          && protoIdx == methodId.protoIdx) {
        return methodIdIdx;
      }
      methodIdIdx++;
    }
    return -1;
  }

  /**
   * Given a fully qualified class name (Ljava/lang/System;), method name (gc) and
   * and signature (()V), either find the MethodId in our DEX file's table, or create it.
   */
  public int findOrCreateMethodId(String className, String methodName, String shorty) {
    int methodIdIdx = findMethodId(className, methodName, shorty);
    if (methodIdIdx != -1) {
      return methodIdIdx;
    }
    return createMethodId(className, methodName, shorty);
  }

  private int createTypeId(String className) {
    if (rawDexFile.typeIds.size() >= 65536) {
      Log.errorAndQuit("Referenced too many classes for the DEX file.");
    }

    // Search for (or create) the string representing the class descriptor.
    int descriptorStringIdx = findOrCreateString(className);

    // Create TypeIdItem.
    TypeIdItem newTypeId = new TypeIdItem();
    newTypeId.descriptorIdx = descriptorStringIdx;

    // TypeIds must be ordered.
    int newTypeIdIdx = findTypeIdInsertionPoint(className);

    rawDexFile.typeIds.add(newTypeIdIdx, newTypeId);

    // Insert into OffsetTracker.
    if (newTypeIdIdx == 0) {
      rawDexFile.getOffsetTracker().insertNewOffsettableAsFirstOfType(newTypeId, rawDexFile);
    } else {
      TypeIdItem prevTypeId = rawDexFile.typeIds.get(newTypeIdIdx - 1);
      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newTypeId, prevTypeId);
    }

    Log.info(String.format("Created new ClassIdItem for %s, index: 0x%04x",
        className, newTypeIdIdx));

    // Now that we've potentially moved a lot of type IDs along, all references
    // to them need to be updated.
    rawDexFile.incrementIndex(IndexUpdateKind.TYPE_ID, newTypeIdIdx);

    // All done, return the index for the new class.
    return newTypeIdIdx;
  }

  private int findTypeId(String className) {
    int descriptorIdx = findString(className);
    if (descriptorIdx == -1) {
      return -1;
    }

    // Search for class.
    int typeIdIdx = 0;
    for (TypeIdItem typeId : rawDexFile.typeIds) {
      if (descriptorIdx == typeId.descriptorIdx) {
        return typeIdIdx;
      }
      typeIdIdx++;
    }
    return -1;
  }

  /**
   * Given a fully qualified class name (Ljava/lang/System;)
   * either find the TypeId in our DEX file's table, or create it.
   */
  public int findOrCreateTypeId(String className) {
    int typeIdIdx = findTypeId(className);
    if (typeIdIdx != -1) {
      return typeIdIdx;
    }
    return createTypeId(className);
  }

  private int createString(String string) {
    // Didn't find it, create one...
    int stringsCount = rawDexFile.stringIds.size();
    if (stringsCount != rawDexFile.stringDatas.size()) {
      Log.errorAndQuit("Corrupted DEX file, len(StringIDs) != len(StringDatas)");
    }

    // StringData must be ordered.
    int newStringIdx = findStringDataInsertionPoint(string);

    // Create StringDataItem.
    StringDataItem newStringData = new StringDataItem();
    newStringData.setSize(string.length());
    newStringData.setString(string);

    rawDexFile.stringDatas.add(newStringIdx, newStringData);

    // Insert into OffsetTracker.
    // (Need to save the Offsettable, because the StringIdItem will point to it.)
    Offsettable offsettableStringData = null;
    if (newStringIdx == 0) {
      offsettableStringData =
          rawDexFile.getOffsetTracker()
          .insertNewOffsettableAsFirstOfType(newStringData, rawDexFile);
    } else {
      StringDataItem prevStringData = rawDexFile.stringDatas.get(newStringIdx - 1);
      offsettableStringData = rawDexFile.getOffsetTracker()
          .insertNewOffsettableAfter(newStringData, prevStringData);
    }

    // Create StringIdItem.
    StringIdItem newStringId = new StringIdItem();
    newStringId.stringDataOff = new Offset(false);
    newStringId.stringDataOff.pointToNew(offsettableStringData);

    rawDexFile.stringIds.add(newStringIdx, newStringId);

    // Insert into OffsetTracker.
    if (newStringIdx == 0) {
      rawDexFile.getOffsetTracker()
        .insertNewOffsettableAsFirstOfType(newStringId, rawDexFile);
    } else {
      StringIdItem prevStringId = rawDexFile.stringIds.get(newStringIdx - 1);
      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newStringId, prevStringId);
    }


    Log.info(String.format("Created new StringIdItem and StringDataItem for %s, index: 0x%04x",
        string, newStringIdx));

    // Now that we've potentially moved a lot of string IDs along, all references
    // to them need to be updated.
    rawDexFile.incrementIndex(IndexUpdateKind.STRING_ID, newStringIdx);

    // All done, return the index for the new string.
    return newStringIdx;
  }

  private int findString(String string) {
    // Search for string.
    int stringIdx = 0;
    for (StringDataItem stringDataItem : rawDexFile.stringDatas) {
      if (stringDataItem.getSize() == 0 && string.isEmpty()) {
        return stringIdx;
      } else if (stringDataItem.getSize() > 0 && stringDataItem.getString().equals(string)) {
        return stringIdx;
      }
      stringIdx++;
    }
    return -1;
  }

  /**
   * Given a string, either find the StringId in our DEX file's table, or create it.
   */
  public int findOrCreateString(String string) {
    int stringIdx = findString(string);
    if (stringIdx != -1) {
      return stringIdx;
    }
    return createString(string);
  }

  private int createFieldId(String className, String typeName, String fieldName) {
    if (rawDexFile.fieldIds.size() >= 65536) {
      Log.errorAndQuit("Referenced too many fields for the DEX file.");
    }

    // Search for (or create) the owning class.
    int classIdx = findOrCreateTypeId(className);

    // Search for (or create) the field's type.
    int typeIdx = findOrCreateTypeId(typeName);

    // The creation of the typeIdx may have changed the classIdx, search again!
    classIdx = findOrCreateTypeId(className);

    // Search for (or create) the string representing the field name.
    int fieldNameStringIdx = findOrCreateString(fieldName);

    // Create FieldIdItem.
    FieldIdItem newFieldId = new FieldIdItem();
    newFieldId.classIdx = (short) classIdx;
    newFieldId.typeIdx = (short) typeIdx;
    newFieldId.nameIdx = fieldNameStringIdx;

    // FieldIds must be ordered.
    int newFieldIdIdx = findFieldIdInsertionPoint(className, typeName, fieldName);

    rawDexFile.fieldIds.add(newFieldIdIdx, newFieldId);

    // Insert into OffsetTracker.
    if (newFieldIdIdx == 0 && rawDexFile.fieldIds.size() == 1) {
      // Special case: we didn't have any fields before!
      rawDexFile.getOffsetTracker()
        .insertNewOffsettableAsFirstEverField(newFieldId, rawDexFile);
    } else if (newFieldIdIdx == 0) {
      rawDexFile.getOffsetTracker().insertNewOffsettableAsFirstOfType(newFieldId, rawDexFile);
    } else {
      FieldIdItem prevFieldId = rawDexFile.fieldIds.get(newFieldIdIdx - 1);
      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newFieldId, prevFieldId);
    }

    Log.info(String.format("Created new FieldIdItem for %s %s %s, index: 0x%04x",
        className, typeName, fieldName, newFieldIdIdx));

    // Now that we've potentially moved a lot of field IDs along, all references
    // to them need to be updated.
    rawDexFile.incrementIndex(IndexUpdateKind.FIELD_ID, newFieldIdIdx);

    // All done, return the index for the new field.
    return newFieldIdIdx;
  }

  private int findFieldId(String className, String typeName, String fieldName) {
    int classIdx = findTypeId(className);
    if (classIdx == -1) {
      return -1;
    }
    int typeIdx = findTypeId(typeName);
    if (typeIdx == -1) {
      return -1;
    }
    int nameIdx = findString(fieldName);
    if (nameIdx == -1) {
      return -1;
    }

    int fieldIdIdx = 0;
    for (FieldIdItem fieldId : rawDexFile.fieldIds) {
      if (classIdx == fieldId.classIdx
          && typeIdx == fieldId.typeIdx
          && nameIdx == fieldId.nameIdx) {
        return fieldIdIdx;
      }
      fieldIdIdx++;
    }
    return -1;
  }

  /**
   * Given a field's fully qualified class name, type name, and name,
   * either find the FieldId in our DEX file's table, or create it.
   */
  public int findOrCreateFieldId(String className, String typeName, String fieldName) {
    int fieldIdx = findFieldId(className, typeName, fieldName);
    if (fieldIdx != -1) {
      return fieldIdx;
    }
    return createFieldId(className, typeName, fieldName);
  }

  /**
   * Returns a 1 or 2 element String[]. If 1 element, the only element is the return type
   * part of the signature. If 2 elements, the first is the parameters, the second is
   * the return type.
   */
  private String[] convertSignatureToParametersAndReturnType(String signature) {
    if (signature.charAt(0) != '(' || !signature.contains(")")) {
      Log.errorAndQuit("Invalid signature: " + signature);
    }
    String[] elems = signature.substring(1).split("\\)");
    return elems;
  }

  private String[] convertSignatureToParameterList(String signature) {
    String[] elems = convertSignatureToParametersAndReturnType(signature);
    String parameters = "";
    if (elems.length == 2) {
      parameters = elems[0];
    }

    List<String> parameterList = new ArrayList<String>();

    int typePointer = 0;
    while (typePointer != parameters.length()) {
      if (elems[0].charAt(typePointer) == 'L') {
        int start = typePointer;
        // Read up to the next ;
        while (elems[0].charAt(typePointer) != ';') {
          typePointer++;
        }
        parameterList.add(parameters.substring(start, typePointer + 1));
      } else {
        parameterList.add(Character.toString(parameters.charAt(typePointer)));
      }
      typePointer++;
    }

    return parameterList.toArray(new String[]{});
  }

  private String convertSignatureToReturnType(String signature) {
    String[] elems = convertSignatureToParametersAndReturnType(signature);
    String returnType = "";
    if (elems.length == 1) {
      returnType = elems[0];
    } else {
      returnType = elems[1];
    }

    return returnType;
  }

  private String convertSignatureToShorty(String signature) {
    String[] elems = convertSignatureToParametersAndReturnType(signature);

    StringBuilder shortyBuilder = new StringBuilder();

    String parameters = "";
    String returnType = "";

    if (elems.length == 1) {
      shortyBuilder.append("V");
    } else {
      parameters = elems[0];
      returnType = elems[1];
      char returnChar = returnType.charAt(0);
      // Arrays are references in shorties.
      if (returnChar == '[') {
        returnChar = 'L';
      }
      shortyBuilder.append(returnChar);
    }

    int typePointer = 0;
    while (typePointer != parameters.length()) {
      if (parameters.charAt(typePointer) == 'L') {
        shortyBuilder.append('L');
        // Read up to the next ;
        while (parameters.charAt(typePointer) != ';') {
          typePointer++;
          if (typePointer == parameters.length()) {
            Log.errorAndQuit("Illegal type specified in signature - L with no ;!");
          }
        }
      } else if (parameters.charAt(typePointer) == '[') {
        // Arrays are references in shorties.
        shortyBuilder.append('L');
        // Read past all the [s
        while (parameters.charAt(typePointer) == '[') {
          typePointer++;
        }
        if (parameters.charAt(typePointer) == 'L') {
          // Read up to the next ;
          while (parameters.charAt(typePointer) != ';') {
            typePointer++;
            if (typePointer == parameters.length()) {
              Log.errorAndQuit("Illegal type specified in signature - L with no ;!");
            }
          }
        }
      } else {
        shortyBuilder.append(parameters.charAt(typePointer));
      }

      typePointer++;
    }

    return shortyBuilder.toString();
  }

  private Integer[] convertParameterListToTypeIdList(String[] parameterList) {
    List<Integer> typeIdList = new ArrayList<Integer>();
    for (String parameter : parameterList) {
      int typeIdx = findTypeId(parameter);
      if (typeIdx == -1) {
        return null;
      }
      typeIdList.add(typeIdx);
    }
    return typeIdList.toArray(new Integer[]{});
  }

  private TypeList createTypeList(String[] parameterList) {
    TypeList typeList = new TypeList();
    List<TypeItem> typeItemList = new ArrayList<TypeItem>();

    // This must be done as two passes, one to create all the types,
    // and then one to put them in the type list.
    for (String parameter : parameterList) {
      findOrCreateTypeId(parameter);
    }

    // Now actually put them in the list.
    for (String parameter : parameterList) {
      TypeItem typeItem = new TypeItem();
      typeItem.typeIdx = (short) findOrCreateTypeId(parameter);
      typeItemList.add(typeItem);
    }
    typeList.list = typeItemList.toArray(new TypeItem[]{});
    typeList.size = typeItemList.size();

    // Insert into OffsetTracker.
    if (rawDexFile.typeLists == null) {
      // Special case: we didn't have any fields before!
      Log.info("Need to create first type list.");
      rawDexFile.typeLists = new ArrayList<TypeList>();
      rawDexFile.getOffsetTracker()
        .insertNewOffsettableAsFirstEverTypeList(typeList, rawDexFile);
    } else {
      TypeList prevTypeList =
          rawDexFile.typeLists.get(rawDexFile.typeLists.size() - 1);
      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(typeList, prevTypeList);
    }

    // Finally, add this new TypeList to the list of them.
    rawDexFile.typeLists.add(typeList);

    return typeList;
  }

  private TypeList findTypeList(String[] parameterList) {
    Integer[] typeIdList = convertParameterListToTypeIdList(parameterList);
    if (typeIdList == null) {
      return null;
    }

    if (rawDexFile.typeLists == null) {
      // There's no type lists yet!
      return null;
    }

    for (TypeList typeList : rawDexFile.typeLists) {
      if (typeList.size != typeIdList.length) {
        continue;
      }

      boolean found = true;
      int idx = 0;
      for (TypeItem typeItem : typeList.list) {
        if (typeItem.typeIdx != typeIdList[idx]) {
          found = false;
          break;
        }
        idx++;
      }
      if (found && idx == parameterList.length) {
        return typeList;
      }
    }

    return null;
  }

  private TypeList findOrCreateTypeList(String[] parameterList) {
    TypeList typeList = findTypeList(parameterList);
    if (typeList != null) {
      return typeList;
    }
    return createTypeList(parameterList);
  }

  private int createProtoId(String signature) {
    String shorty = convertSignatureToShorty(signature);
    String returnType = convertSignatureToReturnType(signature);
    String[] parameterList = convertSignatureToParameterList(signature);

    if (rawDexFile.protoIds.size() >= 65536) {
      Log.errorAndQuit("Referenced too many protos for the DEX file.");
    }

    TypeList typeList = null;
    Offsettable typeListOffsettable = null;

    if (parameterList.length > 0) {
      // Search for (or create) the parameter list.
      typeList = findOrCreateTypeList(parameterList);

      typeListOffsettable =
          rawDexFile.getOffsetTracker().getOffsettableForItem(typeList);
    }

    // Search for (or create) the return type.
    int returnTypeIdx = findOrCreateTypeId(returnType);

    // Search for (or create) the shorty string.
    int shortyIdx = findOrCreateString(shorty);

    // Create ProtoIdItem.
    ProtoIdItem newProtoId = new ProtoIdItem();
    newProtoId.shortyIdx = shortyIdx;
    newProtoId.returnTypeIdx = returnTypeIdx;
    newProtoId.parametersOff = new Offset(false);
    if (parameterList.length > 0) {
      newProtoId.parametersOff.pointToNew(typeListOffsettable);
    }

    // ProtoIds must be ordered.
    int newProtoIdIdx = findProtoIdInsertionPoint(signature);

    rawDexFile.protoIds.add(newProtoIdIdx, newProtoId);

    // Insert into OffsetTracker.
    if (newProtoIdIdx == 0) {
      rawDexFile.getOffsetTracker().insertNewOffsettableAsFirstOfType(newProtoId, rawDexFile);
    } else {
      ProtoIdItem prevProtoId = rawDexFile.protoIds.get(newProtoIdIdx - 1);
      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newProtoId, prevProtoId);
    }

    Log.info(String.format("Created new ProtoIdItem for %s, index: 0x%04x",
        signature, newProtoIdIdx));

    // Now that we've potentially moved a lot of proto IDs along, all references
    // to them need to be updated.
    rawDexFile.incrementIndex(IndexUpdateKind.PROTO_ID, newProtoIdIdx);

    // All done, return the index for the new proto.
    return newProtoIdIdx;
  }

  private int findProtoId(String signature) {
    String shorty = convertSignatureToShorty(signature);
    String returnType = convertSignatureToReturnType(signature);
    String[] parameterList = convertSignatureToParameterList(signature);

    int shortyIdx = findString(shorty);
    if (shortyIdx == -1) {
      return -1;
    }
    int returnTypeIdx = findTypeId(returnType);
    if (returnTypeIdx == -1) {
      return -1;
    }

    // Only look for a TypeList if there's a parameter list.
    TypeList typeList = null;
    if (parameterList.length > 0) {
      typeList = findTypeList(parameterList);
      if (typeList == null) {
        return -1;
      }
    }

    int protoIdIdx = 0;
    for (ProtoIdItem protoId : rawDexFile.protoIds) {
      if (parameterList.length > 0) {
        // With parameters.
        if (shortyIdx == protoId.shortyIdx
            && returnTypeIdx == protoId.returnTypeIdx
            && typeList.equals(protoId.parametersOff.getPointedToItem())) {
          return protoIdIdx;
        }
      } else {
        // Without parameters.
        if (shortyIdx == protoId.shortyIdx
            && returnTypeIdx == protoId.returnTypeIdx) {
          return protoIdIdx;
        }
      }
      protoIdIdx++;
    }
    return -1;
  }

  private int findOrCreateProtoId(String signature) {
    int protoIdx = findProtoId(signature);
    if (protoIdx != -1) {
      return protoIdx;
    }
    return createProtoId(signature);
  }
}