1 # This module is part of debbugs, and is released
2 # under the terms of the GPL version 2, or any later
3 # version at your option.
4 # See the file README and COPYING for more information.
6 # [Other people have contributed to this file; their copyrights should
9 package Debbugs::Versions;
15 Debbugs::Versions - debbugs version information processing
19 The Debbugs::Versions module provides generic support functions for the
20 implementation of version tracking in debbugs.
22 Complex organizations, such as Debian, require the tracking of bugs in
23 multiple versions of packages. The versioning scheme is frequently branched:
24 for example, a security update announced by an upstream developer will be
25 packaged as-is for the unstable distribution while a minimal backport is
26 made to the stable distribution. In order to report properly on the bugs
27 open in each distribution, debbugs must be aware of the structure of the
28 version tree for each package.
30 Gathering the version data is beyond the scope of this module: in the case
31 of Debian it is carried out by mechanical analysis of package changelogs.
32 Debbugs::Versions takes version data for a package generated by this or any
33 other means, merges it into a tree structure, and allows the user to perform
34 queries based on supplied data about the versions in which bugs have been
35 found and the versions in which they have been fixed.
39 The data format looks like this (backslashes are not actually there, and
40 indicate continuation lines):
42 1.5.4 1.5.0 1.5-iwj.0.4 1.5-iwj.0.3 1.5-iwj.0.2 1.5-iwj.0.1 1.4.0 1.3.14 \
43 1.3.13 1.3.12 1.3.11 1.3.10 ...
44 1.4.1.6 1.4.1.5 1.4.1.4 1.4.1.3 1.4.1.2 1.4.1.1 1.4.1 1.4.0.31 1.4.0.30 \
45 1.4.0.29 1.4.0.28 1.4.0.27 1.4.0.26.0.1 1.4.0.26 1.4.0.25 1.4.0.24 \
46 1.4.0.23.2 1.4.0.23.1 1.4.0.23 1.4.0.22 1.4.0.21 1.4.0.20 1.4.0.19 \
47 1.4.0.18 1.4.0.17 1.4.0.16 1.4.0.15 1.4.0.14 1.4.0.13 1.4.0.12 \
48 1.4.0.11 1.4.0.10 1.4.0.9 1.4.0.8 1.4.0.7 1.4.0.6 1.4.0.5 1.4.0.4 \
49 1.4.0.3 1.4.0.2 1.4.0.1 1.4.0 \
50 1.4.0.35 1.4.0.34 1.4.0.33 1.4.0.32 1.4.0.31
58 Constructs a Debbugs::Versions object. The argument is a reference to a
59 version comparison function, which must be usable by Perl's built-in C<sort>
67 my $class = ref($this) || $this;
69 my $self = { parent => {}, vercmp => $vercmp };
70 return bless $self, $class;
75 Takes two arguments, C<ancestor> and C<descendant>. Returns true if and only
76 if C<ancestor> is a version on which C<descendant> is based according to the
77 version data supplied to this object. (As a degenerate case, this relation
78 is reflexive: a version is considered to be an ancestor of itself.)
80 This method is expected mainly to be used internally by the C<merge> method.
88 my $descendant = shift;
90 my $parent = $self->{parent};
91 for (my $node = $descendant; defined $node; $node = $parent->{$node}) {
92 return 1 if $node eq $ancestor;
100 Find the leaves of the version tree, i.e. those versions with no
103 This method is mainly for internal use.
111 my $parent = $self->{parent};
112 my @vers = keys %$parent;
114 @leaf{@vers} = (1) x @vers;
116 delete $leaf{$parent->{$v}} if defined $parent->{$v};
123 Merges one branch of version data into this object. This branch takes the
124 form of a list of versions, each of which is to be considered as based on
125 the next in the list.
134 for my $i (1 .. $#_) {
136 next if $self->isancestor($last, $_[$i]);
138 # If it's already an ancestor version, don't add it again. This
139 # keeps the tree correct when we get several partial branches, such
140 # as '1.4.0 1.3.14 1.3.13 1.3.12' followed by '1.4.0 1.3.12 1.3.10'.
141 unless ($self->isancestor($_[$i], $last)) {
142 $self->{parent}{$last} = $_[$i];
147 # Insert undef for the last version so that we can tell a known version
148 # by seeing if it exists in $self->{parent}.
149 $self->{parent}{$_[$#_]} = undef unless exists $self->{parent}{$_[$#_]};
154 Loads version data from the filehandle passed as the argument. Each line of
155 input is expected to represent one branch, with versions separated by
172 Outputs the version tree represented by this object to the filehandle passed
173 as the argument. The format is the same as that expected by the C<load>
183 my $parent = $self->{parent};
185 # TODO: breaks with tcp-wrappers/1.0-1 tcpd/2.0-1 case
186 my @leaves = reverse sort {
187 my ($x, $y) = ($a, $b);
190 $self->{vercmp}->($x, $y);
194 for my $lf (@leaves) {
197 for (my $node = $parent->{$lf}; defined $node;
198 $node = $parent->{$node}) {
200 last if exists $seen{$node};
209 Takes three arguments, C<version>, C<found>, and C<fixed>. Returns true if
210 and only if C<version> is based on or equal to a version in the list
211 referenced by C<found>, and not based on or equal to one referenced by
214 C<buggy> attempts to cope with found and fixed versions not in the version
215 tree by simply checking whether any fixed versions are recorded in the event
216 that nothing is known about any of the found versions.
227 my %found = map { $_ => 1 } @$found;
228 my %fixed = map { $_ => 1 } @$fixed;
229 my $parent = $self->{parent};
230 for (my $node = $version; defined $node; $node = $parent->{$node}) {
231 # The found and fixed tests are this way round because the most
232 # likely scenario is that somebody thought they'd fixed a bug and
233 # then it was reopened because it turned out not to have been fixed
234 # after all. However, tools that build found and fixed lists should
235 # generally know the order of events and make sure that the two
236 # lists have no common entries.
237 return 'found' if $found{$node};
238 return 'fixed' if $fixed{$node};
242 # We don't know when it was found. Was it fixed in a descendant of
243 # this version? If so, this one should be considered buggy.
244 for my $f (@$fixed) {
245 for (my $node = $f; defined $node; $node = $parent->{$node}) {
246 return 'found' if $node eq $version;
251 # Nothing in the requested version's ancestor chain can be confirmed as
252 # a version in which the bug was found or fixed. If it was only found or
253 # fixed on some other branch, then this one isn't buggy.
254 for my $f (@$found, @$fixed) {
255 return 'absent' if exists $parent->{$f};
258 # Otherwise, we degenerate to checking whether any fixed versions at all
260 return 'fixed' if @$fixed;
266 Takes two arguments, C<found> and C<fixed>, which are interpreted as in
267 L</buggy>. Efficiently returns the state of the bug at every known version,
268 in the form of a hash from versions to states (as returned by L</buggy>). If
269 you pass a third argument, C<interested>, this method will stop after
270 determining the state of the bug at all the versions listed therein.
272 Whether this is faster than calling L</buggy> for each version you're
273 interested in is not altogether clear, and depends rather strongly on the
274 number of known and interested versions.
278 sub allstates ($$$;$)
283 my $interested = shift;
285 my %found = map { $_ => 1 } @$found;
286 my %fixed = map { $_ => 1 } @$fixed;
288 if (defined $interested) {
289 %interested = map { $_ => 1 } @$interested;
291 my $parent = $self->{parent};
292 my @leaves = $self->leaves();
294 # Are any of the found or fixed versions known? We'll need this later.
296 for my $f (@$found, @$fixed) {
297 if (exists $parent->{$f}) {
303 # Start at each leaf in turn, working our way up and remembering the
304 # list of versions in the branch.
306 LEAF: for my $lf (@leaves) {
310 for (my $node = $lf; defined $node; $node = $parent->{$node}) {
311 # If we're about to start a new branch, check whether we know
312 # the state of every version in which we're interested. If so,
314 if (defined $interested and not @branch) {
316 for my $interest (keys %interested) {
317 if (exists $state{$interest}) {
318 push @remove, $interest;
321 delete @interested{@remove};
322 last LEAF unless keys %interested;
325 # We encounter a version whose state we already know. Record the
326 # branch with the same state as that version, and go on to the
328 if (exists $state{$node}) {
329 $state{$_} = $state{$node} foreach @branch;
335 # We encounter a version in the found list. Record the branch as
336 # 'found', and start a new branch.
338 $state{$_} = 'found' foreach @branch;
342 # We encounter a version in the fixed list. Record the branch as
343 # 'fixed', and start a new branch, remembering that we have a
345 elsif ($fixed{$node}) {
346 $state{$_} = 'fixed' foreach @branch;
351 # We encounter a root.
352 elsif (not defined $parent->{$node}) {
353 # If the found list is empty and we have a fixed descendant,
354 # record the branch as 'found' (since they probably just
355 # forgot to report a version when opening the bug).
356 if (not @$found and $fixeddesc) {
357 $state{$_} = 'found' foreach @branch;
360 # If any of the found or fixed versions are known, record
361 # the branch as 'absent' (since all the activity must have
362 # happened on some other branch).
364 $state{$_} = 'absent' foreach @branch;
367 # If there are any fixed versions at all (but they're
368 # unknown), then who knows, but we guess at recording the
371 $state{$_} = 'fixed' foreach @branch;
374 # Otherwise, fall back to recording the branch as 'found'.
376 $state{$_} = 'found' foreach @branch;
379 # In any case, we're done.