Dépôt officiel du code source de l'ERP OpenConcerto

/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

 *

 * Copyright 2011-2019 OpenConcerto, by ILM Informatique. All rights reserved.

 *

 * The contents of this file are subject to the terms of the GNU General Public License Version 3

 * only ("GPL"). You may not use this file except in compliance with the License. You can obtain a

 * copy of the License at http://www.gnu.org/licenses/gpl-3.0.html See the License for the specific

 * language governing permissions and limitations under the License.

 *

 * When distributing the software, include this License Header Notice in each file.

 */

 package org.openconcerto.sql.model;

import org.openconcerto.sql.model.SQLRowValues.CreateMode;

import org.openconcerto.sql.model.SQLRowValues.FillMode;

import org.openconcerto.sql.model.SQLRowValues.ForeignCopyMode;

import org.openconcerto.sql.model.SQLRowValues.ReferentChangeEvent;

import org.openconcerto.sql.model.SQLRowValues.ReferentChangeListener;

import org.openconcerto.sql.model.graph.Link.Direction;

import org.openconcerto.sql.model.graph.Path;

import org.openconcerto.sql.model.graph.Step;

import org.openconcerto.sql.utils.SQLUtils;

import org.openconcerto.utils.CollectionMap2.Mode;

import org.openconcerto.utils.CollectionUtils;

import org.openconcerto.utils.CompareUtils;

import org.openconcerto.utils.Matrix;

import org.openconcerto.utils.RecursionType;

import org.openconcerto.utils.SetMap;

import org.openconcerto.utils.StringUtils;

import org.openconcerto.utils.StringUtils.Side;

import org.openconcerto.utils.cc.Closure;

import org.openconcerto.utils.cc.IClosure;

import org.openconcerto.utils.cc.ITransformer;

import org.openconcerto.utils.cc.IdentityHashSet;

import org.openconcerto.utils.cc.IdentitySet;

import java.sql.SQLException;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Collections;

import java.util.Comparator;

import java.util.EventObject;

import java.util.HashSet;

import java.util.IdentityHashMap;

import java.util.Iterator;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.Map;

import java.util.Map.Entry;

import java.util.Set;

import java.util.concurrent.atomic.AtomicInteger;

import net.jcip.annotations.Immutable;

/**

 * A set of linked SQLRowValues.

 *

 * @author Sylvain

 */

public class SQLRowValuesCluster {

    private static final Comparator<SQLField> FIELD_COMPARATOR = new Comparator<SQLField>() {

        @Override

        public int compare(SQLField o1, SQLField o2) {

            return o1.getSQLName().quote().compareTo(o2.getSQLName().quote());

        }

    };

    /**

     * The list of links in the order they've been set. This allows deterministic and predictable

     * insertion order. E.g. for

     *

     * <pre>

     * r2.put(f, r1);

     * r3.put(f2, r2);

     * r4.put(f2, r2);

     * </pre>

     *

     * the links will be :

     *

     * <pre>

     * r1

     * r2 f r1

     * r3 f2 r2

     * r4 f2 r2

     * </pre>

     */

    private final List<Link> links;

    private final IdentitySet<SQLRowValues> items;

    // { vals -> listener on vals' graph }

    private Map<SQLRowValues, List<ValueChangeListener>> listeners;

    private boolean frozen = false;

    private SQLRowValuesCluster() {

        this.links = new ArrayList<Link>();

        // SQLRowValues equals() depends on their values, but we must tell apart each reference

        this.items = new IdentityHashSet<SQLRowValues>();

        this.listeners = null;

    }

    SQLRowValuesCluster(SQLRowValues vals) {

        this();

        addVals(-1, vals);

    }

    // add a lonely node to this

    private final void addVals(final int index, final SQLRowValues vals) {

        assert vals.getGraph(false) == null;

        if (index < 0)

            this.links.add(new Link(vals));

        else

            this.links.add(index, new Link(vals));

        this.items.add(vals);

    }

    private final SQLRowValues getHead() {

        return this.links.get(0).getSrc();

    }

    private final DBSystemRoot getSystemRoot() {

        return this.getHead().getTable().getDBSystemRoot();

    }

    public final int getLinksCount() {

        return this.links.size();

    }

    /**

     * All the rowValues in this cluster.

     *

     * @return the set of SQLRowValues.

     */

    public final Set<SQLRowValues> getItems() {

        return Collections.unmodifiableSet(this.items);

    }

    /**

     * The number of items in this instance. NOTE: calling {@link SQLRowValues#getGraphSize()} is

     * preferable since it might avoid an allocation.

     *

     * @return the number of items.

     */

    public final int size() {

        return this.items.size();

    }

    public final boolean contains(SQLRowValues start) {

        return this.items.contains(start);

    }

    private final void containsCheck(SQLRowValues vals) {

        if (!this.contains(vals))

            throw new IllegalArgumentException(vals + " not in " + this);

    }

    // if true a single link path passed to followPath() will never yield more than one row

    final boolean hasOneRowPerPath() {

        for (final SQLRowValues item : this.getItems()) {

            for (final Entry<SQLField, Set<SQLRowValues>> e : item.getReferents().entrySet()) {

                if (e.getValue().size() > 1)

                    return false;

            }

        }

        return true;

    }

    public final Set<SQLTable> getTables() {

        final Set<SQLTable> res = new HashSet<SQLTable>();

        for (final SQLRowValues v : this.items)

            res.add(v.getTable());

        return res;

    }

    public final boolean isFrozen() {

        return this.frozen;

    }

    /**

     * Freeze this graph so that no modification can be made. Once this method returns, this

     * instance can be safely published (e.g. stored into a field that is properly guarded by a

     * lock) to other threads without further synchronizations.

     *

     * @return <code>true</code> if this call changed the frozen status.

     */

    public final boolean freeze() {

        if (this.frozen)

            return false;

        this.frozen = true;

        return true;

    }

    void remove(SQLRowValues src, SQLField f, SQLRowValues dest) {

        assert dest != null;

        assert src.getGraph() == this;

        assert src.getTable() == f.getTable();

        assert !this.isFrozen() : "Should already be checked by SQLRowValues";

        final Link toRm = new Link(src, f, dest);

        this.links.remove(toRm);

        // test if the removal of the link split the graph

        final IdentitySet<SQLRowValues> reachable = this.getReachable(src);

        if (reachable.size() < this.size()) {

            final SQLRowValuesCluster newCluster = new SQLRowValuesCluster();

            // moves the links no longer in us into a new cluster

            final Iterator<Link> iter = this.links.iterator();

            while (iter.hasNext()) {

                final Link l = iter.next();

                // the graph is split in two, so every link is in one part

                assert l.getDest() == null || reachable.contains(l.getSrc()) == reachable.contains(l.getDest());

                // hence only test the source

                if (!reachable.contains(l.getSrc())) {

                    iter.remove();

                    newCluster.links.add(l);

                }

            }

            // move unreachable items

            assert newCluster.items.isEmpty();

            final Iterator<SQLRowValues> itemIter = this.items.iterator();

            while (itemIter.hasNext()) {

                final SQLRowValues key = itemIter.next();

                if (!reachable.contains(key)) {

                    itemIter.remove();

                    newCluster.items.add(key);

                    if (this.listeners != null && this.listeners.containsKey(key))

                        newCluster.getListeners().put(key, this.listeners.remove(key));

                }

            }

            // http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6612102

            // resolved in 7b25 : iterator.remove() might decrement the size twice : e.g. size is 0

            // and thus isEmpty() is true, while there's still elements in this.items

            assert !this.items.isEmpty() : "Empty items while removing " + f + " -> " + dest + " from " + src;

            assert !newCluster.items.isEmpty() : "New graph is empty while removing " + f + " -> " + dest + " from " + src;

            assert !CollectionUtils.containsAny(this.items, newCluster.items) : "Shared items while removing " + f + " -> " + dest + " from " + src;

            for (final SQLRowValues vals : newCluster.getItems())

                vals.setGraph(newCluster);

        }

    }

    void add(SQLRowValues src, SQLField f, SQLRowValues dest) {

        assert dest != null;

        assert src.getTable() == f.getTable();

        assert !this.isFrozen() : "Should already be checked by SQLRowValues";

        final boolean containsSrc = this.contains(src);

        final boolean containsDest = this.contains(dest);

        if (!containsSrc && !containsDest)

            throw new IllegalArgumentException("Neither source nor destination are contained in this :\n" + src + "\n" + dest);

        final Link toAdd = new Link(src, f, dest);

        if (containsSrc && containsDest) {

            // both source and dest are in us

            this.links.add(toAdd);

        } else {

            assert src.getGraph(false) != dest.getGraph(false);

            final SQLRowValues rowToAdd;

            final int index;

            if (containsSrc) {

                rowToAdd = dest;

                // merge the two graphs

                // add dest before src since it will be needed to store us (adding at the end would

                // work, but src would need to be inserted, then updated)

                // add dest just before src, to keep the order of foreigns (needed for deepCopy()

                // and insertion order) (adding at the beginning would reverse the order of foreign

                // rows to insert)

                final int srcIndex = this.links.indexOf(new Link(src));

                if (srcIndex < 0)

                    throw new IllegalStateException("Source link not found for " + src);

                index = srcIndex;

            } else {

                assert containsDest;

                rowToAdd = src;

                index = -1;

            }

            final SQLRowValuesCluster graphToAdd = rowToAdd.getGraph(false);

            // to preserve memory a single node has no graph unless required

            // this way rowToAdd never had to create a Cluster, it will use us.

            if (graphToAdd == null) {

                this.addVals(index, rowToAdd);

                rowToAdd.setGraph(this);

            } else {

                if (index < 0)

                    this.links.addAll(graphToAdd.links);

                else

                    this.links.addAll(index, graphToAdd.links);

                graphToAdd.links.clear();

                this.items.addAll(graphToAdd.items);

                for (final SQLRowValues newlyAdded : graphToAdd.items) {

                    newlyAdded.setGraph(this);

                }

                graphToAdd.items.clear();

                if (graphToAdd.listeners != null) {

                    this.getListeners().putAll(graphToAdd.listeners);

                    graphToAdd.listeners = null;

                }

            }

            // To keep foreign links order, new links should be added after existing ones from src

            // (which are after srcIndex). Since they're merged in store(), just add at the end.

            this.links.add(toAdd);

        }

        assert src.getGraph() == dest.getGraph();

    }

    private IdentitySet<SQLRowValues> getReachable(final SQLRowValues from) {

        final IdentitySet<SQLRowValues> res = new IdentityHashSet<SQLRowValues>();

        getReachableRec(from, res);

        return res;

    }

    private void getReachableRec(final SQLRowValues from, final IdentitySet<SQLRowValues> acc) {

        if (!acc.add(from))

            return;

        for (final SQLRowValues fVals : from.getForeigns().values()) {

            this.getReachableRec(fVals, acc);

        }

        for (final SQLRowValues fVals : from.getReferentRows()) {

            this.getReachableRec(fVals, acc);

        }

    }

    final SQLRowValues deepCopy(SQLRowValues v, final boolean freeze) {

        return deepCopy(freeze).get(v);

    }

    public final Map<SQLRowValues, SQLRowValues> deepCopy(final boolean freeze) {

        return this.copy(null, false, freeze);

    }

    /**

     * Copy a subset of this graph. For each link to copy, if the destination was copied then the

     * new row will point to it, otherwise the new row will point to the original row. For example,

     * if

     *

     * <pre>

     * start is CONTAINER <-- *ITEM [F1, F2]* --> PRIVATE

     * and graph is ITEM [F2, ID_PRIVATE]

     * then after this method :

     *  CONTAINER <-- ITEM [F1, F2] --> PRIVATE

     *            \-- ITEM [F2]     --> PRIVATE

     * </pre>

     *

     * @param start where to start copying.

     * @param graph which rows and which fields to copy, not <code>null</code>.

     * @return the new rows, indexed by the original rows in this instance.

     */

    public final Map<SQLRowValues, SQLRowValues> copy(final SQLRowValues start, final SQLRowValues graph) {

        return this.copy(computeToRetain(start, graph, true), true, false);

    }

    /**

     * Copy rows of this graph.

     *

     * @param subset which rows and which fields to copy, <code>null</code> to copy all rows.

     * @param allowSameGraph used when copied rows point to rows which weren't copied,

     *        <code>true</code> to point to the original rows (and thus linking the new rows into

     *        the existing graph), <code>false</code> to flatten the link (like

     *        {@link ForeignCopyMode#COPY_ID_OR_RM}).

     * @param freeze <code>true</code> if the copied rows should be frozen.

     * @return the new rows, indexed by the original rows in this instance.

     */

    private final Map<SQLRowValues, SQLRowValues> copy(final SetMap<SQLRowValues, String> subset, final boolean allowSameGraph, final boolean freeze) {

        assert !allowSameGraph || !freeze;

        // copy all rowValues of this graph

        final Map<SQLRowValues, SQLRowValues> noLinkCopy = new IdentityHashMap<SQLRowValues, SQLRowValues>();

        // don't copy foreigns, but we want to preserve the order of all fields. This works because

        // the second put() with the actual foreign row doesn't change the order.

        final ForeignCopyMode copyMode = ForeignCopyMode.COPY_NULL;

        for (final SQLRowValues n : this.getItems()) {

            final SQLRowValues copy;

            if (subset == null || subset.containsKey(n)) {

                // might as well use the minimum memory if the values won't change

                if (freeze) {

                    copy = new SQLRowValues(n.getTable(), n.size(), n.getForeignsSize(), n.getReferents().size());

                    copy.setAll(n.getAllValues(copyMode));

                } else {

                    copy = new SQLRowValues(n, copyMode);

                    if (subset != null) {

                        copy.retainAll(subset.get(n));

                    }

                }

                noLinkCopy.put(n, copy);

            }

        }

        // and link them together in order

        final List<Link> iterableLinks = subset == null ? this.links : new ArrayList<Link>(this.links);

        for (final Link l : iterableLinks) {

            if (l.getField() != null) {

                final SQLRowValues sourceCopy = noLinkCopy.get(l.getSrc());

                if (subset == null || (sourceCopy != null && sourceCopy.contains(l.getField().getName()))) {

                    assert l.getDest() != null;

                    final SQLRowValues destCopy = noLinkCopy.get(l.getDest());

                    final Object dest;

                    if (destCopy != null)

                        dest = destCopy;

                    else if (allowSameGraph)

                        dest = l.getDest();

                    else if (l.getDest().hasID())

                        dest = l.getDest().getIDNumber();

                    else

                        dest = null;

                    if (dest != null) {

                        sourceCopy.put(l.getField().getName(), dest);

                    } else {

                        // ForeignCopyMode.COPY_ID_OR_RM like pruneWithoutCopy() (avoids

                        // leaving nulls)

                        sourceCopy.remove(l.getField().getName());

                    }

                }

            } else {

                assert subset != null || noLinkCopy.containsKey(l.getSrc());

            }

        }

        final SQLRowValues res = noLinkCopy.values().iterator().next();

        // only force graph creation if needed

        if (freeze)

            res.getGraph().freeze();

        assert res.isFrozen() == freeze;

        assert allowSameGraph || res.getGraph() != this;

        return noLinkCopy;

    }

    public final StoreResult insert() throws SQLException {

        return this.store(StoreMode.INSERT);

    }

    public final StoreResult store(final StoreMode mode) throws SQLException {

        return this.store(mode, null);

    }

    // checkValidity false useful when we want to avoid loading the graph

    public final StoreResult store(final StoreMode mode, final Boolean checkValidity) throws SQLException {

        return this.store(mode, null, null, checkValidity, true);

    }

    /**

     * Store this graph into the DB.

     *

     * @param mode how to store.

     * @param start when storing a subset, the start of <code>pruneGraph</code> in this, can be

     *        <code>null</code>.

     * @param pruneGraph the maximum graph to store, can be <code>null</code>.

     * @param checkValidity whether to {@link SQLRowValues#getInvalid() checking validity} of rows,

     *        see {@link SQLRowValues#setValidityChecked(SQLRowValues.ValidityCheck)}.

     * @param fireEvent <code>false</code> if stored rows shouldn't be fetched and

     *        {@link SQLTableEvent} should not be fired.

     * @return the store result.

     * @throws SQLException if an exception occurs.

     * @see {@link #prune(SQLRowValues, SQLRowValues)}

     */

    public final StoreResult store(final StoreMode mode, final SQLRowValues start, final SQLRowValues pruneGraph, final Boolean checkValidity, final boolean fireEvent) throws SQLException {

        final Map<SQLRowValues, SQLRowValues> prune2orig;

        final SQLRowValuesCluster toStore;

        final boolean prune = pruneGraph != null;

        if (!prune) {

            toStore = this;

            prune2orig = null;

        } else {

            final Map<SQLRowValues, SQLRowValues> orig2prune = this.pruneMap(start, pruneGraph, true);

            toStore = orig2prune.get(start).getGraph();

            prune2orig = CollectionUtils.invertMap(new IdentityHashMap<SQLRowValues, SQLRowValues>(), orig2prune);

        }

        final Map<SQLRowValues, Node> nodes = new IdentityHashMap<SQLRowValues, Node>(toStore.size());

        final Map<SQLRowValues, Node> res = prune ? new IdentityHashMap<SQLRowValues, Node>(toStore.size()) : nodes;

        for (final SQLRowValues vals : toStore.getItems()) {

            nodes.put(vals, new Node(vals));

            if (prune) {

                final SQLRowValues src = prune2orig.get(vals);

                assert this.contains(src);

                res.put(src, nodes.get(vals));

            }

        }

        // check validity first, avoid beginning a transaction for nothing

        // do it after reset otherwise check previous values

        if (SQLRowValues.isValidityChecked(checkValidity))

            for (final Node n : nodes.values()) {

                n.noLink.checkValidity();

            }

        // this will hold the links and their ID as they are known

        /**

         * A cycle example :

         *

         * <pre>

         * s null

         * c ID_SITE s

         * c null

         * s ID_CONTACT_RAPPORT c

         * s ID_CONTACT_UTILE c

         * </pre>

         *

         * First s will be inserted :

         *

         * <pre>

         * c ID_SITE sID

         * c null

         * s ID_CONTACT_RAPPORT c

         * s ID_CONTACT_UTILE c

         * </pre>

         *

         * Then c :

         *

         * <pre>

         * s ID_CONTACT_RAPPORT cID

         * s ID_CONTACT_UTILE cID

         * </pre>

         *

         * And finally, s will be updated.

         */

        final List<StoringLink> storingLinks = new ArrayList<StoringLink>(toStore.links.size());

        for (final Link l : toStore.links)

            storingLinks.add(new StoringLink(l));

        // store the whole graph atomically

        final List<SQLTableEvent> events = SQLUtils.executeAtomic(getSystemRoot().getDataSource(), new ConnectionHandlerNoSetup<List<SQLTableEvent>, SQLException>() {

            @Override

            public List<SQLTableEvent> handle(SQLDataSource ds) throws SQLException {

                final List<SQLTableEvent> res = new ArrayList<SQLTableEvent>();

                while (storingLinks.size() > 0) {

                    final StoringLink toStore = storingLinks.remove(0);

                    if (!toStore.canStore())

                        throw new IllegalStateException();

                    final Node n = nodes.get(toStore.getSrc());

                    // merge the maximum of links starting from the row to be stored

                    boolean lastDBAccess = true;

                    final Iterator<StoringLink> iter = storingLinks.iterator();

                    while (iter.hasNext()) {

                        final StoringLink sl = iter.next();

                        if (sl.getSrc() == toStore.getSrc()) {

                            if (sl.canStore()) {

                                iter.remove();

                                // sl can either be the main row or one the link from the row

                                // (bear in mind that toStore can be not the main row if the link

                                // destination has already been inserted)

                                if (sl.destID != null)

                                    n.noLink.put(sl.getField().getName(), sl.destID);

                            } else {

                                lastDBAccess = false;

                            }

                        }

                    }

                    if (n.isStored()) {

                        // if there's a cycle, we have to update an already inserted row

                        res.add(n.update(fireEvent));

                    } else {

                        res.add(n.store(fireEvent, mode));

                        final SQLRow r = n.getStoredRow();

                        // fill the noLink of referent nodes with the new ID

                        for (final StoringLink sl : storingLinks) {

                            if (sl.getDest() == toStore.getSrc()) {

                                sl.destID = r.getIDNumber();

                                nodes.get(sl.getSrc()).noLink.put(sl.getField().getName(), r.getIDNumber());

                            }

                        }

                    }

                    // link together the new values

                    // if there is a cycle not all foreign keys can be stored at the same time, so

                    // wait for the last DB access

                    if (lastDBAccess) {

                        for (final Map.Entry<String, SQLRowValues> e : toStore.getSrc().getForeigns().entrySet()) {

                            final SQLRowValues foreign = nodes.get(e.getValue()).getStoredValues();

                            assert foreign != null : "since this the last db access for this row, all foreigns should have been inserted";

                            // check coherence

                            if (n.getStoredValues().getLong(e.getKey()) != foreign.getIDNumber().longValue())

                                throw new IllegalStateException("stored " + n.getStoredValues().getObject(e.getKey()) + " but foreign is " + SQLRowValues.trim(foreign));

                            n.getStoredValues().put(e.getKey(), foreign);

                        }

                    }

                }

                // all nodes share the same graph, so pick any and freeze the graph

                // null if !fireEvent or if non-rowable table

                final SQLRowValues graphFetched = nodes.values().iterator().next().getStoredValues();

                if (graphFetched != null)

                    graphFetched.getGraph().freeze();

                return res;

            }

        });

        // fire events

        if (fireEvent) {

            for (final SQLTableEvent n : events) {

                // MAYBE put a Map<SQLRowValues, SQLTableEvent> to know how our fellow values have

                // been affected

                n.getTable().fire(n);

            }

        }

        return new StoreResult(res);

    }

    static public final class WalkOptions {

        private final Direction direction;

        private RecursionType recType;

        private boolean allowCycle;

        private boolean includeStart;

        private boolean ignoreForeignsOrder;

        public WalkOptions(final Direction dir) {

            if (dir == null)

                throw new NullPointerException("No direction");

            this.direction = dir;

            this.recType = RecursionType.BREADTH_FIRST;

            this.allowCycle = false;

            this.includeStart = true;

            this.ignoreForeignsOrder = true;

        }

        public Direction getDirection() {

            return this.direction;

        }

        public RecursionType getRecursionType() {

            return this.recType;

        }

        public WalkOptions setRecursionType(RecursionType recType) {

            if (recType == null)

                throw new NullPointerException("No type");

            this.recType = recType;

            return this;

        }

        public boolean isCycleAllowed() {

            return this.allowCycle;

        }

        /**

         * Set whether cycles (encountering the same row twice) are allowed. If <code>false</code>

         * is passed, then steps that go back to already visited rows will never be crossed :

         *

         * <pre>

         *       /- ID_CONTACT_RAPPORT \

         *  SITE -- ID_CONTACT_CHEF ---> CONTACT

         *       \-     ID_SITE        /

         * </pre>

         *

         * The SITE will only be passed once and ID_SITE would never be crossed from CONTACT. To go

         * through all paths, pass <code>true</code> and SITE will be visited 3 times if

         * {@link Direction#FOREIGN} and 7 times if {@link Direction#ANY}. Note that in both cases,

         * CONTACT will be visited 3 times if {@link Direction#ANY} and twice if

         * {@link Direction#FOREIGN}.

         *

         * @param allowCycle <code>true</code> if {@link State#getValsPath()} can contains the same

         *        row twice, <code>false</code> to stop before that happens.

         * @return this.

         */

        public WalkOptions setCycleAllowed(boolean allowCycle) {

            this.allowCycle = allowCycle;

            return this;

        }

        public boolean isStartIncluded() {

            return this.includeStart;

        }

        public WalkOptions setStartIncluded(boolean includeStart) {

            this.includeStart = includeStart;

            return this;

        }

        public boolean isForeignsOrderIgnored() {

            return this.ignoreForeignsOrder;

        }

        public WalkOptions setForeignsOrderIgnored(boolean ignoreForeignsOrder) {

            this.ignoreForeignsOrder = ignoreForeignsOrder;

            return this;

        }

    }

    /**

     * Walk the graph from the passed node, executing the closure for each node on the path. NOTE

     * that this method only goes one way through foreign keys, ie if this cluster is a tree and

     * <code>start</code> is not the root, some nodes will not be traversed.

     *

     * @param <T> type of acc

     * @param start where to start the walk.

     * @param acc the initial value.

     * @param closure what to do on each node.

     */

    public final <T> void walk(final SQLRowValues start, T acc, ITransformer<State<T>, T> closure) {

        this.walk(start, acc, closure, RecursionType.BREADTH_FIRST);

    }

    /**

     * Walk the graph from the passed node, executing the closure for each node on the path. NOTE

     * that this method only goes one way through foreign keys, ie if this cluster is a tree and

     * <code>start</code> is not the root, some nodes will not be traversed. Also you can stop the

     * recursion by throwing {@link StopRecurseException} in <code>closure</code>.

     *

     * @param <T> type of acc

     * @param start where to start the walk.

     * @param acc the initial value.

     * @param closure what to do on each node.

     * @param recType how to recurse.

     * @return the exception that stopped the recursion, <code>null</code> if none was thrown.

     */

    public final <T> StopRecurseException walk(final SQLRowValues start, T acc, ITransformer<State<T>, T> closure, RecursionType recType) {

        return this.walk(start, acc, closure, recType, Direction.FOREIGN);

    }

    public final <T> StopRecurseException walk(final SQLRowValues start, T acc, ITransformer<State<T>, T> closure, RecursionType recType, final Direction foreign) {

        return this.walk(start, acc, closure, new WalkOptions(foreign).setRecursionType(recType));

    }

    public final <T> StopRecurseException walk(final SQLRowValues start, T acc, ITransformer<State<T>, T> closure, final WalkOptions options) {

        this.containsCheck(start);

        return this.walk(new State<T>(Collections.singletonList(start), Path.get(start.getTable()), acc, closure), options, options.isStartIncluded());

    }

    /**

     * Walk through the graph from the passed state. NOTE: this method will call the {@link State}

     * with each path a row can be reached (except if this would cause a cycle, see

     * {@link WalkOptions#setCycleAllowed(boolean)}). E.g. for :

     *

     * <pre>

     *  SITE -- ID_CONTACT_CHEF ---> CONTACT -- ID_TITLE ---> TITLE

     *       \- ID_CONTACT_RAPPORT /

     * </pre>

     *

     * The CONTACT and TITLE will be passed twice, once for each link.

     *

     * @param <T> type of acc.

     * @param state the current position in the graph.

     * @param options how to walk the graph.

     * @param computeThisState <code>false</code> if the <code>state</code> should not be

     *        {@link State#compute() computed}.

     * @return the exception that stopped the recursion, <code>null</code> if none was thrown.

     */

    private final <T> StopRecurseException walk(final State<T> state, final WalkOptions options, final boolean computeThisState) {

        if (computeThisState && options.getRecursionType() == RecursionType.BREADTH_FIRST) {

            final StopRecurseException e = state.compute();

            if (e != null)

                return e;

        }

        if (!options.isCycleAllowed() || !state.hasCycle()) {

            // get the foreign or referents rowValues

            StopRecurseException res = null;

            if (options.getDirection() != Direction.REFERENT) {

                res = rec(state, options, Direction.FOREIGN);

            }

            if (res != null)

                return res;

            if (options.getDirection() != Direction.FOREIGN) {

                res = rec(state, options, Direction.REFERENT);

            }

            if (res != null)

                return res;

        }

        if (computeThisState && options.getRecursionType() == RecursionType.DEPTH_FIRST) {

            final StopRecurseException e = state.compute();

            if (e != null)

                return e;

        }

        return null;

    }

    private <T> StopRecurseException rec(final State<T> state, final WalkOptions options, final Direction actualDirection) {

        final SQLRowValues current = state.getCurrent();

        final List<SQLRowValues> currentValsPath = state.getValsPath();

        final SetMap<SQLField, SQLRowValues> nextVals;

        if (actualDirection == Direction.FOREIGN) {

            final Map<SQLField, SQLRowValues> foreigns = current.getForeignsBySQLField();

            nextVals = new SetMap<SQLField, SQLRowValues>(new LinkedHashMap<SQLField, Set<SQLRowValues>>(foreigns.size()), Mode.NULL_FORBIDDEN);

            nextVals.mergeScalarMap(foreigns);

        } else {

            assert actualDirection == Direction.REFERENT;

            nextVals = current.getReferents();

        }

        // predictable and repeatable order (SQLRowValues.referents has no order, but .foreigns has)

        final List<SQLField> keys = new ArrayList<SQLField>(nextVals.keySet());

        if (actualDirection == Direction.REFERENT || options.isForeignsOrderIgnored())

            Collections.sort(keys, FIELD_COMPARATOR);

        for (final SQLField f : keys) {

            final Step step = Step.create(f, actualDirection);

            // we must never go back from where we came

            final boolean backtrack = state.getPath().length() > 0 && state.getPath().getStep(-1).equals(step.reverse());

            for (final SQLRowValues v : nextVals.getNonNull(f)) {

                // backtrack is not enough, there can be other referents than previous

                // avoid infinite loop (don't use equals so that we can go over several equals rows)

                if (!(backtrack && v == state.getPrevious()) && (options.isCycleAllowed() || !state.identityContains(v))) {

                    final Path path = state.getPath().add(step);

                    final List<SQLRowValues> valsPath = new ArrayList<SQLRowValues>(currentValsPath);

                    valsPath.add(v);

                    final StopRecurseException e = this.walk(new State<T>(Collections.unmodifiableList(valsPath), path, state.getAcc(), state.closure), options, true);

                    if (e != null && e.isCompletely())

                        return e;

                }

            }

        }

        return null;

    }

    @Immutable

    static public final class IndexedRows {

        private final List<State<?>> flatList;

        private final Map<SQLRowValues, Integer> indexes;

        // optimization

        private IndexedRows(final SQLRowValues sole) {

            this(Collections.<State<?>> singletonList(new State<Object>(Collections.singletonList(sole), Path.get(sole.getTable()), null, null)), Collections.singletonMap(sole, 0));

            if (sole.getGraphSize() != 1)

                throw new IllegalArgumentException("Row is not alone : " + sole.printGraph());

        }

        // private to make sure the arguments are immutable

        private IndexedRows(List<State<?>> flatList, Map<SQLRowValues, Integer> indexes) {

            super();

            this.flatList = flatList;

            this.indexes = indexes;

            assert flatList.size() == indexes.size();

        }

        List<State<?>> getStates() {

            return this.flatList;

        }

        public int getSize() {

            return this.flatList.size();

        }

        State<?> getFirstState(int i) {

            return this.flatList.get(i);

        }

        public SQLRowValues getRow(int i) {

            return this.getFirstState(i).getCurrent();

        }

        public Path getFirstPath(int i) {

            return this.getFirstState(i).getPath();

        }

        public int getIndex(final SQLRowValues v) {

            return this.indexes.get(v);

        }

    }

    /**

     * Return all rows of this graph. This method will

     * {@link #walk(SQLRowValues, Object, ITransformer, WalkOptions) walk} the graph with the passed

     * parameters and collect the {@link State state} when it first reaches each row.

     *

     * @param vals where to start.

     * @param recType how to recurse.

     * @param useForeignsOrder <code>true</code> to use the order of foreign keys.

     * @return all rows.

     */

    public final IndexedRows getIndexedRows(final SQLRowValues vals, final RecursionType recType, final boolean useForeignsOrder) {

        final int size = this.size();

        final List<State<?>> flatList = new ArrayList<State<?>>(size);

        final IdentityHashMap<SQLRowValues, Integer> thisIndexes = new IdentityHashMap<SQLRowValues, Integer>(size);

        final WalkOptions walkOptions = new WalkOptions(Direction.ANY).setRecursionType(recType).setForeignsOrderIgnored(!useForeignsOrder).setStartIncluded(true);

        this.walk(vals, null, new ITransformer<State<Object>, Object>() {

            @Override

            public Object transformChecked(State<Object> input) {

                final SQLRowValues r = input.getCurrent();

                if (thisIndexes.containsKey(r)) {

                    // happens when there's multiple paths between 2 rows

                    throw new StopRecurseException("already added").setCompletely(false);

                } else {

                    thisIndexes.put(r, flatList.size());

                    flatList.add(input);

                }

                return null;

            }

        }, walkOptions);

        assert flatList.size() == size : "missing rows, should have been " + size + " but was " + flatList.size() + " : " + flatList;

        return new IndexedRows(Collections.unmodifiableList(flatList), Collections.unmodifiableMap(thisIndexes));

    }

    final void walkFields(final SQLRowValues start, IClosure<FieldPath> closure, final boolean includeFK) {

        walkFields(start, Path.get(start.getTable()), Collections.singletonList(start), closure, includeFK);

    }

    private void walkFields(final SQLRowValues current, final Path p, final List<SQLRowValues> currentValsPath, IClosure<FieldPath> closure, final boolean includeFK) {

        final Map<String, SQLRowValues> foreigns = current.getForeigns();

        for (final String field : current.getFields()) {

            final boolean isFK = foreigns.containsKey(field);

            if (!isFK || includeFK)

                closure.executeChecked(new FieldPath(p, field));

            if (isFK) {

                final SQLRowValues newVals = foreigns.get(field);

                // avoid infinite loop

                if (!currentValsPath.contains(newVals)) {

                    final Path newP = p.add(current.getTable().getField(field), Direction.FOREIGN);

                    final List<SQLRowValues> newValsPath = new ArrayList<SQLRowValues>(currentValsPath);

                    newValsPath.add(newVals);

                    this.walkFields(newVals, newP, newValsPath, closure, includeFK);

                }

            }

        }

    }

    /**

     * Copy this leaving only the fields specified by <code>graph</code>. NOTE: the result is

     * guaranteed not to be larger than <code>graph</code>, but it might be smaller if this didn't

     * contain all the paths.

     *

     * @param start where to start pruning, eg RECEPTEUR {DESIGNATION="rec", CONSTAT="ok",

     *        ID_LOCAL=LOCAL{DESIGNATION="local"}}.

     * @param graph the maximum structure wanted, eg RECEPTEUR {DESIGNATION=null}.

     * @return a copy of this no larger than <code>graph</code>, eg RECEPTEUR {DESIGNATION="rec"}.

     */

    public final SQLRowValues prune(final SQLRowValues start, final SQLRowValues graph) {

        return this.prune(start, graph, true);

    }

    /**

     * Copy this leaving only the fields specified by <code>graph</code>. NOTE: the result is

     * guaranteed not to be larger than <code>graph</code>, but it might be smaller if this didn't

     * contain all the paths. NOTE : only fields are considered, i.e. referents are not used. E.g.

     * with the rows below, no links would be removed, even though one LOCAL in the graph has no

     * CPI.

     *

     * <pre>

     * Graph :

     *        LOCAL LOCAL

     *      /        |

     *   SOURCE --> CPI

     *

     * This :

     *        LOCAL

     *      /       \

     *   SOURCE --> CPI

     * </pre>

     *

     *

     * @param start where to start pruning, e.g. RECEPTEUR {DESIGNATION="rec", CONSTAT="ok",

     *        ID_LOCAL=LOCAL{DESIGNATION="local"}}.

     * @param graph the maximum structure wanted, e.g. RECEPTEUR {DESIGNATION=null}.

     * @param keepUnionOfFields only relevant when the same row from this can be reached by more

     *        than one path in <code>graph</code>.

     *

     *        <pre>

     * Graph :

     *       /- ID_CONTACT_RAPPORT --> CONTACT1

     *  SITE -- ID_CONTACT_CHEF ---> CONTACT2

     *

     * This :

     *       /- ID_CONTACT_RAPPORT \

     *  SITE -- ID_CONTACT_CHEF ---> CONTACT

     *        </pre>

     *

     *        If <code>true</code> keep the union of all fields, if <code>false</code> the

     *        intersection.

     * @return a copy of this no larger than <code>graph</code>, e.g. RECEPTEUR {DESIGNATION="rec"}.

     */

    public final SQLRowValues prune(final SQLRowValues start, final SQLRowValues graph, final boolean keepUnionOfFields) {

        return pruneMap(start, graph, keepUnionOfFields).get(start);

    }

    public final Map<SQLRowValues, SQLRowValues> pruneMap(final SQLRowValues start, final SQLRowValues graph, final boolean keepUnionOfFields) {

        this.containsCheck(start);

        return this.copy(computeToRetain(start, graph, keepUnionOfFields), false, false);

    }

    static SetMap<SQLRowValues, String> computeToRetain(final SQLRowValues start, final SQLRowValues graph, final boolean keepUnionOfFields) {

        if (!start.getTable().equals(graph.getTable()))

            throw new IllegalArgumentException(start + " is not from the same table as " + graph);