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