41 #include <unordered_map> 55 bool gc = FST_FLAGS_fst_default_cache_gc,
56 size_t gc_limit = FST_FLAGS_fst_default_cache_gc_limit)
57 : gc(gc), gc_limit(gc_limit) {}
62 template <
class CacheStore>
70 bool gc = FST_FLAGS_fst_default_cache_gc,
71 size_t gc_limit = FST_FLAGS_fst_default_cache_gc_limit,
72 CacheStore *store =
nullptr)
73 : gc(gc), gc_limit(gc_limit), store(store), own_store(true) {}
76 : gc(opts.gc), gc_limit(opts.gc_limit), store(nullptr), own_store(true) {}
88 template <
class A,
class M = PoolAllocator<A>>
92 using Label =
typename Arc::Label;
102 : final_weight_(
Weight::Zero()),
110 : final_weight_(state.
Final()),
113 arcs_(state.arcs_.begin(), state.arcs_.end(), alloc),
114 flags_(state.Flags()),
118 final_weight_ = Weight::Zero();
132 size_t NumArcs()
const {
return arcs_.size(); }
137 const Arc *
Arcs()
const {
return !arcs_.empty() ? &arcs_[0] :
nullptr; }
140 uint8_t
Flags()
const {
return flags_; }
146 final_weight_ = std::move(weight);
154 IncrementNumEpsilons(arc);
155 arcs_.push_back(arc);
159 IncrementNumEpsilons(arc);
160 arcs_.push_back(std::move(arc));
169 template <
class... T>
171 arcs_.emplace_back(std::forward<T>(ctor_args)...);
176 for (
const auto &arc : arcs_) {
177 IncrementNumEpsilons(arc);
183 if (arcs_[n].ilabel == 0) --niepsilons_;
184 if (arcs_[n].olabel == 0) --noepsilons_;
185 IncrementNumEpsilons(arc);
197 for (
size_t i = 0; i < n; ++i) {
198 if (arcs_.back().ilabel == 0) --niepsilons_;
199 if (arcs_.back().olabel == 0) --noepsilons_;
221 return alloc->allocate(1);
227 state->~CacheState<
Arc>();
228 alloc->deallocate(state, 1);
234 void IncrementNumEpsilons(
const Arc &arc) {
235 if (arc.ilabel == 0) ++niepsilons_;
236 if (arc.olabel == 0) ++noepsilons_;
242 std::vector<Arc, ArcAllocator> arcs_;
243 mutable uint8_t flags_;
244 mutable int ref_count_;
316 using StateList = std::list<StateId, PoolAllocator<StateId>>;
325 : cache_gc_(store.cache_gc_) {
333 if (
this != &store) {
341 return s < static_cast<StateId>(state_vec_.size());
346 return InBounds(s) ? state_vec_[s] :
nullptr;
351 State *state =
nullptr;
353 state = state_vec_[s];
355 state_vec_.resize(s + 1,
nullptr);
358 state =
new (&state_alloc_)
State(arc_alloc_);
359 state_vec_[s] = state;
360 if (cache_gc_) state_list_.push_back(s);
380 for (
State *s : state_vec_) {
388 return std::count_if(state_vec_.begin(), state_vec_.end(),
389 [](
const State *s) {
return s !=
nullptr; });
394 bool Done()
const {
return iter_ == state_list_.end(); }
400 void Reset() { iter_ = state_list_.begin(); }
405 state_vec_[*iter_] =
nullptr;
406 state_list_.erase(iter_++);
412 state_vec_.reserve(store.state_vec_.size());
413 for (
size_t s = 0; s < store.state_vec_.size(); ++s) {
414 State *state =
nullptr;
415 const auto *store_state = store.state_vec_[s];
417 state =
new (&state_alloc_)
State(*store_state, arc_alloc_);
418 if (cache_gc_) state_list_.push_back(s);
420 state_vec_.push_back(state);
425 std::vector<State *> state_vec_;
427 typename StateList::iterator iter_;
429 typename State::ArcAllocator arc_alloc_;
437 using Arc =
typename State::Arc;
441 std::unordered_map<StateId, State *, std::hash<StateId>,
442 std::equal_to<StateId>,
459 if (
this != &store) {
468 const auto it = state_map_.find(s);
469 return it != state_map_.end() ? it->second :
nullptr;
474 auto *&state = state_map_[s];
475 if (!state) state =
new (&state_alloc_)
State(arc_alloc_);
494 for (
auto &[unused_state_id, state_ptr] : state_map_) {
503 bool Done()
const {
return iter_ == state_map_.end(); }
509 void Reset() { iter_ = state_map_.begin(); }
514 state_map_.erase(iter_++);
520 for (
auto &[state_id, state_ptr] : store.state_map_) {
521 state_map_[state_id] =
new (&state_alloc_)
State(*state_ptr, arc_alloc_);
526 typename StateMap::iterator iter_;
527 typename State::StateAllocator state_alloc_;
528 typename State::ArcAllocator arc_alloc_;
542 template <
class CacheStore>
545 using State =
typename CacheStore::State;
546 using Arc =
typename State::Arc;
554 cache_first_state_(nullptr) {}
557 : store_(store.store_),
558 cache_gc_(store.cache_gc_),
559 cache_first_state_id_(store.cache_first_state_id_),
560 cache_first_state_(store.cache_first_state_id_ !=
kNoStateId 561 ? store_.GetMutableState(0)
566 if (
this != &store) {
567 store_ = store.store_;
568 cache_gc_ = store.cache_gc_;
569 cache_first_state_id_ = store.cache_first_state_id_;
570 cache_first_state_ = store.cache_first_state_id_ !=
kNoStateId 571 ? store_.GetMutableState(0)
580 return s == cache_first_state_id_ ? cache_first_state_
581 : store_.GetState(s + 1);
588 if (cache_first_state_id_ == s) {
589 return cache_first_state_;
593 cache_first_state_id_ = s;
594 cache_first_state_ = store_.GetMutableState(0);
595 cache_first_state_->SetFlags(kCacheInit, kCacheInit);
596 cache_first_state_->ReserveArcs(2 *
kAllocSize);
597 return cache_first_state_;
598 }
else if (cache_first_state_->RefCount() == 0) {
599 cache_first_state_id_ = s;
600 cache_first_state_->Reset();
601 cache_first_state_->SetFlags(kCacheInit, kCacheInit);
602 return cache_first_state_;
604 cache_first_state_->SetFlags(0, kCacheInit);
608 auto *state = store_.GetMutableState(s + 1);
613 void AddArc(State *state,
const Arc &arc) { store_.AddArc(state, arc); }
617 void SetArcs(State *state) { store_.SetArcs(state); }
623 void DeleteArcs(State *state,
size_t n) { store_.DeleteArcs(state, n); }
629 cache_first_state_ =
nullptr;
636 bool Done()
const {
return store_.Done(); }
640 const auto s = store_.Value();
641 return s ? s - 1 : cache_first_state_id_;
650 if (Value() == cache_first_state_id_) {
652 cache_first_state_ =
nullptr;
661 State *cache_first_state_;
670 template <
class CacheStore>
673 using State =
typename CacheStore::State;
674 using Arc =
typename State::Arc;
680 cache_gc_request_(opts.
gc),
691 auto *state = store_.GetMutableState(s);
692 if (cache_gc_request_ && !(state->Flags() &
kCacheInit)) {
693 state->SetFlags(kCacheInit, kCacheInit);
694 cache_size_ +=
sizeof(
State) + state->NumArcs() *
sizeof(
Arc);
697 if (cache_size_ > cache_limit_) GC(state,
false);
704 store_.AddArc(state, arc);
705 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
706 cache_size_ +=
sizeof(
Arc);
707 if (cache_size_ > cache_limit_) GC(state,
false);
714 store_.SetArcs(state);
715 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
716 cache_size_ += state->NumArcs() *
sizeof(
Arc);
717 if (cache_size_ > cache_limit_) GC(state,
false);
723 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
724 cache_size_ -= state->NumArcs() *
sizeof(
Arc);
726 store_.DeleteArcs(state);
731 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
732 cache_size_ -= n *
sizeof(
Arc);
734 store_.DeleteArcs(state, n);
747 bool Done()
const {
return store_.Done(); }
758 const auto *state = store_.GetState(Value());
760 cache_size_ -=
sizeof(
State) + state->NumArcs() *
sizeof(
Arc);
771 void GC(
const State *current,
bool free_recent,
float cache_fraction = 0.666);
780 static constexpr
size_t kMinCacheLimit = 8096;
783 bool cache_gc_request_;
789 template <
class CacheStore>
791 float cache_fraction) {
792 if (!cache_gc_)
return;
793 VLOG(2) <<
"GCCacheStore: Enter GC: object = " 794 <<
"(" <<
this <<
"), free recently cached = " << free_recent
795 <<
", cache size = " << cache_size_
796 <<
", cache frac = " << cache_fraction
797 <<
", cache limit = " << cache_limit_ <<
"\n";
798 size_t cache_target = cache_fraction * cache_limit_;
800 while (!store_.Done()) {
801 auto *state = store_.GetMutableState(store_.Value());
802 if (cache_size_ > cache_target && state->RefCount() == 0 &&
803 (free_recent || !(state->Flags() &
kCacheRecent)) && state != current) {
805 size_t size =
sizeof(
State) + state->NumArcs() *
sizeof(
Arc);
806 if (size < cache_size_) {
812 state->SetFlags(0, kCacheRecent);
816 if (!free_recent && cache_size_ > cache_target) {
817 GC(current,
true, cache_fraction);
818 }
else if (cache_target > 0) {
819 while (cache_size_ > cache_target) {
823 }
else if (cache_size_ > 0) {
824 FSTERROR() <<
"GCCacheStore:GC: Unable to free all cached states";
826 VLOG(2) <<
"GCCacheStore: Exit GC: object = " 827 <<
"(" <<
this <<
"), free recently cached = " << free_recent
828 <<
", cache size = " << cache_size_
829 <<
", cache frac = " << cache_fraction
830 <<
", cache limit = " << cache_limit_ <<
"\n";
838 :
public GCCacheStore<FirstCacheStore<VectorCacheStore<CacheState<Arc>>>> {
855 template <
class State,
859 using Arc =
typename State::Arc;
872 min_unexpanded_state_id_(0),
873 max_expanded_state_id_(-1),
876 cache_store_(new CacheStore(opts)),
877 new_cache_store_(true),
878 own_cache_store_(true) {}
884 min_unexpanded_state_id_(0),
885 max_expanded_state_id_(-1),
889 opts.store ? opts.store
891 new_cache_store_(!opts.store),
892 own_cache_store_(opts.store ? opts.own_store : true) {}
897 bool preserve_cache =
false)
902 min_unexpanded_state_id_(0),
903 max_expanded_state_id_(-1),
904 cache_gc_(impl.cache_gc_),
905 cache_limit_(impl.cache_limit_),
906 cache_store_(new CacheStore(
CacheOptions(cache_gc_, cache_limit_))),
907 new_cache_store_(impl.new_cache_store_ || !preserve_cache),
908 own_cache_store_(true) {
909 if (preserve_cache) {
910 *cache_store_ = *impl.cache_store_;
911 has_start_ = impl.has_start_;
912 cache_start_ = impl.cache_start_;
913 nknown_states_ = impl.nknown_states_;
914 expanded_states_ = impl.expanded_states_;
915 min_unexpanded_state_id_ = impl.min_unexpanded_state_id_;
916 max_expanded_state_id_ = impl.max_expanded_state_id_;
921 if (own_cache_store_)
delete cache_store_;
927 if (s >= nknown_states_) nknown_states_ = s + 1;
931 auto *state = cache_store_->GetMutableState(s);
932 state->SetFinal(std::move(weight));
933 static constexpr
auto flags = kCacheFinal |
kCacheRecent;
934 state->SetFlags(flags, flags);
941 auto *state = cache_store_->GetMutableState(s);
946 auto *state = cache_store_->GetMutableState(s);
947 state->PushArc(std::move(arc));
953 template <
class... T>
955 auto *state = cache_store_->GetMutableState(s);
956 state->EmplaceArc(std::forward<T>(ctor_args)...);
962 auto *state = cache_store_->GetMutableState(s);
963 cache_store_->SetArcs(state);
964 const auto narcs = state->NumArcs();
965 for (
size_t a = 0; a < narcs; ++a) {
966 const auto &arc = state->GetArc(a);
967 if (arc.nextstate >= nknown_states_) nknown_states_ = arc.nextstate + 1;
970 static constexpr
auto flags = kCacheArcs |
kCacheRecent;
971 state->SetFlags(flags, flags);
975 auto *state = cache_store_->GetMutableState(s);
976 state->ReserveArcs(n);
980 auto *state = cache_store_->GetMutableState(s);
981 cache_store_->DeleteArcs(state);
985 auto *state = cache_store_->GetMutableState(s);
986 cache_store_->DeleteArcs(state, n);
991 min_unexpanded_state_id_ = 0;
992 max_expanded_state_id_ = -1;
995 cache_store_->Clear();
1000 if (!has_start_ && Properties(
kError)) has_start_ =
true;
1006 const auto *state = cache_store_->GetState(s);
1008 state->SetFlags(kCacheRecent, kCacheRecent);
1017 const auto *state = cache_store_->GetState(s);
1019 state->SetFlags(kCacheRecent, kCacheRecent);
1029 const auto *state = cache_store_->GetState(s);
1030 return state->Final();
1034 const auto *state = cache_store_->GetState(s);
1035 return state->NumArcs();
1039 const auto *state = cache_store_->GetState(s);
1040 return state->NumInputEpsilons();
1044 const auto *state = cache_store_->GetState(s);
1045 return state->NumOutputEpsilons();
1050 const auto *state = cache_store_->GetState(s);
1051 data->
base =
nullptr;
1052 data->
narcs = state->NumArcs();
1053 data->
arcs = state->Arcs();
1054 data->
ref_count = state->MutableRefCount();
1055 state->IncrRefCount();
1063 if (s >= nknown_states_) nknown_states_ = s + 1;
1068 while (min_unexpanded_state_id_ <= max_expanded_state_id_ &&
1069 ExpandedState(min_unexpanded_state_id_)) {
1070 ++min_unexpanded_state_id_;
1072 return min_unexpanded_state_id_;
1079 if (s > max_expanded_state_id_) max_expanded_state_id_ = s;
1080 if (s < min_unexpanded_state_id_)
return;
1081 if (s == min_unexpanded_state_id_) ++min_unexpanded_state_id_;
1082 if (cache_gc_ || cache_limit_ == 0) {
1083 if (expanded_states_.size() <=
static_cast<size_t>(s))
1084 expanded_states_.resize(s + 1,
false);
1085 expanded_states_[s] =
true;
1090 if (cache_gc_ || cache_limit_ == 0) {
1091 return expanded_states_[s];
1092 }
else if (new_cache_store_) {
1093 return cache_store_->GetState(s) !=
nullptr;
1112 mutable bool has_start_;
1115 std::vector<bool> expanded_states_;
1116 mutable StateId min_unexpanded_state_id_;
1117 mutable StateId max_expanded_state_id_;
1119 size_t cache_limit_;
1120 CacheStore *cache_store_;
1121 bool new_cache_store_;
1122 bool own_cache_store_;
1128 template <
class Arc>
1153 template <
class FST>
1156 using Arc =
typename FST::Arc;
1165 : fst_(fst), impl_(impl), s_(0) {
1170 if (s_ < impl_->NumKnownStates())
return false;
1171 for (
StateId u = impl_->MinUnexpandedState(); u < impl_->NumKnownStates();
1172 u = impl_->MinUnexpandedState()) {
1176 for (; !aiter.
Done(); aiter.
Next()) {
1177 impl_->UpdateNumKnownStates(aiter.
Value().nextstate);
1179 impl_->SetExpandedState(u);
1180 if (s_ < impl_->NumKnownStates())
return false;
1199 template <
class FST>
1202 using Arc =
typename FST::Arc;
1207 using State =
typename Store::State;
1212 state_->IncrRefCount();
1217 bool Done()
const {
return i_ >= state_->NumArcs(); }
1219 const Arc &
Value()
const {
return state_->GetArc(i_); }
1234 const State *state_;
1243 template <
class FST>
1247 using Arc =
typename FST::Arc;
1257 state_ = impl_->GetCacheStore()->GetMutableState(s_);
1258 state_->IncrRefCount();
1263 bool Done() const final {
return i_ >= state_->NumArcs(); }
1265 const Arc &
Value() const final {
return state_->GetArc(i_); }
1273 void Seek(
size_t a)
final { i_ = a; }
1292 template <
class CacheStore>
1295 using State =
typename CacheStore::State;
1296 using Arc =
typename CacheStore::Arc;
1303 template <
class Expander>
1305 auto *state = store_.GetMutableState(s);
1306 if (state->Flags()) {
1307 state->SetFlags(kCacheRecent, kCacheRecent);
1309 StateBuilder builder(state);
1310 expander.Expand(s, &builder);
1311 state->SetFlags(kCacheFlags, kCacheFlags);
1312 store_.SetArcs(state);
1320 struct StateBuilder {
1323 explicit StateBuilder(
State *state_) : state(state_) {}
1325 void AddArc(
const Arc &arc) { state->PushArc(arc); }
1327 void AddArc(
Arc &&arc) { state->PushArc(std::move(arc)); }
1329 void SetFinal(
Weight weight = Weight::One()) {
1330 state->SetFinal(std::move(weight));
1337 #endif // FST_CACHE_H_ void GC(const State *current, bool free_recent, float cache_fraction=0.666)
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
VectorCacheStore(const VectorCacheStore< S > &store)
size_t CacheLimit() const
typename Arc::StateId StateId
VectorCacheStore & operator=(const VectorCacheStore &store)
State * GetMutableState(StateId s)
CacheImpl(const CacheOptions &opts)
constexpr uint8_t kCacheArcs
constexpr uint8_t kArcValueFlags
typename Arc::StateId StateId
uint8_t Flags() const final
CacheState(const ArcAllocator &alloc)
size_t NumInputEpsilons(StateId s) const
CacheOptions(bool gc=FST_FLAGS_fst_default_cache_gc, size_t gc_limit=FST_FLAGS_fst_default_cache_gc_limit)
HashCacheStore(const HashCacheStore< S > &store)
const Arc & Value() const
constexpr uint8_t kArcNoCache
void EmplaceArc(T &&...ctor_args)
bool HasFinal(StateId s) const
const Arc & GetArc(size_t n) const
GCCacheStore(const CacheOptions &opts)
bool ExpandedState(StateId s) const
void PushArc(const Arc &arc)
StateId CountStates() const
size_t NumOutputEpsilons() const
DECLARE_int64(fst_default_cache_gc_limit)
typename Arc::StateId StateId
typename SynchronizeFst< Arc >::Store Store
void SetFinal(StateId s, Weight weight=Weight::One())
typename Arc::StateId StateId
void SetFlags(uint8_t flags, uint8_t mask) const
void UpdateNumKnownStates(StateId s)
typename Store::State State
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
~CacheMutableArcIterator() override
void SetArcs(State *state)
constexpr uint8_t kCacheRecent
constexpr uint8_t kCacheFlags
constexpr uint64_t kError
FirstCacheStore< CacheStore > & operator=(const FirstCacheStore< CacheStore > &store)
CacheState(const CacheState< A > &state, const ArcAllocator &alloc)
typename std::allocator_traits< ArcAllocator >::template rebind_alloc< CacheState< A, M >> StateAllocator
typename CacheStore::State State
void AddArc(State *state, const Arc &arc)
StateId CountStates() const
typename SynchronizeFst< Arc >::Arc Arc
State * FindOrExpand(Expander &expander, StateId s)
std::unordered_map< StateId, State *, std::hash< StateId >, std::equal_to< StateId >, PoolAllocator< std::pair< const StateId, State * >>> StateMap
typename Arc::Weight Weight
typename Store::State State
State * GetMutableState(StateId s)
void SetArcs(State *state)
void DeleteArcs(State *state)
typename Arc::Weight Weight
const Arc & Value() const
static void Destroy(CacheState< Arc > *state, StateAllocator *alloc)
void SetFlags(uint8_t flags, uint8_t mask)
size_t NumArcs(StateId s) const
typename SynchronizeFst< Arc >::Store Store
CacheImpl(const CacheImpl< Arc > &impl, bool preserve_cache=false)
void SetFlags(uint8_t flags, uint8_t mask)
typename Arc::Weight Weight
CacheBaseImpl(const CacheImplOptions< CacheStore > &opts)
typename Arc::StateId StateId
CacheStore * GetCacheStore()
constexpr uint8_t kCacheFinal
VectorCacheStore(const CacheOptions &opts)
const State * GetState(StateId s) const
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
State * GetMutableState(StateId s)
std::list< StateId, PoolAllocator< StateId >> StateList
void DeleteArcs(StateId s, size_t n)
typename Arc::StateId StateId
void SetArcs(State *state)
CacheBaseImpl(const CacheBaseImpl< State, CacheStore > &impl, bool preserve_cache=false)
constexpr uint8_t kCacheInit
void SetArc(const Arc &arc, size_t n)
typename Arc::StateId StateId
void AddArc(const Arc &arc)
HashCacheStore & operator=(const HashCacheStore &store)
typename Arc::Weight Weight
typename FirstCacheStore< VectorCacheStore< CacheState< Arc > > >::State State
CacheBaseImpl(const CacheOptions &opts=CacheOptions())
const Arc & Value() const final
void ReserveArcs(StateId s, size_t n)
FirstCacheStore(const CacheOptions &opts)
StateId Value() const final
void DeleteArcs(State *state)
const State * GetState(StateId s) const
CacheArcIterator(Impl *impl, StateId s)
void Seek(size_t a) final
size_t NumInputEpsilons() const
void SetValue(const Arc &arc) final
void ReserveArcs(size_t n)
size_t Position() const final
void DeleteArcs(State *state)
CacheImplOptions(bool gc=FST_FLAGS_fst_default_cache_gc, size_t gc_limit=FST_FLAGS_fst_default_cache_gc_limit, CacheStore *store=nullptr)
void DeleteArcs(State *state, size_t n)
StateId MinUnexpandedState() const
void SetArcs(State *state)
void SetFlags(uint8_t, uint8_t) final
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const
void SetFinal(Weight weight=Weight::One())
State * GetMutableState(StateId s)
DefaultCacheStore(const CacheOptions &opts)
int * MutableRefCount() const
void EmplaceArc(StateId s, T &&...ctor_args)
std::unique_ptr< ArcIteratorBase< Arc > > base
bool HasArcs(StateId s) const
typename Arc::Label Label
void DeleteArcs(size_t n)
typename Arc::Weight Weight
StateId MaxExpandedState() const
void PushArc(StateId s, const Arc &arc)
HashCacheStore(const CacheOptions &opts)
void SetExpandedState(StateId s)
CacheImplOptions(const CacheOptions &opts)
typename SynchronizeFst< Arc >::Arc Arc
const State * GetState(StateId s) const
typename Arc::StateId StateId
CacheMutableArcIterator(Impl *impl, StateId s)
Weight Final(StateId s) const
StateId NumKnownStates() const
void DeleteArcs(State *state)
void DeleteArcs(State *state, size_t n)
typename FST::Store Store
ExpanderCacheStore(const CacheOptions &opts=CacheOptions())
FirstCacheStore(const FirstCacheStore< CacheStore > &store)
bool InBounds(StateId s) const
void DeleteArcs(StateId s)
void PushArc(StateId s, Arc &&arc)
StateId CountStates() const
const CacheStore * GetCacheStore() const
void AddArc(State *state, const Arc &arc)
size_t GetCacheLimit() const
void DeleteArcs(State *state, size_t n)
typename CacheState< A >::Arc Arc
constexpr uint8_t Flags() const
DECLARE_bool(fst_default_cache_gc)
~CacheBaseImpl() override
const State * GetState(StateId s) const
StateId CountStates() const
typename Arc::Weight Weight
void AddArc(State *state, const Arc &arc)
size_t NumOutputEpsilons(StateId s) const
typename Arc::StateId StateId
typename CacheStore::Arc Arc
void Destroy(ArcIterator< FST > *aiter, MemoryPool< ArcIterator< FST >> *pool)
typename Arc::StateId StateId
void DeleteArcs(State *state, size_t n)
void AddArc(State *state, const Arc &arc)
CacheStateIterator(const FST &fst, Impl *impl)