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