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    }