blob: a09931408bd66ae3a880097e12386b5f97b6e905 [file] [log] [blame]
// 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 {
s = 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")
}
// TODO: Handle special regular values: invalid and AnyRegular.
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)", x)
default:
// Use a different message is it is the result of evaluation.
c.AddErrf("index %s out of range [%s]", src, 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)", 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 }