Fix bug in RegExp first-character-lookahead.

src/jsregexp.cc

 // Copyright 2006-2009 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 4969 matching lines @@
         break;
       }
       case AT_START:
       case AT_BOUNDARY:
       case AT_NON_BOUNDARY:
       case AFTER_NEWLINE:
       case AFTER_NONWORD_CHARACTER:
       case AFTER_WORD_CHARACTER: {
         ASSERT_NOT_NULL(on_success());
         budget = on_success()->ComputeFirstCharacterSet(budget);
-        set_first_character_set(on_success()->first_character_set());
+        if (budget >= 0) {
+          set_first_character_set(on_success()->first_character_set());
+        }
         break;
       }
     }
   }
   return budget;
 }
 
 
 int ActionNode::ComputeFirstCharacterSet(int budget) {
   if (type_ == POSITIVE_SUBMATCH_SUCCESS) return kComputeFirstCharacterSetFail;
   budget--;
   if (budget >= 0) {
     ASSERT_NOT_NULL(on_success());
     budget = on_success()->ComputeFirstCharacterSet(budget);
     if (budget >= 0) {
       set_first_character_set(on_success()->first_character_set());
     }
   }
   return budget;
 }
 
 
 int BackReferenceNode::ComputeFirstCharacterSet(int budget) {
   // We don't know anything about the first character of a backreference
   // at this point.
+  // The potential first characters are the first characters of the capture,
+  // and the first characters of the on_success node, depending on whether the
+  // capture can be empty and whether it is known to be participating or known
+  // not to be.
   return kComputeFirstCharacterSetFail;
 }
 
 
 int TextNode::ComputeFirstCharacterSet(int budget) {
   budget--;
   if (budget >= 0) {
     ASSERT_NE(0, elements()->length());
     TextElement text = elements()->at(0);
     if (text.type == TextElement::ATOM) {
       RegExpAtom* atom = text.data.u_atom;
       ASSERT_NE(0, atom->length());
       uc16 first_char = atom->data()[0];
       ZoneList<CharacterRange>* range = new ZoneList<CharacterRange>(1);
       range->Add(CharacterRange(first_char, first_char));
       set_first_character_set(range);
     } else {
       ASSERT(text.type == TextElement::CHAR_CLASS);
       RegExpCharacterClass* char_class = text.data.u_char_class;
+      ZoneList<CharacterRange>* ranges = char_class->ranges();
+      CharacterRange::Canonicalize(ranges);
       if (char_class->is_negated()) {
-        ZoneList<CharacterRange>* ranges = char_class->ranges();
         int length = ranges->length();
         int new_length = length + 1;
         if (length > 0) {
           if (ranges->at(0).from() == 0) new_length--;
           if (ranges->at(length - 1).to() == String::kMaxUC16CharCode) {
             new_length--;
           }
         }
         ZoneList<CharacterRange>* negated_ranges =
             new ZoneList<CharacterRange>(new_length);
         CharacterRange::Negate(ranges, negated_ranges);
         set_first_character_set(negated_ranges);
       } else {
-        set_first_character_set(char_class->ranges());
+        // TODO(lrn): Canonicalize ranges when they are created
+        // instead of waiting until now.
+        set_first_character_set(ranges);
       }
     }
   }
   return budget;
 }
 
 
 
 // -------------------------------------------------------------------
 // Dispatch table construction
@@ skipping 185 matching lines @@
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 int OffsetsVector::static_offsets_vector_[
     OffsetsVector::kStaticOffsetsVectorSize];
 
 }}  // namespace v8::internal