simplify.go

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

     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 adt
    16  
    17  import (
    18  	"github.com/cockroachdb/apd/v3"
    19  
    20  	"cuelang.org/go/internal"
    21  )
    22  
    23  // SimplifyBounds collapses bounds if possible. The bound values must be
    24  // concrete. It returns nil if the bound values cannot be collapsed.
    25  //
    26  // k represents additional type constraints, such as `int`.
    27  func SimplifyBounds(ctx *OpContext, k Kind, x, y *BoundValue) Value {
    28  	xv := x.Value
    29  	yv := y.Value
    30  
    31  	cmp, xCat := opInfo(x.Op)
    32  	_, yCat := opInfo(y.Op)
    33  
    34  	// k := x.Kind() & y.Kind()
    35  
    36  	switch {
    37  	case xCat == yCat:
    38  		switch x.Op {
    39  		// NOTE: EqualOp should not happen, but include it defensively.
    40  		// Maybe an API would use it, for instance.
    41  		case EqualOp, NotEqualOp, MatchOp, NotMatchOp:
    42  			if test(ctx, EqualOp, xv, yv) {
    43  				return x
    44  			}
    45  			return nil // keep both bounds
    46  		}
    47  
    48  		// xCat == yCat && x.Op != NotEqualOp
    49  		// > a & >= b
    50  		//    > a   if a >= b
    51  		//    >= b  if a <  b
    52  		// > a & > b
    53  		//    > a   if a >= b
    54  		//    > b   if a <  b
    55  		// >= a & > b
    56  		//    >= a   if a > b
    57  		//    > b    if a <= b
    58  		// >= a & >= b
    59  		//    >= a   if a > b
    60  		//    >= b   if a <= b
    61  		// inverse is true as well.
    62  
    63  		// Tighten bound.
    64  		if test(ctx, cmp, xv, yv) {
    65  			return x
    66  		}
    67  		return y
    68  
    69  	case xCat == -yCat:
    70  		if xCat == -1 {
    71  			x, y = y, x
    72  		}
    73  		a, aOK := xv.(*Num)
    74  		b, bOK := yv.(*Num)
    75  
    76  		if !aOK || !bOK {
    77  			break
    78  		}
    79  
    80  		var d, lo, hi apd.Decimal
    81  		lo.Set(&a.X)
    82  		hi.Set(&b.X)
    83  		if k&FloatKind == 0 {
    84  			// Readjust bounds for integers.
    85  			if x.Op == GreaterEqualOp {
    86  				// >=3.4  ==>  >=4
    87  				_, _ = internal.BaseContext.Ceil(&lo, &a.X)
    88  			} else {
    89  				// >3.4  ==>  >3
    90  				_, _ = internal.BaseContext.Floor(&lo, &a.X)
    91  			}
    92  			if y.Op == LessEqualOp {
    93  				// <=2.3  ==>  <= 2
    94  				_, _ = internal.BaseContext.Floor(&hi, &b.X)
    95  			} else {
    96  				// <2.3   ==>  < 3
    97  				_, _ = internal.BaseContext.Ceil(&hi, &b.X)
    98  			}
    99  		}
   100  
   101  		cond, err := internal.BaseContext.Sub(&d, &hi, &lo)
   102  		if cond.Inexact() || err != nil {
   103  			break
   104  		}
   105  
   106  		// attempt simplification
   107  		// numbers
   108  		// >=a & <=b
   109  		//     a   if a == b
   110  		//     _|_ if a < b
   111  		// >=a & <b
   112  		//     _|_ if b <= a
   113  		// >a  & <=b
   114  		//     _|_ if b <= a
   115  		// >a  & <b
   116  		//     _|_ if b <= a
   117  
   118  		// integers
   119  		// >=a & <=b
   120  		//     a   if b-a == 0
   121  		//     _|_ if a < b
   122  		// >=a & <b
   123  		//     a   if b-a == 1
   124  		//     _|_ if b <= a
   125  		// >a  & <=b
   126  		//     b   if b-a == 1
   127  		//     _|_ if b <= a
   128  		// >a  & <b
   129  		//     a+1 if b-a == 2
   130  		//     _|_ if b <= a
   131  
   132  		switch diff, err := d.Int64(); {
   133  		case diff == 1:
   134  			if k&FloatKind == 0 {
   135  				if x.Op == GreaterEqualOp && y.Op == LessThanOp {
   136  					return ctx.newNum(&lo, k&NumKind, x, y)
   137  				}
   138  				if x.Op == GreaterThanOp && y.Op == LessEqualOp {
   139  					return ctx.newNum(&hi, k&NumKind, x, y)
   140  				}
   141  			}
   142  
   143  		case diff == 2:
   144  			if k&FloatKind == 0 && x.Op == GreaterThanOp && y.Op == LessThanOp {
   145  				_, _ = internal.BaseContext.Add(&d, d.SetInt64(1), &lo)
   146  				return ctx.newNum(&d, k&NumKind, x, y)
   147  
   148  			}
   149  
   150  		case diff == 0 && err == nil:
   151  			if x.Op == GreaterEqualOp && y.Op == LessEqualOp {
   152  				return ctx.newNum(&lo, k&NumKind, x, y)
   153  			}
   154  			fallthrough
   155  
   156  		case d.Negative:
   157  			return ctx.NewErrf("incompatible bounds %v and %v", x, y)
   158  		}
   159  
   160  	case x.Op == NotEqualOp:
   161  		if !test(ctx, y.Op, xv, yv) {
   162  			return y
   163  		}
   164  
   165  	case y.Op == NotEqualOp:
   166  		if !test(ctx, x.Op, yv, xv) {
   167  			return x
   168  		}
   169  	}
   170  	return nil
   171  }
   172  
   173  func opInfo(op Op) (cmp Op, norm int) {
   174  	switch op {
   175  	case GreaterThanOp:
   176  		return GreaterEqualOp, 1
   177  	case GreaterEqualOp:
   178  		return GreaterThanOp, 1
   179  	case LessThanOp:
   180  		return LessEqualOp, -1
   181  	case LessEqualOp:
   182  		return LessThanOp, -1
   183  	case NotEqualOp:
   184  		return NotEqualOp, 0
   185  	case MatchOp:
   186  		return MatchOp, 2
   187  	case NotMatchOp:
   188  		return NotMatchOp, 3
   189  	}
   190  	panic("cue: unreachable")
   191  }
   192  
   193  func test(ctx *OpContext, op Op, a, b Value) bool {
   194  	if b, ok := BinOp(ctx, op, a, b).(*Bool); ok {
   195  		return b.B
   196  	}
   197  	return false
   198  }
   199  
   200  // SimplifyValidator simplifies non-bound validators.
   201  //
   202  // Currently this only checks for pure equality. In the future this can be used
   203  // to simplify certain builtin validators analogously to how we simplify bounds
   204  // now.
   205  func SimplifyValidator(ctx *OpContext, v, w Validator) Validator {
   206  	switch x := v.(type) {
   207  	case *BuiltinValidator:
   208  		switch y := w.(type) {
   209  		case *BuiltinValidator:
   210  			if x == y {
   211  				return x
   212  			}
   213  			if x.Builtin != y.Builtin || len(x.Args) != len(y.Args) {
   214  				return nil
   215  			}
   216  			for i, a := range x.Args {
   217  				if !Equal(ctx, a, y.Args[i], CheckStructural) {
   218  					return nil
   219  				}
   220  			}
   221  			return x
   222  		}
   223  	}
   224  	return nil
   225  }
   226
View as plain text