1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/graphite2/src/inc/Rule.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,293 @@
1.4 +/* GRAPHITE2 LICENSING
1.5 +
1.6 + Copyright 2011, SIL International
1.7 + All rights reserved.
1.8 +
1.9 + This library is free software; you can redistribute it and/or modify
1.10 + it under the terms of the GNU Lesser General Public License as published
1.11 + by the Free Software Foundation; either version 2.1 of License, or
1.12 + (at your option) any later version.
1.13 +
1.14 + This program is distributed in the hope that it will be useful,
1.15 + but WITHOUT ANY WARRANTY; without even the implied warranty of
1.16 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1.17 + Lesser General Public License for more details.
1.18 +
1.19 + You should also have received a copy of the GNU Lesser General Public
1.20 + License along with this library in the file named "LICENSE".
1.21 + If not, write to the Free Software Foundation, 51 Franklin Street,
1.22 + Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
1.23 + internet at http://www.fsf.org/licenses/lgpl.html.
1.24 +
1.25 +Alternatively, the contents of this file may be used under the terms of the
1.26 +Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
1.27 +License, as published by the Free Software Foundation, either version 2
1.28 +of the License or (at your option) any later version.
1.29 +*/
1.30 +
1.31 +#pragma once
1.32 +
1.33 +#include "inc/Code.h"
1.34 +#include "inc/Slot.h"
1.35 +
1.36 +namespace graphite2 {
1.37 +
1.38 +struct Rule {
1.39 + const vm::Machine::Code * constraint,
1.40 + * action;
1.41 + unsigned short sort;
1.42 + byte preContext;
1.43 +#ifndef NDEBUG
1.44 + uint16 rule_idx;
1.45 +#endif
1.46 +
1.47 + Rule() : constraint(0), action(0), sort(0), preContext(0) {}
1.48 + ~Rule();
1.49 +
1.50 + CLASS_NEW_DELETE;
1.51 +
1.52 +private:
1.53 + Rule(const Rule &);
1.54 + Rule & operator = (const Rule &);
1.55 +};
1.56 +
1.57 +inline Rule::~Rule()
1.58 +{
1.59 + delete constraint;
1.60 + delete action;
1.61 +}
1.62 +
1.63 +
1.64 +struct RuleEntry
1.65 +{
1.66 + const Rule * rule;
1.67 +
1.68 + inline
1.69 + bool operator < (const RuleEntry &r) const
1.70 + {
1.71 + const unsigned short lsort = rule->sort, rsort = r.rule->sort;
1.72 + return lsort > rsort || (lsort == rsort && rule < r.rule);
1.73 + }
1.74 +
1.75 + inline
1.76 + bool operator == (const RuleEntry &r) const
1.77 + {
1.78 + return rule == r.rule;
1.79 + }
1.80 +};
1.81 +
1.82 +
1.83 +struct State
1.84 +{
1.85 + const RuleEntry * rules,
1.86 + * rules_end;
1.87 +
1.88 + bool empty() const;
1.89 +};
1.90 +
1.91 +inline
1.92 +bool State::empty() const
1.93 +{
1.94 + return rules_end == rules;
1.95 +}
1.96 +
1.97 +
1.98 +class SlotMap
1.99 +{
1.100 +public:
1.101 + enum {MAX_SLOTS=64};
1.102 + SlotMap(Segment & seg);
1.103 +
1.104 + Slot * * begin();
1.105 + Slot * * end();
1.106 + size_t size() const;
1.107 + unsigned short context() const;
1.108 + void reset(Slot &, unsigned short);
1.109 +
1.110 + Slot * const & operator[](int n) const;
1.111 + Slot * & operator [] (int);
1.112 + void pushSlot(Slot * const slot);
1.113 + void collectGarbage();
1.114 +
1.115 + Slot * highwater() { return m_highwater; }
1.116 + void highwater(Slot *s) { m_highwater = s; m_highpassed = false; }
1.117 + bool highpassed() const { return m_highpassed; }
1.118 + void highpassed(bool v) { m_highpassed = v; }
1.119 +
1.120 + Segment & segment;
1.121 +private:
1.122 + Slot * m_slot_map[MAX_SLOTS+1];
1.123 + unsigned short m_size;
1.124 + unsigned short m_precontext;
1.125 + Slot * m_highwater;
1.126 + bool m_highpassed;
1.127 +};
1.128 +
1.129 +
1.130 +class FiniteStateMachine
1.131 +{
1.132 +public:
1.133 + enum {MAX_RULES=128};
1.134 +
1.135 +private:
1.136 + class Rules
1.137 + {
1.138 + public:
1.139 + Rules();
1.140 + void clear();
1.141 + const RuleEntry * begin() const;
1.142 + const RuleEntry * end() const;
1.143 + size_t size() const;
1.144 +
1.145 + void accumulate_rules(const State &state);
1.146 +
1.147 + private:
1.148 + RuleEntry * m_begin,
1.149 + * m_end,
1.150 + m_rules[MAX_RULES*2];
1.151 + };
1.152 +
1.153 +public:
1.154 + FiniteStateMachine(SlotMap & map, json * logger);
1.155 + void reset(Slot * & slot, const short unsigned int max_pre_ctxt);
1.156 +
1.157 + Rules rules;
1.158 + SlotMap & slots;
1.159 + json * const dbgout;
1.160 +};
1.161 +
1.162 +
1.163 +inline
1.164 +FiniteStateMachine::FiniteStateMachine(SlotMap& map, json * logger)
1.165 +: slots(map),
1.166 + dbgout(logger)
1.167 +{
1.168 +}
1.169 +
1.170 +inline
1.171 +void FiniteStateMachine::reset(Slot * & slot, const short unsigned int max_pre_ctxt)
1.172 +{
1.173 + rules.clear();
1.174 + int ctxt = 0;
1.175 + for (; ctxt != max_pre_ctxt && slot->prev(); ++ctxt, slot = slot->prev());
1.176 + slots.reset(*slot, ctxt);
1.177 +}
1.178 +
1.179 +inline
1.180 +FiniteStateMachine::Rules::Rules()
1.181 + : m_begin(m_rules), m_end(m_rules)
1.182 +{
1.183 +}
1.184 +
1.185 +inline
1.186 +void FiniteStateMachine::Rules::clear()
1.187 +{
1.188 + m_end = m_begin;
1.189 +}
1.190 +
1.191 +inline
1.192 +const RuleEntry * FiniteStateMachine::Rules::begin() const
1.193 +{
1.194 + return m_begin;
1.195 +}
1.196 +
1.197 +inline
1.198 +const RuleEntry * FiniteStateMachine::Rules::end() const
1.199 +{
1.200 + return m_end;
1.201 +}
1.202 +
1.203 +inline
1.204 +size_t FiniteStateMachine::Rules::size() const
1.205 +{
1.206 + return m_end - m_begin;
1.207 +}
1.208 +
1.209 +inline
1.210 +void FiniteStateMachine::Rules::accumulate_rules(const State &state)
1.211 +{
1.212 + // Only bother if there are rules in the State object.
1.213 + if (state.empty()) return;
1.214 +
1.215 + // Merge the new sorted rules list into the current sorted result set.
1.216 + const RuleEntry * lre = begin(), * rre = state.rules;
1.217 + RuleEntry * out = m_rules + (m_begin == m_rules)*MAX_RULES;
1.218 + const RuleEntry * const lrend = out + MAX_RULES,
1.219 + * const rrend = state.rules_end;
1.220 + m_begin = out;
1.221 + while (lre != end() && out != lrend)
1.222 + {
1.223 + if (*lre < *rre) *out++ = *lre++;
1.224 + else if (*rre < *lre) { *out++ = *rre++; }
1.225 + else { *out++ = *lre++; ++rre; }
1.226 +
1.227 + if (rre == rrend)
1.228 + {
1.229 + while (lre != end() && out != lrend) { *out++ = *lre++; }
1.230 + m_end = out;
1.231 + return;
1.232 + }
1.233 + }
1.234 + while (rre != rrend && out != lrend) { *out++ = *rre++; }
1.235 + m_end = out;
1.236 +}
1.237 +
1.238 +inline
1.239 +SlotMap::SlotMap(Segment & seg)
1.240 +: segment(seg), m_size(0), m_precontext(0), m_highwater(0), m_highpassed(false)
1.241 +{
1.242 + m_slot_map[0] = 0;
1.243 +}
1.244 +
1.245 +inline
1.246 +Slot * * SlotMap::begin()
1.247 +{
1.248 + return &m_slot_map[1]; // allow map to go 1 before slot_map when inserting
1.249 + // at start of segment.
1.250 +}
1.251 +
1.252 +inline
1.253 +Slot * * SlotMap::end()
1.254 +{
1.255 + return m_slot_map + m_size + 1;
1.256 +}
1.257 +
1.258 +inline
1.259 +size_t SlotMap::size() const
1.260 +{
1.261 + return m_size;
1.262 +}
1.263 +
1.264 +inline
1.265 +short unsigned int SlotMap::context() const
1.266 +{
1.267 + return m_precontext;
1.268 +}
1.269 +
1.270 +inline
1.271 +void SlotMap::reset(Slot & slot, short unsigned int ctxt)
1.272 +{
1.273 + m_size = 0;
1.274 + m_precontext = ctxt;
1.275 + *m_slot_map = slot.prev();
1.276 +}
1.277 +
1.278 +inline
1.279 +void SlotMap::pushSlot(Slot*const slot)
1.280 +{
1.281 + m_slot_map[++m_size] = slot;
1.282 +}
1.283 +
1.284 +inline
1.285 +Slot * const & SlotMap::operator[](int n) const
1.286 +{
1.287 + return m_slot_map[n + 1];
1.288 +}
1.289 +
1.290 +inline
1.291 +Slot * & SlotMap::operator[](int n)
1.292 +{
1.293 + return m_slot_map[n + 1];
1.294 +}
1.295 +
1.296 +} // namespace graphite2
