Versions
One base over several versions of the facts: answering at a revision with At, across many at once with Across, and what changed between two with Diff.
A host often keeps several versions of the same facts: the revisions of a design, or the commits of a repo. Most facts don’t change between two of them, so serving each version as its own source repeats nearly everything. A source implementing ns.TimedSource serves each fact once, with the versions it holds in, and one base answers at any of them (#179).
package guide_test
import (
"context"
"encoding/json"
"fmt"
"slices"
"github.com/panyam/jaala/datalog"
"github.com/panyam/jaala/ns"
)
// history serves three revisions of the imports. app imports api
// throughout, api imports log from revision 1 on, and api imported util
// only in revision 0. A fact is its values, so each one is served once with
// the revisions it holds in, and its citations can differ per revision.
func history() *ns.TimedMemSource {
src := ns.NewTimedMemSource(ns.Span(0, 3))
src.Declare("imports", "from", "to").Declare("pkg", "name", "license")
src.Add("imports", ns.Since(0), []string{"app.go:3"}, ns.S("app"), ns.S("api"))
src.Add("imports", ns.Since(1), []string{"api.go:5"}, ns.S("api"), ns.S("log"))
src.Add("imports", ns.Bits(0), []string{"api.go:4"}, ns.S("api"), ns.S("util"))
return src
}
func versionedBase() *datalog.Base {
src := history()
v, err := vocabulary(src)
if err != nil {
panic(err)
}
return datalog.MustBase(v, src)
}
// At answers a query at one revision, over the facts that hold there, as a
// Base over only those facts would. One Base serves every revision.
func Example_at() {
b, ctx := versionedBase(), context.Background()
q := datalog.MustParse(`deps.depends_on("app", ?d) => ?d`)
for _, rev := range []ns.Version{0, 2} {
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.At(rev))
fmt.Print(rev, ":")
for _, r := range rows {
fmt.Print(" ", r.Bind["d"].S)
}
fmt.Println()
}
// Output:
// 0: api util
// 2: api log
}
// Diff is what changed in a relation between two revisions, each fact with
// the citations of the revision it holds in.
func Example_diff() {
b, ctx := versionedBase(), context.Background()
d, _ := b.Diff(ctx, "imports", 0, 2)
for _, t := range d.Added {
fmt.Println("+", t.Vals[0].S, t.Vals[1].S, t.Cites)
}
for _, t := range d.Removed {
fmt.Println("-", t.Vals[0].S, t.Vals[1].S, t.Cites)
}
// Output:
// + api log [api.go:5]
// - api util [api.go:4]
}
// A session's edits are a change set over the last revision, read through
// an overlay before anything is saved: api drops log for util. Effective
// is what the session changes, and a commit keeps it as revision 3, which
// the Base answers at as it does any other.
func Example_session() {
src, ctx := history(), context.Background()
v, err := vocabulary(src)
if err != nil {
panic(err)
}
var edit ns.Changes
edit.Remove("imports", ns.Tuple{Vals: []ns.Value{ns.S("api"), ns.S("log")}}).
Add("imports", ns.Tuple{Vals: []ns.Value{ns.S("api"), ns.S("util")}, Cites: []string{"session:1"}})
session := ns.Overlay(src, edit)
q := datalog.MustParse(`deps.depends_on("app", ?d) => ?d`)
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, datalog.MustBase(v, session))
fmt.Println("session:", depsOf(rows))
changed, _ := session.Effective(ctx)
fmt.Println("changes:", len(changed.Added("imports")), "added,", len(changed.Removed("imports")), "removed")
b := datalog.MustBase(v, src)
if err := src.Commit(edit, 2, 3); err != nil {
panic(err)
}
for _, rev := range []ns.Version{2, 3} {
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.At(rev))
fmt.Println("revision", rev, depsOf(rows))
}
// Output:
// session: [api util]
// changes: 1 added, 1 removed
// revision 2 [api log]
// revision 3 [api util]
}
// A session travels as JSON: a browser keeps it beside its snapshot, and a
// server reads it through an overlay of its own store. Base names the
// revision it was made over, so a server can tell when that has moved.
func Example_sessionWire() {
var edit ns.Changes
edit.Remove("imports", ns.Tuple{Vals: []ns.Value{ns.S("api"), ns.S("log")}}).
Add("imports", ns.Tuple{Vals: []ns.Value{ns.S("api"), ns.S("util")}, Cites: []string{"session:1"}})
data, _ := json.Marshal(ns.Session{Base: "2", Changes: edit})
fmt.Println(string(data))
var back ns.Session
if err := json.Unmarshal(data, &back); err != nil {
panic(err)
}
fmt.Println(back.Base, len(back.Changes.Added("imports")), "added")
// Output:
// {"base":"2","changes":{"format":1,"ops":[{"rel":"imports","op":"remove","vals":["api","log"]},{"rel":"imports","op":"add","vals":["api","util"],"cites":["session:1"]}]}}
// 2 1 added
}
func depsOf(rows []datalog.Row) []string {
var out []string
for _, r := range rows {
out = append(out, r.Bind["d"].S)
}
return out
}
// Across evaluates once over a range of revisions, and each row carries
// the revisions it holds in, so "since when does app depend on log" is one
// query rather than one per revision.
func Example_across() {
b, ctx := versionedBase(), context.Background()
q := datalog.MustParse(`deps.depends_on("app", ?d) => ?d`)
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Across(ns.Span(0, 3)))
for _, r := range rows {
fmt.Println(r.Bind["d"].S, slices.Collect(r.Versions.Ranges()))
}
// Output:
// api [{0 3}]
// log [{1 3}]
// util [{0 1}]
}
// An aggregate across revisions is cut where its inputs change, so a
// count per revision is one query. app has two dependencies in every
// revision, but not the same two, so the count is two rows citing
// different facts.
func Example_acrossCount() {
b, ctx := versionedBase(), context.Background()
q := datalog.MustParse(`deps.depends_on("app", ?d) => count(?d)`)
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Across(ns.Span(0, 3)))
for _, r := range rows {
fmt.Println(r.Bind["count(d)"].S, slices.Collect(r.Versions.Ranges()))
}
// Output:
// 2 [{0 1}]
// 2 [{1 3}]
}
// revisions is history served a revision at a time as a store of its own
// (ns.SourceAt), the way a host keeps revisions in a database: a question
// at a revision asks that revision's store for what it binds.
type revisions struct{ *ns.TimedMemSource }
func (r revisions) SourceAt(v ns.Version) (ns.Source, error) {
return revisionStore{r.TimedMemSource, v}, nil
}
// LookupTimed answers a bound call across every revision at once
// (ns.TimedLookupSource), each fact with the revisions it holds in, which
// is what Across asks. A real store would ask its database for the rows
// with their revision ranges.
func (r revisions) LookupTimed(ctx context.Context, rel string, bound map[int]ns.Value) ([]ns.TimedTuple, error) {
fmt.Println("history looks up", rel, bound[0].S)
all, err := r.TimedTuples(ctx, rel)
var out []ns.TimedTuple
for _, t := range all {
if v, ok := bound[0]; !ok || t.Vals[0].S == v.S {
out = append(out, t)
}
}
return out, err
}
// revisionStore is one revision's facts, answering lookups. A real store
// would ask its database for the revision's rows.
type revisionStore struct {
*ns.TimedMemSource
v ns.Version
}
func (s revisionStore) Tuples(rel string) []ns.Tuple {
all, _ := s.TimedTuples(context.Background(), rel)
var out []ns.Tuple
for _, t := range all {
if t.Versions.Contains(s.v) {
out = append(out, ns.Tuple{Vals: t.Vals, Cites: t.CitesAt(s.v)})
}
}
return out
}
func (s revisionStore) Lookup(_ context.Context, rel string, bound map[int]ns.Value) ([]ns.Tuple, error) {
fmt.Println("revision", s.v, "looks up", rel, bound[0].S)
var out []ns.Tuple
for _, t := range s.Tuples(rel) {
if v, ok := bound[0]; !ok || t.Vals[0].S == v.S {
out = append(out, t)
}
}
return out, nil
}
// A timed source that serves each revision as a store is asked at a
// revision as any store is, and a Federation of it with a source that
// doesn't change between revisions (licenses here) answers At over both.
func Example_atFromStores() {
licenses := ns.NewMemSource()
licenses.Declare("pkg", "name", "license")
licenses.Add("pkg", ns.Tuple{Vals: []ns.Value{ns.S("log"), ns.S("MIT")}})
f, _ := ns.NewFederation(ns.Member{Source: revisions{history()}}, ns.Member{Source: licenses})
tf, _ := f.Timed()
v, _ := vocabulary(tf)
b, ctx := datalog.MustBase(v, tf), context.Background()
q := datalog.MustParse(`imports("api", ?d), pkg(?d, ?l) => ?d, ?l`)
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.At(2))
for _, r := range rows {
fmt.Println(r.Bind["d"].S, r.Bind["l"].S)
}
// Output:
// revision 2 looks up imports api
// log MIT
}
// Across over a timed source that looks up across revisions asks it for
// what the query binds, rather than reading every revision's facts whole.
// The rows hold in the revisions they do when read whole.
func Example_acrossFromStores() {
src := revisions{history()}
v, _ := vocabulary(src)
b, ctx := datalog.MustBase(v, src), context.Background()
q := datalog.MustParse(`deps.depends_on("app", ?d) => ?d`)
rows, _ := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Across(ns.Span(0, 3)))
for _, r := range rows {
fmt.Println(r.Bind["d"].S, slices.Collect(r.Versions.Ranges()))
}
// Output:
// history looks up imports app
// history looks up imports api
// history looks up imports log
// history looks up imports util
// api [{0 3}]
// log [{1 3}]
// util [{0 1}]
}
Versions and version sets ¶
A version is an ns.Version, a number the host assigns. jaala only compares and collects versions, so what they stand for is up to the host. The versions a fact holds in are an ns.VersionSet, and ns has two kinds. An IntervalSet holds ranges, for linear history, where a fact usually holds from one revision until another: ns.Span(1, 4) is revisions 1 to 3, and ns.Since(1) is revision 1 and every one after it. A BitSet holds bits, for history that branches, where a fact’s commits can be anywhere: ns.Bits(0, 5, 9). The two combine with each other, and an operation answers in its receiver’s kind.
A fact is its values. Two versions holding the same values hold one fact, even when their citations differ, so a host whose citations change on every export, such as one embedding an export’s own ids, still shares its unchanged facts. A TimedTuple carries its citations per version, and the engine shows the ones for the version asked about. Deciding which facts are the same across versions is the host’s job: jaala never guesses that two different values name one thing.
At ¶
datalog.At(v) answers a query at version v, over exactly the facts holding there, each with v’s citations. It answers as a base over a source serving only those facts would, with every evaluator, option and witness. Each version’s facts, indexes and derived relations are cached apart from every other’s, and Base.LimitVersions bounds how many versions’ caches a base keeps, 8 by default. The facts themselves are read from the source once for every version. A generator called under At is handed the version’s facts as its source, and a context carrying the version (ns.VersionOf), so one reading versioned data of its own can read the same version.
A query without At reads a timed source as any other, through Tuples, so it sees whichever facts the source serves there, usually its latest version. ns.TimedMemSource serves its last version that way.
A timed source that is also ns.Versioned drops every version’s caches when its version moves, as it would its own, so a host adding a new revision bumps the version.
Versions from stores ¶
A timed source read through TimedTuples hands over every fact of a relation, in every version, the first time a version reads it. That suits facts held in memory. For versions kept in a store, the source implements ns.SourceAt as well, returning version v’s facts as a source of its own (#312). At(v) then reads that source as it reads any other, so a lookup, a pushed join, a walk, a summary or a page goes to the version’s store, and TimedTuples isn’t read at all. The engine asks SourceAt once per version whose caches it keeps, so a source over one database returns a small view of it (the database and the version) rather than copying anything. A version’s source that is ns.Versioned drops that version’s caches when it moves, and what a version keeps in a DerivedStore is filed under the version too.
Facts often come from places with different histories, such as a design’s netlist, which changes every revision, and a datasheet library, which doesn’t. Federation.Timed makes a federation a timed source: a member that serves versions holds its facts in them, any other member holds its facts in every version, and at a version the federation is one over the members at that version, with their names, Holds and partitioning. Its versions are the ones every timed member serves.
Example_atFromStores, in the example at the top of the page, asks revision 2’s store for what api imports, and the license comes from the member that doesn’t change.
Across asks a different question of a store: every fact matching a call, in every version at once. A timed source that can answer it implements ns.TimedLookupSource, whose LookupTimed takes the bound values as Lookup does and returns TimedTuples, each fact once with the versions it holds in (#317). Across then asks it for what a query binds rather than reading TimedTuples whole, and ns.TimedLookupRelations says which relations it looks up, when not all of them. A timed federation looks a call up in the members whose Holds allow it, a timed member through LookupTimed and any other through Lookup, its facts holding in every version. Example_acrossFromStores asks the history for what each package imports, a call per package the recursion reaches, and answers the rows reading it whole gives.
Across ¶
datalog.Across(vs) evaluates a query once over every version in vs, and each row carries the versions it holds in, in Row.Versions (#180). The rows holding version v are exactly the rows At(v) answers. A join holds in the versions all its facts hold in, a tuple derived two ways holds in the versions either holds in, and a not holds in the versions the negated relation doesn’t. So when most facts hold in most versions, a recursive relation is worked out about once rather than once per version. On a points-to analysis over 50 revisions with 4% of its facts changing somewhere, Across does a ninth of the work of 50 Ats and takes about a fifth of the time (BenchmarkVersions).
A row that holds in some versions and not others says when it started or stopped holding, like log above, which app depends on from revision 1. Where a row is derived differently in two versions, it’s answered once per derivation, each copy with the versions it holds that way in, so each version’s copy is the row At gives it, witness included. A limit and offset page each version’s rows separately, as At would.
Citations differ per version, so a row’s Cites are its facts’ citations in the latest version it holds in, and Row.CitesAt(v) gives another version’s. Likewise Witness.At(v) turns a row’s witness into the one At(v) gives. A generator, filter or comparison holds in every version, since jaala can’t know what a host’s Go reads, so a generator reading versioned data of its own belongs under At. Across reads the source’s facts through TimedTuples, or LookupTimed for a bound call, without pushdown, walks or streaming, and keeps nothing for a later query, neither the facts it looked up nor a derived relation.
An aggregate across versions is cut at the versions where its inputs change (#181). Each group is reduced per stretch of versions over the bindings holding in all of them, and stretches that reduce to the same row from the same facts share one. app depends on two packages in every revision above, but on util in revision 0 and log after, so its count is two rows, each citing its own facts, and a count over facts that don’t change between revisions is one. A group with no rows in some versions has no row there, and a goal with no group column answers its row over nothing (a count of 0) in the versions where nothing matched, as At does. That covers aggregates in the goal, in a rule head and in a body, having included.
Diff ¶
Base.Diff(ctx, rel, from, to) lists the facts of a base relation that hold in to and not from, with to’s citations, and those that held in from and not to, with from’s. Facts are compared as the engine reads them, as the relation’s declared types with units folded, so "1.0" served in one version and 1 in the next is one unchanged number. A fact whose citations changed and nothing else isn’t in either list.
Sessions ¶
A session’s edits are checked as if they were applied before anything is saved, and then kept as a new version or thrown away (#288). The engine never writes to a source, so an edit is an ns.Changes, the facts to add to and remove from each base relation (#287), and ns.Overlay(src, changes) is a source serving src’s facts minus the ones removed, plus the ones added. A base over it answers with the session’s own writes, as Example_session shows, and the base over src never sees them. Throwing the session away means dropping the overlay; an undo is the change sets before the last one, composed with Changes.Then.
A fact is named by its values, read as its argument’s declared type as a lookup reads it, so a removal names a fact as the store serves it, units and all. The last operation on a fact wins, and a fact the change set names is replaced wherever the store holds it, every copy, so adding a fact the store holds already holds it once, with the session’s citations.
An overlay passes on every store interface its source implements. A lookup or a batch goes to the store, and the facts the session adds join every answer for that relation. A pushed conjunction, a walk or a summary goes to the store only when it reads no relation the session touched; otherwise the planner solves it literal by literal through lookups, since the store’s own join can’t see the session. Each overlay’s Version is the source’s joined with a fingerprint of its change set, so a base kept over a session drops what it held when an edit makes a new overlay.
Effective is what a session changes: the removals of facts the store holds and the additions of facts it doesn’t, which is what a host rechecks. A commit keeps them as a new version. TimedMemSource.Commit(changes, from, to) adds version to holding from’s facts with the changes applied, so Diff from from to to lists the session’s effective changes, and a host’s own timed store commits the same way. To edit an older version, overlay that version’s source (SourceAt) rather than the timed source, whose plain reads serve its latest.
A session moves between processes as JSON (#417): ns.Changes implements json.Marshaler and json.Unmarshaler, and ns.Session adds the version it was made over, the host’s own name for it, which jaala carries and never reads. Example_sessionWire shows the form. A browser running the engine in wasm keeps a session beside its snapshot and sends it to a server, which reads it through an overlay of its own store and answers as the browser did. A decoded change set is the one that was encoded, down to each value’s kind, spelling and unit, the order of its operations and its overlay’s Version. A value is a string, a number, null for absent, or an object of num, unit and text for what plain JSON would lose (a unit, a spelling such as 1.50, NaN), so a list’s values read the same way. A statement that writes compiles into a change set where it’s written, and the change set is what travels.