Author: Sam McCall Date: 2022-06-23T18:16:38+02:00 New Revision: 2c80b5319870b57fbdbb6c9cef9c86c26c65371d
URL: https://github.com/llvm/llvm-project/commit/2c80b5319870b57fbdbb6c9cef9c86c26c65371d DIFF: https://github.com/llvm/llvm-project/commit/2c80b5319870b57fbdbb6c9cef9c86c26c65371d.diff LOG: Revert "[pseudo] Track heads as GSS nodes, rather than as "pending actions"." This reverts commit e3ec054dfdf48f19cb6726cb3f4965b9ab320ed9. Tests fail in asserts mode: https://lab.llvm.org/buildbot/#/builders/109/builds/41217 Added: Modified: clang-tools-extra/pseudo/include/clang-pseudo/GLR.h clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h clang-tools-extra/pseudo/lib/GLR.cpp clang-tools-extra/pseudo/lib/grammar/LRTable.cpp clang-tools-extra/pseudo/unittests/GLRTest.cpp Removed: ################################################################################ diff --git a/clang-tools-extra/pseudo/include/clang-pseudo/GLR.h b/clang-tools-extra/pseudo/include/clang-pseudo/GLR.h index a3e8611de4252..8783872fa3556 100644 --- a/clang-tools-extra/pseudo/include/clang-pseudo/GLR.h +++ b/clang-tools-extra/pseudo/include/clang-pseudo/GLR.h @@ -132,17 +132,34 @@ struct ParseParams { const ForestNode &glrParse(const TokenStream &Code, const ParseParams &Params, SymbolID StartSymbol); -// Shift a token onto all OldHeads, placing the results into NewHeads. +// An active stack head can have multiple available actions (reduce/reduce +// actions, reduce/shift actions). +// A step is any one action applied to any one stack head. +struct ParseStep { + // A specific stack head. + const GSS::Node *Head = nullptr; + // An action associated with the head. + LRTable::Action Action = LRTable::Action::sentinel(); +}; +// A callback is invoked whenever a new GSS head is created during the GLR +// parsing process (glrShift, or glrReduce). +using NewHeadCallback = std::function<void(const GSS::Node *)>; +// Apply all PendingShift actions on a given GSS state, newly-created heads are +// passed to the callback. +// +// When this function returns, PendingShift is empty. // // Exposed for testing only. -void glrShift(llvm::ArrayRef<const GSS::Node *> OldHeads, - const ForestNode &NextTok, const ParseParams &Params, - std::vector<const GSS::Node *> &NewHeads); -// Applies available reductions on Heads, appending resulting heads to the list. +void glrShift(std::vector<ParseStep> &PendingShift, const ForestNode &NextTok, + const ParseParams &Params, NewHeadCallback NewHeadCB); +// Applies PendingReduce actions, until no more reduce actions are available. +// +// When this function returns, PendingReduce is empty. Calls to NewHeadCB may +// add elements to PendingReduce // // Exposed for testing only. -void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead, - const ParseParams &Params); +void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params, + NewHeadCallback NewHeadCB); } // namespace pseudo } // namespace clang diff --git a/clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h b/clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h index ab619774d93da..08e4868b88f70 100644 --- a/clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h +++ b/clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h @@ -128,12 +128,7 @@ class LRTable { llvm::ArrayRef<Action> getActions(StateID State, SymbolID Terminal) const; // Returns the state after we reduce a nonterminal. // Expected to be called by LR parsers. - // REQUIRES: Nonterminal is valid here. StateID getGoToState(StateID State, SymbolID Nonterminal) const; - // Returns the state after we shift a terminal. - // Expected to be called by LR parsers. - // If the terminal is invalid here, returns None. - llvm::Optional<StateID> getShiftState(StateID State, SymbolID Terminal) const; // Looks up available actions. // Returns empty if no available actions in the table. diff --git a/clang-tools-extra/pseudo/lib/GLR.cpp b/clang-tools-extra/pseudo/lib/GLR.cpp index 927aed39549d2..39da7f15c5c9a 100644 --- a/clang-tools-extra/pseudo/lib/GLR.cpp +++ b/clang-tools-extra/pseudo/lib/GLR.cpp @@ -45,41 +45,68 @@ const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params, (void)G; auto &GSS = Params.GSStack; + // Lists of active shift, reduce actions. + std::vector<ParseStep> PendingShift, PendingReduce; + auto AddSteps = [&](const GSS::Node *Head, SymbolID NextTok) { + for (const auto &Action : Params.Table.getActions(Head->State, NextTok)) { + switch (Action.kind()) { + case LRTable::Action::Shift: + PendingShift.push_back({Head, Action}); + break; + case LRTable::Action::Reduce: + PendingReduce.push_back({Head, Action}); + break; + default: + llvm_unreachable("unexpected action kind!"); + } + } + }; StateID StartState = Params.Table.getStartState(StartSymbol); - // Heads correspond to the parse of tokens [0, I), NextHeads to [0, I+1). - std::vector<const GSS::Node *> Heads = {GSS.addNode(/*State=*/StartState, - /*ForestNode=*/nullptr, - {})}; - std::vector<const GSS::Node *> NextHeads; + std::vector<const GSS::Node *> NewHeads = { + GSS.addNode(/*State=*/StartState, + /*ForestNode=*/nullptr, {})}; auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable { - assert(NextHeads.empty() && "Running GC at the wrong time!"); + assert(PendingShift.empty() && PendingReduce.empty() && + "Running GC at the wrong time!"); + if (++I != 20) // Run periodically to balance CPU and memory usage. return; I = 0; // We need to copy the list: Roots is consumed by the GC. - Roots = Heads; + Roots = NewHeads; GSS.gc(std::move(Roots)); }; - // Each iteration fully processes a single token. - for (unsigned I = 0; I < Terminals.size(); ++I) { - LLVM_DEBUG(llvm::dbgs() << llvm::formatv( - "Next token {0} (id={1})\n", - G.symbolName(Terminals[I].symbol()), Terminals[I].symbol())); - // Consume the token. - glrShift(Heads, Terminals[I], Params, NextHeads); - // Form nonterminals containing the token we just consumed. - SymbolID Lookahead = I + 1 == Terminals.size() ? tokenSymbol(tok::eof) - : Terminals[I + 1].symbol(); - glrReduce(NextHeads, Lookahead, Params); - // Prepare for the next token. - std::swap(Heads, NextHeads); - NextHeads.clear(); + for (const ForestNode &Terminal : Terminals) { + LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n", + G.symbolName(Terminal.symbol()), + Terminal.symbol())); + for (const auto *Head : NewHeads) + AddSteps(Head, Terminal.symbol()); + NewHeads.clear(); + glrReduce(PendingReduce, Params, + [&](const GSS::Node * NewHead) { + // A reduce will enable more steps. + AddSteps(NewHead, Terminal.symbol()); + }); + + glrShift(PendingShift, Terminal, Params, + [&](const GSS::Node *NewHead) { NewHeads.push_back(NewHead); }); MaybeGC(); } - LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Reached eof\n")); + LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next is eof\n")); + for (const auto *Heads : NewHeads) + AddSteps(Heads, tokenSymbol(tok::eof)); StateID AcceptState = Params.Table.getGoToState(StartState, StartSymbol); + // Collect new heads created from the final reduce. + std::vector<const GSS::Node*> Heads; + glrReduce(PendingReduce, Params, [&](const GSS::Node *NewHead) { + Heads.push_back(NewHead); + // A reduce will enable more steps. + AddSteps(NewHead, tokenSymbol(tok::eof)); + }); + const ForestNode *Result = nullptr; for (const auto *Head : Heads) { if (Head->State == AcceptState) { @@ -111,40 +138,42 @@ const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params, // After the shift action, the GSS is: // 0---1---2---4 // └---3---┘ -void glrShift(llvm::ArrayRef<const GSS::Node *> OldHeads, - const ForestNode &NewTok, const ParseParams &Params, - std::vector<const GSS::Node *> &NewHeads) { +void glrShift(std::vector<ParseStep> &PendingShift, const ForestNode &NewTok, + const ParseParams &Params, NewHeadCallback NewHeadCB) { assert(NewTok.kind() == ForestNode::Terminal); + assert(llvm::all_of(PendingShift, + [](const ParseStep &Step) { + return Step.Action.kind() == LRTable::Action::Shift; + }) && + "Pending shift actions must be shift actions"); LLVM_DEBUG(llvm::dbgs() << llvm::formatv(" Shift {0} ({1} active heads):\n", Params.G.symbolName(NewTok.symbol()), - OldHeads.size())); + PendingShift.size())); // We group pending shifts by their target state so we can merge them. - llvm::SmallVector<std::pair<StateID, const GSS::Node *>, 8> Shifts; - for (const auto *H : OldHeads) - if (auto S = Params.Table.getShiftState(H->State, NewTok.symbol())) - Shifts.push_back({*S, H}); - llvm::stable_sort(Shifts, llvm::less_first{}); - - auto Rest = llvm::makeArrayRef(Shifts); + llvm::stable_sort(PendingShift, [](const ParseStep &L, const ParseStep &R) { + return L.Action.getShiftState() < R.Action.getShiftState(); + }); + auto Rest = llvm::makeArrayRef(PendingShift); llvm::SmallVector<const GSS::Node *> Parents; while (!Rest.empty()) { // Collect the batch of PendingShift that have compatible shift states. // Their heads become TempParents, the parents of the new GSS node. - StateID NextState = Rest.front().first; + StateID NextState = Rest.front().Action.getShiftState(); Parents.clear(); for (const auto &Base : Rest) { - if (Base.first != NextState) + if (Base.Action.getShiftState() != NextState) break; - Parents.push_back(Base.second); + Parents.push_back(Base.Head); } Rest = Rest.drop_front(Parents.size()); LLVM_DEBUG(llvm::dbgs() << llvm::formatv(" --> S{0} ({1} heads)\n", NextState, Parents.size())); - NewHeads.push_back(Params.GSStack.addNode(NextState, &NewTok, Parents)); + NewHeadCB(Params.GSStack.addNode(NextState, &NewTok, Parents)); } + PendingShift.clear(); } namespace { @@ -202,9 +231,8 @@ template <typename T> void sortAndUnique(std::vector<T> &Vec) { // After reducing 3 by `pointer := class-name STAR` and // 2 by`enum-name := class-name STAR`: // 0--5(pointer) // 5 is goto(0, pointer) -void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead, - const ParseParams &Params) { - assert(isToken(Lookahead)); +void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params, + NewHeadCallback NewHeadCB) { // There are two interacting complications: // 1. Performing one reduce can unlock new reduces on the newly-created head. // 2a. The ambiguous ForestNodes must be complete (have all sequence nodes). @@ -263,10 +291,6 @@ void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead, KeyedQueue<Family, PushSpec> Sequences; Sequence TempSequence; - - // We treat Heads as a queue of Pop operations still to be performed. - // NextPopHead is our position within it. - unsigned NextPopHead = 0; // Pop walks up the parent chain(s) for a reduction from Head by to Rule. // Once we reach the end, record the bases and sequences. auto Pop = [&](const GSS::Node *Head, RuleID RID) { @@ -288,16 +312,9 @@ void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead, DFS(Head, 0, DFS); }; auto PopPending = [&] { - for (; NextPopHead < Heads.size(); ++NextPopHead) { - // FIXME: if there's exactly one head in the queue, and the pop stage - // is trivial, we could pop + push without touching the expensive queues. - for (const auto &A : - Params.Table.getActions(Heads[NextPopHead]->State, Lookahead)) { - if (A.kind() != LRTable::Action::Reduce) - continue; - Pop(Heads[NextPopHead], A.getReduceRule()); - } - } + for (const ParseStep &Pending : PendingReduce) + Pop(Pending.Head, Pending.Action.getReduceRule()); + PendingReduce.clear(); }; std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases; @@ -361,7 +378,10 @@ void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead, Parents.push_back(Base.second); } BasesLeft = BasesLeft.drop_front(Parents.size()); - Heads.push_back(Params.GSStack.addNode(NextState, Parsed, Parents)); + + // Invoking the callback for new heads, a real GLR parser may add new + // reduces to the PendingReduce queue! + NewHeadCB(Params.GSStack.addNode(NextState, Parsed, Parents)); } PopPending(); } diff --git a/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp b/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp index 1f700e53a92f2..016949df5e640 100644 --- a/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp +++ b/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp @@ -72,17 +72,6 @@ std::string LRTable::dumpForTests(const Grammar &G) const { return OS.str(); } -llvm::Optional<LRTable::StateID> -LRTable::getShiftState(StateID State, SymbolID Terminal) const { - // FIXME: we spend a significant amount of time on misses here. - // We could consider storing a std::bitset for a cheaper test? - assert(pseudo::isToken(Terminal) && "expected terminal symbol!"); - for (const auto &Result : getActions(State, Terminal)) - if (Result.kind() == Action::Shift) - return Result.getShiftState(); // unique: no shift/shift conflicts. - return llvm::None; -} - llvm::ArrayRef<LRTable::Action> LRTable::getActions(StateID State, SymbolID Terminal) const { assert(pseudo::isToken(Terminal) && "expect terminal symbol!"); diff --git a/clang-tools-extra/pseudo/unittests/GLRTest.cpp b/clang-tools-extra/pseudo/unittests/GLRTest.cpp index 6e72f1049878e..d9555a8d56dd9 100644 --- a/clang-tools-extra/pseudo/unittests/GLRTest.cpp +++ b/clang-tools-extra/pseudo/unittests/GLRTest.cpp @@ -7,8 +7,8 @@ //===----------------------------------------------------------------------===// #include "clang-pseudo/GLR.h" -#include "clang-pseudo/Token.h" #include "clang-pseudo/grammar/Grammar.h" +#include "clang-pseudo/Token.h" #include "clang/Basic/LangOptions.h" #include "clang/Basic/TokenKinds.h" #include "llvm/ADT/StringExtras.h" @@ -31,7 +31,6 @@ namespace { using Action = LRTable::Action; using testing::AllOf; -using testing::UnorderedElementsAre; MATCHER_P(state, StateID, "") { return arg->State == StateID; } MATCHER_P(parsedSymbol, FNode, "") { return arg->Payload == FNode; } @@ -84,10 +83,17 @@ class GLRTest : public ::testing::Test { return 0; } + NewHeadCallback captureNewHeads() { + return [this](const GSS::Node *NewHead) { + NewHeadResults.push_back(NewHead); + }; + }; + protected: std::unique_ptr<Grammar> G; ForestArena Arena; GSS GSStack; + std::vector<const GSS::Node*> NewHeadResults; }; TEST_F(GLRTest, ShiftMergingHeads) { @@ -103,32 +109,31 @@ TEST_F(GLRTest, ShiftMergingHeads) { // └---3---5 auto *GSSNode0 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); - auto *GSSNode1 = GSStack.addNode(/*State=*/1, /*ForestNode=*/nullptr, + auto *GSSNode1 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{GSSNode0}); - auto *GSSNode2 = GSStack.addNode(/*State=*/2, /*ForestNode=*/nullptr, + auto *GSSNode2 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{GSSNode0}); - auto *GSSNode3 = GSStack.addNode(/*State=*/3, /*ForestNode=*/nullptr, + auto *GSSNode3 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{GSSNode0}); buildGrammar({}, {}); // Create a fake empty grammar. - LRTable T = - LRTable::buildForTests(G->table(), /*Entries=*/{ - {1, tokenSymbol(tok::semi), Action::shift(4)}, - {2, tokenSymbol(tok::semi), Action::shift(4)}, - {3, tokenSymbol(tok::semi), Action::shift(5)}, - }); + LRTable T = LRTable::buildForTests(G->table(), /*Entries=*/{}); ForestNode &SemiTerminal = Arena.createTerminal(tok::semi, 0); - std::vector<const GSS::Node *> NewHeads; - glrShift({GSSNode1, GSSNode2, GSSNode3}, SemiTerminal, - {*G, T, Arena, GSStack}, NewHeads); - - EXPECT_THAT(NewHeads, - UnorderedElementsAre(AllOf(state(4), parsedSymbol(&SemiTerminal), - parents({GSSNode1, GSSNode2})), - AllOf(state(5), parsedSymbol(&SemiTerminal), - parents({GSSNode3})))) - << NewHeads; + std::vector<ParseStep> PendingShift = { + {GSSNode1, Action::shift(4)}, + {GSSNode3, Action::shift(5)}, + {GSSNode2, Action::shift(4)}, + }; + glrShift(PendingShift, SemiTerminal, {*G, T, Arena, GSStack}, + captureNewHeads()); + + EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre( + AllOf(state(4), parsedSymbol(&SemiTerminal), + parents({GSSNode1, GSSNode2})), + AllOf(state(5), parsedSymbol(&SemiTerminal), + parents({GSSNode3})))) + << NewHeadResults; } TEST_F(GLRTest, ReduceConflictsSplitting) { @@ -142,29 +147,25 @@ TEST_F(GLRTest, ReduceConflictsSplitting) { {"class-name := IDENTIFIER", "enum-name := IDENTIFIER"}); LRTable Table = LRTable::buildForTests( - G->table(), { - {/*State=*/0, id("class-name"), Action::goTo(2)}, - {/*State=*/0, id("enum-name"), Action::goTo(3)}, - {/*State=*/1, tokenSymbol(tok::l_brace), - Action::reduce(ruleFor("class-name"))}, - {/*State=*/1, tokenSymbol(tok::l_brace), - Action::reduce(ruleFor("enum-name"))}, - }); + G->table(), {{/*State=*/0, id("class-name"), Action::goTo(2)}, + {/*State=*/0, id("enum-name"), Action::goTo(3)}}); const auto *GSSNode0 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); const auto *GSSNode1 = - GSStack.addNode(1, &Arena.createTerminal(tok::identifier, 0), {GSSNode0}); - - std::vector<const GSS::Node *> Heads = {GSSNode1}; - glrReduce(Heads, tokenSymbol(tok::l_brace), {*G, Table, Arena, GSStack}); - EXPECT_THAT(Heads, UnorderedElementsAre( - GSSNode1, - AllOf(state(2), parsedSymbolID(id("class-name")), - parents({GSSNode0})), - AllOf(state(3), parsedSymbolID(id("enum-name")), - parents({GSSNode0})))) - << Heads; + GSStack.addNode(3, &Arena.createTerminal(tok::identifier, 0), {GSSNode0}); + + std::vector<ParseStep> PendingReduce = { + {GSSNode1, Action::reduce(ruleFor("class-name"))}, + {GSSNode1, Action::reduce(ruleFor("enum-name"))}}; + glrReduce(PendingReduce, {*G, Table, Arena, GSStack}, + captureNewHeads()); + EXPECT_THAT(NewHeadResults, + testing::UnorderedElementsAre( + AllOf(state(2), parsedSymbolID(id("class-name")), + parents({GSSNode0})), + AllOf(state(3), parsedSymbolID(id("enum-name")), + parents({GSSNode0})))) << NewHeadResults; } TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) { @@ -190,25 +191,22 @@ TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) { LRTable Table = LRTable::buildForTests( G->table(), - { - {/*State=*/2, id("ptr-operator"), Action::goTo(/*NextState=*/5)}, - {/*State=*/3, id("ptr-operator"), Action::goTo(/*NextState=*/6)}, - {/*State=*/4, tokenSymbol(tok::identifier), - Action::reduce(ruleFor("ptr-operator"))}, - }); - std::vector<const GSS::Node *> Heads = {GSSNode4}; - glrReduce(Heads, tokenSymbol(tok::identifier), {*G, Table, Arena, GSStack}); - - EXPECT_THAT(Heads, UnorderedElementsAre( - GSSNode4, - AllOf(state(5), parsedSymbolID(id("ptr-operator")), - parents({GSSNode2})), - AllOf(state(6), parsedSymbolID(id("ptr-operator")), - parents({GSSNode3})))) - << Heads; + {{/*State=*/2, id("ptr-operator"), Action::goTo(/*NextState=*/5)}, + {/*State=*/3, id("ptr-operator"), Action::goTo(/*NextState=*/6)}}); + std::vector<ParseStep> PendingReduce = { + {GSSNode4, Action::reduce(ruleFor("ptr-operator"))}}; + glrReduce(PendingReduce, {*G, Table, Arena, GSStack}, + captureNewHeads()); + + EXPECT_THAT(NewHeadResults, + testing::UnorderedElementsAre( + AllOf(state(5), parsedSymbolID(id("ptr-operator")), + parents({GSSNode2})), + AllOf(state(6), parsedSymbolID(id("ptr-operator")), + parents({GSSNode3})))) << NewHeadResults; // Verify that the payload of the two new heads is shared, only a single // ptr-operator node is created in the forest. - EXPECT_EQ(Heads[1]->Payload, Heads[2]->Payload); + EXPECT_EQ(NewHeadResults[0]->Payload, NewHeadResults[1]->Payload); } TEST_F(GLRTest, ReduceJoiningWithMultipleBases) { @@ -240,28 +238,28 @@ TEST_F(GLRTest, ReduceJoiningWithMultipleBases) { GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode, /*Parents=*/{GSSNode2}); - // FIXME: figure out a way to get rid of the hard-coded reduce RuleID! LRTable Table = LRTable::buildForTests( G->table(), + {{/*State=*/1, id("type-name"), Action::goTo(/*NextState=*/5)}, + {/*State=*/2, id("type-name"), Action::goTo(/*NextState=*/5)}}); + // FIXME: figure out a way to get rid of the hard-coded reduce RuleID! + std::vector<ParseStep> PendingReduce = { { - {/*State=*/1, id("type-name"), Action::goTo(/*NextState=*/5)}, - {/*State=*/2, id("type-name"), Action::goTo(/*NextState=*/5)}, - {/*State=*/3, tokenSymbol(tok::l_paren), - Action::reduce(/* type-name := class-name */ 0)}, - {/*State=*/4, tokenSymbol(tok::l_paren), - Action::reduce(/* type-name := enum-name */ 1)}, - }); - std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4}; - glrReduce(Heads, tokenSymbol(tok::l_paren), {*G, Table, Arena, GSStack}); + GSSNode3, Action::reduce(/*RuleID=*/0) // type-name := class-name + }, + { + GSSNode4, Action::reduce(/*RuleID=*/1) // type-name := enum-name + }}; + glrReduce(PendingReduce, {*G, Table, Arena, GSStack}, + captureNewHeads()); // Verify that the stack heads are joint at state 5 after reduces. - EXPECT_THAT(Heads, UnorderedElementsAre(GSSNode3, GSSNode4, - AllOf(state(5), - parsedSymbolID(id("type-name")), - parents({GSSNode1, GSSNode2})))) - << Heads; + EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre(AllOf( + state(5), parsedSymbolID(id("type-name")), + parents({GSSNode1, GSSNode2})))) + << NewHeadResults; // Verify that we create an ambiguous ForestNode of two parses of `type-name`. - EXPECT_EQ(Heads.back()->Payload->dumpRecursive(*G), + EXPECT_EQ(NewHeadResults.front()->Payload->dumpRecursive(*G), "[ 1, end) type-name := <ambiguous>\n" "[ 1, end) ├─type-name := class-name\n" "[ 1, end) │ └─class-name := <opaque>\n" @@ -298,24 +296,24 @@ TEST_F(GLRTest, ReduceJoiningWithSameBase) { GSStack.addNode(/*State=*/4, /*ForestNode=*/StartTerminal, /*Parents=*/{GSSNode2}); - // FIXME: figure out a way to get rid of the hard-coded reduce RuleID! LRTable Table = LRTable::buildForTests( - G->table(), { - {/*State=*/0, id("pointer"), Action::goTo(5)}, - {3, tokenSymbol(tok::l_paren), - Action::reduce(/* pointer := class-name */ 0)}, - {4, tokenSymbol(tok::l_paren), - Action::reduce(/* pointer := enum-name */ 1)}, - }); - std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4}; - glrReduce(Heads, tokenSymbol(tok::l_paren), {*G, Table, Arena, GSStack}); - - EXPECT_THAT( - Heads, UnorderedElementsAre(GSSNode3, GSSNode4, + G->table(), {{/*State=*/0, id("pointer"), Action::goTo(5)}}); + // FIXME: figure out a way to get rid of the hard-coded reduce RuleID! + std::vector<ParseStep> PendingReduce = { + { + GSSNode3, Action::reduce(/*RuleID=*/0) // pointer := class-name * + }, + { + GSSNode4, Action::reduce(/*RuleID=*/1) // pointer := enum-name * + }}; + glrReduce(PendingReduce, {*G, Table, Arena, GSStack}, + captureNewHeads()); + + EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre( AllOf(state(5), parsedSymbolID(id("pointer")), parents({GSSNode0})))) - << Heads; - EXPECT_EQ(Heads.back()->Payload->dumpRecursive(*G), + << NewHeadResults; + EXPECT_EQ(NewHeadResults.front()->Payload->dumpRecursive(*G), "[ 0, end) pointer := <ambiguous>\n" "[ 0, end) ├─pointer := class-name *\n" "[ 0, 1) │ ├─class-name := <opaque>\n" _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
