static boolean snlToTree_debug = false;

static Lisp snlToTree(S snl) {
  ret snlToTree(snlParse(snl));
}

static Lisp snlToTree(Explain e) {
  class T {
    L<Explain> scanJuxta(Explain e) {
      boolean isJuxta = isA(e, "juxta");
      if (snlToTree_debug)
        print("scanJuxta " + e.string() + " " + isJuxta);
      if (isJuxta) {
        Explain juxta = descend(e, "juxta");
        Explain a = juxta.sub(0), b = juxta.sub(1);
        ret concatLists(scanJuxta(a), scanJuxta(b));
      } else
        ret litlist(e);
    }
    
    boolean isSame(Explain a, Explain b) {
      ret a.fromToken() == b.fromToken() && a.toToken() == b.toToken();
    }
    
    L<S> getClasses(Explain e) {
      new L<S> l;
      while (e != null) {
        l.add(e.className());
        if (l(e.subs) == 1 && e.sub(0) != null && isSame(e, e.sub(0)))
          e = e.sub(0);
        else
          break;
      }
      ret l;
    }
    
    Explain castTo(Explain e, S className) {
      ret descend(e, className);
    }
    
    Explain descend(Explain e, S className) {
      new L<S> l;
      while (e != null) {
        if (eq(e.className(), className))
          ret e;
        if (l(e.subs) == 1)
          e = e.sub(0);
        else
          break;
      }
      ret null;
    }
    
    boolean isA(Explain e, S className) {
      ret getClasses(e).contains(className);
    }
    
    boolean allAre(L<Explain> l, S className) {
      for (Explain e: l)
        if (!isA(e, className))
          ret false;
      ret true;
    }
    
    boolean anyAre(L<Explain> l, S className) {
      for (Explain e : l)
        if (isA(e, className))
          ret true;
      ret false;
    }
    
    L<S> getOperators(L<Explain> parts) {
      new L<S> l;
      for (Explain e : parts)
        l.add(makeOperator(e));
      ret l;
    }
    
    // true = it's a sub part
    boolean[] opMap(L<Explain> parts) {
      boolean[] map = new boolean[l(parts)];
      if (anyAre(parts, "symbol")) {
        for (int i = 0; i < l(parts); i++)
          if (!isA(parts.get(i), "symbol"))
            map[i] = true;
      } else
        for (int i = 0; i < l(parts); i++)
          //if (!isA(parts.get(i), "extidentifier"))
          if (!startsWithLetter(parts.get(i).string()))
            map[i] = true;
      ret map;
    }
    
    S makeOperatorFromJuxta(L<Explain> parts) {
      new L<S> l;
      boolean[] map = opMap(parts);
      for (int i = 0; i < l(parts); i++) {
        //print("Operator part " + (++i) + ": " + e.string() + " / " + structure(getClasses(e)));
        
        if (map[i])
          l.add("*");
        else
          l.add(parts.get(i).string());
      }
      S op = join(" ", l);
      if (snlToTree_debug)
        print("makeOperatorFromJuxta " + structure(parts) + " => " + op);
      ret op;
    }
    
    L<Explain> getJuxtaArgs(L<Explain> parts) {
      new L<Explain> l;
      boolean[] map = opMap(parts);
      for (int i = 0; i < l(parts); i++)
        if (map[i])
          l.add(parts.get(i));
      ret l;
    }
    
    S makeOperator(Explain e) {
      if (isA(e, "realarrow"))
        ret descend(e, "realarrow").sub(0).string() + " *";
      else if (isA(e, "juxta")) {
        L<Explain> j = scanJuxta(e);
        //print("scanJuxta => " + structure(j));
        ret makeOperatorFromJuxta(j);
      } else
        ret e.string();
    }
    
    Lisp getTree(Explain e) {
      //print("getTree " + structure(getClasses(e)));
      
      if (isA(e, "realarrow")) {
        //print("realarrow");
        Explain a = castTo(e, "realarrow");
        ret snlToTree_lisp(e, "<", getTree(a.sub(0)), getTree(a.sub(1)));
      }
      
      if (isA(e, "realarrowr")) {
        //print("realarrowr");
        Explain a = castTo(e, "realarrowr");
        ret snlToTree_lisp(e, ">", getTree(a.sub(0)), getTree(a.sub(1)));
      }
      
      if (isA(e, "square")) {
        //print("square");
        Explain a = castTo(e, "square");
        ret snlToTree_lisp(e, "[]", getTree(a.sub(0)));
      }
      
      if (isA(e, "round")) {
        Explain a = castTo(e, "round");
        ret snlToTree_lisp(e, "()", getTree(a.sub(0)));
      }
      
      if (isA(e, "juxta")) {
        Explain juxta = descend(e, "juxta");
        L<Explain> parts = scanJuxta(juxta);
        
        if (snlToTree_debug) {
          print("juxta " + e.string());
          for (int i = 0; i < l(parts); i++)
            print("  part " + parts.get(i).string() + " " + structure(getClasses(parts.get(i))));
        }
        
        if (l(parts) == 2 && eq(parts.get(0).string(), "="))
          ret snlToTree_lisp(e, "= *", removeBrackets(getTree(parts.get(1))));
        else /*if (anyAre(parts, "subword") || anyAre(parts, "ucid")) */ {
          if (snlToTree_debug)
            print("subwords!");
            
          L<Explain> args = getJuxtaArgs(parts);
          Lisp l = snlToTree_lisp(e, makeOperatorFromJuxta(parts));
          for (Explain arg : args)
            l.add(removeBrackets(getTree(arg)));
          ret l; // snlSimplifyJuxta(l);
        }
    
        // fall back to simple string
      }
      
      ret snlToTree_lisp(e, e.string());
    }

    Lisp removeBrackets(Lisp l) {
      while (l != null && eq(l.head, "[]") && l.size() == 1)
        l = l.get(0);
      ret l;
    }
  }
  
  if (e == null) ret null;
  ret simplifySNLTree(new T().getTree(e));
}

static Lisp snlToTree_lisp(Explain e, S head, Lisp... args) {
  Lisp l = lisp(head, args);
  
  // this is problematic with serialization...
  //new SNLInfo info;
  //info.originalExplain = e;
  //l.more = info;
  
  ret l;
}