// 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_