# 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](https://crates.io/crates/semver) crate for more information.

First we define the `Package` struct:
```rust
struct Package {
    name: &'static str,
    version: Version,
    dependencies: Vec<Dependency>,
}
```
Where `Dependency` is:
```rust
struct Dependency {
    name: &'static str,
    version: VersionReq,
}

```

Implementing the `Node` trait for our `Package` is pretty simple:
```rust
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:
```rust
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.

```rust
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!
```