code review 1740045: factor common prefixes from alternations

re2/compile.cc

 // Copyright 2007 The RE2 Authors.  All Rights Reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // Compile regular expression to Prog.
 //
 // Prog and Inst are defined in prog.h.
 // This file's external interface is just Regexp::CompileToProg.
 // The Compiler class defined in this file is private.
 
@@ skipping 75 matching lines @@
 
   PatchList l = l1;
   for (;;) {
     PatchList next = PatchList::Deref(inst0, l);
     if (next.p == 0)
       break;
     l = next;
   }
 
   Prog::Inst* ip = &inst0[l.p>>1];
-  if(l.p&1)
+  if (l.p&1)
     ip->out1_ = l2.p;
   else
     ip->set_out(l2.p);
 
   return l1;
 }
 
 // Compiled program fragment.
 struct Frag {
   uint32 begin;
@@ skipping 18 matching lines @@
 
   // Compiles Regexp to a new Prog.
   // Caller is responsible for deleting Prog when finished with it.
   // If reversed is true, compiles for walking over the input
   // string backward (reverses all concatenations).
   static Prog *Compile(Regexp* re, bool reversed, int64 max_mem);
 
   // Compiles alternation of all the re to a new Prog.
   // Each re has a match with an id equal to its index in the vector.
   static Prog* CompileSet(const RE2::Options& options, RE2::Anchor anchor,
-                          const vector<Regexp*>& re);
+                          Regexp* re);
 
   // Interface for Regexp::Walker, which helps traverse the Regexp.
   // The walk is purely post-recursive: given the machines for the
   // children, PostVisit combines them to create the machine for
   // the current node.  The child_args are Frags.
   // The Compiler traverses the Regexp parse tree, visiting
   // each node in depth-first order.  It invokes PreVisit before
   // visiting the node's children and PostVisit after visiting
   // the children.
   Frag PreVisit(Regexp* re, Frag parent_arg, bool* stop);
@@ skipping 54 matching lines @@
 
   // Adds a suffix to alternation.
   void AddSuffix(int id);
 
   // Returns the alternation of all the added suffixes.
   Frag EndRange();
 
   // Single rune.
   Frag Literal(Rune r, bool foldcase);
 
-  void Setup(Regexp::ParseFlags, int64);
+  void Setup(Regexp::ParseFlags, int64, RE2::Anchor);
   Prog* Finish();
 
   // Returns .* where dot = any byte
   Frag DotStar();
 
  private:
   Prog* prog_;         // Program being built.
   bool failed_;        // Did we give up compiling?
   Encoding encoding_;  // Input encoding
   bool reversed_;      // Should program run backward over text?
 
   int max_inst_;       // Maximum number of instructions.
 
   Prog::Inst* inst_;   // Pointer to first instruction.
   int inst_len_;       // Number of instructions used.
   int inst_cap_;       // Number of instructions allocated.
 
   int64 max_mem_;      // Total memory budget.
 
   map<uint64, int> rune_cache_;
   Frag rune_range_;
 
+  RE2::Anchor anchor_;  // anchor mode for RE2::Set
+
   DISALLOW_EVIL_CONSTRUCTORS(Compiler);
 };
 
 Compiler::Compiler() {
   prog_ = new Prog();
   failed_ = false;
   encoding_ = kEncodingUTF8;
   reversed_ = false;
   inst_ = NULL;
   inst_len_ = 0;
@@ skipping 228 matching lines @@
 // The Frag accumulates in rune_range_.  Caching common
 // suffixes reduces the UTF-8 "." from 32 to 24 instructions,
 // and it reduces the corresponding one-pass NFA from 16 nodes to 8.
 
 void Compiler::BeginRange() {
   rune_cache_.clear();
   rune_range_.begin = NULL;
   rune_range_.end = nullPatchList;
 }
 
-int Compiler::UncachedRuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, int next) {
+int Compiler::UncachedRuneByteSuffix(uint8 lo, uint8 hi, bool foldcase,
+                                     int next) {
   Frag f = ByteRange(lo, hi, foldcase);
   if (next != 0) {
     PatchList::Patch(inst_, f.end, next);
   } else {
     rune_range_.end = PatchList::Append(inst_, rune_range_.end, f.end);
   }
   return f.begin;
 }
 
 int Compiler::RuneByteSuffix(uint8 lo, uint8 hi, bool foldcase, int next) {
   // In Latin1 mode, there's no point in caching.
   // In forward UTF-8 mode, only need to cache continuation bytes.
   if (encoding_ == kEncodingLatin1 ||
-      (encoding_ == kEncodingUTF8 && !reversed_ && !(0x80 <= lo && hi <= 0xbf))) {
+      (encoding_ == kEncodingUTF8 &&
+       !reversed_ &&
+       !(0x80 <= lo && hi <= 0xbf))) {
     return UncachedRuneByteSuffix(lo, hi, foldcase, next);
   }
 
   uint64 key = ((uint64)next << 17) | (lo<<9) | (hi<<1) | foldcase;
   map<uint64, int>::iterator it = rune_cache_.find(key);
   if (it != rune_cache_.end())
     return it->second;
   int id = UncachedRuneByteSuffix(lo, hi, foldcase, next);
   rune_cache_[key] = id;
   return id;
@@ skipping 210 matching lines @@
     case kRegexpRepeat:
       // Should not see; code at bottom of function will print error
       break;
 
     case kRegexpNoMatch:
       return NoMatch();
 
     case kRegexpEmptyMatch:
       return Nop();
 
+    case kRegexpHaveMatch: {
+      Frag f = Match(re->match_id());
+      // Remember unanchored match to end of string.
+      if (anchor_ != RE2::ANCHOR_BOTH)
+        f = Cat(DotStar(), f);
+      return f;
+    }
+
     case kRegexpConcat: {
       Frag f = child_frags[0];
       for (int i = 1; i < nchild_frags; i++)
         f = Cat(f, child_frags[i]);
       return f;
     }
 
     case kRegexpAlternate: {
       Frag f = child_frags[0];
       for (int i = 1; i < nchild_frags; i++)
@@ skipping 153 matching lines @@
         continue;
       case kRegexpEndText:
         *pre = Regexp::LiteralString(NULL, 0, re->parse_flags());
         re->Decref();
         return true;
     }
     return false;
   }
 }
 
-void Compiler::Setup(Regexp::ParseFlags flags, int64 max_mem) {
+void Compiler::Setup(Regexp::ParseFlags flags, int64 max_mem,
+                     RE2::Anchor anchor) {
   prog_->set_flags(flags);
 
   if (flags & Regexp::Latin1)
     encoding_ = kEncodingLatin1;
   max_mem_ = max_mem;
   if (max_mem <= 0) {
     max_inst_ = 100000;  // more than enough
   } else if (max_mem <= sizeof(Prog)) {
     // No room for anything.
     max_inst_ = 0;
   } else {
     int64 m = (max_mem - sizeof(Prog)) / sizeof(Prog::Inst);
     // Limit instruction count so that inst->id() fits nicely in an int.
     // SparseArray also assumes that the indices (inst->id()) are ints.
     // The call to WalkExponential uses 2*max_inst_ below,
     // and other places in the code use 2 or 3 * prog->size().
     // Limiting to 2^24 should avoid overflow in those places.
     // (The point of allowing more than 32 bits of memory is to
     // have plenty of room for the DFA states, not to use it up
     // on the program.)
     if (m >= 1<<24)
       m = 1<<24;
 
     // Inst imposes its own limit (currently bigger than 2^24 but be safe).
     if (m > Prog::Inst::kMaxInst)
       m = Prog::Inst::kMaxInst;
 
     max_inst_ = m;
   }
+
+  anchor_ = anchor;
 }
 
 // Compiles re, returning program.
 // Caller is responsible for deleting prog_.
 // If reversed is true, compiles a program that expects
 // to run over the input string backward (reverses all concatenations).
 // The reversed flag is also recorded in the returned program.
 Prog* Compiler::Compile(Regexp* re, bool reversed, int64 max_mem) {
   Compiler c;
 
-  c.Setup(re->parse_flags(), max_mem);
+  c.Setup(re->parse_flags(), max_mem, RE2::ANCHOR_BOTH /* unused */);
   c.reversed_ = reversed;
 
   // Simplify to remove things like counted repetitions
   // and character classes like \d.
   Regexp* sre = re->Simplify();
   if (sre == NULL)
     return NULL;
 
   // Record whether prog is anchored, removing the anchors.
   // (They get in the way of other optimizations.)
@@ skipping 78 matching lines @@
 Prog* Regexp::CompileToReverseProg(int64 max_mem) {
   return Compiler::Compile(this, true, max_mem);
 }
 
 Frag Compiler::DotStar() {
   return Star(ByteRange(0x00, 0xff, false), true);
 }
 
 // Compiles RE set to Prog.
 Prog* Compiler::CompileSet(const RE2::Options& options, RE2::Anchor anchor,
-                           const vector<Regexp*>& re) {
+                           Regexp* re) {
   Compiler c;
 
-  c.Setup(static_cast<Regexp::ParseFlags>(options.ParseFlags()),
-          options.max_mem());
+  Regexp::ParseFlags pf = static_cast<Regexp::ParseFlags>(options.ParseFlags());
+  c.Setup(pf, options.max_mem(), anchor);
 
-  // Accumulate alternation of fragments.
-  Frag all = kNullFrag;
-  for (int i = 0; i < re.size(); i++) {
-    Frag f = c.WalkExponential(re[i], kNullFrag, 2*c.max_inst_);
-    if (c.failed_)
-      return NULL;
-    switch (anchor) {
-      case RE2::UNANCHORED:
-        f = c.Cat(c.Cat(c.DotStar(), f), c.DotStar());
-        break;
-      case RE2::ANCHOR_START:
-        f = c.Cat(f, c.DotStar());
-        break;
-      case RE2::ANCHOR_BOTH:
-        break;
-    }
-    f = c.Cat(f, c.Match(i));
-    all = c.Alt(all, f);
+  // Compile alternation of fragments.
+  Frag all = c.WalkExponential(re, kNullFrag, 2*c.max_inst_);
+  re->Decref();
+  if (c.failed_)
+    return NULL;
+
+  if (anchor == RE2::UNANCHORED) {
+    // The trailing .* was added while handling kRegexpHaveMatch.
+    // We just have to add the leading one.
+    all = c.Cat(c.DotStar(), all);
   }
 
   c.prog_->set_start(all.begin);
   c.prog_->set_start_unanchored(all.begin);
   c.prog_->set_anchor_start(true);
   c.prog_->set_anchor_end(true);
 
-  // Also create unanchored version, which starts with a .*? loop.
-  if (c.prog_->anchor_start()) {
-    c.prog_->set_start_unanchored(c.prog_->start());
-  } else {
-    Frag unanchored = c.Cat(c.DotStar(), all);
-    c.prog_->set_start_unanchored(unanchored.begin);
-  }
-
   Prog* prog = c.Finish();
   if (prog == NULL)
     return NULL;
 
   // Make sure DFA has enough memory to operate,
   // since we're not going to fall back to the NFA.
   bool failed;
   StringPiece sp = "hello, world";
   prog->SearchDFA(sp, sp, Prog::kAnchored, Prog::kManyMatch,
                   NULL, &failed, NULL);
   if (failed) {
     delete prog;
     return NULL;
   }
 
   return prog;
 }
 
 Prog* Prog::CompileSet(const RE2::Options& options, RE2::Anchor anchor,
-                       const vector<Regexp*>& re) {
+                       Regexp* re) {
   return Compiler::CompileSet(options, anchor, re);
 }
 
 }  // namespace re2