######################################################################
# Copyright (C) 2019-2020 VMWare, Inc.
# All Rights Reserved
######################################################################

"""
This module contains classes that support component scanning and
validation.
"""
import logging

from . import Scan
from .ImageManager.Constants import VALIDATE_PREFIX
from .ImageManager.Utils import Notification

logger = logging.getLogger('ComponentScanner')

BASE_TASK_TIME_FORMAT = '%Y-%m-%dT%H:%M:%S.%f'
ROLE_CONFLICT_COMP = 0
ROLE_REPLACED_BY_COMP = 1
ROLE_REPLACES_COMP = 2
# The depth of recursion to find a resolution to a problem
RESOLUTION_DEPTH = 5
isNotNone = lambda x: x is not None

def _getCompUiStr(compUiStrMap, compId):
   """Helper to get component UI string while handling KeyError.
   """
   try:
      return compUiStrMap[compId]
   except KeyError:
      raise KeyError('Cannot find UI string of component %s' % compId)

def _getJoinedCompsStr(compUiStrMap, compIds):
   """Translate a set of component IDs to UI strings, sort them, and join
      into a comma-separated list.
   """
   return ', '.join(sorted([_getCompUiStr(compUiStrMap, c) for c in compIds]))


class ComponentScanProblem(object):
   """Structure to hold scan result information.

      Attributes:
         * id             - Problem id of the form type:compId
         * reltype        - Type of relation of the problem.
         * addedResArgs   - Newly added resolution arguments for resolution.
         * removedResArgs - Deleted resolution arguments for resolution.
         * isResolved     - True when the problem has resolution
                            otherwise False
   """
   TYPE_CONFLICT = 'conflicts'
   TYPE_SELFCONFLICT = 'selfconflict'
   TYPE_OBSOLETES = 'obsoletes'
   TYPE_SELFOBSOLETE = 'selfobsolete'
   TYPE_DEPENDS = 'unmetdependency'
   ALL_TYPES = (TYPE_CONFLICT, TYPE_SELFCONFLICT, TYPE_OBSOLETES,
                TYPE_SELFOBSOLETE, TYPE_DEPENDS)
   # Resolution messages
   ADD_REMOVE_RES_MSG = ('Add component(s) %(addComps)s and remove component(s)'
                         ' %(removeComps)s to resolve the problem.')
   ADD_RES_MSG = 'Add component(s) %(addComps)s to resolve the problem.'
   REMOVE_RES_MSG = ('Remove component(s) %(removeComps)s to resolve the'
                     ' problem.')
   NO_RES_MSG = 'Problem with component %(comp)s could not be resolved.'
   SELF_CONFLICT_RES_MSG = ('Remove component %(comp)s as it contains'
                            ' conflicting VIBs.')
   SELF_OBSOLETE_RES_MSG = ('Remove component %(comp)s as it contains VIBs'
                            ' that obsolete each other.')
   # Below messages are for notifications where argument starts from {1}
   ADD_REMOVE_RES_NTFN_MSG = ADD_REMOVE_RES_MSG.replace('%(addComps)s', '{1}') \
                                .replace('%(removeComps)s', '{2}')
   ADD_RES_NTFN_MSG = ADD_RES_MSG.replace('%(addComps)s', '{1}')
   REMOVE_RES_NTFN_MSG = REMOVE_RES_MSG.replace('%(removeComps)s', '{1}')
   NO_RES_NTFN_MSG = NO_RES_MSG.replace('%(comp)s', '{1}')
   SELF_CONFLICT_RES_NTFN_MSG = SELF_CONFLICT_RES_MSG.replace('%(comp)s',
                                                              '{1}')
   SELF_OBSOLETE_RES_NTFN_MSG = SELF_OBSOLETE_RES_MSG.replace('%(comp)s',
                                                              '{1}')
   # Below are notification ids for each type of resolution message
   RES_MSG_PREFIX = VALIDATE_PREFIX + 'Resolution.'
   ADD_REMOVE_RES_ID = RES_MSG_PREFIX + 'AddRemoveComponents'
   ADD_RES_ID = RES_MSG_PREFIX + 'AddComponents'
   REMOVE_RES_ID = RES_MSG_PREFIX + 'RemoveComponents'
   NO_RES_ID = RES_MSG_PREFIX + 'NoResolution'
   SELF_CONFLICT_RES_ID = RES_MSG_PREFIX + 'SelfConflict'
   SELF_OBSOLETE_RES_ID = RES_MSG_PREFIX + 'SelfObsolete'

   def __init__(self):
      self.comp = ''
      self.msg = ''
      self._reltype = ''
      self.addedResArgs = set()
      self.removedResArgs = set()
      self.isResolved = False

   def __str__(self):
      return '%s' % self.msg

   def __eq__(self, other):
      return self.id == other.id

   @property
   def id(self):
      raise NotImplementedError('Must instantiate a sub-class')

   def ImpactsComponent(self, compId):
      """Returns if this problem concerns a component.
      """
      return self.comp == compId

   def _SetReltype(self, reltype):
      if reltype not in self.ALL_TYPES:
         raise ValueError('%s is not a valid component relation type' % reltype)
      self._reltype = reltype

   def UpdatePartialRes(self, res):
      """Collects recursion result to update problem with resolution result.

         Parameters:
            * res - A ResolutionResult object holding partial resolution
                    result for the problem
      """
      self.addedResArgs.update(res.addedComps)
      self.removedResArgs.update(res.removedComps)
      if self.addedResArgs & self.removedResArgs:
         # Self-conflicting resolution (add and then remove).
         self.isResolved = False
      else:
         self.isResolved = self.isResolved or res.isResolved

   def _getResolutionInfo(self, compUiStrMap):
      """Returns resolution ID, message and arguments.
      """
      if not self.isResolved:
         return (self.NO_RES_ID, self.NO_RES_NTFN_MSG,
                 [_getCompUiStr(compUiStrMap, self.comp)])

      if self.reltype == self.TYPE_SELFCONFLICT:
         resId = self.SELF_CONFLICT_RES_ID
         resMsg = self.SELF_CONFLICT_RES_NTFN_MSG
         resArgs = [_getCompUiStr(compUiStrMap, self.comp)]
      elif self.reltype == self.TYPE_SELFOBSOLETE:
         resId = self.SELF_OBSOLETE_RES_ID
         resMsg = self.SELF_OBSOLETE_RES_NTFN_MSG
         resArgs = [_getCompUiStr(compUiStrMap, self.comp)]
      elif self.addedResArgs and self.removedResArgs:
         resId = self.ADD_REMOVE_RES_ID
         resMsg = self.ADD_REMOVE_RES_NTFN_MSG
         resArgs = [_getJoinedCompsStr(compUiStrMap, self.addedResArgs),
                    _getJoinedCompsStr(compUiStrMap, self.removedResArgs)]
      elif self.addedResArgs:
         resId = self.ADD_RES_ID
         resMsg = self.ADD_RES_NTFN_MSG
         resArgs = [_getJoinedCompsStr(compUiStrMap, self.addedResArgs)]
      elif self.removedResArgs:
         resId = self.REMOVE_RES_ID
         resMsg = self.REMOVE_RES_NTFN_MSG
         resArgs = [_getJoinedCompsStr(compUiStrMap, self.removedResArgs)]

      return resId, resMsg, resArgs

   reltype = property(lambda self: self._reltype, _SetReltype)

class ComponentConflict(ComponentScanProblem):
   """Structure to hold conflict scan result.

      Attributes:
         * comp         - Component Id which has unmet dependency
         * conflictComp - Component Id which conflicts with comp
   """
   SELF_CONFLICT_MSG = 'Component %(comp)s has VIBs that conflict each other.'
   CONFLICT_MSG = 'Component %(comp)s conflicts with %(conflictComp)s.'
   # Below messages are for notifications where argument starts from {1}
   SELF_CONFLICT_NTFN_MSG = SELF_CONFLICT_MSG.replace('%(comp)s', '{1}')
   CONFLICT_NTFN_MSG = CONFLICT_MSG.replace('%(comp)s', '{1}') \
                          .replace('%(conflictComp)s', '{2}')

   def __init__(self, comp, conflictComp):
      super(ComponentConflict, self).__init__()
      # Since conflicts are bi-directional, sort them to make sure ID is
      # consistent and ___eq__ works.
      self.comp, self.conflictComp = sorted([comp, conflictComp])

      if self.comp == self.conflictComp:
         self.reltype = self.TYPE_SELFCONFLICT
         self.msg = self.SELF_CONFLICT_MSG % {'comp': self.comp}
      else:
         self.reltype = self.TYPE_CONFLICT
         self.msg = self.CONFLICT_MSG % {'comp': self.comp,
                                         'conflictComp': self.conflictComp}

   def __eq__(self, other):
      return self.reltype == other.reltype and self.comp == other.comp \
             and self.conflictComp == other.conflictComp

   @property
   def id(self):
      return self.reltype + '_' + self.comp + '_' + self.conflictComp

   def ImpactsComponent(self, compId):
      """Returns if this problem concerns a component.
      """
      return super().ImpactsComponent(compId) or self.conflictComp == compId

   def GetNotification(self, compUiStrMap):
      """Returns a Notification object with message and resolution for this
         problem. compUiStrMap is a map from component ID to its UI string
         to provide component arguments.
      """
      if self.reltype == self.TYPE_SELFCONFLICT:
         msgId = VALIDATE_PREFIX + 'SelfConflict'
         msg = self.SELF_CONFLICT_NTFN_MSG
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp)]
      else:
         msgId = VALIDATE_PREFIX + 'Conflict'
         msg = self.CONFLICT_NTFN_MSG
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp),
                    _getCompUiStr(compUiStrMap, self.conflictComp)]

      resId, resMsg, resArgs = self._getResolutionInfo(compUiStrMap)

      return Notification(msgId, msgId, msg, resId, resMsg, msgArgs, resArgs)

class ComponentObsolete(ComponentScanProblem):
   """Structure to hold obsolete scan result.

      Attributes:
         * comp           - Component ID which has unmet dependency
         * replacesComp   - Component ID which is replaced by comp
         * isFullObsolete - Indicates whether comp completely obsoletes
                            replacesComp, i.e. all vibs in replacesComp are
                            obsoleted
   """
   SELF_OBSOLETE_MSG = 'Component %(comp)s has VIBs that obsolete each other.'
   OBSOLETE_MSG = 'Component %(comp)s obsoletes %(replacesComp)s.'
   # Below messages are for notifications where argument starts from {1}
   SELF_OBSOLETE_NTFN_MSG = SELF_OBSOLETE_MSG.replace('%(comp)s', '{1}')
   OBSOLETE_NTFN_MSG = OBSOLETE_MSG.replace('%(comp)s', '{1}') \
                          .replace('%(replacesComp)s', '{2}')

   def __init__(self, comp, replacesComp, isFullObsolete):
      super(ComponentObsolete, self).__init__()
      self.comp = comp
      self.replacesComp = replacesComp
      self.isFullObsolete = isFullObsolete

      if self.comp == self.replacesComp:
         self.reltype = self.TYPE_SELFOBSOLETE
         self.msg = self.SELF_OBSOLETE_MSG % {'comp': self.comp}
      else:
         self.reltype = self.TYPE_OBSOLETES
         self.msg = self.OBSOLETE_MSG % {'comp': self.comp,
                                         'replacesComp': self.replacesComp}

   @property
   def id(self):
      return self.reltype + '_' + self.comp + '_' + self.replacesComp

   def ImpactsComponent(self, comp):
      """Returns if this problem concerns a component.
      """
      return super().ImpactsComponent(comp) or self.replacesComp == comp

   def GetNotification(self, compUiStrMap):
      """Returns a Notification object with message and resolution for this
         problem. compUiStrMap is a map from component ID to its UI string
         to provide component arguments.
      """
      if self.reltype == self.TYPE_SELFOBSOLETE:
         msgId = VALIDATE_PREFIX + 'SelfObsolete'
         msg = self.SELF_OBSOLETE_NTFN_MSG
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp)]
      else:
         msgId = VALIDATE_PREFIX + 'Obsolete'
         msg = self.OBSOLETE_NTFN_MSG
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp),
                   _getCompUiStr(compUiStrMap, self.replacesComp)]

      resId, resMsg, resArgs = self._getResolutionInfo(compUiStrMap)

      return Notification(msgId, msgId, msg, resId, resMsg, msgArgs, resArgs)

class ComponentUnmetDep(ComponentScanProblem):
   """Structure to hold results from unmet dependency.

      Attributes:
         * comp               - Component Id which has unmet dependency
         * did                - Dependency Id of depends relation
         * dependsOnComps     - List of component Ids which can satisfy
                                the dependency problem for comp.
         * obsoletedProviders - Obsoleted providers of the dependency that are
                                in effective components. These components
                                will not be used as candidates to resolve
                                the problem.
   """
   UNMET_DEPENDENCY_MSG = ('Component %(comp)s has unmet dependency.'
                           ' It depends on %(depends)s.')
   UNMET_DEPENDENCY_NO_PROVIDES = ('Component %(comp)s has unmet dependency'
                                   ' %(did)s that is not provided by any'
                                   ' component in depot.')
   UNMET_DEPENDENCY_PROVIDER_OBSOLETED_MSG = ('Component %(comp)s has unmet '
      'dependency %(did)s because providing component(s) '
      '%(obsoletedProviders)s are obsoleted.')
   # Below messages are for notifications where argument starts from {1}
   UNMET_DEPENDENCY_NTFN_MSG = UNMET_DEPENDENCY_MSG.replace('%(comp)s', '{1}') \
                                  .replace('%(depends)s', '{2}')
   UNMET_DEPENDENCY_NO_PROVIDES_NTFN = UNMET_DEPENDENCY_NO_PROVIDES \
                                          .replace('%(comp)s', '{1}') \
                                          .replace('%(did)s', '{2}')
   UNMET_DEPENDENCY_PROVIDER_OBSOLETED_NTFN_MSG = \
      UNMET_DEPENDENCY_PROVIDER_OBSOLETED_MSG.replace('%(comp)s', '{1}') \
                                             .replace('%(did)s', '{2}') \
                                             .replace('%(obsoletedProviders)s',
                                                      '{3}')

   def __init__(self, comp, did, dependsOnComps, obsoletedProviders):
      super(ComponentUnmetDep, self).__init__()
      self.comp = comp
      self.did = did
      self.dependsOnComps = dependsOnComps
      self.obsoletedProviders = obsoletedProviders
      self.reltype = self.TYPE_DEPENDS

      if self.providerCandidates:
         self.msg = self.UNMET_DEPENDENCY_MSG % {'comp': self.comp,
                                                 'depends':
                                                 ', '.join(self.dependsOnComps)}
      elif self.obsoletedProviders:
         self.msg = self.UNMET_DEPENDENCY_PROVIDER_OBSOLETED_MSG % {
            'comp': self.comp,
            'did': self.did,
            'obsoletedProviders': ', '.join(self.obsoletedProviders),
         }
      else:
         self.msg = self.UNMET_DEPENDENCY_NO_PROVIDES % {'comp': self.comp,
                                                         'did': self.did}

   @property
   def providerCandidates(self):
      """Candidate components that can provide the dependency, which is
         all providers minus those that are obsoleted in effective components.
      """
      return list(set(self.dependsOnComps) - set(self.obsoletedProviders))

   @property
   def id(self):
      return self.reltype + '_' + self.comp + '_' + self.did

   def GetNotification(self, compUiStrMap):
      """Returns a Notification object with message and resolution for this
         problem. compUiStrMap is a map from component ID to its UI string
         to provide component arguments.
      """
      if self.providerCandidates:
         msgId = VALIDATE_PREFIX + 'Depend'
         msg = self.UNMET_DEPENDENCY_NTFN_MSG
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp),
                    _getJoinedCompsStr(compUiStrMap, self.providerCandidates)]
      elif self.obsoletedProviders:
         msgId = VALIDATE_PREFIX + 'ProviderComponentObsoleted'
         msg = self.UNMET_DEPENDENCY_PROVIDER_OBSOLETED_NTFN_MSG
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp), self.did,
                    _getJoinedCompsStr(compUiStrMap, self.obsoletedProviders)]
      else:
         msgId = VALIDATE_PREFIX + 'MissingProvidingComponent'
         msg = self.UNMET_DEPENDENCY_NO_PROVIDES_NTFN
         msgArgs = [_getCompUiStr(compUiStrMap, self.comp), self.did]

      resId, resMsg, resArgs = self._getResolutionInfo(compUiStrMap)

      return Notification(msgId, msgId, msg, resId, resMsg, msgArgs, resArgs)

class ProblemCollection(dict):
   """Provides methods to perform operations on validation scan result.
   """
   def __init__(self, compUiStrMap):
      # Used to generate notifications with UI name/version.
      self._compUiStrMap = compUiStrMap

   def HasProblem(self, problemId):
      return problemId in self

   def AddProblem(self, problem):
      if self.HasProblem(problem.id):
         self[problem.id].UpdatePartialRes(problem)
      else:
         self[problem.id] = problem

   def GetProblemsByType(self, problemType):
      """Returns problems of type problemType from collection.

         Parameters:
            * problemType - Type of problem to be fetched

         Returns:
            * A dict of problems of type problemType
      """
      probs = {}
      for pid, problem in self.items():
         if problem.reltype == problemType:
            probs[pid] = problem
      return probs

   def GetErrorsByComponent(self, comp):
      """Returns errors related to component from collection.

         Parameters:
            * comp - Component for which errors are collected

         Returns:
            * A dict of problems related to comId
      """
      probs = {}
      for pid, problem in self.items():
         if problem.ImpactsComponent(comp.id):
            # A fully obsolete is taken care of automatically,
            # it is not an error.
            if (problem.reltype == problem.TYPE_OBSOLETES and
                problem.isFullObsolete):
               continue

            probs[pid] = problem

      return probs

   def GetFullyObsoletedComps(self):
      """Returns a set of components that are fully obsoleted.
      """
      probs = self.GetProblemsByType(ComponentScanProblem.TYPE_OBSOLETES)
      return set([prob.replacesComp for prob in probs.values()
                  if prob.isFullObsolete])

   def GetErrorsAndWarnings(self):
      """Returns errors and warnings from collection. Complete obsolete
         problems are considered as warnings while the rest are errors.

         Returns:
            * A tuple of errors and warnings dictionary with problem
              id as key and ComponentScanProblem as value.
      """
      errors, warnings = {}, {}
      for pid, problem in self.items():
         if problem.reltype == problem.TYPE_OBSOLETES and \
            problem.isFullObsolete:
            warnings[pid] = problem
         else:
            errors[pid] = problem
      return errors, warnings

   def GetAllRemovedComps(self):
      """Returns a list of all components removed.
      """
      allRemovedComps = set()
      for problem in self.values():
         if problem.isResolved:
            allRemovedComps.update(problem.removedResArgs)
      return allRemovedComps

   def _ToNotificationList(self, problems):
      """Forms notifications from problems and returns them as a list

         Parameters:
            * problems - A dict of problems with problem id as key and
                         ComponentScanProblem as value.

         Returns:
            * A list of problem notification
      """
      notifications = []
      if problems:
         for _, prob in sorted(problems.items()):
            notifications.append(
               prob.GetNotification(self._compUiStrMap).toDict())
      return notifications

   def ToNotificationLists(self):
      """Provides localised message of validate result.
         Returns a tuple of list of error and warning notifications.
         Full obsolete problems are returned as warnings, while others are
         returned as errors.
      """
      errors, warnings = self.GetErrorsAndWarnings()
      warningNotifications = self._ToNotificationList(warnings)
      errorNotifications = self._ToNotificationList(errors)
      return errorNotifications, warningNotifications

   @property
   def isResolved(self):
      for problem in self.values():
         if not problem.isResolved:
            return False
      return True


class ResolutionResult(object):
   """Provides methods to hold resolution results.
      This is necessary to return results to each
      problem in recursive resolution.

      Parameters:
         * components - Components which provide resolution
         * isResolved - Boolean variable which is True
                        when problem is solved, otherwise
                        False
   """
   def __init__(self, addedComps, removedComps, isResolved=False):
      self.addedComps = addedComps
      self.removedComps = removedComps
      self.isResolved = isResolved


def combineComponentScanObject(one, other):
   """Adds two component scan object.

      Parameters:
         * one   - ScanResult object of one component
         * other - ScanResult object of the other component
                   whose relationship information needs to be
                   combined.
      Return:
         * Combined result of two ScanResult objects.
           The relationship information are merged.
   """
   ret = Scan.ScanResult(one.id, one.comptype)

   ret.depends = one.depends.copy()
   for dependencyId, depends in other.depends.items():
      ret.depends.setdefault(dependencyId, set()).update(depends)

   ret.dependedOnBy = one.dependedOnBy.union(other.dependedOnBy)
   ret.replaces = one.replaces.union(other.replaces)
   ret.replacedBy = one.replacedBy.union(other.replacedBy)
   ret.conflicts = one.conflicts.union(other.conflicts)

   return ret


class ComponentScanner(object):
   """Provides the method for establishing relationships between components.

      Parameters:
         * components     - A complete collection of components
         * vibs           - A vib collection object
         * effectiveComps - A collection of effective components
                            on which validate is performed. If not given,
                            validation is performed on complete collection
                            of components

      Attributes:
         * components          - Component collection object on which validate
                                 is performed
         * vibs                - Vibs corresponding to component collection
         * result              - The result obtained after validation
         * componentScanResult - Dict of scan result object involving
                                 component relation
   """
   def __init__(self, components, vibs, effectiveComps=None):
      self.components = components
      self.vibs = components.GetVibCollection(vibs)
      self.effectiveComps = effectiveComps

      # ProblemCollection requires component UI strings to return notifications,
      # keep one instance of global map.
      self._compUiStrMap = components.GetUiStrMap()
      self.result = ProblemCollection(self._compUiStrMap)
      self.componentScanResult = dict()
      # _vibComponentMap is a map of vib ids to their corresponding
      # list of components
      # _vibScanResult is a Dict of scan result object performed on vib
      # finalComps holds list of all installable components including
      # resolution components at any time
      # _obsoleteCountMap is a Dict holding count of number of vibs
      # in a comp obsoleting the other comp
      self._vibComponentMap = dict()
      self._vibScanResult = dict()
      self.finalComps = set()
      self._obsoleteCountMap = dict()

   def _PopulateVibMapping(self):
      """Build vib to component mapping.
      """
      # Populate vib to component map.
      self._vibComponentMap.clear()
      for versionDict in self.components.values():
         for comp in versionDict.values():
            for vib in comp.vibids:
               self._vibComponentMap.setdefault(vib, set()).add(comp.id)

   def _ComponentScan(self):
      """Translates the vib relation to component level.
      """
      for vibId, vibScanRes in self._vibScanResult.items():

         for compId in self._vibComponentMap[vibId]:
            compRelation = Scan.ScanResult(compId,
                                           Scan.ScanResult.TYPE_COMPONENT)

            # Populate conflicts relation
            for conflicts in vibScanRes.conflicts:
               # Condition where conflicting vibs are in same component.
               # Validation will continue ignoring component with conflicting
               # vibs.
               for conflictCompId in self._vibComponentMap[conflicts]:
                  compRelation.conflicts.add(conflictCompId)

            # Populate depends relation
            for dependencyId, depends in vibScanRes.depends.items():
               if not depends:
                  compRelation.depends[dependencyId] = set()
                  continue
               for dId in depends:
                  # Condition where both the vibs are inside same component
                  for depCompId in self._vibComponentMap[dId]:
                     compRelation.depends.setdefault(dependencyId,
                                                     set()).add(depCompId)

            # Populate depended on relation
            for dependedOnBy in vibScanRes.dependedOnBy:
               for depByCompId in self._vibComponentMap[dependedOnBy]:
                  compRelation.dependedOnBy.add(depByCompId)

            # Populate obsoletes relation
            for replaces in vibScanRes.replaces:
               # Condition where obsoleting vib and obsoletedBy vib are inside
               # same component. This appears as a warning in validate result.
               for replaceCompId in self._vibComponentMap[replaces]:
                  compRelation.replaces.add(replaceCompId)
                  # Populate _obsoleteCountMap
                  if compId in self._obsoleteCountMap and \
                     replaceCompId in self._obsoleteCountMap[compId]:
                        self._obsoleteCountMap[compId][replaceCompId] += 1
                  else:
                     self._obsoleteCountMap.setdefault(
                        compId,
                        dict())[replaceCompId] = 1

            # Populate obsoleted relations
            for replacedBy in vibScanRes.replacedBy:
               for replacedByCompId in self._vibComponentMap[replacedBy]:
                  compRelation.replacedBy.add(replacedByCompId)

            # Update ScanResult object of component
            if compId in self.componentScanResult:
               self.componentScanResult[compId] = combineComponentScanObject(
                                            self.componentScanResult[compId],
                                            compRelation)
            else:
               self.componentScanResult[compId] = compRelation

   def _CheckComponentObsolete(self, comp, replacesComp):
      """Checks whether comp obsoletes replacesComp completely.

         Parameters:
            * comp         - Id of component
            * replacesComp - Id of component replaced by comp

         Returns:
            True if all vibs in comp replaces all vibs in replacesComp or
            if remaining vibs which are not obsoleted remains same in
            both components
      """
      comp = self.components.GetComponent(comp)
      replacesComp = self.components.GetComponent(replacesComp)
      if comp.compNameStr == replacesComp.compNameStr:
         return True

      vibs = comp.vibids
      obsoletedVibs = replacesComp.vibids
      totalVibs = vibs | obsoletedVibs
      return (self._obsoleteCountMap[comp.id][replacesComp.id] ==
              len(totalVibs - vibs))

   def _GetAllProblems(self):
      """Collects all unmet dependency, conflict and obsolete problems.
      """
      # Problems are identified in effectiveComps when they are
      # passed. Else, problems are identified for all components in the depot
      components = self.effectiveComps if self.effectiveComps else \
                   self.components

      # First iteration to add all obsolete and conflict problems.
      for versionDict in components.values():
         for comp in versionDict.values():
            compRelation = self.componentScanResult[comp.id]
            # Collect obsolete and self-obsolete problems
            for obsolete in compRelation.replaces:
               if components.HasComponent(obsolete):
                  res = ComponentObsolete(comp.id, obsolete,
                                          self._CheckComponentObsolete(
                                             comp.id,
                                             obsolete))

                  if not self.result.HasProblem(res.id):
                     logger.info('Found problem: %s', str(res))
                     self.result.AddProblem(res)
                     # Discarding these component as it contains problem. At any
                     # time, finalComps will have components with no problem
                     # or with complete resolution
                     self.finalComps.discard(comp.id)
                     self.finalComps.discard(obsolete)

            # Collect conflict and self-conflict problems
            for conflict in compRelation.conflicts:
               if components.HasComponent(conflict):
                  res = ComponentConflict(comp.id, conflict)

                  if not self.result.HasProblem(res.id):
                     logger.info('Found problem: %s', str(res))
                     self.result.AddProblem(res)
                     self.finalComps.discard(comp.id)
                     self.finalComps.discard(conflict)

      # Second iteration to discover unmet dependency problems that arise
      # because the provider in effective components is fully obsoleted.
      # Fully obsoleted components are automatically removed, and thus they
      # cannot be a provider of any dependency.
      fullyObsoletedComps = (self.result.GetFullyObsoletedComps()
                             & set(components.GetComponentIds()))
      for versionDict in components.values():
         for comp in versionDict.values():
            # Collect unmet dependency problems
            compRelation = self.componentScanResult[comp.id]
            for depId, depends in compRelation.depends.items():
               if not depends:
                  res = ComponentUnmetDep(comp.id, depId, [], [])
                  if not self.result.HasProblem(res.id):
                     logger.info('Found problem: %s', str(res))
                     self.result.AddProblem(res)
                     self.finalComps.discard(comp.id)
                  continue
               for dep in depends:
                  if (components.HasComponent(dep)
                      and not dep in fullyObsoletedComps):
                     break
               else:
                  # Dependency is unmet in this case, create a problem and add
                  # it to result.
                  res = ComponentUnmetDep(comp.id, depId, depends,
                                          list(depends & fullyObsoletedComps))
                  if not self.result.HasProblem(res.id):
                     logger.info('Found problem: %s', str(res))
                     self.result.AddProblem(res)
                     self.finalComps.discard(comp.id)


   def _GetHigherVersions(self, compId):
      """Returns the highest version of components from all components

         Parameters:
            * compId - Id of component

         Returns:
            * List of higher versions of compId if found in collection else
              empty
      """
      comp = self.components.GetComponent(compId)
      comps = self.components.GetComponents(name=comp.compNameStr)
      higherComps = sorted([c for c in comps
                            if c.compVersion > comp.compVersion],
                           key=lambda x: x.compVersion)
      return [c.id for c in higherComps]

   def GetFinalComps(self):
      """Returns final list of components after validation and resolution

         Returns:
            * Set of componentIds which work together without problems
              for the given scanner.
      """
      return self.finalComps

   def _UpdateFinalComps(self):
      """Updates final list of components
      """
      # Workable set of components are calculated by collecting all resolved
      # components, all added components for resolution and removing all
      # removed components. This approach is particularly required for cases
      # like chain obsolete where A -o- B -o- C. In this case, final list
      # of components should just have A
      allComps = set()
      allRemovedComps = set()
      for problem in self.result.values():
         if problem.isResolved:
            allComps.add(problem.comp)
            allComps.update(problem.addedResArgs)
            allRemovedComps.update(problem.removedResArgs)
      self.finalComps.update(allComps - allRemovedComps)

   def _ResolveSelfConflictAndSelfObsolete(self, problem, addedResArgs,
                                           removedResArgs):
      """Resolves self-conflict and self-obsolete cases.

         Parameters:
            * problem        - ComponentScanProblem object of type
                               self-conflict or self-obsolete problem
                               object
            * addedResArgs   - Set of components added to resolve this problem
                               from earlier iteration
            * removedResArgs - Set of components removed to resolve this problem
                               from earlier iteration
      """
      removedResArgs.add(problem.comp)
      if self._CheckCompRequired(problem.comp, addedResArgs, removedResArgs):
         # This means problem is found in effective components.
         # Resolution is provided by removing this component only if it's not
         # depended on by any other component. Else validate fails to provide
         # resolution.
         problem.UpdatePartialRes(ResolutionResult(addedResArgs,
                                                   removedResArgs,
                                                   True))
      else:
         # This is hit while recursively resolving other problems.
         # Case where A -> AA -> XX -> PP, PP is a self conflicting or self
         # obsoleting component. Resolution cann't be provided as previous
         # depenedency problem cannot be solved with this component
         problem.UpdatePartialRes(ResolutionResult(addedResArgs,
                                                   removedResArgs,
                                                   False))

   def _Resolve(self, problems, addedResArgs, removedResArgs,
                remainingDepth):
      """Recursively resolves each problem using DFS. For each problem we go
         till constant depth after which resolution stops.

         Parameters:
            * problems       - Dictionary of ComponentScanProblem object
                               addressing problems
            * addedResArgs   - Set of components added to resolve this problem
                               from earlier iteration
            * removedResArgs - Set of components removed to resolve this problem
                               from earlier iteration
            * remainingDepth - The level of remainingDepth while resolving
                               each problem
      """
      for pid, problem in problems.items():
         # If the problem has already been resolved, we can
         # reuse resolution results
         logger.info('Resolving problem: %s', str(problem))
         if self.result.HasProblem(pid):
            actual = self.result[pid]
            if actual and actual.isResolved:
               problem.UpdatePartialRes(ResolutionResult(actual.addedResArgs,
                                                         actual.removedResArgs,
                                                         True))
               continue

         if problem.reltype in (problem.TYPE_SELFOBSOLETE,
                                problem.TYPE_SELFCONFLICT):
            self._ResolveSelfConflictAndSelfObsolete(problem, addedResArgs,
                                                     removedResArgs)

         elif problem.reltype == problem.TYPE_OBSOLETES:
            res = self._ResolveObsolete(problem.comp,
                                        problem.replacesComp,
                                        addedResArgs, removedResArgs,
                                        problem.isFullObsolete,
                                        remainingDepth)
            problem.UpdatePartialRes(res)

         elif problem.reltype == problem.TYPE_CONFLICT:
            res = self._ResolveConflict(problem.comp,
                                        problem.conflictComp,
                                        addedResArgs, removedResArgs,
                                        remainingDepth)
            problem.UpdatePartialRes(res)

         elif problem.reltype == problem.TYPE_DEPENDS:
            res = self._ResolveUnmetDependencies(problem.comp,
                                                 problem.providerCandidates,
                                                 addedResArgs,
                                                 removedResArgs, remainingDepth)
            problem.UpdatePartialRes(res)

   def _GetCurrentEffectiveComps(self, addedResArgs, removedResArgs):
      """Returns effective components computed until this time.

         Parameters:
            * addedResArgs   - Set of added components during resolution
            * removedResArgs - Set of removed components during resolution

         Returns:
            * List of components with no problems
      """
      self._UpdateFinalComps()
      res = self.finalComps | addedResArgs
      return res - removedResArgs

   def _GetProblemsForComp(self, compId, addedResArgs, removedResArgs):
      """Collects problems for given component in relation to itself and
         effecitve component with add/remove adjustments.

         Parameter:
            * compId - Id of the component

         Returns:
            * Dictionary of ComponentScanProblem objects for problems
              introduced by compId
      """
      problems = ProblemCollection(self._compUiStrMap)
      effectivecomps = self._GetCurrentEffectiveComps(addedResArgs,
                                                      removedResArgs)

      compRel = self.componentScanResult[compId]
      # Collecting all conflict problems
      if compRel.conflicts:
         for conflict in compRel.conflicts:
            if conflict == compId or conflict in effectivecomps:
               problems.AddProblem(ComponentConflict(compId, conflict))

      # Collect obsoletes caused by this component.
      fullyObsoletedComps = set()
      if compRel.replaces:
         for rcId in compRel.replaces & effectivecomps:
            fullObsolete = self._CheckComponentObsolete(compId, rcId)
            p = ComponentObsolete(compId, rcId, fullObsolete)
            problems.AddProblem(p)
            if rcId != compId and fullObsolete:
               fullyObsoletedComps.add(rcId)

      # Collecting all unmet dependency problems, including when provier is
      # fully obsoleted by this componet itself. Self-obsolete and partial
      # obsolete are anyway reported as errors and need not to be checked.
      if compRel.depends:
         for dId, depends in compRel.depends.items():
            for dep in depends:
               if dep in effectivecomps and not dep in fullyObsoletedComps:
                  break
            else:
               res = ComponentUnmetDep(compId, dId, depends,
                                       list(depends & fullyObsoletedComps))
               problems.AddProblem(res)

      return problems

   def _CollectResolutions(self, problems):
      """Collects resolution from problems. This is
         needed as providing resolution to one problem can create additional
         problems. We try to provide resolution going 10 levels deep
         for each problem

         Parameters:
            * problems - List of ComponentScanProblem objects

         Returns:
            * A tuple after merging all resolution messages and resolution
              args
      """
      addedResArgs = set()
      removedResArgs = set()
      for problem in problems.values():
         addedResArgs.update(problem.addedResArgs)
         removedResArgs.update(problem.removedResArgs)

      return addedResArgs, removedResArgs

   def _CheckCompRequired(self, compId, addedResArgs, removedResArgs):
      """Checks whether component is depended on by any component from
         final list of components.

         Parameters:
            * compId         - Id of a component
            * addedResArgs   - Set of components added to resolve this
                               problem
            * removedResArgs - Set of components removed to resolve this
                               problem. These are required to judge whether
                               a component is good to be removed. If its
                               depended on by any of the component in the
                               resolution path, it is not recommeded to be
                               removed.

         Returns:
            * True if component is not depended on by any component from
              final list of components, else False
      """
      effectivecomps = self._GetCurrentEffectiveComps(addedResArgs,
                                                      removedResArgs)
      for comp in effectivecomps:
         compRel = self.componentScanResult[comp]
         for depends in compRel.depends.values():
            if compId in depends and comp != compId:
               return False
      return True

   def _GetResolutionResult(self, comp, addedResArgs, removedResArgs,
                            remainingDepth):
      """Collects new problems for component and resolves each problem

         Parameters:
            * comp            - Id of component
            * addedResArgs    - Set of components added to resolve this
                                problem
            * removedResArgs  - Set of components removed to resolve this
                                problem.
            * remainingDepth  - Depth of the resolution.

         Returns:
            * A tuple returning resolution result and a bool which is set to
              True when resolution is found.
      """
      newProblems = self._GetProblemsForComp(comp, addedResArgs, removedResArgs)
      if newProblems:
         logger.info('Finding solution to additional problems for %s', comp)
         # Avoid side-effect in _Resolve, use copy()
         self._Resolve(newProblems, addedResArgs.copy(), removedResArgs.copy(),
                       remainingDepth - 1)
         if newProblems.isResolved:
            logger.info('All new problems are resolved for component %s', comp)
            newAddedResArgs, newRemovedResArgs = \
               self._CollectResolutions(newProblems)
            if not comp in newRemovedResArgs:
               # Reject self-conflicting resolution, i.e. add and then remove
               # the component we are trying to resolve new problems for.
               return True, ResolutionResult(newAddedResArgs, newRemovedResArgs,
                                             True)
         logger.info('Resolution not found for problems to component %s', comp)
         return False, ResolutionResult(addedResArgs, removedResArgs, False)
      else:
         return True, ResolutionResult(addedResArgs, removedResArgs, True)

   def _TryAddHigherVerComp(self, comp, relComp, addedResArgs, removedResArgs,
                            remainingDepth, compRole):
      """Checks whether a conflict/obsolete can be resolved by considering
         higher versions of conflicting component.

         Parameters:
            * comp           - Id of component
            * relComp        - Id of component having relation with comp
            * addedResArgs   - Set of components added to resolve this
                               problem
            * removedResArgs - Set of components removed to resolve this
                               problem.
            * remainingDepth - Depth of the resolution.
            * compRole       - Role of comp. It can either be
                               ROLE_CONFLICT_COMP, ROLE_REPLACES_COMP or
                               ROLE_REPLACED_BY_COMP

         Returns:
            * A tuple returning resolution result and a bool which is set to
              True when resolution is found.
      """
      nextComps = self._GetHigherVersions(comp)
      if nextComps:
         for nextComp in nextComps:
            foundRes = False
            if compRole == ROLE_CONFLICT_COMP:
               if not relComp in self.componentScanResult[nextComp].conflicts:
                  logger.info('Conflict between %s and %s resolved by adding'
                              ' %s', comp, relComp, nextComp)
                  foundRes = True

            elif compRole == ROLE_REPLACES_COMP:
               if not nextComp in self.componentScanResult[relComp].replaces:
                  logger.info('Obsolescence between %s and %s resolved by'
                              ' adding %s', relComp, comp, nextComp)
                  foundRes = True

            elif compRole == ROLE_REPLACED_BY_COMP:
               if not relComp in self.componentScanResult[nextComp].replaces:
                  logger.info('Obsolescence between %s and %s resolved by'
                              ' adding %s', comp, relComp, nextComp)
                  foundRes = True

            if foundRes:
               addedResArgs.add(nextComp)
               addedResArgs.add(relComp)
               removedResArgs.add(comp)
               # If its already present in finalComps, resolution has
               # been provided to all problems from this component. Hence
               # resolving this issue
               self._UpdateFinalComps()
               if nextComp in self.finalComps:
                  return True, ResolutionResult(addedResArgs,
                                                removedResArgs, True)
               else:
                  # Adding this as part of resolution can bring in some more
                  # problems. Collect all new problems and recursively resolve
                  # them.
                  isResolved, res = self._GetResolutionResult(nextComp,
                                                              addedResArgs,
                                                              removedResArgs,
                                                              remainingDepth)
                  if isResolved:
                     return True, res

      logger.info('Higher versions of %s didn\'t resolve the problem', comp)
      return False, ResolutionResult(addedResArgs, removedResArgs, False)

   def _TryHigherVerPairs(self, comp, relComp, addedResArgs, removedResArgs,
                          remainingDepth, isObsoleteProblem=False):
      """Checks whether a conflict/oblescence can be resolved by considering
         higher versions of both components.

         Parameters:
            * comp              - Id of component
            * relComp           - Id of component in relation with comp
            * addedResArgs      - Set of components added to resolve this
                                  problem
            * removedResArgs    - Set of components removed to resolve this
                                  problem.
            * remainingDepth    - Depth of the resolution.
            * isObsoleteProblem - True if the problem is an obsolete problem,
                                  False when it is a conflict problem

         Returns:
            * A tuple returning resolution result and a bool which is set
              to True when resolution is found.
      """
      nextComps = self._GetHigherVersions(comp)
      nextRelComps = self._GetHigherVersions(relComp)
      if nextComps and nextRelComps:
         for nextComp in nextComps:
            for nextRelComp in nextRelComps:
               foundRes = False
               # Prechecking this pair of component does not have the same
               # issue.
               if isObsoleteProblem:
                  if not nextRelComp in \
                     self.componentScanResult[nextComp].replaces:
                     logger.info('Obsolescence between %s and %s resolved by'
                                 ' adding %s, %s', comp, relComp, nextComp,
                                 nextRelComp)
                     foundRes = True
               else:
                  if not nextComp in \
                     self.componentScanResult[nextRelComp].conflicts:
                     logger.info('Conflict between %s and %s resolved by'
                                 ' adding %s, %s', comp, relComp, nextComp,
                                 nextRelComp)
                     foundRes = True

               if foundRes:
                  addedResArgs.add(nextComp)
                  addedResArgs.add(nextRelComp)
                  removedResArgs.add(comp)
                  removedResArgs.add(relComp)
                  self._UpdateFinalComps()
                  if nextComp in self.finalComps and nextRelComp \
                     in self.finalComps:
                     return True, ResolutionResult(addedResArgs,
                                                   removedResArgs, True)
                  else:
                     isResolved, res = self._GetResolutionResult(nextComp,
                                                                 addedResArgs,
                                                                 removedResArgs,
                                                                 remainingDepth)
                     if isResolved:
                        addedResArgs.update(res.addedComps)
                        removedResArgs.update(res.removedComps)
                        isResolved, res = self._GetResolutionResult(
                                             nextRelComp,
                                             addedResArgs,
                                             removedResArgs,
                                             remainingDepth)
                        if isResolved:
                           logger.info('Higher version components %s and %s '
                                       'resolve the problem.', nextComp,
                                       nextRelComp)
                           return True, res

      logger.info('Higher versions of %s and %s didn\'t resolve the problem',
                  comp, relComp)
      return False, ResolutionResult(addedResArgs, removedResArgs, False)

   def _ResolveObsolete(self, comp, replacesComp, addedResArgs, removedResArgs,
                        isFullyObsolete, remainingDepth):
      """Resolves obsolete for given component collection.
         Obsolete resolution happens in following ways.
         1. Remove component if it is completely obsoleted by another component
         2. Remove either one of the components. Component not depended on by
            other components in effective components will be chosen
         3. Check whether higher version of one component solves obsolescence
         4. Check whether higher versions of both components resolve
            obsolescence

         Parameters:
            * comp            - Id of component
            * replacesComp    - Id of component replaced by comp
            * addedResArgs    - Set of components added to resolve this problem
            * removedResArgs  - Set of components removed to resolve this
                                problem.
            * isFullyObsolete - True when comp truly replaces replacesComp,
                                otherwise False
            * remainingDepth  - Depth of the resolution. If this is 0, further
                                resolution will not be provided

         Returns:
            * A ResolutionResult object for this particular problem
      """
      if remainingDepth == 0:
         return ResolutionResult(addedResArgs, removedResArgs, False)

      # Cycle is detected when replacesComp is already present in effective
      # components
      if replacesComp in self._GetCurrentEffectiveComps(addedResArgs,
                                                        removedResArgs):
         logger.info('Remove %s to resolve obsolescence between %s and %s',
                     comp, comp, replacesComp)
         removedResArgs.add(comp)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      # Remove obsoleted component in case of fully obsolete.
      if isFullyObsolete:
         logger.info('Remove %s to resolve obsolescence between %s and %s',
                     replacesComp, comp, replacesComp)
         removedResArgs.add(replacesComp)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      # Try higher versions of replacesComp
      isResolved, res = self._TryAddHigherVerComp(replacesComp, comp,
                                                  addedResArgs,
                                                  removedResArgs,
                                                  remainingDepth,
                                                  ROLE_REPLACES_COMP)
      if isResolved:
         return res

      # Try higher versions of comp
      isResolved, res = self._TryAddHigherVerComp(comp, replacesComp,
                                                  addedResArgs,
                                                  removedResArgs,
                                                  remainingDepth,
                                                  ROLE_REPLACED_BY_COMP)
      if isResolved:
         return res

      # Try higher version pairs
      isResolved, res = self._TryHigherVerPairs(comp, replacesComp,
                                                addedResArgs, removedResArgs,
                                                remainingDepth, True)
      if isResolved:
         return res

      # Consider removing replacesComp
      if self._CheckCompRequired(replacesComp, addedResArgs, removedResArgs):
         logger.info('Remove %s to resolve obsolescence between %s and %s',
                     replacesComp, comp, replacesComp)
         removedResArgs.add(replacesComp)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      # Consider removing comp.
      if self._CheckCompRequired(comp, addedResArgs, removedResArgs):
         logger.info('Remove %s to resolve obsolescence between %s and %s',
                     comp, comp, replacesComp)
         addedResArgs.add(replacesComp)
         removedResArgs.add(comp)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      # No resolution found to this problem
      logger.info('Failed to provide resolution to obsolescence between %s'
                  ' and %s', comp, replacesComp)
      return ResolutionResult(addedResArgs, removedResArgs, False)

   def _ResolveConflict(self, comp, conflictingComp, addedResArgs,
                        removedResArgs, remainingDepth):
      """Resolve conflicts for given component collection.
         There are 3 possibilities to resolve conflicts.
         1. Check whether higher version of one component solves conflict
         2. Check whether higher versions of both components resolves conflict
         3. Remove anyone of the component. Component not depended on by
            either of the components in effective components will be chosen

         Parameters:
            * comp            - Id of component
            * conflictingComp - Id of component conflicting comp
            * addedResArgs    - Set of components added to resolve this problem
            * removedResArgs  - Set of components removed to resolve this
                                problem.
            * remainingDepth  - Depth of the resolution. If this is 0, further
                                resolution will not be provided

         Returns:
            * A ResolutionResult object for this particular conflict
      """
      if remainingDepth == 0:
         return ResolutionResult(addedResArgs, removedResArgs, False)

      # Considering higher versions of comp
      isResolved, res = self._TryAddHigherVerComp(comp, conflictingComp,
                                                  addedResArgs,
                                                  removedResArgs,
                                                  remainingDepth,
                                                  ROLE_CONFLICT_COMP)
      if isResolved:
         return res

      # Considering higher version of conflictingComp
      isResolved, res = self._TryAddHigherVerComp(conflictingComp, comp,
                                                  addedResArgs,
                                                  removedResArgs,
                                                  remainingDepth,
                                                  ROLE_CONFLICT_COMP)
      if isResolved:
         return res

      # Considering higher version of both components, comp, conflictingComp
      isResolved, res = self._TryHigherVerPairs(comp, conflictingComp,
                                                addedResArgs, removedResArgs,
                                                remainingDepth)
      if isResolved:
         return res

      # Considering removing either comp or conflictingComp. Removing a
      # component can create additional problems. This might unsatisfy any
      # dependency problem solved before. We will remove those which don't give
      # raise to additional problems. If both gives rise to problems, then
      # resolution could not be provided to this conflict
      if self._CheckCompRequired(comp, addedResArgs, removedResArgs):
         logger.info('Remove %s to resolve conflict between %s and %s',
                     comp, comp, conflictingComp)
         addedResArgs.add(conflictingComp)
         removedResArgs.add(comp)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      elif self._CheckCompRequired(conflictingComp, addedResArgs,
                                   removedResArgs):
         logger.info('Remove %s to resolve conflict between %s and %s',
                     conflictingComp, comp, conflictingComp)
         addedResArgs.add(comp)
         removedResArgs.add(conflictingComp)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      # No resolution found to this problem
      logger.info('Failed to provide resolution to conflict between %s and %s',
                  comp, conflictingComp)
      return ResolutionResult(addedResArgs, removedResArgs, False)

   def _ConflictsWithEffComps(self, comp, effectivecomps):
      """Checks whether component conflicts with any components in the effective
         components.

         Parameters:
            * comp           - Component Id
            * effectivecomps - List of componentIds which is a part of final
                               components.

         Returns:
            * True if components conflicts with any of the component in
              effective components. Else False.
      """
      compRel = self.componentScanResult[comp]
      for conflict in compRel.conflicts:
         if conflict in effectivecomps:
            return True
      return False

   def _ResolveUnmetDependencies(self, compId, candidateComps, addedResArgs,
                                 removedResArgs, remainingDepth):
      """Resolves unmet dependencies for given component collection

         Parameters:
            * compId         - ComponentId with unmet dependency problem
            * candidateComps - List of componentIds which can satisfy unmet
                               dependency
            * addedResArgs   - Set of components added to resolve this problem
            * removedResArgs - Set of components removed to resolve this
                               problem.
            * remainingDepth - Depth of the resolution. If this is 0, further
                               resoluion will not be provided
         Returns:
            * A ResolutionResult object for this particular conflict
      """
      if not candidateComps or remainingDepth == 0:
         return ResolutionResult(addedResArgs, removedResArgs, False)

      effectivecomps = self._GetCurrentEffectiveComps(addedResArgs,
                                                      removedResArgs)

      # If the component is being removed, i.e. as part of an obsolete/conflict
      # problem, simply also remove it to resolve the issue
      if compId in self.result.GetAllRemovedComps():
         logger.info('Remove %s to resolve unmet dependency problem of %s',
                     compId, compId)
         removedResArgs.add(compId)
         return ResolutionResult(addedResArgs, removedResArgs, True)

      # If a component is in final components, then it is chosen
      # as a resolution.
      for comp in candidateComps:
         if comp in effectivecomps:
            return ResolutionResult(addedResArgs, removedResArgs, True)

      # Try adding a candidate to resolve unmet dependency
      for comp in candidateComps:
         if self._ConflictsWithEffComps(comp, effectivecomps):
            logger.info('%s conflicts with effective components', comp)
            continue
         addedResArgs.add(comp)
         addedResArgs.add(compId)

         newProblems = self._GetProblemsForComp(comp, addedResArgs,
                                                removedResArgs)
         logger.info('Adding %s to resolve unmet depedency problem of %s',
                     comp, compId)
         if newProblems:
            # Avoid side-effect in _Resolve, use copy().
            self._Resolve(newProblems, addedResArgs.copy(),
                          removedResArgs.copy(),
                          remainingDepth - 1)
            if newProblems.isResolved:
               newAddedResArgs, newRemovedResArgs = \
                  self._CollectResolutions(newProblems)
               if not comp in newRemovedResArgs:
                  # Reject self-conflicting resolution, i.e. add and then remove
                  # the component we are trying to resolve new problems for.
                  return ResolutionResult(newAddedResArgs, newRemovedResArgs,
                                          True)
            logger.info('%s couldn\'t resolve unmet dependency problem for '
                        '%s', comp, compId)
            addedResArgs.remove(comp)
            addedResArgs.add(compId)
         else:
            return ResolutionResult(addedResArgs, removedResArgs, True)

      logger.info('Failed to provide resolution to %s', compId)
      return ResolutionResult(addedResArgs, removedResArgs, False)

   def _AdjustFinalComps(self, problem):
      """In case of obsolete and conflict problems, both components will not
         be in final list of components before problem resolution.
         This method moves the problem component from added components to the
         final components.
         This method adjust the final components by adding the added components
         and remove removed components to properly refect either resolved and
         unresolved obsolete/conflict problems.
      """
      if problem.reltype in (problem.TYPE_OBSOLETES, problem.TYPE_CONFLICT):
         # Copy to be able to modify.
         for compId in problem.addedResArgs.copy():
            if problem.ImpactsComponent(compId):
               # A component in the pair is being added back.
               problem.addedResArgs.remove(compId)
               self.finalComps.add(compId)
      self.finalComps -= self.result.GetAllRemovedComps()

   def Validate(self):
      """Validates a final component collection to be applied,
         returns a result object that contain problems and resolutions.

         Return:
            * A ProblemCollection object containing ComponentScanProblem
              object having problem and resolution
      """
      # Populate vib to component mapping
      self._PopulateVibMapping()

      # Populate scan result for each vib
      scanner = Scan.VibScanner()
      scanner.Scan(self.vibs)
      self._vibScanResult = scanner.results
      # Removing esximage library version from vib scan data.
      del self._vibScanResult['installer:esximage']

      # Convert the vib level relations to component level.
      self._ComponentScan()
      for compId, compRelation in self.componentScanResult.items():
         for dId, depends in compRelation.depends.items():
            logger.info('Component %s requires %s provided by %s',
                        compId, dId, '/ '.join(depends))
         if compRelation.replaces:
            logger.info('Component %s replaces %s',
                        compId, ', '.join(compRelation.replaces))
         if compRelation.conflicts:
            logger.info('Component %s conflicts %s',
                        compId, ', '.join(compRelation.conflicts))

      # Get all problems
      if self.effectiveComps:
         logger.info('Effective components: %s',
                     self.effectiveComps.GetComponentIds())
         self.finalComps = set(self.effectiveComps.GetComponentIds())
      else:
         logger.info('Effective components are not provided.')
         self.finalComps = set(self.components.GetComponentIds())
      self._GetAllProblems()
      for pId, problem in self.result.items():
         logger.info('Found %s: %s', pId, problem.msg)

      # Resolve problems. We resolve obsolete problems first followed by
      # conflict and then depends.

      # Resolve obsolete problems
      obsoleteProbs = self.result.GetProblemsByType(
                         ComponentScanProblem.TYPE_OBSOLETES)
      obsoleteProbs.update(self.result.GetProblemsByType(
                              ComponentScanProblem.TYPE_SELFOBSOLETE))
      for pid, problem in sorted(obsoleteProbs.items()):
         self._Resolve({pid: problem}, set(), set(), RESOLUTION_DEPTH)
         self._AdjustFinalComps(problem)

      # Resolve conflict problems
      conflictProbs = self.result.GetProblemsByType(
                         ComponentScanProblem.TYPE_CONFLICT)
      conflictProbs.update(self.result.GetProblemsByType(
                              ComponentScanProblem.TYPE_SELFCONFLICT))
      for pid, problem in sorted(conflictProbs.items()):
         self._Resolve({pid: problem}, set(), set(), RESOLUTION_DEPTH)
         self._AdjustFinalComps(problem)

      # Resolve unmetdependency problems
      dependsProbs = self.result.GetProblemsByType(
                        ComponentScanProblem.TYPE_DEPENDS)
      for pid, problem in sorted(dependsProbs.items()):
         self._Resolve({pid: problem}, set(), set(), RESOLUTION_DEPTH)
         if problem.comp in problem.addedResArgs:
            problem.addedResArgs.remove(problem.comp)

      self._UpdateFinalComps()

      return self.result
