Introduce text nodes

src/parser.cc

 // 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
@@ skipping 238 matching lines @@
   }
 
   T* last() {
     ASSERT(last_ != NULL);
     return last_;
   }
 
   T* RemoveLast() {
     ASSERT(last_ != NULL);
     T* result = last_;
-    last_ = NULL;
+    if (list_ != NULL && list_->length() > 0)
+      last_ = list_->RemoveLast();

[Lasse Reichstein, 2008/11/15 23:58:06]

This allows removing more than the last added element from the buffer. Removing
the last element is only a feature to support adding parsed quantifiers after
adding the atom it quantifies. The method (or class for that matter) wasn't
intended to be general purpose.
Is there a current need for this feature?

[Christian Plesner Hansen, 2008/11/16 09:05:06]

Not as such, no, but it's not a good property that using RemoveLast puts the
data structure in a semi-inconsistent state.  What I needed was actually to use
last() after RemoveLast has been used and that didn't work.

[Lasse Reichstein, 2008/11/16 10:53:15]

Ah, so there was a need :)

+    else
+      last_ = NULL;
     return result;
   }
 
+  T* Get(int i) {
+    ASSERT(0 <= i && i < length());
+    if (list_ == NULL) {
+      ASSERT_EQ(0, i);
+      return last_;
+    } else {
+      if (i == list_->length()) {
+        ASSERT(last_ != NULL);
+        return last_;
+      } else {
+        return list_->at(i);
+      }
+    }
+  }
+
   void Clear() {
     list_ = NULL;
     last_ = NULL;
   }
 
   int length() {
     int length = (list_ == NULL) ? 0 : list_->length();
     return length + ((last_ == NULL) ? 0 : 1);
   }
 
@@ skipping 14 matching lines @@
 };
 
 // Accumulates RegExp atoms and assertions into lists of terms and alternatives.
 class RegExpBuilder {
  public:
   RegExpBuilder();
   void AddCharacter(uc16 character);
   // "Adds" an empty expression. Does nothing except consume a
   // following quantifier
   void AddEmpty();
-  void AddAtom(RegExpTree* tree);
+  void AddTerm(RegExpTree* tree);

[Lasse Reichstein, 2008/11/15 23:58:06]

I would prefer if this is still called AddAtom (see below).

[Christian Plesner Hansen, 2008/11/16 09:05:06]

You're right -- I've been using the term 'atom' incorrectly as meaning flat
character sequences.  I'll fix that.

   void AddAssertion(RegExpTree* tree);
   void NewAlternative();  // '|'
   void AddQuantifierToAtom(int min, int max, bool is_greedy);
   RegExpTree* ToRegExp();
  private:
   void FlushCharacters();
+  void FlushText();
   bool FlushTerms();
   bool pending_empty_;
   ZoneList<uc16>* characters_;
   BufferedZoneList<RegExpTree, 2> terms_;
+  BufferedZoneList<RegExpTree, 2> text_;
   BufferedZoneList<RegExpTree, 2> alternatives_;
 #ifdef DEBUG
   enum {ADD_NONE, ADD_CHAR, ADD_TERM, ADD_ASSERT, ADD_ATOM} last_added_;
 #define LAST(x) last_added_ = x;
 #else
 #define LAST(x)
 #endif
 };
 
 
 RegExpBuilder::RegExpBuilder()
   : pending_empty_(false), characters_(NULL), terms_(), alternatives_()
 #ifdef DEBUG
   , last_added_(ADD_NONE)
 #endif
   {}
 
 
 void RegExpBuilder::FlushCharacters() {
   pending_empty_ = false;
   if (characters_ != NULL) {
     RegExpTree* atom = new RegExpAtom(characters_->ToConstVector());
     characters_ = NULL;
-    terms_.Add(atom);
+    text_.Add(atom);
     LAST(ADD_ATOM);
   }
 }
 
 
+void RegExpBuilder::FlushText() {
+  FlushCharacters();
+  int num_text = text_.length();
+  if (num_text == 0) {
+    return;
+  } else if (num_text == 1) {
+    terms_.Add(text_.last());
+  } else {
+    RegExpText* text = new RegExpText();
+    for (int i = 0; i < num_text; i++)
+      text_.Get(i)->AppendToText(text);
+    terms_.Add(text);

[Lasse Reichstein, 2008/11/15 23:58:06]

The other places where a buffer is used, the contents are extracted into a
single list, using GetList(). Is there an advantage to building a RegExpText
incrementally instead of passing it a single ZoneList (which already exists)?

[Christian Plesner Hansen, 2008/11/16 09:05:06]

If we're always using GetList anyway then why even use buffered lists?  I'd
rather not use GetList because in the (common) case where there is just one
element if will allocate an unnecessary one-element list.

We only ever need AppendToText for text nodes and passing the text node means
that it doesn't have to expose that it happens to have been implemented using a
list.  I can easily imagine us changing the internal representation, for
instance to avoid allocating a list when there is only one element.

[Lasse Reichstein, 2008/11/16 10:53:15]

The current uses all have special cases for one element, where they just use
last(). If there are more than one element, they use GetList() to get all the
elements as a list, and pass it to the constructors that already happened to
expect a list (RegExpDisjunction, RegExpAlternatives).

RegExpText seems to follow the same pattern: If there is only one element, just
return that, otherwise create a wrapper RegExpText to contain the list of text
elements. If RegExpText had a constructor taking a pointer to a list, it could
choose to use that instead of creating a new list.
However, I can see that adding one RegExpText node to another might want to
flatten the resulting tree, which leads to different requirements.

+  }
+  text_.Clear();
+}
+
+
 void RegExpBuilder::AddCharacter(uc16 c) {
   pending_empty_ = false;
   if (characters_ == NULL) {
     characters_ = new ZoneList<uc16>(4);
   }
   characters_->Add(c);
   LAST(ADD_CHAR);
 }
 
 
 void RegExpBuilder::AddEmpty() {
   pending_empty_ = true;
 }
 
 
-void RegExpBuilder::AddAtom(RegExpTree* atom) {
-  FlushCharacters();
-  terms_.Add(atom);
+void RegExpBuilder::AddTerm(RegExpTree* term) {

[Lasse Reichstein, 2008/11/15 23:58:06]

The original method was called AddAtom to match the grammar productions. An Atom
is something that can be quantified. A Term cannot have a quantifier applied. I
would keep this method called AddAtom, and make another called AddText (to match
AddCharacter) or AddCharacterClass (because that's the only text content that is
added directly and not using AddCharacter).

[Christian Plesner Hansen, 2008/11/16 09:05:06]

You don't always know that you're adding a character class.  Consider "foo
(?:[bar]) baz".  Also, text nodes can themselves be added to other text nodes.

[Lasse Reichstein, 2008/11/16 10:53:15]

I can see the point. If the result of a sub-parse is a single text node, then it
might be recognized as such an added to text_ instead of terms_. So I would use
AddText to add it, and any character classes, together with setting last_ to
ADD_TEXT. 

+  if (term->IsTextElement()) {
+    FlushCharacters();
+    text_.Add(term);
+  } else {
+    FlushText();
+    terms_.Add(term);
+  }
   LAST(ADD_ATOM);
 }
 
 
 void RegExpBuilder::AddAssertion(RegExpTree* assert) {
-  FlushCharacters();
+  FlushText();
   terms_.Add(assert);
   LAST(ADD_ASSERT);
 }
 
 
 void RegExpBuilder::NewAlternative() {
   if (!FlushTerms()) {
     alternatives_.Add(RegExpEmpty::GetInstance());
   }
 }
 
 
 bool RegExpBuilder::FlushTerms() {
-  FlushCharacters();
+  FlushText();
   int num_terms = terms_.length();
   if (num_terms == 0) {
     return false;
   }
   RegExpTree* alternative;
   if (num_terms == 1) {
     alternative = terms_.last();
   } else {
     alternative = new RegExpAlternative(terms_.GetList());
   }
@@ skipping 23 matching lines @@
     return;
   }
   RegExpTree* atom;
   if (characters_ != NULL) {
     ASSERT(last_added_ == ADD_CHAR);
     // Last atom was character.
     Vector<const uc16> char_vector = characters_->ToConstVector();
     int num_chars = char_vector.length();
     if (num_chars > 1) {
       Vector<const uc16> prefix = char_vector.SubVector(0, num_chars - 1);
-      terms_.Add(new RegExpAtom(prefix));
+      text_.Add(new RegExpAtom(prefix));
       char_vector = char_vector.SubVector(num_chars - 1, num_chars);
     }
     characters_ = NULL;
     atom = new RegExpAtom(char_vector);
+    FlushText();
+  } else if (text_.length() > 0) {
+    ASSERT(last_added_ == ADD_ATOM);

[Lasse Reichstein, 2008/11/15 23:58:06]

The last thing added was a character class. 
The last_added property is pure debugging, so it should be as specific as
possible. I would add an ADD_CHAR_CLASS to represent it.

[Christian Plesner Hansen, 2008/11/16 09:05:06]

What about "foo (?:bar) baz"?

[Lasse Reichstein, 2008/11/16 10:53:15]

Indeed. It would have to be ADD_TEXT to capture that.

+    atom = text_.RemoveLast();
+    FlushText();
   } else if (terms_.length() > 0) {
     ASSERT(last_added_ == ADD_ATOM);
     atom = terms_.RemoveLast();
   } else {
     // Only call immediately after adding an atom or character!
     UNREACHABLE();
     return;
   }
   terms_.Add(new RegExpQuantifier(min, max, is_greedy, atom));
   LAST(ADD_TERM);
@@ skipping 3145 matching lines @@
                             RegExpAssertion::END_OF_INPUT;
       builder.AddAssertion(new RegExpAssertion(type));
       continue;
     }
     case '.': {
       Advance();
       // everything except \x0a, \x0d, \u2028 and \u2029
       ZoneList<CharacterRange>* ranges = new ZoneList<CharacterRange>(2);
       CharacterRange::AddClassEscape('.', ranges);
       RegExpTree* atom = new RegExpCharacterClass(ranges, false);
-      builder.AddAtom(atom);
+      builder.AddTerm(atom);
       break;
     }
     case '(': {
       RegExpTree* atom = ParseGroup(CHECK_OK);
-      builder.AddAtom(atom);
+      builder.AddTerm(atom);

[Lasse Reichstein, 2008/11/16 10:53:15]

At this point we could check whether the atom is a text node, and use a
specialized AddText instead if it is.
We can't recognize assertions and use AddAssertion, because (?:\b) is an atom
and can be quantified, even if it's ridiculous :(

       break;
     }
     case '[': {
       RegExpTree* atom = ParseCharacterClass(CHECK_OK);
-      builder.AddAtom(atom);
+      builder.AddTerm(atom);
       break;
     }
     // Atom ::
     //   \ AtomEscape
     case '\\':
       switch (next()) {
       case kEndMarker:
         ReportError(CStrVector("\\ at end of pattern"), CHECK_OK);
       case 'b':
         Advance(2);
         builder.AddAssertion(
             new RegExpAssertion(RegExpAssertion::BOUNDARY));
         continue;
       case 'B':
         Advance(2);
         builder.AddAssertion(
             new RegExpAssertion(RegExpAssertion::NON_BOUNDARY));
         continue;
         // AtomEscape ::
         //   CharacterClassEscape
         //
         // CharacterClassEscape :: one of
         //   d D s S w W
       case 'd': case 'D': case 's': case 'S': case 'w': case 'W': {
         uc32 c = next();
         Advance(2);
         ZoneList<CharacterRange>* ranges = new ZoneList<CharacterRange>(2);
         CharacterRange::AddClassEscape(c, ranges);
         RegExpTree* atom = new RegExpCharacterClass(ranges, false);
-        builder.AddAtom(atom);
+        builder.AddTerm(atom);
         goto has_read_atom;  // Avoid setting has_character_escapes_.
       }
       case '1': case '2': case '3': case '4': case '5': case '6':
       case '7': case '8': case '9': {
         int index = 0;
         if (ParseBackreferenceIndex(&index)) {
           RegExpCapture* capture = captures_->at(index - 1);
           if (capture == NULL || capture->available() != CAPTURE_AVAILABLE) {
             // Prepare to ignore a following quantifier
             builder.AddEmpty();
             goto has_read_atom;
           }
           RegExpTree* atom = new RegExpBackreference(capture);
-          builder.AddAtom(atom);
+          builder.AddTerm(atom);
           goto has_read_atom;  // Avoid setting has_character_escapes_.
         }
         uc32 first_digit = next();
         if (first_digit == '8' || first_digit == '9') {
           // Treat as identity escape
           builder.AddCharacter(first_digit);
           Advance(2);
           break;
         }
       }
@@ skipping 619 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal