constraints.go

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

     1  // Copyright 2023 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  // This file contains functionality for pattern constraints.
    18  
    19  // Constraints keeps track of pattern constraints and the set of allowed
    20  // fields.
    21  type Constraints struct {
    22  	// Pairs lists Pattern-Constraint pairs.
    23  	Pairs []PatternConstraint // TODO(perf): move to Arcs?
    24  
    25  	// Allowed is a Value that defines the set of all allowed fields.
    26  	// To check if a field is allowed, its correpsonding CUE value can be
    27  	// unified with this value.
    28  	Allowed Value
    29  }
    30  
    31  // A PatternConstraint represents a single
    32  //
    33  //	[pattern]: T.
    34  //
    35  // The Vertex holds a list of conjuncts to represent the constraints. We use
    36  // a Vertex so that these can be evaluated and compared for equality.
    37  // Unlike for regular Vertex values, CloseInfo.closeContext is set for
    38  // constraints: it is needed when matching subfields to ensure that conjuncts
    39  // get inserted into the proper groups.
    40  type PatternConstraint struct {
    41  	Pattern    Value
    42  	Constraint *Vertex
    43  }
    44  
    45  // insertListEllipsis inserts the given list ellipsis as a pattern constraint on
    46  // n, applying it to all elements at indexes >= offset.
    47  func (n *nodeContext) insertListEllipsis(offset int, ellipsis Conjunct) {
    48  	ctx := n.ctx
    49  
    50  	var p Value
    51  	if offset == 0 {
    52  		p = &BasicType{
    53  			Src: ellipsis.Field().Source(),
    54  			K:   IntKind,
    55  		}
    56  	} else {
    57  		p = &BoundValue{
    58  			Src:   nil, // TODO: field source.
    59  			Op:    GreaterEqualOp,
    60  			Value: ctx.NewInt64(int64(offset)),
    61  		}
    62  	}
    63  	n.insertConstraint(p, ellipsis)
    64  }
    65  
    66  // insertConstraint ensures a given pattern constraint is present in the
    67  // constraints of n and reports whether the pair was added newly.
    68  //
    69  // The given conjunct must have a closeContext associated with it. This ensures
    70  // that different pattern constraints pairs originating from the same
    71  // closeContext will be collated properly in fields to which these constraints
    72  // are applied.
    73  func (n *nodeContext) insertConstraint(pattern Value, c Conjunct) bool {
    74  	if c.CloseInfo.cc == nil {
    75  		panic("constraint conjunct must have closeContext associated with it")
    76  	}
    77  
    78  	ctx := n.ctx
    79  	v := n.node
    80  
    81  	pcs := v.PatternConstraints
    82  	if pcs == nil {
    83  		pcs = &Constraints{}
    84  		v.PatternConstraints = pcs
    85  	}
    86  
    87  	var constraint *Vertex
    88  	for _, pc := range pcs.Pairs {
    89  		if Equal(ctx, pc.Pattern, pattern, 0) {
    90  			constraint = pc.Constraint
    91  			break
    92  		}
    93  	}
    94  
    95  	if constraint == nil {
    96  		constraint = &Vertex{}
    97  		pcs.Pairs = append(pcs.Pairs, PatternConstraint{
    98  			Pattern:    pattern,
    99  			Constraint: constraint,
   100  		})
   101  	} else if constraint.hasConjunct(c) {
   102  		// The constraint already existed and the conjunct was already added.
   103  		return false
   104  	}
   105  
   106  	constraint.addConjunctUnchecked(c)
   107  	return true
   108  }
   109  
   110  // matchPattern reports whether f matches pattern. The result reflects
   111  // whether unification of pattern with f converted to a CUE value succeeds.
   112  func matchPattern(ctx *OpContext, pattern Value, f Feature) bool {
   113  	if pattern == nil || !f.IsRegular() {
   114  		return false
   115  	}
   116  
   117  	// TODO(perf): this assumes that comparing an int64 against apd.Decimal
   118  	// is faster than converting this to a Num and using that for comparison.
   119  	// This may very well not be the case. But it definitely will be if we
   120  	// special-case integers that can fit in an int64 (or int32 if we want to
   121  	// avoid many bound checks), which we probably should. Especially when we
   122  	// allow list constraints, like [<10]: T.
   123  	var label Value
   124  	if int64(f.Index()) == MaxIndex {
   125  		f = 0
   126  	} else if f.IsString() {
   127  		label = f.ToValue(ctx)
   128  	}
   129  
   130  	return matchPatternValue(ctx, pattern, f, label)
   131  }
   132  
   133  // matchPatternValue matches a concrete value against f. label must be the
   134  // CUE value that is obtained from converting f.
   135  //
   136  // This is an optimization an intended to be faster than regular CUE evaluation
   137  // for the majority of cases where pattern constraints are used.
   138  func matchPatternValue(ctx *OpContext, pattern Value, f Feature, label Value) (result bool) {
   139  	pattern = Unwrap(pattern)
   140  	label = Unwrap(label)
   141  
   142  	if pattern == label {
   143  		return true
   144  	}
   145  
   146  	// Fast track for the majority of cases.
   147  	switch x := pattern.(type) {
   148  	case *Bottom:
   149  		// TODO: hoist and reuse with the identical code in optional.go.
   150  		if x == cycle {
   151  			err := ctx.NewPosf(pos(pattern), "cyclic pattern constraint")
   152  			for _, c := range ctx.vertex.Conjuncts {
   153  				addPositions(err, c)
   154  			}
   155  			ctx.AddBottom(&Bottom{
   156  				Err: err,
   157  			})
   158  		}
   159  		if ctx.errs == nil {
   160  			ctx.AddBottom(x)
   161  		}
   162  		return false
   163  
   164  	case *Top:
   165  		return true
   166  
   167  	case *BasicType:
   168  		k := label.Kind()
   169  		return x.K&k == k
   170  
   171  	case *BoundValue:
   172  		switch x.Kind() {
   173  		case StringKind:
   174  			if label == nil {
   175  				return false
   176  			}
   177  			str := label.(*String).Str
   178  			return x.validateStr(ctx, str)
   179  
   180  		case NumKind:
   181  			return x.validateInt(ctx, int64(f.Index()))
   182  		}
   183  
   184  	case *Num:
   185  		if !f.IsInt() {
   186  			return false
   187  		}
   188  		yi := int64(f.Index())
   189  		xi, err := x.X.Int64()
   190  		return err == nil && xi == yi
   191  
   192  	case *String:
   193  		y, ok := label.(*String)
   194  		return ok && x.Str == y.Str
   195  
   196  	case *Conjunction:
   197  		for _, a := range x.Values {
   198  			if !matchPatternValue(ctx, a, f, label) {
   199  				return false
   200  			}
   201  		}
   202  		return true
   203  
   204  	case *Disjunction:
   205  		for _, a := range x.Values {
   206  			if matchPatternValue(ctx, a, f, label) {
   207  				return true
   208  			}
   209  		}
   210  		return false
   211  	}
   212  
   213  	// Slow track.
   214  	//
   215  	// TODO(perf): if a pattern tree has many values that are not handled in the
   216  	// fast track, it is probably more efficient to handle everything in the
   217  	// slow track. One way to signal this would be to have a "value thunk" at
   218  	// the root that causes the fast track to be bypassed altogether.
   219  
   220  	if label == nil {
   221  		label = f.ToValue(ctx)
   222  	}
   223  
   224  	n := ctx.newInlineVertex(nil, nil,
   225  		MakeConjunct(ctx.e, pattern, ctx.ci),
   226  		MakeConjunct(ctx.e, label, ctx.ci))
   227  	n.Finalize(ctx)
   228  	return n.Err(ctx) == nil
   229  }
   230
View as plain text