michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2011, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street, 
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the 
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: 
michael@0: #pragma once
michael@0: 
michael@0: #include "inc/Code.h"
michael@0: #include "inc/Slot.h"
michael@0: 
michael@0: namespace graphite2 {
michael@0: 
michael@0: struct Rule {
michael@0:   const vm::Machine::Code * constraint, 
michael@0:                  * action;
michael@0:   unsigned short   sort;
michael@0:   byte             preContext;
michael@0: #ifndef NDEBUG
michael@0:   uint16           rule_idx;
michael@0: #endif
michael@0: 
michael@0:   Rule() : constraint(0), action(0), sort(0), preContext(0) {}
michael@0:   ~Rule();
michael@0: 
michael@0:   CLASS_NEW_DELETE;
michael@0: 
michael@0: private:
michael@0:   Rule(const Rule &);
michael@0:   Rule & operator = (const Rule &);
michael@0: };
michael@0: 
michael@0: inline Rule::~Rule()
michael@0: {
michael@0:   delete constraint;
michael@0:   delete action;
michael@0: }
michael@0: 
michael@0: 
michael@0: struct RuleEntry
michael@0: {
michael@0:   const Rule   * rule;
michael@0: 
michael@0:   inline
michael@0:   bool operator < (const RuleEntry &r) const
michael@0:   {
michael@0:     const unsigned short lsort = rule->sort, rsort = r.rule->sort;
michael@0:     return lsort > rsort || (lsort == rsort && rule < r.rule);
michael@0:   }
michael@0: 
michael@0:   inline
michael@0:   bool operator == (const RuleEntry &r) const
michael@0:   {
michael@0:     return rule == r.rule;
michael@0:   }
michael@0: };
michael@0: 
michael@0: 
michael@0: struct State
michael@0: {
michael@0:   const RuleEntry     * rules,
michael@0:                       * rules_end;
michael@0:   
michael@0:   bool   empty() const;
michael@0: };
michael@0: 
michael@0: inline
michael@0: bool State::empty() const
michael@0: {
michael@0:     return rules_end == rules;
michael@0: }
michael@0: 
michael@0: 
michael@0: class SlotMap
michael@0: {
michael@0: public:
michael@0:   enum {MAX_SLOTS=64};
michael@0:   SlotMap(Segment & seg);
michael@0:   
michael@0:   Slot       * * begin();
michael@0:   Slot       * * end();
michael@0:   size_t         size() const;
michael@0:   unsigned short context() const;
michael@0:   void           reset(Slot &, unsigned short);
michael@0:   
michael@0:   Slot * const & operator[](int n) const;
michael@0:   Slot       * & operator [] (int);
michael@0:   void           pushSlot(Slot * const slot);
michael@0:   void           collectGarbage();
michael@0: 
michael@0:   Slot         * highwater() { return m_highwater; }
michael@0:   void           highwater(Slot *s) { m_highwater = s; m_highpassed = false; }
michael@0:   bool           highpassed() const { return m_highpassed; }
michael@0:   void           highpassed(bool v) { m_highpassed = v; }
michael@0: 
michael@0:   Segment &    segment;
michael@0: private:
michael@0:   Slot         * m_slot_map[MAX_SLOTS+1];
michael@0:   unsigned short m_size;
michael@0:   unsigned short m_precontext;
michael@0:   Slot         * m_highwater;
michael@0:   bool           m_highpassed;
michael@0: };
michael@0: 
michael@0: 
michael@0: class FiniteStateMachine
michael@0: {
michael@0: public:
michael@0:   enum {MAX_RULES=128};
michael@0: 
michael@0: private:
michael@0:   class Rules
michael@0:   {
michael@0:   public:
michael@0:       Rules();
michael@0:       void              clear();
michael@0:       const RuleEntry * begin() const;
michael@0:       const RuleEntry * end() const;
michael@0:       size_t            size() const;
michael@0:       
michael@0:       void accumulate_rules(const State &state);
michael@0: 
michael@0:   private:
michael@0:       RuleEntry * m_begin, 
michael@0:                 * m_end,
michael@0:                   m_rules[MAX_RULES*2];
michael@0:   };
michael@0: 
michael@0: public:
michael@0:   FiniteStateMachine(SlotMap & map, json * logger);
michael@0:   void      reset(Slot * & slot, const short unsigned int max_pre_ctxt);
michael@0: 
michael@0:   Rules     rules;
michael@0:   SlotMap   & slots;
michael@0:   json    * const dbgout;
michael@0: };
michael@0: 
michael@0: 
michael@0: inline
michael@0: FiniteStateMachine::FiniteStateMachine(SlotMap& map, json * logger)
michael@0: : slots(map),
michael@0:   dbgout(logger)
michael@0: {
michael@0: }
michael@0: 
michael@0: inline
michael@0: void FiniteStateMachine::reset(Slot * & slot, const short unsigned int max_pre_ctxt)
michael@0: {
michael@0:   rules.clear();
michael@0:   int ctxt = 0;
michael@0:   for (; ctxt != max_pre_ctxt && slot->prev(); ++ctxt, slot = slot->prev());
michael@0:   slots.reset(*slot, ctxt);
michael@0: }
michael@0: 
michael@0: inline
michael@0: FiniteStateMachine::Rules::Rules()
michael@0:   : m_begin(m_rules), m_end(m_rules)
michael@0: {
michael@0: }
michael@0: 
michael@0: inline
michael@0: void FiniteStateMachine::Rules::clear()
michael@0: {
michael@0:   m_end = m_begin;
michael@0: }
michael@0: 
michael@0: inline
michael@0: const RuleEntry * FiniteStateMachine::Rules::begin() const
michael@0: {
michael@0:   return m_begin;
michael@0: }
michael@0: 
michael@0: inline
michael@0: const RuleEntry * FiniteStateMachine::Rules::end() const
michael@0: {
michael@0:   return m_end;
michael@0: }
michael@0: 
michael@0: inline
michael@0: size_t FiniteStateMachine::Rules::size() const
michael@0: {
michael@0:   return m_end - m_begin;
michael@0: }
michael@0: 
michael@0: inline
michael@0: void FiniteStateMachine::Rules::accumulate_rules(const State &state)
michael@0: {
michael@0:   // Only bother if there are rules in the State object.
michael@0:   if (state.empty()) return;
michael@0:   
michael@0:   // Merge the new sorted rules list into the current sorted result set.
michael@0:   const RuleEntry * lre = begin(), * rre = state.rules;
michael@0:   RuleEntry * out = m_rules + (m_begin == m_rules)*MAX_RULES;    
michael@0:   const RuleEntry * const lrend = out + MAX_RULES,
michael@0:                   * const rrend = state.rules_end;
michael@0:   m_begin = out; 
michael@0:   while (lre != end() && out != lrend)
michael@0:   {
michael@0:     if (*lre < *rre)      *out++ = *lre++;
michael@0:     else if (*rre < *lre) { *out++ = *rre++; }
michael@0:     else                { *out++ = *lre++; ++rre; }
michael@0: 
michael@0:     if (rre == rrend)
michael@0:     { 
michael@0:       while (lre != end() && out != lrend) { *out++ = *lre++; }
michael@0:       m_end = out;
michael@0:       return;
michael@0:     }
michael@0:   }
michael@0:   while (rre != rrend && out != lrend) { *out++ = *rre++; }
michael@0:   m_end = out;
michael@0: }
michael@0: 
michael@0: inline
michael@0: SlotMap::SlotMap(Segment & seg)
michael@0: : segment(seg), m_size(0), m_precontext(0), m_highwater(0), m_highpassed(false)
michael@0: {
michael@0:     m_slot_map[0] = 0;
michael@0: }
michael@0: 
michael@0: inline
michael@0: Slot * * SlotMap::begin()
michael@0: {
michael@0:   return &m_slot_map[1]; // allow map to go 1 before slot_map when inserting
michael@0:                          // at start of segment.
michael@0: }
michael@0: 
michael@0: inline
michael@0: Slot * * SlotMap::end()
michael@0: {
michael@0:   return m_slot_map + m_size + 1;
michael@0: }
michael@0: 
michael@0: inline
michael@0: size_t SlotMap::size() const
michael@0: {
michael@0:   return m_size;
michael@0: }
michael@0: 
michael@0: inline
michael@0: short unsigned int SlotMap::context() const
michael@0: {
michael@0:   return m_precontext;
michael@0: }
michael@0: 
michael@0: inline
michael@0: void SlotMap::reset(Slot & slot, short unsigned int ctxt)
michael@0: {
michael@0:   m_size = 0;
michael@0:   m_precontext = ctxt;
michael@0:   *m_slot_map = slot.prev();
michael@0: }
michael@0: 
michael@0: inline
michael@0: void SlotMap::pushSlot(Slot*const slot)
michael@0: {
michael@0:   m_slot_map[++m_size] = slot;
michael@0: }
michael@0: 
michael@0: inline
michael@0: Slot * const & SlotMap::operator[](int n) const
michael@0: {
michael@0:   return m_slot_map[n + 1];
michael@0: }
michael@0: 
michael@0: inline
michael@0: Slot * & SlotMap::operator[](int n)
michael@0: {
michael@0:   return m_slot_map[n + 1];
michael@0: }
michael@0: 
michael@0: } // namespace graphite2