mod form;
#[cfg(test)]
mod tests;
use serde::Serialize;
use crate::hash::HashMap;
use crate::limits::{Held, Refusal};
use crate::protocol::{self, Check, Class, Cost, Kind, Limit, Operation, Produced, Status};
use crate::{Error, ErrorKind, Limits, Progress, Settings};
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
pub struct NodeId(u32);
impl NodeId {
pub const fn new(raw: u32) -> Self {
Self(raw)
}
pub const fn index(self) -> u32 {
self.0
}
}
impl std::fmt::Display for NodeId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct ValueId(u32);
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct RecordId(u32);
#[derive(Clone, Debug)]
struct Value {
kind: &'static Kind,
text: Box<str>,
}
#[derive(Clone, Debug)]
struct Recipe {
operation: &'static Operation,
from: Vec<NodeId>,
parameters: Box<str>,
settings: Box<str>,
}
impl PartialEq for Recipe {
fn eq(&self, other: &Self) -> bool {
self.operation.name == other.operation.name
&& self.from == other.from
&& self.parameters == other.parameters
&& self.settings == other.settings
}
}
impl Eq for Recipe {}
#[derive(Clone, Debug, PartialEq, Eq)]
enum Body {
Given(ValueId),
Derived {
recipe: Recipe,
record: Option<RecordId>,
},
Work {
recipe: Recipe,
value: ValueId,
started: Vec<ValueId>,
},
Copy {
recipe: Recipe,
value: ValueId,
},
}
#[derive(Clone, Debug, PartialEq, Eq)]
struct Node {
id: NodeId,
body: Body,
}
impl Node {
const fn recipe(&self) -> Option<&Recipe> {
match &self.body {
Body::Given(_) => None,
Body::Derived { recipe, .. }
| Body::Work { recipe, .. }
| Body::Copy { recipe, .. } => Some(recipe),
}
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct Key {
operation: &'static str,
parameters: Box<str>,
settings: Box<str>,
inputs: Vec<ValueId>,
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum End {
Done,
Limit(Limit),
Refused(Box<str>),
}
#[derive(Clone, Debug)]
struct Record {
key: Key,
end: End,
output: Option<ValueId>,
check: Option<Check>,
foreign: bool,
trusted: bool,
made: u64,
}
#[derive(Clone, Debug)]
struct Swap {
id: NodeId,
before: Option<Node>,
after: Option<Node>,
}
#[derive(Clone, Debug)]
struct Entry {
name: Box<str>,
swaps: Vec<Swap>,
pins: Vec<RecordId>,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum State {
Given,
Current,
OutOfDate(Cause),
NotRun,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Cause {
Input(NodeId),
Recipe,
Version,
Waits(NodeId),
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, serde::Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum What {
Output,
Check,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct NodeView<'a> {
pub id: NodeId,
pub kind: &'static str,
pub value: Option<&'a str>,
pub operation: Option<&'static str>,
pub from: &'a [NodeId],
pub parameters: Option<&'a str>,
pub settings: Option<&'a str>,
pub state: State,
pub end: Option<&'a End>,
pub check: Option<&'a Check>,
}
#[non_exhaustive]
#[derive(Clone, Debug, Serialize, serde::Deserialize)]
pub struct Computed {
node: u32,
operation: String,
parameters: String,
settings: String,
inputs: Vec<String>,
output: Result<Output, String>,
check: Option<Check>,
}
#[derive(Clone, Debug, Serialize, serde::Deserialize)]
struct Output {
value: String,
limit: Option<(String, Option<String>)>,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Ran {
pub node: NodeId,
pub state: State,
}
#[derive(Clone, Debug, Default)]
pub struct Workspace {
values: Vec<Value>,
interned: HashMap<(&'static str, Box<str>), ValueId>,
nodes: Vec<Node>,
next: u32,
records: Vec<Option<Record>>,
index: HashMap<Key, RecordId>,
log: Vec<Entry>,
at: usize,
made: u64,
}
fn base_settings() -> Settings {
Settings::default().deterministic()
}
fn at_key<'v>(value: &'v serde_json::Value, key: &str) -> Option<&'v serde_json::Value> {
key.split('.')
.try_fold(value, |value, part| value.get(part))
}
fn project(settings: &Settings, reads: &[&str]) -> Result<Box<str>, Error> {
let whole = serde_json::to_value(settings.clone().deterministic()).map_err(json_error)?;
let mut picked = serde_json::Map::new();
for key in reads {
if let Some(value) = at_key(&whole, key) {
picked.insert((*key).to_owned(), value.clone());
}
}
Ok(serde_json::Value::Object(picked).to_string().into())
}
fn settings_of(projection: &str) -> Result<Settings, Error> {
let mut whole = serde_json::to_value(base_settings()).map_err(json_error)?;
let keys: serde_json::Map<String, serde_json::Value> =
serde_json::from_str(projection).map_err(json_error)?;
for (key, value) in keys {
let mut at = &mut whole;
let mut parts = key.split('.').peekable();
while let Some(part) = parts.next() {
let object = at.as_object_mut().ok_or_else(|| Error::InvalidOption {
key: "settings",
message: format!("{key} names no setting"),
})?;
if parts.peek().is_none() {
object.insert(part.to_owned(), value);
break;
}
at = object.get_mut(part).ok_or_else(|| Error::InvalidOption {
key: "settings",
message: format!("{key} names no setting"),
})?;
}
}
let settings: Settings =
serde_json::from_value(whole).map_err(|error| Error::InvalidOption {
key: "settings",
message: error.to_string(),
})?;
Ok(settings.deterministic())
}
fn canonical(parameters: &str) -> Result<Box<str>, Error> {
if parameters.trim().is_empty() {
return Ok("".into());
}
let value: serde_json::Value =
serde_json::from_str(parameters).map_err(|error| Error::InvalidOption {
key: "parameters",
message: error.to_string(),
})?;
if !value.is_object() {
return Err(Error::InvalidOption {
key: "parameters",
message: "parameters are a JSON object".to_owned(),
});
}
Ok(value.to_string().into())
}
fn json_error(error: serde_json::Error) -> Error {
Error::Json {
form: "workspace",
message: error.to_string(),
}
}
fn refused(what: Held, count: usize, limit: u64) -> Error {
Error::Refused(Refusal::Workspace {
what,
count: u64::try_from(count).unwrap_or(u64::MAX),
limit,
})
}
fn past(count: usize, bound: Option<u64>) -> Option<u64> {
bound.filter(|&bound| u64::try_from(count).unwrap_or(u64::MAX) > bound)
}
fn rebind(node: &mut Node, bounds: &serde_json::Value) -> bool {
let recipe = match &mut node.body {
Body::Given(_) => return false,
Body::Derived { recipe, .. } | Body::Work { recipe, .. } | Body::Copy { recipe, .. } => {
recipe
}
};
let Ok(mut keys) =
serde_json::from_str::<serde_json::Map<String, serde_json::Value>>(&recipe.settings)
else {
return false;
};
let mut touched = false;
for (key, value) in &mut keys {
if let Some(limit) = key.strip_prefix("limits.").and_then(|k| at_key(bounds, k))
&& value != limit
{
*value = limit.clone();
touched = true;
}
}
if touched {
recipe.settings = serde_json::Value::Object(keys).to_string().into();
}
touched
}
impl Workspace {
pub fn new() -> Self {
Self::default()
}
fn node(&self, id: NodeId) -> Option<&Node> {
self.nodes
.binary_search_by_key(&id, |node| node.id)
.ok()
.map(|at| &self.nodes[at])
}
fn record(&self, id: RecordId) -> Option<&Record> {
self.records.get(id.0 as usize).and_then(Option::as_ref)
}
fn text(&self, id: ValueId) -> &str {
&self.values[id.0 as usize].text
}
fn shown(&self, node: &Node) -> Option<ValueId> {
match &node.body {
Body::Given(value) | Body::Work { value, .. } | Body::Copy { value, .. } => {
Some(*value)
}
Body::Derived { record, .. } => record
.and_then(|record| self.record(record))
.and_then(|r| r.output),
}
}
fn kind_of(&self, node: &Node) -> &'static str {
match &node.body {
Body::Given(value) => self.values[value.0 as usize].kind.name,
Body::Derived { recipe, .. }
| Body::Work { recipe, .. }
| Body::Copy { recipe, .. } => recipe.operation.to,
}
}
fn intern(
&mut self,
kind: &'static Kind,
text: &str,
limits: &Limits,
) -> Result<ValueId, Error> {
if let Some(&id) = self.interned.get(&(kind.name, Box::from(text))) {
return Ok(id);
}
let bytes = self.bytes() + text.len();
if let Some(limit) = past(bytes, limits.workspace.bytes) {
return Err(refused(Held::Bytes, bytes, limit));
}
let id = ValueId(u32::try_from(self.values.len()).map_err(|_| {
Error::Refused(Refusal::Index {
what: crate::limits::Space::Node,
count: u64::MAX,
most: u64::from(u32::MAX),
})
})?);
self.values.push(Value {
kind,
text: text.into(),
});
self.interned.insert((kind.name, text.into()), id);
Ok(id)
}
fn bytes(&self) -> usize {
self.values.iter().map(|value| value.text.len()).sum()
}
fn key_of(&self, recipe: &Recipe) -> Result<Key, NodeId> {
let mut inputs = Vec::with_capacity(recipe.from.len());
for &input in &recipe.from {
let value = self.node(input).and_then(|node| self.shown(node));
inputs.push(value.ok_or(input)?);
}
Ok(Key {
operation: recipe.operation.name,
parameters: recipe.parameters.clone(),
settings: recipe.settings.clone(),
inputs,
})
}
fn states(&self) -> Vec<State> {
let mut states: Vec<State> = Vec::with_capacity(self.nodes.len());
let state_of = |states: &Vec<State>, id: NodeId| {
self.nodes
.binary_search_by_key(&id, |node| node.id)
.ok()
.map(|at| states[at])
};
for node in &self.nodes {
let state = match &node.body {
Body::Given(_) | Body::Copy { .. } => State::Given,
Body::Derived { recipe, record } => {
let waits = recipe.from.iter().copied().find(|&input| {
!matches!(
state_of(&states, input),
Some(State::Given | State::Current)
) || self.failed(input)
});
let shown = record.and_then(|record| self.record(record));
match (waits, shown) {
(Some(_), None) | (None, None) => State::NotRun,
(Some(input), Some(_)) => State::OutOfDate(Cause::Waits(input)),
(None, Some(shown)) => match self.key_of(recipe) {
Ok(key) if key == shown.key && shown.foreign => {
State::OutOfDate(Cause::Version)
}
Ok(key) if key == shown.key => State::Current,
Ok(key) => State::OutOfDate(
key.inputs
.iter()
.zip(&shown.key.inputs)
.zip(&recipe.from)
.find(|((now, then), _)| now != then)
.map_or(Cause::Recipe, |(_, &input)| Cause::Input(input)),
),
Err(input) => State::OutOfDate(Cause::Waits(input)),
},
}
}
Body::Work {
recipe, started, ..
} => {
let waits = recipe.from.iter().copied().find(|&input| {
!matches!(
state_of(&states, input),
Some(State::Given | State::Current)
)
});
match (waits, self.key_of(recipe)) {
(Some(input), _) | (None, Err(input)) => {
State::OutOfDate(Cause::Waits(input))
}
(None, Ok(key)) => key
.inputs
.iter()
.zip(started)
.zip(&recipe.from)
.find(|((now, then), _)| now != then)
.map_or(State::Current, |(_, &input)| {
State::OutOfDate(Cause::Input(input))
}),
}
}
};
states.push(state);
}
states
}
fn failed(&self, id: NodeId) -> bool {
self.node(id)
.and_then(|node| match &node.body {
Body::Derived {
record: Some(record),
..
} => self.record(*record),
_ => None,
})
.and_then(|record| record.check.as_ref())
.is_some_and(|check| check.status == Status::Failed)
}
pub fn state(&self, node: NodeId) -> State {
self.nodes
.binary_search_by_key(&node, |n| n.id)
.map_or(State::NotRun, |at| self.states()[at])
}
pub fn nodes(&self) -> impl Iterator<Item = NodeView<'_>> + '_ {
let states = self.states();
self.nodes.iter().zip(states).map(|(node, state)| {
let recipe = node.recipe();
let shown = match &node.body {
Body::Derived {
record: Some(record),
..
} => self.record(*record),
_ => None,
};
NodeView {
id: node.id,
kind: self.kind_of(node),
value: self.shown(node).map(|value| self.text(value)),
operation: recipe.map(|recipe| recipe.operation.name),
from: recipe.map_or(&[], |recipe| &recipe.from),
parameters: recipe.map(|recipe| &*recipe.parameters),
settings: recipe.map(|recipe| &*recipe.settings),
state,
end: shown.map(|record| &record.end),
check: shown.and_then(|record| record.check.as_ref()),
}
})
}
pub fn value(&self, node: NodeId) -> Option<&str> {
self.node(node)
.and_then(|node| self.shown(node))
.map(|value| self.text(value))
}
pub fn layers(&self) -> Vec<(NodeId, u32)> {
let mut columns: Vec<(NodeId, u32)> = Vec::with_capacity(self.nodes.len());
for node in &self.nodes {
let column = node.recipe().map_or(0, |recipe| {
recipe
.from
.iter()
.filter_map(|input| {
columns
.binary_search_by_key(input, |&(id, _)| id)
.ok()
.map(|at| columns[at].1 + 1)
})
.max()
.unwrap_or(0)
});
columns.push((node.id, column));
}
columns
}
pub fn undoable(&self) -> Option<&str> {
self.at.checked_sub(1).map(|at| &*self.log[at].name)
}
pub fn redoable(&self) -> Option<&str> {
self.log.get(self.at).map(|entry| &*entry.name)
}
fn put(&mut self, id: NodeId, node: Option<Node>) -> Option<Node> {
match (self.nodes.binary_search_by_key(&id, |n| n.id), node) {
(Ok(at), Some(node)) => Some(std::mem::replace(&mut self.nodes[at], node)),
(Ok(at), None) => Some(self.nodes.remove(at)),
(Err(at), Some(node)) => {
self.nodes.insert(at, node);
None
}
(Err(_), None) => None,
}
}
pub fn edit<T>(
&mut self,
name: &str,
limits: &Limits,
f: impl FnOnce(&mut Edit<'_>) -> Result<T, Error>,
) -> Result<T, Error> {
self.collect(limits);
let pins = self.pinned_now();
let mut edit = Edit {
workspace: self,
limits,
swaps: Vec::new(),
};
let done = f(&mut edit);
let mut swaps = std::mem::take(&mut edit.swaps);
match done {
Ok(done) => {
for (id, before) in self.settled(&[]) {
if let Some(now) = self.node(id).cloned() {
let mut then = now.clone();
if let Body::Derived { record, .. } = &mut then.body {
*record = before;
}
swaps.push(Swap {
id,
before: Some(then),
after: Some(now),
});
}
}
if !swaps.is_empty() {
self.log.truncate(self.at);
self.log.push(Entry {
name: name.into(),
swaps,
pins,
});
if let Some(bound) = limits.workspace.log {
let most = usize::try_from(bound).unwrap_or(usize::MAX);
let over = self.log.len().saturating_sub(most);
self.log.drain(..over);
}
self.at = self.log.len();
self.made += 1;
}
Ok(done)
}
Err(error) => {
for swap in swaps.into_iter().rev() {
self.put(swap.id, swap.before);
}
Err(error)
}
}
}
fn pinned_now(&self) -> Vec<RecordId> {
self.nodes
.iter()
.filter_map(|node| match &node.body {
Body::Derived { record, .. } => *record,
_ => None,
})
.collect()
}
pub fn undo(&mut self) -> Option<String> {
let at = self.at.checked_sub(1)?;
let swaps: Vec<Swap> = self.log[at].swaps.clone();
let touched: Vec<NodeId> = swaps.iter().map(|swap| swap.id).collect();
for swap in swaps.into_iter().rev() {
self.put(swap.id, swap.before);
}
self.at = at;
self.settled(&touched);
Some(self.log[at].name.to_string())
}
pub fn redo(&mut self) -> Option<String> {
let swaps: Vec<Swap> = self.log.get(self.at)?.swaps.clone();
let touched: Vec<NodeId> = swaps.iter().map(|swap| swap.id).collect();
for swap in swaps {
self.put(swap.id, swap.after);
}
self.at += 1;
self.settled(&touched);
Some(self.log[self.at - 1].name.to_string())
}
pub fn settle(&mut self) -> Vec<NodeId> {
self.settled(&[]).into_iter().map(|(id, _)| id).collect()
}
fn settled(&mut self, kept: &[NodeId]) -> Vec<(NodeId, Option<RecordId>)> {
let mut moved = Vec::new();
for at in 0..self.nodes.len() {
if kept.contains(&self.nodes[at].id) {
continue;
}
let Body::Derived { recipe, record } = &self.nodes[at].body else {
continue;
};
let Ok(key) = self.key_of(recipe) else {
continue;
};
let fits = |record: &Option<RecordId>| {
record
.and_then(|record| self.record(record))
.is_some_and(|record| record.key == key && !record.foreign)
};
if fits(record) {
continue;
}
if let Some(&found) = self.index.get(&key)
&& self.record(found).is_some_and(|record| !record.foreign)
{
let id = self.nodes[at].id;
if let Body::Derived { record, .. } = &mut self.nodes[at].body {
moved.push((id, record.replace(found)));
}
}
}
moved
}
pub fn work(&mut self, node: NodeId, session: &str, limits: &Limits) -> Result<(), Error> {
let Some(at) = self.nodes.binary_search_by_key(&node, |n| n.id).ok() else {
return Err(no_node(node));
};
let Body::Work { recipe, .. } = &self.nodes[at].body else {
return Err(Error::NotApplicable {
operation: "work".into(),
reason: format!("node {node} holds no proof in progress"),
});
};
let (_, kind) = protocol::kind(recipe.operation.to)?;
protocol::read(kind.name, session, limits)?;
let id = self.intern(kind, session, limits)?;
if let Body::Work { value, .. } = &mut self.nodes[at].body {
*value = id;
}
self.made += 1;
Ok(())
}
pub fn plan(&self, targets: &[NodeId]) -> Vec<NodeId> {
let mut wanted: Vec<NodeId> = targets.to_vec();
let mut at = 0;
while at < wanted.len() {
if let Some(recipe) = self.node(wanted[at]).and_then(Node::recipe) {
for &input in &recipe.from {
if !wanted.contains(&input) {
wanted.push(input);
}
}
}
at += 1;
}
wanted.sort_unstable();
let states = self.states();
self.nodes
.iter()
.zip(states)
.filter(|(node, state)| {
wanted.binary_search(&node.id).is_ok()
&& matches!(node.body, Body::Derived { .. })
&& !matches!(state, State::Current)
})
.map(|(node, _)| node.id)
.collect()
}
pub fn compute(
&self,
node: NodeId,
what: What,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Computed, Error> {
let stopped = std::cell::Cell::new(false);
let mut stop = |progress: Progress| {
let now = stop(progress);
if now {
stopped.set(true);
}
now
};
let halted = || {
Error::Refused(Refusal::Stopped {
phase: crate::Phase::Search,
})
};
let found = self.node(node).ok_or_else(|| no_node(node))?;
let Body::Derived { recipe, record } = &found.body else {
return Err(Error::NotApplicable {
operation: "run".into(),
reason: format!("node {node} is no output of a recipe that runs again"),
});
};
let key = self.key_of(recipe).map_err(|input| Error::NotApplicable {
operation: recipe.operation.name.into(),
reason: format!("input {input} has no value yet"),
})?;
let inputs: Vec<String> = key
.inputs
.iter()
.map(|&v| self.text(v).to_owned())
.collect();
let texts: Vec<&str> = inputs.iter().map(String::as_str).collect();
let settings = settings_of(&recipe.settings)?;
let current = record
.and_then(|record| self.record(record))
.filter(|record| record.key == key && !record.foreign);
let output = match current {
Some(record) => match (&record.end, record.output) {
(End::Refused(error), _) => Err(error.to_string()),
(end, Some(output)) => Ok(Output {
value: self.text(output).to_owned(),
limit: match end {
End::Limit(limit) => {
Some((limit.reason.to_owned(), limit.setting.map(str::to_owned)))
}
_ => None,
},
}),
(_, None) => Err(String::new()),
},
None => {
match protocol::run(
recipe.operation.name,
&texts,
&recipe.parameters,
&settings,
&mut stop,
) {
Ok(_) if stopped.get() => return Err(halted()),
Ok(produced) => Ok(output_of(produced)),
Err(error) if error.kind() == ErrorKind::Stopped => return Err(error),
Err(error) => Err(serde_json::to_string(&error).map_err(json_error)?),
}
}
};
let check = match (&output, what) {
(Ok(output), What::Check) => {
let (suite, operation) = protocol::operation(recipe.operation.name)?;
let call = protocol::Call::new(operation, &texts, &recipe.parameters, &settings);
let stop = std::cell::RefCell::new(&mut stop);
let mut ask = |name: &str, inputs: &[&str], parameters: &str| {
self.asked(name, inputs, parameters, &settings).map_or_else(
|| {
protocol::run(name, inputs, parameters, &settings, |progress| {
(stop.borrow_mut())(progress)
})
.map(|produced| produced.value)
},
Ok,
)
};
let check = suite.check(&call, &output.value, &mut ask, &mut |progress| {
(stop.borrow_mut())(progress)
})?;
Some(check)
}
_ => None,
};
if stopped.get() {
return Err(halted());
}
Ok(Computed {
node: node.0,
operation: recipe.operation.name.to_owned(),
parameters: recipe.parameters.to_string(),
settings: recipe.settings.to_string(),
inputs,
output,
check,
})
}
fn asked(
&self,
name: &str,
inputs: &[&str],
parameters: &str,
settings: &Settings,
) -> Option<String> {
let (_, operation) = protocol::operation(name).ok()?;
let mut values = Vec::with_capacity(inputs.len());
for (text, kinds) in inputs.iter().zip(operation.from) {
let value = kinds
.iter()
.find_map(|kind| self.interned.get(&(*kind, Box::from(*text))))?;
values.push(*value);
}
let key = Key {
operation: operation.name,
parameters: canonical(parameters).ok()?,
settings: project(settings, operation.reads).ok()?,
inputs: values,
};
let record = self
.record(*self.index.get(&key)?)
.filter(|record| record.trusted && !record.foreign)?;
record.output.map(|output| self.text(output).to_owned())
}
pub fn accept(&mut self, computed: Computed, limits: &Limits) -> Result<bool, Error> {
let node = NodeId(computed.node);
let Some(found) = self.recorded(computed, limits)? else {
return Ok(false);
};
if let Ok(at) = self.nodes.binary_search_by_key(&node, |n| n.id)
&& let Body::Derived { record, .. } = &mut self.nodes[at].body
{
*record = Some(found);
}
self.settle();
Ok(true)
}
fn recorded(&mut self, computed: Computed, limits: &Limits) -> Result<Option<RecordId>, Error> {
let node = NodeId(computed.node);
let Some(Body::Derived { recipe, .. }) = self.node(node).map(|n| &n.body) else {
return Ok(None);
};
let recipe = recipe.clone();
let Ok(key) = self.key_of(&recipe) else {
return Ok(None);
};
let same = computed.operation == recipe.operation.name
&& *computed.parameters == *recipe.parameters
&& *computed.settings == *recipe.settings
&& computed.inputs.len() == key.inputs.len()
&& computed
.inputs
.iter()
.zip(&key.inputs)
.all(|(text, &value)| text == self.text(value));
if !same {
return Ok(None);
}
let (end, output) = match computed.output {
Ok(output) => {
let (_, kind) = protocol::kind(recipe.operation.to)?;
protocol::read(kind.name, &output.value, limits)?;
let value = self.intern(kind, &output.value, limits)?;
let end = match output.limit {
Some((reason, setting)) => End::Limit(limit_named(&reason, setting.as_deref())),
None => End::Done,
};
(end, Some(value))
}
Err(error) => (End::Refused(error.into()), None),
};
let fresh = Record {
key: key.clone(),
end,
output,
check: None,
foreign: false,
trusted: true,
made: self.made,
};
let found = match self.index.get(&key) {
Some(&found) if self.record(found).is_some_and(|r| r.foreign) => {
self.records[found.0 as usize] = Some(fresh);
found
}
Some(&found) if self.record(found).is_some() => found,
_ => self.insert(fresh, limits)?,
};
if let Some(check) = computed.check
&& let Some(Some(record)) = self.records.get_mut(found.0 as usize)
{
record.check = Some(check);
}
self.made += 1;
Ok(Some(found))
}
fn insert(&mut self, record: Record, limits: &Limits) -> Result<RecordId, Error> {
if let Some(bound) = limits.workspace.records {
let most = usize::try_from(bound).unwrap_or(usize::MAX);
let mut held = self.records.iter().flatten().count();
if held >= most {
let pinned = self.pinned();
let mut free: Vec<(u64, usize)> = self
.records
.iter()
.enumerate()
.filter_map(|(at, record)| record.as_ref().map(|r| (r.made, at)))
.filter(|&(_, at)| {
!pinned.contains(&RecordId(u32::try_from(at).unwrap_or(u32::MAX)))
})
.collect();
free.sort_unstable();
for (_, at) in free {
if held < most {
break;
}
if let Some(gone) = self.records[at].take() {
self.index.remove(&gone.key);
}
held -= 1;
}
if held >= most {
return Err(refused(Held::Records, held + 1, bound));
}
}
}
let id = RecordId(
u32::try_from(self.records.len())
.map_err(|_| refused(Held::Records, self.records.len(), u64::from(u32::MAX)))?,
);
self.index.insert(record.key.clone(), id);
self.records.push(Some(record));
Ok(id)
}
fn pinned(&self) -> std::collections::BTreeSet<RecordId> {
let mut pinned: std::collections::BTreeSet<RecordId> =
self.pinned_now().into_iter().collect();
for entry in &self.log {
pinned.extend(entry.pins.iter().copied());
for swap in &entry.swaps {
for node in [&swap.before, &swap.after].into_iter().flatten() {
if let Body::Derived {
record: Some(record),
..
} = node.body
{
pinned.insert(record);
}
}
}
}
pinned
}
pub fn run(
&mut self,
targets: &[NodeId],
what: What,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Vec<Ran>, Error> {
self.collect(limits);
let mut ran = Vec::new();
for node in self.plan(targets) {
if self.state(node) == State::Current {
continue;
}
let wants = if targets.contains(&node) {
what
} else {
What::Output
};
let computed = self.compute(node, wants, &mut stop)?;
self.accept(computed, limits)?;
ran.push(Ran {
node,
state: self.state(node),
});
}
if what == What::Check {
for &node in targets {
let lacks = self.node(node).is_some_and(|n| match &n.body {
Body::Derived {
record: Some(record),
..
} => self.record(*record).is_some_and(|r| {
r.output.is_some()
&& r.check.as_ref().is_none_or(|check| {
matches!(
check.status,
Status::Recorded | Status::Failed | Status::Open
)
})
}),
_ => false,
});
if lacks && self.state(node) == State::Current {
let computed = self.compute(node, What::Check, &mut stop)?;
self.accept(computed, limits)?;
ran.push(Ran {
node,
state: self.state(node),
});
}
}
}
Ok(ran)
}
#[must_use]
pub fn pack(&self, nodes: &[NodeId]) -> Self {
let mut kept: Vec<NodeId> = nodes.to_vec();
let mut at = 0;
while at < kept.len() {
if let Some(recipe) = self.node(kept[at]).and_then(Node::recipe) {
for &input in &recipe.from {
if !kept.contains(&input) {
kept.push(input);
}
}
}
at += 1;
}
let mut packed = Self {
values: self.values.clone(),
interned: self.interned.clone(),
nodes: self
.nodes
.iter()
.filter(|node| kept.contains(&node.id))
.cloned()
.collect(),
next: self.next,
..Self::default()
};
for node in &mut packed.nodes {
if let Body::Derived { record, .. } = &mut node.body {
*record = None;
}
}
packed
.collect(&Limits::default().with_workspace(crate::limits::WorkspaceLimits::UNBOUNDED));
packed
}
pub fn rebound(&mut self, limits: &Limits) -> Vec<NodeId> {
let Ok(bounds) = serde_json::to_value(limits) else {
return Vec::new();
};
let mut changed = Vec::new();
for node in &mut self.nodes {
if rebind(node, &bounds) {
changed.push(node.id);
}
}
for entry in &mut self.log {
for swap in &mut entry.swaps {
for node in swap.before.iter_mut().chain(swap.after.iter_mut()) {
rebind(node, &bounds);
}
}
}
self.settle();
changed
}
fn collect(&mut self, limits: &Limits) {
let over = past(self.bytes(), limits.workspace.bytes).is_some();
let pinned = self.pinned();
if over {
for (at, record) in self.records.iter_mut().enumerate() {
if !pinned.contains(&RecordId(u32::try_from(at).unwrap_or(u32::MAX)))
&& let Some(gone) = record.take()
{
self.index.remove(&gone.key);
}
}
}
let mut reached = vec![false; self.values.len()];
let mark = |node: &Node, reached: &mut Vec<bool>| match &node.body {
Body::Given(value) | Body::Copy { value, .. } => reached[value.0 as usize] = true,
Body::Work { value, started, .. } => {
reached[value.0 as usize] = true;
for value in started {
reached[value.0 as usize] = true;
}
}
Body::Derived { .. } => {}
};
for node in &self.nodes {
mark(node, &mut reached);
}
for entry in &self.log {
for swap in &entry.swaps {
for node in [&swap.before, &swap.after].into_iter().flatten() {
mark(node, &mut reached);
}
}
}
for record in self.records.iter().flatten() {
for value in record.key.inputs.iter().chain(&record.output) {
reached[value.0 as usize] = true;
}
}
if reached.iter().all(|&r| r) && !over {
return;
}
let mut renumbered = vec![ValueId(u32::MAX); self.values.len()];
let mut values = Vec::new();
for (at, value) in std::mem::take(&mut self.values).into_iter().enumerate() {
if reached[at] {
renumbered[at] = ValueId(u32::try_from(values.len()).unwrap_or(u32::MAX));
values.push(value);
}
}
self.values = values;
self.interned = self
.values
.iter()
.enumerate()
.map(|(at, value)| {
(
(value.kind.name, value.text.clone()),
ValueId(u32::try_from(at).unwrap_or(u32::MAX)),
)
})
.collect();
let map = |value: &mut ValueId| *value = renumbered[value.0 as usize];
let remap = |node: &mut Node| match &mut node.body {
Body::Given(value) | Body::Copy { value, .. } => map(value),
Body::Work { value, started, .. } => {
map(value);
started.iter_mut().for_each(map);
}
Body::Derived { .. } => {}
};
self.nodes.iter_mut().for_each(remap);
for entry in &mut self.log {
for swap in &mut entry.swaps {
swap.before
.iter_mut()
.chain(swap.after.iter_mut())
.for_each(remap);
}
}
self.index.clear();
for (at, record) in self.records.iter_mut().enumerate() {
if let Some(record) = record {
record.key.inputs.iter_mut().for_each(map);
record.output.iter_mut().for_each(map);
self.index.insert(
record.key.clone(),
RecordId(u32::try_from(at).unwrap_or(u32::MAX)),
);
}
}
}
}
fn output_of(produced: Produced) -> Output {
Output {
value: produced.value,
limit: produced
.limit
.map(|limit| (limit.reason.to_owned(), limit.setting.map(str::to_owned))),
}
}
fn limit_named(reason: &str, setting: Option<&str>) -> Limit {
let known = crate::linear::search::Reason::NAMES
.iter()
.chain(crate::Error::CODES)
.find(|&&name| name == reason)
.copied()
.unwrap_or("unknown");
let setting = setting.and_then(|setting| {
[
"limits.memory_bytes",
"limits.occurrences",
"limits.terms",
"limits.derivation_bytes",
"limits.work",
"limits.table_atoms",
"limits.recursion_depth",
"search.copies",
"search.witness_depth",
"search.instances",
]
.into_iter()
.find(|&key| key == setting)
});
Limit {
reason: known,
setting,
}
}
fn no_node(node: NodeId) -> Error {
Error::IndexOutOfBounds {
space: crate::limits::Space::Node,
index: node.0 as usize,
len: 0,
}
}
#[derive(Debug)]
pub struct Edit<'a> {
workspace: &'a mut Workspace,
limits: &'a Limits,
swaps: Vec<Swap>,
}
impl Edit<'_> {
fn put(&mut self, id: NodeId, node: Option<Node>) {
let after = node.clone();
let before = self.workspace.put(id, node);
self.swaps.push(Swap { id, before, after });
}
fn number(&mut self) -> Result<NodeId, Error> {
let alive = self.workspace.nodes.len() + 1;
if let Some(limit) = past(alive, self.limits.workspace.nodes) {
return Err(refused(Held::Nodes, alive, limit));
}
let id = NodeId(self.workspace.next);
self.workspace.next = self
.workspace
.next
.checked_add(1)
.ok_or_else(|| refused(Held::Nodes, usize::MAX, u64::from(u32::MAX)))?;
Ok(id)
}
fn existing(&self, id: NodeId) -> Result<Node, Error> {
self.workspace.node(id).cloned().ok_or_else(|| no_node(id))
}
pub fn add(&mut self, kind: &str, value: &str) -> Result<NodeId, Error> {
let (_, kind) = protocol::kind(kind)?;
protocol::read(kind.name, value, self.limits)?;
let value = self.workspace.intern(kind, value, self.limits)?;
let id = self.number()?;
self.put(
id,
Some(Node {
id,
body: Body::Given(value),
}),
);
Ok(id)
}
pub fn set(&mut self, node: NodeId, value: &str) -> Result<(), Error> {
let mut changed = self.existing(node)?;
if matches!(changed.body, Body::Derived { .. } | Body::Work { .. }) {
return Err(Error::NotGiven { node: node.0 });
}
let kind = self.workspace.kind_of(&changed);
let (_, kind) = protocol::kind(kind)?;
protocol::read(kind.name, value, self.limits)?;
let id = self.workspace.intern(kind, value, self.limits)?;
match &mut changed.body {
Body::Given(value) | Body::Copy { value, .. } => *value = id,
Body::Derived { .. } | Body::Work { .. } => {
return Err(Error::NotGiven { node: node.0 });
}
}
self.put(node, Some(changed));
Ok(())
}
pub fn connect(
&mut self,
operation: &str,
from: &[NodeId],
parameters: &str,
settings: &Settings,
) -> Result<NodeId, Error> {
let (_, operation) = protocol::operation(operation)?;
if from.len() != operation.from.len() {
return Err(Error::NotApplicable {
operation: operation.name.into(),
reason: format!(
"it takes {} inputs, not {}",
operation.from.len(),
from.len()
),
});
}
for (&input, kinds) in from.iter().zip(operation.from) {
let node = self.existing(input)?;
let kind = self.workspace.kind_of(&node);
if !kinds.contains(&kind) {
return Err(Error::NotApplicable {
operation: operation.name.into(),
reason: format!(
"node {input} is {kind}, and it takes {}",
kinds.join(" or ")
),
});
}
}
let recipe = Recipe {
operation,
from: from.to_vec(),
parameters: canonical(parameters)?,
settings: project(settings, operation.reads)?,
};
let body = match operation.class {
Class::Derived => Body::Derived {
recipe,
record: None,
},
Class::Work | Class::Copy => {
self.ready(&recipe.from)?;
let (value, started) = self.made_now(&recipe)?;
if operation.class == Class::Work {
Body::Work {
recipe,
value,
started,
}
} else {
Body::Copy { recipe, value }
}
}
};
let id = self.number()?;
self.put(id, Some(Node { id, body }));
Ok(id)
}
fn made_now(&mut self, recipe: &Recipe) -> Result<(ValueId, Vec<ValueId>), Error> {
let key = self
.workspace
.key_of(recipe)
.map_err(|input| Error::NotApplicable {
operation: recipe.operation.name.into(),
reason: format!("input {input} has no value yet"),
})?;
let texts: Vec<&str> = key.inputs.iter().map(|&v| self.workspace.text(v)).collect();
let settings = settings_of(&recipe.settings)?;
let produced = protocol::run(
recipe.operation.name,
&texts,
&recipe.parameters,
&settings,
|_| false,
)?;
let (_, kind) = protocol::kind(recipe.operation.to)?;
let value = self.workspace.intern(kind, &produced.value, self.limits)?;
Ok((value, key.inputs))
}
pub fn set_parameters(&mut self, node: NodeId, parameters: &str) -> Result<(), Error> {
let parameters = canonical(parameters)?;
self.change_recipe(node, |recipe| recipe.parameters = parameters)
}
pub fn set_settings(&mut self, node: NodeId, settings: &Settings) -> Result<(), Error> {
let reads = self
.existing(node)?
.recipe()
.map_or(&[][..], |recipe| recipe.operation.reads);
let settings = project(settings, reads)?;
self.change_recipe(node, |recipe| recipe.settings = settings)
}
fn change_recipe(
&mut self,
node: NodeId,
change: impl FnOnce(&mut Recipe),
) -> Result<(), Error> {
let mut changed = self.existing(node)?;
match &mut changed.body {
Body::Given(_) => {
return Err(Error::NotApplicable {
operation: "recipe".into(),
reason: format!("node {node} has no recipe"),
});
}
Body::Derived { recipe, .. }
| Body::Work { recipe, .. }
| Body::Copy { recipe, .. } => {
change(recipe);
}
}
self.put(node, Some(changed));
Ok(())
}
pub fn restart(&mut self, node: NodeId) -> Result<(), Error> {
let mut changed = self.existing(node)?;
let Body::Work {
recipe,
value,
started,
} = &mut changed.body
else {
return Err(Error::NotApplicable {
operation: "restart".into(),
reason: format!("node {node} holds no proof in progress"),
});
};
let from = recipe.from.clone();
self.ready(&from)?;
let (made, inputs) = self.made_now(recipe)?;
*value = made;
*started = inputs;
self.put(node, Some(changed));
Ok(())
}
fn ready(&mut self, inputs: &[NodeId]) -> Result<(), Error> {
for id in self.workspace.plan(inputs) {
let Some(node) = self.workspace.node(id).cloned() else {
continue;
};
let Body::Derived { recipe, .. } = &node.body else {
continue;
};
if recipe.operation.cost != Cost::Instant || self.workspace.key_of(recipe).is_err() {
continue;
}
let computed = self.workspace.compute(id, What::Output, |_| false)?;
if let Some(found) = self.workspace.recorded(computed, self.limits)? {
let mut shown = node.clone();
if let Body::Derived { record, .. } = &mut shown.body {
*record = Some(found);
}
self.put(id, Some(shown));
}
}
Ok(())
}
pub fn work(&mut self, node: NodeId, session: &str) -> Result<(), Error> {
let mut changed = self.existing(node)?;
let Body::Work { recipe, value, .. } = &mut changed.body else {
return Err(Error::NotApplicable {
operation: "work".into(),
reason: format!("node {node} holds no proof in progress"),
});
};
let (_, kind) = protocol::kind(recipe.operation.to)?;
protocol::read(kind.name, session, self.limits)?;
*value = self.workspace.intern(kind, session, self.limits)?;
self.put(node, Some(changed));
Ok(())
}
pub fn detach(&mut self, node: NodeId) -> Result<(), Error> {
let found = self.existing(node)?;
let value = self
.workspace
.shown(&found)
.ok_or_else(|| Error::NotApplicable {
operation: "detach".into(),
reason: format!("node {node} shows no value yet"),
})?;
self.put(
node,
Some(Node {
id: node,
body: Body::Given(value),
}),
);
Ok(())
}
pub fn remove(&mut self, node: NodeId) -> Result<Vec<NodeId>, Error> {
self.existing(node)?;
let mut gone = vec![node];
for found in &self.workspace.nodes {
if found
.recipe()
.is_some_and(|recipe| recipe.from.iter().any(|input| gone.contains(input)))
{
gone.push(found.id);
}
}
for &id in gone.iter().rev() {
self.put(id, None);
}
Ok(gone)
}
}