struct.go

Documentation: go.starlark.net/starlarkstruct

     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  //
     8  package 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  
    25  import (
    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  //
    43  func 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.)
    52  func 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 new struct instance whose elements are those of d.
    70  // The constructor parameter specifies the constructor; use Default for an ordinary struct.
    71  func 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.
   101  type 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".
   108  const Default = starlark.String("struct")
   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 {
   117  	name  string
   118  	value starlark.Value
   119  }
   120  
   121  var (
   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.
   127  func (s *Struct) ToStringDict(d starlark.StringDict) {
   128  	for _, e := range s.entries {
   129  		d[e.name] = e.value
   130  	}
   131  }
   132  
   133  func (s *Struct) String() string {
   134  	buf := new(strings.Builder)
   135  	switch constructor := s.constructor.(type) {
   136  	case starlark.String:
   137  		// NB: The Java implementation always prints struct
   138  		// even for Bazel provider instances.
   139  		buf.WriteString(constructor.GoString()) // avoid String()'s quotation
   140  	default:
   141  		buf.WriteString(s.constructor.String())
   142  	}
   143  	buf.WriteByte('(')
   144  	for i, e := range s.entries {
   145  		if i > 0 {
   146  			buf.WriteString(", ")
   147  		}
   148  		buf.WriteString(e.name)
   149  		buf.WriteString(" = ")
   150  		buf.WriteString(e.value.String())
   151  	}
   152  	buf.WriteByte(')')
   153  	return buf.String()
   154  }
   155  
   156  // Constructor returns the constructor used to create this struct.
   157  func (s *Struct) Constructor() starlark.Value { return s.constructor }
   158  
   159  func (s *Struct) Type() string         { return "struct" }
   160  func (s *Struct) Truth() starlark.Bool { return true } // even when empty
   161  func (s *Struct) Hash() (uint32, error) {
   162  	// Same algorithm as Tuple.hash, but with different primes.
   163  	var x, m uint32 = 8731, 9839
   164  	for _, e := range s.entries {
   165  		namehash, _ := starlark.String(e.name).Hash()
   166  		x = x ^ 3*namehash
   167  		y, err := e.value.Hash()
   168  		if err != nil {
   169  			return 0, err
   170  		}
   171  		x = x ^ y*m
   172  		m += 7349
   173  	}
   174  	return x, nil
   175  }
   176  func (s *Struct) Freeze() {
   177  	for _, e := range s.entries {
   178  		e.value.Freeze()
   179  	}
   180  }
   181  
   182  func (x *Struct) Binary(op syntax.Token, y starlark.Value, side starlark.Side) (starlark.Value, error) {
   183  	if y, ok := y.(*Struct); ok && op == syntax.PLUS {
   184  		if side == starlark.Right {
   185  			x, y = y, x
   186  		}
   187  
   188  		if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil {
   189  			return nil, fmt.Errorf("in %s + %s: error comparing constructors: %v",
   190  				x.constructor, y.constructor, err)
   191  		} else if !eq {
   192  			return nil, fmt.Errorf("cannot add structs of different constructors: %s + %s",
   193  				x.constructor, y.constructor)
   194  		}
   195  
   196  		z := make(starlark.StringDict, x.len()+y.len())
   197  		for _, e := range x.entries {
   198  			z[e.name] = e.value
   199  		}
   200  		for _, e := range y.entries {
   201  			z[e.name] = e.value
   202  		}
   203  
   204  		return FromStringDict(x.constructor, z), nil
   205  	}
   206  	return nil, nil // unhandled
   207  }
   208  
   209  // Attr returns the value of the specified field.
   210  func (s *Struct) Attr(name string) (starlark.Value, error) {
   211  	// Binary search the entries.
   212  	// This implementation is a specialization of
   213  	// sort.Search that avoids dynamic dispatch.
   214  	n := len(s.entries)
   215  	i, j := 0, n
   216  	for i < j {
   217  		h := int(uint(i+j) >> 1)
   218  		if s.entries[h].name < name {
   219  			i = h + 1
   220  		} else {
   221  			j = h
   222  		}
   223  	}
   224  	if i < n && s.entries[i].name == name {
   225  		return s.entries[i].value, nil
   226  	}
   227  
   228  	var ctor string
   229  	if s.constructor != Default {
   230  		ctor = s.constructor.String() + " "
   231  	}
   232  	return nil, starlark.NoSuchAttrError(
   233  		fmt.Sprintf("%sstruct has no .%s attribute", ctor, name))
   234  }
   235  
   236  func (s *Struct) len() int { return len(s.entries) }
   237  
   238  // AttrNames returns a new sorted list of the struct fields.
   239  func (s *Struct) AttrNames() []string {
   240  	names := make([]string, len(s.entries))
   241  	for i, e := range s.entries {
   242  		names[i] = e.name
   243  	}
   244  	return names
   245  }
   246  
   247  func (x *Struct) CompareSameType(op syntax.Token, y_ starlark.Value, depth int) (bool, error) {
   248  	y := y_.(*Struct)
   249  	switch op {
   250  	case syntax.EQL:
   251  		return structsEqual(x, y, depth)
   252  	case syntax.NEQ:
   253  		eq, err := structsEqual(x, y, depth)
   254  		return !eq, err
   255  	default:
   256  		return false, fmt.Errorf("%s %s %s not implemented", x.Type(), op, y.Type())
   257  	}
   258  }
   259  
   260  func structsEqual(x, y *Struct, depth int) (bool, error) {
   261  	if x.len() != y.len() {
   262  		return false, nil
   263  	}
   264  
   265  	if eq, err := starlark.Equal(x.constructor, y.constructor); err != nil {
   266  		return false, fmt.Errorf("error comparing struct constructors %v and %v: %v",
   267  			x.constructor, y.constructor, err)
   268  	} else if !eq {
   269  		return false, nil
   270  	}
   271  
   272  	for i, n := 0, x.len(); i < n; i++ {
   273  		if x.entries[i].name != y.entries[i].name {
   274  			return false, nil
   275  		} else if eq, err := starlark.EqualDepth(x.entries[i].value, y.entries[i].value, depth-1); err != nil {
   276  			return false, err
   277  		} else if !eq {
   278  			return false, nil
   279  		}
   280  	}
   281  	return true, nil
   282  }
   283
View as plain text