1// Copyright 2017 The Bazel Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package starlarkstruct defines the Starlark types 'struct' and 6// 'module', both optional language extensions. 7// 8package starlarkstruct // import "go.starlark.net/starlarkstruct" 9 10// It is tempting to introduce a variant of Struct that is a wrapper 11// around a Go struct value, for stronger typing guarantees and more 12// efficient and convenient field lookup. However: 13// 1) all fields of Starlark structs are optional, so we cannot represent 14// them using more specific types such as String, Int, *Depset, and 15// *File, as such types give no way to represent missing fields. 16// 2) the efficiency gain of direct struct field access is rather 17// marginal: finding the index of a field by binary searching on the 18// sorted list of field names is quite fast compared to the other 19// overheads. 20// 3) the gains in compactness and spatial locality are also rather 21// marginal: the array behind the []entry slice is (due to field name 22// strings) only a factor of 2 larger than the corresponding Go struct 23// would be, and, like the Go struct, requires only a single allocation. 24 25import ( 26 "fmt" 27 "sort" 28 "strings" 29 30 "go.starlark.net/starlark" 31 "go.starlark.net/syntax" 32) 33 34// Make is the implementation of a built-in function that instantiates 35// an immutable struct from the specified keyword arguments. 36// 37// An application can add 'struct' to the Starlark environment like so: 38// 39// globals := starlark.StringDict{ 40// "struct": starlark.NewBuiltin("struct", starlarkstruct.Make), 41// } 42// 43func Make(_ *starlark.Thread, _ *starlark.Builtin, args starlark.Tuple, kwargs []starlark.Tuple) (starlark.Value, error) { 44 if len(args) > 0 { 45 return nil, fmt.Errorf("struct: unexpected positional arguments") 46 } 47 return FromKeywords(Default, kwargs), nil 48} 49 50// FromKeywords returns a new struct instance whose fields are specified by the 51// key/value pairs in kwargs. (Each kwargs[i][0] must be a starlark.String.) 52func FromKeywords(constructor starlark.Value, kwargs []starlark.Tuple) *Struct { 53 if constructor == nil { 54 panic("nil constructor") 55 } 56 s := &Struct{ 57 constructor: constructor, 58 entries: make(entries, 0, len(kwargs)), 59 } 60 for _, kwarg := range kwargs { 61 k := string(kwarg[0].(starlark.String)) 62 v := kwarg[1] 63 s.entries = append(s.entries, entry{k, v}) 64 } 65 sort.Sort(s.entries) 66 return s 67} 68 69// FromStringDict returns a whose elements are those of d. 70// The constructor parameter specifies the constructor; use Default for an ordinary struct. 71func FromStringDict(constructor starlark.Value, d starlark.StringDict) *Struct { 72 if constructor == nil { 73 panic("nil constructor") 74 } 75 s := &Struct{ 76 constructor: constructor, 77 entries: make(entries, 0, len(d)), 78 } 79 for k, v := range d { 80 s.entries = append(s.entries, entry{k, v}) 81 } 82 sort.Sort(s.entries) 83 return s 84} 85 86// Struct is an immutable Starlark type that maps field names to values. 87// It is not iterable and does not support len. 88// 89// A struct has a constructor, a distinct value that identifies a class 90// of structs, and which appears in the struct's string representation. 91// 92// Operations such as x+y fail if the constructors of the two operands 93// are not equal. 94// 95// The default constructor, Default, is the string "struct", but 96// clients may wish to 'brand' structs for their own purposes. 97// The constructor value appears in the printed form of the value, 98// and is accessible using the Constructor method. 99// 100// Use Attr to access its fields and AttrNames to enumerate them. 101type Struct struct { 102 constructor starlark.Value 103 entries entries // sorted by name 104} 105 106// Default is the default constructor for structs. 107// It is merely the string "struct". 108const Default = starlark.String("struct") 109 110type entries []entry 111 112func (a entries) Len() int { return len(a) } 113func (a entries) Less(i, j int) bool { return a[i].name < a[j].name } 114func (a entries) Swap(i, j int) { a[i], a[j] = a[j], a[i] } 115 116type entry struct { 117 name string 118 value starlark.Value 119} 120 121var ( 122 _ starlark.HasAttrs = (*Struct)(nil) 123 _ starlark.HasBinary = (*Struct)(nil) 124) 125 126// ToStringDict adds a name/value entry to d for each field of the struct. 127func (s *Struct) ToStringDict(d starlark.StringDict) { 128 for _, e := range s.entries { 129 d[e.name] = e.value 130 } 131} 132 133func (s *Struct) String() string { 134 buf := new(strings.Builder) 135 if s.constructor == Default { 136 // NB: The Java implementation always prints struct 137 // even for Bazel provider instances. 138 buf.WriteString("struct") // avoid String()'s quotation 139 } else { 140 buf.WriteString(s.constructor.String()) 141 } 142 buf.WriteByte('(') 143 for i, e := range s.entries { 144 if i > 0 { 145 buf.WriteString(", ") 146 } 147 buf.WriteString(e.name) 148 buf.WriteString(" = ") 149 buf.WriteString(e.value.String()) 150 } 151 buf.WriteByte(')') 152 return buf.String() 153} 154 155// Constructor returns the constructor used to create this struct. 156func (s *Struct) Constructor() starlark.Value { return s.constructor } 157 158func (s *Struct) Type() string { return "struct" } 159func (s *Struct) Truth() starlark.Bool { return true } // even when empty 160func (s *Struct) Hash() (uint32, error) { 161 // Same algorithm as Tuple.hash, but with different primes. 162 var x, m uint32 = 8731, 9839 163 for _, e := range s.entries { 164 namehash, _ := starlark.String(e.name).Hash() 165 x = x ^ 3*namehash 166 y, err := e.value.Hash() 167 if err != nil { 168 return 0, err 169 } 170 x = x ^ y*m 171 m += 7349 172 } 173 return x, nil 174} 175func (s *Struct) Freeze() { 176 for _, e := range s.entries { 177 e.value.Freeze() 178 } 179} 180 181func (x *Struct) Binary(op syntax.Token, y starlark.Value, side starlark.Side) (starlark.Value, error) { 182 if y, ok := y.(*Struct); ok && op == syntax.PLUS { 183 if side == starlark.Right { 184 x, y = y, x 185 } 186 187 if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil { 188 return nil, fmt.Errorf("in %s + %s: error comparing constructors: %v", 189 x.constructor, y.constructor, err) 190 } else if !eq { 191 return nil, fmt.Errorf("cannot add structs of different constructors: %s + %s", 192 x.constructor, y.constructor) 193 } 194 195 z := make(starlark.StringDict, x.len()+y.len()) 196 for _, e := range x.entries { 197 z[e.name] = e.value 198 } 199 for _, e := range y.entries { 200 z[e.name] = e.value 201 } 202 203 return FromStringDict(x.constructor, z), nil 204 } 205 return nil, nil // unhandled 206} 207 208// Attr returns the value of the specified field. 209func (s *Struct) Attr(name string) (starlark.Value, error) { 210 // Binary search the entries. 211 // This implementation is a specialization of 212 // sort.Search that avoids dynamic dispatch. 213 n := len(s.entries) 214 i, j := 0, n 215 for i < j { 216 h := int(uint(i+j) >> 1) 217 if s.entries[h].name < name { 218 i = h + 1 219 } else { 220 j = h 221 } 222 } 223 if i < n && s.entries[i].name == name { 224 return s.entries[i].value, nil 225 } 226 227 var ctor string 228 if s.constructor != Default { 229 ctor = s.constructor.String() + " " 230 } 231 return nil, starlark.NoSuchAttrError( 232 fmt.Sprintf("%sstruct has no .%s attribute", ctor, name)) 233} 234 235func (s *Struct) len() int { return len(s.entries) } 236 237// AttrNames returns a new sorted list of the struct fields. 238func (s *Struct) AttrNames() []string { 239 names := make([]string, len(s.entries)) 240 for i, e := range s.entries { 241 names[i] = e.name 242 } 243 return names 244} 245 246func (x *Struct) CompareSameType(op syntax.Token, y_ starlark.Value, depth int) (bool, error) { 247 y := y_.(*Struct) 248 switch op { 249 case syntax.EQL: 250 return structsEqual(x, y, depth) 251 case syntax.NEQ: 252 eq, err := structsEqual(x, y, depth) 253 return !eq, err 254 default: 255 return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type()) 256 } 257} 258 259func structsEqual(x, y *Struct, depth int) (bool, error) { 260 if x.len() != y.len() { 261 return false, nil 262 } 263 264 if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil { 265 return false, fmt.Errorf("error comparing struct constructors %v and %v: %v", 266 x.constructor, y.constructor, err) 267 } else if !eq { 268 return false, nil 269 } 270 271 for i, n := 0, x.len(); i < n; i++ { 272 if x.entries[i].name != y.entries[i].name { 273 return false, nil 274 } else if eq, err := starlark.EqualDepth(x.entries[i].value, y.entries[i].value, depth-1); err != nil { 275 return false, err 276 } else if !eq { 277 return false, nil 278 } 279 } 280 return true, nil 281} 282