walk.go

Documentation: cuelang.org/go/cue/ast

     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 ast
    16  
    17  import (
    18  	"fmt"
    19  
    20  	"cuelang.org/go/cue/token"
    21  )
    22  
    23  // Walk traverses an AST in depth-first order: It starts by calling f(node);
    24  // node must not be nil. If before returns true, Walk invokes f recursively for
    25  // each of the non-nil children of node, followed by a call of after. Both
    26  // functions may be nil. If before is nil, it is assumed to always return true.
    27  func Walk(node Node, before func(Node) bool, after func(Node)) {
    28  	walk(&inspector{before: before, after: after}, node)
    29  }
    30  
    31  // A visitor's before method is invoked for each node encountered by Walk.
    32  // If the result visitor w is true, Walk visits each of the children
    33  // of node with the visitor w, followed by a call of w.After.
    34  type visitor interface {
    35  	Before(node Node) (w visitor)
    36  	After(node Node)
    37  }
    38  
    39  // Helper functions for common node lists. They may be empty.
    40  
    41  func walkExprList(v visitor, list []Expr) {
    42  	for _, x := range list {
    43  		walk(v, x)
    44  	}
    45  }
    46  
    47  func walkDeclList(v visitor, list []Decl) {
    48  	for _, x := range list {
    49  		walk(v, x)
    50  	}
    51  }
    52  
    53  // walk traverses an AST in depth-first order: It starts by calling
    54  // v.Visit(node); node must not be nil. If the visitor w returned by
    55  // v.Visit(node) is not nil, walk is invoked recursively with visitor
    56  // w for each of the non-nil children of node, followed by a call of
    57  // w.Visit(nil).
    58  func walk(v visitor, node Node) {
    59  	if v = v.Before(node); v == nil {
    60  		return
    61  	}
    62  
    63  	// TODO: record the comment groups and interleave with the values like for
    64  	// parsing and printing?
    65  	for _, c := range Comments(node) {
    66  		walk(v, c)
    67  	}
    68  
    69  	// walk children
    70  	// (the order of the cases matches the order
    71  	// of the corresponding node types in go)
    72  	switch n := node.(type) {
    73  	// Comments and fields
    74  	case *Comment:
    75  		// nothing to do
    76  
    77  	case *CommentGroup:
    78  		for _, c := range n.List {
    79  			walk(v, c)
    80  		}
    81  
    82  	case *Attribute:
    83  		// nothing to do
    84  
    85  	case *Field:
    86  		walk(v, n.Label)
    87  		if n.Value != nil {
    88  			walk(v, n.Value)
    89  		}
    90  		for _, a := range n.Attrs {
    91  			walk(v, a)
    92  		}
    93  
    94  	case *Func:
    95  		walkExprList(v, n.Args)
    96  		walk(v, n.Ret)
    97  
    98  	case *StructLit:
    99  		walkDeclList(v, n.Elts)
   100  
   101  	// Expressions
   102  	case *BottomLit, *BadExpr, *Ident, *BasicLit:
   103  		// nothing to do
   104  
   105  	case *Interpolation:
   106  		for _, e := range n.Elts {
   107  			walk(v, e)
   108  		}
   109  
   110  	case *ListLit:
   111  		walkExprList(v, n.Elts)
   112  
   113  	case *Ellipsis:
   114  		if n.Type != nil {
   115  			walk(v, n.Type)
   116  		}
   117  
   118  	case *ParenExpr:
   119  		walk(v, n.X)
   120  
   121  	case *SelectorExpr:
   122  		walk(v, n.X)
   123  		walk(v, n.Sel)
   124  
   125  	case *IndexExpr:
   126  		walk(v, n.X)
   127  		walk(v, n.Index)
   128  
   129  	case *SliceExpr:
   130  		walk(v, n.X)
   131  		if n.Low != nil {
   132  			walk(v, n.Low)
   133  		}
   134  		if n.High != nil {
   135  			walk(v, n.High)
   136  		}
   137  
   138  	case *CallExpr:
   139  		walk(v, n.Fun)
   140  		walkExprList(v, n.Args)
   141  
   142  	case *UnaryExpr:
   143  		walk(v, n.X)
   144  
   145  	case *BinaryExpr:
   146  		walk(v, n.X)
   147  		walk(v, n.Y)
   148  
   149  	// Declarations
   150  	case *ImportSpec:
   151  		if n.Name != nil {
   152  			walk(v, n.Name)
   153  		}
   154  		walk(v, n.Path)
   155  
   156  	case *BadDecl:
   157  		// nothing to do
   158  
   159  	case *ImportDecl:
   160  		for _, s := range n.Specs {
   161  			walk(v, s)
   162  		}
   163  
   164  	case *EmbedDecl:
   165  		walk(v, n.Expr)
   166  
   167  	case *LetClause:
   168  		walk(v, n.Ident)
   169  		walk(v, n.Expr)
   170  
   171  	case *Alias:
   172  		walk(v, n.Ident)
   173  		walk(v, n.Expr)
   174  
   175  	case *Comprehension:
   176  		for _, c := range n.Clauses {
   177  			walk(v, c)
   178  		}
   179  		walk(v, n.Value)
   180  
   181  	// Files and packages
   182  	case *File:
   183  		walkDeclList(v, n.Decls)
   184  
   185  	case *Package:
   186  		walk(v, n.Name)
   187  
   188  	case *ForClause:
   189  		if n.Key != nil {
   190  			walk(v, n.Key)
   191  		}
   192  		walk(v, n.Value)
   193  		walk(v, n.Source)
   194  
   195  	case *IfClause:
   196  		walk(v, n.Condition)
   197  
   198  	default:
   199  		panic(fmt.Sprintf("Walk: unexpected node type %T", n))
   200  	}
   201  
   202  	v.After(node)
   203  }
   204  
   205  type inspector struct {
   206  	before func(Node) bool
   207  	after  func(Node)
   208  
   209  	commentStack []commentFrame
   210  	current      commentFrame
   211  }
   212  
   213  type commentFrame struct {
   214  	cg  []*CommentGroup
   215  	pos int8
   216  }
   217  
   218  func (f *inspector) Before(node Node) visitor {
   219  	if f.before == nil || f.before(node) {
   220  		f.commentStack = append(f.commentStack, f.current)
   221  		f.current = commentFrame{cg: Comments(node)}
   222  		f.visitComments(f.current.pos)
   223  		return f
   224  	}
   225  	return nil
   226  }
   227  
   228  func (f *inspector) After(node Node) {
   229  	f.visitComments(127)
   230  	p := len(f.commentStack) - 1
   231  	f.current = f.commentStack[p]
   232  	f.commentStack = f.commentStack[:p]
   233  	f.current.pos++
   234  	if f.after != nil {
   235  		f.after(node)
   236  	}
   237  }
   238  
   239  func (f *inspector) Token(t token.Token) {
   240  	f.current.pos++
   241  }
   242  
   243  func (f *inspector) visitComments(pos int8) {
   244  	c := &f.current
   245  	for ; len(c.cg) > 0; c.cg = c.cg[1:] {
   246  		cg := c.cg[0]
   247  		if cg.Position == pos {
   248  			continue
   249  		}
   250  		if f.before == nil || f.before(cg) {
   251  			for _, c := range cg.List {
   252  				if f.before == nil || f.before(c) {
   253  					if f.after != nil {
   254  						f.after(c)
   255  					}
   256  				}
   257  			}
   258  			if f.after != nil {
   259  				f.after(cg)
   260  			}
   261  		}
   262  	}
   263  }
   264
View as plain text