001 /* Copyright 2000, 2001, Compaq Computer Corporation */
002
003 package javafe.ast;
004
005 import javafe.parser.TagConstants;
006 import javafe.util.Assert;
007
008 /**
009 * An <code>Identifier</code> is a symbol, that is, a sequence of
010 * characters. <code>Identifier</code>s are interned: for any given
011 * sequence of characters, we create exactly one instance of
012 * <code>Identifier</code> to represent it (we say that the sequence
013 * of characters is <I>associated with</I> this
014 * <code>Identifier</code> instance). This allows us to use object
015 * equality (that is, <code>==</code>) to check symbol equality.
016 *
017 * <p> This class is thread-safe: multiple threads can enter its any
018 * of its methods (static or non-static) simultaneously. </p>
019 */
020
021 public final class Identifier
022 {
023 //// Private, static variables
024
025 /** Size of intern table. */
026 private static final int TABLE_SIZE = 128;
027
028 /** Table containing every instance of <code>Identifier</code>
029 created. If a symbol <TT>s</TT> has been interned, its
030 associated <code>Identifier</code> is found by hashing it to
031 integer <TT>h</TT> such that <TT>0 <= h <= TABLE_SIZE</TT>,
032 looking up <TT>v = chains[h]</TT>, which is a an array of arrays
033 of <code>Identifier</code>s, then searching <TT>v</TT> for the
034 <code>Identifier</code> associated with <TT>s</TT>. If no such
035 element exists, then <TT>s</TT> hasn't been interned yet.
036
037 <P> This table is only extended, old parts are never updated.
038 Thus, reading the table can occur without any locks being held.
039 Extension of the table is protected by the mutex associated with
040 the table itself (that is, the object pointed to by
041 <code>chains</code>. */
042
043 /*@ invariant (\forall int i; 0<=i && i<chains.length
044 ==> chains[i]==null || chains[i].length>0); */
045 //@ spec_public
046 private static final Identifier chains[][] = new Identifier[TABLE_SIZE][];
047
048
049 /** Initial size of chains inside the table. */
050 private static final int INITIAL_CHAIN_SIZE = 4;
051
052
053 // Private, instance variables
054
055 /** Sequence of characters represented by this Identifier (never
056 <code>null</code>). */
057 //@ invariant chars != null;
058
059 //private char[] chars; //@ in objectState;
060 public char[] chars; //@ in objectState;
061
062 /** Memoization of <code>String.valueOf(chars, 0,
063 chars.length)</code>; may be <code>null</code>. This variable may
064 be written exactly once. */
065 private String equiv; //@ in privateState;
066
067
068 //// "Friend", variables
069
070 /** Constant used for hashing. The hash function used to hash a
071 <i>n</i>-character identifier <code>idn</code> is to sum
072 <code>HC</code>^<i>(n-(i+1))</i><code>*idn[</code><i>i</i><code>]</code>.
073 Note that this is the same hash function used by Java 1.1 for
074 hashing <code>String</code> objects. */
075 static final int HC = 31;
076
077
078 /**
079 * This field defaults to <code>TagConstants.IDENT</code>, but
080 * is set to other values by the scanner to indicate keywords.
081 */
082 /*@ invariant tokenType != TagConstants.BOOLEANLIT &&
083 tokenType != TagConstants.INTLIT &&
084 tokenType != TagConstants.LONGLIT &&
085 tokenType != TagConstants.FLOATLIT &&
086 tokenType != TagConstants.DOUBLELIT &&
087 tokenType != TagConstants.STRINGLIT &&
088 tokenType != TagConstants.CHARLIT &&
089 tokenType != TagConstants.LEXICALPRAGMA &&
090 tokenType != TagConstants.MODIFIERPRAGMA &&
091 tokenType != TagConstants.STMTPRAGMA &&
092 tokenType != TagConstants.TYPEDECLELEMPRAGMA &&
093 tokenType != TagConstants.TYPEMODIFIERPRAGMA; */
094 int tokenType = TagConstants.IDENT;
095
096
097 //@ requires text != null;
098 //@ requires 0<=textlen && textlen<=text.length;
099 private Identifier(char[] text, int textlen, int hashcode) {
100 this.chars = new char[textlen];
101 System.arraycopy(text, 0, this.chars, 0, textlen);
102 }
103
104
105 /** Returns the <code>Identifier</code> associated with
106 <TT>s</TT>. */
107 //@ requires s != null;
108 //@ ensures \result != null;
109 public static Identifier intern(String s) {
110 // Expensive way of doing things, but at least we don't have
111 // to rewrite the above code...
112
113 int len = s.length();
114 char[] chars = new char[len];
115 s.getChars(0, len, chars, 0);
116 return intern(chars, len, hash(chars, len));
117 }
118
119
120 /** Intern a sequence of characters with a pre-computed hashcode.
121
122 <BR> Requires: <code>hashcode = Identifier.hash(text, textlen)</code>
123
124 <P> Ensures: returns the <code>Identifier</code> instance
125 associated with the symbol consisting of the first
126 <code>textlen</code> characters of <code>text</code>. */
127
128 //@ requires text != null;
129 //@ requires 0<=textlen && textlen<=text.length;
130 //@ ensures \result != null;
131 static Identifier intern(char[] text, int textlen, int hashcode) {
132
133 int h = Math.abs(hashcode) % TABLE_SIZE;
134 Identifier[] chain = chains[h];
135
136 // See if it's already in the table
137 int index = 0;
138 if (chain == null) {
139 chain = chains[h] = new Identifier[INITIAL_CHAIN_SIZE];
140 return (chain[0] = new Identifier(text, textlen, hashcode));
141 } else
142 searchloop:
143 for( ; index < chain.length; index++) {
144 Identifier k = chain[index];
145 if (k == null) break;
146 char[] chars = k.chars;
147 if (chars.length == textlen) {
148 for(int j = 0; j < textlen; j++)
149 if (text[j] != chars[j]) continue searchloop;
150 return k;
151 }
152 }
153
154 // Add it to the table
155 if (index == chain.length) { // Expand this chain
156 chain = new Identifier[2*index];
157 System.arraycopy(chains[h], 0, chain, 0, index);
158 chains[h] = chain;
159 }
160 return (chain[index] = new Identifier(text, textlen, hashcode));
161 }
162
163 //@ requires s != null;
164 static int hash(String s) {
165 int len = s.length();
166 int hashcode = 0;
167 for(int i = 0; i < len; i++)
168 hashcode = HC*hashcode + s.charAt(i);
169 return hashcode;
170 }
171
172 //@ requires text != null;
173 //@ requires 0<=textlen && textlen<=text.length;
174 static int hash(char[] text, int textlen) {
175 int hashcode = 0;
176 for(int i = 0; i < textlen; i++)
177 hashcode = HC*hashcode + text[i];
178 return hashcode;
179 }
180
181
182 /** Return a string containing the symbol associated with
183 <code>this</code>. */
184 public /*@non_null*/String toString() {
185 if (equiv == null) equiv = String.valueOf(chars);
186 return equiv;
187 }
188
189 public int hashCode() {
190 return hash(chars, chars.length);
191 }
192
193 public boolean equals(Object o) {
194 return this == o;
195 }
196
197 /** Return true if all invariants are satisfied. */
198 public static void check() {
199 if (chains.length != TABLE_SIZE) Assert.fail("Bad size");
200 for(int hashcode = 0; hashcode < TABLE_SIZE; hashcode++) {
201 Identifier[] chain = chains[hashcode];
202 if (chain != null) {
203 int i;
204 // First in chain must be good
205 for(i = 0; i < chain.length && chain[i] != null; i++) {
206 Identifier idn = chain[i];
207 Identifier idn2 = slowFind(String.valueOf(idn.chars));
208 if (idn != idn2) Assert.fail("Missing entry");
209 // if (idn.hashcode != hash(idn.chars, idn.chars.length))
210 // Assert.fail("Bad hashcode");
211 if (hashcode !=
212 Math.abs(hash(idn.chars, idn.chars.length)) % TABLE_SIZE)
213 Assert.fail("Bad position in table");
214 if (idn.equiv != null)
215 if (! idn.equiv.equals(String.valueOf(idn.chars)))
216 Assert.fail("Bad equiv field");
217 }
218 // Rest in chain must be null;
219 for( ; i < chain.length; i++)
220 if (chain[i] != null) Assert.fail("Bad chain");
221 }
222 }
223 }
224
225
226 /** Used by <code>check</code>; checks for duplicates. */
227 //@ requires s != null;
228 private static Identifier slowFind(String s) {
229 Identifier result = null;
230 for(int h = 0; h < TABLE_SIZE; h++) {
231 Identifier[] chain = chains[h];
232 if (chain != null)
233 for(int i = 0; i < chain.length && chain[i] != null; i++) {
234 Identifier idn = chain[i];
235 if (s.equals(String.valueOf(idn.chars)))
236 if (result == null) result = idn;
237 else Assert.fail("Duplicate entry (" + s + ')');
238 }
239 }
240 if (result == null) Assert.fail("Strange error");
241 return result;
242 }
243
244 //@ requires argv != null;
245 /*@ requires (\forall int i; (0<=i && i<argv.length)
246 ==> argv[i] != null); */
247 public static void main(String[] argv) {
248 String stem = "gensym";
249 int stemlen = stem.length();
250
251 Identifier[] table = new Identifier[2*TABLE_SIZE*INITIAL_CHAIN_SIZE];
252
253
254 // Build table
255 int stemhash = HC*HC*HC*HC*hash(stem);
256 char[] buffer = new char[stemlen + 4];
257 stem.getChars(0, stemlen, buffer, 0);
258 for(int i = 0; i < table.length; i++) {
259 String num = Integer.toHexString(0x1000 + i);
260 if (num.length() != 4)
261 Assert.fail("Ooops");
262 num.getChars(0, 4, buffer, stemlen);
263 table[i] = intern(buffer, stemlen+4, stemhash + hash(num));
264 }
265
266 // Check table
267 for(int i = 0; i < table.length; i++) {
268 String key = stem + Integer.toHexString(0x1000 + i);
269 Identifier idn = intern(key);
270 if (table[i] != idn) Assert.fail("== failed " + i);
271 if (! key.equals(idn.toString()))
272 Assert.fail("toString failed");
273 }
274
275 // Check invariants of table
276 check();
277 }
278 }