| // 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 } |