1 // matcher.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@google.com (Michael Riley)
17 //
18 // \file
19 // Classes to allow matching labels leaving FST states.
20
21 #ifndef FST_LIB_MATCHER_H__
22 #define FST_LIB_MATCHER_H__
23
24 #include <algorithm>
25 #include <set>
26 #include <utility>
27 using std::pair; using std::make_pair;
28
29 #include <fst/mutable-fst.h> // for all internal FST accessors
30
31
32 namespace fst {
33
34 // MATCHERS - these can find and iterate through requested labels at
35 // FST states. In the simplest form, these are just some associative
36 // map or search keyed on labels. More generally, they may
37 // implement matching special labels that represent sets of labels
38 // such as 'sigma' (all), 'rho' (rest), or 'phi' (fail).
39 // The Matcher interface is:
40 //
41 // template <class F>
42 // class Matcher {
43 // public:
44 // typedef F FST;
45 // typedef F::Arc Arc;
46 // typedef typename Arc::StateId StateId;
47 // typedef typename Arc::Label Label;
48 // typedef typename Arc::Weight Weight;
49 //
50 // // Required constructors.
51 // Matcher(const F &fst, MatchType type);
52 // // If safe=true, the copy is thread-safe. See Fst<>::Copy()
53 // // for further doc.
54 // Matcher(const Matcher &matcher, bool safe = false);
55 //
56 // // If safe=true, the copy is thread-safe. See Fst<>::Copy()
57 // // for further doc.
58 // Matcher<F> *Copy(bool safe = false) const;
59 //
60 // // Returns the match type that can be provided (depending on
61 // // compatibility of the input FST). It is either
62 // // the requested match type, MATCH_NONE, or MATCH_UNKNOWN.
63 // // If 'test' is false, a costly testing is avoided, but
64 // // MATCH_UNKNOWN may be returned. If 'test' is true,
65 // // a definite answer is returned, but may involve more costly
66 // // computation (e.g., visiting the Fst).
67 // MatchType Type(bool test) const;
68 // // Specifies the current state.
69 // void SetState(StateId s);
70 //
71 // // This finds matches to a label at the current state.
72 // // Returns true if a match found. kNoLabel matches any
73 // // 'non-consuming' transitions, e.g., epsilon transitions,
74 // // which do not require a matching symbol.
75 // bool Find(Label label);
76 // // These iterate through any matches found:
77 // bool Done() const; // No more matches.
78 // const A& Value() const; // Current arc (when !Done)
79 // void Next(); // Advance to next arc (when !Done)
80 // // Initially and after SetState() the iterator methods
81 // // have undefined behavior until Find() is called.
82 //
83 // // Indicates preference for being the side used for matching in
84 // // composition/intersection. If the value is kRequirePriority,
85 // // then it is manditory that it be used.
86 // // Calling this method when 's' is not the current state of matcher
87 // // invalidates the state of the matcher.
88 // ssize_t Priority(StateId s);
89 //
90 // // Return matcher FST.
91 // const F& GetFst() const;
92 // // This specifies the known Fst properties as viewed from this
93 // // matcher. It takes as argument the input Fst's known properties.
94 // uint64 Properties(uint64 props) const;
95 // };
96
97 //
98 // MATCHER FLAGS (see also kLookAheadFlags in lookahead-matcher.h)
99 //
100 // Matcher needs to be used as the matching side in composition for
101 // at least one state (has kRequirePriority).
102 const uint32 kRequireMatch = 0x00000001;
103
104 // Flags used for basic matchers (see also lookahead.h).
105 const uint32 kMatcherFlags = kRequireMatch;
106
107 // Matcher priority that is manditory.
108 const ssize_t kRequirePriority = -1;
109
110 // Matcher interface, templated on the Arc definition; used
111 // for matcher specializations that are returned by the
112 // InitMatcher Fst method.
113 template <class A>
114 class MatcherBase {
115 public:
116 typedef A Arc;
117 typedef typename A::StateId StateId;
118 typedef typename A::Label Label;
119 typedef typename A::Weight Weight;
120
~MatcherBase()121 virtual ~MatcherBase() {}
122
123 virtual MatcherBase<A> *Copy(bool safe = false) const = 0;
124 virtual MatchType Type(bool test) const = 0;
SetState(StateId s)125 void SetState(StateId s) { SetState_(s); }
Find(Label label)126 bool Find(Label label) { return Find_(label); }
Done()127 bool Done() const { return Done_(); }
Value()128 const A& Value() const { return Value_(); }
Next()129 void Next() { Next_(); }
Priority(StateId s)130 ssize_t Priority(StateId s) { return Priority_(s); }
131
132 virtual const Fst<A> &GetFst() const = 0;
133 virtual uint64 Properties(uint64 props) const = 0;
Flags()134 virtual uint32 Flags() const { return 0; }
135 private:
136 virtual void SetState_(StateId s) = 0;
137 virtual bool Find_(Label label) = 0;
138 virtual bool Done_() const = 0;
139 virtual const A& Value_() const = 0;
140 virtual void Next_() = 0;
141
Priority_(StateId s)142 virtual ssize_t Priority_(StateId s) {
143 return GetFst().NumArcs(s);
144 }
145 };
146
147
148 // A matcher that expects sorted labels on the side to be matched.
149 // If match_type == MATCH_INPUT, epsilons match the implicit self loop
150 // Arc(kNoLabel, 0, Weight::One(), current_state) as well as any
151 // actual epsilon transitions. If match_type == MATCH_OUTPUT, then
152 // Arc(0, kNoLabel, Weight::One(), current_state) is instead matched.
153 template <class F>
154 class SortedMatcher : public MatcherBase<typename F::Arc> {
155 public:
156 typedef F FST;
157 typedef typename F::Arc Arc;
158 typedef typename Arc::StateId StateId;
159 typedef typename Arc::Label Label;
160 typedef typename Arc::Weight Weight;
161
162 // Labels >= binary_label will be searched for by binary search,
163 // o.w. linear search is used.
164 SortedMatcher(const F &fst, MatchType match_type,
165 Label binary_label = 1)
166 : fst_(fst.Copy()),
167 s_(kNoStateId),
168 aiter_(0),
169 match_type_(match_type),
170 binary_label_(binary_label),
171 match_label_(kNoLabel),
172 narcs_(0),
173 loop_(kNoLabel, 0, Weight::One(), kNoStateId),
174 error_(false),
175 aiter_pool_(1) {
176 switch(match_type_) {
177 case MATCH_INPUT:
178 case MATCH_NONE:
179 break;
180 case MATCH_OUTPUT:
181 swap(loop_.ilabel, loop_.olabel);
182 break;
183 default:
184 FSTERROR() << "SortedMatcher: bad match type";
185 match_type_ = MATCH_NONE;
186 error_ = true;
187 }
188 }
189
190 SortedMatcher(const SortedMatcher<F> &matcher, bool safe = false)
191 : fst_(matcher.fst_->Copy(safe)),
192 s_(kNoStateId),
193 aiter_(0),
194 match_type_(matcher.match_type_),
195 binary_label_(matcher.binary_label_),
196 match_label_(kNoLabel),
197 narcs_(0),
198 loop_(matcher.loop_),
199 error_(matcher.error_),
200 aiter_pool_(1) { }
201
~SortedMatcher()202 virtual ~SortedMatcher() {
203 Destroy(aiter_, &aiter_pool_);
204 delete fst_;
205 }
206
207 virtual SortedMatcher<F> *Copy(bool safe = false) const {
208 return new SortedMatcher<F>(*this, safe);
209 }
210
Type(bool test)211 virtual MatchType Type(bool test) const {
212 if (match_type_ == MATCH_NONE)
213 return match_type_;
214
215 uint64 true_prop = match_type_ == MATCH_INPUT ?
216 kILabelSorted : kOLabelSorted;
217 uint64 false_prop = match_type_ == MATCH_INPUT ?
218 kNotILabelSorted : kNotOLabelSorted;
219 uint64 props = fst_->Properties(true_prop | false_prop, test);
220
221 if (props & true_prop)
222 return match_type_;
223 else if (props & false_prop)
224 return MATCH_NONE;
225 else
226 return MATCH_UNKNOWN;
227 }
228
SetState(StateId s)229 void SetState(StateId s) {
230 if (s_ == s)
231 return;
232 s_ = s;
233 if (match_type_ == MATCH_NONE) {
234 FSTERROR() << "SortedMatcher: bad match type";
235 error_ = true;
236 }
237 Destroy(aiter_, &aiter_pool_);
238 aiter_ = new(&aiter_pool_) ArcIterator<F>(*fst_, s);
239 aiter_->SetFlags(kArcNoCache, kArcNoCache);
240 narcs_ = internal::NumArcs(*fst_, s);
241 loop_.nextstate = s;
242 }
243
Find(Label match_label)244 bool Find(Label match_label) {
245 exact_match_ = true;
246 if (error_) {
247 current_loop_ = false;
248 match_label_ = kNoLabel;
249 return false;
250 }
251 current_loop_ = match_label == 0;
252 match_label_ = match_label == kNoLabel ? 0 : match_label;
253 if (Search()) {
254 return true;
255 } else {
256 return current_loop_;
257 }
258 }
259
260 // Positions matcher to the first position where inserting
261 // match_label would maintain the sort order.
LowerBound(Label match_label)262 void LowerBound(Label match_label) {
263 exact_match_ = false;
264 current_loop_ = false;
265 if (error_) {
266 match_label_ = kNoLabel;
267 return;
268 }
269 match_label_ = match_label;
270 Search();
271 }
272
273 // After Find(), returns false if no more exact matches.
274 // After LowerBound(), returns false if no more arcs.
Done()275 bool Done() const {
276 if (current_loop_)
277 return false;
278 if (aiter_->Done())
279 return true;
280 if (!exact_match_)
281 return false;
282 aiter_->SetFlags(
283 match_type_ == MATCH_INPUT ? kArcILabelValue : kArcOLabelValue,
284 kArcValueFlags);
285 Label label = match_type_ == MATCH_INPUT ?
286 aiter_->Value().ilabel : aiter_->Value().olabel;
287 return label != match_label_;
288 }
289
Value()290 const Arc& Value() const {
291 if (current_loop_) {
292 return loop_;
293 }
294 aiter_->SetFlags(kArcValueFlags, kArcValueFlags);
295 return aiter_->Value();
296 }
297
Next()298 void Next() {
299 if (current_loop_)
300 current_loop_ = false;
301 else
302 aiter_->Next();
303 }
304
Priority(StateId s)305 ssize_t Priority(StateId s) {
306 return internal::NumArcs(*fst_, s);
307 }
308
GetFst()309 virtual const F &GetFst() const { return *fst_; }
310
Properties(uint64 inprops)311 virtual uint64 Properties(uint64 inprops) const {
312 uint64 outprops = inprops;
313 if (error_) outprops |= kError;
314 return outprops;
315 }
316
Position()317 size_t Position() const { return aiter_ ? aiter_->Position() : 0; }
318
319 private:
SetState_(StateId s)320 virtual void SetState_(StateId s) { SetState(s); }
Find_(Label label)321 virtual bool Find_(Label label) { return Find(label); }
Done_()322 virtual bool Done_() const { return Done(); }
Value_()323 virtual const Arc& Value_() const { return Value(); }
Next_()324 virtual void Next_() { Next(); }
Priority_(StateId s)325 virtual ssize_t Priority_(StateId s) { return Priority(s); }
326
327 bool Search();
328
329 const F *fst_;
330 StateId s_; // Current state
331 ArcIterator<F> *aiter_; // Iterator for current state
332 MatchType match_type_; // Type of match to perform
333 Label binary_label_; // Least label for binary search
334 Label match_label_; // Current label to be matched
335 size_t narcs_; // Current state arc count
336 Arc loop_; // For non-consuming symbols
337 bool current_loop_; // Current arc is the implicit loop
338 bool exact_match_; // Exact match or lower bound?
339 bool error_; // Error encountered
340 MemoryPool< ArcIterator<F> > aiter_pool_; // Pool of arc iterators
341
342 void operator=(const SortedMatcher<F> &); // Disallow
343 };
344
345 // Returns true iff match to match_label_. Positions arc iterator at
346 // lower bound regardless.
347 template <class F> inline
Search()348 bool SortedMatcher<F>::Search() {
349 aiter_->SetFlags(
350 match_type_ == MATCH_INPUT ? kArcILabelValue : kArcOLabelValue,
351 kArcValueFlags);
352 if (match_label_ >= binary_label_) {
353 // Binary search for match.
354 size_t low = 0;
355 size_t high = narcs_;
356 while (low < high) {
357 size_t mid = (low + high) / 2;
358 aiter_->Seek(mid);
359 Label label = match_type_ == MATCH_INPUT ?
360 aiter_->Value().ilabel : aiter_->Value().olabel;
361 if (label > match_label_) {
362 high = mid;
363 } else if (label < match_label_) {
364 low = mid + 1;
365 } else {
366 // find first matching label (when non-determinism)
367 for (size_t i = mid; i > low; --i) {
368 aiter_->Seek(i - 1);
369 label = match_type_ == MATCH_INPUT ? aiter_->Value().ilabel :
370 aiter_->Value().olabel;
371 if (label != match_label_) {
372 aiter_->Seek(i);
373 return true;
374 }
375 }
376 return true;
377 }
378 }
379 aiter_->Seek(low);
380 return false;
381 } else {
382 // Linear search for match.
383 for (aiter_->Reset(); !aiter_->Done(); aiter_->Next()) {
384 Label label = match_type_ == MATCH_INPUT ?
385 aiter_->Value().ilabel : aiter_->Value().olabel;
386 if (label == match_label_) {
387 return true;
388 }
389 if (label > match_label_)
390 break;
391 }
392 return false;
393 }
394 }
395
396
397 // Specifies whether during matching we rewrite both the input and output sides.
398 enum MatcherRewriteMode {
399 MATCHER_REWRITE_AUTO = 0, // Rewrites both sides iff acceptor.
400 MATCHER_REWRITE_ALWAYS,
401 MATCHER_REWRITE_NEVER
402 };
403
404
405 // For any requested label that doesn't match at a state, this matcher
406 // considers all transitions that match the label 'rho_label' (rho =
407 // 'rest'). Each such rho transition found is returned with the
408 // rho_label rewritten as the requested label (both sides if an
409 // acceptor, or if 'rewrite_both' is true and both input and output
410 // labels of the found transition are 'rho_label'). If 'rho_label' is
411 // kNoLabel, this special matching is not done. RhoMatcher is
412 // templated itself on a matcher, which is used to perform the
413 // underlying matching. By default, the underlying matcher is
414 // constructed by RhoMatcher. The user can instead pass in this
415 // object; in that case, RhoMatcher takes its ownership.
416 template <class M>
417 class RhoMatcher : public MatcherBase<typename M::Arc> {
418 public:
419 typedef typename M::FST FST;
420 typedef typename M::Arc Arc;
421 typedef typename Arc::StateId StateId;
422 typedef typename Arc::Label Label;
423 typedef typename Arc::Weight Weight;
424
425 RhoMatcher(const FST &fst,
426 MatchType match_type,
427 Label rho_label = kNoLabel,
428 MatcherRewriteMode rewrite_mode = MATCHER_REWRITE_AUTO,
429 M *matcher = 0)
430 : matcher_(matcher ? matcher : new M(fst, match_type)),
431 match_type_(match_type),
432 rho_label_(rho_label),
433 error_(false),
434 s_(kNoStateId) {
435 if (match_type == MATCH_BOTH) {
436 FSTERROR() << "RhoMatcher: bad match type";
437 match_type_ = MATCH_NONE;
438 error_ = true;
439 }
440 if (rho_label == 0) {
441 FSTERROR() << "RhoMatcher: 0 cannot be used as rho_label";
442 rho_label_ = kNoLabel;
443 error_ = true;
444 }
445
446 if (rewrite_mode == MATCHER_REWRITE_AUTO)
447 rewrite_both_ = fst.Properties(kAcceptor, true);
448 else if (rewrite_mode == MATCHER_REWRITE_ALWAYS)
449 rewrite_both_ = true;
450 else
451 rewrite_both_ = false;
452 }
453
454 RhoMatcher(const RhoMatcher<M> &matcher, bool safe = false)
455 : matcher_(new M(*matcher.matcher_, safe)),
456 match_type_(matcher.match_type_),
457 rho_label_(matcher.rho_label_),
458 rewrite_both_(matcher.rewrite_both_),
459 error_(matcher.error_),
460 s_(kNoStateId) {}
461
~RhoMatcher()462 virtual ~RhoMatcher() {
463 delete matcher_;
464 }
465
466 virtual RhoMatcher<M> *Copy(bool safe = false) const {
467 return new RhoMatcher<M>(*this, safe);
468 }
469
Type(bool test)470 virtual MatchType Type(bool test) const { return matcher_->Type(test); }
471
SetState(StateId s)472 void SetState(StateId s) {
473 if (s_ == s) return;
474 s_ = s;
475 matcher_->SetState(s);
476 has_rho_ = rho_label_ != kNoLabel;
477 }
478
Find(Label match_label)479 bool Find(Label match_label) {
480 if (match_label == rho_label_ && rho_label_ != kNoLabel) {
481 FSTERROR() << "RhoMatcher::Find: bad label (rho)";
482 error_ = true;
483 return false;
484 }
485 if (matcher_->Find(match_label)) {
486 rho_match_ = kNoLabel;
487 return true;
488 } else if (has_rho_ && match_label != 0 && match_label != kNoLabel &&
489 (has_rho_ = matcher_->Find(rho_label_))) {
490 rho_match_ = match_label;
491 return true;
492 } else {
493 return false;
494 }
495 }
496
Done()497 bool Done() const { return matcher_->Done(); }
498
Value()499 const Arc& Value() const {
500 if (rho_match_ == kNoLabel) {
501 return matcher_->Value();
502 } else {
503 rho_arc_ = matcher_->Value();
504 if (rewrite_both_) {
505 if (rho_arc_.ilabel == rho_label_)
506 rho_arc_.ilabel = rho_match_;
507 if (rho_arc_.olabel == rho_label_)
508 rho_arc_.olabel = rho_match_;
509 } else if (match_type_ == MATCH_INPUT) {
510 rho_arc_.ilabel = rho_match_;
511 } else {
512 rho_arc_.olabel = rho_match_;
513 }
514 return rho_arc_;
515 }
516 }
517
Next()518 void Next() { matcher_->Next(); }
519
Priority(StateId s)520 ssize_t Priority(StateId s) {
521 s_ = s;
522 matcher_->SetState(s);
523 has_rho_ = matcher_->Find(rho_label_);
524 if (has_rho_) {
525 return kRequirePriority;
526 } else {
527 return matcher_->Priority(s);
528 }
529 }
530
GetFst()531 virtual const FST &GetFst() const { return matcher_->GetFst(); }
532
533 virtual uint64 Properties(uint64 props) const;
534
Flags()535 virtual uint32 Flags() const {
536 if (rho_label_ == kNoLabel || match_type_ == MATCH_NONE) {
537 return matcher_->Flags();
538 }
539 return matcher_->Flags() | kRequireMatch;
540 }
541
542 private:
SetState_(StateId s)543 virtual void SetState_(StateId s) { SetState(s); }
Find_(Label label)544 virtual bool Find_(Label label) { return Find(label); }
Done_()545 virtual bool Done_() const { return Done(); }
Value_()546 virtual const Arc& Value_() const { return Value(); }
Next_()547 virtual void Next_() { Next(); }
Priority_(StateId s)548 virtual ssize_t Priority_(StateId s) { return Priority(s); }
549
550 M *matcher_;
551 MatchType match_type_; // Type of match requested
552 Label rho_label_; // Label that represents the rho transition
553 bool rewrite_both_; // Rewrite both sides when both are 'rho_label_'
554 bool has_rho_; // Are there possibly rhos at the current state?
555 Label rho_match_; // Current label that matches rho transition
556 mutable Arc rho_arc_; // Arc to return when rho match
557 bool error_; // Error encountered
558 StateId s_; // Current state
559
560 void operator=(const RhoMatcher<M> &); // Disallow
561 };
562
563 template <class M> inline
Properties(uint64 inprops)564 uint64 RhoMatcher<M>::Properties(uint64 inprops) const {
565 uint64 outprops = matcher_->Properties(inprops);
566 if (error_) outprops |= kError;
567
568 if (match_type_ == MATCH_NONE) {
569 return outprops;
570 } else if (match_type_ == MATCH_INPUT) {
571 if (rewrite_both_) {
572 return outprops & ~(kODeterministic | kNonODeterministic | kString |
573 kILabelSorted | kNotILabelSorted |
574 kOLabelSorted | kNotOLabelSorted);
575 } else {
576 return outprops & ~(kODeterministic | kAcceptor | kString |
577 kILabelSorted | kNotILabelSorted);
578 }
579 } else if (match_type_ == MATCH_OUTPUT) {
580 if (rewrite_both_) {
581 return outprops & ~(kIDeterministic | kNonIDeterministic | kString |
582 kILabelSorted | kNotILabelSorted |
583 kOLabelSorted | kNotOLabelSorted);
584 } else {
585 return outprops & ~(kIDeterministic | kAcceptor | kString |
586 kOLabelSorted | kNotOLabelSorted);
587 }
588 } else {
589 // Shouldn't ever get here.
590 FSTERROR() << "RhoMatcher:: bad match type: " << match_type_;
591 return 0;
592 }
593 }
594
595
596 // For any requested label, this matcher considers all transitions
597 // that match the label 'sigma_label' (sigma = "any"), and this in
598 // additions to transitions with the requested label. Each such sigma
599 // transition found is returned with the sigma_label rewritten as the
600 // requested label (both sides if an acceptor, or if 'rewrite_both' is
601 // true and both input and output labels of the found transition are
602 // 'sigma_label'). If 'sigma_label' is kNoLabel, this special
603 // matching is not done. SigmaMatcher is templated itself on a
604 // matcher, which is used to perform the underlying matching. By
605 // default, the underlying matcher is constructed by SigmaMatcher.
606 // The user can instead pass in this object; in that case,
607 // SigmaMatcher takes its ownership.
608 template <class M>
609 class SigmaMatcher : public MatcherBase<typename M::Arc> {
610 public:
611 typedef typename M::FST FST;
612 typedef typename M::Arc Arc;
613 typedef typename Arc::StateId StateId;
614 typedef typename Arc::Label Label;
615 typedef typename Arc::Weight Weight;
616
617 SigmaMatcher(const FST &fst,
618 MatchType match_type,
619 Label sigma_label = kNoLabel,
620 MatcherRewriteMode rewrite_mode = MATCHER_REWRITE_AUTO,
621 M *matcher = 0)
622 : matcher_(matcher ? matcher : new M(fst, match_type)),
623 match_type_(match_type),
624 sigma_label_(sigma_label),
625 error_(false),
626 s_(kNoStateId) {
627 if (match_type == MATCH_BOTH) {
628 FSTERROR() << "SigmaMatcher: bad match type";
629 match_type_ = MATCH_NONE;
630 error_ = true;
631 }
632 if (sigma_label == 0) {
633 FSTERROR() << "SigmaMatcher: 0 cannot be used as sigma_label";
634 sigma_label_ = kNoLabel;
635 error_ = true;
636 }
637
638 if (rewrite_mode == MATCHER_REWRITE_AUTO)
639 rewrite_both_ = fst.Properties(kAcceptor, true);
640 else if (rewrite_mode == MATCHER_REWRITE_ALWAYS)
641 rewrite_both_ = true;
642 else
643 rewrite_both_ = false;
644 }
645
646 SigmaMatcher(const SigmaMatcher<M> &matcher, bool safe = false)
647 : matcher_(new M(*matcher.matcher_, safe)),
648 match_type_(matcher.match_type_),
649 sigma_label_(matcher.sigma_label_),
650 rewrite_both_(matcher.rewrite_both_),
651 error_(matcher.error_),
652 s_(kNoStateId) {}
653
~SigmaMatcher()654 virtual ~SigmaMatcher() {
655 delete matcher_;
656 }
657
658 virtual SigmaMatcher<M> *Copy(bool safe = false) const {
659 return new SigmaMatcher<M>(*this, safe);
660 }
661
Type(bool test)662 virtual MatchType Type(bool test) const { return matcher_->Type(test); }
663
SetState(StateId s)664 void SetState(StateId s) {
665 if (s == s_) return;
666 s_ = s;
667 matcher_->SetState(s);
668 has_sigma_ =
669 sigma_label_ != kNoLabel ? matcher_->Find(sigma_label_) : false;
670 }
671
Find(Label match_label)672 bool Find(Label match_label) {
673 match_label_ = match_label;
674 if (match_label == sigma_label_ && sigma_label_ != kNoLabel) {
675 FSTERROR() << "SigmaMatcher::Find: bad label (sigma)";
676 error_ = true;
677 return false;
678 }
679 if (matcher_->Find(match_label)) {
680 sigma_match_ = kNoLabel;
681 return true;
682 } else if (has_sigma_ && match_label != 0 && match_label != kNoLabel &&
683 matcher_->Find(sigma_label_)) {
684 sigma_match_ = match_label;
685 return true;
686 } else {
687 return false;
688 }
689 }
690
Done()691 bool Done() const {
692 return matcher_->Done();
693 }
694
Value()695 const Arc& Value() const {
696 if (sigma_match_ == kNoLabel) {
697 return matcher_->Value();
698 } else {
699 sigma_arc_ = matcher_->Value();
700 if (rewrite_both_) {
701 if (sigma_arc_.ilabel == sigma_label_)
702 sigma_arc_.ilabel = sigma_match_;
703 if (sigma_arc_.olabel == sigma_label_)
704 sigma_arc_.olabel = sigma_match_;
705 } else if (match_type_ == MATCH_INPUT) {
706 sigma_arc_.ilabel = sigma_match_;
707 } else {
708 sigma_arc_.olabel = sigma_match_;
709 }
710 return sigma_arc_;
711 }
712 }
713
Next()714 void Next() {
715 matcher_->Next();
716 if (matcher_->Done() && has_sigma_ && (sigma_match_ == kNoLabel) &&
717 (match_label_ > 0)) {
718 matcher_->Find(sigma_label_);
719 sigma_match_ = match_label_;
720 }
721 }
722
Priority(StateId s)723 ssize_t Priority(StateId s) {
724 if (sigma_label_ != kNoLabel) {
725 SetState(s);
726 return has_sigma_ ? kRequirePriority : matcher_->Priority(s);
727 } else {
728 return matcher_->Priority(s);
729 }
730 }
731
GetFst()732 virtual const FST &GetFst() const { return matcher_->GetFst(); }
733
734 virtual uint64 Properties(uint64 props) const;
735
Flags()736 virtual uint32 Flags() const {
737 if (sigma_label_ == kNoLabel || match_type_ == MATCH_NONE)
738 return matcher_->Flags();
739 return matcher_->Flags() | kRequireMatch;
740 }
741
742 private:
SetState_(StateId s)743 virtual void SetState_(StateId s) { SetState(s); }
Find_(Label label)744 virtual bool Find_(Label label) { return Find(label); }
Done_()745 virtual bool Done_() const { return Done(); }
Value_()746 virtual const Arc& Value_() const { return Value(); }
Next_()747 virtual void Next_() { Next(); }
Priority_(StateId s)748 virtual ssize_t Priority_(StateId s) { return Priority(s); }
749
750 M *matcher_;
751 MatchType match_type_; // Type of match requested
752 Label sigma_label_; // Label that represents the sigma transition
753 bool rewrite_both_; // Rewrite both sides when both are 'sigma_label_'
754 bool has_sigma_; // Are there sigmas at the current state?
755 Label sigma_match_; // Current label that matches sigma transition
756 mutable Arc sigma_arc_; // Arc to return when sigma match
757 Label match_label_; // Label being matched
758 bool error_; // Error encountered
759 StateId s_; // Current state
760
761 void operator=(const SigmaMatcher<M> &); // disallow
762 };
763
764 template <class M> inline
Properties(uint64 inprops)765 uint64 SigmaMatcher<M>::Properties(uint64 inprops) const {
766 uint64 outprops = matcher_->Properties(inprops);
767 if (error_) outprops |= kError;
768
769 if (match_type_ == MATCH_NONE) {
770 return outprops;
771 } else if (rewrite_both_) {
772 return outprops & ~(kIDeterministic | kNonIDeterministic |
773 kODeterministic | kNonODeterministic |
774 kILabelSorted | kNotILabelSorted |
775 kOLabelSorted | kNotOLabelSorted |
776 kString);
777 } else if (match_type_ == MATCH_INPUT) {
778 return outprops & ~(kIDeterministic | kNonIDeterministic |
779 kODeterministic | kNonODeterministic |
780 kILabelSorted | kNotILabelSorted |
781 kString | kAcceptor);
782 } else if (match_type_ == MATCH_OUTPUT) {
783 return outprops & ~(kIDeterministic | kNonIDeterministic |
784 kODeterministic | kNonODeterministic |
785 kOLabelSorted | kNotOLabelSorted |
786 kString | kAcceptor);
787 } else {
788 // Shouldn't ever get here.
789 FSTERROR() << "SigmaMatcher:: bad match type: " << match_type_;
790 return 0;
791 }
792 }
793
794
795 // For any requested label that doesn't match at a state, this matcher
796 // considers the *unique* transition that matches the label 'phi_label'
797 // (phi = 'fail'), and recursively looks for a match at its
798 // destination. When 'phi_loop' is true, if no match is found but a
799 // phi self-loop is found, then the phi transition found is returned
800 // with the phi_label rewritten as the requested label (both sides if
801 // an acceptor, or if 'rewrite_both' is true and both input and output
802 // labels of the found transition are 'phi_label'). If 'phi_label' is
803 // kNoLabel, this special matching is not done. PhiMatcher is
804 // templated itself on a matcher, which is used to perform the
805 // underlying matching. By default, the underlying matcher is
806 // constructed by PhiMatcher. The user can instead pass in this
807 // object; in that case, PhiMatcher takes its ownership.
808 // Warning: phi non-determinism not supported (for simplicity).
809 template <class M>
810 class PhiMatcher : public MatcherBase<typename M::Arc> {
811 public:
812 typedef typename M::FST FST;
813 typedef typename M::Arc Arc;
814 typedef typename Arc::StateId StateId;
815 typedef typename Arc::Label Label;
816 typedef typename Arc::Weight Weight;
817
818 PhiMatcher(const FST &fst,
819 MatchType match_type,
820 Label phi_label = kNoLabel,
821 bool phi_loop = true,
822 MatcherRewriteMode rewrite_mode = MATCHER_REWRITE_AUTO,
823 M *matcher = 0)
824 : matcher_(matcher ? matcher : new M(fst, match_type)),
825 match_type_(match_type),
826 phi_label_(phi_label),
827 state_(kNoStateId),
828 phi_loop_(phi_loop),
829 error_(false) {
830 if (match_type == MATCH_BOTH) {
831 FSTERROR() << "PhiMatcher: bad match type";
832 match_type_ = MATCH_NONE;
833 error_ = true;
834 }
835
836 if (rewrite_mode == MATCHER_REWRITE_AUTO)
837 rewrite_both_ = fst.Properties(kAcceptor, true);
838 else if (rewrite_mode == MATCHER_REWRITE_ALWAYS)
839 rewrite_both_ = true;
840 else
841 rewrite_both_ = false;
842 }
843
844 PhiMatcher(const PhiMatcher<M> &matcher, bool safe = false)
845 : matcher_(new M(*matcher.matcher_, safe)),
846 match_type_(matcher.match_type_),
847 phi_label_(matcher.phi_label_),
848 rewrite_both_(matcher.rewrite_both_),
849 state_(kNoStateId),
850 phi_loop_(matcher.phi_loop_),
851 error_(matcher.error_) {}
852
~PhiMatcher()853 virtual ~PhiMatcher() {
854 delete matcher_;
855 }
856
857 virtual PhiMatcher<M> *Copy(bool safe = false) const {
858 return new PhiMatcher<M>(*this, safe);
859 }
860
Type(bool test)861 virtual MatchType Type(bool test) const { return matcher_->Type(test); }
862
SetState(StateId s)863 void SetState(StateId s) {
864 if (state_ == s) return;
865 matcher_->SetState(s);
866 state_ = s;
867 has_phi_ = phi_label_ != kNoLabel;
868 }
869
870 bool Find(Label match_label);
871
Done()872 bool Done() const { return matcher_->Done(); }
873
Value()874 const Arc& Value() const {
875 if ((phi_match_ == kNoLabel) && (phi_weight_ == Weight::One())) {
876 return matcher_->Value();
877 } else if (phi_match_ == 0) { // Virtual epsilon loop
878 phi_arc_ = Arc(kNoLabel, 0, Weight::One(), state_);
879 if (match_type_ == MATCH_OUTPUT)
880 swap(phi_arc_.ilabel, phi_arc_.olabel);
881 return phi_arc_;
882 } else {
883 phi_arc_ = matcher_->Value();
884 phi_arc_.weight = Times(phi_weight_, phi_arc_.weight);
885 if (phi_match_ != kNoLabel) { // Phi loop match
886 if (rewrite_both_) {
887 if (phi_arc_.ilabel == phi_label_)
888 phi_arc_.ilabel = phi_match_;
889 if (phi_arc_.olabel == phi_label_)
890 phi_arc_.olabel = phi_match_;
891 } else if (match_type_ == MATCH_INPUT) {
892 phi_arc_.ilabel = phi_match_;
893 } else {
894 phi_arc_.olabel = phi_match_;
895 }
896 }
897 return phi_arc_;
898 }
899 }
900
Next()901 void Next() { matcher_->Next(); }
902
Priority(StateId s)903 ssize_t Priority(StateId s) {
904 if (phi_label_ != kNoLabel) {
905 matcher_->SetState(s);
906 has_phi_ = matcher_->Find(phi_label_);
907 state_ = s;
908 return has_phi_ ? kRequirePriority : matcher_->Priority(s);
909 } else {
910 return matcher_->Priority(s);
911 }
912 }
913
GetFst()914 virtual const FST &GetFst() const { return matcher_->GetFst(); }
915
916 virtual uint64 Properties(uint64 props) const;
917
Flags()918 virtual uint32 Flags() const {
919 if (phi_label_ == kNoLabel || match_type_ == MATCH_NONE)
920 return matcher_->Flags();
921 return matcher_->Flags() | kRequireMatch;
922 }
923
924 private:
SetState_(StateId s)925 virtual void SetState_(StateId s) { SetState(s); }
Find_(Label label)926 virtual bool Find_(Label label) { return Find(label); }
Done_()927 virtual bool Done_() const { return Done(); }
Value_()928 virtual const Arc& Value_() const { return Value(); }
Next_()929 virtual void Next_() { Next(); }
Priority_(StateId s)930 virtual ssize_t Priority_(StateId s) { return Priority(s); }
931
932 M *matcher_;
933 MatchType match_type_; // Type of match requested
934 Label phi_label_; // Label that represents the phi transition
935 bool rewrite_both_; // Rewrite both sides when both are 'phi_label_'
936 bool has_phi_; // Are there possibly phis at the current state?
937 Label phi_match_; // Current label that matches phi loop
938 mutable Arc phi_arc_; // Arc to return
939 StateId state_; // State where looking for matches
940 Weight phi_weight_; // Product of the weights of phi transitions taken
941 bool phi_loop_; // When true, phi self-loop are allowed and treated
942 // as rho (required for Aho-Corasick)
943 bool error_; // Error encountered
944
945 void operator=(const PhiMatcher<M> &); // disallow
946 };
947
948 template <class M> inline
Find(Label match_label)949 bool PhiMatcher<M>::Find(Label match_label) {
950 if (match_label == phi_label_ && phi_label_ != kNoLabel && phi_label_ != 0) {
951 FSTERROR() << "PhiMatcher::Find: bad label (phi): " << phi_label_;
952 error_ = true;
953 return false;
954 }
955 matcher_->SetState(state_);
956 phi_match_ = kNoLabel;
957 phi_weight_ = Weight::One();
958 if (phi_label_ == 0) { // When 'phi_label_ == 0',
959 if (match_label == kNoLabel) // there are no more true epsilon arcs,
960 return false;
961 if (match_label == 0) { // but virtual eps loop need to be returned
962 if (!matcher_->Find(kNoLabel)) {
963 return matcher_->Find(0);
964 } else {
965 phi_match_ = 0;
966 return true;
967 }
968 }
969 }
970 if (!has_phi_ || match_label == 0 || match_label == kNoLabel)
971 return matcher_->Find(match_label);
972 StateId state = state_;
973 while (!matcher_->Find(match_label)) {
974 // Look for phi transition (if phi_label_ == 0, we need to look
975 // for -1 to avoid getting the virtual self-loop)
976 if (!matcher_->Find(phi_label_ == 0 ? -1 : phi_label_))
977 return false;
978 if (phi_loop_ && matcher_->Value().nextstate == state) {
979 phi_match_ = match_label;
980 return true;
981 }
982 phi_weight_ = Times(phi_weight_, matcher_->Value().weight);
983 state = matcher_->Value().nextstate;
984 matcher_->Next();
985 if (!matcher_->Done()) {
986 FSTERROR() << "PhiMatcher: phi non-determinism not supported";
987 error_ = true;
988 }
989 matcher_->SetState(state);
990 }
991 return true;
992 }
993
994 template <class M> inline
Properties(uint64 inprops)995 uint64 PhiMatcher<M>::Properties(uint64 inprops) const {
996 uint64 outprops = matcher_->Properties(inprops);
997 if (error_) outprops |= kError;
998
999 if (match_type_ == MATCH_NONE) {
1000 return outprops;
1001 } else if (match_type_ == MATCH_INPUT) {
1002 if (phi_label_ == 0) {
1003 outprops &= ~kEpsilons | ~kIEpsilons | ~kOEpsilons;
1004 outprops |= kNoEpsilons | kNoIEpsilons;
1005 }
1006 if (rewrite_both_) {
1007 return outprops & ~(kODeterministic | kNonODeterministic | kString |
1008 kILabelSorted | kNotILabelSorted |
1009 kOLabelSorted | kNotOLabelSorted);
1010 } else {
1011 return outprops & ~(kODeterministic | kAcceptor | kString |
1012 kILabelSorted | kNotILabelSorted |
1013 kOLabelSorted | kNotOLabelSorted);
1014 }
1015 } else if (match_type_ == MATCH_OUTPUT) {
1016 if (phi_label_ == 0) {
1017 outprops &= ~kEpsilons | ~kIEpsilons | ~kOEpsilons;
1018 outprops |= kNoEpsilons | kNoOEpsilons;
1019 }
1020 if (rewrite_both_) {
1021 return outprops & ~(kIDeterministic | kNonIDeterministic | kString |
1022 kILabelSorted | kNotILabelSorted |
1023 kOLabelSorted | kNotOLabelSorted);
1024 } else {
1025 return outprops & ~(kIDeterministic | kAcceptor | kString |
1026 kILabelSorted | kNotILabelSorted |
1027 kOLabelSorted | kNotOLabelSorted);
1028 }
1029 } else {
1030 // Shouldn't ever get here.
1031 FSTERROR() << "PhiMatcher:: bad match type: " << match_type_;
1032 return 0;
1033 }
1034 }
1035
1036
1037 //
1038 // MULTI-EPS MATCHER FLAGS
1039 //
1040
1041 // Return multi-epsilon arcs for Find(kNoLabel).
1042 const uint32 kMultiEpsList = 0x00000001;
1043
1044 // Return a kNolabel loop for Find(multi_eps).
1045 const uint32 kMultiEpsLoop = 0x00000002;
1046
1047 // MultiEpsMatcher: allows treating multiple non-0 labels as
1048 // non-consuming labels in addition to 0 that is always
1049 // non-consuming. Precise behavior controlled by 'flags' argument. By
1050 // default, the underlying matcher is constructed by
1051 // MultiEpsMatcher. The user can instead pass in this object; in that
1052 // case, MultiEpsMatcher takes its ownership iff 'own_matcher' is
1053 // true.
1054 template <class M>
1055 class MultiEpsMatcher {
1056 public:
1057 typedef typename M::FST FST;
1058 typedef typename M::Arc Arc;
1059 typedef typename Arc::StateId StateId;
1060 typedef typename Arc::Label Label;
1061 typedef typename Arc::Weight Weight;
1062
1063 MultiEpsMatcher(const FST &fst, MatchType match_type,
1064 uint32 flags = (kMultiEpsLoop | kMultiEpsList),
1065 M *matcher = 0, bool own_matcher = true)
1066 : matcher_(matcher ? matcher : new M(fst, match_type)),
1067 flags_(flags),
1068 own_matcher_(matcher ? own_matcher : true) {
1069 if (match_type == MATCH_INPUT) {
1070 loop_.ilabel = kNoLabel;
1071 loop_.olabel = 0;
1072 } else {
1073 loop_.ilabel = 0;
1074 loop_.olabel = kNoLabel;
1075 }
1076 loop_.weight = Weight::One();
1077 loop_.nextstate = kNoStateId;
1078 }
1079
1080 MultiEpsMatcher(const MultiEpsMatcher<M> &matcher, bool safe = false)
1081 : matcher_(new M(*matcher.matcher_, safe)),
1082 flags_(matcher.flags_),
1083 own_matcher_(true),
1084 multi_eps_labels_(matcher.multi_eps_labels_),
1085 loop_(matcher.loop_) {
1086 loop_.nextstate = kNoStateId;
1087 }
1088
~MultiEpsMatcher()1089 ~MultiEpsMatcher() {
1090 if (own_matcher_)
1091 delete matcher_;
1092 }
1093
1094 MultiEpsMatcher<M> *Copy(bool safe = false) const {
1095 return new MultiEpsMatcher<M>(*this, safe);
1096 }
1097
Type(bool test)1098 MatchType Type(bool test) const { return matcher_->Type(test); }
1099
SetState(StateId s)1100 void SetState(StateId s) {
1101 matcher_->SetState(s);
1102 loop_.nextstate = s;
1103 }
1104
1105 bool Find(Label match_label);
1106
Done()1107 bool Done() const {
1108 return done_;
1109 }
1110
Value()1111 const Arc& Value() const {
1112 return current_loop_ ? loop_ : matcher_->Value();
1113 }
1114
Next()1115 void Next() {
1116 if (!current_loop_) {
1117 matcher_->Next();
1118 done_ = matcher_->Done();
1119 if (done_ && multi_eps_iter_ != multi_eps_labels_.End()) {
1120 ++multi_eps_iter_;
1121 while ((multi_eps_iter_ != multi_eps_labels_.End()) &&
1122 !matcher_->Find(*multi_eps_iter_))
1123 ++multi_eps_iter_;
1124 if (multi_eps_iter_ != multi_eps_labels_.End())
1125 done_ = false;
1126 else
1127 done_ = !matcher_->Find(kNoLabel);
1128
1129 }
1130 } else {
1131 done_ = true;
1132 }
1133 }
1134
Priority(StateId s)1135 ssize_t Priority(StateId s) { return matcher_->Priority(s); }
1136
GetFst()1137 const FST &GetFst() const { return matcher_->GetFst(); }
1138
GetMatcher()1139 const M *GetMatcher() const { return matcher_; }
1140
Properties(uint64 props)1141 uint64 Properties(uint64 props) const { return matcher_->Properties(props); }
1142
Flags()1143 uint32 Flags() const { return matcher_->Flags(); }
1144
AddMultiEpsLabel(Label label)1145 void AddMultiEpsLabel(Label label) {
1146 if (label == 0) {
1147 FSTERROR() << "MultiEpsMatcher: Bad multi-eps label: 0";
1148 } else {
1149 multi_eps_labels_.Insert(label);
1150 }
1151 }
1152
RemoveMultiEpsLabel(Label label)1153 void RemoveMultiEpsLabel(Label label) {
1154 if (label == 0) {
1155 FSTERROR() << "MultiEpsMatcher: Bad multi-eps label: 0";
1156 } else {
1157 multi_eps_labels_.Erase(label);
1158 }
1159 }
1160
ClearMultiEpsLabels()1161 void ClearMultiEpsLabels() {
1162 multi_eps_labels_.Clear();
1163 }
1164
1165 private:
1166 M *matcher_;
1167 uint32 flags_;
1168 bool own_matcher_; // Does this class delete the matcher?
1169
1170 // Multi-eps label set
1171 CompactSet<Label, kNoLabel> multi_eps_labels_;
1172 typename CompactSet<Label, kNoLabel>::const_iterator multi_eps_iter_;
1173
1174 bool current_loop_; // Current arc is the implicit loop
1175 mutable Arc loop_; // For non-consuming symbols
1176 bool done_; // Matching done
1177
1178 void operator=(const MultiEpsMatcher<M> &); // Disallow
1179 };
1180
1181 template <class M> inline
Find(Label match_label)1182 bool MultiEpsMatcher<M>::Find(Label match_label) {
1183 multi_eps_iter_ = multi_eps_labels_.End();
1184 current_loop_ = false;
1185 bool ret;
1186 if (match_label == 0) {
1187 ret = matcher_->Find(0);
1188 } else if (match_label == kNoLabel) {
1189 if (flags_ & kMultiEpsList) {
1190 // return all non-consuming arcs (incl. epsilon)
1191 multi_eps_iter_ = multi_eps_labels_.Begin();
1192 while ((multi_eps_iter_ != multi_eps_labels_.End()) &&
1193 !matcher_->Find(*multi_eps_iter_))
1194 ++multi_eps_iter_;
1195 if (multi_eps_iter_ != multi_eps_labels_.End())
1196 ret = true;
1197 else
1198 ret = matcher_->Find(kNoLabel);
1199 } else {
1200 // return all epsilon arcs
1201 ret = matcher_->Find(kNoLabel);
1202 }
1203 } else if ((flags_ & kMultiEpsLoop) &&
1204 multi_eps_labels_.Find(match_label) != multi_eps_labels_.End()) {
1205 // return 'implicit' loop
1206 current_loop_ = true;
1207 ret = true;
1208 } else {
1209 ret = matcher_->Find(match_label);
1210 }
1211 done_ = !ret;
1212 return ret;
1213 }
1214
1215
1216 // This class discards any implicit matches (e.g. the implicit epsilon
1217 // self-loops in the SortedMatcher). Matchers are most often used in
1218 // composition/intersection where the implicit matches are needed
1219 // e.g. for epsilon processing. However, if a matcher is simply being
1220 // used to look-up explicit label matches, this class saves the user
1221 // from having to check for and discard the unwanted implicit matches
1222 // themselves.
1223 template <class M>
1224 class ExplicitMatcher : public MatcherBase<typename M::Arc> {
1225 public:
1226 typedef typename M::FST FST;
1227 typedef typename M::Arc Arc;
1228 typedef typename Arc::StateId StateId;
1229 typedef typename Arc::Label Label;
1230 typedef typename Arc::Weight Weight;
1231
1232 ExplicitMatcher(const FST &fst,
1233 MatchType match_type,
1234 M *matcher = 0)
1235 : matcher_(matcher ? matcher : new M(fst, match_type)),
1236 match_type_(match_type),
1237 error_(false) {
1238 }
1239
1240 ExplicitMatcher(const ExplicitMatcher<M> &matcher, bool safe = false)
1241 : matcher_(new M(*matcher.matcher_, safe)),
1242 match_type_(matcher.match_type_),
1243 error_(matcher.error_) {}
1244
~ExplicitMatcher()1245 virtual ~ExplicitMatcher() {
1246 delete matcher_;
1247 }
1248
1249 virtual ExplicitMatcher<M> *Copy(bool safe = false) const {
1250 return new ExplicitMatcher<M>(*this, safe);
1251 }
1252
Type(bool test)1253 virtual MatchType Type(bool test) const { return matcher_->Type(test); }
1254
SetState(StateId s)1255 void SetState(StateId s) {
1256 matcher_->SetState(s);
1257 }
1258
Find(Label match_label)1259 bool Find(Label match_label) {
1260 matcher_->Find(match_label);
1261 CheckArc();
1262 return !Done();
1263 }
1264
Done()1265 bool Done() const { return matcher_->Done(); }
1266
Value()1267 const Arc& Value() const { return matcher_->Value(); }
1268
Next()1269 void Next() {
1270 matcher_->Next();
1271 CheckArc();
1272 }
1273
Priority(StateId s)1274 ssize_t Priority(StateId s) { return matcher_->Priority(s); }
1275
GetFst()1276 virtual const FST &GetFst() const { return matcher_->GetFst(); }
1277
Properties(uint64 inprops)1278 virtual uint64 Properties(uint64 inprops) const {
1279 return matcher_->Properties(inprops);
1280 }
1281
Flags()1282 virtual uint32 Flags() const {
1283 return matcher_->Flags();
1284 }
1285
1286 private:
1287 // Checks current arc if available and explicit.
1288 // If not available, stops. If not explicit, checks next ones.
CheckArc()1289 void CheckArc() {
1290 for (; !matcher_->Done(); matcher_->Next()) {
1291 Label label = match_type_ == MATCH_INPUT ?
1292 matcher_->Value().ilabel : matcher_->Value().olabel;
1293 if (label != kNoLabel) return;
1294 }
1295 }
1296
SetState_(StateId s)1297 virtual void SetState_(StateId s) { SetState(s); }
Find_(Label label)1298 virtual bool Find_(Label label) { return Find(label); }
Done_()1299 virtual bool Done_() const { return Done(); }
Value_()1300 virtual const Arc& Value_() const { return Value(); }
Next_()1301 virtual void Next_() { Next(); }
Priority_(StateId s)1302 virtual ssize_t Priority_(StateId s) { return Priority(s); }
1303
1304 M *matcher_;
1305 MatchType match_type_; // Type of match requested
1306 bool error_; // Error encountered
1307
1308 void operator=(const ExplicitMatcher<M> &); // disallow
1309 };
1310
1311
1312 // Generic matcher, templated on the FST definition
1313 // - a wrapper around pointer to specific one.
1314 // Here is a typical use: \code
1315 // Matcher<StdFst> matcher(fst, MATCH_INPUT);
1316 // matcher.SetState(state);
1317 // if (matcher.Find(label))
1318 // for (; !matcher.Done(); matcher.Next()) {
1319 // StdArc &arc = matcher.Value();
1320 // ...
1321 // } \endcode
1322 template <class F>
1323 class Matcher {
1324 public:
1325 typedef F FST;
1326 typedef typename F::Arc Arc;
1327 typedef typename Arc::StateId StateId;
1328 typedef typename Arc::Label Label;
1329 typedef typename Arc::Weight Weight;
1330
Matcher(const F & fst,MatchType match_type)1331 Matcher(const F &fst, MatchType match_type) {
1332 base_ = fst.InitMatcher(match_type);
1333 if (!base_)
1334 base_ = new SortedMatcher<F>(fst, match_type);
1335 }
1336
1337 Matcher(const Matcher<F> &matcher, bool safe = false) {
1338 base_ = matcher.base_->Copy(safe);
1339 }
1340
1341 // Takes ownership of the provided matcher
Matcher(MatcherBase<Arc> * base_matcher)1342 Matcher(MatcherBase<Arc>* base_matcher) { base_ = base_matcher; }
1343
~Matcher()1344 ~Matcher() { delete base_; }
1345
1346 Matcher<F> *Copy(bool safe = false) const {
1347 return new Matcher<F>(*this, safe);
1348 }
1349
Type(bool test)1350 MatchType Type(bool test) const { return base_->Type(test); }
SetState(StateId s)1351 void SetState(StateId s) { base_->SetState(s); }
Find(Label label)1352 bool Find(Label label) { return base_->Find(label); }
Done()1353 bool Done() const { return base_->Done(); }
Value()1354 const Arc& Value() const { return base_->Value(); }
Next()1355 void Next() { base_->Next(); }
Priority(StateId s)1356 ssize_t Priority(StateId s) { return base_->Priority(s); }
GetFst()1357 const F &GetFst() const { return static_cast<const F &>(base_->GetFst()); }
Properties(uint64 props)1358 uint64 Properties(uint64 props) const { return base_->Properties(props); }
Flags()1359 uint32 Flags() const { return base_->Flags() & kMatcherFlags; }
1360
1361 private:
1362 MatcherBase<Arc> *base_;
1363
1364 void operator=(const Matcher<Arc> &); // disallow
1365 };
1366
1367 } // namespace fst
1368
1369
1370
1371 #endif // FST_LIB_MATCHER_H__
1372