structs: deal with initialization diamond problem.

Until now it has been documented that if a struct type
inherits a supertype two or more times, then the supertype
initialization occurs that many times.

This change fixes the behavior: bases are initialized once.

* struct.c (struct struct_type): New members, ndsupers, dsus
providing a flat array for tracking duplicate supertypes.
(get_all_supers, get_duplicate_supers): New static functions.
(make_struct_type): Calculate the duplicate supers, and store
them in the dsus array. Under 242 or lower compat mode,
pretend there are duplicates, which defeats the duplicate
detecting mechanism
(struct_type_destroy): Free the dsus array.
(call_inittfun_chain, call_postinitfun_chain): Take new
arguments: the root type from which the recursion started, and
a stack-allocated bit vector indicating which duplicate bases
have already been initialized. If the given type appears in
the duplicate bases list of the root type, and its bit is
already set, then skip all initialization for it. Otherwise
set its bit and proceed.
(alloc_seen, clear_seen): New macros to help with allocating
the bitvector of duplicate bases.
(make_struct_impl, lazy_struct_init, reset_struct): Use
alloc_seen and clear_seen macros to manage the bitvector of
duplicate bases for calling call_initfun_chain and
call_postinitfun_chain.

* txr.1: Updated doc with new paragraph about duplicated
supertypes, and compat note added.

1 files changed, 89 insertions, 2 deletions

diff --git a/txr.1 b/txr.1
index dea21da5..3d4c645b 100644
--- a/txr.1
+++ b/txr.1
@@ -26248,8 +26248,80 @@ methods are similarly invoked in right-to-left order, before the
 .code :postinit
 methods of the new type itself.
 Thus the order is: supertype inits, own inits, supertype post-inits,
-own post-inits.  If a supertype is referenced, directly or indirectly, two or
-more times, then its initializing expressions are evaluated that many times.
+own post-inits.
+
+.NP* Duplicate Supertypes
+Multiple inheritance makes it possible for a type to inherit the
+same supertype more than once, either directly (by naming it more than
+once as a direct supertype) or indirectly (by inheriting two or
+more different types, which have a common ancestor).
+The latter situation is sometimes referred to as the
+.IR "diamond problem" .
+
+Until \*(TX 242, the situation of duplicate supertypes was
+ignored for the purposes of object initialization. It was documented that if a
+supertype is referenced by inheritance, directly or indirectly, two or more
+times, then its initializing expressions are evaluated that many times.
+
+Starting in \*(TX 243, duplicate supertypes no longer give rise to duplicate
+initialization. When an object is instantiated, only one initialization of a
+duplicated supertype occurs. The subsequent initializations that would take
+place in the absence of duplicate detection are suppressed.
+
+.TP* Examples:
+
+Consider following program:
+
+.verb
+  (defstruct base ()
+    (:init (me) (put-line "base init")))
+
+  (defstruct d1 (base)
+    (:init (me) (put-line "d1 init")))
+
+  (defstruct d2 (base)
+    (:init (me) (put-line "d2 init")))
+
+  (defstruct s (d1 d2))
+
+  (new s)
+.brev
+
+Under \*(TX 242, and earlier versions that support multiple inheritance, it
+produces the output:
+
+.verb
+  base init
+  d2 init
+  base init
+  d1 init
+.brev
+
+The supertypes are initialized in a right-to-left traversal of the
+type lattice, without regard for
+.code base
+being duplicated.
+
+Starting with \*(TX 243, the output is:
+
+.verb
+  base init
+  d2 init
+  d1 init
+.brev
+
+The rightmost duplicate of the base is initialized, so that the initialization
+is complete prior to the initializations of any dependent types.
+
+Note, however, that the
+.code derived
+function function mechanism is not required to detect duplicated direct
+supertypes.
+If a supertype implements the
+.code derived
+function to detect situations when it is the target of inheritance,
+and some subtype inherits that type more than once, that function
+may be called more than once. The behavior is unspecified.
 
 .NP* Dirty Flags
 All structure instances contain a Boolean flag called the
@@ -29367,6 +29439,13 @@ The function is not retroactively invoked. If it is defined for
 a structure type from which subtypes have already been derived,
 it is not invoked for those existing subtypes.
 
+If
+.meta derived
+directly inherits
+.meta supertype
+more than once, it is not specified whether this function is called
+once, or multiple times.
+
 Note: the
 .meta supertype
 parameter exists because the
@@ -75262,6 +75341,14 @@ Compatibility values of 237 or lower restore the destructive behavior of the
 and
 .code shuffle
 functions.
+.IP 242
+In \*(TX 242 and older, the instantiation of an object whose type inherits
+from the same supertype more than once resulted in duplicate execution
+of the supertype's initialization. This was a documented behavior.
+After 242, duplicate initialization is suppressed. For more information, see
+the section
+.BR "Duplicate Supertypes" . A compatibility value of 242 or lower restores
+the duplicate initialization behavior.
 .IP 234
 In \*(TX 234 and older versions, the exception throwing functions
 .code throw