Pkg dependenciestree to handle topological sort#2138
Pkg dependenciestree to handle topological sort#2138unmultimedio wants to merge 2 commits intomainfrom
Conversation
bufdev
left a comment
There was a problem hiding this comment.
I think this package could be replaced with a DAG and topo sort, see https://github.com/stevenle/topsort as an example
| "github.com/bufbuild/buf/private/pkg/stringutil" | ||
| ) | ||
|
|
||
| // DependenciesTree is a tree that holds nodes depending on other nodes. One level deep. |
There was a problem hiding this comment.
What does "one level deep" mean? Does this mean this structure only deals with direct dependencies?
There was a problem hiding this comment.
Correct, which for our cases is good. Workspaces have modules (first level), and each module have dependencies (all direct and transitive, second level).
For the third-party modules sync job in the BSR, modules have a single list of dependencies, which are also root nodes that have their own deps.
This doesn't mean we cannot have a multi-level link like a->b->...->z, it just means that all of those need to also be root nodes.
There was a problem hiding this comment.
I'm thinking now that the fact that the tree is one-level deep it's an implementation detail that doesn't need to be disclosed in the docs. To the user, it's a regular graph with nodes that depend on other nodes.
| // - c: [d] | ||
| // - d: [b] // circular dependency: b.c.d.b | ||
|
|
||
| package dependenciestree |
There was a problem hiding this comment.
Somewhat awkward package name - plurals, named after main type in package. Consider some other name, would need to brainstorm.
There was a problem hiding this comment.
This package is also in pkg, so should be universal and not buf-specific. Is this package intended to be useful across constructs other than modules?
There was a problem hiding this comment.
yeah, I thought about it and doesn't feel something that's Buf-specific. Tbh locally I tried other two, I started with toposort, but discarded it because it doesn't only sort, it also validates, and I'd like to leave it open for more functionalities when handling a tree, so I then went to depstree, and then ended up with dependenciestree. Open for suggestions.
| for _, opt := range opts { | ||
| opt(&config) | ||
| } | ||
| return &depsTree{ |
There was a problem hiding this comment.
Per Go Code Standards, this would be in a separate file named deps_tree.go. However, it likely would be named after the interface as well, in this case dependenciesTree, although this is an awkward name. Perhaps instead, standardize on DepTree (and depTree in dep_tree.go).
| } | ||
|
|
||
| // NewDependenciesTreeOption are options that can be passed when instantiating a new dependencies tree. | ||
| type NewDependenciesTreeOption func(*newDependenciesTreeOptions) |
There was a problem hiding this comment.
All other options structs in this codebase are named after the type they initialize, in this case dependenciesTreeOption, however it is unlikely this is needed at all (see below).
| return t.sort(pendingRootNodes, nil) | ||
| } | ||
|
|
||
| type newDependenciesTreeOptions struct { |
There was a problem hiding this comment.
There's likely no need for this at all - you can make the options func(*depTree)
| // (external or circular) is possible, tree should be checked against the Validate func. | ||
| NewRootNode(rootNode string, dependencies map[string]struct{}) error | ||
| // Validate checks that the tree nodes have valid dependencies, with no circular dependencies. | ||
| Validate() error |
There was a problem hiding this comment.
Interfaces in this codebase are generally validated upon construction, perhaps you want a *Builder?
There was a problem hiding this comment.
Yes! A builder strategy will help me here.
| Validate() error | ||
| // Sort validates that the tree is valid, and then returns the tree in topological order, leafs | ||
| // first. Useful for installation or update order. | ||
| Sort() ([]string, error) |
There was a problem hiding this comment.
Why do we need an explicit Validate if Sort validates as well?
There was a problem hiding this comment.
Correct, having a builder solves this.
| } | ||
|
|
||
| // New initializes a new dependencies tree, ready to have root nodes added to it. | ||
| func New(opts ...NewDependenciesTreeOption) DependenciesTree { |
There was a problem hiding this comment.
Typically would be named options...
There was a problem hiding this comment.
I find almost an equal amount of results of opts ... and options .... in the codebase. I'll change it though.
| // NewDependenciesTreeOption are options that can be passed when instantiating a new dependencies tree. | ||
| type NewDependenciesTreeOption func(*newDependenciesTreeOptions) | ||
|
|
||
| // NewDependenciesTreeWithAllowExternalDeps allows a root node in the tree to depend on external |
There was a problem hiding this comment.
I don't understand what an "external dependency" is, can you clarify? What dependencies are internal dependencies, and what are external?
There was a problem hiding this comment.
Docs can be improved, you're right. I "internal" means that a tree node depends on another tree node, while an external depends on a value that's not a tree node:
{
aaa: {
bbb, // internal
ccc, // internal
},
bbb: {
ccc, // internal
zzz, // external
},
ccc: {},
}
| allowExternalDependencies bool | ||
| } | ||
|
|
||
| func (t *depsTree) validateDependencies( |
There was a problem hiding this comment.
This package switches between deps and dependencies a lot, see above comments
There was a problem hiding this comment.
I'll default to deps.
Thanks for the review, I thought it's a simple enough functionality that could live in the repo instead of vendoring it from another library? As per the questions: is this a tree? how many root nodes? wdym one-level deep?, probably those can be solved by renaming structs/interfaces, and better documenting? I'd hope the testing scenarios would make it much clearer. |
|
I get the instinct of not depending on another lib, but for the record, I just looked through https://github.com/stevenle/topsort a bit more carefully including who is using it and who is committing to it, and it looks legitimate. I'm putting up a PR that effectively vendors it with proper attribution - take it or leave it, but just as a competing idea here of what we could do. |
|
Merged #2141, which I believe replaces this, let me know otherwise. |
For dealing with workspaces (push, sync), we need first to sort modules in topological order. This pkg will be useful in the BSR as well for syncing third party modules, where a similar logic lives, and will be replaced by this pkg.