{- # -*- Mode: perl -*-

 use File::Basename;

 my $debug_resolvedepends = $ENV{BUILDFILE_DEBUG_DEPENDS};
 my $debug_rules = $ENV{BUILDFILE_DEBUG_RULES};

 # A cache of objects for which a recipe has already been generated
 my %cache;

 # collectdepends, expanddepends and reducedepends work together to make
 # sure there are no duplicate or weak dependencies and that they are in
 # the right order.  This is used to sort the list of libraries  that a
 # build depends on.
 sub extensionlesslib {
     my @result = map { $_ =~ /(\.a)?$/; $` } @_;
     return @result if wantarray;
     return $result[0];
 }

 # collectdepends dives into the tree of dependencies and returns
 # a list of all the non-weak ones.
 sub collectdepends {
     return () unless @_;

     my $thing = shift;
     my $extensionlessthing = extensionlesslib($thing);
     my @listsofar = @_;    # to check if we're looping
     my @list = @{$unified_info{depends}->{$thing} //
                      $unified_info{depends}->{$extensionlessthing}};
     my @newlist = ();

     print STDERR "DEBUG[collectdepends] $thing > ", join(' ', @listsofar), "\n"
         if $debug_resolvedepends;
     foreach my $item (@list) {
         my $extensionlessitem = extensionlesslib($item);
         # It's time to break off when the dependency list starts looping
         next if grep { extensionlesslib($_) eq $extensionlessitem } @listsofar;
         # Don't add anything here if the dependency is weak
         next if defined $unified_info{attributes}->{depends}->{$thing}->{$item}->{'weak'};
         my @resolved = collectdepends($item, @listsofar, $item);
         push @newlist, $item, @resolved;
     }
     print STDERR "DEBUG[collectdepends] $thing < ", join(' ', @newlist), "\n"
         if $debug_resolvedepends;
     @newlist;
 }

 # expanddepends goes through a list of stuff, checks if they have any
 # dependencies, and adds them at the end of the current position if
 # they aren't already present later on.
 sub expanddepends {
     my @after = ( @_ );
     print STDERR "DEBUG[expanddepends]> ", join(' ', @after), "\n"
         if $debug_resolvedepends;
     my @before = ();
     while (@after) {
         my $item = shift @after;
         print STDERR "DEBUG[expanddepends]\\  ", join(' ', @before), "\n"
             if $debug_resolvedepends;
         print STDERR "DEBUG[expanddepends] - ", $item, "\n"
             if $debug_resolvedepends;
         my @middle = (
             $item,
             map {
                 my $x = $_;
                 my $extlessx = extensionlesslib($x);
                 if (grep { $extlessx eq extensionlesslib($_) } @before
                     and
                     !grep { $extlessx eq extensionlesslib($_) } @after) {
                     print STDERR "DEBUG[expanddepends] + ", $x, "\n"
                         if $debug_resolvedepends;
                     ( $x )
                 } else {
                     print STDERR "DEBUG[expanddepends] ! ", $x, "\n"
                         if $debug_resolvedepends;
                     ()
                 }
             } @{$unified_info{depends}->{$item} // []}
         );
         print STDERR "DEBUG[expanddepends] = ", join(' ', @middle), "\n"
             if $debug_resolvedepends;
         print STDERR "DEBUG[expanddepends]/  ", join(' ', @after), "\n"
             if $debug_resolvedepends;
         push @before, @middle;
     }
     print STDERR "DEBUG[expanddepends]< ", join(' ', @before), "\n"
         if $debug_resolvedepends;
     @before;
 }

 # reducedepends looks through a list, and checks if each item is
 # repeated later on.  If it is, the earlier copy is dropped.
 sub reducedepends {
     my @list = @_;
     print STDERR "DEBUG[reducedepends]> ", join(' ', @list), "\n"
         if $debug_resolvedepends;
     my @newlist = ();
     my %replace = ();
     while (@list) {
         my $item = shift @list;
         my $extensionlessitem = extensionlesslib($item);
         if (grep { $extensionlessitem eq extensionlesslib($_) } @list) {
             if ($item ne $extensionlessitem) {
                 # If this instance of the library is explicitly static, we
                 # prefer that to any shared library name, since it must have
                 # been done on purpose.
                 $replace{$extensionlessitem} = $item;
             }
         } else {
             push @newlist, $item;
         }
     }
     @newlist = map { $replace{$_} // $_; } @newlist;
     print STDERR "DEBUG[reducedepends]< ", join(' ', @newlist), "\n"
         if $debug_resolvedepends;
     @newlist;
 }

 # Do it all
 # This takes multiple inputs and combine them into a single list of
 # interdependent things.  The returned value will include all the input.
 # Callers are responsible for taking away the things they are building.
 sub resolvedepends {
     print STDERR "DEBUG[resolvedepends] START (", join(', ', @_), ")\n"
         if $debug_resolvedepends;
     my @all =
         reducedepends(expanddepends(map { ( $_, collectdepends($_) ) } @_));
     print STDERR "DEBUG[resolvedepends] END (", join(', ', @_), ") : ",
         join(',', map { "\n    $_" } @all), "\n"
         if $debug_resolvedepends;
     @all;
 }

 # dogenerate is responsible for producing all the recipes that build
 # generated source files.  It recurses in case a dependency is also a
 # generated source file.
 sub dogenerate {
     my $src = shift;
     return "" if $cache{$src};
     my $obj = shift;
     my $bin = shift;
     my %opts = @_;
     if ($unified_info{generate}->{$src}) {
         die "$src is generated by Configure, should not appear in build file\n"
             if ref $unified_info{generate}->{$src} eq "";
         my $script = $unified_info{generate}->{$src}->[0];
         $OUT .= generatesrc(src => $src,
                             product => $bin,
                             generator => $unified_info{generate}->{$src},
                             generator_incs => $unified_info{includes}->{$script},
                             generator_deps => $unified_info{depends}->{$script},
                             deps => $unified_info{depends}->{$src},
                             incs => [ @{$unified_info{includes}->{$obj}},
                                       @{$unified_info{includes}->{$bin}} ],
                             defs => [ @{$unified_info{defines}->{$obj}},
                                       @{$unified_info{defines}->{$bin}} ],
                             %opts);
         foreach (@{$unified_info{depends}->{$src}}) {
             dogenerate($_, $obj, $bin, %opts);
         }
     }
     $cache{$src} = 1;
 }

 # doobj is responsible for producing all the recipes that build
 # object files as well as dependency files.
 sub doobj {
     my $obj = shift;
     return "" if $cache{$obj};
     my $bin = shift;
     my %opts = @_;
     if (@{$unified_info{sources}->{$obj}}) {
         my @srcs = @{$unified_info{sources}->{$obj}};
         my @deps = @{$unified_info{depends}->{$obj}};
         my @incs = ( @{$unified_info{includes}->{$obj}},
                      @{$unified_info{includes}->{$bin}} );
         my @defs = ( @{$unified_info{defines}->{$obj}},
                      @{$unified_info{defines}->{$bin}} );
         print STDERR "DEBUG[doobj] \@srcs for $obj ($bin) : ",
             join(",", map { "\n    $_" } @srcs), "\n"
             if $debug_rules;
         print STDERR "DEBUG[doobj] \@deps for $obj ($bin) : ",
             join(",", map { "\n    $_" } @deps), "\n"
             if $debug_rules;
         print STDERR "DEBUG[doobj] \@incs for $obj ($bin) : ",
             join(",", map { "\n    $_" } @incs), "\n"
             if $debug_rules;
         print STDERR "DEBUG[doobj] \@defs for $obj ($bin) : ",
             join(",", map { "\n    $_" } @defs), "\n"
             if $debug_rules;
         print STDERR "DEBUG[doobj] \%opts for $obj ($bin) : ", ,
             join(",", map { "\n    $_ = $opts{$_}" } sort keys %opts), "\n"
             if $debug_rules;
         $OUT .= src2obj(obj => $obj, product => $bin,
                         srcs => [ @srcs ], deps => [ @deps ],
                         incs => [ @incs ], defs => [ @defs ],
                         %opts);
         foreach ((@{$unified_info{sources}->{$obj}},
                   @{$unified_info{depends}->{$obj}})) {
             dogenerate($_, $obj, $bin, %opts);
         }
     }
     $cache{$obj} = 1;
 }

 # Helper functions to grab all applicable intermediary files.
 # This is particularly useful when a library is given as source
 # rather than a dependency.  In that case, we consider it to be a
 # container with object file references, or possibly references
 # to further libraries to pilfer in the same way.
 sub getsrclibs {
     my $section = shift;

     # For all input, see if it sources static libraries.  If it does,
     # return them together with the result of a recursive call.
     map { ( $_, getsrclibs($section, $_) ) }
     grep { $_ =~ m|\.a$| }
     map { @{$unified_info{$section}->{$_} // []} }
     @_;
 }

 sub getlibobjs {
     my $section = shift;

     # For all input, see if it's an intermediary file (library or object).
     # If it is, collect the result of a recursive call, or if that returns
     # an empty list, the element itself.  Return the result.
     map {
         my @x = getlibobjs($section, @{$unified_info{$section}->{$_}});
         @x ? @x : ( $_ );
     }
     grep { defined $unified_info{$section}->{$_} }
     @_;
 }

 # dolib is responsible for building libraries.  It will call
 # obj2shlib if shared libraries are produced, and obj2lib in all
 # cases.  It also makes sure all object files for the library are
 # built.
 sub dolib {
     my $lib = shift;
     return "" if $cache{$lib};

     my %attrs = %{$unified_info{attributes}->{libraries}->{$lib}};

     my @deps = ( resolvedepends(getsrclibs('sources', $lib)) );

     # We support two types of objs, those who are specific to this library
     # (they end up in @objs) and those that we get indirectly, via other
     # libraries (they end up in @foreign_objs).  We get the latter any time
     # someone has done something like this in build.info:
     #     SOURCE[libfoo.a]=libbar.a
     # The indirect object files must be kept in a separate array so they
     # don't get rebuilt unnecessarily (and with incorrect auxiliary
     # information).
     #
     # Object files can't be collected commonly for shared and static
     # libraries, because we contain their respective object files in
     # {shared_sources} and {sources}, and because the implications are
     # slightly different for each library form.
     #
     # We grab all these "foreign" object files recursively with getlibobjs().

     unless ($disabled{shared} || $lib =~ /\.a$/) {
         my $obj2shlib = defined &obj2shlib ? \&obj2shlib : \&libobj2shlib;
         # If this library sources other static libraries and those
         # libraries are marked {noinst}, there's no need to include
         # all of their object files.  Instead, we treat those static
         # libraries as dependents alongside any other library this
         # one depends on, and let symbol resolution do its job.
         my @sourced_libs = ();
         my @objs = ();
         my @foreign_objs = ();
         my @deps = ();
         foreach (@{$unified_info{shared_sources}->{$lib}}) {
             if ($_ !~ m|\.a$|) {
                 push @objs, $_;
             } elsif ($unified_info{attributes}->{libraries}->{$_}->{noinst}) {
                 push @deps, $_;
             } else {
                 push @deps, getsrclibs('sources', $_);
                 push @foreign_objs, getlibobjs('sources', $_);
             }
         }
         @deps = ( grep { $_ ne $lib } resolvedepends($lib, @deps) );
         print STDERR "DEBUG[dolib:shlib] \%attrs for $lib : ", ,
             join(",", map { "\n    $_ = $attrs{$_}" } sort keys %attrs), "\n"
             if %attrs && $debug_rules;
         print STDERR "DEBUG[dolib:shlib] \@deps for $lib : ",
             join(",", map { "\n    $_" } @deps), "\n"
             if @deps && $debug_rules;
         print STDERR "DEBUG[dolib:shlib] \@objs for $lib : ",
             join(",", map { "\n    $_" } @objs), "\n"
             if @objs && $debug_rules;
         print STDERR "DEBUG[dolib:shlib] \@foreign_objs for $lib : ",
             join(",", map { "\n    $_" } @foreign_objs), "\n"
             if @foreign_objs && $debug_rules;
         $OUT .= $obj2shlib->(lib => $lib,
                              attrs => { %attrs },
                              objs => [ @objs, @foreign_objs ],
                              deps => [ @deps ]);
         foreach (@objs) {
             # If this is somehow a compiled object, take care of it that way
             # Otherwise, it might simply be generated
             if (defined $unified_info{sources}->{$_}) {
                 if($_ =~ /\.a$/) {
                     dolib($_);
                 } else {
                     doobj($_, $lib, intent => "shlib", attrs => { %attrs });
                 }
             } else {
                 dogenerate($_, undef, undef, intent => "lib");
             }
         }
     }
     {
         # When putting static libraries together, we cannot rely on any
         # symbol resolution, so for all static libraries used as source for
         # this one, as well as other libraries they depend on, we simply
         # grab all their object files unconditionally,
         # Symbol resolution will happen when any program, module or shared
         # library is linked with this one.
         my @objs = ();
         my @sourcedeps = ();
         my @foreign_objs = ();
         foreach (@{$unified_info{sources}->{$lib}}) {
             if ($_ !~ m|\.a$|) {
                 push @objs, $_;
             } else {
                 push @sourcedeps, $_;
             }
         }
         @sourcedeps = ( grep { $_ ne $lib } resolvedepends(@sourcedeps) );
         print STDERR "DEBUG[dolib:lib] : \@sourcedeps for $_ : ",
             join(",", map { "\n    $_" } @sourcedeps), "\n"
             if @sourcedeps && $debug_rules;
         @foreign_objs = getlibobjs('sources', @sourcedeps);
         print STDERR "DEBUG[dolib:lib] \%attrs for $lib : ", ,
             join(",", map { "\n    $_ = $attrs{$_}" } sort keys %attrs), "\n"
             if %attrs && $debug_rules;
         print STDERR "DEBUG[dolib:lib] \@objs for $lib : ",
             join(",", map { "\n    $_" } @objs), "\n"
             if @objs && $debug_rules;
         print STDERR "DEBUG[dolib:lib] \@foreign_objs for $lib : ",
             join(",", map { "\n    $_" } @foreign_objs), "\n"
             if @foreign_objs && $debug_rules;
         $OUT .= obj2lib(lib => $lib, attrs => { %attrs },
                         objs => [ @objs, @foreign_objs ]);
         foreach (@objs) {
             doobj($_, $lib, intent => "lib", attrs => { %attrs });
         }
     }
     $cache{$lib} = 1;
 }

 # domodule is responsible for building modules.  It will call
 # obj2dso, and also makes sure all object files for the library
 # are built.
 sub domodule {
     my $module = shift;
     return "" if $cache{$module};
     my %attrs = %{$unified_info{attributes}->{modules}->{$module}};
     my @objs = @{$unified_info{sources}->{$module}};
     my @deps = ( grep { $_ ne $module }
                  resolvedepends($module) );
     print STDERR "DEBUG[domodule] \%attrs for $module :",
         join(",", map { "\n    $_ = $attrs{$_}" } sort keys %attrs), "\n"
         if $debug_rules;
     print STDERR "DEBUG[domodule] \@objs for $module : ",
         join(",", map { "\n    $_" } @objs), "\n"
         if $debug_rules;
     print STDERR "DEBUG[domodule] \@deps for $module : ",
         join(",", map { "\n    $_" } @deps), "\n"
         if $debug_rules;
     $OUT .= obj2dso(module => $module,
                     attrs => { %attrs },
                     objs => [ @objs ],
                     deps => [ @deps ]);
     foreach (@{$unified_info{sources}->{$module}}) {
         # If this is somehow a compiled object, take care of it that way
         # Otherwise, it might simply be generated
         if (defined $unified_info{sources}->{$_}) {
             doobj($_, $module, intent => "dso", attrs => { %attrs });
         } else {
             dogenerate($_, undef, $module, intent => "dso");
         }
     }
     $cache{$module} = 1;
 }

 # dobin is responsible for building programs.  It will call obj2bin,
 # and also makes sure all object files for the library are built.
 sub dobin {
     my $bin = shift;
     return "" if $cache{$bin};
     my %attrs = %{$unified_info{attributes}->{programs}->{$bin}};
     my @objs = @{$unified_info{sources}->{$bin}};
     my @deps = ( grep { $_ ne $bin } resolvedepends($bin) );
     print STDERR "DEBUG[dobin] \%attrs for $bin : ",
         join(",", map { "\n    $_ = $attrs{$_}" } sort keys %attrs), "\n"
         if %attrs && $debug_rules;
     print STDERR "DEBUG[dobin] \@objs for $bin : ",
         join(",", map { "\n    $_" } @objs), "\n"
         if @objs && $debug_rules;
     print STDERR "DEBUG[dobin] \@deps for $bin : ",
         join(",", map { "\n    $_" } @deps), "\n"
         if @deps && $debug_rules;
     $OUT .= obj2bin(bin => $bin,
                     attrs => { %attrs },
                     objs => [ @objs ],
                     deps => [ @deps ]);
     foreach (@objs) {
         doobj($_, $bin, intent => "bin", attrs => { %attrs });
     }
     $cache{$bin} = 1;
 }

 # dobin is responsible for building scripts from templates.  It will
 # call in2script.
 sub doscript {
     my $script = shift;
     return "" if $cache{$script};
     $OUT .= in2script(script => $script,
                       attrs => $unified_info{attributes}->{$script},
                       sources => $unified_info{sources}->{$script});
     $cache{$script} = 1;
 }

 sub dodir {
     my $dir = shift;
     return "" if !exists(&generatedir) or $cache{$dir};
     $OUT .= generatedir(dir => $dir,
                         deps => $unified_info{dirinfo}->{$dir}->{deps},
                         %{$unified_info{dirinfo}->{$_}->{products}});
     $cache{$dir} = 1;
 }

 # Start with populating the cache with all the overrides
 %cache = map { $_ => 1 } @{$unified_info{overrides}};

 # Build mandatory generated headers
 foreach (@{$unified_info{depends}->{""}}) { dogenerate($_); }

 # Build all known libraries, modules, programs and scripts.
 # Everything else will be handled as a consequence.
 foreach (@{$unified_info{libraries}}) { dolib($_);    }
 foreach (@{$unified_info{modules}})   { domodule($_); }
 foreach (@{$unified_info{programs}})  { dobin($_);    }
 foreach (@{$unified_info{scripts}})   { doscript($_); }

 foreach (sort keys %{$unified_info{dirinfo}})  { dodir($_); }
-}