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

rieske / trans / 29699202186

19 Jul 2026 06:43PM UTC coverage: 90.726% (+0.2%) from 90.53%
29699202186

Pull #46

github

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

493 of 504 new or added lines in 17 files covered. (97.82%)

1 existing line in 1 file now uncovered.

5283 of 5823 relevant lines covered (90.73%)

308093.56 hits per line

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

96.67
/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,418✔
38
        const std::size_t index = worklist[head++];
2,926,072✔
39
        if (!items[index].hasUnvisitedSymbols() || grammar.isTerminal(items[index].nextUnvisitedSymbol())) {
2,926,072✔
40
            continue;
896,562✔
41
        }
42

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

48
        for (const auto& production : grammar.getProductionsOfSymbol(B)) {
12,826,582✔
49
            const std::uint64_t key =
50
                    (static_cast<std::uint64_t>(static_cast<std::uint32_t>(production.getId())) << 32);
10,797,072✔
51
            const auto existing = coreIndex.find(key);
10,797,072✔
52
            if (existing == coreIndex.end()) {
10,797,072✔
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,772✔
58
                worklist.push_back(existing->second);
1,743,258✔
59
            }
60
        }
61
    }
62
}
113,346✔
63

64
std::unordered_map<int, std::vector<LR1Item>> gotoAllFrom(
12,004✔
65
        const std::vector<LR1Item>& I,
66
        const FirstTable& first,
67
        const Grammar& grammar,
68
        GenerationBuffers& buffers) {
69
    std::unordered_map<int, std::vector<LR1Item>> bySymbol;
12,004✔
70
    bySymbol.reserve(I.size());
12,004✔
71
    for (const auto& item : I) {
210,548✔
72
        if (item.hasUnvisitedSymbols()) {
198,544✔
73
            bySymbol[item.nextUnvisitedSymbol()].push_back(item.advance());
191,488✔
74
        }
75
    }
76
    for (auto& entry : bySymbol) {
125,324✔
77
        entry.second.reserve(entry.second.size() + 16);
113,320✔
78
        closeItemSet(first, grammar, buffers, entry.second);
113,320✔
79
    }
80
    return bySymbol;
12,004✔
NEW
81
}
×
82

83
// --- LALR(1) ---
84

85
std::vector<std::uint64_t> makeCoreSignature(const std::vector<LR1Item>& items, GenerationBuffers& buffers) {
54,632✔
86
    auto& signature = buffers.coreSignature;
54,632✔
87
    signature.clear();
54,632✔
88
    signature.reserve(items.size());
54,632✔
89
    for (const auto& item : items) {
646,946✔
90
        signature.push_back(item.coreKey());
592,314✔
91
    }
92
    std::sort(signature.begin(), signature.end());
54,632✔
93
    return signature;
54,632✔
94
}
95

96
struct CoreSignatureHash {
97
    std::size_t operator()(const std::vector<std::uint64_t>& signature) const noexcept {
74,586✔
98
        std::size_t hash = signature.size();
74,586✔
99
        for (const std::uint64_t key : signature) {
890,124✔
100
            hashCombine(hash, key);
815,538✔
101
        }
102
        return hash;
74,586✔
103
    }
104
};
105

106
bool mergeLookaheadsByCore(
51,370✔
107
        std::vector<LR1Item>& existing,
108
        const std::vector<LR1Item>& incoming,
109
        GenerationBuffers& buffers) {
110
    buffers.prepareMerge(existing.size());
51,370✔
111
    auto& index = buffers.mergeIndexByCore;
51,370✔
112
    for (std::size_t i = 0; i < existing.size(); ++i) {
592,620✔
113
        index.emplace(existing[i].coreKey(), i);
541,250✔
114
    }
115
    bool merged = false;
51,370✔
116
    for (const auto& item : incoming) {
592,620✔
117
        merged |= existing[index.at(item.coreKey())].mergeLookaheads(item.lookaheads());
541,250✔
118
    }
119
    return merged;
51,370✔
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) {
12,004✔
124
    std::vector<int> symbols;
12,004✔
125
    symbols.reserve(gotos.size());
12,004✔
126
    for (const auto& entry : gotos) {
125,324✔
127
        if (!entry.second.empty()) {
113,320✔
128
            symbols.push_back(entry.first);
113,320✔
129
        }
130
    }
131
    std::sort(symbols.begin(), symbols.end());
12,004✔
132
    return symbols;
12,004✔
NEW
133
}
×
134

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

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

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

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

164
        auto gotos = gotoAllFrom(canonicalCollection[state], first, grammar, buffers);
5,566✔
165
        for (const int X : sortedGotoSymbols(gotos)) {
60,182✔
166
            auto& gotoSet = gotos[X];
54,616✔
167
            auto signature = makeCoreSignature(gotoSet, buffers);
54,616✔
168
            const auto existing = stateByCores.find(signature);
54,616✔
169
            if (existing == stateByCores.end()) {
54,616✔
170
                const std::size_t newState = canonicalCollection.size();
3,246✔
171
                canonicalCollection.push_back(std::move(gotoSet));
3,246✔
172
                stateByCores.emplace(std::move(signature), newState);
3,246✔
173
                computedGotos[{ state, X }] = newState;
3,246✔
174
                enqueue(newState);
3,246✔
175
            } else {
176
                const std::size_t target = existing->second;
51,370✔
177
                computedGotos[{ state, X }] = target;
51,370✔
178
                if (mergeLookaheadsByCore(canonicalCollection[target], gotoSet, buffers)) {
51,370✔
179
                    enqueue(target);
3,224✔
180
                }
181
            }
182
        }
60,182✔
183
    }
5,566✔
184
}
16✔
185

186
// --- LR(1) ---
187

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

190
ItemSetSignature makeItemSetSignature(const std::vector<LR1Item>& items) {
58,714✔
191
    ItemSetSignature signature;
58,714✔
192
    signature.reserve(items.size());
58,714✔
193
    for (const auto& item : items) {
649,214✔
194
        signature.emplace_back(item.coreKey(), item.lookaheads());
590,500✔
195
    }
196
    // Cores are unique within a closed item set; sort by core only.
197
    std::sort(signature.begin(), signature.end(),
58,714✔
198
            [](const auto& left, const auto& right) {
3,577,638✔
199
                return left.first < right.first;
3,577,638✔
200
            });
201
    return signature;
58,714✔
NEW
202
}
×
203

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

223
void computeLR1(
10✔
224
        std::vector<std::vector<LR1Item>>& canonicalCollection,
225
        GotoMap& computedGotos,
226
        const FirstTable& first,
227
        const Grammar& grammar,
228
        GenerationBuffers& buffers) {
229
    std::unordered_map<ItemSetSignature, std::size_t, ItemSetSignatureHash> stateByItems;
10✔
230
    stateByItems.reserve(256);
10✔
231
    stateByItems.emplace(makeItemSetSignature(canonicalCollection[0]), 0);
10✔
232

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

251
} // namespace
252

253
namespace parser {
254

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

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

273
    logCollection(grammar);
26✔
274
}
26✔
275

276
std::size_t CanonicalCollection::stateCount() const noexcept {
34✔
277
    return canonicalCollection.size();
34✔
278
}
279

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

284
std::size_t CanonicalCollection::goTo(std::size_t stateFrom, int symbol) const {
21,276✔
285
    return computedGotos.at({ stateFrom, symbol });
21,276✔
286
}
287

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

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

312
} // 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