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