1###############################################################################
2# Copyright (c) 2013 INRIA
3#
4# This program is free software; you can redistribute it and/or modify
5# it under the terms of the GNU General Public License version 2 as
6# published by the Free Software Foundation;
7#
8# This program is distributed in the hope that it will be useful,
9# but WITHOUT ANY WARRANTY; without even the implied warranty of
10# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11# GNU General Public License for more details.
12#
13# You should have received a copy of the GNU General Public License
14# along with this program; if not, write to the Free Software
15# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16#
17# Authors: Daniel Camara  <daniel.camara@inria.fr>
18#          Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19###############################################################################
20'''
21 Dependencies.py
22
23 The purpose of this class is to capture a set of dependencies
24 between a set of objects. The idea is that you have a set of 'targets'
25 which depend on a set of sources. Each target can be the source of another
26 target. There might be cycles but it's a bug and we need to detect it.
27
28 Once we have all dependencies, we need to 'resolve' them. This means
29 that we need to iterate over all targets and invoke a user-provided
30 callback on each target. The tricky thing here is that the user-provided
31 callback is allowed to recursively add new arbitrary dependencies, even
32 to targets which have already been 'resolved' so, we need to be careful
33 to re-resolve the targets to which dependencies have been recursively
34 added.
35'''
36
37import copy
38import sys
39from bake.Exceptions import TaskError
40from bake.ModuleSource import SystemDependency
41
42class CycleDetected:
43    def __init__(self):
44        return
45
46class DependencyUnmet(Exception):
47    def __init__(self, failed, method=''):
48        self._failed = failed
49        self._method = method
50    def method(self):
51        return self._method
52
53    def failed(self):
54        return self._failed
55
56class DependencyLink():
57    """ Stores information about the optional chain link of modules."""
58    moduleProblem=False
59    optionalChain=True
60    module=None
61    def __init__(self, optionalChain, module):
62        self.optionalChain = optionalChain
63        self.module = copy.copy(module)
64
65
66class Target:
67    """ Target modules meta information."""
68
69    def __init__(self, dst, context):
70        self._dst = dst
71        self._src = []
72        self._optional = dict()
73        self._context = context
74        self._dirty = True
75    def is_dirty(self):
76        return self._dirty
77    def dirty(self):
78        self._dirty = True
79    def clean(self):
80        self._dirty = False
81    def add_src(self, src, optional):
82        assert src not in self._src
83        self._src.append(src)
84        self._optional[src] = optional
85    def dst(self):
86        return self._dst
87    def src(self):
88        return self._src
89    def is_src_optional(self,src):
90        assert src in self._optional
91        return self._optional[src]
92    def context(self):
93        return self._context
94
95class Dependencies:
96    def __init__(self):
97        # a dictionnary that maps a string (key) to the only instance
98        # of the class Target that has this string as its target.
99        self._targets = dict()
100        # a dictionnary that maps a string (key) to the list of
101        # instances of the class Target that have this string in their
102        # source list
103        self._sources = dict()
104        # the list of all items
105        self._items = []
106        # Are we currently executing the resolve method. ?
107        self._resolving = False
108        # is there any target that is dirty ?
109        self._dirty = False
110
111    def add_dst(self, dst, context = None):
112        """ Add the dependence"""
113
114        # if the module passed as parameter, dst, is in fact a list of modules
115        if isinstance(dst,list):
116            return [self.add_dst(d,context) for d in dst]
117        # the dependency is already recorded. nothing to do.
118        if dst in self._targets:
119            return
120        # update dependency information
121        target = Target(dst, context)
122        self._targets[dst] = target
123        # mark dirty target and its depending targets
124        self._update_dirty(target)
125
126    def add_dep(self, src, dst, optional = False):
127        """ Registers a dependency regarding one module to another."""
128
129        # if the dependence is in fact for a list of dependencies
130        if isinstance(src,list):
131            return [self.add_dep(s,dst) for s in src]
132        assert dst in self._targets
133        # the dependency is already recorded. nothing to do.
134        target = self._targets[dst]
135        if src in target.src ():
136            return
137
138        # record new dependency
139        target = self._targets[dst]
140        target.add_src(src, optional)
141        if not src in self._sources:
142            self._sources[src] = [target]
143        elif target not in self._sources[src]:
144            self._sources[src].append(target)
145
146        # mark dirty target and its depending targets
147        self._update_dirty(target)
148
149#    def rec_dump(self,target):
150#        """ Debugging purpose function to visualize the targets."""
151#        str = ""
152#        for src in target._dependencies:
153#            str = str + " -> " + self.rec_dump(src)
154#
155#        return target._name
156#
157#    def dump2(self,f,dot=True):
158#        """ Debugging purpose function to visualize the targets."""
159#
160#        f.write('digraph {\n')
161#        for target in self._targets.values():
162#            element = self.rec_dump(target.dst())
163#            f.write('"' + target.dst()._name + '" -> ' + element + ';\n')
164
165
166    def dump(self,f,dot=True):
167        """ Debugging purpose function to visualize the targets."""
168
169        f.write('digraph {\n')
170        for target in self._targets.values():
171            for src in target.src ():
172                f.write('"' + src._name + '" -> "' + target.dst()._name + '";\n')
173        f.write('}')
174
175    def resolve(self, targets, callback = None, n=1):
176        """ Resolve dependencies wrapper function."""
177
178        # raise exceptions to signal errors:
179        # todo:
180        #  CycleDetected ()
181        #  DependencyUnmet ()
182
183        if isinstance(targets,str):
184            targets = [targets]
185
186        self._resolving = True
187        if n == 1:
188            self._resolve_serial(targets, callback)
189        else:
190            self._resolve_parallel(targets, callback, n)
191
192        self._resolving = False
193
194    def _update_dirty(self,target):
195        """Registers dependency added modules for later treatment."""
196
197        if self._resolving:
198            depending = self._depend_on([target])
199            for i in depending:
200                i.dirty()
201            self._dirty = True
202
203    # return list of targets which depend on the input
204    # target, including the input target itself.
205    def _depend_on(self,targets):
206        """ Finds the list of modules that depends on the target module."""
207
208        workqueue = copy.copy(targets)
209        deps = []
210        while len(workqueue) > 0:
211            i = workqueue.pop()
212            if i not in deps:
213                deps.append(i)
214            if i.dst() in self._sources:
215                workqueue.extend(self._sources[i.dst()])
216        return deps
217
218    # return list of targets which need to be resolved
219    # to resolve the input targets
220    def _dependencies_of(self,targets):
221        """ Finds the list of dependencies of the target module."""
222
223        # XXX: should detect cycles here.
224        workqueue = [self._targets[target]
225                     for target in targets
226                        if target in self._targets]
227
228        deps = []
229        while len(workqueue) > 0:
230            i = workqueue.pop()
231            if i not in deps:
232                deps.append(i)
233
234            for src in i.src():
235                if src in self._targets:
236                    workqueue.append(self._targets[src])
237        return deps
238
239    def _is_leaf(self, target):
240        """ Verifies if the target is independent of any module."""
241
242        assert target.dst() in self._targets
243        # a 'leaf' is a target which either has
244        # no source or whose sources are not
245        # targets themselves.
246        for src in target.src():
247            if src in self._targets:
248                return False
249        return True
250
251    # return sorted list of targets such that the first
252    # items must be 'resolved' first.
253    def _sort(self,targets):
254        """ Organize the modules putting on the head the resolved ones."""
255
256        # to calculate this, we first collect the set of targets to
257        # 'resolve'. i.e., the targets that 'targets' depends upon.
258        to_resolve = self._dependencies_of(targets)
259
260        # then, we collect the set of targets that are the leaves
261        # of the dependency graph to initialize our workqueue
262        leaves = [i for i in to_resolve if self._is_leaf(i)]
263        workqueue = leaves
264        prio = dict()
265
266        # let's initialize the piority of every item to zero.
267        for work in to_resolve:
268            prio[work] = 0
269
270        # and, now, we update the priority so that the
271        # deepest targets of the dependency tree have the highest
272        # priority.
273        while len(workqueue) > 0:
274            source = workqueue.pop()
275            if not source.dst() in self._sources:
276                continue
277            for dst in self._sources[source.dst()]:
278                if dst not in to_resolve:
279                    continue
280                prio[dst] = max(prio[dst], prio[source] + 1)
281                workqueue.append(dst)
282
283        # now, build an inverted dictionary of priorities
284        # we want to find the list of targets for each priority
285        prio_inverted = dict()
286        for target in to_resolve:
287            if prio[target] in prio_inverted:
288                prio_inverted[prio[target]].append(target)
289            else:
290                prio_inverted[prio[target]] = [target]
291
292        # generate a sorted list of targets, lowest-priority first
293        sorted_targets = []
294        for key in sorted(prio_inverted.keys()):
295            sorted_targets.extend(sorted(prio_inverted[key], key=self.cmp_to_key(self._cmp)))
296        # convert the list of targets into a list of steps
297        return sorted_targets
298    def cmp_to_key(self, mycmp):
299        'Convert a cmp= function into a key= function'
300        class K(object):
301            def __init__(self, obj, *args):
302                self.obj = obj
303            def __lt__(self, other):
304                return mycmp(self.obj, other.obj) < 0
305            def __gt__(self, other):
306                return mycmp(self.obj, other.obj) > 0
307            def __eq__(self, other):
308                return mycmp(self.obj, other.obj) == 0
309            def __le__(self, other):
310                return mycmp(self.obj, other.obj) <= 0
311            def __ge__(self, other):
312                return mycmp(self.obj, other.obj) >= 0
313            def __ne__(self, other):
314                return mycmp(self.obj, other.obj) != 0
315        return K
316
317
318    def _cmp(self, a, b):
319        return (id(b.dst())-id(a.dst()));
320
321    def _is_clean(self,targets):
322        """ Returns true if the target is clean, resolved, and False if it
323        is dirty, i.e. not all the dependencies resolved yet.
324        """
325
326        for target in targets:
327            if target in self._targets:
328                if self._targets[target].is_dirty():
329                    return False
330        return True
331
332    def _resolve_one_iteration(self, targets, callback):
333        """ 'resolve' all targets which the input targets depend upon
334        in the right order. If resolving one of these targets
335        creates new targets, the function is interrupted and returns
336        False. Otherwise, the function completes and returns True.
337        """
338
339        self._dirty = False
340
341        # sort in a way that the nodes that have no dependencies are first
342        queue = self._sort(targets)
343        dirty = [i for i in queue if i.is_dirty()]
344        for i in dirty:
345            i.clean();
346            assert self._is_clean(i.src())
347            success = True
348            if callback is None and i.context() is not None:
349                try:
350                    success = i.context()()
351                except TaskError as e:
352                    success = False
353                    print("  > Error: " + e._reason)
354#                except SystemExit as e:
355#                    print(sys.exc_info())
356#
357#                    success = False
358#                    print ("  > Error: " + e._reason)
359                except:
360                    success = False
361                    import sys
362                    er = sys.exc_info()[1]
363                    print("  > Error: " + str(er))
364                    from bake.ModuleEnvironment import ModuleEnvironment
365                    if ModuleEnvironment._stopOnError:
366                        er = sys.exc_info()[1]
367                        sys.exit(1)
368
369            elif callback is not None:
370                try:
371                    success = callback(i.dst(), i.context())
372                except TaskError as e:
373                    success = False
374                    print("  > Error: " + e._reason)
375                    from bake.ModuleEnvironment import ModuleEnvironment
376                    if ModuleEnvironment._stopOnError:
377                        er = sys.exc_info()[1]
378                        sys.exit(1)
379                except:
380                    success = False
381                    import sys
382                    er = sys.exc_info()[1]
383                    print("  > Unexpected error: " + str(er))
384                    from bake.ModuleEnvironment import ModuleEnvironment
385                    if ModuleEnvironment._stopOnError:
386                        er = sys.exc_info()[1]
387                        sys.exit(1)
388            if not success:
389                if not i.dst() in self._sources:
390                    raise DependencyUnmet(i.dst())
391                else:
392                    for j in self._sources[i.dst()]:
393                        dependencyTmp= self.dependencies.get(i.dst()._name)
394                        if dependencyTmp:
395                            if isinstance(i.dst()._source, SystemDependency):
396                                tailError =  'not available'
397                            else:
398                                tailError =  'failed'
399
400                            if not dependencyTmp.optionalChain:
401                                raise DependencyUnmet(i.dst(), tailError)
402
403                            if not self.dependencies[i.dst()._name].moduleProblem:
404
405                                print(' > Problem: Optional dependency,'
406                                             ' module "%s" %s\n'
407                                             '   This may reduce the  '
408                                             'functionality of the final build. \n'
409                                             '   However, bake will continue since'
410                                             ' "%s" is not an essential dependency.\n'
411                                             '   For more'
412                                             ' information call bake with -v or -vvv, for full verbose mode.\n'
413                                             % (i.dst()._name,tailError, i.dst()._name))
414                                self.dependencies[i.dst()._name].moduleProblem = True
415            if self._dirty:
416                self._dirty = False
417                return False
418        return True
419
420    def _resolve_serial(self, targets, callback):
421        """ Resolves the dependencies in serial mode."""
422
423        finished = self._resolve_one_iteration(targets, callback)
424        while not finished:
425            finished = self._resolve_one_iteration(targets, callback)
426
427    def _resolve_parallel(self, targets, callback, n):
428        """ Resolves the dependencies in parallel mode. Not yet functional."""
429
430        # todo: implement parallel version
431        self._resolve_serial(targets, callback)
432
433
434    dependencies=dict()
435    modTmp = dict()
436    def recDependencies(self, targetModule, optionalDepChain):
437        existModule = self.dependencies.get(targetModule._name)
438
439        # verify if the module exist or not if does not insert it as a dependency
440        if not existModule:
441            self.dependencies[targetModule._name] = DependencyLink(optionalDepChain, targetModule)
442        elif existModule.optionalChain and not optionalDepChain : # if it exists check if the
443            self.dependencies[targetModule._name].optionalChain = optionalDepChain
444
445        if targetModule._dependencies:
446            for j in targetModule._dependencies:
447                if j._optional:
448                    optionalDepChain= j._optional
449                self.recDependencies(self.modTmp[j._name], optionalDepChain)
450
451
452
453    def checkDependencies(self, targets, modules):
454        enabled = copy.copy(targets)
455
456        for i in modules:
457            self.modTmp[i._name]=i
458
459        for i in enabled:
460            self.dependencies[i._name]= DependencyLink(False, i)
461            if i._dependencies:
462                for j in i._dependencies:
463                    self.recDependencies(self.modTmp[j._name], j._optional)
464
465        return self.dependencies
466
467