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