// info.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
// Class to compute various information about FSTs, helper class for fstinfo.cc
#ifndef FST_SCRIPT_INFO_IMPL_H_
#define FST_SCRIPT_INFO_IMPL_H_
#include <string>
#include <vector>
using std::vector;
#include <fst/connect.h>
#include <fst/dfs-visit.h>
#include <fst/fst.h>
#include <fst/lookahead-matcher.h>
#include <fst/matcher.h>
#include <fst/queue.h>
#include <fst/test-properties.h>
#include <fst/verify.h>
#include <fst/visit.h>
namespace fst {
// Compute various information about FSTs, helper class for fstinfo.cc.
// WARNING: Stand-alone use of this class is not recommended, most code
// should call directly the relevant library functions: Fst<A>::NumStates,
// Fst<A>::NumArcs, TestProperties, ...
template <class A> class FstInfo {
public:
typedef A Arc;
typedef typename A::StateId StateId;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
// When info_type is "short" (or "auto" and not an ExpandedFst)
// then only minimal info is computed and can be requested.
FstInfo(const Fst<A> &fst, bool test_properties,
const string &arc_filter_type = "any",
string info_type = "auto", bool verify = true)
: fst_type_(fst.Type()),
input_symbols_(fst.InputSymbols() ?
fst.InputSymbols()->Name() : "none"),
output_symbols_(fst.OutputSymbols() ?
fst.OutputSymbols()->Name() : "none"),
nstates_(0), narcs_(0), start_(kNoStateId), nfinal_(0),
nepsilons_(0), niepsilons_(0), noepsilons_(0),
naccess_(0), ncoaccess_(0), nconnect_(0), ncc_(0), nscc_(0),
input_match_type_(MATCH_NONE), output_match_type_(MATCH_NONE),
input_lookahead_(false), output_lookahead_(false),
properties_(0), arc_filter_type_(arc_filter_type), long_info_(true) {
if (info_type == "long") {
long_info_ = true;
} else if (info_type == "short") {
long_info_ = false;
} else if (info_type == "auto") {
long_info_ = fst.Properties(kExpanded, false);
} else {
FSTERROR() << "Bad info type: " << info_type;
return;
}
if (!long_info_)
return;
// If the FST is not sane, we return.
if (verify && !Verify(fst)) {
FSTERROR() << "FstInfo: Verify: FST not well-formed.";
return;
}
start_ = fst.Start();
properties_ = fst.Properties(kFstProperties, test_properties);
for (StateIterator< Fst<A> > siter(fst);
!siter.Done();
siter.Next()) {
++nstates_;
StateId s = siter.Value();
if (fst.Final(s) != Weight::Zero())
++nfinal_;
for (ArcIterator< Fst<A> > aiter(fst, s);
!aiter.Done();
aiter.Next()) {
const A &arc = aiter.Value();
++narcs_;
if (arc.ilabel == 0 && arc.olabel == 0)
++nepsilons_;
if (arc.ilabel == 0)
++niepsilons_;
if (arc.olabel == 0)
++noepsilons_;
}
}
{
vector<StateId> cc;
CcVisitor<Arc> cc_visitor(&cc);
FifoQueue<StateId> fifo_queue;
if (arc_filter_type == "any") {
Visit(fst, &cc_visitor, &fifo_queue);
} else if (arc_filter_type == "epsilon") {
Visit(fst, &cc_visitor, &fifo_queue, EpsilonArcFilter<Arc>());
} else if (arc_filter_type == "iepsilon") {
Visit(fst, &cc_visitor, &fifo_queue, InputEpsilonArcFilter<Arc>());
} else if (arc_filter_type == "oepsilon") {
Visit(fst, &cc_visitor, &fifo_queue, OutputEpsilonArcFilter<Arc>());
} else {
FSTERROR() << "Bad arc filter type: " << arc_filter_type;
return;
}
for (StateId s = 0; s < cc.size(); ++s) {
if (cc[s] >= ncc_)
ncc_ = cc[s] + 1;
}
}
{
vector<StateId> scc;
vector<bool> access, coaccess;
uint64 props = 0;
SccVisitor<Arc> scc_visitor(&scc, &access, &coaccess, &props);
if (arc_filter_type == "any") {
DfsVisit(fst, &scc_visitor);
} else if (arc_filter_type == "epsilon") {
DfsVisit(fst, &scc_visitor, EpsilonArcFilter<Arc>());
} else if (arc_filter_type == "iepsilon") {
DfsVisit(fst, &scc_visitor, InputEpsilonArcFilter<Arc>());
} else if (arc_filter_type == "oepsilon") {
DfsVisit(fst, &scc_visitor, OutputEpsilonArcFilter<Arc>());
} else {
FSTERROR() << "Bad arc filter type: " << arc_filter_type;
return;
}
for (StateId s = 0; s < scc.size(); ++s) {
if (access[s])
++naccess_;
if (coaccess[s])
++ncoaccess_;
if (access[s] && coaccess[s])
++nconnect_;
if (scc[s] >= nscc_)
nscc_ = scc[s] + 1;
}
}
LookAheadMatcher< Fst<A> > imatcher(fst, MATCH_INPUT);
input_match_type_ = imatcher.Type(test_properties);
input_lookahead_ = imatcher.Flags() & kInputLookAheadMatcher;
LookAheadMatcher< Fst<A> > omatcher(fst, MATCH_OUTPUT);
output_match_type_ = omatcher.Type(test_properties);
output_lookahead_ = omatcher.Flags() & kOutputLookAheadMatcher;
}
// Short info
const string& FstType() const { return fst_type_; }
const string& ArcType() const { return A::Type(); }
const string& InputSymbols() const { return input_symbols_; }
const string& OutputSymbols() const { return output_symbols_; }
const bool LongInfo() const { return long_info_; }
const string& ArcFilterType() const { return arc_filter_type_; }
// Long info
MatchType InputMatchType() const { CheckLong(); return input_match_type_; }
MatchType OutputMatchType() const { CheckLong(); return output_match_type_; }
bool InputLookAhead() const { CheckLong(); return input_lookahead_; }
bool OutputLookAhead() const { CheckLong(); return output_lookahead_; }
int64 NumStates() const { CheckLong(); return nstates_; }
int64 NumArcs() const { CheckLong(); return narcs_; }
int64 Start() const { CheckLong(); return start_; }
int64 NumFinal() const { CheckLong(); return nfinal_; }
int64 NumEpsilons() const { CheckLong(); return nepsilons_; }
int64 NumInputEpsilons() const { CheckLong(); return niepsilons_; }
int64 NumOutputEpsilons() const { CheckLong(); return noepsilons_; }
int64 NumAccessible() const { CheckLong(); return naccess_; }
int64 NumCoAccessible() const { CheckLong(); return ncoaccess_; }
int64 NumConnected() const { CheckLong(); return nconnect_; }
int64 NumCc() const { CheckLong(); return ncc_; }
int64 NumScc() const { CheckLong(); return nscc_; }
uint64 Properties() const { CheckLong(); return properties_; }
private:
void CheckLong() const {
if (!long_info_)
FSTERROR() << "FstInfo: method only available with long info version";
}
string fst_type_;
string input_symbols_;
string output_symbols_;
int64 nstates_;
int64 narcs_;
int64 start_;
int64 nfinal_;
int64 nepsilons_;
int64 niepsilons_;
int64 noepsilons_;
int64 naccess_;
int64 ncoaccess_;
int64 nconnect_;
int64 ncc_;
int64 nscc_;
MatchType input_match_type_;
MatchType output_match_type_;
bool input_lookahead_;
bool output_lookahead_;
uint64 properties_;
string arc_filter_type_;
bool long_info_;
DISALLOW_COPY_AND_ASSIGN(FstInfo);
};
template <class A>
void PrintFstInfo(const FstInfo<A> &fstinfo, bool pipe = false) {
ostream &os = pipe ? cerr : cout;
ios_base::fmtflags old = os.setf(ios::left);
os.width(50);
os << "fst type" << fstinfo.FstType() << endl;
os.width(50);
os << "arc type" << fstinfo.ArcType() << endl;
os.width(50);
os << "input symbol table" << fstinfo.InputSymbols() << endl;
os.width(50);
os << "output symbol table" << fstinfo.OutputSymbols() << endl;
if (!fstinfo.LongInfo()) {
os.setf(old);
return;
}
os.width(50);
os << "# of states" << fstinfo.NumStates() << endl;
os.width(50);
os << "# of arcs" << fstinfo.NumArcs() << endl;
os.width(50);
os << "initial state" << fstinfo.Start() << endl;
os.width(50);
os << "# of final states" << fstinfo.NumFinal() << endl;
os.width(50);
os << "# of input/output epsilons" << fstinfo.NumEpsilons() << endl;
os.width(50);
os << "# of input epsilons" << fstinfo.NumInputEpsilons() << endl;
os.width(50);
os << "# of output epsilons" << fstinfo.NumOutputEpsilons() << endl;
os.width(50);
string arc_type = "";
if (fstinfo.ArcFilterType() == "epsilon")
arc_type = "epsilon ";
else if (fstinfo.ArcFilterType() == "iepsilon")
arc_type = "input-epsilon ";
else if (fstinfo.ArcFilterType() == "oepsilon")
arc_type = "output-epsilon ";
string accessible_label = "# of " + arc_type + "accessible states";
os.width(50);
os << accessible_label << fstinfo.NumAccessible() << endl;
string coaccessible_label = "# of " + arc_type + "coaccessible states";
os.width(50);
os << coaccessible_label << fstinfo.NumCoAccessible() << endl;
string connected_label = "# of " + arc_type + "connected states";
os.width(50);
os << connected_label << fstinfo.NumConnected() << endl;
string numcc_label = "# of " + arc_type + "connected components";
os.width(50);
os << numcc_label << fstinfo.NumCc() << endl;
string numscc_label = "# of " + arc_type + "strongly conn components";
os.width(50);
os << numscc_label << fstinfo.NumScc() << endl;
os.width(50);
os << "input matcher"
<< (fstinfo.InputMatchType() == MATCH_INPUT ? 'y' :
fstinfo.InputMatchType() == MATCH_NONE ? 'n' : '?') << endl;
os.width(50);
os << "output matcher"
<< (fstinfo.OutputMatchType() == MATCH_OUTPUT ? 'y' :
fstinfo.OutputMatchType() == MATCH_NONE ? 'n' : '?') << endl;
os.width(50);
os << "input lookahead"
<< (fstinfo.InputLookAhead() ? 'y' : 'n') << endl;
os.width(50);
os << "output lookahead"
<< (fstinfo.OutputLookAhead() ? 'y' : 'n') << endl;
uint64 prop = 1;
for (int i = 0; i < 64; ++i, prop <<= 1) {
if (prop & kBinaryProperties) {
char value = 'n';
if (fstinfo.Properties() & prop) value = 'y';
os.width(50);
os << PropertyNames[i] << value << endl;
} else if (prop & kPosTrinaryProperties) {
char value = '?';
if (fstinfo.Properties() & prop) value = 'y';
else if (fstinfo.Properties() & prop << 1) value = 'n';
os.width(50);
os << PropertyNames[i] << value << endl;
}
}
os.setf(old);
}
} // namespace fst
#endif // FST_SCRIPT_INFO_IMPL_H_