src/include/fst/properties.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // FST property bits.
   5
   6 #ifndef FST_PROPERTIES_H_
   7 #define FST_PROPERTIES_H_
   8
   9 #include <sys/types.h>
  10 #include <vector>
  11
  12 #include <fst/compat.h>
  13
  14 namespace fst {
  15
  16 // The property bits here assert facts about an FST. If individual bits are
  17 // added, then the composite properties below, the property functions and
  18 // property names in properties.cc, and TestProperties() in test-properties.h
  19 // should be updated.
  20
  21 // BINARY PROPERTIES
  22 //
  23 // For each property below, there is a single bit. If it is set, the property is
  24 // true. If it is not set, the property is false.
  25
  26 // The Fst is an ExpandedFst.
  27 constexpr uint64 kExpanded = 0x0000000000000001ULL;
  28
  29 // The Fst is a MutableFst.
  30 constexpr uint64 kMutable = 0x0000000000000002ULL;
  31
  32 // An error was detected while constructing/using the FST.
  33 constexpr uint64 kError = 0x0000000000000004ULL;
  34
  35 // TRINARY PROPERTIES
  36 //
  37 // For each of these properties below there is a pair of property bits, one
  38 // positive and one negative. If the positive bit is set, the property is true.
  39 // If the negative bit is set, the property is false. If neither is set, the
  40 // property has unknown value. Both should never be simultaneously set. The
  41 // individual positive and negative bit pairs should be adjacent with the
  42 // positive bit at an odd and lower position.
  43
  44 // ilabel == olabel for each arc.
  45 constexpr uint64 kAcceptor = 0x0000000000010000ULL;
  46 // ilabel != olabel for some arc.
  47 constexpr uint64 kNotAcceptor = 0x0000000000020000ULL;
  48
  49 // ilabels unique leaving each state.
  50 constexpr uint64 kIDeterministic = 0x0000000000040000ULL;
  51 // ilabels not unique leaving some state.
  52 constexpr uint64 kNonIDeterministic = 0x0000000000080000ULL;
  53
  54 // olabels unique leaving each state.
  55 constexpr uint64 kODeterministic = 0x0000000000100000ULL;
  56 // olabels not unique leaving some state.
  57 constexpr uint64 kNonODeterministic = 0x0000000000200000ULL;
  58
  59 // FST has input/output epsilons.
  60 constexpr uint64 kEpsilons = 0x0000000000400000ULL;
  61 // FST has no input/output epsilons.
  62 constexpr uint64 kNoEpsilons = 0x0000000000800000ULL;
  63
  64 // FST has input epsilons.
  65 constexpr uint64 kIEpsilons = 0x0000000001000000ULL;
  66 // FST has no input epsilons.
  67 constexpr uint64 kNoIEpsilons = 0x0000000002000000ULL;
  68
  69 // FST has output epsilons.
  70 constexpr uint64 kOEpsilons = 0x0000000004000000ULL;
  71 // FST has no output epsilons.
  72 constexpr uint64 kNoOEpsilons = 0x0000000008000000ULL;
  73
  74 // ilabels sorted wrt < for each state.
  75 constexpr uint64 kILabelSorted = 0x0000000010000000ULL;
  76 // ilabels not sorted wrt < for some state.
  77 constexpr uint64 kNotILabelSorted = 0x0000000020000000ULL;
  78
  79 // olabels sorted wrt < for each state.
  80 constexpr uint64 kOLabelSorted = 0x0000000040000000ULL;
  81 // olabels not sorted wrt < for some state.
  82 constexpr uint64 kNotOLabelSorted = 0x0000000080000000ULL;
  83
  84 // Non-trivial arc or final weights.
  85 constexpr uint64 kWeighted = 0x0000000100000000ULL;
  86 // Only trivial arc and final weights.
  87 constexpr uint64 kUnweighted = 0x0000000200000000ULL;
  88
  89 // FST has cycles.
  90 constexpr uint64 kCyclic = 0x0000000400000000ULL;
  91 // FST has no cycles.
  92 constexpr uint64 kAcyclic = 0x0000000800000000ULL;
  93
  94 // FST has cycles containing the initial state.
  95 constexpr uint64 kInitialCyclic = 0x0000001000000000ULL;
  96 // FST has no cycles containing the initial state.
  97 constexpr uint64 kInitialAcyclic = 0x0000002000000000ULL;
  98
  99 // FST is topologically sorted.
 100 constexpr uint64 kTopSorted = 0x0000004000000000ULL;
 101 // FST is not topologically sorted.
 102 constexpr uint64 kNotTopSorted = 0x0000008000000000ULL;
 103
 104 // All states reachable from the initial state.
 105 constexpr uint64 kAccessible = 0x0000010000000000ULL;
 106 // Not all states reachable from the initial state.
 107 constexpr uint64 kNotAccessible = 0x0000020000000000ULL;
 108
 109 // All states can reach a final state.
 110 constexpr uint64 kCoAccessible = 0x0000040000000000ULL;
 111 // Not all states can reach a final state.
 112 constexpr uint64 kNotCoAccessible = 0x0000080000000000ULL;
 113
 114 // If NumStates() > 0, then state 0 is initial, state NumStates() - 1 is final,
 115 // there is a transition from each non-final state i to state i + 1, and there
 116 // are no other transitions.
 117 constexpr uint64 kString = 0x0000100000000000ULL;
 118
 119 // Not a string FST.
 120 constexpr uint64 kNotString = 0x0000200000000000ULL;
 121
 122 // FST has least one weighted cycle.
 123 constexpr uint64 kWeightedCycles = 0x0000400000000000ULL;
 124
 125 // Only unweighted cycles.
 126 constexpr uint64 kUnweightedCycles = 0x0000800000000000ULL;
 127
 128 // COMPOSITE PROPERTIES
 129
 130 // Properties of an empty machine.
 131 constexpr uint64 kNullProperties =
 132     kAcceptor | kIDeterministic | kODeterministic | kNoEpsilons | kNoIEpsilons |
 133     kNoOEpsilons | kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
 134     kInitialAcyclic | kTopSorted | kAccessible | kCoAccessible | kString |
 135     kUnweightedCycles;
 136
 137 // Properties that are preserved when an FST is copied.
 138 constexpr uint64 kCopyProperties =
 139     kError | kAcceptor | kNotAcceptor | kIDeterministic | kNonIDeterministic |
 140     kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
 141     kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted |
 142     kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kWeighted |
 143     kUnweighted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
 144     kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
 145     kNotCoAccessible | kString | kNotString | kWeightedCycles |
 146     kUnweightedCycles;
 147
 148 // Properties that are intrinsic to the FST.
 149 constexpr uint64 kIntrinsicProperties =
 150     kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
 151     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 152     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 153     kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted |
 154     kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
 155     kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
 156     kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString |
 157     kWeightedCycles | kUnweightedCycles;
 158
 159 // Properties that are (potentially) extrinsic to the FST.
 160 constexpr uint64 kExtrinsicProperties = kError;
 161
 162 // Properties that are preserved when an FST start state is set.
 163 constexpr uint64 kSetStartProperties =
 164     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 165     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 166     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 167     kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted |
 168     kWeighted | kUnweighted | kCyclic | kAcyclic | kTopSorted | kNotTopSorted |
 169     kCoAccessible | kNotCoAccessible | kWeightedCycles | kUnweightedCycles;
 170
 171 // Properties that are preserved when an FST final weight is set.
 172 constexpr uint64 kSetFinalProperties =
 173     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 174     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 175     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 176     kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted |
 177     kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic | kTopSorted |
 178     kNotTopSorted | kAccessible | kNotAccessible | kWeightedCycles |
 179     kUnweightedCycles;
 180
 181 // Properties that are preserved when an FST state is added.
 182 constexpr uint64 kAddStateProperties =
 183     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 184     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 185     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 186     kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted |
 187     kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
 188     kInitialAcyclic | kTopSorted | kNotTopSorted | kNotAccessible |
 189     kNotCoAccessible | kNotString | kWeightedCycles | kUnweightedCycles;
 190
 191 // Properties that are preserved when an FST arc is added.
 192 constexpr uint64 kAddArcProperties =
 193     kExpanded | kMutable | kError | kNotAcceptor | kNonIDeterministic |
 194     kNonODeterministic | kEpsilons | kIEpsilons | kOEpsilons |
 195     kNotILabelSorted | kNotOLabelSorted | kWeighted | kCyclic | kInitialCyclic |
 196     kNotTopSorted | kAccessible | kCoAccessible | kWeightedCycles;
 197
 198 // Properties that are preserved when an FST arc is set.
 199 constexpr uint64 kSetArcProperties = kExpanded | kMutable | kError;
 200
 201 // Properties that are preserved when FST states are deleted.
 202 constexpr uint64 kDeleteStatesProperties =
 203     kExpanded | kMutable | kError | kAcceptor | kIDeterministic |
 204     kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
 205     kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic | kInitialAcyclic |
 206     kTopSorted | kUnweightedCycles;
 207
 208 // Properties that are preserved when FST arcs are deleted.
 209 constexpr uint64 kDeleteArcsProperties =
 210     kExpanded | kMutable | kError | kAcceptor | kIDeterministic |
 211     kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
 212     kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic | kInitialAcyclic |
 213     kTopSorted | kNotAccessible | kNotCoAccessible | kUnweightedCycles;
 214
 215 // Properties that are preserved when an FST's states are reordered.
 216 constexpr uint64 kStateSortProperties =
 217     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 218     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 219     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 220     kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted |
 221     kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
 222     kInitialAcyclic | kAccessible | kNotAccessible | kCoAccessible |
 223     kNotCoAccessible | kWeightedCycles | kUnweightedCycles;
 224
 225 // Properties that are preserved when an FST's arcs are reordered.
 226 constexpr uint64 kArcSortProperties =
 227     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 228     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 229     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 230     kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
 231     kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
 232     kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString |
 233     kWeightedCycles | kUnweightedCycles;
 234
 235 // Properties that are preserved when an FST's input labels are changed.
 236 constexpr uint64 kILabelInvariantProperties =
 237     kExpanded | kMutable | kError | kODeterministic | kNonODeterministic |
 238     kOEpsilons | kNoOEpsilons | kOLabelSorted | kNotOLabelSorted | kWeighted |
 239     kUnweighted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
 240     kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
 241     kNotCoAccessible | kString | kNotString | kWeightedCycles |
 242     kUnweightedCycles;
 243
 244 // Properties that are preserved when an FST's output labels are changed.
 245 constexpr uint64 kOLabelInvariantProperties =
 246     kExpanded | kMutable | kError | kIDeterministic | kNonIDeterministic |
 247     kIEpsilons | kNoIEpsilons | kILabelSorted | kNotILabelSorted | kWeighted |
 248     kUnweighted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
 249     kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
 250     kNotCoAccessible | kString | kNotString | kWeightedCycles |
 251     kUnweightedCycles;
 252
 253 // Properties that are preserved when an FST's weights are changed. This
 254 // assumes that the set of states that are non-final is not changed.
 255 constexpr uint64 kWeightInvariantProperties =
 256     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 257     kNonIDeterministic | kODeterministic | kNonODeterministic | kEpsilons |
 258     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
 259     kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted |
 260     kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic | kTopSorted |
 261     kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
 262     kNotCoAccessible | kString | kNotString;
 263
 264 // Properties that are preserved when a superfinal state is added and an FST's
 265 // final weights are directed to it via new transitions.
 266 constexpr uint64 kAddSuperFinalProperties =
 267     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor |
 268     kNonIDeterministic | kNonODeterministic | kEpsilons | kIEpsilons |
 269     kOEpsilons | kNotILabelSorted | kNotOLabelSorted | kWeighted | kUnweighted |
 270     kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic | kNotTopSorted |
 271     kNotAccessible | kCoAccessible | kNotCoAccessible | kNotString |
 272     kWeightedCycles | kUnweightedCycles;
 273
 274 // Properties that are preserved when a superfinal state is removed and the
 275 // epsilon transitions directed to it are made final weights.
 276 constexpr uint64 kRmSuperFinalProperties =
 277     kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic |
 278     kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
 279     kILabelSorted | kOLabelSorted | kWeighted | kUnweighted | kCyclic |
 280     kAcyclic | kInitialCyclic | kInitialAcyclic | kTopSorted | kAccessible |
 281     kCoAccessible | kNotCoAccessible | kString | kWeightedCycles |
 282     kUnweightedCycles;
 283
 284 // All binary properties.
 285 constexpr uint64 kBinaryProperties = 0x0000000000000007ULL;
 286
 287 // All trinary properties.
 288 constexpr uint64 kTrinaryProperties = 0x0000ffffffff0000ULL;
 289
 290 // COMPUTED PROPERTIES
 291
 292 // 1st bit of trinary properties.
 293 constexpr uint64 kPosTrinaryProperties = kTrinaryProperties &
 294     0x5555555555555555ULL;
 295
 296 // 2nd bit of trinary properties.
 297 constexpr uint64 kNegTrinaryProperties = kTrinaryProperties &
 298     0xaaaaaaaaaaaaaaaaULL;
 299
 300 // All properties.
 301 constexpr uint64 kFstProperties = kBinaryProperties | kTrinaryProperties;
 302
 303 // PROPERTY FUNCTIONS and STRING NAMES (defined in properties.cc).
 304
 305 // Below are functions for getting property bit vectors when executing
 306 // mutation operations.
 307 inline uint64 SetStartProperties(uint64 inprops);
 308
 309 template <typename Weight>
 310 uint64 SetFinalProperties(uint64 inprops, const Weight &old_weight,
 311                           const Weight &new_weight);
 312
 313 inline uint64 AddStateProperties(uint64 inprops);
 314
 315 template <typename A>
 316 uint64 AddArcProperties(uint64 inprops, typename A::StateId s, const A &arc,
 317                         const A *prev_arc);
 318
 319 inline uint64 DeleteStatesProperties(uint64 inprops);
 320
 321 inline uint64 DeleteAllStatesProperties(uint64 inprops, uint64 staticProps);
 322
 323 inline uint64 DeleteArcsProperties(uint64 inprops);
 324
 325 uint64 ClosureProperties(uint64 inprops, bool star, bool delayed = false);
 326
 327 uint64 ComplementProperties(uint64 inprops);
 328
 329 uint64 ComposeProperties(uint64 inprops1, uint64 inprops2);
 330
 331 uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, bool delayed = false);
 332
 333 uint64 DeterminizeProperties(uint64 inprops, bool has_subsequential_label,
 334                              bool distinct_psubsequential_labels);
 335
 336 uint64 FactorWeightProperties(uint64 inprops);
 337
 338 uint64 InvertProperties(uint64 inprops);
 339
 340 uint64 ProjectProperties(uint64 inprops, bool project_input);
 341
 342 uint64 RandGenProperties(uint64 inprops, bool weighted);
 343
 344 uint64 RelabelProperties(uint64 inprops);
 345
 346 uint64 ReplaceProperties(const std::vector<uint64> &inprops, ssize_t root,
 347                          bool epsilon_on_call, bool epsilon_on_return,
 348                          bool out_epsilon_on_call, bool out_epsilon_on_return,
 349                          bool replace_transducer, bool no_empty_fst,
 350                          bool all_ilabel_sorted, bool all_olabel_sorted,
 351                          bool all_negative_or_dense);
 352
 353 uint64 ReverseProperties(uint64 inprops, bool has_superinitial);
 354
 355 uint64 ReweightProperties(uint64 inprops);
 356
 357 uint64 RmEpsilonProperties(uint64 inprops, bool delayed = false);
 358
 359 uint64 ShortestPathProperties(uint64 props, bool tree = false);
 360
 361 uint64 SynchronizeProperties(uint64 inprops);
 362
 363 uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed = false);
 364
 365 // Definitions of inlined functions.
 366
 367 uint64 SetStartProperties(uint64 inprops) {
 368   auto outprops = inprops & kSetStartProperties;
 369   if (inprops & kAcyclic) {
 370     outprops |= kInitialAcyclic;
 371   }
 372   return outprops;
 373 }
 374
 375 uint64 AddStateProperties(uint64 inprops) {
 376   return inprops & kAddStateProperties;
 377 }
 378
 379 uint64 DeleteStatesProperties(uint64 inprops) {
 380   return inprops & kDeleteStatesProperties;
 381 }
 382
 383 uint64 DeleteAllStatesProperties(uint64 inprops, uint64 staticprops) {
 384   const auto outprops = inprops & kError;
 385   return outprops | kNullProperties | staticprops;
 386 }
 387
 388 uint64 DeleteArcsProperties(uint64 inprops) {
 389   return inprops & kDeleteArcsProperties;
 390 }
 391
 392 // Definitions of template functions.
 393
 394 template <typename Weight>
 395 uint64 SetFinalProperties(uint64 inprops, const Weight &old_weight,
 396                           const Weight &new_weight) {
 397   auto outprops = inprops;
 398   if (old_weight != Weight::Zero() && old_weight != Weight::One()) {
 399     outprops &= ~kWeighted;
 400   }
 401   if (new_weight != Weight::Zero() && new_weight != Weight::One()) {
 402     outprops |= kWeighted;
 403     outprops &= ~kUnweighted;
 404   }
 405   outprops &= kSetFinalProperties | kWeighted | kUnweighted;
 406   return outprops;
 407 }
 408
 409 /// Gets the properties for the MutableFst::AddArc method.
 410 ///
 411 /// \param inprops  the current properties of the FST
 412 /// \param s        the ID of the state to which an arc is being added.
 413 /// \param arc      the arc being added to the state with the specified ID
 414 /// \param prev_arc the previously-added (or "last") arc of state s, or nullptr
 415 //                  if s currently has no arcs.
 416 template <typename Arc>
 417 uint64 AddArcProperties(uint64 inprops, typename Arc::StateId s,
 418                         const Arc &arc, const Arc *prev_arc) {
 419   using Weight = typename Arc::Weight;
 420   auto outprops = inprops;
 421   if (arc.ilabel != arc.olabel) {
 422     outprops |= kNotAcceptor;
 423     outprops &= ~kAcceptor;
 424   }
 425   if (arc.ilabel == 0) {
 426     outprops |= kIEpsilons;
 427     outprops &= ~kNoIEpsilons;
 428     if (arc.olabel == 0) {
 429       outprops |= kEpsilons;
 430       outprops &= ~kNoEpsilons;
 431     }
 432   }
 433   if (arc.olabel == 0) {
 434     outprops |= kOEpsilons;
 435     outprops &= ~kNoOEpsilons;
 436   }
 437   if (prev_arc) {
 438     if (prev_arc->ilabel > arc.ilabel) {
 439       outprops |= kNotILabelSorted;
 440       outprops &= ~kILabelSorted;
 441     }
 442     if (prev_arc->olabel > arc.olabel) {
 443       outprops |= kNotOLabelSorted;
 444       outprops &= ~kOLabelSorted;
 445     }
 446   }
 447   if (arc.weight != Weight::Zero() && arc.weight != Weight::One()) {
 448     outprops |= kWeighted;
 449     outprops &= ~kUnweighted;
 450   }
 451   if (arc.nextstate <= s) {
 452     outprops |= kNotTopSorted;
 453     outprops &= ~kTopSorted;
 454   }
 455   outprops &= kAddArcProperties | kAcceptor | kNoEpsilons | kNoIEpsilons |
 456               kNoOEpsilons | kILabelSorted | kOLabelSorted | kUnweighted |
 457               kTopSorted;
 458   if (outprops & kTopSorted) {
 459     outprops |= kAcyclic | kInitialAcyclic;
 460   }
 461   return outprops;
 462 }
 463
 464 extern const char *PropertyNames[];
 465
 466 }  // namespace fst
 467
 468 #endif  // FST_PROPERTIES_H_