1// properties.cc
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//
16// \file
17// Functions for updating property bits for various FST operations and
18// string names of the properties.
19
20#include <vector>
21
22#include "fst/lib/properties.h"
23
24namespace fst {
25
26// These functions determine the properties associated with the FST
27// result of various finite-state operations. The property arguments
28// correspond to the operation's FST arguments. The properties
29// returned assume the operation modifies its first argument.
30// Bitwise-and this result with kCopyProperties for the case when a
31// new (possibly delayed) FST is instead constructed.
32
33// Properties for a concatenatively-closed FST.
34uint64 ClosureProperties(uint64 inprops, bool star, bool delayed) {
35  uint64 outprops = (kAcceptor | kUnweighted | kAccessible) & inprops;
36  if (!delayed)
37       outprops |= (kExpanded | kMutable | kCoAccessible |
38                    kNotTopSorted | kNotString) & inprops;
39  if (!delayed || inprops & kAccessible)
40    outprops |= (kNotAcceptor | kNonIDeterministic | kNonODeterministic |
41                 kNotILabelSorted | kNotOLabelSorted | kWeighted |
42                 kNotAccessible | kNotCoAccessible) & inprops;
43  return outprops;
44}
45
46// Properties for a complemented FST.
47uint64 ComplementProperties(uint64 inprops) {
48  uint64 outprops = kAcceptor | kUnweighted | kNoEpsilons |
49                    kNoIEpsilons | kNoOEpsilons |
50                    kIDeterministic | kODeterministic | kAccessible;
51  outprops |= (kILabelSorted | kOLabelSorted | kInitialCyclic) & inprops;
52  if (inprops & kAccessible)
53    outprops |= kNotILabelSorted | kNotOLabelSorted | kCyclic;
54  return outprops;
55}
56
57// Properties for a composed FST.
58uint64 ComposeProperties(uint64 inprops1, uint64 inprops2) {
59  uint64 outprops = kAccessible;
60  outprops |= (kAcceptor | kNoIEpsilons | kAcyclic | kInitialAcyclic) &
61              inprops1 & inprops2;
62  if ((kNoIEpsilons & inprops1 & inprops2)) {
63    outprops |= kIDeterministic & inprops1 & inprops2;
64  }
65  return outprops;
66}
67
68// Properties for a concatenated FST.
69uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, bool delayed) {
70  uint64 outprops =
71    (kAcceptor | kUnweighted | kAcyclic) & inprops1 & inprops2;
72
73  bool empty1 = delayed;  // Can fst1 be the empty machine?
74  bool empty2 = delayed;  // Can fst2 be the empty machine?
75
76  if (!delayed) {
77    outprops |= (kExpanded | kMutable | kNotTopSorted | kNotString) & inprops1;
78    outprops |= (kNotTopSorted | kNotString) & inprops2;
79  }
80  if (!empty1)
81    outprops |= (kInitialAcyclic | kInitialCyclic) & inprops1;
82  if (!delayed || inprops1 & kAccessible)
83    outprops |= (kNotAcceptor | kNonIDeterministic | kNonODeterministic |
84                 kEpsilons | kIEpsilons | kOEpsilons | kNotILabelSorted |
85                 kNotOLabelSorted | kWeighted | kCyclic |
86                 kNotAccessible | kNotCoAccessible) & inprops1;
87  if ((inprops1 & (kAccessible | kCoAccessible)) ==
88      (kAccessible | kCoAccessible) && !empty1) {
89    outprops |= kAccessible & inprops2;
90    if (!empty2)
91      outprops |= kCoAccessible & inprops2;
92    if (!delayed || inprops2 & kAccessible)
93      outprops |= (kNotAcceptor | kNonIDeterministic | kNonODeterministic |
94                   kEpsilons | kIEpsilons | kOEpsilons | kNotILabelSorted |
95                   kNotOLabelSorted | kWeighted | kCyclic |
96                   kNotAccessible | kNotCoAccessible) & inprops2;
97  }
98  return outprops;
99}
100
101// Properties for a determinized FST.
102uint64 DeterminizeProperties(uint64 inprops) {
103  uint64 outprops = kIDeterministic | kAccessible;
104  outprops |= (kAcceptor | kNoEpsilons | kAcyclic |
105               kInitialAcyclic | kCoAccessible | kString) & inprops;
106  if (inprops & kAccessible)
107     outprops |= (kNotAcceptor | kEpsilons | kIEpsilons | kOEpsilons |
108                  kCyclic) & inprops;
109  if (inprops & kAcceptor)
110    outprops |= (kNoIEpsilons | kNoOEpsilons | kAccessible) & inprops;
111  return outprops;
112}
113
114// Properties for a differenced FST.
115uint64 DifferenceProperties(uint64 inprops1, uint64 inprops2) {
116  return IntersectProperties(inprops1, ComplementProperties(inprops2));
117}
118
119// Properties for factored weight FST.
120uint64 FactorWeightProperties(uint64 inprops) {
121  uint64 outprops = (kExpanded | kMutable | kAcceptor |
122                     kAcyclic | kAccessible | kCoAccessible) & inprops;
123  if (inprops & kAccessible)
124    outprops |= (kNotAcceptor | kNonIDeterministic | kNonODeterministic |
125                 kEpsilons | kIEpsilons | kOEpsilons | kCyclic |
126                 kNotILabelSorted | kNotOLabelSorted)
127        & inprops;
128  return outprops;
129}
130
131// Properties for an intersected FST.
132uint64 IntersectProperties(uint64 inprops1, uint64 inprops2) {
133  uint64 outprops = kAcceptor | kAccessible;
134
135  outprops |= (kNoEpsilons | kNoIEpsilons | kNoOEpsilons | kAcyclic |
136               kInitialAcyclic) & inprops1 & inprops2;
137
138  if ((kNoIEpsilons & inprops1 & inprops2))
139    outprops |= (kIDeterministic | kODeterministic) & inprops1 & inprops2;
140  return outprops;
141}
142
143// Properties for an inverted FST.
144uint64 InvertProperties(uint64 inprops) {
145  uint64 outprops = (kExpanded | kMutable | kAcceptor | kNotAcceptor |
146                     kEpsilons | kNoEpsilons | kWeighted | kUnweighted |
147                     kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
148                     kTopSorted | kNotTopSorted |
149                     kAccessible | kNotAccessible |
150                     kCoAccessible | kNotCoAccessible |
151                     kString | kNotString) & inprops;
152  if (kIDeterministic & inprops)
153    outprops |= kODeterministic;
154  if (kNonIDeterministic & inprops)
155    outprops |= kNonODeterministic;
156  if (kODeterministic & inprops)
157    outprops |= kIDeterministic;
158  if (kNonODeterministic & inprops)
159    outprops |= kNonIDeterministic;
160
161  if (kIEpsilons & inprops)
162    outprops |= kOEpsilons;
163  if (kNoIEpsilons & inprops)
164    outprops |= kNoOEpsilons;
165  if (kOEpsilons & inprops)
166    outprops |= kIEpsilons;
167  if (kNoOEpsilons & inprops)
168    outprops |= kNoIEpsilons;
169
170  if (kILabelSorted & inprops)
171    outprops |= kOLabelSorted;
172  if (kNotILabelSorted & inprops)
173    outprops |= kNotOLabelSorted;
174  if (kOLabelSorted & inprops)
175    outprops |= kILabelSorted;
176  if (kNotOLabelSorted & inprops)
177    outprops |= kNotILabelSorted;
178  return outprops;
179}
180
181// Properties for a projected FST.
182uint64 ProjectProperties(uint64 inprops, bool project_input) {
183  uint64 outprops = kAcceptor;
184  outprops |= (kExpanded | kMutable | kWeighted | kUnweighted |
185               kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
186               kTopSorted | kNotTopSorted | kAccessible | kNotAccessible |
187               kCoAccessible | kNotCoAccessible |
188               kString | kNotString) & inprops;
189  if (project_input) {
190    outprops |= (kIDeterministic | kNonIDeterministic |
191                 kIEpsilons | kNoIEpsilons |
192                 kILabelSorted | kNotILabelSorted) & inprops;
193
194    if (kIDeterministic & inprops)
195      outprops |= kODeterministic;
196    if (kNonIDeterministic & inprops)
197      outprops |= kNonODeterministic;
198
199    if (kIEpsilons & inprops)
200      outprops |= kOEpsilons | kEpsilons;
201    if (kNoIEpsilons & inprops)
202      outprops |= kNoOEpsilons | kNoEpsilons;
203
204    if (kILabelSorted & inprops)
205      outprops |= kOLabelSorted;
206    if (kNotILabelSorted & inprops)
207      outprops |= kNotOLabelSorted;
208  } else {
209    outprops |= (kODeterministic | kNonODeterministic |
210                 kOEpsilons | kNoOEpsilons |
211                 kOLabelSorted | kNotOLabelSorted) & inprops;
212
213    if (kODeterministic & inprops)
214      outprops |= kIDeterministic;
215    if (kNonODeterministic & inprops)
216      outprops |= kNonIDeterministic;
217
218    if (kOEpsilons & inprops)
219      outprops |= kIEpsilons | kEpsilons;
220    if (kNoOEpsilons & inprops)
221      outprops |= kNoIEpsilons | kNoEpsilons;
222
223    if (kOLabelSorted & inprops)
224      outprops |= kILabelSorted;
225    if (kNotOLabelSorted & inprops)
226      outprops |= kNotILabelSorted;
227  }
228  return outprops;
229}
230
231// Properties for a replace FST.
232uint64 ReplaceProperties(const vector<uint64>& inprops) {
233  return 0;
234}
235
236// Properties for a relabeled FST.
237uint64 RelabelProperties(uint64 inprops) {
238  uint64 outprops = (kExpanded | kMutable |
239                     kWeighted | kUnweighted |
240                     kCyclic | kAcyclic |
241                     kInitialCyclic | kInitialAcyclic |
242                     kTopSorted | kNotTopSorted |
243                     kAccessible | kNotAccessible |
244                     kCoAccessible | kNotCoAccessible |
245                     kString | kNotString) & inprops;
246  return outprops;
247}
248
249// Properties for a reversed FST. (the superinitial state limits this set)
250uint64 ReverseProperties(uint64 inprops) {
251  uint64 outprops =
252    (kExpanded | kMutable | kAcceptor | kNotAcceptor | kEpsilons |
253     kIEpsilons | kOEpsilons | kWeighted | kUnweighted |
254     kCyclic | kAcyclic) & inprops;
255  return outprops;
256}
257
258// Properties for re-weighted FST.
259uint64 ReweightProperties(uint64 inprops) {
260  uint64 outprops = inprops & kWeightInvariantProperties;
261  outprops = outprops & ~kCoAccessible;
262  return outprops;
263}
264
265// Properties for an epsilon-removed FST.
266uint64 RmEpsilonProperties(uint64 inprops, bool delayed) {
267  uint64 outprops = kNoEpsilons;
268  outprops |= (kAcceptor | kAcyclic | kInitialAcyclic) & inprops;
269  if (inprops & kAcceptor)
270    outprops |= kNoIEpsilons | kNoOEpsilons;
271  if (!delayed) {
272    outprops |= kExpanded | kMutable;
273    outprops |= kTopSorted & inprops;
274  }
275  if (!delayed || inprops & kAccessible)
276    outprops |= kNotAcceptor & inprops;
277  return outprops;
278}
279
280// Properties for a synchronized FST.
281uint64 SynchronizeProperties(uint64 inprops) {
282  uint64 outprops = (kAcceptor | kAcyclic | kAccessible | kCoAccessible |
283                     kUnweighted) & inprops;
284  if (inprops & kAccessible)
285    outprops |= (kCyclic | kNotCoAccessible | kWeighted) & inprops;
286  return outprops;
287}
288
289// Properties for a unioned FST.
290uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed) {
291  uint64 outprops = (kAcceptor | kUnweighted | kAcyclic | kAccessible)
292                    & inprops1 & inprops2;
293  bool empty1 = delayed;  // Can fst1 be the empty machine?
294  bool empty2 = delayed;  // Can fst2 be the empty machine?
295  if (!delayed) {
296    outprops |= (kExpanded | kMutable | kNotTopSorted | kNotString) & inprops1;
297    outprops |= (kNotTopSorted | kNotString) & inprops2;
298  }
299  if (!empty1 && !empty2) {
300    outprops |= kEpsilons | kIEpsilons | kOEpsilons;
301    outprops |= kCoAccessible & inprops1 & inprops2;
302  }
303  // Note kNotCoAccessible does not hold because of kInitialAcyclic opt.
304  if (!delayed || inprops1 & kAccessible)
305    outprops |= (kNotAcceptor | kNonIDeterministic | kNonODeterministic |
306                 kEpsilons | kIEpsilons | kOEpsilons | kNotILabelSorted |
307                 kNotOLabelSorted | kWeighted | kCyclic |
308                 kNotAccessible) & inprops1;
309  if (!delayed || inprops2 & kAccessible)
310    outprops |= (kNotAcceptor | kNonIDeterministic | kNonODeterministic |
311                 kEpsilons | kIEpsilons | kOEpsilons | kNotILabelSorted |
312                 kNotOLabelSorted | kWeighted | kCyclic |
313                 kNotAccessible | kNotCoAccessible) & inprops2;
314  return outprops;
315}
316
317// Property string names (indexed by bit position).
318const char *PropertyNames[] = {
319  // binary
320  "expanded", "mutable", "", "", "", "", "", "",
321  "", "", "", "", "", "", "", "",
322  // trinary
323  "acceptor", "not acceptor",
324  "input deterministic", "non input deterministic",
325  "output deterministic", "non output deterministic",
326  "input/output epsilons", "no input/output epsilons",
327  "input epsilons", "no input epsilons",
328  "output epsilons", "no output epsilons",
329  "input label sorted", "not input label sorted",
330  "output label sorted", "not output label sorted",
331  "weighted", "unweighted",
332  "cyclic", "acyclic",
333  "cyclic at initial state", "acyclic at initial state",
334  "top sorted", "not top sorted",
335  "accessible", "not accessible",
336  "coaccessible", "not coaccessible",
337  "string", "not string",
338};
339
340}
341