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