hierarchical_select.module in Hierarchical Select 6.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);

// 6 hours cache life time for forms should be plenty.
define('HS_CACHE_LIFETIME_DEFAULT', 21600);

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

// Drupal core hooks.

/**
 * Implementation of hook_menu().
 */
function hierarchical_select_menu() {
  $items['hierarchical_select_json'] = array(
    'page 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 callback' => TRUE,
  );
  $items['admin/settings/hierarchical_select'] = array(
    'title' => 'Hierarchical Select',
    'description' => 'Configure site-wide settings for the Hierarchical Select form element.',
    'access arguments' => array(
      'administer site configuration',
    ),
    'page callback' => 'drupal_get_form',
    'page arguments' => array(
      'hierarchical_select_admin_settings',
    ),
    'type' => MENU_NORMAL_ITEM,
    'file' => 'hierarchical_select.admin.inc',
  );
  $items['admin/settings/hierarchical_select/settings'] = array(
    'title' => 'Site-wide settings',
    'access arguments' => array(
      'administer site configuration',
    ),
    'weight' => -10,
    'type' => MENU_DEFAULT_LOCAL_TASK,
    'file' => 'hierarchical_select.admin.inc',
  );
  $items['admin/settings/hierarchical_select/configs'] = array(
    'title' => 'Configurations',
    'description' => 'All available Hierarchical Select configurations.',
    'access arguments' => array(
      'administer site configuration',
    ),
    'page callback' => 'hierarchical_select_admin_configs',
    'type' => MENU_LOCAL_TASK,
    'file' => 'hierarchical_select.admin.inc',
  );
  $items['admin/settings/hierarchical_select/implementations'] = array(
    'title' => 'Implementations',
    'description' => 'Features of each Hierarchical Select implementation.',
    'access arguments' => array(
      'administer site configuration',
    ),
    'page callback' => 'hierarchical_select_admin_implementations',
    'type' => MENU_LOCAL_TASK,
    'file' => 'hierarchical_select.admin.inc',
  );
  $items['admin/settings/hierarchical_select/export/%hierarchical_select_config_id'] = array(
    'title' => 'Export',
    'access arguments' => array(
      'administer site configuration',
    ),
    'page callback' => 'drupal_get_form',
    'page arguments' => array(
      'hierarchical_select_admin_export',
      4,
    ),
    'type' => MENU_LOCAL_TASK,
    'file' => 'hierarchical_select.admin.inc',
  );
  $items['admin/settings/hierarchical_select/import/%hierarchical_select_config_id'] = array(
    'title' => 'Import',
    'access arguments' => array(
      'administer site configuration',
    ),
    'page callback' => 'drupal_get_form',
    'page arguments' => array(
      'hierarchical_select_admin_import',
      4,
    ),
    'type' => MENU_LOCAL_TASK,
    'file' => 'hierarchical_select.admin.inc',
  );
  return $items;
}

/**
 * Implementation of hook_flush_caches().
 */
function hierarchical_select_flush_caches() {
  return array(
    'cache_hierarchical_select',
  );
}

/**
 * Implementation of hook_form_alter().
 */
function hierarchical_select_form_alter(&$form, $form_state, $form_id) {
  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',
    ),
    '#config' => array(
      'module' => 'some_module',
      'params' => array(),
      'save_lineage' => 0,
      'enforce_deepest' => 0,
      'entity_count' => 0,
      'require_entity' => 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),
      'special_items' => array(),
      'render_flat_select' => 0,
      'path' => 'hierarchical_select_json',
    ),
    '#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;
    $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 = drupal_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 = drupal_parse_info_file(dirname($filename) . "/{$module}.info");
        $weight_errors[] = t('!module (!weight)', array(
          '!module' => $module_info['name'],
          '!weight' => $weight,
        ));
      }
    }
    if ($up_to_date && !count($path_errors) && !count($weight_errors)) {
      $value = t('All updates installed. Implementation modules are installed correctly.');
      $description = '';
      $severity = REQUIREMENT_OK;
    }
    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;
    }
    else {
      $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;
    }
    $requirements['hierarchical_select'] = array(
      'title' => t('Hierarchical Select'),
      'value' => $value,
      'description' => $description,
      'severity' => $severity,
    );
  }
  return $requirements;
}

/**
 * Implementation of hook_theme().
 */
function hierarchical_select_theme() {
  return array(
    'hierarchical_select_form_element' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'element' => NULL,
        'value' => NULL,
      ),
    ),
    'hierarchical_select' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'element' => NULL,
      ),
    ),
    'hierarchical_select_selects_container' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'element' => NULL,
      ),
    ),
    'hierarchical_select_select' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'element' => NULL,
      ),
    ),
    'hierarchical_select_special_option' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'option' => NULL,
      ),
    ),
    'hierarchical_select_textfield' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'element' => NULL,
      ),
    ),
    'hierarchical_select_dropbox_table' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'element' => NULL,
      ),
    ),
    'hierarchical_select_common_config_form_level_labels' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'form' => NULL,
      ),
    ),
    'hierarchical_select_common_config_form_editability' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'form' => NULL,
      ),
    ),
    'hierarchical_select_selection_as_lineages' => array(
      'file' => 'includes/theme.inc',
      'arguments' => array(
        'selection' => NULL,
        'config' => NULL,
      ),
    ),
  );
}

/**
 * Implementation of hook_simpletest().
 */
function hierarchical_select_simpletest() {
  $dir = drupal_get_path('module', 'hierarchical_select') . '/tests';
  $tests = file_scan_directory($dir, '\\.test$');
  return array_keys($tests);
}

/**
 * Implementation of hook_features_api().
 */
function hierarchical_select_features_api() {
  return array(
    'hierarchical_select' => array(
      'name' => t('Hierarchical select configs'),
      'feature_source' => TRUE,
      'default_hook' => 'hierarchical_select_default_configs',
      'default_file' => FEATURES_DEFAULTS_INCLUDED,
      'file' => drupal_get_path('module', 'hierarchical_select') . '/hierarchical_select.features.inc',
    ),
  );
}

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

// Menu system callbacks.

/**
 * Wildcard loader for Hierarchical Select config ID's.
 */
function hierarchical_select_config_id_load($config_id) {
  $config = variable_get('hs_config_' . $config_id, FALSE);
  return $config !== FALSE ? $config['config_id'] : FALSE;
}

/**
 * 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'];

  // In this context, we're in a node selection mode.
  // See http://drupal.org/node/683574#comment-3117926.
  if (module_exists('i18n') && isset($_POST['language'])) {
    i18n_selection_mode('node', $_POST['language']);
  }

  // Collect all necessary variables.
  $cached = cache_get($hs_form_build_id, 'cache_hierarchical_select');
  $storage = $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];
  if (HS_DEVELOPER_MODE) {
    _hierarchical_select_log("form_id: {$form_id}");
    _hierarchical_select_log("hs_form_build_id: {$hs_form_build_id}");
  }
  $form_state =& $storage['parameters'][1];

  // Include the file in which the form definition function lives.
  if (!empty($storage['file'])) {
    require_once $storage['file'];
  }

  // Also include files set in $form_state['form_load_files']. Set by CTools
  // Delegator, which is used by Panels (i.e. this is necessary for Panels
  // compatibility).
  if (isset($form_state['form_load_files'])) {
    foreach ($form_state['form_load_files'] as $file) {
      require_once './' . $file;
    }
  }

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

  // 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 (isset($_POST['client_supports_caching'])) {
    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' => isset($part_of_form['log']['#value']) ? $part_of_form['log']['#value'] : NULL,
  ));
  exit;
}

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

// Forms API callbacks.

/**
 * Hierarchical select form element type #process callback.
 */
function hierarchical_select_process($element, $edit, &$form_state, $form) {
  if (!is_array($element['#value']) || !isset($element['#value']['hsid'])) {
    $hsid = uniqid();
  }
  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);

  // Get the config and convert the 'special_items' setting to a more easily
  // accessible format.
  $config = $element['#config'];
  if (isset($config['special_items'])) {
    $special_items['exclusive'] = array_keys(array_filter($config['special_items'], '_hierarchical_select_special_item_exclusive'));
    $special_items['none'] = array_keys(array_filter($config['special_items'], '_hierarchical_select_special_item_none'));
  }

  // Set up Javascript and add settings specifically for the current
  // hierarchical select.
  $config = _hierarchical_select_inherit_default_config($element['#config']);
  _hierarchical_select_setup_js();
  _hierarchical_select_setup_js($form_state);
  $settings = 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,
          'path' => $config['path'],
        ),
      ),
    ),
  );
  _hierarchical_select_add_js_settings($settings, $form_state);

  // 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 special_items setting has been configured
  // - at least one special item has the 'exclusive' property
  // - the dropbox is enabled
  // then do the necessary processing to make exclusive lineages possible.
  if (isset($special_items) && count($special_items['exclusive']) && $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).
    $exclusive_item = array_intersect($selection, $special_items['exclusive']);
    if (count($exclusive_item)) {

      // 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']);

      // Set the hierarchical select to the exclusive item and make the
      // dropbox empty.
      $hs_selection = array(
        0 => reset($exclusive_item),
      );
      $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'] = isset($element['#size']) ? $element['#size'] : 0;
  }

  // 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 = count($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.
  if (isset($element['#post'])) {
    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.
  // Also make sure it is the *first* validate callback.
  $element['#element_validate'] = isset($element['#element_validate']) ? $element['#element_validate'] : array();
  $element['#element_validate'] = array_merge(array(
    '_hierarchical_select_validate',
  ), $element['#element_validate']);
  if (HS_DEVELOPER_MODE) {
    $element['log'] = array(
      '#type' => 'value',
      '#value' => _hierarchical_select_log(NULL, TRUE),
    );
    $settings = array(
      'HierarchicalSelect' => array(
        'initialLog' => array(
          $hsid => $element['log']['#value'],
        ),
      ),
    );
    _hierarchical_select_add_js_settings($settings, $form_state);
  }

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

  // Remove #options in case it's been added.
  if (isset($element['#options'])) {
    unset($element['#options']);
  }
  return $element;
}

/**
 * Hierarchical select form element type #after_build callback.
 */
function hierarchical_select_after_build($form, &$form_state) {

  // TRICKY: Pageroute compatibility: avoid that the body of this #after_build
  // callback is executed twice.
  if (isset($form['hs_form_build_id'])) {
    return $form;
  }
  $names = _hierarchical_select_store_name(NULL, NULL, TRUE);
  if (!isset($_POST['hs_form_build_id']) && count($names)) {
    $parameters = isset($form['#parameters']) ? $form['#parameters'] : array();
    $menu_item = menu_get_item();

    // 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,
      // … include the file in which the form function lives.
      'file' => $menu_item['file'],
    );

    // 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());
    $lifetime = variable_get('hierarchical_select_cache_lifetime', HS_CACHE_LIFETIME_DEFAULT);
    cache_set($hs_form_build_id, $storage, 'cache_hierarchical_select', time() + $lifetime);
  }
  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, $form_state);
  return $form;
}

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

  // 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: #element_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 (isset($element['#disabled']) && $element['#disabled']) {
    $element['#return_value'] = $element['#default_value'];
  }
  $element['#value'] = $element['#return_value'];
  form_set_value($element, $element['#value'], $form_state);

  // 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'] && (!count($element['#value']) || is_string($element['#value']) && strlen(trim($element['#value'])) == 0)) {
    form_error($element, t('!name field is required.', array(
      '!name' => $element['#title'],
    )));
    _hierarchical_select_form_set_error_class($element);
  }
}

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

// 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 (!empty($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 (!empty($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'];

  // When:
  // - no data was POSTed
  // - or #value is set directly and not by a Hierarchical Select POST (and
  //   therefor set either manually or by another module),
  // then use the value of #default_value, or when available, of #value.
  if (!isset($element['#post']) || !isset($element['#value']['hierarchical_select']) && !isset($element['#value']['dropbox'])) {
    $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 {
    $op = isset($element['#post']['op']) ? $element['#post']['op'] : NULL;
    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 = isset($element['#value']['hierarchical_select']['selects']) ? $element['#value']['hierarchical_select']['selects'] : array();
        $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,
      // 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' => isset($hierarchy->childinfo[$depth]) ? $hierarchy->childinfo[$depth] : NULL,
    );
  }
  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,
    '#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.
 *
 * @param $form_state
 *   A form state array. Necessary to set the callback URL for Hierarchical
 *   Select through _hierarchical_select_add_js_settings().
 */
function _hierarchical_select_setup_js(&$form_state = NULL) {
  global $language;
  static $ran_once;
  static $js_settings_added;
  $jquery_ui_components = array(
    'effects.core',
    'effects.drop',
  );
  if (!$js_settings_added && isset($form_state)) {
    $url = base_path();
    $url .= variable_get('clean_url', 0) ? '' : 'index.php?q=';

    // Prefix URL with language path when i18n is enabled and when path-based
    // negotiation is being used.
    $negotiation = variable_get('language_negotiation', LANGUAGE_NEGOTIATION_NONE);
    if (module_exists('i18n') && $language->prefix != '' && ($negotiation == LANGUAGE_NEGOTIATION_PATH_DEFAULT || $negotiation == LANGUAGE_NEGOTIATION_PATH)) {
      $url .= $language->prefix . '/';
    }
    if (module_exists('purl')) {
      $options = array();
      purl_url_outbound_alter($url, $options, '');
      $url = str_replace('//', '/', '/' . $url);
    }
    _hierarchical_select_add_js_settings(array(
      'HierarchicalSelect' => array(
        'basePath' => $url,
        'getArguments' => drupal_query_string_encode($_GET, array(
          'q',
        )),
      ),
    ), $form_state);
    $js_settings_added = TRUE;
  }
  if (!$ran_once) {
    $ran_once = TRUE;

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

/**
 * 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 (isset($form['#type']) && $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();

  // Convert the 'special_items' setting to a more easily accessible format.
  if (isset($config['special_items'])) {
    $special_items['exclusive'] = array_keys(array_filter($config['special_items'], '_hierarchical_select_special_item_exclusive'));
    $special_items['none'] = array_keys(array_filter($config['special_items'], '_hierarchical_select_special_item_none'));
  }

  //
  // 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>" (or its equivalent special item) 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;

    // If
    // - the special_items setting has been configured, and
    // - one special item has the 'none' property
    // then we'll use the special item instead of the normal "<none>" option.
    $none_option = count($special_items['none']) ? $special_items['none'][0] : 'none';

    // Set "<none>" option (or its equivalent special item), or "label_0".
    $hierarchy->lineage[0] = $first_case || $second_case ? $none_option : '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 = count($config['editability']['item_types']) > 0 ? t($config['editability']['item_types'][0]) : 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)
  // except when:
  // - the special_items setting has been configured, and
  // - one special item has the 'none' property
  $first_case = !$required;
  $second_case = $config['enforce_deepest'];
  $third_case = $dropbox && count($dropbox->lineages) > 0;
  if (($first_case || $second_case || $third_case) && !count($special_items['none'])) {
    $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 = count($config['editability']['item_types']) == $depth ? t($config['editability']['item_types'][$depth]) : 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 = count($config['editability']['item_types']) == $depth ? t($config['editability']['item_types'][$depth]) : 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 = count($config['editability']['item_types']) == $depth ? t($config['editability']['item_types'][$depth]) : 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 = count($config['editability']['item_types']) == $depth ? t($config['editability']['item_types'][$depth]) : 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) {
  if (isset($config['special_items'])) {
    $special_items['exclusive'] = array_keys(array_filter($config['special_items'], '_hierarchical_select_special_item_exclusive'));
    $special_items['none'] = array_keys(array_filter($config['special_items'], '_hierarchical_select_special_item_none'));
  }

  // 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 internal or special items.
      if (!preg_match('/(none|label_\\d+|create_new_item)/', $item) && !in_array($item, $special_items['exclusive']) && !in_array($item, $special_items['none'])) {
        $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']) ? filter_xss_admin($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' => module_invoke($config['module'], 'hierarchical_select_item_get_label', $item, $config['params']),
          );
        }
      }
    }

    // Sanitize the labels.
    foreach ($dropbox->lineages as $id => $lineage) {
      foreach ($lineage as $level => $item) {
        $dropbox->lineages[$id][$level]['label'] = check_plain($dropbox->lineages[$id][$level]['label']);
      }
    }
    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'];
}

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

/**
 * Helper function needed for the array_filter() call to filter the items
 * marked with the 'exclusive' property
 *
 * @param $item
 *   An item in the 'special_items' setting.
 * @return
 *   TRUE if it's marked with the 'exclusive' property, FALSE otherwise.
 */
function _hierarchical_select_special_item_exclusive($item) {
  return in_array('exclusive', $item);
}

/**
 * Helper function needed for the array_filter() call to filter the items
 * marked with the 'none' property
 *
 * @param $item
 *   An item in the 'special_items' setting.
 * @return
 *   TRUE if it's marked with the 'none' property, FALSE otherwise.
 */
function _hierarchical_select_special_item_none($item) {
  return in_array('none', $item);
}

/**
 * Abstraction around drupal_add_js() and Views' $form_state['js settings'].
 *
 * @param $settings
 *   The JS settings you'd like to add.
 * @param $form_state
 *   A form state array.
 */
function _hierarchical_select_add_js_settings($settings, &$form_state) {
  global $views_ajax_form_js_settings;

  // If we're on a Views-powered form, we must use $form_state['js settings'].
  if (isset($form_state['view']) && isset($form_state['ajax']) && !empty($form_state['ajax'])) {
    $form_state['js settings'] = !isset($form_state['js settings']) || !is_array($form_state['js settings']) ? array() : $form_state['js settings'];
    $form_state['js settings'] = array_merge_recursive($form_state['js settings'], $settings);
  }
  else {
    drupal_add_js($settings, 'setting');

    // Necessary for Views AJAX pager support.
    // Also see hierarchical_select_ajax_data_alter().
    if (isset($settings['HierarchicalSelect']['settings'])) {
      $views_ajax_form_js_settings = $settings['HierarchicalSelect']['settings'];
    }
  }
}

/**
 * Implementation of hook_ajax_data_alter().
 * (Necessary for Views AJAX pager support.)
 */
function hierarchical_select_ajax_data_alter(&$object, $module, $view) {
  global $views_ajax_form_js_settings;
  if (!empty($views_ajax_form_js_settings)) {
    $object->hs_drupal_js_settings = $views_ajax_form_js_settings;
    $object->__callbacks = array_merge(array(
      'Drupal.HierarchicalSelect.ajaxViewPagerSettingsUpdate',
    ), $object->__callbacks);
  }
}

Functions

Name	Description
hierarchical_select_after_build	Hierarchical select form element type #after_build callback.
hierarchical_select_ajax_data_alter	Implementation of hook_ajax_data_alter(). (Necessary for Views AJAX pager support.)
hierarchical_select_config_id_load	Wildcard loader for Hierarchical Select config ID's.
hierarchical_select_elements	Implementation of hook_elements().
hierarchical_select_features_api	Implementation of hook_features_api().
hierarchical_select_flush_caches	Implementation of hook_flush_caches().
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().
hierarchical_select_simpletest	Implementation of hook_simpletest().
hierarchical_select_theme	Implementation of hook_theme().
_hierarchical_select_add_js_settings	Abstraction around drupal_add_js() and Views' $form_state['js settings'].
_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_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_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_special_item_exclusive	Helper function needed for the array_filter() call to filter the items marked with the 'exclusive' property
_hierarchical_select_special_item_none	Helper function needed for the array_filter() call to filter the items marked with the 'none' property
_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_validate	Hierarchical select form element #element_validate callback.

Constants

Name	Description
HS_CACHE_LIFETIME_DEFAULT
HS_DEVELOPER_MODE