trim.go

Documentation: cuelang.org/go/tools/trim

     1  // Copyright 2018 The CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  // Package trim removes fields that may be inferred from another mixed in value
    16  // that "dominates" it. For instance, a value that is merged in from a
    17  // definition is considered to dominate a value from a regular struct that
    18  // mixes in this definition. Values derived from constraints and comprehensions
    19  // can also dominate other fields.
    20  //
    21  // A value A is considered to be implied by a value B if A subsumes the default
    22  // value of B. For instance, if a definition defines a field `a: *1 | int` and
    23  // mixed in with a struct that defines a field `a: 1 | 2`, then the latter can
    24  // be removed because a definition field dominates a regular field and because
    25  // the latter subsumes the default value of the former.
    26  //
    27  // Examples:
    28  //
    29  //	light: [string]: {
    30  //		room:          string
    31  //		brightnessOff: *0.0 | >=0 & <=100.0
    32  //		brightnessOn:  *100.0 | >=0 & <=100.0
    33  //	}
    34  //
    35  //	light: ceiling50: {
    36  //		room:          "MasterBedroom"
    37  //		brightnessOff: 0.0    // this line
    38  //		brightnessOn:  100.0  // and this line will be removed
    39  //	}
    40  //
    41  // Results in:
    42  //
    43  //	// Unmodified: light: [string]: { ... }
    44  //
    45  //	light: ceiling50: {
    46  //		room: "MasterBedroom"
    47  //	}
    48  package trim
    49  
    50  import (
    51  	"io"
    52  	"os"
    53  
    54  	"cuelang.org/go/cue"
    55  	"cuelang.org/go/cue/ast"
    56  	"cuelang.org/go/cue/ast/astutil"
    57  	"cuelang.org/go/internal/core/adt"
    58  	"cuelang.org/go/internal/core/debug"
    59  	"cuelang.org/go/internal/core/subsume"
    60  	"cuelang.org/go/internal/core/walk"
    61  	"cuelang.org/go/internal/value"
    62  )
    63  
    64  // Config configures trim options.
    65  type Config struct {
    66  	Trace bool
    67  }
    68  
    69  // Files trims fields in the given files that can be implied from other fields,
    70  // as can be derived from the evaluated values in inst.
    71  // Trimming is done on a best-effort basis and only when the removed field
    72  // is clearly implied by another field, rather than equal sibling fields.
    73  func Files(files []*ast.File, inst cue.InstanceOrValue, cfg *Config) error {
    74  	r, v := value.ToInternal(inst.Value())
    75  
    76  	t := &trimmer{
    77  		Config:  *cfg,
    78  		ctx:     adt.NewContext(r, v),
    79  		remove:  map[ast.Node]bool{},
    80  		exclude: map[ast.Node]bool{},
    81  		debug:   Debug,
    82  		w:       os.Stderr,
    83  	}
    84  
    85  	// Mark certain expressions as off limits.
    86  	// TODO: We could alternatively ensure that comprehensions unconditionally
    87  	// resolve.
    88  	visitor := &walk.Visitor{
    89  		Before: func(n adt.Node) bool {
    90  			switch x := n.(type) {
    91  			case *adt.StructLit:
    92  				// Structs with comprehensions may never be removed.
    93  				for _, d := range x.Decls {
    94  					switch d.(type) {
    95  					case *adt.Comprehension:
    96  						t.markKeep(x)
    97  					}
    98  				}
    99  			}
   100  			return true
   101  		},
   102  	}
   103  	for _, c := range v.Conjuncts {
   104  		visitor.Elem(c.Elem())
   105  	}
   106  
   107  	d, _, _, pickedDefault := t.addDominators(nil, v, false)
   108  	t.findSubordinates(d, v, pickedDefault)
   109  
   110  	// Remove subordinate values from files.
   111  	for _, f := range files {
   112  		astutil.Apply(f, func(c astutil.Cursor) bool {
   113  			if f, ok := c.Node().(*ast.Field); ok && t.remove[f.Value] && !t.exclude[f.Value] {
   114  				c.Delete()
   115  			}
   116  			return true
   117  		}, nil)
   118  		if err := astutil.Sanitize(f); err != nil {
   119  			return err
   120  		}
   121  	}
   122  
   123  	return nil
   124  }
   125  
   126  type trimmer struct {
   127  	Config
   128  
   129  	ctx     *adt.OpContext
   130  	remove  map[ast.Node]bool
   131  	exclude map[ast.Node]bool
   132  
   133  	debug  bool
   134  	indent int
   135  	w      io.Writer
   136  }
   137  
   138  var Debug bool = false
   139  
   140  func (t *trimmer) markRemove(c adt.Conjunct) {
   141  	if src := c.Elem().Source(); src != nil {
   142  		t.remove[src] = true
   143  		if t.debug {
   144  			t.logf("removing %s", debug.NodeString(t.ctx, c.Elem(), nil))
   145  		}
   146  	}
   147  }
   148  
   149  func (t *trimmer) markKeep(x adt.Expr) {
   150  	if src := x.Source(); src != nil {
   151  		t.exclude[src] = true
   152  		if t.debug {
   153  			t.logf("keeping")
   154  		}
   155  	}
   156  }
   157  
   158  const dominatorNode = adt.ComprehensionSpan | adt.DefinitionSpan | adt.ConstraintSpan
   159  
   160  // isDominator reports whether a node can remove other nodes.
   161  func isDominator(c adt.Conjunct) (ok, mayRemove bool) {
   162  	if !c.CloseInfo.IsInOneOf(dominatorNode) {
   163  		return false, false
   164  	}
   165  	switch f := c.Field().(type) {
   166  	case *adt.Field: // bulk constraints handled elsewhere.
   167  		return true, f.ArcType == adt.ArcMember
   168  	}
   169  	return true, true
   170  }
   171  
   172  // Removable reports whether a non-dominator conjunct can be removed. This is
   173  // not the case if it has pattern constraints that could turn into dominator
   174  // nodes.
   175  func removable(c adt.Conjunct, v *adt.Vertex) bool {
   176  	return c.CloseInfo.FieldTypes&(adt.HasAdditional|adt.HasPattern) == 0
   177  }
   178  
   179  // Roots of constraints are not allowed to strip conjuncts by
   180  // themselves as it will eliminate the reason for the trigger.
   181  func (t *trimmer) allowRemove(v *adt.Vertex) bool {
   182  	for _, c := range v.Conjuncts {
   183  		_, allowRemove := isDominator(c)
   184  		loc := c.CloseInfo.Location() != c.Elem()
   185  		isSpan := c.CloseInfo.RootSpanType() != adt.ConstraintSpan
   186  		if allowRemove && (loc || isSpan) {
   187  			return true
   188  		}
   189  	}
   190  	return false
   191  }
   192  
   193  // A parent may be removed if there is not a `no` and there is at least one
   194  // `yes`. A `yes` is proves that there is at least one node that is not a
   195  // dominator node and that we are not removing nodes from a declaration of a
   196  // dominator itself.
   197  const (
   198  	no = 1 << iota
   199  	maybe
   200  	yes
   201  )
   202  
   203  // addDominators injects dominator values from v into d. If no default has
   204  // been selected from dominators so far, the values are erased. Otherwise,
   205  // both default and new values are merged.
   206  //
   207  // Erasing the previous values when there has been no default so far allows
   208  // interpolations, for instance, to be evaluated in the new context and
   209  // eliminated.
   210  //
   211  // Values are kept when there has been a default (current or ancestor) because
   212  // the current value may contain information that caused that default to be
   213  // selected and thus erasing it would cause that information to be lost.
   214  //
   215  // TODO:
   216  // In principle, information only needs to be kept for discriminator values, or
   217  // any value that was instrumental in selecting the default. This is currently
   218  // hard to do, however, so we just fall back to a stricter mode in the presence
   219  // of defaults.
   220  func (t *trimmer) addDominators(d, v *adt.Vertex, hasDisjunction bool) (doms *adt.Vertex, ambiguous, hasSubs, strict bool) {
   221  	strict = hasDisjunction
   222  	doms = &adt.Vertex{
   223  		Parent: v.Parent,
   224  		Label:  v.Label,
   225  	}
   226  	if d != nil && hasDisjunction {
   227  		doms.Conjuncts = append(doms.Conjuncts, d.Conjuncts...)
   228  	}
   229  
   230  	hasDoms := false
   231  	for _, c := range v.Conjuncts {
   232  		isDom, _ := isDominator(c)
   233  		switch {
   234  		case isDom:
   235  			doms.AddConjunct(c)
   236  		default:
   237  			if r, ok := c.Elem().(adt.Resolver); ok {
   238  				x, _ := t.ctx.Resolve(c, r)
   239  				// Even if this is not a dominator now, descendants will be.
   240  				if x != nil && x.Label.IsDef() {
   241  					for _, c := range x.Conjuncts {
   242  						doms.AddConjunct(c)
   243  					}
   244  					break
   245  				}
   246  			}
   247  			hasSubs = true
   248  		}
   249  	}
   250  	doms.Finalize(t.ctx)
   251  
   252  	switch x := doms.Value().(type) {
   253  	case *adt.Disjunction:
   254  		switch x.NumDefaults {
   255  		case 1:
   256  			strict = true
   257  		default:
   258  			ambiguous = true
   259  		}
   260  	}
   261  
   262  	if doms = doms.Default(); doms.IsErr() {
   263  		ambiguous = true
   264  	}
   265  
   266  	_ = hasDoms
   267  	return doms, hasSubs, ambiguous, strict || ambiguous
   268  }
   269  
   270  func (t *trimmer) findSubordinates(doms, v *adt.Vertex, hasDisjunction bool) (result int) {
   271  	defer un(t.trace(v))
   272  	defer func() {
   273  		if result == no {
   274  			for _, c := range v.Conjuncts {
   275  				t.markKeep(c.Expr())
   276  			}
   277  		}
   278  	}()
   279  
   280  	doms, hasSubs, ambiguous, pickedDefault := t.addDominators(doms, v, hasDisjunction)
   281  
   282  	if ambiguous {
   283  		return no
   284  	}
   285  
   286  	// TODO(structure sharing): do not descend into vertices whose parent is not
   287  	// equal to the parent. This is not relevant at this time, but may be so in
   288  	// the future.
   289  
   290  	if len(v.Arcs) > 0 {
   291  		var match int
   292  		for _, a := range v.Arcs {
   293  			d := doms.Lookup(a.Label)
   294  			match |= t.findSubordinates(d, a, pickedDefault)
   295  		}
   296  
   297  		// This also skips embedded scalars if not all fields are removed. In
   298  		// this case we need to preserve the scalar to keep the type of the
   299  		// struct intact, which might as well be done by not removing the scalar
   300  		// type.
   301  		if match&yes == 0 || match&no != 0 {
   302  			return match
   303  		}
   304  	}
   305  
   306  	if !t.allowRemove(v) {
   307  		return no
   308  	}
   309  
   310  	switch v.BaseValue.(type) {
   311  	case *adt.StructMarker, *adt.ListMarker:
   312  		// Rely on previous processing of the Arcs and the fact that we take the
   313  		// default value to check dominator subsumption, meaning that we don't
   314  		// have to check additional optional constraints to pass subsumption.
   315  
   316  	default:
   317  		if !hasSubs {
   318  			return maybe
   319  		}
   320  
   321  		// This should normally not be necessary, as subsume should catch this.
   322  		// But as we already take the default value for doms, it doesn't hurt to
   323  		// do it.
   324  		v = v.Default()
   325  
   326  		// This is not necessary, but seems like it may result in more
   327  		// user-friendly semantics.
   328  		if v.IsErr() {
   329  			return no
   330  		}
   331  
   332  		// TODO: since we take v, instead of the unification of subordinate
   333  		// values, it should suffice to take equality here:
   334  		//    doms ⊑ subs  ==> doms == subs&doms
   335  		if err := subsume.Value(t.ctx, v, doms); err != nil {
   336  			return no
   337  		}
   338  	}
   339  
   340  	for _, c := range v.Conjuncts {
   341  		_, allowRemove := isDominator(c)
   342  		if !allowRemove && removable(c, v) {
   343  			t.markRemove(c)
   344  		}
   345  	}
   346  
   347  	return yes
   348  }
   349
View as plain text