prog: remove StructDesc

Remove StructDesc, KeyedStruct, StructKey and all associated
logic/complexity in prog and pkg/compiler.
We can now handle recursion more generically with the Ref type,
and Dir/FieldName are not a part of the type anymore.
This makes StructType/UnionType simpler and more natural.

Reduces size of sys/linux/gen/amd64.go from 5201321 to 4180861 (-20%).

Update #1580

8 files changed, 162 insertions, 189 deletions

diff --git a/prog/any.go b/prog/any.go
index 1ce444ce2..ce3736a4b 100644
--- a/prog/any.go
+++ b/prog/any.go
@@ -36,7 +36,12 @@ type anyTypes struct {
 //	resoct	fmt[oct, ANYRES64]
 // ] [varlen]
 func initAnyTypes(target *Target) {
-	target.any.union = &UnionType{}
+	target.any.union = &UnionType{
+		TypeCommon: TypeCommon{
+			TypeName: "ANYUNION",
+			IsVarlen: true,
+		},
+	}
 	target.any.array = &ArrayType{
 		TypeCommon: TypeCommon{
 			TypeName: "ANYARRAY",
@@ -89,20 +94,14 @@ func initAnyTypes(target *Target) {
 	target.any.resdec = createResource("ANYRESDEC", "int64", FormatStrDec, 20)
 	target.any.reshex = createResource("ANYRESHEX", "int64", FormatStrHex, 18)
 	target.any.resoct = createResource("ANYRESOCT", "int64", FormatStrOct, 23)
-	target.any.union.StructDesc = &StructDesc{
-		TypeCommon: TypeCommon{
-			TypeName: "ANYUNION",
-			IsVarlen: true,
-		},
-		Fields: []Field{
-			{Name: "ANYBLOB", Type: target.any.blob},
-			{Name: "ANYRES16", Type: target.any.res16},
-			{Name: "ANYRES32", Type: target.any.res32},
-			{Name: "ANYRES64", Type: target.any.res64},
-			{Name: "ANYRESDEC", Type: target.any.resdec},
-			{Name: "ANYRESHEX", Type: target.any.reshex},
-			{Name: "ANYRESOCT", Type: target.any.resoct},
-		},
+	target.any.union.Fields = []Field{
+		{Name: "ANYBLOB", Type: target.any.blob},
+		{Name: "ANYRES16", Type: target.any.res16},
+		{Name: "ANYRES32", Type: target.any.res32},
+		{Name: "ANYRES64", Type: target.any.res64},
+		{Name: "ANYRESDEC", Type: target.any.resdec},
+		{Name: "ANYRESHEX", Type: target.any.reshex},
+		{Name: "ANYRESOCT", Type: target.any.resoct},
 	}
 }
 
diff --git a/prog/prio.go b/prog/prio.go
index 43668d48d..648af0422 100644
--- a/prog/prio.go
+++ b/prog/prio.go
@@ -64,56 +64,55 @@ func (target *Target) calcStaticPriorities() [][]float32 {
 
 func (target *Target) calcResourceUsage() map[string]map[int]weights {
 	uses := make(map[string]map[int]weights)
-	for _, c := range target.Syscalls {
-		foreachType(c, func(t Type, ctx typeCtx) {
-			switch a := t.(type) {
-			case *ResourceType:
-				if target.AuxResources[a.Desc.Name] {
-					noteUsage(uses, c, 0.1, ctx.Dir, "res%v", a.Desc.Name)
-				} else {
-					str := "res"
-					for i, k := range a.Desc.Kind {
-						str += "-" + k
-						w := 1.0
-						if i < len(a.Desc.Kind)-1 {
-							w = 0.2
-						}
-						noteUsage(uses, c, float32(w), ctx.Dir, str)
+	ForeachType(target.Syscalls, func(t Type, ctx TypeCtx) {
+		c := ctx.Meta
+		switch a := t.(type) {
+		case *ResourceType:
+			if target.AuxResources[a.Desc.Name] {
+				noteUsage(uses, c, 0.1, ctx.Dir, "res%v", a.Desc.Name)
+			} else {
+				str := "res"
+				for i, k := range a.Desc.Kind {
+					str += "-" + k
+					w := 1.0
+					if i < len(a.Desc.Kind)-1 {
+						w = 0.2
 					}
+					noteUsage(uses, c, float32(w), ctx.Dir, str)
 				}
-			case *PtrType:
-				if _, ok := a.Elem.(*StructType); ok {
-					noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name())
-				}
-				if _, ok := a.Elem.(*UnionType); ok {
-					noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name())
-				}
-				if arr, ok := a.Elem.(*ArrayType); ok {
-					noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", arr.Elem.Name())
-				}
-			case *BufferType:
-				switch a.Kind {
-				case BufferBlobRand, BufferBlobRange, BufferText:
-				case BufferString:
-					if a.SubKind != "" {
-						noteUsage(uses, c, 0.2, ctx.Dir, fmt.Sprintf("str-%v", a.SubKind))
-					}
-				case BufferFilename:
-					noteUsage(uses, c, 1.0, DirIn, "filename")
-				default:
-					panic("unknown buffer kind")
-				}
-			case *VmaType:
-				noteUsage(uses, c, 0.5, ctx.Dir, "vma")
-			case *IntType:
-				switch a.Kind {
-				case IntPlain, IntRange:
-				default:
-					panic("unknown int kind")
+			}
+		case *PtrType:
+			if _, ok := a.Elem.(*StructType); ok {
+				noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name())
+			}
+			if _, ok := a.Elem.(*UnionType); ok {
+				noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", a.Elem.Name())
+			}
+			if arr, ok := a.Elem.(*ArrayType); ok {
+				noteUsage(uses, c, 1.0, ctx.Dir, "ptrto-%v", arr.Elem.Name())
+			}
+		case *BufferType:
+			switch a.Kind {
+			case BufferBlobRand, BufferBlobRange, BufferText:
+			case BufferString:
+				if a.SubKind != "" {
+					noteUsage(uses, c, 0.2, ctx.Dir, fmt.Sprintf("str-%v", a.SubKind))
 				}
+			case BufferFilename:
+				noteUsage(uses, c, 1.0, DirIn, "filename")
+			default:
+				panic("unknown buffer kind")
 			}
-		})
-	}
+		case *VmaType:
+			noteUsage(uses, c, 0.5, ctx.Dir, "vma")
+		case *IntType:
+			switch a.Kind {
+			case IntPlain, IntRange:
+			default:
+				panic("unknown int kind")
+			}
+		}
+	})
 	return uses
 }
 
diff --git a/prog/prog_test.go b/prog/prog_test.go
index 9b8f442e3..6374b6d25 100644
--- a/prog/prog_test.go
+++ b/prog/prog_test.go
@@ -20,15 +20,13 @@ func TestGeneration(t *testing.T) {
 
 func TestDefault(t *testing.T) {
 	target, _, _ := initTest(t)
-	for _, meta := range target.Syscalls {
-		foreachType(meta, func(typ Type, ctx typeCtx) {
-			arg := typ.DefaultArg(ctx.Dir)
-			if !isDefault(arg) {
-				t.Errorf("default arg is not default: %s\ntype: %#v\narg: %#v",
-					typ, typ, arg)
-			}
-		})
-	}
+	ForeachType(target.Syscalls, func(typ Type, ctx TypeCtx) {
+		arg := typ.DefaultArg(ctx.Dir)
+		if !isDefault(arg) {
+			t.Errorf("default arg is not default: %s\ntype: %#v\narg: %#v",
+				typ, typ, arg)
+		}
+	})
 }
 
 func TestDefaultCallArgs(t *testing.T) {
@@ -203,7 +201,7 @@ func TestSpecialStructs(t *testing.T) {
 			t.Run(special, func(t *testing.T) {
 				var typ Type
 				for i := 0; i < len(target.Syscalls) && typ == nil; i++ {
-					foreachType(target.Syscalls[i], func(t Type, ctx typeCtx) {
+					ForeachCallType(target.Syscalls[i], func(t Type, ctx TypeCtx) {
 						if ctx.Dir == DirOut {
 							return
 						}
diff --git a/prog/rand_test.go b/prog/rand_test.go
index 6f251cb7c..da0871505 100644
--- a/prog/rand_test.go
+++ b/prog/rand_test.go
@@ -101,22 +101,20 @@ func TestEnabledCalls(t *testing.T) {
 func TestSizeGenerateConstArg(t *testing.T) {
 	target, rs, iters := initRandomTargetTest(t, "test", "64")
 	r := newRand(target, rs)
-	for _, c := range target.Syscalls {
-		foreachType(c, func(typ Type, ctx typeCtx) {
-			if _, ok := typ.(*IntType); !ok {
-				return
-			}
-			bits := typ.TypeBitSize()
-			limit := uint64(1<<bits - 1)
-			for i := 0; i < iters; i++ {
-				newArg, _ := typ.generate(r, nil, ctx.Dir)
-				newVal := newArg.(*ConstArg).Val
-				if newVal > limit {
-					t.Fatalf("invalid generated value: %d. (arg bitsize: %d; max value: %d)", newVal, bits, limit)
-				}
+	ForeachType(target.Syscalls, func(typ Type, ctx TypeCtx) {
+		if _, ok := typ.(*IntType); !ok {
+			return
+		}
+		bits := typ.TypeBitSize()
+		limit := uint64(1<<bits - 1)
+		for i := 0; i < iters; i++ {
+			newArg, _ := typ.generate(r, nil, ctx.Dir)
+			newVal := newArg.(*ConstArg).Val
+			if newVal > limit {
+				t.Fatalf("invalid generated value: %d. (arg bitsize: %d; max value: %d)", newVal, bits, limit)
 			}
-		})
-	}
+		}
+	})
 }
 
 func TestFlags(t *testing.T) {
diff --git a/prog/resources.go b/prog/resources.go
index b7bcecf95..311eb72dd 100644
--- a/prog/resources.go
+++ b/prog/resources.go
@@ -45,16 +45,14 @@ func (target *Target) calcResourceCtors(res *ResourceDesc, precise bool) []*Sysc
 func (target *Target) populateResourceCtors() {
 	// Find resources that are created by each call.
 	callsResources := make([][]*ResourceDesc, len(target.Syscalls))
-	for call, meta := range target.Syscalls {
-		foreachType(meta, func(typ Type, ctx typeCtx) {
-			switch typ1 := typ.(type) {
-			case *ResourceType:
-				if ctx.Dir != DirIn {
-					callsResources[call] = append(callsResources[call], typ1.Desc)
-				}
+	ForeachType(target.Syscalls, func(typ Type, ctx TypeCtx) {
+		switch typ1 := typ.(type) {
+		case *ResourceType:
+			if ctx.Dir != DirIn {
+				callsResources[ctx.Meta.ID] = append(callsResources[ctx.Meta.ID], typ1.Desc)
 			}
-		})
-	}
+		}
+	})
 
 	// Populate resource ctors accounting for resource compatibility.
 	for _, res := range target.Resources {
@@ -126,7 +124,7 @@ func isCompatibleResourceImpl(dst, src []string, precise bool) bool {
 
 func (target *Target) getInputResources(c *Syscall) []*ResourceDesc {
 	var resources []*ResourceDesc
-	foreachType(c, func(typ Type, ctx typeCtx) {
+	ForeachCallType(c, func(typ Type, ctx TypeCtx) {
 		if ctx.Dir == DirOut {
 			return
 		}
@@ -146,7 +144,7 @@ func (target *Target) getInputResources(c *Syscall) []*ResourceDesc {
 
 func (target *Target) getOutputResources(c *Syscall) []*ResourceDesc {
 	var resources []*ResourceDesc
-	foreachType(c, func(typ Type, ctx typeCtx) {
+	ForeachCallType(c, func(typ Type, ctx TypeCtx) {
 		switch typ1 := typ.(type) {
 		case *ResourceType:
 			if ctx.Dir != DirIn {
diff --git a/prog/rotation.go b/prog/rotation.go
index 47ee2ca81..0171e6ace 100644
--- a/prog/rotation.go
+++ b/prog/rotation.go
@@ -50,7 +50,7 @@ func MakeRotator(target *Target, calls map[*Syscall]bool, rnd *rand.Rand) *Rotat
 		}
 		// VMAs and filenames are effectively resources for our purposes
 		// (but they don't have ctors).
-		foreachType(call, func(t Type, _ typeCtx) {
+		ForeachCallType(call, func(t Type, _ TypeCtx) {
 			switch a := t.(type) {
 			case *BufferType:
 				switch a.Kind {
diff --git a/prog/target.go b/prog/target.go
index 89940a61a..8999f25ac 100644
--- a/prog/target.go
+++ b/prog/target.go
@@ -22,7 +22,6 @@ type Target struct {
 
 	Syscalls  []*Syscall
 	Resources []*ResourceDesc
-	Structs   []*KeyedStruct
 	Consts    []ConstValue
 	Types     []Type
 
@@ -137,8 +136,7 @@ func (target *Target) initTarget() {
 		target.ConstMap[c.Name] = c.Value
 	}
 
-	target.resourceMap = restoreLinks(target.Syscalls, target.Resources, target.Structs, target.Types)
-	target.Structs = nil
+	target.resourceMap = restoreLinks(target.Syscalls, target.Resources, target.Types)
 	target.Types = nil
 
 	target.SyscallMap = make(map[string]*Syscall)
@@ -173,63 +171,30 @@ func (target *Target) sanitize(c *Call, fix bool) error {
 	return nil
 }
 
-func RestoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct, types []Type) {
-	restoreLinks(syscalls, resources, structs, types)
+func RestoreLinks(syscalls []*Syscall, resources []*ResourceDesc, types []Type) {
+	restoreLinks(syscalls, resources, types)
 }
 
-func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, structs []*KeyedStruct,
-	types []Type) map[string]*ResourceDesc {
+func restoreLinks(syscalls []*Syscall, resources []*ResourceDesc, types []Type) map[string]*ResourceDesc {
 	resourceMap := make(map[string]*ResourceDesc)
 	for _, res := range resources {
 		resourceMap[res.Name] = res
 	}
-	keyedStructs := make(map[StructKey]*StructDesc)
-	for _, desc := range structs {
-		keyedStructs[desc.Key] = desc.Desc
-		for i := range desc.Desc.Fields {
-			unref(&desc.Desc.Fields[i].Type, types)
+	ForeachType(syscalls, func(_ Type, ctx TypeCtx) {
+		if ref, ok := (*ctx.Ptr).(Ref); ok {
+			*ctx.Ptr = types[ref]
 		}
-	}
-	for _, c := range syscalls {
-		for i := range c.Args {
-			unref(&c.Args[i].Type, types)
-		}
-		if c.Ret != nil {
-			unref(&c.Ret, types)
-		}
-		foreachType(c, func(t0 Type, _ typeCtx) {
-			switch t := t0.(type) {
-			case *PtrType:
-				unref(&t.Elem, types)
-			case *ArrayType:
-				unref(&t.Elem, types)
-			case *ResourceType:
-				t.Desc = resourceMap[t.TypeName]
-				if t.Desc == nil {
-					panic("no resource desc")
-				}
-			case *StructType:
-				t.StructDesc = keyedStructs[t.Key]
-				if t.StructDesc == nil {
-					panic("no struct desc")
-				}
-			case *UnionType:
-				t.StructDesc = keyedStructs[t.Key]
-				if t.StructDesc == nil {
-					panic("no union desc")
-				}
+		switch t := (*ctx.Ptr).(type) {
+		case *ResourceType:
+			t.Desc = resourceMap[t.TypeName]
+			if t.Desc == nil {
+				panic("no resource desc")
 			}
-		})
-	}
+		}
+	})
 	return resourceMap
 }
 
-func unref(tp *Type, types []Type) {
-	if ref, ok := (*tp).(Ref); ok {
-		*tp = types[ref]
-	}
-}
-
 type Gen struct {
 	r *randGen
 	s *state
diff --git a/prog/types.go b/prog/types.go
index 4412239d3..33c7bd356 100644
--- a/prog/types.go
+++ b/prog/types.go
@@ -110,7 +110,6 @@ type Ref uint32
 
 func (ti Ref) String() string       { panic("prog.Ref method called") }
 func (ti Ref) Name() string         { panic("prog.Ref method called") }
-func (ti Ref) FieldName() string    { panic("prog.Ref method called") }
 func (ti Ref) TemplateName() string { panic("prog.Ref method called") }
 
 func (ti Ref) Optional() bool                                        { panic("prog.Ref method called") }
@@ -579,8 +578,9 @@ func (t *PtrType) isDefaultArg(arg Arg) bool {
 }
 
 type StructType struct {
-	Key StructKey
-	*StructDesc
+	TypeCommon
+	Fields    []Field
+	AlignAttr uint64
 }
 
 func (t *StructType) String() string {
@@ -606,8 +606,8 @@ func (t *StructType) isDefaultArg(arg Arg) bool {
 }
 
 type UnionType struct {
-	Key StructKey
-	*StructDesc
+	TypeCommon
+	Fields []Field
 }
 
 func (t *UnionType) String() string {
@@ -623,64 +623,80 @@ func (t *UnionType) isDefaultArg(arg Arg) bool {
 	return a.Index == 0 && isDefault(a.Option)
 }
 
-type StructDesc struct {
-	TypeCommon
-	Fields    []Field
-	AlignAttr uint64
+type ConstValue struct {
+	Name  string
+	Value uint64
 }
 
-type StructKey struct {
-	Name string
+type TypeCtx struct {
+	Meta *Syscall
+	Dir  Dir
+	Ptr  *Type
 }
 
-type KeyedStruct struct {
-	Key  StructKey
-	Desc *StructDesc
+func ForeachType(syscalls []*Syscall, f func(t Type, ctx TypeCtx)) {
+	for _, meta := range syscalls {
+		foreachTypeImpl(meta, true, f)
+	}
 }
 
-type ConstValue struct {
-	Name  string
-	Value uint64
+func ForeachTypePost(syscalls []*Syscall, f func(t Type, ctx TypeCtx)) {
+	for _, meta := range syscalls {
+		foreachTypeImpl(meta, false, f)
+	}
 }
 
-type typeCtx struct {
-	Dir Dir
+func ForeachCallType(meta *Syscall, f func(t Type, ctx TypeCtx)) {
+	foreachTypeImpl(meta, true, f)
 }
 
-func foreachType(meta *Syscall, f func(t Type, ctx typeCtx)) {
-	var rec func(t Type, dir Dir)
-	seen := make(map[*StructDesc]bool)
-	recStruct := func(desc *StructDesc, dir Dir) {
-		if seen[desc] {
-			return // prune recursion via pointers to structs/unions
-		}
-		seen[desc] = true
-		for _, f := range desc.Fields {
-			rec(f.Type, dir)
+func foreachTypeImpl(meta *Syscall, preorder bool, f func(t Type, ctx TypeCtx)) {
+	// Note: we specifically don't create seen in ForeachType.
+	// It would prune recursion more (across syscalls), but lots of users need to
+	// visit each struct per-syscall (e.g. prio, used resources).
+	seen := make(map[Type]bool)
+	var rec func(*Type, Dir)
+	rec = func(ptr *Type, dir Dir) {
+		if preorder {
+			f(*ptr, TypeCtx{Meta: meta, Dir: dir, Ptr: ptr})
 		}
-	}
-	rec = func(t Type, dir Dir) {
-		f(t, typeCtx{Dir: dir})
-		switch a := t.(type) {
+		switch a := (*ptr).(type) {
 		case *PtrType:
-			rec(a.Elem, a.ElemDir)
+			rec(&a.Elem, a.ElemDir)
 		case *ArrayType:
-			rec(a.Elem, dir)
+			rec(&a.Elem, dir)
 		case *StructType:
-			recStruct(a.StructDesc, dir)
+			if seen[a] {
+				break // prune recursion via pointers to structs/unions
+			}
+			seen[a] = true
+			for i := range a.Fields {
+				rec(&a.Fields[i].Type, dir)
+			}
 		case *UnionType:
-			recStruct(a.StructDesc, dir)
-		case *ResourceType, *BufferType, *VmaType, *LenType,
-			*FlagsType, *ConstType, *IntType, *ProcType, *CsumType:
+			if seen[a] {
+				break // prune recursion via pointers to structs/unions
+			}
+			seen[a] = true
+			for i := range a.Fields {
+				rec(&a.Fields[i].Type, dir)
+			}
+		case *ResourceType, *BufferType, *VmaType, *LenType, *FlagsType,
+			*ConstType, *IntType, *ProcType, *CsumType:
+		case Ref:
+			// This is only needed for pkg/compiler.
 		default:
 			panic("unknown type")
 		}
+		if !preorder {
+			f(*ptr, TypeCtx{Meta: meta, Dir: dir, Ptr: ptr})
+		}
 	}
-	for _, field := range meta.Args {
-		rec(field.Type, DirIn)
+	for i := range meta.Args {
+		rec(&meta.Args[i].Type, DirIn)
 	}
 	if meta.Ret != nil {
-		rec(meta.Ret, DirOut)
+		rec(&meta.Ret, DirOut)
 	}
 }