src/libshared/src/Packrat.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2015 - 2017, Paul Beckingham, Federico Hernandez.
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining a copy
   6 // of this software and associated documentation files (the "Software"), to deal
   7 // in the Software without restriction, including without limitation the rights
   8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 // copies of the Software, and to permit persons to whom the Software is
  10 // furnished to do so, subject to the following conditions:
  11 //
  12 // The above copyright notice and this permission notice shall be included
  13 // in all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  16 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21 // SOFTWARE.
  22 //
  23 // http://www.opensource.org/licenses/mit-license.php
  24 //
  25 ////////////////////////////////////////////////////////////////////////////////
  26
  27 #include <cmake.h>
  28 #include <Packrat.h>
  29 #include <shared.h>
  30 #include <format.h>
  31 #include <unicode.h>
  32 #include <utf8.h>
  33 #include <iostream>
  34
  35 int Packrat::minimumMatchLength = 3;
  36
  37 ////////////////////////////////////////////////////////////////////////////////
  38 void Packrat::debug ()
  39 {
  40   ++_debug;
  41 }
  42
  43 ////////////////////////////////////////////////////////////////////////////////
  44 // Walk the grammar tree to parse the input text, resulting in a parse tree.
  45 void Packrat::parse (const PEG& peg, const std::string& input)
  46 {
  47   // Used to walk the grammar tree.
  48   // Note there is only one rule at the top of the syntax tree, which was the
  49   // first one defined.
  50   _syntax = peg.syntax ();
  51   _tree->_name = peg.firstRule ();
  52
  53   // The pig that will be sent down the pipe.
  54   Pig pig (input);
  55   if (_debug)
  56     std::cout << "trace " << pig.dump () << "\n";
  57
  58   // Match the first rule.  Recursion does the rest.
  59   if (! matchRule (_tree->_name, pig, _tree, 0))
  60     throw std::string ("Parse failed.");
  61
  62   if (! pig.eos ())
  63     throw format ("Parse failed - extra character at position {1}.", pig.cursor ());
  64 }
  65
  66 ////////////////////////////////////////////////////////////////////////////////
  67 void Packrat::entity (const std::string& category, const std::string& name)
  68 {
  69   // Walk the list of entities for category.
  70   auto c = _entities.equal_range (category);
  71   for (auto e = c.first; e != c.second; ++e)
  72     if (e->second == name)
  73       return;
  74
  75   // The category/name pair was not found, therefore add it.
  76   _entities.insert (std::pair <std::string, std::string> (category, name));
  77 }
  78
  79 ////////////////////////////////////////////////////////////////////////////////
  80 void Packrat::external (
  81   const std::string& rule,
  82   bool (*fn)(Pig&, std::shared_ptr <Tree>))
  83 {
  84   if (_externals.find (rule) != _externals.end ())
  85     throw format ("There is already an external parser defined for rule '{1}'.", rule);
  86
  87   _externals[rule] = fn;
  88 }
  89
  90 ////////////////////////////////////////////////////////////////////////////////
  91 // If there is a match, pig advances further down the pipe.
  92 bool Packrat::matchRule (
  93   const std::string& rule,
  94   Pig& pig,
  95   std::shared_ptr <Tree> parseTree,
  96   int indent)
  97 {
  98   if (_debug > 1)
  99     std::cout << "trace " << std::string (indent, ' ') << "matchRule " << rule << "\n";
 100   auto checkpoint = pig.cursor ();
 101
 102   for (const auto& production : _syntax.find (rule)->second)
 103     if (matchProduction (production, pig, parseTree, indent + 1))
 104       return true;
 105
 106   pig.restoreTo (checkpoint);
 107   return false;
 108 }
 109
 110 ////////////////////////////////////////////////////////////////////////////////
 111 bool Packrat::matchProduction (
 112   const PEG::Production& production,
 113   Pig& pig,
 114   std::shared_ptr <Tree> parseTree,
 115   int indent)
 116 {
 117   if (_debug > 1)
 118     std::cout << "trace " << std::string (indent, ' ') << "matchProduction\n";
 119   auto checkpoint = pig.cursor ();
 120
 121   auto collector = std::make_shared <Tree> ();
 122   for (const auto& token : production)
 123   {
 124     auto b = std::make_shared <Tree> ();
 125     if (! matchTokenQuant (token, pig, b, indent + 1))
 126     {
 127       pig.restoreTo (checkpoint);
 128       return false;
 129     }
 130
 131     // Accumulate branches.
 132     collector->addBranch (b);
 133   }
 134
 135   // On success transfer all sub-branches.
 136   for (auto& b : collector->_branches)
 137     for (auto sub : b->_branches)
 138       parseTree->addBranch (sub);
 139
 140   return true;
 141 }
 142
 143 ////////////////////////////////////////////////////////////////////////////////
 144 // Wraps calls to matchTokenLookahead, while properly handling the quantifier.
 145 bool Packrat::matchTokenQuant (
 146   const PEG::Token& token,
 147   Pig& pig,
 148   std::shared_ptr <Tree> parseTree,
 149   int indent)
 150 {
 151   if (_debug > 1)
 152     std::cout << "trace " << std::string (indent, ' ') << "matchTokenQuant " << token.dump () << "\n";
 153
 154   // Must match exactly once, so run once and return the result.
 155   if (token._quantifier == PEG::Token::Quantifier::one)
 156   {
 157     return matchTokenLookahead (token, pig, parseTree, indent + 1);
 158   }
 159
 160   // May match zero or one time.  If it matches, the cursor will be advanced.
 161   // If it fails, the cursor will not be advanced, but this is still considered
 162   // successful.  Return true either way, but backtrack the cursor on failure.
 163   else if (token._quantifier == PEG::Token::Quantifier::zero_or_one)
 164   {
 165     // Check for a single match, succeed anyway.
 166     matchTokenLookahead (token, pig, parseTree, indent + 1);
 167     if (_debug > 1)
 168       std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch ?\e[0m " << token.dump () << "\n";
 169     if (_debug)
 170       std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 171     return true;
 172   }
 173
 174   // May match 1 or more times.  If it matches on the first attempt, continue
 175   // to greedily match until it fails.  If it fails on the first attempt, then
 176   // the rule fails.
 177   else if (token._quantifier == PEG::Token::Quantifier::one_or_more)
 178   {
 179     if (! matchTokenLookahead (token, pig, parseTree, indent + 1))
 180       return false;
 181
 182     while (matchTokenLookahead (token, pig, parseTree, indent + 1))
 183     {
 184       // "Forget it, he's rolling."
 185     }
 186
 187     if (_debug > 1)
 188       std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch +\e[0m " << token.dump () << "\n";
 189     if (_debug)
 190       std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 191     return true;
 192   }
 193
 194   // May match zero or more times.  Keep calling while there are matches, and
 195   // return true always.  Backtrack the cursor on failure.
 196   else if (token._quantifier == PEG::Token::Quantifier::zero_or_more)
 197   {
 198     while (matchTokenLookahead (token, pig, parseTree, indent + 1))
 199     {
 200       // Let it go.
 201     }
 202
 203     if (_debug > 1)
 204       std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch *\e[0m " << token.dump () << "\n";
 205     if (_debug)
 206       std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 207     return true;
 208   }
 209
 210   throw std::string ("This should never happen.");
 211   return false;
 212 }
 213
 214 ////////////////////////////////////////////////////////////////////////////////
 215 // Wraps calls to matchToken, while properly handling lookahead.
 216 bool Packrat::matchTokenLookahead (
 217   const PEG::Token& token,
 218   Pig& pig,
 219   std::shared_ptr <Tree> parseTree,
 220   int indent)
 221 {
 222   if (_debug > 1)
 223     std::cout << "trace " << std::string (indent, ' ') << "matchTokenLookahead " << token.dump () << "\n";
 224
 225   if (token._lookahead == PEG::Token::Lookahead::none)
 226   {
 227     return matchToken (token, pig, parseTree, indent + 1);
 228   }
 229   else if (token._lookahead == PEG::Token::Lookahead::positive)
 230   {
 231     auto checkpoint = pig.cursor ();
 232     auto b = std::make_shared <Tree> ();
 233     if (matchToken (token, pig, b, indent + 1))
 234     {
 235       pig.restoreTo (checkpoint);
 236       return true;
 237     }
 238   }
 239   else if (token._lookahead == PEG::Token::Lookahead::negative)
 240   {
 241     auto checkpoint = pig.cursor ();
 242     auto b = std::make_shared <Tree> ();
 243     if (! matchToken (token, pig, b, indent + 1))
 244     {
 245       return true;
 246     }
 247
 248     pig.restoreTo (checkpoint);
 249   }
 250
 251   return false;
 252 }
 253
 254 ////////////////////////////////////////////////////////////////////////////////
 255 bool Packrat::matchToken (
 256   const PEG::Token& token,
 257   Pig& pig,
 258   std::shared_ptr <Tree> parseTree,
 259   int indent)
 260 {
 261   if (_debug > 1)
 262     std::cout << "trace " << std::string (indent, ' ') << "matchToken " << token.dump () << "\n";
 263
 264   auto checkpoint = pig.cursor ();
 265   auto b = std::make_shared <Tree> ();
 266
 267   if (token.hasTag ("intrinsic") &&
 268       matchIntrinsic (token, pig, parseTree, indent + 1))
 269   {
 270     return true;
 271   }
 272
 273   else if (_syntax.find (token._token) != _syntax.end () &&
 274            matchRule (token._token, pig, b, indent + 1))
 275   {
 276     // This is the only case that adds a sub-branch.
 277     b->_name = token._token;
 278     parseTree->addBranch (b);
 279     return true;
 280   }
 281
 282   else if (token.hasTag ("literal") &&
 283            token.hasTag ("character") &&
 284            matchCharLiteral (token, pig, parseTree, indent + 1))
 285   {
 286    return true;
 287   }
 288
 289   else if (token.hasTag ("literal") &&
 290            token.hasTag ("string") &&
 291            matchStringLiteral (token, pig, parseTree, indent + 1))
 292   {
 293     return true;
 294   }
 295
 296   pig.restoreTo (checkpoint);
 297   return false;
 298 }
 299
 300 ////////////////////////////////////////////////////////////////////////////////
 301 // Supports the following:
 302 //   <digit>      --> unicodeLatinDigit
 303 //   <hex>        --> unicodeHexDigit
 304 //   <character>  --> anything
 305 //   <alpha>      --> unicodeAlpha
 306 //   <punct>      --> unicodePunctuation
 307 //   <ws>         --> unicodeWhitespace
 308 //   <sep>        --> unicodeHorizontalWhitespace
 309 //   <eol>        --> unicodeVerticalWhitespace
 310 //   <word>       --> <alpha>
 311 //   <token>      --> consecutive non <ws>
 312 //   <entity:e>   --> Any category 'e' token
 313 //   <external:x> --> Delegate to external function
 314 bool Packrat::matchIntrinsic (
 315   const PEG::Token& token,
 316   Pig& pig,
 317   std::shared_ptr <Tree> parseTree,
 318   int indent)
 319 {
 320   if (_debug > 1)
 321     std::cout << "trace " << std::string (indent, ' ') << "matchIntrinsic " << token.dump () << "\n";
 322   auto checkpoint = pig.cursor ();
 323
 324   // There are only 10 digits.
 325   if (token._token == "<digit>")
 326   {
 327     int digit;
 328     if (pig.getDigit (digit))
 329     {
 330       // Create a populated branch.
 331       auto b = std::make_shared <Tree> ();
 332       b->_name = "intrinsic";
 333       b->attribute ("expected", token._token);
 334       b->attribute ("value", format ("{1}", digit));
 335       parseTree->addBranch (b);
 336
 337       if (_debug > 1)
 338         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << digit << "\n";
 339       if (_debug)
 340         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 341       return true;
 342     }
 343   }
 344
 345   // Upper or lower case hex digit.
 346   if (token._token == "<hex>")
 347   {
 348     int digit;
 349     if (pig.getHexDigit (digit))
 350     {
 351       // Create a populated branch.
 352       auto b = std::make_shared <Tree> ();
 353       b->_name = "intrinsic";
 354       b->attribute ("expected", token._token);
 355       b->attribute ("value", format ("{1}", digit));
 356       parseTree->addBranch (b);
 357
 358       if (_debug > 1)
 359         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << digit << "\n";
 360       if (_debug)
 361         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 362       return true;
 363     }
 364   }
 365
 366   // Character means anything.
 367   else if (token._token == "<character>")
 368   {
 369     int character;
 370     if (pig.getCharacter (character))
 371     {
 372       // Create a populated branch.
 373       auto b = std::make_shared <Tree> ();
 374       b->_name = "intrinsic";
 375       b->attribute ("expected", token._token);
 376       b->attribute ("value", format ("{1}", character));
 377       parseTree->addBranch (b);
 378
 379       if (_debug > 1)
 380         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << character << "\n";
 381       if (_debug)
 382         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 383       return true;
 384     }
 385   }
 386
 387   // <punct> ::ispunct
 388   else if (token._token == "<punct>")
 389   {
 390     int character = pig.peek ();
 391     if (unicodePunctuation (character))
 392     {
 393       pig.skip (character);
 394
 395       // Create a populated branch.
 396       auto b = std::make_shared <Tree> ();
 397       b->_name = "intrinsic";
 398       b->attribute ("expected", token._token);
 399       b->attribute ("value", format ("{1}", character));
 400       parseTree->addBranch (b);
 401
 402       if (_debug > 1)
 403         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << character << "\n";
 404       if (_debug)
 405         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 406       return true;
 407     }
 408   }
 409
 410   // <alpha>
 411   else if (token._token == "<alpha>")
 412   {
 413     int character = pig.peek ();
 414     if (unicodeAlpha (character))
 415     {
 416       pig.skip (character);
 417
 418       // Create a populated branch.
 419       auto b = std::make_shared <Tree> ();
 420       b->_name = "intrinsic";
 421       b->attribute ("expected", token._token);
 422       b->attribute ("value", format ("{1}", character));
 423       parseTree->addBranch (b);
 424
 425       if (_debug > 1)
 426         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << character << "\n";
 427       if (_debug)
 428         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 429       return true;
 430     }
 431   }
 432
 433   // <ws>
 434   else if (token._token == "<ws>")
 435   {
 436     int character = pig.peek ();
 437     if (unicodeWhitespace (character))
 438     {
 439       pig.skip (character);
 440
 441       // Create a populated branch.
 442       auto b = std::make_shared <Tree> ();
 443       b->_name = "intrinsic";
 444       b->attribute ("expected", token._token);
 445       b->attribute ("value", format ("{1}", character));
 446       parseTree->addBranch (b);
 447
 448       if (_debug > 10)
 449         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << character << "\n";
 450       if (_debug)
 451         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 452       return true;
 453     }
 454   }
 455
 456   // <sep>
 457   else if (token._token == "<sep>")
 458   {
 459     int character = pig.peek ();
 460     if (unicodeHorizontalWhitespace (character))
 461     {
 462       pig.skip (character);
 463
 464       // Create a populated branch.
 465       auto b = std::make_shared <Tree> ();
 466       b->_name = "intrinsic";
 467       b->attribute ("expected", token._token);
 468       b->attribute ("value", format ("{1}", character));
 469       parseTree->addBranch (b);
 470
 471       if (_debug > 1)
 472         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << character << "\n";
 473       if (_debug)
 474         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 475       return true;
 476     }
 477   }
 478
 479   // <eol>
 480   else if (token._token == "<eol>")
 481   {
 482     int character = pig.peek ();
 483     if (unicodeVerticalWhitespace (character))
 484     {
 485       pig.skip (character);
 486
 487       // Create a populated branch.
 488       auto b = std::make_shared <Tree> ();
 489       b->_name = "intrinsic";
 490       b->attribute ("expected", token._token);
 491       b->attribute ("value", format ("{1}", character));
 492       parseTree->addBranch (b);
 493
 494       if (_debug > 1)
 495         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << character << "\n";
 496       if (_debug)
 497         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 498       return true;
 499     }
 500   }
 501
 502   // <word> consecutive non-<ws>, non-<punct>.
 503   else if (token._token == "<word>")
 504   {
 505     while (auto character = pig.peek ())
 506     {
 507       if (! character ||
 508           unicodeWhitespace (character) ||
 509           unicodePunctuation (character))
 510         break;
 511
 512       pig.skip (character);
 513     }
 514
 515     if (pig.cursor () > checkpoint)
 516     {
 517       auto word = pig.substr (checkpoint, pig.cursor () - checkpoint + 1);
 518
 519       // Create a populated branch.
 520       auto b = std::make_shared <Tree> ();
 521       b->_name = "intrinsic";
 522       b->attribute ("expected", token._token);
 523       b->attribute ("value", word);
 524       parseTree->addBranch (b);
 525
 526       if (_debug > 1)
 527         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << word << "\n";
 528       if (_debug)
 529         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 530       return true;
 531     }
 532   }
 533
 534   // <token> consecutive non-<ws>.
 535   else if (token._token == "<token>")
 536   {
 537     while (auto character = pig.peek ())
 538     {
 539       if (! character ||
 540           unicodeWhitespace (character))
 541         break;
 542
 543       pig.skip (character);
 544     }
 545
 546     if (pig.cursor () > checkpoint)
 547     {
 548       auto word = pig.substr (checkpoint, pig.cursor () - checkpoint);
 549
 550       // Create a populated branch.
 551       auto b = std::make_shared <Tree> ();
 552       b->_name = "intrinsic";
 553       b->attribute ("expected", token._token);
 554       b->attribute ("value", word);
 555       parseTree->addBranch (b);
 556
 557       if (_debug > 1)
 558         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << word << "\n";
 559       if (_debug)
 560         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 561       return true;
 562     }
 563   }
 564
 565   // <entity:category>.
 566   else if (token._token.find ("<entity:") == 0)
 567   {
 568     // Extract entity category
 569     auto category = token._token.substr (8, token._token.length () - 9);
 570
 571     // Match against any one of the entity values in this category.
 572     auto values = _entities.equal_range (category);
 573     for (auto value = values.first; value != values.second; ++value)
 574     {
 575       if (pig.skipLiteral (value->second))
 576       {
 577         // Create a populated branch.
 578         auto b = std::make_shared <Tree> ();
 579         b->_name = "intrinsic";
 580         b->tag ("entity");
 581         b->attribute ("expected", token._token);
 582         b->attribute ("value", value->second);
 583         parseTree->addBranch (b);
 584
 585         if (_debug > 1)
 586           std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << value->second << "\n";
 587         if (_debug)
 588           std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 589
 590         return true;
 591       }
 592     }
 593   }
 594
 595   // <external:rule>
 596   else if (token._token.find ("<external:") == 0)
 597   {
 598     // Extract entity category
 599     auto rule = token._token.substr (10, token._token.length () - 11);
 600
 601     // Any rule can be overridden by an external parser.
 602     if (_externals.find (rule) != _externals.end ())
 603     {
 604       // Create a pre-populated branch, which is attached on success only.
 605       auto newBranch = std::make_shared <Tree> ();
 606       newBranch->_name = "intrinsic";
 607       newBranch->tag ("external");
 608       newBranch->attribute ("expected", token._token);
 609
 610       if (_externals[rule] (pig, newBranch))
 611       {
 612         // Determine what was parsed.
 613         auto word = pig.substr (checkpoint, pig.cursor () - checkpoint);
 614
 615         // Attach the new branch.
 616         newBranch->attribute ("value", word);
 617         parseTree->addBranch (newBranch);
 618
 619         if (_debug > 1)
 620           std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << word << "\n";
 621         if (_debug)
 622           std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 623
 624         return true;
 625       }
 626
 627       // Note: Branch 'newBranch' goes out of scope here if parsing fails.
 628     }
 629   }
 630
 631   if (_debug > 1)
 632      std::cout << "trace " << std::string (indent, ' ') << "\e[31mfail\e[0m " << token._token << "\n";
 633   pig.restoreTo (checkpoint);
 634   return false;
 635 }
 636
 637 ////////////////////////////////////////////////////////////////////////////////
 638 bool Packrat::matchCharLiteral (
 639   const PEG::Token& token,
 640   Pig& pig,
 641   std::shared_ptr <Tree> parseTree,
 642   int indent)
 643 {
 644   if (_debug > 1)
 645     std::cout << "trace " << std::string (indent, ' ') << "matchCharLiteral " << token.dump () << "\n";
 646   auto checkpoint = pig.cursor ();
 647
 648   if (token._token.length () >= 3 &&
 649       token._token[0] == '\'' &&
 650       token._token[2] == '\'')
 651   {
 652     int literal = token._token[1];
 653     if (pig.skip (literal))
 654     {
 655       // Create a populated branch.
 656       auto b = std::make_shared <Tree> ();
 657       b->_name = "charLiteral";
 658       b->attribute ("expected", token._token);
 659       b->attribute ("value", utf8_character (literal));
 660       parseTree->addBranch (b);
 661
 662       if (_debug > 1)
 663         std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << token._token << "\n";
 664       if (_debug)
 665         std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 666       return true;
 667     }
 668   }
 669
 670   if (_debug > 1)
 671     std::cout << "trace " << std::string (indent, ' ') << "\e[31mfail\e[0m " << token._token << "\n";
 672   pig.restoreTo (checkpoint);
 673   return false;
 674 }
 675
 676 ////////////////////////////////////////////////////////////////////////////////
 677 bool Packrat::matchStringLiteral (
 678   const PEG::Token& token,
 679   Pig& pig,
 680   std::shared_ptr <Tree> parseTree,
 681   int indent)
 682 {
 683   if (_debug > 1)
 684     std::cout << "trace " << std::string (indent, ' ') << "matchStringLiteral " << token.dump () << "\n";
 685   auto checkpoint = pig.cursor ();
 686
 687   std::string literal = token._token.substr (1, token._token.length () - 2);
 688   if (pig.skipLiteral (literal))
 689   {
 690     // Create a populated branch.
 691     auto b = std::make_shared <Tree> ();
 692     b->_name = "stringLiteral";
 693     b->attribute ("expected", token._token);
 694     b->attribute ("value", literal);
 695     parseTree->addBranch (b);
 696
 697     if (_debug > 1)
 698       std::cout << "trace " << std::string (indent, ' ') << "\e[32mmatch\e[0m " << literal << "\n";
 699     if (_debug)
 700       std::cout << "trace " << pig.dump () << ' ' << token.dump () << "\n";
 701     return true;
 702   }
 703
 704   if (_debug > 1)
 705     std::cout << "trace " << std::string (indent, ' ') << "\e[31mfail\e[0m " << token._token << "\n";
 706   pig.restoreTo (checkpoint);
 707   return false;
 708 }
 709
 710 ////////////////////////////////////////////////////////////////////////////////
 711 // Search for 'value' in _entities category, return canonicalized value.
 712 bool Packrat::canonicalize (
 713   std::string& canonicalized,
 714   const std::string& category,
 715   const std::string& value) const
 716 {
 717   // Extract a list of entities for category.
 718   std::vector <std::string> options;
 719   auto c = _entities.equal_range (category);
 720   for (auto e = c.first; e != c.second; ++e)
 721   {
 722     // Shortcut: if an exact match is found, success.
 723     if (value == e->second)
 724     {
 725       canonicalized = value;
 726       return true;
 727     }
 728
 729     options.push_back (e->second);
 730   }
 731
 732   // Match against the options, throw away results.
 733   std::vector <std::string> matches;
 734   if (autoComplete (value, options, matches, minimumMatchLength) == 1)
 735   {
 736     canonicalized = matches[0];
 737     return true;
 738   }
 739
 740   return false;
 741 }
 742
 743 ////////////////////////////////////////////////////////////////////////////////
 744 std::string Packrat::dump () const
 745 {
 746   std::stringstream out;
 747   if (_debug)
 748     out << '\n';
 749
 750   out << "Packrat Parse "
 751       << _tree->dump ();
 752
 753   if (_entities.size ())
 754   {
 755     out << "  Entities\n";
 756     for (const auto& entity : _entities)
 757       out << "    " << entity.first << ':' << entity.second << '\n';
 758   }
 759
 760   if (_externals.size ())
 761   {
 762     out << "  Externals\n";
 763     for (const auto& external : _externals)
 764       out << "    " << external.first << "\n";
 765   }
 766
 767   return out.str ();
 768 }
 769
 770 ////////////////////////////////////////////////////////////////////////////////