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