Hidden, unnecessary assumptions about the AST object iteration order

[koponen-styra]

The object key-value iteration order is (correctly) not specified anywhere in the object interface. The current implementation iterates the key-values in the insertion order and it seems moving away from the insertion order iteration may allow for potential performance improvements. However, the code base has unnecessary assumptions around the iteration order which tie the users of the object to its implementation.

Changing the iterator implementation per the patch below and re-running the go tests a few times (without result caching) is enough to shake out the problematic tests:

1. TestCompilerRewriteLocalAssignments/13
2. TestFormatSource
3. ExampleRego_Eval_multipleDocuments
4. TestNetCIDRContainsMatches/objects
5. TestTopDownWithKeyword/with_virtual_doc_exact_value

--- a/ast/term.go
+++ b/ast/term.go
@@ -1680,14 +1680,11 @@ func (obj *object) Intersect(other Object) [][3]*Term {
 // Iter calls the function f for each key-value pair in the object. If f
 // returns an error, iteration stops and the error is returned.
 func (obj *object) Iter(f func(*Term, *Term) error) error {
-       for i := range obj.keys {
-               k := obj.keys[i]
-               node := obj.get(k)
-               if node == nil {
-                       panic("corrupt object")
-               }
-               if err := f(k, node.value); err != nil {
-                       return err
+       for _, elem := range obj.elems {
+               for node := elem; node != nil; node = node.next {
+                       if err := f(node.key, node.value); err != nil {
+                               return err
+                       }
                }
        }

[koponen-styra]

The AST sets would benefit from similar treatment. With both objects and sets, removing the iteration order assumption opens the path towards removing the keys field within their implementation which will result in reduced memory usage, less memory allocations, and faster evaluation.

[tsandall]

We no longer sort keys based on insertion order, instead we're using Compare(). The reason for this was that Compare() used to sort the keys slice on sets and objects and that caused incorrect answers to be generated by topdown.

With #4028 we've removed the insertion ordering.

cc @srenatus

[philipaconrad]

@tsandall Do you think we can close this issue, since keys have been sorted on Objects for a while now?

[anderseknert]

@tsandall @koponen-styra @srenatus OK to close?