src/graph/ligature-graph.hh - third_party/harfbuzz - Git at Google



            /*

            
             * Copyright © 2025  Google, Inc.

            
             *

            
             *  This is part of HarfBuzz, a text shaping library.

            
             *

            
             * Permission is hereby granted, without written agreement and without

            
             * license or royalty fees, to use, copy, modify, and distribute this

            
             * software and its documentation for any purpose, provided that the

            
             * above copyright notice and the following two paragraphs appear in

            
             * all copies of this software.

            
             *

            
             * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR

            
             * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES

            
             * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN

            
             * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH

            
             * DAMAGE.

            
             *

            
             * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,

            
             * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND

            
             * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS

            
             * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO

            
             * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

            
             *

            
             * Google Author(s): Garret Rieger

            
             */


            #ifndef GRAPH_LIGATURE_GRAPH_HH

            
            #define GRAPH_LIGATURE_GRAPH_HH


            #include "graph.hh"

            
            #include "../OT/Layout/GSUB/LigatureSubst.hh"

            
            #include "../OT/Layout/GSUB/LigatureSubstFormat1.hh"

            
            #include "../OT/Layout/GSUB/LigatureSet.hh"

            
            #include "../OT/Layout/types.hh"

            
            #include <algorithm>

            
            #include <utility>


            namespace graph {


            struct LigatureSet : public OT::Layout::GSUB_impl::LigatureSet<SmallTypes>

            
            {

            
              bool sanitize (const graph_t::vertex_t& vertex) const

            
              {

            
                size_t vertex_len = vertex.obj.tail - vertex.obj.head;

            
                if (vertex_len < OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size) return false;

            
                hb_barrier ();


                size_t total_len = ligature.get_size() + OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size - ligature.len.get_size();

            
                if (vertex_len < total_len) {

            
                  return false;

            
                }

            
                return true;

            
              }

            
            };


            struct LigatureSubstFormat1 : public OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>

            
            {

            
              bool sanitize (const graph_t::vertex_t& vertex) const

            
              {

            
                size_t vertex_len = vertex.obj.tail - vertex.obj.head;

            
                unsigned min_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size;

            
                if (vertex_len < min_size) return false;

            
                hb_barrier ();


                return vertex_len >=

            
                    min_size + ligatureSet.get_size() - ligatureSet.len.get_size();

            
              }


              hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,

            
                                                     unsigned this_index)

            
              {

            
                auto split_points = compute_split_points(c, this_index);

            
                if (!split_points)

            
                  return hb_vector_t<unsigned> ();


                split_context_t split_context {

            
                  c,

            
                  this,

            
                  this_index,

            
                  total_number_ligas(c, this_index),

            
                  liga_counts(c, this_index),

            
                };

            
                return actuate_subtable_split<split_context_t> (split_context, split_points);

            
              }


             private:

            
              unsigned total_number_ligas(gsubgpos_graph_context_t& c, unsigned this_index) const {

            
                unsigned total = 0;

            
                for (unsigned i = 0; i < ligatureSet.len; i++)

            
                {

            
                  auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);

            
                  if (!liga_set.table) {

            
                    return 0;

            
                  }

            
                  total += liga_set.table->ligature.len;

            
                }

            
                return total;

            
              }


              hb_vector_t<unsigned> liga_counts(gsubgpos_graph_context_t& c, unsigned this_index) const {

            
                hb_vector_t<unsigned> result;

            
                for (unsigned i = 0; i < ligatureSet.len; i++)

            
                {

            
                  auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);

            
                  result.push(!liga_set.table ? 0 : liga_set.table->ligature.len);

            
                }

            
                return result;

            
              }


              template <graph_t::vertex_mutability_t mutability>

            
              hb_vector_t<unsigned> ligature_index_to_object_id(const graph_t::vertex_and_table_t<LigatureSet, mutability>& liga_set) const {

            
                hb_vector_t<unsigned> map;

            
                map.resize_exact(liga_set.table->ligature.len);

            
                if (map.in_error()) return map;


                for (unsigned i = 0; i < map.length; i++) {

            
                  map[i] = (unsigned) -1;

            
                }


                for (const auto& l : liga_set.vertex->obj.real_links) {

            
                  if (l.position < 2) continue;

            
                  unsigned array_index = (l.position - 2) / 2;

            
                  map[array_index] = l.objidx;

            
                }

            
                return map;

            
              }


              hb_vector_t<unsigned> compute_split_points(gsubgpos_graph_context_t& c,

            
                                                         unsigned this_index) const

            
              {

            
                // For ligature subst coverage is always packed last, and as a result is where an overflow

            
                // will happen if there is one, so we can check the estimate length of the

            
                // LigatureSubstFormat1 -> Coverage offset length which is the sum of all data in the

            
                // retained sub graph except for the coverage table itself.

            
                const unsigned base_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size;

            
                unsigned accumulated = base_size;


                unsigned ligature_index = 0;

            
                hb_vector_t<unsigned> split_points;

            
                for (unsigned i = 0; i < ligatureSet.len; i++)

            
                {

            
                  accumulated += OT::HBUINT16::static_size; // for ligature set offset

            
                  accumulated += OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size; // for ligature set table


                  auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);

            
                  if (!liga_set.table) {

            
                    return hb_vector_t<unsigned> {};

            
                  }


                  // Finding the object id associated with an array index is O(n)

            
                  // so to avoid O(n^2), precompute the mapping by scanning through

            
                  // all links

            
                  auto index_to_id = ligature_index_to_object_id(liga_set);

            
                  if (index_to_id.in_error()) return hb_vector_t<unsigned>();


                  for (unsigned j = 0; j < liga_set.table->ligature.len; j++)

            
                  {

            
                    const unsigned liga_id = index_to_id[j];

            
                    if (liga_id == (unsigned) -1) continue; // no outgoing link, ignore

            
                    const unsigned liga_size = c.graph.vertices_[liga_id].table_size ();


                    accumulated += OT::HBUINT16::static_size; // for ligature offset

            
                    accumulated += liga_size; // for the ligature table


                    if (accumulated >= (1 << 16))

            
                    {

            
                      split_points.push(ligature_index);

            
                      // We're going to split such that the current ligature will be in the new sub table.

            
                      // That means we'll have one ligature subst (base_base), one ligature set, and one liga table

            
                      accumulated = base_size + // for liga subst subtable

            
                        (OT::HBUINT16::static_size * 2) + // for liga set and liga offset

            
                        OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size + // for liga set subtable

            
                        liga_size; // for liga sub table

            
                    }


                    ligature_index++;

            
                  }

            
                }


                return split_points;

            
              }


              struct split_context_t

            
              {

            
                gsubgpos_graph_context_t& c;

            
                LigatureSubstFormat1* thiz;

            
                unsigned this_index;

            
                unsigned original_count_;

            
                hb_vector_t<unsigned> liga_counts;


                unsigned original_count ()

            
                {

            
                  return original_count_;

            
                }


                unsigned clone_range (unsigned start, unsigned end)

            
                {

            
                  return thiz->clone_range (c, this_index, liga_counts, start, end);

            
                }


                bool shrink (unsigned count)

            
                {

            
                  return thiz->shrink (c, this_index, original_count(), liga_counts, count);

            
                }

            
              };


              hb_pair_t<unsigned, LigatureSet*> new_liga_set(gsubgpos_graph_context_t& c, unsigned count) const {

            
                unsigned prime_size = OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size

            
                                      + count * SmallTypes::size;


                unsigned prime_id = c.create_node (prime_size);

            
                if (prime_id == (unsigned) -1) return hb_pair(-1, nullptr);


                LigatureSet* prime = (LigatureSet*) c.graph.object (prime_id).head;

            
                prime->ligature.len = count;

            
                return hb_pair(prime_id, prime);

            
              }


              void clear_virtual_links (gsubgpos_graph_context_t& c, unsigned node_index) const

            
              {

            
                auto& obj = c.graph.vertices_[node_index].obj;

            
                for (const auto& l : obj.virtual_links)

            
                {

            
                  auto& child = c.graph.vertices_[l.objidx];

            
                  child.remove_parent(node_index);

            
                }

            
                obj.virtual_links.clear();

            
              }


              void add_virtual_link(gsubgpos_graph_context_t& c, unsigned from, unsigned to) const {

            
                auto& from_obj = c.graph.vertices_[from].obj;

            
                c.graph.vertices_[to].add_parent(from, true);

            
                auto& link = *from_obj.virtual_links.push ();

            
                link.objidx = to;

            
              }


              hb_pair_t<unsigned, unsigned> current_liga_set_bounds (gsubgpos_graph_context_t& c,

            
                                                                     unsigned liga_set_index,

            
                                                                     const hb_serialize_context_t::object_t& liga_set) const

            
              {

            
                // Finds the actual liga indices present in the liga set currently. Takes

            
                // into account those that have been removed by processing.

            
                unsigned min_index = (unsigned) -1;

            
                unsigned max_index = 0;

            
                for (const auto& l : liga_set.real_links) {

            
                  if (l.position < 2) continue;


                  unsigned liga_index = (l.position - 2) / 2;

            
                  min_index = hb_min(min_index, liga_index);

            
                  max_index = hb_max(max_index, liga_index);

            
                }

            
                return hb_pair(min_index, max_index + 1);

            
              }


              void compact_liga_set (gsubgpos_graph_context_t& c, LigatureSet* table, hb_serialize_context_t::object_t& obj) const

            
              {

            
                if (table->ligature.len <= obj.real_links.length) return;


                // compact the remaining linked liga offsets into a continous array and shrink the node as needed.

            
                unsigned to_remove = table->ligature.len - obj.real_links.length;

            
                unsigned new_position = SmallTypes::size;

            
                obj.real_links.qsort(); // for this to work we need to process links in order of position.

            
                for (auto& l : obj.real_links)

            
                {

            
                  l.position = new_position;

            
                  new_position += SmallTypes::size;

            
                }


                table->ligature.len = obj.real_links.length;

            
                obj.tail -= to_remove * SmallTypes::size;

            
              }


              unsigned clone_range (gsubgpos_graph_context_t& c,

            
                                    unsigned this_index,

            
                                    hb_vector_t<unsigned> liga_counts,

            
                                    unsigned start, unsigned end) const

            
              {

            
                DEBUG_MSG (SUBSET_REPACK, nullptr,

            
                           "  Cloning LigatureSubstFormat1 (%u) range [%u, %u).", this_index, start, end);


                // Create an oversized new liga subst, we'll adjust the size down later. We don't know

            
                // the final size until we process it but we also need it to exist while we're processing

            
                // so that nodes can be moved to it as needed.

            
                unsigned prime_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size

            
                                      + ligatureSet.get_size() - ligatureSet.len.get_size();


                unsigned liga_subst_prime_id = c.create_node (prime_size);

            
                if (liga_subst_prime_id == (unsigned) -1) return -1;


                LigatureSubstFormat1* liga_subst_prime = (LigatureSubstFormat1*) c.graph.object (liga_subst_prime_id).head;

            
                liga_subst_prime->format = this->format;

            
                liga_subst_prime->ligatureSet.len = this->ligatureSet.len;


                // Create a place holder coverage prime id since we need to add virtual links to it while

            
                // generating liga and liga sets. Afterwards it will be updated to have the correct coverage.

            
                unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage);

            
                unsigned coverage_prime_id = c.graph.duplicate(coverage_id);

            
                auto& coverage_prime_vertex = c.graph.vertices_[coverage_prime_id];

            
                auto* coverage_prime_link = c.graph.vertices_[liga_subst_prime_id].obj.real_links.push ();

            
                coverage_prime_link->width = SmallTypes::size;

            
                coverage_prime_link->objidx = coverage_prime_id;

            
                coverage_prime_link->position = 2;

            
                coverage_prime_vertex.add_parent (liga_subst_prime_id, false);


                // Locate all liga sets with ligas between start and end.

            
                // Clone or move them as needed.

            
                unsigned count = 0;

            
                unsigned liga_set_count = 0;

            
                unsigned liga_set_start = -1;

            
                unsigned liga_set_end = 0; // inclusive

            
                for (unsigned i = 0; i < liga_counts.length; i++)

            
                {

            
                  unsigned num_ligas = liga_counts[i];


                  unsigned current_start = count;

            
                  unsigned current_end = count + num_ligas;


                  if (current_start >= end || start >= current_end) {

            
                    // No intersection, so just skip

            
                    count += num_ligas;

            
                    continue;

            
                  }


                  auto liga_set = c.graph.as_mutable_table<LigatureSet>(this_index, &ligatureSet[i]);

            
                  if (!liga_set.table) {

            
                    return -1;

            
                  }


                  unsigned liga_set_index = liga_set.index;

            
                  // Bounds may need to be adjusted if some ligas have been previously removed.

            
                  hb_pair_t<unsigned, unsigned> liga_bounds = current_liga_set_bounds(c, liga_set_index, liga_set.vertex->obj);

            
                  current_start = hb_max(count + liga_bounds.first, current_start);

            
                  current_end = hb_min(count + liga_bounds.second, current_end);


                  unsigned liga_set_prime_id;

            
                  if (current_start >= start && current_end <= end) {

            
                    // This liga set is fully contined within [start, end)

            
                    // We can move the entire ligaset to the new liga subset object.

            
                    liga_set_end = i;

            
                    if (i < liga_set_start) liga_set_start = i;

            
                    liga_set_prime_id = c.graph.move_child<> (this_index,

            
                                          &ligatureSet[i],

            
                                          liga_subst_prime_id,

            
                                          &liga_subst_prime->ligatureSet[liga_set_count++]);

            
                    compact_liga_set(c, liga_set.table, liga_set.vertex->obj);

            
                  }

            
                  else

            
                  {

            
                    // This liga set partially overlaps [start, end). We'll need to create

            
                    // a new liga set sub table and move the intersecting ligas to it.

            
                    unsigned start_index = hb_max(start, current_start) - count;

            
                    unsigned end_index = hb_min(end, current_end) - count;

            
                    unsigned liga_count = end_index - start_index;

            
                    auto result = new_liga_set(c, liga_count);

            
                    liga_set_prime_id = result.first;

            
                    if (liga_set_prime_id == (unsigned) -1) return -1;


                    c.graph.move_children<OT::Offset16>(

            
                      liga_set_index,

            
                      2 + start_index * 2,

            
                      2 + end_index * 2,

            
                      liga_set_prime_id,

            
                      2);


                    liga_set_end = i;

            
                    if (i < liga_set_start) liga_set_start = i;

            
                    c.graph.add_link(&liga_subst_prime->ligatureSet[liga_set_count++], liga_subst_prime_id, liga_set_prime_id);

            
                  }


                  // The new liga and all children set needs to have a virtual link to the new coverage table:

            
                  auto& liga_set_prime = c.graph.vertices_[liga_set_prime_id].obj;

            
                  clear_virtual_links(c, liga_set_prime_id);

            
                  add_virtual_link(c, liga_set_prime_id, coverage_prime_id);

            
                  for (const auto& l : liga_set_prime.real_links) {

            
                    clear_virtual_links(c, l.objidx);

            
                    add_virtual_link(c, l.objidx, coverage_prime_id);

            
                  }


                  count += num_ligas;

            
                }


                c.graph.vertices_[liga_subst_prime_id].obj.tail -= (liga_subst_prime->ligatureSet.len - liga_set_count) * SmallTypes::size;

            
                liga_subst_prime->ligatureSet.len = liga_set_count;


                if (!Coverage::filter_coverage (c,

            
                                                coverage_prime_id,

            
                                                liga_set_start, liga_set_end + 1))

            
                  return -1;


                return liga_subst_prime_id;

            
              }


              bool shrink (gsubgpos_graph_context_t& c,

            
                           unsigned this_index,

            
                           unsigned old_count,

            
                           hb_vector_t<unsigned> liga_counts,

            
                           unsigned count)

            
              {

            
                DEBUG_MSG (SUBSET_REPACK, nullptr,

            
                           "  Shrinking LigatureSubstFormat1 (%u) to [0, %u).",

            
                           this_index,

            
                           count);

            
                if (count >= old_count)

            
                  return true;


                hb_set_t retained_indices;

            
                unsigned new_liga_set_count = 0;

            
                for (unsigned i = 0; i < liga_counts.length; i++)

            
                {

            
                  auto liga_set = c.graph.as_mutable_table<LigatureSet>(this_index, &ligatureSet[i]);

            
                  if (!liga_set.table) {

            
                    return false;

            
                  }


                  // We need the virtual links to coverage removed from all descendants on this liga subst.

            
                  // If any are left when we try to mutate the coverage table later it will be unnessecarily

            
                  // duplicated. Code later on will re-add the virtual links as needed (via retained_indices).

            
                  clear_virtual_links(c, liga_set.index);

            
                  retained_indices.add(liga_set.index);


                  auto index_to_id = ligature_index_to_object_id(liga_set);

            
                  if (index_to_id.in_error()) return false;


                  for (unsigned i = 0; i < liga_set.table->ligature.len; i++) {

            
                    unsigned liga_index = index_to_id[i];

            
                    if (liga_index != (unsigned) -1) {

            
                      clear_virtual_links(c, liga_index);

            
                      retained_indices.add(liga_index);

            
                    }

            
                  }


                  unsigned num_ligas = liga_counts[i];

            
                  if (num_ligas >= count) {

            
                    // drop the trailing liga's from this set and all subsequent liga sets

            
                    unsigned num_ligas_to_remove = num_ligas - count;

            
                    new_liga_set_count = i + 1;

            
                    c.graph.vertices_[liga_set.index].obj.tail -= num_ligas_to_remove * SmallTypes::size;

            
                    liga_set.table->ligature.len = count;

            
                    break;

            
                  } else {

            
                    count -= num_ligas;

            
                  }

            
                }


                // Adjust liga set array

            
                auto& this_vertex = c.graph.vertices_[this_index];

            
                this_vertex.obj.tail -= (ligatureSet.len - new_liga_set_count) * SmallTypes::size;

            
                ligatureSet.len = new_liga_set_count;


                // Coverage matches the number of liga sets so rebuild as needed

            
                unsigned coverage_idx = c.graph.index_for_offset (this_index, &this->coverage);

            
                if (coverage_idx == (unsigned) -1) return false;


                auto& coverage_v = c.graph.vertices_[coverage_idx];

            
                unsigned coverage_size = coverage_v.table_size ();

            
                Coverage* coverage_table = (Coverage*) coverage_v.obj.head;


                if (coverage_v.is_shared ())

            
                {

            
                  coverage_idx = c.graph.remap_child (this_index, coverage_idx);

            
                  if (coverage_idx == (unsigned) -1) return false;

            
                }


                for (unsigned i : retained_indices.iter())

            
                  add_virtual_link(c, i, coverage_idx);


                auto new_coverage =

            
                    + hb_zip (coverage_table->iter (), hb_range ())

            
                    | hb_filter ([&] (hb_pair_t<unsigned, unsigned> p) {

            
                      return p.second < new_liga_set_count;

            
                    })

            
                    | hb_map_retains_sorting (hb_first)

            
                    ;


                return Coverage::make_coverage (c, new_coverage, coverage_idx, coverage_size);

            
              }

            
            };


            struct LigatureSubst : public OT::Layout::GSUB_impl::LigatureSubst

            
            {


              hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,

            
                                                     unsigned this_index)

            
              {

            
                switch (u.format.v) {

            
                case 1:

            
                  hb_barrier ();

            
                  return ((LigatureSubstFormat1*)(&u.format1))->split_subtables (c, this_index);

            
            #ifndef HB_NO_BEYOND_64K

            
                case 2: HB_FALLTHROUGH;

            
                  // Don't split 24bit Ligature Subs

            
            #endif

            
                default:

            
                  return hb_vector_t<unsigned> ();

            
                }

            
              }


              bool sanitize (const graph_t::vertex_t& vertex) const

            
              {

            
                size_t vertex_len = vertex.obj.tail - vertex.obj.head;

            
                if (vertex_len < u.format.v.get_size ()) return false;

            
                hb_barrier ();


                switch (u.format.v) {

            
                case 1:

            
                  hb_barrier ();

            
                  return ((LigatureSubstFormat1*)(&u.format1))->sanitize (vertex);

            
            #ifndef HB_NO_BEYOND_64K

            
                case 2:  HB_FALLTHROUGH;

            
            #endif

            
                default:

            
                  // We don't handle format 2 here.

            
                  return false;

            
                }

            
              }

            
            };


            }


            #endif  // GRAPH_LIGATURE_GRAPH_HH

	/*
	* Copyright © 2025 Google, Inc.
	*
	* This is part of HarfBuzz, a text shaping library.
	*
	* Permission is hereby granted, without written agreement and without
	* license or royalty fees, to use, copy, modify, and distribute this
	* software and its documentation for any purpose, provided that the
	* above copyright notice and the following two paragraphs appear in
	* all copies of this software.
	*
	* IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
	* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
	* ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
	* IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
	* DAMAGE.
	*
	* THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
	* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
	* FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
	* ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
	* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
	*
	* Google Author(s): Garret Rieger
	*/

	#ifndef GRAPH_LIGATURE_GRAPH_HH
	#define GRAPH_LIGATURE_GRAPH_HH

	#include "graph.hh"
	#include "../OT/Layout/GSUB/LigatureSubst.hh"
	#include "../OT/Layout/GSUB/LigatureSubstFormat1.hh"
	#include "../OT/Layout/GSUB/LigatureSet.hh"
	#include "../OT/Layout/types.hh"
	#include <algorithm>
	#include <utility>

	namespace graph {

	struct LigatureSet : public OT::Layout::GSUB_impl::LigatureSet<SmallTypes>
	{
	bool sanitize (const graph_t::vertex_t& vertex) const
	{
	size_t vertex_len = vertex.obj.tail - vertex.obj.head;
	if (vertex_len < OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size) return false;
	hb_barrier ();

	size_t total_len = ligature.get_size() + OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size - ligature.len.get_size();
	if (vertex_len < total_len) {
	return false;
	}
	return true;
	}
	};

	struct LigatureSubstFormat1 : public OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>
	{
	bool sanitize (const graph_t::vertex_t& vertex) const
	{
	size_t vertex_len = vertex.obj.tail - vertex.obj.head;
	unsigned min_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size;
	if (vertex_len < min_size) return false;
	hb_barrier ();

	return vertex_len >=
	min_size + ligatureSet.get_size() - ligatureSet.len.get_size();
	}

	hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,
	unsigned this_index)
	{
	auto split_points = compute_split_points(c, this_index);
	if (!split_points)
	return hb_vector_t<unsigned> ();

	split_context_t split_context {
	c,
	this,
	this_index,
	total_number_ligas(c, this_index),
	liga_counts(c, this_index),
	};
	return actuate_subtable_split<split_context_t> (split_context, split_points);
	}

	private:
	unsigned total_number_ligas(gsubgpos_graph_context_t& c, unsigned this_index) const {
	unsigned total = 0;
	for (unsigned i = 0; i < ligatureSet.len; i++)
	{
	auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);
	if (!liga_set.table) {
	return 0;
	}
	total += liga_set.table->ligature.len;
	}
	return total;
	}

	hb_vector_t<unsigned> liga_counts(gsubgpos_graph_context_t& c, unsigned this_index) const {
	hb_vector_t<unsigned> result;
	for (unsigned i = 0; i < ligatureSet.len; i++)
	{
	auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);
	result.push(!liga_set.table ? 0 : liga_set.table->ligature.len);
	}
	return result;
	}

	template <graph_t::vertex_mutability_t mutability>
	hb_vector_t<unsigned> ligature_index_to_object_id(const graph_t::vertex_and_table_t<LigatureSet, mutability>& liga_set) const {
	hb_vector_t<unsigned> map;
	map.resize_exact(liga_set.table->ligature.len);
	if (map.in_error()) return map;

	for (unsigned i = 0; i < map.length; i++) {
	map[i] = (unsigned) -1;
	}

	for (const auto& l : liga_set.vertex->obj.real_links) {
	if (l.position < 2) continue;
	unsigned array_index = (l.position - 2) / 2;
	map[array_index] = l.objidx;
	}
	return map;
	}

	hb_vector_t<unsigned> compute_split_points(gsubgpos_graph_context_t& c,
	unsigned this_index) const
	{
	// For ligature subst coverage is always packed last, and as a result is where an overflow
	// will happen if there is one, so we can check the estimate length of the
	// LigatureSubstFormat1 -> Coverage offset length which is the sum of all data in the
	// retained sub graph except for the coverage table itself.
	const unsigned base_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size;
	unsigned accumulated = base_size;

	unsigned ligature_index = 0;
	hb_vector_t<unsigned> split_points;
	for (unsigned i = 0; i < ligatureSet.len; i++)
	{
	accumulated += OT::HBUINT16::static_size; // for ligature set offset
	accumulated += OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size; // for ligature set table

	auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);
	if (!liga_set.table) {
	return hb_vector_t<unsigned> {};
	}

	// Finding the object id associated with an array index is O(n)
	// so to avoid O(n^2), precompute the mapping by scanning through
	// all links
	auto index_to_id = ligature_index_to_object_id(liga_set);
	if (index_to_id.in_error()) return hb_vector_t<unsigned>();

	for (unsigned j = 0; j < liga_set.table->ligature.len; j++)
	{
	const unsigned liga_id = index_to_id[j];
	if (liga_id == (unsigned) -1) continue; // no outgoing link, ignore
	const unsigned liga_size = c.graph.vertices_[liga_id].table_size ();

	accumulated += OT::HBUINT16::static_size; // for ligature offset
	accumulated += liga_size; // for the ligature table

	if (accumulated >= (1 << 16))
	{
	split_points.push(ligature_index);
	// We're going to split such that the current ligature will be in the new sub table.
	// That means we'll have one ligature subst (base_base), one ligature set, and one liga table
	accumulated = base_size + // for liga subst subtable
	(OT::HBUINT16::static_size * 2) + // for liga set and liga offset
	OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size + // for liga set subtable
	liga_size; // for liga sub table
	}

	ligature_index++;
	}
	}

	return split_points;
	}

	struct split_context_t
	{
	gsubgpos_graph_context_t& c;
	LigatureSubstFormat1* thiz;
	unsigned this_index;
	unsigned original_count_;
	hb_vector_t<unsigned> liga_counts;

	unsigned original_count ()
	{
	return original_count_;
	}

	unsigned clone_range (unsigned start, unsigned end)
	{
	return thiz->clone_range (c, this_index, liga_counts, start, end);
	}

	bool shrink (unsigned count)
	{
	return thiz->shrink (c, this_index, original_count(), liga_counts, count);
	}
	};

	hb_pair_t<unsigned, LigatureSet*> new_liga_set(gsubgpos_graph_context_t& c, unsigned count) const {
	unsigned prime_size = OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size
	+ count * SmallTypes::size;

	unsigned prime_id = c.create_node (prime_size);
	if (prime_id == (unsigned) -1) return hb_pair(-1, nullptr);

	LigatureSet* prime = (LigatureSet*) c.graph.object (prime_id).head;
	prime->ligature.len = count;
	return hb_pair(prime_id, prime);
	}

	void clear_virtual_links (gsubgpos_graph_context_t& c, unsigned node_index) const
	{
	auto& obj = c.graph.vertices_[node_index].obj;
	for (const auto& l : obj.virtual_links)
	{
	auto& child = c.graph.vertices_[l.objidx];
	child.remove_parent(node_index);
	}
	obj.virtual_links.clear();
	}

	void add_virtual_link(gsubgpos_graph_context_t& c, unsigned from, unsigned to) const {
	auto& from_obj = c.graph.vertices_[from].obj;
	c.graph.vertices_[to].add_parent(from, true);
	auto& link = *from_obj.virtual_links.push ();
	link.objidx = to;
	}

	hb_pair_t<unsigned, unsigned> current_liga_set_bounds (gsubgpos_graph_context_t& c,
	unsigned liga_set_index,
	const hb_serialize_context_t::object_t& liga_set) const
	{
	// Finds the actual liga indices present in the liga set currently. Takes
	// into account those that have been removed by processing.
	unsigned min_index = (unsigned) -1;
	unsigned max_index = 0;
	for (const auto& l : liga_set.real_links) {
	if (l.position < 2) continue;

	unsigned liga_index = (l.position - 2) / 2;
	min_index = hb_min(min_index, liga_index);
	max_index = hb_max(max_index, liga_index);
	}
	return hb_pair(min_index, max_index + 1);
	}

	void compact_liga_set (gsubgpos_graph_context_t& c, LigatureSet* table, hb_serialize_context_t::object_t& obj) const
	{
	if (table->ligature.len <= obj.real_links.length) return;

	// compact the remaining linked liga offsets into a continous array and shrink the node as needed.
	unsigned to_remove = table->ligature.len - obj.real_links.length;
	unsigned new_position = SmallTypes::size;
	obj.real_links.qsort(); // for this to work we need to process links in order of position.
	for (auto& l : obj.real_links)
	{
	l.position = new_position;
	new_position += SmallTypes::size;
	}

	table->ligature.len = obj.real_links.length;
	obj.tail -= to_remove * SmallTypes::size;
	}

	unsigned clone_range (gsubgpos_graph_context_t& c,
	unsigned this_index,
	hb_vector_t<unsigned> liga_counts,
	unsigned start, unsigned end) const
	{
	DEBUG_MSG (SUBSET_REPACK, nullptr,
	" Cloning LigatureSubstFormat1 (%u) range [%u, %u).", this_index, start, end);

	// Create an oversized new liga subst, we'll adjust the size down later. We don't know
	// the final size until we process it but we also need it to exist while we're processing
	// so that nodes can be moved to it as needed.
	unsigned prime_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size
	+ ligatureSet.get_size() - ligatureSet.len.get_size();

	unsigned liga_subst_prime_id = c.create_node (prime_size);
	if (liga_subst_prime_id == (unsigned) -1) return -1;

	LigatureSubstFormat1* liga_subst_prime = (LigatureSubstFormat1*) c.graph.object (liga_subst_prime_id).head;
	liga_subst_prime->format = this->format;
	liga_subst_prime->ligatureSet.len = this->ligatureSet.len;

	// Create a place holder coverage prime id since we need to add virtual links to it while
	// generating liga and liga sets. Afterwards it will be updated to have the correct coverage.
	unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage);
	unsigned coverage_prime_id = c.graph.duplicate(coverage_id);
	auto& coverage_prime_vertex = c.graph.vertices_[coverage_prime_id];
	auto* coverage_prime_link = c.graph.vertices_[liga_subst_prime_id].obj.real_links.push ();
	coverage_prime_link->width = SmallTypes::size;
	coverage_prime_link->objidx = coverage_prime_id;
	coverage_prime_link->position = 2;
	coverage_prime_vertex.add_parent (liga_subst_prime_id, false);

	// Locate all liga sets with ligas between start and end.
	// Clone or move them as needed.
	unsigned count = 0;
	unsigned liga_set_count = 0;
	unsigned liga_set_start = -1;
	unsigned liga_set_end = 0; // inclusive
	for (unsigned i = 0; i < liga_counts.length; i++)
	{
	unsigned num_ligas = liga_counts[i];

	unsigned current_start = count;
	unsigned current_end = count + num_ligas;

	if (current_start >= end \|\| start >= current_end) {
	// No intersection, so just skip
	count += num_ligas;
	continue;
	}

	auto liga_set = c.graph.as_mutable_table<LigatureSet>(this_index, &ligatureSet[i]);
	if (!liga_set.table) {
	return -1;
	}

	unsigned liga_set_index = liga_set.index;
	// Bounds may need to be adjusted if some ligas have been previously removed.
	hb_pair_t<unsigned, unsigned> liga_bounds = current_liga_set_bounds(c, liga_set_index, liga_set.vertex->obj);
	current_start = hb_max(count + liga_bounds.first, current_start);
	current_end = hb_min(count + liga_bounds.second, current_end);

	unsigned liga_set_prime_id;
	if (current_start >= start && current_end <= end) {
	// This liga set is fully contined within [start, end)
	// We can move the entire ligaset to the new liga subset object.
	liga_set_end = i;
	if (i < liga_set_start) liga_set_start = i;
	liga_set_prime_id = c.graph.move_child<> (this_index,
	&ligatureSet[i],
	liga_subst_prime_id,
	&liga_subst_prime->ligatureSet[liga_set_count++]);
	compact_liga_set(c, liga_set.table, liga_set.vertex->obj);
	}
	else
	{
	// This liga set partially overlaps [start, end). We'll need to create
	// a new liga set sub table and move the intersecting ligas to it.
	unsigned start_index = hb_max(start, current_start) - count;
	unsigned end_index = hb_min(end, current_end) - count;
	unsigned liga_count = end_index - start_index;
	auto result = new_liga_set(c, liga_count);
	liga_set_prime_id = result.first;
	if (liga_set_prime_id == (unsigned) -1) return -1;

	c.graph.move_children<OT::Offset16>(
	liga_set_index,
	2 + start_index * 2,
	2 + end_index * 2,
	liga_set_prime_id,
	2);

	liga_set_end = i;
	if (i < liga_set_start) liga_set_start = i;
	c.graph.add_link(&liga_subst_prime->ligatureSet[liga_set_count++], liga_subst_prime_id, liga_set_prime_id);
	}

	// The new liga and all children set needs to have a virtual link to the new coverage table:
	auto& liga_set_prime = c.graph.vertices_[liga_set_prime_id].obj;
	clear_virtual_links(c, liga_set_prime_id);
	add_virtual_link(c, liga_set_prime_id, coverage_prime_id);
	for (const auto& l : liga_set_prime.real_links) {
	clear_virtual_links(c, l.objidx);
	add_virtual_link(c, l.objidx, coverage_prime_id);
	}

	count += num_ligas;
	}

	c.graph.vertices_[liga_subst_prime_id].obj.tail -= (liga_subst_prime->ligatureSet.len - liga_set_count) * SmallTypes::size;
	liga_subst_prime->ligatureSet.len = liga_set_count;

	if (!Coverage::filter_coverage (c,
	coverage_prime_id,
	liga_set_start, liga_set_end + 1))
	return -1;

	return liga_subst_prime_id;
	}

	bool shrink (gsubgpos_graph_context_t& c,
	unsigned this_index,
	unsigned old_count,
	hb_vector_t<unsigned> liga_counts,
	unsigned count)
	{
	DEBUG_MSG (SUBSET_REPACK, nullptr,
	" Shrinking LigatureSubstFormat1 (%u) to [0, %u).",
	this_index,
	count);
	if (count >= old_count)
	return true;

	hb_set_t retained_indices;
	unsigned new_liga_set_count = 0;
	for (unsigned i = 0; i < liga_counts.length; i++)
	{
	auto liga_set = c.graph.as_mutable_table<LigatureSet>(this_index, &ligatureSet[i]);
	if (!liga_set.table) {
	return false;
	}

	// We need the virtual links to coverage removed from all descendants on this liga subst.
	// If any are left when we try to mutate the coverage table later it will be unnessecarily
	// duplicated. Code later on will re-add the virtual links as needed (via retained_indices).
	clear_virtual_links(c, liga_set.index);
	retained_indices.add(liga_set.index);

	auto index_to_id = ligature_index_to_object_id(liga_set);
	if (index_to_id.in_error()) return false;

	for (unsigned i = 0; i < liga_set.table->ligature.len; i++) {
	unsigned liga_index = index_to_id[i];
	if (liga_index != (unsigned) -1) {
	clear_virtual_links(c, liga_index);
	retained_indices.add(liga_index);
	}
	}

	unsigned num_ligas = liga_counts[i];
	if (num_ligas >= count) {
	// drop the trailing liga's from this set and all subsequent liga sets
	unsigned num_ligas_to_remove = num_ligas - count;
	new_liga_set_count = i + 1;
	c.graph.vertices_[liga_set.index].obj.tail -= num_ligas_to_remove * SmallTypes::size;
	liga_set.table->ligature.len = count;
	break;
	} else {
	count -= num_ligas;
	}
	}

	// Adjust liga set array
	auto& this_vertex = c.graph.vertices_[this_index];
	this_vertex.obj.tail -= (ligatureSet.len - new_liga_set_count) * SmallTypes::size;
	ligatureSet.len = new_liga_set_count;

	// Coverage matches the number of liga sets so rebuild as needed
	unsigned coverage_idx = c.graph.index_for_offset (this_index, &this->coverage);
	if (coverage_idx == (unsigned) -1) return false;

	auto& coverage_v = c.graph.vertices_[coverage_idx];
	unsigned coverage_size = coverage_v.table_size ();
	Coverage* coverage_table = (Coverage*) coverage_v.obj.head;

	if (coverage_v.is_shared ())
	{
	coverage_idx = c.graph.remap_child (this_index, coverage_idx);
	if (coverage_idx == (unsigned) -1) return false;
	}

	for (unsigned i : retained_indices.iter())
	add_virtual_link(c, i, coverage_idx);

	auto new_coverage =
	+ hb_zip (coverage_table->iter (), hb_range ())
	\| hb_filter ([&] (hb_pair_t<unsigned, unsigned> p) {
	return p.second < new_liga_set_count;
	})
	\| hb_map_retains_sorting (hb_first)
	;

	return Coverage::make_coverage (c, new_coverage, coverage_idx, coverage_size);
	}
	};

	struct LigatureSubst : public OT::Layout::GSUB_impl::LigatureSubst
	{

	hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,
	unsigned this_index)
	{
	switch (u.format.v) {
	case 1:
	hb_barrier ();
	return ((LigatureSubstFormat1*)(&u.format1))->split_subtables (c, this_index);
	#ifndef HB_NO_BEYOND_64K
	case 2: HB_FALLTHROUGH;
	// Don't split 24bit Ligature Subs
	#endif
	default:
	return hb_vector_t<unsigned> ();
	}
	}

	bool sanitize (const graph_t::vertex_t& vertex) const
	{
	size_t vertex_len = vertex.obj.tail - vertex.obj.head;
	if (vertex_len < u.format.v.get_size ()) return false;
	hb_barrier ();

	switch (u.format.v) {
	case 1:
	hb_barrier ();
	return ((LigatureSubstFormat1*)(&u.format1))->sanitize (vertex);
	#ifndef HB_NO_BEYOND_64K
	case 2: HB_FALLTHROUGH;
	#endif
	default:
	// We don't handle format 2 here.
	return false;
	}
	}
	};

	}

	#endif // GRAPH_LIGATURE_GRAPH_HH