# Copyright 2015 VMware, Inc.  All rights reserved. -- VMware Confidential
#
'''
Holder of a class representing components dependencies, and utilities over
that representation.
'''

import logging

logger = logging.getLogger(__name__)

class CyclicGraphDependencyError(ValueError):
    '''Thrown if there is a graph unresolvable cyclic dependency.
    '''
    def __init__(self, msg, components):
        ValueError.__init__(self, msg)
        self.components = components

class Graph(object):
    '''Graph representation of components dependencies.
    '''

    def __init__(self):
        '''Creates new Components graph instance.
        '''
        # Keep all components and their dependencies
        self.components = {}

    def addComponentDependency(self, depComponent, component):
        '''Add component dependency between two components, i.e. depComponent
        depends on component.

        @param depComponent: Name of the component which depends on component

        @param component: Name of the component which depComponent depends on.
        '''
        self.addComponentDependencies(depComponent, [component])

    def addComponentDependencies(self, depComponent, components):
        '''Add component dependencies.

        @param depComponent: Name of the component which depends on given
          components

        @param components: Name of the components which depComponent depends on.
        '''
        self.getComponentDependencies(depComponent).update(components)

    def addComponentsDependency(self, depComponents, component):
        '''Add component dependencies.

        @param depComponents: Name of the components which depends on given
          component

        @param component: Name of the component which depComponents depend on.
        '''
        for depComp in depComponents:
            self.addComponentDependency(depComp, component)

    def getComponentDependencies(self, componentName):
        '''Gets the component dependencies.

        @param component: Component name

        @return: Set of component names which current component is depending on.
        '''
        dependencies = self.components.get(componentName, None)
        if dependencies is None:
            dependencies = set()
            self.components[componentName] = dependencies
        return dependencies

def sortTopologically(graph):
    '''Sorts the graph topologically.

    @param graph: Component graph instance

    @return: 1dimentional array, where each component is sorted by its
      dependencies. The components on index (i) have at least one dependency
      from the components at index j < i. The order of components which have
      none or same dependencies is undefined.
    Example:
       a depends on b; b depends on c; a depends on d, d depends on c
       [c, b, d, a]

    @raise CyclicGraphDependencyError: If a cyclic dependency is found
    '''
    def _addComponentDependeciesFirst(graph, sortedList, inspectedComp, traversedList):
        if inspectedComp in sortedList:
            # Already added
            return
        if inspectedComp in traversedList:
            raise CyclicGraphDependencyError(
                    'Found cyclic dependency! Suspected components: %s' % str(traversedList),
                    traversedList)

        traversedList.append(inspectedComp)
        for depComp in graph.getComponentDependencies(inspectedComp):
            _addComponentDependeciesFirst(graph, sortedList, depComp, traversedList)
        traversedList.remove(inspectedComp)

        sortedList.append(inspectedComp)

    sortedList = []
    traversedList = []
    for comp in graph.components.keys():
        _addComponentDependeciesFirst(graph, sortedList, comp, traversedList)

    return sortedList

class GraphBuilder(object):
    '''Builds the graph object based on the components dependencies.
    '''
    def __init__(self, components):
        '''Creates a builder of components dependencies graph.

        @param components: Array of components
        @type components: Array of vmware.patching.data.model.Component
        '''
        if components is None:
            raise ValueError('Invalid components input.')

        self.components = components

    def buildDependenciesGraph(self):
        '''Builds a component graph based on the source components dependencies.
          Every edge(a->b) shows that component a should be patched after b.

        @return: Graph object where the graph edges represent the components
          dependencies.
        @rtype: Graph
        '''
        graph = Graph()
        seenComponents = []
        componentsNames = [c.discoveryResult.componentId for c in self.components]
        for c in self.components:
            componentName = c.discoveryResult.componentId
            if componentName in seenComponents:
                raise ValueError('More than one patch script wants to patch'
                                'component %s.', componentName)
            seenComponents.append(componentName)

            # Special handling for system last-patching-component. We want
            # this component to be specially handled and do not rely on the
            # components's dependency in order to be executed as last component
            # regardless the new coming components.
            if componentName == "last-patching-component":
                dependentComponents = list(componentsNames)
                dependentComponents.remove(componentName)
            else:
                #This ensures that graph only contains nodes that participate
                # in patching
                dependentComponents = [comp for comp in c.discoveryResult.dependentComponents \
                                            if comp in componentsNames]
            graph.addComponentDependencies(componentName, dependentComponents)
        return graph