This is a root cause I guess from at least

- #211182: Updates run in unpredictable order
- #717834: The dependencies declared in core's hook_update_dependencies() implementations aren't actually correct
- #1072450: Upgrade from 6.20 to 7.2 - Update #7003 still fails

Changing the test for graph.inc by adding a test by reusing the graph from test testDepthFirstSearch

  function testCircularDepthFirstSearch() {
    // The sample graph used is:
    // 1 --> 2 <-- 3     5 ---> 6
    //       |     ^     ^
    //       |     |     |
    //       |     |     |
    //       +---> 4 <-- 7      8 ---> 9
    $graph = $this->normalizeGraph(array(
      1 => array(2),
      2 => array(4), // <== removed 3
      3 => array(2), // <== add 2 introduced circular
      4 => array(3),
      5 => array(6),
      7 => array(4, 5),
      8 => array(9),
      9 => array(),
    ));
    drupal_depth_first_search($graph);

    $expected_paths = array();
/*
      1 => array(2, 3, 4),
      2 => array(3, 4),
      3 => array(),
      4 => array(3),
      5 => array(6),
      7 => array(4, 3, 5, 6),
      8 => array(9),
      9 => array(),
    );
*/
    $this->assertPaths($graph, $expected_paths);
  }

The $expected_path should be empty as by definition a DepthFirstSearch graph should be a http://en.wikipedia.org/wiki/Directed_acyclic_graph

Our _update_dependencies graph is not as noted in those issues.

drupal-7-hook-update-n.png

Support from Acquia helps fund testing for Drupal Acquia logo

Comments

Damien Tournoud’s picture

This is by design. The result of drupal_depth_first_search() is not a topological order when the graph contains cycles, but it should be close enough for our purpose.

For the following graph, for example:

A <-> B <- C

Our order should guarantee that C is enabled before B, and makes no guarantee between A and B.

clemens.tolboom’s picture

(déjà vu: where did we talked about this before)

As the call to drupal_depth_first_search is used by update_resolve_dependencies in update.inc and we have a lot of issues regarding upgrading I guess we need to address this right?

The mentioned issues maybe related to this issue but I'm not sure how to get a grip on that :-(

Is taxonomy_update_7002 intended to run before or after user_update_7006 ?

Furthermore I still consider this a bug ... as it simply ignores a loop in the graph. Or am I missing some vital point?

Edit: déjà vu: #896698: Circular dependency references between field and field_sql_storage

Damien Tournoud’s picture

Well. At least I am consistent in my answers :)

This loop is ignored, yes, but for good reasons: there is no way to get an order that satisfies all the dependencies. I feel that we should just remove the loop and close this issue, except if you have reason to believes that our DFS doesn't return something "close enough" in that case.

David_Rothstein’s picture

One thing that might be useful is to have an API function that detects circular graphs. It should be pretty easy to do, I think (just check for a vertex that appears in its own 'paths' or 'reverse_paths'?).

That way calling code that cares about preventing circular dependencies could easily check that and e.g. throw an exception if it finds one.

David_Rothstein’s picture

Version: 7.x-dev » 8.x-dev
Priority: Major » Normal

Downgrading for now, and moving to the proper version. As Damien said, this may not actually be a bug, but leaving it there at the moment...

clemens.tolboom’s picture

Agreed ... we are now fixing the graph and #4 is a good idea to have lying around. We can then writing tests for circular graphs within core.

clemens.tolboom’s picture

Assigned: Unassigned » clemens.tolboom
Status: Active » Needs review
FileSize
3.31 KB

According to http://en.wikipedia.org/wiki/Topological_sorting#Algorithms a TSL cannot be when applying Kahn's algorithm having node leftovers.

Are there other/better algorithms?

The attached patch utilizes another TSL algorithm which indicates the graph.inc could be refactored.

clemens.tolboom’s picture

Status: Needs review » Needs work
+++ b/modules/simpletest/tests/graph.test
@@ -85,6 +85,29 @@ class GraphUnitTest extends DrupalUnitTestCase {
+    $graph = array();
+    $graph['a']['edges']['b'] = 1;
+    $graph['b']['edges']['c'] = 1;
+    $graph['c']['edges']['a'] = 1;

This should conform to $this->normalizeGraph method.

+++ b/includes/graph.inc
@@ -144,3 +144,80 @@ function _drupal_depth_first_search(&$graph, &$state, $start, &$component = NULL
+ * @return boolean Indicating the graph is cyclic

Better text would contain graph has one or more cycles

+++ b/modules/simpletest/tests/graph.test
@@ -85,6 +85,29 @@ class GraphUnitTest extends DrupalUnitTestCase {
+  function testCycles() {

Could use a more complex example too

+++ b/modules/simpletest/tests/graph.test
@@ -85,6 +85,29 @@ class GraphUnitTest extends DrupalUnitTestCase {
+    $is_cyclic = drupal_graph_is_cyclic($graph);

Duplicate line

23 days to next Drupal core point release.

clemens.tolboom’s picture

Status: Needs work » Needs review
FileSize
4.26 KB

I've renamed some elements and added an update test too.

Strange this about simple test is how could we ever test for ie #717834: The dependencies declared in core's hook_update_dependencies() implementations aren't actually correct that is having all _hook_update_dependencies() available.

The test I added function testUpdateDependenciesCore() only test the update_test_x modules :(
How can we make that testing whole core?

kscheirer’s picture

#9: drupal-graph-cycle-1217648-9.patch queued for re-testing.

Status: Needs review » Needs work

The last submitted patch, drupal-graph-cycle-1217648-9.patch, failed testing.

clemens.tolboom’s picture

Assigned: clemens.tolboom » Unassigned
clemens.tolboom’s picture

clemens.tolboom’s picture

Issue summary: View changes

Marked the expected graph deleted

Version: 8.0.x-dev » 8.1.x-dev

Drupal 8.0.6 was released on April 6 and is the final bugfix release for the Drupal 8.0.x series. Drupal 8.0.x will not receive any further development aside from security fixes. Drupal 8.1.0-rc1 is now available and sites should prepare to update to 8.1.0.

Bug reports should be targeted against the 8.1.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.2.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

Version: 8.1.x-dev » 8.2.x-dev

Drupal 8.1.9 was released on September 7 and is the final bugfix release for the Drupal 8.1.x series. Drupal 8.1.x will not receive any further development aside from security fixes. Drupal 8.2.0-rc1 is now available and sites should prepare to upgrade to 8.2.0.

Bug reports should be targeted against the 8.2.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.3.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

Version: 8.2.x-dev » 8.3.x-dev

Drupal 8.2.6 was released on February 1, 2017 and is the final full bugfix release for the Drupal 8.2.x series. Drupal 8.2.x will not receive any further development aside from critical and security fixes. Sites should prepare to update to 8.3.0 on April 5, 2017. (Drupal 8.3.0-alpha1 is available for testing.)

Bug reports should be targeted against the 8.3.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.4.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

Version: 8.3.x-dev » 8.4.x-dev

Drupal 8.3.6 was released on August 2, 2017 and is the final full bugfix release for the Drupal 8.3.x series. Drupal 8.3.x will not receive any further development aside from critical and security fixes. Sites should prepare to update to 8.4.0 on October 4, 2017. (Drupal 8.4.0-alpha1 is available for testing.)

Bug reports should be targeted against the 8.4.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.5.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

Version: 8.4.x-dev » 8.5.x-dev

Drupal 8.4.4 was released on January 3, 2018 and is the final full bugfix release for the Drupal 8.4.x series. Drupal 8.4.x will not receive any further development aside from critical and security fixes. Sites should prepare to update to 8.5.0 on March 7, 2018. (Drupal 8.5.0-alpha1 is available for testing.)

Bug reports should be targeted against the 8.5.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.6.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

Version: 8.5.x-dev » 8.6.x-dev

Drupal 8.5.6 was released on August 1, 2018 and is the final bugfix release for the Drupal 8.5.x series. Drupal 8.5.x will not receive any further development aside from security fixes. Sites should prepare to update to 8.6.0 on September 5, 2018. (Drupal 8.6.0-rc1 is available for testing.)

Bug reports should be targeted against the 8.6.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.7.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

Version: 8.6.x-dev » 8.8.x-dev

Drupal 8.6.x will not receive any further development aside from security fixes. Bug reports should be targeted against the 8.8.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.9.x-dev branch. For more information see the Drupal 8 and 9 minor version schedule and the Allowed changes during the Drupal 8 and 9 release cycles.

Version: 8.8.x-dev » 8.9.x-dev

Drupal 8.8.7 was released on June 3, 2020 and is the final full bugfix release for the Drupal 8.8.x series. Drupal 8.8.x will not receive any further development aside from security fixes. Sites should prepare to update to Drupal 8.9.0 or Drupal 9.0.0 for ongoing support.

Bug reports should be targeted against the 8.9.x-dev branch from now on, and new development or disruptive changes should be targeted against the 9.1.x-dev branch. For more information see the Drupal 8 and 9 minor version schedule and the Allowed changes during the Drupal 8 and 9 release cycles.

drumm’s picture

Issue summary: View changes
clemens.tolboom’s picture

Status: Needs work » Closed (outdated)

I close this as outdated as this was about D7 and never got a patch for D8.