57 files changed, 4369 insertions, 788 deletions

diff --git a/crates/driver/src/driver.rs b/crates/driver/src/driver.rs
deleted file mode 100644
index d0abbcb..0000000
--- a/crates/driver/src/driver.rs
+++ /dev/null
@@ -1,409 +0,0 @@
-use std::{
-	collections::{HashMap, HashSet},
-	os::unix::{net::UnixStream, prelude::*},
-};
-
-use indoc::indoc;
-use nix::poll;
-
-use common::{error::*, string_hash::*, types::*};
-use runner::Runner;
-
-use crate::{
-	context::{Context, TaskRef},
-	paths, resolve,
-	task::*,
-	template,
-};
-
-#[derive(Debug)]
-pub struct CompletionState<'ctx> {
-	ctx: &'ctx Context,
-	tasks_done: HashMap<TaskRef<'ctx>, TaskOutput>,
-}
-
-impl<'ctx> CompletionState<'ctx> {
-	pub fn new(ctx: &'ctx Context) -> Self {
-		CompletionState {
-			ctx,
-			tasks_done: Default::default(),
-		}
-	}
-
-	// Treats both "depends" and "inherit" as dependencies
-	fn deps_satisfied(&self, task_ref: &TaskRef) -> bool {
-		resolve::get_dependent_tasks(self.ctx, task_ref)
-			.map_err(|_| Error::new(format!("invalid dependency for {}", task_ref)))
-			.unwrap()
-			.into_iter()
-			.all(|dep| self.tasks_done.contains_key(&dep))
-	}
-
-	fn fetch_deps(&self, task: &TaskRef<'ctx>) -> Result<Vec<Dependency>> {
-		let task_def = &self.ctx[task];
-		task_def
-			.fetch
-			.iter()
-			.map(|Fetch { name, sha256 }| {
-				Ok(Dependency::Fetch {
-					name: template::ENGINE
-						.eval_raw(name, &task.args)
-						.with_context(|| {
-							format!("Failed to evaluate fetch filename for task {}", task)
-						})?,
-					target_dir: paths::TASK_DLDIR.to_string(),
-					sha256: *sha256,
-				})
-			})
-			.collect()
-	}
-
-	fn task_deps(&self, task: &TaskRef<'ctx>) -> Result<HashSet<Dependency>> {
-		Ok(self
-			.fetch_deps(task)?
-			.into_iter()
-			.chain(
-				resolve::runtime_depends(
-					self.ctx,
-					self.ctx
-						.get_build_depends(task)
-						.with_context(|| format!("invalid build depends for {}", task))?,
-				)
-				.expect("invalid runtime depends of build_depends")
-				.into_iter()
-				.filter_map(|dep| self.tasks_done[&dep.task].outputs.get(dep.output))
-				.map(|&output| Dependency::Task {
-					output,
-					path: "".to_string(),
-				}),
-			)
-			.chain(
-				resolve::runtime_depends(
-					self.ctx,
-					self.ctx
-						.get_host_depends(task)
-						.with_context(|| format!("invalid depends for {}", task))?,
-				)
-				.expect("invalid runtime depends of host_depends")
-				.into_iter()
-				.filter_map(|dep| self.tasks_done[&dep.task].outputs.get(dep.output))
-				.map(|&output| Dependency::Task {
-					output,
-					path: paths::TASK_SYSROOT.to_string(),
-				}),
-			)
-			.collect())
-	}
-
-	fn task_inherit_chain(&self, task_ref: &TaskRef<'ctx>) -> Vec<LayerHash> {
-		let inherit = match self
-			.ctx
-			.get_inherit_depend(task_ref)
-			.expect("invalid inherit depends")
-		{
-			Some(inherit) => inherit,
-			None => return vec![],
-		};
-
-		let mut chain = self.task_inherit_chain(&inherit);
-		if let Some(layer) = self.tasks_done[&inherit].layer {
-			chain.push(layer);
-		}
-		chain
-	}
-
-	fn print_summary(&self) {
-		println!();
-		println!("Summary:");
-
-		let mut tasks: Box<[_]> = self.tasks_done.iter().collect();
-		tasks.sort_by_cached_key(|(task, _)| format!("{:#}", task));
-		for (task_ref, task) in tasks.iter() {
-			println!();
-			println!("{:#}", task_ref);
-			if let Some(hash) = task.input_hash {
-				println!("  input: {}", hash);
-			}
-			if let Some(hash) = task.layer {
-				println!("  layer: {}", hash);
-			}
-			if !task.outputs.is_empty() {
-				println!("  outputs:");
-
-				let mut outputs: Box<[_]> = task.outputs.iter().collect();
-				outputs.sort_by_key(|(output, _)| *output);
-				for (output, hash) in outputs.iter() {
-					println!("    {}: {}", output, hash);
-				}
-			}
-		}
-	}
-}
-
-enum SpawnResult {
-	Spawned(UnixStream),
-	Skipped(TaskOutput),
-}
-
-#[derive(Debug)]
-pub struct Driver<'ctx> {
-	rdeps: HashMap<TaskRef<'ctx>, Vec<TaskRef<'ctx>>>,
-	force_run: HashSet<TaskRef<'ctx>>,
-	tasks_blocked: HashSet<TaskRef<'ctx>>,
-	tasks_runnable: Vec<TaskRef<'ctx>>,
-	tasks_running: HashMap<RawFd, (UnixStream, TaskRef<'ctx>)>,
-	state: CompletionState<'ctx>,
-}
-
-impl<'ctx> Driver<'ctx> {
-	pub fn new(
-		ctx: &'ctx Context,
-		taskset: HashSet<TaskRef<'ctx>>,
-		force_run: HashSet<TaskRef<'ctx>>,
-	) -> Result<Self> {
-		let mut driver = Driver {
-			rdeps: Default::default(),
-			force_run,
-			tasks_blocked: Default::default(),
-			tasks_runnable: Default::default(),
-			tasks_running: Default::default(),
-			state: CompletionState::new(ctx),
-		};
-
-		for task in taskset {
-			let mut has_depends = false;
-			for dep in resolve::get_dependent_tasks(ctx, &task)
-				.map_err(|_| Error::new(format!("invalid dependency for {}", task)))?
-			{
-				let rdep = driver.rdeps.entry(dep.clone()).or_default();
-				rdep.push(task.clone());
-				has_depends = true;
-			}
-
-			if has_depends {
-				driver.tasks_blocked.insert(task);
-			} else {
-				driver.tasks_runnable.push(task);
-			}
-		}
-
-		Ok(driver)
-	}
-
-	fn task_setup(task_ref: &TaskRef<'ctx>) -> Vec<&'static str> {
-		let mut ret = vec![indoc! {"
-			export PATH={{build.prefix}}/sbin:{{build.prefix}}/bin:$PATH
-			cd {{workdir}}
-
-			export SOURCE_DATE_EPOCH=1
-
-			export AR_FOR_BUILD=ar
-			export AS_FOR_BUILD=as
-			export DLLTOOL_FOR_BUILD=dlltool
-			export CC_FOR_BUILD=gcc
-			export CXX_FOR_BUILD=g++
-			export GCC_FOR_BUILD=gcc
-			export GFORTRAN_FOR_BUILD=gfortran
-			export GOC_FOR_BUILD=goc
-			export LD_FOR_BUILD=ld
-			export LIPO_FOR_BUILD=lipo
-			export NM_FOR_BUILD=nm
-			export OBJCOPY_FOR_BUILD=objcopy
-			export OBJDUMP_FOR_BUILD=objdump
-			export RANLIB_FOR_BUILD=ranlib
-			export STRIP_FOR_BUILD=strip
-			export WINDRES_FOR_BUILD=windres
-			export WINDMC_FOR_BUILD=windmc
-		"}];
-
-		if task_ref.args.contains_key("build_to_host") {
-			ret.push(indoc! {"
-				export AR={{build_to_host.cross_compile}}ar
-				export AS={{build_to_host.cross_compile}}as
-				export DLLTOOL={{build_to_host.cross_compile}}dlltool
-				export CC={{build_to_host.cross_compile}}gcc
-				export CXX={{build_to_host.cross_compile}}g++
-				export GCC={{build_to_host.cross_compile}}gcc
-				export GFORTRAN={{build_to_host.cross_compile}}gfortran
-				export GOC={{build_to_host.cross_compile}}goc
-				export LD={{build_to_host.cross_compile}}ld
-				export LIPO={{build_to_host.cross_compile}}lipo
-				export NM={{build_to_host.cross_compile}}nm
-				export OBJCOPY={{build_to_host.cross_compile}}objcopy
-				export OBJDUMP={{build_to_host.cross_compile}}objdump
-				export RANLIB={{build_to_host.cross_compile}}ranlib
-				export STRIP={{build_to_host.cross_compile}}strip
-				export WINDRES={{build_to_host.cross_compile}}windres
-				export WINDMC={{build_to_host.cross_compile}}windmc
-			"});
-		}
-
-		if task_ref.args.contains_key("build_to_target") {
-			ret.push(indoc! {"
-				export AR_FOR_TARGET={{build_to_target.cross_compile}}ar
-				export AS_FOR_TARGET={{build_to_target.cross_compile}}as
-				export DLLTOOL_FOR_TARGET={{build_to_target.cross_compile}}dlltool
-				export CC_FOR_TARGET={{build_to_target.cross_compile}}gcc
-				export CXX_FOR_TARGET={{build_to_target.cross_compile}}g++
-				export GCC_FOR_TARGET={{build_to_target.cross_compile}}gcc
-				export GFORTRAN_FOR_TARGET={{build_to_target.cross_compile}}gfortran
-				export GOC_FOR_TARGET={{build_to_target.cross_compile}}goc
-				export LD_FOR_TARGET={{build_to_target.cross_compile}}ld
-				export LIPO_FOR_TARGET={{build_to_target.cross_compile}}lipo
-				export NM_FOR_TARGET={{build_to_target.cross_compile}}nm
-				export OBJCOPY_FOR_TARGET={{build_to_target.cross_compile}}objcopy
-				export OBJDUMP_FOR_TARGET={{build_to_target.cross_compile}}objdump
-				export RANLIB_FOR_TARGET={{build_to_target.cross_compile}}ranlib
-				export STRIP_FOR_TARGET={{build_to_target.cross_compile}}strip
-				export WINDRES_FOR_TARGET={{build_to_target.cross_compile}}windres
-				export WINDMC_FOR_TARGET={{build_to_target.cross_compile}}windmc
-			"});
-		}
-		ret
-	}
-
-	fn update_runnable(&mut self, task_ref: TaskRef<'ctx>, task_output: TaskOutput) {
-		let rdeps = self.rdeps.get(&task_ref);
-
-		self.state.tasks_done.insert(task_ref, task_output);
-
-		for rdep in rdeps.unwrap_or(&Vec::new()) {
-			if !self.tasks_blocked.contains(rdep) {
-				continue;
-			}
-			if self.state.deps_satisfied(rdep) {
-				self.tasks_blocked.remove(rdep);
-				self.tasks_runnable.push(rdep.clone());
-			}
-		}
-	}
-
-	fn spawn_task(&self, task_ref: &TaskRef<'ctx>, runner: &Runner) -> Result<SpawnResult> {
-		let task_def = &self.state.ctx[task_ref];
-		if task_def.action.is_empty() {
-			println!("Skipping empty task {:#}", task_ref);
-			return Ok(SpawnResult::Skipped(TaskOutput::default()));
-		}
-
-		let task_deps = self.state.task_deps(task_ref)?;
-		let task_output = task_def
-			.output
-			.iter()
-			.map(|(name, Output { path, .. })| {
-				let output_path = if let Some(path) = path {
-					format!("{}/{}", paths::TASK_DESTDIR, path)
-				} else {
-					paths::TASK_DESTDIR.to_string()
-				};
-				(name.clone(), output_path)
-			})
-			.collect();
-
-		let inherit_chain = self.state.task_inherit_chain(task_ref);
-
-		let mut run = Self::task_setup(task_ref);
-		run.push(&task_def.action.run);
-
-		let command = template::ENGINE
-			.eval(&run.concat(), &task_ref.args)
-			.with_context(|| {
-				format!("Failed to evaluate command template for task {}", task_ref)
-			})?;
-
-		let rootfs = self.state.ctx.get_rootfs();
-		let task = Task {
-			label: format!("{:#}", task_ref),
-			command,
-			workdir: paths::TASK_WORKDIR.to_string(),
-			rootfs: rootfs.0,
-			inherit: inherit_chain,
-			depends: task_deps,
-			outputs: task_output,
-			pins: HashMap::from([rootfs.clone()]),
-			force_run: self.force_run.contains(task_ref),
-		};
-
-		Ok(SpawnResult::Spawned(runner.spawn(&task)))
-	}
-
-	fn run_task(&mut self, task_ref: TaskRef<'ctx>, runner: &Runner) -> Result<()> {
-		match self.spawn_task(&task_ref, runner)? {
-			SpawnResult::Spawned(socket) => {
-				assert!(self
-					.tasks_running
-					.insert(socket.as_raw_fd(), (socket, task_ref))
-					.is_none());
-			}
-			SpawnResult::Skipped(result) => {
-				self.update_runnable(task_ref, result);
-			}
-		}
-		Ok(())
-	}
-
-	fn run_tasks(&mut self, runner: &Runner) -> Result<()> {
-		while let Some(task_ref) = self.tasks_runnable.pop() {
-			self.run_task(task_ref, runner)?;
-		}
-		Ok(())
-	}
-
-	fn wait_for_task(&mut self) -> Result<()> {
-		let mut pollfds: Vec<_> = self
-			.tasks_running
-			.values()
-			.map(|(socket, _)| poll::PollFd::new(socket, poll::PollFlags::POLLIN))
-			.collect();
-
-		while poll::poll(&mut pollfds, -1).context("poll()")? == 0 {}
-
-		let pollevents: Vec<_> = pollfds
-			.into_iter()
-			.map(|pollfd| {
-				(
-					pollfd.as_fd().as_raw_fd(),
-					pollfd.revents().expect("Unknown events in poll() return"),
-				)
-			})
-			.collect();
-
-		for (fd, events) in pollevents {
-			if !events.contains(poll::PollFlags::POLLIN) {
-				if events.intersects(!poll::PollFlags::POLLIN) {
-					return Err(Error::new(
-						"Unexpected error status for socket file descriptor",
-					));
-				}
-				continue;
-			}
-
-			let (socket, task_ref) = self.tasks_running.remove(&fd).unwrap();
-
-			let task_output = Runner::result(&socket)?;
-			self.update_runnable(task_ref, task_output);
-		}
-
-		Ok(())
-	}
-
-	fn is_empty(&self) -> bool {
-		self.tasks_runnable.is_empty() && self.tasks_running.is_empty()
-	}
-
-	fn is_done(&self) -> bool {
-		self.is_empty() && self.tasks_blocked.is_empty()
-	}
-
-	pub fn run(&mut self, runner: &Runner) -> Result<()> {
-		while !self.is_empty() {
-			self.run_tasks(runner)?;
-			self.wait_for_task()?;
-		}
-
-		assert!(self.is_done(), "No runnable tasks left");
-
-		self.state.print_summary();
-
-		Ok(())
-	}
-}
diff --git a/crates/driver/src/parse.rs b/crates/driver/src/parse.rs
deleted file mode 100644
index aad9360..0000000
--- a/crates/driver/src/parse.rs
+++ /dev/null
@@ -1,95 +0,0 @@
-use nom::{
-	bytes::complete::{tag, take_while1},
-	combinator::{all_consuming, opt},
-	error::ParseError,
-	Err, IResult, InputLength, Parser,
-};
-
-#[derive(Debug, Clone, Copy)]
-pub struct Task<'a> {
-	pub recipe: &'a str,
-	pub task: &'a str,
-	pub host: Option<&'a str>,
-	pub target: Option<&'a str>,
-}
-
-#[derive(Debug, Clone, Copy)]
-pub struct TaskFlags {
-	pub force_run: bool,
-}
-
-fn is_name_char(c: char) -> bool {
-	matches!(c, 'a'..='z' | 'A' ..='Z' | '0'..='9' | '_' | '-')
-}
-
-fn name(input: &str) -> IResult<&str, &str> {
-	take_while1(is_name_char)(input)
-}
-
-fn task_id(input: &str) -> IResult<&str, (&str, &str)> {
-	let (input, recipe) = name(input)?;
-	let (input, _) = tag(":")(input)?;
-	let (input, task) = name(input)?;
-	Ok((input, (recipe, task)))
-}
-
-fn task_arg_target(input: &str) -> IResult<&str, &str> {
-	let (input, _) = tag(":")(input)?;
-	let (input, target) = name(input)?;
-	Ok((input, target))
-}
-
-fn task_args(input: &str) -> IResult<&str, (Option<&str>, Option<&str>)> {
-	let (input, _) = tag("/")(input)?;
-	let (input, host) = opt(name)(input)?;
-	let (input, target) = opt(task_arg_target)(input)?;
-
-	Ok((input, (host, target)))
-}
-
-fn task(input: &str) -> IResult<&str, Task> {
-	let (input, (recipe, task)) = task_id(input)?;
-	let (input, args) = opt(task_args)(input)?;
-
-	let (host, target) = args.unwrap_or_default();
-
-	Ok((
-		input,
-		Task {
-			recipe,
-			task,
-			host,
-			target,
-		},
-	))
-}
-
-fn task_flags(input: &str) -> IResult<&str, TaskFlags> {
-	let (input, force_run) = opt(tag("+"))(input)?;
-
-	Ok((
-		input,
-		TaskFlags {
-			force_run: force_run.is_some(),
-		},
-	))
-}
-
-fn task_with_flags(input: &str) -> IResult<&str, (Task, TaskFlags)> {
-	let (input, task) = task(input)?;
-	let (input, flags) = task_flags(input)?;
-
-	Ok((input, (task, flags)))
-}
-
-fn parse_all<I, O, E: ParseError<I>, F>(f: F, input: I) -> Result<O, Err<E>>
-where
-	I: InputLength,
-	F: Parser<I, O, E>,
-{
-	all_consuming(f)(input).map(|(_, result)| result)
-}
-
-pub fn parse_task_with_flags(input: &str) -> Option<(Task, TaskFlags)> {
-	parse_all(task_with_flags, input).ok()
-}
diff --git a/crates/driver/src/recipe.rs b/crates/driver/src/recipe.rs
deleted file mode 100644
index 474096b..0000000
--- a/crates/driver/src/recipe.rs
+++ /dev/null
@@ -1,97 +0,0 @@
-use std::{collections::HashMap, fs::File, path::Path, result};
-
-use scoped_tls_hkt::scoped_thread_local;
-use serde::{Deserialize, Deserializer};
-use walkdir::WalkDir;
-
-use common::{error::*, types::*};
-
-use crate::task::{RecipeMeta, TaskDef};
-
-scoped_thread_local!(static CURRENT_RECIPE: str);
-
-fn current_recipe() -> String {
-	CURRENT_RECIPE.with(|current| current.to_string())
-}
-
-pub fn deserialize_task_id<'de, D>(deserializer: D) -> result::Result<TaskID, D::Error>
-where
-	D: Deserializer<'de>,
-{
-	#[derive(Deserialize)]
-	struct RecipeTaskID {
-		recipe: Option<String>,
-		task: String,
-	}
-	let RecipeTaskID { recipe, task } = RecipeTaskID::deserialize(deserializer)?;
-	Ok(TaskID {
-		recipe: recipe.unwrap_or_else(current_recipe),
-		task,
-	})
-}
-
-#[derive(Debug, Deserialize)]
-struct Recipe {
-	#[serde(default)]
-	pub meta: RecipeMeta,
-	pub tasks: HashMap<String, TaskDef>,
-}
-
-fn read_recipe(path: &Path) -> Result<Recipe> {
-	let f = File::open(path).context("IO error")?;
-
-	let recipe: Recipe = serde_yaml::from_reader(f)
-		.map_err(Error::new)
-		.context("YAML error")?;
-
-	Ok(recipe)
-}
-
-fn is_yml(path: &Path) -> bool {
-	path.extension() == Some("yml".as_ref())
-}
-
-pub fn read_recipes<P: AsRef<Path>>(path: P) -> Result<HashMap<TaskID, Vec<TaskDef>>> {
-	let mut tasks = HashMap::<TaskID, Vec<TaskDef>>::new();
-
-	for entry in WalkDir::new(path)
-		.sort_by_file_name()
-		.into_iter()
-		.filter_map(|e| e.ok())
-	{
-		let path = entry.path();
-		if !path.is_file() || !is_yml(path) {
-			continue;
-		}
-
-		let stem: &str = match path.file_stem().map(|n| n.to_str()) {
-			Some(Some(v)) => v,
-			_ => continue,
-		};
-		let (basename, version) = match stem.split_once('@') {
-			Some((basename, version)) => (basename, Some(version)),
-			None => (stem, None),
-		};
-
-		let recipe = CURRENT_RECIPE.set(basename, || read_recipe(path))?;
-
-		let mut meta = recipe.meta;
-		if meta.name.is_empty() {
-			meta.name = basename.to_string();
-		}
-		if meta.version.is_none() {
-			meta.version = version.map(|v| v.to_string());
-		}
-
-		for (label, mut task) in recipe.tasks {
-			let task_id = TaskID {
-				recipe: basename.to_string(),
-				task: label,
-			};
-			task.meta = meta.clone();
-			tasks.entry(task_id).or_default().push(task);
-		}
-	}
-
-	Ok(tasks)
-}
diff --git a/crates/common/Cargo.toml b/crates/rebel-common/Cargo.toml
index 954ebe5..954ebe5 100644
--- a/crates/common/Cargo.toml
+++ b/crates/rebel-common/Cargo.toml
diff --git a/crates/common/src/error.rs b/crates/rebel-common/src/error.rs
index ba25af4..ba25af4 100644
--- a/crates/common/src/error.rs
+++ b/crates/rebel-common/src/error.rs
diff --git a/crates/common/src/lib.rs b/crates/rebel-common/src/lib.rs
index 8d630dd..8d630dd 100644
--- a/crates/common/src/lib.rs
+++ b/crates/rebel-common/src/lib.rs
diff --git a/crates/common/src/string_hash.rs b/crates/rebel-common/src/string_hash.rs
index a2b00db..a2b00db 100644
--- a/crates/common/src/string_hash.rs
+++ b/crates/rebel-common/src/string_hash.rs
diff --git a/crates/common/src/types.rs b/crates/rebel-common/src/types.rs
index 32b9182..d3beb70 100644
--- a/crates/common/src/types.rs
+++ b/crates/rebel-common/src/types.rs
@@ -13,9 +13,30 @@ pub struct TaskID {
 	pub task: String,
 }
 
+impl TaskID {
+	pub fn as_ref(&self) -> TaskIDRef<'_> {
+		TaskIDRef {
+			recipe: &self.recipe,
+			task: &self.task,
+		}
+	}
+}
+
 impl Display for TaskID {
 	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-		write!(f, "{}:{}", self.recipe, self.task)
+		self.as_ref().fmt(f)
+	}
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+pub struct TaskIDRef<'a> {
+	pub recipe: &'a str,
+	pub task: &'a str,
+}
+
+impl<'a> Display for TaskIDRef<'a> {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		write!(f, "{}::{}", self.recipe, self.task)
 	}
 }
 
@@ -39,7 +60,7 @@ pub struct Task {
 	pub command: String,
 	pub workdir: String,
 	pub rootfs: ArchiveHash,
-	pub inherit: Vec<LayerHash>,
+	pub ancestors: Vec<LayerHash>,
 	pub depends: HashSet<Dependency>,
 	pub outputs: HashMap<String, String>,
 	pub pins: HashMap<ArchiveHash, String>,
diff --git a/crates/rebel-lang/Cargo.toml b/crates/rebel-lang/Cargo.toml
new file mode 100644
index 0000000..a0a04a6
--- /dev/null
+++ b/crates/rebel-lang/Cargo.toml
@@ -0,0 +1,24 @@
+[package]
+name = "rebel-lang"
+version = "0.1.0"
+authors = ["Matthias Schiffer <mschiffer@universe-factory.net>"]
+license = "MIT"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+rebel-common = { path = "../rebel-common" }
+rebel-parse = { path = "../rebel-parse" }
+
+enum-kinds = "0.5.1"
+rustc-hash = "1.1.0"
+
+[dev-dependencies]
+clap = { version = "4.0.0", features = ["derive"] }
+divan = "0.1.14"
+reedline = "0.32.0"
+
+[[bench]]
+name = "recipe"
+harness = false
diff --git a/crates/rebel-lang/benches/recipe.rs b/crates/rebel-lang/benches/recipe.rs
new file mode 100644
index 0000000..fe017f5
--- /dev/null
+++ b/crates/rebel-lang/benches/recipe.rs
@@ -0,0 +1,104 @@
+use rebel_lang::{
+	scope::Scope,
+	typing::{self, Type, VarType},
+	value::{self, Value},
+};
+use rebel_parse::ast;
+
+fn main() {
+	divan::main();
+}
+
+const RECIPE: &str = include_str!("../../../examples/recipes/gmp/build.recipe");
+
+fn recipe() -> ast::Recipe<'static> {
+	let tokens = rebel_parse::tokenize::token_stream(RECIPE).unwrap();
+	rebel_parse::recipe::recipe(&tokens).unwrap()
+}
+
+fn type_scope() -> Box<Scope<VarType>> {
+	let mut scope = Box::<Scope<_>>::default();
+
+	scope.defs.insert_value("workdir", VarType::new(Type::Str));
+	scope.initialize("workdir");
+	scope.defs.insert_value("name", VarType::new(Type::Str));
+	scope.initialize("name");
+
+	scope
+}
+
+fn value_scope() -> Box<Scope<Value>> {
+	let mut scope = Box::<Scope<_>>::default();
+
+	scope
+		.defs
+		.insert_value("workdir", Value::Str("workdir".to_owned()));
+	scope
+		.defs
+		.insert_value("name", Value::Str("gpm".to_owned()));
+
+	scope
+}
+
+#[divan::bench]
+fn validate(bencher: divan::Bencher) {
+	let recipe = recipe();
+
+	bencher.bench(|| {
+		for stmt in divan::black_box(&recipe) {
+			stmt.validate().unwrap();
+		}
+	});
+}
+
+#[divan::bench]
+fn typecheck(bencher: divan::Bencher) {
+	let recipe = recipe();
+	let scope = type_scope();
+
+	for stmt in &recipe {
+		stmt.validate().unwrap();
+	}
+
+	bencher
+		.with_inputs(|| scope.clone())
+		.bench_local_values(|mut scope| {
+			let mut ctx = typing::Context(&mut scope);
+
+			for stmt in divan::black_box(&recipe) {
+				let ast::RecipeStmt::BlockStmt(stmt) = stmt else {
+					// TODO: Check other statements
+					continue;
+				};
+
+				ctx.type_block_stmt(stmt).unwrap();
+			}
+			scope
+		});
+}
+
+#[divan::bench]
+fn execute(bencher: divan::Bencher) {
+	let recipe = recipe();
+	let scope = value_scope();
+
+	for stmt in &recipe {
+		stmt.validate().unwrap();
+	}
+
+	bencher
+		.with_inputs(|| scope.clone())
+		.bench_local_values(|mut scope| {
+			let mut ctx = value::Context(&mut scope);
+
+			for stmt in divan::black_box(&recipe) {
+				let ast::RecipeStmt::BlockStmt(stmt) = stmt else {
+					// TODO: Execute other statements
+					continue;
+				};
+
+				ctx.eval_block_stmt(stmt).unwrap();
+			}
+			scope
+		});
+}
diff --git a/crates/rebel-lang/examples/repl.rs b/crates/rebel-lang/examples/repl.rs
new file mode 100644
index 0000000..3e0c319
--- /dev/null
+++ b/crates/rebel-lang/examples/repl.rs
@@ -0,0 +1,141 @@
+use std::rc::Rc;
+
+use rebel_lang::{
+	func::{Func, FuncDef, FuncType},
+	scope::{MethodMap, Scope},
+	typing::{self, Type, TypeFamily, VarType},
+	value::{self, Value},
+	Error, Result,
+};
+use rebel_parse::{recipe, tokenize};
+use reedline::{DefaultPrompt, DefaultPromptSegment, Reedline, Signal, ValidationResult};
+
+fn intrinsic_array_len(params: &[Value]) -> Result<Value> {
+	assert!(params.len() == 1);
+	let Value::Array(array) = &params[0] else {
+		panic!();
+	};
+	Ok(Value::Int(
+		array
+			.len()
+			.try_into()
+			.or(Err(Error::eval("array length out of bounds")))?,
+	))
+}
+fn intrinsic_string_len(params: &[Value]) -> Result<Value> {
+	assert!(params.len() == 1);
+	let Value::Str(string) = &params[0] else {
+		panic!();
+	};
+	Ok(Value::Int(
+		string
+			.chars()
+			.count()
+			.try_into()
+			.or(Err(Error::eval("string length out of bounds")))?,
+	))
+}
+
+struct Validator;
+
+impl reedline::Validator for Validator {
+	fn validate(&self, line: &str) -> ValidationResult {
+		if tokenize::token_stream(line).is_ok() {
+			ValidationResult::Complete
+		} else {
+			ValidationResult::Incomplete
+		}
+	}
+}
+
+fn main() {
+	let mut methods = MethodMap::default();
+	methods.entry(TypeFamily::Array).or_default().insert(
+		"len",
+		Func {
+			typ: FuncType {
+				params: vec![Type::Array(Box::new(Type::Free))],
+				ret: Type::Int,
+			},
+			def: FuncDef::Intrinsic(intrinsic_array_len),
+		},
+	);
+	methods.entry(TypeFamily::Str).or_default().insert(
+		"len",
+		Func {
+			typ: FuncType {
+				params: vec![Type::Str],
+				ret: Type::Int,
+			},
+			def: FuncDef::Intrinsic(intrinsic_string_len),
+		},
+	);
+	let methods = Rc::new(methods);
+
+	let mut type_scope = Box::<Scope<VarType>>::default();
+	type_scope.methods = methods.clone();
+	let mut value_scope = Box::<Scope<Value>>::default();
+	value_scope.methods = methods.clone();
+
+	let mut rl = Reedline::create().with_validator(Box::new(Validator));
+	let prompt = DefaultPrompt::new(DefaultPromptSegment::Empty, DefaultPromptSegment::Empty);
+
+	'repl: loop {
+		let input = match rl.read_line(&prompt).unwrap() {
+			Signal::Success(input) => input,
+			Signal::CtrlC => continue,
+			Signal::CtrlD => break,
+		};
+
+		let tokens = match tokenize::token_stream(&input) {
+			Ok(value) => value,
+			Err(err) => {
+				println!("Tokenize error: {err}");
+				continue;
+			}
+		};
+		let block = match recipe::block(&tokens) {
+			Ok(value) => value,
+			Err(err) => {
+				println!("Parse error: {err}");
+				continue;
+			}
+		};
+
+		let mut type_scope_tmp = type_scope.clone();
+		let mut value_scope_tmp = value_scope.clone();
+
+		let mut typ = Type::unit();
+		let mut value = Value::unit();
+
+		for stmt in &block.0 {
+			if let Err(err) = stmt.validate() {
+				println!("Validation error: {err:?}");
+				continue 'repl;
+			}
+
+			typ = match typing::Context(&mut type_scope_tmp).type_block_stmt(stmt) {
+				Ok(typ) => typ,
+				Err(err) => {
+					println!("Type checking failed: {err}");
+					continue 'repl;
+				}
+			};
+
+			value = match value::Context(&mut value_scope_tmp).eval_block_stmt(stmt) {
+				Ok(value) => value,
+				Err(err) => {
+					println!("Evaluation failed: {err}");
+					continue 'repl;
+				}
+			};
+		}
+
+		if value != Value::unit() {
+			println!("{value}: {typ}");
+		}
+
+		type_scope = type_scope_tmp;
+		value_scope = value_scope_tmp;
+	}
+}
diff --git a/crates/rebel-lang/src/func.rs b/crates/rebel-lang/src/func.rs
new file mode 100644
index 0000000..19d3ea0
--- /dev/null
+++ b/crates/rebel-lang/src/func.rs
@@ -0,0 +1,33 @@
+use std::fmt::Display;
+
+use rebel_parse::ast::Block;
+
+use crate::{typing::Type, value::Value, Result};
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct Func {
+	pub typ: FuncType,
+	pub def: FuncDef,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct FuncType {
+	pub params: Vec<Type>,
+	pub ret: Type,
+}
+
+impl Display for FuncType {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		// TODO
+		write!(f, "fn( ... ) -> {}", self.ret)
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum FuncDef {
+	Intrinsic(fn(&[Value]) -> Result<Value>),
+	Body {
+		param_names: Vec<String>,
+		block: Block<'static>,
+	},
+}
diff --git a/crates/rebel-lang/src/lib.rs b/crates/rebel-lang/src/lib.rs
new file mode 100644
index 0000000..001bb79
--- /dev/null
+++ b/crates/rebel-lang/src/lib.rs
@@ -0,0 +1,36 @@
+use std::fmt::Display;
+
+pub mod func;
+pub mod scope;
+pub mod typing;
+pub mod value;
+
+#[derive(Debug)]
+pub struct Error(pub &'static str, pub &'static str);
+
+impl Error {
+	pub fn lookup(text: &'static str) -> Self {
+		Self("Lookup", text)
+	}
+
+	pub fn typ(text: &'static str) -> Self {
+		Self("Type", text)
+	}
+
+	pub fn eval(text: &'static str) -> Self {
+		Self("Eval", text)
+	}
+
+	pub fn bug(text: &'static str) -> Self {
+		Self("BUG", text)
+	}
+}
+
+impl Display for Error {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		let Error(cat, text) = self;
+		write!(f, "{cat} error: {text}")
+	}
+}
+
+pub type Result<T> = std::result::Result<T, Error>;
diff --git a/crates/rebel-lang/src/scope.rs b/crates/rebel-lang/src/scope.rs
new file mode 100644
index 0000000..decb427
--- /dev/null
+++ b/crates/rebel-lang/src/scope.rs
@@ -0,0 +1,277 @@
+use std::{borrow::Cow, mem, rc::Rc};
+
+use rebel_parse::ast::{self, pat};
+use rustc_hash::{FxHashMap, FxHashSet};
+
+use crate::{
+	func::Func,
+	typing::{Type, TypeFamily},
+	Error, Result,
+};
+
+pub type MethodMap = FxHashMap<TypeFamily, FxHashMap<&'static str, Func>>;
+
+#[derive(Debug, Clone)]
+pub struct Scope<T> {
+	pub defs: Module<T>,
+	pub initialized: Rc<FxHashSet<String>>,
+	pub methods: Rc<MethodMap>,
+	pub parent: Option<Box<Scope<T>>>,
+	pub upvalue_initialized: FxHashSet<String>,
+}
+
+impl<T> Default for Scope<T> {
+	fn default() -> Self {
+		let mut ret = Scope {
+			defs: Module::default(),
+			initialized: Rc::default(),
+			methods: Rc::default(),
+			parent: None,
+			upvalue_initialized: FxHashSet::default(),
+		};
+
+		// Type "prelude"
+		ret.defs.insert_type("bool", Type::Bool);
+		ret.defs.insert_type("int", Type::Int);
+		ret.defs.insert_type("str", Type::Str);
+
+		ret
+	}
+}
+
+impl<T> Scope<T> {
+	pub fn is_initialized(&self, path: &ast::Path) -> bool {
+		// TODO: What to do about other paths?
+		if let [ident] = &path.components[..] {
+			self.initialized.contains(ident.name.as_ref())
+		} else {
+			true
+		}
+	}
+
+	pub fn initialize(&mut self, ident: &str) {
+		if !self.initialized.contains(ident) {
+			Rc::make_mut(&mut self.initialized).insert(ident.to_owned());
+		}
+		if !self.defs.values.contains_key(ident) {
+			self.upvalue_initialized.insert(ident.to_owned());
+		}
+	}
+
+	pub fn initialize_all(&mut self, idents: impl IntoIterator<Item = impl AsRef<str>>) {
+		for ident in idents {
+			self.initialize(ident.as_ref());
+		}
+	}
+
+	pub fn func(&self) -> Self {
+		// TODO: Upvalues
+		Scope {
+			defs: Module::default(),
+			initialized: Rc::default(),
+			methods: self.methods.clone(),
+			parent: None,
+			upvalue_initialized: FxHashSet::default(),
+		}
+	}
+
+	pub fn scoped<F, R>(self: &mut Box<Self>, f: F) -> (R, FxHashSet<String>)
+	where
+		F: FnOnce(&mut Box<Self>) -> R,
+	{
+		let child = Box::new(Scope {
+			defs: Module::default(),
+			initialized: self.initialized.clone(),
+			methods: self.methods.clone(),
+			parent: None,
+			upvalue_initialized: FxHashSet::default(),
+		});
+		let scope = mem::replace(self, child);
+		self.parent = Some(scope);
+
+		let ret = f(self);
+
+		let parent = self.parent.take().unwrap();
+		let child = mem::replace(self, parent);
+		let Scope {
+			upvalue_initialized,
+			..
+		} = *child;
+
+		(ret, upvalue_initialized)
+	}
+
+	pub fn lookup_value(&self, path: &ast::Path) -> Result<&T> {
+		if path.root != ast::PathRoot::Relative {
+			return Err(Error::lookup("invalid path"));
+		}
+
+		let mut lookup_scope = Some(self);
+		while let Some(scope) = lookup_scope {
+			if scope.defs.contains_value(&path.components) {
+				return scope
+					.defs
+					.lookup_value(&path.components)
+					.ok_or(Error::lookup("unresolved path"));
+			}
+			lookup_scope = scope.parent.as_deref();
+		}
+
+		Err(Error::lookup("undefined variable"))
+	}
+
+	pub fn lookup_type(&self, path: &ast::Path) -> Result<&Type> {
+		if path.root != ast::PathRoot::Relative {
+			return Err(Error::lookup("invalid path"));
+		}
+		if path.components
+			== [ast::Ident {
+				name: Cow::Borrowed("_"),
+			}] {
+			return Ok(&Type::Free);
+		}
+
+		let mut lookup_scope = Some(self);
+		while let Some(scope) = lookup_scope {
+			if scope.defs.contains_type(&path.components) {
+				return scope
+					.defs
+					.lookup(&path.components)
+					.and_then(|def| def.typ.as_deref())
+					.ok_or(Error::lookup("unresolved path"));
+			}
+			lookup_scope = scope.parent.as_deref();
+		}
+
+		Err(Error::lookup("undefined type"))
+	}
+}
+
+impl<T: Clone> Scope<T> {
+	pub fn lookup_var_mut<'a>(&mut self, path: &ast::Path<'a>) -> Result<(&mut T, ast::Ident<'a>)> {
+		if path.root != ast::PathRoot::Relative {
+			return Err(Error::lookup("invalid path"));
+		}
+
+		let mut lookup_scope = Some(self);
+		while let Some(scope) = lookup_scope {
+			if scope.defs.contains_value(&path.components) {
+				return scope
+					.defs
+					.lookup_value_mut(&path.components)
+					.ok_or(Error::lookup("unresolved path"));
+			}
+			lookup_scope = scope.parent.as_deref_mut();
+		}
+
+		Err(Error::lookup("undefined variable"))
+	}
+}
+
+pub fn pat_ident<'a>(pat: &pat::Pat<'a>) -> ast::Ident<'a> {
+	match pat {
+		pat::Pat::Paren(subpat) => pat_ident(subpat),
+		pat::Pat::Ident(ident) => ident.clone(),
+	}
+}
+
+pub fn is_wildcard_destr_pat(pat: &pat::DestrPat) -> bool {
+	match pat {
+		pat::DestrPat::Index { .. } => false,
+		pat::DestrPat::Field { .. } => false,
+		pat::DestrPat::Paren(pat) => is_wildcard_destr_pat(pat),
+		pat::DestrPat::Path(path) => {
+			path.root == ast::PathRoot::Relative
+				&& path.components
+					== [ast::Ident {
+						name: Cow::Borrowed("_"),
+					}]
+		}
+	}
+}
+
+#[derive(Debug)]
+pub struct Module<T> {
+	pub values: FxHashMap<String, Rc<T>>,
+	pub typ: Option<Rc<Type>>,
+	pub children: Rc<FxHashMap<String, Module<T>>>,
+}
+
+impl<T> Module<T> {
+	pub fn contains_value(&self, path: &[ast::Ident<'_>]) -> bool {
+		match path {
+			[] => true,
+			[ident] => self.values.contains_key(ident.name.as_ref()),
+			[ident, ..] => self.children.contains_key(ident.name.as_ref()),
+		}
+	}
+
+	pub fn contains_type(&self, path: &[ast::Ident<'_>]) -> bool {
+		match path {
+			[] => true,
+			[ident, ..] => self.children.contains_key(ident.name.as_ref()),
+		}
+	}
+
+	pub fn insert_value(&mut self, ident: &str, value: T) {
+		self.values.insert(ident.to_owned(), Rc::new(value));
+	}
+
+	pub fn insert_type(&mut self, ident: &str, typ: Type) {
+		Rc::make_mut(&mut self.children)
+			.entry(ident.to_owned())
+			.or_default()
+			.typ = Some(Rc::new(typ));
+	}
+
+	pub fn lookup(&self, path: &[ast::Ident<'_>]) -> Option<&Module<T>> {
+		let Some((ident, rest)) = path.split_first() else {
+			return Some(self);
+		};
+
+		self.children.get(ident.name.as_ref())?.lookup(rest)
+	}
+
+	pub fn lookup_value(&self, path: &[ast::Ident<'_>]) -> Option<&T> {
+		let (ident, prefix) = path.split_last()?;
+		let module = self.lookup(prefix)?;
+		module.values.get(ident.name.as_ref()).map(Rc::as_ref)
+	}
+}
+
+impl<T: Clone> Module<T> {
+	pub fn lookup_value_mut<'a>(
+		&mut self,
+		path: &[ast::Ident<'a>],
+	) -> Option<(&mut T, ast::Ident<'a>)> {
+		if let [ident] = path {
+			return Some((
+				self.values.get_mut(ident.name.as_ref()).map(Rc::make_mut)?,
+				ident.clone(),
+			));
+		}
+
+		// TODO: Decide how to handle this case
+		None
+	}
+}
+
+impl<T> Default for Module<T> {
+	fn default() -> Self {
+		Self {
+			values: Default::default(),
+			typ: Default::default(),
+			children: Default::default(),
+		}
+	}
+}
+
+impl<T> Clone for Module<T> {
+	fn clone(&self) -> Self {
+		Self {
+			values: self.values.clone(),
+			typ: self.typ.clone(),
+			children: self.children.clone(),
+		}
+	}
+}
diff --git a/crates/rebel-lang/src/typing.rs b/crates/rebel-lang/src/typing.rs
new file mode 100644
index 0000000..34280cd
--- /dev/null
+++ b/crates/rebel-lang/src/typing.rs
@@ -0,0 +1,791 @@
+use std::{fmt::Display, iter, rc::Rc};
+
+use enum_kinds::EnumKind;
+
+use rebel_parse::ast::{self, expr, pat, typ};
+use rustc_hash::{FxHashMap, FxHashSet};
+
+use crate::{
+	func::FuncType,
+	scope::{self, Scope},
+	Error, Result,
+};
+
+#[derive(Debug)]
+pub struct Context<'scope>(pub &'scope mut Box<Scope<VarType>>);
+
+#[derive(Debug)]
+pub struct TypeContext<'scope, T>(pub &'scope Scope<T>);
+
+#[derive(Debug, Clone)]
+pub struct VarType {
+	pub explicit_type: Type,
+	pub inferred_type: Type,
+}
+
+impl VarType {
+	pub fn new(explicit_type: Type) -> Self {
+		VarType {
+			inferred_type: explicit_type.clone(),
+			explicit_type,
+		}
+	}
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum Coerce {
+	Common,
+	Compare,
+	Assign,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, EnumKind)]
+#[enum_kind(TypeFamily, derive(Hash))]
+pub enum Type {
+	Free,
+	Bool,
+	Int,
+	Str,
+	Option(Box<Type>),
+	Tuple(Vec<Type>),
+	Array(Box<Type>),
+	Map(OrdType, Box<Type>),
+	Struct(FxHashMap<String, Type>),
+	Fn(Box<FuncType>),
+}
+
+impl Type {
+	pub fn unit() -> Self {
+		Type::Tuple(Vec::new())
+	}
+
+	pub fn unify(self, other: Type, coerce: Coerce) -> Result<Type> {
+		use Type::*;
+
+		Ok(match (self, other) {
+			(Free, typ) => typ,
+			(typ, Free) => typ,
+			(Bool, Bool) => Bool,
+			(Int, Int) => Int,
+			(Str, Str) => Str,
+			(Option(self_inner), Option(other_inner)) => {
+				Option(Box::new(self_inner.unify(*other_inner, coerce)?))
+			}
+			(Option(self_inner), other_typ) => {
+				Option(Box::new(self_inner.unify(other_typ, coerce)?))
+			}
+			(self_typ, Option(other_inner)) if coerce != Coerce::Assign => {
+				Option(Box::new(self_typ.unify(*other_inner, coerce)?))
+			}
+			(Tuple(self_elems), Tuple(other_elems)) if self_elems.len() == other_elems.len() => {
+				Tuple(
+					self_elems
+						.into_iter()
+						.zip(other_elems.into_iter())
+						.map(|(t1, t2)| t1.unify(t2, coerce))
+						.collect::<Result<_>>()?,
+				)
+			}
+			(Array(self_inner), Array(other_inner)) => {
+				Array(Box::new(self_inner.unify(*other_inner, coerce)?))
+			}
+			(Map(self_key, self_value), Map(other_key, other_value)) if self_key == other_key => {
+				Map(self_key, Box::new(self_value.unify(*other_value, coerce)?))
+			}
+			(Struct(self_entries), Struct(mut other_entries)) => {
+				if self_entries.len() != other_entries.len() {
+					return Err(Error::typ("conflicting struct types"));
+				}
+				Struct(
+					self_entries
+						.into_iter()
+						.map(|(k, v)| {
+							let Some(v2) = other_entries.remove(&k) else {
+								return Err(Error::typ("conflicting struct types"));
+							};
+							Ok((k, v.unify(v2, coerce)?))
+						})
+						.collect::<Result<_>>()?,
+				)
+			}
+			_ => return Err(Error::typ("type conflict")),
+		})
+	}
+}
+
+impl From<OrdType> for Type {
+	fn from(value: OrdType) -> Self {
+		match value {
+			OrdType::Free => Type::Free,
+			OrdType::Int => Type::Int,
+			OrdType::Str => Type::Str,
+		}
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum OrdType {
+	Free,
+	Int,
+	Str,
+}
+
+impl OrdType {
+	pub fn unify(self, other: OrdType, _coerce: Coerce) -> Result<OrdType> {
+		use OrdType::*;
+
+		Ok(match (self, other) {
+			(Free, typ) => typ,
+			(typ, Free) => typ,
+			(Int, Int) => Int,
+			(Str, Str) => Str,
+			_ => return Err(Error::typ("type conflict")),
+		})
+	}
+}
+
+impl Display for OrdType {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		match self {
+			OrdType::Free => f.write_str("_"),
+			OrdType::Int => f.write_str("int"),
+			OrdType::Str => f.write_str("str"),
+		}
+	}
+}
+
+impl TryFrom<Type> for OrdType {
+	type Error = Error;
+
+	fn try_from(value: Type) -> Result<Self> {
+		Ok(match value {
+			Type::Free => OrdType::Free,
+			Type::Int => OrdType::Int,
+			Type::Str => OrdType::Str,
+			_ => return Err(Error::typ("invalid type for set/map key")),
+		})
+	}
+}
+
+impl<'scope> Context<'scope> {
+	pub fn type_block_stmt(&mut self, stmt: &ast::BlockStmt) -> Result<Type> {
+		Ok(match stmt {
+			ast::BlockStmt::Let { dest, expr } => {
+				let ast::TypedPat { pat, typ } = dest.as_ref();
+
+				let dest_ident = scope::pat_ident(pat);
+
+				let explicit_type = if let Some(typ) = typ {
+					let type_ctx = TypeContext(self.0);
+					type_ctx.type_type(typ)?
+				} else {
+					Type::Free
+				};
+
+				let expr_type = expr
+					.as_ref()
+					.map(|expr| {
+						let expr_type = self.type_expr(expr)?;
+						explicit_type
+							.clone()
+							.unify(expr_type.clone(), Coerce::Assign)?;
+						Ok(expr_type)
+					})
+					.transpose()?;
+
+				if dest_ident.name == "_" {
+					return Ok(Type::unit());
+				}
+
+				self.0
+					.defs
+					.insert_value(dest_ident.name.as_ref(), VarType::new(explicit_type));
+				Rc::make_mut(&mut self.0.initialized).remove(dest_ident.name.as_ref());
+
+				let Some(expr_type) = expr_type else {
+					return Ok(Type::unit());
+				};
+
+				self.assign_destr_pat_type(&pat::DestrPat::from(pat.borrowed()), expr_type)?
+			}
+			ast::BlockStmt::Assign { dest, expr } => {
+				let expr_type = self.type_expr(expr)?;
+				self.assign_destr_pat_type(dest, expr_type)?
+			}
+			ast::BlockStmt::Fn {
+				ident,
+				params,
+				ret,
+				block,
+			} => {
+				let typ = Type::Fn(Box::new(self.type_fn_def(params, ret.as_deref(), block)?));
+
+				// TODO: Reject in validation?
+				if ident.name == "_" {
+					return Ok(Type::unit());
+				}
+				self.0
+					.defs
+					.insert_value(ident.name.as_ref(), VarType::new(typ.clone()));
+				Rc::make_mut(&mut self.0.initialized).insert(ident.name.as_ref().to_owned());
+
+				typ
+			}
+			ast::BlockStmt::Expr { expr } => self.type_expr(expr)?,
+			ast::BlockStmt::Empty => Type::unit(),
+		})
+	}
+
+	fn type_fn_def(
+		&mut self,
+		params: &[ast::FuncParam],
+		ret: Option<&typ::Type>,
+		block: &ast::Block,
+	) -> Result<FuncType> {
+		let type_ctx = TypeContext(self.0);
+		let typ = type_ctx.type_fn_def(params, ret)?;
+
+		let mut scope = Box::new(self.0.func());
+
+		{
+			let defs = &mut scope.defs;
+			let initialized = Rc::make_mut(&mut scope.initialized);
+
+			for (param, param_type) in params.iter().zip(&typ.params) {
+				defs.insert_value(param.name.name.as_ref(), VarType::new(param_type.clone()));
+				initialized.insert(param.name.name.as_ref().to_owned());
+			}
+		}
+
+		typ.ret
+			.clone()
+			.unify(Context(&mut scope).type_block(block)?, Coerce::Assign)?;
+
+		Ok(typ)
+	}
+
+	pub fn type_expr(&mut self, expr: &expr::Expr<'_>) -> Result<Type> {
+		use expr::Expr::*;
+
+		match expr {
+			Binary { left, op, right } => self.type_binary_op(left, *op, right),
+			Unary { op, expr } => self.type_unary_op(*op, expr),
+			Apply { expr, params } => self.type_apply(expr, params),
+			Method {
+				expr,
+				method,
+				params,
+			} => self.type_method(expr, method, params),
+			Index { base, index } => self.type_index(base, index),
+			Field { base, field } => self.type_field(base, field),
+			Block(block) => self.type_block(block),
+			IfElse {
+				if_blocks,
+				else_block,
+			} => self.type_ifelse(if_blocks, else_block),
+			Paren(subexpr) => self.type_expr(subexpr),
+			Path(path) => self.type_path(path),
+			Literal(lit) => self.type_literal(lit),
+		}
+	}
+
+	fn type_binary_op(
+		&mut self,
+		left: &expr::Expr<'_>,
+		op: expr::OpBinary,
+		right: &expr::Expr<'_>,
+	) -> Result<Type> {
+		use expr::OpBinary::*;
+		use Type::*;
+
+		let tl = self.type_expr(left)?;
+		let tr = self.type_expr(right)?;
+
+		Ok(match (tl, op, tr) {
+			(Str, Add, Str) => Str,
+			(Int, Add, Int) => Int,
+			(Array(t1), Add, Array(t2)) => Array(Box::new(t1.unify(*t2, Coerce::Common)?)),
+			(Int, Sub, Int) => Int,
+			(Array(t1), Sub, Array(t2)) => {
+				(*t1).clone().unify(*t2, Coerce::Compare)?;
+				Array(t1)
+			}
+			(Int, Mul, Int) => Int,
+			(Int, Div, Int) => Int,
+			(Int, Rem, Int) => Int,
+			(Bool, And, Bool) => Bool,
+			(Bool, Or, Bool) => Bool,
+			(l, Eq, r) => {
+				l.unify(r, Coerce::Compare)?;
+				Bool
+			}
+			(l, Ne, r) => {
+				l.unify(r, Coerce::Compare)?;
+				Bool
+			}
+			(Int, Lt, Int) => Bool,
+			(Int, Le, Int) => Bool,
+			(Int, Ge, Int) => Bool,
+			(Int, Gt, Int) => Bool,
+			(Str, Lt, Str) => Bool,
+			(Str, Le, Str) => Bool,
+			(Str, Ge, Str) => Bool,
+			(Str, Gt, Str) => Bool,
+			_ => return Err(Error::typ("invalid types for operation")),
+		})
+	}
+
+	fn type_unary_op(&mut self, op: expr::OpUnary, expr: &expr::Expr<'_>) -> Result<Type> {
+		use expr::OpUnary::*;
+		use Type::*;
+
+		let typ = self.type_expr(expr)?;
+
+		Ok(match (op, typ) {
+			(Not, Bool) => Bool,
+			(Neg, Int) => Int,
+			_ => return Err(Error::typ("invalid type for operation")),
+		})
+	}
+
+	fn type_index(&mut self, base: &expr::Expr<'_>, index: &expr::Expr<'_>) -> Result<Type> {
+		use Type::*;
+
+		let base_type = self.type_expr(base)?;
+		let index_type = self.type_expr(index)?;
+
+		if let Array(elem_type) = base_type {
+			if index_type == Int {
+				return Ok(*elem_type);
+			}
+		} else if let Map(key_type, value_type) = base_type {
+			if Type::from(key_type)
+				.unify(index_type, Coerce::Assign)
+				.is_ok()
+			{
+				return Ok(*value_type);
+			}
+		}
+
+		Err(Error::typ("invalid types index operation"))
+	}
+
+	fn type_func(&mut self, func: FuncType, call_param_types: Vec<Result<Type>>) -> Result<Type> {
+		if func.params.len() != call_param_types.len() {
+			return Err(Error::typ("incorrect number of parameters"));
+		}
+
+		for (func_param_type, call_param_type) in func.params.iter().zip(call_param_types) {
+			func_param_type
+				.clone()
+				.unify(call_param_type?, Coerce::Assign)?;
+		}
+
+		Ok(func.ret)
+	}
+
+	fn type_apply(&mut self, expr: &expr::Expr<'_>, params: &[expr::Expr]) -> Result<Type> {
+		use Type::*;
+
+		let expr_type = self.type_expr(expr)?;
+
+		let Fn(func) = expr_type else {
+			return Err(Error::typ("invalid type for function call"));
+		};
+
+		let param_types = params.iter().map(|param| self.type_expr(param)).collect();
+
+		self.type_func(*func, param_types)
+	}
+
+	fn type_method(
+		&mut self,
+		expr: &expr::Expr<'_>,
+		method: &ast::Ident<'_>,
+		params: &[expr::Expr],
+	) -> Result<Type> {
+		let self_type = self.type_expr(expr)?;
+		let type_family = TypeFamily::from(&self_type);
+
+		let method = self
+			.0
+			.methods
+			.get(&type_family)
+			.and_then(|methods| methods.get(method.name.as_ref()))
+			.ok_or(Error::lookup("undefined method"))?
+			.typ
+			.clone();
+
+		let param_types = iter::once(Ok(self_type))
+			.chain(params.iter().map(|param| self.type_expr(param)))
+			.collect();
+
+		self.type_func(method, param_types)
+	}
+
+	fn type_field(&mut self, base: &expr::Expr<'_>, field: &ast::Ident<'_>) -> Result<Type> {
+		use Type::*;
+
+		let base_type = self.type_expr(base)?;
+		let name = field.name.as_ref();
+
+		Ok(match base_type {
+			Tuple(elems) => {
+				let index: usize = name.parse().or(Err(Error::typ("no such field")))?;
+				elems
+					.into_iter()
+					.nth(index)
+					.ok_or(Error::typ("no such field"))?
+			}
+			Struct(mut entries) => entries.remove(name).ok_or(Error::typ("no such field"))?,
+			_ => return Err(Error::typ("invalid field access base type")),
+		})
+	}
+
+	fn type_scope(&mut self, stmts: &[ast::BlockStmt]) -> Result<(Type, FxHashSet<String>)> {
+		let (ret, upvalues) = self.scoped(|ctx| {
+			let mut ret = Type::unit();
+			for stmt in stmts {
+				ret = ctx.type_block_stmt(stmt)?;
+			}
+			Ok(ret)
+		});
+		Ok((ret?, upvalues))
+	}
+
+	fn type_block(&mut self, block: &ast::Block) -> Result<Type> {
+		if let [ast::BlockStmt::Expr { expr }] = &block.0[..] {
+			return self.type_expr(expr);
+		}
+
+		let (ret, upvalues) = self.type_scope(&block.0)?;
+		self.0.initialize_all(upvalues);
+		Ok(ret)
+	}
+
+	fn type_ifelse(
+		&mut self,
+		if_blocks: &[(expr::Expr, ast::Block)],
+		else_block: &Option<Box<ast::Block>>,
+	) -> Result<Type> {
+		let (mut ret, mut common_upvalues) = if let Some(block) = else_block {
+			self.type_scope(&block.0)?
+		} else {
+			(Type::unit(), FxHashSet::default())
+		};
+
+		for (cond, block) in if_blocks {
+			Type::Bool.unify(self.type_expr(cond)?, Coerce::Assign)?;
+
+			let (typ, upvalues) = self.type_scope(&block.0)?;
+			ret = ret.unify(typ, Coerce::Common)?;
+			common_upvalues = &common_upvalues & &upvalues;
+		}
+
+		self.0.initialize_all(common_upvalues);
+
+		Ok(ret)
+	}
+
+	fn type_path(&self, path: &ast::Path<'_>) -> Result<Type> {
+		let var = self.0.lookup_value(path)?;
+		if !self.0.is_initialized(path) {
+			return Err(Error::typ("uninitialized variable"));
+		}
+		Ok(var.inferred_type.clone())
+	}
+
+	fn check_string_interp_type(typ: Type, kind: expr::StrKind) -> Result<()> {
+		match (typ, kind) {
+			(Type::Free, _) => Ok(()),
+			(Type::Bool, _) => Ok(()),
+			(Type::Int, _) => Ok(()),
+			(Type::Str, _) => Ok(()),
+			(Type::Option(inner), expr::StrKind::Script) => {
+				Self::check_string_interp_type(*inner, kind)
+			}
+			(Type::Tuple(elems), expr::StrKind::Script) => {
+				for elem in elems {
+					Self::check_string_interp_type(elem, kind)?;
+				}
+				Ok(())
+			}
+			(Type::Array(inner), expr::StrKind::Script) => {
+				Self::check_string_interp_type(*inner, kind)
+			}
+			_ => Err(Error::typ("invalid type for string interpolation")),
+		}
+	}
+
+	fn check_string_piece(&mut self, piece: &expr::StrPiece, kind: expr::StrKind) -> Result<()> {
+		let typ = match piece {
+			expr::StrPiece::Chars(_) => return Ok(()),
+			expr::StrPiece::Escape(_) => return Ok(()),
+			expr::StrPiece::Interp(expr) => self.type_expr(expr)?,
+		};
+		Self::check_string_interp_type(typ, kind)
+	}
+
+	fn type_literal(&mut self, lit: &expr::Literal<'_>) -> Result<Type> {
+		use expr::Literal;
+		use Type::*;
+
+		Ok(match lit {
+			Literal::Unit => Type::unit(),
+			Literal::None => Type::Option(Box::new(Type::Free)),
+			Literal::Bool(_) => Bool,
+			Literal::Int(_) => Int,
+			Literal::Str { pieces, kind } => {
+				for piece in pieces {
+					self.check_string_piece(piece, *kind)?;
+				}
+				Str
+			}
+			Literal::Tuple(elems) => Tuple(
+				elems
+					.iter()
+					.map(|elem| self.type_expr(elem))
+					.collect::<Result<_>>()?,
+			),
+			Literal::Array(elems) => Array(Box::new(
+				elems.iter().try_fold(Type::Free, |acc, elem| {
+					acc.unify(self.type_expr(elem)?, Coerce::Common)
+				})?,
+			)),
+			Literal::Map(entries) => {
+				let (key, value) = entries.iter().try_fold(
+					(Type::Free, Type::Free),
+					|(acc_key, acc_value), expr::MapEntry { key, value }| {
+						Ok((
+							acc_key.unify(self.type_expr(key)?, Coerce::Common)?,
+							acc_value.unify(self.type_expr(value)?, Coerce::Common)?,
+						))
+					},
+				)?;
+				Type::Map(key.try_into()?, Box::new(value))
+			}
+			Literal::Struct(entries) => {
+				if entries.is_empty() {
+					return Ok(Type::unit());
+				}
+				Struct(
+					entries
+						.iter()
+						.map(|expr::StructField { name, value }| {
+							Ok((name.as_ref().to_owned(), self.type_expr(value)?))
+						})
+						.collect::<Result<_>>()?,
+				)
+			}
+		})
+	}
+
+	#[allow(clippy::type_complexity)]
+	fn assign_destr_pat_type_with<'a, 'r, R: 'r>(
+		&mut self,
+		pat: &pat::DestrPat<'a>,
+		f: Box<dyn FnOnce(&mut Type, ast::Ident<'a>) -> Result<R> + 'r>,
+	) -> Result<R> {
+		let initialized = self.0.initialized.clone();
+		match pat {
+			pat::DestrPat::Index { base, index } => {
+				let index_type = self.type_expr(index)?;
+				self.assign_destr_pat_type_with(
+					base,
+					Box::new(|base_type, ident| {
+						if !initialized.contains(ident.name.as_ref()) {
+							return Err(Error::typ(
+								"tried to assign field of uninitialized variable",
+							));
+						}
+						match (base_type, index_type) {
+							(Type::Array(inner), Type::Int) => f(inner.as_mut(), ident),
+							(Type::Map(key_type, value_type), index_type) => {
+								*key_type = key_type
+									.clone()
+									.unify(OrdType::try_from(index_type)?, Coerce::Common)?;
+								f(value_type.as_mut(), ident)
+							}
+							_ => Err(Error::typ("invalid types for index operation")),
+						}
+					}),
+				)
+			}
+			pat::DestrPat::Field { base, field } => self.assign_destr_pat_type_with(
+				base,
+				Box::new(|typ, ident| {
+					if !initialized.contains(ident.name.as_ref()) {
+						return Err(Error::typ(
+							"tried to assign field of uninitialized variable",
+						));
+					}
+					match typ {
+						Type::Tuple(elems) => {
+							let index: Option<usize> = field.name.parse().ok();
+							f(
+								index
+									.and_then(|index| elems.get_mut(index))
+									.ok_or(Error::typ("no such field"))?,
+								ident,
+							)
+						}
+						Type::Struct(entries) => f(
+							entries
+								.get_mut(field.name.as_ref())
+								.ok_or(Error::typ("no such field"))?,
+							ident,
+						),
+						_ => Err(Error::typ("invalid field access base type")),
+					}
+				}),
+			),
+			pat::DestrPat::Paren(subpat) => self.assign_destr_pat_type_with(subpat, f),
+			pat::DestrPat::Path(path) => {
+				let (var, ident) = self.0.lookup_var_mut(path)?;
+				f(&mut var.inferred_type, ident)
+			}
+		}
+	}
+
+	fn assign_destr_pat_type(&mut self, dest: &pat::DestrPat, typ: Type) -> Result<Type> {
+		if scope::is_wildcard_destr_pat(dest) {
+			return Ok(Type::unit());
+		}
+
+		let (inferred_type, ident) = self.assign_destr_pat_type_with(
+			dest,
+			Box::new(|dest_type, ident| {
+				let inferred_type = dest_type.clone().unify(typ, Coerce::Common)?;
+				*dest_type = inferred_type.clone();
+
+				Ok((inferred_type, ident))
+			}),
+		)?;
+
+		self.0.initialize(ident.name.as_ref());
+
+		// TODO: Check explicit type
+
+		Ok(inferred_type)
+	}
+
+	fn scoped<F, R>(&mut self, f: F) -> (R, FxHashSet<String>)
+	where
+		F: FnOnce(&mut Context) -> R,
+	{
+		self.0.scoped(|scope| f(&mut Context(scope)))
+	}
+}
+
+impl<'scope, T> TypeContext<'scope, T> {
+	pub fn type_type(&self, typ: &typ::Type<'_>) -> Result<Type> {
+		use typ::Type::*;
+
+		Ok(match typ {
+			Paren(subtyp) => self.type_type(subtyp)?,
+			Option(subtyp) => Type::Option(Box::new(self.type_type(subtyp)?)),
+			Path(path) => self.type_type_path(path)?,
+			Literal(lit) => self.type_type_literal(lit)?,
+		})
+	}
+
+	fn type_type_path(&self, path: &ast::Path<'_>) -> Result<Type> {
+		self.0.lookup_type(path).cloned()
+	}
+
+	fn type_type_literal(&self, lit: &typ::Literal<'_>) -> Result<Type> {
+		use typ::Literal;
+		use Type::*;
+
+		Ok(match lit {
+			Literal::Unit => Type::unit(),
+			Literal::Tuple(elems) => Tuple(
+				elems
+					.iter()
+					.map(|elem| self.type_type(elem))
+					.collect::<Result<_>>()?,
+			),
+			Literal::Array(typ) => Array(Box::new(self.type_type(typ)?)),
+			Literal::Map(key, value) => Map(
+				self.type_type(key)?.try_into()?,
+				Box::new(self.type_type(value)?),
+			),
+			Literal::Struct(entries) => {
+				if entries.is_empty() {
+					return Ok(Type::unit());
+				}
+				Struct(
+					entries
+						.iter()
+						.map(|typ::StructField { name, typ }| {
+							Ok((name.as_ref().to_owned(), self.type_type(typ)?))
+						})
+						.collect::<Result<_>>()?,
+				)
+			}
+		})
+	}
+
+	pub fn type_fn_def(
+		&self,
+		params: &[ast::FuncParam],
+		ret: Option<&typ::Type>,
+	) -> Result<FuncType> {
+		let param_types: Vec<_> = params
+			.iter()
+			.map(|param| self.type_type(&param.typ))
+			.collect::<Result<_>>()?;
+		let ret_type = ret
+			.map(|typ| self.type_type(typ))
+			.transpose()?
+			.unwrap_or(Type::unit());
+
+		Ok(FuncType {
+			params: param_types,
+			ret: ret_type,
+		})
+	}
+}
+
+impl Display for Type {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		match self {
+			Type::Free => f.write_str("_"),
+			Type::Bool => f.write_str("bool"),
+			Type::Int => f.write_str("int"),
+			Type::Str => f.write_str("str"),
+			Type::Option(inner) => write!(f, "{inner}?"),
+			Type::Tuple(elems) => {
+				let mut first = true;
+				f.write_str("(")?;
+				for elem in elems {
+					if !first {
+						f.write_str(", ")?;
+					}
+					first = false;
+					elem.fmt(f)?;
+				}
+				if elems.len() == 1 {
+					f.write_str(",")?;
+				}
+				f.write_str(")")
+			}
+			Type::Array(typ) => write!(f, "[{typ}]"),
+			Type::Map(key, value) => write!(f, "map{{{key} => {value}}}"),
+			Type::Struct(entries) => {
+				let mut first = true;
+				f.write_str("{")?;
+				for (key, typ) in entries {
+					if !first {
+						f.write_str(", ")?;
+					}
+					first = false;
+					write!(f, "{key}: {typ}")?;
+				}
+				f.write_str("}")
+			}
+			/* TODO */
+			Type::Fn(func) => write!(f, "{func}"),
+		}
+	}
+}
diff --git a/crates/rebel-lang/src/value.rs b/crates/rebel-lang/src/value.rs
new file mode 100644
index 0000000..bca3fee
--- /dev/null
+++ b/crates/rebel-lang/src/value.rs
@@ -0,0 +1,713 @@
+use std::{
+	cell::RefCell,
+	fmt::{Display, Write},
+	iter,
+};
+
+use rebel_parse::ast::{self, expr, pat, typ};
+use rustc_hash::{FxHashMap, FxHashSet};
+
+use crate::{
+	func::{Func, FuncDef},
+	scope::{self, Scope},
+	typing::{Coerce, OrdType, Type, TypeContext, TypeFamily},
+	Error, Result,
+};
+
+#[derive(Debug)]
+pub struct Context<'scope>(pub &'scope mut Box<Scope<Value>>);
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum Value {
+	Uninitialized,
+	None,
+	Bool(bool),
+	Int(i64),
+	Str(String),
+	Tuple(Vec<Value>),
+	Map(FxHashMap<OrdValue, Value>),
+	Array(Vec<Value>),
+	Struct(FxHashMap<String, Value>),
+	Fn(Box<Func>),
+}
+
+impl Value {
+	pub fn unit() -> Self {
+		Value::Tuple(Vec::new())
+	}
+
+	pub fn typ(&self) -> Result<Type> {
+		Ok(match self {
+			Value::Uninitialized => return Err(Error::typ("uninitialized value")),
+			Value::None => Type::Option(Box::new(Type::Free)),
+			Value::Bool(_) => Type::Bool,
+			Value::Int(_) => Type::Int,
+			Value::Str(_) => Type::Str,
+			Value::Tuple(elems) => {
+				Type::Tuple(elems.iter().map(|elem| elem.typ()).collect::<Result<_>>()?)
+			}
+			Value::Array(elems) => Type::Array(Box::new(Self::common_type(elems)?)),
+			Value::Map(entries) => Type::Map(
+				Self::common_ord_type(entries.keys())?,
+				Box::new(Self::common_type(entries.values())?),
+			),
+			Value::Struct(entries) => Type::Struct(
+				entries
+					.iter()
+					.map(|(k, v)| Ok((k.clone(), v.typ()?)))
+					.collect::<Result<_>>()?,
+			),
+			Value::Fn(func) => Type::Fn(Box::new(func.typ.clone())),
+		})
+	}
+
+	fn common_type<'a>(values: impl IntoIterator<Item = &'a Value>) -> Result<Type> {
+		values.into_iter().try_fold(Type::Free, |acc, value| {
+			acc.unify(value.typ()?, Coerce::Common)
+		})
+	}
+
+	fn common_ord_type<'a>(values: impl IntoIterator<Item = &'a OrdValue>) -> Result<OrdType> {
+		values.into_iter().try_fold(OrdType::Free, |acc, value| {
+			acc.unify(value.typ()?, Coerce::Common)
+		})
+	}
+}
+
+impl From<OrdValue> for Value {
+	fn from(value: OrdValue) -> Self {
+		match value {
+			OrdValue::Int(v) => Value::Int(v),
+			OrdValue::Str(v) => Value::Str(v),
+		}
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub enum OrdValue {
+	Int(i64),
+	Str(String),
+}
+
+impl OrdValue {
+	pub fn typ(&self) -> Result<OrdType> {
+		Ok(match self {
+			OrdValue::Int(_) => OrdType::Int,
+			OrdValue::Str(_) => OrdType::Str,
+		})
+	}
+}
+
+impl Display for OrdValue {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		match self {
+			OrdValue::Int(value) => value.fmt(f),
+			OrdValue::Str(value) => write!(f, "{value:?}"),
+		}
+	}
+}
+
+impl TryFrom<Value> for OrdValue {
+	type Error = Error;
+
+	fn try_from(value: Value) -> Result<Self> {
+		Ok(match value {
+			Value::Int(v) => OrdValue::Int(v),
+			Value::Str(v) => OrdValue::Str(v),
+			_ => return Err(Error::bug("OrdValue from unordered value")),
+		})
+	}
+}
+
+impl<'scope> Context<'scope> {
+	pub fn eval_block_stmt(&mut self, stmt: &ast::BlockStmt) -> Result<Value> {
+		Ok(match stmt {
+			ast::BlockStmt::Let { dest, expr } => {
+				let ast::TypedPat { pat, typ: _ } = dest.as_ref();
+
+				let dest_ident = scope::pat_ident(pat);
+
+				let value = expr.as_ref().map(|expr| self.eval_expr(expr)).transpose()?;
+
+				if dest_ident.name == "_" {
+					return Ok(Value::unit());
+				}
+
+				self.0
+					.defs
+					.insert_value(dest_ident.name.as_ref(), Value::Uninitialized);
+
+				let Some(value) = value else {
+					return Ok(Value::unit());
+				};
+
+				self.assign_destr_pat_value(&pat::DestrPat::from(pat.borrowed()), value)?
+			}
+			ast::BlockStmt::Assign { dest, expr } => {
+				let value = self.eval_expr(expr)?;
+				self.assign_destr_pat_value(dest, value)?
+			}
+			ast::BlockStmt::Fn {
+				ident,
+				params,
+				ret,
+				block,
+			} => {
+				let value = Value::Fn(Box::new(self.eval_fn_def(params, ret.as_deref(), block)?));
+
+				// TODO: Reject in validation?
+				if ident.name == "_" {
+					return Ok(Value::unit());
+				}
+				self.0.defs.insert_value(ident.name.as_ref(), value.clone());
+
+				value
+			}
+			ast::BlockStmt::Expr { expr } => self.eval_expr(expr)?,
+			ast::BlockStmt::Empty => Value::unit(),
+		})
+	}
+
+	fn eval_fn_def(
+		&mut self,
+		params: &[ast::FuncParam],
+		ret: Option<&typ::Type>,
+		block: &ast::Block,
+	) -> Result<Func> {
+		let type_ctx = TypeContext(self.0);
+		let typ = type_ctx.type_fn_def(params, ret)?;
+
+		let param_names: Vec<_> = params
+			.iter()
+			.map(|param| param.name.name.as_ref().to_owned())
+			.collect();
+
+		Ok(Func {
+			typ,
+			def: FuncDef::Body {
+				param_names,
+				block: block.borrowed().into_owned(),
+			},
+		})
+	}
+
+	pub fn eval_expr(&mut self, expr: &expr::Expr<'_>) -> Result<Value> {
+		use expr::Expr::*;
+
+		match expr {
+			Binary { left, op, right } => self.eval_binary_op(left, *op, right),
+			Unary { op, expr } => self.eval_unary_op(*op, expr),
+			Apply { expr, params } => self.eval_apply(expr, params),
+			Method {
+				expr,
+				method,
+				params,
+			} => self.eval_method(expr, method, params),
+			Index { base, index } => self.eval_index(base, index),
+			Field { base, field } => self.eval_field(base, field),
+			Block(block) => self.eval_block(block),
+			IfElse {
+				if_blocks,
+				else_block,
+			} => self.eval_ifelse(if_blocks, else_block),
+			Paren(subexpr) => self.eval_expr(subexpr),
+			Path(path) => self.eval_path(path),
+			Literal(lit) => self.eval_literal(lit),
+		}
+	}
+
+	fn eval_binary_op(
+		&mut self,
+		left: &expr::Expr<'_>,
+		op: expr::OpBinary,
+		right: &expr::Expr<'_>,
+	) -> Result<Value> {
+		use expr::OpBinary::*;
+		use Value::*;
+
+		let tl = self.eval_expr(left)?;
+		let tr = self.eval_expr(right)?;
+
+		Ok(match (tl, op, tr) {
+			(Str(s1), Add, Str(s2)) => Str(s1 + &s2),
+			(Int(i1), Add, Int(i2)) => Int(i1
+				.checked_add(i2)
+				.ok_or(Error::eval("integer over- or underflow"))?),
+			(Array(elems1), Add, Array(elems2)) => Array([elems1, elems2].concat()),
+			(Int(i1), Sub, Int(i2)) => Int(i1
+				.checked_sub(i2)
+				.ok_or(Error::eval("integer over- or underflow"))?),
+			(Array(elems1), Sub, Array(elems2)) => Array(
+				elems1
+					.into_iter()
+					.filter(|elem| !elems2.contains(elem))
+					.collect(),
+			),
+			(Int(i1), Mul, Int(i2)) => Int(i1
+				.checked_mul(i2)
+				.ok_or(Error::eval("integer over- or underflow"))?),
+			(Int(i1), Div, Int(i2)) => {
+				Int(i1.checked_div(i2).ok_or(Error::eval("division by zero"))?)
+			}
+			(Int(i1), Rem, Int(i2)) => {
+				Int(i1.checked_rem(i2).ok_or(Error::eval("division by zero"))?)
+			}
+			(Bool(b1), And, Bool(b2)) => Bool(b1 && b2),
+			(Bool(b1), Or, Bool(b2)) => Bool(b1 || b2),
+			(l, Eq, r) => Bool(l == r),
+			(l, Ne, r) => Bool(l != r),
+			(Int(i1), Lt, Int(i2)) => Bool(i1 < i2),
+			(Int(i1), Le, Int(i2)) => Bool(i1 <= i2),
+			(Int(i1), Ge, Int(i2)) => Bool(i1 >= i2),
+			(Int(i1), Gt, Int(i2)) => Bool(i1 > i2),
+			(Str(i1), Lt, Str(i2)) => Bool(i1 < i2),
+			(Str(i1), Le, Str(i2)) => Bool(i1 <= i2),
+			(Str(i1), Ge, Str(i2)) => Bool(i1 >= i2),
+			(Str(i1), Gt, Str(i2)) => Bool(i1 > i2),
+			_ => return Err(Error::typ("invalid types for operation")),
+		})
+	}
+
+	fn eval_unary_op(&mut self, op: expr::OpUnary, expr: &expr::Expr<'_>) -> Result<Value> {
+		use expr::OpUnary::*;
+		use Value::*;
+
+		let typ = self.eval_expr(expr)?;
+
+		Ok(match (op, typ) {
+			(Not, Bool(val)) => Bool(!val),
+			(Neg, Int(val)) => Int(val
+				.checked_neg()
+				.ok_or(Error::eval("integer over- or underflow"))?),
+			_ => return Err(Error::typ("invalid type for operation")),
+		})
+	}
+
+	fn eval_index(&mut self, base: &expr::Expr<'_>, index: &expr::Expr<'_>) -> Result<Value> {
+		use Value::*;
+
+		let base_value = self.eval_expr(base)?;
+		let index_value = self.eval_expr(index)?;
+
+		if let Array(elems) = base_value {
+			if let Int(index) = index_value {
+				return usize::try_from(index)
+					.ok()
+					.and_then(|index| elems.into_iter().nth(index))
+					.ok_or(Error::eval("array index out of bounds"));
+			}
+		} else if let Map(entries) = base_value {
+			return entries
+				.get(&index_value.try_into()?)
+				.cloned()
+				.ok_or(Error::eval("map key not found"));
+		}
+
+		Err(Error::typ("invalid types index operation"))
+	}
+
+	fn eval_func(&mut self, func: Func, call_param_values: Vec<Value>) -> Result<Value> {
+		match func.def {
+			FuncDef::Intrinsic(f) => f(&call_param_values),
+			FuncDef::Body { param_names, block } => {
+				let mut scope = Box::new(self.0.func());
+
+				for (param_name, param_value) in param_names.iter().zip(call_param_values) {
+					scope.defs.insert_value(param_name, param_value);
+				}
+
+				Context(&mut scope).eval_block(&block)
+			}
+		}
+	}
+
+	fn eval_apply(&mut self, expr: &expr::Expr<'_>, params: &[expr::Expr]) -> Result<Value> {
+		use Value::*;
+
+		let value = self.eval_expr(expr)?;
+
+		let Fn(func) = value else {
+			return Err(Error::typ("invalid type for function call"));
+		};
+
+		let param_values: Vec<_> = params
+			.iter()
+			.map(|param| self.eval_expr(param))
+			.collect::<Result<_>>()?;
+
+		self.eval_func(*func, param_values)
+	}
+
+	fn eval_method(
+		&mut self,
+		expr: &expr::Expr<'_>,
+		method: &ast::Ident<'_>,
+		params: &[expr::Expr],
+	) -> Result<Value> {
+		let self_value = self.eval_expr(expr)?;
+		// TODO: Use inferred type for method lookup
+		let self_type = self_value.typ()?;
+		let type_family = TypeFamily::from(&self_type);
+
+		let method = self
+			.0
+			.methods
+			.get(&type_family)
+			.and_then(|methods| methods.get(method.name.as_ref()))
+			.ok_or(Error::lookup("undefined method"))?
+			.clone();
+
+		let param_values: Vec<_> = iter::once(Ok(self_value))
+			.chain(params.iter().map(|param| self.eval_expr(param)))
+			.collect::<Result<_>>()?;
+
+		self.eval_func(method, param_values)
+	}
+
+	fn eval_field(&mut self, base: &expr::Expr<'_>, field: &ast::Ident<'_>) -> Result<Value> {
+		use Value::*;
+
+		let base_value = self.eval_expr(base)?;
+		let name = field.name.as_ref();
+
+		Ok(match base_value {
+			Tuple(elems) => {
+				let index: usize = name.parse().or(Err(Error::typ("no such field")))?;
+				elems
+					.into_iter()
+					.nth(index)
+					.ok_or(Error::typ("no such field"))?
+			}
+			Struct(mut entries) => entries.remove(name).ok_or(Error::typ("no such field"))?,
+			_ => return Err(Error::typ("invalid field access base type")),
+		})
+	}
+
+	fn eval_scope(&mut self, stmts: &[ast::BlockStmt]) -> Result<(Value, FxHashSet<String>)> {
+		let (ret, upvalues) = self.scoped(|ctx| {
+			let mut ret = Value::unit();
+			for stmt in stmts {
+				ret = ctx.eval_block_stmt(stmt)?;
+			}
+			Ok(ret)
+		});
+		Ok((ret?, upvalues))
+	}
+
+	fn eval_block(&mut self, block: &ast::Block) -> Result<Value> {
+		if let [ast::BlockStmt::Expr { expr }] = &block.0[..] {
+			return self.eval_expr(expr);
+		}
+
+		let (ret, upvalues) = self.eval_scope(&block.0)?;
+		self.0.initialize_all(upvalues);
+		Ok(ret)
+	}
+
+	fn eval_ifelse(
+		&mut self,
+		if_blocks: &[(expr::Expr, ast::Block)],
+		else_block: &Option<Box<ast::Block>>,
+	) -> Result<Value> {
+		for (cond, block) in if_blocks {
+			if self.eval_expr(cond)? == Value::Bool(true) {
+				return self.eval_block(block);
+			}
+		}
+		if let Some(block) = else_block {
+			self.eval_block(block)
+		} else {
+			Ok(Value::unit())
+		}
+	}
+
+	fn eval_path(&self, path: &ast::Path<'_>) -> Result<Value> {
+		Ok(self.0.lookup_value(path)?.clone())
+	}
+
+	fn eval_literal(&mut self, lit: &expr::Literal<'_>) -> Result<Value> {
+		use expr::Literal;
+		use Value::*;
+
+		Ok(match lit {
+			Literal::Unit => Value::unit(),
+			Literal::None => Value::None,
+			Literal::Bool(val) => Bool(*val),
+			Literal::Int(val) => Int(*val),
+			Literal::Str { pieces, kind } => Str(StrDisplay {
+				pieces,
+				kind: *kind,
+				ctx: RefCell::new(self),
+			}
+			.to_string()),
+			Literal::Tuple(elems) => Tuple(
+				elems
+					.iter()
+					.map(|elem| self.eval_expr(elem))
+					.collect::<Result<_>>()?,
+			),
+			Literal::Array(elems) => Array(
+				elems
+					.iter()
+					.map(|elem| self.eval_expr(elem))
+					.collect::<Result<_>>()?,
+			),
+			Literal::Map(entries) => {
+				let map: FxHashMap<_, _> = entries
+					.iter()
+					.map(|expr::MapEntry { key, value }| {
+						Ok((self.eval_expr(key)?.try_into()?, self.eval_expr(value)?))
+					})
+					.collect::<Result<_>>()?;
+				if map.len() != entries.len() {
+					return Err(Error::eval("duplicate map key"));
+				}
+				Map(map)
+			}
+			Literal::Struct(entries) => {
+				if entries.is_empty() {
+					return Ok(Value::unit());
+				}
+				Struct(
+					entries
+						.iter()
+						.map(|expr::StructField { name, value }| {
+							Ok((name.as_ref().to_owned(), self.eval_expr(value)?))
+						})
+						.collect::<Result<_>>()?,
+				)
+			}
+		})
+	}
+
+	#[allow(clippy::type_complexity)]
+	fn assign_destr_pat_value_with<'r, R: 'r>(
+		&mut self,
+		pat: &pat::DestrPat,
+		f: Box<dyn FnOnce(&mut Value) -> Result<R> + 'r>,
+	) -> Result<R> {
+		match pat {
+			pat::DestrPat::Index { base, index } => {
+				let index_value = self.eval_expr(index)?;
+				self.assign_destr_pat_value_with(
+					base,
+					Box::new(|base_value| match (base_value, index_value) {
+						(Value::Array(inner), Value::Int(index)) => f(usize::try_from(index)
+							.ok()
+							.and_then(|index| inner.get_mut(index))
+							.ok_or(Error::eval("array index out of bounds"))?),
+						(Value::Map(entries), key) => {
+							use std::collections::hash_map::Entry;
+							match entries.entry(OrdValue::try_from(key)?) {
+								Entry::Occupied(mut entry) => f(entry.get_mut()),
+								Entry::Vacant(entry) => {
+									let mut tmp = Value::Uninitialized;
+									let ret =
+										f(&mut tmp).or(Err(Error::eval("map key not found")))?;
+									entry.insert(tmp);
+									Ok(ret)
+								}
+							}
+						}
+						_ => Err(Error::typ("invalid types for index operation")),
+					}),
+				)
+			}
+			pat::DestrPat::Field { base, field } => self.assign_destr_pat_value_with(
+				base,
+				Box::new(|value| match value {
+					Value::Tuple(elems) => {
+						let index: Option<usize> = field.name.parse().ok();
+						f(index
+							.and_then(|index| elems.get_mut(index))
+							.ok_or(Error::typ("no such field"))?)
+					}
+					Value::Struct(value_entries) => f(value_entries
+						.get_mut(field.name.as_ref())
+						.ok_or(Error::typ("no such field"))?),
+					_ => Err(Error::typ("invalid field access base type")),
+				}),
+			),
+			pat::DestrPat::Paren(subpat) => self.assign_destr_pat_value_with(subpat, f),
+			pat::DestrPat::Path(path) => f(self.0.lookup_var_mut(path)?.0),
+		}
+	}
+
+	fn assign_destr_pat_value(&mut self, dest: &pat::DestrPat, value: Value) -> Result<Value> {
+		if scope::is_wildcard_destr_pat(dest) {
+			return Ok(Value::unit());
+		}
+
+		self.assign_destr_pat_value_with(
+			dest,
+			Box::new(|dest_value| {
+				*dest_value = value.clone();
+				Ok(())
+			}),
+		)?;
+
+		Ok(value)
+	}
+
+	fn scoped<F, R>(&mut self, f: F) -> (R, FxHashSet<String>)
+	where
+		F: FnOnce(&mut Context) -> R,
+	{
+		self.0.scoped(|scope| f(&mut Context(scope)))
+	}
+}
+
+impl Display for Value {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		match self {
+			Value::Uninitialized => f.write_str("_"),
+			Value::None => f.write_str("none"),
+			Value::Bool(value) => value.fmt(f),
+			Value::Int(value) => value.fmt(f),
+			Value::Str(value) => write!(f, "{value:?}"),
+			Value::Tuple(elems) => {
+				let mut first = true;
+				f.write_str("(")?;
+				for elem in elems {
+					if !first {
+						f.write_str(", ")?;
+					}
+					first = false;
+					elem.fmt(f)?;
+				}
+				if elems.len() == 1 {
+					f.write_str(",")?;
+				}
+				f.write_str(")")
+			}
+			Value::Array(elems) => {
+				let mut first = true;
+				f.write_str("[")?;
+				for elem in elems {
+					if !first {
+						f.write_str(", ")?;
+					}
+					first = false;
+					elem.fmt(f)?;
+				}
+				f.write_str("]")
+			}
+			Value::Map(entries) => {
+				let mut first = true;
+				let mut entries: Vec<_> = entries.iter().collect();
+				entries.sort_unstable_by_key(|(key, _)| *key);
+				f.write_str("map{")?;
+				for (key, value) in entries {
+					if !first {
+						f.write_str(", ")?;
+					}
+					first = false;
+					write!(f, "{key} => {value}")?;
+				}
+				f.write_str("}")
+			}
+			Value::Struct(entries) => {
+				let mut first = true;
+				f.write_str("{")?;
+				for (key, value) in entries {
+					if !first {
+						f.write_str(", ")?;
+					}
+					first = false;
+					write!(f, "{key}: {value}")?;
+				}
+				f.write_str("}")
+			}
+			Value::Fn(func) => func.typ.fmt(f),
+		}
+	}
+}
+
+#[derive(Debug)]
+struct Stringify<'a>(&'a Value);
+
+impl<'a> Display for Stringify<'a> {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		match self.0 {
+			Value::Bool(value) => value.fmt(f),
+			Value::Int(value) => value.fmt(f),
+			Value::Str(value) => value.fmt(f),
+			_ => Err(std::fmt::Error),
+		}
+	}
+}
+
+#[derive(Debug)]
+struct ScriptStringify<'a>(&'a Value);
+
+impl<'a> ScriptStringify<'a> {
+	fn fmt_list(elems: &'a [Value], f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		let mut first = true;
+		for elem in elems {
+			if !first {
+				f.write_char(' ')?;
+			}
+			ScriptStringify(elem).fmt(f)?;
+			first = false;
+		}
+		Ok(())
+	}
+}
+
+impl<'a> Display for ScriptStringify<'a> {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		match self.0 {
+			Value::Bool(value) => {
+				value.fmt(f)?;
+			}
+			Value::Int(value) => {
+				value.fmt(f)?;
+			}
+			Value::Str(value) => {
+				f.write_char('\'')?;
+				f.write_str(&value.replace('\'', "'\\''"))?;
+				f.write_char('\'')?;
+			}
+			Value::None => {}
+			Value::Array(elems) => {
+				Self::fmt_list(elems, f)?;
+			}
+			Value::Tuple(elems) => {
+				Self::fmt_list(elems, f)?;
+			}
+			_ => return Err(std::fmt::Error),
+		};
+		Ok(())
+	}
+}
+
+#[derive(Debug)]
+struct StrDisplay<'a, 'scope> {
+	pieces: &'a [expr::StrPiece<'a>],
+	kind: expr::StrKind,
+	ctx: RefCell<&'a mut Context<'scope>>,
+}
+
+impl<'a, 'scope> Display for StrDisplay<'a, 'scope> {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		for piece in self.pieces {
+			match piece {
+				expr::StrPiece::Chars(chars) => f.write_str(chars)?,
+				expr::StrPiece::Escape(c) => f.write_char(*c)?,
+				expr::StrPiece::Interp(expr) => {
+					let val = self
+						.ctx
+						.borrow_mut()
+						.eval_expr(expr)
+						.or(Err(std::fmt::Error))?;
+					match self.kind {
+						expr::StrKind::Regular => Stringify(&val).fmt(f),
+						expr::StrKind::Raw => unreachable!(),
+						expr::StrKind::Script => ScriptStringify(&val).fmt(f),
+					}?;
+				}
+			};
+		}
+		Ok(())
+	}
+}
diff --git a/crates/rebel-parse/Cargo.toml b/crates/rebel-parse/Cargo.toml
new file mode 100644
index 0000000..d116736
--- /dev/null
+++ b/crates/rebel-parse/Cargo.toml
@@ -0,0 +1,23 @@
+[package]
+name = "rebel-parse"
+version = "0.1.0"
+authors = ["Matthias Schiffer <mschiffer@universe-factory.net>"]
+license = "MIT"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+derive-into-owned = { git = "https://github.com/neocturne/derive-into-owned.git", branch = "more-types" }
+peg = "0.8.3"
+phf = { version = "0.11.2", features = ["macros"] }
+rebel-common = { path = "../rebel-common" }
+rustc-hash = "1.1.0"
+
+[dev-dependencies]
+clap = { version = "4.0.0", features = ["derive"] }
+divan = "0.1.14"
+
+[[bench]]
+name = "recipe"
+harness = false
diff --git a/crates/rebel-parse/benches/recipe.rs b/crates/rebel-parse/benches/recipe.rs
new file mode 100644
index 0000000..4cff857
--- /dev/null
+++ b/crates/rebel-parse/benches/recipe.rs
@@ -0,0 +1,21 @@
+use rebel_parse::{ast, token::TokenStream};
+
+fn main() {
+	divan::main();
+}
+
+const RECIPE: &str = include_str!("../../../examples/recipes/gmp/build.recipe");
+
+#[divan::bench]
+fn tokenize() -> TokenStream<'static> {
+	rebel_parse::tokenize::token_stream(divan::black_box(RECIPE)).unwrap()
+}
+
+#[divan::bench]
+fn parse(bencher: divan::Bencher) {
+	let tokens = tokenize();
+
+	bencher.bench(|| -> ast::Recipe<'static> {
+		rebel_parse::recipe::recipe(divan::black_box(&tokens)).unwrap()
+	});
+}
diff --git a/crates/rebel-parse/examples/parse-string.rs b/crates/rebel-parse/examples/parse-string.rs
new file mode 100644
index 0000000..9750a87
--- /dev/null
+++ b/crates/rebel-parse/examples/parse-string.rs
@@ -0,0 +1,70 @@
+use std::{fmt::Debug, process, time::Instant};
+
+use clap::{Parser, ValueEnum};
+
+use rebel_parse::{recipe, tokenize};
+
+#[derive(Clone, Debug, PartialEq, Eq, ValueEnum)]
+enum Rule {
+	Tokenize,
+	Recipe,
+	RecipeStmt,
+	Block,
+	BlockStmt,
+	Expr,
+	Type,
+	Pat,
+}
+
+#[derive(Clone, Debug, Parser)]
+struct Opts {
+	rule: Rule,
+	input: String,
+}
+
+fn main() {
+	let opts: Opts = Opts::parse();
+	let input = opts.input.trim();
+
+	fn as_debug<'a>(v: impl Debug + 'a) -> Box<dyn Debug + 'a> {
+		Box::new(v)
+	}
+
+	let start = Instant::now();
+	let result = tokenize::token_stream(input);
+	let dur = Instant::now().duration_since(start);
+	println!("Tokenization took {} µs", dur.as_micros());
+
+	let tokens = match result {
+		Ok(value) => value,
+		Err(err) => {
+			println!("{err}");
+			process::exit(1);
+		}
+	};
+
+	let start = Instant::now();
+	let result = match opts.rule {
+		Rule::Tokenize => Ok(as_debug(tokens)),
+		Rule::Recipe => recipe::recipe(&tokens).map(as_debug),
+		Rule::RecipeStmt => recipe::recipe_stmt(&tokens).map(as_debug),
+		Rule::Block => recipe::block(&tokens).map(as_debug),
+		Rule::BlockStmt => recipe::block_stmt(&tokens).map(as_debug),
+		Rule::Expr => recipe::expr(&tokens).map(as_debug),
+		Rule::Type => recipe::typ(&tokens).map(as_debug),
+		Rule::Pat => recipe::pat(&tokens).map(as_debug),
+	};
+	if opts.rule != Rule::Tokenize {
+		let dur = Instant::now().duration_since(start);
+		println!("Parsing took {} µs", dur.as_micros());
+	}
+
+	match result {
+		Ok(value) => {
+			println!("{value:#?}");
+		}
+		Err(err) => {
+			println!("{err}");
+		}
+	};
+}
diff --git a/crates/rebel-parse/src/ast/expr.rs b/crates/rebel-parse/src/ast/expr.rs
new file mode 100644
index 0000000..a35a9af
--- /dev/null
+++ b/crates/rebel-parse/src/ast/expr.rs
@@ -0,0 +1,333 @@
+use std::borrow::Cow;
+
+use super::{Block, DestrPat, Ident, Path, PathRoot, ValidationError};
+use crate::token;
+use derive_into_owned::{Borrowed, IntoOwned};
+use rustc_hash::FxHashSet;
+
+pub use token::StrKind;
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum Expr<'a> {
+	Binary {
+		left: Box<Expr<'a>>,
+		op: OpBinary,
+		right: Box<Expr<'a>>,
+	},
+	Unary {
+		op: OpUnary,
+		expr: Box<Expr<'a>>,
+	},
+	Apply {
+		expr: Box<Expr<'a>>,
+		params: Vec<Expr<'a>>,
+	},
+	Method {
+		expr: Box<Expr<'a>>,
+		method: Ident<'a>,
+		params: Vec<Expr<'a>>,
+	},
+	Index {
+		base: Box<Expr<'a>>,
+		index: Box<Expr<'a>>,
+	},
+	Field {
+		base: Box<Expr<'a>>,
+		field: Ident<'a>,
+	},
+	Block(Block<'a>),
+	IfElse {
+		if_blocks: Vec<(Expr<'a>, Block<'a>)>,
+		else_block: Option<Box<Block<'a>>>,
+	},
+	Paren(Box<Expr<'a>>),
+	Path(Path<'a>),
+	Literal(Literal<'a>),
+}
+
+impl<'a> Expr<'a> {
+	pub(crate) fn binary(left: Expr<'a>, op: OpBinary, right: Expr<'a>) -> Self {
+		Expr::Binary {
+			left: Box::new(left),
+			op,
+			right: Box::new(right),
+		}
+	}
+
+	pub(crate) fn unary(op: OpUnary, expr: Expr<'a>) -> Self {
+		Expr::Unary {
+			op,
+			expr: Box::new(expr),
+		}
+	}
+
+	pub(crate) fn apply(expr: Expr<'a>, params: Vec<Expr<'a>>) -> Self {
+		Expr::Apply {
+			expr: Box::new(expr),
+			params,
+		}
+	}
+
+	pub(crate) fn method(expr: Expr<'a>, method: Ident<'a>, params: Vec<Expr<'a>>) -> Self {
+		Expr::Method {
+			expr: Box::new(expr),
+			method,
+			params,
+		}
+	}
+
+	pub(crate) fn index(base: Expr<'a>, index: Expr<'a>) -> Self {
+		Expr::Index {
+			base: Box::new(base),
+			index: Box::new(index),
+		}
+	}
+
+	pub(crate) fn field(base: Expr<'a>, field: Ident<'a>) -> Self {
+		Expr::Field {
+			base: Box::new(base),
+			field,
+		}
+	}
+
+	pub(crate) fn paren(expr: Expr<'a>) -> Self {
+		Expr::Paren(Box::new(expr))
+	}
+
+	pub fn validate(&self) -> Result<(), ValidationError> {
+		match self {
+			Expr::Binary { left, op, right } => {
+				left.validate()?;
+				right.validate()?;
+
+				if op.is_comparision()
+					&& (left.is_binary_comparison() || right.is_binary_comparison())
+				{
+					return Err(ValidationError::NeedsParens);
+				}
+				Ok(())
+			}
+			Expr::Unary { op: _, expr } => expr.validate(),
+			Expr::Apply { expr, params } => {
+				for param in params {
+					param.validate()?;
+				}
+				expr.validate()
+			}
+			Expr::Method {
+				expr,
+				method: _,
+				params,
+			} => {
+				for param in params {
+					param.validate()?;
+				}
+				expr.validate()
+			}
+			Expr::Index { base, index } => {
+				index.validate()?;
+				base.validate()
+			}
+			Expr::Field { base, field: _ } => base.validate(),
+			Expr::Block(block) => {
+				for stmt in &block.0 {
+					stmt.validate()?;
+				}
+				Ok(())
+			}
+			Expr::IfElse {
+				if_blocks,
+				else_block,
+			} => {
+				for (cond, block) in if_blocks {
+					cond.validate()?;
+					block.validate()?;
+				}
+				if let Some(block) = else_block {
+					block.validate()?;
+				}
+				Ok(())
+			}
+			Expr::Paren(expr) => expr.validate(),
+			Expr::Path(_) => Ok(()),
+			Expr::Literal(lit) => lit.validate(),
+		}
+	}
+
+	fn is_binary_comparison(&self) -> bool {
+		let Expr::Binary {
+			left: _,
+			op,
+			right: _,
+		} = self
+		else {
+			return false;
+		};
+
+		op.is_comparision()
+	}
+}
+
+impl<'a> From<DestrPat<'a>> for Expr<'a> {
+	fn from(value: DestrPat<'a>) -> Self {
+		match value {
+			DestrPat::Index { base, index } => Expr::Index {
+				base: Box::new((*base).into()),
+				index: index.clone(),
+			},
+			DestrPat::Field { base, field } => Expr::Field {
+				base: Box::new((*base).into()),
+				field: field.clone(),
+			},
+			DestrPat::Paren(pat) => Expr::Paren(Box::new((*pat).into())),
+			DestrPat::Path(path) => Expr::Path(path.clone()),
+		}
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum Literal<'a> {
+	Unit,
+	None,
+	Bool(bool),
+	Int(i64),
+	Str {
+		pieces: Vec<StrPiece<'a>>,
+		kind: StrKind,
+	},
+	Tuple(Vec<Expr<'a>>),
+	Array(Vec<Expr<'a>>),
+	Map(Vec<MapEntry<'a>>),
+	Struct(Vec<StructField<'a>>),
+}
+
+impl<'a> Literal<'a> {
+	fn validate(&self) -> Result<(), ValidationError> {
+		match self {
+			Literal::Unit => Ok(()),
+			Literal::None => Ok(()),
+			Literal::Bool(_) => Ok(()),
+			Literal::Int(_) => Ok(()),
+			Literal::Str { pieces, kind: _ } => {
+				for piece in pieces {
+					match piece {
+						StrPiece::Chars(_) => {}
+						StrPiece::Escape(_) => {}
+						StrPiece::Interp(expr) => expr.validate()?,
+					}
+				}
+				Ok(())
+			}
+			Literal::Tuple(elems) => {
+				for elem in elems {
+					elem.validate()?;
+				}
+				Ok(())
+			}
+			Literal::Array(elems) => {
+				for elem in elems {
+					elem.validate()?;
+				}
+				Ok(())
+			}
+			Literal::Map(entries) => {
+				for MapEntry { key, value } in entries {
+					key.validate()?;
+					value.validate()?;
+				}
+				Ok(())
+			}
+			Literal::Struct(entries) => {
+				let mut fields = FxHashSet::default();
+				for StructField { name, value } in entries {
+					if !fields.insert(name) {
+						return Err(ValidationError::DuplicateKey);
+					}
+					value.validate()?;
+				}
+				Ok(())
+			}
+		}
+	}
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum StrPiece<'a> {
+	Chars(Cow<'a, str>),
+	Escape(char),
+	Interp(Expr<'a>),
+}
+
+impl<'a> TryFrom<&token::StrPiece<'a>> for StrPiece<'a> {
+	type Error = &'static str;
+
+	fn try_from(value: &token::StrPiece<'a>) -> Result<Self, Self::Error> {
+		use crate::recipe;
+
+		Ok(match value {
+			token::StrPiece::Chars(chars) => StrPiece::Chars(Cow::Borrowed(chars)),
+			token::StrPiece::Escape(c) => StrPiece::Escape(*c),
+			token::StrPiece::Interp(tokens) => StrPiece::Interp(
+				recipe::expr(tokens).or(Err("Invalid expression in string interpolation"))?,
+			),
+		})
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct MapEntry<'a> {
+	pub key: Expr<'a>,
+	pub value: Expr<'a>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct StructField<'a> {
+	pub name: Cow<'a, str>,
+	pub value: Expr<'a>,
+}
+
+impl<'a> StructField<'a> {
+	pub(crate) fn new(field: Ident<'a>, value: Option<Expr<'a>>) -> Self {
+		let value = value.unwrap_or_else(|| {
+			Expr::Path(Path {
+				root: PathRoot::Relative,
+				components: vec![field.clone()],
+			})
+		});
+		StructField {
+			name: field.name,
+			value,
+		}
+	}
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum OpUnary {
+	Not,
+	Neg,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum OpBinary {
+	Add,
+	Sub,
+	Mul,
+	Div,
+	Rem,
+	And,
+	Or,
+	Eq,
+	Lt,
+	Le,
+	Ne,
+	Ge,
+	Gt,
+}
+
+impl OpBinary {
+	fn is_comparision(self) -> bool {
+		use OpBinary::*;
+
+		matches!(self, Eq | Lt | Le | Ne | Ge | Gt)
+	}
+}
diff --git a/crates/rebel-parse/src/ast/mod.rs b/crates/rebel-parse/src/ast/mod.rs
new file mode 100644
index 0000000..0cdc808
--- /dev/null
+++ b/crates/rebel-parse/src/ast/mod.rs
@@ -0,0 +1,187 @@
+use std::borrow::Cow;
+
+use derive_into_owned::{Borrowed, IntoOwned};
+use rustc_hash::FxHashSet;
+
+pub mod expr;
+pub mod pat;
+pub mod typ;
+
+use expr::{Expr, StructField};
+use pat::{DestrPat, Pat};
+use typ::Type;
+
+pub type Recipe<'a> = Vec<RecipeStmt<'a>>;
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum RecipeStmt<'a> {
+	BlockStmt(BlockStmt<'a>),
+	Fetch {
+		name: Ident<'a>,
+		entries: Vec<StructField<'a>>,
+	},
+	Task {
+		name: Ident<'a>,
+		params: Vec<FuncParam<'a>>,
+		block: Block<'a>,
+	},
+}
+
+impl<'a> RecipeStmt<'a> {
+	pub fn validate(&self) -> Result<(), ValidationError> {
+		match self {
+			RecipeStmt::BlockStmt(stmt) => stmt.validate(),
+			RecipeStmt::Fetch { name: _, entries } => {
+				let mut fields = FxHashSet::default();
+				for StructField { name, value } in entries {
+					if !fields.insert(name) {
+						return Err(ValidationError::DuplicateKey);
+					}
+					value.validate()?;
+				}
+				Ok(())
+			}
+			RecipeStmt::Task {
+				name: _,
+				params: _,
+				block,
+			} => {
+				// TODO: Validate params?
+				block.validate()
+			}
+		}
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct Block<'a>(pub Vec<BlockStmt<'a>>);
+
+impl<'a> Block<'a> {
+	pub fn validate(&self) -> Result<(), ValidationError> {
+		for stmt in &self.0 {
+			stmt.validate()?;
+		}
+		Ok(())
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum BlockStmt<'a> {
+	Let {
+		dest: Box<TypedPat<'a>>,
+		expr: Option<Box<Expr<'a>>>,
+	},
+	Assign {
+		dest: Box<DestrPat<'a>>,
+		expr: Box<Expr<'a>>,
+	},
+	Fn {
+		ident: Ident<'a>,
+		params: Vec<FuncParam<'a>>,
+		ret: Option<Box<Type<'a>>>,
+		block: Block<'a>,
+	},
+	Expr {
+		expr: Box<Expr<'a>>,
+	},
+	Empty,
+}
+
+impl<'a> BlockStmt<'a> {
+	pub(crate) fn let_assign(dest: TypedPat<'a>, expr: Option<Expr<'a>>) -> Self {
+		BlockStmt::Let {
+			dest: Box::new(dest),
+			expr: expr.map(Box::new),
+		}
+	}
+
+	pub(crate) fn assign(
+		dest: DestrPat<'a>,
+		op: Option<expr::OpBinary>,
+		swapped: bool,
+		expr: Expr<'a>,
+	) -> Self {
+		let expr = match op {
+			Some(op) => {
+				let dest_expr = Expr::from(dest.clone());
+				if swapped {
+					Expr::binary(expr, op, dest_expr)
+				} else {
+					Expr::binary(dest_expr, op, expr)
+				}
+			}
+			None => expr,
+		};
+		BlockStmt::Assign {
+			dest: Box::new(dest),
+			expr: Box::new(expr),
+		}
+	}
+
+	pub fn validate(&self) -> Result<(), ValidationError> {
+		match self {
+			BlockStmt::Let { dest, expr } => {
+				let TypedPat { pat, typ: _ } = dest.as_ref();
+				pat.validate()?;
+				if let Some(expr) = expr {
+					expr.validate()?;
+				}
+				Ok(())
+			}
+			BlockStmt::Assign { dest, expr } => {
+				dest.validate()?;
+				expr.validate()?;
+				Ok(())
+			}
+			BlockStmt::Fn {
+				ident: _,
+				params: _,
+				ret: _,
+				block,
+			} => {
+				// TODO: Validate params?
+				block.validate()
+			}
+			BlockStmt::Expr { expr } => expr.validate(),
+			BlockStmt::Empty => Ok(()),
+		}
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct TypedPat<'a> {
+	pub pat: Pat<'a>,
+	pub typ: Option<Type<'a>>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct FuncParam<'a> {
+	pub name: Ident<'a>,
+	pub typ: Type<'a>,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PathRoot {
+	Absolute,
+	Relative,
+	Recipe,
+	Task,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct Path<'a> {
+	pub root: PathRoot,
+	pub components: Vec<Ident<'a>>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct Ident<'a> {
+	pub name: Cow<'a, str>,
+}
+
+#[derive(Debug, Clone, Copy)]
+pub enum ValidationError {
+	DuplicateKey,
+	NeedsParens,
+	InvalidLet,
+}
diff --git a/crates/rebel-parse/src/ast/pat.rs b/crates/rebel-parse/src/ast/pat.rs
new file mode 100644
index 0000000..c85f625
--- /dev/null
+++ b/crates/rebel-parse/src/ast/pat.rs
@@ -0,0 +1,57 @@
+use super::*;
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum Pat<'a> {
+	Paren(Box<Pat<'a>>),
+	Ident(Ident<'a>),
+}
+
+impl<'a> Pat<'a> {
+	pub fn validate(&self) -> Result<(), ValidationError> {
+		match self {
+			Pat::Paren(pat) => pat.validate(),
+			Pat::Ident(_) => Ok(()),
+		}
+	}
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum DestrPat<'a> {
+	Index {
+		base: Box<DestrPat<'a>>,
+		index: Box<Expr<'a>>,
+	},
+	Field {
+		base: Box<DestrPat<'a>>,
+		field: Ident<'a>,
+	},
+	Paren(Box<DestrPat<'a>>),
+	Path(Path<'a>),
+}
+
+impl<'a> DestrPat<'a> {
+	pub fn validate(&self) -> Result<(), ValidationError> {
+		match self {
+			DestrPat::Index { base, index } => {
+				base.validate()?;
+				index.validate()?;
+				Ok(())
+			}
+			DestrPat::Field { base, field: _ } => base.validate(),
+			DestrPat::Paren(pat) => pat.validate(),
+			DestrPat::Path(_) => Ok(()),
+		}
+	}
+}
+
+impl<'a> From<Pat<'a>> for DestrPat<'a> {
+	fn from(value: Pat<'a>) -> Self {
+		match value {
+			Pat::Paren(pat) => DestrPat::Paren(Box::new((*pat).into())),
+			Pat::Ident(ident) => DestrPat::Path(Path {
+				root: PathRoot::Relative,
+				components: vec![ident],
+			}),
+		}
+	}
+}
diff --git a/crates/rebel-parse/src/ast/typ.rs b/crates/rebel-parse/src/ast/typ.rs
new file mode 100644
index 0000000..54ab1b9
--- /dev/null
+++ b/crates/rebel-parse/src/ast/typ.rs
@@ -0,0 +1,28 @@
+use std::borrow::Cow;
+
+use derive_into_owned::{Borrowed, IntoOwned};
+
+use super::Path;
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum Type<'a> {
+	Paren(Box<Type<'a>>),
+	Option(Box<Type<'a>>),
+	Path(Path<'a>),
+	Literal(Literal<'a>),
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub enum Literal<'a> {
+	Unit,
+	Tuple(Vec<Type<'a>>),
+	Array(Box<Type<'a>>),
+	Map(Box<Type<'a>>, Box<Type<'a>>),
+	Struct(Vec<StructField<'a>>),
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, IntoOwned, Borrowed)]
+pub struct StructField<'a> {
+	pub name: Cow<'a, str>,
+	pub typ: Type<'a>,
+}
diff --git a/crates/rebel-parse/src/grammar/mod.rs b/crates/rebel-parse/src/grammar/mod.rs
new file mode 100644
index 0000000..de06991
--- /dev/null
+++ b/crates/rebel-parse/src/grammar/mod.rs
@@ -0,0 +1,3 @@
+pub mod recipe;
+pub mod task_ref;
+pub mod tokenize;
diff --git a/crates/rebel-parse/src/grammar/recipe.rs b/crates/rebel-parse/src/grammar/recipe.rs
new file mode 100644
index 0000000..81b47c9
--- /dev/null
+++ b/crates/rebel-parse/src/grammar/recipe.rs
@@ -0,0 +1,277 @@
+use std::borrow::Cow;
+
+use crate::{
+	ast::{
+		self,
+		expr::{self, Expr},
+		pat::{DestrPat, Pat},
+		typ::{self, Type},
+	},
+	token::*,
+};
+
+pub use rules::*;
+
+peg::parser! {
+	pub grammar rules<'a>() for TokenStream<'a> {
+		use expr::OpBinary::*;
+		use expr::OpUnary::*;
+
+		pub rule recipe() -> ast::Recipe<'a>
+			= recipe:recipe_stmt()* { recipe }
+
+		pub rule recipe_stmt() -> ast::RecipeStmt<'a>
+			= [Token::Keyword(Keyword::Fetch)] name:ident() p('{') entries:delimited(<struct_field()>, <p(',')>) p('}') {
+				ast::RecipeStmt::Fetch { name, entries }
+			}
+			/ [Token::Keyword(Keyword::Task)] name:ident() p('(') params:func_params() p(')')
+			  p('{') block:block() p('}') {
+				ast::RecipeStmt::Task { name, params, block }
+			}
+			/ stmt:block_stmt() p(';') {
+				ast::RecipeStmt::BlockStmt(stmt)
+			}
+
+		pub rule block() -> ast::Block<'a>
+			= block:block_stmt() ++ p(';') { ast::Block(block) }
+
+		pub rule block_stmt() -> ast::BlockStmt<'a>
+			= [Token::Keyword(Keyword::Let)] dest:typed_pat() p('=') expr:expr() {
+				ast::BlockStmt::let_assign(dest, Some(expr))
+			}
+			/ [Token::Keyword(Keyword::Let)] dest:typed_pat() {
+				ast::BlockStmt::let_assign(dest, None)
+			}
+			/ [Token::Keyword(Keyword::Fn)] ident:ident() p('(') params:func_params() p(')')
+				ret:tagged(<p2('-', '>')>, <typ()>)? p('{') block:block() p('}')
+			{
+				ast::BlockStmt::Fn {
+					ident,
+					params,
+					ret: ret.map(Box::new),
+					block,
+				}
+			}
+			/ dest:destr_pat() op:assign_op() expr:expr() {
+				ast::BlockStmt::assign(dest, op, false, expr)
+			}
+			/ dest:destr_pat() p2('=', '+') expr:expr() {
+				ast::BlockStmt::assign(dest, Some(Add), true, expr)
+			}
+			/ expr:expr() {
+				ast::BlockStmt::Expr { expr: Box::new(expr) }
+			}
+			/ { ast::BlockStmt::Empty }
+
+		rule assign_op() -> Option<expr::OpBinary>
+			= p('=') { None }
+			/ p2('+', '=') { Some(Add) }
+			/ p2('-', '=') { Some(Sub) }
+			/ p2('*', '=') { Some(Mul) }
+			/ p2('/', '=') { Some(Div) }
+			/ p2('%', '=') { Some(Rem) }
+
+		rule typed_pat() -> ast::TypedPat<'a>
+			= pat:pat() typ:tagged(<p(':')>, <typ()>)? { ast::TypedPat { pat, typ } }
+
+		pub rule typ() -> Type<'a> = precedence! {
+			t:@ p('?') { Type::Option(Box::new(t)) }
+			--
+			t:typ_atom() { t }
+		}
+
+		rule typ_atom() -> Type<'a>
+			= p('(') t:typ() p(')') { Type::Paren(Box::new(t)) }
+			/ lit:typ_literal() { Type::Literal(lit) }
+			/ path:path() { Type::Path(path) }
+
+		rule typ_literal() -> typ::Literal<'a>
+			= p('(') p(')') { typ::Literal::Unit }
+			/ p('(') elements:(typ() ++ p(',')) p(',')? p(')') {
+				typ::Literal::Tuple(elements)
+			}
+			/ p('[') typ:typ() p(']') {
+				typ::Literal::Array(Box::new(typ))
+			}
+			/ [Token::Keyword(Keyword::Map)] p('{') key:typ() p2('=', '>') value:typ() p('}') {
+				typ::Literal::Map(Box::new(key), Box::new(value))
+			}
+			/ p('{') entries:delimited(<struct_field_typ()>, <p(',')>) p('}') {
+				typ::Literal::Struct(entries)
+			}
+
+		pub rule pat() -> ast::pat::Pat<'a>
+			= p('(') pat:pat() p(')') { Pat::Paren(Box::new(pat)) }
+			/ ident:ident() { Pat::Ident(ident) }
+
+		pub rule destr_pat() -> DestrPat<'a> = precedence! {
+			base:@ p('[') index:expr() p(']') {
+				DestrPat::Index { base: Box::new(base), index: Box::new(index) }
+			}
+			--
+			base:@ p('.') field:field() {
+				DestrPat::Field { base: Box::new(base), field }
+			}
+			--
+			p('(') pat:destr_pat() p(')') { DestrPat::Paren(Box::new(pat)) }
+			path:path() { DestrPat::Path(path) }
+		}
+
+		rule struct_field_typ() -> typ::StructField<'a>
+			= field:field() p(':') typ:typ() {
+				typ::StructField { name: field.name, typ }
+			}
+
+		pub rule expr() -> Expr<'a> = precedence! {
+			left:(@) p2('|', '|') right:@ { Expr::binary(left, Or, right) }
+			--
+			left:(@) p2('&', '&') right:@ { Expr::binary(left, And, right) }
+			--
+			left:(@) p2('=', '=') right:@ { Expr::binary(left, Eq, right) }
+			left:(@) p2('!', '=') right:@ { Expr::binary(left, Ne, right) }
+			left:(@) p('<')  right:@ { Expr::binary(left, Lt, right) }
+			left:(@) p('>')  right:@ { Expr::binary(left, Gt, right) }
+			left:(@) p2('<', '=') right:@ { Expr::binary(left, Le, right) }
+			left:(@) p2('>', '=') right:@ { Expr::binary(left, Ge, right) }
+			--
+			left:(@) p('+')  right:@ { Expr::binary(left, Add, right) }
+			left:(@) p('-')  right:@ { Expr::binary(left, Sub, right) }
+			--
+			left:(@) p('*')  right:@ { Expr::binary(left, Mul, right) }
+			left:(@) p('/')  right:@ { Expr::binary(left, Div, right) }
+			left:(@) p('%')  right:@ { Expr::binary(left, Rem, right) }
+			--
+			p('-') expr:@ { Expr::unary(Neg, expr) }
+			p('!') expr:@ { Expr::unary(Not, expr) }
+			--
+			expr:@ p('(') params:call_params() p(')') {
+				Expr::apply(expr, params)
+			}
+			base:@ p('[') index:expr() p(']') { Expr::index(base, index) }
+			--
+			expr:@ p('.') method:field() p('(') params:call_params() p(')') {
+				Expr::method(expr, method, params)
+			}
+			base:@ p('.') field:field() { Expr::field(base, field) }
+			--
+			e:atom() { e }
+		}
+
+		rule atom() -> Expr<'a>
+			= p('(') e:expr() p(')') { Expr::paren(e) }
+			/ [Token::Keyword(Keyword::If)]
+				if_blocks:(cond_block() ++ ([Token::Keyword(Keyword::Else)] [Token::Keyword(Keyword::If)]))
+				else_block:([Token::Keyword(Keyword::Else)] p('{') block:block() p('}') { Box::new(block) })?
+			{
+				Expr::IfElse { if_blocks, else_block }
+			}
+			/ lit:literal() { Expr::Literal(lit) }
+			/ p('{') block:block() p('}') { Expr::Block(block) }
+			/ path:path() { Expr::Path(path) }
+
+		rule cond_block() -> (Expr<'a>, ast::Block<'a>)
+			= cond:expr() p('{') block:block() p('}') { (cond, block) }
+
+		rule call_params() -> Vec<expr::Expr<'a>>
+			= args:delimited(<expr()>, <p(',')>) { args }
+
+		rule func_params() -> Vec<ast::FuncParam<'a>>
+			= params:delimited(<func_param()>, <p(',')>) { params }
+
+		rule func_param() -> ast::FuncParam<'a>
+			= name:ident() p(':') typ:typ() { ast::FuncParam { name, typ } }
+
+		rule literal() -> expr::Literal<'a>
+			= [Token::Keyword(Keyword::True)] { expr::Literal::Bool(true) }
+			/ [Token::Keyword(Keyword::False)] { expr::Literal::Bool(false) }
+			/ [Token::Keyword(Keyword::None)] { expr::Literal::None }
+			/ n:number() { expr::Literal::Int(n) }
+			/ [Token::Str(Str { pieces, kind })] { ?
+				let pieces = pieces
+					.iter()
+					.map(|piece| piece.try_into())
+					.collect::<Result<_, _>>()?;
+				Ok(expr::Literal::Str{ pieces, kind: *kind })
+			}
+			/ p('(') p(')') { expr::Literal::Unit }
+			/ p('(') elements:(expr() ++ p(',')) p(',')? p(')') {
+				expr::Literal::Tuple(elements)
+			}
+			/ p('[') elements:delimited(<expr()>, <p(',')>) p(']') {
+				expr::Literal::Array(elements)
+			}
+			/ [Token::Keyword(Keyword::Map)] p('{') entries:delimited(<map_entry()>, <p(',')>) p('}') {
+				expr::Literal::Map(entries)
+			}
+			/ p('{') entries:delimited(<struct_field()>, <p(',')>) p('}') {
+				expr::Literal::Struct(entries)
+			}
+
+		rule map_entry() -> expr::MapEntry<'a>
+			= key:expr() p2('=', '>') value:expr() {
+				expr::MapEntry { key, value }
+			}
+
+		rule struct_field() -> expr::StructField<'a>
+			= field:field() value:tagged(<p(':')>, <expr()>)? {
+				expr::StructField::new(field, value)
+			}
+
+		rule path() -> ast::Path<'a>
+			= components:(ident() ++ p2(':', ':')) {
+				ast::Path { root: ast::PathRoot::Relative, components }
+			}
+			/ components:(p2(':', ':') ident:ident() { ident })+ {
+				ast::Path { root: ast::PathRoot::Absolute, components }
+			}
+			/ [Token::Keyword(Keyword::Recipe)] components:(p2(':', ':') ident:ident() { ident })* {
+				ast::Path { root: ast::PathRoot::Recipe, components }
+			}
+			/ [Token::Keyword(Keyword::Task)] components:(p2(':', ':') ident:ident() { ident })* {
+				ast::Path { root: ast::PathRoot::Task, components }
+			}
+
+		rule field() -> ast::Ident<'a>
+			= ident()
+			/ [Token::Number(content)] {
+				ast::Ident { name: Cow::Borrowed(content) }
+			}
+
+		rule number() -> i64
+			= neg:p('-')? [Token::Number(s)] { ?
+				let (radix, rest) = if let Some(rest) = s.strip_prefix("0x") {
+					(16, rest)
+				} else if let Some(rest) = s.strip_prefix("0o") {
+					(8, rest)
+				} else if let Some(rest) = s.strip_prefix("0b") {
+					(2, rest)
+				} else {
+					(10, *s)
+				};
+				let mut digits = rest.replace('_', "");
+				if neg.is_some() {
+					digits = format!("-{digits}");
+				}
+				i64::from_str_radix(&digits, radix).or(Err("number"))
+			}
+
+		rule p_(ch: char)
+			= [Token::Punct(Punct(c, Spacing::Joint)) if *c == ch] {}
+
+		rule p(ch: char) -> ()
+			= [Token::Punct(Punct(c, _)) if *c == ch] {}
+
+		rule p2(ch1: char, ch2: char) -> ()
+			= p_(ch1) p(ch2)
+
+		rule ident() -> ast::Ident<'a>
+			= [Token::Ident(name)] { ast::Ident { name: Cow::Borrowed(name) } }
+
+		rule delimited<T>(expr: rule<T>, delim: rule<()>) -> Vec<T>
+			= values:(expr() ++ delim()) delim()? { values }
+			/ { Vec::new() }
+
+		rule tagged<T>(tag: rule<()>, value: rule<T>) -> T
+			= tag() v:value() { v }
+	}
+}
diff --git a/crates/rebel-parse/src/grammar/task_ref.rs b/crates/rebel-parse/src/grammar/task_ref.rs
new file mode 100644
index 0000000..77d6c5f
--- /dev/null
+++ b/crates/rebel-parse/src/grammar/task_ref.rs
@@ -0,0 +1,65 @@
+pub use rules::*;
+
+use rebel_common::types::TaskIDRef;
+
+#[derive(Debug, Clone, Copy)]
+pub struct TaskRef<'a> {
+	pub id: TaskIDRef<'a>,
+	pub args: TaskArgs<'a>,
+}
+
+#[derive(Debug, Clone, Copy, Default)]
+pub struct TaskArgs<'a> {
+	pub host: Option<&'a str>,
+	pub target: Option<&'a str>,
+}
+
+#[derive(Debug, Clone, Copy)]
+pub struct TaskFlags {
+	pub force_run: bool,
+}
+
+peg::parser! {
+	pub grammar rules() for str {
+		pub rule task_ref_with_flags() -> (TaskRef<'input>, TaskFlags)
+			= task:task_ref() flags:task_flags() { (task, flags) }
+
+		pub rule task_ref() -> TaskRef<'input>
+			= id:task_id() args:task_args() {
+				TaskRef {
+					id,
+					args,
+				}
+			}
+
+		rule recipe_id() -> &'input str
+			= $(name() ("/" name())?)
+
+		rule task_id() -> TaskIDRef<'input>
+			= recipe:recipe_id() "::" task:name() {
+				TaskIDRef { recipe, task }
+			}
+
+		rule task_args() -> TaskArgs<'input>
+			= "@" host:name()? target:tagged(<":">, <name()>)? {
+				TaskArgs {
+					host,
+					target,
+				}
+			}
+			/ { Default::default() }
+
+		rule task_flags() -> TaskFlags
+			= force_run:force_run() { TaskFlags { force_run } }
+
+		rule force_run() -> bool
+			= "+" { true }
+			/ { false }
+
+		rule name() -> &'input str
+			= $(['a'..='z' | 'A' ..='Z' | '0'..='9' | '_' | '-']+)
+
+		rule tagged<T>(tag: rule<()>, value: rule<T>) -> T
+			= tag() v:value() { v }
+	}
+}
diff --git a/crates/rebel-parse/src/grammar/tokenize.rs b/crates/rebel-parse/src/grammar/tokenize.rs
new file mode 100644
index 0000000..eb8a900
--- /dev/null
+++ b/crates/rebel-parse/src/grammar/tokenize.rs
@@ -0,0 +1,137 @@
+use crate::token::*;
+
+pub use rules::*;
+
+static KEYWORDS: phf::Map<&'static str, Keyword> = phf::phf_map! {
+	"else" => Keyword::Else,
+	"false" => Keyword::False,
+	"fetch" => Keyword::Fetch,
+	"fn" => Keyword::Fn,
+	"for" => Keyword::For,
+	"if" => Keyword::If,
+	"let" => Keyword::Let,
+	"map" => Keyword::Map,
+	"mut" => Keyword::Mut,
+	"none" => Keyword::None,
+	"recipe" => Keyword::Recipe,
+	"set" =>  Keyword::Set,
+	"task" => Keyword::Task,
+	"true" => Keyword::True,
+};
+
+peg::parser! {
+	pub grammar rules() for str {
+		pub rule token_stream() -> TokenStream<'input>
+			= _ tokens:(token() ** _) _ { TokenStream(tokens) }
+
+		pub rule token() -> Token<'input>
+			= number:number() { Token::Number(number) }
+			/ string:string() { Token::Str(string) }
+			/ token:ident_or_keyword() { token }
+			/ punct:punct() { Token::Punct(punct) }
+
+		rule ident_or_keyword() -> Token<'input>
+			= s:$(
+				['a'..='z' | 'A' ..='Z' | '_' ]
+				['a'..='z' | 'A' ..='Z' | '_' | '0'..='9']*
+			) {
+				if let Some(kw) = KEYWORDS.get(s) {
+					Token::Keyword(*kw)
+				} else {
+					Token::Ident(s)
+				}
+			}
+
+		rule punct() -> Punct
+			= ch:punct_char() spacing:spacing() { Punct(ch, spacing) }
+
+		rule punct_char() -> char
+			= !comment_start() ch:[
+				| '~' | '!' | '@' | '#' | '$' | '%' | '^' | '&'
+				| '*' | '-' | '=' | '+' | '|' | ';' | ':' | ','
+				| '<' | '.' | '>' | '/' | '\'' | '?' | '(' | ')'
+				| '[' | ']' | '{' | '}'
+			] { ch }
+
+		rule spacing() -> Spacing
+			= &punct_char() { Spacing::Joint }
+			/ { Spacing::Alone }
+
+		rule number() -> &'input str
+			= $(['0'..='9'] ['0'..='9' | 'a'..='z' | 'A'..='Z' | '_']*)
+
+		rule string() -> Str<'input>
+			= "\"" pieces:string_piece()* "\"" {
+				Str {
+					pieces,
+					kind: StrKind::Regular,
+				}
+			}
+			/ "r\"" chars:$([^'"']*) "\"" {
+				Str {
+					pieces: vec![StrPiece::Chars(chars)],
+					kind: StrKind::Raw,
+				}
+			}
+			/ "```" newline() pieces:script_string_piece()* "```" {
+				Str {
+					pieces,
+					kind: StrKind::Script,
+				}
+			}
+
+		rule string_piece() -> StrPiece<'input>
+			= chars:$((!"{{" [^'"' | '\\'])+) { StrPiece::Chars(chars) }
+			/ "\\" escape:string_escape() { StrPiece::Escape(escape) }
+			/ string_interp()
+
+		rule string_escape() -> char
+			= "n" { '\n' }
+			/ "r" { '\r' }
+			/ "t" { '\t' }
+			/ "\\" { '\\' }
+			/ "\"" { '"' }
+			/ "{" { '{' }
+			/ "0" { '\0' }
+			/ "x" digits:$(['0'..='7'] hex_digit()) {
+				u8::from_str_radix(digits, 16).unwrap().into()
+			}
+			/ "u{" digits:$(hex_digit()*<1,6>) "}" { ?
+				u32::from_str_radix(digits, 16).unwrap().try_into().or(Err("Invalid unicode escape"))
+			}
+
+		rule script_string_piece() -> StrPiece<'input>
+			= chars:$((!"{{" !"```" [_])+) { StrPiece::Chars(chars) }
+			/ string_interp()
+
+		rule string_interp() -> StrPiece<'input>
+			= "{{" _ tokens:(subtoken() ++ _) _ "}}" {
+				StrPiece::Interp(TokenStream(tokens))
+			}
+
+		rule subtoken() -> Token<'input>
+			= !"}}" token:token() { token }
+
+		rule hex_digit()
+			= ['0'..='9' | 'a'..='f' | 'A'..='F']
+
+		/// Mandatory whitespace
+		rule __
+			= ([' ' | '\t'] / quiet!{newline()} / quiet!{comment()})+
+
+		/// Optional whitespace
+		rule _
+			= quiet!{__?}
+
+		rule comment_start()
+			= "//"
+			/ "/*"
+
+		rule comment()
+			= "//" (!newline() [_])* (newline() / ![_])
+			/ "/*" (!"*/" [_])* "*/"
+
+		rule newline()
+			= ['\n' | '\r']
+	}
+}
diff --git a/crates/rebel-parse/src/lib.rs b/crates/rebel-parse/src/lib.rs
new file mode 100644
index 0000000..4a8c431
--- /dev/null
+++ b/crates/rebel-parse/src/lib.rs
@@ -0,0 +1,8 @@
+pub mod ast;
+pub mod token;
+
+mod grammar;
+
+pub use grammar::recipe;
+pub use grammar::task_ref;
+pub use grammar::tokenize;
diff --git a/crates/rebel-parse/src/token.rs b/crates/rebel-parse/src/token.rs
new file mode 100644
index 0000000..444b5a8
--- /dev/null
+++ b/crates/rebel-parse/src/token.rs
@@ -0,0 +1,87 @@
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum Token<'a> {
+	Keyword(Keyword),
+	Ident(&'a str),
+	Punct(Punct),
+	Str(Str<'a>),
+	Number(&'a str),
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub enum Keyword {
+	Else,
+	False,
+	Fetch,
+	Fn,
+	For,
+	If,
+	Let,
+	Map,
+	Mut,
+	None,
+	Recipe,
+	Set,
+	Task,
+	True,
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub struct Punct(pub char, pub Spacing);
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub enum Spacing {
+	Alone,
+	Joint,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct Str<'a> {
+	pub pieces: Vec<StrPiece<'a>>,
+	pub kind: StrKind,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum StrPiece<'a> {
+	Chars(&'a str),
+	Escape(char),
+	Interp(TokenStream<'a>),
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub enum StrKind {
+	Regular,
+	Raw,
+	Script,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct TokenStream<'a>(pub Vec<Token<'a>>);
+
+impl<'a> peg::Parse for TokenStream<'a> {
+	type PositionRepr = usize;
+
+	fn start(&self) -> usize {
+		0
+	}
+
+	fn is_eof(&self, pos: usize) -> bool {
+		pos >= self.0.len()
+	}
+
+	fn position_repr(&self, pos: usize) -> Self::PositionRepr {
+		pos
+	}
+}
+
+impl<'input, 'a: 'input> peg::ParseElem<'input> for TokenStream<'a> {
+	type Element = &'input Token<'a>;
+
+	fn parse_elem(&'input self, pos: usize) -> peg::RuleResult<Self::Element> {
+		use peg::RuleResult;
+
+		match self.0[pos..].first() {
+			Some(c) => RuleResult::Matched(pos + 1, c),
+			None => RuleResult::Failed,
+		}
+	}
+}
diff --git a/crates/rebel-resolve/Cargo.toml b/crates/rebel-resolve/Cargo.toml
new file mode 100644
index 0000000..4b3e113
--- /dev/null
+++ b/crates/rebel-resolve/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "rebel-resolve"
+version = "0.1.0"
+authors = ["Matthias Schiffer <mschiffer@universe-factory.net>"]
+license = "MIT"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+rebel-common = { path = "../rebel-common" }
+
+deb-version = "0.1.1"
+enum-kinds = "0.5.1"
+serde = { version = "1", features = ["derive", "rc"] }
diff --git a/crates/driver/src/args.rs b/crates/rebel-resolve/src/args.rs
index 805646a..805646a 100644
--- a/crates/driver/src/args.rs
+++ b/crates/rebel-resolve/src/args.rs
diff --git a/crates/driver/src/context.rs b/crates/rebel-resolve/src/context.rs
index 9674e5f..996d981 100644
--- a/crates/driver/src/context.rs
+++ b/crates/rebel-resolve/src/context.rs
@@ -9,15 +9,14 @@ use std::{
 	result,
 };
 
-use common::{
+use rebel_common::{
 	error::{self, Contextualizable},
 	string_hash::ArchiveHash,
-	types::TaskID,
+	types::TaskIDRef,
 };
 
 use crate::{
 	args::*,
-	parse::{self, TaskFlags},
 	paths,
 	pin::{self, Pins},
 	task::*,
@@ -32,7 +31,7 @@ pub enum ErrorKind<'a> {
 
 #[derive(Debug, Clone, Copy)]
 pub struct Error<'a> {
-	pub task: &'a TaskID,
+	pub task: TaskIDRef<'a>,
 	pub kind: ErrorKind<'a>,
 }
 
@@ -65,7 +64,7 @@ pub type Result<'a, T> = result::Result<T, Error<'a>>;
 
 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub struct TaskRef<'ctx> {
-	pub id: &'ctx TaskID,
+	pub id: TaskIDRef<'ctx>,
 	pub args: Rc<TaskArgs>,
 }
 
@@ -75,7 +74,7 @@ impl<'ctx> Display for TaskRef<'ctx> {
 			return self.id.fmt(f);
 		}
 
-		let pv_arg = match self.args.get("pv") {
+		let version_arg = match self.args.get("version") {
 			Some(Arg::String(s)) => Some(s),
 			_ => None,
 		};
@@ -89,13 +88,13 @@ impl<'ctx> Display for TaskRef<'ctx> {
 		};
 
 		write!(f, "{}", self.id.recipe)?;
-		if let Some(pv) = pv_arg {
-			write!(f, "@{}", pv)?;
+		if let Some(version) = version_arg {
+			write!(f, "#{}", version)?;
 		}
-		write!(f, ":{}", self.id.task)?;
+		write!(f, "::{}", self.id.task)?;
 
 		if host_arg.is_some() || target_arg.is_some() {
-			write!(f, "/")?;
+			write!(f, "@")?;
 		}
 
 		if let Some(host) = host_arg {
@@ -144,12 +143,15 @@ fn platform_relation(args: &TaskArgs, from: &str, to: &str) -> Option<PlatformRe
 pub struct Context {
 	platforms: HashMap<String, Arg>,
 	globals: TaskArgs,
-	tasks: HashMap<TaskID, Vec<TaskDef>>,
+	tasks: HashMap<String, HashMap<String, Vec<TaskDef>>>,
 	rootfs: (ArchiveHash, String),
 }
 
 impl Context {
-	pub fn new(mut tasks: HashMap<TaskID, Vec<TaskDef>>, pins: Pins) -> error::Result<Self> {
+	pub fn new(
+		mut tasks: HashMap<String, HashMap<String, Vec<TaskDef>>>,
+		pins: Pins,
+	) -> error::Result<Self> {
 		let platforms: HashMap<_, _> = [
 			arg(
 				"build",
@@ -212,7 +214,7 @@ impl Context {
 	}
 
 	fn add_rootfs_tasks(
-		tasks: &mut HashMap<TaskID, Vec<TaskDef>>,
+		tasks: &mut HashMap<String, HashMap<String, Vec<TaskDef>>>,
 		provides: Vec<pin::Provides>,
 		globals: &TaskArgs,
 	) -> error::Result<()> {
@@ -255,10 +257,9 @@ impl Context {
 			task_def.priority = i32::MAX;
 
 			tasks
-				.entry(TaskID {
-					recipe: recipe.to_string(),
-					task: task.to_string(),
-				})
+				.entry(recipe)
+				.or_default()
+				.entry(task)
 				.or_default()
 				.push(task_def);
 		}
@@ -293,9 +294,12 @@ impl Context {
 			.max_by(|task1, task2| Self::compare_tasks(task1, task2))
 	}
 
-	fn get_with_args<'a>(&self, id: &'a TaskID, args: &TaskArgs) -> Result<'a, &TaskDef> {
-		self.tasks
-			.get(id)
+	fn get_by_ref(&self, id: TaskIDRef) -> Option<&[TaskDef]> {
+		Some(self.tasks.get(id.recipe)?.get(id.task)?)
+	}
+
+	fn get_with_args<'a>(&self, id: TaskIDRef<'a>, args: &TaskArgs) -> Result<'a, &TaskDef> {
+		self.get_by_ref(id)
 			.and_then(|tasks| Self::select_task(tasks, args))
 			.ok_or(Error {
 				task: id,
@@ -307,7 +311,7 @@ impl Context {
 		self.get_with_args(task.id, task.args.as_ref())
 	}
 
-	fn task_ref<'ctx>(&'ctx self, id: &'ctx TaskID, args: &TaskArgs) -> Result<TaskRef> {
+	fn task_ref<'ctx>(&'ctx self, id: TaskIDRef<'ctx>, args: &TaskArgs) -> Result<TaskRef> {
 		let task_def = self.get_with_args(id, args)?;
 
 		let mut arg_def: HashMap<_, _> = task_def.args.iter().map(|(k, &v)| (k, v)).collect();
@@ -345,8 +349,11 @@ impl Context {
 
 		new_args.set("cross_compile", cross_compile);
 
-		new_args.set("pn", Some(task_def.meta.name.clone()));
-		new_args.set("pv", task_def.meta.version.clone());
+		new_args.set("basename", Some(task_def.meta.basename.clone()));
+		new_args.set("recipename", Some(task_def.meta.recipename.clone()));
+		new_args.set("recipe", Some(task_def.meta.recipe.clone()));
+		new_args.set("name", Some(task_def.meta.name.clone()));
+		new_args.set("version", task_def.meta.version.clone());
 
 		Ok(TaskRef {
 			id,
@@ -354,21 +361,27 @@ impl Context {
 		})
 	}
 
-	pub fn parse(&self, s: &str) -> error::Result<(TaskRef, TaskFlags)> {
-		let (parsed, flags) = parse::parse_task_with_flags(s).context("Invalid task syntax")?;
-
-		let recipe = parsed.recipe.to_string();
-		let task = parsed.task.to_string();
-
-		let id = TaskID { recipe, task };
-		let (ctx_id, _) = self
+	pub fn lookup(
+		&self,
+		id: TaskIDRef,
+		host: Option<&str>,
+		target: Option<&str>,
+	) -> error::Result<TaskRef> {
+		let (ctx_recipe, recipe_tasks) = self
 			.tasks
-			.get_key_value(&id)
+			.get_key_value(id.recipe)
 			.with_context(|| format!("Task {} not found", id))?;
+		let (ctx_task, _) = recipe_tasks
+			.get_key_value(id.task)
+			.with_context(|| format!("Task {} not found", id))?;
+		let ctx_id = TaskIDRef {
+			recipe: ctx_recipe,
+			task: ctx_task,
+		};
 
 		let mut args = self.globals.clone();
 
-		if let Some(host) = parsed.host {
+		if let Some(host) = host {
 			let plat = self
 				.platforms
 				.get(host)
@@ -376,7 +389,7 @@ impl Context {
 			args.set("host", Some(plat));
 			args.set("target", Some(plat));
 		}
-		if let Some(target) = parsed.target {
+		if let Some(target) = target {
 			let plat = self
 				.platforms
 				.get(target)
@@ -388,11 +401,11 @@ impl Context {
 			.task_ref(ctx_id, &args)
 			.with_context(|| format!("Failed to instantiate task {}", id))?;
 
-		Ok((task_ref, flags))
+		Ok(task_ref)
 	}
 
 	fn map_args<'ctx, 'args>(
-		task: &'ctx TaskID,
+		task: TaskIDRef<'ctx>,
 		mapping: &'ctx ArgMapping,
 		args: &'args TaskArgs,
 		build_dep: bool,
@@ -419,37 +432,44 @@ impl Context {
 		Ok(Cow::Owned(ret))
 	}
 
-	fn inherit_ref<'ctx>(&'ctx self, dep: &'ctx InheritDep, args: &TaskArgs) -> Result<TaskRef> {
-		let mapped_args = Context::map_args(&dep.dep.id, &dep.dep.args, args, false)?;
-		self.task_ref(&dep.dep.id, mapped_args.as_ref())
+	fn parent_ref<'ctx>(
+		&'ctx self,
+		dep_of: TaskIDRef<'ctx>,
+		dep: &'ctx ParentDep,
+		args: &TaskArgs,
+	) -> Result<TaskRef> {
+		let id = dep.dep.id(dep_of.recipe);
+		let mapped_args = Context::map_args(id, &dep.dep.args, args, false)?;
+		self.task_ref(id, mapped_args.as_ref())
 	}
 
 	pub fn output_ref<'ctx>(
 		&'ctx self,
+		dep_of: TaskIDRef<'ctx>,
 		dep: &'ctx OutputDep,
 		args: &TaskArgs,
 		build_dep: bool,
 	) -> Result<OutputRef<'ctx>> {
-		let mapped_args = Context::map_args(&dep.dep.id, &dep.dep.args, args, build_dep)?;
+		let id = dep.dep.id(dep_of.recipe);
+		let mapped_args = Context::map_args(id, &dep.dep.args, args, build_dep)?;
 		Ok(OutputRef {
-			task: self.task_ref(&dep.dep.id, mapped_args.as_ref())?,
+			task: self.task_ref(id, mapped_args.as_ref())?,
 			output: &dep.output,
 		})
 	}
 
-	pub fn get_inherit_depend<'ctx>(
+	pub fn get_parent_depend<'ctx>(
 		&'ctx self,
 		task_ref: &TaskRef<'ctx>,
 	) -> Result<Option<TaskRef>> {
 		let task = self.get(task_ref)?;
-		let inherit = match &task.inherit {
-			Some(inherit) => inherit,
-			None => return Ok(None),
+		let Some(parent) = &task.parent else {
+			return Ok(None);
 		};
-		Some(self.inherit_ref(inherit, &task_ref.args)).transpose()
+		Some(self.parent_ref(task_ref.id, parent, &task_ref.args)).transpose()
 	}
 
-	fn inherit_iter<'ctx>(
+	fn ancestor_iter<'ctx>(
 		&'ctx self,
 		task_ref: &TaskRef<'ctx>,
 	) -> impl Iterator<Item = Result<TaskRef>> {
@@ -463,7 +483,7 @@ impl Context {
 					Ok(task_ref) => task_ref,
 					Err(err) => return Some(Err(err)),
 				};
-				self.1 = self.0.get_inherit_depend(&task_ref).transpose();
+				self.1 = self.0.get_parent_depend(&task_ref).transpose();
 				Some(Ok(task_ref))
 			}
 		}
@@ -478,14 +498,14 @@ impl Context {
 		let mut ret = HashSet::new();
 		let mut allow_noinherit = true;
 
-		for current in self.inherit_iter(task_ref) {
+		for current in self.ancestor_iter(task_ref) {
 			let current_ref = current?;
 			let task = self.get(&current_ref)?;
 			let entries = task
 				.build_depends
 				.iter()
 				.filter(|dep| allow_noinherit || !dep.noinherit)
-				.map(|dep| self.output_ref(dep, &current_ref.args, true))
+				.map(|dep| self.output_ref(task_ref.id, dep, &current_ref.args, true))
 				.collect::<Result<Vec<_>>>()?;
 			ret.extend(entries);
 
@@ -502,14 +522,14 @@ impl Context {
 		let mut ret = HashSet::new();
 		let mut allow_noinherit = true;
 
-		for current in self.inherit_iter(task_ref) {
+		for current in self.ancestor_iter(task_ref) {
 			let current_ref = current?;
 			let task = self.get(&current_ref)?;
 			let entries = task
 				.depends
 				.iter()
 				.filter(|dep| allow_noinherit || !dep.noinherit)
-				.map(|dep| self.output_ref(dep, &current_ref.args, false))
+				.map(|dep| self.output_ref(task_ref.id, dep, &current_ref.args, false))
 				.collect::<Result<Vec<_>>>()?;
 			ret.extend(entries);
 
diff --git a/crates/driver/src/resolve.rs b/crates/rebel-resolve/src/lib.rs
index d03f26d..cc44de8 100644
--- a/crates/driver/src/resolve.rs
+++ b/crates/rebel-resolve/src/lib.rs
@@ -1,13 +1,19 @@
+pub mod args;
+pub mod context;
+pub mod paths;
+pub mod pin;
+pub mod task;
+
 use std::collections::{HashMap, HashSet};
 use std::fmt;
 use std::rc::Rc;
 
-use common::types::TaskID;
+use rebel_common::types::TaskIDRef;
 
-use crate::args::TaskArgs;
-use crate::context::{self, Context, OutputRef, TaskRef};
+use args::TaskArgs;
+use context::{Context, OutputRef, TaskRef};
 
-#[derive(Debug)]
+#[derive(Debug, Default)]
 pub struct DepChain<'ctx>(pub Vec<TaskRef<'ctx>>);
 
 impl<'ctx> fmt::Display for DepChain<'ctx> {
@@ -38,8 +44,8 @@ impl<'ctx> From<&TaskRef<'ctx>> for DepChain<'ctx> {
 	}
 }
 
-impl<'ctx> From<&'ctx TaskID> for DepChain<'ctx> {
-	fn from(id: &'ctx TaskID) -> Self {
+impl<'ctx> From<TaskIDRef<'ctx>> for DepChain<'ctx> {
+	fn from(id: TaskIDRef<'ctx>) -> Self {
 		TaskRef {
 			id,
 			args: Rc::new(TaskArgs::default()),
@@ -48,11 +54,14 @@ impl<'ctx> From<&'ctx TaskID> for DepChain<'ctx> {
 	}
 }
 
+const MAX_ERRORS: usize = 100;
+
 #[derive(Debug)]
 pub enum ErrorKind<'ctx> {
 	Context(context::Error<'ctx>),
 	OutputNotFound(&'ctx str),
 	DependencyCycle,
+	TooManyErrors,
 }
 
 #[derive(Debug)]
@@ -76,6 +85,13 @@ impl<'ctx> Error<'ctx> {
 		}
 	}
 
+	fn too_many_errors() -> Self {
+		Error {
+			dep_chain: DepChain::default(),
+			kind: ErrorKind::TooManyErrors,
+		}
+	}
+
 	fn extend(&mut self, task: &TaskRef<'ctx>) {
 		self.dep_chain.0.push(task.clone());
 	}
@@ -94,6 +110,9 @@ impl<'ctx> fmt::Display for Error<'ctx> {
 			ErrorKind::DependencyCycle => {
 				write!(f, "Dependency Cycle: ")?;
 			}
+			ErrorKind::TooManyErrors => {
+				write!(f, "Too many errors, stopping.")?;
+			}
 		}
 		dep_chain.fmt(f)
 	}
@@ -149,7 +168,7 @@ where
 
 		let mut errors = Vec::new();
 		for runtime_dep in &output.runtime_depends {
-			match ctx.output_ref(runtime_dep, &task.args, false) {
+			match ctx.output_ref(task.id, runtime_dep, &task.args, false) {
 				Ok(output_ref) => {
 					for mut error in add_dep(ret, ctx, output_ref) {
 						error.extend(task);
@@ -201,7 +220,7 @@ pub fn get_dependent_tasks<'ctx>(
 	task_ref: &TaskRef<'ctx>,
 ) -> Result<HashSet<TaskRef<'ctx>>, Vec<Error<'ctx>>> {
 	Ok(ctx
-		.get_inherit_depend(task_ref)
+		.get_parent_depend(task_ref)
 		.map_err(|err| vec![err.into()])?
 		.into_iter()
 		.chain(
@@ -254,33 +273,43 @@ impl<'ctx> Resolver<'ctx> {
 			.insert(task.clone(), ResolveState::Resolving);
 
 		let mut ret = Vec::new();
-		let mut handle_errors = |errors: Vec<Error<'ctx>>| {
+		let mut handle_errors = |errors: Vec<Error<'ctx>>| -> Result<(), ()> {
 			for mut error in errors {
 				error.extend(task);
 				ret.push(error);
+
+				if ret.len() > MAX_ERRORS {
+					ret.push(Error::too_many_errors());
+					return Err(());
+				}
 			}
+			Ok(())
 		};
 
-		match self.ctx.get_inherit_depend(task) {
-			Ok(Some(inherit)) => {
-				handle_errors(self.add_task(&inherit, None));
-			}
-			Ok(None) => {}
-			Err(err) => {
-				handle_errors(vec![err.into()]);
+		let _ = (|| -> Result<(), ()> {
+			match self.ctx.get_parent_depend(task) {
+				Ok(Some(parent)) => {
+					handle_errors(self.add_task(&parent, None))?;
+				}
+				Ok(None) => {}
+				Err(err) => {
+					handle_errors(vec![err.into()])?;
+				}
 			}
-		}
 
-		match get_dependent_outputs(self.ctx, task) {
-			Ok(rdeps) => {
-				for rdep in rdeps {
-					handle_errors(self.add_task(&rdep.task, Some(rdep.output)));
+			match get_dependent_outputs(self.ctx, task) {
+				Ok(rdeps) => {
+					for rdep in rdeps {
+						handle_errors(self.add_task(&rdep.task, Some(rdep.output)))?;
+					}
+				}
+				Err(errors) => {
+					handle_errors(errors)?;
 				}
 			}
-			Err(errors) => {
-				handle_errors(errors);
-			}
-		}
+
+			Ok(())
+		})();
 
 		if ret.is_empty() {
 			*self
diff --git a/crates/driver/src/paths.rs b/crates/rebel-resolve/src/paths.rs
index 274dda1..274dda1 100644
--- a/crates/driver/src/paths.rs
+++ b/crates/rebel-resolve/src/paths.rs
diff --git a/crates/driver/src/pin.rs b/crates/rebel-resolve/src/pin.rs
index 26e445c..bffc940 100644
--- a/crates/driver/src/pin.rs
+++ b/crates/rebel-resolve/src/pin.rs
@@ -1,8 +1,8 @@
-use std::{collections::HashMap, fs::File, path::Path};
+use std::collections::HashMap;
 
 use serde::{Deserialize, Serialize};
 
-use common::{error::*, string_hash::*};
+use rebel_common::string_hash::*;
 
 #[derive(Clone, Debug, Deserialize, Serialize)]
 pub struct Args {
@@ -29,11 +29,3 @@ pub struct Pin {
 }
 
 pub type Pins = HashMap<String, Pin>;
-
-pub fn read_pins<P: AsRef<Path>>(path: P) -> Result<Pins> {
-	let f = File::open(path)?;
-	let pins: Pins = serde_yaml::from_reader(f)
-		.map_err(Error::new)
-		.context("YAML error")?;
-	Ok(pins)
-}
diff --git a/crates/driver/src/task.rs b/crates/rebel-resolve/src/task.rs
index df3bc68..1220d45 100644
--- a/crates/driver/src/task.rs
+++ b/crates/rebel-resolve/src/task.rs
@@ -2,28 +2,26 @@ use std::collections::{HashMap, HashSet};
 
 use serde::Deserialize;
 
-use common::{string_hash::StringHash, types::TaskID};
+use rebel_common::{string_hash::StringHash, types::TaskIDRef};
 
-use crate::{
-	args::{ArgMapping, ArgType, TaskArgs},
-	recipe,
-};
-
-#[derive(Clone, Debug, Deserialize, PartialEq, Eq, Hash, Default)]
-pub struct RecipeMeta {
-	#[serde(default)]
-	pub name: String,
-	pub version: Option<String>,
-}
+use crate::args::{ArgMapping, ArgType, TaskArgs};
 
 #[derive(Clone, Debug, Deserialize, PartialEq, Eq, Hash)]
 pub struct TaskDep {
-	#[serde(flatten, deserialize_with = "recipe::deserialize_task_id")]
-	pub id: TaskID,
+	pub recipe: Option<String>,
+	pub task: String,
 	#[serde(default)]
 	pub args: ArgMapping,
 }
 
+impl TaskDep {
+	pub fn id<'a>(&'a self, recipe: &'a str) -> TaskIDRef<'a> {
+		let recipe = self.recipe.as_deref().unwrap_or(recipe);
+		let task = &self.task;
+		TaskIDRef { recipe, task }
+	}
+}
+
 #[derive(Clone, Debug, Deserialize, PartialEq, Eq, Hash)]
 pub struct Fetch {
 	pub name: String,
@@ -35,7 +33,7 @@ fn default_output_name() -> String {
 }
 
 #[derive(Clone, Debug, Deserialize)]
-pub struct InheritDep {
+pub struct ParentDep {
 	#[serde(flatten)]
 	pub dep: TaskDep,
 }
@@ -69,14 +67,23 @@ impl Action {
 	}
 }
 
+#[derive(Clone, Debug, Default)]
+pub struct TaskMeta {
+	pub basename: String,
+	pub recipename: String,
+	pub recipe: String,
+	pub name: String,
+	pub version: Option<String>,
+}
+
 #[derive(Clone, Debug, Deserialize, Default)]
 pub struct TaskDef {
 	#[serde(skip)]
-	pub meta: RecipeMeta,
+	pub meta: TaskMeta,
 	#[serde(default)]
 	pub args: HashMap<String, ArgType>,
 	#[serde(default)]
-	pub inherit: Option<InheritDep>,
+	pub parent: Option<ParentDep>,
 	#[serde(default)]
 	pub fetch: HashSet<Fetch>,
 	#[serde(default)]
diff --git a/crates/runner/Cargo.toml b/crates/rebel-runner/Cargo.toml
index bd1287e..3df06f8 100644
--- a/crates/runner/Cargo.toml
+++ b/crates/rebel-runner/Cargo.toml
@@ -8,14 +8,14 @@ edition = "2021"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
-common = { path = "../common", package = "rebel-common" }
+rebel-common = { path = "../rebel-common" }
 
 bincode = "1.3.3"
 blake3 = { version = "1.3.0", features = ["traits-preview"] }
 capctl = "0.2.0"
 digest = "0.10.1"
 libc = "0.2.84"
-nix = { version = "0.27.1", features = ["user", "fs", "process", "mount", "sched", "poll", "signal", "hostname"] }
+nix = { version = "0.28.0", features = ["user", "fs", "process", "mount", "sched", "poll", "signal", "hostname", "resource"] }
 olpc-cjson = "0.1.0"
 serde = { version = "1", features = ["derive"] }
 serde_json = "1.0.62"
diff --git a/crates/runner/src/init.rs b/crates/rebel-runner/src/init.rs
index ede8fd8..0172a01 100644
--- a/crates/runner/src/init.rs
+++ b/crates/rebel-runner/src/init.rs
@@ -1,6 +1,6 @@
 use nix::mount::{self, MsFlags};
 
-use common::error::*;
+use rebel_common::error::*;
 
 use crate::{paths, util::fs};
 
diff --git a/crates/runner/src/jobserver.rs b/crates/rebel-runner/src/jobserver.rs
index 2422a75..7c3f2f7 100644
--- a/crates/runner/src/jobserver.rs
+++ b/crates/rebel-runner/src/jobserver.rs
@@ -1,11 +1,11 @@
 use std::{
-	os::fd::{AsRawFd, FromRawFd, OwnedFd},
+	os::fd::{AsFd, AsRawFd, OwnedFd},
 	slice,
 };
 
 use nix::{errno::Errno, fcntl::OFlag, poll, unistd};
 
-use common::error::*;
+use rebel_common::error::*;
 
 use super::util::unix;
 
@@ -18,13 +18,10 @@ pub struct Jobserver {
 
 impl Jobserver {
 	pub fn new(tokens: usize) -> Result<Jobserver> {
-		let (piper, pipew) =
-			unistd::pipe2(OFlag::O_CLOEXEC | OFlag::O_NONBLOCK).context("pipe()")?;
-		let r = unsafe { OwnedFd::from_raw_fd(piper) };
-		let w = unsafe { OwnedFd::from_raw_fd(pipew) };
+		let (r, w) = unistd::pipe2(OFlag::O_CLOEXEC | OFlag::O_NONBLOCK).context("pipe()")?;
 
 		for _ in 0..tokens {
-			if unistd::write(w.as_raw_fd(), b"+").is_err() {
+			if unistd::write(w.as_fd(), b"+").is_err() {
 				break;
 			}
 		}
@@ -36,8 +33,8 @@ impl Jobserver {
 	pub fn wait(&mut self) -> u8 {
 		loop {
 			poll::poll(
-				&mut [poll::PollFd::new(&self.r, poll::PollFlags::POLLIN)],
-				-1,
+				&mut [poll::PollFd::new(self.r.as_fd(), poll::PollFlags::POLLIN)],
+				poll::PollTimeout::NONE,
 			)
 			.expect("poll()");
 
@@ -59,7 +56,7 @@ impl Jobserver {
 	}
 
 	pub fn post(&mut self, token: u8) {
-		let n = unistd::write(self.w.as_raw_fd(), slice::from_ref(&token)).expect("write()");
+		let n = unistd::write(self.w.as_fd(), slice::from_ref(&token)).expect("write()");
 		assert!(n == 1);
 	}
 
diff --git a/crates/runner/src/lib.rs b/crates/rebel-runner/src/lib.rs
index 308b54c..7dde05d 100644
--- a/crates/runner/src/lib.rs
+++ b/crates/rebel-runner/src/lib.rs
@@ -17,6 +17,7 @@ use std::{
 use capctl::prctl;
 use nix::{
 	errno::Errno,
+	fcntl::Flock,
 	poll,
 	sched::CloneFlags,
 	sys::{
@@ -28,7 +29,7 @@ use nix::{
 };
 use uds::UnixSeqpacketConn;
 
-use common::{error::*, types::*};
+use rebel_common::{error::*, types::*};
 
 use jobserver::Jobserver;
 use util::{checkable::Checkable, clone, steal::Steal, unix};
@@ -99,7 +100,14 @@ fn borrow_socket_fd(socket: &UnixSeqpacketConn) -> BorrowedFd<'_> {
 	unsafe { BorrowedFd::borrow_raw(socket.as_raw_fd()) }
 }
 
-fn runner(uid: Uid, gid: Gid, socket: UnixSeqpacketConn, _lockfile: File, options: &Options) -> ! {
+fn runner(
+	uid: Uid,
+	gid: Gid,
+	socket: UnixSeqpacketConn,
+	_lockfile: Flock<File>,
+	options: &Options,
+) -> ! {
+	unistd::setsid().expect("setsid()");
 	ns::mount_proc();
 	ns::setup_userns(Uid::from_raw(0), Gid::from_raw(0), uid, gid);
 
@@ -127,10 +135,10 @@ fn runner(uid: Uid, gid: Gid, socket: UnixSeqpacketConn, _lockfile: File, option
 	loop {
 		let socket_fd = borrow_socket_fd(&ctx.socket);
 		let mut pollfds = [
-			poll::PollFd::new(&signal_fd, poll::PollFlags::POLLIN),
-			poll::PollFd::new(&socket_fd, poll::PollFlags::POLLIN),
+			poll::PollFd::new(signal_fd.as_fd(), poll::PollFlags::POLLIN),
+			poll::PollFd::new(socket_fd.as_fd(), poll::PollFlags::POLLIN),
 		];
-		poll::poll(&mut pollfds, -1).expect("poll()");
+		poll::poll(&mut pollfds, poll::PollTimeout::NONE).expect("poll()");
 
 		let signal_events = pollfds[0]
 			.revents()
diff --git a/crates/runner/src/ns.rs b/crates/rebel-runner/src/ns.rs
index 4a8e3e7..986aa80 100644
--- a/crates/runner/src/ns.rs
+++ b/crates/rebel-runner/src/ns.rs
@@ -4,7 +4,7 @@ use nix::{
 	unistd::{self, Gid, Pid, Uid},
 };
 
-use common::error::*;
+use rebel_common::error::*;
 
 use super::util::clone;
 
diff --git a/crates/runner/src/paths.rs b/crates/rebel-runner/src/paths.rs
index 4b3a126..84f9c4d 100644
--- a/crates/runner/src/paths.rs
+++ b/crates/rebel-runner/src/paths.rs
@@ -36,7 +36,7 @@
 //!             └── rootfs/           # rootfs overlay mountpoint
 //! ```
 
-use common::string_hash::*;
+use rebel_common::string_hash::*;
 
 pub const DOWNLOADS_DIR: &str = "build/downloads";
 pub const PIN_DIR: &str = "build/pinned";
diff --git a/crates/runner/src/tar.rs b/crates/rebel-runner/src/tar.rs
index 1a66408..891c603 100644
--- a/crates/runner/src/tar.rs
+++ b/crates/rebel-runner/src/tar.rs
@@ -11,7 +11,7 @@ use nix::{
 	sys::wait,
 };
 
-use common::{error::*, string_hash::ArchiveHash};
+use rebel_common::{error::*, string_hash::ArchiveHash};
 
 use super::{
 	ns,
diff --git a/crates/runner/src/task.rs b/crates/rebel-runner/src/task.rs
index b716b82..5bb253a 100644
--- a/crates/runner/src/task.rs
+++ b/crates/rebel-runner/src/task.rs
@@ -11,13 +11,13 @@ use capctl::prctl;
 use nix::{
 	mount::{self, MsFlags},
 	sched::{unshare, CloneFlags},
-	sys::wait,
+	sys::{resource, time::TimeVal, wait},
 	unistd::{self, Gid, Uid},
 };
 use serde::Serialize;
 use tee_readwrite::{TeeReader, TeeWriter};
 
-use common::{error::*, string_hash::*, types::*};
+use rebel_common::{error::*, string_hash::*, types::*};
 use walkdir::WalkDir;
 
 use super::{
@@ -52,7 +52,7 @@ fn input_hash(task: &Task) -> InputHash {
 		pub command: &'a str,
 		pub workdir: &'a str,
 		pub rootfs: &'a ArchiveHash,
-		pub inherit: &'a [LayerHash],
+		pub ancestors: &'a [LayerHash],
 		pub depends: HashMap<DependencyHash, &'a Dependency>,
 		pub outputs: &'a HashMap<String, String>,
 	}
@@ -60,7 +60,7 @@ fn input_hash(task: &Task) -> InputHash {
 		command: &task.command,
 		workdir: &task.workdir,
 		rootfs: &task.rootfs,
-		inherit: &task.inherit,
+		ancestors: &task.ancestors,
 		depends: task
 			.depends
 			.iter()
@@ -94,7 +94,7 @@ fn init_task(input_hash: &InputHash, task: &Task) -> Result<fs::Mount> {
 		.with_context(|| format!("Failed to write {}", runfile))?;
 
 	let mount_target = paths::join(&[&task_tmp_dir, &task.workdir]);
-	let mount = if task.inherit.is_empty() {
+	let mount = if task.ancestors.is_empty() {
 		fs::mount(task_layer_dir, &mount_target, None, MsFlags::MS_BIND, None)
 			.with_context(|| format!("Failed to bind mount to {:?}", mount_target))?
 	} else {
@@ -104,7 +104,7 @@ fn init_task(input_hash: &InputHash, task: &Task) -> Result<fs::Mount> {
 		fs::fixup_permissions(&task_work_dir)?;
 
 		let lower = task
-			.inherit
+			.ancestors
 			.iter()
 			.rev()
 			.map(paths::layer_dir)
@@ -452,7 +452,6 @@ fn run_task(input_hash: &InputHash, task: &Task, jobserver: &mut Jobserver) -> R
 			.env_clear()
 			.env("PATH", "/usr/sbin:/usr/bin:/sbin:/bin")
 			.env("HOME", "/build")
-			.env("INPUT_HASH", input_hash.to_string())
 			.env("MAKEFLAGS", jobserver.to_makeflags())
 			.exec();
 		eprintln!("{}", err);
@@ -569,6 +568,26 @@ fn save_cached(input_hash: &InputHash, output: &TaskOutput) -> Result<()> {
 	Ok(())
 }
 
+trait AsSecsF32 {
+	fn as_secs_f32(&self) -> f32;
+}
+
+impl AsSecsF32 for TimeVal {
+	fn as_secs_f32(&self) -> f32 {
+		self.tv_sec() as f32 + 1e-6 * (self.tv_usec() as f32)
+	}
+}
+
+fn get_usage(total: f32) -> String {
+	let usage = resource::getrusage(resource::UsageWho::RUSAGE_CHILDREN).expect("getrusage()");
+
+	let user = usage.user_time().as_secs_f32();
+	let system = usage.system_time().as_secs_f32();
+	let cpu = (100.0 * (user + system) / total).round();
+
+	format!("{user:.2}s user {system:.2}s system {cpu:.0}% cpu")
+}
+
 pub fn handle(task: Task, jobserver: &mut Jobserver) -> Result<TaskOutput> {
 	let input_hash = input_hash(&task);
 
@@ -597,12 +616,11 @@ pub fn handle(task: Task, jobserver: &mut Jobserver) -> Result<TaskOutput> {
 
 	save_cached(&input_hash, &task_output)?;
 
-	let duration = Instant::now().duration_since(start_time);
+	let duration = Instant::now().duration_since(start_time).as_secs_f32();
+	let usage = get_usage(duration);
 	println!(
-		"Finished task {} ({}) in {}",
-		task.label,
-		input_hash,
-		duration.as_secs_f32()
+		"Finished task {} ({}) in {:.2}s ({})",
+		task.label, input_hash, duration, usage,
 	);
 
 	if let Ok(cached_output) = cached_output {
diff --git a/crates/runner/src/util/checkable.rs b/crates/rebel-runner/src/util/checkable.rs
index 8528d29..8528d29 100644
--- a/crates/runner/src/util/checkable.rs
+++ b/crates/rebel-runner/src/util/checkable.rs
diff --git a/crates/runner/src/util/cjson.rs b/crates/rebel-runner/src/util/cjson.rs
index e3840ce..e3840ce 100644
--- a/crates/runner/src/util/cjson.rs
+++ b/crates/rebel-runner/src/util/cjson.rs
diff --git a/crates/runner/src/util/clone.rs b/crates/rebel-runner/src/util/clone.rs
index 51a31c3..51a31c3 100644
--- a/crates/runner/src/util/clone.rs
+++ b/crates/rebel-runner/src/util/clone.rs
diff --git a/crates/runner/src/util/fs.rs b/crates/rebel-runner/src/util/fs.rs
index 9e16648..9e33eb7 100644
--- a/crates/runner/src/util/fs.rs
+++ b/crates/rebel-runner/src/util/fs.rs
@@ -11,7 +11,7 @@ use nix::{
 	unistd,
 };
 
-use common::error::*;
+use rebel_common::error::*;
 
 pub fn open<P: AsRef<Path>>(path: P) -> Result<fs::File> {
 	fs::File::open(path.as_ref())
@@ -123,5 +123,5 @@ pub fn mount<P1: AsRef<Path>, P2: AsRef<Path>>(
 pub fn pipe() -> Result<(File, File)> {
 	unistd::pipe2(OFlag::O_CLOEXEC)
 		.context("pipe2()")
-		.map(|(piper, pipew)| unsafe { (File::from_raw_fd(piper), File::from_raw_fd(pipew)) })
+		.map(|(piper, pipew)| (File::from(piper), File::from(pipew)))
 }
diff --git a/crates/runner/src/util/mod.rs b/crates/rebel-runner/src/util/mod.rs
index 0fbe3b5..0fbe3b5 100644
--- a/crates/runner/src/util/mod.rs
+++ b/crates/rebel-runner/src/util/mod.rs
diff --git a/crates/runner/src/util/stack.rs b/crates/rebel-runner/src/util/stack.rs
index 15d5daf..15d5daf 100644
--- a/crates/runner/src/util/stack.rs
+++ b/crates/rebel-runner/src/util/stack.rs
diff --git a/crates/runner/src/util/steal.rs b/crates/rebel-runner/src/util/steal.rs
index 91b2cdf..91b2cdf 100644
--- a/crates/runner/src/util/steal.rs
+++ b/crates/rebel-runner/src/util/steal.rs
diff --git a/crates/runner/src/util/unix.rs b/crates/rebel-runner/src/util/unix.rs
index 156e441..a97b1db 100644
--- a/crates/runner/src/util/unix.rs
+++ b/crates/rebel-runner/src/util/unix.rs
@@ -1,12 +1,12 @@
 use std::{fs::File, os::unix::prelude::*, path::Path};
 
 use nix::{
-	fcntl::{self, FcntlArg, FdFlag, OFlag},
+	fcntl::{self, FcntlArg, FdFlag, Flock, OFlag},
 	sched,
 	unistd::Pid,
 };
 
-use common::error::*;
+use rebel_common::error::*;
 
 use super::fs;
 
@@ -65,7 +65,7 @@ pub fn nproc() -> Result<usize> {
 	Ok(count)
 }
 
-pub fn lock<P: AsRef<Path>>(path: P, exclusive: bool, blocking: bool) -> Result<File> {
+pub fn lock<P: AsRef<Path>>(path: P, exclusive: bool, blocking: bool) -> Result<Flock<File>> {
 	use fcntl::FlockArg::*;
 
 	if let Some(parent) = path.as_ref().parent() {
@@ -80,8 +80,7 @@ pub fn lock<P: AsRef<Path>>(path: P, exclusive: bool, blocking: bool) -> Result<
 	};
 
 	let file = fs::create(path.as_ref())?;
-	fcntl::flock(file.as_raw_fd(), arg)
-		.with_context(|| format!("flock failed on {:?}", path.as_ref()))?;
-
-	Ok(file)
+	fcntl::Flock::lock(file, arg)
+		.map_err(|(_, errno)| errno)
+		.with_context(|| format!("flock failed on {:?}", path.as_ref()))
 }
diff --git a/crates/driver/Cargo.toml b/crates/rebel/Cargo.toml
index ecea8b8..9eba0fa 100644
--- a/crates/driver/Cargo.toml
+++ b/crates/rebel/Cargo.toml
@@ -8,18 +8,16 @@ edition = "2021"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
-common = { path = "../common", package = "rebel-common" }
-runner = { path = "../runner", package = "rebel-runner" }
+rebel-common = { path = "../rebel-common" }
+rebel-parse = { path = "../rebel-parse" }
+rebel-resolve = { path = "../rebel-resolve" }
+rebel-runner = { path = "../rebel-runner" }
 
 clap = { version = "4.0.0", features = ["derive"] }
-deb-version = "0.1.1"
-enum-kinds = "0.5.1"
-handlebars = "4.1.3"
+handlebars = "5.1.2"
 indoc = "2.0.4"
 lazy_static = "1.4.0"
-nix = { version = "0.27.1", features = ["poll"] }
-nom = "7.1.0"
-scoped-tls-hkt = "0.1.2"
-serde = { version = "1", features = ["derive", "rc"] }
+nix = { version = "0.28.0", features = ["poll", "signal"] }
+serde = { version = "1", features = ["derive"] }
 serde_yaml = "0.9"
 walkdir = "2"
diff --git a/crates/rebel/src/driver.rs b/crates/rebel/src/driver.rs
new file mode 100644
index 0000000..e4de2a7
--- /dev/null
+++ b/crates/rebel/src/driver.rs
@@ -0,0 +1,481 @@
+use std::{
+	collections::{HashMap, HashSet},
+	iter,
+	os::unix::{net::UnixStream, prelude::*},
+};
+
+use indoc::indoc;
+use nix::{
+	poll,
+	sys::{
+		signal,
+		signalfd::{SfdFlags, SignalFd},
+	},
+};
+
+use rebel_common::{error::*, string_hash::*, types::*};
+use rebel_resolve::{
+	self as resolve,
+	context::{Context, OutputRef, TaskRef},
+	paths,
+	task::*,
+};
+use rebel_runner::Runner;
+
+use crate::template;
+
+#[derive(Debug)]
+pub struct CompletionState<'ctx> {
+	ctx: &'ctx Context,
+	tasks_done: HashMap<TaskRef<'ctx>, TaskOutput>,
+}
+
+impl<'ctx> CompletionState<'ctx> {
+	pub fn new(ctx: &'ctx Context) -> Self {
+		CompletionState {
+			ctx,
+			tasks_done: Default::default(),
+		}
+	}
+
+	// Treats both "depends" and "parent" as dependencies
+	fn deps_satisfied(&self, task_ref: &TaskRef) -> bool {
+		resolve::get_dependent_tasks(self.ctx, task_ref)
+			.map_err(|_| Error::new(format!("invalid dependency for {}", task_ref)))
+			.unwrap()
+			.into_iter()
+			.all(|dep| self.tasks_done.contains_key(&dep))
+	}
+
+	fn fetch_deps(&self, task: &TaskRef<'ctx>) -> Result<Vec<Dependency>> {
+		let task_def = &self.ctx[task];
+		task_def
+			.fetch
+			.iter()
+			.map(|Fetch { name, sha256 }| {
+				Ok(Dependency::Fetch {
+					name: template::ENGINE.eval(name, &task.args).with_context(|| {
+						format!("Failed to evaluate fetch filename for task {}", task)
+					})?,
+					target_dir: paths::TASK_DLDIR.to_string(),
+					sha256: *sha256,
+				})
+			})
+			.collect()
+	}
+
+	fn dep_closure<I>(&self, deps: I, path: &'ctx str) -> impl Iterator<Item = Dependency> + '_
+	where
+		I: IntoIterator<Item = OutputRef<'ctx>>,
+	{
+		resolve::runtime_depends(self.ctx, deps)
+			.expect("invalid runtime depends")
+			.into_iter()
+			.filter_map(|dep| self.tasks_done[&dep.task].outputs.get(dep.output))
+			.map(|&output| Dependency::Task {
+				output,
+				path: path.to_string(),
+			})
+	}
+
+	fn build_deps(&self, task: &TaskRef<'ctx>) -> Result<impl Iterator<Item = Dependency> + '_> {
+		Ok(self.dep_closure(
+			self.ctx
+				.get_build_depends(task)
+				.with_context(|| format!("invalid build depends for {}", task))?,
+			"",
+		))
+	}
+
+	fn host_deps(&self, task: &TaskRef<'ctx>) -> Result<impl Iterator<Item = Dependency> + '_> {
+		Ok(self.dep_closure(
+			self.ctx
+				.get_host_depends(task)
+				.with_context(|| format!("invalid depends for {}", task))?,
+			paths::TASK_SYSROOT,
+		))
+	}
+
+	fn task_deps(&self, task: &TaskRef<'ctx>) -> Result<HashSet<Dependency>> {
+		let fetch_deps = self.fetch_deps(task)?.into_iter();
+		let build_deps = self.build_deps(task)?;
+		let host_deps = self.host_deps(task)?;
+
+		Ok(fetch_deps.chain(build_deps).chain(host_deps).collect())
+	}
+
+	fn task_ancestors(&self, task_ref: &TaskRef<'ctx>) -> Vec<LayerHash> {
+		let Some(parent) = self
+			.ctx
+			.get_parent_depend(task_ref)
+			.expect("invalid parent depends")
+		else {
+			return vec![];
+		};
+
+		let mut chain = self.task_ancestors(&parent);
+		if let Some(layer) = self.tasks_done[&parent].layer {
+			chain.push(layer);
+		}
+		chain
+	}
+
+	fn print_summary(&self) {
+		println!();
+		println!("Summary:");
+
+		let mut tasks: Box<[_]> = self.tasks_done.iter().collect();
+		tasks.sort_by_cached_key(|(task, _)| format!("{:#}", task));
+		for (task_ref, task) in tasks.iter() {
+			println!();
+			println!("{:#}", task_ref);
+			if let Some(hash) = task.input_hash {
+				println!("  input: {}", hash);
+			}
+			if let Some(hash) = task.layer {
+				println!("  layer: {}", hash);
+			}
+			if !task.outputs.is_empty() {
+				println!("  outputs:");
+
+				let mut outputs: Box<[_]> = task.outputs.iter().collect();
+				outputs.sort_by_key(|(output, _)| *output);
+				for (output, hash) in outputs.iter() {
+					println!("    {}: {}", output, hash);
+				}
+			}
+		}
+	}
+}
+
+#[derive(Debug)]
+enum SpawnResult {
+	Spawned(UnixStream),
+	Skipped(TaskOutput),
+}
+
+#[derive(Debug, PartialEq, Eq, Hash)]
+enum TaskWaitResult {
+	Failed,
+	Interrupted,
+}
+
+#[derive(Debug)]
+pub struct Driver<'ctx> {
+	rdeps: HashMap<TaskRef<'ctx>, Vec<TaskRef<'ctx>>>,
+	force_run: HashSet<TaskRef<'ctx>>,
+	tasks_blocked: HashSet<TaskRef<'ctx>>,
+	tasks_runnable: Vec<TaskRef<'ctx>>,
+	tasks_running: HashMap<RawFd, (UnixStream, TaskRef<'ctx>)>,
+	state: CompletionState<'ctx>,
+}
+
+impl<'ctx> Driver<'ctx> {
+	pub fn new(
+		ctx: &'ctx Context,
+		taskset: HashSet<TaskRef<'ctx>>,
+		force_run: HashSet<TaskRef<'ctx>>,
+	) -> Result<Self> {
+		let mut driver = Driver {
+			rdeps: Default::default(),
+			force_run,
+			tasks_blocked: Default::default(),
+			tasks_runnable: Default::default(),
+			tasks_running: Default::default(),
+			state: CompletionState::new(ctx),
+		};
+
+		for task in taskset {
+			let mut has_depends = false;
+			for dep in resolve::get_dependent_tasks(ctx, &task)
+				.map_err(|_| Error::new(format!("invalid dependency for {}", task)))?
+			{
+				let rdep = driver.rdeps.entry(dep.clone()).or_default();
+				rdep.push(task.clone());
+				has_depends = true;
+			}
+
+			if has_depends {
+				driver.tasks_blocked.insert(task);
+			} else {
+				driver.tasks_runnable.push(task);
+			}
+		}
+
+		Ok(driver)
+	}
+
+	const PREAMBLE: &'static str = indoc! {"
+		export PATH={{build.prefix}}/sbin:{{build.prefix}}/bin:$PATH
+		cd {{workdir}}
+
+		export SOURCE_DATE_EPOCH=1
+
+		export AR_FOR_BUILD=ar
+		export AS_FOR_BUILD=as
+		export DLLTOOL_FOR_BUILD=dlltool
+		export CC_FOR_BUILD=gcc
+		export CXX_FOR_BUILD=g++
+		export GCC_FOR_BUILD=gcc
+		export GFORTRAN_FOR_BUILD=gfortran
+		export GOC_FOR_BUILD=goc
+		export LD_FOR_BUILD=ld
+		export LIPO_FOR_BUILD=lipo
+		export NM_FOR_BUILD=nm
+		export OBJCOPY_FOR_BUILD=objcopy
+		export OBJDUMP_FOR_BUILD=objdump
+		export RANLIB_FOR_BUILD=ranlib
+		export STRIP_FOR_BUILD=strip
+		export WINDRES_FOR_BUILD=windres
+		export WINDMC_FOR_BUILD=windmc
+	"};
+	const PREAMBLE_HOST: &'static str = indoc! {"
+		export AR={{build_to_host.cross_compile}}ar
+		export AS={{build_to_host.cross_compile}}as
+		export DLLTOOL={{build_to_host.cross_compile}}dlltool
+		export CC={{build_to_host.cross_compile}}gcc
+		export CXX={{build_to_host.cross_compile}}g++
+		export GCC={{build_to_host.cross_compile}}gcc
+		export GFORTRAN={{build_to_host.cross_compile}}gfortran
+		export GOC={{build_to_host.cross_compile}}goc
+		export LD={{build_to_host.cross_compile}}ld
+		export LIPO={{build_to_host.cross_compile}}lipo
+		export NM={{build_to_host.cross_compile}}nm
+		export OBJCOPY={{build_to_host.cross_compile}}objcopy
+		export OBJDUMP={{build_to_host.cross_compile}}objdump
+		export RANLIB={{build_to_host.cross_compile}}ranlib
+		export STRIP={{build_to_host.cross_compile}}strip
+		export WINDRES={{build_to_host.cross_compile}}windres
+		export WINDMC={{build_to_host.cross_compile}}windmc
+	"};
+	const PREAMBLE_TARGET: &'static str = indoc! {"
+		export AR_FOR_TARGET={{build_to_target.cross_compile}}ar
+		export AS_FOR_TARGET={{build_to_target.cross_compile}}as
+		export DLLTOOL_FOR_TARGET={{build_to_target.cross_compile}}dlltool
+		export CC_FOR_TARGET={{build_to_target.cross_compile}}gcc
+		export CXX_FOR_TARGET={{build_to_target.cross_compile}}g++
+		export GCC_FOR_TARGET={{build_to_target.cross_compile}}gcc
+		export GFORTRAN_FOR_TARGET={{build_to_target.cross_compile}}gfortran
+		export GOC_FOR_TARGET={{build_to_target.cross_compile}}goc
+		export LD_FOR_TARGET={{build_to_target.cross_compile}}ld
+		export LIPO_FOR_TARGET={{build_to_target.cross_compile}}lipo
+		export NM_FOR_TARGET={{build_to_target.cross_compile}}nm
+		export OBJCOPY_FOR_TARGET={{build_to_target.cross_compile}}objcopy
+		export OBJDUMP_FOR_TARGET={{build_to_target.cross_compile}}objdump
+		export RANLIB_FOR_TARGET={{build_to_target.cross_compile}}ranlib
+		export STRIP_FOR_TARGET={{build_to_target.cross_compile}}strip
+		export WINDRES_FOR_TARGET={{build_to_target.cross_compile}}windres
+		export WINDMC_FOR_TARGET={{build_to_target.cross_compile}}windmc
+	"};
+
+	fn task_preamble(task_ref: &TaskRef<'ctx>) -> Vec<&'static str> {
+		let mut ret = vec![Self::PREAMBLE];
+
+		if task_ref.args.contains_key("build_to_host") {
+			ret.push(Self::PREAMBLE_HOST);
+		}
+		if task_ref.args.contains_key("build_to_target") {
+			ret.push(Self::PREAMBLE_TARGET);
+		}
+		ret
+	}
+
+	fn update_runnable(&mut self, task_ref: TaskRef<'ctx>, task_output: TaskOutput) {
+		let rdeps = self.rdeps.get(&task_ref);
+
+		self.state.tasks_done.insert(task_ref, task_output);
+
+		for rdep in rdeps.unwrap_or(&Vec::new()) {
+			if !self.tasks_blocked.contains(rdep) {
+				continue;
+			}
+			if self.state.deps_satisfied(rdep) {
+				self.tasks_blocked.remove(rdep);
+				self.tasks_runnable.push(rdep.clone());
+			}
+		}
+	}
+
+	fn spawn_task(&self, task_ref: &TaskRef<'ctx>, runner: &Runner) -> Result<SpawnResult> {
+		let task_def = &self.state.ctx[task_ref];
+		if task_def.action.is_empty() {
+			println!("Skipping empty task {:#}", task_ref);
+			return Ok(SpawnResult::Skipped(TaskOutput::default()));
+		}
+
+		let task_deps = self.state.task_deps(task_ref)?;
+		let task_output = task_def
+			.output
+			.iter()
+			.map(|(name, Output { path, .. })| {
+				let output_path = if let Some(path) = path {
+					format!("{}/{}", paths::TASK_DESTDIR, path)
+				} else {
+					paths::TASK_DESTDIR.to_string()
+				};
+				(name.clone(), output_path)
+			})
+			.collect();
+
+		let ancestors = self.state.task_ancestors(task_ref);
+
+		let mut run = Self::task_preamble(task_ref);
+		run.push(&task_def.action.run);
+
+		let command = template::ENGINE
+			.eval_sh(&run.concat(), &task_ref.args)
+			.with_context(|| {
+				format!("Failed to evaluate command template for task {}", task_ref)
+			})?;
+
+		let rootfs = self.state.ctx.get_rootfs();
+		let task = Task {
+			label: format!("{:#}", task_ref),
+			command,
+			workdir: paths::TASK_WORKDIR.to_string(),
+			rootfs: rootfs.0,
+			ancestors,
+			depends: task_deps,
+			outputs: task_output,
+			pins: HashMap::from([rootfs.clone()]),
+			force_run: self.force_run.contains(task_ref),
+		};
+
+		Ok(SpawnResult::Spawned(runner.spawn(&task)))
+	}
+
+	fn run_task(&mut self, task_ref: TaskRef<'ctx>, runner: &Runner) -> Result<()> {
+		match self.spawn_task(&task_ref, runner)? {
+			SpawnResult::Spawned(socket) => {
+				assert!(self
+					.tasks_running
+					.insert(socket.as_raw_fd(), (socket, task_ref))
+					.is_none());
+			}
+			SpawnResult::Skipped(result) => {
+				self.update_runnable(task_ref, result);
+			}
+		}
+		Ok(())
+	}
+
+	fn run_tasks(&mut self, runner: &Runner) -> Result<()> {
+		while let Some(task_ref) = self.tasks_runnable.pop() {
+			self.run_task(task_ref, runner)?;
+		}
+		Ok(())
+	}
+
+	fn wait_for_task(&mut self, signal_fd: &mut SignalFd) -> Result<Option<TaskWaitResult>> {
+		let mut pollfds: Vec<_> = self
+			.tasks_running
+			.values()
+			.map(|(socket, _)| socket.as_fd())
+			.chain(iter::once(signal_fd.as_fd()))
+			.map(|fd| poll::PollFd::new(fd, poll::PollFlags::POLLIN))
+			.collect();
+
+		while poll::poll(&mut pollfds, poll::PollTimeout::NONE).context("poll()")? == 0 {}
+
+		let pollevents: Vec<_> = pollfds
+			.into_iter()
+			.map(|pollfd| {
+				(
+					pollfd.as_fd().as_raw_fd(),
+					pollfd.revents().expect("Unknown events in poll() return"),
+				)
+			})
+			.collect();
+
+		for (fd, events) in pollevents {
+			if !events.contains(poll::PollFlags::POLLIN) {
+				if events.intersects(!poll::PollFlags::POLLIN) {
+					return Err(Error::new(
+						"Unexpected error status for socket file descriptor",
+					));
+				}
+				continue;
+			}
+
+			if fd == signal_fd.as_raw_fd() {
+				let _signal = signal_fd.read_signal().expect("read_signal()").unwrap();
+				return Ok(Some(TaskWaitResult::Interrupted));
+			}
+
+			let (socket, task_ref) = self.tasks_running.remove(&fd).unwrap();
+
+			match Runner::result(&socket) {
+				Ok(task_output) => {
+					self.update_runnable(task_ref, task_output);
+				}
+				Err(error) => {
+					eprintln!("{}", error);
+					return Ok(Some(TaskWaitResult::Failed));
+				}
+			}
+		}
+
+		Ok(None)
+	}
+
+	fn is_done(&self) -> bool {
+		self.tasks_blocked.is_empty()
+			&& self.tasks_runnable.is_empty()
+			&& self.tasks_running.is_empty()
+	}
+
+	fn setup_signalfd() -> Result<SignalFd> {
+		let mut signals = signal::SigSet::empty();
+		signals.add(signal::Signal::SIGINT);
+		signal::pthread_sigmask(signal::SigmaskHow::SIG_BLOCK, Some(&signals), None)
+			.expect("pthread_sigmask()");
+		SignalFd::with_flags(&signals, SfdFlags::SFD_CLOEXEC)
+			.context("Failed to create signal file descriptor")
+	}
+
+	fn raise_sigint() {
+		let mut signals = signal::SigSet::empty();
+		signals.add(signal::Signal::SIGINT);
+		signal::pthread_sigmask(signal::SigmaskHow::SIG_UNBLOCK, Some(&signals), None)
+			.expect("pthread_sigmask()");
+		signal::raise(signal::Signal::SIGINT).expect("raise()");
+		unreachable!();
+	}
+
+	pub fn run(&mut self, runner: &Runner, keep_going: bool) -> Result<bool> {
+		let mut success = true;
+		let mut interrupted = false;
+
+		let mut signal_fd = Self::setup_signalfd()?;
+
+		self.run_tasks(runner)?;
+
+		while !self.tasks_running.is_empty() {
+			match self.wait_for_task(&mut signal_fd)? {
+				Some(TaskWaitResult::Failed) => {
+					success = false;
+				}
+				Some(TaskWaitResult::Interrupted) => {
+					if interrupted {
+						Self::raise_sigint();
+					}
+					eprintln!("Interrupt received, not spawning new tasks. Interrupt again to stop immediately.");
+					interrupted = true;
+				}
+				None => {}
+			}
+			if !interrupted && (success || keep_going) {
+				self.run_tasks(runner)?;
+			}
+		}
+
+		if interrupted || !success {
+			return Ok(false);
+		}
+
+		assert!(self.is_done(), "No runnable tasks left");
+		self.state.print_summary();
+
+		Ok(true)
+	}
+}
diff --git a/crates/driver/src/main.rs b/crates/rebel/src/main.rs
index 98aa10a..625b43d 100644
--- a/crates/driver/src/main.rs
+++ b/crates/rebel/src/main.rs
@@ -1,19 +1,15 @@
-mod args;
-mod context;
 mod driver;
-mod parse;
-mod paths;
-mod pin;
 mod recipe;
-mod resolve;
-mod task;
 mod template;
 
-use std::collections::HashSet;
+use std::{collections::HashSet, fs::File, path::Path};
 
 use clap::Parser;
 
-use runner::Runner;
+use rebel_common::error::*;
+use rebel_parse as parse;
+use rebel_resolve::{self as resolve, context, pin};
+use rebel_runner::{self as runner, Runner};
 
 #[derive(Parser)]
 #[clap(version, about)]
@@ -22,11 +18,22 @@ struct Opts {
 	/// Defaults to the number of available CPUs
 	#[clap(short, long)]
 	jobs: Option<usize>,
+	/// Keep going after some tasks have failed
+	#[clap(short, long)]
+	keep_going: bool,
 	/// The tasks to run
 	#[clap(name = "task", required = true)]
 	tasks: Vec<String>,
 }
 
+fn read_pins<P: AsRef<Path>>(path: P) -> Result<pin::Pins> {
+	let f = File::open(path)?;
+	let pins: pin::Pins = serde_yaml::from_reader(f)
+		.map_err(Error::new)
+		.context("YAML error")?;
+	Ok(pins)
+}
+
 fn main() {
 	let opts: Opts = Opts::parse();
 
@@ -34,7 +41,7 @@ fn main() {
 
 	let ctx = context::Context::new(
 		recipe::read_recipes("examples/recipes").unwrap(),
-		pin::read_pins("examples/pins.yml").unwrap(),
+		read_pins("examples/pins.yml").unwrap(),
 	)
 	.unwrap();
 
@@ -42,7 +49,11 @@ fn main() {
 	let mut force_run = HashSet::new();
 
 	for task in opts.tasks {
-		let (task_ref, flags) = match ctx.parse(&task) {
+		let Ok((parsed, flags)) = parse::task_ref::task_ref_with_flags(&task) else {
+			eprintln!("Invalid task syntax");
+			std::process::exit(1);
+		};
+		let task_ref = match ctx.lookup(parsed.id, parsed.args.host, parsed.args.target) {
 			Ok(task_ref) => task_ref,
 			Err(err) => {
 				eprintln!("{}", err);
@@ -62,8 +73,15 @@ fn main() {
 	}
 	let taskset = rsv.into_taskset();
 	let mut driver = driver::Driver::new(&ctx, taskset, force_run).unwrap();
-	if let Err(error) = driver.run(&runner) {
-		eprintln!("{}", error);
-		std::process::exit(1);
+	match driver.run(&runner, opts.keep_going) {
+		Ok(success) => {
+			if !success {
+				std::process::exit(1);
+			}
+		}
+		Err(error) => {
+			eprintln!("{}", error);
+			std::process::exit(1);
+		}
 	}
 }
diff --git a/crates/rebel/src/recipe.rs b/crates/rebel/src/recipe.rs
new file mode 100644
index 0000000..28cc84c
--- /dev/null
+++ b/crates/rebel/src/recipe.rs
@@ -0,0 +1,167 @@
+use std::{collections::HashMap, ffi::OsStr, fs::File, path::Path};
+
+use serde::{de::DeserializeOwned, Deserialize};
+use walkdir::WalkDir;
+
+use rebel_common::error::*;
+use rebel_resolve::task::{TaskDef, TaskMeta};
+
+#[derive(Clone, Debug, Deserialize, Default)]
+pub struct RecipeMeta {
+	pub name: Option<String>,
+	pub version: Option<String>,
+}
+
+#[derive(Debug, Deserialize)]
+struct Recipe {
+	#[serde(default)]
+	pub meta: RecipeMeta,
+	pub tasks: HashMap<String, TaskDef>,
+}
+
+#[derive(Debug, Deserialize)]
+struct Subrecipe {
+	pub tasks: HashMap<String, TaskDef>,
+}
+
+fn read_yaml<T: DeserializeOwned>(path: &Path) -> Result<T> {
+	let f = File::open(path).context("IO error")?;
+
+	let value: T = serde_yaml::from_reader(f)
+		.map_err(Error::new)
+		.context("YAML error")?;
+
+	Ok(value)
+}
+
+const RECIPE_NAME: &str = "build";
+const RECIPE_PREFIX: &str = "build.";
+
+fn recipe_name(path: &Path) -> Option<&str> {
+	if path.extension() != Some("yml".as_ref()) {
+		return None;
+	}
+
+	let stem = path.file_stem()?.to_str()?;
+	if stem == RECIPE_NAME {
+		return Some("");
+	}
+	stem.strip_prefix(RECIPE_PREFIX)
+}
+
+fn handle_recipe_tasks(
+	tasks: &mut HashMap<String, HashMap<String, Vec<TaskDef>>>,
+	recipe_tasks: HashMap<String, TaskDef>,
+	meta: &TaskMeta,
+) {
+	let task_map = match tasks.get_mut(&meta.recipe) {
+		Some(task_map) => task_map,
+		None => tasks.entry(meta.recipe.clone()).or_default(),
+	};
+
+	for (label, mut task) in recipe_tasks {
+		task.meta = meta.clone();
+		task_map.entry(label).or_default().push(task);
+	}
+}
+
+fn read_recipe_tasks(
+	path: &Path,
+	basename: &str,
+	tasks: &mut HashMap<String, HashMap<String, Vec<TaskDef>>>,
+) -> Result<RecipeMeta> {
+	let recipe_def = read_yaml::<Recipe>(path)?;
+
+	let name = recipe_def
+		.meta
+		.name
+		.as_deref()
+		.unwrap_or(basename)
+		.to_string();
+
+	let meta = TaskMeta {
+		basename: basename.to_string(),
+		recipename: "".to_string(),
+		recipe: basename.to_string(),
+		name,
+		version: recipe_def.meta.version.clone(),
+	};
+
+	handle_recipe_tasks(tasks, recipe_def.tasks, &meta);
+
+	Ok(recipe_def.meta)
+}
+
+fn read_subrecipe_tasks(
+	path: &Path,
+	basename: &str,
+	recipename: &str,
+	recipe_meta: &RecipeMeta,
+	tasks: &mut HashMap<String, HashMap<String, Vec<TaskDef>>>,
+) -> Result<()> {
+	let recipe = format!("{basename}/{recipename}");
+	let recipe_def = read_yaml::<Subrecipe>(path)?;
+
+	let name = recipe_meta.name.as_deref().unwrap_or(basename).to_string();
+
+	let meta = TaskMeta {
+		basename: basename.to_string(),
+		recipename: recipename.to_string(),
+		recipe: recipe.clone(),
+		name,
+		version: recipe_meta.version.clone(),
+	};
+
+	handle_recipe_tasks(tasks, recipe_def.tasks, &meta);
+
+	Ok(())
+}
+
+pub fn read_recipes<P: AsRef<Path>>(
+	path: P,
+) -> Result<HashMap<String, HashMap<String, Vec<TaskDef>>>> {
+	let mut tasks = HashMap::<String, HashMap<String, Vec<TaskDef>>>::new();
+	let mut recipe_metas = HashMap::<String, RecipeMeta>::new();
+
+	for entry in WalkDir::new(path)
+		.sort_by(|a, b| {
+			// Files are sorted first by stem, then by extension, so that
+			// recipe.yml will always be read before recipe.NAME.yml
+			let stem_cmp = a.path().file_stem().cmp(&b.path().file_stem());
+			let ext_cmp = a.path().extension().cmp(&b.path().extension());
+			stem_cmp.then(ext_cmp)
+		})
+		.into_iter()
+		.filter_map(|e| e.ok())
+	{
+		let path = entry.path();
+		if !path.is_file() {
+			continue;
+		}
+
+		let Some(recipename) = recipe_name(path) else {
+			continue;
+		};
+		let Some(basename) = path
+			.parent()
+			.and_then(Path::file_name)
+			.and_then(OsStr::to_str)
+		else {
+			continue;
+		};
+
+		if recipename.is_empty() {
+			recipe_metas.insert(
+				basename.to_string(),
+				read_recipe_tasks(path, basename, &mut tasks)?,
+			);
+		} else {
+			let Some(recipe_meta) = recipe_metas.get(basename) else {
+				continue;
+			};
+			read_subrecipe_tasks(path, basename, recipename, recipe_meta, &mut tasks)?;
+		}
+	}
+
+	Ok(tasks)
+}
diff --git a/crates/driver/src/template.rs b/crates/rebel/src/template.rs
index 7bb089c..50fb334 100644
--- a/crates/driver/src/template.rs
+++ b/crates/rebel/src/template.rs
@@ -1,42 +1,39 @@
 use handlebars::Handlebars;
 use lazy_static::lazy_static;
 
-use common::error::*;
+use rebel_common::error::*;
+use rebel_resolve::args::TaskArgs;
 
-use crate::args::TaskArgs;
-
-fn escape(s: &str) -> String {
+fn escape_sh(s: &str) -> String {
 	format!("'{}'", s.replace('\'', "'\\''"))
 }
 
 #[derive(Debug)]
 pub struct TemplateEngine {
 	tpl: Handlebars<'static>,
-	tpl_raw: Handlebars<'static>,
+	tpl_sh: Handlebars<'static>,
 }
 
 impl TemplateEngine {
 	pub fn new() -> Self {
 		let mut tpl = Handlebars::new();
 		tpl.set_strict_mode(true);
-		tpl.register_escape_fn(escape);
-
-		let mut tpl_raw = Handlebars::new();
-		tpl_raw.set_strict_mode(true);
-		tpl_raw.register_escape_fn(handlebars::no_escape);
+		tpl.register_escape_fn(handlebars::no_escape);
 
-		TemplateEngine { tpl, tpl_raw }
-	}
+		let mut tpl_sh = Handlebars::new();
+		tpl_sh.set_strict_mode(true);
+		tpl_sh.register_escape_fn(escape_sh);
 
-	pub fn eval_raw(&self, input: &str, args: &TaskArgs) -> Result<String> {
-		self.tpl_raw
-			.render_template(input, args)
-			.map_err(Error::new)
+		TemplateEngine { tpl, tpl_sh }
 	}
 
 	pub fn eval(&self, input: &str, args: &TaskArgs) -> Result<String> {
 		self.tpl.render_template(input, args).map_err(Error::new)
 	}
+
+	pub fn eval_sh(&self, input: &str, args: &TaskArgs) -> Result<String> {
+		self.tpl_sh.render_template(input, args).map_err(Error::new)
+	}
 }
 
 lazy_static! {