--- /dev/null
+/*
+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
projects / dotfiles / .git / blobdiff