RFR: Add topological merge bot

[Jorn Vernee via github.com]

On Thu, 29 Aug 2019 13:19:41 GMT, mcimadamore via github.com <duke at openjdk.java.net> wrote:

> 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
> 
> 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

Yep, it's pretty quick and dirty implementation of finding any nodes without incoming edges and then adding them to the sorted list and removing from the graph. Finally, we need to once more find all leaves, since those will always have incoming edges.

It doesn't seem like perf would be a problem, and the GraphUtils impl seems a lot more extensive. So, since it works (just done writing tests), maybe stick with Quick & Dirtyâ„¢ for now?

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