FST  openfst-1.7.1
OpenFst Library
replace-util.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 // Utility classes for the recursive replacement of FSTs (RTNs).
5 
6 #ifndef FST_REPLACE_UTIL_H_
7 #define FST_REPLACE_UTIL_H_
8 
9 #include <map>
10 #include <unordered_map>
11 #include <unordered_set>
12 #include <vector>
13 
14 #include <fst/log.h>
15 
16 #include <fst/connect.h>
17 #include <fst/mutable-fst.h>
18 #include <fst/topsort.h>
19 #include <fst/vector-fst.h>
20 
21 
22 namespace fst {
23 
24 // This specifies what labels to output on the call or return arc. Note that
25 // REPLACE_LABEL_INPUT and REPLACE_LABEL_OUTPUT will produce transducers when
26 // applied to acceptors.
28  // Epsilon labels on both input and output.
30  // Non-epsilon labels on input and epsilon on output.
32  // Epsilon on input and non-epsilon on output.
34  // Non-epsilon labels on both input and output.
36 };
37 
38 // By default ReplaceUtil will copy the input label of the replace arc.
39 // The call_label_type and return_label_type options specify how to manage
40 // the labels of the call arc and the return arc of the replace FST
42  int64 root; // Root rule for expansion.
43  ReplaceLabelType call_label_type; // How to label call arc.
44  ReplaceLabelType return_label_type; // How to label return arc.
45  int64 return_label; // Label to put on return arc.
46 
48  int64 root = kNoLabel,
49  ReplaceLabelType call_label_type = REPLACE_LABEL_INPUT,
50  ReplaceLabelType return_label_type = REPLACE_LABEL_NEITHER,
51  int64 return_label = 0)
52  : root(root),
53  call_label_type(call_label_type),
54  return_label_type(return_label_type),
55  return_label(return_label) {}
56 
57  // For backwards compatibility.
58  ReplaceUtilOptions(int64 root, bool epsilon_replace_arc)
59  : ReplaceUtilOptions(root,
60  epsilon_replace_arc ? REPLACE_LABEL_NEITHER
62 };
63 
64 // Every non-terminal on a path appears as the first label on that path in every
65 // FST associated with a given SCC of the replace dependency graph. This would
66 // be true if the SCC were formed from left-linear grammar rules.
67 constexpr uint8 kReplaceSCCLeftLinear = 0x01;
68 // Every non-terminal on a path appears as the final label on that path in every
69 // FST associated with a given SCC of the replace dependency graph. This would
70 // be true if the SCC were formed from right-linear grammar rules.
71 constexpr uint8 kReplaceSCCRightLinear = 0x02;
72 // The SCC in the replace dependency graph has more than one state or a
73 // self-loop.
74 constexpr uint8 kReplaceSCCNonTrivial = 0x04;
75 
76 // Defined in replace.h.
77 template <class Arc>
78 void Replace(
79  const std::vector<std::pair<typename Arc::Label, const Fst<Arc> *>> &,
81 
82 // Utility class for the recursive replacement of FSTs (RTNs). The user provides
83 // a set of label/FST pairs at construction. These are used by methods for
84 // testing cyclic dependencies and connectedness and doing RTN connection and
85 // specific FST replacement by label or for various optimization properties. The
86 // modified results can be obtained with the GetFstPairs() or
87 // GetMutableFstPairs() methods.
88 template <class Arc>
89 class ReplaceUtil {
90  public:
91  using Label = typename Arc::Label;
92  using StateId = typename Arc::StateId;
93  using Weight = typename Arc::Weight;
94 
95  using FstPair = std::pair<Label, const Fst<Arc> *>;
96  using MutableFstPair = std::pair<Label, MutableFst<Arc> *>;
97  using NonTerminalHash = std::unordered_map<Label, Label>;
98 
99  // Constructs from mutable FSTs; FST ownership is given to ReplaceUtil.
100  ReplaceUtil(const std::vector<MutableFstPair> &fst_pairs,
101  const ReplaceUtilOptions &opts);
102 
103  // Constructs from FSTs; FST ownership is retained by caller.
104  ReplaceUtil(const std::vector<FstPair> &fst_pairs,
105  const ReplaceUtilOptions &opts);
106 
107  // Constructs from ReplaceFst internals; FST ownership is retained by caller.
108  ReplaceUtil(const std::vector<std::unique_ptr<const Fst<Arc>>> &fst_array,
109  const NonTerminalHash &nonterminal_hash,
110  const ReplaceUtilOptions &opts);
111 
113  for (Label i = 0; i < fst_array_.size(); ++i) delete fst_array_[i];
114  }
115 
116  // True if the non-terminal dependencies are cyclic. Cyclic dependencies will
117  // result in an unexpandable FST.
118  bool CyclicDependencies() const {
119  GetDependencies(false);
120  return depprops_ & kCyclic;
121  }
122 
123  // Returns the strongly-connected component ID in the dependency graph of the
124  // replace FSTS.
125  StateId SCC(Label label) const {
126  GetDependencies(false);
127  const auto it = nonterminal_hash_.find(label);
128  if (it == nonterminal_hash_.end()) return kNoStateId;
129  return depscc_[it->second];
130  }
131 
132  // Returns properties for the strongly-connected component in the dependency
133  // graph of the replace FSTs. If the SCC is kReplaceSCCLeftLinear or
134  // kReplaceSCCRightLinear, that SCC can be represented as finite-state despite
135  // any cyclic dependencies, but not by the usual replacement operation (see
136  // fst/extensions/pdt/replace.h).
138  GetSCCProperties();
139  return depsccprops_[scc_id];
140  }
141 
142  // Returns true if no useless FSTs, states or transitions are present in the
143  // RTN.
144  bool Connected() const {
145  GetDependencies(false);
146  uint64 props = kAccessible | kCoAccessible;
147  for (Label i = 0; i < fst_array_.size(); ++i) {
148  if (!fst_array_[i]) continue;
149  if (fst_array_[i]->Properties(props, true) != props || !depaccess_[i]) {
150  return false;
151  }
152  }
153  return true;
154  }
155 
156  // Removes useless FSTs, states and transitions from the RTN.
157  void Connect();
158 
159  // Replaces FSTs specified by labels, unless there are cyclic dependencies.
160  void ReplaceLabels(const std::vector<Label> &labels);
161 
162  // Replaces FSTs that have at most nstates states, narcs arcs and nnonterm
163  // non-terminals (updating in reverse dependency order), unless there are
164  // cyclic dependencies.
165  void ReplaceBySize(size_t nstates, size_t narcs, size_t nnonterms);
166 
167  // Replaces singleton FSTS, unless there are cyclic dependencies.
168  void ReplaceTrivial() { ReplaceBySize(2, 1, 1); }
169 
170  // Replaces non-terminals that have at most ninstances instances (updating in
171  // dependency order), unless there are cyclic dependencies.
172  void ReplaceByInstances(size_t ninstances);
173 
174  // Replaces non-terminals that have only one instance, unless there are cyclic
175  // dependencies.
176  void ReplaceUnique() { ReplaceByInstances(1); }
177 
178  // Returns label/FST pairs, retaining FST ownership.
179  void GetFstPairs(std::vector<FstPair> *fst_pairs);
180 
181  // Returns label/mutable FST pairs, giving FST ownership over to the caller.
182  void GetMutableFstPairs(std::vector<MutableFstPair> *mutable_fst_pairs);
183 
184  private:
185  // FST statistics.
186  struct ReplaceStats {
187  StateId nstates; // Number of states.
188  StateId nfinal; // Number of final states.
189  size_t narcs; // Number of arcs.
190  Label nnonterms; // Number of non-terminals in FST.
191  size_t nref; // Number of non-terminal instances referring to this FST.
192  // Number of times that ith FST references this FST
193  std::map<Label, size_t> inref;
194  // Number of times that this FST references the ith FST
195  std::map<Label, size_t> outref;
196 
197  ReplaceStats() : nstates(0), nfinal(0), narcs(0), nnonterms(0), nref(0) {}
198  };
199 
200  // Checks that Mutable FSTs exists, creating them if necessary.
201  void CheckMutableFsts();
202 
203  // Computes the dependency graph for the RTN, computing dependency statistics
204  // if stats is true.
205  void GetDependencies(bool stats) const;
206 
207  void ClearDependencies() const {
208  depfst_.DeleteStates();
209  stats_.clear();
210  depprops_ = 0;
211  depsccprops_.clear();
212  have_stats_ = false;
213  }
214 
215  // Gets topological order of dependencies, returning false with cyclic input.
216  bool GetTopOrder(const Fst<Arc> &fst, std::vector<Label> *toporder) const;
217 
218  // Updates statistics to reflect the replacement of the jth FST.
219  void UpdateStats(Label j);
220 
221  // Computes the properties for the strongly-connected component in the
222  // dependency graph of the replace FSTs.
223  void GetSCCProperties() const;
224 
225  Label root_label_; // Root non-terminal.
226  Label root_fst_; // Root FST ID.
227  ReplaceLabelType call_label_type_; // See Replace().
228  ReplaceLabelType return_label_type_; // See Replace().
229  int64 return_label_; // See Replace().
230  std::vector<const Fst<Arc> *> fst_array_; // FST per ID.
231  std::vector<MutableFst<Arc> *> mutable_fst_array_; // Mutable FST per ID.
232  std::vector<Label> nonterminal_array_; // FST ID to non-terminal.
233  NonTerminalHash nonterminal_hash_; // Non-terminal to FST ID.
234  mutable VectorFst<Arc> depfst_; // FST ID dependencies.
235  mutable std::vector<StateId> depscc_; // FST SCC ID.
236  mutable std::vector<bool> depaccess_; // FST ID accessibility.
237  mutable uint64 depprops_; // Dependency FST props.
238  mutable bool have_stats_; // Have dependency statistics?
239  mutable std::vector<ReplaceStats> stats_; // Per-FST statistics.
240  mutable std::vector<uint8> depsccprops_; // SCC properties.
241  ReplaceUtil(const ReplaceUtil &) = delete;
242  ReplaceUtil &operator=(const ReplaceUtil &) = delete;
243 };
244 
245 template <class Arc>
246 ReplaceUtil<Arc>::ReplaceUtil(const std::vector<MutableFstPair> &fst_pairs,
247  const ReplaceUtilOptions &opts)
248  : root_label_(opts.root),
249  call_label_type_(opts.call_label_type),
250  return_label_type_(opts.return_label_type),
251  return_label_(opts.return_label),
252  depprops_(0),
253  have_stats_(false) {
254  fst_array_.push_back(nullptr);
255  mutable_fst_array_.push_back(nullptr);
256  nonterminal_array_.push_back(kNoLabel);
257  for (const auto &fst_pair : fst_pairs) {
258  const auto label = fst_pair.first;
259  auto *fst = fst_pair.second;
260  nonterminal_hash_[label] = fst_array_.size();
261  nonterminal_array_.push_back(label);
262  fst_array_.push_back(fst);
263  mutable_fst_array_.push_back(fst);
264  }
265  root_fst_ = nonterminal_hash_[root_label_];
266  if (!root_fst_) {
267  FSTERROR() << "ReplaceUtil: No root FST for label: " << root_label_;
268  }
269 }
270 
271 template <class Arc>
272 ReplaceUtil<Arc>::ReplaceUtil(const std::vector<FstPair> &fst_pairs,
273  const ReplaceUtilOptions &opts)
274  : root_label_(opts.root),
275  call_label_type_(opts.call_label_type),
276  return_label_type_(opts.return_label_type),
277  return_label_(opts.return_label),
278  depprops_(0),
279  have_stats_(false) {
280  fst_array_.push_back(nullptr);
281  nonterminal_array_.push_back(kNoLabel);
282  for (const auto &fst_pair : fst_pairs) {
283  const auto label = fst_pair.first;
284  const auto *fst = fst_pair.second;
285  nonterminal_hash_[label] = fst_array_.size();
286  nonterminal_array_.push_back(label);
287  fst_array_.push_back(fst->Copy());
288  }
289  root_fst_ = nonterminal_hash_[root_label_];
290  if (!root_fst_) {
291  FSTERROR() << "ReplaceUtil: No root FST for label: " << root_label_;
292  }
293 }
294 
295 template <class Arc>
297  const std::vector<std::unique_ptr<const Fst<Arc>>> &fst_array,
298  const NonTerminalHash &nonterminal_hash, const ReplaceUtilOptions &opts)
299  : root_fst_(opts.root),
300  call_label_type_(opts.call_label_type),
301  return_label_type_(opts.return_label_type),
302  return_label_(opts.return_label),
303  nonterminal_array_(fst_array.size()),
304  nonterminal_hash_(nonterminal_hash),
305  depprops_(0),
306  have_stats_(false) {
307  fst_array_.push_back(nullptr);
308  for (size_t i = 1; i < fst_array.size(); ++i) {
309  fst_array_.push_back(fst_array[i]->Copy());
310  }
311  for (auto it = nonterminal_hash.begin(); it != nonterminal_hash.end(); ++it) {
312  nonterminal_array_[it->second] = it->first;
313  }
314  root_label_ = nonterminal_array_[root_fst_];
315 }
316 
317 template <class Arc>
318 void ReplaceUtil<Arc>::GetDependencies(bool stats) const {
319  if (depfst_.NumStates() > 0) {
320  if (stats && !have_stats_) {
321  ClearDependencies();
322  } else {
323  return;
324  }
325  }
326  have_stats_ = stats;
327  if (have_stats_) stats_.reserve(fst_array_.size());
328  for (Label i = 0; i < fst_array_.size(); ++i) {
329  depfst_.AddState();
330  depfst_.SetFinal(i, Weight::One());
331  if (have_stats_) stats_.push_back(ReplaceStats());
332  }
333  depfst_.SetStart(root_fst_);
334  // An arc from each state (representing the FST) to the state representing the
335  // FST being replaced
336  for (Label i = 0; i < fst_array_.size(); ++i) {
337  const auto *ifst = fst_array_[i];
338  if (!ifst) continue;
339  for (StateIterator<Fst<Arc>> siter(*ifst); !siter.Done(); siter.Next()) {
340  const auto s = siter.Value();
341  if (have_stats_) {
342  ++stats_[i].nstates;
343  if (ifst->Final(s) != Weight::Zero()) ++stats_[i].nfinal;
344  }
345  for (ArcIterator<Fst<Arc>> aiter(*ifst, s); !aiter.Done();
346  aiter.Next()) {
347  if (have_stats_) ++stats_[i].narcs;
348  const auto &arc = aiter.Value();
349  auto it = nonterminal_hash_.find(arc.olabel);
350  if (it != nonterminal_hash_.end()) {
351  const auto j = it->second;
352  depfst_.EmplaceArc(i, arc.olabel, arc.olabel, Weight::One(), j);
353  if (have_stats_) {
354  ++stats_[i].nnonterms;
355  ++stats_[j].nref;
356  ++stats_[j].inref[i];
357  ++stats_[i].outref[j];
358  }
359  }
360  }
361  }
362  }
363  // Computes accessibility info.
364  SccVisitor<Arc> scc_visitor(&depscc_, &depaccess_, nullptr, &depprops_);
365  DfsVisit(depfst_, &scc_visitor);
366 }
367 
368 template <class Arc>
370  if (!have_stats_) {
371  FSTERROR() << "ReplaceUtil::UpdateStats: Stats not available";
372  return;
373  }
374  if (j == root_fst_) return; // Can't replace root.
375  for (auto in = stats_[j].inref.begin(); in != stats_[j].inref.end(); ++in) {
376  const auto i = in->first;
377  const auto ni = in->second;
378  stats_[i].nstates += stats_[j].nstates * ni;
379  stats_[i].narcs += (stats_[j].narcs + 1) * ni;
380  stats_[i].nnonterms += (stats_[j].nnonterms - 1) * ni;
381  stats_[i].outref.erase(j);
382  for (auto out = stats_[j].outref.begin(); out != stats_[j].outref.end();
383  ++out) {
384  const auto k = out->first;
385  const auto nk = out->second;
386  stats_[i].outref[k] += ni * nk;
387  }
388  }
389  for (auto out = stats_[j].outref.begin(); out != stats_[j].outref.end();
390  ++out) {
391  const auto k = out->first;
392  const auto nk = out->second;
393  stats_[k].nref -= nk;
394  stats_[k].inref.erase(j);
395  for (auto in = stats_[j].inref.begin(); in != stats_[j].inref.end(); ++in) {
396  const auto i = in->first;
397  const auto ni = in->second;
398  stats_[k].inref[i] += ni * nk;
399  stats_[k].nref += ni * nk;
400  }
401  }
402 }
403 
404 template <class Arc>
406  if (mutable_fst_array_.empty()) {
407  for (Label i = 0; i < fst_array_.size(); ++i) {
408  if (!fst_array_[i]) {
409  mutable_fst_array_.push_back(nullptr);
410  } else {
411  mutable_fst_array_.push_back(new VectorFst<Arc>(*fst_array_[i]));
412  delete fst_array_[i];
413  fst_array_[i] = mutable_fst_array_[i];
414  }
415  }
416  }
417 }
418 
419 template <class Arc>
421  CheckMutableFsts();
422  static constexpr auto props = kAccessible | kCoAccessible;
423  for (auto *mutable_fst : mutable_fst_array_) {
424  if (!mutable_fst) continue;
425  if (mutable_fst->Properties(props, false) != props) {
426  fst::Connect(mutable_fst);
427  }
428  }
429  GetDependencies(false);
430  for (Label i = 0; i < mutable_fst_array_.size(); ++i) {
431  auto *fst = mutable_fst_array_[i];
432  if (fst && !depaccess_[i]) {
433  delete fst;
434  fst_array_[i] = nullptr;
435  mutable_fst_array_[i] = nullptr;
436  }
437  }
438  ClearDependencies();
439 }
440 
441 template <class Arc>
443  std::vector<Label> *toporder) const {
444  // Finds topological order of dependencies.
445  std::vector<StateId> order;
446  bool acyclic = false;
447  TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
448  DfsVisit(fst, &top_order_visitor);
449  if (!acyclic) {
450  LOG(WARNING) << "ReplaceUtil::GetTopOrder: Cyclical label dependencies";
451  return false;
452  }
453  toporder->resize(order.size());
454  for (Label i = 0; i < order.size(); ++i) (*toporder)[order[i]] = i;
455  return true;
456 }
457 
458 template <class Arc>
459 void ReplaceUtil<Arc>::ReplaceLabels(const std::vector<Label> &labels) {
460  CheckMutableFsts();
461  std::unordered_set<Label> label_set;
462  for (const auto label : labels) {
463  // Can't replace root.
464  if (label != root_label_) label_set.insert(label);
465  }
466  // Finds FST dependencies restricted to the labels requested.
467  GetDependencies(false);
468  VectorFst<Arc> pfst(depfst_);
469  for (StateId i = 0; i < pfst.NumStates(); ++i) {
470  std::vector<Arc> arcs;
471  for (ArcIterator<VectorFst<Arc>> aiter(pfst, i); !aiter.Done();
472  aiter.Next()) {
473  const auto &arc = aiter.Value();
474  const auto label = nonterminal_array_[arc.nextstate];
475  if (label_set.count(label) > 0) arcs.push_back(arc);
476  }
477  pfst.DeleteArcs(i);
478  for (auto &arc : arcs) pfst.AddArc(i, std::move(arc));
479  }
480  std::vector<Label> toporder;
481  if (!GetTopOrder(pfst, &toporder)) {
482  ClearDependencies();
483  return;
484  }
485  // Visits FSTs in reverse topological order of dependencies and performs
486  // replacements.
487  for (Label o = toporder.size() - 1; o >= 0; --o) {
488  std::vector<FstPair> fst_pairs;
489  auto s = toporder[o];
490  for (ArcIterator<VectorFst<Arc>> aiter(pfst, s); !aiter.Done();
491  aiter.Next()) {
492  const auto &arc = aiter.Value();
493  const auto label = nonterminal_array_[arc.nextstate];
494  const auto *fst = fst_array_[arc.nextstate];
495  fst_pairs.push_back(std::make_pair(label, fst));
496  }
497  if (fst_pairs.empty()) continue;
498  const auto label = nonterminal_array_[s];
499  const auto *fst = fst_array_[s];
500  fst_pairs.push_back(std::make_pair(label, fst));
501  const ReplaceUtilOptions opts(label, call_label_type_, return_label_type_,
502  return_label_);
503  Replace(fst_pairs, mutable_fst_array_[s], opts);
504  }
505  ClearDependencies();
506 }
507 
508 template <class Arc>
509 void ReplaceUtil<Arc>::ReplaceBySize(size_t nstates, size_t narcs,
510  size_t nnonterms) {
511  std::vector<Label> labels;
512  GetDependencies(true);
513  std::vector<Label> toporder;
514  if (!GetTopOrder(depfst_, &toporder)) {
515  ClearDependencies();
516  return;
517  }
518  for (Label o = toporder.size() - 1; o >= 0; --o) {
519  const auto j = toporder[o];
520  if (stats_[j].nstates <= nstates && stats_[j].narcs <= narcs &&
521  stats_[j].nnonterms <= nnonterms) {
522  labels.push_back(nonterminal_array_[j]);
523  UpdateStats(j);
524  }
525  }
526  ReplaceLabels(labels);
527 }
528 
529 template <class Arc>
530 void ReplaceUtil<Arc>::ReplaceByInstances(size_t ninstances) {
531  std::vector<Label> labels;
532  GetDependencies(true);
533  std::vector<Label> toporder;
534  if (!GetTopOrder(depfst_, &toporder)) {
535  ClearDependencies();
536  return;
537  }
538  for (Label o = 0; o < toporder.size(); ++o) {
539  const auto j = toporder[o];
540  if (stats_[j].nref <= ninstances) {
541  labels.push_back(nonterminal_array_[j]);
542  UpdateStats(j);
543  }
544  }
545  ReplaceLabels(labels);
546 }
547 
548 template <class Arc>
549 void ReplaceUtil<Arc>::GetFstPairs(std::vector<FstPair> *fst_pairs) {
550  CheckMutableFsts();
551  fst_pairs->clear();
552  for (Label i = 0; i < fst_array_.size(); ++i) {
553  const auto label = nonterminal_array_[i];
554  const auto *fst = fst_array_[i];
555  if (!fst) continue;
556  fst_pairs->push_back(std::make_pair(label, fst));
557  }
558 }
559 
560 template <class Arc>
562  std::vector<MutableFstPair> *mutable_fst_pairs) {
563  CheckMutableFsts();
564  mutable_fst_pairs->clear();
565  for (Label i = 0; i < mutable_fst_array_.size(); ++i) {
566  const auto label = nonterminal_array_[i];
567  const auto *fst = mutable_fst_array_[i];
568  if (!fst) continue;
569  mutable_fst_pairs->push_back(std::make_pair(label, fst->Copy()));
570  }
571 }
572 
573 template <class Arc>
575  if (!depsccprops_.empty()) return;
576  GetDependencies(false);
577  if (depscc_.empty()) return;
578  for (StateId scc = 0; scc < depscc_.size(); ++scc) {
579  depsccprops_.push_back(kReplaceSCCLeftLinear | kReplaceSCCRightLinear);
580  }
581  if (!(depprops_ & kCyclic)) return; // No cyclic dependencies.
582  // Checks for self-loops in the dependency graph.
583  for (StateId scc = 0; scc < depscc_.size(); ++scc) {
584  for (ArcIterator<Fst<Arc> > aiter(depfst_, scc);
585  !aiter.Done(); aiter.Next()) {
586  const auto &arc = aiter.Value();
587  if (arc.nextstate == scc) { // SCC has a self loop.
588  depsccprops_[scc] |= kReplaceSCCNonTrivial;
589  }
590  }
591  }
592  std::vector<bool> depscc_visited(depscc_.size(), false);
593  for (Label i = 0; i < fst_array_.size(); ++i) {
594  const auto *fst = fst_array_[i];
595  if (!fst) continue;
596  const auto depscc = depscc_[i];
597  if (depscc_visited[depscc]) { // SCC has more than one state.
598  depsccprops_[depscc] |= kReplaceSCCNonTrivial;
599  }
600  depscc_visited[depscc] = true;
601  std::vector<StateId> fstscc; // SCCs of the current FST.
602  uint64 fstprops;
603  SccVisitor<Arc> scc_visitor(&fstscc, nullptr, nullptr, &fstprops);
604  DfsVisit(*fst, &scc_visitor);
605  for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
606  const auto s = siter.Value();
607  for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
608  const auto &arc = aiter.Value();
609  auto it = nonterminal_hash_.find(arc.olabel);
610  if (it == nonterminal_hash_.end() || depscc_[it->second] != depscc) {
611  continue; // Skips if a terminal or a non-terminal not in SCC.
612  }
613  const bool arc_in_cycle = fstscc[s] == fstscc[arc.nextstate];
614  // Left linear iff all non-terminals are initial.
615  if (s != fst->Start() || arc_in_cycle) {
616  depsccprops_[depscc] &= ~kReplaceSCCLeftLinear;
617  }
618  // Right linear iff all non-terminals are final.
619  if (fst->Final(arc.nextstate) == Weight::Zero() || arc_in_cycle) {
620  depsccprops_[depscc] &= ~kReplaceSCCRightLinear;
621  }
622  }
623  }
624  }
625 }
626 
627 } // namespace fst
628 
629 #endif // FST_REPLACE_UTIL_H_
void DeleteArcs(StateId s, size_t n) override
Definition: mutable-fst.h:330
void AddArc(StateId s, const Arc &arc) override
Definition: mutable-fst.h:303
void ReplaceByInstances(size_t ninstances)
Definition: replace-util.h:530
void SetStart(StateId s) override
Definition: mutable-fst.h:280
constexpr int kNoLabel
Definition: fst.h:179
uint64_t uint64
Definition: types.h:32
void ReplaceBySize(size_t nstates, size_t narcs, size_t nnonterms)
Definition: replace-util.h:509
uint8 SCCProperties(StateId scc_id)
Definition: replace-util.h:137
void SetFinal(StateId s, Weight weight) override
Definition: mutable-fst.h:285
void GetFstPairs(std::vector< FstPair > *fst_pairs)
Definition: replace-util.h:549
ReplaceLabelType
Definition: replace-util.h:27
typename Arc::Weight Weight
Definition: replace-util.h:93
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
void ReplaceLabels(const std::vector< Label > &labels)
Definition: replace-util.h:459
#define LOG(type)
Definition: log.h:48
virtual Weight Final(StateId) const =0
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
std::pair< Label, const Fst< Arc > * > FstPair
Definition: replace-util.h:95
void Replace(const std::vector< std::pair< typename Arc::Label, const Fst< Arc > * >> &ifst_array, MutableFst< Arc > *ofst, std::vector< std::pair< typename Arc::Label, typename Arc::Label >> *parens, const PdtReplaceOptions< Arc > &opts)
Definition: replace.h:785
constexpr uint8 kReplaceSCCNonTrivial
Definition: replace-util.h:74
constexpr int kNoStateId
Definition: fst.h:180
bool Connected() const
Definition: replace-util.h:144
int64_t int64
Definition: types.h:27
#define FSTERROR()
Definition: util.h:35
StateId AddState() override
Definition: mutable-fst.h:298
ReplaceUtilOptions(int64 root=kNoLabel, ReplaceLabelType call_label_type=REPLACE_LABEL_INPUT, ReplaceLabelType return_label_type=REPLACE_LABEL_NEITHER, int64 return_label=0)
Definition: replace-util.h:47
void GetMutableFstPairs(std::vector< MutableFstPair > *mutable_fst_pairs)
Definition: replace-util.h:561
uint8_t uint8
Definition: types.h:29
StateId NumStates() const override
Definition: expanded-fst.h:119
virtual StateId Start() const =0
std::pair< Label, MutableFst< Arc > * > MutableFstPair
Definition: replace-util.h:96
constexpr uint8 kReplaceSCCLeftLinear
Definition: replace-util.h:67
void EmplaceArc(StateId state, T &&...ctor_args)
Definition: vector-fst.h:533
StateId SCC(Label label) const
Definition: replace-util.h:125
constexpr uint8 kReplaceSCCRightLinear
Definition: replace-util.h:71
ReplaceUtil(const std::vector< MutableFstPair > &fst_pairs, const ReplaceUtilOptions &opts)
Definition: replace-util.h:246
ReplaceLabelType return_label_type
Definition: replace-util.h:44
constexpr uint64 kCoAccessible
Definition: properties.h:110
bool CyclicDependencies() const
Definition: replace-util.h:118
ReplaceUtilOptions(int64 root, bool epsilon_replace_arc)
Definition: replace-util.h:58
std::unordered_map< Label, Label > NonTerminalHash
Definition: replace-util.h:97
typename Arc::StateId StateId
Definition: replace-util.h:92
typename Arc::Label Label
Definition: replace-util.h:91
ReplaceLabelType call_label_type
Definition: replace-util.h:43
virtual Fst< Arc > * Copy(bool safe=false) const =0
constexpr uint64 kAccessible
Definition: properties.h:105
constexpr uint64 kCyclic
Definition: properties.h:90