#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;

my @patches;
my %state;
my %order;
my %touches; # { patch => file => 1 }
my %conflicts; # { patch 1 => { patch that patch 1 conflicts with => 1 } }

my $dumpfile = "/tmp/patchdeps.dat";

if (@ARGV > 0) {
    open(my $in, "<", $dumpfile) or die "open $dumpfile: $!";
    no strict;
    my $data = eval do { local $/; <$in> };
    @patches = @{ $data->{patches} };
    %state = %{ $data->{state} };
    %order = %{ $data->{order} };
    %touches = %{ $data->{touches} };
    %conflicts = %{ $data->{conflicts} };
} else {
    open(my $patches, "hg qseries -v |");
    while(<$patches>) {
        chomp;
        if (/^\s*(\d+) (\w+) (.*)/) {
            push @patches, $3;
            $state{$3} = $2;
            $order{$3} = $1;
        }
    }

    chomp(my $top = qx(hg root --mq));
    for my $patch (@patches) {
#        print STDERR "Scanning $patch...\n";
#        open(my $stat, "hg show --stat $patch |");
        open(my $stat, "diffstat -p1 $top/$patch |");
        while(<$stat>) {
            chomp;
            if (/^ (\D.*?)\s+\|/) {
                my $file = $1;
                $touches{$patch}{$file} = 1;
            }
        }
    }

    for my $patch (@patches) {
        for my $file (keys %{ $touches{$patch} }) {
            for my $i (reverse 0..$order{$patch}-1) {
                if ($touches{$patches[$i]}{$file}) {
                    $conflicts{$patch}{$patches[$i]} = 1;
                }
            }
        }
    }
}

sub patchnode {
    my ($patch) = @_;
    return "P$order{$patch}";
}

# dot format output. Kinda useless.
if (0) {
    print "digraph ConflictMap {\n";
    print "node [shape=box]\n";

    for my $patch (@patches) {
        print patchnode($patch) . " [label=\"$order{$patch}: $patch\"]\n";
        for my $conflict (keys %{ $conflicts{$patch} }) {
            print patchnode($patch) . " -> " . patchnode($conflict) . "\n";
        }
    }

    print "}\n";
}

# - Distinguish between full blocks and partial blocks? (whether *all* files
#   are conflicted, or only some, which means that a later patch might only
#   conflict with the remaining files...)

open(my $tmp, ">", $dumpfile) or die "create $dumpfile: $!";
print $tmp Dumper({ patches => \@patches,
                    conflicts => \%conflicts,
                    state => \%state,
                    order => \%order,
                    touches => \%touches,
                  });
close $tmp;

my @screen;

sub init_screen {
    my ($width, $height) = @_;
    @screen = (scalar(' ' x $width)) x $height;
}

sub draw_horiz {
    my ($y, $x0, $x1) = @_;
    for my $x ($x0 .. $x1) {
        substr($screen[$y], $x, 1) = '-';
    }
}

my %chart_vmap = ( ' ' => '|',
                   '-' => '-',
                   '\'' => '+',
                   '' => '|' );

sub draw_vert {
    my ($x, $y0, $y1, $map) = @_;
    ($y0, $y1) = ($y1, $y0) if $y1 < $y0;

    for my $y ($y0 .. $y1) {
        my $old = substr($screen[$y], $x, 1);
        substr($screen[$y], $x, 1) = $map->{$old} // $map->{''} // $old;
    }
}

sub title {
    my ($patch) = @_;
    return $state{$patch} . " " . $patch;
}

my $start = 0;
my $maxneed = 0;
for my $patch (@patches) {
    my $name = title($patch);
    my $need = length($name) + 2 * (@patches - $order{$patch});
    if ($need > $maxneed) {
        $maxneed = $need;
        $start = length($name);
    }
}
$start += 2; # Leading space and dash (looks bad if you immediately turn up)

my $X_GAP = 2;
my $Y_SPACING = 1;

sub y_of {
    my ($patch) = @_;
    return $order{$patch} * $Y_SPACING + 1;
}

my @x_offsets;
sub x_of {
    my ($patch) = @_;
    $x_offsets[$order{$patch}] + $start;
}

print "Note: This is based on filename collisions only, so may overreport conflicts\n";
print "if patches touch different parts of the same file. (TODO)\n";

my $simple_vmap = { '-' => '\'',
                    '' => '|' };

# Patches that don't conflict with anything before them don't get a vertical
# line. So compute the x offsets of everything.
my @width;
PATCH: for my $i (0 .. $#patches) {
    for my $j (reverse 0 .. $i - 1) {
        if ($conflicts{$patches[$i]}{$patches[$j]}) {
            $width[$i] = $X_GAP;
            next PATCH;
        }
    }
}

my $x = 0;
for (0 .. $#patches) {
    $x_offsets[$_] = $x;
    $x += $width[$_] || 0;
}

init_screen(x_of($patches[-1]) + 1, y_of($patches[-1]) + 1);

for my $patch (@patches) {
    my $i = $order{$patch};
    my $name = title($patch);
    substr($screen[$i * $Y_SPACING + 1], 0, length($name)) = $name;

    my $start = length($name);

    my $last_conflict;
    my $first_conflict;
    for my $j (reverse 0 .. $i - 1) {
        if ($conflicts{$patch}{$patches[$j]}) {
            $last_conflict ||= $patches[$j];
            $first_conflict = $patches[$j];
        }
    }

    next if ! $width[$i];

    draw_horiz(y_of($patch), $start, x_of($patch));

    draw_vert(x_of($patch), y_of($patch), y_of($last_conflict) + 1, $simple_vmap);

    for my $j (reverse 0 .. $order{$patch} - 1) {
        my $conflict = $patches[$j];
        if ($conflicts{$patch}{$conflict}) {
            # Mark each conflict with an 'x' (nearest conflict gets an 'X')
            my $mark = ($conflict eq $last_conflict) ? 'X' : 'x';
            draw_vert(x_of($patch), y_of($conflict), y_of($conflict), { '' => $mark });
        }
    }

    draw_vert(x_of($patch), y_of($patch), y_of($first_conflict), { ' ' => ':', '' => undef });
}

print "$_\n" for @screen;