View Javadoc
1   /*
2    * Copyright (c) 2001, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  package com.sun.java.util.jar.pack;
27  
28  import java.util.AbstractList;
29  import java.util.ArrayList;
30  import java.util.Arrays;
31  import java.util.Collection;
32  import java.util.List;
33  import java.util.ListIterator;
34  import java.util.Map;
35  import java.util.Set;
36  import static com.sun.java.util.jar.pack.Constants.*;
37  
38  /**
39   * Representation of constant pool entries and indexes.
40   * @author John Rose
41   */
42  abstract
43  class ConstantPool {
44      private ConstantPool() {}  // do not instantiate
45  
46      static int verbose() {
47          return Utils.currentPropMap().getInteger(Utils.DEBUG_VERBOSE);
48      }
49  
50      /** Factory for Utf8 string constants.
51       *  Used for well-known strings like "SourceFile", "<init>", etc.
52       *  Also used to back up more complex constant pool entries, like Class.
53       */
54      public static synchronized Utf8Entry getUtf8Entry(String value) {
55          Map<String, Utf8Entry> utf8Entries  = Utils.getTLGlobals().getUtf8Entries();
56          Utf8Entry e = utf8Entries.get(value);
57          if (e == null) {
58              e = new Utf8Entry(value);
59              utf8Entries.put(e.stringValue(), e);
60          }
61          return e;
62      }
63      /** Factory for Class constants. */
64      public static ClassEntry getClassEntry(String name) {
65          Map<String, ClassEntry> classEntries = Utils.getTLGlobals().getClassEntries();
66          ClassEntry e = classEntries.get(name);
67          if (e == null) {
68              e = new ClassEntry(getUtf8Entry(name));
69              assert(name.equals(e.stringValue()));
70              classEntries.put(e.stringValue(), e);
71          }
72          return e;
73      }
74      /** Factory for literal constants (String, Integer, etc.). */
75      public static LiteralEntry getLiteralEntry(Comparable<?> value) {
76          Map<Object, LiteralEntry> literalEntries = Utils.getTLGlobals().getLiteralEntries();
77          LiteralEntry e = literalEntries.get(value);
78          if (e == null) {
79              if (value instanceof String)
80                  e = new StringEntry(getUtf8Entry((String)value));
81              else
82                  e = new NumberEntry((Number)value);
83              literalEntries.put(value, e);
84          }
85          return e;
86      }
87      /** Factory for literal constants (String, Integer, etc.). */
88      public static StringEntry getStringEntry(String value) {
89          return (StringEntry) getLiteralEntry(value);
90      }
91  
92      /** Factory for signature (type) constants. */
93      public static SignatureEntry getSignatureEntry(String type) {
94          Map<String, SignatureEntry> signatureEntries = Utils.getTLGlobals().getSignatureEntries();
95          SignatureEntry e = signatureEntries.get(type);
96          if (e == null) {
97              e = new SignatureEntry(type);
98              assert(e.stringValue().equals(type));
99              signatureEntries.put(type, e);
100         }
101         return e;
102     }
103     // Convenience overloading.
104     public static SignatureEntry getSignatureEntry(Utf8Entry formRef, ClassEntry[] classRefs) {
105         return getSignatureEntry(SignatureEntry.stringValueOf(formRef, classRefs));
106     }
107 
108     /** Factory for descriptor (name-and-type) constants. */
109     public static DescriptorEntry getDescriptorEntry(Utf8Entry nameRef, SignatureEntry typeRef) {
110         Map<String, DescriptorEntry> descriptorEntries = Utils.getTLGlobals().getDescriptorEntries();
111         String key = DescriptorEntry.stringValueOf(nameRef, typeRef);
112         DescriptorEntry e = descriptorEntries.get(key);
113         if (e == null) {
114             e = new DescriptorEntry(nameRef, typeRef);
115             assert(e.stringValue().equals(key))
116                 : (e.stringValue()+" != "+(key));
117             descriptorEntries.put(key, e);
118         }
119         return e;
120     }
121     // Convenience overloading.
122     public static DescriptorEntry getDescriptorEntry(Utf8Entry nameRef, Utf8Entry typeRef) {
123         return getDescriptorEntry(nameRef, getSignatureEntry(typeRef.stringValue()));
124     }
125 
126     /** Factory for member reference constants. */
127     public static MemberEntry getMemberEntry(byte tag, ClassEntry classRef, DescriptorEntry descRef) {
128         Map<String, MemberEntry> memberEntries = Utils.getTLGlobals().getMemberEntries();
129         String key = MemberEntry.stringValueOf(tag, classRef, descRef);
130         MemberEntry e = memberEntries.get(key);
131         if (e == null) {
132             e = new MemberEntry(tag, classRef, descRef);
133             assert(e.stringValue().equals(key))
134                 : (e.stringValue()+" != "+(key));
135             memberEntries.put(key, e);
136         }
137         return e;
138     }
139 
140     /** Factory for MethodHandle constants. */
141     public static MethodHandleEntry getMethodHandleEntry(byte refKind, MemberEntry memRef) {
142         Map<String, MethodHandleEntry> methodHandleEntries = Utils.getTLGlobals().getMethodHandleEntries();
143         String key = MethodHandleEntry.stringValueOf(refKind, memRef);
144         MethodHandleEntry e = methodHandleEntries.get(key);
145         if (e == null) {
146             e = new MethodHandleEntry(refKind, memRef);
147             assert(e.stringValue().equals(key));
148             methodHandleEntries.put(key, e);
149         }
150         return e;
151     }
152 
153     /** Factory for MethodType constants. */
154     public static MethodTypeEntry getMethodTypeEntry(SignatureEntry sigRef) {
155         Map<String, MethodTypeEntry> methodTypeEntries = Utils.getTLGlobals().getMethodTypeEntries();
156         String key = sigRef.stringValue();
157         MethodTypeEntry e = methodTypeEntries.get(key);
158         if (e == null) {
159             e = new MethodTypeEntry(sigRef);
160             assert(e.stringValue().equals(key));
161             methodTypeEntries.put(key, e);
162         }
163         return e;
164     }
165     public static MethodTypeEntry getMethodTypeEntry(Utf8Entry typeRef) {
166         return getMethodTypeEntry(getSignatureEntry(typeRef.stringValue()));
167     }
168 
169     /** Factory for InvokeDynamic constants. */
170     public static InvokeDynamicEntry getInvokeDynamicEntry(BootstrapMethodEntry bssRef, DescriptorEntry descRef) {
171         Map<String, InvokeDynamicEntry> invokeDynamicEntries = Utils.getTLGlobals().getInvokeDynamicEntries();
172         String key = InvokeDynamicEntry.stringValueOf(bssRef, descRef);
173         InvokeDynamicEntry e = invokeDynamicEntries.get(key);
174         if (e == null) {
175             e = new InvokeDynamicEntry(bssRef, descRef);
176             assert(e.stringValue().equals(key));
177             invokeDynamicEntries.put(key, e);
178         }
179         return e;
180     }
181 
182     /** Factory for BootstrapMethod pseudo-constants. */
183     public static BootstrapMethodEntry getBootstrapMethodEntry(MethodHandleEntry bsmRef, Entry[] argRefs) {
184         Map<String, BootstrapMethodEntry> bootstrapMethodEntries = Utils.getTLGlobals().getBootstrapMethodEntries();
185         String key = BootstrapMethodEntry.stringValueOf(bsmRef, argRefs);
186         BootstrapMethodEntry e = bootstrapMethodEntries.get(key);
187         if (e == null) {
188             e = new BootstrapMethodEntry(bsmRef, argRefs);
189             assert(e.stringValue().equals(key));
190             bootstrapMethodEntries.put(key, e);
191         }
192         return e;
193     }
194 
195 
196     /** Entries in the constant pool. */
197     public static abstract
198     class Entry implements Comparable<Object> {
199         protected final byte tag;       // a CONSTANT_foo code
200         protected int valueHash;        // cached hashCode
201 
202         protected Entry(byte tag) {
203             this.tag = tag;
204         }
205 
206         public final byte getTag() {
207             return tag;
208         }
209 
210         public final boolean tagEquals(int tag) {
211             return getTag() == tag;
212         }
213 
214         public Entry getRef(int i) {
215             return null;
216         }
217 
218         public boolean eq(Entry that) {  // same reference
219             assert(that != null);
220             return this == that || this.equals(that);
221         }
222 
223         // Equality of Entries is value-based.
224         public abstract boolean equals(Object o);
225         public final int hashCode() {
226             if (valueHash == 0) {
227                 valueHash = computeValueHash();
228                 if (valueHash == 0)  valueHash = 1;
229             }
230             return valueHash;
231         }
232         protected abstract int computeValueHash();
233 
234         public abstract int compareTo(Object o);
235 
236         protected int superCompareTo(Object o) {
237             Entry that = (Entry) o;
238 
239             if (this.tag != that.tag) {
240                 return TAG_ORDER[this.tag] - TAG_ORDER[that.tag];
241             }
242 
243             return 0;  // subclasses must refine this
244         }
245 
246         public final boolean isDoubleWord() {
247             return tag == CONSTANT_Double || tag == CONSTANT_Long;
248         }
249 
250         public final boolean tagMatches(int matchTag) {
251             if (tag == matchTag)
252                 return true;
253             byte[] allowedTags;
254             switch (matchTag) {
255                 case CONSTANT_All:
256                     return true;
257                 case CONSTANT_Signature:
258                     return tag == CONSTANT_Utf8;  // format check also?
259                 case CONSTANT_LoadableValue:
260                     allowedTags = LOADABLE_VALUE_TAGS;
261                     break;
262                 case CONSTANT_AnyMember:
263                     allowedTags = ANY_MEMBER_TAGS;
264                     break;
265                 case CONSTANT_FieldSpecific:
266                     allowedTags = FIELD_SPECIFIC_TAGS;
267                     break;
268                 default:
269                     return false;
270             }
271             for (byte b : allowedTags) {
272                 if (b == tag)
273                     return true;
274             }
275             return false;
276         }
277 
278         public String toString() {
279             String valuePrint = stringValue();
280             if (verbose() > 4) {
281                 if (valueHash != 0)
282                     valuePrint += " hash="+valueHash;
283                 valuePrint += " id="+System.identityHashCode(this);
284             }
285             return tagName(tag)+"="+valuePrint;
286         }
287         public abstract String stringValue();
288     }
289 
290     public static
291     class Utf8Entry extends Entry {
292         final String value;
293 
294         Utf8Entry(String value) {
295             super(CONSTANT_Utf8);
296             this.value = value.intern();
297             hashCode();  // force computation of valueHash
298         }
299         protected int computeValueHash() {
300             return value.hashCode();
301         }
302         public boolean equals(Object o) {
303             // Use reference equality of interned strings:
304             return (o != null && o.getClass() == Utf8Entry.class
305                     && ((Utf8Entry) o).value.equals(value));
306         }
307         public int compareTo(Object o) {
308             int x = superCompareTo(o);
309             if (x == 0) {
310                 x = value.compareTo(((Utf8Entry)o).value);
311             }
312             return x;
313         }
314         public String stringValue() {
315             return value;
316         }
317     }
318 
319     static boolean isMemberTag(byte tag) {
320         switch (tag) {
321         case CONSTANT_Fieldref:
322         case CONSTANT_Methodref:
323         case CONSTANT_InterfaceMethodref:
324             return true;
325         }
326         return false;
327     }
328 
329     static byte numberTagOf(Number value) {
330         if (value instanceof Integer)  return CONSTANT_Integer;
331         if (value instanceof Float)    return CONSTANT_Float;
332         if (value instanceof Long)     return CONSTANT_Long;
333         if (value instanceof Double)   return CONSTANT_Double;
334         throw new RuntimeException("bad literal value "+value);
335     }
336 
337     static boolean isRefKind(byte refKind) {
338         return (REF_getField <= refKind && refKind <= REF_invokeInterface);
339     }
340 
341     public static abstract
342     class LiteralEntry extends Entry {
343         protected LiteralEntry(byte tag) {
344             super(tag);
345         }
346 
347         public abstract Comparable<?> literalValue();
348     }
349 
350     public static
351     class NumberEntry extends LiteralEntry {
352         final Number value;
353         NumberEntry(Number value) {
354             super(numberTagOf(value));
355             this.value = value;
356             hashCode();  // force computation of valueHash
357         }
358         protected int computeValueHash() {
359             return value.hashCode();
360         }
361 
362         public boolean equals(Object o) {
363             return (o != null && o.getClass() == NumberEntry.class
364                     && ((NumberEntry) o).value.equals(value));
365 
366         }
367         public int compareTo(Object o) {
368             int x = superCompareTo(o);
369             if (x == 0) {
370                 @SuppressWarnings("unchecked")
371                 Comparable<Number> compValue = (Comparable<Number>)value;
372                 x = compValue.compareTo(((NumberEntry)o).value);
373             }
374             return x;
375         }
376         public Number numberValue() {
377             return value;
378         }
379         public Comparable<?> literalValue() {
380             return (Comparable<?>) value;
381         }
382         public String stringValue() {
383             return value.toString();
384         }
385     }
386 
387     public static
388     class StringEntry extends LiteralEntry {
389         final Utf8Entry ref;
390         public Entry getRef(int i) { return i == 0 ? ref : null; }
391 
392         StringEntry(Entry ref) {
393             super(CONSTANT_String);
394             this.ref = (Utf8Entry) ref;
395             hashCode();  // force computation of valueHash
396         }
397         protected int computeValueHash() {
398             return ref.hashCode() + tag;
399         }
400         public boolean equals(Object o) {
401             return (o != null && o.getClass() == StringEntry.class &&
402                     ((StringEntry)o).ref.eq(ref));
403         }
404         public int compareTo(Object o) {
405             int x = superCompareTo(o);
406             if (x == 0) {
407                 x = ref.compareTo(((StringEntry)o).ref);
408             }
409             return x;
410         }
411         public Comparable<?> literalValue() {
412             return ref.stringValue();
413         }
414         public String stringValue() {
415             return ref.stringValue();
416         }
417     }
418 
419     public static
420     class ClassEntry extends Entry {
421         final Utf8Entry ref;
422         public Entry getRef(int i) { return i == 0 ? ref : null; }
423 
424         protected int computeValueHash() {
425             return ref.hashCode() + tag;
426         }
427         ClassEntry(Entry ref) {
428             super(CONSTANT_Class);
429             this.ref = (Utf8Entry) ref;
430             hashCode();  // force computation of valueHash
431         }
432         public boolean equals(Object o) {
433             return (o != null && o.getClass() == ClassEntry.class
434                     && ((ClassEntry) o).ref.eq(ref));
435         }
436         public int compareTo(Object o) {
437             int x = superCompareTo(o);
438             if (x == 0) {
439                 x = ref.compareTo(((ClassEntry)o).ref);
440             }
441             return x;
442         }
443         public String stringValue() {
444             return ref.stringValue();
445         }
446     }
447 
448     public static
449     class DescriptorEntry extends Entry {
450         final Utf8Entry      nameRef;
451         final SignatureEntry typeRef;
452         public Entry getRef(int i) {
453             if (i == 0)  return nameRef;
454             if (i == 1)  return typeRef;
455             return null;
456         }
457         DescriptorEntry(Entry nameRef, Entry typeRef) {
458             super(CONSTANT_NameandType);
459             if (typeRef instanceof Utf8Entry) {
460                 typeRef = getSignatureEntry(typeRef.stringValue());
461             }
462             this.nameRef = (Utf8Entry) nameRef;
463             this.typeRef = (SignatureEntry) typeRef;
464             hashCode();  // force computation of valueHash
465         }
466         protected int computeValueHash() {
467             int hc2 = typeRef.hashCode();
468             return (nameRef.hashCode() + (hc2 << 8)) ^ hc2;
469         }
470         public boolean equals(Object o) {
471             if (o == null || o.getClass() != DescriptorEntry.class) {
472                 return false;
473             }
474             DescriptorEntry that = (DescriptorEntry)o;
475             return this.nameRef.eq(that.nameRef)
476                 && this.typeRef.eq(that.typeRef);
477         }
478         public int compareTo(Object o) {
479             int x = superCompareTo(o);
480             if (x == 0) {
481                 DescriptorEntry that = (DescriptorEntry)o;
482                 // Primary key is typeRef, not nameRef.
483                 x = this.typeRef.compareTo(that.typeRef);
484                 if (x == 0)
485                     x = this.nameRef.compareTo(that.nameRef);
486             }
487             return x;
488         }
489         public String stringValue() {
490             return stringValueOf(nameRef, typeRef);
491         }
492         static
493         String stringValueOf(Entry nameRef, Entry typeRef) {
494             return qualifiedStringValue(typeRef, nameRef);
495         }
496 
497         public String prettyString() {
498             return nameRef.stringValue()+typeRef.prettyString();
499         }
500 
501         public boolean isMethod() {
502             return typeRef.isMethod();
503         }
504 
505         public byte getLiteralTag() {
506             return typeRef.getLiteralTag();
507         }
508     }
509 
510     static String qualifiedStringValue(Entry e1, Entry e2) {
511         return qualifiedStringValue(e1.stringValue(), e2.stringValue());
512     }
513     static String qualifiedStringValue(String s1, String s234) {
514         // Qualification by dot must decompose uniquely.  Second string might already be qualified.
515         assert(s1.indexOf(".") < 0);
516         return s1+"."+s234;
517     }
518 
519     public static
520     class MemberEntry extends Entry {
521         final ClassEntry classRef;
522         final DescriptorEntry descRef;
523         public Entry getRef(int i) {
524             if (i == 0)  return classRef;
525             if (i == 1)  return descRef;
526             return null;
527         }
528         protected int computeValueHash() {
529             int hc2 = descRef.hashCode();
530             return (classRef.hashCode() + (hc2 << 8)) ^ hc2;
531         }
532 
533         MemberEntry(byte tag, ClassEntry classRef, DescriptorEntry descRef) {
534             super(tag);
535             assert(isMemberTag(tag));
536             this.classRef = classRef;
537             this.descRef  = descRef;
538             hashCode();  // force computation of valueHash
539         }
540         public boolean equals(Object o) {
541             if (o == null || o.getClass() != MemberEntry.class) {
542                 return false;
543             }
544             MemberEntry that = (MemberEntry)o;
545             return this.classRef.eq(that.classRef)
546                 && this.descRef.eq(that.descRef);
547         }
548         public int compareTo(Object o) {
549             int x = superCompareTo(o);
550             if (x == 0) {
551                 MemberEntry that = (MemberEntry)o;
552                 if (Utils.SORT_MEMBERS_DESCR_MAJOR)
553                     // descRef is transmitted as UDELTA5; sort it first?
554                     x = this.descRef.compareTo(that.descRef);
555                 // Primary key is classRef.
556                 if (x == 0)
557                     x = this.classRef.compareTo(that.classRef);
558                 if (x == 0)
559                     x = this.descRef.compareTo(that.descRef);
560             }
561             return x;
562         }
563         public String stringValue() {
564             return stringValueOf(tag, classRef, descRef);
565         }
566         static
567         String stringValueOf(byte tag, ClassEntry classRef, DescriptorEntry descRef) {
568             assert(isMemberTag(tag));
569             String pfx;
570             switch (tag) {
571             case CONSTANT_Fieldref:            pfx = "Field:";   break;
572             case CONSTANT_Methodref:           pfx = "Method:";  break;
573             case CONSTANT_InterfaceMethodref:  pfx = "IMethod:"; break;
574             default:                           pfx = tag+"???";  break;
575             }
576             return pfx+qualifiedStringValue(classRef, descRef);
577         }
578 
579         public boolean isMethod() {
580             return descRef.isMethod();
581         }
582     }
583 
584     public static
585     class SignatureEntry extends Entry {
586         final Utf8Entry    formRef;
587         final ClassEntry[] classRefs;
588         String             value;
589         Utf8Entry          asUtf8Entry;
590         public Entry getRef(int i) {
591             if (i == 0)  return formRef;
592             return i-1 < classRefs.length ? classRefs[i-1] : null;
593         }
594         SignatureEntry(String value) {
595             super(CONSTANT_Signature);
596             value = value.intern();  // always do this
597             this.value = value;
598             String[] parts = structureSignature(value);
599             formRef = getUtf8Entry(parts[0]);
600             classRefs = new ClassEntry[parts.length-1];
601             for (int i = 1; i < parts.length; i++) {
602                 classRefs[i - 1] = getClassEntry(parts[i]);
603             }
604             hashCode();  // force computation of valueHash
605         }
606         protected int computeValueHash() {
607             stringValue();  // force computation of value
608             return value.hashCode() + tag;
609         }
610 
611         public Utf8Entry asUtf8Entry() {
612             if (asUtf8Entry == null) {
613                 asUtf8Entry = getUtf8Entry(stringValue());
614             }
615             return asUtf8Entry;
616         }
617 
618         public boolean equals(Object o) {
619             return (o != null && o.getClass() == SignatureEntry.class &&
620                     ((SignatureEntry)o).value.equals(value));
621         }
622         public int compareTo(Object o) {
623             int x = superCompareTo(o);
624             if (x == 0) {
625                 SignatureEntry that = (SignatureEntry)o;
626                 x = compareSignatures(this.value, that.value);
627             }
628             return x;
629         }
630         public String stringValue() {
631             if (value == null) {
632                 value = stringValueOf(formRef, classRefs);
633             }
634             return value;
635         }
636         static
637         String stringValueOf(Utf8Entry formRef, ClassEntry[] classRefs) {
638             String[] parts = new String[1+classRefs.length];
639             parts[0] = formRef.stringValue();
640             for (int i = 1; i < parts.length; i++) {
641                 parts[i] = classRefs[i - 1].stringValue();
642             }
643             return flattenSignature(parts).intern();
644         }
645 
646         public int computeSize(boolean countDoublesTwice) {
647             String form = formRef.stringValue();
648             int min = 0;
649             int max = 1;
650             if (isMethod()) {
651                 min = 1;
652                 max = form.indexOf(')');
653             }
654             int size = 0;
655             for (int i = min; i < max; i++) {
656                 switch (form.charAt(i)) {
657                     case 'D':
658                     case 'J':
659                         if (countDoublesTwice) {
660                             size++;
661                         }
662                         break;
663                     case '[':
664                         // Skip rest of array info.
665                         while (form.charAt(i) == '[') {
666                             ++i;
667                         }
668                         break;
669                     case ';':
670                         continue;
671                     default:
672                         assert (0 <= JAVA_SIGNATURE_CHARS.indexOf(form.charAt(i)));
673                         break;
674                 }
675                 size++;
676             }
677             return size;
678         }
679         public boolean isMethod() {
680             return formRef.stringValue().charAt(0) == '(';
681         }
682         public byte getLiteralTag() {
683             switch (formRef.stringValue().charAt(0)) {
684             case 'I': return CONSTANT_Integer;
685             case 'J': return CONSTANT_Long;
686             case 'F': return CONSTANT_Float;
687             case 'D': return CONSTANT_Double;
688             case 'B': case 'S': case 'C': case 'Z':
689                 return CONSTANT_Integer;
690             case 'L':
691                 /*
692                 switch (classRefs[0].stringValue()) {
693                 case "java/lang/String":
694                     return CONSTANT_String;
695                 case "java/lang/invoke/MethodHandle":
696                     return CONSTANT_MethodHandle;
697                 case "java/lang/invoke/MethodType":
698                     return CONSTANT_MethodType;
699                 default:  // java/lang/Object, etc.
700                     return CONSTANT_LoadableValue;
701                 }
702                 */
703                 return CONSTANT_String;  // JDK 7 ConstantValue limited to String
704             }
705             assert(false);
706             return CONSTANT_None;
707         }
708         public String prettyString() {
709             String s;
710             if (isMethod()) {
711                 s = formRef.stringValue();
712                 s = s.substring(0, 1+s.indexOf(')'));
713             } else {
714                 s = "/" + formRef.stringValue();
715             }
716             int i;
717             while ((i = s.indexOf(';')) >= 0) {
718                 s = s.substring(0, i) + s.substring(i + 1);
719             }
720             return s;
721         }
722     }
723 
724     static int compareSignatures(String s1, String s2) {
725         return compareSignatures(s1, s2, null, null);
726     }
727     static int compareSignatures(String s1, String s2, String[] p1, String[] p2) {
728         final int S1_COMES_FIRST = -1;
729         final int S2_COMES_FIRST = +1;
730         char c1 = s1.charAt(0);
731         char c2 = s2.charAt(0);
732         // fields before methods (because there are fewer of them)
733         if (c1 != '(' && c2 == '(')  return S1_COMES_FIRST;
734         if (c2 != '(' && c1 == '(')  return S2_COMES_FIRST;
735         if (p1 == null)  p1 = structureSignature(s1);
736         if (p2 == null)  p2 = structureSignature(s2);
737         /*
738          // non-classes before classes (because there are fewer of them)
739          if (p1.length == 1 && p2.length > 1)  return S1_COMES_FIRST;
740          if (p2.length == 1 && p1.length > 1)  return S2_COMES_FIRST;
741          // all else being equal, use the same comparison as for Utf8 strings
742          return s1.compareTo(s2);
743          */
744         if (p1.length != p2.length)  return p1.length - p2.length;
745         int length = p1.length;
746         for (int i = length; --i >= 0; ) {
747             int res = p1[i].compareTo(p2[i]);
748             if (res != 0)  return res;
749         }
750         assert(s1.equals(s2));
751         return 0;
752     }
753 
754     static int countClassParts(Utf8Entry formRef) {
755         int num = 0;
756         String s = formRef.stringValue();
757         for (int i = 0; i < s.length(); i++) {
758             if (s.charAt(i) == 'L')  ++num;
759         }
760         return num;
761     }
762 
763     static String flattenSignature(String[] parts) {
764         String form = parts[0];
765         if (parts.length == 1)  return form;
766         int len = form.length();
767         for (int i = 1; i < parts.length; i++) {
768             len += parts[i].length();
769         }
770         char[] sig = new char[len];
771         int j = 0;
772         int k = 1;
773         for (int i = 0; i < form.length(); i++) {
774             char ch = form.charAt(i);
775             sig[j++] = ch;
776             if (ch == 'L') {
777                 String cls = parts[k++];
778                 cls.getChars(0, cls.length(), sig, j);
779                 j += cls.length();
780                 //sig[j++] = ';';
781             }
782         }
783         assert(j == len);
784         assert(k == parts.length);
785         return new String(sig);
786     }
787 
788     static private int skipTo(char semi, String sig, int i) {
789         i = sig.indexOf(semi, i);
790         return (i >= 0) ? i : sig.length();
791     }
792 
793     static String[] structureSignature(String sig) {
794         int firstl = sig.indexOf('L');
795         if (firstl < 0) {
796             String[] parts = { sig };
797             return parts;
798         }
799         // Segment the string like sig.split("L\\([^;<]*\\)").
800         // N.B.: Previous version of this code did a more complex match,
801         // to next ch < ' ' or ch in [';'..'@'].  The only important
802         // characters are ';' and '<', since they are part of the
803         // signature syntax.
804         // Examples:
805         //   "(Ljava/lang/Object;IJLLoo;)V" => {"(L;IJL;)V", "java/lang/Object", "Loo"}
806         //   "Ljava/util/List<Ljava/lang/String;>;" => {"L<L;>;", "java/util/List", "java/lang/String"}
807         char[] form = null;
808         String[] parts = null;
809         for (int pass = 0; pass <= 1; pass++) {
810             // pass 0 is a sizing pass, pass 1 packs the arrays
811             int formPtr = 0;
812             int partPtr = 1;
813             int nextsemi = 0, nextangl = 0;  // next ';' or '<', or zero, or sigLen
814             int lastj = 0;
815             for (int i = firstl + 1, j; i > 0; i = sig.indexOf('L', j) + 1) {
816                 // sig[i-1] is 'L', while sig[j] will be the first ';' or '<' after it
817                 // each part is in sig[i .. j-1]
818                 if (nextsemi < i)  nextsemi = skipTo(';', sig, i);
819                 if (nextangl < i)  nextangl = skipTo('<', sig, i);
820                 j = (nextsemi < nextangl ? nextsemi : nextangl);
821                 if (pass != 0) {
822                     sig.getChars(lastj, i, form, formPtr);
823                     parts[partPtr] = sig.substring(i, j);
824                 }
825                 formPtr += (i - lastj);
826                 partPtr += 1;
827                 lastj = j;
828             }
829             if (pass != 0) {
830                 sig.getChars(lastj, sig.length(), form, formPtr);
831                 break;
832             }
833             formPtr += (sig.length() - lastj);
834             form = new char[formPtr];
835             parts = new String[partPtr];
836         }
837         parts[0] = new String(form);
838         //assert(flattenSignature(parts).equals(sig));
839         return parts;
840     }
841 
842     /** @since JDK 7, JSR 292 */
843     public static
844     class MethodHandleEntry extends Entry {
845         final int refKind;
846         final MemberEntry memRef;
847         public Entry getRef(int i) { return i == 0 ? memRef : null; }
848 
849         protected int computeValueHash() {
850             int hc2 = refKind;
851             return (memRef.hashCode() + (hc2 << 8)) ^ hc2;
852         }
853 
854         MethodHandleEntry(byte refKind, MemberEntry memRef) {
855             super(CONSTANT_MethodHandle);
856             assert(isRefKind(refKind));
857             this.refKind = refKind;
858             this.memRef  = memRef;
859             hashCode();  // force computation of valueHash
860         }
861         public boolean equals(Object o) {
862             if (o == null || o.getClass() != MethodHandleEntry.class) {
863                 return false;
864             }
865             MethodHandleEntry that = (MethodHandleEntry)o;
866             return this.refKind == that.refKind
867                 && this.memRef.eq(that.memRef);
868         }
869         public int compareTo(Object o) {
870             int x = superCompareTo(o);
871             if (x == 0) {
872                 MethodHandleEntry that = (MethodHandleEntry)o;
873                 if (Utils.SORT_HANDLES_KIND_MAJOR)
874                     // Primary key could be refKind.
875                     x = this.refKind - that.refKind;
876                 // Primary key is memRef, which is transmitted as UDELTA5.
877                 if (x == 0)
878                     x = this.memRef.compareTo(that.memRef);
879                 if (x == 0)
880                     x = this.refKind - that.refKind;
881             }
882             return x;
883         }
884         public static String stringValueOf(int refKind, MemberEntry memRef) {
885             return refKindName(refKind)+":"+memRef.stringValue();
886         }
887         public String stringValue() {
888             return stringValueOf(refKind, memRef);
889         }
890     }
891 
892     /** @since JDK 7, JSR 292 */
893     public static
894     class MethodTypeEntry extends Entry {
895         final SignatureEntry typeRef;
896         public Entry getRef(int i) { return i == 0 ? typeRef : null; }
897 
898         protected int computeValueHash() {
899             return typeRef.hashCode() + tag;
900         }
901 
902         MethodTypeEntry(SignatureEntry typeRef) {
903             super(CONSTANT_MethodType);
904             this.typeRef  = typeRef;
905             hashCode();  // force computation of valueHash
906         }
907         public boolean equals(Object o) {
908             if (o == null || o.getClass() != MethodTypeEntry.class) {
909                 return false;
910             }
911             MethodTypeEntry that = (MethodTypeEntry)o;
912             return this.typeRef.eq(that.typeRef);
913         }
914         public int compareTo(Object o) {
915             int x = superCompareTo(o);
916             if (x == 0) {
917                 MethodTypeEntry that = (MethodTypeEntry)o;
918                 x = this.typeRef.compareTo(that.typeRef);
919             }
920             return x;
921         }
922         public String stringValue() {
923             return typeRef.stringValue();
924         }
925     }
926 
927     /** @since JDK 7, JSR 292 */
928     public static
929     class InvokeDynamicEntry extends Entry {
930         final BootstrapMethodEntry bssRef;
931         final DescriptorEntry descRef;
932         public Entry getRef(int i) {
933             if (i == 0)  return bssRef;
934             if (i == 1)  return descRef;
935             return null;
936         }
937         protected int computeValueHash() {
938             int hc2 = descRef.hashCode();
939             return (bssRef.hashCode() + (hc2 << 8)) ^ hc2;
940         }
941 
942         InvokeDynamicEntry(BootstrapMethodEntry bssRef, DescriptorEntry descRef) {
943             super(CONSTANT_InvokeDynamic);
944             this.bssRef  = bssRef;
945             this.descRef = descRef;
946             hashCode();  // force computation of valueHash
947         }
948         public boolean equals(Object o) {
949             if (o == null || o.getClass() != InvokeDynamicEntry.class) {
950                 return false;
951             }
952             InvokeDynamicEntry that = (InvokeDynamicEntry)o;
953             return this.bssRef.eq(that.bssRef)
954                 && this.descRef.eq(that.descRef);
955         }
956         public int compareTo(Object o) {
957             int x = superCompareTo(o);
958             if (x == 0) {
959                 InvokeDynamicEntry that = (InvokeDynamicEntry)o;
960                 if (Utils.SORT_INDY_BSS_MAJOR)
961                     // Primary key could be bsmRef.
962                     x = this.bssRef.compareTo(that.bssRef);
963                 // Primary key is descriptor, which is transmitted as UDELTA5.
964                 if (x == 0)
965                     x = this.descRef.compareTo(that.descRef);
966                 if (x == 0)
967                     x = this.bssRef.compareTo(that.bssRef);
968             }
969             return x;
970         }
971         public String stringValue() {
972             return stringValueOf(bssRef, descRef);
973         }
974         static
975         String stringValueOf(BootstrapMethodEntry bssRef, DescriptorEntry descRef) {
976             return "Indy:"+bssRef.stringValue()+"."+descRef.stringValue();
977         }
978     }
979 
980     /** @since JDK 7, JSR 292 */
981     public static
982     class BootstrapMethodEntry extends Entry {
983         final MethodHandleEntry bsmRef;
984         final Entry[] argRefs;
985         public Entry getRef(int i) {
986             if (i == 0)  return bsmRef;
987             if (i-1 < argRefs.length)  return argRefs[i-1];
988             return null;
989         }
990         protected int computeValueHash() {
991             int hc2 = bsmRef.hashCode();
992             return (Arrays.hashCode(argRefs) + (hc2 << 8)) ^ hc2;
993         }
994 
995         BootstrapMethodEntry(MethodHandleEntry bsmRef, Entry[] argRefs) {
996             super(CONSTANT_BootstrapMethod);
997             this.bsmRef  = bsmRef;
998             this.argRefs = argRefs.clone();
999             hashCode();  // force computation of valueHash
1000         }
1001         public boolean equals(Object o) {
1002             if (o == null || o.getClass() != BootstrapMethodEntry.class) {
1003                 return false;
1004             }
1005             BootstrapMethodEntry that = (BootstrapMethodEntry)o;
1006             return this.bsmRef.eq(that.bsmRef)
1007                 && Arrays.equals(this.argRefs, that.argRefs);
1008         }
1009         public int compareTo(Object o) {
1010             int x = superCompareTo(o);
1011             if (x == 0) {
1012                 BootstrapMethodEntry that = (BootstrapMethodEntry)o;
1013                 if (Utils.SORT_BSS_BSM_MAJOR)
1014                     // Primary key is bsmRef.
1015                     x = this.bsmRef.compareTo(that.bsmRef);
1016                 // Primary key is args array length, which is transmitted as UDELTA5.
1017                 if (x == 0)
1018                     x = compareArgArrays(this.argRefs, that.argRefs);
1019                 if (x == 0)
1020                     x = this.bsmRef.compareTo(that.bsmRef);
1021             }
1022             return x;
1023         }
1024         public String stringValue() {
1025             return stringValueOf(bsmRef, argRefs);
1026         }
1027         static
1028         String stringValueOf(MethodHandleEntry bsmRef, Entry[] argRefs) {
1029             StringBuffer sb = new StringBuffer(bsmRef.stringValue());
1030             // Arguments are formatted as "<foo;bar;baz>" instead of "[foo,bar,baz]".
1031             // This ensures there will be no confusion if "[,]" appear inside of names.
1032             char nextSep = '<';
1033             boolean didOne = false;
1034             for (Entry argRef : argRefs) {
1035                 sb.append(nextSep).append(argRef.stringValue());
1036                 nextSep = ';';
1037             }
1038             if (nextSep == '<')  sb.append(nextSep);
1039             sb.append('>');
1040             return sb.toString();
1041         }
1042         static
1043         int compareArgArrays(Entry[] a1, Entry[] a2) {
1044             int x = a1.length - a2.length;
1045             if (x != 0)  return x;
1046             for (int i = 0; i < a1.length; i++) {
1047                 x = a1[i].compareTo(a2[i]);
1048                 if (x != 0)  break;
1049             }
1050             return x;
1051         }
1052     }
1053 
1054     // Handy constants:
1055     protected static final Entry[] noRefs = {};
1056     protected static final ClassEntry[] noClassRefs = {};
1057 
1058     /** An Index is a mapping between CP entries and small integers. */
1059     public static final
1060     class Index extends AbstractList<Entry> {
1061         protected String debugName;
1062         protected Entry[] cpMap;
1063         protected boolean flattenSigs;
1064         protected Entry[] getMap() {
1065             return cpMap;
1066         }
1067         protected Index(String debugName) {
1068             this.debugName = debugName;
1069         }
1070         protected Index(String debugName, Entry[] cpMap) {
1071             this(debugName);
1072             setMap(cpMap);
1073         }
1074         protected void setMap(Entry[] cpMap) {
1075             clearIndex();
1076             this.cpMap = cpMap;
1077         }
1078         protected Index(String debugName, Collection<Entry> cpMapList) {
1079             this(debugName);
1080             setMap(cpMapList);
1081         }
1082         protected void setMap(Collection<Entry> cpMapList) {
1083             cpMap = new Entry[cpMapList.size()];
1084             cpMapList.toArray(cpMap);
1085             setMap(cpMap);
1086         }
1087         public int size() {
1088             return cpMap.length;
1089         }
1090         public Entry get(int i) {
1091             return cpMap[i];
1092         }
1093         public Entry getEntry(int i) {
1094             // same as get(), with covariant return type
1095             return cpMap[i];
1096         }
1097 
1098         // Find index of e in cpMap, or return -1 if none.
1099         //
1100         // As a special hack, if flattenSigs, signatures are
1101         // treated as equivalent entries of cpMap.  This is wrong
1102         // from a Collection point of view, because contains()
1103         // reports true for signatures, but the iterator()
1104         // never produces them!
1105         private int findIndexOf(Entry e) {
1106             if (indexKey == null) {
1107                 initializeIndex();
1108             }
1109             int probe = findIndexLocation(e);
1110             if (indexKey[probe] != e) {
1111                 if (flattenSigs && e.tag == CONSTANT_Signature) {
1112                     SignatureEntry se = (SignatureEntry) e;
1113                     return findIndexOf(se.asUtf8Entry());
1114                 }
1115                 return -1;
1116             }
1117             int index = indexValue[probe];
1118             assert(e.equals(cpMap[index]));
1119             return index;
1120         }
1121         public boolean contains(Entry e) {
1122             return findIndexOf(e) >= 0;
1123         }
1124         // Find index of e in cpMap.  Should not return -1.
1125         public int indexOf(Entry e) {
1126             int index = findIndexOf(e);
1127             if (index < 0 && verbose() > 0) {
1128                 System.out.println("not found: "+e);
1129                 System.out.println("       in: "+this.dumpString());
1130                 Thread.dumpStack();
1131             }
1132             assert(index >= 0);
1133             return index;
1134         }
1135         public int lastIndexOf(Entry e) {
1136             return indexOf(e);
1137         }
1138 
1139         public boolean assertIsSorted() {
1140             for (int i = 1; i < cpMap.length; i++) {
1141                 if (cpMap[i-1].compareTo(cpMap[i]) > 0) {
1142                     System.out.println("Not sorted at "+(i-1)+"/"+i+": "+this.dumpString());
1143                     return false;
1144                 }
1145             }
1146             return true;
1147         }
1148 
1149         // internal hash table
1150         protected Entry[] indexKey;
1151         protected int[]   indexValue;
1152         protected void clearIndex() {
1153             indexKey   = null;
1154             indexValue = null;
1155         }
1156         private int findIndexLocation(Entry e) {
1157             int size   = indexKey.length;
1158             int hash   = e.hashCode();
1159             int probe  = hash & (size - 1);
1160             int stride = ((hash >>> 8) | 1) & (size - 1);
1161             for (;;) {
1162                 Entry e1 = indexKey[probe];
1163                 if (e1 == e || e1 == null)
1164                     return probe;
1165                 probe += stride;
1166                 if (probe >= size)  probe -= size;
1167             }
1168         }
1169         private void initializeIndex() {
1170             if (verbose() > 2)
1171                 System.out.println("initialize Index "+debugName+" ["+size()+"]");
1172             int hsize0 = (int)((cpMap.length + 10) * 1.5);
1173             int hsize = 1;
1174             while (hsize < hsize0) {
1175                 hsize <<= 1;
1176             }
1177             indexKey   = new Entry[hsize];
1178             indexValue = new int[hsize];
1179             for (int i = 0; i < cpMap.length; i++) {
1180                 Entry e = cpMap[i];
1181                 if (e == null)  continue;
1182                 int probe = findIndexLocation(e);
1183                 assert(indexKey[probe] == null);  // e has unique index
1184                 indexKey[probe] = e;
1185                 indexValue[probe] = i;
1186             }
1187         }
1188         public Entry[] toArray(Entry[] a) {
1189             int sz = size();
1190             if (a.length < sz)  return super.toArray(a);
1191             System.arraycopy(cpMap, 0, a, 0, sz);
1192             if (a.length > sz)  a[sz] = null;
1193             return a;
1194         }
1195         public Entry[] toArray() {
1196             return toArray(new Entry[size()]);
1197         }
1198         public Object clone() {
1199             return new Index(debugName, cpMap.clone());
1200         }
1201         public String toString() {
1202             return "Index "+debugName+" ["+size()+"]";
1203         }
1204         public String dumpString() {
1205             String s = toString();
1206             s += " {\n";
1207             for (int i = 0; i < cpMap.length; i++) {
1208                 s += "    "+i+": "+cpMap[i]+"\n";
1209             }
1210             s += "}";
1211             return s;
1212         }
1213     }
1214 
1215     // Index methods.
1216 
1217     public static
1218     Index makeIndex(String debugName, Entry[] cpMap) {
1219         return new Index(debugName, cpMap);
1220     }
1221 
1222     public static
1223     Index makeIndex(String debugName, Collection<Entry> cpMapList) {
1224         return new Index(debugName, cpMapList);
1225     }
1226 
1227     /** Sort this index (destructively) into canonical order. */
1228     public static
1229     void sort(Index ix) {
1230         // %%% Should move this into class Index.
1231         ix.clearIndex();
1232         Arrays.sort(ix.cpMap);
1233         if (verbose() > 2)
1234             System.out.println("sorted "+ix.dumpString());
1235     }
1236 
1237     /** Return a set of indexes partitioning these entries.
1238      *  The keys array must of length this.size(), and marks entries.
1239      *  The result array is as long as one plus the largest key value.
1240      *  Entries with a negative key are dropped from the partition.
1241      */
1242     public static
1243     Index[] partition(Index ix, int[] keys) {
1244         // %%% Should move this into class Index.
1245         List<List<Entry>> parts = new ArrayList<>();
1246         Entry[] cpMap = ix.cpMap;
1247         assert(keys.length == cpMap.length);
1248         for (int i = 0; i < keys.length; i++) {
1249             int key = keys[i];
1250             if (key < 0)  continue;
1251             while (key >= parts.size()) {
1252                 parts.add(null);
1253             }
1254             List<Entry> part = parts.get(key);
1255             if (part == null) {
1256                 parts.set(key, part = new ArrayList<>());
1257             }
1258             part.add(cpMap[i]);
1259         }
1260         Index[] indexes = new Index[parts.size()];
1261         for (int key = 0; key < indexes.length; key++) {
1262             List<Entry> part = parts.get(key);
1263             if (part == null)  continue;
1264             indexes[key] = new Index(ix.debugName+"/part#"+key, part);
1265             assert(indexes[key].indexOf(part.get(0)) == 0);
1266         }
1267         return indexes;
1268     }
1269     public static
1270     Index[] partitionByTag(Index ix) {
1271         // Partition by tag.
1272         Entry[] cpMap = ix.cpMap;
1273         int[] keys = new int[cpMap.length];
1274         for (int i = 0; i < keys.length; i++) {
1275             Entry e = cpMap[i];
1276             keys[i] = (e == null)? -1: e.tag;
1277         }
1278         Index[] byTag = partition(ix, keys);
1279         for (int tag = 0; tag < byTag.length; tag++) {
1280             if (byTag[tag] == null)  continue;
1281             byTag[tag].debugName = tagName(tag);
1282         }
1283         if (byTag.length < CONSTANT_Limit) {
1284             Index[] longer = new Index[CONSTANT_Limit];
1285             System.arraycopy(byTag, 0, longer, 0, byTag.length);
1286             byTag = longer;
1287         }
1288         return byTag;
1289     }
1290 
1291     /** Coherent group of constant pool indexes. */
1292     public static
1293     class IndexGroup {
1294         private Index[] indexByTag = new Index[CONSTANT_Limit];
1295         private Index[] indexByTagGroup;
1296         private int[]   untypedFirstIndexByTag;
1297         private int     totalSizeQQ;
1298         private Index[][] indexByTagAndClass;
1299 
1300         /** Index of all CP entries of all types, in definition order. */
1301         private Index makeTagGroupIndex(byte tagGroupTag, byte[] tagsInGroup) {
1302             if (indexByTagGroup == null)
1303                 indexByTagGroup = new Index[CONSTANT_GroupLimit - CONSTANT_GroupFirst];
1304             int which = tagGroupTag - CONSTANT_GroupFirst;
1305             assert(indexByTagGroup[which] == null);
1306             int fillp = 0;
1307             Entry[] cpMap = null;
1308             for (int pass = 1; pass <= 2; pass++) {
1309                 untypedIndexOf(null);  // warm up untypedFirstIndexByTag
1310                 for (byte tag : tagsInGroup) {
1311                     Index ix = indexByTag[tag];
1312                     if (ix == null)  continue;
1313                     int ixLen = ix.cpMap.length;
1314                     if (ixLen == 0)  continue;
1315                     assert(tagGroupTag == CONSTANT_All
1316                             ? fillp == untypedFirstIndexByTag[tag]
1317                             : fillp  < untypedFirstIndexByTag[tag]);
1318                     if (cpMap != null) {
1319                         assert(cpMap[fillp] == null);
1320                         assert(cpMap[fillp+ixLen-1] == null);
1321                         System.arraycopy(ix.cpMap, 0, cpMap, fillp, ixLen);
1322                     }
1323                     fillp += ixLen;
1324                 }
1325                 if (cpMap == null) {
1326                     assert(pass == 1);
1327                     // get ready for pass 2
1328                     cpMap = new Entry[fillp];
1329                     fillp = 0;
1330                 }
1331             }
1332             indexByTagGroup[which] = new Index(tagName(tagGroupTag), cpMap);
1333             return indexByTagGroup[which];
1334         }
1335 
1336         public int untypedIndexOf(Entry e) {
1337             if (untypedFirstIndexByTag == null) {
1338                 untypedFirstIndexByTag = new int[CONSTANT_Limit+1];
1339                 int fillp = 0;
1340                 for (int i = 0; i < TAGS_IN_ORDER.length; i++) {
1341                     byte tag = TAGS_IN_ORDER[i];
1342                     Index ix = indexByTag[tag];
1343                     if (ix == null)  continue;
1344                     int ixLen = ix.cpMap.length;
1345                     untypedFirstIndexByTag[tag] = fillp;
1346                     fillp += ixLen;
1347                 }
1348                 untypedFirstIndexByTag[CONSTANT_Limit] = fillp;
1349             }
1350             if (e == null)  return -1;
1351             int tag = e.tag;
1352             Index ix = indexByTag[tag];
1353             if (ix == null)  return -1;
1354             int idx = ix.findIndexOf(e);
1355             if (idx >= 0)
1356                 idx += untypedFirstIndexByTag[tag];
1357             return idx;
1358         }
1359 
1360         public void initIndexByTag(byte tag, Index ix) {
1361             assert(indexByTag[tag] == null);  // do not init twice
1362             Entry[] cpMap = ix.cpMap;
1363             for (int i = 0; i < cpMap.length; i++) {
1364                 // It must be a homogeneous Entry set.
1365                 assert(cpMap[i].tag == tag);
1366             }
1367             if (tag == CONSTANT_Utf8) {
1368                 // Special case:  First Utf8 must always be empty string.
1369                 assert(cpMap.length == 0 || cpMap[0].stringValue().equals(""));
1370             }
1371             indexByTag[tag] = ix;
1372             // decache indexes derived from this one:
1373             untypedFirstIndexByTag = null;
1374             indexByTagGroup = null;
1375             if (indexByTagAndClass != null)
1376                 indexByTagAndClass[tag] = null;
1377         }
1378 
1379         /** Index of all CP entries of a given tag. */
1380         public Index getIndexByTag(byte tag) {
1381             if (tag >= CONSTANT_GroupFirst)
1382                 return getIndexByTagGroup(tag);
1383             Index ix = indexByTag[tag];
1384             if (ix == null) {
1385                 // Make an empty one by default.
1386                 ix = new Index(tagName(tag), new Entry[0]);
1387                 indexByTag[tag] = ix;
1388             }
1389             return ix;
1390         }
1391 
1392         private Index getIndexByTagGroup(byte tag) {
1393             // pool groups:
1394             if (indexByTagGroup != null) {
1395                 Index ix = indexByTagGroup[tag - CONSTANT_GroupFirst];
1396                 if (ix != null)  return ix;
1397             }
1398             switch (tag) {
1399             case CONSTANT_All:
1400                 return makeTagGroupIndex(CONSTANT_All, TAGS_IN_ORDER);
1401             case CONSTANT_LoadableValue:
1402                     return makeTagGroupIndex(CONSTANT_LoadableValue, LOADABLE_VALUE_TAGS);
1403             case CONSTANT_AnyMember:
1404                 return makeTagGroupIndex(CONSTANT_AnyMember, ANY_MEMBER_TAGS);
1405             case CONSTANT_FieldSpecific:
1406                 // This one does not have any fixed index, since it is context-specific.
1407                 return null;
1408             }
1409             throw new AssertionError("bad tag group "+tag);
1410         }
1411 
1412         /** Index of all CP entries of a given tag and class. */
1413         public Index getMemberIndex(byte tag, ClassEntry classRef) {
1414             if (classRef == null)
1415                 throw new RuntimeException("missing class reference for " + tagName(tag));
1416             if (indexByTagAndClass == null)
1417                 indexByTagAndClass = new Index[CONSTANT_Limit][];
1418             Index allClasses =  getIndexByTag(CONSTANT_Class);
1419             Index[] perClassIndexes = indexByTagAndClass[tag];
1420             if (perClassIndexes == null) {
1421                 // Create the partition now.
1422                 // Divide up all entries of the given tag according to their class.
1423                 Index allMembers = getIndexByTag(tag);
1424                 int[] whichClasses = new int[allMembers.size()];
1425                 for (int i = 0; i < whichClasses.length; i++) {
1426                     MemberEntry e = (MemberEntry) allMembers.get(i);
1427                     int whichClass = allClasses.indexOf(e.classRef);
1428                     whichClasses[i] = whichClass;
1429                 }
1430                 perClassIndexes = partition(allMembers, whichClasses);
1431                 for (int i = 0; i < perClassIndexes.length; i++) {
1432                     assert (perClassIndexes[i] == null ||
1433                             perClassIndexes[i].assertIsSorted());
1434                 }
1435                 indexByTagAndClass[tag] = perClassIndexes;
1436             }
1437             int whichClass = allClasses.indexOf(classRef);
1438             return perClassIndexes[whichClass];
1439         }
1440 
1441         // Given the sequence of all methods of the given name and class,
1442         // produce the ordinal of this particular given overloading.
1443         public int getOverloadingIndex(MemberEntry methodRef) {
1444             Index ix = getMemberIndex(methodRef.tag, methodRef.classRef);
1445             Utf8Entry nameRef = methodRef.descRef.nameRef;
1446             int ord = 0;
1447             for (int i = 0; i < ix.cpMap.length; i++) {
1448                 MemberEntry e = (MemberEntry) ix.cpMap[i];
1449                 if (e.equals(methodRef))
1450                     return ord;
1451                 if (e.descRef.nameRef.equals(nameRef))
1452                     // Found a different overloading.  Increment the ordinal.
1453                     ord++;
1454             }
1455             throw new RuntimeException("should not reach here");
1456         }
1457 
1458         // Inverse of getOverloadingIndex
1459         public MemberEntry getOverloadingForIndex(byte tag, ClassEntry classRef, String name, int which) {
1460             assert(name.equals(name.intern()));
1461             Index ix = getMemberIndex(tag, classRef);
1462             int ord = 0;
1463             for (int i = 0; i < ix.cpMap.length; i++) {
1464                 MemberEntry e = (MemberEntry) ix.cpMap[i];
1465                 if (e.descRef.nameRef.stringValue().equals(name)) {
1466                     if (ord == which)  return e;
1467                     ord++;
1468                 }
1469             }
1470             throw new RuntimeException("should not reach here");
1471         }
1472 
1473         public boolean haveNumbers() {
1474             for (byte tag : NUMBER_TAGS) {
1475                 if (getIndexByTag(tag).size() > 0)  return true;
1476             }
1477             return false;
1478         }
1479 
1480         public boolean haveExtraTags() {
1481             for (byte tag : EXTRA_TAGS) {
1482                 if (getIndexByTag(tag).size() > 0)  return true;
1483             }
1484             return false;
1485         }
1486 
1487     }
1488 
1489     /** Close the set cpRefs under the getRef(*) relation.
1490      *  Also, if flattenSigs, replace all signatures in cpRefs
1491      *  by their equivalent Utf8s.
1492      *  Also, discard null from cpRefs.
1493      */
1494     public static void completeReferencesIn(Set<Entry> cpRefs, boolean flattenSigs) {
1495          completeReferencesIn(cpRefs, flattenSigs, null);
1496     }
1497 
1498     public static
1499     void completeReferencesIn(Set<Entry> cpRefs, boolean flattenSigs,
1500                               List<BootstrapMethodEntry>bsms) {
1501         cpRefs.remove(null);
1502         for (ListIterator<Entry> work =
1503                  new ArrayList<>(cpRefs).listIterator(cpRefs.size());
1504              work.hasPrevious(); ) {
1505             Entry e = work.previous();
1506             work.remove();          // pop stack
1507             assert(e != null);
1508             if (flattenSigs && e.tag == CONSTANT_Signature) {
1509                 SignatureEntry se = (SignatureEntry) e;
1510                 Utf8Entry      ue = se.asUtf8Entry();
1511                 // Totally replace e by se.
1512                 cpRefs.remove(se);
1513                 cpRefs.add(ue);
1514                 e = ue;   // do not descend into the sig
1515             }
1516             if (bsms != null && e.tag == CONSTANT_BootstrapMethod) {
1517                 BootstrapMethodEntry bsm = (BootstrapMethodEntry)e;
1518                 cpRefs.remove(bsm);
1519                 // move it away to the side table where it belongs
1520                 if (!bsms.contains(bsm))
1521                     bsms.add(bsm);
1522                 // fall through to recursively add refs for this entry
1523             }
1524             // Recursively add the refs of e to cpRefs:
1525             for (int i = 0; ; i++) {
1526                 Entry re = e.getRef(i);
1527                 if (re == null)
1528                     break;          // no more refs in e
1529                 if (cpRefs.add(re)) // output the ref
1530                     work.add(re);   // push stack, if a new ref
1531             }
1532         }
1533     }
1534 
1535     static double percent(int num, int den) {
1536         return (int)((10000.0*num)/den + 0.5) / 100.0;
1537     }
1538 
1539     public static String tagName(int tag) {
1540         switch (tag) {
1541             case CONSTANT_Utf8:                 return "Utf8";
1542             case CONSTANT_Integer:              return "Integer";
1543             case CONSTANT_Float:                return "Float";
1544             case CONSTANT_Long:                 return "Long";
1545             case CONSTANT_Double:               return "Double";
1546             case CONSTANT_Class:                return "Class";
1547             case CONSTANT_String:               return "String";
1548             case CONSTANT_Fieldref:             return "Fieldref";
1549             case CONSTANT_Methodref:            return "Methodref";
1550             case CONSTANT_InterfaceMethodref:   return "InterfaceMethodref";
1551             case CONSTANT_NameandType:          return "NameandType";
1552             case CONSTANT_MethodHandle:         return "MethodHandle";
1553             case CONSTANT_MethodType:           return "MethodType";
1554             case CONSTANT_InvokeDynamic:        return "InvokeDynamic";
1555 
1556                 // pseudo-tags:
1557             case CONSTANT_All:                  return "**All";
1558             case CONSTANT_None:                 return "**None";
1559             case CONSTANT_LoadableValue:        return "**LoadableValue";
1560             case CONSTANT_AnyMember:            return "**AnyMember";
1561             case CONSTANT_FieldSpecific:        return "*FieldSpecific";
1562             case CONSTANT_Signature:            return "*Signature";
1563             case CONSTANT_BootstrapMethod:      return "*BootstrapMethod";
1564         }
1565         return "tag#"+tag;
1566     }
1567 
1568     public static String refKindName(int refKind) {
1569         switch (refKind) {
1570             case REF_getField:                  return "getField";
1571             case REF_getStatic:                 return "getStatic";
1572             case REF_putField:                  return "putField";
1573             case REF_putStatic:                 return "putStatic";
1574             case REF_invokeVirtual:             return "invokeVirtual";
1575             case REF_invokeStatic:              return "invokeStatic";
1576             case REF_invokeSpecial:             return "invokeSpecial";
1577             case REF_newInvokeSpecial:          return "newInvokeSpecial";
1578             case REF_invokeInterface:           return "invokeInterface";
1579         }
1580         return "refKind#"+refKind;
1581     }
1582 
1583     // archive constant pool definition order
1584     static final byte TAGS_IN_ORDER[] = {
1585         CONSTANT_Utf8,
1586         CONSTANT_Integer,           // cp_Int
1587         CONSTANT_Float,
1588         CONSTANT_Long,
1589         CONSTANT_Double,
1590         CONSTANT_String,            // note that String=8 precedes Class=7
1591         CONSTANT_Class,
1592         CONSTANT_Signature,
1593         CONSTANT_NameandType,       // cp_Descr
1594         CONSTANT_Fieldref,          // cp_Field
1595         CONSTANT_Methodref,         // cp_Method
1596         CONSTANT_InterfaceMethodref, // cp_Imethod
1597 
1598         // Constants defined in JDK 7 and later:
1599         CONSTANT_MethodHandle,
1600         CONSTANT_MethodType,
1601         CONSTANT_BootstrapMethod,  // pseudo-tag, really stored in a class attribute
1602         CONSTANT_InvokeDynamic
1603     };
1604     static final byte TAG_ORDER[];
1605     static {
1606         TAG_ORDER = new byte[CONSTANT_Limit];
1607         for (int i = 0; i < TAGS_IN_ORDER.length; i++) {
1608             TAG_ORDER[TAGS_IN_ORDER[i]] = (byte)(i+1);
1609         }
1610         /*
1611         System.out.println("TAG_ORDER[] = {");
1612         for (int i = 0; i < TAG_ORDER.length; i++)
1613             System.out.println("  "+TAG_ORDER[i]+",");
1614         System.out.println("};");
1615         */
1616     }
1617     static final byte[] NUMBER_TAGS = {
1618         CONSTANT_Integer, CONSTANT_Float, CONSTANT_Long, CONSTANT_Double
1619     };
1620     static final byte[] EXTRA_TAGS = {
1621         CONSTANT_MethodHandle, CONSTANT_MethodType,
1622         CONSTANT_BootstrapMethod, // pseudo-tag
1623         CONSTANT_InvokeDynamic
1624     };
1625     static final byte[] LOADABLE_VALUE_TAGS = { // for CONSTANT_LoadableValue
1626         CONSTANT_Integer, CONSTANT_Float, CONSTANT_Long, CONSTANT_Double,
1627         CONSTANT_String, CONSTANT_Class,
1628         CONSTANT_MethodHandle, CONSTANT_MethodType
1629     };
1630     static final byte[] ANY_MEMBER_TAGS = { // for CONSTANT_AnyMember
1631         CONSTANT_Fieldref, CONSTANT_Methodref, CONSTANT_InterfaceMethodref
1632     };
1633     static final byte[] FIELD_SPECIFIC_TAGS = { // for CONSTANT_FieldSpecific
1634         CONSTANT_Integer, CONSTANT_Float, CONSTANT_Long, CONSTANT_Double,
1635         CONSTANT_String
1636     };
1637     static {
1638         assert(
1639             verifyTagOrder(TAGS_IN_ORDER) &&
1640             verifyTagOrder(NUMBER_TAGS) &&
1641             verifyTagOrder(EXTRA_TAGS) &&
1642             verifyTagOrder(LOADABLE_VALUE_TAGS) &&
1643             verifyTagOrder(ANY_MEMBER_TAGS) &&
1644             verifyTagOrder(FIELD_SPECIFIC_TAGS)
1645         );
1646     }
1647     private static boolean verifyTagOrder(byte[] tags) {
1648         int prev = -1;
1649         for (byte tag : tags) {
1650             int next = TAG_ORDER[tag];
1651             assert(next > 0) : "tag not found: "+tag;
1652             assert(TAGS_IN_ORDER[next-1] == tag) : "tag repeated: "+tag+" => "+next+" => "+TAGS_IN_ORDER[next-1];
1653             assert(prev < next) : "tags not in order: "+Arrays.toString(tags)+" at "+tag;
1654             prev = next;
1655         }
1656         return true;
1657     }
1658 }