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.

Sign up for GitHub

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

Jump to bottom

Use the dependency graph format for the GoMod package manager #4249

Closed
oheger-bosch opened this issue Jul 2, 2021 · 8 comments
Closed

Use the dependency graph format for the GoMod package manager #4249

oheger-bosch opened this issue Jul 2, 2021 · 8 comments
Labels
analyzer About the analyzer tool enhancement Issues that are considered to be enhancements

Comments

@oheger-bosch
Copy link
Member

This is a sub ticket of #3825 that addresses the GoMod package manager implementation.
@oheger-bosch oheger-bosch added analyzer About the analyzer tool enhancement Issues that are considered to be enhancements labels Jul 2, 2021
@oheger-bosch oheger-bosch mentioned this issue Jul 2, 2021
Open
25 tasks
@sschuberth sschuberth changed the title Use the dependency graph format for the GoMod package manager. Use the dependency graph format for the GoMod package manager Jul 2, 2021
@sschuberth sschuberth mentioned this issue Jul 2, 2021
Closed
@sschuberth
Copy link
Member

@fviernau, in order to move a bit forward with the #3825 epic, I was wondering whether you'd have a chance to work on this issue as you were doing a lot of Go(Mod) stuff recently?

@fviernau
Copy link
Member

fviernau commented Jul 20, 2022 •
edited
Loading

I'd actually be interested in doing this, I would volunteer but I cannot make promises about any E.T.A. right now, so I'm fine if someone else steals it. It may make sense to do it after #5555, as I expect to unlock quite a bit of simplification potential in that ticket.

fviernau added a commit that referenced this issue Aug 2, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
bed6ae3 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinited recursion
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway, which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
@fviernau fviernau mentioned this issue Aug 2, 2022
Merged
fviernau added a commit that referenced this issue Aug 2, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
effa5f9 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinited recursion
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway, which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
fviernau added a commit that referenced this issue Aug 2, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
ec1d003 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinited recursion.
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion.
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway, which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
fviernau added a commit that referenced this issue Aug 3, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
3f9e8a6 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinited recursion.
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion.
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway, which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
fviernau added a commit that referenced this issue Aug 3, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
69de79a 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinited recursion.
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion.
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway [2], which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
fviernau added a commit that referenced this issue Aug 3, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
1467603 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinite recursion.
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion.
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway [2], which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
fviernau added a commit that referenced this issue Aug 3, 2022
@fviernau
GoMod: Fix the algorithm for handling cycles
aec19fc 
The previous algorithm exhibits the following issues when run on graphs
with cycles, in particular when the amount of edges is large:

1. Cycles of length 1 lead to infinite recursion.
2. The algorithm is inefficient in terms of execution time and memory
   allocation, as it creates a copy of the
   `predecessorNodes` set per recursion.
3. When run against [1] the execution of `toPackageReferenceForest()`
   didn't finish within 15 minutes, causing high CPU load and memory
   consumption.

If GoMod used the dependency graph format already, the solution would be
as simple as calling `DependencyGraphBuilder.breakCycles()`. Fix the
problem by copying the code of `DependencyGraphBuilder.breakCycles()` as
a temporary quick fix. This saves effort, because refactoring GoMod to
use the dependency graph is planned anyway [2], which will allow for
removing that copied code again.

[1] https://github.com/ossf/scorecard
[2] #4249

Fixes #5627.

Signed-off-by: Frank Viernau <[email protected]>
@sschuberth
Copy link
Member

I'd actually be interested in doing this

@fviernau, is there still interested from your side to implement his?

@fviernau
Copy link
Member

fviernau commented Apr 17, 2024 •
edited
Loading

@fviernau, is there still interested from your side to implement his?

Interest yes, available time in near future: no.
In particular about the thing we had discussed a while ago:
Not make GoMod more complicated but replace or refactor the depdendency graph API so that it better fits.
IIUC migrating to the depedency graph in my view would complicate the implementation again, and I believe this is undersirable.

So, I cannot make any promises on that right now, sadly.

@sschuberth
Copy link
Member

Not make GoMod more complicated but replace or refactor the depdendency graph API so that it better fits.

Fair enough, then we should probably involve @oheger-bosch to check whether he'd have time for such a refactoring...

@fviernau
Copy link
Member

@schuberth what's the main reason for the migration?

  1. Consistency
  2. Removal of the redundant breakCycles() code
  3. Anything else

@sschuberth
Copy link
Member

I don't think there one main reason, but a mix of

  • consistency / reduction of similar code
  • preparing for the removal of legacy dependency tree code (once all PMs have been migrated)
  • the hope for reduced memory usage during analysis

@sschuberth
Copy link
Member

Closing this in favor of tracking it only in parent issue #3825.

@sschuberth sschuberth closed this as not planned Won't fix, can't repro, duplicate, stale Jun 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
analyzer About the analyzer tool enhancement Issues that are considered to be enhancements
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@sschuberth @fviernau @oheger-bosch