"""The tasklist module contains the TaskList class. """ from bootstrapvz.common.exceptions import TaskListError import logging log = logging.getLogger(__name__) class TaskList(object): """The tasklist class aggregates all tasks that should be run and orders them according to their dependencies. """ def __init__(self, tasks): self.tasks = tasks self.tasks_completed = [] def run(self, info, dry_run=False): """Converts the taskgraph into a list and runs all tasks in that list :param dict info: The bootstrap information object :param bool dry_run: Whether to actually run the tasks or simply step through them """ # Get a hold of every task we can find, so that we can topologically sort # all tasks, rather than just the subset we are going to run. # We pass in the modules which the manifest has already loaded in order # to support third-party plugins, which are not in the bootstrapvz package # and therefore wouldn't be discovered. all_tasks = set(get_all_tasks([info.manifest.modules['provider']] + info.manifest.modules['plugins'])) # Create a list for us to run task_list = create_list(self.tasks, all_tasks) # Output the tasklist log.debug('Tasklist:\n\t' + ('\n\t'.join(map(repr, task_list)))) for task in task_list: # Tasks are not required to have a description if hasattr(task, 'description'): log.info(task.description) else: # If there is no description, simply coerce the task into a string and print its name log.info('Running ' + str(task)) if not dry_run: # Run the task task.run(info) # Remember which tasks have been run for later use (e.g. when rolling back, because of an error) self.tasks_completed.append(task) def load_tasks(function, manifest, *args): """Calls ``function`` on the provider and all plugins that have been loaded by the manifest. Any additional arguments are passed directly to ``function``. The function that is called shall accept the taskset as its first argument and the manifest as its second argument. :param str function: Name of the function to call :param Manifest manifest: The manifest :param list args: Additional arguments that should be passed to the function that is called """ tasks = set() # Call 'function' on the provider getattr(manifest.modules['provider'], function)(tasks, manifest, *args) for plugin in manifest.modules['plugins']: # Plugins are not required to have whatever function we call fn = getattr(plugin, function, None) if callable(fn): fn(tasks, manifest, *args) return tasks def create_list(taskset, all_tasks): """Creates a list of all the tasks that should be run. """ from bootstrapvz.common.phases import order # Make sure all_tasks is a superset of the resolved taskset if not all_tasks >= taskset: msg = ('bootstrap-vz generated a list of all available tasks. ' 'That list is not a superset of the tasks required for bootstrapping. ' 'The tasks that were not found are: {tasks} ' '(This is an error in the code and not the manifest, please report this issue.)' .format(tasks=', '.join(map(str, taskset - all_tasks))) ) raise TaskListError(msg) # Create a graph over all tasks by creating a map of each tasks successors graph = {} for task in all_tasks: # Do a sanity check first check_ordering(task) successors = set() # Add all successors mentioned in the task successors.update(task.successors) # Add all tasks that mention this task as a predecessor successors.update(filter(lambda succ: task in succ.predecessors, all_tasks)) # Create a list of phases that succeed the phase of this task succeeding_phases = order[order.index(task.phase) + 1:] # Add all tasks that occur in above mentioned succeeding phases successors.update(filter(lambda succ: succ.phase in succeeding_phases, all_tasks)) # Map the successors to the task graph[task] = successors # Use the strongly connected components algorithm to check for cycles in our task graph components = strongly_connected_components(graph) cycles_found = 0 for component in components: # Node of 1 is also a strongly connected component but hardly a cycle, so we filter them out if len(component) > 1: cycles_found += 1 log.debug('Cycle: {list}\n' + (', '.join(map(repr, component)))) if cycles_found > 0: msg = ('{num} cycles were found in the tasklist, ' 'consult the logfile for more information.'.format(num=cycles_found)) raise TaskListError(msg) # Run a topological sort on the graph, returning an ordered list sorted_tasks = topological_sort(graph) # Filter out any tasks not in the tasklist # We want to maintain ordering, so we don't use set intersection sorted_tasks = filter(lambda task: task in taskset, sorted_tasks) return sorted_tasks def get_all_tasks(loaded_modules): """Gets a list of all task classes in the package :return: A list of all tasks in the package :rtype: list """ import pkgutil import os.path import bootstrapvz from bootstrapvz.common.tools import rel_path module_paths = set([(rel_path(bootstrapvz.__file__, 'common/tasks'), 'bootstrapvz.common.tasks.')]) for module in loaded_modules: module_path = os.path.dirname(module.__file__) module_prefix = module.__name__ + '.' module_paths.add((module_path, module_prefix)) providers = rel_path(bootstrapvz.__file__, 'providers') for module_loader, module_name, ispkg in pkgutil.iter_modules([providers, 'bootstrapvz.providers']): module_path = os.path.join(module_loader.path, module_name) # The prefix param seems to do nothing, so we prefix the module name ourselves module_prefix = 'bootstrapvz.providers.{}.'.format(module_name) module_paths.add((module_path, module_prefix)) plugins = rel_path(bootstrapvz.__file__, 'plugins') for module_loader, module_name, ispkg in pkgutil.iter_modules([plugins, 'bootstrapvz.plugins']): module_path = os.path.join(module_loader.path, module_name) module_prefix = 'bootstrapvz.plugins.{}.'.format(module_name) module_paths.add((module_path, module_prefix)) # Get generators that return all classes in a module generators = [] for (module_path, module_prefix) in module_paths: generators.append(get_all_classes(module_path, module_prefix)) import itertools classes = itertools.chain(*generators) # lambda function to check whether a class is a task (excluding the superclass Task) def is_task(obj): from task import Task return issubclass(obj, Task) and obj is not Task return filter(is_task, classes) # Only return classes that are tasks def get_all_classes(path=None, prefix='', excludes=[]): """ Given a path to a package, this function retrieves all the classes in it :param str path: Path to the package :param str prefix: Name of the package followed by a dot :param list excludes: List of str matching module names that should be ignored :return: A generator that yields classes :rtype: generator :raises Exception: If a module cannot be inspected. """ import pkgutil import importlib import inspect def walk_error(module_name): if not any(map(lambda excl: module_name.startswith(excl), excludes)): raise TaskListError('Unable to inspect module ' + module_name) walker = pkgutil.walk_packages([path], prefix, walk_error) for _, module_name, _ in walker: if any(map(lambda excl: module_name.startswith(excl), excludes)): continue module = importlib.import_module(module_name) classes = inspect.getmembers(module, inspect.isclass) for class_name, obj in classes: # We only want classes that are defined in the module, and not imported ones if obj.__module__ == module_name: yield obj def check_ordering(task): """Checks the ordering of a task in relation to other tasks and their phases. This function checks for a subset of what the strongly connected components algorithm does, but can deliver a more precise error message, namely that there is a conflict between what a task has specified as its predecessors or successors and in which phase it is placed. :param Task task: The task to check the ordering for :raises TaskListError: If there is a conflict between task precedence and phase precedence """ for successor in task.successors: # Run through all successors and throw an error if the phase of the task # lies before the phase of a successor, log a warning if it lies after. if task.phase > successor.phase: msg = ("The task {task} is specified as running before {other}, " "but its phase '{phase}' lies after the phase '{other_phase}'" .format(task=task, other=successor, phase=task.phase, other_phase=successor.phase)) raise TaskListError(msg) if task.phase < successor.phase: log.warn("The task {task} is specified as running before {other} " "although its phase '{phase}' already lies before the phase '{other_phase}' " "(or the task has been placed in the wrong phase)" .format(task=task, other=successor, phase=task.phase, other_phase=successor.phase)) for predecessor in task.predecessors: # Run through all successors and throw an error if the phase of the task # lies after the phase of a predecessor, log a warning if it lies before. if task.phase < predecessor.phase: msg = ("The task {task} is specified as running after {other}, " "but its phase '{phase}' lies before the phase '{other_phase}'" .format(task=task, other=predecessor, phase=task.phase, other_phase=predecessor.phase)) raise TaskListError(msg) if task.phase > predecessor.phase: log.warn("The task {task} is specified as running after {other} " "although its phase '{phase}' already lies after the phase '{other_phase}' " "(or the task has been placed in the wrong phase)" .format(task=task, other=predecessor, phase=task.phase, other_phase=predecessor.phase)) def strongly_connected_components(graph): """Find the strongly connected components in a graph using Tarjan's algorithm. Source: http://www.logarithmic.net/pfh-files/blog/01208083168/sort.py :param dict graph: mapping of tasks to lists of successor tasks :return: List of tuples that are strongly connected comoponents :rtype: list """ result = [] stack = [] low = {} def visit(node): if node in low: return num = len(low) low[node] = num stack_pos = len(stack) stack.append(node) for successor in graph[node]: visit(successor) low[node] = min(low[node], low[successor]) if num == low[node]: component = tuple(stack[stack_pos:]) del stack[stack_pos:] result.append(component) for item in component: low[item] = len(graph) for node in graph: visit(node) return result def topological_sort(graph): """Runs a topological sort on a graph. Source: http://www.logarithmic.net/pfh-files/blog/01208083168/sort.py :param dict graph: mapping of tasks to lists of successor tasks :return: A list of all tasks in the graph sorted according to ther dependencies :rtype: list """ count = {} for node in graph: count[node] = 0 for node in graph: for successor in graph[node]: count[successor] += 1 ready = [node for node in graph if count[node] == 0] result = [] while ready: node = ready.pop(-1) result.append(node) for successor in graph[node]: count[successor] -= 1 if count[successor] == 0: ready.append(successor) return result