blob: a456dc6e77401c2aa060b237edd210797e31b619 [file] [log] [blame]
Reid Spencerb195d9d2006-03-23 23:21:29 +00001#!@PERL@
Chris Lattner584073a2006-06-02 18:58:21 +00002##===- tools/llvm-config ---------------------------------------*- perl -*-===##
3#
4# The LLVM Compiler Infrastructure
Reid Spencerf2722ca2006-03-22 15:59:55 +00005#
Chris Lattner234d5292007-12-29 22:59:10 +00006# This file is distributed under the University of Illinois Open Source
7# License. See LICENSE.TXT for details.
Chris Lattner584073a2006-06-02 18:58:21 +00008#
9##===----------------------------------------------------------------------===##
Reid Spencerf2722ca2006-03-22 15:59:55 +000010#
11# Synopsis: Prints out compiler options needed to build against an installed
12# copy of LLVM.
13#
Chris Lattner7f71e212006-04-13 04:21:31 +000014# Syntax: llvm-config OPTIONS... [COMPONENTS...]
Chris Lattner584073a2006-06-02 18:58:21 +000015#
16##===----------------------------------------------------------------------===##
Reid Spencerf2722ca2006-03-22 15:59:55 +000017
Reid Spencerb195d9d2006-03-23 23:21:29 +000018use 5.006;
Reid Spencerf2722ca2006-03-22 15:59:55 +000019use strict;
20use warnings;
Chris Lattner59780b82010-01-18 22:27:43 +000021use Cwd 'abs_path';
Reid Spencerf2722ca2006-03-22 15:59:55 +000022
23#---- begin autoconf values ----
Reid Spencer2d2c2f22006-06-02 18:31:41 +000024my $PACKAGE_NAME = q{@PACKAGE_NAME@};
Reid Spencerf2722ca2006-03-22 15:59:55 +000025my $VERSION = q{@PACKAGE_VERSION@};
26my $PREFIX = q{@LLVM_PREFIX@};
Reid Spencer2d2c2f22006-06-02 18:31:41 +000027my $LLVM_CONFIGTIME = q{@LLVM_CONFIGTIME@};
28my $LLVM_SRC_ROOT = q{@abs_top_srcdir@};
29my $LLVM_OBJ_ROOT = q{@abs_top_builddir@};
Reid Spencerf2722ca2006-03-22 15:59:55 +000030my $ARCH = lc(q{@ARCH@});
Reid Spencer2d2c2f22006-06-02 18:31:41 +000031my $TARGET_TRIPLE = q{@target@};
32my $TARGETS_TO_BUILD = q{@TARGETS_TO_BUILD@};
Reid Spencerb195d9d2006-03-23 23:21:29 +000033my $TARGET_HAS_JIT = q{@TARGET_HAS_JIT@};
Reid Spencerf2722ca2006-03-22 15:59:55 +000034my @TARGETS_BUILT = map { lc($_) } qw{@TARGETS_TO_BUILD@};
35#---- end autoconf values ----
36
Jeff Cohen02c91ef2007-03-28 04:45:02 +000037# Must pretend x86_64 architecture is really x86, otherwise the native backend
38# won't get linked in.
39$ARCH = "x86" if $ARCH eq "x86_64";
40
Reid Spencerf2722ca2006-03-22 15:59:55 +000041#---- begin Makefile values ----
David Greenea696d242007-06-28 19:36:08 +000042my $CPPFLAGS = q{@LLVM_CPPFLAGS@};
Reid Spencerf72538e2007-01-06 02:48:03 +000043my $CFLAGS = q{@LLVM_CFLAGS@};
Reid Spencerf2722ca2006-03-22 15:59:55 +000044my $CXXFLAGS = q{@LLVM_CXXFLAGS@};
45my $LDFLAGS = q{@LLVM_LDFLAGS@};
Reid Spencer1bc68642006-07-27 23:00:30 +000046my $SYSTEM_LIBS = q{@LIBS@};
Chris Lattnerabdbae72006-06-02 19:13:29 +000047my $LLVM_BUILDMODE = q{@LLVM_BUILDMODE@};
Peter Collingbourneee826c82011-10-28 01:02:16 +000048my $LLVM_OBJ_SUFFIX = q{@LLVM_OBJ_SUFFIX@};
Reid Spencerf2722ca2006-03-22 15:59:55 +000049#---- end Makefile values ----
50
Chris Lattner16ad6182006-06-02 21:48:10 +000051# Figure out where llvm-config is being run from. Primarily, we care if it has
52# been installed, or is running from the build directory, which changes the
53# locations of some files.
54
Chris Lattnere02b97b2006-06-02 01:23:18 +000055# Convert the current executable name into its directory (e.g. ".").
Chris Lattner16ad6182006-06-02 21:48:10 +000056my ($RUN_DIR) = ($0 =~ /^(.*)\/.*$/);
57
58# Turn the directory into an absolute directory on the file system, also pop up
59# from "bin" into the build or prefix dir.
Chris Lattner59780b82010-01-18 22:27:43 +000060my $ABS_RUN_DIR = abs_path("$RUN_DIR/..");
Tanya Lattnere32d58f2008-11-04 21:06:11 +000061chomp($ABS_RUN_DIR);
Chris Lattner16ad6182006-06-02 21:48:10 +000062
63# Compute the absolute object directory build, e.g. "foo/llvm/Debug".
Peter Collingbourneee826c82011-10-28 01:02:16 +000064my $ABS_OBJ_ROOT = "$LLVM_OBJ_ROOT$LLVM_OBJ_SUFFIX";
Chris Lattner59780b82010-01-18 22:27:43 +000065$ABS_OBJ_ROOT = abs_path("$ABS_OBJ_ROOT") if (-d $ABS_OBJ_ROOT);
Tanya Lattnere32d58f2008-11-04 21:06:11 +000066chomp($ABS_OBJ_ROOT);
Chris Lattner16ad6182006-06-02 21:48:10 +000067
Chris Lattner0cd059e2006-06-02 22:03:50 +000068my $INCLUDEDIR = "$ABS_RUN_DIR/include";
Jeffrey Yasskin9a3b13f2009-07-07 22:15:37 +000069my $INCLUDEOPTION = "-I$INCLUDEDIR";
Chris Lattner0cd059e2006-06-02 22:03:50 +000070my $LIBDIR = "$ABS_RUN_DIR/lib";
71my $BINDIR = "$ABS_RUN_DIR/bin";
Chris Lattner16ad6182006-06-02 21:48:10 +000072if ($ABS_RUN_DIR eq $ABS_OBJ_ROOT) {
73 # If we are running out of the build directory, the include dir is in the
74 # srcdir.
75 $INCLUDEDIR = "$LLVM_SRC_ROOT/include";
Jeffrey Yasskin9a3b13f2009-07-07 22:15:37 +000076 # We need include files from both the srcdir and objdir.
77 $INCLUDEOPTION = "-I$INCLUDEDIR -I$LLVM_OBJ_ROOT/include"
Chris Lattner16ad6182006-06-02 21:48:10 +000078} else {
Chris Lattner0cd059e2006-06-02 22:03:50 +000079 # If installed, ignore the prefix the tree was configured with, use the
80 # current prefix.
81 $PREFIX = $ABS_RUN_DIR;
Chris Lattner16ad6182006-06-02 21:48:10 +000082}
Chris Lattnere02b97b2006-06-02 01:23:18 +000083
Reid Spencerf2722ca2006-03-22 15:59:55 +000084sub usage;
85sub fix_library_names (@);
Chris Lattnerd179de52006-06-06 22:38:29 +000086sub fix_library_files (@);
Reid Spencerd8c20a92006-08-03 21:45:35 +000087sub expand_dependencies (@);
Reid Spencerf2722ca2006-03-22 15:59:55 +000088sub name_map_entries;
89
90# Parse our command-line arguments.
91usage if @ARGV == 0;
92my @components;
93my $has_opt = 0;
94my $want_libs = 0;
95my $want_libnames = 0;
Chris Lattnerd179de52006-06-06 22:38:29 +000096my $want_libfiles = 0;
Reid Spencerf2722ca2006-03-22 15:59:55 +000097my $want_components = 0;
98foreach my $arg (@ARGV) {
99 if ($arg =~ /^-/) {
100 if ($arg eq "--version") {
101 $has_opt = 1; print "$VERSION\n";
102 } elsif ($arg eq "--prefix") {
103 $has_opt = 1; print "$PREFIX\n";
104 } elsif ($arg eq "--bindir") {
Chris Lattner16ad6182006-06-02 21:48:10 +0000105 $has_opt = 1; print "$BINDIR\n";
Reid Spencerf2722ca2006-03-22 15:59:55 +0000106 } elsif ($arg eq "--includedir") {
Chris Lattner16ad6182006-06-02 21:48:10 +0000107 $has_opt = 1; print "$INCLUDEDIR\n";
Reid Spencerf2722ca2006-03-22 15:59:55 +0000108 } elsif ($arg eq "--libdir") {
Chris Lattner16ad6182006-06-02 21:48:10 +0000109 $has_opt = 1; print "$LIBDIR\n";
David Greenea696d242007-06-28 19:36:08 +0000110 } elsif ($arg eq "--cppflags") {
Jeffrey Yasskin9a3b13f2009-07-07 22:15:37 +0000111 $has_opt = 1; print "$INCLUDEOPTION $CPPFLAGS\n";
Reid Spencerf72538e2007-01-06 02:48:03 +0000112 } elsif ($arg eq "--cflags") {
Jeffrey Yasskin9a3b13f2009-07-07 22:15:37 +0000113 $has_opt = 1; print "$INCLUDEOPTION $CFLAGS\n";
Reid Spencerf2722ca2006-03-22 15:59:55 +0000114 } elsif ($arg eq "--cxxflags") {
Jeffrey Yasskin9a3b13f2009-07-07 22:15:37 +0000115 $has_opt = 1; print "$INCLUDEOPTION $CXXFLAGS\n";
Reid Spencerf2722ca2006-03-22 15:59:55 +0000116 } elsif ($arg eq "--ldflags") {
Reid Spencer1bc68642006-07-27 23:00:30 +0000117 $has_opt = 1; print "-L$LIBDIR $LDFLAGS $SYSTEM_LIBS\n";
Reid Spencerf2722ca2006-03-22 15:59:55 +0000118 } elsif ($arg eq "--libs") {
119 $has_opt = 1; $want_libs = 1;
120 } elsif ($arg eq "--libnames") {
121 $has_opt = 1; $want_libnames = 1;
Chris Lattnerd179de52006-06-06 22:38:29 +0000122 } elsif ($arg eq "--libfiles") {
123 $has_opt = 1; $want_libfiles = 1;
Reid Spencerf2722ca2006-03-22 15:59:55 +0000124 } elsif ($arg eq "--components") {
125 $has_opt = 1; print join(' ', name_map_entries), "\n";
126 } elsif ($arg eq "--targets-built") {
127 $has_opt = 1; print join(' ', @TARGETS_BUILT), "\n";
Reid Spencer3b87d6a2007-04-22 05:05:36 +0000128 } elsif ($arg eq "--host-target") {
129 $has_opt = 1; print "$TARGET_TRIPLE\n";
Chris Lattner0cd059e2006-06-02 22:03:50 +0000130 } elsif ($arg eq "--build-mode") {
131 $has_opt = 1; print "$LLVM_BUILDMODE\n";
132 } elsif ($arg eq "--obj-root") {
Chris Lattner59780b82010-01-18 22:27:43 +0000133 $has_opt = 1; print abs_path("$LLVM_OBJ_ROOT/");
Chris Lattner0cd059e2006-06-02 22:03:50 +0000134 } elsif ($arg eq "--src-root") {
Chris Lattner59780b82010-01-18 22:27:43 +0000135 $has_opt = 1; print abs_path("$LLVM_SRC_ROOT/");
Reid Spencerf2722ca2006-03-22 15:59:55 +0000136 } else {
137 usage();
138 }
139 } else {
140 push @components, $arg;
141 }
142}
143
144# If no options were specified, fail.
145usage unless $has_opt;
146
147# If no components were specified, default to 'all'.
148if (@components == 0) {
149 push @components, 'all';
150}
151
Chris Lattner54eae9e2006-09-04 05:35:23 +0000152# Force component names to lower case.
153@components = map lc, @components;
154
Reid Spencerf2722ca2006-03-22 15:59:55 +0000155# Handle any arguments which require building our dependency graph.
Chris Lattnerd179de52006-06-06 22:38:29 +0000156if ($want_libs || $want_libnames || $want_libfiles) {
Reid Spencerd8c20a92006-08-03 21:45:35 +0000157 my @libs = expand_dependencies(@components);
Chris Lattnerd179de52006-06-06 22:38:29 +0000158 print join(' ', fix_library_names(@libs)), "\n" if ($want_libs);
159 print join(' ', @libs), "\n" if ($want_libnames);
160 print join(' ', fix_library_files(@libs)), "\n" if ($want_libfiles);
Reid Spencerf2722ca2006-03-22 15:59:55 +0000161}
162
163exit 0;
164
165#==========================================================================
166# Support Routines
167#==========================================================================
168
169sub usage {
170 print STDERR <<__EOD__;
171Usage: llvm-config <OPTION>... [<COMPONENT>...]
172
173Get various configuration information needed to compile programs which use
174LLVM. Typically called from 'configure' scripts. Examples:
175 llvm-config --cxxflags
176 llvm-config --ldflags
Reid Spencerb195d9d2006-03-23 23:21:29 +0000177 llvm-config --libs engine bcreader scalaropts
Reid Spencerf2722ca2006-03-22 15:59:55 +0000178
179Options:
Reid Spencer087d90e2007-07-10 07:48:09 +0000180 --version Print LLVM version.
181 --prefix Print the installation prefix.
182 --src-root Print the source root LLVM was built from.
183 --obj-root Print the object root used to build LLVM.
184 --bindir Directory containing LLVM executables.
185 --includedir Directory containing LLVM headers.
186 --libdir Directory containing LLVM libraries.
187 --cppflags C preprocessor flags for files that include LLVM headers.
188 --cflags C compiler flags for files that include LLVM headers.
189 --cxxflags C++ compiler flags for files that include LLVM headers.
190 --ldflags Print Linker flags.
191 --libs Libraries needed to link against LLVM components.
192 --libnames Bare library names for in-tree builds.
193 --libfiles Fully qualified library filenames for makefile depends.
194 --components List of all possible components.
195 --targets-built List of all targets currently built.
196 --host-target Target triple used to configure LLVM.
197 --build-mode Print build mode of LLVM tree (e.g. Debug or Release).
Reid Spencerf2722ca2006-03-22 15:59:55 +0000198Typical components:
Reid Spencer087d90e2007-07-10 07:48:09 +0000199 all All LLVM libraries (default).
200 backend Either a native backend or the C backend.
Duncan Sands18d52f22010-09-29 20:09:55 +0000201 engine Either a native JIT or a bitcode interpreter.
Reid Spencerf2722ca2006-03-22 15:59:55 +0000202__EOD__
203 exit(1);
204}
205
206# Use -lfoo instead of libfoo.a whenever possible, and add directories to
207# files which can't be found using -L.
208sub fix_library_names (@) {
209 my @libs = @_;
210 my @result;
211 foreach my $lib (@libs) {
212 # Transform the bare library name appropriately.
213 my ($basename) = ($lib =~ /^lib([^.]*)\.a/);
214 if (defined $basename) {
215 push @result, "-l$basename";
216 } else {
Chris Lattner16ad6182006-06-02 21:48:10 +0000217 push @result, "$LIBDIR/$lib";
Reid Spencerf2722ca2006-03-22 15:59:55 +0000218 }
219 }
220 return @result;
221}
222
Chris Lattnerd179de52006-06-06 22:38:29 +0000223# Turn the list of libraries into a list of files.
224sub fix_library_files(@) {
225 my @libs = @_;
226 my @result;
227 foreach my $lib (@libs) {
228 # Transform the bare library name into a filename.
229 push @result, "$LIBDIR/$lib";
230 }
231 return @result;
232}
Reid Spencerf2722ca2006-03-22 15:59:55 +0000233
234#==========================================================================
235# Library Dependency Analysis
236#==========================================================================
237# Given a few human-readable library names, find all their dependencies
238# and sort them into an order which the linker will like. If we packed
239# our libraries into fewer archives, we could make the linker do much
240# of this work for us.
241#
242# Libraries have two different types of names in this code: Human-friendly
243# "component" names entered on the command-line, and the raw file names
244# we use internally (and ultimately pass to the linker).
245#
246# To understand this code, you'll need a working knowledge of Perl 5,
247# and possibly some quality time with 'man perlref'.
248
249sub load_dependencies;
250sub build_name_map;
Reid Spencerb195d9d2006-03-23 23:21:29 +0000251sub have_native_backend;
252sub find_best_engine;
Reid Spencerf2722ca2006-03-22 15:59:55 +0000253sub expand_names (@);
254sub find_all_required_sets (@);
255sub find_all_required_sets_helper ($$@);
Reid Spencerf2722ca2006-03-22 15:59:55 +0000256
257# Each "set" contains one or more libraries which must be included as a
258# group (due to cyclic dependencies). Sets are represented as a Perl array
259# reference pointing to a list of internal library names.
260my @SETS;
261
262# Various mapping tables.
263my %LIB_TO_SET_MAP; # Maps internal library names to their sets.
264my %SET_DEPS; # Maps sets to a list of libraries they depend on.
265my %NAME_MAP; # Maps human-entered names to internal names.
266
267# Have our dependencies been loaded yet?
268my $DEPENDENCIES_LOADED = 0;
269
270# Given a list of human-friendly component names, translate them into a
271# complete set of linker arguments.
Reid Spencerd8c20a92006-08-03 21:45:35 +0000272sub expand_dependencies (@) {
Reid Spencerf2722ca2006-03-22 15:59:55 +0000273 my @libs = @_;
274 load_dependencies;
275 my @required_sets = find_all_required_sets(expand_names(@libs));
276 my @sorted_sets = topologically_sort_sets(@required_sets);
277
Chris Lattner06e752e2006-06-02 00:56:15 +0000278 # Expand the library sets into libraries.
Reid Spencerf2722ca2006-03-22 15:59:55 +0000279 my @result;
280 foreach my $set (@sorted_sets) { push @result, @{$set}; }
Chris Lattner06e752e2006-06-02 00:56:15 +0000281 return @result;
Reid Spencerf2722ca2006-03-22 15:59:55 +0000282}
283
284# Load in the raw dependency data stored at the end of this file.
285sub load_dependencies {
286 return if $DEPENDENCIES_LOADED;
287 $DEPENDENCIES_LOADED = 1;
288 while (<DATA>) {
289 # Parse our line.
Anton Korobeynikovde9c02b2006-08-04 21:52:23 +0000290 my ($libs, $deps) = /^\s*([^:]+):\s*(.*)\s*$/;
Reid Spencerf2722ca2006-03-22 15:59:55 +0000291 die "Malformed dependency data" unless defined $deps;
292 my @libs = split(' ', $libs);
293 my @deps = split(' ', $deps);
294
295 # Record our dependency data.
296 my $set = \@libs;
297 push @SETS, $set;
298 foreach my $lib (@libs) { $LIB_TO_SET_MAP{$lib} = $set; }
299 $SET_DEPS{$set} = \@deps;
300 }
301 build_name_map;
302}
303
304# Build a map converting human-friendly component names into internal
305# library names.
306sub build_name_map {
307 # Add entries for all the actual libraries.
308 foreach my $set (@SETS) {
309 foreach my $lib (sort @$set) {
310 my $short_name = $lib;
311 $short_name =~ s/^(lib)?LLVM([^.]*)\..*$/$2/;
312 $short_name =~ tr/A-Z/a-z/;
313 $NAME_MAP{$short_name} = [$lib];
314 }
315 }
316
Anton Korobeynikov3c3bc482008-08-17 13:53:59 +0000317 # Add target-specific entries
Daniel Dunbara6b19292011-10-18 19:27:08 +0000318 my @all_targets;
Anton Korobeynikov3c3bc482008-08-17 13:53:59 +0000319 foreach my $target (@TARGETS_BUILT) {
320 # FIXME: Temporary, until we don't switch all targets
321 if (defined $NAME_MAP{$target.'asmprinter'}) {
Daniel Dunbar8cca8f92009-07-15 07:43:34 +0000322 $NAME_MAP{$target} = [$target.'info',
323 $target.'asmprinter',
324 $target.'codegen']
Chris Lattnere15f2e12010-11-14 19:10:47 +0000325 } elsif (defined $NAME_MAP{$target.'codegen'}) {
Daniel Dunbara6b19292011-10-18 19:27:08 +0000326 $NAME_MAP{$target} = [$target.'info',
327 $target.'codegen']
Daniel Dunbar8cca8f92009-07-15 07:43:34 +0000328 } else {
329 $NAME_MAP{$target} = [$target.'info',
330 $NAME_MAP{$target}[0]]
Anton Korobeynikov3c3bc482008-08-17 13:53:59 +0000331 }
Daniel Dunbarf8bd8442009-07-17 21:26:27 +0000332
333 if (defined $NAME_MAP{$target.'asmparser'}) {
334 push @{$NAME_MAP{$target}},$target.'asmparser'
335 }
Daniel Dunbarf87ea4d2009-11-25 04:46:58 +0000336
337 if (defined $NAME_MAP{$target.'disassembler'}) {
338 push @{$NAME_MAP{$target}},$target.'disassembler'
339 }
Daniel Dunbara6b19292011-10-18 19:27:08 +0000340
341 push @all_targets, $target;
Anton Korobeynikov3c3bc482008-08-17 13:53:59 +0000342 }
343
Reid Spencerf2722ca2006-03-22 15:59:55 +0000344 # Add virtual entries.
Reid Spencerb195d9d2006-03-23 23:21:29 +0000345 $NAME_MAP{'native'} = have_native_backend() ? [$ARCH] : [];
Anton Korobeynikov3c3bc482008-08-17 13:53:59 +0000346 $NAME_MAP{'nativecodegen'} = have_native_backend() ? [$ARCH.'codegen'] : [];
Reid Spencerb195d9d2006-03-23 23:21:29 +0000347 $NAME_MAP{'backend'} = have_native_backend() ? ['native'] : ['cbackend'];
348 $NAME_MAP{'engine'} = find_best_engine;
Daniel Dunbara6b19292011-10-18 19:27:08 +0000349 $NAME_MAP{'all-targets'} = \@all_targets;
Reid Spencerb195d9d2006-03-23 23:21:29 +0000350 $NAME_MAP{'all'} = [name_map_entries]; # Must be last.
Reid Spencerf2722ca2006-03-22 15:59:55 +0000351}
352
Reid Spencerb195d9d2006-03-23 23:21:29 +0000353# Return true if we have a native backend to use.
354sub have_native_backend {
Reid Spencerf2722ca2006-03-22 15:59:55 +0000355 my %BUILT;
356 foreach my $target (@TARGETS_BUILT) { $BUILT{$target} = 1; }
Reid Spencerb195d9d2006-03-23 23:21:29 +0000357 return defined $NAME_MAP{$ARCH} && defined $BUILT{$ARCH};
358}
359
360# Find a working subclass of ExecutionEngine for this platform.
361sub find_best_engine {
362 if (have_native_backend && $TARGET_HAS_JIT) {
Reid Spencer1c070fc2006-03-24 01:10:39 +0000363 return ['jit', 'native'];
Reid Spencerf2722ca2006-03-22 15:59:55 +0000364 } else {
Reid Spencerb195d9d2006-03-23 23:21:29 +0000365 return ['interpreter'];
Reid Spencerf2722ca2006-03-22 15:59:55 +0000366 }
367}
368
369# Get all the human-friendly component names.
370sub name_map_entries {
371 load_dependencies;
372 return sort keys %NAME_MAP;
373}
374
375# Map human-readable names to internal library names.
376sub expand_names (@) {
377 my @names = @_;
378 my @result;
379 foreach my $name (@names) {
380 if (defined $LIB_TO_SET_MAP{$name}) {
381 # We've hit bottom: An actual library name.
382 push @result, $name;
383 } elsif (defined $NAME_MAP{$name}) {
384 # We've found a short name to expand.
385 push @result, expand_names(@{$NAME_MAP{$name}});
386 } else {
387 print STDERR "llvm-config: unknown component name: $name\n";
388 exit(1);
389 }
390 }
391 return @result;
392}
393
394# Given a list of internal library names, return all sets of libraries which
395# will need to be included by the linker (in no particular order).
396sub find_all_required_sets (@) {
397 my @libs = @_;
398 my %sets_added;
399 my @result;
400 find_all_required_sets_helper(\%sets_added, \@result, @libs);
401 return @result;
402}
403
404# Recursive closures are pretty broken in Perl, so we're going to separate
405# this function from find_all_required_sets and pass in the state we need
406# manually, as references. Yes, this is fairly unpleasant.
407sub find_all_required_sets_helper ($$@) {
408 my ($sets_added, $result, @libs) = @_;
409 foreach my $lib (@libs) {
410 my $set = $LIB_TO_SET_MAP{$lib};
411 next if defined $$sets_added{$set};
412 $$sets_added{$set} = 1;
413 push @$result, $set;
414 find_all_required_sets_helper($sets_added, $result, @{$SET_DEPS{$set}});
415 }
416}
417
418# Print a list of sets, with a label. Used for debugging.
419sub print_sets ($@) {
420 my ($label, @sets) = @_;
421 my @output;
422 foreach my $set (@sets) { push @output, join(',', @$set); }
423 print "$label: ", join(';', @output), "\n";
424}
425
426# Returns true if $lib is a key in $added.
427sub has_lib_been_added ($$) {
428 my ($added, $lib) = @_;
429 return defined $$added{$LIB_TO_SET_MAP{$lib}};
430}
431
432# Returns true if all the dependencies of $set appear in $added.
433sub have_all_deps_been_added ($$) {
434 my ($added, $set) = @_;
435 #print_sets(" Checking", $set);
436 #print_sets(" Wants", $SET_DEPS{$set});
437 foreach my $lib (@{$SET_DEPS{$set}}) {
438 return 0 unless has_lib_been_added($added, $lib);
439 }
440 return 1;
441}
442
443# Given a list of sets, topologically sort them using dependencies.
444sub topologically_sort_sets (@) {
445 my @sets = @_;
446 my %added;
447 my @result;
448 SCAN: while (@sets) { # We'll delete items from @sets as we go.
449 #print_sets("So far", reverse(@result));
450 #print_sets("Remaining", @sets);
451 for (my $i = 0; $i < @sets; ++$i) {
452 my $set = $sets[$i];
453 if (have_all_deps_been_added(\%added, $set)) {
454 push @result, $set;
455 $added{$set} = 1;
456 #print "Removing $i.\n";
457 splice(@sets, $i, 1);
458 next SCAN; # Restart our scan.
459 }
460 }
461 die "Can't find a library with no dependencies";
462 }
463 return reverse(@result);
464}
465
Reid Spencerf2722ca2006-03-22 15:59:55 +0000466# Our library dependency data will be added after the '__END__' token, and will
467# be read through the magic <DATA> filehandle.
468__END__