[nem-bug] [Nemerle 0000875]: StackOverflowException inside ncc, if there is a circular depenedcy in source

[feedback at nemerle.org]

The following issue has been RESOLVED.
======================================================================
<http://nemerle.org/bugs/view.php?id=875> 
======================================================================
Reported By:                nikov
Assigned To:                VladD2
======================================================================
Project:                    Nemerle
Issue ID:                   875
Category:                   Compiler
Reproducibility:            always
Severity:                   major
Priority:                   normal
Status:                     resolved
Resolution:                 fixed
Fixed in Version:           
======================================================================
Date Submitted:             02-05-2007 16:36 CET
Last Modified:              02-12-2007 02:41 CET
======================================================================
Summary:                    StackOverflowException inside ncc, if there is a
circular depenedcy in source
Description: 
module A{
	public Foo[T,S](x : T) : void where T : S where S : T {
        _ = x.Foo()
    }
}
======================================================================

----------------------------------------------------------------------
 nazgul - 02-05-07 20:22 
----------------------------------------------------------------------
We need a graph cycle detection algorithm here. Any volunteers?

----------------------------------------------------------------------
 VladD2 - 02-05-07 22:42 
----------------------------------------------------------------------
Maybe simply add all dependency in Hashtable? If some exists in Hashtable
thin we have cycle.

----------------------------------------------------------------------
 nazgul - 02-05-07 22:48 
----------------------------------------------------------------------
No, this must be full-featured graph traversal check:

class A [x,y,z,w] : where x : y where y : z where w : z, w : x { }  // OK

class A [x,y,z,w] : where x : y where y : z where w : z where z : y { } 
// ERROR

The algorithm is simple: 
- create graph with parameters as nodes
- fill it by constraints as edges
- traverse it using DFS detecting cycles

But having a (generic) graph component would be nice.

----------------------------------------------------------------------
 VladD2 - 02-05-07 23:20 
----------------------------------------------------------------------
I think graph can be represent as Hashtable or as array.

----------------------------------------------------------------------
 nazgul - 02-05-07 23:23 
----------------------------------------------------------------------
Whatever, probably the best is  class Graph ['a] { edges :
array[array[int]]; 
  nodes : array ['a] ... }

or  array [SCG.List [int]]

----------------------------------------------------------------------
 VladD2 - 02-06-07 06:51 
----------------------------------------------------------------------
Fixed in 7388.

----------------------------------------------------------------------
 nikov - 02-11-07 18:53 
----------------------------------------------------------------------
False positive.

module A{
	public Foo[T,S,U](x : T) : void where S : T where U: S, T {
    }
}

----------------------------------------------------------------------
 VladD2 - 02-12-07 02:41 
----------------------------------------------------------------------
Fix in 4707.

Issue History
Date Modified  Username       Field                    Change              
======================================================================
02-05-07 16:36 nikov          New Issue                                    
02-05-07 20:22 nazgul         Note Added: 0001693                          
02-05-07 22:42 VladD2         Note Added: 0001694                          
02-05-07 22:48 nazgul         Note Added: 0001695                          
02-05-07 23:20 VladD2         Note Added: 0001698                          
02-05-07 23:23 nazgul         Note Added: 0001700                          
02-06-07 06:51 VladD2         Status                   new => resolved     
02-06-07 06:51 VladD2         Resolution               open => fixed       
02-06-07 06:51 VladD2         Assigned To               => VladD2          
02-06-07 06:51 VladD2         Note Added: 0001701                          
02-06-07 06:51 VladD2         Description Updated                          
02-11-07 18:53 nikov          Status                   resolved => feedback
02-11-07 18:53 nikov          Resolution               fixed => reopened   
02-11-07 18:53 nikov          Note Added: 0001709                          
02-11-07 18:53 nikov          Description Updated                          
02-12-07 02:41 VladD2         Status                   feedback => resolved
02-12-07 02:41 VladD2         Resolution               reopened => fixed   
02-12-07 02:41 VladD2         Note Added: 0001712                          
======================================================================