FST  openfst-1.7.2
OpenFst Library
compose.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Class to compute the composition of two FSTs.
5 
6 #ifndef FST_COMPOSE_H_
7 #define FST_COMPOSE_H_
8 
9 #include <algorithm>
10 #include <memory>
11 #include <utility>
12 
13 #include <fst/log.h>
14 
15 #include <fst/cache.h>
16 #include <fst/compose-filter.h>
17 #include <fst/fst-decl.h> // For optional argument declarations
18 #include <fst/lookahead-filter.h>
19 #include <fst/matcher.h>
20 #include <fst/state-table.h>
21 #include <fst/test-properties.h>
22 
23 
24 namespace fst {
25 
26 // Delayed composition options templated on the arc type, the matcher,
27 // the composition filter, and the composition state table. By
28 // default, the matchers, filter, and state table are constructed by
29 // composition. If set below, the user can instead pass in these
30 // objects; in that case, ComposeFst takes their ownership. This
31 // version controls composition implemented between generic Fst<Arc>
32 // types and a shared matcher type M for Fst<Arc>. This should be
33 // adequate for most applications, giving a reasonable tradeoff
34 // between efficiency and code sharing (but see ComposeFstImplOptions).
35 template <class Arc, class M = Matcher<Fst<Arc>>,
36  class Filter = SequenceComposeFilter<M>,
37  class StateTable =
38  GenericComposeStateTable<Arc, typename Filter::FilterState>>
40  M *matcher1; // FST1 matcher.
41  M *matcher2; // FST2 matcher.
42  Filter *filter; // Composition filter.
43  StateTable *state_table; // Composition state table.
44 
45  explicit ComposeFstOptions(const CacheOptions &opts = CacheOptions(),
46  M *matcher1 = nullptr, M *matcher2 = nullptr,
47  Filter *filter = nullptr,
48  StateTable *state_table = nullptr)
49  : CacheOptions(opts),
50  matcher1(matcher1),
51  matcher2(matcher2),
52  filter(filter),
53  state_table(state_table) {}
54 };
55 
56 // Forward declaration of ComposeFstMatcher.
57 template <class C, class F, class T>
59 
60 // Delayed composition options templated on the two matcher types, the
61 // composition filter, the composition state table and the cache store. By
62 // default, the matchers, filter, state table and cache store are constructed
63 // by composition. If set below, the user can instead pass in these objects; in
64 // that case, ComposeFst takes their ownership. This version controls
65 // composition implemented using arbitrary matchers (of the same arc type but
66 // otherwise arbitrary FST type). The user must ensure the matchers are
67 // compatible. These options permit the most efficient use, but shares the
68 // least code. This is for advanced use only in the most demanding or
69 // specialized applications that can benefit from it; otherwise, prefer
70 // ComposeFstOptions).
71 template <class M1, class M2, class Filter = SequenceComposeFilter<M1, M2>,
72  class StateTable = GenericComposeStateTable<
73  typename M1::Arc, typename Filter::FilterState>,
74  class CacheStore = DefaultCacheStore<typename M1::Arc>>
75 struct ComposeFstImplOptions : public CacheImplOptions<CacheStore> {
76  M1 *matcher1; // FST1 matcher (see matcher.h)....
77  M2 *matcher2; // FST2 matcher.
78  Filter *filter; // Composition filter (see compose-filter.h).
79  StateTable
80  *state_table; // Composition state table (see compose-state-table.h).
81  bool own_state_table; // ComposeFstImpl takes ownership of 'state_table'?
82  bool allow_noncommute; // Allow non-commutative weights
83 
84  explicit ComposeFstImplOptions(const CacheOptions &opts,
85  M1 *matcher1 = nullptr, M2 *matcher2 = nullptr,
86  Filter *filter = nullptr,
87  StateTable *state_table = nullptr)
88  : CacheImplOptions<CacheStore>(opts),
89  matcher1(matcher1),
90  matcher2(matcher2),
91  filter(filter),
92  state_table(state_table),
93  own_state_table(true),
94  allow_noncommute(false) {}
95 
97  M1 *matcher1 = nullptr, M2 *matcher2 = nullptr,
98  Filter *filter = nullptr,
99  StateTable *state_table = nullptr)
100  : CacheImplOptions<CacheStore>(opts),
101  matcher1(matcher1),
102  matcher2(matcher2),
103  filter(filter),
104  state_table(state_table),
105  own_state_table(true),
106  allow_noncommute(false) {}
107 
109  : matcher1(nullptr),
110  matcher2(nullptr),
111  filter(nullptr),
112  state_table(nullptr),
113  own_state_table(true),
114  allow_noncommute(false) {}
115 };
116 
117 namespace internal {
118 
119 // Implementation of delayed composition. This base class is common to the
120 // variants with different matchers, composition filters and state tables.
121 template <class Arc, class CacheStore = DefaultCacheStore<Arc>,
122  class F = ComposeFst<Arc, CacheStore>>
124  : public CacheBaseImpl<typename CacheStore::State, CacheStore> {
125  public:
126  using FST = F;
127  using Label = typename Arc::Label;
128  using StateId = typename Arc::StateId;
129  using Weight = typename Arc::Weight;
130 
131  using State = typename CacheStore::State;
133 
134  using FstImpl<Arc>::SetType;
139 
140  using CacheImpl::HasStart;
141  using CacheImpl::HasFinal;
142  using CacheImpl::HasArcs;
143  using CacheImpl::SetFinal;
144  using CacheImpl::SetStart;
145 
147  : CacheImpl(opts) {}
148 
149  ComposeFstImplBase(const CacheOptions &opts) : CacheImpl(opts) {}
150 
151  ComposeFstImplBase(const ComposeFstImplBase &impl) : CacheImpl(impl, true) {
152  SetType(impl.Type());
153  SetProperties(impl.Properties(), kCopyProperties);
154  SetInputSymbols(impl.InputSymbols());
155  SetOutputSymbols(impl.OutputSymbols());
156  }
157 
158  virtual ComposeFstImplBase *Copy() const = 0;
159 
160  ~ComposeFstImplBase() override {}
161 
163  if (!HasStart()) {
164  const auto start = ComputeStart();
165  if (start != kNoStateId) SetStart(start);
166  }
167  return CacheImpl::Start();
168  }
169 
171  if (!HasFinal(s)) SetFinal(s, ComputeFinal(s));
172  return CacheImpl::Final(s);
173  }
174 
175  virtual void Expand(StateId s) = 0;
176 
177  size_t NumArcs(StateId s) {
178  if (!HasArcs(s)) Expand(s);
179  return CacheImpl::NumArcs(s);
180  }
181 
183  if (!HasArcs(s)) Expand(s);
184  return CacheImpl::NumInputEpsilons(s);
185  }
186 
188  if (!HasArcs(s)) Expand(s);
190  }
191 
193  if (!HasArcs(s)) Expand(s);
194  CacheImpl::InitArcIterator(s, data);
195  }
196 
197  virtual MatcherBase<Arc> *InitMatcher(const F &fst,
198  MatchType match_type) const {
199  // Use the default matcher if no override is provided.
200  return nullptr;
201  }
202 
203  protected:
204  virtual StateId ComputeStart() = 0;
205  virtual Weight ComputeFinal(StateId s) = 0;
206 };
207 
208 // Implementation of delayed composition templated on the matchers (see
209 // matcher.h), composition filter (see compose-filter.h) and the composition
210 // state table (see compose-state-table.h).
211 template <class CacheStore, class Filter, class StateTable>
213  : public ComposeFstImplBase<typename CacheStore::Arc, CacheStore> {
214  public:
215  using Matcher1 = typename Filter::Matcher1;
216  using Matcher2 = typename Filter::Matcher2;
217 
218  using FST1 = typename Matcher1::FST;
219  using FST2 = typename Matcher2::FST;
220 
221  using Arc = typename CacheStore::Arc;
222  using Label = typename Arc::Label;
223  using StateId = typename Arc::StateId;
224  using Weight = typename Arc::Weight;
225 
226  using FilterState = typename Filter::FilterState;
227  using State = typename CacheStore::State;
228 
230 
231  using StateTuple = typename StateTable::StateTuple;
232 
233  friend class ComposeFstMatcher<CacheStore, Filter, StateTable>;
234 
237  using FstImpl<Arc>::SetType;
239 
240  template <class M1, class M2>
241  ComposeFstImpl(const FST1 &fst1, const FST2 &fst2,
242  const ComposeFstImplOptions<M1, M2, Filter, StateTable,
243  CacheStore> &opts);
244 
246  : ComposeFstImplBase<Arc, CacheStore>(impl),
247  filter_(new Filter(*impl.filter_, true)),
248  matcher1_(filter_->GetMatcher1()),
249  matcher2_(filter_->GetMatcher2()),
250  fst1_(matcher1_->GetFst()),
251  fst2_(matcher2_->GetFst()),
252  state_table_(new StateTable(*impl.state_table_)),
253  own_state_table_(true),
254  match_type_(impl.match_type_) {}
255 
256  ~ComposeFstImpl() override {
257  if (own_state_table_) delete state_table_;
258  }
259 
260  ComposeFstImpl *Copy() const override { return new ComposeFstImpl(*this); }
261 
262  uint64 Properties() const override { return Properties(kFstProperties); }
263 
264  // Sets error if found, and returns other FST impl properties.
265  uint64 Properties(uint64 mask) const override {
266  if ((mask & kError) &&
267  (fst1_.Properties(kError, false) || fst2_.Properties(kError, false) ||
268  (matcher1_->Properties(0) & kError) ||
269  (matcher2_->Properties(0) & kError) |
270  (filter_->Properties(0) & kError) ||
271  state_table_->Error())) {
272  SetProperties(kError, kError);
273  }
274  return FstImpl<Arc>::Properties(mask);
275  }
276 
277  // Arranges it so that the first arg to OrderedExpand is the Fst
278  // that will be matched on.
279  void Expand(StateId s) override {
280  const auto &tuple = state_table_->Tuple(s);
281  const auto s1 = tuple.StateId1();
282  const auto s2 = tuple.StateId2();
283  filter_->SetState(s1, s2, tuple.GetFilterState());
284  if (MatchInput(s1, s2)) {
285  OrderedExpand(s, fst2_, s2, fst1_, s1, matcher2_, true);
286  } else {
287  OrderedExpand(s, fst1_, s1, fst2_, s2, matcher1_, false);
288  }
289  }
290 
291  const FST1 &GetFst1() const { return fst1_; }
292 
293  const FST2 &GetFst2() const { return fst2_; }
294 
295  const Matcher1 *GetMatcher1() const { return matcher1_; }
296 
297  Matcher1 *GetMatcher1() { return matcher1_; }
298 
299  const Matcher2 *GetMatcher2() const { return matcher2_; }
300 
301  Matcher2 *GetMatcher2() { return matcher2_; }
302 
303  const Filter *GetFilter() const { return filter_.get(); }
304 
305  Filter *GetFilter() { return filter_.get(); }
306 
307  const StateTable *GetStateTable() const { return state_table_; }
308 
309  StateTable *GetStateTable() { return state_table_; }
310 
312  MatchType match_type) const override {
313  const auto test_props = match_type == MATCH_INPUT
316  // If both matchers support 'match_type' and we have a guarantee that a
317  // call to 'filter_->FilterArc(arc1, arc2)' will not modify the ilabel of
318  // arc1 when MATCH_INPUT or the olabel or arc2 when MATCH_OUTPUT, then
319  // ComposeFstMatcher can be used.
320  if ((matcher1_->Type(false) == match_type) &&
321  (matcher2_->Type(false) == match_type) &&
322  (filter_->Properties(test_props) == test_props)) {
323  return new ComposeFstMatcher<
324  CacheStore, Filter, StateTable>(&fst, match_type);
325  }
326  return nullptr;
327  }
328 
329  private:
330  // This does that actual matching of labels in the composition. The
331  // arguments are ordered so matching is called on state 'sa' of
332  // 'fsta' for each arc leaving state 'sb' of 'fstb'. The 'match_input' arg
333  // determines whether the input or output label of arcs at 'sb' is
334  // the one to match on.
335  template <class FST, class Matcher>
336  void OrderedExpand(StateId s, const Fst<Arc> &, StateId sa, const FST &fstb,
337  StateId sb, Matcher *matchera, bool match_input) {
338  matchera->SetState(sa);
339  // First processes non-consuming symbols (e.g., epsilons) on FSTA.
340  const Arc loop(match_input ? 0 : kNoLabel, match_input ? kNoLabel : 0,
341  Weight::One(), sb);
342  MatchArc(s, matchera, loop, match_input);
343  // Then processes matches on FSTB.
344  for (ArcIterator<FST> iterb(fstb, sb); !iterb.Done(); iterb.Next()) {
345  MatchArc(s, matchera, iterb.Value(), match_input);
346  }
347  CacheImpl::SetArcs(s);
348  }
349 
350  // Matches a single transition from 'fstb' against 'fata' at 's'.
351  template <class Matcher>
352  void MatchArc(StateId s, Matcher *matchera, const Arc &arc,
353  bool match_input) {
354  if (matchera->Find(match_input ? arc.olabel : arc.ilabel)) {
355  for (; !matchera->Done(); matchera->Next()) {
356  auto arca = matchera->Value();
357  auto arcb = arc;
358  if (match_input) {
359  const auto &fs = filter_->FilterArc(&arcb, &arca);
360  if (fs != FilterState::NoState()) AddArc(s, arcb, arca, fs);
361  } else {
362  const auto &fs = filter_->FilterArc(&arca, &arcb);
363  if (fs != FilterState::NoState()) AddArc(s, arca, arcb, fs);
364  }
365  }
366  }
367  }
368 
369  // Add a matching transition at 's'.
370  void AddArc(StateId s, const Arc &arc1, const Arc &arc2,
371  const FilterState &f) {
372  const StateTuple tuple(arc1.nextstate, arc2.nextstate, f);
373  CacheImpl::EmplaceArc(
374  s, arc1.ilabel, arc2.olabel, Times(arc1.weight, arc2.weight),
375  state_table_->FindState(tuple));
376  }
377 
378  StateId ComputeStart() override {
379  const auto s1 = fst1_.Start();
380  if (s1 == kNoStateId) return kNoStateId;
381  const auto s2 = fst2_.Start();
382  if (s2 == kNoStateId) return kNoStateId;
383  const auto &fs = filter_->Start();
384  const StateTuple tuple(s1, s2, fs);
385  return state_table_->FindState(tuple);
386  }
387 
388  Weight ComputeFinal(StateId s) override {
389  const auto &tuple = state_table_->Tuple(s);
390  const auto s1 = tuple.StateId1();
391  auto final1 = matcher1_->Final(s1);
392  if (final1 == Weight::Zero()) return final1;
393  const auto s2 = tuple.StateId2();
394  auto final2 = matcher2_->Final(s2);
395  if (final2 == Weight::Zero()) return final2;
396  filter_->SetState(s1, s2, tuple.GetFilterState());
397  filter_->FilterFinal(&final1, &final2);
398  return Times(final1, final2);
399  }
400 
401  // Determines which side to match on per composition state.
402  bool MatchInput(StateId s1, StateId s2) {
403  switch (match_type_) {
404  case MATCH_INPUT:
405  return true;
406  case MATCH_OUTPUT:
407  return false;
408  default: // MATCH_BOTH
409  const auto priority1 = matcher1_->Priority(s1);
410  const auto priority2 = matcher2_->Priority(s2);
411  if (priority1 == kRequirePriority && priority2 == kRequirePriority) {
412  FSTERROR() << "ComposeFst: Both sides can't require match";
413  SetProperties(kError, kError);
414  return true;
415  }
416  if (priority1 == kRequirePriority) return false;
417  if (priority2 == kRequirePriority) {
418  return true;
419  }
420  return priority1 <= priority2;
421  }
422  }
423 
424  // Identifies and verifies the capabilities of the matcher to be used for
425  // composition.
426  void SetMatchType();
427 
428  std::unique_ptr<Filter> filter_;
429  Matcher1 *matcher1_; // Borrowed reference.
430  Matcher2 *matcher2_; // Borrowed reference.
431  const FST1 &fst1_;
432  const FST2 &fst2_;
433  StateTable *state_table_;
434  bool own_state_table_;
435 
436  MatchType match_type_;
437 };
438 
439 template <class CacheStore, class Filter, class StateTable>
440 template <class M1, class M2>
442  const FST1 &fst1, const FST2 &fst2,
444  : ComposeFstImplBase<Arc, CacheStore>(opts),
445  filter_(opts.filter
446  ? opts.filter
447  : new Filter(fst1, fst2, opts.matcher1, opts.matcher2)),
448  matcher1_(filter_->GetMatcher1()),
449  matcher2_(filter_->GetMatcher2()),
450  fst1_(matcher1_->GetFst()),
451  fst2_(matcher2_->GetFst()),
452  state_table_(opts.state_table ? opts.state_table
453  : new StateTable(fst1_, fst2_)),
454  own_state_table_(opts.state_table ? opts.own_state_table : true) {
455  SetType("compose");
456  if (!CompatSymbols(fst2.InputSymbols(), fst1.OutputSymbols())) {
457  FSTERROR() << "ComposeFst: Output symbol table of 1st argument "
458  << "does not match input symbol table of 2nd argument";
460  }
461  SetInputSymbols(fst1_.InputSymbols());
462  SetOutputSymbols(fst2_.OutputSymbols());
463  SetMatchType();
464  VLOG(2) << "ComposeFstImpl: Match type: " << match_type_;
465  if (match_type_ == MATCH_NONE) SetProperties(kError, kError);
466  const auto fprops1 = fst1.Properties(kFstProperties, false);
467  const auto fprops2 = fst2.Properties(kFstProperties, false);
468  const auto mprops1 = matcher1_->Properties(fprops1);
469  const auto mprops2 = matcher2_->Properties(fprops2);
470  const auto cprops = ComposeProperties(mprops1, mprops2);
471  SetProperties(filter_->Properties(cprops), kCopyProperties);
472  if (state_table_->Error()) SetProperties(kError, kError);
473 }
474 
475 template <class CacheStore, class Filter, class StateTable>
477  // Ensures any required matching is possible and known.
478  if ((matcher1_->Flags() & kRequireMatch) &&
479  matcher1_->Type(true) != MATCH_OUTPUT) {
480  FSTERROR() << "ComposeFst: 1st argument cannot perform required matching "
481  << "(sort?).";
482  match_type_ = MATCH_NONE;
483  return;
484  }
485  if ((matcher2_->Flags() & kRequireMatch) &&
486  matcher2_->Type(true) != MATCH_INPUT) {
487  FSTERROR() << "ComposeFst: 2nd argument cannot perform required matching "
488  << "(sort?).";
489  match_type_ = MATCH_NONE;
490  return;
491  }
492  // Finds which sides to match on (favoring minimal testing of capabilities).
493  const auto type1 = matcher1_->Type(false);
494  const auto type2 = matcher2_->Type(false);
495  if (type1 == MATCH_OUTPUT && type2 == MATCH_INPUT) {
496  match_type_ = MATCH_BOTH;
497  } else if (type1 == MATCH_OUTPUT) {
498  match_type_ = MATCH_OUTPUT;
499  } else if (type2 == MATCH_INPUT) {
500  match_type_ = MATCH_INPUT;
501  } else if (matcher1_->Type(true) == MATCH_OUTPUT) {
502  match_type_ = MATCH_OUTPUT;
503  } else if (matcher2_->Type(true) == MATCH_INPUT) {
504  match_type_ = MATCH_INPUT;
505  } else {
506  FSTERROR() << "ComposeFst: 1st argument cannot match on output labels "
507  << "and 2nd argument cannot match on input labels (sort?).";
508  match_type_ = MATCH_NONE;
509  }
510 }
511 
512 } // namespace internal
513 
514 // Computes the composition of two transducers. This version is a delayed FST.
515 // If FST1 transduces string x to y with weight a and FST2 transduces y to z
516 // with weight b, then their composition transduces string x to z with weight
517 // Times(x, z).
518 //
519 // The output labels of the first transducer or the input labels of the second
520 // transducer must be sorted (with the default matcher). The weights need to
521 // form a commutative semiring (valid for TropicalWeight and LogWeight).
522 //
523 // Complexity:
524 //
525 // Assuming the first FST is unsorted and the second is sorted,
526 //
527 // Time: O(v1 v2 d1 (log d2 + m2)),
528 // Space: O(v1 v2)
529 //
530 // where vi = # of states visited, di = maximum out-degree, and mi the
531 // maximum multiplicity of the states visited, for the ith FST. Constant time
532 // and space to visit an input state or arc is assumed and exclusive of caching.
533 //
534 // Caveats:
535 // - ComposeFst does not trim its output (since it is a delayed operation).
536 // - The efficiency of composition can be strongly affected by several factors:
537 // - the choice of which transducer is sorted - prefer sorting the FST
538 // that has the greater average out-degree.
539 // - the amount of non-determinism
540 // - the presence and location of epsilon transitions - avoid epsilon
541 // transitions on the output side of the first transducer or
542 // the input side of the second transducer or prefer placing
543 // them later in a path since they delay matching and can
544 // introduce non-coaccessible states and transitions.
545 //
546 // This class attaches interface to implementation and handles reference
547 // counting, delegating most methods to ImplToFst. The CacheStore specifies the
548 // cache store (default declared in fst-decl.h).
549 template <class A, class CacheStore /* = DefaultCacheStore<A> */>
551  : public ImplToFst<internal::ComposeFstImplBase<A, CacheStore>> {
552  public:
553  using Arc = A;
554  using StateId = typename Arc::StateId;
555  using Weight = typename Arc::Weight;
556 
557  using Store = CacheStore;
558  using State = typename CacheStore::State;
559 
561 
562  friend class ArcIterator<ComposeFst<Arc, CacheStore>>;
563  friend class StateIterator<ComposeFst<Arc, CacheStore>>;
564  template <class, class, class> friend class ComposeFstMatcher;
565 
566  // Compose specifying only caching options.
567  ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
568  const CacheOptions &opts = CacheOptions())
569  : ImplToFst<Impl>(CreateBase(fst1, fst2, opts)) {}
570 
571  // Compose specifying one shared matcher type M. Requires that the input FSTs
572  // and matcher FST types be Fst<Arc>. Recommended for best code-sharing and
573  // matcher compatiblity.
574  template <class Matcher, class Filter, class StateTuple>
575  ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
577  : ImplToFst<Impl>(CreateBase1(fst1, fst2, opts)) {}
578 
579  // Compose specifying two matcher types Matcher1 and Matcher2. Requires input
580  // FST (of the same Arc type, but o.w. arbitrary) match the corresponding
581  // matcher FST types). Recommended only for advanced use in demanding or
582  // specialized applications due to potential code bloat and matcher
583  // incompatibilities.
584  template <class Matcher1, class Matcher2, class Filter, class StateTuple>
585  ComposeFst(const typename Matcher1::FST &fst1,
586  const typename Matcher2::FST &fst2,
588  CacheStore> &opts)
589  : ImplToFst<Impl>(CreateBase2(fst1, fst2, opts)) {}
590 
591  // See Fst<>::Copy() for doc.
592  ComposeFst(const ComposeFst<A, CacheStore> &fst, bool safe = false)
593  : ImplToFst<Impl>(safe ? std::shared_ptr<Impl>(fst.GetImpl()->Copy())
594  : fst.GetSharedImpl()) {}
595 
596  // Get a copy of this ComposeFst. See Fst<>::Copy() for further doc.
597  ComposeFst<A, CacheStore> *Copy(bool safe = false) const override {
598  return new ComposeFst<A, CacheStore>(*this, safe);
599  }
600 
601  inline void InitStateIterator(StateIteratorData<Arc> *data) const override;
602 
603  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
604  GetMutableImpl()->InitArcIterator(s, data);
605  }
606 
607  MatcherBase<Arc> *InitMatcher(MatchType match_type) const override {
608  return GetImpl()->InitMatcher(*this, match_type);
609  }
610 
611  protected:
614 
615  explicit ComposeFst(std::shared_ptr<Impl> impl) : ImplToFst<Impl>(impl) {}
616 
617  // Create compose implementation specifying two matcher types.
618  template <class Matcher1, class Matcher2, class Filter, class StateTuple>
619  static std::shared_ptr<Impl> CreateBase2(
620  const typename Matcher1::FST &fst1, const typename Matcher2::FST &fst2,
622  CacheStore> &opts) {
623  auto impl = std::make_shared<
625  opts);
626  if (!(Weight::Properties() & kCommutative) && !opts.allow_noncommute) {
627  const auto props1 = fst1.Properties(kUnweighted, true);
628  const auto props2 = fst2.Properties(kUnweighted, true);
629  if (!(props1 & kUnweighted) && !(props2 & kUnweighted)) {
630  FSTERROR() << "ComposeFst: Weights must be a commutative semiring: "
631  << Weight::Type();
632  impl->SetProperties(kError, kError);
633  }
634  }
635  return impl;
636  }
637 
638  // Create compose implementation specifying one matcher type; requires that
639  // input and matcher FST types be Fst<Arc>.
640  template <class Matcher, class Filter, class StateTuple>
641  static std::shared_ptr<Impl> CreateBase1(
642  const Fst<Arc> &fst1, const Fst<Arc> &fst2,
645  nopts(opts, opts.matcher1, opts.matcher2, opts.filter,
646  opts.state_table);
647  return CreateBase2(fst1, fst2, nopts);
648  }
649 
650  // Create compose implementation specifying no matcher type.
651  static std::shared_ptr<Impl> CreateBase(const Fst<Arc> &fst1,
652  const Fst<Arc> &fst2,
653  const CacheOptions &opts) {
654  switch (LookAheadMatchType(fst1, fst2)) { // Check for lookahead matchers
655  default:
656  case MATCH_NONE: { // Default composition (no look-ahead).
657  ComposeFstOptions<Arc> nopts(opts);
658  return CreateBase1(fst1, fst2, nopts);
659  }
660  case MATCH_OUTPUT: { // Lookahead on fst1.
663  ComposeFstOptions<Arc, M, F> nopts(opts);
664  return CreateBase1(fst1, fst2, nopts);
665  }
666  case MATCH_INPUT: { // Lookahead on fst2
669  ComposeFstOptions<Arc, M, F> nopts(opts);
670  return CreateBase1(fst1, fst2, nopts);
671  }
672  }
673  }
674 
675  private:
676  ComposeFst &operator=(const ComposeFst &fst) = delete;
677 };
678 
679 // Specialization for ComposeFst.
680 template <class Arc, class CacheStore>
681 class StateIterator<ComposeFst<Arc, CacheStore>>
682  : public CacheStateIterator<ComposeFst<Arc, CacheStore>> {
683  public:
685  : CacheStateIterator<ComposeFst<Arc, CacheStore>>(fst,
686  fst.GetMutableImpl()) {}
687 };
688 
689 // Specialization for ComposeFst.
690 template <class Arc, class CacheStore>
691 class ArcIterator<ComposeFst<Arc, CacheStore>>
692  : public CacheArcIterator<ComposeFst<Arc, CacheStore>> {
693  public:
694  using StateId = typename Arc::StateId;
695 
697  : CacheArcIterator<ComposeFst<Arc, CacheStore>>(fst.GetMutableImpl(), s) {
698  if (!fst.GetImpl()->HasArcs(s)) fst.GetMutableImpl()->Expand(s);
699  }
700 };
701 
702 template <class Arc, class CacheStore>
704  StateIteratorData<Arc> *data) const {
706 }
707 
708 // Specialized matcher for ComposeFst. Supports MATCH_INPUT or MATCH_OUTPUT,
709 // iff the underlying matchers for the two FSTS being composed support
710 // MATCH_INPUT or MATCH_OUTPUT, respectively.
711 template <class CacheStore, class Filter, class StateTable>
712 class ComposeFstMatcher : public MatcherBase<typename CacheStore::Arc> {
713  public:
714  using Arc = typename CacheStore::Arc;
715  using Label = typename Arc::Label;
716  using StateId = typename Arc::StateId;
717  using Weight = typename Arc::Weight;
718 
719  using Matcher1 = typename Filter::Matcher1;
720  using Matcher2 = typename Filter::Matcher2;
721  using FilterState = typename Filter::FilterState;
722 
723  using StateTuple = typename StateTable::StateTuple;
725 
726  // The compose FST arg must match the filter and state table types.
727  // This makes a copy of the FST.
729  MatchType match_type)
730  : owned_fst_(fst.Copy()),
731  fst_(*owned_fst_),
732  impl_(static_cast<const Impl *>(fst_.GetImpl())),
733  s_(kNoStateId),
734  match_type_(match_type),
735  matcher1_(impl_->matcher1_->Copy()),
736  matcher2_(impl_->matcher2_->Copy()),
737  current_loop_(false),
738  loop_(kNoLabel, 0, Weight::One(), kNoStateId) {
739  if (match_type_ == MATCH_OUTPUT) std::swap(loop_.ilabel, loop_.olabel);
740  }
741 
742  // The compose FST arg must match the filter and state table types.
743  // This doesn't copy the FST (although it may copy components).
745  MatchType match_type)
746  : fst_(*fst),
747  impl_(static_cast<const Impl *>(fst_.GetImpl())),
748  s_(kNoStateId),
749  match_type_(match_type),
750  matcher1_(impl_->matcher1_->Copy()),
751  matcher2_(impl_->matcher2_->Copy()),
752  current_loop_(false),
753  loop_(kNoLabel, 0, Weight::One(), kNoStateId) {
754  if (match_type_ == MATCH_OUTPUT) std::swap(loop_.ilabel, loop_.olabel);
755  }
756 
757  // This makes a copy of the FST.
760  bool safe = false)
761  : owned_fst_(matcher.fst_.Copy(safe)),
762  fst_(*owned_fst_),
763  impl_(static_cast<const Impl *>(fst_.GetImpl())),
764  s_(kNoStateId),
765  match_type_(matcher.match_type_),
766  matcher1_(matcher.matcher1_->Copy(safe)),
767  matcher2_(matcher.matcher2_->Copy(safe)),
768  current_loop_(false),
769  loop_(kNoLabel, 0, Weight::One(), kNoStateId) {
770  if (match_type_ == MATCH_OUTPUT) std::swap(loop_.ilabel, loop_.olabel);
771  }
772 
774  bool safe = false) const override {
776  }
777 
778  MatchType Type(bool test) const override {
779  if ((matcher1_->Type(test) == MATCH_NONE) ||
780  (matcher2_->Type(test) == MATCH_NONE)) {
781  return MATCH_NONE;
782  }
783  if (((matcher1_->Type(test) == MATCH_UNKNOWN) &&
784  (matcher2_->Type(test) == MATCH_UNKNOWN)) ||
785  ((matcher1_->Type(test) == MATCH_UNKNOWN) &&
786  (matcher2_->Type(test) == match_type_)) ||
787  ((matcher1_->Type(test) == match_type_) &&
788  (matcher2_->Type(test) == MATCH_UNKNOWN))) {
789  return MATCH_UNKNOWN;
790  }
791  if ((matcher1_->Type(test) == match_type_) &&
792  (matcher2_->Type(test) == match_type_)) {
793  return match_type_;
794  }
795  return MATCH_NONE;
796  }
797 
798  const Fst<Arc> &GetFst() const override { return fst_; }
799 
800  uint64 Properties(uint64 inprops) const override {
801  return inprops;
802  }
803 
804  void SetState(StateId s) final {
805  if (s_ == s) return;
806  s_ = s;
807  const auto &tuple = impl_->state_table_->Tuple(s);
808  matcher1_->SetState(tuple.StateId1());
809  matcher2_->SetState(tuple.StateId2());
810  loop_.nextstate = s_;
811  }
812 
813  bool Find(Label label) final {
814  bool found = false;
815  current_loop_ = false;
816  if (label == 0) {
817  current_loop_ = true;
818  found = true;
819  }
820  if (match_type_ == MATCH_INPUT) {
821  found = found || FindLabel(label, matcher1_.get(), matcher2_.get());
822  } else { // match_type_ == MATCH_OUTPUT
823  found = found || FindLabel(label, matcher2_.get(), matcher1_.get());
824  }
825  return found;
826  }
827 
828  bool Done() const final {
829  return !current_loop_ && matcher1_->Done() && matcher2_->Done();
830  }
831 
832  const Arc &Value() const final { return current_loop_ ? loop_ : arc_; }
833 
834  void Next() final {
835  if (current_loop_) {
836  current_loop_ = false;
837  } else if (match_type_ == MATCH_INPUT) {
838  FindNext(matcher1_.get(), matcher2_.get());
839  } else { // match_type_ == MATCH_OUTPUT
840  FindNext(matcher2_.get(), matcher1_.get());
841  }
842  }
843 
844  ssize_t Priority(StateId s) final { return fst_.NumArcs(s); }
845 
846  private:
847  // Processes a match with the filter and creates resulting arc.
848  bool MatchArc(StateId s, Arc arc1,
849  Arc arc2) { // FIXME(kbg): copy but not assignment.
850  const auto &fs = impl_->filter_->FilterArc(&arc1, &arc2);
851  if (fs == FilterState::NoState()) return false;
852  const StateTuple tuple(arc1.nextstate, arc2.nextstate, fs);
853  arc_.ilabel = arc1.ilabel;
854  arc_.olabel = arc2.olabel;
855  arc_.weight = Times(arc1.weight, arc2.weight);
856  arc_.nextstate = impl_->state_table_->FindState(tuple);
857  return true;
858  }
859 
860  // Finds the first match allowed by the filter.
861  template <class MatcherA, class MatcherB>
862  bool FindLabel(Label label, MatcherA *matchera, MatcherB *matcherb) {
863  if (matchera->Find(label)) {
864  matcherb->Find(match_type_ == MATCH_INPUT ? matchera->Value().olabel
865  : matchera->Value().ilabel);
866  return FindNext(matchera, matcherb);
867  }
868  return false;
869  }
870 
871  // Finds the next match allowed by the filter, returning true iff such a
872  // match is found.
873  template <class MatcherA, class MatcherB>
874  bool FindNext(MatcherA *matchera, MatcherB *matcherb) {
875  // State when entering this function:
876  // 'matchera' is pointed to a match x, y for label x, and a match for y was
877  // requested on 'matcherb'.
878  while (!matchera->Done() || !matcherb->Done()) {
879  if (matcherb->Done()) {
880  // If no more matches for y on 'matcherb', moves forward on 'matchera'
881  // until a match x, y' is found such that there is a match for y' on
882  // 'matcherb'.
883  matchera->Next();
884  while (!matchera->Done() &&
885  !matcherb->Find(match_type_ == MATCH_INPUT
886  ? matchera->Value().olabel
887  : matchera->Value().ilabel)) {
888  matchera->Next();
889  }
890  }
891  while (!matcherb->Done()) {
892  // 'matchera' is pointing to a match x, y' ('arca') and 'matcherb' is
893  // pointing to a match y', z' ('arcb'). If combining these two arcs is
894  // allowed by the filter (hence resulting in an arc x, z') return true.
895  // Position 'matcherb' on the next potential match for y' before
896  // returning.
897  const auto &arca = matchera->Value();
898  const auto &arcb = matcherb->Value();
899  // Position 'matcherb' on the next potential match for y'.
900  matcherb->Next();
901  // Returns true If combining these two arcs is allowed by the filter
902  // (hence resulting in an arc x, z'); otherwise consider next match
903  // for y' on 'matcherb'.
904  if (MatchArc(s_, match_type_ == MATCH_INPUT ? arca : arcb,
905  match_type_ == MATCH_INPUT ? arcb : arca)) {
906  return true;
907  }
908  }
909  }
910  // Both 'matchera' and 'matcherb' are done, no more match to analyse.
911  return false;
912  }
913 
914  std::unique_ptr<const ComposeFst<Arc, CacheStore>> owned_fst_;
915  const ComposeFst<Arc, CacheStore> &fst_;
916  const Impl *impl_;
917  StateId s_;
918  MatchType match_type_;
919  std::unique_ptr<Matcher1> matcher1_;
920  std::unique_ptr<Matcher2> matcher2_;
921  bool current_loop_;
922  Arc loop_;
923  Arc arc_;
924 };
925 
926 // Useful alias when using StdArc.
928 
937 };
938 
940  bool connect; // Connect output?
941  ComposeFilter filter_type; // Pre-defined filter to use.
942 
943  explicit ComposeOptions(bool connect = true,
944  ComposeFilter filter_type = AUTO_FILTER)
945  : connect(connect), filter_type(filter_type) {}
946 };
947 
948 // Computes the composition of two transducers. This version writes
949 // the composed FST into a MutableFst. If FST1 transduces string x to
950 // y with weight a and FST2 transduces y to z with weight b, then
951 // their composition transduces string x to z with weight
952 // Times(x, z).
953 //
954 // The output labels of the first transducer or the input labels of
955 // the second transducer must be sorted. The weights need to form a
956 // commutative semiring (valid for TropicalWeight and LogWeight).
957 //
958 // Complexity:
959 //
960 // Assuming the first FST is unsorted and the second is sorted:
961 //
962 // Time: O(V1 V2 D1 (log D2 + M2)),
963 // Space: O(V1 V2 D1 M2)
964 //
965 // where Vi = # of states, Di = maximum out-degree, and Mi is the maximum
966 // multiplicity, for the ith FST.
967 //
968 // Caveats:
969 //
970 // - Compose trims its output.
971 // - The efficiency of composition can be strongly affected by several factors:
972 // - the choice of which transducer is sorted - prefer sorting the FST
973 // that has the greater average out-degree.
974 // - the amount of non-determinism
975 // - the presence and location of epsilon transitions - avoid epsilon
976 // transitions on the output side of the first transducer or
977 // the input side of the second transducer or prefer placing
978 // them later in a path since they delay matching and can
979 // introduce non-coaccessible states and transitions.
980 template <class Arc>
981 void Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
982  MutableFst<Arc> *ofst,
983  const ComposeOptions &opts = ComposeOptions()) {
984  using M = Matcher<Fst<Arc>>;
985  // In each case, we cache only the last state for fastest copy.
986  switch (opts.filter_type) {
987  case AUTO_FILTER: {
988  CacheOptions nopts;
989  nopts.gc_limit = 0;
990  *ofst = ComposeFst<Arc>(ifst1, ifst2, nopts);
991  break;
992  }
993  case NULL_FILTER: {
995  copts.gc_limit = 0;
996  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
997  break;
998  }
999  case SEQUENCE_FILTER: {
1001  copts.gc_limit = 0;
1002  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
1003  break;
1004  }
1005  case ALT_SEQUENCE_FILTER: {
1007  copts.gc_limit = 0;
1008  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
1009  break;
1010  }
1011  case MATCH_FILTER: {
1013  copts.gc_limit = 0;
1014  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
1015  break;
1016  }
1017  case NO_MATCH_FILTER: {
1019  copts.gc_limit = 0;
1020  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
1021  break;
1022  }
1023  case TRIVIAL_FILTER: {
1025  copts.gc_limit = 0;
1026  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
1027  break;
1028  }
1029  }
1030  if (opts.connect) Connect(ofst);
1031 }
1032 
1033 } // namespace fst
1034 
1035 #endif // FST_COMPOSE_H_
typename Impl::Arc Arc
Definition: fst.h:871
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:99
typename Filter::Matcher1 Matcher1
Definition: compose.h:215
ssize_t Priority(StateId s) final
Definition: compose.h:844
ComposeFst< A, CacheStore > * Copy(bool safe=false) const override
Definition: compose.h:597
uint64 Properties(uint64 inprops) const override
Definition: compose.h:800
ComposeFst(const typename Matcher1::FST &fst1, const typename Matcher2::FST &fst2, const ComposeFstImplOptions< Matcher1, Matcher2, Filter, StateTuple, CacheStore > &opts)
Definition: compose.h:585
typename Filter::Matcher2 Matcher2
Definition: compose.h:216
const StateTable * GetStateTable() const
Definition: compose.h:307
size_t NumArcs(StateId s)
Definition: compose.h:177
constexpr uint32 kRequireMatch
Definition: matcher.h:104
constexpr ssize_t kRequirePriority
Definition: matcher.h:110
void Expand(StateId s) override
Definition: compose.h:279
constexpr int kNoLabel
Definition: fst.h:179
typename Filter::Matcher2 Matcher2
Definition: compose.h:720
uint64_t uint64
Definition: types.h:32
typename StateTable::StateTuple StateTuple
Definition: compose.h:723
static std::shared_ptr< Impl > CreateBase1(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const ComposeFstOptions< Arc, Matcher, Filter, StateTuple > &opts)
Definition: compose.h:641
uint64 ComposeProperties(uint64 inprops1, uint64 inprops2)
Definition: properties.cc:55
typename StateTable::StateTuple StateTuple
Definition: compose.h:231
typename Filter::Matcher1 Matcher1
Definition: compose.h:719
typename Arc::Label Label
Definition: compose.h:715
ComposeFstImplOptions(const CacheImplOptions< CacheStore > &opts, M1 *matcher1=nullptr, M2 *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: compose.h:96
bool Done() const final
Definition: compose.h:828
size_t NumOutputEpsilons(StateId s)
Definition: compose.h:187
ComposeFilter filter_type
Definition: compose.h:941
MatchType LookAheadMatchType(const Matcher1 &m1, const Matcher2 &m2)
ComposeOptions(bool connect=true, ComposeFilter filter_type=AUTO_FILTER)
Definition: compose.h:943
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:82
const SymbolTable * OutputSymbols() const
Definition: fst.h:690
MatchType
Definition: fst.h:171
ComposeFstMatcher(const ComposeFst< Arc, CacheStore > *fst, MatchType match_type)
Definition: compose.h:744
ComposeFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts=CacheOptions())
Definition: compose.h:567
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
static std::shared_ptr< Impl > CreateBase(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const CacheOptions &opts)
Definition: compose.h:651
void SetOutputSymbols(const SymbolTable *osyms)
Definition: fst.h:700
SetType
Definition: set-weight.h:37
typename Matcher2::FST FST2
Definition: compose.h:219
typename ComposeFst< Arc, CacheStore >::Arc Arc
Definition: cache.h:1148
constexpr uint64 kCommutative
Definition: weight.h:120
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
ssize_t NumArcs(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:88
typename CacheStore::State State
Definition: compose.h:227
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data)
Definition: compose.h:192
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: compose.h:603
MatcherBase< Arc > * InitMatcher(const ComposeFst< Arc, CacheStore > &fst, MatchType match_type) const override
Definition: compose.h:311
StateTable * state_table
Definition: compose.h:80
constexpr uint64 kFstProperties
Definition: properties.h:301
const Matcher1 * GetMatcher1() const
Definition: compose.h:295
constexpr uint64 kCopyProperties
Definition: properties.h:138
virtual uint64 Properties() const
Definition: fst.h:666
constexpr int kNoStateId
Definition: fst.h:180
ComposeFstMatcher(const ComposeFst< Arc, CacheStore > &fst, MatchType match_type)
Definition: compose.h:728
void SetType(const string &type)
Definition: fst.h:664
ComposeFstMatcher< CacheStore, Filter, StateTable > * Copy(bool safe=false) const override
Definition: compose.h:773
#define FSTERROR()
Definition: util.h:35
constexpr uint64 kUnweighted
Definition: properties.h:87
typename Arc::Weight Weight
Definition: fst.h:873
StateTable * GetStateTable()
Definition: compose.h:309
StateIteratorBase< Arc > * base
Definition: fst.h:351
typename Arc::Weight Weight
Definition: compose.h:224
CacheOptions(bool gc=FLAGS_fst_default_cache_gc, size_t gc_limit=FLAGS_fst_default_cache_gc_limit)
Definition: cache.h:31
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:93
MatchType Type(bool test) const override
Definition: compose.h:778
typename CacheStore::Arc Arc
Definition: compose.h:221
bool Done() const
Definition: matcher.h:1550
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: compose.h:703
const Filter * GetFilter() const
Definition: compose.h:303
void Compose(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
Definition: compose.h:981
ComposeFstImplBase(const CacheOptions &opts)
Definition: compose.h:149
typename Arc::StateId StateId
Definition: compose.h:223
ComposeFst(std::shared_ptr< Impl > impl)
Definition: compose.h:615
size_t NumInputEpsilons(StateId s)
Definition: compose.h:182
#define VLOG(level)
Definition: log.h:49
const string & Type() const
Definition: fst.h:662
bool Done() const
Definition: fst.h:499
void Next()
Definition: matcher.h:1554
const FST1 & GetFst1() const
Definition: compose.h:291
typename Arc::StateId StateId
Definition: compose.h:716
bool Find(Label label)
Definition: matcher.h:1548
ComposeFstMatcher(const ComposeFstMatcher< CacheStore, Filter, StateTable > &matcher, bool safe=false)
Definition: compose.h:758
ComposeFstImpl * Copy() const override
Definition: compose.h:260
const FST2 & GetFst2() const
Definition: compose.h:293
ComposeFstImpl(const ComposeFstImpl &impl)
Definition: compose.h:245
const Matcher2 * GetMatcher2() const
Definition: compose.h:299
static std::shared_ptr< Impl > CreateBase2(const typename Matcher1::FST &fst1, const typename Matcher2::FST &fst2, const ComposeFstImplOptions< Matcher1, Matcher2, Filter, StateTuple, CacheStore > &opts)
Definition: compose.h:619
void SetInputSymbols(const SymbolTable *isyms)
Definition: fst.h:696
typename CacheStore::Arc Arc
Definition: compose.h:714
virtual MatcherBase< Arc > * InitMatcher(const F &fst, MatchType match_type) const
Definition: compose.h:197
constexpr uint64 kOLabelInvariantProperties
Definition: properties.h:245
MatcherBase< Arc > * InitMatcher(MatchType match_type) const override
Definition: compose.h:607
typename Filter::FilterState FilterState
Definition: compose.h:226
ComposeFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const ComposeFstOptions< Arc, Matcher, Filter, StateTuple > &opts)
Definition: compose.h:575
void SetState(StateId s) final
Definition: compose.h:804
typename Matcher1::FST FST1
Definition: compose.h:218
typename Arc::StateId StateId
Definition: fst.h:872
void SetState(StateId s)
Definition: matcher.h:1546
ComposeFstOptions(const CacheOptions &opts=CacheOptions(), M *matcher1=nullptr, M *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: compose.h:45
const Arc & Value() const final
Definition: compose.h:832
const Fst< Arc > & GetFst() const override
Definition: compose.h:798
uint64 Properties() const override
Definition: compose.h:262
typename Arc::Weight Weight
Definition: compose.h:717
typename ComposeFst< Arc, CacheStore >::Arc Arc
Definition: cache.h:1194
const SymbolTable * InputSymbols() const
Definition: fst.h:688
ComposeFstImplBase(const CacheImplOptions< CacheStore > &opts)
Definition: compose.h:146
typename Filter::FilterState FilterState
Definition: compose.h:721
constexpr uint64 kError
Definition: properties.h:33
uint64 Properties(uint64 mask) const override
Definition: compose.h:265
ArcIterator(const ComposeFst< Arc, CacheStore > &fst, StateId s)
Definition: compose.h:696
ComposeFstImplBase(const ComposeFstImplBase &impl)
Definition: compose.h:151
typename CacheStore::State State
Definition: compose.h:558
void Next() final
Definition: compose.h:834
bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
void Expand(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, const std::vector< typename Arc::Label > &assignments, MutableFst< Arc > *ofst, const MPdtExpandOptions &opts)
Definition: expand.h:302
const Arc & Value() const
Definition: matcher.h:1552
Impl * GetMutableImpl() const
Definition: fst.h:947
ComposeFst(const ComposeFst< A, CacheStore > &fst, bool safe=false)
Definition: compose.h:592
typename Arc::Label Label
Definition: compose.h:222
constexpr uint64 kILabelInvariantProperties
Definition: properties.h:236
ComposeFilter
Definition: compose.h:929
size_t gc_limit
Definition: cache.h:29
StateIterator(const ComposeFst< Arc, CacheStore > &fst)
Definition: compose.h:684
bool Find(Label label) final
Definition: compose.h:813
const Impl * GetImpl() const
Definition: fst.h:945
ComposeFstImplOptions(const CacheOptions &opts, M1 *matcher1=nullptr, M2 *matcher2=nullptr, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: compose.h:84
StateTable * state_table
Definition: compose.h:43