Merge pull request #41100 from bruvzg/ctl_text_server_interface

[Complex Text Layouts] Implement TextServer interface.

1 files changed, 1107 insertions, 0 deletions

diff --git a/thirdparty/graphite/src/Pass.cpp b/thirdparty/graphite/src/Pass.cpp
new file mode 100644
index 0000000000..db31c22d46
--- /dev/null
+++ b/thirdparty/graphite/src/Pass.cpp
@@ -0,0 +1,1107 @@
+/*  GRAPHITE2 LICENSING
+
+    Copyright 2010, SIL International
+    All rights reserved.
+
+    This library is free software; you can redistribute it and/or modify
+    it under the terms of the GNU Lesser General Public License as published
+    by the Free Software Foundation; either version 2.1 of License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+
+    You should also have received a copy of the GNU Lesser General Public
+    License along with this library in the file named "LICENSE".
+    If not, write to the Free Software Foundation, 51 Franklin Street,
+    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
+    internet at http://www.fsf.org/licenses/lgpl.html.
+
+Alternatively, the contents of this file may be used under the terms of the
+Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
+License, as published by the Free Software Foundation, either version 2
+of the License or (at your option) any later version.
+*/
+#include "inc/Main.h"
+#include "inc/debug.h"
+#include "inc/Endian.h"
+#include "inc/Pass.h"
+#include <cstring>
+#include <cstdlib>
+#include <cassert>
+#include <cmath>
+#include "inc/Segment.h"
+#include "inc/Code.h"
+#include "inc/Rule.h"
+#include "inc/Error.h"
+#include "inc/Collider.h"
+
+using namespace graphite2;
+using vm::Machine;
+typedef Machine::Code  Code;
+
+enum KernCollison
+{
+    None       = 0,
+    CrossSpace = 1,
+    InWord     = 2,
+    reserved   = 3
+};
+
+Pass::Pass()
+: m_silf(0),
+  m_cols(0),
+  m_rules(0),
+  m_ruleMap(0),
+  m_startStates(0),
+  m_transitions(0),
+  m_states(0),
+  m_codes(0),
+  m_progs(0),
+  m_numCollRuns(0),
+  m_kernColls(0),
+  m_iMaxLoop(0),
+  m_numGlyphs(0),
+  m_numRules(0),
+  m_numStates(0),
+  m_numTransition(0),
+  m_numSuccess(0),
+  m_successStart(0),
+  m_numColumns(0),
+  m_minPreCtxt(0),
+  m_maxPreCtxt(0),
+  m_colThreshold(0),
+  m_isReverseDir(false)
+{
+}
+
+Pass::~Pass()
+{
+    free(m_cols);
+    free(m_startStates);
+    free(m_transitions);
+    free(m_states);
+    free(m_ruleMap);
+
+    if (m_rules) delete [] m_rules;
+    if (m_codes) delete [] m_codes;
+    free(m_progs);
+}
+
+bool Pass::readPass(const byte * const pass_start, size_t pass_length, size_t subtable_base,
+        GR_MAYBE_UNUSED Face & face, passtype pt, GR_MAYBE_UNUSED uint32 version, Error &e)
+{
+    const byte * p              = pass_start,
+               * const pass_end = p + pass_length;
+    size_t numRanges;
+
+    if (e.test(pass_length < 40, E_BADPASSLENGTH)) return face.error(e);
+    // Read in basic values
+    const byte flags = be::read<byte>(p);
+    if (e.test((flags & 0x1f) &&
+            (pt < PASS_TYPE_POSITIONING || !m_silf->aCollision() || !face.glyphs().hasBoxes() || !(m_silf->flags() & 0x20)),
+            E_BADCOLLISIONPASS))
+        return face.error(e);
+    m_numCollRuns = flags & 0x7;
+    m_kernColls   = (flags >> 3) & 0x3;
+    m_isReverseDir = (flags >> 5) & 0x1;
+    m_iMaxLoop = be::read<byte>(p);
+    if (m_iMaxLoop < 1) m_iMaxLoop = 1;
+    be::skip<byte>(p,2); // skip maxContext & maxBackup
+    m_numRules = be::read<uint16>(p);
+    if (e.test(!m_numRules && m_numCollRuns == 0, E_BADEMPTYPASS)) return face.error(e);
+    be::skip<uint16>(p);   // fsmOffset - not sure why we would want this
+    const byte * const pcCode = pass_start + be::read<uint32>(p) - subtable_base,
+               * const rcCode = pass_start + be::read<uint32>(p) - subtable_base,
+               * const aCode  = pass_start + be::read<uint32>(p) - subtable_base;
+    be::skip<uint32>(p);
+    m_numStates = be::read<uint16>(p);
+    m_numTransition = be::read<uint16>(p);
+    m_numSuccess = be::read<uint16>(p);
+    m_numColumns = be::read<uint16>(p);
+    numRanges = be::read<uint16>(p);
+    be::skip<uint16>(p, 3); // skip searchRange, entrySelector & rangeShift.
+    assert(p - pass_start == 40);
+    // Perform some sanity checks.
+    if ( e.test(m_numTransition > m_numStates, E_BADNUMTRANS)
+            || e.test(m_numSuccess > m_numStates, E_BADNUMSUCCESS)
+            || e.test(m_numSuccess + m_numTransition < m_numStates, E_BADNUMSTATES)
+            || e.test(m_numRules && numRanges == 0, E_NORANGES)
+            || e.test(m_numColumns > 0x7FFF, E_BADNUMCOLUMNS))
+        return face.error(e);
+
+    m_successStart = m_numStates - m_numSuccess;
+    // test for beyond end - 1 to account for reading uint16
+    if (e.test(p + numRanges * 6 - 2 > pass_end, E_BADPASSLENGTH)) return face.error(e);
+    m_numGlyphs = be::peek<uint16>(p + numRanges * 6 - 4) + 1;
+    // Calculate the start of various arrays.
+    const byte * const ranges = p;
+    be::skip<uint16>(p, numRanges*3);
+    const byte * const o_rule_map = p;
+    be::skip<uint16>(p, m_numSuccess + 1);
+
+    // More sanity checks
+    if (e.test(reinterpret_cast<const byte *>(o_rule_map + m_numSuccess*sizeof(uint16)) > pass_end
+            || p > pass_end, E_BADRULEMAPLEN))
+        return face.error(e);
+    const size_t numEntries = be::peek<uint16>(o_rule_map + m_numSuccess*sizeof(uint16));
+    const byte * const   rule_map = p;
+    be::skip<uint16>(p, numEntries);
+
+    if (e.test(p + 2*sizeof(uint8) > pass_end, E_BADPASSLENGTH)) return face.error(e);
+    m_minPreCtxt = be::read<uint8>(p);
+    m_maxPreCtxt = be::read<uint8>(p);
+    if (e.test(m_minPreCtxt > m_maxPreCtxt, E_BADCTXTLENBOUNDS)) return face.error(e);
+    const byte * const start_states = p;
+    be::skip<int16>(p, m_maxPreCtxt - m_minPreCtxt + 1);
+    const uint16 * const sort_keys = reinterpret_cast<const uint16 *>(p);
+    be::skip<uint16>(p, m_numRules);
+    const byte * const precontext = p;
+    be::skip<byte>(p, m_numRules);
+
+    if (e.test(p + sizeof(uint16) + sizeof(uint8) > pass_end, E_BADCTXTLENS)) return face.error(e);
+    m_colThreshold = be::read<uint8>(p);
+    if (m_colThreshold == 0) m_colThreshold = 10;       // A default
+    const size_t pass_constraint_len = be::read<uint16>(p);
+
+    const uint16 * const o_constraint = reinterpret_cast<const uint16 *>(p);
+    be::skip<uint16>(p, m_numRules + 1);
+    const uint16 * const o_actions = reinterpret_cast<const uint16 *>(p);
+    be::skip<uint16>(p, m_numRules + 1);
+    const byte * const states = p;
+    if (e.test(2u*m_numTransition*m_numColumns >= (unsigned)(pass_end - p), E_BADPASSLENGTH)
+            || e.test(p >= pass_end, E_BADPASSLENGTH))
+        return face.error(e);
+    be::skip<int16>(p, m_numTransition*m_numColumns);
+    be::skip<uint8>(p);
+    if (e.test(p != pcCode, E_BADPASSCCODEPTR)) return face.error(e);
+    be::skip<byte>(p, pass_constraint_len);
+    if (e.test(p != rcCode, E_BADRULECCODEPTR)
+        || e.test(size_t(rcCode - pcCode) != pass_constraint_len, E_BADCCODELEN)) return face.error(e);
+    be::skip<byte>(p, be::peek<uint16>(o_constraint + m_numRules));
+    if (e.test(p != aCode, E_BADACTIONCODEPTR)) return face.error(e);
+    be::skip<byte>(p, be::peek<uint16>(o_actions + m_numRules));
+
+    // We should be at the end or within the pass
+    if (e.test(p > pass_end, E_BADPASSLENGTH)) return face.error(e);
+
+    // Load the pass constraint if there is one.
+    if (pass_constraint_len)
+    {
+        face.error_context(face.error_context() + 1);
+        m_cPConstraint = vm::Machine::Code(true, pcCode, pcCode + pass_constraint_len,
+                                  precontext[0], be::peek<uint16>(sort_keys), *m_silf, face, PASS_TYPE_UNKNOWN);
+        if (e.test(!m_cPConstraint, E_OUTOFMEM)
+                || e.test(m_cPConstraint.status() != Code::loaded, m_cPConstraint.status() + E_CODEFAILURE))
+            return face.error(e);
+        face.error_context(face.error_context() - 1);
+    }
+    if (m_numRules)
+    {
+        if (!readRanges(ranges, numRanges, e)) return face.error(e);
+        if (!readRules(rule_map, numEntries,  precontext, sort_keys,
+                   o_constraint, rcCode, o_actions, aCode, face, pt, e)) return false;
+    }
+#ifdef GRAPHITE2_TELEMETRY
+    telemetry::category _states_cat(face.tele.states);
+#endif
+    return m_numRules ? readStates(start_states, states, o_rule_map, face, e) : true;
+}
+
+
+bool Pass::readRules(const byte * rule_map, const size_t num_entries,
+                     const byte *precontext, const uint16 * sort_key,
+                     const uint16 * o_constraint, const byte *rc_data,
+                     const uint16 * o_action,     const byte * ac_data,
+                     Face & face, passtype pt, Error &e)
+{
+    const byte * const ac_data_end = ac_data + be::peek<uint16>(o_action + m_numRules);
+    const byte * const rc_data_end = rc_data + be::peek<uint16>(o_constraint + m_numRules);
+
+    precontext += m_numRules;
+    sort_key   += m_numRules;
+    o_constraint += m_numRules;
+    o_action += m_numRules;
+
+    // Load rules.
+    const byte * ac_begin = 0, * rc_begin = 0,
+               * ac_end = ac_data + be::peek<uint16>(o_action),
+               * rc_end = rc_data + be::peek<uint16>(o_constraint);
+
+    // Allocate pools
+    m_rules = new Rule [m_numRules];
+    m_codes = new Code [m_numRules*2];
+    int totalSlots = 0;
+    const uint16 *tsort = sort_key;
+    for (int i = 0; i < m_numRules; ++i)
+        totalSlots += be::peek<uint16>(--tsort);
+    const size_t prog_pool_sz = vm::Machine::Code::estimateCodeDataOut(ac_end - ac_data + rc_end - rc_data, 2 * m_numRules, totalSlots);
+    m_progs = gralloc<byte>(prog_pool_sz);
+    byte * prog_pool_free = m_progs,
+         * prog_pool_end  = m_progs + prog_pool_sz;
+    if (e.test(!(m_rules && m_codes && m_progs), E_OUTOFMEM)) return face.error(e);
+
+    Rule * r = m_rules + m_numRules - 1;
+    for (size_t n = m_numRules; r >= m_rules; --n, --r, ac_end = ac_begin, rc_end = rc_begin)
+    {
+        face.error_context((face.error_context() & 0xFFFF00) + EC_ARULE + int((n - 1) << 24));
+        r->preContext = *--precontext;
+        r->sort       = be::peek<uint16>(--sort_key);
+#ifndef NDEBUG
+        r->rule_idx   = uint16(n - 1);
+#endif
+        if (r->sort > 63 || r->preContext >= r->sort || r->preContext > m_maxPreCtxt || r->preContext < m_minPreCtxt)
+            return false;
+        ac_begin      = ac_data + be::peek<uint16>(--o_action);
+        --o_constraint;
+        rc_begin      = be::peek<uint16>(o_constraint) ? rc_data + be::peek<uint16>(o_constraint) : rc_end;
+
+        if (ac_begin > ac_end || ac_begin > ac_data_end || ac_end > ac_data_end
+                || rc_begin > rc_end || rc_begin > rc_data_end || rc_end > rc_data_end
+                || vm::Machine::Code::estimateCodeDataOut(ac_end - ac_begin + rc_end - rc_begin, 2, r->sort) > size_t(prog_pool_end - prog_pool_free))
+            return false;
+        r->action     = new (m_codes+n*2-2) vm::Machine::Code(false, ac_begin, ac_end, r->preContext, r->sort, *m_silf, face, pt, &prog_pool_free);
+        r->constraint = new (m_codes+n*2-1) vm::Machine::Code(true,  rc_begin, rc_end, r->preContext, r->sort, *m_silf, face, pt, &prog_pool_free);
+
+        if (e.test(!r->action || !r->constraint, E_OUTOFMEM)
+                || e.test(r->action->status() != Code::loaded, r->action->status() + E_CODEFAILURE)
+                || e.test(r->constraint->status() != Code::loaded, r->constraint->status() + E_CODEFAILURE)
+                || e.test(!r->constraint->immutable(), E_MUTABLECCODE))
+            return face.error(e);
+    }
+
+    byte * const moved_progs = prog_pool_free > m_progs ? static_cast<byte *>(realloc(m_progs, prog_pool_free - m_progs)) : 0;
+    if (e.test(!moved_progs, E_OUTOFMEM))
+    {
+        free(m_progs);
+        m_progs = 0;
+        return face.error(e);
+    }
+
+    if (moved_progs != m_progs)
+    {
+        for (Code * c = m_codes, * const ce = c + m_numRules*2; c != ce; ++c)
+        {
+            c->externalProgramMoved(moved_progs - m_progs);
+        }
+        m_progs = moved_progs;
+    }
+
+    // Load the rule entries map
+    face.error_context((face.error_context() & 0xFFFF00) + EC_APASS);
+    //TODO: Coverity: 1315804: FORWARD_NULL
+    RuleEntry * re = m_ruleMap = gralloc<RuleEntry>(num_entries);
+    if (e.test(!re, E_OUTOFMEM)) return face.error(e);
+    for (size_t n = num_entries; n; --n, ++re)
+    {
+        const ptrdiff_t rn = be::read<uint16>(rule_map);
+        if (e.test(rn >= m_numRules, E_BADRULENUM))  return face.error(e);
+        re->rule = m_rules + rn;
+    }
+
+    return true;
+}
+
+static int cmpRuleEntry(const void *a, const void *b) { return (*(RuleEntry *)a < *(RuleEntry *)b ? -1 :
+                                                                (*(RuleEntry *)b < *(RuleEntry *)a ? 1 : 0)); }
+
+bool Pass::readStates(const byte * starts, const byte *states, const byte * o_rule_map, GR_MAYBE_UNUSED Face & face, Error &e)
+{
+#ifdef GRAPHITE2_TELEMETRY
+    telemetry::category _states_cat(face.tele.starts);
+#endif
+    m_startStates = gralloc<uint16>(m_maxPreCtxt - m_minPreCtxt + 1);
+#ifdef GRAPHITE2_TELEMETRY
+    telemetry::set_category(face.tele.states);
+#endif
+    m_states      = gralloc<State>(m_numStates);
+#ifdef GRAPHITE2_TELEMETRY
+    telemetry::set_category(face.tele.transitions);
+#endif
+    m_transitions      = gralloc<uint16>(m_numTransition * m_numColumns);
+
+    if (e.test(!m_startStates || !m_states || !m_transitions, E_OUTOFMEM)) return face.error(e);
+    // load start states
+    for (uint16 * s = m_startStates,
+                * const s_end = s + m_maxPreCtxt - m_minPreCtxt + 1; s != s_end; ++s)
+    {
+        *s = be::read<uint16>(starts);
+        if (e.test(*s >= m_numStates, E_BADSTATE))
+        {
+            face.error_context((face.error_context() & 0xFFFF00) + EC_ASTARTS + int((s - m_startStates) << 24));
+            return face.error(e); // true;
+        }
+    }
+
+    // load state transition table.
+    for (uint16 * t = m_transitions,
+                * const t_end = t + m_numTransition*m_numColumns; t != t_end; ++t)
+    {
+        *t = be::read<uint16>(states);
+        if (e.test(*t >= m_numStates, E_BADSTATE))
+        {
+            face.error_context((face.error_context() & 0xFFFF00) + EC_ATRANS + int(((t - m_transitions) / m_numColumns) << 8));
+            return face.error(e);
+        }
+    }
+
+    State * s = m_states,
+          * const success_begin = m_states + m_numStates - m_numSuccess;
+    const RuleEntry * rule_map_end = m_ruleMap + be::peek<uint16>(o_rule_map + m_numSuccess*sizeof(uint16));
+    for (size_t n = m_numStates; n; --n, ++s)
+    {
+        RuleEntry * const begin = s < success_begin ? 0 : m_ruleMap + be::read<uint16>(o_rule_map),
+                  * const end   = s < success_begin ? 0 : m_ruleMap + be::peek<uint16>(o_rule_map);
+
+        if (e.test(begin >= rule_map_end || end > rule_map_end || begin > end, E_BADRULEMAPPING))
+        {
+            face.error_context((face.error_context() & 0xFFFF00) + EC_ARULEMAP + int(n << 24));
+            return face.error(e);
+        }
+        s->rules = begin;
+        s->rules_end = (end - begin <= FiniteStateMachine::MAX_RULES)? end :
+            begin + FiniteStateMachine::MAX_RULES;
+        if (begin)      // keep UBSan happy can't call qsort with null begin
+            qsort(begin, end - begin, sizeof(RuleEntry), &cmpRuleEntry);
+    }
+
+    return true;
+}
+
+bool Pass::readRanges(const byte * ranges, size_t num_ranges, Error &e)
+{
+    m_cols = gralloc<uint16>(m_numGlyphs);
+    if (e.test(!m_cols, E_OUTOFMEM)) return false;
+    memset(m_cols, 0xFF, m_numGlyphs * sizeof(uint16));
+    for (size_t n = num_ranges; n; --n)
+    {
+        uint16     * ci     = m_cols + be::read<uint16>(ranges),
+                   * ci_end = m_cols + be::read<uint16>(ranges) + 1,
+                     col    = be::read<uint16>(ranges);
+
+        if (e.test(ci >= ci_end || ci_end > m_cols+m_numGlyphs || col >= m_numColumns, E_BADRANGE))
+            return false;
+
+        // A glyph must only belong to one column at a time
+        while (ci != ci_end && *ci == 0xffff)
+            *ci++ = col;
+
+        if (e.test(ci != ci_end, E_BADRANGE))
+            return false;
+    }
+    return true;
+}
+
+
+bool Pass::runGraphite(vm::Machine & m, FiniteStateMachine & fsm, bool reverse) const
+{
+    Slot *s = m.slotMap().segment.first();
+    if (!s || !testPassConstraint(m)) return true;
+    if (reverse)
+    {
+        m.slotMap().segment.reverseSlots();
+        s = m.slotMap().segment.first();
+    }
+    if (m_numRules)
+    {
+        Slot *currHigh = s->next();
+
+#if !defined GRAPHITE2_NTRACING
+        if (fsm.dbgout)  *fsm.dbgout << "rules" << json::array;
+        json::closer rules_array_closer(fsm.dbgout);
+#endif
+
+        m.slotMap().highwater(currHigh);
+        int lc = m_iMaxLoop;
+        do
+        {
+            findNDoRule(s, m, fsm);
+            if (m.status() != Machine::finished) return false;
+            if (s && (s == m.slotMap().highwater() || m.slotMap().highpassed() || --lc == 0)) {
+                if (!lc)
+                    s = m.slotMap().highwater();
+                lc = m_iMaxLoop;
+                if (s)
+                    m.slotMap().highwater(s->next());
+            }
+        } while (s);
+    }
+    //TODO: Use enums for flags
+    const bool collisions = m_numCollRuns || m_kernColls;
+
+    if (!collisions || !m.slotMap().segment.hasCollisionInfo())
+        return true;
+
+    if (m_numCollRuns)
+    {
+        if (!(m.slotMap().segment.flags() & Segment::SEG_INITCOLLISIONS))
+        {
+            m.slotMap().segment.positionSlots(0, 0, 0, m.slotMap().dir(), true);
+//            m.slotMap().segment.flags(m.slotMap().segment.flags() | Segment::SEG_INITCOLLISIONS);
+        }
+        if (!collisionShift(&m.slotMap().segment, m.slotMap().dir(), fsm.dbgout))
+            return false;
+    }
+    if ((m_kernColls) && !collisionKern(&m.slotMap().segment, m.slotMap().dir(), fsm.dbgout))
+        return false;
+    if (collisions && !collisionFinish(&m.slotMap().segment, fsm.dbgout))
+        return false;
+    return true;
+}
+
+bool Pass::runFSM(FiniteStateMachine& fsm, Slot * slot) const
+{
+    fsm.reset(slot, m_maxPreCtxt);
+    if (fsm.slots.context() < m_minPreCtxt)
+        return false;
+
+    uint16 state = m_startStates[m_maxPreCtxt - fsm.slots.context()];
+    uint8  free_slots = SlotMap::MAX_SLOTS;
+    do
+    {
+        fsm.slots.pushSlot(slot);
+        if (slot->gid() >= m_numGlyphs
+         || m_cols[slot->gid()] == 0xffffU
+         || --free_slots == 0
+         || state >= m_numTransition)
+            return free_slots != 0;
+
+        const uint16 * transitions = m_transitions + state*m_numColumns;
+        state = transitions[m_cols[slot->gid()]];
+        if (state >= m_successStart)
+            fsm.rules.accumulate_rules(m_states[state]);
+
+        slot = slot->next();
+    } while (state != 0 && slot);
+
+    fsm.slots.pushSlot(slot);
+    return true;
+}
+
+#if !defined GRAPHITE2_NTRACING
+
+inline
+Slot * input_slot(const SlotMap &  slots, const int n)
+{
+    Slot * s = slots[slots.context() + n];
+    if (!s->isCopied())     return s;
+
+    return s->prev() ? s->prev()->next() : (s->next() ? s->next()->prev() : slots.segment.last());
+}
+
+inline
+Slot * output_slot(const SlotMap &  slots, const int n)
+{
+    Slot * s = slots[slots.context() + n - 1];
+    return s ? s->next() : slots.segment.first();
+}
+
+#endif //!defined GRAPHITE2_NTRACING
+
+void Pass::findNDoRule(Slot * & slot, Machine &m, FiniteStateMachine & fsm) const
+{
+    assert(slot);
+
+    if (runFSM(fsm, slot))
+    {
+        // Search for the first rule which passes the constraint
+        const RuleEntry *        r = fsm.rules.begin(),
+                        * const re = fsm.rules.end();
+        while (r != re && !testConstraint(*r->rule, m))
+        {
+            ++r;
+            if (m.status() != Machine::finished)
+                return;
+        }
+
+#if !defined GRAPHITE2_NTRACING
+        if (fsm.dbgout)
+        {
+            if (fsm.rules.size() != 0)
+            {
+                *fsm.dbgout << json::item << json::object;
+                dumpRuleEventConsidered(fsm, *r);
+                if (r != re)
+                {
+                    const int adv = doAction(r->rule->action, slot, m);
+                    dumpRuleEventOutput(fsm, *r->rule, slot);
+                    if (r->rule->action->deletes()) fsm.slots.collectGarbage(slot);
+                    adjustSlot(adv, slot, fsm.slots);
+                    *fsm.dbgout << "cursor" << objectid(dslot(&fsm.slots.segment, slot))
+                            << json::close; // Close RuelEvent object
+
+                    return;
+                }
+                else
+                {
+                    *fsm.dbgout << json::close  // close "considered" array
+                            << "output" << json::null
+                            << "cursor" << objectid(dslot(&fsm.slots.segment, slot->next()))
+                            << json::close;
+                }
+            }
+        }
+        else
+#endif
+        {
+            if (r != re)
+            {
+                const int adv = doAction(r->rule->action, slot, m);
+                if (m.status() != Machine::finished) return;
+                if (r->rule->action->deletes()) fsm.slots.collectGarbage(slot);
+                adjustSlot(adv, slot, fsm.slots);
+                return;
+            }
+        }
+    }
+
+    slot = slot->next();
+    return;
+}
+
+#if !defined GRAPHITE2_NTRACING
+
+void Pass::dumpRuleEventConsidered(const FiniteStateMachine & fsm, const RuleEntry & re) const
+{
+    *fsm.dbgout << "considered" << json::array;
+    for (const RuleEntry *r = fsm.rules.begin(); r != &re; ++r)
+    {
+        if (r->rule->preContext > fsm.slots.context())
+            continue;
+        *fsm.dbgout << json::flat << json::object
+                    << "id" << r->rule - m_rules
+                    << "failed" << true
+                    << "input" << json::flat << json::object
+                        << "start" << objectid(dslot(&fsm.slots.segment, input_slot(fsm.slots, -r->rule->preContext)))
+                        << "length" << r->rule->sort
+                        << json::close  // close "input"
+                    << json::close; // close Rule object
+    }
+}
+
+
+void Pass::dumpRuleEventOutput(const FiniteStateMachine & fsm, const Rule & r, Slot * const last_slot) const
+{
+    *fsm.dbgout     << json::item << json::flat << json::object
+                        << "id"     << &r - m_rules
+                        << "failed" << false
+                        << "input" << json::flat << json::object
+                            << "start" << objectid(dslot(&fsm.slots.segment, input_slot(fsm.slots, 0)))
+                            << "length" << r.sort - r.preContext
+                            << json::close // close "input"
+                        << json::close  // close Rule object
+                << json::close // close considered array
+                << "output" << json::object
+                    << "range" << json::flat << json::object
+                        << "start"  << objectid(dslot(&fsm.slots.segment, input_slot(fsm.slots, 0)))
+                        << "end"    << objectid(dslot(&fsm.slots.segment, last_slot))
+                    << json::close // close "input"
+                    << "slots"  << json::array;
+    const Position rsb_prepos = last_slot ? last_slot->origin() : fsm.slots.segment.advance();
+    fsm.slots.segment.positionSlots(0, 0, 0, fsm.slots.segment.currdir());
+
+    for(Slot * slot = output_slot(fsm.slots, 0); slot != last_slot; slot = slot->next())
+        *fsm.dbgout     << dslot(&fsm.slots.segment, slot);
+    *fsm.dbgout         << json::close  // close "slots"
+                    << "postshift"  << (last_slot ? last_slot->origin() : fsm.slots.segment.advance()) - rsb_prepos
+                << json::close;         // close "output" object
+
+}
+
+#endif
+
+
+inline
+bool Pass::testPassConstraint(Machine & m) const
+{
+    if (!m_cPConstraint) return true;
+
+    assert(m_cPConstraint.constraint());
+
+    m.slotMap().reset(*m.slotMap().segment.first(), 0);
+    m.slotMap().pushSlot(m.slotMap().segment.first());
+    vm::slotref * map = m.slotMap().begin();
+    const uint32 ret = m_cPConstraint.run(m, map);
+
+#if !defined GRAPHITE2_NTRACING
+    json * const dbgout = m.slotMap().segment.getFace()->logger();
+    if (dbgout)
+        *dbgout << "constraint" << (ret && m.status() == Machine::finished);
+#endif
+
+    return ret && m.status() == Machine::finished;
+}
+
+
+bool Pass::testConstraint(const Rule & r, Machine & m) const
+{
+    const uint16 curr_context = m.slotMap().context();
+    if (unsigned(r.sort + curr_context - r.preContext) > m.slotMap().size()
+        || curr_context - r.preContext < 0) return false;
+
+    vm::slotref * map = m.slotMap().begin() + curr_context - r.preContext;
+    if (map[r.sort - 1] == 0)
+        return false;
+
+    if (!*r.constraint) return true;
+    assert(r.constraint->constraint());
+    for (int n = r.sort; n && map; --n, ++map)
+    {
+        if (!*map) continue;
+        const int32 ret = r.constraint->run(m, map);
+        if (!ret || m.status() != Machine::finished)
+            return false;
+    }
+
+    return true;
+}
+
+
+void SlotMap::collectGarbage(Slot * &aSlot)
+{
+    for(Slot **s = begin(), *const *const se = end() - 1; s != se; ++s) {
+        Slot *& slot = *s;
+        if(slot && (slot->isDeleted() || slot->isCopied()))
+        {
+            if (slot == aSlot)
+                aSlot = slot->prev() ? slot->prev() : slot->next();
+            segment.freeSlot(slot);
+        }
+    }
+}
+
+
+
+int Pass::doAction(const Code *codeptr, Slot * & slot_out, vm::Machine & m) const
+{
+    assert(codeptr);
+    if (!*codeptr) return 0;
+    SlotMap   & smap = m.slotMap();
+    vm::slotref * map = &smap[smap.context()];
+    smap.highpassed(false);
+
+    int32 ret = codeptr->run(m, map);
+
+    if (m.status() != Machine::finished)
+    {
+        slot_out = NULL;
+        smap.highwater(0);
+        return 0;
+    }
+
+    slot_out = *map;
+    return ret;
+}
+
+
+void Pass::adjustSlot(int delta, Slot * & slot_out, SlotMap & smap) const
+{
+    if (!slot_out)
+    {
+        if (smap.highpassed() || slot_out == smap.highwater())
+        {
+            slot_out = smap.segment.last();
+            ++delta;
+            if (!smap.highwater() || smap.highwater() == slot_out)
+                smap.highpassed(false);
+        }
+        else
+        {
+            slot_out = smap.segment.first();
+            --delta;
+        }
+    }
+    if (delta < 0)
+    {
+        while (++delta <= 0 && slot_out)
+        {
+            slot_out = slot_out->prev();
+            if (smap.highpassed() && smap.highwater() == slot_out)
+                smap.highpassed(false);
+        }
+    }
+    else if (delta > 0)
+    {
+        while (--delta >= 0 && slot_out)
+        {
+            if (slot_out == smap.highwater() && slot_out)
+                smap.highpassed(true);
+            slot_out = slot_out->next();
+        }
+    }
+}
+
+bool Pass::collisionShift(Segment *seg, int dir, json * const dbgout) const
+{
+    ShiftCollider shiftcoll(dbgout);
+    // bool isfirst = true;
+    bool hasCollisions = false;
+    Slot *start = seg->first();      // turn on collision fixing for the first slot
+    Slot *end = NULL;
+    bool moved = false;
+
+#if !defined GRAPHITE2_NTRACING
+    if (dbgout)
+        *dbgout << "collisions" << json::array
+            << json::flat << json::object << "num-loops" << m_numCollRuns << json::close;
+#endif
+
+    while (start)
+    {
+#if !defined GRAPHITE2_NTRACING
+        if (dbgout)  *dbgout << json::object << "phase" << "1" << "moves" << json::array;
+#endif
+        hasCollisions = false;
+        end = NULL;
+        // phase 1 : position shiftable glyphs, ignoring kernable glyphs
+        for (Slot *s = start; s; s = s->next())
+        {
+            const SlotCollision * c = seg->collisionInfo(s);
+            if (start && (c->flags() & (SlotCollision::COLL_FIX | SlotCollision::COLL_KERN)) == SlotCollision::COLL_FIX
+                      && !resolveCollisions(seg, s, start, shiftcoll, false, dir, moved, hasCollisions, dbgout))
+                return false;
+            if (s != start && (c->flags() & SlotCollision::COLL_END))
+            {
+                end = s->next();
+                break;
+            }
+        }
+
+#if !defined GRAPHITE2_NTRACING
+        if (dbgout)
+            *dbgout << json::close << json::close; // phase-1
+#endif
+
+        // phase 2 : loop until happy.
+        for (int i = 0; i < m_numCollRuns - 1; ++i)
+        {
+            if (hasCollisions || moved)
+            {
+
+#if !defined GRAPHITE2_NTRACING
+                if (dbgout)
+                    *dbgout << json::object << "phase" << "2a" << "loop" << i << "moves" << json::array;
+#endif
+                // phase 2a : if any shiftable glyphs are in collision, iterate backwards,
+                // fixing them and ignoring other non-collided glyphs. Note that this handles ONLY
+                // glyphs that are actually in collision from phases 1 or 2b, and working backwards
+                // has the intended effect of breaking logjams.
+                if (hasCollisions)
+                {
+                    hasCollisions = false;
+                    #if 0
+                    moved = true;
+                    for (Slot *s = start; s != end; s = s->next())
+                    {
+                        SlotCollision * c = seg->collisionInfo(s);
+                        c->setShift(Position(0, 0));
+                    }
+                    #endif
+                    Slot *lend = end ? end->prev() : seg->last();
+                    Slot *lstart = start->prev();
+                    for (Slot *s = lend; s != lstart; s = s->prev())
+                    {
+                        SlotCollision * c = seg->collisionInfo(s);
+                        if (start && (c->flags() & (SlotCollision::COLL_FIX | SlotCollision::COLL_KERN | SlotCollision::COLL_ISCOL))
+                                        == (SlotCollision::COLL_FIX | SlotCollision::COLL_ISCOL)) // ONLY if this glyph is still colliding
+                        {
+                            if (!resolveCollisions(seg, s, lend, shiftcoll, true, dir, moved, hasCollisions, dbgout))
+                                return false;
+                            c->setFlags(c->flags() | SlotCollision::COLL_TEMPLOCK);
+                        }
+                    }
+                }
+
+#if !defined GRAPHITE2_NTRACING
+                if (dbgout)
+                    *dbgout << json::close << json::close // phase 2a
+                        << json::object << "phase" << "2b" << "loop" << i << "moves" << json::array;
+#endif
+
+                // phase 2b : redo basic diacritic positioning pass for ALL glyphs. Each successive loop adjusts
+                // glyphs from their current adjusted position, which has the effect of gradually minimizing the
+                // resulting adjustment; ie, the final result will be gradually closer to the original location.
+                // Also it allows more flexibility in the final adjustment, since it is moving along the
+                // possible 8 vectors from successively different starting locations.
+                if (moved)
+                {
+                    moved = false;
+                    for (Slot *s = start; s != end; s = s->next())
+                    {
+                        SlotCollision * c = seg->collisionInfo(s);
+                        if (start && (c->flags() & (SlotCollision::COLL_FIX | SlotCollision::COLL_TEMPLOCK
+                                                        | SlotCollision::COLL_KERN)) == SlotCollision::COLL_FIX
+                                  && !resolveCollisions(seg, s, start, shiftcoll, false, dir, moved, hasCollisions, dbgout))
+                            return false;
+                        else if (c->flags() & SlotCollision::COLL_TEMPLOCK)
+                            c->setFlags(c->flags() & ~SlotCollision::COLL_TEMPLOCK);
+                    }
+                }
+        //      if (!hasCollisions) // no, don't leave yet because phase 2b will continue to improve things
+        //          break;
+#if !defined GRAPHITE2_NTRACING
+                if (dbgout)
+                    *dbgout << json::close << json::close; // phase 2
+#endif
+            }
+        }
+        if (!end)
+            break;
+        start = NULL;
+        for (Slot *s = end->prev(); s; s = s->next())
+        {
+            if (seg->collisionInfo(s)->flags() & SlotCollision::COLL_START)
+            {
+                start = s;
+                break;
+            }
+        }
+    }
+    return true;
+}
+
+bool Pass::collisionKern(Segment *seg, int dir, json * const dbgout) const
+{
+    Slot *start = seg->first();
+    float ymin = 1e38f;
+    float ymax = -1e38f;
+    const GlyphCache &gc = seg->getFace()->glyphs();
+
+    // phase 3 : handle kerning of clusters
+#if !defined GRAPHITE2_NTRACING
+    if (dbgout)
+        *dbgout << json::object << "phase" << "3" << "moves" << json::array;
+#endif
+
+    for (Slot *s = seg->first(); s; s = s->next())
+    {
+        if (!gc.check(s->gid()))
+            return false;
+        const SlotCollision * c = seg->collisionInfo(s);
+        const Rect &bbox = seg->theGlyphBBoxTemporary(s->gid());
+        float y = s->origin().y + c->shift().y;
+        if (!(c->flags() & SlotCollision::COLL_ISSPACE))
+        {
+            ymax = max(y + bbox.tr.y, ymax);
+            ymin = min(y + bbox.bl.y, ymin);
+        }
+        if (start && (c->flags() & (SlotCollision::COLL_KERN | SlotCollision::COLL_FIX))
+                        == (SlotCollision::COLL_KERN | SlotCollision::COLL_FIX))
+            resolveKern(seg, s, start, dir, ymin, ymax, dbgout);
+        if (c->flags() & SlotCollision::COLL_END)
+            start = NULL;
+        if (c->flags() & SlotCollision::COLL_START)
+            start = s;
+    }
+
+#if !defined GRAPHITE2_NTRACING
+    if (dbgout)
+        *dbgout << json::close << json::close; // phase 3
+#endif
+    return true;
+}
+
+bool Pass::collisionFinish(Segment *seg, GR_MAYBE_UNUSED json * const dbgout) const
+{
+    for (Slot *s = seg->first(); s; s = s->next())
+    {
+        SlotCollision *c = seg->collisionInfo(s);
+        if (c->shift().x != 0 || c->shift().y != 0)
+        {
+            const Position newOffset = c->shift();
+            const Position nullPosition(0, 0);
+            c->setOffset(newOffset + c->offset());
+            c->setShift(nullPosition);
+        }
+    }
+//    seg->positionSlots();
+
+#if !defined GRAPHITE2_NTRACING
+        if (dbgout)
+            *dbgout << json::close;
+#endif
+    return true;
+}
+
+// Can slot s be kerned, or is it attached to something that can be kerned?
+static bool inKernCluster(Segment *seg, Slot *s)
+{
+    SlotCollision *c = seg->collisionInfo(s);
+    if (c->flags() & SlotCollision::COLL_KERN /** && c->flags() & SlotCollision::COLL_FIX **/ )
+        return true;
+    while (s->attachedTo())
+    {
+        s = s->attachedTo();
+        c = seg->collisionInfo(s);
+        if (c->flags() & SlotCollision::COLL_KERN /** && c->flags() & SlotCollision::COLL_FIX **/ )
+            return true;
+    }
+    return false;
+}
+
+// Fix collisions for the given slot.
+// Return true if everything was fixed, false if there are still collisions remaining.
+// isRev means be we are processing backwards.
+bool Pass::resolveCollisions(Segment *seg, Slot *slotFix, Slot *start,
+        ShiftCollider &coll, GR_MAYBE_UNUSED bool isRev, int dir, bool &moved, bool &hasCol,
+        json * const dbgout) const
+{
+    Slot * nbor;  // neighboring slot
+    SlotCollision *cFix = seg->collisionInfo(slotFix);
+    if (!coll.initSlot(seg, slotFix, cFix->limit(), cFix->margin(), cFix->marginWt(),
+            cFix->shift(), cFix->offset(), dir, dbgout))
+        return false;
+    bool collides = false;
+    // When we're processing forward, ignore kernable glyphs that preceed the target glyph.
+    // When processing backward, don't ignore these until we pass slotFix.
+    bool ignoreForKern = !isRev;
+    bool rtl = dir & 1;
+    Slot *base = slotFix;
+    while (base->attachedTo())
+        base = base->attachedTo();
+    Position zero(0., 0.);
+
+    // Look for collisions with the neighboring glyphs.
+    for (nbor = start; nbor; nbor = isRev ? nbor->prev() : nbor->next())
+    {
+        SlotCollision *cNbor = seg->collisionInfo(nbor);
+        bool sameCluster = nbor->isChildOf(base);
+        if (nbor != slotFix         						// don't process if this is the slot of interest
+                      && !(cNbor->ignore())    				// don't process if ignoring
+                      && (nbor == base || sameCluster       // process if in the same cluster as slotFix
+                            || !inKernCluster(seg, nbor))   // or this cluster is not to be kerned
+//                            || (rtl ^ ignoreForKern))       // or it comes before(ltr) or after(rtl)
+                      && (!isRev    // if processing forwards then good to merge otherwise only:
+                            || !(cNbor->flags() & SlotCollision::COLL_FIX)     // merge in immovable stuff
+                            || ((cNbor->flags() & SlotCollision::COLL_KERN) && !sameCluster)     // ignore other kernable clusters
+                            || (cNbor->flags() & SlotCollision::COLL_ISCOL))   // test against other collided glyphs
+                      && !coll.mergeSlot(seg, nbor, cNbor, cNbor->shift(), !ignoreForKern, sameCluster, collides, false, dbgout))
+            return false;
+        else if (nbor == slotFix)
+            // Switching sides of this glyph - if we were ignoring kernable stuff before, don't anymore.
+            ignoreForKern = !ignoreForKern;
+
+        if (nbor != start && (cNbor->flags() & (isRev ? SlotCollision::COLL_START : SlotCollision::COLL_END)))
+            break;
+    }
+    bool isCol = false;
+    if (collides || cFix->shift().x != 0.f || cFix->shift().y != 0.f)
+    {
+        Position shift = coll.resolve(seg, isCol, dbgout);
+        // isCol has been set to true if a collision remains.
+        if (std::fabs(shift.x) < 1e38f && std::fabs(shift.y) < 1e38f)
+        {
+            if (sqr(shift.x-cFix->shift().x) + sqr(shift.y-cFix->shift().y) >= m_colThreshold * m_colThreshold)
+                moved = true;
+            cFix->setShift(shift);
+            if (slotFix->firstChild())
+            {
+                Rect bbox;
+                Position here = slotFix->origin() + shift;
+                float clusterMin = here.x;
+                slotFix->firstChild()->finalise(seg, NULL, here, bbox, 0, clusterMin, rtl, false);
+            }
+        }
+    }
+    else
+    {
+        // This glyph is not colliding with anything.
+#if !defined GRAPHITE2_NTRACING
+        if (dbgout)
+        {
+            *dbgout << json::object
+                            << "missed" << objectid(dslot(seg, slotFix));
+            coll.outputJsonDbg(dbgout, seg, -1);
+            *dbgout << json::close;
+        }
+#endif
+    }
+
+    // Set the is-collision flag bit.
+    if (isCol)
+    { cFix->setFlags(cFix->flags() | SlotCollision::COLL_ISCOL | SlotCollision::COLL_KNOWN); }
+    else
+    { cFix->setFlags((cFix->flags() & ~SlotCollision::COLL_ISCOL) | SlotCollision::COLL_KNOWN); }
+    hasCol |= isCol;
+    return true;
+}
+
+float Pass::resolveKern(Segment *seg, Slot *slotFix, GR_MAYBE_UNUSED Slot *start, int dir,
+    float &ymin, float &ymax, json *const dbgout) const
+{
+    Slot *nbor; // neighboring slot
+    float currSpace = 0.;
+    bool collides = false;
+    unsigned int space_count = 0;
+    Slot *base = slotFix;
+    while (base->attachedTo())
+        base = base->attachedTo();
+    SlotCollision *cFix = seg->collisionInfo(base);
+    const GlyphCache &gc = seg->getFace()->glyphs();
+    const Rect &bbb = seg->theGlyphBBoxTemporary(slotFix->gid());
+    const float by = slotFix->origin().y + cFix->shift().y;
+
+    if (base != slotFix)
+    {
+        cFix->setFlags(cFix->flags() | SlotCollision::COLL_KERN | SlotCollision::COLL_FIX);
+        return 0;
+    }
+    bool seenEnd = (cFix->flags() & SlotCollision::COLL_END) != 0;
+    bool isInit = false;
+    KernCollider coll(dbgout);
+
+    ymax = max(by + bbb.tr.y, ymax);
+    ymin = min(by + bbb.bl.y, ymin);
+    for (nbor = slotFix->next(); nbor; nbor = nbor->next())
+    {
+        if (nbor->isChildOf(base))
+            continue;
+        if (!gc.check(nbor->gid()))
+            return 0.;
+        const Rect &bb = seg->theGlyphBBoxTemporary(nbor->gid());
+        SlotCollision *cNbor = seg->collisionInfo(nbor);
+        if ((bb.bl.y == 0.f && bb.tr.y == 0.f) || (cNbor->flags() & SlotCollision::COLL_ISSPACE))
+        {
+            if (m_kernColls == InWord)
+                break;
+            // Add space for a space glyph.
+            currSpace += nbor->advance();
+            ++space_count;
+        }
+        else
+        {
+            space_count = 0;
+            if (nbor != slotFix && !cNbor->ignore())
+            {
+                seenEnd = true;
+                if (!isInit)
+                {
+                    if (!coll.initSlot(seg, slotFix, cFix->limit(), cFix->margin(),
+                                    cFix->shift(), cFix->offset(), dir, ymin, ymax, dbgout))
+                        return 0.;
+                    isInit = true;
+                }
+                collides |= coll.mergeSlot(seg, nbor, cNbor->shift(), currSpace, dir, dbgout);
+            }
+        }
+        if (cNbor->flags() & SlotCollision::COLL_END)
+        {
+            if (seenEnd && space_count < 2)
+                break;
+            else
+                seenEnd = true;
+        }
+    }
+    if (collides)
+    {
+        Position mv = coll.resolve(seg, slotFix, dir, dbgout);
+        coll.shift(mv, dir);
+        Position delta = slotFix->advancePos() + mv - cFix->shift();
+        slotFix->advance(delta);
+        cFix->setShift(mv);
+        return mv.x;
+    }
+    return 0.;
+}