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