import copy
from Logger import Logger
from constants import constants
from SpecData import SPECS
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 list(self.__buildDependencyGraph.keys())
def createSortListForPkg(self, pkg):
runTimeDepPkgList = self.__runTimeDependencyGraph[pkg]
runTimeDepPkgList.append(pkg)
sortListForPkg = []
for p in runTimeDepPkgList:
basePkg = SPECS.getData().getSpecName(p)
for bPkg in self.__sortedBuildDependencyGraph[basePkg]:
if bPkg not in sortListForPkg:
sortListForPkg.append(bPkg)
return sortListForPkg
def getCircularDependentPackages(self, pkg):
circularDependentPackages = []
if pkg in self.__mapPackageToCycle:
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 = SPECS.getData().getSpecName(package)
addBuildTimeGraph = True
addRunTimeGraph = True
if basePackage in self.__buildDependencyGraph:
addBuildTimeGraph = False
if basePackage in self.__runTimeDependencyGraph:
addRunTimeGraph = False
nextPackagesToConstructGraph = []
if addBuildTimeGraph:
listDependentRpmPackages = SPECS.getData().getBuildRequiresForPackage(basePackage)
listDependentPackages = []
for rpmPkg in listDependentRpmPackages:
basePkg = SPECS.getData().getSpecName(rpmPkg)
if basePkg not in listDependentPackages:
listDependentPackages.append(basePkg)
self.__buildDependencyGraph[basePackage] = listDependentPackages
nextPackagesToConstructGraph.extend(listDependentPackages)
if addRunTimeGraph:
listRpmPackages = SPECS.getData().getPackages(basePackage)
for rpmPkg in listRpmPackages:
listDependentRpmPackages = SPECS.getData().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)
for pkg in self.__buildDependencyGraph.keys():
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 pkg in dependentPackages:
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 depPkg not in dependentOfPackage:
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 = {}
for pkg in dependentPackages.keys():
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, yclicDependencyGraph):
self.logger.info("Constructing dependency map from circular dependency graph.....")
constructDependencyMap = {}
for node in cyclicDependencyGraph.keys():
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
for node in cyclicDependencyGraph.keys():
listDepPkg = constructDependencyMap[node]
cycPkgs = []
if node not in self.__mapPackageToCycle:
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 += 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 += 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.")