Term evaluation was not plugging the expression before checking if the indexer
could be used. As a result, the index was being built on the unplugged version
of the expression which resulted in false positives being returned by the
indexer. Because the evaluation expects the indexer to provide exact matches,
the query evaluation was yielding false positives.
Also, made a slight tweak to the docs to make the example slightly clearer.
- Basic compiler framework with a few steps to resolve references
- Extend runtime to support loading policies
- Update evaluation to deal with resolved references
* Store calls (e.g., Patch, Get) expect paths. It's assumed that the path
has had the "data" prefix removed.
* The top level query interface expects paths so the "data" prefix is
added before calling into the actual TopDown implementation.
* The head of a reference can be used to determine whether it refers to a
local variable or a document in the db.
* Updates to misc. test helpers to preserve existing structure. Implicitly
import top-level documents, rename local variables to avoid conflicts,
etc.
- Refactor reference evaluation
* Remove special casing around first reference term.
This was what prevented embedded virtual doc references from working
immediately. Previously, the code assumed that the first term in the
reference identified the virtual doc/rule. This was an over simplification
that worked while the initial implementation was in progress. Now that
modules are supported, virtual docs/rules may be embedded at arbitrary
depths, e.g., "data.a.b.c[i].d[j]" where "c" is the rule name and
"a.b" is the package containing the rule.
* Break up the reference valuation into smaller functions.
* Reorder ref/path arguments
* Rename path/ref to path/tail respectively
- Separate test case for embedded virtual docs.
Also, a few misc. changes:
- Fix Ref.String() in empty case.
- Refactor hashMap into separate package.
- Get rid of ad-hoc FNV implementation. Use the one from the stdlib!
- Refactored parsing helpers from eval into ast
Non-ground references are lazily indexed during evaluation if they are
contained in an equality expression where the other side is ground (or ground
after plugging the current bindings).
Updates to data that is indexed cause the built index to be dropped from the
indices.
The indexing supports exact match, reverse lookup using the ground value in
the expression. The result of the lookup is a set of bindings that when
plugged into the reference, result in the equality evaluating to true. In
this way, the indexing is not "lossy", i.e., it does not produce false matches
(positive or negative).
These were accidentally added with the liner and termtables dependencies. They
do not appear to be needed. However, "go get github.com/open-policy-agent/opa"
fails because "git submodule init ..." is run and this fails to find the
.gitmodules file it expects.
1. Refs to rules that produce set or object docs were not being handled
correctly when the key value was a variable that had an existing binding. The
term evaluation code must check the bindings for variables it encounters while
processing references.
2. Refs to vars were not being handled correctly when the ref contained
variables that had existing bindings. This issue was similar to (1).
3. Refs to vars bound to arrays or objects with invalid indices/keys (e.g.,
out of range) were causing evaluation to panic. Invalid indices/keys are
now treated as undefined.
4. Header field composition wasn't taking objects and arrays into account.
5. An equality expr with vars on both sides will eval to true and the vars will
be unified. However, if this was the last expression in the body, the vars are
still non-ground and so the proof should not be considered successful.
6. Move traceSuccess call into evalExpr. This way it will be applied for all
built-ins automatically.
7. Address comments from PR #27:
- Rename isDefined to isTrue in evalContextNegated
- Add comment about substituting variables in partial set/object evaluation
- Add test cases involving multiple virtual docs and subsitution
- Introduced new run command that lets users start an instance of OPA.
- Added basic REPL as first mode that can be run, server mode coming soon.
- Extended Storage to support a JSON Patch like interface.
Emit messages for four main steps of the evaluation process:
1. new expression (eval)
2. trying to evaluate a plugged expression (try)
3. successfully evaluated a plugged expression (success)
4. finished evaluating a query (finish)
Also refactored query interface slightly to take a params struct. This will be
a bit more future proof.
- Refactored TopDownContext to contain a slice of expressions instead of a
rule. This will allow the TopDown algorithm to be readily used for ad-hoc
expressions.
- Refactored test cases to avoid duplicating test logic.
These changes extend the reference evaluation to support virtual docs, i.e.,
rules that reference other rules. The reference evaluation is extended so that
references to rules are evaluated and then the bindings are updated to map the
original reference to the output of the referenced rule (aka, the virtual
document).
Additional changes:
- Added support for references against variables.
- Added hashMap to store bindings. This is required because bindings can now
be variables or references.
- Added Query helper on Array and Object AST types.
Addressed comments from initial PR:
- Comments for future optimization
- Additional test cases
- Removed unnecessary branch from evalEqUnifyArrayRef
- Fixed evaluation of non-ground refs embedded inside objects/arrays.
- Renamed document kind enumeration values
This is the initial implementation of the top down evaluation algorithm. It
has not be optimized at all and there are a few features that are still not
implemented.
The initial implementation handles:
- Evaluation of rules that produce object, set, and scalar documents.
- Equality built-in that unifies variables found in the operands.
- Basic helper modules (storage.go and compare.go) to assist evaluation.
This initial implementation does not include:
- Any type of tracing
- Negation
- Disjunction
- References against virtual documents or variables (i.e., only storage)
- Added expressions, packages, imports, rules, and modules to grammar
- Added support for comments
- Added a few failure cases to strings, arrays, and objects
- Added IsGround interface to terms
The special iterator variable ("_") is not supported yet. The _ variable will
be handled by mangling the variable name while parsing the rules (which are
still to come).
Also refactored terms to use type declaration and type switches. All terms are
now represented by underlying Go types without relying on extra structs. The
Kind attribute on Term has been removed in favour of type switches.
Lastly, removing the generated parser from the repository for now. Once the
grammar has stabilized, we can add the generated code back. The diffs were
unpleasant.
This change set also includes a bit of refactoring:
- Renamed jsonlog to opalog
- Renamed Dictionary to Object
- Split AST into separate files
- Tweaked parser definition to separate terms with whitespace
- Renamed helper functions in parser_test.go to distinguish from cases
- Moved reflection helper into test suite and renamed
- Modified Term.String() to make output more readable
- Reorganized the grammar file
- Allow scalars and variables as object keys. We will deal with this when
serializing to JSON.
- Updated source code layout to use standard Go project structure.
- Makefile for build and test execution.
- Glide for dependency management.
- Integrated spf13/cobra for command line entry point.
- Added docs on release and development process.
The main changes are:
Removed the overloading of the equality operator to do set membership tests
and updated set generation syntax to align with the new membership test
syntax.
Also, got rid of the "[]" syntax in references and replaced with special "_"
character that is treated as a special iterator. Documented this behaviour in
the references section.
Also, fixed semantics so that document content is defined in terms of the rule
head which is in turn defined by instances of the body that evaluate to true.
E.g., instead of "p :- 7", we now write "p = 7", which is short for "p = 7 :-
true".
Torin Sandall