Home | History | Annotate | Download | only in lib 
      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.
     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.
     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.
     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.
     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.
    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.
    115 uint64 DifferenceProperties(uint64 inprops1, uint64 inprops2) {
    116   return IntersectProperties(inprops1, ComplementProperties(inprops2));
    117 }
    118 
    119 // Properties for factored weight FST.
    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.
    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.
    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.
    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.
    232 uint64 ReplaceProperties(const vector<uint64>& inprops) {
    233   return 0;
    234 }
    235 
    236 // Properties for a relabeled FST.
    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)
    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.
    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.
    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.
    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.
    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