www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4384] New: Cyclic dependency check for modules is broken

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4384

           Summary: Cyclic dependency check for modules is broken
           Product: D
           Version: D1 & D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: major
          Priority: P2
         Component: druntime
        AssignedTo: sean invisibleduck.org
        ReportedBy: schveiguy yahoo.com



07:07:15 PDT ---
Example code that compiles/runs but results in undetermined behavior:

mod1.d:
public import mod2;
public import mod3;
import std.stdio;

void main()
{
    writefln("x = %d, y = %d", x, y);
}

mod2.d:
import mod1;

__gshared int x = 1;

static this()
{
    x = y;
}

mod3.d:
import mod1;

__gshared int y = 2;

static this()
{
    y = x;
}

The problem stems from the code assuming that an import with no static
ctors/dtors is "finished" after the first time it is encountered.  This is done
because "trivial" cycles are allowed, that is, cycles that involve only one
module with static ctors/dtors.  Such cycles are ok because a module can
trivially depend on itself or other modules without ctors/dtors.  However, when
a cycle requires going through such a module (sans ctor/dtor) twice as in the
above example, it will not be detected.

The logical way around this is to remove those nodes from the dependency graph,
forwarding all edges to incoming connections.  Such an algorithm would be an
O(n^2) task.  I don't know if there's a way to do this without creating a
separate table.  If the compiler could generate transitive dependencies, then
we could do this trivially by just skipping those modules.  But I'm pretty sure
that's can be impossible if the modules are not compiled together.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 24 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4384


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |bugzilla digitalmars.com
         Resolution|                            |WONTFIX



13:25:04 PDT ---
Module dependencies are solely based on the import statements and the existence
of static constructors. Beyond that, it's the responsibility of the programmer
to order things. In particular, the contents of the static constructors are not
considered. Doing so is beyond the current scope of the language.

Won't fix.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4384


Steven Schveighoffer <schveiguy yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|WONTFIX                     |



13:37:13 PDT ---
No, this can be fixed.  It has nothing to do with the contents of the static
ctors/dtors, the problem is that the cycle detection algorithm is broken (it
fails to detect non-trivial cycles).

The question to answer is if the compiler can generate a transitive dependency
list.

That is, if module a depends on b, and module b depends on c, then module a
depends on c.  Can this be detected at compile time?

If so, then the compiler can generate a full list, and the topographical sort
of the modules can be very easy without allocating extra space.

If not, then we can still solve the problem by first eliminating unneeded
modules from the list.

My guess is that the compiler cannot generate such a list, but if I"m wrong,
then the compiler can improve startup performance by generating the list.

Right now, the runtime incorrectly allows cycles which can result in undefined
behavior when D specifically is supposed to disallow import cycles, regardless
of ctor/dtor contents.  I can fix this, and keep the algorithm complexity the
same, but it's a bit awkward and requires allocating memory.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4384


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc



Topological sort :-)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4384




13:59:22 PDT ---
No, topographical.  I plan to use GPS coordinates and everything :D

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 25 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4384


Steven Schveighoffer <schveiguy yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |FIXED



06:31:00 PST ---
Fixed in changeset http://www.dsource.org/projects/druntime/changeset/414

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 08 2010