Transitive closure of depends-on PRs

[jcommelin]

One thing that would be amazing for me would be to get the transitive closure of the depends-on relation for a given PR. I frequently think "I want to make progress on PR #XXXXX, which has a lot of dependent PRs, which PRs are ready for review that ultimately contribute to this PR", and then I have to do a manual depth-first search to find which PRs are ready for review.

This would provide a clear value-add over Github. But it might require quite an overhaul of our current approach using a static webpage.

[grunweg]

Actually, this could also be fit into the current approach, by performing this analysis during the pre-processing of the raw data. In other words, the bulk of this logic would live in process.py or dependencies of it.

[grunweg]

The necessary work should be manageable, but requires a number of steps. Even help with just some of these is welcome.
Here are some rough mentoring instructions: don't hesitate to ask if anything is too terse or unclear!

Step 1. Determine the open PRs that a given PR directly depends on. We can do this by parsing the PR description.

• add a function which parses the list of dependent PRs from a PR description
  I believe there are two possible (slightly different) syntaxes for dependent issues; just supporting the one in the default PR template is a useful start.
• add some unit tests, to be confident this works: including the cases of an empty description, just one vertical line and several of them; both with and without any dependent PR.
• preliminary work: add the PR description to the aggregate data
  See docs/Overview.md for instructions. The first step is already complete (the .json files contain the PR description as the description field); you just need to add an extra field to AggregatePRData. I'll be happy to help. This has been done now.
• given a PR, retrieve its description from its aggregate data, parse the dependent PR and filter these PRs to just the open ones (as given by the aggregate data). Careful: do not parse the "open/closed" status from the description (as that can be stale); use the aggregate data instead.

Step 2. Determine all open PRs that a PR transitively depends on
PR dependencies are acyclic in practice, so you can (probably) just compute this recursively: determine all open dependencies of a given PR, repeat this process for the these PRs (recursively) and aggregate the results.
It would also be great to have some tests for this logic.
For faster performance, you can cache the computation "PR -> direct dependencies", and use a set for the dependents (in case there are duplicates).

Step 3. Compute this information for all PR, and add it to the aggregate files.
Again, see the instructions in Overview.md for some pointers. In particular, make sure to update dashboard.py once the processed files were re-generated.

Step 4. Expose this information on the webpage
For instance, you could add another column to each dashboard, with the number of transive (open) dependencies --- say, with a tooltip showing the PR numbers. This column is by definition never useful for the queue itself (so you could hide it there), but other lists could have it.

Further ideas

• filter the list of open PRs to just those on the queue, and report just these (or perhaps, just these as well as all dependencies)
• create a "reverse query" (i.e. the number of open PRs that an open PR transitively blocks: that is useful information for the queue. This will require the work above, and some amount of additional code. This is tracked in dashboard for PRs that are blocking other PRs #26 and Display number of PRs blocked by a given PR #28.

[grunweg]

Let's keep this issue open until

• the new dashboard is tested and confirmed working,
• it is exposed on the webpage
• we have decided whether adding a new column to the table is useful or not. (This could also be split into another issue.)