1 // Copyright 2007 The RE2 Authors. All Rights Reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 #ifndef RE2_PROG_H_ 6 #define RE2_PROG_H_ 7 8 // Compiled representation of regular expressions. 9 // See regexp.h for the Regexp class, which represents a regular 10 // expression symbolically. 11 12 #include <stdint.h> 13 #include <functional> 14 #include <mutex> 15 #include <string> 16 #include <vector> 17 #include <type_traits> 18 19 #include "util/util.h" 20 #include "util/logging.h" 21 #include "re2/pod_array.h" 22 #include "re2/re2.h" 23 #include "re2/sparse_array.h" 24 #include "re2/sparse_set.h" 25 26 namespace re2 { 27 28 // Opcodes for Inst 29 enum InstOp { 30 kInstAlt = 0, // choose between out_ and out1_ 31 kInstAltMatch, // Alt: out_ is [00-FF] and back, out1_ is match; or vice versa. 32 kInstByteRange, // next (possible case-folded) byte must be in [lo_, hi_] 33 kInstCapture, // capturing parenthesis number cap_ 34 kInstEmptyWidth, // empty-width special (^ $ ...); bit(s) set in empty_ 35 kInstMatch, // found a match! 36 kInstNop, // no-op; occasionally unavoidable 37 kInstFail, // never match; occasionally unavoidable 38 kNumInst, 39 }; 40 41 // Bit flags for empty-width specials 42 enum EmptyOp { 43 kEmptyBeginLine = 1<<0, // ^ - beginning of line 44 kEmptyEndLine = 1<<1, // $ - end of line 45 kEmptyBeginText = 1<<2, // \A - beginning of text 46 kEmptyEndText = 1<<3, // \z - end of text 47 kEmptyWordBoundary = 1<<4, // \b - word boundary 48 kEmptyNonWordBoundary = 1<<5, // \B - not \b 49 kEmptyAllFlags = (1<<6)-1, 50 }; 51 52 class DFA; 53 class Regexp; 54 55 // Compiled form of regexp program. 56 class Prog { 57 public: 58 Prog(); 59 ~Prog(); 60 61 // Single instruction in regexp program. 62 class Inst { 63 public: 64 // See the assertion below for why this is so. 65 Inst() = default; 66 67 // Copyable. 68 Inst(const Inst&) = default; 69 Inst& operator=(const Inst&) = default; 70 71 // Constructors per opcode 72 void InitAlt(uint32_t out, uint32_t out1); 73 void InitByteRange(int lo, int hi, int foldcase, uint32_t out); 74 void InitCapture(int cap, uint32_t out); 75 void InitEmptyWidth(EmptyOp empty, uint32_t out); 76 void InitMatch(int id); 77 void InitNop(uint32_t out); as_raw_fd(&self) -> std::os::unix::io::RawFd78 void InitFail(); 79 80 // Getters 81 int id(Prog* p) { return static_cast<int>(this - p->inst_.data()); } 82 InstOp opcode() { return static_cast<InstOp>(out_opcode_&7); } 83 int last() { return (out_opcode_>>3)&1; } 84 int out() { return out_opcode_>>4; } as_raw_handle(&self) -> std::os::windows::io::RawHandle85 int out1() { DCHECK(opcode() == kInstAlt || opcode() == kInstAltMatch); return out1_; } 86 int cap() { DCHECK_EQ(opcode(), kInstCapture); return cap_; } 87 int lo() { DCHECK_EQ(opcode(), kInstByteRange); return lo_; } 88 int hi() { DCHECK_EQ(opcode(), kInstByteRange); return hi_; } 89 int foldcase() { DCHECK_EQ(opcode(), kInstByteRange); return hint_foldcase_&1; } 90 int hint() { DCHECK_EQ(opcode(), kInstByteRange); return hint_foldcase_>>1; } poll_write( mut self: Pin<&mut Self>, cx: &mut Context<'_>, buf: &[u8], ) -> Poll<io::Result<usize>>91 int match_id() { DCHECK_EQ(opcode(), kInstMatch); return match_id_; } 92 EmptyOp empty() { DCHECK_EQ(opcode(), kInstEmptyWidth); return empty_; } 93 94 bool greedy(Prog* p) { 95 DCHECK_EQ(opcode(), kInstAltMatch); 96 return p->inst(out())->opcode() == kInstByteRange || 97 (p->inst(out())->opcode() == kInstNop && 98 p->inst(p->inst(out())->out())->opcode() == kInstByteRange); poll_flush(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Result<(), io::Error>>99 } 100 101 // Does this inst (an kInstByteRange) match c? 102 inline bool Matches(int c) { 103 DCHECK_EQ(opcode(), kInstByteRange); 104 if (foldcase() && 'A' <= c && c <= 'Z') 105 c += 'a' - 'A'; 106 return lo_ <= c && c <= hi_; 107 } 108 109 // Returns string representation for debugging. 110 std::string Dump(); 111 112 // Maximum instruction id. 113 // (Must fit in out_opcode_. PatchList/last steal another bit.) 114 static const int kMaxInst = (1<<28) - 1; 115 116 private: 117 void set_opcode(InstOp opcode) { 118 out_opcode_ = (out()<<4) | (last()<<3) | opcode; 119 } 120 121 void set_last() { 122 out_opcode_ = (out()<<4) | (1<<3) | opcode(); 123 } 124 125 void set_out(int out) { 126 out_opcode_ = (out<<4) | (last()<<3) | opcode(); 127 } 128 129 void set_out_opcode(int out, InstOp opcode) { 130 out_opcode_ = (out<<4) | (last()<<3) | opcode; 131 } 132 133 uint32_t out_opcode_; // 28 bits: out, 1 bit: last, 3 (low) bits: opcode 134 union { // additional instruction arguments: 135 uint32_t out1_; // opcode == kInstAlt 136 // alternate next instruction 137 138 int32_t cap_; // opcode == kInstCapture 139 // Index of capture register (holds text 140 // position recorded by capturing parentheses). 141 // For \n (the submatch for the nth parentheses), 142 // the left parenthesis captures into register 2*n 143 // and the right one captures into register 2*n+1. 144 145 int32_t match_id_; // opcode == kInstMatch 146 // Match ID to identify this match (for re2::Set). 147 148 struct { // opcode == kInstByteRange 149 uint8_t lo_; // byte range is lo_-hi_ inclusive 150 uint8_t hi_; // 151 uint16_t hint_foldcase_; // 15 bits: hint, 1 (low) bit: foldcase 152 // hint to execution engines: the delta to the 153 // next instruction (in the current list) worth 154 // exploring iff this instruction matched; 0 155 // means there are no remaining possibilities, 156 // which is most likely for character classes. 157 // foldcase: A-Z -> a-z before checking range. 158 }; 159 160 EmptyOp empty_; // opcode == kInstEmptyWidth 161 // empty_ is bitwise OR of kEmpty* flags above. 162 }; 163 164 friend class Compiler; 165 friend struct PatchList; 166 friend class Prog; 167 }; 168 169 // Inst must be trivial so that we can freely clear it with memset(3). 170 // Arrays of Inst are initialised by copying the initial elements with 171 // memmove(3) and then clearing any remaining elements with memset(3). 172 static_assert(std::is_trivial<Inst>::value, "Inst must be trivial"); 173 174 // Whether to anchor the search. 175 enum Anchor { 176 kUnanchored, // match anywhere 177 kAnchored, // match only starting at beginning of text 178 }; 179 180 // Kind of match to look for (for anchor != kFullMatch) 181 // 182 // kLongestMatch mode finds the overall longest 183 // match but still makes its submatch choices the way 184 // Perl would, not in the way prescribed by POSIX. 185 // The POSIX rules are much more expensive to implement, 186 // and no one has needed them. 187 // 188 // kFullMatch is not strictly necessary -- we could use 189 // kLongestMatch and then check the length of the match -- but 190 // the matching code can run faster if it knows to consider only 191 // full matches. 192 enum MatchKind { 193 kFirstMatch, // like Perl, PCRE 194 kLongestMatch, // like egrep or POSIX 195 kFullMatch, // match only entire text; implies anchor==kAnchored 196 kManyMatch // for SearchDFA, records set of matches 197 }; 198 199 Inst *inst(int id) { return &inst_[id]; } 200 int start() { return start_; } 201 void set_start(int start) { start_ = start; } 202 int start_unanchored() { return start_unanchored_; } 203 void set_start_unanchored(int start) { start_unanchored_ = start; } 204 int size() { return size_; } 205 bool reversed() { return reversed_; } 206 void set_reversed(bool reversed) { reversed_ = reversed; } 207 int list_count() { return list_count_; } 208 int inst_count(InstOp op) { return inst_count_[op]; } 209 uint16_t* list_heads() { return list_heads_.data(); } 210 int64_t dfa_mem() { return dfa_mem_; } 211 void set_dfa_mem(int64_t dfa_mem) { dfa_mem_ = dfa_mem; } 212 bool anchor_start() { return anchor_start_; } 213 void set_anchor_start(bool b) { anchor_start_ = b; } 214 bool anchor_end() { return anchor_end_; } 215 void set_anchor_end(bool b) { anchor_end_ = b; } 216 int bytemap_range() { return bytemap_range_; } 217 const uint8_t* bytemap() { return bytemap_; } 218 bool can_prefix_accel() { return prefix_size_ != 0; } 219 220 // Accelerates to the first likely occurrence of the prefix. 221 // Returns a pointer to the first byte or NULL if not found. 222 const void* PrefixAccel(const void* data, size_t size) { 223 DCHECK_GE(prefix_size_, 1); 224 return prefix_size_ == 1 ? memchr(data, prefix_front_, size) 225 : PrefixAccel_FrontAndBack(data, size); 226 } 227 228 // An implementation of prefix accel that looks for prefix_front_ and 229 // prefix_back_ to return fewer false positives than memchr(3) alone. 230 const void* PrefixAccel_FrontAndBack(const void* data, size_t size); 231 232 // Returns string representation of program for debugging. 233 std::string Dump(); 234 std::string DumpUnanchored(); 235 std::string DumpByteMap(); 236 237 // Returns the set of kEmpty flags that are in effect at 238 // position p within context. 239 static uint32_t EmptyFlags(const StringPiece& context, const char* p); 240 241 // Returns whether byte c is a word character: ASCII only. 242 // Used by the implementation of \b and \B. 243 // This is not right for Unicode, but: 244 // - it's hard to get right in a byte-at-a-time matching world 245 // (the DFA has only one-byte lookahead). 246 // - even if the lookahead were possible, the Progs would be huge. 247 // This crude approximation is the same one PCRE uses. 248 static bool IsWordChar(uint8_t c) { 249 return ('A' <= c && c <= 'Z') || 250 ('a' <= c && c <= 'z') || 251 ('0' <= c && c <= '9') || 252 c == '_'; 253 } 254 255 // Execution engines. They all search for the regexp (run the prog) 256 // in text, which is in the larger context (used for ^ $ \b etc). 257 // Anchor and kind control the kind of search. 258 // Returns true if match found, false if not. 259 // If match found, fills match[0..nmatch-1] with submatch info. 260 // match[0] is overall match, match[1] is first set of parens, etc. 261 // If a particular submatch is not matched during the regexp match, 262 // it is set to NULL. 263 // 264 // Matching text == StringPiece(NULL, 0) is treated as any other empty 265 // string, but note that on return, it will not be possible to distinguish 266 // submatches that matched that empty string from submatches that didn't 267 // match anything. Either way, match[i] == NULL. 268 269 // Search using NFA: can find submatches but kind of slow. 270 bool SearchNFA(const StringPiece& text, const StringPiece& context, 271 Anchor anchor, MatchKind kind, 272 StringPiece* match, int nmatch); 273 274 // Search using DFA: much faster than NFA but only finds 275 // end of match and can use a lot more memory. 276 // Returns whether a match was found. 277 // If the DFA runs out of memory, sets *failed to true and returns false. 278 // If matches != NULL and kind == kManyMatch and there is a match, 279 // SearchDFA fills matches with the match IDs of the final matching state. 280 bool SearchDFA(const StringPiece& text, const StringPiece& context, 281 Anchor anchor, MatchKind kind, StringPiece* match0, 282 bool* failed, SparseSet* matches); 283 284 // The callback issued after building each DFA state with BuildEntireDFA(). 285 // If next is null, then the memory budget has been exhausted and building 286 // will halt. Otherwise, the state has been built and next points to an array 287 // of bytemap_range()+1 slots holding the next states as per the bytemap and 288 // kByteEndText. The number of the state is implied by the callback sequence: 289 // the first callback is for state 0, the second callback is for state 1, ... 290 // match indicates whether the state is a matching state. 291 using DFAStateCallback = std::function<void(const int* next, bool match)>; 292 293 // Build the entire DFA for the given match kind. 294 // Usually the DFA is built out incrementally, as needed, which 295 // avoids lots of unnecessary work. 296 // If cb is not empty, it receives one callback per state built. 297 // Returns the number of states built. 298 // FOR TESTING OR EXPERIMENTAL PURPOSES ONLY. 299 int BuildEntireDFA(MatchKind kind, const DFAStateCallback& cb); 300 301 // Controls whether the DFA should bail out early if the NFA would be faster. 302 // FOR TESTING ONLY. 303 static void TEST_dfa_should_bail_when_slow(bool b); 304 305 // Compute bytemap. 306 void ComputeByteMap(); 307 308 // Run peep-hole optimizer on program. 309 void Optimize(); 310 311 // One-pass NFA: only correct if IsOnePass() is true, 312 // but much faster than NFA (competitive with PCRE) 313 // for those expressions. 314 bool IsOnePass(); 315 bool SearchOnePass(const StringPiece& text, const StringPiece& context, 316 Anchor anchor, MatchKind kind, 317 StringPiece* match, int nmatch); 318 319 // Bit-state backtracking. Fast on small cases but uses memory 320 // proportional to the product of the list count and the text size. 321 bool CanBitState() { return list_heads_.data() != NULL; } 322 bool SearchBitState(const StringPiece& text, const StringPiece& context, 323 Anchor anchor, MatchKind kind, 324 StringPiece* match, int nmatch); 325 326 static const int kMaxOnePassCapture = 5; // $0 through $4 327 328 // Backtracking search: the gold standard against which the other 329 // implementations are checked. FOR TESTING ONLY. 330 // It allocates a ton of memory to avoid running forever. 331 // It is also recursive, so can't use in production (will overflow stacks). 332 // The name "Unsafe" here is supposed to be a flag that 333 // you should not be using this function. 334 bool UnsafeSearchBacktrack(const StringPiece& text, 335 const StringPiece& context, 336 Anchor anchor, MatchKind kind, 337 StringPiece* match, int nmatch); 338 339 // Computes range for any strings matching regexp. The min and max can in 340 // some cases be arbitrarily precise, so the caller gets to specify the 341 // maximum desired length of string returned. 342 // 343 // Assuming PossibleMatchRange(&min, &max, N) returns successfully, any 344 // string s that is an anchored match for this regexp satisfies 345 // min <= s && s <= max. 346 // 347 // Note that PossibleMatchRange() will only consider the first copy of an 348 // infinitely repeated element (i.e., any regexp element followed by a '*' or 349 // '+' operator). Regexps with "{N}" constructions are not affected, as those 350 // do not compile down to infinite repetitions. 351 // 352 // Returns true on success, false on error. 353 bool PossibleMatchRange(std::string* min, std::string* max, int maxlen); 354 355 // EXPERIMENTAL! SUBJECT TO CHANGE! 356 // Outputs the program fanout into the given sparse array. 357 void Fanout(SparseArray<int>* fanout); 358 359 // Compiles a collection of regexps to Prog. Each regexp will have 360 // its own Match instruction recording the index in the output vector. 361 static Prog* CompileSet(Regexp* re, RE2::Anchor anchor, int64_t max_mem); 362 363 // Flattens the Prog from "tree" form to "list" form. This is an in-place 364 // operation in the sense that the old instructions are lost. 365 void Flatten(); 366 367 // Walks the Prog; the "successor roots" or predecessors of the reachable 368 // instructions are marked in rootmap or predmap/predvec, respectively. 369 // reachable and stk are preallocated scratch structures. 370 void MarkSuccessors(SparseArray<int>* rootmap, 371 SparseArray<int>* predmap, 372 std::vector<std::vector<int>>* predvec, 373 SparseSet* reachable, std::vector<int>* stk); 374 375 // Walks the Prog from the given "root" instruction; the "dominator root" 376 // of the reachable instructions (if such exists) is marked in rootmap. 377 // reachable and stk are preallocated scratch structures. 378 void MarkDominator(int root, SparseArray<int>* rootmap, 379 SparseArray<int>* predmap, 380 std::vector<std::vector<int>>* predvec, 381 SparseSet* reachable, std::vector<int>* stk); 382 383 // Walks the Prog from the given "root" instruction; the reachable 384 // instructions are emitted in "list" form and appended to flat. 385 // reachable and stk are preallocated scratch structures. 386 void EmitList(int root, SparseArray<int>* rootmap, 387 std::vector<Inst>* flat, 388 SparseSet* reachable, std::vector<int>* stk); 389 390 // Computes hints for ByteRange instructions in [begin, end). 391 void ComputeHints(std::vector<Inst>* flat, int begin, int end); 392 393 private: 394 friend class Compiler; 395 396 DFA* GetDFA(MatchKind kind); 397 void DeleteDFA(DFA* dfa); 398 399 bool anchor_start_; // regexp has explicit start anchor 400 bool anchor_end_; // regexp has explicit end anchor 401 bool reversed_; // whether program runs backward over input 402 bool did_flatten_; // has Flatten been called? 403 bool did_onepass_; // has IsOnePass been called? 404 405 int start_; // entry point for program 406 int start_unanchored_; // unanchored entry point for program 407 int size_; // number of instructions 408 int bytemap_range_; // bytemap_[x] < bytemap_range_ 409 size_t prefix_size_; // size of prefix (0 if no prefix) 410 int prefix_front_; // first byte of prefix (-1 if no prefix) 411 int prefix_back_; // last byte of prefix (-1 if no prefix) 412 413 int list_count_; // count of lists (see above) 414 int inst_count_[kNumInst]; // count of instructions by opcode 415 PODArray<uint16_t> list_heads_; // sparse array enumerating list heads 416 // not populated if size_ is overly large 417 418 PODArray<Inst> inst_; // pointer to instruction array 419 PODArray<uint8_t> onepass_nodes_; // data for OnePass nodes 420 421 int64_t dfa_mem_; // Maximum memory for DFAs. 422 DFA* dfa_first_; // DFA cached for kFirstMatch/kManyMatch 423 DFA* dfa_longest_; // DFA cached for kLongestMatch/kFullMatch 424 425 uint8_t bytemap_[256]; // map from input bytes to byte classes 426 427 std::once_flag dfa_first_once_; 428 std::once_flag dfa_longest_once_; 429 430 Prog(const Prog&) = delete; 431 Prog& operator=(const Prog&) = delete; 432 }; 433 434 } // namespace re2 435 436 #endif // RE2_PROG_H_ 437