// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// DWARF type information structures.
// The format is heavily biased toward C, but for simplicity
// the String methods use a pseudo-Go syntax.

package dwarf

import 

// A Type conventionally represents a pointer to any of the
// specific Type structures (CharType, StructType, etc.).
type Type interface {
	Common() *CommonType
	String() string
	Size() int64
}

// A CommonType holds fields common to multiple types.
// If a field is not known or not applicable for a given type,
// the zero value is used.
type CommonType struct {
	ByteSize int64  // size of value of this type, in bytes
	Name     string // name that can be used to refer to type
}

func ( *CommonType) () *CommonType { return  }

func ( *CommonType) () int64 { return .ByteSize }

// Basic types

// A BasicType holds fields common to all basic types.
type BasicType struct {
	CommonType
	BitSize   int64
	BitOffset int64
}

func ( *BasicType) () *BasicType { return  }

func ( *BasicType) () string {
	if .Name != "" {
		return .Name
	}
	return "?"
}

// A CharType represents a signed character type.
type CharType struct {
	BasicType
}

// A UcharType represents an unsigned character type.
type UcharType struct {
	BasicType
}

// An IntType represents a signed integer type.
type IntType struct {
	BasicType
}

// A UintType represents an unsigned integer type.
type UintType struct {
	BasicType
}

// A FloatType represents a floating point type.
type FloatType struct {
	BasicType
}

// A ComplexType represents a complex floating point type.
type ComplexType struct {
	BasicType
}

// A BoolType represents a boolean type.
type BoolType struct {
	BasicType
}

// An AddrType represents a machine address type.
type AddrType struct {
	BasicType
}

// An UnspecifiedType represents an implicit, unknown, ambiguous or nonexistent type.
type UnspecifiedType struct {
	BasicType
}

// qualifiers

// A QualType represents a type that has the C/C++ "const", "restrict", or "volatile" qualifier.
type QualType struct {
	CommonType
	Qual string
	Type Type
}

func ( *QualType) () string { return .Qual + " " + .Type.String() }

func ( *QualType) () int64 { return .Type.Size() }

// An ArrayType represents a fixed size array type.
type ArrayType struct {
	CommonType
	Type          Type
	StrideBitSize int64 // if > 0, number of bits to hold each element
	Count         int64 // if == -1, an incomplete array, like char x[].
}

func ( *ArrayType) () string {
	return "[" + strconv.FormatInt(.Count, 10) + "]" + .Type.String()
}

func ( *ArrayType) () int64 {
	if .Count == -1 {
		return 0
	}
	return .Count * .Type.Size()
}

// A VoidType represents the C void type.
type VoidType struct {
	CommonType
}

func ( *VoidType) () string { return "void" }

// A PtrType represents a pointer type.
type PtrType struct {
	CommonType
	Type Type
}

func ( *PtrType) () string { return "*" + .Type.String() }

// A StructType represents a struct, union, or C++ class type.
type StructType struct {
	CommonType
	StructName string
	Kind       string // "struct", "union", or "class".
	Field      []*StructField
	Incomplete bool // if true, struct, union, class is declared but not defined
}

// A StructField represents a field in a struct, union, or C++ class type.
type StructField struct {
	Name       string
	Type       Type
	ByteOffset int64
	ByteSize   int64 // usually zero; use Type.Size() for normal fields
	BitOffset  int64 // within the ByteSize bytes at ByteOffset
	BitSize    int64 // zero if not a bit field
}

func ( *StructType) () string {
	if .StructName != "" {
		return .Kind + " " + .StructName
	}
	return .Defn()
}

func ( *StructType) () string {
	 := .Kind
	if .StructName != "" {
		 += " " + .StructName
	}
	if .Incomplete {
		 += " /*incomplete*/"
		return 
	}
	 += " {"
	for ,  := range .Field {
		if  > 0 {
			 += "; "
		}
		 += .Name + " " + .Type.String()
		 += "@" + strconv.FormatInt(.ByteOffset, 10)
		if .BitSize > 0 {
			 += " : " + strconv.FormatInt(.BitSize, 10)
			 += "@" + strconv.FormatInt(.BitOffset, 10)
		}
	}
	 += "}"
	return 
}

// An EnumType represents an enumerated type.
// The only indication of its native integer type is its ByteSize
// (inside CommonType).
type EnumType struct {
	CommonType
	EnumName string
	Val      []*EnumValue
}

// An EnumValue represents a single enumeration value.
type EnumValue struct {
	Name string
	Val  int64
}

func ( *EnumType) () string {
	 := "enum"
	if .EnumName != "" {
		 += " " + .EnumName
	}
	 += " {"
	for ,  := range .Val {
		if  > 0 {
			 += "; "
		}
		 += .Name + "=" + strconv.FormatInt(.Val, 10)
	}
	 += "}"
	return 
}

// A FuncType represents a function type.
type FuncType struct {
	CommonType
	ReturnType Type
	ParamType  []Type
}

func ( *FuncType) () string {
	 := "func("
	for ,  := range .ParamType {
		if  > 0 {
			 += ", "
		}
		 += .String()
	}
	 += ")"
	if .ReturnType != nil {
		 += " " + .ReturnType.String()
	}
	return 
}

// A DotDotDotType represents the variadic ... function parameter.
type DotDotDotType struct {
	CommonType
}

func ( *DotDotDotType) () string { return "..." }

// A TypedefType represents a named type.
type TypedefType struct {
	CommonType
	Type Type
}

func ( *TypedefType) () string { return .Name }

func ( *TypedefType) () int64 { return .Type.Size() }

// An UnsupportedType is a placeholder returned in situations where we
// encounter a type that isn't supported.
type UnsupportedType struct {
	CommonType
	Tag Tag
}

func ( *UnsupportedType) () string {
	if .Name != "" {
		return .Name
	}
	return .Name + "(unsupported type " + .Tag.String() + ")"
}

// typeReader is used to read from either the info section or the
// types section.
type typeReader interface {
	Seek(Offset)
	Next() (*Entry, error)
	clone() typeReader
	offset() Offset
	// AddressSize returns the size in bytes of addresses in the current
	// compilation unit.
	AddressSize() int
}

// Type reads the type at off in the DWARF ``info'' section.
func ( *Data) ( Offset) (Type, error) {
	return .readType("info", .Reader(), , .typeCache, nil)
}

// readType reads a type from r at off of name. It adds types to the
// type cache, appends new typedef types to typedefs, and computes the
// sizes of types. Callers should pass nil for typedefs; this is used
// for internal recursion.
func ( *Data) ( string,  typeReader,  Offset,  map[Offset]Type,  *[]*TypedefType) (Type, error) {
	if ,  := [];  {
		return , nil
	}
	.Seek()
	,  := .Next()
	if  != nil {
		return nil, 
	}
	 := .AddressSize()
	if  == nil || .Offset !=  {
		return nil, DecodeError{, , "no type at offset"}
	}

	// If this is the root of the recursion, prepare to resolve
	// typedef sizes once the recursion is done. This must be done
	// after the type graph is constructed because it may need to
	// resolve cycles in a different order than readType
	// encounters them.
	if  == nil {
		var  []*TypedefType
		defer func() {
			for ,  := range  {
				.Common().ByteSize = .Type.Size()
			}
		}()
		 = &
	}

	// Parse type from Entry.
	// Must always set typeCache[off] before calling
	// d.readType recursively, to handle circular types correctly.
	var  Type

	 := 0

	// Get next child; set err if error happens.
	 := func() *Entry {
		if !.Children {
			return nil
		}
		// Only return direct children.
		// Skip over composite entries that happen to be nested
		// inside this one. Most DWARF generators wouldn't generate
		// such a thing, but clang does.
		// See golang.org/issue/6472.
		for {
			,  := .Next()
			if  != nil {
				 = 
				return nil
			}
			if  == nil {
				 = DecodeError{, .offset(), "unexpected end of DWARF entries"}
				return nil
			}
			if .Tag == 0 {
				if  > 0 {
					--
					continue
				}
				return nil
			}
			if .Children {
				++
			}
			if  > 0 {
				continue
			}
			return 
		}
	}

	// Get Type referred to by Entry's AttrType field.
	// Set err if error happens. Not having a type is an error.
	 := func( *Entry) Type {
		 := .Val(AttrType)
		var  Type
		switch toff := .(type) {
		case Offset:
			if ,  = .(, .clone(), , , );  != nil {
				return nil
			}
		case uint64:
			if ,  = .sigToType();  != nil {
				return nil
			}
		default:
			// It appears that no Type means "void".
			return new(VoidType)
		}
		return 
	}

	switch .Tag {
	case TagArrayType:
		// Multi-dimensional array.  (DWARF v2 §5.4)
		// Attributes:
		//	AttrType:subtype [required]
		//	AttrStrideSize: size in bits of each element of the array
		//	AttrByteSize: size of entire array
		// Children:
		//	TagSubrangeType or TagEnumerationType giving one dimension.
		//	dimensions are in left to right order.
		 := new(ArrayType)
		 = 
		[] = 
		if .Type = ();  != nil {
			goto 
		}
		.StrideBitSize, _ = .Val(AttrStrideSize).(int64)

		// Accumulate dimensions,
		var  []int64
		for  := ();  != nil;  = () {
			// TODO(rsc): Can also be TagEnumerationType
			// but haven't seen that in the wild yet.
			switch .Tag {
			case TagSubrangeType:
				,  := .Val(AttrCount).(int64)
				if ! {
					// Old binaries may have an upper bound instead.
					,  = .Val(AttrUpperBound).(int64)
					if  {
						++ // Length is one more than upper bound.
					} else if len() == 0 {
						 = -1 // As in x[].
					}
				}
				 = append(, )
			case TagEnumerationType:
				 = DecodeError{, .Offset, "cannot handle enumeration type as array bound"}
				goto 
			}
		}
		if len() == 0 {
			// LLVM generates this for x[].
			 = []int64{-1}
		}

		.Count = [0]
		for  := len() - 1;  >= 1; -- {
			.Type = &ArrayType{Type: .Type, Count: []}
		}

	case TagBaseType:
		// Basic type.  (DWARF v2 §5.1)
		// Attributes:
		//	AttrName: name of base type in programming language of the compilation unit [required]
		//	AttrEncoding: encoding value for type (encFloat etc) [required]
		//	AttrByteSize: size of type in bytes [required]
		//	AttrBitOffset: for sub-byte types, size in bits
		//	AttrBitSize: for sub-byte types, bit offset of high order bit in the AttrByteSize bytes
		,  := .Val(AttrName).(string)
		,  := .Val(AttrEncoding).(int64)
		if ! {
			 = DecodeError{, .Offset, "missing encoding attribute for " + }
			goto 
		}
		switch  {
		default:
			 = DecodeError{, .Offset, "unrecognized encoding attribute value"}
			goto 

		case encAddress:
			 = new(AddrType)
		case encBoolean:
			 = new(BoolType)
		case encComplexFloat:
			 = new(ComplexType)
			if  == "complex" {
				// clang writes out 'complex' instead of 'complex float' or 'complex double'.
				// clang also writes out a byte size that we can use to distinguish.
				// See issue 8694.
				switch ,  := .Val(AttrByteSize).(int64);  {
				case 8:
					 = "complex float"
				case 16:
					 = "complex double"
				}
			}
		case encFloat:
			 = new(FloatType)
		case encSigned:
			 = new(IntType)
		case encUnsigned:
			 = new(UintType)
		case encSignedChar:
			 = new(CharType)
		case encUnsignedChar:
			 = new(UcharType)
		}
		[] = 
		 := .(interface {
			() *BasicType
		}).()
		.Name = 
		.BitSize, _ = .Val(AttrBitSize).(int64)
		.BitOffset, _ = .Val(AttrBitOffset).(int64)

	case TagClassType, TagStructType, TagUnionType:
		// Structure, union, or class type.  (DWARF v2 §5.5)
		// Attributes:
		//	AttrName: name of struct, union, or class
		//	AttrByteSize: byte size [required]
		//	AttrDeclaration: if true, struct/union/class is incomplete
		// Children:
		//	TagMember to describe one member.
		//		AttrName: name of member [required]
		//		AttrType: type of member [required]
		//		AttrByteSize: size in bytes
		//		AttrBitOffset: bit offset within bytes for bit fields
		//		AttrBitSize: bit size for bit fields
		//		AttrDataMemberLoc: location within struct [required for struct, class]
		// There is much more to handle C++, all ignored for now.
		 := new(StructType)
		 = 
		[] = 
		switch .Tag {
		case TagClassType:
			.Kind = "class"
		case TagStructType:
			.Kind = "struct"
		case TagUnionType:
			.Kind = "union"
		}
		.StructName, _ = .Val(AttrName).(string)
		.Incomplete = .Val(AttrDeclaration) != nil
		.Field = make([]*StructField, 0, 8)
		var  *Type
		var  int64
		for  := ();  != nil;  = () {
			if .Tag != TagMember {
				continue
			}
			 := new(StructField)
			if .Type = ();  != nil {
				goto 
			}
			switch loc := .Val(AttrDataMemberLoc).(type) {
			case []byte:
				// TODO: Should have original compilation
				// unit here, not unknownFormat.
				 := makeBuf(, unknownFormat{}, "location", 0, )
				if .uint8() != opPlusUconst {
					 = DecodeError{, .Offset, "unexpected opcode"}
					goto 
				}
				.ByteOffset = int64(.uint())
				if .err != nil {
					 = .err
					goto 
				}
			case int64:
				.ByteOffset = 
			}

			 := false
			.Name, _ = .Val(AttrName).(string)
			.ByteSize, _ = .Val(AttrByteSize).(int64)
			.BitOffset,  = .Val(AttrBitOffset).(int64)
			.BitSize, _ = .Val(AttrBitSize).(int64)
			.Field = append(.Field, )

			 := .BitOffset
			if ! {
				 = .ByteOffset * 8
			}
			if  ==  && .Kind != "union" {
				// Last field was zero width. Fix array length.
				// (DWARF writes out 0-length arrays as if they were 1-length arrays.)
				zeroArray()
			}
			 = &.Type
			 = 
		}
		if .Kind != "union" {
			,  := .Val(AttrByteSize).(int64)
			if  && *8 ==  {
				// Final field must be zero width. Fix array length.
				zeroArray()
			}
		}

	case TagConstType, TagVolatileType, TagRestrictType:
		// Type modifier (DWARF v2 §5.2)
		// Attributes:
		//	AttrType: subtype
		 := new(QualType)
		 = 
		[] = 
		if .Type = ();  != nil {
			goto 
		}
		switch .Tag {
		case TagConstType:
			.Qual = "const"
		case TagRestrictType:
			.Qual = "restrict"
		case TagVolatileType:
			.Qual = "volatile"
		}

	case TagEnumerationType:
		// Enumeration type (DWARF v2 §5.6)
		// Attributes:
		//	AttrName: enum name if any
		//	AttrByteSize: bytes required to represent largest value
		// Children:
		//	TagEnumerator:
		//		AttrName: name of constant
		//		AttrConstValue: value of constant
		 := new(EnumType)
		 = 
		[] = 
		.EnumName, _ = .Val(AttrName).(string)
		.Val = make([]*EnumValue, 0, 8)
		for  := ();  != nil;  = () {
			if .Tag == TagEnumerator {
				 := new(EnumValue)
				.Name, _ = .Val(AttrName).(string)
				.Val, _ = .Val(AttrConstValue).(int64)
				 := len(.Val)
				if  >= cap(.Val) {
					 := make([]*EnumValue, , *2)
					copy(, .Val)
					.Val = 
				}
				.Val = .Val[0 : +1]
				.Val[] = 
			}
		}

	case TagPointerType:
		// Type modifier (DWARF v2 §5.2)
		// Attributes:
		//	AttrType: subtype [not required!  void* has no AttrType]
		//	AttrAddrClass: address class [ignored]
		 := new(PtrType)
		 = 
		[] = 
		if .Val(AttrType) == nil {
			.Type = &VoidType{}
			break
		}
		.Type = ()

	case TagSubroutineType:
		// Subroutine type.  (DWARF v2 §5.7)
		// Attributes:
		//	AttrType: type of return value if any
		//	AttrName: possible name of type [ignored]
		//	AttrPrototyped: whether used ANSI C prototype [ignored]
		// Children:
		//	TagFormalParameter: typed parameter
		//		AttrType: type of parameter
		//	TagUnspecifiedParameter: final ...
		 := new(FuncType)
		 = 
		[] = 
		if .ReturnType = ();  != nil {
			goto 
		}
		.ParamType = make([]Type, 0, 8)
		for  := ();  != nil;  = () {
			var  Type
			switch .Tag {
			default:
				continue
			case TagFormalParameter:
				if  = ();  != nil {
					goto 
				}
			case TagUnspecifiedParameters:
				 = &DotDotDotType{}
			}
			.ParamType = append(.ParamType, )
		}

	case TagTypedef:
		// Typedef (DWARF v2 §5.3)
		// Attributes:
		//	AttrName: name [required]
		//	AttrType: type definition [required]
		 := new(TypedefType)
		 = 
		[] = 
		.Name, _ = .Val(AttrName).(string)
		.Type = ()

	case TagUnspecifiedType:
		// Unspecified type (DWARF v3 §5.2)
		// Attributes:
		//	AttrName: name
		 := new(UnspecifiedType)
		 = 
		[] = 
		.Name, _ = .Val(AttrName).(string)

	default:
		// This is some other type DIE that we're currently not
		// equipped to handle. Return an abstract "unsupported type"
		// object in such cases.
		 := new(UnsupportedType)
		 = 
		[] = 
		.Tag = .Tag
		.Name, _ = .Val(AttrName).(string)
	}

	if  != nil {
		goto 
	}

	{
		,  := .Val(AttrByteSize).(int64)
		if ! {
			 = -1
			switch t := .(type) {
			case *TypedefType:
				// Record that we need to resolve this
				// type's size once the type graph is
				// constructed.
				* = append(*, )
			case *PtrType:
				 = int64()
			}
		}
		.Common().ByteSize = 
	}
	return , nil

:
	// If the parse fails, take the type out of the cache
	// so that the next call with this offset doesn't hit
	// the cache and return success.
	delete(, )
	return nil, 
}

func zeroArray( *Type) {
	if  == nil {
		return
	}
	,  := (*).(*ArrayType)
	if ! || .Type.Size() == 0 {
		return
	}
	// Make a copy to avoid invalidating typeCache.
	 := *
	.Count = 0
	* = &
}