[Bug dynamic-link/15311] _dl_sort_fini static deps can be violated by dynamic ones

["dhatch at ilm dot com" <sourceware-bugzilla@sourceware.org>]

http://sourceware.org/bugzilla/show_bug.cgi?id=15311

--- Comment #6 from Don Hatch <dhatch at ilm dot com> 2013-03-28 05:00:18 UTC ---
(In reply to comment #3)
> If you do topologic sort it should suffice to take static dependency
> edges before dynamic ones, it assures that static when static are acyclic then
> they are always correctly ordered.

Hi Ondrej,

I'm sorry, I just realized that in my previous reply to this comment of yours,
I outlined my strategy without actually addressing your simpler proposal at
all.

I don't think what you are suggesting will work.
If I'm reading it correctly, you're saying that, when iterating through
the successors of a given node, consider static successors first
and dynamic onces after that.

Here is an example where that doesn't work:
    Static dependencies: A->B->C->D->E
    Dynamic dependencies: E->A
In this case each node has exactly one successor (static or dynamic),
so the order in which successors are considered clearly makes no difference.
If the depth-first-search happens to start at C,
it will produce the output (reverse postordering): C D E A B.
The correct answer is A B C D E.

My strategy works properly on this example (of course :-)):
first pass (topsort static+dynamic) produces arbitrary output,
since it's all one big SCC;
second pass (topsort static only) produces correct order A B C D E.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.