tools/build/src/util/order.py

   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
   6 class 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 containts 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