1 files changed, 159 insertions, 0 deletions
diff --git a/src/boost/tools/build/src/engine/modules/order.cpp b/src/boost/tools/build/src/engine/modules/order.cpp
new file mode 100644
index 000000000..38209b889
--- /dev/null
+++ b/src/boost/tools/build/src/engine/modules/order.cpp
@@ -0,0 +1,159 @@
+/* Copyright 2004. Vladimir Prus
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at
+ * http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#include "../lists.h"
+#include "../mem.h"
+#include "../native.h"
+#include "../object.h"
+#include "../jam_strings.h"
+#include "../variable.h"
+
+
+/* Use quite klugy approach: when we add order dependency from 'a' to 'b', just
+ * append 'b' to of value of variable 'a'.
+ */
+LIST * add_pair( FRAME * frame, int flags )
+{
+    LIST * arg = lol_get( frame->args, 0 );
+    LISTITER iter = list_begin( arg );
+    LISTITER const end = list_end( arg );
+    var_set( frame->module, list_item( iter ), list_copy_range( arg, list_next(
+        iter ), end ), VAR_APPEND );
+    return L0;
+}
+
+
+/* Given a list and a value, returns position of that value in the list, or -1
+ * if not found.
+ */
+int list_index( LIST * list, OBJECT * value )
+{
+    int result = 0;
+    LISTITER iter = list_begin( list );
+    LISTITER const end = list_end( list );
+    for ( ; iter != end; iter = list_next( iter ), ++result )
+        if ( object_equal( list_item( iter ), value ) )
+            return result;
+    return -1;
+}
+
+enum colors { white, gray, black };
+
+
+/* Main routine for topological sort. Calls itself recursively on all adjacent
+ * vertices which were not yet visited. After that, 'current_vertex' is added to
+ * '*result_ptr'.
+ */
+void do_ts( int * * graph, int current_vertex, int * colors, int * * result_ptr
+    )
+{
+    int i;
+
+    colors[ current_vertex ] = gray;
+    for ( i = 0; graph[ current_vertex ][ i ] != -1; ++i )
+    {
+        int adjacent_vertex = graph[ current_vertex ][ i ];
+        if ( colors[ adjacent_vertex ] == white )
+            do_ts( graph, adjacent_vertex, colors, result_ptr );
+        /* The vertex is either black, in which case we do not have to do
+         * anything, or gray, in which case we have a loop. If we have a loop,
+         * it is not clear what useful diagnostic we can emit, so we emit
+         * nothing.
+         */
+    }
+    colors[ current_vertex ] = black;
+    **result_ptr = current_vertex;
+    ( *result_ptr )++;
+}
+
+
+void topological_sort( int * * graph, int num_vertices, int * result )
+{
+    int i;
+    int * colors = ( int * )BJAM_CALLOC( num_vertices, sizeof( int ) );
+    for ( i = 0; i < num_vertices; ++i )
+        colors[ i ] = white;
+
+    for ( i = num_vertices - 1; i >= 0; --i )
+        if ( colors[ i ] == white )
+            do_ts( graph, i, colors, &result );
+
+    BJAM_FREE( colors );
+}
+
+
+LIST * order( FRAME * frame, int flags )
+{
+    LIST * arg = lol_get( frame->args, 0 );
+    LIST * result = L0;
+    int src;
+    LISTITER iter = list_begin( arg );
+    LISTITER const end = list_end( arg );
+
+    /* We need to create a graph of order dependencies between the passed
+     * objects. We assume there are no duplicates passed to 'add_pair'.
+     */
+    int length = list_length( arg );
+    int * * graph = ( int * * )BJAM_CALLOC( length, sizeof( int * ) );
+    int * order = ( int * )BJAM_MALLOC( ( length + 1 ) * sizeof( int ) );
+
+    for ( src = 0; iter != end; iter = list_next( iter ), ++src )
+    {
+        /* For all objects this one depends upon, add elements to 'graph'. */
+        LIST * dependencies = var_get( frame->module, list_item( iter ) );
+        int index = 0;
+        LISTITER dep_iter = list_begin( dependencies );
+        LISTITER const dep_end = list_end( dependencies );
+
+        graph[ src ] = ( int * )BJAM_CALLOC( list_length( dependencies ) + 1,
+            sizeof( int ) );
+        for ( ; dep_iter != dep_end; dep_iter = list_next( dep_iter ) )
+        {
+            int const dst = list_index( arg, list_item( dep_iter ) );
+            if ( dst != -1 )
+                graph[ src ][ index++ ] = dst;
+        }
+        graph[ src ][ index ] = -1;
+    }
+
+    topological_sort( graph, length, order );
+
+    {
+        int index = length - 1;
+        for ( ; index >= 0; --index )
+        {
+            int i;
+            LISTITER iter = list_begin( arg );
+            for ( i = 0; i < order[ index ]; ++i, iter = list_next( iter ) );
+            result = list_push_back( result, object_copy( list_item( iter ) ) );
+        }
+    }
+
+    /* Clean up */
+    {
+        int i;
+        for ( i = 0; i < length; ++i )
+            BJAM_FREE( graph[ i ] );
+        BJAM_FREE( graph );
+        BJAM_FREE( order );
+    }
+
+    return result;
+}
+
+
+void init_order()
+{
+    {
+        char const * args[] = { "first", "second", 0 };
+        declare_native_rule( "class@order", "add-pair", args, add_pair, 1 );
+    }
+
+    {
+        char const * args[] = { "objects", "*", 0 };
+        declare_native_rule( "class@order", "order", args, order, 1 );
+    }
+}