Predicates and generators

Not everything a host knows is a fact it wants to serve. A license list, a parser, a geometry index or a walk over a graph the host already holds in memory is easier to compute than to project into relations. Vocabulary.AddPredicate registers a computed predicate at a path, and a query calls it like a relation: lic.permissive(?l), size.lines(?d, ?n). It comes in two kinds. A filter tests values that are all bound, and a generator produces values. A generator is also how a host makes a query fast where jaala’s own evaluation would be slow, since it’s the host’s Go running inside the query, citing what it read (#41).

The examples register one of each beside the guide’s deps vocabulary. stdlib’s str.* and num.* are registered the same way, and the built-ins page lists them.

package guide_test

import (
	"context"
	"fmt"
	"slices"

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

// lines is how big each package is, which the host knows and doesn't serve
// as facts.
var lines = map[string]int{"app": 120, "api": 900, "log": 40, "util": 300}

// predicates registers a filter and a generator beside the guide's
// vocabulary.
func predicates() (*ns.Vocabulary, error) {
	src := source()
	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
	}
	// A filter tests arguments that are all bound.
	err = v.AddPredicate("lic.permissive", ns.Builtin{
		Arity: 1,
		Doc:   "the license lets anyone reuse the code",
		Holds: func(args []ns.Value) (bool, error) {
			return slices.Contains([]string{"MIT", "Apache-2.0"}, args[0].S), nil
		},
	})
	if err != nil {
		return nil, err
	}
	// A generator produces values. It runs with the package bound, or with
	// nothing bound, listing every package; its Types read the count as a
	// number, so ?n > 100 compares numbers.
	err = v.AddPredicate("size.lines", ns.Builtin{
		Arity:  2,
		Labels: []string{"pkg", "lines"},
		Types:  []ns.ArgType{{}, {Type: ns.TypeNumber}},
		Modes:  [][]bool{{true, false}, {false, false}},
		Doc:    "how many lines a package has",
		Gen: func(ctx context.Context, _ ns.Source, args []ns.Arg, emit func([]ns.Value, []string) error) error {
			for _, pkg := range []string{"app", "api", "log", "util"} {
				if args[0].Bound && args[0].Value.S != pkg {
					continue
				}
				if err := emit([]ns.Value{ns.S(pkg), ns.N(float64(lines[pkg]))}, []string{"sloc:" + pkg}); err != nil {
					return err
				}
			}
			return ctx.Err()
		},
	})
	if err != nil {
		return nil, err
	}
	if err := v.AddModule("deps", datalog.LanguageName, deps, "deps.dl"); err != nil {
		return nil, err
	}
	return v, v.Check()
}

func predicateRows(query string) {
	v, err := predicates()
	if err != nil {
		panic(err)
	}
	q := datalog.MustParse(query)
	rows, err := datalog.SemiNaive{}.Eval(context.Background(), q, datalog.MustBase(v, source()))
	if err != nil {
		fmt.Println(err)
		return
	}
	for _, r := range rows {
		var vals []string
		for _, col := range q.Select {
			vals = append(vals, r.Bind[col.Var].S)
		}
		fmt.Println(vals, r.Cites)
	}
}

// A filter keeps a binding when Holds says so, and `not` keeps it when Holds
// says no, so the two can't disagree.
func Example_filter() {
	predicateRows(`pkg(?p, ?l), lic.permissive(?l) => ?p`)
	predicateRows(`pkg(?p, ?l), not lic.permissive(?l) => ?p`)
	// Output:
	// [app] []
	// [util] []
	// [api] []
	// [log] []
}

// A generator runs once one of its modes is satisfied, wherever it's
// written: here depends_on binds ?d first, so size.lines is asked about each
// dependency rather than listing every package. Each answer cites what the
// generator emitted.
func Example_generator() {
	predicateRows(`size.lines(?d, ?n), deps.depends_on("app", ?d), ?n > 100 => ?d, ?n`)
	// Output:
	// [api 900] [sloc:api]
	// [util 300] [sloc:util]
}

// A generator must say which bindings it runs under, so a scan of
// everything is a declaration rather than an accident.
func Example_generatorNeedsModes() {
	v, _ := ns.NewVocabulary(source())
	err := v.AddPredicate("size.lines", ns.Builtin{
		Arity: 2,
		Gen: func(context.Context, ns.Source, []ns.Arg, func([]ns.Value, []string) error) error {
			return nil
		},
	})
	fmt.Println(err)
	// Output:
	// query: generator "size.lines" declares no Modes; list the binding patterns it accepts (an all-false mode if it may enumerate with nothing bound)
}

Filters ¶

A filter’s ns.Builtin sets Holds, which gets the argument values and says whether the binding passes. Every argument has to be bound when it runs. jaala holds a filter until the literals binding its arguments have run, so one written before them still works, and refuses a body where nothing ever binds one: query: lic.permissive needs all arguments bound (a variable must appear in a relation before lic.permissive tests it).

not lic.permissive(?l) runs the same test and keeps the binding when it fails, so a filter and its negation can’t disagree. Example_filter lists the packages with a permissive license, then the rest: api, whose license the source didn’t state, fails the test, so it’s among the rest. A filter cites nothing, so a row’s citations are its facts’. A store that applies a filter exactly as the vocabulary does can be sent it with a pushed join (ns.FilterSource, on facts from stores).

Generators ¶

A generator sets Gen. It gets the query’s context, the source the query runs over, and one ns.Arg per argument, Value set where the binding fixes it and Bound saying whether it does. It calls emit once per solution, with a value for every argument and the citations that justify it, and jaala unifies each solution with the call, so one disagreeing with a bound argument is dropped there. jaala copies what it needs before emit returns, so a generator can reuse one buffer for every solution.

emit returns an error when the query stops, cancelled or over its Budget (every emitted solution counts as work), and the generator returns it as is. A long walk should also check ctx itself, and can charge its own steps to the query’s budget through ns.AllowanceFrom(ctx) (#361): Spend(n) errs once the budget is spent, and the generator returns that error as it is, so a walk of a hundred thousand steps under a budget of a thousand stops after a thousand rather than after it’s done. Left() says what’s left, and whether there’s a budget at all. What a generator spends counts against the Budget beside the query’s work but isn’t part of Work; Explain reports it as Report.Spent, and on the literal that called the generator. A generator’s values must come from finite data the host holds, since jaala’s guarantee that evaluation ends rests on no rule inventing a value.

Modes ¶

Modes says which bindings a generator runs under: one list per mode, true where that argument must be bound. size.lines runs with its package bound, {true, false}, or with nothing bound, {false, false}, listing every package. A generator that can list everything says so with an all-false mode, so a full scan is a declaration rather than an accident, and AddPredicate refuses a generator with no modes (Example_generatorNeedsModes).

The planned SemiNaive runs a generator as soon as one of its modes is satisfied, so a host never has to write a body generator-first (#36). In Example_generator, size.lines(?d, ?n) is written first, but depends_on binds ?d, so the generator is asked about each dependency rather than listing every package, and each row cites sloc: for its size. A call with nothing bound lists everything, so it ranks after relations the engine already holds or derives (#293), and a variable only the all-free mode would take counts as unbound when ranking (#304). A generator whose only bound arguments are constants waits, once the body has bound something, for a literal that joins it to what’s bound (#402), so two generators each with a constant don’t run as a cross product ahead of the edge between them. A body that can never satisfy any mode is refused before anything runs, by every evaluator and by Validate: query: … calls …, and nothing binds what … needs first: it needs ….

Naive doesn’t plan. It calls a generator where it’s written, with the unbound arguments Bound: false, so a generator must refuse a call it can’t run, returning an error, rather than read the zero value. stdlib’s str.distance errs that way.

A walk of the host’s own ¶

A host whose graph lives in its own structures, rather than in a relation a query can walk with graph.closure, writes only one step: stdlib.Hops(step, extra...) takes a function listing one node’s neighbours, with each edge’s citations, and builds reach(?from, ?to, extra..., ?within, ?hops) (#281). jaala walks breadth first from whichever end the body binds, so ?within is “at most this many steps” and the walk asks nothing past it, and ?hops is the fewest steps, cited by one path of that length in order from ?from to ?to. stdlib.Reach hands the host the whole walk instead, for a host whose walk is its own.

stdlib.Paths(step, extra...) builds paths(?from, ?to, extra..., mode, ?within, ?path) over the same step, binding each path as a value, as graph.paths does over a relation, with the same modes and ?within 0 for no bound (#280). stdlib.EdgePaths takes a step that names each edge too (a part between two nets, a call site), so two parallel edges make two paths and a trail takes each once. It asks for each node’s steps once per call and stops when the query has enough.

Labels and types ¶

Labels and Types describe the arguments as a base relation’s schema does. jaala reads an emitted value as its argument’s type, so size.lines emitting ns.N(900) into a number column compares as a number in ?n > 100, and a generator reading a number argument waits for the relations binding it, so it reads the spelling they agree on (#244). A generator typing nothing, as most hosts’ do, is never held. Doc is the line a host shows when it lists the vocabulary.

When answers can be kept ¶

A Base keeps the derived relations a query evaluated in full and reuses them in later queries (host options), which assumes a predicate answers the same for the same arguments and source. One that doesn’t, because it reads the clock, the network, or a host index updated in place, sets Volatile, and no relation reading it, directly or through others, is kept.

Under At(v) a generator’s context carries the version (ns.VersionOf), so one reading versioned data of its own reads the same version. Under Across a generator holds in every version, since jaala can’t know what it read (versions).