Home | History | Annotate | Download | only in fst 
      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 // Copyright 2005-2010 Google, Inc.
     16 // Author: riley (at) google.com (Michael Riley)
     17 //
     18 // \file
     19 // Functions to manipulate and test property bits
     20 
     21 #ifndef FST_LIB_TEST_PROPERTIES_H__
     22 #define FST_LIB_TEST_PROPERTIES_H__
     23 
     24 #include <tr1/unordered_set>
     25 using std::tr1::unordered_set;
     26 using std::tr1::unordered_multiset;
     27 
     28 #include <fst/dfs-visit.h>
     29 #include <fst/connect.h>
     30 
     31 
     32 DECLARE_bool(fst_verify_properties);
     33 
     34 namespace fst {
     35 
     36 // For a binary property, the bit is always returned set.
     37 // For a trinary (i.e. two-bit) property, both bits are
     38 // returned set iff either corresponding input bit is set.
     39 inline uint64 KnownProperties(uint64 props) {
     40   return kBinaryProperties | (props & kTrinaryProperties) |
     41     ((props & kPosTrinaryProperties) << 1) |
     42     ((props & kNegTrinaryProperties) >> 1);
     43 }
     44 
     45 // Tests compatibility between two sets of properties
     46 inline bool CompatProperties(uint64 props1, uint64 props2) {
     47   uint64 known_props1 = KnownProperties(props1);
     48   uint64 known_props2 = KnownProperties(props2);
     49   uint64 known_props = known_props1 & known_props2;
     50   uint64 incompat_props = (props1 & known_props) ^ (props2 & known_props);
     51   if (incompat_props) {
     52     uint64 prop = 1;
     53     for (int i = 0; i < 64; ++i, prop <<= 1)
     54       if (prop & incompat_props)
     55         LOG(ERROR) << "CompatProperties: mismatch: " << PropertyNames[i]
     56                    << ": props1 = " << (props1 & prop ? "true" : "false")
     57                    << ", props2 = " << (props2 & prop ? "true" : "false");
     58     return false;
     59   } else {
     60     return true;
     61   }
     62 }
     63 
     64 // Computes FST property values defined in properties.h.  The value of
     65 // each property indicated in the mask will be determined and returned
     66 // (these will never be unknown here). In the course of determining
     67 // the properties specifically requested in the mask, certain other
     68 // properties may be determined (those with little additional expense)
     69 // and their values will be returned as well. The complete set of
     70 // known properties (whether true or false) determined by this
     71 // operation will be assigned to the the value pointed to by KNOWN.
     72 // If 'use_stored' is true, pre-computed FST properties may be used
     73 // when possible. This routine is seldom called directly; instead it
     74 // is used to implement fst.Properties(mask, true).
     75 template<class Arc>
     76 uint64 ComputeProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known,
     77                          bool use_stored) {
     78   typedef typename Arc::Label Label;
     79   typedef typename Arc::Weight Weight;
     80   typedef typename Arc::StateId StateId;
     81 
     82   uint64 fst_props = fst.Properties(kFstProperties, false);  // Fst-stored
     83 
     84   // Check stored FST properties first if allowed.
     85   if (use_stored) {
     86     uint64 known_props = KnownProperties(fst_props);
     87     // If FST contains required info, return it.
     88     if ((known_props & mask) == mask) {
     89       *known = known_props;
     90       return fst_props;
     91     }
     92   }
     93 
     94   // Compute (trinary) properties explicitly.
     95 
     96   // Initialize with binary properties (already known).
     97   uint64 comp_props = fst_props & kBinaryProperties;
     98 
     99   // Compute these trinary properties with a DFS. We compute only those
    100   // that need a DFS here, since we otherwise would like to avoid a DFS
    101   // since its stack could grow large.
    102   uint64 dfs_props = kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
    103                      kAccessible | kNotAccessible |
    104                      kCoAccessible | kNotCoAccessible;
    105   if (mask & dfs_props) {
    106     SccVisitor<Arc> scc_visitor(&comp_props);
    107     DfsVisit(fst, &scc_visitor);
    108   }
    109 
    110   // Compute any remaining trinary properties via a state and arcs iterations
    111   if (mask & ~(kBinaryProperties | dfs_props)) {
    112     comp_props |= kAcceptor | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
    113         kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted | kString;
    114     if (mask & (kIDeterministic | kNonIDeterministic))
    115       comp_props |= kIDeterministic;
    116     if (mask & (kODeterministic | kNonODeterministic))
    117       comp_props |= kODeterministic;
    118 
    119     unordered_set<Label> *ilabels = 0;
    120     unordered_set<Label> *olabels = 0;
    121 
    122     StateId nfinal = 0;
    123     for (StateIterator< Fst<Arc> > siter(fst);
    124          !siter.Done();
    125          siter.Next()) {
    126       StateId s = siter.Value();
    127 
    128       Arc prev_arc;
    129       // Create these only if we need to
    130       if (mask & (kIDeterministic | kNonIDeterministic))
    131         ilabels = new unordered_set<Label>;
    132       if (mask & (kODeterministic | kNonODeterministic))
    133         olabels = new unordered_set<Label>;
    134 
    135       bool first_arc = true;
    136       for (ArcIterator< Fst<Arc> > aiter(fst, s);
    137            !aiter.Done();
    138            aiter.Next()) {
    139         const Arc &arc =aiter.Value();
    140 
    141         if (ilabels && ilabels->find(arc.ilabel) != ilabels->end()) {
    142           comp_props |= kNonIDeterministic;
    143           comp_props &= ~kIDeterministic;
    144         }
    145         if (olabels && olabels->find(arc.olabel) != olabels->end()) {
    146           comp_props |= kNonODeterministic;
    147           comp_props &= ~kODeterministic;
    148         }
    149         if (arc.ilabel != arc.olabel) {
    150           comp_props |= kNotAcceptor;
    151           comp_props &= ~kAcceptor;
    152         }
    153         if (arc.ilabel == 0 && arc.olabel == 0) {
    154           comp_props |= kEpsilons;
    155           comp_props &= ~kNoEpsilons;
    156         }
    157         if (arc.ilabel == 0) {
    158           comp_props |= kIEpsilons;
    159           comp_props &= ~kNoIEpsilons;
    160         }
    161         if (arc.olabel == 0) {
    162           comp_props |= kOEpsilons;
    163           comp_props &= ~kNoOEpsilons;
    164         }
    165         if (!first_arc) {
    166           if (arc.ilabel < prev_arc.ilabel) {
    167             comp_props |= kNotILabelSorted;
    168             comp_props &= ~kILabelSorted;
    169           }
    170           if (arc.olabel < prev_arc.olabel) {
    171             comp_props |= kNotOLabelSorted;
    172             comp_props &= ~kOLabelSorted;
    173           }
    174         }
    175         if (arc.weight != Weight::One() && arc.weight != Weight::Zero()) {
    176           comp_props |= kWeighted;
    177           comp_props &= ~kUnweighted;
    178         }
    179         if (arc.nextstate <= s) {
    180           comp_props |= kNotTopSorted;
    181           comp_props &= ~kTopSorted;
    182         }
    183         if (arc.nextstate != s + 1) {
    184           comp_props |= kNotString;
    185           comp_props &= ~kString;
    186         }
    187         prev_arc = arc;
    188         first_arc = false;
    189         if (ilabels)
    190           ilabels->insert(arc.ilabel);
    191         if (olabels)
    192           olabels->insert(arc.olabel);
    193       }
    194 
    195       if (nfinal > 0) {             // final state not last
    196         comp_props |= kNotString;
    197         comp_props &= ~kString;
    198       }
    199 
    200       Weight final = fst.Final(s);
    201 
    202       if (final != Weight::Zero()) {  // final state
    203         if (final != Weight::One()) {
    204           comp_props |= kWeighted;
    205           comp_props &= ~kUnweighted;
    206         }
    207         ++nfinal;
    208       } else {                        // non-final state
    209         if (fst.NumArcs(s) != 1) {
    210           comp_props |= kNotString;
    211           comp_props &= ~kString;
    212         }
    213       }
    214 
    215       delete ilabels;
    216       delete olabels;
    217     }
    218 
    219     if (fst.Start() != kNoStateId && fst.Start() != 0) {
    220       comp_props |= kNotString;
    221       comp_props &= ~kString;
    222     }
    223   }
    224 
    225   *known = KnownProperties(comp_props);
    226   return comp_props;
    227 }
    228 
    229 // This is a wrapper around ComputeProperties that will cause a fatal
    230 // error if the stored properties and the computed properties are
    231 // incompatible when 'FLAGS_fst_verify_properties' is true.  This
    232 // routine is seldom called directly; instead it is used to implement
    233 // fst.Properties(mask, true).
    234 template<class Arc>
    235 uint64 TestProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known) {
    236   if (FLAGS_fst_verify_properties) {
    237     uint64 stored_props = fst.Properties(kFstProperties, false);
    238     uint64 computed_props = ComputeProperties(fst, mask, known, false);
    239     if (!CompatProperties(stored_props, computed_props))
    240       LOG(FATAL) << "TestProperties: stored Fst properties incorrect"
    241                  << " (stored: props1, computed: props2)";
    242     return computed_props;
    243   } else {
    244     return ComputeProperties(fst, mask, known, true);
    245   }
    246 }
    247 
    248 }  // namespace fst
    249 
    250 #endif  // FST_LIB_TEST_PROPERTIES_H__
    251