import { Direction, RectangleMarker, layer, type EditorView, type ViewUpdate } from '@codemirror/view'

const DOM_SELECTION_BACKGROUND_CLASS = 'cm-domSelectionBackground'

type DomSelectionState = 'editor-range' | 'external-range' | 'collapsed-or-none'
const cleanupByView = new WeakMap<EditorView, () => void>()
const RECT_EPSILON = 1
const HORIZONTAL_MERGE_GAP = 4
const VERTICAL_JOIN_GAP = 8

export interface SelectionRectLike {
  left: number
  right: number
  top: number
  bottom: number
}

function getLayerBase(view: EditorView): { left: number; top: number } {
  const rect = view.scrollDOM.getBoundingClientRect()
  const left = view.textDirection === Direction.LTR
    ? rect.left
    : rect.right - view.scrollDOM.clientWidth * view.scaleX

  return {
    left: left - view.scrollDOM.scrollLeft * view.scaleX,
    top: rect.top - view.scrollDOM.scrollTop * view.scaleY,
  }
}

function selectionBelongsToEditor(view: EditorView, selection: Selection): boolean {
  const anchorElement = selection.anchorNode?.nodeType === Node.ELEMENT_NODE
    ? selection.anchorNode as Element
    : selection.anchorNode?.parentElement
  const focusElement = selection.focusNode?.nodeType === Node.ELEMENT_NODE
    ? selection.focusNode as Element
    : selection.focusNode?.parentElement

  return !!anchorElement && view.contentDOM.contains(anchorElement)
    || !!focusElement && view.contentDOM.contains(focusElement)
}

function getDomSelectionState(view: EditorView, selection: Selection | null): DomSelectionState {
  if (!selection || selection.rangeCount === 0 || selection.isCollapsed) {
    return 'collapsed-or-none'
  }

  return selectionBelongsToEditor(view, selection) ? 'editor-range' : 'external-range'
}

function clipRectToBounds(rect: SelectionRectLike, bounds: SelectionRectLike): SelectionRectLike | null {
  const left = Math.max(rect.left, bounds.left)
  const right = Math.min(rect.right, bounds.right)
  const top = Math.max(rect.top, bounds.top)
  const bottom = Math.min(rect.bottom, bounds.bottom)

  if (right - left <= RECT_EPSILON || bottom - top <= RECT_EPSILON) {
    return null
  }

  return { left, right, top, bottom }
}

function sameRect(a: SelectionRectLike, b: SelectionRectLike): boolean {
  return Math.abs(a.left - b.left) <= RECT_EPSILON
    && Math.abs(a.right - b.right) <= RECT_EPSILON
    && Math.abs(a.top - b.top) <= RECT_EPSILON
    && Math.abs(a.bottom - b.bottom) <= RECT_EPSILON
}

function containsRect(outer: SelectionRectLike, inner: SelectionRectLike): boolean {
  return outer.left <= inner.left + RECT_EPSILON
    && outer.right >= inner.right - RECT_EPSILON
    && outer.top <= inner.top + RECT_EPSILON
    && outer.bottom >= inner.bottom - RECT_EPSILON
}

function mergeRectPair(a: SelectionRectLike, b: SelectionRectLike): SelectionRectLike {
  return {
    left: Math.min(a.left, b.left),
    right: Math.max(a.right, b.right),
    top: Math.min(a.top, b.top),
    bottom: Math.max(a.bottom, b.bottom),
  }
}

export function normalizeSelectionRects(
  rects: readonly SelectionRectLike[],
  bounds: SelectionRectLike,
): SelectionRectLike[] {
  const clipped = rects
    .map(rect => clipRectToBounds(rect, bounds))
    .filter((rect): rect is SelectionRectLike => rect !== null)
    .sort((a, b) => a.top - b.top || a.left - b.left)

  const deduped: SelectionRectLike[] = []
  for (const rect of clipped) {
    if (!deduped.some(existing => sameRect(existing, rect))) {
      deduped.push(rect)
    }
  }

  const mergedRows: SelectionRectLike[] = []
  for (const rect of deduped) {
    const previous = mergedRows[mergedRows.length - 1]
    if (!previous) {
      mergedRows.push(rect)
      continue
    }

    const verticalOverlap = Math.min(previous.bottom, rect.bottom) - Math.max(previous.top, rect.top)
    const horizontalGap = rect.left - previous.right
    // Only merge rects that are on the SAME visual line — they must have
    // real vertical overlap (more than epsilon). Rects from adjacent lines
    // that merely touch (verticalOverlap ≈ 0) must NOT be merged, otherwise
    // a multi-line selection collapses into a single tall rect.
    if (verticalOverlap > RECT_EPSILON && horizontalGap <= HORIZONTAL_MERGE_GAP) {
      mergedRows[mergedRows.length - 1] = mergeRectPair(previous, rect)
      continue
    }

    mergedRows.push(rect)
  }

  const withoutContained = mergedRows.filter((rect, index) =>
    !mergedRows.some((other, otherIndex) => otherIndex !== index && containsRect(other, rect)),
  )

  const joined: SelectionRectLike[] = [...withoutContained]
  for (let index = 1; index < withoutContained.length; index += 1) {
    const previous = withoutContained[index - 1]
    const current = withoutContained[index]
    const overlapLeft = Math.max(previous.left, current.left)
    const overlapRight = Math.min(previous.right, current.right)
    const gap = current.top - previous.bottom

    if (overlapRight - overlapLeft > RECT_EPSILON && gap > RECT_EPSILON && gap <= VERTICAL_JOIN_GAP) {
      joined.push({
        left: overlapLeft,
        right: overlapRight,
        top: previous.bottom,
        bottom: current.top,
      })
    }
  }

  return joined.sort((a, b) => a.top - b.top || a.left - b.left)
}

/**
 * Cached line geometry for a single `.cm-line` element: its viewport
 * bounding rect and the CSS `line-height` (one visual row height).
 * When `line-height: normal` or unavailable, `cssLineHeight` is null
 * and callers must estimate the per-row height.
 */
interface LineInfo {
  rect: DOMRect
  cssLineHeight: number | null
}

/**
 * Query all `.cm-line` elements and compute their geometry once.
 * Shared between {@link expandRectsToLineHeight} and
 * {@link getSelectionLineBounds} to avoid duplicate
 * `querySelectorAll` + `getBoundingClientRect` + `getComputedStyle`
 * calls on every selection update.
 */
function collectLineInfo(view: EditorView): LineInfo[] {
  const win = view.dom.ownerDocument.defaultView
  return Array.from(view.dom.querySelectorAll<HTMLElement>('.cm-line')).map(el => {
    const rect = el.getBoundingClientRect()
    const computed = win?.getComputedStyle(el).lineHeight
    const parsed = computed ? parseFloat(computed) : NaN
    const cssLineHeight = Number.isFinite(parsed) && parsed > 0 ? parsed : null
    return { rect, cssLineHeight }
  })
}

/**
 * Expand each native selection rect vertically to cover the full height of
 * one visual row (CSS line-height). The browser's `getClientRects()`
 * returns the text content's bounding box, which is shorter than the
 * line-height due to CSS `line-height` spacing. Without this expansion,
 * the selection background appears shorter than the rendered line.
 *
 * For wrapped paragraphs (where a single `.cm-line` element spans
 * multiple visual rows), each rect is expanded to one CSS line-height
 * centered on the rect's vertical midpoint, NOT to the full `.cm-line`
 * element height. Expanding to the full element height would paint the
 * entire paragraph when only one visual row is selected.
 *
 * For non-wrapped lines (`.cm-line` height ≈ CSS line-height), the rect
 * is expanded to the full `.cm-line` bounds — this is the fix for the
 * bold-text height mismatch bug where the native rect was shorter than
 * the line height.
 *
 * When `cssLineHeight` is null (`line-height: normal` or unavailable),
 * the per-row height is estimated by dividing the `.cm-line` element
 * height by the number of native rects that fall within its vertical
 * range. This prevents wrapped paragraphs from being expanded to full
 * height when the CSS line-height can't be read.
 *
 * When `clipBounds` is provided, expanded rects are clipped to the
 * selection's logical line bounds and rects entirely outside those bounds
 * are filtered out. This prevents the browser's `getClientRects()` from
 * including rects for lines beyond the selection range (a known browser
 * behavior when the selection ends at a `\n`).
 */
function expandRectsToLineHeight(
  lineInfo: LineInfo[],
  rects: readonly SelectionRectLike[],
  clipBounds: { top: number; bottom: number } | null,
  expandFirstRectLeft: boolean,
  expandLastRectRight: boolean,
): SelectionRectLike[] {
  if (lineInfo.length === 0) return [...rects]

  // Pre-filter rects by clipBounds to remove out-of-range rects before
  // computing firstTop/lastTop. The browser's getClientRects() can
  // include rects for lines beyond the selection range (e.g., when the
  // selection ends at a \n boundary). Without pre-filtering, those
  // extra rects make lastTop point below the actual last selected line,
  // causing all rects on the real last line to have their right edge
  // expanded — the "right edge is too trigger happy" bug.
  //
  // Use strict comparison (no epsilon) for the bottom boundary: the
  // extra rect starts at exactly clipBounds.bottom (the next .cm-line
  // element's top), and adding epsilon would let it survive.
  const inBoundsRects = clipBounds
    ? rects.filter(rect =>
        rect.bottom > clipBounds.top - RECT_EPSILON
        && rect.top < clipBounds.bottom,
      )
    : rects

  // Sort by top so we can identify the first (topmost) and last
  // (bottommost) rects. The first rect's left edge is the selection
  // start position; the last rect's right edge is the selection end
  // position. When the selection starts/ends mid-line, these edges
  // must NOT be expanded. When the selection starts/ends at a line
  // boundary, they should also align with the .cm-line edge.
  // All other rects represent lines selected from beginning to end,
  // so both their left and right edges should align with the .cm-line
  // bounds.
  const sortedRects = [...inBoundsRects].sort((a, b) => a.top - b.top || a.left - b.left)
  const firstTop = sortedRects[0]?.top ?? -Infinity
  const lastTop = sortedRects[sortedRects.length - 1]?.top ?? Infinity

  // When CSS line-height is unavailable, estimate per-row height by
  // counting native rects per .cm-line and dividing the element height.
  const estimatedLineHeights = new Map<DOMRect, number>()
  for (const { rect: lineRect, cssLineHeight } of lineInfo) {
    if (cssLineHeight !== null) continue
    let count = 0
    for (const nativeRect of sortedRects) {
      if (nativeRect.top >= lineRect.top - RECT_EPSILON && nativeRect.top < lineRect.bottom) {
        count += 1
      }
    }
    if (count > 1) {
      estimatedLineHeights.set(lineRect, lineRect.height / count)
    }
  }

  function expandRect(
    rect: SelectionRectLike,
    lineRect: DOMRect,
    cssLineHeight: number | null,
    expandLeft: boolean,
    expandRight: boolean,
  ): SelectionRectLike {
    // Resolve the effective per-row height: CSS line-height when available,
    // estimated from native rect count when not.
    const rowHeight = cssLineHeight ?? estimatedLineHeights.get(lineRect) ?? null

    // Expand the left edge to the .cm-line left edge for fully-selected
    // lines (all rects except the first). The native rect's left edge
    // may start after the bullet marker because the DOM selection range
    // doesn't always include the formatting span that renders the marker.
    const left = expandLeft ? Math.min(rect.left, lineRect.left) : rect.left
    // Expand the right edge to the .cm-line right edge for fully-selected
    // lines (all rects except the last). The native rect's right edge
    // stops at the last selected character, not at the content area's
    // right edge, producing a selection that "only goes to the last word."
    //
    // When NOT expanding (the last rect), CLIP the right edge to just
    // before the .cm-line right edge. The browser's getClientRects() can
    // return a rect whose right edge extends to the line's right edge
    // when the selection includes a \n (e.g., when dragging past the
    // right edge of the editor, or for backward/upward selections where
    // the anchor line's native rect includes the \n from the line above).
    // Without clipping, the last rect appears full-width — the
    // "current line also gets fully selected" bug. The clip ensures the
    // last rect is always partial on the right, regardless of what the
    // browser's native rect says.
    const right = expandRight
      ? Math.max(rect.right, lineRect.right)
      : Math.min(rect.right, lineRect.right - RECT_EPSILON)

    // Wrapped paragraph: .cm-line height > one row height.
    // Expand to one visual row centered on the rect's midpoint,
    // clipped to the .cm-line bounds.
    if (rowHeight !== null && lineRect.height > rowHeight + RECT_EPSILON) {
      const midY = (rect.top + rect.bottom) / 2
      return {
        left,
        right,
        top: Math.max(midY - rowHeight / 2, lineRect.top),
        bottom: Math.min(midY + rowHeight / 2, lineRect.bottom),
      }
    }
    // Non-wrapped (or row height unavailable): expand to full
    // .cm-line bounds. This fixes the bold-text height mismatch where
    // the native rect is shorter than the line-height due to CSS spacing.
    return {
      left,
      right,
      top: lineRect.top,
      bottom: lineRect.bottom,
    }
  }

  return sortedRects
    .map(rect => {
      const expandLeft = expandFirstRectLeft || rect.top > firstTop + RECT_EPSILON
      const expandRight = expandLastRectRight || rect.top < lastTop - RECT_EPSILON
      for (const { rect: lineRect, cssLineHeight } of lineInfo) {
        if (rect.top >= lineRect.top - RECT_EPSILON && rect.top < lineRect.bottom) {
          return expandRect(rect, lineRect, cssLineHeight, expandLeft, expandRight)
        }
      }
      const midY = (rect.top + rect.bottom) / 2
      for (const { rect: lineRect, cssLineHeight } of lineInfo) {
        if (midY >= lineRect.top && midY <= lineRect.bottom) {
          return expandRect(rect, lineRect, cssLineHeight, expandLeft, expandRight)
        }
      }
      return { ...rect }
    })
    .filter(rect => {
      if (!clipBounds) return true
      return rect.bottom > clipBounds.top - RECT_EPSILON
        && rect.top < clipBounds.bottom + RECT_EPSILON
    })
    .map(rect => {
      if (!clipBounds) return rect
      return {
        left: rect.left,
        right: rect.right,
        top: Math.max(rect.top, clipBounds.top),
        bottom: Math.min(rect.bottom, clipBounds.bottom),
      }
    })
}

/**
 * Compute the vertical bounds of the first and last source lines covered
 * by the selection, in viewport coordinates. Used to clip expanded native
 * selection rects so they don't extend beyond the selection's logical
 * line range (the browser's getClientRects() can return rects for lines
 * beyond the selection when it ends at a \n).
 *
 * Uses `coordsAtPos` to get the approximate y-coordinate of each endpoint,
 * then finds the `.cm-line` element whose vertical range contains that
 * y-coordinate. This gives the full line height (including CSS line-height
 * spacing), which `coordsAtPos` alone does not provide.
 *
 * When the selection ends at a `\n` boundary, `coordsAtPos(range.to)` may
 * return coordinates at the beginning of the *next* line. To avoid this,
 * we use `range.to - 1` when the character before `to` is a `\n`, ensuring
 * we get coordinates on the correct (last) line of the selection.
 */
function getSelectionLineBounds(
  view: EditorView,
  range: { from: number; to: number },
  lineInfo: LineInfo[],
): { top: number; bottom: number } | null {
  const startCoords = view.coordsAtPos(range.from)
  if (!startCoords) return null

  // When the selection ends at a \n, coordsAtPos(range.to) returns
  // coordinates at the start of the next line. Step back one position
  // to get coordinates on the last content line of the selection.
  let endPos = range.to
  if (range.to > range.from) {
    const charBefore = view.state.doc.sliceString(range.to - 1, range.to)
    if (charBefore === '\n') {
      endPos = range.to - 1
    }
  }
  const endCoords = view.coordsAtPos(endPos)
  if (!endCoords) return null

  const startMidY = (startCoords.top + startCoords.bottom) / 2
  const endMidY = (endCoords.top + endCoords.bottom) / 2

  let startLineRect: DOMRect | null = null
  let endLineRect: DOMRect | null = null

  for (const { rect: lineRect } of lineInfo) {
    if (startLineRect === null && startMidY >= lineRect.top && startMidY <= lineRect.bottom) {
      startLineRect = lineRect
    }
    if (endLineRect === null && endMidY >= lineRect.top && endMidY <= lineRect.bottom) {
      endLineRect = lineRect
    }
    if (startLineRect && endLineRect) break
  }

  if (!startLineRect || !endLineRect) return null

  return {
    top: Math.min(startLineRect.top, endLineRect.top),
    bottom: Math.max(startLineRect.bottom, endLineRect.bottom),
  }
}

/**
 * Post-normalization clip: ensure the last (bottommost) rect's right
 * edge does NOT reach the .cm-line right edge.
 *
 * The clip in {@link expandRectsToLineHeight} clips the last rect's
 * right edge to just before the line's right edge. However,
 * {@link normalizeSelectionRects} can merge the clipped last rect
 * with an adjacent \n rect whose right edge was EXPANDED (the \n rect
 * is sorted before the anchor rect by left position, making the anchor
 * rect the "last" rect and the \n rect an "interior" rect with
 * expandRight=true). The merge takes `Math.max(a.right, b.right)`,
 * which overrides the clip.
 *
 * This function re-applies the clip AFTER normalization, ensuring it
 * persists regardless of what merge operations occurred. Also clips
 * any bridge rect immediately above the last rect that may have
 * inherited the unclipped right edge from the merge.
 *
 * Returns a new array — does not mutate the input.
 */
function clipLastRectRightEdge(
  rects: SelectionRectLike[],
  lineInfo: LineInfo[],
  clipRightOverride: number | null,
): SelectionRectLike[] {
  if (rects.length === 0 || lineInfo.length === 0) return rects

  // Find the bottommost rect (last in sorted order).
  const sorted = [...rects].sort((a, b) => a.top - b.top || a.left - b.left)
  const lastRect = sorted[sorted.length - 1]

  // Find the .cm-line element whose vertical range contains this rect.
  let targetLineRect: DOMRect | null = null
  for (const { rect: lineRect } of lineInfo) {
    if (lastRect.top >= lineRect.top - RECT_EPSILON && lastRect.top < lineRect.bottom) {
      targetLineRect = lineRect
      break
    }
  }
  // Fallback: match by midpoint.
  if (!targetLineRect) {
    const midY = (lastRect.top + lastRect.bottom) / 2
    for (const { rect: lineRect } of lineInfo) {
      if (midY >= lineRect.top && midY <= lineRect.bottom) {
        targetLineRect = lineRect
        break
      }
    }
  }

  if (!targetLineRect) return rects

  const clipRight = clipRightOverride === null
    ? targetLineRect.right - RECT_EPSILON
    : Math.min(clipRightOverride, targetLineRect.right - RECT_EPSILON)
  if (lastRect.right < clipRight) return rects // already clipped, no change

  // Return a new array with the last row's rects (and any adjacent bridge
  // it) clipped. Bridge rects created by normalizeSelectionRects can
  // inherit the unclipped right edge from the merge — clip them too.
  const lastTop = lastRect.top
  return rects.map(rect => {
    if (Math.abs(rect.top - lastTop) <= RECT_EPSILON && rect.right > clipRight) {
      return { ...rect, right: Math.min(rect.right, clipRight) }
    }
    // Clip bridge rects that sit immediately above the last rect
    // (their bottom == lastTop) and extend past clipRight.
    const rectHeight = rect.bottom - rect.top
    if (
      rect.bottom <= lastTop + RECT_EPSILON
      && rect.bottom >= lastTop - VERTICAL_JOIN_GAP - RECT_EPSILON
      && rectHeight <= VERTICAL_JOIN_GAP + RECT_EPSILON
      && rect.right > clipRight
    ) {
      return { ...rect, right: Math.min(rect.right, clipRight) }
    }
    return rect
  })
}

export function clipFirstRowLeftEdge(
  rects: SelectionRectLike[],
  clipLeftBounds: SelectionRectLike | null,
): SelectionRectLike[] {
  if (rects.length === 0 || clipLeftBounds === null) return rects

  return rects
    .map(rect => {
      const overlap = Math.min(rect.bottom, clipLeftBounds.bottom)
        - Math.max(rect.top, clipLeftBounds.top)
      const overlapsFromRow = overlap > RECT_EPSILON
      if (!overlapsFromRow || rect.left >= clipLeftBounds.left) return rect
      return { ...rect, left: clipLeftBounds.left }
    })
    .filter(rect => rect.right - rect.left > RECT_EPSILON)
}

function selectionMarkers(view: EditorView): readonly RectangleMarker[] {
  if (view.state.selection.ranges.every(range => range.empty)) return []
  const selection = view.dom.ownerDocument.defaultView?.getSelection() ?? null
  const base = getLayerBase(view)
  const domSelectionState = getDomSelectionState(view, selection)
  const contentRect = view.contentDOM.getBoundingClientRect()

  if (domSelectionState === 'external-range') {
    return []
  }

  const mainRange = view.state.selection.main
  // Collect .cm-line geometry once and share between expandRectsToLineHeight
  // and getSelectionLineBounds to avoid duplicate DOM queries.
  const lineInfo = collectLineInfo(view)
  const clipBounds = mainRange.empty ? null : getSelectionLineBounds(view, mainRange, lineInfo)

  // Determine whether the selection starts at a line boundary (position 0
  // or after a \n). When it does, the first rect's left edge should also
  // be expanded to the .cm-line left edge — the selection covers the full
  // line from its beginning, so the rect should include the bullet marker.
  const startsAtLineBoundary = !mainRange.empty && (
    mainRange.from === 0
    || view.state.doc.sliceString(mainRange.from - 1, mainRange.from) === '\n'
  )
  const fromCoords = !mainRange.empty && !startsAtLineBoundary
    ? view.coordsAtPos(mainRange.from, 1)
    : null

  const bottomEndpointAtLineBoundary = mainRange.to === 0
    || view.state.doc.sliceString(mainRange.to - 1, mainRange.to) === '\n'
  const endsAfterSelectedNewline = !mainRange.empty
    && mainRange.to > mainRange.from
    && view.state.doc.sliceString(mainRange.to - 1, mainRange.to) === '\n'
  const bottomEndpointCoords = !mainRange.empty && !bottomEndpointAtLineBoundary
    ? view.coordsAtPos(mainRange.to, -1)
    : null

  // The last rect's right edge expands only when the logical selection
  // actually includes a trailing newline. Selecting `x` should stay
  // text-width; selecting `x\n` should paint the whole source line.
  // The first rect's right edge is expanded for all multi-line selections
  // — the selection goes from the drag start to the end of the line.
  // Interior lines always get their right edge expanded.
  const mainRangeRects = domSelectionState !== 'editor-range' || !selection
    ? null
    : clipFirstRowLeftEdge(
        normalizeSelectionRects(
          expandRectsToLineHeight(
            lineInfo,
            Array.from(selection.getRangeAt(0).getClientRects()),
            clipBounds,
            startsAtLineBoundary,
            endsAfterSelectedNewline,
          ),
          contentRect,
        ),
        fromCoords,
      )
  const mainRangeMarkers = mainRangeRects === null
    ? null
    : (endsAfterSelectedNewline
        ? mainRangeRects
        : clipLastRectRightEdge(
            mainRangeRects,
            lineInfo,
            bottomEndpointCoords?.left ?? null,
          )).map(
        rect =>
          new RectangleMarker(
            DOM_SELECTION_BACKGROUND_CLASS,
            rect.left - base.left,
            rect.top - base.top,
            rect.right - rect.left,
            rect.bottom - rect.top,
          ),
      )
  const mainMarkers = mainRangeMarkers && mainRangeMarkers.length > 0 ? mainRangeMarkers : null

  const markers: RectangleMarker[] = []
  for (const range of view.state.selection.ranges) {
    if (range.empty) continue

    if (range === view.state.selection.main && mainMarkers !== null) {
      markers.push(...mainMarkers)
      continue
    }

    if (!view.hasFocus) {
      continue
    }

    markers.push(...RectangleMarker.forRange(view, DOM_SELECTION_BACKGROUND_CLASS, range))
  }

  return markers
}

export const domSelectionLayer = layer({
  above: false,
  class: 'cm-dom-selectionLayer',
  markers: selectionMarkers,
  update(update: ViewUpdate) {
    return (
      update.selectionSet
      || update.docChanged
      || update.viewportChanged
      || update.focusChanged
      || update.geometryChanged
    )
  },
  mount(_layer, view) {
    const onSelectionChange = () => {
      view.requestMeasure()
    }

    view.dom.ownerDocument.addEventListener('selectionchange', onSelectionChange)
    cleanupByView.set(view, () => {
      view.dom.ownerDocument.removeEventListener('selectionchange', onSelectionChange)
    })
  },
  destroy(_layer, view) {
    cleanupByView.get(view)?.()
    cleanupByView.delete(view)
  },
})