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