aboutsummaryrefslogtreecommitdiff
path: root/src/include/fst/test-properties.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/include/fst/test-properties.h')
-rw-r--r--src/include/fst/test-properties.h246
1 files changed, 246 insertions, 0 deletions
diff --git a/src/include/fst/test-properties.h b/src/include/fst/test-properties.h
new file mode 100644
index 0000000..db1ddcc
--- /dev/null
+++ b/src/include/fst/test-properties.h
@@ -0,0 +1,246 @@
+// 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__
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 18:08:19 +0000