Adrien Kohlbecker requested to merge ak/mr-dependency into master Jan 25, 2021

What does this MR do?

In #11393 (closed), we consider how to allow complex dependency chains of MRs to be represented using the "merge request dependencies" feature.

Initially, only single-level trees of merge requests were allowed to avoid complicating things too much. Meaning you could have A->B and A->C but not A->B->C for example. The concern was that it would be complicated to unfurl complex trees of dependencies and reasonably display them.

Here, I'm proposing that we don't attempt to display complex dependency trees: If you create a chain of MRs, let's say A->B->C:

the MR page for C will only show the dependency on B
the MR page for B will only show the dependency on A
the MR page for A will not show anything

That is the current display behavior; nothing changes here. We only allow more complex relationships to exist in the backend.

As a user, I think it makes sense that on C's page, I'm shown that it depends on B. B's conditions for merge are varied (dependency, green pipeline, no conflicts, etc.). So if I'm interested to see how to resolve the dependency on B, I have to open B's page to figure out what's blocking it. I then see a dependency on A. All in all, unfurling the whole tree is nice to have but not a must-have.

Value provided by this feature

This allows creating Russian doll MRs (a sequence of MRs where each MR depends on the previous one). Inline with our iteration value, we aim to work in small increments. It follows that to work on complex features, opening small, iterative MRs is the way to go. However, today there is no way to ensure that such a chain of small MRs is merged in the intended order. See for example this recent chain of mine:

In this list, both gitlab-org/ci-cd/custom-executor-drivers/autoscaler!113 (merged) and gitlab-org/ci-cd/custom-executor-drivers/autoscaler!121 (merged) were merged, by different maintainers, while earlier MRs in the chain were still open.

Being able to prevent this from happening is the value added by this MR.

How it works

We remove the validation on multi-level chains of dependencies and add a new validation to make sure we're not introducing circular dependencies.

Assuming a pre-existing chain of dependencies A->B->C. We check that we're not prepending or appending an MR to this chain that already exists in it.

The check recursively traverses the dependencies first towards the parents. Say we want to add C->D, it would check that first B, then A is different than D.

Then it traverses the dependencies towards the children. Say we want to add D->A, it would check that first B, then C is different than D.

Screenshots (strongly suggested)

Title	Screenshot
A->B dependency
B->C dependency is now possible!
Adding circular dependency B->A is forbidden

Database review

recursively_find_blocked_mrs

Link to explain execution in database-lab

Formatted plan

WITH RECURSIVE children(id, path, cycle) AS
(
  SELECT
    77699665,
    ARRAY[77699665],
    FALSE
  UNION ALL
  SELECT
    b.blocked_merge_request_id,
    path || b.blocked_merge_request_id,
    b.blocked_merge_request_id = ANY(path)
  FROM
    merge_request_blocks b
    JOIN
      children
      ON children.id = b.blocking_merge_request_id
  WHERE
    NOT cycle
)
SELECT id FROM children WHERE id != 77699665

Time: 6.626 ms
  - planning: 0.550 ms
  - execution: 6.076 ms
    - I/O read: 5.821 ms
    - I/O write: N/A

Shared buffers:
  - hits: 1 (~8.00 KiB) from the buffer pool
  - reads: 5 (~40.00 KiB) from the OS file cache, including disk I/O
  - dirtied: 1 (~8.00 KiB)
  - writes: 0

CTE Scan on children  (cost=109.88..111.25 rows=60 width=4) (actual time=4.989..5.972 rows=1 loops=1)
   Filter: (children.id <> 77699665)
   Rows Removed by Filter: 1
   Buffers: shared hit=1 read=5 dirtied=1
   I/O Timings: read=5.821
   CTE children
     ->  Recursive Union  (cost=0.00..109.88 rows=61 width=37) (actual time=0.003..5.964 rows=2 loops=1)
           Buffers: shared hit=1 read=5 dirtied=1
           I/O Timings: read=5.821
           ->  Result  (cost=0.00..0.01 rows=1 width=37) (actual time=0.002..0.002 rows=1 loops=1)
           ->  Nested Loop  (cost=0.29..10.87 rows=6 width=37) (actual time=2.973..2.975 rows=0 loops=2)
                 Buffers: shared hit=1 read=5 dirtied=1
                 I/O Timings: read=5.821
                 ->  WorkTable Scan on children children_1  (cost=0.00..0.20 rows=5 width=36) (actual time=0.001..0.002 rows=1 loops=2)
                       Filter: (NOT children_1.cycle)
                       Rows Removed by Filter: 0
                 ->  Index Only Scan using index_mr_blocks_on_blocking_and_blocked_mr_ids on public.merge_request_blocks b  (cost=0.29..2.11 rows=1 width=8) (actual time=2.961..2.963 rows=0 loops=2)
                       Index Cond: (b.blocking_merge_request_id = children_1.id)
                       Heap Fetches: 1
                       Buffers: shared hit=1 read=5 dirtied=1
                       I/O Timings: read=5.821

recursively_find_blocking_mrs

Link to explain execution in database-lab

Formatted plan

WITH RECURSIVE parents(id, path, cycle) AS
(
  SELECT
    86065460,
    ARRAY[86065460],
    FALSE
  UNION ALL
  SELECT
    b.blocking_merge_request_id,
    path || b.blocking_merge_request_id,
    b.blocking_merge_request_id = ANY(path)
  FROM
    merge_request_blocks b
    JOIN
      parents
      ON parents.id = b.blocked_merge_request_id
  WHERE
    NOT cycle
)
SELECT id FROM parents WHERE id != 86065460

Time: 3.775 ms
  - planning: 0.511 ms
  - execution: 3.264 ms
    - I/O read: 3.017 ms
    - I/O write: N/A

Shared buffers:
  - hits: 1 (~8.00 KiB) from the buffer pool
  - reads: 4 (~32.00 KiB) from the OS file cache, including disk I/O
  - dirtied: 1 (~8.00 KiB)
  - writes: 0

 CTE Scan on parents  (cost=169.88..171.25 rows=60 width=4) (actual time=2.215..3.129 rows=1 loops=1)
   Filter: (parents.id <> 86065460)
   Rows Removed by Filter: 1
   Buffers: shared hit=1 read=4 dirtied=1
   I/O Timings: read=3.017
   CTE parents
     ->  Recursive Union  (cost=0.00..169.88 rows=61 width=37) (actual time=0.003..3.121 rows=2 loops=1)
           Buffers: shared hit=1 read=4 dirtied=1
           I/O Timings: read=3.017
           ->  Result  (cost=0.00..0.01 rows=1 width=37) (actual time=0.002..0.002 rows=1 loops=1)
           ->  Nested Loop  (cost=0.29..16.87 rows=6 width=37) (actual time=1.552..1.554 rows=0 loops=2)
                 Buffers: shared hit=1 read=4 dirtied=1
                 I/O Timings: read=3.017
                 ->  WorkTable Scan on parents parents_1  (cost=0.00..0.20 rows=5 width=36) (actual time=0.001..0.002 rows=1 loops=2)
                       Filter: (NOT parents_1.cycle)
                       Rows Removed by Filter: 0
                 ->  Index Scan using index_merge_request_blocks_on_blocked_merge_request_id on public.merge_request_blocks b  (cost=0.29..3.31 rows=1 width=8) (actual time=1.541..1.542 rows=0 loops=2)
                       Index Cond: (b.blocked_merge_request_id = parents_1.id)
                       Buffers: shared hit=1 read=4 dirtied=1
                       I/O Timings: read=3.017

Does this MR meet the acceptance criteria?

Conformity

Availability and Testing

Review and add/update tests for this feature/bug. Consider all test levels. See the Test Planning Process.
Tested in all supported browsers
Informed Infrastructure department of a default or new setting change, if applicable per definition of done

Security

If this MR contains changes to processing or storing of credentials or tokens, authorization and authentication methods and other items described in the security review guidelines:

Label as security and @ mention @gitlab-com/gl-security/appsec
The MR includes necessary changes to maintain consistency between UI, API, email, or other methods
Security reports checked/validated by a reviewer from the AppSec team

Edited Feb 04, 2021 by Adrien Kohlbecker

Allow creating a tree of MR dependencies