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