Lines Matching +full:fast +full:- +full:deep +full:- +full:equal
2 // Use of this source code is governed by a BSD-style
24 #include "re2/walker-inl.h"
42 // Can't call Decref on the sub-Regexps here because
43 // that could cause arbitrarily deep recursion, so
60 cc_->Delete(); in ~Regexp()
90 if (ref_ >= kMaxRef-1) { in Incref()
119 int r = (*ref_map)[this] - 1; in Decref()
122 ref_map->erase(this); in Decref()
128 ref_--; in Decref()
139 // to avoid arbitrarily deep recursion on process stack [sigh]. in Destroy()
144 stack = re->down_; in Destroy()
145 if (re->ref_ != 0) in Destroy()
146 LOG(DFATAL) << "Bad reference count " << re->ref_; in Destroy()
147 if (re->nsub_ > 0) { in Destroy()
148 Regexp** subs = re->sub(); in Destroy()
149 for (int i = 0; i < re->nsub_; i++) { in Destroy()
153 if (sub->ref_ == kMaxRef) in Destroy()
154 sub->Decref(); in Destroy()
156 --sub->ref_; in Destroy()
157 if (sub->ref_ == 0 && !sub->QuickDestroy()) { in Destroy()
158 sub->down_ = stack; in Destroy()
162 if (re->nsub_ > 1) in Destroy()
164 re->nsub_ = 0; in Destroy()
175 } else if (nrunes_ >= 8 && (nrunes_ & (nrunes_ - 1)) == 0) { in AddRuneToString()
189 re->match_id_ = match_id; in HaveMatch()
195 if (op == sub->op() && flags == sub->parse_flags()) in StarPlusOrQuest()
199 // op is Star/Plus/Quest, we just have to check that sub->op() is too. in StarPlusOrQuest()
200 if ((sub->op() == kRegexpStar || in StarPlusOrQuest()
201 sub->op() == kRegexpPlus || in StarPlusOrQuest()
202 sub->op() == kRegexpQuest) && in StarPlusOrQuest()
203 flags == sub->parse_flags()) { in StarPlusOrQuest()
205 if (sub->op() == kRegexpStar) in StarPlusOrQuest()
210 re->AllocSub(1); in StarPlusOrQuest()
211 re->sub()[0] = sub->sub()[0]->Incref(); in StarPlusOrQuest()
212 sub->Decref(); // We didn't consume the reference after all. in StarPlusOrQuest()
217 re->AllocSub(1); in StarPlusOrQuest()
218 re->sub()[0] = sub; in StarPlusOrQuest()
262 // Make a two-level tree. Two levels gets us to 65535^2. in ConcatOrAlternate()
263 int nbigsub = (nsub+kMaxNsub-1)/kMaxNsub; in ConcatOrAlternate()
265 re->AllocSub(nbigsub); in ConcatOrAlternate()
266 Regexp** subs = re->sub(); in ConcatOrAlternate()
267 for (int i = 0; i < nbigsub - 1; i++) in ConcatOrAlternate()
269 subs[nbigsub - 1] = ConcatOrAlternate(op, sub+(nbigsub-1)*kMaxNsub, in ConcatOrAlternate()
270 nsub - (nbigsub-1)*kMaxNsub, flags, in ConcatOrAlternate()
277 re->AllocSub(nsub); in ConcatOrAlternate()
278 Regexp** subs = re->sub(); in ConcatOrAlternate()
300 re->AllocSub(1); in Capture()
301 re->sub()[0] = sub; in Capture()
302 re->cap_ = cap; in Capture()
308 re->AllocSub(1); in Repeat()
309 re->sub()[0] = sub; in Repeat()
310 re->min_ = min; in Repeat()
311 re->max_ = max; in Repeat()
317 re->rune_ = rune; in NewLiteral()
328 re->AddRuneToString(runes[i]); in LiteralString()
334 re->cc_ = cc; in NewCharClass()
349 // Tests equality of all top-level structure but not subregexps.
351 if (a->op() != b->op()) in TopEqual()
354 switch (a->op()) { in TopEqual()
367 // The parse flags remember whether it's \z or (?-m:$), in TopEqual()
369 return ((a->parse_flags() ^ b->parse_flags()) & Regexp::WasDollar) == 0; in TopEqual()
372 return a->rune() == b->rune() && in TopEqual()
373 ((a->parse_flags() ^ b->parse_flags()) & Regexp::FoldCase) == 0; in TopEqual()
376 return a->nrunes() == b->nrunes() && in TopEqual()
377 ((a->parse_flags() ^ b->parse_flags()) & Regexp::FoldCase) == 0 && in TopEqual()
378 memcmp(a->runes(), b->runes(), in TopEqual()
379 a->nrunes() * sizeof a->runes()[0]) == 0; in TopEqual()
383 return a->nsub() == b->nsub(); in TopEqual()
388 return ((a->parse_flags() ^ b->parse_flags()) & Regexp::NonGreedy) == 0; in TopEqual()
391 return ((a->parse_flags() ^ b->parse_flags()) & Regexp::NonGreedy) == 0 && in TopEqual()
392 a->min() == b->min() && in TopEqual()
393 a->max() == b->max(); in TopEqual()
396 return a->cap() == b->cap() && a->name() == b->name(); in TopEqual()
399 return a->match_id() == b->match_id(); in TopEqual()
402 CharClass* acc = a->cc(); in TopEqual()
403 CharClass* bcc = b->cc(); in TopEqual()
404 return acc->size() == bcc->size() && in TopEqual()
405 acc->end() - acc->begin() == bcc->end() - bcc->begin() && in TopEqual()
406 memcmp(acc->begin(), bcc->begin(), in TopEqual()
407 (acc->end() - acc->begin()) * sizeof acc->begin()[0]) == 0; in TopEqual()
411 LOG(DFATAL) << "Unexpected op in Regexp::Equal: " << a->op(); in TopEqual()
415 bool Regexp::Equal(Regexp* a, Regexp* b) { in Equal() function in re2::Regexp
422 // Fast path: in Equal()
424 switch (a->op()) { in Equal()
440 // be compared. The regexps are only equal if in Equal()
441 // all the pairs end up being equal. in Equal()
448 switch (a->op()) { in Equal()
453 for (int i = 0; i < a->nsub(); i++) { in Equal()
454 a2 = a->sub()[i]; in Equal()
455 b2 = b->sub()[i]; in Equal()
468 a2 = a->sub()[0]; in Equal()
469 b2 = b->sub()[0]; in Equal()
487 a = stk[n-2]; in Equal()
488 b = stk[n-1]; in Equal()
489 stk.resize(n-2); in Equal()
509 "invalid UTF-8",
543 if (re->op() == kRegexpCapture) in PreVisit()
579 if (re->op() == kRegexpCapture && re->name() != NULL) { in PreVisit()
587 if (map_->find(*re->name()) == map_->end()) in PreVisit()
588 (*map_)[*re->name()] = re->cap(); in PreVisit()
625 if (re->op() == kRegexpCapture && re->name() != NULL) { in PreVisit()
630 (*map_)[re->cap()] = *re->name(); in PreVisit()
657 // be ASCII case-insensitive.
663 prefix->clear(); in RequiredPrefix()
671 Regexp** sub = this->sub(); in RequiredPrefix()
672 while (i < nsub_ && sub[i]->op_ == kRegexpBeginText) in RequiredPrefix()
678 switch (re->op_) { in RequiredPrefix()
684 if (re->parse_flags() & Latin1) { in RequiredPrefix()
685 prefix->resize(re->nrunes_); in RequiredPrefix()
686 for (int j = 0; j < re->nrunes_; j++) in RequiredPrefix()
687 (*prefix)[j] = static_cast<char>(re->runes_[j]); in RequiredPrefix()
689 // Convert to UTF-8 in place. in RequiredPrefix()
690 // Assume worst-case space and then trim. in RequiredPrefix()
691 prefix->resize(re->nrunes_ * UTFmax); in RequiredPrefix()
693 for (int j = 0; j < re->nrunes_; j++) { in RequiredPrefix()
694 Rune r = re->runes_[j]; in RequiredPrefix()
700 prefix->resize(p - &(*prefix)[0]); in RequiredPrefix()
705 if ((re->parse_flags() & Latin1) || re->rune_ < Runeself) { in RequiredPrefix()
706 prefix->append(1, static_cast<char>(re->rune_)); in RequiredPrefix()
709 prefix->append(buf, runetochar(buf, &re->rune_)); in RequiredPrefix()
713 *foldcase = (sub[i]->parse_flags() & FoldCase) != 0; in RequiredPrefix()
719 sub[j]->Incref(); in RequiredPrefix()
720 re = Concat(sub + i, nsub_ - i, parse_flags()); in RequiredPrefix()
729 // containing non-overlapping, non-abutting RuneRanges.
730 // The less-than operator used in the tree treats two
731 // ranges as equal if they overlap at all, so that
740 // Add lo-hi to the class; return whether class got bigger.
751 upper_ |= ((1 << (hi1 - lo1 + 1)) - 1) << (lo1 - 'A'); in AddRange()
756 lower_ |= ((1 << (hi1 - lo1 + 1)) - 1) << (lo1 - 'a'); in AddRange()
761 if (it != end() && it->lo <= lo && hi <= it->hi) in AddRange()
768 iterator it = ranges_.find(RuneRange(lo-1, lo-1)); in AddRange()
770 lo = it->lo; in AddRange()
771 if (it->hi > hi) in AddRange()
772 hi = it->hi; in AddRange()
773 nrunes_ -= it->hi - it->lo + 1; in AddRange()
783 hi = it->hi; in AddRange()
784 nrunes_ -= it->hi - it->lo + 1; in AddRange()
797 nrunes_ -= it->hi - it->lo + 1; in AddRange()
802 nrunes_ += hi - lo + 1; in AddRange()
808 for (iterator it = cc->begin(); it != cc->end(); ++it) in AddCharClass()
809 AddRange(it->lo, it->hi); in AddCharClass()
816 // Does the character class behave the same on A-Z as on a-z?
824 cc->ranges_.insert(RuneRange(it->lo, it->hi)); in Copy()
825 cc->upper_ = upper_; in Copy()
826 cc->lower_ = lower_; in Copy()
827 cc->nrunes_ = nrunes_; in Copy()
841 lower_ &= AlphaMask >> ('z' - r); in RemoveAbove()
848 upper_ &= AlphaMask >> ('Z' - r); in RemoveAbove()
858 nrunes_ -= rr.hi - rr.lo + 1; in RemoveAbove()
862 nrunes_ += rr.hi - rr.lo + 1; in RemoveAbove()
880 if (it->lo == 0) { in Negate()
881 nextlo = it->hi + 1; in Negate()
885 v.push_back(RuneRange(nextlo, it->lo - 1)); in Negate()
886 nextlo = it->hi + 1; in Negate()
898 nrunes_ = Runemax+1 - nrunes_; in Negate()
907 uint8_t* data = new uint8_t[sizeof *cc + maxranges*sizeof cc->ranges_[0]]; in New()
909 cc->ranges_ = reinterpret_cast<RuneRange*>(data + sizeof *cc); in New()
910 cc->nranges_ = 0; in New()
911 cc->folds_ascii_ = false; in New()
912 cc->nrunes_ = 0; in New()
923 cc->folds_ascii_ = folds_ascii_; in Negate()
924 cc->nrunes_ = Runemax + 1 - nrunes_; in Negate()
928 if (it->lo == nextlo) { in Negate()
929 nextlo = it->hi + 1; in Negate()
931 cc->ranges_[n++] = RuneRange(nextlo, it->lo - 1); in Negate()
932 nextlo = it->hi + 1; in Negate()
936 cc->ranges_[n++] = RuneRange(nextlo, Runemax); in Negate()
937 cc->nranges_ = n; in Negate()
948 n -= m+1; in Contains()
962 cc->ranges_[n++] = *it; in GetCharClass()
963 cc->nranges_ = n; in GetCharClass()
965 cc->nrunes_ = nrunes_; in GetCharClass()
966 cc->folds_ascii_ = FoldsASCII(); in GetCharClass()