FST  openfst-1.7.2
OpenFst Library
visit.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Queue-dependent visitation of finite-state transducers. See also dfs-visit.h.
5 
6 #ifndef FST_VISIT_H_
7 #define FST_VISIT_H_
8 
9 
10 #include <fst/arcfilter.h>
11 #include <fst/mutable-fst.h>
12 
13 
14 namespace fst {
15 
16 // Visitor Interface: class determining actions taken during a visit. If any of
17 // the boolean member functions return false, the visit is aborted by first
18 // calling FinishState() on all unfinished (grey) states and then calling
19 // FinishVisit().
20 //
21 // Note this is more general than the visitor interface in dfs-visit.h but lacks
22 // some DFS-specific behavior.
23 //
24 // template <class Arc>
25 // class Visitor {
26 // public:
27 // using StateId = typename Arc::StateId;
28 //
29 // Visitor(T *return_data);
30 //
31 // // Invoked before visit.
32 // void InitVisit(const Fst<Arc> &fst);
33 //
34 // // Invoked when state discovered (2nd arg is visitation root).
35 // bool InitState(StateId s, StateId root);
36 //
37 // // Invoked when arc to white/undiscovered state examined.
38 // bool WhiteArc(StateId s, const Arc &arc);
39 //
40 // // Invoked when arc to grey/unfinished state examined.
41 // bool GreyArc(StateId s, const Arc &arc);
42 //
43 // // Invoked when arc to black/finished state examined.
44 // bool BlackArc(StateId s, const Arc &arc);
45 //
46 // // Invoked when state finished.
47 // void FinishState(StateId s);
48 //
49 // // Invoked after visit.
50 // void FinishVisit();
51 // };
52 
53 // Performs queue-dependent visitation. Visitor class argument determines
54 // actions and contains any return data. ArcFilter determines arcs that are
55 // considered. If 'access_only' is true, performs visitation only to states
56 // accessible from the initial state.
57 template <class FST, class Visitor, class Queue, class ArcFilter>
58 void Visit(const FST &fst, Visitor *visitor, Queue *queue, ArcFilter filter,
59  bool access_only = false) {
60  using Arc = typename FST::Arc;
61  using StateId = typename Arc::StateId;
62  visitor->InitVisit(fst);
63  const auto start = fst.Start();
64  if (start == kNoStateId) {
65  visitor->FinishVisit();
66  return;
67  }
68  // An FST's state's visit color.
69  static constexpr uint8 kWhiteState = 0x01; // Undiscovered.
70  static constexpr uint8 kGreyState = 0x02; // Discovered & unfinished.
71  static constexpr uint8 kBlackState = 0x04; // Finished.
72  // We destroy an iterator as soon as possible and mark it so.
73  static constexpr uint8 kArcIterDone = 0x08;
74  std::vector<uint8> state_status;
75  std::vector<ArcIterator<FST> *> arc_iterator;
76  MemoryPool<ArcIterator<FST>> aiter_pool;
77  StateId nstates = start + 1; // Number of known states in general case.
78  bool expanded = false;
79  if (fst.Properties(kExpanded, false)) { // Tests if expanded, then uses
80  nstates = CountStates(fst); // ExpandedFst::NumStates().
81  expanded = true;
82  }
83  state_status.resize(nstates, kWhiteState);
84  arc_iterator.resize(nstates);
85  StateIterator<Fst<Arc>> siter(fst);
86  // Continues visit while true.
87  bool visit = true;
88  // Iterates over trees in visit forest.
89  for (auto root = start; visit && root < nstates;) {
90  visit = visitor->InitState(root, root);
91  state_status[root] = kGreyState;
92  queue->Enqueue(root);
93  while (!queue->Empty()) {
94  auto state = queue->Head();
95  if (state >= state_status.size()) {
96  nstates = state + 1;
97  state_status.resize(nstates, kWhiteState);
98  arc_iterator.resize(nstates);
99  }
100  // Creates arc iterator if needed.
101  if (!arc_iterator[state] && !(state_status[state] & kArcIterDone) &&
102  visit) {
103  arc_iterator[state] = new (&aiter_pool) ArcIterator<FST>(fst, state);
104  }
105  // Deletes arc iterator if done.
106  auto *aiter = arc_iterator[state];
107  if ((aiter && aiter->Done()) || !visit) {
108  Destroy(aiter, &aiter_pool);
109  arc_iterator[state] = nullptr;
110  state_status[state] |= kArcIterDone;
111  }
112  // Dequeues state and marks black if done.
113  if (state_status[state] & kArcIterDone) {
114  queue->Dequeue();
115  visitor->FinishState(state);
116  state_status[state] = kBlackState;
117  continue;
118  }
119  const auto &arc = aiter->Value();
120  if (arc.nextstate >= state_status.size()) {
121  nstates = arc.nextstate + 1;
122  state_status.resize(nstates, kWhiteState);
123  arc_iterator.resize(nstates);
124  }
125  // Visits respective arc types.
126  if (filter(arc)) {
127  // Enqueues destination state and marks grey if white.
128  if (state_status[arc.nextstate] == kWhiteState) {
129  visit = visitor->WhiteArc(state, arc);
130  if (!visit) continue;
131  visit = visitor->InitState(arc.nextstate, root);
132  state_status[arc.nextstate] = kGreyState;
133  queue->Enqueue(arc.nextstate);
134  } else if (state_status[arc.nextstate] == kBlackState) {
135  visit = visitor->BlackArc(state, arc);
136  } else {
137  visit = visitor->GreyArc(state, arc);
138  }
139  }
140  aiter->Next();
141  // Destroys an iterator ASAP for efficiency.
142  if (aiter->Done()) {
143  Destroy(aiter, &aiter_pool);
144  arc_iterator[state] = nullptr;
145  state_status[state] |= kArcIterDone;
146  }
147  }
148  if (access_only) break;
149  // Finds next tree root.
150  for (root = (root == start) ? 0 : root + 1;
151  root < nstates && state_status[root] != kWhiteState; ++root) {
152  }
153  // Check for a state beyond the largest known state.
154  if (!expanded && root == nstates) {
155  for (; !siter.Done(); siter.Next()) {
156  if (siter.Value() == nstates) {
157  ++nstates;
158  state_status.push_back(kWhiteState);
159  arc_iterator.push_back(nullptr);
160  break;
161  }
162  }
163  }
164  }
165  visitor->FinishVisit();
166 }
167 
168 template <class Arc, class Visitor, class Queue>
169 inline void Visit(const Fst<Arc> &fst, Visitor *visitor, Queue *queue) {
170  Visit(fst, visitor, queue, AnyArcFilter<Arc>());
171 }
172 
173 // Copies input FST to mutable FST following queue order.
174 template <class A>
175 class CopyVisitor {
176  public:
177  using Arc = A;
178  using StateId = typename Arc::StateId;
179 
180  explicit CopyVisitor(MutableFst<Arc> *ofst) : ifst_(nullptr), ofst_(ofst) {}
181 
182  void InitVisit(const Fst<A> &ifst) {
183  ifst_ = &ifst;
184  ofst_->DeleteStates();
185  ofst_->SetStart(ifst_->Start());
186  }
187 
188  bool InitState(StateId state, StateId) {
189  while (ofst_->NumStates() <= state) ofst_->AddState();
190  return true;
191  }
192 
193  bool WhiteArc(StateId state, const Arc &arc) {
194  ofst_->AddArc(state, arc);
195  return true;
196  }
197 
198  bool GreyArc(StateId state, const Arc &arc) {
199  ofst_->AddArc(state, arc);
200  return true;
201  }
202 
203  bool BlackArc(StateId state, const Arc &arc) {
204  ofst_->AddArc(state, arc);
205  return true;
206  }
207 
208  void FinishState(StateId state) {
209  ofst_->SetFinal(state, ifst_->Final(state));
210  }
211 
212  void FinishVisit() {}
213 
214  private:
215  const Fst<Arc> *ifst_;
216  MutableFst<Arc> *ofst_;
217 };
218 
219 // Visits input FST up to a state limit following queue order.
220 template <class A>
222  public:
223  using Arc = A;
224  using StateId = typename Arc::StateId;
225 
226  explicit PartialVisitor(StateId maxvisit)
227  : fst_(nullptr), maxvisit_(maxvisit) {}
228 
229  void InitVisit(const Fst<A> &ifst) {
230  fst_ = &ifst;
231  ninit_ = 0;
232  nfinish_ = 0;
233  }
234 
235  bool InitState(StateId state, StateId root) {
236  ++ninit_;
237  return ninit_ <= maxvisit_;
238  }
239 
240  bool WhiteArc(StateId state, const Arc &arc) { return true; }
241 
242  bool GreyArc(StateId state, const Arc &arc) { return true; }
243 
244  bool BlackArc(StateId state, const Arc &arc) { return true; }
245 
246  void FinishState(StateId state) {
247  fst_->Final(state); // Visits super-final arc.
248  ++nfinish_;
249  }
250 
251  void FinishVisit() {}
252 
253  StateId NumInitialized() { return ninit_; }
254 
255  StateId NumFinished() { return nfinish_; }
256 
257  private:
258  const Fst<Arc> *fst_;
259  StateId maxvisit_;
260  StateId ninit_;
261  StateId nfinish_;
262 };
263 
264 // Copies input FST to mutable FST up to a state limit following queue order.
265 template <class A>
266 class PartialCopyVisitor : public CopyVisitor<A> {
267  public:
268  using Arc = A;
269  using StateId = typename Arc::StateId;
270 
272 
274  bool copy_grey = true, bool copy_black = true)
275  : CopyVisitor<A>(ofst), maxvisit_(maxvisit),
276  copy_grey_(copy_grey), copy_black_(copy_black) {}
277 
278  void InitVisit(const Fst<A> &ifst) {
280  ninit_ = 0;
281  nfinish_ = 0;
282  }
283 
284  bool InitState(StateId state, StateId root) {
285  CopyVisitor<A>::InitState(state, root);
286  ++ninit_;
287  return ninit_ <= maxvisit_;
288  }
289 
290  bool GreyArc(StateId state, const Arc &arc) {
291  if (copy_grey_) return CopyVisitor<A>::GreyArc(state, arc);
292  return true;
293  }
294 
295  bool BlackArc(StateId state, const Arc &arc) {
296  if (copy_black_) return CopyVisitor<A>::BlackArc(state, arc);
297  return true;
298  }
299 
300  void FinishState(StateId state) {
302  ++nfinish_;
303  }
304 
305  void FinishVisit() {}
306 
307  StateId NumInitialized() { return ninit_; }
308 
309  StateId NumFinished() { return nfinish_; }
310 
311  private:
312  StateId maxvisit_;
313  StateId ninit_;
314  StateId nfinish_;
315  const bool copy_grey_;
316  const bool copy_black_;
317 };
318 
319 } // namespace fst
320 
321 #endif // FST_VISIT_H_
bool WhiteArc(StateId state, const Arc &arc)
Definition: visit.h:240
bool BlackArc(StateId state, const Arc &arc)
Definition: visit.h:295
void FinishVisit()
Definition: visit.h:251
bool GreyArc(StateId state, const Arc &arc)
Definition: visit.h:242
bool WhiteArc(StateId state, const Arc &arc)
Definition: visit.h:193
void FinishState(StateId state)
Definition: visit.h:300
CopyVisitor(MutableFst< Arc > *ofst)
Definition: visit.h:180
virtual void AddArc(StateId, const Arc &arc)=0
void Visit(const FST &fst, Visitor *visitor, Queue *queue, ArcFilter filter, bool access_only=false)
Definition: visit.h:58
typename Arc::StateId StateId
Definition: visit.h:178
bool BlackArc(StateId state, const Arc &arc)
Definition: visit.h:244
void InitVisit(const Fst< A > &ifst)
Definition: visit.h:182
void FinishState(StateId state)
Definition: visit.h:208
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
bool GreyArc(StateId state, const Arc &arc)
Definition: visit.h:198
bool BlackArc(StateId state, const Arc &arc)
Definition: visit.h:203
constexpr int kNoStateId
Definition: fst.h:180
constexpr uint64 kExpanded
Definition: properties.h:27
typename Arc::StateId StateId
Definition: visit.h:224
virtual void SetFinal(StateId, Weight)=0
uint8_t uint8
Definition: types.h:29
PartialCopyVisitor(MutableFst< Arc > *ofst, StateId maxvisit, bool copy_grey=true, bool copy_black=true)
Definition: visit.h:273
void FinishVisit()
Definition: visit.h:212
PartialVisitor(StateId maxvisit)
Definition: visit.h:226
virtual StateId Start() const =0
StateId NumInitialized()
Definition: visit.h:253
bool InitState(StateId state, StateId root)
Definition: visit.h:284
StateId Value() const
Definition: fst.h:387
void InitVisit(const Fst< A > &ifst)
Definition: visit.h:278
bool GreyArc(StateId state, const Arc &arc)
Definition: visit.h:290
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:154
void Next()
Definition: fst.h:389
void FinishState(StateId state)
Definition: visit.h:246
bool Done() const
Definition: fst.h:383
virtual StateId AddState()=0
virtual void DeleteStates(const std::vector< StateId > &)=0
StateId NumFinished()
Definition: visit.h:309
virtual StateId NumStates() const =0
StateId NumInitialized()
Definition: visit.h:307
bool InitState(StateId state, StateId root)
Definition: visit.h:235
bool InitState(StateId state, StateId)
Definition: visit.h:188
void Destroy(ArcIterator< FST > *aiter, MemoryPool< ArcIterator< FST >> *pool)
Definition: fst.h:564
StateId NumFinished()
Definition: visit.h:255
void InitVisit(const Fst< A > &ifst)
Definition: visit.h:229