1 /*
2 * Copyright (c) 2001, 2010, 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.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 synchronized ClassEntry getClassEntry(String name) {
65 Map<String, ClassEntry> classEntries = Utils.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 synchronized LiteralEntry getLiteralEntry(Comparable value) {
76 Map<Object, LiteralEntry> literalEntries = Utils.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 synchronized StringEntry getStringEntry(String value) {
89 return (StringEntry) getLiteralEntry(value);
90 }
91
92 /** Factory for signature (type) constants. */
93 public static synchronized SignatureEntry getSignatureEntry(String type) {
94 Map<String, SignatureEntry> signatureEntries = Utils.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 synchronized DescriptorEntry getDescriptorEntry(Utf8Entry nameRef, SignatureEntry typeRef) {
110 Map<String, DescriptorEntry> descriptorEntries = Utils.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 synchronized MemberEntry getMemberEntry(byte tag, ClassEntry classRef, DescriptorEntry descRef) {
128 Map<String, MemberEntry> memberEntries = Utils.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
141 /** Entries in the constant pool. */
142 public static abstract
143 class Entry implements Comparable {
144 protected final byte tag; // a CONSTANT_foo code
145 protected int valueHash; // cached hashCode
146
147 protected Entry(byte tag) {
148 this.tag = tag;
149 }
150
151 public final byte getTag() {
152 return tag;
153 }
154
155 public Entry getRef(int i) {
156 return null;
157 }
158
159 public boolean eq(Entry that) { // same reference
160 assert(that != null);
161 return this == that || this.equals(that);
162 }
163
164 // Equality of Entries is value-based.
165 public abstract boolean equals(Object o);
166 public final int hashCode() {
167 if (valueHash == 0) {
168 valueHash = computeValueHash();
169 if (valueHash == 0) valueHash = 1;
170 }
171 return valueHash;
172 }
173 protected abstract int computeValueHash();
174
175 public abstract int compareTo(Object o);
176
177 protected int superCompareTo(Object o) {
178 Entry that = (Entry) o;
179
180 if (this.tag != that.tag) {
181 return TAG_ORDER[this.tag] - TAG_ORDER[that.tag];
182 }
183
184 return 0; // subclasses must refine this
185 }
186
187 public final boolean isDoubleWord() {
188 return tag == CONSTANT_Double || tag == CONSTANT_Long;
189 }
190
191 public final boolean tagMatches(int tag) {
192 return (this.tag == tag);
193 }
194
195 public String toString() {
196 String valuePrint = stringValue();
197 if (verbose() > 4) {
198 if (valueHash != 0)
199 valuePrint += " hash="+valueHash;
200 valuePrint += " id="+System.identityHashCode(this);
201 }
202 return tagName(tag)+"="+valuePrint;
203 }
204 public abstract String stringValue();
205 }
206
207 public static
208 class Utf8Entry extends Entry {
209 final String value;
210
211 Utf8Entry(String value) {
212 super(CONSTANT_Utf8);
213 this.value = value.intern();
214 hashCode(); // force computation of valueHash
215 }
216 protected int computeValueHash() {
217 return value.hashCode();
218 }
219 public boolean equals(Object o) {
220 // Use reference equality of interned strings:
221 return (o != null && o.getClass() == Utf8Entry.class
222 && ((Utf8Entry) o).value.equals(value));
223 }
224 public int compareTo(Object o) {
225 int x = superCompareTo(o);
226 if (x == 0) {
227 x = value.compareTo(((Utf8Entry)o).value);
228 }
229 return x;
230 }
231 public String stringValue() {
232 return value;
233 }
234 }
235
236 static boolean isMemberTag(byte tag) {
237 switch (tag) {
238 case CONSTANT_Fieldref:
239 case CONSTANT_Methodref:
240 case CONSTANT_InterfaceMethodref:
241 return true;
242 }
243 return false;
244 }
245
246 static byte numberTagOf(Number value) {
247 if (value instanceof Integer) return CONSTANT_Integer;
248 if (value instanceof Float) return CONSTANT_Float;
249 if (value instanceof Long) return CONSTANT_Long;
250 if (value instanceof Double) return CONSTANT_Double;
251 throw new RuntimeException("bad literal value "+value);
252 }
253
254 public static abstract
255 class LiteralEntry extends Entry {
256 protected LiteralEntry(byte tag) {
257 super(tag);
258 }
259
260 public abstract Comparable literalValue();
261 }
262
263 public static
264 class NumberEntry extends LiteralEntry {
265 final Number value;
266 NumberEntry(Number value) {
267 super(numberTagOf(value));
268 this.value = value;
269 hashCode(); // force computation of valueHash
270 }
271 protected int computeValueHash() {
272 return value.hashCode();
273 }
274
275 public boolean equals(Object o) {
276 return (o != null && o.getClass() == NumberEntry.class
277 && ((NumberEntry) o).value.equals(value));
278
279 }
280 public int compareTo(Object o) {
281 int x = superCompareTo(o);
282 if (x == 0) {
283 x = ((Comparable)value).compareTo(((NumberEntry)o).value);
284 }
285 return x;
286 }
287 public Number numberValue() {
288 return value;
289 }
290 public Comparable literalValue() {
291 return (Comparable) value;
292 }
293 public String stringValue() {
294 return value.toString();
295 }
296 }
297
298 public static
299 class StringEntry extends LiteralEntry {
300 final Utf8Entry ref;
301 public Entry getRef(int i) { return i == 0 ? ref : null; }
302
303 StringEntry(Entry ref) {
304 super(CONSTANT_String);
305 this.ref = (Utf8Entry) ref;
306 hashCode(); // force computation of valueHash
307 }
308 protected int computeValueHash() {
309 return ref.hashCode() + tag;
310 }
311 public boolean equals(Object o) {
312 return (o != null && o.getClass() == StringEntry.class &&
313 ((StringEntry)o).ref.eq(ref));
314 }
315 public int compareTo(Object o) {
316 int x = superCompareTo(o);
317 if (x == 0) {
318 x = ref.compareTo(((StringEntry)o).ref);
319 }
320 return x;
321 }
322 public Comparable literalValue() {
323 return ref.stringValue();
324 }
325 public String stringValue() {
326 return ref.stringValue();
327 }
328 }
329
330 public static
331 class ClassEntry extends Entry {
332 final Utf8Entry ref;
333 public Entry getRef(int i) { return i == 0 ? ref : null; }
334
335 protected int computeValueHash() {
336 return ref.hashCode() + tag;
337 }
338 ClassEntry(Entry ref) {
339 super(CONSTANT_Class);
340 this.ref = (Utf8Entry) ref;
341 hashCode(); // force computation of valueHash
342 }
343 public boolean equals(Object o) {
344 return (o != null && o.getClass() == ClassEntry.class
345 && ((ClassEntry) o).ref.eq(ref));
346 }
347 public int compareTo(Object o) {
348 int x = superCompareTo(o);
349 if (x == 0) {
350 x = ref.compareTo(((ClassEntry)o).ref);
351 }
352 return x;
353 }
354 public String stringValue() {
355 return ref.stringValue();
356 }
357 }
358
359 public static
360 class DescriptorEntry extends Entry {
361 final Utf8Entry nameRef;
362 final SignatureEntry typeRef;
363 public Entry getRef(int i) {
364 if (i == 0) return nameRef;
365 if (i == 1) return typeRef;
366 return null;
367 }
368 DescriptorEntry(Entry nameRef, Entry typeRef) {
369 super(CONSTANT_NameandType);
370 if (typeRef instanceof Utf8Entry) {
371 typeRef = getSignatureEntry(typeRef.stringValue());
372 }
373 this.nameRef = (Utf8Entry) nameRef;
374 this.typeRef = (SignatureEntry) typeRef;
375 hashCode(); // force computation of valueHash
376 }
377 protected int computeValueHash() {
378 int hc2 = typeRef.hashCode();
379 return (nameRef.hashCode() + (hc2 << 8)) ^ hc2;
380 }
381 public boolean equals(Object o) {
382 if (o == null || o.getClass() != DescriptorEntry.class) {
383 return false;
384 }
385 DescriptorEntry that = (DescriptorEntry)o;
386 return this.nameRef.eq(that.nameRef)
387 && this.typeRef.eq(that.typeRef);
388 }
389 public int compareTo(Object o) {
390 int x = superCompareTo(o);
391 if (x == 0) {
392 DescriptorEntry that = (DescriptorEntry)o;
393 // Primary key is typeRef, not nameRef.
394 x = this.typeRef.compareTo(that.typeRef);
395 if (x == 0)
396 x = this.nameRef.compareTo(that.nameRef);
397 }
398 return x;
399 }
400 public String stringValue() {
401 return stringValueOf(nameRef, typeRef);
402 }
403 static
404 String stringValueOf(Entry nameRef, Entry typeRef) {
405 return typeRef.stringValue()+","+nameRef.stringValue();
406 }
407
408 public String prettyString() {
409 return nameRef.stringValue()+typeRef.prettyString();
410 }
411
412 public boolean isMethod() {
413 return typeRef.isMethod();
414 }
415
416 public byte getLiteralTag() {
417 return typeRef.getLiteralTag();
418 }
419 }
420
421 public static
422 class MemberEntry extends Entry {
423 final ClassEntry classRef;
424 final DescriptorEntry descRef;
425 public Entry getRef(int i) {
426 if (i == 0) return classRef;
427 if (i == 1) return descRef;
428 return null;
429 }
430 protected int computeValueHash() {
431 int hc2 = descRef.hashCode();
432 return (classRef.hashCode() + (hc2 << 8)) ^ hc2;
433 }
434
435 MemberEntry(byte tag, ClassEntry classRef, DescriptorEntry descRef) {
436 super(tag);
437 assert(isMemberTag(tag));
438 this.classRef = classRef;
439 this.descRef = descRef;
440 hashCode(); // force computation of valueHash
441 }
442 public boolean equals(Object o) {
443 if (o == null || o.getClass() != MemberEntry.class) {
444 return false;
445 }
446 MemberEntry that = (MemberEntry)o;
447 return this.classRef.eq(that.classRef)
448 && this.descRef.eq(that.descRef);
449 }
450 public int compareTo(Object o) {
451 int x = superCompareTo(o);
452 if (x == 0) {
453 MemberEntry that = (MemberEntry)o;
454 // Primary key is classRef.
455 x = this.classRef.compareTo(that.classRef);
456 if (x == 0)
457 x = this.descRef.compareTo(that.descRef);
458 }
459 return x;
460 }
461 public String stringValue() {
462 return stringValueOf(tag, classRef, descRef);
463 }
464 static
465 String stringValueOf(byte tag, ClassEntry classRef, DescriptorEntry descRef) {
466 assert(isMemberTag(tag));
467 String pfx;
468 switch (tag) {
469 case CONSTANT_Fieldref: pfx = "Field:"; break;
470 case CONSTANT_Methodref: pfx = "Method:"; break;
471 case CONSTANT_InterfaceMethodref: pfx = "IMethod:"; break;
472 default: pfx = tag+"???"; break;
473 }
474 return pfx+classRef.stringValue()+","+descRef.stringValue();
475 }
476
477 public boolean isMethod() {
478 return descRef.isMethod();
479 }
480 }
481
482 public static
483 class SignatureEntry extends Entry {
484 final Utf8Entry formRef;
485 final ClassEntry[] classRefs;
486 String value;
487 Utf8Entry asUtf8Entry;
488 public Entry getRef(int i) {
489 if (i == 0) return formRef;
490 return i-1 < classRefs.length ? classRefs[i-1] : null;
491 }
492 SignatureEntry(String value) {
493 super(CONSTANT_Signature);
494 value = value.intern(); // always do this
495 this.value = value;
496 String[] parts = structureSignature(value);
497 formRef = getUtf8Entry(parts[0]);
498 classRefs = new ClassEntry[parts.length-1];
499 for (int i = 1; i < parts.length; i++) {
500 classRefs[i - 1] = getClassEntry(parts[i]);
501 }
502 hashCode(); // force computation of valueHash
503 }
504 protected int computeValueHash() {
505 stringValue(); // force computation of value
506 return value.hashCode() + tag;
507 }
508
509 public Utf8Entry asUtf8Entry() {
510 if (asUtf8Entry == null) {
511 asUtf8Entry = getUtf8Entry(stringValue());
512 }
513 return asUtf8Entry;
514 }
515
516 public boolean equals(Object o) {
517 return (o != null && o.getClass() == SignatureEntry.class &&
518 ((SignatureEntry)o).value.equals(value));
519 }
520 public int compareTo(Object o) {
521 int x = superCompareTo(o);
522 if (x == 0) {
523 SignatureEntry that = (SignatureEntry)o;
524 x = compareSignatures(this.value, that.value);
525 }
526 return x;
527 }
528 public String stringValue() {
529 if (value == null) {
530 value = stringValueOf(formRef, classRefs);
531 }
532 return value;
533 }
534 static
535 String stringValueOf(Utf8Entry formRef, ClassEntry[] classRefs) {
536 String[] parts = new String[1+classRefs.length];
537 parts[0] = formRef.stringValue();
538 for (int i = 1; i < parts.length; i++) {
539 parts[i] = classRefs[i - 1].stringValue();
540 }
541 return flattenSignature(parts).intern();
542 }
543
544 public int computeSize(boolean countDoublesTwice) {
545 String form = formRef.stringValue();
546 int min = 0;
547 int max = 1;
548 if (isMethod()) {
549 min = 1;
550 max = form.indexOf(')');
551 }
552 int size = 0;
553 for (int i = min; i < max; i++) {
554 switch (form.charAt(i)) {
555 case 'D':
556 case 'J':
557 if (countDoublesTwice) {
558 size++;
559 }
560 break;
561 case '[':
562 // Skip rest of array info.
563 while (form.charAt(i) == '[') {
564 ++i;
565 }
566 break;
567 case ';':
568 continue;
569 default:
570 assert (0 <= JAVA_SIGNATURE_CHARS.indexOf(form.charAt(i)));
571 break;
572 }
573 size++;
574 }
575 return size;
576 }
577 public boolean isMethod() {
578 return formRef.stringValue().charAt(0) == '(';
579 }
580 public byte getLiteralTag() {
581 switch (formRef.stringValue().charAt(0)) {
582 case 'L': return CONSTANT_String;
583 case 'I': return CONSTANT_Integer;
584 case 'J': return CONSTANT_Long;
585 case 'F': return CONSTANT_Float;
586 case 'D': return CONSTANT_Double;
587 case 'B': case 'S': case 'C': case 'Z':
588 return CONSTANT_Integer;
589 }
590 assert(false);
591 return CONSTANT_None;
592 }
593 public String prettyString() {
594 String s;
595 if (isMethod()) {
596 s = formRef.stringValue();
597 s = s.substring(0, 1+s.indexOf(')'));
598 } else {
599 s = "/" + formRef.stringValue();
600 }
601 int i;
602 while ((i = s.indexOf(';')) >= 0) {
603 s = s.substring(0, i) + s.substring(i + 1);
604 }
605 return s;
606 }
607 }
608
609 static int compareSignatures(String s1, String s2) {
610 return compareSignatures(s1, s2, null, null);
611 }
612 static int compareSignatures(String s1, String s2, String[] p1, String[] p2) {
613 final int S1_COMES_FIRST = -1;
614 final int S2_COMES_FIRST = +1;
615 char c1 = s1.charAt(0);
616 char c2 = s2.charAt(0);
617 // fields before methods (because there are fewer of them)
618 if (c1 != '(' && c2 == '(') return S1_COMES_FIRST;
619 if (c2 != '(' && c1 == '(') return S2_COMES_FIRST;
620 if (p1 == null) p1 = structureSignature(s1);
621 if (p2 == null) p2 = structureSignature(s2);
622 /*
623 // non-classes before classes (because there are fewer of them)
624 if (p1.length == 1 && p2.length > 1) return S1_COMES_FIRST;
625 if (p2.length == 1 && p1.length > 1) return S2_COMES_FIRST;
626 // all else being equal, use the same comparison as for Utf8 strings
627 return s1.compareTo(s2);
628 */
629 if (p1.length != p2.length) return p1.length - p2.length;
630 int length = p1.length;
631 for (int i = length; --i >= 0; ) {
632 int res = p1[i].compareTo(p2[i]);
633 if (res != 0) return res;
634 }
635 assert(s1.equals(s2));
636 return 0;
637 }
638
639 static int countClassParts(Utf8Entry formRef) {
640 int num = 0;
641 String s = formRef.stringValue();
642 for (int i = 0; i < s.length(); i++) {
643 if (s.charAt(i) == 'L') ++num;
644 }
645 return num;
646 }
647
648 static String flattenSignature(String[] parts) {
649 String form = parts[0];
650 if (parts.length == 1) return form;
651 int len = form.length();
652 for (int i = 1; i < parts.length; i++) {
653 len += parts[i].length();
654 }
655 char[] sig = new char[len];
656 int j = 0;
657 int k = 1;
658 for (int i = 0; i < form.length(); i++) {
659 char ch = form.charAt(i);
660 sig[j++] = ch;
661 if (ch == 'L') {
662 String cls = parts[k++];
663 cls.getChars(0, cls.length(), sig, j);
664 j += cls.length();
665 //sig[j++] = ';';
666 }
667 }
668 assert(j == len);
669 assert(k == parts.length);
670 return new String(sig);
671 }
672
673 static private int skipClassNameChars(String sig, int i) {
674 int len = sig.length();
675 for (; i < len; i++) {
676 char ch = sig.charAt(i);
677 if (ch <= ' ') break;
678 if (ch >= ';' && ch <= '@') break;
679 }
680 return i;
681 }
682
683 static String[] structureSignature(String sig) {
684 sig = sig.intern();
685
686 int formLen = 0;
687 int nparts = 1;
688 for (int i = 0; i < sig.length(); i++) {
689 char ch = sig.charAt(i);
690 formLen++;
691 if (ch == 'L') {
692 nparts++;
693 int i2 = skipClassNameChars(sig, i+1);
694 i = i2-1; // keep the semicolon in the form
695 int i3 = sig.indexOf('<', i+1);
696 if (i3 > 0 && i3 < i2)
697 i = i3-1;
698 }
699 }
700 char[] form = new char[formLen];
701 if (nparts == 1) {
702 String[] parts = { sig };
703 return parts;
704 }
705 String[] parts = new String[nparts];
706 int j = 0;
707 int k = 1;
708 for (int i = 0; i < sig.length(); i++) {
709 char ch = sig.charAt(i);
710 form[j++] = ch;
711 if (ch == 'L') {
712 int i2 = skipClassNameChars(sig, i+1);
713 parts[k++] = sig.substring(i+1, i2);
714 i = i2;
715 --i; // keep the semicolon in the form
716 }
717 }
718 assert(j == formLen);
719 assert(k == parts.length);
720 parts[0] = new String(form);
721 //assert(flattenSignature(parts).equals(sig));
722 return parts;
723 }
724
725 // Handy constants:
726 protected static final Entry[] noRefs = {};
727 protected static final ClassEntry[] noClassRefs = {};
728
729 /** An Index is a mapping between CP entries and small integers. */
730 public static final
731 class Index extends AbstractList {
732 protected String debugName;
733 protected Entry[] cpMap;
734 protected boolean flattenSigs;
735 protected Entry[] getMap() {
736 return cpMap;
737 }
738 protected Index(String debugName) {
739 this.debugName = debugName;
740 }
741 protected Index(String debugName, Entry[] cpMap) {
742 this(debugName);
743 setMap(cpMap);
744 }
745 protected void setMap(Entry[] cpMap) {
746 clearIndex();
747 this.cpMap = cpMap;
748 }
749 protected Index(String debugName, Collection<Entry> cpMapList) {
750 this(debugName);
751 setMap(cpMapList);
752 }
753 protected void setMap(Collection<Entry> cpMapList) {
754 cpMap = new Entry[cpMapList.size()];
755 cpMapList.toArray(cpMap);
756 setMap(cpMap);
757 }
758 public int size() {
759 return cpMap.length;
760 }
761 public Object get(int i) {
762 return cpMap[i];
763 }
764 public Entry getEntry(int i) {
765 // same as get(), with covariant return type
766 return cpMap[i];
767 }
768
769 // Find index of e in cpMap, or return -1 if none.
770 //
771 // As a special hack, if flattenSigs, signatures are
772 // treated as equivalent entries of cpMap. This is wrong
773 // from a Collection point of view, because contains()
774 // reports true for signatures, but the iterator()
775 // never produces them!
776 private int findIndexOf(Entry e) {
777 if (indexKey == null) {
778 initializeIndex();
779 }
780 int probe = findIndexLocation(e);
781 if (indexKey[probe] != e) {
782 if (flattenSigs && e.tag == CONSTANT_Signature) {
783 SignatureEntry se = (SignatureEntry) e;
784 return findIndexOf(se.asUtf8Entry());
785 }
786 return -1;
787 }
788 int index = indexValue[probe];
789 assert(e.equals(cpMap[index]));
790 return index;
791 }
792 public boolean contains(Entry e) {
793 return findIndexOf(e) >= 0;
794 }
795 // Find index of e in cpMap. Should not return -1.
796 public int indexOf(Entry e) {
797 int index = findIndexOf(e);
798 if (index < 0 && verbose() > 0) {
799 System.out.println("not found: "+e);
800 System.out.println(" in: "+this.dumpString());
801 Thread.dumpStack();
802 }
803 assert(index >= 0);
804 return index;
805 }
806 public boolean contains(Object e) {
807 return findIndexOf((Entry)e) >= 0;
808 }
809 public int indexOf(Object e) {
810 return findIndexOf((Entry)e);
811 }
812 public int lastIndexOf(Object e) {
813 return indexOf(e);
814 }
815
816 public boolean assertIsSorted() {
817 for (int i = 1; i < cpMap.length; i++) {
818 if (cpMap[i-1].compareTo(cpMap[i]) > 0) {
819 System.out.println("Not sorted at "+(i-1)+"/"+i+": "+this.dumpString());
820 return false;
821 }
822 }
823 return true;
824 }
825
826 // internal hash table
827 protected Entry[] indexKey;
828 protected int[] indexValue;
829 protected void clearIndex() {
830 indexKey = null;
831 indexValue = null;
832 }
833 private int findIndexLocation(Entry e) {
834 int size = indexKey.length;
835 int hash = e.hashCode();
836 int probe = hash & (size - 1);
837 int stride = ((hash >>> 8) | 1) & (size - 1);
838 for (;;) {
839 Entry e1 = indexKey[probe];
840 if (e1 == e || e1 == null)
841 return probe;
842 probe += stride;
843 if (probe >= size) probe -= size;
844 }
845 }
846 private void initializeIndex() {
847 if (verbose() > 2)
848 System.out.println("initialize Index "+debugName+" ["+size()+"]");
849 int hsize0 = (int)((cpMap.length + 10) * 1.5);
850 int hsize = 1;
851 while (hsize < hsize0) {
852 hsize <<= 1;
853 }
854 indexKey = new Entry[hsize];
855 indexValue = new int[hsize];
856 for (int i = 0; i < cpMap.length; i++) {
857 Entry e = cpMap[i];
858 if (e == null) continue;
859 int probe = findIndexLocation(e);
860 assert(indexKey[probe] == null); // e has unique index
861 indexKey[probe] = e;
862 indexValue[probe] = i;
863 }
864 }
865 public Object[] toArray(Object[] a) {
866 int sz = size();
867 if (a.length < sz) return super.toArray(a);
868 System.arraycopy(cpMap, 0, a, 0, sz);
869 if (a.length > sz) a[sz] = null;
870 return a;
871 }
872 public Object[] toArray() {
873 return toArray(new Entry[size()]);
874 }
875 public Object clone() {
876 return new Index(debugName, cpMap.clone());
877 }
878 public String toString() {
879 return "Index "+debugName+" ["+size()+"]";
880 }
881 public String dumpString() {
882 String s = toString();
883 s += " {\n";
884 for (int i = 0; i < cpMap.length; i++) {
885 s += " "+i+": "+cpMap[i]+"\n";
886 }
887 s += "}";
888 return s;
889 }
890 }
891
892 // Index methods.
893
894 public static
895 Index makeIndex(String debugName, Entry[] cpMap) {
896 return new Index(debugName, cpMap);
897 }
898
899 public static
900 Index makeIndex(String debugName, Collection<Entry> cpMapList) {
901 return new Index(debugName, cpMapList);
902 }
903
904 /** Sort this index (destructively) into canonical order. */
905 public static
906 void sort(Index ix) {
907 // %%% Should move this into class Index.
908 ix.clearIndex();
909 Arrays.sort(ix.cpMap);
910 if (verbose() > 2)
911 System.out.println("sorted "+ix.dumpString());
912 }
913
914 /** Return a set of indexes partitioning these entries.
915 * The keys array must of length this.size(), and marks entries.
916 * The result array is as long as one plus the largest key value.
917 * Entries with a negative key are dropped from the partition.
918 */
919 public static
920 Index[] partition(Index ix, int[] keys) {
921 // %%% Should move this into class Index.
922 List<List<Entry>> parts = new ArrayList<>();
923 Entry[] cpMap = ix.cpMap;
924 assert(keys.length == cpMap.length);
925 for (int i = 0; i < keys.length; i++) {
926 int key = keys[i];
927 if (key < 0) continue;
928 while (key >= parts.size()) {
929 parts.add(null);
930 }
931 List<Entry> part = parts.get(key);
932 if (part == null) {
933 parts.set(key, part = new ArrayList<>());
934 }
935 part.add(cpMap[i]);
936 }
937 Index[] indexes = new Index[parts.size()];
938 for (int key = 0; key < indexes.length; key++) {
939 List<Entry> part = parts.get(key);
940 if (part == null) continue;
941 indexes[key] = new Index(ix.debugName+"/part#"+key, part);
942 assert(indexes[key].indexOf(part.get(0)) == 0);
943 }
944 return indexes;
945 }
946 public static
947 Index[] partitionByTag(Index ix) {
948 // Partition by tag.
949 Entry[] cpMap = ix.cpMap;
950 int[] keys = new int[cpMap.length];
951 for (int i = 0; i < keys.length; i++) {
952 Entry e = cpMap[i];
953 keys[i] = (e == null)? -1: e.tag;
954 }
955 Index[] byTag = partition(ix, keys);
956 for (int tag = 0; tag < byTag.length; tag++) {
957 if (byTag[tag] == null) continue;
958 byTag[tag].debugName = tagName(tag);
959 }
960 if (byTag.length < CONSTANT_Limit) {
961 Index[] longer = new Index[CONSTANT_Limit];
962 System.arraycopy(byTag, 0, longer, 0, byTag.length);
963 byTag = longer;
964 }
965 return byTag;
966 }
967
968 /** Coherent group of constant pool indexes. */
969 public static
970 class IndexGroup {
971 private Index indexUntyped;
972 private Index[] indexByTag = new Index[CONSTANT_Limit];
973 private int[] untypedFirstIndexByTag;
974 private int totalSize;
975 private Index[][] indexByTagAndClass;
976
977 /** Index of all CP entries of all types, in definition order. */
978 public Index getUntypedIndex() {
979 if (indexUntyped == null) {
980 untypedIndexOf(null); // warm up untypedFirstIndexByTag
981 Entry[] cpMap = new Entry[totalSize];
982 for (int tag = 0; tag < indexByTag.length; tag++) {
983 Index ix = indexByTag[tag];
984 if (ix == null) continue;
985 int ixLen = ix.cpMap.length;
986 if (ixLen == 0) continue;
987 int fillp = untypedFirstIndexByTag[tag];
988 assert(cpMap[fillp] == null);
989 assert(cpMap[fillp+ixLen-1] == null);
990 System.arraycopy(ix.cpMap, 0, cpMap, fillp, ixLen);
991 }
992 indexUntyped = new Index("untyped", cpMap);
993 }
994 return indexUntyped;
995 }
996
997 public int untypedIndexOf(Entry e) {
998 if (untypedFirstIndexByTag == null) {
999 untypedFirstIndexByTag = new int[CONSTANT_Limit];
1000 int fillp = 0;
1001 for (int i = 0; i < TAGS_IN_ORDER.length; i++) {
1002 byte tag = TAGS_IN_ORDER[i];
1003 Index ix = indexByTag[tag];
1004 if (ix == null) continue;
1005 int ixLen = ix.cpMap.length;
1006 untypedFirstIndexByTag[tag] = fillp;
1007 fillp += ixLen;
1008 }
1009 totalSize = fillp;
1010 }
1011 if (e == null) return -1;
1012 int tag = e.tag;
1013 Index ix = indexByTag[tag];
1014 if (ix == null) return -1;
1015 int idx = ix.findIndexOf(e);
1016 if (idx >= 0)
1017 idx += untypedFirstIndexByTag[tag];
1018 return idx;
1019 }
1020
1021 public void initIndexByTag(byte tag, Index ix) {
1022 assert(indexByTag[tag] == null); // do not init twice
1023 Entry[] cpMap = ix.cpMap;
1024 for (int i = 0; i < cpMap.length; i++) {
1025 // It must be a homogeneous Entry set.
1026 assert(cpMap[i].tag == tag);
1027 }
1028 if (tag == CONSTANT_Utf8) {
1029 // Special case: First Utf8 must always be empty string.
1030 assert(cpMap.length == 0 || cpMap[0].stringValue().equals(""));
1031 }
1032 indexByTag[tag] = ix;
1033 // decache indexes derived from this one:
1034 untypedFirstIndexByTag = null;
1035 indexUntyped = null;
1036 if (indexByTagAndClass != null)
1037 indexByTagAndClass[tag] = null;
1038 }
1039
1040 /** Index of all CP entries of a given tag. */
1041 public Index getIndexByTag(byte tag) {
1042 if (tag == CONSTANT_All) {
1043 return getUntypedIndex();
1044 }
1045 Index ix = indexByTag[tag];
1046 if (ix == null) {
1047 // Make an empty one by default.
1048 ix = new Index(tagName(tag), new Entry[0]);
1049 indexByTag[tag] = ix;
1050 }
1051 return ix;
1052 }
1053
1054 /** Index of all CP entries of a given tag and class. */
1055 public Index getMemberIndex(byte tag, ClassEntry classRef) {
1056 if (indexByTagAndClass == null)
1057 indexByTagAndClass = new Index[CONSTANT_Limit][];
1058 Index allClasses = getIndexByTag(CONSTANT_Class);
1059 Index[] perClassIndexes = indexByTagAndClass[tag];
1060 if (perClassIndexes == null) {
1061 // Create the partition now.
1062 // Divide up all entries of the given tag according to their class.
1063 Index allMembers = getIndexByTag(tag);
1064 int[] whichClasses = new int[allMembers.size()];
1065 for (int i = 0; i < whichClasses.length; i++) {
1066 MemberEntry e = (MemberEntry) allMembers.get(i);
1067 int whichClass = allClasses.indexOf(e.classRef);
1068 whichClasses[i] = whichClass;
1069 }
1070 perClassIndexes = partition(allMembers, whichClasses);
1071 for (int i = 0; i < perClassIndexes.length; i++) {
1072 assert (perClassIndexes[i] == null ||
1073 perClassIndexes[i].assertIsSorted());
1074 }
1075 indexByTagAndClass[tag] = perClassIndexes;
1076 }
1077 int whichClass = allClasses.indexOf(classRef);
1078 return perClassIndexes[whichClass];
1079 }
1080
1081 // Given the sequence of all methods of the given name and class,
1082 // produce the ordinal of this particular given overloading.
1083 public int getOverloadingIndex(MemberEntry methodRef) {
1084 Index ix = getMemberIndex(methodRef.tag, methodRef.classRef);
1085 Utf8Entry nameRef = methodRef.descRef.nameRef;
1086 int ord = 0;
1087 for (int i = 0; i < ix.cpMap.length; i++) {
1088 MemberEntry e = (MemberEntry) ix.cpMap[i];
1089 if (e.equals(methodRef))
1090 return ord;
1091 if (e.descRef.nameRef.equals(nameRef))
1092 // Found a different overloading. Increment the ordinal.
1093 ord++;
1094 }
1095 throw new RuntimeException("should not reach here");
1096 }
1097
1098 // Inverse of getOverloadingIndex
1099 public MemberEntry getOverloadingForIndex(byte tag, ClassEntry classRef, String name, int which) {
1100 assert(name.equals(name.intern()));
1101 Index ix = getMemberIndex(tag, classRef);
1102 int ord = 0;
1103 for (int i = 0; i < ix.cpMap.length; i++) {
1104 MemberEntry e = (MemberEntry) ix.cpMap[i];
1105 if (e.descRef.nameRef.stringValue().equals(name)) {
1106 if (ord == which) return e;
1107 ord++;
1108 }
1109 }
1110 throw new RuntimeException("should not reach here");
1111 }
1112
1113 public boolean haveNumbers() {
1114 for (byte tag = CONSTANT_Integer; tag <= CONSTANT_Double; tag++) {
1115 switch (tag) {
1116 case CONSTANT_Integer:
1117 case CONSTANT_Float:
1118 case CONSTANT_Long:
1119 case CONSTANT_Double:
1120 break;
1121 default:
1122 assert(false);
1123 }
1124 if (getIndexByTag(tag).size() > 0) return true;
1125 }
1126 return false;
1127 }
1128
1129 }
1130
1131 /** Close the set cpRefs under the getRef(*) relation.
1132 * Also, if flattenSigs, replace all signatures in cpRefs
1133 * by their equivalent Utf8s.
1134 * Also, discard null from cpRefs.
1135 */
1136 public static
1137 void completeReferencesIn(Set<Entry> cpRefs, boolean flattenSigs) {
1138 cpRefs.remove(null);
1139 for (ListIterator<Entry> work =
1140 new ArrayList<>(cpRefs).listIterator(cpRefs.size());
1141 work.hasPrevious(); ) {
1142 Entry e = work.previous();
1143 work.remove(); // pop stack
1144 assert(e != null);
1145 if (flattenSigs && e.tag == CONSTANT_Signature) {
1146 SignatureEntry se = (SignatureEntry) e;
1147 Utf8Entry ue = se.asUtf8Entry();
1148 // Totally replace e by se.
1149 cpRefs.remove(se);
1150 cpRefs.add(ue);
1151 e = ue; // do not descend into the sig
1152 }
1153 // Recursively add the refs of e to cpRefs:
1154 for (int i = 0; ; i++) {
1155 Entry re = e.getRef(i);
1156 if (re == null)
1157 break; // no more refs in e
1158 if (cpRefs.add(re)) // output the ref
1159 work.add(re); // push stack, if a new ref
1160 }
1161 }
1162 }
1163
1164 static double percent(int num, int den) {
1165 return (int)((10000.0*num)/den + 0.5) / 100.0;
1166 }
1167
1168 public static String tagName(int tag) {
1169 switch (tag) {
1170 case CONSTANT_Utf8: return "Utf8";
1171 case CONSTANT_Integer: return "Integer";
1172 case CONSTANT_Float: return "Float";
1173 case CONSTANT_Long: return "Long";
1174 case CONSTANT_Double: return "Double";
1175 case CONSTANT_Class: return "Class";
1176 case CONSTANT_String: return "String";
1177 case CONSTANT_Fieldref: return "Fieldref";
1178 case CONSTANT_Methodref: return "Methodref";
1179 case CONSTANT_InterfaceMethodref: return "InterfaceMethodref";
1180 case CONSTANT_NameandType: return "NameandType";
1181
1182 // pseudo-tags:
1183 case CONSTANT_All: return "*All";
1184 case CONSTANT_None: return "*None";
1185 case CONSTANT_Signature: return "*Signature";
1186 }
1187 return "tag#"+tag;
1188 }
1189
1190 // archive constant pool definition order
1191 static final byte TAGS_IN_ORDER[] = {
1192 CONSTANT_Utf8,
1193 CONSTANT_Integer, // cp_Int
1194 CONSTANT_Float,
1195 CONSTANT_Long,
1196 CONSTANT_Double,
1197 CONSTANT_String,
1198 CONSTANT_Class,
1199 CONSTANT_Signature,
1200 CONSTANT_NameandType, // cp_Descr
1201 CONSTANT_Fieldref, // cp_Field
1202 CONSTANT_Methodref, // cp_Method
1203 CONSTANT_InterfaceMethodref // cp_Imethod
1204 };
1205 static final byte TAG_ORDER[];
1206 static {
1207 TAG_ORDER = new byte[CONSTANT_Limit];
1208 for (int i = 0; i < TAGS_IN_ORDER.length; i++) {
1209 TAG_ORDER[TAGS_IN_ORDER[i]] = (byte)(i+1);
1210 }
1211 /*
1212 System.out.println("TAG_ORDER[] = {");
1213 for (int i = 0; i < TAG_ORDER.length; i++)
1214 System.out.println(" "+TAG_ORDER[i]+",");
1215 System.out.println("};");
1216 */
1217 }
1218 }