RFR: Add topological merge bot

[mcimadamore via github.com]

On Thu, 29 Aug 2019 12:28:41 GMT, Jorn Vernee via github.com <duke at openjdk.java.net> wrote:

> This PR adds a bot that does a topological merge of the branches in a repo.
> 
> The branches can declare a dependencies file, which lists the branches that they depend on. This bot will crawl the branches, collect the dependencies for each branch, and topologically sort them based on their dependencies. Following that it will attempt to merge each dependency into the dependent in this order (this is mainly done so that we get less merges/failures if one of the root merges fails).
> 
> Branches that do not declare a dependency file implicitly depend on the master branch. Therefore the list of branches that the bot considers is passed in during configuration.
> 
> ---
> 
> Aside from that, it also fixes a minor problem with `Repository::clone` on Windows.
> 
> ----------------
> 
> Commits:
>  - 4a8f3610:	Added top bot module
> 
> Pull request:
> https://git.openjdk.java.net/skara/pull/105
> 
> Webrev:
> https://webrevs.openjdk.java.net/skara/105/webrev.00
> 
> Patch:
> https://git.openjdk.java.net/skara/pull/105.diff
> 
> Fetch command:
> git fetch https://git.openjdk.java.net/skara pull/105/head:pull/105

This PR has been reviewed by mcimadamore via github.com - a comment has been added. Review comment:

While the code looks generally ok, I'd like to understand a bit more what it does (e.g. what the various API method translate to when it comes to Git, and what the actual behavior is in case of merge conflicts). Also there are some improvements on the topo sort handling.

PR: https://git.openjdk.java.net/skara/pull/105

bots/topological/src/main/java/org/openjdk/skara/bots/topological/TopologicalBot.java line 152:

> 151:             var isFastForward = repo.isAncestor(repo.head(), fromHash);
> 152:             repo.merge(fromHash);
> 153:             if (!isFastForward) {

All the logic in this routine is very dependent on the behavior of the VCS, and on which actual concrete commands do these API method map to, so it's hard to check whether this code is correct. One issue you already pointed oit yourself: with the abortMerge() method. Another issue I see is the behavior with respect to a merge conflict. In the old script we had to tweak the standard behavior a bit to try and auto-resolve conflicts as much as possible. I don't know what the standard merge behavior is in Git.

PR: https://git.openjdk.java.net/skara/pull/105

bots/topological/src/main/java/org/openjdk/skara/bots/topological/TopologicalBot.java line 210:

> 209:     private static List<Branch> tsort(List<Edge> edges) {
> 210:         List<Edge> eCopy = new ArrayList<>(edges);
> 211:         List<Branch> result = new ArrayList<>();

It seems to me that this methods is walking all the edges and trying to find cycles, and leaves. This probably works, but can be quadratic in cost. There are better alternatives out there - some of which already tried and tested which are part of the javac compiler itself. I suggest maybe directly using this?

http://hg.openjdk.java.net/jdk/jdk/file/c16208de74da/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java

There, you will also find interfaces for Node and the likes. The topo sort algo used there is routinely used in javac type inference, so it's been rather heavily tested :-)

PR: https://git.openjdk.java.net/skara/pull/105