value.go

Documentation: cuelang.org/go/internal/core/subsume

     1  // Copyright 2020 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 subsume
    16  
    17  import (
    18  	"bytes"
    19  
    20  	"cuelang.org/go/cue/errors"
    21  	"cuelang.org/go/internal/core/adt"
    22  )
    23  
    24  func (s *subsumer) values(a, b adt.Value) (result bool) {
    25  	defer func() {
    26  		if !result && s.gt == nil && s.lt == nil {
    27  			s.gt = a
    28  			s.lt = b
    29  		}
    30  	}()
    31  
    32  	if a == b {
    33  		return true
    34  	}
    35  
    36  	if s.Defaults {
    37  		b = adt.Default(b)
    38  	}
    39  
    40  	switch b := b.(type) {
    41  	case *adt.Bottom:
    42  		// If the value is incomplete, the error is not final. So either check
    43  		// structural equivalence or return an error.
    44  		return !b.IsIncomplete()
    45  
    46  	case *adt.Vertex:
    47  		if a, ok := a.(*adt.Vertex); ok {
    48  			return s.vertices(a, b)
    49  		}
    50  		if v, ok := b.BaseValue.(adt.Value); ok {
    51  			// Safe to ignore arcs of w.
    52  			return s.values(a, v)
    53  		}
    54  		// Check based on first value.
    55  
    56  	case *adt.Conjunction:
    57  		if _, ok := a.(*adt.Conjunction); ok {
    58  			break
    59  		}
    60  		for _, y := range b.Values {
    61  			if s.values(a, y) {
    62  				return true
    63  			}
    64  		}
    65  		return false
    66  
    67  	case *adt.Disjunction:
    68  		if _, ok := a.(*adt.Disjunction); ok {
    69  			break
    70  		}
    71  
    72  		for _, y := range b.Values {
    73  			if !s.values(a, y) {
    74  				return false
    75  			}
    76  		}
    77  		return true
    78  
    79  	case *adt.NodeLink:
    80  		// Do not descend into NodeLinks to avoid processing cycles.
    81  		// TODO: this would work better if all equal nodes shared the same
    82  		// node link.
    83  		return deref(a) == deref(b)
    84  	}
    85  
    86  	switch x := a.(type) {
    87  	case *adt.Top:
    88  		return true
    89  
    90  	case *adt.Bottom:
    91  		// isBottom(b) was already tested above.
    92  		return false
    93  
    94  	case *adt.BasicType:
    95  		k := b.Kind()
    96  		return x.K&k == k
    97  
    98  	case *adt.BoundValue:
    99  		return s.bound(x, b)
   100  
   101  	case *adt.Builtin:
   102  		return x == b
   103  
   104  	case *adt.BuiltinValidator:
   105  		if y := s.ctx.Validate(x, b); y != nil {
   106  			s.errs = errors.Append(s.errs, y.Err)
   107  			return false
   108  		}
   109  		return true
   110  
   111  	case *adt.Null:
   112  		return b.Kind() == adt.NullKind
   113  
   114  	case *adt.Bool:
   115  		y, ok := b.(*adt.Bool)
   116  		return ok && x.B == y.B
   117  
   118  	case *adt.Num:
   119  		y, ok := b.(*adt.Num)
   120  		return ok && x.K&y.K == y.K && test(s.ctx, x, adt.EqualOp, x, y)
   121  
   122  	case *adt.String:
   123  		y, ok := b.(*adt.String)
   124  		return ok && x.Str == y.Str
   125  
   126  	case *adt.Bytes:
   127  		y, ok := b.(*adt.Bytes)
   128  		return ok && bytes.Equal(x.B, y.B)
   129  
   130  	case *adt.Vertex:
   131  		y, ok := b.(*adt.Vertex)
   132  		if ok {
   133  			return s.vertices(x, y)
   134  		}
   135  
   136  		// TODO: Under what conditions can we cast to the value?
   137  		if v, _ := x.BaseValue.(adt.Value); v != nil {
   138  			return s.values(v, b)
   139  		}
   140  		return false
   141  
   142  	case *adt.Conjunction:
   143  		if y, ok := b.(*adt.Conjunction); ok {
   144  			// A Conjunction subsumes another Conjunction if for all values a in
   145  			// x there is a value b in y such that a subsumes b.
   146  			//
   147  			// This assumes overlapping ranges in disjunctions are merged.If
   148  			// this is not the case, subsumes will return a false negative,
   149  			// which is allowed.
   150  		outerC:
   151  			for _, a := range x.Values {
   152  				for _, b := range y.Values {
   153  					if s.values(a, b) {
   154  						continue outerC
   155  					}
   156  				}
   157  				// TODO: should this be marked as inexact?
   158  				return false
   159  			}
   160  			return true
   161  		}
   162  		subsumed := true
   163  		for _, a := range x.Values {
   164  			subsumed = subsumed && s.values(a, b)
   165  		}
   166  		return subsumed
   167  
   168  	case *adt.Disjunction:
   169  
   170  		if s.LeftDefault {
   171  			a = adt.Default(a)
   172  			var ok bool
   173  			x, ok = a.(*adt.Disjunction)
   174  			if !ok {
   175  				return s.values(a, b)
   176  			}
   177  		}
   178  
   179  		// A Disjunction subsumes another Disjunction if all values of y are
   180  		// subsumed by any of the values of x, and default values in y are
   181  		// subsumed by the default values of x.
   182  		//
   183  		// This assumes that overlapping ranges in x are merged. If this is not
   184  		// the case, subsumes will return a false negative, which is allowed.
   185  		if y, ok := b.(*adt.Disjunction); ok {
   186  			// at least one value in x should subsume each value in d.
   187  		outerD:
   188  			for i, b := range y.Values {
   189  				bDefault := i < y.NumDefaults
   190  				// v is subsumed if any value in x subsumes v.
   191  				for j, a := range x.Values {
   192  					aDefault := j < x.NumDefaults
   193  					if (aDefault || !bDefault) && s.values(a, b) {
   194  						continue outerD
   195  					}
   196  				}
   197  				return false
   198  			}
   199  			return true
   200  		}
   201  		// b is subsumed if any value in x subsumes b.
   202  		for _, a := range x.Values {
   203  			if s.values(a, b) {
   204  				return true
   205  			}
   206  		}
   207  		// TODO: should this be marked as inexact?
   208  		return false
   209  
   210  	case *adt.NodeLink:
   211  		return deref(x) == deref(b)
   212  	}
   213  	return false
   214  }
   215  
   216  func deref(v adt.Expr) *adt.Vertex {
   217  	switch x := v.(type) {
   218  	case *adt.Vertex:
   219  		return x
   220  	case *adt.NodeLink:
   221  		return x.Node
   222  	}
   223  	return nil
   224  }
   225  
   226  func (s *subsumer) bound(x *adt.BoundValue, v adt.Value) bool {
   227  	ctx := s.ctx
   228  	if isBottom(v) {
   229  		return true
   230  	}
   231  
   232  	switch y := v.(type) {
   233  	case *adt.BoundValue:
   234  		if !adt.IsConcrete(y.Value) {
   235  			return false
   236  		}
   237  
   238  		kx := x.Kind()
   239  		ky := y.Kind()
   240  		if (kx&ky)&^kx != 0 {
   241  			return false
   242  		}
   243  		// x subsumes y if
   244  		// x: >= a, y: >= b ==> a <= b
   245  		// x: >= a, y: >  b ==> a <= b
   246  		// x: >  a, y: >  b ==> a <= b
   247  		// x: >  a, y: >= b ==> a < b
   248  		//
   249  		// x: <= a, y: <= b ==> a >= b
   250  		//
   251  		// x: != a, y: != b ==> a != b
   252  		//
   253  		// false if types or op direction doesn't match
   254  
   255  		xv := x.Value
   256  		yv := y.Value
   257  		switch x.Op {
   258  		case adt.GreaterThanOp:
   259  			if y.Op == adt.GreaterEqualOp {
   260  				return test(ctx, x, adt.LessThanOp, xv, yv)
   261  			}
   262  			fallthrough
   263  		case adt.GreaterEqualOp:
   264  			if y.Op == adt.GreaterThanOp || y.Op == adt.GreaterEqualOp {
   265  				return test(ctx, x, adt.LessEqualOp, xv, yv)
   266  			}
   267  		case adt.LessThanOp:
   268  			if y.Op == adt.LessEqualOp {
   269  				return test(ctx, x, adt.GreaterThanOp, xv, yv)
   270  			}
   271  			fallthrough
   272  		case adt.LessEqualOp:
   273  			if y.Op == adt.LessThanOp || y.Op == adt.LessEqualOp {
   274  				return test(ctx, x, adt.GreaterEqualOp, xv, yv)
   275  			}
   276  		case adt.NotEqualOp:
   277  			switch y.Op {
   278  			case adt.NotEqualOp:
   279  				return test(ctx, x, adt.EqualOp, xv, yv)
   280  			case adt.GreaterEqualOp:
   281  				return test(ctx, x, adt.LessThanOp, xv, yv)
   282  			case adt.GreaterThanOp:
   283  				return test(ctx, x, adt.LessEqualOp, xv, yv)
   284  			case adt.LessThanOp:
   285  				return test(ctx, x, adt.GreaterEqualOp, xv, yv)
   286  			case adt.LessEqualOp:
   287  				return test(ctx, x, adt.GreaterThanOp, xv, yv)
   288  			}
   289  
   290  		case adt.MatchOp, adt.NotMatchOp:
   291  			// these are just approximations
   292  			if y.Op == x.Op {
   293  				return test(ctx, x, adt.EqualOp, xv, yv)
   294  			}
   295  
   296  		default:
   297  			// adt.NotEqualOp already handled above.
   298  			panic("cue: undefined bound mode")
   299  		}
   300  
   301  	case *adt.Num, *adt.String, *adt.Bool:
   302  		return test(ctx, x, x.Op, y, x.Value)
   303  	}
   304  	return false
   305  }
   306  
   307  func test(ctx *adt.OpContext, src adt.Node, op adt.Op, gt, lt adt.Value) bool {
   308  	x := adt.BinOp(ctx, op, gt, lt)
   309  	b, ok := x.(*adt.Bool)
   310  	return ok && b.B
   311  }
   312
View as plain text