Uniqueify out sets.

src/jsregexp.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 718 matching lines @@
  private:
   RegExpNode* on_failure_;
   int start_reg_;
   int end_reg_;
 };
 
 
 class CharacterClassNode: public SeqRegExpNode {
  public:
   CharacterClassNode(ZoneList<CharacterRange>* ranges,
+                     bool is_negated,
                      RegExpNode* on_success,
                      RegExpNode* on_failure)
     : SeqRegExpNode(on_success),
       on_failure_(on_failure),
-      ranges_(ranges) { }
+      ranges_(ranges),
+      is_negated_(is_negated ){ }
   virtual void Accept(NodeVisitor* visitor);
   ZoneList<CharacterRange>* ranges() { return ranges_; }
+  bool is_negated() { return is_negated_; }
   RegExpNode* on_failure() { return on_failure_; }
+  static void AddInverseToTable(List<CharacterRange> ranges,
+                                DispatchTable* table,
+                                int index);
  private:
   RegExpNode* on_failure_;
   ZoneList<CharacterRange>* ranges_;
+  bool is_negated_;
 };
 
 
 class Guard: public ZoneObject {
  public:
   enum Relation { LT, GEQ };
   Guard(int reg, Relation op, int value)
     : reg_(reg),
       op_(op),
       value_(value) { }
@@ skipping 320 matching lines @@
   DispatchTableDumper(StringStream* stream) : stream_(stream) { }
   void Call(uc16 key, DispatchTable::Entry entry);
   StringStream* stream() { return stream_; }
  private:
   StringStream* stream_;
 };
 
 
 void DispatchTableDumper::Call(uc16 key, DispatchTable::Entry entry) {
   stream()->Add("[%k-%k]: {", key, entry.to());
-  OutSet set = entry.out_set();
+  OutSet* set = entry.out_set();
   bool first = true;
   for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
-    if (set.Get(i)) {
+    if (set->Get(i)) {
       if (first) first = false;
       else stream()->Add(", ");
       stream()->Add("%i", i);
     }
   }
   stream()->Add("}\n");
 }
 
 
 void DispatchTable::Dump() {
@@ skipping 20 matching lines @@
 RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success,
                                RegExpNode* on_failure) {
   return new AtomNode(data(), on_success, on_failure);
 }
 
 
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success,
                                          RegExpNode* on_failure) {
-  return new CharacterClassNode(ranges(), on_success, on_failure);
+  return new CharacterClassNode(ranges(),
+                                is_negated(),
+                                on_success,
+                                on_failure);
 }
 
 
 RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success,
                                       RegExpNode* on_failure) {
   ZoneList<RegExpTree*>* children = nodes();
   int length = children->length();
   ChoiceNode* result = new ChoiceNode(length, on_failure);
   for (int i = 0; i < length; i++) {
@@ skipping 221 matching lines @@
     default:
       UNREACHABLE();
   }
 }
 
 
 // -------------------------------------------------------------------
 // Splay tree
 
 
+OutSet* OutSet::Extend(unsigned value) {
+  if (Get(value))
+    return this;
+  if (successors() != NULL) {
+    for (int i = 0; i < successors()->length(); i++) {
+      OutSet* successor = successors()->at(i);
+      if (successor->Get(value))
+        return successor;
+    }
+  } else {
+    successors_ = new ZoneList<OutSet*>(2);
+  }
+  OutSet* result = new OutSet(first_, remaining_);
+  result->Set(value);
+  successors()->Add(result);
+  return result;
+}
+
+
 void OutSet::Set(unsigned value) {
   if (value < kFirstLimit) {
     first_ |= (1 << value);
   } else {
     if (remaining_ == NULL)
       remaining_ = new ZoneList<unsigned>(1);
     if (remaining_->is_empty() || !remaining_->Contains(value))
       remaining_->Add(value);
   }
 }
 
 
 bool OutSet::Get(unsigned value) {
   if (value < kFirstLimit) {
     return (first_ & (1 << value)) != 0;
   } else if (remaining_ == NULL) {
     return false;
   } else {
     return remaining_->Contains(value);
   }
 }
 
 
-OutSet OutSet::Clone() {
-  if (remaining_ == NULL) {
-    return OutSet(first_, NULL);
-  } else {
-    int length = remaining_->length();
-    ZoneList<unsigned>* clone = new ZoneList<unsigned>(length);
-    for (int i = 0; i < length; i++)
-      clone->Add(remaining_->at(i));
-    return OutSet(first_, clone);
-  }
-}
-
-
 const uc16 DispatchTable::Config::kNoKey = unibrow::Utf8::kBadChar;
 const DispatchTable::Entry DispatchTable::Config::kNoValue;
 
 
 void DispatchTable::AddRange(CharacterRange full_range, int value) {
   CharacterRange current = full_range;
   if (tree()->is_empty()) {
     // If this is the first range we just insert into the table.
     ZoneSplayTree<Config>::Locator loc;
     ASSERT_RESULT(tree()->Insert(current.from(), &loc));
-    loc.set_value(Entry(current.from(), current.to(), value));
+    loc.set_value(Entry(current.from(), current.to(), empty()->Extend(value)));
     return;
   }
   // First see if there is a range to the left of this one that
   // overlaps.
   ZoneSplayTree<Config>::Locator loc;
   if (tree()->FindGreatestLessThan(current.from(), &loc)) {
     Entry* entry = &loc.value();
     // If we've found a range that overlaps with this one, and it
     // starts strictly to the left of this one, we have to fix it
     // because the following code only handles ranges that start on
     // or after the start point of the range we're adding.
     if (entry->from() < current.from() && entry->to() >= current.from()) {
       // Snap the overlapping range in half around the start point of
       // the range we're adding.
       CharacterRange left(entry->from(), current.from() - 1);
       CharacterRange right(current.from(), entry->to());
       // The left part of the overlapping range doesn't overlap.
       // Truncate the whole entry to be just the left part.
       entry->set_to(left.to());
       // The right part is the one that overlaps.  We add this part
       // to the map and let the next step deal with merging it with
       // the range we're adding.
       ZoneSplayTree<Config>::Locator loc;
       ASSERT_RESULT(tree()->Insert(right.from(), &loc));
       loc.set_value(Entry(right.from(),
                           right.to(),
-                          entry->out_set().Clone()));
+                          entry->out_set()));
     }
   }
   while (current.is_valid()) {
     if (tree()->FindLeastGreaterThan(current.from(), &loc) &&
         (loc.value().from() <= current.to())) {
       Entry* entry = &loc.value();
       // We have overlap.  If there is space between the start point of
       // the range we're adding and where the overlapping range starts
       // then we have to add a range covering just that space.
       if (current.from() < entry->from()) {
         ZoneSplayTree<Config>::Locator ins;
         ASSERT_RESULT(tree()->Insert(current.from(), &ins));
-        ins.set_value(Entry(current.from(), entry->from() - 1, value));
+        ins.set_value(Entry(current.from(),
+                            entry->from() - 1,
+                            empty()->Extend(value)));
         current.set_from(entry->from());
       }
       ASSERT_EQ(current.from(), entry->from());
       // If the overlapping range extends beyond the one we want to add
       // we have to snap the right part off and add it separately.
       if (entry->to() > current.to()) {
         ZoneSplayTree<Config>::Locator ins;
         ASSERT_RESULT(tree()->Insert(current.to() + 1, &ins));
         ins.set_value(Entry(current.to() + 1,
                             entry->to(),
-                            entry->out_set().Clone()));
+                            entry->out_set()));
         entry->set_to(current.to());
       }
       ASSERT(entry->to() <= current.to());
       // The overlapping range is now completely contained by the range
       // we're adding so we can just update it and move the start point
       // of the range we're adding just past it.
       entry->AddValue(value);
       current.set_from(entry->to() + 1);
     } else {
       // There is no overlap so we can just add the range
       ZoneSplayTree<Config>::Locator ins;
       ASSERT_RESULT(tree()->Insert(current.from(), &ins));
-      ins.set_value(Entry(current.from(), current.to(), value));
+      ins.set_value(Entry(current.from(),
+                          current.to(),
+                          empty()->Extend(value)));
       break;
     }
   }
 }
 
 
-OutSet DispatchTable::Get(uc16 value) {
+OutSet* DispatchTable::Get(uc16 value) {
   ZoneSplayTree<Config>::Locator loc;
   if (!tree()->FindGreatestLessThan(value, &loc))
-    return OutSet::empty();
+    return empty();
   Entry* entry = &loc.value();
   if (value <= entry->to())
     return entry->out_set();
   else
-    return OutSet::empty();
+    return empty();
 }
 
 
 // -------------------------------------------------------------------
 // Analysis
 
 
 class Analysis: public NodeVisitor {
  public:
   Analysis(RegExpCompiler* compiler)
@@ skipping 114 matching lines @@
 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) {
   RegExpCompiler compiler(input->capture_count);
   RegExpNode* node = compiler.Compile(input->tree,
                                       EndNode::GetAccept(),
                                       EndNode::GetBacktrack());
   return node;
 }
 
 
 }}  // namespace v8::internal