• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

rieske / trans / 29699540882

19 Jul 2026 06:54PM UTC coverage: 90.709% (+0.2%) from 90.53%
29699540882

Pull #46

github

rieske
Experimental parser generator optimization
Pull Request #46: Experimental parser generator optimization

453 of 465 new or added lines in 16 files covered. (97.42%)

1 existing line in 1 file now uncovered.

5272 of 5812 relevant lines covered (90.71%)

320203.21 hits per line

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

96.55
/src/parser/CanonicalCollection.cpp
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(
113,346✔
22
        const FirstTable& first,
23
        const Grammar& grammar,
24
        GenerationBuffers& buffers,
25
        std::vector<LR1Item>& items) {
26
    auto& coreIndex = buffers.coreIndex;
113,346✔
27
    auto& worklist = buffers.worklist;
113,346✔
28
    buffers.prepareClosure(items.size());
113,346✔
29

30
    for (std::size_t i = 0; i < items.size(); ++i) {
304,860✔
31
        coreIndex.emplace(items[i].coreKey(), i);
191,514✔
32
        worklist.push_back(i);
191,514✔
33
    }
34
    items.reserve(std::max(items.capacity(), items.size() + 64));
113,346✔
35

36
    std::size_t head = 0;
113,346✔
37
    while (head < worklist.size()) {
3,039,458✔
38
        const std::size_t index = worklist[head++];
2,926,112✔
39
        if (!items[index].hasUnvisitedSymbols() || grammar.isTerminal(items[index].nextUnvisitedSymbol())) {
2,926,112✔
40
            continue;
896,578✔
41
        }
42

43
        const int B = items[index].nextUnvisitedSymbol();
2,029,534✔
44
        const LR1Item::LookaheadSet propagated = items[index].hasSymbolsAfterNext()
2,029,534✔
45
                ? first.firstBits(items[index].symbolAfterNext())
2,029,534✔
46
                : items[index].lookaheads();
568,156✔
47

48
        for (const auto& production : grammar.getProductionsOfSymbol(B)) {
12,826,726✔
49
            const std::uint64_t key =
50
                    (static_cast<std::uint64_t>(static_cast<std::uint32_t>(production.getId())) << 32);
10,797,192✔
51
            const auto existing = coreIndex.find(key);
10,797,192✔
52
            if (existing == coreIndex.end()) {
10,797,192✔
53
                items.emplace_back(production, propagated);
991,300✔
54
                const std::size_t newIndex = items.size() - 1;
991,300✔
55
                coreIndex.emplace(key, newIndex);
991,300✔
56
                worklist.push_back(newIndex);
991,300✔
57
            } else if (items[existing->second].mergeLookaheads(propagated)) {
9,805,892✔
58
                worklist.push_back(existing->second);
1,743,298✔
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) {
113,346✔
66
        return left.coreKey() < right.coreKey();
7,363,574✔
67
    });
68
}
113,346✔
69

70
std::unordered_map<int, std::vector<LR1Item>> gotoAllFrom(
12,004✔
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;
12,004✔
76
    bySymbol.reserve(I.size());
12,004✔
77
    for (const auto& item : I) {
210,548✔
78
        if (item.hasUnvisitedSymbols()) {
198,544✔
79
            bySymbol[item.nextUnvisitedSymbol()].push_back(item.advance());
191,488✔
80
        }
81
    }
82
    for (auto& entry : bySymbol) {
125,324✔
83
        entry.second.reserve(entry.second.size() + 16);
113,320✔
84
        closeItemSet(first, grammar, buffers, entry.second);
113,320✔
85
    }
86
    return bySymbol;
12,004✔
NEW
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) {
54,632✔
93
    auto& signature = buffers.coreSignature;
54,632✔
94
    signature.clear();
54,632✔
95
    signature.reserve(items.size());
54,632✔
96
    for (const auto& item : items) {
646,946✔
97
        signature.push_back(item.coreKey());
592,314✔
98
    }
99
    return signature;
54,632✔
100
}
101

102
struct CoreSignatureHash {
103
    std::size_t operator()(const std::vector<std::uint64_t>& signature) const noexcept {
74,586✔
104
        std::size_t hash = signature.size();
74,586✔
105
        for (const std::uint64_t key : signature) {
890,124✔
106
            hashCombine(hash, key);
815,538✔
107
        }
108
        return hash;
74,586✔
109
    }
110
};
111

112
// Both sides sorted by the same cores (LALR state with matching core signature).
113
bool mergeLookaheadsByCore(
51,370✔
114
        std::vector<LR1Item>& existing,
115
        const std::vector<LR1Item>& incoming) {
116
    bool merged = false;
51,370✔
117
    for (std::size_t i = 0; i < existing.size(); ++i) {
592,620✔
118
        merged |= existing[i].mergeLookaheads(incoming[i].lookaheads());
541,250✔
119
    }
120
    return merged;
51,370✔
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) {
12,004✔
125
    std::vector<int> symbols;
12,004✔
126
    symbols.reserve(gotos.size());
12,004✔
127
    for (const auto& entry : gotos) {
125,324✔
128
        if (!entry.second.empty()) {
113,320✔
129
            symbols.push_back(entry.first);
113,320✔
130
        }
131
    }
132
    std::sort(symbols.begin(), symbols.end());
12,004✔
133
    return symbols;
12,004✔
NEW
134
}
×
135

136
void computeLALR1(
16✔
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;
16✔
143
    stateByCores.reserve(512);
16✔
144
    stateByCores.emplace(makeCoreSignature(canonicalCollection[0], buffers), 0);
16✔
145
    computedGotos.reserve(512);
16✔
146

147
    std::deque<std::size_t> worklist { 0 };
48✔
148
    std::vector<char> inQueue(1, 1);
16✔
149

150
    auto enqueue = [&](std::size_t state) {
6,470✔
151
        if (state >= inQueue.size()) {
6,470✔
152
            inQueue.resize(state + 1, 0);
3,246✔
153
        }
154
        if (!inQueue[state]) {
6,470✔
155
            inQueue[state] = 1;
5,550✔
156
            worklist.push_back(state);
5,550✔
157
        }
158
    };
6,470✔
159

160
    while (!worklist.empty()) {
5,582✔
161
        const std::size_t state = worklist.front();
5,566✔
162
        worklist.pop_front();
5,566✔
163
        inQueue[state] = 0;
5,566✔
164

165
        auto gotos = gotoAllFrom(canonicalCollection[state], first, grammar, buffers);
5,566✔
166
        for (const int X : sortedGotoSymbols(gotos)) {
60,182✔
167
            auto& gotoSet = gotos[X];
54,616✔
168
            auto signature = makeCoreSignature(gotoSet, buffers);
54,616✔
169
            const auto existing = stateByCores.find(signature);
54,616✔
170
            if (existing == stateByCores.end()) {
54,616✔
171
                const std::size_t newState = canonicalCollection.size();
3,246✔
172
                canonicalCollection.push_back(std::move(gotoSet));
3,246✔
173
                stateByCores.emplace(std::move(signature), newState);
3,246✔
174
                computedGotos[{ state, X }] = newState;
3,246✔
175
                enqueue(newState);
3,246✔
176
            } else {
177
                const std::size_t target = existing->second;
51,370✔
178
                computedGotos[{ state, X }] = target;
51,370✔
179
                if (mergeLookaheadsByCore(canonicalCollection[target], gotoSet)) {
51,370✔
180
                    enqueue(target);
3,224✔
181
                }
182
            }
183
        }
60,182✔
184
    }
5,566✔
185
}
16✔
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) {
58,714✔
193
    ItemSetSignature signature;
58,714✔
194
    signature.reserve(items.size());
58,714✔
195
    for (const auto& item : items) {
649,214✔
196
        signature.emplace_back(item.coreKey(), item.lookaheads());
590,500✔
197
    }
198
    return signature;
58,714✔
NEW
199
}
×
200

201
struct ItemSetSignatureHash {
202
    std::size_t operator()(const ItemSetSignature& signature) const noexcept {
104,314✔
203
        std::size_t hash = signature.size();
104,314✔
204
        for (const auto& entry : signature) {
1,282,006✔
205
            hashCombine(hash, entry.first);
1,177,692✔
206
            for (std::size_t i = 0; i < entry.second.size(); i += 64) {
3,533,076✔
207
                unsigned long long word = 0;
2,355,384✔
208
                for (std::size_t b = 0; b < 64 && i + b < entry.second.size(); ++b) {
153,099,960✔
209
                    if (entry.second.test(i + b)) {
150,744,576✔
210
                        word |= 1ULL << b;
23,600,556✔
211
                    }
212
                }
213
                hashCombine(hash, word);
2,355,384✔
214
            }
215
        }
216
        return hash;
104,314✔
217
    }
218
};
219

220
void computeLR1(
10✔
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;
10✔
227
    stateByItems.reserve(256);
10✔
228
    stateByItems.emplace(makeItemSetSignature(canonicalCollection[0]), 0);
10✔
229

230
    for (std::size_t i = 0; i < canonicalCollection.size(); ++i) {
6,448✔
231
        auto gotos = gotoAllFrom(canonicalCollection[i], first, grammar, buffers);
6,438✔
232
        for (const int X : sortedGotoSymbols(gotos)) {
65,142✔
233
            auto& gotoSet = gotos[X];
58,704✔
234
            auto signature = makeItemSetSignature(gotoSet);
58,704✔
235
            const auto existing = stateByItems.find(signature);
58,704✔
236
            if (existing == stateByItems.end()) {
58,704✔
237
                const std::size_t newState = canonicalCollection.size();
6,428✔
238
                canonicalCollection.push_back(std::move(gotoSet));
6,428✔
239
                stateByItems.emplace(std::move(signature), newState);
6,428✔
240
                computedGotos[{ i, X }] = newState;
6,428✔
241
            } else {
242
                computedGotos[{ i, X }] = existing->second;
52,276✔
243
            }
244
        }
65,142✔
245
    }
6,438✔
246
}
10✔
247

248
} // namespace
249

250
namespace parser {
251

252
CanonicalCollection::CanonicalCollection(
26✔
253
        const FirstTable& firstTable,
254
        const Grammar& grammar,
255
        AutomatonKind kind) :
26✔
256
        firstTable { firstTable }
26✔
257
{
258
    std::vector<LR1Item> initialSet {
259
        LR1Item { grammar.getTopRule(), std::vector<int>{ grammar.getEndSymbol() }, grammar }
52✔
260
    };
104✔
261
    closeItemSet(firstTable, grammar, buffers, initialSet);
26✔
262
    canonicalCollection.push_back(std::move(initialSet));
26✔
263

264
    if (kind == AutomatonKind::LALR1) {
26✔
265
        computeLALR1(canonicalCollection, computedGotos, firstTable, grammar, buffers);
16✔
266
    } else {
267
        computeLR1(canonicalCollection, computedGotos, firstTable, grammar, buffers);
10✔
268
    }
269

270
    logCollection(grammar);
26✔
271
}
26✔
272

273
std::size_t CanonicalCollection::stateCount() const noexcept {
34✔
274
    return canonicalCollection.size();
34✔
275
}
276

277
const std::vector<LR1Item>& CanonicalCollection::setOfItemsAtState(size_t state) const {
3,492✔
278
    return canonicalCollection.at(state);
3,492✔
279
}
280

281
std::size_t CanonicalCollection::goTo(std::size_t stateFrom, int symbol) const {
21,276✔
282
    return computedGotos.at({ stateFrom, symbol });
21,276✔
283
}
284

UNCOV
285
std::optional<std::size_t> CanonicalCollection::findGoTo(std::size_t stateFrom, int symbol) const noexcept {
×
NEW
286
    const auto it = computedGotos.find({ stateFrom, symbol });
×
NEW
287
    return it != computedGotos.end() ? std::optional<std::size_t>{ it->second } : std::nullopt;
×
288
}
289

290
void CanonicalCollection::logCollection(const Grammar& grammar) const {
26✔
291
    if (logger.isNull()) {
26✔
292
        return;
24✔
293
    }
294
    logger << "\n*********************\nCanonical collection:\n*********************\n";
2✔
295
    int setNo = 0;
2✔
296
    for (const auto& setOfItems : canonicalCollection) {
16✔
297
        logger << "Set " << setNo++ << ":\n";
14✔
298
        for (const auto& item : setOfItems) {
42✔
299
            logger << item.str(grammar);
28✔
300
        }
301
        logger << "\n";
14✔
302
    }
303
    logger << "Computed GOTOs:\n";
2✔
304
    for (const auto& g : computedGotos) {
22✔
305
        logger << g.first.first << "\t" << g.first.second << "\t" << g.second << "\n";
20✔
306
    }
307
}
308

309
} // namespace parser
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc