Class Order

v2/util/order.py:6–121

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.

#  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 ;