rieske / trans / 29766085819

coverage: 90.582% (+0.05%) from 90.53%
29766085819

push

github

web-flow 
Merge pull request #47 from rieske/perf/parser/1-lookahead-model

perf(parser): dense lookahead bitsets and terminal maps

146 of 147 new or added lines in 7 files covered. (99.32%)

1 existing line in 1 file now uncovered.

5155 of 5691 relevant lines covered (90.58%)

340886.7 hits per line

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

98.41
/src/parser/LR1Item.cpp
1 
#include "LR1Item.h"
2 









3



#include <algorithm>










4



#include <sstream>










5



#include <stdexcept>










6












7



namespace parser {










8













9



LR1Item::LR1Item(const Production& production, LookaheadSet lookaheads) :




2,122,820✔






10



        production { &production },




2,122,820✔






11



        lookaheadBits { lookaheads }




2,122,820✔





12



{











13



}




2,122,820✔





14













15



LR1Item::LR1Item(const Production& production, const std::vector<int>& lookaheadSymbolIds, const Grammar& grammar) :




22✔






16



        production { &production },




22✔






17



        lookaheadBits { grammar.toLookaheadBits(lookaheadSymbolIds) }




22✔





18



{










19



}




22✔





20












21



LR1Item LR1Item::advance() const {




56,566✔






22



    LR1Item next { *this };




56,566✔






23



    ++next.visitedOffset;




56,566✔






24



    if (next.visitedOffset > static_cast<int>(production->size())) {




56,566✔





25



        throw std::out_of_range { "attempted to advance LR1Item past production size" };




2✔





26



    }











27



    return next;




56,564✔





28



}










29













30



bool LR1Item::mergeLookaheads(const LookaheadSet& more) {




2,067,986✔






31



    const LookaheadSet before = lookaheadBits;




2,067,986✔






32



    lookaheadBits |= more;




2,067,986✔






33



    return lookaheadBits != before;




2,067,986✔





34



}










35













36



bool LR1Item::hasUnvisitedSymbols() const {




8,630,038✔






37



    return visitedOffset < static_cast<int>(production->size());




8,630,038✔





38



}










39













40



int LR1Item::nextUnvisitedSymbol() const {




8,805,270✔






41



    return *(production->begin() + visitedOffset);




8,805,270✔





42



}










43













44



bool LR1Item::hasSymbolsAfterNext() const {




493,488✔






45



    return visitedOffset + 1 < static_cast<int>(production->size());




493,488✔





46



}










47













48



int LR1Item::symbolAfterNext() const {




300,256✔






49



    return *(production->begin() + visitedOffset + 1);




300,256✔





50



}










51













52



std::vector<int> LR1Item::getVisited() const {




36,332✔






53



    return { production->begin(), production->begin() + visitedOffset };




108,996✔





54



}










55












56



std::vector<int> LR1Item::getExpectedSymbols() const {




36,332✔






57



    return { production->begin() + visitedOffset, production->end() };




108,996✔





58



}










59













60



std::vector<int> LR1Item::getLookaheads(const Grammar& grammar) const {




37,940✔






61



    auto ids = grammar.toTerminalIds(lookaheadBits);




37,940✔






62



    std::sort(ids.begin(), ids.end());




37,940✔






63



    return ids;




37,940✔






UNCOV

64



}




×







65













66



const LR1Item::LookaheadSet& LR1Item::lookaheads() const noexcept {




2,261,222✔






67



    return lookaheadBits;




2,261,222✔





68



}










69













70



bool LR1Item::hasLookahead(int symbolId, const Grammar& grammar) const {




6✔






71



    return lookaheadBits.test(static_cast<std::size_t>(grammar.terminalBit(symbolId)));




6✔





72



}










73













74



const Production& LR1Item::getProduction() const {




31,174✔






75



    return *production;




31,174✔





76



}










77













78



std::uint64_t LR1Item::coreKey() const noexcept {




152,640,100✔






79



    return (static_cast<std::uint64_t>(static_cast<std::uint32_t>(production->getId())) << 32)




152,640,100✔






80



            | static_cast<std::uint32_t>(visitedOffset);




152,640,100✔





81



}










82













83



bool LR1Item::operator==(const LR1Item& rhs) const {




659,070✔






84



    return coreKey() == rhs.coreKey() && lookaheadBits == rhs.lookaheadBits;




659,070✔





85



}










86












87



std::string LR1Item::str(const Grammar& grammar) const {




36,326✔





88



    std::stringstream out;




36,326✔






89



    out << "[ " << grammar.str(production->getDefiningSymbol()) << " -> ";




36,326✔






90



    for (const auto& s : getVisited()) {




44,396✔






91



        out << grammar.str(s) << " ";




8,070✔





92



    }




36,326✔





93



    out << ". ";




36,326✔






94



    for (const auto& s : getExpectedSymbols()) {




110,722✔






95



        out << grammar.str(s) << " ";




74,396✔





96



    }




36,326✔





97



    out << ", ";




36,326✔






98



    for (const auto& s : getLookaheads(grammar)) {




746,142✔






99



        out << grammar.str(s) << " ";




709,816✔





100



    }




36,326✔





101



    out << "]\n";




36,326✔





102



    return out.str();




72,652✔





103



}




36,326✔





104












105



} // namespace parser
























    

  • 

    •