1// fst_test.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// Copyright 2005-2010 Google, Inc.
16// Author: riley@google.com (Michael Riley)
17//
18// \file
19// Regression test for FST classes.
20
21#ifndef FST_TEST_FST_TEST_H_
22#define FST_TEST_FST_TEST_H_
23
24#include <fst/equal.h>
25#include <fst/matcher.h>
26#include <fst/vector-fst.h>
27#include <fst/verify.h>
28
29DECLARE_string(tmpdir);
30
31namespace fst {
32
33// This tests an Fst F that is assumed to have a copy method from an
34// arbitrary Fst. Some test functions make further assumptions mostly
35// obvious from their name. These tests are written as member temple
36// functions that take a test fst as its argument so that different
37// Fsts in the interface hierarchy can be tested separately and so
38// that we can instantiate only those tests that make sense for a
39// particular Fst.
40template <class F>
41class FstTester {
42 public:
43  typedef typename F::Arc Arc;
44  typedef typename Arc::StateId StateId;
45  typedef typename Arc::Weight Weight;
46  typedef typename Arc::Label Label;
47
48  FstTester() {
49    VectorFst<Arc> vfst;
50    InitFst(&vfst, 128);
51    testfst_ = new F(vfst);
52  }
53
54  ~FstTester() {
55    delete testfst_;
56  }
57
58  // This verifies the contents described in InitFst() using
59  // methods defined in a generic Fst.
60  template <class G>
61  void TestBase(const G &fst) const {
62    CHECK(Verify(fst));
63    CHECK_EQ(fst.Start(), 0);
64    StateId ns = 0;
65    StateIterator<G> siter(fst);
66    Matcher<G> matcher(fst, MATCH_INPUT);
67    MatchType match_type = matcher.Type(true);
68    for (; !siter.Done(); siter.Next());
69    for (siter.Reset(); !siter.Done(); siter.Next()) {
70      StateId s = siter.Value();
71      matcher.SetState(s);
72      CHECK_EQ(fst.Final(s), NthWeight(s));
73      size_t na = 0;
74      ArcIterator<G> aiter(fst, s);
75      for (; !aiter.Done(); aiter.Next());
76      for (aiter.Reset(); !aiter.Done(); aiter.Next()) {
77        ++na;
78        const Arc &arc = aiter.Value();
79        CHECK_EQ(arc.ilabel, na);
80        CHECK_EQ(arc.olabel, 0);
81        CHECK_EQ(arc.weight, NthWeight(na));
82        CHECK_EQ(arc.nextstate, s);
83        if (match_type == MATCH_INPUT) {
84          CHECK(matcher.Find(arc.ilabel));
85          CHECK_EQ(matcher.Value().ilabel, arc.ilabel);
86        }
87      }
88      CHECK_EQ(na, s);
89      CHECK_EQ(na, aiter.Position());
90      CHECK_EQ(fst.NumArcs(s), s);
91      CHECK_EQ(fst.NumInputEpsilons(s),  0);
92      CHECK_EQ(fst.NumOutputEpsilons(s), s);
93      CHECK(!matcher.Find(s + 1));                 // out-of-range
94      CHECK(!matcher.Find(kNoLabel));              // no explicit epsilons
95      CHECK(matcher.Find(0));
96      CHECK_EQ(matcher.Value().ilabel, kNoLabel);  // implicit epsilon loop
97      ++ns;
98    }
99    CHECK(fst.Properties(kNotAcceptor, true));
100    CHECK(fst.Properties(kOEpsilons, true));
101  }
102
103  void TestBase() const {
104    TestBase(*testfst_);
105  }
106
107  // This verifies methods specfic to an ExpandedFst.
108  template <class G>
109  void TestExpanded(const G &fst) const {
110    StateId ns = 0;
111    for (StateIterator<G> siter(fst);
112         !siter.Done();
113         siter.Next()) {
114      ++ns;
115    }
116    CHECK_EQ(fst.NumStates(), ns);
117    CHECK(fst.Properties(kExpanded, false));
118  }
119
120  void TestExpanded() const { TestExpanded(*testfst_); }
121
122  // This verifies methods specific to a MutableFst.
123  template <class G>
124  void TestMutable(G *fst) const {
125    for (StateIterator<G> siter(*fst);
126         !siter.Done();
127         siter.Next()) {
128      StateId s = siter.Value();
129      size_t na = 0;
130      size_t ni = fst->NumInputEpsilons(s);
131      MutableArcIterator<G> aiter(fst, s);
132      for (; !aiter.Done(); aiter.Next());
133      for (aiter.Reset(); !aiter.Done(); aiter.Next()) {
134        ++na;
135        Arc arc = aiter.Value();
136        arc.ilabel = 0;
137        aiter.SetValue(arc);
138        arc = aiter.Value();
139        CHECK_EQ(arc.ilabel, 0);
140        CHECK_EQ(fst->NumInputEpsilons(s), ni + 1);
141        arc.ilabel = na;
142        aiter.SetValue(arc);
143        CHECK_EQ(fst->NumInputEpsilons(s), ni);
144      }
145    }
146
147    G *cfst1 = fst->Copy();
148    cfst1->DeleteStates();
149    CHECK_EQ(cfst1->NumStates(), 0);
150    delete cfst1;
151
152    G *cfst2 = fst->Copy();
153    for (StateIterator<G> siter(*cfst2);
154         !siter.Done();
155         siter.Next()) {
156      StateId s = siter.Value();
157      cfst2->DeleteArcs(s);
158      CHECK_EQ(cfst2->NumArcs(s), 0);
159      CHECK_EQ(cfst2->NumInputEpsilons(s), 0);
160      CHECK_EQ(cfst2->NumOutputEpsilons(s), 0);
161    }
162    delete cfst2;
163  }
164
165  void TestMutable() { TestMutable(testfst_); }
166
167  // This verifies the copy methods.
168  template <class G>
169  void TestAssign(G *fst) const {
170    // Assignment from G
171    G afst1;
172    afst1 = *fst;
173    CHECK(Equal(*fst, afst1));
174
175    // Assignment from Fst
176    G afst2;
177    afst2 = *static_cast<const Fst<Arc> *>(fst);
178    CHECK(Equal(*fst, afst2));
179
180    // Assignment from self
181    afst2.operator=(afst2);
182    CHECK(Equal(*fst, afst2));
183  }
184
185  void TestAssign() { TestAssign(testfst_); }
186
187  // This verifies the copy methods.
188  template <class G>
189  void TestCopy(const G &fst) const {
190    // Copy from G
191    G c1fst(fst);
192    TestBase(c1fst);
193
194    // Copy from Fst
195    const G c2fst(static_cast<const Fst<Arc> &>(fst));
196    TestBase(c2fst);
197
198    // Copy from self
199    const G *c3fst = fst.Copy();
200    TestBase(*c3fst);
201    delete c3fst;
202  }
203
204  void TestCopy() const { TestCopy(*testfst_); }
205
206  // This verifies the read/write methods.
207  template <class G>
208  void TestIO(const G &fst) const {
209    const string filename = FLAGS_tmpdir + "/test.fst";
210    {
211      // write/read
212      CHECK(fst.Write(filename));
213      G *ffst = G::Read(filename);
214      CHECK(ffst);
215      TestBase(*ffst);
216      delete ffst;
217    }
218
219    {
220      // generic read/cast/test
221      Fst<Arc> *gfst = Fst<Arc>::Read(filename);
222      CHECK(gfst);
223      G *dfst = static_cast<G *>(gfst);
224      TestBase(*dfst);
225
226      // generic write/read/test
227      CHECK(gfst->Write(filename));
228      Fst<Arc> *hfst = Fst<Arc>::Read(filename);
229      CHECK(hfst);
230      TestBase(*hfst);
231      delete gfst;
232      delete hfst;
233    }
234
235    // expanded write/read/test
236    if (fst.Properties(kExpanded, false)) {
237      ExpandedFst<Arc> *efst = ExpandedFst<Arc>::Read(filename);
238      CHECK(efst);
239      TestBase(*efst);
240      TestExpanded(*efst);
241      delete efst;
242    }
243
244    // mutable write/read/test
245    if (fst.Properties(kMutable, false)) {
246      MutableFst<Arc> *mfst = MutableFst<Arc>::Read(filename);
247      CHECK(mfst);
248      TestBase(*mfst);
249      TestExpanded(*mfst);
250      TestMutable(mfst);
251      delete mfst;
252    }
253  }
254
255  void TestIO() const { TestIO(*testfst_); }
256
257 private:
258  // This constructs test FSTs. Given a mutable FST, will leave
259  // the FST as follows:
260  // (I) NumStates() = nstates
261  // (II) Start() = 0
262  // (III) Final(s) =  NthWeight(s)
263  // (IV) For state s:
264  //     (a) NumArcs(s) == s
265  //     (b) For ith arc of s:
266  //         (1) ilabel = i
267  //         (2) olabel = 0
268  //         (3) weight = NthWeight(i)
269  //         (4) nextstate = s
270  void InitFst(MutableFst<Arc> *fst, size_t nstates) const {
271    fst->DeleteStates();
272    CHECK_GT(nstates, 0);
273
274    for (StateId s = 0; s < nstates; ++s) {
275      fst->AddState();
276      fst->SetFinal(s, NthWeight(s));
277      for (size_t i = 1; i <= s; ++i) {
278        Arc arc(i, 0, NthWeight(i), s);
279        fst->AddArc(s, arc);
280      }
281    }
282
283    fst->SetStart(0);
284  }
285
286  // Generates One() + ... + One() (n times)
287  Weight NthWeight(int n) const {
288    Weight w = Weight::Zero();
289    for (int i = 0; i < n; ++i)
290      w = Plus(w, Weight::One());
291    return w;
292  }
293
294  F *testfst_;   // what we're testing
295};
296
297}  // namespace fst
298
299#endif  // FST_TEST_FST_TEST_H_
300