1 /* GRAPHITE2 LICENSING
2
3 Copyright 2011, SIL International
4 All rights reserved.
5
6 This library is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as published
8 by the Free Software Foundation; either version 2.1 of License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should also have received a copy of the GNU Lesser General Public
17 License along with this library in the file named "LICENSE".
18 If not, write to the Free Software Foundation, 51 Franklin Street,
19 Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
20 internet at http://www.fsf.org/licenses/lgpl.html.
21
22 Alternatively, the contents of this file may be used under the terms of the
23 Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
24 License, as published by the Free Software Foundation, either version 2
25 of the License or (at your option) any later version.
26 */
27
28 #pragma once
29
30 #include "inc/Code.h"
31 #include "inc/Slot.h"
32
33 namespace graphite2 {
34
35 struct Rule {
36 const vm::Machine::Code * constraint,
37 * action;
38 unsigned short sort;
39 byte preContext;
40 #ifndef NDEBUG
41 uint16 rule_idx;
42 #endif
43
44 Rule();
~RuleRule45 ~Rule() {}
46
47 CLASS_NEW_DELETE;
48
49 private:
50 Rule(const Rule &);
51 Rule & operator = (const Rule &);
52 };
53
54 inline
Rule()55 Rule::Rule()
56 : constraint(0),
57 action(0),
58 sort(0),
59 preContext(0)
60 {
61 #ifndef NDEBUG
62 rule_idx = 0;
63 #endif
64 }
65
66
67 struct RuleEntry
68 {
69 const Rule * rule;
70
71 inline
72 bool operator < (const RuleEntry &r) const
73 {
74 const unsigned short lsort = rule->sort, rsort = r.rule->sort;
75 return lsort > rsort || (lsort == rsort && rule < r.rule);
76 }
77
78 inline
79 bool operator == (const RuleEntry &r) const
80 {
81 return rule == r.rule;
82 }
83 };
84
85
86 struct State
87 {
88 const RuleEntry * rules,
89 * rules_end;
90
91 bool empty() const;
92 };
93
94 inline
empty()95 bool State::empty() const
96 {
97 return rules_end == rules;
98 }
99
100
101 class SlotMap
102 {
103 public:
104 enum {MAX_SLOTS=64};
105 SlotMap(Segment & seg, uint8 direction, size_t maxSize);
106
107 Slot * * begin();
108 Slot * * end();
109 size_t size() const;
110 unsigned short context() const;
111 void reset(Slot &, unsigned short);
112
113 Slot * const & operator[](int n) const;
114 Slot * & operator [] (int);
115 void pushSlot(Slot * const slot);
116 void collectGarbage(Slot *& aSlot);
117
highwater()118 Slot * highwater() { return m_highwater; }
highwater(Slot * s)119 void highwater(Slot *s) { m_highwater = s; m_highpassed = false; }
highpassed()120 bool highpassed() const { return m_highpassed; }
highpassed(bool v)121 void highpassed(bool v) { m_highpassed = v; }
122
dir()123 uint8 dir() const { return m_dir; }
decMax()124 int decMax() { return --m_maxSize; }
125
126 Segment & segment;
127 private:
128 Slot * m_slot_map[MAX_SLOTS+1];
129 unsigned short m_size;
130 unsigned short m_precontext;
131 Slot * m_highwater;
132 int m_maxSize;
133 uint8 m_dir;
134 bool m_highpassed;
135 };
136
137
138 class FiniteStateMachine
139 {
140 public:
141 enum {MAX_RULES=128};
142
143 private:
144 class Rules
145 {
146 public:
147 Rules();
148 void clear();
149 const RuleEntry * begin() const;
150 const RuleEntry * end() const;
151 size_t size() const;
152
153 void accumulate_rules(const State &state);
154
155 private:
156 RuleEntry * m_begin,
157 * m_end,
158 m_rules[MAX_RULES*2];
159 };
160
161 public:
162 FiniteStateMachine(SlotMap & map, json * logger);
163 void reset(Slot * & slot, const short unsigned int max_pre_ctxt);
164
165 Rules rules;
166 SlotMap & slots;
167 json * const dbgout;
168 };
169
170
171 inline
FiniteStateMachine(SlotMap & map,json * logger)172 FiniteStateMachine::FiniteStateMachine(SlotMap& map, json * logger)
173 : slots(map),
174 dbgout(logger)
175 {
176 }
177
178 inline
reset(Slot * & slot,const short unsigned int max_pre_ctxt)179 void FiniteStateMachine::reset(Slot * & slot, const short unsigned int max_pre_ctxt)
180 {
181 rules.clear();
182 int ctxt = 0;
183 for (; ctxt != max_pre_ctxt && slot->prev(); ++ctxt, slot = slot->prev());
184 slots.reset(*slot, ctxt);
185 }
186
187 inline
Rules()188 FiniteStateMachine::Rules::Rules()
189 : m_begin(m_rules), m_end(m_rules)
190 {
191 }
192
193 inline
clear()194 void FiniteStateMachine::Rules::clear()
195 {
196 m_end = m_begin;
197 }
198
199 inline
begin()200 const RuleEntry * FiniteStateMachine::Rules::begin() const
201 {
202 return m_begin;
203 }
204
205 inline
end()206 const RuleEntry * FiniteStateMachine::Rules::end() const
207 {
208 return m_end;
209 }
210
211 inline
size()212 size_t FiniteStateMachine::Rules::size() const
213 {
214 return m_end - m_begin;
215 }
216
217 inline
accumulate_rules(const State & state)218 void FiniteStateMachine::Rules::accumulate_rules(const State &state)
219 {
220 // Only bother if there are rules in the State object.
221 if (state.empty()) return;
222
223 // Merge the new sorted rules list into the current sorted result set.
224 const RuleEntry * lre = begin(), * rre = state.rules;
225 RuleEntry * out = m_rules + (m_begin == m_rules)*MAX_RULES;
226 const RuleEntry * const lrend = out + MAX_RULES,
227 * const rrend = state.rules_end;
228 m_begin = out;
229 while (lre != end() && out != lrend)
230 {
231 if (*lre < *rre) *out++ = *lre++;
232 else if (*rre < *lre) { *out++ = *rre++; }
233 else { *out++ = *lre++; ++rre; }
234
235 if (rre == rrend)
236 {
237 while (lre != end() && out != lrend) { *out++ = *lre++; }
238 m_end = out;
239 return;
240 }
241 }
242 while (rre != rrend && out != lrend) { *out++ = *rre++; }
243 m_end = out;
244 }
245
246 inline
SlotMap(Segment & seg,uint8 direction,size_t maxSize)247 SlotMap::SlotMap(Segment & seg, uint8 direction, size_t maxSize)
248 : segment(seg), m_size(0), m_precontext(0), m_highwater(0),
249 m_maxSize(int(maxSize)), m_dir(direction), m_highpassed(false)
250 {
251 m_slot_map[0] = 0;
252 }
253
254 inline
begin()255 Slot * * SlotMap::begin()
256 {
257 return &m_slot_map[1]; // allow map to go 1 before slot_map when inserting
258 // at start of segment.
259 }
260
261 inline
end()262 Slot * * SlotMap::end()
263 {
264 return m_slot_map + m_size + 1;
265 }
266
267 inline
size()268 size_t SlotMap::size() const
269 {
270 return m_size;
271 }
272
273 inline
context()274 short unsigned int SlotMap::context() const
275 {
276 return m_precontext;
277 }
278
279 inline
reset(Slot & slot,short unsigned int ctxt)280 void SlotMap::reset(Slot & slot, short unsigned int ctxt)
281 {
282 m_size = 0;
283 m_precontext = ctxt;
284 *m_slot_map = slot.prev();
285 }
286
287 inline
pushSlot(Slot * const slot)288 void SlotMap::pushSlot(Slot*const slot)
289 {
290 m_slot_map[++m_size] = slot;
291 }
292
293 inline
294 Slot * const & SlotMap::operator[](int n) const
295 {
296 return m_slot_map[n + 1];
297 }
298
299 inline
300 Slot * & SlotMap::operator[](int n)
301 {
302 return m_slot_map[n + 1];
303 }
304
305 } // namespace graphite2
306