1// 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// \file
16// FST property bits.
17
18#ifndef FST_LIB_PROPERTIES_H__
19#define FST_LIB_PROPERTIES_H__
20
21#include "fst/lib/compat.h"
22
23namespace fst {
24
25// The property bits here assert facts about an FST. If individual
26// bits are added, then the composite properties below, the property
27// functions and property names in properties.cc, and
28// TestProperties() in test-properties.h should be updated.
29
30//
31// BINARY PROPERTIES
32//
33// For each property below, there is a single bit. If it is set,
34// the property is true. If it is not set, the property is false.
35//
36
37// The Fst is an ExpandedFst
38const uint64 kExpanded =          0x0000000000000001ULL;
39
40// The Fst is a MutableFst
41const uint64 kMutable =           0x0000000000000002ULL;
42
43//
44// TRINARY PROPERTIES
45//
46// For each of these properties below there is a pair of property bits
47// - one positive and one negative. If the positive bit is set, the
48// property is true. If the negative bit is set, the property is
49// false. If neither is set, the property has unknown value. Both
50// should never be simultaneously set. The individual positive and
51// negative bit pairs should be adjacent with the positive bit
52// at an odd and lower position.
53
54// ilabel == olabel for each arc
55const uint64 kAcceptor =          0x0000000000010000ULL;
56// ilabel != olabel for some arc
57const uint64 kNotAcceptor =       0x0000000000020000ULL;
58
59// ilabels unique leaving each state
60const uint64 kIDeterministic =    0x0000000000040000ULL;
61// ilabels not unique leaving some state
62const uint64 kNonIDeterministic = 0x0000000000080000ULL;
63
64// olabels unique leaving each state
65const uint64 kODeterministic =    0x0000000000100000ULL;
66// olabels not unique leaving some state
67const uint64 kNonODeterministic = 0x0000000000200000ULL;
68
69// FST has input/output epsilons
70const uint64 kEpsilons =          0x0000000000400000ULL;
71// FST has no input/output epsilons
72const uint64 kNoEpsilons =        0x0000000000800000ULL;
73
74// FST has input epsilons
75const uint64 kIEpsilons =         0x0000000001000000ULL;
76// FST has no input epsilons
77const uint64 kNoIEpsilons =       0x0000000002000000ULL;
78
79// FST has output epsilons
80const uint64 kOEpsilons =         0x0000000004000000ULL;
81// FST has no output epsilons
82const uint64 kNoOEpsilons =       0x0000000008000000ULL;
83
84// ilabels sorted wrt < for each state
85const uint64 kILabelSorted =      0x0000000010000000ULL;
86// ilabels not sorted wrt < for some state
87const uint64 kNotILabelSorted =   0x0000000020000000ULL;
88
89// olabels sorted wrt < for each state
90const uint64 kOLabelSorted =      0x0000000040000000ULL;
91// olabels not sorted wrt < for some state
92const uint64 kNotOLabelSorted =   0x0000000080000000ULL;
93
94// Non-trivial arc or final weights
95const uint64 kWeighted =          0x0000000100000000ULL;
96// Only trivial arc and final weights
97const uint64 kUnweighted =        0x0000000200000000ULL;
98
99// FST has cycles
100const uint64 kCyclic =            0x0000000400000000ULL;
101// FST has no cycles
102const uint64 kAcyclic =           0x0000000800000000ULL;
103
104// FST has cycles containing the initial state
105const uint64 kInitialCyclic =     0x0000001000000000ULL;
106// FST has no cycles containing the initial state
107const uint64 kInitialAcyclic =    0x0000002000000000ULL;
108
109// FST is topologically sorted
110const uint64 kTopSorted =         0x0000004000000000ULL;
111// FST is not topologically sorted
112const uint64 kNotTopSorted =      0x0000008000000000ULL;
113
114// All states reachable from the initial state
115const uint64 kAccessible =        0x0000010000000000ULL;
116// Not all states reachable from the initial state
117const uint64 kNotAccessible =     0x0000020000000000ULL;
118
119// All states can reach a final state
120const uint64 kCoAccessible =      0x0000040000000000ULL;
121// Not all states can reach a final state
122const uint64 kNotCoAccessible =   0x0000080000000000ULL;
123
124// If NumStates() > 0, then state 0 is initial, state NumStates()-1 is
125// final, there is a transition from each non-final state i to
126// state i+1, and there are no other transitions.
127const uint64 kString =            0x0000100000000000ULL;
128
129// Not a string FST
130const uint64 kNotString =         0x0000200000000000ULL;
131
132//
133// COMPOSITE PROPERTIES
134//
135
136// Properties of an empty machine
137
138const uint64 kNullProperties
139  = kAcceptor | kIDeterministic | kODeterministic | kNoEpsilons |
140    kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted |
141    kUnweighted | kAcyclic | kInitialAcyclic | kTopSorted |
142    kAccessible | kCoAccessible | kString;
143
144// Properties that are preserved when an FST is copied
145const uint64 kCopyProperties
146  = kAcceptor | kNotAcceptor | kIDeterministic | kNonIDeterministic |
147    kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
148    kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
149    kILabelSorted | kNotILabelSorted | kOLabelSorted |
150    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
151    kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
152    kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
153    kString | kNotString;
154
155// Properties that are preserved when an FST start state is set
156const uint64 kSetStartProperties
157  = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
158    kNonIDeterministic | kODeterministic | kNonODeterministic |
159    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
160    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
161    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
162    kTopSorted | kNotTopSorted | kCoAccessible | kNotCoAccessible;
163
164// Properties that are preserved when an FST final weight is set
165const uint64 kSetFinalProperties
166  = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
167    kNonIDeterministic | kODeterministic | kNonODeterministic |
168    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
169    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
170    kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic |
171    kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
172    kNotAccessible;
173
174// Properties that are preserved when an FST state is added
175const uint64 kAddStateProperties
176  = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
177    kNonIDeterministic | kODeterministic | kNonODeterministic |
178    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
179    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
180    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
181    kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
182    kNotAccessible | kNotCoAccessible | kNotString;
183
184// Properties that are preserved when an FST arc is added
185const uint64 kAddArcProperties = kExpanded | kMutable | kNotAcceptor |
186    kNonIDeterministic | kNonODeterministic | kEpsilons | kIEpsilons |
187    kOEpsilons | kNotILabelSorted | kNotOLabelSorted | kWeighted |
188    kCyclic | kInitialCyclic | kNotTopSorted | kAccessible | kCoAccessible;
189
190// Properties that are preserved when an FST arc is set
191const uint64 kSetArcProperties = kExpanded | kMutable;
192
193// Properties that are preserved when FST states are deleted
194const uint64 kDeleteStatesProperties
195  = kExpanded | kMutable | kAcceptor | kIDeterministic |
196    kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
197    kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
198    kInitialAcyclic | kTopSorted;
199
200// Properties that are preserved when FST arcs are deleted
201const uint64 kDeleteArcsProperties
202  = kExpanded | kMutable | kAcceptor | kIDeterministic |
203    kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
204    kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
205    kInitialAcyclic | kTopSorted |  kNotAccessible | kNotCoAccessible;
206
207// Properties that are preserved when an FST's states are reordered
208const uint64 kStateSortProperties = kExpanded | kMutable | kAcceptor |
209  kNotAcceptor | kIDeterministic | kNonIDeterministic |
210  kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
211  kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
212  kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted
213  | kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
214  kInitialAcyclic | kAccessible | kNotAccessible | kCoAccessible |
215  kNotCoAccessible;
216
217// Properties that are preserved when an FST's arcs are reordered
218const uint64 kArcSortProperties =
219  kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
220  kNonIDeterministic | kODeterministic | kNonODeterministic |
221  kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
222  kNoOEpsilons | kWeighted | kUnweighted | kCyclic | kAcyclic |
223  kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
224  kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
225  kString | kNotString;
226
227// Properties that are preserved when an FST's input labels are changed.
228const uint64 kILabelInvariantProperties =
229  kExpanded | kMutable | kODeterministic | kNonODeterministic |
230  kOEpsilons | kNoOEpsilons | kOLabelSorted | kNotOLabelSorted |
231  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
232  kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
233  kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString;
234
235// Properties that are preserved when an FST's output labels are changed.
236const uint64 kOLabelInvariantProperties =
237  kExpanded | kMutable | kIDeterministic | kNonIDeterministic |
238  kIEpsilons | kNoIEpsilons | kILabelSorted | kNotILabelSorted |
239  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
240  kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
241  kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString;
242
243// Properties that are preserved when an FST's weights are changed.
244// This assumes that the set of states that are non-final is not changed.
245const uint64 kWeightInvariantProperties =
246  kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
247  kNonIDeterministic | kODeterministic | kNonODeterministic |
248  kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
249  kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
250  kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
251  kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
252  kNotCoAccessible | kString | kNotString;
253
254// Properties that are preserved when a superfinal state is added
255// and an FSTs final weights are directed to it via new transitions.
256const uint64 kAddSuperFinalProperties  = kExpanded | kMutable | kAcceptor |
257  kNotAcceptor | kNonIDeterministic | kNonODeterministic | kEpsilons |
258  kIEpsilons | kOEpsilons | kNotILabelSorted | kNotOLabelSorted |
259  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
260  kInitialAcyclic | kNotTopSorted | kNotAccessible | kCoAccessible |
261  kNotCoAccessible | kNotString;
262
263// Properties that are preserved when a superfinal state is removed
264// and the epsilon transitions directed to it are made final weights.
265const uint64 kRmSuperFinalProperties  = kExpanded | kMutable | kAcceptor |
266  kNotAcceptor | kIDeterministic | kODeterministic | kNoEpsilons |
267  kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted |
268  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
269  kInitialAcyclic | kTopSorted | kAccessible | kCoAccessible |
270  kNotCoAccessible | kString;
271
272// All binary properties
273const uint64 kBinaryProperties =  0x0000000000000003ULL;
274
275// All trinary properties
276const uint64 kTrinaryProperties = 0x00003fffffff0000ULL;
277
278//
279// COMPUTED PROPERTIES
280//
281
282// 1st bit of trinary properties
283const uint64 kPosTrinaryProperties =
284  kTrinaryProperties & 0x5555555555555555ULL;
285
286// 2nd bit of trinary properties
287const uint64 kNegTrinaryProperties =
288  kTrinaryProperties & 0xaaaaaaaaaaaaaaaaULL;
289
290// All properties
291const uint64 kFstProperties = kBinaryProperties | kTrinaryProperties;
292
293//
294// PROPERTY FUNCTIONS and STRING NAMES (defined in properties.cc)
295//
296
297uint64 ClosureProperties(uint64 inprops, bool star, bool delayed = false);
298uint64 ComplementProperties(uint64 inprops);
299uint64 ComposeProperties(uint64 inprops1, uint64 inprops2);
300uint64 ConcatProperties(uint64 inprops1, uint64 inprops2,
301                        bool delayed = false);
302uint64 DeterminizeProperties(uint64 inprops);
303uint64 DifferenceProperties(uint64 inprops1, uint64 inprops2);
304uint64 FactorWeightProperties(uint64 inprops);
305uint64 IntersectProperties(uint64 inprops1, uint64 inprops2);
306uint64 InvertProperties(uint64 inprops);
307uint64 ProjectProperties(uint64 inprops, bool project_input);
308uint64 RelabelProperties(uint64 inprops);
309uint64 ReplaceProperties(const vector<uint64>& inprops);
310uint64 ReverseProperties(uint64 inprops);
311uint64 ReweightProperties(uint64 inprops);
312uint64 RmEpsilonProperties(uint64 inprops, bool delayed = false);
313uint64 SynchronizeProperties(uint64 inprops);
314uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed = false);
315
316extern const char *PropertyNames[];
317
318}  // namespace fst
319
320#endif  // FST_LIB_PROPERTIES_H__
321