func (dq *typeDeque) shift() *Type {
	if dq.read == dq.write {
		return nil
	}
	index := dq.read & dq.mask
	t := dq.types[index]
	dq.types[index] = nil
	dq.read++
	return t
}
shift returns the first element or null.
package btf
import (
	"fmt"
	"math"
	"strings"
)
const maxTypeDepth = 32
type TypeID uint32
func (tid TypeID) ID() TypeID {
	return tid
}
type Type interface {
	ID() TypeID
	String() string
	copy() Type
	walk(*typeDeque)
}
type namedType interface {
	Type
	name() string
	essentialName() string
}
type Name string
func (n Name) name() string {
	return string(n)
}
func (n Name) essentialName() string {
	return essentialName(string(n))
}
type Void struct{}
func (v *Void) ID() TypeID      { return 0 }
func (v *Void) String() string  { return "void#0" }
func (v *Void) size() uint32    { return 0 }
func (v *Void) copy() Type      { return (*Void)(nil) }
func (v *Void) walk(*typeDeque) {}
type IntEncoding byte
const (
	Signed IntEncoding = 1 << iota
	Char
	Bool
)
type Int struct {
	TypeID
	Name
	Size     uint32
	Encoding IntEncoding
	Offset uint32
	Bits   byte
}
var _ namedType = (*Int)(nil)
func (i *Int) String() string {
	var s strings.Builder
	switch {
	case i.Encoding&Char != 0:
		s.WriteString("char")
	case i.Encoding&Bool != 0:
		s.WriteString("bool")
	default:
		if i.Encoding&Signed == 0 {
			s.WriteRune('u')
		}
		s.WriteString("int")
		fmt.Fprintf(&s, "%d", i.Size*8)
	}
	fmt.Fprintf(&s, "#%d", i.TypeID)
	if i.Bits > 0 {
		fmt.Fprintf(&s, "[bits=%d]", i.Bits)
	}
	return s.String()
}
func (i *Int) size() uint32    { return i.Size }
func (i *Int) walk(*typeDeque) {}
func (i *Int) copy() Type {
	cpy := *i
	return &cpy
}
func (i *Int) isBitfield() bool {
	return i.Offset > 0
}
type Pointer struct {
	TypeID
	Target Type
}
func (p *Pointer) String() string {
	return fmt.Sprintf("pointer#%d[target=#%d]", p.TypeID, p.Target.ID())
}
func (p *Pointer) size() uint32        { return 8 }
func (p *Pointer) walk(tdq *typeDeque) { tdq.push(&p.Target) }
func (p *Pointer) copy() Type {
	cpy := *p
	return &cpy
}
type Array struct {
	TypeID
	Type   Type
	Nelems uint32
}
func (arr *Array) String() string {
	return fmt.Sprintf("array#%d[type=#%d n=%d]", arr.TypeID, arr.Type.ID(), arr.Nelems)
}
func (arr *Array) walk(tdq *typeDeque) { tdq.push(&arr.Type) }
func (arr *Array) copy() Type {
	cpy := *arr
	return &cpy
}
type Struct struct {
	TypeID
	Name
	Size    uint32
	Members []Member
}
func (s *Struct) String() string {
	return fmt.Sprintf("struct#%d[%q]", s.TypeID, s.Name)
}
func (s *Struct) size() uint32 { return s.Size }
func (s *Struct) walk(tdq *typeDeque) {
	for i := range s.Members {
		tdq.push(&s.Members[i].Type)
	}
}
func (s *Struct) copy() Type {
	cpy := *s
	cpy.Members = copyMembers(s.Members)
	return &cpy
}
func (s *Struct) members() []Member {
	return s.Members
}
type Union struct {
	TypeID
	Name
	Size    uint32
	Members []Member
}
func (u *Union) String() string {
	return fmt.Sprintf("union#%d[%q]", u.TypeID, u.Name)
}
func (u *Union) size() uint32 { return u.Size }
func (u *Union) walk(tdq *typeDeque) {
	for i := range u.Members {
		tdq.push(&u.Members[i].Type)
	}
}
func (u *Union) copy() Type {
	cpy := *u
	cpy.Members = copyMembers(u.Members)
	return &cpy
}
func (u *Union) members() []Member {
	return u.Members
}
func copyMembers(orig []Member) []Member {
	cpy := make([]Member, len(orig))
	copy(cpy, orig)
	return cpy
}
type composite interface {
	members() []Member
}
var (
	_ composite = (*Struct)(nil)
	_ composite = (*Union)(nil)
)
type Member struct {
	Name
	Type Type
	Offset       uint32
	BitfieldSize uint32
}
type Enum struct {
	TypeID
	Name
	Values []EnumValue
}
func (e *Enum) String() string {
	return fmt.Sprintf("enum#%d[%q]", e.TypeID, e.Name)
}
type EnumValue struct {
	Name
	Value int32
}
func (e *Enum) size() uint32    { return 4 }
func (e *Enum) walk(*typeDeque) {}
func (e *Enum) copy() Type {
	cpy := *e
	cpy.Values = make([]EnumValue, len(e.Values))
	copy(cpy.Values, e.Values)
	return &cpy
}
type FwdKind int
const (
	FwdStruct FwdKind = iota
	FwdUnion
)
func (fk FwdKind) String() string {
	switch fk {
	case FwdStruct:
		return "struct"
	case FwdUnion:
		return "union"
	default:
		return fmt.Sprintf("%T(%d)", fk, int(fk))
	}
}
type Fwd struct {
	TypeID
	Name
	Kind FwdKind
}
func (f *Fwd) String() string {
	return fmt.Sprintf("fwd#%d[%s %q]", f.TypeID, f.Kind, f.Name)
}
func (f *Fwd) walk(*typeDeque) {}
func (f *Fwd) copy() Type {
	cpy := *f
	return &cpy
}
type Typedef struct {
	TypeID
	Name
	Type Type
}
func (td *Typedef) String() string {
	return fmt.Sprintf("typedef#%d[%q #%d]", td.TypeID, td.Name, td.Type.ID())
}
func (td *Typedef) walk(tdq *typeDeque) { tdq.push(&td.Type) }
func (td *Typedef) copy() Type {
	cpy := *td
	return &cpy
}
type Volatile struct {
	TypeID
	Type Type
}
func (v *Volatile) String() string {
	return fmt.Sprintf("volatile#%d[#%d]", v.TypeID, v.Type.ID())
}
func (v *Volatile) qualify() Type       { return v.Type }
func (v *Volatile) walk(tdq *typeDeque) { tdq.push(&v.Type) }
func (v *Volatile) copy() Type {
	cpy := *v
	return &cpy
}
type Const struct {
	TypeID
	Type Type
}
func (c *Const) String() string {
	return fmt.Sprintf("const#%d[#%d]", c.TypeID, c.Type.ID())
}
func (c *Const) qualify() Type       { return c.Type }
func (c *Const) walk(tdq *typeDeque) { tdq.push(&c.Type) }
func (c *Const) copy() Type {
	cpy := *c
	return &cpy
}
type Restrict struct {
	TypeID
	Type Type
}
func (r *Restrict) String() string {
	return fmt.Sprintf("restrict#%d[#%d]", r.TypeID, r.Type.ID())
}
func (r *Restrict) qualify() Type       { return r.Type }
func (r *Restrict) walk(tdq *typeDeque) { tdq.push(&r.Type) }
func (r *Restrict) copy() Type {
	cpy := *r
	return &cpy
}
type Func struct {
	TypeID
	Name
	Type    Type
	Linkage FuncLinkage
}
func (f *Func) String() string {
	return fmt.Sprintf("func#%d[%s %q proto=#%d]", f.TypeID, f.Linkage, f.Name, f.Type.ID())
}
func (f *Func) walk(tdq *typeDeque) { tdq.push(&f.Type) }
func (f *Func) copy() Type {
	cpy := *f
	return &cpy
}
type FuncProto struct {
	TypeID
	Return Type
	Params []FuncParam
}
func (fp *FuncProto) String() string {
	var s strings.Builder
	fmt.Fprintf(&s, "proto#%d[", fp.TypeID)
	for _, param := range fp.Params {
		fmt.Fprintf(&s, "%q=#%d, ", param.Name, param.Type.ID())
	}
	fmt.Fprintf(&s, "return=#%d]", fp.Return.ID())
	return s.String()
}
func (fp *FuncProto) walk(tdq *typeDeque) {
	tdq.push(&fp.Return)
	for i := range fp.Params {
		tdq.push(&fp.Params[i].Type)
	}
}
func (fp *FuncProto) copy() Type {
	cpy := *fp
	cpy.Params = make([]FuncParam, len(fp.Params))
	copy(cpy.Params, fp.Params)
	return &cpy
}
type FuncParam struct {
	Name
	Type Type
}
type Var struct {
	TypeID
	Name
	Type    Type
	Linkage VarLinkage
}
func (v *Var) String() string {
	return fmt.Sprintf("var#%d[%s %q]", v.TypeID, v.Linkage, v.Name)
}
func (v *Var) walk(tdq *typeDeque) { tdq.push(&v.Type) }
func (v *Var) copy() Type {
	cpy := *v
	return &cpy
}
type Datasec struct {
	TypeID
	Name
	Size uint32
	Vars []VarSecinfo
}
func (ds *Datasec) String() string {
	return fmt.Sprintf("section#%d[%q]", ds.TypeID, ds.Name)
}
func (ds *Datasec) size() uint32 { return ds.Size }
func (ds *Datasec) walk(tdq *typeDeque) {
	for i := range ds.Vars {
		tdq.push(&ds.Vars[i].Type)
	}
}
func (ds *Datasec) copy() Type {
	cpy := *ds
	cpy.Vars = make([]VarSecinfo, len(ds.Vars))
	copy(cpy.Vars, ds.Vars)
	return &cpy
}
type VarSecinfo struct {
	Type   Type
	Offset uint32
	Size   uint32
}
type sizer interface {
	size() uint32
}
var (
	_ sizer = (*Int)(nil)
	_ sizer = (*Pointer)(nil)
	_ sizer = (*Struct)(nil)
	_ sizer = (*Union)(nil)
	_ sizer = (*Enum)(nil)
	_ sizer = (*Datasec)(nil)
)
type qualifier interface {
	qualify() Type
}
var (
	_ qualifier = (*Const)(nil)
	_ qualifier = (*Restrict)(nil)
	_ qualifier = (*Volatile)(nil)
)
func Sizeof(typ Type) (int, error) {
	var (
		n    = int64(1)
		elem int64
	)
	for i := 0; i < maxTypeDepth; i++ {
		switch v := typ.(type) {
		case *Array:
			if n > 0 && int64(v.Nelems) > math.MaxInt64/n {
				return 0, fmt.Errorf("type %s: overflow", typ)
			}
			n *= int64(v.Nelems)
			typ = v.Type
			continue
		case sizer:
			elem = int64(v.size())
		case *Typedef:
			typ = v.Type
			continue
		case qualifier:
			typ = v.qualify()
			continue
		default:
			return 0, fmt.Errorf("unsized type %T", typ)
		}
		if n > 0 && elem > math.MaxInt64/n {
			return 0, fmt.Errorf("type %s: overflow", typ)
		}
		size := n * elem
		if int64(int(size)) != size {
			return 0, fmt.Errorf("type %s: overflow", typ)
		}
		return int(size), nil
	}
	return 0, fmt.Errorf("type %s: exceeded type depth", typ)
}
func copyType(typ Type, transform func(Type) (Type, error)) (Type, error) {
	var (
		copies = make(map[Type]Type)
		work   typeDeque
	)
	for t := &typ; t != nil; t = work.pop() {
		if cpy := copies[*t]; cpy != nil {
			*t = cpy
			continue
		}
		var cpy Type
		if transform != nil {
			tf, err := transform(*t)
			if err != nil {
				return nil, fmt.Errorf("copy %s: %w", typ, err)
			}
			cpy = tf.copy()
		} else {
			cpy = (*t).copy()
		}
		copies[*t] = cpy
		*t = cpy
		cpy.walk(&work)
	}
	return typ, nil
}
type typeDeque struct {
	types       []*Type
	read, write uint64
	mask        uint64
}
func (dq *typeDeque) push(t *Type) {
	if dq.write-dq.read < uint64(len(dq.types)) {
		dq.types[dq.write&dq.mask] = t
		dq.write++
		return
	}
	new := len(dq.types) * 2
	if new == 0 {
		new = 8
	}
	types := make([]*Type, new)
	pivot := dq.read & dq.mask
	n := copy(types, dq.types[pivot:])
	n += copy(types[n:], dq.types[:pivot])
	types[n] = t
	dq.types = types
	dq.mask = uint64(new) - 1
	dq.read, dq.write = 0, uint64(n+1)
}