Putting 4.2.0 on top of 4.0.17
[usit-rt.git] / lib / RT / DependencyWalker.pm
1 # BEGIN BPS TAGGED BLOCK {{{
2 #
3 # COPYRIGHT:
4 #
5 # This software is Copyright (c) 1996-2013 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::Dependencies;
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;