xref: /external/openfst/src/include/fst/properties.h

// 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: Michael Riley <riley@google.com>
// \file
// FST property bits.

#ifndef FST_LIB_PROPERTIES_H__
#define FST_LIB_PROPERTIES_H__

#include <sys/types.h>
#include <vector>
using std::vector;

#include <fst/compat.h>

namespace fst {

// The property bits here assert facts about an FST. If individual
// bits are added, then the composite properties below, the property
// functions and property names in properties.cc, and
// TestProperties() in test-properties.h should be updated.

//
// BINARY PROPERTIES
//
// For each property below, there is a single bit. If it is set,
// the property is true. If it is not set, the property is false.
//

// The Fst is an ExpandedFst
const uint64 kExpanded =          0x0000000000000001ULL;

// The Fst is a MutableFst
const uint64 kMutable =           0x0000000000000002ULL;

// An error was detected while constructing/using the FST
const uint64 kError =             0x0000000000000004ULL;

//
// TRINARY PROPERTIES
//
// For each of these properties below there is a pair of property bits
// - one positive and one negative. If the positive bit is set, the
// property is true. If the negative bit is set, the property is
// false. If neither is set, the property has unknown value. Both
// should never be simultaneously set. The individual positive and
// negative bit pairs should be adjacent with the positive bit
// at an odd and lower position.

// ilabel == olabel for each arc
const uint64 kAcceptor =          0x0000000000010000ULL;
// ilabel != olabel for some arc
const uint64 kNotAcceptor =       0x0000000000020000ULL;

// ilabels unique leaving each state
const uint64 kIDeterministic =    0x0000000000040000ULL;
// ilabels not unique leaving some state
const uint64 kNonIDeterministic = 0x0000000000080000ULL;

// olabels unique leaving each state
const uint64 kODeterministic =    0x0000000000100000ULL;
// olabels not unique leaving some state
const uint64 kNonODeterministic = 0x0000000000200000ULL;

// FST has input/output epsilons
const uint64 kEpsilons =          0x0000000000400000ULL;
// FST has no input/output epsilons
const uint64 kNoEpsilons =        0x0000000000800000ULL;

// FST has input epsilons
const uint64 kIEpsilons =         0x0000000001000000ULL;
// FST has no input epsilons
const uint64 kNoIEpsilons =       0x0000000002000000ULL;

// FST has output epsilons
const uint64 kOEpsilons =         0x0000000004000000ULL;
// FST has no output epsilons
const uint64 kNoOEpsilons =       0x0000000008000000ULL;

// ilabels sorted wrt < for each state
const uint64 kILabelSorted =      0x0000000010000000ULL;
// ilabels not sorted wrt < for some state
const uint64 kNotILabelSorted =   0x0000000020000000ULL;

// olabels sorted wrt < for each state
const uint64 kOLabelSorted =      0x0000000040000000ULL;
// olabels not sorted wrt < for some state
const uint64 kNotOLabelSorted =   0x0000000080000000ULL;

// Non-trivial arc or final weights
const uint64 kWeighted =          0x0000000100000000ULL;
// Only trivial arc and final weights
const uint64 kUnweighted =        0x0000000200000000ULL;

// FST has cycles
const uint64 kCyclic =            0x0000000400000000ULL;
// FST has no cycles
const uint64 kAcyclic =           0x0000000800000000ULL;

// FST has cycles containing the initial state
const uint64 kInitialCyclic =     0x0000001000000000ULL;
// FST has no cycles containing the initial state
const uint64 kInitialAcyclic =    0x0000002000000000ULL;

// FST is topologically sorted
const uint64 kTopSorted =         0x0000004000000000ULL;
// FST is not topologically sorted
const uint64 kNotTopSorted =      0x0000008000000000ULL;

// All states reachable from the initial state
const uint64 kAccessible =        0x0000010000000000ULL;
// Not all states reachable from the initial state
const uint64 kNotAccessible =     0x0000020000000000ULL;

// All states can reach a final state
const uint64 kCoAccessible =      0x0000040000000000ULL;
// Not all states can reach a final state
const uint64 kNotCoAccessible =   0x0000080000000000ULL;

// If NumStates() > 0, then state 0 is initial, state NumStates()-1 is
// final, there is a transition from each non-final state i to
// state i+1, and there are no other transitions.
const uint64 kString =            0x0000100000000000ULL;

// Not a string FST
const uint64 kNotString =         0x0000200000000000ULL;

//
// COMPOSITE PROPERTIES
//

// Properties of an empty machine
const uint64 kNullProperties
  = kAcceptor | kIDeterministic | kODeterministic | kNoEpsilons |
    kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted |
    kUnweighted | kAcyclic | kInitialAcyclic | kTopSorted |
    kAccessible | kCoAccessible | kString;

// Properties that are preserved when an FST is copied
const uint64 kCopyProperties
  = kError | kAcceptor | kNotAcceptor | kIDeterministic | kNonIDeterministic |
    kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
    kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
    kILabelSorted | kNotILabelSorted | kOLabelSorted |
    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
    kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
    kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
    kString | kNotString;

// Properites that are intrinsic to the FST
const uint64 kIntrinsicProperties
  = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
    kNonIDeterministic | kODeterministic | kNonODeterministic |
    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
    kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
    kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
    kString | kNotString;

// Properites that are (potentially) extrinsic to the FST
const uint64 kExtrinsicProperties = kError;

// Properties that are preserved when an FST start state is set
const uint64 kSetStartProperties
  = kExpanded | kMutable | kError | kAcceptor | kNotAcceptor |
    kIDeterministic | kNonIDeterministic | kODeterministic |
    kNonODeterministic | kEpsilons | kNoEpsilons | kIEpsilons |
    kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted |
    kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kWeighted |
    kUnweighted | kCyclic | kAcyclic | kTopSorted | kNotTopSorted |
    kCoAccessible | kNotCoAccessible;

// Properties that are preserved when an FST final weight is set
const uint64 kSetFinalProperties
  = kExpanded | kMutable | kError | kAcceptor | kNotAcceptor |
    kIDeterministic | kNonIDeterministic | kODeterministic |
    kNonODeterministic | kEpsilons | kNoEpsilons | kIEpsilons |
    kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted |
    kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kCyclic |
    kAcyclic | kInitialCyclic | kInitialAcyclic | kTopSorted |
    kNotTopSorted | kAccessible | kNotAccessible;

// Properties that are preserved when an FST state is added
const uint64 kAddStateProperties
  = kExpanded | kMutable | kError | kAcceptor | kNotAcceptor |
    kIDeterministic | kNonIDeterministic | kODeterministic |
    kNonODeterministic | kEpsilons | kNoEpsilons | kIEpsilons |
    kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted |
    kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kWeighted |
    kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
    kInitialAcyclic | kTopSorted | kNotTopSorted | kNotAccessible |
    kNotCoAccessible | kNotString;

// Properties that are preserved when an FST arc is added
const uint64 kAddArcProperties = kExpanded | kMutable | kError | kNotAcceptor |
    kNonIDeterministic | kNonODeterministic | kEpsilons | kIEpsilons |
    kOEpsilons | kNotILabelSorted | kNotOLabelSorted | kWeighted |
    kCyclic | kInitialCyclic | kNotTopSorted | kAccessible | kCoAccessible;

// Properties that are preserved when an FST arc is set
const uint64 kSetArcProperties = kExpanded | kMutable | kError;

// Properties that are preserved when FST states are deleted
const uint64 kDeleteStatesProperties
  = kExpanded | kMutable | kError | kAcceptor | kIDeterministic |
    kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
    kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
    kInitialAcyclic | kTopSorted;

// Properties that are preserved when FST arcs are deleted
const uint64 kDeleteArcsProperties
  = kExpanded | kMutable | kError | kAcceptor | kIDeterministic |
    kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
    kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
    kInitialAcyclic | kTopSorted |  kNotAccessible | kNotCoAccessible;

// Properties that are preserved when an FST's states are reordered
const uint64 kStateSortProperties = kExpanded | kMutable | kError | kAcceptor |
    kNotAcceptor | kIDeterministic | kNonIDeterministic |
    kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
    kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
    kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted
    | kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
    kInitialAcyclic | kAccessible | kNotAccessible | kCoAccessible |
    kNotCoAccessible;

// Properties that are preserved when an FST's arcs are reordered
const uint64 kArcSortProperties =
  kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
  kNonIDeterministic | kODeterministic | kNonODeterministic |
  kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
  kNoOEpsilons | kWeighted | kUnweighted | kCyclic | kAcyclic |
  kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
  kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
  kString | kNotString;

// Properties that are preserved when an FST's input labels are changed.
const uint64 kILabelInvariantProperties =
  kExpanded | kMutable | kError | kODeterministic | kNonODeterministic |
  kOEpsilons | kNoOEpsilons | kOLabelSorted | kNotOLabelSorted |
  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
  kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString;

// Properties that are preserved when an FST's output labels are changed.
const uint64 kOLabelInvariantProperties =
  kExpanded | kMutable | kError | kIDeterministic | kNonIDeterministic |
  kIEpsilons | kNoIEpsilons | kILabelSorted | kNotILabelSorted |
  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
  kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString;

// Properties that are preserved when an FST's weights are changed.
// This assumes that the set of states that are non-final is not changed.
const uint64 kWeightInvariantProperties =
  kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
  kNonIDeterministic | kODeterministic | kNonODeterministic |
  kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
  kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
  kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
  kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
  kNotCoAccessible | kString | kNotString;

// Properties that are preserved when a superfinal state is added
// and an FSTs final weights are directed to it via new transitions.
const uint64 kAddSuperFinalProperties  = kExpanded | kMutable | kError |
    kAcceptor | kNotAcceptor | kNonIDeterministic | kNonODeterministic |
    kEpsilons | kIEpsilons | kOEpsilons | kNotILabelSorted | kNotOLabelSorted |
    kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
    kInitialAcyclic | kNotTopSorted | kNotAccessible | kCoAccessible |
    kNotCoAccessible | kNotString;

// Properties that are preserved when a superfinal state is removed
// and the epsilon transitions directed to it are made final weights.
const uint64 kRmSuperFinalProperties  = kExpanded | kMutable | kError |
    kAcceptor | kNotAcceptor | kIDeterministic | kODeterministic |
    kNoEpsilons | kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted |
    kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
    kInitialAcyclic | kTopSorted | kAccessible | kCoAccessible |
    kNotCoAccessible | kString;

// All binary properties
const uint64 kBinaryProperties =  0x0000000000000007ULL;

// All trinary properties
const uint64 kTrinaryProperties = 0x00003fffffff0000ULL;

//
// COMPUTED PROPERTIES
//

// 1st bit of trinary properties
const uint64 kPosTrinaryProperties =
  kTrinaryProperties & 0x5555555555555555ULL;

// 2nd bit of trinary properties
const uint64 kNegTrinaryProperties =
  kTrinaryProperties & 0xaaaaaaaaaaaaaaaaULL;

// All properties
const uint64 kFstProperties = kBinaryProperties | kTrinaryProperties;

//
// PROPERTY FUNCTIONS and STRING NAMES (defined in properties.cc)
//

// Below are functions for getting property bit vectors when executing
// mutating fst operations.
inline uint64 SetStartProperties(uint64 inprops);
template <typename Weight>
uint64 SetFinalProperties(uint64 inprops, Weight old_weight,
                          Weight new_weight);
inline uint64 AddStateProperties(uint64 inprops);
template <typename A>
uint64 AddArcProperties(uint64 inprops, typename A::StateId s, const A &arc,
                           const A *prev_arc);
inline uint64 DeleteStatesProperties(uint64 inprops);
inline uint64 DeleteAllStatesProperties(uint64 inprops, uint64 staticProps);
inline uint64 DeleteArcsProperties(uint64 inprops);

uint64 ClosureProperties(uint64 inprops, bool star, bool delayed = false);
uint64 ComplementProperties(uint64 inprops);
uint64 ComposeProperties(uint64 inprops1, uint64 inprops2);
uint64 ConcatProperties(uint64 inprops1, uint64 inprops2,
                        bool delayed = false);
uint64 DeterminizeProperties(uint64 inprops, bool has_subsequential_label);
uint64 FactorWeightProperties(uint64 inprops);
uint64 InvertProperties(uint64 inprops);
uint64 ProjectProperties(uint64 inprops, bool project_input);
uint64 RandGenProperties(uint64 inprops, bool weighted);
uint64 RelabelProperties(uint64 inprops);
uint64 ReplaceProperties(const vector<uint64>& inprops,
                         ssize_t root,
                         bool epsilon_on_replace,
                         bool no_empty_fst);
uint64 ReverseProperties(uint64 inprops);
uint64 ReweightProperties(uint64 inprops);
uint64 RmEpsilonProperties(uint64 inprops, bool delayed = false);
uint64 ShortestPathProperties(uint64 props);
uint64 SynchronizeProperties(uint64 inprops);
uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed = false);

// Definitions of inlined functions.

uint64 SetStartProperties(uint64 inprops) {
  uint64 outprops = inprops & kSetStartProperties;
  if (inprops & kAcyclic) {
    outprops |= kInitialAcyclic;
  }
  return outprops;
}

uint64 AddStateProperties(uint64 inprops) {
  return inprops & kAddStateProperties;
}

uint64 DeleteStatesProperties(uint64 inprops) {
  return inprops & kDeleteStatesProperties;
}

uint64 DeleteAllStatesProperties(uint64 inprops, uint64 staticprops) {
  uint64 outprops = inprops & kError;
  return outprops | kNullProperties | staticprops;
}

uint64 DeleteArcsProperties(uint64 inprops) {
  return inprops & kDeleteArcsProperties;
}

// Definitions of template functions.

//
template <typename Weight>
uint64 SetFinalProperties(uint64 inprops, Weight old_weight,
                          Weight new_weight) {
  uint64 outprops = inprops;
  if (old_weight != Weight::Zero() && old_weight != Weight::One()) {
    outprops &= ~kWeighted;
  }
  if (new_weight != Weight::Zero() && new_weight != Weight::One()) {
    outprops |= kWeighted;
    outprops &= ~kUnweighted;
  }
  outprops &= kSetFinalProperties | kWeighted | kUnweighted;
  return outprops;
}

/// Gets the properties for the MutableFst::AddArc method.
///
/// \param inprops  the current properties of the fst
/// \param s        the id of the state to which an arc is being added
/// \param arc      the arc being added to the state with the specified id
/// \param prev_arc the previously-added (or "last") arc of state s, or NULL if
///                 s currently has no arcs
template <typename A>
uint64 AddArcProperties(uint64 inprops, typename A::StateId s,
                        const A &arc, const A *prev_arc) {
  uint64 outprops = inprops;
  if (arc.ilabel != arc.olabel) {
    outprops |= kNotAcceptor;
    outprops &= ~kAcceptor;
  }
  if (arc.ilabel == 0) {
    outprops |= kIEpsilons;
    outprops &= ~kNoIEpsilons;
    if (arc.olabel == 0) {
      outprops |= kEpsilons;
      outprops &= ~kNoEpsilons;
    }
  }
  if (arc.olabel == 0) {
    outprops |= kOEpsilons;
    outprops &= ~kNoOEpsilons;
  }
  if (prev_arc != 0) {
    if (prev_arc->ilabel > arc.ilabel) {
      outprops |= kNotILabelSorted;
      outprops &= ~kILabelSorted;
    }
    if (prev_arc->olabel > arc.olabel) {
      outprops |= kNotOLabelSorted;
      outprops &= ~kOLabelSorted;
    }
  }
  if (arc.weight != A::Weight::Zero() && arc.weight != A::Weight::One()) {
    outprops |= kWeighted;
    outprops &= ~kUnweighted;
  }
  if (arc.nextstate <= s) {
    outprops |= kNotTopSorted;
    outprops &= ~kTopSorted;
  }
  outprops &= kAddArcProperties | kAcceptor |
              kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
              kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted;
  if (outprops & kTopSorted) {
    outprops |= kAcyclic | kInitialAcyclic;
  }
  return outprops;
}

extern const char *PropertyNames[];

}  // namespace fst

#endif  // FST_LIB_PROPERTIES_H__