Re: reverse dependency order?

[Dan Nicolaescu]

Tim Landscheidt <address@hidden> writes:

> Dan Nicolaescu <address@hidden> wrote some time ago:
>
>> I've run into situations where given:
>
>> foo: a b c
>
>> and "b" was missing a dependency on "a".
>
>> The above did not fail with parallel make for years because "a" finished
>> fast, before "b" actually needed to use it's result.
>
>> It might be interesting to have a make flag that would reverse the order
>> in which dependencies are considered, this will catch really fast
>> missing dependencies even when building with "make -j1".
>
>> Is something like that feasible?  Would it be easy to implement?
>
> I asked that exact question in 2012
> (http://permalink.gmane.org/gmane.comp.gnu.make.general/10601)
> and even then there had already been requests for that "in
> the past" :-).  I wrote a basic patch to reverse or random-
> ize the order
> (http://permalink.gmane.org/gmane.comp.gnu.make.general/10608),
> but I don't think it applies cleanly anymore.


I updated your patch to apply to the current git (see attached).
I've only tested it lightly, but it seems to work just fine.

Hopefully it can be considered for inclusion...

Thanks!

diff --git a/remake.c b/remake.c
index 1722474..f7b6256 100644
--- a/remake.c
+++ b/remake.c
@@ -24,6 +24,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
@@ -542,39 +545,58 @@ 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;
-
-      /* Find the deps we're scanning */
-      d = ad->file->deps;
-      ad = ad->next;
-
-      while (d)
+       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++);
+ 
+       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;
+ 
+       for (i = 0; i < depscount; i++)
         {
           enum update_status new;
           FILE_TIMESTAMP mtime;
           int maybe_make;
           int dontcare = 0;
 
-          check_renamed (d->file);
+         d = deps [i];
+
+         check_renamed (d->file);
 
           mtime = file_mtime (d->file);
           check_renamed (d->file);
 
           if (is_updating (d->file))
             {
+              struct dep **dp;
+
               OSS (error, NILF, _("Circular %s <- %s dependency dropped."),
                    file->name, d->file->name);
+             for (dp = &ad->file->deps; *dp != d; dp = &(*dp)->next);
+             *dp = d->next;
               /* 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;
               continue;
             }
 
@@ -622,10 +644,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.