class Parser::Source::TreeRewriter::Action

def analyse_hierarchy(action)
  r = action.range
  # left_index is the index of the first child that isn't completely to the left of action
  left_index = bsearch_child_index { |child| child.range.end_pos > r.begin_pos }
  # right_index is the index of the first child that is completely on the right of action
  start = left_index == 0 ? 0 : left_index - 1  # See "corner case" below for reason of -1
  right_index = bsearch_child_index(start) { |child| child.range.begin_pos >= r.end_pos }
  center = right_index - left_index
  case center
  when 0
    # All children are disjoint from action, nothing else to do
  when -1
    # Corner case: if a child has empty range == action's range
    # then it will appear to be both disjoint and to the left of action,
    # as well as disjoint and to the right of action.
    # Since ranges are equal, we return it as parent
    left_index -= 1  # Fix indices, as otherwise this child would be
    right_index += 1 # considered as a sibbling (both left and right!)
    parent = @children[left_index]
  else
    overlap_left = @children[left_index].range.begin_pos <=> r.begin_pos
    overlap_right = @children[right_index-1].range.end_pos <=> r.end_pos
    # For one child to be the parent of action, we must have:
    if center == 1 && overlap_left <= 0 && overlap_right >= 0
      parent = @children[left_index]
    else
      # Otherwise consider all non disjoint elements (center) to be contained...
      contained = @children[left_index...right_index]
      fusible = check_fusible(action,
        (contained.shift if overlap_left < 0),  # ... but check first and last one
        (contained.pop if overlap_right > 0)    # ... for overlaps
      )
    end
  end
  {
    parent: parent,
    sibbling_left: @children[0...left_index],
    sibbling_right: @children[right_index...@children.size],
    fusible: fusible,
    child: contained,
  }
end

def bsearch_child_index(from = 0)
  size = @children.size
  (from...size).bsearch { |i| yield @children[i] } || size
end

def call_enforcer_for_merge(action)
  @enforcer.call(:different_replacements) do
    if @replacement && action.replacement && @replacement != action.replacement
      {range: @range, replacement: action.replacement, other_replacement: @replacement}
    end
  end
end

def check_fusible(action, *fusible)
  fusible.compact!
  return if fusible.empty?
  fusible.each do |child|
    kind = action.insertion? || child.insertion? ? :crossing_insertions : :crossing_deletions
    @enforcer.call(kind) { {range: action.range, conflict: child.range} }
  end
  fusible
end

def combine(action)
  return self if action.empty? # Ignore empty action
  do_combine(action)
end

def combine_children(more_children)
  more_children.inject(self) do |parent, new_child|
    parent.place_in_hierarchy(new_child)
  end
end

def contract
  raise 'Empty actions can not be contracted' if empty?
  return self if insertion?
  range = @range.with(
    begin_pos: children.first.range.begin_pos,
    end_pos: children.last.range.end_pos,
  )
  with(range: range)
end

def do_combine(action)
  if action.range == @range
    merge(action)
  else
    place_in_hierarchy(action)
  end
end

def empty?
  @insert_before.empty? &&
    @insert_after.empty? &&
    @children.empty? &&
    (@replacement == nil || (@replacement.empty? && @range.empty?))
end

def fuse_deletions(action, fusible, other_sibblings)
  without_fusible = with(children: other_sibblings)
  fused_range = [action, *fusible].map(&:range).inject(:join)
  fused_deletion = action.with(range: fused_range)
  without_fusible.do_combine(fused_deletion)
end

def initialize(range, enforcer,
     insert_before: '',
     replacement: nil,
     insert_after: '',
     children: []
  )
  @range, @enforcer, @children, @insert_before, @replacement, @insert_after =
    range, enforcer, children.freeze, insert_before.freeze, replacement, insert_after.freeze
  freeze
end

def insertion?
  !insert_before.empty? || !insert_after.empty? || (replacement && !replacement.empty?)
end

def merge(action)
  call_enforcer_for_merge(action)
  with(
    insert_before: "#{action.insert_before}#{insert_before}",
    replacement: action.replacement || @replacement,
    insert_after: "#{insert_after}#{action.insert_after}",
  ).combine_children(action.children)
end

def moved(source_buffer, offset)
  moved_range = ::Parser::Source::Range.new(
    source_buffer,
    @range.begin_pos + offset,
    @range.end_pos + offset
  )
  with(
    range: moved_range,
    children: children.map { |child| child.moved(source_buffer, offset) }
  )
end

def nested_actions
  actions = []
  actions << [:wrap, @range, @insert_before, @insert_after] if !@insert_before.empty? ||
                                                               !@insert_after.empty?
  actions << [:replace, @range, @replacement] if @replacement
  actions.concat(@children.flat_map(&:nested_actions))
end

def ordered_replacements
  reps = []
  reps << [@range.begin, @insert_before] unless @insert_before.empty?
  reps << [@range, @replacement] if @replacement
  reps.concat(@children.flat_map(&:ordered_replacements))
  reps << [@range.end, @insert_after] unless @insert_after.empty?
  reps
end

def place_in_hierarchy(action)
  family = analyse_hierarchy(action)
  if family[:fusible]
    fuse_deletions(action, family[:fusible], [*family[:sibbling_left], *family[:child], *family[:sibbling_right]])
  else
    extra_sibbling = if family[:parent]  # action should be a descendant of one of the children
      family[:parent].do_combine(action)
    elsif family[:child]                 # or it should become the parent of some of the children,
      action.with(children: family[:child], enforcer: @enforcer)
        .combine_children(action.children)
    else                                 # or else it should become an additional child
      action
    end
    with(children: [*family[:sibbling_left], extra_sibbling, *family[:sibbling_right]])
  end
end

def swallow(children)
  @enforcer.call(:swallowed_insertions) do
    insertions = children.select(&:insertion?)
    {range: @range, conflict: insertions.map(&:range)} unless insertions.empty?
  end
  []
end

def with(range: @range, enforcer: @enforcer, children: @children, insert_before: @insert_before, replacement: @replacement, insert_after: @insert_after)
  children = swallow(children) if replacement
  self.class.new(range, enforcer, children: children, insert_before: insert_before, replacement: replacement, insert_after: insert_after)
end