fix(package-graph): Flatten cycles to avoid skipping packages by nicolo-ribaudo · Pull Request #2185 · lerna/lerna

nicolo-ribaudo · 2019-07-16T23:42:01Z

Description

To correctly handle cycles, I wrote an algorithm which flattens cycles into single nodes. Then every cycled, when it becomes a "leaf node", can be normally executed.

Example:

          +---+
   /----> | B |
  |       +---+
  |
+---+     +---+ <----\
| A | --> | C |       |
+---+     +---+ --\   |
                   |  |
          +---+ <-/   |
          | D |       |
          +---+ -----/
            |
            v
          +---+
          | E |
          +---+

Becomes

          +---+
   /----> | B |
  |       +---+
  |
+---+     +-------+
| A | --> | C + D |
+---+     +-------+
              |
              v
            +---+
            | E |
            +---+

Now that there aren't anymore nodes, E and B can be executed since they are leaf nodes. The graph becomes:

+---+     +-------+
| A | --> | C + D |
+---+     +-------+

C + D now is a leaf node, so C and D can be executed. The cycle is then removed from the graph.

At this point, A becomes a leaf node and can be executed.

Note that two cycles might have an intersection (or be nested): in that case they are handled as a single cycle.

Context

Fixes #2107
Need to check: #2165 (@alcferreira)

How Has This Been Tested?

It fixed our problem in the Babel publishing process.

Types of changes

Bug fix (non-breaking change which fixes an issue)
New feature (non-breaking change which adds functionality)
Breaking change (fix or feature that would cause existing functionality to change)

Checklist:

My code follows the code style of this project.
My change requires a change to the documentation.
I have updated the documentation accordingly.
I have read the CONTRIBUTING document.
I have added tests to cover my changes.
All new and existing tests passed.

nicolo-ribaudo

I will mark this PR as ready after I have tested it with Babel.

I suggest reviewing it with whitespace diff disabled (https://github.com/lerna/lerna/pull/2185/files?w=1)

utils/pack-directory/__tests__/pack-directory.test.js

utils/listable/__tests__/listable-format.test.js

commands/run/__tests__/run-command.test.js

core/package-graph/index.js

nicolo-ribaudo · 2019-07-17T20:46:33Z

Oh this PR makes lerna warn about 6 cycles in Babel (instead of about 30), making it way more actionable to resolve 😄

And it seems to correctly update every package 😎

evocateur

I'm very impressed by this PR, thanks so much! (and huge apologies for the pain!)

evocateur · 2019-07-17T22:35:43Z

__fixtures__/cycle-intersection/graph.txt

+
+Cycles:
+B -> C -> D -> E -> B
+B -> C -> F -> G -> B


I love the graphs!

commands/run/__tests__/run-command.test.js

core/package-graph/index.js

utils/pack-directory/__tests__/pack-directory.test.js

core/package-graph/index.js

evocateur · 2019-07-18T16:38:17Z

I have no idea why the exec+run tests are flaking (inconsistently!) in CI. I'm fixing that now, then I'll merge.

…pace

…unnecessary

…every_ member

…, avoid environmental variability

bweggersen

Really great work! I love how you solved the problem at the right abstraction and simplified the way we should reason about cycles. I had to re-read the visits() function a few times to "get it". Especially lines 378-380, 384 and 391 in package-graph/index.js. There's a lot going on!

I'm grateful you were able to solve this so well, and I'm sorry this was a problem in the first place. I learned a lot reviewing your code!

bweggersen · 2019-07-18T08:49:22Z

__fixtures__/cycle-parent/graph.txt

+  |
+---+     +---+ <----\
+| A | --> | C |       |
+---+     +---+ <-\   |


nit: C and D's dependency lines should only point one direction each, right?

Good catch, I've fixed this

nicolo-ribaudo · 2019-07-18T18:35:19Z

@evocateur Thanks for your new commits ☺️

evocateur · 2019-07-18T19:02:49Z

ok ok i'm done tweaking i swear

evocateur · 2019-07-18T19:09:13Z

@nicolo-ribaudo @bweggersen Huge thanks for all your help!

Thanks to a gracious fix to Lerna by the Babel community, this issue (originally reported in my lerna/lerna#2107) is no longer an issue in new versions of Lerna, thanks to the fix provided in lerna/lerna#2185. Ref: lerna/lerna#2185 Ref: lerna/lerna#2107

v3.16 includes lerna/lerna#2185, which fixes an issue we had in the v7.5 releases

@JakeDawkins

> In the same spirit as `apollo-server`: > apollographql/apollo-server@585085d4d8dd7ab Thanks to a gracious fix to Lerna by the Babel community, this issue (originally reported in my lerna/lerna#2107) is no longer an issue in new versions of Lerna, thanks to the fix provided in lerna/lerna#2185. Ref: lerna/lerna#2185 Ref: lerna/lerna#2107 cc @JakeDawkins cc @trevor-scheer

@JakeDawkins

* Stop pinning Lerna to pre v3.14.0. > In the same spirit as `apollo-server`: > apollographql/apollo-server@585085d4d8dd7ab Thanks to a gracious fix to Lerna by the Babel community, this issue (originally reported in my lerna/lerna#2107) is no longer an issue in new versions of Lerna, thanks to the fix provided in lerna/lerna#2185. Ref: lerna/lerna#2185 Ref: lerna/lerna#2107 cc @JakeDawkins cc @trevor-scheer * chore(deps): update dependency lerna to v3.16.4

nicolo-ribaudo force-pushed the cycle-parent-version-bug branch from e5917a0 to 10ded5e Compare July 16, 2019 23:42

nicolo-ribaudo changed the title ~~Add wrong test~~ Fix cycle detection in "lerna version" Jul 17, 2019

nicolo-ribaudo force-pushed the cycle-parent-version-bug branch 2 times, most recently from b619ccb to 0f0dae2 Compare July 17, 2019 20:16

nicolo-ribaudo commented Jul 17, 2019

View reviewed changes

nicolo-ribaudo marked this pull request as ready for review July 17, 2019 20:50

evocateur approved these changes Jul 17, 2019

View reviewed changes

nicolo-ribaudo added 6 commits July 18, 2019 13:47

Add wrong test

6faa234

Fix partitionCycles with multiple dependencies

284b9b8

Add more fixtures

a918a22

Update cycles detection logic

d405c84

Tests

14ab7a8

[lint] Use fn declarations

031ecf3

nicolo-ribaudo force-pushed the cycle-parent-version-bug branch from b9d9352 to 031ecf3 Compare July 18, 2019 11:59

Revert wrong change in fixture lerna.json

9c5d045

evocateur added 7 commits July 18, 2019 09:38

test: cover PackageGraphNode.toString()

8461839

chore: package.json files should be 2-space indented, with trailing s…

9072dea

…pace

Remove externalDependencies map from PackageGraphCollapsedNode, it's …

bf6ee90

…unnecessary

Refactor hasPackageDeep() to return early instead of iterating over _…

f8c531a

…every_ member

un-nest version-command tests

d06424a

test: Always run order-sensitive toposort tests with concurrency of 1…

807ea59

…, avoid environmental variability

test: Update expected order of toposort calls

11f9ff4

bweggersen approved these changes Jul 18, 2019

View reviewed changes

evocateur added 4 commits July 18, 2019 11:13

fix arrows in graph models

0fd8bec

cleanup query-graph

176c0cb

Rename PackageGraphCollapsedNode -> CyclicPackageGraphNode

eeab59d

cleanup cyclic methods

35a2b49

evocateur added 4 commits July 18, 2019 11:43

Add .unlink() instance method to CyclicPackageGraphNode

28727a3

forEach -> for-of

df7021c

rename methods and parameters for clarity

794af07

s/add/insert/, former method was too Set-like

1006a36

evocateur changed the title ~~Fix cycle detection in "lerna version"~~ fix(package-graph): Flatten cycles to avoid skipping packages Jul 18, 2019

evocateur merged commit b335763 into lerna:master Jul 18, 2019

nicolo-ribaudo deleted the cycle-parent-version-bug branch July 18, 2019 20:12

nicolo-ribaudo mentioned this pull request Aug 12, 2019

fix(bootstrap): Run lifecycle scripts in topological queue instead of batches #2224

Merged

10 tasks

nicolo-ribaudo added a commit to babel/babel that referenced this pull request Sep 6, 2019

Update lerna

735abc0

v3.16 includes lerna/lerna#2185, which fixes an issue we had in the v7.5 releases

abernix mentioned this pull request Sep 6, 2019

Stop pinning Lerna to pre v3.14.0. apollographql/apollo-tooling#1505

Merged

snyk-bot mentioned this pull request Sep 27, 2019

[Snyk] Upgrade lerna from 3.15.0 to 3.16.4 adamlaska/scatter-js#3

Open

Conversation

nicolo-ribaudo commented Jul 16, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description

Context

How Has This Been Tested?

Types of changes

Checklist:

Uh oh!

nicolo-ribaudo left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

nicolo-ribaudo commented Jul 17, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

evocateur left a comment

Choose a reason for hiding this comment

Uh oh!

evocateur Jul 17, 2019

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

evocateur commented Jul 18, 2019

Uh oh!

bweggersen left a comment

Choose a reason for hiding this comment

Uh oh!

bweggersen Jul 18, 2019

Choose a reason for hiding this comment

Uh oh!

evocateur Jul 18, 2019

Choose a reason for hiding this comment

Uh oh!

nicolo-ribaudo Jul 18, 2019

Choose a reason for hiding this comment

Uh oh!

nicolo-ribaudo commented Jul 18, 2019

Uh oh!

evocateur commented Jul 18, 2019

Uh oh!

evocateur commented Jul 18, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

nicolo-ribaudo commented Jul 16, 2019 •

edited

Loading

nicolo-ribaudo commented Jul 17, 2019 •

edited

Loading