class RubyLsp::Document

def locate(node, char_position, node_types: [])
  queue = T.let(node.child_nodes.compact, T::Array[T.nilable(Prism::Node)])
  closest = node
  parent = T.let(nil, T.nilable(Prism::Node))
  nesting = T.let([], T::Array[T.any(Prism::ClassNode, Prism::ModuleNode)])
  until queue.empty?
    candidate = queue.shift
    # Skip nil child nodes
    next if candidate.nil?
    # Add the next child_nodes to the queue to be processed. The order here is important! We want to move in the
    # same order as the visiting mechanism, which means searching the child nodes before moving on to the next
    # sibling
    T.unsafe(queue).unshift(*candidate.child_nodes)
    # Skip if the current node doesn't cover the desired position
    loc = candidate.location
    next unless (loc.start_offset...loc.end_offset).cover?(char_position)
    # If the node's start character is already past the position, then we should've found the closest node
    # already
    break if char_position < loc.start_offset
    # If the candidate starts after the end of the previous nesting level, then we've exited that nesting level and
    # need to pop the stack
    previous_level = nesting.last
    nesting.pop if previous_level && loc.start_offset > previous_level.location.end_offset
    # Keep track of the nesting where we found the target. This is used to determine the fully qualified name of the
    # target when it is a constant
    if candidate.is_a?(Prism::ClassNode) || candidate.is_a?(Prism::ModuleNode)
      nesting << candidate
    end
    # If there are node types to filter by, and the current node is not one of those types, then skip it
    next if node_types.any? && node_types.none? { |type| candidate.class == type }
    # If the current node is narrower than or equal to the previous closest node, then it is more precise
    closest_loc = closest.location
    if loc.end_offset - loc.start_offset <= closest_loc.end_offset - closest_loc.start_offset
      parent = closest
      closest = candidate
    end
  end
  [closest, parent, nesting.map { |n| n.constant_path.location.slice }]
end