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 (graph_t::vertex_t& vertex) const
  {
    int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
    if (vertex_len < OT::Layout::GSUB_impl::LigatureSet<SmallTypes>::min_size) return false;
    hb_barrier ();

    int64_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 (graph_t::vertex_t& vertex) const
  {
    int64_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 parent_index,
                                         unsigned this_index)
  {
    auto split_points = compute_split_points(c, parent_index, this_index);
    split_context_t split_context {
      c,
      this,
      c.graph.duplicate_if_shared (parent_index, 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;
  }

  hb_vector_t<unsigned> compute_split_points(gsubgpos_graph_context_t& c,
                                             unsigned parent_index,
                                             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> {};
      }

      for (unsigned j = 0; j < liga_set.table->ligature.len; j++)
      {
        const unsigned liga_id = c.graph.index_for_offset (liga_set.index, &liga_set.table->ligature[j]);
        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_index = c.graph.index_for_offset(this_index, &ligatureSet[i]);
      auto liga_set = c.graph.as_table<LigatureSet>(this_index, &ligatureSet[i]);
      if (!liga_set.table) {
        return -1;
      }

      // 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 liga_count = hb_min(end, current_end) - hb_max(start, current_start);
        auto result = new_liga_set(c, liga_count);
        liga_set_prime_id = result.first;
        LigatureSet* prime = result.second;
        if (liga_set_prime_id == (unsigned) -1) return -1;

        unsigned new_index = 0;
        for (unsigned j = hb_max(start, current_start) - count; j < hb_min(end, current_end) - count; j++) {
          c.graph.move_child<> (liga_set_index,
                                &liga_set.table->ligature[j],
                                liga_set_prime_id,
                                &prime->ligature[new_index++]);
        }

        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_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);
      for (const auto& liga_offset : liga_set.table->ligature) {
        unsigned liga_index = c.graph.index_for_offset(liga_set.index, &liga_offset);
        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
    c.graph.vertices_[this_index].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
    auto coverage = c.graph.as_mutable_table<Coverage> (this_index, &this->coverage);
    if (!coverage) return false;

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

    unsigned coverage_size = coverage.vertex->table_size ();
    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.index, coverage_size);
  }
};

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

  hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,
                                         unsigned parent_index,
                                         unsigned this_index)
  {
    switch (u.format) {
    case 1:
      return ((LigatureSubstFormat1*)(&u.format1))->split_subtables (c, parent_index, 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 (graph_t::vertex_t& vertex) const
  {
    int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
    if (vertex_len < u.format.get_size ()) return false;
    hb_barrier ();

    switch (u.format) {
    case 1:
      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