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

rieske / trans / 29701014723

19 Jul 2026 07:38PM UTC coverage: 90.735% (+0.2%) from 90.53%
29701014723

Pull #46

github

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

487 of 497 new or added lines in 19 files covered. (97.99%)

17 existing lines in 6 files now uncovered.

5269 of 5807 relevant lines covered (90.74%)

352430.51 hits per line

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

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

29
    for (std::size_t i = 0; i < items.size(); ++i) {
323,386 ✔
30
        coreIndex.emplace(items[i].coreKey(), i);
206,316 ✔
31
        worklist.push_back(i);
206,316 ✔
32
    }
33
    items.reserve(std::max(items.capacity(), items.size() + 64));
117,070 ✔
34

35
    std::size_t head = 0;
117,070 ✔
36
    while (head < worklist.size()) {
3,606,244 ✔
37
        const std::size_t index = worklist[head++];
3,489,174 ✔
38
        if (!items[index].hasUnvisitedSymbols() || grammar.isTerminal(items[index].nextUnvisitedSymbol())) {
3,489,174 ✔
39
            continue;
1,048,042 ✔
40
        }
41

42
        const int B = items[index].nextUnvisitedSymbol();
2,441,132 ✔
43
        const LR1Item::LookaheadSet propagated = items[index].hasSymbolsAfterNext()
2,441,132 ✔
44
                ? first.firstBits(items[index].symbolAfterNext())
2,441,132 ✔
45
                : items[index].lookaheads();
663,600 ✔
46

47
        for (const auto& production : grammar.getProductionsOfSymbol(B)) {
15,905,388 ✔
48
            const std::uint64_t key =
49
                    (static_cast<std::uint64_t>(static_cast<std::uint32_t>(production.getId())) << 32);
13,464,256 ✔
50
            const auto existing = coreIndex.find(key);
13,464,256 ✔
51
            if (existing == coreIndex.end()) {
13,464,256 ✔
52
                items.emplace_back(production, propagated);
1,101,408 ✔
53
                const std::size_t newIndex = items.size() - 1;
1,101,408 ✔
54
                coreIndex.emplace(key, newIndex);
1,101,408 ✔
55
                worklist.push_back(newIndex);
1,101,408 ✔
56
            } else if (items[existing->second].mergeLookaheads(propagated)) {
12,362,848 ✔
57
                worklist.push_back(existing->second);
2,181,450 ✔
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) {
117,070 ✔
65
        return left.coreKey() < right.coreKey();
8,354,926 ✔
66
    });
67
}
117,070 ✔
68

69
std::unordered_map<int, std::vector<LR1Item>> gotoAllFrom(
11,266 ✔
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;
11,266 ✔
75
    bySymbol.reserve(I.size());
11,266 ✔
76
    for (const auto& item : I) {
224,068 ✔
77
        if (item.hasUnvisitedSymbols()) {
212,802 ✔
78
            bySymbol[item.nextUnvisitedSymbol()].push_back(item.advance());
206,296 ✔
79
        }
80
    }
81
    for (auto& entry : bySymbol) {
128,316 ✔
82
        entry.second.reserve(entry.second.size() + 16);
117,050 ✔
83
        closeItemSet(first, grammar, buffers, entry.second);
117,050 ✔
84
    }
85
    return bySymbol;
11,266 ✔
NEW
UNCOV
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) {
44,036 ✔
92
    auto& signature = buffers.coreSignature;
44,036 ✔
93
    signature.clear();
44,036 ✔
94
    signature.reserve(items.size());
44,036 ✔
95
    for (const auto& item : items) {
540,702 ✔
96
        signature.push_back(item.coreKey());
496,666 ✔
97
    }
98
    return signature;
44,036 ✔
99
}
100

101
struct CoreSignatureHash {
102
    std::size_t operator()(const std::vector<std::uint64_t>& signature) const noexcept {
60,002 ✔
103
        std::size_t hash = signature.size();
60,002 ✔
104
        for (const std::uint64_t key : signature) {
752,476 ✔
105
            hashCombine(hash, key);
692,474 ✔
106
        }
107
        return hash;
60,002 ✔
108
    }
109
};
110

111
// Both sides sorted by the same cores (LALR state with matching core signature).
112
bool mergeLookaheadsByCore(
41,594 ✔
113
        std::vector<LR1Item>& existing,
114
        const std::vector<LR1Item>& incoming) {
115
    bool merged = false;
41,594 ✔
116
    for (std::size_t i = 0; i < existing.size(); ++i) {
496,004 ✔
117
        merged |= existing[i].mergeLookaheads(incoming[i].lookaheads());
454,410 ✔
118
    }
119
    return merged;
41,594 ✔
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) {
11,266 ✔
124
    std::vector<int> symbols;
11,266 ✔
125
    symbols.reserve(gotos.size());
11,266 ✔
126
    for (const auto& entry : gotos) {
128,316 ✔
127
        if (!entry.second.empty()) {
117,050 ✔
128
            symbols.push_back(entry.first);
117,050 ✔
129
        }
130
    }
131
    std::sort(symbols.begin(), symbols.end());
11,266 ✔
132
    return symbols;
11,266 ✔
NEW
UNCOV
133
}
×
134

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

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

149
    auto enqueue = [&](std::size_t state) {
4,898 ✔
150
        if (state >= inQueue.size()) {
4,898 ✔
151
            inQueue.resize(state + 1, 0);
2,430 ✔
152
        }
153
        if (!inQueue[state]) {
4,898 ✔
154
            inQueue[state] = 1;
4,218 ✔
155
            worklist.push_back(state);
4,218 ✔
156
        }
157
    };
4,898 ✔
158

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

164
        auto gotos = gotoAllFrom(canonicalCollection[state], first, grammar, buffers);
4,230 ✔
165
        for (const int X : sortedGotoSymbols(gotos)) {
48,254 ✔
166
            auto& gotoSet = gotos[X];
44,024 ✔
167
            auto signature = makeCoreSignature(gotoSet, buffers);
44,024 ✔
168
            const auto existing = stateByCores.find(signature);
44,024 ✔
169
            if (existing == stateByCores.end()) {
44,024 ✔
170
                const std::size_t newState = canonicalCollection.size();
2,430 ✔
171
                canonicalCollection.push_back(std::move(gotoSet));
2,430 ✔
172
                stateByCores.emplace(std::move(signature), newState);
2,430 ✔
173
                computedGotos[{ state, X }] = newState;
2,430 ✔
174
                enqueue(newState);
2,430 ✔
175
            } else {
176
                const std::size_t target = existing->second;
41,594 ✔
177
                computedGotos[{ state, X }] = target;
41,594 ✔
178
                if (mergeLookaheadsByCore(canonicalCollection[target], gotoSet)) {
41,594 ✔
179
                    enqueue(target);
2,468 ✔
180
                }
181
            }
182
        }
48,254 ✔
183
    }
4,230 ✔
184
}
12 ✔
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) {
73,034 ✔
192
    ItemSetSignature signature;
73,034 ✔
193
    signature.reserve(items.size());
73,034 ✔
194
    for (const auto& item : items) {
884,092 ✔
195
        signature.emplace_back(item.coreKey(), item.lookaheads());
811,058 ✔
196
    }
197
    return signature;
73,034 ✔
NEW
UNCOV
198
}
×
199

200
struct ItemSetSignatureHash {
201
    std::size_t operator()(const ItemSetSignature& signature) const noexcept {
126,764 ✔
202
        std::size_t hash = signature.size();
126,764 ✔
203
        for (const auto& entry : signature) {
1,714,476 ✔
204
            hashCombine(hash, entry.first);
1,587,712 ✔
205
            for (std::size_t i = 0; i < entry.second.size(); i += 64) {
4,763,136 ✔
206
                unsigned long long word = 0;
3,175,424 ✔
207
                for (std::size_t b = 0; b < 64 && i + b < entry.second.size(); ++b) {
206,402,560 ✔
208
                    if (entry.second.test(i + b)) {
203,227,136 ✔
209
                        word |= 1ULL << b;
32,809,568 ✔
210
                    }
211
                }
212
                hashCombine(hash, word);
3,175,424 ✔
213
            }
214
        }
215
        return hash;
126,764 ✔
216
    }
217
};
218

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

229
    for (std::size_t i = 0; i < canonicalCollection.size(); ++i) {
7,044 ✔
230
        auto gotos = gotoAllFrom(canonicalCollection[i], first, grammar, buffers);
7,036 ✔
231
        for (const int X : sortedGotoSymbols(gotos)) {
80,062 ✔
232
            auto& gotoSet = gotos[X];
73,026 ✔
233
            auto signature = makeItemSetSignature(gotoSet);
73,026 ✔
234
            const auto existing = stateByItems.find(signature);
73,026 ✔
235
            if (existing == stateByItems.end()) {
73,026 ✔
236
                const std::size_t newState = canonicalCollection.size();
7,028 ✔
237
                canonicalCollection.push_back(std::move(gotoSet));
7,028 ✔
238
                stateByItems.emplace(std::move(signature), newState);
7,028 ✔
239
                computedGotos[{ i, X }] = newState;
7,028 ✔
240
            } else {
241
                computedGotos[{ i, X }] = existing->second;
65,998 ✔
242
            }
243
        }
80,062 ✔
244
    }
7,036 ✔
245
}
8 ✔
246

247
} // namespace
248

249
namespace parser {
250

251
CanonicalCollection::CanonicalCollection(
20 ✔
252
        const FirstTable& first,
253
        const Grammar& grammar,
254
        AutomatonKind kind)
20 ✔
255
{
256
    std::vector<LR1Item> initialSet {
257
        LR1Item { grammar.getTopRule(), std::vector<int>{ grammar.getEndSymbol() }, grammar }
40 ✔
258
    };
80 ✔
259
    closeItemSet(first, grammar, buffers, initialSet);
20 ✔
260
    canonicalCollection.push_back(std::move(initialSet));
20 ✔
261

262
    if (kind == AutomatonKind::LALR1) {
20 ✔
263
        computeLALR1(canonicalCollection, computedGotos, first, grammar, buffers);
12 ✔
264
    } else {
265
        computeLR1(canonicalCollection, computedGotos, first, grammar, buffers);
8 ✔
266
    }
267

268
    logCollection(grammar);
20 ✔
269
}
20 ✔
270

271
std::size_t CanonicalCollection::stateCount() const noexcept {
28 ✔
272
    return canonicalCollection.size();
28 ✔
273
}
274

275
const std::vector<LR1Item>& CanonicalCollection::setOfItemsAtState(size_t state) const {
5,128 ✔
276
    return canonicalCollection.at(state);
5,128 ✔
277
}
278

279
std::size_t CanonicalCollection::goTo(std::size_t stateFrom, int symbol) const {
41,064 ✔
280
    return computedGotos.at({ stateFrom, symbol });
41,064 ✔
281
}
282

283
void CanonicalCollection::logCollection(const Grammar& grammar) const {
20 ✔
284
    if (logger.isNull()) {
20 ✔
285
        return;
18 ✔
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
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