Introduce text nodes

src/parser.cc

Index: src/parser.cc
diff --git a/src/parser.cc b/src/parser.cc
index 82d0370a97b9c7e44d3d176b63f9b903db40abca..820b9ba3a2de9f7b99212f27f3c88212632e1248 100644
--- a/src/parser.cc
+++ b/src/parser.cc
@@ -256,10 +256,28 @@ class BufferedZoneList {
   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;
@@ -294,17 +312,19 @@ class RegExpBuilder {
   // "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_;
@@ -328,12 +348,29 @@ void RegExpBuilder::FlushCharacters() {
   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) {
@@ -349,15 +386,20 @@ void RegExpBuilder::AddEmpty() {
 }
 
 
-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);
 }
@@ -371,7 +413,7 @@ void RegExpBuilder::NewAlternative() {
 
 
 bool RegExpBuilder::FlushTerms() {
-  FlushCharacters();
+  FlushText();
   int num_terms = terms_.length();
   if (num_terms == 0) {
     return false;
@@ -415,11 +457,16 @@ void RegExpBuilder::AddQuantifierToAtom(int min, int max, bool is_greedy) {
     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();
@@ -3585,17 +3632,17 @@ RegExpTree* RegExpParser::ParseDisjunction(bool* ok) {
       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 ::
@@ -3625,7 +3672,7 @@ RegExpTree* RegExpParser::ParseDisjunction(bool* ok) {
         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':
@@ -3639,7 +3686,7 @@ RegExpTree* RegExpParser::ParseDisjunction(bool* ok) {
             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();