Optimize parsing of qualified identifiers.

runtime/vm/parser.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/parser.h"
 
 #include "vm/bigint_operations.h"
 #include "vm/class_finalizer.h"
 #include "vm/compiler.h"
 #include "vm/compiler_stats.h"
@@ skipping 251 matching lines @@
   return &result;
 }
 
 
 // A QualIdent is an optionally qualified identifier.
 struct QualIdent {
   QualIdent() {
     Clear();
   }
   void Clear() {
-    is_local_scope_ident = false;
     lib_prefix = NULL;
     qualifier = NULL;
     ident_pos = 0;
     ident = NULL;
   }
-  bool is_local_scope_ident;
   LibraryPrefix* lib_prefix;
   String* qualifier;
   intptr_t ident_pos;
   String* ident;
 };
 
 
 struct ParamDesc {
   ParamDesc()
       : type(NULL),
@@ skipping 1613 matching lines @@
       SkipExpr();
       SetAllowFunctionLiterals(true);
     }
   } while (CurrentToken() == Token::kCOMMA);
 }
 
 
 void Parser::ParseQualIdent(QualIdent* qual_ident) {
   ASSERT(IsIdentifier());
   if (!is_top_level_) {
-    AstNode* var_or_field = NULL;
-    bool is_local_ident = ResolveIdentInLocalScope(token_index_,
-                                                   *CurrentLiteral(),
-                                                   &var_or_field);
     qual_ident->ident_pos = token_index_;
     qual_ident->ident = CurrentLiteral();
     qual_ident->lib_prefix = NULL;
     qual_ident->qualifier = NULL;
-    qual_ident->is_local_scope_ident = is_local_ident;
     ConsumeToken();
-    if (!is_local_ident && (CurrentToken() == Token::kPERIOD)) {
-      LibraryPrefix& lib_prefix = LibraryPrefix::ZoneHandle();
-      lib_prefix = current_class().LookupLibraryPrefix(*(qual_ident->ident));
-      if (!lib_prefix.IsNull()) {
-        // We have a library prefix qualified identifier.
-        ConsumeToken();  // Consume the kPERIOD token.
-        qual_ident->lib_prefix = &lib_prefix;
-        qual_ident->qualifier = qual_ident->ident;
-        qual_ident->ident_pos = token_index_;
-        qual_ident->ident = ExpectIdentifier("identifier expected after '.'");
+    if (CurrentToken() == Token::kPERIOD) {
+      if (!ResolveIdentInLocalScope(qual_ident->ident_pos,
+                                    *(qual_ident->ident),
+                                    NULL)) {
+        LibraryPrefix& lib_prefix = LibraryPrefix::ZoneHandle();
+        lib_prefix = current_class().LookupLibraryPrefix(*(qual_ident->ident));
+        if (!lib_prefix.IsNull()) {
+          // We have a library prefix qualified identifier.
+          ConsumeToken();  // Consume the kPERIOD token.
+          qual_ident->lib_prefix = &lib_prefix;
+          qual_ident->qualifier = qual_ident->ident;
+          qual_ident->ident_pos = token_index_;
+          qual_ident->ident = ExpectIdentifier("identifier expected after '.'");
+        }
       }
     }
   } else {
     qual_ident->ident_pos = token_index_;
     qual_ident->ident = CurrentLiteral();
     qual_ident->lib_prefix = NULL;
     qual_ident->qualifier = NULL;
-    qual_ident->is_local_scope_ident = false;
     ConsumeToken();
     if (CurrentToken() == Token::kPERIOD) {
       ConsumeToken();  // Consume the kPERIOD token.
       qual_ident->qualifier = qual_ident->ident;
       qual_ident->ident_pos = token_index_;
       qual_ident->ident = ExpectIdentifier("identifier expected after '.'");
     }
   }
 }
 
@@ skipping 686 matching lines @@
 // and the alias name of a function type alias.
 // Token position remains unchanged.
 bool Parser::IsFunctionTypeAliasName() {
   if (IsIdentifier() && (LookaheadToken(1) == Token::kLPAREN)) {
     return true;
   }
   const intptr_t saved_pos = token_index_;
   bool is_alias_name = false;
   if (IsIdentifier() && (LookaheadToken(1) == Token::kLT)) {
     ConsumeToken();
-    if (IsTypeParameter() && (CurrentToken() == Token::kLPAREN)) {
+    if (TryParseTypeParameter() && (CurrentToken() == Token::kLPAREN)) {
       is_alias_name = true;
     }
   }
   SetPosition(saved_pos);
   return is_alias_name;
 }
 
 
 void Parser::ParseFunctionTypeAlias(GrowableArray<const Class*>* classes) {
   TRACE_PARSER("ParseFunctionTypeAlias");
@@ skipping 132 matching lines @@
     if (CurrentToken() == Token::kFACTORY) {
       Warning("'factory' is obsolete, use 'default' instead.");
     }
     ConsumeToken();
     if (CurrentToken() != Token::kIDENT) {
       ErrorMsg("class name expected");
     }
     const intptr_t factory_pos = token_index_;
     QualIdent factory_name;
     ParseQualIdent(&factory_name);
-    if (factory_name.is_local_scope_ident) {
-      ErrorMsg(factory_pos,
-               "using '%s' in this context is invalid",
-               factory_name.ident->ToCString());
-    }
     String& qualifier = String::Handle();
     if (factory_name.qualifier != NULL) {
       qualifier ^= factory_name.qualifier->raw();
     }
     const UnresolvedClass& unresolved_factory_class = UnresolvedClass::Handle(
         UnresolvedClass::New(factory_pos, qualifier, *(factory_name.ident)));
     const Class& factory_class = Class::Handle(
         Class::New(String::Handle(String::NewSymbol(":factory_signature")),
                    script_));
     factory_class.set_library(library_);
@@ skipping 1095 matching lines @@
   } else {
     AstNode* initialization =
         new StoreLocalNode(ident_pos, *function_variable, closure);
     return initialization;
   }
 }
 
 
 // Returns true if the current and next tokens can be parsed as type
 // parameters. Current token position is not saved and restored.
-bool Parser::IsTypeParameter() {
+bool Parser::TryParseTypeParameter() {
   if (CurrentToken() == Token::kLT) {
     // We are possibly looking at type parameters. Find closing ">".
     int nesting_level = 0;
     do {
       if (CurrentToken() == Token::kLT) {
         nesting_level++;
       } else if (CurrentToken() == Token::kGT) {
         nesting_level--;
       } else if (CurrentToken() == Token::kSHR) {
         nesting_level -= 2;
@@ skipping 19 matching lines @@
 
 
 // Returns true if the current token is kIDENT or a pseudo-keyword.
 bool Parser::IsIdentifier() {
   return Token::IsIdentifier(CurrentToken());
 }
 
 
 // Returns true if the next tokens can be parsed as a type with optional
 // type parameters. Current token position is not restored.
-bool Parser::IsOptionalType() {
+bool Parser::TryParseOptionalType() {
   if (CurrentToken() == Token::kIDENT) {
     QualIdent type_name;
     ParseQualIdent(&type_name);
-    // Check if the type_name has been defined as a variable in a local scope,
-    // hiding the type.
-    if (type_name.is_local_scope_ident) {
-      return false;
-    }
-    if (CurrentToken() == Token::kLT && !IsTypeParameter()) {
+    if (CurrentToken() == Token::kLT && !TryParseTypeParameter()) {

[hausner, 2012/01/23 18:31:24]

I've been conditioned to expect extra parens here.

[regis, 2012/01/23 19:56:23]

Done.

       return false;
     }
   }
   return true;
 }
 
 
 // Returns true if the next tokens can be parsed as a type with optional
 // type parameters, or keyword "void".
 // Current token position is not restored.
-bool Parser::IsReturnType() {
+bool Parser::TryParseReturnType() {
   if (CurrentToken() == Token::kVOID) {
     ConsumeToken();
     return true;
   } else if (CurrentToken() == Token::kIDENT) {
-    return IsOptionalType();
+    return TryParseOptionalType();
   }
   return false;
 }
 
 
 // Look ahead to detect whether the next tokens should be parsed as
 // a variable declaration. Returns true if we detect the token pattern:
 // ('var' | 'final' | type ident (';' | '=' | ','))
 // Token position remains unchanged.
 bool Parser::IsVariableDeclaration() {
   if ((CurrentToken() == Token::kVAR) ||
       (CurrentToken() == Token::kFINAL)) {
     return true;
   }
   if (CurrentToken() != Token::kIDENT) {
     // Not a legal type identifier.
     return false;
   }
   const intptr_t saved_pos = token_index_;
   bool is_var_decl = false;
-  if (IsOptionalType()) {
+  if (TryParseOptionalType()) {
     if (IsIdentifier()) {
       ConsumeToken();
       if ((CurrentToken() == Token::kSEMICOLON) ||
           (CurrentToken() == Token::kCOMMA) ||
           (CurrentToken() == Token::kASSIGN)) {
         is_var_decl = true;
       }
     }
   }
   SetPosition(saved_pos);
@@ skipping 14 matching lines @@
   return (IsIdentifier() &&
       (LookaheadToken(1) == Token::kLPAREN)) || IsFunctionDeclaration();
 }
 
 
 bool Parser::IsTopLevelAccessor() {
   if ((CurrentToken() == Token::kGET) || (CurrentToken() == Token::kSET)) {
     return true;
   }
   const intptr_t saved_pos = token_index_;
-  if (IsReturnType()) {
+  if (TryParseReturnType()) {
     if ((CurrentToken() == Token::kGET) || (CurrentToken() == Token::kSET)) {
       if (Token::IsIdentifier(LookaheadToken(1))) {  // Accessor name.
         SetPosition(saved_pos);
         return true;
       }
     }
   }
   SetPosition(saved_pos);
   return false;
 }
 
 
 bool Parser::IsFunctionLiteral() {
   if (!allow_function_literals_) {
     return false;
   }
   const intptr_t saved_pos = token_index_;
   bool is_function_literal = false;
   if (IsIdentifier() && (LookaheadToken(1) == Token::kLPAREN)) {
     ConsumeToken();  // Consume function identifier.
-  } else if (IsReturnType()) {
+  } else if (TryParseReturnType()) {
     if (!IsIdentifier()) {
       SetPosition(saved_pos);
       return false;
     }
     ConsumeToken();  // Comsume function identifier.
   }
   if (CurrentToken() == Token::kLPAREN) {
     SkipToMatchingParenthesis();
     if ((CurrentToken() == Token::kLBRACE) ||
         (CurrentToken() == Token::kARROW)) {
@@ skipping 10 matching lines @@
 // statement.
 bool Parser::IsForInStatement() {
   const intptr_t saved_pos = token_index_;
   bool result = false;
   if (CurrentToken() == Token::kVAR || CurrentToken() == Token::kFINAL) {
     ConsumeToken();
   }
   if (IsIdentifier()) {
     if (LookaheadToken(1) == Token::kIN) {
       result = true;
-    } else if (IsOptionalType()) {
+    } else if (TryParseOptionalType()) {
       if (IsIdentifier()) {
         ConsumeToken();
       }
       result = (CurrentToken() == Token::kIN);
     }
   }
   SetPosition(saved_pos);
   return result;
 }
 
@@ skipping 959 matching lines @@
   if (target->FunctionLevel() != current_block_->scope->function_level()) {
     ErrorMsg(jump_pos, "'%s' target must be in same function context",
              Token::Str(jump_kind));
   }
   return new JumpNode(jump_pos, jump_kind, target);
 }
 
 
 bool Parser::IsDefinedInLexicalScope(const String& ident) {
   AstNode* var_or_field = NULL;
   if (ResolveIdentInLocalScope(token_index_, ident, &var_or_field)) {

[siva, 2012/01/23 18:11:38]

Since we now take NULL as a param maybe this can be NULL

[regis, 2012/01/23 19:56:23]

Done.

     return true;
   }
   Object& obj = Object::Handle();
   obj = library_.LookupObject(ident);
   return !obj.IsNull();
 }
 
 
 AstNode* Parser::ParseStatement() {
   TRACE_PARSER("ParseStatement");
@@ skipping 1347 matching lines @@
   return instance.raw();
 }
 
 
 // Do a lookup for the identifier in the block scope and the class scope
 // return true if the identifier is found, false otherwise.
 // If node is non NULL return an AST node corresponding to the identifier.
 bool Parser::ResolveIdentInLocalScope(intptr_t ident_pos,
                                       const String &ident,
                                       AstNode** node) {
-  ASSERT(node != NULL);
   TRACE_PARSER("ResolveIdentInLocalScope");
   Isolate* isolate = Isolate::Current();
   // First try to find the identifier in the nested local scopes.
   LocalVariable* local = LookupLocalScope(ident);
   if (local != NULL) {
-    *node = new LoadLocalNode(ident_pos, *local);
+    if (node != NULL) {
+      *node = new LoadLocalNode(ident_pos, *local);
+    }
     return true;
   }
 
   // Try to find the identifier in the class scope.
   Class& cls = Class::Handle(isolate, current_class().raw());
   Function& func = Function::Handle(isolate, Function::null());
   Field& field = Field::Handle(isolate, Field::null());
   while (!cls.IsNull()) {
     // First check if a field exists.
     field = cls.LookupField(ident);
     if (!field.IsNull()) {
-      if (!field.is_static()) {
-        CheckInstanceFieldAccess(ident_pos, ident);
-        *node = CallGetter(ident_pos, LoadReceiver(ident_pos), ident);
-      } else {
-        *node = GenerateStaticFieldLookup(field, ident_pos);
+      if (node != NULL) {
+        if (!field.is_static()) {
+          CheckInstanceFieldAccess(ident_pos, ident);
+          *node = CallGetter(ident_pos, LoadReceiver(ident_pos), ident);
+        } else {
+          *node = GenerateStaticFieldLookup(field, ident_pos);
+        }
       }
       return true;
     }
 
     // Check if an instance/static function exists.
     func = cls.LookupFunction(ident);
     if (!func.IsNull() &&
         (func.IsDynamicFunction() || func.IsStaticFunction())) {
-      *node = new PrimaryNode(ident_pos,
-                              Function::ZoneHandle(isolate, func.raw()));
+      if (node != NULL) {
+        *node = new PrimaryNode(ident_pos,
+                                Function::ZoneHandle(isolate, func.raw()));
+      }
       return true;
     }
 
     // Now check if a getter/setter method exists for it in which case
     // it is still a field.
     func = cls.LookupGetterFunction(ident);
     if (!func.IsNull()) {
       if (func.IsDynamicFunction()) {
         CheckInstanceFieldAccess(ident_pos, ident);
         ASSERT(AbstractType::Handle(func.result_type()).IsResolved());

[siva, 2012/01/23 18:11:38]

The CheckInstance and ASSERT could also be inside the
conditional (if (node != NULL))?

[regis, 2012/01/23 19:56:23]

Done.

-        *node = CallGetter(ident_pos, LoadReceiver(ident_pos), ident);
+        if (node != NULL) {
+          *node = CallGetter(ident_pos, LoadReceiver(ident_pos), ident);
+        }
         return true;
       } else if (func.IsStaticFunction()) {
         ASSERT(AbstractType::Handle(func.result_type()).IsResolved());

[regis, 2012/01/23 19:56:23]

Done here too.

-        *node = new StaticGetterNode(ident_pos,
-                                     Class::ZoneHandle(isolate, cls.raw()),
-                                     ident);
+        if (node != NULL) {
+          *node = new StaticGetterNode(ident_pos,
+                                       Class::ZoneHandle(isolate, cls.raw()),
+                                       ident);
+        }
         return true;
       }
     }
     func = cls.LookupSetterFunction(ident);
     if (!func.IsNull()) {
       if (func.IsDynamicFunction()) {
-        // We create a getter node even though a getter doesn't exist as
-        // it could be followed by an assignment which will convert it to
-        // a setter node. If there is no assignment we will get an error
-        // when we try to invoke the getter.
-        CheckInstanceFieldAccess(ident_pos, ident);
-        ASSERT(AbstractType::Handle(func.result_type()).IsResolved());
-        *node = CallGetter(ident_pos, LoadReceiver(ident_pos), ident);
+        if (node != NULL) {
+          // We create a getter node even though a getter doesn't exist as
+          // it could be followed by an assignment which will convert it to
+          // a setter node. If there is no assignment we will get an error
+          // when we try to invoke the getter.
+          CheckInstanceFieldAccess(ident_pos, ident);
+          ASSERT(AbstractType::Handle(func.result_type()).IsResolved());
+          *node = CallGetter(ident_pos, LoadReceiver(ident_pos), ident);
+        }
         return true;
       } else if (func.IsStaticFunction()) {
-        // We create a getter node even though a getter doesn't exist as
-        // it could be followed by an assignment which will convert it to
-        // a setter node. If there is no assignment we will get an error
-        // when we try to invoke the getter.
-        *node = new StaticGetterNode(ident_pos,
-                                     Class::ZoneHandle(isolate, cls.raw()),
-                                     ident);
+        if (node != NULL) {
+          // We create a getter node even though a getter doesn't exist as
+          // it could be followed by an assignment which will convert it to
+          // a setter node. If there is no assignment we will get an error
+          // when we try to invoke the getter.
+          *node = new StaticGetterNode(ident_pos,
+                                       Class::ZoneHandle(isolate, cls.raw()),
+                                       ident);
+        }
         return true;
       }
     }
 
     cls = cls.SuperClass();
   }
-  *node = NULL;
+  if (node != NULL) {
+    *node = NULL;
+  }
   return false;  // Not an unqualified identifier.
 }
 
 
 // Do a lookup for the identifier in the library scope of the specified
 // library. If resolve_locally is true the lookup does not consider
 // the libraries imported by it for the lookup.
 AstNode* Parser::ResolveIdentInLibraryScope(const Library& lib,
                                             const QualIdent& qual_ident,
                                             bool resolve_locally) {
@@ skipping 122 matching lines @@
 RawAbstractType* Parser::ParseType(TypeResolution type_resolution) {
   if (CurrentToken() != Token::kIDENT) {
     ErrorMsg("type name expected");
   }
   QualIdent type_name;
   const intptr_t type_pos = token_index_;
   if (type_resolution == kIgnore) {
     SkipQualIdent();
   } else {
     ParseQualIdent(&type_name);
-    if (type_name.is_local_scope_ident) {
+    if (!is_top_level_ && (type_name.qualifier == NULL) &&
+        ResolveIdentInLocalScope(type_pos, *(type_name.ident), NULL)) {

[siva, 2012/01/23 18:11:38]

Should we be reporting this as an error?

[hausner, 2012/01/23 18:31:24]

The parens around type_name.ident seem weird.

[regis, 2012/01/23 19:56:23]

They were sometimes added, sometimes not. I now removed them at every location I
could find them.

[regis, 2012/01/23 19:56:23]

Yes, we have to. The fact that the qualident is declared in the local scope
indicates that it is not a type as expected.

       ErrorMsg(type_pos, "using '%s' in this context is invalid",
                type_name.ident->ToCString());
     }
   }
   Class& scope_class = Class::Handle();
   Object& type_class = Object::Handle();
   if (type_resolution == kIgnore) {
     // Leave type_class as null.
   } else if (type_resolution == kDoNotResolve) {
     String& qualifier = String::Handle();
@@ skipping 460 matching lines @@
 
   // The grammar allows for an optional ('.' identifier)?, which is a named
   // constructor. For that reason, we cannot unconditionally call
   // ParseType(kMustResolve) after we see an identifier, because the named
   // constructor would be misinterpreted as a qualified type name.
   // TODO(regis): Revisit once we correctly support qualified identifiers.
   // For now, we inline a customized version of ParseType(kMustResolve).
   const intptr_t  type_pos = token_index_;
   QualIdent type_name;
   ParseQualIdent(&type_name);
-  if (type_name.is_local_scope_ident) {
+  ASSERT(!is_top_level_);

[hausner, 2012/01/23 18:31:24]

Not sure whether you can assert this here. What if we parse code that contains a
"new List()" statement in the initializer of a top-level variable? While that is
not valid Dart code, it should not crash the compiler.

[regis, 2012/01/23 19:56:23]

As discussed, we already have top level initializers using const parsed by this
code. ParseNewOperator() is only called from ParsePrimary(), in which I added an
ASSERT(!is_top_level_);

+  if ((type_name.qualifier == NULL) &&
+      ResolveIdentInLocalScope(type_pos, *(type_name.ident), NULL)) {

[siva, 2012/01/23 18:11:38]

In the cases where current token is "." and the qualifying token is not a
library prefix we end up calling ResolveIdentInLocalScope twice.

[regis, 2012/01/23 19:56:23]

Consider this example calling a named constructor:

  var Test;
  var i = new Test.named(10);  // This should be an error.

ParseQualIdent will stop parsing at the period, because Test is a local ident,
but not a prefix. Although we see a period, we have to repeat the test to report
the error.

To make the code more efficient and robust, we would need to   remember one of 3
possible states: unchecked, local, non-local. After submitting this cl, I'll
measure if it is worth it or not.

     ErrorMsg(type_pos, "using '%s' in this context is invalid",
              type_name.ident->ToCString());
   }
   String* named_constructor = NULL;
   if (CurrentToken() == Token::kPERIOD) {
     ConsumeToken();
     named_constructor = ExpectIdentifier("identifier expected after '.'");
   }
   const Class& scope_class = Class::Handle(TypeParametersScopeClass());
   if (!scope_class.IsNull()) {
@@ skipping 230 matching lines @@
   AstNode* primary = NULL;
   if (IsFunctionLiteral()) {
     // The name of a literal function is visible from inside the function, but
     // must not collide with names in the scope declaring the literal.
     OpenBlock();
     primary = ParseFunctionStatement(true);
     CloseBlock();
   } else if (IsIdentifier()) {
     QualIdent qual_ident;
     ParseQualIdent(&qual_ident);
-    if (qual_ident.is_local_scope_ident) {
-      ResolveIdentInLocalScope(qual_ident.ident_pos,
-                               *qual_ident.ident,
-                               &primary);
-    } else {
-      if (qual_ident.qualifier == NULL) {
-        // This is an unqualified identifier so resolve the identifier
+    if (qual_ident.qualifier == NULL) {
+      if (!ResolveIdentInLocalScope(qual_ident.ident_pos,
+                                    *(qual_ident.ident),

[hausner, 2012/01/23 18:31:24]

The parens are unnecessary.

[regis, 2012/01/23 19:56:23]

Done.

+                                    &primary)) {
+        // This is a non-local unqualified identifier so resolve the identifier
         // locally in the main app library and all libraries imported by it.
         primary = ResolveIdentInLibraryScope(library_,
                                              qual_ident,
                                              kResolveIncludingImports);
-      } else {
-        // This is a qualified identifier with a library prefix so resolve
-        // the identifier locally in that library (we do not include the
-        // libraries imported by that library).
-        const Library& lib = Library::Handle(qual_ident.lib_prefix->library());
-        primary = ResolveIdentInLibraryScope(lib,
-                                             qual_ident,
-                                             kResolveLocally);
       }
+    } else {
+      // This is a qualified identifier with a library prefix so resolve
+      // the identifier locally in that library (we do not include the
+      // libraries imported by that library).
+      const Library& lib = Library::Handle(qual_ident.lib_prefix->library());
+      primary = ResolveIdentInLibraryScope(lib,
+                                           qual_ident,
+                                           kResolveLocally);
     }
     ASSERT(primary != NULL);
   } else if (CurrentToken() == Token::kTHIS) {
     const String& this_name = String::Handle(String::NewSymbol(kThisName));
     LocalVariable* local = LookupLocalScope(this_name);
     if (local == NULL) {
       ErrorMsg("unexpected use of 'this' in primary expression");
     }
     primary = new LoadLocalNode(token_index_, *local);
     ConsumeToken();
@@ skipping 347 matching lines @@
 void Parser::SkipQualIdent() {
   ASSERT(IsIdentifier());
   ConsumeToken();
   if (CurrentToken() == Token::kPERIOD) {
     ConsumeToken();  // Consume the kPERIOD token.
     ExpectIdentifier("identifier expected after '.'");
   }
 }
 
 }  // namespace dart