summaryrefslogtreecommitdiff
path: root/jam-files/boost-build/util/order.jam
diff options
context:
space:
mode:
authorPatrick Simianer <simianer@cl.uni-heidelberg.de>2012-05-13 03:35:30 +0200
committerPatrick Simianer <simianer@cl.uni-heidelberg.de>2012-05-13 03:35:30 +0200
commit670a8f984fc6d8342180c59ae9e96b0b76f34d3d (patch)
tree9f2ce7eec1a77e56b3bb1ad0ad40f212d7a996b0 /jam-files/boost-build/util/order.jam
parenteb3ee28dc0eb1d3e5ed01ba0df843be329ae450d (diff)
parent2f64af3e06a518b93f7ca2c30a9d0aeb2c947031 (diff)
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'jam-files/boost-build/util/order.jam')
-rw-r--r--jam-files/boost-build/util/order.jam169
1 files changed, 169 insertions, 0 deletions
diff --git a/jam-files/boost-build/util/order.jam b/jam-files/boost-build/util/order.jam
new file mode 100644
index 00000000..a74fc8c8
--- /dev/null
+++ b/jam-files/boost-build/util/order.jam
@@ -0,0 +1,169 @@
+# 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)
+
+# This module defines a class which allows to order arbitrary object 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 is not possible to use the dependency graph as order requirements.
+# What we need is a "use symbols" relationship while dependency graph provides
+# the "needs to be updated" relationship.
+#
+# For example::
+# lib a : a.cpp b;
+# lib b ;
+#
+# For static linking, library 'a' need not depend on 'b'. However, it should
+# still come before 'b' on the command line.
+
+class order
+{
+ rule __init__ ( )
+ {
+ }
+
+ # Adds the constraint that 'first' should preceede 'second'.
+ rule add-pair ( first second )
+ {
+ .constraits += $(first)--$(second) ;
+ }
+ NATIVE_RULE class@order : add-pair ;
+
+ # Given a list of objects, reorder them so that the constraints specified by
+ # 'add-pair' are satisfied.
+ #
+ # The algorithm was adopted from an awk script by Nikita Youshchenko
+ # (yoush at cs dot msu dot su)
+ rule order ( objects * )
+ {
+ # 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.
+ local result ;
+ if $(objects)
+ {
+ local constraints = [ eliminate-unused-constraits $(objects) ] ;
+
+ # Find some library that nobody depends upon and add it to the
+ # 'result' array.
+ local obj ;
+ while $(objects)
+ {
+ local new_objects ;
+ while $(objects)
+ {
+ obj = $(objects[1]) ;
+ if [ has-no-dependents $(obj) : $(constraints) ]
+ {
+ # Emulate break ;
+ new_objects += $(objects[2-]) ;
+ objects = ;
+ }
+ else
+ {
+ new_objects += $(obj) ;
+ obj = ;
+ objects = $(objects[2-]) ;
+ }
+ }
+
+ if ! $(obj)
+ {
+ errors.error "Circular order dependencies" ;
+ }
+ # No problem with placing first.
+ result += $(obj) ;
+ # Remove all contraints where 'obj' comes first, since they are
+ # already satisfied.
+ constraints = [ remove-satisfied $(constraints) : $(obj) ] ;
+
+ # Add the remaining objects for further processing on the next
+ # iteration
+ objects = $(new_objects) ;
+ }
+
+ }
+ return $(result) ;
+ }
+ NATIVE_RULE class@order : order ;
+
+ # Eliminate constraints which mention objects not in 'objects'. In
+ # graph-theory terms, this is finding a subgraph induced by ordered
+ # vertices.
+ rule eliminate-unused-constraits ( objects * )
+ {
+ local result ;
+ for local c in $(.constraints)
+ {
+ local m = [ MATCH (.*)--(.*) : $(c) ] ;
+ if $(m[1]) in $(objects) && $(m[2]) in $(objects)
+ {
+ result += $(c) ;
+ }
+ }
+ return $(result) ;
+ }
+
+ # Returns true if there's no constraint in 'constaraints' where 'obj' comes
+ # second.
+ rule has-no-dependents ( obj : constraints * )
+ {
+ local failed ;
+ while $(constraints) && ! $(failed)
+ {
+ local c = $(constraints[1]) ;
+ local m = [ MATCH (.*)--(.*) : $(c) ] ;
+ if $(m[2]) = $(obj)
+ {
+ failed = true ;
+ }
+ constraints = $(constraints[2-]) ;
+ }
+ if ! $(failed)
+ {
+ return true ;
+ }
+ }
+
+ rule remove-satisfied ( constraints * : obj )
+ {
+ local result ;
+ for local c in $(constraints)
+ {
+ local m = [ MATCH (.*)--(.*) : $(c) ] ;
+ if $(m[1]) != $(obj)
+ {
+ result += $(c) ;
+ }
+ }
+ return $(result) ;
+ }
+}
+
+
+rule __test__ ( )
+{
+ import "class" : new ;
+ import assert ;
+
+ c1 = [ new order ] ;
+ $(c1).add-pair l1 l2 ;
+
+ assert.result l1 l2 : $(c1).order l1 l2 ;
+ assert.result l1 l2 : $(c1).order l2 l1 ;
+
+ $(c1).add-pair l2 l3 ;
+ assert.result l1 l2 : $(c1).order l2 l1 ;
+ $(c1).add-pair x l2 ;
+ assert.result l1 l2 : $(c1).order l2 l1 ;
+ assert.result l1 l2 l3 : $(c1).order l2 l3 l1 ;
+}