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