FST  openfst-1.8.3
OpenFst Library
edit-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 // An FST implementation that allows non-destructive edit operations on an
19 // existing FST.
20 //
21 // The EditFst class enables non-destructive edit operations on a wrapped
22 // ExpandedFst. The implementation uses copy-on-write semantics at the node
23 // level: if a user has an underlying FST on which they want to perform a
24 // relatively small number of edits (read: mutations), then this implementation
25 // will copy the edited node to an internal MutableFst and perform any edits in
26 // situ on that copied node. This class supports all the methods of MutableFst
27 // except for DeleteStates(const std::vector<StateId> &); thus, new nodes may
28 // also be
29 // added, and one may add transitions from existing nodes of the wrapped FST to
30 // new nodes.
31 //
32 // N.B.: The documentation for Fst::Copy(true) says that its behavior is
33 // undefined if invoked on an FST that has already been accessed. This class
34 // requires that the Fst implementation it wraps provides consistent, reliable
35 // behavior when its Copy(true) method is invoked, where consistent means
36 // the graph structure, graph properties and state numbering and do not change.
37 // VectorFst and CompactFst, for example, are both well-behaved in this regard.
38 
39 #ifndef FST_EDIT_FST_H_
40 #define FST_EDIT_FST_H_
41 
42 #include <cstddef>
43 #include <cstdint>
44 #include <istream>
45 #include <memory>
46 #include <ostream>
47 #include <string>
48 #include <vector>
49 
50 #include <fst/log.h>
51 #include <fst/cache.h>
52 #include <fst/expanded-fst.h>
53 #include <fst/fst.h>
54 #include <fst/impl-to-fst.h>
55 #include <fst/mutable-fst.h>
56 #include <fst/properties.h>
57 #include <fst/util.h>
58 #include <fst/vector-fst.h>
59 #include <unordered_map>
60 #include <string_view>
61 
62 namespace fst {
63 namespace internal {
64 
65 // The EditFstData class is a container for all mutable data for EditFstImpl;
66 // also, this class provides most of the actual implementation of what EditFst
67 // does (that is, most of EditFstImpl's methods delegate to methods in this, the
68 // EditFstData class). Instances of this class are reference-counted and can be
69 // shared between otherwise independent EditFstImpl instances. This scheme
70 // allows EditFstImpl to implement the thread-safe, copy-on-write semantics
71 // required by Fst::Copy(true).
72 //
73 // template parameters:
74 // A: the type of arc to use
75 // WrappedFstT: the type of FST wrapped by the EditFst instance that
76 // this EditFstData instance is backing
77 // MutableFstT: the type of mutable FST to use internally for edited states;
78 // crucially, MutableFstT::Copy(false) *must* yield an FST that is
79 // thread-safe for reading (VectorFst, for example, has this property)
80 template <typename Arc, typename WrappedFstT = ExpandedFst<Arc>,
81  typename MutableFstT = VectorFst<Arc>>
82 class EditFstData {
83  public:
84  using StateId = typename Arc::StateId;
85  using Weight = typename Arc::Weight;
86 
87  EditFstData() : num_new_states_(0) {}
88 
89  EditFstData(const EditFstData &other)
90  : edits_(other.edits_),
91  external_to_internal_ids_(other.external_to_internal_ids_),
92  edited_final_weights_(other.edited_final_weights_),
93  num_new_states_(other.num_new_states_) {}
94 
95  ~EditFstData() = default;
96 
97  static EditFstData *Read(std::istream &strm, const FstReadOptions &opts);
98 
99  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
100  // Serializes all private data members of this class.
101  FstWriteOptions edits_opts(opts);
102  edits_opts.write_header = true; // Forces writing contained header.
103  edits_.Write(strm, edits_opts);
104  WriteType(strm, external_to_internal_ids_);
105  WriteType(strm, edited_final_weights_);
106  WriteType(strm, num_new_states_);
107  if (!strm) {
108  LOG(ERROR) << "EditFstData::Write: Write failed: " << opts.source;
109  return false;
110  }
111  return true;
112  }
113 
114  StateId NumNewStates() const { return num_new_states_; }
115 
116  // Accessor methods for the FST holding edited states.
117  StateId EditedStart() const { return edits_.Start(); }
118 
119  Weight Final(StateId s, const WrappedFstT *wrapped) const {
120  auto final_weight_it = GetFinalWeightIterator(s);
121  if (final_weight_it == NotInFinalWeightMap()) {
122  const auto it = GetEditedIdMapIterator(s);
123  return it == NotInEditedMap() ? wrapped->Final(s)
124  : edits_.Final(it->second);
125  } else {
126  return final_weight_it->second;
127  }
128  }
129 
130  size_t NumArcs(StateId s, const WrappedFstT *wrapped) const {
131  const auto it = GetEditedIdMapIterator(s);
132  return it == NotInEditedMap() ? wrapped->NumArcs(s)
133  : edits_.NumArcs(it->second);
134  }
135 
136  size_t NumInputEpsilons(StateId s, const WrappedFstT *wrapped) const {
137  const auto it = GetEditedIdMapIterator(s);
138  return it == NotInEditedMap() ? wrapped->NumInputEpsilons(s)
139  : edits_.NumInputEpsilons(it->second);
140  }
141 
142  size_t NumOutputEpsilons(StateId s, const WrappedFstT *wrapped) const {
143  const auto it = GetEditedIdMapIterator(s);
144  return it == NotInEditedMap() ? wrapped->NumOutputEpsilons(s)
145  : edits_.NumOutputEpsilons(it->second);
146  }
147 
148  void SetEditedProperties(uint64_t props, uint64_t mask) {
149  edits_.SetProperties(props, mask);
150  }
151 
152  // Non-const MutableFst operations.
153 
154  // Sets the start state for this FST.
155  void SetStart(StateId s) { edits_.SetStart(s); }
156 
157  // Sets the final state for this FST.
158  Weight SetFinal(StateId s, Weight weight, const WrappedFstT *wrapped) {
159  const auto old_weight = Final(s, wrapped);
160  const auto it = GetEditedIdMapIterator(s);
161  // If we haven't already edited state s, don't add it to edited_ (which can
162  // be expensive if s has many transitions); just use the
163  // edited_final_weights_ map.
164  if (it == NotInEditedMap()) {
165  edited_final_weights_[s] = weight;
166  } else {
167  edits_.SetFinal(GetEditableInternalId(s, wrapped), weight);
168  }
169  return old_weight;
170  }
171 
172  // Adds a new state to this FST.
173  StateId AddState(StateId curr_num_states) {
174  external_to_internal_ids_[curr_num_states] = edits_.AddState();
175  ++num_new_states_;
176  return curr_num_states;
177  }
178 
179  // Adds new states to this FST.
180  void AddStates(StateId curr_num_states, size_t n) {
181  for (size_t i = 0; i < n; ++i) {
182  curr_num_states = AddState(curr_num_states);
183  }
184  }
185 
186  // Adds the specified arc to the specified state of this FST.
187  const Arc *AddArc(StateId s, const Arc &arc, const WrappedFstT *wrapped) {
188  const auto internal_id = GetEditableInternalId(s, wrapped);
189  const auto num_arcs = edits_.NumArcs(internal_id);
190  ArcIterator<MutableFstT> arc_it(edits_, internal_id);
191  const Arc *prev_arc = nullptr;
192  if (num_arcs > 0) {
193  // Grabs the final arc associated with this state in edits_.
194  arc_it.Seek(num_arcs - 1);
195  prev_arc = &(arc_it.Value());
196  }
197  edits_.AddArc(internal_id, arc);
198  return prev_arc;
199  }
200 
201  void DeleteStates() {
202  edits_.DeleteStates();
203  num_new_states_ = 0;
204  external_to_internal_ids_.clear();
205  edited_final_weights_.clear();
206  }
207 
208  // Removes all but the first n outgoing arcs of the specified state.
209  void DeleteArcs(StateId s, size_t n, const WrappedFstT *wrapped) {
210  edits_.DeleteArcs(GetEditableInternalId(s, wrapped), n);
211  }
212 
213  // Removes all outgoing arcs from the specified state.
214  void DeleteArcs(StateId s, const WrappedFstT *wrapped) {
215  edits_.DeleteArcs(GetEditableInternalId(s, wrapped));
216  }
217 
218  // End methods for non-const MutableFst operations.
219 
220  // Provides information for the generic arc iterator.
222  const WrappedFstT *wrapped) const {
223  const auto it = GetEditedIdMapIterator(s);
224  if (it == NotInEditedMap()) {
225  VLOG(3) << "EditFstData::InitArcIterator: iterating on state " << s
226  << " of original FST";
227  wrapped->InitArcIterator(s, data);
228  } else {
229  VLOG(2) << "EditFstData::InitArcIterator: iterating on edited state " << s
230  << " (internal state ID: " << it->second << ")";
231  edits_.InitArcIterator(it->second, data);
232  }
233  }
234 
235  // Provides information for the generic mutable arc iterator.
237  const WrappedFstT *wrapped) {
238  data->base = std::make_unique<MutableArcIterator<MutableFstT>>(
239  &edits_, GetEditableInternalId(s, wrapped));
240  }
241 
242  // Prints out the map from external to internal state IDs (for debugging
243  // purposes).
244  void PrintMap() {
245  for (auto it = external_to_internal_ids_.begin(); it != NotInEditedMap();
246  ++it) {
247  LOG(INFO) << "(external,internal)=(" << it->first << "," << it->second
248  << ")";
249  }
250  }
251 
252  private:
253  // Returns the iterator of the map from external to internal state IDs
254  // of edits_ for the specified external state IDs.
255  typename std::unordered_map<StateId, StateId>::const_iterator
256  GetEditedIdMapIterator(StateId s) const {
257  return external_to_internal_ids_.find(s);
258  }
259 
260  typename std::unordered_map<StateId, StateId>::const_iterator
261  NotInEditedMap() const {
262  return external_to_internal_ids_.end();
263  }
264 
265  typename std::unordered_map<StateId, Weight>::const_iterator
266  GetFinalWeightIterator(StateId s) const {
267  return edited_final_weights_.find(s);
268  }
269 
270  typename std::unordered_map<StateId, Weight>::const_iterator
271  NotInFinalWeightMap() const {
272  return edited_final_weights_.end();
273  }
274 
275  // Returns the internal state ID of the specified external ID if the state has
276  // already been made editable, or else copies the state from wrapped_ to
277  // edits_ and returns the state ID of the newly editable state in edits_.
278  StateId GetEditableInternalId(StateId s, const WrappedFstT *wrapped) {
279  auto id_map_it = GetEditedIdMapIterator(s);
280  if (id_map_it == NotInEditedMap()) {
281  StateId new_internal_id = edits_.AddState();
282  VLOG(2) << "EditFstData::GetEditableInternalId: editing state " << s
283  << " of original FST; new internal state id:" << new_internal_id;
284  external_to_internal_ids_[s] = new_internal_id;
285  for (ArcIterator<Fst<Arc>> arc_iterator(*wrapped, s);
286  !arc_iterator.Done(); arc_iterator.Next()) {
287  edits_.AddArc(new_internal_id, arc_iterator.Value());
288  }
289  // Copies the final weight.
290  auto final_weight_it = GetFinalWeightIterator(s);
291  if (final_weight_it == NotInFinalWeightMap()) {
292  edits_.SetFinal(new_internal_id, wrapped->Final(s));
293  } else {
294  edits_.SetFinal(new_internal_id, final_weight_it->second);
295  edited_final_weights_.erase(s);
296  }
297  return new_internal_id;
298  } else {
299  return id_map_it->second;
300  }
301  }
302 
303  // A mutable FST (by default, a VectorFst) to contain new states, and/or
304  // copies of states from a wrapped ExpandedFst that have been modified in
305  // some way.
306  MutableFstT edits_;
307  // A mapping from external state IDs to the internal IDs of states that
308  // appear in edits_.
309  std::unordered_map<StateId, StateId> external_to_internal_ids_;
310  // A mapping from external state IDs to final state weights assigned to
311  // those states. The states in this map are *only* those whose final weight
312  // has been modified; if any other part of the state has been modified,
313  // the entire state is copied to edits_, and all modifications reside there.
314  std::unordered_map<StateId, Weight> edited_final_weights_;
315  // The number of new states added to this mutable FST impl, which is <= the
316  // number of states in edits_ (since edits_ contains both edited *and* new
317  // states).
318  StateId num_new_states_;
319 };
320 
321 // EditFstData method implementations: just the Read method.
322 template <typename A, typename WrappedFstT, typename MutableFstT>
325  const FstReadOptions &opts) {
326  auto data = fst::make_unique_for_overwrite<EditFstData>();
327  // Next read in MutabelFstT machine that stores edits
328  FstReadOptions edits_opts(opts);
329  // Contained header was written out, so read it in.
330  edits_opts.header = nullptr;
331  // Because our internal representation of edited states is a solid object
332  // of type MutableFstT (defaults to VectorFst<A>) and not a pointer,
333  // and because the static Read method allocates a new object on the heap,
334  // we need to call Read, check if there was a failure, use
335  // MutableFstT::operator= to assign the object (not the pointer) to the
336  // edits_ data member (which will increase the ref count by 1 on the impl)
337  // and, finally, delete the heap-allocated object.
338  std::unique_ptr<MutableFstT> edits(MutableFstT::Read(strm, edits_opts));
339  if (!edits) return nullptr;
340  data->edits_ = *edits;
341  edits.reset();
342  // Finally, reads in rest of private data members.
343  ReadType(strm, &data->external_to_internal_ids_);
344  ReadType(strm, &data->edited_final_weights_);
345  ReadType(strm, &data->num_new_states_);
346  if (!strm) {
347  LOG(ERROR) << "EditFst::Read: read failed: " << opts.source;
348  return nullptr;
349  }
350  return data.release();
351 }
352 
353 // This class enables non-destructive edit operations on a wrapped ExpandedFst.
354 // The implementation uses copy-on-write semantics at the node level: if a user
355 // has an underlying FST on which they want to perform a relatively small
356 // number of edits (read: mutations), then this implementation will copy the
357 // edited node to an internal MutableFst and perform any edits in situ on that
358 // copied node. This class supports all the methods of MutableFst except for
359 // DeleteStates(const std::vector<StateId> &); thus, new nodes may also be
360 // added, and
361 // one may add transitions from existing nodes of the wrapped FST to new nodes.
362 //
363 // template parameters:
364 // A: the type of arc to use
365 // WrappedFstT: the type of FST wrapped by the EditFst instance that
366 // this EditFstImpl instance is backing
367 // MutableFstT: the type of mutable FST to use internally for edited states;
368 // crucially, MutableFstT::Copy(false) must yield an FST that is
369 // thread-safe for reading (VectorFst, for example, has this property)
370 template <typename A, typename WrappedFstT = ExpandedFst<A>,
371  typename MutableFstT = VectorFst<A>>
372 class EditFstImpl : public FstImpl<A> {
373  public:
374  using Arc = A;
375  using StateId = typename Arc::StateId;
376  using Weight = typename Arc::Weight;
377 
382 
383  // Constructs an editable FST implementation with no states. Effectively, this
384  // initially-empty FST will in every way mimic the behavior of a
385  // VectorFst---more precisely, a VectorFstImpl instance---but with slightly
386  // slower performance (by a constant factor), due to the fact that
387  // this class maintains a mapping between external state id's and
388  // their internal equivalents.
389  EditFstImpl() : wrapped_(new MutableFstT()) {
390  FstImpl<Arc>::SetType("edit");
391  InheritPropertiesFromWrapped();
392  data_ = std::make_shared<EditFstData<Arc, WrappedFstT, MutableFstT>>();
393  }
394 
395  // Wraps the specified ExpandedFst. This constructor requires that the
396  // specified Fst is an ExpandedFst instance. This requirement is only enforced
397  // at runtime. (See below for the reason.)
398  //
399  // This library uses the pointer-to-implementation or "PIMPL" design pattern.
400  // In particular, to make it convenient to bind an implementation class to its
401  // interface, there are a pair of template "binder" classes, one for immutable
402  // and one for mutable FSTs (ImplToFst and ImplToMutableFst, respectively).
403  // As it happens, the API for the ImplToMutableFst<I,F> class requires that
404  // the implementation class--the template parameter "I"--have a constructor
405  // taking a const Fst<A> reference. Accordingly, the constructor here must
406  // perform a down_cast to the WrappedFstT type required by EditFst and
407  // therefore EditFstImpl.
408  explicit EditFstImpl(const Fst<Arc> &wrapped)
409  : wrapped_(down_cast<WrappedFstT *>(wrapped.Copy())) {
410  FstImpl<Arc>::SetType("edit");
411  data_ = std::make_shared<EditFstData<Arc, WrappedFstT, MutableFstT>>();
412  // have edits_ inherit all properties from wrapped_
413  data_->SetEditedProperties(wrapped_->Properties(kFstProperties, false),
415  InheritPropertiesFromWrapped();
416  }
417 
418  // A copy constructor for this implementation class, used to implement
419  // the Copy() method of the Fst interface.
421  : FstImpl<Arc>(),
422  wrapped_(down_cast<WrappedFstT *>(impl.wrapped_->Copy(true))),
423  data_(impl.data_) {
424  SetProperties(impl.Properties());
425  }
426 
427  // const Fst/ExpandedFst operations, declared in the Fst and ExpandedFst
428  // interfaces
429  StateId Start() const {
430  const auto edited_start = data_->EditedStart();
431  return edited_start == kNoStateId ? wrapped_->Start() : edited_start;
432  }
433 
434  Weight Final(StateId s) const { return data_->Final(s, wrapped_.get()); }
435 
436  size_t NumArcs(StateId s) const { return data_->NumArcs(s, wrapped_.get()); }
437 
438  size_t NumInputEpsilons(StateId s) const {
439  return data_->NumInputEpsilons(s, wrapped_.get());
440  }
441 
442  size_t NumOutputEpsilons(StateId s) const {
443  return data_->NumOutputEpsilons(s, wrapped_.get());
444  }
445 
446  StateId NumStates() const {
447  return wrapped_->NumStates() + data_->NumNewStates();
448  }
449 
450  static EditFstImpl *Read(std::istream &strm, const FstReadOptions &opts);
451 
452  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
453  FstHeader hdr;
454  hdr.SetStart(Start());
455  hdr.SetNumStates(NumStates());
456  FstWriteOptions header_opts(opts);
457  // Allows the contained FST to hold any symbols.
458  header_opts.write_isymbols = false;
459  header_opts.write_osymbols = false;
460  WriteHeader(strm, header_opts, kFileVersion, &hdr);
461  // Serializes the wrapped FST to stream.
462  FstWriteOptions wrapped_opts(opts);
463  // Forces writing the contained header.
464  wrapped_opts.write_header = true;
465  wrapped_->Write(strm, wrapped_opts);
466  data_->Write(strm, opts);
467  strm.flush();
468  if (!strm) {
469  LOG(ERROR) << "EditFst::Write: Write failed: " << opts.source;
470  return false;
471  }
472  return true;
473  }
474 
475  // Sets the start state for this FST.
476  void SetStart(StateId s) {
477  MutateCheck();
478  data_->SetStart(s);
480  }
481 
482  // Sets the final state for this FST.
483  void SetFinal(StateId s, Weight weight) {
484  MutateCheck();
485  Weight old_weight = data_->SetFinal(s, weight, wrapped_.get());
486  SetProperties(
487  SetFinalProperties(FstImpl<Arc>::Properties(), old_weight, weight));
488  }
489 
490  // Adds a new state to this FST.
492  MutateCheck();
494  return data_->AddState(NumStates());
495  }
496 
497  // Adds new states to this FST.
498  void AddStates(size_t n) {
499  MutateCheck();
501  return data_->AddStates(NumStates(), n);
502  }
503 
504  // Adds the specified arc to the specified state of this FST.
505  void AddArc(StateId s, const Arc &arc) {
506  MutateCheck();
507  const auto *prev_arc = data_->AddArc(s, arc, wrapped_.get());
508  SetProperties(
509  AddArcProperties(FstImpl<Arc>::Properties(), s, arc, prev_arc));
510  }
511 
512  void DeleteStates(const std::vector<StateId> &dstates) {
513  FSTERROR() << ": EditFstImpl::DeleteStates(const std::vector<StateId>&): "
514  << " not implemented";
515  SetProperties(kError, kError);
516  }
517 
518  // Deletes all states in this FST.
519  void DeleteStates();
520 
521  // Removes all but the first n outgoing arcs of the specified state.
522  void DeleteArcs(StateId s, size_t n) {
523  MutateCheck();
524  data_->DeleteArcs(s, n, wrapped_.get());
526  }
527 
528  // Removes all outgoing arcs from the specified state.
529  void DeleteArcs(StateId s) {
530  MutateCheck();
531  data_->DeleteArcs(s, wrapped_.get());
533  }
534 
536 
537  void ReserveArcs(StateId s, size_t n) {}
538 
539  // Ends non-const MutableFst operations.
540 
541  // Provides information for the generic state iterator.
543  data->base = nullptr;
544  data->nstates = NumStates();
545  }
546 
547  // Provides information for the generic arc iterator.
549  data_->InitArcIterator(s, data, wrapped_.get());
550  }
551 
552  // Provides information for the generic mutable arc iterator.
554  MutateCheck();
555  data_->InitMutableArcIterator(s, data, wrapped_.get());
556  }
557 
558  private:
559  // Properties always true of this FST class.
560  static constexpr uint64_t kStaticProperties = kExpanded | kMutable;
561  // Current file format version.
562  static constexpr int kFileVersion = 2;
563  // Minimum file format version supported
564  static constexpr int kMinFileVersion = 2;
565 
566  // Causes this FST to inherit all the properties from its wrapped FST, except
567  // for the two properties that always apply to EditFst instances: kExpanded
568  // and kMutable.
569  void InheritPropertiesFromWrapped() {
570  SetProperties(wrapped_->Properties(kCopyProperties, false) |
571  kStaticProperties);
572  SetInputSymbols(wrapped_->InputSymbols());
573  SetOutputSymbols(wrapped_->OutputSymbols());
574  }
575 
576  // This method ensures that any operations that alter the mutable data
577  // portion of this EditFstImpl cause the data_ member to be copied when its
578  // reference count is greater than 1. Note that this method is distinct from
579  // MutableFst::Mutate, which gets invoked whenever one of the basic mutation
580  // methods defined in MutableFst is invoked, such as SetInputSymbols.
581  // The MutateCheck here in EditFstImpl is invoked whenever one of the
582  // mutating methods specifically related to the types of edits provided
583  // by EditFst is performed, such as changing an arc of an existing state
584  // of the wrapped FST via a MutableArcIterator, or adding a new state via
585  // AddState().
586  void MutateCheck() {
587  if (!data_.unique()) {
588  data_ =
589  std::make_shared<EditFstData<Arc, WrappedFstT, MutableFstT>>(*data_);
590  }
591  }
592 
593  // The FST that this FST wraps. The purpose of this class is to enable
594  // non-destructive edits on this wrapped FST.
595  std::unique_ptr<const WrappedFstT> wrapped_;
596  // The mutable data for this EditFst instance, with delegates for all the
597  // methods that can mutate data.
598  std::shared_ptr<EditFstData<Arc, WrappedFstT, MutableFstT>> data_;
599 };
600 
601 template <typename Arc, typename WrappedFstT, typename MutableFstT>
603  data_->DeleteStates();
604  // we are deleting all states, so just forget about pointer to wrapped_
605  // and do what default constructor does: set wrapped_ to a new VectorFst
606  wrapped_ = std::make_unique<MutableFstT>();
607  const auto new_props =
609  FstImpl<Arc>::SetProperties(new_props);
610 }
611 
612 template <typename Arc, typename WrappedFstT, typename MutableFstT>
615  const FstReadOptions &opts) {
616  auto impl = std::make_unique<EditFstImpl>();
617  FstHeader hdr;
618  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) return nullptr;
619  impl->SetStart(hdr.Start());
620  // Reads in wrapped FST.
621  FstReadOptions wrapped_opts(opts);
622  // Contained header was written out, so reads it in too.
623  wrapped_opts.header = nullptr;
624  std::unique_ptr<Fst<Arc>> wrapped_fst(Fst<Arc>::Read(strm, wrapped_opts));
625  if (!wrapped_fst) return nullptr;
626  impl->wrapped_.reset(down_cast<WrappedFstT *>(wrapped_fst.release()));
627  impl->data_ = std::shared_ptr<EditFstData<Arc, WrappedFstT, MutableFstT>>(
629  if (!impl->data_) return nullptr;
630  return impl.release();
631 }
632 
633 } // namespace internal
634 
635 // Concrete, editable FST. This class attaches interface to implementation.
636 //
637 // EditFst is thread-compatible.
638 template <typename A, typename WrappedFstT = ExpandedFst<A>,
639  typename MutableFstT = VectorFst<A>>
640 class EditFst : public ImplToMutableFst<
641  internal::EditFstImpl<A, WrappedFstT, MutableFstT>> {
642  public:
643  using Arc = A;
644  using StateId = typename Arc::StateId;
645 
647 
648  friend class MutableArcIterator<EditFst<Arc, WrappedFstT, MutableFstT>>;
649 
650  EditFst() : ImplToMutableFst<Impl>(std::make_shared<Impl>()) {}
651 
652  explicit EditFst(const Fst<Arc> &fst)
653  : ImplToMutableFst<Impl>(std::make_shared<Impl>(fst)) {}
654 
655  explicit EditFst(const WrappedFstT &fst)
656  : ImplToMutableFst<Impl>(std::make_shared<Impl>(fst)) {}
657 
658  // See Fst<>::Copy() for doc.
659  EditFst(const EditFst &fst, bool safe = false)
660  : ImplToMutableFst<Impl>(fst, safe) {}
661 
662  ~EditFst() override = default;
663 
664  // Gets a copy of this EditFst. See Fst<>::Copy() for further doc.
665  EditFst *Copy(bool safe = false) const override {
666  return new EditFst(*this, safe);
667  }
668 
670  SetImpl(fst.GetSharedImpl());
671  return *this;
672  }
673 
674  EditFst &operator=(const Fst<Arc> &fst) override {
675  SetImpl(std::make_shared<Impl>(fst));
676  return *this;
677  }
678 
679  // Reads an EditFst from an input stream, returning nullptr on error.
680  static EditFst *Read(std::istream &strm, const FstReadOptions &opts) {
681  auto *impl = Impl::Read(strm, opts);
682  return impl ? new EditFst(std::shared_ptr<Impl>(impl)) : nullptr;
683  }
684 
685  // Reads an EditFst from a file, returning nullptr on error. If the source
686  // argument is an empty string, it reads from standard input.
687  static EditFst *Read(std::string_view source) {
688  auto *impl = ImplToExpandedFst<Impl, MutableFst<Arc>>::Read(source);
689  return impl ? new EditFst(std::shared_ptr<Impl>(impl)) : nullptr;
690  }
691 
692  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
693  return GetImpl()->Write(strm, opts);
694  }
695 
696  bool Write(const std::string &source) const override {
697  return Fst<Arc>::WriteFile(source);
698  }
699 
700  void InitStateIterator(StateIteratorData<Arc> *data) const override {
701  GetImpl()->InitStateIterator(data);
702  }
703 
704  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
705  GetImpl()->InitArcIterator(s, data);
706  }
707 
709  MutableArcIteratorData<A> *data) override {
710  GetMutableImpl()->InitMutableArcIterator(s, data);
711  }
712 
713  private:
714  explicit EditFst(std::shared_ptr<Impl> impl) : ImplToMutableFst<Impl>(impl) {}
715 
716  using ImplToFst<Impl, MutableFst<Arc>>::GetImpl;
717  using ImplToFst<Impl, MutableFst<Arc>>::GetMutableImpl;
718  using ImplToFst<Impl, MutableFst<Arc>>::SetImpl;
719 };
720 
721 } // namespace fst
722 
723 #endif // FST_EDIT_FST_H_
EditFst * Copy(bool safe=false) const override
Definition: edit-fst.h:665
static EditFst * Read(std::istream &strm, const FstReadOptions &opts)
Definition: edit-fst.h:680
void SetStart(StateId s)
Definition: edit-fst.h:476
void ReserveArcs(StateId s, size_t n)
Definition: edit-fst.h:537
uint64_t AddArcProperties(uint64_t inprops, typename A::StateId s, const A &arc, const A *prev_arc)
void SetProperties(uint64_t props)
Definition: fst.h:709
constexpr uint64_t kMutable
Definition: properties.h:49
static EditFst * Read(std::string_view source)
Definition: edit-fst.h:687
void InitMutableArcIterator(StateId s, MutableArcIteratorData< Arc > *data, const WrappedFstT *wrapped)
Definition: edit-fst.h:236
typename Arc::Weight Weight
Definition: edit-fst.h:376
Weight SetFinal(StateId s, Weight weight, const WrappedFstT *wrapped)
Definition: edit-fst.h:158
const FstHeader * header
Definition: fst.h:74
uint64_t SetStartProperties(uint64_t inprops)
Definition: properties.h:396
bool Write(const std::string &source) const override
Definition: edit-fst.h:696
void AddArc(StateId s, const Arc &arc)
Definition: edit-fst.h:505
std::unique_ptr< MutableArcIteratorBase< Arc > > base
Definition: mutable-fst.h:206
std::shared_ptr< Impl > GetSharedImpl() const
Definition: impl-to-fst.h:128
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const
Definition: edit-fst.h:548
StateId NumStates() const
Definition: edit-fst.h:446
size_t NumInputEpsilons(StateId s, const WrappedFstT *wrapped) const
Definition: edit-fst.h:136
StateId AddState(StateId curr_num_states)
Definition: edit-fst.h:173
std::string source
Definition: fst.h:73
uint64_t AddStateProperties(uint64_t inprops)
Definition: properties.h:404
StateId Start() const
Definition: edit-fst.h:429
uint64_t DeleteAllStatesProperties(uint64_t inprops, uint64_t staticProps)
Definition: properties.h:412
constexpr uint64_t kError
Definition: properties.h:52
#define LOG(type)
Definition: log.h:53
size_t NumArcs(StateId s, const WrappedFstT *wrapped) const
Definition: edit-fst.h:130
EditFstImpl(const Fst< Arc > &wrapped)
Definition: edit-fst.h:408
void DeleteArcs(StateId s)
Definition: edit-fst.h:529
void SetStart(StateId s)
Definition: edit-fst.h:155
StateId NumNewStates() const
Definition: edit-fst.h:114
static EditFstData * Read(std::istream &strm, const FstReadOptions &opts)
Definition: edit-fst.h:324
void SetEditedProperties(uint64_t props, uint64_t mask)
Definition: edit-fst.h:148
To down_cast(From *f)
Definition: compat.h:50
uint64_t SetFinalProperties(uint64_t inprops, const Weight &old_weight, const Weight &new_weight)
Definition: properties.h:424
typename Arc::StateId StateId
Definition: edit-fst.h:644
constexpr int kNoStateId
Definition: fst.h:196
void DeleteStates(const std::vector< StateId > &dstates)
Definition: edit-fst.h:512
EditFst(const WrappedFstT &fst)
Definition: edit-fst.h:655
const Arc & Value() const
Definition: fst.h:536
typename Arc::StateId StateId
Definition: edit-fst.h:375
std::ostream & WriteType(std::ostream &strm, const T t)
Definition: util.h:228
std::string source
Definition: fst.h:102
#define FSTERROR()
Definition: util.h:56
void AddStates(StateId curr_num_states, size_t n)
Definition: edit-fst.h:180
void DeleteArcs(StateId s, size_t n, const WrappedFstT *wrapped)
Definition: edit-fst.h:209
static EditFstImpl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: edit-fst.h:614
bool write_osymbols
Definition: fst.h:105
typename Arc::Weight Weight
Definition: edit-fst.h:85
virtual uint64_t Properties() const
Definition: fst.h:701
void Seek(size_t a)
Definition: fst.h:556
constexpr uint64_t kCopyProperties
Definition: properties.h:163
Weight Final(StateId s, const WrappedFstT *wrapped) const
Definition: edit-fst.h:119
void DeleteArcs(StateId s, size_t n)
Definition: edit-fst.h:522
bool write_isymbols
Definition: fst.h:104
StateId EditedStart() const
Definition: edit-fst.h:117
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data, const WrappedFstT *wrapped) const
Definition: edit-fst.h:221
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: edit-fst.h:704
StateId nstates
Definition: fst.h:384
EditFst(const Fst< Arc > &fst)
Definition: edit-fst.h:652
#define VLOG(level)
Definition: log.h:54
size_t NumInputEpsilons(StateId s) const
Definition: edit-fst.h:438
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
size_t NumOutputEpsilons(StateId s, const WrappedFstT *wrapped) const
Definition: edit-fst.h:142
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: edit-fst.h:692
EditFstImpl(const EditFstImpl &impl)
Definition: edit-fst.h:420
void AddStates(size_t n)
Definition: edit-fst.h:498
bool write_header
Definition: fst.h:103
EditFstData(const EditFstData &other)
Definition: edit-fst.h:89
bool WriteFile(const std::string &source) const
Definition: fst.h:332
void ReserveStates(StateId s)
Definition: edit-fst.h:535
constexpr uint64_t kFstProperties
Definition: properties.h:326
void SetNumStates(int64_t numstates)
Definition: fst.h:164
Weight Final(StateId s) const
Definition: edit-fst.h:434
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: edit-fst.h:700
void SetType(std::string_view type)
Definition: fst.h:699
const Arc * AddArc(StateId s, const Arc &arc, const WrappedFstT *wrapped)
Definition: edit-fst.h:187
void SetStart(int64_t start)
Definition: fst.h:162
void SetFinal(StateId s, Weight weight)
Definition: edit-fst.h:483
EditFst & operator=(const Fst< Arc > &fst) override
Definition: edit-fst.h:674
std::istream & ReadType(std::istream &strm, T *t)
Definition: util.h:80
uint64_t DeleteArcsProperties(uint64_t inprops)
Definition: properties.h:417
void InitMutableArcIterator(StateId s, MutableArcIteratorData< Arc > *data)
Definition: edit-fst.h:553
typename Arc::StateId StateId
Definition: edit-fst.h:84
size_t NumArcs(StateId s) const
Definition: edit-fst.h:436
EditFst(const EditFst &fst, bool safe=false)
Definition: edit-fst.h:659
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: edit-fst.h:99
size_t NumOutputEpsilons(StateId s) const
Definition: edit-fst.h:442
void InitMutableArcIterator(StateId s, MutableArcIteratorData< A > *data) override
Definition: edit-fst.h:708
void InitStateIterator(StateIteratorData< Arc > *data) const
Definition: edit-fst.h:542
constexpr uint64_t kExpanded
Definition: properties.h:46
void DeleteArcs(StateId s, const WrappedFstT *wrapped)
Definition: edit-fst.h:214
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: edit-fst.h:452
EditFst & operator=(const EditFst &fst)
Definition: edit-fst.h:669