Fix alternatives handling

3 files changed, 24 insertions, 28 deletions

diff --git a/TODO b/TODO
index a1d7b33..58b4f2b 100644
--- a/TODO
+++ b/TODO
@@ -4,3 +4,6 @@
 
 start symbol implicitly from bnf
 validate bnf: no empty types or values, or empty target lists
+
+map -> unordered_map
+set -> unordered_set
diff --git a/grammer.cpp b/grammer.cpp
index 8f38e3e..07e527f 100644
--- a/grammer.cpp
+++ b/grammer.cpp
@@ -105,13 +105,10 @@ bool Compiler::subTreeIsComplete(index_t node_id, index_t& to_fill)
  return true;
 }
 
-bool Compiler::StartsWith(const std::vector<Token>& tokens, const std::vector<std::string>& types)
+size_t Compiler::CommonPrefix(const std::vector<Token>& tokens, const std::vector<std::string>& types)
 {
- if (tokens.size() < types.size())
-  return false;
-
  auto [tokens_it, types_it] = std::mismatch(tokens.begin(), tokens.end(), types.begin(), types.end(), [](const Token& token, const std::string& s){ return token.type == s; });
- return types_it == types.end(); // no mismatch: tokens (types) start wit specified types list
+ return types_it - types.begin(); // a distance, 0 on no match
 }
 
 void Compiler::AddFirstNode()
@@ -127,21 +124,22 @@ void Compiler::AddFirstNode()
 
  std::string node_type;
  index_t node_variant;
- std::deque<std::string> alternatives; // only for valid elements from alternatives_set
+ std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set
  std::vector<index_t> child_ids;
 
  for (const auto& type : alternatives_set) {
   const auto& variants{bnf[type]};
   for (int i = 0; i < variants.size(); i++) {
    const std::vector<std::string> & variant{variants[i]};
-   if (StartsWith(tokens, variant)) { // match
-    if (node_type == "") {
+   size_t common{};
+   if ((common = CommonPrefix(tokens, variant)) > 0) { // match a common prefix
+    if (node_type == "") { // no match yet
      node_type = type;
      node_variant = i;
-     for (int token_id = 0; token_id < variant.size())
+     for (int token_id = 0; token_id < common; token_id++)
       child_ids.push_back(ChildIdFromTokenId(token_id));
     } else
-     alternatives.push_back(type); // duplicates possible: variants of same type!
+     alternatives.emplace_back(type, i);
    }
   }
  }
@@ -172,7 +170,7 @@ bool Compiler::AddRootNode()
 
   std::string node_type;
   index_t node_variant;
-  std::deque<std::string> alternatives; // only for valid elements from alternatives_set
+  std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set
   std::vector<index_t> child_ids{1, old_root_node_id};
 
   for (const auto& type : alternatives_set) {
@@ -184,12 +182,12 @@ bool Compiler::AddRootNode()
       node_type = type;
       node_variant = i;
      } else
-      alternatives.push_back(type); // duplicates possible: variants of same type
+      alternatives.emplace_back(type, i); // duplicates possible: variants of same type
     }
    }
   }
 
-  if (node_type == "") // no matching type found
+  if (node_type == "") // no matching type found (maybe backtrack possible?)
    return false;
 
   // now add! 
@@ -232,28 +230,22 @@ void ChangeNodeType()
  TreeNode& node {nodes.back()};
  index_t node_id = node.node_id;
 
- if (node.alternative_types.empty())
+ if (node.alternatives.empty())
   throw std::runtime_error("No alternatives found during Backtrack"); // ICE
 
- if (node.alternative_types.front() == node.type) { // Keep type, change variant
-  if (root_node_id == node_id) { // Root node
-   // TODO ...
-  } else if (node.child_ids().empty()) { // leaf node
-  } else
-   throw std::runtime_error("Backtrack: Can't set alternative in the middle of the tree.");
- } else { // Different type
-  if (root_node_id == node_id) { // Root node
-  } else if (node.child_ids().empty()) { // leaf node
-  } else
-   throw std::runtime_error("Backtrack: Can't set alternative in the middle of the tree.");
- }
+ auto& [type, variant] {node.alternatives.front()};
+
+ node.type = type;
+ node.variant = variant;
+
+ node.alternatives.pop_front();
 }
 
 // throws if no further track back is possible: compile error
 void Compiler::TrackBack()
 {
  // Search backwards for alternatives: last node with alternatives (variant or alt. token)
- while (!nodes.empty() && nodes.last().alternative_types.empty()) {
+ while (!nodes.empty() && nodes.last().alternatives.empty()) {
   RemoveLastNode();
  }
 
diff --git a/grammer.h b/grammer.h
index 18719cd..996d023 100644
--- a/grammer.h
+++ b/grammer.h
@@ -4,6 +4,7 @@
 #include "minicc.h"
 
 #include <cstdint>
+#include <utility>
 
 namespace Gram {
 
@@ -16,7 +17,7 @@ struct TreeNode {
 
  std::string type;
  index_t variant; // bnf[type][variant]
- std::deque<std::string> alternative_types; // alternatives that we can consider if type fails. Discard after parsing!
+ std::deque<std::pair<std::string, index_t>> alternatives; // [type][value] alternatives that we can consider on fail. Discard after parsing!
  std::vector<int32_t> child_ids; // < 0: terminal: token_id; >= 0: non-terminal: node_id; fill token by token
 };