1 # Copyright (C) 2003 Vladimir Prus
2 # Use, modification, and distribution is subject to the Boost Software
3 # License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy
4 # at http://www.boost.org/LICENSE_1_0.txt)
6 # This module defines a class which allows to order arbitrary object with
7 # regard to arbitrary binary relation.
9 # The primary use case is the gcc toolset, which is sensitive to library order:
10 # if library 'a' uses symbols from library 'b', then 'a' must be present before
11 # 'b' on the linker's command line.
13 # This requirement can be lifted for gcc with GNU ld, but for gcc with Solaris
14 # LD (and for Solaris toolset as well), the order always matters.
16 # So, we need to store order requirements and then order libraries according to
17 # them. It is not possible to use the dependency graph as order requirements.
18 # What we need is a "use symbols" relationship while dependency graph provides
19 # the "needs to be updated" relationship.
25 # For static linking, library 'a' need not depend on 'b'. However, it should
26 # still come before 'b' on the command line.
34 # Adds the constraint that 'first' should preceede 'second'.
35 rule add-pair ( first second )
37 .constraits += $(first)--$(second) ;
39 NATIVE_RULE class@order : add-pair ;
41 # Given a list of objects, reorder them so that the constraints specified by
42 # 'add-pair' are satisfied.
44 # The algorithm was adopted from an awk script by Nikita Youshchenko
45 # (yoush at cs dot msu dot su)
46 rule order ( objects * )
48 # The algorithm used is the same is standard transitive closure, except
49 # that we're not keeping in-degree for all vertices, but rather removing
54 local constraints = [ eliminate-unused-constraits $(objects) ] ;
56 # Find some library that nobody depends upon and add it to the
65 if [ has-no-dependents $(obj) : $(constraints) ]
68 new_objects += $(objects[2-]) ;
73 new_objects += $(obj) ;
75 objects = $(objects[2-]) ;
81 errors.error "Circular order dependencies" ;
83 # No problem with placing first.
85 # Remove all constraints where 'obj' comes first, since they are
87 constraints = [ remove-satisfied $(constraints) : $(obj) ] ;
89 # Add the remaining objects for further processing on the next
91 objects = $(new_objects) ;
97 NATIVE_RULE class@order : order ;
99 # Eliminate constraints which mention objects not in 'objects'. In
100 # graph-theory terms, this is finding a subgraph induced by ordered
102 rule eliminate-unused-constraits ( objects * )
105 for local c in $(.constraints)
107 local m = [ MATCH (.*)--(.*) : $(c) ] ;
108 if $(m[1]) in $(objects) && $(m[2]) in $(objects)
116 # Returns true if there's no constraint in 'constaraints' where 'obj' comes
118 rule has-no-dependents ( obj : constraints * )
121 while $(constraints) && ! $(failed)
123 local c = $(constraints[1]) ;
124 local m = [ MATCH (.*)--(.*) : $(c) ] ;
129 constraints = $(constraints[2-]) ;
137 rule remove-satisfied ( constraints * : obj )
140 for local c in $(constraints)
142 local m = [ MATCH (.*)--(.*) : $(c) ] ;
155 import "class" : new ;
159 $(c1).add-pair l1 l2 ;
161 assert.result l1 l2 : $(c1).order l1 l2 ;
162 assert.result l1 l2 : $(c1).order l2 l1 ;
164 $(c1).add-pair l2 l3 ;
165 assert.result l1 l2 : $(c1).order l2 l1 ;
166 $(c1).add-pair x l2 ;
167 assert.result l1 l2 : $(c1).order l2 l1 ;
168 assert.result l1 l2 l3 : $(c1).order l2 l3 l1 ;
170 # The output should be stable for unconstrained
172 assert.result l4 l5 : $(c1).order l4 l5 ;