CSE2410 Fall 2014 Bounce

// Copyright 2006-2008 the V8 project authors. All rights reserved.

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

//       notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

//       copyright notice, this list of conditions and the following

//       disclaimer in the documentation and/or other materials provided

//       with the distribution.

//     * Neither the name of Google Inc. nor the names of its

//       contributors may be used to endorse or promote products derived

//       from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "token.h"

namespace v8 { namespace internal {

#ifdef DEBUG

#define T(name, string, precedence) #name,

const char* Token::name_[NUM_TOKENS] = {

  TOKEN_LIST(T, T, IGNORE_TOKEN)

};

#undef T

#endif

#define T(name, string, precedence) string,

const char* Token::string_[NUM_TOKENS] = {

  TOKEN_LIST(T, T, IGNORE_TOKEN)

};

#undef T

#define T(name, string, precedence) precedence,

int8_t Token::precedence_[NUM_TOKENS] = {

  TOKEN_LIST(T, T, IGNORE_TOKEN)

};

#undef T

// A perfect (0 collision) hash table of keyword token values.

// larger N will reduce the number of collisions (power of 2 for fast %)

const unsigned int N = 128;

// make this small since we have <= 256 tokens

static uint8_t Hashtable[N];

static bool IsInitialized = false;

static unsigned int Hash(const char* s) {

  // The following constants have been found using trial-and-error. If the

  // keyword set changes, they may have to be recomputed (make them flags

  // and play with the flag values). Increasing N is the simplest way to

  // reduce the number of collisions.

  // we must use at least 4 or more chars ('const' and 'continue' share

  // 'con')

  const unsigned int L = 5;

  // smaller S tend to reduce the number of collisions

  const unsigned int S = 4;

  // make this a prime, or at least an odd number

  const unsigned int M = 3;

  unsigned int h = 0;

  for (unsigned int i = 0; s[i] != '\0' && i < L; i++) {

    h += (h << S) + s[i];

  }

  // unsigned int % by a power of 2 (otherwise this will not be a bit mask)

  return h * M % N;

}

Token::Value Token::Lookup(const char* str) {

  ASSERT(IsInitialized);

  Value k = static_cast<Value>(Hashtable[Hash(str)]);

  const char* s = string_[k];

  ASSERT(s != NULL || k == IDENTIFIER);

  if (s == NULL || strcmp(s, str) == 0) {

    return k;

  }

  return IDENTIFIER;

}

#ifdef DEBUG

// We need this function because C++ doesn't allow the expression

// NULL == NULL, which is a result of macro expansion below. What

// the hell?

static bool IsNull(const char* s) {

  return s == NULL;

}

#endif

void Token::Initialize() {

  if (IsInitialized) return;

  // A list of all keywords, terminated by ILLEGAL.

#define T(name, string, precedence) name,

  static Value keyword[] = {

    TOKEN_LIST(IGNORE_TOKEN, T, IGNORE_TOKEN)

    ILLEGAL

  };

#undef T

  // Assert that the keyword array contains the 25 keywords, 3 future

  // reserved words (const, debugger, and native), and the 3 named literals

  // defined by ECMA-262 standard.

  ASSERT(ARRAY_SIZE(keyword) == 25 + 3 + 3 + 1);  // +1 for ILLEGAL sentinel

  // Initialize Hashtable.

  ASSERT(NUM_TOKENS <= 256);  // Hashtable contains uint8_t elements

  for (unsigned int i = 0; i < N; i++) {

    Hashtable[i] = IDENTIFIER;

  }

  // Insert all keywords into Hashtable.

  int collisions = 0;

  for (int i = 0; keyword[i] != ILLEGAL; i++) {

    Value k = keyword[i];

    unsigned int h = Hash(string_[k]);

    if (Hashtable[h] != IDENTIFIER) collisions++;

    Hashtable[h] = k;

  }

  if (collisions > 0) {

    PrintF("%d collisions in keyword hashtable\n", collisions);

    FATAL("Fix keyword lookup!");

  }

  IsInitialized = true;

  // Verify hash table.

#define T(name, string, precedence) \

  ASSERT(IsNull(string) || Lookup(string) == IDENTIFIER);

#define K(name, string, precedence) \

  ASSERT(Lookup(string) == name);

  TOKEN_LIST(T, K, IGNORE_TOKEN)

#undef K

#undef T

}

} }  // namespace v8::internal