New equality substitution.

If the equal method is defined for structs, its return
value is used in their place for hashing and comparison.

* eval.h (eq_s, eql_s, equal_s): Declared.

* hash.c (equal_hash): If a COBJ defines an equalsub
function, we call it. If it returns non-nil, we
take the object in its place and recurse.

* lib.c (equal): Refactored to support equality substitution.
(less): Support equality substitution.

* lib.h (cobj_ops): New function pointer member, equalsub.
Only struct instances define this, currently.
(cobj_ops_init): Add null entry to initializer for equalsub.
(cobj_ops_init_ex): New initialiation macro for
situations when the equalsub member must be provided.

* struct.c (struct struct_type): new member eqmslot.
(make_struct_type): Initialize emslot to zero.
(static_slot_set, static_slot_ensure): If eqmslot is -1,
indicating positive knowledge that there is no equal method
static slot, we must invalidate that with a zero: it is no
longer known whether there is or isn't such a slot.
(get_equal_method, struct_inst_equalsub): New static functions.
(struct_inst_ops): Initialize the equalsub member using
new cobj_ops_init_ex macro.

* txr.1: Document equality substitution.

1 files changed, 59 insertions, 2 deletions

diff --git a/txr.1 b/txr.1
index d6b128ef..067e9b85 100644
--- a/txr.1
+++ b/txr.1
@@ -13607,8 +13607,10 @@ The
 .code equal
 function is less strict still than
 .codn eql .
-In general, it recurses into some
-kinds of aggregate objects to perform a structural equivalence check.
+In general, it recurses into some kinds of aggregate objects to perform a
+structural equivalence check.  For struct types, it also supports customization
+via equality substitution.  See the Equality Substitution section under
+Structures.
 
 Firstly, if
 .meta left-obj
@@ -13830,6 +13832,15 @@ correct behavior when
 is regarded as an empty list, since the empty list is lexicographically prior to
 a nonempty list.
 
+If either argument is a structure for which the
+.code equal
+method is defined, the method is invoked on that argument, and the
+value returned is used in place of that argument for performing
+the comparison.  Structures with no
+.code equal
+method cannot participate in a comparison, resulting in an error.
+See the Equality Substitution section under Structures.
+
 Finally, if either of the arguments has a type other than the above discussed
 types, the situation is an error.
 
@@ -18201,6 +18212,47 @@ is evaluated only once:
   (mapcar s list)  <-->  (mapcar (meth s lambda) list)
 .cble
 
+.NP* Equality Substitution
+
+Normally, two struct values are not considered the same under the
+.code equal
+function unless they are the same objects.
+
+However, if a method named
+.code equal
+is defined for a structure type, via a static slot, then instances of
+that structure type support
+.IR "equality substitution" .
+
+The
+.code equal
+method must take exactly one argument: the structure object.
+Moreover, the method must never return
+.codn nil .
+
+When a struct which supports equality substitution is compared using
+.codn equal ,
+.codn less
+or
+.codn greater ,
+its
+.code equal
+method is invoked, and the return value is used in place of that
+structure for the purposes of the comparison.
+
+The same applies when an struct is hashed using the
+.code hash-equal
+function, or implicitly by an
+.code :equal-hash
+hash tables.
+
+Note: if an
+.code equal
+method is defined or redefined with different semantics for a struct
+type whose instances have already been inserted as keys in an
+.code :equal-based
+hash table, searches for those keys will not work reliably.
+
 .coNP Macro @ defstruct
 .synb
 .mets (defstruct >> { name | >> ( name << arg *)} < super
@@ -29473,6 +29525,11 @@ each produce the same integer hash value.  In all other
 circumstances, the hash values of two distinct objects are unrelated, and
 may or may not be the same.
 
+Object of struct type may support custom hashing by way of defining
+an equality substitution via an
+.code equal
+method. See the Equality Substitution section under Structures.
+
 .coNP Functions @, hash_keys @, hash_values @ hash_pairs and @ hash_alist
 .synb
 .mets (hash-keys << hash )