Debian Codegraph @

src/boolean.c

raw
1 /*
2 * boolean.c
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/configP.h"
37 #include "gauche/priv/vmP.h" /* for ScmVMUndefinedBool() */
38
39 int Scm_EqP(ScmObj x, ScmObj y)
40 {
41 return SCM_EQ(x, y);
42 }
43
44 int Scm_EqvP(ScmObj x, ScmObj y)
45 {
46 /* For our implementation, only numbers need different treatment
47 than SCM_EQ. We first check flonums, or we'd have to FLONUM_ENSURE_MEM
48 before we pass them to Scm_NumEq.
49 */
50 if (SCM_NUMBERP(x)) {
51 if (SCM_NUMBERP(y)) {
52 /* Since flonums are the only "inexact real" type in Gauche,
53 we can safely reject the cases where either one is flonum and
54 another is not. */
55 if (SCM_FLONUMP(x)) {
56 if (SCM_FLONUMP(y)) {
57 double rx = SCM_FLONUM_VALUE(x);
58 double ry = SCM_FLONUM_VALUE(y);
59 /* Comparison of signbit is for (eq? 0.0 -0.0) => #f.
60 R7RS 6.1: eqv? returns #f if ... obj1 and obj2 are
61 both inexact numbers such that ... they do not yield
62 the same results when passed as arguments to any
63 other procedure that can be defined as a finite
64 composition of Scheme's standard arithmetic
65 procedures, ... */
66 return (rx == ry && signbit(rx) == signbit(ry));
67 } else {
68 return FALSE;
69 }
70 } else if (SCM_FLONUMP(y)) {
71 return FALSE;
72 }
73 /* More generic case. */
74 if ((SCM_EXACTP(x) && SCM_EXACTP(y))
75 || (SCM_INEXACTP(x) && SCM_INEXACTP(y))) {
76 return Scm_NumEq(x, y);
77 }
78 }
79 return FALSE;
80 }
81 return SCM_EQ(x, y);
82 }
83
84 /* Equal? needs to deal with circuler structures.
85 We adopt the algorithm in Adams&Dybvig's "Efficient Nondestructive
86 Equality Checking for Trees and Graphs",
87 Proceedings of ICFP 08, pp. 179-188.
88
89 It is much easier to write the algorithm in Scheme, but we don't want
90 the overhead of crossing C-Scheme boundary for trivial cases.
91 So we cover a simple cases (non-aggregates, user-defined objects and
92 flat lists/vectors) in C, and fall back to Scheme routine if we encounter
93 more complex structures.
94
95 Caveat: The cycle may involve user-defined objects. To detect such
96 cycle, we need to pass down the context info to ScmClass.compare
97 procedure and object-equal? method. This change would break
98 the backward compatibility, so we'll consider it in future versions.
99 For now, let such cyclic structures explode.
100 */
101
102 int Scm_EqualP(ScmObj x, ScmObj y)
103 {
104 #define CHECK_AGGREGATE(a, b) \
105 do { \
106 if (SCM_PAIRP(a)) { \
107 if (SCM_PAIRP(b)) goto fallback; \
108 return FALSE; \
109 } \
110 if (SCM_VECTORP(a)) { \
111 if (SCM_VECTORP(b)) goto fallback; \
112 return FALSE; \
113 } \
114 if (!Scm_EqualP(a, b)) return FALSE; \
115 } while (0) \
116
117 if (SCM_EQ(x, y)) return TRUE;
118
119 if (SCM_NUMBERP(x)) {
120 if (!SCM_NUMBERP(y)) return FALSE;
121 return Scm_EqvP(x, y);
122 }
123 if (SCM_PAIRP(x)) {
124 if (!SCM_PAIRP(y)) return FALSE;
125 /* We loop on "spine" of lists, so that the typical long flat list
126 can be compared quickly. If we find nested lists/vectors, we
127 jump to Scheme routine. We adopt hare and tortoise to detect
128 loop in the CDR side. */
129 ScmObj xslow = x; ScmObj yslow = y;
130 int xcirc = FALSE; int ycirc = FALSE;
131 for (;;) {
132 ScmObj carx = SCM_CAR(x);
133 ScmObj cary = SCM_CAR(y);
134 CHECK_AGGREGATE(carx, cary);
135
136 x = SCM_CDR(x); y = SCM_CDR(y);
137 if (!SCM_PAIRP(x) || !SCM_PAIRP(y)) return Scm_EqualP(x, y);
138 carx = SCM_CAR(x); cary = SCM_CAR(y);
139
140 CHECK_AGGREGATE(carx, cary);
141
142 if (xslow == x) {
143 if (ycirc) return TRUE;
144 xcirc = TRUE;
145 }
146 if (yslow == y) {
147 if (xcirc) return TRUE;
148 ycirc = TRUE;
149 }
150
151 x = SCM_CDR(x); y = SCM_CDR(y);
152 if (!SCM_PAIRP(x) || !SCM_PAIRP(y)) return Scm_EqualP(x, y);
153 xslow = SCM_CDR(xslow); yslow = SCM_CDR(yslow);
154 }
155 }
156 if (SCM_VECTORP(x)) {
157 if (!SCM_VECTORP(y)) return FALSE;
158 ScmWord i = 0, len = SCM_VECTOR_SIZE(x);
159 if (SCM_VECTOR_SIZE(y) != len) return FALSE;
160 for (; i < len; i++) {
161 ScmObj xx = SCM_VECTOR_ELEMENT(x, i);
162 ScmObj yy = SCM_VECTOR_ELEMENT(y, i);
163 /* NB: If we detect nested structure in middle of vectors,
164 we run Scheme routine for the entire vector; so we'll test
165 equality of elements before the current one again. If
166 they are simple objects that's negligible, but there may
167 be objects of user-defined datatypes, for which object-equal?
168 could be expensive; we'll fix it in future. */
169 CHECK_AGGREGATE(xx, yy);
170 }
171 return TRUE;
172 }
173 if (SCM_STRINGP(x)) {
174 if (!SCM_STRINGP(y)) return FALSE;
175 return Scm_StringEqual(SCM_STRING(x), SCM_STRING(y));
176 }
177 /* EXPERIMENTAL: when identifier is compared by equal?,
178 we use its symbolic name to compare. This allows
179 comparing macro output with equal?, and also less confusing
180 when R5RS macro and legacy macro are mixed.
181 For "proper" comparison of identifiers keeping their semantics,
182 we need such procedures as free-identifier=? and bound-identifier=?
183 anyway, so this change of equal? won't have a negative impact, I hope.
184
185 NB: this operation come here instead of the beginning of this
186 procedure, since comparing identifiers are relatively rare so
187 we don't want to check idnetifier-ness every time.
188 */
189 if (SCM_IDENTIFIERP(x) || SCM_IDENTIFIERP(y)) {
190 if (SCM_IDENTIFIERP(x))
191 x = SCM_OBJ(Scm_UnwrapIdentifier(SCM_IDENTIFIER(x)));
192 if (SCM_IDENTIFIERP(y))
193 y = SCM_OBJ(Scm_UnwrapIdentifier(SCM_IDENTIFIER(y)));
194 return SCM_EQ(x, y);
195 }
196 /* End of EXPERIMENTAL code */
197
198 if (!SCM_HPTRP(x)) return (x == y);
199 ScmClass *cx = Scm_ClassOf(x);
200 ScmClass *cy = Scm_ClassOf(y);
201 if (cx == cy && cx->compare) return (cx->compare(x, y, TRUE) == 0);
202 else return FALSE;
203
204 fallback:
205 {
206 /* Fall back to Scheme version. */
207 static ScmObj equal_interleave_proc = SCM_UNDEFINED;
208 SCM_BIND_PROC(equal_interleave_proc, "%interleave-equal?",
209 Scm_GaucheInternalModule());
210 return !SCM_FALSEP(Scm_ApplyRec2(equal_interleave_proc, x, y));
211 }
212 #undef CHECK_AGGREGATE
213 }
214
215 int Scm_EqualM(ScmObj x, ScmObj y, int mode)
216 {
217 switch (mode) {
218 case SCM_CMP_EQ:
219 return SCM_EQ(x, y);
220 case SCM_CMP_EQV:
221 return Scm_EqvP(x, y);
222 case SCM_CMP_EQUAL:
223 return Scm_EqualP(x, y);
224 }
225 return FALSE;
226 }
227
228 /*
229 * This is called from BF and BT instructions, right after we found
230 * #<undef> is used in boolean expression.
231 */
232
233 extern void Scm_DumpStackTrace(ScmVM*, ScmPort*);
234 extern void Scm_VMDump(ScmVM*);
235
236 int Scm_VMUndefinedBool(ScmVM *vm)
237 {
238 if (SCM_VM_RUNTIME_FLAG_IS_SET(vm, SCM_CHECK_UNDEFINED_TEST)) {
239 Scm_Warn("#<undef> is used in boolean context.\n");
240 Scm_DumpStackTrace(vm, SCM_CURERR);
241 //Too verbose, but can be useful to track into precomp'd code
242 //Scm_VMDump(vm);
243 }
244 return FALSE; /* must return FALSE (meaning 'undefined is not #f') */
245 }