diff options
-rw-r--r-- | Cargo.lock | 62 | ||||
-rw-r--r-- | Cargo.toml | 1 | ||||
-rw-r--r-- | src/main.rs | 84 | ||||
-rw-r--r-- | src/recipe.rs | 10 | ||||
-rw-r--r-- | src/resolve.rs | 91 | ||||
-rw-r--r-- | src/types.rs | 20 |
6 files changed, 130 insertions, 138 deletions
@@ -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" @@ -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) + } +} |