| // test-properties.h |
| |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // Copyright 2005-2010 Google, Inc. |
| // Author: riley@google.com (Michael Riley) |
| // |
| // \file |
| // Functions to manipulate and test property bits |
| |
| #ifndef FST_LIB_TEST_PROPERTIES_H__ |
| #define FST_LIB_TEST_PROPERTIES_H__ |
| |
| #include <unordered_set> |
| using std::tr1::unordered_set; |
| using std::tr1::unordered_multiset; |
| |
| #include <fst/dfs-visit.h> |
| #include <fst/connect.h> |
| |
| |
| DECLARE_bool(fst_verify_properties); |
| |
| namespace fst { |
| |
| // For a binary property, the bit is always returned set. |
| // For a trinary (i.e. two-bit) property, both bits are |
| // returned set iff either corresponding input bit is set. |
| inline uint64 KnownProperties(uint64 props) { |
| return kBinaryProperties | (props & kTrinaryProperties) | |
| ((props & kPosTrinaryProperties) << 1) | |
| ((props & kNegTrinaryProperties) >> 1); |
| } |
| |
| // Tests compatibility between two sets of properties |
| inline bool CompatProperties(uint64 props1, uint64 props2) { |
| uint64 known_props1 = KnownProperties(props1); |
| uint64 known_props2 = KnownProperties(props2); |
| uint64 known_props = known_props1 & known_props2; |
| uint64 incompat_props = (props1 & known_props) ^ (props2 & known_props); |
| if (incompat_props) { |
| uint64 prop = 1; |
| for (int i = 0; i < 64; ++i, prop <<= 1) |
| if (prop & incompat_props) |
| LOG(ERROR) << "CompatProperties: mismatch: " << PropertyNames[i] |
| << ": props1 = " << (props1 & prop ? "true" : "false") |
| << ", props2 = " << (props2 & prop ? "true" : "false"); |
| return false; |
| } else { |
| return true; |
| } |
| } |
| |
| // Computes FST property values defined in properties.h. The value of |
| // each property indicated in the mask will be determined and returned |
| // (these will never be unknown here). In the course of determining |
| // the properties specifically requested in the mask, certain other |
| // properties may be determined (those with little additional expense) |
| // and their values will be returned as well. The complete set of |
| // known properties (whether true or false) determined by this |
| // operation will be assigned to the the value pointed to by KNOWN. |
| // If 'use_stored' is true, pre-computed FST properties may be used |
| // when possible. This routine is seldom called directly; instead it |
| // is used to implement fst.Properties(mask, true). |
| template<class Arc> |
| uint64 ComputeProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known, |
| bool use_stored) { |
| typedef typename Arc::Label Label; |
| typedef typename Arc::Weight Weight; |
| typedef typename Arc::StateId StateId; |
| |
| uint64 fst_props = fst.Properties(kFstProperties, false); // Fst-stored |
| |
| // Check stored FST properties first if allowed. |
| if (use_stored) { |
| uint64 known_props = KnownProperties(fst_props); |
| // If FST contains required info, return it. |
| if ((known_props & mask) == mask) { |
| *known = known_props; |
| return fst_props; |
| } |
| } |
| |
| // Compute (trinary) properties explicitly. |
| |
| // Initialize with binary properties (already known). |
| uint64 comp_props = fst_props & kBinaryProperties; |
| |
| // Compute these trinary properties with a DFS. We compute only those |
| // that need a DFS here, since we otherwise would like to avoid a DFS |
| // since its stack could grow large. |
| uint64 dfs_props = kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic | |
| kAccessible | kNotAccessible | |
| kCoAccessible | kNotCoAccessible; |
| if (mask & dfs_props) { |
| SccVisitor<Arc> scc_visitor(&comp_props); |
| DfsVisit(fst, &scc_visitor); |
| } |
| |
| // Compute any remaining trinary properties via a state and arcs iterations |
| if (mask & ~(kBinaryProperties | dfs_props)) { |
| comp_props |= kAcceptor | kNoEpsilons | kNoIEpsilons | kNoOEpsilons | |
| kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted | kString; |
| if (mask & (kIDeterministic | kNonIDeterministic)) |
| comp_props |= kIDeterministic; |
| if (mask & (kODeterministic | kNonODeterministic)) |
| comp_props |= kODeterministic; |
| |
| unordered_set<Label> *ilabels = 0; |
| unordered_set<Label> *olabels = 0; |
| |
| StateId nfinal = 0; |
| for (StateIterator< Fst<Arc> > siter(fst); |
| !siter.Done(); |
| siter.Next()) { |
| StateId s = siter.Value(); |
| |
| Arc prev_arc(kNoLabel, kNoLabel, Weight::One(), 0); |
| // Create these only if we need to |
| if (mask & (kIDeterministic | kNonIDeterministic)) |
| ilabels = new unordered_set<Label>; |
| if (mask & (kODeterministic | kNonODeterministic)) |
| olabels = new unordered_set<Label>; |
| |
| for (ArcIterator< Fst<Arc> > aiter(fst, s); |
| !aiter.Done(); |
| aiter.Next()) { |
| const Arc &arc =aiter.Value(); |
| |
| if (ilabels && ilabels->find(arc.ilabel) != ilabels->end()) { |
| comp_props |= kNonIDeterministic; |
| comp_props &= ~kIDeterministic; |
| } |
| if (olabels && olabels->find(arc.olabel) != olabels->end()) { |
| comp_props |= kNonODeterministic; |
| comp_props &= ~kODeterministic; |
| } |
| if (arc.ilabel != arc.olabel) { |
| comp_props |= kNotAcceptor; |
| comp_props &= ~kAcceptor; |
| } |
| if (arc.ilabel == 0 && arc.olabel == 0) { |
| comp_props |= kEpsilons; |
| comp_props &= ~kNoEpsilons; |
| } |
| if (arc.ilabel == 0) { |
| comp_props |= kIEpsilons; |
| comp_props &= ~kNoIEpsilons; |
| } |
| if (arc.olabel == 0) { |
| comp_props |= kOEpsilons; |
| comp_props &= ~kNoOEpsilons; |
| } |
| if (prev_arc.ilabel != kNoLabel && arc.ilabel < prev_arc.ilabel) { |
| comp_props |= kNotILabelSorted; |
| comp_props &= ~kILabelSorted; |
| } |
| if (prev_arc.olabel != kNoLabel && arc.olabel < prev_arc.olabel) { |
| comp_props |= kNotOLabelSorted; |
| comp_props &= ~kOLabelSorted; |
| } |
| if (arc.weight != Weight::One() && arc.weight != Weight::Zero()) { |
| comp_props |= kWeighted; |
| comp_props &= ~kUnweighted; |
| } |
| if (arc.nextstate <= s) { |
| comp_props |= kNotTopSorted; |
| comp_props &= ~kTopSorted; |
| } |
| if (arc.nextstate != s + 1) { |
| comp_props |= kNotString; |
| comp_props &= ~kString; |
| } |
| prev_arc = arc; |
| if (ilabels) |
| ilabels->insert(arc.ilabel); |
| if (olabels) |
| olabels->insert(arc.olabel); |
| } |
| |
| if (nfinal > 0) { // final state not last |
| comp_props |= kNotString; |
| comp_props &= ~kString; |
| } |
| |
| Weight final = fst.Final(s); |
| |
| if (final != Weight::Zero()) { // final state |
| if (final != Weight::One()) { |
| comp_props |= kWeighted; |
| comp_props &= ~kUnweighted; |
| } |
| ++nfinal; |
| } else { // non-final state |
| if (fst.NumArcs(s) != 1) { |
| comp_props |= kNotString; |
| comp_props &= ~kString; |
| } |
| } |
| |
| delete ilabels; |
| delete olabels; |
| } |
| |
| if (fst.Start() != kNoStateId && fst.Start() != 0) { |
| comp_props |= kNotString; |
| comp_props &= ~kString; |
| } |
| } |
| |
| *known = KnownProperties(comp_props); |
| return comp_props; |
| } |
| |
| // This is a wrapper around ComputeProperties that will cause a fatal |
| // error if the stored properties and the computed properties are |
| // incompatible when 'FLAGS_fst_verify_properties' is true. This |
| // routine is seldom called directly; instead it is used to implement |
| // fst.Properties(mask, true). |
| template<class Arc> |
| uint64 TestProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known) { |
| if (FLAGS_fst_verify_properties) { |
| uint64 stored_props = fst.Properties(kFstProperties, false); |
| uint64 computed_props = ComputeProperties(fst, mask, known, false); |
| if (!CompatProperties(stored_props, computed_props)) |
| LOG(FATAL) << "TestProperties: stored Fst properties incorrect" |
| << " (stored: props1, computed: props2)"; |
| return computed_props; |
| } else { |
| return ComputeProperties(fst, mask, known, true); |
| } |
| } |
| |
| } // namespace fst |
| |
| #endif // FST_LIB_TEST_PROPERTIES_H__ |
