Support for Drupal 7 is ending on 5 January 2025—it’s time to migrate to Drupal 10! Learn about the many benefits of Drupal 10 and find migration tools in our resource center.
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.
Comment | File | Size | Author |
---|---|---|---|
#9 | drupal-graph-cycle-1217648-9.patch | 4.26 KB | clemens.tolboom |
#7 | drupal-graph-cycle-1217648-7.patch | 3.31 KB | clemens.tolboom |
Comments
Comment #1
Damien Tournoud CreditAttribution: Damien Tournoud commentedThis 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:
Our order should guarantee that C is enabled before B, and makes no guarantee between A and B.
Comment #2
clemens.tolboom(déjà vu: where did we talked about this before)
As the call to
drupal_depth_first_search
is used byupdate_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
Comment #3
Damien Tournoud CreditAttribution: Damien Tournoud commentedWell. 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.
Comment #4
David_Rothstein CreditAttribution: David_Rothstein commentedOne 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.
Comment #5
David_Rothstein CreditAttribution: David_Rothstein commentedDowngrading 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...
Comment #6
clemens.tolboomAgreed ... 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.
Comment #7
clemens.tolboomAccording 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.
Comment #8
clemens.tolboomThis should conform to $this->normalizeGraph method.
Better text would contain graph has one or more cycles
Could use a more complex example too
Duplicate line
23 days to next Drupal core point release.
Comment #9
clemens.tolboomI'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?
Comment #10
kscheirer#9: drupal-graph-cycle-1217648-9.patch queued for re-testing.
Comment #12
clemens.tolboomCode is changed last year and a half :/
See also #1915308: Make the graph component input an edge list and add topological sort which is put "on hold" by chx #1915308: Make the graph component input an edge list and add topological sort
(unassigned)
Comment #13
clemens.tolboom(wtf I cannot change the issue summary)
These XREF should be added to the summary
- #896698: Circular dependency references between field and field_sql_storage
- #1247476: ModuleHandler::parseDependency fails on major version ops (>27.x) and (<=28.x)
- #1915308: Make the graph component input an edge list and add topological sort
all indicating we have a brittle package manager.
Comment #13.0
clemens.tolboomMarked the expected graph deleted
Comment #22
drummComment #23
clemens.tolboomI close this as outdated as this was about D7 and never got a patch for D8.