src/include/fst/fst.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // FST abstract base class definition, state and arc iterator interface, and
   5 // suggested base implementation.
   6
   7 #ifndef FST_FST_H_
   8 #define FST_FST_H_
   9
  10 #include <sys/types.h>
  11
  12 #include <cmath>
  13 #include <cstddef>
  14
  15 #include <iostream>
  16 #include <memory>
  17 #include <sstream>
  18 #include <string>
  19 #include <utility>
  20
  21 #include <fst/compat.h>
  22 #include <fst/types.h>
  23 #include <fst/flags.h>
  24 #include <fst/log.h>
  25 #include <fstream>
  26
  27 #include <fst/arc.h>
  28 #include <fst/memory.h>
  29 #include <fst/properties.h>
  30 #include <fst/register.h>
  31 #include <fst/symbol-table.h>
  32 #include <fst/util.h>
  33
  34
  35 DECLARE_bool(fst_align);
  36
  37 namespace fst {
  38
  39 bool IsFstHeader(std::istream &, const string &);
  40
  41 class FstHeader;
  42 template <class Arc>
  43
  44 struct StateIteratorData;
  45 template <class Arc>
  46
  47 struct ArcIteratorData;
  48
  49 template <class Arc>
  50 class MatcherBase;
  51
  52 struct FstReadOptions {
  53   // FileReadMode(s) are advisory, there are many conditions than prevent a
  54   // file from being mapped, READ mode will be selected in these cases with
  55   // a warning indicating why it was chosen.
  56   enum FileReadMode { READ, MAP };
  57
  58   string source;                // Where you're reading from.
  59   const FstHeader *header;      // Pointer to FST header; if non-zero, use
  60                                 // this info (don't read a stream header).
  61   const SymbolTable *isymbols;  // Pointer to input symbols; if non-zero, use
  62                                 // this info (read and skip stream isymbols)
  63   const SymbolTable *osymbols;  // Pointer to output symbols; if non-zero, use
  64                                 // this info (read and skip stream osymbols)
  65   FileReadMode mode;            // Read or map files (advisory, if possible)
  66   bool read_isymbols;           // Read isymbols, if any (default: true).
  67   bool read_osymbols;           // Read osymbols, if any (default: true).
  68
  69   explicit FstReadOptions(const string &source = "<unspecified>",
  70                           const FstHeader *header = nullptr,
  71                           const SymbolTable *isymbols = nullptr,
  72                           const SymbolTable *osymbols = nullptr);
  73
  74   explicit FstReadOptions(const string &source, const SymbolTable *isymbols,
  75                           const SymbolTable *osymbols = nullptr);
  76
  77   // Helper function to convert strings FileReadModes into their enum value.
  78   static FileReadMode ReadMode(const string &mode);
  79
  80   // Outputs a debug string for the FstReadOptions object.
  81   string DebugString() const;
  82 };
  83
  84 struct FstWriteOptions {
  85   string source;        // Where you're writing to.
  86   bool write_header;    // Write the header?
  87   bool write_isymbols;  // Write input symbols?
  88   bool write_osymbols;  // Write output symbols?
  89   bool align;           // Write data aligned (may fail on pipes)?
  90   bool stream_write;    // Avoid seek operations in writing.
  91
  92   explicit FstWriteOptions(const string &source = "<unspecifed>",
  93                            bool write_header = true, bool write_isymbols = true,
  94                            bool write_osymbols = true,
  95                            bool align = FLAGS_fst_align,
  96                            bool stream_write = false)
  97       : source(source),
  98         write_header(write_header),
  99         write_isymbols(write_isymbols),
 100         write_osymbols(write_osymbols),
 101         align(align),
 102         stream_write(stream_write) {}
 103 };
 104
 105 // Header class.
 106 //
 107 // This is the recommended file header representation.
 108
 109 class FstHeader {
 110  public:
 111   enum {
 112     HAS_ISYMBOLS = 0x1,  // Has input symbol table.
 113     HAS_OSYMBOLS = 0x2,  // Has output symbol table.
 114     IS_ALIGNED = 0x4,    // Memory-aligned (where appropriate).
 115   } Flags;
 116
 117   FstHeader() : version_(0), flags_(0), properties_(0), start_(-1),
 118       numstates_(0), numarcs_(0) {}
 119
 120   const string &FstType() const { return fsttype_; }
 121
 122   const string &ArcType() const { return arctype_; }
 123
 124   int32 Version() const { return version_; }
 125
 126   int32 GetFlags() const { return flags_; }
 127
 128   uint64 Properties() const { return properties_; }
 129
 130   int64 Start() const { return start_; }
 131
 132   int64 NumStates() const { return numstates_; }
 133
 134   int64 NumArcs() const { return numarcs_; }
 135
 136   void SetFstType(const string &type) { fsttype_ = type; }
 137
 138   void SetArcType(const string &type) { arctype_ = type; }
 139
 140   void SetVersion(int32 version) { version_ = version; }
 141
 142   void SetFlags(int32 flags) { flags_ = flags; }
 143
 144   void SetProperties(uint64 properties) { properties_ = properties; }
 145
 146   void SetStart(int64 start) { start_ = start; }
 147
 148   void SetNumStates(int64 numstates) { numstates_ = numstates; }
 149
 150   void SetNumArcs(int64 numarcs) { numarcs_ = numarcs; }
 151
 152   bool Read(std::istream &strm, const string &source,
 153             bool rewind = false);
 154
 155   bool Write(std::ostream &strm, const string &source) const;
 156
 157   // Outputs a debug string for the FstHeader object.
 158   string DebugString() const;
 159
 160  private:
 161   string fsttype_;     // E.g. "vector".
 162   string arctype_;     // E.g. "standard".
 163   int32 version_;      // Type version number.
 164   int32 flags_;        // File format bits.
 165   uint64 properties_;  // FST property bits.
 166   int64 start_;        // Start state.
 167   int64 numstates_;    // # of states.
 168   int64 numarcs_;      // # of arcs.
 169 };
 170
 171 // Specifies matcher action.
 172 enum MatchType {
 173   MATCH_INPUT = 1,   // Match input label.
 174   MATCH_OUTPUT = 2,  // Match output label.
 175   MATCH_BOTH = 3,    // Match input or output label.
 176   MATCH_NONE = 4,    // Match nothing.
 177   MATCH_UNKNOWN = 5
 178 };  // Otherwise, match type unknown.
 179
 180 constexpr int kNoStateId = -1;  // Not a valid state ID.
 181 constexpr int kNoLabel = -1;    // Not a valid label.
 182
 183 // A generic FST, templated on the arc definition, with common-demoninator
 184 // methods (use StateIterator and ArcIterator to iterate over its states and
 185 // arcs).
 186 template <class A>
 187 class Fst {
 188  public:
 189   using Arc = A;
 190   using StateId = typename Arc::StateId;
 191   using Weight = typename Arc::Weight;
 192
 193   virtual ~Fst() {}
 194
 195   // Initial state.
 196   virtual StateId Start() const = 0;
 197
 198   // State's final weight.
 199   virtual Weight Final(StateId) const = 0;
 200
 201   // State's arc count.
 202   virtual size_t NumArcs(StateId) const = 0;
 203
 204   // State's input epsilon count.
 205   virtual size_t NumInputEpsilons(StateId) const = 0;
 206
 207   // State's output epsilon count.
 208   virtual size_t NumOutputEpsilons(StateId) const = 0;
 209
 210   // Property bits. If test = false, return stored properties bits for mask
 211   // (some possibly unknown); if test = true, return property bits for mask
 212   // (computing o.w. unknown).
 213   virtual uint64 Properties(uint64 mask, bool test) const = 0;
 214
 215   // FST type name.
 216   virtual const string &Type() const = 0;
 217
 218   // Gets a copy of this Fst. The copying behaves as follows:
 219   //
 220   // (1) The copying is constant time if safe = false or if safe = true
 221   // and is on an otherwise unaccessed FST.
 222   //
 223   // (2) If safe = true, the copy is thread-safe in that the original
 224   // and copy can be safely accessed (but not necessarily mutated) by
 225   // separate threads. For some FST types, 'Copy(true)' should only be
 226   // called on an FST that has not otherwise been accessed. Behavior is
 227   // otherwise undefined.
 228   //
 229   // (3) If a MutableFst is copied and then mutated, then the original is
 230   // unmodified and vice versa (often by a copy-on-write on the initial
 231   // mutation, which may not be constant time).
 232   virtual Fst<Arc> *Copy(bool safe = false) const = 0;
 233
 234   // Reads an FST from an input stream; returns nullptr on error.
 235   static Fst<Arc> *Read(std::istream &strm, const FstReadOptions &opts) {
 236     FstReadOptions ropts(opts);
 237     FstHeader hdr;
 238     if (ropts.header) {
 239       hdr = *opts.header;
 240     } else {
 241       if (!hdr.Read(strm, opts.source)) return nullptr;
 242       ropts.header = &hdr;
 243     }
 244     const auto &fst_type = hdr.FstType();
 245     const auto reader = FstRegister<Arc>::GetRegister()->GetReader(fst_type);
 246     if (!reader) {
 247       LOG(ERROR) << "Fst::Read: Unknown FST type " << fst_type
 248                  << " (arc type = " << Arc::Type() << "): " << ropts.source;
 249       return nullptr;
 250     }
 251     return reader(strm, ropts);
 252   }
 253
 254   // Reads an FST from a file; returns nullptr on error. An empty filename
 255   // results in reading from standard input.
 256   static Fst<Arc> *Read(const string &filename) {
 257     if (!filename.empty()) {
 258       std::ifstream strm(filename,
 259                               std::ios_base::in | std::ios_base::binary);
 260       if (!strm) {
 261         LOG(ERROR) << "Fst::Read: Can't open file: " << filename;
 262         return nullptr;
 263       }
 264       return Read(strm, FstReadOptions(filename));
 265     } else {
 266       return Read(std::cin, FstReadOptions("standard input"));
 267     }
 268   }
 269
 270   // Writes an FST to an output stream; returns false on error.
 271   virtual bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
 272     LOG(ERROR) << "Fst::Write: No write stream method for " << Type()
 273                << " FST type";
 274     return false;
 275   }
 276
 277   // Writes an FST to a file; returns false on error; an empty filename
 278   // results in writing to standard output.
 279   virtual bool Write(const string &filename) const {
 280     LOG(ERROR) << "Fst::Write: No write filename method for " << Type()
 281                << " FST type";
 282     return false;
 283   }
 284
 285   // Returns input label symbol table; return nullptr if not specified.
 286   virtual const SymbolTable *InputSymbols() const = 0;
 287
 288   // Return output label symbol table; return nullptr if not specified.
 289   virtual const SymbolTable *OutputSymbols() const = 0;
 290
 291   // For generic state iterator construction (not normally called directly by
 292   // users).
 293   virtual void InitStateIterator(StateIteratorData<Arc> *data) const = 0;
 294
 295   // For generic arc iterator construction (not normally called directly by
 296   // users).
 297   virtual void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const = 0;
 298
 299   // For generic matcher construction (not normally called directly by users).
 300   virtual MatcherBase<Arc> *InitMatcher(MatchType match_type) const;
 301
 302  protected:
 303   bool WriteFile(const string &filename) const {
 304     if (!filename.empty()) {
 305       std::ofstream strm(filename,
 306                                std::ios_base::out | std::ios_base::binary);
 307       if (!strm) {
 308         LOG(ERROR) << "Fst::Write: Can't open file: " << filename;
 309         return false;
 310       }
 311       bool val = Write(strm, FstWriteOptions(filename));
 312       if (!val) LOG(ERROR) << "Fst::Write failed: " << filename;
 313       return val;
 314     } else {
 315       return Write(std::cout, FstWriteOptions("standard output"));
 316     }
 317   }
 318 };
 319
 320 // A useful alias when using StdArc.
 321 using StdFst = Fst<StdArc>;
 322
 323 // State and arc iterator definitions.
 324 //
 325 // State iterator interface templated on the Arc definition; used for
 326 // StateIterator specializations returned by the InitStateIterator FST method.
 327 template <class Arc>
 328 class StateIteratorBase {
 329  public:
 330   using StateId = typename Arc::StateId;
 331
 332   virtual ~StateIteratorBase() {}
 333
 334   // End of iterator?
 335   virtual bool Done() const = 0;
 336   // Returns current state (when !Done()).
 337   virtual StateId Value() const = 0;
 338   // Advances to next state (when !Done()).
 339   virtual void Next() = 0;
 340   // Resets to initial condition.
 341   virtual void Reset() = 0;
 342 };
 343
 344 // StateIterator initialization data.
 345
 346 template <class Arc>
 347 struct StateIteratorData {
 348   using StateId = typename Arc::StateId;
 349
 350   // Specialized iterator if non-zero.
 351   StateIteratorBase<Arc> *base;
 352   // Otherwise, the total number of states.
 353   StateId nstates;
 354
 355   StateIteratorData() : base(nullptr), nstates(0) {}
 356
 357   StateIteratorData(const StateIteratorData &) = delete;
 358   StateIteratorData &operator=(const StateIteratorData &) = delete;
 359 };
 360
 361 // Generic state iterator, templated on the FST definition (a wrapper
 362 // around a pointer to a specific one). Here is a typical use:
 363 //
 364 //   for (StateIterator<StdFst> siter(fst);
 365 //        !siter.Done();
 366 //        siter.Next()) {
 367 //     StateId s = siter.Value();
 368 //     ...
 369 //   }
 370 template <class FST>
 371 class StateIterator {
 372  public:
 373   using Arc = typename FST::Arc;
 374   using StateId = typename Arc::StateId;
 375
 376   explicit StateIterator(const FST &fst) : s_(0) {
 377     fst.InitStateIterator(&data_);
 378   }
 379
 380   ~StateIterator() { delete data_.base; }
 381
 382   bool Done() const {
 383     return data_.base ? data_.base->Done() : s_ >= data_.nstates;
 384   }
 385
 386   StateId Value() const { return data_.base ? data_.base->Value() : s_; }
 387
 388   void Next() {
 389     if (data_.base) {
 390       data_.base->Next();
 391     } else {
 392       ++s_;
 393     }
 394   }
 395
 396   void Reset() {
 397     if (data_.base) {
 398       data_.base->Reset();
 399     } else {
 400       s_ = 0;
 401     }
 402   }
 403
 404  private:
 405   StateIteratorData<Arc> data_;
 406   StateId s_;
 407 };
 408
 409 // Flags to control the behavior on an arc iterator.
 410 static constexpr uint32 kArcILabelValue =
 411     0x0001;  // Value() gives valid ilabel.
 412 static constexpr uint32 kArcOLabelValue = 0x0002;  //  "       "     " olabel.
 413 static constexpr uint32 kArcWeightValue = 0x0004;  //  "       "     " weight.
 414 static constexpr uint32 kArcNextStateValue =
 415     0x0008;                                    //  "       "     " nextstate.
 416 static constexpr uint32 kArcNoCache = 0x0010;  // No need to cache arcs.
 417
 418 static constexpr uint32 kArcValueFlags =
 419     kArcILabelValue | kArcOLabelValue | kArcWeightValue | kArcNextStateValue;
 420
 421 static constexpr uint32 kArcFlags = kArcValueFlags | kArcNoCache;
 422
 423 // Arc iterator interface, templated on the arc definition; used for arc
 424 // iterator specializations that are returned by the InitArcIterator FST method.
 425 template <class Arc>
 426 class ArcIteratorBase {
 427  public:
 428   using StateId = typename Arc::StateId;
 429
 430   virtual ~ArcIteratorBase() {}
 431
 432   // End of iterator?
 433   virtual bool Done() const = 0;
 434   // Returns current arc (when !Done()).
 435   virtual const Arc &Value() const = 0;
 436   // Advances to next arc (when !Done()).
 437   virtual void Next() = 0;
 438   // Returns current position.
 439   virtual size_t Position() const = 0;
 440   // Returns to initial condition.
 441   virtual void Reset() = 0;
 442   // Advances to arbitrary arc by position.
 443   virtual void Seek(size_t) = 0;
 444   // Returns current behavorial flags
 445   virtual uint32 Flags() const = 0;
 446   // Sets behavorial flags.
 447   virtual void SetFlags(uint32, uint32) = 0;
 448 };
 449
 450 // ArcIterator initialization data.
 451 template <class Arc>
 452 struct ArcIteratorData {
 453   ArcIteratorData()
 454       : base(nullptr), arcs(nullptr), narcs(0), ref_count(nullptr) {}
 455
 456   ArcIteratorData(const ArcIteratorData &) = delete;
 457
 458   ArcIteratorData &operator=(const ArcIteratorData &) = delete;
 459
 460   ArcIteratorBase<Arc> *base;  // Specialized iterator if non-zero.
 461   const Arc *arcs;             // O.w. arcs pointer
 462   size_t narcs;                // ... and arc count.
 463   int *ref_count;              // ... and reference count if non-zero.
 464 };
 465
 466 // Generic arc iterator, templated on the FST definition (a wrapper around a
 467 // pointer to a specific one). Here is a typical use:
 468 //
 469 //   for (ArcIterator<StdFst> aiter(fst, s);
 470 //        !aiter.Done();
 471 //         aiter.Next()) {
 472 //     StdArc &arc = aiter.Value();
 473 //     ...
 474 //   }
 475 template <class FST>
 476 class ArcIterator {
 477  public:
 478   using Arc = typename FST::Arc;
 479   using StateId = typename Arc::StateId;
 480
 481   ArcIterator(const FST &fst, StateId s) : i_(0) {
 482     fst.InitArcIterator(s, &data_);
 483   }
 484
 485   explicit ArcIterator(const ArcIteratorData<Arc> &data) : data_(data), i_(0) {
 486     if (data_.ref_count) ++(*data_.ref_count);
 487   }
 488
 489   ~ArcIterator() {
 490     if (data_.base) {
 491       delete data_.base;
 492     } else if (data_.ref_count) {
 493       --(*data_.ref_count);
 494     }
 495   }
 496
 497   bool Done() const {
 498     return data_.base ? data_.base->Done() : i_ >= data_.narcs;
 499   }
 500
 501   const Arc &Value() const {
 502     return data_.base ? data_.base->Value() : data_.arcs[i_];
 503   }
 504
 505   void Next() {
 506     if (data_.base) {
 507       data_.base->Next();
 508     } else {
 509       ++i_;
 510     }
 511   }
 512
 513   void Reset() {
 514     if (data_.base) {
 515       data_.base->Reset();
 516     } else {
 517       i_ = 0;
 518     }
 519   }
 520
 521   void Seek(size_t a) {
 522     if (data_.base) {
 523       data_.base->Seek(a);
 524     } else {
 525       i_ = a;
 526     }
 527   }
 528
 529   size_t Position() const { return data_.base ? data_.base->Position() : i_; }
 530
 531   uint32 Flags() const {
 532     if (data_.base) {
 533       return data_.base->Flags();
 534     } else {
 535       return kArcValueFlags;
 536     }
 537   }
 538
 539   void SetFlags(uint32 flags, uint32 mask) {
 540     if (data_.base) data_.base->SetFlags(flags, mask);
 541   }
 542
 543  private:
 544   ArcIteratorData<Arc> data_;
 545   size_t i_;
 546 };
 547
 548 }  // namespace fst
 549
 550 // ArcIterator placement operator new and destroy function; new needs to be in
 551 // the global namespace.
 552
 553 template <class FST>
 554 void *operator new(size_t size,
 555                    fst::MemoryPool<fst::ArcIterator<FST>> *pool) {
 556   return pool->Allocate();
 557 }
 558
 559 namespace fst {
 560
 561 template <class FST>
 562 void Destroy(ArcIterator<FST> *aiter, MemoryPool<ArcIterator<FST>> *pool) {
 563   if (aiter) {
 564     aiter->~ArcIterator<FST>();
 565     pool->Free(aiter);
 566   }
 567 }
 568
 569 // Matcher definitions.
 570
 571 template <class Arc>
 572 MatcherBase<Arc> *Fst<Arc>::InitMatcher(MatchType match_type) const {
 573   return nullptr;  // One should just use the default matcher.
 574 }
 575
 576 // FST accessors, useful in high-performance applications.
 577
 578 namespace internal {
 579
 580 // General case, requires non-abstract, 'final' methods. Use for inlining.
 581
 582 template <class F>
 583 inline typename F::Arc::Weight Final(const F &fst, typename F::Arc::StateId s) {
 584   return fst.F::Final(s);
 585 }
 586
 587 template <class F>
 588 inline ssize_t NumArcs(const F &fst, typename F::Arc::StateId s) {
 589   return fst.F::NumArcs(s);
 590 }
 591
 592 template <class F>
 593 inline ssize_t NumInputEpsilons(const F &fst, typename F::Arc::StateId s) {
 594   return fst.F::NumInputEpsilons(s);
 595 }
 596
 597 template <class F>
 598 inline ssize_t NumOutputEpsilons(const F &fst, typename F::Arc::StateId s) {
 599   return fst.F::NumOutputEpsilons(s);
 600 }
 601
 602 // Fst<Arc> case, abstract methods.
 603
 604 template <class Arc>
 605 inline typename Arc::Weight Final(const Fst<Arc> &fst,
 606                                   typename Arc::StateId s) {
 607   return fst.Final(s);
 608 }
 609
 610 template <class Arc>
 611 inline size_t NumArcs(const Fst<Arc> &fst, typename Arc::StateId s) {
 612   return fst.NumArcs(s);
 613 }
 614
 615 template <class Arc>
 616 inline size_t NumInputEpsilons(const Fst<Arc> &fst, typename Arc::StateId s) {
 617   return fst.NumInputEpsilons(s);
 618 }
 619
 620 template <class Arc>
 621 inline size_t NumOutputEpsilons(const Fst<Arc> &fst, typename Arc::StateId s) {
 622   return fst.NumOutputEpsilons(s);
 623 }
 624
 625 // FST implementation base.
 626 //
 627 // This is the recommended FST implementation base class. It will handle
 628 // reference counts, property bits, type information and symbols.
 629 //
 630 // Users are discouraged, but not prohibited, from subclassing this outside the
 631 // FST library.
 632 template <class Arc>
 633 class FstImpl {
 634  public:
 635   using StateId = typename Arc::StateId;
 636   using Weight = typename Arc::Weight;
 637
 638   FstImpl() : properties_(0), type_("null") {}
 639
 640   FstImpl(const FstImpl<Arc> &impl)
 641       : properties_(impl.properties_),
 642         type_(impl.type_),
 643         isymbols_(impl.isymbols_ ? impl.isymbols_->Copy() : nullptr),
 644         osymbols_(impl.osymbols_ ? impl.osymbols_->Copy() : nullptr) {}
 645
 646   virtual ~FstImpl() {}
 647
 648   const string &Type() const { return type_; }
 649
 650   void SetType(const string &type) { type_ = type; }
 651
 652   virtual uint64 Properties() const { return properties_; }
 653
 654   virtual uint64 Properties(uint64 mask) const { return properties_ & mask; }
 655
 656   void SetProperties(uint64 props) {
 657     properties_ &= kError;  // kError can't be cleared.
 658     properties_ |= props;
 659   }
 660
 661   void SetProperties(uint64 props, uint64 mask) {
 662     properties_ &= ~mask | kError;  // kError can't be cleared.
 663     properties_ |= props & mask;
 664   }
 665
 666   // Allows (only) setting error bit on const FST implementations.
 667   void SetProperties(uint64 props, uint64 mask) const {
 668     if (mask != kError) {
 669       FSTERROR() << "FstImpl::SetProperties() const: Can only set kError";
 670     }
 671     properties_ |= kError;
 672   }
 673
 674   const SymbolTable *InputSymbols() const { return isymbols_.get(); }
 675
 676   const SymbolTable *OutputSymbols() const { return osymbols_.get(); }
 677
 678   SymbolTable *InputSymbols() { return isymbols_.get(); }
 679
 680   SymbolTable *OutputSymbols() { return osymbols_.get(); }
 681
 682   void SetInputSymbols(const SymbolTable *isyms) {
 683     isymbols_.reset(isyms ? isyms->Copy() : nullptr);
 684   }
 685
 686   void SetOutputSymbols(const SymbolTable *osyms) {
 687     osymbols_.reset(osyms ? osyms->Copy() : nullptr);
 688   }
 689
 690   // Reads header and symbols from input stream, initializes FST, and returns
 691   // the header. If opts.header is non-null, skips reading and uses the option
 692   // value instead. If opts.[io]symbols is non-null, reads in (if present), but
 693   // uses the option value.
 694   bool ReadHeader(std::istream &strm, const FstReadOptions &opts,
 695                   int min_version, FstHeader *hdr);
 696
 697   // Writes header and symbols to output stream. If opts.header is false, skips
 698   // writing header. If opts.[io]symbols is false, skips writing those symbols.
 699   // This method is needed for implementations that implement Write methods.
 700   void WriteHeader(std::ostream &strm, const FstWriteOptions &opts,
 701                    int version, FstHeader *hdr) const {
 702     if (opts.write_header) {
 703       hdr->SetFstType(type_);
 704       hdr->SetArcType(Arc::Type());
 705       hdr->SetVersion(version);
 706       hdr->SetProperties(properties_);
 707       int32 file_flags = 0;
 708       if (isymbols_ && opts.write_isymbols) {
 709         file_flags |= FstHeader::HAS_ISYMBOLS;
 710       }
 711       if (osymbols_ && opts.write_osymbols) {
 712         file_flags |= FstHeader::HAS_OSYMBOLS;
 713       }
 714       if (opts.align) file_flags |= FstHeader::IS_ALIGNED;
 715       hdr->SetFlags(file_flags);
 716       hdr->Write(strm, opts.source);
 717     }
 718     if (isymbols_ && opts.write_isymbols) isymbols_->Write(strm);
 719     if (osymbols_ && opts.write_osymbols) osymbols_->Write(strm);
 720   }
 721
 722   // Writes out header and symbols to output stream. If opts.header is false,
 723   // skips writing header. If opts.[io]symbols is false, skips writing those
 724   // symbols. `type` is the FST type being written. This method is used in the
 725   // cross-type serialization methods Fst::WriteFst.
 726   static void WriteFstHeader(const Fst<Arc> &fst, std::ostream &strm,
 727                              const FstWriteOptions &opts, int version,
 728                              const string &type, uint64 properties,
 729                              FstHeader *hdr) {
 730     if (opts.write_header) {
 731       hdr->SetFstType(type);
 732       hdr->SetArcType(Arc::Type());
 733       hdr->SetVersion(version);
 734       hdr->SetProperties(properties);
 735       int32 file_flags = 0;
 736       if (fst.InputSymbols() && opts.write_isymbols) {
 737         file_flags |= FstHeader::HAS_ISYMBOLS;
 738       }
 739       if (fst.OutputSymbols() && opts.write_osymbols) {
 740         file_flags |= FstHeader::HAS_OSYMBOLS;
 741       }
 742       if (opts.align) file_flags |= FstHeader::IS_ALIGNED;
 743       hdr->SetFlags(file_flags);
 744       hdr->Write(strm, opts.source);
 745     }
 746     if (fst.InputSymbols() && opts.write_isymbols) {
 747       fst.InputSymbols()->Write(strm);
 748     }
 749     if (fst.OutputSymbols() && opts.write_osymbols) {
 750       fst.OutputSymbols()->Write(strm);
 751     }
 752   }
 753
 754   // In serialization routines where the header cannot be written until after
 755   // the machine has been serialized, this routine can be called to seek to the
 756   // beginning of the file an rewrite the header with updated fields. It
 757   // repositions the file pointer back at the end of the file. Returns true on
 758   // success, false on failure.
 759   static bool UpdateFstHeader(const Fst<Arc> &fst, std::ostream &strm,
 760                               const FstWriteOptions &opts, int version,
 761                               const string &type, uint64 properties,
 762                               FstHeader *hdr, size_t header_offset) {
 763     strm.seekp(header_offset);
 764     if (!strm) {
 765       LOG(ERROR) << "Fst::UpdateFstHeader: Write failed: " << opts.source;
 766       return false;
 767     }
 768     WriteFstHeader(fst, strm, opts, version, type, properties, hdr);
 769     if (!strm) {
 770       LOG(ERROR) << "Fst::UpdateFstHeader: Write failed: " << opts.source;
 771       return false;
 772     }
 773     strm.seekp(0, std::ios_base::end);
 774     if (!strm) {
 775       LOG(ERROR) << "Fst::UpdateFstHeader: Write failed: " << opts.source;
 776       return false;
 777     }
 778     return true;
 779   }
 780
 781  protected:
 782   mutable uint64 properties_;  // Property bits.
 783
 784  private:
 785   string type_;  // Unique name of FST class.
 786   std::unique_ptr<SymbolTable> isymbols_;
 787   std::unique_ptr<SymbolTable> osymbols_;
 788 };
 789
 790 template <class Arc>
 791 bool FstImpl<Arc>::ReadHeader(std::istream &strm, const FstReadOptions &opts,
 792                               int min_version, FstHeader *hdr) {
 793   if (opts.header) {
 794     *hdr = *opts.header;
 795   } else if (!hdr->Read(strm, opts.source)) {
 796     return false;
 797   }
 798   if (FLAGS_v >= 2) {
 799     LOG(INFO) << "FstImpl::ReadHeader: source: " << opts.source
 800               << ", fst_type: " << hdr->FstType()
 801               << ", arc_type: " << Arc::Type()
 802               << ", version: " << hdr->Version()
 803               << ", flags: " << hdr->GetFlags();
 804   }
 805   if (hdr->FstType() != type_) {
 806     LOG(ERROR) << "FstImpl::ReadHeader: FST not of type " << type_
 807                << ": " << opts.source;
 808     return false;
 809   }
 810   if (hdr->ArcType() != Arc::Type()) {
 811     LOG(ERROR) << "FstImpl::ReadHeader: Arc not of type " << Arc::Type()
 812                << ": " << opts.source;
 813     return false;
 814   }
 815   if (hdr->Version() < min_version) {
 816     LOG(ERROR) << "FstImpl::ReadHeader: Obsolete " << type_
 817                << " FST version: " << opts.source;
 818     return false;
 819   }
 820   properties_ = hdr->Properties();
 821   if (hdr->GetFlags() & FstHeader::HAS_ISYMBOLS) {
 822     isymbols_.reset(SymbolTable::Read(strm, opts.source));
 823   }
 824   // Deletes input symbol table.
 825   if (!opts.read_isymbols) SetInputSymbols(nullptr);
 826   if (hdr->GetFlags() & FstHeader::HAS_OSYMBOLS) {
 827     osymbols_.reset(SymbolTable::Read(strm, opts.source));
 828   }
 829   // Deletes output symbol table.
 830   if (!opts.read_osymbols) SetOutputSymbols(nullptr);
 831   if (opts.isymbols) {
 832     isymbols_.reset(opts.isymbols->Copy());
 833   }
 834   if (opts.osymbols) {
 835     osymbols_.reset(opts.osymbols->Copy());
 836   }
 837   return true;
 838 }
 839
 840 }  // namespace internal
 841
 842 template <class Arc>
 843 uint64 TestProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known);
 844
 845 // This is a helper class template useful for attaching an FST interface to
 846 // its implementation, handling reference counting.
 847 template <class Impl, class FST = Fst<typename Impl::Arc>>
 848 class ImplToFst : public FST {
 849  public:
 850   using Arc = typename Impl::Arc;
 851   using StateId = typename Arc::StateId;
 852   using Weight = typename Arc::Weight;
 853   using FST::operator=;
 854
 855   StateId Start() const override { return impl_->Start(); }
 856
 857   Weight Final(StateId s) const override { return impl_->Final(s); }
 858
 859   size_t NumArcs(StateId s) const override { return impl_->NumArcs(s); }
 860
 861   size_t NumInputEpsilons(StateId s) const override {
 862     return impl_->NumInputEpsilons(s);
 863   }
 864
 865   size_t NumOutputEpsilons(StateId s) const override {
 866     return impl_->NumOutputEpsilons(s);
 867   }
 868
 869   uint64 Properties(uint64 mask, bool test) const override {
 870     if (test) {
 871       uint64 knownprops, testprops = TestProperties(*this, mask, &knownprops);
 872       impl_->SetProperties(testprops, knownprops);
 873       return testprops & mask;
 874     } else {
 875       return impl_->Properties(mask);
 876     }
 877   }
 878
 879   const string &Type() const override { return impl_->Type(); }
 880
 881   const SymbolTable *InputSymbols() const override {
 882     return impl_->InputSymbols();
 883   }
 884
 885   const SymbolTable *OutputSymbols() const override {
 886     return impl_->OutputSymbols();
 887   }
 888
 889  protected:
 890   explicit ImplToFst(std::shared_ptr<Impl> impl) : impl_(std::move(impl)) {}
 891
 892   // This constructor presumes there is a copy constructor for the
 893   // implementation.
 894   ImplToFst(const ImplToFst<Impl, FST> &fst, bool safe) {
 895     if (safe) {
 896       impl_ = std::make_shared<Impl>(*(fst.impl_));
 897     } else {
 898       impl_ = fst.impl_;
 899     }
 900   }
 901
 902   // Returns raw pointers to the shared object.
 903   const Impl *GetImpl() const { return impl_.get(); }
 904
 905   Impl *GetMutableImpl() const { return impl_.get(); }
 906
 907   // Returns a ref-counted smart poiner to the implementation.
 908   std::shared_ptr<Impl> GetSharedImpl() const { return impl_; }
 909
 910   bool Unique() const { return impl_.unique(); }
 911
 912   void SetImpl(std::shared_ptr<Impl> impl) { impl_ = impl; }
 913
 914  private:
 915   template <class IFST, class OFST>
 916   friend void Cast(const IFST &ifst, OFST *ofst);
 917
 918   std::shared_ptr<Impl> impl_;
 919 };
 920
 921 // Converts FSTs by casting their implementations, where this makes sense
 922 // (which excludes implementations with weight-dependent virtual methods).
 923 // Must be a friend of the FST classes involved (currently the concrete FSTs:
 924 // ConstFst, CompactFst, and VectorFst). This can only be safely used for arc
 925 // types that have identical storage characteristics. As with an FST
 926 // copy constructor and Copy() method, this is a constant time operation
 927 // (but subject to copy-on-write if it is a MutableFst and modified).
 928 template <class IFST, class OFST>
 929 void Cast(const IFST &ifst, OFST *ofst) {
 930   using OImpl = typename OFST::Impl;
 931   ofst->impl_ = std::shared_ptr<OImpl>(ifst.impl_,
 932       reinterpret_cast<OImpl *>(ifst.impl_.get()));
 933 }
 934
 935 // FST serialization.
 936
 937 template <class Arc>
 938 void FstToString(const Fst<Arc> &fst, string *result) {
 939   std::ostringstream ostrm;
 940   fst.Write(ostrm, FstWriteOptions("FstToString"));
 941   *result = ostrm.str();
 942 }
 943
 944 template <class Arc>
 945 void FstToString(const Fst<Arc> &fst, string *result,
 946                  const FstWriteOptions &options) {
 947   std::ostringstream ostrm;
 948   fst.Write(ostrm, options);
 949   *result = ostrm.str();
 950 }
 951
 952 template <class Arc>
 953 Fst<Arc> *StringToFst(const string &s) {
 954   std::istringstream istrm(s);
 955   return Fst<Arc>::Read(istrm, FstReadOptions("StringToFst"));
 956 }
 957
 958 }  // namespace fst
 959
 960 #endif  // FST_FST_H_