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 //@ spec_public 059 private char[] chars; //@ in objectState; 060 061 /** Memoization of <code>String.valueOf(chars, 0, 062 chars.length)</code>; may be <code>null</code>. This variable may 063 be written exactly once. */ 064 private String equiv; //@ in privateState; 065 066 067 //// "Friend", variables 068 069 /** Constant used for hashing. The hash function used to hash a 070 <i>n</i>-character identifier <code>idn</code> is to sum 071 <code>HC</code>^<i>(n-(i+1))</i><code>*idn[</code><i>i</i><code>]</code>. 072 Note that this is the same hash function used by Java 1.1 for 073 hashing <code>String</code> objects. */ 074 static final int HC = 31; 075 076 077 /** 078 * This field defaults to <code>TagConstants.IDENT</code>, but 079 * is set to other values by the scanner to indicate keywords. 080 */ 081 /*@ invariant tokenType != TagConstants.BOOLEANLIT && 082 tokenType != TagConstants.INTLIT && 083 tokenType != TagConstants.LONGLIT && 084 tokenType != TagConstants.FLOATLIT && 085 tokenType != TagConstants.DOUBLELIT && 086 tokenType != TagConstants.STRINGLIT && 087 tokenType != TagConstants.CHARLIT && 088 tokenType != TagConstants.LEXICALPRAGMA && 089 tokenType != TagConstants.MODIFIERPRAGMA && 090 tokenType != TagConstants.STMTPRAGMA && 091 tokenType != TagConstants.TYPEDECLELEMPRAGMA && 092 tokenType != TagConstants.TYPEMODIFIERPRAGMA; */ 093 int tokenType = TagConstants.IDENT; 094 095 096 //@ requires text != null; 097 //@ requires 0<=textlen && textlen<=text.length; 098 private Identifier(char[] text, int textlen, int hashcode) { 099 this.chars = new char[textlen]; 100 System.arraycopy(text, 0, this.chars, 0, textlen); 101 } 102 103 104 /** Returns the <code>Identifier</code> associated with 105 <TT>s</TT>. */ 106 //@ requires s != null; 107 //@ ensures \result != null; 108 public static Identifier intern(String s) { 109 // Expensive way of doing things, but at least we don't have 110 // to rewrite the above code... 111 112 int len = s.length(); 113 char[] chars = new char[len]; 114 s.getChars(0, len, chars, 0); 115 return intern(chars, len, hash(chars, len)); 116 } 117 118 119 /** Intern a sequence of characters with a pre-computed hashcode. 120 121 <BR> Requires: <code>hashcode = Identifier.hash(text, textlen)</code> 122 123 <P> Ensures: returns the <code>Identifier</code> instance 124 associated with the symbol consisting of the first 125 <code>textlen</code> characters of <code>text</code>. */ 126 127 //@ requires text != null; 128 //@ requires 0<=textlen && textlen<=text.length; 129 //@ ensures \result != null; 130 static Identifier intern(char[] text, int textlen, int hashcode) { 131 132 int h = Math.abs(hashcode) % TABLE_SIZE; 133 Identifier[] chain = chains[h]; 134 135 // See if it's already in the table 136 int index = 0; 137 if (chain == null) { 138 chain = chains[h] = new Identifier[INITIAL_CHAIN_SIZE]; 139 return (chain[0] = new Identifier(text, textlen, hashcode)); 140 } else 141 searchloop: 142 for( ; index < chain.length; index++) { 143 Identifier k = chain[index]; 144 if (k == null) break; 145 char[] chars = k.chars; 146 if (chars.length == textlen) { 147 for(int j = 0; j < textlen; j++) 148 if (text[j] != chars[j]) continue searchloop; 149 return k; 150 } 151 } 152 153 // Add it to the table 154 if (index == chain.length) { // Expand this chain 155 chain = new Identifier[2*index]; 156 System.arraycopy(chains[h], 0, chain, 0, index); 157 chains[h] = chain; 158 } 159 return (chain[index] = new Identifier(text, textlen, hashcode)); 160 } 161 162 //@ requires s != null; 163 static int hash(String s) { 164 int len = s.length(); 165 int hashcode = 0; 166 for(int i = 0; i < len; i++) 167 hashcode = HC*hashcode + s.charAt(i); 168 return hashcode; 169 } 170 171 //@ requires text != null; 172 //@ requires 0<=textlen && textlen<=text.length; 173 static int hash(char[] text, int textlen) { 174 int hashcode = 0; 175 for(int i = 0; i < textlen; i++) 176 hashcode = HC*hashcode + text[i]; 177 return hashcode; 178 } 179 180 181 /** Return a string containing the symbol associated with 182 <code>this</code>. */ 183 public String toString() { 184 if (equiv == null) equiv = String.valueOf(chars); 185 return equiv; 186 } 187 188 public int hashCode() { 189 return hash(chars, chars.length); 190 } 191 192 public boolean equals(Object o) { 193 return this == o; 194 } 195 196 /** Return true if all invariants are satisfied. */ 197 public static void check() { 198 if (chains.length != TABLE_SIZE) Assert.fail("Bad size"); 199 for(int hashcode = 0; hashcode < TABLE_SIZE; hashcode++) { 200 Identifier[] chain = chains[hashcode]; 201 if (chain != null) { 202 int i; 203 // First in chain must be good 204 for(i = 0; i < chain.length && chain[i] != null; i++) { 205 Identifier idn = chain[i]; 206 Identifier idn2 = slowFind(String.valueOf(idn.chars)); 207 if (idn != idn2) Assert.fail("Missing entry"); 208 // if (idn.hashcode != hash(idn.chars, idn.chars.length)) 209 // Assert.fail("Bad hashcode"); 210 if (hashcode != 211 Math.abs(hash(idn.chars, idn.chars.length)) % TABLE_SIZE) 212 Assert.fail("Bad position in table"); 213 if (idn.equiv != null) 214 if (! idn.equiv.equals(String.valueOf(idn.chars))) 215 Assert.fail("Bad equiv field"); 216 } 217 // Rest in chain must be null; 218 for( ; i < chain.length; i++) 219 if (chain[i] != null) Assert.fail("Bad chain"); 220 } 221 } 222 } 223 224 225 /** Used by <code>check</code>; checks for duplicates. */ 226 //@ requires s != null; 227 private static Identifier slowFind(String s) { 228 Identifier result = null; 229 for(int h = 0; h < TABLE_SIZE; h++) { 230 Identifier[] chain = chains[h]; 231 if (chain != null) 232 for(int i = 0; i < chain.length && chain[i] != null; i++) { 233 Identifier idn = chain[i]; 234 if (s.equals(String.valueOf(idn.chars))) 235 if (result == null) result = idn; 236 else Assert.fail("Duplicate entry (" + s + ')'); 237 } 238 } 239 if (result == null) Assert.fail("Strange error"); 240 return result; 241 } 242 243 //@ requires argv != null; 244 /*@ requires (\forall int i; (0<=i && i<argv.length) 245 ==> argv[i] != null); */ 246 public static void main(String[] argv) { 247 String stem = "gensym"; 248 int stemlen = stem.length(); 249 250 Identifier[] table = new Identifier[2*TABLE_SIZE*INITIAL_CHAIN_SIZE]; 251 252 253 // Build table 254 int stemhash = HC*HC*HC*HC*hash(stem); 255 char[] buffer = new char[stemlen + 4]; 256 stem.getChars(0, stemlen, buffer, 0); 257 for(int i = 0; i < table.length; i++) { 258 String num = Integer.toHexString(0x1000 + i); 259 if (num.length() != 4) 260 Assert.fail("Ooops"); 261 num.getChars(0, 4, buffer, stemlen); 262 table[i] = intern(buffer, stemlen+4, stemhash + hash(num)); 263 } 264 265 // Check table 266 for(int i = 0; i < table.length; i++) { 267 String key = stem + Integer.toHexString(0x1000 + i); 268 Identifier idn = intern(key); 269 if (table[i] != idn) Assert.fail("== failed " + i); 270 if (! key.equals(idn.toString())) 271 Assert.fail("toString failed"); 272 } 273 274 // Check invariants of table 275 check(); 276 } 277 }