Represent tokens as a compressed stream instead of an array.

vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/bigint_operations.h"
 #include "vm/bootstrap.h"
@@ skipping 4337 matching lines @@
   return result.raw();
 }
 
 
 const char* LiteralToken::ToCString() const {
   const String& token = String::Handle(literal());
   return token.ToCString();
 }
 
 
+RawArray* TokenStream::TokenObjects() const {
+  return raw_ptr()->token_objects_;
+}
+
+
+void TokenStream::SetTokenObjects(const Array& value) const {
+  StorePointer(&raw_ptr()->token_objects_, value.raw());
+}
+
+
 void TokenStream::SetLength(intptr_t value) const {
-  raw_ptr()->length_ = Smi::New(value);
-}
-
-
-void TokenStream::SetTokenAt(intptr_t index,
-                             Token::Kind kind,
-                             const String& literal) {
-  if (kind == Token::kIDENT) {
-    if (FLAG_compiler_stats) {
-      CompilerStats::num_ident_tokens_total += 1;
-    }
-    StorePointer(EntryAddr(index), reinterpret_cast<RawObject*>(literal.raw()));
-  } else if (Token::NeedsLiteralToken(kind)) {
-    if (FLAG_compiler_stats) {
-      CompilerStats::num_literal_tokens_total += 1;
-    }
-    StorePointer(
-        EntryAddr(index),
-        reinterpret_cast<RawObject*>(LiteralToken::New(kind, literal)));
-  } else {
-    ASSERT(kind < Token::kNumTokens);
-    *(SmiAddr(index)) = Smi::New(kind);
-  }
-}
-
-
-void TokenStream::SetTokenAt(intptr_t index, const Object& token) {
-  StorePointer(EntryAddr(index), token.raw());
-}
-
-
-RawObject* TokenStream::TokenAt(intptr_t index) const {
-  return *EntryAddr(index);
-}
-
-
-RawString* TokenStream::LiteralAt(intptr_t index) const {
-  const Object& obj = Object::Handle(TokenAt(index));
-  if (obj.IsString()) {
-    return reinterpret_cast<RawString*>(obj.raw());
-  } else if (obj.IsSmi()) {
-    Token::Kind kind = static_cast<Token::Kind>(
-        Smi::Value(reinterpret_cast<RawSmi*>(obj.raw())));
-    ASSERT(kind < Token::kNumTokens);
-    if (Token::IsPseudoKeyword(kind) || Token::IsKeyword(kind)) {
-      Isolate* isolate = Isolate::Current();
-      ObjectStore* object_store = isolate->object_store();
-      String& str = String::Handle(isolate, String::null());
-      const Array& symbols = Array::Handle(isolate,
-                                           object_store->keyword_symbols());
-      ASSERT(!symbols.IsNull());
-      str ^= symbols.At(kind - Token::kFirstKeyword);
-      ASSERT(!str.IsNull());
-      return str.raw();
-    }
-    return String::NewSymbol(Token::Str(kind));
-  } else {
-    LiteralToken& token = LiteralToken::Handle();
-    token ^= obj.raw();  // Must be a literal token.
-    return token.literal();
-  }
+  raw_ptr()->length_ = value;
 }
 
 
 RawString* TokenStream::GenerateSource() const {
+  TokenStreamIterator iterator(*this, 0);
   GrowableObjectArray& literals =
       GrowableObjectArray::Handle(GrowableObjectArray::New(Length()));
   String& literal = String::Handle();
   String& blank = String::Handle(String::New(" "));
   String& newline = String::Handle(String::New("\n"));
-  for (intptr_t i = 0; i < Length(); i++) {
-    Token::Kind kind = KindAt(i);
-    literal = LiteralAt(i);
+  Object& obj = Object::Handle();
+  Token::Kind kind = iterator.CurrentTokenKind();
+  while (kind != Token::kEOS) {
+    obj = iterator.CurrentToken();
+    literal = iterator.MakeLiteralToken(obj);
     literals.Add(literal);
     if (kind == Token::kLBRACE) {
       literals.Add(newline);
     } else {
       literals.Add(blank);
     }
+    iterator.Advance();
+    kind = iterator.CurrentTokenKind();
   }
   const Array& source = Array::Handle(Array::MakeArray(literals));
   return String::ConcatAll(source);
 }
 
 
+intptr_t TokenStream::ComputeSourcePosition(intptr_t tok_pos) const {
+  TokenStreamIterator iterator(*this, 0);
+  intptr_t src_pos = 0;
+  Token::Kind kind = iterator.CurrentTokenKind();
+  while (iterator.CurrentPosition() < tok_pos && kind != Token::kEOS) {
+    iterator.Advance();
+    kind = iterator.CurrentTokenKind();
+    src_pos += 1;
+  }
+  return src_pos;
+}
+
+
 RawTokenStream* TokenStream::New(intptr_t len) {
   const Class& token_stream_class = Class::Handle(Object::token_stream_class());
   TokenStream& result = TokenStream::Handle();
   {
     RawObject* raw = Object::Allocate(token_stream_class,
                                       TokenStream::InstanceSize(len),
                                       Heap::kOld);
     NoGCScope no_gc;
     result ^= raw;
     result.SetLength(len);
   }
   return result.raw();
 }
 
 
+// Helper class for creation of compressed token stream data.
+class CompressedTokenStreamData : public ValueObject {
+ public:
+  CompressedTokenStreamData() :
+      buffer_(NULL),
+      stream_(&buffer_, Reallocate),
+      token_objects_(GrowableObjectArray::Handle(
+          GrowableObjectArray::New(kInitialTokenCount, Heap::kOld))),
+      ident_obj_(Object::Handle()),
+      literal_token_(LiteralToken::Handle()) {
+    const String& empty_literal = String::Handle();
+    token_objects_.Add(empty_literal);
+  }
+  ~CompressedTokenStreamData() {
+    free(buffer_);
+  }
+
+  // Add an IDENT token into the stream and the token objects array.
+  void AddIdentToken(String* ident) {
+    if (ident != NULL) {
+      // If the IDENT token is already in the tokens object array use the
+      // same index instead of duplicating it.
+      intptr_t index = FindIdentIndex(ident);
+      if (index == -1) {
+        WriteIndex(token_objects_.Length());
+        ASSERT(ident != NULL);
+        token_objects_.Add(*ident);
+      } else {
+        WriteIndex(index);
+      }
+    } else {
+      WriteIndex(0);
+    }
+  }
+
+  // Add a LITERAL token into the stream and the token objects array.
+  void AddLiteralToken(Token::Kind kind, String* literal) {
+    if (literal != NULL) {
+      WriteIndex(token_objects_.Length());
+      ASSERT(literal != NULL);
+      literal_token_ = LiteralToken::New(kind, *literal);
+      token_objects_.Add(literal_token_);
+    } else {
+      WriteIndex(0);
+    }
+  }
+
+  // Add a simple token into the stream.
+  void AddSimpleToken(intptr_t kind) {
+    stream_.WriteUnsigned(kind);
+  }
+
+  // Return the compressed token stream length.
+  intptr_t Length() const { return stream_.bytes_written(); }
+
+  // Finalize the compressed token stream by copying the stream into the
+  // TokenStream object and setting up the token objects array.
+  void FinalizeTokenStreamData(const TokenStream& token_stream,
+                               void* data_addr) {
+    NoGCScope no_gc;
+    memmove(data_addr, buffer_, Length());
+    const Array& tokens = Array::Handle(Array::MakeArray(token_objects_));
+    token_stream.SetTokenObjects(tokens);
+  }
+
+ private:
+  intptr_t FindIdentIndex(String* ident) {

[Ivan Posva, 2012/07/02 22:56:05]

We should also investigate unique indices for literals.

[siva, 2012/07/04 01:43:02]

Done.

+    ASSERT(ident != NULL);
+    intptr_t hash_value = ident->Hash() % kTableSize;
+    GrowableArray<intptr_t>& value = table_[hash_value];
+    for (intptr_t i = 0; i < value.length(); i++) {
+      intptr_t index = value[i];
+      ident_obj_ = token_objects_.At(index);
+      if (ident_obj_.IsString()) {
+        const String& ident_str = String::Cast(ident_obj_);
+        if (ident->Equals(ident_str)) {
+          return index;
+        }
+      }
+    }
+    value.Add(token_objects_.Length());
+    return -1;
+  }
+
+  void WriteIndex(intptr_t value) {
+    stream_.WriteUnsigned(value + Token::kNumTokens);
+  }
+
+  static uint8_t* Reallocate(uint8_t* ptr,
+                             intptr_t old_size,
+                             intptr_t new_size) {
+    void* new_ptr = ::realloc(reinterpret_cast<void*>(ptr), new_size);
+    return reinterpret_cast<uint8_t*>(new_ptr);
+  }
+
+  static const int kInitialTokenCount = 32;
+  static const intptr_t kTableSize = 128;
+
+  uint8_t* buffer_;
+  WriteStream stream_;
+  GrowableArray<intptr_t> table_[kTableSize];
+  const GrowableObjectArray& token_objects_;
+  Object& ident_obj_;
+  LiteralToken& literal_token_;
+
+  DISALLOW_COPY_AND_ASSIGN(CompressedTokenStreamData);
+};
+
+
 RawTokenStream* TokenStream::New(const Scanner::GrowableTokenStream& tokens) {
+  // Copy the relevant data out of the scanner into a compressed stream of
+  // tokens.
+  CompressedTokenStreamData data;
   intptr_t len = tokens.length();
-
-  TokenStream& result = TokenStream::Handle(New(len));
-  // Copy the relevant data out of the scanner's token stream.
-  const String& empty_literal = String::Handle();
   for (intptr_t i = 0; i < len; i++) {
     Scanner::TokenDescriptor token = tokens[i];
-    if (token.literal != NULL) {
-      result.SetTokenAt(i, token.kind, *(token.literal));
-    } else {
-      result.SetTokenAt(i, token.kind, empty_literal);
+    if (token.kind == Token::kIDENT) {  // Identifier token.
+      if (FLAG_compiler_stats) {
+        CompilerStats::num_ident_tokens_total += 1;
+      }
+      data.AddIdentToken(token.literal);
+    } else if (Token::NeedsLiteralToken(token.kind)) {  // Literal token.
+      if (FLAG_compiler_stats) {
+        CompilerStats::num_literal_tokens_total += 1;
+      }
+      data.AddLiteralToken(token.kind, token.literal);
+    } else {  // Keyword, pseudo keyword etc.
+      ASSERT(token.kind < Token::kNumTokens);
+      data.AddSimpleToken(token.kind);
     }
   }
+  if (FLAG_compiler_stats) {
+    CompilerStats::num_tokens_total += len;
+  }
+  data.AddSimpleToken(Token::kEOS);  // End of stream.
+
+  // Create and setup the token stream object.
+  const TokenStream& result = TokenStream::Handle(New(data.Length()));
+  data.FinalizeTokenStreamData(result, result.EntryAddr(0));
   return result.raw();
 }
 
 
 const char* TokenStream::ToCString() const {
   return "TokenStream";
 }
 
 
+TokenStreamIterator::TokenStreamIterator(const TokenStream& tokens,
+                                         intptr_t token_pos)
+    : tokens_(tokens),
+      stream_(tokens.EntryAddr(0), tokens.Length()),

[Ivan Posva, 2012/07/02 21:48:32]

This is not GC safe.

[siva, 2012/07/04 01:43:02]

Removed the stream_ field and instead use EntryAddr(pos) for access to the
stream bytes.

On 2012/07/02 21:48:32, Ivan Posva wrote:

+      token_objects_(Array::Handle(tokens.TokenObjects())),
+      obj_(Object::Handle()),
+      cur_token_pos_(token_pos),
+      cur_token_kind_(Token::kILLEGAL),
+      cur_token_obj_index_(-1) {
+  SetCurrentPosition(token_pos);
+}
+
+
+bool TokenStreamIterator::IsValid() const {
+  return !tokens_.IsNull();
+}
+
+
+Token::Kind TokenStreamIterator::LookaheadTokenKind(intptr_t num_tokens) {
+  intptr_t saved_position = stream_.CurrentPosition();
+  Token::Kind kind = Token::kILLEGAL;
+  intptr_t value = -1;
+  intptr_t count = 0;
+  while (count < num_tokens && value != Token::kEOS) {
+    value = ReadToken();
+    count += 1;
+  }
+  if (value < Token::kNumTokens) {
+    kind = static_cast<Token::Kind>(value);
+  } else {
+    value = value - Token::kNumTokens;
+    obj_ = token_objects_.At(value);
+    if (obj_.IsLiteralToken()) {
+      const LiteralToken& literal_token = LiteralToken::Cast(obj_);
+      kind = literal_token.kind();
+    } else {
+      ASSERT(obj_.IsString());  // Must be an identifier.
+      kind = Token::kIDENT;
+    }
+  }
+  stream_.SetPosition(saved_position);
+  return kind;
+}
+
+
+intptr_t TokenStreamIterator::CurrentPosition() const {
+  return cur_token_pos_;
+}
+
+
+void TokenStreamIterator::SetCurrentPosition(intptr_t value) {
+  stream_.SetPosition(value);
+  Advance();
+}
+
+
+void TokenStreamIterator::Advance() {
+  cur_token_pos_ = stream_.CurrentPosition();
+  intptr_t value = ReadToken();
+  if (value < Token::kNumTokens) {
+    cur_token_kind_ = static_cast<Token::Kind>(value);
+    cur_token_obj_index_ = -1;
+    return;
+  }
+  cur_token_obj_index_ = value - Token::kNumTokens;
+  obj_ = token_objects_.At(cur_token_obj_index_);
+  if (obj_.IsLiteralToken()) {
+    const LiteralToken& literal_token = LiteralToken::Cast(obj_);
+    cur_token_kind_ = literal_token.kind();
+    return;
+  }
+  ASSERT(obj_.IsString());  // Must be an identifier.
+  cur_token_kind_ = Token::kIDENT;
+}
+
+
+RawObject* TokenStreamIterator::CurrentToken() const {
+  if (cur_token_obj_index_ != -1) {
+    return token_objects_.At(cur_token_obj_index_);
+  } else {
+    return Smi::New(cur_token_kind_);
+  }
+}
+
+
+RawString* TokenStreamIterator::CurrentLiteral() const {
+  obj_ = CurrentToken();
+  return MakeLiteralToken(obj_);
+}
+
+
+RawString* TokenStreamIterator::MakeLiteralToken(const Object& obj) const {
+  if (obj.IsString()) {
+    return reinterpret_cast<RawString*>(obj.raw());
+  } else if (obj.IsSmi()) {
+    Token::Kind kind = static_cast<Token::Kind>(
+        Smi::Value(reinterpret_cast<RawSmi*>(obj.raw())));
+    ASSERT(kind < Token::kNumTokens);
+    if (Token::IsPseudoKeyword(kind) || Token::IsKeyword(kind)) {
+      Isolate* isolate = Isolate::Current();
+      ObjectStore* object_store = isolate->object_store();
+      String& str = String::Handle(isolate, String::null());
+      const Array& symbols = Array::Handle(isolate,
+                                           object_store->keyword_symbols());
+      ASSERT(!symbols.IsNull());
+      str ^= symbols.At(kind - Token::kFirstKeyword);
+      ASSERT(!str.IsNull());
+      return str.raw();
+    }
+    return String::NewSymbol(Token::Str(kind));
+  } else {
+    ASSERT(obj.IsLiteralToken());  // Must be a literal token.
+    const LiteralToken& literal_token = LiteralToken::Cast(obj);
+    return literal_token.literal();
+  }
+}
+
+
 RawString* Script::source() const {
   String& source = String::Handle(raw_ptr()->source_);
   if (source.IsNull()) {
     const TokenStream& token_stream = TokenStream::Handle(tokens());
     return token_stream.GenerateSource();
   } else {
     return raw_ptr()->source_;
   }
 }
 
@@ skipping 34 matching lines @@
     CompilerStats::src_length += src.Length();
   }
 }
 
 
 void Script::GetTokenLocation(intptr_t token_pos,
                               intptr_t* line,
                               intptr_t* column) const {
   const String& src = String::Handle(source());
   const String& dummy_key = String::Handle(String::New(""));
+  const TokenStream& tkns = TokenStream::Handle(tokens());
+  intptr_t src_pos = tkns.ComputeSourcePosition(token_pos);
   Scanner scanner(src, dummy_key);
-  scanner.ScanTo(token_pos);
+  scanner.ScanTo(src_pos);
   *line = scanner.CurrentPosition().line;
   *column = scanner.CurrentPosition().column;
 }
 
 
 void Script::TokenRangeAtLine(intptr_t line_number,
                               intptr_t* first_token_index,
                               intptr_t* last_token_index) const {
   const String& src = String::Handle(source());
   const String& dummy_key = String::Handle(String::New(""));
@@ skipping 5710 matching lines @@
   const String& str = String::Handle(pattern());
   const char* format = "JSRegExp: pattern=%s flags=%s";
   intptr_t len = OS::SNPrint(NULL, 0, format, str.ToCString(), Flags());
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len + 1));
   OS::SNPrint(chars, (len + 1), format, str.ToCString(), Flags());
   return chars;
 }
 
 }  // namespace dart