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>
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.
KnownProperties(uint64 props)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
CompatProperties(uint64 props1,uint64 props2)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>
ComputeProperties(const Fst<Arc> & fst,uint64 mask,uint64 * known,bool use_stored)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;
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).
234 template<class Arc>
TestProperties(const Fst<Arc> & fst,uint64 mask,uint64 * known)235 uint64 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