summaryrefslogtreecommitdiff
path: root/jam-files/boost-build/util/order.py
diff options
context:
space:
mode:
Diffstat (limited to 'jam-files/boost-build/util/order.py')
-rw-r--r--jam-files/boost-build/util/order.py121
1 files changed, 0 insertions, 121 deletions
diff --git a/jam-files/boost-build/util/order.py b/jam-files/boost-build/util/order.py
deleted file mode 100644
index 4e67b3f1..00000000
--- a/jam-files/boost-build/util/order.py
+++ /dev/null
@@ -1,121 +0,0 @@
-# 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