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