1""" 2Classes and functions for validating graphs that contain view 3and inplace operations. 4 5""" 6from __future__ import absolute_import, print_function, division 7 8from collections import deque, OrderedDict 9 10from six import iteritems 11import itertools 12 13import theano 14from theano import config 15from . import toolbox 16from . import graph 17from theano.misc.ordered_set import OrderedSet 18 19from .fg import InconsistencyError 20 21 22class ProtocolError(Exception): 23 """ 24 Raised when FunctionGraph calls DestroyHandler callbacks in 25 an invalid way, for example, pruning or changing a node that has 26 never been imported. 27 28 """ 29 30 pass 31 32 33def _contains_cycle(fgraph, orderings): 34 """ 35 Function to check if the given graph contains a cycle 36 37 Parameters 38 ---------- 39 fgraph 40 The FunctionGraph to check for cycles. 41 orderings 42 Dictionary specifying extra dependencies besides those encoded in 43 Variable.owner / Apply.inputs. 44 45 If orderings[my_apply] == dependencies, then my_apply is an Apply 46 instance, dependencies is a set of Apply instances, and every member 47 of dependencies must be executed before my_apply. 48 49 The dependencies are typically used to prevent 50 inplace apply nodes from destroying their input before 51 other apply nodes with the same input access it. 52 53 Returns 54 ------- 55 bool 56 True if the graph contains a cycle, False otherwise. 57 58 """ 59 # These are lists of Variable instances 60 outputs = fgraph.outputs 61 62 # this is hard-coded reimplementation of functions from graph.py 63 # reason: go faster, prepare for port to C. 64 # specifically, it could be replaced with a wrapper 65 # around graph.io_toposort that returns True iff io_toposort raises 66 # a ValueError containing the substring 'cycle'. 67 # This implementation is optimized for the destroyhandler and runs 68 # slightly faster than io_toposort. 69 70 # this is performance-critical code. it is the largest single-function 71 # bottleneck when compiling large graphs. 72 assert isinstance(outputs, (tuple, list, deque)) 73 74 # TODO: For more speed - use a defaultdict for the orderings 75 # (defaultdict runs faster than dict in the case where the key 76 # is not in the dictionary, at least in CPython) 77 78 # IG: I tried converting parent_counts to use an id for the key, 79 # so that the dict would do reference counting on its keys. 80 # This caused a slowdown. 81 # Separate benchmark tests showed that calling id is about 82 # half as expensive as a dictionary access, and that the 83 # dictionary also runs slower when storing ids than when 84 # storing objects. 85 86 # dict mapping an Apply or Variable instance to the number 87 # of its parents (including parents imposed by orderings) 88 # that haven't been visited yet 89 parent_counts = {} 90 # dict mapping an Apply or Variable instance to its children 91 node_to_children = {} 92 93 # visitable: A container holding all Variable and Apply instances 94 # that can currently be visited according to the graph topology 95 # (ie, whose parents have already been visited) 96 # TODO: visitable is a fifo_queue. could this run faster if we 97 # implement it as a stack rather than a deque? 98 # TODO: visitable need not be a fifo_queue, any kind of container 99 # that we can throw things into and take things out of quickly will 100 # work. is there another kind of container that could run faster? 101 # we don't care about the traversal order here as much as we do 102 # in io_toposort because we aren't trying to generate an ordering 103 # on the nodes 104 visitable = deque() 105 106 # IG: visitable could in principle be initialized to fgraph.inputs 107 # + fgraph.orphans... if there were an fgraph.orphans structure. 108 # I tried making one and maintaining it caused a huge slowdown. 109 # This may be because I made it a list, so it would have a 110 # deterministic iteration order, in hopes of using it to speed 111 # up toposort as well. 112 # I think since we need to scan through all variables and nodes 113 # to make parent_counts anyway, it's cheap enough to always 114 # detect orphans at cycle detection / toposort time 115 116 # Pass through all the nodes to build visitable, parent_count, and 117 # node_to_children 118 for var in fgraph.variables: 119 120 # this is faster than calling get_parents 121 owner = var.owner 122 # variables don't appear in orderings, so we don't need to worry 123 # about that here 124 if owner: 125 # insert node in node_to_children[r] 126 # (if r is not already in node_to_children, 127 # intialize it to []) 128 node_to_children.setdefault(owner, []).append(var) 129 parent_counts[var] = 1 130 else: 131 visitable.append(var) 132 parent_counts[var] = 0 133 134 for a_n in fgraph.apply_nodes: 135 parents = list(a_n.inputs) 136 # This is faster than conditionally extending 137 # IG: I tried using a shared empty_list = [] constructed 138 # outside of the for loop to avoid constructing multiple 139 # lists, but this was not any faster. 140 parents.extend(orderings.get(a_n, [])) 141 142 if parents: 143 for parent in parents: 144 # insert node in node_to_children[r] 145 # (if r is not already in node_to_children, 146 # intialize it to []) 147 node_to_children.setdefault(parent, []).append(a_n) 148 parent_counts[a_n] = len(parents) 149 else: 150 # an Apply with no inputs would be a weird case, but I'm 151 # not sure we forbid it 152 visitable.append(a_n) 153 parent_counts[a_n] = 0 154 155 # at this point, 156 # parent_counts.keys() == fgraph.apply_nodes + fgraph.variables 157 158 # Now we actually check for cycles 159 # As long as there are nodes that can be visited while respecting 160 # the topology, we keep visiting nodes 161 # If we run out of visitable nodes and we haven't visited all nodes, 162 # then there was a cycle. It blocked the traversal because some 163 # node couldn't be visited until one of its descendants had been 164 # visited too. 165 # This is a standard cycle detection algorithm. 166 167 visited = 0 168 while visitable: 169 # Since each node is inserted into the visitable queue exactly 170 # once, it comes out of the queue exactly once 171 # That means we can decrement its children's unvisited parent count 172 # and increment the visited node count without double-counting 173 node = visitable.popleft() 174 visited += 1 175 for client in node_to_children.get(node, []): 176 parent_counts[client] -= 1 177 # If all of a node's parents have been visited, 178 # it may now be visited too 179 if not parent_counts[client]: 180 visitable.append(client) 181 182 return visited != len(parent_counts) 183 184 185def _build_droot_impact(destroy_handler): 186 droot = {} # destroyed view + nonview variables -> foundation 187 impact = {} # destroyed nonview variable -> it + all views of it 188 root_destroyer = {} # root -> destroyer apply 189 190 for app in destroy_handler.destroyers: 191 for output_idx, input_idx_list in app.op.destroy_map.items(): 192 if len(input_idx_list) != 1: 193 raise NotImplementedError() 194 input_idx = input_idx_list[0] 195 input = app.inputs[input_idx] 196 197 # Find non-view variable which is ultimatly viewed by input. 198 view_i = destroy_handler.view_i 199 _r = input 200 while _r is not None: 201 r = _r 202 _r = view_i.get(r) 203 input_root = r 204 205 if input_root in droot: 206 raise InconsistencyError( 207 "Multiple destroyers of %s" % input_root) 208 droot[input_root] = input_root 209 root_destroyer[input_root] = app 210 211 # The code here add all the variables that are views of r into 212 # an OrderedSet input_impact 213 input_impact = OrderedSet() 214 215 q = deque() 216 q.append(input_root) 217 while len(q) > 0: 218 v = q.popleft() 219 for n in destroy_handler.view_o.get(v, []): 220 input_impact.add(n) 221 q.append(n) 222 223 for v in input_impact: 224 assert v not in droot 225 droot[v] = input_root 226 227 impact[input_root] = input_impact 228 impact[input_root].add(input_root) 229 230 return droot, impact, root_destroyer 231 232 233def fast_inplace_check(inputs): 234 """ 235 Return the variables in inputs that are posible candidate for as inputs of 236 inplace operation. 237 238 Parameters 239 ---------- 240 inputs : list 241 Inputs Variable that you want to use as inplace destination. 242 243 """ 244 fgraph = inputs[0].fgraph 245 Supervisor = theano.compile.function_module.Supervisor 246 protected_inputs = [f.protected for f in fgraph._features 247 if isinstance(f, Supervisor)] 248 protected_inputs = sum(protected_inputs, []) # flatten the list 249 protected_inputs.extend(fgraph.outputs) 250 251 inputs = [i for i in inputs if 252 not isinstance(i, graph.Constant) and 253 not fgraph.has_destroyers([i]) and 254 i not in protected_inputs] 255 return inputs 256 257 258class DestroyHandler(toolbox.Bookkeeper): # noqa 259 """ 260 The DestroyHandler class detects when a graph is impossible to evaluate 261 because of aliasing and destructive operations. 262 263 Several data structures are used to do this. 264 265 An Op can use its view_map property to declare that an output may be 266 aliased to an input. If that output is destroyed, the input is also 267 considered to be destroyed. The view_maps of several Ops can feed into 268 one another and form a directed graph. The consequence of destroying any 269 variable in such a graph is that all variables in the graph must be 270 considered to be destroyed, because they could all be referring to the 271 same underlying storage. 272 273 In the current implementation, that graph is a tree, and the root of that 274 tree is called the foundation. 275 276 TODO: why "in the current implementation" ? is there another implementation 277 planned? 278 TODO: why is the graph a tree? isn't it possible that one variable could 279 be aliased to many variables? for example, don't switch and ifelse 280 have to do this? 281 282 The original DestroyHandler (if 0'ed out above) computed several data 283 structures from scratch each time it was asked to validate the graph. 284 Because this happens potentially thousands of times and each graph to 285 validate is extremely similar to the previous one, computing the 286 data structures from scratch repeatedly was wasteful and resulted in 287 high compile times for large graphs. 288 289 This implementation computes the data structures once at initialization 290 and then incrementally updates them. 291 292 It is a work in progress. The following data structures have been 293 converted to use the incremental strategy: 294 <none> 295 296 The following data structures remain to be converted: 297 <unknown> 298 299 """ 300 pickle_rm_attr = ["destroyers", "has_destroyers"] 301 302 def __init__(self, do_imports_on_attach=True, algo=None): 303 self.fgraph = None 304 self.do_imports_on_attach = do_imports_on_attach 305 306 """ 307 Maps every variable in the graph to its "foundation" (deepest 308 ancestor in view chain). 309 TODO: change name to var_to_vroot. 310 311 """ 312 self.droot = OrderedDict() 313 314 """ 315 Maps a variable to all variables that are indirect or direct views of it 316 (including itself) essentially the inverse of droot. 317 TODO: do all variables appear in this dict, or only those that are 318 foundations? 319 TODO: do only destroyed variables go in here? one old docstring said so. 320 TODO: rename to x_to_views after reverse engineering what x is 321 322 """ 323 self.impact = OrderedDict() 324 325 """ 326 If a var is destroyed, then this dict will map 327 droot[var] to the apply node that destroyed var 328 TODO: rename to vroot_to_destroyer 329 330 """ 331 self.root_destroyer = OrderedDict() 332 if algo is None: 333 algo = config.cycle_detection 334 self.algo = algo 335 self.fail_validate = OrderedDict() 336 337 def on_attach(self, fgraph): 338 """ 339 When attaching to a new fgraph, check that 340 1) This DestroyHandler wasn't already attached to some fgraph 341 (its data structures are only set up to serve one). 342 2) The FunctionGraph doesn't already have a DestroyHandler. 343 This would result in it validating everything twice, causing 344 compilation to be slower. 345 346 Give the FunctionGraph instance: 347 1) A new method "destroyers(var)" 348 TODO: what does this do exactly? 349 2) A new attribute, "destroy_handler" 350 TODO: WRITEME: what does this do besides the checks? 351 352 """ 353 354 # Do the checking # 355 already_there = False 356 if self.fgraph is fgraph: 357 already_there = True 358 if self.fgraph is not None: 359 raise Exception( 360 "A DestroyHandler instance can only serve one" 361 " FunctionGraph. (Matthew 6:24)") 362 for attr in ('destroyers', 'destroy_handler'): 363 if hasattr(fgraph, attr): 364 already_there = True 365 366 if already_there: 367 # FunctionGraph.attach_feature catches AlreadyThere and cancels the attachment 368 raise toolbox.AlreadyThere( 369 "DestroyHandler feature is already present" 370 " or in conflict with another plugin.") 371 372 # Annotate the FunctionGraph # 373 self.unpickle(fgraph) 374 fgraph.destroy_handler = self 375 376 self.fgraph = fgraph 377 self.destroyers = OrderedSet() # set of Apply instances with non-null destroy_map 378 self.view_i = {} # variable -> variable used in calculation 379 self.view_o = {} # variable -> set of variables that use this one as a direct input 380 # clients: how many times does an apply use a given variable 381 self.clients = OrderedDict() # variable -> apply -> ninputs 382 self.stale_droot = True 383 384 self.debug_all_apps = set() 385 if self.do_imports_on_attach: 386 toolbox.Bookkeeper.on_attach(self, fgraph) 387 388 def unpickle(self, fgraph): 389 def get_destroyers_of(r): 390 droot, _, root_destroyer = self.refresh_droot_impact() 391 try: 392 return [root_destroyer[droot[r]]] 393 except Exception: 394 return [] 395 fgraph.destroyers = get_destroyers_of 396 397 def has_destroyers(protected_list): 398 if self.algo != 'fast': 399 droot, _, root_destroyer = self.refresh_droot_impact() 400 for protected_var in protected_list: 401 try: 402 root_destroyer[droot[protected_var]] 403 return True 404 except KeyError: 405 pass 406 return False 407 408 def recursive_destroys_finder(protected_var): 409 # protected_var is the idx'th input of app. 410 for (app, idx) in protected_var.clients: 411 if app == 'output': 412 continue 413 destroy_maps = getattr(app.op, 'destroy_map', {}).values() 414 # If True means that the apply node, destroys the protected_var. 415 if idx in [dmap for sublist in destroy_maps for dmap in sublist]: 416 return True 417 for var_idx in getattr(app.op, 'view_map', {}).keys(): 418 if idx in app.op.view_map[var_idx]: 419 # We need to recursivly check the destroy_map of all the 420 # outputs that we have a view_map on. 421 if recursive_destroys_finder(app.outputs[var_idx]): 422 return True 423 return False 424 425 for protected_var in protected_list: 426 if recursive_destroys_finder(protected_var): 427 return True 428 return False 429 430 fgraph.has_destroyers = has_destroyers 431 432 def refresh_droot_impact(self): 433 """ 434 Makes sure self.droot, self.impact, and self.root_destroyer are up to 435 date, and returns them (see docstrings for these properties above). 436 437 """ 438 if self.stale_droot: 439 self.droot, self.impact, self.root_destroyer =\ 440 _build_droot_impact(self) 441 self.stale_droot = False 442 return self.droot, self.impact, self.root_destroyer 443 444 def on_detach(self, fgraph): 445 if fgraph is not self.fgraph: 446 raise Exception("detaching wrong fgraph", fgraph) 447 del self.destroyers 448 del self.view_i 449 del self.view_o 450 del self.clients 451 del self.stale_droot 452 assert self.fgraph.destroyer_handler is self 453 delattr(self.fgraph, 'destroyers') 454 delattr(self.fgraph, 'has_destroyers') 455 delattr(self.fgraph, 'destroy_handler') 456 self.fgraph = None 457 458 def fast_destroy(self, app, reason): 459 """ 460 Do the check for only 1 level. 461 462 For now: 463 - Destroyed variables can have only 1 clients. 464 - Allow view to have multiple clients. 465 - Allow sequence of view. 466 - But don't allow to destroy view 467 """ 468 dm = getattr(app.op, 'destroy_map', None) 469 if not dm: 470 return 471 inputs = set(itertools.chain.from_iterable(dm.values())) # list of app's destroyed inputs 472 for inp_idx in inputs: 473 inp = app.inputs[inp_idx] 474 if getattr(inp.tag, 'indestructible', False) or isinstance(inp, graph.Constant): 475 self.fail_validate[app] = InconsistencyError( 476 "Attempting to destroy indestructible variables: %s" % 477 inp) 478 elif len(inp.clients) > 1: 479 self.fail_validate[app] = theano.gof.InconsistencyError( 480 "Destroyed variable has more than one client. " + str(reason)) 481 elif inp.owner: 482 app2 = inp.owner 483 inp_idx2 = app2.outputs.index(inp) 484 v = getattr(app2.op, 'view_map', {}) 485 d = getattr(app2.op, 'destroy_map', {}) 486 if v: 487 v = v.get(inp_idx2, []) 488 if len(v) > 0: 489 self.fail_validate[app] = theano.gof.InconsistencyError( 490 "Destroyed variable has view_map. " + str(reason)) 491 elif d: 492 d = d.get(inp_idx2, []) 493 if len(d) > 0: 494 self.fail_validate[app] = theano.gof.InconsistencyError( 495 "Destroyed variable has destroy_map. " + str(reason)) 496 497 # These 2 assertions are commented since this function is called so many times 498 # but they should be true. 499 # assert len(v) <= 1 500 # assert len(d) <= 1 501 502 def on_import(self, fgraph, app, reason): 503 """ 504 Add Apply instance to set which must be computed. 505 506 """ 507 if app in self.debug_all_apps: 508 raise ProtocolError("double import") 509 self.debug_all_apps.add(app) 510 # print 'DH IMPORT', app, id(app), id(self), len(self.debug_all_apps) 511 512 # If it's a destructive op, add it to our watch list 513 dmap = getattr(app.op, 'destroy_map', None) 514 vmap = getattr(app.op, 'view_map', {}) 515 if dmap: 516 self.destroyers.add(app) 517 if self.algo == 'fast': 518 self.fast_destroy(app, reason) 519 520 # add this symbol to the forward and backward maps 521 for o_idx, i_idx_list in iteritems(vmap): 522 if len(i_idx_list) > 1: 523 raise NotImplementedError( 524 'destroying this output invalidates multiple inputs', 525 (app. op)) 526 o = app.outputs[o_idx] 527 i = app.inputs[i_idx_list[0]] 528 self.view_i[o] = i 529 self.view_o.setdefault(i, OrderedSet()).add(o) 530 531 # update self.clients 532 for i, input in enumerate(app.inputs): 533 self.clients.setdefault(input, OrderedDict()).setdefault(app, 0) 534 self.clients[input][app] += 1 535 536 for i, output in enumerate(app.outputs): 537 self.clients.setdefault(output, OrderedDict()) 538 539 self.stale_droot = True 540 541 def on_prune(self, fgraph, app, reason): 542 """ 543 Remove Apply instance from set which must be computed. 544 545 """ 546 if app not in self.debug_all_apps: 547 raise ProtocolError("prune without import") 548 self.debug_all_apps.remove(app) 549 550 # UPDATE self.clients 551 for input in set(app.inputs): 552 del self.clients[input][app] 553 554 if getattr(app.op, 'destroy_map', OrderedDict()): 555 self.destroyers.remove(app) 556 557 # Note: leaving empty client dictionaries in the struct. 558 # Why? It's a pain to remove them. I think they aren't doing any harm, they will be 559 # deleted on_detach(). 560 561 # UPDATE self.view_i, self.view_o 562 for o_idx, i_idx_list in iteritems(getattr(app.op, 'view_map', 563 OrderedDict())): 564 if len(i_idx_list) > 1: 565 # destroying this output invalidates multiple inputs 566 raise NotImplementedError() 567 o = app.outputs[o_idx] 568 i = app.inputs[i_idx_list[0]] 569 570 del self.view_i[o] 571 572 self.view_o[i].remove(o) 573 if not self.view_o[i]: 574 del self.view_o[i] 575 576 self.stale_droot = True 577 if app in self.fail_validate: 578 del self.fail_validate[app] 579 580 def on_change_input(self, fgraph, app, i, old_r, new_r, reason): 581 """ 582 app.inputs[i] changed from old_r to new_r. 583 584 """ 585 if app == 'output': 586 # app == 'output' is special key that means FunctionGraph is redefining which nodes are being 587 # considered 'outputs' of the graph. 588 pass 589 else: 590 if app not in self.debug_all_apps: 591 raise ProtocolError("change without import") 592 593 # UPDATE self.clients 594 self.clients[old_r][app] -= 1 595 if self.clients[old_r][app] == 0: 596 del self.clients[old_r][app] 597 598 self.clients.setdefault(new_r, OrderedDict()).setdefault(app, 0) 599 self.clients[new_r][app] += 1 600 601 # UPDATE self.view_i, self.view_o 602 for o_idx, i_idx_list in iteritems(getattr(app.op, 'view_map', 603 OrderedDict())): 604 if len(i_idx_list) > 1: 605 # destroying this output invalidates multiple inputs 606 raise NotImplementedError() 607 i_idx = i_idx_list[0] 608 output = app.outputs[o_idx] 609 if i_idx == i: 610 if app.inputs[i_idx] is not new_r: 611 raise ProtocolError("wrong new_r on change") 612 613 self.view_i[output] = new_r 614 615 self.view_o[old_r].remove(output) 616 if not self.view_o[old_r]: 617 del self.view_o[old_r] 618 619 self.view_o.setdefault(new_r, OrderedSet()).add(output) 620 621 if self.algo == 'fast': 622 if app in self.fail_validate: 623 del self.fail_validate[app] 624 self.fast_destroy(app, reason) 625 self.stale_droot = True 626 627 def validate(self, fgraph): 628 """ 629 Return None. 630 631 Raise InconsistencyError when 632 a) orderings() raises an error 633 b) orderings cannot be topologically sorted. 634 635 """ 636 if self.destroyers: 637 if self.algo == 'fast': 638 if self.fail_validate: 639 app_err_pairs = self.fail_validate 640 self.fail_validate = OrderedDict() 641 # self.fail_validate can only be a hint that maybe/probably 642 # there is a cycle.This is because inside replace() we could 643 # record many reasons to not accept a change, but we don't 644 # know which one will fail first inside validate(). Thus,the 645 # graph might have already changed when we raise the 646 # self.fail_validate error. So before raising the error, we 647 # double check here. 648 for app in app_err_pairs: 649 if app in fgraph.apply_nodes: 650 self.fast_destroy(app, 'validate') 651 if self.fail_validate: 652 self.fail_validate = app_err_pairs 653 raise app_err_pairs[app] 654 else: 655 ords = self.orderings(fgraph, ordered=False) 656 if _contains_cycle(fgraph, ords): 657 raise InconsistencyError("Dependency graph contains cycles") 658 else: 659 # James's Conjecture: 660 # If there are no destructive ops, then there can be no cycles. 661 662 # FB: This isn't always True. It can happened that 663 # optimization introduce node that depend on itself. This 664 # is very rare and should not happen in general. It will be 665 # caught later. The error will be far from the source. But 666 # doing this conjecture should speed up compilation most of 667 # the time. The user should create such dependency except 668 # if he mess too much with the internal. 669 pass 670 return True 671 672 def orderings(self, fgraph, ordered=True): 673 """ 674 Return orderings induced by destructive operations. 675 676 Raise InconsistencyError when 677 a) attempting to destroy indestructable variable, or 678 b) attempting to destroy a value multiple times, or 679 c) an Apply destroys (illegally) one of its own inputs by aliasing 680 681 """ 682 if ordered: 683 set_type = OrderedSet 684 rval = OrderedDict() 685 else: 686 set_type = set 687 rval = dict() 688 689 if self.destroyers: 690 # BUILD DATA STRUCTURES 691 # CHECK for multiple destructions during construction of variables 692 693 droot, impact, __ignore = self.refresh_droot_impact() 694 695 # check for destruction of constants 696 illegal_destroy = [r for r in droot if 697 getattr(r.tag, 'indestructible', False) or 698 isinstance(r, graph.Constant)] 699 if illegal_destroy: 700 raise InconsistencyError( 701 "Attempting to destroy indestructible variables: %s" % 702 illegal_destroy) 703 704 # add destroyed variable clients as computational dependencies 705 for app in self.destroyers: 706 # keep track of clients that should run before the current Apply 707 root_clients = set_type() 708 # for each destroyed input... 709 for output_idx, input_idx_list in iteritems(app.op.destroy_map): 710 destroyed_idx = input_idx_list[0] 711 destroyed_variable = app.inputs[destroyed_idx] 712 root = droot[destroyed_variable] 713 root_impact = impact[root] 714 # we generally want to put all clients of things which depend on root 715 # as pre-requisites of app. 716 # But, app is itself one such client! 717 # App will always be a client of the node we're destroying 718 # (destroyed_variable, but the tricky thing is when it is also a client of 719 # *another variable* viewing on the root. Generally this is illegal, (e.g., 720 # add_inplace(x, x.T). In some special cases though, the in-place op will 721 # actually be able to work properly with multiple destroyed inputs (e.g, 722 # add_inplace(x, x). An Op that can still work in this case should declare 723 # so via the 'destroyhandler_tolerate_same' attribute or 724 # 'destroyhandler_tolerate_aliased' attribute. 725 # 726 # destroyhandler_tolerate_same should be a list of pairs of the form 727 # [(idx0, idx1), (idx0, idx2), ...] 728 # The first element of each pair is the input index of a destroyed 729 # variable. 730 # The second element of each pair is the index of a different input where 731 # we will permit exactly the same variable to appear. 732 # For example, add_inplace.tolerate_same might be [(0,1)] if the destroyed 733 # input is also allowed to appear as the second argument. 734 # 735 # destroyhandler_tolerate_aliased is the same sort of list of 736 # pairs. 737 # op.destroyhandler_tolerate_aliased = [(idx0, idx1)] tells the 738 # destroyhandler to IGNORE an aliasing between a destroyed 739 # input idx0 and another input idx1. 740 # This is generally a bad idea, but it is safe in some 741 # cases, such as 742 # - the op reads from the aliased idx1 before modifying idx0 743 # - the idx0 and idx1 are guaranteed not to overlap (e.g. 744 # they are pointed at different rows of a matrix). 745 # 746 747 # CHECK FOR INPUT ALIASING 748 # OPT: pre-compute this on import 749 tolerate_same = getattr(app.op, 750 'destroyhandler_tolerate_same', []) 751 assert isinstance(tolerate_same, list) 752 tolerated = set(idx1 for idx0, idx1 in tolerate_same 753 if idx0 == destroyed_idx) 754 tolerated.add(destroyed_idx) 755 tolerate_aliased = getattr( 756 app.op, 'destroyhandler_tolerate_aliased', []) 757 assert isinstance(tolerate_aliased, list) 758 ignored = set(idx1 for idx0, idx1 in tolerate_aliased 759 if idx0 == destroyed_idx) 760 for i, input in enumerate(app.inputs): 761 if i in ignored: 762 continue 763 if input in root_impact \ 764 and (i not in tolerated or 765 input is not destroyed_variable): 766 raise InconsistencyError("Input aliasing: %s (%i, %i)" 767 % (app, destroyed_idx, i)) 768 769 # add the rule: app must be preceded by all other Apply instances that 770 # depend on destroyed_input 771 for r in root_impact: 772 assert not [a for a, c in self.clients[r].items() if not c] 773 root_clients.update([a for a, c in self.clients[r].items() if c]) 774 775 # app itself is a client of the destroyed inputs, 776 # but should not run before itself 777 root_clients.remove(app) 778 if root_clients: 779 rval[app] = root_clients 780 781 return rval 782