topdown

Documentation

Index

• Constants
• func Eval(ctx *Context, iter Iterator) error
• func IsUnboundGlobal(e error) bool
• func PlugExpr(expr *ast.Expr, ctx *Context) *ast.Expr
• func PlugTerm(term *ast.Term, ctx *Context) *ast.Term
• func PlugValue(v ast.Value, ctx *Context) ast.Value
• func Query(params *QueryParams) (interface{}, error)
• func RegisterBuiltinFunc(name ast.Var, fun BuiltinFunc)
• func ValueToFloat64(v ast.Value, ctx *Context) (float64, error)
• func ValueToInterface(v ast.Value, ctx *Context) (interface{}, error)
• func ValueToSlice(v ast.Value, ctx *Context) ([]interface{}, error)
• func ValueToString(v ast.Value, ctx *Context) (string, error)
• type BuiltinFunc
• type Context
  • func NewContext(query ast.Body, ds *storage.DataStore) *Context
  • func (ctx *Context) BindValue(key ast.Value, value ast.Value) *Context
  • func (ctx *Context) BindVar(variable ast.Var, value ast.Value) *Context
  • func (ctx *Context) Binding(k ast.Value) ast.Value
  • func (ctx *Context) Child(query ast.Body, locals *storage.Bindings) *Context
  • func (ctx *Context) Current() *ast.Expr
  • func (ctx *Context) Step() *Context
• type Error
  • func (e *Error) Error() string
• type Iterator
• type QueryParams
  • func NewQueryParams(ds *storage.DataStore, globals *storage.Bindings, path []interface{}) (q *QueryParams)
• type StdoutTracer
  • func (t *StdoutTracer) Enabled() bool
  • func (t *StdoutTracer) Trace(ctx *Context, f string, a ...interface{})
• type Tracer
• type Undefined
  • func (undefined Undefined) String() string

Constants

const (

	// InternalErr represents an unknown evaluation error
	InternalErr = iota

	// UnboundGlobalErr indicates a global variable without a binding was
	// encountered during evaluation.
	UnboundGlobalErr = iota

	// ConflictErr indicates multiple (conflicting) values were produced
	// while generating a virtual document. E.g., given two rules that share
	// the same name: p = false :- true, p = true :- true, a query "p" would
	// evaluate p to "true" and "false".
	ConflictErr = iota
)

Functions

func Eval

func Eval(ctx *Context, iter Iterator) error

Eval runs the evaluation algorithm on the contxet and calls the iterator foreach context that contains bindings that satisfy all of the expressions inside the body.

func IsUnboundGlobal

func IsUnboundGlobal(e error) bool

IsUnboundGlobal returns true if the error e is an UnboundGlobalErr

func PlugExpr

func PlugExpr(expr *ast.Expr, ctx *Context) *ast.Expr

PlugExpr returns a copy of expr with bound terms substituted for values in ctx.

func PlugTerm

func PlugTerm(term *ast.Term, ctx *Context) *ast.Term

PlugTerm returns a copy of term with bound terms substituted for values in ctx.

func PlugValue

func PlugValue(v ast.Value, ctx *Context) ast.Value

PlugValue returns a copy of v with bound terms substituted for values in ctx.

func Query

func Query(params *QueryParams) (interface{}, error)

Query returns the document identified by the path.

If the storage node identified by the path is a collection of rules, then the TopDown algorithm is run to generate the virtual document defined by the rules.

func RegisterBuiltinFunc

func RegisterBuiltinFunc(name ast.Var, fun BuiltinFunc)

RegisterBuiltinFunc adds a new built-in function to the evaluation engine.

func ValueToFloat64

func ValueToFloat64(v ast.Value, ctx *Context) (float64, error)

ValueToFloat64 returns the underlying Go value associated with an AST value. If the value is a reference, the reference is fetched from storage.

func ValueToInterface

func ValueToInterface(v ast.Value, ctx *Context) (interface{}, error)

ValueToInterface returns the underlying Go value associated with an AST value. If the value is a reference, the reference is fetched from storage. Composite AST values such as objects and arrays are converted recursively.

func ValueToSlice

func ValueToSlice(v ast.Value, ctx *Context) ([]interface{}, error)

ValueToSlice returns the underlying Go value associated with an AST value. If the value is a reference, the reference is fetched from storage.

func ValueToString

func ValueToString(v ast.Value, ctx *Context) (string, error)

ValueToString returns the underlying Go value associated with an AST value. If the value is a reference, the reference is fetched from storage.

Types

type BuiltinFunc

type BuiltinFunc func(ctx *Context, expr *ast.Expr, iter Iterator) (err error)

BuiltinFunc defines the interface that the evaluation engine uses to invoke built-in functions. Users can implement their own built-in functions and register them with the evaluation engine.

Callers are given the current evaluation Context ctx with the expression expr to be evaluated. Callers can assume that the expression has been plugged with bindings from the current context. If the built-in function determines that the expression has evaluated successfully it should bind any output variables and invoke the iterator with the context produced by binding the output variables.

type Context

type Context struct {
	Query     ast.Body
	Globals   *storage.Bindings
	Locals    *storage.Bindings
	Index     int
	Previous  *Context
	DataStore *storage.DataStore
	Tracer    Tracer
}

Context contains the state of the evaluation process.

TODO(tsandall): profile perf/memory usage with current approach; the current approach copies the Context structure for each step and binding. This avoids the need to undo steps and bindings each time the proof fails but this may be too expensive.

func NewContext

func NewContext(query ast.Body, ds *storage.DataStore) *Context

NewContext creates a new Context with no bindings.

func (*Context) BindValue

func (ctx *Context) BindValue(key ast.Value, value ast.Value) *Context

BindValue returns a new Context with bindings that map the key to the value.

func (*Context) BindVar

func (ctx *Context) BindVar(variable ast.Var, value ast.Value) *Context

BindVar returns a new Context with bindings that map the variable to the value.

If the caller attempts to bind a variable to itself (e.g., "x = x"), no mapping is added. This is effectively a no-op.

If the call would introduce a recursive binding, nil is returned. This represents an undefined context that cannot be evaluated. E.g., "x = [x]".

Binding a variable to some value also updates existing bindings to that variable.

TODO(tsandall): potential optimization:

The current implementation eagerly flattens the bindings by updating existing bindings each time a new binding is added. E.g., if Bind(y, [1,2,x]) and Bind(x, 3) are called (one after the other), the binding for "y" will be updated. It may be possible to defer this to a later stage, e.g., when plugging the values.

func (*Context) Binding

func (ctx *Context) Binding(k ast.Value) ast.Value

Binding returns the value bound to the given key.

func (*Context) Child

func (ctx *Context) Child(query ast.Body, locals *storage.Bindings) *Context

Child returns a new context to evaluate a query that was referenced by this context.

func (*Context) Current

func (ctx *Context) Current() *ast.Expr

Current returns the current expression to evaluate.

func (*Context) Step

func (ctx *Context) Step() *Context

Step returns a new context to evaluate the next expression.

type Error

type Error struct {
	Code    int
	Message string
}

Error is the error type returned by the Eval and Query functions when an evaluation error occurs.

func (*Error) Error

func (e *Error) Error() string

type Iterator

type Iterator func(*Context) error

Iterator is the interface for processing contexts.

type QueryParams

type QueryParams struct {
	DataStore *storage.DataStore
	Globals   *storage.Bindings
	Tracer    Tracer
	Path      []interface{}
}

QueryParams defines input parameters for the query interface.

func NewQueryParams

func NewQueryParams(ds *storage.DataStore, globals *storage.Bindings, path []interface{}) (q *QueryParams)

NewQueryParams returns a new QueryParams q.

type StdoutTracer

type StdoutTracer struct{}

StdoutTracer writes trace messages to stdout.

func (*StdoutTracer) Enabled

func (t *StdoutTracer) Enabled() bool

Enabled always returns true.

func (*StdoutTracer) Trace

func (t *StdoutTracer) Trace(ctx *Context, f string, a ...interface{})

Trace writes a trace message to stdout.

type Tracer

type Tracer interface {

	// Enabled returns true if the tracer is enabled.
	Enabled() bool

	// Trace emits a message if the tracer is enabled.
	Trace(ctx *Context, f string, a ...interface{})
}

Tracer defines the interface for tracing evaluation.

type Undefined

type Undefined struct{}

Undefined represents the absence of bindings that satisfy a completely defined rule. See the documentation for Query for more details.

func (Undefined) String

func (undefined Undefined) String() string