FST  openfst-1.8.2.post1
OpenFst Library
test-properties.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 // Functions to manipulate and test property bits.
19 
20 #ifndef FST_TEST_PROPERTIES_H_
21 #define FST_TEST_PROPERTIES_H_
22 
23 #include <cstdint>
24 
25 #include <fst/flags.h>
26 
27 #include <fst/connect.h>
28 #include <fst/dfs-visit.h>
29 
30 #include <unordered_set>
31 
32 DECLARE_bool(fst_verify_properties);
33 
34 namespace fst {
35 namespace internal {
36 
37 // Computes FST property values defined in properties.h. The value of each
38 // property indicated in the mask will be determined and returned (these will
39 // never be unknown here). In the course of determining the properties
40 // specifically requested in the mask, certain other properties may be
41 // determined (those with little additional expense) and their values will be
42 // returned as well. The complete set of known properties (whether true or
43 // false) determined by this operation will be assigned to the the value pointed
44 // to by KNOWN. 'mask & required_mask' is used to determine whether the stored
45 // properties can be used. This routine is seldom called directly; instead it is
46 // used to implement fst.Properties(mask, /*test=*/true).
47 template <class Arc>
48 uint64_t ComputeProperties(const Fst<Arc> &fst, uint64_t mask,
49  uint64_t *known) {
50  using Label = typename Arc::Label;
51  using StateId = typename Arc::StateId;
52  using Weight = typename Arc::Weight;
53  const auto fst_props = fst.Properties(kFstProperties, false); // FST-stored.
54  // Computes (trinary) properties explicitly.
55  // Initialize with binary properties (already known).
56  uint64_t comp_props = fst_props & kBinaryProperties;
57  // Computes these trinary properties with a DFS. We compute only those that
58  // need a DFS here, since we otherwise would like to avoid a DFS since its
59  // stack could grow large.
60  constexpr uint64_t kDfsProps =
63  std::vector<StateId> scc;
64  if (mask & (kDfsProps | kWeightedCycles | kUnweightedCycles)) {
65  SccVisitor<Arc> scc_visitor(&scc, nullptr, nullptr, &comp_props);
66  DfsVisit(fst, &scc_visitor);
67  }
68  // Computes any remaining trinary properties via a state and arcs iterations
69  if (mask & ~(kBinaryProperties | kDfsProps)) {
70  comp_props |= kAcceptor | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
72  kString;
73  if (mask & (kIDeterministic | kNonIDeterministic)) {
74  comp_props |= kIDeterministic;
75  }
76  if (mask & (kODeterministic | kNonODeterministic)) {
77  comp_props |= kODeterministic;
78  }
79  if (mask & (kDfsProps | kWeightedCycles | kUnweightedCycles)) {
80  comp_props |= kUnweightedCycles;
81  }
82  std::unique_ptr<std::unordered_set<Label>> ilabels;
83  std::unique_ptr<std::unordered_set<Label>> olabels;
84  StateId nfinal = 0;
85  for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
86  StateId s = siter.Value();
87  Arc prev_arc;
88  // Creates these only if we need to.
89  if (mask & (kIDeterministic | kNonIDeterministic)) {
90  ilabels = std::make_unique<std::unordered_set<Label>>();
91  }
92  if (mask & (kODeterministic | kNonODeterministic)) {
93  olabels = std::make_unique<std::unordered_set<Label>>();
94  }
95  bool first_arc = true;
96  for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
97  const auto &arc = aiter.Value();
98  if (ilabels && ilabels->find(arc.ilabel) != ilabels->end()) {
99  comp_props |= kNonIDeterministic;
100  comp_props &= ~kIDeterministic;
101  }
102  if (olabels && olabels->find(arc.olabel) != olabels->end()) {
103  comp_props |= kNonODeterministic;
104  comp_props &= ~kODeterministic;
105  }
106  if (arc.ilabel != arc.olabel) {
107  comp_props |= kNotAcceptor;
108  comp_props &= ~kAcceptor;
109  }
110  if (arc.ilabel == 0 && arc.olabel == 0) {
111  comp_props |= kEpsilons;
112  comp_props &= ~kNoEpsilons;
113  }
114  if (arc.ilabel == 0) {
115  comp_props |= kIEpsilons;
116  comp_props &= ~kNoIEpsilons;
117  }
118  if (arc.olabel == 0) {
119  comp_props |= kOEpsilons;
120  comp_props &= ~kNoOEpsilons;
121  }
122  if (!first_arc) {
123  if (arc.ilabel < prev_arc.ilabel) {
124  comp_props |= kNotILabelSorted;
125  comp_props &= ~kILabelSorted;
126  }
127  if (arc.olabel < prev_arc.olabel) {
128  comp_props |= kNotOLabelSorted;
129  comp_props &= ~kOLabelSorted;
130  }
131  }
132  if (arc.weight != Weight::One() && arc.weight != Weight::Zero()) {
133  comp_props |= kWeighted;
134  comp_props &= ~kUnweighted;
135  if ((comp_props & kUnweightedCycles) &&
136  scc[s] == scc[arc.nextstate]) {
137  comp_props |= kWeightedCycles;
138  comp_props &= ~kUnweightedCycles;
139  }
140  }
141  if (arc.nextstate <= s) {
142  comp_props |= kNotTopSorted;
143  comp_props &= ~kTopSorted;
144  }
145  if (arc.nextstate != s + 1) {
146  comp_props |= kNotString;
147  comp_props &= ~kString;
148  }
149  prev_arc = arc;
150  first_arc = false;
151  if (ilabels) ilabels->insert(arc.ilabel);
152  if (olabels) olabels->insert(arc.olabel);
153  }
154 
155  if (nfinal > 0) { // Final state not last.
156  comp_props |= kNotString;
157  comp_props &= ~kString;
158  }
159  const auto final_weight = fst.Final(s);
160  if (final_weight != Weight::Zero()) { // Final state.
161  if (final_weight != Weight::One()) {
162  comp_props |= kWeighted;
163  comp_props &= ~kUnweighted;
164  }
165  ++nfinal;
166  } else { // Non-final state.
167  if (fst.NumArcs(s) != 1) {
168  comp_props |= kNotString;
169  comp_props &= ~kString;
170  }
171  }
172  }
173  if (fst.Start() != kNoStateId && fst.Start() != 0) {
174  comp_props |= kNotString;
175  comp_props &= ~kString;
176  }
177  }
178  if (known) *known = KnownProperties(comp_props);
179  return comp_props;
180 }
181 
182 // Similar to ComputeProperties, but uses the properties already stored
183 // in the FST when possible.
184 template <class Arc>
185 uint64_t ComputeOrUseStoredProperties(const Fst<Arc> &fst, uint64_t mask,
186  uint64_t *known) {
187  // Check stored FST properties first.
188  const auto fst_props = fst.Properties(kFstProperties, /*test=*/false);
189  const auto known_props = KnownProperties(fst_props);
190  // If FST contains required info, return it.
191  if ((known_props & mask) == mask) {
192  if (known) *known = known_props;
193  return fst_props;
194  }
195 
196  return ComputeProperties(fst, mask, known);
197 }
198 
199 // This is a wrapper around ComputeProperties that will cause a fatal error if
200 // the stored properties and the computed properties are incompatible when
201 // FST_FLAGS_fst_verify_properties is true. This routine is seldom called directly;
202 // instead it is used to implement fst.Properties(mask, /*test=*/true).
203 template <class Arc>
204 uint64_t TestProperties(const Fst<Arc> &fst, uint64_t mask, uint64_t *known) {
205  if (FST_FLAGS_fst_verify_properties) {
206  const auto stored_props = fst.Properties(kFstProperties, false);
207  const auto computed_props = ComputeProperties(fst, mask, known);
208  if (!CompatProperties(stored_props, computed_props)) {
209  FSTERROR() << "TestProperties: stored FST properties incorrect"
210  << " (stored: props1, computed: props2)";
211  }
212  return computed_props;
213  } else {
214  return ComputeOrUseStoredProperties(fst, mask, known);
215  }
216 }
217 
218 // If all the properties of 'fst' corresponding to 'check_mask' are known,
219 // returns the stored properties. Otherwise, the properties corresponding to
220 // both 'check_mask' and 'test_mask' are computed. This is used to check for
221 // newly-added properties that might not be set in old binary files.
222 template <class Arc>
223 uint64_t CheckProperties(const Fst<Arc> &fst, uint64_t check_mask,
224  uint64_t test_mask) {
225  auto props = fst.Properties(kFstProperties, false);
226  if (FST_FLAGS_fst_verify_properties) {
227  props = TestProperties(fst, check_mask | test_mask, /*known=*/nullptr);
228  } else if ((KnownProperties(props) & check_mask) != check_mask) {
229  props = ComputeProperties(fst, check_mask | test_mask, /*known=*/nullptr);
230  }
231  return props & (check_mask | test_mask);
232 }
233 
234 } // namespace internal
235 } // namespace fst
236 
237 #endif // FST_TEST_PROPERTIES_H_
constexpr uint64_t kCyclic
Definition: properties.h:108
constexpr uint64_t kNotString
Definition: properties.h:138
uint64_t TestProperties(const Fst< Arc > &fst, uint64_t mask, uint64_t *known)
uint64_t ComputeProperties(const Fst< Arc > &fst, uint64_t mask, uint64_t *known)
constexpr uint64_t kWeightedCycles
Definition: properties.h:141
virtual uint64_t Properties(uint64_t mask, bool test) const =0
constexpr uint64_t kOEpsilons
Definition: properties.h:88
constexpr uint64_t kInitialCyclic
Definition: properties.h:113
virtual size_t NumArcs(StateId) const =0
constexpr uint64_t kCoAccessible
Definition: properties.h:128
bool CompatProperties(uint64_t props1, uint64_t props2)
Definition: properties.h:506
constexpr uint64_t kBinaryProperties
Definition: properties.h:309
constexpr uint64_t kNotAccessible
Definition: properties.h:125
constexpr uint64_t kNotTopSorted
Definition: properties.h:120
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:109
constexpr uint64_t kInitialAcyclic
Definition: properties.h:115
virtual Weight Final(StateId) const =0
constexpr uint64_t kUnweightedCycles
Definition: properties.h:144
constexpr uint64_t kEpsilons
Definition: properties.h:78
constexpr uint64_t kNotOLabelSorted
Definition: properties.h:100
constexpr uint64_t kTopSorted
Definition: properties.h:118
DECLARE_bool(fst_verify_properties)
constexpr uint64_t kODeterministic
Definition: properties.h:73
constexpr int kNoStateId
Definition: fst.h:202
#define FSTERROR()
Definition: util.h:53
constexpr uint64_t kNonIDeterministic
Definition: properties.h:70
constexpr uint64_t kNotILabelSorted
Definition: properties.h:95
constexpr uint64_t kNoOEpsilons
Definition: properties.h:90
constexpr uint64_t kOLabelSorted
Definition: properties.h:98
constexpr uint64_t kNotAcceptor
Definition: properties.h:65
constexpr uint64_t kAcyclic
Definition: properties.h:110
constexpr uint64_t kNoEpsilons
Definition: properties.h:80
uint64_t CheckProperties(const Fst< Arc > &fst, uint64_t check_mask, uint64_t test_mask)
uint64_t KnownProperties(uint64_t props)
Definition: properties.h:499
constexpr uint64_t kAccessible
Definition: properties.h:123
virtual StateId Start() const =0
constexpr uint64_t kIDeterministic
Definition: properties.h:68
constexpr uint64_t kIEpsilons
Definition: properties.h:83
uint64_t ComputeOrUseStoredProperties(const Fst< Arc > &fst, uint64_t mask, uint64_t *known)
constexpr uint64_t kILabelSorted
Definition: properties.h:93
constexpr uint64_t kFstProperties
Definition: properties.h:325
constexpr uint64_t kUnweighted
Definition: properties.h:105
constexpr uint64_t kNonODeterministic
Definition: properties.h:75
constexpr uint64_t kString
Definition: properties.h:135
constexpr uint64_t kNotCoAccessible
Definition: properties.h:130
constexpr uint64_t kWeighted
Definition: properties.h:103
constexpr uint64_t kNoIEpsilons
Definition: properties.h:85
constexpr uint64_t kAcceptor
Definition: properties.h:63