taskdata.py: Stop failed dependencies being added back into taskData. Improve multipl...
[bitbake.git] / lib / bb / taskdata.py
1 #!/usr/bin/env python
2 # ex:ts=4:sw=4:sts=4:et
3 # -*- tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
4 """
5 BitBake 'TaskData' implementation
6
7 Task data collection and handling
8
9 Copyright (C) 2006  Richard Purdie
10
11 This program is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License version 2 as published by the Free 
13 Software Foundation
14
15 This program is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License along with
20 """
21
22 from bb import data, fetch, event, mkdirhier, utils
23 import bb, os
24
25 class TaskData:
26     """
27     BitBake Task Data implementation
28     """
29     def __init__(self, abort = True):
30         self.build_names_index = []
31         self.run_names_index = []
32         self.fn_index = []
33
34         self.build_targets = {}
35         self.run_targets = {}
36
37         self.external_targets = []
38
39         self.tasks_fnid = []
40         self.tasks_name = []
41         self.tasks_tdepends = []
42         # Cache to speed up task ID lookups
43         self.tasks_lookup = {}
44
45         self.depids = {}
46         self.rdepids = {}
47
48         self.consider_msgs_cache = []
49
50         self.failed_deps = []
51         self.failed_rdeps = []
52         self.failed_fnids = []
53
54         self.abort = abort
55
56     def matches_in_list(self, data, substring):
57         """
58         Return a list of the positions of substring in list data
59         """
60         matches = []
61         start = 0
62         while 1:
63             try:
64                 start = data.index(substring, start)
65             except ValueError:
66                 return matches
67             matches.append(start)
68             start = start + 1
69
70     def both_contain(self, list1, list2):
71         """
72         Return the items present in both list1 and list2
73         """
74         matches = []
75         for data in list1:
76             if data in list2:
77                 return data
78         return None
79
80
81     def getbuild_id(self, name):
82         """
83         Return an ID number for the build target name.
84         If it doesn't exist, create one.
85         """
86         if not name in self.build_names_index:
87             self.build_names_index.append(name)
88
89         return self.build_names_index.index(name)
90
91     def getrun_id(self, name):
92         """
93         Return an ID number for the run target name. 
94         If it doesn't exist, create one.
95         """
96         if not name in self.run_names_index:
97             self.run_names_index.append(name)
98
99         return self.run_names_index.index(name)
100
101     def getfn_id(self, name):
102         """
103         Return an ID number for the filename. 
104         If it doesn't exist, create one.
105         """
106         if not name in self.fn_index:
107             self.fn_index.append(name)
108
109         return self.fn_index.index(name)
110
111     def gettask_id(self, fn, task):
112         """
113         Return an ID number for the task matching fn and task.
114         If it doesn't exist, create one.
115         """
116         fnid = self.getfn_id(fn)
117
118         if fnid in self.tasks_lookup:
119             if task in self.tasks_lookup[fnid]:
120                 return self.tasks_lookup[fnid][task]
121
122         self.tasks_name.append(task)
123         self.tasks_fnid.append(fnid)
124         self.tasks_tdepends.append([])
125
126         listid = len(self.tasks_name) - 1
127
128         if fnid not in self.tasks_lookup:
129             self.tasks_lookup[fnid] = {}
130         self.tasks_lookup[fnid][task] = listid
131
132         return listid
133
134     def add_tasks(self, fn, dataCache):
135         """
136         Add tasks for a given fn to the database
137         """
138
139         task_graph = dataCache.task_queues[fn]
140         task_deps = dataCache.task_deps[fn]
141
142         fnid = self.getfn_id(fn)
143
144         if fnid in self.failed_fnids:
145             bb.msg.fatal(bb.msg.domain.TaskData, "Trying to re-add a failed file? Something is broken...")
146
147         # Check if we've already seen this fn
148         if fnid in self.tasks_fnid:
149             return
150
151         # Work out task dependencies
152         for task in task_graph.allnodes():
153             parentids = []
154             for dep in task_graph.getparents(task):
155                 parentid = self.gettask_id(fn, dep)
156                 parentids.append(parentid)
157             taskid = self.gettask_id(fn, task)
158             self.tasks_tdepends[taskid].extend(parentids)
159
160         # Work out build dependencies
161         if not fnid in self.depids:
162             dependids = {}
163             for depend in dataCache.deps[fn]:
164                 bb.msg.debug(2, bb.msg.domain.TaskData, "Added dependency %s for %s" % (depend, fn))
165                 dependids[self.getbuild_id(depend)] = None
166             self.depids[fnid] = dependids.keys()
167
168         # Work out runtime dependencies
169         if not fnid in self.rdepids:
170             rdependids = {}
171             rdepends = dataCache.rundeps[fn]
172             rrecs = dataCache.runrecs[fn]
173             for package in rdepends:
174                 for rdepend in rdepends[package]:
175                     bb.msg.debug(2, bb.msg.domain.TaskData, "Added runtime dependency %s for %s" % (rdepend, fn))
176                     rdependids[self.getrun_id(rdepend)] = None
177             for package in rrecs:
178                 for rdepend in rrecs[package]:
179                     bb.msg.debug(2, bb.msg.domain.TaskData, "Added runtime recommendation %s for %s" % (rdepend, fn))
180                     rdependids[self.getrun_id(rdepend)] = None
181             self.rdepids[fnid] = rdependids.keys()
182
183         for dep in self.depids[fnid]:
184             if dep in self.failed_deps:
185                 self.fail_fnid(fnid)
186                 return
187         for dep in self.rdepids[fnid]:
188             if dep in self.failed_rdeps:
189                 self.fail_fnid(fnid)
190                 return
191
192     def have_build_target(self, target):
193         """
194         Have we a build target matching this name?
195         """
196         targetid = self.getbuild_id(target)
197
198         if targetid in self.build_targets:
199             return True
200         return False
201
202     def have_runtime_target(self, target):
203         """
204         Have we a runtime target matching this name?
205         """
206         targetid = self.getrun_id(target)
207
208         if targetid in self.run_targets:
209             return True
210         return False
211
212     def add_build_target(self, fn, item):
213         """
214         Add a build target.
215         If already present, append the provider fn to the list
216         """
217         targetid = self.getbuild_id(item)
218         fnid = self.getfn_id(fn)
219
220         if targetid in self.build_targets:
221             if fnid in self.build_targets[targetid]:
222                 return
223             self.build_targets[targetid].append(fnid)
224             return
225         self.build_targets[targetid] = [fnid]
226
227     def add_runtime_target(self, fn, item):
228         """
229         Add a runtime target.
230         If already present, append the provider fn to the list
231         """
232         targetid = self.getrun_id(item)
233         fnid = self.getfn_id(fn)
234
235         if targetid in self.run_targets:
236             if fnid in self.run_targets[targetid]:
237                 return
238             self.run_targets[targetid].append(fnid)
239             return
240         self.run_targets[targetid] = [fnid]
241
242     def mark_external_target(self, item):
243         """
244         Mark a build target as being externally requested
245         """
246         targetid = self.getbuild_id(item)
247
248         if targetid not in self.external_targets:
249             self.external_targets.append(targetid)
250
251     def get_unresolved_build_targets(self, dataCache):
252         """
253         Return a list of build targets who's providers 
254         are unknown.
255         """
256         unresolved = []
257         for target in self.build_names_index:
258             if target in dataCache.ignored_dependencies:
259                 continue
260             if self.build_names_index.index(target) in self.failed_deps:
261                 continue
262             if not self.have_build_target(target):
263                 unresolved.append(target)
264         return unresolved
265
266     def get_unresolved_run_targets(self, dataCache):
267         """
268         Return a list of runtime targets who's providers 
269         are unknown.
270         """
271         unresolved = []
272         for target in self.run_names_index:
273             if target in dataCache.ignored_dependencies:
274                 continue
275             if self.run_names_index.index(target) in self.failed_rdeps:
276                 continue
277             if not self.have_runtime_target(target):
278                 unresolved.append(target)
279         return unresolved
280
281     def get_provider(self, item):
282         """
283         Return a list of providers of item
284         """
285         targetid = self.getbuild_id(item)
286    
287         return self.build_targets[targetid]
288
289     def get_dependees(self, itemid):
290         """
291         Return a list of targets which depend on item
292         """
293         dependees = []
294         for fnid in self.depids:
295             if itemid in self.depids[fnid]:
296                 dependees.append(fnid)
297         return dependees
298
299     def get_dependees_str(self, item):
300         """
301         Return a list of targets which depend on item as a user readable string
302         """
303         itemid = self.getbuild_id(item)
304         dependees = []
305         for fnid in self.depids:
306             if itemid in self.depids[fnid]:
307                 dependees.append(self.fn_index[fnid])
308         return dependees
309
310     def get_rdependees(self, itemid):
311         """
312         Return a list of targets which depend on runtime item
313         """
314         dependees = []
315         for fnid in self.rdepids:
316             if itemid in self.rdepids[fnid]:
317                 dependees.append(fnid)
318         return dependees
319
320     def get_rdependees_str(self, item):
321         """
322         Return a list of targets which depend on runtime item as a user readable string
323         """
324         itemid = self.getrun_id(item)
325         dependees = []
326         for fnid in self.rdepids:
327             if itemid in self.rdepids[fnid]:
328                 dependees.append(self.fn_index[fnid])
329         return dependees
330
331     def add_provider(self, cfgData, dataCache, item):
332         try:
333             self.add_provider_internal(cfgData, dataCache, item)
334         except bb.providers.NoProvider:
335             if self.abort:
336                 bb.msg.error(bb.msg.domain.Provider, "No providers of build target %s (for %s)" % (item, self.get_dependees_str(item)))
337                 raise
338             targetid = self.getbuild_id(item)
339             self.remove_buildtarget(targetid)
340
341         self.mark_external_target(item)
342
343     def add_provider_internal(self, cfgData, dataCache, item):
344         """
345         Add the providers of item to the task data
346         Mark entries were specifically added externally as against dependencies 
347         added internally during dependency resolution
348         """
349
350         if item in dataCache.ignored_dependencies:
351             return
352
353         if not item in dataCache.providers:
354             bb.msg.debug(1, bb.msg.domain.Provider, "No providers of build target %s (for %s)" % (item, self.get_dependees_str(item)))
355             bb.event.fire(bb.event.NoProvider(item, cfgData))
356             raise bb.providers.NoProvider(item)
357
358         if self.have_build_target(item):
359             return
360
361         all_p = dataCache.providers[item]
362
363         eligible = bb.providers.filterProviders(all_p, item, cfgData, dataCache)
364
365         for p in eligible:
366             fnid = self.getfn_id(p)
367             if fnid in self.failed_fnids:
368                 eligible.remove(p)
369
370         if not eligible:
371             bb.msg.debug(1, bb.msg.domain.Provider, "No providers of build target %s after filtering (for %s)" % (item, self.get_dependees_str(item)))
372             bb.event.fire(bb.event.NoProvider(item, cfgData))
373             raise bb.providers.NoProvider(item)
374
375         prefervar = bb.data.getVar('PREFERRED_PROVIDER_%s' % item, cfgData, 1)
376         if prefervar:
377             dataCache.preferred[item] = prefervar
378
379         discriminated = False
380         if item in dataCache.preferred:
381             for p in eligible:
382                 pn = dataCache.pkg_fn[p]
383                 if dataCache.preferred[item] == pn:
384                     bb.msg.note(2, bb.msg.domain.Provider, "selecting %s to satisfy %s due to PREFERRED_PROVIDERS" % (pn, item))
385                     eligible.remove(p)
386                     eligible = [p] + eligible
387                     discriminated = True
388                     break
389
390         if len(eligible) > 1 and discriminated == False:
391             if item not in self.consider_msgs_cache:
392                 providers_list = []
393                 for fn in eligible:
394                     providers_list.append(dataCache.pkg_fn[fn])
395                 bb.msg.note(1, bb.msg.domain.Provider, "multiple providers are available for %s (%s);" % (item, ", ".join(providers_list)))
396                 bb.msg.note(1, bb.msg.domain.Provider, "consider defining PREFERRED_PROVIDER_%s" % item)
397                 bb.event.fire(bb.event.MultipleProviders(item,providers_list,cfgData))
398             self.consider_msgs_cache.append(item)
399
400         for fn in eligible:
401             fnid = self.getfn_id(fn)
402             if fnid in self.failed_fnids:
403                 continue
404             bb.msg.debug(2, bb.msg.domain.Provider, "adding %s to satisfy %s" % (fn, item))
405             self.add_build_target(fn, item)
406             self.add_tasks(fn, dataCache)
407
408
409             #item = dataCache.pkg_fn[fn]
410
411     def add_rprovider(self, cfgData, dataCache, item):
412         """
413         Add the runtime providers of item to the task data
414         (takes item names from RDEPENDS/PACKAGES namespace)
415         """
416
417         if item in dataCache.ignored_dependencies:
418             return
419
420         if self.have_runtime_target(item):
421             return
422
423         all_p = bb.providers.getRuntimeProviders(dataCache, item)
424
425         if not all_p:
426             bb.msg.error(bb.msg.domain.Provider, "No providers of runtime build target %s (for %s)" % (item, self.get_rdependees_str(item)))
427             bb.event.fire(bb.event.NoProvider(item, cfgData, runtime=True))
428             raise bb.providers.NoRProvider(item)
429
430         eligible = bb.providers.filterProviders(all_p, item, cfgData, dataCache)
431
432         for p in eligible:
433             fnid = self.getfn_id(p)
434             if fnid in self.failed_fnids:
435                 eligible.remove(p)
436
437         if not eligible:
438             bb.msg.error(bb.msg.domain.Provider, "No providers of runtime build target %s after filtering (for %s)" % (item, self.get_rdependees_str(item)))
439             bb.event.fire(bb.event.NoProvider(item, cfgData, runtime=True))
440             raise bb.providers.NoRProvider(item)
441
442         # Should use dataCache.preferred here?
443         preferred = []
444         for p in eligible:
445             pn = dataCache.pkg_fn[p]
446             provides = dataCache.pn_provides[pn]
447             for provide in provides:
448                 prefervar = bb.data.getVar('PREFERRED_PROVIDER_%s' % provide, cfgData, 1)
449                 if prefervar == pn:
450                     bb.msg.note(2, bb.msg.domain.Provider, "selecting %s to satisfy runtime %s due to PREFERRED_PROVIDERS" % (pn, item))
451                     eligible.remove(p)
452                     eligible = [p] + eligible
453                     preferred.append(p)
454
455         if len(eligible) > 1 and len(preferred) == 0:
456             if item not in self.consider_msgs_cache:
457                 providers_list = []
458                 for fn in eligible:
459                     providers_list.append(dataCache.pkg_fn[fn])
460                 bb.msg.note(2, bb.msg.domain.Provider, "multiple providers are available for runtime %s (%s);" % (item, ", ".join(providers_list)))
461                 bb.msg.note(2, bb.msg.domain.Provider, "consider defining a PREFERRED_PROVIDER entry to match runtime %s" % item)
462                 bb.event.fire(bb.event.MultipleProviders(item,providers_list, cfgData, runtime=True))
463             self.consider_msgs_cache.append(item)
464
465         if len(preferred) > 1:
466             if item not in self.consider_msgs_cache:
467                 providers_list = []
468                 for fn in preferred:
469                     providers_list.append(dataCache.pkg_fn[fn])
470                 bb.msg.note(2, bb.msg.domain.Provider, "multiple preferred providers are available for runtime %s (%s);" % (item, ", ".join(providers_list)))
471                 bb.msg.note(2, bb.msg.domain.Provider, "consider defining only one PREFERRED_PROVIDER entry to match runtime %s" % item)
472                 bb.event.fire(bb.event.MultipleProviders(item,providers_list, cfgData, runtime=True))
473             self.consider_msgs_cache.append(item)
474
475         # run through the list until we find one that we can build
476         for fn in eligible:
477             fnid = self.getfn_id(fn)
478             if fnid in self.failed_fnids:
479                 continue
480             bb.msg.debug(2, bb.msg.domain.Provider, "adding %s to satisfy runtime %s" % (fn, item))
481             self.add_runtime_target(fn, item)
482             self.add_tasks(fn, dataCache)
483
484     def fail_fnid(self, fnid):
485         """
486         Mark a file as failed (unbuildable)
487         Remove any references from build and runtime provider lists
488         """
489         if fnid in self.failed_fnids:
490             return
491         bb.msg.debug(1, bb.msg.domain.Provider, "Removing failed file %s" % self.fn_index[fnid])
492         self.failed_fnids.append(fnid)
493         for target in self.build_targets:
494             if fnid in self.build_targets[target]:
495                 self.build_targets[target].remove(fnid)
496                 if len(self.build_targets[target]) == 0:
497                     self.remove_buildtarget(target)
498         for target in self.run_targets:
499             if fnid in self.run_targets[target]:
500                 self.run_targets[target].remove(fnid)
501                 if len(self.run_targets[target]) == 0:
502                     self.remove_runtarget(target)
503
504     def remove_buildtarget(self, targetid):
505         """
506         Mark a build target as failed (unbuildable)
507         Trigger removal of any files that have this as a dependency
508         """
509         bb.msg.debug(1, bb.msg.domain.Provider, "Removing failed build target %s" % self.build_names_index[targetid])
510         self.failed_deps.append(targetid)
511         dependees = self.get_dependees(targetid)
512         for fnid in dependees:
513             self.fail_fnid(fnid)
514         if self.abort and targetid in self.external_targets:
515             bb.msg.error(bb.msg.domain.Provider, "No buildable providers available for required build target %s" % self.build_names_index[targetid])
516             raise bb.providers.NoProvider
517
518     def remove_runtarget(self, targetid):
519         """
520         Mark a run target as failed (unbuildable)
521         Trigger removal of any files that have this as a dependency
522         """
523         bb.msg.note(1, bb.msg.domain.Provider, "Removing failed runtime build target %s" % self.run_names_index[targetid])
524         self.failed_rdeps.append(targetid)
525         dependees = self.get_rdependees(targetid)
526         for fnid in dependees:
527             self.fail_fnid(fnid)
528
529     def add_unresolved(self, cfgData, dataCache):
530         """
531         Resolve all unresolved build and runtime targets
532         """
533         bb.msg.note(1, bb.msg.domain.TaskData, "Resolving missing task queue dependencies")
534         while 1:
535             added = 0
536             for target in self.get_unresolved_build_targets(dataCache):
537                 try:
538                     self.add_provider_internal(cfgData, dataCache, target)
539                     added = added + 1
540                 except bb.providers.NoProvider:
541                     targetid = self.getbuild_id(target)
542                     if self.abort and targetid in self.external_targets:
543                         raise
544                     self.remove_buildtarget(targetid)
545             for target in self.get_unresolved_run_targets(dataCache):
546                 try:
547                     self.add_rprovider(cfgData, dataCache, target)
548                     added = added + 1
549                 except bb.providers.NoRProvider:
550                     self.remove_runtarget(self.getrun_id(target))
551             bb.msg.debug(1, bb.msg.domain.TaskData, "Resolved " + str(added) + " extra dependecies")
552             if added == 0:
553                 break
554
555     def dump_data(self):
556         """
557         Dump some debug information on the internal data structures
558         """
559         bb.msg.debug(3, bb.msg.domain.TaskData, "build_names:")
560         bb.msg.debug(3, bb.msg.domain.TaskData, ", ".join(self.build_names_index))
561         bb.msg.debug(3, bb.msg.domain.TaskData, "run_names:")
562         bb.msg.debug(3, bb.msg.domain.TaskData, ", ".join(self.run_names_index))
563         bb.msg.debug(3, bb.msg.domain.TaskData, "build_targets:")
564         for target in self.build_targets.keys():
565             bb.msg.debug(3, bb.msg.domain.TaskData, " %s: %s" % (self.build_names_index[target], self.build_targets[target]))
566         bb.msg.debug(3, bb.msg.domain.TaskData, "run_targets:")
567         for target in self.run_targets.keys():
568             bb.msg.debug(3, bb.msg.domain.TaskData, " %s: %s" % (self.run_names_index[target], self.run_targets[target]))
569         bb.msg.debug(3, bb.msg.domain.TaskData, "tasks:")
570         for task in range(len(self.tasks_name)):
571             bb.msg.debug(3, bb.msg.domain.TaskData, " (%s)%s - %s: %s" % (
572                 task, 
573                 self.fn_index[self.tasks_fnid[task]], 
574                 self.tasks_name[task], 
575                 self.tasks_tdepends[task]))
576         bb.msg.debug(3, bb.msg.domain.TaskData, "runtime ids (per fn):")
577         for fnid in self.rdepids:
578             bb.msg.debug(3, bb.msg.domain.TaskData, " %s %s: %s" % (fnid, self.fn_index[fnid], self.rdepids[fnid]))
579
580