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
24 namespace 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.
ClosureProperties(uint64 inprops,bool star,bool delayed)34 uint64 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.
ComplementProperties(uint64 inprops)47 uint64 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.
ComposeProperties(uint64 inprops1,uint64 inprops2)58 uint64 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.
ConcatProperties(uint64 inprops1,uint64 inprops2,bool delayed)69 uint64 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.
DeterminizeProperties(uint64 inprops)102 uint64 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.
DifferenceProperties(uint64 inprops1,uint64 inprops2)115 uint64 DifferenceProperties(uint64 inprops1, uint64 inprops2) {
116 return IntersectProperties(inprops1, ComplementProperties(inprops2));
117 }
118
119 // Properties for factored weight FST.
FactorWeightProperties(uint64 inprops)120 uint64 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.
IntersectProperties(uint64 inprops1,uint64 inprops2)132 uint64 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.
InvertProperties(uint64 inprops)144 uint64 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.
ProjectProperties(uint64 inprops,bool project_input)182 uint64 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.
ReplaceProperties(const vector<uint64> & inprops)232 uint64 ReplaceProperties(const vector<uint64>& inprops) {
233 return 0;
234 }
235
236 // Properties for a relabeled FST.
RelabelProperties(uint64 inprops)237 uint64 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)
ReverseProperties(uint64 inprops)250 uint64 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.
ReweightProperties(uint64 inprops)259 uint64 ReweightProperties(uint64 inprops) {
260 uint64 outprops = inprops & kWeightInvariantProperties;
261 outprops = outprops & ~kCoAccessible;
262 return outprops;
263 }
264
265 // Properties for an epsilon-removed FST.
RmEpsilonProperties(uint64 inprops,bool delayed)266 uint64 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.
SynchronizeProperties(uint64 inprops)281 uint64 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.
UnionProperties(uint64 inprops1,uint64 inprops2,bool delayed)290 uint64 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).
318 const 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