1 /* compare.c -*- mode:c; coding:utf-8; -*-
2 *
3 * Copyright (c) 2010-2021 Takashi Kato <ktakashi@ymail.com>
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * $Id: $
29 */
30 #define LIBSAGITTARIUS_BODY
31 #include "sagittarius/private/compare.h"
32 #include "sagittarius/private/codec.h"
33 #include "sagittarius/private/clos.h"
34 #include "sagittarius/private/error.h"
35 #include "sagittarius/private/identifier.h"
36 #include "sagittarius/private/instruction.h"
37 #include "sagittarius/private/library.h"
38 #include "sagittarius/private/number.h"
39 #include "sagittarius/private/pair.h"
40 #include "sagittarius/private/bytevector.h"
41 #include "sagittarius/private/record.h"
42 #include "sagittarius/private/string.h"
43 #include "sagittarius/private/subr.h"
44 #include "sagittarius/private/symbol.h"
45 #include "sagittarius/private/vector.h"
46 #include "sagittarius/private/hashtable.h"
47 #include "sagittarius/private/vm.h" /* for box */
48 #include "sagittarius/private/writer.h"
49
50 /* #undef INSPECT_RECORD_FIELD */
51 #define INSPECT_RECORD_FIELD
52
comparator_print(SgObject o,SgPort * port,SgWriteContext * ctx)53 static void comparator_print(SgObject o, SgPort *port, SgWriteContext *ctx)
54 {
55 SgComparator *c = SG_COMPARATOR(o);
56 if (SG_FALSEP(c->name)) {
57 Sg_Printf(port, UC("#<comparator %p>"), c);
58 } else {
59 Sg_Printf(port, UC("#<comparator %S>"), c->name);
60 }
61 }
62
63 SG_DEFINE_BUILTIN_CLASS_SIMPLE(Sg_ComparatorClass, comparator_print);
64
65 /* fields are immutable */
66 #define DEF_ACCESSOR(field) \
67 static SgObject SG_CPP_CAT(comparator_, field)(SgObject c) \
68 { \
69 return SG_COMPARATOR(c)->field; \
70 }
71 DEF_ACCESSOR(name)
72 DEF_ACCESSOR(typeFn)
73 DEF_ACCESSOR(eqFn)
74 DEF_ACCESSOR(compFn)
75 DEF_ACCESSOR(hashFn)
76
77 static SgSlotAccessor comparator_slots[] = {
78 SG_CLASS_SLOT_SPEC("name", 0, comparator_name, NULL),
79 SG_CLASS_SLOT_SPEC("type-test", 1, comparator_typeFn, NULL),
80 SG_CLASS_SLOT_SPEC("equality", 2, comparator_eqFn, NULL),
81 SG_CLASS_SLOT_SPEC("comparison", 3, comparator_compFn, NULL),
82 SG_CLASS_SLOT_SPEC("hash", 4, comparator_hashFn, NULL),
83 { { NULL } }
84 };
85
no_type_test(SgObject * args,int argc,void * data)86 static SgObject no_type_test(SgObject *args, int argc, void *data)
87 {
88 return SG_TRUE;
89 }
no_comparison(SgObject * args,int argc,void * data)90 static SgObject no_comparison(SgObject *args, int argc, void *data)
91 {
92 Sg_Error(UC("comparison: can't compare objects %S vs %S"), args[0], args[1]);
93 return SG_UNDEF; /* dummy */
94 }
no_hash(SgObject * args,int argc,void * data)95 static SgObject no_hash(SgObject *args, int argc, void *data)
96 {
97 Sg_Error(UC("hash function is not supported"));
98 return SG_UNDEF; /* dummy */
99 }
100 static SG_DEFINE_SUBR(no_type_test_stub, 1, 0, no_type_test, SG_FALSE, NULL);
101 static SG_DEFINE_SUBR(no_comparison_stub, 2, 0, no_comparison, SG_FALSE, NULL);
102 static SG_DEFINE_SUBR(no_hash_stub, 1, 0, no_hash, SG_FALSE, NULL);
103
104 /* now we define eq?, eqv? equal? eq-hash, eqv-hash and equal-hash here */
105 #define DEF_EQ_PROC(name, proc) \
106 static SgObject SG_CPP_CAT(name, _proc)(SgObject *args, int argc, void *data) \
107 { \
108 return SG_MAKE_BOOL(proc(args[0], args[1])); \
109 } \
110 static SG_DEFINE_SUBR(SG_CPP_CAT(name, _proc_stub), 2, 0, \
111 SG_CPP_CAT(name, _proc), SG_FALSE, NULL);
112 DEF_EQ_PROC(eq, SG_EQ)
113 DEF_EQ_PROC(eqv, Sg_EqvP)
114 DEF_EQ_PROC(equal, Sg_EqualP)
115
116 static int r6rs_equalp(SgObject x, SgObject y);
DEF_EQ_PROC(r6rs_equal,r6rs_equalp)117 DEF_EQ_PROC(r6rs_equal, r6rs_equalp)
118 #undef DEF_EQ_PROC
119
120 #define DEF_HASH_PROC(name, proc) \
121 static SgObject SG_CPP_CAT(name, _hash_proc) \
122 (SgObject *args, int argc, void *data) \
123 { \
124 long bound = 0; \
125 if (argc > 2) { \
126 if (!SG_INTP(args[1])) { \
127 Sg_Error(UC("bound must a fixnum: %S"), args[1]); \
128 } \
129 bound = SG_INT_VALUE(args[1]); \
130 } \
131 return Sg_MakeIntegerU(proc(args[0], bound)); \
132 } \
133 static SG_DEFINE_SUBR(SG_CPP_CAT(name, _hash_proc_stub), 1, 1, \
134 SG_CPP_CAT(name, _hash_proc), SG_FALSE, NULL);
135 DEF_HASH_PROC(eq, Sg_EqHash)
136 DEF_HASH_PROC(eqv, Sg_EqvHash)
137 DEF_HASH_PROC(equal, Sg_EqualHash)
138 #undef DEF_HASH_PROC
139
140 /* string comparator. this is not the same as string=?, string-hash but
141 match more simplified.
142 NOTE: we don't expose them directly from (sagittarius) or (core)
143 */
144 /* string?
145 TODO Should we export this from (core)?
146 */
147 static SgObject string_p(SgObject *args, int argc, void *data)
148 {
149 return SG_MAKE_BOOL(SG_STRINGP(args[0]));
150 }
151 static SG_DEFINE_SUBR(string_p_stub, 1, 0, string_p, SG_FALSE, NULL);
152
153 /* string-hash */
string_hash(SgObject * args,int argc,void * data)154 static SgObject string_hash(SgObject *args, int argc, void *data)
155 {
156 if (!SG_STRINGP(args[0])) {
157 Sg_WrongTypeOfArgumentViolation(SG_INTERN("string-comparator"),
158 SG_INTERN("string"), args[0], SG_NIL);
159 }
160 return Sg_MakeIntegerU(Sg_StringHash(SG_STRING(args[0]),
161 (uint32_t)SG_INT_MAX));
162 }
163 static SG_DEFINE_SUBR(string_hash_stub, 1, 3, string_hash, SG_FALSE, NULL);
164
string_eq(SgObject * args,int argc,void * data)165 static SgObject string_eq(SgObject *args, int argc, void *data)
166 {
167 if (!SG_STRINGP(args[0]) || !SG_STRINGP(args[1])) {
168 Sg_WrongTypeOfArgumentViolation(SG_INTERN("string-comparator"),
169 SG_INTERN("string"),
170 SG_LIST2(args[0], args[1]),
171 SG_NIL);
172 }
173 return SG_MAKE_BOOL(Sg_StringEqual(SG_STRING(args[0]), SG_STRING(args[1])));
174 }
175 static SG_DEFINE_SUBR(string_eq_stub, 2, 0, string_eq, SG_FALSE, NULL);
176
string_cmp(SgObject * args,int argc,void * data)177 static SgObject string_cmp(SgObject *args, int argc, void *data)
178 {
179 int r;
180 if (!SG_STRINGP(args[0]) || !SG_STRINGP(args[1])) {
181 Sg_WrongTypeOfArgumentViolation(SG_INTERN("string-comparator"),
182 SG_INTERN("string"),
183 SG_LIST2(args[0], args[1]),
184 SG_NIL);
185 }
186 r = Sg_StringCompare(SG_STRING(args[0]), SG_STRING(args[1]));
187 return SG_MAKE_INT(r);
188 }
189 static SG_DEFINE_SUBR(string_cmp_stub, 2, 0, string_cmp, SG_FALSE, NULL);
190
191
make_comparator(SgObject typeFn,SgObject eqFn,SgObject compFn,SgObject hashFn,SgObject name,unsigned long flags)192 static SgComparator* make_comparator(SgObject typeFn, SgObject eqFn,
193 SgObject compFn, SgObject hashFn,
194 SgObject name, unsigned long flags)
195 {
196 SgComparator *c = SG_NEW(SgComparator);
197 SG_SET_CLASS(c, SG_CLASS_COMPARATOR);
198 c->name = name;
199 c->typeFn = typeFn;
200 c->eqFn = eqFn;
201 c->compFn = compFn;
202 c->hashFn = hashFn;
203 c->flags = flags;
204 return c;
205 }
206
Sg_MakeComparator(SgObject typeFn,SgObject eqFn,SgObject compFn,SgObject hashFn,SgObject name)207 SgObject Sg_MakeComparator(SgObject typeFn, SgObject eqFn,
208 SgObject compFn, SgObject hashFn,
209 SgObject name)
210 {
211 unsigned long flags = 0;
212 if (SG_TRUEP(typeFn)) {
213 typeFn = SG_OBJ(&no_type_test_stub);
214 flags |= SG_COMPARATOR_ANY_TYPE;
215 }
216 if (SG_FALSEP(compFn)) {
217 compFn = SG_OBJ(&no_comparison_stub);
218 flags |= SG_COMPARATOR_NO_ORDER;
219 }
220 if (SG_FALSEP(hashFn)) {
221 hashFn = SG_OBJ(&no_hash_stub);
222 flags |= SG_COMPARATOR_NO_HASH;
223 }
224 return SG_OBJ(make_comparator(typeFn, eqFn, compFn, hashFn, name, flags));
225 }
226
227 #define DEF_BUILTIN_COMPARATOR(type, eq, comp, hash, flags) \
228 { { SG_CLASS_STATIC_TAG(Sg_ComparatorClass) }, \
229 SG_FALSE, (type), (eq), (comp), (hash), (flags) }
230 #define DEF_EQ_COMPARATOR(eq, hash) \
231 DEF_BUILTIN_COMPARATOR(&no_type_test_stub, \
232 (eq), \
233 &no_comparison_stub, \
234 (hash), \
235 SG_COMPARATOR_NO_ORDER | \
236 SG_COMPARATOR_ANY_TYPE)
237
238 static SgComparator eq_comparator =
239 DEF_EQ_COMPARATOR(&eq_proc_stub, &eq_hash_proc_stub);
240 static SgComparator eqv_comparator =
241 DEF_EQ_COMPARATOR(&eqv_proc_stub, &eqv_hash_proc_stub);
242 static SgComparator equal_comparator =
243 DEF_EQ_COMPARATOR(&equal_proc_stub, &equal_hash_proc_stub);
244 static SgComparator string_comparator =
245 DEF_BUILTIN_COMPARATOR(&string_p_stub, &string_eq_stub, &string_cmp_stub,
246 &string_hash_stub, 0);
247
Sg_EqComparator()248 SgObject Sg_EqComparator()
249 {
250 return SG_OBJ(&eq_comparator);
251 }
Sg_EqvComparator()252 SgObject Sg_EqvComparator()
253 {
254 return SG_OBJ(&eqv_comparator);
255 }
Sg_EqualComparator()256 SgObject Sg_EqualComparator()
257 {
258 return SG_OBJ(&equal_comparator);
259 }
Sg_StringComparator()260 SgObject Sg_StringComparator()
261 {
262 return SG_OBJ(&string_comparator);
263 }
264
265 /* initialise */
Sg__InitComparator()266 void Sg__InitComparator()
267 {
268 SgLibrary *closlib = Sg_FindLibrary(SG_INTERN("(sagittarius clos)"), FALSE);
269 SgLibrary *corelib = Sg_FindLibrary(SG_INTERN("(core)"), FALSE);
270 SgLibrary *sglib = Sg_FindLibrary(SG_INTERN("(sagittarius)"), FALSE);
271
272 Sg_InitStaticClass(SG_CLASS_COMPARATOR, UC("<comparator>"),
273 closlib, comparator_slots, 0);
274 #define INSERT_EQ_PROC(name, stub, inliner) \
275 do { \
276 SgObject nameS = SG_MAKE_STRING(name); \
277 SG_PROCEDURE_NAME(stub) = nameS; \
278 SG_PROCEDURE_TRANSPARENT(stub) = SG_PROC_TRANSPARENT; \
279 SG_PROCEDURE_INLINER(stub) = (inliner); \
280 Sg_InsertBinding(corelib, Sg_Intern(nameS), SG_OBJ(stub)); \
281 } while (0)
282 INSERT_EQ_PROC("eq?", &eq_proc_stub, SG_MAKE_INT(EQ));
283 INSERT_EQ_PROC("eqv?", &eqv_proc_stub, SG_MAKE_INT(EQV));
284 INSERT_EQ_PROC("equal?", &equal_proc_stub, SG_FALSE);
285 INSERT_EQ_PROC("r6rs-equal?", &r6rs_equal_proc_stub, SG_FALSE);
286 #undef INSERT_EQ_PROC
287
288 #define INSERT_HASH_PROC(lib, name, stub) \
289 do { \
290 SgObject nameS = SG_MAKE_STRING(name); \
291 SG_PROCEDURE_NAME(stub) = nameS; \
292 SG_PROCEDURE_TRANSPARENT(stub) = SG_PROC_NO_SIDE_EFFECT; \
293 Sg_InsertBinding(lib, Sg_Intern(nameS), SG_OBJ(stub)); \
294 } while (0)
295 INSERT_HASH_PROC(sglib, "eq-hash", &eq_hash_proc_stub);
296 INSERT_HASH_PROC(sglib, "eqv-hash", &eqv_hash_proc_stub);
297 INSERT_HASH_PROC(corelib, "equal-hash", &equal_hash_proc_stub);
298 #undef INSERT_HASH_PROC
299 eq_comparator.name = SG_INTERN("eq-comparator");
300 eqv_comparator.name = SG_INTERN("eqv-comparator");
301 equal_comparator.name = SG_INTERN("equal-comparator");
302 string_comparator.name = SG_INTERN("string-comparator");
303 /* for convenience */
304 SG_PROCEDURE_NAME(&string_p_stub) = SG_MAKE_STRING("comparator-string?");
305 SG_PROCEDURE_NAME(&string_eq_stub) = SG_MAKE_STRING("comparator-string=?");
306 SG_PROCEDURE_NAME(&string_cmp_stub) =
307 SG_MAKE_STRING("comparator-string-compare");
308 SG_PROCEDURE_NAME(&string_hash_stub) =
309 SG_MAKE_STRING("comparator-string-hash");
310 }
311
Sg_Compare(SgObject x,SgObject y)312 int Sg_Compare(SgObject x, SgObject y)
313 {
314 SgClass *cx, *cy;
315 if (SG_NUMBERP(x) && SG_NUMBERP(y))
316 return Sg_NumCmp(x, y);
317 if (SG_STRINGP(x) && SG_STRINGP(y))
318 return Sg_StringCompare(SG_STRING(x), SG_STRING(y));
319 if (SG_CHARP(x) && SG_CHARP(y)) {
320 return SG_EQ(x, y)
321 ? 0
322 : (SG_CHAR_VALUE(x) < SG_CHAR_VALUE(y)) ? -1 : 1;
323 }
324 if (SG_BVECTORP(x) && SG_BVECTORP(y))
325 return Sg_ByteVectorCmp(SG_BVECTOR(x), SG_BVECTOR(y));
326 if (SG_BOOLP(x) && SG_BOOLP(y)) {
327 /* following SRFI-128 */
328 if (SG_EQ(x, y)) return 0;
329 if (SG_FALSEP(x)) return -1;
330 return 1;
331 }
332
333 cx = Sg_ClassOf(x);
334 cy = Sg_ClassOf(y);
335 if (Sg_SubtypeP(cx, cy)) {
336 if (cy->compare) return cy->compare(x, y, FALSE);
337 } else {
338 if (cx->compare) return cx->compare(x, y, FALSE);
339 }
340 /* for builtin class extension. e.g <symbol> ... */
341 return Sg_ObjectCompare(x, y);
342 }
343
Sg_EqP(SgObject x,SgObject y)344 int Sg_EqP(SgObject x, SgObject y)
345 {
346 return SG_EQ(x, y);
347 }
348
compare_double(double dx,double dy)349 static int compare_double(double dx, double dy)
350 {
351 if (dx == 0.0 && dy == 0.0) {
352 /* get sign */
353 union { double f64; uint64_t u64; } d1, d2;
354 int signx, signy;
355 d1.f64 = dx;
356 d2.f64 = dy;
357 signx = d1.u64 >> 63;
358 signy = d2.u64 >> 63;
359 return signx == signy;
360 } else {
361 return dx == dy;
362 }
363 }
364
eqv_internal(SgObject x,SgObject y,int from_equal_p)365 static int eqv_internal(SgObject x, SgObject y, int from_equal_p)
366 {
367 SgClass *cx, *cy;
368 if (SG_EQ(x, y)) return TRUE;
369 if (SG_NUMBERP(x)) {
370 if (SG_NUMBERP(y)) {
371 if (SG_FLONUMP(x)) {
372 if (SG_FLONUMP(y)) {
373 /* R6RS 11.5 6th item */
374 double dx = SG_FLONUM_VALUE(x);
375 double dy = SG_FLONUM_VALUE(y);
376 return compare_double(dx, dy);
377 } else {
378 return FALSE;
379 }
380 } else if (SG_FLONUMP(y)) {
381 return FALSE;
382 }
383 if (Sg_ExactP(x) && Sg_ExactP(y)) {
384 return Sg_NumEq(x, y);
385 } else if (Sg_InexactP(x) && Sg_InexactP(y)) {
386 /* must be both complex numbers but just in case */
387 if (SG_COMPLEXP(x) && SG_COMPLEXP(y)) {
388 /* both imag and ream must be flonum but just in case */
389 double xr = Sg_GetDouble(SG_COMPLEX(x)->real);
390 double xi = Sg_GetDouble(SG_COMPLEX(x)->imag);
391 double yr = Sg_GetDouble(SG_COMPLEX(y)->real);
392 double yi = Sg_GetDouble(SG_COMPLEX(y)->imag);
393 return compare_double(xr, yr) && compare_double(xi, yi);
394 } else {
395 return FALSE;
396 }
397 } else {
398 /* exact and inexact */
399 return FALSE;
400 }
401 }
402 return FALSE;
403 }
404 if (SG_CODECP(x)) {
405 if (SG_CODECP(y)) {
406 /* if these 2 are the same codec, it must use the same putc and getc
407 method and the same endianness.
408 */
409 if ((SG_CODEC(x)->type == SG_BUILTIN_CODEC &&
410 (SG_CODEC_BUILTIN(x)->getc == SG_CODEC_BUILTIN(y)->getc) &&
411 (SG_CODEC_BUILTIN(x)->putc == SG_CODEC_BUILTIN(y)->putc) &&
412 (SG_CODEC_ENDIAN(x) == SG_CODEC_ENDIAN(y))) ||
413 (SG_CODEC(x)->type == SG_CUSTOM_CODEC &&
414 /* we just compare the name */
415 SG_EQ(SG_CODEC(x)->name, SG_CODEC(y)->name))) {
416 return TRUE;
417 } else {
418 return FALSE;
419 }
420 } else {
421 return FALSE;
422 }
423 }
424
425 if (!SG_HPTRP(x)) return SG_EQ(x, y);
426
427 if (from_equal_p) {
428 cx = Sg_ClassOf(x);
429 cy = Sg_ClassOf(y);
430 if (cx == cy && cx->compare) {
431 return (cx->compare(x, y, TRUE) == 0);
432 }
433 }
434 return FALSE;
435 }
436
Sg_EqvP(SgObject x,SgObject y)437 int Sg_EqvP(SgObject x, SgObject y)
438 {
439 return eqv_internal(x, y, FALSE);
440 }
441
442 /* R6RS requires to equal? to stop when the given object were shared object */
443 #if 0
444 int Sg_EqualP(SgObject x, SgObject y)
445 {
446 if (SG_EQ(x, y)) return TRUE;
447 if (SG_PAIRP(x)) {
448 if (!SG_PAIRP(y)) return FALSE;
449 do {
450 if (!Sg_EqualP(SG_CAR(x), SG_CAR(y))) return FALSE;
451 x = SG_CDR(x);
452 y = SG_CDR(y);
453 } while(SG_PAIRP(x) && SG_PAIRP(y));
454 return Sg_EqualP(x, y);
455 }
456 if (SG_STRINGP(x)) {
457 if (!SG_STRINGP(y)) return FALSE;
458 return Sg_StringEqual(SG_STRING(x), SG_STRING(y));
459 }
460 if (SG_NUMBERP(x)) {
461 if (SG_NUMBERP(y)) {
462 if ((Sg_ExactP(x) && Sg_ExactP(y))
463 && (Sg_InexactP(x) && Sg_InexactP(y))) {
464 return Sg_NumEq(x, y);
465 }
466 }
467 return FALSE;
468 }
469 if (SG_VECTORP(x)) {
470 if (SG_VECTORP(y)) {
471 int sizex = SG_VECTOR_SIZE(x);
472 int sizey = SG_VECTOR_SIZE(y);
473 if (sizex == sizey) {
474 while (sizex--) {
475 if (!Sg_EqualP(SG_VECTOR_ELEMENT(x, sizex),
476 SG_VECTOR_ELEMENT(y, sizex)))
477 break;
478 }
479 if (sizex < 0) return TRUE;
480 }
481 }
482 }
483 /* TODO: gauche just compare the name. should this be like that? */
484 if (SG_IDENTIFIERP(x)) {
485 if (SG_IDENTIFIERP(y)) {
486 return SG_EQ(SG_IDENTIFIER(x)->name, SG_IDENTIFIER(y)->name)
487 && SG_EQ(SG_IDENTIFIER(x)->library, SG_IDENTIFIER(y)->library);
488 }
489 return FALSE;
490 }
491
492 return FALSE;
493 }
494
495 #endif
496
497 /* should i make api for box? */
make_box(SgObject value)498 static inline SgObject make_box(SgObject value)
499 {
500 SgBox *b = SG_NEW(SgBox);
501 SG_SET_CLASS(b, SG_CLASS_BOX);
502 b->value = value;
503 return SG_OBJ(b);
504 }
505
506 struct equal_context
507 {
508 SgObject k0;
509 SgObject kb;
510 int inspect_record_p; /* compares record fields or not */
511 };
512
pre_p(SgObject x,SgObject y,SgObject k,struct equal_context * ctx)513 static SgObject pre_p(SgObject x, SgObject y, SgObject k,
514 struct equal_context *ctx)
515 {
516 if (x == y) return k;
517 if (SG_PAIRP(x)) {
518 if (!SG_PAIRP(y)) {
519 return SG_FALSE;
520 }
521 ASSERT(SG_INTP(k));
522 if (SG_INT_VALUE(k) <= 0) {
523 return k;
524 } else {
525 SgObject k2 = pre_p(SG_CAR(x), SG_CAR(y),
526 SG_MAKE_INT(SG_INT_VALUE(k) - 1),
527 ctx);
528 if (SG_FALSEP(k2)) {
529 return SG_FALSE;
530 }
531 return pre_p(SG_CDR(x), SG_CDR(y), k2, ctx);
532 }
533 }
534 if (SG_VECTORP(x)) {
535 if (!SG_VECTORP(y)) {
536 return SG_FALSE;
537 } else {
538 long sizex = SG_VECTOR_SIZE(x);
539 long sizey = SG_VECTOR_SIZE(y);
540 if (sizex != sizey) {
541 return SG_FALSE;
542 } else {
543 long i;
544 ASSERT(SG_INTP(k));
545 for (i = 0;; i++) {
546 if (i == sizex || SG_INT_VALUE(k) <= 0) {
547 return k;
548 } else {
549 SgObject k2 = pre_p(SG_VECTOR_ELEMENT(x, i),
550 SG_VECTOR_ELEMENT(y, i),
551 SG_MAKE_INT(SG_INT_VALUE(k) - 1),
552 ctx);
553 if (SG_FALSEP(k2)) {
554 return SG_FALSE;
555 }
556 k = k2;
557 }
558 }
559 }
560 }
561 }
562 if (SG_STRINGP(x)) {
563 if (!SG_STRINGP(y)) {
564 return SG_FALSE;
565 }
566 if (Sg_StringEqual(x, y)) {
567 return k;
568 } else {
569 return SG_FALSE;
570 }
571 }
572
573 if (SG_BVECTORP(x)) {
574 if (!SG_BVECTORP(y)) {
575 return SG_FALSE;
576 }
577 if (Sg_ByteVectorEqP(x, y)) {
578 return k;
579 } else {
580 return SG_FALSE;
581 }
582 }
583
584 /* Record inspection */
585 if (ctx->inspect_record_p) {
586 if (Sg_RecordP(x)) {
587 if (Sg_RecordP(y)) {
588 SgClass *xklass = Sg_ClassOf(x);
589 SgClass *yklass = Sg_ClassOf(y);
590 if (xklass != yklass) return SG_FALSE; /* obvious */
591 else {
592 SgSlotAccessor **xacc = xklass->gettersNSetters;
593 SgSlotAccessor **yacc = yklass->gettersNSetters;
594 for (; xacc && *xacc && yacc && *yacc; xacc++, yacc++) {
595 SgObject xe = Sg_SlotRefUsingAccessor(x, *xacc);
596 SgObject ye = Sg_SlotRefUsingAccessor(y, *yacc);
597 SgObject k2;
598 if (SG_INT_VALUE(k) <= 0) return k;
599 if (SG_UNBOUNDP(xe) || SG_UNBOUNDP(ye)) return SG_FALSE;
600 k2 = pre_p(xe, ye, SG_MAKE_INT(SG_INT_VALUE(k) -1), ctx);
601 if (SG_FALSEP(k2)) {
602 return SG_FALSE;
603 }
604 k = k2;
605 }
606 return k;
607 }
608 }
609 return SG_FALSE;
610 }
611 }
612 if (eqv_internal(x, y, TRUE)) {
613 return k;
614 } else {
615 return SG_FALSE;
616 }
617 }
618
619 /* for VS2008 */
620 static SgObject fast_p(SgHashTable **pht, SgObject x, SgObject y,
621 SgObject k, struct equal_context *ctx);
622 static SgObject slow_p(SgHashTable **pht, SgObject x, SgObject y,
623 SgObject k, struct equal_context *ctx);
624
625 #ifdef _WIN32
626 #define random rand
627 #endif
eP(SgHashTable ** pht,SgObject x,SgObject y,SgObject k,struct equal_context * ctx)628 static SgObject eP(SgHashTable **pht, SgObject x, SgObject y, SgObject k,
629 struct equal_context *ctx)
630 {
631 ASSERT(SG_INTP(k));
632 if (SG_INT_VALUE(k) <= 0) {
633 if (k == ctx->kb) {
634 k = SG_MAKE_INT(random() % (2 * SG_INT_VALUE(ctx->k0)));
635 return fast_p(pht, x, y, k, ctx);
636 } else {
637 return slow_p(pht, x, y, k, ctx);
638 }
639 } else {
640 return fast_p(pht, x, y, k, ctx);
641 }
642 }
643 /*
644 since (probably) VS2008 or earlier won't do tail recursion optiomisation,
645 so this equal? implementation would cause stack overflow. to avoid it as
646 much as possible, we do some manual tail recursion optiomisation.
647 (using goto)
648 */
649 #if defined(_MSC_VER) && _MSC_VER <= 1500
650 # define FAST_ENTRY fast_entry:
651 # define SLOW_ENTRY slow_entry:
652 # define tail_eP(nx, ny, nk, ctx, fast_body, slow_body) \
653 do { \
654 /* change it */ \
655 x = (nx); \
656 y = (ny); \
657 k = (nk); \
658 if (SG_INT_VALUE(k) <= 0) { \
659 if ((k) == (ctx)->kb) { \
660 (k) = SG_MAKE_INT(random() % (2 * SG_INT_VALUE(ctx->k0))); \
661 fast_body; \
662 } else { \
663 slow_body; \
664 } \
665 } else { \
666 fast_body; \
667 } \
668 } while (0)
669 # define fast_tail_eP(pht, x, y, k, ctx) \
670 tail_eP(x, y, k, ctx, goto fast_entry, slow_p(pht, x, y, k, ctx))
671 # define slow_tail_eP(pht, x, y, k, ctx) \
672 tail_eP(x, y, k, ctx, fast_p(pht, x, y, k, ctx), goto slow_entry)
673 #else
674 # define FAST_ENTRY /* dummy */
675 # define SLOW_ENTRY /* dummy */
676 # define fast_tail_eP(pht, x, y, k, ctx) return eP(pht, x, y, k, ctx)
677 # define slow_tail_eP(pht, x, y, k, ctx) return eP(pht, x, y, k, ctx)
678 #endif
679
fast_p(SgHashTable ** pht,SgObject x,SgObject y,SgObject k,struct equal_context * ctx)680 SgObject fast_p(SgHashTable **pht, SgObject x, SgObject y,
681 SgObject k, struct equal_context *ctx)
682 {
683 FAST_ENTRY;
684 if (x == y) return k;
685 if (SG_PAIRP(x)) {
686 if (!SG_PAIRP(y)) {
687 return SG_FALSE;
688 }
689 k = eP(pht, SG_CAR(x), SG_CAR(y), k, ctx);
690 if (SG_FALSEP(k)) {
691 return SG_FALSE;
692 }
693 fast_tail_eP(pht, SG_CDR(x), SG_CDR(y), k, ctx);
694 }
695 if (SG_VECTORP(x)) {
696 if (!SG_VECTORP(y)) {
697 return SG_FALSE;
698 } else {
699 long sizex = SG_VECTOR_SIZE(x);
700 long sizey = SG_VECTOR_SIZE(y);
701 if (sizex != sizey) {
702 return SG_FALSE;
703 } else {
704 long i;
705 for (i = 0;; i++) {
706 if (i == sizex || SG_INT_VALUE(k) <= 0) {
707 return k;
708 } else {
709 k = eP(pht,
710 SG_VECTOR_ELEMENT(x, i),
711 SG_VECTOR_ELEMENT(y, i),
712 k, ctx);
713 if (SG_FALSEP(k)) {
714 return SG_FALSE;
715 }
716 }
717 }
718 }
719 }
720 }
721 if (SG_STRINGP(x)) {
722 if (!SG_STRING(y)) {
723 return SG_FALSE;
724 }
725 if (Sg_StringEqual(x, y)) {
726 return k;
727 } else {
728 return SG_FALSE;
729 }
730 }
731
732 if (SG_BVECTORP(x)) {
733 if (!SG_BVECTORP(y)) {
734 return SG_FALSE;
735 }
736 if (Sg_ByteVectorEqP(x, y)) {
737 return k;
738 } else {
739 return SG_FALSE;
740 }
741 }
742 /* Record inspection */
743 if (ctx->inspect_record_p) {
744 if (Sg_RecordP(x)) {
745 if (Sg_RecordP(y)) {
746 SgClass *xklass = Sg_ClassOf(x);
747 SgClass *yklass = Sg_ClassOf(y);
748 if (xklass != yklass) return SG_FALSE; /* obvious */
749 else {
750 SgSlotAccessor **xacc = xklass->gettersNSetters;
751 SgSlotAccessor **yacc = yklass->gettersNSetters;
752 for (; xacc && *xacc && yacc && *yacc; xacc++, yacc++) {
753 SgObject xe = Sg_SlotRefUsingAccessor(x, *xacc);
754 SgObject ye = Sg_SlotRefUsingAccessor(y, *yacc);
755 if (SG_UNBOUNDP(xe) || SG_UNBOUNDP(ye)) return SG_FALSE;
756 k = eP(pht, xe, ye, k, ctx);
757 if (SG_FALSEP(k)) return SG_FALSE;
758 }
759 return k;
760 }
761 }
762 return SG_FALSE;
763 }
764 }
765
766 if (eqv_internal(x, y, TRUE)) {
767 return k;
768 } else {
769 return SG_FALSE;
770 }
771 }
772
find(SgObject b)773 static SgObject find(SgObject b)
774 {
775 SgObject n;
776 ASSERT(SG_BOXP(b));
777 n = SG_BOX(b)->value;
778 if (SG_BOXP(n)) {
779 for (;;) {
780 SgObject nn = SG_BOX(n)->value;
781 if (SG_BOXP(nn)) {
782 SG_BOX(b)->value = nn;
783 b = n;
784 n = nn;
785 } else {
786 return n;
787 }
788 }
789 } else {
790 return b;
791 }
792 }
793
union_find(SgHashTable * ht,SgObject x,SgObject y,struct equal_context * ctx)794 static SgObject union_find(SgHashTable *ht, SgObject x, SgObject y,
795 struct equal_context *ctx)
796 {
797 SgObject bx = Sg_HashTableRef(ht, x, SG_FALSE);
798 SgObject by = Sg_HashTableRef(ht, y, SG_FALSE);
799 if (SG_FALSEP(bx)) {
800 if (SG_FALSEP(by)) {
801 SgObject b = make_box(SG_MAKE_INT(1));
802 Sg_HashTableSet(ht, x, b, 0);
803 Sg_HashTableSet(ht, y, b, 0);
804 return SG_FALSE;
805 } else {
806 SgObject ry = find(by);
807 Sg_HashTableSet(ht, x, ry, 0);
808 return SG_FALSE;
809 }
810 } else if (SG_FALSEP(by)) {
811 SgObject rx = find(bx);
812 Sg_HashTableSet(ht, y, rx, 0);
813 return SG_FALSE;
814 } else {
815 SgObject rx = find(bx);
816 SgObject ry = find(by);
817 SgObject nx, ny;
818 if (rx == ry) {
819 return SG_TRUE;
820 }
821 nx = SG_BOX(rx)->value;
822 ny = SG_BOX(ry)->value;
823 ASSERT(SG_INTP(nx));
824 ASSERT(SG_INTP(ny));
825 if (SG_INT_VALUE(nx) > SG_INT_VALUE(ny)) {
826 SG_BOX(ry)->value = rx;
827 SG_BOX(rx)->value = SG_MAKE_INT(SG_INT_VALUE(nx) + SG_INT_VALUE(ny));
828 return SG_FALSE;
829 } else {
830 SG_BOX(rx)->value = ry;
831 SG_BOX(ry)->value = SG_MAKE_INT(SG_INT_VALUE(ny) + SG_INT_VALUE(nx));
832 return SG_FALSE;
833 }
834 }
835 }
836
call_union_find(SgHashTable ** pht,SgObject x,SgObject y,struct equal_context * ctx)837 static SgObject call_union_find(SgHashTable **pht, SgObject x,
838 SgObject y, struct equal_context *ctx)
839 {
840 if (*pht == NULL) {
841 *pht = Sg_MakeHashTableSimple(SG_HASH_EQ, 0);
842 }
843 return union_find(*pht, x, y, ctx);
844 }
845
slow_p(SgHashTable ** pht,SgObject x,SgObject y,SgObject k,struct equal_context * ctx)846 SgObject slow_p(SgHashTable **pht, SgObject x, SgObject y,
847 SgObject k, struct equal_context *ctx)
848 {
849 SLOW_ENTRY;
850 if (x == y) return k;
851 if (SG_PAIRP(x)) {
852 if (!SG_PAIRP(y)) {
853 return SG_FALSE;
854 }
855 if (!SG_FALSEP(call_union_find(pht, x, y, ctx))) {
856 return SG_MAKE_INT(0);
857 } else {
858 ASSERT(SG_INTP(k));
859 k = eP(pht, SG_CAR(x), SG_CAR(y), k, ctx);
860 if (SG_FALSEP(k)) {
861 return SG_FALSE;
862 }
863 slow_tail_eP(pht, SG_CDR(x), SG_CDR(y), k, ctx);
864 }
865 }
866 if (SG_VECTORP(x)) {
867 long n = SG_VECTOR_SIZE(x);
868 long i;
869 if (!SG_VECTORP(y)) {
870 return SG_FALSE;
871 }
872 if (n != SG_VECTOR_SIZE(y)) {
873 return SG_FALSE;
874 }
875 if (!SG_FALSEP(call_union_find(pht, x, y, ctx))) {
876 return SG_MAKE_INT(0);
877 }
878 ASSERT(SG_INTP(k));
879 k = SG_MAKE_INT(SG_INT_VALUE(k) - 1);
880 for (i = 0;; i++) {
881 if (i == n) {
882 return k;
883 } else {
884 k = eP(pht,
885 SG_VECTOR_ELEMENT(x, i),
886 SG_VECTOR_ELEMENT(y, i),
887 k, ctx);
888 if (SG_FALSEP(k)) {
889 return SG_FALSE;
890 }
891 }
892 }
893 }
894 if (SG_STRINGP(x)) {
895 if (!SG_STRING(y)) {
896 return SG_FALSE;
897 }
898 if(Sg_StringEqual(x, y)) {
899 return k;
900 } else {
901 return SG_FALSE;
902 }
903 }
904 if (SG_BVECTORP(x)) {
905 if (!SG_BVECTORP(y)) {
906 return SG_FALSE;
907 }
908 if (Sg_ByteVectorEqP(x, y)) {
909 return k;
910 } else {
911 return SG_FALSE;
912 }
913 }
914 /* inspection */
915 if (ctx->inspect_record_p) {
916 if (Sg_RecordP(x)) {
917 if (Sg_RecordP(y)) {
918 SgClass *xklass = Sg_ClassOf(x);
919 SgClass *yklass = Sg_ClassOf(y);
920 if (xklass != yklass) return SG_FALSE; /* obvious */
921 if (!SG_FALSEP(call_union_find(pht, x, y, ctx))) {
922 return SG_MAKE_INT(0);
923 } else {
924 SgSlotAccessor **xacc = xklass->gettersNSetters;
925 SgSlotAccessor **yacc = yklass->gettersNSetters;
926 k = SG_MAKE_INT(SG_INT_VALUE(k) - 1);
927 for (; xacc && *xacc && yacc && *yacc; xacc++, yacc++) {
928 SgObject xe = Sg_SlotRefUsingAccessor(x, *xacc);
929 SgObject ye = Sg_SlotRefUsingAccessor(y, *yacc);
930 if (SG_INT_VALUE(k) <= 0) return k;
931 if (SG_UNBOUNDP(xe) || SG_UNBOUNDP(ye)) return SG_FALSE;
932 k = eP(pht, xe, ye, k, ctx);
933 if (SG_FALSEP(k)) return SG_FALSE;
934 }
935 return k;
936 }
937 }
938 return SG_FALSE;
939 }
940 }
941 if (eqv_internal(x, y, TRUE)) {
942 return k;
943 } else {
944 return SG_FALSE;
945 }
946 }
947
interleave_p(SgObject x,SgObject y,SgObject k,struct equal_context * ctx)948 static int interleave_p(SgObject x, SgObject y, SgObject k, struct equal_context *ctx)
949 {
950 SgHashTable *ht = NULL;
951 if (SG_FALSEP(eP(&ht, x, y, k, ctx))) {
952 return FALSE;
953 }
954 return TRUE;
955 }
956
957 /*
958 (define (precheck/interleave-equal? x y)
959 (let ((k (pre? x y k0)))
960 (and k (or (> k 0)) (interleave? x y 0))))
961 */
precheck_interleave_equal_p(SgObject x,SgObject y,struct equal_context * ctx)962 static int precheck_interleave_equal_p(SgObject x, SgObject y, struct equal_context *ctx)
963 {
964 SgObject k = pre_p(x, y, ctx->k0, ctx);
965 if (SG_FALSEP(k)) {
966 return FALSE;
967 }
968 ASSERT(SG_INTP(k));
969 if (SG_INT_VALUE(k) > 0) {
970 return TRUE;
971 }
972 return interleave_p(x, y, SG_MAKE_INT(0), ctx);
973 }
974
975 /*
976 (define (equal? x y)
977 (precheck/interleave-equal? x y))
978 */
Sg_EqualP(SgObject x,SgObject y)979 int Sg_EqualP(SgObject x, SgObject y)
980 {
981 struct equal_context ctx = {SG_MAKE_INT(400), SG_MAKE_INT(-40), TRUE};
982 return precheck_interleave_equal_p(x, y, &ctx);
983 }
984
r6rs_equalp(SgObject x,SgObject y)985 static int r6rs_equalp(SgObject x, SgObject y)
986 {
987 struct equal_context ctx = {SG_MAKE_INT(400), SG_MAKE_INT(-40), FALSE};
988 return precheck_interleave_equal_p(x, y, &ctx);
989 }
990
991
Sg_EqualM(SgObject x,SgObject y,int mode)992 int Sg_EqualM(SgObject x, SgObject y, int mode)
993 {
994 switch (mode) {
995 case SG_CMP_EQ:
996 return Sg_EqP(x, y);
997 case SG_CMP_EQV:
998 return Sg_EqvP(x, y);
999 case SG_CMP_EQUAL:
1000 return Sg_EqualP(x, y);
1001 }
1002 return FALSE;
1003 }
1004 /*
1005 end of file
1006 Local Variables:
1007 coding: utf-8-unix
1008 End:
1009 */
1010