Home | History | Annotate | Download | only in fst 
      1 // lookahead-filter.h
      2 
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //     http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 //
     15 // Copyright 2005-2010 Google, Inc.
     16 // Author: riley (at) google.com (Michael Riley)
     17 //
     18 // \file
     19 // Composition filters to support lookahead matchers, useful for improving
     20 // composition efficiency with certain inputs.
     21 
     22 #ifndef FST_LIB_LOOKAHEAD_FILTER_H__
     23 #define FST_LIB_LOOKAHEAD_FILTER_H__
     24 
     25 #include <vector>
     26 using std::vector;
     27 
     28 #include <fst/fst.h>
     29 #include <fst/lookahead-matcher.h>
     30 
     31 
     32 namespace fst {
     33 
     34 // Identifies and verifies the capabilities of the matcher to be used for
     35 // lookahead with the composition filters below. This version is passed
     36 // the matchers.
     37 template <class M1, class M2>
     38 MatchType LookAheadMatchType(const M1 &m1, const M2 &m2) {
     39   MatchType type1 = m1.Type(false);
     40   MatchType type2 = m2.Type(false);
     41   if (type1 == MATCH_OUTPUT &&
     42       m1.Flags() & kOutputLookAheadMatcher)
     43     return MATCH_OUTPUT;
     44   else if (type2 == MATCH_INPUT &&
     45            m2.Flags() & kInputLookAheadMatcher)
     46     return MATCH_INPUT;
     47   else if (m1.Flags() & kOutputLookAheadMatcher &&
     48            m1.Type(true) == MATCH_OUTPUT)
     49     return MATCH_OUTPUT;
     50   else if (m2.Flags() & kInputLookAheadMatcher &&
     51            m2.Type(true) == MATCH_INPUT)
     52     return MATCH_INPUT;
     53   else
     54     return MATCH_NONE;
     55 }
     56 
     57 // Identifies and verifies the capabilities of the matcher to be used for
     58 // lookahead with the composition filters below. This version uses the
     59 // Fst's default matchers.
     60 template <class Arc>
     61 MatchType LookAheadMatchType(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
     62   LookAheadMatcher< Fst <Arc> > matcher1(fst1, MATCH_OUTPUT);
     63   LookAheadMatcher< Fst <Arc> > matcher2(fst2, MATCH_INPUT);
     64   return LookAheadMatchType(matcher1, matcher2);
     65 }
     66 
     67 //
     68 // LookAheadSelector - a helper class for selecting among possibly
     69 // distinct FST and matcher types w/o using a common base class. This
     70 // lets us avoid virtual function calls.
     71 //
     72 
     73 // Stores and returns the appropriate FST and matcher for lookahead.
     74 // It is templated on the matcher types.  General case has no methods
     75 // since not currently supported.
     76 template <class M1, class M2, MatchType MT>
     77 class LookAheadSelector {
     78 };
     79 
     80 // Stores and returns the appropriate FST and matcher for lookahead.
     81 // Specialized for two matchers of same type with the (match) 'type'
     82 // arg determining which is used for lookahead.
     83 template <class M, MatchType MT>
     84 class LookAheadSelector<M, M, MT> {
     85  public:
     86   typedef typename M::Arc Arc;
     87   typedef typename M::FST F;
     88 
     89   LookAheadSelector(M *lmatcher1, M *lmatcher2, MatchType type)
     90       : lmatcher1_(lmatcher1->Copy()),
     91         lmatcher2_(lmatcher2->Copy()),
     92         type_(type) {}
     93 
     94   LookAheadSelector(const LookAheadSelector<M, M, MT> &selector)
     95       : lmatcher1_(selector.lmatcher1_->Copy()),
     96         lmatcher2_(selector.lmatcher2_->Copy()),
     97         type_(selector.type_) {}
     98 
     99   ~LookAheadSelector() {
    100     delete lmatcher1_;
    101     delete lmatcher2_;
    102   }
    103 
    104   const F &GetFst() const {
    105     return type_ == MATCH_OUTPUT ? lmatcher2_->GetFst() :
    106         lmatcher1_->GetFst();
    107   }
    108 
    109   M *GetMatcher() const {
    110     return type_ == MATCH_OUTPUT ? lmatcher1_ : lmatcher2_;
    111   }
    112 
    113  private:
    114   M *lmatcher1_;
    115   M *lmatcher2_;
    116   MatchType type_;
    117 
    118   void operator=(const LookAheadSelector<M, M, MT> &);  // disallow
    119 };
    120 
    121 // Stores and returns the appropriate FST and matcher for lookahead.
    122 // Specialized for lookahead on input labels.
    123 template <class M1, class M2>
    124 class LookAheadSelector<M1, M2, MATCH_INPUT> {
    125  public:
    126   typedef typename M1::FST F1;
    127 
    128   LookAheadSelector(M1 *lmatcher1, M2 *lmatcher2, MatchType)
    129       : fst_(lmatcher1->GetFst().Copy()),
    130         lmatcher_(lmatcher2->Copy()) {}
    131 
    132   LookAheadSelector(const LookAheadSelector<M1, M2, MATCH_INPUT> &selector)
    133       : fst_(selector.fst_->Copy()),
    134         lmatcher_(selector.lmatcher_->Copy()) {}
    135 
    136   ~LookAheadSelector() {
    137     delete lmatcher_;
    138     delete fst_;
    139   }
    140 
    141   const F1 &GetFst() const { return *fst_; }
    142 
    143   M2 *GetMatcher() const { return lmatcher_; }
    144 
    145  private:
    146   const F1 *fst_;
    147   M2 *lmatcher_;
    148 
    149   void operator=(const LookAheadSelector<M1, M2, MATCH_INPUT> &);  // disallow
    150 };
    151 
    152 
    153 // Stores and returns the appropriate FST and matcher for lookahead.
    154 // Specialized for lookahead on output labels.
    155 template <class M1, class M2>
    156 class LookAheadSelector<M1, M2, MATCH_OUTPUT> {
    157  public:
    158   typedef typename M2::FST F2;
    159 
    160   LookAheadSelector(M1 *lmatcher1, M2 *lmatcher2, MatchType)
    161       : fst_(lmatcher2->GetFst().Copy()),
    162         lmatcher_(lmatcher1->Copy()) {}
    163 
    164   LookAheadSelector(const LookAheadSelector<M1, M2, MATCH_OUTPUT> &selector)
    165       : fst_(selector.fst_->Copy()),
    166         lmatcher_(selector.lmatcher_->Copy()) {}
    167 
    168   ~LookAheadSelector() {
    169     delete lmatcher_;
    170     delete fst_;
    171   }
    172 
    173   const F2 &GetFst() const { return *fst_; }
    174 
    175   M1 *GetMatcher() const { return lmatcher_; }
    176 
    177  private:
    178   const F2 *fst_;
    179   M1 *lmatcher_;
    180 
    181   void operator=(const LookAheadSelector<M1, M2, MATCH_OUTPUT> &);  // disallow
    182 };
    183 
    184 // This filter uses a lookahead matcher in FilterArc(arc1, arc2) to
    185 // examine the future of the composition state (arc1.nextstate,
    186 // arc2.nextstate), blocking moving forward when its determined to be
    187 // non-coaccessible. It is templated on an underlying filter,
    188 // typically the epsilon filter.  Which matcher is the lookahead
    189 // matcher is determined by the template argument MT unless it is
    190 // MATCH_BOTH. In that case, both matcher arguments must be lookahead
    191 // matchers of the same type and one will be selected by
    192 // LookAheadMatchType() based on their capability.
    193 template <class F,
    194           class M1 = LookAheadMatcher<typename F::FST1>,
    195           class M2 = M1,
    196           MatchType MT = MATCH_BOTH>
    197 class LookAheadComposeFilter {
    198  public:
    199   typedef typename F::FST1 FST1;
    200   typedef typename F::FST2 FST2;
    201   typedef typename F::Arc Arc;
    202   typedef typename F::Matcher1 Matcher1;
    203   typedef typename F::Matcher2 Matcher2;
    204   typedef typename F::FilterState FilterState;
    205   typedef LookAheadComposeFilter<F, M1, M2, MT> Filter;
    206 
    207   typedef typename Arc::StateId StateId;
    208   typedef typename Arc::Label Label;
    209   typedef typename Arc::Weight Weight;
    210 
    211   LookAheadComposeFilter(const FST1 &fst1, const FST2 &fst2,
    212                          M1 *matcher1,  M2 *matcher2)
    213       : filter_(fst1, fst2, matcher1, matcher2),
    214         lookahead_type_(MT == MATCH_BOTH ?
    215                         LookAheadMatchType(*filter_.GetMatcher1(),
    216                                            *filter_.GetMatcher2()) : MT),
    217         selector_(filter_.GetMatcher1(), filter_.GetMatcher2(),
    218                   lookahead_type_),
    219         flags_(lookahead_type_ == MATCH_OUTPUT ?
    220                filter_.GetMatcher1()->Flags() :
    221                filter_.GetMatcher2()->Flags()) {
    222     if (lookahead_type_ == MATCH_NONE) {
    223       FSTERROR() << "LookAheadComposeFilter: 1st argument cannot "
    224                  << "match/look-ahead on output labels and 2nd argument "
    225                  << "cannot match/look-ahead on input labels.";
    226     }
    227     selector_.GetMatcher()->InitLookAheadFst(selector_.GetFst());
    228   }
    229 
    230   LookAheadComposeFilter(const LookAheadComposeFilter<F, M1, M2, MT> &filter,
    231                          bool safe = false)
    232       : filter_(filter.filter_, safe),
    233         lookahead_type_(filter.lookahead_type_),
    234         selector_(filter_.GetMatcher1(), filter_.GetMatcher2(),
    235                   lookahead_type_),
    236         flags_(filter.flags_) {
    237     selector_.GetMatcher()->InitLookAheadFst(selector_.GetFst(), true);
    238   }
    239 
    240   FilterState Start() const {
    241     return filter_.Start();
    242   }
    243 
    244   void SetState(StateId s1, StateId s2, const FilterState &f) {
    245     filter_.SetState(s1, s2, f);
    246   }
    247 
    248   FilterState FilterArc(Arc *arc1, Arc *arc2) const {
    249     lookahead_arc_ = false;
    250 
    251     const FilterState &f = filter_.FilterArc(arc1, arc2);
    252     if (f == FilterState::NoState())
    253       return FilterState::NoState();
    254 
    255     return LookAheadOutput() ? LookAheadFilterArc(arc1, arc2, f) :
    256         LookAheadFilterArc(arc2, arc1, f);
    257   }
    258 
    259   void FilterFinal(Weight *weight1, Weight *weight2) const {
    260     filter_.FilterFinal(weight1, weight2);
    261   }
    262 
    263   // Return resp matchers. Ownership stays with filter.
    264   Matcher1 *GetMatcher1() { return filter_.GetMatcher1(); }
    265   Matcher2 *GetMatcher2() { return filter_.GetMatcher2(); }
    266 
    267   const LookAheadSelector<Matcher1, Matcher2, MT> &Selector() const {
    268     return selector_;
    269   }
    270 
    271   uint64 Properties(uint64 inprops) const {
    272     uint64 outprops = filter_.Properties(inprops);
    273     if (lookahead_type_ == MATCH_NONE)
    274       outprops |= kError;
    275     return outprops;
    276   }
    277 
    278   uint32 LookAheadFlags() const { return flags_; }
    279 
    280   bool LookAheadArc() const { return lookahead_arc_; }
    281 
    282   bool LookAheadOutput() const {
    283     if (MT == MATCH_OUTPUT)
    284       return true;
    285     else if (MT == MATCH_INPUT)
    286       return false;
    287     else if (lookahead_type_ == MATCH_OUTPUT)
    288       return true;
    289     else
    290       return false;
    291   }
    292 
    293  private:
    294   FilterState LookAheadFilterArc(Arc *arca, Arc *arcb,
    295                                  const FilterState &f) const {
    296     Label &labela = LookAheadOutput() ? arca->olabel : arca->ilabel;
    297 
    298     if (labela != 0 && !(flags_ & kLookAheadNonEpsilons))
    299       return f;
    300     if (labela == 0 && !(flags_ & kLookAheadEpsilons))
    301       return f;
    302 
    303     lookahead_arc_ = true;
    304     selector_.GetMatcher()->SetState(arca->nextstate);
    305 
    306     return selector_.GetMatcher()->LookAheadFst(selector_.GetFst(),
    307                                                 arcb->nextstate) ? f :
    308                                                 FilterState::NoState();
    309   }
    310 
    311   F filter_;                    // Underlying filter
    312   MatchType lookahead_type_;    // Lookahead match type
    313   LookAheadSelector<Matcher1, Matcher2, MT> selector_;
    314   uint32 flags_;                // Lookahead flags
    315   mutable bool lookahead_arc_;  // Look-ahead performed at last FilterArc()?
    316 
    317   void operator=(const LookAheadComposeFilter<F, M1, M2> &);  // disallow
    318 };
    319 
    320 
    321 // This filter adds weight-pushing to a lookahead composition filter
    322 // using the LookAheadWeight() method of matcher argument. It is
    323 // templated on an underlying lookahead filter, typically the basic
    324 // lookahead filter. Weight-pushing in composition brings weights
    325 // forward as much as possible based on the lookahead information.
    326 template <class F,
    327           class M1 = LookAheadMatcher<typename F::FST1>,
    328           class M2 = M1,
    329           MatchType MT = MATCH_BOTH>
    330 class PushWeightsComposeFilter {
    331  public:
    332   typedef typename F::FST1 FST1;
    333   typedef typename F::FST2 FST2;
    334   typedef typename F::Arc Arc;
    335   typedef typename F::Matcher1 Matcher1;
    336   typedef typename F::Matcher2 Matcher2;
    337   typedef typename F::FilterState FilterState1;
    338   typedef WeightFilterState<typename Arc::Weight> FilterState2;
    339   typedef PairFilterState<FilterState1, FilterState2> FilterState;
    340 
    341   typedef typename Arc::StateId StateId;
    342   typedef typename Arc::Label Label;
    343   typedef typename Arc::Weight Weight;
    344 
    345   PushWeightsComposeFilter(const FST1 &fst1, const FST2 &fst2,
    346                          M1 *matcher1,  M2 *matcher2)
    347       : filter_(fst1, fst2, matcher1, matcher2),
    348         f_(FilterState::NoState()) {}
    349 
    350   PushWeightsComposeFilter(const PushWeightsComposeFilter<F, M1, M2, MT>
    351                            &filter,
    352                            bool safe = false)
    353       : filter_(filter.filter_, safe),
    354         f_(FilterState::NoState()) {}
    355 
    356   FilterState Start() const {
    357     return FilterState(filter_.Start(), FilterState2(Weight::One()));
    358   }
    359 
    360   void SetState(StateId s1, StateId s2, const FilterState &f) {
    361     f_ = f;
    362     filter_.SetState(s1, s2, f.GetState1());
    363   }
    364 
    365   FilterState FilterArc(Arc *arc1, Arc *arc2) const {
    366     const FilterState1 &f1 = filter_.FilterArc(arc1, arc2);
    367     if (f1 == FilterState1::NoState())
    368       return FilterState::NoState();
    369 
    370     if (!(LookAheadFlags() & kLookAheadWeight))
    371       return FilterState(f1, FilterState2(Weight::One()));
    372 
    373     const Weight &lweight = filter_.LookAheadArc() ?
    374         Selector().GetMatcher()->LookAheadWeight() : Weight::One();
    375     const FilterState2 &f2 = f_.GetState2();
    376     const Weight &fweight = f2.GetWeight();
    377 
    378     arc2->weight = Divide(Times(arc2->weight, lweight), fweight);
    379     return FilterState(f1, FilterState2(lweight));
    380   }
    381 
    382   void FilterFinal(Weight *weight1, Weight *weight2) const {
    383     filter_.FilterFinal(weight1, weight2);
    384     if (!(LookAheadFlags() & kLookAheadWeight) || *weight1 == Weight::Zero())
    385       return;
    386 
    387     const FilterState2 &f2 = f_.GetState2();
    388     const Weight &fweight = f2.GetWeight();
    389     *weight1 = Divide(*weight1, fweight);
    390   }
    391   // Return resp matchers. Ownership states with filter.
    392   Matcher1 *GetMatcher1() { return filter_.GetMatcher1(); }
    393   Matcher2 *GetMatcher2() { return filter_.GetMatcher2(); }
    394 
    395   const LookAheadSelector<Matcher1, Matcher2, MT> &Selector() const {
    396     return filter_.Selector();
    397   }
    398 
    399   uint32 LookAheadFlags() const { return filter_.LookAheadFlags(); }
    400   bool LookAheadArc() const { return filter_.LookAheadArc(); }
    401   bool LookAheadOutput() const { return filter_.LookAheadOutput(); }
    402 
    403   uint64 Properties(uint64 props) const {
    404     return filter_.Properties(props) & kWeightInvariantProperties;
    405   }
    406 
    407  private:
    408   F filter_;                       // Underlying filter
    409   FilterState f_;                  // Current filter state
    410 
    411   void operator=(const PushWeightsComposeFilter<F, M1, M2, MT> &);  // disallow
    412 };
    413 
    414 // This filter adds label-pushing to a lookahead composition filter
    415 // using the LookAheadPrefix() method of the matcher argument. It is
    416 // templated on an underlying filter, typically the basic lookahead
    417 // or weight-pushing lookahead filter. Label-pushing in composition
    418 // matches labels as early as possible based on the lookahead
    419 // information.
    420 template <class F,
    421           class M1 = LookAheadMatcher<typename F::FST1>,
    422           class M2 = M1,
    423           MatchType MT = MATCH_BOTH>
    424 class PushLabelsComposeFilter {
    425  public:
    426   typedef typename F::FST1 FST1;
    427   typedef typename F::FST2 FST2;
    428   typedef typename F::Arc Arc;
    429   typedef typename Arc::StateId StateId;
    430   typedef typename Arc::Label Label;
    431   typedef typename Arc::Weight Weight;
    432 
    433   typedef MultiEpsMatcher<typename F::Matcher1> Matcher1;
    434   typedef MultiEpsMatcher<typename F::Matcher2> Matcher2;
    435   typedef typename F::FilterState FilterState1;
    436   typedef IntegerFilterState<typename Arc::Label> FilterState2;
    437   typedef PairFilterState<FilterState1, FilterState2> FilterState;
    438 
    439   PushLabelsComposeFilter(const FST1 &fst1, const FST2 &fst2,
    440                          M1 *matcher1,  M2 *matcher2)
    441       : filter_(fst1, fst2, matcher1, matcher2),
    442         f_(FilterState::NoState()),
    443         fst1_(filter_.GetMatcher1()->GetFst()),
    444         fst2_(filter_.GetMatcher2()->GetFst()),
    445         matcher1_(fst1_, MATCH_OUTPUT,
    446                   filter_.LookAheadOutput() ? kMultiEpsList : kMultiEpsLoop,
    447                   filter_.GetMatcher1(),
    448                   false),
    449         matcher2_(fst2_, MATCH_INPUT,
    450                   filter_.LookAheadOutput() ? kMultiEpsLoop : kMultiEpsList,
    451                   filter_.GetMatcher2(),
    452                   false) {}
    453 
    454   PushLabelsComposeFilter(const PushLabelsComposeFilter<F, M1, M2, MT> &filter,
    455                           bool safe = false)
    456       : filter_(filter.filter_, safe),
    457         f_(FilterState::NoState()),
    458         fst1_(filter_.GetMatcher1()->GetFst()),
    459         fst2_(filter_.GetMatcher2()->GetFst()),
    460         matcher1_(fst1_,  MATCH_OUTPUT,
    461                   filter_.LookAheadOutput() ? kMultiEpsList : kMultiEpsLoop,
    462                   filter_.GetMatcher1(),
    463                   false),
    464         matcher2_(fst2_, MATCH_INPUT,
    465                   filter_.LookAheadOutput() ? kMultiEpsLoop : kMultiEpsList,
    466                   filter_.GetMatcher2(),
    467                   false) {
    468   }
    469 
    470   FilterState Start() const {
    471     return FilterState(filter_.Start(), FilterState2(kNoLabel));
    472   }
    473 
    474   void SetState(StateId s1, StateId s2, const FilterState &f) {
    475     f_ = f;
    476     filter_.SetState(s1, s2, f.GetState1());
    477     if (!(LookAheadFlags() & kLookAheadPrefix))
    478       return;
    479 
    480     narcsa_ = LookAheadOutput() ? internal::NumArcs(fst1_, s1)
    481         : internal::NumArcs(fst2_, s2);
    482 
    483     const FilterState2 &f2 = f_.GetState2();
    484     const Label &flabel = f2.GetState();
    485 
    486     GetMatcher1()->ClearMultiEpsLabels();
    487     GetMatcher2()->ClearMultiEpsLabels();
    488     if (flabel != kNoLabel) {                   // Have a lookahead label?
    489       GetMatcher1()->AddMultiEpsLabel(flabel);  // Yes, make it a multi-epsilon
    490       GetMatcher2()->AddMultiEpsLabel(flabel);  // label so that it matches the
    491     }                                           // implicit epsilon arc to be
    492   }                                             // modified below when pushing.
    493 
    494   FilterState FilterArc(Arc *arc1, Arc *arc2) const {
    495     if (!(LookAheadFlags() & kLookAheadPrefix))
    496       return FilterState(filter_.FilterArc(arc1, arc2),
    497                          FilterState2(kNoLabel));
    498 
    499     const FilterState2 &f2 = f_.GetState2();
    500     const Label &flabel = f2.GetState();
    501     if (flabel != kNoLabel)             // Have a lookahead label?
    502       return LookAheadOutput() ? PushedLabelFilterArc(arc1, arc2, flabel) :
    503           PushedLabelFilterArc(arc2, arc1, flabel);
    504 
    505     const FilterState1 &f1 = filter_.FilterArc(arc1, arc2);
    506     if (f1 == FilterState1::NoState())
    507       return FilterState::NoState();
    508 
    509     if (!filter_.LookAheadArc())
    510       return FilterState(f1, FilterState2(kNoLabel));
    511 
    512     return LookAheadOutput() ? PushLabelFilterArc(arc1, arc2, f1) :
    513         PushLabelFilterArc(arc2, arc1, f1);
    514   }
    515 
    516   void FilterFinal(Weight *weight1, Weight *weight2) const {
    517     filter_.FilterFinal(weight1, weight2);
    518     if (!(LookAheadFlags() & kLookAheadPrefix) ||
    519         *weight1 == Weight::Zero())
    520       return;
    521 
    522     const FilterState2 &f2 = f_.GetState2();
    523     const Label &flabel = f2.GetState();
    524     if (flabel != kNoLabel)
    525       *weight1 = Weight::Zero();
    526   }
    527 
    528   // Return resp matchers. Ownership states with filter.
    529   Matcher1 *GetMatcher1() { return &matcher1_; }
    530   Matcher2 *GetMatcher2() { return &matcher2_; }
    531 
    532   uint64 Properties(uint64 iprops) const {
    533     uint64 oprops = filter_.Properties(iprops);
    534     if (LookAheadOutput())
    535       return oprops & kOLabelInvariantProperties;
    536     else
    537       return oprops & kILabelInvariantProperties;
    538   }
    539 
    540  private:
    541   const LookAheadSelector<typename F::Matcher1, typename F::Matcher2, MT>
    542   &Selector() const {
    543     return filter_.Selector();
    544   }
    545 
    546   // Consumes an already pushed label.
    547   FilterState PushedLabelFilterArc(Arc *arca, Arc *arcb,
    548                                    Label flabel) const {
    549     Label &labela = LookAheadOutput() ? arca->olabel : arca->ilabel;
    550     const Label &labelb = LookAheadOutput() ? arcb->ilabel : arcb->olabel;
    551 
    552     if (labelb != kNoLabel) {
    553       return FilterState::NoState();    // Block non- (multi-) epsilon label
    554     } else if (labela == flabel) {
    555       labela = 0;                       // Convert match to multi-eps to eps
    556       return Start();
    557     } else if (labela == 0) {
    558       if (narcsa_ == 1)
    559         return f_;                      // Take eps; keep state w/ label
    560       Selector().GetMatcher()->SetState(arca->nextstate);
    561       if (Selector().GetMatcher()->LookAheadLabel(flabel))
    562         return f_;                      // Take eps; keep state w/ label
    563       else
    564         return FilterState::NoState();  // Block non-coaccessible path
    565     } else {
    566       return FilterState::NoState();    // Block mismatch to multi-eps label
    567     }
    568   }
    569 
    570   // Pushes a label forward when possible.
    571   FilterState PushLabelFilterArc(Arc *arca, Arc *arcb,
    572                                  const FilterState1 &f1) const {
    573     Label &labela = LookAheadOutput() ? arca->olabel : arca->ilabel;
    574     const Label &labelb = LookAheadOutput() ? arcb->olabel : arcb->ilabel;
    575 
    576     if (labelb != 0)                   // No place to push.
    577       return FilterState(f1, FilterState2(kNoLabel));
    578     if (labela != 0 &&                 // Wrong lookahead prefix type?
    579         LookAheadFlags() & kLookAheadNonEpsilonPrefix)
    580       return FilterState(f1, FilterState2(kNoLabel));
    581 
    582     Arc larc(kNoLabel, kNoLabel, Weight::Zero(), kNoStateId);
    583 
    584     if (Selector().GetMatcher()->LookAheadPrefix(&larc)) {  // Have prefix arc?
    585       labela = LookAheadOutput() ? larc.ilabel : larc.olabel;
    586       arcb->ilabel = larc.ilabel;      // Yes, go forward on that arc,
    587       arcb->olabel = larc.olabel;      // thus pushing the label.
    588       arcb->weight = Times(arcb->weight, larc.weight);
    589       arcb->nextstate = larc.nextstate;
    590       return FilterState(f1, FilterState2(labela));
    591     } else {
    592       return FilterState(f1, FilterState2(kNoLabel));
    593     }
    594   }
    595 
    596   uint32 LookAheadFlags() const { return filter_.LookAheadFlags(); }
    597   bool LookAheadArc() const { return filter_.LookAheadArc(); }
    598   bool LookAheadOutput() const { return filter_.LookAheadOutput(); }
    599 
    600   F filter_;                  // Underlying filter
    601   FilterState f_ ;            // Current filter state
    602   const FST1 &fst1_;
    603   const FST2 &fst2_;
    604   Matcher1 matcher1_;         // Multi-epsilon matcher for fst1
    605   Matcher2 matcher2_;         // Multi-epsilon matcher for fst2
    606   ssize_t narcsa_;            // Number of arcs leaving look-ahead match FST
    607 
    608   void operator=(const PushLabelsComposeFilter<F, M1, M2, MT> &);  // disallow
    609 };
    610 
    611 //
    612 // CONVENIENCE CLASS useful for setting up composition with a default
    613 // look-ahead matcher and filter.
    614 //
    615 
    616 template <class A, MatchType type>  // MATCH_NONE
    617 class DefaultLookAhead {
    618  public:
    619   typedef Matcher< Fst<A> > M;
    620   typedef SequenceComposeFilter<M> ComposeFilter;
    621   typedef M FstMatcher;
    622 };
    623 
    624 // Specializes for MATCH_INPUT to allow lookahead.
    625 template <class A>
    626 class DefaultLookAhead<A, MATCH_INPUT> {
    627  public:
    628   typedef LookAheadMatcher< Fst<A> > M;
    629   typedef SequenceComposeFilter<M> SF;
    630   typedef LookAheadComposeFilter<SF, M> ComposeFilter;
    631   typedef M FstMatcher;
    632 };
    633 
    634 // Specializes for MATCH_OUTPUT to allow lookahead.
    635 template <class A>
    636 class DefaultLookAhead<A, MATCH_OUTPUT> {
    637  public:
    638   typedef LookAheadMatcher< Fst<A> > M;
    639   typedef AltSequenceComposeFilter<M> SF;
    640   typedef LookAheadComposeFilter<SF, M> ComposeFilter;
    641   typedef M FstMatcher;
    642 };
    643 
    644 // Specializes for StdArc to allow weight and label pushing.
    645 template <>
    646 class DefaultLookAhead<StdArc, MATCH_INPUT> {
    647  public:
    648   typedef StdArc A;
    649   typedef LookAheadMatcher< Fst<A> > M;
    650   typedef SequenceComposeFilter<M> SF;
    651   typedef LookAheadComposeFilter<SF, M> LF;
    652   typedef PushWeightsComposeFilter<LF, M> WF;
    653   typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
    654   typedef M FstMatcher;
    655 };
    656 
    657 // Specializes for StdArc to allow weight and label pushing.
    658 template <>
    659 class DefaultLookAhead<StdArc, MATCH_OUTPUT> {
    660  public:
    661   typedef StdArc A;
    662   typedef LookAheadMatcher< Fst<A> > M;
    663   typedef AltSequenceComposeFilter<M> SF;
    664   typedef LookAheadComposeFilter<SF, M>  LF;
    665   typedef PushWeightsComposeFilter<LF, M> WF;
    666   typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
    667   typedef M FstMatcher;
    668 };
    669 
    670 // Specializes for LogArc to allow weight and label pushing.
    671 template <>
    672 class DefaultLookAhead<LogArc, MATCH_INPUT> {
    673  public:
    674   typedef LogArc A;
    675   typedef LookAheadMatcher< Fst<A> > M;
    676   typedef SequenceComposeFilter<M> SF;
    677   typedef LookAheadComposeFilter<SF, M> LF;
    678   typedef PushWeightsComposeFilter<LF, M> WF;
    679   typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
    680   typedef M FstMatcher;
    681 };
    682 
    683 // Specializes for LogArc to allow weight and label pushing.
    684 template <>
    685 class DefaultLookAhead<LogArc, MATCH_OUTPUT> {
    686  public:
    687   typedef LogArc A;
    688   typedef LookAheadMatcher< Fst<A> > M;
    689   typedef AltSequenceComposeFilter<M> SF;
    690   typedef LookAheadComposeFilter<SF, M> LF;
    691   typedef PushWeightsComposeFilter<LF, M> WF;
    692   typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
    693   typedef M FstMatcher;
    694 };
    695 
    696 }  // namespace fst
    697 
    698 #endif  // FST_LIB_LOOKAHEAD_FILTER_H__
    699