Runs a backtracking search.
| 97 | |
| 98 | // Runs a backtracking search. |
| 99 | bool Backtracker::Search(const StringPiece& text, const StringPiece& context, |
| 100 | bool anchored, bool longest, |
| 101 | StringPiece* submatch, int nsubmatch) { |
| 102 | text_ = text; |
| 103 | context_ = context; |
| 104 | if (context_.data() == NULL) |
| 105 | context_ = text; |
| 106 | if (prog_->anchor_start() && text.begin() > context_.begin()) |
| 107 | return false; |
| 108 | if (prog_->anchor_end() && text.end() < context_.end()) |
| 109 | return false; |
| 110 | anchored_ = anchored | prog_->anchor_start(); |
| 111 | longest_ = longest | prog_->anchor_end(); |
| 112 | endmatch_ = prog_->anchor_end(); |
| 113 | submatch_ = submatch; |
| 114 | nsubmatch_ = nsubmatch; |
| 115 | CHECK_LT(2*nsubmatch_, static_cast<int>(arraysize(cap_))); |
| 116 | memset(cap_, 0, sizeof cap_); |
| 117 | |
| 118 | // We use submatch_[0] for our own bookkeeping, |
| 119 | // so it had better exist. |
| 120 | StringPiece sp0; |
| 121 | if (nsubmatch < 1) { |
| 122 | submatch_ = &sp0; |
| 123 | nsubmatch_ = 1; |
| 124 | } |
| 125 | submatch_[0] = StringPiece(); |
| 126 | |
| 127 | // Allocate new visited_ bitmap -- size is proportional |
| 128 | // to text, so have to reallocate on each call to Search. |
| 129 | int nvisited = prog_->size() * static_cast<int>(text.size()+1); |
| 130 | nvisited = (nvisited + 31) / 32; |
| 131 | visited_ = PODArray<uint32_t>(nvisited); |
| 132 | memset(visited_.data(), 0, nvisited*sizeof visited_[0]); |
| 133 | |
| 134 | // Anchored search must start at text.begin(). |
| 135 | if (anchored_) { |
| 136 | cap_[0] = text.data(); |
| 137 | return Visit(prog_->start(), text.data()); |
| 138 | } |
| 139 | |
| 140 | // Unanchored search, starting from each possible text position. |
| 141 | // Notice that we have to try the empty string at the end of |
| 142 | // the text, so the loop condition is p <= text.end(), not p < text.end(). |
| 143 | for (const char* p = text.data(); p <= text.data() + text.size(); p++) { |
| 144 | cap_[0] = p; |
| 145 | if (Visit(prog_->start(), p)) // Match must be leftmost; done. |
| 146 | return true; |
| 147 | // Avoid invoking undefined behavior (arithmetic on a null pointer) |
| 148 | // by simply not continuing the loop. |
| 149 | if (p == NULL) |
| 150 | break; |
| 151 | } |
| 152 | return false; |
| 153 | } |
| 154 | |
| 155 | // Explores from instruction id at string position p looking for a match. |
| 156 | // Return true if found (so that caller can stop trying other possibilities). |
no test coverage detected