A spreadsheet, II: a formula is code as a resource

Part I stored what a person typed and passed it through as the cell’s value. That is enough for 42 and for Rent. It is not enough for =A1*2, which is not a value but a program: it has to be parsed, checked and run, and what it produces depends on other cells.

The usual way to handle that is to parse the formula when it is typed and keep the parse tree in the cell, beside the text. This part does something else. The compiled form of a formula is a resource of its own, with a name, and compiling is a transreption: the kernel finds the compiler by what it converts, runs it, and caches what it produces like any other answer. NetKernel treated code this way (its Java and Groovy were compiled by transreptors, and the compiled classes were cached representations), and the reason it matters is the same here: when a formula changes, exactly that formula is compiled again, and the kernel works out which one without being told.

The formula language

The sheet’s formulas are small on purpose: numbers, cells, + - * /, parentheses, a minus sign in front of anything, and SUM over any mix of cells, numbers and ranges (A1:B3). That is enough to show a formula reading other cells, a range reading a rectangle of them, and every kind of error a formula can make. (Later parts add three functions, NOW() and TODAY() in Part IV and FEED(name) in Part V; the listings below already show them.)

A formula compiles to an expression:

/// A compiled formula.
#[derive(Clone, Debug, PartialEq)]
pub enum Expr {
    /// A number, `2.5`.
    Number(f64),
    /// The value of a cell, `A1`.
    Cell(CellRef),
    /// Every cell in a rectangle, top-left to bottom-right, `(range A1 B2)`. Only ever an
    /// argument of `sum`.
    Range(CellRef, CellRef),
    /// Minus one thing, `(- A1)`.
    Negate(Box<Expr>),
    /// Two things and an operator, `(* B1 2)`.
    Binary(Op, Box<Expr>, Box<Expr>),
    /// The sum of its arguments, `(sum (range A1 A3) 10)`.
    Sum(Vec<Expr>),
    /// The current instant, `(now)`: the date and the time, read from the time chapter's
    /// `instant`.
    Now,
    /// Today's date, `(today)`.
    Today,
    /// The latest value written to a feed, `(feed acme)`: data that something other than the
    /// sheet writes.
    Feed(String),
    /// A formula that does not compile, and why: `(syntax-error "…")`. Its value is
    /// `#SYNTAX`. The compiler answers with this rather than refusing, so a formula with a
    /// mistake in it is still a representation the kernel can cache.
    SyntaxError(String),
}

/// An arithmetic operator.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Op {
    /// `+`
    Add,
    /// `-`
    Subtract,
    /// `*`
    Multiply,
    /// `/`
    Divide,
}

and the expression is written as an s-expression, in the one spelling this crate reads back:

/// The expression as an s-expression, in the one spelling the reader takes back.
///
/// ```
/// use spreadsheet::formula::compile;
/// assert_eq!(compile("=A1 + b2*2").to_string(), "(+ A1 (* B2 2))");
/// assert_eq!(compile("=SUM(A3:A1, 10)").to_string(), "(sum (range A1 A3) 10)");
/// assert_eq!(compile("=now()").to_string(), "(now)");
/// assert_eq!(compile("=FEED(Acme) * B1").to_string(), "(* (feed acme) B1)");
/// ```
impl fmt::Display for Expr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Expr::Number(n) => f.write_str(&number_text(*n)),
            Expr::Cell(r) => write!(f, "{r}"),
            Expr::Range(a, b) => write!(f, "(range {a} {b})"),
            Expr::Negate(inner) => write!(f, "(- {inner})"),
            Expr::Binary(op, left, right) => write!(f, "({} {left} {right})", op.symbol()),
            Expr::Sum(args) => {
                f.write_str("(sum")?;
                for arg in args {
                    write!(f, " {arg}")?;
                }
                f.write_str(")")
            }
            Expr::Now => f.write_str("(now)"),
            Expr::Today => f.write_str("(today)"),
            Expr::Feed(name) => write!(f, "(feed {name})"),
            Expr::SyntaxError(why) => {
                let quoted = why.replace('\\', "\\\\").replace('"', "\\\"");
                write!(f, "(syntax-error \"{quoted}\")")
            }
        }
    }
}

S-expressions are the ecosystem’s way of writing code down as data (ikigai-sexpr compiles them to SPARQL), and they suit a compiled formula because they make the structure visible: the precedence of * over +, which the text only implies, is the nesting of the lists. The sheet carries its own small reader rather than ikigai-sexpr’s, because a formula needs decimals and that datum has only integers.

The compiler itself is a short recursive-descent parser, and its one entry point never fails:

/// Compile a formula, `=A1*2`, into an expression.
///
/// This never fails. A formula that does not parse compiles to [`Expr::SyntaxError`],
/// saying what was expected where, so a mistake is a value the sheet shows (`#SYNTAX`)
/// rather than a request that failed. The compiler accepts a formula however it is
/// spelled (`=a1 + 2`, `=SUM(a3:a1)`) and writes the one spelling back (`(+ A1 2)`,
/// `(sum (range A1 A3))`).
pub fn compile(formula: &str) -> Expr {
    let mut parser = Parser {
        text: formula.as_bytes(),
        at: 0,
        depth: 0,
    };
    match parser.formula() {
        Ok(expr) => expr,
        Err(why) => Expr::SyntaxError(why),
    }
}

The section on errors says why it does not.

The compiler is a transreptor

Wrapped as an endpoint, the compiler takes formula text as content and answers the s-expression. What makes it a transreptor is its description:

/// `sheet-compile`: a transreptor from formula text to its compiled form, an s-expression.
///
/// A pure function of `content`, so `.cacheable()`: the kernel keeps one entry per formula
/// text, and a formula typed into two cells is compiled once. It never refuses a formula:
/// one that does not parse compiles to `(syntax-error "…")`, and its value is `#SYNTAX`.
///
/// The description is what makes it the compiler. `.transreptor(from, to)` is what the
/// kernel selects on, so `formula:{ref}` finds it by what it converts, never by its name.
/// And `.lossy()` is true: compiling forgets how the formula was spelled (`=a1 +2` and
/// `=A1+2` compile alike), so the formula cannot be recovered from what comes out.
pub fn compile() -> FnEndpoint {
    FnEndpoint::new("sheet-compile", |inv: &Invocation<'_>| {
        let compiled = formula::compile(inv.inline_str("content")?);
        Ok(
            Representation::new(ReprType::new(SEXPR_TYPE), compiled.to_string().into_bytes())
                .cacheable(),
        )
    })
    .with_description(
        Description::new("sheet-compile")
            .title("Compile a formula")
            .summary("Compiles a formula (=A1*2) to an s-expression ((* A1 2)).")
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(
                ArgSpec::new("content")
                    .summary("the formula, starting with =")
                    .class(XSD_STRING),
            )
            .input(
                ArgSpec::new("as")
                    .summary("the target type; only text/x-sexpr")
                    .class(XSD_STRING)
                    .optional(),
            )
            .output(SEXPR_TYPE)
            .transreptor([FORMULA_TYPE], [SEXPR_TYPE])
            .lossy(),
    )
}

.transreptor([FORMULA_TYPE], [SEXPR_TYPE]) says it converts text/x-formula into text/x-sexpr, and that declaration is what the kernel selects on, as in Transreption. describe shows it, as the description’s Turtle; the lines to look for are ik:transreptsFrom, ik:transreptsTo and ik:lossless:

@prefix ik: <https://ikigai-rs.dev/ns#> .
 
<urn:ikigai:endpoint:sheet-compile> a ik:Endpoint, ik:Transreptor ;
    ik:id "sheet-compile" ;
    ik:title "Compile a formula" ;
    ik:summary "Compiles a formula (=A1*2) to an s-expression ((* A1 2))." ;
    ik:verb "Source", "Meta" ;
    ik:output "text/x-sexpr" ;
    ik:transreptsFrom "text/x-formula" ;
    ik:transreptsTo "text/x-sexpr" ;
    ik:lossless false ;
    ik:input <urn:ikigai:endpoint:sheet-compile:input:content> ;
    ik:input <urn:ikigai:endpoint:sheet-compile:input:as> ;
    ik:action <urn:ikigai:contract:sheet-compile:source:b3:…> .
 
<urn:ikigai:endpoint:sheet-compile:input:content> ik:inputName "content" ;
    ik:source "argument" ;
    ik:required true ;
    ik:summary "the formula, starting with =" ;
    ik:class <http://www.w3.org/2001/XMLSchema#string> .
 
<urn:ikigai:endpoint:sheet-compile:input:as> ik:inputName "as" ;
    ik:source "argument" ;
    ik:required false ;
    ik:summary "the target type; only text/x-sexpr" ;
    ik:class <http://www.w3.org/2001/XMLSchema#string> .
 
<urn:ikigai:contract:sheet-compile:source:b3:…:input:content> ik:inputName "content" ;
    ik:source "argument" ;
    ik:required true ;
    ik:summary "the formula, starting with =" ;
    ik:class <http://www.w3.org/2001/XMLSchema#string> .
 
<urn:ikigai:contract:sheet-compile:source:b3:…:input:as> ik:inputName "as" ;
    ik:source "argument" ;
    ik:required false ;
    ik:summary "the target type; only text/x-sexpr" ;
    ik:class <http://www.w3.org/2001/XMLSchema#string> .
 
<urn:ikigai:contract:sheet-compile:source:b3:…> a ik:Action ;
    ik:verb "Source" ;
    ik:output "text/x-sexpr" ;
    ik:input <urn:ikigai:contract:sheet-compile:source:b3:…:input:content> ;
    ik:input <urn:ikigai:contract:sheet-compile:source:b3:…:input:as> .
[computed]

.lossy() is the honest half. A transreption proper changes form without changing what is represented, so the original could be recovered from what comes out. Compiling cannot promise that: =a1 +2 and =A1+2 compile to the same (+ A1 2), and nothing in the output says which was typed. So the compiler declares itself a projection, and the kernel will not route through it unless the caller consents.

The compiled formula is a resource

formula:{ref} is the cell’s formula, compiled. It reads the cell’s input, asks the kernel for a plan from the input’s type to text/x-sexpr, and runs the plan:

/// `sheet-formula`: the cell's formula, compiled.
///
/// It reads the input, and asks the kernel for a plan from what the input is
/// (`text/x-formula`) to what this answers (`text/x-sexpr`), then runs the plan through the
/// kernel. The compiler is whatever transreptor the plan names; this code does not know it.
/// The consent to a lossy step is this endpoint's to give, because it is the one that knows
/// losing the spelling is what compiling means.
///
/// Cacheable, with no thread named: it read the input, so the kernel hangs it from the
/// input's thread, and typing into that cell, and only that cell, recompiles it. A cell
/// holding no formula is `NotFound`.
pub fn formula() -> AsyncFnEndpoint {
    AsyncFnEndpoint::new(
        "sheet-formula",
        |inv: &Invocation<'_>| -> InvokeFuture<'_> {
            Box::pin(async move {
                let at = cell_binding(inv, "ref")?;
                let typed = inv.source(&iri(&input_name(at))?).await?;
                if typed.repr_type.media_type != FORMULA_TYPE {
                    return Err(Error::NotFound(format!("{at} holds no formula")));
                }
                let plan = inv
                    .select_transreptor_with(
                        FORMULA_TYPE,
                        SEXPR_TYPE,
                        &TransreptionPolicy::allow_lossy(),
                    )
                    .ok_or_else(|| {
                        Error::Endpoint(format!("nothing converts {FORMULA_TYPE} to {SEXPR_TYPE}"))
                    })?;
                let mut compiled = typed;
                for step in plan {
                    let request = Request::new(Verb::Source, iri(&step.endpoint)?)
                        .with_arg("content", ArgRef::Inline(compiled.bytes))
                        .with_arg("as", ArgRef::Inline(step.to.into_bytes()));
                    compiled = inv.issue(request).await?;
                }
                Ok(Representation::new(compiled.repr_type, compiled.bytes).cacheable())
            })
        },
    )
    .with_description(
        Description::new("sheet-formula")
            .title("Compiled formula")
            .summary("The cell's formula, compiled to an s-expression; NotFound if it holds none.")
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(ref_input("the cell, A1 to D6"))
            .output(SEXPR_TYPE),
    )
}

This is where Part I’s media type earns its place. The input says it is text/x-formula, the compiler says it converts text/x-formula, and the kernel joins the two. formula:{ref} never names the compiler, and a different one bound in its place would be found the same way. The consent to the lossy step is given here, by the one endpoint that knows losing the spelling is what compiling means.

Type a formula, and ask for its compiled form twice:

5
[uncacheable]
=a1 * 2
[uncacheable]
(* A1 2)
[computed]
(* A1 2)
[cached]

The second time, nothing was compiled. Now give the sheet a second formula, and read both values:

=A2+1
[uncacheable]
10
[cached]
11
[computed]

A2 was cached before this cell asked for it. The grid at the bottom of the page draws itself again after every cell runs, so it read A2’s value, and compiled A2’s formula, as soon as the last cell had typed it. A3 is new, so it was computed here.

Editing a formula compiles exactly that formula

Both formulas are compiled and cached now (the grid below read every value after that cell ran, and a value reads its formula). Three edits, three different things to change:

7
[uncacheable]
cached
=A1*3
[uncacheable]
not cached
cached

Changing A1, a cell the formula names, leaves the formula compiled: =A1*2 is the same program whatever A1 holds, and the compiled form never read A1. Changing A2’s own input cuts A2’s compiled form, and only that one: A3’s formula names A2 too, and is still cached, because =A2+1 did not change either.

Nothing here decides any of that. The compiled form read the input, and only the input, so it hangs from the input’s thread and nothing else. Which is the whole point of making the compiled form a resource: “recompile when the source changes” is not code anybody wrote, it is what caching a transreption means.

Code as data: which cells a formula reads

A compiled formula is data, and the next question is one a spreadsheet asks constantly: which cells does this formula read? The text could be scanned for things that look like cells, but the compiled form already knows, so refs:{ref} reads it:

/// `sheet-refs`: the cells the cell's formula reads, one name per line, each once.
///
/// Read from the compiled form, not the text: the cells it names and the cells of each
/// range, which `range:{from}:{to}` lists. A cell off the sheet is not listed (nothing is
/// read for it; its value is `#REF`). A cell holding no formula reads nothing: the empty list.
pub fn refs() -> AsyncFnEndpoint {
    AsyncFnEndpoint::new("sheet-refs", |inv: &Invocation<'_>| -> InvokeFuture<'_> {
        Box::pin(async move {
            let at = cell_binding(inv, "ref")?;
            let mut names: Vec<String> = Vec::new();
            let typed = typed_into(inv, at).await?;
            if let Some(expr) = compiled(inv, at, typed.as_ref()).await? {
                let (cells, ranges) = expr.names();
                for (from, to) in ranges
                    .into_iter()
                    .filter(|(a, b)| a.on_sheet() && b.on_sheet())
                {
                    for name in lines_of(&text_of(inv, &range_name(from, to)).await?) {
                        names.push(name.to_string());
                    }
                }
                names.extend(cells.into_iter().filter(CellRef::on_sheet).map(cell_name));
            }
            let mut once = Vec::new();
            for name in names {
                if !once.contains(&name) {
                    once.push(name);
                }
            }
            Ok(name_list(&once))
        })
    })
    .with_description(
        Description::new("sheet-refs")
            .title("References")
            .summary("The cells a cell's formula reads, one name per line.")
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(ref_input("the cell, A1 to D6"))
            .output(TEXT_PLAIN_UTF8),
    )
}

A range is listed cell by cell, and the listing is a resource too, range:{from}:{to}, a pure function of its own name:

/// `sheet-range`: the cells from `from` (top-left) to `to` (bottom-right), row by row, one
/// name per line. A pure function of its name, so it is computed once.
///
/// One spelling per rectangle: `A1:B2`, never `B2:A1` or `A2:B1`, so a range has one name
/// and one cache entry. The compiler writes that spelling whatever order a formula used.
pub fn range() -> FnEndpoint {
    FnEndpoint::new("sheet-range", |inv: &Invocation<'_>| {
        let (from, to) = (cell_binding(inv, "from")?, cell_binding(inv, "to")?);
        if from.column > to.column || from.row > to.row {
            let (top_left, bottom_right) = (
                CellRef::new(from.column.min(to.column), from.row.min(to.row)),
                CellRef::new(from.column.max(to.column), from.row.max(to.row)),
            );
            return Err(Error::InvalidArgument {
                name: "from, to".to_string(),
                detail: format!("{from}:{to} is spelled top-left first: {top_left}:{bottom_right}"),
            });
        }
        let names: Vec<String> = (from.row..=to.row)
            .flat_map(|row| (from.column..=to.column).map(move |c| cell_name(CellRef::new(c, row))))
            .collect();
        Ok(name_list(&names))
    })
    .with_description(
        Description::new("sheet-range")
            .title("Range")
            .summary("The cells in a rectangle, row by row, one name per line.")
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(
                ArgSpec::new("from")
                    .summary("the top-left cell")
                    .class(XSD_STRING)
                    .binding(),
            )
            .input(
                ArgSpec::new("to")
                    .summary("the bottom-right cell")
                    .class(XSD_STRING)
                    .binding(),
            )
            .output(TEXT_PLAIN_UTF8),
    )
}

=SUM(A1:A3) * 2
[uncacheable]
(* (sum (range A1 A3)) 2)
[computed]
urn:iki:tutorial:sheet:cell:A1
urn:iki:tutorial:sheet:cell:A2
urn:iki:tutorial:sheet:cell:A3
[computed]
error: invalid argument `from, to`: A3:A1 is spelled top-left first: A1:A3

A range has one spelling, top-left first, for the reason a cell does: one name, one cache entry, one thread. The compiler writes that spelling whatever order the formula used, so SUM(A3:A1) and SUM(A1:A3) read the same range.

Evaluating: a value reads the values it names

Part I showed the value endpoint and skipped its formula branch. Here it is again, and now the branch is the interesting part:

/// `sheet-cell`: the cell's value.
///
/// A cell nobody has typed into is empty. A literal (a number, some text) passes through as
/// typed. A formula is evaluated: first the cell's precedents are read, and a cell among its
/// own is `#CYCLE`; otherwise the compiled form is read back and evaluated over the values
/// of the cells it names.
///
/// Every answer is `.cacheable()` and names no thread. It hangs from what it read: the
/// input, the compiled formula, the precedents, and the values of the cells the formula
/// named. So typing into a cell cuts that cell's value, and the values that read it, and the
/// values that read those, and nothing else.
pub fn cell() -> AsyncFnEndpoint {
    AsyncFnEndpoint::new("sheet-cell", |inv: &Invocation<'_>| -> InvokeFuture<'_> {
        Box::pin(async move {
            let at = cell_binding(inv, "ref")?;
            let typed = typed_into(inv, at).await?;
            let value = match &typed {
                None => String::new(),
                Some(literal) if literal.repr_type.media_type != FORMULA_TYPE => {
                    String::from_utf8_lossy(&literal.bytes).into_owned()
                }
                Some(_) => {
                    let precedents = text_of(inv, &precedents_name(at)).await?;
                    if lines_of(&precedents).any(|name| cell_of(name) == Some(at)) {
                        CYCLE_ERROR.to_string()
                    } else {
                        let expr = compiled(inv, at, typed.as_ref()).await?.ok_or_else(|| {
                            Error::Endpoint(format!("{at} held a formula and then did not"))
                        })?;
                        eval(inv, &expr).await?.text()
                    }
                }
            };
            Ok(Representation::new(text_plain_utf8(), value.into_bytes()).cacheable())
        })
    })
    .with_description(
        Description::new("sheet-cell")
            .title("Cell")
            .summary(
                "A cell's value: a literal as typed, or its formula evaluated. Errors are \
                 values: #REF, #DIV/0, #CYCLE, #VALUE, #SYNTAX, #N/A.",
            )
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(ref_input("the cell, A1 to D6"))
            .output(TEXT_PLAIN_UTF8),
    )
}

For a formula, the value reads the cell’s precedents (the next section but one), then the compiled formula, reads it back into an expression, and evaluates it:

/// Evaluate `expr`, reading every cell it names through the kernel.
///
/// Each read is a sub-request, so the value being computed depends on exactly the cells
/// this evaluation read, and on nothing else: the kernel records them as it goes. Nothing
/// here writes down a dependency. A sheet error is a [`Value::Error`], and the first one met
/// (left to right) is the answer; a failure of the kernel's own is an `Err` and passes on.
fn eval<'a>(inv: &'a Invocation<'_>, expr: &'a Expr) -> Evaluated<'a> {
    Box::pin(async move {
        let arithmetic = |result: std::result::Result<f64, &'static str>| match result {
            Ok(n) if n.is_finite() => Value::Number(n),
            Ok(_) => Value::Error(VALUE_ERROR),
            Err(e) => Value::Error(e),
        };
        Ok(match expr {
            Expr::Number(n) => Value::Number(*n),
            Expr::Cell(cell) => read_cell(inv, *cell).await?,
            Expr::Negate(inner) => arithmetic(eval(inv, inner).await?.number().map(|n| -n)),
            Expr::Binary(op, left, right) => {
                let left = match eval(inv, left).await?.number() {
                    Ok(n) => n,
                    Err(e) => return Ok(Value::Error(e)),
                };
                let right = match eval(inv, right).await?.number() {
                    Ok(n) => n,
                    Err(e) => return Ok(Value::Error(e)),
                };
                arithmetic(match op {
                    formula::Op::Add => Ok(left + right),
                    formula::Op::Subtract => Ok(left - right),
                    formula::Op::Multiply => Ok(left * right),
                    formula::Op::Divide if right == 0.0 => Err(DIV_ERROR),
                    formula::Op::Divide => Ok(left / right),
                })
            }
            Expr::Sum(args) => {
                let mut total = 0.0;
                for arg in args {
                    match sum_of(inv, arg).await? {
                        Ok(n) => total += n,
                        Err(e) => return Ok(Value::Error(e)),
                    }
                }
                arithmetic(Ok(total))
            }
            Expr::Now => read_time(inv, TIME_INSTANT).await?,
            Expr::Today => read_time(inv, TIME_TODAY).await?,
            Expr::Feed(name) => read_feed(inv, name).await?,
            // A range means something only as an argument of SUM.
            Expr::Range(..) => Value::Error(VALUE_ERROR),
            Expr::SyntaxError(_) => Value::Error(SYNTAX_ERROR),
        })
    })
}

/// The value of `cell`, read through the kernel; `#REF` for a cell off the sheet, which is
/// never asked for, since no name answers for it.
async fn read_cell(inv: &Invocation<'_>, cell: CellRef) -> Result<Value> {
    if !cell.on_sheet() {
        return Ok(Value::Error(REF_ERROR));
    }
    Ok(Value::of(&text_of(inv, &cell_name(cell)).await?))
}

/// `NOW()` or `TODAY()`: the text of the time chapter's `instant` or `today`, read through
/// the kernel, so the value that asked inherits its deadline. A kernel with no clock has no
/// time to give, and never will (its clock is fixed when it is built), so that is `#N/A`,
/// and nothing is asked.
async fn read_time(inv: &Invocation<'_>, name: &str) -> Result<Value> {
    if inv.now().is_none() {
        return Ok(Value::Error(NA_ERROR));
    }
    Ok(Value::Text(text_of(inv, name).await?))
}

/// `FEED(name)`: the latest value written to the feed, read through the kernel.
///
/// A feed nothing has written to is `#N/A`. That fallback is safe to cache: the value that
/// caught the `NotFound` hangs from the feed's golden thread, so the first write to the feed
/// cuts it. It catches the ATOM's own `NotFound`, which says exactly what is missing; before
/// core 0.1.82 that was also the only safe choice, since a composite's `NotFound` hung the
/// fallback from a thread nobody cuts.
async fn read_feed(inv: &Invocation<'_>, name: &str) -> Result<Value> {
    match inv.source(&iri(&feed_name(name))?).await {
        Ok(latest) => Ok(Value::of(&String::from_utf8_lossy(&latest.bytes))),
        Err(Error::NotFound(_)) => Ok(Value::Error(NA_ERROR)),
        Err(other) => Err(other),
    }
}

/// What one argument of SUM adds. A range, or a cell named on its own, adds its numbers
/// and skips its empty cells and its text, as spreadsheets do; anything else is arithmetic.
async fn sum_of(
    inv: &Invocation<'_>,
    arg: &Expr,
) -> Result<std::result::Result<f64, &'static str>> {
    let cells = match arg {
        Expr::Range(from, to) if from.on_sheet() && to.on_sheet() => {
            let listed = text_of(inv, &range_name(*from, *to)).await?;
            lines_of(&listed).filter_map(cell_of).collect()
        }
        Expr::Range(..) => return Ok(Err(REF_ERROR)),
        Expr::Cell(cell) => vec![*cell],
        other => return Ok(eval(inv, other).await?.number()),
    };
    let mut total = 0.0;
    for cell in cells {
        match read_cell(inv, cell).await? {
            Value::Number(n) => total += n,
            Value::Error(e) => return Ok(Err(e)),
            Value::Empty | Value::Text(_) => {}
        }
    }
    Ok(Ok(total))
}

Every cell the expression names is read through the kernel, as cell:{ref}. So a value is a composite over other values, the way tic-tac-toe’s line was a composite over cells, and its dependencies are exactly the cells the evaluation read, recorded by the kernel as it read them. An empty cell is 0 in arithmetic; SUM skips text and empty cells, as spreadsheets do.

Errors are values

A formula can go wrong five ways, and each is a value the cell shows, never a failed request or a crashed page:

/// A reference to a cell that is not on the sheet.
pub const REF_ERROR: &str = "#REF";
/// A division by zero.
pub const DIV_ERROR: &str = "#DIV/0";
/// A cell whose value depends on itself.
pub const CYCLE_ERROR: &str = "#CYCLE";
/// Text where a number was needed.
pub const VALUE_ERROR: &str = "#VALUE";
/// A formula that does not compile.
pub const SYNTAX_ERROR: &str = "#SYNTAX";
/// A value that is not available: a feed nothing has written to, or the time on a kernel
/// with no clock.
pub const NA_ERROR: &str = "#N/A";

An error is also passed on: a formula that reads a cell showing #DIV/0 shows #DIV/0.

Rent
[uncacheable]
=A1/0
[uncacheable]
=C1+1
[uncacheable]
=E1+1
[uncacheable]
=B2*2
[uncacheable]
#DIV/0
[computed]
#DIV/0
[computed]
#REF
[computed]
#VALUE
[computed]

E1 is #REF because the sheet has no column E, so no name answers for it. The evaluator knows that without asking, and asks for nothing.

The fifth error is the reason the compiler never fails. A formula with a mistake in it still compiles, to an expression that says what was wrong:

=A1+
[uncacheable]
(syntax-error "expected a number, a cell or (, and the formula ended")
[computed]
#SYNTAX
[computed]
#SYNTAX
[cached]

A compiler that refused =A1+ would be the more obvious design, and it would cost the cache. The kernel never caches an answer built on a refusal of that kind, because it cannot name what would make the refusal go away: it records a failed read as a dependency that has already expired. So every read of a cell with a typo in it would compile the typo again, and every value that read that cell would be computed again with it. Compiled to a value instead, (syntax-error …) is cached, hangs from the input like any other compiled form, and goes away when the input is fixed.

A cycle is named, not chased

A formula can read itself, the long way round: D1 reads D2, and D2 reads D1. Evaluated naively, D1 asks for D2, which asks for D1, which asks for D2, until something stops it. Here something would: the kernel bounds how deep one resolution may go (64 levels, by default), and refuses past it. But that refusal is a kernel error with the whole chain in it, the kind of answer the last section said cannot be cached, and it would arrive as a failed page rather than a cell saying what is wrong.

So a value checks first, with one more resource. precedents:{ref} is every cell a cell’s value depends on, however far back, found by walking refs:{ref}:

/// `sheet-precedents`: every cell the cell's value depends on, however far back, one name
/// per line, nearest first.
///
/// A walk over `refs:{ref}`: the cells this one reads, then the cells those read, and so on,
/// each visited once. It reads formulas and never values, so it ends even when the formulas
/// go round in a circle, and a cell that turns up among its own precedents is in one. That
/// is how a cell's value can say `#CYCLE` instead of chasing itself down to the kernel's
/// depth bound.
pub fn precedents() -> AsyncFnEndpoint {
    AsyncFnEndpoint::new(
        "sheet-precedents",
        |inv: &Invocation<'_>| -> InvokeFuture<'_> {
            Box::pin(async move {
                let at = cell_binding(inv, "ref")?;
                let mut found: Vec<String> = Vec::new();
                let mut queue = VecDeque::from([at]);
                while let Some(next) = queue.pop_front() {
                    for name in lines_of(&text_of(inv, &refs_name(next)).await?) {
                        if found.iter().any(|seen| seen == name) {
                            continue;
                        }
                        found.push(name.to_string());
                        if let Some(cell) = cell_of(name).filter(|cell| *cell != at) {
                            queue.push_back(cell);
                        }
                    }
                }
                Ok(name_list(&found))
            })
        },
    )
    .with_description(
        Description::new("sheet-precedents")
            .title("Precedents")
            .summary("Every cell a cell's value depends on, however far back, one name per line.")
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(ref_input("the cell, A1 to D6"))
            .output(TEXT_PLAIN_UTF8),
    )
}

It reads formulas and never values, and it visits each cell once, so it ends even when the formulas go round in a circle. A cell that turns up among its own precedents is in one, and its value is #CYCLE:

=D2+1
[uncacheable]
=D1*2
[uncacheable]
#CYCLE
[computed]
urn:iki:tutorial:sheet:cell:D2
urn:iki:tutorial:sheet:cell:D1
[cached]

Break the cycle by giving D2 a number, and D1 is computed again from it. Its precedents were built from D2’s old formula, so D2’s input cut them too:

4
[uncacheable]
urn:iki:tutorial:sheet:cell:D2
[computed]
5
[computed]

The sheet

The same sheet as Part I, on this page’s kernel, with everything the cells above typed into it. Try a formula of your own, a range, and a mistake.

What was built

formula:{ref} is glue for the reason the time chapter’s view used to be: a name cannot carry an argument. A view no longer needs one, since compose_over fixes the template when it is bound (Part I’s grid is built that way), but nothing fixes a transreption’s target type. If a name could mean “this resource, transrepted to that type”, the compiled formula would be a rule, formula:{ref} = input:{ref} as text/x-sexpr, and no code at all.

Every one of these is cacheable, and not one names a golden thread or lists a dependency. The next part edits a cell and asks what that cost.