<?php
/**
 * @file
 * Provides configurable blocks of menu items.
 */

/**
 * Denotes that the tree should use the menu picked by the current page.
 */
define('MENU_TREE__CURRENT_PAGE_MENU', '_active');

// Off-load the following infrequently called hooks to another file.
function menu_block_block_info() {
  module_load_include('inc', 'menu_block', 'menu_block.admin');
  return _menu_block_block_info();
}
function menu_block_block_configure($delta = '') {
  module_load_include('inc', 'menu_block', 'menu_block.admin');
  return _menu_block_block_configure($delta);
}
function menu_block_block_save($delta = '', $edit = array()) {
  module_load_include('inc', 'menu_block', 'menu_block.admin');
  return _menu_block_block_save($delta, $edit);
}
function menu_block_form_block_admin_display_form_alter(&$form, $form_state) {
  module_load_include('inc', 'menu_block', 'menu_block.admin');
  return _menu_block_form_block_admin_display_form_alter($form, $form_state);
}

/**
 * Implements hook_menu().
 */
function menu_block_menu() {
  // @todo Remove this check if block module is re-added as a dependency.
  if (module_exists('block')) {
    $items['admin/structure/block/add-menu-block'] = array(
      'title' => 'Add menu block',
      'description' => 'Add a new menu block.',
      'page callback' => 'drupal_get_form',
      'page arguments' => array('menu_block_add_block_form'),
      'access callback' => 'menu_block_access',
      'type' => MENU_LOCAL_ACTION,
      'file' => 'menu_block.admin.inc',
    );
    $default_theme = variable_get('theme_default', 'bartik');
    foreach (list_themes() as $key => $theme) {
      if ($key != $default_theme) {
        $items['admin/structure/block/list/' . $key . '/add-menu-block'] = array(
          'title' => 'Add menu block',
          'description' => 'Add a new menu block.',
          'page callback' => 'drupal_get_form',
          'page arguments' => array('menu_block_add_block_form'),
          'access callback' => 'menu_block_access',
          'type' => MENU_LOCAL_ACTION,
          'file' => 'menu_block.admin.inc',
        );
      }
    }
    $items['admin/structure/block/delete-menu-block'] = array(
      'title' => 'Delete menu block',
      'page callback' => 'drupal_get_form',
      'page arguments' => array('menu_block_delete_form'),
      'access callback' => 'menu_block_access',
      'type' => MENU_CALLBACK,
      'file' => 'menu_block.admin.inc',
    );
  }

  $items['admin/config/user-interface/menu-block'] = array(
    'title' => 'Menu block',
    'description' => 'Configure menu block.',
    'page callback' => 'drupal_get_form',
    'page arguments' => array('menu_block_admin_settings_form'),
    'access callback' => 'menu_block_access',
    'type' => MENU_NORMAL_ITEM,
    'file' => 'menu_block.admin.inc',
  );
  return $items;
}

/**
 * Determine whether the user has permission to use menu_block module.
 */
function menu_block_access($account = NULL) {
  return user_access('administer blocks', $account) && user_access('administer menu', $account);
}

/**
 * Implements hook_menu_alter().
 */
function menu_block_menu_alter(&$items) {
  // Fake the necessary menu attributes necessary for a contextual link.
  $items['admin/content/book/%node']['title'] = 'Edit book outline';
  $items['admin/content/book/%node']['type'] = MENU_LOCAL_TASK;
  $items['admin/content/book/%node']['context'] = (MENU_CONTEXT_PAGE | MENU_CONTEXT_INLINE);
  $items['admin/content/book/%node']['tab_root'] = 'admin/content/book';
}

/**
 * Implements hook_ctools_plugin_directory().
 */
function menu_block_ctools_plugin_directory($module, $plugin) {
  if ($plugin == 'content_types') {
    return 'plugins/' . $plugin;
  }
}

/**
 * Implements hook_ctools_block_info().
 *
 * @see ctools_block_content_type_content_types().
 */
function menu_block_ctools_block_info($module, $delta, &$info) {
  $info['icon'] = 'icon_contrib_menu.png';
  $info['category'] = t('Menus');
}

/**
 * Implements hook_theme().
 */
function menu_block_theme(&$existing, $type, $theme, $path) {
  // Add theme hook suggestion patterns for the core theme functions used in
  // this module. We can't add them during hook_theme_registry_alter() because
  // we will already have missed the opportunity for the theme engine's
  // theme_hook() to process the pattern. And we can't run the pattern ourselves
  // because we aren't given the type, theme and path in that hook.
  $existing['menu_tree']['pattern'] = 'menu_tree__';
  $existing['menu_link']['pattern'] = 'menu_link__';

  return array(
    'menu_block_wrapper' => array(
      'template' => 'menu-block-wrapper',
      'variables' => array('content' => array(), 'config' => array(), 'delta' => NULL),
      'pattern' => 'menu_block_wrapper__',
    ),
    'menu_block_menu_order' => array(
      'render element' => 'element',
      'file' => 'menu_block.admin.inc',
    ),
  );
}

/**
 * Implements hook_help().
 */
function menu_block_help($path, $arg) {
  switch ($path) {
    case 'admin/structure/block/manage/%/%':
      if ($arg[4] != 'menu_block') {
        break;
      }
    case 'admin/help#menu_block':
    case 'admin/structure/block/add-menu-block':
      module_load_include('inc', 'menu_block', 'menu_block.pages');
      return _menu_block_help($path, $arg);
  }
}

/**
 * Implements hook_block_view().
 */
function menu_block_block_view($delta = '') {
  $config = menu_block_get_config($delta);
  return menu_tree_build($config);
}

/**
 * Implements hook_block_view_alter().
 */
function menu_block_block_view_alter(&$data, $block) {
  // Add contextual links for menu blocks.
  if ($block->module == 'menu_block' && !empty($data['content']['#config'])) {
    $menu_name = $data['content']['#config']['menu_name'];
    if (in_array($menu_name, array_keys(menu_get_menus()))) {
      $data['content']['#contextual_links']['menu_block'] = array('admin/structure/menu/manage', array($menu_name));
    }
    elseif (strpos($menu_name, 'book-toc-') === 0) {
      $node = str_replace('book-toc-', '', $menu_name);
      $data['content']['#contextual_links']['menu_block'] = array('admin/content/book', array($node));
    }
  }
}

/**
 * Process variables for menu-block-wrapper.tpl.php.
 *
 * @see menu-block-wrapper.tpl.php
 */
function template_preprocess_menu_block_wrapper(&$variables) {
  $variables['classes_array'][] = 'menu-block-' . $variables['delta'];
  $variables['classes_array'][] = 'menu-name-' . $variables['config']['menu_name'];
  $variables['classes_array'][] = 'parent-mlid-' . menu_block_clean_css_identifier($variables['config']['parent_mlid']);
  $variables['classes_array'][] = 'menu-level-' . $variables['config']['level'];
}

/**
 * A copy of drupal_clean_css_identifier() that cleans up colon characters.
 */
function menu_block_clean_css_identifier($identifier, $filter = array(' ' => '-', '_' => '-', '/' => '-', '[' => '-', ']' => '', ':' => '-')) {
  return drupal_clean_css_identifier($identifier, $filter);
}

/**
 * Returns a list of menu names implemented by all modules.
 *
 * @return array
 *   An array of menu titles keyed by menu machine name.
 */
function menu_block_get_all_menus() {
  $all_menus = &drupal_static(__FUNCTION__);

  if (!$all_menus) {
    $cid = 'menu_block_menus:' . $GLOBALS['language']->language;
    if ($cached = cache_get($cid, 'cache_menu')) {
      $all_menus = $cached->data;
    }
    else {
      // Retrieve core's menus.
      $all_menus = menu_get_menus();
      // Retrieve all the menu names provided by hook_menu_block_get_menus().
      $all_menus = array_merge($all_menus, module_invoke_all('menu_block_get_menus'));
      asort($all_menus);
      // Add an option to use the menu for the active menu item.
      $all_menus = array(MENU_TREE__CURRENT_PAGE_MENU => '<' . t('the menu selected by the page') . '>') + $all_menus;
      cache_set($cid, $all_menus, 'cache_menu');
    }
  }

  return $all_menus;
}

/**
 * The default menu block configuration.
 *
 * @return array
 */
function menu_block_default_config() {
  return array(
    'parent' => 'main-menu:0',
    'title_link' => 0,
    'admin_title' => '',
    'level' => 1,
    'follow' => 0,
    'display_empty' => 0,
    'depth' => 0,
    'depth_relative' => 0,
    'expanded' => 0,
    'sort' => 0,
  );
}

/**
 * Fetch all exported menu blocks.
 *
 * @return array
 */
function menu_block_get_exported_blocks() {
  $blocks = &drupal_static(__FUNCTION__);
  if (!isset($blocks)) {
    $blocks = array();
    // Do not use module_invoke_all() since it rewrites numeric indexes.
    // Although exported menu blocks should not be using numeric IDs, we
    // should still prevent them from being changed.
    foreach (module_implements('menu_block_blocks') as $module) {
      $blocks += module_invoke($module, 'menu_block_blocks');
    }
  }
  return $blocks;
}

/**
 * Returns the configuration for the requested block delta.
 *
 * @param string $delta
 *   The delta that uniquely identifies the block in the block system. If
 *   not specified, the default configuration will be returned.
 *   This is deprecated. Use menu_block_default_config() instead.
 *
 * @return array
 *   An associated array of configuration options.
 *
 * @see menu_block_default_config()
 */
function menu_block_get_config($delta = NULL) {
  static $defaults, $exported;

  if (!isset($defaults)) {
    $defaults = menu_block_default_config();
  }

  if (!isset($delta)) {
    return $defaults;
  }

  if (!isset($exported)) {
    $exported = menu_block_get_exported_blocks();
  }

  $configs = &drupal_static(__FUNCTION__, array());
  if (!isset($configs[$delta])) {
    $config = array();

    // Check if this an exported menu block.
    if (isset($exported[$delta])) {
      $config += $exported[$delta];
      $config['exported_to_code'] = TRUE;
      // Exported blocks generally have 'menu_name' and 'parent_mlid' defined
      // but not 'parent'
      if (!isset($config['parent'])) {
        $config['parent'] = $config['menu_name'] . ':' . $config['parent_mlid'];
      }
    }

    // Add in variable overrides and defaults.
    foreach ($defaults as $key => $default) {
      $override = variable_get("menu_block_{$delta}_{$key}");
      if (isset($override)) {
        $config[$key] = $override;
      }
      elseif (!isset($config[$key])) {
        $config[$key] = $default;
      }
    }

    // Split out the 'parent' item into 'menu_name' and 'parent_mlid'.
    if (!isset($config['menu_name']) && !isset($config['parent_mlid'])) {
      list($config['menu_name'], $config['parent_mlid']) = explode(':', $config['parent']);
    }

    $config['delta'] = $delta;
    $configs[$delta] = $config;
  }

  return $configs[$delta];
}

/**
 * Gets the data structure representing a menu tree for the given configuration.
 *
 * @param array $config
 *   See the $config param of menu_tree_build().
 *
 * @return array
 */
function menu_tree_block_data(array &$config) {
  // Determine the max depth based on level and depth setting.
  $max_depth = ($config['depth'] == 0) ? NULL : min($config['level'] + $config['depth'] - 1, MENU_MAX_DEPTH);

  if ($config['expanded'] || $config['parent_mlid']) {
    // Get the full, un-pruned tree.
    if ($config['parent_mlid'] || !empty($config['depth_relative'])) {
      $tree = menu_tree_all_data($config['menu_name']);
    }
    else {
      $tree = menu_tree_all_data($config['menu_name'], NULL, $max_depth);
    }
    // And add the active trail data back to the full tree.
    menu_tree_add_active_path($tree);
  }
  else {
    if (!empty($config['depth_relative'])) {
      // Get the tree pruned for just the active trail.
      $tree = menu_tree_page_data($config['menu_name']);
    }
    else {
      $tree = menu_tree_page_data($config['menu_name'], $max_depth);
    }
  }

  // Allow alteration of the tree and config before we begin operations on it.
  drupal_alter('menu_block_tree', $tree, $config);

  // Localize the tree.
  if (module_exists('i18n_menu')) {
    $tree = i18n_menu_localize_tree($tree);
  }

  // Prune the tree along the active trail to the specified level.
  if ($config['level'] > 1 || $config['parent_mlid']) {
    if ($config['parent_mlid']) {
      $parent_item = menu_link_load($config['parent_mlid']);
      if (!$parent_item) {
        watchdog('menu_block', "Menu block @delta is set to use parent menu link @plid but the menu link was not loadable or does not exist.", array(
          '@delta' => $config['delta'],
          '@plid' => $config['parent_mlid'],
        ), WATCHDOG_ERROR);
        $parent_item = NULL;
      }
      menu_tree_prune_tree($tree, $config['level'], $parent_item);
    }
    else {
      menu_tree_prune_tree($tree, $config['level']);
    }
  }

  // Prune the tree to the active menu item.
  if ($config['follow']) {
    menu_tree_prune_active_tree($tree, $config['follow']);
  }

  // If the menu-item-based tree is not "expanded", trim the tree to the active path.
  if ($config['parent_mlid'] && !$config['expanded']) {
    menu_tree_trim_active_path($tree);
  }

  // Trim the branches that extend beyond the specified depth.
  if ($config['depth'] > 0) {
    menu_tree_depth_trim($tree, $config['depth']);
  }

  // Sort the active path to the top of the tree.
  if ($config['sort']) {
    menu_tree_sort_active_path($tree);
  }

  return $tree;
}

/**
 * Returns the current page's menu.
 *
 * @return string|bool
 *   The current page's menu, or FALSE if no menu applied.
 */
function menu_block_get_current_page_menu() {
  // Retrieve the list of available menus.
  $menu_order = variable_get('menu_block_menu_order', array('main-menu' => '', 'user-menu' => ''));

  // Check for regular expressions as menu keys.
  $patterns = array();
  foreach (array_keys($menu_order) as $pattern) {
    if ($pattern[0] == '/') {
      $patterns[$pattern] = NULL;
    }
  }

  // Extract the "current" path from the request, or from the active menu
  // trail if applicable.
  $link_path = $_GET['q'] ? $_GET['q'] : '<front>';
  $trail = menu_get_active_trail();
  $last_item = end($trail);
  if (!empty($last_item['link_path'])) {
    $link_path = $last_item['link_path'];
  }

  // Retrieve all the menus containing a link to the current page.
  $result = db_query("SELECT menu_name FROM {menu_links} WHERE link_path = :link_path", array(':link_path' => $link_path));
  foreach ($result as $item) {
    // Check if the menu is in the list of available menus.
    if (isset($menu_order[$item->menu_name])) {
      // Mark the menu.
      $menu_order[$item->menu_name] = MENU_TREE__CURRENT_PAGE_MENU;
    }
    else {
      // Check if the menu matches one of the available patterns.
      foreach (array_keys($patterns) as $pattern) {
        if (preg_match($pattern, $item->menu_name)) {
          // Mark the menu.
          $menu_order[$pattern] = MENU_TREE__CURRENT_PAGE_MENU;
          // Store the actual menu name.
          $patterns[$pattern] = $item->menu_name;
        }
      }
    }
  }
  // Find the first marked menu.
  $menu_name = array_search(MENU_TREE__CURRENT_PAGE_MENU, $menu_order);
  // If a pattern was matched, use the actual menu name instead of the pattern.
  if (!empty($patterns[$menu_name])) {
    $menu_name = $patterns[$menu_name];
  }

  return $menu_name;
}

/**
 * Build a menu tree based on the provided configuration.
 *
 * @param array $config
 *   An array of configuration options that specifies how to build the
 *   menu tree and its title.
 *   - delta: (string) The menu_block's block delta.
 *   - menu_name: (string) The machine name of the requested menu. Can also be
 *     set to MENU_TREE__CURRENT_PAGE_MENU to use the menu selected by the page.
 *   - parent_mlid: (int) The mlid of the item that should root the tree. Use 0
 *     to use the menu's root.
 *   - title_link: (boolean) Specifies if the title should be rendered as a link
 *     or a simple string.
 *   - admin_title: (string) An optional title to uniquely identify the block on
 *     the administer blocks page.
 *   - level: (int) The starting level of the tree.
 *   - follow: (string) Specifies if the starting level should follow the
 *     active menu item. Should be set to 0, 'active' or 'child'.
 *   - depth: (int) The maximum depth the tree should contain, relative to the
 *     starting level.
 *   - expanded: (boolean) Specifies if the entire tree be expanded or not.
 *   - sort: (boolean) Specifies if the tree should be sorted with the active
 *     trail at the top of the tree.
 *
 * @return array
 *   An associative array containing several pieces of data.
 *   - content: The tree as a renderable array.
 *   - subject: The title rendered as HTML.
 *   - subject_array: The title as a renderable array.
 */
function menu_tree_build(array &$config) {
  // Retrieve the active menu item from the database.
  if ($config['menu_name'] == MENU_TREE__CURRENT_PAGE_MENU) {
    $config['menu_name'] = menu_block_get_current_page_menu();
    $config['parent_mlid'] = 0;

    // If no menu link was found, don't display the block.
    if (empty($config['menu_name'])) {
      return array(
        'subject' => t('The menu selected by the page'),
        'subject_array' => array(),
        'content' => array(),
      );
    }
  }

  // Get the default block name.
  drupal_static_reset('menu_block_set_title');
  $menu_names = menu_block_get_all_menus();
  menu_block_set_title($menu_names[$config['menu_name']]);

  // Get the raw menu tree data.
  $tree = menu_tree_block_data($config);
  $title = menu_block_get_title($config['title_link']);

  // Create a renderable tree.
  $data = array();
  $data['subject_array'] = $title;
  $data['subject'] = drupal_render($title);
  $data['content'] = array();
  if (!empty($tree) || !empty($config['display_empty'])) {
    if ($output = menu_block_tree_output($tree, $config)) {
      $data['content']['#content'] = $output;
      $data['content']['#theme'] = array(
        'menu_block_wrapper__' . str_replace('-', '_', $config['delta']),
        'menu_block_wrapper__' . str_replace('-', '_', $config['menu_name']),
        'menu_block_wrapper'
      );
    }
    else {
      $data['content']['#content'] = NULL;
    }
    $data['content']['#config'] = $config;
    $data['content']['#delta'] = $config['delta'];
  }

  return $data;
}

/**
 * Retrieves the menu item to use for the tree's title.
 *
 * @param bool $render_title_as_link
 *   boolean A boolean that says whether to render the title as a link or a
 *   simple string.
 *
 * @return array|string
 *   A render array or string containing the tree's title.
 */
function menu_block_get_title($render_title_as_link = TRUE) {
  $menu_item = menu_block_set_title();

  if (is_string($menu_item)) {
    // The tree's title is a menu title, a normal string.
    $title = array('#markup' => check_plain($menu_item));
  }
  elseif ($render_title_as_link) {
    // The tree's title is a menu item with a link.
    if (!empty($menu_item['in_active_trail'])) {
      $menu_item['localized_options']['attributes']['class'][] = 'active-trail';
    }
    $title = array(
      '#type' => 'link',
      '#title' => $menu_item['title'],
      '#href' => $menu_item['href'],
      '#options' => $menu_item['localized_options'],
    );
  }
  // The tree's title is a menu item.
  else {
    $title = array('#markup' => check_plain($menu_item['title']));
  }
  return $title;
}

/**
 * Sets the menu item to use for the tree's title.
 *
 * @param array|string $item
 *   The menu item (an array) or the menu item's title as a string.
 *
 * @return array|string
 *   The saved title value.
 */
function menu_block_set_title($item = NULL) {
  $menu_item = &drupal_static(__FUNCTION__, '');

  // Save the menu item.
  if (!is_null($item)) {
    $menu_item = $item;
  }

  return $menu_item;
}

/**
 * Add the active trail indicators into the tree.
 *
 * The data returned by menu_tree_page_data() has link['in_active_trail'] set to
 * TRUE for each menu item in the active trail. The data returned from
 * menu_tree_all_data() does not contain the active trail indicators. This is a
 * helper function that adds it back in.
 *
 * @param array $tree
 *   The menu tree.
 */
function menu_tree_add_active_path(array &$tree) {
  // Grab any menu item to find the menu_name for this tree.
  $menu_item = current($tree);
  $tree_with_trail = menu_tree_page_data($menu_item['link']['menu_name']);

  // To traverse the original tree down the active trail, we use a pointer.
  $subtree_pointer =& $tree;

  // Find each key in the active trail.
  while ($tree_with_trail) {
    foreach ($tree_with_trail as $key => &$value) {
      if ($tree_with_trail[$key]['link']['in_active_trail'] && isset($subtree_pointer[$key])) {
        // Set the active trail info in the original tree.
        $subtree_pointer[$key]['link']['in_active_trail'] = TRUE;
        // Continue in the subtree, if it exists.
        $tree_with_trail =& $tree_with_trail[$key]['below'];
        $subtree_pointer =& $subtree_pointer[$key]['below'];
        break;
      }
      else {
        unset($tree_with_trail[$key]);
      }
    }
  }
}

/**
 * Trim everything but the active trail in the tree.
 *
 * @param array $tree
 *   The menu tree to trim.
 */
function menu_tree_trim_active_path(array &$tree) {
  foreach ($tree as $key => &$value) {
    if (($tree[$key]['link']['in_active_trail'] || $tree[$key]['link']['expanded']) && $tree[$key]['below']) {
      // Continue in the subtree, if it exists.
      menu_tree_trim_active_path($tree[$key]['below']);
    }
    else {
      // Trim anything not expanded or along the active trail.
      $tree[$key]['below'] = FALSE;
    }
  }
}

/**
 * Sort the active trail to the top of the tree.
 *
 * @param array $tree
 *   array The menu tree to sort.
 */
function menu_tree_sort_active_path(array &$tree) {
  module_load_include('inc', 'menu_block', 'menu_block.sort');
  _menu_tree_sort_active_path($tree);
}

/**
 * Prune a tree so that it begins at the specified level.
 *
 * This function will follow the active menu trail to the specified level.
 *
 * @param array $tree
 *   The menu tree to prune.
 * @param int $level
 *   The level of the original tree that will start the pruned tree.
 * @param array $parent_item
 *   The menu item that should be used as the root of the tree.
 */
function menu_tree_prune_tree(array &$tree, $level, array $parent_item = NULL) {
  if (!empty($parent_item)) {
    // Prune the tree along the path to the menu item.
    for ($i = 1; $i <= MENU_MAX_DEPTH && $parent_item["p$i"] != '0'; $i++) {
      $plid = $parent_item["p$i"];
      $found_active_trail = FALSE;
      // Examine each element at this level for the ancestor.
      foreach ($tree as $key => &$value) {
        if ($tree[$key]['link']['mlid'] == $plid) {
          menu_block_set_title($tree[$key]['link']);
          // Prune the tree to the children of this ancestor.
          $tree = $tree[$key]['below'] ? $tree[$key]['below'] : array();
          $found_active_trail = TRUE;
          break;
        }
      }
      // If we don't find the ancestor, bail out.
      if (!$found_active_trail) {
        $tree = array();
        break;
      }
    }
  }

  $is_front_page = drupal_is_front_page();
  // Trim the upper levels down to the one desired.
  for ($i = 1; $i < $level; $i++) {
    $found_active_trail = FALSE;
    // Examine each element at this level for the active trail.
    foreach ($tree as $key => &$value) {
      // Also include the children of the front page.
      if ($tree[$key]['link']['in_active_trail'] || ($tree[$key]['link']['link_path'] == '<front>' && $is_front_page)) {
        // Get the title for the pruned tree.
        menu_block_set_title($tree[$key]['link']);
        // Prune the tree to the children of the item in the active trail.
        $tree = $tree[$key]['below'] ? $tree[$key]['below'] : array();
        $found_active_trail = TRUE;
        break;
      }
    }
    // If we don't find the active trail, the active item isn't in the tree we want.
    if (!$found_active_trail) {
      $tree = array();
      break;
    }
  }
}

/**
 * Prune a tree so that it begins at the active menu item.
 *
 * @param array $tree
 *   The menu tree to prune.
 * @param string $level
 *   The level which the tree will be pruned to: 'active' or 'child'.
 */
function menu_tree_prune_active_tree(array &$tree, $level) {
  module_load_include('inc', 'menu_block', 'menu_block.follow');
  _menu_tree_prune_active_tree($tree, $level);
}

/**
 * Prune a tree so it does not extend beyond the specified depth limit.
 *
 * @param array $tree
 *   The menu tree to prune.
 * @param int $depth_limit
 *   The maximum depth of the returned tree; must be a positive integer.
 */
function menu_tree_depth_trim(array &$tree, $depth_limit) {
  // Prevent invalid input from returning a trimmed tree.
  if ($depth_limit < 1) {
    return;
  }

  // Examine each element at this level to find any possible children.
  foreach ($tree as $key => &$value) {
    if ($tree[$key]['below']) {
      if ($depth_limit > 1) {
        menu_tree_depth_trim($tree[$key]['below'], $depth_limit-1);
      }
      else {
        // Remove the children items.
        $tree[$key]['below'] = FALSE;
      }
    }
    if ($depth_limit == 1 && $tree[$key]['link']['has_children']) {
      // Turn off the menu styling that shows there were children.
      $tree[$key]['link']['has_children'] = FALSE;
      $tree[$key]['link']['leaf_has_children'] = TRUE;
    }
  }
}

/**
 * Returns a renderable menu tree.
 *
 * This is a copy of menu_tree_output() with additional classes added to the
 * output.
 *
 * @param array $tree
 *   A data structure representing the tree as returned from menu_tree_data.
 * @param array $config
 *
 * @return array
 *   The menu tree as a render array.
 */
function menu_block_tree_output(array &$tree, array $config = array()) {
  $build = array();
  $items = array();

  // Create context if no config was provided.
  if (empty($config)) {
    $config['delta'] = 0;
    // Grab any menu item to find the menu_name for this tree.
    $menu_item = current($tree);
    $config['menu_name'] = $menu_item['link']['menu_name'];
  }
  $hook_delta = str_replace('-', '_', $config['delta']);
  $hook_menu_name = str_replace('-', '_', $config['menu_name']);

  // Pull out just the menu links we are going to render so that we
  // get an accurate count for the first/last classes.
  foreach ($tree as $key => &$value) {
    if ($tree[$key]['link']['access'] && !$tree[$key]['link']['hidden']) {
      $items[] = $tree[$key];
    }
  }

  $router_item = menu_get_item();
  $num_items = count($items);
  foreach ($items as $i => &$data) {
    $class = array();
    if ($i == 0) {
      $class[] = 'first';
    }
    if ($i == $num_items - 1) {
      $class[] = 'last';
    }
    // Set a class for the <li>-tag. Since $data['below'] may contain local
    // tasks, only set 'expanded' class if the link also has children within
    // the current menu.
    if ($data['link']['has_children'] && $data['below']) {
      $class[] = 'expanded';
    }
    elseif ($data['link']['has_children']) {
      $class[] = 'collapsed';
    }
    else {
      $class[] = 'leaf';
    }
    if (!empty($data['link']['leaf_has_children'])) {
      $class[] = 'has-children';
    }
    // Set a class if the link is in the active trail.
    if ($data['link']['in_active_trail']) {
      $class[] = 'active-trail';
      $data['link']['localized_options']['attributes']['class'][] = 'active-trail';
    }
    if ($data['link']['href'] == $_GET['q'] || ($data['link']['href'] == '<front>' && drupal_is_front_page())) {
      $class[] = 'active';
    }
    // Set a menu link ID class.
    $class[] = 'menu-mlid-' . $data['link']['mlid'];
    // Normally, l() compares the href of every link with $_GET['q'] and sets
    // the active class accordingly. But local tasks do not appear in menu
    // trees, so if the current path is a local task, and this link is its
    // tab root, then we have to set the class manually.
    if ($data['link']['href'] == $router_item['tab_root_href'] && $data['link']['href'] != $_GET['q']) {
      $data['link']['localized_options']['attributes']['class'][] = 'active';
    }

    // Allow menu-specific theme overrides.
    $element['#theme'] = array(
      'menu_link__menu_block__' . $hook_delta,
      'menu_link__menu_block__' . $hook_menu_name,
      'menu_link__menu_block',
      'menu_link__' . $hook_menu_name,
      'menu_link',
    );
    $element['#attributes']['class'] = $class;
    $element['#title'] = $data['link']['title'];
    $element['#href'] = $data['link']['href'];
    $element['#localized_options'] = !empty($data['link']['localized_options']) ? $data['link']['localized_options'] : array();
    $element['#below'] = $data['below'] ? menu_block_tree_output($data['below'], $config) : $data['below'];
    $element['#original_link'] = $data['link'];
    $element['#bid'] = array('module' => 'menu_block', 'delta' => $config['delta']);
    // Index using the link's unique mlid.
    $build[$data['link']['mlid']] = $element;
  }
  if ($build) {
    // Make sure drupal_render() does not re-order the links.
    $build['#sorted'] = TRUE;
    // Add the theme wrapper for outer markup.
    // Allow menu-specific theme overrides.
    $build['#theme_wrappers'][] = array(
      'menu_tree__menu_block__' . $hook_delta,
      'menu_tree__menu_block__' . $hook_menu_name,
      'menu_tree__menu_block',
      'menu_tree__' . $hook_menu_name,
      'menu_tree',
    );
  }

  return $build;
}

/**
 * Implements hook_menu_block_get_menus() on behalf of book.module.
 */
function book_menu_block_get_menus() {
  $menus = array();
  foreach (book_get_books() as $book) {
    $menus[$book['menu_name']] = $book['title'];
  }
  return $menus;
}

/**
 * Implements hook_menu_block_get_sort_menus() on behalf of book.module.
 */
function book_menu_block_get_sort_menus() {
  return array(
    '/^book\-toc\-.+/' => t('Book navigation'),
  );
}

/**
 * Implements hook_get_pane_links_alter().
 */
function menu_block_get_pane_links_alter(&$links, $pane, $content_type) {
  if ($pane->type === 'menu_tree') {
    if (in_array($pane->subtype, array_keys(menu_get_menus()))) {
      $links['top'][] = array(
        'title' => t('Edit menu links'),
        'href' => url('admin/structure/menu/manage/' . $pane->subtype, array('absolute' => TRUE)),
        'attributes' => array('target' => array('_blank')),
      );
    }
  }
}

/**
 * Implements hook_menu_insert().
 */
function menu_block_menu_insert($menu) {
  if (!empty($menu['menu_block_menu_order'])) {
    menu_block_menu_order_set_menu($menu['menu_name'], TRUE);
  }
}

/**
 * Implements hook_menu_update().
 */
function menu_block_menu_update($menu) {
  if (isset($menu['menu_block_menu_order'])) {
    menu_block_menu_order_set_menu($menu['menu_name'], $menu['menu_block_menu_order']);
  }
}

/**
 * Implements hook_menu_delete().
 */
function menu_block_menu_delete($menu) {
  // Delete menu block variables.
  foreach (variable_get('menu_block_ids', array()) as $delta) {
    $config = menu_block_get_config($delta);
    if ($config['menu_name'] === $menu['menu_name']) {
      menu_block_delete($delta);
    }
  }

  menu_block_menu_order_set_menu($menu['menu_name'], FALSE);
}

/**
 * Delete a menu block.
 *
 * @param string $delta
 *   The delta of the menu block.
 */
function menu_block_delete($delta) {
  // Since this used to be a form callback, prevent unintentional uses.
  if (is_array($delta)) {
    variable_set('menu_rebuild_needed', TRUE);
    return;
  }

  $block_ids = variable_get('menu_block_ids', array());
  $index = array_search($delta, $block_ids);
  if ($index !== FALSE && $config = menu_block_get_config($delta)) {
    module_invoke_all('menu_block_delete', $config);

    // Remove the delta from the list of custom IDs.
    unset($block_ids[$index]);
    sort($block_ids);
    variable_set('menu_block_ids', $block_ids);

    // Remove all the individual variables.
    $variable_keys = array_keys(menu_block_default_config());
    foreach ($variable_keys as $key) {
      variable_del("menu_block_{$delta}_{$key}");
    }
  }
}

/**
 * Implements hook_menu_block_delete() on behalf of block.module.
 */
function block_menu_block_delete(array $config) {
  db_delete('block')
    ->condition('module', 'menu_block')
    ->condition('delta', $config['delta'])
    ->execute();
  db_delete('block_role')
    ->condition('module', 'menu_block')
    ->condition('delta', $config['delta'])
    ->execute();
}

/**
 * Implements hook_menu_block_delete() on behalf of node.module.
 */
function node_menu_block_delete(array $config) {
  db_delete('block_node_type')
    ->condition('module', 'menu_block')
    ->condition('delta', $config['delta'])
    ->execute();
}

/**
 * Implements hook_form_FORM_ID_alter().
 */
function menu_block_form_menu_edit_menu_alter(&$form, &$form_state) {
  $menus = variable_get('menu_block_menu_order', array('main-menu' => '', 'user-menu' => ''));
  $form['menu_block_menu_order'] = array(
    '#type' => 'checkbox',
    '#title' => t('Include this menu in the <em>"the menu selected by the page"</em> menu available to menu blocks.'),
    '#default_value' => isset($menus[$form['old_name']['#value']]),
  );
}

/**
 * Add or remove a menu from the menu_block_menu_order variable.
 *
 * @param string $menu_name
 *   A menu machine name.
 * @param mixed $status
 *   If $status evaluates to TRUE, the menu will be added. If $status evaluates
 *   to FALSE, the menu will be removed.
 */
function menu_block_menu_order_set_menu($menu_name, $status) {
  $menus = variable_get('menu_block_menu_order', array('main-menu' => '', 'user-menu' => ''));
  if ($status && !isset($menus[$menu_name])) {
    $menus[$menu_name] = '';
    variable_set('menu_block_menu_order', $menus);
  }
  elseif (!$status && isset($menus[$menu_name])) {
    unset($menus[$menu_name]);
    variable_set('menu_block_menu_order', $menus);
  }
}

/**
 * Implements hook_menu_link_insert().
 */
function menu_block_menu_link_insert($link) {
  // If a book is being created, updated, or deleted, clear the
  // menu_block_get_all_menus() cache since it means a change to a book "menu"
  // that would need to be picked up by book_menu_block_get_menus().
  if (strpos($link['menu_name'], 'book-toc-') === 0 && !$link['plid']) {
    cache_clear_all('menu_block_menus:', 'cache_menu', TRUE);
    drupal_static_reset('menu_block_get_all_menus');
  }
}

/**
 * Implements hook_menu_link_update().
 */
function menu_block_menu_link_update($link) {
  menu_block_menu_link_insert($link);
}

/**
 * Implements hook_menu_link_delete().
 */
function menu_block_menu_link_delete($link) {
  menu_block_menu_link_insert($link);
}