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