menu_tree_data() doesn't build proper hierarchy

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

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;
}

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.

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

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.

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.

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

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

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.

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

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

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.

Nice catch, and tests too!

Committed to HEAD. Thanks!

Setting status back to closed.