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. 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 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> 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> 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