| 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 |
} |