FST  openfst-1.8.2.post1
OpenFst Library
mpdt.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
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 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Common classes for Multi Pushdown Transducer (MPDT) expansion/traversal.
19 
20 #ifndef FST_EXTENSIONS_MPDT_MPDT_H_
21 #define FST_EXTENSIONS_MPDT_MPDT_H_
22 
23 #include <algorithm>
24 #include <array>
25 #include <cstdint>
26 #include <functional>
27 #include <map>
28 #include <vector>
29 
30 #include <fst/compat.h>
31 #include <fst/extensions/pdt/pdt.h>
32 #include <unordered_map>
33 #include <optional>
34 
35 namespace fst {
36 
37 enum class MPdtType : uint8_t {
38  READ_RESTRICT, // Can only read from first empty stack
39  WRITE_RESTRICT, // Can only write to first empty stack
40  NO_RESTRICT, // No read-write restrictions
41 };
42 
43 namespace internal {
44 
45 template <typename StackId, typename Level, Level nlevels>
46 using StackConfig = std::array<StackId, nlevels>;
47 
48 // Forward declaration so `KeyPair` can declare `KeyPairHasher` its friend.
49 template <typename Level>
51 
52 // Defines the KeyPair type used as the key to MPdtStack.paren_id_map_. The hash
53 // function is provided as a separate struct to match templating syntax.
54 template <typename Level>
55 class KeyPair {
56  public:
57  KeyPair(Level level, size_t id) : level_(level), underlying_id_(id) {}
58 
59  inline bool operator==(const KeyPair &rhs) const {
60  return level_ == rhs.level_ && underlying_id_ == rhs.underlying_id_;
61  }
62 
63  private:
64  friend KeyPairHasher<Level>;
65  Level level_;
66  size_t underlying_id_;
67 };
68 
69 template <typename Level>
70 struct KeyPairHasher {
71  inline size_t operator()(const KeyPair<Level> &keypair) const {
72  return std::hash<Level>()(keypair.level_) ^
73  (std::hash<size_t>()(keypair.underlying_id_) << 1);
74  }
75 };
76 
77 template <typename StackId, typename Level, Level nlevels = 2,
79 class MPdtStack {
80  public:
81  using Label = Level;
83  using ConfigToStackId = std::map<Config, StackId>;
84 
85  MPdtStack(const std::vector<std::pair<Label, Label>> &parens,
86  const std::vector<Level> &assignments);
87 
88  ~MPdtStack() = default;
89 
90  MPdtStack(const MPdtStack &other)
91  : error_(other.error_),
92  min_paren_(other.min_paren_),
93  max_paren_(other.max_paren_),
94  paren_levels_(other.paren_levels_),
95  parens_(other.parens_),
96  paren_map_(other.paren_map_),
97  paren_id_map_(other.paren_id_map_),
98  config_to_stack_id_map_(other.config_to_stack_id_map_),
99  stack_id_to_config_map_(other.stack_id_to_config_map_),
100  next_stack_id_(other.next_stack_id_),
101  stacks_(other.stacks_) {}
102 
103  MPdtStack &operator=(const MPdtStack &other) {
104  *this = MPdtStack(other);
105  return *this;
106  }
107 
108  MPdtStack(MPdtStack &&) = default;
109 
110  MPdtStack &operator=(MPdtStack &&) = default;
111 
112  StackId Find(StackId stack_id, Label label);
113 
114  // For now we do not implement Pop since this is needed only for
115  // ShortestPath().
116 
117  // For Top we find the first non-empty config, and find the paren ID of that
118  // (or -1) if there is none, then map that to the external stack_id to return.
119  ssize_t Top(StackId stack_id) const {
120  if (stack_id == -1) return -1;
121  const auto config = InternalStackIds(stack_id);
122  Level level = 0;
123  StackId underlying_id = -1;
124  for (; level < nlevels; ++level) {
125  if (!Empty(config, level)) {
126  underlying_id = stacks_[level]->Top(config[level]);
127  break;
128  }
129  }
130  if (underlying_id == -1) return -1;
131  const auto it = paren_id_map_.find(KeyPair<Level>(level, underlying_id));
132  if (it == paren_id_map_.end()) return -1; // NB: shouldn't happen.
133  return it->second;
134  }
135 
136  ssize_t ParenId(Label label) const {
137  const auto it = paren_map_.find(label);
138  return it != paren_map_.end() ? it->second : -1;
139  }
140 
141  bool Error() { return error_; }
142 
143  // Each component stack has an internal stack ID for a given configuration and
144  // label.
145  // This function maps a configuration of those to the stack ID the caller
146  // sees.
147  inline StackId ExternalStackId(const Config &config) {
148  const auto it = config_to_stack_id_map_.find(config);
149  StackId result;
150  if (it == config_to_stack_id_map_.end()) {
151  result = next_stack_id_++;
152  config_to_stack_id_map_.insert(
153  std::pair<Config, StackId>(config, result));
154  stack_id_to_config_map_[result] = config;
155  } else {
156  result = it->second;
157  }
158  return result;
159  }
160 
161  // Retrieves the internal stack ID for a corresponding external stack ID.
162  inline const Config InternalStackIds(StackId stack_id) const {
163  auto it = stack_id_to_config_map_.find(stack_id);
164  if (it == stack_id_to_config_map_.end()) {
165  it = stack_id_to_config_map_.find(-1);
166  }
167  return it->second;
168  }
169 
170  inline bool Empty(const Config &config, Level level) const {
171  return config[level] <= 0;
172  }
173 
174  inline bool AllEmpty(const Config &config) {
175  for (Level level = 0; level < nlevels; ++level) {
176  if (!Empty(config, level)) return false;
177  }
178  return true;
179  }
180 
181  private:
182  bool error_;
183  Label min_paren_;
184  Label max_paren_;
185  // Stores level of each paren.
186  std::unordered_map<Label, Label> paren_levels_;
187  std::vector<std::pair<Label, Label>> parens_; // As in pdt.h.
188  std::unordered_map<Label, size_t> paren_map_; // As in pdt.h.
189  // Maps between internal paren_id and external paren_id.
190  std::unordered_map<KeyPair<Level>, size_t, KeyPairHasher<Level>>
191  paren_id_map_;
192  // Maps between internal stack ids and external stack id.
193  ConfigToStackId config_to_stack_id_map_;
194  std::unordered_map<StackId, Config> stack_id_to_config_map_;
195  StackId next_stack_id_;
196  // Array of stacks.
197  std::array<std::optional<PdtStack<StackId, Label>>, nlevels> stacks_;
198 };
199 
200 template <typename StackId, typename Level, Level nlevels, MPdtType restrict>
202  const std::vector<std::pair<Level, Level>> &parens, // NB: Label = Level.
203  const std::vector<Level> &assignments)
204  : error_(false),
205  min_paren_(kNoLabel),
206  max_paren_(kNoLabel),
207  parens_(parens),
208  next_stack_id_(1) {
209  using Label = Level;
210  if (parens.size() != assignments.size()) {
211  FSTERROR() << "MPdtStack: Parens of different size from assignments";
212  error_ = true;
213  return;
214  }
215  std::array<std::vector<std::pair<Label, Label>>, nlevels> vectors;
216  for (Level i = 0; i < assignments.size(); ++i) {
217  // Assignments here start at 0, so assuming the human-readable version has
218  // them starting at 1, we should subtract 1 here
219  const auto level = assignments[i] - 1;
220  if (level < 0 || level >= nlevels) {
221  FSTERROR() << "MPdtStack: Specified level " << level << " out of bounds";
222  error_ = true;
223  return;
224  }
225  const auto &pair = parens[i];
226  vectors[level].push_back(pair);
227  paren_levels_[pair.first] = level;
228  paren_levels_[pair.second] = level;
229  paren_map_[pair.first] = i;
230  paren_map_[pair.second] = i;
231  const KeyPair<Level> key(level, vectors[level].size() - 1);
232  paren_id_map_[key] = i;
233  if (min_paren_ == kNoLabel || pair.first < min_paren_) {
234  min_paren_ = pair.first;
235  }
236  if (pair.second < min_paren_) min_paren_ = pair.second;
237  if (max_paren_ == kNoLabel || pair.first > max_paren_) {
238  max_paren_ = pair.first;
239  }
240  if (pair.second > max_paren_) max_paren_ = pair.second;
241  }
243  Config neg_one;
244  Config zero;
245  for (Level level = 0; level < nlevels; ++level) {
246  stacks_[level].emplace(vectors[level]);
247  neg_one[level] = -1;
248  zero[level] = 0;
249  }
250  config_to_stack_id_map_[neg_one] = -1;
251  config_to_stack_id_map_[zero] = 0;
252  stack_id_to_config_map_[-1] = neg_one;
253  stack_id_to_config_map_[0] = zero;
254 }
255 
256 template <typename StackId, typename Level, Level nlevels, MPdtType restrict>
258  Level label) {
259  // Non-paren.
260  if (min_paren_ == kNoLabel || label < min_paren_ || label > max_paren_) {
261  return stack_id;
262  }
263  const auto it = paren_map_.find(label);
264  // Non-paren.
265  if (it == paren_map_.end()) return stack_id;
266  ssize_t paren_id = it->second;
267  // Gets the configuration associated with this stack_id.
268  const auto config = InternalStackIds(stack_id);
269  // Gets the level.
270  const auto level = paren_levels_.find(label)->second;
271  // If the label is an open paren we push:
272  //
273  // 1) if the restrict type is not MPdtType::WRITE_RESTRICT, or
274  // 2) the restrict type is MPdtType::WRITE_RESTRICT, and all the stacks above
275  // the level are empty.
276  if (label == parens_[paren_id].first) { // Open paren.
277  if (restrict == MPdtType::WRITE_RESTRICT) {
278  for (Level upper_level = 0; upper_level < level; ++upper_level) {
279  if (!Empty(config, upper_level)) return -1; // Non-empty stack blocks.
280  }
281  }
282  // If the label is an close paren we pop:
283  //
284  // 1) if the restrict type is not MPdtType::READ_RESTRICT, or
285  // 2) the restrict type is MPdtType::READ_RESTRICT, and all the stacks above
286  // the level are empty.
287  } else if (restrict == MPdtType::READ_RESTRICT) {
288  for (Level lower_level = 0; lower_level < level; ++lower_level) {
289  if (!Empty(config, lower_level)) return -1; // Non-empty stack blocks.
290  }
291  }
292  const auto nid = stacks_[level]->Find(config[level], label);
293  // If the new ID is -1, that means that there is no valid transition at the
294  // level we want.
295  if (nid == -1) {
296  return -1;
297  } else {
299  Config nconfig(config);
300  nconfig[level] = nid;
301  return ExternalStackId(nconfig);
302  }
303 }
304 
305 } // namespace internal
306 } // namespace fst
307 
308 #endif // FST_EXTENSIONS_MPDT_MPDT_H_
MPdtStack & operator=(const MPdtStack &other)
Definition: mpdt.h:103
constexpr int kNoLabel
Definition: fst.h:201
MPdtStack(const MPdtStack &other)
Definition: mpdt.h:90
std::array< StackId, nlevels > StackConfig
Definition: mpdt.h:46
ssize_t Top(StackId stack_id) const
Definition: mpdt.h:119
const Config InternalStackIds(StackId stack_id) const
Definition: mpdt.h:162
std::map< Config, StackId > ConfigToStackId
Definition: mpdt.h:83
MPdtType
Definition: mpdt.h:37
StackId ExternalStackId(const Config &config)
Definition: mpdt.h:147
#define FSTERROR()
Definition: util.h:53
bool Empty(const Config &config, Level level) const
Definition: mpdt.h:170
bool operator==(const KeyPair &rhs) const
Definition: mpdt.h:59
KeyPair(Level level, size_t id)
Definition: mpdt.h:57
ssize_t ParenId(Label label) const
Definition: mpdt.h:136
bool AllEmpty(const Config &config)
Definition: mpdt.h:174
StackConfig< StackId, Label, 2 > Config
Definition: mpdt.h:82
size_t operator()(const KeyPair< Level > &keypair) const
Definition: mpdt.h:71
StackId Find(StackId stack_id, Label label)
Definition: mpdt.h:257