cue/ast/walk.go

// Copyright 2018 The 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 ast

import (
	"fmt"

	"cuelang.org/go/cue/token"
)

// Walk traverses an AST in depth-first order: It starts by calling f(node);
// node must not be nil. If before returns true, Walk invokes f recursively for
// each of the non-nil children of node, followed by a call of after. Both
// functions may be nil. If before is nil, it is assumed to always return true.
//
func Walk(node Node, before func(Node) bool, after func(Node)) {
	walk(&inspector{before: before, after: after}, node)
}

// A visitor's before method is invoked for each node encountered by Walk.
// If the result visitor w is not nil, Walk visits each of the children
// of node with the visitor w, followed by a call of w.After.
type visitor interface {
	Before(node Node) (w visitor)
	After(node Node)
}

// Helper functions for common node lists. They may be empty.

func walkIdentList(v visitor, list []*Ident) {
	for _, x := range list {
		walk(v, x)
	}
}

func walkExprList(v visitor, list []Expr) {
	for _, x := range list {
		walk(v, x)
	}
}

func walkDeclList(v visitor, list []Decl) {
	for _, x := range list {
		walk(v, x)
	}
}

// walk traverses an AST in depth-first order: It starts by calling
// v.Visit(node); node must not be nil. If the visitor w returned by
// v.Visit(node) is not nil, walk is invoked recursively with visitor
// w for each of the non-nil children of node, followed by a call of
// w.Visit(nil).
//
func walk(v visitor, node Node) {
	if v = v.Before(node); v == nil {
		return
	}

	// TODO: record the comment groups and interleave with the values like for
	// parsing and printing?
	for _, c := range node.Comments() {
		walk(v, c)
	}

	// walk children
	// (the order of the cases matches the order
	// of the corresponding node types in go)
	switch n := node.(type) {
	// Comments and fields
	case *Comment:
		// nothing to do

	case *CommentGroup:
		for _, c := range n.List {
			walk(v, c)
		}

	case *Field:
		walk(v, n.Label)
		if n.Value != nil {
			walk(v, n.Value)
		}

	case *StructLit:
		for _, f := range n.Elts {
			walk(v, f)
		}

	// Expressions
	case *BottomLit, *BadExpr, *Ident, *BasicLit:
		// nothing to do

	case *TemplateLabel:
		walk(v, n.Ident)

	case *Interpolation:
		for _, e := range n.Elts {
			walk(v, e)
		}

	case *Ellipsis:
		if n.Elt != nil {
			walk(v, n.Elt)
		}

	case *ListLit:
		walkExprList(v, n.Elts)
		if n.Type != nil {
			walk(v, n.Type)
		}

	case *ParenExpr:
		walk(v, n.X)

	case *SelectorExpr:
		walk(v, n.X)
		walk(v, n.Sel)

	case *IndexExpr:
		walk(v, n.X)
		walk(v, n.Index)

	case *SliceExpr:
		walk(v, n.X)
		if n.Low != nil {
			walk(v, n.Low)
		}
		if n.High != nil {
			walk(v, n.High)
		}

	case *CallExpr:
		walk(v, n.Fun)
		walkExprList(v, n.Args)

	case *UnaryExpr:
		walk(v, n.X)

	case *BinaryExpr:
		walk(v, n.X)
		walk(v, n.Y)

	// Declarations
	case *ImportSpec:
		if n.Name != nil {
			walk(v, n.Name)
		}
		walk(v, n.Path)

	case *BadDecl:
		// nothing to do

	case *ImportDecl:
		for _, s := range n.Specs {
			walk(v, s)
		}

	case *EmitDecl:
		walk(v, n.Expr)

	case *Alias:
		walk(v, n.Ident)
		walk(v, n.Expr)

	case *ComprehensionDecl:
		walk(v, n.Field)
		for _, c := range n.Clauses {
			walk(v, c)
		}

	// Files and packages
	case *File:
		if n.Name != nil {
			walk(v, n.Name)
		}
		walkDeclList(v, n.Decls)
		// don't walk n.Comments - they have been
		// visited already through the individual
		// nodes

	case *ListComprehension:
		walk(v, n.Expr)
		for _, c := range n.Clauses {
			walk(v, c)
		}

	case *ForClause:
		if n.Key != nil {
			walk(v, n.Key)
		}
		walk(v, n.Value)
		walk(v, n.Source)

	case *IfClause:
		walk(v, n.Condition)

	default:
		panic(fmt.Sprintf("Walk: unexpected node type %T", n))
	}

	v.After(node)
}

type inspector struct {
	before func(Node) bool
	after  func(Node)

	commentStack []commentFrame
	current      commentFrame
}

type commentFrame struct {
	cg  []*CommentGroup
	pos int8
}

func (f *inspector) Before(node Node) visitor {
	if f.before == nil || f.before(node) {
		f.commentStack = append(f.commentStack, f.current)
		f.current = commentFrame{cg: node.Comments()}
		f.visitComments(f.current.pos)
		return f
	}
	return nil
}

func (f *inspector) After(node Node) {
	f.visitComments(127)
	p := len(f.commentStack) - 1
	f.current = f.commentStack[p]
	f.commentStack = f.commentStack[:p]
	f.current.pos++
	if f.after != nil {
		f.after(node)
	}
}

func (f *inspector) Token(t token.Token) {
	f.current.pos++
}

func (f *inspector) setPos(i int8) {
	f.current.pos = i
}

func (f *inspector) visitComments(pos int8) {
	c := &f.current
	for ; len(c.cg) > 0; c.cg = c.cg[1:] {
		cg := c.cg[0]
		if cg.Position == pos {
			continue
		}
		if f.before == nil || f.before(cg) {
			for _, c := range cg.List {
				if f.before == nil || f.before(c) {
					if f.after != nil {
						f.after(c)
					}
				}
			}
			if f.after != nil {
				f.after(cg)
			}
		}
	}
}