Rewrite dependency resolution to reuse solutions

6 files changed, 130 insertions, 138 deletions

diff --git a/Cargo.lock b/Cargo.lock
index ac42b1b..5b12c9a 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1,36 +1,12 @@
 # This file is automatically @generated by Cargo.
 # It is not intended for manual editing.
 [[package]]
-name = "bitmaps"
-version = "2.1.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "031043d04099746d8db04daf1fa424b2bc8bd69d92b25962dcde24da39ab64a2"
-dependencies = [
- "typenum",
-]
-
-[[package]]
 name = "dtoa"
 version = "0.4.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "88d7ed2934d741c6b37e33e3832298e8850b53fd2d2bea03873375596c7cea4e"
 
 [[package]]
-name = "im"
-version = "15.0.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "111c1983f3c5bb72732df25cddacee9b546d08325fb584b5ebd38148be7b0246"
-dependencies = [
- "bitmaps",
- "rand_core",
- "rand_xoshiro",
- "serde",
- "sized-chunks",
- "typenum",
- "version_check",
-]
-
-[[package]]
 name = "linked-hash-map"
 version = "0.5.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -55,25 +31,9 @@ dependencies = [
 ]
 
 [[package]]
-name = "rand_core"
-version = "0.5.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
-
-[[package]]
-name = "rand_xoshiro"
-version = "0.4.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a9fcdd2e881d02f1d9390ae47ad8e5696a9e4be7b547a1da2afbc61973217004"
-dependencies = [
- "rand_core",
-]
-
-[[package]]
 name = "rebel"
 version = "0.1.0"
 dependencies = [
- "im",
  "serde",
  "serde_yaml",
  "walkdir",
@@ -121,16 +81,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "sized-chunks"
-version = "0.6.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1ec31ceca5644fa6d444cc77548b88b67f46db6f7c71683b0f9336e671830d2f"
-dependencies = [
- "bitmaps",
- "typenum",
-]
-
-[[package]]
 name = "syn"
 version = "1.0.59"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -142,24 +92,12 @@ dependencies = [
 ]
 
 [[package]]
-name = "typenum"
-version = "1.12.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "373c8a200f9e67a0c95e62a4f52fbf80c23b4381c05a17845531982fa99e6b33"
-
-[[package]]
 name = "unicode-xid"
 version = "0.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "f7fe0bb3479651439c9112f72b6c505038574c9fbb575ed1bf3b797fa39dd564"
 
 [[package]]
-name = "version_check"
-version = "0.9.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b5a972e5669d67ba988ce3dc826706fb0a8b01471c088cb0b6110b805cc36aed"
-
-[[package]]
 name = "walkdir"
 version = "2.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 3626264..d6eea9f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,7 +7,6 @@ edition = "2018"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
-im = { version = "15", features = ["serde"] }
 serde = { version = "1", features = ["derive"] }
 serde_yaml = "0.8"
 walkdir = "2"
diff --git a/src/main.rs b/src/main.rs
index 8c5708f..b572afc 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,88 +1,38 @@
-use im::{HashMap, HashSet};
-use std::{fmt, path::Path, rc::Rc};
+use std::collections::HashSet;
+use std::path::Path;
 
 mod recipe;
+mod resolve;
+mod types;
 
-#[derive(Debug)]
-enum Error {
-	TaskNotFound(String),
-	DependencyCycle(String),
-}
-
-impl fmt::Display for Error {
-	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-		match self {
-			Error::TaskNotFound(id) => write!(f, "Task not found: {}", id),
-			Error::DependencyCycle(id) => write!(f, "DependencyCycle: {}", id),
-		}
-	}
-}
-
-impl std::error::Error for Error {}
-
-type Result<T> = std::result::Result<T, Error>;
-
-#[derive(Default)]
-struct Context {
-	tasks: HashMap<String, Rc<recipe::Task>>,
-}
-
-impl Context {
-	fn collect_subtasks<'a>(
-		&'a self,
-		queued: &HashSet<&'a str>,
-		id: &str,
-	) -> Result<HashSet<&'a str>> {
-		let (task_id, task) = match self.tasks.get_key_value(id) {
-			Some(t) => t,
-			None => {
-				return Err(Error::TaskNotFound(id.to_string()));
-			}
-		};
-
-		if queued.contains(id) {
-			return Err(Error::DependencyCycle(id.to_string()));
-		}
-
-		let queued_sub = queued.update(task_id);
-
-		let mut subtasks: HashSet<&'a str> = HashSet::new();
-		subtasks.insert(task_id);
-
-		for dep in &task.depends {
-			let deptasks = self.collect_subtasks(&queued_sub, dep)?;
-			subtasks = subtasks.union(deptasks);
-		}
-
-		Ok(subtasks)
-	}
-
-	fn collect_tasks(&self, id: &str) -> Result<HashSet<&str>> {
-		self.collect_subtasks(&HashSet::new(), id)
-	}
-}
+use resolve::Result;
+use types::*;
 
 fn main() -> Result<()> {
 	let recipes = recipe::read_recipes(Path::new("examples")).unwrap();
 
-	let mut ctx = Context::default();
+	let mut tasks: TaskMap = TaskMap::default();
 	for (recipe_name, recipe) in recipes {
 		for (task_name, task) in recipe.tasks {
 			let full_name = format!("{}:{}", recipe_name, task_name);
-			ctx.tasks.insert(full_name, Rc::new(task));
+			tasks.0.insert(full_name, task);
 		}
 	}
 
-	let queue = ctx.collect_tasks("ls:build")?;
-	let (runnable, queued): (HashSet<&str>, HashSet<&str>) = queue
+	let mut rsv = resolve::Resolver::new(&tasks);
+
+	rsv.add_goal(&"ls:build".to_string())?;
+	let taskset = rsv.to_taskset();
+
+	let (runnable, queued): (HashSet<TaskRef>, HashSet<TaskRef>) = taskset
 		.into_iter()
-		.partition(|id| ctx.tasks.get(*id).unwrap().depends.is_empty());
+		.partition(|id| tasks.get(id).unwrap().depends.is_empty());
 
 	for t in &runnable {
-		println!("Runnable: {} ({:?})", t, ctx.tasks.get(*t).unwrap().run);
+		println!("Runnable: {} ({:?})", t, tasks.get(t).unwrap().run);
 	}
 	for t in &queued {
-		println!("Queued: {} ({:?})", t, ctx.tasks.get(*t).unwrap().run);
+		println!("Queued: {} ({:?})", t, tasks.get(t).unwrap().run);
 	}
 
 	Ok(())
diff --git a/src/recipe.rs b/src/recipe.rs
index d06b62b..20bca6d 100644
--- a/src/recipe.rs
+++ b/src/recipe.rs
@@ -1,14 +1,8 @@
-use im::HashMap;
 use serde::Deserialize;
-use std::{fmt, fs::File, io, path::Path};
+use std::{collections::HashMap, fmt, fs::File, io, path::Path};
 use walkdir::WalkDir;
 
-#[derive(Clone, Debug, Deserialize)]
-pub struct Task {
-	#[serde(default)]
-	pub depends: Vec<String>,
-	pub run: String,
-}
+use crate::types::*;
 
 #[derive(Clone, Debug, Deserialize)]
 pub struct Recipe {
diff --git a/src/resolve.rs b/src/resolve.rs
new file mode 100644
index 0000000..0758016
--- /dev/null
+++ b/src/resolve.rs
@@ -0,0 +1,91 @@
+use std::collections::{HashMap, HashSet};
+use std::fmt;
+
+use crate::types::*;
+
+#[derive(Debug)]
+pub enum Error {
+	TaskNotFound(TaskRef),
+	DependencyCycle(TaskRef),
+}
+
+impl fmt::Display for Error {
+	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+		match self {
+			Error::TaskNotFound(id) => write!(f, "Task not found: {}", id),
+			Error::DependencyCycle(id) => write!(f, "DependencyCycle: {}", id),
+		}
+	}
+}
+
+impl std::error::Error for Error {}
+
+pub type Result<T> = std::result::Result<T, Error>;
+
+#[derive(PartialEq)]
+enum ResolveState {
+	Resolving,
+	Resolved,
+}
+
+pub struct Resolver<'a> {
+	tasks: &'a TaskMap,
+	resolve_state: HashMap<TaskRef, ResolveState>,
+}
+
+impl<'a> Resolver<'a> {
+	pub fn new(tasks: &'a TaskMap) -> Self {
+		Resolver {
+			tasks: tasks,
+			resolve_state: HashMap::new(),
+		}
+	}
+
+	pub fn add_goal(&mut self, task: &TaskRef) -> Result<()> {
+		match self.resolve_state.get(task) {
+			Some(ResolveState::Resolving) => return Err(Error::DependencyCycle(task.clone())),
+			Some(ResolveState::Resolved) => return Ok(()),
+			None => (),
+		}
+
+		let task_def = match self.tasks.get(task) {
+			None => return Err(Error::TaskNotFound(task.clone())),
+			Some(task_def) => task_def,
+		};
+
+		self.resolve_state
+			.insert(task.clone(), ResolveState::Resolving);
+
+		for dep in &task_def.depends {
+			let res = self.add_goal(dep);
+			if res.is_err() {
+				self.resolve_state.remove(task);
+				return res;
+			}
+		}
+
+		*self
+			.resolve_state
+			.get_mut(task)
+			.expect("Missing resolve_state") = ResolveState::Resolved;
+
+		Ok(())
+	}
+
+	pub fn to_taskset(self) -> HashSet<TaskRef> {
+		fn tasks_resolved(this: &Resolver) -> bool {
+			for (_, resolved) in &this.resolve_state {
+				if *resolved != ResolveState::Resolved {
+					return false;
+				}
+			}
+			true
+		}
+		debug_assert!(tasks_resolved(&self));
+
+		self.resolve_state
+			.into_iter()
+			.map(|entry| entry.0)
+			.collect()
+	}
+}
diff --git a/src/types.rs b/src/types.rs
new file mode 100644
index 0000000..cb777f7
--- /dev/null
+++ b/src/types.rs
@@ -0,0 +1,20 @@
+use serde::Deserialize;
+use std::collections::HashMap;
+
+pub type TaskRef = String;
+
+#[derive(Clone, Debug, Deserialize)]
+pub struct Task {
+	#[serde(default)]
+	pub depends: Vec<TaskRef>,
+	pub run: String,
+}
+
+#[derive(Default)]
+pub struct TaskMap(pub HashMap<String, Task>);
+
+impl TaskMap {
+	pub fn get(&self, task: &TaskRef) -> Option<&Task> {
+		self.0.get(task)
+	}
+}