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!