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