1 /* Copyright 2004. Vladimir Prus
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.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 */
add_pair(FRAME * frame,int flags)18 LIST * add_pair( FRAME * frame, int 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 */
list_index(LIST * list,OBJECT * value)32 int list_index( LIST * list, OBJECT * value )
33 {
34 int 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 */
do_ts(int ** graph,int current_vertex,int * colors,int ** result_ptr)50 void do_ts( int * * graph, int current_vertex, int * colors, int * * result_ptr
51 )
52 {
53 int i;
54
55 colors[ current_vertex ] = gray;
56 for ( i = 0; graph[ current_vertex ][ i ] != -1; ++i )
57 {
58 int 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
topological_sort(int ** graph,int num_vertices,int * result)73 void topological_sort( int * * graph, int num_vertices, int * result )
74 {
75 int i;
76 int * colors = ( int * )BJAM_CALLOC( num_vertices, sizeof( int ) );
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
order(FRAME * frame,int flags)88 LIST * order( FRAME * frame, int flags )
89 {
90 LIST * arg = lol_get( frame->args, 0 );
91 LIST * result = L0;
92 int 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 int length = list_length( arg );
100 int * * graph = ( int * * )BJAM_CALLOC( length, sizeof( int * ) );
101 int * order = ( int * )BJAM_MALLOC( ( length + 1 ) * sizeof( int ) );
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 int index = 0;
108 LISTITER dep_iter = list_begin( dependencies );
109 LISTITER const dep_end = list_end( dependencies );
110
111 graph[ src ] = ( int * )BJAM_CALLOC( list_length( dependencies ) + 1,
112 sizeof( int ) );
113 for ( ; dep_iter != dep_end; dep_iter = list_next( dep_iter ) )
114 {
115 int 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 int index = length - 1;
126 for ( ; index >= 0; --index )
127 {
128 int 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 int 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
init_order()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 }
160