Re: Trigger missing dependencies by changing order of execution?

[Tim Landscheidt]

Paul Smith <address@hidden> wrote:

>> As in real-life scenarios there is seldomly a sleep 3 and
>> the bug will thus only show very randomly, I'm looking for a
>> way to smoke out such errors with a higher probability.  One
>> idea would be to reverse the order of execution for targets
>> "on the same level": As the test suite will usually trigger
>> first generation of a.out, then b.out, if instead first
>> b.out was generated, the bug would surface.

>>   Is there a way in GNU make to do this?

> No.  There have been requests for "randomized" prerequisite lists for
> this exact reason in the past, but nothing like this has ever been
> implemented.

> One issue is that you really can't "randomize" (or reverse) the first
> prerequisite as it has a special status (being the value of $<); if you
> randomize all prerequisites of all targets then most of your rules will
> fail.  So you have to special-case that one and only "randomize" the 2nd
> and subsequent prerequisites.

Why?  You don't have to change the order of the prerequi-
sites, only the order of their execution.  So $< will stay
untouched.

> The other issue is just that the way make is coded, it's not so easy to
> do this.

After several hours: I have noticed :-).  What do you think
of the attached patch?  (Imagine setting tl_randomize_deps/
tl_reverse_deps per command line option.)  I have tried com-
piling Bison and Emacs with tl_reverse_deps == 1, and it
worked.

  With both "options" set to false, the test suite passes
(including the circular tests), so it doesn't seem to intro-
duce regressions.  When the order of execution is changed,
some tests fail, but browsing through *.diff that seems to
be caused by the test suite expecting the "normal" order.

  I haven't looked deeper into GNU make's internals, so I
don't know how many side-effects this patch disables :-).

Tim

diff --git a/remake.c b/remake.c
index c58d3a5..fbef0c1 100644
--- a/remake.c
+++ b/remake.c
@@ -26,6 +26,9 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 #include <assert.h>
 
+#define tl_randomize_deps 0
+#define tl_reverse_deps   1
+
 #ifdef HAVE_FCNTL_H
 #include <fcntl.h>
 #else
@@ -510,21 +513,41 @@ update_file_1 (struct file *file, unsigned int depth)
 
   amake.file = file;
   amake.next = file->also_make;
-  ad = &amake;
-  while (ad)
+  for (ad = &amake; ad; ad = ad->next)
     {
-      struct dep *lastd = 0;
+      struct dep **deps, *di;
+      int depscount, i;
+
+      /* Short-cut if there are no dependencies to scan. */
+      if (!ad->file->deps)
+        continue;
+
+      /* Count the number of dependencies. */
+      for (di = ad->file->deps, depscount = 0; di; di = di->next, depscount++);
 
-      /* Find the deps we're scanning */
-      d = ad->file->deps;
-      ad = ad->next;
+      deps = calloc (depscount, sizeof (**deps));   /* Must be initialized to 
NULLs for tl_randomize_deps. */
+      assert (deps != 0);   /* TODO: Replace with some error handling. */
+      for (di = ad->file->deps, i = tl_reverse_deps ? depscount : 0; di; di = 
di->next)
+        if (tl_randomize_deps)
+          {
+            srand (time (NULL));   /* TODO: Move to global initialization. */
+            while (deps [i = rand () % depscount]);   /* Find an free element. 
*/
+            deps [i] = di;
+          }
+        else
+          if (tl_reverse_deps)
+            deps [--i] = di;
+          else
+            deps [i++] = di;
 
-      while (d)
+      for (i = 0; i < depscount; i++)
         {
           FILE_TIMESTAMP mtime;
           int maybe_make;
           int dontcare = 0;
 
+          d = deps [i];
+
           check_renamed (d->file);
 
           mtime = file_mtime (d->file);
@@ -532,16 +555,15 @@ update_file_1 (struct file *file, unsigned int depth)
 
           if (is_updating (d->file))
             {
+              struct dep **dp;
+
               error (NILF, _("Circular %s <- %s dependency dropped."),
                      file->name, d->file->name);
               /* We cannot free D here because our the caller will still have
                  a reference to it when we were called recursively via
                  check_dep below.  */
-              if (lastd == 0)
-                file->deps = d->next;
-              else
-                lastd->next = d->next;
-              d = d->next;
+              for (dp = &ad->file->deps; *dp != d; dp = &(*dp)->next);
+              *dp = d->next;
               continue;
             }
 
@@ -587,10 +609,8 @@ update_file_1 (struct file *file, unsigned int depth)
                it was built, OR it doesn't exist.  */
             d->changed = ((file_mtime (d->file) != mtime)
                           || (mtime == NONEXISTENT_MTIME));
-
-          lastd = d;
-          d = d->next;
         }
+      free (deps);
     }
 
   /* Now we know whether this target needs updating.