self.go

Documentation: cuelang.org/go/internal/core/export

     1  // Copyright 2022 CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package export
    16  
    17  import (
    18  	"fmt"
    19  	"strconv"
    20  	"strings"
    21  
    22  	"cuelang.org/go/cue/ast"
    23  	"cuelang.org/go/cue/token"
    24  	"cuelang.org/go/internal/core/adt"
    25  	"cuelang.org/go/internal/core/dep"
    26  )
    27  
    28  // This file contains the algorithm to contain a self-contained CUE file.
    29  
    30  // TODO:
    31  // - Handle below edge cases where a reference directly references the root
    32  //   of the exported main tree.
    33  // - Inline smallish structs that themselves do not have outside
    34  //   references.
    35  // - Overall better inlining.
    36  // - Consider a shorthand for the `let X = { #x: foo }` annotation. Possibly
    37  //   allow `#{}`, or allow "let definitions", like `let #X = {}`.
    38  // - Make doc comment of root the file comment.
    39  
    40  // initPivotter initializes a selfContainedCloser if either a subtree
    41  // is exported or imports need to be removed. It will not initialize one if
    42  // neither is the case.
    43  func (e *exporter) initPivotter(v *adt.Vertex) {
    44  	s := &pivotter{}
    45  	e.pivotter = s
    46  	s.x = e
    47  
    48  	s.depsMap = map[*adt.Vertex]*depData{}
    49  	s.refMap = map[adt.Resolver]*refData{}
    50  
    51  	s.linkDependencies(v)
    52  }
    53  
    54  func (e *exporter) completePivot(f *ast.File) {
    55  	s := e.pivotter
    56  	if s == nil || f == nil {
    57  		return
    58  	}
    59  	for _, d := range s.deps {
    60  		if !d.isExternalRoot() {
    61  			continue
    62  		}
    63  		s.addExternal(d)
    64  	}
    65  	f.Decls = append(f.Decls, s.decls...)
    66  }
    67  
    68  // A pivotter pivots a graph around a new root.
    69  //
    70  // Given a Vertex that itself is not the root of a configuration, the pivotter
    71  // recomputes the configuration to have that node as a root instead.
    72  //
    73  // TODO: although this is currently part of Package export, it could be its own
    74  // package down the line, if there is a proven need for it.
    75  type pivotter struct {
    76  	x *exporter
    77  
    78  	deps    []*depData
    79  	depsMap map[*adt.Vertex]*depData
    80  
    81  	refs   []*refData
    82  	refMap map[adt.Resolver]*refData
    83  
    84  	decls []ast.Decl
    85  }
    86  
    87  type depData struct {
    88  	parent *depData
    89  
    90  	dstNode   *adt.Vertex
    91  	dstImport *adt.ImportReference
    92  
    93  	ident        adt.Feature
    94  	path         []adt.Feature
    95  	useCount     int // Other reference using this vertex
    96  	included     bool
    97  	needTopLevel bool
    98  }
    99  
   100  // isExternalRoot reports whether d is an external node (a node referenced
   101  // outside main exported tree) that has no further parent nodes that are
   102  // referenced.
   103  func (d *depData) isExternalRoot() bool {
   104  	return d.ident != 0
   105  }
   106  
   107  func (d *depData) usageCount() int {
   108  	return getParent(d).useCount
   109  }
   110  
   111  type refData struct {
   112  	dst *depData
   113  }
   114  
   115  func (v *depData) node() *adt.Vertex {
   116  	return v.dstNode
   117  }
   118  
   119  func (p *pivotter) linkDependencies(v *adt.Vertex) {
   120  	p.markDeps(v, nil)
   121  
   122  	// Explicitly add the root of the configuration.
   123  	p.markIncluded(v)
   124  
   125  	// Link one parent up
   126  	for _, d := range p.depsMap {
   127  		p.markParentsPass1(d)
   128  	}
   129  
   130  	// Get transitive closure of parents.
   131  	for _, d := range p.depsMap {
   132  		if d.parent != nil {
   133  			d.parent = getParent(d)
   134  			d.parent.useCount++
   135  		}
   136  	}
   137  
   138  	// Compute the paths for the parent nodes.
   139  	for _, d := range p.deps {
   140  		if d.parent == nil {
   141  			p.makeParentPath(d)
   142  		}
   143  	}
   144  }
   145  
   146  func getParent(d *depData) *depData {
   147  	for ; d.parent != nil; d = d.parent {
   148  	}
   149  	return d
   150  }
   151  
   152  func (p *pivotter) markDeps(v *adt.Vertex, pkg *adt.ImportReference) {
   153  	// TODO: sweep all child nodes and mark as no need for recursive checks.
   154  
   155  	cfg := &dep.Config{
   156  		Descend: true,
   157  		Pkg:     pkg,
   158  	}
   159  	dep.Visit(cfg, p.x.ctx, v, func(d dep.Dependency) error {
   160  		node := d.Node
   161  
   162  		switch {
   163  		case p.refMap[d.Reference] != nil:
   164  			// Already done.
   165  			return nil
   166  
   167  		case d.Import() != nil:
   168  			// Only record nodes within import if we want to expand imports.
   169  			if !p.x.cfg.InlineImports {
   170  				return nil
   171  			}
   172  
   173  			// Never resolve core packages. Reasons:
   174  			// - most of them are builtins
   175  			// - they are available anyway
   176  			// - some of the types have special meaning, which would be lost
   177  			//   by rewriting to their underlying type.
   178  			// TODO: support marking non-CUE packages as "special". This could
   179  			// be done, for instance, by marking them as "core" in the runtime
   180  			// and using a Runtime method to determine whether something is
   181  			// a core package, rather than relying on the presence of a dot.
   182  			path := d.Import().ImportPath.StringValue(p.x.ctx)
   183  			if !strings.ContainsRune(path, '.') {
   184  				return nil
   185  			}
   186  
   187  		case node.IsUnprocessed():
   188  			// This may happen for DynamicReferences.
   189  			return nil
   190  		}
   191  
   192  		data, ok := p.depsMap[node]
   193  		if !ok {
   194  			data = &depData{
   195  				dstNode:   node,
   196  				dstImport: d.Import(),
   197  			}
   198  			p.depsMap[node] = data
   199  			p.deps = append(p.deps, data)
   200  		}
   201  		data.useCount++
   202  
   203  		ref := &refData{dst: data}
   204  		p.refs = append(p.refs, ref)
   205  		p.refMap[d.Reference] = ref
   206  
   207  		if !ok {
   208  			d.Recurse()
   209  		}
   210  
   211  		return nil
   212  	})
   213  }
   214  
   215  // markIncluded marks all referred nodes that are within the normal tree to be
   216  // exported.
   217  func (p *pivotter) markIncluded(v *adt.Vertex) {
   218  	d, ok := p.depsMap[v]
   219  	if !ok {
   220  		d = &depData{dstNode: v}
   221  		p.depsMap[v] = d
   222  	}
   223  	d.included = true
   224  
   225  	for _, a := range v.Arcs {
   226  		p.markIncluded(a)
   227  	}
   228  }
   229  
   230  // markParentPass1 marks the furthest ancestor node for which there is a
   231  // dependency as its parent. Only dependencies that do not have a parent
   232  // will be assigned to hidden reference.
   233  func (p *pivotter) markParentsPass1(d *depData) {
   234  	for n := d.node().Parent; n != nil; n = n.Parent {
   235  		if v, ok := p.depsMap[n]; ok {
   236  			d.parent = v
   237  		}
   238  	}
   239  }
   240  
   241  func (p *pivotter) makeParentPath(d *depData) {
   242  	if d.parent != nil {
   243  		panic("not a parent")
   244  	}
   245  
   246  	if d.included || d.isExternalRoot() {
   247  		return
   248  	}
   249  
   250  	var f adt.Feature
   251  
   252  	if path := d.dstNode.Path(); len(path) > 0 {
   253  		f = path[len(path)-1]
   254  	} else if imp := d.dstImport; imp != nil {
   255  		f = imp.Label
   256  	} else {
   257  		// This may legitimately happen for internal vertices, such as
   258  		// comprehension scopes.
   259  		return
   260  	}
   261  
   262  	var str string
   263  	if f.IsInt() {
   264  		str = fmt.Sprintf("Index%d", f.Index())
   265  	} else {
   266  		str = f.IdentString(p.x.ctx)
   267  		str = strings.TrimLeft(str, "_#")
   268  		str = strings.ToUpper(str)
   269  	}
   270  	uf, _ := p.x.uniqueFeature(str)
   271  
   272  	d.path = []adt.Feature{uf}
   273  	d.ident = uf
   274  
   275  	// Make it a definition if we need it.
   276  	if d.dstNode.IsRecursivelyClosed() {
   277  		d.path = append(d.path, adt.MakeIdentLabel(p.x.ctx, "#x", ""))
   278  	}
   279  }
   280  
   281  // makeAlternativeReference computes the alternative path for the reference.
   282  func (p *pivotter) makeAlternativeReference(ref *refData, r adt.Resolver) ast.Expr {
   283  	d := ref.dst
   284  
   285  	// Determine if the reference can be inline.
   286  
   287  	var path []adt.Feature
   288  	if d.parent == nil {
   289  		// Get canonical vertexData.
   290  		path = d.path
   291  	} else {
   292  		pathLen, pkgRef := relPathLength(r)
   293  		path = d.node().Path()
   294  		count := d.stepsToParent()
   295  
   296  		switch {
   297  		case ref.dst.included:
   298  			// Inside main tree.
   299  			if count > pathLen {
   300  				// Cannot refer to root, so cannot use >=
   301  				return nil
   302  			}
   303  
   304  		case pkgRef:
   305  
   306  		default:
   307  			// Inside hoisted value.
   308  			if count >= pathLen {
   309  				return nil
   310  			}
   311  		}
   312  
   313  		path = path[len(path)-count:]
   314  		path = append(d.parent.path, path...)
   315  	}
   316  
   317  	if len(path) == 0 {
   318  		path = append(path, p.x.ctx.StringLabel("ROOT"))
   319  	}
   320  
   321  	var x ast.Expr = p.x.ident(path[0])
   322  
   323  	for _, f := range path[1:] {
   324  		if f.IsInt() {
   325  			x = &ast.IndexExpr{
   326  				X:     x,
   327  				Index: ast.NewLit(token.INT, strconv.Itoa(f.Index())),
   328  			}
   329  		} else {
   330  			x = &ast.SelectorExpr{
   331  				X:   x,
   332  				Sel: p.x.stringLabel(f),
   333  			}
   334  		}
   335  	}
   336  
   337  	return x
   338  }
   339  
   340  func (d *depData) stepsToParent() int {
   341  	parent := d.parent.node()
   342  	count := 0
   343  	for p := d.node(); p != parent; p = p.Parent {
   344  		if p == nil {
   345  			break
   346  		}
   347  		count++
   348  	}
   349  	return count
   350  }
   351  
   352  func relPathLength(r adt.Resolver) (length int, newRoot bool) {
   353  	for {
   354  		var expr adt.Expr
   355  		switch x := r.(type) {
   356  		case *adt.FieldReference,
   357  			*adt.DynamicReference,
   358  			*adt.LetReference,
   359  			*adt.ValueReference:
   360  			length++
   361  		case *adt.ImportReference:
   362  			// This reference indicates a different vertex as root, but doesn't
   363  			// increase the path length.
   364  			return length, true
   365  		case *adt.SelectorExpr:
   366  			length++
   367  			expr = x.X
   368  		case *adt.IndexExpr:
   369  			length++
   370  			expr = x.X
   371  		}
   372  
   373  		switch x := expr.(type) {
   374  		case nil:
   375  			return length, false
   376  		case adt.Resolver:
   377  			r = x
   378  		default:
   379  			panic("unreachable")
   380  		}
   381  	}
   382  }
   383  
   384  // refExpr returns a substituted expression for a given reference, or nil if
   385  // there are no changes. This function implements most of the policy to decide
   386  // when an expression can be inlined.
   387  func (p *pivotter) refExpr(r adt.Resolver) ast.Expr {
   388  	ref, ok := p.refMap[r]
   389  	if !ok {
   390  		return nil
   391  	}
   392  
   393  	dst := ref.dst
   394  	n := dst.node()
   395  
   396  	// Inline value, but only when this may not lead to an exponential
   397  	// expansion. We allow inlining when a value is only used once, or when
   398  	// it is a simple concrete scalar value.
   399  	switch {
   400  	case dst.included:
   401  		// Keep references that point inside the hoisted vertex.
   402  		// TODO: force hoisting. This would be akin to taking the interpretation
   403  		// that references that initially point outside the included vertex
   404  		// are external inputs too, even if they eventually point inside.
   405  	case p.x.inDefinition == 0 && n.IsRecursivelyClosed():
   406  		// We need to wrap the value in a definition.
   407  	case dst.usageCount() == 0:
   408  		// The root value itself.
   409  	case n.IsErr():
   410  		// Don't simplify for errors to make the position of the error clearer.
   411  	case !n.IsConcrete() && p.x.inExpression > 0:
   412  		// Don't simplify an expression that is known will fail.
   413  	case dst.usageCount() == 1 && p.x.inExpression == 0:
   414  		// Used only once.
   415  		fallthrough
   416  	case n.IsConcrete() && len(n.Arcs) == 0:
   417  		// Simple scalar value.
   418  		return p.x.expr(nil, n)
   419  	}
   420  
   421  	if r := p.makeAlternativeReference(ref, r); r != nil {
   422  		dst.needTopLevel = true
   423  		return r
   424  	}
   425  
   426  	return nil
   427  }
   428  
   429  // addExternal converts a vertex for an external reference.
   430  func (p *pivotter) addExternal(d *depData) {
   431  	if !d.needTopLevel {
   432  		return
   433  	}
   434  
   435  	expr := p.x.expr(nil, d.node())
   436  
   437  	if len(d.path) > 1 {
   438  		expr = ast.NewStruct(&ast.Field{
   439  			Label: p.x.stringLabel(d.path[1]),
   440  			Value: expr,
   441  		})
   442  	}
   443  	let := &ast.LetClause{
   444  		Ident: p.x.ident(d.path[0]),
   445  		Expr:  expr,
   446  	}
   447  
   448  	ast.SetRelPos(let, token.NewSection)
   449  
   450  	path := p.x.ctx.PathToString(d.node().Path())
   451  	var msg string
   452  	if d.dstImport == nil {
   453  		msg = fmt.Sprintf("//cue:path: %s", path)
   454  	} else {
   455  		pkg := d.dstImport.ImportPath.SelectorString(p.x.ctx)
   456  		if path == "" {
   457  			msg = fmt.Sprintf("//cue:path: %s", pkg)
   458  		} else {
   459  			msg = fmt.Sprintf("//cue:path: %s.%s", pkg, path)
   460  		}
   461  	}
   462  	cg := &ast.CommentGroup{
   463  		Doc:  true,
   464  		List: []*ast.Comment{{Text: msg}},
   465  	}
   466  	ast.SetRelPos(cg, token.NewSection)
   467  	ast.AddComment(let, cg)
   468  
   469  	p.decls = append(p.decls, let)
   470  }
   471
View as plain text