pkg/compiler: support type templates

Netlink descriptions contain tons of code duplication,
and need much more for proper descriptions. Introduce
type templates to simplify writing such descriptions
and remove code duplication.

Note: type templates are experimental, have poor error handling
and are subject to change.

Type templates can be declared as follows:

```
type buffer[DIR] ptr[DIR, array[int8]]
type fileoff[BASE] BASE
type nlattr[TYPE, PAYLOAD] {
	nla_len		len[parent, int16]
	nla_type	const[TYPE, int16]
	payload		PAYLOAD
} [align_4]
```

and later used as follows:

```
syscall(a buffer[in], b fileoff[int64], c ptr[in, nlattr[FOO, int32]])
```

7 files changed, 180 insertions, 110 deletions

diff --git a/pkg/ast/ast.go b/pkg/ast/ast.go
index 454f28b37..08703ba33 100644
--- a/pkg/ast/ast.go
+++ b/pkg/ast/ast.go
@@ -21,9 +21,7 @@ type Description struct {
 type Node interface {
 	Info() (pos Pos, typ string, name string)
 	// Clone makes a deep copy of the node.
-	// If newPos is not zero, sets Pos of all nodes to newPos.
-	// If newPos is zero, Pos of nodes is left intact.
-	Clone(newPos Pos) Node
+	Clone() Node
 	// Walk calls callback cb for all child nodes of this node.
 	// Note: it's not recursive. Use Recursive helper for recursive walk.
 	Walk(cb func(Node))
@@ -140,7 +138,11 @@ func (n *StrFlags) Info() (Pos, string, string) {
 type TypeDef struct {
 	Pos  Pos
 	Name *Ident
-	Type *Type
+	// Non-template type aliases have only Type filled.
+	// Templates have Args and either Type or Struct filled.
+	Args   []*Ident
+	Type   *Type
+	Struct *Struct
 }
 
 func (n *TypeDef) Info() (Pos, string, string) {
diff --git a/pkg/ast/clone.go b/pkg/ast/clone.go
index dcd715c0a..b915c1f33 100644
--- a/pkg/ast/clone.go
+++ b/pkg/ast/clone.go
@@ -6,86 +6,93 @@ package ast
 func (desc *Description) Clone() *Description {
 	desc1 := &Description{}
 	for _, n := range desc.Nodes {
-		desc1.Nodes = append(desc1.Nodes, n.Clone(Pos{}))
+		desc1.Nodes = append(desc1.Nodes, n.Clone())
 	}
 	return desc1
 }
 
-func selectPos(newPos, oldPos Pos) Pos {
-	if newPos.File != "" || newPos.Off != 0 || newPos.Line != 0 || newPos.Col != 0 {
-		return newPos
-	}
-	return oldPos
-}
-
-func (n *NewLine) Clone(newPos Pos) Node {
+func (n *NewLine) Clone() Node {
 	return &NewLine{
-		Pos: selectPos(newPos, n.Pos),
+		Pos: n.Pos,
 	}
 }
 
-func (n *Comment) Clone(newPos Pos) Node {
+func (n *Comment) Clone() Node {
 	return &Comment{
-		Pos:  selectPos(newPos, n.Pos),
+		Pos:  n.Pos,
 		Text: n.Text,
 	}
 }
 
-func (n *Include) Clone(newPos Pos) Node {
+func (n *Include) Clone() Node {
 	return &Include{
-		Pos:  selectPos(newPos, n.Pos),
-		File: n.File.Clone(newPos).(*String),
+		Pos:  n.Pos,
+		File: n.File.Clone().(*String),
 	}
 }
 
-func (n *Incdir) Clone(newPos Pos) Node {
+func (n *Incdir) Clone() Node {
 	return &Incdir{
-		Pos: selectPos(newPos, n.Pos),
-		Dir: n.Dir.Clone(newPos).(*String),
+		Pos: n.Pos,
+		Dir: n.Dir.Clone().(*String),
 	}
 }
 
-func (n *Define) Clone(newPos Pos) Node {
+func (n *Define) Clone() Node {
 	return &Define{
-		Pos:   selectPos(newPos, n.Pos),
-		Name:  n.Name.Clone(newPos).(*Ident),
-		Value: n.Value.Clone(newPos).(*Int),
+		Pos:   n.Pos,
+		Name:  n.Name.Clone().(*Ident),
+		Value: n.Value.Clone().(*Int),
 	}
 }
 
-func (n *Resource) Clone(newPos Pos) Node {
+func (n *Resource) Clone() Node {
 	var values []*Int
 	for _, v := range n.Values {
-		values = append(values, v.Clone(newPos).(*Int))
+		values = append(values, v.Clone().(*Int))
 	}
 	return &Resource{
-		Pos:    selectPos(newPos, n.Pos),
-		Name:   n.Name.Clone(newPos).(*Ident),
-		Base:   n.Base.Clone(newPos).(*Type),
+		Pos:    n.Pos,
+		Name:   n.Name.Clone().(*Ident),
+		Base:   n.Base.Clone().(*Type),
 		Values: values,
 	}
 }
 
-func (n *TypeDef) Clone(newPos Pos) Node {
+func (n *TypeDef) Clone() Node {
+	var args []*Ident
+	for _, v := range n.Args {
+		args = append(args, v.Clone().(*Ident))
+	}
+	var typ *Type
+	if n.Type != nil {
+		typ = n.Type.Clone().(*Type)
+	}
+	var str *Struct
+	if n.Struct != nil {
+		str = n.Struct.Clone().(*Struct)
+	}
 	return &TypeDef{
-		Pos:  selectPos(newPos, n.Pos),
-		Name: n.Name.Clone(newPos).(*Ident),
-		Type: n.Type.Clone(newPos).(*Type),
+		Pos:    n.Pos,
+		Name:   n.Name.Clone().(*Ident),
+		Args:   args,
+		Type:   typ,
+		Struct: str,
 	}
 }
 
-func (n *Call) Clone(newPos Pos) Node {
+func (n *Call) Clone() Node {
 	var args []*Field
 	for _, a := range n.Args {
-		args = append(args, a.Clone(newPos).(*Field))
+		args = append(args, a.Clone().(*Field))
 	}
 	var ret *Type
 	if n.Ret != nil {
-		ret = n.Ret.Clone(newPos).(*Type)
+		ret = n.Ret.Clone().(*Type)
 	}
 	return &Call{
-		Pos:      selectPos(newPos, n.Pos),
-		Name:     n.Name.Clone(newPos).(*Ident),
+		Pos:      n.Pos,
+		Name:     n.Name.Clone().(*Ident),
 		CallName: n.CallName,
 		NR:       n.NR,
 		Args:     args,
@@ -93,22 +100,22 @@ func (n *Call) Clone(newPos Pos) Node {
 	}
 }
 
-func (n *Struct) Clone(newPos Pos) Node {
+func (n *Struct) Clone() Node {
 	var fields []*Field
 	for _, f := range n.Fields {
-		fields = append(fields, f.Clone(newPos).(*Field))
+		fields = append(fields, f.Clone().(*Field))
 	}
 	var attrs []*Ident
 	for _, a := range n.Attrs {
-		attrs = append(attrs, a.Clone(newPos).(*Ident))
+		attrs = append(attrs, a.Clone().(*Ident))
 	}
 	var comments []*Comment
 	for _, c := range n.Comments {
-		comments = append(comments, c.Clone(newPos).(*Comment))
+		comments = append(comments, c.Clone().(*Comment))
 	}
 	return &Struct{
-		Pos:      selectPos(newPos, n.Pos),
-		Name:     n.Name.Clone(newPos).(*Ident),
+		Pos:      n.Pos,
+		Name:     n.Name.Clone().(*Ident),
 		Fields:   fields,
 		Attrs:    attrs,
 		Comments: comments,
@@ -116,47 +123,47 @@ func (n *Struct) Clone(newPos Pos) Node {
 	}
 }
 
-func (n *IntFlags) Clone(newPos Pos) Node {
+func (n *IntFlags) Clone() Node {
 	var values []*Int
 	for _, v := range n.Values {
-		values = append(values, v.Clone(newPos).(*Int))
+		values = append(values, v.Clone().(*Int))
 	}
 	return &IntFlags{
-		Pos:    selectPos(newPos, n.Pos),
-		Name:   n.Name.Clone(newPos).(*Ident),
+		Pos:    n.Pos,
+		Name:   n.Name.Clone().(*Ident),
 		Values: values,
 	}
 }
 
-func (n *StrFlags) Clone(newPos Pos) Node {
+func (n *StrFlags) Clone() Node {
 	var values []*String
 	for _, v := range n.Values {
-		values = append(values, v.Clone(newPos).(*String))
+		values = append(values, v.Clone().(*String))
 	}
 	return &StrFlags{
-		Pos:    selectPos(newPos, n.Pos),
-		Name:   n.Name.Clone(newPos).(*Ident),
+		Pos:    n.Pos,
+		Name:   n.Name.Clone().(*Ident),
 		Values: values,
 	}
 }
 
-func (n *Ident) Clone(newPos Pos) Node {
+func (n *Ident) Clone() Node {
 	return &Ident{
-		Pos:  selectPos(newPos, n.Pos),
+		Pos:  n.Pos,
 		Name: n.Name,
 	}
 }
 
-func (n *String) Clone(newPos Pos) Node {
+func (n *String) Clone() Node {
 	return &String{
-		Pos:   selectPos(newPos, n.Pos),
+		Pos:   n.Pos,
 		Value: n.Value,
 	}
 }
 
-func (n *Int) Clone(newPos Pos) Node {
+func (n *Int) Clone() Node {
 	return &Int{
-		Pos:      selectPos(newPos, n.Pos),
+		Pos:      n.Pos,
 		Value:    n.Value,
 		ValueHex: n.ValueHex,
 		Ident:    n.Ident,
@@ -164,19 +171,19 @@ func (n *Int) Clone(newPos Pos) Node {
 	}
 }
 
-func (n *Type) Clone(newPos Pos) Node {
+func (n *Type) Clone() Node {
 	var args []*Type
 	for _, a := range n.Args {
-		args = append(args, a.Clone(newPos).(*Type))
+		args = append(args, a.Clone().(*Type))
 	}
 	return &Type{
-		Pos:       selectPos(newPos, n.Pos),
+		Pos:       n.Pos,
 		Value:     n.Value,
 		ValueHex:  n.ValueHex,
 		Ident:     n.Ident,
 		String:    n.String,
 		HasColon:  n.HasColon,
-		Pos2:      selectPos(newPos, n.Pos2),
+		Pos2:      n.Pos2,
 		Value2:    n.Value2,
 		Value2Hex: n.Value2Hex,
 		Ident2:    n.Ident2,
@@ -184,15 +191,15 @@ func (n *Type) Clone(newPos Pos) Node {
 	}
 }
 
-func (n *Field) Clone(newPos Pos) Node {
+func (n *Field) Clone() Node {
 	var comments []*Comment
 	for _, c := range n.Comments {
-		comments = append(comments, c.Clone(newPos).(*Comment))
+		comments = append(comments, c.Clone().(*Comment))
 	}
 	return &Field{
-		Pos:      selectPos(newPos, n.Pos),
-		Name:     n.Name.Clone(newPos).(*Ident),
-		Type:     n.Type.Clone(newPos).(*Type),
+		Pos:      n.Pos,
+		Name:     n.Name.Clone().(*Ident),
+		Type:     n.Type.Clone().(*Type),
 		NewBlock: n.NewBlock,
 		Comments: comments,
 	}
diff --git a/pkg/ast/format.go b/pkg/ast/format.go
index a77662df8..c1dd3a624 100644
--- a/pkg/ast/format.go
+++ b/pkg/ast/format.go
@@ -25,6 +25,16 @@ func FormatWriter(w io.Writer, desc *Description) {
 	}
 }
 
+func SerializeNode(n Node) string {
+	s, ok := n.(serializer)
+	if !ok {
+		panic(fmt.Sprintf("unknown node: %#v", n))
+	}
+	buf := new(bytes.Buffer)
+	s.serialize(buf)
+	return buf.String()
+}
+
 type serializer interface {
 	serialize(w io.Writer)
 }
@@ -52,27 +62,25 @@ func (def *Define) serialize(w io.Writer) {
 func (res *Resource) serialize(w io.Writer) {
 	fmt.Fprintf(w, "resource %v[%v]", res.Name.Name, fmtType(res.Base))
 	for i, v := range res.Values {
-		if i == 0 {
-			fmt.Fprintf(w, ": ")
-		} else {
-			fmt.Fprintf(w, ", ")
-		}
-		fmt.Fprintf(w, "%v", fmtInt(v))
+		fmt.Fprintf(w, "%v%v", comma(i, ": "), fmtInt(v))
 	}
 	fmt.Fprintf(w, "\n")
 }
 
 func (typedef *TypeDef) serialize(w io.Writer) {
-	fmt.Fprintf(w, "type %v %v\n", typedef.Name.Name, fmtType(typedef.Type))
+	fmt.Fprintf(w, "type %v%v", typedef.Name.Name, fmtIdentList(typedef.Args, false))
+	if typedef.Type != nil {
+		fmt.Fprintf(w, " %v\n", fmtType(typedef.Type))
+	}
+	if typedef.Struct != nil {
+		typedef.Struct.serialize(w)
+	}
 }
 
 func (c *Call) serialize(w io.Writer) {
 	fmt.Fprintf(w, "%v(", c.Name.Name)
 	for i, a := range c.Args {
-		if i != 0 {
-			fmt.Fprintf(w, ", ")
-		}
-		fmt.Fprintf(w, "%v", fmtField(a))
+		fmt.Fprintf(w, "%v%v", comma(i, ""), fmtField(a))
 	}
 	fmt.Fprintf(w, ")")
 	if c.Ret != nil {
@@ -112,24 +120,13 @@ func (str *Struct) serialize(w io.Writer) {
 	for _, com := range str.Comments {
 		fmt.Fprintf(w, "#%v\n", com.Text)
 	}
-	fmt.Fprintf(w, "%c", closing)
-	if len(str.Attrs) != 0 {
-		fmt.Fprintf(w, " [")
-		for i, attr := range str.Attrs {
-			fmt.Fprintf(w, "%v%v", comma(i), attr.Name)
-		}
-		fmt.Fprintf(w, "]")
-	}
-	fmt.Fprintf(w, "\n")
+	fmt.Fprintf(w, "%c%v\n", closing, fmtIdentList(str.Attrs, true))
 }
 
 func (flags *IntFlags) serialize(w io.Writer) {
 	fmt.Fprintf(w, "%v = ", flags.Name.Name)
 	for i, v := range flags.Values {
-		if i != 0 {
-			fmt.Fprintf(w, ", ")
-		}
-		fmt.Fprintf(w, "%v", fmtInt(v))
+		fmt.Fprintf(w, "%v%v", comma(i, ""), fmtInt(v))
 	}
 	fmt.Fprintf(w, "\n")
 }
@@ -137,10 +134,7 @@ func (flags *IntFlags) serialize(w io.Writer) {
 func (flags *StrFlags) serialize(w io.Writer) {
 	fmt.Fprintf(w, "%v = ", flags.Name.Name)
 	for i, v := range flags.Values {
-		if i != 0 {
-			fmt.Fprintf(w, ", ")
-		}
-		fmt.Fprintf(w, "\"%v\"", v.Value)
+		fmt.Fprintf(w, "%v\"%v\"", comma(i, ""), v.Value)
 	}
 	fmt.Fprintf(w, "\n")
 }
@@ -149,6 +143,10 @@ func fmtField(f *Field) string {
 	return fmt.Sprintf("%v %v", f.Name.Name, fmtType(f.Type))
 }
 
+func (n *Type) serialize(w io.Writer) {
+	w.Write([]byte(fmtType(n)))
+}
+
 func fmtType(t *Type) string {
 	v := ""
 	switch {
@@ -178,7 +176,23 @@ func fmtTypeList(args []*Type) string {
 	w := new(bytes.Buffer)
 	fmt.Fprintf(w, "[")
 	for i, t := range args {
-		fmt.Fprintf(w, "%v%v", comma(i), fmtType(t))
+		fmt.Fprintf(w, "%v%v", comma(i, ""), fmtType(t))
+	}
+	fmt.Fprintf(w, "]")
+	return w.String()
+}
+
+func fmtIdentList(args []*Ident, space bool) string {
+	if len(args) == 0 {
+		return ""
+	}
+	w := new(bytes.Buffer)
+	if space {
+		fmt.Fprintf(w, " ")
+	}
+	fmt.Fprintf(w, "[")
+	for i, arg := range args {
+		fmt.Fprintf(w, "%v%v", comma(i, ""), arg.Name)
 	}
 	fmt.Fprintf(w, "]")
 	return w.String()
@@ -202,9 +216,9 @@ func fmtIntValue(v uint64, hex bool) string {
 	return fmt.Sprint(v)
 }
 
-func comma(i int) string {
+func comma(i int, or string) string {
 	if i == 0 {
-		return ""
+		return or
 	}
 	return ", "
 }
diff --git a/pkg/ast/parser.go b/pkg/ast/parser.go
index db211ab2a..bd5650ad5 100644
--- a/pkg/ast/parser.go
+++ b/pkg/ast/parser.go
@@ -251,11 +251,34 @@ func (p *parser) parseResource() *Resource {
 func (p *parser) parseTypeDef() *TypeDef {
 	pos0 := p.pos
 	name := p.parseIdent()
-	typ := p.parseType()
+	var typ *Type
+	var str *Struct
+	var args []*Ident
+	p.expect(tokLBrack, tokIdent)
+	if p.tryConsume(tokLBrack) {
+		args = append(args, p.parseIdent())
+		for p.tryConsume(tokComma) {
+			args = append(args, p.parseIdent())
+		}
+		p.consume(tokRBrack)
+		if p.tok == tokLBrace || p.tok == tokLBrack {
+			name := &Ident{
+				Pos:  pos0,
+				Name: "",
+			}
+			str = p.parseStruct(name)
+		} else {
+			typ = p.parseType()
+		}
+	} else {
+		typ = p.parseType()
+	}
 	return &TypeDef{
-		Pos:  pos0,
-		Name: name,
-		Type: typ,
+		Pos:    pos0,
+		Name:   name,
+		Args:   args,
+		Type:   typ,
+		Struct: str,
 	}
 }
 
diff --git a/pkg/ast/test_util.go b/pkg/ast/test_util.go
index 0aed0a2dc..b9fe12152 100644
--- a/pkg/ast/test_util.go
+++ b/pkg/ast/test_util.go
@@ -7,6 +7,7 @@ import (
 	"bufio"
 	"bytes"
 	"io/ioutil"
+	"path/filepath"
 	"strings"
 	"testing"
 )
@@ -41,7 +42,7 @@ func NewErrorMatcher(t *testing.T, file string) *ErrorMatcher {
 				break
 			}
 			errors = append(errors, &errorDesc{
-				file: file,
+				file: filepath.Base(file),
 				line: i,
 				text: strings.TrimSpace(string(ln[pos+3:])),
 			})
@@ -82,13 +83,13 @@ nextErr:
 			want.matched = true
 			continue nextErr
 		}
-		t.Errorf("unexpected error: %v:%v:%v: %v", e.file, e.line, e.col, e.text)
+		t.Errorf("unexpected error:\n%v:%v:%v: %v", e.file, e.line, e.col, e.text)
 	}
 	for _, want := range em.expect {
 		if want.matched {
 			continue
 		}
-		t.Errorf("unmatched error: %v:%v: %v", want.file, want.line, want.text)
+		t.Errorf("unmatched error:\n%v:%v: %v", want.file, want.line, want.text)
 	}
 }
 
diff --git a/pkg/ast/testdata/all.txt b/pkg/ast/testdata/all.txt
index 268b49a47..d4452b34f 100644
--- a/pkg/ast/testdata/all.txt
+++ b/pkg/ast/testdata/all.txt
@@ -48,5 +48,20 @@ s2 {
 
 type mybool8 int8
 type net_port proc[1, 2, int16be]
-type mybool16				### unexpected '\n', expecting int, identifier, string
-type type4:4 int32			### unexpected ':', expecting int, identifier, string
+type mybool16				### unexpected '\n', expecting '[', identifier
+type type4:4 int32			### unexpected ':', expecting '[', identifier
+
+type templ0[] int8			### unexpected ']', expecting identifier
+type templ1[A,] int8			### unexpected ']', expecting identifier
+type templ2[,] int8			### unexpected ',', expecting identifier
+type templ3[				### unexpected '\n', expecting identifier
+type templ4[A]				### unexpected '\n', expecting int, identifier, string
+type templ5[A] const[A]
+type templ6[A, B] const[A, B]
+type templ7[0] ptr[in, int8]		### unexpected int, expecting identifier
+
+type templ_struct0[A, B] {
+	len	len[parent, int16]
+	typ	const[A, int16]
+	data	B
+} [align_4]
diff --git a/pkg/ast/walk.go b/pkg/ast/walk.go
index fd5065013..fe9112578 100644
--- a/pkg/ast/walk.go
+++ b/pkg/ast/walk.go
@@ -49,7 +49,15 @@ func (n *Resource) Walk(cb func(Node)) {
 
 func (n *TypeDef) Walk(cb func(Node)) {
 	cb(n.Name)
-	cb(n.Type)
+	for _, a := range n.Args {
+		cb(a)
+	}
+	if n.Type != nil {
+		cb(n.Type)
+	}
+	if n.Struct != nil {
+		cb(n.Struct)
+	}
 }
 
 func (n *Call) Walk(cb func(Node)) {