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  explicit FstTester(F *testfst) : testfst_(testfst) { }
55
56  ~FstTester() {
57    delete testfst_;
58  }
59
60  // This verifies the contents described in InitFst() using
61  // methods defined in a generic Fst.
62  template <class G>
63  void TestBase(const G &fst) const {
64    CHECK(Verify(fst));
65    CHECK_EQ(fst.Start(), 0);
66    StateId ns = 0;
67    StateIterator<G> siter(fst);
68    Matcher<G> matcher(fst, MATCH_INPUT);
69    MatchType match_type = matcher.Type(true);
70    for (; !siter.Done(); siter.Next()) {}
71    for (siter.Reset(); !siter.Done(); siter.Next()) {
72      StateId s = siter.Value();
73      matcher.SetState(s);
74      CHECK_EQ(fst.Final(s), NthWeight(s));
75      size_t na = 0;
76      ArcIterator<G> aiter(fst, s);
77      for (; !aiter.Done(); aiter.Next()) {}
78      for (aiter.Reset(); !aiter.Done(); aiter.Next()) {
79        ++na;
80        const Arc &arc = aiter.Value();
81        CHECK_EQ(arc.ilabel, na);
82        CHECK_EQ(arc.olabel, 0);
83        CHECK_EQ(arc.weight, NthWeight(na));
84        CHECK_EQ(arc.nextstate, s);
85        if (match_type == MATCH_INPUT) {
86          CHECK(matcher.Find(arc.ilabel));
87          CHECK_EQ(matcher.Value().ilabel, arc.ilabel);
88        }
89      }
90      CHECK_EQ(na, s);
91      CHECK_EQ(na, aiter.Position());
92      CHECK_EQ(fst.NumArcs(s), s);
93      CHECK_EQ(fst.NumInputEpsilons(s),  0);
94      CHECK_EQ(fst.NumOutputEpsilons(s), s);
95      CHECK(!matcher.Find(s + 1));                 // out-of-range
96      CHECK(!matcher.Find(kNoLabel));              // no explicit epsilons
97      CHECK(matcher.Find(0));
98      CHECK_EQ(matcher.Value().ilabel, kNoLabel);  // implicit epsilon loop
99      ++ns;
100    }
101    CHECK(fst.Properties(kNotAcceptor, true));
102    CHECK(fst.Properties(kOEpsilons, true));
103  }
104
105  void TestBase() const {
106    TestBase(*testfst_);
107  }
108
109  // This verifies methods specfic to an ExpandedFst.
110  template <class G>
111  void TestExpanded(const G &fst) const {
112    StateId ns = 0;
113    for (StateIterator<G> siter(fst);
114         !siter.Done();
115         siter.Next()) {
116      ++ns;
117    }
118    CHECK_EQ(fst.NumStates(), ns);
119    CHECK(fst.Properties(kExpanded, false));
120  }
121
122  void TestExpanded() const { TestExpanded(*testfst_); }
123
124  // This verifies methods specific to a MutableFst.
125  template <class G>
126  void TestMutable(G *fst) const {
127    for (StateIterator<G> siter(*fst);
128         !siter.Done();
129         siter.Next()) {
130      StateId s = siter.Value();
131      size_t na = 0;
132      size_t ni = fst->NumInputEpsilons(s);
133      MutableArcIterator<G> aiter(fst, s);
134      for (; !aiter.Done(); aiter.Next()) {}
135      for (aiter.Reset(); !aiter.Done(); aiter.Next()) {
136        ++na;
137        Arc arc = aiter.Value();
138        arc.ilabel = 0;
139        aiter.SetValue(arc);
140        arc = aiter.Value();
141        CHECK_EQ(arc.ilabel, 0);
142        CHECK_EQ(fst->NumInputEpsilons(s), ni + 1);
143        arc.ilabel = na;
144        aiter.SetValue(arc);
145        CHECK_EQ(fst->NumInputEpsilons(s), ni);
146      }
147    }
148
149    G *cfst1 = fst->Copy();
150    cfst1->DeleteStates();
151    CHECK_EQ(cfst1->NumStates(), 0);
152    delete cfst1;
153
154    G *cfst2 = fst->Copy();
155    for (StateIterator<G> siter(*cfst2);
156         !siter.Done();
157         siter.Next()) {
158      StateId s = siter.Value();
159      cfst2->DeleteArcs(s);
160      CHECK_EQ(cfst2->NumArcs(s), 0);
161      CHECK_EQ(cfst2->NumInputEpsilons(s), 0);
162      CHECK_EQ(cfst2->NumOutputEpsilons(s), 0);
163    }
164    delete cfst2;
165  }
166
167  void TestMutable() { TestMutable(testfst_); }
168
169  // This verifies the copy methods.
170  template <class G>
171  void TestAssign(G *fst) const {
172    // Assignment from G
173    G afst1;
174    afst1 = *fst;
175    CHECK(Equal(*fst, afst1));
176
177    // Assignment from Fst
178    G afst2;
179    afst2 = *static_cast<const Fst<Arc> *>(fst);
180    CHECK(Equal(*fst, afst2));
181
182    // Assignment from self
183    afst2.operator=(afst2);
184    CHECK(Equal(*fst, afst2));
185  }
186
187  void TestAssign() { TestAssign(testfst_); }
188
189  // This verifies the copy methods.
190  template <class G>
191  void TestCopy(const G &fst) const {
192    // Copy from G
193    G c1fst(fst);
194    TestBase(c1fst);
195
196    // Copy from Fst
197    const G c2fst(static_cast<const Fst<Arc> &>(fst));
198    TestBase(c2fst);
199
200    // Copy from self
201    const G *c3fst = fst.Copy();
202    TestBase(*c3fst);
203    delete c3fst;
204  }
205
206  void TestCopy() const { TestCopy(*testfst_); }
207
208  // This verifies the read/write methods.
209  template <class G>
210  void TestIO(const G &fst) const {
211    const string filename = FLAGS_tmpdir + "/test.fst";
212    const string aligned = FLAGS_tmpdir + "/aligned.fst";
213    {
214      // write/read
215      CHECK(fst.Write(filename));
216      G *ffst = G::Read(filename);
217      CHECK(ffst);
218      TestBase(*ffst);
219      delete ffst;
220    }
221
222    {
223      // generic read/cast/test
224      Fst<Arc> *gfst = Fst<Arc>::Read(filename);
225      CHECK(gfst);
226      G *dfst = static_cast<G *>(gfst);
227      TestBase(*dfst);
228
229      // generic write/read/test
230      CHECK(gfst->Write(filename));
231      Fst<Arc> *hfst = Fst<Arc>::Read(filename);
232      CHECK(hfst);
233      TestBase(*hfst);
234      delete gfst;
235      delete hfst;
236    }
237
238    {
239      // check mmaping by first writing the file with the aligned attribute set
240      {
241        ofstream ostr(aligned.c_str());
242        FstWriteOptions opts;
243        opts.source = aligned;
244        opts.align = true;
245        CHECK(fst.Write(ostr, opts));
246      }
247      ifstream istr(aligned.c_str());
248      FstReadOptions opts;
249      opts.mode = FstReadOptions::ReadMode("map");
250      opts.source = aligned;
251      G *gfst = G::Read(istr, opts);
252      CHECK(gfst);
253      TestBase(*gfst);
254      delete gfst;
255    }
256
257    // check mmaping of unaligned files to make sure it does not fail.
258    {
259      {
260        ofstream ostr(aligned.c_str());
261        FstWriteOptions opts;
262        opts.source = aligned;
263        opts.align = false;
264        CHECK(fst.Write(ostr, opts));
265      }
266      ifstream istr(aligned.c_str());
267      FstReadOptions opts;
268      opts.mode = FstReadOptions::ReadMode("map");
269      opts.source = aligned;
270      G *gfst = G::Read(istr, opts);
271      CHECK(gfst);
272      TestBase(*gfst);
273      delete gfst;
274    }
275
276    // expanded write/read/test
277    if (fst.Properties(kExpanded, false)) {
278      ExpandedFst<Arc> *efst = ExpandedFst<Arc>::Read(filename);
279      CHECK(efst);
280      TestBase(*efst);
281      TestExpanded(*efst);
282      delete efst;
283    }
284
285    // mutable write/read/test
286    if (fst.Properties(kMutable, false)) {
287      MutableFst<Arc> *mfst = MutableFst<Arc>::Read(filename);
288      CHECK(mfst);
289      TestBase(*mfst);
290      TestExpanded(*mfst);
291      TestMutable(mfst);
292      delete mfst;
293    }
294  }
295
296  void TestIO() const { TestIO(*testfst_); }
297
298 private:
299  // This constructs test FSTs. Given a mutable FST, will leave
300  // the FST as follows:
301  // (I) NumStates() = nstates
302  // (II) Start() = 0
303  // (III) Final(s) =  NthWeight(s)
304  // (IV) For state s:
305  //     (a) NumArcs(s) == s
306  //     (b) For ith arc of s:
307  //         (1) ilabel = i
308  //         (2) olabel = 0
309  //         (3) weight = NthWeight(i)
310  //         (4) nextstate = s
311  void InitFst(MutableFst<Arc> *fst, size_t nstates) const {
312    fst->DeleteStates();
313    CHECK_GT(nstates, 0);
314
315    for (StateId s = 0; s < nstates; ++s) {
316      fst->AddState();
317      fst->SetFinal(s, NthWeight(s));
318      for (size_t i = 1; i <= s; ++i) {
319        Arc arc(i, 0, NthWeight(i), s);
320        fst->AddArc(s, arc);
321      }
322    }
323
324    fst->SetStart(0);
325  }
326
327  // Generates One() + ... + One() (n times)
328  Weight NthWeight(int n) const {
329    Weight w = Weight::Zero();
330    for (int i = 0; i < n; ++i)
331      w = Plus(w, Weight::One());
332    return w;
333  }
334
335  F *testfst_;   // what we're testing
336};
337
338}  // namespace fst
339
340#endif  // FST_TEST_FST_TEST_H_
341