sbool structure_showTiming, structure_checkTokenCount;

sS structure(O o) {
  ret structure(o, new structure_Data);
}

sS structure(O o, structure_Data d) {
  new StringWriter sw;
  d.out = new PrintWriter(sw);
  structure_go(o, d);
  S s = str(sw);
  if (structure_checkTokenCount) {
    print("token count=" + d.n);
    assertEquals("token count", l(javaTokC(s)), d.n);
  }
  ret s;
}

svoid structure_go(O o, structure_Data d) {
  structure_1(o, d);
  while (nempty(d.stack))
    popLast(d.stack).run();
}

svoid structureToPrintWriter(O o, PrintWriter out, structure_Data d default new) {
  d.out = out;
  structure_go(o, d);
}

// leave to false, unless unstructure() breaks
static boolean structure_allowShortening = false;

// info on how to serialize objects of a certain class
sclass structure_ClassInfo<A> {
  Class c;
  S shortName;
  L<Field> fields;
  Method customSerializer;
  IVF1<O> serializeObject; // can be set by caller of structure function
  bool special; // various special classes
  bool nullInstances; // serialize all instances as null (e.g. lambdas/anonymous classes)
  bool javafy; // always convert to "j ..."
  O emptyInstance; // to grab default field values from
  
  toString {
    ret commaCombine(
      "Class " + className(c),
      stringIf(+special),
      stringIf(+customSerializer != null),
      stringIf(+javafy),
      stringIf(+nullInstances),
    );
  }
  
  void nullInstances(bool b) {
    this.nullInstances = b;
    if (b) set special;
  }
  
  void javafy(bool b) {
    this.javafy = b;
    if (b) set special;
  }
  
  // overridable - return true if you wrote the object
  bool handle(A o) { false; }
}

sclass structure_Data {
  PrintWriter out;
  int stringSizeLimit;
  int shareStringsLongerThan = 20;
  bool noStringSharing;
  bool storeBaseClasses;
  bool honorFieldOrder = true;
  S mcDollar = actualMCDollar();
  settable bool warnIfUnpersistable = true;
  settable bool stackTraceIfUnpersistable = true;
  
  // skip a field if it has the default value defined in the class
  // -slower, and may cause issues with schema evolution
  // -OTOH, it can serialize null values for a field with default non-null value
  settable bool skipDefaultValues;
  
  structure_Data d() { this; }

  swappable bool shouldIncludeField(Field f) { true; }

  new IdentityHashMap<O, Integer> seen;
  //new BitSet refd;
  new HashMap<S, Int> strings;
  new HashSet<S> concepts;
  HashMap<Class, structure_ClassInfo> infoByClass = new HashMap;
  
  // wrapper for _persistenceInfo field or _persistenceInfo method
  // by class (taking the object instance)
  new HashMap<Class, IF1<O, Map>> persistenceInfo;
  
  int n; // token count
  new L<Runnable> stack;
  
  // append single token
  structure_Data append(S token) { out.print(token); ++n; ret this; }
  structure_Data append(int i) { out.print(i); ++n; ret this; }
  
  // append multiple tokens
  structure_Data append(S token, int tokCount) { out.print(token); n += tokCount; ret this; }
  
  // extend last token
  structure_Data app(S token) { out.print(token); this; }
  structure_Data app(int i) { out.print(i); this; }
  structure_Data app(char c) { out.print(c); this; }

  structure_ClassInfo infoForClass(Class c) {
    structure_ClassInfo info = infoByClass.get(c);
    if (info == null) info = newClass(c);
    ret info;
  }
  
  swappable S realShortName(S name) {
    ret dropPrefix("main$",
      dropPrefix("loadableUtils.utils$",
        dropPrefix(mcDollar, name)));
  }
  
  // called when a new class is detected
  // can be overridden by clients
  structure_ClassInfo newClass(Class c) {
    // special classes here!
    
    var d = d();
    bool isJavaXClass = isJavaXClassName(c.getName(), mcDollar);
    printVars ifdef structure_debug("newClass", +c, +isJavaXClass);
    
    if (c == S)
      ret new structure_ClassInfo<S> {
        @Override bool handle(S o) {
          S s = d.stringSizeLimit != 0 ? shorten((S) o, d.stringSizeLimit) : (S) o;
          if (!d.noStringSharing) {
            if (d.shareStringsLongerThan == Int.MAX_VALUE)
              d.seen.put(o, d.n);
            if (l(s) >= d.shareStringsLongerThan)
              d.strings.put(s, d.n);
          }
          quoteToPrintWriter(s, d.out); d.n++;
          true;
        }
      };

    
    if (c == File)
      ret new structure_ClassInfo<File> {
        @Override bool handle(File o) {
          append("File ").append(quote(o.getPath()));
          true;
        }
      };

    if (!isJavaXClass) {
      if (isSubClassOf(c, Set.class))
        ret new structure_ClassInfo<Set> {
          @Override bool handle(Set o) {
            writeSet(o);
            true;
          }
        };

      if (isSubClassOf(c, Cl))
        ret new structure_ClassInfo<Cl> {
          @Override bool handle(Cl o) {
            writeCollection(o);
            true;
          }
        };
        
      if (isSubClassOf(c, Map))
        ret new structure_ClassInfo<Map> {
          @Override bool handle(Map o) {
            writeMap(o);
            true;
          }
        };
    }

    new structure_ClassInfo info;
    info.c = c;
    infoByClass.put(c, info);
    
    S name = c.getName();
    S shortName = realShortName(name);
    if (startsWithDigit(shortName)) shortName = name; // for anonymous classes
    info.shortName = shortName;
    
    try {
      if (isSyntheticOrAnonymous(c)) {
        info.nullInstances(true);
        ret info;
      }
      
      if (c.isEnum()) {
        info.special = true;
        ret info;
      }
      
      ifdef OurSyncCollections
        if (isSubClassOf(c, SynchronizedMap))
          ret new structure_ClassInfo<SynchronizedMap> {
            @Override bool handle(SynchronizedMap o) {
              append("sync ");
              structure_1(o.m, d);
              true;
            }
          };
          
        if (isSubClassOf(c, SynchronizedList))
          ret new structure_ClassInfo<SynchronizedList> {
            @Override bool handle(SynchronizedList o) {
              append("sync ");
              structure_1(unwrapSynchronizedList(o), d);
              true;
            }
          };
      endifdef

      if (c.isArray()) {
        // info.special?
        ret info;
      }
      
      if ((info.customSerializer = findMethodNamed(c, '_serialize))
        != null) info.special = true;
        
      if (storeBaseClasses) {
        Class sup = c.getSuperclass();
        if (sup != O) {
          append("bc ");
          append(shortDynClassNameForStructure(c));
          out.print(" ");
          append(shortDynClassNameForStructure(sup));
          out.print(" ");
          infoForClass(sup); // transitively write out superclass relations
        }
      }
      
      if (eqOneOf(name, "java.awt.Color", "java.lang.ThreadLocal"))
        info.javafy(true);
      else if (name.startsWith("sun") || !isPersistableClass(c)) {
        info.javafy(true);
        if (warnIfUnpersistable) {
          S msg = "Class not persistable: " + c + " (anonymous or no default constructor), referenced from " + last(stack);
          if (stackTraceIfUnpersistable)
            printStackTrace(new Throwable(msg));
          else
            print(msg);
        }
      } else if (skipDefaultValues) {
        var ctor = getDefaultConstructor(c);
        if (ctor != null)
          info.emptyInstance = invokeConstructor(ctor);
      }
    } catch print e {
      info.nullInstances(true);
    }
    
    ret info;
  }
  
  void setFields(structure_ClassInfo info, L<Field> fields) { 
    info.fields = fields;
  }
  
  void writeObject(O o, S shortName, MapSO fv) {
    S singleField = fv.size() == 1 ? first(fv.keySet()) : null;
  
    append(shortName);
    n += countDots(shortName)*2; // correct token count
    ifdef structure_debug
      print("Fields for " + shortName + ": " + fv.keySet());
    endifdef
  
    int l = n;
    Iterator it = fv.entrySet().iterator();
    
    class WritingObject is Runnable {
      S lastFieldWritten;
      
      run {
        if (!it.hasNext()) {
          if (n != l)
            append(")");
        } else {
          Map.Entry e = cast it.next();
          append(n == l ? "(" : ", ");
          append(lastFieldWritten = (S) e.getKey()).append("=");
          stack.add(this);
          structure_1(e.getValue(), structure_Data.this);
        }
      }
      
      toString { ret shortName + "." + lastFieldWritten; }
    }
    
    stack.add(new WritingObject);
  }
  
  void writeMap(Map o) {
    var d = this;
    S name = o.getClass().getName();
    if (o instanceof LinkedHashMap) d.append("lhm");
    else if (o instanceof HashMap) d.append("hm");
    else if (o cast TreeMap)
      d.append(isCIMap_gen(o) ? "cimap" : "tm");
    else if (name.equals("java.util.Collections$SynchronizedMap")
      || name.equals("java.util.Collections$SynchronizedSortedMap")
      || name.equals("java.util.Collections$SynchronizedNavigableMap")) {
      d.append("sync "); 
      ret with structure_1(unwrapSynchronizedMap(o/Map), d);
    }
    
    d.append("{");
    final int l = d.n;
    final Iterator it = cloneMap((Map) o).entrySet().iterator();
    
    class WritingMap is Runnable {
      bool v;
      Map.Entry e;
      
      toString {
        ret renderVars("WritingMap", e := mapEntryToPair(e), v := !v);
      }
      
      run {
        if (v) {
          d.append("=");
          v = false;
          d.stack.add(this);
          structure_1(e.getValue(), d);
        } else {
          if (!it.hasNext())
            d.append("}");
          else {
            e = (Map.Entry) it.next();
            v = true;
            d.stack.add(this);
            if (d.n != l) d.append(", ");
            structure_1(e.getKey(), d);
          }
        }
      }
    }
    
    d.stack.add(new WritingMap);
  }

  void writeSet(Set o) {
    var d = this;
    S name = o.getClass().getName();
    
    /*O set2 = unwrapSynchronizedSet(o);
    if (set2 != o) {
      d.append("sync");
      o = set2;
    } TODO */
    
    if (o instanceof TreeSet) {
      d.append(isCISet_gen(o) ? "ciset" : "treeset");
      structure_1(new ArrayList(o), d);
      ret;
    }
    
    // assume it's a HashSet or LinkedHashSet
    d.append(o instanceof LinkedHashSet ? "lhs" : "hashset");
    structure_1(new ArrayList(o), d);
  }

  void writeCollection(Cl o) {
    var d = this;
    S name = o.getClass().getName();
    
    print ifdef structure_debug("writeCollection", name);
    
    if (name.equals("java.util.Collections$SynchronizedList")
      || name.equals("java.util.Collections$SynchronizedRandomAccessList")) {
      d.append("sync ");
      ret with structure_1(unwrapSynchronizedList(o/List), d);
    }
    else if (name.equals("java.util.LinkedList"))
      d.append("ll");
    d.append("[");
    int l = d.n;
    Iterator it = cloneList(o).iterator();
    d.stack.add(r {
      if (!it.hasNext())
        d.append("]");
      else {
        d.stack.add(this);
        if (d.n != l) d.append(", ");
        structure_1(it.next(), d);
      }
    });
  }
} // end of class structure_Data

svoid structure_1(O o, structure_Data d) ctex {
  if (o == null) { d.append("null"); ret; }
  
  Class c = o.getClass();
  bool concept = false;
  ifclass Concept
    concept = o instanceof Concept;
  endif
  structure_ClassInfo info = d.infoForClass(c);
  
  print ifdef structure_debug("structure_1 " + c);

  bool isJavaXName = isJavaXClassName(c.getName(), d.mcDollar);
  
  bool referencable = isJavaXName &&
    !(o instanceof Number || o instanceof Char || o instanceof Bool)
    || o instanceof Cl || o instanceof Map
    || o instanceof Rectangle;
    
  printVars ifdef structure_debug(+isJavaXName, +referencable, mcDollar := d.mcDollar);
  
  if (referencable) {
    Int ref = d.seen.get(o);
    if (ref != null) {
      print ifdef structure_debug("Existing reference " + className(o) + " " + ref);
      //d.refd.set(ref);
      d.append("t").app(ref);
      ret;
    }
    
    d.seen.put(o, d.n); // record token number
    print ifdef structure_debug("Recorded reference " + d.n);
  }
      
  if (info.handle(o)) {
    print ifdef structure_debug("handled by " + className(info));
    ret;
  }
  
  if (info.special) {
    if (info.javafy) {
      d.append("j ").append(quote(str(o))); ret; // This is not unstructure-able except for java.awt.Color
    }
    
    if (c.isEnum()) {
      d.append("enum ");
      d.append(info.shortName);
      d.out.append(' ');
      d.append(((Enum) o).ordinal());
      ret;
    }
    
    if (info.customSerializer != null) {
      // custom serialization (_serialize method)
      O o2 = invokeMethod(info.customSerializer, o);
      if (o2 == o) {} // bail out to standard serialization
      else {
        d.append("cu ");
        S name = c.getName();
        S shortName = d.realShortName(name);
        d.append(shortName);
        d.out.append(' ');
        structure_1(o2, d);
        ret;
      }
    } else if (info.nullInstances) ret with d.append("null");
    else if (info.serializeObject != null)
      ret with info.serializeObject.get(o);
    else fail("unknown special type");
  }
    
  L<Field> lFields = info.fields;
  if (lFields == null) {
    // these are never back-referenced (for readability)
    
    if (o instanceof Number) {
      PrintWriter out = d.out;
if (o instanceof Integer) { int i = ((Int) o).intValue(); out.print(i); d.n += i < 0 ? 2 : 1; ret; }
      if (o instanceof Long) { long l = ((Long) o).longValue(); out.print(l); out.print("L"); d.n += l < 0 ? 2 : 1; ret; }
      if (o cast Short) { short s = o.shortValue(); d.append("sh "); out.print(s); d.n += s < 0 ? 2 : 1; ret; }
      if (o instanceof Float) { d.append("fl ", 2); quoteToPrintWriter(str(o), out); ret; }
      if (o instanceof Double) { d.append("d(", 3); quoteToPrintWriter(str(o), out); d.append(")"); ret; }
      if (o instanceof BigInteger) { out.print("bigint("); out.print(o); out.print(")"); d.n += ((BigInteger) o).signum() < 0 ? 5 : 4; ret; }
    }
  
    if (o instanceof Boolean) {
      d.append(((Boolean) o).booleanValue() ? "t" : "f"); ret;
    }
      
    if (o instanceof Character) {
      d.append(quoteCharacter((Character) o)); ret;
    }
      
    S name = c.getName();
    
    if (!isJavaXName) {
      if (o cast Set)
        ret with d.writeSet(o);
      
      if (o cast Cl
        /* && neq(name, "main$Concept$RefL") */) {
        
        ret with d.writeCollection(o);
      }
    
      if (o cast Map)
        ret with d.writeMap(o);
    }
    
    if (c.isArray()) {
      if (o instanceof byte[]) {
        d.append("ba ").append(quote(bytesToHex((byte[]) o))); ret;
      }
  
      final int n = Array.getLength(o);
  
      if (o instanceof bool[]) {
        S hex = boolArrayToHex((bool[]) o);
        int i = l(hex);
        while (i > 0 && hex.charAt(i-1) == '0' && hex.charAt(i-2) == '0') i -= 2;
        d.append("boolarray ").append(n).app(" ").append(quote(substring(hex, 0, i))); ret;
      }
      
      if (o cast short[]) {
        S hex = shortArrayToHex_bigEndian(o);
        d.append("shortarray \"").append(hex).app('\"');
        ret;
      }
      
      if (o cast long[]) {
        S hex = longArrayToHex_bigEndian(o);
        d.append("longarray \"").append(hex).app('\"');
        ret;
      }
      
      S atype = "array"/*, sep = ", "*/; // sep is not used yet
  
      if (o instanceof int[]) {
        //ret "intarray " + quote(intArrayToHex((int[]) o));
        atype = "intarray";
        //sep = " ";
      } else if (o instanceof double[]) {
        atype = "dblarray";
        //sep = " ";
      } else if (o instanceof float[]) {
        atype = "floatarray";
      } else {
        // 2-dimensional and deeper arrays
        Pair<Class, Int> p = arrayTypeAndDimensions(c);
        if (p.a == int.class) atype = "intarray";
        else if (p.a == byte.class) atype = "bytearray";
        else if (p.a == bool.class) atype = "boolarray";
        else if (p.a == double.class) atype = "dblarray";
        else if (p.a == float.class) atype = "floatarray";
        else if (p.a == S) { atype = "array S"; d.n++; }
        else atype = "array"; // fail("Unsupported array type: " + p.a);
        if (p.b > 1) {
          atype += "/" + p.b; // add number of dimensions
          d.n += 2; // 2 additional tokens will be written
        }
      }
      
      d.append(atype).append("{");
      d.stack.add(new Runnable() {
        int i;
        public void run() {
          if (i >= n)
            d.append("}");
          else {
            d.stack.add(this);
            if (i > 0) d.append(", ");
            structure_1(Array.get(o, i++), d);
          }
        }
      });
      ret;
    }
  
    if (o instanceof Class) {
      d.append("class(", 2).append(quote(((Class) o).getName())).append(")"); ret;
    }
      
    if (o instanceof Throwable) {
      d.append("exception(", 2).append(quote(((Throwable) o).getMessage())).append(")"); ret;
    }
      
    if (o instanceof BitSet) {
      BitSet bs = (BitSet) o;
      d.append("bitset{", 2);
      int l = d.n;
      for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
        if (d.n != l) d.append(", ");
        d.append(i);
      }
      d.append("}"); ret;
    }
      
    ifclass Lisp
      if (o instanceof Lisp) {
        d.append("l(", 2);
        final Lisp lisp = cast o;
        structure_1(lisp.head, d);
        final Iterator it = lisp.args == null ? emptyIterator() : lisp.args.iterator();
        d.stack.add(r {
          if (!it.hasNext())
            d.append(")");
          else {
            d.stack.add(this);
            d.append(", ");
            structure_1(it.next(), d);
          }
        });
        ret;
      }
    endif
      
    /*if (name.equals("main$Lisp")) {
      fail("lisp not supported right now");
    }*/
    
    S dynName = shortDynClassNameForStructure(o);
    if (concept && !d.concepts.contains(dynName)) {
      d.concepts.add(dynName);
      d.append("c ");
    }
    
    // serialize an object with fields.
    // first, collect all fields and values in fv.
    
    TreeSet<Field> fields = new TreeSet<Field>(new Comparator<Field>() {
      public int compare(Field a, Field b) {
        ret stdcompare(a.getName(), b.getName());
      }
    });
    
    Class cc = c;
    while (cc != O.class) {
      for (Field field : getDeclaredFields_cached(cc)) {
        if (!d.shouldIncludeField(field)) continue;
        
        S fieldName = field.getName();
        if (fieldName.equals("_persistenceInfo"))
          d.persistenceInfo.put(c, obj -> (Map) fieldGet(field, obj));
        if ((field.getModifiers() & (java.lang.reflect.Modifier.STATIC | java.lang.reflect.Modifier.TRANSIENT)) != 0)
          continue;

        fields.add(field);
        
        // put special cases here...?
      }
        
      cc = cc.getSuperclass();
    }
    
    Method persistenceInfoMethod = findInstanceMethod(c, "_persistenceInfo");
    if (persistenceInfoMethod != null)
      d.persistenceInfo.put(c, obj -> (Map) invokeMethod(persistenceInfoMethod, obj));
    
    lFields = asList(d.honorFieldOrder ? fieldObjectsInFieldOrder(c, fields) : fields);

    // Render this$0/this$1 first because unstructure needs it for constructor call.
    
    int n = l(lFields);
    for (int i = 0; i < n; i++) {
      Field f = lFields.get(i);
      if (f.getName().startsWith("this$")) {
        lFields.remove(i);
        lFields.add(0, f);
        break;
      }
    }
  
    ifdef structure_debug
      print("Saving fields for " + c + ": " + lFields);
    endifdef
    d.setFields(info, lFields);
  } // << if (lFields == null)

  // get _persistenceInfo from field and/or dynamic field
  IF1<O, Map> piGetter = d.persistenceInfo.get(c);
  Map persistenceInfo = piGetter?.get(o);
  
  if (piGetter == null && o instanceof DynamicObject)
    persistenceInfo = (Map) getOptDynOnly(o/DynamicObject, "_persistenceInfo");

  ifdef structure_debug
    print("persistenceInfo for " + c + ": " + persistenceInfo);
  endifdef
  new LinkedHashMap<S, O> fv;
  O defaultInstance = info.emptyInstance;
  if (!referencable)
    fail("Not referencable: " + className(o));
    
  for (Field f : lFields) {
    O value, defaultValue = null;
    try {
      value = f.get(o);
      defaultValue = defaultInstance == null ?: f.get(defaultInstance);
    } catch (Exception e) {
      value = "?";
    }
      
    if (!eq(defaultValue, value) && (persistenceInfo == null
      || !Boolean.FALSE.equals(persistenceInfo.get(f.getName()))))
      fv.put(f.getName(), value);
      
    ifdef structure_debug
      else print("Skipping default value " + defaultValue + " of " + f.getName() + " for " + identityHashCode(o));
    endifdef
  }
  
  S shortName = info.shortName;
    
  // Now we have fields & values. Process fieldValues if it's a DynamicObject.
  
  O classNameFromFV = fv.get("className");
  
  // omit field "className" if equal to class's name
  if (concept && eq(classNameFromFV, shortName))
    fv.remove("className");
          
  if (o cast DynamicObject) {
    putAll(fv, (Map) fv.get("fieldValues"));
    fv.remove("fieldValues");
    if (o.className != null) {
      // TODO: this probably doesn't work with inner classes
      
      shortName = shortDynClassNameForStructure(o);
      fv.remove("className");
      
      // special handling for missing Class objects encoded as DynamicObject
      if (eq(shortName, "java.lang.Class")) {
        d.append("class(");
        d.append(quoted(fv.get("name")));
        d.append(")");
        ret;
      }
    }
  }
  
  d.writeObject(o, shortName, fv);
}