ceph/src/boost/tools/build/src/engine/modules/order.cpp

   1 /* Copyright 2004. Vladimir Prus
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE.txt or copy at
   4  * https://www.bfgroup.xyz/b2/LICENSE.txt)
   5  */
   6
   7 #include "../lists.h"
   8 #include "../mem.h"
   9 #include "../native.h"
  10 #include "../object.h"
  11 #include "../jam_strings.h"
  12 #include "../variable.h"
  13
  14
  15 /* Use quite klugy approach: when we add order dependency from 'a' to 'b', just
  16  * append 'b' to of value of variable 'a'.
  17  */
  18 LIST * add_pair( FRAME * frame, int32_t flags )
  19 {
  20     LIST * arg = lol_get( frame->args, 0 );
  21     LISTITER iter = list_begin( arg );
  22     LISTITER const end = list_end( arg );
  23     var_set( frame->module, list_item( iter ), list_copy_range( arg, list_next(
  24         iter ), end ), VAR_APPEND );
  25     return L0;
  26 }
  27
  28
  29 /* Given a list and a value, returns position of that value in the list, or -1
  30  * if not found.
  31  */
  32 int32_t list_index( LIST * list, OBJECT * value )
  33 {
  34     int32_t result = 0;
  35     LISTITER iter = list_begin( list );
  36     LISTITER const end = list_end( list );
  37     for ( ; iter != end; iter = list_next( iter ), ++result )
  38         if ( object_equal( list_item( iter ), value ) )
  39             return result;
  40     return -1;
  41 }
  42
  43 enum colors { white, gray, black };
  44
  45
  46 /* Main routine for topological sort. Calls itself recursively on all adjacent
  47  * vertices which were not yet visited. After that, 'current_vertex' is added to
  48  * '*result_ptr'.
  49  */
  50 void do_ts( int32_t * * graph, int32_t current_vertex, int32_t * colors, int32_t * * result_ptr
  51     )
  52 {
  53     int32_t i;
  54
  55     colors[ current_vertex ] = gray;
  56     for ( i = 0; graph[ current_vertex ][ i ] != -1; ++i )
  57     {
  58         int32_t adjacent_vertex = graph[ current_vertex ][ i ];
  59         if ( colors[ adjacent_vertex ] == white )
  60             do_ts( graph, adjacent_vertex, colors, result_ptr );
  61         /* The vertex is either black, in which case we do not have to do
  62          * anything, or gray, in which case we have a loop. If we have a loop,
  63          * it is not clear what useful diagnostic we can emit, so we emit
  64          * nothing.
  65          */
  66     }
  67     colors[ current_vertex ] = black;
  68     **result_ptr = current_vertex;
  69     ( *result_ptr )++;
  70 }
  71
  72
  73 static void topological_sort( int32_t * * graph, int32_t num_vertices, int32_t * result )
  74 {
  75     int32_t i;
  76     int32_t * colors = ( int32_t * )BJAM_CALLOC( num_vertices, sizeof( int32_t ) );
  77     for ( i = 0; i < num_vertices; ++i )
  78         colors[ i ] = white;
  79
  80     for ( i = num_vertices - 1; i >= 0; --i )
  81         if ( colors[ i ] == white )
  82             do_ts( graph, i, colors, &result );
  83
  84     BJAM_FREE( colors );
  85 }
  86
  87
  88 LIST * order( FRAME * frame, int32_t flags )
  89 {
  90     LIST * arg = lol_get( frame->args, 0 );
  91     LIST * result = L0;
  92     int32_t src;
  93     LISTITER iter = list_begin( arg );
  94     LISTITER const end = list_end( arg );
  95
  96     /* We need to create a graph of order dependencies between the passed
  97      * objects. We assume there are no duplicates passed to 'add_pair'.
  98      */
  99     int32_t length = list_length( arg );
 100     int32_t * * graph = ( int32_t * * )BJAM_CALLOC( length, sizeof( int32_t * ) );
 101     int32_t * order = ( int32_t * )BJAM_MALLOC( ( length + 1 ) * sizeof( int32_t ) );
 102
 103     for ( src = 0; iter != end; iter = list_next( iter ), ++src )
 104     {
 105         /* For all objects this one depends upon, add elements to 'graph'. */
 106         LIST * dependencies = var_get( frame->module, list_item( iter ) );
 107         int32_t index = 0;
 108         LISTITER dep_iter = list_begin( dependencies );
 109         LISTITER const dep_end = list_end( dependencies );
 110
 111         graph[ src ] = ( int32_t * )BJAM_CALLOC( list_length( dependencies ) + 1,
 112             sizeof( int32_t ) );
 113         for ( ; dep_iter != dep_end; dep_iter = list_next( dep_iter ) )
 114         {
 115             int32_t const dst = list_index( arg, list_item( dep_iter ) );
 116             if ( dst != -1 )
 117                 graph[ src ][ index++ ] = dst;
 118         }
 119         graph[ src ][ index ] = -1;
 120     }
 121
 122     topological_sort( graph, length, order );
 123
 124     {
 125         int32_t index = length - 1;
 126         for ( ; index >= 0; --index )
 127         {
 128             int32_t i;
 129             LISTITER iter = list_begin( arg );
 130             for ( i = 0; i < order[ index ]; ++i, iter = list_next( iter ) );
 131             result = list_push_back( result, object_copy( list_item( iter ) ) );
 132         }
 133     }
 134
 135     /* Clean up */
 136     {
 137         int32_t i;
 138         for ( i = 0; i < length; ++i )
 139             BJAM_FREE( graph[ i ] );
 140         BJAM_FREE( graph );
 141         BJAM_FREE( order );
 142     }
 143
 144     return result;
 145 }
 146
 147
 148 void init_order()
 149 {
 150     {
 151         char const * args[] = { "first", "second", 0 };
 152         declare_native_rule( "class@order", "add-pair", args, add_pair, 1 );
 153     }
 154
 155     {
 156         char const * args[] = { "objects", "*", 0 };
 157         declare_native_rule( "class@order", "order", args, order, 1 );
 158     }
 159 }