doc.go

/*
Package pattern implements a simple language for pattern matching Go ASTs.

Design decisions and trade-offs

The language is designed specifically for the task of filtering ASTs
to simplify the implementation of analyses in staticcheck.
It is also intended to be trivial to parse and execute.

To that end, we make certain decisions that make the language more
suited to its task, while making certain queries infeasible.

Furthermore, it is fully expected that the majority of analyses will still require ordinary Go code
to further process the filtered AST, to make use of type information and to enforce complex invariants.
It is not our goal to design a scripting language for writing entire checks in.

The language

At its core, patterns are a representation of Go ASTs, allowing for the use of placeholders to enable pattern matching.
Their syntax is inspired by LISP and Haskell, but unlike LISP, the core unit of patterns isn't the list, but the node.
There is a fixed set of nodes, identified by name, and with the exception of the Or node, all nodes have a fixed number of arguments.
In addition to nodes, there are atoms, which represent basic units such as strings or the nil value.

Pattern matching is implemented via bindings, represented by the Binding node.
A Binding can match nodes and associate them with names, to later recall the nodes.
This allows for expressing "this node must be equal to that node" constraints.

To simplify writing and reading patterns, a small amount of additional syntax exists on top of nodes and atoms.
This additional syntax doesn't add any new features of its own, it simply provides shortcuts to creating nodes and atoms.

To show an example of a pattern, first consider this snippet of Go code:

	if x := fn(); x != nil {
		for _, v := range x {
			println(v, x)
		}
	}

The corresponding AST expressed as an idiomatic pattern would look as follows:

	(IfStmt
		(AssignStmt (Ident "x") ":=" (CallExpr (Ident "fn") []))
		(BinaryExpr (Ident "x") "!=" (Ident "nil"))
		(RangeStmt
			(Ident "_") (Ident "v") ":=" (Ident "x")
			(CallExpr (Ident "println") [(Ident "v") (Ident "x")]))
		nil)

Two things are worth noting about this representation.
First, the [el1 el2 ...] syntax is a short-hand for creating lists.
It is a short-hand for el1:el2:[], which itself is a short-hand for (List el1 (List el2 (List nil nil)).
Second, note the absence of a lot of lists in places that normally accept lists.
For example, assignment assigns a number of right-hands to a number of left-hands, yet our AssignStmt is lacking any form of list.
This is due to the fact that a single node can match a list of exactly one element.
Thus, the two following forms have identical matching behavior:

	(AssignStmt (Ident "x") ":=" (CallExpr (Ident "fn") []))
	(AssignStmt [(Ident "x")] ":=" [(CallExpr (Ident "fn") [])])

This section serves as an overview of the language's syntax.
More in-depth explanations of the matching behavior as well as an exhaustive list of node types follows in the coming sections.

Pattern matching

TODO write about pattern matching

- inspired by haskell syntax, but much, much simpler and naive

Node types

The language contains two kinds of nodes: those that map to nodes in the AST, and those that implement additional logic.

Nodes that map directly to AST nodes are named identically to the types in the go/ast package.
What follows is an exhaustive list of these nodes:

	(ArrayType len elt)
	(AssignStmt lhs tok rhs)
	(BasicLit kind value)
	(BinaryExpr x op y)
	(BranchStmt tok label)
	(CallExpr fun args)
	(CaseClause list body)
	(ChanType dir value)
	(CommClause comm body)
	(CompositeLit type elts)
	(DeferStmt call)
	(Ellipsis elt)
	(EmptyStmt)
	(Field names type tag)
	(ForStmt init cond post body)
	(FuncDecl recv name type body)
	(FuncLit type body)
	(FuncType params results)
	(GenDecl specs)
	(GoStmt call)
	(Ident name)
	(IfStmt init cond body else)
	(ImportSpec name path)
	(IncDecStmt x tok)
	(IndexExpr x index)
	(InterfaceType methods)
	(KeyValueExpr key value)
	(MapType key value)
	(RangeStmt key value tok x body)
	(ReturnStmt results)
	(SelectStmt body)
	(SelectorExpr x sel)
	(SendStmt chan value)
	(SliceExpr x low high max)
	(StarExpr x)
	(StructType fields)
	(SwitchStmt init tag body)
	(TypeAssertExpr)
	(TypeSpec name type)
	(TypeSwitchStmt init assign body)
	(UnaryExpr op x)
	(ValueSpec names type values)

Additionally, there are the String, Token and nil atoms.
Strings are double-quoted string literals, as in (Ident "someName").
Tokens are also represented as double-quoted string literals, but are converted to token.Token values in contexts that require tokens,
such as in (BinaryExpr x "<" y), where "<" is transparently converted to token.LSS during matching.
The keyword 'nil' denotes the nil value, which represents the absence of any value.

We also defines the (List head tail) node, which is used to represent sequences of elements as a singly linked list.
The head is a single element, and the tail is the remainder of the list.
For example,

	(List "foo" (List "bar" (List "baz" (List nil nil))))

represents a list of three elements, "foo", "bar" and "baz". There is dedicated syntax for writing lists, which looks as follows:

	["foo" "bar" "baz"]

This syntax is itself syntactic sugar for the following form:

	"foo":"bar":"baz":[]

This form is of particular interest for pattern matching, as it allows matching on the head and tail. For example,

	"foo":"bar":_

would match any list with at least two elements, where the first two elements are "foo" and "bar". This is equivalent to writing

	(List "foo" (List "bar" _))

Note that it is not possible to match from the end of the list.
That is, there is no way to express a query such as "a list of any length where the last element is foo".

Note that unlike in LISP, nil and empty lists are distinct from one another.
In patterns, with respect to lists, nil is akin to Go's untyped nil.
It will match a nil ast.Node, but it will not match a nil []ast.Expr. Nil will, however, match pointers to named types such as *ast.Ident.
Similarly, lists are akin to Go's
slices. An empty list will match both a nil and an empty []ast.Expr, but it will not match a nil ast.Node.

Due to the difference between nil and empty lists, an empty list is represented as (List nil nil), i.e. a list with no head or tail.
Similarly, a list of one element is represented as (List el (List nil nil)). Unlike in LISP, it cannot be represented by (List el nil).

Finally, there are nodes that implement special logic or matching behavior.

(Any) matches any value. The underscore (_) maps to this node, making the following two forms equivalent:

	(Ident _)
	(Ident (Any))

(Builtin name) matches a built-in identifier or function by name.
This is a type-aware variant of (Ident name).
Instead of only comparing the name, it resolves the object behind the name and makes sure it's a pre-declared identifier.

For example, in the following piece of code

	func fn() {
		println(true)
		true := false
		println(true)
	}

the pattern

	(Builtin "true")

will match exactly once, on the first use of 'true' in the function.
Subsequent occurrences of 'true' no longer refer to the pre-declared identifier.

(Object name) matches an identifier by name, but yields the
types.Object it refers to.

(Function name) matches ast.Idents and ast.SelectorExprs that refer to a function with a given fully qualified name.
For example, "net/url.PathEscape" matches the PathEscape function in the net/url package,
and "(net/url.EscapeError).Error" refers to the Error method on the net/url.EscapeError type,
either on an instance of the type, or on the type itself.

For example, the following patterns match the following lines of code:

	(CallExpr (Function "fmt.Println") _) // pattern 1
	(CallExpr (Function "(net/url.EscapeError).Error") _) // pattern 2

	fmt.Println("hello, world") // matches pattern 1
	var x url.EscapeError
	x.Error() // matches pattern 2
	(url.EscapeError).Error(x) // also matches pattern 2

(Binding name node) creates or uses a binding.
Bindings work like variable assignments, allowing referring to already matched nodes.
As an example, bindings are necessary to match self-assignment of the form "x = x",
since we need to express that the right-hand side is identical to the left-hand side.

If a binding's node is not nil, the matcher will attempt to match a node according to the pattern.
If a binding's node is nil, the binding will either recall an existing value, or match the Any node.
It is an error to provide a non-nil node to a binding that has already been bound.

Referring back to the earlier example, the following pattern will match self-assignment of idents:

	(AssignStmt (Binding "lhs" (Ident _)) "=" (Binding "lhs" nil))

Because bindings are a crucial component of pattern matching, there is special syntax for creating and recalling bindings.
Lower-case names refer to bindings. If standing on its own, the name "foo" will be equivalent to (Binding "foo" nil).
If a name is followed by an at-sign (@) then it will create a binding for the node that follows.
Together, this allows us to rewrite the earlier example as follows:

	(AssignStmt lhs@(Ident _) "=" lhs)

(Or nodes...) is a variadic node that tries matching each node until one succeeds. For example, the following pattern matches all idents of name "foo" or "bar":

	(Ident (Or "foo" "bar"))

We could also have written

	(Or (Ident "foo") (Ident "bar"))

and achieved the same result. We can also mix different kinds of nodes:

	(Or (Ident "foo") (CallExpr (Ident "bar") _))

When using bindings inside of nodes used inside Or, all or none of the bindings will be bound.
That is, partially matched nodes that ultimately failed to match will not produce any bindings observable outside of the matching attempt.
We can thus write

	(Or (Ident name) (CallExpr name))

and 'name' will either be a String if the first option matched, or an Ident or SelectorExpr if the second option matched.

(Not node)

The Not node negates a match. For example, (Not (Ident _)) will match all nodes that aren't identifiers.

ChanDir(0)

Automatic unnesting of AST nodes

The Go AST has several types of nodes that wrap other nodes.
To simplify matching, we automatically unwrap some of these nodes.

These nodes are ExprStmt (for using expressions in a statement context),
ParenExpr (for parenthesized expressions),
DeclStmt (for declarations in a statement context),
and LabeledStmt (for labeled statements).

Thus, the query

	(FuncLit _ [(CallExpr _ _)]

will match a function literal containing a single function call,
even though in the actual Go AST, the CallExpr is nested inside an ExprStmt,
as function bodies are made up of sequences of statements.

On the flip-side, there is no way to specifically match these wrapper nodes.
For example, there is no way of searching for unnecessary parentheses, like in the following piece of Go code:

	((x)) += 2

*/
package pattern