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 "../hb-ot-dual.hh"

            
            #include <algorithm>

            
            #include <utility>


            namespace graph {


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

            
            {

            
              graph_result_t<void> sanitize (const graph_t::vertex_t& vertex) const

            
              {

            
                size_t vertex_len = vertex.table_size ();

            
                if (unlikely (vertex_len < OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size)) return Err(SANITIZE_FAILURE);

            
                hb_barrier ();


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

            
                if (unlikely (vertex_len < total_len)) {

            
                  return Err(SANITIZE_FAILURE);

            
                }

            
                return Ok();

            
              }

            
            };


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

            
            {

            
              graph_result_t<void> sanitize (const graph_t::vertex_t& vertex) const

            
              {

            
                size_t vertex_len = vertex.table_size ();

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

            
                if (unlikely (vertex_len < min_size)) return Err(SANITIZE_FAILURE);

            
                hb_barrier ();


                if (unlikely (vertex_len < min_size + ligatureSet.get_size() - ligatureSet.len.get_size()))

            
                  return Err(SANITIZE_FAILURE);

            
                return Ok();

            
              }


              graph_result_t<hb_vector_t<unsigned>> split_subtables (gsubgpos_graph_context_t& c,

            
                                                                     unsigned this_index)

            
              {

            
                TRY_ASSIGN (auto split_points, compute_split_points(c, this_index));

            
                if (!split_points)

            
                  return Ok(hb_vector_t<unsigned> ());


                TRY_ASSIGN (unsigned total_ligas, total_number_ligas(c, this_index));

            
                TRY_ASSIGN (hb_vector_t<unsigned> counts, liga_counts(c, this_index));

            
                split_context_t split_context {

            
                  c,

            
                  this,

            
                  this_index,

            
                  total_ligas,

            
                  std::move (counts),

            
                };

            
                return actuate_subtable_split<split_context_t> (split_context, split_points);

            
              }


             private:

            
              graph_result_t<unsigned> total_number_ligas(gsubgpos_graph_context_t& c, unsigned this_index) const {

            
                unsigned total = 0;

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

            
                {

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

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

            
                }

            
                return Ok(total);

            
              }


              graph_result_t<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++)

            
                {

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

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

            
                }

            
                return graph_result_t<hb_vector_t<unsigned>>::from(std::move(result), ALLOCATION_FAILURE);

            
              }


              template <graph_t::vertex_mutability_t mutability>

            
              graph_result_t<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;

            
                if (!map.resize_exact(liga_set.table->ligature.len)) return Err(ALLOCATION_FAILURE);


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

            
                  map[i] = HB_GRAPH_INVALID;

            
                }


                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;

            
              }


              graph_result_t<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


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


                  // 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

            
                  TRY_ASSIGN (auto index_to_id, ligature_index_to_object_id (liga_set));


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

            
                  {

            
                    const unsigned liga_id = index_to_id[j];

            
                    if (liga_id == HB_GRAPH_INVALID) 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_;

            
                }


                graph_result_t<unsigned> clone_range (unsigned start, unsigned end)

            
                {

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

            
                }


                graph_result_t<void> shrink (unsigned count)

            
                {

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

            
                }

            
              };


              graph_result_t<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;


                TRY_ASSIGN (unsigned prime_id, c.create_node (prime_size));


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

            
                prime->ligature.len = count;

            
                return Ok(hb_pair(prime_id, prime));

            
              }


              void clear_virtual_links (gsubgpos_graph_context_t& c, unsigned node_index) const

            
              {

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

            
                for (const auto& l : v.obj ().virtual_links)

            
                {

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

            
                  child.remove_parent(node_index);

            
                }

            
                v.clear_virtual_links ();

            
              }


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

            
                if (unlikely (from >= c.graph.vertices_.length || to >= c.graph.vertices_.length)) return Err(OUT_OF_BOUNDS);

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

            
                TRY(c.graph.vertices_[from].add_virtual_link (to));

            
                return Ok();

            
              }


              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 = HB_GRAPH_INVALID;

            
                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, graph_t::vertex_t* v) const

            
              {

            
                const auto& obj = v->obj ();

            
                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;

            
                v->sort_real_links (); // for this to work we need to process links in order of position.

            
                for (auto& l : v->real_links_writer ())

            
                {

            
                  l.position = new_position;

            
                  new_position += SmallTypes::size;

            
                }


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

            
                v->shrink_buffer (to_remove * SmallTypes::size);

            
              }


              graph_result_t<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();


                TRY_ASSIGN (unsigned liga_subst_prime_id, c.create_node (prime_size));


                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.

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

            
                TRY_ASSIGN (unsigned coverage_prime_id, c.graph.duplicate(coverage_id));

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


                TRY(c.graph.vertices_[liga_subst_prime_id].add_real_link (SmallTypes::size, coverage_prime_id, 2));

            
                TRY(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 = HB_GRAPH_INVALID;

            
                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;

            
                  }


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


                  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;

            
                    TRY_ASSIGN (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);

            
                  }

            
                  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;

            
                    TRY_ASSIGN (auto result, new_liga_set(c, liga_count));

            
                    liga_set_prime_id = result.first;


                    TRY (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;

            
                    TRY (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:

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

            
                  clear_virtual_links(c, liga_set_prime_id);

            
                  TRY(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);

            
                    TRY(add_virtual_link(c, l.objidx, coverage_prime_id));

            
                  }


                  count += num_ligas;

            
                }


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

            
                liga_subst_prime->ligatureSet.len = liga_set_count;


                TRY (Coverage::filter_coverage (c,

            
                                                coverage_prime_id,

            
                                                liga_set_start, liga_set_end + 1));


                return Ok(liga_subst_prime_id);

            
              }


              graph_result_t<void> 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 Ok();


                hb_set_t retained_indices;

            
                unsigned new_liga_set_count = 0;

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

            
                {

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


                  // 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);


                  TRY_ASSIGN (auto index_to_id, ligature_index_to_object_id (liga_set));


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

            
                    unsigned liga_index = index_to_id[i];

            
                    if (liga_index != HB_GRAPH_INVALID) {

            
                      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].shrink_buffer (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.shrink_buffer ((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

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


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

            
                unsigned coverage_size = coverage_v.table_size ();

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


                if (coverage_v.is_shared ())

            
                {

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

            
                }


                for (unsigned i : retained_indices.iter())

            
                  TRY(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

            
            {


              graph_result_t<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;

            
                  // 24-bit LigatureSubst already has widened offsets; leave it unsplit.

            
            #endif

            
                default:

            
                  return Ok(hb_vector_t<unsigned> ());

            
                }

            
              }


              graph_result_t<void> sanitize (const graph_t::vertex_t& vertex) const

            
              {

            
                size_t vertex_len = vertex.table_size ();

            
                if (unlikely (vertex_len < u.format.v.get_size ())) return Err(SANITIZE_FAILURE);

            
                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 Err(SANITIZE_FAILURE);

            
                }

            
              }

            
            };


            }


            #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 "../hb-ot-dual.hh"
	#include <algorithm>
	#include <utility>

	namespace graph {

	struct LigatureSet : public OT::Layout::GSUB_impl::LigatureSet<SmallTypes>
	{
	graph_result_t<void> sanitize (const graph_t::vertex_t& vertex) const
	{
	size_t vertex_len = vertex.table_size ();
	if (unlikely (vertex_len < OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size)) return Err(SANITIZE_FAILURE);
	hb_barrier ();

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

	struct LigatureSubstFormat1 : public OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>
	{
	graph_result_t<void> sanitize (const graph_t::vertex_t& vertex) const
	{
	size_t vertex_len = vertex.table_size ();
	unsigned min_size = OT::Layout::GSUB_impl::LigatureSubstFormat1_2<SmallTypes>::min_size;
	if (unlikely (vertex_len < min_size)) return Err(SANITIZE_FAILURE);
	hb_barrier ();

	if (unlikely (vertex_len < min_size + ligatureSet.get_size() - ligatureSet.len.get_size()))
	return Err(SANITIZE_FAILURE);
	return Ok();
	}

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

	TRY_ASSIGN (unsigned total_ligas, total_number_ligas(c, this_index));
	TRY_ASSIGN (hb_vector_t<unsigned> counts, liga_counts(c, this_index));
	split_context_t split_context {
	c,
	this,
	this_index,
	total_ligas,
	std::move (counts),
	};
	return actuate_subtable_split<split_context_t> (split_context, split_points);
	}

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

	graph_result_t<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++)
	{
	TRY_ASSIGN (auto liga_set, c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]));
	result.push(!liga_set.table ? 0 : liga_set.table->ligature.len);
	}
	return graph_result_t<hb_vector_t<unsigned>>::from(std::move(result), ALLOCATION_FAILURE);
	}

	template <graph_t::vertex_mutability_t mutability>
	graph_result_t<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;
	if (!map.resize_exact(liga_set.table->ligature.len)) return Err(ALLOCATION_FAILURE);

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

	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;
	}

	graph_result_t<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

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

	// 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
	TRY_ASSIGN (auto index_to_id, ligature_index_to_object_id (liga_set));

	for (unsigned j = 0; j < liga_set.table->ligature.len; j++)
	{
	const unsigned liga_id = index_to_id[j];
	if (liga_id == HB_GRAPH_INVALID) 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_;
	}

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

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

	graph_result_t<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;

	TRY_ASSIGN (unsigned prime_id, c.create_node (prime_size));

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

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

	graph_result_t<void> add_virtual_link(gsubgpos_graph_context_t& c, unsigned from, unsigned to) const {
	if (unlikely (from >= c.graph.vertices_.length \|\| to >= c.graph.vertices_.length)) return Err(OUT_OF_BOUNDS);
	TRY(c.graph.vertices_[to].add_parent (from, true));
	TRY(c.graph.vertices_[from].add_virtual_link (to));
	return Ok();
	}

	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 = HB_GRAPH_INVALID;
	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, graph_t::vertex_t* v) const
	{
	const auto& obj = v->obj ();
	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;
	v->sort_real_links (); // for this to work we need to process links in order of position.
	for (auto& l : v->real_links_writer ())
	{
	l.position = new_position;
	new_position += SmallTypes::size;
	}

	table->ligature.len = obj.real_links.length;
	v->shrink_buffer (to_remove * SmallTypes::size);
	}

	graph_result_t<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();

	TRY_ASSIGN (unsigned liga_subst_prime_id, c.create_node (prime_size));

	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.
	TRY_ASSIGN (unsigned coverage_id, c.graph.index_for_offset (this_index, &coverage));
	TRY_ASSIGN (unsigned coverage_prime_id, c.graph.duplicate(coverage_id));
	auto& coverage_prime_vertex = c.graph.vertices_[coverage_prime_id];

	TRY(c.graph.vertices_[liga_subst_prime_id].add_real_link (SmallTypes::size, coverage_prime_id, 2));
	TRY(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 = HB_GRAPH_INVALID;
	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;
	}

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

	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;
	TRY_ASSIGN (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);
	}
	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;
	TRY_ASSIGN (auto result, new_liga_set(c, liga_count));
	liga_set_prime_id = result.first;

	TRY (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;
	TRY (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:
	const auto& liga_set_prime = c.graph.vertices_[liga_set_prime_id].obj ();
	clear_virtual_links(c, liga_set_prime_id);
	TRY(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);
	TRY(add_virtual_link(c, l.objidx, coverage_prime_id));
	}

	count += num_ligas;
	}

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

	TRY (Coverage::filter_coverage (c,
	coverage_prime_id,
	liga_set_start, liga_set_end + 1));

	return Ok(liga_subst_prime_id);
	}

	graph_result_t<void> 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 Ok();

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

	// 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);

	TRY_ASSIGN (auto index_to_id, ligature_index_to_object_id (liga_set));

	for (unsigned i = 0; i < liga_set.table->ligature.len; i++) {
	unsigned liga_index = index_to_id[i];
	if (liga_index != HB_GRAPH_INVALID) {
	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].shrink_buffer (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.shrink_buffer ((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
	TRY_ASSIGN (unsigned coverage_idx, c.graph.index_for_offset (this_index, &this->coverage));

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

	if (coverage_v.is_shared ())
	{
	TRY_ASSIGN (coverage_idx, c.graph.remap_child (this_index, coverage_idx));
	}

	for (unsigned i : retained_indices.iter())
	TRY(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
	{

	graph_result_t<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;
	// 24-bit LigatureSubst already has widened offsets; leave it unsplit.
	#endif
	default:
	return Ok(hb_vector_t<unsigned> ());
	}
	}

	graph_result_t<void> sanitize (const graph_t::vertex_t& vertex) const
	{
	size_t vertex_len = vertex.table_size ();
	if (unlikely (vertex_len < u.format.v.get_size ())) return Err(SANITIZE_FAILURE);
	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 Err(SANITIZE_FAILURE);
	}
	}
	};

	}

	#endif // GRAPH_LIGATURE_GRAPH_HH