3 files changed, 134 insertions, 0 deletions
diff --git a/vendor/github.com/authzed/spicedb/pkg/graph/doc.go b/vendor/github.com/authzed/spicedb/pkg/graph/doc.go
new file mode 100644
index 0000000..d632bc5
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/pkg/graph/doc.go
@@ -0,0 +1,2 @@
+// Package graph contains helper code to traverse a schema.
+package graph
diff --git a/vendor/github.com/authzed/spicedb/pkg/graph/tree.go b/vendor/github.com/authzed/spicedb/pkg/graph/tree.go
new file mode 100644
index 0000000..f8fae34
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/pkg/graph/tree.go
@@ -0,0 +1,61 @@
+package graph
+
+import (
+	core "github.com/authzed/spicedb/pkg/proto/core/v1"
+	"github.com/authzed/spicedb/pkg/tuple"
+)
+
+// Leaf constructs a RelationTupleTreeNode leaf.
+func Leaf(start *tuple.ObjectAndRelation, subjects ...*core.DirectSubject) *core.RelationTupleTreeNode {
+	var startONR *core.ObjectAndRelation
+	if start != nil {
+		startONR = start.ToCoreONR()
+	}
+
+	return &core.RelationTupleTreeNode{
+		NodeType: &core.RelationTupleTreeNode_LeafNode{
+			LeafNode: &core.DirectSubjects{
+				Subjects: subjects,
+			},
+		},
+		Expanded:         startONR,
+		CaveatExpression: nil, // Set by caller if necessary
+	}
+}
+
+func setResult(
+	op core.SetOperationUserset_Operation,
+	start *tuple.ObjectAndRelation,
+	children []*core.RelationTupleTreeNode,
+) *core.RelationTupleTreeNode {
+	var startONR *core.ObjectAndRelation
+	if start != nil {
+		startONR = start.ToCoreONR()
+	}
+
+	return &core.RelationTupleTreeNode{
+		NodeType: &core.RelationTupleTreeNode_IntermediateNode{
+			IntermediateNode: &core.SetOperationUserset{
+				Operation:  op,
+				ChildNodes: children,
+			},
+		},
+		Expanded:         startONR,
+		CaveatExpression: nil, // Set by caller if necessary
+	}
+}
+
+// Union constructs a RelationTupleTreeNode union operation.
+func Union(start *tuple.ObjectAndRelation, children ...*core.RelationTupleTreeNode) *core.RelationTupleTreeNode {
+	return setResult(core.SetOperationUserset_UNION, start, children)
+}
+
+// Intersection constructs a RelationTupleTreeNode intersection operation.
+func Intersection(start *tuple.ObjectAndRelation, children ...*core.RelationTupleTreeNode) *core.RelationTupleTreeNode {
+	return setResult(core.SetOperationUserset_INTERSECTION, start, children)
+}
+
+// Exclusion constructs a RelationTupleTreeNode exclusion operation.
+func Exclusion(start *tuple.ObjectAndRelation, children ...*core.RelationTupleTreeNode) *core.RelationTupleTreeNode {
+	return setResult(core.SetOperationUserset_EXCLUSION, start, children)
+}
diff --git a/vendor/github.com/authzed/spicedb/pkg/graph/walker.go b/vendor/github.com/authzed/spicedb/pkg/graph/walker.go
new file mode 100644
index 0000000..3ae8b6b
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/pkg/graph/walker.go
@@ -0,0 +1,71 @@
+package graph
+
+import (
+	core "github.com/authzed/spicedb/pkg/proto/core/v1"
+	"github.com/authzed/spicedb/pkg/spiceerrors"
+)
+
+// WalkHandler is a function invoked for each node in the rewrite tree. If it returns non-nil,
+// that value is returned from the walk. Otherwise, the walk continues.
+type WalkHandler func(childOneof *core.SetOperation_Child) (interface{}, error)
+
+// WalkRewrite walks a userset rewrite tree, invoking the handler found on each node of the tree
+// until the handler returns a non-nil value, which is in turn returned from this function. Returns
+// nil if no valid value was found. If the rewrite is nil, returns nil.
+func WalkRewrite(rewrite *core.UsersetRewrite, handler WalkHandler) (interface{}, error) {
+	if rewrite == nil {
+		return nil, nil
+	}
+
+	switch rw := rewrite.RewriteOperation.(type) {
+	case *core.UsersetRewrite_Union:
+		return walkRewriteChildren(rw.Union, handler)
+	case *core.UsersetRewrite_Intersection:
+		return walkRewriteChildren(rw.Intersection, handler)
+	case *core.UsersetRewrite_Exclusion:
+		return walkRewriteChildren(rw.Exclusion, handler)
+	default:
+		return nil, spiceerrors.MustBugf("unknown type of rewrite operation in walker: %T", rw)
+	}
+}
+
+// HasThis returns true if there exists a `_this` node anywhere within the given rewrite. If
+// the rewrite is nil, returns false.
+func HasThis(rewrite *core.UsersetRewrite) (bool, error) {
+	result, err := WalkRewrite(rewrite, func(childOneof *core.SetOperation_Child) (interface{}, error) {
+		switch childOneof.ChildType.(type) {
+		case *core.SetOperation_Child_XThis:
+			return true, nil
+		default:
+			return nil, nil
+		}
+	})
+	return result != nil && result.(bool), err
+}
+
+func walkRewriteChildren(so *core.SetOperation, handler WalkHandler) (interface{}, error) {
+	for _, childOneof := range so.Child {
+		vle, err := handler(childOneof)
+		if err != nil {
+			return nil, err
+		}
+
+		if vle != nil {
+			return vle, nil
+		}
+
+		switch child := childOneof.ChildType.(type) {
+		case *core.SetOperation_Child_UsersetRewrite:
+			rvle, err := WalkRewrite(child.UsersetRewrite, handler)
+			if err != nil {
+				return nil, err
+			}
+
+			if rvle != nil {
+				return rvle, nil
+			}
+		}
+	}
+
+	return nil, nil
+}