Introduce text nodes

Replaced atom and character class nodes by text nodes that contain a
sequence of each.

[Erik Corry, 2008-11-14 21:42:55]

LGTM

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

LGTM, with comments.
Primarily looked at parser.cc

http://codereview.chromium.org/10759/diff/14/206
File src/parser.cc (right):

http://codereview.chromium.org/10759/diff/14/206#newcode260
Line 260: last_ = list_->RemoveLast();
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?

http://codereview.chromium.org/10759/diff/14/206#newcode315
Line 315: void AddTerm(RegExpTree* tree);
I would prefer if this is still called AddAtom (see below).

http://codereview.chromium.org/10759/diff/14/206#newcode368
Line 368: terms_.Add(text);
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)?

http://codereview.chromium.org/10759/diff/14/206#newcode389
Line 389: void RegExpBuilder::AddTerm(RegExpTree* term) {
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).

http://codereview.chromium.org/10759/diff/14/206#newcode467
Line 467: ASSERT(last_added_ == ADD_ATOM);
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]

http://codereview.chromium.org/10759/diff/14/206
File src/parser.cc (right):

http://codereview.chromium.org/10759/diff/14/206#newcode260
Line 260: last_ = list_->RemoveLast();
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.

http://codereview.chromium.org/10759/diff/14/206#newcode315
Line 315: void AddTerm(RegExpTree* tree);
You're right -- I've been using the term 'atom' incorrectly as meaning flat
character sequences.  I'll fix that.

http://codereview.chromium.org/10759/diff/14/206#newcode368
Line 368: terms_.Add(text);
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.

http://codereview.chromium.org/10759/diff/14/206#newcode389
Line 389: void RegExpBuilder::AddTerm(RegExpTree* term) {
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.

http://codereview.chromium.org/10759/diff/14/206#newcode467
Line 467: ASSERT(last_added_ == ADD_ATOM);
What about "foo (?:bar) baz"?

[Lasse Reichstein, 2008-11-16 10:53:14]

http://codereview.chromium.org/10759/diff/14/206
File src/parser.cc (right):

http://codereview.chromium.org/10759/diff/14/206#newcode260
Line 260: last_ = list_->RemoveLast();
Ah, so there was a need :)

http://codereview.chromium.org/10759/diff/14/206#newcode368
Line 368: terms_.Add(text);
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.

http://codereview.chromium.org/10759/diff/14/206#newcode389
Line 389: void RegExpBuilder::AddTerm(RegExpTree* term) {
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.

http://codereview.chromium.org/10759/diff/14/206#newcode467
Line 467: ASSERT(last_added_ == ADD_ATOM);
Indeed. It would have to be ADD_TEXT to capture that.

http://codereview.chromium.org/10759/diff/14/206#newcode3640
Line 3640: builder.AddTerm(atom);
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 :(