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