Dependency-ordered autosort algorithm

[MythicManiac]

Create an autosort algorithm that orders all packages defined in the package.lock file in a fashion where everything gets their dependencies satisfied first (where possible)

Example ordering

Dependency graph:

                   +-----+
                   |     |
              +----+  B  +-----+
              |    |     |     |
              |    +-----+     |
              |                |
              |                |
              |                |
              |                |
           +--+--+          +--+--+
           |     |          |     |
   +-------+  A  |    +-----+  C  +-----+
   |       |     |    |     |     |     |
   |       +-----+    |     +-----+     |
   |                  |                 |
   |                  |                 |
+--+--+            +--+--+           +--+--+
|     |            |     |           |     |
|  D  |            |  E  |           |  F  |
|     |            |     |           |     |
+-----+            +-----+           +-----+

Resolved load order:

B
A
C
D
E
F

There are some situations where the load order is ambiguous or does not have a clear dependency order (e.g. between D, E, and F). Strategy for deciding in which order to load these is up to the implementation, feel free to suggest how that could be done

[MythicManiac]

Relates to #12

[marius851000]

I would consider order independantly than depth. The idea that was brought up in Discord some time ago is (from left to right, so B depend on ["A", "B"] (it is important to have a deterministic order for reproductability):

We first try to solve the most left branch. That is easy, and resolve to D, A

Then we solve the right branch. We have C, with two depency. We load the left depency of C, and then it's right one : D, A, E, F

Finally, we load C, then B : D, A, E, F, C, B

Here is a rust implementation of this, (with additionally a check for infinite recursion): https://gist.github.com/marius851000/d004ac69af86b1337ce8b295a1b6787e

[MythicManiac]

@marius851000 if you're referring to the example graph posted above, I wonder if you're reading it the correct way around, since my example assumed that

• D depends on A
• E depends on C
• F depends on C
• A depends on B
• C depends on B

was this how you interpreted it as well?

[marius851000]

@MythicManiac Oups, I indeed interpreted it in the the wrong way (like C depend on F instead of F depend on C). In This case, my idea would then be (assuming we add a Z that depend on (D, E, F): Z depend on D depend on A that depend on B that depend on nothing: add B. Z depend on D depend on A depend on nothing that wasn't added: add A (and then add D), so now we have: B, A, D

Now we have Z depend on E depend on C depend on nothing that wasn't added: we add C then E. Finally, every depency of F is loaded, so add F, ending with the root Z (note: Z is the profile), we then have B, A, D, C, E, F, Z

If I'm okay, the name of this kind of tree is deep-first tree instead of your propsed broad-first tree.

[MythicManiac]

Yeah that seems good to me 👍 in my example the load order between A and C doesn't actually matter, and the way you explained it is what implementation-wise is probably the easiest, so it'd make sense to do it that way.