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) 5 6class Order: 7 """Allows ordering arbitrary objects with regard to arbitrary binary relation. 8 9 The primary use case is the gcc toolset, which is sensitive to 10 library order: if library 'a' uses symbols from library 'b', 11 then 'a' must be present before 'b' on the linker's command line. 12 13 This requirement can be lifted for gcc with GNU ld, but for gcc with 14 Solaris LD (and for Solaris toolset as well), the order always matters. 15 16 So, we need to store order requirements and then order libraries 17 according to them. It it not possible to use dependency graph as 18 order requirements. What we need is "use symbols" relationship 19 while dependency graph provides "needs to be updated" relationship. 20 21 For example:: 22 lib a : a.cpp b; 23 lib b ; 24 25 For static linking, the 'a' library need not depend on 'b'. However, it 26 still should come before 'b' on the command line. 27 """ 28 29 def __init__ (self): 30 self.constraints_ = [] 31 32 def add_pair (self, first, second): 33 """ Adds the constraint that 'first' should precede 'second'. 34 """ 35 self.constraints_.append ((first, second)) 36 37 def order (self, objects): 38 """ Given a list of objects, reorder them so that the constains specified 39 by 'add_pair' are satisfied. 40 41 The algorithm was adopted from an awk script by Nikita Youshchenko 42 (yoush at cs dot msu dot su) 43 """ 44 # The algorithm used is the same is standard transitive closure, 45 # except that we're not keeping in-degree for all vertices, but 46 # rather removing edges. 47 result = [] 48 49 if not objects: 50 return result 51 52 constraints = self.__eliminate_unused_constraits (objects) 53 54 # Find some library that nobody depends upon and add it to 55 # the 'result' array. 56 obj = None 57 while objects: 58 new_objects = [] 59 while objects: 60 obj = objects [0] 61 62 if self.__has_no_dependents (obj, constraints): 63 # Emulate break ; 64 new_objects.extend (objects [1:]) 65 objects = [] 66 67 else: 68 new_objects.append (obj) 69 obj = None 70 objects = objects [1:] 71 72 if not obj: 73 raise BaseException ("Circular order dependencies") 74 75 # No problem with placing first. 76 result.append (obj) 77 78 # Remove all contains where 'obj' comes first, 79 # since they are already satisfied. 80 constraints = self.__remove_satisfied (constraints, obj) 81 82 # Add the remaining objects for further processing 83 # on the next iteration 84 objects = new_objects 85 86 return result 87 88 def __eliminate_unused_constraits (self, objects): 89 """ Eliminate constraints which mention objects not in 'objects'. 90 In graph-theory terms, this is finding subgraph induced by 91 ordered vertices. 92 """ 93 result = [] 94 for c in self.constraints_: 95 if c [0] in objects and c [1] in objects: 96 result.append (c) 97 98 return result 99 100 def __has_no_dependents (self, obj, constraints): 101 """ Returns true if there's no constraint in 'constraints' where 102 'obj' comes second. 103 """ 104 failed = False 105 while constraints and not failed: 106 c = constraints [0] 107 108 if c [1] == obj: 109 failed = True 110 111 constraints = constraints [1:] 112 113 return not failed 114 115 def __remove_satisfied (self, constraints, obj): 116 result = [] 117 for c in constraints: 118 if c [0] != obj: 119 result.append (c) 120 121 return result 122