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