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