topdown

package
v0.2.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 1, 2016 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Overview

Package topdown provides query evaluation support.

The topdown implementation is a (slightly modified) version of the standard "top-down evaluation" algorithm used in query languages such as Datalog. The main difference in the implementation is in the handling of Rego references.

At a high level, the topdown implementation consists of (1) term evaluation and (2) expression evaluation. Term evaluation involves handling expression terms in isolation whereas expression evaluation involves evaluating the terms in relation to each other.

During the term evaluation phase, the topdown implementation will evaluate references found in the expression to produce bindings for:

  1. Variables appearing in references
  2. References to Virtual Documents
  3. Comprehensions

Once terms have been evaluated in isolation, the overall expression can be evaluated. If the expression is simply a term (e.g., string, reference, variable, etc.) then it is compared against the boolean "false" value. If the value IS NOT "false", evaluation continues. On the other hand, if the expression is defined by a built-in operator (e.g., =, !=, min, max, etc.) then the appropriate built-in function is invoked to determine if evaluation continues and bind variables accordingly.

Index

Examples

Constants

View Source 
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

	// TypeErr indicates evaluation stopped because an expression was applied to
	// a value of an inappropriate type.
	TypeErr = iota
)

Variables

This section is empty.

Functions

func Continue 

func Continue(ctx *Context, key, value ast.Value, iter Iterator) error

Continue binds the key to the value in the current context and invokes the iterator. This is a helper function for simple cases where a single value (e.g., a variable) needs to be bound to a value in order for the evaluation the proceed.

func ContinueN 

func ContinueN(ctx *Context, iter Iterator, x ...ast.Value) error

ContinueN binds N keys to N values. The key/value pairs are passed in as alternating pairs, e.g., key-1, value-1, key-2, value-2, ..., key-N, value-N.

func Eval 

func Eval(ctx *Context, iter Iterator) error

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

Example 
package main

import (
	"encoding/json"
	"fmt"

	"github.com/open-policy-agent/opa/ast"
	"github.com/open-policy-agent/opa/storage"
	"github.com/open-policy-agent/opa/topdown"
)

func main() {

	compiler := ast.NewCompiler()

	// Define a dummy query and some data that the query will execute against.
	query, err := compiler.QueryCompiler().Compile(ast.MustParseBody("data.a[_] = x, x >= 2"))
	if err != nil {
		// Handle error.
	}

	var data map[string]interface{}

	if err := json.Unmarshal([]byte(`{"a": [1,2,3,4]}`), &data); err != nil {
		// Handle error.
	}

	// Instantiate the policy engine's storage layer.
	store := storage.New(storage.InMemoryWithJSONConfig(data))

	// Create a new transaction. Transactions allow the policy engine to
	// evaluate the query over a consistent snapshot fo the storage layer.
	txn, err := store.NewTransaction()
	if err != nil {
		// Handle error.
	}

	defer store.Close(txn)

	// Prepare the evaluation parameters. Evaluation executes against the policy engine's
	// storage. In this case, we seed the storage with a single array of number. Other parameters
	// such as globals, tracing configuration, etc. can be set on the context. See the Context
	// documentation for more details.
	ctx := topdown.NewContext(query, compiler, store, txn)

	result := []interface{}{}

	// Execute the query and provide a callbakc function to accumulate the results.
	err = topdown.Eval(ctx, func(ctx *topdown.Context) error {

		// Each variable in the query will have an associated "binding" in the context.
		x := ctx.Binding(ast.Var("x"))

		// The bindings are ast.Value types so we will convert to a native Go value here.
		v, err := topdown.ValueToInterface(x, ctx)
		if err != nil {
			return err
		}

		result = append(result, v)
		return nil
	})

	// Inspect the query result.
	fmt.Println("result:", result)
	fmt.Println("err:", err)

}

Output:

result: [2 3 4]
err: <nil>

func IsUnboundGlobal 

func IsUnboundGlobal(e error) bool

IsUnboundGlobal returns true if the error e is an UnboundGlobalErr

func MakeGlobals added in v0.2.1 

func MakeGlobals(pairs [][2]*ast.Term) (*ast.ValueMap, error)

MakeGlobals returns a globals mapping for the given key-value pairs.

func PlugExpr 

func PlugExpr(expr *ast.Expr, binding Binding) *ast.Expr

PlugExpr returns a copy of expr with bound terms substituted for the binding.

func PlugHead added in v0.2.0 

func PlugHead(head *ast.Head, binding Binding) *ast.Head

PlugHead returns a copy of head with bound terms substituted for the binding.

func PlugTerm 

func PlugTerm(term *ast.Term, binding Binding) *ast.Term

PlugTerm returns a copy of term with bound terms substituted for the binding.

func PlugValue 

func PlugValue(v ast.Value, binding func(ast.Value) ast.Value) ast.Value

PlugValue returns a copy of v with bound terms substituted for the binding.

func PrettyTrace added in v0.2.0 

func PrettyTrace(w io.Writer, trace []*Event)

PrettyTrace pretty prints the trace to the writer.

func RegisterBuiltinFunc 

func RegisterBuiltinFunc(name ast.Var, fun BuiltinFunc)

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

func ResetQueryIDs added in v0.2.0 

func ResetQueryIDs()

ResetQueryIDs resets the query ID generator. This is only for test purposes.

func ResolveRefs added in v0.2.0 

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

ResolveRefs returns the AST value obtained by resolving references to base documents.

func ValueToFloat64 

func ValueToFloat64(v ast.Value, resolver Resolver) (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 ValueToInt added in v0.2.1 

func ValueToInt(v ast.Value, resolver Resolver) (int64, error)

ValueToInt 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, resolver Resolver) (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, resolver Resolver) ([]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, resolver Resolver) (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.

func ValueToStrings added in v0.2.0 

func ValueToStrings(v ast.Value, resolver Resolver) ([]string, error)

ValueToStrings returns a slice of strings associated with an AST value.

Types

type Binding added in v0.2.0 

type Binding func(ast.Value) ast.Value

Binding defines the interface used to apply term bindings to terms, expressions, etc.

type BufferTracer added in v0.2.0 

type BufferTracer []*Event

BufferTracer implements the Tracer interface by simply buffering all events received.

func NewBufferTracer added in v0.2.0 

func NewBufferTracer() *BufferTracer

NewBufferTracer returns a new BufferTracer.

func (*BufferTracer) Enabled added in v0.2.0 

func (b *BufferTracer) Enabled() bool

Enabled always returns true.

func (*BufferTracer) Trace added in v0.2.0 

func (b *BufferTracer) Trace(ctx *Context, evt *Event)

Trace adds the event to the buffer.

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
	Compiler *ast.Compiler
	Globals  *ast.ValueMap
	Locals   *ast.ValueMap
	Index    int
	Previous *Context
	Store    *storage.Storage
	Tracer   Tracer
	// contains filtered or unexported fields
}

Context contains the state of the evaluation process.

func NewContext 

func NewContext(query ast.Body, compiler *ast.Compiler, store *storage.Storage, txn storage.Transaction) *Context

NewContext creates a new Context with no bindings.

func (*Context) Bind 

func (ctx *Context) Bind(key ast.Value, value ast.Value, prev *Undo) *Undo

Bind updates the context to include a binding from the key to the value. The return value is used to return the context to the state before the binding was added.

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 *ast.ValueMap) *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) Resolve added in v0.2.1 

func (ctx *Context) Resolve(ref ast.Ref) (interface{}, error)

Resolve returns the native Go value referred to by the ref.

func (*Context) Step 

func (ctx *Context) Step() *Context

Step returns a new context to evaluate the next expression.

func (*Context) Unbind 

func (ctx *Context) Unbind(undo *Undo)

Unbind updates the context by removing the binding represented by the undo.

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 Event added in v0.2.0 

type Event struct {
	Op       Op            // Identifies type of event.
	Node     interface{}   // Contains AST node relevant to the event.
	QueryID  uint64        // Identifies the query this event belongs to.
	ParentID uint64        // Identifies the parent query this event belongs to.
	Locals   *ast.ValueMap // Contains local variable bindings from the query context.
}

Event contains state associated with a tracing event.

func (*Event) Equal added in v0.2.0 

func (evt *Event) Equal(other *Event) bool

Equal returns true if this event is equal to the other event.

func (*Event) HasBody added in v0.2.0 

func (evt *Event) HasBody() bool

HasBody returns true if the Event contains an ast.Body.

func (*Event) HasExpr added in v0.2.0 

func (evt *Event) HasExpr() bool

HasExpr returns true if the Event contains an ast.Expr.

func (*Event) HasRule added in v0.2.0 

func (evt *Event) HasRule() bool

HasRule returns true if the Event contains an ast.Rule.

func (*Event) String added in v0.2.0 

func (evt *Event) String() string

type Iterator 

type Iterator func(*Context) error

Iterator is the interface for processing contexts.

type Op added in v0.2.0 

type Op string

Op defines the types of tracing events. 

const (
	// EnterOp is emitted when a new query is about to be evaluated.
	EnterOp Op = "Enter"

	// ExitOp is emitted when a query has evaluated to true.
	ExitOp Op = "Exit"

	// EvalOp is emitted when an expression is about to be evaluated.
	EvalOp Op = "Eval"

	// RedoOp is emitted when an expression, rule, or query is being re-evaluated.
	RedoOp Op = "Redo"

	// FailOp is emitted when an expression evaluates to false.
	FailOp Op = "Fail"
)

type QueryParams 

type QueryParams struct {
	Compiler    *ast.Compiler
	Store       *storage.Storage
	Transaction storage.Transaction
	Globals     *ast.ValueMap
	Tracer      Tracer
	Path        ast.Ref
}

QueryParams defines input parameters for the query interface.

func NewQueryParams 

func NewQueryParams(compiler *ast.Compiler, store *storage.Storage, txn storage.Transaction, globals *ast.ValueMap, path ast.Ref) *QueryParams

NewQueryParams returns a new QueryParams.

func (*QueryParams) NewContext added in v0.2.0 

func (q *QueryParams) NewContext(body ast.Body) *Context

NewContext returns a new Context that can be used to do evaluation.

type QueryResult added in v0.2.1 

type QueryResult struct {
	Result  interface{}            // Result contains the document referred to by the params Path.
	Globals map[string]interface{} // Globals contains bindings for variables in the params Globals.
}

QueryResult represents a single query result.

func (*QueryResult) String added in v0.2.1 

func (qr *QueryResult) String() string

type QueryResultSet added in v0.2.1 

type QueryResultSet []*QueryResult

QueryResultSet represents a collection of query results.

func Query 

func Query(params *QueryParams) (QueryResultSet, error)

Query returns the value of document referred to by the params Path field. If the params Globals field contains values that are non-ground (i.e., they contain variables), then the result may contain multiple entries.

Example 
package main

import (
	"fmt"

	"github.com/open-policy-agent/opa/ast"
	"github.com/open-policy-agent/opa/storage"
	"github.com/open-policy-agent/opa/topdown"
)

func main() {

	compiler := ast.NewCompiler()

	// Define a dummy module with rules that produce documents that we will query below.
	module, err := ast.ParseModule("my_module.rego", `

	    package opa.example

	    p[x] :- q[x], not r[x]
	    q[y] :- a = [1,2,3], y = a[_]
	    r[z] :- b = [2,4], z = b[_]

	`)

	mods := map[string]*ast.Module{
		"my_module": module,
	}

	if compiler.Compile(mods); compiler.Failed() {
		fmt.Println(compiler.Errors)
	}

	if err != nil {
		// Handle error.
	}

	// Instantiate the policy engine's storage layer.
	store := storage.New(storage.InMemoryConfig())

	// Create a new transaction. Transactions allow the policy engine to
	// evaluate the query over a consistent snapshot fo the storage layer.
	txn, err := store.NewTransaction()
	if err != nil {
		// Handle error.
	}

	defer store.Close(txn)

	// Prepare the query parameters. Queries execute against the policy engine's storage and can
	// accept additional documents (which are referred to as "globals"). In this case we have no
	// additional documents.
	globals := ast.NewValueMap()
	params := topdown.NewQueryParams(compiler, store, txn, globals, ast.MustParseRef("data.opa.example.p"))

	// Execute the query against "p".
	v1, err1 := topdown.Query(params)

	// Inspect the result.
	fmt.Println("v1:", v1[0].Result)
	fmt.Println("err1:", err1)

}

Output:

v1: [1 3]
err1: <nil>

func (*QueryResultSet) Add added in v0.2.1 

func (qrs *QueryResultSet) Add(qr *QueryResult)

Add inserts a result into the query result set.

func (QueryResultSet) Undefined added in v0.2.1 

func (qrs QueryResultSet) Undefined() bool

Undefined returns true if the query did not find any results.

type Resolver added in v0.2.1 

type Resolver interface {
	Resolve(ref ast.Ref) (value interface{}, err error)
}

Resolver defines the interface for resolving references to base documents to native Go values. The native Go value types map to JSON types.

type Tracer 

type Tracer interface {
	Enabled() bool
	Trace(ctx *Context, evt *Event)
}

Tracer defines the interface for tracing in the top-down evaluation engine.

type Undo 

type Undo struct {
	Key   ast.Value
	Value ast.Value
	Prev  *Undo
}

Undo represents a binding that can be undone.

Source Files

View all Source files

Directories

Path Synopsis
Package explain contains utilities for post-processing traces emitted by the evaluation engine.
 Package explain contains utilities for post-processing traces emitted by the evaluation engine.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.