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
  43 template <class Arc>
  44 struct StateIteratorData;
  45
  46 template <class Arc>
  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). Does not copy the FST.
 293   virtual void InitStateIterator(StateIteratorData<Arc> *data) const = 0;
 294
 295   // For generic arc iterator construction (not normally called directly by
 296   // users). Does not copy the FST.
 297   virtual void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const = 0;
 298
 299   // For generic matcher construction (not normally called directly by users).
 300   // Does not copy the FST.
 301   virtual MatcherBase<Arc> *InitMatcher(MatchType match_type) const;
 302
 303  protected:
 304   bool WriteFile(const string &filename) const {
 305     if (!filename.empty()) {
 306       std::ofstream strm(filename,
 307                                std::ios_base::out | std::ios_base::binary);
 308       if (!strm) {
 309         LOG(ERROR) << "Fst::Write: Can't open file: " << filename;
 310         return false;
 311       }
 312       bool val = Write(strm, FstWriteOptions(filename));
 313       if (!val) LOG(ERROR) << "Fst::Write failed: " << filename;
 314       return val;
 315     } else {
 316       return Write(std::cout, FstWriteOptions("standard output"));
 317     }
 318   }
 319 };
 320
 321 // A useful alias when using StdArc.
 322 using StdFst = Fst<StdArc>;
 323
 324 // State and arc iterator definitions.
 325 //
 326 // State iterator interface templated on the Arc definition; used for
 327 // StateIterator specializations returned by the InitStateIterator FST method.
 328 template <class Arc>
 329 class StateIteratorBase {
 330  public:
 331   using StateId = typename Arc::StateId;
 332
 333   virtual ~StateIteratorBase() {}
 334
 335   // End of iterator?
 336   virtual bool Done() const = 0;
 337   // Returns current state (when !Done()).
 338   virtual StateId Value() const = 0;
 339   // Advances to next state (when !Done()).
 340   virtual void Next() = 0;
 341   // Resets to initial condition.
 342   virtual void Reset() = 0;
 343 };
 344
 345 // StateIterator initialization data.
 346
 347 template <class Arc>
 348 struct StateIteratorData {
 349   using StateId = typename Arc::StateId;
 350
 351   // Specialized iterator if non-zero.
 352   StateIteratorBase<Arc> *base;
 353   // Otherwise, the total number of states.
 354   StateId nstates;
 355
 356   StateIteratorData() : base(nullptr), nstates(0) {}
 357
 358   StateIteratorData(const StateIteratorData &) = delete;
 359   StateIteratorData &operator=(const StateIteratorData &) = delete;
 360 };
 361
 362 // Generic state iterator, templated on the FST definition (a wrapper
 363 // around a pointer to a specific one). Here is a typical use:
 364 //
 365 //   for (StateIterator<StdFst> siter(fst);
 366 //        !siter.Done();
 367 //        siter.Next()) {
 368 //     StateId s = siter.Value();
 369 //     ...
 370 //   }
 371 // There is no copying of the FST.
 372 template <class FST>
 373 class StateIterator {
 374  public:
 375   using Arc = typename FST::Arc;
 376   using StateId = typename Arc::StateId;
 377
 378   explicit StateIterator(const FST &fst) : s_(0) {
 379     fst.InitStateIterator(&data_);
 380   }
 381
 382   ~StateIterator() { delete data_.base; }
 383
 384   bool Done() const {
 385     return data_.base ? data_.base->Done() : s_ >= data_.nstates;
 386   }
 387
 388   StateId Value() const { return data_.base ? data_.base->Value() : s_; }
 389
 390   void Next() {
 391     if (data_.base) {
 392       data_.base->Next();
 393     } else {
 394       ++s_;
 395     }
 396   }
 397
 398   void Reset() {
 399     if (data_.base) {
 400       data_.base->Reset();
 401     } else {
 402       s_ = 0;
 403     }
 404   }
 405
 406  private:
 407   StateIteratorData<Arc> data_;
 408   StateId s_;
 409 };
 410
 411 // Flags to control the behavior on an arc iterator.
 412 static constexpr uint32 kArcILabelValue =
 413     0x0001;  // Value() gives valid ilabel.
 414 static constexpr uint32 kArcOLabelValue = 0x0002;  //  "       "     " olabel.
 415 static constexpr uint32 kArcWeightValue = 0x0004;  //  "       "     " weight.
 416 static constexpr uint32 kArcNextStateValue =
 417     0x0008;                                    //  "       "     " nextstate.
 418 static constexpr uint32 kArcNoCache = 0x0010;  // No need to cache arcs.
 419
 420 static constexpr uint32 kArcValueFlags =
 421     kArcILabelValue | kArcOLabelValue | kArcWeightValue | kArcNextStateValue;
 422
 423 static constexpr uint32 kArcFlags = kArcValueFlags | kArcNoCache;
 424
 425 // Arc iterator interface, templated on the arc definition; used for arc
 426 // iterator specializations that are returned by the InitArcIterator FST method.
 427 template <class Arc>
 428 class ArcIteratorBase {
 429  public:
 430   using StateId = typename Arc::StateId;
 431
 432   virtual ~ArcIteratorBase() {}
 433
 434   // End of iterator?
 435   virtual bool Done() const = 0;
 436   // Returns current arc (when !Done()).
 437   virtual const Arc &Value() const = 0;
 438   // Advances to next arc (when !Done()).
 439   virtual void Next() = 0;
 440   // Returns current position.
 441   virtual size_t Position() const = 0;
 442   // Returns to initial condition.
 443   virtual void Reset() = 0;
 444   // Advances to arbitrary arc by position.
 445   virtual void Seek(size_t) = 0;
 446   // Returns current behavorial flags
 447   virtual uint32 Flags() const = 0;
 448   // Sets behavorial flags.
 449   virtual void SetFlags(uint32, uint32) = 0;
 450 };
 451
 452 // ArcIterator initialization data.
 453 template <class Arc>
 454 struct ArcIteratorData {
 455   ArcIteratorData()
 456       : base(nullptr), arcs(nullptr), narcs(0), ref_count(nullptr) {}
 457
 458   ArcIteratorData(const ArcIteratorData &) = delete;
 459
 460   ArcIteratorData &operator=(const ArcIteratorData &) = delete;
 461
 462   ArcIteratorBase<Arc> *base;  // Specialized iterator if non-zero.
 463   const Arc *arcs;             // O.w. arcs pointer
 464   size_t narcs;                // ... and arc count.
 465   int *ref_count;              // ... and reference count if non-zero.
 466 };
 467
 468 // Generic arc iterator, templated on the FST definition (a wrapper around a
 469 // pointer to a specific one). Here is a typical use:
 470 //
 471 //   for (ArcIterator<StdFst> aiter(fst, s);
 472 //        !aiter.Done();
 473 //         aiter.Next()) {
 474 //     StdArc &arc = aiter.Value();
 475 //     ...
 476 //   }
 477 // There is no copying of the FST.
 478 template <class FST>
 479 class ArcIterator {
 480  public:
 481   using Arc = typename FST::Arc;
 482   using StateId = typename Arc::StateId;
 483
 484   ArcIterator(const FST &fst, StateId s) : i_(0) {
 485     fst.InitArcIterator(s, &data_);
 486   }
 487
 488   explicit ArcIterator(const ArcIteratorData<Arc> &data) : data_(data), i_(0) {
 489     if (data_.ref_count) ++(*data_.ref_count);
 490   }
 491
 492   ~ArcIterator() {
 493     if (data_.base) {
 494       delete data_.base;
 495     } else if (data_.ref_count) {
 496       --(*data_.ref_count);
 497     }
 498   }
 499
 500   bool Done() const {
 501     return data_.base ? data_.base->Done() : i_ >= data_.narcs;
 502   }
 503
 504   const Arc &Value() const {
 505     return data_.base ? data_.base->Value() : data_.arcs[i_];
 506   }
 507
 508   void Next() {
 509     if (data_.base) {
 510       data_.base->Next();
 511     } else {
 512       ++i_;
 513     }
 514   }
 515
 516   void Reset() {
 517     if (data_.base) {
 518       data_.base->Reset();
 519     } else {
 520       i_ = 0;
 521     }
 522   }
 523
 524   void Seek(size_t a) {
 525     if (data_.base) {
 526       data_.base->Seek(a);
 527     } else {
 528       i_ = a;
 529     }
 530   }
 531
 532   size_t Position() const { return data_.base ? data_.base->Position() : i_; }
 533
 534   uint32 Flags() const {
 535     if (data_.base) {
 536       return data_.base->Flags();
 537     } else {
 538       return kArcValueFlags;
 539     }
 540   }
 541
 542   void SetFlags(uint32 flags, uint32 mask) {
 543     if (data_.base) data_.base->SetFlags(flags, mask);
 544   }
 545
 546  private:
 547   ArcIteratorData<Arc> data_;
 548   size_t i_;
 549 };
 550
 551 }  // namespace fst
 552
 553 // ArcIterator placement operator new and destroy function; new needs to be in
 554 // the global namespace.
 555
 556 template <class FST>
 557 void *operator new(size_t size,
 558                    fst::MemoryPool<fst::ArcIterator<FST>> *pool) {
 559   return pool->Allocate();
 560 }
 561
 562 namespace fst {
 563
 564 template <class FST>
 565 void Destroy(ArcIterator<FST> *aiter, MemoryPool<ArcIterator<FST>> *pool) {
 566   if (aiter) {
 567     aiter->~ArcIterator<FST>();
 568     pool->Free(aiter);
 569   }
 570 }
 571
 572 // Matcher definitions.
 573
 574 template <class Arc>
 575 MatcherBase<Arc> *Fst<Arc>::InitMatcher(MatchType match_type) const {
 576   return nullptr;  // One should just use the default matcher.
 577 }
 578
 579 // FST accessors, useful in high-performance applications.
 580
 581 namespace internal {
 582
 583 // General case, requires non-abstract, 'final' methods. Use for inlining.
 584
 585 template <class F>
 586 inline typename F::Arc::Weight Final(const F &fst, typename F::Arc::StateId s) {
 587   return fst.F::Final(s);
 588 }
 589
 590 template <class F>
 591 inline ssize_t NumArcs(const F &fst, typename F::Arc::StateId s) {
 592   return fst.F::NumArcs(s);
 593 }
 594
 595 template <class F>
 596 inline ssize_t NumInputEpsilons(const F &fst, typename F::Arc::StateId s) {
 597   return fst.F::NumInputEpsilons(s);
 598 }
 599
 600 template <class F>
 601 inline ssize_t NumOutputEpsilons(const F &fst, typename F::Arc::StateId s) {
 602   return fst.F::NumOutputEpsilons(s);
 603 }
 604
 605 // Fst<Arc> case, abstract methods.
 606
 607 template <class Arc>
 608 inline typename Arc::Weight Final(const Fst<Arc> &fst,
 609                                   typename Arc::StateId s) {
 610   return fst.Final(s);
 611 }
 612
 613 template <class Arc>
 614 inline size_t NumArcs(const Fst<Arc> &fst, typename Arc::StateId s) {
 615   return fst.NumArcs(s);
 616 }
 617
 618 template <class Arc>
 619 inline size_t NumInputEpsilons(const Fst<Arc> &fst, typename Arc::StateId s) {
 620   return fst.NumInputEpsilons(s);
 621 }
 622
 623 template <class Arc>
 624 inline size_t NumOutputEpsilons(const Fst<Arc> &fst, typename Arc::StateId s) {
 625   return fst.NumOutputEpsilons(s);
 626 }
 627
 628 // FST implementation base.
 629 //
 630 // This is the recommended FST implementation base class. It will handle
 631 // reference counts, property bits, type information and symbols.
 632 //
 633 // Users are discouraged, but not prohibited, from subclassing this outside the
 634 // FST library.
 635 template <class Arc>
 636 class FstImpl {
 637  public:
 638   using StateId = typename Arc::StateId;
 639   using Weight = typename Arc::Weight;
 640
 641   FstImpl() : properties_(0), type_("null") {}
 642
 643   FstImpl(const FstImpl<Arc> &impl)
 644       : properties_(impl.properties_),
 645         type_(impl.type_),
 646         isymbols_(impl.isymbols_ ? impl.isymbols_->Copy() : nullptr),
 647         osymbols_(impl.osymbols_ ? impl.osymbols_->Copy() : nullptr) {}
 648
 649   virtual ~FstImpl() {}
 650
 651   const string &Type() const { return type_; }
 652
 653   void SetType(const string &type) { type_ = type; }
 654
 655   virtual uint64 Properties() const { return properties_; }
 656
 657   virtual uint64 Properties(uint64 mask) const { return properties_ & mask; }
 658
 659   void SetProperties(uint64 props) {
 660     properties_ &= kError;  // kError can't be cleared.
 661     properties_ |= props;
 662   }
 663
 664   void SetProperties(uint64 props, uint64 mask) {
 665     properties_ &= ~mask | kError;  // kError can't be cleared.
 666     properties_ |= props & mask;
 667   }
 668
 669   // Allows (only) setting error bit on const FST implementations.
 670   void SetProperties(uint64 props, uint64 mask) const {
 671     if (mask != kError) {
 672       FSTERROR() << "FstImpl::SetProperties() const: Can only set kError";
 673     }
 674     properties_ |= kError;
 675   }
 676
 677   const SymbolTable *InputSymbols() const { return isymbols_.get(); }
 678
 679   const SymbolTable *OutputSymbols() const { return osymbols_.get(); }
 680
 681   SymbolTable *InputSymbols() { return isymbols_.get(); }
 682
 683   SymbolTable *OutputSymbols() { return osymbols_.get(); }
 684
 685   void SetInputSymbols(const SymbolTable *isyms) {
 686     isymbols_.reset(isyms ? isyms->Copy() : nullptr);
 687   }
 688
 689   void SetOutputSymbols(const SymbolTable *osyms) {
 690     osymbols_.reset(osyms ? osyms->Copy() : nullptr);
 691   }
 692
 693   // Reads header and symbols from input stream, initializes FST, and returns
 694   // the header. If opts.header is non-null, skips reading and uses the option
 695   // value instead. If opts.[io]symbols is non-null, reads in (if present), but
 696   // uses the option value.
 697   bool ReadHeader(std::istream &strm, const FstReadOptions &opts,
 698                   int min_version, FstHeader *hdr);
 699
 700   // Writes header and symbols to output stream. If opts.header is false, skips
 701   // writing header. If opts.[io]symbols is false, skips writing those symbols.
 702   // This method is needed for implementations that implement Write methods.
 703   void WriteHeader(std::ostream &strm, const FstWriteOptions &opts,
 704                    int version, FstHeader *hdr) const {
 705     if (opts.write_header) {
 706       hdr->SetFstType(type_);
 707       hdr->SetArcType(Arc::Type());
 708       hdr->SetVersion(version);
 709       hdr->SetProperties(properties_);
 710       int32 file_flags = 0;
 711       if (isymbols_ && opts.write_isymbols) {
 712         file_flags |= FstHeader::HAS_ISYMBOLS;
 713       }
 714       if (osymbols_ && opts.write_osymbols) {
 715         file_flags |= FstHeader::HAS_OSYMBOLS;
 716       }
 717       if (opts.align) file_flags |= FstHeader::IS_ALIGNED;
 718       hdr->SetFlags(file_flags);
 719       hdr->Write(strm, opts.source);
 720     }
 721     if (isymbols_ && opts.write_isymbols) isymbols_->Write(strm);
 722     if (osymbols_ && opts.write_osymbols) osymbols_->Write(strm);
 723   }
 724
 725   // Writes out header and symbols to output stream. If opts.header is false,
 726   // skips writing header. If opts.[io]symbols is false, skips writing those
 727   // symbols. `type` is the FST type being written. This method is used in the
 728   // cross-type serialization methods Fst::WriteFst.
 729   static void WriteFstHeader(const Fst<Arc> &fst, std::ostream &strm,
 730                              const FstWriteOptions &opts, int version,
 731                              const string &type, uint64 properties,
 732                              FstHeader *hdr) {
 733     if (opts.write_header) {
 734       hdr->SetFstType(type);
 735       hdr->SetArcType(Arc::Type());
 736       hdr->SetVersion(version);
 737       hdr->SetProperties(properties);
 738       int32 file_flags = 0;
 739       if (fst.InputSymbols() && opts.write_isymbols) {
 740         file_flags |= FstHeader::HAS_ISYMBOLS;
 741       }
 742       if (fst.OutputSymbols() && opts.write_osymbols) {
 743         file_flags |= FstHeader::HAS_OSYMBOLS;
 744       }
 745       if (opts.align) file_flags |= FstHeader::IS_ALIGNED;
 746       hdr->SetFlags(file_flags);
 747       hdr->Write(strm, opts.source);
 748     }
 749     if (fst.InputSymbols() && opts.write_isymbols) {
 750       fst.InputSymbols()->Write(strm);
 751     }
 752     if (fst.OutputSymbols() && opts.write_osymbols) {
 753       fst.OutputSymbols()->Write(strm);
 754     }
 755   }
 756
 757   // In serialization routines where the header cannot be written until after
 758   // the machine has been serialized, this routine can be called to seek to the
 759   // beginning of the file an rewrite the header with updated fields. It
 760   // repositions the file pointer back at the end of the file. Returns true on
 761   // success, false on failure.
 762   static bool UpdateFstHeader(const Fst<Arc> &fst, std::ostream &strm,
 763                               const FstWriteOptions &opts, int version,
 764                               const string &type, uint64 properties,
 765                               FstHeader *hdr, size_t header_offset) {
 766     strm.seekp(header_offset);
 767     if (!strm) {
 768       LOG(ERROR) << "Fst::UpdateFstHeader: Write failed: " << opts.source;
 769       return false;
 770     }
 771     WriteFstHeader(fst, strm, opts, version, type, properties, hdr);
 772     if (!strm) {
 773       LOG(ERROR) << "Fst::UpdateFstHeader: Write failed: " << opts.source;
 774       return false;
 775     }
 776     strm.seekp(0, std::ios_base::end);
 777     if (!strm) {
 778       LOG(ERROR) << "Fst::UpdateFstHeader: Write failed: " << opts.source;
 779       return false;
 780     }
 781     return true;
 782   }
 783
 784  protected:
 785   mutable uint64 properties_;  // Property bits.
 786
 787  private:
 788   string type_;  // Unique name of FST class.
 789   std::unique_ptr<SymbolTable> isymbols_;
 790   std::unique_ptr<SymbolTable> osymbols_;
 791 };
 792
 793 template <class Arc>
 794 bool FstImpl<Arc>::ReadHeader(std::istream &strm, const FstReadOptions &opts,
 795                               int min_version, FstHeader *hdr) {
 796   if (opts.header) {
 797     *hdr = *opts.header;
 798   } else if (!hdr->Read(strm, opts.source)) {
 799     return false;
 800   }
 801   if (FLAGS_v >= 2) {
 802     LOG(INFO) << "FstImpl::ReadHeader: source: " << opts.source
 803               << ", fst_type: " << hdr->FstType()
 804               << ", arc_type: " << Arc::Type()
 805               << ", version: " << hdr->Version()
 806               << ", flags: " << hdr->GetFlags();
 807   }
 808   if (hdr->FstType() != type_) {
 809     LOG(ERROR) << "FstImpl::ReadHeader: FST not of type " << type_
 810                << ": " << opts.source;
 811     return false;
 812   }
 813   if (hdr->ArcType() != Arc::Type()) {
 814     LOG(ERROR) << "FstImpl::ReadHeader: Arc not of type " << Arc::Type()
 815                << ": " << opts.source;
 816     return false;
 817   }
 818   if (hdr->Version() < min_version) {
 819     LOG(ERROR) << "FstImpl::ReadHeader: Obsolete " << type_
 820                << " FST version: " << opts.source;
 821     return false;
 822   }
 823   properties_ = hdr->Properties();
 824   if (hdr->GetFlags() & FstHeader::HAS_ISYMBOLS) {
 825     isymbols_.reset(SymbolTable::Read(strm, opts.source));
 826   }
 827   // Deletes input symbol table.
 828   if (!opts.read_isymbols) SetInputSymbols(nullptr);
 829   if (hdr->GetFlags() & FstHeader::HAS_OSYMBOLS) {
 830     osymbols_.reset(SymbolTable::Read(strm, opts.source));
 831   }
 832   // Deletes output symbol table.
 833   if (!opts.read_osymbols) SetOutputSymbols(nullptr);
 834   if (opts.isymbols) {
 835     isymbols_.reset(opts.isymbols->Copy());
 836   }
 837   if (opts.osymbols) {
 838     osymbols_.reset(opts.osymbols->Copy());
 839   }
 840   return true;
 841 }
 842
 843 }  // namespace internal
 844
 845 template <class Arc>
 846 uint64 TestProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known);
 847
 848 // This is a helper class template useful for attaching an FST interface to
 849 // its implementation, handling reference counting.
 850 template <class Impl, class FST = Fst<typename Impl::Arc>>
 851 class ImplToFst : public FST {
 852  public:
 853   using Arc = typename Impl::Arc;
 854   using StateId = typename Arc::StateId;
 855   using Weight = typename Arc::Weight;
 856   using FST::operator=;
 857
 858   StateId Start() const override { return impl_->Start(); }
 859
 860   Weight Final(StateId s) const override { return impl_->Final(s); }
 861
 862   size_t NumArcs(StateId s) const override { return impl_->NumArcs(s); }
 863
 864   size_t NumInputEpsilons(StateId s) const override {
 865     return impl_->NumInputEpsilons(s);
 866   }
 867
 868   size_t NumOutputEpsilons(StateId s) const override {
 869     return impl_->NumOutputEpsilons(s);
 870   }
 871
 872   uint64 Properties(uint64 mask, bool test) const override {
 873     if (test) {
 874       uint64 knownprops, testprops = TestProperties(*this, mask, &knownprops);
 875       impl_->SetProperties(testprops, knownprops);
 876       return testprops & mask;
 877     } else {
 878       return impl_->Properties(mask);
 879     }
 880   }
 881
 882   const string &Type() const override { return impl_->Type(); }
 883
 884   const SymbolTable *InputSymbols() const override {
 885     return impl_->InputSymbols();
 886   }
 887
 888   const SymbolTable *OutputSymbols() const override {
 889     return impl_->OutputSymbols();
 890   }
 891
 892  protected:
 893   explicit ImplToFst(std::shared_ptr<Impl> impl) : impl_(std::move(impl)) {}
 894
 895   // This constructor presumes there is a copy constructor for the
 896   // implementation.
 897   ImplToFst(const ImplToFst<Impl, FST> &fst, bool safe) {
 898     if (safe) {
 899       impl_ = std::make_shared<Impl>(*(fst.impl_));
 900     } else {
 901       impl_ = fst.impl_;
 902     }
 903   }
 904
 905   // Returns raw pointers to the shared object.
 906   const Impl *GetImpl() const { return impl_.get(); }
 907
 908   Impl *GetMutableImpl() const { return impl_.get(); }
 909
 910   // Returns a ref-counted smart poiner to the implementation.
 911   std::shared_ptr<Impl> GetSharedImpl() const { return impl_; }
 912
 913   bool Unique() const { return impl_.unique(); }
 914
 915   void SetImpl(std::shared_ptr<Impl> impl) { impl_ = impl; }
 916
 917  private:
 918   template <class IFST, class OFST>
 919   friend void Cast(const IFST &ifst, OFST *ofst);
 920
 921   std::shared_ptr<Impl> impl_;
 922 };
 923
 924 // Converts FSTs by casting their implementations, where this makes sense
 925 // (which excludes implementations with weight-dependent virtual methods).
 926 // Must be a friend of the FST classes involved (currently the concrete FSTs:
 927 // ConstFst, CompactFst, and VectorFst). This can only be safely used for arc
 928 // types that have identical storage characteristics. As with an FST
 929 // copy constructor and Copy() method, this is a constant time operation
 930 // (but subject to copy-on-write if it is a MutableFst and modified).
 931 template <class IFST, class OFST>
 932 void Cast(const IFST &ifst, OFST *ofst) {
 933   using OImpl = typename OFST::Impl;
 934   ofst->impl_ = std::shared_ptr<OImpl>(ifst.impl_,
 935       reinterpret_cast<OImpl *>(ifst.impl_.get()));
 936 }
 937
 938 // FST serialization.
 939
 940 template <class Arc>
 941 string FstToString(const Fst<Arc> &fst,
 942                    const FstWriteOptions &options =
 943                        FstWriteOptions("FstToString")) {
 944   std::ostringstream ostrm;
 945   fst.Write(ostrm, options);
 946   return ostrm.str();
 947 }
 948
 949 template <class Arc>
 950 void FstToString(const Fst<Arc> &fst, string *result) {
 951   *result = FstToString(fst);
 952 }
 953
 954 template <class Arc>
 955 void FstToString(const Fst<Arc> &fst, string *result,
 956                  const FstWriteOptions &options) {
 957   *result = FstToString(fst, options);
 958 }
 959
 960 template <class Arc>
 961 Fst<Arc> *StringToFst(const string &s) {
 962   std::istringstream istrm(s);
 963   return Fst<Arc>::Read(istrm, FstReadOptions("StringToFst"));
 964 }
 965
 966 }  // namespace fst
 967
 968 #endif  // FST_FST_H_