Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

An openspec/ tree as a graph

The previous chapter’s tree is five Markdown files. This chapter makes it a graph in which every requirement, scenario, change and task has a name — an IRI — and asks it questions with SPARQL. It writes no parser to do it.

The lifting is ikigai-markdown, and it works in two stages that are worth keeping apart:

  1. A generic lift that knows Markdown and nothing else: documents, headings with their levels and their enclosing section, list items with their checkbox state, paragraphs, links. Every node is named under the document’s IRI; there are no blank nodes.
  2. A mapping, which is a resource, not code: a small lift profile plus SPARQL CONSTRUCT queries that turn that structure into a domain — here, OpenSpec’s. The lifter has never heard of a requirement. Every word of OpenSpec in this chapter is in the mapping.

ikigai-markdown is on crates.io (its first release was 0.1.0); this book’s workspace takes 0.1.4.

The mapping, by name

A mapping is found by name, urn:markdown:mapping:{name}, as a file under the config home: <config home>/markdown/mappings/openspec/mapping.ttl. The one this book uses is crates/openspec-ledger/config/markdown/mappings/openspec/mapping.ttl; copying that directory into ~/.config/ikigai/markdown/mappings/ installs it for any ikigai host on your machine. The host in this chapter is given config/ beside it as its config home instead, so the book never reads yours:

/// The store, the ledger, and the lift, as one space.
///
/// The lift finds mappings BY NAME under a config home, at
/// `<home>/markdown/mappings/<name>/mapping.ttl`. A host passes its own; this crate's is
/// `config/` beside it, so the book never reads the reader's `~/.config`.
pub fn space(mapping_home: &Path) -> Fallback {
    let store = DurableStore::in_memory().expect("an in-memory store opens");
    let home = Arc::new(MappingHome::new(Some(mapping_home.to_path_buf())));
    Fallback::new(vec![
        Arc::new(ikigai_store::space(store)) as Arc<dyn Space>,
        Arc::new(ikigai_ledger::space()) as Arc<dyn Space>,
        Arc::new(ikigai_markdown::space_with(home)) as Arc<dyn Space>,
    ])
}

/// The host: [`space`] over this crate's config home, a Meta renderer and the story clock.
pub fn kernel() -> Kernel {
    Kernel::with_meta_renderer(
        Arc::new(space(&crate_dir().join("config"))),
        Arc::new(ikigai_vocab::TurtleRenderer),
    )
    .with_clock(Arc::new(ledger_host::StoryClock::default()))
}

The store and the ledger are the first chapter’s; the lift is the third space. The graph will live in the same store as the ledger, which is what the next chapter needs.

A mapping’s constructs are SPARQL, and the lift runs them under a time budget, the same one the store’s own doors use: 5 seconds for a caller, raised by a urn:cap:store:budget:<ms> grant, 120 seconds for root, and a Timeout past it. An evaluation that cannot be stopped is counted, and while too many are still running the lift refuses new ones, so the count is what keeps a runaway mapping from holding the machine’s cores. space_with makes that budget itself. A host that mounts the lift more than once, or wants other numbers, makes ONE EvaluationBudget and passes it to every space_with_budget it mounts, so that every lift shares one count. This host mounts one lift, so the default is already the one. The store keeps its own count for its own doors.

The mapping’s lift profile has one entry. It turns every RFC 2119 keyword in the tree into a match the constructs can see, one per occurrence:

    # --- the lift profile --------------------------------------------------------------------
    # One md:Match per RFC 2119 keyword, wherever it is. SPARQL's REPLACE gives one value per
    # row, so "MUST refuse … and MUST NOT change" would be one keyword to a construct; the
    # profile makes it two rows. Longest alternatives first: the regex takes the first that fits.
    md:citation <urn:markdown:mapping:openspec:citation:keyword> ;

<urn:markdown:mapping:openspec:citation:keyword>
    md:name "keyword" ;
    md:pattern "(?P<v>MUST NOT|SHALL NOT|SHOULD NOT|MUST|SHALL|SHOULD|MAY)" .

A construct could find the first keyword in a paragraph with a regular expression, but not both of “MUST refuse … and MUST NOT change”. The profile is where the one-to-many part of reading text belongs. Then the constructs, six of them. Each runs over one document’s structural graph, and decides what that document is from its path — OpenSpec’s own rule. This is the first: a capability and its requirements, from a current spec.

    # 1. A capability and its requirements, from a current spec.
    md:construct """
PREFIX md: <https://ikigai-rs.dev/ns/md#>
PREFIX os: <http://example.org/openspec#>
CONSTRUCT {
  ?cap a os:Capability ; os:name ?capName ; os:requirement ?req .
  ?req a os:Requirement ; os:name ?reqName ; os:capability ?cap ; os:line ?line .
}
WHERE {
  ?doc a md:Document ; md:path ?path .
  FILTER(REGEX(?path, "(^|/)openspec/specs/[^/]+/spec[.]md$"))
  BIND(REPLACE(?path, "^(.*/)?openspec/specs/([^/]+)/spec[.]md$", "$2") AS ?capName)
  BIND(IRI(CONCAT("urn:openspec:spec:", ?capName)) AS ?cap)
  # OPTIONAL, so a capability with no requirements is still a capability. Its BINDs come AFTER
  # it: a group inside OPTIONAL is evaluated on its own, where ?cap is not bound yet.
  OPTIONAL {
    ?h a md:Heading ; md:document ?doc ; md:level 3 ; md:text ?text ; md:line ?line .
    FILTER(STRSTARTS(?text, "Requirement: "))
  }
  BIND(SUBSTR(?text, 14) AS ?reqName)
  BIND(IRI(CONCAT(STR(?cap), ":requirement:",
       REPLACE(REPLACE(LCASE(?reqName), "[^a-z0-9]+", "-"), "^-+|-+$", ""))) AS ?req)
}
""" ;

md:Heading, md:level, md:text and md:path are the generic lift’s words; os: is OpenSpec’s, made up for this book (http://example.org/openspec#, a namespace reserved for examples). Every IRI is minted from names in the tree — urn:openspec:spec:moves:requirement:players-alternate — so the same bytes always give the same graph, and a requirement named in a delta spec and the same requirement in the current spec are one node. The others: each requirement’s scenarios and their steps; the keywords; a change, and the date it was archived if its folder is under archive/; what a delta adds, modifies or removes; and a change’s tasks:

    # 6. A change's tasks: every checkbox in its tasks.md. A task that ends in "(Requirement
    #    name)" cites that requirement BY NAME; which capability it belongs to is the change's
    #    delta, another document, so resolving the name is a query over the union.
    md:construct """
PREFIX md: <https://ikigai-rs.dev/ns/md#>
PREFIX os: <http://example.org/openspec#>
CONSTRUCT {
  ?change os:task ?task .
  ?task a os:Task ; os:change ?change ; os:number ?number ; os:title ?title ;
        os:done ?done ; os:group ?group ; os:cites ?cites .
}
WHERE {
  ?doc a md:Document ; md:path ?path .
  FILTER(REGEX(?path, "(^|/)openspec/changes/(archive/)?[^/]+/tasks[.]md$"))
  BIND(REPLACE(?path, "^(.*/)?openspec/changes/(archive/[0-9]{4}-[0-9]{2}-[0-9]{2}-)?([^/]+)/tasks[.]md$", "$3") AS ?id)
  BIND(IRI(CONCAT("urn:openspec:change:", ?id)) AS ?change)
  ?item a md:ListItem ; md:document ?doc ; md:checked ?done ; md:text ?text .
  FILTER(REGEX(?text, "^[0-9]+([.][0-9]+)* "))
  BIND(REPLACE(?text, "^([0-9]+([.][0-9]+)*) .*$", "$1") AS ?number)
  BIND(REPLACE(?text, "^[0-9.]+ +", "") AS ?rest)
  BIND(REPLACE(?rest, " *[(][^()]+[)]$", "") AS ?title)
  BIND(IF(REGEX(?rest, "[(][^()]+[)]$"), REPLACE(?rest, "^.*[(]([^()]+)[)]$", "$1"), ?unbound) AS ?cites)
  BIND(IRI(CONCAT(STR(?change), ":task:", ?number)) AS ?task)
  OPTIONAL { ?item md:section ?g . ?g md:text ?group }
}
""" .

A task’s checkbox is the generic lift’s md:checked; its number, title and cited requirement are cut from its text. What a task does not get here is the requirement itself: the name The last move can be undone is in tasks.md, the requirement it names is in the delta spec, and a construct only ever sees one document. That join is a query, below.

Lifting one document

urn:markdown:lift takes the Markdown (content, or a resource IRI as src), the path, and the mapping, and answers N-Quads: the structural graph and the mapped one, together, in a named graph for the document.

#![allow(unused)]
fn main() {
extern crate openspec_ledger;
extern crate ikigai_core;
use ikigai_core::Verb;
use openspec_ledger::{ask, crate_dir, kernel, MAPPING};

let host = kernel();
let tasks = std::fs::read_to_string(
    crate_dir().join("openspec/changes/add-undo/tasks.md")).unwrap();
let quads = ask(&host, Verb::Source, "urn:markdown:lift", &[
    ("content", &tasks),
    ("path", "openspec/changes/add-undo/tasks.md"),
    ("mapping", MAPPING),
]).unwrap();

let graph = "<urn:markdown:doc:openspec/changes/add-undo/tasks.md>";
let task = "<urn:openspec:change:add-undo:task:1.2>";
let os = |p: &str| format!("<http://example.org/openspec#{p}>");
for line in [
    format!(r#"{task} {} "1.2" {graph} ."#, os("number")),
    format!(r#"{task} {} "false"^^<http://www.w3.org/2001/XMLSchema#boolean> {graph} ."#, os("done")),
    format!(r#"{task} {} "The last move can be undone" {graph} ."#, os("cites")),
    format!(r#"{task} {} <urn:openspec:change:add-undo> {graph} ."#, os("change")),
] {
    assert!(quads.lines().any(|l| l == line), "missing: {line}");
}
// The structural half is there too, under the document's own IRI.
assert!(quads.contains("<https://ikigai-rs.dev/ns/md#checked>"));
}

Task 1.2 is unchecked, numbered, part of add-undo, and cites a requirement by name. The lift is cacheable — a function of its arguments and of the mapping it names — so asking again for the same bytes, path and mapping is answered from the kernel’s cache.

The tree, in the store

A tree is many documents, so a host lifts each and loads it into the store, one named graph per document. Archiving a change moves files, so lifting a tree also drops the graphs of documents that are gone:

/// Make the store's spec graphs exactly the lift of `tree`: one graph per document, named by
/// its path, and no graph for a document that is gone (archiving a change MOVES its files, so
/// the old paths must disappear). Returns how many documents were lifted.
pub fn lift_tree(kernel: &Kernel, tree: &[(String, String)]) -> Result<usize> {
    for graph in spec_graphs(kernel)? {
        ask(
            kernel,
            Verb::Sink,
            "urn:iki:store:update",
            &[("content", &format!("DROP SILENT GRAPH <{graph}>"))],
        )?;
    }
    for (path, text) in tree {
        let quads = ask(
            kernel,
            Verb::Source,
            "urn:markdown:lift",
            &[("content", text), ("path", path), ("mapping", MAPPING)],
        )?;
        ask(
            kernel,
            Verb::Sink,
            "urn:iki:store:load",
            &[("content", &quads), ("format", "application/n-quads")],
        )?;
    }
    Ok(tree.len())
}

and asks the union of those graphs, through the store’s narrow read door for a set of graphs:

/// A SPARQL SELECT over the union of every spec graph and the ledger's graph, answered as a
/// tab-separated table (one header line, terms in N-Triples spelling).
///
/// The union is the store's `graph=` set: one value, several IRIs, and the dataset becomes their
/// merge — so a query needs no `GRAPH` clause to join a task in `tasks.md` to the requirement it
/// names in a delta spec, or to the ledger item about it.
pub fn select(kernel: &Kernel, query: &str) -> Result<String> {
    let mut graphs = spec_graphs(kernel)?;
    graphs.push(LEDGER_GRAPH.to_string());
    ask(
        kernel,
        Verb::Source,
        "urn:iki:store:graph-select",
        &[
            ("query", query),
            ("graph", &graphs.join(" ")),
            ("as", "text/tab-separated-values"),
        ],
    )
}

Now the questions. Which requirements are there, and how strong is each?

#![allow(unused)]
fn main() {
extern crate openspec_ledger;
use openspec_ledger::{crate_dir, kernel, lift_tree, read_tree, select};

let host = kernel();
assert_eq!(lift_tree(&host, &read_tree(&crate_dir())).unwrap(), 5);

let strength = select(&host, r#"
    PREFIX os: <http://example.org/openspec#>
    SELECT DISTINCT ?capability ?requirement ?keyword WHERE {
      ?c a os:Capability ; os:name ?capability ; os:requirement ?r .
      ?r os:name ?requirement ; os:keyword ?keyword .
    } ORDER BY ?capability ?requirement ?keyword"#).unwrap();
assert_eq!(strength, "\
?capability\t?requirement\t?keyword
\"board\"\t\"A new game has an empty board\"\t\"SHALL\"
\"board\"\t\"Three in a line wins\"\t\"SHALL\"
\"moves\"\t\"A taken square is refused\"\t\"MUST\"
\"moves\"\t\"A taken square is refused\"\t\"MUST NOT\"
\"moves\"\t\"Players alternate\"\t\"SHALL\"
");
}

What does the change touch, and which of its tasks implements which requirement? This is the join no construct could make, across tasks.md and the delta spec:

#![allow(unused)]
fn main() {
extern crate openspec_ledger;
use openspec_ledger::{crate_dir, kernel, lift_tree, read_tree, select};

let host = kernel();
lift_tree(&host, &read_tree(&crate_dir())).unwrap();

let work = select(&host, r#"
    PREFIX os: <http://example.org/openspec#>
    SELECT DISTINCT ?number ?done ?how ?name WHERE {
      ?change os:id "add-undo" ; os:task ?t .
      ?t os:number ?number ; os:done ?done ; os:cites ?name .
      { ?change os:adds ?r BIND("adds" AS ?how) }
        UNION { ?change os:modifies ?r BIND("modifies" AS ?how) }
      ?r os:name ?name .
    } ORDER BY ?number"#).unwrap();
assert_eq!(work, "\
?number\t?done\t?how\t?name
\"1.2\"\tfalse\t\"adds\"\t\"The last move can be undone\"
\"1.3\"\tfalse\t\"adds\"\t\"The last move can be undone\"
\"2.1\"\tfalse\t\"modifies\"\t\"Players alternate\"
");
}

Two things to notice. DISTINCT is not decoration: a fact several documents state (that add-undo is a change, say — every file in its folder says so) is in the union once per document, so counting without DISTINCT over-counts. And task 1.1, which cites nothing, is not in the answer, because the query asked for tasks that cite; nothing about it is lost, it is simply about its change and no requirement.

What you built

The atoms are the Markdown files and the mapping file; the graph is derived from them, one named graph per document, and rebuilt from them whenever the host asks (lift_tree holds nothing). The lift and the mapping are compositions the host did not write; the queries are views. The code this chapter added to the book is a directory walk and two loops of requests.