35 #include <unordered_map> 48 bool gc = FST_FLAGS_fst_default_cache_gc,
49 size_t gc_limit = FST_FLAGS_fst_default_cache_gc_limit)
50 : gc(gc), gc_limit(gc_limit) {}
55 template <
class CacheStore>
63 bool gc = FST_FLAGS_fst_default_cache_gc,
64 size_t gc_limit = FST_FLAGS_fst_default_cache_gc_limit,
65 CacheStore *store =
nullptr)
66 : gc(gc), gc_limit(gc_limit), store(store), own_store(true) {}
69 : gc(opts.gc), gc_limit(opts.gc_limit), store(nullptr), own_store(true) {}
81 template <
class A,
class M = PoolAllocator<A>>
85 using Label =
typename Arc::Label;
95 : final_weight_(
Weight::Zero()),
103 : final_weight_(state.
Final()),
106 arcs_(state.arcs_.begin(), state.arcs_.end(), alloc),
107 flags_(state.Flags()),
111 final_weight_ = Weight::Zero();
125 size_t NumArcs()
const {
return arcs_.size(); }
130 const Arc *
Arcs()
const {
return !arcs_.empty() ? &arcs_[0] :
nullptr; }
133 uint8_t
Flags()
const {
return flags_; }
139 final_weight_ = std::move(weight);
147 IncrementNumEpsilons(arc);
148 arcs_.push_back(arc);
152 IncrementNumEpsilons(arc);
153 arcs_.push_back(std::move(arc));
162 template <
class... T>
164 arcs_.emplace_back(std::forward<T>(ctor_args)...);
169 for (
const auto &arc : arcs_) {
170 IncrementNumEpsilons(arc);
176 if (arcs_[n].ilabel == 0) --niepsilons_;
177 if (arcs_[n].olabel == 0) --noepsilons_;
178 IncrementNumEpsilons(arc);
190 for (
size_t i = 0; i < n; ++i) {
191 if (arcs_.back().ilabel == 0) --niepsilons_;
192 if (arcs_.back().olabel == 0) --noepsilons_;
214 return alloc->allocate(1);
220 state->~CacheState<
Arc>();
221 alloc->deallocate(state, 1);
227 void IncrementNumEpsilons(
const Arc &arc) {
228 if (arc.ilabel == 0) ++niepsilons_;
229 if (arc.olabel == 0) ++noepsilons_;
235 std::vector<Arc, ArcAllocator> arcs_;
236 mutable uint8_t flags_;
237 mutable int ref_count_;
309 using StateList = std::list<StateId, PoolAllocator<StateId>>;
318 : cache_gc_(store.cache_gc_) {
326 if (
this != &store) {
334 return s < static_cast<StateId>(state_vec_.size());
339 return InBounds(s) ? state_vec_[s] :
nullptr;
344 State *state =
nullptr;
346 state = state_vec_[s];
348 state_vec_.resize(s + 1,
nullptr);
351 state =
new (&state_alloc_)
State(arc_alloc_);
352 state_vec_[s] = state;
353 if (cache_gc_) state_list_.push_back(s);
373 for (
State *s : state_vec_) {
381 return std::count_if(state_vec_.begin(), state_vec_.end(),
382 [](
const State *s) {
return s !=
nullptr; });
387 bool Done()
const {
return iter_ == state_list_.end(); }
393 void Reset() { iter_ = state_list_.begin(); }
398 state_vec_[*iter_] =
nullptr;
399 state_list_.erase(iter_++);
405 state_vec_.reserve(store.state_vec_.size());
406 for (
size_t s = 0; s < store.state_vec_.size(); ++s) {
407 State *state =
nullptr;
408 const auto *store_state = store.state_vec_[s];
410 state =
new (&state_alloc_)
State(*store_state, arc_alloc_);
411 if (cache_gc_) state_list_.push_back(s);
413 state_vec_.push_back(state);
418 std::vector<State *> state_vec_;
420 typename StateList::iterator iter_;
421 typename State::StateAllocator state_alloc_;
422 typename State::ArcAllocator arc_alloc_;
430 using Arc =
typename State::Arc;
434 std::unordered_map<StateId, State *, std::hash<StateId>,
435 std::equal_to<StateId>,
452 if (
this != &store) {
461 const auto it = state_map_.find(s);
462 return it != state_map_.end() ? it->second :
nullptr;
467 auto *&state = state_map_[s];
468 if (!state) state =
new (&state_alloc_)
State(arc_alloc_);
487 for (
auto &[unused_state_id, state_ptr] : state_map_) {
496 bool Done()
const {
return iter_ == state_map_.end(); }
502 void Reset() { iter_ = state_map_.begin(); }
507 state_map_.erase(iter_++);
513 for (
auto &[state_id, state_ptr] : store.state_map_) {
514 state_map_[state_id] =
new (&state_alloc_)
State(*state_ptr, arc_alloc_);
519 typename StateMap::iterator iter_;
520 typename State::StateAllocator state_alloc_;
521 typename State::ArcAllocator arc_alloc_;
535 template <
class CacheStore>
538 using State =
typename CacheStore::State;
539 using Arc =
typename State::Arc;
547 cache_first_state_(nullptr) {}
550 : store_(store.store_),
551 cache_gc_(store.cache_gc_),
552 cache_first_state_id_(store.cache_first_state_id_),
553 cache_first_state_(store.cache_first_state_id_ !=
kNoStateId 554 ? store_.GetMutableState(0)
559 if (
this != &store) {
560 store_ = store.store_;
561 cache_gc_ = store.cache_gc_;
562 cache_first_state_id_ = store.cache_first_state_id_;
563 cache_first_state_ = store.cache_first_state_id_ !=
kNoStateId 564 ? store_.GetMutableState(0)
573 return s == cache_first_state_id_ ? cache_first_state_
574 : store_.GetState(s + 1);
581 if (cache_first_state_id_ == s) {
582 return cache_first_state_;
586 cache_first_state_id_ = s;
587 cache_first_state_ = store_.GetMutableState(0);
588 cache_first_state_->SetFlags(kCacheInit, kCacheInit);
589 cache_first_state_->ReserveArcs(2 *
kAllocSize);
590 return cache_first_state_;
591 }
else if (cache_first_state_->RefCount() == 0) {
592 cache_first_state_id_ = s;
593 cache_first_state_->Reset();
594 cache_first_state_->SetFlags(kCacheInit, kCacheInit);
595 return cache_first_state_;
597 cache_first_state_->SetFlags(0, kCacheInit);
601 auto *state = store_.GetMutableState(s + 1);
606 void AddArc(State *state,
const Arc &arc) { store_.AddArc(state, arc); }
610 void SetArcs(State *state) { store_.SetArcs(state); }
616 void DeleteArcs(State *state,
size_t n) { store_.DeleteArcs(state, n); }
622 cache_first_state_ =
nullptr;
629 bool Done()
const {
return store_.Done(); }
633 const auto s = store_.Value();
634 return s ? s - 1 : cache_first_state_id_;
643 if (Value() == cache_first_state_id_) {
645 cache_first_state_ =
nullptr;
654 State *cache_first_state_;
663 template <
class CacheStore>
666 using State =
typename CacheStore::State;
667 using Arc =
typename State::Arc;
673 cache_gc_request_(opts.
gc),
684 auto *state = store_.GetMutableState(s);
685 if (cache_gc_request_ && !(state->Flags() &
kCacheInit)) {
686 state->SetFlags(kCacheInit, kCacheInit);
687 cache_size_ +=
sizeof(
State) + state->NumArcs() *
sizeof(
Arc);
690 if (cache_size_ > cache_limit_) GC(state,
false);
697 store_.AddArc(state, arc);
698 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
699 cache_size_ +=
sizeof(
Arc);
700 if (cache_size_ > cache_limit_) GC(state,
false);
707 store_.SetArcs(state);
708 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
709 cache_size_ += state->NumArcs() *
sizeof(
Arc);
710 if (cache_size_ > cache_limit_) GC(state,
false);
716 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
717 cache_size_ -= state->NumArcs() *
sizeof(
Arc);
719 store_.DeleteArcs(state);
724 if (cache_gc_ && (state->Flags() &
kCacheInit)) {
725 cache_size_ -= n *
sizeof(
Arc);
727 store_.DeleteArcs(state, n);
740 bool Done()
const {
return store_.Done(); }
751 const auto *state = store_.GetState(Value());
753 cache_size_ -=
sizeof(
State) + state->NumArcs() *
sizeof(
Arc);
764 void GC(
const State *current,
bool free_recent,
float cache_fraction = 0.666);
773 static constexpr
size_t kMinCacheLimit = 8096;
776 bool cache_gc_request_;
782 template <
class CacheStore>
784 float cache_fraction) {
785 if (!cache_gc_)
return;
786 VLOG(2) <<
"GCCacheStore: Enter GC: object = " 787 <<
"(" <<
this <<
"), free recently cached = " << free_recent
788 <<
", cache size = " << cache_size_
789 <<
", cache frac = " << cache_fraction
790 <<
", cache limit = " << cache_limit_ <<
"\n";
791 size_t cache_target = cache_fraction * cache_limit_;
793 while (!store_.Done()) {
794 auto *state = store_.GetMutableState(store_.Value());
795 if (cache_size_ > cache_target && state->RefCount() == 0 &&
796 (free_recent || !(state->Flags() &
kCacheRecent)) && state != current) {
798 size_t size =
sizeof(
State) + state->NumArcs() *
sizeof(
Arc);
799 if (size < cache_size_) {
805 state->SetFlags(0, kCacheRecent);
809 if (!free_recent && cache_size_ > cache_target) {
810 GC(current,
true, cache_fraction);
811 }
else if (cache_target > 0) {
812 while (cache_size_ > cache_target) {
816 }
else if (cache_size_ > 0) {
817 FSTERROR() <<
"GCCacheStore:GC: Unable to free all cached states";
819 VLOG(2) <<
"GCCacheStore: Exit GC: object = " 820 <<
"(" <<
this <<
"), free recently cached = " << free_recent
821 <<
", cache size = " << cache_size_
822 <<
", cache frac = " << cache_fraction
823 <<
", cache limit = " << cache_limit_ <<
"\n";
831 :
public GCCacheStore<FirstCacheStore<VectorCacheStore<CacheState<Arc>>>> {
848 template <
class State,
852 using Arc =
typename State::Arc;
865 min_unexpanded_state_id_(0),
866 max_expanded_state_id_(-1),
869 cache_store_(new CacheStore(opts)),
870 new_cache_store_(true),
871 own_cache_store_(true) {}
877 min_unexpanded_state_id_(0),
878 max_expanded_state_id_(-1),
882 opts.store ? opts.store
884 new_cache_store_(!opts.store),
885 own_cache_store_(opts.store ? opts.own_store : true) {}
890 bool preserve_cache =
false)
895 min_unexpanded_state_id_(0),
896 max_expanded_state_id_(-1),
897 cache_gc_(impl.cache_gc_),
898 cache_limit_(impl.cache_limit_),
899 cache_store_(new CacheStore(
CacheOptions(cache_gc_, cache_limit_))),
900 new_cache_store_(impl.new_cache_store_ || !preserve_cache),
901 own_cache_store_(true) {
902 if (preserve_cache) {
903 *cache_store_ = *impl.cache_store_;
904 has_start_ = impl.has_start_;
905 cache_start_ = impl.cache_start_;
906 nknown_states_ = impl.nknown_states_;
907 expanded_states_ = impl.expanded_states_;
908 min_unexpanded_state_id_ = impl.min_unexpanded_state_id_;
909 max_expanded_state_id_ = impl.max_expanded_state_id_;
914 if (own_cache_store_)
delete cache_store_;
920 if (s >= nknown_states_) nknown_states_ = s + 1;
924 auto *state = cache_store_->GetMutableState(s);
925 state->SetFinal(std::move(weight));
926 static constexpr
auto flags = kCacheFinal |
kCacheRecent;
927 state->SetFlags(flags, flags);
934 auto *state = cache_store_->GetMutableState(s);
939 auto *state = cache_store_->GetMutableState(s);
940 state->PushArc(std::move(arc));
946 template <
class... T>
948 auto *state = cache_store_->GetMutableState(s);
949 state->EmplaceArc(std::forward<T>(ctor_args)...);
955 auto *state = cache_store_->GetMutableState(s);
956 cache_store_->SetArcs(state);
957 const auto narcs = state->NumArcs();
958 for (
size_t a = 0; a < narcs; ++a) {
959 const auto &arc = state->GetArc(a);
960 if (arc.nextstate >= nknown_states_) nknown_states_ = arc.nextstate + 1;
963 static constexpr
auto flags = kCacheArcs |
kCacheRecent;
964 state->SetFlags(flags, flags);
968 auto *state = cache_store_->GetMutableState(s);
969 state->ReserveArcs(n);
973 auto *state = cache_store_->GetMutableState(s);
974 cache_store_->DeleteArcs(state);
978 auto *state = cache_store_->GetMutableState(s);
979 cache_store_->DeleteArcs(state, n);
984 min_unexpanded_state_id_ = 0;
985 max_expanded_state_id_ = -1;
988 cache_store_->Clear();
993 if (!has_start_ && Properties(
kError)) has_start_ =
true;
999 const auto *state = cache_store_->GetState(s);
1001 state->SetFlags(kCacheRecent, kCacheRecent);
1010 const auto *state = cache_store_->GetState(s);
1012 state->SetFlags(kCacheRecent, kCacheRecent);
1022 const auto *state = cache_store_->GetState(s);
1023 return state->Final();
1027 const auto *state = cache_store_->GetState(s);
1028 return state->NumArcs();
1032 const auto *state = cache_store_->GetState(s);
1033 return state->NumInputEpsilons();
1037 const auto *state = cache_store_->GetState(s);
1038 return state->NumOutputEpsilons();
1043 const auto *state = cache_store_->GetState(s);
1044 data->
base =
nullptr;
1045 data->
narcs = state->NumArcs();
1046 data->
arcs = state->Arcs();
1047 data->
ref_count = state->MutableRefCount();
1048 state->IncrRefCount();
1056 if (s >= nknown_states_) nknown_states_ = s + 1;
1061 while (min_unexpanded_state_id_ <= max_expanded_state_id_ &&
1062 ExpandedState(min_unexpanded_state_id_)) {
1063 ++min_unexpanded_state_id_;
1065 return min_unexpanded_state_id_;
1072 if (s > max_expanded_state_id_) max_expanded_state_id_ = s;
1073 if (s < min_unexpanded_state_id_)
return;
1074 if (s == min_unexpanded_state_id_) ++min_unexpanded_state_id_;
1075 if (cache_gc_ || cache_limit_ == 0) {
1076 if (expanded_states_.size() <=
static_cast<size_t>(s))
1077 expanded_states_.resize(s + 1,
false);
1078 expanded_states_[s] =
true;
1083 if (cache_gc_ || cache_limit_ == 0) {
1084 return expanded_states_[s];
1085 }
else if (new_cache_store_) {
1086 return cache_store_->GetState(s) !=
nullptr;
1105 mutable bool has_start_;
1108 std::vector<bool> expanded_states_;
1109 mutable StateId min_unexpanded_state_id_;
1110 mutable StateId max_expanded_state_id_;
1112 size_t cache_limit_;
1113 CacheStore *cache_store_;
1114 bool new_cache_store_;
1115 bool own_cache_store_;
1121 template <
class Arc>
1146 template <
class FST>
1149 using Arc =
typename FST::Arc;
1158 : fst_(fst), impl_(impl), s_(0) {
1163 if (s_ < impl_->NumKnownStates())
return false;
1164 for (
StateId u = impl_->MinUnexpandedState(); u < impl_->NumKnownStates();
1165 u = impl_->MinUnexpandedState()) {
1169 for (; !aiter.
Done(); aiter.
Next()) {
1170 impl_->UpdateNumKnownStates(aiter.
Value().nextstate);
1172 impl_->SetExpandedState(u);
1173 if (s_ < impl_->NumKnownStates())
return false;
1192 template <
class FST>
1195 using Arc =
typename FST::Arc;
1200 using State =
typename Store::State;
1205 state_->IncrRefCount();
1210 bool Done()
const {
return i_ >= state_->NumArcs(); }
1212 const Arc &
Value()
const {
return state_->GetArc(i_); }
1227 const State *state_;
1236 template <
class FST>
1240 using Arc =
typename FST::Arc;
1250 state_ = impl_->GetCacheStore()->GetMutableState(s_);
1251 state_->IncrRefCount();
1256 bool Done() const final {
return i_ >= state_->NumArcs(); }
1258 const Arc &
Value() const final {
return state_->GetArc(i_); }
1266 void Seek(
size_t a)
final { i_ = a; }
1285 template <
class CacheStore>
1288 using State =
typename CacheStore::State;
1289 using Arc =
typename CacheStore::Arc;
1296 template <
class Expander>
1298 auto *state = store_.GetMutableState(s);
1299 if (state->Flags()) {
1300 state->SetFlags(kCacheRecent, kCacheRecent);
1302 StateBuilder builder(state);
1303 expander.Expand(s, &builder);
1304 state->SetFlags(kCacheFlags, kCacheFlags);
1305 store_.SetArcs(state);
1313 struct StateBuilder {
1316 explicit StateBuilder(
State *state_) : state(state_) {}
1318 void AddArc(
const Arc &arc) { state->PushArc(arc); }
1320 void AddArc(
Arc &&arc) { state->PushArc(std::move(arc)); }
1322 void SetFinal(
Weight weight = Weight::One()) {
1323 state->SetFinal(std::move(weight));
1330 #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)