protected function WebformConditionals::topologicalSort in Webform 7.4

Sorts the conditionals into topological order.

The "nodes" of the list are the conditionals, not the components that they operate upon.

The webform components must already be sorted into component tree order before calling this method.

See http://en.wikipedia.org/wiki/Topological_sorting

2 calls to WebformConditionals::topologicalSort()

WebformConditionals::getOrder in includes/webform.webformconditionals.inc

Returns the (possibly cached) topological sort order.

WebformConditionals::getPageMap in includes/webform.webformconditionals.inc

Returns an index of components by page number.

File

includes/webform.webformconditionals.inc, line 69

Conditional engine to process dependencies within the webform's conditionals.

Class

WebformConditionals

Performs analysis and topological sorting on the conditionals.

Code

protected function topologicalSort() {
  $components = $this->node->webform['components'];
  $conditionals = $this->node->webform['conditionals'];
  $errors = array();

  // Generate a component to conditional map for conditional targets.
  $cid_to_target_rgid = array();
  $cid_hidden = array();
  foreach ($conditionals as $rgid => $conditional) {
    foreach ($conditional['actions'] as $aid => $action) {
      $target_id = $action['target'];
      $cid_to_target_rgid[$target_id][$rgid] = $rgid;
      if ($action['action'] == 'show') {
        $cid_hidden[$target_id] = isset($cid_hidden[$target_id]) ? $cid_hidden[$target_id] + 1 : 1;
        if ($cid_hidden[$target_id] == 2) {
          $component = $components[$target_id];
          $errors[$component['page_num']][] = t('More than one conditional hides or shows component "@name".', array(
            '@name' => $component['name'],
          ));
        }
      }
    }
  }

  // Generate T-Orders for each page.
  $new_entry = array(
    'in' => array(),
    'out' => array(),
    'rgid' => array(),
  );
  $page_num = 0;

  // If the first component is a page break, then no component is on page 1. Create empty arrays for page 1.
  $sorted = array(
    1 => array(),
  );
  $page_map = array(
    1 => array(),
  );
  $component = reset($components);
  while ($component) {
    $cid = $component['cid'];

    // Start a new page, if needed.
    if ($component['page_num'] > $page_num) {
      $page_num = $component['page_num'];

      // Create an empty list that will contain the sorted elements.
      // This list is known as L in the literature.
      $sorted[$page_num] = array();

      // Create an empty list of dependency nodes for this page.
      $nodes = array();
    }

    // Create the pageMap as a side benefit of generating the t-sort.
    $page_map[$page_num][$cid] = $cid;

    // Process component by adding it's conditional data to a component-tree-traversal order an index of:
    // - incoming dependencies = the source components for the conditions for this target component and
    // - outgoing dependencies = components which depend upon the target component
    // Note: Surprisingly, 0 is a valid rgid, as well as a valid rid. Use -1 as a semaphore.
    if (isset($cid_to_target_rgid[$cid])) {

      // The component is the target of conditional(s)
      foreach ($cid_to_target_rgid[$cid] as $rgid) {
        $conditional = $conditionals[$rgid];
        if (!isset($nodes[$cid])) {
          $nodes[$cid] = $new_entry;
        }
        $nodes[$cid]['rgid'][$rgid] = $rgid;
        foreach ($conditional['rules'] as $rule) {
          if ($rule['source_type'] == 'component') {
            $source_id = $rule['source'];
            if (!isset($nodes[$source_id])) {
              $nodes[$source_id] = $new_entry;
            }
            $nodes[$cid]['in'][$source_id] = $source_id;
            $nodes[$source_id]['out'][$cid] = $cid;
            $source_component = $components[$source_id];
            $source_pid = $source_component['pid'];
            if ($source_pid) {
              if (!isset($nodes[$source_pid])) {
                $nodes[$source_pid] = $new_entry;
              }

              // The rule source is within a parent fieldset. Create a dependency on the parent.
              $nodes[$source_pid]['out'][$source_id] = $source_id;
              $nodes[$source_id]['in'][$source_pid] = $source_pid;
            }
            if ($source_component['page_num'] > $page_num) {
              $errors[$page_num][] = t('A forward reference from page @from, %from to %to was found.', array(
                '%from' => $source_component['name'],
                '@from' => $source_component['page_num'],
                '%to' => $component['name'],
              ));
            }
            elseif ($source_component['page_num'] == $page_num && $component['type'] == 'pagebreak') {
              $errors[$page_num][] = t("The page break %to can't be controlled by %from on the same page.", array(
                '%from' => $source_component['name'],
                '%to' => $component['name'],
              ));
            }
          }
        }
      }
    }

    // Fetch the next component, if any.
    $component = next($components);

    // Finish any previous page already processed.
    if (!$component || $component['page_num'] > $page_num) {

      // Create a set of all components which have are not dependent upon anything.
      // This list is known as S in the literature.
      $start_nodes = array();
      foreach ($nodes as $id => $n) {
        if (!$n['in']) {
          $start_nodes[] = $id;
        }
      }

      // Process the start nodes, removing each one in turn from the queue.
      while ($start_nodes) {
        $id = array_shift($start_nodes);

        // If the node represents an actual conditional, it can now be added
        // to the end of the sorted order because anything it depends upon has
        // already been calculated.
        if ($nodes[$id]['rgid']) {
          foreach ($nodes[$id]['rgid'] as $rgid) {
            $sorted[$page_num][] = array(
              'cid' => $id,
              'rgid' => $rgid,
              'name' => $components[$id]['name'],
            );
          }
        }

        // Any other nodes that depend upon this node may now have their dependency
        // on this node removed, since it has now been calculated.
        foreach ($nodes[$id]['out'] as $out_id) {
          unset($nodes[$out_id]['in'][$id]);
          if (!$nodes[$out_id]['in']) {
            $start_nodes[] = $out_id;
          }
        }

        // All out-going dependencies have been handled.
        $nodes[$id]['out'] = array();
      }

      // Check for a cyclic graph (circular dependency).
      foreach ($nodes as $id => $n) {
        if ($n['in'] || $n['out']) {
          $errors[$page_num][] = t('A circular reference involving %name was found.', array(
            '%name' => $components[$id]['name'],
          ));
        }
      }
    }

    // End finishing previous page.
  }

  // End component loop.
  // Create an empty page map for the preview page.
  $page_map[$page_num + 1] = array();
  $this->topologicalOrder = $sorted;
  $this->errors = $errors;
  $this->pageMap = $page_map;
}