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;
17 Debbugs::Versions - debbugs version information processing
21 The Debbugs::Versions module provides generic support functions for the
22 implementation of version tracking in debbugs.
24 Complex organizations, such as Debian, require the tracking of bugs in
25 multiple versions of packages. The versioning scheme is frequently branched:
26 for example, a security update announced by an upstream developer will be
27 packaged as-is for the unstable distribution while a minimal backport is
28 made to the stable distribution. In order to report properly on the bugs
29 open in each distribution, debbugs must be aware of the structure of the
30 version tree for each package.
32 Gathering the version data is beyond the scope of this module: in the case
33 of Debian it is carried out by mechanical analysis of package changelogs.
34 Debbugs::Versions takes version data for a package generated by this or any
35 other means, merges it into a tree structure, and allows the user to perform
36 queries based on supplied data about the versions in which bugs have been
37 found and the versions in which they have been fixed.
41 The data format looks like this (backslashes are not actually there, and
42 indicate continuation lines):
44 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 \
45 1.3.13 1.3.12 1.3.11 1.3.10 ...
46 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 \
47 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 \
48 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 \
49 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 \
50 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 \
51 1.4.0.3 1.4.0.2 1.4.0.1 1.4.0 \
52 1.4.0.35 1.4.0.34 1.4.0.33 1.4.0.32 1.4.0.31
60 Constructs a Debbugs::Versions object. The argument is a reference to a
61 version comparison function, which must be usable by Perl's built-in C<sort>
69 my $class = ref($this) || $this;
71 my $self = { parent => {}, vercmp => $vercmp };
72 return bless $self, $class;
77 Takes two arguments, C<ancestor> and C<descendant>. Returns true if and only
78 if C<ancestor> is a version on which C<descendant> is based according to the
79 version data supplied to this object. (As a degenerate case, this relation
80 is reflexive: a version is considered to be an ancestor of itself.)
82 This method is expected mainly to be used internally by the C<merge> method.
90 my $descendant = shift;
92 my $parent = $self->{parent};
93 for (my $node = $descendant; defined $node; $node = $parent->{$node}) {
94 return 1 if $node eq $ancestor;
102 Find the leaves of the version tree, i.e. those versions with no
105 This method is mainly for internal use.
113 my $parent = $self->{parent};
114 my @vers = keys %$parent;
116 @leaf{@vers} = (1) x @vers;
118 delete $leaf{$parent->{$v}} if defined $parent->{$v};
125 Merges one branch of version data into this object. This branch takes the
126 form of a list of versions, each of which is to be considered as based on
127 the next in the list.
136 for my $i (1 .. $#_) {
138 next if $self->isancestor($last, $_[$i]);
140 # If it's already an ancestor version, don't add it again. This
141 # keeps the tree correct when we get several partial branches, such
142 # as '1.4.0 1.3.14 1.3.13 1.3.12' followed by '1.4.0 1.3.12 1.3.10'.
143 unless ($self->isancestor($_[$i], $last)) {
144 $self->{parent}{$last} = $_[$i];
149 # Insert undef for the last version so that we can tell a known version
150 # by seeing if it exists in $self->{parent}.
151 $self->{parent}{$_[$#_]} = undef unless exists $self->{parent}{$_[$#_]};
156 Loads version data from the filehandle passed as the argument. Each line of
157 input is expected to represent one branch, with versions separated by
174 Outputs the version tree represented by this object to the filehandle passed
175 as the argument. The format is the same as that expected by the C<load>
185 my $parent = $self->{parent};
187 # TODO: breaks with tcp-wrappers/1.0-1 tcpd/2.0-1 case
188 my @leaves = reverse sort {
189 my ($x, $y) = ($a, $b);
192 $self->{vercmp}->($x, $y);
196 for my $lf (@leaves) {
199 for (my $node = $parent->{$lf}; defined $node;
200 $node = $parent->{$node}) {
202 last if exists $seen{$node};
211 Takes three arguments, C<version>, C<found>, and C<fixed>. Returns true if
212 and only if C<version> is based on or equal to a version in the list
213 referenced by C<found>, and not based on or equal to one referenced by
216 C<buggy> attempts to cope with found and fixed versions not in the version
217 tree by simply checking whether any fixed versions are recorded in the event
218 that nothing is known about any of the found versions.
229 my %found = map { $_ => 1 } @$found;
230 my %fixed = map { $_ => 1 } @$fixed;
231 my $parent = $self->{parent};
232 for (my $node = $version; defined $node; $node = $parent->{$node}) {
233 # The found and fixed tests are this way round because the most
234 # likely scenario is that somebody thought they'd fixed a bug and
235 # then it was reopened because it turned out not to have been fixed
236 # after all. However, tools that build found and fixed lists should
237 # generally know the order of events and make sure that the two
238 # lists have no common entries.
239 return 'found' if $found{$node};
240 return 'fixed' if $fixed{$node};
244 # We don't know when it was found. Was it fixed in a descendant of
245 # this version? If so, this one should be considered buggy.
246 for my $f (@$fixed) {
247 for (my $node = $f; defined $node; $node = $parent->{$node}) {
248 return 'found' if $node eq $version;
253 # Nothing in the requested version's ancestor chain can be confirmed as
254 # a version in which the bug was found or fixed. If it was only found or
255 # fixed on some other branch, then this one isn't buggy.
256 for my $f (@$found, @$fixed) {
257 return 'absent' if exists $parent->{$f};
260 # Otherwise, we degenerate to checking whether any fixed versions at all
262 return 'fixed' if @$fixed;
268 Takes two arguments, C<found> and C<fixed>, which are interpreted as in
269 L</buggy>. Efficiently returns the state of the bug at every known version,
270 in the form of a hash from versions to states (as returned by L</buggy>). If
271 you pass a third argument, C<interested>, this method will stop after
272 determining the state of the bug at all the versions listed therein.
274 Whether this is faster than calling L</buggy> for each version you're
275 interested in is not altogether clear, and depends rather strongly on the
276 number of known and interested versions.
285 my $interested = shift;
287 my %found = map { $_ => 1 } @$found;
288 my %fixed = map { $_ => 1 } @$fixed;
290 if (defined $interested) {
291 %interested = map { $_ => 1 } @$interested;
293 my $parent = $self->{parent};
294 my @leaves = $self->leaves();
296 # Are any of the found or fixed versions known? We'll need this later.
298 for my $f (@$found, @$fixed) {
299 if (exists $parent->{$f}) {
305 # Start at each leaf in turn, working our way up and remembering the
306 # list of versions in the branch.
308 LEAF: for my $lf (@leaves) {
312 for (my $node = $lf; defined $node; $node = $parent->{$node}) {
313 # If we're about to start a new branch, check whether we know
314 # the state of every version in which we're interested. If so,
316 if (defined $interested and not @branch) {
318 for my $interest (keys %interested) {
319 if (exists $state{$interest}) {
320 push @remove, $interest;
323 delete @interested{@remove};
324 last LEAF unless keys %interested;
327 # We encounter a version whose state we already know. Record the
328 # branch with the same state as that version, and go on to the
330 if (exists $state{$node}) {
331 $state{$_} = $state{$node} foreach @branch;
337 # We encounter a version in the found list. Record the branch as
338 # 'found', and start a new branch.
340 $state{$_} = 'found' foreach @branch;
344 # We encounter a version in the fixed list. Record the branch as
345 # 'fixed', and start a new branch, remembering that we have a
347 elsif ($fixed{$node}) {
348 $state{$_} = 'fixed' foreach @branch;
353 # We encounter a root.
354 elsif (not defined $parent->{$node}) {
355 # If the found list is empty and we have a fixed descendant,
356 # record the branch as 'found' (since they probably just
357 # forgot to report a version when opening the bug).
358 if (not @$found and $fixeddesc) {
359 $state{$_} = 'found' foreach @branch;
362 # If any of the found or fixed versions are known, record
363 # the branch as 'absent' (since all the activity must have
364 # happened on some other branch).
366 $state{$_} = 'absent' foreach @branch;
369 # If there are any fixed versions at all (but they're
370 # unknown), then who knows, but we guess at recording the
373 $state{$_} = 'fixed' foreach @branch;
376 # Otherwise, fall back to recording the branch as 'found'.
378 $state{$_} = 'found' foreach @branch;
381 # In any case, we're done.