hierarchical_select.module in Hierarchical Select 5.3

This module defines the "hierarchical_select" form element, which is a greatly enhanced way for letting the user select items in a hierarchy.

File

hierarchical_select.module

<?php

/**
 * @file
 * This module defines the "hierarchical_select" form element, which is a
 * greatly enhanced way for letting the user select items in a hierarchy.
 */

// Make sure that the devel module is installed when you enable developer mode!
define('HS_DEVELOPER_MODE', 0);

//----------------------------------------------------------------------------

// Drupal core hooks.

/**
 * Implementation of hook_menu().
 */
function hierarchical_select_menu($may_cache) {
  if ($may_cache) {
    $items[] = array(
      'path' => 'hierarchical_select_json',
      'callback' => 'hierarchical_select_json',
      'type' => MENU_CALLBACK,
      // TODO: Needs improvements. Ideally, this would inherit the permissions
      // of the form the Hierarchical Select was in.
      'access' => TRUE,
    );
    $items[] = array(
      'path' => 'admin/settings/hierarchical_select',
      'title' => t('Hierarchical Select'),
      'description' => t('Configure site-wide settings for the Hierarchical Select form element.'),
      'callback' => 'drupal_get_form',
      'callback arguments' => array(
        'hierarchical_select_admin_settings',
      ),
      'type' => MENU_NORMAL_ITEM,
    );
    $items[] = array(
      'path' => 'admin/settings/hierarchical_select/settings',
      'title' => t('Site-wide settings'),
      'weight' => -10,
      'type' => MENU_DEFAULT_LOCAL_TASK,
    );
    $items[] = array(
      'path' => 'admin/settings/hierarchical_select/configs',
      'title' => t('Configurations'),
      'description' => t('All available Hierarchical Select configurations.'),
      'callback' => 'hierarchical_select_admin_configs',
      'type' => MENU_LOCAL_TASK,
    );
    $items[] = array(
      'path' => 'admin/settings/hierarchical_select/implementations',
      'title' => t('Implementations'),
      'description' => t('Features of each Hierarchical Select implementation.'),
      'callback' => 'hierarchical_select_admin_implementations',
      'type' => MENU_LOCAL_TASK,
    );
  }
  else {

    // Work-around for bug in Drupal 5 (fixed in Drupal 5.8).
    // See http://drupal.org/node/109459.
    global $user;
    if (!isset($user->theme)) {
      $user->theme = variable_get('theme_default', 'garland');
    }
    if (arg(0) == 'admin' && arg(1) == 'settings' && arg(2) == 'hierarchical_select') {
      require_once drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select.admin.inc';
      if (in_array(arg(3), array(
        'export',
        'import',
      ))) {
        require_once drupal_get_path('module', 'hierarchical_select') . '/includes/common.inc';
        $items[] = array(
          'path' => 'admin/settings/hierarchical_select/export/' . arg(4),
          'title' => t('Export'),
          'callback' => 'drupal_get_form',
          'callback arguments' => array(
            'hierarchical_select_admin_export',
            arg(4),
          ),
          'type' => MENU_LOCAL_TASK,
        );
        $items[] = array(
          'path' => 'admin/settings/hierarchical_select/import/' . arg(4),
          'title' => t('Import'),
          'callback' => 'drupal_get_form',
          'callback arguments' => array(
            'hierarchical_select_admin_import',
            arg(4),
          ),
          'type' => MENU_LOCAL_TASK,
        );
      }
    }
  }
  return $items;
}

/**
 * Implementation of hook_form_alter().
 */
function hierarchical_select_form_alter($form_id, &$form) {
  if (_hierarchical_select_form_has_hierarchical_select($form)) {
    $form['#after_build'][] = 'hierarchical_select_after_build';
  }
}

/**
 * Implementation of hook_elements().
 */
function hierarchical_select_elements() {
  $type['hierarchical_select'] = array(
    '#input' => TRUE,
    '#process' => array(
      'hierarchical_select_process' => array(),
    ),
    '#config' => array(
      'module' => 'some_module',
      'params' => array(),
      'save_lineage' => 0,
      'enforce_deepest' => 0,
      'entity_count' => 0,
      'resizable' => 1,
      'level_labels' => array(
        'status' => 0,
        'labels' => array(),
      ),
      'dropbox' => array(
        'status' => 0,
        'title' => t('All selections'),
        'limit' => 0,
        'reset_hs' => 1,
      ),
      'editability' => array(
        'status' => 0,
        'item_types' => array(),
        'allowed_levels' => array(),
        'allow_new_levels' => 0,
        'max_levels' => 3,
      ),
      'animation_delay' => variable_get('hierarchical_select_animation_delay', 400),
      'exclusive_lineages' => array(),
      'render_flat_select' => 0,
    ),
    '#default_value' => -1,
  );
  return $type;
}

/**
 * Implementation of hook_requirements().
 */
function hierarchical_select_requirements($phase) {
  $requirements = array();
  if ($phase == 'runtime') {

    // Check if all hook_update_n() hooks have been executed.
    require_once 'includes/install.inc';
    drupal_load_updates();
    $updates = drupal_get_schema_versions('hierarchical_select');
    $current = drupal_get_installed_schema_version('hierarchical_select');
    $up_to_date = end($updates) == $current;
    $jquery_update_v2 = file_exists(drupal_get_path('module', 'jquery_update') . '/compat.js');
    $jquery_interface = module_exists('jquery_interface');
    $hierarchical_select_weight = db_result(db_query("SELECT weight FROM {system} WHERE type = 'module' AND name = 'hierarchical_select'"));
    $core_overriding_modules = array(
      'hs_book',
      'hs_menu',
      'hs_taxonomy',
    );
    $path_errors = array();
    foreach ($core_overriding_modules as $module) {
      $filename = db_result(db_query("SELECT filename FROM {system} WHERE type = 'module' AND name = '%s'", $module));
      if (strpos($filename, 'modules/') === 0) {
        $module_info = _module_parse_info_file(dirname($filename) . "/{$module}.info");
        $path_errors[] = t('!module', array(
          '!module' => $module_info['name'],
        ));
      }
    }
    $weight_errors = array();
    foreach (module_implements('hierarchical_select_root_level') as $module) {
      $weight = db_result(db_query("SELECT weight FROM {system} WHERE name = '%s'", $module));
      if (!($hierarchical_select_weight > $weight)) {
        $filename = db_result(db_query("SELECT filename FROM {system} WHERE type = 'module' AND name = '%s'", $module));
        $module_info = _module_parse_info_file(dirname($filename) . "/{$module}.info");
        $weight_errors[] = t('!module (!weight)', array(
          '!module' => $module_info['name'],
          '!weight' => $weight,
        ));
      }
    }
    if ($up_to_date && $jquery_update_v2 && !$jquery_interface && !count($path_errors) && !count($weight_errors)) {
      $value = t('All updates installed. jQuery Update 2.x installed. Implementation modules are installed correctly.');
      $description = '';
      $severity = REQUIREMENT_OK;
    }
    elseif (!$up_to_date) {
      $value = t('Not all updates installed!');
      $description = t('Please run update.php to install the latest updates!
        You have installed update !installed_update, but the latest update is
        !latest_update!', array(
        '!installed_update' => $current,
        '!latest_update' => end($updates),
      ));
      $severity = REQUIREMENT_ERROR;
    }
    elseif (!$jquery_update_v2) {
      $value = t('jQuery Update 1.x installed!');
      $description = t('Please upgrade to jQuery Update 2.x! jQuery Update
        1.x contains jQuery 1.1.x, which is incompatible with the Javascript
        code of Hierarchical Select!');
      $severity = REQUIREMENT_ERROR;
    }
    elseif ($jquery_interface) {
      $value = t('jQuery Interface installed!');
      $description = t('Please disable and uninstall jQuery Interface, as it
        is incompatible with jQuery Update 2. It is very buggy anyway and any
        module that uses it should upgrade to jQuery UI.');
      $severity = REQUIREMENT_ERROR;
    }
    elseif ($path_errors) {
      $value = t('Modules incorrectly installed!');
      $description = t("The following modules implement Hierarchical Select module for Drupal\n        core modules, but are installed in the wrong location. They're\n        installed in core's <code>modules</code> directory, but should be\n        installed in either the <code>sites/all/modules</code> directory or a\n        <code>sites/yoursite.com/modules</code> directory") . ':' . theme('item_list', $path_errors);
      $severity = REQUIREMENT_ERROR;
    }
    elseif ($weight_errors) {
      $value = t('Module weight incorrectly configured!');
      $description = t('The weight of the Hierarchical Select module (!weight) is not
        strictly higher than the weight of the following modules', array(
        '!weight' => $hierarchical_select_weight,
      )) . ':' . theme('item_list', $weight_errors);
      $severity = REQUIREMENT_ERROR;
    }
    $requirements['hierarchical_select'] = array(
      'title' => t('Hierarchical Select'),
      'value' => $value,
      'description' => $description,
      'severity' => $severity,
    );
  }
  return $requirements;
}

//----------------------------------------------------------------------------

// Menu callbacks.

/**
 * Menu callback; format=text/json; generates and outputs the appropriate HTML.
 */
function hierarchical_select_json() {

  // We are returning Javascript, so tell the browser. Ripped from Drupal 6's
  // drupal_json() function.
  drupal_set_header('Content-Type: text/javascript; charset=utf-8');
  $hs_form_build_id = $_POST['hs_form_build_id'];
  $hs_form_build_id = _hierarchical_select_get_hs_form_build_id();

  // Collect all necessary variables.
  $cached = cache_get($hs_form_build_id, 'cache');
  $storage = unserialize($cached->data);

  // Ensure that the form id in the POST array is the same as the one of the
  // stored parameters of the original form. For 99% of the forms, this step
  // is not necessary, but when a hierarchical_select form item is inside a
  // form in a subform_element in a form, then it is necessary.
  $form_id = $_POST['form_id'] = $storage['parameters'][0];

  // Pick the correct language.
  if (module_exists('i18n')) {
    i18n_selection_mode($storage['i18n']['mode'], $storage['i18n']['params']);
  }
  if (HS_DEVELOPER_MODE) {
    _hierarchical_select_log("form_id: {$form_id}");
    _hierarchical_select_log("hs_form_build_id: {$hs_form_build_id}");
  }

  // Retrieve and process the form.
  $form = call_user_func_array('drupal_retrieve_form', $storage['parameters']);
  drupal_prepare_form($form_id, $form);

  // Render only the relevant part of the form (i.e. the hierarchical_select
  // form item that has triggered this AJAX callback).
  $hsid = $_POST['hsid'];
  $name = $storage['#names'][$hsid];
  $part_of_form = _hierarchical_select_get_form_item($form, $name);
  $output = drupal_render($part_of_form);

  // If the user's browser supports the active cache system, then send the
  // currently requested hierarchy in an easy-to-manage form.
  $cache = array();
  if ($_POST['client_supports_caching'] == 'true') {
    $cache = _hierarchical_select_json_convert_hierarchy_to_cache($part_of_form['hierarchy']['#value']);
  }
  else {
    if ($_POST['client_supports_caching'] == 'false') {

      // This indicates that a client-side cache is installed, but not working
      // properly.
      // TODO: figure out a clean way to notify the administrator.
    }
  }
  print drupal_to_js(array(
    'cache' => $cache,
    'output' => $output,
    'log' => $part_of_form['log']['#value'],
  ));
  exit;
}

//----------------------------------------------------------------------------

// Forms API callbacks.

/**
 * Hierarchical select form element type #process callback.
 */
function hierarchical_select_process($element) {
  if (!isset($element['#value']['hsid'])) {

    // The HSID is stored in the session, to allow for multiple Hierarchical
    // Select form items on the same page of which at least one is added through
    // AHAH. A normal static variable won't do in this case, because then at
    // least two Hierarchical Select form items will have HSID 0, because they
    // are generated in different requests, both of which will have a first HSID
    // of 0. This will then cause problems on the page.
    if (!isset($_SESSION['hsid'])) {
      $_SESSION['hsid'] = 0;
    }
    else {

      // Let the HSID go from 0 to 99, then start over. Larger numbers are
      // pointless: who's going to use more than a hundred Hierarchical Select
      // form items on the same page?
      $_SESSION['hsid'] = ($_SESSION['hsid'] + 1) % 100;
    }
    $hsid = $_SESSION['hsid'];
  }
  else {
    $hsid = check_plain($element['#value']['hsid']);
  }
  $element['hsid'] = array(
    '#type' => 'hidden',
    '#value' => $hsid,
  );

  // A hierarchical_select form element expands to multiple items. For example
  // $element['hsid'] got set just above. If #value is not an array, then
  // form_set_value(), which is called by form_builder() will fail, because it
  // assumes that #value is an array, because we are trying to set a child of
  // it.
  if (!is_array($element['#value'])) {
    $element['#value'] = array(
      $element['#value'],
    );
  }

  // Store the #name property of each hierarchical_select form item, this is
  // necessary to find this form item back in an AJAX callback.
  _hierarchical_select_store_name($element, $hsid);

  // Set up Javascript and add settings specifically for the current
  // hierarchical select.
  _hierarchical_select_setup_js();
  $config = _hierarchical_select_inherit_default_config($element['#config']);
  drupal_add_js(array(
    'HierarchicalSelect' => array(
      'settings' => array(
        $hsid => array(
          'animationDelay' => $config['animation_delay'] == 0 ? (int) variable_get('hierarchical_select_animation_delay', 400) : $config['animation_delay'],
          'cacheId' => $config['module'] . '_' . implode('_', is_array($config['params']) ? $config['params'] : array()),
          'renderFlatSelect' => isset($config['render_flat_select']) ? (int) $config['render_flat_select'] : 0,
          'createNewItems' => isset($config['editability']['status']) ? (int) $config['editability']['status'] : 0,
          'createNewLevels' => isset($config['editability']['allow_new_levels']) ? (int) $config['editability']['allow_new_levels'] : 0,
          'resizable' => isset($config['resizable']) ? (int) $config['resizable'] : 0,
        ),
      ),
    ),
  ), 'setting');

  // Basic config validation and diagnostics.
  if (HS_DEVELOPER_MODE) {
    $diagnostics = array();
    if (!isset($config['module']) || empty($config['module'])) {
      $diagnostics[] = t("'module is not set!");
    }
    elseif (!module_exists($config['module'])) {
      $diagnostics[] = t('the module that should be used (module) is not installed!', array(
        '%module' => $config['module'],
      ));
    }
    else {
      $required_params = module_invoke($config['module'], 'hierarchical_select_params');
      $missing_params = array_diff($required_params, array_keys($config['params']));
      if (!empty($missing_params)) {
        $diagnostics[] = t("'params' is missing values for: ") . implode(', ', $missing_params) . '.';
      }
    }
    $config_id = isset($config['config_id']) && is_string($config['config_id']) ? $config['config_id'] : 'none';
    if (empty($diagnostics)) {
      _hierarchical_select_log("Config diagnostics (config id: {$config_id}): no problems found!");
    }
    else {
      $diagnostics_string = print_r($diagnostics, TRUE);
      $message = "Config diagnostics (config id: {$config_id}): {$diagnostics_string}";
      _hierarchical_select_log($message);
      $element['#type'] = 'item';
      $element['#value'] = '<p><span style="color:red;">Fix the indicated errors in the #config property first!</span><br />' . nl2br($message) . '</p>';
      return $element;
    }
  }

  // Calculate the selections in both the hierarchical select and the dropbox,
  // we need these before we can render anything.
  list($hs_selection, $db_selection) = _hierarchical_select_process_calculate_selections($element);
  if (HS_DEVELOPER_MODE) {
    _hierarchical_select_log("Calculated hierarchical select selection:");
    _hierarchical_select_log($hs_selection);
    if ($config['dropbox']['status']) {
      _hierarchical_select_log("Calculated dropbox selection:");
      _hierarchical_select_log($db_selection);
    }
  }

  // If the exclusive_lineages setting has been configured, and the dropbox
  // is enabled, then do the necessary processing to make exclusive lineages
  // possible.
  if (count($config['exclusive_lineages']) && $config['dropbox']['status']) {

    // When the form is first loaded, $db_selection will contain the selection
    // that we should check, but in updates, $hs_selection will.
    $selection = !empty($hs_selection) ? $hs_selection : $db_selection;

    // If the current selection of the hierarchical select matches one of the
    // configured exclusive items, then disable the dropbox (to ensure an
    // exclusive selection).
    if (in_array($selection, $config['exclusive_lineages']) || count($selection) == 1 && in_array($selection[0], $config['exclusive_lineages'])) {

      // An item at the root level.
      // By also updating the configuration stored in $element, we ensure that
      // the validation step, which extracts the configuration again, also gets
      // the updated config.
      $element['#config']['dropbox']['status'] = 0;
      $config = _hierarchical_select_inherit_default_config($element['#config']);

      // When the form is first loaded, $db_selection contained the selection
      // selection that we checked for. Since we've now disabled the dropbox,
      // we should overwrite $hs_selection with the value of $db_selection and
      // reset $db_selection.
      if (empty($hs_selection)) {
        $hs_selection = $db_selection;
        $db_selection = array();
      }
    }
  }

  // Generate the $hierarchy and $dropbox objects using the selections that
  // were just calculated.
  $dropbox = !$config['dropbox']['status'] ? FALSE : _hierarchical_select_dropbox_generate($config, $db_selection);
  $hierarchy = _hierarchical_select_hierarchy_generate($config, $hs_selection, $element['#required'], $dropbox);
  if (HS_DEVELOPER_MODE) {
    _hierarchical_select_log('Generated hierarchy in ' . $hierarchy->build_time['total'] . ' ms:');
    _hierarchical_select_log($hierarchy);
    if ($config['dropbox']['status']) {
      _hierarchical_select_log('Generated dropbox in ' . $dropbox->build_time . ' ms: ');
      _hierarchical_select_log($dropbox);
    }
  }

  // Store the hierarchy object in the element, we'll need this if the user's
  // browser supports the active cache system.
  $element['hierarchy'] = array(
    '#type' => 'value',
    '#value' => $hierarchy,
  );

  // Ensure that #tree is enabled!
  $element['#tree'] = TRUE;

  // If render_flat_select is enabled, render a flat select.
  if ($config['render_flat_select']) {
    $element['flat_select'] = _hierarchical_select_process_render_flat_select($hierarchy, $dropbox, $config);
  }

  // Render the hierarchical select.
  $element['hierarchical_select'] = array(
    '#theme' => 'hierarchical_select_selects_container',
  );
  $element['hierarchical_select']['selects'] = _hierarchical_select_process_render_hs_selects($hsid, $hierarchy);

  // The selects in the hierarchical select should inherit the #size property.
  foreach (element_children($element['hierarchical_select']['selects']) as $depth) {
    $element['hierarchical_select']['selects'][$depth]['#size'] = $element['#size'];
  }

  // Check if a new item is being created.
  $creating_new_item = FALSE;
  if (isset($element['#value']['hierarchical_select']['selects'])) {
    foreach ($element['#value']['hierarchical_select']['selects'] as $depth => $value) {
      if ($value == 'create_new_item' && _hierarchical_select_create_new_item_is_allowed($config, $depth)) {
        $creating_new_item = TRUE;

        // We want to override the select in which the "create_new_item"
        // option was selected and hide all selects after that, if they exist.
        for ($i = $depth; $i < count($hierarchy->lineage); $i++) {
          unset($element['hierarchical_select']['selects'][$i]);
        }
        $element['hierarchical_select']['create_new_item'] = array(
          '#prefix' => '<div class="' . str_replace('_', '-', $value) . '">',
          '#suffix' => '</div>',
        );
        $item_type_depth = $value == 'create_new_item' ? $depth : $depth + 1;
        $item_type = !empty($config['editability']['item_types'][$item_type_depth]) ? t($config['editability']['item_types'][$item_type_depth]) : t('item');
        $element['hierarchical_select']['create_new_item']['input'] = array(
          '#type' => 'textfield',
          '#size' => 20,
          '#maxlength' => 255,
          '#default_value' => t('new @item', array(
            '@item' => $item_type,
          )),
          '#attributes' => array(
            'title' => t('new @item', array(
              '@item' => $item_type,
            )),
            'class' => 'create-new-item-input',
          ),
          // Use a #theme callback to prevent the textfield from being wrapped
          // in a div. This simplifies the CSS and JS code.
          '#theme' => 'hierarchical_select_textfield',
        );
        $element['hierarchical_select']['create_new_item']['create'] = array(
          '#type' => 'button',
          '#value' => t('Create'),
          '#attributes' => array(
            'class' => 'create-new-item-create',
          ),
        );
        $element['hierarchical_select']['create_new_item']['cancel'] = array(
          '#type' => 'button',
          '#value' => t('Cancel'),
          '#attributes' => array(
            'class' => 'create-new-item-cancel',
          ),
        );
      }
    }
  }
  if ($config['dropbox']['status']) {
    if (!$creating_new_item) {

      // Append an "Add" button to the selects.
      $element['hierarchical_select']['dropbox_add'] = array(
        '#type' => 'button',
        '#value' => t('Add'),
        '#attributes' => array(
          'class' => 'add-to-dropbox',
        ),
      );
    }
    if ($config['dropbox']['limit'] > 0) {

      // Zero as dropbox limit means no limit.
      if (count($dropbox->lineages) == $config['dropbox']['limit']) {
        $element['dropbox_limit_warning'] = array(
          '#value' => t("You've reached the maximal number of items you can select."),
          '#prefix' => '<p class="hierarchical-select-dropbox-limit-warning">',
          '#suffix' => '</p>',
        );

        // Disable all child form elements of $element['hierarchical_select].
        _hierarchical_select_mark_as_disabled($element['hierarchical_select']);
      }
    }

    // Add the hidden part of the dropbox. This will be used to store the
    // currently selected lineages.
    $element['dropbox']['hidden'] = array(
      '#prefix' => '<div class="dropbox-hidden">',
      '#suffix' => '</div>',
    );
    $element['dropbox']['hidden'] = _hierarchical_select_process_render_db_hidden($hsid, $dropbox);

    // Add the dropbox-as-a-table that will be visible to the user.
    $element['dropbox']['visible'] = _hierarchical_select_process_render_db_visible($hsid, $dropbox);
  }

  // This button and accompanying help text will be hidden when Javascript is
  // enabled.
  $element['nojs'] = array(
    '#prefix' => '<div class="nojs">',
    '#suffix' => '</div>',
  );
  $element['nojs']['update_button'] = array(
    '#type' => 'button',
    '#value' => t('Update'),
    '#attributes' => array(
      'class' => 'update-button',
    ),
  );
  $element['nojs']['update_button_help_text'] = array(
    '#value' => _hierarchical_select_nojs_helptext($config['dropbox']['status']),
    '#prefix' => '<div class="help-text">',
    '#suffix' => '</div>',
  );

  // Ensure the render order is correct.
  $element['hierarchical_select']['#weight'] = 0;
  $element['dropbox_limit_warning']['#weight'] = 1;
  $element['dropbox']['#weight'] = 2;
  $element['nojs']['#weight'] = 3;

  // This prevents values from in $element['#post'] to be used instead of the
  // generated default values (#default_value).
  // For example: $element['hierarchical_select']['selects']['0']['#default_value']
  // is set to 'label_0' after an "Add" operation. When $element['#post'] is
  // NOT unset, the corresponding value in $element['#post'] will be used
  // instead of the default value that was set. This is undesired behavior.
  unset($element['#post']);

  // Finally, calculate the return value of this hierarchical_select form
  // element. This will be set in _hierarchical_select_validate(). (If we'd
  // set it now, it would be overridden again.)
  $element['#return_value'] = _hierarchical_select_process_calculate_return_value($hierarchy, $config['dropbox']['status'] ? $dropbox : FALSE, $config['module'], $config['params'], $config['save_lineage']);

  // Add a validate callback, which will:
  // - validate that the dropbox limit was not exceeded.
  // - set the return value of this form element.
  $element['#validate'] = array(
    '_hierarchical_select_validate' => array(),
  );
  if (HS_DEVELOPER_MODE) {
    $element['log'] = array(
      '#type' => 'value',
      '#value' => _hierarchical_select_log(NULL, TRUE),
    );
    drupal_add_js(array(
      'HierarchicalSelect' => array(
        'initialLog' => array(
          $hsid => $element['log']['#value'],
        ),
      ),
    ), 'setting');
  }

  // If the form item is marked as disabled, disable all child form items as
  // well.
  if ($element['#disabled']) {
    _hierarchical_select_mark_as_disabled($element);
  }
  return $element;
}

/**
 * Hierarchical select form element type #after_build callback.
 */
function hierarchical_select_after_build($form, $form_values) {
  $names = _hierarchical_select_store_name(NULL, NULL, TRUE);
  $post_hs_form_build_id = _hierarchical_select_get_hs_form_build_id();
  if (!isset($post_hs_form_build_id) && count($names)) {
    $parameters = isset($form['#parameters']) ? $form['#parameters'] : array();

    // Collect information in this array, which will be used in dynamic form
    // updates, to …
    $storage = array(
      // … retrieve $form.
      'parameters' => $parameters,
      // … determine which part of $form should be rendered.
      '#names' => $names,
    );
    if (module_exists('i18n')) {
      $storage['i18n'] = array(
        'mode' => i18n_selection_mode(),
        'params' => i18n_selection_mode('params'),
      );
    }

    // 6 hours cache life time for forms should be plenty.
    $expire = 21600;

    // Store the information needed for dynamic form updates in the cache, so
    // we can retrieve this in our JSON callbacks (to be able to rebuild and
    // render part of the form).
    $hs_form_build_id = 'hs_form_' . md5(mt_rand());
    cache_set($hs_form_build_id, 'cache', serialize($storage), time() + $expire);
  }
  elseif (isset($post_hs_form_build_id)) {

    // Don't generate a new hs_form_build_id if this is a re-rendering of the
    // same form!
    $hs_form_build_id = $post_hs_form_build_id;
  }

  // Store the hs_form_build_id in a hidden value, so that it gets POSTed.
  $form_element = array(
    '#type' => 'hidden',
    '#value' => $hs_form_build_id,
    // We have to set #parents manually because we want to send only
    // $form_element through form_builder(), not $form. If we set #parents,
    // form_builder() has all info it needs to generate #name and #id.
    '#parents' => array(
      'hs_form_build_id',
    ),
  );
  $form['hs_form_build_id'] = form_builder($form['form_id']['#value'], $form_element);

  // Pass the hs_form_build_id to a custom submit function that will clear
  // the associated values from the cache.
  $form['#submit']['_hierarchical_select_submit'] = array(
    $post_hs_form_build_id,
  );
  return $form;
}

/**
 * Hierarchical select form element #validate callback.
 */
function _hierarchical_select_validate(&$element) {

  // If the dropbox is enabled and a dropbox limit is configured, check if
  // this limit is not exceeded.
  $config = _hierarchical_select_inherit_default_config($element['#config']);
  if ($config['dropbox']['status']) {
    if ($config['dropbox']['limit'] > 0) {

      // Zero as dropbox limit means no limit.
      // TRICKY: #validate is not called upon the initial rendering (i.e. it
      // is assumed that the default value is valid). However, Hierarchical
      // Select's config can influence the validity (i.e. how many selections
      // may be added to the dropbox). This means it's possible the user has
      // actually selected too many items without being notified of this.
      $lineage_count = count($element['#value']['dropbox']['hidden']['lineages_selections']);
      if ($lineage_count > $config['dropbox']['limit']) {

        // TRICKY: this should propagate the error down to the children, but
        // this doesn't seem to happen, since for example the selects of the
        // hierarchical select don't get the error class set. Further
        // investigation needed.
        form_error($element, t("You've selected %lineage-count items, but you're only allowed to select %dropbox-limit items.", array(
          '%lineage-count' => $lineage_count,
          '%dropbox-limit' => $config['dropbox']['limit'],
        )));
        _hierarchical_select_form_set_error_class($element);
      }
    }
  }

  // Set the proper return value. I.e. instead of returning all the values
  // that are used for making the hierarchical_select form element type work,
  // we pass a flat array of item ids. e.g. for the taxonomy module, this will
  // be an array of term ids. If a single item is selected, this will not be
  // an array.
  // If the form item is disabled, set the default value as the return value,
  // because otherwise nothing would be returned (disabled form items are not
  // submitted, as described in the HTML standard).
  if ($element['#disabled']) {
    $element['#return_value'] = $element['#default_value'];
  }

  // If the array is empty, set 0 as the value, which the Forms API
  // detects as an empty form value.
  $value = empty($element['#return_value']) ? 0 : $element['#return_value'];
  $element['#value'] = $value;
  form_set_value($element, $value);

  // We have to check again for errors. This line is taken litterally from
  // form.inc, so it works in an identical way.
  if ($element['#required'] && empty($element['#value']) && $element['#value'] !== '0') {
    form_error($element, t('!name field is required.', array(
      '!name' => $element['#title'],
    )));
    _hierarchical_select_form_set_error_class($element);
  }
}

/**
 * Hierarchical select form element #submit callback.
 */
function _hierarchical_select_submit($form_id, $form_values, $hs_form_build_id) {

  // Delete the stored form information when the form is submitted.
  cache_clear_all($hs_form_build_id, 'cache');
}

//----------------------------------------------------------------------------

// Forms API #process callback:
// Calculation of hierarchical select and dropbox selection.

/**
 * Get the current (flat) selection of the hierarchical select.
 *
 * This selection is updatable by the user, because the values are retrieved
 * from the selects in $element['hierarchical_select']['selects'].
 *
 * @param $element
 *   A hierarchical_select form element.
 * @return
 *   An array (bag) containing the ids of the selected items in the
 *   hierarchical select.
 */
function _hierarchical_select_process_get_hs_selection($element) {
  $hs_selection = array();
  $config = _hierarchical_select_inherit_default_config($element['#config']);
  if (count($element['#value']['hierarchical_select']['selects'])) {
    if ($config['save_lineage']) {
      foreach ($element['#value']['hierarchical_select']['selects'] as $key => $value) {
        $hs_selection[] = $value;
      }
    }
    else {
      foreach ($element['#value']['hierarchical_select']['selects'] as $key => $value) {
        $hs_selection[] = $value;
      }
      $hs_selection = _hierarchical_select_hierarchy_validate($hs_selection, $config['module'], $config['params']);

      // Get the last valid value. (Only the deepest item gets saved). Make
      // sure $hs_selection is an array at all times.
      $hs_selection = $hs_selection != -1 ? array(
        end($hs_selection),
      ) : array();
    }
  }
  return $hs_selection;
}

/**
 * Get the current (flat) selection of the dropbox.
 *
 * This selection is not updatable by the user, because the values are
 * retrieved from the hidden values in
 * $element['dropbox']['hidden']['lineages_selections']. This selection can
 * only be updated by the server, i.e. when the user clicks the "Add" button.
 * But this selection can still be reduced in size if the user has marked
 * dropbox entries (lineages) for removal.
 *
 * @param $element
 *   A hierarchical_select form element.
 * @return
 *   An array (bag) containing the ids of the selected items in the
 *   dropbox.
 */
function _hierarchical_select_process_get_db_selection($element) {
  $db_selection = array();
  if (count($element['#value']['dropbox']['hidden']['lineages_selections'])) {

    // This is only present in #value if at least one "Remove" checkbox was
    // checked, so ensure that we're doing something valid.
    $remove_from_db_selection = !isset($element['#value']['dropbox']['visible']['lineages']) ? array() : array_keys($element['#value']['dropbox']['visible']['lineages']);

    // Add all selections to the dropbox selection, except for the ones that
    // are scheduled for removal.
    foreach ($element['#value']['dropbox']['hidden']['lineages_selections'] as $x => $selection) {
      if (!in_array($x, $remove_from_db_selection)) {
        $db_selection = array_merge($db_selection, unserialize($selection));
      }
    }

    // Ensure that the last item of each selection that was scheduled for
    // removal is completely absent from the dropbox selection.
    // In case of a tree with multiple parents, the same item can exist in
    // different entries, and thus it would stay in the selection. When the
    // server then reconstructs all lineages, the lineage we're removing, will
    // also be reconstructed: it will seem as if the removing didn't work!
    // This will not break removing dropbox entries for hierarchies without
    // multiple parents, since items at the deepest level are always unique to
    // that specific lineage.
    // Easier explanation at http://drupal.org/node/221210#comment-733715.
    foreach ($remove_from_db_selection as $key => $x) {
      $item = end(unserialize($element['#value']['dropbox']['hidden']['lineages_selections'][$x]));
      $position = array_search($item, $db_selection);
      if ($position) {
        unset($db_selection[$position]);
      }
    }
    $db_selection = array_unique($db_selection);
  }
  return $db_selection;
}

/**
 * Calculates the flat selections of both the hierarchical select and the
 * dropbox.
 *
 * @param $element
 *   A hierarchical_select form element.
 * @return
 *   An array of the following structure:
 *   array(
 *     $hierarchical_select_selection = array(), // Flat list of selected ids.
 *     $dropbox_selection = array(),
 *   )
 *   with both of the subarrays flat lists of selected ids. The
 *   _hierarchical_select_hierarchy_generate() and
 *   _hierarchical_select_dropbox_generate() functions should be applied on
 *   these respective subarrays.
 *
 * @see _hierarchical_select_hierarchy_generate()
 * @see _hierarchical_select_dropbox_generate()
 */
function _hierarchical_select_process_calculate_selections(&$element) {
  $hs_selection = array();

  // hierarchical select selection
  $db_selection = array();

  // dropbox selection
  $config = _hierarchical_select_inherit_default_config($element['#config']);
  $dropbox = (bool) $config['dropbox']['status'];
  $op = $element['#post']['op'];
  if (empty($element['#post'])) {
    $value = isset($element['#value']) ? $element['#value'] : $element['#default_value'];
    $value = is_array($value) ? $value : array(
      $value,
    );
    if ($dropbox) {
      $db_selection = $value;
    }
    else {
      $hs_selection = $value;
    }
  }
  else {
    if ($dropbox && $op == t('Add')) {
      $hs_selection = _hierarchical_select_process_get_hs_selection($element);
      $db_selection = _hierarchical_select_process_get_db_selection($element);

      // Add $hs_selection to $db_selection (automatically filters to keep
      // only the unique ones).
      $db_selection = array_merge($db_selection, $hs_selection);

      // Only reset $hs_selection if the user has configured it that way.
      if ($config['dropbox']['reset_hs']) {
        $hs_selection = array();
      }
    }
    else {
      if ($op == t('Create')) {

        // This code handles both the creation of a new item in an existing
        // level and the creation of an item that also creates a new level.
        // TODO: http://drupal.org/node/253868
        // TODO: http://drupal.org/node/253869
        $label = trim($element['#value']['hierarchical_select']['create_new_item']['input']);
        $selects = $element['#value']['hierarchical_select']['selects'];
        $depth = count($selects);
        $parent = $depth > 0 ? end($selects) : 0;

        // Disallow items with empty labels; allow the user again to create a
        // (proper) new item.
        if (empty($label)) {
          $element['#value']['hierarchical_select']['selects'][count($selects)] = 'create_new_item';
        }
        else {
          if ((count(module_invoke($config['module'], 'hierarchical_select_children', $parent, $config['params'])) || $config['editability']['max_levels'] == 0 || $depth < $config['editability']['max_levels']) && _hierarchical_select_create_new_item_is_allowed($config, $depth)) {

            // Create the new item in the hierarchy and retrieve its value.
            $value = module_invoke($config['module'], 'hierarchical_select_create_item', check_plain($label), $parent, $config['params']);

            // Ensure the newly created item will be selected after rendering.
            if ($value) {

              // Pretend there was a select where the "create new item" section
              // was, and assign it the value of the item that was just created.
              $element['#value']['hierarchical_select']['selects'][count($selects)] = $value;
            }
          }
        }
        $hs_selection = _hierarchical_select_process_get_hs_selection($element);
        if ($dropbox) {
          $db_selection = _hierarchical_select_process_get_db_selection($element);
        }
      }
      else {

        // This handles the cases of:
        // - $op == t('Update')
        // - $op == t('Cancel') (used when creating a new item or a new level)
        // - any other submit button, e.g. the "Preview" button
        $hs_selection = _hierarchical_select_process_get_hs_selection($element);
        if ($dropbox) {
          $db_selection = _hierarchical_select_process_get_db_selection($element);
        }
      }
    }
  }

  // Prevent doubles in either array.
  $hs_selection = array_unique($hs_selection);
  $db_selection = array_unique($db_selection);
  return array(
    $hs_selection,
    $db_selection,
  );
}

//----------------------------------------------------------------------------

// Forms API #process callback:
// Rendering (generation of FAPI code) of hierarchical select and dropbox.

/**
 * Render the selects in the hierarchical select.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @param $hierarchy
 *   A hierarchy object.
 * @return
 *   A structured array for use in the Forms API.
 */
function _hierarchical_select_process_render_hs_selects($hsid, $hierarchy) {
  $form['#tree'] = TRUE;
  $form['#prefix'] = '<div class="selects">';
  $form['#suffix'] = '</div>';
  foreach ($hierarchy->lineage as $depth => $selected_item) {
    $form[$depth] = array(
      '#type' => 'select',
      '#options' => $hierarchy->levels[$depth],
      '#default_value' => $selected_item,
      // We need to skip the check of valid options, because they may be
      // modified after each update.
      '#DANGEROUS_SKIP_CHECK' => TRUE,
      // Use a #theme callback to prevent the select from being wrapped in a
      // div. This simplifies the CSS and JS code. Also sets a special class
      // on the level label option, if any, to make level label styles
      // possible.
      '#theme' => 'hierarchical_select_select',
      // Add child information. When a child has no children, its
      // corresponding "option" element will be marked as such.
      '#childinfo' => $hierarchy->childinfo[$depth],
    );
  }
  return $form;
}

/**
 * Render the hidden part of the dropbox. This part stores the lineages of all
 * selections in the dropbox.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @param $dropbox
 *   A dropbox object.
 * @return
 *   A structured array for use in the Forms API.
 */
function _hierarchical_select_process_render_db_hidden($hsid, $dropbox) {
  $element['#tree'] = TRUE;
  foreach ($dropbox->lineages_selections as $x => $lineage_selection) {
    $element['lineages_selections'][$x] = array(
      '#type' => 'hidden',
      '#value' => serialize($lineage_selection),
    );
  }
  return $element;
}

/**
 * Render the visible part of the dropbox.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @param $dropbox
 *   A dropbox object.
 * @return
 *   A structured array for use in the Forms API.
 */
function _hierarchical_select_process_render_db_visible($hsid, $dropbox) {
  $element['#tree'] = TRUE;
  $element['#theme'] = 'hierarchical_select_dropbox_table';

  // This information is necessary for the #theme callback.
  $element['title'] = array(
    '#type' => 'value',
    '#value' => t($dropbox->title),
  );
  $element['separator'] = array(
    '#type' => 'value',
    '#value' => '›',
  );
  $element['is_empty'] = array(
    '#type' => 'value',
    '#value' => empty($dropbox->lineages),
  );
  if (!empty($dropbox->lineages)) {
    foreach ($dropbox->lineages as $x => $lineage) {

      // Store position information for the lineage. This will be used in the
      // #theme callback.
      $element['lineages'][$x] = array(
        '#zebra' => ($x + 1) % 2 == 0 ? 'even' : 'odd',
        '#first' => $x == 0 ? 'first' : '',
        '#last' => $x == count($dropbox->lineages) - 1 ? 'last' : '',
      );

      // Create a 'markup' element for each item in the lineage.
      foreach ($lineage as $depth => $item) {

        // The item is selected when save_lineage is enabled (i.e. each item
        // will be selected), or when the item is the last item in the current
        // lineage.
        $is_selected = $dropbox->save_lineage || $depth == count($lineage) - 1;
        $element['lineages'][$x][$depth] = array(
          '#value' => $item['label'],
          '#prefix' => '<span class="dropbox-item' . ($is_selected ? ' dropbox-selected-item' : '') . '">',
          '#suffix' => '</span>',
        );
      }

      // Finally, create a "Remove" checkbox for the lineage.
      $element['lineages'][$x]['remove'] = array(
        '#type' => 'checkbox',
        '#title' => t('Remove'),
      );
    }
  }
  return $element;
}

/**
 * Render a flat select version of a hierarchical_select form element. This is
 * necessary for backwards compatibility (together with some Javascript code)
 * in case of GET forms.
 *
 * @param $hierarchy
 *   A hierarchy object.
 * @param $dropbox
 *   A dropbox object.
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - params
 *   - dropbox
 *     - status
 * @return
 *   A structured array for use in the Forms API.
 */
function _hierarchical_select_process_render_flat_select($hierarchy, $dropbox, $config) {
  $selection = array();
  if ($config['dropbox']['status']) {
    foreach ($dropbox->lineages_selections as $lineage_selection) {
      $selection = array_merge($selection, $lineage_selection);
    }
  }
  else {
    $selection = $hierarchy->lineage;
  }
  $options = array();
  foreach ($selection as $value) {
    $is_valid = module_invoke($config['module'], 'hierarchical_select_valid_item', $value, $config['params']);
    if ($is_valid) {
      $options[$value] = $value;
    }
  }
  $element = array(
    '#type' => 'select',
    '#multiple' => $config['save_lineage'] || $config['dropbox']['status'],
    '#options' => $options,
    '#default_value' => array_keys($options),
    // Use a #theme callback to prevent the select from being wrapped in a
    // div. This simplifies the CSS and JS code.
    '#theme' => 'hierarchical_select_select',
    '#attributes' => array(
      'class' => 'flat-select',
    ),
  );
  return $element;
}

/**
 * Calculate the return value of a hierarchical_select form element, based on
 * the $hierarchy and $dropbox objects. We have to set a return value, because
 * the values set and used by this form element ($element['#value]) are not
 * easily usable in the Forms API; we want to return a flat list of item ids.
 *
 * @param $hierarchy
 *   A hierarchy object.
 * @param $dropbox
 *   Optional. A dropbox object.
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $params
 *   Optional. An array of parameters, which may be necessary for some
 *   implementations.
 * @param $save_lineage
 *   Whether the save_lineage setting is enabled or not.
 * @return
 *   A single item id or a flat array of item ids.
 */
function _hierarchical_select_process_calculate_return_value($hierarchy, $dropbox = FALSE, $module, $params, $save_lineage) {
  if (!$dropbox) {
    $return_value = _hierarchical_select_hierarchy_validate($hierarchy->lineage, $module, $params);

    // If the save_lineage setting is disabled, keep only the deepest item.
    if (!$save_lineage) {
      $return_value = is_array($return_value) ? end($return_value) : NULL;
    }

    // Prevent a return value of -1. -1 is used for HS' internal system and
    // means "nothing selected", but to Drupal it *will* seam like a valid
    // value. Therefore, we set it to NULL.
    $return_value = $return_value != -1 ? $return_value : NULL;
  }
  else {
    $return_value = array();
    foreach ($dropbox->lineages_selections as $x => $selection) {
      if (!$save_lineage) {

        // An entry in the dropbox when the save_lineage setting is disabled
        // is only the deepest item of the generated lineage.
        $return_value[] = end($selection);
      }
      else {

        // An entry in the dropbox when the save_lineage setting is enabled is
        // the entire generated lineage, if it's valid (i.e. if the user has
        // not tampered with it).
        $lineage = _hierarchical_select_hierarchy_validate($selection, $module, $params);
        $return_value = array_merge($return_value, $lineage);
      }
    }
    $return_value = array_unique($return_value);
  }
  return $return_value;
}

//----------------------------------------------------------------------------

// Private functions.

/**
 * Inherit the default config from Hierarchical Selects' hook_elements().
 *
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - params
 * @return
 *   An updated config array.
 */
function _hierarchical_select_inherit_default_config($config, $defaults_override = array()) {

  // Set defaults for unconfigured settings. Get the defaults from our
  // hook_elements() implementation. Default properties from this hook are
  // applied automatically, but properties inside properties, such as is the
  // case for Hierarchical Select's #config property, aren't applied.
  $type = hierarchical_select_elements();
  $defaults = $type['hierarchical_select']['#config'];

  // Don't inherit the module and params settings.
  unset($defaults['module']);
  unset($defaults['params']);

  // Allow the defaults to be overridden.
  $defaults = array_smart_merge($defaults, $defaults_override);

  // Apply the defaults to the config.
  $config = array_smart_merge($defaults, $config);
  return $config;
}

/**
 * Helper function to add the required Javascript files and settings.
 */
function _hierarchical_select_setup_js() {
  static $ran_once;
  $jquery_ui_components = array(
    'effects.core',
    'effects.drop',
  );
  if (!$ran_once) {
    $ran_once = TRUE;
    $url = base_path();
    $url .= variable_get('clean_url', 0) ? '' : 'index.php?q=';
    $url .= 'hierarchical_select_json';

    // Add the CSS and JS, set the URL that should be used by all hierarchical
    // selects.
    drupal_add_css(drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select.css');
    drupal_add_js(drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select.js');
    if (variable_get('hierarchical_select_js_cache_system', 0) == 1) {
      drupal_add_js(drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select_cache.js');
    }
    if (!module_exists('jquery_form')) {
      drupal_add_js(drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select_formtoarray.js');
    }
    else {
      jquery_form_add();
    }
    if (!module_exists('jquery_ui')) {
      foreach ($jquery_ui_components as $component) {
        drupal_add_js(drupal_get_path('module', 'hierarchical_select') . "/js/jquery.ui/{$component}.js");
      }
    }
    else {
      jquery_ui_add($jquery_ui_components);
    }
    drupal_add_js(array(
      'HierarchicalSelect' => array(
        'url' => $url,
        'getArguments' => drupal_query_string_encode($_GET, array(
          'q',
        )),
      ),
    ), 'setting');
  }
}

/**
 * Convert a hierarchy object into an array of arrays that can be used for
 * caching an entire hierarchy in a client-side database.
 *
 * @param $hierarchy
 *   A hierarchy object.
 * @return
 *   An array of arrays.
 */
function _hierarchical_select_json_convert_hierarchy_to_cache($hierarchy) {

  // Convert the hierarchy object to an array of values like these:
  // array('value' => $term_id, 'label => $term_name, 'parent' => $term_id)
  $cache = array();
  foreach ($hierarchy->levels as $depth => $items) {
    $weight = 0;
    foreach ($items as $value => $label) {
      $weight++;
      $cache[] = array(
        'value' => $value,
        'label' => $label,
        'parent' => $depth == 0 ? 0 : $hierarchy->lineage[$depth - 1],
        'weight' => $weight,
      );
    }
  }

  // The last item in the lineage never has any children.
  $value = end($hierarchy->lineage);
  $cache[] = array(
    'value' => $value . '-has-no-children',
    // Construct a pseudo-value (will never be actually used).
    'label' => '',
    'parent' => $value,
    'weight' => 0,
  );
  return $cache;
}

/**
 * Helper function that marks every element in the given element as disabled.
 *
 * @param &$element
 *   The element of which we want to mark all elements as disabled.
 * @return
 *   A structured array for use in the Forms API.
 */
function _hierarchical_select_mark_as_disabled(&$element) {
  $element['#disabled'] = TRUE;

  // Recurse through all children:
  foreach (element_children($element) as $key) {
    if (isset($element[$key]) && $element[$key]) {
      _hierarchical_select_mark_as_disabled($element[$key]);
    }
  }
}

/**
 * Helper function to determine whether a given depth (i.e. the depth of a
 * level) is allowed by the allowed_levels setting.
 *
 * @param $config
 *   A config array with at least the following settings:
 *   - editability
 *     - allowed_levels
 * @param $depth
 *   A depth, starting from 0.
 * @return
 *   0 or 1 if it allowed_levels is set for the given depth, 1 otherwise.
 */
function _hierarchical_select_create_new_item_is_allowed($config, $depth) {
  return isset($config['editability']['allowed_levels'][$depth]) ? $config['editability']['allowed_levels'][$depth] : 1;
}

/**
 * Helper function that generates the help text is that is displayed to the
 * user when Javascript is disabled.
 *
 * @param $dropbox_is_enabled
 *   Indicates if the dropbox is enabled or not, the help text will be
 *   adjusted depending on this value.
 * @return
 *   The generated help text (in HTML).
 */
function _hierarchical_select_nojs_helptext($dropbox_is_enabled) {
  $output = '';

  // The options that will be used in the unordered list.
  $items = array(
    t('<span class="highlight">enable Javascript</span> in your browser and then refresh this page, for a much enhanced experience.'),
    t('<span class="highlight">click the <em>Update</em> button</span> every time you want to update the selection'),
  );
  $items[1] .= !$dropbox_is_enabled ? '.' : t(", or when you've checked some checkboxes for entries in the dropbox you'd like to remove.");
  $output .= '<span class="warning">';
  $output .= t("You don't have Javascript enabled.");
  $output .= '</span> ';
  $output .= '<span class="ask-to-hover">';
  $output .= t('Hover for more information!');
  $output .= '</span> ';
  $output .= t("But don't worry: you can still use this web site! You have two options:");
  $output .= theme('item_list', $items, NULL, 'ul', array(
    'class' => 'solutions',
  ));
  return $output;
}

/**
 * Get the form item that has the the given #name property.
 *
 * @param $form
 *   A structured array for use in the Forms API.
 * @param $name
 *   A #name value.
 * @return
 *   A form item.
 */
function _hierarchical_select_get_form_item($form, $name) {
  if (isset($form['#name']) && $form['#name'] == $name) {
    return $form;
  }

  // The current form item apparently is not the one we're looking for, so try
  // to find it in the child form items.
  foreach (element_children($form) as $child) {
    $form_item = _hierarchical_select_get_form_item($form[$child], $name);
    if ($form_item !== FALSE) {
      return $form_item;
    }
  }

  // No match in the children either, so return FALSE.
  return FALSE;
}

/**
 * Store the #name property of the given form item, so we can retrieve a list
 * of #name properties of hierarchical_select form items present in this form
 * later.
 *
 * @param $form_item
 *   Optional. A hierarchical_select form item.
 * @param $hsid
 *   Optional. A hierarchical select ID.
 * @param $reset
 *   Optional. Flag that marks if the stored #name properties should be reset.
 * @return
 *   The stored #name properties per hierarchical_select form item.
 */
function _hierarchical_select_store_name($form_item = NULL, $hsid = NULL, $reset = FALSE) {
  static $names;
  if ($reset) {
    $ret = $names;
    $names = array();
    return $ret;
  }
  if (isset($form_item) && isset($hsid)) {
    $names[$hsid] = $form_item['#name'];
  }
  return $names;
}

/**
 * Detect whether a form has at least one hierarchical_select form element.
 *
 * @param $form
 *   A structured array for use in the Forms API.
 * @return
 *   TRUE if the form contains a hierarchical_select form element, FALSE
 *   otherwise.
 */
function _hierarchical_select_form_has_hierarchical_select($form) {
  if ($form['#type'] == 'hierarchical_select') {
    return TRUE;
  }
  else {
    $has_hierarchical_select = FALSE;
    foreach (element_children($form) as $name) {
      if (is_array($form[$name])) {
        $has_hierarchical_select = _hierarchical_select_form_has_hierarchical_select($form[$name]);
        if ($has_hierarchical_select) {
          break;
        }
      }
    }
    return $has_hierarchical_select;
  }
}

/**
 * Set the 'error' class on the appropriate part of Hierarchical Select,
 * depending on its configuration.
 *
 * @param $element
 *   A Hierarchical Select form item.
 */
function _hierarchical_select_form_set_error_class(&$element) {
  $config = _hierarchical_select_inherit_default_config($element['#config']);
  if ($config['dropbox']['status']) {
    form_error($element['dropbox']['visible']);
  }
  else {
    for ($i = 0; $i < count(element_children($element['hierarchical_select']['selects'])); $i++) {
      form_error($element['hierarchical_select']['selects'][$i]);
    }
  }
}

/**
 * Append messages to Hierarchical Select's log. Used when in developer mode.
 *
 * @param $item
 *   Either a message (string) or an array.
 * @param $reset
 *   Reset the stored log.
 * @return
 *   Only when the log is being reset, the stored log is returned.
 */
function _hierarchical_select_log($item, $reset = FALSE) {
  static $log;
  if ($reset) {
    $copy_of_log = $log;
    $log = array();
    return $copy_of_log;
  }
  $log[] = $item;
}

//----------------------------------------------------------------------------

// Hierarchy object generation functions.

/**
 * Generate the hierarchy object.
 *
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - params
 *   - enforce_deepest
 *   - save_lineage
 *   - level_labels
 *     - status
 *     - labels
 *   - editability
 *     - status
 *     - allow_new_levels
 *     - max_levels
 * @param $selection
 *   The selection based on which a HS should be rendered.
 * @param $required
 *   Whether the form element is required or not. (#required in Forms API)
 * @param $dropbox
 *   A dropbox object, or FALSE.
 * @return
 *   A hierarchy object.
 */
function _hierarchical_select_hierarchy_generate($config, $selection, $required, $dropbox = FALSE) {
  $hierarchy = new stdClass();

  //
  // Build the lineage.
  //
  $start_lineage = microtime();

  // If save_linage is enabled, reconstruct the lineage. This is necessary
  // because e.g. the taxonomy module stores the terms by order of weight and
  // lexicography, rather than by hierarchy.
  if ($config['save_lineage'] && is_array($selection) && count($selection) >= 2) {

    // Ensure the item in the root level is the first item in the selection.
    $root_level = array_keys(module_invoke($config['module'], 'hierarchical_select_root_level', $config['params']));
    for ($i = 0; $i < count($selection); $i++) {
      if (in_array($selection[$i], $root_level)) {
        if ($i != 0) {

          // Don't swap if it's already the first item.
          list($selection[0], $selection[$i]) = array(
            $selection[$i],
            $selection[0],
          );
        }
        break;
      }
    }

    // Reconstruct all sublevels.
    for ($i = 0; $i < count($selection); $i++) {
      $children = array_keys(module_invoke($config['module'], 'hierarchical_select_children', $selection[$i], $config['params']));

      // Ensure the next item in the selection is a child of the current item.
      for ($j = $i + 1; $j < count($selection); $j++) {
        if (in_array($selection[$j], $children)) {
          list($selection[$j], $selection[$i + 1]) = array(
            $selection[$i + 1],
            $selection[$j],
          );
        }
      }
    }
  }

  // Validate the hierarchy.
  $selection = _hierarchical_select_hierarchy_validate($selection, $config['module'], $config['params']);

  // When nothing is currently selected, set the root level to:
  // - "<none>" when:
  //    - enforce_deepest is enabled *and* level labels are enabled *and*
  //      no root level label is set (1), or
  //    - the dropbox is enabled *and* at least one selection has been added
  //      to the dropbox (2)
  // - "label_0" (the root level label) in all other cases.
  if ($selection == -1) {
    $root_level = module_invoke($config['module'], 'hierarchical_select_root_level', $config['params']);
    $first_case = $config['enforce_deepest'] && $config['level_labels']['status'] && !isset($config['level_labels']['labels'][0]);
    $second_case = $dropbox && count($dropbox->lineages) > 0;
    $hierarchy->lineage[0] = $first_case || $second_case ? 'none' : 'label_0';
  }
  else {

    // If save_lineage setting is enabled, then the selection *is* a lineage.
    // If it's disabled, we have to generate one ourselves based on the
    // (deepest) selected item.
    if ($config['save_lineage']) {

      // When the form element is optional, the "<none>" setting can be
      // selected, thus only the first level will be displayed. As a result,
      // we won't receive an array as the selection, but only a single item.
      // We convert this into an array.
      $hierarchy->lineage = is_array($selection) ? $selection : array(
        0 => $selection,
      );
    }
    else {
      $selection = is_array($selection) ? $selection[0] : $selection;
      if (module_invoke($config['module'], 'hierarchical_select_valid_item', $selection, $config['params'])) {
        $hierarchy->lineage = module_invoke($config['module'], 'hierarchical_select_lineage', $selection, $config['params']);
      }
      else {

        // If the selected item is invalid, then start with an empty lineage.
        $hierarchy->lineage = array();
      }
    }
  }

  // If enforce_deepest is enabled, ensure that the lineage goes as deep as
  // possible: append values of items that will be selected by default.
  if ($config['enforce_deepest'] && !in_array($hierarchy->lineage[0], array(
    'none',
    'label_0',
  ))) {
    $hierarchy->lineage = _hierarchical_select_hierarchy_enforce_deepest($hierarchy->lineage, $config['module'], $config['params']);
  }
  $end_lineage = microtime();

  //
  // Build the levels.
  //
  $start_levels = microtime();

  // Start building the levels, initialize with the root level.
  $hierarchy->levels[0] = module_invoke($config['module'], 'hierarchical_select_root_level', $config['params']);
  $hierarchy->levels[0] = _hierarchical_select_apply_entity_settings($hierarchy->levels[0], $config);

  // Prepend a "<create new item>" option to the root level when:
  // - the editability setting is enabled, and
  // - the hook is implemented (this is an optional hook), and
  // - the allowed_levels setting allows to create new items at this level.
  if ($config['editability']['status'] && module_hook($config['module'], 'hierarchical_select_create_item') && _hierarchical_select_create_new_item_is_allowed($config, 0)) {
    $item_type = t($config['editability']['item_types'][0]);
    $item_type = !empty($item_type) ? $item_type : t('item');
    $option = theme('hierarchical_select_special_option', t('create new !item_type', array(
      '!item_type' => $item_type,
    )));
    $hierarchy->levels[0] = array(
      'create_new_item' => $option,
    ) + $hierarchy->levels[0];
  }

  // Prepend a "<none>" option to the root level when:
  // - the form element is optional (1), or
  // - enforce_deepest is enabled (2), or
  // - the dropbox is enabled *and* at least one selection has been added to
  //   the dropbox (3)
  $first_case = !$required;
  $second_case = $config['enforce_deepest'];
  $third_case = $dropbox && count($dropbox->lineages) > 0;
  if ($first_case || $second_case || $third_case) {
    $option = theme('hierarchical_select_special_option', t('none'));
    $hierarchy->levels[0] = array(
      'none' => $option,
    ) + $hierarchy->levels[0];
  }

  // Calculate the lineage's depth (starting from 0).
  $max_depth = count($hierarchy->lineage) - 1;

  // Build all sublevels, based on the lineage.
  for ($depth = 1; $depth <= $max_depth; $depth++) {
    $hierarchy->levels[$depth] = module_invoke($config['module'], 'hierarchical_select_children', $hierarchy->lineage[$depth - 1], $config['params']);
    $hierarchy->levels[$depth] = _hierarchical_select_apply_entity_settings($hierarchy->levels[$depth], $config);
  }
  if ($config['enforce_deepest']) {

    // Prepend a "<create new item>" option to each level below the root level
    // when:
    // - the editability setting is enabled, and
    // - the hook is implemented (this is an optional hook), and
    // - the allowed_levels setting allows to create new items at this level.
    if ($config['editability']['status'] && module_hook($config['module'], 'hierarchical_select_create_item')) {
      for ($depth = 1; $depth <= $max_depth; $depth++) {
        $item_type = t($config['editability']['item_types'][$depth]);
        $item_type = !empty($item_type) ? $item_type : t('item');
        $option = theme('hierarchical_select_special_option', t('create new !item_type', array(
          '!item_type' => $item_type,
        )));
        if (_hierarchical_select_create_new_item_is_allowed($config, $depth)) {
          $hierarchy->levels[$depth] = array(
            'create_new_item' => $option,
          ) + $hierarchy->levels[$depth];
        }
      }
    }

    // If level labels are enabled and the root label is set, prepend it.
    if ($config['level_labels']['status'] && isset($config['level_labels']['labels'][0])) {
      $hierarchy->levels[0] = array(
        'label_0' => t($config['level_labels']['labels'][0]),
      ) + $hierarchy->levels[0];
    }
  }
  else {
    if (!$config['enforce_deepest']) {

      // Prepend special options to every level.
      for ($depth = 0; $depth <= $max_depth; $depth++) {

        // Prepend a "<create new item>" option to the current level when:
        // - this is not the root level (the root level already has this), and
        // - the editability setting is enabled, and
        // - the hook is implemented (this is an optional hook), and
        // - the allowed_levels setting allows to create new items at this level.
        if ($depth > 0 && $config['editability']['status'] && module_hook($config['module'], 'hierarchical_select_create_item') && _hierarchical_select_create_new_item_is_allowed($config, $depth)) {
          $item_type = t($config['editability']['item_types'][$depth]);
          $item_type = !empty($item_type) ? $item_type : t('item');
          $option = theme('hierarchical_select_special_option', t('create new !item_type', array(
            '!item_type' => $item_type,
          )));
          $hierarchy->levels[$depth] = array(
            'create_new_item' => $option,
          ) + $hierarchy->levels[$depth];
        }

        // Level label: set an empty level label if they've been disabled.
        $label = $config['level_labels']['status'] && isset($config['level_labels']['labels'][$depth]) ? t($config['level_labels']['labels'][$depth]) : '';
        $hierarchy->levels[$depth] = array(
          'label_' . $depth => $label,
        ) + $hierarchy->levels[$depth];
      }

      // If the root level label is empty and the none option is present, remove
      // the root level label because it's conceptually identical.
      if ($hierarchy->levels[0]['label_0'] == '' && isset($hierarchy->levels[0]['none'])) {
        unset($hierarchy->levels[0]['label_0']);

        // Update the selected lineage when necessary to prevent an item that
        // doesn't exist from being "selected" internally.
        if ($hierarchy->lineage[0] == 'label_0') {
          $hierarchy->lineage[0] = 'none';
        }
      }

      // Add one more level if appropriate.
      $parent = $hierarchy->lineage[$max_depth];
      if (module_invoke($config['module'], 'hierarchical_select_valid_item', $parent, $config['params'])) {
        $children = module_invoke($config['module'], 'hierarchical_select_children', $parent, $config['params']);
        if (count($children)) {

          // We're good, let's add one level!
          $depth = $max_depth + 1;
          $hierarchy->levels[$depth] = array();

          // Prepend a "<create new item>" option to the current level when:
          // - the editability setting is enabled, and
          // - the hook is implemented (this is an optional hook), and
          // - the allowed_levels setting allows to create new items at this level.
          if ($config['editability']['status'] && module_hook($config['module'], 'hierarchical_select_create_item') && _hierarchical_select_create_new_item_is_allowed($config, $depth)) {
            $item_type = t($config['editability']['item_types'][$depth]);
            $item_type = !empty($item_type) ? $item_type : t('item');
            $option = theme('hierarchical_select_special_option', t('create new !item_type', array(
              '!item_type' => $item_type,
            )));
            $hierarchy->levels[$depth] = array(
              'create_new_item' => $option,
            );
          }

          // Level label: set an empty level label if they've been disabled.
          $hierarchy->lineage[$depth] = 'label_' . $depth;
          $label = $config['level_labels']['status'] ? t($config['level_labels']['labels'][$depth]) : '';
          $hierarchy->levels[$depth] = array(
            'label_' . $depth => $label,
          ) + $hierarchy->levels[$depth] + $children;
          $hierarchy->levels[$depth] = _hierarchical_select_apply_entity_settings($hierarchy->levels[$depth], $config);
        }
      }
    }
  }

  // Add an extra level with only a level label and a "<create new item>"
  // option, if:
  // - the editability setting is enabled
  // - the allow_new_levels setting is enabled
  // - an additional level is permitted by the max_levels setting
  // - the deepest item of the lineage is a valid item
  // NOTE: this uses an optional hook, so we also check if it's implemented.
  if ($config['editability']['status'] && $config['editability']['allow_new_levels'] && ($config['editability']['max_levels'] == 0 || count($hierarchy->lineage) < $config['editability']['max_levels']) && module_invoke($config['module'], 'hierarchical_select_valid_item', end($hierarchy->lineage), $config['params']) && module_hook($config['module'], 'hierarchical_select_create_item')) {
    $depth = $max_depth + 1;

    // Level label: set an empty level label if they've been disabled.
    $hierarchy->lineage[$depth] = 'label_' . $depth;
    $label = $config['level_labels']['status'] ? t($config['level_labels']['labels'][$depth]) : '';

    // Item type.
    $item_type = t($config['editability']['item_types'][$depth]);
    $item_type = !empty($item_type) ? $item_type : t('item');

    // The new level with only a level label and a "<create new item>" option.
    $option = theme('hierarchical_select_special_option', t('create new !item_type', array(
      '!item_type' => $item_type,
    )));
    $hierarchy->levels[$depth] = array(
      'label_' . $depth => $label,
      'create_new_item' => $option,
    );
  }

  // Calculate the time it took to generate the levels.
  $end_levels = microtime();

  // Add child information.
  $start_childinfo = microtime();
  $hierarchy = _hierarchical_select_hierarchy_add_childinfo($hierarchy, $config);
  $end_childinfo = microtime();

  // Calculate the time it took to build the hierarchy object.
  $hierarchy->build_time['total'] = ($end_childinfo - $start_lineage) * 1000;
  $hierarchy->build_time['lineage'] = ($end_lineage - $start_lineage) * 1000;
  $hierarchy->build_time['levels'] = ($end_levels - $start_levels) * 1000;
  $hierarchy->build_time['childinfo'] = ($end_childinfo - $start_childinfo) * 1000;
  return $hierarchy;
}

/**
 * Given a level, apply the entity_count and require_entity settings.
 *
 * @param $level
 *   A level in the hierarchy.
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - params
 *   - entity_count
 *   - require_entity
 * @return
 *   The updated level
 */
function _hierarchical_select_apply_entity_settings($level, $config) {

  // Only do something when the entity_count or the require_entity (or both)
  // settings are enabled.
  // NOTE: this uses the optional "hierarchical_selectentity_count" hook, so
  // we also check if it's implemented.
  if (($config['entity_count'] || $config['require_entity']) && module_hook($config['module'], 'hierarchical_select_entity_count')) {
    foreach ($level as $item => $label) {

      // We don't want to alter special items.
      if (!preg_match('/(none|label_\\d+|create_new_item)/', $item)) {
        $entity_count = module_invoke($config['module'], 'hierarchical_select_entity_count', $item, $config['params']);

        // When the require_entity setting is enabled and the entity count is
        // zero, then remove the item from the level.
        // When the item is not removed from the level due to the above and
        // the entity_count setting is enabled, update the label of the item
        // to include the entity count.
        if ($config['require_entity'] && $entity_count == 0) {
          unset($level[$item]);
        }
        elseif ($config['entity_count']) {
          $level[$item] = "{$label} ({$entity_count})";
        }
      }
    }
  }
  return $level;
}

/**
 * Extends a hierarchy object with child information: for each item in the
 * hierarchy, the child count will be retrieved and stored in the hierarchy
 * object, in the "childinfo" property. Items are grouped per level.
 *
 * @param $hierarchy
 *   A hierarchy object with the "levels" property set.
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - params
 * @return
 *   An updated hierarchy object with the "childinfo" property set.
 */
function _hierarchical_select_hierarchy_add_childinfo($hierarchy, $config) {
  foreach ($hierarchy->levels as $depth => $level) {
    foreach (array_keys($level) as $item) {
      if (!preg_match('/(none|label_\\d+|create_new_item)/', $item)) {
        $hierarchy->childinfo[$depth][$item] = count(module_invoke($config['module'], 'hierarchical_select_children', $item, $config['params']));
      }
    }
  }
  return $hierarchy;
}

/**
 * Reset the selection if no valid item was selected. The first item in the
 * array corresponds to the first selected term. As soon as an invalid item
 * is encountered, the lineage from that level to the deeper levels should be
 * unset. This is so to ignore selection of a level label.
 *
 * @param $selection
 *   Either a single item id or an array of item ids.
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $params
 *   The module that should be passed to HS hooks.
 * @return
 *   The updated selection.
 */
function _hierarchical_select_hierarchy_validate($selection, $module, $params) {
  $valid = TRUE;
  $selection_levels = count($selection);
  for ($i = 0; $i < $selection_levels; $i++) {

    // As soon as one invalid item has been found, we'll stop validating; all
    // subsequently selected items will be removed from the selection.
    if ($valid) {
      $valid = module_invoke($module, 'hierarchical_select_valid_item', $selection[$i], $params);
      if ($i > 0) {
        $parent = $selection[$i - 1];
        $child = $selection[$i];
        $children = array_keys(module_invoke($module, 'hierarchical_select_children', $parent, $params));
        $valid = $valid && in_array($child, $children);
      }
    }
    if (!$valid) {
      unset($selection[$i]);
    }
  }
  if (empty($selection)) {
    $selection = -1;
  }
  return $selection;
}

/**
 * Helper function to update the lineage of the hierarchy to ensure that the
 * user selects an item in the deepest level of the hierarchy.
 *
 * @param $lineage
 *   The lineage up to the deepest selection the user has made so far.
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $params
 *   The params that should be passed to HS hooks.
 * @return
 *   The updated lineage.
 */
function _hierarchical_select_hierarchy_enforce_deepest($lineage, $module, $params) {

  // Use the deepest item as the first parent. Then apply this algorithm:
  // 1) get the parent's children, stop if no children
  // 2) choose the first child as the option that is selected by default, by
  //    adding it to the lineage of the hierarchy
  // 3) make this child the parent, go to step 1.
  $parent = end($lineage);

  // The last item in the lineage is the deepest one.
  $children = module_invoke($module, 'hierarchical_select_children', $parent, $params);
  while (count($children)) {
    $first_child = reset(array_keys($children));
    $lineage[] = $first_child;
    $parent = $first_child;
    $children = module_invoke($module, 'hierarchical_select_children', $parent, $params);
  }
  return $lineage;
}

//----------------------------------------------------------------------------

// Dropbox object generation functions.

/**
 * Generate the dropbox object.
 *
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - save_lineage
 *   - params
 *   - dropbox
 *     - title
 * @param $selection
 *   The selection based on which a dropbox should be generated.
 * @return
 *   A dropbox object.
 */
function _hierarchical_select_dropbox_generate($config, $selection) {
  $dropbox = new stdClass();
  $start = microtime();
  $dropbox->title = !empty($config['dropbox']['title']) ? $config['dropbox']['title'] : t('All selections');
  $dropbox->lineages = array();
  $dropbox->lineages_selections = array();

  // Clean selection.
  foreach ($selection as $key => $item) {
    if (!module_invoke($config['module'], 'hierarchical_select_valid_item', $item, $config['params'])) {
      unset($selection[$key]);
    }
  }
  if (!empty($selection)) {

    // Store the "save lineage" setting, needed in the rendering layer.
    $dropbox->save_lineage = $config['save_lineage'];
    if ($config['save_lineage']) {
      $dropbox->lineages = _hierarchical_select_dropbox_reconstruct_lineages_save_lineage_enabled($config['module'], $selection, $config['params']);
    }
    else {

      // Retrieve the lineage of each item.
      foreach ($selection as $item) {
        $dropbox->lineages[] = module_invoke($config['module'], 'hierarchical_select_lineage', $item, $config['params']);
      }

      // We will also need the labels of each item in the rendering layer.
      foreach ($dropbox->lineages as $id => $lineage) {
        foreach ($lineage as $level => $item) {
          $dropbox->lineages[$id][$level] = array(
            'value' => $item,
            'label' => check_plain(module_invoke($config['module'], 'hierarchical_select_item_get_label', $item, $config['params'])),
          );
        }
      }
    }
    usort($dropbox->lineages, '_hierarchical_select_dropbox_sort');

    // Now store each lineage's selection too. This is needed on the client side
    // to enable the remove button to let the server know which selected items
    // should be removed.
    foreach ($dropbox->lineages as $id => $lineage) {
      if ($config['save_lineage']) {

        // Store the entire lineage.
        $dropbox->lineages_selections[$id] = array_map('_hierarchical_select_dropbox_lineage_item_get_value', $lineage);
      }
      else {

        // Store only the last (aka the deepest) value of the lineage.
        $dropbox->lineages_selections[$id][0] = $lineage[count($lineage) - 1]['value'];
      }
    }
  }

  // Calculate the time it took to build the dropbox object.
  $dropbox->build_time = (microtime() - $start) * 1000;
  return $dropbox;
}

/**
 * Helper function to reconstruct the lineages given a set of selected items
 * and the fact that the "save lineage" setting is enabled.
 *
 * Note that it's impossible to predict how many lineages if we know the
 * number of selected items, exactly because the "save lineage" setting is
 * enabled.
 *
 * Worst case time complexity is O(n^3), optimizations are still possible.
 *
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $selection
 *   The selection based on which a dropbox should be generated.
 * @param $params
 *   Optional. An array of parameters, which may be necessary for some
 *   implementations.
 * @return
 *   An array of dropbox lineages.
 */
function _hierarchical_select_dropbox_reconstruct_lineages_save_lineage_enabled($module, $selection, $params) {

  // We have to reconstruct all lineages from the given set of selected items.
  // That means: we have to reconstruct every possible combination!
  $lineages = array();
  $root_level = module_invoke($module, 'hierarchical_select_root_level', $params);
  foreach ($selection as $key => $item) {

    // Create new lineage if the item can be found in the root level.
    if (array_key_exists($item, $root_level)) {
      $lineages[][0] = array(
        'value' => $item,
        'label' => $root_level[$item],
      );
      unset($selection[$key]);
    }
  }

  // Keep on trying as long as at least one lineage has been extended.
  $at_least_one = TRUE;
  for ($i = 0; $at_least_one; $i++) {
    $at_least_one = FALSE;
    $num = count($lineages);

    // Try to improve every lineage. Make sure we don't iterate over
    // possibly new lineages.
    for ($id = 0; $id < $num; $id++) {
      $children = module_invoke($module, 'hierarchical_select_children', $lineages[$id][$i]['value'], $params);
      $child_added_to_lineage = FALSE;
      foreach (array_keys($children) as $child) {
        if (in_array($child, $selection)) {
          if (!$child_added_to_lineage) {

            // Add the child to the lineage.
            $lineages[$id][$i + 1] = array(
              'value' => $child,
              'label' => $children[$child],
            );
            $child_added_to_lineage = TRUE;
            $at_least_one = TRUE;
          }
          else {

            // Create new lineage based on current one and add the child.
            $lineage = $lineages[$id];
            $lineage[$i + 1] = array(
              'value' => $child,
              'label' => $children[$child],
            );

            // Add the new lineage to the set of lineages
            $lineages[] = $lineage;
          }
        }
      }
    }
  }
  return $lineages;
}

/**
 * Dropbox lineages sorting callback.
 *
 * @param $lineage_a
 *   The first lineage.
 * @param $lineage_b
 *   The second lineage.
 * @return
 *   An integer that determines which of the two lineages comes first.
 */
function _hierarchical_select_dropbox_sort($lineage_a, $lineage_b) {
  $string_a = implode('', array_map('_hierarchical_select_dropbox_lineage_item_get_label', $lineage_a));
  $string_b = implode('', array_map('_hierarchical_select_dropbox_lineage_item_get_label', $lineage_b));
  return strcmp($string_a, $string_b);
}

/**
 * Helper function needed for the array_map() call in the dropbox sorting
 * callback.
 *
 * @param $item
 *   An item in a dropbox lineage.
 * @return
 *   The value associated with the "label" key of the item.
 */
function _hierarchical_select_dropbox_lineage_item_get_label($item) {
  return t($item['label']);
}

/**
 * Helper function needed for the array_map() call in the dropbox lineages
 * selections creation.
 *
 * @param $item
 *   An item in a dropbox lineage.
 * @return
 *   The value associated with the "value" key of the item.
 */
function _hierarchical_select_dropbox_lineage_item_get_value($item) {
  return $item['value'];
}

/**
 * This is an altered clone of form_select_options(). The reason: I need to be
 * able to set a class on an option element if it contains a level label, to
 * allow for level label styles.
 * Secondly, I need to be able to mark childless items (i.e. "option"
 * elements).
 */
function _hierarchical_select_options($element) {
  if (!isset($choices)) {
    $choices = $element['#options'];
  }

  // array_key_exists() accommodates the rare event where $element['#value'] is NULL.
  // isset() fails in this situation.
  $value_valid = isset($element['#value']) || array_key_exists('#value', $element);
  $value_is_array = is_array($element['#value']);
  $options = '';
  foreach ($choices as $key => $choice) {
    $key = (string) $key;
    if ($value_valid && (!$value_is_array && (string) $element['#value'] === $key || $value_is_array && in_array($key, $element['#value']))) {
      $selected = ' selected="selected"';
    }
    else {
      $selected = '';
    }

    // If an option DOES NOT have child info, then it's a special option:
    // - label_\d+ (level label)
    // - none ("<none>")
    // - create_new_item ("<create new item>")
    // Only when it's a level label, we have to add a class to this option.
    if (!isset($element['#childinfo'][$key])) {
      $class = preg_match('/label_\\d+/', $key) ? ' level-label' : '';
    }
    else {
      $class = $element['#childinfo'][$key] == 0 ? 'has-no-children' : 'has-children';
    }
    $options .= '<option value="' . check_plain($key) . '" class="' . $class . '"' . $selected . '>' . check_plain($choice) . '</option>';
  }
  return $options;
}

/**
 * Get the HS form build ID.
 *
 * Instead of just looking at $_POST['hs_form_build_id'], where it will be 99%
 * of the time, this function also looks for 'hs_form_build_id' in each second
 * level of the array, to support subforms. E.g. the nodeprofile module
 * requires this.
 */
function _hierarchical_select_get_hs_form_build_id() {
  $hs_form_build_id = $_POST['hs_form_build_id'];
  if (empty($hs_form_build_id)) {
    foreach ($_POST as $key => $value) {
      if (is_array($_POST[$key]) && !empty($_POST[$key]['hs_form_build_id'])) {
        return $_POST[$key]['hs_form_build_id'];
      }
    }
  }
  return $hs_form_build_id;
}

/**
 * Smarter version of array_merge_recursive: overwrites scalar values.
 *
 * From: http://www.php.net/manual/en/function.array-merge-recursive.php#82976.
 */
if (!function_exists('array_smart_merge')) {
  function array_smart_merge($array, $override) {
    if (is_array($array) && is_array($override)) {
      foreach ($override as $k => $v) {
        if (isset($array[$k]) && is_array($v) && is_array($array[$k])) {
          $array[$k] = array_smart_merge($array[$k], $v);
        }
        else {
          $array[$k] = $v;
        }
      }
    }
    return $array;
  }
}

//----------------------------------------------------------------------------

// Theming callbacks.

/**
 * @ingroup themeable
 * @{
 */

/**
 * Format a hierarchical select.
 *
 * @param $element
 *   An associative array containing the properties of the element.
 * @return
 *   A themed HTML string representing the form element.
 */
function theme_hierarchical_select($element) {
  $output = '';

  // Update $element['#attributes']['class'].
  $hsid = $element['hsid']['#value'];
  $level_labels_style = variable_get('hierarchical_select_level_labels_style', 'none');
  $classes = array(
    'hierarchical-select-wrapper',
    "hierarchical-select-level-labels-style-{$level_labels_style}",
    // Classes that make it possible to override the styling of specific
    // instances of Hierarchical Select, based on either the ID of the form
    // element or the config that it uses.
    'hierarchical-select-wrapper-for-name-' . $element['#id'],
    isset($element['#config']['config_id']) ? 'hierarchical-select-wrapper-for-config-' . $element['#config']['config_id'] : NULL,
  );
  $element['#attributes']['class'] .= ' ' . implode(' ', $classes);
  $element['#attributes']['id'] = "hierarchical-select-{$hsid}-wrapper";
  $element['#id'] = "hierarchical-select-{$hsid}-wrapper";

  // This ensures the label's for attribute is correct.
  $output .= theme('form_element', array(
    '#title' => $element['#title'],
    '#description' => $element['#description'],
    '#id' => $element['#id'],
    '#required' => $element['#required'],
    '#error' => $element['#error'],
  ), '<div ' . drupal_attributes($element['#attributes']) . '>' . $element['#children'] . '</div>');
  return $output;
}

/**
 * Format the container for all selects in the hierarchical select.
 *
 * @param $element
 *   An associative array containing the properties of the element.
 * @return
 *   A themed HTML string representing the form element.
 */
function theme_hierarchical_select_selects_container($element) {
  $output = '';
  $output .= '<div class="hierarchical-select clear-block">';
  $output .= drupal_render($element);
  $output .= '</div>';
  return $output;
}

/**
 * Format a select in the .hierarchial-select div: prevent it from being
 * wrapped in a div. This simplifies the CSS and JS code.
 *
 * @param $element
 *   An associative array containing the properties of the element.
 * @return
 *   A themed HTML string representing the form element.
 */
function theme_hierarchical_select_select($element) {
  $select = '';
  $size = $element['#size'] ? ' size="' . $element['#size'] . '"' : '';
  $class = array(
    'form-select',
  );
  if (form_get_error($element) === '') {
    $class = array_merge($class, array(
      'error',
    ));
  }
  _form_set_class($element, $class);
  $multiple = isset($element['#multiple']) && $element['#multiple'];
  return '<select name="' . $element['#name'] . '' . ($multiple ? '[]' : '') . '"' . ($multiple ? ' multiple="multiple" ' : '') . drupal_attributes($element['#attributes']) . ' id="' . $element['#id'] . '" ' . $size . '>' . _hierarchical_select_options($element) . '</select>';
}

/**
 * Format a special option in a Hierarchical Select select. For example the
 * "none" option or the "create new item" option. This theme function allows
 * you to change how a special option is indicated textually.
 *
 * @param $option
 *   A special option.
 * @return
 *   A textually indicated special option.
 */
function theme_hierarchical_select_special_option($option) {
  return '<' . $option . '>';
}

/**
 * Format a textfield in the .hierarchial-select div: prevent it from being
 * wrapped in a div. This simplifies the CSS and JS code.
 *
 * @param $element
 *   An associative array containing the properties of the element.
 * @return
 *   A themed HTML string representing the form element.
 */
function theme_hierarchical_select_textfield($element) {
  $size = $element['#size'] ? ' size="' . $element['#size'] . '"' : '';
  $class = array(
    'form-text',
  );
  $extra = '';
  $output = '';
  if ($element['#autocomplete_path']) {
    drupal_add_js('misc/autocomplete.js');
    $class[] = 'form-autocomplete';
    $extra = '<input class="autocomplete" type="hidden" id="' . $element['#id'] . '-autocomplete" value="' . check_url(url($element['#autocomplete_path'], NULL, NULL, TRUE)) . '" disabled="disabled" />';
  }
  _form_set_class($element, $class);
  if (isset($element['#field_prefix'])) {
    $output .= '<span class="field-prefix">' . $element['#field_prefix'] . '</span> ';
  }
  $output .= '<input type="text" maxlength="' . $element['#maxlength'] . '" name="' . $element['#name'] . '" id="' . $element['#id'] . '" ' . $size . ' value="' . check_plain($element['#value']) . '"' . drupal_attributes($element['#attributes']) . ' />';
  if (isset($element['#field_suffix'])) {
    $output .= ' <span class="field-suffix">' . $element['#field_suffix'] . '</span>';
  }
  return $output . $extra;
}

/**
 * Forms API theming callback for the dropbox. Renders the dropbox as a table.
 *
 * @param $element
 *   An element for which the #theme property was set to this function.
 * @return
 *   A themed HTML string.
 */
function theme_hierarchical_select_dropbox_table($element) {
  $output = '';
  $class = 'dropbox';
  if (form_get_error($element) === '') {
    $class .= ' error';
  }
  $title = $element['title']['#value'];
  $separator = $element['separator']['#value'];
  $is_empty = $element['is_empty']['#value'];
  $separator_html = '<span class="hierarchical-select-item-separator">' . $separator . '</span>';
  $output .= '<div class="' . $class . '">';
  $output .= '<table>';
  $output .= '<caption class="dropbox-title">' . $title . '</caption>';
  $output .= '<tbody>';
  if (!$is_empty) {

    // Each lineage in the dropbox corresponds to an entry in the dropbox table.
    $lineage_count = count(element_children($element['lineages']));
    for ($x = 0; $x < $lineage_count; $x++) {
      $db_entry = $element['lineages'][$x];
      $zebra = $db_entry['#zebra'];
      $first = $db_entry['#first'];
      $last = $db_entry['#last'];

      // The deepest level is the number of child levels minus one. This "one"
      // is the element for the "Remove" checkbox.
      $deepest_level = count(element_children($db_entry)) - 1;
      $output .= '<tr class="dropbox-entry ' . $first . ' ' . $last . ' ' . $zebra . '">';
      $output .= '<td>';

      // Each item in a lineage is separated by the separator string.
      for ($depth = 0; $depth < $deepest_level; $depth++) {
        $output .= drupal_render($db_entry[$depth]);
        if ($depth < $deepest_level - 1) {
          $output .= $separator_html;
        }
      }
      $output .= '</td>';
      $output .= '<td class="dropbox-remove">' . drupal_render($db_entry['remove']) . '</td>';
      $output .= '</tr>';
    }
  }
  else {
    $output .= '<tr class="dropbox-entry first last dropbox-is-empty"><td>';
    $output .= t('Nothing has been selected.');
    $output .= '</td></tr>';
  }
  $output .= '</tbody>';
  $output .= '</table>';
  $output .= '</div>';
  return $output;
}

/**
 * Themeing function to render a selection (of items) according to a given
 * Hierarchical Select configuration as one or more lineages.
 *
 * @param $selection
 *   A selection of items of a hierarchy.
 * @param $config
 *   A config array with at least the following settings:
 *   - module
 *   - save_lineage
 *   - params
 */
function theme_hierarchical_select_selection_as_lineages($selection, $config) {
  $output = '';
  $selection = !is_array($selection) ? array(
    $selection,
  ) : $selection;

  // Generate a dropbox out of the selection. This will automatically
  // calculate all lineages for us.
  $selection = array_keys($selection);
  $dropbox = _hierarchical_select_dropbox_generate($config, $selection);

  // Actual formatting.
  foreach ($dropbox->lineages as $id => $lineage) {
    if ($id > 0) {
      $output .= '<br />';
    }
    $items = array();
    foreach ($lineage as $level => $item) {
      $items[] = $item['label'];
    }
    $output .= implode('<span class="hierarchical-select-item-separator">›</span>', $items);
  }

  // Add the CSS.
  drupal_add_css(drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select.css');
  return $output;
}

/**
 * @} End of "ingroup themeable".
 */

Functions

Name	Description
hierarchical_select_after_build	Hierarchical select form element type #after_build callback.
hierarchical_select_elements	Implementation of hook_elements().
hierarchical_select_form_alter	Implementation of hook_form_alter().
hierarchical_select_json	Menu callback; format=text/json; generates and outputs the appropriate HTML.
hierarchical_select_menu	Implementation of hook_menu().
hierarchical_select_process	Hierarchical select form element type #process callback.
hierarchical_select_requirements	Implementation of hook_requirements().
theme_hierarchical_select	Format a hierarchical select.
theme_hierarchical_select_dropbox_table	Forms API theming callback for the dropbox. Renders the dropbox as a table.
theme_hierarchical_select_select	Format a select in the .hierarchial-select div: prevent it from being wrapped in a div. This simplifies the CSS and JS code.
theme_hierarchical_select_selection_as_lineages	Themeing function to render a selection (of items) according to a given Hierarchical Select configuration as one or more lineages.
theme_hierarchical_select_selects_container	Format the container for all selects in the hierarchical select.
theme_hierarchical_select_special_option	Format a special option in a Hierarchical Select select. For example the "none" option or the "create new item" option. This theme function allows you to change how a special option is indicated textually.
theme_hierarchical_select_textfield	Format a textfield in the .hierarchial-select div: prevent it from being wrapped in a div. This simplifies the CSS and JS code.
_hierarchical_select_apply_entity_settings	Given a level, apply the entity_count and require_entity settings.
_hierarchical_select_create_new_item_is_allowed	Helper function to determine whether a given depth (i.e. the depth of a level) is allowed by the allowed_levels setting.
_hierarchical_select_dropbox_generate	Generate the dropbox object.
_hierarchical_select_dropbox_lineage_item_get_label	Helper function needed for the array_map() call in the dropbox sorting callback.
_hierarchical_select_dropbox_lineage_item_get_value	Helper function needed for the array_map() call in the dropbox lineages selections creation.
_hierarchical_select_dropbox_reconstruct_lineages_save_lineage_enabled	Helper function to reconstruct the lineages given a set of selected items and the fact that the "save lineage" setting is enabled.
_hierarchical_select_dropbox_sort	Dropbox lineages sorting callback.
_hierarchical_select_form_has_hierarchical_select	Detect whether a form has at least one hierarchical_select form element.
_hierarchical_select_form_set_error_class	Set the 'error' class on the appropriate part of Hierarchical Select, depending on its configuration.
_hierarchical_select_get_form_item	Get the form item that has the the given #name property.
_hierarchical_select_get_hs_form_build_id	Get the HS form build ID.
_hierarchical_select_hierarchy_add_childinfo	Extends a hierarchy object with child information: for each item in the hierarchy, the child count will be retrieved and stored in the hierarchy object, in the "childinfo" property. Items are grouped per level.
_hierarchical_select_hierarchy_enforce_deepest	Helper function to update the lineage of the hierarchy to ensure that the user selects an item in the deepest level of the hierarchy.
_hierarchical_select_hierarchy_generate	Generate the hierarchy object.
_hierarchical_select_hierarchy_validate	Reset the selection if no valid item was selected. The first item in the array corresponds to the first selected term. As soon as an invalid item is encountered, the lineage from that level to the deeper levels should be unset. This is so to ignore…
_hierarchical_select_inherit_default_config	Inherit the default config from Hierarchical Selects' hook_elements().
_hierarchical_select_json_convert_hierarchy_to_cache	Convert a hierarchy object into an array of arrays that can be used for caching an entire hierarchy in a client-side database.
_hierarchical_select_log	Append messages to Hierarchical Select's log. Used when in developer mode.
_hierarchical_select_mark_as_disabled	Helper function that marks every element in the given element as disabled.
_hierarchical_select_nojs_helptext	Helper function that generates the help text is that is displayed to the user when Javascript is disabled.
_hierarchical_select_options	This is an altered clone of form_select_options(). The reason: I need to be able to set a class on an option element if it contains a level label, to allow for level label styles. Secondly, I need to be able to mark childless items (i.e.…
_hierarchical_select_process_calculate_return_value	Calculate the return value of a hierarchical_select form element, based on the $hierarchy and $dropbox objects. We have to set a return value, because the values set and used by this form element ($element['#value]) are not easily usable in the…
_hierarchical_select_process_calculate_selections	Calculates the flat selections of both the hierarchical select and the dropbox.
_hierarchical_select_process_get_db_selection	Get the current (flat) selection of the dropbox.
_hierarchical_select_process_get_hs_selection	Get the current (flat) selection of the hierarchical select.
_hierarchical_select_process_render_db_hidden	Render the hidden part of the dropbox. This part stores the lineages of all selections in the dropbox.
_hierarchical_select_process_render_db_visible	Render the visible part of the dropbox.
_hierarchical_select_process_render_flat_select	Render a flat select version of a hierarchical_select form element. This is necessary for backwards compatibility (together with some Javascript code) in case of GET forms.
_hierarchical_select_process_render_hs_selects	Render the selects in the hierarchical select.
_hierarchical_select_setup_js	Helper function to add the required Javascript files and settings.
_hierarchical_select_store_name	Store the #name property of the given form item, so we can retrieve a list of #name properties of hierarchical_select form items present in this form later.
_hierarchical_select_submit	Hierarchical select form element #submit callback.
_hierarchical_select_validate	Hierarchical select form element #validate callback.

Constants

Name	Description
HS_DEVELOPER_MODE