rt/lib/RT/DependencyWalker.pm

   1 # BEGIN BPS TAGGED BLOCK {{{
   2 #
   3 # COPYRIGHT:
   4 #
   5 # This software is Copyright (c) 1996-2017 Best Practical Solutions, LLC
   6 #                                          <sales@bestpractical.com>
   7 #
   8 # (Except where explicitly superseded by other copyright notices)
   9 #
  10 #
  11 # LICENSE:
  12 #
  13 # This work is made available to you under the terms of Version 2 of
  14 # the GNU General Public License. A copy of that license should have
  15 # been provided with this software, but in any event can be snarfed
  16 # from www.gnu.org.
  17 #
  18 # This work is distributed in the hope that it will be useful, but
  19 # WITHOUT ANY WARRANTY; without even the implied warranty of
  20 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21 # General Public License for more details.
  22 #
  23 # You should have received a copy of the GNU General Public License
  24 # along with this program; if not, write to the Free Software
  25 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  26 # 02110-1301 or visit their web page on the internet at
  27 # http://www.gnu.org/licenses/old-licenses/gpl-2.0.html.
  28 #
  29 #
  30 # CONTRIBUTION SUBMISSION POLICY:
  31 #
  32 # (The following paragraph is not intended to limit the rights granted
  33 # to you to modify and distribute this software under the terms of
  34 # the GNU General Public License and is only of importance to you if
  35 # you choose to contribute your changes and enhancements to the
  36 # community by submitting them to Best Practical Solutions, LLC.)
  37 #
  38 # By intentionally submitting any modifications, corrections or
  39 # derivatives to this work, or any other work intended for use with
  40 # Request Tracker, to Best Practical Solutions, LLC, you confirm that
  41 # you are the copyright holder for those contributions and you grant
  42 # Best Practical Solutions,  LLC a nonexclusive, worldwide, irrevocable,
  43 # royalty-free, perpetual, license to use, copy, create derivative
  44 # works based on those contributions, and sublicense and distribute
  45 # those contributions and any derivatives thereof.
  46 #
  47 # END BPS TAGGED BLOCK }}}
  48
  49 package RT::DependencyWalker;
  50
  51 use strict;
  52 use warnings;
  53
  54 use RT::DependencyWalker::FindDependencies;
  55 use Carp;
  56
  57 sub new {
  58     my $class = shift;
  59     my $self = bless {}, $class;
  60     $self->Init(@_);
  61     return $self;
  62 }
  63
  64 sub Init {
  65     my $self = shift;
  66     my %args = (
  67         First          => "top",
  68         GC             => 0,
  69         Page           => 100,
  70         Progress       => undef,
  71         MessageHandler => \&Carp::carp,
  72         @_
  73     );
  74
  75     $self->{first}    = $args{First};
  76     $self->{GC}       = $args{GC};
  77     $self->{Page}     = $args{Page};
  78     $self->{progress} = $args{Progress};
  79     $self->{msg}      = $args{MessageHandler},
  80     $self->{stack}    = [];
  81 }
  82
  83 sub PushObj {
  84     my $self = shift;
  85     push @{$self->{stack}}, { object => $_ }
  86         for @_;
  87 }
  88
  89 sub Walk {
  90     my $self = shift;
  91
  92     $self->PushObj( @_ );
  93
  94     # Ensure that RT::Ticket's ->Load doesn't follow a merged ticket to
  95     # the ticket it was merged into.
  96     no warnings 'redefine';
  97     local *RT::Ticket::Load = sub {
  98         my $self = shift;
  99         my $id   = shift;
 100         $self->LoadById( $id );
 101         return $self->Id;
 102     };
 103
 104     # When we walk ticket links, find deleted tickets as well
 105     local *RT::Links::IsValidLink = sub {
 106         my $self = shift;
 107         my $link = shift;
 108         return unless $link && ref $link && $link->Target && $link->Base;
 109         return 1;
 110     };
 111
 112     $self->{visited} = {};
 113     $self->{seen}    = {};
 114     $self->{gc_count} = 0;
 115
 116     my $stack = $self->{stack};
 117     while (@{$stack}) {
 118         my %frame = %{ shift @{$stack} };
 119         $self->{top}     = [];
 120         $self->{replace} = [];
 121         $self->{bottom}  = [];
 122         my $ref = $frame{object};
 123         if ($ref->isa("RT::Record")) {
 124             $self->Process(%frame);
 125         } else {
 126             unless ($ref->{unrolled}) {
 127                 $ref->FindAllRows;
 128                 $ref->RowsPerPage( $self->{Page} );
 129                 $ref->FirstPage;
 130                 $ref->{unrolled}++;
 131             }
 132             my $last;
 133             while (my $obj = $ref->DBIx::SearchBuilder::Next) {
 134                 $last = $obj->Id;
 135                 $self->Process(%frame, object => $obj );
 136             }
 137             if (defined $last) {
 138                 $self->NextPage($ref => $last);
 139                 push @{$self->{replace}}, \%frame;
 140             }
 141         }
 142         unshift @{$stack}, @{$self->{replace}};
 143         unshift @{$stack}, @{$self->{top}};
 144         push    @{$stack}, @{$self->{bottom}};
 145
 146         if ($self->{GC} > 0 and $self->{gc_count} > $self->{GC}) {
 147             $self->{gc_count} = 0;
 148             require Time::HiRes;
 149             my $start_time = Time::HiRes::time();
 150             $self->{msg}->("Starting GC pass...");
 151             my $start_size = @{$self->{stack}};
 152             @{ $self->{stack} } = grep {
 153                 $_->{object}->isa("RT::Record")
 154                     ? not exists $self->{visited}{$_->{uid} ||= $_->{object}->UID}
 155                     : ( $_->{has_results} ||= do {
 156                         $_->{object}->FindAllRows;
 157                         $_->{object}->RowsPerPage(1);
 158                         $_->{object}->Count;
 159                     } )
 160             } @{ $self->{stack} };
 161             my $end_time = Time::HiRes::time();
 162             my $end_size = @{$self->{stack}};
 163             my $size = $start_size - $end_size;
 164             my $time = $end_time - $start_time;
 165             $self->{msg}->(
 166                 sprintf(
 167                     "GC -- %d removed, %.2f seconds, %d/s",
 168                     $size, $time, int($size/$time)
 169                 )
 170             );
 171         }
 172     }
 173     $self->{progress}->(undef, 'force') if $self->{progress};
 174 }
 175
 176 sub NextPage {
 177     my $self        = shift;
 178     my $collection  = shift;
 179
 180     $collection->NextPage;
 181 }
 182
 183 sub Process {
 184     my $self = shift;
 185     my %args = (
 186         object    => undef,
 187         direction => undef,
 188         from      => undef,
 189         @_
 190     );
 191
 192     my $obj = $args{object};
 193     return if $obj->isa("RT::System");
 194
 195     my $uid = $obj->UID;
 196     unless ($uid) {
 197         warn "$args{direction} from $args{from} to $obj is an invalid reference";
 198         return;
 199     }
 200     $self->{progress}->($obj) if $self->{progress};
 201     if (exists $self->{visited}{$uid}) {
 202         # Already visited -- no-op
 203         $self->Again(%args);
 204     } elsif (exists $obj->{satisfied}) {
 205         # All dependencies visited -- time to visit
 206         $self->Visit(%args);
 207         $self->{visited}{$uid}++;
 208     } elsif (exists $self->{seen}{$uid}) {
 209         # All of the dependencies are on the stack already.  We may not
 210         # have gotten to them, but we will eventually.  This _may_ be a
 211         # cycle, but true cycle detection is too memory-intensive, as it
 212         # requires keeping track of the history of how each dep got
 213         # added to the stack, all of the way back.
 214         $self->ForcedVisit(%args);
 215         $self->{visited}{$uid}++;
 216     } else {
 217         # Nothing known about this previously; add its deps to the
 218         # stack, then objects it refers to.
 219         return if defined $args{from}
 220             and not $self->Observe(%args);
 221         my $deps = RT::DependencyWalker::FindDependencies->new;
 222         $obj->FindDependencies($self, $deps);
 223         # Shove it back for later
 224         push @{$self->{replace}}, \%args;
 225         if ($self->{first} eq "top") {
 226             # Top-first; that is, visit things we point to first,
 227             # then deal with us, then deal with things that point to
 228             # us.  For serialization.
 229             $self->PrependDeps( out => $deps, $uid );
 230             $self->AppendDeps(  in  => $deps, $uid );
 231         } else {
 232             # Bottom-first; that is, deal with things that point to
 233             # us first, then deal with us, then deal with things we
 234             # point to.  For removal.
 235             $self->PrependDeps( in => $deps, $uid );
 236             $self->AppendDeps( out => $deps, $uid );
 237         }
 238         $obj->{satisfied}++;
 239         $self->{seen}{$uid}++;
 240         $self->{gc_count}++ if $self->{GC} > 0;
 241     }
 242 }
 243
 244 sub Observe { 1 }
 245
 246 sub Again {}
 247
 248 sub Visit {}
 249
 250 sub ForcedVisit {
 251     my $self = shift;
 252     $self->Visit( @_ );
 253 }
 254
 255 sub AppendDeps {
 256     my $self = shift;
 257     my ($dir, $deps, $from) = @_;
 258     for my $obj (@{$deps->{$dir}}) {
 259         if (not defined $obj) {
 260             warn "$dir from $from contained an invalid reference";
 261             next;
 262         } elsif ($obj->isa("RT::Record")) {
 263             warn "$dir from $from to $obj is an invalid reference" unless $obj->UID;
 264             next if $self->{GC} < 0 and exists $self->{seen}{$obj->UID};
 265         } else {
 266             $obj->FindAllRows;
 267             if ($self->{GC} < 0) {
 268                 $obj->RowsPerPage(1);
 269                 next unless $obj->Count;
 270             }
 271         }
 272         push @{$self->{bottom}}, {
 273             object    => $obj,
 274             direction => $dir,
 275             from      => $from,
 276         };
 277     }
 278 }
 279
 280 sub PrependDeps {
 281     my $self = shift;
 282     my ($dir, $deps, $from) = @_;
 283     for my $obj (@{$deps->{$dir}}) {
 284         if (not defined $obj) {
 285             warn "$dir from $from contained an invalid reference";
 286             next;
 287         } elsif ($obj->isa("RT::Record")) {
 288             warn "$dir from $from to $obj is an invalid reference" unless $obj->UID;
 289             next if $self->{GC} < 0 and exists $self->{visited}{$obj->UID};
 290         } else {
 291             $obj->FindAllRows;
 292             if ($self->{GC} < 0) {
 293                 $obj->RowsPerPage(1);
 294                 next unless $obj->Count;
 295             }
 296         }
 297         unshift @{$self->{top}}, {
 298             object    => $obj,
 299             direction => $dir,
 300             from      => $from,
 301         };
 302     }
 303 }
 304
 305 1;