Run runq on byte c, appending new states to nextq. Updates matched_ and match_ as new, better matches are found. context is used (with p) for evaluating empty-width specials. p is the position of byte c in the input string for AddToThreadq; p-1 will be used when processing Match instructions. Frees all the threads on runq. If there is a shortcut to the end, returns that shortcut.
| 329 | // Frees all the threads on runq. |
| 330 | // If there is a shortcut to the end, returns that shortcut. |
| 331 | int NFA::Step(Threadq* runq, Threadq* nextq, int c, const StringPiece& context, |
| 332 | const char* p) { |
| 333 | nextq->clear(); |
| 334 | |
| 335 | for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) { |
| 336 | Thread* t = i->value(); |
| 337 | if (t == NULL) |
| 338 | continue; |
| 339 | |
| 340 | if (longest_) { |
| 341 | // Can skip any threads started after our current best match. |
| 342 | if (matched_ && match_[0] < t->capture[0]) { |
| 343 | Decref(t); |
| 344 | continue; |
| 345 | } |
| 346 | } |
| 347 | |
| 348 | int id = i->index(); |
| 349 | Prog::Inst* ip = prog_->inst(id); |
| 350 | |
| 351 | switch (ip->opcode()) { |
| 352 | default: |
| 353 | // Should only see the values handled below. |
| 354 | LOG(DFATAL) << "Unhandled " << ip->opcode() << " in step"; |
| 355 | break; |
| 356 | |
| 357 | case kInstByteRange: |
| 358 | AddToThreadq(nextq, ip->out(), c, context, p, t); |
| 359 | break; |
| 360 | |
| 361 | case kInstAltMatch: |
| 362 | if (i != runq->begin()) |
| 363 | break; |
| 364 | // The match is ours if we want it. |
| 365 | if (ip->greedy(prog_) || longest_) { |
| 366 | CopyCapture(match_, t->capture); |
| 367 | matched_ = true; |
| 368 | |
| 369 | Decref(t); |
| 370 | for (++i; i != runq->end(); ++i) { |
| 371 | if (i->value() != NULL) |
| 372 | Decref(i->value()); |
| 373 | } |
| 374 | runq->clear(); |
| 375 | if (ip->greedy(prog_)) |
| 376 | return ip->out1(); |
| 377 | return ip->out(); |
| 378 | } |
| 379 | break; |
| 380 | |
| 381 | case kInstMatch: { |
| 382 | // Avoid invoking undefined behavior (arithmetic on a null pointer) |
| 383 | // by storing p instead of p-1. (What would the latter even mean?!) |
| 384 | // This complements the special case in NFA::Search(). |
| 385 | if (p == NULL) { |
| 386 | CopyCapture(match_, t->capture); |
| 387 | match_[1] = p; |
| 388 | matched_ = true; |