tools/build/src/util/order.jam

   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 #  This module defines a class which allows to order arbitrary object with
   7 # regard to arbitrary binary relation.
   8 #
   9 #  The primary use case is the gcc toolset, which is sensitive to library order:
  10 #  if library 'a' uses symbols from library 'b', then 'a' must be present before
  11 #  'b' on the linker's command line.
  12 #
  13 #  This requirement can be lifted for gcc with GNU ld, but for gcc with Solaris
  14 #  LD (and for Solaris toolset as well), the order always matters.
  15 #
  16 #  So, we need to store order requirements and then order libraries according to
  17 #  them. It is not possible to use the dependency graph as order requirements.
  18 #  What we need is a "use symbols" relationship while dependency graph provides
  19 #  the "needs to be updated" relationship.
  20 #
  21 #  For example::
  22 #    lib a : a.cpp b;
  23 #    lib b ;
  24 #
  25 #  For static linking, library 'a' need not depend on 'b'. However, it should
  26 #  still come before 'b' on the command line.
  27
  28 class order
  29 {
  30     rule __init__ ( )
  31     {
  32     }
  33
  34     # Adds the constraint that 'first' should preceede 'second'.
  35     rule add-pair ( first second )
  36     {
  37         .constraits += $(first)--$(second) ;
  38     }
  39     NATIVE_RULE class@order : add-pair ;
  40
  41     # Given a list of objects, reorder them so that the constraints specified by
  42     # 'add-pair' are satisfied.
  43     #
  44     # The algorithm was adopted from an awk script by Nikita Youshchenko
  45     # (yoush at cs dot msu dot su)
  46     rule order ( objects * )
  47     {
  48         # The algorithm used is the same is standard transitive closure, except
  49         # that we're not keeping in-degree for all vertices, but rather removing
  50         # edges.
  51         local result ;
  52         if $(objects)
  53         {
  54             local constraints = [ eliminate-unused-constraits $(objects) ] ;
  55
  56             # Find some library that nobody depends upon and add it to the
  57             # 'result' array.
  58             local obj ;
  59             while $(objects)
  60             {
  61                 local new_objects ;
  62                 while $(objects)
  63                 {
  64                     obj = $(objects[1]) ;
  65                     if [ has-no-dependents $(obj) : $(constraints) ]
  66                     {
  67                         # Emulate break ;
  68                         new_objects += $(objects[2-]) ;
  69                         objects = ;
  70                     }
  71                     else
  72                     {
  73                         new_objects += $(obj) ;
  74                         obj = ;
  75                         objects = $(objects[2-]) ;
  76                     }
  77                 }
  78
  79                 if ! $(obj)
  80                 {
  81                     errors.error "Circular order dependencies" ;
  82                 }
  83                 # No problem with placing first.
  84                 result += $(obj) ;
  85                 # Remove all contraints where 'obj' comes first, since they are
  86                 # already satisfied.
  87                 constraints = [ remove-satisfied $(constraints) : $(obj) ] ;
  88
  89                 # Add the remaining objects for further processing on the next
  90                 # iteration
  91                 objects = $(new_objects) ;
  92             }
  93
  94         }
  95         return $(result) ;
  96     }
  97     NATIVE_RULE class@order : order ;
  98
  99     # Eliminate constraints which mention objects not in 'objects'. In
 100     # graph-theory terms, this is finding a subgraph induced by ordered
 101     # vertices.
 102     rule eliminate-unused-constraits ( objects * )
 103     {
 104         local result ;
 105         for local c in $(.constraints)
 106         {
 107             local m = [ MATCH (.*)--(.*) : $(c) ] ;
 108             if $(m[1]) in $(objects) && $(m[2]) in $(objects)
 109             {
 110                 result += $(c) ;
 111             }
 112         }
 113         return $(result) ;
 114     }
 115
 116     # Returns true if there's no constraint in 'constaraints' where 'obj' comes
 117     # second.
 118     rule has-no-dependents ( obj : constraints * )
 119     {
 120         local failed ;
 121         while $(constraints) && ! $(failed)
 122         {
 123             local c = $(constraints[1]) ;
 124             local m = [ MATCH (.*)--(.*) : $(c) ] ;
 125             if $(m[2]) = $(obj)
 126             {
 127                 failed = true ;
 128             }
 129             constraints = $(constraints[2-]) ;
 130         }
 131         if ! $(failed)
 132         {
 133             return true ;
 134         }
 135     }
 136
 137     rule remove-satisfied ( constraints * : obj )
 138     {
 139         local result ;
 140         for local c in $(constraints)
 141         {
 142             local m = [ MATCH (.*)--(.*) : $(c) ] ;
 143             if $(m[1]) != $(obj)
 144             {
 145                 result += $(c) ;
 146             }
 147         }
 148         return $(result) ;
 149     }
 150 }
 151
 152
 153 rule __test__ ( )
 154 {
 155     import "class" : new ;
 156     import assert ;
 157
 158     c1 = [ new order ] ;
 159     $(c1).add-pair l1 l2 ;
 160
 161     assert.result l1 l2 : $(c1).order l1 l2 ;
 162     assert.result l1 l2 : $(c1).order l2 l1 ;
 163
 164     $(c1).add-pair l2 l3 ;
 165     assert.result l1 l2 : $(c1).order l2 l1 ;
 166     $(c1).add-pair x l2 ;
 167     assert.result l1 l2 : $(c1).order l2 l1 ;
 168     assert.result l1 l2 l3 : $(c1).order l2 l3 l1 ;
 169 }