// TODO: cyclic structures involving certain lists & sets

sclass unstructure_X {
  // classFinder: func(name) -> class (optional)
  Producer<S> tok;
  bool allDynamic;
  bool debug;

  asclass Receiver {
    abstract void set(O o);
  }

  *(S text) {
    this(text, false);
  }

  *(S text, bool allDynamic) {
    this(text, allDynamic, null);
  }

  *(S text, IF1<S, Class> classFinder) {
    this(text, false, classFinder);
  }

  *(String text, bool allDynamic, O classFinder) {
    this(javaTokC_noMLS_iterator(text), allDynamic, classFinder);
  }

  *(BufferedReader reader) {
    this(javaTokC_noMLS_onReader(reader), false, null);
  }

  *(Producer<S> *tok, bool *allDynamic, O _classFinder) {
    classFinder = _classFinder != null ? _classFinder : _defaultClassFinder();
    pcall {
      Class mc = cast callF(classFinder, "<main>");
      if (mc != null) mcDollar = mc.getName() + "$";
    }
  }
  
  int i = -1;
  final O classFinder;
  S mcDollar = actualMCDollar();

  // use Eclipse primitive collection if possible (smaller & hopefully faster?)
  ifdef UseEclipseCollections
  new IntObjectHashMap<O> refs;
  new IntObjectHashMap<O> tokrefs;
  endifdef
  ifndef UseEclipseCollections
  new HashMap<Integer, O> refs;
  new HashMap<Integer, O> tokrefs;
  endifndef
    
  new HashSet<S> concepts;
  new HashMap<S, Class> classesMap;
  new L<Runnable> stack;
  new SS baseClassMap;
  new HashMap<Class, Constructor> innerClassConstructors;
  S curT;
  
  int internStringsLongerThan = 50;
  int unquoteBufSize = 100;
  char[] unquoteBuf = new char[unstructure_unquoteBufSize];
  
  Class findAClass(S fullClassName) null on exception {
    ret classFinder != null ? (Class) callF(classFinder, fullClassName) : findClass_fullName(fullClassName);
  }
  
  S unquote(S s) {
    ret unquoteUsingCharArray(s, unquoteBuf); 
  }

  // look at current token
  S t() {
    ret curT;
  }
  
  // get current token, move to next
  S tpp() {
    S t = curT;
    consume();
    ret t;
  }
  
  void parse(Receiver out) {
    S t = t();
    
    int refID;
    if (structure_isMarker(t, 0, l(t))) {
      refID = parseInt(t.substring(1));
      consume();
    } else refID = -1;
    
    // if (debug) print("parse: " + quote(t));
    
    final int tokIndex = i;  
    parse_inner(refID, tokIndex, new Receiver {
      void set(O o) {
        if (refID >= 0)
          refs.put(refID, o);
        if (o != null)
          tokrefs.put(tokIndex, o);
        out.set(o);
      }
    });
  }
  
  void parse_inner(int refID, int tokIndex, Receiver out) {
    S t = t();
    
    // if (debug) print("parse_inner: " + quote(t));
    
    Class c = classesMap.get(t);
    if (c == null) {
      if (t.startsWith("\"")) {
        S s = internIfLongerThan(unquote(tpp()), structure_internStringsLongerThan);
        out.set(s); ret;
      }
      
      if (t.startsWith("'")) {
        out.set(unquoteCharacter(tpp())); ret;
      }
      if (t.equals("bigint")) {
        out.set(parseBigInt()); ret;
      }
      if (t.equals("d")) {
        out.set(parseDouble()); ret;
      }
      if (t.equals("fl")) {
        out.set(parseFloat()); ret;
      }
      if (t.equals("sh")) {
        consume();
        t = tpp();
        if (t.equals("-")) {
          t = tpp();
          out.set((short) (-parseInt(t)); ret;
        }
        out.set((short) parseInt(t)); ret;
      }
      if (t.equals("-")) {
        consume();
        t = tpp();
        out.set(isLongConstant(t) ? (O) (-parseLong(t)) : (O) (-parseInt(t))); ret;
      }
      if (isInteger(t) || isLongConstant(t)) {
        consume();
        //if (debug) print("isLongConstant " + quote(t) + " => " + isLongConstant(t));
        if (isLongConstant(t)) {
          out.set(parseLong(t)); ret;
        }
        long l = parseLong(t);
        bool isInt = l == (int) l;
        ifdef unstructure_debug
          print("l=" + l + ", isInt: " + isInt);
        endifdef
        out.set(isInt ? (O) Integer.valueOf((int) l) : (O) Long.valueOf(l)); ret;
      }
      if (t.equals("false") || t.equals("f")) {
        consume(); out.set(false); ret;
      }
      if (t.equals("true") || t.equals("t")) {
        consume(); out.set(true); ret;
      }
      if (t.equals("-")) {
        consume();
        t = tpp();
        out.set(isLongConstant(t) ? (O) (-parseLong(t)) : (O) (-parseInt(t))); ret;
      }
      if (isInteger(t) || isLongConstant(t)) {
        consume();
        //if (debug) print("isLongConstant " + quote(t) + " => " + isLongConstant(t));
        if (isLongConstant(t)) {
          out.set(parseLong(t)); ret;
        }
        long l = parseLong(t);
        bool isInt = l == (int) l;
        ifdef unstructure_debug
          print("l=" + l + ", isInt: " + isInt);
        endifdef
        out.set(isInt ? (O) Integer.valueOf((int) l) : (O) Long.valueOf(l)); ret;
      }
      
      if (t.equals("File")) {
        consume();
        File f = new File(unquote(tpp()));
        out.set(f); ret;
      }
      
      if (t.startsWith("r") && isInteger(t.substring(1))) {
        consume();
        int ref = Integer.parseInt(t.substring(1));
        O o = refs.get(ref);
        if (o == null)
          warn("unsatisfied back reference " + ref);
        out.set(o); ret;
      }
    
      if (t.startsWith("t") && isInteger(t.substring(1))) {
        consume();
        int ref = Integer.parseInt(t.substring(1));
        O o = tokrefs.get(ref);
        if (o == null)
          warn("unsatisfied token reference " + ref + " at " + tokIndex);
        out.set(o); ret;
      }
      
      if (t.equals("hashset")) ret with parseHashSet(out);
      if (t.equals("lhs")) ret with parseLinkedHashSet(out);
      if (t.equals("treeset")) ret with parseTreeSet(out);
      if (t.equals("ciset")) ret with parseCISet(out);
      
      if (eqOneOf(t, "hashmap", "hm")) {
        consume();
        parseMap(new HashMap, out);
        ret;
      }
      if (t.equals("lhm")) {
        consume();
        parseMap(new LinkedHashMap, out);
        ret;
      }
      if (t.equals("tm")) {
        consume();
        parseMap(new TreeMap, out);
        ret;
      }
      if (t.equals("cimap")) {
        consume();
        parseMap(ciMap(), out);
        ret;
      }
      
      if (t.equals("ll")) {
        consume();
        new LinkedList l;
        if (refID >= 0) refs.put(refID, l);
        ret with parseList(l, out);
      }

      if (t.equals("syncLL")) { // legacy
        consume();
        ret with parseList(synchroLinkedList(), out);
      }

      if (t.equals("sync")) {
        consume();
        ret with parse(new Receiver {
          void set(O value) {
            if (value instanceof Map) {
              ifndef Android // Java 7
              if (value cast NavigableMap)
                ret with out.set(synchroNavigableMap(value);
              endifndef
              if (value cast SortedMap)
                ret with out.set(synchroSortedMap(value);
              ret with out.set(synchroMap((Map) value));
            } else
              ret with out.set(synchroList((L) value);
          }
        });
      }
      
      if (t.equals("{")) {
        parseMap(out); ret;
      }
      if (t.equals("[")) {
        new ArrayList l;
        if (refID >= 0) refs.put(refID, l);
        this.parseList(l, out); ret;
      }
      if (t.equals("bitset")) {
        parseBitSet(out); ret;
      }
      if (t.equals("array") || t.equals("intarray") || t.equals("dblarray")) {
        parseArray(out); ret;
      }
      if (t.equals("ba")) {
        consume();
        S hex = unquote(tpp());
        out.set(hexToBytes(hex)); ret;
      }
      if (t.equals("boolarray")) {
        consume();
        int n = parseInt(tpp());
        S hex = unquote(tpp());
        out.set(boolArrayFromBytes(hexToBytes(hex), n)); ret;
      }
      if (t.equals("class")) {
        out.set(parseClass()); ret;
      }
      if (t.equals("l")) {
        parseLisp(out); ret;
      }
      if (t.equals("null")) {
        consume(); out.set(null); ret;
      }
      
      if (eq(t, "c")) {
        consume();
        t = t();
        assertTrue(isJavaIdentifier(t));
        concepts.add(t);
      }
      
      // custom deserialization (new static method method)
      if (eq(t, "cu")) {
        consume();
        t = tpp();
        assertTrue(isJavaIdentifier(t));
        S fullClassName = mcDollar + t;
        Class _c = findAClass(fullClassName);
        if (_c == null) fail("Class not found: " + fullClassName);
        parse(new Receiver {
          void set(O value) {
            ifdef unstructure_debug
              print("Consumed custom object, next token: " + t());
            endifdef
            out.set(call(_c, "_deserialize", value);
          }
        });
        ret;
      }
    }
    
    if (eq(t, "j")) {
      consume();
      out.set(parseJava()); ret;
    }
    
    if (eq(t, "bc")) {
      consume();
      S c1 = tpp();
      S c2 = tpp();
      baseClassMap.put(c1, c2);
      ret with parse_inner(refID, i, out);
    }
    
    // add more tokens here

    if (c == null && !isJavaIdentifier(t))
      throw new RuntimeException("Unknown token " + (i+1) + ": " + quote(t));
      
    // any other class name (or package name)
    consume();
    S className, fullClassName;
    
    // Is it a package name?
    if (eq(t(), ".")) {
      consume();
      className = fullClassName = t + "." + assertIdentifier(tpp());
    } else {
      className = t;
      fullClassName = mcDollar + t;
    }
    
    if (c == null && !allDynamic) {
      // First, find class
      c = findAClass(fullClassName);
      if (c != null)
        classesMap.put(className, c);
    }
    
    // check for existing base class
    if (c == null && !allDynamic) {
      new Set<S> seen;
      S parent = className;
      while true {
        S baseName = baseClassMap.get(parent);
        if (baseName == null)
          break;
        if (!seen.add(baseName))
          fail("Cyclic superclass info: " + baseName);
        c = findAClass(mcDollar + baseName);
        if (c == null)
          print("Base class " + baseName + " of " + parent +  " doesn't exist either");
        else if (isAbstract(c))
          print("Can't instantiate abstract base class: " + c);
        else {
          printVars_str("Reverting to base class", +className, +baseName, +c);
          classesMap.put(className, c);
          break;
        }
        parent = baseName;
      }
    }
        
    // Check if it has an outer reference
    bool hasBracket = eq(t(), "(");
    if (hasBracket) consume();
    bool hasOuter = hasBracket && startsWith(t(), "this$");
    
    DynamicObject dO = null;
    O o = null;
    fS thingName = t;
    if (c != null) {
      if (hasOuter) ctex {
        Constructor ctor = innerClassConstructors.get(c);
        if (ctor == null)
          innerClassConstructors.put(c, ctor = nuStubInnerObject_findConstructor(c, classFinder));
        o = ctor.newInstance(new O[] {null});
      } else
        o = nuEmptyObject(c);
      if (o instanceof DynamicObject) dO = (DynamicObject) o;
    } else {
      if (concepts.contains(t) && (c = findAClass(mcDollar + "Concept")) != null)
        o = dO = (DynamicObject) nuEmptyObject(c);
      else
        dO = new DynamicObject;
      dO.className = className;
      ifdef unstructure_debug
        print("Made dynamic object " + t + " " + shortClassName(dO));
      endifdef
    }
    
    // Save in references list early because contents of object
    // might link back to main object
    
    if (refID >= 0)
      refs.put(refID, o != null ? o : dO);
    tokrefs.put(tokIndex, o != null ? o : dO);
    
    // NOW parse the fields!
    
    new /*Linked*/HashMap<S, O> fields; // no longer preserving order (why did we do this?)
    O _o = o;
    DynamicObject _dO = dO;
    if (hasBracket) {
      stack.add(r {
        ifdef unstructure_debug
          print("in object values, token: " + t());
        endifdef
        if (eq(t(), ",")) consume();
        if (eq(t(), ")")) {
          consume(")");
          objRead(_o, _dO, fields, hasOuter);
          out.set(_o != null ? _o : _dO);
        } else {
          final S key = unquote(tpp());
          S t = tpp();
          if (!eq(t, "="))
            fail("= expected, got " + t + " after " + quote(key) + " in object " + thingName /*+ " " + sfu(fields)*/);
          stack.add(this);
          parse(new Receiver {
            void set(O value) {
              fields.put(key, value);
              /*ifdef unstructure_debug
                print("Got field value " + value + ", next token: " + t());
              endifdef*/
              //if (eq(t(), ",")) consume();
            }
          });
        }
      });
    } else {
      objRead(o, dO, fields, hasOuter);
      out.set(o != null ? o : dO);
    }
  }
  
  void objRead(O o, DynamicObject dO, MapSO fields, bool hasOuter) {
    ifdef unstructure_debug
    print("objRead " + className(o) + " " + className(dO) + " " + struct(fields));
    endifdef
    
    // translate between diferent compilers (this$0 vs this$1)
    O outer = fields.get("this$0");
    if (outer != null) fields.put("this$1", outer);
    else {
      outer = fields.get("this$1");
      if (outer != null) fields.put("this$0", outer);
    }
    
    if (o != null) {
      if (dO != null) {
        ifdef unstructure_debug
          printStructure("setOptAllDyn", fields);
        endifdef
        setOptAllDyn_pcall(dO, fields);
      } else {
        setOptAll_pcall(o, fields);
        ifdef unstructure_debug
          print("objRead now: " + struct(o));
        endifdef
      }
      if (hasOuter)
        fixOuterRefs(o);
    } else for (Map.Entry<S, O> e : fields.entrySet())
      setDynObjectValue(dO, intern(e.getKey()), e.getValue());

    if (o != null)
      pcallOpt_noArgs(o, "_doneLoading");
  }
  
  void parseSet(final Set set, final Receiver out) {
    this.parseList(new ArrayList, new Receiver {
      void set(O o) {
        set.addAll((L) o);
        out.set(set);
      }
    });
  }
  
  void parseLisp(final Receiver out) {
    ifclass Lisp
      consume("l");
      consume("(");
      final new ArrayList list;
      stack.add(r {
        if (eq(t(), ")")) {
          consume(")");
          out.set(Lisp((S) list.get(0), subList(list, 1)));
        } else {
          stack.add(this);
          parse(new Receiver {
            void set(O o) {
              list.add(o);
              if (eq(t(), ",")) consume();
            }
          });
        }
      });
      if (false) // skip fail line
    endif
    
    fail("class Lisp not included");
  }
  
  void parseBitSet(final Receiver out) {
    consume("bitset");
    consume("{");
    final new BitSet bs;
    stack.add(r {
      if (eq(t(), "}")) {
        consume("}");
        out.set(bs);
      } else {
        stack.add(this);
        parse(new Receiver {
          void set(O o) {
            bs.set((Integer) o);
            if (eq(t(), ",")) consume();
          }
        });
      }
    });
  }
  
  void parseList(final L list, final Receiver out) {
    tokrefs.put(i, list);
    consume("[");
    stack.add(r {
      if (eq(t(), "]")) {
        consume();
        ifdef unstructure_debug
          print("Consumed list, next token: " + t());
        endifdef
        out.set(list);
      } else {
        stack.add(this);
        parse(new Receiver {
          void set(O o) {
            //if (debug) print("List element type: " + getClassName(o));
            list.add(o);
            if (eq(t(), ",")) consume();
          }
        });
      }
    });
  }
  
  void parseArray(Receiver out) {
    S _type = tpp();
    int dims;

    if (eq(t(), "S")) { // string array
      _type = "S";
      consume();
    }
    
    if (eq(t(), "/")) { // multi-dimensional array
      consume();
      dims = parseInt(tpp());
    } else
      dims = 1;
    
    consume("{");
    List list = new ArrayList;
    S type = _type;
    
    stack.add(r {
      if (eq(t(), "}")) {
        consume("}");
        if (dims > 1) {
          Class atype;
          if (type.equals("intarray")) atype = int.class;
          else if (type.equals("S")) atype = S.class;
          else todo("multi-dimensional arrays of other types");
          
          out.set(list.toArray((O[]) newMultiDimensionalOuterArray(atype, dims, l(list))));
        } else
          out.set(
            type.equals("intarray") ? toIntArray(list)
            : type.equals("dblarray") ? toDoubleArray(list)
            : type.equals("S") ? toStringArray(list)
            : list.toArray());
      } else {
        stack.add(this);
        parse(new Receiver {
          void set(O o) {
            list.add(o);
            if (eq(t(), ",")) consume();
          }
        });
      }
    });
  }
  
  Object parseClass() {
    consume("class");
    consume("(");
    S name = unquote(tpp());
    consume(")");
    Class c = allDynamic ? null : findAClass(name);
    if (c != null) ret c;
    new DynamicObject dO;
    dO.className = "java.lang.Class";
    name = dropPrefix(mcDollar, name);
    dO.fieldValues.put("name", name);
    ret dO;
  }
  
  Object parseBigInt() {
    consume("bigint");
    consume("(");
    S val = tpp();
    if (eq(val, "-"))
      val = "-" + tpp();
    consume(")");
    ret new BigInteger(val);
  }
  
  Object parseDouble() {
    consume("d");
    consume("(");
    S val = unquote(tpp());
    consume(")");
    ret Double.parseDouble(val);
  }
  
  Object parseFloat() {
    consume("fl");
    S val;
    if (eq(t(), "(")) {
      consume("(");
      val = unquote(tpp());
      consume(")");
    } else {
      val = unquote(tpp());
    }
    ret Float.parseFloat(val);
  }
  
  void parseHashSet(Receiver out) {
    consume("hashset");
    parseSet(new HashSet, out);
  }
  
  void parseLinkedHashSet(Receiver out) {
    consume("lhs");
    parseSet(new LinkedHashSet, out);
  }
  
  void parseTreeSet(Receiver out) {
    consume("treeset");
    parseSet(new TreeSet, out);
  }
  
  void parseCISet(Receiver out) {
    consume("ciset");
    parseSet(ciSet(), out);
  }
  
  void parseMap(Receiver out) {
    parseMap(new TreeMap, out);
  }
  
  O parseJava() {
    S j = unquote(tpp());
    new Matches m;
    if (jmatch("java.awt.Color[r=*,g=*,b=*]", j, m))
      ret nuObject("java.awt.Color", parseInt($1), parseInt($2), parseInt($3));
    else {
      warn("Unknown Java object: " + j);
      null;
    }
  }
  
  void parseMap(final Map map, final Receiver out) {
    consume("{");
    stack.add(new Runnable {
      bool v;
      O key;
      
      public void run() { 
        if (v) {
          v = false;
          stack.add(this);
          if (!eq(tpp(), "="))
            fail("= expected, got " + t() + " in map of size " + l(map));

          parse(new Receiver {
            void set(O value) {
              map.put(key, value);
              ifdef unstructure_debug
                print("parseMap: Got value " + getClassName(value) + ", next token: " + quote(t()));
              endifdef
              if (eq(t(), ",")) consume();
            }
          });
        } else {
          if (eq(t(), "}")) {
            consume("}");
            out.set(map);
          } else {
            v = true;
            stack.add(this);
            parse(new Receiver {
              void set(O o) {
                key = o;
              }
            });
          }
        } // if v else
      } // run()
    });
  }
  
  /*void parseSub(Receiver out) {
    int n = l(stack);
    parse(out);
    while (l(stack) > n)
      stack
  }*/
  
  void consume() { curT = tok.next(); ++i; }
  
  void consume(S s) {
    if (!eq(t(), s)) {
      /*S prevToken = i-1 >= 0 ? tok.get(i-1) : "";
      S nextTokens = join(tok.subList(i, Math.min(i+2, tok.size())));
      fail(quote(s) + " expected: " + prevToken + " " + nextTokens + " (" + i + "/" + tok.size() + ")");*/
      fail(quote(s) + " expected, got " + quote(t()));
    }
    consume();
  }
    
  // outer wrapper function getting first token and unwinding the stack
  void parse_initial(Receiver out) {
    consume(); // get first token
    if (t() == null) ret with out.set(null); // empty string
    parse(out);
    while (nempty(stack))
      popLast(stack).run();
  }

  O parse() {
    ThreadLocal<Bool> tlLoading = dynamicObjectIsLoading_threadLocal();
    Bool b = tlLoading!;
    tlLoading.set(true);
    try {
      new Var v;
      parse_initial(new Receiver {
        void set(O o) { v.set(o); }
      });
      ret v!;
    } finally {
      tlLoading.set(b);
    }
  }
}

Began life as a copy of #1030946