feature.go

Documentation: cuelang.org/go/internal/core/adt

     1  // Copyright 2020 CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package adt
    16  
    17  import (
    18  	"fmt"
    19  	"strconv"
    20  	"strings"
    21  
    22  	"cuelang.org/go/cue/ast"
    23  	"cuelang.org/go/cue/errors"
    24  	"cuelang.org/go/cue/literal"
    25  	"cuelang.org/go/cue/token"
    26  	"cuelang.org/go/internal"
    27  )
    28  
    29  // A Feature is an encoded form of a label which comprises a compact
    30  // representation of an integer or string label as well as a label type.
    31  type Feature uint32
    32  
    33  // TODO: create labels such that list are sorted first (or last with index.)
    34  
    35  // InvalidLabel is an encoding of an erroneous label.
    36  const (
    37  	InvalidLabel Feature = 0
    38  
    39  	// MaxIndex indicates the maximum number of unique strings that are used for
    40  	// labels within this CUE implementation.
    41  	MaxIndex = 1<<(32-indexShift) - 1
    42  )
    43  
    44  // These labels can be used for wildcard queries.
    45  var (
    46  	AnyDefinition Feature = makeLabel(MaxIndex, DefinitionLabel)
    47  	AnyHidden     Feature = makeLabel(MaxIndex, HiddenLabel)
    48  	AnyString     Feature = makeLabel(MaxIndex, StringLabel)
    49  	AnyIndex      Feature = makeLabel(MaxIndex, IntLabel)
    50  )
    51  
    52  // A StringIndexer coverts strings to and from an index that is unique for a
    53  // given string.
    54  type StringIndexer interface {
    55  	// ToIndex returns a unique positive index for s (0 < index < 2^28-1).
    56  	//
    57  	// For each pair of strings s and t it must return the same index if and
    58  	// only if s == t.
    59  	StringToIndex(s string) (index int64)
    60  
    61  	// ToString returns a string s for index such that ToIndex(s) == index.
    62  	IndexToString(index int64) string
    63  
    64  	// NextUniqueID returns a new unique identifier.
    65  	NextUniqueID() uint64
    66  }
    67  
    68  // SelectorString reports the shortest string representation of f when used as a
    69  // selector.
    70  func (f Feature) SelectorString(index StringIndexer) string {
    71  	x := f.safeIndex()
    72  	switch f.Typ() {
    73  	case IntLabel:
    74  		if f == AnyIndex {
    75  			return "_"
    76  		}
    77  		return strconv.Itoa(int(x))
    78  	case StringLabel:
    79  		s := index.IndexToString(x)
    80  		if ast.IsValidIdent(s) && !internal.IsDefOrHidden(s) {
    81  			return s
    82  		}
    83  		if f == AnyString {
    84  			return "_"
    85  		}
    86  		return literal.String.Quote(s)
    87  	default:
    88  		return f.IdentString(index)
    89  	}
    90  }
    91  
    92  // IdentString reports the identifier of f. The result is undefined if f
    93  // is not an identifier label.
    94  func (f Feature) IdentString(index StringIndexer) string {
    95  	s := index.IndexToString(f.safeIndex())
    96  	if f.IsHidden() || f.IsLet() {
    97  		if p := strings.IndexByte(s, '\x00'); p >= 0 {
    98  			s = s[:p]
    99  		}
   100  	}
   101  	return s
   102  }
   103  
   104  // PkgID returns the package identifier, composed of the module and package
   105  // name, associated with this identifier. It will return "" if this is not
   106  // a hidden label.
   107  func (f Feature) PkgID(index StringIndexer) string {
   108  	if !f.IsHidden() {
   109  		return ""
   110  	}
   111  	s := index.IndexToString(f.safeIndex())
   112  	if p := strings.IndexByte(s, '\x00'); p >= 0 {
   113  		s = s[p+1:]
   114  	}
   115  	return s
   116  }
   117  
   118  // StringValue reports the string value of f, which must be a string label.
   119  func (f Feature) StringValue(index StringIndexer) string {
   120  	if !f.IsString() {
   121  		panic("not a string label")
   122  	}
   123  	x := f.safeIndex()
   124  	return index.IndexToString(x)
   125  }
   126  
   127  // RawString reports the underlying string value of f without interpretation.
   128  func (f Feature) RawString(index StringIndexer) string {
   129  	x := f.safeIndex()
   130  	return index.IndexToString(x)
   131  }
   132  
   133  // ToValue converts a label to a value, which will be a Num for integer labels
   134  // and a String for string labels. It panics when f is not a regular label.
   135  func (f Feature) ToValue(ctx *OpContext) Value {
   136  	if !f.IsRegular() {
   137  		panic("not a regular label")
   138  	}
   139  	// TODO: Handle special regular values: invalid and AnyRegular.
   140  	if f.IsInt() {
   141  		return ctx.NewInt64(int64(f.Index()))
   142  	}
   143  	x := f.safeIndex()
   144  	str := ctx.IndexToString(x)
   145  	return ctx.NewString(str)
   146  }
   147  
   148  // StringLabel converts s to a string label.
   149  func (c *OpContext) StringLabel(s string) Feature {
   150  	return LabelFromValue(c, nil, &String{Str: s})
   151  }
   152  
   153  // MakeStringLabel creates a label for the given string.
   154  func MakeStringLabel(r StringIndexer, s string) Feature {
   155  	i := r.StringToIndex(s)
   156  
   157  	// TODO: set position if it exists.
   158  	f, err := MakeLabel(nil, i, StringLabel)
   159  	if err != nil {
   160  		panic("out of free string slots")
   161  	}
   162  	return f
   163  }
   164  
   165  // MakeIdentLabel creates a label for the given identifier.
   166  func MakeIdentLabel(r StringIndexer, s, pkgpath string) Feature {
   167  	t := StringLabel
   168  	switch {
   169  	case strings.HasPrefix(s, "_#"):
   170  		t = HiddenDefinitionLabel
   171  		s = HiddenKey(s, pkgpath)
   172  	case strings.HasPrefix(s, "#"):
   173  		t = DefinitionLabel
   174  	case strings.HasPrefix(s, "_"):
   175  		s = HiddenKey(s, pkgpath)
   176  		t = HiddenLabel
   177  	}
   178  	i := r.StringToIndex(s)
   179  	f, err := MakeLabel(nil, i, t)
   180  	if err != nil {
   181  		panic("out of free string slots")
   182  	}
   183  	return f
   184  }
   185  
   186  // HiddenKey constructs the uniquely identifying string for a hidden fields and
   187  // its package.
   188  func HiddenKey(s, pkgPath string) string {
   189  	// TODO: Consider just using space instead of \x00.
   190  	return fmt.Sprintf("%s\x00%s", s, pkgPath)
   191  }
   192  
   193  // MakeNamedLabel creates a feature for the given name and feature type.
   194  func MakeNamedLabel(r StringIndexer, t FeatureType, s string) Feature {
   195  	i := r.StringToIndex(s)
   196  	f, err := MakeLabel(nil, i, t)
   197  	if err != nil {
   198  		panic("out of free string slots")
   199  	}
   200  	return f
   201  }
   202  
   203  // MakeLetLabel creates a label for the given let identifier s.
   204  //
   205  // A let declaration is always logically unique within its scope and will never
   206  // unify with a let field of another struct. This is enforced by ensuring that
   207  // the let identifier is unique across an entire configuration. This, in turn,
   208  // is done by adding a unique number to each let identifier.
   209  func MakeLetLabel(r StringIndexer, s string) Feature {
   210  	id := r.NextUniqueID()
   211  	s = fmt.Sprintf("%s\x00%X", s, id)
   212  	i := r.StringToIndex(s)
   213  	f, err := MakeLabel(nil, i, LetLabel)
   214  	if err != nil {
   215  		panic("out of free string slots")
   216  	}
   217  	return f
   218  }
   219  
   220  // MakeIntLabel creates an integer label.
   221  func MakeIntLabel(t FeatureType, i int64) Feature {
   222  	f, err := MakeLabel(nil, i, t)
   223  	if err != nil {
   224  		panic("index out of range")
   225  	}
   226  	return f
   227  }
   228  
   229  const msgGround = "invalid non-ground value %s (must be concrete %s)"
   230  
   231  func LabelFromValue(c *OpContext, src Expr, v Value) Feature {
   232  	v, _ = c.getDefault(v)
   233  
   234  	var i int64
   235  	var t FeatureType
   236  	if isError(v) {
   237  		return InvalidLabel
   238  	}
   239  	switch v.Kind() {
   240  	case IntKind, NumKind:
   241  		x, _ := Unwrap(v).(*Num)
   242  		if x == nil {
   243  			c.addErrf(IncompleteError, pos(v), msgGround, v, "int")
   244  			return InvalidLabel
   245  		}
   246  		t = IntLabel
   247  		var err error
   248  		i, err = x.X.Int64()
   249  		if err != nil || x.K != IntKind {
   250  			if src == nil {
   251  				src = v
   252  			}
   253  			c.AddErrf("invalid index %v: %v", src, err)
   254  			return InvalidLabel
   255  		}
   256  		if i < 0 {
   257  			switch src.(type) {
   258  			case nil, *Num, *UnaryExpr:
   259  				// If the value is a constant, we know it is always an error.
   260  				// UnaryExpr is an approximation for a constant value here.
   261  				c.AddErrf("invalid index %v (index must be non-negative)", x)
   262  			default:
   263  				// Use a different message is it is the result of evaluation.
   264  				c.AddErrf("index %v out of range [%v]", src, x)
   265  			}
   266  			return InvalidLabel
   267  		}
   268  
   269  	case StringKind:
   270  		x, _ := Unwrap(v).(*String)
   271  		if x == nil {
   272  			c.addErrf(IncompleteError, pos(v), msgGround, v, "string")
   273  			return InvalidLabel
   274  		}
   275  		t = StringLabel
   276  		i = c.StringToIndex(x.Str)
   277  
   278  	default:
   279  		if src != nil {
   280  			c.AddErrf("invalid index %s (invalid type %v)", src, v.Kind())
   281  		} else {
   282  			c.AddErrf("invalid index type %v", v.Kind())
   283  		}
   284  		return InvalidLabel
   285  	}
   286  
   287  	// TODO: set position if it exists.
   288  	f, err := MakeLabel(nil, i, t)
   289  	if err != nil {
   290  		c.AddErr(err)
   291  	}
   292  	return f
   293  }
   294  
   295  // MakeLabel creates a label. It reports an error if the index is out of range.
   296  func MakeLabel(src ast.Node, index int64, f FeatureType) (Feature, errors.Error) {
   297  	if 0 > index || index > MaxIndex-1 {
   298  		p := token.NoPos
   299  		if src != nil {
   300  			p = src.Pos()
   301  		}
   302  		return InvalidLabel,
   303  			errors.Newf(p, "int label out of range (%d not >=0 and <= %d)",
   304  				index, MaxIndex-1)
   305  	}
   306  	return Feature(index)<<indexShift | Feature(f), nil
   307  }
   308  
   309  func makeLabel(index int64, f FeatureType) Feature {
   310  	return Feature(index)<<indexShift | Feature(f)
   311  }
   312  
   313  // A FeatureType indicates the type of label.
   314  type FeatureType int8
   315  
   316  const (
   317  	InvalidLabelType FeatureType = iota
   318  	StringLabel
   319  	IntLabel
   320  	DefinitionLabel
   321  	HiddenLabel
   322  	HiddenDefinitionLabel
   323  	LetLabel
   324  )
   325  
   326  const (
   327  	fTypeMask Feature = 0b1111
   328  
   329  	indexShift = 4
   330  )
   331  
   332  func (f FeatureType) IsDef() bool {
   333  	return f == DefinitionLabel || f == HiddenDefinitionLabel
   334  }
   335  
   336  func (f FeatureType) IsHidden() bool {
   337  	return f == HiddenLabel || f == HiddenDefinitionLabel
   338  }
   339  
   340  func (f FeatureType) IsLet() bool {
   341  	return f == LetLabel
   342  }
   343  
   344  // IsValid reports whether f is a valid label.
   345  func (f Feature) IsValid() bool { return f != InvalidLabel }
   346  
   347  // Typ reports the type of label.
   348  func (f Feature) Typ() FeatureType { return FeatureType(f & fTypeMask) }
   349  
   350  // IsRegular reports whether a label represents a data field.
   351  func (f Feature) IsRegular() bool {
   352  	t := f.Typ()
   353  	return t == IntLabel || t == StringLabel
   354  }
   355  
   356  // IsString reports whether a label represents a regular field.
   357  func (f Feature) IsString() bool { return f.Typ() == StringLabel }
   358  
   359  // IsDef reports whether the label is a definition (an identifier starting with
   360  // # or _#.
   361  func (f Feature) IsDef() bool {
   362  	return f.Typ().IsDef()
   363  }
   364  
   365  // IsInt reports whether this is an integer index.
   366  func (f Feature) IsInt() bool { return f.Typ() == IntLabel }
   367  
   368  // IsHidden reports whether this label is hidden (an identifier starting with
   369  // _ or #_).
   370  func (f Feature) IsHidden() bool {
   371  	return f.Typ().IsHidden()
   372  }
   373  
   374  // IsLet reports whether this label is a let field (like `let X = value`).
   375  func (f Feature) IsLet() bool {
   376  	return f.Typ().IsLet()
   377  }
   378  
   379  // Index reports the abstract index associated with f.
   380  func (f Feature) Index() int {
   381  	return int(f >> indexShift)
   382  }
   383  
   384  // SafeIndex reports the abstract index associated with f, setting MaxIndex to 0.
   385  func (f Feature) safeIndex() int64 {
   386  	x := int(f >> indexShift)
   387  	if x == MaxIndex {
   388  		x = 0 // Safety, MaxIndex means any
   389  	}
   390  	return int64(x)
   391  }
   392  
   393  // TODO: should let declarations be implemented as fields?
   394  // func (f Feature) isLet() bool  { return f.typ() == letLabel }
   395
View as plain text