equality.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  type Flag uint16
    18  
    19  const (
    20  	// IgnoreOptional allows optional information to be ignored. This only
    21  	// applies when CheckStructural is given.
    22  	IgnoreOptional Flag = 1 << iota
    23  
    24  	// CheckStructural indicates that closedness information should be
    25  	// considered for equality. Equal may return false even when values are
    26  	// equal.
    27  	CheckStructural Flag = 1 << iota
    28  )
    29  
    30  func Equal(ctx *OpContext, v, w Value, flags Flag) bool {
    31  	if x, ok := v.(*Vertex); ok {
    32  		return equalVertex(ctx, x, w, flags)
    33  	}
    34  	if y, ok := w.(*Vertex); ok {
    35  		return equalVertex(ctx, y, v, flags)
    36  	}
    37  	return equalTerminal(ctx, v, w, flags)
    38  }
    39  
    40  func equalVertex(ctx *OpContext, x *Vertex, v Value, flags Flag) bool {
    41  	y, ok := v.(*Vertex)
    42  	if !ok {
    43  		return false
    44  	}
    45  	if x == y {
    46  		return true
    47  	}
    48  	if x.ArcType != y.ArcType {
    49  		return false
    50  	}
    51  	xk := x.Kind()
    52  	yk := y.Kind()
    53  
    54  	if xk != yk {
    55  		return false
    56  	}
    57  
    58  	maxArcType := ArcMember
    59  	if flags&CheckStructural != 0 {
    60  		// Do not ignore optional fields
    61  		// TODO(required): consider making this unconditional
    62  		maxArcType = ArcOptional
    63  	}
    64  
    65  	// TODO: this really should be subsumption.
    66  	if flags != 0 {
    67  		if x.IsClosedStruct() != y.IsClosedStruct() {
    68  			return false
    69  		}
    70  		if !equalClosed(ctx, x, y, flags) {
    71  			return false
    72  		}
    73  	}
    74  
    75  loop1:
    76  	for _, a := range x.Arcs {
    77  		if a.ArcType > maxArcType {
    78  			continue
    79  		}
    80  		for _, b := range y.Arcs {
    81  			if a.Label == b.Label {
    82  				if a.ArcType != b.ArcType || !Equal(ctx, a, b, flags) {
    83  					return false
    84  				}
    85  				continue loop1
    86  			}
    87  		}
    88  		return false
    89  	}
    90  
    91  loop2:
    92  	for _, b := range y.Arcs {
    93  		if b.ArcType > maxArcType {
    94  			continue
    95  		}
    96  		for _, a := range x.Arcs {
    97  			if a.Label == b.Label {
    98  				if a.ArcType > maxArcType {
    99  					// No need to continue: arc with label not found.
   100  					break
   101  				}
   102  				// Label found. Equality was already tested in loop 1.
   103  				continue loop2
   104  			}
   105  		}
   106  		// Arc with same label not found.
   107  		return false
   108  	}
   109  
   110  	v, ok1 := x.BaseValue.(Value)
   111  	w, ok2 := y.BaseValue.(Value)
   112  	if !ok1 && !ok2 {
   113  		return true // both are struct or list.
   114  	}
   115  
   116  	return equalTerminal(ctx, v, w, flags)
   117  }
   118  
   119  // equalClosed tests if x and y have the same set of close information.
   120  // TODO: the following refinements are possible:
   121  //   - unify optional fields and equate the optional fields
   122  //   - do the same for pattern constraints, where the pattern constraints
   123  //     are collated by pattern equality.
   124  //   - a further refinement would collate patterns by ranges.
   125  //
   126  // For all these refinements it would be necessary to have well-working
   127  // structure sharing so as to not repeatedly recompute optional arcs.
   128  func equalClosed(ctx *OpContext, x, y *Vertex, flags Flag) bool {
   129  	return verifyStructs(x, y, flags) && verifyStructs(y, x, flags)
   130  }
   131  
   132  func verifyStructs(x, y *Vertex, flags Flag) bool {
   133  outer:
   134  	for _, s := range x.Structs {
   135  		if (flags&IgnoreOptional != 0) && !s.StructLit.HasOptional() {
   136  			continue
   137  		}
   138  		if s.span()&DefinitionSpan == 0 {
   139  			if !s.StructLit.HasOptional() {
   140  				continue
   141  			}
   142  		}
   143  		for _, t := range y.Structs {
   144  			if s.StructLit == t.StructLit {
   145  				continue outer
   146  			}
   147  		}
   148  		return false
   149  	}
   150  	return true
   151  }
   152  
   153  func equalTerminal(ctx *OpContext, v, w Value, flags Flag) bool {
   154  	if v == w {
   155  		return true
   156  	}
   157  
   158  	switch x := v.(type) {
   159  	case *Bottom:
   160  		// All errors are logically the same.
   161  		_, ok := w.(*Bottom)
   162  		return ok
   163  
   164  	case *Num, *String, *Bool, *Bytes, *Null:
   165  		if b, ok := BinOp(ctx, EqualOp, v, w).(*Bool); ok {
   166  			return b.B
   167  		}
   168  		return false
   169  
   170  	// TODO: for the remainder we are dealing with non-concrete values, so we
   171  	// could also just not bother.
   172  
   173  	case *BoundValue:
   174  		if y, ok := w.(*BoundValue); ok {
   175  			return x.Op == y.Op && Equal(ctx, x.Value, y.Value, flags)
   176  		}
   177  
   178  	case *BasicType:
   179  		if y, ok := w.(*BasicType); ok {
   180  			return x.K == y.K
   181  		}
   182  
   183  	case *Conjunction:
   184  		y, ok := w.(*Conjunction)
   185  		if !ok || len(x.Values) != len(y.Values) {
   186  			return false
   187  		}
   188  		// always ordered the same
   189  		for i, xe := range x.Values {
   190  			if !Equal(ctx, xe, y.Values[i], flags) {
   191  				return false
   192  			}
   193  		}
   194  		return true
   195  
   196  	case *Disjunction:
   197  		// The best way to compute this is with subsumption, but even that won't
   198  		// be too accurate. Assume structural equivalence for now.
   199  		y, ok := w.(*Disjunction)
   200  		if !ok || len(x.Values) != len(y.Values) {
   201  			return false
   202  		}
   203  		for i, xe := range x.Values {
   204  			if !Equal(ctx, xe, y.Values[i], flags) {
   205  				return false
   206  			}
   207  		}
   208  		return true
   209  
   210  	case *BuiltinValidator:
   211  	}
   212  
   213  	return false
   214  }
   215
View as plain text