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 
17 package dexfuzz.program;
18 
19 import dexfuzz.Log;
20 import dexfuzz.rawdex.FieldIdItem;
21 import dexfuzz.rawdex.MethodIdItem;
22 import dexfuzz.rawdex.Offset;
23 import dexfuzz.rawdex.Offsettable;
24 import dexfuzz.rawdex.ProtoIdItem;
25 import dexfuzz.rawdex.RawDexFile;
26 import dexfuzz.rawdex.RawDexObject.IndexUpdateKind;
27 import dexfuzz.rawdex.StringDataItem;
28 import dexfuzz.rawdex.StringIdItem;
29 import dexfuzz.rawdex.TypeIdItem;
30 import dexfuzz.rawdex.TypeItem;
31 import dexfuzz.rawdex.TypeList;
32 
33 import java.util.ArrayList;
34 import java.util.List;
35 
36 /**
37  * Responsible for the finding and creation of TypeIds, MethodIds, FieldIds, and StringIds,
38  * during mutation.
39  */
40 public class IdCreator {
41   private RawDexFile rawDexFile;
42 
IdCreator(RawDexFile rawDexFile)43   public IdCreator(RawDexFile rawDexFile) {
44     this.rawDexFile = rawDexFile;
45   }
46 
findProtoIdInsertionPoint(String signature)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 
findMethodIdInsertionPoint(String className, String methodName, String signature)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 
findTypeIdInsertionPoint(String className)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 
findStringDataInsertionPoint(String string)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 
findFieldIdInsertionPoint(String className, String typeName, String fieldName)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 
createMethodId(String className, String methodName, String signature)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 
findMethodId(String className, String methodName, String signature)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    */
findOrCreateMethodId(String className, String methodName, String shorty)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 
createTypeId(String className)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 
findTypeId(String className)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    */
findOrCreateTypeId(String className)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 
createString(String string)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 
findString(String string)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    */
findOrCreateString(String string)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 
createFieldId(String className, String typeName, String fieldName)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 
findFieldId(String className, String typeName, String fieldName)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    */
findOrCreateFieldId(String className, String typeName, String fieldName)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    */
convertSignatureToParametersAndReturnType(String signature)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 
convertSignatureToParameterList(String signature)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 
convertSignatureToReturnType(String signature)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 
convertSignatureToShorty(String signature)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 
convertParameterListToTypeIdList(String[] parameterList)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 
createTypeList(String[] parameterList)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 
findTypeList(String[] parameterList)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 
findOrCreateTypeList(String[] parameterList)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 
createProtoId(String signature)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 
findProtoId(String signature)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 
findOrCreateProtoId(String signature)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