| 410 | } |
| 411 | |
| 412 | bool Regexp::Equal(Regexp* a, Regexp* b) { |
| 413 | if (a == NULL || b == NULL) |
| 414 | return a == b; |
| 415 | |
| 416 | if (!TopEqual(a, b)) |
| 417 | return false; |
| 418 | |
| 419 | // Fast path: |
| 420 | // return without allocating vector if there are no subregexps. |
| 421 | switch (a->op()) { |
| 422 | case kRegexpAlternate: |
| 423 | case kRegexpConcat: |
| 424 | case kRegexpStar: |
| 425 | case kRegexpPlus: |
| 426 | case kRegexpQuest: |
| 427 | case kRegexpRepeat: |
| 428 | case kRegexpCapture: |
| 429 | break; |
| 430 | |
| 431 | default: |
| 432 | return true; |
| 433 | } |
| 434 | |
| 435 | // Committed to doing real work. |
| 436 | // The stack (vector) has pairs of regexps waiting to |
| 437 | // be compared. The regexps are only equal if |
| 438 | // all the pairs end up being equal. |
| 439 | std::vector<Regexp*> stk; |
| 440 | |
| 441 | for (;;) { |
| 442 | // Invariant: TopEqual(a, b) == true. |
| 443 | Regexp* a2; |
| 444 | Regexp* b2; |
| 445 | switch (a->op()) { |
| 446 | default: |
| 447 | break; |
| 448 | case kRegexpAlternate: |
| 449 | case kRegexpConcat: |
| 450 | for (int i = 0; i < a->nsub(); i++) { |
| 451 | a2 = a->sub()[i]; |
| 452 | b2 = b->sub()[i]; |
| 453 | if (!TopEqual(a2, b2)) |
| 454 | return false; |
| 455 | stk.push_back(a2); |
| 456 | stk.push_back(b2); |
| 457 | } |
| 458 | break; |
| 459 | |
| 460 | case kRegexpStar: |
| 461 | case kRegexpPlus: |
| 462 | case kRegexpQuest: |
| 463 | case kRegexpRepeat: |
| 464 | case kRegexpCapture: |
| 465 | a2 = a->sub()[0]; |
| 466 | b2 = b->sub()[0]; |
| 467 | if (!TopEqual(a2, b2)) |
| 468 | return false; |
| 469 | // Really: |