FST  openfst-1.8.3
OpenFst Library
matcher-fst.h
Go to the documentation of this file.
1 // Copyright 2005-2024 Google LLC
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 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Class to add a matcher to an FST.
19 
20 #ifndef FST_MATCHER_FST_H_
21 #define FST_MATCHER_FST_H_
22 
23 #include <cstdint>
24 #include <istream>
25 #include <memory>
26 #include <ostream>
27 #include <string>
28 
29 #include <fst/accumulator.h>
30 #include <fst/add-on.h>
31 #include <fst/arc.h>
32 #include <fst/const-fst.h>
33 #include <fst/expanded-fst.h>
34 #include <fst/float-weight.h>
35 #include <fst/fst.h>
36 #include <fst/impl-to-fst.h>
37 #include <fst/lookahead-matcher.h>
38 #include <fst/matcher.h>
39 #include <string_view>
40 
41 namespace fst {
42 
43 // Writeable matchers have the same interface as Matchers (as defined in
44 // matcher.h) along with the following additional methods:
45 //
46 // template <class F>
47 // class Matcher {
48 // public:
49 // using FST = F;
50 // ...
51 // using MatcherData = ...; // Initialization data.
52 //
53 // // Constructor with additional argument for external initialization data;
54 // // matcher increments its reference count on construction and decrements
55 // // the reference count, and deletes once the reference count has reached
56 // // zero.
57 // Matcher(const FST &fst, MatchType type, MatcherData *data);
58 //
59 // // Returns pointer to initialization data that can be passed to a Matcher
60 // // constructor.
61 // MatcherData *GetData() const;
62 // };
63 
64 // The matcher initialization data class must also provide the following
65 // interface:
66 //
67 // class MatcherData {
68 // public:
69 // // Required copy constructor.
70 // MatcherData(const MatcherData &);
71 //
72 // // Required I/O methods.
73 // static MatcherData *Read(std::istream &istrm, const FstReadOptions &opts);
74 // bool Write(std::ostream &ostrm, const FstWriteOptions &opts) const;
75 // };
76 
77 // Trivial (no-op) MatcherFst initializer functor.
78 template <class M>
80  public:
81  using MatcherData = typename M::MatcherData;
84 
85  explicit NullMatcherFstInit(std::shared_ptr<Impl> *) {}
86 };
87 
88 // Class adding a matcher to an FST type. Creates a new FST whose name is given
89 // by N. An optional functor Init can be used to initialize the FST. The Data
90 // template parameter allows the user to select the type of the add-on.
91 template <
92  class F, class M, const char *Name, class Init = NullMatcherFstInit<M>,
94 class MatcherFst : public ImplToExpandedFst<internal::AddOnImpl<F, Data>> {
95  public:
96  using FST = F;
97  using Arc = typename FST::Arc;
98  using StateId = typename Arc::StateId;
99 
100  using FstMatcher = M;
101  using MatcherData = typename FstMatcher::MatcherData;
102 
104  using D = Data;
105 
106  friend class StateIterator<MatcherFst<FST, FstMatcher, Name, Init, Data>>;
107  friend class ArcIterator<MatcherFst<FST, FstMatcher, Name, Init, Data>>;
108 
109  MatcherFst() : ImplToExpandedFst<Impl>(std::make_shared<Impl>(FST(), Name)) {}
110 
111  // Constructs a MatcherFst from an FST, which is the underlying FST type used
112  // by this class. Uses the existing Data if present, and runs Init on it.
113  // Stores fst internally, making a thread-safe copy of it.
114  explicit MatcherFst(const FST &fst, std::shared_ptr<Data> data = nullptr)
115  : ImplToExpandedFst<Impl>(data ? CreateImpl(fst, Name, data)
116  : CreateDataAndImpl(fst, Name)) {}
117 
118  // Constructs a MatcherFst from an Fst<Arc>, which is *not* the underlying
119  // FST type used by this class. Uses the existing Data if present, and
120  // runs Init on it. Stores fst internally, converting Fst<Arc> to FST and
121  // therefore making a deep copy.
122  explicit MatcherFst(const Fst<Arc> &fst, std::shared_ptr<Data> data = nullptr)
123  : ImplToExpandedFst<Impl>(data ? CreateImpl(fst, Name, data)
124  : CreateDataAndImpl(fst, Name)) {}
125 
126  // See Fst<>::Copy() for doc.
127  MatcherFst(const MatcherFst &fst, bool safe = false)
128  : ImplToExpandedFst<Impl>(fst, safe) {}
129 
130  // Get a copy of this MatcherFst. See Fst<>::Copy() for further doc.
131  MatcherFst *Copy(bool safe = false) const override {
132  return new MatcherFst(*this, safe);
133  }
134 
135  // Read a MatcherFst from an input stream; return nullptr on error
136  static MatcherFst *Read(std::istream &strm, const FstReadOptions &opts) {
137  auto *impl = Impl::Read(strm, opts);
138  return impl ? new MatcherFst(std::shared_ptr<Impl>(impl)) : nullptr;
139  }
140 
141  // Read a MatcherFst from a file; return nullptr on error
142  // Empty source reads from standard input
143  static MatcherFst *Read(std::string_view source) {
144  auto *impl = ImplToExpandedFst<Impl>::Read(source);
145  return impl ? new MatcherFst(std::shared_ptr<Impl>(impl)) : nullptr;
146  }
147 
148  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
149  return GetImpl()->Write(strm, opts);
150  }
151 
152  bool Write(const std::string &source) const override {
153  return Fst<Arc>::WriteFile(source);
154  }
155 
156  void InitStateIterator(StateIteratorData<Arc> *data) const override {
157  return GetImpl()->InitStateIterator(data);
158  }
159 
160  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
161  return GetImpl()->InitArcIterator(s, data);
162  }
163 
164  FstMatcher *InitMatcher(MatchType match_type) const override {
165  return new FstMatcher(&GetFst(), match_type, GetSharedData(match_type));
166  }
167 
168  const FST &GetFst() const { return GetImpl()->GetFst(); }
169 
170  const Data *GetAddOn() const { return GetImpl()->GetAddOn(); }
171 
172  std::shared_ptr<Data> GetSharedAddOn() const {
173  return GetImpl()->GetSharedAddOn();
174  }
175 
176  const MatcherData *GetData(MatchType match_type) const {
177  const auto *data = GetAddOn();
178  return match_type == MATCH_INPUT ? data->First() : data->Second();
179  }
180 
181  std::shared_ptr<MatcherData> GetSharedData(MatchType match_type) const {
182  const auto *data = GetAddOn();
183  return match_type == MATCH_INPUT ? data->SharedFirst()
184  : data->SharedSecond();
185  }
186 
187  protected:
188  using ImplToFst<Impl, ExpandedFst<Arc>>::GetImpl;
189 
190  // Makes a thread-safe copy of fst.
191  static std::shared_ptr<Impl> CreateDataAndImpl(const FST &fst,
192  std::string_view name) {
193  FstMatcher imatcher(fst, MATCH_INPUT);
194  FstMatcher omatcher(fst, MATCH_OUTPUT);
195  return CreateImpl(fst, name,
196  std::make_shared<Data>(imatcher.GetSharedData(),
197  omatcher.GetSharedData()));
198  }
199 
200  // Makes a deep copy of fst.
201  static std::shared_ptr<Impl> CreateDataAndImpl(const Fst<Arc> &fst,
202  std::string_view name) {
203  FST result(fst);
204  return CreateDataAndImpl(result, name);
205  }
206 
207  // Makes a thread-safe copy of fst.
208  static std::shared_ptr<Impl> CreateImpl(const FST &fst,
209  std::string_view name,
210  std::shared_ptr<Data> data) {
211  auto impl = std::make_shared<Impl>(fst, name);
212  impl->SetAddOn(data);
213  Init init(&impl);
214  return impl;
215  }
216 
217  // Makes a deep copy of fst.
218  static std::shared_ptr<Impl> CreateImpl(const Fst<Arc> &fst,
219  std::string_view name,
220  std::shared_ptr<Data> data) {
221  auto impl = std::make_shared<Impl>(fst, name);
222  impl->SetAddOn(data);
223  Init init(&impl);
224  return impl;
225  }
226 
227  explicit MatcherFst(std::shared_ptr<Impl> impl)
228  : ImplToExpandedFst<Impl>(impl) {}
229 
230  private:
231  MatcherFst &operator=(const MatcherFst &) = delete;
232 };
233 
234 // Specialization for MatcherFst.
235 template <class FST, class M, const char *Name, class Init>
236 class StateIterator<MatcherFst<FST, M, Name, Init>>
237  : public StateIterator<FST> {
238  public:
240  : StateIterator<FST>(fst.GetImpl()->GetFst()) {}
241 };
242 
243 // Specialization for MatcherFst.
244 template <class FST, class M, const char *Name, class Init>
245 class ArcIterator<MatcherFst<FST, M, Name, Init>> : public ArcIterator<FST> {
246  public:
247  using StateId = typename FST::Arc::StateId;
248 
250  typename FST::Arc::StateId s)
251  : ArcIterator<FST>(fst.GetImpl()->GetFst(), s) {}
252 };
253 
254 // Specialization for MatcherFst.
255 template <class F, class M, const char *Name, class Init>
256 class Matcher<MatcherFst<F, M, Name, Init>> {
257  public:
259  using Arc = typename F::Arc;
260  using Label = typename Arc::Label;
261  using StateId = typename Arc::StateId;
262 
263  Matcher(const FST &fst, MatchType match_type)
264  : matcher_(fst.InitMatcher(match_type)) {}
265 
266  Matcher(const Matcher &matcher) : matcher_(matcher.matcher_->Copy()) {}
267 
268  Matcher *Copy() const { return new Matcher(*this); }
269 
270  MatchType Type(bool test) const { return matcher_->Type(test); }
271 
272  void SetState(StateId s) { matcher_->SetState(s); }
273 
274  bool Find(Label label) { return matcher_->Find(label); }
275 
276  bool Done() const { return matcher_->Done(); }
277 
278  const Arc &Value() const { return matcher_->Value(); }
279 
280  void Next() { matcher_->Next(); }
281 
282  uint64_t Properties(uint64_t props) const {
283  return matcher_->Properties(props);
284  }
285 
286  uint32_t Flags() const { return matcher_->Flags(); }
287 
288  private:
289  std::unique_ptr<M> matcher_;
290 };
291 
292 // Specialization for MatcherFst.
293 template <class F, class M, const char *Name, class Init>
294 class LookAheadMatcher<MatcherFst<F, M, Name, Init>> {
295  public:
297  using Arc = typename F::Arc;
298  using Label = typename Arc::Label;
299  using StateId = typename Arc::StateId;
300  using Weight = typename Arc::Weight;
301 
302  LookAheadMatcher(const FST &fst, MatchType match_type)
303  : matcher_(fst.InitMatcher(match_type)) {}
304 
305  LookAheadMatcher(const LookAheadMatcher &matcher, bool safe = false)
306  : matcher_(matcher.matcher_->Copy(safe)) {}
307 
308  // General matcher methods.
309  LookAheadMatcher *Copy(bool safe = false) const {
310  return new LookAheadMatcher(*this, safe);
311  }
312 
313  MatchType Type(bool test) const { return matcher_->Type(test); }
314 
315  void SetState(StateId s) { matcher_->SetState(s); }
316 
317  bool Find(Label label) { return matcher_->Find(label); }
318 
319  bool Done() const { return matcher_->Done(); }
320 
321  const Arc &Value() const { return matcher_->Value(); }
322 
323  void Next() { matcher_->Next(); }
324 
325  const FST &GetFst() const { return matcher_->GetFst(); }
326 
327  uint64_t Properties(uint64_t props) const {
328  return matcher_->Properties(props);
329  }
330 
331  uint32_t Flags() const { return matcher_->Flags(); }
332 
333  bool LookAheadLabel(Label label) const {
334  return matcher_->LookAheadLabel(label);
335  }
336 
337  bool LookAheadFst(const Fst<Arc> &fst, StateId s) {
338  return matcher_->LookAheadFst(fst, s);
339  }
340 
341  Weight LookAheadWeight() const { return matcher_->LookAheadWeight(); }
342 
343  bool LookAheadPrefix(Arc *arc) const {
344  return matcher_->LookAheadPrefix(arc);
345  }
346 
347  void InitLookAheadFst(const Fst<Arc> &fst, bool copy = false) {
348  matcher_->InitLookAheadFst(fst, copy);
349  }
350 
351  private:
352  std::unique_ptr<M> matcher_;
353 };
354 
355 // Useful aliases when using StdArc.
356 
357 inline constexpr char arc_lookahead_fst_type[] = "arc_lookahead";
358 
359 using StdArcLookAheadFst =
362  arc_lookahead_fst_type>;
363 
364 inline constexpr char ilabel_lookahead_fst_type[] = "ilabel_lookahead";
365 inline constexpr char olabel_lookahead_fst_type[] = "olabel_lookahead";
366 
367 constexpr auto ilabel_lookahead_flags =
370 
371 constexpr auto olabel_lookahead_flags =
374 
380 
382  ConstFst<StdArc>,
383  LabelLookAheadMatcher<SortedMatcher<ConstFst<StdArc>>,
384  olabel_lookahead_flags, FastLogAccumulator<StdArc>>,
385  olabel_lookahead_fst_type, LabelLookAheadRelabeler<StdArc>>;
386 
387 } // namespace fst
388 
389 #endif // FST_MATCHER_FST_H_
static Impl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: expanded-fst.h:155
typename FstMatcher::MatcherData MatcherData
Definition: matcher-fst.h:101
void InitLookAheadFst(const Fst< Arc > &fst, bool copy=false)
Definition: matcher-fst.h:347
static std::shared_ptr< Impl > CreateDataAndImpl(const Fst< Arc > &fst, std::string_view name)
Definition: matcher-fst.h:201
typename M::MatcherData MatcherData
Definition: matcher-fst.h:81
LookAheadMatcher * Copy(bool safe=false) const
Definition: matcher-fst.h:309
MatcherFst * Copy(bool safe=false) const override
Definition: matcher-fst.h:131
const FST & GetFst() const
Definition: matcher-fst.h:168
constexpr char olabel_lookahead_fst_type[]
Definition: matcher-fst.h:365
const MatcherData * GetData(MatchType match_type) const
Definition: matcher-fst.h:176
MatchType
Definition: fst.h:187
constexpr char ilabel_lookahead_fst_type[]
Definition: matcher-fst.h:364
static MatcherFst * Read(std::istream &strm, const FstReadOptions &opts)
Definition: matcher-fst.h:136
std::shared_ptr< Data > GetSharedAddOn() const
Definition: matcher-fst.h:172
uint64_t Properties(uint64_t props) const
Definition: matcher-fst.h:282
LookAheadMatcher(const FST &fst, MatchType match_type)
Definition: matcher-fst.h:302
constexpr auto olabel_lookahead_flags
Definition: matcher-fst.h:371
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: matcher-fst.h:160
constexpr uint32_t kOutputLookAheadMatcher
constexpr uint32_t kLookAheadEpsilons
LookAheadMatcher(const LookAheadMatcher &matcher, bool safe=false)
Definition: matcher-fst.h:305
constexpr uint32_t kLookAheadNonEpsilonPrefix
MatcherFst(const Fst< Arc > &fst, std::shared_ptr< Data > data=nullptr)
Definition: matcher-fst.h:122
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: matcher-fst.h:156
constexpr auto ilabel_lookahead_flags
Definition: matcher-fst.h:367
MatcherFst(const FST &fst, std::shared_ptr< Data > data=nullptr)
Definition: matcher-fst.h:114
constexpr uint32_t kInputLookAheadMatcher
AddOnPair< MatcherData, MatcherData > Data
Definition: matcher-fst.h:82
typename Arc::StateId StateId
Definition: fst.h:518
constexpr uint32_t kLookAheadPrefix
MatcherFst(std::shared_ptr< Impl > impl)
Definition: matcher-fst.h:227
static std::shared_ptr< Impl > CreateImpl(const Fst< Arc > &fst, std::string_view name, std::shared_ptr< Data > data)
Definition: matcher-fst.h:218
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: matcher-fst.h:148
Matcher(const FST &fst, MatchType match_type)
Definition: matcher-fst.h:263
bool WriteFile(const std::string &source) const
Definition: fst.h:332
ArcIterator(const MatcherFst< FST, M, Name, Init > &fst, typename FST::Arc::StateId s)
Definition: matcher-fst.h:249
bool LookAheadFst(const Fst< Arc > &fst, StateId s)
Definition: matcher-fst.h:337
A Arc
Definition: fst.h:205
bool Write(const std::string &source) const override
Definition: matcher-fst.h:152
constexpr uint32_t kLookAheadWeight
StateIterator(const MatcherFst< FST, M, Name, Init > &fst)
Definition: matcher-fst.h:239
std::shared_ptr< MatcherData > GetSharedData(MatchType match_type) const
Definition: matcher-fst.h:181
NullMatcherFstInit(std::shared_ptr< Impl > *)
Definition: matcher-fst.h:85
const Data * GetAddOn() const
Definition: matcher-fst.h:170
MatcherFst(const MatcherFst &fst, bool safe=false)
Definition: matcher-fst.h:127
FstMatcher * InitMatcher(MatchType match_type) const override
Definition: matcher-fst.h:164
static std::shared_ptr< Impl > CreateImpl(const FST &fst, std::string_view name, std::shared_ptr< Data > data)
Definition: matcher-fst.h:208
typename Arc::StateId StateId
Definition: fst.h:206
static std::shared_ptr< Impl > CreateDataAndImpl(const FST &fst, std::string_view name)
Definition: matcher-fst.h:191
static MatcherFst * Read(std::string_view source)
Definition: matcher-fst.h:143
constexpr char arc_lookahead_fst_type[]
Definition: matcher-fst.h:357
static AddOnImpl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: add-on.h:171