properties.h revision 8fc5a7f51e62cb4ae44a27bdf4176d04adc80ede
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