docs/depend-for-closure.md

# Using Depend for Closure Computation

The depend API can be used to compute glyph closures - determining which glyphs
are reachable from a given set of input codepoints and active features. This
document explains how to compute closures using the depend graph and provides a
reference implementation.

## Computing Closure with Depend

To compute a closure using the depend graph:

1. **Map input codepoints to starting glyphs** using `hb_font_get_nominal_glyph()`
2. **Handle Unicode Variation Sequences** using `hb_font_get_variation_glyph()` for
   UVS-based glyph expansion (not in depend graph)
3. **Initialize the reachable set** with these starting glyphs
4. **Expand through dependencies** by following edges in the depend graph
5. **Filter by active features** to only follow edges for enabled GSUB features
6. **Handle ligatures correctly** - only add ligature outputs when all component
   glyphs are present
7. **Check context requirements** - only follow edges when positional requirements
   (backtrack/lookahead) are satisfied

### Context Set Filtering

Context and ChainContext GSUB rules have positional requirements encoded in the
context_set field. Each context_set specifies which backtrack and/or lookahead
glyphs must be present for a dependency edge to apply.

When context_set filtering is implemented, recent testing has not generated any
over-approximation cases - the depend-based closure matches the subset-based
closure in all tested scenarios.

**With context_set filtering:** Recent testing shows no over-approximation
**Without context_set filtering:** Conservative over-approximation (safe but may include extra glyphs)

See `docs/depend-api.md` section "Working with Context Sets" for details on the
context_set encoding and how to check context requirements.

### Reference Implementation

The test suite includes a production-quality implementation of depend-based
closure in `test/fuzzing/hb-depend-closure-parity.cc`. The `compute_depend_closure()`
function demonstrates proper handling of:

- Feature filtering (only following edges for active GSUB features)
- Ligature sets (only adding ligature outputs when all components present)
- Context sets (only following edges when positional requirements satisfied)
- Non-GSUB dependencies (glyf, CFF, COLR, MATH)
- UVS handling (via `hb_font_get_variation_glyph()`, separate from depend graph)

Key aspects of the implementation:

```c++
// entry is hb_subset_depend_entry_t

// Feature filtering - only follow GSUB edges for active features
if (entry.table_tag == HB_OT_TAG_GSUB) {
  if (active_features && !hb_set_has(active_features, entry.layout_tag))
    continue;  // Skip edge if feature not active
}

// Context filtering - only follow edges when requirements satisfied
if (entry.context_set_index != HB_CODEPOINT_INVALID) {
  if (!check_context_satisfied(depend, entry.context_set_index, glyphs))
    continue;  // Skip edge if context not satisfied
}

// Ligature handling - only add ligature when all components present
if (entry.ligature_set_index != HB_CODEPOINT_INVALID) {
  hb_set_t *ligature_glyphs = hb_set_create();
  hb_subset_depend_lookup_set(depend, entry.ligature_set_index, ligature_glyphs);

  // Check if all component glyphs are in reachable set
  if (!hb_set_is_subset(ligature_glyphs, glyphs)) {
    hb_set_destroy(ligature_glyphs);
    continue;  // Skip ligature if not all components present
  }
  hb_set_destroy(ligature_glyphs);
}

// Add dependent glyph to closure
if (!hb_set_has(glyphs, entry.dependent)) {
  hb_set_add(glyphs, entry.dependent);
  hb_set_add(to_process, entry.dependent);
}
```

## Table-Specific Closure Behavior

### MATH Closure

MATH edges should be followed in a **single pass**: follow MATH edges for glyphs
that are in the set before the MATH stage, but do NOT follow MATH edges for
glyphs that the MATH stage itself added.  This matches the subsetter's behavior,
which retains MATH-closure glyphs (their outlines are needed for drawing assembly
parts) but strips their own MATH constructions from the subset.

Math layout engines do not recursively stretch assembly parts, so the
second-hop constructions are not functionally needed.

### GSUB Self-Feeding Chains

The depend graph captures all GSUB substitution edges.  When computing transitive
closure, a lookup's output glyph may itself be in the same lookup's coverage,
creating a chain: A → B → C → ... through the same lookup.  No shaper actually
re-applies a lookup to its own output within a single feature application, so
these chains are over-approximation relative to real shaping behavior.

The subsetter's iterative closure (`HB_CLOSURE_MAX_STAGES`) truncates these
chains.  The depend closure, following edges to a fixed point, may go further.

To detect this condition (only relevant when unexpected over-approximation is
found without flagged edges):

1. For each active GSUB feature, collect source glyphs and dependent glyphs
2. If those sets intersect for any feature, the font has **self-feeding potential**
3. Trace extra glyphs through self-feeding feature edges from the subset closure
4. If all extra glyphs are reachable through self-feeding chains, the
   over-approximation is a known artifact of self-feeding, not a bug

This detection only runs on the failure path and is O(edges), so real fonts pay
no cost.  In practice, well-formed fonts do not have self-feeding lookups.

## Edge Flags and Over-Approximation Detection

Each dependency edge has an optional `flags` field that indicates potential over-approximation:

- **`HB_SUBSET_DEPEND_EDGE_FLAG_FROM_CONTEXT_POSITION` (0x01)**: Edge from a multi-position
  contextual rule
- **`HB_SUBSET_DEPEND_EDGE_FLAG_FROM_NESTED_CONTEXT` (0x02)**: Edge from a nested contextual
  lookup

When computing closure, track whether any flagged edges contributed to the result:

```c++
bool hit_flagged_edge = false;

// When following an edge (entry is hb_subset_depend_entry_t)...
if (!hb_set_has(closure, entry.dependent)) {
  hb_set_add(closure, entry.dependent);
  if (entry.flags & (HB_SUBSET_DEPEND_EDGE_FLAG_FROM_CONTEXT_POSITION |
                     HB_SUBSET_DEPEND_EDGE_FLAG_FROM_NESTED_CONTEXT))
    hit_flagged_edge = true;
}

// After closure computation...
if (depend_closure.is_superset_of(subset_closure)) {
  if (hit_flagged_edge)
    printf("Expected over-approximation (hit flagged edge)\n");
  else
    printf("UNEXPECTED over-approximation (bug)\n");
}
```

## Optional Over-Approximation

You can choose to skip context_set checking for:

- **Simpler implementation** - Fewer steps, less complex code
- **Coverage analysis** - Finding all glyphs that participate in a feature, regardless
  of whether they're reachable for specific input
- **Conservative estimates** - Ensuring no glyphs are missed

Skipping context_set produces a safe over-approximation - all needed glyphs are
included, possibly with some additional glyphs that wouldn't be reached for the
specific input.

## Use Cases

### Font Subsetting

Determine which glyphs must be retained to properly render a specific set of
characters, accounting for all OpenType substitutions and compositions.

With context_set filtering, depend-based subsetting produces results that match
subset-based subsetting in recent testing.

### Coverage Analysis

Analyze which features or scripts require which glyphs. For this use case,
skipping context_set filtering may be desirable - it shows all glyphs that
participate in a feature, not just those reachable for specific input.

### Font Segmentation

Partition a font into smaller subsets where each segment contains glyphs reachable
from a specific set of input characters, enabling more efficient font delivery
for web applications.

### Testing

Verify that font modifications haven't inadvertently broken glyph references or
substitution chains. The depend graph provides a complete view of font structure
that can be compared before and after modifications.

## Implementation Notes

### Non-GSUB Dependencies

Dependencies from non-GSUB tables do not require context filtering:
- **Composite glyphs (glyf, CFF)**: Structural component relationships
- **Color layers (COLR)**: Layer composition
- **Math variants (MATH)**: Size variant relationships

These dependencies should always be followed during closure computation.

**Note**: Unicode Variation Sequences (UVS) are handled separately via
`hb_font_get_variation_glyph()` and are not part of the depend graph.

### Feature Filtering

GSUB edges should be filtered by active features. The layout_tag field contains
the feature tag for GSUB dependencies. Only follow edges where the feature is
active in your shaping configuration.

### Ligature Filtering

Ligature dependencies should only be followed when ALL component glyphs in the
ligature_set are present in the current closure. This prevents adding ligature
outputs prematurely.

## Further Reading

For detailed API documentation:
- `docs/depend-api.md` - API usage guide with examples
- `docs/depend-implementation.md` - Implementation details and architecture

For reference implementation:
- `test/fuzzing/hb-depend-closure-parity.cc` - Production-quality closure computation
- `test/api/test-ot-depend.c` - Unit tests for depend API