| 1 | package App::cpm::CircularDependency; | ||
| 2 | use v5.24; | ||
| 3 | use warnings; | ||
| 4 | use experimental qw(lexical_subs signatures); | ||
| 5 | |||
| 6 | use App::cpm::Util 'uniq'; | ||
| 7 | |||
| 8 | package App::cpm::CircularDependency::_OrderedSet { | ||
| 9 | sub new ($class) { | ||
| 10 | bless { index => 0, hash => +{} }, $class; | ||
| 11 | } | ||
| 12 | sub add ($self, $name) { | ||
| 13 | $self->{hash}{$name} = $self->{index}++; | ||
| 14 | } | ||
| 15 | sub exists ($self, $name) { | ||
| 16 | exists $self->{hash}{$name}; | ||
| 17 | } | ||
| 18 | sub values ($self) { | ||
| 19 | sort { $self->{hash}{$a} <=> $self->{hash}{$b} } keys $self->{hash}->%*; | ||
| 20 | } | ||
| 21 | sub clone ($self) { | ||
| 22 | my $new = (ref $self)->new; | ||
| 23 | $new->add($_) for $self->values; | ||
| 24 | $new; | ||
| 25 | } | ||
| 26 | } | ||
| 27 | |||
| 28 | sub new ($class) { | ||
| 29 | bless { _tmp => {} }, $class; | ||
| 30 | } | ||
| 31 | |||
| 32 | sub add ($self, $distfile, $provides, $requirements) { | ||
| 33 | $self->{_tmp}{$distfile} = +{ | ||
| 34 | provides => [ map $_->{package}, $provides->@* ], | ||
| 35 | requirements => [ map $_->{package}, $requirements->@* ], | ||
| 36 | }; | ||
| 37 | } | ||
| 38 | |||
| 39 | sub finalize ($self) { | ||
| 40 | for my $distfile (sort keys $self->{_tmp}->%*) { | ||
| 41 | $self->{$distfile} = [ | ||
| 42 | uniq map $self->_find($_), $self->{_tmp}{$distfile}{requirements}->@* | ||
| 43 | ]; | ||
| 44 | } | ||
| 45 | delete $self->{_tmp}; | ||
| 46 | return; | ||
| 47 | } | ||
| 48 | |||
| 49 | sub _find ($self, $package) { | ||
| 50 | for my $distfile (sort keys $self->{_tmp}->%*) { | ||
| 51 | if (grep { $_ eq $package } $self->{_tmp}{$distfile}{provides}->@*) { | ||
| 52 | return $distfile; | ||
| 53 | } | ||
| 54 | } | ||
| 55 | return; | ||
| 56 | } | ||
| 57 | |||
| 58 | sub detect ($self) { | ||
| 59 | my %result; | ||
| 60 | for my $distfile (sort keys $self->%*) { | ||
| 61 | my $seen = App::cpm::CircularDependency::_OrderedSet->new; | ||
| 62 | $seen->add($distfile); | ||
| 63 | if (my $detected = $self->_detect($distfile, $seen)) { | ||
| 64 | $result{$distfile} = $detected; | ||
| 65 | } | ||
| 66 | } | ||
| 67 | return \%result; | ||
| 68 | } | ||
| 69 | |||
| 70 | sub _detect ($self, $distfile, $seen) { | ||
| 71 | for my $req ($self->{$distfile}->@*) { | ||
| 72 | if ($seen->exists($req)) { | ||
| 73 | return [$seen->values, $req]; | ||
| 74 | } | ||
| 75 | |||
| 76 | my $clone = $seen->clone; | ||
| 77 | $clone->add($req); | ||
| 78 | if (my $detected = $self->_detect($req, $clone)) { | ||
| 79 | return $detected; | ||
| 80 | } | ||
| 81 | } | ||
| 82 | return; | ||
| 83 | } | ||
| 84 | |||
| 85 | 1; |