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 */