1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
4 // Classes to allow matching labels leaving FST states.
10 #include <unordered_map>
15 #include <fst/mutable-fst.h> // for all internal FST accessors.
20 // Matchers find and iterate through requested labels at FST states. In the
21 // simplest form, these are just some associative map or search keyed on labels.
22 // More generally, they may implement matching special labels that represent
23 // sets of labels such as sigma (all), rho (rest), or phi (fail). The Matcher
30 // using Arc = typename FST::Arc;
31 // using Label = typename Arc::Label;
32 // using StateId = typename Arc::StateId;
33 // using Weight = typename Arc::Weight;
35 // // Required constructors.
37 // Matcher(const FST &fst, MatchType type);
38 // Matcher(const Matcher &matcher, bool safe = false);
40 // // Standard copy method.
41 // Matcher<FST> *Copy(bool safe = false) const override;
43 // // Returns the match type that can be provided (depending on compatibility
44 // of the input FST). It is either the requested match type, MATCH_NONE, or
45 // MATCH_UNKNOWN. If test is false, a costly testing is avoided, but
46 // MATCH_UNKNOWN may be returned. If test is true, a definite answer is
47 // returned, but may involve more costly computation (e.g., visiting the FST).
48 // MatchType Type(bool test) const override;
50 // // Specifies the current state.
51 // void SetState(StateId s) final;
53 // // Finds matches to a label at the current state, returning true if a match
54 // // found. kNoLabel matches any non-consuming transitions, e.g., epsilon
55 // // transitions, which do not require a matching symbol.
56 // bool Find(Label label) final;
58 // // Iterator methods. Note that initially and after SetState() these have
59 // undefined behavior until Find() is called.
61 // bool Done() const final;
63 // const Arc &Value() const final;
67 // // Returns final weight of a state.
68 // Weight Final(StateId) const final;
70 // // Indicates preference for being the side used for matching in
71 // // composition. If the value is kRequirePriority, then it is
72 // // mandatory that it be used. Calling this method without passing the
73 // // current state of the matcher invalidates the state of the matcher.
74 // ssize_t Priority(StateId s) final;
76 // // This specifies the known FST properties as viewed from this matcher. It
77 // // takes as argument the input FST's known properties.
78 // uint64 Properties(uint64 props) const override;
80 // // Returns matcher flags.
81 // uint32 Flags() const override;
83 // // Returns matcher FST.
84 // const FST &GetFst() const override;
87 // Basic matcher flags.
89 // Matcher needs to be used as the matching side in composition for
90 // at least one state (has kRequirePriority).
91 constexpr uint32 kRequireMatch = 0x00000001;
93 // Flags used for basic matchers (see also lookahead.h).
94 constexpr uint32 kMatcherFlags = kRequireMatch;
96 // Matcher priority that is mandatory.
97 constexpr ssize_t kRequirePriority = -1;
99 // Matcher interface, templated on the Arc definition; used for matcher
100 // specializations that are returned by the InitMatcher FST method.
105 using Label = typename Arc::Label;
106 using StateId = typename Arc::StateId;
107 using Weight = typename Arc::Weight;
109 virtual ~MatcherBase() {}
111 // Virtual interface.
113 virtual MatcherBase<Arc> *Copy(bool safe = false) const = 0;
114 virtual MatchType Type(bool) const = 0;
115 virtual void SetState(StateId) = 0;
116 virtual bool Find(Label) = 0;
117 virtual bool Done() const = 0;
118 virtual const Arc &Value() const = 0;
119 virtual void Next() = 0;
120 virtual const Fst<Arc> &GetFst() const = 0;
121 virtual uint64 Properties(uint64) const = 0;
123 // Trivial implementations that can be used by derived classes. Full
124 // devirtualization is expected for any derived class marked final.
125 virtual uint32 Flags() const { return 0; }
127 virtual Weight Final(StateId s) const { return internal::Final(GetFst(), s); }
129 virtual ssize_t Priority(StateId s) { return internal::NumArcs(GetFst(), s); }
132 // A matcher that expects sorted labels on the side to be matched.
133 // If match_type == MATCH_INPUT, epsilons match the implicit self-loop
134 // Arc(kNoLabel, 0, Weight::One(), current_state) as well as any
135 // actual epsilon transitions. If match_type == MATCH_OUTPUT, then
136 // Arc(0, kNoLabel, Weight::One(), current_state) is instead matched.
138 class SortedMatcher : public MatcherBase<typename F::Arc> {
141 using Arc = typename FST::Arc;
142 using Label = typename Arc::Label;
143 using StateId = typename Arc::StateId;
144 using Weight = typename Arc::Weight;
146 using MatcherBase<Arc>::Flags;
147 using MatcherBase<Arc>::Properties;
149 // Labels >= binary_label will be searched for by binary search;
150 // o.w. linear search is used.
151 SortedMatcher(const FST &fst, MatchType match_type, Label binary_label = 1)
155 match_type_(match_type),
156 binary_label_(binary_label),
157 match_label_(kNoLabel),
159 loop_(kNoLabel, 0, Weight::One(), kNoStateId),
162 switch (match_type_) {
167 std::swap(loop_.ilabel, loop_.olabel);
170 FSTERROR() << "SortedMatcher: Bad match type";
171 match_type_ = MATCH_NONE;
176 SortedMatcher(const SortedMatcher<FST> &matcher, bool safe = false)
177 : fst_(matcher.fst_->Copy(safe)),
180 match_type_(matcher.match_type_),
181 binary_label_(matcher.binary_label_),
182 match_label_(kNoLabel),
184 loop_(matcher.loop_),
185 error_(matcher.error_),
188 ~SortedMatcher() override { Destroy(aiter_, &aiter_pool_); }
190 SortedMatcher<FST> *Copy(bool safe = false) const override {
191 return new SortedMatcher<FST>(*this, safe);
194 MatchType Type(bool test) const override {
195 if (match_type_ == MATCH_NONE) return match_type_;
196 const auto true_prop =
197 match_type_ == MATCH_INPUT ? kILabelSorted : kOLabelSorted;
198 const auto false_prop =
199 match_type_ == MATCH_INPUT ? kNotILabelSorted : kNotOLabelSorted;
200 const auto props = fst_->Properties(true_prop | false_prop, test);
201 if (props & true_prop) {
203 } else if (props & false_prop) {
206 return MATCH_UNKNOWN;
210 void SetState(StateId s) final {
211 if (state_ == s) return;
213 if (match_type_ == MATCH_NONE) {
214 FSTERROR() << "SortedMatcher: Bad match type";
217 Destroy(aiter_, &aiter_pool_);
218 aiter_ = new (&aiter_pool_) ArcIterator<FST>(*fst_, s);
219 aiter_->SetFlags(kArcNoCache, kArcNoCache);
220 narcs_ = internal::NumArcs(*fst_, s);
224 bool Find(Label match_label) final {
227 current_loop_ = false;
228 match_label_ = kNoLabel;
231 current_loop_ = match_label == 0;
232 match_label_ = match_label == kNoLabel ? 0 : match_label;
236 return current_loop_;
240 // Positions matcher to the first position where inserting match_label would
241 // maintain the sort order.
242 void LowerBound(Label label) {
243 exact_match_ = false;
244 current_loop_ = false;
246 match_label_ = kNoLabel;
249 match_label_ = label;
253 // After Find(), returns false if no more exact matches.
254 // After LowerBound(), returns false if no more arcs.
255 bool Done() const final {
256 if (current_loop_) return false;
257 if (aiter_->Done()) return true;
258 if (!exact_match_) return false;
260 match_type_ == MATCH_INPUT ? kArcILabelValue : kArcOLabelValue,
262 const auto label = match_type_ == MATCH_INPUT ? aiter_->Value().ilabel
263 : aiter_->Value().olabel;
264 return label != match_label_;
267 const Arc &Value() const final {
268 if (current_loop_) return loop_;
269 aiter_->SetFlags(kArcValueFlags, kArcValueFlags);
270 return aiter_->Value();
275 current_loop_ = false;
281 Weight Final(StateId s) const final {
282 return MatcherBase<Arc>::Final(s);
285 ssize_t Priority(StateId s) final {
286 return MatcherBase<Arc>::Priority(s);
289 const FST &GetFst() const override { return *fst_; }
291 uint64 Properties(uint64 inprops) const override {
292 return inprops | (error_ ? kError : 0);
295 size_t Position() const { return aiter_ ? aiter_->Position() : 0; }
298 Label GetLabel() const {
299 const auto &arc = aiter_->Value();
300 return match_type_ == MATCH_INPUT ? arc.ilabel : arc.olabel;
307 std::unique_ptr<const FST> fst_;
308 StateId state_; // Matcher state.
309 ArcIterator<FST> *aiter_; // Iterator for current state.
310 MatchType match_type_; // Type of match to perform.
311 Label binary_label_; // Least label for binary search.
312 Label match_label_; // Current label to be matched.
313 size_t narcs_; // Current state arc count.
314 Arc loop_; // For non-consuming symbols.
315 bool current_loop_; // Current arc is the implicit loop.
316 bool exact_match_; // Exact match or lower bound?
317 bool error_; // Error encountered?
318 MemoryPool<ArcIterator<FST>> aiter_pool_; // Pool of arc iterators.
321 // Returns true iff match to match_label_. The arc iterator is positioned at the
322 // lower bound, that is, the first element greater than or equal to
323 // match_label_, or the end if all elements are less than match_label_.
325 inline bool SortedMatcher<FST>::BinarySearch() {
327 size_t high = narcs_;
329 const size_t mid = low + (high - low) / 2;
331 if (GetLabel() < match_label_) {
339 return low < narcs_ && GetLabel() == match_label_;
342 // Returns true iff match to match_label_, positioning arc iterator at lower
345 inline bool SortedMatcher<FST>::LinearSearch() {
346 for (aiter_->Reset(); !aiter_->Done(); aiter_->Next()) {
347 const auto label = GetLabel();
348 if (label == match_label_) return true;
349 if (label > match_label_) break;
354 // Returns true iff match to match_label_, positioning arc iterator at lower
357 inline bool SortedMatcher<FST>::Search() {
358 aiter_->SetFlags(match_type_ == MATCH_INPUT ?
359 kArcILabelValue : kArcOLabelValue,
361 if (match_label_ >= binary_label_) {
362 return BinarySearch();
364 return LinearSearch();
368 // A matcher that stores labels in a per-state hash table populated upon the
369 // first visit to that state. Sorting is not required. Treatment of
370 // epsilons are the same as with SortedMatcher.
372 class HashMatcher : public MatcherBase<typename F::Arc> {
375 using Arc = typename FST::Arc;
376 using Label = typename Arc::Label;
377 using StateId = typename Arc::StateId;
378 using Weight = typename Arc::Weight;
380 using MatcherBase<Arc>::Flags;
381 using MatcherBase<Arc>::Final;
382 using MatcherBase<Arc>::Priority;
384 HashMatcher(const FST &fst, MatchType match_type)
387 match_type_(match_type),
388 loop_(kNoLabel, 0, Weight::One(), kNoStateId) {
389 switch (match_type_) {
394 std::swap(loop_.ilabel, loop_.olabel);
397 FSTERROR() << "SortedMatcher: Bad match type";
398 match_type_ = MATCH_NONE;
403 HashMatcher(const HashMatcher<FST> &matcher, bool safe = false)
404 : fst_(matcher.fst_->Copy(safe)),
406 match_type_(matcher.match_type_),
407 loop_(matcher.loop_),
408 error_(matcher.error_) {}
410 HashMatcher<FST> *Copy(bool safe = false) const override {
411 return new HashMatcher<FST>(*this, safe);
414 // The argument is ignored as there are no relevant properties to test.
415 MatchType Type(bool test) const override { return match_type_; }
417 void SetState(StateId s) final;
419 bool Find(Label label) final {
420 current_loop_ = label == 0;
425 if (label == kNoLabel) label = 0;
426 return Search(label);
429 bool Done() const final {
430 if (current_loop_) return false;
431 return label_it_ == label_end_;
434 const Arc &Value() const final {
435 if (current_loop_) return loop_;
436 aiter_->Seek(label_it_->second);
437 return aiter_->Value();
442 current_loop_ = false;
448 const FST &GetFst() const override { return *fst_; }
450 uint64 Properties(uint64 inprops) const override {
451 return inprops | (error_ ? kError : 0);
455 bool Search(Label match_label);
457 using LabelTable = std::unordered_multimap<Label, size_t>;
458 using StateTable = std::unordered_map<StateId, LabelTable>;
460 std::unique_ptr<const FST> fst_;
461 StateId state_; // Matcher state.
462 MatchType match_type_;
463 Arc loop_; // The implicit loop itself.
464 bool current_loop_; // Is the current arc is the implicit loop?
465 bool error_; // Error encountered?
466 std::unique_ptr<ArcIterator<FST>> aiter_;
467 StateTable state_table_; // Table from states to label table.
468 LabelTable *label_table_; // Pointer to current state's label table.
469 typename LabelTable::iterator label_it_; // Position for label.
470 typename LabelTable::iterator label_end_; // Position for last label + 1.
474 void HashMatcher<FST>::SetState(typename FST::Arc::StateId s) {
475 if (state_ == s) return;
476 // Resets everything for the state.
478 loop_.nextstate = state_;
479 aiter_.reset(new ArcIterator<FST>(*fst_, state_));
480 if (match_type_ == MATCH_NONE) {
481 FSTERROR() << "HashMatcher: Bad match type";
484 // Attempts to insert a new label table; if it already exists,
485 // no additional work is done and we simply return.
486 auto it_and_success = state_table_.emplace(state_, LabelTable());
487 if (!it_and_success.second) return;
488 // Otherwise, populate this new table.
489 // Sets instance's pointer to the label table for this state.
490 label_table_ = &(it_and_success.first->second);
491 // Populates the label table.
492 label_table_->reserve(internal::NumArcs(*fst_, state_));
493 const auto aiter_flags =
494 (match_type_ == MATCH_INPUT ? kArcILabelValue : kArcOLabelValue) |
496 aiter_->SetFlags(aiter_flags, kArcFlags);
497 for (; !aiter_->Done(); aiter_->Next()) {
498 const auto label = (match_type_ == MATCH_INPUT) ? aiter_->Value().ilabel
499 : aiter_->Value().olabel;
500 label_table_->emplace(label, aiter_->Position());
502 aiter_->SetFlags(kArcValueFlags, kArcValueFlags);
506 inline bool HashMatcher<FST>::Search(typename FST::Arc::Label match_label) {
507 auto range = label_table_->equal_range(match_label);
508 if (range.first == range.second) return false;
509 label_it_ = range.first;
510 label_end_ = range.second;
511 aiter_->Seek(label_it_->second);
515 // Specifies whether we rewrite both the input and output sides during matching.
516 enum MatcherRewriteMode {
517 MATCHER_REWRITE_AUTO = 0, // Rewrites both sides iff acceptor.
518 MATCHER_REWRITE_ALWAYS,
519 MATCHER_REWRITE_NEVER
522 // For any requested label that doesn't match at a state, this matcher
523 // considers the *unique* transition that matches the label 'phi_label'
524 // (phi = 'fail'), and recursively looks for a match at its
525 // destination. When 'phi_loop' is true, if no match is found but a
526 // phi self-loop is found, then the phi transition found is returned
527 // with the phi_label rewritten as the requested label (both sides if
528 // an acceptor, or if 'rewrite_both' is true and both input and output
529 // labels of the found transition are 'phi_label'). If 'phi_label' is
530 // kNoLabel, this special matching is not done. PhiMatcher is
531 // templated itself on a matcher, which is used to perform the
532 // underlying matching. By default, the underlying matcher is
533 // constructed by PhiMatcher. The user can instead pass in this
534 // object; in that case, PhiMatcher takes its ownership.
535 // Phi non-determinism not supported. No non-consuming symbols other
536 // than epsilon supported with the underlying template argument matcher.
538 class PhiMatcher : public MatcherBase<typename M::Arc> {
540 using FST = typename M::FST;
541 using Arc = typename FST::Arc;
542 using Label = typename Arc::Label;
543 using StateId = typename Arc::StateId;
544 using Weight = typename Arc::Weight;
546 PhiMatcher(const FST &fst, MatchType match_type, Label phi_label = kNoLabel,
547 bool phi_loop = true,
548 MatcherRewriteMode rewrite_mode = MATCHER_REWRITE_AUTO,
549 M *matcher = nullptr)
550 : matcher_(matcher ? matcher : new M(fst, match_type)),
551 match_type_(match_type),
552 phi_label_(phi_label),
556 if (match_type == MATCH_BOTH) {
557 FSTERROR() << "PhiMatcher: Bad match type";
558 match_type_ = MATCH_NONE;
561 if (rewrite_mode == MATCHER_REWRITE_AUTO) {
562 rewrite_both_ = fst.Properties(kAcceptor, true);
563 } else if (rewrite_mode == MATCHER_REWRITE_ALWAYS) {
564 rewrite_both_ = true;
566 rewrite_both_ = false;
570 PhiMatcher(const PhiMatcher<M> &matcher, bool safe = false)
571 : matcher_(new M(*matcher.matcher_, safe)),
572 match_type_(matcher.match_type_),
573 phi_label_(matcher.phi_label_),
574 rewrite_both_(matcher.rewrite_both_),
576 phi_loop_(matcher.phi_loop_),
577 error_(matcher.error_) {}
579 PhiMatcher<M> *Copy(bool safe = false) const override {
580 return new PhiMatcher<M>(*this, safe);
583 MatchType Type(bool test) const override { return matcher_->Type(test); }
585 void SetState(StateId s) final {
586 if (state_ == s) return;
587 matcher_->SetState(s);
589 has_phi_ = phi_label_ != kNoLabel;
592 bool Find(Label match_label) final;
594 bool Done() const final { return matcher_->Done(); }
596 const Arc &Value() const final {
597 if ((phi_match_ == kNoLabel) && (phi_weight_ == Weight::One())) {
598 return matcher_->Value();
599 } else if (phi_match_ == 0) { // Virtual epsilon loop.
600 phi_arc_ = Arc(kNoLabel, 0, Weight::One(), state_);
601 if (match_type_ == MATCH_OUTPUT) {
602 std::swap(phi_arc_.ilabel, phi_arc_.olabel);
606 phi_arc_ = matcher_->Value();
607 phi_arc_.weight = Times(phi_weight_, phi_arc_.weight);
608 if (phi_match_ != kNoLabel) { // Phi loop match.
610 if (phi_arc_.ilabel == phi_label_) phi_arc_.ilabel = phi_match_;
611 if (phi_arc_.olabel == phi_label_) phi_arc_.olabel = phi_match_;
612 } else if (match_type_ == MATCH_INPUT) {
613 phi_arc_.ilabel = phi_match_;
615 phi_arc_.olabel = phi_match_;
622 void Next() final { matcher_->Next(); }
624 Weight Final(StateId s) const final {
625 auto weight = matcher_->Final(s);
626 if (phi_label_ == kNoLabel || weight != Weight::Zero()) {
629 weight = Weight::One();
630 matcher_->SetState(s);
631 while (matcher_->Final(s) == Weight::Zero()) {
632 if (!matcher_->Find(phi_label_ == 0 ? -1 : phi_label_)) break;
633 weight = Times(weight, matcher_->Value().weight);
634 if (s == matcher_->Value().nextstate) {
635 return Weight::Zero(); // Does not follow phi self-loops.
637 s = matcher_->Value().nextstate;
638 matcher_->SetState(s);
640 weight = Times(weight, matcher_->Final(s));
644 ssize_t Priority(StateId s) final {
645 if (phi_label_ != kNoLabel) {
646 matcher_->SetState(s);
647 const bool has_phi = matcher_->Find(phi_label_ == 0 ? -1 : phi_label_);
648 return has_phi ? kRequirePriority : matcher_->Priority(s);
650 return matcher_->Priority(s);
654 const FST &GetFst() const override { return matcher_->GetFst(); }
656 uint64 Properties(uint64 props) const override;
658 uint32 Flags() const override {
659 if (phi_label_ == kNoLabel || match_type_ == MATCH_NONE) {
660 return matcher_->Flags();
662 return matcher_->Flags() | kRequireMatch;
665 Label PhiLabel() const { return phi_label_; }
668 mutable std::unique_ptr<M> matcher_;
669 MatchType match_type_; // Type of match requested.
670 Label phi_label_; // Label that represents the phi transition.
671 bool rewrite_both_; // Rewrite both sides when both are phi_label_?
672 bool has_phi_; // Are there possibly phis at the current state?
673 Label phi_match_; // Current label that matches phi loop.
674 mutable Arc phi_arc_; // Arc to return.
675 StateId state_; // Matcher state.
676 Weight phi_weight_; // Product of the weights of phi transitions taken.
677 bool phi_loop_; // When true, phi self-loop are allowed and treated
678 // as rho (required for Aho-Corasick).
679 bool error_; // Error encountered?
681 PhiMatcher &operator=(const PhiMatcher &) = delete;
685 inline bool PhiMatcher<M>::Find(Label label) {
686 if (label == phi_label_ && phi_label_ != kNoLabel && phi_label_ != 0) {
687 FSTERROR() << "PhiMatcher::Find: bad label (phi): " << phi_label_;
691 matcher_->SetState(state_);
692 phi_match_ = kNoLabel;
693 phi_weight_ = Weight::One();
694 // If phi_label_ == 0, there are no more true epsilon arcs.
695 if (phi_label_ == 0) {
696 if (label == kNoLabel) {
699 if (label == 0) { // but a virtual epsilon loop needs to be returned.
700 if (!matcher_->Find(kNoLabel)) {
701 return matcher_->Find(0);
708 if (!has_phi_ || label == 0 || label == kNoLabel) {
709 return matcher_->Find(label);
712 while (!matcher_->Find(label)) {
713 // Look for phi transition (if phi_label_ == 0, we need to look
714 // for -1 to avoid getting the virtual self-loop)
715 if (!matcher_->Find(phi_label_ == 0 ? -1 : phi_label_)) return false;
716 if (phi_loop_ && matcher_->Value().nextstate == s) {
720 phi_weight_ = Times(phi_weight_, matcher_->Value().weight);
721 s = matcher_->Value().nextstate;
723 if (!matcher_->Done()) {
724 FSTERROR() << "PhiMatcher: Phi non-determinism not supported";
727 matcher_->SetState(s);
733 inline uint64 PhiMatcher<M>::Properties(uint64 inprops) const {
734 auto outprops = matcher_->Properties(inprops);
735 if (error_) outprops |= kError;
736 if (match_type_ == MATCH_NONE) {
738 } else if (match_type_ == MATCH_INPUT) {
739 if (phi_label_ == 0) {
740 outprops &= ~kEpsilons | ~kIEpsilons | ~kOEpsilons;
741 outprops |= kNoEpsilons | kNoIEpsilons;
745 ~(kODeterministic | kNonODeterministic | kString | kILabelSorted |
746 kNotILabelSorted | kOLabelSorted | kNotOLabelSorted);
749 ~(kODeterministic | kAcceptor | kString | kILabelSorted |
750 kNotILabelSorted | kOLabelSorted | kNotOLabelSorted);
752 } else if (match_type_ == MATCH_OUTPUT) {
753 if (phi_label_ == 0) {
754 outprops &= ~kEpsilons | ~kIEpsilons | ~kOEpsilons;
755 outprops |= kNoEpsilons | kNoOEpsilons;
759 ~(kIDeterministic | kNonIDeterministic | kString | kILabelSorted |
760 kNotILabelSorted | kOLabelSorted | kNotOLabelSorted);
763 ~(kIDeterministic | kAcceptor | kString | kILabelSorted |
764 kNotILabelSorted | kOLabelSorted | kNotOLabelSorted);
767 // Shouldn't ever get here.
768 FSTERROR() << "PhiMatcher: Bad match type: " << match_type_;
773 // For any requested label that doesn't match at a state, this matcher
774 // considers all transitions that match the label 'rho_label' (rho =
775 // 'rest'). Each such rho transition found is returned with the
776 // rho_label rewritten as the requested label (both sides if an
777 // acceptor, or if 'rewrite_both' is true and both input and output
778 // labels of the found transition are 'rho_label'). If 'rho_label' is
779 // kNoLabel, this special matching is not done. RhoMatcher is
780 // templated itself on a matcher, which is used to perform the
781 // underlying matching. By default, the underlying matcher is
782 // constructed by RhoMatcher. The user can instead pass in this
783 // object; in that case, RhoMatcher takes its ownership.
784 // No non-consuming symbols other than epsilon supported with
785 // the underlying template argument matcher.
787 class RhoMatcher : public MatcherBase<typename M::Arc> {
789 using FST = typename M::FST;
790 using Arc = typename FST::Arc;
791 using Label = typename Arc::Label;
792 using StateId = typename Arc::StateId;
793 using Weight = typename Arc::Weight;
795 RhoMatcher(const FST &fst, MatchType match_type, Label rho_label = kNoLabel,
796 MatcherRewriteMode rewrite_mode = MATCHER_REWRITE_AUTO,
797 M *matcher = nullptr)
798 : matcher_(matcher ? matcher : new M(fst, match_type)),
799 match_type_(match_type),
800 rho_label_(rho_label),
803 if (match_type == MATCH_BOTH) {
804 FSTERROR() << "RhoMatcher: Bad match type";
805 match_type_ = MATCH_NONE;
808 if (rho_label == 0) {
809 FSTERROR() << "RhoMatcher: 0 cannot be used as rho_label";
810 rho_label_ = kNoLabel;
813 if (rewrite_mode == MATCHER_REWRITE_AUTO) {
814 rewrite_both_ = fst.Properties(kAcceptor, true);
815 } else if (rewrite_mode == MATCHER_REWRITE_ALWAYS) {
816 rewrite_both_ = true;
818 rewrite_both_ = false;
822 RhoMatcher(const RhoMatcher<M> &matcher, bool safe = false)
823 : matcher_(new M(*matcher.matcher_, safe)),
824 match_type_(matcher.match_type_),
825 rho_label_(matcher.rho_label_),
826 rewrite_both_(matcher.rewrite_both_),
827 error_(matcher.error_),
828 state_(kNoStateId) {}
830 RhoMatcher<M> *Copy(bool safe = false) const override {
831 return new RhoMatcher<M>(*this, safe);
834 MatchType Type(bool test) const override { return matcher_->Type(test); }
836 void SetState(StateId s) final {
837 if (state_ == s) return;
839 matcher_->SetState(s);
840 has_rho_ = rho_label_ != kNoLabel;
843 bool Find(Label label) final {
844 if (label == rho_label_ && rho_label_ != kNoLabel) {
845 FSTERROR() << "RhoMatcher::Find: bad label (rho)";
849 if (matcher_->Find(label)) {
850 rho_match_ = kNoLabel;
852 } else if (has_rho_ && label != 0 && label != kNoLabel &&
853 (has_rho_ = matcher_->Find(rho_label_))) {
861 bool Done() const final { return matcher_->Done(); }
863 const Arc &Value() const final {
864 if (rho_match_ == kNoLabel) {
865 return matcher_->Value();
867 rho_arc_ = matcher_->Value();
869 if (rho_arc_.ilabel == rho_label_) rho_arc_.ilabel = rho_match_;
870 if (rho_arc_.olabel == rho_label_) rho_arc_.olabel = rho_match_;
871 } else if (match_type_ == MATCH_INPUT) {
872 rho_arc_.ilabel = rho_match_;
874 rho_arc_.olabel = rho_match_;
880 void Next() final { matcher_->Next(); }
882 Weight Final(StateId s) const final { return matcher_->Final(s); }
884 ssize_t Priority(StateId s) final {
886 matcher_->SetState(s);
887 has_rho_ = matcher_->Find(rho_label_);
889 return kRequirePriority;
891 return matcher_->Priority(s);
895 const FST &GetFst() const override { return matcher_->GetFst(); }
897 uint64 Properties(uint64 props) const override;
899 uint32 Flags() const override {
900 if (rho_label_ == kNoLabel || match_type_ == MATCH_NONE) {
901 return matcher_->Flags();
903 return matcher_->Flags() | kRequireMatch;
906 Label RhoLabel() const { return rho_label_; }
909 std::unique_ptr<M> matcher_;
910 MatchType match_type_; // Type of match requested.
911 Label rho_label_; // Label that represents the rho transition
912 bool rewrite_both_; // Rewrite both sides when both are rho_label_?
913 bool has_rho_; // Are there possibly rhos at the current state?
914 Label rho_match_; // Current label that matches rho transition.
915 mutable Arc rho_arc_; // Arc to return when rho match.
916 bool error_; // Error encountered?
917 StateId state_; // Matcher state.
921 inline uint64 RhoMatcher<M>::Properties(uint64 inprops) const {
922 auto outprops = matcher_->Properties(inprops);
923 if (error_) outprops |= kError;
924 if (match_type_ == MATCH_NONE) {
926 } else if (match_type_ == MATCH_INPUT) {
929 ~(kODeterministic | kNonODeterministic | kString | kILabelSorted |
930 kNotILabelSorted | kOLabelSorted | kNotOLabelSorted);
933 ~(kODeterministic | kAcceptor | kString | kILabelSorted |
936 } else if (match_type_ == MATCH_OUTPUT) {
939 ~(kIDeterministic | kNonIDeterministic | kString | kILabelSorted |
940 kNotILabelSorted | kOLabelSorted | kNotOLabelSorted);
943 ~(kIDeterministic | kAcceptor | kString | kOLabelSorted |
947 // Shouldn't ever get here.
948 FSTERROR() << "RhoMatcher: Bad match type: " << match_type_;
953 // For any requested label, this matcher considers all transitions
954 // that match the label 'sigma_label' (sigma = "any"), and this in
955 // additions to transitions with the requested label. Each such sigma
956 // transition found is returned with the sigma_label rewritten as the
957 // requested label (both sides if an acceptor, or if 'rewrite_both' is
958 // true and both input and output labels of the found transition are
959 // 'sigma_label'). If 'sigma_label' is kNoLabel, this special
960 // matching is not done. SigmaMatcher is templated itself on a
961 // matcher, which is used to perform the underlying matching. By
962 // default, the underlying matcher is constructed by SigmaMatcher.
963 // The user can instead pass in this object; in that case,
964 // SigmaMatcher takes its ownership. No non-consuming symbols other
965 // than epsilon supported with the underlying template argument matcher.
967 class SigmaMatcher : public MatcherBase<typename M::Arc> {
969 using FST = typename M::FST;
970 using Arc = typename FST::Arc;
971 using Label = typename Arc::Label;
972 using StateId = typename Arc::StateId;
973 using Weight = typename Arc::Weight;
975 SigmaMatcher(const FST &fst, MatchType match_type,
976 Label sigma_label = kNoLabel,
977 MatcherRewriteMode rewrite_mode = MATCHER_REWRITE_AUTO,
978 M *matcher = nullptr)
979 : matcher_(matcher ? matcher : new M(fst, match_type)),
980 match_type_(match_type),
981 sigma_label_(sigma_label),
984 if (match_type == MATCH_BOTH) {
985 FSTERROR() << "SigmaMatcher: Bad match type";
986 match_type_ = MATCH_NONE;
989 if (sigma_label == 0) {
990 FSTERROR() << "SigmaMatcher: 0 cannot be used as sigma_label";
991 sigma_label_ = kNoLabel;
994 if (rewrite_mode == MATCHER_REWRITE_AUTO) {
995 rewrite_both_ = fst.Properties(kAcceptor, true);
996 } else if (rewrite_mode == MATCHER_REWRITE_ALWAYS) {
997 rewrite_both_ = true;
999 rewrite_both_ = false;
1003 SigmaMatcher(const SigmaMatcher<M> &matcher, bool safe = false)
1004 : matcher_(new M(*matcher.matcher_, safe)),
1005 match_type_(matcher.match_type_),
1006 sigma_label_(matcher.sigma_label_),
1007 rewrite_both_(matcher.rewrite_both_),
1008 error_(matcher.error_),
1009 state_(kNoStateId) {}
1011 SigmaMatcher<M> *Copy(bool safe = false) const override {
1012 return new SigmaMatcher<M>(*this, safe);
1015 MatchType Type(bool test) const override { return matcher_->Type(test); }
1017 void SetState(StateId s) final {
1018 if (state_ == s) return;
1020 matcher_->SetState(s);
1022 (sigma_label_ != kNoLabel) ? matcher_->Find(sigma_label_) : false;
1025 bool Find(Label match_label) final {
1026 match_label_ = match_label;
1027 if (match_label == sigma_label_ && sigma_label_ != kNoLabel) {
1028 FSTERROR() << "SigmaMatcher::Find: bad label (sigma)";
1032 if (matcher_->Find(match_label)) {
1033 sigma_match_ = kNoLabel;
1035 } else if (has_sigma_ && match_label != 0 && match_label != kNoLabel &&
1036 matcher_->Find(sigma_label_)) {
1037 sigma_match_ = match_label;
1044 bool Done() const final { return matcher_->Done(); }
1046 const Arc &Value() const final {
1047 if (sigma_match_ == kNoLabel) {
1048 return matcher_->Value();
1050 sigma_arc_ = matcher_->Value();
1051 if (rewrite_both_) {
1052 if (sigma_arc_.ilabel == sigma_label_) sigma_arc_.ilabel = sigma_match_;
1053 if (sigma_arc_.olabel == sigma_label_) sigma_arc_.olabel = sigma_match_;
1054 } else if (match_type_ == MATCH_INPUT) {
1055 sigma_arc_.ilabel = sigma_match_;
1057 sigma_arc_.olabel = sigma_match_;
1065 if (matcher_->Done() && has_sigma_ && (sigma_match_ == kNoLabel) &&
1066 (match_label_ > 0)) {
1067 matcher_->Find(sigma_label_);
1068 sigma_match_ = match_label_;
1072 Weight Final(StateId s) const final { return matcher_->Final(s); }
1074 ssize_t Priority(StateId s) final {
1075 if (sigma_label_ != kNoLabel) {
1077 return has_sigma_ ? kRequirePriority : matcher_->Priority(s);
1079 return matcher_->Priority(s);
1083 const FST &GetFst() const override { return matcher_->GetFst(); }
1085 uint64 Properties(uint64 props) const override;
1087 uint32 Flags() const override {
1088 if (sigma_label_ == kNoLabel || match_type_ == MATCH_NONE) {
1089 return matcher_->Flags();
1091 return matcher_->Flags() | kRequireMatch;
1094 Label SigmaLabel() const { return sigma_label_; }
1097 std::unique_ptr<M> matcher_;
1098 MatchType match_type_; // Type of match requested.
1099 Label sigma_label_; // Label that represents the sigma transition.
1100 bool rewrite_both_; // Rewrite both sides when both are sigma_label_?
1101 bool has_sigma_; // Are there sigmas at the current state?
1102 Label sigma_match_; // Current label that matches sigma transition.
1103 mutable Arc sigma_arc_; // Arc to return when sigma match.
1104 Label match_label_; // Label being matched.
1105 bool error_; // Error encountered?
1106 StateId state_; // Matcher state.
1110 inline uint64 SigmaMatcher<M>::Properties(uint64 inprops) const {
1111 auto outprops = matcher_->Properties(inprops);
1112 if (error_) outprops |= kError;
1113 if (match_type_ == MATCH_NONE) {
1115 } else if (rewrite_both_) {
1117 ~(kIDeterministic | kNonIDeterministic | kODeterministic |
1118 kNonODeterministic | kILabelSorted | kNotILabelSorted |
1119 kOLabelSorted | kNotOLabelSorted | kString);
1120 } else if (match_type_ == MATCH_INPUT) {
1122 ~(kIDeterministic | kNonIDeterministic | kODeterministic |
1123 kNonODeterministic | kILabelSorted | kNotILabelSorted | kString |
1125 } else if (match_type_ == MATCH_OUTPUT) {
1127 ~(kIDeterministic | kNonIDeterministic | kODeterministic |
1128 kNonODeterministic | kOLabelSorted | kNotOLabelSorted | kString |
1131 // Shouldn't ever get here.
1132 FSTERROR() << "SigmaMatcher: Bad match type: " << match_type_;
1137 // Flags for MultiEpsMatcher.
1139 // Return multi-epsilon arcs for Find(kNoLabel).
1140 const uint32 kMultiEpsList = 0x00000001;
1142 // Return a kNolabel loop for Find(multi_eps).
1143 const uint32 kMultiEpsLoop = 0x00000002;
1145 // MultiEpsMatcher: allows treating multiple non-0 labels as
1146 // non-consuming labels in addition to 0 that is always
1147 // non-consuming. Precise behavior controlled by 'flags' argument. By
1148 // default, the underlying matcher is constructed by
1149 // MultiEpsMatcher. The user can instead pass in this object; in that
1150 // case, MultiEpsMatcher takes its ownership iff 'own_matcher' is
1153 class MultiEpsMatcher {
1155 using FST = typename M::FST;
1156 using Arc = typename FST::Arc;
1157 using Label = typename Arc::Label;
1158 using StateId = typename Arc::StateId;
1159 using Weight = typename Arc::Weight;
1161 MultiEpsMatcher(const FST &fst, MatchType match_type,
1162 uint32 flags = (kMultiEpsLoop | kMultiEpsList),
1163 M *matcher = nullptr, bool own_matcher = true)
1164 : matcher_(matcher ? matcher : new M(fst, match_type)),
1166 own_matcher_(matcher ? own_matcher : true) {
1167 if (match_type == MATCH_INPUT) {
1168 loop_.ilabel = kNoLabel;
1172 loop_.olabel = kNoLabel;
1174 loop_.weight = Weight::One();
1175 loop_.nextstate = kNoStateId;
1178 MultiEpsMatcher(const MultiEpsMatcher<M> &matcher, bool safe = false)
1179 : matcher_(new M(*matcher.matcher_, safe)),
1180 flags_(matcher.flags_),
1182 multi_eps_labels_(matcher.multi_eps_labels_),
1183 loop_(matcher.loop_) {
1184 loop_.nextstate = kNoStateId;
1187 ~MultiEpsMatcher() {
1188 if (own_matcher_) delete matcher_;
1191 MultiEpsMatcher<M> *Copy(bool safe = false) const {
1192 return new MultiEpsMatcher<M>(*this, safe);
1195 MatchType Type(bool test) const { return matcher_->Type(test); }
1197 void SetState(StateId state) {
1198 matcher_->SetState(state);
1199 loop_.nextstate = state;
1202 bool Find(Label label);
1204 bool Done() const { return done_; }
1206 const Arc &Value() const { return current_loop_ ? loop_ : matcher_->Value(); }
1209 if (!current_loop_) {
1211 done_ = matcher_->Done();
1212 if (done_ && multi_eps_iter_ != multi_eps_labels_.End()) {
1214 while ((multi_eps_iter_ != multi_eps_labels_.End()) &&
1215 !matcher_->Find(*multi_eps_iter_)) {
1218 if (multi_eps_iter_ != multi_eps_labels_.End()) {
1221 done_ = !matcher_->Find(kNoLabel);
1229 const FST &GetFst() const { return matcher_->GetFst(); }
1231 uint64 Properties(uint64 props) const { return matcher_->Properties(props); }
1233 const M *GetMatcher() const { return matcher_; }
1235 Weight Final(StateId s) const { return matcher_->Final(s); }
1237 uint32 Flags() const { return matcher_->Flags(); }
1239 ssize_t Priority(StateId s) { return matcher_->Priority(s); }
1241 void AddMultiEpsLabel(Label label) {
1243 FSTERROR() << "MultiEpsMatcher: Bad multi-eps label: 0";
1245 multi_eps_labels_.Insert(label);
1249 void RemoveMultiEpsLabel(Label label) {
1251 FSTERROR() << "MultiEpsMatcher: Bad multi-eps label: 0";
1253 multi_eps_labels_.Erase(label);
1257 void ClearMultiEpsLabels() { multi_eps_labels_.Clear(); }
1262 bool own_matcher_; // Does this class delete the matcher?
1264 // Multi-eps label set.
1265 CompactSet<Label, kNoLabel> multi_eps_labels_;
1266 typename CompactSet<Label, kNoLabel>::const_iterator multi_eps_iter_;
1268 bool current_loop_; // Current arc is the implicit loop?
1269 mutable Arc loop_; // For non-consuming symbols.
1270 bool done_; // Matching done?
1272 MultiEpsMatcher &operator=(const MultiEpsMatcher &) = delete;
1276 inline bool MultiEpsMatcher<M>::Find(Label label) {
1277 multi_eps_iter_ = multi_eps_labels_.End();
1278 current_loop_ = false;
1281 ret = matcher_->Find(0);
1282 } else if (label == kNoLabel) {
1283 if (flags_ & kMultiEpsList) {
1284 // Returns all non-consuming arcs (including epsilon).
1285 multi_eps_iter_ = multi_eps_labels_.Begin();
1286 while ((multi_eps_iter_ != multi_eps_labels_.End()) &&
1287 !matcher_->Find(*multi_eps_iter_)) {
1290 if (multi_eps_iter_ != multi_eps_labels_.End()) {
1293 ret = matcher_->Find(kNoLabel);
1296 // Returns all epsilon arcs.
1297 ret = matcher_->Find(kNoLabel);
1299 } else if ((flags_ & kMultiEpsLoop) &&
1300 multi_eps_labels_.Find(label) != multi_eps_labels_.End()) {
1301 // Returns implicit loop.
1302 current_loop_ = true;
1305 ret = matcher_->Find(label);
1311 // This class discards any implicit matches (e.g., the implicit epsilon
1312 // self-loops in the SortedMatcher). Matchers are most often used in
1313 // composition/intersection where the implicit matches are needed
1314 // e.g. for epsilon processing. However, if a matcher is simply being
1315 // used to look-up explicit label matches, this class saves the user
1316 // from having to check for and discard the unwanted implicit matches
1319 class ExplicitMatcher : public MatcherBase<typename M::Arc> {
1321 using FST = typename M::FST;
1322 using Arc = typename FST::Arc;
1323 using Label = typename Arc::Label;
1324 using StateId = typename Arc::StateId;
1325 using Weight = typename Arc::Weight;
1327 ExplicitMatcher(const FST &fst, MatchType match_type, M *matcher = nullptr)
1328 : matcher_(matcher ? matcher : new M(fst, match_type)),
1329 match_type_(match_type),
1332 ExplicitMatcher(const ExplicitMatcher<M> &matcher, bool safe = false)
1333 : matcher_(new M(*matcher.matcher_, safe)),
1334 match_type_(matcher.match_type_),
1335 error_(matcher.error_) {}
1337 ExplicitMatcher<M> *Copy(bool safe = false) const override {
1338 return new ExplicitMatcher<M>(*this, safe);
1341 MatchType Type(bool test) const override { return matcher_->Type(test); }
1343 void SetState(StateId s) final { matcher_->SetState(s); }
1345 bool Find(Label label) final {
1346 matcher_->Find(label);
1351 bool Done() const final { return matcher_->Done(); }
1353 const Arc &Value() const final { return matcher_->Value(); }
1360 Weight Final(StateId s) const final { return matcher_->Final(s); }
1362 ssize_t Priority(StateId s) final { return matcher_->Priority(s); }
1364 const FST &GetFst() const final { return matcher_->GetFst(); }
1366 uint64 Properties(uint64 inprops) const override {
1367 return matcher_->Properties(inprops);
1370 const M *GetMatcher() const { return matcher_.get(); }
1372 uint32 Flags() const override { return matcher_->Flags(); }
1375 // Checks current arc if available and explicit. If not available, stops. If
1376 // not explicit, checks next ones.
1378 for (; !matcher_->Done(); matcher_->Next()) {
1379 const auto label = match_type_ == MATCH_INPUT ? matcher_->Value().ilabel
1380 : matcher_->Value().olabel;
1381 if (label != kNoLabel) return;
1385 std::unique_ptr<M> matcher_;
1386 MatchType match_type_; // Type of match requested.
1387 bool error_; // Error encountered?
1390 // Generic matcher, templated on the FST definition.
1392 // Here is a typical use:
1394 // Matcher<StdFst> matcher(fst, MATCH_INPUT);
1395 // matcher.SetState(state);
1396 // if (matcher.Find(label))
1397 // for (; !matcher.Done(); matcher.Next()) {
1398 // auto &arc = matcher.Value();
1405 using Arc = typename F::Arc;
1406 using Label = typename Arc::Label;
1407 using StateId = typename Arc::StateId;
1408 using Weight = typename Arc::Weight;
1410 Matcher(const FST &fst, MatchType match_type) {
1411 base_.reset(fst.InitMatcher(match_type));
1412 if (!base_) base_.reset(new SortedMatcher<FST>(fst, match_type));
1415 Matcher(const Matcher<FST> &matcher, bool safe = false) {
1416 base_.reset(matcher.base_->Copy(safe));
1419 // Takes ownership of the provided matcher.
1420 explicit Matcher(MatcherBase<Arc> *base_matcher) {
1421 base_.reset(base_matcher);
1424 Matcher<FST> *Copy(bool safe = false) const {
1425 return new Matcher<FST>(*this, safe);
1428 MatchType Type(bool test) const { return base_->Type(test); }
1430 void SetState(StateId s) { base_->SetState(s); }
1432 bool Find(Label label) { return base_->Find(label); }
1434 bool Done() const { return base_->Done(); }
1436 const Arc &Value() const { return base_->Value(); }
1438 void Next() { base_->Next(); }
1440 const FST &GetFst() const {
1441 return static_cast<const FST &>(base_->GetFst());
1444 uint64 Properties(uint64 props) const { return base_->Properties(props); }
1446 Weight Final(StateId s) const { return base_->Final(s); }
1448 uint32 Flags() const { return base_->Flags() & kMatcherFlags; }
1450 ssize_t Priority(StateId s) { return base_->Priority(s); }
1453 std::unique_ptr<MatcherBase<Arc>> base_;
1458 #endif // FST_MATCHER_H_