extensions/pdt/compose.h

// compose.h

// 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
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Compose a PDT and an FST.

#ifndef FST_EXTENSIONS_PDT_COMPOSE_H__
#define FST_EXTENSIONS_PDT_COMPOSE_H__

#include <list>

#include <fst/extensions/pdt/pdt.h>
#include <fst/compose.h>

namespace fst {

// Return paren arcs for Find(kNoLabel).
const uint32 kParenList =  0x00000001;

// Return a kNolabel loop for Find(paren).
const uint32 kParenLoop =  0x00000002;

// This class is a matcher that treats parens as multi-epsilon labels.
// It is most efficient if the parens are in a range non-overlapping with
// the non-paren labels.
template <class F>
class ParenMatcher {
 public:
  typedef SortedMatcher<F> M;
  typedef typename M::FST FST;
  typedef typename M::Arc Arc;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;

  ParenMatcher(const FST &fst, MatchType match_type,
               uint32 flags = (kParenLoop | kParenList))
      : matcher_(fst, match_type),
        match_type_(match_type),
        flags_(flags) {
    if (match_type == MATCH_INPUT) {
      loop_.ilabel = kNoLabel;
      loop_.olabel = 0;
    } else {
      loop_.ilabel = 0;
      loop_.olabel = kNoLabel;
    }
    loop_.weight = Weight::One();
    loop_.nextstate = kNoStateId;
  }

  ParenMatcher(const ParenMatcher<F> &matcher, bool safe = false)
      : matcher_(matcher.matcher_, safe),
        match_type_(matcher.match_type_),
        flags_(matcher.flags_),
        open_parens_(matcher.open_parens_),
        close_parens_(matcher.close_parens_),
        loop_(matcher.loop_) {
    loop_.nextstate = kNoStateId;
  }

  ParenMatcher<F> *Copy(bool safe = false) const {
    return new ParenMatcher<F>(*this, safe);
  }

  MatchType Type(bool test) const { return matcher_.Type(test); }

  void SetState(StateId s) {
    matcher_.SetState(s);
    loop_.nextstate = s;
  }

  bool Find(Label match_label);

  bool Done() const {
    return done_;
  }

  const Arc& Value() const {
    return paren_loop_ ? loop_ : matcher_.Value();
  }

  void Next();

  const FST &GetFst() const { return matcher_.GetFst(); }

  uint64 Properties(uint64 props) const { return matcher_.Properties(props); }

  uint32 Flags() const { return matcher_.Flags(); }

  void AddOpenParen(Label label) {
    if (label == 0) {
      FSTERROR() << "ParenMatcher: Bad open paren label: 0";
    } else {
      open_parens_.Insert(label);
    }
  }

  void AddCloseParen(Label label) {
    if (label == 0) {
      FSTERROR() << "ParenMatcher: Bad close paren label: 0";
    } else {
      close_parens_.Insert(label);
    }
  }

  void RemoveOpenParen(Label label) {
    if (label == 0) {
      FSTERROR() << "ParenMatcher: Bad open paren label: 0";
    } else {
      open_parens_.Erase(label);
    }
  }

  void RemoveCloseParen(Label label) {
    if (label == 0) {
      FSTERROR() << "ParenMatcher: Bad close paren label: 0";
    } else {
      close_parens_.Erase(label);
    }
  }

  void ClearOpenParens() {
    open_parens_.Clear();
  }

  void ClearCloseParens() {
    close_parens_.Clear();
  }

  bool IsOpenParen(Label label) const {
    return open_parens_.Member(label);
  }

  bool IsCloseParen(Label label) const {
    return close_parens_.Member(label);
  }

 private:
  // Advances matcher to next open paren if it exists, returning true.
  // O.w. returns false.
  bool NextOpenParen();

  // Advances matcher to next open paren if it exists, returning true.
  // O.w. returns false.
  bool NextCloseParen();

  M matcher_;
  MatchType match_type_;          // Type of match to perform
  uint32 flags_;

  // open paren label set
  CompactSet<Label, kNoLabel> open_parens_;

  // close paren label set
  CompactSet<Label, kNoLabel> close_parens_;


  bool open_paren_list_;         // Matching open paren list
  bool close_paren_list_;        // Matching close paren list
  bool paren_loop_;              // Current arc is the implicit paren loop
  mutable Arc loop_;             // For non-consuming symbols
  bool done_;                    // Matching done

  void operator=(const ParenMatcher<F> &);  // Disallow
};

template <class M> inline
bool ParenMatcher<M>::Find(Label match_label) {
  open_paren_list_ = false;
  close_paren_list_ = false;
  paren_loop_ = false;
  done_ = false;

  // Returns all parenthesis arcs
  if (match_label == kNoLabel && (flags_ & kParenList)) {
    if (open_parens_.LowerBound() != kNoLabel) {
      matcher_.LowerBound(open_parens_.LowerBound());
      open_paren_list_ = NextOpenParen();
      if (open_paren_list_) return true;
    }
    if (close_parens_.LowerBound() != kNoLabel) {
      matcher_.LowerBound(close_parens_.LowerBound());
      close_paren_list_ = NextCloseParen();
      if (close_paren_list_) return true;
    }
  }

  // Returns 'implicit' paren loop
  if (match_label > 0 && (flags_ & kParenLoop) &&
      (IsOpenParen(match_label) || IsCloseParen(match_label))) {
    paren_loop_ = true;
    return true;
  }

  // Returns all other labels
  if (matcher_.Find(match_label))
    return true;

  done_ = true;
  return false;
}

template <class F> inline
void ParenMatcher<F>::Next() {
  if (paren_loop_) {
    paren_loop_ = false;
    done_ = true;
  } else if (open_paren_list_) {
    matcher_.Next();
    open_paren_list_ = NextOpenParen();
    if (open_paren_list_) return;

    if (close_parens_.LowerBound() != kNoLabel) {
      matcher_.LowerBound(close_parens_.LowerBound());
      close_paren_list_ = NextCloseParen();
      if (close_paren_list_) return;
    }
    done_ = !matcher_.Find(kNoLabel);
  } else if (close_paren_list_) {
    matcher_.Next();
    close_paren_list_ = NextCloseParen();
    if (close_paren_list_) return;
    done_ = !matcher_.Find(kNoLabel);
  } else {
    matcher_.Next();
    done_ = matcher_.Done();
  }
}

// Advances matcher to next open paren if it exists, returning true.
// O.w. returns false.
template <class F> inline
bool ParenMatcher<F>::NextOpenParen() {
  for (; !matcher_.Done(); matcher_.Next()) {
    Label label = match_type_ == MATCH_INPUT ?
        matcher_.Value().ilabel : matcher_.Value().olabel;
    if (label > open_parens_.UpperBound())
      return false;
    if (IsOpenParen(label))
      return true;
  }
  return false;
}

// Advances matcher to next close paren if it exists, returning true.
// O.w. returns false.
template <class F> inline
bool ParenMatcher<F>::NextCloseParen() {
  for (; !matcher_.Done(); matcher_.Next()) {
    Label label = match_type_ == MATCH_INPUT ?
        matcher_.Value().ilabel : matcher_.Value().olabel;
    if (label > close_parens_.UpperBound())
      return false;
    if (IsCloseParen(label))
      return true;
  }
  return false;
}


template <class F>
class ParenFilter {
 public:
  typedef typename F::FST1 FST1;
  typedef typename F::FST2 FST2;
  typedef typename F::Arc Arc;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;
  typedef typename F::Matcher1 Matcher1;
  typedef typename F::Matcher2 Matcher2;
  typedef typename F::FilterState FilterState1;
  typedef StateId StackId;
  typedef PdtStack<StackId, Label> ParenStack;
  typedef IntegerFilterState<StackId> FilterState2;
  typedef PairFilterState<FilterState1, FilterState2> FilterState;
  typedef ParenFilter<F> Filter;

  ParenFilter(const FST1 &fst1, const FST2 &fst2,
              Matcher1 *matcher1 = 0,  Matcher2 *matcher2 = 0,
              const vector<pair<Label, Label> > *parens = 0,
              bool expand = false, bool keep_parens = true)
      : filter_(fst1, fst2, matcher1, matcher2),
        parens_(parens ? *parens : vector<pair<Label, Label> >()),
        expand_(expand),
        keep_parens_(keep_parens),
        f_(FilterState::NoState()),
        stack_(parens_),
        paren_id_(-1) {
    if (parens) {
      for (size_t i = 0; i < parens->size(); ++i) {
        const pair<Label, Label>  &p = (*parens)[i];
        parens_.push_back(p);
        GetMatcher1()->AddOpenParen(p.first);
        GetMatcher2()->AddOpenParen(p.first);
        if (!expand_) {
          GetMatcher1()->AddCloseParen(p.second);
          GetMatcher2()->AddCloseParen(p.second);
        }
      }
    }
  }

  ParenFilter(const Filter &filter, bool safe = false)
      : filter_(filter.filter_, safe),
        parens_(filter.parens_),
        expand_(filter.expand_),
        keep_parens_(filter.keep_parens_),
        f_(FilterState::NoState()),
        stack_(filter.parens_),
        paren_id_(-1) { }

  FilterState Start() const {
    return FilterState(filter_.Start(), FilterState2(0));
  }

  void SetState(StateId s1, StateId s2, const FilterState &f) {
    f_ = f;
    filter_.SetState(s1, s2, f_.GetState1());
    if (!expand_)
      return;

    ssize_t paren_id = stack_.Top(f.GetState2().GetState());
    if (paren_id != paren_id_) {
      if (paren_id_ != -1) {
        GetMatcher1()->RemoveCloseParen(parens_[paren_id_].second);
        GetMatcher2()->RemoveCloseParen(parens_[paren_id_].second);
      }
      paren_id_ = paren_id;
      if (paren_id_ != -1) {
        GetMatcher1()->AddCloseParen(parens_[paren_id_].second);
        GetMatcher2()->AddCloseParen(parens_[paren_id_].second);
      }
    }
  }

  FilterState FilterArc(Arc *arc1, Arc *arc2) const {
    FilterState1 f1 = filter_.FilterArc(arc1, arc2);
    const FilterState2 &f2 = f_.GetState2();
    if (f1 == FilterState1::NoState())
      return FilterState::NoState();

    if (arc1->olabel == kNoLabel && arc2->ilabel) {         // arc2 parentheses
      if (keep_parens_) {
        arc1->ilabel = arc2->ilabel;
      } else if (arc2->ilabel) {
        arc2->olabel = arc1->ilabel;
      }
      return FilterParen(arc2->ilabel, f1, f2);
    } else if (arc2->ilabel == kNoLabel && arc1->olabel) {  // arc1 parentheses
      if (keep_parens_) {
        arc2->olabel = arc1->olabel;
      } else {
        arc1->ilabel = arc2->olabel;
      }
      return FilterParen(arc1->olabel, f1, f2);
    } else {
      return FilterState(f1, f2);
    }
  }

  void FilterFinal(Weight *w1, Weight *w2) const {
    if (f_.GetState2().GetState() != 0)
      *w1 = Weight::Zero();
    filter_.FilterFinal(w1, w2);
  }

  // Return resp matchers. Ownership stays with filter.
  Matcher1 *GetMatcher1() { return filter_.GetMatcher1(); }
  Matcher2 *GetMatcher2() { return filter_.GetMatcher2(); }

  uint64 Properties(uint64 iprops) const {
    uint64 oprops = filter_.Properties(iprops);
    return oprops & kILabelInvariantProperties & kOLabelInvariantProperties;
  }

 private:
  const FilterState FilterParen(Label label, const FilterState1 &f1,
                                const FilterState2 &f2) const {
    if (!expand_)
      return FilterState(f1, f2);

    StackId stack_id = stack_.Find(f2.GetState(), label);
    if (stack_id < 0) {
      return FilterState::NoState();
    } else {
      return FilterState(f1, FilterState2(stack_id));
    }
  }

  F filter_;
  vector<pair<Label, Label> > parens_;
  bool expand_;                    // Expands to FST
  bool keep_parens_;               // Retains parentheses in output
  FilterState f_;                  // Current filter state
  mutable ParenStack stack_;
  ssize_t paren_id_;
};

// Class to setup composition options for PDT composition.
// Default is for the PDT as the first composition argument.
template <class Arc, bool left_pdt = true>
class PdtComposeFstOptions : public
ComposeFstOptions<Arc,
                  ParenMatcher< Fst<Arc> >,
                  ParenFilter<AltSequenceComposeFilter<
                                ParenMatcher< Fst<Arc> > > > > {
 public:
  typedef typename Arc::Label Label;
  typedef ParenMatcher< Fst<Arc> > PdtMatcher;
  typedef ParenFilter<AltSequenceComposeFilter<PdtMatcher> > PdtFilter;
  typedef ComposeFstOptions<Arc, PdtMatcher, PdtFilter> COptions;
  using COptions::matcher1;
  using COptions::matcher2;
  using COptions::filter;

  PdtComposeFstOptions(const Fst<Arc> &ifst1,
                    const vector<pair<Label, Label> > &parens,
                       const Fst<Arc> &ifst2, bool expand = false,
                       bool keep_parens = true) {
    matcher1 = new PdtMatcher(ifst1, MATCH_OUTPUT, kParenList);
    matcher2 = new PdtMatcher(ifst2, MATCH_INPUT, kParenLoop);

    filter = new PdtFilter(ifst1, ifst2, matcher1, matcher2, &parens,
                           expand, keep_parens);
  }
};

// Class to setup composition options for PDT with FST composition.
// Specialization is for the FST as the first composition argument.
template <class Arc>
class PdtComposeFstOptions<Arc, false> : public
ComposeFstOptions<Arc,
                  ParenMatcher< Fst<Arc> >,
                  ParenFilter<SequenceComposeFilter<
                                ParenMatcher< Fst<Arc> > > > > {
 public:
  typedef typename Arc::Label Label;
  typedef ParenMatcher< Fst<Arc> > PdtMatcher;
  typedef ParenFilter<SequenceComposeFilter<PdtMatcher> > PdtFilter;
  typedef ComposeFstOptions<Arc, PdtMatcher, PdtFilter> COptions;
  using COptions::matcher1;
  using COptions::matcher2;
  using COptions::filter;

  PdtComposeFstOptions(const Fst<Arc> &ifst1,
                       const Fst<Arc> &ifst2,
                       const vector<pair<Label, Label> > &parens,
                       bool expand = false, bool keep_parens = true) {
    matcher1 = new PdtMatcher(ifst1, MATCH_OUTPUT, kParenLoop);
    matcher2 = new PdtMatcher(ifst2, MATCH_INPUT, kParenList);

    filter = new PdtFilter(ifst1, ifst2, matcher1, matcher2, &parens,
                           expand, keep_parens);
  }
};

enum PdtComposeFilter {
  PAREN_FILTER,          // Bar-Hillel construction; keeps parentheses
  EXPAND_FILTER,         // Bar-Hillel + expansion; removes parentheses
  EXPAND_PAREN_FILTER,   // Bar-Hillel + expansion; keeps parentheses
};

struct PdtComposeOptions {
  bool connect;  // Connect output
  PdtComposeFilter filter_type;  // Which pre-defined filter to use

  explicit PdtComposeOptions(bool c, PdtComposeFilter ft = PAREN_FILTER)
      : connect(c), filter_type(ft) {}
  PdtComposeOptions() : connect(true), filter_type(PAREN_FILTER) {}
};

// Composes pushdown transducer (PDT) encoded as an FST (1st arg) and
// an FST (2nd arg) with the result also a PDT encoded as an Fst. (3rd arg).
// In the PDTs, some transitions are labeled with open or close
// parentheses. To be interpreted as a PDT, the parens must balance on
// a path (see PdtExpand()). The open-close parenthesis label pairs
// are passed in 'parens'.
template <class Arc>
void Compose(const Fst<Arc> &ifst1,
             const vector<pair<typename Arc::Label,
                               typename Arc::Label> > &parens,
             const Fst<Arc> &ifst2,
             MutableFst<Arc> *ofst,
             const PdtComposeOptions &opts = PdtComposeOptions()) {
  bool expand = opts.filter_type != PAREN_FILTER;
  bool keep_parens = opts.filter_type != EXPAND_FILTER;
  PdtComposeFstOptions<Arc, true> copts(ifst1, parens, ifst2,
                                        expand, keep_parens);
  copts.gc_limit = 0;
  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
  if (opts.connect)
    Connect(ofst);
}

// Composes an FST (1st arg) and pushdown transducer (PDT) encoded as
// an FST (2nd arg) with the result also a PDT encoded as an Fst (3rd arg).
// In the PDTs, some transitions are labeled with open or close
// parentheses. To be interpreted as a PDT, the parens must balance on
// a path (see ExpandFst()). The open-close parenthesis label pairs
// are passed in 'parens'.
template <class Arc>
void Compose(const Fst<Arc> &ifst1,
             const Fst<Arc> &ifst2,
             const vector<pair<typename Arc::Label,
                               typename Arc::Label> > &parens,
             MutableFst<Arc> *ofst,
             const PdtComposeOptions &opts = PdtComposeOptions()) {
  bool expand = opts.filter_type != PAREN_FILTER;
  bool keep_parens = opts.filter_type != EXPAND_FILTER;
  PdtComposeFstOptions<Arc, false> copts(ifst1, ifst2, parens,
                                         expand, keep_parens);
  copts.gc_limit = 0;
  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
  if (opts.connect)
    Connect(ofst);
}

}  // namespace fst

#endif  // FST_EXTENSIONS_PDT_COMPOSE_H__