// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
//
|
// Functions to manipulate and test property bits.
|
|
#ifndef FST_TEST_PROPERTIES_H_
|
#define FST_TEST_PROPERTIES_H_
|
|
#include <unordered_set>
|
|
#include <fst/flags.h>
|
#include <fst/log.h>
|
|
#include <fst/connect.h>
|
#include <fst/dfs-visit.h>
|
|
|
DECLARE_bool(fst_verify_properties);
|
|
namespace fst {
|
// namespace internal {
|
|
// 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) {
|
const auto known_props1 = KnownProperties(props1);
|
const auto known_props2 = KnownProperties(props2);
|
const auto known_props = known_props1 & known_props2;
|
const auto 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. 'mask & required_mask' is used to determine whether the stored
|
// propertoes can be used. 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) {
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
const auto fst_props = fst.Properties(kFstProperties, false); // FST-stored.
|
// Check stored FST properties first if allowed.
|
if (use_stored) {
|
const auto known_props = KnownProperties(fst_props);
|
// If FST contains required info, return it.
|
if ((known_props & mask) == mask) {
|
if (known) *known = known_props;
|
return fst_props;
|
}
|
}
|
// Computes (trinary) properties explicitly.
|
// Initialize with binary properties (already known).
|
uint64 comp_props = fst_props & kBinaryProperties;
|
// Computes 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;
|
std::vector<StateId> scc;
|
if (mask & (dfs_props | kWeightedCycles | kUnweightedCycles)) {
|
SccVisitor<Arc> scc_visitor(&scc, nullptr, nullptr, &comp_props);
|
DfsVisit(fst, &scc_visitor);
|
}
|
// Computes 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;
|
}
|
if (mask & (dfs_props | kWeightedCycles | kUnweightedCycles)) {
|
comp_props |= kUnweightedCycles;
|
}
|
std::unique_ptr<std::unordered_set<Label>> ilabels;
|
std::unique_ptr<std::unordered_set<Label>> olabels;
|
StateId nfinal = 0;
|
for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
|
StateId s = siter.Value();
|
Arc prev_arc;
|
// Creates these only if we need to.
|
if (mask & (kIDeterministic | kNonIDeterministic)) {
|
ilabels.reset(new std::unordered_set<Label>());
|
}
|
if (mask & (kODeterministic | kNonODeterministic)) {
|
olabels.reset(new std::unordered_set<Label>());
|
}
|
bool first_arc = true;
|
for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
|
const auto &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 (!first_arc) {
|
if (arc.ilabel < prev_arc.ilabel) {
|
comp_props |= kNotILabelSorted;
|
comp_props &= ~kILabelSorted;
|
}
|
if (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 ((comp_props & kUnweightedCycles) &&
|
scc[s] == scc[arc.nextstate]) {
|
comp_props |= kWeightedCycles;
|
comp_props &= ~kUnweightedCycles;
|
}
|
}
|
if (arc.nextstate <= s) {
|
comp_props |= kNotTopSorted;
|
comp_props &= ~kTopSorted;
|
}
|
if (arc.nextstate != s + 1) {
|
comp_props |= kNotString;
|
comp_props &= ~kString;
|
}
|
prev_arc = arc;
|
first_arc = false;
|
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;
|
}
|
const auto final_weight = fst.Final(s);
|
if (final_weight != Weight::Zero()) { // Final state.
|
if (final_weight != Weight::One()) {
|
comp_props |= kWeighted;
|
comp_props &= ~kUnweighted;
|
}
|
++nfinal;
|
} else { // Non-final state.
|
if (fst.NumArcs(s) != 1) {
|
comp_props |= kNotString;
|
comp_props &= ~kString;
|
}
|
}
|
}
|
if (fst.Start() != kNoStateId && fst.Start() != 0) {
|
comp_props |= kNotString;
|
comp_props &= ~kString;
|
}
|
}
|
if (known) *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) {
|
const auto stored_props = fst.Properties(kFstProperties, false);
|
const auto computed_props = ComputeProperties(fst, mask, known, false);
|
if (!CompatProperties(stored_props, computed_props)) {
|
FSTERROR() << "TestProperties: stored FST properties incorrect"
|
<< " (stored: props1, computed: props2)";
|
}
|
return computed_props;
|
} else {
|
return ComputeProperties(fst, mask, known, true);
|
}
|
}
|
|
// If all the properties of 'fst' corresponding to 'check_mask' are known,
|
// returns the stored properties. Otherwise, the properties corresponding to
|
// both 'check_mask' and 'test_mask' are computed. This is used to check for
|
// newly-added properties that might not be set in old binary files.
|
template <class Arc>
|
uint64 CheckProperties(const Fst<Arc> &fst, uint64 check_mask,
|
uint64 test_mask) {
|
auto props = fst.Properties(kFstProperties, false);
|
if (FLAGS_fst_verify_properties) {
|
props = TestProperties(fst, check_mask | test_mask, nullptr);
|
} else if ((KnownProperties(props) & check_mask) != check_mask) {
|
props = ComputeProperties(fst, check_mask | test_mask, nullptr, false);
|
}
|
return props & (check_mask | test_mask);
|
}
|
|
//} // namespace internal
|
} // namespace fst
|
|
#endif // FST_TEST_PROPERTIES_H_
|
