Migrate WebRequestRedirectByRegExAction to use RE2 and roll RE2 to revision 97:401ab4168e8e

third_party/re2/re2/dfa.cc

 // Copyright 2008 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.
 
 // A DFA (deterministic finite automaton)-based regular expression search.
 //
 // The DFA search has two main parts: the construction of the automaton,
 // which is represented by a graph of State structures, and the execution
 // of the automaton over a given input string.
 //
@@ skipping 99 matching lines @@
 
   enum {
     kByteEndText = 256,         // imaginary byte at end of text
 
     kFlagEmptyMask = 0xFFF,     // State.flag_: bits holding kEmptyXXX flags
     kFlagMatch = 0x1000,        // State.flag_: this is a matching state
     kFlagLastWord = 0x2000,     // State.flag_: last byte was a word char
     kFlagNeedShift = 16,        // needed kEmpty bits are or'ed in shifted left
   };
 
+#ifndef STL_MSVC
   // STL function structures for use with unordered_set.
   struct StateEqual {
     bool operator()(const State* a, const State* b) const {
       if (a == b)
         return true;
       if (a == NULL || b == NULL)
         return false;
       if (a->ninst_ != b->ninst_)
         return false;
       if (a->flag_ != b->flag_)
         return false;
       for (int i = 0; i < a->ninst_; i++)
         if (a->inst_[i] != b->inst_[i])
           return false;
       return true;  // they're equal
     }
   };
+#endif  // STL_MSVC
   struct StateHash {
     size_t operator()(const State* a) const {
       if (a == NULL)
         return 0;
       const char* s = reinterpret_cast<const char*>(a->inst_);
       int len = a->ninst_ * sizeof a->inst_[0];
       if (sizeof(size_t) == sizeof(uint32))
         return Hash32StringWithSeed(s, len, a->flag_);
       else
         return Hash64StringWithSeed(s, len, a->flag_);
     }
+#ifdef STL_MSVC
+    // Less than operator.
+    bool operator()(const State* a, const State* b) const {
+      if (a == b)
+        return false;
+      if (a == NULL || b == NULL)
+        return a == NULL;
+      if (a->ninst_ != b->ninst_)
+        return a->ninst_ < b->ninst_;
+      if (a->flag_ != b->flag_)
+        return a->flag_ < b->flag_;
+      for (int i = 0; i < a->ninst_; ++i)
+        if (a->inst_[i] != b->inst_[i])
+          return a->inst_[i] < b->inst_[i];
+      return false;  // they're equal
+    }
+    // The two public members are required by msvc. 4 and 8 are default values.
+    // Reference: http://msdn.microsoft.com/en-us/library/1s1byw77.aspx
+    static const size_t bucket_size = 4;
+    static const size_t min_buckets = 8;
+#endif  // STL_MSVC
   };
 
+#ifdef STL_MSVC
+  typedef unordered_set<State*, StateHash> StateSet;
+#else  // !STL_MSVC
   typedef unordered_set<State*, StateHash, StateEqual> StateSet;
+#endif  // STL_MSVC
 
 
  private:
   // Special "firstbyte" values for a state.  (Values >= 0 denote actual bytes.)
   enum {
     kFbUnknown = -1,   // No analysis has been performed.
     kFbMany = -2,      // Many bytes will lead out of this state.
     kFbNone = -3,      // No bytes lead out of this state.
   };
 
@@ skipping 796 matching lines @@
     if (state == NULL) {
       LOG(DFATAL) << "NULL state in RunStateOnByte";
       return NULL;
     }
     LOG(DFATAL) << "Unexpected special state in RunStateOnByte";
     return NULL;
   }
 
   // If someone else already computed this, return it.
   MaybeReadMemoryBarrier(); // On alpha we need to ensure read ordering
-  if (state->next_[ByteMap(c)])
-    return state->next_[ByteMap(c)];
+  State* ns = state->next_[ByteMap(c)];
+  ANNOTATE_HAPPENS_AFTER(ns);
+  if (ns != NULL)
+    return ns;
 
   // Convert state into Workq.
   StateToWorkq(state, q0_);
 
   // Flags marking the kinds of empty-width things (^ $ etc)
   // around this byte.  Before the byte we have the flags recorded
   // in the State structure itself.  After the byte we have
   // nothing yet (but that will change: read on).
   uint needflag = state->flag_ >> kFlagNeedShift;
   uint beforeflag = state->flag_ & kFlagEmptyMask;
@@ skipping 22 matching lines @@
     beforeflag |= kEmptyWordBoundary;
 
   // Okay, finally ready to run.
   // Only useful to rerun on empty string if there are new, useful flags.
   if (beforeflag & ~oldbeforeflag & needflag) {
     RunWorkqOnEmptyString(q0_, q1_, beforeflag);
     swap(q0_, q1_);
   }
   bool ismatch = false;
   RunWorkqOnByte(q0_, q1_, c, afterflag, &ismatch, kind_, start_unanchored_);
-  swap(q0_, q1_);
+  
+  // Most of the time, we build the state from the output of
+  // RunWorkqOnByte, so swap q0_ and q1_ here.  However, so that
+  // RE2::Set can tell exactly which match instructions
+  // contributed to the match, don't swap if c is kByteEndText.
+  // The resulting state wouldn't be correct for further processing
+  // of the string, but we're at the end of the text so that's okay.
+  // Leaving q0_ alone preseves the match instructions that led to
+  // the current setting of ismatch.
+  if (c != kByteEndText || kind_ != Prog::kManyMatch)
+    swap(q0_, q1_);
 
   // Save afterflag along with ismatch and isword in new state.
   uint flag = afterflag;
   if (ismatch)
     flag |= kFlagMatch;
   if (isword)
     flag |= kFlagLastWord;
 
-  State* ns = WorkqToCachedState(q0_, flag);
+  ns = WorkqToCachedState(q0_, flag);
 
   // Write barrier before updating state->next_ so that the
   // main search loop can proceed without any locking, for speed.
   // (Otherwise it would need one mutex operation per input byte.)
   // The annotations below tell race detectors that:
   //   a) the access to next_ should be ignored,
   //   b) 'ns' is properly published.
   WriteMemoryBarrier();  // Flush ns before linking to it.
-  ANNOTATE_PUBLISH_MEMORY_RANGE(ns, sizeof(*ns));
 
   ANNOTATE_IGNORE_WRITES_BEGIN();
+  ANNOTATE_HAPPENS_BEFORE(ns);
   state->next_[ByteMap(c)] = ns;
   ANNOTATE_IGNORE_WRITES_END();
   return ns;
 }
 
 
 //////////////////////////////////////////////////////////////////////
 // DFA cache reset.
 
 // Reader-writer lock helper.
@@ skipping 304 matching lines @@
     // ns == NULL means the state has not yet been computed
     // (need to call RunStateOnByteUnlocked).
     // RunStateOnByte returns ns == NULL if it is out of memory.
     // ns == FullMatchState means the rest of the string matches.
     //
     // Okay to use bytemap[] not ByteMap() here, because
     // c is known to be an actual byte and not kByteEndText.
 
     MaybeReadMemoryBarrier(); // On alpha we need to ensure read ordering
     State* ns = s->next_[bytemap[c]];
+    ANNOTATE_HAPPENS_AFTER(ns);
     if (ns == NULL) {
       ns = RunStateOnByteUnlocked(s, c);
       if (ns == NULL) {
         // After we reset the cache, we hold cache_mutex exclusively,
         // so if resetp != NULL, it means we filled the DFA state
         // cache with this search alone (without any other threads).
         // Benchmarks show that doing a state computation on every
         // byte runs at about 0.2 MB/s, while the NFA (nfa.cc) can do the
         // same at about 2 MB/s.  Unless we're processing an average
         // of 10 bytes per state computation, fail so that RE2 can
@@ skipping 51 matching lines @@
                 static_cast<int>(lastmatch - bp),
                 DumpState(s).c_str());
 
       if (want_earliest_match) {
         params->ep = reinterpret_cast<const char*>(lastmatch);
         return true;
       }
     }
   }
 
-  // Peek in state to see if a match is coming up.
-  if (params->matches && kind_ == Prog::kManyMatch) {
-    vector<int>* v = params->matches;
-    v->clear();
-    if (s > SpecialStateMax) {
-      for (int i = 0; i < s->ninst_; i++) {
-        Prog::Inst* ip = prog_->inst(s->inst_[i]);
-        if (ip->opcode() == kInstMatch)
-          v->push_back(ip->match_id());
-      }
-    }
-  }
-
-
   // Process one more byte to see if it triggers a match.
   // (Remember, matches are delayed one byte.)
   int lastbyte;
   if (run_forward) {
     if (params->text.end() == params->context.end())
       lastbyte = kByteEndText;
     else
       lastbyte = params->text.end()[0] & 0xFF;
   } else {
     if (params->text.begin() == params->context.begin())
       lastbyte = kByteEndText;
     else
       lastbyte = params->text.begin()[-1] & 0xFF;
   }
 
   MaybeReadMemoryBarrier(); // On alpha we need to ensure read ordering
   State* ns = s->next_[ByteMap(lastbyte)];
+  ANNOTATE_HAPPENS_AFTER(ns);
   if (ns == NULL) {
     ns = RunStateOnByteUnlocked(s, lastbyte);
     if (ns == NULL) {
       StateSaver save_s(this, s);
       ResetCache(params->cache_lock);
       if ((s = save_s.Restore()) == NULL) {
         params->failed = true;
         return false;
       }
       ns = RunStateOnByteUnlocked(s, lastbyte);
       if (ns == NULL) {
         LOG(DFATAL) << "RunStateOnByteUnlocked failed after Reset";
         params->failed = true;
         return false;
       }
     }
   }
   s = ns;
   if (DebugDFA)
     fprintf(stderr, "@_: %s\n", DumpState(s).c_str());
   if (s == FullMatchState) {
     params->ep = reinterpret_cast<const char*>(ep);
     return true;
   }
   if (s > SpecialStateMax && s->IsMatch()) {
     matched = true;
     lastmatch = p;
+    if (params->matches && kind_ == Prog::kManyMatch) {
+      vector<int>* v = params->matches;
+      v->clear();
+      for (int i = 0; i < s->ninst_; i++) {
+        Prog::Inst* ip = prog_->inst(s->inst_[i]);
+        if (ip->opcode() == kInstMatch)
+          v->push_back(ip->match_id());
+      }
+    }
     if (DebugDFA)
       fprintf(stderr, "match @%d! [%s]\n", static_cast<int>(lastmatch - bp),
               DumpState(s).c_str());
   }
   params->ep = reinterpret_cast<const char*>(lastmatch);
   return matched;
 }
 
 // Inline specializations of the general loop.
 bool DFA::SearchFFF(SearchParams* params) {
@@ skipping 137 matching lines @@
       return false;
     }
   }
 
   if (DebugDFA)
     fprintf(stderr, "anchored=%d fwd=%d flags=%#x state=%s firstbyte=%d\n",
             params->anchored, params->run_forward, flags,
             DumpState(info->start).c_str(), info->firstbyte);
 
   params->start = info->start;
-  params->firstbyte = info->firstbyte;
+  params->firstbyte = ANNOTATE_UNPROTECTED_READ(info->firstbyte);
 
   return true;
 }
 
 // Fills in info if needed.  Returns true on success, false on failure.
 bool DFA::AnalyzeSearchHelper(SearchParams* params, StartInfo* info,
                               uint flags) {
   // Quick check; okay because of memory barriers below.
-  if (info->firstbyte != kFbUnknown)
+  if (ANNOTATE_UNPROTECTED_READ(info->firstbyte) != kFbUnknown) {
+    ANNOTATE_HAPPENS_AFTER(&info->firstbyte);
     return true;
+  }
 
   MutexLock l(&mutex_);
-  if (info->firstbyte != kFbUnknown)
+  if (info->firstbyte != kFbUnknown) {
+    ANNOTATE_HAPPENS_AFTER(&info->firstbyte);
     return true;
+  }
 
   q0_->clear();
   AddToQueue(q0_,
              params->anchored ? prog_->start() : prog_->start_unanchored(),
              flags);
   info->start = WorkqToCachedState(q0_, flags);
   if (info->start == NULL)
     return false;
 
   if (info->start == DeadState) {
+    ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
     WriteMemoryBarrier();  // Synchronize with "quick check" above.
     info->firstbyte = kFbNone;
     return true;
   }
 
   if (info->start == FullMatchState) {
+    ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
     WriteMemoryBarrier();  // Synchronize with "quick check" above.
     info->firstbyte = kFbNone;  // will be ignored
     return true;
   }
 
   // Compute info->firstbyte by running state on all
   // possible byte values, looking for a single one that
   // leads to a different state.
   int firstbyte = kFbNone;
   for (int i = 0; i < 256; i++) {
     State* s = RunStateOnByte(info->start, i);
     if (s == NULL) {
+      ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
       WriteMemoryBarrier();  // Synchronize with "quick check" above.
       info->firstbyte = firstbyte;
       return false;
     }
     if (s == info->start)
       continue;
     // Goes to new state...
     if (firstbyte == kFbNone) {
       firstbyte = i;        // ... first one
     } else {
       firstbyte = kFbMany;  // ... too many
       break;
     }
   }
+  ANNOTATE_HAPPENS_BEFORE(&info->firstbyte);
   WriteMemoryBarrier();  // Synchronize with "quick check" above.
   info->firstbyte = firstbyte;
   return true;
 }
 
 // The actual DFA search: calls AnalyzeSearch and then FastSearchLoop.
 bool DFA::Search(const StringPiece& text,
                  const StringPiece& context,
                  bool anchored,
                  bool want_earliest_match,
@@ skipping 62 matching lines @@
 DFA* Prog::GetDFA(MatchKind kind) {
   DFA*volatile* pdfa;
   if (kind == kFirstMatch || kind == kManyMatch) {
     pdfa = &dfa_first_;
   } else {
     kind = kLongestMatch;
     pdfa = &dfa_longest_;
   }
 
   // Quick check; okay because of memory barrier below.
-  DFA *dfa = *pdfa;
+  DFA *dfa = ANNOTATE_UNPROTECTED_READ(*pdfa);
   if (dfa != NULL) {
     ANNOTATE_HAPPENS_AFTER(dfa);
     return dfa;
   }
 
   MutexLock l(&dfa_mutex_);
   dfa = *pdfa;
-  if (dfa != NULL)
+  if (dfa != NULL) {
+    ANNOTATE_HAPPENS_AFTER(dfa);
     return dfa;
+  }
 
   // For a forward DFA, half the memory goes to each DFA.
   // For a reverse DFA, all the memory goes to the
   // "longest match" DFA, because RE2 never does reverse
   // "first match" searches.
   int64 m = dfa_mem_/2;
   if (reversed_) {
     if (kind == kLongestMatch || kind == kManyMatch)
       m = dfa_mem_;
     else
@@ skipping 278 matching lines @@
     if (dfa_longest_ == NULL) {
       dfa_longest_ = new DFA(this, Prog::kLongestMatch, dfa_mem_/2);
       delete_dfa_ = DeleteDFA;
     }
     dfa = dfa_longest_;
   }
   return dfa->PossibleMatchRange(min, max, maxlen);
 }
 
 }  // namespace re2