1 # BEGIN BPS TAGGED BLOCK {{{
5 # This software is Copyright (c) 1996-2017 Best Practical Solutions, LLC
6 # <sales@bestpractical.com>
8 # (Except where explicitly superseded by other copyright notices)
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
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.
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.
30 # CONTRIBUTION SUBMISSION POLICY:
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.)
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.
47 # END BPS TAGGED BLOCK }}}
49 package RT::DependencyWalker;
54 use RT::DependencyWalker::FindDependencies;
59 my $self = bless {}, $class;
71 MessageHandler => \&Carp::carp,
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},
85 push @{$self->{stack}}, { object => $_ }
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 {
100 $self->LoadById( $id );
104 # When we walk ticket links, find deleted tickets as well
105 local *RT::Links::IsValidLink = sub {
108 return unless $link && ref $link && $link->Target && $link->Base;
112 $self->{visited} = {};
114 $self->{gc_count} = 0;
116 my $stack = $self->{stack};
118 my %frame = %{ shift @{$stack} };
120 $self->{replace} = [];
121 $self->{bottom} = [];
122 my $ref = $frame{object};
123 if ($ref->isa("RT::Record")) {
124 $self->Process(%frame);
126 unless ($ref->{unrolled}) {
128 $ref->RowsPerPage( $self->{Page} );
133 while (my $obj = $ref->DBIx::SearchBuilder::Next) {
135 $self->Process(%frame, object => $obj );
138 $self->NextPage($ref => $last);
139 push @{$self->{replace}}, \%frame;
142 unshift @{$stack}, @{$self->{replace}};
143 unshift @{$stack}, @{$self->{top}};
144 push @{$stack}, @{$self->{bottom}};
146 if ($self->{GC} > 0 and $self->{gc_count} > $self->{GC}) {
147 $self->{gc_count} = 0;
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);
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;
167 "GC -- %d removed, %.2f seconds, %d/s",
168 $size, $time, int($size/$time)
173 $self->{progress}->(undef, 'force') if $self->{progress};
178 my $collection = shift;
180 $collection->NextPage;
192 my $obj = $args{object};
193 return if $obj->isa("RT::System");
197 warn "$args{direction} from $args{from} to $obj is an invalid reference";
200 $self->{progress}->($obj) if $self->{progress};
201 if (exists $self->{visited}{$uid}) {
202 # Already visited -- no-op
204 } elsif (exists $obj->{satisfied}) {
205 # All dependencies visited -- time to visit
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}++;
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 );
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 );
239 $self->{seen}{$uid}++;
240 $self->{gc_count}++ if $self->{GC} > 0;
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";
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};
267 if ($self->{GC} < 0) {
268 $obj->RowsPerPage(1);
269 next unless $obj->Count;
272 push @{$self->{bottom}}, {
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";
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};
292 if ($self->{GC} < 0) {
293 $obj->RowsPerPage(1);
294 next unless $obj->Count;
297 unshift @{$self->{top}}, {