    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    }