internal/core/adt/feature.go - cue - Git at Google

 // Copyright 2020 CUE Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 package adt

 import (
 	"fmt"
 	"strconv"
 	"strings"

 	"cuelang.org/go/cue/ast"
 	"cuelang.org/go/cue/errors"
 	"cuelang.org/go/cue/literal"
 	"cuelang.org/go/cue/token"
 	"cuelang.org/go/internal"
 )

 // A Feature is an encoded form of a label which comprises a compact
 // representation of an integer or string label as well as a label type.
 type Feature uint32

 // TODO: create labels such that list are sorted first (or last with index.)

 // InvalidLabel is an encoding of an erroneous label.
 const (
 	InvalidLabel Feature = 0x7 // 0xb111

 	// MaxIndex indicates the maximum number of unique strings that are used for
 	// labeles within this CUE implementation.
 	MaxIndex = 1<<28 - 1
 )

 // These labels can be used for wildcard queries.
 var (
 	// AnyLabel represents any label or index.
 	AnyLabel Feature = 0

 	AnyDefinition Feature = makeLabel(MaxIndex, DefinitionLabel)
 	AnyHidden     Feature = makeLabel(MaxIndex, HiddenLabel)
 	AnyRegular    Feature = makeLabel(MaxIndex, StringLabel)
 	AnyIndex      Feature = makeLabel(MaxIndex, IntLabel)
 )

 // A StringIndexer coverts strings to and from an index that is unique for a
 // given string.
 type StringIndexer interface {
 	// ToIndex returns a unique positive index for s (0 < index < 2^28-1).
 	//
 	// For each pair of strings s and t it must return the same index if and
 	// only if s == t.
 	StringToIndex(s string) (index int64)

 	// ToString returns a string s for index such that ToIndex(s) == index.
 	IndexToString(index int64) string
 }

 // SelectorString reports the shortest string representation of f when used as a
 // selector.
 func (f Feature) SelectorString(index StringIndexer) string {
 	if f == 0 {
 		return "_"
 	}
 	x := f.safeIndex()
 	switch f.Typ() {
 	case IntLabel:
 		return strconv.Itoa(int(x))
 	case StringLabel:
 		s := index.IndexToString(x)
 		if ast.IsValidIdent(s) && !internal.IsDefOrHidden(s) {
 			return s
 		}
 		return literal.String.Quote(s)
 	default:
 		return f.IdentString(index)
 	}
 }

 // IdentString reports the identifier of f. The result is undefined if f
 // is not an identifier label.
 func (f Feature) IdentString(index StringIndexer) string {
 	s := index.IndexToString(f.safeIndex())
 	if f.IsHidden() {
 		if p := strings.IndexByte(s, '\x00'); p >= 0 {
 			s = s[:p]
 		}
 	}
 	return s
 }

 // PkgID returns the package identifier, composed of the module and package
 // name, associated with this identifier. It will return "" if this is not
 // a hidden label.
 func (f Feature) PkgID(index StringIndexer) string {
 	if !f.IsHidden() {
 		return ""
 	}
 	s := index.IndexToString(f.safeIndex())
 	if p := strings.IndexByte(s, '\x00'); p >= 0 {
 		return s[p+1:]
 	}
 	return s
 }

 // StringValue reports the string value of f, which must be a string label.
 func (f Feature) StringValue(index StringIndexer) string {
 	if !f.IsString() {
 		panic("not a string label")
 	}
 	x := f.safeIndex()
 	return index.IndexToString(x)
 }

 // ToValue converts a label to a value, which will be a Num for integer labels
 // and a String for string labels. It panics when f is not a regular label.
 func (f Feature) ToValue(ctx *OpContext) Value {
 	if !f.IsRegular() {
 		panic("not a regular label")
 	}
 	if f.IsInt() {
 		return ctx.NewInt64(int64(f.Index()))
 	}
 	x := f.safeIndex()
 	str := ctx.IndexToString(x)
 	return ctx.NewString(str)
 }

 // StringLabel converts s to a string label.
 func (c *OpContext) StringLabel(s string) Feature {
 	return labelFromValue(c, nil, &String{Str: s})
 }

 // MakeStringLabel creates a label for the given string.
 func MakeStringLabel(r StringIndexer, s string) Feature {
 	i := r.StringToIndex(s)

 	// TODO: set position if it exists.
 	f, err := MakeLabel(nil, i, StringLabel)
 	if err != nil {
 		panic("out of free string slots")
 	}
 	return f
 }

 // MakeIdentLabel creates a label for the given identifier.
 func MakeIdentLabel(r StringIndexer, s, pkgpath string) Feature {
 	t := StringLabel
 	switch {
 	case strings.HasPrefix(s, "_#"):
 		t = HiddenDefinitionLabel
 		s = fmt.Sprintf("%s\x00%s", s, pkgpath)
 	case strings.HasPrefix(s, "#"):
 		t = DefinitionLabel
 	case strings.HasPrefix(s, "_"):
 		s = fmt.Sprintf("%s\x00%s", s, pkgpath)
 		t = HiddenLabel
 	}
 	i := r.StringToIndex(s)
 	f, err := MakeLabel(nil, i, t)
 	if err != nil {
 		panic("out of free string slots")
 	}
 	return f
 }

 const msgGround = "invalid non-ground value %s (must be concrete %s)"

 func labelFromValue(c *OpContext, src Expr, v Value) Feature {
 	var i int64
 	var t FeatureType
 	if isError(v) {
 		return InvalidLabel
 	}
 	switch v.Kind() {
 	case IntKind, NumKind:
 		x, _ := Unwrap(v).(*Num)
 		if x == nil {
 			c.addErrf(IncompleteError, pos(v), msgGround, v, "int")
 			return InvalidLabel
 		}
 		t = IntLabel
 		var err error
 		i, err = x.X.Int64()
 		if err != nil || x.K != IntKind {
 			if src == nil {
 				src = v
 			}
 			c.AddErrf("invalid index %v: %v", src, err)
 			return InvalidLabel
 		}
 		if i < 0 {
 			switch src.(type) {
 			case nil, *Num, *UnaryExpr:
 				// If the value is a constant, we know it is always an error.
 				// UnaryExpr is an approximation for a constant value here.
 				c.AddErrf("invalid index %s (index must be non-negative)",
 					c.Str(x))
 			default:
 				// Use a different message is it is the result of evaluation.
 				c.AddErrf("index %s out of range [%s]", c.Str(src), c.Str(x))
 			}
 			return InvalidLabel
 		}

 	case StringKind:
 		x, _ := Unwrap(v).(*String)
 		if x == nil {
 			c.addErrf(IncompleteError, pos(v), msgGround, v, "string")
 			return InvalidLabel
 		}
 		t = StringLabel
 		i = c.StringToIndex(x.Str)

 	default:
 		if src != nil {
 			c.AddErrf("invalid index %s (invalid type %v)",
 				c.Str(src), v.Kind())
 		} else {
 			c.AddErrf("invalid index type %v", v.Kind())
 		}
 		return InvalidLabel
 	}

 	// TODO: set position if it exists.
 	f, err := MakeLabel(nil, i, t)
 	if err != nil {
 		c.AddErr(err)
 	}
 	return f
 }

 // MakeLabel creates a label. It reports an error if the index is out of range.
 func MakeLabel(src ast.Node, index int64, f FeatureType) (Feature, errors.Error) {
 	if 0 > index || index > MaxIndex-1 {
 		p := token.NoPos
 		if src != nil {
 			p = src.Pos()
 		}
 		return InvalidLabel,
 			errors.Newf(p, "int label out of range (%d not >=0 and <= %d)",
 				index, MaxIndex-1)
 	}
 	return Feature(index)<<indexShift | Feature(f), nil
 }

 func makeLabel(index int64, f FeatureType) Feature {
 	return Feature(index)<<indexShift | Feature(f)
 }

 // A FeatureType indicates the type of label.
 type FeatureType int8

 const (
 	StringLabel           FeatureType = 0 // 0b000
 	IntLabel              FeatureType = 1 // 0b001
 	DefinitionLabel       FeatureType = 3 // 0b011
 	HiddenLabel           FeatureType = 6 // 0b110
 	HiddenDefinitionLabel FeatureType = 7 // 0b111

 	// letLabel              FeatureType = 0b010

 	fTypeMask Feature = 7 // 0b111

 	indexShift = 3
 )

 func (f FeatureType) IsDef() bool {
 	return f&DefinitionLabel == DefinitionLabel
 }

 func (f FeatureType) IsHidden() bool {
 	return f&HiddenLabel == HiddenLabel
 }

 // IsValid reports whether f is a valid label.
 func (f Feature) IsValid() bool { return f != InvalidLabel }

 // Typ reports the type of label.
 func (f Feature) Typ() FeatureType { return FeatureType(f & fTypeMask) }

 // IsRegular reports whether a label represents a data field.
 func (f Feature) IsRegular() bool { return f.Typ() <= IntLabel }

 // IsString reports whether a label represents a regular field.
 func (f Feature) IsString() bool { return f.Typ() == StringLabel }

 // IsDef reports whether the label is a definition (an identifier starting with
 // # or #_.
 func (f Feature) IsDef() bool {
 	if f == InvalidLabel {
 		// TODO(perf): do more mask trickery to avoid this branch.
 		return false
 	}
 	return f.Typ().IsDef()
 }

 // IsInt reports whether this is an integer index.
 func (f Feature) IsInt() bool { return f.Typ() == IntLabel }

 // IsHidden reports whether this label is hidden (an identifier starting with
 // _ or #_).
 func (f Feature) IsHidden() bool {
 	if f == InvalidLabel {
 		// TODO(perf): do more mask trickery to avoid this branch.
 		return false
 	}
 	return f.Typ().IsHidden()
 }

 // Index reports the abstract index associated with f.
 func (f Feature) Index() int {
 	return int(f >> indexShift)
 }

 // SafeIndex reports the abstract index associated with f, setting MaxIndex to 0.
 func (f Feature) safeIndex() int64 {
 	x := int(f >> indexShift)
 	if x == MaxIndex {
 		x = 0 // Safety, MaxIndex means any
 	}
 	return int64(x)
 }

 // TODO: should let declarations be implemented as fields?
 // func (f Feature) isLet() bool  { return f.typ() == letLabel }
	// Copyright 2020 CUE Authors
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	package adt

	import (
	"fmt"
	"strconv"
	"strings"

	"cuelang.org/go/cue/ast"
	"cuelang.org/go/cue/errors"
	"cuelang.org/go/cue/literal"
	"cuelang.org/go/cue/token"
	"cuelang.org/go/internal"
	)

	// A Feature is an encoded form of a label which comprises a compact
	// representation of an integer or string label as well as a label type.
	type Feature uint32

	// TODO: create labels such that list are sorted first (or last with index.)

	// InvalidLabel is an encoding of an erroneous label.
	const (
	InvalidLabel Feature = 0x7 // 0xb111

	// MaxIndex indicates the maximum number of unique strings that are used for
	// labeles within this CUE implementation.
	MaxIndex = 1<<28 - 1
	)

	// These labels can be used for wildcard queries.
	var (
	// AnyLabel represents any label or index.
	AnyLabel Feature = 0

	AnyDefinition Feature = makeLabel(MaxIndex, DefinitionLabel)
	AnyHidden Feature = makeLabel(MaxIndex, HiddenLabel)
	AnyRegular Feature = makeLabel(MaxIndex, StringLabel)
	AnyIndex Feature = makeLabel(MaxIndex, IntLabel)
	)

	// A StringIndexer coverts strings to and from an index that is unique for a
	// given string.
	type StringIndexer interface {
	// ToIndex returns a unique positive index for s (0 < index < 2^28-1).
	//
	// For each pair of strings s and t it must return the same index if and
	// only if s == t.
	StringToIndex(s string) (index int64)

	// ToString returns a string s for index such that ToIndex(s) == index.
	IndexToString(index int64) string
	}

	// SelectorString reports the shortest string representation of f when used as a
	// selector.
	func (f Feature) SelectorString(index StringIndexer) string {
	if f == 0 {
	return "_"
	}
	x := f.safeIndex()
	switch f.Typ() {
	case IntLabel:
	return strconv.Itoa(int(x))
	case StringLabel:
	s := index.IndexToString(x)
	if ast.IsValidIdent(s) && !internal.IsDefOrHidden(s) {
	return s
	}
	return literal.String.Quote(s)
	default:
	return f.IdentString(index)
	}
	}

	// IdentString reports the identifier of f. The result is undefined if f
	// is not an identifier label.
	func (f Feature) IdentString(index StringIndexer) string {
	s := index.IndexToString(f.safeIndex())
	if f.IsHidden() {
	if p := strings.IndexByte(s, '\x00'); p >= 0 {
	s = s[:p]
	}
	}
	return s
	}

	// PkgID returns the package identifier, composed of the module and package
	// name, associated with this identifier. It will return "" if this is not
	// a hidden label.
	func (f Feature) PkgID(index StringIndexer) string {
	if !f.IsHidden() {
	return ""
	}
	s := index.IndexToString(f.safeIndex())
	if p := strings.IndexByte(s, '\x00'); p >= 0 {
	return s[p+1:]
	}
	return s
	}

	// StringValue reports the string value of f, which must be a string label.
	func (f Feature) StringValue(index StringIndexer) string {
	if !f.IsString() {
	panic("not a string label")
	}
	x := f.safeIndex()
	return index.IndexToString(x)
	}

	// ToValue converts a label to a value, which will be a Num for integer labels
	// and a String for string labels. It panics when f is not a regular label.
	func (f Feature) ToValue(ctx *OpContext) Value {
	if !f.IsRegular() {
	panic("not a regular label")
	}
	if f.IsInt() {
	return ctx.NewInt64(int64(f.Index()))
	}
	x := f.safeIndex()
	str := ctx.IndexToString(x)
	return ctx.NewString(str)
	}

	// StringLabel converts s to a string label.
	func (c *OpContext) StringLabel(s string) Feature {
	return labelFromValue(c, nil, &String{Str: s})
	}

	// MakeStringLabel creates a label for the given string.
	func MakeStringLabel(r StringIndexer, s string) Feature {
	i := r.StringToIndex(s)

	// TODO: set position if it exists.
	f, err := MakeLabel(nil, i, StringLabel)
	if err != nil {
	panic("out of free string slots")
	}
	return f
	}

	// MakeIdentLabel creates a label for the given identifier.
	func MakeIdentLabel(r StringIndexer, s, pkgpath string) Feature {
	t := StringLabel
	switch {
	case strings.HasPrefix(s, "_#"):
	t = HiddenDefinitionLabel
	s = fmt.Sprintf("%s\x00%s", s, pkgpath)
	case strings.HasPrefix(s, "#"):
	t = DefinitionLabel
	case strings.HasPrefix(s, "_"):
	s = fmt.Sprintf("%s\x00%s", s, pkgpath)
	t = HiddenLabel
	}
	i := r.StringToIndex(s)
	f, err := MakeLabel(nil, i, t)
	if err != nil {
	panic("out of free string slots")
	}
	return f
	}

	const msgGround = "invalid non-ground value %s (must be concrete %s)"

	func labelFromValue(c *OpContext, src Expr, v Value) Feature {
	var i int64
	var t FeatureType
	if isError(v) {
	return InvalidLabel
	}
	switch v.Kind() {
	case IntKind, NumKind:
	x, _ := Unwrap(v).(*Num)
	if x == nil {
	c.addErrf(IncompleteError, pos(v), msgGround, v, "int")
	return InvalidLabel
	}
	t = IntLabel
	var err error
	i, err = x.X.Int64()
	if err != nil \|\| x.K != IntKind {
	if src == nil {
	src = v
	}
	c.AddErrf("invalid index %v: %v", src, err)
	return InvalidLabel
	}
	if i < 0 {
	switch src.(type) {
	case nil, Num, UnaryExpr:
	// If the value is a constant, we know it is always an error.
	// UnaryExpr is an approximation for a constant value here.
	c.AddErrf("invalid index %s (index must be non-negative)",
	c.Str(x))
	default:
	// Use a different message is it is the result of evaluation.
	c.AddErrf("index %s out of range [%s]", c.Str(src), c.Str(x))
	}
	return InvalidLabel
	}

	case StringKind:
	x, _ := Unwrap(v).(*String)
	if x == nil {
	c.addErrf(IncompleteError, pos(v), msgGround, v, "string")
	return InvalidLabel
	}
	t = StringLabel
	i = c.StringToIndex(x.Str)

	default:
	if src != nil {
	c.AddErrf("invalid index %s (invalid type %v)",
	c.Str(src), v.Kind())
	} else {
	c.AddErrf("invalid index type %v", v.Kind())
	}
	return InvalidLabel
	}

	// TODO: set position if it exists.
	f, err := MakeLabel(nil, i, t)
	if err != nil {
	c.AddErr(err)
	}
	return f
	}

	// MakeLabel creates a label. It reports an error if the index is out of range.
	func MakeLabel(src ast.Node, index int64, f FeatureType) (Feature, errors.Error) {
	if 0 > index \|\| index > MaxIndex-1 {
	p := token.NoPos
	if src != nil {
	p = src.Pos()
	}
	return InvalidLabel,
	errors.Newf(p, "int label out of range (%d not >=0 and <= %d)",
	index, MaxIndex-1)
	}
	return Feature(index)<<indexShift \| Feature(f), nil
	}

	func makeLabel(index int64, f FeatureType) Feature {
	return Feature(index)<<indexShift \| Feature(f)
	}

	// A FeatureType indicates the type of label.
	type FeatureType int8

	const (
	StringLabel FeatureType = 0 // 0b000
	IntLabel FeatureType = 1 // 0b001
	DefinitionLabel FeatureType = 3 // 0b011
	HiddenLabel FeatureType = 6 // 0b110
	HiddenDefinitionLabel FeatureType = 7 // 0b111

	// letLabel FeatureType = 0b010

	fTypeMask Feature = 7 // 0b111

	indexShift = 3
	)

	func (f FeatureType) IsDef() bool {
	return f&DefinitionLabel == DefinitionLabel
	}

	func (f FeatureType) IsHidden() bool {
	return f&HiddenLabel == HiddenLabel
	}

	// IsValid reports whether f is a valid label.
	func (f Feature) IsValid() bool { return f != InvalidLabel }

	// Typ reports the type of label.
	func (f Feature) Typ() FeatureType { return FeatureType(f & fTypeMask) }

	// IsRegular reports whether a label represents a data field.
	func (f Feature) IsRegular() bool { return f.Typ() <= IntLabel }

	// IsString reports whether a label represents a regular field.
	func (f Feature) IsString() bool { return f.Typ() == StringLabel }

	// IsDef reports whether the label is a definition (an identifier starting with
	// # or #_.
	func (f Feature) IsDef() bool {
	if f == InvalidLabel {
	// TODO(perf): do more mask trickery to avoid this branch.
	return false
	}
	return f.Typ().IsDef()
	}

	// IsInt reports whether this is an integer index.
	func (f Feature) IsInt() bool { return f.Typ() == IntLabel }

	// IsHidden reports whether this label is hidden (an identifier starting with
	// _ or #_).
	func (f Feature) IsHidden() bool {
	if f == InvalidLabel {
	// TODO(perf): do more mask trickery to avoid this branch.
	return false
	}
	return f.Typ().IsHidden()
	}

	// Index reports the abstract index associated with f.
	func (f Feature) Index() int {
	return int(f >> indexShift)
	}

	// SafeIndex reports the abstract index associated with f, setting MaxIndex to 0.
	func (f Feature) safeIndex() int64 {
	x := int(f >> indexShift)
	if x == MaxIndex {
	x = 0 // Safety, MaxIndex means any
	}
	return int64(x)
	}

	// TODO: should let declarations be implemented as fields?
	// func (f Feature) isLet() bool { return f.typ() == letLabel }