package gudusoft.gsqlparser.lineage.v2.shape;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collection;
import java.util.EnumSet;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.function.IntFunction;
import java.util.function.IntSupplier;

import gudusoft.gsqlparser.EExpressionType;

/**
 * Builds the {@link Shape} of one analysis (plan 09, slice 1b) from the live recorder and catalog, on the analysis
 * thread: when the analysis freezes ({@link #freeze}) it copies every member the producer reads, records the
 * traversals its visitors replay and makes the mirrors; when the analysis has finished and before it is disposed
 * ({@link #complete}) it takes the text renderings and seals the shape. It then drops every live object.
 *
 * <p>It calls each copied getter once per object, never a getter that creates what it returns (the field is read and
 * a detached empty list stands in, as the getter would have made), never {@code toString()} before
 * {@link #complete}. A getter that throws is recorded and throws the same kind of exception when the mirror's getter
 * is called.</p>
 *
 * <p>Internal API of the SQL-LR producer.</p>
 *
 * @since 4.2.17
 */
public final class ShapeBuilder {

    /** A copied getter call. */
    public interface Call {
        Object call();
    }

    private final Map<Object, Integer> handles = new IdentityHashMap<Object, Integer>();
    private final List<Object> lives = new ArrayList<Object>();
    private final List<Integer> kinds = new ArrayList<Integer>();
    private final List<Object> values = new ArrayList<Object>();
    private final Map<String, Integer> kindByName = new HashMap<String, Integer>();
    private final Map<Class<?>, Integer> kindCache = new HashMap<Class<?>, Integer>();
    private final int kRecorder;
    private final int kElement;
    private final int kReference;
    private final int kStatementRecord;
    private final int kUnit;
    private final int kDerived;
    private final int kFrozen;
    private final int kParseTreeNode;
    private final int kExpression;
    private int projected;

    // traversals
    private final List<int[]> references = new ArrayList<int[]>();
    private final Map<Integer, int[]> traversal = new HashMap<Integer, int[]>();
    private final Map<Integer, String> traversalThrow = new HashMap<Integer, String>();
    private final Map<Integer, int[]> sliceCandidate = new HashMap<Integer, int[]>();
    private final List<Integer> traversalOrder = new ArrayList<Integer>();

    // the recorder's precomputed answers
    private final Map<Integer, Object> frozenColumns = new LinkedHashMap<Integer, Object>();
    private final Map<Integer, Integer> structItems = new LinkedHashMap<Integer, Integer>();

    private Shape shape;
    private int root;
    /** Traversals: slices taken, slices refused (the node's own traversal differs), own without a slice, nodes visited. */
    private final long[] traversalStats = new long[11];
    private int catalogRoot = -1;

    private ShapeBuilder() {
        for (int k = 0; k < ShapeKinds.COUNT; k++) {
            kindByName.put(ShapeKinds.LIVE[k], Integer.valueOf(k));
        }
        String model = "gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations";
        kRecorder = kind(model);
        kElement = kind(model + "$ElementRecord");
        kReference = kind(model + "$ReferenceRecord");
        kStatementRecord = kind(model + "$StatementRecord");
        kUnit = kind(model + "$UnitRecord");
        kDerived = kind(model + "$DerivedRecord");
        kFrozen = kind(model + "$FrozenRelation");
        kParseTreeNode = kind("gudusoft.gsqlparser.nodes.TParseTreeNode");
        kExpression = kind("gudusoft.gsqlparser.nodes.TExpression");
    }

    private int kind(String liveName) {
        Integer k = kindByName.get(liveName);
        if (k == null) {
            throw new IllegalStateException("not in the shape spec: " + liveName);
        }
        return k.intValue();
    }

    /**
     * Projects what the producer reads, when the analysis freezes. {@code recorder} is the live
     * {@code SqllrObservations}; {@code catalog} the live {@code TSQLEnv} the producer reads, or null.
     */
    public static ShapeBuilder freeze(gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations recorder,
            Object catalog) {
        long started = System.nanoTime();
        ShapeBuilder b = new ShapeBuilder();
        b.root = b.handle(recorder);
        b.catalogRoot = b.handle(catalog);
        b.drain();
        // the statements of the units are the roots of the traversals: their recordings are the references others
        // are slices of
        for (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.UnitRecord u : recorder.getUnits()) {
            for (gudusoft.gsqlparser.TCustomSqlStatement s : u.getStatements()) {
                b.traversalOrder.add(Integer.valueOf(b.handle(s)));
            }
        }
        b.close();
        b.shape.setFreezeNanos(System.nanoTime() - started);
        long stored = 0;
        for (int[] r : b.references) {
            stored += r.length / 2;
        }
        b.traversalStats[10] = stored;
        b.shape.setTraversalStats(b.traversalStats.clone());
        return b;
    }

    /**
     * The completed shape of one statement the producer parses itself (a catalog relation's definition): projected,
     * rendered and released at once, as nothing analyses it.
     */
    public static Shape project(gudusoft.gsqlparser.TCustomSqlStatement statement) {
        ShapeBuilder b = new ShapeBuilder();
        b.root = b.handle(statement);
        b.traversalOrder.add(Integer.valueOf(b.root));
        b.close();
        return b.complete();
    }

    /**
     * {@link #project}, keeping the live objects: a caller holding the live tree finds the mirrors of its nodes with
     * {@link #mirrorOf}.
     */
    public static ShapeBuilder projectKeepingLive(gudusoft.gsqlparser.TCustomSqlStatement statement) {
        ShapeBuilder b = new ShapeBuilder();
        b.root = b.handle(statement);
        b.traversalOrder.add(Integer.valueOf(b.root));
        b.close();
        b.complete(true);
        return b;
    }

    /** The mirror of a projected live object, until {@link #release}; null when it was not projected. */
    public ShapeObject mirrorOf(Object live) {
        int h = handleOf(live);
        return h < 0 ? null : shape.at(h);
    }

    /** Projects and records traversals until nothing new is reached, then makes the mirrors. */
    private void close() {
        while (true) {
            long t0 = System.nanoTime();
            drain();
            long t1 = System.nanoTime();
            int before = traversal.size();
            traverseAll();
            traversalStats[4]++;
            traversalStats[5] += t1 - t0;
            traversalStats[6] += System.nanoTime() - t1;
            if (traversal.size() == before && projected == lives.size()) {
                break;
            }
        }
        long t2 = System.nanoTime();
        build();
        traversalStats[7] += System.nanoTime() - t2;
    }

    /** The handle of a live object, projected later; -1 for null. */
    int handle(Object live) {
        if (live == null) {
            return -1;
        }
        Integer h = handles.get(live);
        if (h != null) {
            return h.intValue();
        }
        int k = kindOf(live.getClass());
        if (k < 0) {
            throw new IllegalArgumentException("no mirror for " + live.getClass().getName());
        }
        h = Integer.valueOf(lives.size());
        handles.put(live, h);
        lives.add(live);
        kinds.add(Integer.valueOf(k));
        values.add(null);
        return h.intValue();
    }

    /** The kind of a live object no mirror class stands for: an opaque {@link LiveObject}. */
    static final int OPAQUE = Integer.MAX_VALUE;

    /**
     * The kind of the nearest mirrored class of a live class, else of a mirrored interface it implements, else
     * {@link #OPAQUE} for another object of the analysis (a parse tree node, a model object, a resolver or catalog
     * object); -1 for anything else.
     */
    int kindOf(Class<?> c) {
        Integer cached = kindCache.get(c);
        if (cached != null) {
            return cached.intValue();
        }
        int found = -1;
        for (Class<?> x = c; x != null && found < 0; x = x.getSuperclass()) {
            Integer k = kindByName.get(x.getName());
            if (k != null && !ShapeKinds.INTERFACE[k.intValue()]) {
                found = k.intValue();
            }
        }
        if (found < 0) {
            for (int k = 0; k < ShapeKinds.COUNT && found < 0; k++) {
                if (!ShapeKinds.INTERFACE[k]) {
                    continue;
                }
                try {
                    if (Class.forName(ShapeKinds.LIVE[k]).isAssignableFrom(c)) {
                        found = k;
                    }
                } catch (ClassNotFoundException e) {
                    throw new IllegalStateException(e);
                }
            }
        }
        if (found < 0 && isAnalysisObject(c)) {
            found = OPAQUE;
        }
        kindCache.put(c, Integer.valueOf(found));
        return found;
    }

    private static boolean isAnalysisObject(Class<?> c) {
        String n = c.getName();
        return n.startsWith("gudusoft.gsqlparser.nodes.") || n.startsWith("gudusoft.gsqlparser.stmt.")
                || n.startsWith("gudusoft.gsqlparser.dlineage.dataflow.model.")
                || n.startsWith("gudusoft.gsqlparser.resolver2.") || n.startsWith("gudusoft.gsqlparser.sqlenv.")
                || n.startsWith("gudusoft.gsqlparser.T");
    }

    /** Projects every handed-out live object not yet projected. */
    private void drain() {
        while (projected < lives.size()) {
            int h = projected++;
            values.set(h, extract(kinds.get(h).intValue(), lives.get(h)));
        }
    }

    private Object extract(int k, Object live) {
        if (k == OPAQUE) {
            return null;
        }
        if (k == kRecorder) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations r =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations) live;
            Object[] v = {refs(r::getUnits), refs(r::getElements), refs(r::getReferences), refs(r::getFrozenRelations),
                refs(r::getFrozenResultSets), refs(r::getDerived), refs(r::getStatements)};
            for (gudusoft.gsqlparser.dlineage.dataflow.model.ResultSet rs : r.getFrozenResultSets()) {
                frozenColumns.put(Integer.valueOf(handle(rs)), refs(() -> r.getFrozenColumns(rs)));
            }
            for (Object column : r.getStructFieldColumns()) {
                structItems.put(Integer.valueOf(handle(column)), Integer.valueOf(handle(r.getStructItem(column))));
            }
            return v;
        }
        if (k == kElement) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.ElementRecord e =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.ElementRecord) live;
            return new Object[] {ref(e::getRelation), ref(e::getElement), Boolean.valueOf(e.isTarget()),
                ref(e::getReference), ref(e::getStatement), Long.valueOf(e.getSequence())};
        }
        if (k == kReference) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.ReferenceRecord e =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.ReferenceRecord) live;
            return new Object[] {ref(e::getReference), dynamic(e::getTarget), ref(e::getStatement),
                Long.valueOf(e.getSequence())};
        }
        if (k == kStatementRecord) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.StatementRecord e =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.StatementRecord) live;
            Throwable f = e.getFailure();
            return new Object[] {ref(e::getStatement), f == null ? null : f.getClass().getName(),
                f == null ? null : f.getMessage(), Boolean.valueOf(e.isFinished()),
                f == null ? null : f.getClass().getSimpleName()};
        }
        if (k == kUnit) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.UnitRecord e =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.UnitRecord) live;
            return new Object[] {Integer.valueOf(e.getUnitIndex()), Integer.valueOf(e.getParseResult()),
                refs(e::getStatements), refs(e::getSyntaxErrors), refs(e::getRecoveredSyntaxErrors)};
        }
        if (k == kDerived) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.DerivedRecord e =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.DerivedRecord) live;
            return new Object[] {ref(e::getStatement), ref(e::getSite)};
        }
        if (k == kFrozen) {
            gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.FrozenRelation e =
                    (gudusoft.gsqlparser.dlineage.dataflow.model.SqllrObservations.FrozenRelation) live;
            return new Object[] {ref(e::getRelation), ref(e::getTarget)};
        }
        return ShapeKinds.extract(k, live, this);
    }

    // ---------------------------------------------------------------------------------------------
    // Member copies (called by ShapeKinds)
    // ---------------------------------------------------------------------------------------------

    static boolean isValue(Object v) {
        return v instanceof String || v instanceof Number || v instanceof Boolean || v instanceof Character
                || v instanceof Enum || v instanceof EnumSet || v instanceof gudusoft.gsqlparser.dlineage.util.Pair3
                || v instanceof gudusoft.gsqlparser.sqlenv.IdentifierService
                || v instanceof gudusoft.gsqlparser.sqlenv.CanonKey;
    }

    private static Shape.Throw thrown(Throwable t) {
        return new Shape.Throw(t.getClass().getName(), t.getMessage());
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    Object value(Call c) {
        try {
            Object v = c.call();
            if (v == null) {
                return null;
            }
            if (v instanceof EnumSet) {
                return EnumSet.copyOf((EnumSet) v);
            }
            return isValue(v) ? valueSlot(v) : new Shape.Unsupported(v.getClass().getName());
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    /** A value as its slot holds it: an identifier service by its profile ({@link Shape.Service}). */
    private static Object valueSlot(Object v) {
        return v instanceof gudusoft.gsqlparser.sqlenv.IdentifierService
                ? new Shape.Service((gudusoft.gsqlparser.sqlenv.IdentifierService) v) : v;
    }

    Object values(Call c) {
        try {
            Object v = c.call();
            if (v == null) {
                return null;
            }
            if (v instanceof EnumSet) {
                return value(c);
            }
            List<Object> copy = new ArrayList<Object>();
            for (Object o : (Collection<?>) v) {
                if (o != null && (!isValue(o) || o instanceof gudusoft.gsqlparser.sqlenv.IdentifierService)) {
                    return new Shape.Unsupported("a collection of " + o.getClass().getName());
                }
                copy.add(o);
            }
            return java.util.Collections.unmodifiableList(copy);
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    Object ref(Call c) {
        try {
            Object v = c.call();
            if (v == null) {
                return null;
            }
            if (kindOf(v.getClass()) < 0) {
                return new Shape.Unsupported(v.getClass().getName());
            }
            return new Shape.Ref(handle(v));
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    Object refs(Call c) {
        try {
            Object v = c.call();
            if (v == null) {
                return null;
            }
            Collection<?> list = (Collection<?>) v;
            int[] hs = new int[list.size()];
            int i = 0;
            for (Object o : list) {
                if (o != null && kindOf(o.getClass()) < 0) {
                    return new Shape.Unsupported("a collection of " + o.getClass().getName());
                }
                hs[i++] = handle(o);
            }
            return new Shape.Refs(hs);
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    Object dynamic(Call c) {
        try {
            Object v = c.call();
            if (v instanceof EnumSet) {
                return EnumSet.copyOf((EnumSet) v);
            }
            if (v == null || isValue(v)) {
                return valueSlot(v);
            }
            if (kindOf(v.getClass()) >= 0) {
                return new Shape.Ref(handle(v));
            }
            return new Shape.Unsupported(v.getClass().getName());
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    /**
     * A getter that creates an empty list when its field is null: the field is read; when null, a detached empty list
     * of the kind's class stands in, as the getter would have made, and the tree is not changed.
     */
    Object lazy(Object owner, String fieldName, int kind) {
        try {
            Class<?> type = Class.forName(ShapeKinds.LIVE[kind]);
            Field f = lazyField(owner.getClass(), fieldName, type);
            Object v = f.get(owner);
            if (v == null) {
                v = type.getConstructor().newInstance();
            }
            return new Shape.Ref(handle(v));
        } catch (IllegalStateException e) {
            throw e;
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    private static final java.util.concurrent.ConcurrentHashMap<List<Object>, Field> LAZY_FIELDS =
            new java.util.concurrent.ConcurrentHashMap<List<Object>, Field>();

    /**
     * The field a lazy getter reads, by name: the fields are private, and every shipping ProGuard policy keeps these
     * names (proguard-gsp-api.cfg; ShapeLazyFieldsKeptTest). Its type must be the kind's list class, so a drift of the
     * live class fails here, not silently.
     */
    static Field lazyField(Class<?> ownerClass, String fieldName, Class<?> type) {
        List<Object> key = java.util.Arrays.<Object>asList(ownerClass, fieldName);
        Field cached = LAZY_FIELDS.get(key);
        if (cached != null) {
            return cached;
        }
        Field f = null;
        for (Class<?> c = ownerClass; c != null; c = c.getSuperclass()) {
            try {
                Field declared = c.getDeclaredField(fieldName);
                if (f != null) {
                    // a subclass shadows the field: which one the getter reads is not known here
                    throw new IllegalStateException("two fields " + fieldName + " in " + ownerClass.getName());
                }
                f = declared;
            } catch (NoSuchFieldException e) {
                // the superclass declares it
            }
        }
        if (f == null || f.getType() != type) {
            throw new IllegalStateException("no field " + fieldName + " of " + type.getName() + " in "
                    + ownerClass.getName() + " (a renamed field: keep it in proguard-gsp-api.cfg)");
        }
        f.setAccessible(true);
        LAZY_FIELDS.put(key, f);
        return f;
    }

    /** The elements of a list class, by its own size and element getter. */
    Object elements(IntSupplier size, IntFunction<Object> get) {
        try {
            int n = size.getAsInt();
            int[] hs = new int[n];
            for (int i = 0; i < n; i++) {
                Object o = get.apply(i);
                if (o != null && kindOf(o.getClass()) < 0) {
                    return new Shape.Unsupported("an element " + o.getClass().getName());
                }
                hs[i] = handle(o);
            }
            return new Shape.Refs(hs);
        } catch (Throwable t) {
            return thrown(t);
        }
    }

    // ---------------------------------------------------------------------------------------------
    // Traversals
    // ---------------------------------------------------------------------------------------------

    /**
     * One recorded live traversal: the relevant events ({overload, handle} pairs), each node's first place, every
     * closed place of at least {@link #MIN_SHARED} events of a node with a handle ({handle, start, end}), and how it
     * ended. Primitive arrays: a recording can hold millions of events (a long UNION chain's statement list).
     */
    private final class Recording implements RecordingVisitor.Sink {
        int[] events = new int[64];
        int size;
        final Map<Object, int[]> places = new IdentityHashMap<Object, int[]>();
        int[] occurrences = new int[48];
        int occurrenceCount;
        Object[] openNodes = new Object[32];
        int[] openStarts = new int[32];
        boolean[] openDirect = new boolean[32];
        int depth;
        final Object root;
        String threw;
        long visited;

        Recording(Object root) {
            this.root = root;
        }

        @Override
        public void event(boolean pre, int overload, Object node) {
            if (pre) {
                visited++;
                if (overload >= 0) {
                    if (2 * size + 2 > events.length) {
                        events = java.util.Arrays.copyOf(events, events.length * 2);
                    }
                    events[2 * size] = overload;
                    events[2 * size + 1] = handle(node);
                    size++;
                }
                if (depth == openNodes.length) {
                    openNodes = java.util.Arrays.copyOf(openNodes, depth * 2);
                    openStarts = java.util.Arrays.copyOf(openStarts, depth * 2);
                    openDirect = java.util.Arrays.copyOf(openDirect, depth * 2);
                }
                // the start counts the node's own relevant event, which its own traversal begins with
                openNodes[depth] = node;
                openStarts[depth] = size - (overload >= 0 ? 1 : 0);
                // the recording's root is its own acceptChildren; a node inside a node whose region is its own
                // acceptChildren, of a class whose acceptChildren reaches every child through the child's own
                // acceptChildren, has its own acceptChildren as its region too (DirectTraversals)
                openDirect[depth] = depth == 0 ? node == root
                        : openDirect[depth - 1] && DirectTraversals.directChild(openNodes[depth - 1], node);
                depth++;
            } else if (depth > 0 && openNodes[depth - 1] == node) {
                depth--;
                openNodes[depth] = null;
                int start = openStarts[depth];
                if (!places.containsKey(node)) {
                    places.put(node, new int[] {start, size, openDirect[depth] ? 1 : 0});
                }
                if (size - start >= MIN_SHARED) {
                    Integer h = handles.get(node);
                    if (h != null) {
                        if (3 * occurrenceCount + 3 > occurrences.length) {
                            occurrences = java.util.Arrays.copyOf(occurrences, occurrences.length * 2);
                        }
                        occurrences[3 * occurrenceCount] = h.intValue();
                        occurrences[3 * occurrenceCount + 1] = start;
                        occurrences[3 * occurrenceCount + 2] = size;
                        occurrenceCount++;
                    }
                }
            }
        }
    }

    /** Stops a comparing traversal at its first difference (no stack trace: it is control flow). */
    private static final class Differs extends RuntimeException {
        private static final long serialVersionUID = 1L;

        Differs() {
            super(null, null, false, false);
        }
    }

    /**
     * Runs a node's own traversal against a region of a recording, event by event, and stops at the first difference:
     * the node's traversal is that region exactly when it reaches the region's end with nothing left over. No map is
     * built, so checking a slice costs the node's own traversal and nothing more.
     */
    private final class Comparing implements RecordingVisitor.Sink {
        final int ref;
        final int[] events;
        final int end;
        final Object root;
        int at;
        long visited;
        // the open nodes of this run of the node's own acceptChildren, and whether each one's region is its own
        Object[] openNodes = new Object[32];
        int[] openStarts = new int[32];
        boolean[] openDirect = new boolean[32];
        int depth;
        /** The regions this run proves: {node, start, end} of every node reached through its own acceptChildren. */
        final List<Object[]> proven = new ArrayList<Object[]>();

        Comparing(Object root, int[] slice) {
            this.root = root;
            this.ref = slice[0];
            this.events = references.get(slice[0]);
            this.at = slice[1];
            this.end = slice[2];
        }

        @Override
        public void event(boolean pre, int overload, Object node) {
            if (!pre) {
                if (depth > 0 && openNodes[depth - 1] == node) {
                    depth--;
                    if (openDirect[depth] && node != root) {
                        proven.add(new Object[] {node, Integer.valueOf(openStarts[depth]), Integer.valueOf(at)});
                    }
                    openNodes[depth] = null;
                }
                return;
            }
            visited++;
            if (depth == openNodes.length) {
                openNodes = java.util.Arrays.copyOf(openNodes, depth * 2);
                openStarts = java.util.Arrays.copyOf(openStarts, depth * 2);
                openDirect = java.util.Arrays.copyOf(openDirect, depth * 2);
            }
            openNodes[depth] = node;
            openStarts[depth] = at;
            openDirect[depth] = depth == 0 ? node == root
                    : openDirect[depth - 1] && DirectTraversals.directChild(openNodes[depth - 1], node);
            depth++;
            if (overload < 0) {
                return;
            }
            if (at >= end || events[2 * at] != overload || lives.get(events[2 * at + 1]) != node) {
                throw new Differs();
            }
            at++;
        }
    }

    /**
     * Whether the node's own traversal is the slice: it ends normally, with exactly the slice's events. When it is,
     * the run also proves the regions of the nodes it reached through their own acceptChildren (DirectTraversals):
     * they become exact candidates in the same reference, so their own traversals need not run again.
     */
    private boolean isSlice(Object live, int[] slice) {
        Comparing c = new Comparing(live, slice);
        boolean same;
        try {
            ((gudusoft.gsqlparser.nodes.TParseTreeNode) live).acceptChildren(new RecordingVisitor(c));
            same = c.at == c.end;
        } catch (Throwable t) {
            same = false; // a difference, or a traversal that throws: its own recording keeps how it ends
        }
        traversalStats[3] += c.visited;
        if (same) {
            for (Object[] p : c.proven) {
                Integer inner = handles.get(p[0]);
                if (inner != null && !traversal.containsKey(inner)) {
                    sliceCandidate.put(inner, new int[] {c.ref, ((Integer) p[1]).intValue(),
                        ((Integer) p[2]).intValue(), 1});
                }
            }
        }
        return same;
    }

    private Recording record(Object live) {
        Recording r = new Recording(live);
        try {
            ((gudusoft.gsqlparser.nodes.TParseTreeNode) live).acceptChildren(new RecordingVisitor(r));
        } catch (Throwable t) {
            r.threw = t.getClass().getName();
        }
        return r;
    }

    /** Records the traversal of every projected parse tree node not yet recorded, roots first. */
    private void traverseAll() {
        List<Integer> order = new ArrayList<Integer>(traversalOrder);
        for (int h = 0; h < lives.size(); h++) {
            order.add(Integer.valueOf(h));
        }
        // the roots first: their recordings offer every node inside them its place
        for (Integer h : traversalOrder) {
            traverse(h, false);
        }
        // then every slice, outermost first: checking a node proves the places of the nodes inside it
        List<Integer> sliced = new ArrayList<Integer>();
        for (Integer h : order) {
            if (sliceCandidate.containsKey(h) && !traversal.containsKey(h)) {
                sliced.add(h);
            }
        }
        java.util.Collections.sort(sliced, (x, y) -> {
            int[] a = sliceCandidate.get(x);
            int[] b = sliceCandidate.get(y);
            return a[0] != b[0] ? Integer.compare(a[0], b[0]) : a[1] != b[1] ? Integer.compare(a[1], b[1])
                    : Integer.compare(b[2], a[2]);
        });
        for (Integer h : sliced) {
            traverse(h, true);
        }
        // the rest on their own, the latest found (the deepest) first, for the same reason
        for (int i = order.size() - 1; i >= 0; i--) {
            traverse(order.get(i), false);
        }
    }

    /** The traversal of one node: a slice when its own traversal is one, else (unless {@code slicesOnly}) its own. */
    private void traverse(Integer h, boolean slicesOnly) {
        {
            Object live = lives.get(h.intValue());
            if (traversal.containsKey(h) || !(live instanceof gudusoft.gsqlparser.nodes.TParseTreeNode)) {
                return;
            }
            int[] slice = sliceCandidate.get(h);
            if (slice != null && slice[3] == 1) {
                // its place is its own acceptChildren (Recording): exact without running it again
                traversal.put(h, new int[] {slice[0], slice[1], slice[2]});
                traversalStats[0]++;
                traversalStats[8]++;
                return;
            }
            if (slice != null && !refused.containsKey(h) && isSlice(live, slice)) {
                traversal.put(h, new int[] {slice[0], slice[1], slice[2]});
                traversalStats[0]++;
                return;
            }
            if (slice != null) {
                refused.put(h, Boolean.TRUE);
            }
            if (slicesOnly) {
                return;
            }
            int[] composed = composedList(live);
            if (composed != null) {
                traversal.put(h, composed);
                traversalStats[9]++;
                return;
            }
            traversalStats[slice != null ? 1 : 2]++;
            Recording own = record(live);
            traversalStats[3] += own.visited;
            traversal.put(h, own(h.intValue(), own));
            if (own.threw != null) {
                traversalThrow.put(h, own.threw);
            }
        }
    }

    /** Nodes whose own traversal is not their slice: never checked twice. */
    private final Map<Integer, Boolean> refused = new HashMap<Integer, Boolean>();

    /** The shortest run of a recording kept as another node's traversal rather than copied. */
    private static final int MIN_SHARED = 16;

    /**
     * The pieces ({ref, start, end}...) of a node's own recording. A run of it that is, event for event, the traversal
     * another node already has (the statement list of a long UNION chain repeats the traversal of each statement in
     * it) is kept as that traversal's pieces, not copied: what replays is the same, and the shape does not grow with
     * the square of the chain. The other events become one new reference; a node inside the recording with no
     * traversal yet is offered its place, where its place is a single piece.
     */
    private int[] own(int h, Recording own) {
        int[] events = own.events;
        int n = own.size;
        List<int[]> ranges = new ArrayList<int[]>();
        for (int o = 0; o < own.occurrenceCount; o++) {
            Integer inner = Integer.valueOf(own.occurrences[3 * o]);
            if (inner.intValue() == h || !traversal.containsKey(inner) || traversalThrow.containsKey(inner)) {
                continue;
            }
            ranges.add(new int[] {own.occurrences[3 * o + 1], own.occurrences[3 * o + 2], inner.intValue()});
        }
        // outermost first; a range inside one already kept is part of it
        java.util.Collections.sort(ranges, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0])
                : Integer.compare(y[1], x[1]));
        List<int[]> kept = new ArrayList<int[]>();
        int keptEnd = 0;
        for (int[] r : ranges) {
            if (r[0] >= keptEnd && sameEvents(events, r[0], r[1], traversal.get(Integer.valueOf(r[2])))) {
                kept.add(r);
                keptEnd = r[1];
            }
        }
        int rawCount = n;
        for (int[] r : kept) {
            rawCount -= r[1] - r[0];
        }
        int ref = -1;
        int[] flat = new int[rawCount * 2];
        if (rawCount > 0) {
            ref = references.size();
            references.add(flat);
        }
        // the pieces, in order: raw runs of the new reference and the kept traversals
        List<Integer> pieces = new ArrayList<Integer>();
        int raw = 0;
        int at = 0;
        for (int k = 0; k <= kept.size(); k++) {
            int runEnd = k < kept.size() ? kept.get(k)[0] : n;
            if (runEnd > at) {
                System.arraycopy(events, 2 * at, flat, 2 * raw, 2 * (runEnd - at));
                addPiece(pieces, ref, raw, raw + runEnd - at);
                raw += runEnd - at;
            }
            if (k < kept.size()) {
                int[] t = traversal.get(Integer.valueOf(kept.get(k)[2]));
                for (int i = 0; i < t.length; i += 3) {
                    addPiece(pieces, t[i], t[i + 1], t[i + 2]);
                }
                at = kept.get(k)[1];
            }
        }
        // the places of nodes with no traversal yet: in a raw run, or inside a kept traversal that is one piece
        int[] keptStarts = new int[kept.size()];
        long[] keptBefore = new long[kept.size() + 1];
        for (int k = 0; k < kept.size(); k++) {
            keptStarts[k] = kept.get(k)[0];
            keptBefore[k + 1] = keptBefore[k] + kept.get(k)[1] - kept.get(k)[0];
        }
        for (Map.Entry<Object, int[]> e : own.places.entrySet()) {
            Integer inner = handles.get(e.getKey());
            if (inner == null || inner.intValue() == h || sliceCandidate.containsKey(inner)
                    || traversal.containsKey(inner)) {
                continue;
            }
            int[] place = e.getValue();
            // the last kept range starting at or before the place, and the first one after it
            int k = java.util.Arrays.binarySearch(keptStarts, place[0]);
            k = k >= 0 ? k : -k - 2;
            if (k >= 0 && kept.get(k)[1] > place[0]) {
                int[] within = kept.get(k);
                if (place[1] > within[1]) {
                    continue; // starts inside a kept range and ends past it
                }
                int[] t = traversal.get(Integer.valueOf(within[2]));
                if (t.length == 3) {
                    sliceCandidate.put(inner, new int[] {t[0], t[1] + place[0] - within[0],
                        t[1] + place[1] - within[0], place[2]});
                }
                continue;
            }
            if (k + 1 < kept.size() && kept.get(k + 1)[0] < place[1]) {
                continue; // a kept range lies inside it: not one run of the new reference
            }
            if (ref >= 0) { // with no raw events the place is empty and the node is recorded on its own
                int before = (int) keptBefore[k + 1];
                sliceCandidate.put(inner, new int[] {ref, place[0] - before, place[1] - before, place[2]});
            }
        }
        int[] out = new int[pieces.size()];
        for (int i = 0; i < out.length; i++) {
            out[i] = pieces.get(i).intValue();
        }
        return out;
    }

    /**
     * The traversal of a list whose acceptChildren is the list classes' own (DirectTraversals.isListTraversal): its
     * elements' traversals in order, made without running it; null when an element has no traversal yet, its traversal
     * throws, or (a statement list) an element is null, or the list's own preVisit is one a producer visitor overrides.
     */
    private int[] composedList(Object live) {
        if (!DirectTraversals.isListTraversal(live) || DirectTraversals.LIST_OVERLOAD_RELEVANT) {
            return null;
        }
        List<Object> elements = DirectTraversals.elements(live);
        if (elements == null) {
            return null;
        }
        List<Integer> pieces = new ArrayList<Integer>();
        for (Object element : elements) {
            Integer e = handles.get(element);
            int[] t = e == null ? null : traversal.get(e);
            if (t == null || traversalThrow.containsKey(e)) {
                return null;
            }
            for (int i = 0; i < t.length; i += 3) {
                addPiece(pieces, t[i], t[i + 1], t[i + 2]);
            }
        }
        int[] out = new int[pieces.size()];
        for (int i = 0; i < out.length; i++) {
            out[i] = pieces.get(i).intValue();
        }
        return out;
    }

    /** Appends a piece, joined to the last one when it continues it in the same reference. */
    private static void addPiece(List<Integer> pieces, int ref, int start, int end) {
        if (end <= start) {
            return;
        }
        int size = pieces.size();
        if (size >= 3 && pieces.get(size - 3).intValue() == ref && pieces.get(size - 1).intValue() == start) {
            pieces.set(size - 1, Integer.valueOf(end));
            return;
        }
        pieces.add(Integer.valueOf(ref));
        pieces.add(Integer.valueOf(start));
        pieces.add(Integer.valueOf(end));
    }

    /** Whether events [start, end) of a recording are exactly the events of a traversal's pieces. */
    private boolean sameEvents(int[] events, int start, int end, int[] pieces) {
        int length = 0;
        for (int i = 0; i < pieces.length; i += 3) {
            length += pieces[i + 2] - pieces[i + 1];
        }
        if (length != end - start) {
            return false;
        }
        int at = start;
        for (int i = 0; i < pieces.length; i += 3) {
            int[] ref = references.get(pieces[i]);
            for (int j = pieces[i + 1]; j < pieces[i + 2]; j++, at++) {
                if (events[2 * at] != ref[2 * j] || events[2 * at + 1] != ref[2 * j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }

    // ---------------------------------------------------------------------------------------------
    // The mirrors
    // ---------------------------------------------------------------------------------------------

    private void build() {
        int n = lives.size();
        String[] names = new String[n];
        String[] simple = new String[n];
        int[][] tPieces = new int[n][];
        String[] tThrow = new String[n];
        for (int h = 0; h < n; h++) {
            names[h] = lives.get(h).getClass().getName();
            simple[h] = lives.get(h).getClass().getSimpleName();
            int[] t = traversal.get(Integer.valueOf(h));
            tPieces[h] = t;
            tThrow[h] = traversalThrow.get(Integer.valueOf(h));
            if (t == null && lives.get(h) instanceof gudusoft.gsqlparser.nodes.TParseTreeNode) {
                throw new IllegalStateException("no traversal for " + names[h]);
            }
        }
        shape = new Shape(n, names, simple, references.toArray(new int[0][]), tPieces, tThrow, root, catalogRoot);
        // mirrors a public field refers to are made first
        for (int pass = 0; pass < 2; pass++) {
            for (int h = 0; h < n; h++) {
                int k = kinds.get(h).intValue();
                if ((k != OPAQUE && ShapeKinds.FIELD_TARGET[k]) == (pass == 0)) {
                    shape.objects[h] = make(k, h);
                }
            }
        }
    }

    private ShapeObject make(int k, int h) {
        Object v = values.get(h);
        if (k == OPAQUE) {
            return new LiveObject(shape, h);
        }
        if (k == kRecorder) {
            return new SqllrObservations(shape, h, (Object[]) v, frozenColumns, structItems);
        }
        if (k == kElement) {
            return new SqllrObservations.ElementRecord(shape, h, (Object[]) v);
        }
        if (k == kReference) {
            return new SqllrObservations.ReferenceRecord(shape, h, (Object[]) v);
        }
        if (k == kStatementRecord) {
            return new SqllrObservations.StatementRecord(shape, h, (Object[]) v);
        }
        if (k == kUnit) {
            return new SqllrObservations.UnitRecord(shape, h, (Object[]) v);
        }
        if (k == kDerived) {
            return new SqllrObservations.DerivedRecord(shape, h, (Object[]) v);
        }
        if (k == kFrozen) {
            return new SqllrObservations.FrozenRelation(shape, h, (Object[]) v);
        }
        return ShapeKinds.create(k, shape, h, (Object[][]) v);
    }

    /**
     * Takes the text renderings, after the analysis has finished and before it is disposed (when the producer took
     * them before slice 1b), seals the shape and drops every live object.
     */
    public Shape complete() {
        return complete(false);
    }

    /**
     * {@link #complete()}; with {@code keepLive} the live objects stay until {@link #release} (tests compare the
     * mirrors with them).
     */
    public Shape complete(boolean keepLive) {
        long started = System.nanoTime();
        for (int h = 0; h < lives.size(); h++) {
            Object live = lives.get(h);
            int k = kinds.get(h).intValue();
            if (k == OPAQUE) {
                continue;
            }
            if (rendered(live)) {
                try {
                    shape.putRendering(h, live.toString());
                } catch (RuntimeException e) {
                    shape.putRendering(h, "\u0000" + e.getClass().getName());
                }
            }
            for (String member : ShapeKinds.renderMembers(k)) {
                try {
                    shape.putMemberRendering(h, member, ShapeKinds.renderMember(live, member));
                } catch (RuntimeException e) {
                    shape.putMemberRendering(h, member, "\u0000" + e.getClass().getName());
                }
            }
        }
        shape.setCompleteNanos(System.nanoTime() - started);
        shape.seal();
        if (!keepLive) {
            release();
        }
        return shape;
    }

    /** Drops every live object. */
    public void release() {
        lives.clear();
        handles.clear();
    }

    /** Tests only: the live object of handle {@code h}, until {@link #release}. */
    Object live(int h) {
        return lives.get(h);
    }

    /** Tests only: the handle of a live object, or -1. */
    int handleOf(Object live) {
        Integer h = handles.get(live);
        return h == null ? -1 : h.intValue();
    }

    /** Names, constants, type names and the leaf expressions the producer shows (a literal, a variable). */
    private static boolean rendered(Object live) {
        if (live instanceof gudusoft.gsqlparser.nodes.TObjectName || live instanceof gudusoft.gsqlparser.nodes.TConstant
                || live instanceof gudusoft.gsqlparser.nodes.TTypeName) {
            return true;
        }
        if (live instanceof gudusoft.gsqlparser.nodes.TExpression) {
            EExpressionType t = ((gudusoft.gsqlparser.nodes.TExpression) live).getExpressionType();
            return t == EExpressionType.simple_constant_t || t == EExpressionType.simple_object_name_t;
        }
        return false;
    }

    /** The shape made at the freeze (renderings come with {@link #complete}). */
    public Shape shape() {
        return shape;
    }
}