FST  openfst-1.8.3
OpenFst Library
compact-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 // FST Class for memory-efficient representation of common types of
19 // FSTs: linear automata, acceptors, unweighted FSTs, ...
20 
21 #ifndef FST_COMPACT_FST_H_
22 #define FST_COMPACT_FST_H_
23 
24 #include <sys/types.h>
25 
26 #include <climits>
27 #include <cstddef>
28 #include <cstdint>
29 #include <cstdlib>
30 #include <cstring>
31 #include <ctime>
32 #include <istream>
33 #include <iterator>
34 #include <memory>
35 #include <ostream>
36 #include <string>
37 #include <tuple>
38 #include <utility>
39 #include <vector>
40 
41 #include <fst/log.h>
42 #include <fst/arc.h>
43 #include <fst/cache.h>
44 #include <fst/expanded-fst.h>
45 #include <fst/fst-decl.h> // For optional argument declarations
46 #include <fst/fst.h>
47 #include <fst/impl-to-fst.h>
48 #include <fst/mapped-file.h>
49 #include <fst/matcher.h>
50 #include <fst/properties.h>
51 #include <fst/test-properties.h>
52 #include <fst/util.h>
53 #include <string_view>
54 
55 namespace fst {
56 
58  // The default caching behaviour is to do no caching. Most compactors are
59  // cheap and therefore we save memory by not doing caching.
61 
62  explicit CompactFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
63 };
64 
65 // New (Fst) Compactor interface - used by CompactFst. This interface
66 // allows complete flexibility in how the compaction is accomplished.
67 //
68 // class Compactor {
69 // public:
70 // // Constructor from the Fst to be compacted. If compactor is present,
71 // // only optional state should be copied from it. Examples of this
72 // // optional state include compression level or ArcCompactors.
73 // explicit Compactor(const Fst<Arc> &fst,
74 // shared_ptr<Compactor> compactor = nullptr);
75 // // Copy constructor. Must make a thread-safe copy suitable for use by
76 // // by Fst::Copy(/*safe=*/true). Only thread-unsafe data structures
77 // // need to be deeply copied. Ideally, this constructor is O(1) and any
78 // // large structures are thread-safe and shared, while small ones may
79 // // need to be copied.
80 // Compactor(const Compactor &compactor);
81 // // Default constructor (optional, see comment below).
82 // Compactor();
83 //
84 // // Returns the start state, number of states, and total number of arcs
85 // // of the compacted Fst
86 // StateId Start() const;
87 // StateId NumStates() const;
88 // size_t NumArcs() const;
89 //
90 // // Accessor class for state attributes.
91 // class State {
92 // public:
93 // State(); // Required, corresponds to kNoStateId.
94 // // This constructor may, of course, also take a const Compactor *
95 // // for the first argument. It is recommended to use const Compactor *
96 // // if possible, but this can be Compactor * if necessary.
97 // State(Compactor *c, StateId s); // Accessor for StateId 's'.
98 // StateId GetStateId() const;
99 // Weight Final() const;
100 // size_t NumArcs() const;
101 // // Gets the 'i'th arc for the state. Requires i < NumArcs().
102 // // Flags are a bitmask of the kArc*Value flags that ArcIterator uses.
103 // Arc GetArc(size_t i, uint8_t flags) const;
104 // };
105 //
106 // // Modifies 'state' accessor to provide access to state id 's'.
107 // void SetState(StateId s, State *state);
108 //
109 // // Tests whether 'fst' can be compacted by this compactor.
110 // template <typename A>
111 // bool IsCompatible(const Fst<A> &fst) const;
112 //
113 // // Returns the properties that are always when an FST with the
114 // // specified properties is compacted using this compactor.
115 // // This function should clear bits for properties that no longer
116 // // hold and set those for properties that are known to hold.
117 // uint64_t Properties(uint64_t props) const;
118 //
119 // // Returns a string identifying the type of compactor.
120 // static const std::string &Type();
121 //
122 // // Returns true if an error has occurred.
123 // bool Error() const;
124 //
125 // // Writes a compactor to a file.
126 // bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
127 //
128 // // Reads a compactor from a file.
129 // static Compactor *Read(std::istream &strm, const FstReadOptions &opts,
130 // const FstHeader &hdr);
131 // };
132 //
133 
134 // Old ArcCompactor Interface:
135 //
136 // This interface is not deprecated; it, along with CompactArcStore and
137 // other Stores that implement its interface, is simply more constrained
138 // by essentially forcing the implementation to use an index array
139 // and an arc array, but giving flexibility in how those are implemented.
140 // This interface may still be useful and more convenient if that is the
141 // desired representation.
142 //
143 // The ArcCompactor class determines how arcs and final weights are compacted
144 // and expanded.
145 //
146 // Final weights are treated as transitions to the superfinal state, i.e.,
147 // ilabel = olabel = kNoLabel and nextstate = kNoStateId.
148 //
149 // There are two types of compactors:
150 //
151 // * Fixed out-degree compactors: 'compactor.Size()' returns a positive integer
152 // 's'. An FST can be compacted by this compactor only if each state has
153 // exactly 's' outgoing transitions (counting a non-Zero() final weight as a
154 // transition). A typical example is a compactor for string FSTs, i.e.,
155 // 's == 1'.
156 //
157 // * Variable out-degree compactors: 'compactor.Size() == -1'. There are no
158 // out-degree restrictions for these compactors.
159 //
160 // Interface:
161 //
162 // class ArcCompactor {
163 // public:
164 // // Default constructor (optional, see comment below).
165 // ArcCompactor();
166 //
167 // // Copy constructor. Must make a thread-safe copy suitable for use by
168 // // by Fst::Copy(/*safe=*/true). Only thread-unsafe data structures
169 // // need to be deeply copied.
170 // ArcCompactor(const ArcCompactor &);
171 //
172 // // Element is the type of the compacted transitions.
173 // using Element = ...
174 //
175 // // Returns the compacted representation of a transition 'arc'
176 // // at a state 's'.
177 // Element Compact(StateId s, const Arc &arc);
178 //
179 // // Returns the transition at state 's' represented by the compacted
180 // // transition 'e'.
181 // Arc Expand(StateId s, const Element &e) const;
182 //
183 // // Returns -1 for variable out-degree compactors, and the mandatory
184 // // out-degree otherwise.
185 // ssize_t Size() const;
186 //
187 // // Tests whether an FST can be compacted by this compactor.
188 // bool Compatible(const Fst<A> &fst) const;
189 //
190 // // Returns the properties that are always true for an FST compacted using
191 // // this compactor. Any Fst with the inverse of these properties should
192 // // be incompatible.
193 // uint64_t Properties() const;
194 //
195 // // Returns a string identifying the type of compactor.
196 // static const std::string &Type();
197 //
198 // // Writes a compactor to a file.
199 // bool Write(std::ostream &strm) const;
200 //
201 // // Reads a compactor from a file.
202 // static ArcCompactor *Read(std::istream &strm);
203 // };
204 //
205 // The default constructor is only required for FST_REGISTER to work (i.e.,
206 // enabling Convert() and the command-line utilities to work with this new
207 // compactor). However, a default constructor always needs to be specified for
208 // this code to compile, but one can have it simply raise an error when called,
209 // like so:
210 //
211 // Compactor::Compactor() {
212 // FSTERROR() << "Compactor: No default constructor";
213 // }
214 
215 // Default implementation data for CompactArcCompactor. Only old-style
216 // ArcCompactors are supported because the CompactArcStore constructors
217 // use the old API.
218 //
219 // DefaultCompact store is thread-compatible, but not thread-safe.
220 // The copy constructor makes a thread-safe copy.
221 //
222 // The implementation contains two arrays: 'states_' and 'compacts_'.
223 //
224 // For fixed out-degree compactors, the 'states_' array is unallocated. The
225 // 'compacts_' array contains the compacted transitions. Its size is
226 // 'ncompacts_'. The outgoing transitions at a given state are stored
227 // consecutively. For a given state 's', its 'compactor.Size()' outgoing
228 // transitions (including a superfinal transition when 's' is final), are stored
229 // in positions ['s*compactor.Size()', '(s+1)*compactor.Size()').
230 //
231 // For variable out-degree compactors, the states_ array has size
232 // 'nstates_ + 1' and contains positions in the 'compacts_' array. For a
233 // given state 's', the compacted transitions of 's' are stored in positions
234 // ['states_[s]', 'states_[s + 1]') in 'compacts_'. By convention,
235 // 'states_[nstates_] == ncompacts_'.
236 //
237 // In both cases, the superfinal transitions (when 's' is final, i.e.,
238 // 'Final(s) != Weight::Zero()') are stored first.
239 //
240 // The unsigned type U is used to represent indices into the compacts_ array.
241 template <class Element, class Unsigned>
243  public:
244  CompactArcStore() = default;
245 
246  // Makes a thread-safe copy. O(1).
247  CompactArcStore(const CompactArcStore &) = default;
248 
249  template <class Arc, class ArcCompactor>
250  CompactArcStore(const Fst<Arc> &fst, const ArcCompactor &arc_compactor);
251 
252  template <class Iterator, class ArcCompactor>
253  CompactArcStore(const Iterator begin, const Iterator end,
254  const ArcCompactor &arc_compactor);
255 
256  ~CompactArcStore() = default;
257 
258  template <class ArcCompactor>
259  static CompactArcStore *Read(std::istream &strm, const FstReadOptions &opts,
260  const FstHeader &hdr,
261  const ArcCompactor &arc_compactor);
262 
263  bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
264 
265  // Returns the starting index in 'compacts_' of the transitions
266  // for state 'i'. See class-level comment for further details.
267  // Requires that the CompactArcStore was constructed with a
268  // variable out-degree compactor. Requires 0 <= i <= NumStates().
269  // By convention, States(NumStates()) == NumCompacts().
270  Unsigned States(ssize_t i) const { return states_[i]; }
271 
272  // Returns the compacted Element at position i. See class-level comment
273  // for further details. Requires 0 <= i < NumCompacts().
274  const Element &Compacts(size_t i) const { return compacts_[i]; }
275 
276  size_t NumStates() const { return nstates_; }
277 
278  size_t NumCompacts() const { return ncompacts_; }
279 
280  size_t NumArcs() const { return narcs_; }
281 
282  ssize_t Start() const { return start_; }
283 
284  bool Error() const { return error_; }
285 
286  // Returns a string identifying the type of data storage container.
287  static const std::string &Type();
288 
289  private:
290  std::shared_ptr<MappedFile> states_region_;
291  std::shared_ptr<MappedFile> compacts_region_;
292  // Unowned pointer into states_region_.
293  Unsigned *states_ = nullptr;
294  // Unowned pointer into compacts_region_.
295  Element *compacts_ = nullptr;
296  size_t nstates_ = 0;
297  size_t ncompacts_ = 0;
298  size_t narcs_ = 0;
299  ssize_t start_ = kNoStateId;
300  bool error_ = false;
301 };
302 
303 template <class Element, class Unsigned>
304 template <class Arc, class ArcCompactor>
306  const Fst<Arc> &fst, const ArcCompactor &arc_compactor) {
307  using StateId = typename Arc::StateId;
308  using Weight = typename Arc::Weight;
309  start_ = fst.Start();
310  // Counts # of states and arcs.
311  StateId nfinals = 0;
312  for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
313  ++nstates_;
314  const auto s = siter.Value();
315  narcs_ += fst.NumArcs(s);
316  if (fst.Final(s) != Weight::Zero()) ++nfinals;
317  }
318  if (arc_compactor.Size() == -1) {
319  states_region_ = fst::WrapUnique(MappedFile::Allocate(
320  sizeof(states_[0]) * (nstates_ + 1), alignof(decltype(states_[0]))));
321  states_ = static_cast<Unsigned *>(states_region_->mutable_data());
322  ncompacts_ = narcs_ + nfinals;
323  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
324  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
325  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
326  states_[nstates_] = ncompacts_;
327  } else {
328  states_ = nullptr;
329  ncompacts_ = nstates_ * arc_compactor.Size();
330  if ((narcs_ + nfinals) != ncompacts_) {
331  FSTERROR() << "CompactArcStore: ArcCompactor incompatible with FST";
332  error_ = true;
333  return;
334  }
335  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
336  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
337  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
338  }
339  size_t pos = 0;
340  size_t fpos = 0;
341  for (size_t s = 0; s < nstates_; ++s) {
342  fpos = pos;
343  if (arc_compactor.Size() == -1) states_[s] = pos;
344  if (fst.Final(s) != Weight::Zero()) {
345  compacts_[pos++] = arc_compactor.Compact(
346  s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
347  }
348  for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
349  compacts_[pos++] = arc_compactor.Compact(s, aiter.Value());
350  }
351  if ((arc_compactor.Size() != -1) && (pos != fpos + arc_compactor.Size())) {
352  FSTERROR() << "CompactArcStore: ArcCompactor incompatible with FST";
353  error_ = true;
354  return;
355  }
356  }
357  if (pos != ncompacts_) {
358  FSTERROR() << "CompactArcStore: ArcCompactor incompatible with FST";
359  error_ = true;
360  return;
361  }
362 }
363 
364 template <class Element, class Unsigned>
365 template <class Iterator, class ArcCompactor>
367  const Iterator begin, const Iterator end,
368  const ArcCompactor &arc_compactor) {
369  using Arc = typename ArcCompactor::Arc;
370  using Weight = typename Arc::Weight;
371  if (arc_compactor.Size() != -1) {
372  ncompacts_ = std::distance(begin, end);
373  if (arc_compactor.Size() == 1) {
374  // For strings, allows implicit final weight. Empty input is the empty
375  // string.
376  if (ncompacts_ == 0) {
377  ++ncompacts_;
378  } else {
379  const auto arc =
380  arc_compactor.Expand(ncompacts_ - 1, *(begin + (ncompacts_ - 1)));
381  if (arc.ilabel != kNoLabel) ++ncompacts_;
382  }
383  }
384  if (ncompacts_ % arc_compactor.Size()) {
385  FSTERROR() << "CompactArcStore: Size of input container incompatible"
386  << " with arc compactor";
387  error_ = true;
388  return;
389  }
390  if (ncompacts_ == 0) return;
391  start_ = 0;
392  nstates_ = ncompacts_ / arc_compactor.Size();
393  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
394  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
395  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
396  size_t i = 0;
397  Iterator it = begin;
398  for (; it != end; ++it, ++i) {
399  compacts_[i] = *it;
400  if (arc_compactor.Expand(i, *it).ilabel != kNoLabel) ++narcs_;
401  }
402  if (i < ncompacts_) {
403  compacts_[i] = arc_compactor.Compact(
404  i, Arc(kNoLabel, kNoLabel, Weight::One(), kNoStateId));
405  }
406  } else {
407  if (std::distance(begin, end) == 0) return;
408  // Count # of states, arcs and compacts.
409  auto it = begin;
410  for (size_t i = 0; it != end; ++it, ++i) {
411  const auto arc = arc_compactor.Expand(i, *it);
412  if (arc.ilabel != kNoLabel) {
413  ++narcs_;
414  ++ncompacts_;
415  } else {
416  ++nstates_;
417  if (arc.weight != Weight::Zero()) ++ncompacts_;
418  }
419  }
420  start_ = 0;
421  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
422  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
423  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
424  states_region_ = fst::WrapUnique(MappedFile::Allocate(
425  sizeof(states_[0]) * (nstates_ + 1), alignof(decltype(states_[0]))));
426  states_ = static_cast<Unsigned *>(states_region_->mutable_data());
427  states_[nstates_] = ncompacts_;
428  size_t i = 0;
429  size_t s = 0;
430  for (it = begin; it != end; ++it) {
431  const auto arc = arc_compactor.Expand(i, *it);
432  if (arc.ilabel != kNoLabel) {
433  compacts_[i++] = *it;
434  } else {
435  states_[s++] = i;
436  if (arc.weight != Weight::Zero()) compacts_[i++] = *it;
437  }
438  }
439  if ((s != nstates_) || (i != ncompacts_)) {
440  FSTERROR() << "CompactArcStore: Ill-formed input container";
441  error_ = true;
442  return;
443  }
444  }
445 }
446 
447 template <class Element, class Unsigned>
448 template <class ArcCompactor>
450  std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr,
451  const ArcCompactor &arc_compactor) {
452  auto data = std::make_unique<CompactArcStore>();
453  data->start_ = hdr.Start();
454  data->nstates_ = hdr.NumStates();
455  data->narcs_ = hdr.NumArcs();
456  if (arc_compactor.Size() == -1) {
457  if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
458  LOG(ERROR) << "CompactArcStore::Read: Alignment failed: " << opts.source;
459  return nullptr;
460  }
461  auto b = (data->nstates_ + 1) * sizeof(Unsigned);
462  data->states_region_.reset(MappedFile::Map(
463  strm, opts.mode == FstReadOptions::MAP, opts.source, b));
464  if (!strm || !data->states_region_) {
465  LOG(ERROR) << "CompactArcStore::Read: Read failed: " << opts.source;
466  return nullptr;
467  }
468  data->states_ =
469  static_cast<Unsigned *>(data->states_region_->mutable_data());
470  } else {
471  data->states_ = nullptr;
472  }
473  data->ncompacts_ = arc_compactor.Size() == -1
474  ? data->states_[data->nstates_]
475  : data->nstates_ * arc_compactor.Size();
476  if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
477  LOG(ERROR) << "CompactArcStore::Read: Alignment failed: " << opts.source;
478  return nullptr;
479  }
480  size_t b = data->ncompacts_ * sizeof(Element);
481  data->compacts_region_.reset(
482  MappedFile::Map(strm, opts.mode == FstReadOptions::MAP, opts.source, b));
483  if (!strm || !data->compacts_region_) {
484  LOG(ERROR) << "CompactArcStore::Read: Read failed: " << opts.source;
485  return nullptr;
486  }
487  data->compacts_ =
488  static_cast<Element *>(data->compacts_region_->mutable_data());
489  return data.release();
490 }
491 
492 template <class Element, class Unsigned>
494  std::ostream &strm, const FstWriteOptions &opts) const {
495  if (states_) {
496  if (opts.align && !AlignOutput(strm)) {
497  LOG(ERROR) << "CompactArcStore::Write: Alignment failed: " << opts.source;
498  return false;
499  }
500  strm.write(reinterpret_cast<const char *>(states_),
501  (nstates_ + 1) * sizeof(Unsigned));
502  }
503  if (opts.align && !AlignOutput(strm)) {
504  LOG(ERROR) << "CompactArcStore::Write: Alignment failed: " << opts.source;
505  return false;
506  }
507  strm.write(reinterpret_cast<const char *>(compacts_),
508  ncompacts_ * sizeof(Element));
509  strm.flush();
510  if (!strm) {
511  LOG(ERROR) << "CompactArcStore::Write: Write failed: " << opts.source;
512  return false;
513  }
514  return true;
515 }
516 
517 template <class Element, class Unsigned>
519  static const std::string *const type = new std::string("compact");
520  return *type;
521 }
522 
523 template <class C, class U, class S>
525 
526 // Wraps an old-style arc compactor and a compact store as a new Fst compactor.
527 // The copy constructors of AC and S must make thread-safe copies and should
528 // be O(1).
529 template <class AC, class U,
530  class S /*= CompactArcStore<typename AC::Element, U>*/>
532  public:
533  using ArcCompactor = AC;
534  using Unsigned = U;
535  using CompactStore = S;
536  using Element = typename AC::Element;
537  using Arc = typename AC::Arc;
538  using StateId = typename Arc::StateId;
539  using Weight = typename Arc::Weight;
541  friend State;
542 
543  CompactArcCompactor() : arc_compactor_(nullptr), compact_store_(nullptr) {}
544 
545  // Constructs from Fst.
547  ArcCompactor &&arc_compactor = ArcCompactor())
549  fst, std::make_shared<ArcCompactor>(std::move(arc_compactor))) {}
550 
552  std::shared_ptr<ArcCompactor> arc_compactor)
553  : arc_compactor_(std::move(arc_compactor)),
554  compact_store_(std::make_shared<S>(fst, *arc_compactor_)) {}
555 
557  std::shared_ptr<CompactArcCompactor> compactor)
558  : arc_compactor_(compactor->arc_compactor_),
559  compact_store_(compactor->compact_store_ == nullptr
560  ? std::make_shared<S>(fst, *arc_compactor_)
561  : compactor->compact_store_) {}
562 
563  // Constructs from CompactStore.
564  CompactArcCompactor(std::shared_ptr<ArcCompactor> arc_compactor,
565  std::shared_ptr<CompactStore> compact_store)
566  : arc_compactor_(std::move(arc_compactor)),
567  compact_store_(std::move(compact_store)) {}
568 
569  // The following 2 constructors take as input two iterators delimiting a set
570  // of (already) compacted transitions, starting with the transitions out of
571  // the initial state. The format of the input differs for fixed out-degree
572  // and variable out-degree arc compactors.
573  //
574  // - For fixed out-degree arc compactors, the final weight (encoded as a
575  // compacted transition) needs to be given only for final states. All strings
576  // (arc compactor of size 1) will be assume to be terminated by a final state
577  // even when the final state is not implicitely given.
578  //
579  // - For variable out-degree arc compactors, the final weight (encoded as a
580  // compacted transition) needs to be given for all states and must appeared
581  // first in the list (for state s, final weight of s, followed by outgoing
582  // transitons in s).
583  //
584  // These 2 constructors allows the direct construction of a CompactArcFst
585  // without first creating a more memory-hungry regular FST. This is useful
586  // when memory usage is severely constrained.
587  //
588  // Usage:
589  // CompactArcFst<...> fst(
590  // std::make_shared<CompactArcFst<...>::Compactor>(b, e));
591  template <class Iterator>
592  CompactArcCompactor(const Iterator b, const Iterator e,
593  std::shared_ptr<ArcCompactor> arc_compactor)
594  : arc_compactor_(std::move(arc_compactor)),
595  compact_store_(std::make_shared<S>(b, e, *arc_compactor_)) {}
596 
597  template <class Iterator>
598  CompactArcCompactor(const Iterator b, const Iterator e)
599  : CompactArcCompactor(b, e, std::make_shared<ArcCompactor>()) {}
600 
601  // Copy constructor. This makes a thread-safe copy, so requires that
602  // The ArcCompactor and CompactStore copy constructors make thread-safe
603  // copies.
605  : arc_compactor_(
606  compactor.GetArcCompactor() == nullptr
607  ? nullptr
608  : std::make_shared<ArcCompactor>(*compactor.GetArcCompactor())),
609  compact_store_(compactor.GetCompactStore() == nullptr
610  ? nullptr
611  : std::make_shared<CompactStore>(
612  *compactor.GetCompactStore())) {}
613 
614  template <class OtherC>
616  const CompactArcCompactor<OtherC, U, S> &compactor)
617  : arc_compactor_(
618  compactor.GetArcCompactor() == nullptr
619  ? nullptr
620  : std::make_shared<ArcCompactor>(*compactor.GetArcCompactor())),
621  compact_store_(compactor.GetCompactStore() == nullptr
622  ? nullptr
623  : std::make_shared<CompactStore>(
624  *compactor.GetCompactStore())) {}
625 
626  StateId Start() const { return compact_store_->Start(); }
627  StateId NumStates() const { return compact_store_->NumStates(); }
628  size_t NumArcs() const { return compact_store_->NumArcs(); }
629 
630  void SetState(StateId s, State *state) const {
631  if (state->GetStateId() != s) state->Set(this, s);
632  }
633 
634  static CompactArcCompactor *Read(std::istream &strm,
635  const FstReadOptions &opts,
636  const FstHeader &hdr) {
637  std::shared_ptr<ArcCompactor> arc_compactor(ArcCompactor::Read(strm));
638  if (arc_compactor == nullptr) return nullptr;
639  std::shared_ptr<S> compact_store(S::Read(strm, opts, hdr, *arc_compactor));
640  if (compact_store == nullptr) return nullptr;
641  return new CompactArcCompactor(arc_compactor, compact_store);
642  }
643 
644  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
645  return arc_compactor_->Write(strm) && compact_store_->Write(strm, opts);
646  }
647 
648  uint64_t Properties(uint64_t props) const {
649  // ArcCompactor properties can just be or-ed in since it is assumed that
650  // if the ArcCompactor sets a property, any FST with the inverse
651  // property is incompatible.
652  return arc_compactor_->Properties() | props;
653  }
654 
655  bool IsCompatible(const Fst<Arc> &fst) const {
656  return arc_compactor_->Compatible(fst);
657  }
658 
659  bool Error() const { return compact_store_->Error(); }
660 
661  bool HasFixedOutdegree() const { return arc_compactor_->Size() != -1; }
662 
663  static const std::string &Type() {
664  static const std::string *const type = [] {
665  std::string type = "compact";
666  if (sizeof(U) != sizeof(uint32_t)) type += std::to_string(8 * sizeof(U));
667  type += "_";
668  type += ArcCompactor::Type();
669  if (CompactStore::Type() != "compact") {
670  type += "_";
671  type += CompactStore::Type();
672  }
673  return new std::string(type);
674  }();
675  return *type;
676  }
677 
678  const ArcCompactor *GetArcCompactor() const { return arc_compactor_.get(); }
679  const CompactStore *GetCompactStore() const { return compact_store_.get(); }
680 
681  ArcCompactor *MutableArcCompactor() { return arc_compactor_.get(); }
682  CompactStore *MutableCompactStore() { return compact_store_.get(); }
683 
684  std::shared_ptr<ArcCompactor> SharedArcCompactor() { return arc_compactor_; }
685  std::shared_ptr<CompactStore> SharedCompactStore() { return compact_store_; }
686 
687  // TODO(allauzen): remove dependencies on this method and make private.
688  Arc ComputeArc(StateId s, Unsigned i, uint8_t flags) const {
689  return arc_compactor_->Expand(s, compact_store_->Compacts(i), flags);
690  }
691 
692  private:
693  std::pair<Unsigned, Unsigned> CompactsRange(StateId s) const {
694  std::pair<size_t, size_t> range;
695  if (HasFixedOutdegree()) {
696  range.first = s * arc_compactor_->Size();
697  range.second = arc_compactor_->Size();
698  } else {
699  range.first = compact_store_->States(s);
700  range.second = compact_store_->States(s + 1) - range.first;
701  }
702  return range;
703  }
704 
705  private:
706  std::shared_ptr<ArcCompactor> arc_compactor_;
707  std::shared_ptr<CompactStore> compact_store_;
708 };
709 
710 // Default implementation of state attributes accessor class for
711 // CompactArcCompactor. Use of efficient specialization strongly encouraged.
712 template <class ArcCompactor, class U, class S>
713 class CompactArcState {
714  public:
715  using Arc = typename ArcCompactor::Arc;
716  using StateId = typename Arc::StateId;
717  using Weight = typename Arc::Weight;
719 
720  CompactArcState() = default;
721 
722  CompactArcState(const Compactor *compactor, StateId s)
723  : compactor_(compactor),
724  s_(s),
725  range_(compactor->CompactsRange(s)),
726  has_final_(
727  range_.second != 0 &&
728  compactor->ComputeArc(s, range_.first, kArcILabelValue).ilabel ==
729  kNoLabel) {
730  if (has_final_) {
731  ++range_.first;
732  --range_.second;
733  }
734  }
735 
736  void Set(const Compactor *compactor, StateId s) {
737  compactor_ = compactor;
738  s_ = s;
739  range_ = compactor->CompactsRange(s);
740  if (range_.second != 0 &&
741  compactor->ComputeArc(s, range_.first, kArcILabelValue).ilabel ==
742  kNoLabel) {
743  has_final_ = true;
744  ++range_.first;
745  --range_.second;
746  } else {
747  has_final_ = false;
748  }
749  }
750 
751  StateId GetStateId() const { return s_; }
752 
753  Weight Final() const {
754  if (!has_final_) return Weight::Zero();
755  return compactor_->ComputeArc(s_, range_.first - 1, kArcWeightValue).weight;
756  }
757 
758  size_t NumArcs() const { return range_.second; }
759 
760  Arc GetArc(size_t i, uint8_t flags) const {
761  return compactor_->ComputeArc(s_, range_.first + i, flags);
762  }
763 
764  private:
765  const Compactor *compactor_ = nullptr; // borrowed ref.
766  StateId s_ = kNoStateId;
767  std::pair<U, U> range_ = {0, 0};
768  bool has_final_ = false;
769 };
770 
771 // Specialization for CompactArcStore.
772 template <class ArcCompactor, class U>
773 class CompactArcState<ArcCompactor, U,
774  CompactArcStore<typename ArcCompactor::Element, U>> {
775  public:
776  using Arc = typename ArcCompactor::Arc;
777  using StateId = typename Arc::StateId;
778  using Weight = typename Arc::Weight;
781 
782  CompactArcState() = default;
783 
784  CompactArcState(const Compactor *compactor, StateId s)
785  : arc_compactor_(compactor->GetArcCompactor()), s_(s) {
786  Init(compactor);
787  }
788 
789  void Set(const Compactor *compactor, StateId s) {
790  arc_compactor_ = compactor->GetArcCompactor();
791  s_ = s;
792  has_final_ = false;
793  Init(compactor);
794  }
795 
796  StateId GetStateId() const { return s_; }
797 
798  Weight Final() const {
799  if (!has_final_) return Weight::Zero();
800  return arc_compactor_->Expand(s_, *(compacts_ - 1), kArcWeightValue).weight;
801  }
802 
803  size_t NumArcs() const { return num_arcs_; }
804 
805  Arc GetArc(size_t i, uint8_t flags) const {
806  return arc_compactor_->Expand(s_, compacts_[i], flags);
807  }
808 
809  private:
810  void Init(const Compactor *compactor) {
811  const auto *store = compactor->GetCompactStore();
812  U offset;
813  if (!compactor->HasFixedOutdegree()) { // Variable out-degree compactor.
814  offset = store->States(s_);
815  num_arcs_ = store->States(s_ + 1) - offset;
816  } else { // Fixed out-degree compactor.
817  offset = s_ * arc_compactor_->Size();
818  num_arcs_ = arc_compactor_->Size();
819  }
820  if (num_arcs_ > 0) {
821  compacts_ = &(store->Compacts(offset));
822  if (arc_compactor_->Expand(s_, *compacts_, kArcILabelValue).ilabel ==
823  kNoStateId) {
824  ++compacts_;
825  --num_arcs_;
826  has_final_ = true;
827  }
828  }
829  }
830 
831  private:
832  const ArcCompactor *arc_compactor_ = nullptr; // Borrowed reference.
833  const typename ArcCompactor::Element *compacts_ =
834  nullptr; // Borrowed reference.
835  StateId s_ = kNoStateId;
836  U num_arcs_ = 0;
837  bool has_final_ = false;
838 };
839 
840 template <class F, class G>
841 void Cast(const F &, G *);
842 
843 template <class CompactArcFST, class FST>
844 bool WriteCompactArcFst(
845  const FST &fst,
846  const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor,
847  std::ostream &strm, const FstWriteOptions &opts);
848 
849 namespace internal {
850 
851 // Implementation class for CompactFst, which contains parametrizeable
852 // Fst data storage (CompactArcStore by default) and Fst cache.
853 // C's copy constructor must make a thread-safe copy.
854 template <class Arc, class C, class CacheStore = DefaultCacheStore<Arc>>
856  : public CacheBaseImpl<typename CacheStore::State, CacheStore> {
857  public:
858  using Weight = typename Arc::Weight;
859  using StateId = typename Arc::StateId;
860  using Compactor = C;
861 
862  using FstImpl<Arc>::SetType;
868 
870  using ImplBase::HasArcs;
871  using ImplBase::HasFinal;
872  using ImplBase::HasStart;
873  using ImplBase::PushArc;
874  using ImplBase::SetArcs;
875  using ImplBase::SetFinal;
876  using ImplBase::SetStart;
877 
880  compactor_(std::make_shared<Compactor>()) {
881  SetType(Compactor::Type());
882  SetProperties(kNullProperties | kStaticProperties);
883  }
884 
885  // Constructs a CompactFstImpl, creating a new Compactor using
886  // Compactor(fst, compactor); this uses the compactor arg only for optional
887  // information, such as compression level. See the Compactor interface
888  // description.
889  CompactFstImpl(const Fst<Arc> &fst, std::shared_ptr<Compactor> compactor,
890  const CompactFstOptions &opts)
891  : ImplBase(opts),
892  compactor_(std::make_shared<Compactor>(fst, std::move(compactor))) {
893  SetType(Compactor::Type());
894  SetInputSymbols(fst.InputSymbols());
895  SetOutputSymbols(fst.OutputSymbols());
896  if (compactor_->Error()) SetProperties(kError, kError);
897  uint64_t copy_properties =
898  fst.Properties(kMutable, false)
899  ? fst.Properties(kCopyProperties, true)
900  : CheckProperties(
903  if ((copy_properties & kError) || !compactor_->IsCompatible(fst)) {
904  FSTERROR() << "CompactFstImpl: Input Fst incompatible with compactor";
905  SetProperties(kError, kError);
906  return;
907  }
908  SetProperties(compactor_->Properties(copy_properties) | kStaticProperties);
909  }
910 
911  CompactFstImpl(std::shared_ptr<Compactor> compactor,
912  const CompactFstOptions &opts)
913  : ImplBase(opts), compactor_(std::move(compactor)) {
914  SetType(Compactor::Type());
915  SetProperties(kStaticProperties | compactor_->Properties(0));
916  if (compactor_->Error()) SetProperties(kError, kError);
917  }
918 
919  // Makes a thread-safe copy; requires that Compactor's copy constructor
920  // does so as well.
922  : ImplBase(impl),
923  compactor_(impl.compactor_ == nullptr
924  ? std::make_shared<Compactor>()
925  : std::make_shared<Compactor>(*impl.compactor_)) {
926  SetType(impl.Type());
927  SetProperties(impl.Properties());
928  SetInputSymbols(impl.InputSymbols());
929  SetOutputSymbols(impl.OutputSymbols());
930  }
931 
932  // Allows to change the cache store from OtherCacheStore to CacheStore.
933  template <class OtherCacheStore>
934  explicit CompactFstImpl(
936  : ImplBase(CacheOptions(impl.GetCacheGc(), impl.GetCacheLimit())),
937  compactor_(impl.compactor_ == nullptr
938  ? std::make_shared<Compactor>()
939  : std::make_shared<Compactor>(*impl.compactor_)) {
940  SetType(impl.Type());
941  SetProperties(impl.Properties());
942  SetInputSymbols(impl.InputSymbols());
943  SetOutputSymbols(impl.OutputSymbols());
944  }
945 
947  if (!HasStart()) SetStart(compactor_->Start());
948  return ImplBase::Start();
949  }
950 
952  if (HasFinal(s)) return ImplBase::Final(s);
953  compactor_->SetState(s, &state_);
954  return state_.Final();
955  }
956 
957  StateId NumStates() const {
958  if (Properties(kError)) return 0;
959  return compactor_->NumStates();
960  }
961 
962  size_t NumArcs(StateId s) {
963  if (HasArcs(s)) return ImplBase::NumArcs(s);
964  compactor_->SetState(s, &state_);
965  return state_.NumArcs();
966  }
967 
969  if (!HasArcs(s) && !Properties(kILabelSorted)) Expand(s);
970  if (HasArcs(s)) return ImplBase::NumInputEpsilons(s);
971  return CountEpsilons(s, false);
972  }
973 
975  if (!HasArcs(s) && !Properties(kOLabelSorted)) Expand(s);
976  if (HasArcs(s)) return ImplBase::NumOutputEpsilons(s);
977  return CountEpsilons(s, true);
978  }
979 
980  size_t CountEpsilons(StateId s, bool output_epsilons) {
981  compactor_->SetState(s, &state_);
982  const uint8_t flags = output_epsilons ? kArcOLabelValue : kArcILabelValue;
983  size_t num_eps = 0;
984  const size_t num_arcs = state_.NumArcs();
985  for (size_t i = 0; i < num_arcs; ++i) {
986  const auto &arc = state_.GetArc(i, flags);
987  const auto label = output_epsilons ? arc.olabel : arc.ilabel;
988  if (label == 0) {
989  ++num_eps;
990  } else if (label > 0) {
991  break;
992  }
993  }
994  return num_eps;
995  }
996 
997  static CompactFstImpl *Read(std::istream &strm, const FstReadOptions &opts) {
998  auto impl = std::make_unique<CompactFstImpl>();
999  FstHeader hdr;
1000  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) {
1001  return nullptr;
1002  }
1003  // Ensures compatibility.
1004  if (hdr.Version() == kAlignedFileVersion) {
1005  hdr.SetFlags(hdr.GetFlags() | FstHeader::IS_ALIGNED);
1006  }
1007  impl->compactor_ =
1008  std::shared_ptr<Compactor>(Compactor::Read(strm, opts, hdr));
1009  if (!impl->compactor_) {
1010  return nullptr;
1011  }
1012  return impl.release();
1013  }
1014 
1015  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
1016  FstHeader hdr;
1017  hdr.SetStart(compactor_->Start());
1018  hdr.SetNumStates(compactor_->NumStates());
1019  hdr.SetNumArcs(compactor_->NumArcs());
1020  // Ensures compatibility.
1021  const auto file_version = opts.align ? kAlignedFileVersion : kFileVersion;
1022  WriteHeader(strm, opts, file_version, &hdr);
1023  return compactor_->Write(strm, opts);
1024  }
1025 
1026  // Provides information needed for generic state iterator.
1028  data->base = nullptr;
1029  data->nstates = compactor_->NumStates();
1030  }
1031 
1033  if (!HasArcs(s)) Expand(s);
1034  ImplBase::InitArcIterator(s, data);
1035  }
1036 
1037  void Expand(StateId s) {
1038  compactor_->SetState(s, &state_);
1039  const size_t num_arcs = state_.NumArcs();
1040  for (size_t i = 0; i < num_arcs; ++i)
1041  PushArc(s, state_.GetArc(i, kArcValueFlags));
1042  SetArcs(s);
1043  if (!HasFinal(s)) SetFinal(s, state_.Final());
1044  }
1045 
1046  const Compactor *GetCompactor() const { return compactor_.get(); }
1047  Compactor *MutableCompactor() { return compactor_.get(); }
1048  std::shared_ptr<Compactor> SharedCompactor() { return compactor_; }
1049  void SetCompactor(std::shared_ptr<Compactor> compactor) {
1050  // TODO(allauzen): is this correct? is this needed?
1051  // TODO(allauzen): consider removing and forcing this through direct calls
1052  // to compactor.
1053  compactor_ = std::move(compactor);
1054  }
1055 
1056  // Properties always true of this FST class.
1057  static constexpr uint64_t kStaticProperties = kExpanded;
1058 
1059  protected:
1060  template <class OtherArc, class OtherCompactor, class OtherCacheStore>
1061  explicit CompactFstImpl(
1063  : compactor_(std::make_shared<Compactor>(*impl.GetCompactor())) {
1064  SetType(impl.Type());
1065  SetProperties(impl.Properties());
1066  SetInputSymbols(impl.InputSymbols());
1067  SetOutputSymbols(impl.OutputSymbols());
1068  }
1069 
1070  private:
1071  // For k*Version constants.
1072  template <class CompactArcFST, class FST>
1074  const FST &fst,
1075  const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor,
1076  std::ostream &strm, const FstWriteOptions &opts);
1077 
1078  // Current unaligned file format version.
1079  static constexpr int kFileVersion = 2;
1080  // Current aligned file format version.
1081  static constexpr int kAlignedFileVersion = 1;
1082  // Minimum file format version supported.
1083  static constexpr int kMinFileVersion = 1;
1084 
1085  std::shared_ptr<Compactor> compactor_;
1086  typename Compactor::State state_;
1087 };
1088 
1089 // Returns the compactor for the CompactFst; intended to be called as
1090 // GetCompactor<CompactorType>(fst), which returns the compactor only if it
1091 // is of the specified type and otherwise nullptr (via the overload below).
1092 template <class Compactor, class Arc>
1093 const Compactor *GetCompactor(const CompactFst<Arc, Compactor> &fst) {
1094  return fst.GetCompactor();
1095 }
1096 
1097 template <class Compactor, class Arc>
1098 const Compactor *GetCompactor(const Fst<Arc> &fst) {
1099  return nullptr;
1100 }
1101 
1102 } // namespace internal
1103 
1104 // This class attaches interface to implementation and handles reference
1105 // counting, delegating most methods to ImplToExpandedFst.
1106 // (Template argument defaults are declared in fst-decl.h.)
1107 template <class A, class C, class CacheStore>
1109  : public ImplToExpandedFst<internal::CompactFstImpl<A, C, CacheStore>> {
1110  public:
1111  template <class F, class G>
1112  void friend Cast(const F &, G *);
1113 
1114  using Arc = A;
1115  using StateId = typename Arc::StateId;
1116  using Compactor = C;
1118  using Store = CacheStore; // for CacheArcIterator
1119 
1120  friend class StateIterator<CompactFst>;
1121  friend class ArcIterator<CompactFst>;
1122 
1123  CompactFst() : ImplToExpandedFst<Impl>(std::make_shared<Impl>()) {}
1124 
1125  explicit CompactFst(const Fst<Arc> &fst,
1126  const CompactFstOptions &opts = CompactFstOptions())
1127  : CompactFst(fst, std::make_shared<Compactor>(fst), opts) {}
1128 
1129  // Constructs a CompactFst, creating a new Compactor using
1130  // Compactor(fst, compactor); this uses the compactor arg only for optional
1131  // information, such as compression level. See the Compactor interface
1132  // description.
1133  CompactFst(const Fst<Arc> &fst, std::shared_ptr<Compactor> compactor,
1134  const CompactFstOptions &opts = CompactFstOptions())
1136  std::make_shared<Impl>(fst, std::move(compactor), opts)) {}
1137 
1138  // Convenience constructor taking a Compactor rvalue ref. Avoids
1139  // clutter of make_shared<Compactor> at call site.
1140  // Constructs a CompactFst, creating a new Compactor using
1141  // Compactor(fst, compactor); this uses the compactor arg only for optional
1142  // information, such as compression level. See the Compactor interface
1143  // description.
1144  CompactFst(const Fst<Arc> &fst, Compactor &&compactor,
1145  const CompactFstOptions &opts = CompactFstOptions())
1146  : CompactFst(fst, std::make_shared<Compactor>(std::move(compactor)),
1147  opts) {}
1148 
1149  explicit CompactFst(std::shared_ptr<Compactor> compactor,
1150  const CompactFstOptions &opts = CompactFstOptions())
1152  std::make_shared<Impl>(std::move(compactor), opts)) {}
1153 
1154  // See Fst<>::Copy() for doc.
1155  CompactFst(const CompactFst &fst, bool safe = false)
1156  : ImplToExpandedFst<Impl>(fst, safe) {}
1157 
1158  // Get a copy of this CompactFst. See Fst<>::Copy() for further doc.
1159  CompactFst *Copy(bool safe = false) const override {
1160  return new CompactFst(*this, safe);
1161  }
1162 
1163  // Read a CompactFst from an input stream; return nullptr on error
1164  static CompactFst *Read(std::istream &strm, const FstReadOptions &opts) {
1165  auto *impl = Impl::Read(strm, opts);
1166  return impl ? new CompactFst(std::shared_ptr<Impl>(impl)) : nullptr;
1167  }
1168 
1169  // Read a CompactFst from a file; return nullptr on error
1170  // Empty source reads from standard input
1171  static CompactFst *Read(std::string_view source) {
1172  auto *impl = ImplToExpandedFst<Impl>::Read(source);
1173  return impl ? new CompactFst(std::shared_ptr<Impl>(impl)) : nullptr;
1174  }
1175 
1176  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
1177  return GetImpl()->Write(strm, opts);
1178  }
1179 
1180  bool Write(const std::string &source) const override {
1181  return Fst<Arc>::WriteFile(source);
1182  }
1183 
1184  void InitStateIterator(StateIteratorData<Arc> *data) const override {
1185  GetImpl()->InitStateIterator(data);
1186  }
1187 
1188  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
1189  GetMutableImpl()->InitArcIterator(s, data);
1190  }
1191 
1192  MatcherBase<Arc> *InitMatcher(MatchType match_type) const override {
1193  return new SortedMatcher<CompactFst>(*this, match_type);
1194  }
1195 
1196  const Compactor *GetCompactor() const { return GetImpl()->GetCompactor(); }
1197 
1198  void SetCompactor(std::shared_ptr<Compactor> compactor) {
1199  GetMutableImpl()->SetCompactor(std::move(compactor));
1200  }
1201 
1202  private:
1203  using ImplToFst<Impl, ExpandedFst<Arc>>::GetImpl;
1204  using ImplToFst<Impl, ExpandedFst<Arc>>::GetMutableImpl;
1205 
1206  explicit CompactFst(std::shared_ptr<Impl> impl)
1207  : ImplToExpandedFst<Impl>(std::move(impl)) {}
1208 
1209  CompactFst &operator=(const CompactFst &fst) = delete;
1210 };
1211 
1212 // Writes FST in ArcCompacted format, with a possible pass over the machine
1213 // before writing to compute the number of states and arcs.
1214 template <class CompactArcFST, class FST>
1216  const FST &fst,
1217  const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor,
1218  std::ostream &strm, const FstWriteOptions &opts) {
1219  using Arc = typename CompactArcFST::Arc;
1220  using Compactor = typename CompactArcFST::Compactor;
1221  using ArcCompactor = typename Compactor::ArcCompactor;
1222  using CompactStore = typename Compactor::CompactStore;
1223  using Element = typename ArcCompactor::Element;
1224  using Impl = typename CompactArcFST::Impl;
1225  using Unsigned = typename Compactor::Unsigned;
1226  using Weight = typename Arc::Weight;
1227  const auto file_version =
1228  opts.align ? Impl::kAlignedFileVersion : Impl::kFileVersion;
1229  size_t num_arcs = -1;
1230  size_t num_states = -1;
1231  auto first_pass_arc_compactor = arc_compactor;
1232  // Note that GetCompactor will only return non-null if the compactor has the
1233  // exact type Compactor == CompactArcFst::Compactor. This is what we want;
1234  // other types must do an extra pass to set the arc compactor state.
1235  if (const Compactor *const compactor =
1236  internal::GetCompactor<Compactor>(fst)) {
1237  num_arcs = compactor->NumArcs();
1238  num_states = compactor->NumStates();
1239  first_pass_arc_compactor = *compactor->GetArcCompactor();
1240  } else {
1241  // A first pass is needed to compute the state of the compactor, which
1242  // is saved ahead of the rest of the data structures. This unfortunately
1243  // means forcing a complete double compaction when writing in this format.
1244  // TODO(allauzen): eliminate mutable state from compactors.
1245  num_arcs = 0;
1246  num_states = 0;
1247  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
1248  const auto s = siter.Value();
1249  ++num_states;
1250  if (fst.Final(s) != Weight::Zero()) {
1251  first_pass_arc_compactor.Compact(
1252  s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
1253  }
1254  for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
1255  ++num_arcs;
1256  first_pass_arc_compactor.Compact(s, aiter.Value());
1257  }
1258  }
1259  }
1260  FstHeader hdr;
1261  hdr.SetStart(fst.Start());
1262  hdr.SetNumStates(num_states);
1263  hdr.SetNumArcs(num_arcs);
1264  std::string type = "compact";
1265  if (sizeof(Unsigned) != sizeof(uint32_t)) {
1266  type += std::to_string(CHAR_BIT * sizeof(Unsigned));
1267  }
1268  type += "_";
1269  type += ArcCompactor::Type();
1270  if (CompactStore::Type() != "compact") {
1271  type += "_";
1272  type += CompactStore::Type();
1273  }
1274  const auto copy_properties = fst.Properties(kCopyProperties, true);
1275  if ((copy_properties & kError) || !arc_compactor.Compatible(fst)) {
1276  FSTERROR() << "Fst incompatible with compactor";
1277  return false;
1278  }
1279  uint64_t properties = copy_properties | Impl::kStaticProperties;
1280  internal::FstImpl<Arc>::WriteFstHeader(fst, strm, opts, file_version, type,
1281  properties, &hdr);
1282  first_pass_arc_compactor.Write(strm);
1283  if (first_pass_arc_compactor.Size() == -1) {
1284  if (opts.align && !AlignOutput(strm)) {
1285  LOG(ERROR) << "WriteCompactArcFst: Alignment failed: " << opts.source;
1286  return false;
1287  }
1288  Unsigned compacts = 0;
1289  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
1290  const auto s = siter.Value();
1291  strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
1292  if (fst.Final(s) != Weight::Zero()) {
1293  ++compacts;
1294  }
1295  compacts += fst.NumArcs(s);
1296  }
1297  strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
1298  }
1299  if (opts.align && !AlignOutput(strm)) {
1300  LOG(ERROR) << "Could not align file during write after writing states";
1301  }
1302  const auto &second_pass_arc_compactor = arc_compactor;
1303  Element element;
1304  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
1305  const auto s = siter.Value();
1306  if (fst.Final(s) != Weight::Zero()) {
1307  element = second_pass_arc_compactor.Compact(
1308  s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
1309  strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
1310  }
1311  for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
1312  element = second_pass_arc_compactor.Compact(s, aiter.Value());
1313  strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
1314  }
1315  }
1316  strm.flush();
1317  if (!strm) {
1318  LOG(ERROR) << "WriteCompactArcFst: Write failed: " << opts.source;
1319  return false;
1320  }
1321  return true;
1322 }
1323 
1324 // Specialization for CompactFst; see generic version in fst.h for sample
1325 // usage (but use the CompactFst type!). This version should inline.
1326 template <class Arc, class Compactor, class CacheStore>
1327 class StateIterator<CompactFst<Arc, Compactor, CacheStore>> {
1328  public:
1329  using StateId = typename Arc::StateId;
1330 
1332  : nstates_(fst.NumStates()), s_(0) {}
1333 
1334  bool Done() const { return s_ >= nstates_; }
1335 
1336  StateId Value() const { return s_; }
1337 
1338  void Next() { ++s_; }
1339 
1340  void Reset() { s_ = 0; }
1341 
1342  private:
1343  StateId nstates_;
1344  StateId s_;
1345 };
1346 
1347 // Specialization for CompactFst. Never caches,
1348 // always iterates over the underlying compact elements.
1349 template <class Arc, class Compactor, class CacheStore>
1350 class ArcIterator<CompactFst<Arc, Compactor, CacheStore>> {
1351  public:
1352  using StateId = typename Arc::StateId;
1353  using State = typename Compactor::State;
1354 
1356  : state_(fst.GetMutableImpl()->MutableCompactor(), s),
1357  pos_(0),
1358  num_arcs_(state_.NumArcs()),
1359  flags_(kArcValueFlags) {}
1360 
1361  bool Done() const { return pos_ >= num_arcs_; }
1362 
1363  const Arc &Value() const {
1364  arc_ = state_.GetArc(pos_, flags_);
1365  return arc_;
1366  }
1367 
1368  void Next() { ++pos_; }
1369 
1370  size_t Position() const { return pos_; }
1371 
1372  void Reset() { pos_ = 0; }
1373 
1374  void Seek(size_t pos) { pos_ = pos; }
1375 
1376  uint8_t Flags() const { return flags_; }
1377 
1378  void SetFlags(uint8_t flags, uint8_t mask) {
1379  flags_ &= ~mask;
1380  flags_ |= (flags & kArcValueFlags);
1381  }
1382 
1383  private:
1384  State state_;
1385  size_t pos_;
1386  // Cache the value of NumArcs(), since it is used in Done() and may be slow.
1387  size_t num_arcs_;
1388  mutable Arc arc_;
1389  uint8_t flags_;
1390 };
1391 
1392 // ArcCompactor for unweighted string FSTs.
1393 template <class A>
1395  public:
1396  using Arc = A;
1397  using Label = typename Arc::Label;
1398  using StateId = typename Arc::StateId;
1399  using Weight = typename Arc::Weight;
1400 
1401  using Element = Label;
1402 
1403  Element Compact(StateId s, const Arc &arc) const { return arc.ilabel; }
1404 
1405  Arc Expand(StateId s, const Element &p,
1406  uint8_t flags = kArcValueFlags) const {
1407  return Arc(p, p, Weight::One(), p != kNoLabel ? s + 1 : kNoStateId);
1408  }
1409 
1410  constexpr ssize_t Size() const { return 1; }
1411 
1412  constexpr uint64_t Properties() const { return kCompiledStringProperties; }
1413 
1414  bool Compatible(const Fst<Arc> &fst) const {
1415  const auto props = Properties();
1416  return fst.Properties(props, true) == props;
1417  }
1418 
1419  static const std::string &Type() {
1420  static const std::string *const type = new std::string("string");
1421  return *type;
1422  }
1423 
1424  bool Write(std::ostream &strm) const { return true; }
1425 
1426  static StringCompactor *Read(std::istream &strm) {
1427  return new StringCompactor;
1428  }
1429 };
1430 
1431 // ArcCompactor for weighted string FSTs.
1432 template <class A>
1434  public:
1435  using Arc = A;
1436  using Label = typename Arc::Label;
1437  using StateId = typename Arc::StateId;
1438  using Weight = typename Arc::Weight;
1439 
1440  using Element = std::pair<Label, Weight>;
1441 
1442  Element Compact(StateId s, const Arc &arc) const {
1443  return std::make_pair(arc.ilabel, arc.weight);
1444  }
1445 
1446  Arc Expand(StateId s, const Element &p,
1447  uint8_t flags = kArcValueFlags) const {
1448  return Arc(p.first, p.first, p.second,
1449  p.first != kNoLabel ? s + 1 : kNoStateId);
1450  }
1451 
1452  constexpr ssize_t Size() const { return 1; }
1453 
1454  constexpr uint64_t Properties() const { return kString | kAcceptor; }
1455 
1456  bool Compatible(const Fst<Arc> &fst) const {
1457  const auto props = Properties();
1458  return fst.Properties(props, true) == props;
1459  }
1460 
1461  static const std::string &Type() {
1462  static const std::string *const type = new std::string("weighted_string");
1463  return *type;
1464  }
1465 
1466  bool Write(std::ostream &strm) const { return true; }
1467 
1468  static WeightedStringCompactor *Read(std::istream &strm) {
1469  return new WeightedStringCompactor;
1470  }
1471 };
1472 
1473 // ArcCompactor for unweighted acceptor FSTs.
1474 template <class A>
1476  public:
1477  using Arc = A;
1478  using Label = typename Arc::Label;
1479  using StateId = typename Arc::StateId;
1480  using Weight = typename Arc::Weight;
1481 
1482  using Element = std::pair<Label, StateId>;
1483 
1484  Element Compact(StateId s, const Arc &arc) const {
1485  return std::make_pair(arc.ilabel, arc.nextstate);
1486  }
1487 
1488  Arc Expand(StateId s, const Element &p,
1489  uint8_t flags = kArcValueFlags) const {
1490  return Arc(p.first, p.first, Weight::One(), p.second);
1491  }
1492 
1493  constexpr ssize_t Size() const { return -1; }
1494 
1495  constexpr uint64_t Properties() const { return kAcceptor | kUnweighted; }
1496 
1497  bool Compatible(const Fst<Arc> &fst) const {
1498  const auto props = Properties();
1499  return fst.Properties(props, true) == props;
1500  }
1501 
1502  static const std::string &Type() {
1503  static const std::string *const type =
1504  new std::string("unweighted_acceptor");
1505  return *type;
1506  }
1507 
1508  bool Write(std::ostream &strm) const { return true; }
1509 
1510  static UnweightedAcceptorCompactor *Read(std::istream &istrm) {
1511  return new UnweightedAcceptorCompactor;
1512  }
1513 };
1514 
1515 // ArcCompactor for weighted acceptor FSTs.
1516 template <class A>
1518  public:
1519  using Arc = A;
1520  using Label = typename Arc::Label;
1521  using StateId = typename Arc::StateId;
1522  using Weight = typename Arc::Weight;
1523 
1524  using Element = std::pair<std::pair<Label, Weight>, StateId>;
1525 
1526  Element Compact(StateId s, const Arc &arc) const {
1527  return std::make_pair(std::make_pair(arc.ilabel, arc.weight),
1528  arc.nextstate);
1529  }
1530 
1531  Arc Expand(StateId s, const Element &p,
1532  uint8_t flags = kArcValueFlags) const {
1533  return Arc(p.first.first, p.first.first, p.first.second, p.second);
1534  }
1535 
1536  constexpr ssize_t Size() const { return -1; }
1537 
1538  constexpr uint64_t Properties() const { return kAcceptor; }
1539 
1540  bool Compatible(const Fst<Arc> &fst) const {
1541  const auto props = Properties();
1542  return fst.Properties(props, true) == props;
1543  }
1544 
1545  static const std::string &Type() {
1546  static const std::string *const type = new std::string("acceptor");
1547  return *type;
1548  }
1549 
1550  bool Write(std::ostream &strm) const { return true; }
1551 
1552  static AcceptorCompactor *Read(std::istream &strm) {
1553  return new AcceptorCompactor;
1554  }
1555 };
1556 
1557 // ArcCompactor for unweighted FSTs.
1558 template <class A>
1560  public:
1561  using Arc = A;
1562  using Label = typename Arc::Label;
1563  using StateId = typename Arc::StateId;
1564  using Weight = typename Arc::Weight;
1565 
1566  using Element = std::pair<std::pair<Label, Label>, StateId>;
1567 
1568  Element Compact(StateId s, const Arc &arc) const {
1569  return std::make_pair(std::make_pair(arc.ilabel, arc.olabel),
1570  arc.nextstate);
1571  }
1572 
1573  Arc Expand(StateId s, const Element &p,
1574  uint8_t flags = kArcValueFlags) const {
1575  return Arc(p.first.first, p.first.second, Weight::One(), p.second);
1576  }
1577 
1578  constexpr ssize_t Size() const { return -1; }
1579 
1580  constexpr uint64_t Properties() const { return kUnweighted; }
1581 
1582  bool Compatible(const Fst<Arc> &fst) const {
1583  const auto props = Properties();
1584  return fst.Properties(props, true) == props;
1585  }
1586 
1587  static const std::string &Type() {
1588  static const std::string *const type = new std::string("unweighted");
1589  return *type;
1590  }
1591 
1592  bool Write(std::ostream &strm) const { return true; }
1593 
1594  static UnweightedCompactor *Read(std::istream &strm) {
1595  return new UnweightedCompactor;
1596  }
1597 };
1598 
1599 template <class Arc, class Unsigned /* = uint32_t */>
1601 
1602 template <class Arc, class Unsigned /* = uint32_t */>
1605 
1606 template <class Arc, class Unsigned /* = uint32_t */>
1608 
1609 template <class Arc, class Unsigned /* = uint32_t */>
1610 using CompactUnweightedFst =
1612 
1613 template <class Arc, class Unsigned /* = uint32_t */>
1616 
1618 
1620 
1622 
1624 
1627 
1628 // Convenience function to make a CompactStringFst from a sequence
1629 // of Arc::Labels. LabelIterator must be an input iterator.
1630 template <class Arc, class Unsigned = uint32_t, class LabelIterator>
1632  const LabelIterator begin, const LabelIterator end) {
1634  using Compactor = typename CompactStringFst::Compactor;
1635  return CompactStringFst(std::make_shared<Compactor>(begin, end));
1636 }
1637 
1638 template <class LabelIterator>
1639 inline StdCompactStringFst MakeStdCompactStringFst(const LabelIterator begin,
1640  const LabelIterator end) {
1641  return MakeCompactStringFst<StdArc>(begin, end);
1642 }
1643 
1644 } // namespace fst
1645 
1646 #endif // FST_COMPACT_FST_H_
static Impl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: expanded-fst.h:155
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:124
Weight Final() const
Definition: compact-fst.h:753
CompactFstImpl(const Fst< Arc > &fst, std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts)
Definition: compact-fst.h:889
constexpr uint64_t Properties() const
Definition: compact-fst.h:1454
CompactArcCompactor(const Fst< Arc > &fst, std::shared_ptr< ArcCompactor > arc_compactor)
Definition: compact-fst.h:551
bool AlignInput(std::istream &strm, size_t align=MappedFile::kArchAlignment)
Definition: util.cc:85
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: compact-fst.h:1188
const Element & Compacts(size_t i) const
Definition: compact-fst.h:274
constexpr uint64_t kMutable
Definition: properties.h:49
StdCompactStringFst MakeStdCompactStringFst(const LabelIterator begin, const LabelIterator end)
Definition: compact-fst.h:1639
constexpr ssize_t Size() const
Definition: compact-fst.h:1410
constexpr uint64_t kWeightedCycles
Definition: properties.h:142
constexpr uint64_t Properties() const
Definition: compact-fst.h:1538
std::pair< std::pair< Label, Label >, StateId > Element
Definition: compact-fst.h:1566
constexpr uint8_t kArcValueFlags
Definition: fst.h:453
CompactFst(const CompactFst &fst, bool safe=false)
Definition: compact-fst.h:1155
static const std::string & Type()
Definition: compact-fst.h:1587
typename Arc::Weight Weight
Definition: compact-fst.h:1564
constexpr int kNoLabel
Definition: fst.h:195
static UnweightedCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1594
Arc GetArc(size_t i, uint8_t flags) const
Definition: compact-fst.h:760
CompactStore * MutableCompactStore()
Definition: compact-fst.h:682
void Cast(const F &, G *)
bool IsCompatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:655
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1497
virtual uint64_t Properties(uint64_t mask, bool test) const =0
const Compactor * GetCompactor() const
Definition: compact-fst.h:1046
typename Arc::StateId StateId
Definition: compact-fst.h:716
typename Arc::Label Label
Definition: compact-fst.h:1562
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1446
static const std::string & Type()
Definition: compact-fst.h:1461
CompactFst(const Fst< Arc > &fst, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1125
std::shared_ptr< CompactStore > SharedCompactStore()
Definition: compact-fst.h:685
CompactFstOptions(const CacheOptions &opts)
Definition: compact-fst.h:62
virtual size_t NumArcs(StateId) const =0
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1568
CompactFstImpl(std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts)
Definition: compact-fst.h:911
void Set(const Compactor *compactor, StateId s)
Definition: compact-fst.h:736
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1405
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1592
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1403
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1466
std::string source
Definition: fst.h:73
CompactArcCompactor(const CompactArcCompactor &compactor)
Definition: compact-fst.h:604
CompactStringFst< Arc, Unsigned > MakeCompactStringFst(const LabelIterator begin, const LabelIterator end)
Definition: compact-fst.h:1631
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:107
CompactArcFst< Arc, StringCompactor< Arc >, Unsigned > CompactStringFst
Definition: compact-fst.h:1600
const SymbolTable * OutputSymbols() const
Definition: fst.h:761
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1424
MatchType
Definition: fst.h:187
constexpr uint64_t Properties() const
Definition: compact-fst.h:1412
StateId GetStateId() const
Definition: compact-fst.h:751
constexpr uint64_t kError
Definition: properties.h:52
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data)
Definition: compact-fst.h:1032
CompactFst(std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1149
static MappedFile * Map(std::istream &istrm, bool memorymap, const std::string &source, size_t size)
Definition: mapped-file.cc:77
#define LOG(type)
Definition: log.h:53
constexpr uint64_t kCompiledStringProperties
Definition: properties.h:157
virtual Weight Final(StateId) const =0
StateIterator(const CompactFst< Arc, Compactor, CacheStore > &fst)
Definition: compact-fst.h:1331
CompactFst(const Fst< Arc > &fst, Compactor &&compactor, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1144
size_t NumArcs() const
Definition: compact-fst.h:280
SetType
Definition: set-weight.h:59
typename Arc::StateId StateId
Definition: compact-fst.h:1563
void SetNumArcs(int64_t numarcs)
Definition: fst.h:166
constexpr uint64_t kUnweightedCycles
Definition: properties.h:145
CompactArcCompactor(const Fst< Arc > &fst, ArcCompactor &&arc_compactor=ArcCompactor())
Definition: compact-fst.h:546
bool AlignOutput(std::ostream &strm, size_t align=MappedFile::kArchAlignment)
Definition: util.cc:101
CompactArcStore()=default
static AcceptorCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1552
static WeightedStringCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1468
constexpr uint8_t kArcILabelValue
Definition: fst.h:444
ssize_t NumArcs(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:113
CompactFstImpl(const CompactFstImpl &impl)
Definition: compact-fst.h:921
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1573
bool Error() const
Definition: compact-fst.h:284
std::shared_ptr< ArcCompactor > SharedArcCompactor()
Definition: compact-fst.h:684
std::unique_ptr< T > WrapUnique(T *ptr)
Definition: compat.h:132
static CompactFst * Read(std::istream &strm, const FstReadOptions &opts)
Definition: compact-fst.h:1164
MatcherBase< Arc > * InitMatcher(MatchType match_type) const override
Definition: compact-fst.h:1192
size_t NumStates() const
Definition: compact-fst.h:276
typename Arc::Weight Weight
Definition: compact-fst.h:858
CompactFstImpl(const CompactFstImpl< OtherArc, OtherCompactor, OtherCacheStore > &impl)
Definition: compact-fst.h:1061
constexpr int kNoStateId
Definition: fst.h:196
ArcCompactor * MutableArcCompactor()
Definition: compact-fst.h:681
typename Arc::Weight Weight
Definition: compact-fst.h:1522
typename ArcCompactor::Arc Arc
Definition: compact-fst.h:715
void SetState(StateId s, State *state) const
Definition: compact-fst.h:630
static MappedFile * Allocate(size_t size, size_t align=kArchAlignment)
Definition: mapped-file.cc:197
std::pair< Label, StateId > Element
Definition: compact-fst.h:1482
CompactArcCompactor(std::shared_ptr< ArcCompactor > arc_compactor, std::shared_ptr< CompactStore > compact_store)
Definition: compact-fst.h:564
uint32_t GetFlags() const
Definition: fst.h:142
typename AC::Arc Arc
Definition: compact-fst.h:537
static const std::string & Type()
Definition: compact-fst.h:1419
std::string source
Definition: fst.h:102
size_t NumOutputEpsilons(StateId s)
Definition: compact-fst.h:974
#define FSTERROR()
Definition: util.h:56
constexpr uint64_t Properties() const
Definition: compact-fst.h:1580
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:811
static UnweightedAcceptorCompactor * Read(std::istream &istrm)
Definition: compact-fst.h:1510
Unsigned States(ssize_t i) const
Definition: compact-fst.h:270
size_t NumArcs() const
Definition: compact-fst.h:628
CompactFst(const Fst< Arc > &fst, std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1133
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:118
std::pair< Label, Weight > Element
Definition: compact-fst.h:1440
virtual uint64_t Properties() const
Definition: fst.h:701
typename Arc::Label Label
Definition: compact-fst.h:1436
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1456
size_t NumCompacts() const
Definition: compact-fst.h:278
typename Arc::Weight Weight
Definition: compact-fst.h:1399
constexpr uint64_t kOLabelSorted
Definition: properties.h:99
constexpr uint64_t kCopyProperties
Definition: properties.h:163
CompactArcCompactor(const Iterator b, const Iterator e, std::shared_ptr< ArcCompactor > arc_compactor)
Definition: compact-fst.h:592
CompactArcCompactor(const CompactArcCompactor< OtherC, U, S > &compactor)
Definition: compact-fst.h:615
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1531
uint64_t CheckProperties(const Fst< Arc > &fst, uint64_t check_mask, uint64_t test_mask)
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1540
StateId nstates
Definition: fst.h:384
constexpr ssize_t Size() const
Definition: compact-fst.h:1452
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1488
constexpr uint8_t kArcOLabelValue
Definition: fst.h:446
virtual StateId Start() const =0
typename Arc::StateId StateId
Definition: compact-fst.h:859
bool Done() const
Definition: fst.h:532
constexpr ssize_t Size() const
Definition: compact-fst.h:1536
static StringCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1426
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
ArcIterator(const CompactFst< Arc, Compactor, CacheStore > &fst, StateId s)
Definition: compact-fst.h:1355
StateId NumStates() const
Definition: compact-fst.h:627
ssize_t Start() const
Definition: compact-fst.h:282
typename Arc::Weight Weight
Definition: compact-fst.h:1438
typename Arc::StateId StateId
Definition: compact-fst.h:1115
typename Arc::StateId StateId
Definition: compact-fst.h:538
bool WriteCompactArcFst(const FST &fst, const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor, std::ostream &strm, const FstWriteOptions &opts)
Definition: compact-fst.h:1215
typename Arc::Label Label
Definition: compact-fst.h:1520
size_t NumInputEpsilons(StateId s)
Definition: compact-fst.h:968
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: compact-fst.h:1015
constexpr uint64_t kNullProperties
Definition: properties.h:150
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1442
typename Arc::Weight Weight
Definition: compact-fst.h:1480
const std::string & Type() const
Definition: fst.h:697
CompactArcCompactor(const Fst< Arc > &fst, std::shared_ptr< CompactArcCompactor > compactor)
Definition: compact-fst.h:556
CompactFstImpl(const CompactFstImpl< Arc, Compactor, OtherCacheStore > &impl)
Definition: compact-fst.h:934
bool HasFixedOutdegree() const
Definition: compact-fst.h:661
std::pair< std::pair< Label, Weight >, StateId > Element
Definition: compact-fst.h:1524
bool WriteFile(const std::string &source) const
Definition: fst.h:332
constexpr uint8_t kArcWeightValue
Definition: fst.h:448
constexpr uint64_t kILabelSorted
Definition: properties.h:94
int64_t NumArcs() const
Definition: fst.h:150
CompactFst * Copy(bool safe=false) const override
Definition: compact-fst.h:1159
static CompactFstImpl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: compact-fst.h:997
constexpr uint64_t kUnweighted
Definition: properties.h:106
typename Arc::Weight Weight
Definition: compact-fst.h:539
void SetNumStates(int64_t numstates)
Definition: fst.h:164
virtual const SymbolTable * InputSymbols() const =0
const SymbolTable * InputSymbols() const
Definition: fst.h:759
void SetCompactor(std::shared_ptr< Compactor > compactor)
Definition: compact-fst.h:1198
int64_t NumStates() const
Definition: fst.h:148
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: compact-fst.h:1176
bool Done() const
Definition: fst.h:415
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1484
typename Arc::Weight Weight
Definition: compact-fst.h:717
CompactArcCompactor(const Iterator b, const Iterator e)
Definition: compact-fst.h:598
const ArcCompactor * GetArcCompactor() const
Definition: compact-fst.h:678
void SetStart(int64_t start)
Definition: fst.h:162
static CompactArcStore * Read(std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr, const ArcCompactor &arc_compactor)
CacheStore Store
Definition: compact-fst.h:1118
void SetCompactor(std::shared_ptr< Compactor > compactor)
Definition: compact-fst.h:1049
typename Arc::StateId StateId
Definition: compact-fst.h:1521
std::shared_ptr< Compactor > SharedCompactor()
Definition: compact-fst.h:1048
typename AC::Element Element
Definition: compact-fst.h:536
FileReadMode mode
Definition: fst.h:80
int64_t Start() const
Definition: fst.h:146
constexpr uint64_t kString
Definition: properties.h:136
uint64_t Properties(uint64_t props) const
Definition: compact-fst.h:648
typename Arc::StateId StateId
Definition: compact-fst.h:1398
size_t NumArcs(StateId s)
Definition: compact-fst.h:962
void Expand(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, const std::vector< typename Arc::Label > &assignments, MutableFst< Arc > *ofst, const MPdtExpandOptions &opts)
Definition: expand.h:323
const Compactor * GetCompactor() const
Definition: compact-fst.h:1196
void InitStateIterator(StateIteratorData< Arc > *data) const
Definition: compact-fst.h:1027
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: compact-fst.h:493
static const std::string & Type()
Definition: compact-fst.h:518
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1550
typename Arc::StateId StateId
Definition: compact-fst.h:1479
CompactArcState(const Compactor *compactor, StateId s)
Definition: compact-fst.h:722
size_t NumArcs() const
Definition: compact-fst.h:758
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1526
constexpr ssize_t Size() const
Definition: compact-fst.h:1578
constexpr uint64_t kExpanded
Definition: properties.h:46
static CompactArcCompactor * Read(std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr)
Definition: compact-fst.h:634
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1582
Arc ComputeArc(StateId s, Unsigned i, uint8_t flags) const
Definition: compact-fst.h:688
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: compact-fst.h:1184
void SetFlags(uint32_t flags)
Definition: fst.h:158
constexpr ssize_t Size() const
Definition: compact-fst.h:1493
StateId NumStates() const
Definition: compact-fst.h:957
typename Arc::Label Label
Definition: compact-fst.h:1397
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: compact-fst.h:644
const CompactStore * GetCompactStore() const
Definition: compact-fst.h:679
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1508
const Compactor * GetCompactor(const Fst< Arc > &fst)
Definition: compact-fst.h:1098
static const std::string & Type()
Definition: compact-fst.h:1502
static const std::string & Type()
Definition: compact-fst.h:663
StateId Start() const
Definition: compact-fst.h:626
static CompactFst * Read(std::string_view source)
Definition: compact-fst.h:1171
size_t CountEpsilons(StateId s, bool output_epsilons)
Definition: compact-fst.h:980
constexpr uint64_t Properties() const
Definition: compact-fst.h:1495
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1414
constexpr uint64_t kAcceptor
Definition: properties.h:64
typename Arc::StateId StateId
Definition: compact-fst.h:1437
static const std::string & Type()
Definition: compact-fst.h:1545
bool Write(const std::string &source) const override
Definition: compact-fst.h:1180
virtual const SymbolTable * OutputSymbols() const =0