def _ParseSingleSequenceExampleShape(op):
    """Shape function for the ParseExample op."""
    op.inputs[0].get_shape().with_rank(0)  # input
    # feature_list_dense_missing_assumed_empty
    op.inputs[1].get_shape().with_rank(1)
    num_context_sparse = op.get_attr("Ncontext_sparse")
    num_context_dense = op.get_attr("Ncontext_dense")
    num_feature_list_dense = op.get_attr("Nfeature_list_dense")
    context_dense_shapes = op.get_attr("context_dense_shapes")
    num_feature_list_sparse = op.get_attr("Nfeature_list_sparse")
    feature_list_dense_shapes = op.get_attr("feature_list_dense_shapes")
    context_sparse_index_shapes = [tensor_shape.matrix(None, 1) for _ in range(num_context_sparse)]
    context_sparse_value_shapes = [tensor_shape.vector(None) for _ in range(num_context_sparse)]
    context_sparse_shape_shapes = [tensor_shape.vector(1) for _ in range(num_context_sparse)]
    context_dense_shapes = [tensor_shape.TensorShape(dense_shape) for dense_shape in context_dense_shapes]
    feature_list_sparse_index_shapes = [tensor_shape.matrix(None, 2) for _ in range(num_feature_list_sparse)]
    feature_list_sparse_value_shapes = [tensor_shape.vector(None) for _ in range(num_feature_list_sparse)]
    feature_list_sparse_shape_shapes = [tensor_shape.vector(2) for _ in range(num_feature_list_sparse)]
    feature_list_dense_shapes = [
        tensor_shape.vector(None).concatenate(dense_shape) for dense_shape in feature_list_dense_shapes
    ]
    assert num_context_dense == len(context_dense_shapes)
    assert num_feature_list_dense == len(feature_list_dense_shapes)
    return (
        context_sparse_index_shapes
        + context_sparse_value_shapes
        + context_sparse_shape_shapes
        + context_dense_shapes
        + feature_list_sparse_index_shapes
        + feature_list_sparse_value_shapes
        + feature_list_sparse_shape_shapes
        + feature_list_dense_shapes
    )

  def testShapes(self):
    fdef = self._build_function_def()

    g = function_def_to_graph.function_def_to_graph(fdef)
    self.assertIsNone(g.inputs[0].shape.dims)  # Unknown dims.
    self.assertIsNone(g.inputs[1].shape.dims)  # Unknown dims.
    self.assertIsNone(g.outputs[0].shape.dims)  # Unknown dims.
    self.assertIsNone(g.outputs[1].shape.dims)  # Unknown dims.

    g = function_def_to_graph.function_def_to_graph(
        fdef, input_shapes=[tensor_shape.vector(5),
                            tensor_shape.vector(5)])
    self.assertSequenceEqual(g.inputs[0].shape.dims, [5])
    self.assertSequenceEqual(g.inputs[1].shape.dims, [5])
    self.assertSequenceEqual(g.outputs[0].shape.dims, [5])
    self.assertSequenceEqual(g.outputs[1].shape.dims, [5])

    g = function_def_to_graph.function_def_to_graph(
        fdef, input_shapes=[None, tensor_shape.matrix(5, 7)])
    self.assertIsNone(g.inputs[0].shape.dims)
    self.assertSequenceEqual(g.inputs[1].shape.dims, [5, 7])
    self.assertSequenceEqual(g.outputs[0].shape.dims, [5, 7])
    self.assertSequenceEqual(g.outputs[1].shape.dims, [5, 7])

    # Should raise a ValueError if the length of input_shapes does not match
    # the number of input args in FunctionDef.signature.input_arg.
    with self.assertRaises(ValueError):
      g = function_def_to_graph.function_def_to_graph(
          fdef, input_shapes=[tensor_shape.matrix(5, 7)])

def _CTCGreedyDecoderShape(op):
  """Shape function for the CTCGreedyDecoder op."""
  inputs_shape = op.inputs[0].get_shape().with_rank(3)
  sequence_length_shape = op.inputs[1].get_shape().with_rank(1)
  # merge batch_size
  sequence_length_shape[0].merge_with(inputs_shape[1])
  inputs_shape[1].merge_with(sequence_length_shape[0])
  batch_size = inputs_shape[1]
  # decoded_indices, decoded_values, decoded_shape, log_probability
  return [tensor_shape.matrix(None, 2),
          tensor_shape.vector(None),
          tensor_shape.vector(2),
          tensor_shape.matrix(batch_size, 1)]

def _SparseConcatShape(op):
  """Shape function for SparseConcat op."""
  num_inputs = int(op.get_attr("N"))

  # TF flattens and concatenates all list inputs, so reconstruct the lists here.
  ind_shapes = [ind.get_shape().with_rank(2) for ind in op.inputs[0:num_inputs]]
  val_shapes = [val.get_shape().with_rank(1)
                for val in op.inputs[num_inputs:2 * num_inputs]]
  shape_shapes = [shape.get_shape().with_rank(1)
                  for shape in op.inputs[2 * num_inputs:]]

  output_ind_rows = tensor_shape.Dimension(0)
  output_ind_cols = tensor_shape.Dimension(None)
  output_val_elems = tensor_shape.Dimension(0)
  output_shape_shape = tensor_shape.TensorShape(None)

  for i in xrange(num_inputs):
    num_elems_i = ind_shapes[i][0].merge_with(val_shapes[i][0])
    output_ind_rows += num_elems_i
    output_ind_cols = output_ind_cols.merge_with(ind_shapes[i][1])
    output_val_elems += num_elems_i
    output_shape_shape = output_shape_shape.merge_with(shape_shapes[i])

  output_ind_shape = tensor_shape.matrix(output_ind_rows, output_ind_cols)
  output_val_shape = tensor_shape.vector(output_val_elems)

  return [output_ind_shape, output_val_shape, output_shape_shape]

def _SerializeManySparseShape(op):  # pylint: disable=invalid-name
  """Shape function for SerializeSparse op."""
  op.inputs[0].get_shape().with_rank(2)
  op.inputs[1].get_shape().with_rank(1)
  op.inputs[2].get_shape().with_rank(1)

  return [tensor_shape.matrix(None, 3)]

def _ComputeAccidentalHitsShape(op):
    num_true = op.get_attr("num_true")
    # Validate that the input shape matches the attrs, even though it
    # does not influence the shape of the output.
    true_candidates_shape = op.inputs[0].get_shape().merge_with(tensor_shape.matrix(None, num_true))
    output_shape = tensor_shape.vector(None)
    return [output_shape] * 3

 def testHelpers(self):
   tensor_shape.TensorShape([]).assert_is_compatible_with(
       tensor_shape.scalar())
   tensor_shape.TensorShape([37]).assert_is_compatible_with(
       tensor_shape.vector(37))
   tensor_shape.TensorShape(
       [94, 43]).assert_is_compatible_with(tensor_shape.matrix(94, 43))

def _reverse_seq(input_seq, lengths):
  """Reverse a list of Tensors up to specified lengths.

  Args:
    input_seq: Sequence of seq_len tensors of dimension (batch_size, depth)
    lengths:   A tensor of dimension batch_size, containing lengths for each
               sequence in the batch. If "None" is specified, simply reverses
               the list.

  Returns:
    time-reversed sequence
  """
  if lengths is None:
    return list(reversed(input_seq))

  input_shape = tensor_shape.matrix(None, None)
  for input_ in input_seq:
    input_shape.merge_with(input_.get_shape())
    input_.set_shape(input_shape)

  # Join into (time, batch_size, depth)
  s_joined = array_ops.pack(input_seq)

  # TODO(schuster, ebrevdo): Remove cast when reverse_sequence takes int32
  if lengths is not None:
    lengths = math_ops.to_int64(lengths)

  # Reverse along dimension 0
  s_reversed = array_ops.reverse_sequence(s_joined, lengths, 0, 1)
  # Split again into list
  result = array_ops.unpack(s_reversed)
  for r in result:
    r.set_shape(input_shape)
  return result

def _CandidateSamplerShape(op):
  true_classes_shape = op.inputs[0].get_shape().with_rank(2)
  batch_size = true_classes_shape[0]
  num_sampled = op.get_attr("num_sampled")
  num_true = op.get_attr("num_true")
  return [tensor_shape.vector(num_sampled),
          tensor_shape.matrix(batch_size, num_true),
          tensor_shape.vector(num_sampled)]

def _DeserializeSparseShape(op):  # pylint: disable=invalid-name
  """Shape function for DeserializeManySparse op."""
  serialized_sparse_shape = op.inputs[0].get_shape().with_rank(2)
  serialized_sparse_shape.merge_with(
      tensor_shape.TensorShape([None, 3]))

  return [tensor_shape.matrix(None, None),
          tensor_shape.vector(None),
          tensor_shape.vector(None)]

def _SparseTensorDenseMatMulShape(op):  # pylint: disable=invalid-name
  """Shape function for SparseTensorDenseMatMul op."""
  adjoint_b = op.get_attr("adjoint_b")
  op.inputs[0].get_shape().assert_has_rank(2)  # a_indices
  op.inputs[1].get_shape().assert_has_rank(1)  # a_values
  op.inputs[2].get_shape().merge_with(tensor_shape.vector(2))  # a_shape
  b_shape = op.inputs[3].get_shape().with_rank(2)
  output_shape_right = b_shape[0] if adjoint_b else b_shape[1]
  return [tensor_shape.matrix(None, output_shape_right)]

def _CTCBeamSearchDecoderShape(op):
  """Shape function for the CTCBeamSearchDecoder op."""
  inputs_shape = op.inputs[0].get_shape().with_rank(3)
  sequence_length_shape = op.inputs[1].get_shape().with_rank(1)
  # merge batch size
  sequence_length_shape[0].merge_with(inputs_shape[1])
  inputs_shape[1].merge_with(sequence_length_shape[0])
  batch_size = inputs_shape[1]
  top_paths = op.get_attr("top_paths")

  # first the decoded indices
  output_shapes = [tensor_shape.matrix(None, 2) for _ in range(top_paths)]
  # next the decoded values
  output_shapes.extend([tensor_shape.vector(None) for _ in range(top_paths)])
  # the shapes of the decoded values
  output_shapes.extend([tensor_shape.vector(2)] * top_paths)
  # the log_probability matrix
  output_shapes.append(tensor_shape.matrix(batch_size, top_paths))
  return output_shapes

  def testStr(self):
    self.assertEqual("<unknown>", str(tensor_shape.unknown_shape()))
    self.assertEqual("(?,)", str(tensor_shape.unknown_shape(ndims=1)))
    self.assertEqual("(?, ?)", str(tensor_shape.unknown_shape(ndims=2)))
    self.assertEqual("(?, ?, ?)", str(tensor_shape.unknown_shape(ndims=3)))

    self.assertEqual("()", str(tensor_shape.scalar()))
    self.assertEqual("(7,)", str(tensor_shape.vector(7)))
    self.assertEqual("(3, 8)", str(tensor_shape.matrix(3, 8)))
    self.assertEqual("(4, 5, 2)", str(tensor_shape.TensorShape([4, 5, 2])))

    self.assertEqual("(32, ?, 1, 9)",
                     str(tensor_shape.TensorShape([32, None, 1, 9])))

def _ParseExampleShape(op):
    """Shape function for the ParseExample op."""
    input_shape = op.inputs[0].get_shape().with_rank(1)
    op.inputs[1].get_shape().with_rank(1)  # names
    num_sparse = op.get_attr("Nsparse")
    num_dense = op.get_attr("Ndense")
    dense_shapes = op.get_attr("dense_shapes")
    sparse_index_shapes = [tensor_shape.matrix(None, 2) for _ in range(num_sparse)]
    sparse_value_shapes = [tensor_shape.vector(None) for _ in range(num_sparse)]
    sparse_shape_shapes = [tensor_shape.vector(2) for _ in range(num_sparse)]
    assert num_dense == len(dense_shapes)
    dense_shapes = [input_shape.concatenate(dense_shape) for dense_shape in dense_shapes]
    return sparse_index_shapes + sparse_value_shapes + sparse_shape_shapes + dense_shapes

  def testBroadcast_many_dimensions(self):
    unknown = tensor_shape.unknown_shape()
    shape_0 = tensor_shape.scalar()
    shape_1 = tensor_shape.vector(1)
    shape_4 = tensor_shape.vector(4)
    shape_1x4 = tensor_shape.matrix(1, 4)
    shape_4x1 = tensor_shape.matrix(4, 1)
    shape_3x4 = tensor_shape.matrix(3, 4)
    shape_4x3 = tensor_shape.matrix(4, 3)

    # Tensors with same shape should have the same broadcast result.
    for shape in (
        shape_0, shape_1, shape_4, shape_1x4, shape_4x1, shape_3x4, shape_4x3):
      self._assert_broadcast(expected=shape, shape1=shape, shape2=shape)

    # [] and [1] act like identity.
    for identity in (shape_0, shape_1):
      for shape in (shape_4, shape_1x4, shape_4x1, shape_3x4, shape_4x3):
        self._assert_broadcast(expected=shape, shape1=identity, shape2=shape)

    # Unknown in, unknown out.
    for shape in (shape_4, shape_1x4, shape_4x1, shape_3x4, shape_4x3):
      self._assert_broadcast(expected=unknown, shape1=shape, shape2=unknown)

    self._assert_broadcast(expected=shape_1x4, shape1=shape_4, shape2=shape_1x4)
    shape_4x4 = tensor_shape.matrix(4, 4)
    self._assert_broadcast(expected=shape_4x4, shape1=shape_4, shape2=shape_4x1)
    self._assert_broadcast(expected=shape_3x4, shape1=shape_4, shape2=shape_3x4)
    self._assert_incompatible_broadcast(shape1=shape_4, shape2=shape_4x3)
    self._assert_broadcast(
        expected=shape_4x4, shape1=shape_1x4, shape2=shape_4x1)
    self._assert_broadcast(
        expected=shape_3x4, shape1=shape_1x4, shape2=shape_3x4)
    self._assert_incompatible_broadcast(shape1=shape_1x4, shape2=shape_4x3)
    self._assert_incompatible_broadcast(shape1=shape_4x1, shape2=shape_3x4)
    self._assert_broadcast(
        expected=shape_4x3, shape1=shape_4x1, shape2=shape_4x3)
    self._assert_incompatible_broadcast(shape1=shape_3x4, shape2=shape_4x3)

 def testStr(self):
   self.assertEqual("<unknown>", str(tensor_shape.unknown_shape()))
   self.assertEqual(
       "(None,)",
       str(tensor_shape.unknown_shape(rank=1)).replace("?", "None"))
   self.assertEqual(
       "(None, None)",
       str(tensor_shape.unknown_shape(rank=2)).replace("?", "None"))
   self.assertEqual(
       "(None, None, None)",
       str(tensor_shape.unknown_shape(rank=3)).replace("?", "None"))
   self.assertEqual(
       "(32, None, 1, 9)",
       str(tensor_shape.TensorShape([32, None, 1, 9])).replace("?", "None"))
   self.assertEqual("()", str(tensor_shape.scalar()))
   self.assertEqual("(7,)", str(tensor_shape.vector(7)))
   self.assertEqual("(3, 8)", str(tensor_shape.matrix(3, 8)))
   self.assertEqual("(4, 5, 2)", str(tensor_shape.TensorShape([4, 5, 2])))

  def testBroadcast_unknown_dims(self):
    unknown = tensor_shape.unknown_shape()
    shape_0 = tensor_shape.scalar()
    shape_1 = tensor_shape.vector(1)
    # pylint: disable=invalid-name
    shape_U = tensor_shape.vector(None)
    shape_1xU = tensor_shape.matrix(1, None)
    shape_Ux1 = tensor_shape.matrix(None, 1)
    shape_4xU = tensor_shape.matrix(4, None)
    shape_Ux4 = tensor_shape.matrix(None, 4)
    # pylint: enable=invalid-name

    # Tensors with same shape should have the same broadcast result.
    for shape in (shape_U, shape_1xU, shape_Ux1, shape_4xU, shape_Ux4):
      self._assert_broadcast_with_unknown_dims(
          expected=shape, shape1=shape, shape2=shape)

    # [] and [1] act like identity.
    for identity in (shape_0, shape_1):
      for shape in (shape_U, shape_1xU, shape_Ux1, shape_4xU, shape_Ux4):
        self._assert_broadcast_with_unknown_dims(
            expected=shape, shape1=identity, shape2=shape)

    # Unknown in, unknown out.
    for shape in (shape_U, shape_1xU, shape_Ux1, shape_4xU, shape_Ux4):
      self._assert_broadcast_with_unknown_dims(
          expected=unknown, shape1=shape, shape2=unknown)

    self._assert_broadcast_with_unknown_dims(
        expected=shape_1xU, shape1=shape_U, shape2=shape_1xU)
    shape_UxU = tensor_shape.matrix(None, None)  # pylint: disable=invalid-name
    self._assert_broadcast_with_unknown_dims(
        expected=shape_UxU, shape1=shape_U, shape2=shape_Ux1)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_4xU, shape1=shape_U, shape2=shape_4xU)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_Ux4, shape1=shape_U, shape2=shape_Ux4)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_UxU, shape1=shape_1xU, shape2=shape_Ux1)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_4xU, shape1=shape_1xU, shape2=shape_4xU)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_Ux4, shape1=shape_1xU, shape2=shape_Ux4)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_4xU, shape1=shape_Ux1, shape2=shape_4xU)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_Ux4, shape1=shape_Ux1, shape2=shape_Ux4)
    shape_4x4 = tensor_shape.matrix(4, 4)
    self._assert_broadcast_with_unknown_dims(
        expected=shape_4x4, shape1=shape_4xU, shape2=shape_Ux4)

def _PadShape(op):
  """Shape function for the Pad op.

  This op has two inputs:

  * input: A rank-N tensor.
  * paddings: An N-by-2 matrix, in which the i^th row contains the
    number of padding elements to add before and after `input` in the
    i^th dimension.

  It has one output, which has the same rank as input, and additional
  elements according to the values in paddings.

  Args:
    op: A Pad Operation.

  Returns:
    A single-element list containing the shape of the output.

  Raises:
    ValueError: If the input shapes are incompatible.
  """
  paddings_shape = op.inputs[1].get_shape().with_rank(2)
  input_shape = op.inputs[0].get_shape()
  if input_shape.ndims == 0 and paddings_shape[0].value == 1:
    # TODO(irving): Remove once !kAllowLegacyScalars.
    input_shape = tensor_shape.TensorShape([1])
  else:
    input_shape = input_shape.with_rank(paddings_shape[0].value)
  paddings_shape = paddings_shape.merge_with(
      tensor_shape.matrix(input_shape.ndims, 2))
  paddings = tensor_util.ConstantValue(op.inputs[1])
  if paddings is None:
    return [tensor_shape.unknown_shape(ndims=input_shape.ndims)]
  else:
    output_dims = []
    for i, dim in enumerate(input_shape.dims):
      if paddings[i, 0] < 0 or paddings[i, 1] < 0:
        raise ValueError("paddings must be non-negative")
      output_dims.append(dim + paddings[i, 0] + paddings[i, 1])
    return [tensor_shape.TensorShape(output_dims)]

def _WhereShape(op):
  """Shape function for the Where op."""
  input_shape = op.inputs[0].get_shape()
  return [tensor_shape.matrix(None, input_shape.ndims)]

 def output_shapes(self):
   num_elements = tensor_shape.Dimension(None)
   return (tensor_shape.matrix(num_elements, self._row_shape.shape[0] + 1),
           tensor_shape.vector(num_elements),
           tensor_shape.vector(self._row_shape.shape[0] + 1))