internal/core/dep/dep.go - cue - Git at Google

 // Copyright 2020 CUE Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 // Package dep analyzes dependencies between values.
 package dep

 import (
 	"errors"

 	"cuelang.org/go/internal/core/adt"
 )

 // A Dependency is a reference and the node that reference resolves to.
 type Dependency struct {
 	// Node is the referenced node.
 	Node *adt.Vertex

 	// Reference is the expression that referenced the node.
 	Reference adt.Resolver

 	top bool
 }

 // Import returns the import reference or nil if the reference was within
 // the same package as the visited Vertex.
 func (d *Dependency) Import() *adt.ImportReference {
 	x, _ := d.Reference.(adt.Expr)
 	return importRef(x)
 }

 // IsRoot reports whether the dependency is referenced by the root of the
 // original Vertex passed to any of the Visit* functions, and not one of its
 // descendent arcs. This always returns true for Visit().
 func (d *Dependency) IsRoot() bool {
 	return d.top
 }

 func (d *Dependency) Path() []adt.Feature {
 	return nil
 }

 func importRef(r adt.Expr) *adt.ImportReference {
 	switch x := r.(type) {
 	case *adt.ImportReference:
 		return x
 	case *adt.SelectorExpr:
 		return importRef(x.X)
 	case *adt.IndexExpr:
 		return importRef(x.X)
 	}
 	return nil
 }

 // VisitFunc is used for reporting dependencies.
 type VisitFunc func(Dependency) error

 // Visit calls f for all vertices referenced by the conjuncts of n without
 // descending into the elements of list or fields of structs. Only references
 // that do not refer to the conjuncts of n itself are reported.
 func Visit(c *adt.OpContext, n *adt.Vertex, f VisitFunc) error {
 	return visit(c, n, f, false, true)
 }

 // VisitAll calls f for all vertices referenced by the conjuncts of n including
 // those of descendant fields and elements. Only references that do not refer to
 // the conjuncts of n itself are reported.
 func VisitAll(c *adt.OpContext, n *adt.Vertex, f VisitFunc) error {
 	return visit(c, n, f, true, true)
 }

 // VisitFields calls f for n and all its descendent arcs that have a conjunct
 // that originates from a conjunct in n. Only the conjuncts of n that ended up
 // as a conjunct in an actual field are visited and they are visited for each
 // field in which the occurs.
 func VisitFields(c *adt.OpContext, n *adt.Vertex, f VisitFunc) error {
 	m := marked{}

 	m.markExpr(n)

 	dynamic(c, n, f, m, true)
 	return nil
 }

 var empty *adt.Vertex

 func init() {
 	empty = &adt.Vertex{}
 	empty.UpdateStatus(adt.Finalized)
 }

 func visit(c *adt.OpContext, n *adt.Vertex, f VisitFunc, all, top bool) (err error) {
 	if c == nil {
 		panic("nil context")
 	}
 	v := visitor{
 		ctxt:  c,
 		visit: f,
 		node:  n,
 		all:   all,
 		top:   top,
 	}

 	defer func() {
 		switch x := recover(); x {
 		case nil:
 		case aborted:
 			err = v.err
 		default:
 			panic(x)
 		}
 	}()

 	for _, x := range n.Conjuncts {
 		v.markExpr(x.Env, x.Expr())
 	}

 	return nil
 }

 var aborted = errors.New("aborted")

 type visitor struct {
 	ctxt  *adt.OpContext
 	visit VisitFunc
 	node  *adt.Vertex
 	err   error
 	all   bool
 	top   bool
 }

 // TODO: factor out the below logic as either a low-level dependency analyzer or
 // some walk functionality.

 // markExpr visits all nodes in an expression to mark dependencies.
 func (c *visitor) markExpr(env *adt.Environment, expr adt.Expr) {
 	switch x := expr.(type) {
 	case nil:
 	case adt.Resolver:
 		c.markResolver(env, x)

 	case *adt.BinaryExpr:
 		c.markExpr(env, x.X)
 		c.markExpr(env, x.Y)

 	case *adt.UnaryExpr:
 		c.markExpr(env, x.X)

 	case *adt.Interpolation:
 		for i := 1; i < len(x.Parts); i += 2 {
 			c.markExpr(env, x.Parts[i])
 		}

 	case *adt.BoundExpr:
 		c.markExpr(env, x.Expr)

 	case *adt.CallExpr:
 		c.markExpr(env, x.Fun)
 		saved := c.all
 		c.all = true
 		for _, a := range x.Args {
 			c.markExpr(env, a)
 		}
 		c.all = saved

 	case *adt.DisjunctionExpr:
 		for _, d := range x.Values {
 			c.markExpr(env, d.Val)
 		}

 	case *adt.SliceExpr:
 		c.markExpr(env, x.X)
 		c.markExpr(env, x.Lo)
 		c.markExpr(env, x.Hi)
 		c.markExpr(env, x.Stride)

 	case *adt.ListLit:
 		for _, e := range x.Elems {
 			switch x := e.(type) {
 			case adt.Yielder:
 				c.markYielder(env, x)

 			case adt.Expr:
 				c.markSubExpr(env, x)

 			case *adt.Ellipsis:
 				if x.Value != nil {
 					c.markSubExpr(env, x.Value)
 				}
 			}
 		}

 	case *adt.StructLit:
 		env := &adt.Environment{Up: env, Vertex: empty}
 		for _, e := range x.Decls {
 			c.markDecl(env, e)
 		}
 	}
 }

 // markResolve resolves dependencies.
 func (c *visitor) markResolver(env *adt.Environment, r adt.Resolver) {
 	switch x := r.(type) {
 	case nil:
 	case *adt.LetReference:
 		saved := c.ctxt.PushState(env, nil)
 		env := c.ctxt.Env(x.UpCount)
 		c.markExpr(env, x.X)
 		c.ctxt.PopState(saved)
 		return
 	}

 	if ref, _ := c.ctxt.Resolve(env, r); ref != nil {
 		if ref != c.node {
 			d := Dependency{
 				Node:      ref,
 				Reference: r,
 				top:       c.top,
 			}
 			if err := c.visit(d); err != nil {
 				c.err = err
 				panic(aborted)
 			}
 		}

 		return
 	}

 	// It is possible that a reference cannot be resolved because it is
 	// incomplete. In this case, we should check whether subexpressions of the
 	// reference can be resolved to mark those dependencies. For instance,
 	// prefix paths of selectors and the value or index of an index experssion
 	// may independently resolve to a valid dependency.

 	switch x := r.(type) {
 	case *adt.NodeLink:
 		panic("unreachable")

 	case *adt.IndexExpr:
 		c.markExpr(env, x.X)
 		c.markExpr(env, x.Index)

 	case *adt.SelectorExpr:
 		c.markExpr(env, x.X)
 	}
 }

 func (c *visitor) markSubExpr(env *adt.Environment, x adt.Expr) {
 	if c.all {
 		saved := c.top
 		c.top = false
 		c.markExpr(env, x)
 		c.top = saved
 	}
 }

 func (c *visitor) markDecl(env *adt.Environment, d adt.Decl) {
 	switch x := d.(type) {
 	case *adt.Field:
 		c.markSubExpr(env, x.Value)

 	case *adt.OptionalField:
 		// when dynamic, only continue if there is evidence of
 		// the field in the parallel actual evaluation.
 		c.markSubExpr(env, x.Value)

 	case *adt.BulkOptionalField:
 		c.markExpr(env, x.Filter)
 		// when dynamic, only continue if there is evidence of
 		// the field in the parallel actual evaluation.
 		c.markSubExpr(env, x.Value)

 	case *adt.DynamicField:
 		c.markExpr(env, x.Key)
 		// when dynamic, only continue if there is evidence of
 		// a matching field in the parallel actual evaluation.
 		c.markSubExpr(env, x.Value)

 	case adt.Yielder:
 		c.markYielder(env, x)

 	case adt.Expr:
 		c.markExpr(env, x)

 	case *adt.Ellipsis:
 		if x.Value != nil {
 			c.markSubExpr(env, x.Value)
 		}
 	}
 }

 func (c *visitor) markYielder(env *adt.Environment, y adt.Yielder) {
 	switch x := y.(type) {
 	case *adt.ForClause:
 		c.markExpr(env, x.Src)
 		env := &adt.Environment{Up: env, Vertex: empty}
 		c.markYielder(env, x.Dst)
 		// In dynamic mode, iterate over all actual value and
 		// evaluate.

 	case *adt.LetClause:
 		c.markExpr(env, x.Expr)
 		env := &adt.Environment{Up: env, Vertex: empty}
 		c.markYielder(env, x.Dst)

 	case *adt.IfClause:
 		c.markExpr(env, x.Condition)
 		// In dynamic mode, only continue if condition is true.
 		c.markYielder(env, x.Dst)

 	case *adt.ValueClause:
 		c.markExpr(env, x.StructLit)
 	}
 }
	// Copyright 2020 CUE Authors
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	// Package dep analyzes dependencies between values.
	package dep

	import (
	"errors"

	"cuelang.org/go/internal/core/adt"
	)

	// A Dependency is a reference and the node that reference resolves to.
	type Dependency struct {
	// Node is the referenced node.
	Node *adt.Vertex

	// Reference is the expression that referenced the node.
	Reference adt.Resolver

	top bool
	}

	// Import returns the import reference or nil if the reference was within
	// the same package as the visited Vertex.
	func (d Dependency) Import() adt.ImportReference {
	x, _ := d.Reference.(adt.Expr)
	return importRef(x)
	}

	// IsRoot reports whether the dependency is referenced by the root of the
	// original Vertex passed to any of the Visit* functions, and not one of its
	// descendent arcs. This always returns true for Visit().
	func (d *Dependency) IsRoot() bool {
	return d.top
	}

	func (d *Dependency) Path() []adt.Feature {
	return nil
	}

	func importRef(r adt.Expr) *adt.ImportReference {
	switch x := r.(type) {
	case *adt.ImportReference:
	return x
	case *adt.SelectorExpr:
	return importRef(x.X)
	case *adt.IndexExpr:
	return importRef(x.X)
	}
	return nil
	}

	// VisitFunc is used for reporting dependencies.
	type VisitFunc func(Dependency) error

	// Visit calls f for all vertices referenced by the conjuncts of n without
	// descending into the elements of list or fields of structs. Only references
	// that do not refer to the conjuncts of n itself are reported.
	func Visit(c adt.OpContext, n adt.Vertex, f VisitFunc) error {
	return visit(c, n, f, false, true)
	}

	// VisitAll calls f for all vertices referenced by the conjuncts of n including
	// those of descendant fields and elements. Only references that do not refer to
	// the conjuncts of n itself are reported.
	func VisitAll(c adt.OpContext, n adt.Vertex, f VisitFunc) error {
	return visit(c, n, f, true, true)
	}

	// VisitFields calls f for n and all its descendent arcs that have a conjunct
	// that originates from a conjunct in n. Only the conjuncts of n that ended up
	// as a conjunct in an actual field are visited and they are visited for each
	// field in which the occurs.
	func VisitFields(c adt.OpContext, n adt.Vertex, f VisitFunc) error {
	m := marked{}

	m.markExpr(n)

	dynamic(c, n, f, m, true)
	return nil
	}

	var empty *adt.Vertex

	func init() {
	empty = &adt.Vertex{}
	empty.UpdateStatus(adt.Finalized)
	}

	func visit(c adt.OpContext, n adt.Vertex, f VisitFunc, all, top bool) (err error) {
	if c == nil {
	panic("nil context")
	}
	v := visitor{
	ctxt: c,
	visit: f,
	node: n,
	all: all,
	top: top,
	}

	defer func() {
	switch x := recover(); x {
	case nil:
	case aborted:
	err = v.err
	default:
	panic(x)
	}
	}()

	for _, x := range n.Conjuncts {
	v.markExpr(x.Env, x.Expr())
	}

	return nil
	}

	var aborted = errors.New("aborted")

	type visitor struct {
	ctxt *adt.OpContext
	visit VisitFunc
	node *adt.Vertex
	err error
	all bool
	top bool
	}

	// TODO: factor out the below logic as either a low-level dependency analyzer or
	// some walk functionality.

	// markExpr visits all nodes in an expression to mark dependencies.
	func (c visitor) markExpr(env adt.Environment, expr adt.Expr) {
	switch x := expr.(type) {
	case nil:
	case adt.Resolver:
	c.markResolver(env, x)

	case *adt.BinaryExpr:
	c.markExpr(env, x.X)
	c.markExpr(env, x.Y)

	case *adt.UnaryExpr:
	c.markExpr(env, x.X)

	case *adt.Interpolation:
	for i := 1; i < len(x.Parts); i += 2 {
	c.markExpr(env, x.Parts[i])
	}

	case *adt.BoundExpr:
	c.markExpr(env, x.Expr)

	case *adt.CallExpr:
	c.markExpr(env, x.Fun)
	saved := c.all
	c.all = true
	for _, a := range x.Args {
	c.markExpr(env, a)
	}
	c.all = saved

	case *adt.DisjunctionExpr:
	for _, d := range x.Values {
	c.markExpr(env, d.Val)
	}

	case *adt.SliceExpr:
	c.markExpr(env, x.X)
	c.markExpr(env, x.Lo)
	c.markExpr(env, x.Hi)
	c.markExpr(env, x.Stride)

	case *adt.ListLit:
	for _, e := range x.Elems {
	switch x := e.(type) {
	case adt.Yielder:
	c.markYielder(env, x)

	case adt.Expr:
	c.markSubExpr(env, x)

	case *adt.Ellipsis:
	if x.Value != nil {
	c.markSubExpr(env, x.Value)
	}
	}
	}

	case *adt.StructLit:
	env := &adt.Environment{Up: env, Vertex: empty}
	for _, e := range x.Decls {
	c.markDecl(env, e)
	}
	}
	}

	// markResolve resolves dependencies.
	func (c visitor) markResolver(env adt.Environment, r adt.Resolver) {
	switch x := r.(type) {
	case nil:
	case *adt.LetReference:
	saved := c.ctxt.PushState(env, nil)
	env := c.ctxt.Env(x.UpCount)
	c.markExpr(env, x.X)
	c.ctxt.PopState(saved)
	return
	}

	if ref, _ := c.ctxt.Resolve(env, r); ref != nil {
	if ref != c.node {
	d := Dependency{
	Node: ref,
	Reference: r,
	top: c.top,
	}
	if err := c.visit(d); err != nil {
	c.err = err
	panic(aborted)
	}
	}

	return
	}

	// It is possible that a reference cannot be resolved because it is
	// incomplete. In this case, we should check whether subexpressions of the
	// reference can be resolved to mark those dependencies. For instance,
	// prefix paths of selectors and the value or index of an index experssion
	// may independently resolve to a valid dependency.

	switch x := r.(type) {
	case *adt.NodeLink:
	panic("unreachable")

	case *adt.IndexExpr:
	c.markExpr(env, x.X)
	c.markExpr(env, x.Index)

	case *adt.SelectorExpr:
	c.markExpr(env, x.X)
	}
	}

	func (c visitor) markSubExpr(env adt.Environment, x adt.Expr) {
	if c.all {
	saved := c.top
	c.top = false
	c.markExpr(env, x)
	c.top = saved
	}
	}

	func (c visitor) markDecl(env adt.Environment, d adt.Decl) {
	switch x := d.(type) {
	case *adt.Field:
	c.markSubExpr(env, x.Value)

	case *adt.OptionalField:
	// when dynamic, only continue if there is evidence of
	// the field in the parallel actual evaluation.
	c.markSubExpr(env, x.Value)

	case *adt.BulkOptionalField:
	c.markExpr(env, x.Filter)
	// when dynamic, only continue if there is evidence of
	// the field in the parallel actual evaluation.
	c.markSubExpr(env, x.Value)

	case *adt.DynamicField:
	c.markExpr(env, x.Key)
	// when dynamic, only continue if there is evidence of
	// a matching field in the parallel actual evaluation.
	c.markSubExpr(env, x.Value)

	case adt.Yielder:
	c.markYielder(env, x)

	case adt.Expr:
	c.markExpr(env, x)

	case *adt.Ellipsis:
	if x.Value != nil {
	c.markSubExpr(env, x.Value)
	}
	}
	}

	func (c visitor) markYielder(env adt.Environment, y adt.Yielder) {
	switch x := y.(type) {
	case *adt.ForClause:
	c.markExpr(env, x.Src)
	env := &adt.Environment{Up: env, Vertex: empty}
	c.markYielder(env, x.Dst)
	// In dynamic mode, iterate over all actual value and
	// evaluate.

	case *adt.LetClause:
	c.markExpr(env, x.Expr)
	env := &adt.Environment{Up: env, Vertex: empty}
	c.markYielder(env, x.Dst)

	case *adt.IfClause:
	c.markExpr(env, x.Condition)
	// In dynamic mode, only continue if condition is true.
	c.markYielder(env, x.Dst)

	case *adt.ValueClause:
	c.markExpr(env, x.StructLit)
	}
	}