// See www.openfst.org for extensive documentation on this weighted
  // finite-state transducer library.
  //
  // Classes to add lookahead to FST matchers, useful for improving composition
  // efficiency with certain inputs.
  
  #ifndef FST_LOOKAHEAD_MATCHER_H_
  #define FST_LOOKAHEAD_MATCHER_H_
  
  #include <memory>
  #include <utility>
  #include <vector>
  
  #include <fst/flags.h>
  #include <fst/log.h>
  
  #include <fst/add-on.h>
  #include <fst/const-fst.h>
  #include <fst/fst.h>
  #include <fst/label-reachable.h>
  #include <fst/matcher.h>
  
  
  DECLARE_string(save_relabel_ipairs);
  DECLARE_string(save_relabel_opairs);
  
  namespace fst {
  
  // Lookahead matches extend the matcher interface with following additional
  // methods:
  //
  // template <class FST>
  // class LookAheadMatcher {
  //  public:
  //   using Arc = typename FST::Arc;
  //   using Label = typename Arc::Label;
  //   using StateId = typename Arc::StateId;
  //   using Weight = typename Arc::Weight;
  //
  //  // Required constructors.
  //  // This makes a copy of the FST.
  //  LookAheadMatcher(const FST &fst, MatchType match_type);
  //  // This doesn't copy the FST.
  //  LookAheadMatcher(const FST *fst, MatchType match_type);
  //  // This makes a copy of the FST.
  //  // See Copy() below.
  //  LookAheadMatcher(const LookAheadMatcher &matcher, bool safe = false);
  //
  //   // If safe = true, the copy is thread-safe (except the lookahead FST is
  //   // preserved). See Fst<>::Copy() for further doc.
  //   LookaheadMatcher<FST> *Copy(bool safe = false) const override;
  
  //  // Below are methods for looking ahead for a match to a label and more
  //  // generally, to a rational set. Each returns false if there is definitely
  //  // not a match and returns true if there possibly is a match.
  //
  //  // Optionally pre-specifies the lookahead FST that will be passed to
  //  // LookAheadFst() for possible precomputation. If copy is true, then the FST
  //  // argument is a copy of the FST used in the previous call to this method
  //  // (to avoid unnecessary updates).
  //  void InitLookAheadFst(const Fst<Arc> &fst, bool copy = false) override;
  //
  //  // Are there paths from a state in the lookahead FST that can be read from
  //  // the curent matcher state?
  //  bool LookAheadFst(const Fst<Arc> &fst, StateId s) override;
  //
  //  // Can the label be read from the current matcher state after possibly
  //  // following epsilon transitions?
  //  bool LookAheadLabel(Label label) const override;
  //
  //  // The following methods allow looking ahead for an arbitrary rational set
  //  // of strings, specified by an FST and a state from which to begin the
  //  // matching. If the lookahead FST is a transducer, this looks on the side
  //  // different from the matcher's match_type (cf. composition).
  //  // Is there is a single non-epsilon arc found in the lookahead FST that
  //  // begins the path (after possibly following any epsilons) in the last call
  //  // to LookAheadFst? If so, return true and copy it to the arc argument;
  //  // otherwise, return false. Non-trivial implementations are useful for
  //  // label-pushing in composition.
  //  bool LookAheadPrefix(Arc *arc) override;
  //
  //  // Gives an estimate of the combined weight of the paths in the lookahead
  //  // and matcher FSTs for the last call to LookAheadFst. Non-trivial
  //  // implementations are useful for weight-pushing in composition.
  //  Weight LookAheadWeight() const override;
  // };
  
  // Look-ahead flags.
  // Matcher is a lookahead matcher when match_type is MATCH_INPUT.
  constexpr uint32 kInputLookAheadMatcher = 0x00000010;
  
  // Matcher is a lookahead matcher when match_type is MATCH_OUTPUT.
  constexpr uint32 kOutputLookAheadMatcher = 0x00000020;
  
  // Is a non-trivial implementation of LookAheadWeight() method defined and
  // if so, should it be used?
  constexpr uint32 kLookAheadWeight = 0x00000040;
  
  // Is a non-trivial implementation of LookAheadPrefix() method defined and
  // if so, should it be used?
  constexpr uint32 kLookAheadPrefix = 0x00000080;
  
  // Look-ahead of matcher FST non-epsilon arcs?
  constexpr uint32 kLookAheadNonEpsilons = 0x00000100;
  
  // Look-ahead of matcher FST epsilon arcs?
  constexpr uint32 kLookAheadEpsilons = 0x00000200;
  
  // Ignore epsilon paths for the lookahead prefix? This gives correct results in
  // composition only with an appropriate composition filter since it depends on
  // the filter blocking the ignored paths.
  constexpr uint32 kLookAheadNonEpsilonPrefix = 0x00000400;
  
  // For LabelLookAheadMatcher, save relabeling data to file?
  constexpr uint32 kLookAheadKeepRelabelData = 0x00000800;
  
  // Flags used for lookahead matchers.
  constexpr uint32 kLookAheadFlags = 0x00000ff0;
  
  // LookAhead Matcher interface, templated on the Arc definition; used
  // for lookahead matcher specializations that are returned by the
  // InitMatcher() Fst method.
  template <class Arc>
  class LookAheadMatcherBase : public MatcherBase<Arc> {
   public:
    using Label = typename Arc::Label;
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
  
    virtual void InitLookAheadFst(const Fst<Arc> &, bool copy = false) = 0;
    virtual bool LookAheadFst(const Fst<Arc> &, StateId) = 0;
    virtual bool LookAheadLabel(Label) const = 0;
  
    // Suggested concrete implementation of lookahead methods.
  
    bool LookAheadPrefix(Arc *arc) const {
      if (prefix_arc_.nextstate != kNoStateId) {
        *arc = prefix_arc_;
        return true;
      } else {
        return false;
      }
    }
  
    Weight LookAheadWeight() const { return weight_; }
  
   protected:
    // Concrete implementations for lookahead helper methods.
  
    void ClearLookAheadWeight() { weight_ = Weight::One(); }
  
    void SetLookAheadWeight(Weight weight) { weight_ = std::move(weight); }
  
    void ClearLookAheadPrefix() { prefix_arc_.nextstate = kNoStateId; }
  
    void SetLookAheadPrefix(Arc arc) { prefix_arc_ = std::move(arc); }
  
   private:
    Arc prefix_arc_;
    Weight weight_;
  };
  
  // Doesn't actually lookahead, just declares that the future looks good.
  template <class M>
  class TrivialLookAheadMatcher
      : public LookAheadMatcherBase<typename M::FST::Arc> {
   public:
    using FST = typename M::FST;
    using Arc = typename FST::Arc;
    using Label = typename Arc::Label;
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
  
    // This makes a copy of the FST.
    TrivialLookAheadMatcher(const FST &fst, MatchType match_type)
        : matcher_(fst, match_type) {}
  
    // This doesn't copy the FST.
    TrivialLookAheadMatcher(const FST *fst, MatchType match_type)
        : matcher_(fst, match_type) {}
  
    // This makes a copy of the FST.
    TrivialLookAheadMatcher(const TrivialLookAheadMatcher<M> &lmatcher,
                            bool safe = false)
        : matcher_(lmatcher.matcher_, safe) {}
  
    TrivialLookAheadMatcher<M> *Copy(bool safe = false) const override {
      return new TrivialLookAheadMatcher<M>(*this, safe);
    }
  
    MatchType Type(bool test) const override { return matcher_.Type(test); }
  
    void SetState(StateId s) final { return matcher_.SetState(s); }
  
    bool Find(Label label) final { return matcher_.Find(label); }
  
    bool Done() const final { return matcher_.Done(); }
  
    const Arc &Value() const final { return matcher_.Value(); }
  
    void Next() final { matcher_.Next(); }
  
    Weight Final(StateId s) const final { return matcher_.Final(s); }
  
    ssize_t Priority(StateId s) final { return matcher_.Priority(s); }
  
    const FST &GetFst() const override { return matcher_.GetFst(); }
  
    uint64 Properties(uint64 props) const override {
      return matcher_.Properties(props);
    }
  
    uint32 Flags() const override {
      return matcher_.Flags() | kInputLookAheadMatcher | kOutputLookAheadMatcher;
    }
  
    // Lookahead methods (all trivial).
  
    void InitLookAheadFst(const Fst<Arc> &fst, bool copy = false) override {}
  
    bool LookAheadFst(const Fst<Arc> &, StateId) final { return true; }
  
    bool LookAheadLabel(Label) const final { return true; }
  
    bool LookAheadPrefix(Arc *) const { return false; }
  
    Weight LookAheadWeight() const { return Weight::One(); }
  
   private:
    M matcher_;
  };
  
  // Look-ahead of one transition. Template argument flags accepts flags to
  // control behavior.
  template <class M,
            uint32 flags = kLookAheadNonEpsilons | kLookAheadEpsilons |
                           kLookAheadWeight | kLookAheadPrefix>
  class ArcLookAheadMatcher : public LookAheadMatcherBase<typename M::FST::Arc> {
   public:
    using FST = typename M::FST;
    using Arc = typename FST::Arc;
    using Label = typename Arc::Label;
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
    using MatcherData = NullAddOn;
  
    using LookAheadMatcherBase<Arc>::ClearLookAheadWeight;
    using LookAheadMatcherBase<Arc>::LookAheadWeight;
    using LookAheadMatcherBase<Arc>::SetLookAheadWeight;
    using LookAheadMatcherBase<Arc>::ClearLookAheadPrefix;
    using LookAheadMatcherBase<Arc>::LookAheadPrefix;
    using LookAheadMatcherBase<Arc>::SetLookAheadPrefix;
  
    enum : uint32 { kFlags = flags };
  
    // This makes a copy of the FST.
    ArcLookAheadMatcher(
        const FST &fst, MatchType match_type,
        std::shared_ptr<MatcherData> data = std::shared_ptr<MatcherData>())
        : matcher_(fst, match_type),
          fst_(matcher_.GetFst()),
          lfst_(nullptr),
          state_(kNoStateId) {}
  
    // This doesn't copy the FST.
    ArcLookAheadMatcher(
        const FST *fst, MatchType match_type,
        std::shared_ptr<MatcherData> data = std::shared_ptr<MatcherData>())
        : matcher_(fst, match_type),
          fst_(matcher_.GetFst()),
          lfst_(nullptr),
          state_(kNoStateId) {}
  
    // This makes a copy of the FST.
    ArcLookAheadMatcher(const ArcLookAheadMatcher<M, flags> &lmatcher,
                        bool safe = false)
        : matcher_(lmatcher.matcher_, safe),
          fst_(matcher_.GetFst()),
          lfst_(lmatcher.lfst_),
          state_(kNoStateId) {}
  
    // General matcher methods.
    ArcLookAheadMatcher<M, flags> *Copy(bool safe = false) const override {
      return new ArcLookAheadMatcher<M, flags>(*this, safe);
    }
  
    MatchType Type(bool test) const override { return matcher_.Type(test); }
  
    void SetState(StateId s) final {
      state_ = s;
      matcher_.SetState(s);
    }
  
    bool Find(Label label) final { return matcher_.Find(label); }
  
    bool Done() const final { return matcher_.Done(); }
  
    const Arc &Value() const final { return matcher_.Value(); }
  
    void Next() final { matcher_.Next(); }
  
    Weight Final(StateId s) const final { return matcher_.Final(s); }
  
    ssize_t Priority(StateId s) final { return matcher_.Priority(s); }
  
    const FST &GetFst() const override { return fst_; }
  
    uint64 Properties(uint64 props) const override {
      return matcher_.Properties(props);
    }
  
    uint32 Flags() const override {
      return matcher_.Flags() | kInputLookAheadMatcher | kOutputLookAheadMatcher |
             kFlags;
    }
  
    const MatcherData *GetData() const { return nullptr; }
  
    std::shared_ptr<MatcherData> GetSharedData() const {
      return std::shared_ptr<MatcherData>();
    }
  
    // Look-ahead methods.
  
    void InitLookAheadFst(const Fst<Arc> &fst, bool copy = false) override {
      lfst_ = &fst;
    }
  
    // Checks if there is a matching (possibly super-final) transition
    // at (state_, s).
    bool LookAheadFst(const Fst<Arc> &, StateId) final;
  
    bool LookAheadLabel(Label label) const final { return matcher_.Find(label); }
  
   private:
    mutable M matcher_;
    const FST &fst_;        // Matcher FST.
    const Fst<Arc> *lfst_;  // Look-ahead FST.
    StateId state_;         // Matcher state.
  };
  
  template <class M, uint32 flags>
  bool ArcLookAheadMatcher<M, flags>::LookAheadFst(const Fst<Arc> &fst,
                                                   StateId s) {
    if (&fst != lfst_) InitLookAheadFst(fst);
    bool result = false;
    ssize_t nprefix = 0;
    if (kFlags & kLookAheadWeight) ClearLookAheadWeight();
    if (kFlags & kLookAheadPrefix) ClearLookAheadPrefix();
    if (fst_.Final(state_) != Weight::Zero() &&
        lfst_->Final(s) != Weight::Zero()) {
      if (!(kFlags & (kLookAheadWeight | kLookAheadPrefix))) return true;
      ++nprefix;
      if (kFlags & kLookAheadWeight) {
        SetLookAheadWeight(
            Plus(LookAheadWeight(), Times(fst_.Final(state_), lfst_->Final(s))));
      }
      result = true;
    }
    if (matcher_.Find(kNoLabel)) {
      if (!(kFlags & (kLookAheadWeight | kLookAheadPrefix))) return true;
      ++nprefix;
      if (kFlags & kLookAheadWeight) {
        for (; !matcher_.Done(); matcher_.Next()) {
          SetLookAheadWeight(Plus(LookAheadWeight(), matcher_.Value().weight));
        }
      }
      result = true;
    }
    for (ArcIterator<Fst<Arc>> aiter(*lfst_, s); !aiter.Done(); aiter.Next()) {
      const auto &arc = aiter.Value();
      Label label = kNoLabel;
      switch (matcher_.Type(false)) {
        case MATCH_INPUT:
          label = arc.olabel;
          break;
        case MATCH_OUTPUT:
          label = arc.ilabel;
          break;
        default:
          FSTERROR() << "ArcLookAheadMatcher::LookAheadFst: Bad match type";
          return true;
      }
      if (label == 0) {
        if (!(kFlags & (kLookAheadWeight | kLookAheadPrefix))) return true;
        if (!(kFlags & kLookAheadNonEpsilonPrefix)) ++nprefix;
        if (kFlags & kLookAheadWeight) {
          SetLookAheadWeight(Plus(LookAheadWeight(), arc.weight));
        }
        result = true;
      } else if (matcher_.Find(label)) {
        if (!(kFlags & (kLookAheadWeight | kLookAheadPrefix))) return true;
        for (; !matcher_.Done(); matcher_.Next()) {
          ++nprefix;
          if (kFlags & kLookAheadWeight) {
            SetLookAheadWeight(Plus(LookAheadWeight(),
                                    Times(arc.weight, matcher_.Value().weight)));
          }
          if ((kFlags & kLookAheadPrefix) && nprefix == 1)
            SetLookAheadPrefix(arc);
        }
        result = true;
      }
    }
    if (kFlags & kLookAheadPrefix) {
      if (nprefix == 1) {
        ClearLookAheadWeight();  // Avoids double counting.
      } else {
        ClearLookAheadPrefix();
      }
    }
    return result;
  }
  
  // Template argument flags accepts flags to control behavior. It must include
  // precisely one of kInputLookAheadMatcher or kOutputLookAheadMatcher.
  template <class M,
            uint32 flags = kLookAheadEpsilons | kLookAheadWeight |
                           kLookAheadPrefix | kLookAheadNonEpsilonPrefix |
                           kLookAheadKeepRelabelData,
            class Accumulator = DefaultAccumulator<typename M::Arc>,
            class Reachable = LabelReachable<typename M::Arc, Accumulator>>
  class LabelLookAheadMatcher
      : public LookAheadMatcherBase<typename M::FST::Arc> {
   public:
    using FST = typename M::FST;
    using Arc = typename FST::Arc;
    using Label = typename Arc::Label;
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
    using MatcherData = typename Reachable::Data;
  
    using LookAheadMatcherBase<Arc>::ClearLookAheadWeight;
    using LookAheadMatcherBase<Arc>::LookAheadWeight;
    using LookAheadMatcherBase<Arc>::SetLookAheadWeight;
    using LookAheadMatcherBase<Arc>::ClearLookAheadPrefix;
    using LookAheadMatcherBase<Arc>::LookAheadPrefix;
    using LookAheadMatcherBase<Arc>::SetLookAheadPrefix;
  
    enum : uint32 { kFlags = flags };
  
    // This makes a copy of the FST.
    LabelLookAheadMatcher(
        const FST &fst, MatchType match_type,
        std::shared_ptr<MatcherData> data = std::shared_ptr<MatcherData>(),
        Accumulator *accumulator = nullptr)
        : matcher_(fst, match_type),
          lfst_(nullptr),
          state_(kNoStateId),
          error_(false) {
      Init(fst, match_type, data, accumulator);
    }
  
    // This doesn't copy the FST.
    LabelLookAheadMatcher(
        const FST *fst, MatchType match_type,
        std::shared_ptr<MatcherData> data = std::shared_ptr<MatcherData>(),
        Accumulator *accumulator = nullptr)
        : matcher_(fst, match_type),
          lfst_(nullptr),
          state_(kNoStateId),
          error_(false) {
      Init(*fst, match_type, data, accumulator);
    }
  
    // This makes a copy of the FST.
    LabelLookAheadMatcher(
        const LabelLookAheadMatcher<M, flags, Accumulator, Reachable> &lmatcher,
        bool safe = false)
        : matcher_(lmatcher.matcher_, safe),
          lfst_(lmatcher.lfst_),
          label_reachable_(lmatcher.label_reachable_
                               ? new Reachable(*lmatcher.label_reachable_, safe)
                               : nullptr),
          state_(kNoStateId),
          error_(lmatcher.error_) {}
  
    LabelLookAheadMatcher<M, flags, Accumulator, Reachable> *Copy(
        bool safe = false) const override {
      return new LabelLookAheadMatcher<M, flags, Accumulator, Reachable>(*this,
                                                                         safe);
    }
  
    MatchType Type(bool test) const override { return matcher_.Type(test); }
  
    void SetState(StateId s) final {
      if (state_ == s) return;
      state_ = s;
      match_set_state_ = false;
      reach_set_state_ = false;
    }
  
    bool Find(Label label) final {
      if (!match_set_state_) {
        matcher_.SetState(state_);
        match_set_state_ = true;
      }
      return matcher_.Find(label);
    }
  
    bool Done() const final { return matcher_.Done(); }
  
    const Arc &Value() const final { return matcher_.Value(); }
  
    void Next() final { matcher_.Next(); }
  
    Weight Final(StateId s) const final { return matcher_.Final(s); }
  
    ssize_t Priority(StateId s) final { return matcher_.Priority(s); }
  
    const FST &GetFst() const override { return matcher_.GetFst(); }
  
    uint64 Properties(uint64 inprops) const override {
      auto outprops = matcher_.Properties(inprops);
      if (error_ || (label_reachable_ && label_reachable_->Error())) {
        outprops |= kError;
      }
      return outprops;
    }
  
    uint32 Flags() const override {
      if (label_reachable_ && label_reachable_->GetData()->ReachInput()) {
        return matcher_.Flags() | kFlags | kInputLookAheadMatcher;
      } else if (label_reachable_ && !label_reachable_->GetData()->ReachInput()) {
        return matcher_.Flags() | kFlags | kOutputLookAheadMatcher;
      } else {
        return matcher_.Flags();
      }
    }
  
    const MatcherData *GetData() const {
      return label_reachable_ ? label_reachable_->GetData() : nullptr;
    };
  
    std::shared_ptr<MatcherData> GetSharedData() const {
      return label_reachable_ ? label_reachable_->GetSharedData()
                              : std::shared_ptr<MatcherData>();
    }
    // Checks if there is a matching (possibly super-final) transition at
    // (state_, s).
    template <class LFST>
    bool LookAheadFst(const LFST &fst, StateId s);
  
    // Required to make class concrete.
    bool LookAheadFst(const Fst<Arc> &fst, StateId s) final {
      return LookAheadFst<Fst<Arc>>(fst, s);
    }
  
    void InitLookAheadFst(const Fst<Arc> &fst, bool copy = false) override {
      lfst_ = &fst;
      if (label_reachable_) {
        const bool reach_input = Type(false) == MATCH_OUTPUT;
        label_reachable_->ReachInit(fst, reach_input, copy);
      }
    }
  
    template <class LFST>
    void InitLookAheadFst(const LFST &fst, bool copy = false) {
      lfst_ = static_cast<const Fst<Arc> *>(&fst);
      if (label_reachable_) {
        const bool reach_input = Type(false) == MATCH_OUTPUT;
        label_reachable_->ReachInit(fst, reach_input, copy);
      }
    }
  
    bool LookAheadLabel(Label label) const final {
      if (label == 0) return true;
      if (label_reachable_) {
        if (!reach_set_state_) {
          label_reachable_->SetState(state_);
          reach_set_state_ = true;
        }
        return label_reachable_->Reach(label);
      } else {
        return true;
      }
    }
  
   private:
    void Init(const FST &fst, MatchType match_type,
              std::shared_ptr<MatcherData> data,
              Accumulator *accumulator) {
      if (!(kFlags & (kInputLookAheadMatcher | kOutputLookAheadMatcher))) {
        FSTERROR() << "LabelLookaheadMatcher: Bad matcher flags: " << kFlags;
        error_ = true;
      }
      const bool reach_input = match_type == MATCH_INPUT;
      if (data) {
        if (reach_input == data->ReachInput()) {
          label_reachable_.reset(new Reachable(data, accumulator));
        }
      } else if ((reach_input && (kFlags & kInputLookAheadMatcher)) ||
                 (!reach_input && (kFlags & kOutputLookAheadMatcher))) {
        label_reachable_.reset(new Reachable(fst, reach_input, accumulator,
                                             kFlags & kLookAheadKeepRelabelData));
      }
    }
  
    mutable M matcher_;
    const Fst<Arc> *lfst_;                        // Look-ahead FST.
    std::unique_ptr<Reachable> label_reachable_;  // Label reachability info.
    StateId state_;                               // Matcher state.
    bool match_set_state_;                        // matcher_.SetState called?
    mutable bool reach_set_state_;                // reachable_.SetState called?
    bool error_;                                  // Error encountered?
  };
  
  template <class M, uint32 flags, class Accumulator, class Reachable>
  template <class LFST>
  inline bool LabelLookAheadMatcher<M, flags, Accumulator,
                                    Reachable>::LookAheadFst(const LFST &fst,
                                                             StateId s) {
    if (static_cast<const Fst<Arc> *>(&fst) != lfst_) InitLookAheadFst(fst);
    ClearLookAheadWeight();
    ClearLookAheadPrefix();
    if (!label_reachable_) return true;
    label_reachable_->SetState(state_, s);
    reach_set_state_ = true;
    bool compute_weight = kFlags & kLookAheadWeight;
    bool compute_prefix = kFlags & kLookAheadPrefix;
    ArcIterator<LFST> aiter(fst, s);
    aiter.SetFlags(kArcNoCache, kArcNoCache);  // Makes caching optional.
    const bool reach_arc = label_reachable_->Reach(
        &aiter, 0, internal::NumArcs(*lfst_, s), compute_weight);
    const auto lfinal = internal::Final(*lfst_, s);
    const bool reach_final =
        lfinal != Weight::Zero() && label_reachable_->ReachFinal();
    if (reach_arc) {
      const auto begin = label_reachable_->ReachBegin();
      const auto end = label_reachable_->ReachEnd();
      if (compute_prefix && end - begin == 1 && !reach_final) {
        aiter.Seek(begin);
        SetLookAheadPrefix(aiter.Value());
        compute_weight = false;
      } else if (compute_weight) {
        SetLookAheadWeight(label_reachable_->ReachWeight());
      }
    }
    if (reach_final && compute_weight) {
      SetLookAheadWeight(reach_arc ? Plus(LookAheadWeight(), lfinal) : lfinal);
    }
    return reach_arc || reach_final;
  }
  
  // Label-lookahead relabeling class.
  template <class Arc, class Data = LabelReachableData<typename Arc::Label>>
  class LabelLookAheadRelabeler {
   public:
    using Label = typename Arc::Label;
    using Reachable = LabelReachable<Arc, DefaultAccumulator<Arc>, Data>;
  
    // Relabels matcher FST (initialization function object).
    template <typename Impl>
    explicit LabelLookAheadRelabeler(std::shared_ptr<Impl> *impl);
  
    // Relabels arbitrary FST. Class LFST should be a label-lookahead FST.
    template <class LFST>
    static void Relabel(MutableFst<Arc> *fst, const LFST &mfst,
                        bool relabel_input) {
      const auto *data = mfst.GetAddOn();
      Reachable reachable(data->First() ? data->SharedFirst()
                                        : data->SharedSecond());
      reachable.Relabel(fst, relabel_input);
    }
  
    // Returns relabeling pairs (cf. relabel.h::Relabel()). Class LFST should be a
    // label-lookahead FST. If avoid_collisions is true, extra pairs are added to
    // ensure no collisions when relabeling automata that have labels unseen here.
    template <class LFST>
    static void RelabelPairs(const LFST &mfst,
                             std::vector<std::pair<Label, Label>> *pairs,
                             bool avoid_collisions = false) {
      const auto *data = mfst.GetAddOn();
      Reachable reachable(data->First() ? data->SharedFirst()
                                        : data->SharedSecond());
      reachable.RelabelPairs(pairs, avoid_collisions);
    }
  };
  
  template <class Arc, class Data>
  template <typename Impl>
  inline LabelLookAheadRelabeler<Arc, Data>::LabelLookAheadRelabeler(
      std::shared_ptr<Impl> *impl) {
    Fst<Arc> &fst = (*impl)->GetFst();
    auto data = (*impl)->GetSharedAddOn();
    const auto name = (*impl)->Type();
    const bool is_mutable = fst.Properties(kMutable, false);
    std::unique_ptr<MutableFst<Arc>> mfst;
    if (is_mutable) {
      mfst.reset(static_cast<MutableFst<Arc> *>(&fst));
    } else {
      mfst.reset(new VectorFst<Arc>(fst));
    }
    if (data->First()) {  // reach_input.
      Reachable reachable(data->SharedFirst());
      reachable.Relabel(mfst.get(), true);
      if (!FLAGS_save_relabel_ipairs.empty()) {
        std::vector<std::pair<Label, Label>> pairs;
        reachable.RelabelPairs(&pairs, true);
        WriteLabelPairs(FLAGS_save_relabel_ipairs, pairs);
      }
    } else {
      Reachable reachable(data->SharedSecond());
      reachable.Relabel(mfst.get(), false);
      if (!FLAGS_save_relabel_opairs.empty()) {
        std::vector<std::pair<Label, Label>> pairs;
        reachable.RelabelPairs(&pairs, true);
        WriteLabelPairs(FLAGS_save_relabel_opairs, pairs);
      }
    }
    if (!is_mutable) {
      *impl = std::make_shared<Impl>(*mfst, name);
      (*impl)->SetAddOn(data);
    }
  }
  
  // Generic lookahead matcher, templated on the FST definition (a wrapper around
  // a pointer to specific one).
  template <class F>
  class LookAheadMatcher {
   public:
    using FST = F;
    using Arc = typename FST::Arc;
    using Label = typename Arc::Label;
    using StateId = typename Arc::StateId;
    using Weight = typename Arc::Weight;
    using LBase = LookAheadMatcherBase<Arc>;
  
    // This makes a copy of the FST.
    LookAheadMatcher(const FST &fst, MatchType match_type)
        : owned_fst_(fst.Copy()),
          base_(owned_fst_->InitMatcher(match_type)),
          lookahead_(false) {
      if (!base_) base_.reset(new SortedMatcher<FST>(owned_fst_.get(),
                                                     match_type));
    }
  
    // This doesn't copy the FST.
    LookAheadMatcher(const FST *fst, MatchType match_type)
        : base_(fst->InitMatcher(match_type)),
          lookahead_(false) {
      if (!base_) base_.reset(new SortedMatcher<FST>(fst, match_type));
    }
  
    // This makes a copy of the FST.
    LookAheadMatcher(const LookAheadMatcher<FST> &matcher, bool safe = false)
        : base_(matcher.base_->Copy(safe)),
          lookahead_(matcher.lookahead_) { }
  
    // Takes ownership of base.
    explicit LookAheadMatcher(MatcherBase<Arc> *base)
        : base_(base), lookahead_(false) {}
  
    LookAheadMatcher<FST> *Copy(bool safe = false) const {
      return new LookAheadMatcher<FST>(*this, safe);
    }
  
    MatchType Type(bool test) const { return base_->Type(test); }
  
    void SetState(StateId s) { base_->SetState(s); }
  
    bool Find(Label label) { return base_->Find(label); }
  
    bool Done() const { return base_->Done(); }
  
    const Arc &Value() const { return base_->Value(); }
  
    void Next() { base_->Next(); }
  
    Weight Final(StateId s) const { return base_->Final(s); }
  
    ssize_t Priority(StateId s) { return base_->Priority(s); }
  
    const FST &GetFst() const {
      return static_cast<const FST &>(base_->GetFst());
    }
  
    uint64 Properties(uint64 props) const { return base_->Properties(props); }
  
    uint32 Flags() const { return base_->Flags(); }
  
    bool LookAheadLabel(Label label) const {
      if (LookAheadCheck()) {
        return static_cast<LBase *>(base_.get())->LookAheadLabel(label);
      } else {
        return true;
      }
    }
  
    bool LookAheadFst(const Fst<Arc> &fst, StateId s) {
      if (LookAheadCheck()) {
        return static_cast<LBase *>(base_.get())->LookAheadFst(fst, s);
      } else {
        return true;
      }
    }
  
    Weight LookAheadWeight() const {
      if (LookAheadCheck()) {
        return static_cast<LBase *>(base_.get())->LookAheadWeight();
      } else {
        return Weight::One();
      }
    }
  
    bool LookAheadPrefix(Arc *arc) const {
      if (LookAheadCheck()) {
        return static_cast<LBase *>(base_.get())->LookAheadPrefix(arc);
      } else {
        return false;
      }
    }
  
    void InitLookAheadFst(const Fst<Arc> &fst, bool copy = false) {
      if (LookAheadCheck()) {
        static_cast<LBase *>(base_.get())->InitLookAheadFst(fst, copy);
      }
    }
  
   private:
    bool LookAheadCheck() const {
      if (!lookahead_) {
        lookahead_ =
            base_->Flags() & (kInputLookAheadMatcher | kOutputLookAheadMatcher);
        if (!lookahead_) {
          FSTERROR() << "LookAheadMatcher: No look-ahead matcher defined";
        }
      }
      return lookahead_;
    }
  
    std::unique_ptr<const FST> owned_fst_;
    std::unique_ptr<MatcherBase<Arc>> base_;
    mutable bool lookahead_;
  
    LookAheadMatcher &operator=(const LookAheadMatcher &) = delete;
  };
  
  }  // namespace fst
  
  #endif  // FST_LOOKAHEAD_MATCHER_H_