taskdata.py: Add some extra debug to dump_data and optimise depid and rdepid to avoid...
[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     def have_build_target(self, target):
184         """
185         Have we a build target matching this name?
186         """
187         targetid = self.getbuild_id(target)
188
189         if targetid in self.build_targets:
190             return True
191         return False
192
193     def have_runtime_target(self, target):
194         """
195         Have we a runtime target matching this name?
196         """
197         targetid = self.getrun_id(target)
198
199         if targetid in self.run_targets:
200             return True
201         return False
202
203     def add_build_target(self, fn, item):
204         """
205         Add a build target.
206         If already present, append the provider fn to the list
207         """
208         targetid = self.getbuild_id(item)
209         fnid = self.getfn_id(fn)
210
211         if targetid in self.build_targets:
212             if fnid in self.build_targets[targetid]:
213                 return
214             self.build_targets[targetid].append(fnid)
215             return
216         self.build_targets[targetid] = [fnid]
217
218     def add_runtime_target(self, fn, item):
219         """
220         Add a runtime target.
221         If already present, append the provider fn to the list
222         """
223         targetid = self.getrun_id(item)
224         fnid = self.getfn_id(fn)
225
226         if targetid in self.run_targets:
227             if fnid in self.run_targets[targetid]:
228                 return
229             self.run_targets[targetid].append(fnid)
230             return
231         self.run_targets[targetid] = [fnid]
232
233     def mark_external_target(self, item):
234         """
235         Mark a build target as being externally requested
236         """
237         targetid = self.getbuild_id(item)
238
239         if targetid not in self.external_targets:
240             self.external_targets.append(targetid)
241
242     def get_unresolved_build_targets(self, dataCache):
243         """
244         Return a list of build targets who's providers 
245         are unknown.
246         """
247         unresolved = []
248         for target in self.build_names_index:
249             if target in dataCache.ignored_dependencies:
250                 continue
251             if self.build_names_index.index(target) in self.failed_deps:
252                 continue
253             if not self.have_build_target(target):
254                 unresolved.append(target)
255         return unresolved
256
257     def get_unresolved_run_targets(self, dataCache):
258         """
259         Return a list of runtime targets who's providers 
260         are unknown.
261         """
262         unresolved = []
263         for target in self.run_names_index:
264             if target in dataCache.ignored_dependencies:
265                 continue
266             if self.run_names_index.index(target) in self.failed_rdeps:
267                 continue
268             if not self.have_runtime_target(target):
269                 unresolved.append(target)
270         return unresolved
271
272     def get_provider(self, item):
273         """
274         Return a list of providers of item
275         """
276         targetid = self.getbuild_id(item)
277    
278         return self.build_targets[targetid]
279
280     def get_dependees(self, itemid):
281         """
282         Return a list of targets which depend on item
283         """
284         dependees = []
285         for fnid in self.depids:
286             if itemid in self.depids[fnid]:
287                 dependees.append(fnid)
288         return dependees
289
290     def get_dependees_str(self, item):
291         """
292         Return a list of targets which depend on item as a user readable string
293         """
294         itemid = self.getbuild_id(item)
295         dependees = []
296         for fnid in self.depids:
297             if itemid in self.depids[fnid]:
298                 dependees.append(self.fn_index[fnid])
299         return dependees
300
301     def get_rdependees(self, itemid):
302         """
303         Return a list of targets which depend on runtime item
304         """
305         dependees = []
306         for fnid in self.rdepids:
307             if itemid in self.rdepids[fnid]:
308                 dependees.append(fnid)
309         return dependees
310
311     def get_rdependees_str(self, item):
312         """
313         Return a list of targets which depend on runtime item as a user readable string
314         """
315         itemid = self.getrun_id(item)
316         dependees = []
317         for fnid in self.rdepids:
318             if itemid in self.rdepids[fnid]:
319                 dependees.append(self.fn_index[fnid])
320         return dependees
321
322     def add_provider(self, cfgData, dataCache, item):
323         try:
324             self.add_provider_internal(cfgData, dataCache, item)
325         except bb.providers.NoProvider:
326             if self.abort:
327                 bb.msg.error(bb.msg.domain.Provider, "No providers of build target %s (for %s)" % (item, self.get_dependees_str(item)))
328                 raise
329             targetid = self.getbuild_id(item)
330             self.remove_buildtarget(targetid)
331
332         self.mark_external_target(item)
333
334     def add_provider_internal(self, cfgData, dataCache, item):
335         """
336         Add the providers of item to the task data
337         Mark entries were specifically added externally as against dependencies 
338         added internally during dependency resolution
339         """
340
341         if item in dataCache.ignored_dependencies:
342             return
343
344         if not item in dataCache.providers:
345             bb.msg.debug(1, bb.msg.domain.Provider, "No providers of build target %s (for %s)" % (item, self.get_dependees_str(item)))
346             bb.event.fire(bb.event.NoProvider(item, cfgData))
347             raise bb.providers.NoProvider(item)
348
349         if self.have_build_target(item):
350             return
351
352         all_p = dataCache.providers[item]
353
354         eligible = bb.providers.filterProviders(all_p, item, cfgData, dataCache)
355
356         for p in eligible:
357             fnid = self.getfn_id(p)
358             if fnid in self.failed_fnids:
359                 eligible.remove(p)
360
361         if not eligible:
362             bb.msg.debug(1, bb.msg.domain.Provider, "No providers of build target %s after filtering (for %s)" % (item, self.get_dependees_str(item)))
363             bb.event.fire(bb.event.NoProvider(item, cfgData))
364             raise bb.providers.NoProvider(item)
365
366         prefervar = bb.data.getVar('PREFERRED_PROVIDER_%s' % item, cfgData, 1)
367         if prefervar:
368             dataCache.preferred[item] = prefervar
369
370         discriminated = False
371         if item in dataCache.preferred:
372             for p in eligible:
373                 pn = dataCache.pkg_fn[p]
374                 if dataCache.preferred[item] == pn:
375                     bb.msg.note(2, bb.msg.domain.Provider, "selecting %s to satisfy %s due to PREFERRED_PROVIDERS" % (pn, item))
376                     eligible.remove(p)
377                     eligible = [p] + eligible
378                     discriminated = True
379                     break
380
381         if len(eligible) > 1 and discriminated == 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 (%s);" % ", ".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_tasks(fn, dataCache)
397             self.add_build_target(fn, item)
398
399             #item = dataCache.pkg_fn[fn]
400
401     def add_rprovider(self, cfgData, dataCache, item):
402         """
403         Add the runtime providers of item to the task data
404         (takes item names from RDEPENDS/PACKAGES namespace)
405         """
406
407         if item in dataCache.ignored_dependencies:
408             return
409
410         if self.have_runtime_target(item):
411             return
412
413         all_p = bb.providers.getRuntimeProviders(dataCache, item)
414
415         if not all_p:
416             bb.msg.error(bb.msg.domain.Provider, "No providers of runtime build target %s (for %s)" % (item, self.get_rdependees_str(item)))
417             bb.event.fire(bb.event.NoProvider(item, cfgData, runtime=True))
418             raise bb.providers.NoRProvider(item)
419
420         eligible = bb.providers.filterProviders(all_p, item, cfgData, dataCache)
421
422         for p in eligible:
423             fnid = self.getfn_id(p)
424             if fnid in self.failed_fnids:
425                 eligible.remove(p)
426
427         if not eligible:
428             bb.msg.error(bb.msg.domain.Provider, "No providers of runtime build target %s after filtering (for %s)" % (item, self.get_rdependees_str(item)))
429             bb.event.fire(bb.event.NoProvider(item, cfgData, runtime=True))
430             raise bb.providers.NoRProvider(item)
431
432         # Should use dataCache.preferred here?
433         preferred = []
434         for p in eligible:
435             pn = dataCache.pkg_fn[p]
436             provides = dataCache.pn_provides[pn]
437             for provide in provides:
438                 prefervar = bb.data.getVar('PREFERRED_PROVIDER_%s' % provide, cfgData, 1)
439                 if prefervar == pn:
440                     bb.msg.note(2, bb.msg.domain.Provider, "selecting %s to satisfy runtime %s due to PREFERRED_PROVIDERS" % (pn, item))
441                     eligible.remove(p)
442                     eligible = [p] + eligible
443                     preferred.append(p)
444
445         if len(eligible) > 1 and len(preferred) == 0:
446             if item not in self.consider_msgs_cache:
447                 providers_list = []
448                 for fn in eligible:
449                     providers_list.append(dataCache.pkg_fn[fn])
450                 bb.msg.note(2, bb.msg.domain.Provider, "multiple providers are available (%s);" % ", ".join(providers_list))
451                 bb.msg.note(2, bb.msg.domain.Provider, "consider defining a PREFERRED_PROVIDER to match runtime %s" % item)
452                 bb.event.fire(bb.event.MultipleProviders(item,providers_list, cfgData, runtime=True))
453             self.consider_msgs_cache.append(item)
454
455         if len(preferred) > 1:
456             if item not in self.consider_msgs_cache:
457                 providers_list = []
458                 for fn in preferred:
459                     providers_list.append(dataCache.pkg_fn[fn])
460                 bb.msg.note(2, bb.msg.domain.Provider, "multiple preferred providers are available (%s);" % ", ".join(providers_list))
461                 bb.msg.note(2, bb.msg.domain.Provider, "consider defining only one PREFERRED_PROVIDER 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         # run through the list until we find one that we can build
466         for fn in eligible:
467             fnid = self.getfn_id(fn)
468             if fnid in self.failed_fnids:
469                 continue
470             bb.msg.debug(2, bb.msg.domain.Provider, "adding %s to satisfy runtime %s" % (fn, item))
471             self.add_tasks(fn, dataCache)
472             self.add_runtime_target(fn, item)
473
474     def fail_fnid(self, fnid):
475         """
476         Mark a file as failed (unbuildable)
477         Remove any references from build and runtime provider lists
478         """
479         if fnid in self.failed_fnids:
480             return
481         bb.msg.debug(1, bb.msg.domain.Provider, "Removing failed file %s" % self.fn_index[fnid])
482         self.failed_fnids.append(fnid)
483         for target in self.build_targets:
484             if fnid in self.build_targets[target]:
485                 self.build_targets[target].remove(fnid)
486                 if len(self.build_targets[target]) == 0:
487                     self.remove_buildtarget(target)
488         for target in self.run_targets:
489             if fnid in self.run_targets[target]:
490                 self.run_targets[target].remove(fnid)
491                 if len(self.run_targets[target]) == 0:
492                     self.remove_runtarget(target)
493
494     def remove_buildtarget(self, targetid):
495         """
496         Mark a build target as failed (unbuildable)
497         Trigger removal of any files that have this as a dependency
498         """
499         bb.msg.debug(1, bb.msg.domain.Provider, "Removing failed build target %s" % self.build_names_index[targetid])
500         self.failed_deps.append(targetid)
501         dependees = self.get_dependees(targetid)
502         for fnid in dependees:
503             self.fail_fnid(fnid)
504         if self.abort and targetid in self.external_targets:
505             bb.msg.error(bb.msg.domain.Provider, "No buildable providers available for required build target %s" % self.build_names_index[targetid])
506             raise bb.providers.NoProvider
507
508     def remove_runtarget(self, targetid):
509         """
510         Mark a run target as failed (unbuildable)
511         Trigger removal of any files that have this as a dependency
512         """
513         bb.msg.note(1, bb.msg.domain.Provider, "Removing failed runtime build target %s" % self.run_names_index[targetid])
514         self.failed_rdeps.append(targetid)
515         dependees = self.get_rdependees(targetid)
516         for fnid in dependees:
517             self.fail_fnid(fnid)
518
519     def add_unresolved(self, cfgData, dataCache):
520         """
521         Resolve all unresolved build and runtime targets
522         """
523         bb.msg.note(1, bb.msg.domain.TaskData, "Resolving missing task queue dependencies")
524         while 1:
525             added = 0
526             for target in self.get_unresolved_build_targets(dataCache):
527                 try:
528                     self.add_provider_internal(cfgData, dataCache, target)
529                     added = added + 1
530                 except bb.providers.NoProvider:
531                     targetid = self.getbuild_id(target)
532                     if self.abort and targetid in self.external_targets:
533                         raise
534                     self.remove_buildtarget(targetid)
535             for target in self.get_unresolved_run_targets(dataCache):
536                 try:
537                     self.add_rprovider(cfgData, dataCache, target)
538                     added = added + 1
539                 except bb.providers.NoRProvider:
540                     self.remove_runtarget(self.getrun_id(target))
541             bb.msg.debug(1, bb.msg.domain.TaskData, "Resolved " + str(added) + " extra dependecies")
542             if added == 0:
543                 break
544
545     def dump_data(self):
546         """
547         Dump some debug information on the internal data structures
548         """
549         bb.msg.debug(3, bb.msg.domain.TaskData, "build_names:")
550         bb.msg.debug(3, bb.msg.domain.TaskData, ", ".join(self.build_names_index))
551         bb.msg.debug(3, bb.msg.domain.TaskData, "run_names:")
552         bb.msg.debug(3, bb.msg.domain.TaskData, ", ".join(self.run_names_index))
553         bb.msg.debug(3, bb.msg.domain.TaskData, "build_targets:")
554         for target in self.build_targets.keys():
555             bb.msg.debug(3, bb.msg.domain.TaskData, " %s: %s" % (self.build_names_index[target], self.build_targets[target]))
556         bb.msg.debug(3, bb.msg.domain.TaskData, "run_targets:")
557         for target in self.run_targets.keys():
558             bb.msg.debug(3, bb.msg.domain.TaskData, " %s: %s" % (self.run_names_index[target], self.run_targets[target]))
559         bb.msg.debug(3, bb.msg.domain.TaskData, "tasks:")
560         for task in range(len(self.tasks_name)):
561             bb.msg.debug(3, bb.msg.domain.TaskData, " (%s)%s - %s: %s" % (
562                 task, 
563                 self.fn_index[self.tasks_fnid[task]], 
564                 self.tasks_name[task], 
565                 self.tasks_tdepends[task]))
566         bb.msg.debug(3, bb.msg.domain.TaskData, "runtime ids (per fn):")
567         for fnid in self.rdepids:
568             bb.msg.debug(3, bb.msg.domain.TaskData, " %s %s: %s" % (fnid, self.fn_index[fnid], self.rdepids[fnid]))
569
570