Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix(collect-dependents): Avoid skipping dependents of cyclic dependencies #2380

Merged
merged 1 commit into from Dec 15, 2019

Conversation

fresk-nc
Copy link
Contributor

In case of cyclic dependencies, some packages of the modified package are skipped.

Description

packages:

package-cycle-1
  localDependents:
    package-cycle-2
    package-cycle-extraneous-1
    package-cycle-extraneous-2

package-cycle-2
  localDependents:
    package-cycle-1
    package-cycle-extraneous-2

Let's say we changed package-cycle-2 then the following will happen:

  1. package-cycle-2 is current node. Check local dependents of package-cycle-2
  2. Check package-cycle-1
  3. Add package-cycle-1 to changed. Remember that we visit it.
  4. Dive to the level below. Check local dependents of package-cycle-1
  5. Skip package-cycle-2 because it is current node. Remember that we visit it.
  6. Skip package-cycle-extraneous-1 because local dependents of package-cycle-1 include package-cycle-2. Remember that we visit it.
  7. Skip package-cycle-extraneous-2 because local dependents of package-cycle-1 include package-cycle-2. Remember that we visit it.
  8. Back to the level above. Check package-cycle-extraneous-2 and skip because we have visited it.

So, we missed package-cycle-extraneous-2 and it looks like a bug.

I replaced depth-first search to breadth-first search. Now it works well.

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.

@evocateur evocateur changed the title fix(collect-dependents): Replace the DFS to BFS fix(collect-dependents): Avoid skipping dependents of cyclic dependencies Dec 15, 2019
@evocateur evocateur merged commit bd19a34 into lerna:master Dec 15, 2019
zxbodya added a commit to zxbodya/babel that referenced this pull request May 18, 2020
because of bug in lerna some dependencies might be installed from npm instead of linking to package in monorepo
fix: lerna/lerna#2380
zxbodya added a commit to zxbodya/babel that referenced this pull request May 18, 2020
because of bug in lerna some dependencies might be installed from npm instead of linking to package in monorepo
fix: lerna/lerna#2380
zxbodya added a commit to zxbodya/babel that referenced this pull request May 20, 2020
because of bug in lerna some dependencies might be installed from npm instead of linking to package in monorepo
fix: lerna/lerna#2380
expect(Array.from(result)).toEqual([
expect.objectContaining({ name: "package-cycle-1" }),
expect.objectContaining({ name: "package-cycle-extraneous-2" }),
// package-cycle-extraneous-1 was ignored
Copy link

@kenrick95 kenrick95 Oct 1, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please excuse me on commenting on old PR, but what is the reason behind ignoring package-cycle-extraneous-1? I know it is directly because siblingDependents.has(currentNode.name) evaluates to true, but what is the intention behind this? I don't fully understand the comment there ("a direct or transitive cycle, skip it"). I hope someone could explain this. Thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants