29767524866

Committed 20 Jul 2026 06:23PM UTC coverage: 90.735% (+0.1%) from 90.628%

Build # 29767524866

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #49 from rieske/perf/parser/3-action-table

perf(parser): value-type Action and flat (state,symbol) tables

Coverage Stats

178 of 181 new or added lines in 9 files covered. (98.34%)

5269 of 5807 relevant lines covered (90.74%)

228952.36 hits per line

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

97.17

/src/parser/Action.cpp

#include "Action.h"

#include <sstream>
#include <stdexcept>

#include "Grammar.h"
#include "ParsingTable.h"
#include "Production.h"
#include "util/Logger.h"
#include "util/LogManager.h"

namespace parser {

namespace {
const char SHIFT_ACTION = 's';
const char REDUCE_ACTION = 'r';
const char ERROR_ACTION = 'e';
const char ACCEPT_ACTION = 'a';

Logger& err = LogManager::getErrorLogger();
} // namespace

Action Action::shift(parse_state state) {
    Action action;
    action.kind_ = Kind::Shift;
    action.state_ = state;
    return action;
}

Action Action::reduce(const Production& production, const ParsingTable* parsingTable) {
    Action action;
    action.kind_ = Kind::Reduce;
    action.production_ = &production;
    action.parsingTable_ = parsingTable;
    return action;
}

Action Action::accept() {
    Action action;
    action.kind_ = Kind::Accept;
    return action;
}

Action Action::error(parse_state state,
        std::shared_ptr<const std::vector<int>> candidateSymbols,
        const Grammar* grammar) {
    Action action;
    action.kind_ = Kind::Error;
    action.state_ = state;
    action.candidateSymbols_ = std::move(candidateSymbols);
    action.grammar_ = grammar;
    return action;
}

std::string Action::serialize() const {
    switch (kind_) {
    case Kind::Accept:
        return std::string{ACCEPT_ACTION};
    case Kind::Shift:
        return std::string{SHIFT_ACTION} + " " + std::to_string(state_);
    case Kind::Reduce:
        return std::string{REDUCE_ACTION} + " " + std::to_string(production_->getId());
    case Kind::Error: {
        std::ostringstream s;
        s << ERROR_ACTION << " " << state_;
        if (candidateSymbols_) {
            for (const auto candidate : *candidateSymbols_) {
                s << " " << candidate;
            }
        }
        return s.str();
    }
    }
    __builtin_unreachable();
}

bool Action::equals(const Action& other) const {
    if (kind_ != other.kind_) {
        return false;
    }
    switch (kind_) {
    case Kind::Accept:
        return true;
    case Kind::Shift:
        return state_ == other.state_;
    case Kind::Reduce:
        return production_->getId() == other.production_->getId();
    case Kind::Error:
        return state_ == other.state_
                && candidateSymbols_ && other.candidateSymbols_
                && *candidateSymbols_ == *other.candidateSymbols_;
    }
    __builtin_unreachable();
}

Action Action::deserialize(const std::string& serializedAction,
        const ParsingTable& parsingTable, const Grammar& grammar) {
    std::istringstream actionStream { serializedAction };
    char type;
    actionStream >> type;
    switch (type) {
    case SHIFT_ACTION: {
        parse_state state;
        actionStream >> state;
        return Action::shift(state);
    }
    case REDUCE_ACTION: {
        size_t productionId;
        actionStream >> productionId;
        return Action::reduce(grammar.getRuleById(static_cast<int>(productionId)), &parsingTable);
    }
    case ERROR_ACTION: {
        parse_state state;
        actionStream >> state;
        std::vector<int> candidates;
        int candidate;
        while (actionStream >> candidate) {
            candidates.push_back(candidate);
        }
        return Action::error(state,
                std::make_shared<const std::vector<int>>(std::move(candidates)),
                &grammar);
    }
    case ACCEPT_ACTION:
        return Action::accept();
    default:
        throw std::runtime_error(
                "Error reading serialized parsing table: invalid action type: "
                        + std::to_string(type));
    }
}

bool Action::parse(std::stack<parse_state>& parsingStack, TokenStream& tokenStream,
        SyntaxTreeBuilder& syntaxTreeBuilder) const {
    switch (kind_) {
    case Kind::Accept:
        return true;
    case Kind::Shift: {
        parsingStack.push(state_);
        scanner::Token token = tokenStream.getCurrentToken();
        syntaxTreeBuilder.makeTerminalNode(token.id, token.lexeme, token.context);
        tokenStream.nextToken();
        return false;
    }
    case Kind::Reduce: {
        for (size_t i = production_->size(); i > 0; --i) {
            parsingStack.pop();
        }
        parsingStack.push(parsingTable_->go_to(parsingStack.top(), production_->getDefiningSymbol()));
        syntaxTreeBuilder.makeNonterminalNode(*production_);
        return false;
    }
    case Kind::Error: {
        syntaxTreeBuilder.err();
        scanner::Token currentToken = tokenStream.getCurrentToken();
        err << "Error: " << currentToken.context << ": unexpected token: " << currentToken.lexeme
                << " expected:";
        if (candidateSymbols_ && grammar_) {
            for (const auto candidate : *candidateSymbols_) {
                err << " " << grammar_->getSymbolById(candidate);
            }
        }
        err << "\n";
        return true;
    }
    }
    __builtin_unreachable();
}

} // namespace parser

1	#include "Action.h"
2
3	#include <sstream>
4	#include <stdexcept>
5
6	#include "Grammar.h"
7	#include "ParsingTable.h"
8	#include "Production.h"
9	#include "util/Logger.h"
10	#include "util/LogManager.h"
11
12	namespace parser {
13
14	namespace {
15	const char SHIFT_ACTION = 's';
16	const char REDUCE_ACTION = 'r';
17	const char ERROR_ACTION = 'e';
18	const char ACCEPT_ACTION = 'a';
19
20	Logger& err = LogManager::getErrorLogger();
21	} // namespace
22
23	Action Action::shift(parse_state state) {	849,154✔
24	Action action;	849,154✔
25	action.kind_ = Kind::Shift;	849,154✔
26	action.state_ = state;	849,154✔
27	return action;	849,154✔
28	}
29
30	Action Action::reduce(const Production& production, const ParsingTable* parsingTable) {	1,997,178✔
31	Action action;	1,997,178✔
32	action.kind_ = Kind::Reduce;	1,997,178✔
33	action.production_ = &production;	1,997,178✔
34	action.parsingTable_ = parsingTable;	1,997,178✔
35	return action;	1,997,178✔
36	}
37
38	Action Action::accept() {	402✔
39	Action action;	402✔
40	action.kind_ = Kind::Accept;	402✔
41	return action;	402✔
42	}
43
44	Action Action::error(parse_state state,	10,398,898✔
45	std::shared_ptr<const std::vector<int>> candidateSymbols,
46	const Grammar* grammar) {
47	Action action;	10,398,898✔
48	action.kind_ = Kind::Error;	10,398,898✔
49	action.state_ = state;	10,398,898✔
50	action.candidateSymbols_ = std::move(candidateSymbols);	10,398,898✔
51	action.grammar_ = grammar;	10,398,898✔
52	return action;	10,398,898✔
53	}
54
55	std::string Action::serialize() const {	68,660✔
56	switch (kind_) {	68,660✔
57	case Kind::Accept:	8✔
58	return std::string{ACCEPT_ACTION};	24✔
59	case Kind::Shift:	4,358✔
60	return std::string{SHIFT_ACTION} + " " + std::to_string(state_);	13,074✔
61	case Kind::Reduce:	10,252✔
62	return std::string{REDUCE_ACTION} + " " + std::to_string(production_->getId());	30,756✔
63	case Kind::Error: {	54,042✔
64	std::ostringstream s;	54,042✔
65	s << ERROR_ACTION << " " << state_;	54,042✔
66	if (candidateSymbols_) {	54,042✔
67	for (const auto candidate : *candidateSymbols_) {	623,358✔
68	s << " " << candidate;	569,316✔
69	}
70	}
71	return s.str();	54,042✔
72	}	54,042✔
73	}
NEW 74	__builtin_unreachable();	×
75	}
76
77	bool Action::equals(const Action& other) const {	3,000✔
78	if (kind_ != other.kind_) {	3,000✔
79	return false;	6✔
80	}
81	switch (kind_) {	2,994✔
82	case Kind::Accept:	2✔
83	return true;	2✔
84	case Kind::Shift:	2,982✔
85	return state_ == other.state_;	2,982✔
86	case Kind::Reduce:	4✔
87	return production_->getId() == other.production_->getId();	4✔
88	case Kind::Error:	6✔
89	return state_ == other.state_	6✔
90	&& candidateSymbols_ && other.candidateSymbols_	6✔
91	&& candidateSymbols_ == other.candidateSymbols_;	12✔
92	}
NEW 93	__builtin_unreachable();	×
94	}
95
96	Action Action::deserialize(const std::string& serializedAction,	13,176,586✔
97	const ParsingTable& parsingTable, const Grammar& grammar) {
98	std::istringstream actionStream { serializedAction };	13,176,586✔
99	char type;
100	actionStream >> type;	13,176,586✔
101	switch (type) {	13,176,586✔
102	case SHIFT_ACTION: {	834,050✔
103	parse_state state;
104	actionStream >> state;	834,050✔
105	return Action::shift(state);	834,050✔
106	}
107	case REDUCE_ACTION: {	1,967,618✔
108	size_t productionId;
109	actionStream >> productionId;	1,967,618✔
110	return Action::reduce(grammar.getRuleById(static_cast<int>(productionId)), &parsingTable);	1,967,618✔
111	}
112	case ERROR_ACTION: {	10,374,530✔
113	parse_state state;
114	actionStream >> state;	10,374,530✔
115	std::vector<int> candidates;	10,374,530✔
116	int candidate;
117	while (actionStream >> candidate) {	119,682,052✔
118	candidates.push_back(candidate);	109,307,522✔
119	}
120	return Action::error(state,
121	std::make_shared<const std::vector<int>>(std::move(candidates)),	20,749,060✔
122	&grammar);	10,374,530✔
123	}	10,374,530✔
124	case ACCEPT_ACTION:	386✔
125	return Action::accept();	386✔
126	default:	2✔
127	throw std::runtime_error(
128	"Error reading serialized parsing table: invalid action type: "
129	+ std::to_string(type));	2✔
130	}
131	}	13,176,586✔
132
133	bool Action::parse(std::stack<parse_state>& parsingStack, TokenStream& tokenStream,	120,798✔
134	SyntaxTreeBuilder& syntaxTreeBuilder) const {
135	switch (kind_) {	120,798✔
136	case Kind::Accept:	384✔
137	return true;	384✔
138	case Kind::Shift: {	18,782✔
139	parsingStack.push(state_);	18,782✔
140	scanner::Token token = tokenStream.getCurrentToken();	18,782✔
141	syntaxTreeBuilder.makeTerminalNode(token.id, token.lexeme, token.context);	18,782✔
142	tokenStream.nextToken();	18,782✔
143	return false;	18,782✔
144	}	18,782✔
145	case Kind::Reduce: {	101,628✔
146	for (size_t i = production_->size(); i > 0; --i) {	221,644✔
147	parsingStack.pop();	120,016✔
148	}
149	parsingStack.push(parsingTable_->go_to(parsingStack.top(), production_->getDefiningSymbol()));	101,628✔
150	syntaxTreeBuilder.makeNonterminalNode(*production_);	101,628✔
151	return false;	101,628✔
152	}
153	case Kind::Error: {	4✔
154	syntaxTreeBuilder.err();	4✔
155	scanner::Token currentToken = tokenStream.getCurrentToken();	4✔
156	err << "Error: " << currentToken.context << ": unexpected token: " << currentToken.lexeme	4✔
157	<< " expected:";	4✔
158	if (candidateSymbols_ && grammar_) {	4✔
159	for (const auto candidate : *candidateSymbols_) {	16✔
160	err << " " << grammar_->getSymbolById(candidate);	12✔
161	}
162	}
163	err << "\n";	4✔
164	return true;	4✔
165	}	4✔
166	}
NEW 167	__builtin_unreachable();	×
168	}
169
170	} // namespace parser

rieske / trans / 29767524866

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