-- lx-bundle:true

--- Tokenize syntax lines into styled text spans
-- Handles tracing, pattern resolution, and nested subsyntaxes

local syntax_registry = require("core.syntax")
local config = require("core.config")
local plugin = require("core.plugin")
local utf8help = require("core.text.utf8help")

local tokenizer = {}
local module_ref_cache = {}
local warned_bad_patterns = setmetatable({}, { __mode = "k" })
local warned_bad_pattern_keys = {}
local warned_bad_subsyntax_specs = setmetatable({}, { __mode = "k" })
local warned_bad_line_patterns = setmetatable({}, { __mode = "k" })
local warned_bad_line_pattern_keys = {}
local trace_state = {
	enabled = false,
	module = nil,
	path = nil,
	fp = nil,
}

local keycap_token_trace_enabled = false

do
	local value = os.getenv("LX_TOKEN_DEBUG_KEYCAP")
	keycap_token_trace_enabled = value ~= nil and value ~= "" and value ~= "0"
end

--- Return the default syntax trace log path
-- Uses the current executable name when available
-- @return string default trace log path
local function get_trace_default_path()
	local exe_name = rawget(_G, "EXE_NAME")
	if type(exe_name) ~= "string" or exe_name == "" then
		exe_name = "lx"
	end
	return exe_name .. "syntax.log"
end

--- Close the active syntax trace sink
-- Clears the stored file handle state after closing
-- @return nil
local function close_trace_sink()
	if trace_state.fp then
		pcall(trace_state.fp.close, trace_state.fp)
		trace_state.fp = nil
	end
end

--- Write one line to the active syntax trace sink
-- Disables tracing when a write fails
-- @param line string|nil line text to append
-- @return nil
local function trace_write_line(line)
	if not trace_state.enabled or not trace_state.fp then
		return
	end

	-- Protect the tokenizer when the trace file becomes unusable
	local ok = pcall(trace_state.fp.write, trace_state.fp, tostring(line or "") .. "\r\n")

	if not ok then
		close_trace_sink()
		trace_state.enabled = false
	end
end

--- Return the syntax identifier used by tracing
-- Prefers stable module names before display labels
-- @param syntax_definition table|any syntax definition or fallback value
-- @return string syntax identifier
local function get_trace_syntax_id(syntax_definition)
	if type(syntax_definition) ~= "table" then
		return tostring(syntax_definition or "syntax")
	end
	return syntax_definition._module_name or syntax_definition.shortname or syntax_definition.name or "syntax"
end

--- Escape text for single-line trace output
-- Replaces control bytes and trims very long payloads
-- @param text string|nil trace payload
-- @return string escaped text
local function trace_escape_text(text)
	local escaped_text = tostring(text or "")

	-- Escape control-sensitive characters before logging the line
	escaped_text = escaped_text:gsub("\\", "\\\\")
	escaped_text = escaped_text:gsub("[%z\1-\31\127]", function(ch)
		return string.format("\\x%02X", string.byte(ch))
	end)
	escaped_text = escaped_text:gsub("\r", "\\r")
	escaped_text = escaped_text:gsub("\n", "\\n")
	escaped_text = escaped_text:gsub("\t", "\\t")

	-- Keep trace lines compact enough to scan in a log file
	if #escaped_text > 180 then
		escaped_text = escaped_text:sub(1, 180) .. "..."
	end
	return escaped_text
end

--- Format text bytes for trace output
-- @param text string source text
-- @return string formatted byte list
local function format_trace_bytes(text)
	local out = {}

	-- Emit bytes in order so broken UTF-8 boundaries are easy to inspect
	for index = 1, #text do
		out[#out + 1] = string.format("%02X", text:byte(index))
	end

	return table.concat(out, " ")
end

--- Check whether text contains keycap-related bytes
-- Limits special tracing to lines that need it
-- @param text string source text
-- @return boolean has keycap-related bytes
local function contains_keycap_trace_bytes(text)
	return text:find("\226\131\163", 1, true) ~= nil or text:find("\239\184\143", 1, true) ~= nil
end

--- Emit token diagnostics for keycap-related text
-- Writes a compact byte dump to stderr when the debug flag is enabled
-- @param text string source line
-- @param tokens table token result list
-- @return nil
local function emit_keycap_token_trace(text, tokens)
	if not keycap_token_trace_enabled or not contains_keycap_trace_bytes(text) then
		return
	end

	io.stderr:write(string.format("[token-keycap] line bytes=%s\n", format_trace_bytes(text)))

	-- Print the final token stream so byte ownership is visible
	for index = 1, #tokens, 2 do
		io.stderr:write(string.format(
			"[token-keycap] token[%d] type=%s bytes=%s text=%s\n",
			math.floor((index + 1) / 2),
			tostring(tokens[index]),
			format_trace_bytes(tokens[index + 1] or ""),
			trace_escape_text(tokens[index + 1] or "")
		))
	end
end

--- Emit one syntax trace event
-- Skips output when tracing is disabled or filtered to another syntax
-- @param syn table|any syntax being traced
-- @param fmt string message format
-- @param ... any format arguments
-- @return nil
local function trace_emit(syn, fmt, ...)
	if not trace_state.enabled then
		return
	end

	-- Ignore trace events outside the selected syntax filter
	local syntax_id = get_trace_syntax_id(syn)
	local filter = trace_state.module
	if filter and syntax_id ~= filter then
		return
	end
	local msg = string.format(fmt, ...)
	trace_write_line(string.format("[%s] %s", syntax_id, msg))
end

--- Append a token to the result list
-- Merges adjacent tokens when safe and repairs grapheme boundaries between token types
-- @param t table token result list
-- @param type string token type
-- @param text string|nil token text
-- @return nil
local function push_token(t, type, text)
	if not text or #text == 0 then
		return
	end

	local prev_type = t[#t - 1]
	local prev_text = t[#t]

	-- Merge adjacent text when the token type stays the same
	if prev_type and (prev_type == type) then
		t[#t - 1] = type
		t[#t] = prev_text .. text
	else
		table.insert(t, type)
		table.insert(t, text)
	end

	local current_text = t[#t]
	local first_byte = current_text and current_text:byte(1)

	-- ASCII starts and single-token results cannot have a split grapheme boundary
	if not first_byte or first_byte < 0x80 or #t < 4 then
		return
	end

	local current_type = t[#t - 1]
	local previous_type = t[#t - 3]
	local previous_text = t[#t - 2]

	-- Same-type neighbors were already merged in the previous step
	if not current_type or not previous_type or not previous_text or previous_type == current_type then
		return
	end

	-- Move leading combining bytes back to the token that owns the grapheme
	local resolved_previous_text, resolved_current_text = utf8help.resolve_boundary(previous_text, current_text)

	if resolved_previous_text == previous_text then
		return
	end

	t[#t - 2] = resolved_previous_text

	-- Drop the current token if boundary repair consumed all of its text
	if resolved_current_text == "" then
		table.remove(t)
		table.remove(t)
	else
		t[#t] = resolved_current_text
	end
end

--- Resolve the base token type for a pattern
-- Uses the first table entry when a pattern defines capture types
-- @param pattern_type string|table|nil raw pattern type
-- @return string|nil base token type
local function resolve_pattern_type(pattern_type)
	if type(pattern_type) == "table" then
		return pattern_type[1]
	end
	return pattern_type
end

--- Resolve capture-aware highlight settings
-- Returns capture token types and the fallback type for uncaptured text
-- @param p table|any syntax pattern
-- @return table|nil capture_types capture token types
-- @return string|nil base_type fallback token type
local function resolve_capture_highlighting(p)
	if type(p) ~= "table" then
		return nil, nil
	end

	-- Delimited pattern tables manage their own token typing elsewhere
	if type(p.pattern) == "table" and p.delim_type then
		return nil, nil
	end

	if type(p.type) == "table" then
		if #p.type == 0 then
			return nil, nil
		end
		local base_type = (#p.type > 1) and p.type[1] or "normal"
		return p.type, base_type
	end
	return nil, nil
end

--- Resolve the syntax match selection strategy
-- Falls back to 'first' when the syntax does not declare a valid strategy
-- @param syn table|any syntax definition
-- @return string strategy name
local function resolve_match_strategy(syn)
	local match_cfg = type(syn) == "table" and syn.match or nil
	local strategy = type(match_cfg) == "table" and match_cfg.strategy or nil
	if
		strategy == "longest"
		or strategy == "priority_longest"
		or strategy == "priority_first"
		or strategy == "first"
	then
		return strategy
	end
	return "first"
end

--- Resolve the numeric priority for a pattern
-- Non-numeric and NaN values collapse to zero
-- @param p table|any syntax pattern
-- @return number priority value
local function resolve_pattern_priority(p)
	local v = type(p) == "table" and p.priority or nil
	v = tonumber(v) or 0
	if v ~= v then
		return 0
	end
	return v
end

--- Decide whether a candidate should replace the current best match
-- Applies the active strategy using priority, match length, and pattern order
-- @param best table|nil current best candidate
-- @param candidate table next candidate to compare
-- @param strategy string match strategy
-- @return boolean should replace the current best match
-- Keep one shared order lookup so renamed candidate fields stay comparable
local function get_candidate_order(candidate)
	return candidate.pattern_index or candidate.rule_index
end

local function should_replace_match(best, candidate, strategy)
	if not best then
		return true
	end

	local candidate_order = get_candidate_order(candidate)
	local best_order = get_candidate_order(best)

	-- Prefer higher priority, then longer matches, then earlier patterns
	if strategy == "priority_longest" then
		if candidate.priority ~= best.priority then
			return candidate.priority > best.priority
		end
		if candidate.length ~= best.length then
			return candidate.length > best.length
		end
		return candidate_order < best_order
	end
	if strategy == "priority_first" then
		if candidate.priority ~= best.priority then
			return candidate.priority > best.priority
		end
		return candidate_order < best_order
	end

	-- Prefer the longest match before falling back to pattern order
	if strategy == "longest" then
		if candidate.length ~= best.length then
			return candidate.length > best.length
		end
		return candidate_order < best_order
	end
	return false
end

--- Warn once about an invalid syntax pattern entry
-- Tracks table entries and derived keys so repeated failures do not spam the log
-- @param syntax table|any owning syntax definition
-- @param idx number|any pattern index
-- @param p table|any invalid pattern entry
-- @param reason string|nil human-readable failure reason
-- @return nil
local function warn_bad_pattern(syntax, idx, p, reason)
	local key

	-- Cache warnings by pattern table when possible, otherwise by a stable text key
	if type(p) == "table" then
		if warned_bad_patterns[p] then
			return
		end
	else
		key = string.format(
			"%s|%d|%s|%s",
			tostring((type(syntax) == "table" and (syntax.shortname or syntax.name)) or "syntax"),
			tonumber(idx) or -1,
			tostring(reason or "invalid pattern"),
			type(p)
		)
		if warned_bad_pattern_keys[key] then
			return
		end
	end

	-- Report invalid syntax data through the shared core error channel
	local msg = string.format(
		"Invalid syntax pattern in %s[%d]: %s",
		tostring((type(syntax) == "table" and (syntax.shortname or syntax.name)) or "syntax"),
		tonumber(idx) or -1,
		tostring(reason or "invalid pattern")
	)
	local core = package.loaded["core"]
	core.error("%s", msg)

	if type(p) == "table" then
		warned_bad_patterns[p] = true
	elseif key then
		warned_bad_pattern_keys[key] = true
	end
end

--- Warn once about an invalid line-pattern rule
-- Tracks table entries and derived keys so repeated failures do not spam the log
-- @param syntax table|any owning syntax definition
-- @param idx number|any rule index
-- @param rule table|any invalid rule entry
-- @param reason string|nil human-readable failure reason
-- @return nil
local function warn_bad_line_pattern(syntax, idx, rule, reason)
	local key

	-- Cache warnings by rule table when possible, otherwise by a stable text key
	if type(rule) == "table" then
		if warned_bad_line_patterns[rule] then
			return
		end
	else
		key = string.format(
			"%s|%d|%s|%s",
			tostring((type(syntax) == "table" and (syntax.shortname or syntax.name)) or "syntax"),
			tonumber(idx) or -1,
			tostring(reason or "invalid line pattern"),
			type(rule)
		)
		if warned_bad_line_pattern_keys[key] then
			return
		end
	end

	-- Report invalid line-pattern data through the shared core error channel
	local msg = string.format(
		"Invalid line_patterns rule in %s[%d]: %s",
		tostring((type(syntax) == "table" and (syntax.shortname or syntax.name)) or "syntax"),
		tonumber(idx) or -1,
		tostring(reason or "invalid line pattern")
	)
	local core = package.loaded["core"]
	core.error("%s", msg)

	if type(rule) == "table" then
		warned_bad_line_patterns[rule] = true
	elseif key then
		warned_bad_line_pattern_keys[key] = true
	end
end

--- Guess the source file path for a syntax module name
-- Converts known module prefixes into project-relative source hints
-- @param module_name string|nil module name
-- @return string|nil source hint path
local function get_source_hint_for_module(module_name)
	if type(module_name) ~= "string" or module_name == "" then
		return nil
	end
	if module_name:sub(1, 7) == "syntax." then
		return "data/syntax/" .. module_name:sub(8):gsub("%.", "/") .. ".lua"
	end
	if module_name:sub(1, 8) == "plugins." then
		local path = plugin.get_module_path(module_name, PLUGINS_DIR)
		if path then
			return path:gsub("\\", "/")
		end
		return "data/plugins/" .. module_name:sub(9):gsub("%.", "/") .. ".lua"
	end
	return nil
end

--- Build a readable detail string for a subsyntax reference
-- Includes the owner syntax, pattern index, raw spec, and source hint when known
-- @param syn table|any owning syntax definition
-- @param pattern_index number|any pattern index
-- @param spec string|any raw syntax specifier
-- @return string detail string
local function get_subsyntax_detail(syn, pattern_index, spec)
	local module_name = type(syn) == "table" and syn._module_name or nil
	local display_name = type(syn) == "table" and (syn.shortname or syn.name) or nil
	local owner = nil

	-- Prefer the module name because it points back to the syntax source
	if type(module_name) == "string" and module_name ~= "" then
		owner = module_name
	elseif type(display_name) == "string" and display_name ~= "" then
		owner = display_name
	else
		owner = "unknown"
	end
	local src = get_source_hint_for_module(module_name)
	if type(src) == "string" and src ~= "" then
		return string.format("%s[%d]=%q @ %s", owner, tonumber(pattern_index) or -1, tostring(spec), src)
	end
	return string.format("%s[%d]=%q", owner, tonumber(pattern_index) or -1, tostring(spec))
end

--- Warn once about an invalid subsyntax specifier
-- @param syn table|any owning syntax definition
-- @param pattern_index number|any pattern index
-- @param p table|any pattern entry
-- @param spec string|any raw syntax specifier
-- @return nil
local function warn_bad_subsyntax_spec_once(syn, pattern_index, p, spec)
	if type(p) == "table" then
		if warned_bad_subsyntax_specs[p] then
			return
		end
		warned_bad_subsyntax_specs[p] = true
	end

	local msg = string.format(
		"Invalid pattern.syntax value, expected 'module:<name>' or '.<ext>': %s",
		get_subsyntax_detail(syn, pattern_index, spec)
	)
	local core = package.loaded["core"]
	core.error("%s", msg)
end

--- Describe a missing or invalid pattern field
-- @param p table|any syntax pattern
-- @return string error description
local function describe_missing_pattern(p)
	if type(p) ~= "table" then
		return "missing/invalid 'pattern'"
	end

	-- Mention the first unexpected field to make syntax mistakes easier to spot
	local alt = nil
	for k, _ in pairs(p) do
		if k ~= "pattern" and k ~= "type" then
			alt = tostring(k)
			break
		end
	end
	if alt then
		return string.format("missing 'pattern' (found '%s' instead)", alt)
	end
	return "missing/invalid 'pattern'"
end

--- Look up a token type in the syntax symbol map
-- @param syn table|nil syntax definition
-- @param token_text string symbol text
-- @return string|nil mapped token type
local function lookup_symbol_type(syn, token_text)
	local symbols = syn and syn.symbols
	if type(symbols) == "table" then
		return symbols[token_text]
	end
	return nil
end

--- Resolve the post-symbol map for a matched pattern
-- Supports the shared syntax map or a named table on the syntax definition
-- @param syntax table|nil syntax definition
-- @param pattern table|any syntax pattern
-- @return table|nil symbol map
local function resolve_post_symbol_map(syntax, pattern)
	if type(pattern) ~= "table" then
		return nil
	end
	local post_symbols = pattern.post_symbols
	if post_symbols == true then
		local map = syntax and syntax.post_symbols
		return type(map) == "table" and map or nil
	end
	if type(post_symbols) == "string" and post_symbols ~= "" then
		local map = syntax and syntax[post_symbols]
		return type(map) == "table" and map or nil
	end
	return nil
end

--- Push token text and recolor nested symbols when configured
-- Splits the text into symbol and non-symbol segments before pushing tokens
-- @param res table token result list
-- @param token_type string fallback token type
-- @param token_text string token text
-- @param symbol_map table|nil symbol recolor map
-- @return nil
local function push_token_with_post_symbols(res, token_type, token_text, symbol_map)
	if type(symbol_map) ~= "table" or next(symbol_map) == nil then
		push_token(res, token_type, token_text)
		return
	end

	local i = 1
	while i <= #token_text do
		-- Reuse the normal symbol pattern so nested identifiers are split consistently
		local match_start, match_end = token_text:find("^" .. config.symbol_pattern, i)
		if match_start then
			local token = token_text:sub(match_start, match_end)
			push_token(res, symbol_map[token] or token_type, token)
			i = match_end + 1
		else
			-- Advance by one UTF-8 codepoint when the next span is not a symbol
			local next_offset = utf8.offset(token_text, 2, i)
			local codepoint_end = next_offset and (next_offset - 1) or #token_text
			push_token(res, token_type, token_text:sub(i, codepoint_end))
			i = codepoint_end + 1
		end
	end
end

--- Tokenize a line using only symbol lookups
-- Falls back to normal tokens when the syntax defines no symbol map
-- @param syntax table|nil syntax definition
-- @param text string source line
-- @return table token result list
local function tokenize_symbols_only(syntax, text)
	local symbols = syntax and syntax.symbols
	if type(symbols) ~= "table" or next(symbols) == nil then
		return { "normal", text }
	end

	local out = {}
	local i = 1
	while i <= #text do
		-- Split mapped symbols from surrounding text using the shared symbol pattern
		local match_start, match_end = text:find("^" .. config.symbol_pattern, i)
		if match_start then
			local token = text:sub(match_start, match_end)
			-- Keep non-mapped identifiers unstyled and color only declared symbols
			push_token(out, lookup_symbol_type(syntax, token) or "normal", token)
			i = match_end + 1
		else
			-- Advance by one UTF-8 codepoint when the next span is not a symbol
			local next_offset = utf8.offset(text, 2, i)
			local codepoint_end = next_offset and (next_offset - 1) or #text
			push_token(out, "normal", text:sub(i, codepoint_end))
			i = codepoint_end + 1
		end
	end
	return out
end

--- Consume one symbol token and apply symbol recoloring
-- Returns the next unread byte index when a symbol starts at the cursor
-- @param res table token result list
-- @param syntax table|nil syntax definition
-- @param text string source text
-- @param i number byte index
-- @return number|nil next byte index
local function push_symbol_or_normal_token(res, syntax, text, i)
	local match_start, match_end = text:find("^" .. config.symbol_pattern, i)
	if not match_start then
		return nil
	end
	local token = text:sub(match_start, match_end)
	push_token(res, lookup_symbol_type(syntax, token) or "normal", token)
	return match_end + 1
end

--- Collect string captures without collapsing their original indices
-- Keeps empty-string captures so later capture types stay aligned
-- @param match_data table|string raw string.find result array
-- @return table captures ordered string captures including empty strings
local function collect_string_captures(match_data)
	local captures = {}
	if type(match_data) ~= "table" then
		return captures
	end

	for capture_index = 3, #match_data do
		local capture_value = match_data[capture_index]
		if type(capture_value) == "string" then
			captures[#captures + 1] = capture_value
		end
	end

	return captures
end

--- Push a matched token span with optional capture recoloring
-- Splits the text around capture substrings and applies post-symbol recoloring to each piece
-- @param res table token result list
-- @param base_type string fallback token type
-- @param token_text string matched token text
-- @param captures table|nil captured substrings
-- @param capture_types table|nil capture token types
-- @param post_symbol_map table|nil symbol recolor map
-- @return nil
local function push_token_with_captures(res, base_type, token_text, captures, capture_types, post_symbol_map)
	if type(capture_types) ~= "table" or #capture_types == 0 or type(captures) ~= "table" or #captures == 0 then
		push_token_with_post_symbols(res, base_type, token_text, post_symbol_map)
		return
	end

	local cursor = 1
	local matched_any = false
	for i = 1, #captures do
		local cap = captures[i]
		if type(cap) == "string" and cap ~= "" then
			-- Match captures left-to-right inside the token text to keep spans stable
			local match_start, match_end = token_text:find(cap, cursor, true)
			if match_start then
				if match_start > cursor then
					push_token_with_post_symbols(res, base_type, token_text:sub(cursor, match_start - 1), post_symbol_map)
				end
				local capture_type = (#capture_types == 1) and capture_types[1] or capture_types[i] or base_type
				push_token_with_post_symbols(res, capture_type, token_text:sub(match_start, match_end), post_symbol_map)
				cursor = match_end + 1
				matched_any = true
			end
		end
	end

	if matched_any then
		if cursor <= #token_text then
			push_token_with_post_symbols(res, base_type, token_text:sub(cursor), post_symbol_map)
		end
	else
		push_token_with_post_symbols(res, base_type, token_text, post_symbol_map)
	end
end

--- Check whether a byte position is escaped
-- Counts the contiguous escape characters immediately before the position
-- @param text string source text
-- @param idx number byte index to test
-- @param esc string one-byte escape character
-- @return boolean is escaped
local function is_escaped(text, idx, esc)
	local byte = esc:byte()
	local count = 0
	for i = idx - 1, 1, -1 do
		if text:byte(i) ~= byte then
			break
		end
		count = count + 1
	end
	return count % 2 == 1
end

--- Find the next unescaped match for a Lua pattern
-- Repeats the search until the match start is not escaped by the given byte
-- @param text string source text
-- @param pattern string Lua pattern
-- @param offset number start index
-- @param esc string|nil one-byte escape character
-- @return number|nil match start
-- @return number|nil match end
local function find_non_escaped(text, pattern, offset, esc)
	while true do
		local match_start, match_end = text:find(pattern, offset)
		if not match_start then
			break
		end
		if esc and is_escaped(text, match_start, esc) then
			offset = match_end + 1
		else
			return match_start, match_end
		end
	end
end

--- Extend a match to include its closing delimiter on the same line
-- Pair-pattern rules search for the first non-escaped closer after the opener
-- @param text string source line
-- @param p table syntax pattern
-- @param start_end_idx number current match end
-- @return number resolved end index
local function get_guard_end(text, p, start_end_idx)
	if type(p.pattern) ~= "table" then
		return start_end_idx
	end
	if type(p.pattern[2]) ~= "string" or p.pattern[2] == "" then
		return start_end_idx
	end
	local _, close_e = find_non_escaped(text, p.pattern[2], start_end_idx + 1, p.pattern[3])
	return close_e or start_end_idx
end

--- Apply an optional stop guard to a matched span
-- 'stop_on' and 'terminators' use Lua pattern syntax against the matched text
-- @param text string source text
-- @param p table|any syntax pattern
-- @param s number match start
-- @param e number match end
-- @return number|nil adjusted start
-- @return number|nil adjusted end
-- @return boolean was adjusted by stop guard
local function apply_stop_guard(text, p, s, e)
	if type(p) ~= "table" or type(p.pattern) == "table" then
		return s, e, false
	end

	-- Accept either stop_on or the older terminators field for the guard pattern
	local stop_pattern = p.stop_on
	if type(stop_pattern) ~= "string" or stop_pattern == "" then
		stop_pattern = p.terminators
	end
	if type(stop_pattern) ~= "string" or stop_pattern == "" then
		return s, e, false
	end

	local token_text = text:sub(s, e)
	local stop_s = token_text:find(stop_pattern)
	if not stop_s then
		return s, e, false
	end

	-- Reject matches that trip the guard immediately at the start of the token
	if stop_s <= 1 then
		return nil, nil, true
	end
	return s, s + stop_s - 2, true
end

--- Select the next line-pattern candidate to evaluate
-- @param candidates table collected candidates
-- @param match_strategy string match strategy
-- @param skipped table set of skipped candidate indexes
-- @return number|nil candidate index
-- @return table|nil selected candidate
local function select_line_pattern_candidate(candidates, match_strategy, skipped)
	local best_index = nil
	local best_candidate = nil
	for candidate_index = 1, #candidates do
		if not skipped[candidate_index] then
			local candidate = candidates[candidate_index]

			-- The first-match strategy can stop as soon as it sees an eligible candidate
			if match_strategy == "first" then
				return candidate_index, candidate
			end
			if should_replace_match(best_candidate, candidate, match_strategy) then
				best_index = candidate_index
				best_candidate = candidate
			end
		end
	end
	return best_index, best_candidate
end

--- Build token-relative spans from positional captures
-- Positional captures are expected after the normal match start and end values
-- @param token_text string matched token text
-- @param match_data table match results from string.find
-- @param match_start_index number absolute match start
-- @param match_end_index number absolute match end
-- @return table|nil spans token-relative spans
-- @return string|nil error validation failure
local function build_line_pattern_spans(token_text, match_data, match_start_index, match_end_index)
	local boundary_positions = { 1 }
	local has_position_capture = false
	local previous_capture_position = nil
	local token_length = #token_text

	-- Convert positional captures into token-relative span boundaries
	for capture_index = 3, #match_data do
		local capture_value = match_data[capture_index]
		if type(capture_value) == "number" then
			has_position_capture = true
			if capture_value < match_start_index or capture_value > (match_end_index + 1) then
				return nil, "position capture is outside matched range"
			end
			local relative_position = capture_value - match_start_index + 1
			if previous_capture_position and relative_position < previous_capture_position then
				return nil, "position captures are not ordered"
			end
			boundary_positions[#boundary_positions + 1] = relative_position
			previous_capture_position = relative_position
		end
	end

	if not has_position_capture then
		return nil, nil
	end

	boundary_positions[#boundary_positions + 1] = token_length + 1

	local spans = {}
	local last_end = 0

	-- Turn the boundary list into non-overlapping token spans
	for boundary_index = 1, (#boundary_positions - 1) do
		local start_position = boundary_positions[boundary_index]
		local next_position = boundary_positions[boundary_index + 1]
		if type(start_position) ~= "number" or type(next_position) ~= "number" then
			return nil, "position capture boundary is invalid"
		end
		if next_position < start_position then
			return nil, "position capture boundaries overlap"
		end

		local end_position = next_position - 1
		if end_position >= start_position then
			if start_position <= last_end then
				return nil, "line-pattern spans overlap"
			end
			spans[#spans + 1] = {
				start_position = start_position,
				end_position = end_position,
			}
			last_end = end_position
		end
	end

	return spans, nil
end

--- Emit tokens for a selected line-pattern candidate
-- Uses positional spans when present, otherwise falls back to substring captures
-- @param result_tokens table token result list
-- @param syntax_definition table|nil owning syntax
-- @param rule table line-pattern rule
-- @param candidate table selected candidate
-- @param emit_end_index number|nil optional emission end bound
-- @return boolean emission succeeded
-- @return number|string emitted end index or error text
local function emit_line_pattern_candidate_tokens(result_tokens, syntax_definition, rule, candidate, emit_end_index)
	local token_end_index = math.min(candidate.match_end, emit_end_index or candidate.match_end)
	if token_end_index < candidate.match_start then
		return true, candidate.match_start - 1
	end

	local token_text = candidate.text:sub(candidate.match_start, token_end_index)
	local post_symbol_map = resolve_post_symbol_map(syntax_definition, rule)
	local token_type = resolve_pattern_type(rule.type)

	if not candidate.capture_types or not candidate.match_data then
		push_token_with_post_symbols(result_tokens, token_type, token_text, post_symbol_map)
		return true, token_end_index
	end

	local spans, span_error = build_line_pattern_spans(
		token_text,
		candidate.match_data,
		candidate.match_start,
		token_end_index
	)
	if span_error then
		return false, span_error
	end

	-- Fall back to substring captures when the match did not supply positional boundaries
	if not spans then
		push_token_with_captures(
			result_tokens,
			candidate.capture_base_type,
			token_text,
			candidate.captures,
			candidate.capture_types,
			post_symbol_map
		)
		return true, token_end_index
	end

	if #candidate.capture_types ~= #spans then
		return false, string.format(
			"type/span length mismatch: types=%d spans=%d",
			#candidate.capture_types,
			#spans
		)
	end

	-- Emit each positional span with its aligned capture type
	for span_index = 1, #spans do
		local span = spans[span_index]
		local span_type = candidate.capture_types[span_index] or token_type or "normal"
		local span_text = token_text:sub(span.start_position, span.end_position)
		if span_text ~= "" then
			push_token_with_post_symbols(result_tokens, span_type, span_text, post_symbol_map)
		end
	end

	return true, token_end_index
end

--- Resolve the consume boundary for a line-pattern candidate
-- Supports full-line consume_line or a positional consume_to capture index
-- @param rule table|any line-pattern rule
-- @param candidate table selected candidate
-- @param line_length number current line length
-- @return number|nil consume end index
-- @return string|nil error validation failure
local function resolve_line_pattern_consume_end(rule, candidate, line_length)
	if type(rule) ~= "table" then
		return nil, nil
	end

	if rule.consume_line == true then
		return line_length, nil
	end

	local consume_to = rule.consume_to
	if consume_to == nil then
		return nil, nil
	end

	local capture_index = tonumber(consume_to)
	if
		type(capture_index) ~= "number"
		or capture_index ~= math.floor(capture_index)
		or capture_index < 1
	then
		return nil, "consume_to must be an integer capture index"
	end
	if not candidate.match_data then
		return nil, "consume_to requires capture data"
	end

	-- Only count positional '()' captures so text capture edits do not renumber consume boundaries
	local positional_capture_index = 0
	local capture_value = nil
	for match_data_index = 3, #candidate.match_data do
		local match_data_value = candidate.match_data[match_data_index]
		if type(match_data_value) == "number" then
			positional_capture_index = positional_capture_index + 1
			if positional_capture_index == capture_index then
				capture_value = match_data_value
				break
			end
		end
	end
	if type(capture_value) ~= "number" then
		return nil, "consume_to positional capture is missing"
	end

	if capture_value < candidate.match_start or capture_value > (candidate.match_end + 1) then
		return nil, "consume_to capture is outside matched range"
	end

	local consume_end = capture_value - 1
	if consume_end < 0 or consume_end > line_length then
		return nil, "consume_to resolved outside line bounds"
	end

	return consume_end, nil
end

--- Run the optional line-pattern prepass
-- Emits tokens for a selected rule and returns the byte index where normal tokenization should continue
-- @param syntax_definition table|nil syntax definition
-- @param text string current line
-- @param next_text string|nil next line text
-- @param result_tokens table token result list
-- @param start_index number|nil first byte to inspect
-- @param max_consume_end_index number|nil maximum byte index the prepass may consume
-- @return number next byte index for normal tokenization
local function run_line_patterns_prepass(
	syntax_definition,
	text,
	next_text,
	result_tokens,
	start_index,
	max_consume_end_index
)
	local line_patterns = type(syntax_definition) == "table" and syntax_definition.line_patterns or nil
	if type(line_patterns) ~= "table" or #line_patterns == 0 then
		return start_index or 1
	end
	start_index = start_index or 1
	local line_end_index = #text
	if
		type(max_consume_end_index) == "number"
		and max_consume_end_index >= (start_index - 1)
		and max_consume_end_index < line_end_index
	then
		line_end_index = max_consume_end_index
	end
	local line_text = text:sub(start_index, line_end_index)
	if line_text == "" then
		return start_index
	end

	-- Trace the exact line slice inspected by the prepass
	trace_emit(
		syntax_definition,
		"line_prepass begin rules=%d start=%d text=%q",
		#line_patterns,
		start_index,
		trace_escape_text(line_text)
	)

	local match_strategy = resolve_match_strategy(syntax_definition)
	local candidates = {}

	for rule_index, rule in ipairs(line_patterns) do
		-- Validate each rule and collect only the candidates that match this line slice
		if type(rule) ~= "table" then
			warn_bad_line_pattern(syntax_definition, rule_index, rule, "entry is not a table")
			goto continue_line_rule
		end
		if rule.next_line and (not next_text or not next_text:match(rule.next_line)) then
			goto continue_line_rule
		end
		if rule.syntax ~= nil then
			warn_bad_line_pattern(syntax_definition, rule_index, rule, "line_patterns does not support 'syntax'")
			trace_emit(syntax_definition, "line_prepass skip_invalid rule=%d reason=%q", rule_index, "unsupported syntax")
			goto continue_line_rule
		end

		local pattern = (type(rule.pattern) == "table") and rule.pattern[1] or rule.pattern
		if type(pattern) ~= "string" or pattern == "" then
			warn_bad_line_pattern(syntax_definition, rule_index, rule, describe_missing_pattern(rule))
			trace_emit(syntax_definition, "line_prepass skip_invalid rule=%d reason=%q", rule_index, "missing pattern")
			goto continue_line_rule
		end
		if type(rule.pattern) == "table" then
			warn_bad_line_pattern(syntax_definition, rule_index, rule, "line_patterns does not support pair pattern tables")
			trace_emit(syntax_definition, "line_prepass skip_invalid rule=%d reason=%q", rule_index, "pair pattern unsupported")
			goto continue_line_rule
		end

		local match_data = { line_text:find("^" .. pattern, 1) }
		local match_start, match_end = match_data[1], match_data[2]
		if not match_start then
			goto continue_line_rule
		end

		local stop_adjusted
		match_start, match_end, stop_adjusted = apply_stop_guard(line_text, rule, match_start, match_end)
		if not match_start then
			goto continue_line_rule
		end
		if stop_adjusted then
			match_data = nil
		end

		if rule.line_prefix then
			local prefix = line_text:sub(1, match_start - 1)
			if not prefix:match("^" .. rule.line_prefix .. "$") then
				goto continue_line_rule
			end
		end
		if rule.preceded_by then
			local prefix = line_text:sub(1, match_start - 1)
			if not prefix:match(rule.preceded_by .. "$") then
				goto continue_line_rule
			end
		end
		local guard_end_index = get_guard_end(line_text, rule, match_end)
		if rule.not_followed_by then
			local suffix = line_text:sub(guard_end_index + 1)
			if suffix:match("^" .. rule.not_followed_by) then
				goto continue_line_rule
			end
		end
		if rule.followed_by then
			local suffix = line_text:sub(guard_end_index + 1)
			if not suffix:match("^" .. rule.followed_by) then
				goto continue_line_rule
			end
		end

		local capture_types, capture_base_type = resolve_capture_highlighting(rule)
	-- Keep empty string captures so later capture types do not shift left
	local captures = (match_data and capture_types) and collect_string_captures(match_data) or {}

		candidates[#candidates + 1] = {
			rule_index = rule_index,
			rule = rule,
			match_start = match_start,
			match_end = match_end,
			match_data = match_data,
			captures = captures,
			capture_types = capture_types,
			capture_base_type = capture_base_type,
			length = match_end - match_start + 1,
			priority = resolve_pattern_priority(rule),
			text = line_text,
		}

		::continue_line_rule::
	end

	local skipped_candidates = {}
	while true do
		-- Re-run selection after each skipped invalid candidate until one succeeds
		local candidate_index, candidate = select_line_pattern_candidate(candidates, match_strategy, skipped_candidates)
		if not candidate then
			return start_index
		end
		local rule = candidate.rule
		local skip_candidate = false
		local consume_end_index, consume_error = resolve_line_pattern_consume_end(rule, candidate, #line_text)
		if consume_error then
			warn_bad_line_pattern(syntax_definition, candidate.rule_index, rule, consume_error)
			trace_emit(
				syntax_definition,
				"line_prepass skip_invalid rule=%d reason=%q",
				candidate.rule_index,
				trace_escape_text(consume_error)
			)
			skipped_candidates[candidate_index] = true
			skip_candidate = true
		end

		if not skip_candidate then
			trace_emit(
				syntax_definition,
				"line_prepass winner rule=%d span=%d-%d len=%d",
				candidate.rule_index,
				start_index + candidate.match_start - 1,
				start_index + candidate.match_end - 1,
				candidate.length
			)

			if consume_end_index then
				-- Emit only the rule-owned portion before filling the consumed remainder as normal text
				local emit_end_index = math.min(consume_end_index, candidate.match_end)
				local emitted_ok, emit_result = emit_line_pattern_candidate_tokens(
					result_tokens,
					syntax_definition,
					rule,
					candidate,
					emit_end_index
				)
				if not emitted_ok then
					local emit_error = tostring(emit_result or "line-pattern token emission failed")
					warn_bad_line_pattern(syntax_definition, candidate.rule_index, rule, emit_error)
					trace_emit(
						syntax_definition,
						"line_prepass skip_invalid rule=%d reason=%q",
						candidate.rule_index,
						trace_escape_text(emit_error)
					)
					skipped_candidates[candidate_index] = true
					skip_candidate = true
				end

				if not skip_candidate then
					local emitted_end_index = tonumber(emit_result) or 0
					if consume_end_index > emitted_end_index then
						push_token(result_tokens, "normal", line_text:sub(emitted_end_index + 1, consume_end_index))
					end
					trace_emit(
						syntax_definition,
						"line_prepass consume rule=%d end=%d",
						candidate.rule_index,
						start_index + consume_end_index - 1
					)
					return start_index + consume_end_index
				end
			else
				return start_index
			end
		end

	end
end

--- Check whether a syntax contains subsyntax pair patterns
-- Caches the result on the syntax table because the answer is stable for the file lifetime
-- @param syntax table syntax definition
-- @return boolean has subsyntax patterns
local function has_subsyntax_patterns(syntax)
	local cached = rawget(syntax, "_has_subsyntax_patterns")
	if cached ~= nil then
		return cached
	end
	local yes = false
	for _, pattern_definition in ipairs(syntax.patterns or {}) do
		if
			type(pattern_definition) == "table"
			and type(pattern_definition.pattern) == "table"
			and pattern_definition.syntax ~= nil
		then
			yes = true
			break
		end
	end
	rawset(syntax, "_has_subsyntax_patterns", yes)
	return yes
end

--- Resolve and cache a pattern's subsyntax target
-- Supports inline syntax tables, 'module:<name>', and file-extension lookups
-- @param p table syntax pattern
-- @param syn table|any owning syntax definition
-- @param pattern_index number|any pattern index
-- @return table|nil resolved subsyntax
local function resolve_pattern_syntax(p, syn, pattern_index)
	--- Check whether a syntax is the plain-text fallback
	-- Plain Text is rejected because it would hide broken subsyntax refs
	-- @param syn table|nil syntax definition
	-- @return boolean is the plain-text fallback
	local function is_plain_syntax(syn)
		return syn and syn.name == "Plain Text" and syn.shortname == "Plain Text"
	end

	local cached = rawget(p, "_resolved_syntax")
	if cached ~= nil then
		return cached ~= false and cached or nil
	end

	local spec = p.syntax
	local resolved = nil
	if type(spec) == "table" then
		-- Accept inline syntax tables when they look like a real syntax definition
		if type(spec.patterns) == "table" and not is_plain_syntax(spec) then
			resolved = spec
		end
	elseif type(spec) == "string" and spec ~= "" then
		local module_ref = nil
		if spec:sub(1, 7) == "module:" then
			local module_name = spec:sub(8)
			if module_name ~= "" then
				module_ref = "syntax." .. module_name
			else
				warn_bad_subsyntax_spec_once(syn, pattern_index, p, spec)
			end
		end

		if module_ref then
			-- Reuse the module cache so nested subsyntax lookup stays cheap
			local mod_cached = module_ref_cache[module_ref]
			if mod_cached ~= nil then
				resolved = (mod_cached ~= false) and mod_cached or nil
				rawset(p, "_resolved_syntax", resolved or false)
				return resolved
			end

			-- Try the module directly, then scan the registry for the syntax object it registered
			local before_count = #syntax_registry.items
			local ok, mod = pcall(require, module_ref)
			if ok and type(mod) == "table" and type(mod.patterns) == "table" and not is_plain_syntax(mod) then
				resolved = mod
			end
			for i = #syntax_registry.items, 1, -1 do
				local item = syntax_registry.items[i]
				if type(item) == "table" and item._module_name == module_ref then
					if type(item.patterns) == "table" and not is_plain_syntax(item) then
						resolved = item
						break
					end
				end
			end
			if not resolved and ok and #syntax_registry.items > before_count then
				for i = #syntax_registry.items, before_count + 1, -1 do
					local item = syntax_registry.items[i]
					if type(item) == "table" and type(item.patterns) == "table" and not is_plain_syntax(item) then
						resolved = item
						break
					end
				end
			end
			module_ref_cache[module_ref] = resolved or false
		elseif spec:sub(1, 1) == "." then
			-- Extension refs resolve through the normal syntax registry lookup path
			resolved = syntax_registry.get("file" .. spec, "", false)
			if is_plain_syntax(resolved) then
				resolved = nil
			end
		else
			warn_bad_subsyntax_spec_once(syn, pattern_index, p, spec)
		end
	end

	rawset(p, "_resolved_syntax", resolved or false)
	return resolved
end

--- Tokenize a line without nested subsyntax support
-- This is the fast path for syntaxes that only use their own patterns
-- @param syntax table syntax definition
-- @param text string current line
-- @param state number|nil open pair pattern index
-- @param next_text string|nil next line text
-- @return table token result list
-- @return number|nil next state
local function tokenize_basic(syntax, text, state, next_text)
	local res = {}
	local i = 1
	local line_prepass_pending = true

	if #syntax.patterns == 0 then
		return tokenize_symbols_only(syntax, text)
	end

	while i <= #text do
		-- Continue an open pair pattern before testing any new starts
		if state then
			local active_pattern = syntax.patterns[state]
			if
				type(active_pattern) ~= "table"
				or type(active_pattern.pattern) ~= "table"
				or type(active_pattern.pattern[2]) ~= "string"
				or active_pattern.pattern[2] == ""
			then
				warn_bad_pattern(syntax, state, active_pattern, "invalid open pair state")
				state = nil
				goto continue_after_state
			end
			local close_start, close_end = find_non_escaped(text, active_pattern.pattern[2], i, active_pattern.pattern[3])
			local state_type = resolve_pattern_type(active_pattern.type)

			if close_start then
				-- Emit either the full close span or split content and delimiter tokens
				if active_pattern.delim_type then
					local content = text:sub(i, close_start - 1)
					local delim = text:sub(close_start, close_end)
					if #content > 0 then
						push_token(res, state_type, content)
					end
					push_token(res, active_pattern.delim_type, delim)
				else
					push_token(res, state_type, text:sub(i, close_end))
				end
				state = nil
				i = close_end + 1
			else
				push_token(res, state_type, text:sub(i))
				break
			end
		end
		::continue_after_state::

		if line_prepass_pending then
			line_prepass_pending = false
			if i == 1 and not state then
				-- Run the line prepass once before normal token matching starts
				i = run_line_patterns_prepass(syntax, text, next_text, res, i)
				if i > #text then
					break
				end
			end
		end

		-- Collect the best matching pattern at the current cursor
		local matched = false
		local match_strategy = resolve_match_strategy(syntax)
		local best_match = nil
		for pattern_index, pattern_definition in ipairs(syntax.patterns) do
			if type(pattern_definition) ~= "table" then
				warn_bad_pattern(syntax, pattern_index, pattern_definition, "entry is not a table")
				goto continue
			end
			if pattern_definition.next_line and (not next_text or not next_text:match(pattern_definition.next_line)) then
				goto continue
			end
			if pattern_definition.not_preceded_by and i > 1 then
				local prev_char = text:sub(i - 1, i - 1)
				if prev_char:match(pattern_definition.not_preceded_by) then
					goto continue
				end
			end
				local pattern = (type(pattern_definition.pattern) == "table") and pattern_definition.pattern[1]
					or pattern_definition.pattern
				if type(pattern) ~= "string" or pattern == "" then
					warn_bad_pattern(syntax, pattern_index, pattern_definition, describe_missing_pattern(pattern_definition))
					goto continue
				end
				if not pattern_definition.line_start or i == 1 then
					local match_start, match_end, match_data
					local capture_types, capture_base_type = resolve_capture_highlighting(pattern_definition)
					if capture_types then
						match_data = { text:find("^" .. pattern, i) }
						match_start, match_end = match_data[1], match_data[2]
					else
						match_start, match_end = text:find("^" .. pattern, i)
					end

					if match_start then
						local stop_adjusted
						match_start, match_end, stop_adjusted =
							apply_stop_guard(text, pattern_definition, match_start, match_end)
						if not match_start then
							goto continue
						end
						if stop_adjusted then
							match_data = nil
							capture_types = nil
							capture_base_type = nil
						end

						if pattern_definition.line_prefix then
							local prefix = text:sub(1, match_start - 1)
							if not prefix:match("^" .. pattern_definition.line_prefix .. "$") then
								goto continue
							end
						end
						if pattern_definition.preceded_by then
							local prefix = text:sub(1, match_start - 1)
							if not prefix:match(pattern_definition.preceded_by .. "$") then
								goto continue
							end
						end
						local guard_end = get_guard_end(text, pattern_definition, match_end)
						if pattern_definition.not_followed_by then
							local suffix = text:sub(guard_end + 1)
							if suffix:match("^" .. pattern_definition.not_followed_by) then
								goto continue
							end
						end
						if pattern_definition.followed_by then
							local suffix = text:sub(guard_end + 1)
							if not suffix:match("^" .. pattern_definition.followed_by) then
								goto continue
							end
						end

						local candidate = {
							pattern_index = pattern_index,
							pattern_definition = pattern_definition,
							match_start = match_start,
							match_end = match_end,
							match_data = match_data,
							capture_types = capture_types,
							capture_base_type = capture_base_type,
							length = match_end - match_start + 1,
							priority = resolve_pattern_priority(pattern_definition),
						}

						-- Trace every valid candidate before the strategy picks a winner
						trace_emit(
							syntax,
							"candidate i=%d rule=%d span=%d-%d len=%d prio=%d pattern=%q",
							i,
							pattern_index,
							match_start,
							match_end,
							candidate.length,
							candidate.priority,
							trace_escape_text(pattern)
						)

						if match_strategy == "first" then
							best_match = candidate
							break
						end
						if should_replace_match(best_match, candidate, match_strategy) then
							best_match = candidate
						end
					end
				end
				::continue::
			end
			if best_match then
				local matched_pattern_index = best_match.pattern_index
				local matched_pattern = best_match.pattern_definition
				local match_end = best_match.match_end
				local match_data = best_match.match_data
				local capture_types = best_match.capture_types
				local capture_base_type = best_match.capture_base_type

				-- Emit the winning match with its final token type
				local matched_text = text:sub(best_match.match_start, match_end)
				local token_type = resolve_pattern_type(matched_pattern.type)
				if type(matched_pattern.pattern) == "table" and matched_pattern.delim_type then
					token_type = matched_pattern.delim_type
				end
				trace_emit(
					syntax,
					"winner i=%d rule=%d span=%d-%d type=%s text=%q",
					i,
					matched_pattern_index,
					best_match.match_start,
					match_end,
					tostring(token_type),
					trace_escape_text(matched_text)
				)

				if keycap_token_trace_enabled then
					local suspicious_boundary, previous_codepoint, next_codepoint =
						utf8help.has_suspicious_boundary(text, match_end)

					if suspicious_boundary then
						io.stderr:write(string.format(
							"[token-boundary] suspicious span=%d-%d prev=U+%04X next=U+%04X left=%s right=%s\n",
							best_match.match_start,
							match_end,
							previous_codepoint,
							next_codepoint,
							format_trace_bytes(text:sub(best_match.match_start, match_end)),
							format_trace_bytes(text:sub(match_end + 1))
						))
					end
				end

				local post_symbol_map = resolve_post_symbol_map(syntax, matched_pattern)

				-- Prefer symbol recoloring first, then capture-aware recoloring, then the base type
				local symbol_type = lookup_symbol_type(syntax, matched_text)
				if not symbol_type and capture_types and match_data then
					-- Preserve empty capture slots so optional groups keep their assigned types
					local captures = collect_string_captures(match_data)
					if #captures > 0 then
						push_token_with_captures(
							res,
							capture_base_type,
							matched_text,
							captures,
							capture_types,
							post_symbol_map
						)
					else
						push_token_with_post_symbols(res, token_type, matched_text, post_symbol_map)
					end
				else
					push_token_with_post_symbols(res, symbol_type or token_type, matched_text, post_symbol_map)
				end

				-- Pair patterns keep their rule index as the open state for the next line segment
				if type(matched_pattern.pattern) == "table" then
					state = matched_pattern_index
				end

				-- Move past the emitted token and continue scanning
				i = match_end + 1
				matched = true
			end

		-- Fall back to symbol-aware single-token consumption when nothing matched
		if not matched then
			trace_emit(syntax, "fallback i=%d char=%q", i, trace_escape_text(text:sub(i, i)))
			local ni = push_symbol_or_normal_token(res, syntax, text, i)
			if ni then
				i = ni
			else
				push_token(res, "normal", text:sub(i, i))
				i = i + 1
			end
		end
	end

	return res, state
end

--- Rebuild nested tokenizer context from state bytes
-- Walks the serialized state stack and resolves the active syntax and open pattern
-- @param base_syntax table root syntax definition
-- @param state string serialized tokenizer state
-- @return table current syntax
-- @return table|nil subsyntax_info owning subsyntax entry pattern
-- @return number current_pattern_idx open pattern index in the current syntax
-- @return number current_level serialized stack depth
local function retrieve_syntax_state(base_syntax, state)
	local current_syntax, subsyntax_info, current_pattern_idx, current_level = base_syntax, nil, state:byte(1) or 0, 1
	if current_pattern_idx > 0 and current_syntax.patterns[current_pattern_idx] then
		-- Replay each state byte until the path stops resolving cleanly
		for i = 1, #state do
			local target = state:byte(i)
			if target ~= 0 and current_syntax.patterns[target] then
				local pattern = current_syntax.patterns[target]
				if type(pattern) ~= "table" then
					break
				end
				if pattern.syntax then
					local subsyntax = resolve_pattern_syntax(pattern, current_syntax, target)
					if not subsyntax then
						break
					end
					subsyntax_info = pattern
					current_syntax = subsyntax
					current_pattern_idx = 0
					current_level = i + 1
				else
					current_pattern_idx = target
					break
				end
			else
				break
			end
		end
	end
	return current_syntax, subsyntax_info, current_pattern_idx, current_level
end

--- Return embedded syntaxes active in a serialized state
-- The list is ordered from innermost to outermost and excludes the base syntax
-- @param base_syntax table base syntax definition
-- @param state string|number serialized state
-- @return table active embedded syntaxes
function tokenizer.extract_subsyntaxes(base_syntax, state)
	local out = {}
	if type(base_syntax) ~= "table" then
		return out
	end
	if type(state) == "number" then
		state = string.char(state)
	elseif type(state) ~= "string" then
		return out
	end
	if state == "" then
		return out
	end

	local cursor = state
	local seen = {}
	while #cursor > 0 do
		-- Shift through the state bytes and keep each resolved embedded syntax once
		local syn = retrieve_syntax_state(base_syntax, cursor)
		if type(syn) == "table" and syn ~= base_syntax and not seen[syn] then
			out[#out + 1] = syn
			seen[syn] = true
		end
		cursor = cursor:sub(2)
	end
	return out
end

--- Tokenize a line with nested subsyntax support
-- Tracks a stack of embedded syntaxes encoded into the returned state string
-- @param base_syntax table root syntax definition
-- @param text string current line
-- @param state string|number|nil serialized tokenizer state
-- @param next_text string|nil next line text
-- @return table token result list
-- @return string serialized next state
local function tokenize_subsyntax(base_syntax, text, state, next_text)
	local res = {}
	local i = 1
	local line_prepass_pending = true

	if #base_syntax.patterns == 0 then
		return tokenize_symbols_only(base_syntax, text), nil
	end

	if type(state) == "number" then
		state = string.char(state)
	elseif type(state) ~= "string" or state == "" then
		state = string.char(0)
	end

	local current_syntax, subsyntax_info, current_pattern_idx, current_level = retrieve_syntax_state(base_syntax, state)

	--- Store the current open-pattern index in the serialized state
	-- @param pattern_idx number pattern index for the current syntax level
	-- @return nil
	local function set_subsyntax_pattern_idx(pattern_idx)
		current_pattern_idx = pattern_idx
		local state_len = #state
		if current_level > state_len then
			state = state .. string.char(pattern_idx)
		elseif state_len == 1 then
			state = string.char(pattern_idx)
		else
			state = ("%s%s%s"):format(
				state:sub(1, current_level - 1),
				string.char(pattern_idx),
				state:sub(current_level + 1)
			)
		end
	end

	--- Enter one nested subsyntax level
	-- @param entering_pattern table pattern that opened the subsyntax
	-- @param pattern_idx number opening pattern index
	-- @param subsyntax table resolved subsyntax
	-- @return nil
	local function push_subsyntax(entering_pattern, pattern_idx, subsyntax)
		set_subsyntax_pattern_idx(pattern_idx)
		current_level = current_level + 1
		subsyntax_info = entering_pattern
		current_syntax = subsyntax
		current_pattern_idx = 0
		line_prepass_pending = true
	end

	--- Leave the current subsyntax level
	-- @return nil
	local function pop_subsyntax()
		current_level = current_level - 1
		state = state:sub(1, current_level)
		set_subsyntax_pattern_idx(0)
		current_syntax, subsyntax_info, current_pattern_idx, current_level = retrieve_syntax_state(base_syntax, state)
		line_prepass_pending = true
	end

	while i <= #text do
		-- Continue an open pair in the current syntax before testing new matches
		if current_pattern_idx > 0 then
			local active_pattern = current_syntax.patterns[current_pattern_idx]
			if
				type(active_pattern) ~= "table"
				or type(active_pattern.pattern) ~= "table"
				or type(active_pattern.pattern[2]) ~= "string"
				or active_pattern.pattern[2] == ""
			then
				warn_bad_pattern(current_syntax, current_pattern_idx, active_pattern, "invalid open pair state")
				set_subsyntax_pattern_idx(0)
				goto continue_after_sub_state
			end
			local close_start, close_end = find_non_escaped(
				text,
				active_pattern.pattern[2],
				i,
				active_pattern.pattern[3]
			)
			local token_type = resolve_pattern_type(active_pattern.type)
			local cont = true

			-- Let the enclosing subsyntax close first when its delimiter appears earlier
			if subsyntax_info then
				if
					type(subsyntax_info.pattern) ~= "table"
					or type(subsyntax_info.pattern[2]) ~= "string"
					or subsyntax_info.pattern[2] == ""
				then
					warn_bad_pattern(
						current_syntax,
						current_pattern_idx,
						subsyntax_info,
						"invalid subsyntax close pattern"
					)
					pop_subsyntax()
					goto continue_after_sub_state
				end
				local ss = find_non_escaped(text, subsyntax_info.pattern[2], i, subsyntax_info.pattern[3])
				if ss and (not close_start or ss < close_start) then
					push_token(res, token_type, text:sub(i, ss - 1))
					i = ss
					cont = false
				end
			end

			if cont then
				if close_start then
					-- Emit either the full close span or split content and delimiter tokens
					if active_pattern.delim_type then
						local content = text:sub(i, close_start - 1)
						local delim = text:sub(close_start, close_end)
						if #content > 0 then
							push_token(res, token_type, content)
						end
						push_token(res, active_pattern.delim_type, delim)
					else
						push_token(res, token_type, text:sub(i, close_end))
					end
					set_subsyntax_pattern_idx(0)
					i = close_end + 1
				else
					push_token(res, token_type, text:sub(i))
					break
				end
			end
		end
		::continue_after_sub_state::

		-- Close nested syntaxes whose delimiter starts exactly at the cursor
		while subsyntax_info do
			if
				type(subsyntax_info.pattern) ~= "table"
				or type(subsyntax_info.pattern[2]) ~= "string"
				or subsyntax_info.pattern[2] == ""
			then
				warn_bad_pattern(current_syntax, current_pattern_idx, subsyntax_info, "invalid subsyntax close pattern")
				pop_subsyntax()
				goto continue_sub_close
			end
			local ss, se = find_non_escaped(text, subsyntax_info.pattern[2], i, subsyntax_info.pattern[3])
			if ss and ss == i then
				local t = text:sub(ss, se)
				local token_type = subsyntax_info.delim_type or resolve_pattern_type(subsyntax_info.type)
				push_token(res, token_type, t)
				pop_subsyntax()
				i = se + 1
			else
				break
			end
			::continue_sub_close::
		end

		if line_prepass_pending then
			line_prepass_pending = false
			if current_pattern_idx == 0 then
				-- Limit prepass consumption so it does not cross an enclosing subsyntax close
				local prepass_start_index = i
				local prepass_consume_limit = nil
				if
					subsyntax_info
					and type(subsyntax_info.pattern) == "table"
					and type(subsyntax_info.pattern[2]) == "string"
					and subsyntax_info.pattern[2] ~= ""
				then
					local close_start = find_non_escaped(text, subsyntax_info.pattern[2], i, subsyntax_info.pattern[3])
					if close_start then
						prepass_consume_limit = close_start - 1
					end
				end
				i = run_line_patterns_prepass(current_syntax, text, next_text, res, i, prepass_consume_limit)
				if i ~= prepass_start_index and i <= #text then
					goto continue_after_sub_state
				end
				if i > #text then
					break
				end
			end
		end

		-- Collect the best match from the currently active syntax
		local matched = false
		local match_strategy = resolve_match_strategy(current_syntax)
		local best_match = nil
		for pattern_index, pattern_definition in ipairs(current_syntax.patterns) do
			if type(pattern_definition) ~= "table" then
				warn_bad_pattern(current_syntax, pattern_index, pattern_definition, "entry is not a table")
				goto continue
			end
			if pattern_definition.next_line and (not next_text or not next_text:match(pattern_definition.next_line)) then
				goto continue
			end
			if pattern_definition.not_preceded_by and i > 1 then
				local prev_char = text:sub(i - 1, i - 1)
				if prev_char:match(pattern_definition.not_preceded_by) then
					goto continue
				end
			end
				local pattern = (type(pattern_definition.pattern) == "table") and pattern_definition.pattern[1]
					or pattern_definition.pattern
				if type(pattern) ~= "string" or pattern == "" then
					warn_bad_pattern(
						current_syntax,
						pattern_index,
						pattern_definition,
						describe_missing_pattern(pattern_definition)
					)
					goto continue
				end
				if not pattern_definition.line_start or i == 1 then
					local match_start, match_end, match_data
					local capture_types, capture_base_type = resolve_capture_highlighting(pattern_definition)
					if capture_types then
						match_data = { text:find("^" .. pattern, i) }
						match_start, match_end = match_data[1], match_data[2]
					else
						match_start, match_end = text:find("^" .. pattern, i)
					end
					if match_start then
						local stop_adjusted
						match_start, match_end, stop_adjusted =
							apply_stop_guard(text, pattern_definition, match_start, match_end)
						if not match_start then
							goto continue
						end
						if stop_adjusted then
							match_data = nil
							capture_types = nil
							capture_base_type = nil
						end

						if pattern_definition.line_prefix then
							local prefix = text:sub(1, match_start - 1)
							if not prefix:match("^" .. pattern_definition.line_prefix .. "$") then
								goto continue
							end
						end
						if pattern_definition.preceded_by then
							local prefix = text:sub(1, match_start - 1)
							if not prefix:match(pattern_definition.preceded_by .. "$") then
								goto continue
							end
						end
						local guard_end = get_guard_end(text, pattern_definition, match_end)
						if pattern_definition.not_followed_by then
							local suffix = text:sub(guard_end + 1)
							if suffix:match("^" .. pattern_definition.not_followed_by) then
								goto continue
							end
						end
						if pattern_definition.followed_by then
							local suffix = text:sub(guard_end + 1)
							if not suffix:match("^" .. pattern_definition.followed_by) then
								goto continue
							end
						end

						local candidate = {
							pattern_index = pattern_index,
							pattern_definition = pattern_definition,
							match_start = match_start,
							match_end = match_end,
							match_data = match_data,
							capture_types = capture_types,
							capture_base_type = capture_base_type,
							length = match_end - match_start + 1,
							priority = resolve_pattern_priority(pattern_definition),
						}

						-- Trace every valid candidate before the strategy picks a winner
						trace_emit(
							current_syntax,
							"candidate i=%d rule=%d span=%d-%d len=%d prio=%d pattern=%q",
							i,
							pattern_index,
							match_start,
							match_end,
							candidate.length,
							candidate.priority,
							trace_escape_text(pattern)
						)

						if match_strategy == "first" then
							best_match = candidate
							break
						end
						if should_replace_match(best_match, candidate, match_strategy) then
							best_match = candidate
						end
					end
				end
				::continue::
			end
			if best_match then
				local matched_pattern_index = best_match.pattern_index
				local matched_pattern = best_match.pattern_definition
				local match_end = best_match.match_end
				local match_data = best_match.match_data
				local capture_types = best_match.capture_types
				local capture_base_type = best_match.capture_base_type

				-- Emit the winning match with its final token type
				local matched_text = text:sub(best_match.match_start, match_end)
				local token_type = resolve_pattern_type(matched_pattern.type)
				if type(matched_pattern.pattern) == "table" and matched_pattern.delim_type then
					token_type = matched_pattern.delim_type
				end
				trace_emit(
					current_syntax,
					"winner i=%d rule=%d span=%d-%d type=%s text=%q",
					i,
					matched_pattern_index,
					best_match.match_start,
					match_end,
					tostring(token_type),
					trace_escape_text(matched_text)
				)
				local post_symbol_map = resolve_post_symbol_map(current_syntax, matched_pattern)

				-- Prefer symbol recoloring first, then capture-aware recoloring, then the base type
				local symbol_type = lookup_symbol_type(current_syntax, matched_text)
				if not symbol_type and capture_types and match_data then
					-- Preserve empty capture slots so optional groups keep their assigned types
					local captures = collect_string_captures(match_data)
					if #captures > 0 then
						push_token_with_captures(
							res,
							capture_base_type,
							matched_text,
							captures,
							capture_types,
							post_symbol_map
						)
					else
						push_token_with_post_symbols(res, token_type, matched_text, post_symbol_map)
					end
				else
					push_token_with_post_symbols(res, symbol_type or token_type, matched_text, post_symbol_map)
				end

				-- Pair patterns either enter a subsyntax or keep their local open-state index
				if type(matched_pattern.pattern) == "table" then
					local subsyntax = matched_pattern.syntax
						and resolve_pattern_syntax(matched_pattern, current_syntax, matched_pattern_index)
						or nil
					if subsyntax then
						push_subsyntax(matched_pattern, matched_pattern_index, subsyntax)
					else
						set_subsyntax_pattern_idx(matched_pattern_index)
					end
				end

				-- Move past the emitted token and continue scanning
				i = match_end + 1
				matched = true
			end

		-- Fall back to symbol-aware single-token consumption when nothing matched
		if not matched then
			trace_emit(current_syntax, "fallback i=%d char=%q", i, trace_escape_text(text:sub(i, i)))
			local ni = push_symbol_or_normal_token(res, current_syntax, text, i)
			if ni then
				i = ni
			else
				push_token(res, "normal", text:sub(i, i))
				i = i + 1
			end
		end
	end

	return res, state
end

--- Tokenize one line of text with the given syntax
-- Chooses the fast path when the syntax has no nested subsyntax patterns
-- @param syntax table syntax definition
-- @param text string current line
-- @param state string|number|nil tokenizer state from the previous line
-- @param next_text string|nil next line text
-- @return table token result list
-- @return string|number|nil next tokenizer state
function tokenizer.tokenize(syntax, text, state, next_text)
	trace_emit(
		syntax,
		"tokenize begin state=%s next=%s text=%q",
		trace_escape_text(state),
		tostring(next_text ~= nil),
		trace_escape_text(text)
	)

	local tokens
	local out_state
	if not has_subsyntax_patterns(syntax) then
		-- Convert serialized string state back to the numeric fast-path state
		if type(state) == "string" and state ~= "" then
			local b = state:byte(1)
			state = (b and b > 0) and b or nil
		end
		tokens, out_state = tokenize_basic(syntax, text, state, next_text)
	else
		tokens, out_state = tokenize_subsyntax(syntax, text, state, next_text)
	end

	trace_emit(
		syntax,
		"tokenize end state=%s tokens=%d",
		trace_escape_text(out_state),
		math.floor((#tokens or 0) / 2)
	)

	emit_keycap_token_trace(text, tokens)

	return tokens, out_state
end

--- Iterate a token array stored as alternating type and text entries
-- @param t table token result list
-- @param i number current raw array index
-- @return number|nil next raw array index
-- @return string|nil token type
-- @return string|nil token text
local function iter(t, i)
	i = i + 2
	local type, text = t[i], t[i + 1]
	if type then
		return i, type, text
	end
end

--- Return an iterator over token type and text pairs
-- @param t table token result list
-- @return function iterator
-- @return table token result list
-- @return number initial raw array index
function tokenizer.each_token(t)
	return iter, t, -1
end

--- Validate one pattern.syntax string value
-- Accepts file extensions and 'module:<name>' references
-- @param spec string|any raw syntax specifier
-- @return boolean is valid
local function is_valid_subsyntax_string(spec)
	if type(spec) ~= "string" or spec == "" then
		return false
	end
	if spec:sub(1, 1) == "." then
		return true
	end
	if spec:sub(1, 7) == "module:" then
		return spec:sub(8) ~= ""
	end
	return false
end

--- Audit loaded syntaxes for invalid pattern.syntax string formats
-- Returns counts and a bounded list of detail entries
-- @param opts table|nil audit options
-- @return table report with total_invalid and details fields
function tokenizer.audit_subsyntax_refs(opts)
	opts = opts or {}
	local syntax_mod = opts.syntax or syntax_registry
	local core_mod = opts.core or package.loaded["core"]
	local details_limit = tonumber(opts.details_limit) or 10
	local details = {}
	local total_invalid = 0
	local scanned = {}

	--- Scan one syntax table once
	-- @param syn table|any syntax definition
	-- @return nil
	local function scan_one_syntax(syn)
		if type(syn) ~= "table" or scanned[syn] then
			return
		end
		scanned[syn] = true
		local patterns = syn.patterns
		if type(patterns) ~= "table" then
			return
		end
		for i = 1, #patterns do
			local pattern_definition = patterns[i]
			if type(pattern_definition) == "table" then
				local spec = pattern_definition.syntax
				if type(spec) == "string" and spec ~= "" and not is_valid_subsyntax_string(spec) then
						total_invalid = total_invalid + 1
						if #details < details_limit then
							details[#details + 1] = {
								detail = get_subsyntax_detail(syn, i, spec),
								pattern_index = i,
								spec = spec,
							}
						end
				end
			end
		end
	end

	-- Optionally scan the registry entries reachable through the public lookup helpers
	if opts.include_registry == true and type(syntax_mod) == "table" then
		local get_available = syntax_mod.get_available
		if type(get_available) == "function" then
			-- Touch only registry metadata here so startup audit stays lazy
			get_available()
		end
	end

	-- Always scan the currently loaded syntax items table when available
	if type(syntax_mod) == "table" and type(syntax_mod.items) == "table" then
		for i = 1, #syntax_mod.items do
			scan_one_syntax(syntax_mod.items[i])
		end
	end

	if opts.log_summary == true and total_invalid > 0 then
		local msg
		local shown = #details
		if shown > 0 then
				local formatted = {}
				for i = 1, shown do
					local d = details[i]
					formatted[#formatted + 1] = d.detail
				end
			-- Summarize the first detail entries and mention how many were omitted
			local suffix = total_invalid > shown and string.format(" (+%d more)", total_invalid - shown) or ""
			msg = string.format(
				"Invalid pattern.syntax string formats found: %d total; %s%s",
				total_invalid,
				table.concat(formatted, ", "),
				suffix
			)
		else
			msg = string.format("Invalid pattern.syntax string formats found: %d total", total_invalid)
		end

		if core_mod then
			core_mod.error("%s", msg)
		else
			print("[tokenizer] " .. msg)
		end
	end

	return {
		total_invalid = total_invalid,
		details = details,
	}
end

--- Start syntax trace logging and recreate the sink file
-- @param opts table|nil trace options: module (string|nil), path (string|nil)
-- @return boolean success flag
-- @return string|nil sink path on success, or error message on failure
function tokenizer.trace_start(opts)
	opts = opts or {}

	local module_filter = opts.module
	if module_filter ~= nil and type(module_filter) ~= "string" then
		return false, "trace module filter must be string or nil"
	end
	if module_filter == "" then
		module_filter = nil
	end

	local path = (type(opts.path) == "string" and opts.path ~= "") and opts.path or get_trace_default_path()

	close_trace_sink()

	local fp, err = io.open(path, "wb")
	if not fp then
		-- Preserve the requested path so callers can report it even on failure
		trace_state.enabled = false
		trace_state.module = nil
		trace_state.path = path
		return false, tostring(err or "failed to open trace sink")
	end

	pcall(fp.setvbuf, fp, "line")

	-- Store the new sink before emitting the start marker
	trace_state.enabled = true
	trace_state.module = module_filter
	trace_state.path = path
	trace_state.fp = fp

	trace_write_line(string.format(
		"[syntax-trace] start module=%s",
		tostring(module_filter or "*")
	))

	return true, path
end

--- Stop active syntax trace logging
-- @return boolean true when tracing was active and is now stopped
function tokenizer.trace_stop()
	local was_enabled = trace_state.enabled == true
	if was_enabled then
		trace_write_line("[syntax-trace] stop")
	end
	trace_state.enabled = false
	trace_state.module = nil
	close_trace_sink()
	return was_enabled
end

--- Return the current syntax trace runtime status
-- @return table status with enabled, module and path fields
function tokenizer.trace_status()
	return {
		enabled = trace_state.enabled == true,
		module = trace_state.module,
		path = trace_state.path,
	}
end

--- Resolve a syntax identifier string for trace filtering and labels
-- @param syntax_definition table|string|nil syntax definition table or id
-- @return string syntax identifier
function tokenizer.trace_get_syntax_id(syntax_definition)
	return get_trace_syntax_id(syntax_definition)
end

return tokenizer
