Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
alandonovan | 9d97771 | 2019-01-04 13:04:59 -0500 | [diff] [blame] | 5 | // Package starlarkstruct defines the Starlark types 'struct' and |
| 6 | // 'module', both optional language extensions. |
Alan Donovan | 6fffce7 | 2019-02-04 16:42:47 -0500 | [diff] [blame] | 7 | // |
Alan Donovan | 551f300 | 2018-11-01 09:44:00 -0400 | [diff] [blame] | 8 | package starlarkstruct // import "go.starlark.net/starlarkstruct" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 9 | |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 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: |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 13 | // 1) all fields of Starlark structs are optional, so we cannot represent |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 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. |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 24 | |
| 25 | import ( |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 26 | "fmt" |
| 27 | "sort" |
Josh Bleecher Snyder | 8cb25c8 | 2019-03-01 14:24:35 -0800 | [diff] [blame] | 28 | "strings" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 29 | |
Alan Donovan | 6beab7e | 2018-10-31 17:53:09 -0400 | [diff] [blame] | 30 | "go.starlark.net/starlark" |
| 31 | "go.starlark.net/syntax" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 32 | ) |
| 33 | |
| 34 | // Make is the implementation of a built-in function that instantiates |
| 35 | // an immutable struct from the specified keyword arguments. |
| 36 | // |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 37 | // An application can add 'struct' to the Starlark environment like so: |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 38 | // |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 39 | // globals := starlark.StringDict{ |
| 40 | // "struct": starlark.NewBuiltin("struct", starlarkstruct.Make), |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 41 | // } |
| 42 | // |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 43 | func Make(_ *starlark.Thread, _ *starlark.Builtin, args starlark.Tuple, kwargs []starlark.Tuple) (starlark.Value, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 51 | // key/value pairs in kwargs. (Each kwargs[i][0] must be a starlark.String.) |
| 52 | func FromKeywords(constructor starlark.Value, kwargs []starlark.Tuple) *Struct { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 61 | k := string(kwarg[0].(starlark.String)) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 71 | func FromStringDict(constructor starlark.Value, d starlark.StringDict) *Struct { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 86 | // Struct is an immutable Starlark type that maps field names to values. |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 87 | // It is not iterable and does not support len. |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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. |
| 101 | type Struct struct { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 102 | constructor starlark.Value |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 103 | entries entries // sorted by name |
| 104 | } |
| 105 | |
| 106 | // Default is the default constructor for structs. |
| 107 | // It is merely the string "struct". |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 108 | const Default = starlark.String("struct") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 109 | |
| 110 | type entries []entry |
| 111 | |
| 112 | func (a entries) Len() int { return len(a) } |
| 113 | func (a entries) Less(i, j int) bool { return a[i].name < a[j].name } |
| 114 | func (a entries) Swap(i, j int) { a[i], a[j] = a[j], a[i] } |
| 115 | |
| 116 | type entry struct { |
alandonovan | a3e7ce0 | 2019-02-06 17:48:33 -0500 | [diff] [blame] | 117 | name string |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 118 | value starlark.Value |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 119 | } |
| 120 | |
| 121 | var ( |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 122 | _ starlark.HasAttrs = (*Struct)(nil) |
| 123 | _ starlark.HasBinary = (*Struct)(nil) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 124 | ) |
| 125 | |
| 126 | // ToStringDict adds a name/value entry to d for each field of the struct. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 127 | func (s *Struct) ToStringDict(d starlark.StringDict) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 128 | for _, e := range s.entries { |
| 129 | d[e.name] = e.value |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | func (s *Struct) String() string { |
Josh Bleecher Snyder | 8cb25c8 | 2019-03-01 14:24:35 -0800 | [diff] [blame] | 134 | buf := new(strings.Builder) |
alandonovan | cada868 | 2018-02-26 12:59:19 -0500 | [diff] [blame] | 135 | if s.constructor == Default { |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 136 | // NB: The Java implementation always prints struct |
| 137 | // even for Bazel provider instances. |
alandonovan | cada868 | 2018-02-26 12:59:19 -0500 | [diff] [blame] | 138 | buf.WriteString("struct") // avoid String()'s quotation |
| 139 | } else { |
| 140 | buf.WriteString(s.constructor.String()) |
| 141 | } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 156 | func (s *Struct) Constructor() starlark.Value { return s.constructor } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 157 | |
Alan Donovan | 551f300 | 2018-11-01 09:44:00 -0400 | [diff] [blame] | 158 | func (s *Struct) Type() string { return "struct" } |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 159 | func (s *Struct) Truth() starlark.Bool { return true } // even when empty |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 160 | func (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 { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 164 | namehash, _ := starlark.String(e.name).Hash() |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | } |
| 175 | func (s *Struct) Freeze() { |
| 176 | for _, e := range s.entries { |
| 177 | e.value.Freeze() |
| 178 | } |
| 179 | } |
| 180 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 181 | func (x *Struct) Binary(op syntax.Token, y starlark.Value, side starlark.Side) (starlark.Value, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 182 | if y, ok := y.(*Struct); ok && op == syntax.PLUS { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 183 | if side == starlark.Right { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 184 | x, y = y, x |
| 185 | } |
| 186 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 187 | if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 195 | z := make(starlark.StringDict, x.len()+y.len()) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
alandonovan | a3e7ce0 | 2019-02-06 17:48:33 -0500 | [diff] [blame] | 208 | // Attr returns the value of the specified field. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 209 | func (s *Struct) Attr(name string) (starlark.Value, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
alandonovan | cada868 | 2018-02-26 12:59:19 -0500 | [diff] [blame] | 227 | var ctor string |
| 228 | if s.constructor != Default { |
| 229 | ctor = s.constructor.String() + " " |
| 230 | } |
alandonovan | 6afa1bb | 2019-02-06 17:49:05 -0500 | [diff] [blame] | 231 | return nil, starlark.NoSuchAttrError( |
| 232 | fmt.Sprintf("%sstruct has no .%s attribute", ctor, name)) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 233 | } |
| 234 | |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 235 | func (s *Struct) len() int { return len(s.entries) } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 236 | |
| 237 | // AttrNames returns a new sorted list of the struct fields. |
| 238 | func (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 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 246 | func (x *Struct) CompareSameType(op syntax.Token, y_ starlark.Value, depth int) (bool, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
| 259 | func structsEqual(x, y *Struct, depth int) (bool, error) { |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 260 | if x.len() != y.len() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 261 | return false, nil |
| 262 | } |
| 263 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 264 | if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil { |
alandonovan | 4b42bbf | 2017-11-10 13:22:52 -0500 | [diff] [blame] | 265 | return false, fmt.Errorf("error comparing struct constructors %v and %v: %v", |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 266 | x.constructor, y.constructor, err) |
| 267 | } else if !eq { |
| 268 | return false, nil |
| 269 | } |
| 270 | |
alandonovan | 67717b5 | 2018-04-23 13:28:48 -0400 | [diff] [blame] | 271 | for i, n := 0, x.len(); i < n; i++ { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 272 | if x.entries[i].name != y.entries[i].name { |
| 273 | return false, nil |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 274 | } else if eq, err := starlark.EqualDepth(x.entries[i].value, y.entries[i].value, depth-1); err != nil { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 275 | return false, err |
| 276 | } else if !eq { |
| 277 | return false, nil |
| 278 | } |
| 279 | } |
| 280 | return true, nil |
| 281 | } |