// nnet3/nnet-descriptor.h

// Copyright   2012-2015  Johns Hopkins University (author: Daniel Povey)

// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_NNET3_NNET_DESCRIPTOR_H_
#define KALDI_NNET3_NNET_DESCRIPTOR_H_

#include "base/kaldi-common.h"
#include "util/kaldi-io.h"
#include "matrix/matrix-lib.h"
#include "nnet3/nnet-common.h"
#include "nnet3/nnet-component-itf.h"

#include <iostream>
#include <sstream>
#include <vector>
#include <map>


namespace kaldi {
namespace nnet3 {

/**
   \file nnet-descriptor.h

   This file contains class definitions for classes ForwardingDescriptor,
   SumDescriptor and Descriptor.  Basically this is code that specifies how
   we glue together the outputs of possibly several other network-nodes, as the
   input of a particular network node (or as an output of the network).  In the
   neural-network code we refer to the top-level descriptor which is
   Descriptor.  The InputDescriptor is a concatenation of features; each part
   is a SumDescriptor.  The SumDescriptor is a summation over a set of features
   of all the same dimension, each of which is represented by a
   ForwardingDescriptor.  A ForwardingDescriptor in the simplest case just
   takes just points you to a particular network node, but in general can do
   things like adding time offsets, and selecting different rows of its matrix
   from different inputs.  Unlike the other descriptors, a ForwardingDescriptor
   is in general a bit like a parse tree, in that it can in general contain
   other ForwardingDescriptors.

   The following gives an overview of the expressions that can appear in
   descriptors.  Caution; this is a simplification that overgenerates
   descriptors: not all combinations are allowed.
\verbatim
<descriptor>  ::=   <node-name>      ;; node name of kInput or kComponent node.
<descriptor>  ::=   Append(<descriptor>, <descriptor> [, <descriptor> ... ] )
<descriptor>  ::=   Sum(<descriptor>, <descriptor>)
<descriptor>  ::=   Const(<value>, <dimension>)    ;; e.g. Const(1.0, 512)
<descriptor>  ::=   Scale(<scale>, <descriptor>)   ;; e.g. Scale(-1.0, tdnn2)
;; Failover or IfDefined might be useful for time t=-1 in a RNN, for instance.
<descriptor>  ::=   Failover(<descriptor>, <descriptor>)   ;; 1st arg if computable, else 2nd
<descriptor>  ::=   IfDefined(<descriptor>)     ;; the arg if defined, else zero.
<descriptor>  ::=   Offset(<descriptor>, <t-offset> [, <x-offset> ] ) ;; offsets are integers
;; Switch(...) is intended to be used in clockwork RNNs or similar schemes.  It chooses
;; one argument based on the value of t (in the requested Index) modulo the number of
;; arguments
<descriptor>  ::=   Switch(<descriptor>, <descriptor> [, <descriptor> ...])
;; For use in clockwork RNNs or similar, Round() rounds the time-index t of the
;; requested Index to the next-lowest multiple of the integer <t-modulus>,
;; and evaluates the input argument for the resulting Index.
<descriptor>  ::=   Round(<descriptor>, <t-modulus>)  ;; <t-modulus> is an integer
;; ReplaceIndex replaces some <variable-name> (t or x) in the requested Index
;; with a fixed integer <value>.  E.g. might be useful when incorporating
;; iVectors; iVector would always have time-index t=0.
<descriptor>  ::=   ReplaceIndex(<descriptor>, <variable-name>, <value>)
\endverbatim

 */



/// A ForwardingDescriptor describes how we copy data from another NetworkNode,
/// or from multiple other NetworkNodes, possibly with a scalar weight.  In the
/// base case this can just be equivalent to giving the name of another
/// NetworkNode, but we also support things like time-offsets, selecting
/// depending on the index from multiple different inputs, and things like that.
///
/// Note: nodes of type kOutput (i.e. output nodes of the network) cannot appear
/// as inputs in any descriptor.  This is to simplify compilation.
class ForwardingDescriptor {
 public:
  // Given an Index that's requested at the output of this descriptor, maps it
  // to a (node_index, Index) pair that says where we are to get the data from.
  //
  virtual Cindex MapToInput(const Index &output) const = 0;

  // Return the feature dimension.
  virtual int32 Dim(const Nnet &nnet) const = 0;

  virtual ForwardingDescriptor *Copy() const = 0;

  /// This function is for use in things like clockwork RNNs, where shifting the
  /// time of the inputs and outputs of the network by some multiple integer n
  /// would leave things the same, but shifting by non-multiples would change the
  /// network structure.  It returns the smallest modulus to which this
  /// descriptor is invariant; the lowest common multiple of all descriptors in
  /// the network gives you the modulus for the whole network.
  virtual int32 Modulus() const { return 1; }

  // Write to string that will be one line of a config-file-like format.  The
  // opposite of Parse.
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const = 0;

  /// This function appends to "node_indexes" all the node indexes
  // that this descriptor may access.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const = 0;

  /// This function returns the scale on the node-index 'node_index' when it
  /// appears in expressions inside this descriptor, or +infinity if it does not
  /// appear.  E.g. if the descriptor is just `Scale(tdnn2, 2.0)` and the node
  /// index for `tdnn2` is 4, then GetScaleForNode(4) would return 2.0.  If a
  /// particular node_index > 0 appears in different sub-expressions of the
  /// descriptor with different scales it is an error (it's not supported) and
  /// this function would crash.
  virtual BaseFloat GetScaleForNode(int32 node_index) const = 0;

  virtual ~ForwardingDescriptor() { }
  ForwardingDescriptor() { }
 private:
  KALDI_DISALLOW_COPY_AND_ASSIGN(ForwardingDescriptor);
};

/// SimpleForwardingDescriptor is the base-case of ForwardingDescriptor,
/// consisting of a source node in the graph with a given scalar weight (which
/// will in the normal case be 1.0).  The string representation in the
/// normal (scale=1.0) case is just the node-name, like `tdnn2`; if
/// the weight is not 1.0 it's something like `Scale(2.0, tdnn2)`
class SimpleForwardingDescriptor: public ForwardingDescriptor {
 public:
  virtual Cindex MapToInput(const Index &index) const;
  virtual int32 Dim(const Nnet &nnet) const;
  virtual ForwardingDescriptor *Copy() const;
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // Write to string that will be one line of a config-file-like format.  The
  // opposite of Parse.
  // written form is just the node-name of src_node_.
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const;

  SimpleForwardingDescriptor(int32 src_node,
                             BaseFloat scale = 1.0):
      src_node_(src_node), scale_(scale) {
    KALDI_ASSERT(src_node >= 0);
  }
  virtual ~SimpleForwardingDescriptor() { }
 private:
  int32 src_node_;  // index of the source NetworkNode.
  BaseFloat scale_;  // Scale of the node in the expression; this will be 1.0
                     // unless you used a Scale(...) expression in your
                     // Descriptor.
};

/// Offsets in 't' and 'x' values of other ForwardingDescriptors.
/// Written form is:
///   `Offset(<descriptor>, <t-offset> [, <x-offset> ] )`
/// e.g. `Offset(tdnn2, -2)`
class OffsetForwardingDescriptor: public ForwardingDescriptor {
 public:
  virtual Cindex MapToInput(const Index &ind) const;
  virtual int32 Dim(const Nnet &nnet) const { return src_->Dim(nnet); }
  virtual ForwardingDescriptor *Copy() const;

  // written form is: Offset(<src-written-form>, t-offset [, x-offset])
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const;

  virtual int32 Modulus() const { return src_->Modulus(); }

  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // takes ownership of src.
  OffsetForwardingDescriptor(ForwardingDescriptor *src,
                             Index offset): src_(src), offset_(offset) { }

  virtual ~OffsetForwardingDescriptor() { delete src_; }


  // this function is not in the shared interface. it's used
  // in class ModelCollapser.
  const ForwardingDescriptor &Src() const { return *src_; }
 private:
  ForwardingDescriptor *src_;  // Owned here.
  Index offset_;  // The index-offset to be added to the index.
};

/// Chooses from different inputs based on the the time index modulo
/// (the number of ForwardingDescriptors given as inputs).  This is rarely
/// if ever used.  Written form is:
///  `Switch(<descriptor>, <descriptor> [, <descriptor> ...])`
/// e.g. `Switch(tdnn2a, tdnn2b, tdnn2c)`
class SwitchingForwardingDescriptor: public ForwardingDescriptor {
 public:
  virtual Cindex MapToInput(const Index &ind) const;
  virtual int32 Dim(const Nnet &nnet) const { return src_[0]->Dim(nnet); }
  virtual ForwardingDescriptor *Copy() const;
  // Written form is "Switch(<written-form-of-src1>, <written-form-of-src2>, ... )"
  virtual void WriteConfig(std::ostream &os,
                          const std::vector<std::string> &node_names) const;

  virtual int32 Modulus() const;

  /// This function appends to "node_indexes" all the node indexes
  // that this descriptor may access.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // takes ownership of items in src.
  SwitchingForwardingDescriptor(std::vector<ForwardingDescriptor*> &src):
      src_(src) { }
  virtual ~SwitchingForwardingDescriptor() { DeletePointers(&src_); }
 private:
  // Pointers are owned here.
  std::vector<ForwardingDescriptor*> src_;
};



/// For use in clockwork RNNs and the like, this forwarding-descriptor
/// rounds the time-index t down to the the closest t' <= t that is
/// an exact multiple of t_modulus_.
/// Written form is: `Round(<descriptor>, <t-modulus>)`
/// e.g.: `Round(tdnn2, 3)`
class RoundingForwardingDescriptor: public ForwardingDescriptor {
 public:
  virtual Cindex MapToInput(const Index &ind) const;
  virtual int32 Dim(const Nnet &nnet) const { return src_->Dim(nnet); }
  virtual ForwardingDescriptor *Copy() const;
  // Written form is "Round(<written-form-of-src>, <t_modulus>)"
  virtual void WriteConfig(std::ostream &os,
                          const std::vector<std::string> &node_names) const;

  virtual int32 Modulus() const { return t_modulus_; }

  /// This function appends to "node_indexes" all the node indexes
  // that this descriptor may access.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // takes ownership of src.
  RoundingForwardingDescriptor(ForwardingDescriptor *src,
                               int32 t_modulus):
      src_(src), t_modulus_(t_modulus) { }

  virtual ~RoundingForwardingDescriptor() { delete src_; }
 private:
  ForwardingDescriptor *src_;
  int32 t_modulus_;
};

/// This ForwardingDescriptor modifies the indexes (n, t, x) by replacing one
/// of them (normally t) with a constant value and keeping the rest.
/// Written form is: `ReplaceIndex(<descriptor>, <variable-name>, <value>)`
/// e.g. `ReplaceIndex(ivector, t, 0)`
class ReplaceIndexForwardingDescriptor: public ForwardingDescriptor {
 public:
  enum VariableName { kN = 0, kT = 1, kX = 2};

  virtual Cindex MapToInput(const Index &ind) const;
  virtual int32 Dim(const Nnet &nnet) const { return src_->Dim(nnet); }
  virtual ForwardingDescriptor *Copy() const;
  // Written form is "ReplaceIndex(<written-form-of-src>, <variable-name>, <value>)"
  // where <variable-name> is either "t" or "x".
  virtual void WriteConfig(std::ostream &os,
                          const std::vector<std::string> &node_names) const;

  /// This function appends to "node_indexes" all the node indexes
  // that this descriptor may access.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // takes ownership of src.
  ReplaceIndexForwardingDescriptor(ForwardingDescriptor *src,
                                   VariableName variable_name,
                                   int32 value):
      src_(src), variable_name_(variable_name), value_(value) { }

  virtual ~ReplaceIndexForwardingDescriptor() { delete src_; }
 private:
  ForwardingDescriptor *src_;
  VariableName variable_name_;
  int32 value_;
};


/// Forward declaration.  This is declared in nnet-computation-graph.h.
class CindexSet;

/// This is an abstract base-class.  In the normal case a SumDescriptor is a sum
/// over one or more ForwardingDescriptors (all of which must be of the same
/// dimension).  However, it also allows for logic for dealing with cases where
/// only some terms in the sum are present, and only some are included in the
/// sum: for example, not just expressions like A + B but also A + (B if
/// present), or (A if present; if not, B).  It also handles
/// expressions involving adding a constant, e.g.
/// `Sum(Scale(tdnn2, -1.0), Const(1.0, 512))` (see ConstantSumDescriptor).
class SumDescriptor {
 public:
  /// Given an Index at the output of this Descriptor, append to "dependencies"
  /// a list of Cindexes that describes what inputs we potentially depend on.
  /// The output list is not necessarily sorted, and this function doesn't make
  /// sure that it's unique.
  virtual void GetDependencies(const Index &ind,
                               std::vector<Cindex> *dependencies) const = 0;

  /// This function exists to enable us to manage optional dependencies,
  /// i.e. for making sense of expressions like (A + (B is present)) and (A if
  /// present; if not, B).  Suppose we are trying to compute the index "ind",
  /// and the user represents that "cindex_set" is the set of Cindexes are
  /// available to the computation; then this function will return true if we
  /// can compute the expression given these inputs; and if so, will output to
  /// "used_inputs" the list of Cindexes that this expression will be a
  /// summation over.
  ///
  ///  @param [in] ind  The index that we want to compute at the output of the
  ///                   Descriptor.
  ///  @param [in] cindex_set  The set of Cindexes that are available at the
  ///                   input of the Descriptor.
  ///  @param [out] used_inputs If non-NULL, if this function returns true then
  ///                  to this vector will be *appended* the inputs that will
  ///                  actually participate in the computation.  Else (if non-NULL) it
  ///                  will be left unchanged.
  ///  @return Returns true if this output is computable given the provided
  ///          inputs.
  virtual bool IsComputable(const Index &ind,
                            const CindexSet &cindex_set,
                            std::vector<Cindex> *used_inputs) const = 0;

  virtual int32 Dim(const Nnet &nnet) const = 0;

  virtual SumDescriptor *Copy() const = 0;

  virtual ~SumDescriptor() { }

  /// This function appends to "node_indexes" a list (not necessarily sorted or
  /// unique) of all the node indexes that this descriptor may forward data from.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const = 0;

  /// This function returns the scale on the node-index 'node_index' when it
  /// appears in expressions inside this descriptor.  E.g. if the descriptor is
  /// just `Scale(tdnn2, 2.0)` and the node index for `tdnn2` is 4, then
  /// GetScaleForNode(4) would return 2.0.  It will return +infinity if the node
  /// is >= 0 and does not appear in this descriptor.  If node_index < 0, it
  /// returns the constant offset value from this descriptor, which will equal
  /// 0.0 if there is no expression like `Const(1.0, 512)` in this node.  If a
  /// particular node_index > 0 appears in different sub-expressions of the
  /// descriptor with different scales it is an error (it's not supported) and
  /// this function would crash.
  virtual BaseFloat GetScaleForNode(int32 node_index) const = 0;

  // see Modulus function of ForwardingDescriptor for explanation.
  virtual int32 Modulus() const = 0;

  /// Write in config-file format.  Conventional Read and Write methods are not
  /// supported.
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const = 0;
};

/// This is the case of class SumDescriptor, in which we contain just one term,
/// and that term is optional (an IfDefined() expression).  That term is a
/// general SumDescriptor.
///  The written form is: `IfDefined(<descriptor>)`, e.g.
///   `IfDefined(Offset(lstm2.s, -3))`
class OptionalSumDescriptor: public SumDescriptor {
 public:
  virtual void GetDependencies(const Index &ind,
                               std::vector<Cindex> *dependencies) const;
  virtual bool IsComputable(const Index &ind,
                            const CindexSet &cindex_set,
                            std::vector<Cindex> *used_inputs) const {
      return src_->IsComputable(ind, cindex_set, used_inputs) || true;
  }

  virtual int32 Dim(const Nnet &nnet) const;

  // This function appends to "node_indexes" a list (not necessarily sorted or
  // unique) of all the node indexes that this descriptor may forward data from.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;
  virtual int32 Modulus() const { return src_->Modulus(); }
  /// written form is: if required_ == true, "<written-form-of-src>"
  /// else "IfDefined(<written-form-of-src>)".
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const;
  virtual SumDescriptor *Copy() const;

  OptionalSumDescriptor(SumDescriptor *src): src_(src) { }
  virtual ~OptionalSumDescriptor() { delete src_; }
 private:
  SumDescriptor *src_;
};

/// This is the normal base-case of SumDescriptor which just wraps a
/// ForwardingDescriptor.  The written form is any valid ForwardingDescriptor,
/// e.g. in the simplest case just `tdnn3`.
/// See also ConstantSumDescriptor().
class SimpleSumDescriptor: public SumDescriptor {
 public:
  virtual void GetDependencies(const Index &ind,
                               std::vector<Cindex> *dependencies) const;
  virtual bool IsComputable(const Index &ind,
                            const CindexSet &cindex_set,
                            std::vector<Cindex> *used_inputs) const;
  virtual int32 Dim(const Nnet &nnet) const;

  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // This function appends to "node_indexes" a list (not necessarily sorted or
  // unique) of all the node indexes that this descriptor may forward data from.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual int32 Modulus() const { return src_->Modulus(); }
  /// written form is: if required_ == true, "<written-form-of-src>"
  /// else "IfDefined(<written-form-of-src>)".
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const;
  virtual SumDescriptor *Copy() const;

  SimpleSumDescriptor(ForwardingDescriptor *src): src_(src) { }
  virtual ~SimpleSumDescriptor() { delete src_; }

  // this function is not in the shared interface. it's used
  // in class ModelCollapser.
  const ForwardingDescriptor &Src() const { return *src_; }
 private:
  ForwardingDescriptor *src_;
};


/// This is an alternative base-case of SumDescriptor (an alternative to
/// SimpleSumDescriptor) which represents a constant term, e.g. `Const(1.0,
/// 512)`.  Note that this is not allowed to appear inside conditionals
/// such as IfDefined() or Failover(); this is enforced in the parsing
/// code involving class GeneralDescriptor.
/// The written form is: `Const(<value>, <dimension>)`, e.g.
/// `Const(-1.0, 512)`
class ConstantSumDescriptor: public SumDescriptor {
 public:
  virtual void GetDependencies(const Index &ind,
                               std::vector<Cindex> *dependencies) const { }
  virtual bool IsComputable(const Index &ind,
                            const CindexSet &cindex_set,
                            std::vector<Cindex> *used_inputs) const {
    return true;
  }
  virtual int32 Dim(const Nnet &nnet) const { return dim_; }
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const { }
  virtual int32 Modulus() const { return 1; }
  /// The written form is: `Const(<value>, <dimension>)`, e.g.
  /// `Const(-1.0, 512)`
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const;
  virtual SumDescriptor *Copy() const;

  ConstantSumDescriptor(BaseFloat value, int32 dim);
  virtual ~ConstantSumDescriptor() {}
 private:
  BaseFloat value_;
  int32 dim_;
};

/// BinarySumDescriptor can represent either A + B, or (A if defined, else B).
/// Other expressions such as A + (B if defined, else zero), (A if defined, else
/// zero) + (B if defined, else zero), and (A if defined, else B if defined,
/// else zero) can be expressed using combinations of the two provided options
/// for BinarySumDescriptor and the variant
class BinarySumDescriptor: public SumDescriptor {
 public:
  enum Operation {
    kSumOperation,  // A + B
    kFailoverOperation, // A if defined, else B.
  };
  virtual void GetDependencies(const Index &ind,
                               std::vector<Cindex> *dependencies) const;
  virtual bool IsComputable(const Index &ind,
                            const CindexSet &cindex_set,
                            std::vector<Cindex> *used_inputs) const;
  virtual int32 Dim(const Nnet &nnet) const;
  virtual BaseFloat GetScaleForNode(int32 node_index) const;

  // This function appends to "node_indexes" a list (not necessarily sorted or
  // unique) of all the node indexes that this descriptor may forward data from.
  virtual void GetNodeDependencies(std::vector<int32> *node_indexes) const;
  virtual int32 Modulus() const;
  /// Written form is: if op_ == kSum then "Sum(<src1>, <src2>)";
  /// if op_ == kFailover, then "Failover(<src1>, <src2>)"
  /// If you need more than binary operations, just use Sum(a, Sum(b, c)).
  virtual void WriteConfig(std::ostream &os,
                           const std::vector<std::string> &node_names) const;
  virtual SumDescriptor *Copy() const;
  BinarySumDescriptor(Operation op, SumDescriptor *src1, SumDescriptor *src2):
      op_(op), src1_(src1), src2_(src2) {}
  virtual ~BinarySumDescriptor() { delete src1_; delete src2_; }
 private:
  Operation op_;
  SumDescriptor *src1_;
  SumDescriptor *src2_;
};


// A Descriptor concatenates over its parts, so its feature-dimension will
// be the sum of the feature-dimensions of its parts.  In a valid Descriptor,
// "parts" will be nonempty.  Each part may be (in general) a summation, but
// usually a summation with just one term.
class Descriptor {
 public:
  int32 Dim(const Nnet &nnet) const;

  // The Parse method is used for reading a config-file-style represenation.
  // Internally this uses class GeneralDescriptor to read and normalize the
  // input.  Assumes the input has already been tokenized into an array of
  // strings by DescriptorTokenize(); it moves the begin-pointer "next_token" to
  // account for each token that it consumes.  Prints warning and returns false on
  // error (including if there was junk after the last token).  The input tokens
  // should be terminated with a token that says "end of input".
  bool Parse(const std::vector<std::string> &node_names,
             const std::string **next_token);

  // Write in config-file format.
  // if parts_.size() == 1, written form is just "<written-form-of-part0>"
  // otherwise, written form is "Append(<written-form-of-part0>, <written-form-of-part1>,  ... )".
  void WriteConfig(std::ostream &os,
                   const std::vector<std::string> &node_names) const;

  /// This function exists to enable us to manage optional dependencies,
  /// i.e. for making sense of expressions like (A + (B is present)) and (A if
  /// present; if not, B).  Suppose we are trying to compute the index "ind",
  /// and the user represents that "cindex_set" is the set of Cindexes are
  /// available to the computation; then this function will return true if we
  /// can compute the expression given these inputs; and if so, will output to
  /// "used_inputs" the list of Cindexes (not necessarily unique) that this
  /// expression will include.  Otherwise it will return false and set
  /// used_inputs to the empty vector.
  ///
  ///  @param [in] ind  The index that we want to compute at the output of the
  ///                   Descriptor.
  ///  @param [in] cindex_set  The set of Cindexes that are available at the
  ///                   input of the Descriptor.
  ///  @param [out] used_inputs If non-NULL, if this function returns true then
  ///                  to this vector will be *appended* the inputs that will
  ///                  actually participate in the computation.  Else (if non-NULL) it
  ///                  will be left unchanged.
  ///  @return Returns true if this output is computable given the provided
  ///          inputs.
  void GetDependencies(const Index &index,
                       std::vector<Cindex> *used_inputs) const;

  /// Has the same purpose and interface as the IsComputable function of the
  /// SumDescriptor function.   Outputs to used_inputs rather than appending
  /// to it, though.  used_inputs will not be sorted or have repeats removed.
  bool IsComputable(const Index &ind,
                    const CindexSet &cindex_set,
                    std::vector<Cindex> *used_inputs) const;

  // This function outputs to "node_indexes" a list (not necessarily sorted or
  // unique) of all the node indexes that this descriptor may forward data from.
  void GetNodeDependencies(std::vector<int32> *node_indexes) const;

  // see Modulus function of ForwardingDescriptor for explanation.
  int32 Modulus() const;

  /// Returns the number of parts that are concatenated over.
  int32 NumParts() const { return parts_.size(); }
  /// returns the n'th part.
  const SumDescriptor &Part(int32 n) const;

  Descriptor() { }
  /// Copy constructor
  Descriptor(const Descriptor &other) { *this = other; }
  /// Assignment operator.
  Descriptor &operator = (const Descriptor &other);
  /// Takes ownership of pointers in "parts".
  Descriptor(const std::vector<SumDescriptor*> &parts):
      parts_(parts) { }
  /// Destructor
  ~Descriptor() { Destroy(); }
 private:
  void Destroy();
  // the elements of parts_ are owned here.
  std::vector<SumDescriptor*> parts_;
};


/**
   This class is only used when parsing Descriptors.  It is useful for normalizing
   descriptors that are structured in an invalid or redundant way, into a
   form that can be turned into a real Descriptor.
 */
struct GeneralDescriptor {
  enum DescriptorType { kAppend, kSum, kFailover, kIfDefined, kOffset, kSwitch,
                        kRound, kReplaceIndex, kScale, kConst, kNodeName };

  // The Parse method is used for reading a config-file-style represenation.
  // Assumes the input has already been tokenized into an array of strings, and
  // it moves the begin-pointer "next_token" to account for token that it
  // consumes.  Calls KALDI_ERR on error.  The list of tokens should be
  // terminated with a string saying "end of input".  Does not check that all
  // the input has been consumed-- the caller should do that [check that
  // **next_token == "end of input" after calling.]
  static GeneralDescriptor *Parse(const std::vector<std::string> &node_names,
                                  const std::string **next_token);

  explicit GeneralDescriptor(DescriptorType t, int32 value1 = -1,
                             int32 value2 = -1, BaseFloat alpha = 0.0):
      descriptor_type_(t), value1_(value1), value2_(value2),
      alpha_(alpha) { }


  ~GeneralDescriptor() { DeletePointers(&descriptors_); }

  GeneralDescriptor *GetNormalizedDescriptor() const;

  Descriptor *ConvertToDescriptor();

  // prints in text form-- this is really only used for debug.
  void Print(const std::vector<std::string> &node_names,
             std::ostream &os);

 private:
  KALDI_DISALLOW_COPY_AND_ASSIGN(GeneralDescriptor);

  DescriptorType descriptor_type_;

  // value1_ is only relevant if:
  //    (a) descriptor_type_ == kReplaceIndex (value1_ is 1 for t, 2 for x)
  //    (b) descriptor_type_ == kNodeName (value1_ is the index of the node)
  //    (c) descriptor_type_ == kOffset (value1_ is the t offset).
  //    (d) descriptor_type_ == kConst (value1_ is the dimension and alpha_
  //                                   is the value).
  int32 value1_;
  // value2_ is only relevant if
  //    (a) descriptor_type == kReplaceIndex (value2_ is the value
  //                                          we replace the index with).
  //    (b) descriptor_type_ == kOffset (value2_ is the x offset)
  int32 value2_;

  // alpha is only relevant if
  //  (a) descriptor_type == kScale, and this will be the scaling factor.
  //  (b) descriptor_type == kConst; this is the value, and value1_ is set to the
  //          dimension.
  BaseFloat alpha_;

  // For any descriptor types that take args of type kDescriptor, a list of those
  // args.  Pointers owned here.
  std::vector<GeneralDescriptor*> descriptors_;

  //  parses an Append() or Sum() or Switch() expression after the "Append(" or
  //  "Sum(" or "Switch(" has been read.
  void ParseAppendOrSumOrSwitch(const std::vector<std::string> &node_names,
                                const std::string **next_token);
  // parse an IfDefined() expression after the IfDefined( has already been
  // read.
  void ParseIfDefined(const std::vector<std::string> &node_names,
                      const std::string **next_token);
  // ... and so on.
  void ParseOffset(const std::vector<std::string> &node_names,
                   const std::string **next_token);
  void ParseSwitch(const std::vector<std::string> &node_names,
                   const std::string **next_token);
  void ParseFailover(const std::vector<std::string> &node_names,
                     const std::string **next_token);
  void ParseRound(const std::vector<std::string> &node_names,
                  const std::string **next_token);
  void ParseScale(const std::vector<std::string> &node_names,
                  const std::string **next_token);
  void ParseConst(const std::vector<std::string> &node_names,
                  const std::string **next_token);
  void ParseReplaceIndex(const std::vector<std::string> &node_names,
                         const std::string **next_token);



  // Used inside NormalizeAppend().  Return the number of terms there
  // would be in a single consolidated Append() expressions, and asserts that in
  // whichever branch of any other expressions we take, the number of terms is
  // the same.
  int32 NumAppendTerms() const;
  // Used inside NormalizeAppend().  Gets one of the appended terms from this
  // descriptor, with 0 <= term < NumAppendTerms().  Answer is newly allocated.
  GeneralDescriptor *GetAppendTerm(int32 term) const;


  // Normalizes w.r.t. Append expressions by moving Append() to the outside.
  // Called only at the top level.
  GeneralDescriptor *NormalizeAppend() const;

  // This call does all other types of normalization except for normalizing
  // Append() expressions (which is assumed to have been done already).  Returns
  // true if anything was changed.
  static bool Normalize(GeneralDescriptor *ptr);

  SumDescriptor *ConvertToSumDescriptor() const;
  ForwardingDescriptor *ConvertToForwardingDescriptor() const;

};




} // namespace nnet3
} // namespace kaldi

#endif