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.

CommentFileSizeAuthor
#8 menu-tree-data-test-566094.patch4.15 KBsmk-ka
Passed: 12836 passes, 0 fails, 0 exceptions View
#4 menu-tree-data-test-566094-4.patch4.94 KBcburschka
Passed: 12882 passes, 0 fails, 0 exceptions View
#3 menu-tree-data-test-566094-3.patch4.33 KBcburschka
Passed: 12898 passes, 0 fails, 0 exceptions View
menu_tree_data.patch1.85 KBsmk-ka
Unable to apply patch menu_tree_data.patch View
Members fund testing for the Drupal project. Drupal Association Learn more

Comments

cburschka’s picture

ARGH.

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.)

cburschka’s picture

Here'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.

require_once 'includes/menu.inc';

for ($i = 0; $i < 1000; $i++) test();

function test() {
  // Generate a menu tree with random depths.
  $text1 = generate(array('Apple', 'Banana', 'Citron', 'Orange', 'Grape', 'Coconut', 'Strawberry', 'Cherry', 'Grapefruit', 'Something', 'Other', 'Yet more'));
  // Turn it into a flat Drupal menu.
  $menu = read($text1);
  // Use menu_tree_data() to build an actual tree.
  $tree = menu_tree_data($menu);
  // Render the tree back into text.
  $text2 = render($tree);

  // Check that they're equal.
  print $text1 == $text2 ? "PASS\n" : "FAIL\n";
}

// Takes a list of words and prints them as a menu with random depths.
function generate($links) {
  $menu = '';
  // Start at level 0.
  $depth = 0;
  foreach ($links as $link) {
    $menu .= str_pad('', $depth, '-') . $link . "\n";
    // Modify depth (don't increase it by more than one, but make an increase more likely than a decrease)
    $depth += min(1, rand(-5, 10));
    // Don't go out of level 0.
    $depth = max($depth, 0);
  }
  return $menu;
}

// Read the text generated above and turn it into a menu as used by Drupal.
function read($text) {
  $menu = array();
  foreach(explode("\n", $text) as $line) {
    if (preg_match('/^(-*)(.+)$/', $line, $match)) {
      $menu[] = array(
        'mlid' => $match[2],
        'depth' => strlen($match[1]) + 1, // menu.inc likes depths to start at 1.
      );
    }
  }
  return $menu;
}

// Take a recursive tree (with 'below' items) and render it into the same format as generate().
function render($tree, $indent = '') {
  $text = '';
  foreach ($tree as $item) {
    $text .= $indent . $item['link']['mlid'] . "\n";
    $text .= render($item['below'], $indent . '-');
  }
  return $text;
}

cburschka’s picture

FileSize
4.33 KB
Passed: 12898 passes, 0 fails, 0 exceptions View

Here'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.

cburschka’s picture

FileSize
4.94 KB
Passed: 12882 passes, 0 fails, 0 exceptions View

I've made some small code-style and phpdoc fixes.

cburschka’s picture

Priority: Normal » Critical

Escalating. 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.

pwolanin’s picture

Looking 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.

cburschka’s picture

Status: Needs review » Needs work

I 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.)

smk-ka’s picture

Status: Needs work » Needs review
FileSize
4.15 KB
Passed: 12836 passes, 0 fails, 0 exceptions View

Rewrote the test to utilize a dummy link structure instead.

Damien Tournoud’s picture

Is that a D7 specific bug? I'm surprised this one hasn't been noticed before.

cburschka’s picture

It'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.

sun’s picture

Status: Needs review » Reviewed & tested by the community

I tested this patch manually - directly after applying the patch and rebuilding the menu, all previously misplaced links in Administration menu were properly located.

pwolanin’s picture

@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.

sun’s picture

This 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.

webchick’s picture

Status: Reviewed & tested by the community » Fixed

Nice catch, and tests too!

Committed to HEAD. Thanks!

Status: Fixed » Closed (fixed)

Automatically closed -- issue fixed for 2 weeks with no activity.

Status: Closed (fixed) » Needs review

suryaprakash requested that failed test be re-tested.

c960657’s picture

Status: Needs review » Closed (fixed)

Setting status back to closed.