#!/usr/bin/perl

# We must have a stable sort algorithm, or else our multiple layared criteria won't work.
use sort 'stable';

# This file parses the "winxp_sample_map.html" file as generated by Dave Miller on
# February 2nd, 2003, with the sole exception that each <br> was replaced by <br>\n.
#
# This parser is copyright (c) 2003 by Shachar Shemesh, and may be freely distributed
# under the terms of the GNU Lesser Public License version 2.1. You may, at your
# option, use any later version of the license, provided that that version was, at
# one time or another, adopted as the official license for the "Wine" project.

($#ARGV >= 0) or die "Usage: parse filename\n";

sub getdll($)
{
    my $dllname=shift;

    $dllname=~m{system(32)?/(\S*) imports:} or return;

    $dllname=lc($2);

    # Make sure we are not dealing with a duplicate of the DLL
    if( $dllname=~m{^dllcache/} )
    {
        return "";
    }

    # Trim the "dll" extension
    $dllname!~/(.*)\.dll/ or $dllname=$1;
   
    # Trim the directory name
    $dllname!~m{/([^/]*)$} or $dllname=$1;

    return $dllname;
}

# first thing's first - read in all the DLLs
open (HTML_FILE, "<$ARGV[0]") or die "Couldn't open file $ARGV[0]\n";

while( <HTML_FILE> )
{
    if( $dllname=getdll($_) )
    {
        # Add our newly found DLL to the list
        $dllnames[$#dllnames+1]=$dllname;
    }
}

@dllnames = sort @dllnames;

for( $i=0; $i<=$#dllnames; ++$i )
{
    $dllloc{$dllnames[$i]}=$i;
    $dllrefed[$i]=0;
}

# Now that we know how much DLLs we have, we can start filling in the cross reference.
# @dllxref is a $#dllnames x $#dllnames size array. The major index ($i*$#dllnames) is the DLL we
# are talking about (from the alphabetical list), and the minor index is the DLL it imports.
seek HTML_FILE, 0, 0;

while( <HTML_FILE> )
{
    if( defined($dllname=getdll($_)) )
    {
        # We are on a line defining a new DLL
        $currdll=$dllloc{$dllname};
    } elsif( m{<a href="#([\w\.]*)">} )
    {
        $dllname=$1;

        # Trim the "dll" extension
        $dllname!~/(.*)\.dll/ or $dllname=$1;

        if( defined($currdll) )
        {
            $dependon=$dllloc{$dllname};
            if( defined $dependon )
            {
                $dllxref[$currdll*$#dllnames+$dependon]=1; # 1 - static. 2 - dynamic. 3 - both. Always static
            } else
            {
                print "DLL $dllnames[$currdll] depends on DLL $dllname, which does not exist\n";
            }
        }
    }
}

for( $i=0; $i <= $#dllnames ; ++$i )
{
    $dllranks[$i]=$i;

    for( $j=0; $j <= $#dllnames ; ++$j )
    {
        # Count how many DLLs point at $i
        $dllxref[$j*$#dllnames+$i] and ++$dllrefed[$i];
    }
}

@dllranks = sort { $dllrefed[$b] <=> $dllrefed[$a] } @dllranks;

sub advance
# Advance $_[1] to be at $_[2]
{
    my $i, $moved;

    if( $_[0]>$_[1] )
    {
        $moved=$dllranks[$_[0]];

        for( $i=$_[0]; $i>$_[1]; --$i )
        {
            $dllranks[$i]=$dllranks[$i-1];
        }
        
        $dllranks[$_[1]]=$moved;
    }
}

# Make sure that no DLL is lower than the DLLs that depend on it
DEPENDSCAN: for( my $i=0; $i<=$#dllnames; ++$i )
{
    for( my $j=$i+1; $j<=$#dllnames; ++$j )
    {
        if( $dllxref[$dllranks[$i]*$#dllnames+$dllranks[$j]] and
                !$dllxref[$dllranks[$j]*$#dllnames+$dllranks[$i]] )
        {
            # $i is higher than $j, depends on it, and $j does not depend on $i.
            # Promote $j to take $i's place, and push everyone else down.
            advance( $j, $i );
            redo DEPENDSCAN;
        }
    }
}

foreach my $i (@dllranks)
{
    print "$dllnames[$i] $dllrefed[$i]\n"
}