[Issue 4384] New: Cyclic dependency check for modules is broken

Jun 24, 2010

Steven Schveighoffer

Jun 25, 2010

Walter Bright

Jun 25, 2010

Steven Schveighoffer

Jun 25, 2010

bearophile_hugs@eml.cc

Jun 25, 2010

Steven Schveighoffer

Nov 08, 2010

Steven Schveighoffer

June 24, 2010

[Issue 4384] New: Cyclic dependency check for modules is broken

Posted by Steven Schveighoffer

Permalink

Steven Schveighoffer

Permalink

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


--- Comment #0 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-06-24 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: -------

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 --- Comment #1 from Walter Bright <bugzilla@digitalmars.com> 2010-06-25 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: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4384 Steven Schveighoffer <schveiguy@yahoo.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |REOPENED Resolution|WONTFIX | --- Comment #2 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-06-25 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: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4384 bearophile_hugs@eml.cc changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |bearophile_hugs@eml.cc --- Comment #3 from bearophile_hugs@eml.cc 2010-06-25 13:56:02 PDT --- Topological sort :-) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4384 --- Comment #4 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-06-25 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: -------

Forums