LCOV - code coverage report
Current view: top level - core/source - dparser.cpp (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 74 240 30.8 %
Date: 2020-02-28 00:44:21 Functions: 20 38 52.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Author(s): Wieger Wesselink
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : /// \file mcrl2/core/dparser.cpp
      10             : /// \brief add your file description here.
      11             : 
      12             : #include <d.h>
      13             : #include "mcrl2/core/detail/dparser_functions.h"
      14             : #include "mcrl2/utilities/logger.h"
      15             : #include <iomanip>
      16             : #include <locale>
      17             : 
      18             : extern "C"
      19             : {
      20             :   extern D_ParserTables parser_tables_mcrl2;
      21             : }
      22             : 
      23             : namespace mcrl2 {
      24             : 
      25             : namespace core {
      26             : 
      27           4 : std::string parse_node::add_context(const std::string& message) const
      28             : {
      29           4 :   return detail::add_context(&node->start_loc, message);
      30             : }
      31             : 
      32      713012 : int parse_node::symbol() const
      33             : {
      34      713012 :   return node->symbol;
      35             : }
      36             : 
      37      742171 : int parse_node::child_count() const
      38             : {
      39      742171 :   return d_get_number_of_children(node);
      40             : }
      41             : 
      42             : // 0 <= i < child_count()
      43      578455 : parse_node parse_node::child(int i) const
      44             : {
      45      578455 :   return parse_node(d_get_child(node, i));
      46             : }
      47             : 
      48           0 : parse_node parse_node::find_in_tree(int symbol) const
      49             : {
      50           0 :   return parse_node(d_find_in_tree(node, symbol));
      51             : }
      52             : 
      53      103701 : std::string parse_node::string() const
      54             : {
      55      103701 :   return std::string(node->start_loc.s, node->end - node->start_loc.s);
      56             : }
      57             : 
      58           0 : std::string parse_node::tree() const
      59             : {
      60           0 :   if (child_count() < 2)
      61           0 :     return this->string();
      62           0 :   std::stringstream result;
      63           0 :   result << "(" << child(0).tree();
      64           0 :   for (int i = 1; i < child_count(); ++i)
      65           0 :     result << " " << child(i).tree();
      66           0 :   result << ")";
      67           0 :   return result.str();
      68             : }
      69             : 
      70           0 : int parse_node::column() const
      71             : {
      72           0 :   return node->start_loc.col;
      73             : }
      74             : 
      75           0 : int parse_node::line() const
      76             : {
      77           0 :   return node->start_loc.line;
      78             : }
      79             : 
      80           0 : std::string parse_node::pathname() const
      81             : {
      82           0 :   return std::string(node->start_loc.pathname);
      83             : }
      84             : 
      85     1162688 : parse_node::~parse_node()
      86             : {
      87      581344 :   if (parser)
      88             :   {
      89        2889 :     free_D_ParseNode(parser, node);
      90             :   }
      91      581344 : }
      92             : 
      93             : // Prints a tree of
      94           0 : std::string parser_table::tree(const core::parse_node& node) const
      95             : {
      96           0 :   std::stringstream result;
      97           0 :   result << symbol_name(node) << "(";
      98           0 :   if (node.child_count() == 0)
      99           0 :     result << '"' << node.string() << '"';
     100             :   else
     101           0 :     result << tree(node.child(0));
     102           0 :   for (int i = 1; i < node.child_count(); ++i)
     103           0 :     result << " " << tree(node.child(i));
     104           0 :   result << ")";
     105           0 :   return result.str();
     106             : }
     107             : 
     108             : // Returns the number of symbols in the table
     109      301979 : unsigned int parser_table::symbol_count() const
     110             : {
     111      301979 :   return m_table.nsymbols;
     112             : }
     113             : 
     114             : // Returns the name of the i-th symbol
     115      820504 : std::string parser_table::symbol_name(unsigned int i) const
     116             : {
     117      820504 :   if (i >= m_table.nsymbols)
     118             :   {
     119           0 :     print();
     120           0 :     std::ostringstream out;
     121           0 :     out << "parser_table::symbol_name: index " << i << " out of bounds!";
     122           0 :     throw std::runtime_error(out.str());
     123             :   }
     124      820504 :   const char* name = m_table.symbols[i].name;
     125      820504 :   if (!name)
     126             :   {
     127           0 :     return "";
     128             :   }
     129      820504 :   return std::string(name);
     130             : }
     131             : 
     132      106039 : std::string parser_table::symbol_name(const parse_node& node) const
     133             : {
     134      106039 :   return symbol_name(node.symbol());
     135             : }
     136             : 
     137             : // Returns the 'start symbol' of the i-th symbol
     138        2889 : int parser_table::start_symbol(unsigned int i) const
     139             : {
     140        2889 :   return m_table.symbols[i].start_symbol;
     141             : }
     142             : 
     143             : // Returns true if the i-th symbol is of type D_SYMBOL_NTERM
     144      301979 : bool parser_table::is_term_symbol(unsigned int i) const
     145             : {
     146      301979 :   return m_table.symbols[i].kind == D_SYMBOL_NTERM;
     147             : }
     148             : 
     149        2889 : unsigned int parser_table::start_symbol_index(const std::string& name) const
     150             : {
     151      301979 :   for (unsigned int i = 0; i < symbol_count(); i++)
     152             :   {
     153      301979 :     if (is_term_symbol(i) && symbol_name(i) == name)
     154             :     {
     155        2889 :       return start_symbol(i);
     156             :     }
     157             :   }
     158           0 :   throw mcrl2::runtime_error("unknown start symbol '" + name + "'");
     159             :   return 0;
     160             : }
     161             : 
     162           0 : void parser_table::print() const
     163             : {
     164           0 :   std::clog << "--------------------" << std::endl;
     165           0 :   std::clog << "-   symbol table   -" << std::endl;
     166           0 :   std::clog << "--------------------" << std::endl;
     167           0 :   for (unsigned int i = 0; i < symbol_count(); i++)
     168             :   {
     169           0 :     std::clog << std::setw(3) << i << " " << symbol_name(i) << std::endl;
     170             :   }
     171           0 :   std::clog << "--------------------" << std::endl;
     172           0 : }
     173             : 
     174        2889 : parser::parser(D_ParserTables& tables, D_AmbiguityFn ambiguity_fn, D_SyntaxErrorFn syntax_error_fn, std::size_t max_error_message_count)
     175        2889 :   : m_table(tables)
     176             : {
     177        2889 :   detail::set_dparser_max_error_message_count(max_error_message_count);
     178        2889 :   m_parser = new_D_Parser(&tables, 0);
     179        2889 :   m_parser->initial_globals = this;
     180        2889 :   m_parser->save_parse_tree = 1;
     181        2889 :   m_parser->initial_scope = nullptr;
     182        2889 :   m_parser->dont_use_greediness_for_disambiguation = 1;
     183        2889 :   m_parser->dont_use_height_for_disambiguation = 1;
     184        2889 :   if (ambiguity_fn)
     185             :   {
     186        2885 :     m_parser->ambiguity_fn = ambiguity_fn;
     187             :   }
     188        2889 :   if (syntax_error_fn)
     189             :   {
     190        2885 :     m_parser->syntax_error_fn = syntax_error_fn;
     191             :   }
     192        2889 : }
     193             : 
     194        5778 : parser::~parser()
     195             : {
     196        2889 :   free_D_Parser(m_parser);
     197        2889 : }
     198             : 
     199      631025 : const parser_table& parser::symbol_table() const
     200             : {
     201      631025 :   return m_table;
     202             : }
     203             : 
     204        2889 : unsigned int parser::start_symbol_index(const std::string& name) const
     205             : {
     206        2889 :   return m_table.start_symbol_index(name);
     207             : }
     208             : 
     209        2889 : parse_node parser::parse(const std::string& text, unsigned int start_symbol_index, bool partial_parses)
     210             : {
     211        2889 :   detail::reset_dparser_error_message_count();
     212        2889 :   m_parser->start_state = start_symbol_index;
     213        2889 :   m_parser->partial_parses = partial_parses ? 1 : 0;
     214        2889 :   D_ParseNode* result = dparse(m_parser, const_cast<char*>(text.c_str()), static_cast<int>(text.size()));
     215        2889 :   if (!result || m_parser->syntax_errors)
     216             :   {
     217           0 :     throw mcrl2::runtime_error("syntax error");
     218             :   }
     219        2889 :   return parse_node(result, m_parser);
     220             : }
     221             : 
     222           0 : void parser::print_symbol_table() const
     223             : {
     224           0 :   m_table.print();
     225           0 : }
     226             : 
     227           0 : std::string parser::indent(unsigned int count) const
     228             : {
     229           0 :   return std::string(count, ' ');
     230             : }
     231             : 
     232           0 : std::string parser::truncate(const std::string& s, unsigned int max_size) const
     233             : {
     234           0 :   std::string result = s.substr(0, max_size);
     235             : 
     236             :   // truncate at newline
     237           0 :   std::string::size_type pos = result.find('\n');
     238           0 :   if (pos != std::string::npos)
     239             :   {
     240           0 :     result = result.substr(0, pos);
     241             :   }
     242             : 
     243           0 :   return result;
     244             : }
     245             : 
     246           0 : void parser::print_tree(const parse_node& node, unsigned int level) const
     247             : {
     248           0 :   if (node)
     249             :   {
     250           0 :     std::string symbol = m_table.symbol_name(node.symbol());
     251           0 :     std::string prefix = indent(2 * level);
     252           0 :     std::cout << prefix << "--- " << symbol << " \"" << truncate(node.string()) << "\"" << std::endl;
     253           0 :     for (int i = 0; i <= node.child_count(); i++)
     254             :     {
     255           0 :       print_tree(node.child(i), level + 1);
     256             :     }
     257             :   }
     258           0 : }
     259             : 
     260           0 : void parser::destroy_parse_node(const parse_node& node)
     261             : {
     262           0 :   free_D_ParseNode(m_parser, node.node);
     263           0 : }
     264             : 
     265             : /// \brief Callback function for nodes in the parse tree
     266           0 : void parser::announce(D_ParseNode& node_ref)
     267             : {
     268           0 :   parse_node node(&node_ref);
     269           0 :   std::cout << "parsed " << m_table.symbol_name(node.symbol()) << " " << node.string() << std::endl;
     270           0 : }
     271             : 
     272             : namespace detail {
     273             : 
     274           4 : std::string add_context(const d_loc_t* loc, const std::string& message)
     275             : {
     276           8 :   std::stringstream s;
     277           4 :   s << "Line " << loc->line << ", column " << loc->col << ": "
     278           4 :     << message << std::endl;
     279           4 :   char* beg = loc->s - loc->col;
     280           4 :   char* end = loc->s;
     281          30 :   while (*end != '\0' && *end != '\n' && *end != '\r')
     282             :   {
     283          13 :     ++end;
     284             :   }
     285           8 :   std::string line(beg, end);
     286           4 :   s << "  " << line << std::endl;
     287          33 :   for (int i = 0; i < loc->col + 2; ++i)
     288             :   {
     289          29 :     s << ' ';
     290             :   }
     291           4 :   s << '^';
     292           8 :   return s.str();
     293             : }
     294             : 
     295             : inline
     296           0 : bool is_all_of_type(D_ParseNode* nodes[], int n, const char* type, const core::parser_table& table)
     297             : {
     298           0 :   for (int i = 0; i < n; i++)
     299             :   {
     300           0 :     core::parse_node node(nodes[i]);
     301           0 :     if (table.symbol_name(node) != type)
     302             :     {
     303           0 :       return false;
     304             :     }
     305             :   }
     306           0 :   return true;
     307             : }
     308             : 
     309             : inline
     310             : void print_ambiguous_nodes(D_ParseNode* nodes[], int n, const char* type, const core::parser_table& table)
     311             : {
     312             :   mCRL2log(log::verbose, "parser") << "--- " << type << " ambiguity" << std::endl;
     313             :   for (int i = 0; i < n; ++i)
     314             :   {
     315             :     core::parse_node vi(nodes[i]);
     316             :     // mCRL2log(log::verbose, "parser") << vi.tree() << " " << table.tree(vi) << std::endl;
     317             :     mCRL2log(log::verbose, "parser") << "ALT " << table.tree(vi) << std::endl;
     318             :   }
     319             : }
     320             : 
     321             : inline
     322             : void print_chosen_node(D_ParseNode* node, const core::parser_table& table)
     323             : {
     324             :   core::parse_node vi(node);
     325             :   mCRL2log(log::verbose, "parser") << "CHOOSE " << table.tree(vi) << std::endl;
     326             : }
     327             : 
     328             : /// \brief Function for resolving parser ambiguities.
     329           0 : D_ParseNode* ambiguity_fn(struct D_Parser * /*p*/, int n, struct D_ParseNode **v)
     330             : {
     331           0 :   core::parser_table table(parser_tables_mcrl2);
     332             : 
     333             :   // resolve PbesExpr ambiguities
     334           0 :   if (is_all_of_type(v, n, "PbesExpr", table))
     335             :   {
     336           0 :     D_ParseNode* result = nullptr;
     337           0 :     for (int i = 0; i < n; i++)
     338             :     {
     339           0 :       core::parse_node node(v[i]);
     340           0 :       if (table.symbol_name(node.child(0)) == "Id")
     341             :       {
     342           0 :         return v[i];
     343             :       }
     344           0 :       else if (table.symbol_name(node.child(0)) != "DataExpr")
     345             :       {
     346           0 :         result = v[i];
     347             :       }
     348             :     }
     349           0 :     if (result)
     350             :     {
     351           0 :       return result;
     352             :     }
     353           0 :     return v[0];
     354             :   }
     355             : 
     356             :   // resolve ActFrm ambiguities
     357           0 :   if (is_all_of_type(v, n, "ActFrm", table))
     358             :   {
     359             : //print_ambiguous_nodes(v, n, "ActFrm", table);
     360           0 :     D_ParseNode* result = nullptr;
     361           0 :     for (int i = 0; i < n; i++)
     362             :     {
     363           0 :       core::parse_node node(v[i]);
     364           0 :       if (table.symbol_name(node.child(0)) == "MultAct")
     365             :       {
     366             : //print_chosen_node(v[i], table);
     367           0 :         return v[i];
     368             :       }
     369           0 :       else if (table.symbol_name(node.child(0)) != "DataExpr")
     370             :       {
     371           0 :         result = v[i];
     372             :       }
     373             :     }
     374           0 :     if (result)
     375             :     {
     376             : //print_chosen_node(result, table);
     377           0 :       return result;
     378             :     }
     379             : //print_chosen_node(v[0], table);
     380           0 :     return v[0];
     381             :   }
     382             : 
     383             :   // resolve StateFrm ambiguities
     384           0 :   if (is_all_of_type(v, n, "StateFrm", table))
     385             :   {
     386             : //print_ambiguous_nodes(v, n, "StateFrm", table);
     387           0 :     D_ParseNode* result = nullptr;
     388           0 :     for (int i = 0; i < n; i++)
     389             :     {
     390           0 :       core::parse_node node(v[i]);
     391           0 :       if (table.symbol_name(node.child(0)) == "Id")
     392             :       {
     393             : //print_chosen_node(v[i], table);
     394           0 :         return v[i];
     395             :       }
     396           0 :       else if (table.symbol_name(node.child(0)) != "DataExpr")
     397             :       {
     398           0 :         result = v[i];
     399             :       }
     400             :     }
     401           0 :     if (result)
     402             :     {
     403             : //print_chosen_node(result, table);
     404           0 :       return result;
     405             :     }
     406             : //print_chosen_node(v[0], table);
     407           0 :     return v[0];
     408             :   }
     409             : 
     410             :   // resolve RegFrm ambiguities
     411           0 :   if (is_all_of_type(v, n, "RegFrm", table))
     412             :   {
     413             : //print_ambiguous_nodes(v, n, "RegFrm", table);
     414           0 :     for (int i = 0; i < n; i++)
     415             :     {
     416           0 :       core::parse_node node(v[i]);
     417           0 :       if (table.symbol_name(node.child(0)) == "RegFrm" || table.symbol_name(node.child(0)) == "(")
     418             :       {
     419             : //print_chosen_node(v[i], table);
     420           0 :         return v[i];
     421             :       }
     422             :     }
     423             :   }
     424             : 
     425             :   // If we reach this point, then the ambiguity is unresolved. We print all
     426             :   // ambiguities on the debug output, then throw an exception.
     427           0 :   for (int i = 0; i < n; ++i)
     428             :   {
     429           0 :     core::parse_node vi(v[i]);
     430           0 :     mCRL2log(log::verbose, "parser") << "Ambiguity: " << vi.tree() << std::endl;
     431           0 :     mCRL2log(log::debug, "parser") << "Ambiguity: " << table.tree(vi) << std::endl;
     432             :   }
     433           0 :   throw mcrl2::runtime_error("Unresolved ambiguity.");
     434             : }
     435             : 
     436           0 : static void log_location(struct D_Parser *ap)
     437             : {
     438             :   // We recover information about the last parsed node by casting D_Parser to Parser, which
     439             :   // is the structure that the dparser library internally uses to keep its administration in.
     440           0 :   std::string after;
     441           0 :   SNode *s = ((Parser*)ap)->snode_hash.last_all;
     442           0 :   ZNode *z = s != nullptr ? s->zns.v[0] : nullptr;
     443           0 :   while (z != nullptr && z->pn->parse_node.start_loc.s == z->pn->parse_node.end)
     444             :   {
     445           0 :     z = (z->sns.v && z->sns.v[0]->zns.v) ? z->sns.v[0]->zns.v[0] : nullptr;
     446             :   }
     447           0 :   if (z && z->pn->parse_node.start_loc.s != z->pn->parse_node.end)
     448             :   {
     449           0 :     after = std::string(z->pn->parse_node.start_loc.s, z->pn->parse_node.end);
     450             :   }
     451             : 
     452           0 :   std::string message = "syntax error";
     453           0 :   if (!after.empty())
     454             :   {
     455           0 :     message = message + " after '" + after + "'";
     456             :   }
     457           0 :   mCRL2log(log::error, "parser") << add_context(&ap->loc, message) << std::endl;
     458           0 : }
     459             : 
     460           0 : void syntax_error_fn(struct D_Parser *ap)
     461             : {
     462           0 :   core::detail::increment_dparser_error_message_count();
     463           0 :   if (core::detail::get_dparser_error_message_count() > core::detail::get_dparser_max_error_message_count())
     464             :   {
     465           0 :     return;
     466             :   }
     467           0 :   log_location(ap);
     468           0 :   if (ap->loc.s == nullptr)
     469             :   {
     470           0 :     mCRL2log(log::error, "parser") << "Unexpected end of input." << std::endl;
     471             :   }
     472             :   else
     473             :   {
     474             :     // Dive into the internals of dparser to recover some extra diagnostics.
     475           0 :     Parser* p = (Parser*)ap;
     476           0 :     if (p->pnode_hash.all && p->pnode_hash.all->latest)
     477             :     {
     478           0 :       core::parse_node n(&p->pnode_hash.all->latest->parse_node);
     479           0 :       D_Symbol &s = p->t->symbols[n.symbol()];
     480           0 :       if (s.kind == D_SYMBOL_INTERNAL)
     481             :       {
     482             :         /* DParser stores production rules in order: search for the corresponding nonterminal. */
     483           0 :         int parentsym = n.symbol() - 1;
     484           0 :         while (p->t->symbols[parentsym].kind == D_SYMBOL_INTERNAL)
     485           0 :           --parentsym;
     486           0 :         s = p->t->symbols[parentsym];
     487             :       }
     488             : 
     489           0 :       switch (s.kind)
     490             :       {
     491           0 :       case D_SYMBOL_STRING:
     492             :       case D_SYMBOL_TOKEN:
     493             :         {
     494           0 :           std::locale loc;
     495           0 :           mCRL2log(log::error, "parser") << "Unexpected "
     496           0 :                                          << (std::isalpha(n.string()[0], loc) ? "keyword " : "")
     497           0 :                                          << "'" << n.string() << "'" << std::endl;
     498             :         }
     499           0 :         break;
     500           0 :       case D_SYMBOL_NTERM:
     501           0 :         mCRL2log(log::error, "parser") << "Unexpected " << s.name << " '" << n.string() << "'" << std::endl;
     502           0 :         break;
     503           0 :       default:
     504             :         // TODO: check if we can give more sensible output in the remaining cases.
     505           0 :         break;
     506             :       }
     507             :     }
     508             :   }
     509             : }
     510             : 
     511             : } // namespace detail
     512             : 
     513           0 : void parser::custom_parse_error(const std::string& message) const
     514             : {
     515           0 :   core::detail::increment_dparser_error_message_count();
     516           0 :   if (core::detail::get_dparser_error_message_count() > core::detail::get_dparser_max_error_message_count())
     517             :   {
     518           0 :     return;
     519             :   }
     520           0 :   detail::log_location(m_parser);
     521           0 :   mCRL2log(log::error, "parser") << message << std::endl;
     522             : }
     523             : 
     524             : } // namespace core
     525             : 
     526         381 : } // namespace mcrl2
     527             : 

Generated by: LCOV version 1.13