12cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// replace.h 22cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 32cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Licensed under the Apache License, Version 2.0 (the "License"); 42cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// you may not use this file except in compliance with the License. 52cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// You may obtain a copy of the License at 62cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 72cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// http://www.apache.org/licenses/LICENSE-2.0 82cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 92cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Unless required by applicable law or agreed to in writing, software 102cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// distributed under the License is distributed on an "AS IS" BASIS, 112cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// See the License for the specific language governing permissions and 132cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// limitations under the License. 142cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 152cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// \file 172cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Functions and classes for the recursive replacement of Fsts. 182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 190b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 200b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor#ifndef FST_LIB_REPLACE_H__ 212cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#define FST_LIB_REPLACE_H__ 227c5d24efcd2e505b5739f7def08dfe25ce59a1b2Chris Lattner 237c5d24efcd2e505b5739f7def08dfe25ce59a1b2Chris Lattner#include <unordered_map> 2414f79002e58556798e86168c63e48d533287eda5Douglas Gregor 2514f79002e58556798e86168c63e48d533287eda5Douglas Gregor#include "fst/lib/fst.h" 26bd94500d3aa60092fb0f1e90f53fb0d03fa502a8Douglas Gregor#include "fst/lib/cache.h" 272bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor#include "fst/lib/test-properties.h" 2817fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor 2917fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregornamespace fst { 302cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 312cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// By default ReplaceFst will copy the input label of the 'replace arc'. 3214f79002e58556798e86168c63e48d533287eda5Douglas Gregor// For acceptors we do not want this behaviour. Instead we need to 333c304bd9ec2b4611572d4cbae9e1727bbecb5dc9Chris Lattner// create an epsilon arc when recursing into the appropriate Fst. 342cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// The epsilon_on_replace option can be used to toggle this behaviour. 352cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregorstruct ReplaceFstOptions : CacheOptions { 362cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int64 root; // root rule for expansion 372cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bool epsilon_on_replace; 382cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 392cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ReplaceFstOptions(const CacheOptions &opts, int64 r) 402cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : CacheOptions(opts), root(r), epsilon_on_replace(false) {} 412cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor explicit ReplaceFstOptions(int64 r) 422cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : root(r), epsilon_on_replace(false) {} 432cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ReplaceFstOptions(int64 r, bool epsilon_replace_arc) 442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : root(r), epsilon_on_replace(epsilon_replace_arc) {} 452cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ReplaceFstOptions() 462cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : root(kNoLabel), epsilon_on_replace(false) {} 472cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor}; 482cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 492cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 502cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// \class ReplaceFstImpl 512cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// \brief Implementation class for replace class Fst 522cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 532cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// The replace implementation class supports a dynamic 542cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// expansion of a recursive transition network represented as Fst 552cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// with dynamic replacable arcs. 562cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 572cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregortemplate <class A> 582cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregorclass ReplaceFstImpl : public CacheImpl<A> { 592cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor public: 602cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::SetType; 612cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::SetProperties; 622cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::Properties; 632cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::SetInputSymbols; 642cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::SetOutputSymbols; 652cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::InputSymbols; 662cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using FstImpl<A>::OutputSymbols; 672cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 682cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using CacheImpl<A>::HasStart; 692cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using CacheImpl<A>::HasArcs; 702cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor using CacheImpl<A>::SetStart; 712cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 722cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef typename A::Label Label; 732cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef typename A::Weight Weight; 742cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef typename A::StateId StateId; 752cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef CacheState<A> State; 762cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef A Arc; 772cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef std::unordered_map<Label, Label> NonTerminalHash; 782cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 792cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 802cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \struct StateTuple 812cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \brief Tuple of information that uniquely defines a state 822cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor struct StateTuple { 832cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typedef int PrefixId; 842cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 852cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateTuple() {} 862cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateTuple(PrefixId p, StateId f, StateId s) : 872cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor prefix_id(p), fst_id(f), fst_state(s) {} 882cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 892cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor PrefixId prefix_id; // index in prefix table 902cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId fst_id; // current fst being walked 912cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId fst_state; // current state in fst being walked, not to be 922cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // confused with the state_id of the combined fst 932cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor }; 942cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 952cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // constructor for replace class implementation. 962cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \param fst_tuples array of label/fst tuples, one for each non-terminal 972cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ReplaceFstImpl(const vector< pair<Label, const Fst<A>* > >& fst_tuples, 982cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const ReplaceFstOptions &opts) 992cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : CacheImpl<A>(opts), opts_(opts) { 1002cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetType("replace"); 1012cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (fst_tuples.size() > 0) { 1022cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetInputSymbols(fst_tuples[0].second->InputSymbols()); 1032cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetOutputSymbols(fst_tuples[0].second->OutputSymbols()); 1042cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1052cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1062cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor fst_array_.push_back(0); 1072cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 0; i < fst_tuples.size(); ++i) 1082cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor AddFst(fst_tuples[i].first, fst_tuples[i].second); 1092cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1102cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetRoot(opts.root); 1112cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1132cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor explicit ReplaceFstImpl(const ReplaceFstOptions &opts) 1142cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : CacheImpl<A>(opts), opts_(opts), root_(kNoLabel) { 1152cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor fst_array_.push_back(0); 1162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1172cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ReplaceFstImpl(const ReplaceFstImpl& impl) 1192cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor : opts_(impl.opts_), state_tuples_(impl.state_tuples_), 1202cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor state_hash_(impl.state_hash_), 1212cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor prefix_hash_(impl.prefix_hash_), 1222cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor stackprefix_array_(impl.stackprefix_array_), 1232cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor nonterminal_hash_(impl.nonterminal_hash_), 1242cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor root_(impl.root_) { 1252cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetType("replace"); 1262cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetProperties(impl.Properties(), kCopyProperties); 1272cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetInputSymbols(InputSymbols()); 1282cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetOutputSymbols(OutputSymbols()); 1290b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor fst_array_.reserve(impl.fst_array_.size()); 1302cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor fst_array_.push_back(0); 1312cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 1; i < impl.fst_array_.size(); ++i) 1322cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor fst_array_.push_back(impl.fst_array_[i]->Copy()); 1332cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1342cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1352cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ~ReplaceFstImpl() { 1362cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 1; i < fst_array_.size(); ++i) { 1372cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor delete fst_array_[i]; 1382cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1392cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1402cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1412cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // Add to Fst array 1422cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void AddFst(Label label, const Fst<A>* fst) { 1432cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor nonterminal_hash_[label] = fst_array_.size(); 1442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor fst_array_.push_back(fst->Copy()); 1452cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (fst_array_.size() > 1) { 1462cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor vector<uint64> inprops(fst_array_.size()); 1472cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1482cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 1; i < fst_array_.size(); ++i) { 1492cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor inprops[i] = fst_array_[i]->Properties(kCopyProperties, false); 1502cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1512cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetProperties(ReplaceProperties(inprops)); 1522cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1532cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const SymbolTable* isymbols = fst_array_[1]->InputSymbols(); 1542cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const SymbolTable* osymbols = fst_array_[1]->OutputSymbols(); 1552cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 2; i < fst_array_.size(); ++i) { 1562cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (!CompatSymbols(isymbols, fst_array_[i]->InputSymbols())) { 1572cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor LOG(FATAL) << "ReplaceFst::AddFst input symbols of Fst " << i-1 1582cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor << " does not match input symbols of base Fst (0'th fst)"; 1592cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1602cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (!CompatSymbols(osymbols, fst_array_[i]->OutputSymbols())) { 1612cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor LOG(FATAL) << "ReplaceFst::AddFst output symbols of Fst " << i-1 1622cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor << " does not match output symbols of base Fst " 1632cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor << "(0'th fst)"; 1642cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1652cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1662cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1672cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1682cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1690b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // Computes the dependency graph of the replace class and returns 1702cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // true if the dependencies are cyclic. Cyclic dependencies will result 1712cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // in an un-expandable replace fst. 1722cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bool CyclicDependencies() const { 1732cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StdVectorFst depfst; 1742cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1752cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // one state for each fst 1762cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 1; i < fst_array_.size(); ++i) 1772cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor depfst.AddState(); 1782cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1792cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // an arc from each state (representing the fst) to the 1802cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // state representing the fst being replaced 1812cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (size_t i = 1; i < fst_array_.size(); ++i) { 1822cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (StateIterator<Fst<A> > siter(*(fst_array_[i])); 1832cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor !siter.Done(); siter.Next()) { 1842cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (ArcIterator<Fst<A> > aiter(*(fst_array_[i]), siter.Value()); 1852cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor !aiter.Done(); aiter.Next()) { 1862cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const A& arc = aiter.Value(); 1872cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1882cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typename NonTerminalHash::const_iterator it = 1892cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor nonterminal_hash_.find(arc.olabel); 1902cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (it != nonterminal_hash_.end()) { 1912cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Label j = it->second - 1; 1922cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor depfst.AddArc(i - 1, A(arc.olabel, arc.olabel, Weight::One(), j)); 1932cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1942cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1952cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1962cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1972cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1982cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor depfst.SetStart(root_ - 1); 1992cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor depfst.SetFinal(root_ - 1, Weight::One()); 2002cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return depfst.Properties(kCyclic, true); 2012cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2022cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2032cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // set root rule for expansion 2042cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void SetRoot(Label root) { 2052cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Label nonterminal = nonterminal_hash_[root]; 2062cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor root_ = (nonterminal > 0) ? nonterminal : 1; 2072cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2082cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2092cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // Change Fst array 2102cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void SetFst(Label label, const Fst<A>* fst) { 2112cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Label nonterminal = nonterminal_hash_[label]; 2122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor delete fst_array_[nonterminal]; 2132cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor fst_array_[nonterminal] = fst->Copy(); 2142cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2152cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // Return or compute start state of replace fst 2172cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId Start() { 2182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (!HasStart()) { 2192cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (fst_array_.size() == 1) { // no fsts defined for replace 2202cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetStart(kNoStateId); 2212cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return kNoStateId; 2222cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } else { 2232cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const Fst<A>* fst = fst_array_[root_]; 2242cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId fst_start = fst->Start(); 2252cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (fst_start == kNoStateId) // root Fst is empty 2262cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return kNoStateId; 2272cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2282cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int prefix = PrefixId(StackPrefix()); 2292cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId start = FindState(StateTuple(prefix, root_, fst_start)); 2302cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetStart(start); 2312cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return start; 2322cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2332cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } else { 2342cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return CacheImpl<A>::Start(); 2352cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2362cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2372cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2382cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // return final weight of state (kInfWeight means state is not final) 2392cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Weight Final(StateId s) { 2402cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (!HasFinal(s)) { 2412cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const StateTuple& tuple = state_tuples_[s]; 2422cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const StackPrefix& stack = stackprefix_array_[tuple.prefix_id]; 2432cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const Fst<A>* fst = fst_array_[tuple.fst_id]; 2442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId fst_state = tuple.fst_state; 2452cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2462cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (fst->Final(fst_state) != Weight::Zero() && stack.Depth() == 0) 2472cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetFinal(s, fst->Final(fst_state)); 2482cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor else 2492cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetFinal(s, Weight::Zero()); 2502cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2512cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return CacheImpl<A>::Final(s); 2522cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2532cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2542cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor size_t NumArcs(StateId s) { 2552cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (!HasArcs(s)) 2562cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Expand(s); 2570a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor return CacheImpl<A>::NumArcs(s); 2580a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor } 2598c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor 2602cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor size_t NumInputEpsilons(StateId s) { 2610a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor if (!HasArcs(s)) 2623a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor Expand(s); 2638c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor return CacheImpl<A>::NumInputEpsilons(s); 2642cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2653a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 2663a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor size_t NumOutputEpsilons(StateId s) { 2671028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor if (!HasArcs(s)) 2681028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor Expand(s); 2692cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return CacheImpl<A>::NumOutputEpsilons(s); 2702cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2712cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2722cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // return the base arc iterator, if arcs have not been computed yet, 2732cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // extend/recurse for new arcs. 2742cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 2752cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (!HasArcs(s)) 2762cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Expand(s); 2772cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor CacheImpl<A>::InitArcIterator(s, data); 2782cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2792cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2802cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // Find/create an Fst state given a StateTuple. Only create a new 2812cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // state if StateTuple is not found in the state hash. 2822cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId FindState(const StateTuple& tuple) { 2832cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typename StateTupleHash::iterator it = state_hash_.find(tuple); 2842cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (it == state_hash_.end()) { 2852cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId new_state_id = state_tuples_.size(); 2862cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor state_tuples_.push_back(tuple); 2872cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor state_hash_[tuple] = new_state_id; 2882cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return new_state_id; 2892cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } else { 2902cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return it->second; 2912cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2922cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2932cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2942cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // extend current state (walk arcs one level deep) 2952cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Expand(StateId s) { 2962cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateTuple tuple = state_tuples_[s]; 2972cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const Fst<A>* fst = fst_array_[tuple.fst_id]; 2982cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor StateId fst_state = tuple.fst_state; 2992cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (fst_state == kNoStateId) { 3002cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor SetArcs(s); 3012cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return; 3022cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 3032cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 3042cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // if state is final, pop up stack 3050a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor const StackPrefix& stack = stackprefix_array_[tuple.prefix_id]; 3060a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor if (fst->Final(fst_state) != Weight::Zero() && stack.Depth()) { 3070a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor int prefix_id = PopPrefix(stack); 3080a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor const PrefixTuple& top = stack.Top(); 3090a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor 3100a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor StateId nextstate = 3110a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor FindState(StateTuple(prefix_id, top.fst_id, top.nextstate)); 3120a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor AddArc(s, A(0, 0, fst->Final(fst_state), nextstate)); 3130a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor } 3140a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor 3150a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor // extend arcs leaving the state 3160a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor for (ArcIterator< Fst<A> > aiter(*fst, fst_state); 3170a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor !aiter.Done(); aiter.Next()) { 3188c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor const Arc& arc = aiter.Value(); 3198c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor if (arc.olabel == 0) { // expand local fst 3208c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor StateId nextstate = 3218c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor FindState(StateTuple(tuple.prefix_id, tuple.fst_id, arc.nextstate)); 3228c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor AddArc(s, A(arc.ilabel, arc.olabel, arc.weight, nextstate)); 3238c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor } else { 3248c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor // check for non terminal 3252cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor typename NonTerminalHash::const_iterator it = 3262cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor nonterminal_hash_.find(arc.olabel); 3272cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (it != nonterminal_hash_.end()) { // recurse into non terminal 3282cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Label nonterminal = it->second; 3292cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const Fst<A>* nt_fst = fst_array_[nonterminal]; 3300a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor int nt_prefix = PushPrefix(stackprefix_array_[tuple.prefix_id], 3310a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor tuple.fst_id, arc.nextstate); 3320b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 3330b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // if start state is valid replace, else arc is implicitly 3340b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // deleted 3350a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor StateId nt_start = nt_fst->Start(); 3360a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor if (nt_start != kNoStateId) { 3370a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor StateId nt_nextstate = FindState( 3380a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor StateTuple(nt_prefix, nonterminal, nt_start)); 3393a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor Label ilabel = (opts_.epsilon_on_replace) ? 0 : arc.ilabel; 3403a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor AddArc(s, A(ilabel, 0, arc.weight, nt_nextstate)); 3413a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor } 3423a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor } else { 3433a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor StateId nextstate = 3443a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor FindState( 3453a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor StateTuple(tuple.prefix_id, tuple.fst_id, arc.nextstate)); 3463a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor AddArc(s, A(arc.ilabel, arc.olabel, arc.weight, nextstate)); 3473a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor } 3483a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor } 3493a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor } 3503a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3513a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor SetArcs(s); 3523a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor } 3533a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3543a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3553a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor // private helper classes 3563a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor private: 3573a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor static const int kPrime0 = 7853; 3588c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor static const int kPrime1 = 7867; 3598c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor 3608c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor // \class StateTupleEqual 3610b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // \brief Compare two StateTuples for equality 3620b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor class StateTupleEqual { 3630b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor public: 3648c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor bool operator()(const StateTuple& x, const StateTuple& y) const { 3658c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor return ((x.prefix_id == y.prefix_id) && (x.fst_id == y.fst_id) && 3668c70006581a9b9e9485570ca727a6c5f7be63521Douglas Gregor (x.fst_state == y.fst_state)); 3672cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 3682cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor }; 3693a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3702cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \class StateTupleKey 3712cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \brief Hash function for StateTuple to Fst states 3722cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor class StateTupleKey { 3732cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor public: 3742cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor size_t operator()(const StateTuple& x) const { 3750b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor return static_cast<size_t>(x.prefix_id + 3760b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor x.fst_id * kPrime0 + 3770b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor x.fst_state * kPrime1); 3782cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 3792cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor }; 3802cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 3813a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor typedef std::unordered_map<StateTuple, StateId, StateTupleKey, StateTupleEqual> 3823a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor StateTupleHash; 3833a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3843a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor // \class PrefixTuple 3853a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor // \brief Tuple of fst_id and destination state (entry in stack prefix) 3863a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor struct PrefixTuple { 3873a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor PrefixTuple(Label f, StateId s) : fst_id(f), nextstate(s) {} 3883a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3893a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor Label fst_id; 3903a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor StateId nextstate; 3913a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor }; 3923a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor 3933a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor // \class StackPrefix 3943a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor // \brief Container for stack prefix. 3953a2f7e42514ddbec983c61826ce85d3071e23e8eDouglas Gregor class StackPrefix { 3961028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor public: 3971028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor StackPrefix() {} 3981028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor 3991028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor // copy constructor 4001028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor StackPrefix(const StackPrefix& x) : 4011028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor prefix_(x.prefix_) { 4021028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor } 4031028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor 4041028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor void Push(int fst_id, StateId nextstate) { 4051028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor prefix_.push_back(PrefixTuple(fst_id, nextstate)); 4061028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor } 4071028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor 4081028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor void Pop() { 4091028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor prefix_.pop_back(); 4101028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor } 4111028bc67d56ea088c3a57c4c44c3f6aeff60a031Douglas Gregor 4122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const PrefixTuple& Top() const { 4132cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return prefix_[prefix_.size()-1]; 4142cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 4152cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 4162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor size_t Depth() const { 4172cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor return prefix_.size(); 4182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 4192cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 4202cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor public: 4212cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor vector<PrefixTuple> prefix_; 4222cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor }; 4232cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 4242cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 4252cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \class StackPrefixEqual 4262cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // \brief Compare two stack prefix classes for equality 4272cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor class StackPrefixEqual { 4282cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor public: 4292cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bool operator()(const StackPrefix& x, const StackPrefix& y) const { 4302cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (x.prefix_.size() != y.prefix_.size()) return false; 4310b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor for (size_t i = 0; i < x.prefix_.size(); ++i) { 4320b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor if (x.prefix_[i].fst_id != y.prefix_[i].fst_id || 4330b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor x.prefix_[i].nextstate != y.prefix_[i].nextstate) return false; 4340b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } 4350b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor return true; 4360b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } 4370b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor }; 4380b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 4390b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // 4400b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // \class StackPrefixKey 4410b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // \brief Hash function for stack prefix to prefix id 4420b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor class StackPrefixKey { 4430b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor public: 4440b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor size_t operator()(const StackPrefix& x) const { 4450b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor int sum = 0; 4460b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor for (size_t i = 0; i < x.prefix_.size(); ++i) { 44717fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor sum += x.prefix_[i].fst_id + x.prefix_[i].nextstate*kPrime0; 4480b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } 4490b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor return (size_t) sum; 45017fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor } 451673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor }; 4520b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 453c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor typedef std::unordered_map<StackPrefix, int, StackPrefixKey, StackPrefixEqual> 4540b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor StackPrefixHash; 4550b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor 4561f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor // private methods 4571f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor private: 458087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor // hash stack prefix (return unique index into stackprefix array) 459db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor int PrefixId(const StackPrefix& prefix) { 460087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor typename StackPrefixHash::iterator it = prefix_hash_.find(prefix); 461db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor if (it == prefix_hash_.end()) { 462db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor int prefix_id = stackprefix_array_.size(); 4630b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor stackprefix_array_.push_back(prefix); 4640b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor prefix_hash_[prefix] = prefix_id; 4650b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor return prefix_id; 4660b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } else { 4670b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor return it->second; 4680b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } 4690b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } 4700b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 4710b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // prefix id after a stack pop 47217fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor int PopPrefix(StackPrefix prefix) { 47317fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor prefix.Pop(); 47417fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor return PrefixId(prefix); 47517fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor } 47617fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor 47717fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor // prefix id after a stack push 47817fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor int PushPrefix(StackPrefix prefix, Label fst_id, StateId nextstate) { 4790b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor prefix.Push(fst_id, nextstate); 4800b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor return PrefixId(prefix); 4810b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor } 4820b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 4830b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 4840b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // private data 4850b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor private: 4860b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // runtime options 4870b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor ReplaceFstOptions opts_; 4880b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 4890b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // maps from StateId to StateTuple 4900b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor vector<StateTuple> state_tuples_; 4910b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 4920b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor // hashes from StateTuple to StateId 49317fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor StateTupleHash state_hash_; 49417fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor 49517fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor // cross index of unique stack prefix 49617fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor // could potentially have one copy of prefix array 49717fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor StackPrefixHash prefix_hash_; 49817fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor vector<StackPrefix> stackprefix_array_; 49917fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor 50017fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor NonTerminalHash nonterminal_hash_; 501673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor vector<const Fst<A>*> fst_array_; 502673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor 503673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor Label root_; 504673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor 505673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor void operator=(const ReplaceFstImpl<A> &); // disallow 506673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor}; 507673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor 508673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor 509673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// 510673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// \class ReplaceFst 511673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// \brief Recursivively replaces arcs in the root Fst with other Fsts. 512673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// This version is a delayed Fst. 513673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// 514673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// ReplaceFst supports dynamic replacement of arcs in one Fst with 515673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// another Fst. This replacement is recursive. ReplaceFst can be used 516673ecd6a4a9f7c12fb6f76f84f654dbdcdc89e76Douglas Gregor// to support a variety of delayed constructions such as recursive 5170b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// transition networks, union, or closure. It is constructed with an 5180b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// array of Fst(s). One Fst represents the root (or topology) 5190b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// machine. The root Fst refers to other Fsts by recursively replacing 5200b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// arcs labeled as non-terminals with the matching non-terminal 5210b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// Fst. Currently the ReplaceFst uses the output symbols of the arcs 5220b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// to determine whether the arc is a non-terminal arc or not. A 5230b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// non-terminal can be any label that is not a non-zero terminal label 5240b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// in the output alphabet. 525c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// 526c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// Note that the constructor uses a vector of pair<>. These correspond 527c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// to the tuple of non-terminal Label and corresponding Fst. For example 528c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// to implement the closure operation we need 2 Fsts. The first root 529c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// Fst is a single Arc on the start State that self loops, it references 530c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// the particular machine for which we are performing the closure operation. 531c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregor// 532c04db4feefa2b0dbbc6876cb4eeeee108aa6791dDouglas Gregortemplate <class A> 5330b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregorclass ReplaceFst : public Fst<A> { 5340b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor public: 5350b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor friend class ArcIterator< ReplaceFst<A> >; 5360b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor friend class CacheStateIterator< ReplaceFst<A> >; 5370b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor friend class CacheArcIterator< ReplaceFst<A> >; 5380b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor 5390b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor typedef A Arc; 5400b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor typedef typename A::Label Label; 5410b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor typedef typename A::Weight Weight; 5420b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor typedef typename A::StateId StateId; 5430b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor typedef CacheState<A> State; 5440b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor 5450b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor ReplaceFst(const vector<pair<Label, const Fst<A>* > >& fst_array, 5460b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor Label root) 5470b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor : impl_(new ReplaceFstImpl<A>(fst_array, ReplaceFstOptions(root))) {} 5480b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor 5490b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor ReplaceFst(const vector<pair<Label, const Fst<A>* > >& fst_array, 5500b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor const ReplaceFstOptions &opts) 5510b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor : impl_(new ReplaceFstImpl<A>(fst_array, opts)) {} 5520b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor 5530b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor ReplaceFst(const ReplaceFst<A>& fst) : 5540b0b77fa29c74c99a77548ed86ca8a04f7cf6b02Douglas Gregor impl_(new ReplaceFstImpl<A>(*(fst.impl_))) {} 5551f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor 5561f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor virtual ~ReplaceFst() { 5571f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor delete impl_; 5581f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor } 5591f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor 5601f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor virtual StateId Start() const { 5611f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor return impl_->Start(); 5621f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor } 5631f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor 5641f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor virtual Weight Final(StateId s) const { 5651f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor return impl_->Final(s); 5661f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor } 5671f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor 5681f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor virtual size_t NumArcs(StateId s) const { 5691f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor return impl_->NumArcs(s); 5701f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor } 5711f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor 5721f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor virtual size_t NumInputEpsilons(StateId s) const { 5731f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor return impl_->NumInputEpsilons(s); 5741f0d0133b0e8d1f01f63951ee04927796b34740dDouglas Gregor } 575087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor 576087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor virtual size_t NumOutputEpsilons(StateId s) const { 577087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor return impl_->NumOutputEpsilons(s); 578087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor } 579087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor 580db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor virtual uint64 Properties(uint64 mask, bool test) const { 581db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor if (test) { 582db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor uint64 known, test = TestProperties(*this, mask, &known); 583db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor impl_->SetProperties(test, known); 584db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor return test & mask; 585db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor } else { 586db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor return impl_->Properties(mask); 587db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor } 588db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor } 589087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor 590087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor virtual const string& Type() const { 591087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor return impl_->Type(); 592087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor } 593087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor 594087fd536809ebe754d91c641a98917e02dd7452dDouglas Gregor virtual ReplaceFst<A>* Copy() const { 595db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor return new ReplaceFst<A>(*this); 596db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor } 597db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor 598db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor virtual const SymbolTable* InputSymbols() const { 599db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor return impl_->InputSymbols(); 600db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor } 601db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor 602db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor virtual const SymbolTable* OutputSymbols() const { 603db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor return impl_->OutputSymbols(); 604db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor } 605db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor 606db600c330a37b1c3ab4533310729910ee188f900Douglas Gregor virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 6070b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor 6082cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 6092cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor impl_->InitArcIterator(s, data); 6102cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 6112bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor 6122bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor bool CyclicDependencies() const { 6132bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor return impl_->CyclicDependencies(); 6142bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor } 6152bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor 6162bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor private: 6172bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor ReplaceFstImpl<A>* impl_; 6182bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor}; 6192bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor 6202bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor 6212bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor// Specialization for ReplaceFst. 6222bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregortemplate<class A> 6232bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregorclass StateIterator< ReplaceFst<A> > 6242bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor : public CacheStateIterator< ReplaceFst<A> > { 6252bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor public: 6260a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor explicit StateIterator(const ReplaceFst<A> &fst) 6270a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor : CacheStateIterator< ReplaceFst<A> >(fst) {} 6280a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6290a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor private: 6300a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor DISALLOW_EVIL_CONSTRUCTORS(StateIterator); 6310a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor}; 6320a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6330a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// Specialization for ReplaceFst. 6340a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregortemplate <class A> 6350a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregorclass ArcIterator< ReplaceFst<A> > 6360a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor : public CacheArcIterator< ReplaceFst<A> > { 6370a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor public: 6380a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor typedef typename A::StateId StateId; 6390a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6400a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor ArcIterator(const ReplaceFst<A> &fst, StateId s) 6410a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor : CacheArcIterator< ReplaceFst<A> >(fst, s) { 6420a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor if (!fst.impl_->HasArcs(s)) 6430a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor fst.impl_->Expand(s); 6440a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor } 6450a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6460a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor private: 6470a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 6480a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor}; 6490a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6500a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregortemplate <class A> inline 6510a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregorvoid ReplaceFst<A>::InitStateIterator(StateIteratorData<A> *data) const { 6520a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor data->base = new StateIterator< ReplaceFst<A> >(*this); 6530a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor} 6540a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6550a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregortypedef ReplaceFst<StdArc> StdReplaceFst; 6560a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6570a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6580a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// // Recursivively replaces arcs in the root Fst with other Fsts. 6590a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// This version writes the result of replacement to an output MutableFst. 6600a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// 6610a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// Replace supports replacement of arcs in one Fst with another 6620a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// Fst. This replacement is recursive. Replace takes an array of 6630a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// Fst(s). One Fst represents the root (or topology) machine. The root 6640a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// Fst refers to other Fsts by recursively replacing arcs labeled as 6650a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// non-terminals with the matching non-terminal Fst. Currently Replace 6660a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// uses the output symbols of the arcs to determine whether the arc is 6670a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// a non-terminal arc or not. A non-terminal can be any label that is 6680a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// not a non-zero terminal label in the output alphabet. Note that 6690a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// input argument is a vector of pair<>. These correspond to the tuple 6700a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// of non-terminal Label and corresponding Fst. 6710a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregortemplate<class Arc> 6720a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregorvoid Replace(const vector<pair<typename Arc::Label, 6730a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor const Fst<Arc>* > >& ifst_array, 6740a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor MutableFst<Arc> *ofst, typename Arc::Label root) { 6750a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor ReplaceFstOptions opts(root); 6760a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor opts.gc_limit = 0; // Cache only the last state for fastest copy. 6770a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor *ofst = ReplaceFst<Arc>(ifst_array, opts); 6780a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor} 6790a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6800a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor} 6810a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor 6820a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor#endif // FST_LIB_REPLACE_H__ 6830a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor