Stefano Mazzocchi <[EMAIL PROTECTED]>:
>
> Hunsberger, Peter wrote:
>
> > Stefano Mazzocchi <[EMAIL PROTECTED]> writes:
> >
> > <snip/>
> >
> >>I have a RT ready for gump that would allow to solve these
> >>issues... but
> >>I need to work more on this since it appears to be a pretty tough
> >>computational problem of graph analysis.
> >
> >
> > We do have generalized hedge generator code (both in a Cocoon sense
> > and in a flat query to data structure sense) that I might
> be able to
> > get you a copy of ;-)... However, I suspect you need the
> opposite of
> > what we have; something to break down tree structured data
> into hedges
> > and look for intersections (cycles)?
>
> oh, nono, the problem is completely different: when a project doesn't
> compile, who's fault is that?
>
> Currently gump has information such as
>
> (A) --(depends on)--> (B)
>
> the problem with this is that if A breaks, it could be because of B's
> fault or because of A's fault, you can't tell.
>
> What I'm going to propose is to have bidimensional dependencies:
>
> (A,20040302) --(depends on)--> (B,20040212)
>
> At this point, gump can do multiple builds based on the
> timestamp and it
> is possible figure out who broke what and when, in theory
> point at the
> very single commit to blame.
>
> The problem is that the complexity of such trellis grows very
> big very
> quickly. I still have to understand if it's duable at all!
Hmm, so, for any random initial state it is possible that:
A -(depends on)-> C
B -(depends on)-> C
And that a single change to C fixes A but breaks B, thus, you add the
timestamp...
If so, it's still the same problem, just more data (which is perhaps the
entire issue?): find all the (perhaps arbitrary) tree roots that either
give a good build or are the most recent version of the code for which a
breakage still exists. If you've got a good build you can prune all
prior timestamps. If you always have breakage you can prune all prior
timestamps. (In the above example, you'd need to retain two versions,
but no more, if everything else dependant on C built properly with
either version.)
However, even with the pruned tree I'm not sure if the problem is
solvable in general: IIUC there is no known general algorithm for cyclic
graph traversal that can be guaranteed to terminate (for any random
graph)? If however, you can force a known initial state (always start
from the same spot on the graph) then perhaps things are a little more
hopeful? Not sure, I think you're on your own on this one...
