1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package dexfuzz.program;
18
19import dexfuzz.Log;
20import dexfuzz.rawdex.FieldIdItem;
21import dexfuzz.rawdex.MethodIdItem;
22import dexfuzz.rawdex.Offset;
23import dexfuzz.rawdex.Offsettable;
24import dexfuzz.rawdex.ProtoIdItem;
25import dexfuzz.rawdex.RawDexFile;
26import dexfuzz.rawdex.RawDexObject.IndexUpdateKind;
27import dexfuzz.rawdex.StringDataItem;
28import dexfuzz.rawdex.StringIdItem;
29import dexfuzz.rawdex.TypeIdItem;
30import dexfuzz.rawdex.TypeItem;
31import dexfuzz.rawdex.TypeList;
32
33import java.util.ArrayList;
34import java.util.List;
35
36/**
37 * Responsible for the finding and creation of TypeIds, MethodIds, FieldIds, and StringIds,
38 * during mutation.
39 */
40public class IdCreator {
41  private RawDexFile rawDexFile;
42
43  public IdCreator(RawDexFile rawDexFile) {
44    this.rawDexFile = rawDexFile;
45  }
46
47  private int findProtoIdInsertionPoint(String signature) {
48    int returnTypeIdx = findTypeId(convertSignatureToReturnType(signature));
49    String[] parameterListStrings = convertSignatureToParameterList(signature);
50    TypeList parameterList = null;
51    if (parameterListStrings.length > 0) {
52      parameterList = findTypeList(parameterListStrings);
53    }
54
55    if (returnTypeIdx < 0) {
56      Log.errorAndQuit("Did not create necessary return type before finding insertion "
57          + "point for new proto!");
58    }
59
60    if (parameterListStrings.length > 0 && parameterList == null) {
61      Log.errorAndQuit("Did not create necessary parameter list before finding insertion "
62          + "point for new proto!");
63    }
64
65    int protoIdIdx = 0;
66    for (ProtoIdItem protoId : rawDexFile.protoIds) {
67      if (returnTypeIdx < protoId.returnTypeIdx) {
68        break;
69      }
70      if (returnTypeIdx == protoId.returnTypeIdx
71          && parameterListStrings.length == 0) {
72        break;
73      }
74      if (returnTypeIdx == protoId.returnTypeIdx
75          && parameterListStrings.length > 0
76          && protoId.parametersOff.pointsToSomething()
77          && parameterList.comesBefore(
78              (TypeList) protoId.parametersOff.getPointedToItem())) {
79        break;
80      }
81      protoIdIdx++;
82    }
83    return protoIdIdx;
84  }
85
86  private int findMethodIdInsertionPoint(String className, String methodName, String signature) {
87    int classIdx = findTypeId(className);
88    int nameIdx = findString(methodName);
89    int protoIdx = findProtoId(signature);
90
91    if (classIdx < 0 || nameIdx < 0 || protoIdx < 0) {
92      Log.errorAndQuit("Did not create necessary class, name or proto strings before finding "
93          + " insertion point for new method!");
94    }
95
96    int methodIdIdx = 0;
97    for (MethodIdItem methodId : rawDexFile.methodIds) {
98      if (classIdx < methodId.classIdx) {
99        break;
100      }
101      if (classIdx == methodId.classIdx && nameIdx < methodId.nameIdx) {
102        break;
103      }
104      if (classIdx == methodId.classIdx && nameIdx == methodId.nameIdx
105          && protoIdx < methodId.protoIdx) {
106        break;
107      }
108      methodIdIdx++;
109    }
110    return methodIdIdx;
111  }
112
113  private int findTypeIdInsertionPoint(String className) {
114    int descriptorIdx = findString(className);
115
116    if (descriptorIdx < 0) {
117      Log.errorAndQuit("Did not create necessary descriptor string before finding "
118          + " insertion point for new type!");
119    }
120
121    int typeIdIdx = 0;
122    for (TypeIdItem typeId : rawDexFile.typeIds) {
123      if (descriptorIdx < typeId.descriptorIdx) {
124        break;
125      }
126      typeIdIdx++;
127    }
128    return typeIdIdx;
129  }
130
131  private int findStringDataInsertionPoint(String string) {
132    int stringDataIdx = 0;
133    for (StringDataItem stringData : rawDexFile.stringDatas) {
134      if (stringData.getSize() > 0 && stringData.getString().compareTo(string) >= 0) {
135        break;
136      }
137      stringDataIdx++;
138    }
139    return stringDataIdx;
140  }
141
142  private int findFieldIdInsertionPoint(String className, String typeName, String fieldName) {
143    int classIdx = findTypeId(className);
144    int typeIdx = findTypeId(typeName);
145    int nameIdx = findString(fieldName);
146
147    if (classIdx < 0 || typeIdx < 0 || nameIdx < 0) {
148      Log.errorAndQuit("Did not create necessary class, type or name strings before finding "
149          + " insertion point for new field!");
150    }
151
152    int fieldIdIdx = 0;
153    for (FieldIdItem fieldId : rawDexFile.fieldIds) {
154      if (classIdx < fieldId.classIdx) {
155        break;
156      }
157      if (classIdx == fieldId.classIdx && nameIdx < fieldId.nameIdx) {
158        break;
159      }
160      if (classIdx == fieldId.classIdx && nameIdx == fieldId.nameIdx
161          && typeIdx < fieldId.typeIdx) {
162        break;
163      }
164      fieldIdIdx++;
165    }
166    return fieldIdIdx;
167  }
168
169  private int createMethodId(String className, String methodName, String signature) {
170    if (rawDexFile.methodIds.size() >= 65536) {
171      Log.errorAndQuit("Referenced too many methods for the DEX file.");
172    }
173
174    // Search for (or create) the prototype.
175    int protoIdx = findOrCreateProtoId(signature);
176
177    // Search for (or create) the owning class.
178    // NB: findOrCreateProtoId could create new types, so this must come
179    //     after it!
180    int typeIdIdx = findOrCreateTypeId(className);
181
182    // Search for (or create) the string representing the method name.
183    // NB: findOrCreateProtoId/TypeId could create new strings, so this must come
184    //     after them!
185    int methodNameStringIdx = findOrCreateString(methodName);
186
187    // Create MethodIdItem.
188    MethodIdItem newMethodId = new MethodIdItem();
189    newMethodId.classIdx = (short) typeIdIdx;
190    newMethodId.protoIdx = (short) protoIdx;
191    newMethodId.nameIdx = methodNameStringIdx;
192
193    // MethodIds must be ordered.
194    int newMethodIdIdx = findMethodIdInsertionPoint(className, methodName, signature);
195
196    rawDexFile.methodIds.add(newMethodIdIdx, newMethodId);
197
198    // Insert into OffsetTracker.
199    if (newMethodIdIdx == 0) {
200      rawDexFile.getOffsetTracker()
201        .insertNewOffsettableAsFirstOfType(newMethodId, rawDexFile);
202    } else {
203      MethodIdItem prevMethodId = rawDexFile.methodIds.get(newMethodIdIdx - 1);
204      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newMethodId, prevMethodId);
205    }
206
207    Log.info(String.format("Created new MethodIdItem for %s %s %s, index: 0x%04x",
208        className, methodName, signature, newMethodIdIdx));
209
210    // Now that we've potentially moved a lot of method IDs along, all references
211    // to them need to be updated.
212    rawDexFile.incrementIndex(IndexUpdateKind.METHOD_ID, newMethodIdIdx);
213
214    // All done, return the index for the new method.
215    return newMethodIdIdx;
216  }
217
218  private int findMethodId(String className, String methodName, String signature) {
219    int classIdx = findTypeId(className);
220    if (classIdx == -1) {
221      return -1;
222    }
223    int nameIdx = findString(methodName);
224    if (nameIdx == -1) {
225      return -1;
226    }
227    int protoIdx = findProtoId(signature);
228    if (nameIdx == -1) {
229      return -1;
230    }
231
232    int methodIdIdx = 0;
233    for (MethodIdItem methodId : rawDexFile.methodIds) {
234      if (classIdx == methodId.classIdx
235          && nameIdx == methodId.nameIdx
236          && protoIdx == methodId.protoIdx) {
237        return methodIdIdx;
238      }
239      methodIdIdx++;
240    }
241    return -1;
242  }
243
244  /**
245   * Given a fully qualified class name (Ljava/lang/System;), method name (gc) and
246   * and signature (()V), either find the MethodId in our DEX file's table, or create it.
247   */
248  public int findOrCreateMethodId(String className, String methodName, String shorty) {
249    int methodIdIdx = findMethodId(className, methodName, shorty);
250    if (methodIdIdx != -1) {
251      return methodIdIdx;
252    }
253    return createMethodId(className, methodName, shorty);
254  }
255
256  private int createTypeId(String className) {
257    if (rawDexFile.typeIds.size() >= 65536) {
258      Log.errorAndQuit("Referenced too many classes for the DEX file.");
259    }
260
261    // Search for (or create) the string representing the class descriptor.
262    int descriptorStringIdx = findOrCreateString(className);
263
264    // Create TypeIdItem.
265    TypeIdItem newTypeId = new TypeIdItem();
266    newTypeId.descriptorIdx = descriptorStringIdx;
267
268    // TypeIds must be ordered.
269    int newTypeIdIdx = findTypeIdInsertionPoint(className);
270
271    rawDexFile.typeIds.add(newTypeIdIdx, newTypeId);
272
273    // Insert into OffsetTracker.
274    if (newTypeIdIdx == 0) {
275      rawDexFile.getOffsetTracker().insertNewOffsettableAsFirstOfType(newTypeId, rawDexFile);
276    } else {
277      TypeIdItem prevTypeId = rawDexFile.typeIds.get(newTypeIdIdx - 1);
278      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newTypeId, prevTypeId);
279    }
280
281    Log.info(String.format("Created new ClassIdItem for %s, index: 0x%04x",
282        className, newTypeIdIdx));
283
284    // Now that we've potentially moved a lot of type IDs along, all references
285    // to them need to be updated.
286    rawDexFile.incrementIndex(IndexUpdateKind.TYPE_ID, newTypeIdIdx);
287
288    // All done, return the index for the new class.
289    return newTypeIdIdx;
290  }
291
292  private int findTypeId(String className) {
293    int descriptorIdx = findString(className);
294    if (descriptorIdx == -1) {
295      return -1;
296    }
297
298    // Search for class.
299    int typeIdIdx = 0;
300    for (TypeIdItem typeId : rawDexFile.typeIds) {
301      if (descriptorIdx == typeId.descriptorIdx) {
302        return typeIdIdx;
303      }
304      typeIdIdx++;
305    }
306    return -1;
307  }
308
309  /**
310   * Given a fully qualified class name (Ljava/lang/System;)
311   * either find the TypeId in our DEX file's table, or create it.
312   */
313  public int findOrCreateTypeId(String className) {
314    int typeIdIdx = findTypeId(className);
315    if (typeIdIdx != -1) {
316      return typeIdIdx;
317    }
318    return createTypeId(className);
319  }
320
321  private int createString(String string) {
322    // Didn't find it, create one...
323    int stringsCount = rawDexFile.stringIds.size();
324    if (stringsCount != rawDexFile.stringDatas.size()) {
325      Log.errorAndQuit("Corrupted DEX file, len(StringIDs) != len(StringDatas)");
326    }
327
328    // StringData must be ordered.
329    int newStringIdx = findStringDataInsertionPoint(string);
330
331    // Create StringDataItem.
332    StringDataItem newStringData = new StringDataItem();
333    newStringData.setSize(string.length());
334    newStringData.setString(string);
335
336    rawDexFile.stringDatas.add(newStringIdx, newStringData);
337
338    // Insert into OffsetTracker.
339    // (Need to save the Offsettable, because the StringIdItem will point to it.)
340    Offsettable offsettableStringData = null;
341    if (newStringIdx == 0) {
342      offsettableStringData =
343          rawDexFile.getOffsetTracker()
344          .insertNewOffsettableAsFirstOfType(newStringData, rawDexFile);
345    } else {
346      StringDataItem prevStringData = rawDexFile.stringDatas.get(newStringIdx - 1);
347      offsettableStringData = rawDexFile.getOffsetTracker()
348          .insertNewOffsettableAfter(newStringData, prevStringData);
349    }
350
351    // Create StringIdItem.
352    StringIdItem newStringId = new StringIdItem();
353    newStringId.stringDataOff = new Offset(false);
354    newStringId.stringDataOff.pointToNew(offsettableStringData);
355
356    rawDexFile.stringIds.add(newStringIdx, newStringId);
357
358    // Insert into OffsetTracker.
359    if (newStringIdx == 0) {
360      rawDexFile.getOffsetTracker()
361        .insertNewOffsettableAsFirstOfType(newStringId, rawDexFile);
362    } else {
363      StringIdItem prevStringId = rawDexFile.stringIds.get(newStringIdx - 1);
364      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newStringId, prevStringId);
365    }
366
367
368    Log.info(String.format("Created new StringIdItem and StringDataItem for %s, index: 0x%04x",
369        string, newStringIdx));
370
371    // Now that we've potentially moved a lot of string IDs along, all references
372    // to them need to be updated.
373    rawDexFile.incrementIndex(IndexUpdateKind.STRING_ID, newStringIdx);
374
375    // All done, return the index for the new string.
376    return newStringIdx;
377  }
378
379  private int findString(String string) {
380    // Search for string.
381    int stringIdx = 0;
382    for (StringDataItem stringDataItem : rawDexFile.stringDatas) {
383      if (stringDataItem.getSize() == 0 && string.isEmpty()) {
384        return stringIdx;
385      } else if (stringDataItem.getSize() > 0 && stringDataItem.getString().equals(string)) {
386        return stringIdx;
387      }
388      stringIdx++;
389    }
390    return -1;
391  }
392
393  /**
394   * Given a string, either find the StringId in our DEX file's table, or create it.
395   */
396  public int findOrCreateString(String string) {
397    int stringIdx = findString(string);
398    if (stringIdx != -1) {
399      return stringIdx;
400    }
401    return createString(string);
402  }
403
404  private int createFieldId(String className, String typeName, String fieldName) {
405    if (rawDexFile.fieldIds.size() >= 65536) {
406      Log.errorAndQuit("Referenced too many fields for the DEX file.");
407    }
408
409    // Search for (or create) the owning class.
410    int classIdx = findOrCreateTypeId(className);
411
412    // Search for (or create) the field's type.
413    int typeIdx = findOrCreateTypeId(typeName);
414
415    // The creation of the typeIdx may have changed the classIdx, search again!
416    classIdx = findOrCreateTypeId(className);
417
418    // Search for (or create) the string representing the field name.
419    int fieldNameStringIdx = findOrCreateString(fieldName);
420
421    // Create FieldIdItem.
422    FieldIdItem newFieldId = new FieldIdItem();
423    newFieldId.classIdx = (short) classIdx;
424    newFieldId.typeIdx = (short) typeIdx;
425    newFieldId.nameIdx = fieldNameStringIdx;
426
427    // FieldIds must be ordered.
428    int newFieldIdIdx = findFieldIdInsertionPoint(className, typeName, fieldName);
429
430    rawDexFile.fieldIds.add(newFieldIdIdx, newFieldId);
431
432    // Insert into OffsetTracker.
433    if (newFieldIdIdx == 0 && rawDexFile.fieldIds.size() == 1) {
434      // Special case: we didn't have any fields before!
435      rawDexFile.getOffsetTracker()
436        .insertNewOffsettableAsFirstEverField(newFieldId, rawDexFile);
437    } else if (newFieldIdIdx == 0) {
438      rawDexFile.getOffsetTracker().insertNewOffsettableAsFirstOfType(newFieldId, rawDexFile);
439    } else {
440      FieldIdItem prevFieldId = rawDexFile.fieldIds.get(newFieldIdIdx - 1);
441      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newFieldId, prevFieldId);
442    }
443
444    Log.info(String.format("Created new FieldIdItem for %s %s %s, index: 0x%04x",
445        className, typeName, fieldName, newFieldIdIdx));
446
447    // Now that we've potentially moved a lot of field IDs along, all references
448    // to them need to be updated.
449    rawDexFile.incrementIndex(IndexUpdateKind.FIELD_ID, newFieldIdIdx);
450
451    // All done, return the index for the new field.
452    return newFieldIdIdx;
453  }
454
455  private int findFieldId(String className, String typeName, String fieldName) {
456    int classIdx = findTypeId(className);
457    if (classIdx == -1) {
458      return -1;
459    }
460    int typeIdx = findTypeId(typeName);
461    if (typeIdx == -1) {
462      return -1;
463    }
464    int nameIdx = findString(fieldName);
465    if (nameIdx == -1) {
466      return -1;
467    }
468
469    int fieldIdIdx = 0;
470    for (FieldIdItem fieldId : rawDexFile.fieldIds) {
471      if (classIdx == fieldId.classIdx
472          && typeIdx == fieldId.typeIdx
473          && nameIdx == fieldId.nameIdx) {
474        return fieldIdIdx;
475      }
476      fieldIdIdx++;
477    }
478    return -1;
479  }
480
481  /**
482   * Given a field's fully qualified class name, type name, and name,
483   * either find the FieldId in our DEX file's table, or create it.
484   */
485  public int findOrCreateFieldId(String className, String typeName, String fieldName) {
486    int fieldIdx = findFieldId(className, typeName, fieldName);
487    if (fieldIdx != -1) {
488      return fieldIdx;
489    }
490    return createFieldId(className, typeName, fieldName);
491  }
492
493  /**
494   * Returns a 1 or 2 element String[]. If 1 element, the only element is the return type
495   * part of the signature. If 2 elements, the first is the parameters, the second is
496   * the return type.
497   */
498  private String[] convertSignatureToParametersAndReturnType(String signature) {
499    if (signature.charAt(0) != '(' || !signature.contains(")")) {
500      Log.errorAndQuit("Invalid signature: " + signature);
501    }
502    String[] elems = signature.substring(1).split("\\)");
503    return elems;
504  }
505
506  private String[] convertSignatureToParameterList(String signature) {
507    String[] elems = convertSignatureToParametersAndReturnType(signature);
508    String parameters = "";
509    if (elems.length == 2) {
510      parameters = elems[0];
511    }
512
513    List<String> parameterList = new ArrayList<String>();
514
515    int typePointer = 0;
516    while (typePointer != parameters.length()) {
517      if (elems[0].charAt(typePointer) == 'L') {
518        int start = typePointer;
519        // Read up to the next ;
520        while (elems[0].charAt(typePointer) != ';') {
521          typePointer++;
522        }
523        parameterList.add(parameters.substring(start, typePointer + 1));
524      } else {
525        parameterList.add(Character.toString(parameters.charAt(typePointer)));
526      }
527      typePointer++;
528    }
529
530    return parameterList.toArray(new String[]{});
531  }
532
533  private String convertSignatureToReturnType(String signature) {
534    String[] elems = convertSignatureToParametersAndReturnType(signature);
535    String returnType = "";
536    if (elems.length == 1) {
537      returnType = elems[0];
538    } else {
539      returnType = elems[1];
540    }
541
542    return returnType;
543  }
544
545  private String convertSignatureToShorty(String signature) {
546    String[] elems = convertSignatureToParametersAndReturnType(signature);
547
548    StringBuilder shortyBuilder = new StringBuilder();
549
550    String parameters = "";
551    String returnType = "";
552
553    if (elems.length == 1) {
554      shortyBuilder.append("V");
555    } else {
556      parameters = elems[0];
557      returnType = elems[1];
558      char returnChar = returnType.charAt(0);
559      // Arrays are references in shorties.
560      if (returnChar == '[') {
561        returnChar = 'L';
562      }
563      shortyBuilder.append(returnChar);
564    }
565
566    int typePointer = 0;
567    while (typePointer != parameters.length()) {
568      if (parameters.charAt(typePointer) == 'L') {
569        shortyBuilder.append('L');
570        // Read up to the next ;
571        while (parameters.charAt(typePointer) != ';') {
572          typePointer++;
573          if (typePointer == parameters.length()) {
574            Log.errorAndQuit("Illegal type specified in signature - L with no ;!");
575          }
576        }
577      } else if (parameters.charAt(typePointer) == '[') {
578        // Arrays are references in shorties.
579        shortyBuilder.append('L');
580        // Read past all the [s
581        while (parameters.charAt(typePointer) == '[') {
582          typePointer++;
583        }
584        if (parameters.charAt(typePointer) == 'L') {
585          // Read up to the next ;
586          while (parameters.charAt(typePointer) != ';') {
587            typePointer++;
588            if (typePointer == parameters.length()) {
589              Log.errorAndQuit("Illegal type specified in signature - L with no ;!");
590            }
591          }
592        }
593      } else {
594        shortyBuilder.append(parameters.charAt(typePointer));
595      }
596
597      typePointer++;
598    }
599
600    return shortyBuilder.toString();
601  }
602
603  private Integer[] convertParameterListToTypeIdList(String[] parameterList) {
604    List<Integer> typeIdList = new ArrayList<Integer>();
605    for (String parameter : parameterList) {
606      int typeIdx = findTypeId(parameter);
607      if (typeIdx == -1) {
608        return null;
609      }
610      typeIdList.add(typeIdx);
611    }
612    return typeIdList.toArray(new Integer[]{});
613  }
614
615  private TypeList createTypeList(String[] parameterList) {
616    TypeList typeList = new TypeList();
617    List<TypeItem> typeItemList = new ArrayList<TypeItem>();
618
619    // This must be done as two passes, one to create all the types,
620    // and then one to put them in the type list.
621    for (String parameter : parameterList) {
622      findOrCreateTypeId(parameter);
623    }
624
625    // Now actually put them in the list.
626    for (String parameter : parameterList) {
627      TypeItem typeItem = new TypeItem();
628      typeItem.typeIdx = (short) findOrCreateTypeId(parameter);
629      typeItemList.add(typeItem);
630    }
631    typeList.list = typeItemList.toArray(new TypeItem[]{});
632    typeList.size = typeItemList.size();
633
634    // Insert into OffsetTracker.
635    if (rawDexFile.typeLists == null) {
636      // Special case: we didn't have any fields before!
637      Log.info("Need to create first type list.");
638      rawDexFile.typeLists = new ArrayList<TypeList>();
639      rawDexFile.getOffsetTracker()
640        .insertNewOffsettableAsFirstEverTypeList(typeList, rawDexFile);
641    } else {
642      TypeList prevTypeList =
643          rawDexFile.typeLists.get(rawDexFile.typeLists.size() - 1);
644      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(typeList, prevTypeList);
645    }
646
647    // Finally, add this new TypeList to the list of them.
648    rawDexFile.typeLists.add(typeList);
649
650    return typeList;
651  }
652
653  private TypeList findTypeList(String[] parameterList) {
654    Integer[] typeIdList = convertParameterListToTypeIdList(parameterList);
655    if (typeIdList == null) {
656      return null;
657    }
658
659    if (rawDexFile.typeLists == null) {
660      // There's no type lists yet!
661      return null;
662    }
663
664    for (TypeList typeList : rawDexFile.typeLists) {
665      if (typeList.size != typeIdList.length) {
666        continue;
667      }
668
669      boolean found = true;
670      int idx = 0;
671      for (TypeItem typeItem : typeList.list) {
672        if (typeItem.typeIdx != typeIdList[idx]) {
673          found = false;
674          break;
675        }
676        idx++;
677      }
678      if (found && idx == parameterList.length) {
679        return typeList;
680      }
681    }
682
683    return null;
684  }
685
686  private TypeList findOrCreateTypeList(String[] parameterList) {
687    TypeList typeList = findTypeList(parameterList);
688    if (typeList != null) {
689      return typeList;
690    }
691    return createTypeList(parameterList);
692  }
693
694  private int createProtoId(String signature) {
695    String shorty = convertSignatureToShorty(signature);
696    String returnType = convertSignatureToReturnType(signature);
697    String[] parameterList = convertSignatureToParameterList(signature);
698
699    if (rawDexFile.protoIds.size() >= 65536) {
700      Log.errorAndQuit("Referenced too many protos for the DEX file.");
701    }
702
703    TypeList typeList = null;
704    Offsettable typeListOffsettable = null;
705
706    if (parameterList.length > 0) {
707      // Search for (or create) the parameter list.
708      typeList = findOrCreateTypeList(parameterList);
709
710      typeListOffsettable =
711          rawDexFile.getOffsetTracker().getOffsettableForItem(typeList);
712    }
713
714    // Search for (or create) the return type.
715    int returnTypeIdx = findOrCreateTypeId(returnType);
716
717    // Search for (or create) the shorty string.
718    int shortyIdx = findOrCreateString(shorty);
719
720    // Create ProtoIdItem.
721    ProtoIdItem newProtoId = new ProtoIdItem();
722    newProtoId.shortyIdx = shortyIdx;
723    newProtoId.returnTypeIdx = returnTypeIdx;
724    newProtoId.parametersOff = new Offset(false);
725    if (parameterList.length > 0) {
726      newProtoId.parametersOff.pointToNew(typeListOffsettable);
727    }
728
729    // ProtoIds must be ordered.
730    int newProtoIdIdx = findProtoIdInsertionPoint(signature);
731
732    rawDexFile.protoIds.add(newProtoIdIdx, newProtoId);
733
734    // Insert into OffsetTracker.
735    if (newProtoIdIdx == 0) {
736      rawDexFile.getOffsetTracker().insertNewOffsettableAsFirstOfType(newProtoId, rawDexFile);
737    } else {
738      ProtoIdItem prevProtoId = rawDexFile.protoIds.get(newProtoIdIdx - 1);
739      rawDexFile.getOffsetTracker().insertNewOffsettableAfter(newProtoId, prevProtoId);
740    }
741
742    Log.info(String.format("Created new ProtoIdItem for %s, index: 0x%04x",
743        signature, newProtoIdIdx));
744
745    // Now that we've potentially moved a lot of proto IDs along, all references
746    // to them need to be updated.
747    rawDexFile.incrementIndex(IndexUpdateKind.PROTO_ID, newProtoIdIdx);
748
749    // All done, return the index for the new proto.
750    return newProtoIdIdx;
751  }
752
753  private int findProtoId(String signature) {
754    String shorty = convertSignatureToShorty(signature);
755    String returnType = convertSignatureToReturnType(signature);
756    String[] parameterList = convertSignatureToParameterList(signature);
757
758    int shortyIdx = findString(shorty);
759    if (shortyIdx == -1) {
760      return -1;
761    }
762    int returnTypeIdx = findTypeId(returnType);
763    if (returnTypeIdx == -1) {
764      return -1;
765    }
766
767    // Only look for a TypeList if there's a parameter list.
768    TypeList typeList = null;
769    if (parameterList.length > 0) {
770      typeList = findTypeList(parameterList);
771      if (typeList == null) {
772        return -1;
773      }
774    }
775
776    int protoIdIdx = 0;
777    for (ProtoIdItem protoId : rawDexFile.protoIds) {
778      if (parameterList.length > 0) {
779        // With parameters.
780        if (shortyIdx == protoId.shortyIdx
781            && returnTypeIdx == protoId.returnTypeIdx
782            && typeList.equals(protoId.parametersOff.getPointedToItem())) {
783          return protoIdIdx;
784        }
785      } else {
786        // Without parameters.
787        if (shortyIdx == protoId.shortyIdx
788            && returnTypeIdx == protoId.returnTypeIdx) {
789          return protoIdIdx;
790        }
791      }
792      protoIdIdx++;
793    }
794    return -1;
795  }
796
797  private int findOrCreateProtoId(String signature) {
798    int protoIdx = findProtoId(signature);
799    if (protoIdx != -1) {
800      return protoIdx;
801    }
802    return createProtoId(signature);
803  }
804}
805