Embedding jaala in Go

The first four tutorials wrote queries against facts the site provided. A real host provides the facts itself, from whatever it already has: a parsed go.mod, a netlist, a database. This tutorial builds the pieces you need as a host, in Go, over a few of the same imports.

Every code block on this page is a file from docsite/examples/host/, included as is. The last three are Go Example functions, so go test runs them on every build of this site and checks their output against the // Output: comment at the end. If jaala’s API or answers change, the build fails before the page can drift.

Facts from Go ¶

A Source serves a relation’s tuples. ns.MemSource is the simplest one, a set of tuples held in memory, which is pretty much all a test or a small host needs. Each tuple carries its citations, which is how an answer can point back at the line of a file it came from:

package host_test

import (
	"fmt"

	"github.com/panyam/jaala/ns"
)

// source is the facts a host serves. A MemSource is the simplest Source. You
// declare each relation with its column labels, then add tuples, each with
// the citations an answer that uses it will show. A real host implements
// ns.Source over its own data instead.
func source() *ns.MemSource {
	src := ns.NewMemSource().Declare("imports", "from", "to")
	edges := [][2]string{
		{"app", "api"}, {"api", "auth"}, {"api", "log"},
		{"auth", "log"}, {"log", "util"},
	}
	for i, e := range edges {
		src.Add("imports", ns.Tuple{
			Vals:  []ns.Value{ns.S(e[0]), ns.S(e[1])},
			Cites: []string{fmt.Sprintf("imports.txt:%d", i+1)},
		})
	}
	return src
}

A vocabulary and a base ¶

The vocabulary is everything a query can name: the source’s relations, the standard library (str.contains and friends), and modules of rules. Here the rules from the second tutorial become a module called deps, so a query calls deps.depends_on. Check resolves the modules and reports a mistake in one, with the file it came from, before any query runs.

package host_test

import (
	"github.com/panyam/jaala/datalog"
	"github.com/panyam/jaala/ns"
	"github.com/panyam/jaala/stdlib"
)

// deps is a module, the rules a host ships as a library. A query calls them
// by path, as deps.depends_on.
const deps = `
depends_on(?a, ?b) :- imports(?a, ?b);
depends_on(?a, ?c) :- depends_on(?a, ?b), imports(?b, ?c);
`

// base builds what a query runs against. The vocabulary names everything a
// query can call, which is the Source's relations, the standard library and
// the modules. A host builds and checks it once, at startup, and builds a
// Base per dataset. A Base is safe to share across concurrent queries.
func base(src ns.Source) (*datalog.Base, error) {
	v, err := ns.NewVocabulary(src)
	if err != nil {
		return nil, err
	}
	if err := v.AddLanguage(datalog.Language); err != nil {
		return nil, err
	}
	if err := stdlib.Register(v); err != nil {
		return nil, err
	}
	err = v.AddModule("deps", datalog.LanguageName, deps, "deps.dl")
	if err != nil {
		return nil, err
	}
	if err := v.Check(); err != nil {
		return nil, err
	}
	return datalog.NewBase(v, src)
}

A host usually builds the vocabulary once at startup and a Base per dataset. A Base caches what it reads, and it’s safe to share between queries running at the same time.

Running a query ¶

MustParse turns query text into a Query, and SemiNaive.Eval answers it. Bind fills a goal variable from Go, so one query serves every package and you never build query text by hand. Budget caps the work, so a query over a big graph stops instead of running on:

package host_test

import (
	"context"
	"fmt"

	"github.com/panyam/jaala/datalog"
	"github.com/panyam/jaala/ns"
)

// A query is parsed once and run as often as needed. Bind gives a goal
// variable its value from the host, so the query text stays fixed while the
// package changes, and Budget caps the work one evaluation may do.
func Example() {
	b, err := base(source())
	if err != nil {
		fmt.Println(err)
		return
	}
	q := datalog.MustParse(`deps.depends_on(?p, ?d) => ?d`)
	for _, pkg := range []string{"api", "log"} {
		rows, err := datalog.SemiNaive{}.Eval(context.Background(), q, b,
			datalog.Bind(map[datalog.Var][]ns.Value{"p": {ns.S(pkg)}}),
			datalog.Budget(100_000))
		if err != nil {
			fmt.Println(err)
			return
		}
		for _, r := range rows {
			fmt.Println(pkg, "depends on", r.Bind["d"].S, r.Cites)
		}
	}
	// Output:
	// api depends on auth [imports.txt:2]
	// api depends on log [imports.txt:3]
	// api depends on util [imports.txt:3 imports.txt:5]
	// log depends on util [imports.txt:5]
}

Each row’s Bind maps a column to its value, and Cites is the sorted set of citations behind it. api depends on util through log, so that row cites both imports.

Witnesses ¶

Citations say which facts an answer used. Ask for Witnesses and each row also says how they were combined, as a tree of the rules that fired:

package host_test

import (
	"context"
	"fmt"
	"strings"

	"github.com/panyam/jaala/datalog"
)

// Witnesses records how each answer was derived, as a tree of the rules that
// fired with the facts at its leaves, in written order.
func Example_witnesses() {
	b, err := base(source())
	if err != nil {
		fmt.Println(err)
		return
	}
	q := datalog.MustParse(`deps.depends_on("app", "util")`)
	ctx := context.Background()
	rows, err := datalog.SemiNaive{}.Eval(ctx, q, b, datalog.Witnesses())
	if err != nil {
		fmt.Println(err)
		return
	}
	for _, w := range rows[0].Witness {
		show(w, 0)
	}
	// Output:
	// deps.depends_on(app, util)
	//   deps.depends_on(app, log)
	//     deps.depends_on(app, api)
	//       imports(app, api)  imports.txt:1
	//     imports(api, log)  imports.txt:3
	//   imports(log, util)  imports.txt:5
}

func show(w *datalog.Witness, depth int) {
	vals := make([]string, len(w.Values))
	for i, v := range w.Values {
		vals[i] = v.S
	}
	line := strings.Repeat("  ", depth) +
		w.Relation + "(" + strings.Join(vals, ", ") + ")"
	if len(w.Cites) > 0 {
		line += "  " + strings.Join(w.Cites, ", ")
	}
	fmt.Println(line)
	for _, c := range w.Children {
		show(c, depth+1)
	}
}

The tree follows the program as written, even though the evaluator may have rewritten it quite a bit to run faster, so you can show it to the person who wrote the rules.

Errors ¶

A query that can’t be right fails with an error whose text starts with query:, which is safe to show whoever wrote the query. Running out of budget is its own type, so a host can tell “this question is too big” apart from “this question is wrong”:

package host_test

import (
	"context"
	"errors"
	"fmt"

	"github.com/panyam/jaala/datalog"
)

// An error is either the query's own fault, whose text starts with "query:"
// and is safe to show to whoever wrote the query, or a BudgetExceeded, which a
// host can test for and handle on its own.
func Example_errors() {
	b, err := base(source())
	if err != nil {
		fmt.Println(err)
		return
	}
	ctx := context.Background()
	wrong := datalog.MustParse(`deps.depends_on(?p) => ?p`)
	_, err = datalog.SemiNaive{}.Eval(ctx, wrong, b)
	fmt.Println(err)

	all := datalog.MustParse(`deps.depends_on(?p, ?d) => ?p, ?d`)
	_, err = datalog.SemiNaive{}.Eval(ctx, all, b, datalog.Budget(5))
	var over *datalog.BudgetExceeded
	if errors.As(err, &over) {
		fmt.Println("stopped at the budget of", over.Limit)
	}
	// Output:
	// query: relation "deps.depends_on" takes 2 args, got 1
	// stopped at the budget of 5
}

A host runs this loop for as long as it lives. Most of the work after this page is deciding which facts to serve and which rules belong in a module. The guide has the language’s rules in full.