29767047230

Committed 20 Jul 2026 06:16PM UTC coverage: 90.628% (+0.05%) from 90.582%

Build # 29767047230

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #48 from rieske/perf/parser/2-automaton

perf(parser): core-hash automaton and worklist closure

Coverage Stats

187 of 192 new or added lines in 7 files covered. (97.4%)

5212 of 5751 relevant lines covered (90.63%)

162489.24 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.24

/src/parser/CanonicalCollection.cpp

#include "CanonicalCollection.h"

#include "util/LogManager.h"
#include "util/Logger.h"

#include <algorithm>
#include <cstdint>
#include <deque>
#include <unordered_map>
#include <utility>
#include <vector>

namespace {

Logger& logger = LogManager::getComponentLogger(Component::PARSER);

using namespace parser;


void closeItemSet(
        const FirstTable& first,
        const Grammar& grammar,
        GenerationBuffers& buffers,
        std::vector<LR1Item>& items) {
    auto& coreIndex = buffers.coreIndex;
    auto& worklist = buffers.worklist;
    buffers.prepareClosure(items.size());

    for (std::size_t i = 0; i < items.size(); ++i) {
        coreIndex.emplace(items[i].coreKey(), i);
        worklist.push_back(i);
    }
    items.reserve(std::max(items.capacity(), items.size() + 64));

    std::size_t head = 0;
    while (head < worklist.size()) {
        const std::size_t index = worklist[head++];
        if (!items[index].hasUnvisitedSymbols() || grammar.isTerminal(items[index].nextUnvisitedSymbol())) {
            continue;
        }

        const int B = items[index].nextUnvisitedSymbol();
        const LR1Item::LookaheadSet propagated = items[index].hasSymbolsAfterNext()
                ? first.firstBits(items[index].symbolAfterNext())
                : items[index].lookaheads();

        for (const auto& production : grammar.getProductionsOfSymbol(B)) {
            const std::uint64_t key =
                    (static_cast<std::uint64_t>(static_cast<std::uint32_t>(production.getId())) << 32);
            const auto existing = coreIndex.find(key);
            if (existing == coreIndex.end()) {
                items.emplace_back(production, propagated);
                const std::size_t newIndex = items.size() - 1;
                coreIndex.emplace(key, newIndex);
                worklist.push_back(newIndex);
            } else if (items[existing->second].mergeLookaheads(propagated)) {
                worklist.push_back(existing->second);
            }
        }
    }

    // Closed sets are sorted by core so LALR merge is a linear zip and
    // core signatures need no extra sort.
    std::sort(items.begin(), items.end(), [](const LR1Item& left, const LR1Item& right) {
        return left.coreKey() < right.coreKey();
    });
}

std::unordered_map<int, std::vector<LR1Item>> gotoAllFrom(
        const std::vector<LR1Item>& I,
        const FirstTable& first,
        const Grammar& grammar,
        GenerationBuffers& buffers) {
    std::unordered_map<int, std::vector<LR1Item>> bySymbol;
    bySymbol.reserve(I.size());
    for (const auto& item : I) {
        if (item.hasUnvisitedSymbols()) {
            bySymbol[item.nextUnvisitedSymbol()].push_back(item.advance());
        }
    }
    for (auto& entry : bySymbol) {
        entry.second.reserve(entry.second.size() + 16);
        closeItemSet(first, grammar, buffers, entry.second);
    }
    return bySymbol;
}

// --- LALR(1) ---

// items must be sorted by coreKey (closeItemSet invariant).
std::vector<std::uint64_t> makeCoreSignature(const std::vector<LR1Item>& items, GenerationBuffers& buffers) {
    auto& signature = buffers.coreSignature;
    signature.clear();
    signature.reserve(items.size());
    for (const auto& item : items) {
        signature.push_back(item.coreKey());
    }
    return signature;
}

struct CoreSignatureHash {
    std::size_t operator()(const std::vector<std::uint64_t>& signature) const noexcept {
        std::size_t hash = signature.size();
        for (const std::uint64_t key : signature) {
            hashCombine(hash, key);
        }
        return hash;
    }
};

// Both sides sorted by the same cores (LALR state with matching core signature).
bool mergeLookaheadsByCore(
        std::vector<LR1Item>& existing,
        const std::vector<LR1Item>& incoming) {
    bool merged = false;
    for (std::size_t i = 0; i < existing.size(); ++i) {
        merged |= existing[i].mergeLookaheads(incoming[i].lookaheads());
    }
    return merged;
}

// Deterministic processing order: only symbols with a non-empty goto, sorted by id.
std::vector<int> sortedGotoSymbols(const std::unordered_map<int, std::vector<LR1Item>>& gotos) {
    std::vector<int> symbols;
    symbols.reserve(gotos.size());
    for (const auto& entry : gotos) {
        if (!entry.second.empty()) {
            symbols.push_back(entry.first);
        }
    }
    std::sort(symbols.begin(), symbols.end());
    return symbols;
}

void computeLALR1(
        std::vector<std::vector<LR1Item>>& canonicalCollection,
        GotoMap& computedGotos,
        const FirstTable& first,
        const Grammar& grammar,
        GenerationBuffers& buffers) {
    std::unordered_map<std::vector<std::uint64_t>, std::size_t, CoreSignatureHash> stateByCores;
    stateByCores.reserve(512);
    stateByCores.emplace(makeCoreSignature(canonicalCollection[0], buffers), 0);
    computedGotos.reserve(512);

    std::deque<std::size_t> worklist { 0 };
    std::vector<char> inQueue(1, 1);

    auto enqueue = [&](std::size_t state) {
        if (state >= inQueue.size()) {
            inQueue.resize(state + 1, 0);
        }
        if (!inQueue[state]) {
            inQueue[state] = 1;
            worklist.push_back(state);
        }
    };

    while (!worklist.empty()) {
        const std::size_t state = worklist.front();
        worklist.pop_front();
        inQueue[state] = 0;

        auto gotos = gotoAllFrom(canonicalCollection[state], first, grammar, buffers);
        for (const int X : sortedGotoSymbols(gotos)) {
            auto& gotoSet = gotos[X];
            auto signature = makeCoreSignature(gotoSet, buffers);
            const auto existing = stateByCores.find(signature);
            if (existing == stateByCores.end()) {
                const std::size_t newState = canonicalCollection.size();
                canonicalCollection.push_back(std::move(gotoSet));
                stateByCores.emplace(std::move(signature), newState);
                computedGotos[{ state, X }] = newState;
                enqueue(newState);
            } else {
                const std::size_t target = existing->second;
                computedGotos[{ state, X }] = target;
                if (mergeLookaheadsByCore(canonicalCollection[target], gotoSet)) {
                    enqueue(target);
                }
            }
        }
    }
}

// --- LR(1) ---

using ItemSetSignature = std::vector<std::pair<std::uint64_t, LR1Item::LookaheadSet>>;

// items must be sorted by coreKey (closeItemSet invariant).
ItemSetSignature makeItemSetSignature(const std::vector<LR1Item>& items) {
    ItemSetSignature signature;
    signature.reserve(items.size());
    for (const auto& item : items) {
        signature.emplace_back(item.coreKey(), item.lookaheads());
    }
    return signature;
}

struct ItemSetSignatureHash {
    std::size_t operator()(const ItemSetSignature& signature) const noexcept {
        std::size_t hash = signature.size();
        for (const auto& entry : signature) {
            hashCombine(hash, entry.first);
            for (std::size_t i = 0; i < entry.second.size(); i += 64) {
                unsigned long long word = 0;
                for (std::size_t b = 0; b < 64 && i + b < entry.second.size(); ++b) {
                    if (entry.second.test(i + b)) {
                        word |= 1ULL << b;
                    }
                }
                hashCombine(hash, word);
            }
        }
        return hash;
    }
};

void computeLR1(
        std::vector<std::vector<LR1Item>>& canonicalCollection,
        GotoMap& computedGotos,
        const FirstTable& first,
        const Grammar& grammar,
        GenerationBuffers& buffers) {
    std::unordered_map<ItemSetSignature, std::size_t, ItemSetSignatureHash> stateByItems;
    stateByItems.reserve(256);
    stateByItems.emplace(makeItemSetSignature(canonicalCollection[0]), 0);

    for (std::size_t i = 0; i < canonicalCollection.size(); ++i) {
        auto gotos = gotoAllFrom(canonicalCollection[i], first, grammar, buffers);
        for (const int X : sortedGotoSymbols(gotos)) {
            auto& gotoSet = gotos[X];
            auto signature = makeItemSetSignature(gotoSet);
            const auto existing = stateByItems.find(signature);
            if (existing == stateByItems.end()) {
                const std::size_t newState = canonicalCollection.size();
                canonicalCollection.push_back(std::move(gotoSet));
                stateByItems.emplace(std::move(signature), newState);
                computedGotos[{ i, X }] = newState;
            } else {
                computedGotos[{ i, X }] = existing->second;
            }
        }
    }
}

} // namespace

namespace parser {

CanonicalCollection::CanonicalCollection(
        const FirstTable& first,
        const Grammar& grammar,
        AutomatonKind kind)
{
    std::vector<LR1Item> initialSet {
        LR1Item { grammar.getTopRule(), std::vector<int>{ grammar.getEndSymbol() }, grammar }
    };
    closeItemSet(first, grammar, buffers, initialSet);
    canonicalCollection.push_back(std::move(initialSet));

    if (kind == AutomatonKind::LALR1) {
        computeLALR1(canonicalCollection, computedGotos, first, grammar, buffers);
    } else {
        computeLR1(canonicalCollection, computedGotos, first, grammar, buffers);
    }

    logCollection(grammar);
}

std::size_t CanonicalCollection::stateCount() const noexcept {
    return canonicalCollection.size();
}

const std::vector<LR1Item>& CanonicalCollection::setOfItemsAtState(size_t state) const {
    return canonicalCollection.at(state);
}

std::size_t CanonicalCollection::goTo(std::size_t stateFrom, int symbol) const {
    return computedGotos.at({ stateFrom, symbol });
}

void CanonicalCollection::logCollection(const Grammar& grammar) const {
    if (logger.isNull()) {
        return;
    }
    logger << "\n*********************\nCanonical collection:\n*********************\n";
    int setNo = 0;
    for (const auto& setOfItems : canonicalCollection) {
        logger << "Set " << setNo++ << ":\n";
        for (const auto& item : setOfItems) {
            logger << item.str(grammar);
        }
        logger << "\n";
    }
    logger << "Computed GOTOs:\n";
    for (const auto& g : computedGotos) {
        logger << g.first.first << "\t" << g.first.second << "\t" << g.second << "\n";
    }
}

} // namespace parser

1	#include "CanonicalCollection.h"
2
3	#include "util/LogManager.h"
4	#include "util/Logger.h"
5
6	#include <algorithm>
7	#include <cstdint>
8	#include <deque>
9	#include <unordered_map>
10	#include <utility>
11	#include <vector>
12
13	namespace {
14
15	Logger& logger = LogManager::getComponentLogger(Component::PARSER);
16
17	using namespace parser;
18
19
20	void closeItemSet(	31,174✔
21	const FirstTable& first,
22	const Grammar& grammar,
23	GenerationBuffers& buffers,
24	std::vector<LR1Item>& items) {
25	auto& coreIndex = buffers.coreIndex;	31,174✔
26	auto& worklist = buffers.worklist;	31,174✔
27	buffers.prepareClosure(items.size());	31,174✔
28
29	for (std::size_t i = 0; i < items.size(); ++i) {	82,004✔
30	coreIndex.emplace(items[i].coreKey(), i);	50,830✔
31	worklist.push_back(i);	50,830✔
32	}
33	items.reserve(std::max(items.capacity(), items.size() + 64));	31,174✔
34
35	std::size_t head = 0;	31,174✔
36	while (head < worklist.size()) {	731,300✔
37	const std::size_t index = worklist[head++];	700,126✔
38	if (!items[index].hasUnvisitedSymbols() \|\| grammar.isTerminal(items[index].nextUnvisitedSymbol())) {	700,126✔
39	continue;	219,736✔
40	}
41
42	const int B = items[index].nextUnvisitedSymbol();	480,390✔
43	const LR1Item::LookaheadSet propagated = items[index].hasSymbolsAfterNext()	480,390✔
44	? first.firstBits(items[index].symbolAfterNext())	480,390✔
45	: items[index].lookaheads();	139,234✔
46
47	for (const auto& production : grammar.getProductionsOfSymbol(B)) {	2,925,254✔
48	const std::uint64_t key =
49	(static_cast<std::uint64_t>(static_cast<std::uint32_t>(production.getId())) << 32);	2,444,864✔
50	const auto existing = coreIndex.find(key);	2,444,864✔
51	if (existing == coreIndex.end()) {	2,444,864✔
52	items.emplace_back(production, propagated);	255,238✔
53	const std::size_t newIndex = items.size() - 1;	255,238✔
54	coreIndex.emplace(key, newIndex);	255,238✔
55	worklist.push_back(newIndex);	255,238✔
56	} else if (items[existing->second].mergeLookaheads(propagated)) {	2,189,626✔
57	worklist.push_back(existing->second);	394,058✔
58	}
59	}
60	}
61
62	// Closed sets are sorted by core so LALR merge is a linear zip and
63	// core signatures need no extra sort.
64	std::sort(items.begin(), items.end(), [](const LR1Item& left, const LR1Item& right) {	31,174✔
65	return left.coreKey() < right.coreKey();	1,859,974✔
66	});
67	}	31,174✔
68
69	std::unordered_map<int, std::vector<LR1Item>> gotoAllFrom(	3,606✔
70	const std::vector<LR1Item>& I,
71	const FirstTable& first,
72	const Grammar& grammar,
73	GenerationBuffers& buffers) {
74	std::unordered_map<int, std::vector<LR1Item>> bySymbol;	3,606✔
75	bySymbol.reserve(I.size());	3,606✔
76	for (const auto& item : I) {	56,572✔
77	if (item.hasUnvisitedSymbols()) {	52,966✔
78	bySymbol[item.nextUnvisitedSymbol()].push_back(item.advance());	50,814✔
79	}
80	}
81	for (auto& entry : bySymbol) {	34,764✔
82	entry.second.reserve(entry.second.size() + 16);	31,158✔
83	closeItemSet(first, grammar, buffers, entry.second);	31,158✔
84	}
85	return bySymbol;	3,606✔
NEW 86	}	×
87
88	// --- LALR(1) ---
89
90	// items must be sorted by coreKey (closeItemSet invariant).
91	std::vector<std::uint64_t> makeCoreSignature(const std::vector<LR1Item>& items, GenerationBuffers& buffers) {	20,026✔
92	auto& signature = buffers.coreSignature;	20,026✔
93	signature.clear();	20,026✔
94	signature.reserve(items.size());	20,026✔
95	for (const auto& item : items) {	233,508✔
96	signature.push_back(item.coreKey());	213,482✔
97	}
98	return signature;	20,026✔
99	}
100
101	struct CoreSignatureHash {
102	std::size_t operator()(const std::vector<std::uint64_t>& signature) const noexcept {	27,398✔
103	std::size_t hash = signature.size();	27,398✔
104	for (const std::uint64_t key : signature) {	319,968✔
105	hashCombine(hash, key);	292,570✔
106	}
107	return hash;	27,398✔
108	}
109	};
110
111	// Both sides sorted by the same cores (LALR state with matching core signature).
112	bool mergeLookaheadsByCore(	18,770✔
113	std::vector<LR1Item>& existing,
114	const std::vector<LR1Item>& incoming) {
115	bool merged = false;	18,770✔
116	for (std::size_t i = 0; i < existing.size(); ++i) {	213,696✔
117	merged \|= existing[i].mergeLookaheads(incoming[i].lookaheads());	194,926✔
118	}
119	return merged;	18,770✔
120	}
121
122	// Deterministic processing order: only symbols with a non-empty goto, sorted by id.
123	std::vector<int> sortedGotoSymbols(const std::unordered_map<int, std::vector<LR1Item>>& gotos) {	3,606✔
124	std::vector<int> symbols;	3,606✔
125	symbols.reserve(gotos.size());	3,606✔
126	for (const auto& entry : gotos) {	34,764✔
127	if (!entry.second.empty()) {	31,158✔
128	symbols.push_back(entry.first);	31,158✔
129	}
130	}
131	std::sort(symbols.begin(), symbols.end());	3,606✔
132	return symbols;	3,606✔
NEW 133	}	×
134
135	void computeLALR1(	10✔
136	std::vector<std::vector<LR1Item>>& canonicalCollection,
137	GotoMap& computedGotos,
138	const FirstTable& first,
139	const Grammar& grammar,
140	GenerationBuffers& buffers) {
141	std::unordered_map<std::vector<std::uint64_t>, std::size_t, CoreSignatureHash> stateByCores;	10✔
142	stateByCores.reserve(512);	10✔
143	stateByCores.emplace(makeCoreSignature(canonicalCollection[0], buffers), 0);	10✔
144	computedGotos.reserve(512);	10✔
145
146	std::deque<std::size_t> worklist { 0 };	30✔
147	std::vector<char> inQueue(1, 1);	10✔
148
149	auto enqueue = [&](std::size_t state) {	2,452✔
150	if (state >= inQueue.size()) {	2,452✔
151	inQueue.resize(state + 1, 0);	1,246✔
152	}
153	if (!inQueue[state]) {	2,452✔
154	inQueue[state] = 1;	2,100✔
155	worklist.push_back(state);	2,100✔
156	}
157	};	2,452✔
158
159	while (!worklist.empty()) {	2,120✔
160	const std::size_t state = worklist.front();	2,110✔
161	worklist.pop_front();	2,110✔
162	inQueue[state] = 0;	2,110✔
163
164	auto gotos = gotoAllFrom(canonicalCollection[state], first, grammar, buffers);	2,110✔
165	for (const int X : sortedGotoSymbols(gotos)) {	22,126✔
166	auto& gotoSet = gotos[X];	20,016✔
167	auto signature = makeCoreSignature(gotoSet, buffers);	20,016✔
168	const auto existing = stateByCores.find(signature);	20,016✔
169	if (existing == stateByCores.end()) {	20,016✔
170	const std::size_t newState = canonicalCollection.size();	1,246✔
171	canonicalCollection.push_back(std::move(gotoSet));	1,246✔
172	stateByCores.emplace(std::move(signature), newState);	1,246✔
173	computedGotos[{ state, X }] = newState;	1,246✔
174	enqueue(newState);	1,246✔
175	} else {
176	const std::size_t target = existing->second;	18,770✔
177	computedGotos[{ state, X }] = target;	18,770✔
178	if (mergeLookaheadsByCore(canonicalCollection[target], gotoSet)) {	18,770✔
179	enqueue(target);	1,206✔
180	}
181	}
182	}	22,126✔
183	}	2,110✔
184	}	10✔
185
186	// --- LR(1) ---
187
188	using ItemSetSignature = std::vector<std::pair<std::uint64_t, LR1Item::LookaheadSet>>;
189
190	// items must be sorted by coreKey (closeItemSet invariant).
191	ItemSetSignature makeItemSetSignature(const std::vector<LR1Item>& items) {	11,148✔
192	ItemSetSignature signature;	11,148✔
193	signature.reserve(items.size());	11,148✔
194	for (const auto& item : items) {	103,734✔
195	signature.emplace_back(item.coreKey(), item.lookaheads());	92,586✔
196	}
197	return signature;	11,148✔
NEW 198	}	×
199
200	struct ItemSetSignatureHash {
201	std::size_t operator()(const ItemSetSignature& signature) const noexcept {	20,586✔
202	std::size_t hash = signature.size();	20,586✔
203	for (const auto& entry : signature) {	212,750✔
204	hashCombine(hash, entry.first);	192,164✔
205	for (std::size_t i = 0; i < entry.second.size(); i += 64) {	576,492✔
206	unsigned long long word = 0;	384,328✔
207	for (std::size_t b = 0; b < 64 && i + b < entry.second.size(); ++b) {	24,981,320✔
208	if (entry.second.test(i + b)) {	24,596,992✔
209	word \|= 1ULL << b;	3,598,216✔
210	}
211	}
212	hashCombine(hash, word);	384,328✔
213	}
214	}
215	return hash;	20,586✔
216	}
217	};
218
219	void computeLR1(	6✔
220	std::vector<std::vector<LR1Item>>& canonicalCollection,
221	GotoMap& computedGotos,
222	const FirstTable& first,
223	const Grammar& grammar,
224	GenerationBuffers& buffers) {
225	std::unordered_map<ItemSetSignature, std::size_t, ItemSetSignatureHash> stateByItems;	6✔
226	stateByItems.reserve(256);	6✔
227	stateByItems.emplace(makeItemSetSignature(canonicalCollection[0]), 0);	6✔
228
229	for (std::size_t i = 0; i < canonicalCollection.size(); ++i) {	1,502✔
230	auto gotos = gotoAllFrom(canonicalCollection[i], first, grammar, buffers);	1,496✔
231	for (const int X : sortedGotoSymbols(gotos)) {	12,638✔
232	auto& gotoSet = gotos[X];	11,142✔
233	auto signature = makeItemSetSignature(gotoSet);	11,142✔
234	const auto existing = stateByItems.find(signature);	11,142✔
235	if (existing == stateByItems.end()) {	11,142✔
236	const std::size_t newState = canonicalCollection.size();	1,490✔
237	canonicalCollection.push_back(std::move(gotoSet));	1,490✔
238	stateByItems.emplace(std::move(signature), newState);	1,490✔
239	computedGotos[{ i, X }] = newState;	1,490✔
240	} else {
241	computedGotos[{ i, X }] = existing->second;	9,652✔
242	}
243	}	12,638✔
244	}	1,496✔
245	}	6✔
246
247	} // namespace
248
249	namespace parser {
250
251	CanonicalCollection::CanonicalCollection(	16✔
252	const FirstTable& first,
253	const Grammar& grammar,
254	AutomatonKind kind)	16✔
255	{
256	std::vector<LR1Item> initialSet {
257	LR1Item { grammar.getTopRule(), std::vector<int>{ grammar.getEndSymbol() }, grammar }	32✔
258	};	64✔
259	closeItemSet(first, grammar, buffers, initialSet);	16✔
260	canonicalCollection.push_back(std::move(initialSet));	16✔
261
262	if (kind == AutomatonKind::LALR1) {	16✔
263	computeLALR1(canonicalCollection, computedGotos, first, grammar, buffers);	10✔
264	} else {
265	computeLR1(canonicalCollection, computedGotos, first, grammar, buffers);	6✔
266	}
267
268	logCollection(grammar);	16✔
269	}	16✔
270
271	std::size_t CanonicalCollection::stateCount() const noexcept {	18✔
272	return canonicalCollection.size();	18✔
273	}
274
275	const std::vector<LR1Item>& CanonicalCollection::setOfItemsAtState(size_t state) const {	2,694✔
276	return canonicalCollection.at(state);	2,694✔
277	}
278
279	std::size_t CanonicalCollection::goTo(std::size_t stateFrom, int symbol) const {	15,102✔
280	return computedGotos.at({ stateFrom, symbol });	15,102✔
281	}
282
283	void CanonicalCollection::logCollection(const Grammar& grammar) const {	16✔
284	if (logger.isNull()) {	16✔
285	return;	14✔
286	}
287	logger << "\n*******************\nCanonical collection:\n*******************\n";	2✔
288	int setNo = 0;	2✔
289	for (const auto& setOfItems : canonicalCollection) {	16✔
290	logger << "Set " << setNo++ << ":\n";	14✔
291	for (const auto& item : setOfItems) {	42✔
292	logger << item.str(grammar);	28✔
293	}
294	logger << "\n";	14✔
295	}
296	logger << "Computed GOTOs:\n";	2✔
297	for (const auto& g : computedGotos) {	22✔
298	logger << g.first.first << "\t" << g.first.second << "\t" << g.second << "\n";	20✔
299	}
300	}
301
302	} // namespace parser

rieske / trans / 29767047230

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous