Include waf as an extracted source directory, rather than as a one-in-a-file script.
[samba.git] / buildtools / wafadmin / Task.py
1 #!/usr/bin/env python
2 # encoding: utf-8
3 # Thomas Nagy, 2005-2008 (ita)
4
5 """
6 Running tasks in parallel is a simple problem, but in practice it is more complicated:
7 * dependencies discovered during the build (dynamic task creation)
8 * dependencies discovered after files are compiled
9 * the amount of tasks and dependencies (graph size) can be huge
10
11 This is why the dependency management is split on three different levels:
12 1. groups of tasks that run all after another group of tasks
13 2. groups of tasks that can be run in parallel
14 3. tasks that can run in parallel, but with possible unknown ad-hoc dependencies
15
16 The point #1 represents a strict sequential order between groups of tasks, for example a compiler is produced
17 and used to compile the rest, whereas #2 and #3 represent partial order constraints where #2 applies to the kind of task
18 and #3 applies to the task instances.
19
20 #1 is held by the task manager: ordered list of TaskGroups (see bld.add_group)
21 #2 is held by the task groups and the task types: precedence after/before (topological sort),
22    and the constraints extracted from file extensions
23 #3 is held by the tasks individually (attribute run_after),
24    and the scheduler (Runner.py) use Task::runnable_status to reorder the tasks
25
26 --
27
28 To try, use something like this in your code:
29 import Constants, Task
30 Task.algotype = Constants.MAXPARALLEL
31
32 --
33
34 There are two concepts with the tasks (individual units of change):
35 * dependency (if 1 is recompiled, recompile 2)
36 * order (run 2 after 1)
37
38 example 1: if t1 depends on t2 and t2 depends on t3 it is not necessary to make t1 depend on t3 (dependency is transitive)
39 example 2: if t1 depends on a node produced by t2, it is not immediately obvious that t1 must run after t2 (order is not obvious)
40
41 The role of the Task Manager is to give the tasks in order (groups of task that may be run in parallel one after the other)
42
43 """
44
45 import os, shutil, sys, re, random, datetime, tempfile, shlex
46 from Utils import md5
47 import Build, Runner, Utils, Node, Logs, Options
48 from Logs import debug, warn, error
49 from Constants import *
50
51 algotype = NORMAL
52 #algotype = JOBCONTROL
53 #algotype = MAXPARALLEL
54
55 COMPILE_TEMPLATE_SHELL = '''
56 def f(task):
57         env = task.env
58         wd = getattr(task, 'cwd', None)
59         p = env.get_flat
60         cmd = \'\'\' %s \'\'\' % s
61         return task.exec_command(cmd, cwd=wd)
62 '''
63
64 COMPILE_TEMPLATE_NOSHELL = '''
65 def f(task):
66         env = task.env
67         wd = getattr(task, 'cwd', None)
68         def to_list(xx):
69                 if isinstance(xx, str): return [xx]
70                 return xx
71         lst = []
72         %s
73         lst = [x for x in lst if x]
74         return task.exec_command(lst, cwd=wd)
75 '''
76
77
78 """
79 Enable different kind of dependency algorithms:
80 1 make groups: first compile all cpps and then compile all links (NORMAL)
81 2 parallelize all (each link task run after its dependencies) (MAXPARALLEL)
82 3 like 1 but provide additional constraints for the parallelization (MAXJOBS)
83
84 In theory 1. will be faster than 2 for waf, but might be slower for builds
85 The scheme 2 will not allow for running tasks one by one so it can cause disk thrashing on huge builds
86 """
87
88 file_deps = Utils.nada
89 """
90 Additional dependency pre-check may be added by replacing the function file_deps.
91 e.g. extract_outputs, extract_deps below.
92 """
93
94 class TaskManager(object):
95         """The manager is attached to the build object, it holds a list of TaskGroup"""
96         def __init__(self):
97                 self.groups = []
98                 self.tasks_done = []
99                 self.current_group = 0
100                 self.groups_names = {}
101
102         def group_name(self, g):
103                 """name for the group g (utility)"""
104                 if not isinstance(g, TaskGroup):
105                         g = self.groups[g]
106                 for x in self.groups_names:
107                         if id(self.groups_names[x]) == id(g):
108                                 return x
109                 return ''
110
111         def group_idx(self, tg):
112                 """group the task generator tg is in"""
113                 se = id(tg)
114                 for i in range(len(self.groups)):
115                         g = self.groups[i]
116                         for t in g.tasks_gen:
117                                 if id(t) == se:
118                                         return i
119                 return None
120
121         def get_next_set(self):
122                 """return the next set of tasks to execute
123                 the first parameter is the maximum amount of parallelization that may occur"""
124                 ret = None
125                 while not ret and self.current_group < len(self.groups):
126                         ret = self.groups[self.current_group].get_next_set()
127                         if ret: return ret
128                         else:
129                                 self.groups[self.current_group].process_install()
130                                 self.current_group += 1
131                 return (None, None)
132
133         def add_group(self, name=None, set=True):
134                 #if self.groups and not self.groups[0].tasks:
135                 #       error('add_group: an empty group is already present')
136                 g = TaskGroup()
137
138                 if name and name in self.groups_names:
139                         error('add_group: name %s already present' % name)
140                 self.groups_names[name] = g
141                 self.groups.append(g)
142                 if set:
143                         self.current_group = len(self.groups) - 1
144
145         def set_group(self, idx):
146                 if isinstance(idx, str):
147                         g = self.groups_names[idx]
148                         for x in xrange(len(self.groups)):
149                                 if id(g) == id(self.groups[x]):
150                                         self.current_group = x
151                 else:
152                         self.current_group = idx
153
154         def add_task_gen(self, tgen):
155                 if not self.groups: self.add_group()
156                 self.groups[self.current_group].tasks_gen.append(tgen)
157
158         def add_task(self, task):
159                 if not self.groups: self.add_group()
160                 self.groups[self.current_group].tasks.append(task)
161
162         def total(self):
163                 total = 0
164                 if not self.groups: return 0
165                 for group in self.groups:
166                         total += len(group.tasks)
167                 return total
168
169         def add_finished(self, tsk):
170                 self.tasks_done.append(tsk)
171                 bld = tsk.generator.bld
172                 if bld.is_install:
173                         f = None
174                         if 'install' in tsk.__dict__:
175                                 f = tsk.__dict__['install']
176                                 # install=0 to prevent installation
177                                 if f: f(tsk)
178                         else:
179                                 tsk.install()
180
181 class TaskGroup(object):
182         "the compilation of one group does not begin until the previous group has finished (in the manager)"
183         def __init__(self):
184                 self.tasks = [] # this list will be consumed
185                 self.tasks_gen = []
186
187                 self.cstr_groups = Utils.DefaultDict(list) # tasks having equivalent constraints
188                 self.cstr_order = Utils.DefaultDict(set) # partial order between the cstr groups
189                 self.temp_tasks = [] # tasks put on hold
190                 self.ready = 0
191                 self.post_funs = []
192
193         def reset(self):
194                 "clears the state of the object (put back the tasks into self.tasks)"
195                 for x in self.cstr_groups:
196                         self.tasks += self.cstr_groups[x]
197                 self.tasks = self.temp_tasks + self.tasks
198                 self.temp_tasks = []
199                 self.cstr_groups = Utils.DefaultDict(list)
200                 self.cstr_order = Utils.DefaultDict(set)
201                 self.ready = 0
202
203         def process_install(self):
204                 for (f, k, kw) in self.post_funs:
205                         f(*k, **kw)
206
207         def prepare(self):
208                 "prepare the scheduling"
209                 self.ready = 1
210                 file_deps(self.tasks)
211                 self.make_cstr_groups()
212                 self.extract_constraints()
213
214         def get_next_set(self):
215                 "next list of tasks to execute using max job settings, returns (maxjobs, task_list)"
216                 global algotype
217                 if algotype == NORMAL:
218                         tasks = self.tasks_in_parallel()
219                         maxj = MAXJOBS
220                 elif algotype == JOBCONTROL:
221                         (maxj, tasks) = self.tasks_by_max_jobs()
222                 elif algotype == MAXPARALLEL:
223                         tasks = self.tasks_with_inner_constraints()
224                         maxj = MAXJOBS
225                 else:
226                         raise Utils.WafError("unknown algorithm type %s" % (algotype))
227
228                 if not tasks: return ()
229                 return (maxj, tasks)
230
231         def make_cstr_groups(self):
232                 "unite the tasks that have similar constraints"
233                 self.cstr_groups = Utils.DefaultDict(list)
234                 for x in self.tasks:
235                         h = x.hash_constraints()
236                         self.cstr_groups[h].append(x)
237
238         def set_order(self, a, b):
239                 self.cstr_order[a].add(b)
240
241         def compare_exts(self, t1, t2):
242                 "extension production"
243                 x = "ext_in"
244                 y = "ext_out"
245                 in_ = t1.attr(x, ())
246                 out_ = t2.attr(y, ())
247                 for k in in_:
248                         if k in out_:
249                                 return -1
250                 in_ = t2.attr(x, ())
251                 out_ = t1.attr(y, ())
252                 for k in in_:
253                         if k in out_:
254                                 return 1
255                 return 0
256
257         def compare_partial(self, t1, t2):
258                 "partial relations after/before"
259                 m = "after"
260                 n = "before"
261                 name = t2.__class__.__name__
262                 if name in Utils.to_list(t1.attr(m, ())): return -1
263                 elif name in Utils.to_list(t1.attr(n, ())): return 1
264                 name = t1.__class__.__name__
265                 if name in Utils.to_list(t2.attr(m, ())): return 1
266                 elif name in Utils.to_list(t2.attr(n, ())): return -1
267                 return 0
268
269         def extract_constraints(self):
270                 "extract the parallelization constraints from the tasks with different constraints"
271                 keys = self.cstr_groups.keys()
272                 max = len(keys)
273                 # hopefully the length of this list is short
274                 for i in xrange(max):
275                         t1 = self.cstr_groups[keys[i]][0]
276                         for j in xrange(i + 1, max):
277                                 t2 = self.cstr_groups[keys[j]][0]
278
279                                 # add the constraints based on the comparisons
280                                 val = (self.compare_exts(t1, t2)
281                                         or self.compare_partial(t1, t2)
282                                         )
283                                 if val > 0:
284                                         self.set_order(keys[i], keys[j])
285                                 elif val < 0:
286                                         self.set_order(keys[j], keys[i])
287
288         def tasks_in_parallel(self):
289                 "(NORMAL) next list of tasks that may be executed in parallel"
290
291                 if not self.ready: self.prepare()
292
293                 keys = self.cstr_groups.keys()
294
295                 unconnected = []
296                 remainder = []
297
298                 for u in keys:
299                         for k in self.cstr_order.values():
300                                 if u in k:
301                                         remainder.append(u)
302                                         break
303                         else:
304                                 unconnected.append(u)
305
306                 toreturn = []
307                 for y in unconnected:
308                         toreturn.extend(self.cstr_groups[y])
309
310                 # remove stuff only after
311                 for y in unconnected:
312                                 try: self.cstr_order.__delitem__(y)
313                                 except KeyError: pass
314                                 self.cstr_groups.__delitem__(y)
315
316                 if not toreturn and remainder:
317                         raise Utils.WafError("circular order constraint detected %r" % remainder)
318
319                 return toreturn
320
321         def tasks_by_max_jobs(self):
322                 "(JOBCONTROL) returns the tasks that can run in parallel with the max amount of jobs"
323                 if not self.ready: self.prepare()
324                 if not self.temp_tasks: self.temp_tasks = self.tasks_in_parallel()
325                 if not self.temp_tasks: return (None, None)
326
327                 maxjobs = MAXJOBS
328                 ret = []
329                 remaining = []
330                 for t in self.temp_tasks:
331                         m = getattr(t, "maxjobs", getattr(self.__class__, "maxjobs", MAXJOBS))
332                         if m > maxjobs:
333                                 remaining.append(t)
334                         elif m < maxjobs:
335                                 remaining += ret
336                                 ret = [t]
337                                 maxjobs = m
338                         else:
339                                 ret.append(t)
340                 self.temp_tasks = remaining
341                 return (maxjobs, ret)
342
343         def tasks_with_inner_constraints(self):
344                 """(MAXPARALLEL) returns all tasks in this group, but add the constraints on each task instance
345                 as an optimization, it might be desirable to discard the tasks which do not have to run"""
346                 if not self.ready: self.prepare()
347
348                 if getattr(self, "done", None): return None
349
350                 for p in self.cstr_order:
351                         for v in self.cstr_order[p]:
352                                 for m in self.cstr_groups[p]:
353                                         for n in self.cstr_groups[v]:
354                                                 n.set_run_after(m)
355                 self.cstr_order = Utils.DefaultDict(set)
356                 self.cstr_groups = Utils.DefaultDict(list)
357                 self.done = 1
358                 return self.tasks[:] # make a copy
359
360 class store_task_type(type):
361         "store the task types that have a name ending in _task into a map (remember the existing task types)"
362         def __init__(cls, name, bases, dict):
363                 super(store_task_type, cls).__init__(name, bases, dict)
364                 name = cls.__name__
365
366                 if name.endswith('_task'):
367                         name = name.replace('_task', '')
368                 if name != 'TaskBase':
369                         TaskBase.classes[name] = cls
370
371 class TaskBase(object):
372         """Base class for all Waf tasks
373
374         The most important methods are (by usual order of call):
375         1 runnable_status: ask the task if it should be run, skipped, or if we have to ask later
376         2 __str__: string to display to the user
377         3 run: execute the task
378         4 post_run: after the task is run, update the cache about the task
379
380         This class should be seen as an interface, it provides the very minimum necessary for the scheduler
381         so it does not do much.
382
383         For illustration purposes, TaskBase instances try to execute self.fun (if provided)
384         """
385
386         __metaclass__ = store_task_type
387
388         color = "GREEN"
389         maxjobs = MAXJOBS
390         classes = {}
391         stat = None
392
393         def __init__(self, *k, **kw):
394                 self.hasrun = NOT_RUN
395
396                 try:
397                         self.generator = kw['generator']
398                 except KeyError:
399                         self.generator = self
400                         self.bld = Build.bld
401
402                 if kw.get('normal', 1):
403                         self.generator.bld.task_manager.add_task(self)
404
405         def __repr__(self):
406                 "used for debugging"
407                 return '\n\t{task: %s %s}' % (self.__class__.__name__, str(getattr(self, "fun", "")))
408
409         def __str__(self):
410                 "string to display to the user"
411                 if hasattr(self, 'fun'):
412                         return 'executing: %s\n' % self.fun.__name__
413                 return self.__class__.__name__ + '\n'
414
415         def exec_command(self, *k, **kw):
416                 "use this for executing commands from tasks"
417                 # TODO in waf 1.6, eliminate bld.exec_command, and move the cwd processing to here
418                 if self.env['env']:
419                         kw['env'] = self.env['env']
420                 return self.generator.bld.exec_command(*k, **kw)
421
422         def runnable_status(self):
423                 "RUN_ME SKIP_ME or ASK_LATER"
424                 return RUN_ME
425
426         def can_retrieve_cache(self):
427                 return False
428
429         def call_run(self):
430                 if self.can_retrieve_cache():
431                         return 0
432                 return self.run()
433
434         def run(self):
435                 "called if the task must run"
436                 if hasattr(self, 'fun'):
437                         return self.fun(self)
438                 return 0
439
440         def post_run(self):
441                 "update the dependency tree (node stats)"
442                 pass
443
444         def display(self):
445                 "print either the description (using __str__) or the progress bar or the ide output"
446                 col1 = Logs.colors(self.color)
447                 col2 = Logs.colors.NORMAL
448
449                 if Options.options.progress_bar == 1:
450                         return self.generator.bld.progress_line(self.position[0], self.position[1], col1, col2)
451
452                 if Options.options.progress_bar == 2:
453                         ela = Utils.get_elapsed_time(self.generator.bld.ini)
454                         try:
455                                 ins  = ','.join([n.name for n in self.inputs])
456                         except AttributeError:
457                                 ins = ''
458                         try:
459                                 outs = ','.join([n.name for n in self.outputs])
460                         except AttributeError:
461                                 outs = ''
462                         return '|Total %s|Current %s|Inputs %s|Outputs %s|Time %s|\n' % (self.position[1], self.position[0], ins, outs, ela)
463
464                 total = self.position[1]
465                 n = len(str(total))
466                 fs = '[%%%dd/%%%dd] %%s%%s%%s' % (n, n)
467                 return fs % (self.position[0], self.position[1], col1, str(self), col2)
468
469         def attr(self, att, default=None):
470                 "retrieve an attribute from the instance or from the class (microoptimization here)"
471                 ret = getattr(self, att, self)
472                 if ret is self: return getattr(self.__class__, att, default)
473                 return ret
474
475         def hash_constraints(self):
476                 "identify a task type for all the constraints relevant for the scheduler: precedence, file production"
477                 a = self.attr
478                 sum = hash((self.__class__.__name__,
479                         str(a('before', '')),
480                         str(a('after', '')),
481                         str(a('ext_in', '')),
482                         str(a('ext_out', '')),
483                         self.__class__.maxjobs))
484                 return sum
485
486         def format_error(self):
487                 "error message to display to the user (when a build fails)"
488                 if getattr(self, "err_msg", None):
489                         return self.err_msg
490                 elif self.hasrun == CRASHED:
491                         try:
492                                 return " -> task failed (err #%d): %r" % (self.err_code, self)
493                         except AttributeError:
494                                 return " -> task failed: %r" % self
495                 elif self.hasrun == MISSING:
496                         return " -> missing files: %r" % self
497                 else:
498                         return ''
499
500         def install(self):
501                 """
502                 installation is performed by looking at the task attributes:
503                 * install_path: installation path like "${PREFIX}/bin"
504                 * filename: install the first node in the outputs as a file with a particular name, be certain to give os.sep
505                 * chmod: permissions
506                 """
507                 bld = self.generator.bld
508                 d = self.attr('install')
509
510                 if self.attr('install_path'):
511                         lst = [a.relpath_gen(bld.srcnode) for a in self.outputs]
512                         perm = self.attr('chmod', O644)
513                         if self.attr('src'):
514                                 # if src is given, install the sources too
515                                 lst += [a.relpath_gen(bld.srcnode) for a in self.inputs]
516                         if self.attr('filename'):
517                                 dir = self.install_path.rstrip(os.sep) + os.sep + self.attr('filename')
518                                 bld.install_as(dir, lst[0], self.env, perm)
519                         else:
520                                 bld.install_files(self.install_path, lst, self.env, perm)
521
522 class Task(TaskBase):
523         """The parent class is quite limited, in this version:
524         * file system interaction: input and output nodes
525         * persistence: do not re-execute tasks that have already run
526         * caching: same files can be saved and retrieved from a cache directory
527         * dependencies:
528                 implicit, like .c files depending on .h files
529                 explicit, like the input nodes or the dep_nodes
530                 environment variables, like the CXXFLAGS in self.env
531         """
532         vars = []
533         def __init__(self, env, **kw):
534                 TaskBase.__init__(self, **kw)
535                 self.env = env
536
537                 # inputs and outputs are nodes
538                 # use setters when possible
539                 self.inputs  = []
540                 self.outputs = []
541
542                 self.dep_nodes = []
543                 self.run_after = []
544
545                 # Additionally, you may define the following
546                 #self.dep_vars  = 'PREFIX DATADIR'
547
548         def __str__(self):
549                 "string to display to the user"
550                 env = self.env
551                 src_str = ' '.join([a.nice_path(env) for a in self.inputs])
552                 tgt_str = ' '.join([a.nice_path(env) for a in self.outputs])
553                 if self.outputs: sep = ' -> '
554                 else: sep = ''
555                 return '%s: %s%s%s\n' % (self.__class__.__name__.replace('_task', ''), src_str, sep, tgt_str)
556
557         def __repr__(self):
558                 return "".join(['\n\t{task: ', self.__class__.__name__, " ", ",".join([x.name for x in self.inputs]), " -> ", ",".join([x.name for x in self.outputs]), '}'])
559
560         def unique_id(self):
561                 "get a unique id: hash the node paths, the variant, the class, the function"
562                 try:
563                         return self.uid
564                 except AttributeError:
565                         "this is not a real hot zone, but we want to avoid surprizes here"
566                         m = md5()
567                         up = m.update
568                         up(self.__class__.__name__)
569                         up(self.env.variant())
570                         p = None
571                         for x in self.inputs + self.outputs:
572                                 if p != x.parent.id:
573                                         p = x.parent.id
574                                         up(x.parent.abspath())
575                                 up(x.name)
576                         self.uid = m.digest()
577                         return self.uid
578
579         def set_inputs(self, inp):
580                 if isinstance(inp, list): self.inputs += inp
581                 else: self.inputs.append(inp)
582
583         def set_outputs(self, out):
584                 if isinstance(out, list): self.outputs += out
585                 else: self.outputs.append(out)
586
587         def set_run_after(self, task):
588                 "set (scheduler) order on another task"
589                 # TODO: handle list or object
590                 assert isinstance(task, TaskBase)
591                 self.run_after.append(task)
592
593         def add_file_dependency(self, filename):
594                 "TODO user-provided file dependencies"
595                 node = self.generator.bld.path.find_resource(filename)
596                 self.dep_nodes.append(node)
597
598         def signature(self):
599                 # compute the result one time, and suppose the scan_signature will give the good result
600                 try: return self.cache_sig[0]
601                 except AttributeError: pass
602
603                 self.m = md5()
604
605                 # explicit deps
606                 exp_sig = self.sig_explicit_deps()
607
608                 # env vars
609                 var_sig = self.sig_vars()
610
611                 # implicit deps
612
613                 imp_sig = SIG_NIL
614                 if self.scan:
615                         try:
616                                 imp_sig = self.sig_implicit_deps()
617                         except ValueError:
618                                 return self.signature()
619
620                 # we now have the signature (first element) and the details (for debugging)
621                 ret = self.m.digest()
622                 self.cache_sig = (ret, exp_sig, imp_sig, var_sig)
623                 return ret
624
625         def runnable_status(self):
626                 "SKIP_ME RUN_ME or ASK_LATER"
627                 #return 0 # benchmarking
628
629                 if self.inputs and (not self.outputs):
630                         if not getattr(self.__class__, 'quiet', None):
631                                 warn("invalid task (no inputs OR outputs): override in a Task subclass or set the attribute 'quiet' %r" % self)
632
633                 for t in self.run_after:
634                         if not t.hasrun:
635                                 return ASK_LATER
636
637                 env = self.env
638                 bld = self.generator.bld
639
640                 # first compute the signature
641                 new_sig = self.signature()
642
643                 # compare the signature to a signature computed previously
644                 key = self.unique_id()
645                 try:
646                         prev_sig = bld.task_sigs[key][0]
647                 except KeyError:
648                         debug("task: task %r must run as it was never run before or the task code changed", self)
649                         return RUN_ME
650
651                 # compare the signatures of the outputs
652                 for node in self.outputs:
653                         variant = node.variant(env)
654                         try:
655                                 if bld.node_sigs[variant][node.id] != new_sig:
656                                         return RUN_ME
657                         except KeyError:
658                                 debug("task: task %r must run as the output nodes do not exist", self)
659                                 return RUN_ME
660
661                 # debug if asked to
662                 if Logs.verbose: self.debug_why(bld.task_sigs[key])
663
664                 if new_sig != prev_sig:
665                         return RUN_ME
666                 return SKIP_ME
667
668         def post_run(self):
669                 "called after a successful task run"
670                 bld = self.generator.bld
671                 env = self.env
672                 sig = self.signature()
673                 ssig = sig.encode('hex')
674
675                 variant = env.variant()
676                 for node in self.outputs:
677                         # check if the node exists ..
678                         try:
679                                 os.stat(node.abspath(env))
680                         except OSError:
681                                 self.hasrun = MISSING
682                                 self.err_msg = '-> missing file: %r' % node.abspath(env)
683                                 raise Utils.WafError
684
685                         # important, store the signature for the next run
686                         bld.node_sigs[variant][node.id] = sig
687                 bld.task_sigs[self.unique_id()] = self.cache_sig
688
689                 # file caching, if possible
690                 # try to avoid data corruption as much as possible
691                 if not Options.cache_global or Options.options.nocache or not self.outputs:
692                         return None
693
694                 if getattr(self, 'cached', None):
695                         return None
696
697                 dname = os.path.join(Options.cache_global, ssig)
698                 tmpdir = tempfile.mkdtemp(prefix=Options.cache_global + os.sep + 'waf')
699
700                 try:
701                         shutil.rmtree(dname)
702                 except:
703                         pass
704
705                 try:
706                         i = 0
707                         for node in self.outputs:
708                                 variant = node.variant(env)
709                                 dest = os.path.join(tmpdir, str(i) + node.name)
710                                 shutil.copy2(node.abspath(env), dest)
711                                 i += 1
712                 except (OSError, IOError):
713                         try:
714                                 shutil.rmtree(tmpdir)
715                         except:
716                                 pass
717                 else:
718                         try:
719                                 os.rename(tmpdir, dname)
720                         except OSError:
721                                 try:
722                                         shutil.rmtree(tmpdir)
723                                 except:
724                                         pass
725                         else:
726                                 try:
727                                         os.chmod(dname, O755)
728                                 except:
729                                         pass
730
731         def can_retrieve_cache(self):
732                 """
733                 Retrieve build nodes from the cache
734                 update the file timestamps to help cleaning the least used entries from the cache
735                 additionally, set an attribute 'cached' to avoid re-creating the same cache files
736
737                 suppose there are files in cache/dir1/file1 and cache/dir2/file2
738                 first, read the timestamp of dir1
739                 then try to copy the files
740                 then look at the timestamp again, if it has changed, the data may have been corrupt (cache update by another process)
741                 should an exception occur, ignore the data
742                 """
743                 if not Options.cache_global or Options.options.nocache or not self.outputs:
744                         return None
745
746                 env = self.env
747                 sig = self.signature()
748                 ssig = sig.encode('hex')
749
750                 # first try to access the cache folder for the task
751                 dname = os.path.join(Options.cache_global, ssig)
752                 try:
753                         t1 = os.stat(dname).st_mtime
754                 except OSError:
755                         return None
756
757                 i = 0
758                 for node in self.outputs:
759                         variant = node.variant(env)
760
761                         orig = os.path.join(dname, str(i) + node.name)
762                         try:
763                                 shutil.copy2(orig, node.abspath(env))
764                                 # mark the cache file as used recently (modified)
765                                 os.utime(orig, None)
766                         except (OSError, IOError):
767                                 debug('task: failed retrieving file')
768                                 return None
769                         i += 1
770
771                 # is it the same folder?
772                 try:
773                         t2 = os.stat(dname).st_mtime
774                 except OSError:
775                         return None
776
777                 if t1 != t2:
778                         return None
779
780                 for node in self.outputs:
781                         self.generator.bld.node_sigs[variant][node.id] = sig
782                         if Options.options.progress_bar < 1:
783                                 self.generator.bld.printout('restoring from cache %r\n' % node.bldpath(env))
784
785                 self.cached = True
786                 return 1
787
788         def debug_why(self, old_sigs):
789                 "explains why a task is run"
790
791                 new_sigs = self.cache_sig
792                 def v(x):
793                         return x.encode('hex')
794
795                 debug("Task %r", self)
796                 msgs = ['Task must run', '* Source file or manual dependency', '* Implicit dependency', '* Environment variable']
797                 tmp = 'task: -> %s: %s %s'
798                 for x in xrange(len(msgs)):
799                         if (new_sigs[x] != old_sigs[x]):
800                                 debug(tmp, msgs[x], v(old_sigs[x]), v(new_sigs[x]))
801
802         def sig_explicit_deps(self):
803                 bld = self.generator.bld
804                 up = self.m.update
805
806                 # the inputs
807                 for x in self.inputs + getattr(self, 'dep_nodes', []):
808                         if not x.parent.id in bld.cache_scanned_folders:
809                                 bld.rescan(x.parent)
810
811                         variant = x.variant(self.env)
812                         try:
813                                 up(bld.node_sigs[variant][x.id])
814                         except KeyError:
815                                 raise Utils.WafError('Missing node signature for %r (required by %r)' % (x, self))
816
817                 # manual dependencies, they can slow down the builds
818                 if bld.deps_man:
819                         additional_deps = bld.deps_man
820                         for x in self.inputs + self.outputs:
821                                 try:
822                                         d = additional_deps[x.id]
823                                 except KeyError:
824                                         continue
825
826                                 for v in d:
827                                         if isinstance(v, Node.Node):
828                                                 bld.rescan(v.parent)
829                                                 variant = v.variant(self.env)
830                                                 try:
831                                                         v = bld.node_sigs[variant][v.id]
832                                                 except KeyError:
833                                                         raise Utils.WafError('Missing node signature for %r (required by %r)' % (v, self))
834                                         elif hasattr(v, '__call__'):
835                                                 v = v() # dependency is a function, call it
836                                         up(v)
837
838                 for x in self.dep_nodes:
839                         v = bld.node_sigs[x.variant(self.env)][x.id]
840                         up(v)
841
842                 return self.m.digest()
843
844         def sig_vars(self):
845                 bld = self.generator.bld
846                 env = self.env
847
848                 # dependencies on the environment vars
849                 act_sig = bld.hash_env_vars(env, self.__class__.vars)
850                 self.m.update(act_sig)
851
852                 # additional variable dependencies, if provided
853                 dep_vars = getattr(self, 'dep_vars', None)
854                 if dep_vars:
855                         self.m.update(bld.hash_env_vars(env, dep_vars))
856
857                 return self.m.digest()
858
859         #def scan(self, node):
860         #       """this method returns a tuple containing:
861         #       * a list of nodes corresponding to real files
862         #       * a list of names for files not found in path_lst
863         #       the input parameters may have more parameters that the ones used below
864         #       """
865         #       return ((), ())
866         scan = None
867
868         # compute the signature, recompute it if there is no match in the cache
869         def sig_implicit_deps(self):
870                 "the signature obtained may not be the one if the files have changed, we do it in two steps"
871
872                 bld = self.generator.bld
873
874                 # get the task signatures from previous runs
875                 key = self.unique_id()
876                 prev_sigs = bld.task_sigs.get(key, ())
877                 if prev_sigs:
878                         try:
879                                 # for issue #379
880                                 if prev_sigs[2] == self.compute_sig_implicit_deps():
881                                         return prev_sigs[2]
882                         except (KeyError, OSError):
883                                 pass
884                         del bld.task_sigs[key]
885                         raise ValueError('rescan')
886
887                 # no previous run or the signature of the dependencies has changed, rescan the dependencies
888                 (nodes, names) = self.scan()
889                 if Logs.verbose:
890                         debug('deps: scanner for %s returned %s %s', str(self), str(nodes), str(names))
891
892                 # store the dependencies in the cache
893                 bld.node_deps[key] = nodes
894                 bld.raw_deps[key] = names
895
896                 # recompute the signature and return it
897                 try:
898                         sig = self.compute_sig_implicit_deps()
899                 except KeyError:
900                         try:
901                                 nodes = []
902                                 for k in bld.node_deps.get(self.unique_id(), []):
903                                         if k.id & 3 == 2: # Node.FILE:
904                                                 if not k.id in bld.node_sigs[0]:
905                                                         nodes.append(k)
906                                         else:
907                                                 if not k.id in bld.node_sigs[self.env.variant()]:
908                                                         nodes.append(k)
909                         except:
910                                 nodes = '?'
911                         raise Utils.WafError('Missing node signature for %r (for implicit dependencies %r)' % (nodes, self))
912
913                 return sig
914
915         def compute_sig_implicit_deps(self):
916                 """it is intended for .cpp and inferred .h files
917                 there is a single list (no tree traversal)
918                 this is the hot spot so ... do not touch"""
919                 upd = self.m.update
920
921                 bld = self.generator.bld
922                 tstamp = bld.node_sigs
923                 env = self.env
924
925                 for k in bld.node_deps.get(self.unique_id(), []):
926                         # unlikely but necessary if it happens
927                         if not k.parent.id in bld.cache_scanned_folders:
928                                 # if the parent folder is removed, an OSError may be thrown
929                                 bld.rescan(k.parent)
930
931                         # if the parent folder is removed, a KeyError will be thrown
932                         if k.id & 3 == 2: # Node.FILE:
933                                 upd(tstamp[0][k.id])
934                         else:
935                                 upd(tstamp[env.variant()][k.id])
936
937                 return self.m.digest()
938
939 def funex(c):
940         dc = {}
941         exec(c, dc)
942         return dc['f']
943
944 reg_act = re.compile(r"(?P<backslash>\\)|(?P<dollar>\$\$)|(?P<subst>\$\{(?P<var>\w+)(?P<code>.*?)\})", re.M)
945 def compile_fun_shell(name, line):
946         """Compiles a string (once) into a function, eg:
947         simple_task_type('c++', '${CXX} -o ${TGT[0]} ${SRC} -I ${SRC[0].parent.bldpath()}')
948
949         The env variables (CXX, ..) on the task must not hold dicts (order)
950         The reserved keywords TGT and SRC represent the task input and output nodes
951
952         quick test:
953         bld(source='wscript', rule='echo "foo\\${SRC[0].name}\\bar"')
954         """
955
956         extr = []
957         def repl(match):
958                 g = match.group
959                 if g('dollar'): return "$"
960                 elif g('backslash'): return '\\\\'
961                 elif g('subst'): extr.append((g('var'), g('code'))); return "%s"
962                 return None
963
964         line = reg_act.sub(repl, line) or line
965
966         parm = []
967         dvars = []
968         app = parm.append
969         for (var, meth) in extr:
970                 if var == 'SRC':
971                         if meth: app('task.inputs%s' % meth)
972                         else: app('" ".join([a.srcpath(env) for a in task.inputs])')
973                 elif var == 'TGT':
974                         if meth: app('task.outputs%s' % meth)
975                         else: app('" ".join([a.bldpath(env) for a in task.outputs])')
976                 else:
977                         if not var in dvars: dvars.append(var)
978                         app("p('%s')" % var)
979         if parm: parm = "%% (%s) " % (',\n\t\t'.join(parm))
980         else: parm = ''
981
982         c = COMPILE_TEMPLATE_SHELL % (line, parm)
983
984         debug('action: %s', c)
985         return (funex(c), dvars)
986
987 def compile_fun_noshell(name, line):
988
989         extr = []
990         def repl(match):
991                 g = match.group
992                 if g('dollar'): return "$"
993                 elif g('subst'): extr.append((g('var'), g('code'))); return "<<|@|>>"
994                 return None
995
996         line2 = reg_act.sub(repl, line)
997         params = line2.split('<<|@|>>')
998
999         buf = []
1000         dvars = []
1001         app = buf.append
1002         for x in xrange(len(extr)):
1003                 params[x] = params[x].strip()
1004                 if params[x]:
1005                         app("lst.extend(%r)" % params[x].split())
1006                 (var, meth) = extr[x]
1007                 if var == 'SRC':
1008                         if meth: app('lst.append(task.inputs%s)' % meth)
1009                         else: app("lst.extend([a.srcpath(env) for a in task.inputs])")
1010                 elif var == 'TGT':
1011                         if meth: app('lst.append(task.outputs%s)' % meth)
1012                         else: app("lst.extend([a.bldpath(env) for a in task.outputs])")
1013                 else:
1014                         app('lst.extend(to_list(env[%r]))' % var)
1015                         if not var in dvars: dvars.append(var)
1016
1017         if params[-1]:
1018                 app("lst.extend(%r)" % shlex.split(params[-1]))
1019
1020         fun = COMPILE_TEMPLATE_NOSHELL % "\n\t".join(buf)
1021         debug('action: %s', fun)
1022         return (funex(fun), dvars)
1023
1024 def compile_fun(name, line, shell=None):
1025         "commands can be launched by the shell or not"
1026         if line.find('<') > 0 or line.find('>') > 0 or line.find('&&') > 0:
1027                 shell = True
1028         #else:
1029         #       shell = False
1030
1031         if shell is None:
1032                 if sys.platform == 'win32':
1033                         shell = False
1034                 else:
1035                         shell = True
1036
1037         if shell:
1038                 return compile_fun_shell(name, line)
1039         else:
1040                 return compile_fun_noshell(name, line)
1041
1042 def simple_task_type(name, line, color='GREEN', vars=[], ext_in=[], ext_out=[], before=[], after=[], shell=None):
1043         """return a new Task subclass with the function run compiled from the line given"""
1044         (fun, dvars) = compile_fun(name, line, shell)
1045         fun.code = line
1046         return task_type_from_func(name, fun, vars or dvars, color, ext_in, ext_out, before, after)
1047
1048 def task_type_from_func(name, func, vars=[], color='GREEN', ext_in=[], ext_out=[], before=[], after=[]):
1049         """return a new Task subclass with the function run compiled from the line given"""
1050         params = {
1051                 'run': func,
1052                 'vars': vars,
1053                 'color': color,
1054                 'name': name,
1055                 'ext_in': Utils.to_list(ext_in),
1056                 'ext_out': Utils.to_list(ext_out),
1057                 'before': Utils.to_list(before),
1058                 'after': Utils.to_list(after),
1059         }
1060
1061         cls = type(Task)(name, (Task,), params)
1062         TaskBase.classes[name] = cls
1063         return cls
1064
1065 def always_run(cls):
1066         """Set all task instances of this class to be executed whenever a build is started
1067         The task signature is calculated, but the result of the comparation between
1068         task signatures is bypassed
1069         """
1070         old = cls.runnable_status
1071         def always(self):
1072                 ret = old(self)
1073                 if ret == SKIP_ME:
1074                         return RUN_ME
1075                 return ret
1076         cls.runnable_status = always
1077
1078 def update_outputs(cls):
1079         """When a command is always run, it is possible that the output only change
1080         sometimes. By default the build node have as a hash the signature of the task
1081         which may not change. With this, the output nodes (produced) are hashed,
1082         and the hashes are set to the build nodes
1083
1084         This may avoid unnecessary recompilations, but it uses more resources
1085         (hashing the output files) so it is not used by default
1086         """
1087         old_post_run = cls.post_run
1088         def post_run(self):
1089                 old_post_run(self)
1090                 bld = self.generator.bld
1091                 for output in self.outputs:
1092                         bld.node_sigs[self.env.variant()][output.id] = Utils.h_file(output.abspath(self.env))
1093                         bld.task_sigs[output.id] = self.unique_id()
1094         cls.post_run = post_run
1095
1096         old_runnable_status = cls.runnable_status
1097         def runnable_status(self):
1098                 status = old_runnable_status(self)
1099                 if status != RUN_ME:
1100                         return status
1101
1102                 uid = self.unique_id()
1103                 try:
1104                         bld = self.outputs[0].__class__.bld
1105                         new_sig  = self.signature()
1106                         prev_sig = bld.task_sigs[uid][0]
1107                         if prev_sig == new_sig:
1108                                 for x in self.outputs:
1109                                         if not x.id in bld.node_sigs[self.env.variant()]:
1110                                                 return RUN_ME
1111                                         if bld.task_sigs[x.id] != uid: # ensure the outputs are associated with *this* task
1112                                                 return RUN_ME
1113                                 return SKIP_ME
1114                 except KeyError:
1115                         pass
1116                 except IndexError:
1117                         pass
1118                 return RUN_ME
1119         cls.runnable_status = runnable_status
1120
1121 def extract_outputs(tasks):
1122         """file_deps: Infer additional dependencies from task input and output nodes
1123         """
1124         v = {}
1125         for x in tasks:
1126                 try:
1127                         (ins, outs) = v[x.env.variant()]
1128                 except KeyError:
1129                         ins = {}
1130                         outs = {}
1131                         v[x.env.variant()] = (ins, outs)
1132
1133                 for a in getattr(x, 'inputs', []):
1134                         try: ins[a.id].append(x)
1135                         except KeyError: ins[a.id] = [x]
1136                 for a in getattr(x, 'outputs', []):
1137                         try: outs[a.id].append(x)
1138                         except KeyError: outs[a.id] = [x]
1139
1140         for (ins, outs) in v.values():
1141                 links = set(ins.iterkeys()).intersection(outs.iterkeys())
1142                 for k in links:
1143                         for a in ins[k]:
1144                                 for b in outs[k]:
1145                                         a.set_run_after(b)
1146
1147 def extract_deps(tasks):
1148         """file_deps: Infer additional dependencies from task input and output nodes and from implicit dependencies
1149         returned by the scanners - that will only work if all tasks are created
1150
1151         this is aimed at people who have pathological builds and who do not care enough
1152         to implement the build dependencies properly
1153
1154         with two loops over the list of tasks, do not expect this to be really fast
1155         """
1156
1157         # first reuse the function above
1158         extract_outputs(tasks)
1159
1160         # map the output nodes to the tasks producing them
1161         out_to_task = {}
1162         for x in tasks:
1163                 v = x.env.variant()
1164                 try:
1165                         lst = x.outputs
1166                 except AttributeError:
1167                         pass
1168                 else:
1169                         for node in lst:
1170                                 out_to_task[(v, node.id)] = x
1171
1172         # map the dependencies found to the tasks compiled
1173         dep_to_task = {}
1174         for x in tasks:
1175                 try:
1176                         x.signature()
1177                 except: # this is on purpose
1178                         pass
1179
1180                 v = x.env.variant()
1181                 key = x.unique_id()
1182                 for k in x.generator.bld.node_deps.get(x.unique_id(), []):
1183                         try: dep_to_task[(v, k.id)].append(x)
1184                         except KeyError: dep_to_task[(v, k.id)] = [x]
1185
1186         # now get the intersection
1187         deps = set(dep_to_task.keys()).intersection(set(out_to_task.keys()))
1188
1189         # and add the dependencies from task to task
1190         for idx in deps:
1191                 for k in dep_to_task[idx]:
1192                         k.set_run_after(out_to_task[idx])
1193
1194         # cleanup, remove the signatures
1195         for x in tasks:
1196                 try:
1197                         delattr(x, 'cache_sig')
1198                 except AttributeError:
1199                         pass
1200