Line data Source code
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();
45 0 : ~Rule() {}
46 :
47 0 : CLASS_NEW_DELETE;
48 :
49 : private:
50 : Rule(const Rule &);
51 : Rule & operator = (const Rule &);
52 : };
53 :
54 : inline
55 0 : Rule::Rule()
56 : : constraint(0),
57 : action(0),
58 : sort(0),
59 0 : preContext(0)
60 : {
61 : #ifndef NDEBUG
62 0 : rule_idx = 0;
63 : #endif
64 0 : }
65 :
66 :
67 : struct RuleEntry
68 : {
69 : const Rule * rule;
70 :
71 : inline
72 0 : bool operator < (const RuleEntry &r) const
73 : {
74 0 : const unsigned short lsort = rule->sort, rsort = r.rule->sort;
75 0 : 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
95 0 : bool State::empty() const
96 : {
97 0 : return rules_end == rules;
98 : }
99 :
100 :
101 : class SlotMap
102 : {
103 : public:
104 : enum {MAX_SLOTS=64};
105 : SlotMap(Segment & seg, uint8 direction, int 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 :
118 0 : Slot * highwater() { return m_highwater; }
119 0 : void highwater(Slot *s) { m_highwater = s; m_highpassed = false; }
120 0 : bool highpassed() const { return m_highpassed; }
121 0 : void highpassed(bool v) { m_highpassed = v; }
122 :
123 0 : uint8 dir() const { return m_dir; }
124 0 : 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
172 0 : FiniteStateMachine::FiniteStateMachine(SlotMap& map, json * logger)
173 : : slots(map),
174 0 : dbgout(logger)
175 : {
176 0 : }
177 :
178 : inline
179 0 : void FiniteStateMachine::reset(Slot * & slot, const short unsigned int max_pre_ctxt)
180 : {
181 0 : rules.clear();
182 0 : int ctxt = 0;
183 0 : for (; ctxt != max_pre_ctxt && slot->prev(); ++ctxt, slot = slot->prev());
184 0 : slots.reset(*slot, ctxt);
185 0 : }
186 :
187 : inline
188 0 : FiniteStateMachine::Rules::Rules()
189 0 : : m_begin(m_rules), m_end(m_rules)
190 : {
191 0 : }
192 :
193 : inline
194 0 : void FiniteStateMachine::Rules::clear()
195 : {
196 0 : m_end = m_begin;
197 0 : }
198 :
199 : inline
200 0 : const RuleEntry * FiniteStateMachine::Rules::begin() const
201 : {
202 0 : return m_begin;
203 : }
204 :
205 : inline
206 0 : const RuleEntry * FiniteStateMachine::Rules::end() const
207 : {
208 0 : return m_end;
209 : }
210 :
211 : inline
212 : size_t FiniteStateMachine::Rules::size() const
213 : {
214 : return m_end - m_begin;
215 : }
216 :
217 : inline
218 0 : void FiniteStateMachine::Rules::accumulate_rules(const State &state)
219 : {
220 : // Only bother if there are rules in the State object.
221 0 : if (state.empty()) return;
222 :
223 : // Merge the new sorted rules list into the current sorted result set.
224 0 : const RuleEntry * lre = begin(), * rre = state.rules;
225 0 : RuleEntry * out = m_rules + (m_begin == m_rules)*MAX_RULES;
226 0 : const RuleEntry * const lrend = out + MAX_RULES,
227 0 : * const rrend = state.rules_end;
228 0 : m_begin = out;
229 0 : while (lre != end() && out != lrend)
230 : {
231 0 : if (*lre < *rre) *out++ = *lre++;
232 0 : else if (*rre < *lre) { *out++ = *rre++; }
233 0 : else { *out++ = *lre++; ++rre; }
234 :
235 0 : if (rre == rrend)
236 : {
237 0 : while (lre != end() && out != lrend) { *out++ = *lre++; }
238 0 : m_end = out;
239 0 : return;
240 : }
241 : }
242 0 : while (rre != rrend && out != lrend) { *out++ = *rre++; }
243 0 : m_end = out;
244 : }
245 :
246 : inline
247 0 : SlotMap::SlotMap(Segment & seg, uint8 direction, int maxSize)
248 : : segment(seg), m_size(0), m_precontext(0), m_highwater(0),
249 0 : m_maxSize(maxSize), m_dir(direction), m_highpassed(false)
250 : {
251 0 : m_slot_map[0] = 0;
252 0 : }
253 :
254 : inline
255 0 : Slot * * SlotMap::begin()
256 : {
257 0 : return &m_slot_map[1]; // allow map to go 1 before slot_map when inserting
258 : // at start of segment.
259 : }
260 :
261 : inline
262 0 : Slot * * SlotMap::end()
263 : {
264 0 : return m_slot_map + m_size + 1;
265 : }
266 :
267 : inline
268 0 : size_t SlotMap::size() const
269 : {
270 0 : return m_size;
271 : }
272 :
273 : inline
274 0 : short unsigned int SlotMap::context() const
275 : {
276 0 : return m_precontext;
277 : }
278 :
279 : inline
280 0 : void SlotMap::reset(Slot & slot, short unsigned int ctxt)
281 : {
282 0 : m_size = 0;
283 0 : m_precontext = ctxt;
284 0 : *m_slot_map = slot.prev();
285 0 : }
286 :
287 : inline
288 0 : void SlotMap::pushSlot(Slot*const slot)
289 : {
290 0 : m_slot_map[++m_size] = slot;
291 0 : }
292 :
293 : inline
294 0 : Slot * const & SlotMap::operator[](int n) const
295 : {
296 0 : return m_slot_map[n + 1];
297 : }
298 :
299 : inline
300 0 : Slot * & SlotMap::operator[](int n)
301 : {
302 0 : return m_slot_map[n + 1];
303 : }
304 :
305 : } // namespace graphite2
|
