The menu tree returned by menu_tree_data() puts elements on the wrong level because it looks at the wrong item when determining the termination condition. After filling the current item's below
array using a recursive call to _menu_tree_data(), the $next element still points at the item before entering the recursion. However, we need to look at the next item after the recursion returned to determine whether the current loop needs to be terminated, thus a refresh of $next is needed.
Example using an excerpt of the menu structure:
+ admin/structure/blocks (depth=2)
+ + admin/structure/blocks/list (depth=3)
+ + - admin/structure/blocks/list/garland etc. (depth=4)
+ + - admin/structure/blocks/list/stark (still depth=4)
+ admin/structure/types (depth=2, need to terminate two recursions but fails!)
Consider we're at admin/structure/blocks/list and about to enter recursion for the sub-tree garland, etc. until stark. When the recursion returns, $next still points at admin/structure/blocks/list/garland, ie. the item before we entered the recursion. However, we need to look at the item after the sub-tree (admin/structure/types), to determine whether the loop needs to be terminated.
You can most easily validate the results by installing Admin Menu HEAD, which is finally working for D7 after applying this patch.
Comment | File | Size | Author |
---|---|---|---|
#8 | menu-tree-data-test-566094.patch | 4.15 KB | smk-ka |
#4 | menu-tree-data-test-566094-4.patch | 4.94 KB | cburschka |
#3 | menu-tree-data-test-566094-3.patch | 4.33 KB | cburschka |
menu_tree_data.patch | 1.85 KB | smk-ka | |
Comments
Comment #1
cburschkaARGH.
I've been investigating this one for ages on DHTML Menu, and it's a core bug? The menu system's recursion has often given me migraine. :P
Patch looks good to me. The next reviewer could set this to RTBC.
(Unless we want a test for _menu_tree_data(). We could just pass it a normal flat hierarchy and see what comes out.)
Comment #2
cburschkaHere's a test script which could probably be turned into a unit test with some changes. It tests a large number of possible trees that are randomly generated. The specific bug that the patch fixes is that any item more than one level above its predecessor will have a misplaced depth.
Pre-patch, I get about 2/3 fails, 1/3 passes. After the patch, all pass.
Comment #3
cburschkaHere's a test that fails before the patch, and passes after it. I've tried to make the test as broad as possible to make sure it can catch other regressions.
Comment #4
cburschkaI've made some small code-style and phpdoc fixes.
Comment #5
cburschkaEscalating. This can mess up menu structures in a nasty way, and the menus don't even need to be set to "always expanded" for it.
Comment #6
pwolanin CreditAttribution: pwolanin commentedLooking at code I see the potential erorr and the fix looks correct, though I hjaven't tested it yet - the addition of tests gets a big +1 also.
However, I'm not sure it makes sense for testing to use a tree with a random structure - the tests should be deterministic so that it would always fail int he case of this bug.
Comment #7
cburschkaI guess so, yeah. In this test case I've just used a 200-item array to let the error occur with some scientific notation likelihood - but it'd be just as easy to use something shorter and pre-chosen.
(Of course, we would *only* catch this current bug through that, and other more complex regressions might slip through later. But that could happen to the current approach as well.)
Comment #8
smk-ka CreditAttribution: smk-ka commentedRewrote the test to utilize a dummy link structure instead.
Comment #9
Damien Tournoud CreditAttribution: Damien Tournoud commentedIs that a D7 specific bug? I'm surprised this one hasn't been noticed before.
Comment #10
cburschkaIt's new. The function has been rewritten in D7 (being passed a reversed array instead of a database result resource), and with the complex recursion an error can sneak in easily.
As for being discovered: In the default profile, the admin menu is never displayed as open due to D7UX nixing sidebar navigation on the admin pages. That means if you install a pristine default, you never get to see any large menu structure at all. Not coincidentally, the only two situations in which this bug has so far been noticed are menu-related contribs.
Comment #11
sunI tested this patch manually - directly after applying the patch and rebuilding the menu, all previously misplaced links in Administration menu were properly located.
Comment #12
pwolanin CreditAttribution: pwolanin commented@Arancaytar - we could certainly randomly generate a 100+ item array and then hard-code it into the test and also use the code you wrote before. Anyhow this looks good, but we shoudl keep adding tests.
Comment #13
sunThis patch blocks a port of menu-related contrib modules to D7. I kindly request to push the button. :)
I also want to expand on the tests added here in #550254: Menu links are sometimes not properly re-parented.
Comment #14
webchickNice catch, and tests too!
Committed to HEAD. Thanks!
Comment #17
c960657 CreditAttribution: c960657 commentedSetting status back to closed.