import { invariant } from './invariant.ts'
import type { FrameContext } from './frame.ts'

type HydratedVirtualRootStartMarker = Comment & {
  $rmx: {
    dispose(): void
  }
}

type CommentMarkerRangeReplacement = {
  currentStart: Comment
  nextStart: Comment
  currentEndIndex: number
  nextEndIndex: number
}

export function diffNodes(curr: Node[], next: Node[], context: FrameContext) {
  let parent = curr[0]?.parentNode ?? context.regionParent ?? null
  invariant(parent, 'Parent node not found')

  // When diffing a bounded region (e.g. between frame comments), we should insert new
  // nodes before the region tail ref rather than appending to the parent.
  let regionTailRef: ChildNode | null =
    context.regionTailRef ??
    (curr.length > 0 ? (curr[curr.length - 1].nextSibling as ChildNode | null) : null)

  let currentIndex = 0
  let nextIndex = 0
  while (currentIndex < curr.length || nextIndex < next.length) {
    let c = curr[currentIndex]
    let n = next[nextIndex]

    if (!c && n) {
      if (regionTailRef) {
        parent.insertBefore(n, regionTailRef)
      } else {
        parent.appendChild(n)
      }
      nextIndex++
    } else if (c && !n) {
      removeNode(c, parent, context)
      currentIndex++
    } else if (c && n) {
      let replacement = getCommentMarkerRangeReplacement(
        c,
        n,
        curr,
        next,
        currentIndex,
        nextIndex,
        context,
      )
      if (replacement) {
        replaceCommentMarkerRange(replacement, parent, context)
        currentIndex = replacement.currentEndIndex + 1
        nextIndex = replacement.nextEndIndex + 1
        continue
      }

      // Skip hydrated client-entry marker ranges; hydration pass re-renders
      // roots with new props from incoming payload
      if (isVirtualRootStartMarker(c) && isVirtualRootStartMarker(n)) {
        let currentEnd = findHydrationEndMarker(c)
        let nextEnd = findHydrationEndMarker(n)
        let nextData = n.data
        if (c.data !== nextData) c.data = nextData

        let currentEndIndex = curr.indexOf(currentEnd)
        let nextEndIndex = next.indexOf(nextEnd)
        currentIndex = currentEndIndex + 1
        nextIndex = nextEndIndex + 1
        continue
      }

      let cursor = diffNode(c, n, context)
      if (cursor) {
        let nextEndIndex = next.indexOf(cursor)
        let currentEndIndex =
          isFrameStartMarker(c) && isFrameEndMarker(cursor)
            ? findFrameEndIndex(curr, currentIndex)
            : currentIndex
        currentIndex = currentEndIndex + 1
        nextIndex = nextEndIndex + 1
        continue
      }

      currentIndex++
      nextIndex++
    }
  }
}

function diffNode(current: Node, next: Node, context: FrameContext): ChildNode | undefined {
  // Text -> Text
  if (isTextNode(current) && isTextNode(next)) {
    let newText = next.textContent || ''
    if (current.textContent !== newText) current.textContent = newText
    return
  }

  // Hydration marker range -> Hydration marker range
  if (isVirtualRootStartMarker(current) && isVirtualRootStartMarker(next)) {
    let nextData = next.data
    if (current.data !== nextData) {
      current.data = nextData
    }

    let end = findHydrationEndMarker(next)
    // Fast-forward across this hydrated region.
    return end
  }

  // Comment -> Comment
  if (isCommentNode(current) && isCommentNode(next)) {
    let newData = next.data
    if (current.data !== newData) {
      let updated = false
      if (isFrameStartMarker(current)) {
        if (shouldPreserveFrameStartMarker(current, next, context)) {
          current.data = newData
          updated = true

          let frame = context.frameInstances.get(current)
          let nextMarkerData = getFrameMarkerData(next, context)
          if (frame && nextMarkerData) {
            if (nextMarkerData.status === 'resolved') {
              let nextEnd = findFrameEndMarker(next)
              let nextContent = collectFrameContentFragment(current.ownerDocument, next, nextEnd)
              void frame.renderMarkerContent(
                { ...nextMarkerData, id: getFrameId(next) },
                nextContent,
                {
                  signal: context.signal,
                },
              )
              return nextEnd
            }

            if (frame.isDisplayingResolvedContent()) {
              return findFrameEndMarker(next)
            }
          }
        } else {
          disposeFrameStartMarker(current, context)
          current.data = newData
          updated = true
        }
      }
      if (!updated) {
        current.data = newData
      }
    }
    return
  }

  // Element -> Element
  if (isElement(current) && isElement(next)) {
    // Different tags: replace
    if (current.tagName !== next.tagName) {
      let parent = current.parentNode
      if (parent) {
        parent.insertBefore(next, current)
        removeNode(current, parent, context)
      }
      return
    }

    // Same tag: update attributes then children
    diffElementAttributes(current, next)
    if (shouldPreserveElementChildren(current, next)) return
    diffElementChildren(current, next, context)
    return
  }

  // Type mismatch: replace
  let parent = current.parentNode
  if (parent) {
    parent.insertBefore(next, current)
    removeNode(current, parent, context)
  }
}

function diffElementAttributes(current: Element, next: Element): void {
  let prevAttrNames = current.getAttributeNames()
  let nextAttrNames = next.getAttributeNames()

  let nextNameSet = new Set(nextAttrNames)

  // Removals
  for (let name of prevAttrNames) {
    if (!nextNameSet.has(name)) {
      if (shouldPreserveLiveAttribute(current, next, name)) continue
      current.removeAttribute(name)
    }
  }

  // Additions/updates
  for (let name of nextAttrNames) {
    let prevVal = current.getAttribute(name)
    let nextVal = next.getAttribute(name)
    if (prevVal !== nextVal) {
      if (shouldPreserveLiveAttribute(current, next, name)) continue
      current.setAttribute(name, nextVal == null ? '' : String(nextVal))
    }
  }
}

function shouldPreserveLiveAttribute(current: Element, next: Element, name: string): boolean {
  if (name === 'open') {
    if (current instanceof HTMLDetailsElement && next instanceof HTMLDetailsElement) {
      return current.open !== next.open
    }

    if (current instanceof HTMLDialogElement && next instanceof HTMLDialogElement) {
      return current.open !== next.open
    }
  }

  if (name === 'checked') {
    if (current instanceof HTMLInputElement && next instanceof HTMLInputElement) {
      return current.checked !== next.checked
    }
  }

  if (name === 'value') {
    if (
      current instanceof HTMLInputElement &&
      next instanceof HTMLInputElement &&
      shouldPreserveInputValue(current)
    ) {
      return current.value !== next.value
    }
  }

  if (name === 'selected') {
    if (current instanceof HTMLOptionElement && next instanceof HTMLOptionElement) {
      return current.selected !== next.selected
    }
  }

  if (name === 'popover') {
    return isPopoverOpen(current) !== isPopoverOpen(next)
  }

  return false
}

function shouldPreserveElementChildren(current: Element, next: Element): boolean {
  if (current instanceof HTMLTextAreaElement && next instanceof HTMLTextAreaElement) {
    return current.value !== next.value
  }

  return false
}

function shouldPreserveInputValue(input: HTMLInputElement): boolean {
  return (
    input.type !== 'button' &&
    input.type !== 'checkbox' &&
    input.type !== 'hidden' &&
    input.type !== 'image' &&
    input.type !== 'radio' &&
    input.type !== 'reset' &&
    input.type !== 'submit'
  )
}

function isPopoverOpen(element: Element): boolean {
  try {
    return element.matches(':popover-open')
  } catch {
    return false
  }
}

function diffElementChildren(current: Element, next: Element, context: FrameContext): void {
  let currentChildren = Array.from(current.childNodes)
  let nextChildren = Array.from(next.childNodes)

  // Keyed map by data-key for current children
  let keyToIndex = new Map<string, number>()
  for (let i = 0; i < currentChildren.length; i++) {
    let node = currentChildren[i]
    if (isElement(node)) {
      let key = node.getAttribute('data-key')
      if (key != null) keyToIndex.set(key, i)
    }
  }

  let used = new Array<boolean>(currentChildren.length).fill(false)
  let matchIndexForNext = new Array<number>(nextChildren.length).fill(-1)

  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i]
    let matchIndex = -1

    if (isFrameEndMarker(nextChild)) {
      for (let j = 0; j < currentChildren.length; j++) {
        if (!used[j] && isFrameEndMarker(currentChildren[j])) {
          matchIndex = j
          break
        }
      }
    } else if (isElement(nextChild)) {
      let key = nextChild.getAttribute('data-key')
      if (key != null && keyToIndex.has(key)) {
        let idx = keyToIndex.get(key)!
        if (!used[idx]) matchIndex = idx
      }
    }

    if (matchIndex === -1) {
      let candidateIndex = i
      if (
        candidateIndex < currentChildren.length &&
        !used[candidateIndex] &&
        nodeTypesComparable(currentChildren[candidateIndex], nextChild)
      ) {
        matchIndex = candidateIndex
      }
    }

    if (matchIndex !== -1) used[matchIndex] = true
    matchIndexForNext[i] = matchIndex
  }

  // Forward pass: update matched, collect committed
  let committed: Array<Node | undefined> = new Array(nextChildren.length)
  for (let i = 0; i < nextChildren.length; i++) {
    let mi = matchIndexForNext[i]
    if (mi !== -1) {
      let curChild = currentChildren[mi]
      let nextChild = nextChildren[i]

      let replacement = getCommentMarkerRangeReplacement(
        curChild,
        nextChild,
        currentChildren,
        nextChildren,
        mi,
        i,
        context,
      )
      if (replacement) {
        replaceCommentMarkerRange(replacement, current, context)

        for (let k = mi; k <= replacement.currentEndIndex; k++) used[k] = true

        committed[i] = replacement.nextStart
        committed[replacement.nextEndIndex] = nextChildren[replacement.nextEndIndex]
        for (let j = i + 1; j < replacement.nextEndIndex; j++) committed[j] = undefined

        i = replacement.nextEndIndex
        continue
      }

      let cursor = diffNode(curChild, nextChild, context)
      if (cursor) {
        // `diffNode` can preserve hydration and frame marker ranges by returning
        // the next end marker, so skip the owned interior nodes here.
        let nextEndIdx = nextChildren.indexOf(cursor)
        let currEndIdx =
          isFrameStartMarker(curChild) && isFrameEndMarker(cursor)
            ? findFrameEndIndex(currentChildren, mi)
            : findHydrationEndIndex(currentChildren, mi)

        // Adjacent marker ranges can pre-match into the next range and leave an
        // orphaned end marker behind. Clear those stale matches first.
        for (let j = i + 1; j <= nextEndIdx; j++) {
          let matchedIndex = matchIndexForNext[j]
          if (matchedIndex > currEndIdx) {
            used[matchedIndex] = false
          }
          matchIndexForNext[j] = -1
        }

        // Mark the entire current region as used to avoid removals.
        for (let k = mi; k <= currEndIdx; k++) used[k] = true

        // Preserve both comment markers in committed; skip interior in reorder pass.
        committed[i] = curChild // start marker
        committed[nextEndIdx] = currentChildren[currEndIdx] // end marker
        for (let j = i + 1; j < nextEndIdx; j++) committed[j] = undefined

        // Jump to end of region.
        i = nextEndIdx
        continue
      }
      committed[i] = curChild
    } else {
      committed[i] = nextChildren[i]
    }
  }

  // Backward pass: reorder via inserts while avoiding redundant moves
  let anchor: Node | undefined = undefined
  for (let i = committed.length - 1; i >= 0; i--) {
    let node = committed[i]
    if (!node) continue

    // Use only an anchor that is actually a child of the current parent
    let ref = anchor && anchor.parentNode === current ? anchor : null

    // Existing comment markers delimit live ranges, so do not reorder them
    // independently from their contents. New markers still need to be inserted
    // before they can be used as anchors.
    if (
      isVirtualRootStartMarker(node) ||
      isVirtualRootEndMarker(node) ||
      isFrameStartMarker(node) ||
      isFrameEndMarker(node)
    ) {
      if (node.parentNode !== current) {
        current.insertBefore(node, ref)
      }
      anchor = node
      continue
    }

    if (node.parentNode === current) {
      // Node already in parent: move only if its nextSibling is not the desired ref.
      let targetNext = ref
      let alreadyInPlace =
        (targetNext === null && node.nextSibling === null) || node.nextSibling === targetNext
      if (!alreadyInPlace) {
        current.insertBefore(node, targetNext)
      }
    } else {
      // New node: insert relative to a valid ref or append
      current.insertBefore(node, ref)
    }

    // Advance anchor only after the node is placed in the correct parent
    if (node.parentNode === current) {
      anchor = node
    }
  }

  // Remove any current children not used
  for (let i = 0; i < currentChildren.length; i++) {
    if (!used[i]) {
      let nodeToRemove = currentChildren[i]
      removeNode(nodeToRemove, current, context)
    }
  }
}

function nodeTypesComparable(a: Node, b: Node): boolean {
  if (isTextNode(a) && isTextNode(b)) return true
  if (isElement(a) && isElement(b)) return a.tagName === b.tagName
  if (isVirtualRootStartMarker(a) && isVirtualRootStartMarker(b)) return true
  if (isVirtualRootEndMarker(a) && isVirtualRootEndMarker(b)) return true
  if (isCommentNode(a) && isCommentNode(b)) return true
  return false
}

function isHydrationEndComment(node: Node): node is Comment {
  return isCommentNode(node) && node.data.trim() === '/rmx:h'
}

function findHydrationEndMarker(start: Comment): Comment {
  let node: Node | null = start.nextSibling
  let depth = 1

  while (node) {
    if (isCommentNode(node)) {
      if (isVirtualRootStartMarker(node)) depth++
      if (isVirtualRootEndMarker(node)) {
        depth--
        if (depth === 0) return node
      }
    }
    node = node.nextSibling
  }

  throw new Error('Hydration end marker not found')
}

function findHydrationEndIndex(nodes: Node[], startIdx: number): number {
  for (let j = startIdx + 1; j < nodes.length; j++) {
    if (isHydrationEndComment(nodes[j])) return j
  }
  return startIdx
}

function findFrameEndMarker(start: Comment): Comment {
  let node: Node | null = start.nextSibling
  let depth = 1

  while (node) {
    if (isFrameStartMarker(node)) depth++
    if (isFrameEndMarker(node)) {
      depth--
      if (depth === 0) return node
    }
    node = node.nextSibling
  }

  throw new Error('Frame end marker not found')
}

function findFrameEndIndex(nodes: Node[], startIdx: number): number {
  let depth = 1

  for (let j = startIdx + 1; j < nodes.length; j++) {
    let node = nodes[j]
    if (isFrameStartMarker(node)) depth++
    if (isFrameEndMarker(node)) {
      depth--
      if (depth === 0) return j
    }
  }

  return startIdx
}

function isTextNode(node: Node): node is Text {
  return node.nodeType === Node.TEXT_NODE
}

function isElement(node: Node): node is Element {
  return node.nodeType === Node.ELEMENT_NODE
}

function isCommentNode(node: Node): node is Comment {
  return node.nodeType === Node.COMMENT_NODE
}

function isFrameStartMarker(node: Node): node is Comment {
  return node instanceof Comment && node.data.trim().startsWith('rmx:f:')
}

function isFrameEndMarker(node: Node): node is Comment {
  return node instanceof Comment && node.data.trim() === '/rmx:f'
}

function shouldPreserveFrameStartMarker(
  current: Comment,
  next: Comment,
  context: FrameContext,
): boolean {
  if (!isFrameStartMarker(next)) return false

  let currentData = getFrameMarkerData(current, context)
  let nextData = getFrameMarkerData(next, context)

  return (
    currentData !== undefined &&
    nextData !== undefined &&
    currentData.src === nextData.src &&
    currentData.name === nextData.name
  )
}

function getCommentMarkerRangeReplacement(
  current: Node,
  next: Node,
  currentNodes: Node[],
  nextNodes: Node[],
  currentIndex: number,
  nextIndex: number,
  context: FrameContext,
): CommentMarkerRangeReplacement | undefined {
  // Comment markers can represent owned DOM ranges, not standalone comments. If
  // the incoming range no longer has the same identity, replace the whole range
  // before regular node diffing mutates either marker.
  if (
    isFrameStartMarker(current) &&
    isFrameStartMarker(next) &&
    !shouldPreserveFrameStartMarker(current, next, context)
  ) {
    return {
      currentStart: current,
      nextStart: next,
      currentEndIndex: findFrameEndIndex(currentNodes, currentIndex),
      nextEndIndex: findFrameEndIndex(nextNodes, nextIndex),
    }
  }
}

function getFrameMarkerData(marker: Comment, context: FrameContext) {
  let id = getFrameId(marker)
  return context.data.f?.[id]
}

function getFrameId(marker: Comment): string {
  let trimmed = marker.data.trim()
  invariant(trimmed.startsWith('rmx:f:'), 'Invalid frame start marker')
  return trimmed.slice('rmx:f:'.length)
}

function replaceCommentMarkerRange(
  replacement: CommentMarkerRangeReplacement,
  parent: ParentNode,
  context: FrameContext,
): void {
  let currentEnd = findFrameEndMarker(replacement.currentStart)
  let nextEnd = findFrameEndMarker(replacement.nextStart)
  let nextNodes = collectNodeRange(replacement.nextStart, nextEnd)
  let currentNodes = collectNodeRange(replacement.currentStart, currentEnd)

  for (let node of nextNodes) {
    parent.insertBefore(node, replacement.currentStart)
  }

  for (let node of currentNodes) {
    removeNode(node, parent, context)
  }
}

function collectNodeRange(start: Node, end: Node): Node[] {
  let nodes: Node[] = []
  let node: Node | null = start

  while (node) {
    nodes.push(node)
    if (node === end) break
    node = node.nextSibling
  }

  return nodes
}

function collectFrameContentFragment(
  doc: Document,
  start: Comment,
  end: Comment,
): DocumentFragment {
  let fragment = doc.createDocumentFragment()
  let node = start.nextSibling

  while (node && node !== end) {
    let next = node.nextSibling
    fragment.appendChild(node)
    node = next
  }

  return fragment
}

function removeNode(node: Node, parent: ParentNode, context: FrameContext): void {
  disposeRemovedVirtualRoots(node)
  disposeRemovedSubFrames(node, context)

  if (node.parentNode === parent) {
    parent.removeChild(node)
  }
}

function disposeRemovedVirtualRoots(node: Node): void {
  let stack: Node[] = [node]
  while (stack.length > 0) {
    let next = stack.pop()
    if (!next) continue

    if (isHydratedVirtualRootStartMarker(next)) {
      next.$rmx.dispose()
      continue
    }

    for (let child of Array.from(next.childNodes)) {
      stack.push(child)
    }
  }
}

function disposeRemovedSubFrames(node: Node, context: FrameContext): void {
  let stack: Node[] = [node]
  while (stack.length > 0) {
    let next = stack.pop()
    if (!next) continue

    if (isFrameStartMarker(next)) {
      disposeFrameStartMarker(next, context)
    }

    for (let child of Array.from(next.childNodes)) {
      stack.push(child)
    }
  }
}

function disposeFrameStartMarker(marker: Comment, context: FrameContext): void {
  let subFrame = context.frameInstances.get(marker)
  if (subFrame) {
    subFrame.dispose()
    context.frameInstances.delete(marker)
  }
}

function isVirtualRootStartMarker(node: Node): node is Comment {
  return isCommentNode(node) && node.data.trim().startsWith('rmx:h:')
}

function isHydratedVirtualRootStartMarker(node: Node): node is HydratedVirtualRootStartMarker {
  return isVirtualRootStartMarker(node) && '$rmx' in node
}

function isVirtualRootEndMarker(node: Node): node is Comment {
  return isCommentNode(node) && node.data.trim() === '/rmx:h'
}