apply.go

Documentation: cuelang.org/go/cue/ast/astutil

     1  // Copyright 2018 The 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 astutil
    16  
    17  import (
    18  	"encoding/hex"
    19  	"fmt"
    20  	"hash/fnv"
    21  	"reflect"
    22  
    23  	"cuelang.org/go/cue/ast"
    24  )
    25  
    26  // A Cursor describes a node encountered during Apply.
    27  // Information about the node and its parent is available
    28  // from the Node, Parent, and Index methods.
    29  //
    30  // The methods Replace, Delete, InsertBefore, and InsertAfter
    31  // can be used to change the AST without disrupting Apply.
    32  // Delete, InsertBefore, and InsertAfter are only defined for modifying
    33  // a StructLit and will panic in any other context.
    34  type Cursor interface {
    35  	// Node returns the current Node.
    36  	Node() ast.Node
    37  
    38  	// Parent returns the parent of the current Node.
    39  	Parent() Cursor
    40  
    41  	// Index reports the index >= 0 of the current Node in the slice of Nodes
    42  	// that contains it, or a value < 0 if the current Node is not part of a
    43  	// list.
    44  	Index() int
    45  
    46  	// Import reports an opaque identifier that refers to the given package. It
    47  	// may only be called if the input to apply was an ast.File. If the import
    48  	// does not exist, it will be added.
    49  	Import(path string) *ast.Ident
    50  
    51  	// Replace replaces the current Node with n.
    52  	// The replacement node is not walked by Apply. Comments of the old node
    53  	// are copied to the new node if it has not yet an comments associated
    54  	// with it.
    55  	Replace(n ast.Node)
    56  
    57  	// Delete deletes the current Node from its containing struct.
    58  	// If the current Node is not part of a struct, Delete panics.
    59  	Delete()
    60  
    61  	// InsertAfter inserts n after the current Node in its containing struct.
    62  	// If the current Node is not part of a struct, InsertAfter panics.
    63  	// Unless n is wrapped by ApplyRecursively, Apply does not walk n.
    64  	InsertAfter(n ast.Node)
    65  
    66  	// InsertBefore inserts n before the current Node in its containing struct.
    67  	// If the current Node is not part of a struct, InsertBefore panics.
    68  	// Unless n is wrapped by ApplyRecursively, Apply does not walk n.
    69  	InsertBefore(n ast.Node)
    70  
    71  	self() *cursor
    72  }
    73  
    74  // ApplyRecursively indicates that a node inserted with InsertBefore,
    75  // or InsertAfter should be processed recursively.
    76  func ApplyRecursively(n ast.Node) ast.Node {
    77  	return recursive{n}
    78  }
    79  
    80  type recursive struct {
    81  	ast.Node
    82  }
    83  
    84  type info struct {
    85  	f       *ast.File
    86  	current *declsCursor
    87  
    88  	importPatch []*ast.Ident
    89  }
    90  
    91  type cursor struct {
    92  	file     *info
    93  	parent   Cursor
    94  	node     ast.Node
    95  	typ      interface{} // the type of the node
    96  	index    int         // position of any of the sub types.
    97  	replaced bool
    98  }
    99  
   100  func newCursor(parent Cursor, n ast.Node, typ interface{}) *cursor {
   101  	return &cursor{
   102  		parent: parent,
   103  		typ:    typ,
   104  		node:   n,
   105  		index:  -1,
   106  	}
   107  }
   108  
   109  func fileInfo(c Cursor) (info *info) {
   110  	for ; c != nil; c = c.Parent() {
   111  		if i := c.self().file; i != nil {
   112  			return i
   113  		}
   114  	}
   115  	return nil
   116  }
   117  
   118  func (c *cursor) self() *cursor  { return c }
   119  func (c *cursor) Parent() Cursor { return c.parent }
   120  func (c *cursor) Index() int     { return c.index }
   121  func (c *cursor) Node() ast.Node { return c.node }
   122  
   123  func (c *cursor) Import(importPath string) *ast.Ident {
   124  	info := fileInfo(c)
   125  	if info == nil {
   126  		return nil
   127  	}
   128  
   129  	name := ImportPathName(importPath)
   130  
   131  	// TODO: come up with something much better.
   132  	// For instance, hoist the uniquer form cue/export.go to
   133  	// here and make export.go use this.
   134  	hash := fnv.New32()
   135  	name += hex.EncodeToString(hash.Sum([]byte(importPath)))[:6]
   136  
   137  	spec := insertImport(&info.current.decls, &ast.ImportSpec{
   138  		Name: ast.NewIdent(name),
   139  		Path: ast.NewString(importPath),
   140  	})
   141  
   142  	ident := &ast.Ident{Node: spec} // Name is set later.
   143  	info.importPatch = append(info.importPatch, ident)
   144  
   145  	ident.Name = name
   146  
   147  	return ident
   148  }
   149  
   150  func (c *cursor) Replace(n ast.Node) {
   151  	// panic if the value cannot convert to the original type.
   152  	reflect.ValueOf(n).Convert(reflect.TypeOf(c.typ).Elem())
   153  	if ast.Comments(n) != nil {
   154  		CopyComments(n, c.node)
   155  	}
   156  	if r, ok := n.(recursive); ok {
   157  		n = r.Node
   158  	} else {
   159  		c.replaced = true
   160  	}
   161  	c.node = n
   162  }
   163  
   164  func (c *cursor) InsertAfter(n ast.Node)  { panic("unsupported") }
   165  func (c *cursor) InsertBefore(n ast.Node) { panic("unsupported") }
   166  func (c *cursor) Delete()                 { panic("unsupported") }
   167  
   168  // Apply traverses a syntax tree recursively, starting with root,
   169  // and calling pre and post for each node as described below.
   170  // Apply returns the syntax tree, possibly modified.
   171  //
   172  // If pre is not nil, it is called for each node before the node's
   173  // children are traversed (pre-order). If pre returns false, no
   174  // children are traversed, and post is not called for that node.
   175  //
   176  // If post is not nil, and a prior call of pre didn't return false,
   177  // post is called for each node after its children are traversed
   178  // (post-order). If post returns false, traversal is terminated and
   179  // Apply returns immediately.
   180  //
   181  // Only fields that refer to AST nodes are considered children;
   182  // i.e., token.Pos, Scopes, Objects, and fields of basic types
   183  // (strings, etc.) are ignored.
   184  //
   185  // Children are traversed in the order in which they appear in the
   186  // respective node's struct definition.
   187  func Apply(node ast.Node, before, after func(Cursor) bool) ast.Node {
   188  	apply(&applier{before: before, after: after}, nil, &node)
   189  	return node
   190  }
   191  
   192  // A applyVisitor's before method is invoked for each node encountered by Walk.
   193  // If the result applyVisitor w is true, Walk visits each of the children
   194  // of node with the applyVisitor w, followed by a call of w.After.
   195  type applyVisitor interface {
   196  	Before(Cursor) applyVisitor
   197  	After(Cursor) bool
   198  }
   199  
   200  // Helper functions for common node lists. They may be empty.
   201  
   202  func applyExprList(v applyVisitor, parent Cursor, list []ast.Expr) {
   203  	c := newCursor(parent, nil, nil)
   204  	for i, x := range list {
   205  		c.index = i
   206  		c.node = x
   207  		c.typ = &list[i]
   208  		applyCursor(v, c)
   209  		if x != c.node {
   210  			list[i] = c.node.(ast.Expr)
   211  		}
   212  	}
   213  }
   214  
   215  type declsCursor struct {
   216  	*cursor
   217  	decls, after, process []ast.Decl
   218  	delete                bool
   219  }
   220  
   221  func (c *declsCursor) InsertAfter(n ast.Node) {
   222  	if r, ok := n.(recursive); ok {
   223  		n = r.Node
   224  		c.process = append(c.process, n.(ast.Decl))
   225  	}
   226  	c.after = append(c.after, n.(ast.Decl))
   227  }
   228  
   229  func (c *declsCursor) InsertBefore(n ast.Node) {
   230  	if r, ok := n.(recursive); ok {
   231  		n = r.Node
   232  		c.process = append(c.process, n.(ast.Decl))
   233  	}
   234  	c.decls = append(c.decls, n.(ast.Decl))
   235  }
   236  
   237  func (c *declsCursor) Delete() { c.delete = true }
   238  
   239  func applyDeclList(v applyVisitor, parent Cursor, list []ast.Decl) []ast.Decl {
   240  	c := &declsCursor{
   241  		cursor: newCursor(parent, nil, nil),
   242  		decls:  make([]ast.Decl, 0, len(list)),
   243  	}
   244  	if file, ok := parent.Node().(*ast.File); ok {
   245  		c.cursor.file = &info{f: file, current: c}
   246  	}
   247  	for i, x := range list {
   248  		c.node = x
   249  		c.typ = &list[i]
   250  		applyCursor(v, c)
   251  		if !c.delete {
   252  			c.decls = append(c.decls, c.node.(ast.Decl))
   253  		}
   254  		c.delete = false
   255  		for i := 0; i < len(c.process); i++ {
   256  			x := c.process[i]
   257  			c.node = x
   258  			c.typ = &c.process[i]
   259  			applyCursor(v, c)
   260  			if c.delete {
   261  				panic("cannot delete a node that was added with InsertBefore or InsertAfter")
   262  			}
   263  		}
   264  		c.decls = append(c.decls, c.after...)
   265  		c.after = c.after[:0]
   266  		c.process = c.process[:0]
   267  	}
   268  
   269  	// TODO: ultimately, programmatically linked nodes have to be resolved
   270  	// at the end.
   271  	// if info := c.cursor.file; info != nil {
   272  	// 	done := map[*ast.ImportSpec]bool{}
   273  	// 	for _, ident := range info.importPatch {
   274  	// 		spec := ident.Node.(*ast.ImportSpec)
   275  	// 		if done[spec] {
   276  	// 			continue
   277  	// 		}
   278  	// 		done[spec] = true
   279  
   280  	// 		path, _ := strconv.Unquote(spec.Path)
   281  
   282  	// 		ident.Name =
   283  	// 	}
   284  	// }
   285  
   286  	return c.decls
   287  }
   288  
   289  func apply[N ast.Node](v applyVisitor, parent Cursor, nodePtr *N) {
   290  	node := *nodePtr
   291  	c := newCursor(parent, node, nodePtr)
   292  	applyCursor(v, c)
   293  	if ast.Node(node) != c.node {
   294  		*nodePtr = c.node.(N)
   295  	}
   296  }
   297  
   298  // applyCursor traverses an AST in depth-first order: It starts by calling
   299  // v.Visit(node); node must not be nil. If the visitor w returned by
   300  // v.Visit(node) is not nil, apply is invoked recursively with visitor
   301  // w for each of the non-nil children of node, followed by a call of
   302  // w.Visit(nil).
   303  func applyCursor(v applyVisitor, c Cursor) {
   304  	if v = v.Before(c); v == nil {
   305  		return
   306  	}
   307  
   308  	node := c.Node()
   309  
   310  	// TODO: record the comment groups and interleave with the values like for
   311  	// parsing and printing?
   312  	comments := node.Comments()
   313  	for _, cm := range comments {
   314  		apply(v, c, &cm)
   315  	}
   316  
   317  	// apply children
   318  	// (the order of the cases matches the order
   319  	// of the corresponding node types in go)
   320  	switch n := node.(type) {
   321  	// Comments and fields
   322  	case *ast.Comment:
   323  		// nothing to do
   324  
   325  	case *ast.CommentGroup:
   326  		for _, cg := range n.List {
   327  			apply(v, c, &cg)
   328  		}
   329  
   330  	case *ast.Attribute:
   331  		// nothing to do
   332  
   333  	case *ast.Field:
   334  		apply(v, c, &n.Label)
   335  		if n.Value != nil {
   336  			apply(v, c, &n.Value)
   337  		}
   338  		for _, a := range n.Attrs {
   339  			apply(v, c, &a)
   340  		}
   341  
   342  	case *ast.StructLit:
   343  		n.Elts = applyDeclList(v, c, n.Elts)
   344  
   345  	// Expressions
   346  	case *ast.BottomLit, *ast.BadExpr, *ast.Ident, *ast.BasicLit:
   347  		// nothing to do
   348  
   349  	case *ast.Interpolation:
   350  		applyExprList(v, c, n.Elts)
   351  
   352  	case *ast.ListLit:
   353  		applyExprList(v, c, n.Elts)
   354  
   355  	case *ast.Ellipsis:
   356  		if n.Type != nil {
   357  			apply(v, c, &n.Type)
   358  		}
   359  
   360  	case *ast.ParenExpr:
   361  		apply(v, c, &n.X)
   362  
   363  	case *ast.SelectorExpr:
   364  		apply(v, c, &n.X)
   365  		apply(v, c, &n.Sel)
   366  
   367  	case *ast.IndexExpr:
   368  		apply(v, c, &n.X)
   369  		apply(v, c, &n.Index)
   370  
   371  	case *ast.SliceExpr:
   372  		apply(v, c, &n.X)
   373  		if n.Low != nil {
   374  			apply(v, c, &n.Low)
   375  		}
   376  		if n.High != nil {
   377  			apply(v, c, &n.High)
   378  		}
   379  
   380  	case *ast.CallExpr:
   381  		apply(v, c, &n.Fun)
   382  		applyExprList(v, c, n.Args)
   383  
   384  	case *ast.UnaryExpr:
   385  		apply(v, c, &n.X)
   386  
   387  	case *ast.BinaryExpr:
   388  		apply(v, c, &n.X)
   389  		apply(v, c, &n.Y)
   390  
   391  	// Declarations
   392  	case *ast.ImportSpec:
   393  		if n.Name != nil {
   394  			apply(v, c, &n.Name)
   395  		}
   396  		apply(v, c, &n.Path)
   397  
   398  	case *ast.BadDecl:
   399  		// nothing to do
   400  
   401  	case *ast.ImportDecl:
   402  		for _, s := range n.Specs {
   403  			apply(v, c, &s)
   404  		}
   405  
   406  	case *ast.EmbedDecl:
   407  		apply(v, c, &n.Expr)
   408  
   409  	case *ast.LetClause:
   410  		apply(v, c, &n.Ident)
   411  		apply(v, c, &n.Expr)
   412  
   413  	case *ast.Alias:
   414  		apply(v, c, &n.Ident)
   415  		apply(v, c, &n.Expr)
   416  
   417  	case *ast.Comprehension:
   418  		clauses := n.Clauses
   419  		for i := range n.Clauses {
   420  			apply(v, c, &clauses[i])
   421  		}
   422  		apply(v, c, &n.Value)
   423  
   424  	// Files and packages
   425  	case *ast.File:
   426  		n.Decls = applyDeclList(v, c, n.Decls)
   427  
   428  	case *ast.Package:
   429  		apply(v, c, &n.Name)
   430  
   431  	case *ast.ForClause:
   432  		if n.Key != nil {
   433  			apply(v, c, &n.Key)
   434  		}
   435  		apply(v, c, &n.Value)
   436  		apply(v, c, &n.Source)
   437  
   438  	case *ast.IfClause:
   439  		apply(v, c, &n.Condition)
   440  
   441  	default:
   442  		panic(fmt.Sprintf("Walk: unexpected node type %T", n))
   443  	}
   444  
   445  	v.After(c)
   446  }
   447  
   448  type applier struct {
   449  	before func(Cursor) bool
   450  	after  func(Cursor) bool
   451  
   452  	commentStack []commentFrame
   453  	current      commentFrame
   454  }
   455  
   456  type commentFrame struct {
   457  	cg  []*ast.CommentGroup
   458  	pos int8
   459  }
   460  
   461  func (f *applier) Before(c Cursor) applyVisitor {
   462  	node := c.Node()
   463  	if f.before == nil || (f.before(c) && node == c.Node()) {
   464  		f.commentStack = append(f.commentStack, f.current)
   465  		f.current = commentFrame{cg: node.Comments()}
   466  		f.visitComments(c, f.current.pos)
   467  		return f
   468  	}
   469  	return nil
   470  }
   471  
   472  func (f *applier) After(c Cursor) bool {
   473  	f.visitComments(c, 127)
   474  	p := len(f.commentStack) - 1
   475  	f.current = f.commentStack[p]
   476  	f.commentStack = f.commentStack[:p]
   477  	f.current.pos++
   478  	if f.after != nil {
   479  		f.after(c)
   480  	}
   481  	return true
   482  }
   483  
   484  func (f *applier) visitComments(p Cursor, pos int8) {
   485  	c := &f.current
   486  	for i := 0; i < len(c.cg); i++ {
   487  		cg := c.cg[i]
   488  		if cg.Position == pos {
   489  			continue
   490  		}
   491  		cursor := newCursor(p, cg, cg)
   492  		if f.before == nil || (f.before(cursor) && !cursor.replaced) {
   493  			for j, c := range cg.List {
   494  				cursor := newCursor(p, c, &c)
   495  				if f.before == nil || (f.before(cursor) && !cursor.replaced) {
   496  					if f.after != nil {
   497  						f.after(cursor)
   498  					}
   499  				}
   500  				cg.List[j] = cursor.node.(*ast.Comment)
   501  			}
   502  			if f.after != nil {
   503  				f.after(cursor)
   504  			}
   505  		}
   506  		c.cg[i] = cursor.node.(*ast.CommentGroup)
   507  	}
   508  }
   509
View as plain text