// 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 caseSensitive = false;

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"; // NL

static S javaRules = "#1002329";

static boolean keepRules = false;

static class ParseResult {

  L<S> tok;

  Map<Integer, MultiMap<S, Integer>> recog;

  L<S> fullMatchClasses() {

    new L<S> l;

    MultiMap<S, Integer> rr = recog.get(1);

    for (S className : rr.keys())

      if (rr.get(className).contains(l(tok)))

        l.add(className);

    ret l;

  }

  L explainLongestMatch() {

    S c = findLongestMatch(1);

    if (c == null) ret null;

    int n = max(recog.get(1).get(c));

    if (n == 1) ret null;

    L l = cast explainMatch(new Pos(tok), n, c).get(0);

    ret shortenExplanation(l);

  }

  S findLongestMatch(int i) {

    MultiMap<S, Integer> rr = recog.get(i);

    new Map<S, Integer> map;

    for (S c : rr.keys())

      map.put(c, max(rr.get(c)));

    ret keyWithBiggestValue(map);

  }

  L explain(S className) {

    ret explain(1, l(tok), className);

  }

  L explainFull(S className) {

    ret explainFull(1, l(tok), className);

  }

  // full = not shortened (include all subclassings)

  L explainFull(int fromToken, int toToken, S className) {

    L<L> matches = explainMatch(new Pos(tok, fromToken), toToken, className);

    ret get(matches, 0);

  }

  L explain(int fromToken, int toToken, S className) {

    L l = explainFull(fromToken, toToken, className);

    if (debug)

      print("Full explanation: " + structure(l));

    ret shortenExplanation(l);

  }

  // Example: [[1, 11, "exp", "<exp1>", [1, 11, "exp1", 11, "exp1", "<exp1> + <exp2>", ...]]]

  L shortenExplanation(L m) {

    if (m == null) ret null;

    if (l(m) == 5) {

      int ii = (Integer) m.get(0), jj = (Integer) m.get(1);

      L sub = (L) m.get(4);

      int II = (Integer) sub.get(0), JJ = (Integer) sub.get(1);

      if (ii == II && jj == JJ)

        ret shortenExplanation(sub); // it's a subclassing  - just drop the outer match

    }

    for (int i = 4; i < l(m); i++)

      m.set(i, shortenExplanation((L) m.get(i)));

    ret m;

  }

  // assumes that there is a match (pos, class, endPos)

  // and gives explanations of how it was probably matched.

  // result list format: [className, prodText, [i1, i2], [i3, i4], ...]

  L explainMatch(Pos pos, int endPos, S forClass) {

    L<L<S>> prods = productionMap.get(forClass);

    new L out;

    for (L<S> prod : prods) {

      L match = litlist(pos.i, endPos, forClass, join(prod));

      if (debug)

        print("Starting match: " + structure(match));

      explainMatch2(pos, new Pos(prod), endPos, forClass, match, out);

    }

    ret out;

  }

  // same, but with fixed production

  void explainMatch2(Pos pos, Pos prod, int endPos, S forClass, L match, L out) {

    if (prod.end()) {

      if (pos.i == endPos) {

        // match done! add sub-explanations.

        match = cloneList(match);

        if (debug)

          print("Match done! " + structure(match));

        for (int i = 4; i < l(match); i++) {

          L m = cloneList((L) match.get(i));

          //print("m=" + structure(m));

          int ii = (Integer) m.get(0), jj = (Integer) m.get(1);

          S className = cast m.get(2);

          L subExplanation = explainMatch(new Pos(pos.tok, ii), jj, className);

          //print(format("Recursed: * * * => ", ii, jj, className) +  structure(subExplanation));

          if (empty(subExplanation)) {

            // weird

          } else

            m.addAll(subList((L) subExplanation.get(0), 3));

          match.set(i, m);

        }

        if (debug)

          print("Match completed: " + structure(match));

        out.add(match);

      }

    } else if (pos.end())

      ret;

    else {

      S p = prod.get();

      if (isBracketedID(p)) {

        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, className));

          explainMatch2(new Pos(pos.tok, i), prod.plus(2), endPos, forClass, match, out);

          removeLast(match);

        }

      } else if (!pos.end()) {

        // it's a literal

        S t = pos.get();

        if (!matchToken(p, t))

          ret;

        //match.add(litlist(pos.i, pos.i+2, p));

        explainMatch2(pos.plus(2), prod.plus(2), endPos, forClass, match, out);

        //removeLast(match);

      }

    }

  }

  S prettierAnalysis() {

    new L<S> l;

    new TreeSet<S> emptyClasses;

    for (int i = 1; i < l(tok); i += 2) {

      MultiMap<S, Integer> rr = recog.get(i);

      new L<S> bla;

      for (S className : rr.keys()) {

        L<Integer> is = rr.get(className);

        if (is.contains(i))

          emptyClasses.add(className);

        int n = (max(is)-i)/2;

        if (n > 0)

          bla.add(className + " " + n);

      }

      l.add(tok.get(i) + " : " + structure(bla));

    }

    if (!empty(emptyClasses))

      l.add("  with empty classes " + structure(asList(emptyClasses)));

    ret fromLines(l);

  }

}

p {

  startBot("Snippet Text Bot", "#1002084");

}

static ParseResult parse(S inputText) {

  ret parse(inputText, defaultParserRules);

}

static ParseResult jparse(S inputText) {

  ret parse(inputText, javaRules);

}

static S keptRulesID;

static S keptRulesText;

static synchronized ParseResult parse(S inputText, S parserRules) {

  S rulesText;

  if (!isSnippetID(parserRules))

    rulesText = parserRules;

  else {

    if (keepRules && sameSnippetID(parserRules, keptRulesID))

      rulesText = keptRulesText;

    else {

      rulesText = loadSnippetThroughBot(parserRules);

      if (keepRules) {

        keptRulesID = parserRules;

        keptRulesText = rulesText;

      }

    }

  }

  productionMap = new MultiMap;

  caseSensitive = false;

  for (S rule : toLinesFullTrim(rulesText)) pcall {

    if (l(javaTok(rule)) == 1) continue; // just a comment

    if (debug)

      printF("Processing rule: *", rule);

    if (rule.contains("=")) {  

      L<S> lr = splitAtJavaToken(rule, "=");

      S l, r;

      if (l(lr) == 1) {

        l = "";

        r = lr.get(0);

      } else if (l(lr) >= 2) {

        l = join(" = ", lr.subList(0, l(lr)-1));

        r = last(lr);

      } else {

        print("Weird rule: " + rule);

        continue;

      }

      L<S> tokr = mergeBracketThingies(javaTok(r));

      assertEquals(structure(tokr), 3, l(tokr));

      S className = assertIdentifier(unbracket(get(tokr, 1)));

      L<S> tok = javaTok(l);

      tok = mergeBracketThingies(tok);

      //printStructure(tok);

      productionMap.put(className, tok);

    } else if (match("case-sensitive", rule)) {

      //print("Now case sensitive.");

      caseSensitive = true;

    } else if (match("case-insensitive", rule)) {

      caseSensitive = false;

    } else

      print("Weird rule: " + rule);

  }

  if (debug) {

    print(n(productionMap.size(), "production") + ".");

    print();

  }

  timing = now();

  tok = javaTok(inputText);

  Pos pos = new Pos(tok);

  parseTop(pos);

  timing = now()-timing;

  int numTok = l(tok)/2;

  print("Iterations required for " + numTok + " tokens: " + iterations*numTok*productionMap.size() + ", time: " + timing + " ms");

  new ParseResult res;

  res.tok = tok;

  res.recog = recog;

  ret res;

}

static void parseTop(Pos pos) {

  // init structures

  recog = new TreeMap;

  for (int i = pos.i; i <= l(pos.tok); i += 2) // contains one more element for empty classes at the end

    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);

    }

  }

  matchSpecials();

  boolean anyChange;

  iterations = 0;

  MultiMap<S, L<S>> fullProductionMap = new MultiMap(productionMap);

  while (iter(pos)) {}

  iter(pos); // XX - one more - fixes anything?

  productionMap = fullProductionMap; // restore ground productions

}

static boolean iter(Pos pos) {

  boolean anyChange = false;

  ++iterations;

  if (iterations == 2) removeGroundProductions();

  if (debug) print("Iteration " + iterations);

  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);

    }

  }

  ret anyChange;

}

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("<any>", "<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, "<any>") || (caseSensitive ? eq(p, t) : eqic(p, t))))

    ret false; // token mismatch

  ret true;

}

static S loadSnippetThroughBot(S snippetID) {

  print("Loading parser rules.");

  time {

    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);

  }

}

// 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))) {

        if (debug)

          print("Ground production: " + className + " = " + join(prods.get(i)));

        prods.remove(i);

      } else

        ++i;

    productionMap.clean(className);

  }

  n -= productionMap.size();

  if (debug && 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(t))

      ret false;

  }

  ret true;

}

static void addDict(S className, Collection<S> entries) {

  dicts.put(className, entries instanceof Set ? (Set) entries : new TreeSet(entries));

}

static void matchSpecials() {

  for (int i = 1; i < l(tok); i += 2) {

    MultiMap<S, Integer> rr = recog.get(i);

    for (S s : specials)

      if (matchToken(s, tok.get(i)))

        rr.put(unbracket(s), i+2);

  }

}