sclass DialogOptimizer {
  OccTree2 tree, botTree;
  bool walkTree_debug;
  bool useAdapter = true;
  O engine;

  *(S theme, S engineID) {
    engine = run(engineID);
    L<Dialog> dialogs = loadDialogs(theme);
    callOpt(mc(), "expandDialogs", dialogs); // hmm.
    expandEllipsis(tree = makeOccTree(dialogs));
    expandEllipsis(botTree = makeOccTree(withoutSecretDialogs(dialogs)));
    printOccTree2(botTree);
    print("Tree size: " + tree.size() + ", bot tree size: " + botTree.size());
    //walkTree_debug = true;
    try {
      walkTree();
    } catch e {
      print("Engine not working, abort.");
      printStackTrace(e);
      ret;
    }
    print("Tree walked! " + inputFed + " -> " + outputGot);
    
    int origSize = botTree.size()-1;
    print("Engine works! Trying to shrink the tree.");
    
    while (canShrinkTree()) {
      print("Tree shrunk, trying it again.");
    }
    
    int newSize = botTree.size()-1;
    printOccTree2(botTree);
    if (newSize < origSize) {
      long percent = newSize == 0 ? 9999 : round(origSize*100.0/newSize-100);
      print("Done shrinking tree (" + origSize + " -> " + newSize + " entries - " + percent + "% shrinkage!)");
    } else
      print("Tree unshrinkable.");
  }
  
  int inputFed, outputGot;
  
  bool canShrinkTree() {
    L<OccTree2> leaves = botTree.allLeaves();
    print("Leaves found: " + l(leaves));
    
    bool anyChange = false;
    for (OccTree2 leaf : leaves) {
      print("Trying to remove leaf: " + leaf.e + " (level " + leaf.level() + ")");
      Reattach reattach = removeLeaf(leaf);
      //printOccTree2(botTree);
      if (canWalkTree()) {
        print("Leaf removed successfully!");
        anyChange = true;
      } else
        reattach.reattach();
    }
    
    ret anyChange;
  }
  
  class Reattach {
    OccTree2 node, leaf;
    int idx;
  
    void reattach() {
      leaf.parent = node;
      node.next.add(idx, leaf);
    }
  }
  
  Reattach removeLeaf(OccTree2 leaf) {
    new Reattach r;
    r.leaf = leaf;
    r.node = leaf.parent;
    r.idx = leaf.parent.next.indexOf(leaf);
    leaf.parent.next.remove(r.idx);
    leaf.parent = null;
    ret r;
  }
  
  bool canWalkTree() {
    ret canWalkTree(tree, makeBot());
  }
  
  bool canWalkTree(OccTree2 tree, O bot) {
    try { walkTree(tree, bot); true; } catch e {
      if (walkTree_debug)
        printStackTrace(e);
      ret false;
    }
  }
  
  void walkTree() {
    walkTree(tree, makeBot());
  }
  
  L<S> statesToIgnore = ll("good", "bad", "end");
  
  void walkTree(OccTree2 tree, O bot) {
    if (tree.isLeaf())
      assertNull(getOutput(bot));
    else
      for (E e : tree.followUpKeys()) {
        if (!contains(statesToIgnore, e.state)) {
          bool input = isInput(e);
          if (walkTree_debug)
            print((input ? "FEED " : "CHECK ") + structure(e));
          if (input) {
            assertNull(getOutput(bot));
            feed(bot, e);
          } else
            checkOutput(e, getOutput(bot), bot);
          walkTree(tree.followUp(e), bot);
          if (walkTree_debug)
            print("Rewind " + structure(e));
          rewind(bot);
        }
      }
  }
  
  void rewind(O bot) {
    call(bot, "rewind"); // rewind one step
  }
  
  void feed(O bot, E e) {
    call(bot, "take", quickExport(e, bot));
    ++inputFed;
  }
  
  E getOutput(O bot) {
    E e = cast quickImport(call(bot, "getSingleOutput"));
    if (e != null) ++outputGot;
    ret e;
  }
  
  void checkOutput(E e, E output, O bot) {
    //if (e.state() && matchStart("result is", e.text())) ret;
    //assertEquals(e, output);
    if (neq(e, output)) {
      print(asciiHeading("THOUGHTS"));
      print(callOpt(bot, "thoughts"));
      print();
      fail("Bot fail: Expected " + e + ", got: " + output);
    }
  }
  
  // should match isCommand() in LooseBot
  bool isInput(E e) {
    ret e.q()
      || e.state() && matchStart("result is ", e.text());
  }

  O makeBot() {
    setOpt(engine, "botTree", quickExport(botTree, engine));
    ret callF(get(engine, "makeBot"));
  }
}