from Logger import Logger from constants import constants from sets import Set import copy def removeDuplicateEntriesInList(myList): myListCopy=[] for p in myList: if p not in myListCopy: myListCopy.append(p) return myListCopy class PackageBuildDataGenerator(object): cycleCount=0 def __init__(self,logName=None,logPath=None): if logName is None: logName = "PackageBuildDataGenerator" if logPath is None: logPath = constants.logPath self.logName=logName self.logPath=logPath self.logger=Logger.getLogger(logName,logPath) self.__mapCyclesToPackageList={} self.__mapPackageToCycle={} self.__buildDependencyGraph={} self.__runTimeDependencyGraph={} self.__sortedPackageList=[] self.__sortedBuildDependencyGraph={} def getPackageBuildData(self,listPackages): self.__readDependencyGraphAndCyclesForGivenPackages(listPackages) self.__getSortedBuildOrderListForGivenPackages(listPackages) return self.__mapCyclesToPackageList, self.__mapPackageToCycle, self.__sortedPackageList #todo def findCompleteListOfPackagesRequiredToBuildGivenPackages(self,listPackages): return self.__buildDependencyGraph.keys() def createSortListForPkg(self,pkg): runTimeDepPkgList=self.__runTimeDependencyGraph[pkg] runTimeDepPkgList.append(pkg) sortListForPkg=[] for p in runTimeDepPkgList: basePkg=constants.specData.getSpecName(p) for bPkg in self.__sortedBuildDependencyGraph[basePkg]: if bPkg not in sortListForPkg: sortListForPkg.append(bPkg) return sortListForPkg def getCircularDependentPackages(self,pkg): circularDependentPackages=[] if self.__mapPackageToCycle.has_key(pkg): circularDependentPackages.extend(self.__mapCyclesToPackageList[self.__mapPackageToCycle[pkg]]) circularDependentPackages.remove(pkg) return circularDependentPackages def __getSortedBuildOrderListForGivenPackages(self,listPackages): alreadyProcessedPackages=[] sortedList=[] completeListPackagesToBuild=self.findCompleteListOfPackagesRequiredToBuildGivenPackages(listPackages) packageIndexInSortedList = 0 prevSortListLen=0 while completeListPackagesToBuild: # find next package to process pkg=None index=-1 lenList=len(sortedList) for i in range(lenList): if sortedList[i] in alreadyProcessedPackages: continue pkg = sortedList[i] packageIndexInSortedList = i break if pkg is None: pkg = completeListPackagesToBuild.pop() packageIndexInSortedList = len(sortedList) #creating sort list for package sortListForPkg=self.createSortListForPkg(pkg) #remove any cyclic packages in sortListForPkg if they already exists in sortedList circularDependentPackages=self.getCircularDependentPackages(pkg) for p in circularDependentPackages: if p in sortedList and p in sortListForPkg: sortListForPkg.remove(p) # insert sort list of package in global sorted list index=packageIndexInSortedList subList=[] if packageIndexInSortedList > 0: subList=sortedList[:packageIndexInSortedList] for p in sortListForPkg: if p not in subList: sortedList.insert(index, p) index = index + 1 alreadyProcessedPackages.append(p) # Remove duplicate entries in sorted list in intervals if (len(sortedList)-prevSortListLen) > 100 : self.logger.info("Removing duplicates in sortedList") sortedList = removeDuplicateEntriesInList(sortedList) else: prevSortListLen=len(sortedList) self.logger.info("Removing duplicates in sorted list") sortedList = removeDuplicateEntriesInList(sortedList) self.logger.info("Sorted list:") self.logger.info(sortedList) self.__sortedPackageList=sortedList def __constructBuildAndRunTimeDependencyGraph(self,package): basePackage=constants.specData.getSpecName(package) addBuildTimeGraph=True addRunTimeGraph=True if self.__buildDependencyGraph.has_key(basePackage): addBuildTimeGraph = False if self.__runTimeDependencyGraph.has_key(basePackage): addRunTimeGraph=False nextPackagesToConstructGraph=[] if addBuildTimeGraph: listDependentRpmPackages=constants.specData.getBuildRequiresForPackage(basePackage) listDependentPackages=[] for rpmPkg in listDependentRpmPackages: basePkg=constants.specData.getSpecName(rpmPkg) if basePkg not in listDependentPackages: listDependentPackages.append(basePkg) self.__buildDependencyGraph[basePackage]=listDependentPackages nextPackagesToConstructGraph.extend(listDependentPackages) if addRunTimeGraph: listRpmPackages=constants.specData.getPackages(basePackage) for rpmPkg in listRpmPackages: listDependentRpmPackages=constants.specData.getRequiresAllForPackage(rpmPkg) self.__runTimeDependencyGraph[rpmPkg]=listDependentRpmPackages[:] nextPackagesToConstructGraph.extend(listDependentRpmPackages) for pkg in nextPackagesToConstructGraph: self.__constructBuildAndRunTimeDependencyGraph(pkg) def __readDependencyGraphAndCyclesForGivenPackages(self,listPackages): self.logger.info("Reading dependency graph to check for cycles") for pkg in listPackages: self.__constructBuildAndRunTimeDependencyGraph(pkg) packagesToBUild=self.__buildDependencyGraph.keys() for pkg in packagesToBUild: sortedPackageList,circularDependentPackages = self.topologicalSortPackages(self.__buildDependencyGraph,pkg) if len(circularDependentPackages) > 0 : self.logger.error("Found circular dependency") self.logger.error(circularDependentPackages) raise Exception("Build Time Circular Dependency") self.__sortedBuildDependencyGraph[pkg]=sortedPackageList sortedPackageList,circularDependentPackages = self.topologicalSortPackages(self.__runTimeDependencyGraph) if len(circularDependentPackages) > 0 : self.__findCircularDependencies(circularDependentPackages) def topologicalSortPackages(self, dependencyGraph, package=None): noDepPackages = Set() sortedPackageList = [] dependentOfPackage = dict() dependentPackages={} if package is None: dependentPackages=copy.deepcopy(dependencyGraph) else: listDepPkgs= Set() listDepPkgs.add(package) while listDepPkgs: pkg = listDepPkgs.pop() if dependentPackages.has_key(pkg): continue dependentPackages[pkg]=dependencyGraph[pkg][:] for depPkg in dependencyGraph[pkg]: listDepPkgs.add(depPkg) #Find packages with no dependencies and generate dependentof_package edge list for pkg in dependentPackages: if len(dependentPackages[pkg]) == 0: noDepPackages.add(pkg) else: for depPkg in dependentPackages[pkg]: if not dependentOfPackage.has_key(depPkg): dependentOfPackage[depPkg]=[pkg] else: if pkg not in dependentOfPackage[depPkg]: dependentOfPackage[depPkg].append(pkg) while noDepPackages: pkg = noDepPackages.pop() sortedPackageList.append(pkg) if dependentOfPackage.get(pkg) is not None: for childPkg in list(dependentOfPackage.get(pkg)): dependentOfPackage.get(pkg).remove(childPkg) dependentPackages[childPkg].remove(pkg) if len(dependentPackages[childPkg])==0: noDepPackages.add(childPkg) # creating circular dependency graph for given dependency graph circularDependencyGraph={} listCircularPkg = dependentPackages.keys() for pkg in listCircularPkg: if len(dependentPackages[pkg]) != 0: circularDependencyGraph[pkg]=dependentPackages[pkg] #return (non-circular dependent package in sorted order and circular dependent package list in a dependencyGraph) return sortedPackageList,circularDependencyGraph def __constructDependencyMap(self,cyclicDependencyGraph): self.logger.info("Constructing dependency map from circular dependency graph.....") constructDependencyMap={} listNodes=cyclicDependencyGraph.keys() for node in listNodes: tmpDepNodeList=[] tmpDepNodeList.append(node) depNodeList=[] while len(tmpDepNodeList)!=0: currentNode = tmpDepNodeList.pop() addDepNodeList = cyclicDependencyGraph[currentNode] depNodeList.append(currentNode) for depNode in addDepNodeList: if depNode in depNodeList: continue else: if depNode not in tmpDepNodeList: tmpDepNodeList.append(depNode) depNodeList.remove(node) constructDependencyMap[node]=depNodeList self.logger.info("Dependency Map:") self.logger.info(constructDependencyMap) return constructDependencyMap def __findCircularDependencies(self,cyclicDependencyGraph): self.logger.info("Looking for circular dependencies") if len(cyclicDependencyGraph) == 0: return #step1: construct dependency map from dependency graph constructDependencyMap=self.__constructDependencyMap(cyclicDependencyGraph) #step2: find cycles in dependency map self.logger.info("Finding and adding cycles using constructed dependency map......") cycleCount=0 listNodes=cyclicDependencyGraph.keys() for node in listNodes: listDepPkg=constructDependencyMap[node] cycPkgs=[] if not self.__mapPackageToCycle.has_key(node): for depPkg in listDepPkg: x = constructDependencyMap[depPkg] if node in x: cycPkgs.append(depPkg) if len(cycPkgs) != 0: cycPkgs.append(node) cycleName="cycle"+str(PackageBuildDataGenerator.cycleCount) PackageBuildDataGenerator.cycleCount=PackageBuildDataGenerator.cycleCount+1 for x in cycPkgs: self.__mapPackageToCycle[x]=cycleName self.__mapCyclesToPackageList[cycleName]=cycPkgs self.logger.info("New circular dependency found:") self.logger.info(cycleName+" "+ ",".join(cycPkgs)) cycleCount = cycleCount + 1 if cycleCount > 0 : self.logger.info("Found "+str(cycleCount) + " cycles.") self.logger.info("Successfully added all detected circular dependencies to list.") else: self.logger.info("No circular dependencies found.")