class_docstr: Parameters
  ----------
  inputs
      Inputs of the inner function of scan.
  outputs
      Outputs of the inner function of scan.
  info
      Dictionary containing different properties of the scan op (like number
      of different types of arguments, name, mode, if it should run on GPU or
      not, etc.).
  typeConstructor
      Function that constructs an equivalent to Theano TensorType.
  
  Notes
  -----
  ``typeConstructor`` had been added to refactor how
  Theano deals with the GPU. If it runs on the GPU, scan needs
  to construct certain outputs (those who reside in the GPU
  memory) as the GPU-specific type.  However we can not import
  gpu code in this file (as it is in sandbox, and not available
  on each machine) so the workaround is that the GPU
  optimization passes to the constructor of this class a
  function that is able to construct a GPU type. This way the
  class Scan does not need to be aware of the details for the
  GPU, it just constructs any tensor using this function (which
  by default constructs normal tensors).
class_docstr_tok: ["Parameters","--","--","--","--","--","inputs","Inputs","of","the","inner","function","of","scan",".","outputs","Outputs","of","the","inner","function","of","scan",".","info","Dictionary","containing","different","properties","of","the","scan","op","(","like","number","of","different","types","of","arguments",",","name",",","mode",",","if","it","should","run","on","GPU","or","not",",","etc.",")",".","typeConstructor","Function","that","constructs","an","equivalent","to","Theano","TensorType",".","Notes","--","--","-","``","typeConstructor","``","had","been","added","to","refactor","how","Theano","deals","with","the","GPU",".","If","it","runs","on","the","GPU",",","scan","needs","to","construct","certain","outputs","(","those","who","reside","in","the","GPU","memory",")","as","the","GPU-specific","type",".","However","we","can","not","import","gpu","code","in","this","file","(","as","it","is","in","sandbox",",","and","not","available","on","each","machine",")","so","the","workaround","is","that","the","GPU","optimization","passes","to","the","constructor","of","this","class","a","function","that","is","able","to","construct","a","GPU","type",".","This","way","the","class","Scan","does","not","need","to","be","aware","of","the","details","for","the","GPU",",","it","just","constructs","any","tensor","using","this","function","(","which","by","default","constructs","normal","tensors",")","."]
docstr: The args are packed like this:
  
      n_steps
  
      X sequence inputs x_1, x_2, ... x_<self.n_seqs>
  
      Y initial states (u_1, u_2, ... u_<self.n_outs>) for our
      outputs. Each must have appropriate length (T_1, T_2, ..., T_Y).
  
      W other inputs w_1, w_2, ... w_W
  
  There are at least 1 + self.n_seqs + self.n_outs inputs, and the
  ones above this number are passed to the scanned function as
  non-sequential inputs.
  
  The outputs are more straightforward:
  
      Y sequence outputs y_1, y_2, ... y_<self.n_outs>
docstr_tok: ["The","args","are","packed","like","this",":","n_steps","X","sequence","inputs","x_1",",","x_2",",","...","x_","<","self.n_seqs",">","Y","initial","states","(","u_1",",","u_2",",","...","u_","<","self.n_outs",">",")","for","our","outputs",".","Each","must","have","appropriate","length","(","T_1",",","T_2",",","...",",","T_Y",")",".","W","other","inputs","w_1",",","w_2",",","...","w_W","There","are","at","least","1","+","self.n_seqs","+","self.n_outs","inputs",",","and","the","ones","above","this","number","are","passed","to","the","scanned","function","as","non-sequential","inputs",".","The","outputs","are","more","straightforward",":","Y","sequence","outputs","y_1",",","y_2",",","...","y_","<","self.n_outs",">"]
code: def execute(self, node, args, outs):
      """
      The args are packed like this:
  
          n_steps
  
          X sequence inputs x_1, x_2, ... x_<self.n_seqs>
  
          Y initial states (u_1, u_2, ... u_<self.n_outs>) for our
          outputs. Each must have appropriate length (T_1, T_2, ..., T_Y).
  
          W other inputs w_1, w_2, ... w_W
  
      There are at least 1 + self.n_seqs + self.n_outs inputs, and the
      ones above this number are passed to the scanned function as
      non-sequential inputs.
  
      The outputs are more straightforward:
  
          Y sequence outputs y_1, y_2, ... y_<self.n_outs>
  
      """
      # 1. Unzip the number of steps and sequences. If number of steps is
      # negative flip sequences around, and make n_steps positive
      t0_call = time.time()
      t_fn = 0
      n_steps = args[0]
      seqs = []
      if n_steps < 0:
          # History, in the past, this was used for backward
          # scan. Now we reverse the inputs outside of scan.
          raise IndexError(
              "Scan was asked to run for negative number of step %d"
              % n_steps
          )
      elif n_steps == 0:
          raise NotImplementedError(
              "We didn't implemented yet the case where scan do 0 iteration"
          )
      else:
          for idx, seq in enumerate(args[1 : self.seqs_arg_offset]):
              if seq.shape[0] < n_steps:
                  raise ValueError(
                      (
                          "Sequence is shorter then the required "
                          "number of steps : (n_steps, seq, "
                          "seq.shape):"
                      ),
                      n_steps,
                      node.inputs[1 + idx],
                      seq.shape,
                  )
              seqs.append(seq)
  
      # 2. Allocate memory for the outputs. Construct the list:
      #       store_steps  -- map containting the length of each output
      #       pos          -- map containing the current position of each
      #                       output
  
      store_steps = [
          arg.shape[0]
          for arg in args[self.seqs_arg_offset : self.shared_arg_offset]
      ]
      store_steps += [
          arg
          for arg in args[
              self.nit_sot_arg_offset : self.nit_sot_arg_offset
              + self.n_nit_sot
          ]
      ]
  
      pos = [
          (-self.mintaps[idx]) % store_steps[idx]
          for idx in xrange(self.n_outs + self.n_nit_sot)
      ]
      if not getattr(self, "destroy_map", None):
          self.destroy_map = OrderedDict()
      # 2.1 Create storage space for outputs
      for idx in xrange(self.n_outs):
          if idx in self.destroy_map:
              # ^ Case 1. Outputs should be computed inplace of their
              # initial state
              outs[idx][0] = args[self.seqs_arg_offset + idx]
          elif (
              outs[idx][0] is not None
              and outs[idx][0].shape[1:]
              == args[self.seqs_arg_offset + idx].shape[1:]
              and outs[idx][0].shape[0] >= store_steps[idx]
          ):
              # Put in the values of the initial state
              outs[idx][0] = outs[idx][0][: store_steps[idx]]
              if idx > self.n_mit_mot:
                  l = -self.mintaps[idx]
                  outs[idx][0][:l] = args[self.seqs_arg_offset + idx][
                      :l
                  ]
              else:
                  outs[idx][0][:] = args[self.seqs_arg_offset + idx]
          else:
              outs[idx][0] = args[self.seqs_arg_offset + idx].copy()
  
      offset = self.nit_sot_arg_offset + self.n_nit_sot
      other_args = args[offset:]
      input_storage = self.fn.input_storage
      nb_mitmot_in = sum(map(len, self.tap_array[: self.n_mit_mot]))
      old_mitmot_input_storage = [None] * nb_mitmot_in
      old_mitmot_input_data = [None] * nb_mitmot_in
      output_storage = self.fn.output_storage
      old_output_storage = [None] * len(output_storage)
      old_output_data = [None] * len(output_storage)
      fn = self.fn.fn
      offset = (
          self.n_seqs
          + sum(map(len, self.tap_array[: self.n_outs]))
          + self.n_shared_outs
      )
      for idx in xrange(len(other_args)):
          input_storage[idx + offset].storage[0] = other_args[idx]
  
      i = 0
      cond = True
      # ############# THE MAIN LOOP ##############
      # for i in xrange(n_steps):
      while (i < n_steps) and cond:
          # sequences over which scan iterates
          # 3. collect input slices
          for idx in xrange(self.n_seqs):
              if self.vector_seqs[idx]:
                  input_storage[idx].storage[0] = seqs[idx][
                      i : i + 1
                  ].reshape(())
              else:
                  input_storage[idx].storage[0] = seqs[idx][i]
  
          offset = self.n_seqs
          for idx in xrange(self.n_outs):
              if self.vector_outs[idx]:
                  for tap in self.tap_array[idx]:
                      _idx = (pos[idx] + tap) % store_steps[idx]
                      input_storage[offset].storage[0] = outs[idx][0][
                          _idx : _idx + 1
                      ].reshape(())
                      offset += 1
              else:
                  for tap in self.tap_array[idx]:
                      _idx = (pos[idx] + tap) % store_steps[idx]
                      input_storage[offset].storage[0] = outs[idx][0][
                          _idx
                      ]
                      offset += 1
  
          a_offset = self.shared_arg_offset
          o_offset = self.n_outs + self.n_nit_sot
          if i == 0:
              for j in xrange(self.n_shared_outs):
                  input_storage[offset].storage[0] = args[a_offset + j]
                  offset += 1
          else:
              for j in xrange(self.n_shared_outs):
                  input_storage[offset].storage[0] = outs[o_offset + j][
                      0
                  ]
                  offset += 1
  
          # 4. collecting slices where the output should be stored
  
          # 4.1. Collect slices for mitmots
          offset = 0
          for idx in xrange(self.n_mit_mot_outs):
              if not self.mitmots_preallocated[idx]:
                  output_storage[offset].storage[0] = None
                  offset += 1
  
          # 4.2. Collect slices for mitsots, sitsots and nitsots
          if i != 0:
              for idx in xrange(
                  self.n_outs + self.n_nit_sot - self.n_mit_mot
              ):
                  if (
                      store_steps[idx + self.n_mit_mot] == 1
                      or self.vector_outs[idx + self.n_mit_mot]
                  ):
                      output_storage[idx + offset].storage[0] = None
                  else:
                      _pos0 = idx + self.n_mit_mot
                      output_storage[idx + offset].storage[0] = outs[
                          _pos0
                      ][0][pos[_pos0]]
          else:
              for idx in xrange(
                  self.n_outs + self.n_nit_sot - self.n_mit_mot
              ):
                  output_storage[idx + offset].storage[0] = None
  
          # 4.3. Collect slices for shared outputs
          offset += self.n_outs + self.n_nit_sot - self.n_mit_mot
          for idx in xrange(self.n_shared_outs):
              output_storage[idx + offset].storage[0] = None
  
          # 4.4. If there is a condition add it to the mix
          if self.as_while:
              pdx = offset + self.n_shared_outs
              output_storage[pdx].storage[0] = None
  
          # 4.5. Keep a reference to the variables (ndarrays, GpuArrays,
          # etc) currently in the output_storage to be able to compare them
          # with the actual outputs of the inner function after its
          # execution. Also keep pointers to their data to be able to detect
          # cases where outputs reused the allocated object but alter the
          # memory region they refer to.
          for idx in xrange(len(output_storage)):
              var = output_storage[idx].storage[0]
              old_output_storage[idx] = var
  
              if var is None:
                  old_output_data[idx] = None
              elif self.outs_is_tensor[idx]:
                  old_output_data[idx] = var.data
              else:
                  old_output_data[idx] = var.gpudata
  
          # 4.6. Keep a reference to the variables (ndarrays, GpuArrays,
          # etc) associated with mitmot inputs currently in the
          # input_storage to be able to compare them with the content of the
          # input_storage after the execution of the function. Also keep
          # pointers to their data to be able to detect cases where outputs
          # reused the allocated object but alter the memory region they
          # refer to.
          for idx in xrange(nb_mitmot_in):
              var = input_storage[idx + self.n_seqs].storage[0]
              old_mitmot_input_storage[idx] = var
  
              if var is None:
                  old_mitmot_input_data[idx] = None
              elif self.inps_is_tensor[idx + self.n_seqs]:
                  old_mitmot_input_data[idx] = var.data
              else:
                  old_mitmot_input_data[idx] = var.gpudata
  
          # 5.1 compute outputs
          t0_fn = time.time()
  
          try:
              fn()
          except Exception:
              if hasattr(fn, "position_of_error"):
                  # this is a new vm-provided function or c linker
                  # they need this because the exception manipulation
                  # done by raise_with_op is not implemented in C.
                  if hasattr(fn, "thunks"):
                      # For the CVM
                      gof.link.raise_with_op(
                          fn.nodes[fn.position_of_error],
                          fn.thunks[fn.position_of_error],
                      )
                  else:
                      # For the c linker
                      # We don't have access from python to all the
                      # temps values So for now, we just don't print
                      # the extra shapes/strides info
                      gof.vm.raise_with_op(
                          fn.nodes[fn.position_of_error]
                      )
              else:
                  # old-style linkers raise their own exceptions
                  raise
  
          dt_fn = time.time() - t0_fn
          if self.as_while:
              pdx = offset + self.n_shared_outs
              cond = output_storage[pdx].storage[0] == 0
  
          # 5.2. By calling fn() directly instead of calling the theano
          # function, it is possible that the updates have not been
          # performed. Perform the updates if needed.
          offset_out = len(output_storage) - 1
          if getattr(fn, "need_update_inputs", True):
              # Update the inputs that have an update function
              for inp, storage in zip(
                  self.fn.maker.expanded_inputs[::-1],
                  self.fn.input_storage[::-1],
              ):
                  if inp.update is not None:
                      storage.data = output_storage[offset_out].data
                      offset_out -= 1
  
          t_fn += dt_fn
          offset_out = 0
  
          # 5.3 Copy over the values for mit_mot outputs
          mitmot_inp_offset = 0
          mitmot_out_idx = 0
          for j in xrange(self.n_mit_mot):
              for k in self.mit_mot_out_slices[j]:
                  if self.mitmots_preallocated[mitmot_out_idx]:
                      # This output tap has been preallocated.
                      inp_idx = mitmot_inp_offset + self.tap_array[
                          j
                      ].index(k)
  
                      # Verify whether the input points to the same data as
                      # it did before the execution of the inner function.
                      old_var = old_mitmot_input_storage[inp_idx]
                      new_var = input_storage[
                          self.n_seqs + inp_idx
                      ].storage[0]
                      if old_var is new_var:
                          old_data = old_mitmot_input_data[inp_idx]
                          if self.inps_is_tensor[self.n_seqs + inp_idx]:
                              same_data = new_var.data == old_data
                          else:
                              same_data = new_var.gpudata == old_data
                      else:
                          same_data = False
  
                      # If the corresponding input storage still points to
                      # the same data, it has been modified inplace and
                      # nothing needs to be done. Otherwise, recover the
                      # and store it in `outs` as usual
                      if not same_data:
                          outs[j][0][k + pos[j]] = input_storage[
                              self.n_seqs + inp_idx
                          ].storage[0]
  
                  else:
                      # This output tap has not been preallocated, recover
                      # its value as usual
                      outs[j][0][k + pos[j]] = output_storage[
                          offset_out
                      ].storage[0]
                      offset_out += 1
  
                  mitmot_out_idx += 1
  
              mitmot_inp_offset += len(self.tap_array[j])
  
          # 5.4 Copy over the values for mit_sot/sit_sot outputs
          begin = self.n_mit_mot
          end = self.n_outs
          offset_out -= self.n_mit_mot
  
          for j in xrange(begin, end):
              # Copy the output value to `outs`, if necessary
              if store_steps[j] == 1 or self.vector_outs[j]:
                  outs[j][0][pos[j]] = output_storage[
                      offset_out + j
                  ].storage[0]
              else:
                  # Check whether the initialization of the output storage
                  # map for this output has been reused.
                  old_var = old_output_storage[offset_out + j]
                  new_var = output_storage[offset_out + j].storage[0]
                  if old_var is new_var:
                      old_data = old_output_data[offset_out + j]
                      if old_data is None:
                          output_reused = False
                      elif self.outs_is_tensor[offset_out + j]:
                          output_reused = new_var.data == old_data
                      else:
                          output_reused = new_var.gpudata == old_data
                  else:
                      output_reused = False
  
                  if not output_reused:
                      try:
                          outs[j][0][pos[j]] = output_storage[
                              offset_out + j
                          ].storage[0]
                      except ValueError as e:
                          if i == 0:
                              # First iteration, so don't change the
                              # error message as it can't be the
                              # case we write about.
                              raise
                          ne = ValueError(
                              "An output of the scan has changed shape. "
                              "This may be caused by a pushout optimization."
                              " Try adding "
                              "'optimizer_excluding=scanOp_pushout_output' "
                              "to your Theano flags."
                          )
                          raise_from(ne, e)
  
          # 5.5 Copy over the values for nit_sot outputs
          begin = end
          end += self.n_nit_sot
          for j in xrange(begin, end):
              if i == 0:
                  jout = j + offset_out
                  shape = (store_steps[j],) + output_storage[
                      jout
                  ].storage[0].shape
                  dtype = output_storage[jout].storage[0].dtype
                  if (
                      outs[j][0] is None
                      or outs[j][0].shape[0] < store_steps[j]
                      or outs[j][0].shape[1:] != shape[1:]
                      or outs[j][0].dtype != dtype
                  ):
                      outs[j][0] = node.outputs[j].type.value_zeros(
                          shape
                      )
                  elif outs[j][0].shape[0] != store_steps[j]:
                      outs[j][0] = outs[j][0][: store_steps[j]]
                  outs[j][0][pos[j]] = output_storage[jout].storage[0]
              elif store_steps[j] == 1 or self.vector_outs[j]:
                  outs[j][0][pos[j]] = output_storage[
                      j + offset_out
                  ].storage[0]
              else:
                  # Check whether the initialization of the output storage map
                  # for this output has been reused.
                  old_var = old_output_storage[offset_out + j]
                  old_data = old_output_data[offset_out + j]
                  new_var = output_storage[offset_out + j].storage[0]
                  if old_var is new_var:
                      if old_data is None:
                          output_reused = False
                      elif self.outs_is_tensor[offset_out + j]:
                          output_reused = new_var.data == old_data
                      else:
                          output_reused = new_var.gpudata == old_data
                  else:
                      output_reused = False
  
                  if not output_reused:
                      outs[j][0][pos[j]] = output_storage[
                          j + offset_out
                      ].storage[0]
  
          # 5.6 Copy over the values for outputs corresponding to shared
          # variables
          begin = end
          end += self.n_shared_outs
          for j in xrange(begin, end):
              jout = j + offset_out
              outs[j][0] = output_storage[jout].storage[0]
  
          pos = [
              (idx + 1) % store for idx, store in izip(pos, store_steps)
          ]
          i = i + 1
  
      # 6. Check if you need to re-order output buffers
      begin = self.n_mit_mot
      end = self.n_outs + self.n_nit_sot
      for idx in xrange(begin, end):
          if (
              store_steps[idx] < i - self.mintaps[idx]
              and pos[idx] < store_steps[idx]
          ):
              pdx = pos[idx]
              if pdx >= store_steps[idx] // 2:
                  # It seems inefficient to copy the bigger part of the
                  # array over, and back, but it is the only way that
                  # there is no overlap in the areas of out[idx][0] that
                  # are read and written.
                  # This way, there will be no information overwritten
                  # before it is read (as it used to happen).
                  shape = (pdx,) + outs[idx][0].shape[1:]
                  tmp = node.outputs[idx].type.value_zeros(shape)
                  tmp[:] = outs[idx][0][:pdx]
                  outs[idx][0][: store_steps[idx] - pdx] = outs[idx][0][
                      pdx:
                  ]
                  outs[idx][0][store_steps[idx] - pdx :] = tmp
                  del tmp
              else:
                  shape = (store_steps[idx] - pdx,) + outs[idx][
                      0
                  ].shape[1:]
                  tmp = node.outputs[idx].type.value_zeros(shape)
                  tmp[:] = outs[idx][0][pdx:]
                  outs[idx][0][store_steps[idx] - pdx :] = outs[idx][0][
                      :pdx
                  ]
                  outs[idx][0][: store_steps[idx] - pdx] = tmp
                  del tmp
          # This would normally happen only when doing truncated
          # backpropagation through time. In such a scenarion Scan is
          # expected to return 0 for all entries for which the gradient is
          # not actually computed
          elif store_steps[idx] > i - self.mintaps[idx]:
              outs[idx][0][i - self.mintaps[idx] :] = 0
              # This is a fix for a bug introduced by while. If you say
              # you want to loop up to a condition, you expect the output
              # to have that length ( and not the maximal length possible)
              #
              # Without this the behaviour of a scan op is not consistent
              # if optimization gets applied compared to when optimization
              # do not get applied
              if i < n_steps:
                  # The reason I don't use out[idx][0][:i] is because for
                  # certain outputs (those with multiple taps),
                  # outs[idx][0] has more than n_steps entries, with the
                  # initial state  at the beginning. When indexing in it I
                  # usually have to do something like
                  # outs[idx][0][i+offset]. To do something similar here,
                  # I would have first to compute the maximal tap for
                  # every output and then do outs[0][:i+maximal_tap],
                  # which implies I think more computations then this
                  # little trick that I used
                  outs[idx][0] = outs[idx][0][: -(n_steps - i)]
  
      # We never reuse the input or output storage of the
      # inner function so we clear it.
      for i_s in input_storage:
          i_s.storage[0] = None
      for o_s in output_storage:
          o_s.storage[0] = None
  
      t_call = time.time() - t0_call
      # NOTE: make this match what's in function_module.Function
      # and this little string helps us to find this spot:
      # "PROFILE_CODE"
  
      if hasattr(self.fn.maker, "profile") and self.fn.maker.profile:
          profile = self.fn.maker.profile
          profile.callcount += 1
          profile.nbsteps += n_steps
          profile.call_time += t_call
          profile.vm_call_time += t_fn
          if hasattr(self.fn.fn, "update_profile"):
              self.fn.fn.update_profile(profile)
  
      self.t_call = t_call
      self.t_fn = t_fn
  
imports: from __future__ import absolute_import, print_function, division
  import copy
  import itertools
  import logging
  import time
  from collections import OrderedDict
  import numpy
  from six import iteritems, integer_types, raise_from
  from six.moves import xrange
  import theano
  from theano.compile import function, In, Out
  from theano.compile.mode import AddFeatureOptimizer
  from theano import compile, config, gradient, gof, tensor
  from theano.gof import PureOp, Apply
  from theano.gof.graph import io_connection_pattern
  from theano.gof.toolbox import NoOutputFromInplace
  from theano.compat import izip
  from theano.tensor import as_tensor_variable, TensorType
  from theano.tensor.opt import Shape_i
  from theano.gradient import grad_undefined, DisconnectedType, NullType
  from six import string_types
  from theano.compile.profiling import ScanProfileStats
  from theano.scan_module import scan_utils
  from theano.scan_module.scan_utils import safe_new, forced_replace
label_desc: Use image node_id 35 for calling the Scan obj's underlying member method code with example usage: obj.execute(node, args, outs) without return types