+\f
+
+/* List of nodes we've seen during substitute_object_in_subtree. */
+static Lisp_Object seen_list;
+
+static void
+substitute_object_in_subtree (object, placeholder)
+ Lisp_Object object;
+ Lisp_Object placeholder;
+{
+ Lisp_Object check_object;
+
+ /* We haven't seen any objects when we start. */
+ seen_list = Qnil;
+
+ /* Make all the substitutions. */
+ check_object
+ = substitute_object_recurse (object, placeholder, object);
+
+ /* Clear seen_list because we're done with it. */
+ seen_list = Qnil;
+
+ /* The returned object here is expected to always eq the
+ original. */
+ if (!EQ (check_object, object))
+ error ("Unexpected mutation error in reader");
+}
+
+/* Feval doesn't get called from here, so no gc protection is needed. */
+#define SUBSTITUTE(get_val, set_val) \
+{ \
+ Lisp_Object old_value = get_val; \
+ Lisp_Object true_value \
+ = substitute_object_recurse (object, placeholder,\
+ old_value); \
+ \
+ if (!EQ (old_value, true_value)) \
+ { \
+ set_val; \
+ } \
+}
+
+static Lisp_Object
+substitute_object_recurse (object, placeholder, subtree)
+ Lisp_Object object;
+ Lisp_Object placeholder;
+ Lisp_Object subtree;
+{
+ /* If we find the placeholder, return the target object. */
+ if (EQ (placeholder, subtree))
+ return object;
+
+ /* If we've been to this node before, don't explore it again. */
+ if (!EQ (Qnil, Fmemq (subtree, seen_list)))
+ return subtree;
+
+ /* If this node can be the entry point to a cycle, remember that
+ we've seen it. It can only be such an entry point if it was made
+ by #n=, which means that we can find it as a value in
+ read_objects. */
+ if (!EQ (Qnil, Frassq (subtree, read_objects)))
+ seen_list = Fcons (subtree, seen_list);
+
+ /* Recurse according to subtree's type.
+ Every branch must return a Lisp_Object. */
+ switch (XTYPE (subtree))
+ {
+ case Lisp_Vectorlike:
+ {
+ int i;
+ int length = Flength(subtree);
+ for (i = 0; i < length; i++)
+ {
+ Lisp_Object idx = make_number (i);
+ SUBSTITUTE (Faref (subtree, idx),
+ Faset (subtree, idx, true_value));
+ }
+ return subtree;
+ }
+
+ case Lisp_Cons:
+ {
+ SUBSTITUTE (Fcar_safe (subtree),
+ Fsetcar (subtree, true_value));
+ SUBSTITUTE (Fcdr_safe (subtree),
+ Fsetcdr (subtree, true_value));
+ return subtree;
+ }
+
+ case Lisp_String:
+ {
+ /* Check for text properties in each interval.
+ substitute_in_interval contains part of the logic. */
+
+ INTERVAL root_interval = XSTRING (subtree)->intervals;
+ Lisp_Object arg = Fcons (object, placeholder);
+
+ traverse_intervals (root_interval, 1, 0,
+ &substitute_in_interval, arg);
+
+ return subtree;
+ }
+
+ /* Other types don't recurse any further. */
+ default:
+ return subtree;
+ }
+}
+
+/* Helper function for substitute_object_recurse. */
+static void
+substitute_in_interval (interval, arg)
+ INTERVAL interval;
+ Lisp_Object arg;
+{
+ Lisp_Object object = Fcar (arg);
+ Lisp_Object placeholder = Fcdr (arg);
+
+ SUBSTITUTE(interval->plist, interval->plist = true_value);
+}
+