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 15package adt 16 17type Flag uint16 18 19const ( 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 30func 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 40func 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 xk := x.Kind() 49 yk := y.Kind() 50 51 if xk != yk { 52 return false 53 } 54 55 if len(x.Arcs) != len(y.Arcs) { 56 return false 57 } 58 59 // TODO: this really should be subsumption. 60 if flags != 0 { 61 if x.IsClosedStruct() != y.IsClosedStruct() { 62 return false 63 } 64 if !equalClosed(ctx, x, y, flags) { 65 return false 66 } 67 } 68 69loop1: 70 for _, a := range x.Arcs { 71 for _, b := range y.Arcs { 72 if a.Label == b.Label { 73 if !Equal(ctx, a, b, flags) { 74 return false 75 } 76 continue loop1 77 } 78 } 79 return false 80 } 81 82 // We do not need to do the following check, because of the pigeon-hole principle. 83 // loop2: 84 // for _, b := range y.Arcs { 85 // for _, a := range x.Arcs { 86 // if a.Label == b.Label { 87 // continue loop2 88 // } 89 // } 90 // return false 91 // } 92 93 v, ok1 := x.BaseValue.(Value) 94 w, ok2 := y.BaseValue.(Value) 95 if !ok1 && !ok2 { 96 return true // both are struct or list. 97 } 98 99 return equalTerminal(ctx, v, w, flags) 100} 101 102// equalClosed tests if x and y have the same set of close information. 103// TODO: the following refinements are possible: 104// - unify optional fields and equate the optional fields 105// - do the same for pattern constraints, where the pattern constraints 106// are collated by pattern equality. 107// - a further refinement would collate patterns by ranges. 108// 109// For all these refinements it would be necessary to have well-working 110// structure sharing so as to not repeatedly recompute optional arcs. 111func equalClosed(ctx *OpContext, x, y *Vertex, flags Flag) bool { 112 return verifyStructs(x, y, flags) && verifyStructs(y, x, flags) 113} 114 115func verifyStructs(x, y *Vertex, flags Flag) bool { 116outer: 117 for _, s := range x.Structs { 118 if (flags&IgnoreOptional != 0) && !s.StructLit.HasOptional() { 119 continue 120 } 121 if s.closeInfo == nil || s.closeInfo.span&DefinitionSpan == 0 { 122 if !s.StructLit.HasOptional() { 123 continue 124 } 125 } 126 for _, t := range y.Structs { 127 if s.StructLit == t.StructLit { 128 continue outer 129 } 130 } 131 return false 132 } 133 return true 134} 135 136func equalTerminal(ctx *OpContext, v, w Value, flags Flag) bool { 137 if v == w { 138 return true 139 } 140 141 switch x := v.(type) { 142 case *Num, *String, *Bool, *Bytes, *Null: 143 if b, ok := BinOp(ctx, EqualOp, v, w).(*Bool); ok { 144 return b.B 145 } 146 return false 147 148 // TODO: for the remainder we are dealing with non-concrete values, so we 149 // could also just not bother. 150 151 case *BoundValue: 152 if y, ok := w.(*BoundValue); ok { 153 return x.Op == y.Op && Equal(ctx, x.Value, y.Value, flags) 154 } 155 156 case *BasicType: 157 if y, ok := w.(*BasicType); ok { 158 return x.K == y.K 159 } 160 161 case *Conjunction: 162 y, ok := w.(*Conjunction) 163 if !ok || len(x.Values) != len(y.Values) { 164 return false 165 } 166 // always ordered the same 167 for i, xe := range x.Values { 168 if !Equal(ctx, xe, y.Values[i], flags) { 169 return false 170 } 171 } 172 return true 173 174 case *Disjunction: 175 // The best way to compute this is with subsumption, but even that won't 176 // be too accurate. Assume structural equivalence for now. 177 y, ok := w.(*Disjunction) 178 if !ok || len(x.Values) != len(y.Values) { 179 return false 180 } 181 for i, xe := range x.Values { 182 if !Equal(ctx, xe, y.Values[i], flags) { 183 return false 184 } 185 } 186 return true 187 188 case *BuiltinValidator: 189 } 190 191 return false 192} 193