# group-checks -- lintian check script -*- perl -*-

# Copyright (C) 2011 Niels Thykier <niels@thykier.net>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, you can find it on the World Wide
# Web at http://www.gnu.org/copyleft/gpl.html, or write to the Free
# Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
# MA 02110-1301, USA.

package Lintian::group_checks;
use strict;
use warnings;

use Lintian::Tags qw(tag);
use Lintian::Data;

my $KNOWN_PRIOS = Lintian::Data->new ('common/priorities', qr/\s*=\s*/o);

sub run {

my $pkg = shift;
my $type = shift;
my $info = shift;
my $proc = shift;
my $group = shift;

## To find circular dependencies, we will first generate
## Strongly Connected Components using Tarjan's algorithm
##
## We are not using DepMap, because it cannot tell how the
## circles are made - only that there exists at least 1
## circle.

# The packages a.k.a. nodes
my @nodes = ();
my %edges = ();
my $sccs;
my $ginfo = $group->info;
my @procs = $group->get_processables ('binary');

_check_file_overlap (@procs);

foreach my $proc (@procs) {
    my $deps = $ginfo->direct_dependencies ($proc);
    if (scalar @$deps > 0) {
        # it depends on another package - it can cause
        # a circular dependency
        my $pname = $proc->pkg_name;
        push @nodes, $pname;
        $edges{$pname} = [map { $_->pkg_name } @$deps];
        _check_priorities ($proc, $deps);
        _check_multiarch ($proc, $deps);
    }
}

# Bail now if we do not have at least two packages depending
# on some other package from this source.
return if scalar @nodes < 2;

$sccs = Lintian::group_checks::Graph->new(\@nodes, \%edges)->tarjans();

foreach my $comp (@$sccs) {
    # It takes two to tango... erh. make a circular dependency.
    next if scalar @$comp < 2;
    tag 'intra-source-package-circular-dependency', sort @$comp;
}


}

# Check that $proc has a priority that is less than or equal to that
# of its dependencies (Policy §2.5)
sub _check_priorities {
    my ($proc, $deps) = @_;
    my $priority = $proc->info->field ('priority');
    my $pkg_name = $proc->pkg_name;
    if ($priority) {
        my $prival = $KNOWN_PRIOS->value ($priority);
        foreach my $dep (@$deps) {
            my $dpri = $dep->info->field ('priority') // '';
            my $dprival = $KNOWN_PRIOS->value ($dpri);
            # Ignore packages without priorities - we have a separate
            # check for that.
            next unless $dprival;
            tag 'package-depends-on-lower-priority-package', "$pkg_name:$priority",
                'depends on', $dep->pkg_name . ":$dpri"
                    unless $prival <= $dprival;
        }
    }
}

sub _check_file_overlap {
    my (@procs) = @_;
    # Sort them for stable output
    my @sorted = sort { $a->pkg_name cmp $b->pkg_name } @procs;
    for (my $i = 0 ; $i < scalar @sorted ; $i++) {
        my $proc = $sorted[$i];
        my $pinfo = $proc->info;
        for (my $j = $i ; $j < scalar @sorted ; $j++) {
            my $other = $sorted[$j];
            my $oinfo = $other->info;
            # poor man's "Multi-arch: same" work-around.
            next if $proc->pkg_name eq $other->pkg_name;

            # $other conflicts/replaces with $proc
            next if $oinfo->relation ('conflicts')->implies ($proc->pkg_name);
            next if $oinfo->relation ('replaces')->implies ($proc->pkg_name);

            # $proc conflicts/replaces with $other
            next if $pinfo->relation ('conflicts')->implies ($other->pkg_name);
            next if $pinfo->relation ('replaces')->implies ($other->pkg_name);

            _overlap_check ($proc, $pinfo, $other, $oinfo);
        }
    }
}

sub _overlap_check {
    my ($a_proc, $a_info, $b_proc, $b_info) = @_;
    my $b_index = $b_info->index;
    foreach my $raw (@{ $a_info->sorted_index }) {
        my $file;
        my $a_file;
        my $b_file;
        next unless $raw;
        $file = $raw; # copy, because we have to modifiy it
        $file =~ s,/$,,o;
        $b_file = $b_index->{$file} // $b_index->{"$file/"};
        if ($b_file) {
            $a_file = $a_info->index->{$file} // $a_info->index->{"$file/"};
            next if $a_file->{type} eq $b_file->{type} && $a_file->{type} eq 'd';
            tag 'binaries-have-file-conflict', $a_proc->pkg_name, $b_proc->pkg_name, $file;
        }
    }
}

sub _check_multiarch {
    my ($proc, $deps) = @_;
    my $ma = $proc->info->field('multi-arch') // 'no';
    if ($ma eq 'same') {
        foreach my $dep (@$deps) {
            my $dma = $dep->info->field('multi-arch') // 'no';
            if ($dma eq 'same' or $dma eq 'foreign') {
                1; # OK
            } else {
                tag 'dependency-is-not-multi-archified', $proc->pkg_name . " depends on " . $dep->pkg_name . " (multi-arch: $dma)";
            }
        }
    }
}

## Encapsulate Tarjan's algorithm in an class/object to keep
## the run sub somewhat sane.
package Lintian::group_checks::Graph;

sub new {
    my ($type, $nodes, $edges) = @_;
    my $self = { nodes => $nodes, edges => $edges};
    bless $self, $type;
    return $self;
}

sub tarjans {
    my ($self) = @_;
    my $nodes = $self->{nodes};
    $self->{index} = 0;
    $self->{scc} = [];
    $self->{stack} = [];
    $self->{on_stack} = {};
    # The information for each node:
    #  $self->{node_info}->{$node}->[X], where X is:
    #    0 => index
    #    1 => low_index
    $self->{node_info} = {};
    foreach my $node (@$nodes) {
        $self->_tarjans_sc($node)
            unless defined $self->{node_info}->{$node};
    }
    return $self->{scc};
}

sub _tarjans_sc{
    my ($self, $node) = @_;
    my $index = $self->{index};
    my $stack = $self->{stack};
    my $ninfo = [$index, $index];
    my $on_stack = $self->{on_stack};
    $self->{node_info}->{$node} = $ninfo;
    $index++;
    $self->{index} = $index;
    push @$stack, $node;
    $on_stack->{$node} = 1;
    foreach my $neighbour (@{ $self->{edges}->{$node} }){
        my $nb_info;
        $nb_info = $self->{node_info}->{$neighbour};
        if (!defined $nb_info){
            # First time visit
            $self->_tarjans_sc($neighbour);
            # refresh $nb_info
            $nb_info = $self->{node_info}->{$neighbour};
            # min($node.low_index, $neigh.low_index)
            $ninfo->[1] = $nb_info->[1] if $nb_info->[1] < $ninfo->[1];
        } elsif (exists $on_stack->{$neighbour})  {
            # Node is in this component
            # min($node.low_index, $neigh.index)
            $ninfo->[1] = $nb_info->[0] if $nb_info->[0] < $ninfo->[1];
        }
    }
    if ($ninfo->[0] == $ninfo->[1]){
        # the "root" node - create the SSC.
        my $component = [];
        my $scc = $self->{scc};
        my $elem = '';
        do {
            $elem = pop @$stack;
            delete $on_stack->{$elem};
            push @$component, $elem;
        } until $node eq $elem;
        push @$scc, $component;
    }
}

1;

# Local Variables:
# indent-tabs-mode: nil
# cperl-indent-level: 4
# End:
# vim: syntax=perl sw=4 sts=4 sr et