test-properties.h revision 73018b4a1d088cdda0e7bd059fddf1f308a8195a
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 28DECLARE_bool(fst_verify_properties); 29 30namespace 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. 35inline 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 42inline 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). 71template<class Arc> 72uint64 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). 226template<class Arc> 227uint64 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