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