29700705556

Committed 19 Jul 2026 07:29PM UTC coverage: 90.76% (+0.2%) from 90.53%

Build # 29700705556

Build Type

Pull #46

github

Committed by

rieske

Commit Message

Experimental parser generator optimization

Pull Request Pull Request #46: Experimental parser generator optimization

Coverage Stats

485 of 494 new or added lines in 16 files covered. (98.18%)

17 existing lines in 6 files now uncovered.

5275 of 5812 relevant lines covered (90.76%)

352127.06 hits per line

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

98.25

/src/parser/CanonicalCollection.cpp

#include "CanonicalCollection.h"

#include "HashCombine.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& firstTable,
        const Grammar& grammar,
        AutomatonKind kind) :
        firstTable { firstTable }
{
    std::vector<LR1Item> initialSet {
        LR1Item { grammar.getTopRule(), std::vector<int>{ grammar.getEndSymbol() }, grammar }
    };
    closeItemSet(firstTable, grammar, buffers, initialSet);
    canonicalCollection.push_back(std::move(initialSet));

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

rieske / trans / 29700705556

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