Complex merge order dependencies
Problem to solve
In https://gitlab.com/gitlab-org/gitlab-ee/issues/9688 , we're adding the first iteration of merge ordering - this forms a directed acyclical graph of dependencies between merge requests, which happens to be only 2 members deep, for simplicity and ease of understanding for the user. That maximum depth will be enforced in the backend.
Some examples of valid trees with this restriction:
graph TD; gitlab-ee-->gitlab-ce;
graph TD; gitlab-proto-->gitlab-ce; gitlab-workhorse-->gitlab-ce;
graph TD; labkit-->gitaly; labkit-->gitlab-pages; labkit-->gitlab-workhorse;
graph TD; labkit-->gitlab-pages; labkit-->gitlab-workhorse; labkit-->gitaly; gitaly-proto-->gitaly; gitaly-proto-->gitlab-workhorse;
However, this is insufficient to solve all our merge request ordering dependency cases. 3, 4, 5, or more levels may be needed in the future. The only reason we have the 2-level restriction at present is because it's simple to display complete information about it to the user.
In GitLab, it's easy to construct a proposed tree of dependencies for a merge that is deeper than two levels. For instance, we could end up with this (suitably hideous) scenario if something went really wrong:
graph TD; labkit-->gitaly; labkit-->gitlab-pages; labkit-->gitlab-workhorse; gitaly-proto-->gitaly; gitaly-proto-->gitlab-workhorse; gitaly-proto-->gitlab-shell; gitaly-->gitlab-ee; gitaly-proto-->gitlab-ee; gitlab-pages-->gitlab-ee; gitlab-workhorse-->gitlab-ee; gitlab-shell-->gitlab-ee; gitlab-ee-->gitlab-ce;
Support setting up and respecting merge order dependencies like those listed above. This can be done in one of two ways:
- Support branchy trees like the above natively
- Flatten the trees into lists by verticalizing each level in the DAG
For the second example, assuming a left-to-right ordering, that means we eventually end up with this list:
graph TD; labkit-->gitaly-proto; gitaly-proto-->gitlab-pages; gitlab-pages-->gitaly gitaly-->gitlab-workhorse; gitlab-workhorse-->gitlab-shell; gitlab-shell-->gitlab-ee; gitlab-ee-->gitlab-ce;
This is simpler, and easier to display/manipulate, but we do lose some efficiency and obviousness in the flattening. Why does
gitlab-shell depend on
gitlab-workhorse in this model? It's completely unobvious. When rearranging, what happens if you move an intermediate node? How do we ensure that the actual dependency (
gitaly-proto in this case) is retained if we're moving
gitlab-shell earlier in the list?
The difficulty of answering these kinds of questions means my preference is for at least storing the tree natively. Moving nodes around in it can then correctly calculate actual dependencies.
What we display is still an open question - the lists are simpler to display, but if moving one items moves a bunch of others too, they're not simpler to understand. So perhaps supporting the tree from the start is the right option?