RFR: Add topological merge bot

[Erik Duveblad 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

On the other hand I don't expect a branch to have more than lets say five other branches it depends on, so I think a quadratic cost could work here :smiley:

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