| // 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 fields that may be inferred from another mixed in value |
| // that "dominates" it. For instance, a value that is merged in from a |
| // definition is considered to dominate a value from a regular struct that |
| // mixes in this definition. Values derived from constraints and comprehensions |
| // can also dominate other fields. |
| // |
| // A value A is considered to be implied by a value B if A subsumes the default |
| // value of B. For instance, if a definition defines a field `a: *1 | int` and |
| // mixed in with a struct that defines a field `a: 1 | 2`, then the latter can |
| // be removed because a definition field dominates a regular field and because |
| // the latter subsumes the default value of the former. |
| // |
| // |
| // 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: |
| // |
| // // Unmodified: light: [string]: { ... } |
| // |
| // light: ceiling50: { |
| // room: "MasterBedroom" |
| // } |
| // |
| package trim |
| |
| import ( |
| "io" |
| "os" |
| |
| "cuelang.org/go/cue" |
| "cuelang.org/go/cue/ast" |
| "cuelang.org/go/cue/ast/astutil" |
| "cuelang.org/go/internal/core/adt" |
| "cuelang.org/go/internal/core/debug" |
| "cuelang.org/go/internal/core/subsume" |
| "cuelang.org/go/internal/value" |
| ) |
| |
| // 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 { |
| r, v := value.ToInternal(inst.Value()) |
| |
| t := &trimmer{ |
| Config: *cfg, |
| ctx: adt.NewContext(r, v), |
| remove: map[ast.Node]bool{}, |
| exclude: map[ast.Node]bool{}, |
| debug: Debug, |
| w: os.Stderr, |
| } |
| |
| d, _, _, pickedDefault := t.addDominators(nil, v, false) |
| t.findSubordinates(d, v, pickedDefault) |
| |
| // Remove subordinate values from files. |
| for _, f := range files { |
| astutil.Apply(f, func(c astutil.Cursor) bool { |
| if f, ok := c.Node().(*ast.Field); ok && t.remove[f.Value] && !t.exclude[f.Value] { |
| c.Delete() |
| } |
| return true |
| }, nil) |
| if err := astutil.Sanitize(f); err != nil { |
| return err |
| } |
| } |
| |
| return nil |
| } |
| |
| type trimmer struct { |
| Config |
| |
| ctx *adt.OpContext |
| remove map[ast.Node]bool |
| exclude map[ast.Node]bool |
| |
| debug bool |
| indent int |
| w io.Writer |
| } |
| |
| var Debug bool = false |
| |
| func (t *trimmer) markRemove(c adt.Conjunct) { |
| if src := c.Expr().Source(); src != nil { |
| t.remove[src] = true |
| if t.debug { |
| t.logf("removing %s", debug.NodeString(t.ctx, c.Expr(), nil)) |
| } |
| } |
| } |
| |
| func (t *trimmer) markKeep(c adt.Conjunct) { |
| if isDom, _ := isDominator(c); isDom { |
| return |
| } |
| if src := c.Expr().Source(); src != nil { |
| t.exclude[src] = true |
| if t.debug { |
| t.logf("keeping") |
| } |
| } |
| } |
| |
| const dominatorNode = adt.ComprehensionSpan | adt.DefinitionSpan | adt.ConstraintSpan |
| |
| // isDominator reports whether a node can remove other nodes. |
| func isDominator(c adt.Conjunct) (ok, mayRemove bool) { |
| if !c.CloseInfo.IsInOneOf(dominatorNode) { |
| return false, false |
| } |
| switch c.Field().(type) { |
| case *adt.OptionalField: // bulk constraints handled elsewhere. |
| return true, false |
| } |
| return true, true |
| } |
| |
| // Removable reports whether a non-dominator conjunct can be removed. This is |
| // not the case if it has pattern constraints that could turn into dominator |
| // nodes. |
| func removable(c adt.Conjunct, v *adt.Vertex) bool { |
| return c.CloseInfo.FieldTypes&(adt.HasAdditional|adt.HasPattern) == 0 |
| } |
| |
| // Roots of constraints are not allowed to strip conjuncts by |
| // themselves as it will eliminate the reason for the trigger. |
| func (t *trimmer) allowRemove(v *adt.Vertex) bool { |
| for _, c := range v.Conjuncts { |
| _, allowRemove := isDominator(c) |
| loc := c.CloseInfo.Location() != c.Expr() |
| isSpan := c.CloseInfo.RootSpanType() != adt.ConstraintSpan |
| if allowRemove && (loc || isSpan) { |
| return true |
| } |
| } |
| return false |
| } |
| |
| // A parent may be removed if there is not a `no` and there is at least one |
| // `yes`. A `yes` is proves that there is at least one node that is not a |
| // dominator node and that we are not removing nodes from a declaration of a |
| // dominator itself. |
| const ( |
| no = 1 << iota |
| maybe |
| yes |
| ) |
| |
| // addDominators injects dominator values from v into d. If no default has |
| // been selected from dominators so far, the values are erased. Otherwise, |
| // both default and new values are merged. |
| // |
| // Erasing the previous values when there has been no default so far allows |
| // interpolations, for instance, to be evaluated in the new context and |
| // eliminated. |
| // |
| // Values are kept when there has been a default (current or ancestor) because |
| // the current value may contain information that caused that default to be |
| // selected and thus erasing it would cause that information to be lost. |
| // |
| // TODO: |
| // In principle, information only needs to be kept for discriminator values, or |
| // any value that was instrumental in selecting the default. This is currently |
| // hard to do, however, so we just fall back to a stricter mode in the presence |
| // of defaults. |
| func (t *trimmer) addDominators(d, v *adt.Vertex, hasDisjunction bool) (doms *adt.Vertex, ambiguous, hasSubs, strict bool) { |
| strict = hasDisjunction |
| doms = &adt.Vertex{} |
| if d != nil && hasDisjunction { |
| doms.Conjuncts = append(doms.Conjuncts, d.Conjuncts...) |
| } |
| |
| hasDoms := false |
| for _, c := range v.Conjuncts { |
| isDom, _ := isDominator(c) |
| switch { |
| case isDom: |
| doms.AddConjunct(c) |
| default: |
| if r, ok := c.Expr().(adt.Resolver); ok { |
| x, _ := t.ctx.Resolve(c.Env, r) |
| // Even if this is not a dominator now, descendants will be. |
| if x.Label.IsDef() { |
| for _, c := range x.Conjuncts { |
| doms.AddConjunct(c) |
| } |
| break |
| } |
| } |
| hasSubs = true |
| } |
| } |
| doms.Finalize(t.ctx) |
| |
| switch x := doms.Value().(type) { |
| case *adt.Disjunction: |
| switch x.NumDefaults { |
| case 1: |
| strict = true |
| default: |
| ambiguous = true |
| } |
| } |
| |
| if doms = doms.Default(); doms.IsErr() { |
| ambiguous = true |
| } |
| |
| _ = hasDoms |
| return doms, hasSubs, ambiguous, strict || ambiguous |
| } |
| |
| func (t *trimmer) findSubordinates(doms, v *adt.Vertex, hasDisjunction bool) (result int) { |
| defer un(t.trace(v)) |
| defer func() { |
| if result == no { |
| for _, c := range v.Conjuncts { |
| t.markKeep(c) |
| } |
| } |
| }() |
| |
| doms, hasSubs, ambiguous, pickedDefault := t.addDominators(doms, v, hasDisjunction) |
| |
| if ambiguous { |
| return no |
| } |
| |
| // TODO(structure sharing): do not descend into vertices whose parent is not |
| // equal to the parent. This is not relevant at this time, but may be so in |
| // the future. |
| |
| if len(v.Arcs) > 0 { |
| var match int |
| for _, a := range v.Arcs { |
| d := doms.Lookup(a.Label) |
| match |= t.findSubordinates(d, a, pickedDefault) |
| } |
| |
| // This also skips embedded scalars if not all fields are removed. In |
| // this case we need to preserve the scalar to keep the type of the |
| // struct intact, which might as well be done by not removing the scalar |
| // type. |
| if match&yes == 0 || match&no != 0 { |
| return match |
| } |
| } |
| |
| if !t.allowRemove(v) { |
| return no |
| } |
| |
| switch v.BaseValue.(type) { |
| case *adt.StructMarker, *adt.ListMarker: |
| // Rely on previous processing of the Arcs and the fact that we take the |
| // default value to check dominator subsumption, meaning that we don't |
| // have to check additional optional constraints to pass subsumption. |
| |
| default: |
| if !hasSubs { |
| return maybe |
| } |
| |
| // This should normally not be necessary, as subsume should catch this. |
| // But as we already take the default value for doms, it doesn't hurt to |
| // do it. |
| v = v.Default() |
| |
| // This is not necessary, but seems like it may result in more |
| // user-friendly semantics. |
| if v.IsErr() { |
| return no |
| } |
| |
| // TODO: since we take v, instead of the unification of subordinate |
| // values, it should suffice to take equality here: |
| // doms ⊑ subs ==> doms == subs&doms |
| if err := subsume.Value(t.ctx, v, doms); err != nil { |
| return no |
| } |
| } |
| |
| for _, c := range v.Conjuncts { |
| _, allowRemove := isDominator(c) |
| if !allowRemove && removable(c, v) { |
| t.markRemove(c) |
| } |
| } |
| |
| return yes |
| } |