[Checkins] SVN: zc.resourcelibrary/trunk/src/zc/resourcelibrary/ Bugfix: use a proper topological sort for pulling in resource library

[Marius Gedminas]

Log message for revision 70892:
  Bugfix: use a proper topological sort for pulling in resource library
  dependencies.
  
  

Changed:
  U   zc.resourcelibrary/trunk/src/zc/resourcelibrary/publication.py
  U   zc.resourcelibrary/trunk/src/zc/resourcelibrary/tests.py

-=-
Modified: zc.resourcelibrary/trunk/src/zc/resourcelibrary/publication.py
===================================================================
--- zc.resourcelibrary/trunk/src/zc/resourcelibrary/publication.py	2006-10-23 14:52:36 UTC (rev 70891)
+++ zc.resourcelibrary/trunk/src/zc/resourcelibrary/publication.py	2006-10-23 15:07:38 UTC (rev 70892)
@@ -109,26 +109,17 @@
         return super(Response, self)._implicitResult(body)
 
     def _addDependencies(self, resource_libraries):
-        # avoid side effects by copying the list before modifying it
-        resource_libraries = list(resource_libraries)
-        # add any libraries that the explicitly referenced
-        # libraries require
-        libs = list(resource_libraries)
-        while libs:
-            lib = libs.pop()
+        result = []
+        def add_lib(lib):
+            if lib in result:
+                return # Nothing to do
             try:
                 required = zc.resourcelibrary.getRequired(lib)
             except KeyError:
                 raise RuntimeError('Unknown resource library: "%s"' % lib)
-            for lib in required:
-                if lib not in resource_libraries:
-                    resource_libraries.append(lib)
-                    libs.append(lib)
-
-        # reverse the order of the libs in order to have the
-        # dependencies first. TODO: this does not work if the
-        # dependency is needed directly in the page before the
-        # dependent lib is needed.
-        resource_libraries.reverse()
-        return resource_libraries
-
+            for other in required:
+                add_lib(other)
+            result.append(lib)
+        for lib in resource_libraries:
+            add_lib(lib)
+        return result

Modified: zc.resourcelibrary/trunk/src/zc/resourcelibrary/tests.py
===================================================================
--- zc.resourcelibrary/trunk/src/zc/resourcelibrary/tests.py	2006-10-23 14:52:36 UTC (rev 70891)
+++ zc.resourcelibrary/trunk/src/zc/resourcelibrary/tests.py	2006-10-23 15:07:38 UTC (rev 70892)
@@ -1,10 +1,71 @@
 import doctest
 import unittest
 from zope.testing.doctestunit import DocTestSuite
+
+from zc.resourcelibrary import resourcelibrary
+from zc.resourcelibrary.resourcelibrary import LibraryInfo
+
+
+def setUp(test):
+    test.old_library_info = resourcelibrary.library_info
+    resourcelibrary.library_info = library_info = {}
+    # Dependencies:
+    #
+    #  libA   libD
+    #     \    /
+    #    libB /
+    #       \/
+    #      libC
+    #
+    library_info['libA'] = LibraryInfo()
+    library_info['libA'].required.append('libB')
+    library_info['libB'] = LibraryInfo()
+    library_info['libB'].required.append('libC')
+    library_info['libC'] = LibraryInfo()
+    library_info['libD'] = LibraryInfo()
+    library_info['libD'].required.append('libC')
+
+
+def tearDown(test):
+    resourcelibrary.library_info = test.old_library_info
+
+
+def doctest_dependency_resolution():
+    """Test Response._addDependencies
+
+        >>> from zc.resourcelibrary.publication import Response
+        >>> r = Response()
+
+    The method gets a list of libraries and adds all their dependencies
+    in the proper order
+
+        >>> r._addDependencies(['libA'])
+        ['libC', 'libB', 'libA']
+
+    Here's a tricky corner case that the old algorithm used to get wrong:
+
+        >>> r._addDependencies(['libA', 'libD'])
+        ['libC', 'libB', 'libA', 'libD']
+
+    No library is included more than once
+
+        >>> r._addDependencies(['libC', 'libA', 'libD', 'libA'])
+        ['libC', 'libB', 'libA', 'libD']
+
+    Unknown library names cause errors
+
+        >>> r._addDependencies(['libA', 'libZ'])
+        Traceback (most recent call last):
+          ...
+        RuntimeError: Unknown resource library: "libZ"
+
+    """
+
+
 def test_suite():
-    
     return unittest.TestSuite(
         (
+        DocTestSuite(setUp=setUp, tearDown=tearDown),
         DocTestSuite('zc.resourcelibrary.publication',
                      optionflags=doctest.NORMALIZE_WHITESPACE|doctest.ELLIPSIS,
                      ),