| // Copyright 2018 The 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 trim removes definitions that may be inferred from |
| // templates. |
| // |
| // A field, struct, or list is removed if it is implied by a constraint, such |
| // as from an optional field matching a required field, a list type value, |
| // a comprehension or any other implied content. It will modify the files in place. |
| // |
| // Limitations |
| // |
| // Removal is on a best effort basis. Some caveats: |
| // - Fields in implied content may refer to fields within the struct in which |
| // they are included, but are only resolved on a best-effort basis. |
| // - Disjunctions that contain structs in implied content cannot be used to |
| // remove fields. |
| // - There is currently no verification step: manual verification is required. |
| // |
| // Examples: |
| // |
| // light: [string]: { |
| // room: string |
| // brightnessOff: *0.0 | >=0 & <=100.0 |
| // brightnessOn: *100.0 | >=0 & <=100.0 |
| // } |
| // |
| // light: ceiling50: { |
| // room: "MasterBedroom" |
| // brightnessOff: 0.0 // this line |
| // brightnessOn: 100.0 // and this line will be removed |
| // } |
| // |
| // Results in: |
| // |
| // light: [string]: { |
| // room: string |
| // brightnessOff: *0.0 | >=0 & <=100.0 |
| // brightnessOn: *100.0 | >=0 & <=100.0 |
| // } |
| // |
| // light: ceiling50: { |
| // room: "MasterBedroom" |
| // } |
| // |
| package trim |
| |
| import ( |
| "bytes" |
| "fmt" |
| "strconv" |
| "strings" |
| |
| "cuelang.org/go/cue/ast" |
| "cuelang.org/go/cue/token" |
| "cuelang.org/go/internal" |
| |
| // "cuelang.org/go/cue" |
| "cuelang.org/go/cue" |
| ) |
| |
| type Runtime = cue.Runtime |
| |
| // TODO: |
| // - remove the limitations mentioned in the documentation |
| // - implement verification post-processing as extra safety |
| |
| // Config configures trim options. |
| type Config struct { |
| Trace bool |
| } |
| |
| // Files trims fields in the given files that can be implied from other fields, |
| // as can be derived from the evaluated values in inst. |
| // Trimming is done on a best-effort basis and only when the removed field |
| // is clearly implied by another field, rather than equal sibling fields. |
| func Files(files []*ast.File, inst *cue.Instance, cfg *Config) error { |
| gen := newTrimSet(cfg) |
| gen.files = files |
| for _, f := range files { |
| gen.markNodes(f) |
| } |
| |
| root := inst.Lookup() |
| rm := gen.trim("root", root, cue.Value{}, root) |
| |
| for _, f := range files { |
| f.Decls = gen.trimDecls(f.Decls, rm, cue.Value{}, true) |
| } |
| return nil |
| } |
| |
| type trimSet struct { |
| cfg Config |
| files []*ast.File |
| stack []string |
| exclude map[ast.Node]bool // don't remove fields marked here |
| alwaysGen map[ast.Node]bool // node is always from a generated source |
| fromComp map[ast.Node]bool // node originated from a comprehension |
| } |
| |
| func newTrimSet(cfg *Config) *trimSet { |
| if cfg == nil { |
| cfg = &Config{} |
| } |
| return &trimSet{ |
| cfg: *cfg, |
| exclude: map[ast.Node]bool{}, |
| alwaysGen: map[ast.Node]bool{}, |
| fromComp: map[ast.Node]bool{}, |
| } |
| } |
| |
| func (t *trimSet) path() string { |
| return strings.Join(t.stack[1:], " ") |
| } |
| |
| func (t *trimSet) traceMsg(msg string) { |
| if t.cfg.Trace { |
| fmt.Print(t.path()) |
| msg = strings.TrimRight(msg, "\n") |
| msg = strings.Replace(msg, "\n", "\n ", -1) |
| fmt.Printf(": %s\n", msg) |
| } |
| } |
| |
| func (t *trimSet) markNodes(n ast.Node) { |
| ast.Walk(n, nil, func(n ast.Node) { |
| switch x := n.(type) { |
| case *ast.Ident: |
| if x.Node != nil { |
| t.exclude[x.Node] = true |
| } |
| if x.Scope != nil { |
| t.exclude[x.Scope] = true |
| } |
| |
| case *ast.ListLit: |
| _, e := internal.ListEllipsis(x) |
| if e != nil && e.Type != nil { |
| t.markAlwaysGen(e.Type, false) |
| } |
| |
| case *ast.Field: |
| switch x.Label.(type) { |
| case *ast.TemplateLabel, *ast.ListLit: |
| t.markAlwaysGen(x.Value, false) |
| } |
| |
| case *ast.ListComprehension, *ast.Comprehension: |
| t.markAlwaysGen(x, true) |
| } |
| }) |
| } |
| |
| func (t *trimSet) markAlwaysGen(first ast.Node, isComp bool) { |
| ast.Walk(first, func(n ast.Node) bool { |
| if t.alwaysGen[n] { |
| return false |
| } |
| t.alwaysGen[n] = true |
| if isComp { |
| t.fromComp[n] = true |
| } |
| if x, ok := n.(*ast.Ident); ok && n != first { |
| // Also mark any value used within a constraint from an optional field. |
| if x.Node != nil { |
| // fmt.Println("MARKED", internal.DebugStr(x.Node), |
| // "by", internal.DebugStr(first)) |
| // t.markAlwaysGen(x.Node) |
| } |
| } |
| return true |
| }, nil) |
| } |
| |
| func (t *trimSet) canRemove(n ast.Node) bool { |
| return !t.exclude[n] && !t.alwaysGen[n] |
| } |
| |
| func isDisjunctionOfStruct(n ast.Node) bool { |
| switch x := n.(type) { |
| case *ast.BinaryExpr: |
| if x.Op == token.OR { |
| return hasStruct(x.X) || hasStruct(x.Y) |
| } |
| } |
| return false |
| } |
| |
| func hasStruct(n ast.Node) bool { |
| hasStruct := false |
| ast.Walk(n, func(n ast.Node) bool { |
| if _, ok := n.(*ast.StructLit); ok { |
| hasStruct = true |
| } |
| return !hasStruct |
| }, nil) |
| return hasStruct |
| } |
| |
| // trim strips fields from structs that would otherwise be generated by implied |
| // content, such as optional fields turned required, comprehensions, and list types. |
| // |
| // The algorithm walks the tree with two values in parallel: one for the full |
| // configuration, and one for implied content. For each node in the tree it |
| // determines the value of the implied content and that of the full value |
| // and strips any of the non-implied fields if it subsumes the implied ones. |
| // |
| // There are a few gotchas: |
| // - Fields in the implied content may refer to fields in the complete config. |
| // To support this, incomplete fields are detected and evaluated within the |
| // configuration. |
| // - Values of optional fields are instantiated as a result of the declaration |
| // of concrete sibling fields. Such fields should not be removed even if the |
| // instantiated constraint completely subsumes such fields as the reason to |
| // apply the optional constraint will disappear with it. |
| // - As the parallel structure is different, it may resolve to different |
| // default values. There is no support yet for selecting defaults of a value |
| // based on another value without doing a full unification. So for now we |
| // skip any disjunction containing structs. |
| // |
| // v the current value |
| // m the "mixed-in" values |
| // scope in which to evaluate expressions |
| // rmSet nodes in v that may be removed by the caller |
| func (t *trimSet) trim(label string, v, m, scope cue.Value) (rmSet []ast.Node) { |
| saved := t.stack |
| t.stack = append(t.stack, label) |
| defer func() { t.stack = saved }() |
| |
| vSplit := v.Split() |
| |
| // At the moment disjunctions of structs are not supported. Detect them and |
| // punt. |
| // TODO: support disjunctions. |
| mSplit := m.Split() |
| for _, v := range mSplit { |
| if isDisjunctionOfStruct(v.Source()) { |
| return |
| } |
| } |
| |
| // Collect generated nodes. |
| // Only keep the good parts of the optional constraint. |
| // Incoming structs may be incomplete resulting in errors. It is safe |
| // to ignore these. If there is an actual error, it will manifest in |
| // the evaluation of v. |
| in := cue.Value{} |
| gen := []ast.Node{} |
| for _, v := range mSplit { |
| // TODO: consider resolving incomplete values within the current |
| // scope, as we do for fields. |
| if v.Exists() { |
| in = in.UnifyAccept(v, m) |
| } |
| gen = append(gen, v.Source()) |
| } |
| |
| accept := v |
| comp := in |
| |
| // Identify generated components and unify them with the mixin value. |
| exists := false |
| for _, v := range vSplit { |
| src := v.Source() |
| alwaysGen := t.alwaysGen[src] |
| inNodes := inNodes(gen, src) |
| fromComp := t.fromComp[src] |
| if fromComp { |
| gen = append(gen, src) |
| comp = comp.UnifyAccept(v, accept) |
| continue |
| } |
| if !(alwaysGen || inNodes) { |
| continue |
| } |
| |
| if !v.IsConcrete() { |
| // The template has an expression that cannot be fully |
| // resolved. Attempt to complete the expression by |
| // evaluting it within the struct to which the template |
| // is applied. |
| expr := internal.ToExpr(v.Syntax()) |
| |
| // TODO: this only resolves references contained in scope. |
| v = internal.EvalExpr(scope, expr).(cue.Value) |
| } |
| |
| if w := in.UnifyAccept(v, accept); w.Err() == nil { |
| in = w |
| } |
| // One of the sources of this struct is generated. That means |
| // we can safely delete a non-generated version. |
| exists = true |
| gen = append(gen, src) |
| } |
| |
| switch v.Kind() { |
| case cue.StructKind: |
| // Build map of mixin fields. |
| valueMap := map[key]cue.Value{} |
| for mIter, _ := in.Fields(cue.All(), cue.Optional(false)); mIter.Next(); { |
| valueMap[iterKey(mIter)] = mIter.Value() |
| } |
| |
| fn := v.Template() |
| |
| // Process fields. |
| rm := []ast.Node{} |
| for iter, _ := v.Fields(cue.All()); iter.Next(); { |
| mSub := valueMap[iterKey(iter)] |
| if fn != nil { |
| label := iter.Label() |
| w := fn(label) |
| mSub = mSub.Unify(w) |
| } |
| |
| label := iter.Label() |
| removed := t.trim(label, iter.Value(), mSub, v) |
| rm = append(rm, removed...) |
| } |
| |
| canRemove := fn == nil |
| for _, v := range vSplit { |
| src := v.Source() |
| if t.fromComp[src] { |
| canRemove = true |
| } |
| } |
| |
| // Remove fields from source. |
| for _, v := range vSplit { |
| if src := v.Source(); !t.alwaysGen[src] { |
| switch x := src.(type) { |
| case *ast.File: |
| // TODO: use in instead? |
| x.Decls = t.trimDecls(x.Decls, rm, m, canRemove) |
| |
| case *ast.StructLit: |
| x.Elts = t.trimDecls(x.Elts, rm, m, canRemove) |
| exists = exists || m.Exists() |
| if len(x.Elts) == 0 && exists && t.canRemove(src) && !inNodes(gen, src) { |
| rmSet = append(rmSet, src) |
| } |
| |
| default: |
| // Currently the ast.Files are not associated with the |
| // nodes. We detect this case here and iterate over all |
| // files. |
| // TODO: fix this. See cue/instance.go. |
| if len(t.stack) == 1 { |
| for _, x := range t.files { |
| x.Decls = t.trimDecls(x.Decls, rm, m, canRemove) |
| } |
| } |
| } |
| } |
| } |
| |
| if t.cfg.Trace { |
| w := &bytes.Buffer{} |
| fmt.Fprintln(w) |
| fmt.Fprintln(w, "value: ", v) |
| if in.Exists() { |
| fmt.Fprintln(w, "mixed in: ", in) |
| } |
| for _, v := range vSplit { |
| status := "[]" |
| src := v.Source() |
| if inNodes(rmSet, src) { |
| status = "[re]" |
| } else if t.alwaysGen[src] { |
| status = "[i]" |
| } |
| fmt.Fprintf(w, " %4s %v: %v %T\n", status, v.Pos(), internal.DebugStr(src), src) |
| } |
| |
| t.traceMsg(w.String()) |
| } |
| |
| case cue.ListKind: |
| mIter, _ := m.List() |
| elem, hasElem := m.Elem() |
| i := 0 |
| rmElem := []ast.Node{} |
| allowRemove := true |
| for iter, _ := v.List(); iter.Next(); i++ { |
| var m cue.Value |
| if mIter.Next() { |
| m = mIter.Value() |
| } else if hasElem { |
| m = elem |
| allowRemove = false |
| } else { |
| allowRemove = false |
| break |
| } |
| rm := t.trim(strconv.Itoa(i), iter.Value(), m, scope) |
| rmElem = append(rmElem, rm...) |
| } |
| |
| // Signal the removal of lists of which all elements have been marked |
| // for removal. |
| if allowRemove { |
| for _, v := range vSplit { |
| if src := v.Source(); !t.alwaysGen[src] { |
| l, ok := src.(*ast.ListLit) |
| if !ok { |
| break |
| } |
| rmList := true |
| iter, _ := v.List() |
| for i := 0; i < len(l.Elts) && iter.Next(); i++ { |
| if !inNodes(rmElem, l.Elts[i]) { |
| rmList = false |
| break |
| } |
| } |
| if rmList && m.Exists() && t.canRemove(src) && !inNodes(gen, src) { |
| rmSet = append(rmSet, src) |
| } |
| } |
| } |
| } |
| fallthrough |
| |
| default: |
| // Mark any subsumed part that is covered by generated config. |
| in, _ := in.Default() |
| if in.Err() == nil && v.Subsume(in) == nil { |
| for _, v := range vSplit { |
| src := v.Source() |
| if t.canRemove(src) && !inNodes(gen, src) && |
| exists { |
| rmSet = append(rmSet, src) |
| } |
| } |
| } |
| |
| if t.cfg.Trace { |
| w := &bytes.Buffer{} |
| if len(rmSet) > 0 { |
| fmt.Fprint(w, "field: SUBSUMED\n") |
| } else { |
| fmt.Fprint(w, "field: \n") |
| } |
| fmt.Fprintln(w, "value: ", v) |
| if in.Exists() { |
| fmt.Fprintln(w, "mixed in: ", in) |
| } |
| for _, v := range vSplit { |
| status := "[" |
| if inNodes(gen, v.Source()) { |
| status += "i" |
| } |
| if inNodes(rmSet, v.Source()) { |
| status += "r" |
| } |
| status += "]" |
| src := v.Source() |
| fmt.Fprintf(w, " %4s %v: %v\n", status, v.Pos(), internal.DebugStr(src)) |
| } |
| |
| t.traceMsg(w.String()) |
| } |
| } |
| |
| if comp.Exists() { |
| if v.Subsume(comp) == nil { |
| for _, v := range vSplit { |
| src := v.Source() |
| if !inNodes(gen, src) { |
| rmSet = append(rmSet, src) |
| } |
| } |
| } |
| } |
| |
| return rmSet |
| } |
| |
| func (t *trimSet) trimDecls(decls []ast.Decl, rm []ast.Node, m cue.Value, allow bool) []ast.Decl { |
| a := make([]ast.Decl, 0, len(decls)) |
| |
| for _, d := range decls { |
| if f, ok := d.(*ast.Field); ok { |
| label, _, err := ast.LabelName(f.Label) |
| v := m.Lookup(label) |
| inNodes := inNodes(rm, f.Value) |
| ok := allow || v.Exists() |
| if err == nil && inNodes && ok { |
| continue |
| } |
| } |
| a = append(a, d) |
| } |
| return a |
| } |
| |
| func inNodes(a []ast.Node, n ast.Node) bool { |
| for _, e := range a { |
| if e == n { |
| return true |
| } |
| } |
| return false |
| } |
| |
| type key struct { |
| label string |
| hidden bool |
| } |
| |
| func iterKey(v *cue.Iterator) key { |
| return key{v.Label(), v.IsHidden()} |
| } |