asciidoc/dev/conflict-solving-algo.adoc

////
   Licensed to the Apache Software Foundation (ASF) under one
   or more contributor license agreements.  See the NOTICE file
   distributed with this work for additional information
   regarding copyright ownership.  The ASF licenses this file
   to you under the Apache License, Version 2.0 (the
   "License"); you may not use this file except in compliance
   with the License.  You may obtain a copy of the License at

     https://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing,
   software distributed under the License is distributed on an
   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   KIND, either express or implied.  See the License for the
   specific language governing permissions and limitations
   under the License.
////
Here are some explanations about the conflict management algorithm in Ivy.

First, one should have a good understanding on how Ivy resolves dependencies, and especially
transitive dependencies.

During the resolve process, Ivy visits each module of the dependency graph. +
Let's call each module a *node*, including the module we are trying to resolve dependencies for.

Each node should be able to give a conflict manager for a particular ModuleId. +
Let's name it *node.cm(mid)*.

Each node should be able to maintain a map from ModuleId to a resolved Collection of nodes.
This resolved collection will never contain any evicted node FOR the concerned node as far
as Ivy knows, depending on where it is in graph visit. +
Let's call this map resolved, and the corresponding resolved collection *node.resolved(mid)*.

During the visit, Ivy should always know from which node it came to visit another node. Let's call
the first node from which Ivy came *node.parent*. Note that this concept is slightly different from
node parent, since a node can have several parents in the graph, but there is also one *node.parent*
during the visit.

Let's say that a conflict manager is able to filter a collection of nodes to return only those
that are not evicted. Let's call that *cm.resolveConflicts(collection)*.

Let's call *node.dependencies* the collection of direct dependencies of a node.

Let's call *node.revision* the module revision id of a node.

And now for the algo. This algo attempts to evict nodes on the fly, i.e. during the Ivy visit,
to minimize the number of resolved modules, and thus the number of Ivy files to download.

It is presented in a very simplified description language, far away from the whole real complexity,
but giving a good understanding of how it works. In particular, it completely hides some complexity due
to configurations management.

[source,java,subs="verbatim,quotes"]
----
resolve(node) {
    node.resolved(node.mid) = _collection_(node);
    resolveConflict(node, node.parent, empty);
    if (!node.evicted && !node.alreadyResolved) {
        node.loadData();
        resolveConflict(node, node.parent, empty);
        if (!node.evicted) {
            // actually do resolve
            foreach (dep in node.dependencies) {
                resolve(dep);
            }
        }
    }
}

resolveConflict(node, parent, toevict) {
    if (node.revision.exact && parent.resolved(node.mid).revision.contains(node.revision)) {
        // exact revision already in resolved
        // => job already done
        return;
    }
    if (parent.resolved(node.mid).containsAny(toevict)) {
        // parent.resolved(node.mid) is not up to date:
        // recompute resolved from all sub nodes
        resolved = parent.cm(node.mid).resolveConflicts(parent.dependencies.resolved(node.mid));
    } else {
        resolved = parent.cm(node.mid).resolveConflicts(_collection_(node, parent.resolved(node.mid)));
    }
    if (resolved.contains(node)) {
        // node has been selected for the current parent
        // we update its eviction... but it can still be evicted by parent !
        node.evicted = false;

        // handle previously selected nodes that are now evicted by this new node
        toevict = parent.resolved(node.mid) - resolved;
        foreach (te in toevict) {
            te.evicted = true;
        }

        // it's very important to update resolved BEFORE recompute parent call
        // to allow it to recompute its resolved collection with correct data
        // if necessary
        parent.resolved(node.mid) = resolved;
        if (parent.parent != null) {
            resolveConflict(node, parent.parent, toevict);
        }
    } else {
        // node has been evicted for the current parent

        // it's time to update parent resolved with found resolved...
        // if they have not been recomputed, it does not change anything
        parent.resolved(node.mid) = resolved;

        node.evicted = true;
    }
}
----