opa: github.com/open-policy-agent/opa/topdown Index | Examples | Files | Directories

package topdown

import "github.com/open-policy-agent/opa/topdown"

Package topdown provides low-level query evaluation support.

The topdown implementation is a modified version of the standard top-down evaluation algorithm used in Datalog. References and comprehensions are evaluated eagerly while all other terms are evaluated lazily.

Index

Examples

Package Files

aggregates.go arithmetic.go array.go binary.go bindings.go builtins.go cache.go cancel.go casts.go cidr.go comparison.go crypto.go doc.go encoding.go errors.go eval.go glob.go http.go input.go instrumentation.go parse.go query.go regex.go regex_template.go runtime.go save.go sets.go strings.go time.go tokens.go trace.go type.go type_name.go walk.go

Constants

const (

    // InternalErr represents an unknown evaluation error.
    InternalErr string = "eval_internal_error"

    // CancelErr indicates the evaluation process was cancelled.
    CancelErr string = "eval_cancel_error"

    // ConflictErr indicates a conflict was encountered during evaluation. For
    // instance, a conflict occurs if a rule produces multiple, differing values
    // for the same key in an object. Conflict errors indicate the policy does
    // not account for the data loaded into the policy engine.
    ConflictErr string = "eval_conflict_error"

    // TypeErr indicates evaluation stopped because an expression was applied to
    // a value of an inappropriate type.
    TypeErr string = "eval_type_error"

    // BuiltinErr indicates a built-in function received a semantically invalid
    // input or encountered some kind of runtime error, e.g., connection
    // timeout, connection refused, etc.
    BuiltinErr string = "eval_builtin_error"

    // WithMergeErr indicates that the real and replacement data could not be merged.
    WithMergeErr string = "eval_with_merge_error"
)

func IsCancel Uses

func IsCancel(err error) bool

IsCancel returns true if err was caused by cancellation.

func IsError Uses

func IsError(err error) bool

IsError returns true if the err is an Error.

func PrettyTrace Uses

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

PrettyTrace pretty prints the trace to the writer.

func RegisterBuiltinFunc Uses

func RegisterBuiltinFunc(name string, f BuiltinFunc)

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

func RegisterFunctionalBuiltin1 Uses

func RegisterFunctionalBuiltin1(name string, fun FunctionalBuiltin1)

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

Code:

// Rego includes a number of built-in functions ("built-ins") for performing
// standard operations like string manipulation, regular expression
// matching, and computing aggregates.
//
// This test shows how to add a new built-in to Rego and OPA.

// Initialize context for the example. Normally the caller would obtain the
// context from an input parameter or instantiate their own.
ctx := context.Background()

// The ast package contains a registry that enumerates the built-ins
// included in Rego. When adding a new built-in, you must update the
// registry to include your built-in. Otherwise, the compiler will complain
// when it encounters your built-in.
builtin := &ast.Builtin{
    Name: "mybuiltins.upper",
    Decl: types.NewFunction(
        types.Args(types.S),
        types.S,
    ),
}

ast.RegisterBuiltin(builtin)

// This is the implementation of the built-in that will be called during
// query evaluation.
builtinImpl := func(a ast.Value) (ast.Value, error) {

    str, err := builtins.StringOperand(a, 1)

    if err != nil {
        return nil, err
    }

    if str.Equal(ast.String("magic")) {
        // topdown.BuiltinEmpty indicates to the evaluation engine that the
        // expression is false/not defined.
        return nil, topdown.BuiltinEmpty{}
    }

    return ast.String(strings.ToUpper(string(str))), nil
}

// See documentation for registering functions that take different numbers
// of arguments.
topdown.RegisterFunctionalBuiltin1(builtin.Name, builtinImpl)

// At this point, the new built-in has been registered and can be used in
// queries. Our custom built-in converts strings to upper case but is not
// defined for the input "magic".
compiler := ast.NewCompiler()
query, err := compiler.QueryCompiler().Compile(ast.MustParseBody(`mybuiltins.upper("custom", x); not mybuiltins.upper("magic", "MAGIC")`))
if err != nil {
    // Handle error.
}

// Evaluate the query.
q := topdown.NewQuery(query).WithCompiler(compiler)

q.Iter(ctx, func(qr topdown.QueryResult) error {
    fmt.Println("x:", qr[ast.Var("x")])
    return nil
})

// If you add a new built-in function to OPA, you should:
//
// 1. Update the Language Reference: http://www.openpolicyagent.org/docs/language-reference.html.
// 2. Add an integration test to the topdown package.

Output:

x: "CUSTOM"

func RegisterFunctionalBuiltin2 Uses

func RegisterFunctionalBuiltin2(name string, fun FunctionalBuiltin2)

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

func RegisterFunctionalBuiltin3 Uses

func RegisterFunctionalBuiltin3(name string, fun FunctionalBuiltin3)

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

func RegisterFunctionalBuiltin4 Uses

func RegisterFunctionalBuiltin4(name string, fun FunctionalBuiltin4)

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

type BufferTracer Uses

type BufferTracer []*Event

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

func NewBufferTracer Uses

func NewBufferTracer() *BufferTracer

NewBufferTracer returns a new BufferTracer.

func (*BufferTracer) Enabled Uses

func (b *BufferTracer) Enabled() bool

Enabled always returns true if the BufferTracer is instantiated.

func (*BufferTracer) Trace Uses

func (b *BufferTracer) Trace(evt *Event)

Trace adds the event to the buffer.

type BuiltinContext Uses

type BuiltinContext struct {
    Runtime  *ast.Term      // runtime information on the OPA instance
    Cache    builtins.Cache // built-in function state cache
    Location *ast.Location  // location of built-in call
    Tracers  []Tracer       // tracer objects for trace() built-in function
    QueryID  uint64         // identifies query being evaluated
    ParentID uint64         // identifies parent of query being evaluated
}

BuiltinContext contains context from the evaluator that may be used by built-in functions.

type BuiltinEmpty Uses

type BuiltinEmpty struct{}

BuiltinEmpty is used to signal that the built-in function evaluated, but the result is undefined so evaluation should not continue.

func (BuiltinEmpty) Error Uses

func (BuiltinEmpty) Error() string

type BuiltinFunc Uses

type BuiltinFunc func(bctx BuiltinContext, operands []*ast.Term, iter func(*ast.Term) error) error

BuiltinFunc defines an interface for implementing built-in functions. The built-in function is called with the plugged operands from the call (including the output operands.) The implementation should evaluate the operands and invoke the iteraror for each successful/defined output value.

type Cancel Uses

type Cancel interface {
    Cancel()
    Cancelled() bool
}

Cancel defines the interface for cancelling topdown queries. Cancel operations are thread-safe and idempotent.

func NewCancel Uses

func NewCancel() Cancel

NewCancel returns a new Cancel object.

type Error Uses

type Error struct {
    Code     string        `json:"code"`
    Message  string        `json:"message"`
    Location *ast.Location `json:"location,omitempty"`
}

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

func (*Error) Error Uses

func (e *Error) Error() string

type Event Uses

type Event struct {
    Op       Op            // Identifies type of event.
    Node     ast.Node      // 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.
    Message  string        // Contains message for Note events.
}

Event contains state associated with a tracing event.

func (*Event) Equal Uses

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

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

func (*Event) HasBody Uses

func (evt *Event) HasBody() bool

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

func (*Event) HasExpr Uses

func (evt *Event) HasExpr() bool

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

func (*Event) HasRule Uses

func (evt *Event) HasRule() bool

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

func (*Event) String Uses

func (evt *Event) String() string

type FunctionalBuiltin1 Uses

type FunctionalBuiltin1 func(op1 ast.Value) (output ast.Value, err error)

FunctionalBuiltin1 defines an interface for simple functional built-ins.

Implement this interface if your built-in function takes one input and produces one output.

If an error occurs, the functional built-in should return a descriptive message. The message should not be prefixed with the built-in name as the framework takes care of this.

type FunctionalBuiltin2 Uses

type FunctionalBuiltin2 func(op1, op2 ast.Value) (output ast.Value, err error)

FunctionalBuiltin2 defines an interface for simple functional built-ins.

Implement this interface if your built-in function takes two inputs and produces one output.

If an error occurs, the functional built-in should return a descriptive message. The message should not be prefixed with the built-in name as the framework takes care of this.

type FunctionalBuiltin3 Uses

type FunctionalBuiltin3 func(op1, op2, op3 ast.Value) (output ast.Value, err error)

FunctionalBuiltin3 defines an interface for simple functional built-ins.

Implement this interface if your built-in function takes three inputs and produces one output.

If an error occurs, the functional built-in should return a descriptive message. The message should not be prefixed with the built-in name as the framework takes care of this.

type FunctionalBuiltin4 Uses

type FunctionalBuiltin4 func(op1, op2, op3, op4 ast.Value) (output ast.Value, err error)

FunctionalBuiltin4 defines an interface for simple functional built-ins.

Implement this interface if your built-in function takes four inputs and produces one output.

If an error occurs, the functional built-in should return a descriptive message. The message should not be prefixed with the built-in name as the framework takes care of this.

type Instrumentation Uses

type Instrumentation struct {
    // contains filtered or unexported fields
}

Instrumentation implements helper functions to instrument query evaluation to diagnose performance issues. Instrumentation may be expensive in some cases, so it is disabled by default.

func NewInstrumentation Uses

func NewInstrumentation(m metrics.Metrics) *Instrumentation

NewInstrumentation returns a new Instrumentation object. Performance diagnostics recorded on this Instrumentation object will stored in m.

type JSONWebToken Uses

type JSONWebToken struct {
    // contains filtered or unexported fields
}

JSONWebToken represent the 3 parts (header, payload & signature) of

a JWT in Base64.

type Op Uses

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"

    // SaveOp is emitted when an expression is saved instead of evaluated
    // during partial evaluation.
    SaveOp Op  = "Save"

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

    // NoteOp is emitted when an expression invokes a tracing built-in function.
    NoteOp Op  = "Note"

    // IndexOp is emitted during an expression evaluation to represent lookup
    // matches.
    IndexOp Op  = "Index"
)

type Query Uses

type Query struct {
    // contains filtered or unexported fields
}

Query provides a configurable interface for performing query evaluation.

func NewQuery Uses

func NewQuery(query ast.Body) *Query

NewQuery returns a new Query object that can be run.

func (*Query) Iter Uses

func (q *Query) Iter(ctx context.Context, iter func(QueryResult) error) error

Iter executes the query and invokes the iter function with query results produced by evaluating the query.

Code:

// Initialize context for the example. Normally the caller would obtain the
// context from an input parameter or instantiate their own.
ctx := context.Background()

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{}

// OPA uses Go's standard JSON library but assumes that numbers have been
// decoded as json.Number instead of float64. You MUST decode with UseNumber
// enabled.
decoder := json.NewDecoder(bytes.NewBufferString(`{"a": [1,2,3,4]}`))
decoder.UseNumber()

if err := decoder.Decode(&data); err != nil {
    // Handle error.
}

// Instantiate the policy engine's storage layer.
store := inmem.NewFromObject(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(ctx)
if err != nil {
    // Handle error.
}

defer store.Abort(ctx, 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 the input, tracing configuration,
// etc. can be set on the query object.
q := topdown.NewQuery(query).
    WithCompiler(compiler).
    WithStore(store).
    WithTransaction(txn)

result := []interface{}{}

// Execute the query and provide a callback function to accumulate the results.
err = q.Iter(ctx, func(qr topdown.QueryResult) error {

    // Each variable in the query will have an associated binding.
    x := qr[ast.Var("x")]

    // The bindings are ast.Value types so we will convert to a native Go value here.
    v, err := ast.JSON(x.Value)
    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 (*Query) PartialRun Uses

func (q *Query) PartialRun(ctx context.Context) (partials []ast.Body, support []*ast.Module, err error)

PartialRun executes partial evaluation on the query with respect to unknown values. Partial evaluation attempts to evaluate as much of the query as possible without requiring values for the unknowns set on the query. The result of partial evaluation is a new set of queries that can be evaluated once the unknown value is known. In addition to new queries, partial evaluation may produce additional support modules that should be used in conjunction with the partially evaluated queries.

Code:

// Initialize context for the example. Normally the caller would obtain the
// context from an input parameter or instantiate their own.
ctx := context.Background()

var data map[string]interface{}
decoder := json.NewDecoder(bytes.NewBufferString(`{
		"roles": [
			{
				"permissions": ["read_bucket"],
				"groups": ["dev", "test", "sre"]
			},
			{
				"permissions": ["write_bucket", "delete_bucket"],
				"groups": ["sre"]
			}
		]
	}`))
if err := decoder.Decode(&data); err != nil {
    // Handle error.
}

// Instantiate the policy engine's storage layer.
store := inmem.NewFromObject(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(ctx)
if err != nil {
    // Handle error.
}

defer store.Abort(ctx, txn)

// Define policy that searches for roles that match input request. If no
// roles are found, allow is undefined and the caller will reject the
// request. This is the user supplied policy that OPA will partially
// evaluate.
modules := map[string]*ast.Module{
    "authz.rego": ast.MustParseModule(`
			package example

			default allow = false

			allow {
				role = data.roles[i]
				input.group = role.groups[j]
				input.permission = role.permissions[k]
			}
		`),
}

// Compile policy.
compiler := ast.NewCompiler()
if compiler.Compile(modules); compiler.Failed() {
    // Handle error.
}

// Construct query and mark the entire input document as partial.
q := topdown.NewQuery(ast.MustParseBody("data.example.allow = true")).
    WithCompiler(compiler).
    WithUnknowns([]*ast.Term{
        ast.MustParseTerm("input"),
    }).
    WithStore(store).
    WithTransaction(txn)

// Execute partial evaluation.
partial, _, err := q.PartialRun(ctx)
if err != nil {
    // Handle error.
}

// Show result of partially evaluating the policy.
fmt.Printf("# partial evaluation result (%d items):\n", len(partial))
for i := range partial {
    fmt.Println(partial[i])
}

// Construct a new policy to contain the result of partial evaluation.
module := ast.MustParseModule("package partial")

for i := range partial {
    rule := &ast.Rule{
        Head: &ast.Head{
            Name:  ast.Var("allow"),
            Value: ast.BooleanTerm(true),
        },
        Body:   partial[i],
        Module: module,
    }
    module.Rules = append(module.Rules, rule)
}

// Compile the partially evaluated policy with the original policy.
modules["partial"] = module

if compiler.Compile(modules); compiler.Failed() {
    // Handle error.
}

// Test different inputs against partially evaluated policy.
inputs := []string{
    `{"group": "dev", "permission": "read_bucket"}`,  // allow
    `{"group": "dev", "permission": "write_bucket"}`, // deny
    `{"group": "sre", "permission": "write_bucket"}`, // allow
}

fmt.Println()
fmt.Println("# evaluation results:")

for i := range inputs {

    // Query partially evaluated policy.
    q = topdown.NewQuery(ast.MustParseBody("data.partial.allow = true")).
        WithCompiler(compiler).
        WithStore(store).
        WithTransaction(txn).
        WithInput(ast.MustParseTerm(inputs[i]))

    qrs, err := q.Run(ctx)
    if err != nil {
        // Handle error.
    }

    // Check if input is allowed.
    allowed := len(qrs) == 1

    fmt.Printf("input %d allowed: %v\n", i+1, allowed)
}

Output:

# partial evaluation result (5 items):
"dev" = input.group; "read_bucket" = input.permission
"test" = input.group; "read_bucket" = input.permission
"sre" = input.group; "read_bucket" = input.permission
"sre" = input.group; "write_bucket" = input.permission
"sre" = input.group; "delete_bucket" = input.permission

# evaluation results:
input 1 allowed: true
input 2 allowed: false
input 3 allowed: true

func (*Query) Run Uses

func (q *Query) Run(ctx context.Context) (QueryResultSet, error)

Run is a wrapper around Iter that accumulates query results and returns them in one shot.

Code:

// Initialize context for the example. Normally the caller would obtain the
// context from an input parameter or instantiate their own.
ctx := context.Background()

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{}

// OPA uses Go's standard JSON library but assumes that numbers have been
// decoded as json.Number instead of float64. You MUST decode with UseNumber
// enabled.
decoder := json.NewDecoder(bytes.NewBufferString(`{"a": [1,2,3,4]}`))
decoder.UseNumber()

if err := decoder.Decode(&data); err != nil {
    // Handle error.
}

// Instantiate the policy engine's storage layer.
store := inmem.NewFromObject(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(ctx)
if err != nil {
    // Handle error.
}

defer store.Abort(ctx, 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 the input, tracing configuration,
// etc. can be set on the query object.
q := topdown.NewQuery(query).
    WithCompiler(compiler).
    WithStore(store).
    WithTransaction(txn)

rs, err := q.Run(ctx)

// Inspect the query result set.
fmt.Println("len:", len(rs))
for i := range rs {
    fmt.Printf("rs[%d][\"x\"]: %v\n", i, rs[i]["x"])
}
fmt.Println("err:", err)

Output:

len: 3
rs[0]["x"]: 2
rs[1]["x"]: 3
rs[2]["x"]: 4
err: <nil>

func (*Query) WithCancel Uses

func (q *Query) WithCancel(cancel Cancel) *Query

WithCancel sets the cancellation object to use for the query. Set this if you need to abort queries based on a deadline. This is optional.

func (*Query) WithCompiler Uses

func (q *Query) WithCompiler(compiler *ast.Compiler) *Query

WithCompiler sets the compiler to use for the query.

func (*Query) WithInput Uses

func (q *Query) WithInput(input *ast.Term) *Query

WithInput sets the input object to use for the query. References rooted at input will be evaluated against this value. This is optional.

func (*Query) WithInstrumentation Uses

func (q *Query) WithInstrumentation(instr *Instrumentation) *Query

WithInstrumentation sets the instrumentation configuration to enable on the evaluation process. By default, instrumentation is turned off.

func (*Query) WithMetrics Uses

func (q *Query) WithMetrics(m metrics.Metrics) *Query

WithMetrics sets the metrics collection to add evaluation metrics to. This is optional.

func (*Query) WithPartialNamespace Uses

func (q *Query) WithPartialNamespace(ns string) *Query

WithPartialNamespace sets the namespace to use for supporting rules generated as part of the partial evaluation process. The ns value must be a valid package path component.

func (*Query) WithRuntime Uses

func (q *Query) WithRuntime(runtime *ast.Term) *Query

WithRuntime sets the runtime data to execute the query with. The runtime data can be returned by the `opa.runtime` built-in function.

func (*Query) WithStore Uses

func (q *Query) WithStore(store storage.Store) *Query

WithStore sets the store to use for the query.

func (*Query) WithTracer Uses

func (q *Query) WithTracer(tracer Tracer) *Query

WithTracer adds a query tracer to use during evaluation. This is optional.

func (*Query) WithTransaction Uses

func (q *Query) WithTransaction(txn storage.Transaction) *Query

WithTransaction sets the transaction to use for the query. All queries should be performed over a consistent snapshot of the storage layer.

func (*Query) WithUnknowns Uses

func (q *Query) WithUnknowns(terms []*ast.Term) *Query

WithUnknowns sets the initial set of variables or references to treat as unknown during query evaluation. This is required for partial evaluation.

type QueryResult Uses

type QueryResult map[ast.Var]*ast.Term

QueryResult represents a single result returned by a query. The result contains bindings for all variables that appear in the query.

type QueryResultSet Uses

type QueryResultSet []QueryResult

QueryResultSet represents a collection of results returned by a query.

type Tracer Uses

type Tracer interface {
    Enabled() bool
    Trace(*Event)
}

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

Directories

PathSynopsis
builtinsPackage builtins contains utilities for implementing built-in functions.
copypropagation
notes

Package topdown imports 40 packages (graph) and is imported by 32 packages. Updated 2019-05-16. Refresh now. Tools for package owners.