sammccall created this revision.
sammccall added a reviewer: hokein.
Herald added a subscriber: mgrang.
Herald added a project: All.
sammccall requested review of this revision.
Herald added subscribers: cfe-commits, alextsao1999.
Herald added a project: clang-tools-extra.
Here is the version where ownership is managed by smart-pointers.
It uses some thread_local magic but it's not hairy, and it seems much easier to
reason about to me.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D126347
Files:
clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/unittests/GLRTest.cpp
Index: clang-tools-extra/pseudo/unittests/GLRTest.cpp
===================================================================
--- clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -36,10 +36,10 @@
MATCHER_P(parsedSymbol, FNode, "") { return arg->Payload == FNode; }
MATCHER_P(parsedSymbolID, SID, "") { return arg->Payload->symbol() == SID; }
-testing::Matcher<const GSS::Node *>
-parents(llvm::ArrayRef<const GSS::Node *> Parents) {
- return testing::Property(&GSS::Node::parents,
- testing::UnorderedElementsAreArray(Parents));
+testing::Matcher<const GSS::NodePtr &>
+parents(llvm::ArrayRef<GSS::NodePtr> Parents) {
+ return testing::Pointee(testing::Property(
+ &GSS::Node::parents, testing::UnorderedElementsAreArray(Parents)));
}
class GLRTest : public ::testing::Test {
@@ -84,22 +84,14 @@
}
NewHeadCallback captureNewHeads() {
- return [this](const GSS::Node *NewHead) {
- GSStack.ref(NewHead);
- NewHeadResults.push_back(NewHead);
- };
+ return [this](GSS::NodePtr P) { NewHeadResults.push_back(std::move(P)); };
};
protected:
- ~GLRTest() {
- for (auto *N : NewHeadResults)
- GSStack.unref(N);
- }
-
std::unique_ptr<Grammar> G;
ForestArena Arena;
GSS GSStack;
- std::vector<const GSS::Node*> NewHeadResults;
+ std::vector<GSS::NodePtr> NewHeadResults;
};
TEST_F(GLRTest, ShiftMergingHeads) {
@@ -113,15 +105,14 @@
// 0---1---4
// â---2---â
// â---3---5
- auto *GSSNode0 =
+ auto GSSNode0 =
GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
- auto *GSSNode1 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
+ auto GSSNode1 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
/*Parents=*/{GSSNode0});
- auto *GSSNode2 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
+ auto GSSNode2 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
/*Parents=*/{GSSNode0});
- auto *GSSNode3 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
- /*Parents=*/{GSSNode0});
- GSStack.unref(GSSNode0);
+ auto GSSNode3 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
+ /*Parents=*/{GSSNode0});
buildGrammar({}, {}); // Create a fake empty grammar.
LRTable T = LRTable::buildForTests(G->table(), /*Entries=*/{});
@@ -139,8 +130,7 @@
AllOf(state(4), parsedSymbol(&SemiTerminal),
parents({GSSNode1, GSSNode2})),
AllOf(state(5), parsedSymbol(&SemiTerminal),
- parents({GSSNode3}))))
- << NewHeadResults;
+ parents({GSSNode3}))));
}
TEST_F(GLRTest, ReduceConflictsSplitting) {
@@ -157,24 +147,21 @@
G->table(), {{/*State=*/0, id("class-name"), Action::goTo(2)},
{/*State=*/0, id("enum-name"), Action::goTo(3)}});
- const auto *GSSNode0 =
+ auto GSSNode0 =
GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
- const auto *GSSNode1 =
+ auto GSSNode1 =
GSStack.addNode(3, &Arena.createTerminal(tok::identifier, 0), {GSSNode0});
- GSStack.unref(GSSNode0);
- GSStack.ref(GSSNode1);
std::vector<ParseStep> PendingReduce = {
{GSSNode1, Action::reduce(ruleFor("class-name"))},
{GSSNode1, Action::reduce(ruleFor("enum-name"))}};
- glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
- captureNewHeads());
+ 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;
+ parents({GSSNode0}))));
}
TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) {
@@ -190,15 +177,13 @@
auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/0);
auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/0);
- const auto *GSSNode2 =
+ auto GSSNode2 =
GSStack.addNode(/*State=*/2, /*ForestNode=*/ClassNameNode, /*Parents=*/{});
- const auto *GSSNode3 =
+ auto GSSNode3 =
GSStack.addNode(/*State=*/3, /*ForestNode=*/EnumNameNode, /*Parents=*/{});
- const auto *GSSNode4 = GSStack.addNode(
+ auto GSSNode4 = GSStack.addNode(
/*State=*/4, &Arena.createTerminal(tok::star, /*TokenIndex=*/1),
/*Parents=*/{GSSNode2, GSSNode3});
- GSStack.unref(GSSNode2);
- GSStack.unref(GSSNode3);
LRTable Table = LRTable::buildForTests(
G->table(),
@@ -214,7 +199,7 @@
AllOf(state(5), parsedSymbolID(id("ptr-operator")),
parents({GSSNode2})),
AllOf(state(6), parsedSymbolID(id("ptr-operator")),
- parents({GSSNode3})))) << NewHeadResults;
+ parents({GSSNode3}))));
// Verify that the payload of the two new heads is shared, only a single
// ptr-operator node is created in the forest.
EXPECT_EQ(NewHeadResults[0]->Payload, NewHeadResults[1]->Payload);
@@ -236,21 +221,16 @@
auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/1);
auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/1);
- const auto *GSSNode0 =
+ auto GSSNode0 =
GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
- const auto *GSSNode1 = GSStack.addNode(
+ auto GSSNode1 = GSStack.addNode(
/*State=*/1, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0});
- const auto *GSSNode2 = GSStack.addNode(
+ auto GSSNode2 = GSStack.addNode(
/*State=*/2, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0});
- const auto *GSSNode3 =
- GSStack.addNode(/*State=*/3, /*ForestNode=*/ClassNameNode,
- /*Parents=*/{GSSNode1});
- const auto *GSSNode4 =
- GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode,
- /*Parents=*/{GSSNode2});
- GSStack.unref(GSSNode0);
- GSStack.unref(GSSNode1);
- GSStack.unref(GSSNode2);
+ auto GSSNode3 = GSStack.addNode(/*State=*/3, /*ForestNode=*/ClassNameNode,
+ /*Parents=*/{GSSNode1});
+ auto GSSNode4 = GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode,
+ /*Parents=*/{GSSNode2});
LRTable Table = LRTable::buildForTests(
G->table(),
@@ -270,8 +250,7 @@
// Verify that the stack heads are joint at state 5 after reduces.
EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre(AllOf(
state(5), parsedSymbolID(id("type-name")),
- parents({GSSNode1, GSSNode2}))))
- << NewHeadResults;
+ parents({GSSNode1, GSSNode2}))));
// Verify that we create an ambiguous ForestNode of two parses of `type-name`.
EXPECT_EQ(NewHeadResults.front()->Payload->dumpRecursive(*G),
"[ 1, end) type-name := <ambiguous>\n"
@@ -295,23 +274,20 @@
auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/0);
auto *StartTerminal = &Arena.createTerminal(tok::star, /*TokenIndex=*/1);
- const auto *GSSNode0 =
+ auto GSSNode0 =
GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
- const auto *GSSNode1 =
+ auto GSSNode1 =
GSStack.addNode(/*State=*/1, /*ForestNode=*/ClassNameNode,
/*Parents=*/{GSSNode0});
- const auto *GSSNode2 =
+ auto GSSNode2 =
GSStack.addNode(/*State=*/2, /*ForestNode=*/EnumNameNode,
/*Parents=*/{GSSNode0});
- const auto *GSSNode3 =
+ auto GSSNode3 =
GSStack.addNode(/*State=*/3, /*ForestNode=*/StartTerminal,
/*Parents=*/{GSSNode1});
- const auto *GSSNode4 =
+ auto GSSNode4 =
GSStack.addNode(/*State=*/4, /*ForestNode=*/StartTerminal,
/*Parents=*/{GSSNode2});
- GSStack.unref(GSSNode0);
- GSStack.unref(GSSNode1);
- GSStack.unref(GSSNode2);
LRTable Table = LRTable::buildForTests(
G->table(), {{/*State=*/0, id("pointer"), Action::goTo(5)}});
@@ -328,8 +304,7 @@
EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre(
AllOf(state(5), parsedSymbolID(id("pointer")),
- parents({GSSNode0}))))
- << NewHeadResults;
+ parents({GSSNode0}))));
EXPECT_EQ(NewHeadResults.front()->Payload->dumpRecursive(*G),
"[ 0, end) pointer := <ambiguous>\n"
"[ 0, end) ââpointer := class-name *\n"
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===================================================================
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -29,7 +29,7 @@
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const GSS::Node &N) {
std::vector<std::string> ParentStates;
- for (const auto *Parent : N.parents())
+ for (const auto &Parent : N.parents())
ParentStates.push_back(llvm::formatv("{0}", Parent->State));
OS << llvm::formatv("state {0}, parsed symbol {1}, parents {{{2}}, refcount={3}",
N.State, N.Payload ? N.Payload->symbol() : 0,
@@ -48,9 +48,9 @@
Queue.pop_back();
if (!Seen.insert(N).second)
continue;
- for (const auto *P : N->parents()) {
- ++Expected[P];
- Queue.push_back(P);
+ for (const auto &P : N->parents()) {
+ ++Expected[P.get()];
+ Queue.push_back(P.get());
}
}
bool AnyWrong = false;
@@ -77,19 +77,16 @@
// Lists of active shift, reduce, accept actions.
std::vector<ParseStep> PendingShift, PendingReduce, PendingAccept;
- auto AddSteps = [&](const GSS::Node *Head, SymbolID NextTok) {
+ auto AddSteps = [&](const GSS::NodePtr &Head, SymbolID NextTok) {
for (const auto &Action : Params.Table.getActions(Head->State, NextTok)) {
switch (Action.kind()) {
case LRTable::Action::Shift:
- GSS.ref(Head);
PendingShift.push_back({Head, Action});
break;
case LRTable::Action::Reduce:
- GSS.ref(Head);
PendingReduce.push_back({Head, Action});
break;
case LRTable::Action::Accept:
- GSS.ref(Head);
PendingAccept.push_back({Head, Action});
break;
default:
@@ -97,16 +94,18 @@
}
}
};
- std::vector<const GSS::Node *> NewHeads = {
+ std::vector<GSS::NodePtr> NewHeads = {
GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
/*ForestNode=*/nullptr, {})};
auto CheckRefcounts = [&] {
DEBUG_WITH_TYPE("GSSNode", {
- std::vector<const GSS::Node *> Roots = NewHeads;
+ std::vector<const GSS::Node *> Roots;
+ for (const auto &H : NewHeads)
+ Roots.push_back(H.get());
for (const auto *Pending :
{&PendingShift, &PendingReduce, &PendingAccept})
for (const ParseStep &Step : *Pending)
- Roots.push_back(Step.Head);
+ Roots.push_back(Step.Head.get());
checkRefcounts(Roots);
});
};
@@ -115,38 +114,31 @@
G.symbolName(Terminal.symbol()),
Terminal.symbol()));
CheckRefcounts();
- for (const auto *Head : NewHeads) {
+ for (const auto &Head : NewHeads)
AddSteps(Head, Terminal.symbol());
- GSS.unref(Head);
- }
NewHeads.clear();
CheckRefcounts();
LLVM_DEBUG(llvm::dbgs() << " Reduce\n");
- glrReduce(PendingReduce, Params,
- [&](const GSS::Node * NewHead) {
- // A reduce will enable more steps.
- AddSteps(NewHead, Terminal.symbol());
- });
+ glrReduce(PendingReduce, Params, [&](GSS::NodePtr NewHead) {
+ // A reduce will enable more steps.
+ AddSteps(NewHead, Terminal.symbol());
+ });
CheckRefcounts();
- glrShift(PendingShift, Terminal, Params, [&](const GSS::Node *NewHead) {
- GSS.ref(NewHead);
- NewHeads.push_back(NewHead);
+ glrShift(PendingShift, Terminal, Params, [&](GSS::NodePtr NewHead) {
+ NewHeads.push_back(std::move(NewHead));
});
}
LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next is eof\n"));
CheckRefcounts();
- for (const auto *Head : NewHeads) {
+ for (const auto &Head : NewHeads)
AddSteps(Head, tokenSymbol(tok::eof));
- GSS.unref(Head);
- }
NewHeads.clear();
CheckRefcounts();
- glrReduce(PendingReduce, Params,
- [&](const GSS::Node * NewHead) {
- // A reduce will enable more steps.
- AddSteps(NewHead, tokenSymbol(tok::eof));
- });
+ glrReduce(PendingReduce, Params, [&](GSS::NodePtr NewHead) {
+ // A reduce will enable more steps.
+ AddSteps(NewHead, tokenSymbol(tok::eof));
+ });
CheckRefcounts();
assert(PendingShift.empty());
@@ -160,9 +152,7 @@
<< "\n";
});
assert(PendingAccept.size() == 1);
- auto *Result = PendingAccept.front().Head->Payload;
- GSS.unref(PendingAccept.front().Head);
- return *Result;
+ return *PendingAccept.front().Head->Payload;
}
// We failed to parse the input, returning an opaque forest node for recovery.
return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
@@ -183,7 +173,6 @@
// â---3---â
void glrShift(std::vector<ParseStep> &PendingShift, const ForestNode &NewTok,
const ParseParams &Params, NewHeadCallback NewHeadCB) {
- auto &GSS = Params.GSStack;
assert(NewTok.kind() == ForestNode::Terminal);
assert(llvm::all_of(PendingShift,
[](const ParseStep &Step) {
@@ -199,7 +188,7 @@
return L.Action.getShiftState() < R.Action.getShiftState();
});
auto Rest = llvm::makeArrayRef(PendingShift);
- llvm::SmallVector<const GSS::Node *> Parents;
+ llvm::SmallVector<GSS::NodePtr> 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.
@@ -209,18 +198,14 @@
for (const auto &Base : Rest) {
if (Base.Action.getShiftState() != NextState)
break;
- Parents.push_back(Base.Head); // safe borrow
+ 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()));
- const auto *NewHead = Params.GSStack.addNode(NextState, &NewTok, Parents);
- NewHeadCB(NewHead);
- GSS.unref(NewHead);
+ NewHeadCB(Params.GSStack.addNode(NextState, &NewTok, Parents));
}
- for (const auto & PS : PendingShift)
- GSS.unref(PS.Head);
PendingShift.clear();
}
@@ -281,7 +266,6 @@
// 0--5(pointer) // 5 is goto(0, pointer)
void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
NewHeadCallback NewHeadCB) {
- auto &GSS = Params.GSStack;
// 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).
@@ -333,7 +317,7 @@
// base includes an item X := ... ⢠S ... and since the grammar is
// context-free, *all* parses of S are valid here.
// FIXME: reuse the queues across calls instead of reallocating.
- KeyedQueue<Family, const GSS::Node *> Bases;
+ KeyedQueue<Family, GSS::NodePtr> Bases;
// A sequence is the ForestNode payloads of the GSS nodes we are reducing.
// These are the RHS of the rule, the RuleID is stored in the Family.
@@ -344,38 +328,35 @@
Sequence TempSequence;
// 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) {
+ auto Pop = [&](const GSS::NodePtr &Head, RuleID RID) {
LLVM_DEBUG(llvm::dbgs() << " Pop " << Params.G.dumpRule(RID) << "\n");
const auto &Rule = Params.G.lookupRule(RID);
Family F{/*Start=*/0, /*Symbol=*/Rule.Target, /*Rule=*/RID};
TempSequence.resize_for_overwrite(Rule.Size);
- auto DFS = [&](const GSS::Node *N, unsigned I, auto &DFS) {
+ auto DFS = [&](const GSS::NodePtr &N, unsigned I, auto &DFS) {
if (I == Rule.Size) {
F.Start = TempSequence.front()->startTokenIndex();
- GSS.ref(N);
Bases.emplace(F, N);
LLVM_DEBUG(llvm::dbgs() << " --> base at S" << N->State << "\n");
Sequences.emplace(F, TempSequence);
return;
}
TempSequence[Rule.Size - 1 - I] = N->Payload;
- for (const GSS::Node *Parent : N->parents())
+ for (const auto &Parent : N->parents())
DFS(Parent, I + 1, DFS);
};
DFS(Head, 0, DFS);
};
auto PopPending = [&] {
- for (const ParseStep &Pending : PendingReduce) {
+ for (const ParseStep &Pending : PendingReduce)
Pop(Pending.Head, Pending.Action.getReduceRule());
- GSS.unref(Pending.Head);
- }
PendingReduce.clear();
};
- std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases;
+ std::vector<std::pair</*Goto*/ StateID, GSS::NodePtr>> FamilyBases;
std::vector<std::pair<RuleID, Sequence>> FamilySequences;
- std::vector<const GSS::Node *> TempGSSNodes;
+ std::vector<GSS::NodePtr> TempGSSNodes;
std::vector<const ForestNode *> TempForestNodes;
// Main reduction loop:
@@ -416,18 +397,14 @@
// Grab the bases for this family.
// As well as deduplicating them, we'll group by the goto state.
do {
- FamilyBases.emplace_back(
- Params.Table.getGoToState(Bases.top().second->State, F.Symbol),
- Bases.top().second); // transfer ownership
+ StateID State =
+ Params.Table.getGoToState(Bases.top().second->State, F.Symbol);
+ FamilyBases.emplace_back(State, std::move(Bases.top().second));
Bases.pop();
} while (!Bases.empty() && Bases.top().first == F);
- llvm::sort(FamilyBases);
- // XXX sortAndUnique is not aware of ref/unref, copy for simplicity.
- std::vector<decltype(FamilyBases)::value_type> UniqueBases;
- std::unique_copy(FamilyBases.begin(), FamilyBases.end(),
- std::back_inserter(UniqueBases));
+ sortAndUnique(FamilyBases);
// Create a GSS node for each unique goto state.
- llvm::ArrayRef<decltype(FamilyBases)::value_type> BasesLeft = UniqueBases;
+ llvm::ArrayRef<decltype(FamilyBases)::value_type> BasesLeft = FamilyBases;
while (!BasesLeft.empty()) {
StateID NextState = BasesLeft.front().first;
auto &Parents = TempGSSNodes;
@@ -435,18 +412,14 @@
for (const auto &Base : BasesLeft) {
if (Base.first != NextState)
break;
- Parents.push_back(Base.second); // safe borrow
+ Parents.push_back(Base.second);
}
BasesLeft = BasesLeft.drop_front(Parents.size());
// Invoking the callback for new heads, a real GLR parser may add new
// reduces to the PendingReduce queue!
- const auto *NewNode = Params.GSStack.addNode(NextState, Parsed, Parents);
- NewHeadCB(NewNode);
- GSS.unref(NewNode);
+ NewHeadCB(Params.GSStack.addNode(NextState, Parsed, Parents));
}
- for (auto &FB : FamilyBases)
- GSS.unref(FB.second);
FamilyBases.clear();
PopPending();
}
@@ -458,35 +431,30 @@
<< Sigil << " " << N << " " << *N << "\n");
}
-const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
- llvm::ArrayRef<const Node *> Parents) {
+GSS::NodePtr GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+ llvm::ArrayRef<NodePtr> Parents) {
++NodesCreated;
Node *Result = new (allocate(Parents.size()))
Node({State, static_cast<uint16_t>(Parents.size()), /*RefCount=*/0});
Result->Payload = Symbol;
- auto *ParentArray = reinterpret_cast<const Node **>(Result + 1);
- for (const auto *Parent : Parents) {
- ref(Parent);
- *ParentArray++ = Parent;
- }
+ auto *ParentArray = reinterpret_cast<NodePtr *>(Result + 1);
+ for (const auto &Parent : Parents)
+ new (ParentArray++) NodePtr(Parent);
logLifetime("*", Result);
- ref(Result);
- return Result;
+ return NodePtr(Result);
}
-void GSS::ref(const Node *N) {
- const_cast<Node *>(N)->RefCount++;
+void GSS::ref(Node *N) {
+ N->RefCount++;
logLifetime("+", N);
}
-void GSS::unref(const Node *N) {
+void GSS::unref(Node *N) {
assert(N->RefCount != 0);
- Node *NN = const_cast<Node *>(N); // I created you, and I can destroy you!
- --NN->RefCount;
+ --N->RefCount;
logLifetime("-", N);
- // Node is const from the caller's perspective, but we created it
- if (0 == NN->RefCount)
- destroy(NN);
+ if (0 == N->RefCount)
+ destroy(N);
}
GSS::Node *GSS::allocate(unsigned Parents) {
@@ -500,21 +468,32 @@
}
++NodesAllocated;
return static_cast<Node *>(
- Arena.Allocate(sizeof(Node) + Parents * sizeof(Node *), alignof(Node)));
+ Arena.Allocate(sizeof(Node) + Parents * sizeof(NodePtr), alignof(Node)));
}
void GSS::destroy(Node *N) {
logLifetime("~", N);
++NodesDestroyed;
- for (auto *Parent : N->parents())
- unref(Parent);
unsigned ParentCount = N->ParentCount;
+ for (auto &Parent : N->parents())
+ Parent.~NodePtr();
N->~Node();
assert(FreeList.size() > ParentCount && "established on construction!");
FreeList[ParentCount].push_back(N);
}
-GSS::~GSS() { assert(NodesCreated == NodesDestroyed); }
+GSS::GSS() {
+ assert(Current == nullptr);
+ Current = this;
+}
+
+GSS::~GSS() {
+ assert(Current == this);
+ assert(NodesCreated == NodesDestroyed);
+ Current = nullptr;
+}
+
+thread_local GSS *GSS::Current = nullptr;
} // namespace pseudo
} // namespace clang
Index: clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
===================================================================
--- clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
+++ clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
@@ -54,8 +54,58 @@
//
// The parser is responsible for creating nodes and keeping track of the set of
// heads. The GSS class is mostly an arena for them.
+//
+// GSS is bound to a single thread, and there can only be one GSS per thread.
+// (Thread-local state is used to implement NodePtr without extra storage).
struct GSS {
+private:
+ static thread_local GSS *Current;
+
+public:
+ GSS();
~GSS();
+
+ struct Node;
+ // A smart-pointer for GSS nodes, which are refcounted.
+ class NodePtr {
+ public:
+ using element_type = const Node;
+ ~NodePtr() {
+ if (P)
+ Current->unref(P);
+ }
+ NodePtr() {}
+ explicit NodePtr(Node *N) : P(N) { Current->ref(P); }
+ NodePtr(const NodePtr &O) : P(O.P) { Current->ref(P); }
+ NodePtr(NodePtr &&O) { std::swap(O.P, P); }
+ NodePtr &operator=(const NodePtr &O) {
+ P = O.P;
+ Current->ref(P);
+ return *this;
+ }
+ NodePtr &operator=(NodePtr &&O) {
+ std::swap(O.P, P);
+ return *this;
+ }
+
+ const Node *get() const { return P; }
+ const Node &operator*() const { return *P; }
+ const Node *operator->() const { return P; }
+ friend bool operator==(const NodePtr &A, const NodePtr &B) {
+ return A.P == B.P;
+ }
+ friend bool operator<(const NodePtr &A, const NodePtr &B) {
+ return A.P < B.P;
+ }
+ friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const NodePtr &N) {
+ return OS << N.P;
+ }
+
+ private:
+ Node *P = nullptr;
+ };
+
// A node represents a partial parse of the input up to some point.
//
// It is the equivalent of a frame in an LR parse stack.
@@ -66,7 +116,7 @@
// Nodes are not exactly pushed and popped on the stack: pushing is just
// allocating a new head node with a parent pointer to the old head. Popping
// is just forgetting about a node and remembering its parent instead.
- struct alignas(struct Node *) Node {
+ struct alignas(class NodePtr) Node {
// LR state describing how parsing should continue from this head.
LRTable::StateID State;
// Number of the parents of this node.
@@ -81,20 +131,18 @@
// (In the literature, the node is attached to the *edge* to the parent).
const ForestNode *Payload = nullptr;
- llvm::ArrayRef<const Node *> parents() const {
- return llvm::makeArrayRef(reinterpret_cast<const Node *const *>(this + 1),
- ParentCount);
+ llvm::ArrayRef<NodePtr> parents() const {
+ return llvm::makeArrayRef(
+ reinterpret_cast<NodePtr *>(const_cast<Node *>(this) + 1),
+ ParentCount);
};
- // Parents are stored as a trailing array of Node*.
+ // Parents are stored as a trailing array of NodePtr.
};
// Allocates a new node in the graph.
// It has a refcount of 1, and should be pased to deref() when done.
- const Node *addNode(LRTable::StateID State, const ForestNode *Symbol,
- llvm::ArrayRef<const Node *> Parents);
- void ref(const Node *N);
- void unref(const Node *N);
-
+ NodePtr addNode(LRTable::StateID State, const ForestNode *Symbol,
+ llvm::ArrayRef<NodePtr> Parents);
size_t bytes() const { return Arena.getTotalMemory() + sizeof(*this); }
size_t nodeCount() const { return NodesCreated; }
@@ -103,6 +151,8 @@
// They are variable size, so use one free-list per distinct #parents.
std::vector<std::vector<Node *>> FreeList;
+ void ref(Node *N);
+ void unref(Node *N);
Node *allocate(unsigned Parents);
void destroy(Node *N);
@@ -139,13 +189,13 @@
// A step is any one action applied to any one stack head.
struct ParseStep {
// A specific stack head.
- const GSS::Node *Head = nullptr;
+ GSS::NodePtr Head;
// 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 *)>;
+using NewHeadCallback = std::function<void(GSS::NodePtr)>;
// Apply all PendingShift actions on a given GSS state, newly-created heads are
// passed to the callback.
//
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
