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@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 <tr1/unordered_set> 25using std::tr1::unordered_set; 26using std::tr1::unordered_multiset; 27 28#include <fst/dfs-visit.h> 29#include <fst/connect.h> 30 31 32DECLARE_bool(fst_verify_properties); 33 34namespace 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. 39inline 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 46inline 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). 75template<class Arc> 76uint64 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; 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 bool first_arc = true; 136 for (ArcIterator< Fst<Arc> > aiter(fst, s); 137 !aiter.Done(); 138 aiter.Next()) { 139 const Arc &arc =aiter.Value(); 140 141 if (ilabels && ilabels->find(arc.ilabel) != ilabels->end()) { 142 comp_props |= kNonIDeterministic; 143 comp_props &= ~kIDeterministic; 144 } 145 if (olabels && olabels->find(arc.olabel) != olabels->end()) { 146 comp_props |= kNonODeterministic; 147 comp_props &= ~kODeterministic; 148 } 149 if (arc.ilabel != arc.olabel) { 150 comp_props |= kNotAcceptor; 151 comp_props &= ~kAcceptor; 152 } 153 if (arc.ilabel == 0 && arc.olabel == 0) { 154 comp_props |= kEpsilons; 155 comp_props &= ~kNoEpsilons; 156 } 157 if (arc.ilabel == 0) { 158 comp_props |= kIEpsilons; 159 comp_props &= ~kNoIEpsilons; 160 } 161 if (arc.olabel == 0) { 162 comp_props |= kOEpsilons; 163 comp_props &= ~kNoOEpsilons; 164 } 165 if (!first_arc) { 166 if (arc.ilabel < prev_arc.ilabel) { 167 comp_props |= kNotILabelSorted; 168 comp_props &= ~kILabelSorted; 169 } 170 if (arc.olabel < prev_arc.olabel) { 171 comp_props |= kNotOLabelSorted; 172 comp_props &= ~kOLabelSorted; 173 } 174 } 175 if (arc.weight != Weight::One() && arc.weight != Weight::Zero()) { 176 comp_props |= kWeighted; 177 comp_props &= ~kUnweighted; 178 } 179 if (arc.nextstate <= s) { 180 comp_props |= kNotTopSorted; 181 comp_props &= ~kTopSorted; 182 } 183 if (arc.nextstate != s + 1) { 184 comp_props |= kNotString; 185 comp_props &= ~kString; 186 } 187 prev_arc = arc; 188 first_arc = false; 189 if (ilabels) 190 ilabels->insert(arc.ilabel); 191 if (olabels) 192 olabels->insert(arc.olabel); 193 } 194 195 if (nfinal > 0) { // final state not last 196 comp_props |= kNotString; 197 comp_props &= ~kString; 198 } 199 200 Weight final = fst.Final(s); 201 202 if (final != Weight::Zero()) { // final state 203 if (final != Weight::One()) { 204 comp_props |= kWeighted; 205 comp_props &= ~kUnweighted; 206 } 207 ++nfinal; 208 } else { // non-final state 209 if (fst.NumArcs(s) != 1) { 210 comp_props |= kNotString; 211 comp_props &= ~kString; 212 } 213 } 214 215 delete ilabels; 216 delete olabels; 217 } 218 219 if (fst.Start() != kNoStateId && fst.Start() != 0) { 220 comp_props |= kNotString; 221 comp_props &= ~kString; 222 } 223 } 224 225 *known = KnownProperties(comp_props); 226 return comp_props; 227} 228 229// This is a wrapper around ComputeProperties that will cause a fatal 230// error if the stored properties and the computed properties are 231// incompatible when 'FLAGS_fst_verify_properties' is true. This 232// routine is seldom called directly; instead it is used to implement 233// fst.Properties(mask, true). 234template<class Arc> 235uint64 TestProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known) { 236 if (FLAGS_fst_verify_properties) { 237 uint64 stored_props = fst.Properties(kFstProperties, false); 238 uint64 computed_props = ComputeProperties(fst, mask, known, false); 239 if (!CompatProperties(stored_props, computed_props)) 240 LOG(FATAL) << "TestProperties: stored Fst properties incorrect" 241 << " (stored: props1, computed: props2)"; 242 return computed_props; 243 } else { 244 return ComputeProperties(fst, mask, known, true); 245 } 246} 247 248} // namespace fst 249 250#endif // FST_LIB_TEST_PROPERTIES_H__ 251