diff options
Diffstat (limited to 'includes')
| -rw-r--r-- | includes/common.inc | 2 | ||||
| -rw-r--r-- | includes/graph.inc | 143 | ||||
| -rw-r--r-- | includes/module.inc | 76 |
3 files changed, 165 insertions, 56 deletions
diff --git a/includes/common.inc b/includes/common.inc index 874c3acdc..8de8894e3 100644 --- a/includes/common.inc +++ b/includes/common.inc @@ -3866,7 +3866,7 @@ function drupal_write_record($table, &$object, $primary_keys = array()) { * Information stored in the module.info file: * - name: The real name of the module for display purposes. * - description: A brief description of the module. - * - dependencies: An array of shortnames of other modules this module depends on. + * - dependencies: An array of shortnames of other modules this module requires. * - package: The name of the package of modules this module belongs to. * * Example of .info file: diff --git a/includes/graph.inc b/includes/graph.inc new file mode 100644 index 000000000..38b2abb1c --- /dev/null +++ b/includes/graph.inc @@ -0,0 +1,143 @@ +<?php +// $Id$ + +/** + * @file + * Directed acyclic graph functions. + */ + + +/** + * Perform a depth first sort on a directed acyclic graph. + * + * @param $graph + * A three dimensional associated array, with the first keys being the names + * of the vertices, these can be strings or numbers. The second key is + * 'edges' and the third one are again vertices, each such key representing + * an edge. Values of array elements do not matter. + * + * Example: + * @code + * $graph[1]['edges'][2] = 1; + * $graph[2]['edges'][3] = 1; + * $graph[2]['edges'][4] = 1; + * $graph[3]['edges'][4] = 1; + * @endcode + * + * On return you will also have: + * @code + * $graph[1]['paths'][2] = 1; + * $graph[1]['paths'][3] = 2; + * $graph[2]['reverse_paths'][1] = 1; + * $graph[3]['reverse_paths'][1] = 1; + * @endcode + * + * @return + * The passed in $graph with more secondary keys filled in: + * - 'paths': Contains a list of vertices than can be reached on a path from + * this vertex. + * - 'reverse_paths': Contains a list of vertices that has a path from them + * to this vertex. + * - 'weight': If there is a path from a vertex to another then the weight of + * the latter is higher. + * - 'component': Vertices in the same component have the same component + * identifier. + * + * @see _drupal_depth_first_search() + */ +function drupal_depth_first_search(&$graph) { + $state = array( + // The order of last visit of the depth first search. This is the reverse + // of the topological order if the graph is acyclic. + 'last_visit_order' => array(), + // The components of the graph. + 'components' => array(), + ); + // Perform the actual sort. + foreach ($graph as $start => $data) { + _drupal_depth_first_search($graph, $state, $start); + } + + // We do such a numbering that every component starts with 0. This is useful + // for module installs as we can install every 0 weighted module in one + // request, and then every 1 weighted etc. + $component_weights = array(); + + foreach ($state['last_visit_order'] as $vertex) { + $component = $graph[$vertex]['component']; + if (!isset($component_weights[$component])) { + $component_weights[$component] = 0; + } + $graph[$vertex]['weight'] = $component_weights[$component]--; + } +} + +/** + * Helper function to perform a depth first sort. + * + * @param &$graph + * A three dimensional associated graph array. + * @param &$state + * An associative array. The key 'last_visit_order' stores a list of the + * vertices visited. The key components stores list of vertices belonging + * to the same the component. + * @param $start + * An arbitrary vertex where we started traversing the graph. + * @param &$component + * The component of the last vertex. + * + * @see drupal_depth_first_search() + */ +function _drupal_depth_first_search(&$graph, &$state, $start, &$component = NULL) { + // Assign new component for each new vertex, i.e. when not called recursively. + if (!isset($component)) { + $component = $start; + } + // Nothing to do, if we already visited this vertex. + if (isset($graph[$start]['paths'])) { + return; + } + // Mark $start as visited. + $graph[$start]['paths'] = array(); + + // Assign $start to the current component. + $graph[$start]['component'] = $component; + $state['components'][$component][] = $start; + + // Visit edges of $start. + if (isset($graph[$start]['edges'])) { + foreach ($graph[$start]['edges'] as $end => $v) { + // Mark that $start can reach $end. + $graph[$start]['paths'][$end] = TRUE; + + if (isset($graph[$end]['component']) && $component != $graph[$end]['component']) { + // This vertex already has a component, use that from now on and + // reassign all the previously explored vertices. + $new_component = $graph[$end]['component']; + foreach ($state['components'][$component] as $vertex) { + $graph[$vertex]['component'] = $new_component; + $state['components'][$new_component][] = $vertex; + } + unset($state['components'][$component]); + $component = $new_component; + } + + // Visit the connected vertex. + _drupal_depth_first_search($graph, $state, $end, $component); + + // All vertices reachable by $end are also reachable by $start. + $graph[$start]['paths'] += $graph[$end]['paths']; + } + } + + // Now that any other subgraph has been explored, add $start to all reverse + // paths. + foreach ($graph[$start]['paths'] as $end => $v) { + $graph[$end]['reverse_paths'][$start] = TRUE; + } + + // Record the order of the last visit. This is the reverse of the + // topological order if the graph is acyclic. + $state['last_visit_order'][] = $start; +} + diff --git a/includes/module.inc b/includes/module.inc index c3ee22128..ca5388e57 100644 --- a/includes/module.inc +++ b/includes/module.inc @@ -145,69 +145,35 @@ function module_rebuild_cache() { } /** - * Find dependencies any level deep and fill in dependents information too. - * - * If module A depends on B which in turn depends on C then this function will - * add C to the list of modules A depends on. This will be repeated until - * module A has a list of all modules it depends on. If it depends on itself, - * called a circular dependency, that's marked by adding a nonexistent module, - * called -circular- to this list of modules. Because this does not exist, - * it'll be impossible to switch module A on. - * - * Also we fill in a dependents array in $file->info. Using the names above, - * the dependents array of module B lists A. + * Find dependencies any level deep and fill in required by information too. * * @param $files * The array of filesystem objects used to rebuild the cache. * @return - * The same array with dependencies and dependents added where applicable. + * The same array with the new keys for each module: + * - requires: An array with the keys being the modules that this module + * requires. + * - required_by: An array with the keys being the modules that will not work + * without this module. */ function _module_build_dependencies($files) { - do { - $new_dependency = FALSE; - foreach ($files as $filename => $file) { - // We will modify this object (module A, see doxygen for module A, B, C). - $file = &$files[$filename]; - if (isset($file->info['dependencies']) && is_array($file->info['dependencies'])) { - foreach ($file->info['dependencies'] as $dependency_name) { - // This is a nonexistent module. - if ($dependency_name == '-circular-' || !isset($files[$dependency_name])) { - continue; - } - // $dependency_name is module B (again, see doxygen). - $files[$dependency_name]->info['dependents'][$filename] = $filename; - $dependency = $files[$dependency_name]; - if (isset($dependency->info['dependencies']) && is_array($dependency->info['dependencies'])) { - // Let's find possible C modules. - foreach ($dependency->info['dependencies'] as $candidate) { - if (array_search($candidate, $file->info['dependencies']) === FALSE) { - // Is this a circular dependency? - if ($candidate == $filename) { - // As a module name can not contain dashes, this makes - // impossible to switch on the module. - $candidate = '-circular-'; - // Do not display the message or add -circular- more than once. - if (array_search($candidate, $file->info['dependencies']) !== FALSE) { - continue; - } - drupal_set_message(t('%module is part of a circular dependency. This is not supported and you will not be able to switch it on.', array('%module' => $file->info['name'])), 'error'); - } - else { - // We added a new dependency to module A. The next loop will - // be able to use this as "B module" thus finding even - // deeper dependencies. - $new_dependency = TRUE; - } - $file->info['dependencies'][] = $candidate; - } - } - } - } + require_once DRUPAL_ROOT .'/includes/graph.inc'; + $roots = $files; + foreach ($files as $filename => $file) { + $graph[$file->name]['edges'] = array(); + if (isset($file->info['dependencies']) && is_array($file->info['dependencies'])) { + foreach ($file->info['dependencies'] as $dependency_name) { + $graph[$file->name]['edges'][$dependency_name] = 1; + unset($roots[$dependency_name]); } - // Don't forget to break the reference. - unset($file); } - } while ($new_dependency); + } + drupal_depth_first_search($graph, array_keys($roots)); + foreach ($graph as $module => $data) { + $files[$module]->required_by= isset($data['reverse_paths']) ? $data['reverse_paths'] : array(); + $files[$module]->requires = isset($data['paths']) ? $data['paths'] : array(); + $files[$module]->sort = $data['weight']; + } return $files; } |