FST  openfst-1.8.2
OpenFst Library
vector-fst.h
Go to the documentation of this file.
1 // Copyright 2005-2020 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 // Simple concrete, mutable FST whose states and arcs are stored in STL vectors.
19 
20 #ifndef FST_VECTOR_FST_H_
21 #define FST_VECTOR_FST_H_
22 
23 #include <algorithm>
24 #include <atomic>
25 #include <cstdint>
26 #include <memory>
27 #include <string>
28 #include <utility>
29 #include <vector>
30 
31 #include <fst/log.h>
32 
33 #include <fst/fst-decl.h> // For optional argument declarations
34 #include <fst/mutable-fst.h>
35 #include <fst/test-properties.h>
36 
37 namespace fst {
38 
39 template <class A, class S>
40 class VectorFst;
41 
42 template <class F, class G>
43 void Cast(const F &, G *);
44 
45 // Arcs (of type A) implemented by an STL vector per state. M specifies Arc
46 // allocator (default declared in fst-decl.h).
47 template <class A, class M /* = std::allocator<A> */>
48 class VectorState {
49  public:
50  using Arc = A;
51  using StateId = typename Arc::StateId;
52  using Weight = typename Arc::Weight;
53  using ArcAllocator = M;
54  using StateAllocator = typename std::allocator_traits<
55  ArcAllocator>::template rebind_alloc<VectorState<Arc, M>>;
56 
57  // Provide STL allocator for arcs.
58  explicit VectorState(const ArcAllocator &alloc)
59  : final_weight_(Weight::Zero()),
60  niepsilons_(0),
61  noepsilons_(0),
62  arcs_(alloc) {}
63 
64  VectorState(const VectorState<A, M> &state, const ArcAllocator &alloc)
65  : final_weight_(state.Final()),
66  niepsilons_(state.NumInputEpsilons()),
67  noepsilons_(state.NumOutputEpsilons()),
68  arcs_(state.arcs_.begin(), state.arcs_.end(), alloc) {}
69 
70  void Reset() {
71  final_weight_ = Weight::Zero();
72  niepsilons_ = 0;
73  noepsilons_ = 0;
74  arcs_.clear();
75  }
76 
77  Weight Final() const { return final_weight_; }
78 
79  size_t NumInputEpsilons() const { return niepsilons_; }
80 
81  size_t NumOutputEpsilons() const { return noepsilons_; }
82 
83  size_t NumArcs() const { return arcs_.size(); }
84 
85  const Arc &GetArc(size_t n) const { return arcs_[n]; }
86 
87  const Arc *Arcs() const { return !arcs_.empty() ? &arcs_[0] : nullptr; }
88 
89  Arc *MutableArcs() { return !arcs_.empty() ? &arcs_[0] : nullptr; }
90 
91  void ReserveArcs(size_t n) { arcs_.reserve(n); }
92 
93  void SetFinal(Weight weight) { final_weight_ = std::move(weight); }
94 
95  void SetNumInputEpsilons(size_t n) { niepsilons_ = n; }
96 
97  void SetNumOutputEpsilons(size_t n) { noepsilons_ = n; }
98 
99  void AddArc(const Arc &arc) {
100  IncrementNumEpsilons(arc);
101  arcs_.push_back(arc);
102  }
103 
104  void AddArc(Arc &&arc) {
105  IncrementNumEpsilons(arc);
106  arcs_.push_back(std::move(arc));
107  }
108 
109  template <class... T>
110  void EmplaceArc(T &&... ctor_args) {
111  arcs_.emplace_back(std::forward<T>(ctor_args)...);
112  IncrementNumEpsilons(arcs_.back());
113  }
114 
115  void SetArc(const Arc &arc, size_t n) {
116  if (arcs_[n].ilabel == 0) --niepsilons_;
117  if (arcs_[n].olabel == 0) --noepsilons_;
118  IncrementNumEpsilons(arc);
119  arcs_[n] = arc;
120  }
121 
122  void DeleteArcs() {
123  niepsilons_ = 0;
124  noepsilons_ = 0;
125  arcs_.clear();
126  }
127 
128  void DeleteArcs(size_t n) {
129  for (size_t i = 0; i < n; ++i) {
130  if (arcs_.back().ilabel == 0) --niepsilons_;
131  if (arcs_.back().olabel == 0) --noepsilons_;
132  arcs_.pop_back();
133  }
134  }
135 
136  // For state class allocation.
137  void *operator new(size_t size, StateAllocator *alloc) {
138  return alloc->allocate(1);
139  }
140 
141  // For state destruction and memory freeing.
142  static void Destroy(VectorState<A, M> *state, StateAllocator *alloc) {
143  if (state) {
144  state->~VectorState<A, M>();
145  alloc->deallocate(state, 1);
146  }
147  }
148 
149  private:
150  // Update the number of epsilons as a result of having added an arc.
151  void IncrementNumEpsilons(const Arc &arc) {
152  if (arc.ilabel == 0) ++niepsilons_;
153  if (arc.olabel == 0) ++noepsilons_;
154  }
155 
156  Weight final_weight_; // Final weight.
157  size_t niepsilons_; // # of input epsilons
158  size_t noepsilons_; // # of output epsilons
159  std::vector<A, ArcAllocator> arcs_; // Arc container.
160 };
161 
162 namespace internal {
163 
164 // States are implemented by STL vectors, templated on the
165 // State definition. This does not manage the Fst properties.
166 template <class S>
167 class VectorFstBaseImpl : public FstImpl<typename S::Arc> {
168  public:
169  using State = S;
170  using Arc = typename State::Arc;
171  using StateId = typename Arc::StateId;
172  using Weight = typename Arc::Weight;
173 
175 
176  ~VectorFstBaseImpl() override {
177  for (auto *state : states_) State::Destroy(state, &state_alloc_);
178  }
179 
180  // Copying is not permitted.
181  VectorFstBaseImpl(const VectorFstBaseImpl<S> &) = delete;
182  VectorFstBaseImpl &operator=(const VectorFstBaseImpl &) = delete;
183 
184  // Moving is permitted.
186  : FstImpl<typename S::Arc>(),
187  states_(std::move(impl.states_)),
188  start_(impl.start_) {
189  impl.states_.clear();
190  impl.start_ = kNoStateId;
191  }
192 
194  for (auto *state : states_) {
195  State::Destroy(state, &state_alloc_);
196  }
197  states_.clear();
198  std::swap(states_, impl.states_);
199  start_ = impl.start_;
200  impl.start_ = kNoStateId;
201  return *this;
202  }
203 
204  StateId Start() const { return start_; }
205 
206  Weight Final(StateId state) const { return states_[state]->Final(); }
207 
208  StateId NumStates() const { return states_.size(); }
209 
210  size_t NumArcs(StateId state) const { return states_[state]->NumArcs(); }
211 
212  size_t NumInputEpsilons(StateId state) const {
213  return GetState(state)->NumInputEpsilons();
214  }
215 
216  size_t NumOutputEpsilons(StateId state) const {
217  return GetState(state)->NumOutputEpsilons();
218  }
219 
220  void SetStart(StateId state) { start_ = state; }
221 
222  void SetFinal(StateId state, Weight weight) {
223  states_[state]->SetFinal(std::move(weight));
224  }
225 
227  states_.push_back(state);
228  return states_.size() - 1;
229  }
230 
231  StateId AddState() { return AddState(CreateState()); }
232 
233  void AddStates(size_t n) {
234  const auto curr_num_states = NumStates();
235  states_.resize(n + curr_num_states);
236  std::generate(states_.begin() + curr_num_states, states_.end(),
237  [this] { return CreateState(); });
238  }
239 
240  void AddArc(StateId state, const Arc &arc) { states_[state]->AddArc(arc); }
241 
242  void AddArc(StateId state, Arc &&arc) {
243  states_[state]->AddArc(std::move(arc));
244  }
245 
246  template <class... T>
247  void EmplaceArc(StateId state, T &&... ctor_args) {
248  states_[state]->EmplaceArc(std::forward<T>(ctor_args)...);
249  }
250 
251  void DeleteStates(const std::vector<StateId> &dstates) {
252  std::vector<StateId> newid(states_.size(), 0);
253  for (size_t i = 0; i < dstates.size(); ++i) newid[dstates[i]] = kNoStateId;
254  StateId nstates = 0;
255  for (StateId state = 0; state < states_.size(); ++state) {
256  if (newid[state] != kNoStateId) {
257  newid[state] = nstates;
258  if (state != nstates) states_[nstates] = states_[state];
259  ++nstates;
260  } else {
261  State::Destroy(states_[state], &state_alloc_);
262  }
263  }
264  states_.resize(nstates);
265  for (StateId state = 0; state < states_.size(); ++state) {
266  auto *arcs = states_[state]->MutableArcs();
267  size_t narcs = 0;
268  auto nieps = states_[state]->NumInputEpsilons();
269  auto noeps = states_[state]->NumOutputEpsilons();
270  for (size_t i = 0; i < states_[state]->NumArcs(); ++i) {
271  const auto t = newid[arcs[i].nextstate];
272  if (t != kNoStateId) {
273  arcs[i].nextstate = t;
274  if (i != narcs) arcs[narcs] = arcs[i];
275  ++narcs;
276  } else {
277  if (arcs[i].ilabel == 0) --nieps;
278  if (arcs[i].olabel == 0) --noeps;
279  }
280  }
281  states_[state]->DeleteArcs(states_[state]->NumArcs() - narcs);
282  states_[state]->SetNumInputEpsilons(nieps);
283  states_[state]->SetNumOutputEpsilons(noeps);
284  }
285  if (Start() != kNoStateId) SetStart(newid[Start()]);
286  }
287 
288  void DeleteStates() {
289  for (size_t state = 0; state < states_.size(); ++state) {
290  State::Destroy(states_[state], &state_alloc_);
291  }
292  states_.clear();
293  SetStart(kNoStateId);
294  }
295 
296  void DeleteArcs(StateId state, size_t n) { states_[state]->DeleteArcs(n); }
297 
298  void DeleteArcs(StateId state) { states_[state]->DeleteArcs(); }
299 
300  State *GetState(StateId state) { return states_[state]; }
301 
302  const State *GetState(StateId state) const { return states_[state]; }
303 
304  void SetState(StateId state, State *vstate) { states_[state] = vstate; }
305 
306  void ReserveStates(size_t n) { states_.reserve(n); }
307 
308  void ReserveArcs(StateId state, size_t n) { states_[state]->ReserveArcs(n); }
309 
310  // Provide information needed for generic state iterator.
312  data->base = nullptr;
313  data->nstates = states_.size();
314  }
315 
316  // Provide information needed for generic arc iterator.
317  void InitArcIterator(StateId state, ArcIteratorData<Arc> *data) const {
318  data->base = nullptr;
319  data->narcs = states_[state]->NumArcs();
320  data->arcs = states_[state]->Arcs();
321  data->ref_count = nullptr;
322  }
323 
324  private:
325  State *CreateState() { return new (&state_alloc_) State(arc_alloc_); }
326 
327  std::vector<State *> states_;
328  StateId start_;
329  typename State::StateAllocator state_alloc_;
330  typename State::ArcAllocator arc_alloc_;
331 };
332 
333 // This is a VectorFstBaseImpl container that holds VectorStates and manages FST
334 // properties.
335 template <class S>
336 class VectorFstImpl : public VectorFstBaseImpl<S> {
337  public:
338  using State = S;
339  using Arc = typename State::Arc;
340  using Label = typename Arc::Label;
341  using StateId = typename Arc::StateId;
342  using Weight = typename Arc::Weight;
343 
346  using FstImpl<Arc>::SetType;
349 
354 
355  friend class MutableArcIterator<VectorFst<Arc, S>>;
356 
358 
360  SetType("vector");
361  SetProperties(kNullProperties | kStaticProperties);
362  }
363 
364  explicit VectorFstImpl(const Fst<Arc> &fst);
365 
366  static VectorFstImpl *Read(std::istream &strm, const FstReadOptions &opts);
367 
368  void SetStart(StateId state) {
369  BaseImpl::SetStart(state);
370  SetProperties(SetStartProperties(Properties()));
371  }
372 
373  void SetFinal(StateId state, Weight weight) {
374  const auto old_weight = BaseImpl::Final(state);
375  const auto properties =
376  SetFinalProperties(Properties(), old_weight, weight);
377  BaseImpl::SetFinal(state, std::move(weight));
378  SetProperties(properties);
379  }
380 
382  const auto state = BaseImpl::AddState();
383  SetProperties(AddStateProperties(Properties()));
384  return state;
385  }
386 
387  void AddStates(size_t n) {
388  BaseImpl::AddStates(n);
389  SetProperties(AddStateProperties(Properties()));
390  }
391 
392  void AddArc(StateId state, const Arc &arc) {
393  BaseImpl::AddArc(state, arc);
394  UpdatePropertiesAfterAddArc(state);
395  }
396 
397  void AddArc(StateId state, Arc &&arc) {
398  BaseImpl::AddArc(state, std::move(arc));
399  UpdatePropertiesAfterAddArc(state);
400  }
401 
402  template <class... T>
403  void EmplaceArc(StateId state, T &&... ctor_args) {
404  BaseImpl::EmplaceArc(state, std::forward<T>(ctor_args)...);
405  UpdatePropertiesAfterAddArc(state);
406  }
407 
408  void DeleteStates(const std::vector<StateId> &dstates) {
409  BaseImpl::DeleteStates(dstates);
410  SetProperties(DeleteStatesProperties(Properties()));
411  }
412 
413  void DeleteStates() {
414  BaseImpl::DeleteStates();
415  SetProperties(DeleteAllStatesProperties(Properties(), kStaticProperties));
416  }
417 
418  void DeleteArcs(StateId state, size_t n) {
419  BaseImpl::DeleteArcs(state, n);
420  SetProperties(DeleteArcsProperties(Properties()));
421  }
422 
423  void DeleteArcs(StateId state) {
424  BaseImpl::DeleteArcs(state);
425  SetProperties(DeleteArcsProperties(Properties()));
426  }
427 
428  // Properties always true of this FST class
429  static constexpr uint64_t kStaticProperties = kExpanded | kMutable;
430 
431  private:
432  void UpdatePropertiesAfterAddArc(StateId state) {
433  auto *vstate = GetState(state);
434  const size_t num_arcs{vstate->NumArcs()};
435  if (num_arcs) {
436  const auto &arc = vstate->GetArc(num_arcs - 1);
437  const auto *parc =
438  (num_arcs < 2) ? nullptr : &(vstate->GetArc(num_arcs - 2));
439  SetProperties(AddArcProperties(Properties(), state, arc, parc));
440  }
441  }
442 
443  // Minimum file format version supported.
444  static constexpr int kMinFileVersion = 2;
445 };
446 
447 template <class S>
449  SetType("vector");
450  SetInputSymbols(fst.InputSymbols());
451  SetOutputSymbols(fst.OutputSymbols());
452  BaseImpl::SetStart(fst.Start());
453  if (fst.Properties(kExpanded, false)) {
454  BaseImpl::ReserveStates(CountStates(fst));
455  }
456  for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
457  const auto state = siter.Value();
458  BaseImpl::AddState();
459  BaseImpl::SetFinal(state, fst.Final(state));
460  ReserveArcs(state, fst.NumArcs(state));
461  for (ArcIterator<Fst<Arc>> aiter(fst, state); !aiter.Done(); aiter.Next()) {
462  const auto &arc = aiter.Value();
463  BaseImpl::AddArc(state, arc);
464  }
465  }
466  SetProperties(fst.Properties(kCopyProperties, false) | kStaticProperties);
467 }
468 
469 template <class S>
471  const FstReadOptions &opts) {
472  auto impl = std::make_unique<VectorFstImpl>();
473  FstHeader hdr;
474  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) return nullptr;
475  impl->BaseImpl::SetStart(hdr.Start());
476  if (hdr.NumStates() != kNoStateId) impl->ReserveStates(hdr.NumStates());
477  StateId state = 0;
478  for (; hdr.NumStates() == kNoStateId || state < hdr.NumStates(); ++state) {
479  Weight weight;
480  if (!weight.Read(strm)) break;
481  impl->BaseImpl::AddState();
482  auto *vstate = impl->GetState(state);
483  vstate->SetFinal(weight);
484  int64_t narcs;
485  ReadType(strm, &narcs);
486  if (!strm) {
487  LOG(ERROR) << "VectorFst::Read: Read failed: " << opts.source;
488  return nullptr;
489  }
490  impl->ReserveArcs(state, narcs);
491  for (int64_t i = 0; i < narcs; ++i) {
492  Arc arc;
493  ReadType(strm, &arc.ilabel);
494  ReadType(strm, &arc.olabel);
495  arc.weight.Read(strm);
496  ReadType(strm, &arc.nextstate);
497  if (!strm) {
498  LOG(ERROR) << "VectorFst::Read: Read failed: " << opts.source;
499  return nullptr;
500  }
501  impl->BaseImpl::AddArc(state, std::move(arc));
502  }
503  }
504  if (hdr.NumStates() != kNoStateId && state != hdr.NumStates()) {
505  LOG(ERROR) << "VectorFst::Read: Unexpected end of file: " << opts.source;
506  return nullptr;
507  }
508  return impl.release();
509 }
510 
511 } // namespace internal
512 
513 // Simple concrete, mutable FST. This class attaches interface to implementation
514 // and handles reference counting, delegating most methods to ImplToMutableFst.
515 // Also supports ReserveStates and ReserveArcs methods (cf. STL vector methods).
516 // The second optional template argument gives the State definition.
517 //
518 // VectorFst is thread-compatible.
519 template <class A, class S /* = VectorState<A> */>
520 class VectorFst : public ImplToMutableFst<internal::VectorFstImpl<S>> {
521  public:
522  using Arc = A;
523  using StateId = typename Arc::StateId;
524 
525  using State = S;
527 
528  friend class StateIterator<VectorFst<Arc, State>>;
529  friend class ArcIterator<VectorFst<Arc, State>>;
530  friend class MutableArcIterator<VectorFst<A, S>>;
531 
532  template <class F, class G>
533  friend void Cast(const F &, G *);
534 
535  VectorFst() : ImplToMutableFst<Impl>(std::make_shared<Impl>()) {}
536 
537  explicit VectorFst(const Fst<Arc> &fst)
538  : ImplToMutableFst<Impl>(std::make_shared<Impl>(fst)) {}
539 
540  VectorFst(const VectorFst &fst, bool unused_safe = false)
541  : ImplToMutableFst<Impl>(fst.GetSharedImpl()) {}
542 
543  VectorFst(VectorFst &&) noexcept;
544 
545  // Get a copy of this VectorFst. See Fst<>::Copy() for further doc.
546  VectorFst *Copy(bool safe = false) const override {
547  return new VectorFst(*this, safe);
548  }
549 
550  VectorFst &operator=(const VectorFst &) = default;
551 
552  VectorFst &operator=(VectorFst &&) noexcept;
553 
554  VectorFst &operator=(const Fst<Arc> &fst) override {
555  if (this != &fst) SetImpl(std::make_shared<Impl>(fst));
556  return *this;
557  }
558 
559  template <class... T>
560  void EmplaceArc(StateId state, T &&... ctor_args) {
561  MutateCheck();
562  GetMutableImpl()->EmplaceArc(state, std::forward<T>(ctor_args)...);
563  }
564 
565  // Reads a VectorFst from an input stream, returning nullptr on error.
566  static VectorFst *Read(std::istream &strm, const FstReadOptions &opts) {
567  auto *impl = Impl::Read(strm, opts);
568  return impl ? new VectorFst(std::shared_ptr<Impl>(impl)) : nullptr;
569  }
570 
571  // Read a VectorFst from a file, returning nullptr on error; empty source
572  // reads from standard input.
573  static VectorFst *Read(const std::string &source) {
574  auto *impl = ImplToExpandedFst<Impl, MutableFst<Arc>>::Read(source);
575  return impl ? new VectorFst(std::shared_ptr<Impl>(impl)) : nullptr;
576  }
577 
578  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
579  return WriteFst(*this, strm, opts);
580  }
581 
582  bool Write(const std::string &source) const override {
583  return Fst<Arc>::WriteFile(source);
584  }
585 
586  template <class FST>
587  static bool WriteFst(const FST &fst, std::ostream &strm,
588  const FstWriteOptions &opts);
589 
590  void InitStateIterator(StateIteratorData<Arc> *data) const override {
591  GetImpl()->InitStateIterator(data);
592  }
593 
594  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
595  GetImpl()->InitArcIterator(s, data);
596  }
597 
598  inline void InitMutableArcIterator(StateId s,
599  MutableArcIteratorData<Arc> *) override;
600 
602  using ImplToMutableFst<Impl, MutableFst<Arc>>::ReserveStates;
603 
604  private:
606  using ImplToMutableFst<Impl, MutableFst<Arc>>::GetMutableImpl;
607  using ImplToMutableFst<Impl, MutableFst<Arc>>::MutateCheck;
609 
610  explicit VectorFst(std::shared_ptr<Impl> impl)
611  : ImplToMutableFst<Impl>(impl) {}
612 };
613 
614 template <class Arc, class State>
615 inline VectorFst<Arc, State>::VectorFst(VectorFst &&fst) noexcept = default;
616 
617 template <class Arc, class State>
619  VectorFst &&fst) noexcept = default;
620 
621 // Writes FST to file in Vector format, potentially with a pass over the machine
622 // before writing to compute number of states.
623 template <class Arc, class State>
624 template <class FST>
625 bool VectorFst<Arc, State>::WriteFst(const FST &fst, std::ostream &strm,
626  const FstWriteOptions &opts) {
627  static constexpr int file_version = 2;
628  bool update_header = true;
629  FstHeader hdr;
630  hdr.SetStart(fst.Start());
632  std::streampos start_offset = 0;
633  if (fst.Properties(kExpanded, false) || opts.stream_write ||
634  (start_offset = strm.tellp()) != -1) {
635  hdr.SetNumStates(CountStates(fst));
636  update_header = false;
637  }
638  const auto properties =
639  fst.Properties(kCopyProperties, false) | Impl::kStaticProperties;
640  internal::FstImpl<Arc>::WriteFstHeader(fst, strm, opts, file_version,
641  "vector", properties, &hdr);
642  StateId num_states = 0;
643  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
644  const auto s = siter.Value();
645  fst.Final(s).Write(strm);
646  const int64_t narcs = fst.NumArcs(s);
647  WriteType(strm, narcs);
648  for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
649  const auto &arc = aiter.Value();
650  WriteType(strm, arc.ilabel);
651  WriteType(strm, arc.olabel);
652  arc.weight.Write(strm);
653  WriteType(strm, arc.nextstate);
654  }
655  ++num_states;
656  }
657  strm.flush();
658  if (!strm) {
659  LOG(ERROR) << "VectorFst::Write: Write failed: " << opts.source;
660  return false;
661  }
662  if (update_header) {
663  hdr.SetNumStates(num_states);
665  fst, strm, opts, file_version, "vector", properties, &hdr,
666  start_offset);
667  } else {
668  if (num_states != hdr.NumStates()) {
669  LOG(ERROR) << "Inconsistent number of states observed during write";
670  return false;
671  }
672  }
673  return true;
674 }
675 
676 // Specialization for VectorFst; see generic version in fst.h for sample usage
677 // (but use the VectorFst type instead). This version should inline.
678 template <class Arc, class State>
679 class StateIterator<VectorFst<Arc, State>> {
680  public:
681  using StateId = typename Arc::StateId;
682 
684  : nstates_(fst.GetImpl()->NumStates()), s_(0) {}
685 
686  bool Done() const { return s_ >= nstates_; }
687 
688  StateId Value() const { return s_; }
689 
690  void Next() { ++s_; }
691 
692  void Reset() { s_ = 0; }
693 
694  private:
695  const StateId nstates_;
696  StateId s_;
697 };
698 
699 // Specialization for VectorFst; see generic version in fst.h for sample usage
700 // (but use the VectorFst type instead). This version should inline.
701 template <class Arc, class State>
702 class ArcIterator<VectorFst<Arc, State>> {
703  public:
704  using StateId = typename Arc::StateId;
705 
707  : arcs_(fst.GetImpl()->GetState(s)->Arcs()),
708  narcs_(fst.GetImpl()->GetState(s)->NumArcs()),
709  i_(0) {}
710 
711  bool Done() const { return i_ >= narcs_; }
712 
713  const Arc &Value() const { return arcs_[i_]; }
714 
715  void Next() { ++i_; }
716 
717  void Reset() { i_ = 0; }
718 
719  void Seek(size_t a) { i_ = a; }
720 
721  size_t Position() const { return i_; }
722 
723  constexpr uint8_t Flags() const { return kArcValueFlags; }
724 
725  void SetFlags(uint8_t, uint8_t) {}
726 
727  private:
728  const Arc *arcs_;
729  size_t narcs_;
730  size_t i_;
731 };
732 
733 // Specialization for VectorFst; see generic version in mutable-fst.h for sample
734 // usage (but use the VectorFst type instead). This version should inline.
735 template <class Arc, class State>
737  : public MutableArcIteratorBase<Arc> {
738  public:
739  using StateId = typename Arc::StateId;
740  using Weight = typename Arc::Weight;
741 
743  fst->MutateCheck();
744  state_ = fst->GetMutableImpl()->GetState(s);
745  properties_ = &fst->GetImpl()->properties_;
746  }
747 
748  bool Done() const final { return i_ >= state_->NumArcs(); }
749 
750  const Arc &Value() const final { return state_->GetArc(i_); }
751 
752  void Next() final { ++i_; }
753 
754  size_t Position() const final { return i_; }
755 
756  void Reset() final { i_ = 0; }
757 
758  void Seek(size_t a) final { i_ = a; }
759 
760  void SetValue(const Arc &arc) final {
761  const auto &oarc = state_->GetArc(i_);
762  uint64_t properties = properties_->load(std::memory_order_relaxed);
763  if (oarc.ilabel != oarc.olabel) properties &= ~kNotAcceptor;
764  if (oarc.ilabel == 0) {
765  properties &= ~kIEpsilons;
766  if (oarc.olabel == 0) properties &= ~kEpsilons;
767  }
768  if (oarc.olabel == 0) properties &= ~kOEpsilons;
769  if (oarc.weight != Weight::Zero() && oarc.weight != Weight::One()) {
770  properties &= ~kWeighted;
771  }
772  state_->SetArc(arc, i_);
773  if (arc.ilabel != arc.olabel) {
774  properties |= kNotAcceptor;
775  properties &= ~kAcceptor;
776  }
777  if (arc.ilabel == 0) {
778  properties |= kIEpsilons;
779  properties &= ~kNoIEpsilons;
780  if (arc.olabel == 0) {
781  properties |= kEpsilons;
782  properties &= ~kNoEpsilons;
783  }
784  }
785  if (arc.olabel == 0) {
786  properties |= kOEpsilons;
787  properties &= ~kNoOEpsilons;
788  }
789  if (arc.weight != Weight::Zero() && arc.weight != Weight::One()) {
790  properties |= kWeighted;
791  properties &= ~kUnweighted;
792  }
793  properties &= kSetArcProperties | kAcceptor | kNotAcceptor | kEpsilons |
796  properties_->store(properties, std::memory_order_relaxed);
797  }
798 
799  uint8_t Flags() const final { return kArcValueFlags; }
800 
801  void SetFlags(uint8_t, uint8_t) final {}
802 
803  private:
804  State *state_;
805  std::atomic<uint64_t> *properties_;
806  size_t i_;
807 };
808 
809 // Provides information needed for the generic mutable arc iterator.
810 template <class Arc, class State>
813  data->base =
814  std::make_unique<MutableArcIterator<VectorFst<Arc, State>>>(this, s);
815 }
816 
817 // A useful alias when using StdArc.
819 
820 } // namespace fst
821 
822 #endif // FST_VECTOR_FST_H_
typename std::allocator_traits< ArcAllocator >::template rebind_alloc< VectorState< Arc, M >> StateAllocator
Definition: vector-fst.h:55
void AddArc(StateId state, const Arc &arc)
Definition: vector-fst.h:240
typename Arc::Weight Weight
Definition: vector-fst.h:172
void SetState(StateId state, State *vstate)
Definition: vector-fst.h:304
uint64_t AddArcProperties(uint64_t inprops, typename A::StateId s, const A &arc, const A *prev_arc)
void DeleteArcs(StateId state)
Definition: vector-fst.h:298
constexpr uint64_t kMutable
Definition: properties.h:48
constexpr uint8_t kArcValueFlags
Definition: fst.h:453
void AddArc(StateId state, Arc &&arc)
Definition: vector-fst.h:397
uint64_t SetStartProperties(uint64_t inprops)
Definition: properties.h:395
void Cast(const F &, G *)
virtual uint64_t Properties(uint64_t mask, bool test) const =0
constexpr uint64_t kOEpsilons
Definition: properties.h:88
void DeleteStates(const std::vector< StateId > &dstates)
Definition: vector-fst.h:408
std::unique_ptr< MutableArcIteratorBase< Arc > > base
Definition: mutable-fst.h:201
virtual size_t NumArcs(StateId) const =0
VectorFstBaseImpl & operator=(VectorFstBaseImpl &&impl) noexcept
Definition: vector-fst.h:193
VectorState(const ArcAllocator &alloc)
Definition: vector-fst.h:58
void DeleteArcs(StateId state, size_t n)
Definition: vector-fst.h:418
std::string source
Definition: fst.h:74
Weight Final() const
Definition: vector-fst.h:77
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:97
void ReserveArcs(size_t n)
Definition: vector-fst.h:91
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: vector-fst.h:594
uint64_t AddStateProperties(uint64_t inprops)
Definition: properties.h:403
StateIterator(const VectorFst< Arc, State > &fst)
Definition: vector-fst.h:683
uint64_t DeleteAllStatesProperties(uint64_t inprops, uint64_t staticProps)
Definition: properties.h:411
Arc * MutableArcs()
Definition: vector-fst.h:89
uint64_t DeleteStatesProperties(uint64_t inprops)
Definition: properties.h:407
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: vector-fst.h:578
void SetNumOutputEpsilons(size_t n)
Definition: vector-fst.h:97
size_t NumArcs(StateId state) const
Definition: vector-fst.h:210
#define LOG(type)
Definition: log.h:49
void SetFinal(StateId state, Weight weight)
Definition: vector-fst.h:222
virtual Weight Final(StateId) const =0
SetType
Definition: set-weight.h:52
static VectorFst * Read(const std::string &source)
Definition: vector-fst.h:573
static VectorFst * Read(std::istream &strm, const FstReadOptions &opts)
Definition: vector-fst.h:566
typename Arc::StateId StateId
Definition: fst.h:462
constexpr uint64_t kEpsilons
Definition: properties.h:78
uint64_t SetFinalProperties(uint64_t inprops, const Weight &old_weight, const Weight &new_weight)
Definition: properties.h:423
void InitMutableArcIterator(StateId s, MutableArcIteratorData< Arc > *) override
Definition: vector-fst.h:811
typename Arc::Label Label
Definition: vector-fst.h:340
bool stream_write
Definition: fst.h:107
constexpr int kNoStateId
Definition: fst.h:202
void DeleteStates(const std::vector< StateId > &dstates)
Definition: vector-fst.h:251
void AddArc(StateId state, Arc &&arc)
Definition: vector-fst.h:242
typename Arc::StateId StateId
Definition: vector-fst.h:51
VectorFst(const Fst< Arc > &fst)
Definition: vector-fst.h:537
std::ostream & WriteType(std::ostream &strm, const T t)
Definition: util.h:211
std::string source
Definition: fst.h:102
void InitStateIterator(StateIteratorData< Arc > *data) const
Definition: vector-fst.h:311
static void WriteFstHeader(const Fst< Arc > &fst, std::ostream &strm, const FstWriteOptions &opts, int version, std::string_view type, uint64_t properties, FstHeader *hdr)
Definition: fst.h:812
Weight Final(StateId state) const
Definition: vector-fst.h:206
const State * GetState(StateId state) const
Definition: vector-fst.h:302
MutableArcIterator(VectorFst< Arc, State > *fst, StateId s)
Definition: vector-fst.h:742
State * GetState(StateId state)
Definition: vector-fst.h:300
size_t NumArcs() const
Definition: vector-fst.h:83
void SetFinal(Weight weight)
Definition: vector-fst.h:93
void EmplaceArc(StateId state, T &&...ctor_args)
Definition: vector-fst.h:403
static void Destroy(VectorState< A, M > *state, StateAllocator *alloc)
Definition: vector-fst.h:142
constexpr uint64_t kNoOEpsilons
Definition: properties.h:90
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: vector-fst.h:590
constexpr uint64_t kNotAcceptor
Definition: properties.h:65
constexpr uint64_t kCopyProperties
Definition: properties.h:162
VectorFst & operator=(const Fst< Arc > &fst) override
Definition: vector-fst.h:554
void AddArc(const Arc &arc)
Definition: vector-fst.h:99
constexpr uint64_t kNoEpsilons
Definition: properties.h:80
ArcIterator(const VectorFst< Arc, State > &fst, StateId s)
Definition: vector-fst.h:706
static bool UpdateFstHeader(const Fst< Arc > &fst, std::ostream &strm, const FstWriteOptions &opts, int version, std::string_view type, uint64_t properties, FstHeader *hdr, size_t header_offset)
Definition: fst.h:845
void SetStart(StateId state)
Definition: vector-fst.h:368
StateId nstates
Definition: fst.h:384
VectorFst * Copy(bool safe=false) const override
Definition: vector-fst.h:546
virtual StateId Start() const =0
bool Done() const
Definition: fst.h:533
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
void DeleteArcs(size_t n)
Definition: vector-fst.h:128
void ReserveArcs(StateId state, size_t n)
Definition: vector-fst.h:308
void AddArc(StateId state, const Arc &arc)
Definition: vector-fst.h:392
size_t NumOutputEpsilons() const
Definition: vector-fst.h:81
VectorFst & operator=(const VectorFst &)=default
void EmplaceArc(StateId state, T &&...ctor_args)
Definition: vector-fst.h:560
typename Arc::StateId StateId
Definition: vector-fst.h:171
constexpr uint64_t kNullProperties
Definition: properties.h:149
std::unique_ptr< ArcIteratorBase< Arc > > base
Definition: fst.h:495
constexpr uint64_t kIEpsilons
Definition: properties.h:83
size_t NumInputEpsilons(StateId state) const
Definition: vector-fst.h:212
VectorState(const VectorState< A, M > &state, const ArcAllocator &alloc)
Definition: vector-fst.h:64
size_t NumOutputEpsilons(StateId state) const
Definition: vector-fst.h:216
bool WriteFile(const std::string &source) const
Definition: fst.h:332
constexpr uint8_t Flags() const
Definition: vector-fst.h:723
void SetNumInputEpsilons(size_t n)
Definition: vector-fst.h:95
bool Write(const std::string &source) const override
Definition: vector-fst.h:582
constexpr uint64_t kUnweighted
Definition: properties.h:105
void EmplaceArc(StateId state, T &&...ctor_args)
Definition: vector-fst.h:247
void SetNumStates(int64_t numstates)
Definition: fst.h:170
A Arc
Definition: fst.h:211
const Arc & GetArc(size_t n) const
Definition: vector-fst.h:85
virtual const SymbolTable * InputSymbols() const =0
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:169
int64_t NumStates() const
Definition: fst.h:154
typename Arc::Weight Weight
Definition: vector-fst.h:52
VectorFst(const VectorFst &fst, bool unused_safe=false)
Definition: vector-fst.h:540
bool Done() const
Definition: fst.h:415
const Arc * Arcs() const
Definition: vector-fst.h:87
void SetStart(int64_t start)
Definition: fst.h:168
const Arc * arcs
Definition: fst.h:496
void DeleteArcs(StateId state, size_t n)
Definition: vector-fst.h:296
void SetStart(StateId state)
Definition: vector-fst.h:220
VectorFstBaseImpl(VectorFstBaseImpl &&impl) noexcept
Definition: vector-fst.h:185
std::istream & ReadType(std::istream &strm, T *t)
Definition: util.h:65
uint64_t DeleteArcsProperties(uint64_t inprops)
Definition: properties.h:416
typename Arc::StateId StateId
Definition: fst.h:212
void DeleteArcs(StateId state)
Definition: vector-fst.h:423
size_t NumInputEpsilons() const
Definition: vector-fst.h:79
void AddArc(Arc &&arc)
Definition: vector-fst.h:104
void InitArcIterator(StateId state, ArcIteratorData< Arc > *data) const
Definition: vector-fst.h:317
constexpr uint64_t kWeighted
Definition: properties.h:103
void EmplaceArc(T &&...ctor_args)
Definition: vector-fst.h:110
static bool WriteFst(const FST &fst, std::ostream &strm, const FstWriteOptions &opts)
Definition: vector-fst.h:625
constexpr uint64_t kExpanded
Definition: properties.h:45
void SetFinal(StateId state, Weight weight)
Definition: vector-fst.h:373
void SetArc(const Arc &arc, size_t n)
Definition: vector-fst.h:115
int * ref_count
Definition: fst.h:498
constexpr uint64_t kNoIEpsilons
Definition: properties.h:85
constexpr uint64_t kSetArcProperties
Definition: properties.h:223
void Destroy(ArcIterator< FST > *aiter, MemoryPool< ArcIterator< FST >> *pool)
Definition: fst.h:594
size_t narcs
Definition: fst.h:497
StateId AddState(State *state)
Definition: vector-fst.h:226
constexpr uint64_t kAcceptor
Definition: properties.h:63
virtual const SymbolTable * OutputSymbols() const =0