PathEnclosingInterval returns the node that encloses the source interval [start, end), and all its ancestors up to the AST root.

The definition of "enclosing" used by this function considers additional whitespace abutting a node to be enclosed by it. In this example:

z := x + y // add them

the ast.BinaryExpr(+) node is considered to enclose interval B even though its [Pos()..End()) is actually only interval A. This behaviour makes user interfaces more tolerant of imperfect input.

This function treats tokens as nodes, though they are not included in the result. e.g. PathEnclosingInterval("+") returns the enclosing ast.BinaryExpr("x + y").

If start==end, the 1-char interval following start is used instead.

The 'exact' result is true if the interval contains only path[0] and perhaps some adjacent whitespace. It is false if the interval overlaps multiple children of path[0], or if it contains only interior whitespace of path[0]. In this example:

z := x + y // add them
  <--C-->     <---E-->

intervals C, D and E are inexact. C is contained by the z-assignment statement, because it spans three of its children (:=, x, +). So too is the 1-char interval D, because it contains only interior whitespace of the assignment. E is considered interior whitespace of the BlockStmt containing the assignment.

Precondition: [start, end) both lie within the same file as root. TODO(adonovan): return (nil, false) in this case and remove precond. Requires FileSet; see loader.tokenFileContainsPos.

Postcondition: path is never nil; it always contains at least 'root'.

PathEnclosingInterval is referenced in 0 repositories


func PathEnclosingInterval(root *ast.File, start, end token.Pos) (path []ast.Node, exact bool) {
	// fmt.Printf("EnclosingInterval %d %d\n", start, end) // debugging

	// Precondition: node.[Pos..End) and adjoining whitespace contain [start, end).
	var visit func(node ast.Node) bool
	visit = func(node ast.Node) bool {
		path = append(path, node)

		nodePos := node.Pos()
		nodeEnd := node.End()

		// fmt.Printf("visit(%T, %d, %d)\n", node, nodePos, nodeEnd) // debugging

		// Intersect [start, end) with interval of node.
		if start < nodePos {
			start = nodePos
		if end > nodeEnd {
			end = nodeEnd

		// Find sole child that contains [start, end).
		children := childrenOf(node)
		l := len(children)
		for i, child := range children {
			// [childPos, childEnd) is unaugmented interval of child.
			childPos := child.Pos()
			childEnd := child.End()

			// [augPos, augEnd) is whitespace-augmented interval of child.
			augPos := childPos
			augEnd := childEnd
			if i > 0 {
				augPos = children[i-1].End() // start of preceding whitespace
			if i < l-1 {
				nextChildPos := children[i+1].Pos()
				// Does [start, end) lie between child and next child?
				if start >= augEnd && end <= nextChildPos {
					return false // inexact match
				augEnd = nextChildPos // end of following whitespace

			// fmt.Printf("\tchild %d: [%d..%d)\tcontains interval [%d..%d)?\n",
			// 	i, augPos, augEnd, start, end) // debugging

			// Does augmented child strictly contain [start, end)?
			if augPos <= start && end <= augEnd {
				_, isToken := child.(tokenNode)
				return isToken || visit(child)

			// Does [start, end) overlap multiple children?
			// i.e. left-augmented child contains start
			// but LR-augmented child does not contain end.
			if start < childEnd && end > augEnd {

		// No single child contained [start, end),
		// so node is the result.  Is it exact?

		// (It's tempting to put this condition before the
		// child loop, but it gives the wrong result in the
		// case where a node (e.g. ExprStmt) and its sole
		// child have equal intervals.)
		if start == nodePos && end == nodeEnd {
			return true // exact match

		return false // inexact: overlaps multiple children

	if start > end {
		start, end = end, start

	if start < root.End() && end > root.Pos() {
		if start == end {
			end = start + 1 // empty interval => interval of size 1
		exact = visit(root)

		// Reverse the path:
		for i, l := 0, len(path); i < l/2; i++ {
			path[i], path[l-1-i] = path[l-1-i], path[i]
	} else {
		// Selection lies within whitespace preceding the
		// first (or following the last) declaration in the file.
		// The result nonetheless always includes the ast.File.
		path = append(path, root)