[Boost-commit] svn:boost r78287 - trunk/tools/build/v2/engine

Subject: [Boost-commit] svn:boost r78287 - trunk/tools/build/v2/engine
From: steven_at_[hidden]
Date: 2012-05-01 02:45:40

Author: steven_watanabe
Date: 2012-05-01 02:45:35 EDT (Tue, 01 May 2012)
New Revision: 78287
URL: http://svn.boost.org/trac/boost/changeset/78287

Log:
Replace ad hoc (incorrect) cycle detection code with a variation of Tarjan's algorithm.
Text files modified: 
   trunk/tools/build/v2/engine/builtins.c |     9 ++                                      
   trunk/tools/build/v2/engine/make.c     |    61 +++++++++++++++++-                      
   trunk/tools/build/v2/engine/make.h     |     2                                         
   trunk/tools/build/v2/engine/make1.c    |   130 +++------------------------------------ 
   trunk/tools/build/v2/engine/rules.h    |     5                                         
   5 files changed, 77 insertions(+), 130 deletions(-)

Modified: trunk/tools/build/v2/engine/builtins.c
==============================================================================
--- trunk/tools/build/v2/engine/builtins.c	(original)
+++ trunk/tools/build/v2/engine/builtins.c	2012-05-01 02:45:35 EDT (Tue, 01 May 2012)
@@ -509,7 +509,14 @@
     for ( ; iter != end; iter = list_next( iter ) )
     {
         TARGET * s = bindtarget( list_item( iter ) );
-        s->dependants = targetlist( s->dependants, targets );
+        if ( flags )
+        {
+            LISTITER t_iter = list_begin( targets ), t_end = list_end( targets );
+            for ( ; t_iter != t_end; t_iter = list_next( t_iter ) )
+                s->dependants = targetentry( s->dependants, bindtarget( list_item( t_iter ) )->includes );
+        }
+        else
+            s->dependants = targetlist( s->dependants, targets );
     }
 
     return L0;

Modified: trunk/tools/build/v2/engine/make.c
==============================================================================
--- trunk/tools/build/v2/engine/make.c	(original)
+++ trunk/tools/build/v2/engine/make.c	2012-05-01 02:45:35 EDT (Tue, 01 May 2012)
@@ -129,7 +129,7 @@
         {
             TARGET * t = bindtarget( list_item( iter ) );
             if ( t->fate == T_FATE_INIT )
-                make0( t, 0, 0, counts, anyhow );
+                make0( t, 0, 0, counts, anyhow, 0 );
         }
         PROFILE_EXIT( MAKE_MAKE0 );
     }
@@ -240,6 +240,48 @@
 }
 
 
+int make0rescan( TARGET * t, TARGET * rescanning )
+{
+    int result = 0;
+    TARGETS * c;
+    /* Check whether we've already found a cycle. */
+    if( target_scc( t ) == rescanning )
+    {
+        return 1;
+    }
+    /* If we've already visited this node, ignore it. */
+    if ( t->rescanning == rescanning )
+        return 0;
+
+    /* If t is already updated, ignore it. */
+    if ( t->scc_root == NULL &&
+        t->progress != T_MAKE_INIT &&
+        t->progress != T_MAKE_ONSTACK &&
+        t->progress != T_MAKE_ACTIVE )
+        return 0;
+
+    t->rescanning = rescanning;
+    for ( c = t->depends; c; c = c->next )
+    {
+        TARGET * dependency = c->target;
+        /* Always start at the root of each new strongly connected component. */
+        if ( target_scc( dependency ) != target_scc( t ) )
+            dependency = target_scc( dependency );
+        result |= make0rescan( dependency, rescanning );
+
+        /* Make sure that we pick up the new include node. */
+        if ( c->target->includes == rescanning )
+            result = 1;
+    }
+    if ( result && t->scc_root == NULL )
+    {
+        t->scc_root = rescanning;
+        rescanning->depends = targetentry( rescanning->depends, t );
+    }
+    return result;
+}
+
+
 /*
  * make0() - bind and scan everything to make a TARGET.
  *
@@ -253,7 +295,8 @@
     TARGET * p,       /* parent */
     int      depth,   /* for display purposes */
     COUNTS * counts,  /* for reporting */
-    int      anyhow
+    int      anyhow,
+    TARGET * rescanning
 )  /* forcibly touch all (real) targets */
 {
     TARGETS    * c;
@@ -303,7 +346,11 @@
          * depending on us will depend on that other target as well.
          */
         if ( another_target )
-            t->depends = targetentry( t->depends, bindtarget( another_target ) );
+        {
+            TARGET * other = bindtarget( another_target );
+            t->depends = targetentry( t->depends, other );
+            other->dependants = targetentry( other->dependants, t );
+        }
 
         t->binding = t->time ? T_BIND_EXISTS : T_BIND_MISSING;
     }
@@ -380,14 +427,18 @@
          * other alot.
          */
         if ( c->target->fate == T_FATE_INIT )
-            make0( c->target, ptime, depth + 1, counts, anyhow );
+            make0( c->target, ptime, depth + 1, counts, anyhow, rescanning );
         else if ( c->target->fate == T_FATE_MAKING && !internal )
             printf( "warning: %s depends on itself\n", object_str( c->target->name ) );
+        else if ( c->target->fate != T_FATE_MAKING && rescanning )
+            make0rescan( c->target, rescanning );
+        if ( rescanning && c->target->includes && c->target->includes->fate != T_FATE_MAKING )
+            make0rescan( target_scc( c->target->includes ), rescanning );
     }
 
     /* Step 3b: recursively make0() internal includes node. */
     if ( t->includes )
-        make0( t->includes, p, depth + 1, counts, anyhow );
+        make0( t->includes, p, depth + 1, counts, anyhow, rescanning );
 
     /* Step 3c: add dependencies' includes to our direct dependencies. */
     {

Modified: trunk/tools/build/v2/engine/make.h
==============================================================================
--- trunk/tools/build/v2/engine/make.h	(original)
+++ trunk/tools/build/v2/engine/make.h	2012-05-01 02:45:35 EDT (Tue, 01 May 2012)
@@ -28,7 +28,7 @@
 
 
 void make0( TARGET *t, TARGET  *p, int depth,
-            COUNTS *counts, int anyhow );
+            COUNTS *counts, int anyhow, TARGET * rescanning );
 
 
 /*

Modified: trunk/tools/build/v2/engine/make1.c
==============================================================================
--- trunk/tools/build/v2/engine/make1.c	(original)
+++ trunk/tools/build/v2/engine/make1.c	2012-05-01 02:45:35 EDT (Tue, 01 May 2012)
@@ -87,8 +87,6 @@
     int made;
 } counts[ 1 ] ;
 
-int handling_rescan;
-
 /* Target state - remove recursive calls by just keeping track of state target
  * is in.
  */
@@ -101,8 +99,7 @@
 #define T_STATE_MAKE1ATAIL 1   /* make1atail() should be called */
 #define T_STATE_MAKE1B     2   /* make1b() should be called */
 #define T_STATE_MAKE1C     3   /* make1c() should be called */
-#define T_STATE_MAKE1CTAIL 4   /* make1ctail() should be called */
-#define T_STATE_MAKE1D     5   /* make1d() should be called */
+#define T_STATE_MAKE1D     4   /* make1d() should be called */
     int             curstate;  /* current state */
     int             status;
 } state;
@@ -111,7 +108,6 @@
 static void make1atail  ( state * );
 static void make1b      ( state * );
 static void make1c      ( state * );
-static void make1ctail  ( state * );
 static void make1d      ( state * );
 static void make_closure( void * closure, int status, timing_info *, const char *, const char * );
 
@@ -233,7 +229,6 @@
                 case T_STATE_MAKE1ATAIL: make1atail( pState ); break;
                 case T_STATE_MAKE1B    : make1b    ( pState ); break;
                 case T_STATE_MAKE1C    : make1c    ( pState ); break;
-                case T_STATE_MAKE1CTAIL: make1ctail( pState ); break;
                 case T_STATE_MAKE1D    : make1d    ( pState ); break;
             }
         }
@@ -284,28 +279,19 @@
      */
     if ( pState->parent )
     {
-        TARGET * cycle_root;
         switch ( t->progress )
         {
             case T_MAKE_ONSTACK:
-                if ( t->depth == handling_rescan )
-                {
-                    if ( target_scc( pState->parent ) != scc_root )
-                        make1breakcycle( pState->parent, t );
-                    break;
-                }
             case T_MAKE_ACTIVE:
-                if ( handling_rescan && ( cycle_root = make1findcycle( t ) ) )
-                {
-                    make1breakcycle( pState->parent, cycle_root ); break;
-                }
             case T_MAKE_INIT:
             case T_MAKE_RUNNING:
-                if( t != pState->parent )
                 {
-                    t->parents = targetentry( t->parents,
-                        pState->parent );
-                    ++pState->parent->asynccnt;
+                    TARGET * parent_scc = target_scc( pState->parent );
+                    if( t != parent_scc )
+                    {
+                        t->parents = targetentry( t->parents, parent_scc );
+                        ++parent_scc->asynccnt;
+                    }
                 }
         }
     }
@@ -338,18 +324,8 @@
      */
     t->asynccnt = 1;
 
-    /* Add header nodes created during the building process. */
-    {
-        TARGETS * inc = 0;
-        for ( c = t->depends; c; c = c->next )
-            if ( c->target->rescanned && c->target->includes )
-                inc = targetentry( inc, c->target->includes );
-        t->depends = targetchain( t->depends, inc );
-    }
-
     /* Guard against circular dependencies. */
     t->progress = T_MAKE_ONSTACK;
-    t->depth = handling_rescan;
 
     {
         stack temp_stack = { NULL };
@@ -644,12 +620,12 @@
                      * target is built, otherwise the parent would be considered
                      * built before this make1a() processing has even started.
                      */
-                    make0( t->includes, t->parents->target, 0, 0, 0 );
+                    make0( t->includes, t->parents->target, 0, 0, 0, t->includes );
                     /* Link the old includes on to make sure that it gets
                      * cleaned up correctly.
                      */
                     t->includes->includes = saved_includes;
-                    for ( c = t->parents; c; c = c->next )
+                    for ( c = t->dependants; c; c = c->next )
                         c->target->depends = targetentry( c->target->depends,
                                                           t->includes );
                     /* Will be processed below. */
@@ -662,16 +638,13 @@
             }
 
             if ( additional_includes )
-            {
-                ++handling_rescan;
                 for ( c = t->parents; c; c = c->next )
                     push_state( &temp_stack, additional_includes, c->target, T_STATE_MAKE1A );
-                push_state( &temp_stack, additional_includes, NULL, T_STATE_MAKE1CTAIL );
-            }
 
             if ( t->scc_root )
             {
                 TARGET * scc_root = target_scc( t );
+                assert( scc_root->progress < T_MAKE_DONE );
                 for ( c = t->parents; c; c = c->next )
                 {
                     if ( target_scc( c->target ) == scc_root )
@@ -724,12 +697,6 @@
     }
 }
 
-static void make1ctail( state * pState )
-{
-    --handling_rescan;
-    pop_state( &state_stack );
-}
-
 
 /*
  * call_timing_rule() - Look up the __TIMING_RULE__ variable on the given
@@ -1217,80 +1184,3 @@
     t->binding = t->time ? T_BIND_EXISTS : T_BIND_MISSING;
     popsettings( root_module(), t->settings );
 }
-
-
-static void make1cyclenode( TARGET * t, TARGET * scc_root )
-{
-    /* if we intersect with another cycle we need to merge the two */
-    if ( t->scc_root )
-    {
-        TARGET * other_root = target_scc( t );
-        if ( other_root != scc_root )
-        {
-            other_root->scc_root = scc_root;
-            other_root->parents = targetentry( other_root->parents, scc_root );
-            ++scc_root->asynccnt;
-        }
-    }
-    if ( t != scc_root )
-        t->scc_root = scc_root;
-}
-
-
-static TARGET * make1findcycle_impl( TARGET * t, TARGET * scc_root )
-{
-    TARGETS * c;
-    TARGET * result;
-
-    if ( t->progress == T_MAKE_ONSTACK )
-        if ( t->depth == handling_rescan )
-            return t;
-        else
-            t->progress = T_MAKE_FINDCYCLE_ONSTACK;
-    else if ( t->progress == T_MAKE_ACTIVE )
-        t->progress = T_MAKE_FINDCYCLE_ACTIVE;
-    else
-        return 0;
-
-
-    for ( c = t->depends; c; c = c->next )
-        if ( ( result = make1findcycle_impl( c->target, scc_root ) ) )
-        {
-            make1cyclenode( c->target, scc_root );
-            return result;
-        }
-
-    return 0;
-}
-
-static void make1findcycle_cleanup( TARGET * t )
-{
-    TARGETS * c;
-
-    if ( t->progress == T_MAKE_FINDCYCLE_ACTIVE )
-        t->progress = T_MAKE_ACTIVE;
-    else if ( t->progress == T_MAKE_FINDCYCLE_ONSTACK )
-        t->progress = T_MAKE_ONSTACK;
-    else
-        return;
-
-    for ( c = t->depends; c; c = c->next )
-        make1findcycle_cleanup( c->target );
-}
-
-static TARGET * make1findcycle( TARGET * t )
-{
-    TARGET * result = make1findcycle_impl( t, target_scc( t ) );
-    make1findcycle_cleanup( t );
-    return result;
-}
-
-static void make1breakcycle( TARGET * t, TARGET * cycle_root )
-{
-    TARGET * scc_root = target_scc( cycle_root );
-    while ( t != cycle_root )
-    {
-        make1cyclenode( t, scc_root );
-        t = t->parents->target;
-    }
-}

Modified: trunk/tools/build/v2/engine/rules.h
==============================================================================
--- trunk/tools/build/v2/engine/rules.h	(original)
+++ trunk/tools/build/v2/engine/rules.h	2012-05-01 02:45:35 EDT (Tue, 01 May 2012)
@@ -212,8 +212,6 @@
 #define T_MAKE_RUNNING        3       /* make1(target) running commands */
 #define T_MAKE_DONE           4       /* make1(target) done */
 #define T_MAKE_NOEXEC_DONE    5       /* make1(target) done with -n in effect */
-#define T_MAKE_FINDCYCLE_ONSTACK  6   /* make1(target) searching for cyclic includes after */
-#define T_MAKE_FINDCYCLE_ACTIVE   7   /* rescanning a generated file. */
 
 #ifdef OPT_SEMAPHORE
     #define T_MAKE_SEMAPHORE  5       /* Special target type for semaphores */
@@ -227,7 +225,8 @@
 
     int        asynccnt;              /* child deps outstanding */
     TARGETS  * parents;               /* used by make1() for completion */
-    TARGET   * scc_root;              /* used by make1 to resolve cyclic includes */
+    TARGET   * scc_root;              /* used by make to resolve cyclic includes */
+    TARGET   * rescanning;            /* used by make0 to mark visited targets when rescanning */
     int        depth;                 /* The depth of the target in the make0 stack. */
     char     * cmds;                  /* type-punned command list */