1# -*- coding: utf-8 -*- 2# 3# Copyright 2013 Ingo Weinhold 4# Copyright 2014 Oliver Tappe 5# Distributed under the terms of the MIT License. 6 7# -- Modules ------------------------------------------------------------------ 8 9import copy 10import os 11import shutil 12from subprocess import CalledProcessError 13 14from .BuildPlatform import buildPlatform 15from .Options import getOption 16from .PackageInfo import PackageInfo, ResolvableExpression 17from .ProvidesManager import ProvidesManager 18from .ShellScriptlets import getScriptletPrerequirements 19from .Utils import sysExit 20 21# ----------------------------------------------------------------------------- 22 23requiresDummyPackageInfo = r''' 24name _dummy_ 25version 1-1 26architecture any 27summary "dummy" 28description "dummy" 29packager "dummy <dummy@dummy.dummy>" 30vendor "Haiku Project" 31licenses "MIT" 32copyrights "none" 33provides { 34 _dummy_ = 1-1 35} 36requires { 37 %s 38} 39''' 40 41# -- PortNode class ------------------------------------------------------------ 42 43class PortNode(object): 44 def __init__(self, portID, port): 45 self.portID = portID 46 self.port = port 47 self.packageNodes = set() 48 self.requires = set() 49 self.buildRequires = set() 50 self.buildPrerequires = set() 51 self.indegree = 0 52 self.outdegree = 0 53 54 @property 55 def name(self): 56 return self.portID 57 58 @property 59 def dependencies(self): 60 return self.buildRequires | self.buildPrerequires 61 62 @property 63 def isPort(self): 64 return True 65 66 def addBuildRequires(self, elements): 67 self.buildRequires |= elements 68 69 def addBuildPrerequires(self, elements): 70 self.buildPrerequires |= elements 71 72 def isBuildable(self, repositoryPath, doneRepositoryPath): 73 # check prerequires 74 dependencyInfoFiles = self.port.getDependencyInfoFiles() 75 requiresTypes = ['BUILD_REQUIRES', 'BUILD_PREREQUIRES', 76 'SCRIPTLET_PREREQUIRES'] 77 repositories = [doneRepositoryPath] 78 if not getOption('noSystemPackages'): 79 repositories.append( 80 buildPlatform.findDirectory('B_SYSTEM_PACKAGES_DIRECTORY')) 81 82 try: 83 buildPlatform.resolveDependencies(dependencyInfoFiles, 84 requiresTypes, 85 repositories) 86 except (CalledProcessError, LookupError): 87 return False 88 89 return True 90 91 def markAsBuilt(self, doneRepositoryPath): 92 with self.port.temporaryRepositoryDir(doneRepositoryPath): 93 self.port.writeDependencyInfosIntoRepository() 94 95# -- PackageNode class --------------------------------------------------------- 96 97class PackageNode(object): 98 def __init__(self, portNode, packageID): 99 self.portNode = portNode 100 self.name = packageID 101 self.requires = set() 102 self.indegree = 0 103 self.outdegree = 0 104 105 @property 106 def isPort(self): 107 return False 108 109 @property 110 def dependencies(self): 111 dependencies = copy.copy(self.requires) 112 dependencies.add(self.portNode) 113 return dependencies 114 115 @property 116 def isSystemPackage(self): 117 return not self.portNode 118 119 def addRequires(self, elements): 120 self.requires |= elements 121 122# -- DependencyAnalyzer class -------------------------------------------------- 123 124class DependencyAnalyzer(object): 125 def __init__(self, repository): 126 self.repository = repository 127 self.portNodes = {} 128 self.packageNodes = {} 129 self.packageInfos = {} 130 self.providesManager = ProvidesManager() 131 132 def printDependencies(self): 133 if not self.portNodes: 134 self._doInitialDependencyResolution() 135 136 print('Required system packages:') 137 for packageNode in sorted(self.systemPackageNodes, 138 key=lambda packageNode: packageNode.name): 139 print(' %s' % packageNode.name) 140 141 print('Ports required by haikuporter:') 142 for packageNode in sorted(self.haikuporterRequires, 143 key=lambda packageNode: packageNode.name): 144 print(' %s' % packageNode.portNode.name) 145 146 print('Ports depending cyclically on each other:') 147 for node in sorted(sorted(self.cyclicNodes, key=lambda node: node.name), 148 key=lambda node: node.outdegree): 149 print(' %s (out-degree %d)' % (node.name, node.outdegree)) 150 151 def getBuildOrderForBootstrap(self): 152 if not self.portNodes: 153 self._doInitialDependencyResolution() 154 155 doneRepositoryPath = self.repository.path + '/.build-order-done' 156 if os.path.exists(doneRepositoryPath): 157 shutil.rmtree(doneRepositoryPath) 158 os.mkdir(doneRepositoryPath) 159 160 done = [] 161 nodes = set(self.cyclicNodes) 162 while nodes: 163 lastDoneCount = len(done) 164 for node in sorted(list(nodes), key=lambda node: node.name): 165 print('# checking if %s is buildable ...' % node.name) 166 if node.isBuildable(self.repository.path, doneRepositoryPath): 167 done.append(node.name) 168 nodes.remove(node) 169 node.markAsBuilt(doneRepositoryPath) 170 if lastDoneCount == len(done): 171 sysExit("None of these cyclic dependencies can be built:\n\t" 172 + "\n\t".join(sorted([node.name for node in nodes]))) 173 174 shutil.rmtree(doneRepositoryPath) 175 176 return done 177 178 def _doInitialDependencyResolution(self): 179 # Iterate through the packages and resolve dependencies. We build a 180 # dependency graph with two different node types: port nodes and package 181 # nodes. A port is something we want to build, a package is a what we 182 # depend on. A package automatically depends on the port it belongs to. 183 # Furthermore it depends on the packages its requires specify. Build 184 # requires and build prerequires are dependencies for a port. 185 print('Resolving dependencies ...') 186 187 self._collectDependencyInfos(self.repository.path) 188 self._collectSystemPackages() 189 190 allActivePorts = [] 191 for portName in sorted(self.repository.portVersionsByName.keys()): 192 activePortVersion = self.repository.getActiveVersionOf(portName) 193 if not activePortVersion: 194 print('Warning: Skipping ' + portName + ', no version active') 195 continue 196 197 allActivePorts.append(portName + '-' + activePortVersion) 198 199 for portID in allActivePorts: 200 portNode = self._getPortNode(portID) 201 for package in portNode.port.packages: 202 packageID = package.versionedName 203 packageNode = self._getPackageNode(packageID) 204 packageInfo = self.packageInfos[packageID] 205 packageNode.addRequires( 206 self._resolveRequiresList(packageInfo.requires, portID, 207 packageID)) 208 portNode.addBuildRequires( 209 self._resolveRequiresList(packageInfo.buildRequires, portID, 210 packageID)) 211 portNode.addBuildPrerequires( 212 self._resolveRequiresList(packageInfo.buildPrerequires, 213 portID, packageID)) 214 215 # determine the needed system packages 216 self.systemPackageNodes = set() 217 remainingPortNodes = set() 218 nonSystemPackageNodes = set() 219 220 for packageNode in self.packageNodes.values(): 221 if packageNode.isSystemPackage: 222 self.systemPackageNodes.add(packageNode) 223 else: 224 nonSystemPackageNodes.add(packageNode) 225 remainingPortNodes.add(packageNode.portNode) 226 227 # resolve system package dependencies 228 for packageNode in self.systemPackageNodes: 229 packageInfo = self.packageInfos[packageNode.name] 230 packageNode.addRequires( 231 self._resolveRequiresList(packageInfo.requires, 232 'system packages', packageNode.name)) 233 234 nodeStack = list(self.systemPackageNodes) 235 while nodeStack: 236 packageNode = nodeStack.pop() 237 for dependency in packageNode.requires: 238 if (dependency in nonSystemPackageNodes 239 and dependency not in self.systemPackageNodes): 240 nodeStack.append(dependency) 241 self.systemPackageNodes.add(dependency) 242 243 # resolve the haikuporter dependencies 244 scriptletPrerequirements = [ResolvableExpression(requires) 245 for requires in getScriptletPrerequirements()] 246 haikuporterDependencies \ 247 = self._resolveRequiresList(scriptletPrerequirements, 248 'haikuporter', 'scriptlet requires') 249 self.haikuporterRequires = set() 250 for packageNode in haikuporterDependencies: 251 if not packageNode.isSystemPackage: 252 self.haikuporterRequires.add(packageNode) 253 254 # ... and their requires closure 255 nodeStack = list(self.haikuporterRequires) 256 while nodeStack: 257 packageNode = nodeStack.pop() 258 for dependency in packageNode.requires: 259 if (dependency in nonSystemPackageNodes 260 and dependency not in self.haikuporterRequires): 261 nodeStack.append(dependency) 262 self.haikuporterRequires.add(dependency) 263 264 # compute the in-degrees of the nodes 265 nodes = set(remainingPortNodes) 266 for portNode in remainingPortNodes: 267 nodes |= portNode.packageNodes 268 269 for node in nodes: 270 for dependency in node.dependencies: 271 if dependency in nodes: 272 dependency.indegree += 1 273 274 indegreeZeroStack = [] 275 for node in nodes: 276 if node.indegree == 0: 277 indegreeZeroStack.append(node) 278 279 # remove the acyclic part of the graph that nothing else depends on 280 while indegreeZeroStack: 281 node = indegreeZeroStack.pop() 282 nodes.remove(node) 283 for dependency in node.dependencies: 284 if dependency in nodes: 285 dependency.indegree -= 1 286 if dependency.indegree == 0: 287 indegreeZeroStack.append(dependency) 288 289 # compute the out-degrees of the remaining nodes 290 for node in nodes: 291 outdegree = 0 292 for dependency in node.dependencies: 293 if dependency in nodes: 294 outdegree += 1 295 node.outdegree = outdegree 296 297 outdegreeZeroStack = [] 298 for node in nodes: 299 if node.outdegree == 0: 300 outdegreeZeroStack.append(node) 301 print('[%s] has out-degree 0' % node.name) 302 303 # remove the acyclic part of the graph that depends on nothing else 304 while outdegreeZeroStack: 305 node = outdegreeZeroStack.pop() 306 nodes.remove(node) 307 for otherNode in nodes: 308 if (node in otherNode.dependencies 309 and otherNode in nodes): 310 otherNode.outdegree -= 1 311 if otherNode.outdegree == 0: 312 outdegreeZeroStack.append(otherNode) 313 314 self.cyclicNodes = [ 315 node for node in nodes if node.isPort 316 ] 317 318 def _collectDependencyInfos(self, path): 319 for entry in os.listdir(path): 320 if not entry.endswith('.DependencyInfo'): 321 continue 322 dependencyInfoFile = path + '/' + entry 323 try: 324 packageInfo = PackageInfo(dependencyInfoFile) 325 except CalledProcessError: 326 print('Warning: Ignoring broken dependency-info file "%s"' 327 % dependencyInfoFile) 328 self.providesManager.addProvidesFromPackageInfo(packageInfo) 329 self.packageInfos[packageInfo.versionedName] = packageInfo 330 331 def _collectSystemPackages(self): 332 if getOption('noSystemPackages'): 333 return 334 335 path = buildPlatform.findDirectory('B_SYSTEM_PACKAGES_DIRECTORY') 336 if not os.path.exists(path): 337 print('Warning: "%s" system package path not found!' % path) 338 # Do we want to "fake inject" haiku, haiku_dev here? 339 return 340 341 for entry in os.listdir(path): 342 if not entry.endswith('.hpkg'): 343 continue 344 packageFile = path + '/' + entry 345 try: 346 packageInfo = PackageInfo(packageFile) 347 except CalledProcessError: 348 print('Warning: Ignoring broken package file "%s"' 349 % packageFile) 350 self.providesManager.addProvidesFromPackageInfo(packageInfo) 351 self.packageInfos[packageInfo.versionedName] = packageInfo 352 353 def _resolveRequiresList(self, requiresList, portID, packageID): 354 dependencies = set() 355 for requires in requiresList: 356 providesInfo = self.providesManager.getMatchingProvides(requires) 357 if providesInfo: 358 isSystemPackage \ 359 = buildPlatform.isSystemPackage(providesInfo.path) 360 packageNode = self._getPackageNode(providesInfo.packageID, 361 isSystemPackage) 362 dependencies.add(packageNode) 363 else: 364 print('Warning: Ignoring unresolvable requires "%s" of package' 365 ' %s in %s' % (requires, packageID, portID)) 366 return dependencies 367 368 def _getPortNode(self, portID): 369 if portID in self.portNodes: 370 return self.portNodes[portID] 371 372 # get the port and create the port node 373 port = self.repository.allPorts[portID] 374 portNode = PortNode(portID, port) 375 self.portNodes[portID] = portNode 376 377 # also create nodes for all of the port's packages 378 portNode.port.parseRecipeFile(False) 379 for package in port.packages: 380 packageID = package.versionedName 381 packageNode = PackageNode(portNode, packageID) 382 self.packageNodes[packageID] = packageNode 383 portNode.packageNodes.add(packageNode) 384 385 return portNode 386 387 def _getPackageNode(self, packageID, isSystemPackage=False): 388 if packageID in self.packageNodes: 389 return self.packageNodes[packageID] 390 391 if isSystemPackage: 392 packageNode = PackageNode(None, packageID) 393 self.packageNodes[packageID] = packageNode 394 return packageNode 395 396 # get the port -- that will also create nodes for all of the port's 397 # packages 398 portID = self.repository.getPortIdForPackageId(packageID) 399 self._getPortNode(portID) 400 401 if packageID not in self.packageNodes: 402 sysExit('package "%s" doesn\'t seem to exist' % packageID) 403 return self.packageNodes[packageID] 404