###################################################################### # 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 class ComponentScanProblem(object): """Structure to hold scan result information. Attributes: * id - Problem id of the form type:compId * msg - Problem text explaining the condition. * reltype - Type of relation of the problem. * resArgs - List of resolution arguments * 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 _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 GetResolutionMsg(self): """Returns resolution message to problem. """ #TO-DO: Include source of resolution components if self.isResolved: if self.reltype == self.TYPE_SELFCONFLICT: return self.SELF_CONFLICT_RES_MSG % {'comp': self.comp} elif self.reltype == self.TYPE_SELFOBSOLETE: return self.SELF_OBSOLETE_RES_MSG % {'comp': self.comp} elif self.addedResArgs and self.removedResArgs: return self.ADD_REMOVE_RES_MSG % { 'addComps': ', '.join(self.addedResArgs), 'removeComps': ', '.join(self.removedResArgs)} elif self.addedResArgs: return self.ADD_RES_MSG % { 'addComps': ', '.join(self.addedResArgs)} elif self.removedResArgs: return self.REMOVE_RES_MSG % { 'removeComps': ', '.join(self.removedResArgs)} else: return self.NO_RES_MSG % {'comp': self.comp} @property def resArgs(self): if self.isResolved: if self.reltype in (self.TYPE_SELFCONFLICT, self.TYPE_SELFOBSOLETE): return [self.comp] elif self.addedResArgs and self.removedResArgs: return [', '.join(sorted(self.addedResArgs)), ', '.join(sorted(self.removedResArgs))] elif self.addedResArgs: return [', '.join(sorted(self.addedResArgs))] elif self.removedResArgs: return [', '.join(sorted(self.removedResArgs))] else: return [self.comp] @property def resMsg(self): if self.isResolved: if self.reltype == self.TYPE_SELFCONFLICT: return self.SELF_CONFLICT_RES_NTFN_MSG elif self.reltype == self.TYPE_SELFOBSOLETE: return self.SELF_OBSOLETE_RES_NTFN_MSG elif self.addedResArgs and self.removedResArgs: return self.ADD_REMOVE_RES_NTFN_MSG elif self.addedResArgs: return self.ADD_RES_NTFN_MSG elif self.removedResArgs: return self.REMOVE_RES_NTFN_MSG else: return self.NO_RES_NTFN_MSG @property def resId(self): if self.isResolved: if self.reltype == self.TYPE_SELFCONFLICT: return self.SELF_CONFLICT_RES_ID elif self.reltype == self.TYPE_SELFOBSOLETE: return self.SELF_OBSOLETE_RES_ID elif self.addedResArgs and self.removedResArgs: return self.ADD_REMOVE_RES_ID elif self.addedResArgs: return self.ADD_RES_ID elif self.removedResArgs: return self.REMOVE_RES_ID else: return self.NO_RES_ID 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 * msgArgs - List of problem arguments """ 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, we need to check #both components to decide whether the problem is same or not #Hence we sort components. 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): #Since conflicts are bi-directional, we need to check #both components to decide whether the problem is same or not return self.reltype == other.reltype and self.comp == other.comp \ and self.conflictComp == other.conflictComp @property def msgArgs(self): """Returns message arguments to be used in a notification message to VC. Conflict problem returns pair of components which conflict each other. """ if self.reltype == self.TYPE_SELFCONFLICT: return [self.comp] else: return [self.comp, self.conflictComp] @property def id(self): return self.reltype + '_' + self.comp + '_' + self.conflictComp @property def notificationMsg(self): if self.reltype == self.TYPE_SELFCONFLICT: return self.SELF_CONFLICT_NTFN_MSG else: return self.CONFLICT_NTFN_MSG @property def msgId(self): if self.reltype == self.TYPE_SELFCONFLICT: return VALIDATE_PREFIX + 'SelfConflict' else: return VALIDATE_PREFIX + 'Conflict' 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 * msgArgs - List of problem arguments """ 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 msgArgs(self): """Returns message arguments to be used in a notification message to VC. Obsoletes problem returns pair of components where a component obsoletes other. """ if self.reltype == self.TYPE_SELFOBSOLETE: return [self.comp] else: return [self.comp, self.replacesComp] @property def id(self): return self.reltype + '_' + self.comp + '_' + self.replacesComp @property def notificationMsg(self): if self.reltype == self.TYPE_SELFOBSOLETE: return self.SELF_OBSOLETE_NTFN_MSG else: return self.OBSOLETE_NTFN_MSG @property def msgId(self): if self.reltype == self.TYPE_SELFOBSOLETE: return VALIDATE_PREFIX + 'SelfObsolete' else: return VALIDATE_PREFIX + 'Obsolete' 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. * msgArgs - List of problem arguments. """ 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 msgArgs(self): """Returns message arguments to be used in a notification message to VC. UnmetDependency problem returns the issue compoment and then depending on the scan result: its depended on components, obsoleted providing components, or the dependency for which no provider exists. """ if self.providerCandidates: return [self.comp, ', '.join(sorted(self.providerCandidates))] elif self.obsoletedProviders: return [self.comp, self.did, ', '.join(sorted(self.obsoletedProviders))] else: return [self.comp, self.did] @property def id(self): return self.reltype + '_' + self.comp + '_' + self.did @property def notificationMsg(self): if self.providerCandidates: return self.UNMET_DEPENDENCY_NTFN_MSG elif self.obsoletedProviders: return self.UNMET_DEPENDENCY_PROVIDER_OBSOLETED_NTFN_MSG else: return self.UNMET_DEPENDENCY_NO_PROVIDES_NTFN @property def msgId(self): if self.providerCandidates: return VALIDATE_PREFIX + 'Depend' elif self.obsoletedProviders: return VALIDATE_PREFIX + 'ProviderComponentObsoleted' else: return VALIDATE_PREFIX + 'MissingProvidingComponent' class ProblemCollection(dict): """Provides methods to perform operations on validation scan result. """ 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 comp.id in problem.msgArgs: # 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: * 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(Notification(prob.msgId, prob.msgId, prob.notificationMsg, prob.resId, prob.resMsg, prob.msgArgs, prob.resArgs ).toDict()) return notifications def ToNotificationLists(self): """Provides localised message of validate result Returns: * A tuple of list of error and warning notifications. Truly obsolete problems are returned as warning notifications 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 self.result = ProblemCollection() 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() 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 == problem.TYPE_OBSOLETES or \ problem.reltype == problem.TYPE_CONFLICT: for args in problem.msgArgs: if args in problem.addedResArgs: problem.addedResArgs.remove(args) self.finalComps.add(args) 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