Missing bug summaries in dependencytree view w/ depth limit

RESOLVED FIXED in Bugzilla 2.16

Status

()

Bugzilla
User Interface
P2
normal
RESOLVED FIXED
17 years ago
6 years ago

People

(Reporter: Andreas Franke (gone), Assigned: Andreas Franke (gone))

Tracking

2.15
Bugzilla 2.16
All
Other

Details

(Whiteboard: [have hack for 2.16])

Attachments

(1 attachment)

(Assignee)

Description

17 years ago
The summaries of some bugs (e.g. 98278) are missing on this page: 
http://bugzilla.mozilla.org/showdependencytree.cgi?id=103705&maxdepth=2&hide_resolved=1

This is an interaction between the patch for bug 104652 and the depth control;
the first hit on the bug is below the depth rendered, but we don't notice.
Priority: -- → P2
Target Milestone: --- → Bugzilla 2.16
I've looked at this, and can't see immediately how to fix it - which is
annoying. Afranke - do you have any insights here?

Gerv
(Assignee)

Comment 2

17 years ago
The origin of the problem here is that we are doing two things during the
recursion:
1.) printing the bugs that the user should see
2.) doing a full recursion to find the actual tree depth

The second thing is only needed for the "<" and ">" buttons to work in cases
where the user has not specified a max_depth for the actual query (and in some
circumstances to decide whether some of the depth control buttons are disabled).

I think before the depth control was introduced, %seen was designed to mean what
%printed means now: "We have already processed this bug, so let's not do it over
and over again."

Anyway, the current computation of $realdepth has some oddities (correct me if
I'm wrong):

- it depends on the order in which the dependencies are processed (but then, the
whole html output depends on this order, so it may not be that bad): Assume the
dependency graph is this: a-->b, a-->c, b-->c, c-->d. This can be represented as
 
a-->b-->c-->d
 \
  \                           (depth 3; this happens when #b < #c)
   >c (occurs elsewhere)

or

a-->c-->d
 \ 
  \                           (depth 2; this happens when #c < #b)
   >b-->c (occurs elsewhere)

I think ideally the depth should always be the maximum. This could be achieved
by remembering the actual subtree depth for each node, instead of just a boolean
flag indicating an already visited node.
Another thing: maybe the loss by limiting the tree depth should be minimized.
This could be achieved by always showing the full subtree at the occurrence with
the least distance from the root node (i.e. at the first occurrence in a
breadth-first traversal of the tree, not at the first occurrence in a
depth-first traversal as it is now). In any case, there should be a named anchor
at the occurrence where the full subtree is shown, and there should be links to
this anchor from all other occurrences. 
[Alternatively, if this algorithm is too confusing for the user and it is
decided that the first occurrence in the depth-first traversal should stay the
one with the full subtree, then the depth limit could be ignored (or extended)
in cases where it would be possible to choose another occurrence where the
subtree could be displayed with a larger depth without violating the user's
depth limit. But maybe this is even more confusing.]

My conclusion from this is: It's probably better to separate the parts of our
algorithm more clearly. We could distinguish the following steps:

1. In any case, compute the complete graph by doing a standard depth-first
traversal, using a %seen (or %visited) hash to avoid doing multiple recursions
from the same node.

2. Compute the $realdepth of this graph, maybe as the maximum path length.
   (Or, instead of this, do 3a later.)

3. Compute a (depth-limited) tree representation of the graph, maybe in a way
that the given depth limit does not cut more bugs than necessary.

[3a. Instead of 2., $realdepth could be computed as the maximum path length in
the tree generated by 3. This way, $realdepth would have the same meaning as it
has now.]

4. Now display this tree, with links to the "main" occurrence from "proxy"
occurrences.

Of course, this will result in a rewrite of showdependency.cgi...
(Assignee)

Comment 3

17 years ago
As a quick improvement, it may make things a bit better if you replace 
$seen{$kid} with $printed{$kid} here:

154                 if (exists $seen{$kid}) {     
155                     $short_desc = "&lt;<em>This bug appears elsewhere in
this tree</em>&gt;";
156                 }

I haven't tested it, though. Also, in order not of not losing the dependencies,
it may be necessary to change something in a recursion condition from $seen{...}
to $printed{...} but this will be more than a one-liner. And still I'm not sure
how to get it right. The best thing would be a cleanup/rewrite. But until then,
the above change may make things a bit better.


No patch, not a blocker, -> 2.18

This is annoying though, if we get a patch in the next few days I'll reconsider
for 2.16.
Target Milestone: Bugzilla 2.16 → Bugzilla 2.18
(Assignee)

Comment 5

17 years ago
Created attachment 69128 [details] [diff] [review]
Replace check for $seen{$kid} with check for $printed{$kid}

This is the hack I described above. I'm not sure whether this solved this bug
completely (so I'd rather leave it open for a while when this gets checked in),
but to me it is plausible, and some preliminary testing shows that it is an
improvement wrt. the current situation.
(Assignee)

Updated

17 years ago
Keywords: patch, review
Whiteboard: [have hack for 2.16]
Target Milestone: Bugzilla 2.18 → Bugzilla 2.16
Comment on attachment 69128 [details] [diff] [review]
Replace check for $seen{$kid} with check for $printed{$kid}

I'm not sure why seen != printed (do we really need the maximum depth of the
tree?), but in any even this fixes it on a quick test case.

r=bbaetz
Attachment #69128 - Flags: review+
Comment on attachment 69128 [details] [diff] [review]
Replace check for $seen{$kid} with check for $printed{$kid}

It can't make things worse :-)

Gerv
(Assignee)

Comment 8

17 years ago
bbaetz: in the unlimited case, we compute the real tree depth so that the "<"
button works as advertized: re-display the tree, but with the depth limit
reduced by one. If we did not know the real tree depth, we would have to compute
"unlimited (=infinite) - 1 = unlimited (=infinite)", so the "<" button would not
have any effect, which may be unexpected. Otherwise the button would have to be
disabled.
But I agree that it's not a core feature, so a rewrite may break it.
-> patch author
Assignee: gerv → afranke
Checking in showdependencytree.cgi;
/cvsroot/mozilla/webtools/bugzilla/showdependencytree.cgi,v  <-- 
showdependencytree.cgi
new revision: 1.14; previous revision: 1.13
done
I meant to hit FIXED there I really did...
Status: NEW → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → FIXED

Comment 12

15 years ago
Re: comment 2

This is still an issue - e.g.
http://bugzilla.mozilla.org/showdependencytree.cgi?id=163993&hide_resolved=1
compare the listings of bug 53597 at depths 2, 3 and unlimited.

I agree, a breadth-first traversal would be a good approach.  Is there a bug
report buried somewhere on implementing this?
QA Contact: matty_is_a_geek → default-qa
You need to log in before you can comment on or make changes to this bug.