diff options
Diffstat (limited to 'starlarkstruct/struct.go')
-rw-r--r-- | starlarkstruct/struct.go | 281 |
1 files changed, 281 insertions, 0 deletions
diff --git a/starlarkstruct/struct.go b/starlarkstruct/struct.go new file mode 100644 index 0000000..1982cc0 --- /dev/null +++ b/starlarkstruct/struct.go @@ -0,0 +1,281 @@ +// Copyright 2017 The Bazel Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package starlarkstruct defines the Starlark types 'struct' and +// 'module', both optional language extensions. +// +package starlarkstruct // import "go.starlark.net/starlarkstruct" + +// It is tempting to introduce a variant of Struct that is a wrapper +// around a Go struct value, for stronger typing guarantees and more +// efficient and convenient field lookup. However: +// 1) all fields of Starlark structs are optional, so we cannot represent +// them using more specific types such as String, Int, *Depset, and +// *File, as such types give no way to represent missing fields. +// 2) the efficiency gain of direct struct field access is rather +// marginal: finding the index of a field by binary searching on the +// sorted list of field names is quite fast compared to the other +// overheads. +// 3) the gains in compactness and spatial locality are also rather +// marginal: the array behind the []entry slice is (due to field name +// strings) only a factor of 2 larger than the corresponding Go struct +// would be, and, like the Go struct, requires only a single allocation. + +import ( + "fmt" + "sort" + "strings" + + "go.starlark.net/starlark" + "go.starlark.net/syntax" +) + +// Make is the implementation of a built-in function that instantiates +// an immutable struct from the specified keyword arguments. +// +// An application can add 'struct' to the Starlark environment like so: +// +// globals := starlark.StringDict{ +// "struct": starlark.NewBuiltin("struct", starlarkstruct.Make), +// } +// +func Make(_ *starlark.Thread, _ *starlark.Builtin, args starlark.Tuple, kwargs []starlark.Tuple) (starlark.Value, error) { + if len(args) > 0 { + return nil, fmt.Errorf("struct: unexpected positional arguments") + } + return FromKeywords(Default, kwargs), nil +} + +// FromKeywords returns a new struct instance whose fields are specified by the +// key/value pairs in kwargs. (Each kwargs[i][0] must be a starlark.String.) +func FromKeywords(constructor starlark.Value, kwargs []starlark.Tuple) *Struct { + if constructor == nil { + panic("nil constructor") + } + s := &Struct{ + constructor: constructor, + entries: make(entries, 0, len(kwargs)), + } + for _, kwarg := range kwargs { + k := string(kwarg[0].(starlark.String)) + v := kwarg[1] + s.entries = append(s.entries, entry{k, v}) + } + sort.Sort(s.entries) + return s +} + +// FromStringDict returns a whose elements are those of d. +// The constructor parameter specifies the constructor; use Default for an ordinary struct. +func FromStringDict(constructor starlark.Value, d starlark.StringDict) *Struct { + if constructor == nil { + panic("nil constructor") + } + s := &Struct{ + constructor: constructor, + entries: make(entries, 0, len(d)), + } + for k, v := range d { + s.entries = append(s.entries, entry{k, v}) + } + sort.Sort(s.entries) + return s +} + +// Struct is an immutable Starlark type that maps field names to values. +// It is not iterable and does not support len. +// +// A struct has a constructor, a distinct value that identifies a class +// of structs, and which appears in the struct's string representation. +// +// Operations such as x+y fail if the constructors of the two operands +// are not equal. +// +// The default constructor, Default, is the string "struct", but +// clients may wish to 'brand' structs for their own purposes. +// The constructor value appears in the printed form of the value, +// and is accessible using the Constructor method. +// +// Use Attr to access its fields and AttrNames to enumerate them. +type Struct struct { + constructor starlark.Value + entries entries // sorted by name +} + +// Default is the default constructor for structs. +// It is merely the string "struct". +const Default = starlark.String("struct") + +type entries []entry + +func (a entries) Len() int { return len(a) } +func (a entries) Less(i, j int) bool { return a[i].name < a[j].name } +func (a entries) Swap(i, j int) { a[i], a[j] = a[j], a[i] } + +type entry struct { + name string + value starlark.Value +} + +var ( + _ starlark.HasAttrs = (*Struct)(nil) + _ starlark.HasBinary = (*Struct)(nil) +) + +// ToStringDict adds a name/value entry to d for each field of the struct. +func (s *Struct) ToStringDict(d starlark.StringDict) { + for _, e := range s.entries { + d[e.name] = e.value + } +} + +func (s *Struct) String() string { + buf := new(strings.Builder) + if s.constructor == Default { + // NB: The Java implementation always prints struct + // even for Bazel provider instances. + buf.WriteString("struct") // avoid String()'s quotation + } else { + buf.WriteString(s.constructor.String()) + } + buf.WriteByte('(') + for i, e := range s.entries { + if i > 0 { + buf.WriteString(", ") + } + buf.WriteString(e.name) + buf.WriteString(" = ") + buf.WriteString(e.value.String()) + } + buf.WriteByte(')') + return buf.String() +} + +// Constructor returns the constructor used to create this struct. +func (s *Struct) Constructor() starlark.Value { return s.constructor } + +func (s *Struct) Type() string { return "struct" } +func (s *Struct) Truth() starlark.Bool { return true } // even when empty +func (s *Struct) Hash() (uint32, error) { + // Same algorithm as Tuple.hash, but with different primes. + var x, m uint32 = 8731, 9839 + for _, e := range s.entries { + namehash, _ := starlark.String(e.name).Hash() + x = x ^ 3*namehash + y, err := e.value.Hash() + if err != nil { + return 0, err + } + x = x ^ y*m + m += 7349 + } + return x, nil +} +func (s *Struct) Freeze() { + for _, e := range s.entries { + e.value.Freeze() + } +} + +func (x *Struct) Binary(op syntax.Token, y starlark.Value, side starlark.Side) (starlark.Value, error) { + if y, ok := y.(*Struct); ok && op == syntax.PLUS { + if side == starlark.Right { + x, y = y, x + } + + if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil { + return nil, fmt.Errorf("in %s + %s: error comparing constructors: %v", + x.constructor, y.constructor, err) + } else if !eq { + return nil, fmt.Errorf("cannot add structs of different constructors: %s + %s", + x.constructor, y.constructor) + } + + z := make(starlark.StringDict, x.len()+y.len()) + for _, e := range x.entries { + z[e.name] = e.value + } + for _, e := range y.entries { + z[e.name] = e.value + } + + return FromStringDict(x.constructor, z), nil + } + return nil, nil // unhandled +} + +// Attr returns the value of the specified field. +func (s *Struct) Attr(name string) (starlark.Value, error) { + // Binary search the entries. + // This implementation is a specialization of + // sort.Search that avoids dynamic dispatch. + n := len(s.entries) + i, j := 0, n + for i < j { + h := int(uint(i+j) >> 1) + if s.entries[h].name < name { + i = h + 1 + } else { + j = h + } + } + if i < n && s.entries[i].name == name { + return s.entries[i].value, nil + } + + var ctor string + if s.constructor != Default { + ctor = s.constructor.String() + " " + } + return nil, starlark.NoSuchAttrError( + fmt.Sprintf("%sstruct has no .%s attribute", ctor, name)) +} + +func (s *Struct) len() int { return len(s.entries) } + +// AttrNames returns a new sorted list of the struct fields. +func (s *Struct) AttrNames() []string { + names := make([]string, len(s.entries)) + for i, e := range s.entries { + names[i] = e.name + } + return names +} + +func (x *Struct) CompareSameType(op syntax.Token, y_ starlark.Value, depth int) (bool, error) { + y := y_.(*Struct) + switch op { + case syntax.EQL: + return structsEqual(x, y, depth) + case syntax.NEQ: + eq, err := structsEqual(x, y, depth) + return !eq, err + default: + return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) + } +} + +func structsEqual(x, y *Struct, depth int) (bool, error) { + if x.len() != y.len() { + return false, nil + } + + if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil { + return false, fmt.Errorf("error comparing struct constructors %v and %v: %v", + x.constructor, y.constructor, err) + } else if !eq { + return false, nil + } + + for i, n := 0, x.len(); i < n; i++ { + if x.entries[i].name != y.entries[i].name { + return false, nil + } else if eq, err := starlark.EqualDepth(x.entries[i].value, y.entries[i].value, depth-1); err != nil { + return false, err + } else if !eq { + return false, nil + } + } + return true, nil +} |