| 770 | } |
| 771 | |
| 772 | void Prog::EmitList(int root, SparseArray<int>* rootmap, |
| 773 | std::vector<Inst>* flat, |
| 774 | SparseSet* reachable, std::vector<int>* stk) { |
| 775 | reachable->clear(); |
| 776 | stk->clear(); |
| 777 | stk->push_back(root); |
| 778 | while (!stk->empty()) { |
| 779 | int id = stk->back(); |
| 780 | stk->pop_back(); |
| 781 | Loop: |
| 782 | if (reachable->contains(id)) |
| 783 | continue; |
| 784 | reachable->insert_new(id); |
| 785 | |
| 786 | if (id != root && rootmap->has_index(id)) { |
| 787 | // We reached another "tree" via epsilon transition. Emit a kInstNop |
| 788 | // instruction so that the Prog does not become quadratically larger. |
| 789 | flat->emplace_back(); |
| 790 | flat->back().set_opcode(kInstNop); |
| 791 | flat->back().set_out(rootmap->get_existing(id)); |
| 792 | continue; |
| 793 | } |
| 794 | |
| 795 | Inst* ip = inst(id); |
| 796 | switch (ip->opcode()) { |
| 797 | default: |
| 798 | LOG(DFATAL) << "unhandled opcode: " << ip->opcode(); |
| 799 | break; |
| 800 | |
| 801 | case kInstAltMatch: |
| 802 | flat->emplace_back(); |
| 803 | flat->back().set_opcode(kInstAltMatch); |
| 804 | flat->back().set_out(static_cast<int>(flat->size())); |
| 805 | flat->back().out1_ = static_cast<uint32_t>(flat->size())+1; |
| 806 | FALLTHROUGH_INTENDED; |
| 807 | |
| 808 | case kInstAlt: |
| 809 | stk->push_back(ip->out1()); |
| 810 | id = ip->out(); |
| 811 | goto Loop; |
| 812 | |
| 813 | case kInstByteRange: |
| 814 | case kInstCapture: |
| 815 | case kInstEmptyWidth: |
| 816 | flat->emplace_back(); |
| 817 | memmove(&flat->back(), ip, sizeof *ip); |
| 818 | flat->back().set_out(rootmap->get_existing(ip->out())); |
| 819 | break; |
| 820 | |
| 821 | case kInstNop: |
| 822 | id = ip->out(); |
| 823 | goto Loop; |
| 824 | |
| 825 | case kInstMatch: |
| 826 | case kInstFail: |
| 827 | flat->emplace_back(); |
| 828 | memmove(&flat->back(), ip, sizeof *ip); |
| 829 | break; |
nothing calls this directly
no test coverage detected