summaryrefslogtreecommitdiff
path: root/jam-files/boost-build/util/order.py
diff options
context:
space:
mode:
authorKenneth Heafield <github@kheafield.com>2012-05-12 14:01:52 -0400
committerKenneth Heafield <github@kheafield.com>2012-05-12 14:01:52 -0400
commit3faecf9a00512dcbc8712c4bca9adae72fb64410 (patch)
tree9761b50d12f81a675fb7cbc663ceebad15079f78 /jam-files/boost-build/util/order.py
parentc806a8fff63043f63773874986301f2822a2b552 (diff)
Give in and copy bjam into cdec source code
Diffstat (limited to 'jam-files/boost-build/util/order.py')
-rw-r--r--jam-files/boost-build/util/order.py121
1 files changed, 121 insertions, 0 deletions
diff --git a/jam-files/boost-build/util/order.py b/jam-files/boost-build/util/order.py
new file mode 100644
index 00000000..4e67b3f1
--- /dev/null
+++ b/jam-files/boost-build/util/order.py
@@ -0,0 +1,121 @@
+# Copyright (C) 2003 Vladimir Prus
+# Use, modification, and distribution is subject to 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)
+
+class Order:
+ """Allows ordering arbitrary objects with regard to arbitrary binary relation.
+
+ The primary use case is the gcc toolset, which is sensitive to
+ library order: if library 'a' uses symbols from library 'b',
+ then 'a' must be present before 'b' on the linker's command line.
+
+ This requirement can be lifted for gcc with GNU ld, but for gcc with
+ Solaris LD (and for Solaris toolset as well), the order always matters.
+
+ So, we need to store order requirements and then order libraries
+ according to them. It it not possible to use dependency graph as
+ order requirements. What we need is "use symbols" relationship
+ while dependency graph provides "needs to be updated" relationship.
+
+ For example::
+ lib a : a.cpp b;
+ lib b ;
+
+ For static linking, the 'a' library need not depend on 'b'. However, it
+ still should come before 'b' on the command line.
+ """
+
+ def __init__ (self):
+ self.constraints_ = []
+
+ def add_pair (self, first, second):
+ """ Adds the constraint that 'first' should precede 'second'.
+ """
+ self.constraints_.append ((first, second))
+
+ def order (self, objects):
+ """ Given a list of objects, reorder them so that the constains specified
+ by 'add_pair' are satisfied.
+
+ The algorithm was adopted from an awk script by Nikita Youshchenko
+ (yoush at cs dot msu dot su)
+ """
+ # The algorithm used is the same is standard transitive closure,
+ # except that we're not keeping in-degree for all vertices, but
+ # rather removing edges.
+ result = []
+
+ if not objects:
+ return result
+
+ constraints = self.__eliminate_unused_constraits (objects)
+
+ # Find some library that nobody depends upon and add it to
+ # the 'result' array.
+ obj = None
+ while objects:
+ new_objects = []
+ while objects:
+ obj = objects [0]
+
+ if self.__has_no_dependents (obj, constraints):
+ # Emulate break ;
+ new_objects.extend (objects [1:])
+ objects = []
+
+ else:
+ new_objects.append (obj)
+ obj = None
+ objects = objects [1:]
+
+ if not obj:
+ raise BaseException ("Circular order dependencies")
+
+ # No problem with placing first.
+ result.append (obj)
+
+ # Remove all containts where 'obj' comes first,
+ # since they are already satisfied.
+ constraints = self.__remove_satisfied (constraints, obj)
+
+ # Add the remaining objects for further processing
+ # on the next iteration
+ objects = new_objects
+
+ return result
+
+ def __eliminate_unused_constraits (self, objects):
+ """ Eliminate constraints which mention objects not in 'objects'.
+ In graph-theory terms, this is finding subgraph induced by
+ ordered vertices.
+ """
+ result = []
+ for c in self.constraints_:
+ if c [0] in objects and c [1] in objects:
+ result.append (c)
+
+ return result
+
+ def __has_no_dependents (self, obj, constraints):
+ """ Returns true if there's no constraint in 'constraints' where
+ 'obj' comes second.
+ """
+ failed = False
+ while constraints and not failed:
+ c = constraints [0]
+
+ if c [1] == obj:
+ failed = True
+
+ constraints = constraints [1:]
+
+ return not failed
+
+ def __remove_satisfied (self, constraints, obj):
+ result = []
+ for c in constraints:
+ if c [0] != obj:
+ result.append (c)
+
+ return result