[Checkins] SVN: GenericSetup/trunk/ Fixed a sorting error (see README.txt).

[Lennart Regebro]

Log message for revision 67831:
  Fixed a sorting error (see README.txt).
  

Changed:
  U   GenericSetup/trunk/CHANGES.txt
  U   GenericSetup/trunk/registry.py
  U   GenericSetup/trunk/tests/test_registry.py

-=-
Modified: GenericSetup/trunk/CHANGES.txt
===================================================================
--- GenericSetup/trunk/CHANGES.txt	2006-05-02 10:56:10 UTC (rev 67830)
+++ GenericSetup/trunk/CHANGES.txt	2006-05-02 12:33:03 UTC (rev 67831)
@@ -1,6 +1,12 @@
 GenericSetup Product Changelog
 
   GenericSetup 1.1 (2006/04/16)
+    - The dependency sorting was highly reliant on steps being added in the
+      right order to work. If import step A depends on import step B which 
+      depends on step C, and step C gets processed early, and they were 
+      processed in the order A, C, B, then the dependency order would be 
+      incorrect. This is now fixed by keeping tack of steps with unresolved
+      dependencies, and trying again after inserting everything else.
 
     - ZCatalog handler: Implemented the 'remove' directive for indexes.
       This allows to write extension profiles that remove or replace indexes.

Modified: GenericSetup/trunk/registry.py
===================================================================
--- GenericSetup/trunk/registry.py	2006-05-02 10:56:10 UTC (rev 67830)
+++ GenericSetup/trunk/registry.py	2006-05-02 12:33:03 UTC (rev 67831)
@@ -237,17 +237,37 @@
         graph = [ ( x[ 'id' ], x[ 'dependencies' ] )
                     for x in self._registered.values() ]
 
-        for node, edges in graph:
+        unresolved = []
 
-            after = -1
+        while 1:
+            for node, edges in graph:
+    
+                after = -1
+                resolved = 0
+    
+                for edge in edges:
+    
+                    if edge in result:
+                        resolved += 1
+                        after = max( after, result.index( edge ) )
+                
+                if len(edges) > resolved:
+                    unresolved.append((node, edges))
+                else:
+                    result.insert( after + 1, node )
 
-            for edge in edges:
-
-                if edge in result:
-                    after = max( after, result.index( edge ) )
-
-            result.insert( after + 1, node )
-
+            if not unresolved:
+                break
+            if len(unresolved) == len(graph):
+                # Nothing was resolved in this loop. There must be circular or
+                # missing dependencies. Just add them to the end. We can't
+                # raise an error, because checkComplete relies on this method.
+                for node, edges in unresolved:
+                    result.append(node)
+                break
+            graph = unresolved
+            unresolved = []
+        
         return result
 
     security.declarePrivate( '_exportTemplate' )

Modified: GenericSetup/trunk/tests/test_registry.py
===================================================================
--- GenericSetup/trunk/tests/test_registry.py	2006-05-02 10:56:10 UTC (rev 67830)
+++ GenericSetup/trunk/tests/test_registry.py	2006-05-02 12:33:03 UTC (rev 67831)
@@ -152,11 +152,6 @@
         steps = registry.listSteps()
         self.assertEqual( len( steps ), 1 )
         self.failUnless( 'one' in steps )
-
-        sorted = registry.sortSteps()
-        self.assertEqual( len( sorted ), 1 )
-        self.assertEqual( sorted[ 0 ], 'one' )
-
         self.assertEqual( registry.getStep( 'one' ), ONE_FUNC )
 
         info = registry.getStepMetadata( 'one' )
@@ -274,14 +269,14 @@
         registry.registerStep( id='one'
                              , version='1'
                              , handler=ONE_FUNC
-                             , dependencies=( 'two', )
+                             , dependencies=( 'three', )
                              , title='One small step'
                              )
 
         registry.registerStep( id='two'
                              , version='2'
                              , handler=TWO_FUNC
-                             , dependencies=( 'three', )
+                             , dependencies=( 'one', )
                              , title='Texas two step'
                              )
 
@@ -291,15 +286,16 @@
                              , dependencies=()
                              , title='Gimme three steps'
                              )
-
+       
         steps = registry.sortSteps()
         self.assertEqual( len( steps ), 3 )
         one = steps.index( 'one' )
         two = steps.index( 'two' )
         three = steps.index( 'three' )
 
-        self.failUnless( 0 <= three < two < one )
+        self.failUnless( 0 <= three < one < two )
 
+
     def test_sortStep_complex( self ):
 
         registry = self._makeOne()