class_docstr: The DestroyHandler class detects when a graph is impossible to evaluate
  because of aliasing and destructive operations.
  
  Several data structures are used to do this.
  
  An Op can use its view_map property to declare that an output may be
  aliased to an input. If that output is destroyed, the input is also
  considered to be destroyed. The view_maps of several Ops can feed into
  one another and form a directed graph. The consequence of destroying any
  variable in such a graph is that all variables in the graph must be
  considered to be destroyed, because they could all be referring to the
  same underlying storage.
  
  In the current implementation, that graph is a tree, and the root of that
  tree is called the foundation.
  
  TODO: why "in the current implementation" ? is there another implementation
        planned?
  TODO: why is the graph a tree? isn't it possible that one variable could
        be aliased to many variables? for example, don't switch and ifelse
        have to do this?
  
  The original DestroyHandler (if 0'ed out above) computed several data
  structures from scratch each time it was asked to validate the graph.
  Because this happens potentially thousands of times and each graph to
  validate is extremely similar to the previous one, computing the
  data structures from scratch repeatedly was wasteful and resulted in
  high compile times for large graphs.
  
  This implementation computes the data structures once at initialization
  and then incrementally updates them.
  
  It is a work in progress. The following data structures have been
  converted to use the incremental strategy:
      <none>
  
  The following data structures remain to be converted:
      <unknown>
class_docstr_tok: ["The","DestroyHandler","class","detects","when","a","graph","is","impossible","to","evaluate","because","of","aliasing","and","destructive","operations",".","Several","data","structures","are","used","to","do","this",".","An","Op","can","use","its","view_map","property","to","declare","that","an","output","may","be","aliased","to","an","input",".","If","that","output","is","destroyed",",","the","input","is","also","considered","to","be","destroyed",".","The","view_maps","of","several","Ops","can","feed","into","one","another","and","form","a","directed","graph",".","The","consequence","of","destroying","any","variable","in","such","a","graph","is","that","all","variables","in","the","graph","must","be","considered","to","be","destroyed",",","because","they","could","all","be","referring","to","the","same","underlying","storage",".","In","the","current","implementation",",","that","graph","is","a","tree",",","and","the","root","of","that","tree","is","called","the","foundation",".","TODO",":","why","``","in","the","current","implementation","''","?","is","there","another","implementation","planned","?","TODO",":","why","is","the","graph","a","tree","?","is","n't","it","possible","that","one","variable","could","be","aliased","to","many","variables","?","for","example",",","do","n't","switch","and","ifelse","have","to","do","this","?","The","original","DestroyHandler","(","if","0'ed","out","above",")","computed","several","data","structures","from","scratch","each","time","it","was","asked","to","validate","the","graph",".","Because","this","happens","potentially","thousands","of","times","and","each","graph","to","validate","is","extremely","similar","to","the","previous","one",",","computing","the","data","structures","from","scratch","repeatedly","was","wasteful","and","resulted","in","high","compile","times","for","large","graphs",".","This","implementation","computes","the","data","structures","once","at","initialization","and","then","incrementally","updates","them",".","It","is","a","work","in","progress",".","The","following","data","structures","have","been","converted","to","use","the","incremental","strategy",":","<","none",">","The","following","data","structures","remain","to","be","converted",":","<","unknown",">"]
docstr: Return orderings induced by destructive operations.
  
  Raise InconsistencyError when
  a) attempting to destroy indestructable variable, or
  b) attempting to destroy a value multiple times, or
  c) an Apply destroys (illegally) one of its own inputs by aliasing
docstr_tok: ["Return","orderings","induced","by","destructive","operations",".","Raise","InconsistencyError","when","a",")","attempting","to","destroy","indestructable","variable",",","or","b",")","attempting","to","destroy","a","value","multiple","times",",","or","c",")","an","Apply","destroys","(","illegally",")","one","of","its","own","inputs","by","aliasing"]
code: def orderings(self, fgraph, ordered=True):
      """
      Return orderings induced by destructive operations.
  
      Raise InconsistencyError when
      a) attempting to destroy indestructable variable, or
      b) attempting to destroy a value multiple times, or
      c) an Apply destroys (illegally) one of its own inputs by aliasing
  
      """
      if ordered:
          set_type = OrderedSet
          rval = OrderedDict()
      else:
          set_type = set
          rval = dict()
  
      if self.destroyers:
          # BUILD DATA STRUCTURES
          # CHECK for multiple destructions during construction of variables
  
          droot, impact, __ignore = self.refresh_droot_impact()
  
          # check for destruction of constants
          illegal_destroy = [
              r
              for r in droot
              if getattr(r.tag, "indestructible", False)
              or isinstance(r, Constant)
          ]
          if illegal_destroy:
              raise InconsistencyError(
                  f"Attempting to destroy indestructible variables: {illegal_destroy}"
              )
  
          # add destroyed variable clients as computational dependencies
          for app in self.destroyers:
              # keep track of clients that should run before the current Apply
              root_clients = set_type()
              # for each destroyed input...
              for (
                  output_idx,
                  input_idx_list,
              ) in app.op.destroy_map.items():
                  destroyed_idx = input_idx_list[0]
                  destroyed_variable = app.inputs[destroyed_idx]
                  root = droot[destroyed_variable]
                  root_impact = impact[root]
                  # we generally want to put all clients of things which depend on root
                  # as pre-requisites of app.
                  # But, app is itself one such client!
                  # App will always be a client of the node we're destroying
                  # (destroyed_variable, but the tricky thing is when it is also a client of
                  # *another variable* viewing on the root.  Generally this is illegal, (e.g.,
                  # add_inplace(x, x.T).  In some special cases though, the in-place op will
                  # actually be able to work properly with multiple destroyed inputs (e.g,
                  # add_inplace(x, x).  An Op that can still work in this case should declare
                  # so via the 'destroyhandler_tolerate_same' attribute or
                  # 'destroyhandler_tolerate_aliased' attribute.
                  #
                  # destroyhandler_tolerate_same should be a list of pairs of the form
                  # [(idx0, idx1), (idx0, idx2), ...]
                  # The first element of each pair is the input index of a destroyed
                  # variable.
                  # The second element of each pair is the index of a different input where
                  # we will permit exactly the same variable to appear.
                  # For example, add_inplace.tolerate_same might be [(0,1)] if the destroyed
                  # input is also allowed to appear as the second argument.
                  #
                  # destroyhandler_tolerate_aliased is the same sort of list of
                  # pairs.
                  # op.destroyhandler_tolerate_aliased = [(idx0, idx1)] tells the
                  # destroyhandler to IGNORE an aliasing between a destroyed
                  # input idx0 and another input idx1.
                  # This is generally a bad idea, but it is safe in some
                  # cases, such as
                  # - the op reads from the aliased idx1 before modifying idx0
                  # - the idx0 and idx1 are guaranteed not to overlap (e.g.
                  #   they are pointed at different rows of a matrix).
                  #
  
                  # CHECK FOR INPUT ALIASING
                  # OPT: pre-compute this on import
                  tolerate_same = getattr(
                      app.op, "destroyhandler_tolerate_same", []
                  )
                  assert isinstance(tolerate_same, list)
                  tolerated = {
                      idx1
                      for idx0, idx1 in tolerate_same
                      if idx0 == destroyed_idx
                  }
                  tolerated.add(destroyed_idx)
                  tolerate_aliased = getattr(
                      app.op, "destroyhandler_tolerate_aliased", []
                  )
                  assert isinstance(tolerate_aliased, list)
                  ignored = {
                      idx1
                      for idx0, idx1 in tolerate_aliased
                      if idx0 == destroyed_idx
                  }
                  for i, input in enumerate(app.inputs):
                      if i in ignored:
                          continue
                      if input in root_impact and (
                          i not in tolerated
                          or input is not destroyed_variable
                      ):
                          raise InconsistencyError(
                              f"Input aliasing: {app} ({destroyed_idx}, {i})"
                          )
  
                  # add the rule: app must be preceded by all other Apply instances that
                  # depend on destroyed_input
                  for r in root_impact:
                      assert not [
                          a for a, c in self.clients[r].items() if not c
                      ]
                      root_clients.update(
                          [a for a, c in self.clients[r].items() if c]
                      )
  
              # app itself is a client of the destroyed inputs,
              # but should not run before itself
              root_clients.remove(app)
              if root_clients:
                  rval[app] = root_clients
  
      return rval
  
imports: import itertools
  from collections import OrderedDict, deque
  import pytensor
  from pytensor.configdefaults import config
  from pytensor.graph.basic import Constant
  from pytensor.graph.features import AlreadyThere, Bookkeeper
  from pytensor.graph.utils import InconsistencyError
  from pytensor.misc.ordered_set import OrderedSet
label_desc: Use image node_id 12 for calling the DestroyHandler obj's underlying member method code with example usage: obj.orderings(fgraph, ordered) and returns: rval