// Idea: For every position, store the productions recognized to start there, then infer up to higher classes

!759

// a recognition is identified by (startPos, className, endPos)


// key 1 = start position, key 2 = class name, value = end position
static Map<Integer, MultiMap<S, Integer>> recog;
static L<S> tok;

static MultiMap<S, L<S>> productionMap;

static boolean debug = false;

static long timing;
static int iterations;

static Map<S, Set<S>> dicts = new TreeMap; // dictionaries - class name to lowercase examples


static S defaultParserRules = "#1002281";
static S defaultMainProd = "line";

p {
  startBot("Snippet Text Bot", "#1002084");
}

static synchronized S parse(S inputText) {
  ret parse(inputText, defaultParserRules, defaultMainProd);
}

static synchronized S parse(S inputText, S parserRules, S mainProd) {
  S rulesText = loadSnippetThroughBot(parserRules);

  productionMap = new MultiMap;
  for (S rule : toLinesFullTrim(rulesText)) pcall {
    //printF("Processing rule: *", rule);
    L<S> lr = splitAtJavaToken(rule, "=");
    S l, r;
    if (l(lr) == 1) {
      l = "";
      r = lr.get(0);
    } else if (l(lr) == 2) {
      l = lr.get(0);
      r = lr.get(1);
    } else {
      print("Weird rule: " + rule);
      continue;
    }
    L<S> tokr = javaTok(r);
    assertEquals(structure(tokr), 3, l(tokr));
    S className = assertIdentifier(get(tokr, 1));
    L<S> tok = javaTok(l);
    tok = mergeBracketThingies(tok);
    //printStructure(tok);
    productionMap.put(className, tok);
  }
  
  print(n(productionMap.size(), "production") + ".");
  print();
  
  timing = now();
  tok = javaTok(inputText);
  Pos pos = new Pos(tok);
  L<Integer> x = parseTop(pos, mainProd);
  S result;
  timing = now()-timing;
  
  int numTok = l(tok)/2;
  print("Iterations required for " + numTok + " tokens: " + iterations*numTok + ", time: " + timing + " ms");
  
  if (x.contains(l(tok)))
    result = "parsed";
  else if (!empty(x))
    result = "beginning matches";
  else
    ret "not parsed";
  L out = explainMatch(new Pos(tok), x.get(0), mainProd);
  ret result + ", detailed analysis: " + structure(out);
}

static L<Integer> parseTop(Pos pos, S mainProd) {
  // init structures
  recog = new TreeMap;
  for (int i = pos.i; i < l(pos.tok); i += 2)
    recog.put(i, new MultiMap);
  print("parser: recog inited " + pos.i + " to " + l(pos.tok));
  
  // process dicts
  for (S className : dicts.keySet()) {
    Set<S> values = dicts.get(className);
    for (int i = pos.i; i < l(pos.tok); i += 2) {
      S t = pos.tok.get(i);
      if (values.contains(t.toLowerCase()))
        recog.get(i).setPut(className, i+2);
    }
  }

  boolean anyChange;
  iterations = 0;
  MultiMap<S, L<S>> fullProductionMap = new MultiMap(productionMap);
  do {
    anyChange = false;
    ++iterations;
    if (iterations == 2) removeGroundProductions();
    for (int i = pos.i; i < l(pos.tok); i += 2) {
      Pos pos2 = new Pos(pos.tok, i);
      for (S className : productionMap.keySet()) {
        MultiMap<S, Integer> rr = recog.get(i);
        L<Integer> recs = rr.getActual(className);
        L<L<S>> prods = productionMap.get(className);
        for (L<S> prod : prods) {
          int n = l(recs);
          matchProd(pos2, new Pos(prod), className, recs);
          anyChange = anyChange || l(recs) > n;
        }
        rr.clean(className);
      }
    }
  } while (anyChange);
  productionMap = fullProductionMap; // restore ground productions
  
  ret recog.get(pos.i).get(mainProd);
}

static class Pos {
  L<S> tok;
  int i = 1;
  
  *() {}
  *(L<S> *tok) {}
  *(L<S> *tok, int *i) {}
  
  boolean end() { ret i >= l(tok)-1; }
  S get() { ret tok.get(i); }
  public Pos clone() { ret new Pos(tok, i); }
  public boolean equals(O o) {
    if (!(o instanceof Pos)) ret false;
    Pos pos = cast o;
    ret tok == pos.tok && i == pos.i;
  }
  
  S rest() {
    ret join(subList(tok, i));
  }

  Pos plus(int x) { ret new Pos(tok, i + x); }
}

static void copy(Pos a, Pos b) {
  b.tok = a.tok;
  b.i = a.i;
}

static void debug(S bla, Pos pos) {
  if (debug)
    print(bla + " on " + quote(pos.rest()));
}

static void matchProd(Pos pos, Pos prod, S forClass, L<Integer> out) {
  if (prod.end())
    setAdd(out, pos.i);
  else if (pos.end())
    ret;
  else {
    S p = prod.get();
    
    if (isBracketedID(p) && !specials.contains(p)) {
      MultiMap<S, Integer> rr = recog.get(pos.i);
      if (rr == null)
        fail("parser: recog null at " + pos.i);
      L<Integer> r = rr.get(unbracket(p));
      
      // keep parsing for every option
  
      for (int i : cloneList(r))
        matchProd(new Pos(pos.tok, i), prod.plus(2), forClass, out);
      
    } else {
      // it's a literal
      S t = pos.get();
      if (!matchToken(p, t))
        ret;
      
      matchProd(pos.plus(2), prod.plus(2), forClass, out);
    }
  }
}

static L<S> specials = litlist("<quoted>", "<int>", "<identifier>");

static boolean matchToken(S p, S t) {
  if (eq(p, "<quoted>")) {
    if (!isQuoted(t)) ret false;
  } else if (eq(p, "<int>")) {
    if (!isInteger(t)) ret false;
  } else if (eq(p, "<identifier>")) {
    if (!isIdentifier(t)) ret false;
  } else if (!(eq(p, "*") || eqic(p, t)))
    ret false; // token mismatch
  ret true;
}

// assumes that there is a match (pos, class, endPos)
// and gives explanations of how it was probably matched
static L explainMatch(Pos pos, int endPos, S forClass) {
  L<L<S>> prods = productionMap.get(forClass);
  new L out;
  for (L<S> prod : prods)
    explainMatch2(pos, new Pos(prod), endPos, forClass, litlist(forClass, join(prod)), out);
  ret out;
}

// same, but with fixed production
static void explainMatch2(Pos pos, Pos prod, int endPos, S forClass, L match, L out) {
  if (prod.end()) {
    if (pos.i == endPos)
      out.add(cloneList(match));
  } else if (pos.end())
    ret;
  else {
    S p = prod.get();
    
    if (isBracketedID(p) && neq(p, "<quoted>")) {
      S className = unbracket(p);
      L<Integer> r = recog.get(pos.i).get(className);

      // keep parsing for every option
  
      for (int i : cloneList(r)) {
        match.add(litlist(pos.i, i));
        explainMatch2(new Pos(pos.tok, i), prod.plus(2), endPos, forClass, match, out);
        removeLast(match);
      }
    } else {
      // it's a literal
      S t = pos.get();
      if (!matchToken(p, t))
        ret;
      
      //match.add(litlist(pos.i, p, pos.i+2));
      explainMatch2(pos.plus(2), prod.plus(2), endPos, forClass, match, out);
      removeLast(match);
    }
  }
}

static S loadSnippetThroughBot(S snippetID) {
  S answer = sendToLocalBot_cached("Snippet Text Bot", "what is the text of snippet *", snippetID);
  new Matches m;
  assertTrue(match("the text of snippet * is *", answer, m));
  ret m.unq(1);
}

static S prettierAnalysis() {
  new L<S> l;
  for (int i = 1; i < l(tok); i += 2) {
    MultiMap<S, Integer> rr = recog.get(i);
    new L<S> bla;
    for (S prod : rr.keys()) {
      L<Integer> is = rr.get(prod);
      bla.add(prod + " " + (max(is)-i)/2);
    }
    l.add(tok.get(i) + " : " + structure(bla));
  } ret fromLines(l);
}

// Non-recursing productions don't need to be repeatedly executed
static void removeGroundProductions() {
  int n = productionMap.size();
  for (S className : new HashSet<S>(productionMap.keySet())) {
    L<L<S>> prods = productionMap.getActual(className);
    for (int i = 0; i < l(prods); )
      if (isGroundProduction(prods.get(i))) {
        //print("Ground production: " + className + " = " + join(prods.get(i)));
        prods.remove(i);
      } else
        ++i;
    productionMap.clean(className);
  }
  n -= productionMap.size();
  if (n != 0)
    print(n + " ground productions removed.");
}

static boolean isGroundProduction(L<S> prod) {
  for (int i = 1; i < l(prod); i += 2) {
    S t = prod.get(i);
    if (isBracketedID(t) && !specials.contains(unbracket(t)))
      ret false;
  }
  ret true;
}

static void addDict(S className, Collection<S> entries) {
  dicts.put(className, entries instanceof Set ? (Set) entries : new TreeSet(entries));
}

Began life as a copy of #1002307