6 releases
0.1.5 | Sep 30, 2021 |
---|---|
0.1.4 | Sep 29, 2021 |
#1861 in Data structures
24 downloads per month
19KB
284 lines
dependency-graph
Dependency-graph is a minimal library, exposing a DependencyGraph
structure and a single Node
trait.
To use the library, simply implement the Node
trait's two functions for the object you wish to resolve dependencies for.
Example
In this example, we'll be using dependency-graph
to resolve dependencies between our Package
structs. We'll be using a custom Dependency
type, because we want to include Semantic Versioning constraints in our dependencies. That way we'll be able to say that our package mypackage
depends on version 2.0 of some package some-library
for instance.
Our Package
and Dependency
structs use the semver::Version
and semver::VersionReq
types to define the versions of the Packages
(such as 1.2.3-beta.4) and the dependency requirements such as >=2.0
. See the semver crate for more information.
First we define the Package
struct:
struct Package {
name: &'static str,
version: Version,
dependencies: Vec<Dependency>,
}
Where Dependency
is:
struct Dependency {
name: &'static str,
version: VersionReq,
}
Implementing the Node
trait for our Package
is pretty simple:
impl Node for Package {
type DependencyType = Dependency;
fn dependencies(&self) -> &[Self::DependencyType] {
&self.dependencies[..]
}
fn matches(&self, dependency: &Self::DependencyType) -> bool {
// Check that name is an exact match, and that the dependency
// requirements are fulfilled by our own version
self.name == dependency.name && dependency.version.matches(&self.version)
}
}
Let's define some packages and dependencies:
let packages = vec![
Package {
name: "base",
version: semver::Version {
major: 1,
minor: 2,
patch: 3,
pre: Prerelease::new("").unwrap(),
build: BuildMetadata::EMPTY,
},
dependencies: vec![],
},
Package {
name: "derived",
version: semver::Version {
major: 3,
minor: 2,
patch: 0,
pre: Prerelease::new("").unwrap(),
build: BuildMetadata::EMPTY,
},
dependencies: vec![Dependency {
name: "base",
version: "=1.2.3".parse().unwrap(),
}],
},
Package {
name: "second_order",
version: semver::Version {
major: 11,
minor: 2,
patch: 4,
pre: Prerelease::new("").unwrap(),
build: BuildMetadata::EMPTY,
},
dependencies: vec![Dependency {
name: "derived",
version: ">=3.0.0".parse().unwrap(),
}],
},
]
Now that we've defined all our packages as well as how dependencies between them are resolved (by implementing Node
), we can build a DependencyGraph
from it and traverse it, knowing that dependencies will always be visited before the packages that depend on them.
In our case, we would expect the base
package to be first (since derived
depends on it), then derived
second, since second_order
depends on it in turn, and therefore cannot be resolved until derived
has been. And then finally second_order
, since all its dependencies have now been resolved.
let graph = DependencyGraph::from(&packages[..]);
for package in graph {
match package {
// Print out the package name so we can verify the order in the console
Step::Resolved(package) => println!("Building {}!", package.name),
// Since we know that all our Packages only have internal references to each other,
// we can safely ignore any Unresolved steps in the graph.
//
// If for example `second_order` required some unknown package `external_package`,
// iterating over our graph would yield that as a Step::Unresolved *before*
// the `second_order` package.
Step::Unresolved(_) => unreachable!()
}
}
If we run the above code, we can verify that they did indeed build in the right order:
Building base!
Building derived!
Building second_order!
Dependencies
~2MB
~29K SLoC