Subtree ts_subtree_edit()

in lib/src/subtree.c [616:763]

• 113 lines of code
• 28 McCabe index (conditional complexity)

Subtree ts_subtree_edit(Subtree self, const TSInputEdit *edit, SubtreePool *pool) {
  typedef struct {
    Subtree *tree;
    Edit edit;
  } StackEntry;

  Array(StackEntry) stack = array_new();
  array_push(&stack, ((StackEntry) {
    .tree = &self,
    .edit = (Edit) {
      .start = {edit->start_byte, edit->start_point},
      .old_end = {edit->old_end_byte, edit->old_end_point},
      .new_end = {edit->new_end_byte, edit->new_end_point},
    },
  }));

  while (stack.size) {
    StackEntry entry = array_pop(&stack);
    Edit edit = entry.edit;
    bool is_noop = edit.old_end.bytes == edit.start.bytes && edit.new_end.bytes == edit.start.bytes;
    bool is_pure_insertion = edit.old_end.bytes == edit.start.bytes;

    Length size = ts_subtree_size(*entry.tree);
    Length padding = ts_subtree_padding(*entry.tree);
    uint32_t lookahead_bytes = ts_subtree_lookahead_bytes(*entry.tree);
    uint32_t end_byte = padding.bytes + size.bytes + lookahead_bytes;
    if (edit.start.bytes > end_byte || (is_noop && edit.start.bytes == end_byte)) continue;

    // If the edit is entirely within the space before this subtree, then shift this
    // subtree over according to the edit without changing its size.
    if (edit.old_end.bytes <= padding.bytes) {
      padding = length_add(edit.new_end, length_sub(padding, edit.old_end));
    }

    // If the edit starts in the space before this subtree and extends into this subtree,
    // shrink the subtree's content to compensate for the change in the space before it.
    else if (edit.start.bytes < padding.bytes) {
      size = length_sub(size, length_sub(edit.old_end, padding));
      padding = edit.new_end;
    }

    // If the edit is a pure insertion right at the start of the subtree,
    // shift the subtree over according to the insertion.
    else if (edit.start.bytes == padding.bytes && is_pure_insertion) {
      padding = edit.new_end;
    }

    // If the edit is within this subtree, resize the subtree to reflect the edit.
    else {
      uint32_t total_bytes = padding.bytes + size.bytes;
      if (edit.start.bytes < total_bytes ||
         (edit.start.bytes == total_bytes && is_pure_insertion)) {
        size = length_add(
          length_sub(edit.new_end, padding),
          length_sub(size, length_sub(edit.old_end, padding))
        );
      }
    }

    MutableSubtree result = ts_subtree_make_mut(pool, *entry.tree);

    if (result.data.is_inline) {
      if (ts_subtree_can_inline(padding, size, lookahead_bytes)) {
        result.data.padding_bytes = padding.bytes;
        result.data.padding_rows = padding.extent.row;
        result.data.padding_columns = padding.extent.column;
        result.data.size_bytes = size.bytes;
      } else {
        SubtreeHeapData *data = ts_subtree_pool_allocate(pool);
        data->ref_count = 1;
        data->padding = padding;
        data->size = size;
        data->lookahead_bytes = lookahead_bytes;
        data->error_cost = 0;
        data->child_count = 0;
        data->symbol = result.data.symbol;
        data->parse_state = result.data.parse_state;
        data->visible = result.data.visible;
        data->named = result.data.named;
        data->extra = result.data.extra;
        data->fragile_left = false;
        data->fragile_right = false;
        data->has_changes = false;
        data->has_external_tokens = false;
        data->is_missing = result.data.is_missing;
        data->is_keyword = result.data.is_keyword;
        result.ptr = data;
      }
    } else {
      result.ptr->padding = padding;
      result.ptr->size = size;
    }

    ts_subtree_set_has_changes(&result);
    *entry.tree = ts_subtree_from_mut(result);

    Length child_left, child_right = length_zero();
    for (uint32_t i = 0, n = ts_subtree_child_count(*entry.tree); i < n; i++) {
      Subtree *child = &result.ptr->children[i];
      Length child_size = ts_subtree_total_size(*child);
      child_left = child_right;
      child_right = length_add(child_left, child_size);

      // If this child ends before the edit, it is not affected.
      if (child_right.bytes + ts_subtree_lookahead_bytes(*child) < edit.start.bytes) continue;

      // If this child starts after the edit, then we're done processing children.
      if (child_left.bytes > edit.old_end.bytes ||
          (child_left.bytes == edit.old_end.bytes && child_size.bytes > 0 && i > 0)) break;

      // Transform edit into the child's coordinate space.
      Edit child_edit = {
        .start = length_sub(edit.start, child_left),
        .old_end = length_sub(edit.old_end, child_left),
        .new_end = length_sub(edit.new_end, child_left),
      };

      // Clamp child_edit to the child's bounds.
      if (edit.start.bytes < child_left.bytes) child_edit.start = length_zero();
      if (edit.old_end.bytes < child_left.bytes) child_edit.old_end = length_zero();
      if (edit.new_end.bytes < child_left.bytes) child_edit.new_end = length_zero();
      if (edit.old_end.bytes > child_right.bytes) child_edit.old_end = child_size;

      // Interpret all inserted text as applying to the *first* child that touches the edit.
      // Subsequent children are only never have any text inserted into them; they are only
      // shrunk to compensate for the edit.
      if (child_right.bytes > edit.start.bytes ||
          (child_right.bytes == edit.start.bytes && is_pure_insertion)) {
        edit.new_end = edit.start;
      }

      // Children that occur before the edit are not reshaped by the edit.
      else {
        child_edit.old_end = child_edit.start;
        child_edit.new_end = child_edit.start;
      }

      // Queue processing of this child's subtree.
      array_push(&stack, ((StackEntry) {
        .tree = child,
        .edit = child_edit,
      }));
    }
  }

  array_delete(&stack);
  return self;
}