third_party/gotools/go/importer/import.go - llvm-project/llgo - Git at Google

 // Copyright 2013 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.

 // This implementation is loosely based on the algorithm described
 // in: "On the linearization of graphs and writing symbol files",
 // by R. Griesemer, Technical Report 156, ETH Zürich, 1991.

 // package importer implements an exporter and importer for Go export data.
 package importer // import "llvm.org/llgo/third_party/gotools/go/importer"

 import (
 	"encoding/binary"
 	"fmt"
 	"go/token"

 	"llvm.org/llgo/third_party/gotools/go/exact"
 	"llvm.org/llgo/third_party/gotools/go/types"
 )

 // ImportData imports a package from the serialized package data
 // and returns the number of bytes consumed and a reference to the package.
 // If data is obviously malformed, an error is returned but in
 // general it is not recommended to call ImportData on untrusted
 // data.
 func ImportData(imports map[string]*types.Package, data []byte) (int, *types.Package, error) {
 	datalen := len(data)

 	// check magic string
 	var s string
 	if len(data) >= len(magic) {
 		s = string(data[:len(magic)])
 		data = data[len(magic):]
 	}
 	if s != magic {
 		return 0, nil, fmt.Errorf("incorrect magic string: got %q; want %q", s, magic)
 	}

 	// check low-level encoding format
 	var m byte = 'm' // missing format
 	if len(data) > 0 {
 		m = data[0]
 		data = data[1:]
 	}
 	if m != format() {
 		return 0, nil, fmt.Errorf("incorrect low-level encoding format: got %c; want %c", m, format())
 	}

 	p := importer{
 		data:    data,
 		datalen: datalen,
 		imports: imports,
 	}

 	// populate typList with predeclared types
 	for _, t := range predeclared {
 		p.typList = append(p.typList, t)
 	}

 	if v := p.string(); v != version {
 		return 0, nil, fmt.Errorf("unknown version: got %s; want %s", v, version)
 	}

 	pkg := p.pkg()
 	if debug && p.pkgList[0] != pkg {
 		panic("imported packaged not found in pkgList[0]")
 	}

 	// read objects
 	n := p.int()
 	for i := 0; i < n; i++ {
 		p.obj(pkg)
 	}

 	// complete interfaces
 	for _, typ := range p.typList {
 		if it, ok := typ.(*types.Interface); ok {
 			it.Complete()
 		}
 	}

 	// package was imported completely and without errors
 	pkg.MarkComplete()

 	return p.consumed(), pkg, nil
 }

 type importer struct {
 	data    []byte
 	datalen int
 	imports map[string]*types.Package
 	pkgList []*types.Package
 	typList []types.Type
 }

 func (p *importer) pkg() *types.Package {
 	// if the package was seen before, i is its index (>= 0)
 	i := p.int()
 	if i >= 0 {
 		return p.pkgList[i]
 	}

 	// otherwise, i is the package tag (< 0)
 	if i != packageTag {
 		panic(fmt.Sprintf("unexpected package tag %d", i))
 	}

 	// read package data
 	name := p.string()
 	path := p.string()

 	// if the package was imported before, use that one; otherwise create a new one
 	pkg := p.imports[path]
 	if pkg == nil {
 		pkg = types.NewPackage(path, name)
 		p.imports[path] = pkg
 	}
 	p.pkgList = append(p.pkgList, pkg)

 	return pkg
 }

 func (p *importer) obj(pkg *types.Package) {
 	var obj types.Object
 	switch tag := p.int(); tag {
 	case constTag:
 		obj = types.NewConst(token.NoPos, pkg, p.string(), p.typ(), p.value())
 	case typeTag:
 		// type object is added to scope via respective named type
 		_ = p.typ().(*types.Named)
 		return
 	case varTag:
 		obj = types.NewVar(token.NoPos, pkg, p.string(), p.typ())
 	case funcTag:
 		obj = types.NewFunc(token.NoPos, pkg, p.string(), p.typ().(*types.Signature))
 	default:
 		panic(fmt.Sprintf("unexpected object tag %d", tag))
 	}

 	if alt := pkg.Scope().Insert(obj); alt != nil {
 		panic(fmt.Sprintf("%s already declared", alt.Name()))
 	}
 }

 func (p *importer) value() exact.Value {
 	switch kind := exact.Kind(p.int()); kind {
 	case falseTag:
 		return exact.MakeBool(false)
 	case trueTag:
 		return exact.MakeBool(true)
 	case int64Tag:
 		return exact.MakeInt64(p.int64())
 	case floatTag:
 		return p.float()
 	case fractionTag:
 		return p.fraction()
 	case complexTag:
 		re := p.fraction()
 		im := p.fraction()
 		return exact.BinaryOp(re, token.ADD, exact.MakeImag(im))
 	case stringTag:
 		return exact.MakeString(p.string())
 	default:
 		panic(fmt.Sprintf("unexpected value kind %d", kind))
 	}
 }

 func (p *importer) float() exact.Value {
 	sign := p.int()
 	if sign == 0 {
 		return exact.MakeInt64(0)
 	}

 	x := p.ufloat()
 	if sign < 0 {
 		x = exact.UnaryOp(token.SUB, x, 0)
 	}
 	return x
 }

 func (p *importer) fraction() exact.Value {
 	sign := p.int()
 	if sign == 0 {
 		return exact.MakeInt64(0)
 	}

 	x := exact.BinaryOp(p.ufloat(), token.QUO, p.ufloat())
 	if sign < 0 {
 		x = exact.UnaryOp(token.SUB, x, 0)
 	}
 	return x
 }

 func (p *importer) ufloat() exact.Value {
 	exp := p.int()
 	x := exact.MakeFromBytes(p.bytes())
 	switch {
 	case exp < 0:
 		d := exact.Shift(exact.MakeInt64(1), token.SHL, uint(-exp))
 		x = exact.BinaryOp(x, token.QUO, d)
 	case exp > 0:
 		x = exact.Shift(x, token.SHL, uint(exp))
 	}
 	return x
 }

 func (p *importer) record(t types.Type) {
 	p.typList = append(p.typList, t)
 }

 func (p *importer) typ() types.Type {
 	// if the type was seen before, i is its index (>= 0)
 	i := p.int()
 	if i >= 0 {
 		return p.typList[i]
 	}

 	// otherwise, i is the type tag (< 0)
 	switch i {
 	case arrayTag:
 		t := new(types.Array)
 		p.record(t)

 		n := p.int64()
 		*t = *types.NewArray(p.typ(), n)
 		return t

 	case sliceTag:
 		t := new(types.Slice)
 		p.record(t)

 		*t = *types.NewSlice(p.typ())
 		return t

 	case structTag:
 		t := new(types.Struct)
 		p.record(t)

 		n := p.int()
 		fields := make([]*types.Var, n)
 		tags := make([]string, n)
 		for i := range fields {
 			fields[i] = p.field()
 			tags[i] = p.string()
 		}
 		*t = *types.NewStruct(fields, tags)
 		return t

 	case pointerTag:
 		t := new(types.Pointer)
 		p.record(t)

 		*t = *types.NewPointer(p.typ())
 		return t

 	case signatureTag:
 		t := new(types.Signature)
 		p.record(t)

 		*t = *p.signature()
 		return t

 	case interfaceTag:
 		// Create a dummy entry in the type list. This is safe because we
 		// cannot expect the interface type to appear in a cycle, as any
 		// such cycle must contain a named type which would have been
 		// first defined earlier.
 		n := len(p.typList)
 		p.record(nil)

 		// read embedded interfaces
 		embeddeds := make([]*types.Named, p.int())
 		for i := range embeddeds {
 			embeddeds[i] = p.typ().(*types.Named)
 		}

 		// read methods
 		methods := make([]*types.Func, p.int())
 		for i := range methods {
 			pkg, name := p.qualifiedName()
 			methods[i] = types.NewFunc(token.NoPos, pkg, name, p.typ().(*types.Signature))
 		}

 		t := types.NewInterface(methods, embeddeds)
 		p.typList[n] = t
 		return t

 	case mapTag:
 		t := new(types.Map)
 		p.record(t)

 		*t = *types.NewMap(p.typ(), p.typ())
 		return t

 	case chanTag:
 		t := new(types.Chan)
 		p.record(t)

 		*t = *types.NewChan(types.ChanDir(p.int()), p.typ())
 		return t

 	case namedTag:
 		// read type object
 		name := p.string()
 		pkg := p.pkg()
 		scope := pkg.Scope()
 		obj := scope.Lookup(name)

 		// if the object doesn't exist yet, create and insert it
 		if obj == nil {
 			obj = types.NewTypeName(token.NoPos, pkg, name, nil)
 			scope.Insert(obj)
 		}

 		// associate new named type with obj if it doesn't exist yet
 		t0 := types.NewNamed(obj.(*types.TypeName), nil, nil)

 		// but record the existing type, if any
 		t := obj.Type().(*types.Named)
 		p.record(t)

 		// read underlying type
 		t0.SetUnderlying(p.typ())

 		// read associated methods
 		for i, n := 0, p.int(); i < n; i++ {
 			t0.AddMethod(types.NewFunc(token.NoPos, pkg, p.string(), p.typ().(*types.Signature)))
 		}

 		return t

 	default:
 		panic(fmt.Sprintf("unexpected type tag %d", i))
 	}
 }

 func deref(typ types.Type) types.Type {
 	if p, _ := typ.(*types.Pointer); p != nil {
 		return p.Elem()
 	}
 	return typ
 }

 func (p *importer) field() *types.Var {
 	pkg, name := p.qualifiedName()
 	typ := p.typ()

 	anonymous := false
 	if name == "" {
 		// anonymous field - typ must be T or *T and T must be a type name
 		switch typ := deref(typ).(type) {
 		case *types.Basic: // basic types are named types
 			pkg = nil
 			name = typ.Name()
 		case *types.Named:
 			obj := typ.Obj()
 			name = obj.Name()
 			// correct the field package for anonymous fields
 			if exported(name) {
 				pkg = p.pkgList[0]
 			}
 		default:
 			panic("anonymous field expected")
 		}
 		anonymous = true
 	}

 	return types.NewField(token.NoPos, pkg, name, typ, anonymous)
 }

 func (p *importer) qualifiedName() (*types.Package, string) {
 	name := p.string()
 	pkg := p.pkgList[0] // exported names assume current package
 	if !exported(name) {
 		pkg = p.pkg()
 	}
 	return pkg, name
 }

 func (p *importer) signature() *types.Signature {
 	var recv *types.Var
 	if p.int() != 0 {
 		recv = p.param()
 	}
 	return types.NewSignature(nil, recv, p.tuple(), p.tuple(), p.int() != 0)
 }

 func (p *importer) param() *types.Var {
 	return types.NewVar(token.NoPos, nil, p.string(), p.typ())
 }

 func (p *importer) tuple() *types.Tuple {
 	vars := make([]*types.Var, p.int())
 	for i := range vars {
 		vars[i] = p.param()
 	}
 	return types.NewTuple(vars...)
 }

 // ----------------------------------------------------------------------------
 // decoders

 func (p *importer) string() string {
 	return string(p.bytes())
 }

 func (p *importer) int() int {
 	return int(p.int64())
 }

 func (p *importer) int64() int64 {
 	if debug {
 		p.marker('i')
 	}

 	return p.rawInt64()
 }

 // Note: bytes() returns the respective byte slice w/o copy.
 func (p *importer) bytes() []byte {
 	if debug {
 		p.marker('b')
 	}

 	var b []byte
 	if n := int(p.rawInt64()); n > 0 {
 		b = p.data[:n]
 		p.data = p.data[n:]
 	}
 	return b
 }

 func (p *importer) marker(want byte) {
 	if debug {
 		if got := p.data[0]; got != want {
 			panic(fmt.Sprintf("incorrect marker: got %c; want %c (pos = %d)", got, want, p.consumed()))
 		}
 		p.data = p.data[1:]

 		pos := p.consumed()
 		if n := int(p.rawInt64()); n != pos {
 			panic(fmt.Sprintf("incorrect position: got %d; want %d", n, pos))
 		}
 	}
 }

 // rawInt64 should only be used by low-level decoders
 func (p *importer) rawInt64() int64 {
 	i, n := binary.Varint(p.data)
 	p.data = p.data[n:]
 	return i
 }

 func (p *importer) consumed() int {
 	return p.datalen - len(p.data)
 }
	// Copyright 2013 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.

	// This implementation is loosely based on the algorithm described
	// in: "On the linearization of graphs and writing symbol files",
	// by R. Griesemer, Technical Report 156, ETH Zürich, 1991.

	// package importer implements an exporter and importer for Go export data.
	package importer // import "llvm.org/llgo/third_party/gotools/go/importer"

	import (
	"encoding/binary"
	"fmt"
	"go/token"

	"llvm.org/llgo/third_party/gotools/go/exact"
	"llvm.org/llgo/third_party/gotools/go/types"
	)

	// ImportData imports a package from the serialized package data
	// and returns the number of bytes consumed and a reference to the package.
	// If data is obviously malformed, an error is returned but in
	// general it is not recommended to call ImportData on untrusted
	// data.
	func ImportData(imports map[string]types.Package, data []byte) (int, types.Package, error) {
	datalen := len(data)

	// check magic string
	var s string
	if len(data) >= len(magic) {
	s = string(data[:len(magic)])
	data = data[len(magic):]
	}
	if s != magic {
	return 0, nil, fmt.Errorf("incorrect magic string: got %q; want %q", s, magic)
	}

	// check low-level encoding format
	var m byte = 'm' // missing format
	if len(data) > 0 {
	m = data[0]
	data = data[1:]
	}
	if m != format() {
	return 0, nil, fmt.Errorf("incorrect low-level encoding format: got %c; want %c", m, format())
	}

	p := importer{
	data: data,
	datalen: datalen,
	imports: imports,
	}

	// populate typList with predeclared types
	for _, t := range predeclared {
	p.typList = append(p.typList, t)
	}

	if v := p.string(); v != version {
	return 0, nil, fmt.Errorf("unknown version: got %s; want %s", v, version)
	}

	pkg := p.pkg()
	if debug && p.pkgList[0] != pkg {
	panic("imported packaged not found in pkgList[0]")
	}

	// read objects
	n := p.int()
	for i := 0; i < n; i++ {
	p.obj(pkg)
	}

	// complete interfaces
	for _, typ := range p.typList {
	if it, ok := typ.(*types.Interface); ok {
	it.Complete()
	}
	}

	// package was imported completely and without errors
	pkg.MarkComplete()

	return p.consumed(), pkg, nil
	}

	type importer struct {
	data []byte
	datalen int
	imports map[string]*types.Package
	pkgList []*types.Package
	typList []types.Type
	}

	func (p importer) pkg() types.Package {
	// if the package was seen before, i is its index (>= 0)
	i := p.int()
	if i >= 0 {
	return p.pkgList[i]
	}

	// otherwise, i is the package tag (< 0)
	if i != packageTag {
	panic(fmt.Sprintf("unexpected package tag %d", i))
	}

	// read package data
	name := p.string()
	path := p.string()

	// if the package was imported before, use that one; otherwise create a new one
	pkg := p.imports[path]
	if pkg == nil {
	pkg = types.NewPackage(path, name)
	p.imports[path] = pkg
	}
	p.pkgList = append(p.pkgList, pkg)

	return pkg
	}

	func (p importer) obj(pkg types.Package) {
	var obj types.Object
	switch tag := p.int(); tag {
	case constTag:
	obj = types.NewConst(token.NoPos, pkg, p.string(), p.typ(), p.value())
	case typeTag:
	// type object is added to scope via respective named type
	_ = p.typ().(*types.Named)
	return
	case varTag:
	obj = types.NewVar(token.NoPos, pkg, p.string(), p.typ())
	case funcTag:
	obj = types.NewFunc(token.NoPos, pkg, p.string(), p.typ().(*types.Signature))
	default:
	panic(fmt.Sprintf("unexpected object tag %d", tag))
	}

	if alt := pkg.Scope().Insert(obj); alt != nil {
	panic(fmt.Sprintf("%s already declared", alt.Name()))
	}
	}

	func (p *importer) value() exact.Value {
	switch kind := exact.Kind(p.int()); kind {
	case falseTag:
	return exact.MakeBool(false)
	case trueTag:
	return exact.MakeBool(true)
	case int64Tag:
	return exact.MakeInt64(p.int64())
	case floatTag:
	return p.float()
	case fractionTag:
	return p.fraction()
	case complexTag:
	re := p.fraction()
	im := p.fraction()
	return exact.BinaryOp(re, token.ADD, exact.MakeImag(im))
	case stringTag:
	return exact.MakeString(p.string())
	default:
	panic(fmt.Sprintf("unexpected value kind %d", kind))
	}
	}

	func (p *importer) float() exact.Value {
	sign := p.int()
	if sign == 0 {
	return exact.MakeInt64(0)
	}

	x := p.ufloat()
	if sign < 0 {
	x = exact.UnaryOp(token.SUB, x, 0)
	}
	return x
	}

	func (p *importer) fraction() exact.Value {
	sign := p.int()
	if sign == 0 {
	return exact.MakeInt64(0)
	}

	x := exact.BinaryOp(p.ufloat(), token.QUO, p.ufloat())
	if sign < 0 {
	x = exact.UnaryOp(token.SUB, x, 0)
	}
	return x
	}

	func (p *importer) ufloat() exact.Value {
	exp := p.int()
	x := exact.MakeFromBytes(p.bytes())
	switch {
	case exp < 0:
	d := exact.Shift(exact.MakeInt64(1), token.SHL, uint(-exp))
	x = exact.BinaryOp(x, token.QUO, d)
	case exp > 0:
	x = exact.Shift(x, token.SHL, uint(exp))
	}
	return x
	}

	func (p *importer) record(t types.Type) {
	p.typList = append(p.typList, t)
	}

	func (p *importer) typ() types.Type {
	// if the type was seen before, i is its index (>= 0)
	i := p.int()
	if i >= 0 {
	return p.typList[i]
	}

	// otherwise, i is the type tag (< 0)
	switch i {
	case arrayTag:
	t := new(types.Array)
	p.record(t)

	n := p.int64()
	t = types.NewArray(p.typ(), n)
	return t

	case sliceTag:
	t := new(types.Slice)
	p.record(t)

	t = types.NewSlice(p.typ())
	return t

	case structTag:
	t := new(types.Struct)
	p.record(t)

	n := p.int()
	fields := make([]*types.Var, n)
	tags := make([]string, n)
	for i := range fields {
	fields[i] = p.field()
	tags[i] = p.string()
	}
	t = types.NewStruct(fields, tags)
	return t

	case pointerTag:
	t := new(types.Pointer)
	p.record(t)

	t = types.NewPointer(p.typ())
	return t

	case signatureTag:
	t := new(types.Signature)
	p.record(t)

	t = p.signature()
	return t

	case interfaceTag:
	// Create a dummy entry in the type list. This is safe because we
	// cannot expect the interface type to appear in a cycle, as any
	// such cycle must contain a named type which would have been
	// first defined earlier.
	n := len(p.typList)
	p.record(nil)

	// read embedded interfaces
	embeddeds := make([]*types.Named, p.int())
	for i := range embeddeds {
	embeddeds[i] = p.typ().(*types.Named)
	}

	// read methods
	methods := make([]*types.Func, p.int())
	for i := range methods {
	pkg, name := p.qualifiedName()
	methods[i] = types.NewFunc(token.NoPos, pkg, name, p.typ().(*types.Signature))
	}

	t := types.NewInterface(methods, embeddeds)
	p.typList[n] = t
	return t

	case mapTag:
	t := new(types.Map)
	p.record(t)

	t = types.NewMap(p.typ(), p.typ())
	return t

	case chanTag:
	t := new(types.Chan)
	p.record(t)

	t = types.NewChan(types.ChanDir(p.int()), p.typ())
	return t

	case namedTag:
	// read type object
	name := p.string()
	pkg := p.pkg()
	scope := pkg.Scope()
	obj := scope.Lookup(name)

	// if the object doesn't exist yet, create and insert it
	if obj == nil {
	obj = types.NewTypeName(token.NoPos, pkg, name, nil)
	scope.Insert(obj)
	}

	// associate new named type with obj if it doesn't exist yet
	t0 := types.NewNamed(obj.(*types.TypeName), nil, nil)

	// but record the existing type, if any
	t := obj.Type().(*types.Named)
	p.record(t)

	// read underlying type
	t0.SetUnderlying(p.typ())

	// read associated methods
	for i, n := 0, p.int(); i < n; i++ {
	t0.AddMethod(types.NewFunc(token.NoPos, pkg, p.string(), p.typ().(*types.Signature)))
	}

	return t

	default:
	panic(fmt.Sprintf("unexpected type tag %d", i))
	}
	}

	func deref(typ types.Type) types.Type {
	if p, _ := typ.(*types.Pointer); p != nil {
	return p.Elem()
	}
	return typ
	}

	func (p importer) field() types.Var {
	pkg, name := p.qualifiedName()
	typ := p.typ()

	anonymous := false
	if name == "" {
	// anonymous field - typ must be T or *T and T must be a type name
	switch typ := deref(typ).(type) {
	case *types.Basic: // basic types are named types
	pkg = nil
	name = typ.Name()
	case *types.Named:
	obj := typ.Obj()
	name = obj.Name()
	// correct the field package for anonymous fields
	if exported(name) {
	pkg = p.pkgList[0]
	}
	default:
	panic("anonymous field expected")
	}
	anonymous = true
	}

	return types.NewField(token.NoPos, pkg, name, typ, anonymous)
	}

	func (p importer) qualifiedName() (types.Package, string) {
	name := p.string()
	pkg := p.pkgList[0] // exported names assume current package
	if !exported(name) {
	pkg = p.pkg()
	}
	return pkg, name
	}

	func (p importer) signature() types.Signature {
	var recv *types.Var
	if p.int() != 0 {
	recv = p.param()
	}
	return types.NewSignature(nil, recv, p.tuple(), p.tuple(), p.int() != 0)
	}

	func (p importer) param() types.Var {
	return types.NewVar(token.NoPos, nil, p.string(), p.typ())
	}

	func (p importer) tuple() types.Tuple {
	vars := make([]*types.Var, p.int())
	for i := range vars {
	vars[i] = p.param()
	}
	return types.NewTuple(vars...)
	}

	// ----------------------------------------------------------------------------
	// decoders

	func (p *importer) string() string {
	return string(p.bytes())
	}

	func (p *importer) int() int {
	return int(p.int64())
	}

	func (p *importer) int64() int64 {
	if debug {
	p.marker('i')
	}

	return p.rawInt64()
	}

	// Note: bytes() returns the respective byte slice w/o copy.
	func (p *importer) bytes() []byte {
	if debug {
	p.marker('b')
	}

	var b []byte
	if n := int(p.rawInt64()); n > 0 {
	b = p.data[:n]
	p.data = p.data[n:]
	}
	return b
	}

	func (p *importer) marker(want byte) {
	if debug {
	if got := p.data[0]; got != want {
	panic(fmt.Sprintf("incorrect marker: got %c; want %c (pos = %d)", got, want, p.consumed()))
	}
	p.data = p.data[1:]

	pos := p.consumed()
	if n := int(p.rawInt64()); n != pos {
	panic(fmt.Sprintf("incorrect position: got %d; want %d", n, pos))
	}
	}
	}

	// rawInt64 should only be used by low-level decoders
	func (p *importer) rawInt64() int64 {
	i, n := binary.Varint(p.data)
	p.data = p.data[n:]
	return i
	}

	func (p *importer) consumed() int {
	return p.datalen - len(p.data)
	}