// SPDX-FileCopyrightText: 2024 Christoph Sax <c_sax@mailbox.org>
//
// SPDX-License-Identifier: EUPL-1.2

use std::{cmp::Ordering, ops::Range};

use serde::Serialize;

use tree_sitter::{Node, Tree, TreeCursor};

use crate::{
    config::SemanticTokenEncoding,
    ls::doc::{GlobalMacroDefIndex, TextDoc, TextDocData, TextDocs},
    protocol::{
        Location, LocationLink, Position, Range as LRange, SemanticTokens, SemanticTokensLegend,
        Uri,
    },
    t32::{
        FindMacroRefsLangContext, FindRefsLangContext, GotoDefLangContext, MacroDefinition,
        MacroDefinitionResult, MacroScope, NodeKind, SemanticToken, Subroutine,
        do_syntax_highlighting, do_syntax_highlighting_in_range, find_command_file_target,
        find_command_identifier, find_label_references, find_macro_definition_references,
        find_stack_macro_references, find_subroutine_call_references, find_subroutine_references,
        get_find_ref_ids, get_goto_def_ids, get_macro_scope, goto_external_macro_definition,
        goto_file, goto_infile_macro_definition, goto_subroutine_definition, id_into_node,
        locate_calls_to_file_target,
    },
    utils::BRange,
};

#[derive(Debug, PartialEq)]
pub enum FindDefintionsForMacroRefResult {
    Final(Vec<MacroDefinitionLocation>, Uri),
    Partial(Vec<MacroDefinitionLocation>, Uri, Vec<Uri>),
}

#[derive(Debug, PartialEq)]
pub enum FindReferencesResult {
    Final(Vec<Location>),
    Partial(FindReferencesPartialResult),
}

#[derive(Debug, PartialEq)]
pub enum FindReferencesPartialResult {
    Command(String),
    MacroDefsComplete {
        origin: MacroReferenceOrigin,
        definitions: Vec<(FileLocation, Option<MacroScope>)>,
    },
    MacroDefsIncomplete {
        origin: MacroReferenceOrigin,
        definitions: Vec<(FileLocation, Option<MacroScope>)>,
    },
    FileTarget {
        origin_uri: Uri,
        target: String,
    },
}

// TODO: Use dedicated types for GoToExternalMacroDef results. The first two
// elements do not have to be repeated in this case.
#[derive(Debug, PartialEq)]
pub enum GotoDefinitionResult {
    Final(Vec<LocationLink>),
    PartialMacro(Uri, String, LRange, Vec<LocationLink>),
}

#[derive(Clone, Debug)]
pub enum MacroDefinitionLocation {
    Private(BRange),
    Local(BRange),
    Global(BRange),
}

#[derive(Debug)]
pub struct FindMacroReferencesResult {
    pub uri: Uri,
    pub references: Vec<LRange>,
    pub subscripts: Vec<Uri>,
}

#[derive(Clone, Debug, PartialEq, Serialize)]
pub struct MacroReferenceOrigin {
    pub name: String,
    pub span: LRange,
    pub uri: Uri,
}

#[derive(Clone, Debug, PartialEq)]
pub struct FileLocation {
    pub uri: Uri,
    pub range: BRange,
}

#[derive(Debug)]
struct SemanticTokenIntegerEncoded {
    pub line: u32,
    pub character: u32,
    pub len: u32,
    pub r#type: u32,
    pub r#modifier: u32,
}

#[derive(Debug)]
struct SemanticTokenAbsoluteEncoding(pub SemanticTokenIntegerEncoded);

#[derive(Debug)]
struct SemanticTokenRelativeEncoding(pub SemanticTokenIntegerEncoded);

impl FindMacroReferencesResult {
    pub fn build(uri: Uri, locations: Vec<LRange>, subscripts: Vec<Uri>) -> Self {
        FindMacroReferencesResult {
            uri,
            references: locations,
            subscripts,
        }
    }
}

impl MacroDefinitionLocation {
    pub fn split(self) -> (MacroScope, BRange) {
        match self {
            Self::Private(span) => (MacroScope::Private, span),
            Self::Local(span) => (MacroScope::Local, span),
            Self::Global(span) => (MacroScope::Global, span),
        }
    }
}

impl LocationLink {
    pub fn build(
        doc: &TextDoc,
        origin: Option<Range<usize>>,
        uri: Uri,
        target_range: Range<usize>,
        target_sel: Range<usize>,
    ) -> Self {
        LocationLink {
            origin_selection_range: match origin {
                Some(range) => Some(doc.to_range(range.start, range.end)),
                None => None,
            },
            target_uri: uri,
            target_range: doc.to_range(target_range.start, target_range.end),
            target_selection_range: doc.to_range(target_sel.start, target_sel.end),
        }
    }

    pub fn from_macro_def(doc: &TextDoc, origin: BRange, r#macro: MacroDefinition) -> Self {
        let (target_range, target_sel) = if let Some(docstring) = r#macro.docstring {
            let start: Range<usize> = Range {
                start: docstring.start,
                end: r#macro.cmd.end,
            };
            (start, r#macro.r#macro)
        } else {
            (r#macro.cmd, r#macro.r#macro)
        };

        LocationLink::build(
            &doc,
            Some(origin.into()),
            doc.uri.clone(),
            target_range,
            target_sel,
        )
    }

    pub fn from_ext_macro_def(doc: &TextDoc, origin: LRange, r#macro: MacroDefinition) -> Self {
        let (target_range, target_sel) = if let Some(docstring) = r#macro.docstring {
            let start: Range<usize> = Range {
                start: docstring.start,
                end: r#macro.cmd.end,
            };
            (start, r#macro.r#macro)
        } else {
            (r#macro.cmd, r#macro.r#macro)
        };

        LocationLink {
            origin_selection_range: Some(origin),
            target_uri: doc.uri.clone(),
            target_range: doc.to_range(target_range.start, target_range.end),
            target_selection_range: doc.to_range(target_sel.start, target_sel.end),
        }
    }
}

impl Eq for MacroDefinitionLocation {}

impl Ord for MacroDefinitionLocation {
    fn cmp(&self, other: &Self) -> Ordering {
        match self {
            MacroDefinitionLocation::Private(span)
            | MacroDefinitionLocation::Local(span)
            | MacroDefinitionLocation::Global(span) => match other {
                MacroDefinitionLocation::Private(other_span)
                | MacroDefinitionLocation::Local(other_span)
                | MacroDefinitionLocation::Global(other_span) => {
                    let cmp = span.cmp(other_span);
                    if cmp != Ordering::Equal {
                        return cmp;
                    }
                }
            },
        }
        match self {
            MacroDefinitionLocation::Private(_) => match other {
                MacroDefinitionLocation::Private(_) => Ordering::Equal,
                MacroDefinitionLocation::Local(_) | MacroDefinitionLocation::Global(_) => {
                    Ordering::Less
                }
            },
            MacroDefinitionLocation::Local(_) => match other {
                MacroDefinitionLocation::Private(_) => Ordering::Greater,
                MacroDefinitionLocation::Local(_) => Ordering::Equal,
                MacroDefinitionLocation::Global(_) => Ordering::Less,
            },
            MacroDefinitionLocation::Global(_) => match other {
                MacroDefinitionLocation::Private(_) | MacroDefinitionLocation::Local(_) => {
                    Ordering::Greater
                }
                MacroDefinitionLocation::Global(_) => Ordering::Equal,
            },
        }
    }
}

impl PartialEq for MacroDefinitionLocation {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

impl PartialOrd for MacroDefinitionLocation {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl MacroDefinitionLocation {
    pub fn from_macro_def(scope: MacroScope, definition: MacroDefinition) -> Self {
        match scope {
            MacroScope::Private => Self::Private(BRange::from(definition.r#macro)),
            MacroScope::Local => Self::Local(BRange::from(definition.r#macro)),
            MacroScope::Global => Self::Global(BRange::from(definition.r#macro)),
        }
    }

    pub fn from_span(scope: Option<&MacroScope>, span: BRange) -> Self {
        match scope {
            Some(MacroScope::Private) => Self::Private(span),
            // Assume block-global, if no other scope is provided.
            Some(MacroScope::Local) | None => Self::Local(span),
            Some(MacroScope::Global) => Self::Global(span),
        }
    }
}

/// Retrieves definitions for `(macro)`, `(subroutine_call_expression)`, and
/// `(command_expression)` nodes. `(command_expression)` nodes capture
/// `DO` and `RUN` commands for subscripts calls.
///   - Macros may have multiple definitions in other files due to the
///     `LOCAL` keyword. `GLOBAL` macro definitions are ignored.
///   - Subscript calls return the start of the script file.
///   - Subroutine definitions are limited to the current file.
///
/// TODO: Add detection for macros that are nested inside HLL expressions. In
///       this case the macro are detected as HLL entities.
pub fn find_definition(
    textdoc: TextDocData,
    t32: GotoDefLangContext,
    position: Position,
) -> Option<GotoDefinitionResult> {
    let offset = textdoc.doc.to_byte_offset(&position);

    let lang = textdoc.tree.language();
    let allowed_kinds = get_goto_def_ids(&lang);

    let origin = find_deepest_node(&textdoc.tree, offset, &allowed_kinds)?;

    let node = origin.node();
    let origin_span = node.range();

    match id_into_node(&lang, origin.node().kind_id()) {
        NodeKind::Macro => {
            match goto_infile_macro_definition(&textdoc.doc.text, &textdoc.tree, &t32, origin)? {
                MacroDefinitionResult::Final(gotos) => {
                    let mut links: Vec<LocationLink> = Vec::with_capacity(gotos.len());
                    for def in gotos {
                        links.push(LocationLink::from_macro_def(
                            &textdoc.doc,
                            origin_span.into(),
                            def,
                        ));
                    }
                    Some(GotoDefinitionResult::Final(links))
                }
                MacroDefinitionResult::Partial(gotos) => {
                    let mut links: Vec<LocationLink> = Vec::with_capacity(gotos.len());
                    for def in gotos {
                        links.push(LocationLink::from_macro_def(
                            &textdoc.doc,
                            origin_span.into(),
                            def,
                        ));
                    }
                    let name = textdoc.doc.text[node.byte_range()].to_string();
                    let span = textdoc
                        .doc
                        .to_range(origin_span.start_byte, origin_span.end_byte);
                    Some(GotoDefinitionResult::PartialMacro(
                        textdoc.doc.uri,
                        name,
                        span,
                        links,
                    ))
                }
                MacroDefinitionResult::Indeterminate => {
                    let name = textdoc.doc.text[node.byte_range()].to_string();
                    let span = textdoc
                        .doc
                        .to_range(origin_span.start_byte, origin_span.end_byte);
                    Some(GotoDefinitionResult::PartialMacro(
                        textdoc.doc.uri,
                        name,
                        span,
                        Vec::new(),
                    ))
                }
            }
        }
        NodeKind::CommandExpression => {
            let uri = goto_file(&textdoc.doc.text, &t32.calls.scripts?, origin)?;

            // Point to start of called script file
            Some(GotoDefinitionResult::Final(vec![LocationLink::build(
                &textdoc.doc,
                Some(Range {
                    start: origin_span.start_byte,
                    end: origin_span.end_byte,
                }),
                uri,
                Range { start: 0, end: 1 },
                Range { start: 0, end: 1 },
            )]))
        }
        // TODO: `GOSUB &macro` must look for macro definition instead of subroutine.
        NodeKind::SubroutineCallExpression => {
            let sub: Subroutine =
                goto_subroutine_definition(&textdoc.doc.text, &t32.subroutines, origin)?;
            let (target_range, target_sel) = if let Some(docstring) = sub.docstring {
                let start: Range<usize> = Range {
                    start: docstring.start,
                    end: sub.definition.end,
                };
                (start, sub.name.clone())
            } else {
                (sub.definition.clone(), sub.name.clone())
            };

            Some(GotoDefinitionResult::Final(vec![LocationLink::build(
                &textdoc.doc,
                Some(Range {
                    start: origin_span.start_byte,
                    end: origin_span.end_byte,
                }),
                textdoc.doc.uri.clone(),
                target_range,
                target_sel,
            )]))
        }
        _ => None,
    }
}

pub fn find_external_macro_definition(
    textdoc: TextDocData,
    t32: GotoDefLangContext,
    callers: Vec<Uri>,
    origin: MacroReferenceOrigin,
    backtrace: Uri,
) -> (Option<GotoDefinitionResult>, Vec<Uri>) {
    let Some(subscripts) = &t32.calls.scripts else {
        return (None, callers);
    };

    let MacroReferenceOrigin {
        name: r#macro,
        span,
        ..
    } = origin;

    let targets: Vec<BRange> = locate_calls_to_file_target(subscripts, &backtrace);
    if targets.is_empty() {
        return (None, callers);
    }

    // TODO: `RUN` clears the PRACTICE stack, so it cannot propagate
    // `LOCAL` macros.
    // TODO: Add support for `GOTO` → `(label)` transitions.
    match goto_external_macro_definition(&textdoc.doc.text, &textdoc.tree, &t32, &r#macro, targets)
    {
        Some(MacroDefinitionResult::Final(gotos)) => {
            let mut links: Vec<LocationLink> = Vec::with_capacity(gotos.len());
            for def in gotos {
                links.push(LocationLink::from_ext_macro_def(
                    &textdoc.doc,
                    span.clone(),
                    def,
                ));
            }
            (Some(GotoDefinitionResult::Final(links)), callers)
        }
        Some(MacroDefinitionResult::Partial(gotos)) => {
            let mut links: Vec<LocationLink> = Vec::with_capacity(gotos.len());
            for def in gotos {
                links.push(LocationLink::from_ext_macro_def(
                    &textdoc.doc,
                    span.clone(),
                    def,
                ));
            }

            (
                Some(GotoDefinitionResult::PartialMacro(
                    textdoc.doc.uri,
                    r#macro,
                    span.clone(),
                    links,
                )),
                callers,
            )
        }
        Some(MacroDefinitionResult::Indeterminate) => (
            Some(GotoDefinitionResult::PartialMacro(
                textdoc.doc.uri,
                r#macro,
                span,
                Vec::new(),
            )),
            callers,
        ),
        None => (None, callers),
    }
}

pub fn find_global_macro_definitions(
    docs: &TextDocs,
    macros: GlobalMacroDefIndex,
    origin: MacroReferenceOrigin,
) -> Vec<LocationLink> {
    let mut links: Vec<LocationLink> = Vec::new();

    let mut base: u32 = 0;
    for (uri, num) in macros.0.into_iter().zip(macros.1.into_iter()) {
        if uri == origin.uri {
            base += num;
            continue;
        }

        for (&r#macro, &def) in macros.2[base as usize..(base + num) as usize]
            .into_iter()
            .zip(macros.3[base as usize..(base + num) as usize].into_iter())
        {
            if *r#macro != origin.name {
                continue;
            }
            let doc = docs.get_doc(&uri).expect("Document must exist.");
            links.push(LocationLink::from_ext_macro_def(
                doc,
                origin.span.clone(),
                def.clone(),
            ));
        }
        base += num;
    }
    links
}

/// Retrieves references for `(macro)`, `(subroutine_call_expression)`,
/// `(labeled_expression)`, `(subroutine_block)`, and `(command_expression)`
/// nodes.
///    - Macro references may be located in other files if `LOCAL` was used
///      to define the macro. `GLOBAL` macros are handled separately.
///    - Subroutine references are restricted to the current file.
///    - Subscript calls should return all similar calls in other script files.
///      Similarly, for all other commands the instances in other files should
///      be included. Both are not covered here.
///
pub fn find_references(
    textdoc: TextDocData,
    t32: FindRefsLangContext,
    position: Position,
) -> Option<FindReferencesResult> {
    let offset = textdoc.doc.to_byte_offset(&position);

    let lang = textdoc.tree.language();
    let allowed_kinds = get_find_ref_ids(&lang);

    let origin = find_deepest_node(&textdoc.tree, offset, &allowed_kinds)?;
    let node = origin.node();

    match id_into_node(&lang, node.kind_id()) {
        NodeKind::CommandExpression => {
            // Selecting one of the command arguments in a `DO` or `RUN`
            // command is sufficient to trigger retrieval of all references
            // to the same file. However, if the command is selected, then
            // all references with the same command will be returned.
            if command_argument_selected(origin.clone(), offset)
                && let Some(target) = find_command_file_target(&textdoc.doc.text, origin.clone())
            {
                debug_assert_eq!(
                    origin.node().kind_id(),
                    NodeKind::CommandExpression.into_id(&lang)
                );
                Some(FindReferencesResult::Partial(
                    FindReferencesPartialResult::FileTarget {
                        origin_uri: textdoc.doc.uri,
                        target,
                    },
                ))
            } else {
                Some(FindReferencesResult::Partial(
                    FindReferencesPartialResult::Command(find_command_identifier(
                        &textdoc.doc.text,
                        origin,
                    )?),
                ))
            }
        }
        NodeKind::LabeledExpression => {
            if !position_aligned_with_node_start(&position, &textdoc.doc, &node) {
                return None;
            }

            if t32.subroutines.is_empty() {
                return None;
            }

            let mut loc: Vec<Location> = Vec::new();

            let refs = if let Some(refs) = find_subroutine_references(
                &textdoc.doc.text,
                &t32.subroutines,
                &origin,
                &textdoc.tree,
            ) {
                Some(refs)
            } else {
                find_label_references(&textdoc.doc.text, &t32.labels, &origin, &textdoc.tree)
            };

            for r#ref in refs? {
                loc.push(Location {
                    uri: textdoc.doc.uri.clone(),
                    range: textdoc.doc.to_range(r#ref.start, r#ref.end),
                });
            }
            Some(FindReferencesResult::Final(loc))
        }
        NodeKind::Macro => {
            let t32 = GotoDefLangContext::from(t32);
            match goto_infile_macro_definition(&textdoc.doc.text, &textdoc.tree, &t32, origin)? {
                MacroDefinitionResult::Final(defs) => {
                    debug_assert!(defs.len() > 0);
                    let name = textdoc.doc.text[defs[0].r#macro.clone()].to_string();

                    let mut origins: Vec<(FileLocation, Option<MacroScope>)> = Vec::new();
                    for def in defs {
                        let scope = get_macro_scope(&t32.macros, &def.r#macro);
                        origins.push((
                            FileLocation {
                                uri: textdoc.doc.uri.clone(),
                                range: BRange::from(def.r#macro),
                            },
                            scope,
                        ));
                    }

                    Some(FindReferencesResult::Partial(
                        FindReferencesPartialResult::MacroDefsComplete {
                            origin: MacroReferenceOrigin {
                                name,
                                span: textdoc.doc.to_range(node.start_byte(), node.end_byte()),
                                uri: textdoc.doc.uri,
                            },
                            definitions: origins,
                        },
                    ))
                }
                MacroDefinitionResult::Partial(defs) => {
                    let mut origins: Vec<(FileLocation, Option<MacroScope>)> = Vec::new();
                    for def in defs {
                        let scope = get_macro_scope(&t32.macros, &def.r#macro);
                        origins.push((
                            FileLocation {
                                uri: textdoc.doc.uri.clone(),
                                range: BRange::from(def.r#macro),
                            },
                            scope,
                        ));
                    }

                    Some(FindReferencesResult::Partial(
                        FindReferencesPartialResult::MacroDefsIncomplete {
                            origin: MacroReferenceOrigin {
                                name: textdoc.doc.text[node.byte_range()].to_string(),
                                span: textdoc.doc.to_range(node.start_byte(), node.end_byte()),
                                uri: textdoc.doc.uri,
                            },
                            definitions: origins,
                        },
                    ))
                }
                MacroDefinitionResult::Indeterminate => Some(FindReferencesResult::Partial(
                    FindReferencesPartialResult::MacroDefsIncomplete {
                        origin: MacroReferenceOrigin {
                            name: textdoc.doc.text[node.byte_range()].to_string(),
                            span: textdoc.doc.to_range(node.start_byte(), node.end_byte()),
                            uri: textdoc.doc.uri,
                        },
                        definitions: Vec::new(),
                    },
                )),
            }
        }
        NodeKind::SubroutineCallExpression => {
            if t32.subroutines.is_empty() {
                return None;
            }

            let mut loc: Vec<Location> = Vec::new();
            for r#ref in find_subroutine_call_references(
                &textdoc.doc.text,
                &t32.subroutines,
                origin,
                &textdoc.tree,
            )? {
                loc.push(Location {
                    uri: textdoc.doc.uri.clone(),
                    range: textdoc.doc.to_range(r#ref.start, r#ref.end),
                });
            }
            Some(FindReferencesResult::Final(loc))
        }
        NodeKind::SubroutineBlock => {
            if !position_aligned_with_node_start(&position, &textdoc.doc, &node) {
                return None;
            }

            if t32.subroutines.is_empty() {
                return None;
            }

            let mut loc: Vec<Location> = Vec::new();
            for r#ref in find_subroutine_references(
                &textdoc.doc.text,
                &t32.subroutines,
                &origin,
                &textdoc.tree,
            )? {
                loc.push(Location {
                    uri: textdoc.doc.uri.clone(),
                    range: textdoc.doc.to_range(r#ref.start, r#ref.end),
                });
            }
            Some(FindReferencesResult::Final(loc))
        }
        _ => None,
    }
}

pub fn find_external_definitions_for_macro_ref(
    textdoc: TextDocData,
    t32: GotoDefLangContext,
    callers: Vec<Uri>,
    origin: MacroReferenceOrigin,
    backtrace: Uri,
) -> FindDefintionsForMacroRefResult {
    let Some(subscripts) = &t32.calls.scripts else {
        return FindDefintionsForMacroRefResult::Final(Vec::new(), textdoc.doc.uri);
    };

    let MacroReferenceOrigin { name: r#macro, .. } = origin;

    let targets: Vec<BRange> = locate_calls_to_file_target(subscripts, &backtrace);
    if targets.is_empty() {
        return FindDefintionsForMacroRefResult::Final(Vec::new(), textdoc.doc.uri);
    }

    match goto_external_macro_definition(&textdoc.doc.text, &textdoc.tree, &t32, &r#macro, targets)
    {
        Some(MacroDefinitionResult::Final(defs)) => {
            let locations: Vec<MacroDefinitionLocation> = {
                let mut locs: Vec<MacroDefinitionLocation> = Vec::with_capacity(defs.len());
                for def in defs {
                    let Some(scope) = get_macro_scope(&t32.macros, &def.r#macro) else {
                        unreachable!(
                            "Retrieved macro definition must already have been registered."
                        );
                    };
                    locs.push(MacroDefinitionLocation::from_macro_def(scope, def));
                }
                locs
            };
            FindDefintionsForMacroRefResult::Final(locations, textdoc.doc.uri)
        }
        Some(MacroDefinitionResult::Partial(defs)) => {
            let locations: Vec<MacroDefinitionLocation> = {
                let mut locs: Vec<MacroDefinitionLocation> = Vec::with_capacity(defs.len());
                for def in defs {
                    let Some(scope) = get_macro_scope(&t32.macros, &def.r#macro) else {
                        unreachable!(
                            "Retrieved macro definition must already have been registered."
                        );
                    };
                    locs.push(MacroDefinitionLocation::from_macro_def(scope, def));
                }
                locs
            };
            FindDefintionsForMacroRefResult::Partial(locations, textdoc.doc.uri, callers)
        }
        Some(MacroDefinitionResult::Indeterminate) => {
            if callers.is_empty() {
                FindDefintionsForMacroRefResult::Final(Vec::new(), textdoc.doc.uri)
            } else {
                FindDefintionsForMacroRefResult::Partial(Vec::new(), textdoc.doc.uri, callers)
            }
        }
        None => FindDefintionsForMacroRefResult::Final(Vec::new(), textdoc.doc.uri),
    }
}

pub fn find_macro_references_from_origin(
    textdoc: TextDocData,
    t32: FindMacroRefsLangContext,
    name: String,
    origins: Vec<MacroDefinitionLocation>,
) -> FindMacroReferencesResult {
    let mut locs: Vec<LRange> = Vec::new();
    let mut callees: Vec<Uri> = Vec::new();

    for origin in origins {
        let (lifetime, loc) = origin.split();

        let (spans, mut scripts) = find_macro_definition_references(
            &textdoc.doc.text,
            &textdoc.tree,
            &t32,
            &name,
            lifetime,
            loc,
        );

        locs.reserve(spans.len());
        for span in spans {
            let inner = span.to_inner();
            locs.push(textdoc.doc.to_range(inner.start, inner.end));
        }
        scripts.retain(|s| !callees.contains(s));
        callees.append(&mut scripts);
    }
    FindMacroReferencesResult::build(textdoc.doc.uri, locs, callees)
}

pub fn find_infile_macro_references(
    textdoc: TextDocData,
    t32: FindMacroRefsLangContext,
    name: String,
) -> FindMacroReferencesResult {
    let doc = &textdoc.doc;

    // It does not matter here what exact scope the respective macro has.
    // Either `GLOBAL` or `LOCAL` will do.
    let (spans, scripts) =
        find_stack_macro_references(&doc.text, &textdoc.tree, &t32, MacroScope::Local, &name);

    let mut locs: Vec<LRange> = Vec::with_capacity(spans.len());
    for span in spans {
        let inner = span.to_inner();
        locs.push(textdoc.doc.to_range(inner.start, inner.end));
    }
    FindMacroReferencesResult::build(textdoc.doc.uri, locs, scripts)
}

pub fn command_argument_selected(mut cursor: TreeCursor, offset: usize) -> bool {
    debug_assert_eq!(
        cursor.node().kind_id(),
        NodeKind::CommandExpression.into_id(&cursor.node().language())
    );

    if cursor.goto_first_child_for_byte(offset).is_none() {
        return false;
    }

    let node = cursor.node();
    let lang = node.language();

    // Selection is on command
    if node.kind_id() != NodeKind::ArgumentList.into_id(&lang) {
        return false;
    }

    if cursor.goto_first_child_for_byte(offset).is_none() {
        return false;
    }

    if cursor.node().byte_range().contains(&offset) {
        true
    } else {
        false
    }
}

pub fn capture_semantic_tokens_full_doc(
    legend: SemanticTokensLegend,
    encoding: SemanticTokenEncoding,
    textdoc: TextDocData,
) -> SemanticTokens {
    let mut tokens = do_syntax_highlighting(legend, &textdoc.doc, &textdoc.tree);
    if !tokens.is_empty() {
        if !encoding.multiline_tokens {
            tokens = split_multiline_semantic_tokens(&textdoc.doc, tokens);
        }
        if !encoding.overlapping_tokens {
            tokens = flatten_semantic_tokens(tokens);
        }
    }
    let tokens = encode_semantic_tokens_absolute_format(&textdoc.doc, &tokens);
    let tokens = encode_semantic_tokens_relative_format(&tokens);
    let tokens = encode_semantic_tokens_integer_array(&tokens);

    SemanticTokens {
        result_id: None,
        data: tokens,
    }
}

pub fn capture_semantic_tokens_doc_range(
    legend: SemanticTokensLegend,
    encoding: SemanticTokenEncoding,
    textdoc: TextDocData,
    range: LRange,
) -> SemanticTokens {
    let mut tokens = do_syntax_highlighting_in_range(legend, &textdoc.doc, &textdoc.tree, &range);
    if !tokens.is_empty() {
        if !encoding.multiline_tokens {
            tokens = split_multiline_semantic_tokens(&textdoc.doc, tokens);
        }
        if !encoding.overlapping_tokens {
            tokens = flatten_semantic_tokens(tokens);
        }
    }
    let tokens = encode_semantic_tokens_absolute_format(&textdoc.doc, &tokens);
    let tokens = encode_semantic_tokens_relative_format(&tokens);
    let tokens = encode_semantic_tokens_integer_array(&tokens);

    SemanticTokens {
        result_id: None,
        data: tokens,
    }
}

fn find_deepest_node<'a>(tree: &'a Tree, offset: usize, stop_at: &[u16]) -> Option<TreeCursor<'a>> {
    let mut cursor = tree.walk();
    let mut sel: Option<TreeCursor> = None;

    while let Some(_) = cursor.goto_first_child_for_byte(offset) {
        let node = cursor.node();
        if !node.byte_range().contains(&offset) {
            break;
        }

        let id = node.kind_id();
        if let Some(_) = stop_at.iter().find(|&&k| k == id) {
            sel = Some(cursor.clone());
        }
    }
    sel
}

fn position_aligned_with_node_start(position: &Position, doc: &TextDoc, node: &Node) -> bool {
    let start = doc.to_position(node.start_byte());
    start.line == position.line
}

fn encode_semantic_tokens_absolute_format(
    doc: &TextDoc,
    tokens: &[SemanticToken],
) -> Vec<SemanticTokenAbsoluteEncoding> {
    if tokens.is_empty() {
        return Vec::new();
    }
    let mut encoded: Vec<SemanticTokenAbsoluteEncoding> = Vec::with_capacity(tokens.len() + 1);

    // Prepend token list with a virtual token starting at the begin of the
    // file. This simplifies the conversion to relative positions, because all
    // operations become uniform.
    encoded.push(SemanticTokenAbsoluteEncoding(SemanticTokenIntegerEncoded {
        line: 0,
        character: 0,
        len: 0,
        r#type: 0,
        modifier: 0,
    }));

    for token in tokens {
        let span = &token.span;

        // The end of a token is one character after its last character.
        let distance = doc.calculate_distance(&span.start, &span.end);

        let len = if distance > 0 { distance - 1 } else { 0 };

        encoded.push(SemanticTokenAbsoluteEncoding(SemanticTokenIntegerEncoded {
            line: span.start.line,
            character: span.start.character,
            len,
            r#type: token.r#type,
            modifier: token.modifier,
        }));
    }
    encoded
}

fn encode_semantic_tokens_relative_format(
    tokens: &[SemanticTokenAbsoluteEncoding],
) -> Vec<SemanticTokenRelativeEncoding> {
    if tokens.is_empty() {
        return Vec::new();
    }
    // The token list starts with a virtual token with length zero at position 0.
    debug_assert!(tokens.len() > 1);

    let mut encoded: Vec<SemanticTokenRelativeEncoding> = Vec::with_capacity(tokens.len());

    for (ii, SemanticTokenAbsoluteEncoding(tok)) in tokens[1..].iter().enumerate() {
        let prior = &tokens[ii].0;

        let (delta_line, delta_char): (u32, u32) = if prior.line == tok.line {
            debug_assert!(prior.character <= tok.character);
            (0, tok.character - prior.character)
        } else {
            debug_assert!(prior.line <= tok.line);
            (tok.line - prior.line, tok.character)
        };

        encoded.push(SemanticTokenRelativeEncoding(SemanticTokenIntegerEncoded {
            line: delta_line,
            character: delta_char,
            ..*tok
        }));
    }
    encoded
}

fn encode_semantic_tokens_integer_array(tokens: &[SemanticTokenRelativeEncoding]) -> Vec<u32> {
    if tokens.is_empty() {
        return Vec::new();
    }
    let mut encoded: Vec<u32> = Vec::with_capacity(tokens.len() * 5);

    for SemanticTokenRelativeEncoding(tok) in tokens {
        encoded.push(tok.line);
        encoded.push(tok.character);
        encoded.push(tok.len);
        encoded.push(tok.r#type);
        encoded.push(tok.r#modifier);
    }
    encoded
}

fn split_multiline_semantic_tokens(
    doc: &TextDoc,
    tokens: Vec<SemanticToken>,
) -> Vec<SemanticToken> {
    if !contains_multiline_tokens(&tokens) {
        return tokens;
    }

    let mut extra_tokens: Vec<SemanticToken> = Vec::with_capacity(tokens.len() + 1);
    let mut segments: Vec<SemanticToken> = Vec::with_capacity(2);

    for token in tokens {
        let (start, end) = (&token.span.start, &token.span.end);

        // Tokens ending at the end of the line have set their end to character
        // 0 of the next line. These tokens do not need to be split, because
        // their length does not take them "past the end of the line" (see
        // LSP specification).
        debug_assert!(end.line >= start.line);
        if end.line <= start.line || (end.character == 0 && end.line == start.line + 1) {
            extra_tokens.push(token);
        } else {
            distribute_multiline_token(doc, &token, &mut segments);
            extra_tokens.append(&mut segments);

            segments.clear();
        }
    }
    extra_tokens
}

fn contains_multiline_tokens(tokens: &[SemanticToken]) -> bool {
    for token in tokens {
        let (start, end) = (&token.span.start, &token.span.end);

        debug_assert!(end.line >= start.line);
        if start.line < end.line {
            return true;
        }
    }
    false
}

fn distribute_multiline_token(
    doc: &TextDoc,
    multiline_token: &SemanticToken,
    segments: &mut Vec<SemanticToken>,
) {
    debug_assert!(segments.is_empty());
    debug_assert!(multiline_token.span.start.line < multiline_token.span.end.line);

    let (start, end) = (&multiline_token.span.start, &multiline_token.span.end);

    let end_pos: Position = if let Some(eol) = doc.get_eol_character_offset(start.line as usize) {
        Position {
            line: start.line,
            character: eol,
        }
    } else {
        // We cannot determine the line length of the token start
        // position. The token cannot start at the end of the line,
        // so we recover with the minimal token length of 1.
        Position {
            line: start.line,
            character: start.character + 1,
        }
    };

    segments.push(SemanticToken {
        span: LRange {
            start: multiline_token.span.start,
            end: end_pos,
        },
        ..multiline_token.clone()
    });

    let mut offset: u32 = 1;

    while start.line + offset < end.line {
        let start_pos = Position {
            line: start.line + offset,
            character: 0,
        };

        let end_pos: Position =
            if let Some(eol) = doc.get_eol_character_offset((start.line + offset) as usize) {
                Position {
                    line: start_pos.line,
                    character: eol,
                }
            } else {
                Position {
                    line: start_pos.line,
                    character: start.character + 1,
                }
            };

        segments.push(SemanticToken {
            span: LRange {
                start: start_pos,
                end: end_pos,
            },
            ..multiline_token.clone()
        });

        offset += 1;
    }

    if end.character > 0 {
        let start_pos = Position {
            line: end.line,
            character: 0,
        };

        segments.push(SemanticToken {
            span: LRange {
                start: start_pos,
                end: multiline_token.span.end,
            },
            ..multiline_token.clone()
        });
    }
    debug_assert!(segments.len() > 1);
}

/// See [Note: Order Overlapping Semantic Tokens] for structure of overlapping
/// tokens.
fn flatten_semantic_tokens(tokens: Vec<SemanticToken>) -> Vec<SemanticToken> {
    debug_assert!(!tokens.is_empty());

    let mut flattened: Vec<SemanticToken> = Vec::with_capacity(tokens.len());

    let mut stacked_tokens: Vec<SemanticToken> = Vec::with_capacity(1);
    let mut cutoff = tokens[0].span.start;

    // The next token can only be processed if all its nested children have
    // been found. We add an extra token at the end, so that we can put the
    // complete logic inside the loop. The extra token is then discarded.
    for token in tokens.into_iter().chain([SemanticToken {
        span: LRange {
            start: Position {
                line: u32::MAX,
                character: u32::MAX,
            },
            end: Position {
                line: u32::MAX,
                character: u32::MAX,
            },
        },
        r#type: 0,
        modifier: 0,
    }]) {
        let len = stacked_tokens.len();
        if len <= 0 {
            cutoff = token.span.start;
            stacked_tokens.push(token);
            continue;
        }

        let top = &stacked_tokens[len - 1];

        if top.span.contains(&token.span) {
            let top = &top.span;
            let child = &token.span;

            // Fill gap until the nested token starts by adding filler
            // segments. Only the direct parent is checked to determine the
            // filler width.
            if top.start < child.start && cutoff < child.start {
                let filler = SemanticToken {
                    span: LRange {
                        start: top.start,
                        end: child.start,
                    },
                    ..stacked_tokens[len - 1]
                };
                flattened.push(filler);
            }
            cutoff = child.start;
        } else {
            // Deal with the prior tokens. Tokens need to be inserted until we
            // find a parent of the current token. Once we have found we have
            // to check wheter we need a filler.
            let mut ii: usize = len;
            while ii > 0 {
                let pos = ii - 1;

                if stacked_tokens[pos].span.contains(&token.span) {
                    let parent = &stacked_tokens[pos].span;
                    let child = &token.span;

                    if parent.start < child.start && cutoff < child.start {
                        let filler = SemanticToken {
                            span: LRange {
                                start: if cutoff < parent.start {
                                    parent.start
                                } else {
                                    cutoff
                                },
                                end: child.start,
                            },
                            ..stacked_tokens[pos]
                        };
                        flattened.push(filler);
                    }
                    cutoff = child.start;
                    break;
                }
                let token = stacked_tokens.pop().unwrap();

                let span = &token.span;
                if cutoff < span.end {
                    flattened.push(SemanticToken {
                        span: LRange {
                            start: if cutoff < span.start {
                                span.start
                            } else {
                                cutoff
                            },
                            end: span.end,
                        },
                        ..token
                    });
                    cutoff = span.end;
                }
                ii -= 1;
            }
        }
        stacked_tokens.push(token);
    }
    debug_assert_eq!(stacked_tokens.len(), 1);

    flattened
}

#[cfg(test)]
mod tests {
    use super::*;

    use std::{env, path};
    use url::Url;

    use crate::{
        config::T32DefaultDirs,
        ls::{
            doc::read_doc,
            workspace::{self, FileIndex},
        },
        protocol::{Range as LRange, TextDocumentItem},
        t32::{LANGUAGE_ID, LangExpressions},
        utils::{files, to_file_uri},
    };

    fn create_file_idx() -> FileIndex {
        workspace::index_files(files())
    }

    fn find_def(file: &str, position: Position) -> Option<GotoDefinitionResult> {
        let uri = Url::from_file_path(path::absolute(file).expect("File must exist.")).unwrap();

        let file_idx = workspace::index_files(files());
        let dirs = T32DefaultDirs::default();

        let (doc, tree, t32) = read_doc(uri, &file_idx, &dirs).unwrap();

        find_definition(
            TextDocData { doc, tree },
            GotoDefLangContext::from(t32),
            position,
        )
    }

    fn find_refs(file: &str, position: Position) -> Option<FindReferencesResult> {
        let uri = Url::from_file_path(path::absolute(file).expect("File must exist.")).unwrap();

        let file_idx = workspace::index_files(files());
        let dirs = T32DefaultDirs::default();

        let (doc, tree, t32) = read_doc(uri, &file_idx, &dirs).unwrap();

        find_references(
            TextDocData { doc, tree },
            FindRefsLangContext::from(t32),
            position,
        )
    }

    fn find_external_macro_def(
        file: &str,
        callers: Vec<Uri>,
        origin: MacroReferenceOrigin,
        backtrace: Uri,
    ) -> (Option<GotoDefinitionResult>, Vec<Uri>) {
        let uri = Url::from_file_path(path::absolute(file).expect("File must exist.")).unwrap();

        let file_idx = workspace::index_files(files());
        let dirs = T32DefaultDirs::default();

        let (doc, tree, t32) = read_doc(uri, &file_idx, &dirs).unwrap();

        find_external_macro_definition(
            TextDocData { doc, tree },
            GotoDefLangContext::from(t32),
            callers,
            origin,
            backtrace,
        )
    }

    #[test]
    fn can_find_private_macro_definition() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 8,
                character: 0,
            },
        );

        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");
        let _uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        let GotoDefinitionResult::Final(loc) = loc.expect("Must not be empty.") else {
            panic!();
        };

        assert!(matches!(
            &loc[..],
            [LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 8,
                        character: 0,
                    },
                    end: Position {
                        line: 8,
                        character: 14,
                    },
                }),
                target_uri: _uri,
                target_range: LRange {
                    start: Position {
                        line: 6,
                        character: 0,
                    },
                    end: Position {
                        line: 7,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 6,
                        character: 8,
                    },
                    end: Position {
                        line: 6,
                        character: 22,
                    },
                },
            }]
        ));
    }

    #[test]
    fn can_find_macro_definition_with_docstring() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 22,
                character: 21,
            },
        );

        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");
        let _uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        let GotoDefinitionResult::Final(loc) = loc.expect("Must not be empty.") else {
            panic!();
        };
        assert!(matches!(
            &loc[..],
            [LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 22,
                        character: 13,
                    },
                    end: Position {
                        line: 22,
                        character: 26,
                    },
                }),
                target_uri: _uri,
                target_range: LRange {
                    start: Position {
                        line: 15,
                        character: 0,
                    },
                    end: Position {
                        line: 19,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 18,
                        character: 12,
                    },
                    end: Position {
                        line: 18,
                        character: 25,
                    },
                },
            }]
        ));
    }

    #[test]
    fn can_find_global_macro_definition() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 133,
                character: 14,
            },
        );

        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");
        let _uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        let GotoDefinitionResult::Final(loc) = loc.expect("Must not be empty.") else {
            panic!();
        };
        assert!(matches!(
            &loc[..],
            [LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 133,
                        character: 11,
                    },
                    end: Position {
                        line: 133,
                        character: 25,
                    },
                }),
                target_uri: _uri,
                target_range: LRange {
                    start: Position {
                        line: 136,
                        character: 0,
                    },
                    end: Position {
                        line: 137,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 136,
                        character: 7,
                    },
                    end: Position {
                        line: 136,
                        character: 21,
                    },
                },
            }]
        ));
    }

    #[test]
    fn can_find_macro_definition_inside_subroutine() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 29,
                character: 11,
            },
        );

        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");
        let _uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        let GotoDefinitionResult::Final(loc) = loc.expect("Must not be empty.") else {
            panic!();
        };
        assert!(matches!(
            &loc[..],
            [LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 29,
                        character: 10,
                    },
                    end: Position {
                        line: 29,
                        character: 12,
                    },
                }),
                target_uri: _uri,
                target_range: LRange {
                    start: Position {
                        line: 28,
                        character: 4,
                    },
                    end: Position {
                        line: 29,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 28,
                        character: 12,
                    },
                    end: Position {
                        line: 28,
                        character: 14,
                    },
                },
            }]
        ));
    }

    #[test]
    fn can_find_outside_macro_definition_for_subroutine() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 38,
                character: 10,
            },
        );

        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");
        let uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        let loc = loc.expect("Must not be empty.");

        assert_eq!(
            loc,
            GotoDefinitionResult::PartialMacro(
                uri.to_string(),
                "&local_macro".to_string(),
                LRange {
                    start: Position {
                        line: 38,
                        character: 4,
                    },
                    end: Position {
                        line: 38,
                        character: 16,
                    },
                },
                vec![
                    LocationLink {
                        origin_selection_range: Some(LRange {
                            start: Position {
                                line: 38,
                                character: 4,
                            },
                            end: Position {
                                line: 38,
                                character: 16,
                            },
                        }),
                        target_uri: uri.to_string(),
                        target_range: LRange {
                            start: Position {
                                line: 42,
                                character: 0,
                            },
                            end: Position {
                                line: 43,
                                character: 0,
                            },
                        },
                        target_selection_range: LRange {
                            start: Position {
                                line: 42,
                                character: 6,
                            },
                            end: Position {
                                line: 42,
                                character: 18,
                            },
                        },
                    },
                    LocationLink {
                        origin_selection_range: Some(LRange {
                            start: Position {
                                line: 38,
                                character: 4,
                            },
                            end: Position {
                                line: 38,
                                character: 16,
                            },
                        }),
                        target_uri: uri.to_string(),
                        target_range: LRange {
                            start: Position {
                                line: 38,
                                character: 4,
                            },
                            end: Position {
                                line: 39,
                                character: 0,
                            },
                        },
                        target_selection_range: LRange {
                            start: Position {
                                line: 38,
                                character: 4,
                            },
                            end: Position {
                                line: 38,
                                character: 16,
                            },
                        },
                    },
                ]
            )
        );
    }

    #[test]
    fn can_find_macro_definition_across_subroutine_calls() {
        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");

        let uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        for (loc, _link) in [
            Position {
                line: 58,
                character: 22,
            },
            Position {
                line: 58,
                character: 30,
            },
        ]
        .into_iter()
        .zip([
            [
                LocationLink {
                    origin_selection_range: Some(LRange {
                        start: Position {
                            line: 58,
                            character: 11,
                        },
                        end: Position {
                            line: 58,
                            character: 23,
                        },
                    }),
                    target_uri: uri.to_string(),
                    target_range: LRange {
                        start: Position {
                            line: 65,
                            character: 4,
                        },
                        end: Position {
                            line: 66,
                            character: 0,
                        },
                    },
                    target_selection_range: LRange {
                        start: Position {
                            line: 65,
                            character: 10,
                        },
                        end: Position {
                            line: 65,
                            character: 22,
                        },
                    },
                },
                LocationLink {
                    origin_selection_range: Some(LRange {
                        start: Position {
                            line: 58,
                            character: 11,
                        },
                        end: Position {
                            line: 58,
                            character: 23,
                        },
                    }),
                    target_uri: uri.to_string(),
                    target_range: LRange {
                        start: Position {
                            line: 72,
                            character: 4,
                        },
                        end: Position {
                            line: 73,
                            character: 0,
                        },
                    },
                    target_selection_range: LRange {
                        start: Position {
                            line: 72,
                            character: 10,
                        },
                        end: Position {
                            line: 72,
                            character: 22,
                        },
                    },
                },
            ],
            [
                LocationLink {
                    origin_selection_range: Some(LRange {
                        start: Position {
                            line: 58,
                            character: 26,
                        },
                        end: Position {
                            line: 58,
                            character: 38,
                        },
                    }),
                    target_uri: uri.to_string(),
                    target_range: LRange {
                        start: Position {
                            line: 61,
                            character: 0,
                        },
                        end: Position {
                            line: 62,
                            character: 0,
                        },
                    },
                    target_selection_range: LRange {
                        start: Position {
                            line: 61,
                            character: 6,
                        },
                        end: Position {
                            line: 61,
                            character: 18,
                        },
                    },
                },
                LocationLink {
                    origin_selection_range: Some(LRange {
                        start: Position {
                            line: 58,
                            character: 26,
                        },
                        end: Position {
                            line: 58,
                            character: 38,
                        },
                    }),
                    target_uri: uri.to_string(),
                    target_range: LRange {
                        start: Position {
                            line: 73,
                            character: 4,
                        },
                        end: Position {
                            line: 74,
                            character: 0,
                        },
                    },
                    target_selection_range: LRange {
                        start: Position {
                            line: 73,
                            character: 10,
                        },
                        end: Position {
                            line: 73,
                            character: 22,
                        },
                    },
                },
            ],
        ]) {
            let def = find_def("tests/samples/a/a.cmm", loc);
            assert!(matches!(def, _link));
        }
    }

    #[test]
    fn can_identify_implicit_macro_definitions() {
        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");

        let uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        for (loc, link) in [
            Position {
                line: 84,
                character: 11,
            },
            Position {
                line: 91,
                character: 12,
            },
            Position {
                line: 100,
                character: 11,
            },
            Position {
                line: 107,
                character: 11,
            },
            Position {
                line: 115,
                character: 11,
            },
            Position {
                line: 170,
                character: 7,
            },
        ]
        .into_iter()
        .zip([
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 84,
                        character: 11,
                    },
                    end: Position {
                        line: 84,
                        character: 13,
                    },
                }),
                target_uri: uri.to_string(),
                target_range: LRange {
                    start: Position {
                        line: 82,
                        character: 4,
                    },
                    end: Position {
                        line: 83,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 82,
                        character: 10,
                    },
                    end: Position {
                        line: 82,
                        character: 12,
                    },
                },
            },
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 91,
                        character: 11,
                    },
                    end: Position {
                        line: 91,
                        character: 13,
                    },
                }),
                target_uri: uri.to_string(),
                target_range: LRange {
                    start: Position {
                        line: 82,
                        character: 4,
                    },
                    end: Position {
                        line: 83,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 82,
                        character: 10,
                    },
                    end: Position {
                        line: 82,
                        character: 12,
                    },
                },
            },
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 100,
                        character: 11,
                    },
                    end: Position {
                        line: 100,
                        character: 13,
                    },
                }),
                target_uri: uri.to_string(),
                target_range: LRange {
                    start: Position {
                        line: 98,
                        character: 4,
                    },
                    end: Position {
                        line: 99,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 98,
                        character: 15,
                    },
                    end: Position {
                        line: 98,
                        character: 17,
                    },
                },
            },
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 107,
                        character: 11,
                    },
                    end: Position {
                        line: 107,
                        character: 13,
                    },
                }),
                target_uri: uri.to_string(),
                target_range: LRange {
                    start: Position {
                        line: 82,
                        character: 4,
                    },
                    end: Position {
                        line: 83,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 82,
                        character: 10,
                    },
                    end: Position {
                        line: 82,
                        character: 12,
                    },
                },
            },
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 115,
                        character: 11,
                    },
                    end: Position {
                        line: 115,
                        character: 13,
                    },
                }),
                target_uri: uri.to_string(),
                target_range: LRange {
                    start: Position {
                        line: 82,
                        character: 4,
                    },
                    end: Position {
                        line: 83,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 82,
                        character: 10,
                    },
                    end: Position {
                        line: 82,
                        character: 12,
                    },
                },
            },
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 170,
                        character: 4,
                    },
                    end: Position {
                        line: 170,
                        character: 13,
                    },
                }),
                target_uri: uri.to_string(),
                target_range: LRange {
                    start: Position {
                        line: 164,
                        character: 0,
                    },
                    end: Position {
                        line: 165,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 164,
                        character: 0,
                    },
                    end: Position {
                        line: 164,
                        character: 9,
                    },
                },
            },
        ]) {
            let result = find_def("tests/samples/a/a.cmm", loc);
            assert!(result.is_some_and(|r| match r {
                GotoDefinitionResult::Final(links)
                | GotoDefinitionResult::PartialMacro(_, _, _, links) => links.contains(&link),
            }));
        }
    }

    #[test]
    fn can_break_recursion_loops_for_subroutine_macro_defs() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 127,
                character: 13,
            },
        );
        assert!(loc.is_none());
    }

    #[test]
    fn can_find_subscript_call_target() {
        let loc = find_def(
            "tests/samples/a/a.cmm",
            Position {
                line: 49,
                character: 8,
            },
        );

        let file = env::current_dir()
            .unwrap()
            .join("tests")
            .join("samples")
            .join("a")
            .join("a.cmm");
        let _uri: Url = Url::from_file_path(path::absolute(file).unwrap()).unwrap();

        let GotoDefinitionResult::Final(loc) = loc.expect("Must not be empty.") else {
            panic!();
        };
        assert!(matches!(
            &loc[0],
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 49,
                        character: 0,
                    },
                    end: Position {
                        line: 50,
                        character: 0,
                    },
                }),
                target_uri: _uri,
                target_range: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 1,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 1,
                    },
                },
            }
        ));
    }

    #[test]
    fn can_find_macro_definition_covering_subscript_call() {
        let mut callers: Vec<Uri> = Vec::new();
        for file in ["tests/samples/c.cmm"].into_iter() {
            callers.push(
                Url::from_file_path(path::absolute(file).expect("File must exist."))
                    .unwrap()
                    .to_string(),
            );
        }

        for ((file, parents, origin, backtrace), _link) in [
            (
                "tests/samples/a/a.cmm",
                callers.clone(),
                MacroReferenceOrigin {
                    name: "&local_macro".to_string(),
                    span: LRange {
                        start: Position {
                            line: 17,
                            character: 6,
                        },
                        end: Position {
                            line: 17,
                            character: 18,
                        },
                    },
                    uri: Url::from_file_path(
                        path::absolute("tests/samples/c.cmm").expect("File must exist."),
                    )
                    .unwrap()
                    .to_string(),
                },
                Url::from_file_path(
                    path::absolute("tests/samples/c.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
            ),
            (
                "tests/samples/c.cmm",
                callers.clone(),
                MacroReferenceOrigin {
                    name: "&from_c_cmm".to_string(),
                    span: LRange {
                        start: Position {
                            line: 139,
                            character: 7,
                        },
                        end: Position {
                            line: 139,
                            character: 18,
                        },
                    },
                    uri: Url::from_file_path(
                        path::absolute("tests/samples/a/a.cmm").expect("File must exist."),
                    )
                    .unwrap()
                    .to_string(),
                },
                Url::from_file_path(
                    path::absolute("tests/samples/a/a.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
            ),
        ]
        .into_iter()
        .zip([
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 17,
                        character: 6,
                    },
                    end: Position {
                        line: 17,
                        character: 18,
                    },
                }),
                target_uri: Url::from_file_path(
                    path::absolute("tests/samples/a/a.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
                target_range: LRange {
                    start: Position {
                        line: 42,
                        character: 0,
                    },
                    end: Position {
                        line: 43,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 42,
                        character: 6,
                    },
                    end: Position {
                        line: 42,
                        character: 18,
                    },
                },
            },
            LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 139,
                        character: 7,
                    },
                    end: Position {
                        line: 139,
                        character: 18,
                    },
                }),
                target_uri: Url::from_file_path(
                    path::absolute("tests/samples/a/a.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
                target_range: LRange {
                    start: Position {
                        line: 22,
                        character: 4,
                    },
                    end: Position {
                        line: 23,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 22,
                        character: 10,
                    },
                    end: Position {
                        line: 22,
                        character: 21,
                    },
                },
            },
        ]) {
            let (Some(GotoDefinitionResult::Final(loc)), successors) =
                find_external_macro_def(file, parents, origin, backtrace)
            else {
                panic!();
            };

            assert!(matches!(&loc[..], _link));
            assert_eq!(successors, callers);
        }
    }

    #[test]
    fn can_find_macro_global_macro_definition() {
        let file_idx = create_file_idx();
        let dirs = T32DefaultDirs::default();

        let files = files();
        let mut members: Vec<(TextDoc, Tree, LangExpressions)> = Vec::new();

        for uri in files {
            let (doc, tree, expr) =
                read_doc(uri.clone(), &file_idx, &dirs).expect("Must not fail.");
            members.push((doc, tree, expr));
        }

        let docs = TextDocs::from_workspace(members);

        let globals = docs.get_all_global_macros().expect("Must not fail.");

        let links = find_global_macro_definitions(
            &docs,
            globals,
            MacroReferenceOrigin {
                name: "&global_macro".to_string(),
                span: LRange {
                    start: Position {
                        line: 31,
                        character: 7,
                    },
                    end: Position {
                        line: 31,
                        character: 20,
                    },
                },
                uri: Url::from_file_path(
                    path::absolute("tests/samples/c.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
            },
        );

        let _uri = to_file_uri("tests/samples/a/a.cmm");

        assert!(matches!(
            &links[..],
            [LocationLink {
                origin_selection_range: Some(LRange {
                    start: Position {
                        line: 31,
                        character: 7,
                    },
                    end: Position {
                        line: 31,
                        character: 20,
                    },
                }),
                target_uri: _uri,
                target_range: LRange {
                    start: Position {
                        line: 41,
                        character: 0,
                    },
                    end: Position {
                        line: 42,
                        character: 0,
                    },
                },
                target_selection_range: LRange {
                    start: Position {
                        line: 41,
                        character: 7,
                    },
                    end: Position {
                        line: 41,
                        character: 20,
                    },
                },
            }]
        ));
    }

    #[test]
    fn can_find_references_for_subroutine_call() {
        let refs = find_refs(
            "tests/samples/a/a.cmm",
            Position {
                line: 67,
                character: 10,
            },
        );

        let Some(FindReferencesResult::Final(refs)) = refs else {
            panic!();
        };

        let uri = to_file_uri("tests/samples/a/a.cmm");

        for (loc, expected) in refs.into_iter().zip([
            Location {
                uri: uri.clone(),
                range: LRange {
                    start: Position {
                        line: 54,
                        character: 11,
                    },
                    end: Position {
                        line: 54,
                        character: 15,
                    },
                },
            },
            Location {
                uri: uri.clone(),
                range: LRange {
                    start: Position {
                        line: 67,
                        character: 10,
                    },
                    end: Position {
                        line: 67,
                        character: 14,
                    },
                },
            },
            Location {
                uri: uri.clone(),
                range: LRange {
                    start: Position {
                        line: 75,
                        character: 10,
                    },
                    end: Position {
                        line: 75,
                        character: 14,
                    },
                },
            },
        ]) {
            assert_eq!(loc, expected);
        }
    }

    #[test]
    fn can_find_references_for_subroutine_defintion() {
        let uri = to_file_uri("tests/samples/a/a.cmm");

        for (loc, expected) in [
            Position {
                line: 113,
                character: 11,
            },
            Position {
                line: 80,
                character: 0,
            },
        ]
        .into_iter()
        .zip([
            [
                Location {
                    uri: uri.clone(),
                    range: LRange {
                        start: Position {
                            line: 113,
                            character: 11,
                        },
                        end: Position {
                            line: 113,
                            character: 15,
                        },
                    },
                },
                Location {
                    uri: uri.clone(),
                    range: LRange {
                        start: Position {
                            line: 110,
                            character: 10,
                        },
                        end: Position {
                            line: 110,
                            character: 14,
                        },
                    },
                },
            ],
            [
                Location {
                    uri: uri.clone(),
                    range: LRange {
                        start: Position {
                            line: 80,
                            character: 0,
                        },
                        end: Position {
                            line: 80,
                            character: 4,
                        },
                    },
                },
                Location {
                    uri: uri.clone(),
                    range: LRange {
                        start: Position {
                            line: 118,
                            character: 6,
                        },
                        end: Position {
                            line: 118,
                            character: 10,
                        },
                    },
                },
            ],
        ]) {
            let refs = find_refs("tests/samples/a/a.cmm", loc);

            let Some(FindReferencesResult::Final(refs)) = refs else {
                panic!();
            };

            for (loc, expected) in refs.into_iter().zip(expected) {
                assert_eq!(loc, expected);
            }
        }
    }

    #[test]
    fn can_find_references_for_label() {
        let refs = find_refs(
            "tests/samples/a/a.cmm",
            Position {
                line: 157,
                character: 3,
            },
        );

        let Some(FindReferencesResult::Final(refs)) = refs else {
            panic!();
        };

        let uri = to_file_uri("tests/samples/a/a.cmm");
        for (loc, expected) in refs.into_iter().zip([
            Location {
                uri: uri.clone(),
                range: LRange {
                    start: Position {
                        line: 157,
                        character: 0,
                    },
                    end: Position {
                        line: 157,
                        character: 6,
                    },
                },
            },
            Location {
                uri: uri.clone(),
                range: LRange {
                    start: Position {
                        line: 160,
                        character: 5,
                    },
                    end: Position {
                        line: 160,
                        character: 11,
                    },
                },
            },
        ]) {
            assert_eq!(loc, expected);
        }
    }

    #[test]
    fn can_find_infile_references_for_macro_definition() {
        let file_idx = create_file_idx();
        let dirs = T32DefaultDirs::default();

        let uri =
            Url::from_file_path(path::absolute("tests/samples/a/a.cmm").expect("File must exist."))
                .unwrap();
        let (doc, tree, t32) = read_doc(uri, &file_idx, &dirs).unwrap();

        for ((name, range, scope), (refs, scripts)) in [
            (
                "&private_macro",
                Range {
                    start: 134usize,
                    end: 148usize,
                },
                MacroScope::Private,
            ),
            (
                "&local_macro",
                Range {
                    start: 509usize,
                    end: 521usize,
                },
                MacroScope::Local,
            ),
            (
                "&implicit",
                Range {
                    start: 1586usize,
                    end: 1595usize,
                },
                MacroScope::Local,
            ),
            (
                "&x",
                Range {
                    start: 919usize,
                    end: 921usize,
                },
                MacroScope::Local,
            ),
            (
                "&param",
                Range {
                    start: 1715usize,
                    end: 1721usize,
                },
                MacroScope::Local,
            ),
        ]
        .into_iter()
        .zip(
            [
                (
                    vec![
                        LRange {
                            start: Position {
                                line: 6,
                                character: 8,
                            },
                            end: Position {
                                line: 6,
                                character: 22,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 8,
                                character: 0,
                            },
                            end: Position {
                                line: 8,
                                character: 14,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 11,
                                character: 3,
                            },
                            end: Position {
                                line: 11,
                                character: 17,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 164,
                                character: 10,
                            },
                            end: Position {
                                line: 164,
                                character: 24,
                            },
                        },
                    ],
                    Vec::<Uri>::new(),
                ),
                (
                    vec![
                        LRange {
                            start: Position {
                                line: 38,
                                character: 4,
                            },
                            end: Position {
                                line: 38,
                                character: 16,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 42,
                                character: 6,
                            },
                            end: Position {
                                line: 42,
                                character: 18,
                            },
                        },
                    ],
                    vec![
                        to_file_uri("tests/samples/b/b.cmm"),
                        to_file_uri("tests/samples/c.cmm"),
                    ],
                ),
                (
                    vec![
                        LRange {
                            start: Position {
                                line: 164,
                                character: 0,
                            },
                            end: Position {
                                line: 164,
                                character: 9,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 170,
                                character: 4,
                            },
                            end: Position {
                                line: 170,
                                character: 13,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 170,
                                character: 14,
                            },
                            end: Position {
                                line: 170,
                                character: 23,
                            },
                        },
                    ],
                    Vec::new(),
                ),
                (
                    vec![
                        LRange {
                            start: Position {
                                line: 82,
                                character: 10,
                            },
                            end: Position {
                                line: 82,
                                character: 12,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 84,
                                character: 11,
                            },
                            end: Position {
                                line: 84,
                                character: 13,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 91,
                                character: 11,
                            },
                            end: Position {
                                line: 91,
                                character: 13,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 98,
                                character: 15,
                            },
                            end: Position {
                                line: 98,
                                character: 17,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 100,
                                character: 11,
                            },
                            end: Position {
                                line: 100,
                                character: 13,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 107,
                                character: 11,
                            },
                            end: Position {
                                line: 107,
                                character: 13,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 109,
                                character: 10,
                            },
                            end: Position {
                                line: 109,
                                character: 12,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 115,
                                character: 11,
                            },
                            end: Position {
                                line: 115,
                                character: 13,
                            },
                        },
                    ],
                    Vec::new(),
                ),
                (
                    vec![
                        LRange {
                            start: Position {
                                line: 176,
                                character: 12,
                            },
                            end: Position {
                                line: 176,
                                character: 18,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 177,
                                character: 15,
                            },
                            end: Position {
                                line: 177,
                                character: 21,
                            },
                        },
                        LRange {
                            start: Position {
                                line: 179,
                                character: 11,
                            },
                            end: Position {
                                line: 179,
                                character: 17,
                            },
                        },
                    ],
                    Vec::new(),
                ),
            ]
            .into_iter(),
        ) {
            let result = find_macro_references_from_origin(
                TextDocData {
                    doc: doc.clone(),
                    tree: tree.clone(),
                },
                FindMacroRefsLangContext::from(t32.clone()),
                name.to_string(),
                vec![MacroDefinitionLocation::from_span(
                    Some(&scope),
                    BRange::from(range),
                )],
            );

            assert_eq!(result.references.len(), refs.len());
            for r#ref in result.references {
                assert!(refs.contains(&r#ref));
            }

            assert_eq!(result.subscripts.len(), scripts.len());
            for file in result.subscripts {
                assert!(scripts.contains(&file));
            }
        }
    }

    #[test]
    fn can_find_references_for_macros_on_stack() {
        let file_idx = create_file_idx();
        let dirs = T32DefaultDirs::default();

        let uri =
            Url::from_file_path(path::absolute("tests/samples/a/a.cmm").expect("File must exist."))
                .unwrap();
        let (doc, tree, t32) = read_doc(uri, &file_idx, &dirs).unwrap();

        let result = find_infile_macro_references(
            TextDocData { doc, tree },
            FindMacroRefsLangContext::from(t32),
            "&from_c_cmm".to_string(),
        );

        assert!(result.references.contains(&LRange {
            start: Position {
                line: 139,
                character: 7
            },
            end: Position {
                line: 139,
                character: 18
            },
        }));

        for target in [
            to_file_uri("tests/samples/b/b.cmm"),
            to_file_uri("tests/samples/c.cmm"),
        ] {
            assert!(result.subscripts.contains(&target));
        }
    }

    #[test]
    fn can_find_external_definitions_for_macro_ref() {
        let file_idx = create_file_idx();
        let dirs = T32DefaultDirs::default();

        let origin = MacroReferenceOrigin {
            name: "&from_c_cmm".to_string(),
            span: LRange {
                start: Position {
                    line: 162,
                    character: 7,
                },
                end: Position {
                    line: 162,
                    character: 18,
                },
            },
            uri: Url::from_file_path(
                path::absolute("tests/samples/a/a.cmm").expect("File must exist."),
            )
            .unwrap()
            .to_string(),
        };

        for ((uri, origin, callers, backtrace), result) in [
            (
                Url::from_file_path(
                    path::absolute("tests/samples/a/d/d.cmm").expect("File must exist."),
                )
                .unwrap(),
                origin.clone(),
                vec![
                    Url::from_file_path(
                        path::absolute("tests/samples/c.cmm").expect("File must exist."),
                    )
                    .unwrap()
                    .to_string(),
                ],
                Url::from_file_path(
                    path::absolute("tests/samples/a/a.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
            ),
            (
                Url::from_file_path(
                    path::absolute("tests/samples/c.cmm").expect("File must exist."),
                )
                .unwrap(),
                origin.clone(),
                vec![
                    Url::from_file_path(
                        path::absolute("tests/samples/c.cmm").expect("File must exist."),
                    )
                    .unwrap()
                    .to_string(),
                ],
                Url::from_file_path(
                    path::absolute("tests/samples/a/d/d.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
            ),
        ]
        .into_iter()
        .zip([
            FindDefintionsForMacroRefResult::Partial(
                Vec::new(),
                Url::from_file_path(
                    path::absolute("tests/samples/a/d/d.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
                vec![
                    Url::from_file_path(
                        path::absolute("tests/samples/c.cmm").expect("File must exist."),
                    )
                    .unwrap()
                    .to_string(),
                ],
            ),
            FindDefintionsForMacroRefResult::Final(
                vec![MacroDefinitionLocation::Local(
                    Range::<usize> {
                        start: 497,
                        end: 508,
                    }
                    .into(),
                )],
                Url::from_file_path(
                    path::absolute("tests/samples/c.cmm").expect("File must exist."),
                )
                .unwrap()
                .to_string(),
            ),
        ]) {
            let (doc, tree, t32) = read_doc(uri, &file_idx, &dirs).unwrap();

            let defs = find_external_definitions_for_macro_ref(
                TextDocData { doc, tree },
                t32.into(),
                callers,
                origin,
                backtrace,
            );
            assert_eq!(defs, result);
        }
    }

    #[test]
    fn can_return_subscript_call_file_target_for_find_reference_req() {
        let file = "tests/samples/a/a.cmm";
        let refs = find_refs(
            &file,
            Position {
                line: 49,
                character: 6,
            },
        );

        assert!(refs.is_some_and(|r| r
            == FindReferencesResult::Partial(FindReferencesPartialResult::FileTarget {
                origin_uri: to_file_uri(file),
                target: "../b/b.cmm".to_string()
            })));
    }

    #[test]
    fn can_return_command_identifier_for_find_references_req() {
        let command = find_refs(
            "tests/samples/b/b.cmm",
            Position {
                line: 4,
                character: 2,
            },
        );
        let arguments = find_refs(
            "tests/samples/b/b.cmm",
            Position {
                line: 4,
                character: 17,
            },
        );

        assert_eq!(command, arguments);
        assert!(command.is_some_and(|c| c
            == FindReferencesResult::Partial(FindReferencesPartialResult::Command(
                "SILENT.PRINT".to_string()
            ))));
    }

    #[test]
    fn can_flatten_overlapping_tokens() {
        let tokens = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 11,
                    },
                    end: Position {
                        line: 0,
                        character: 12,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
        ];

        let flattened = tokens.clone();

        let tokens = flatten_semantic_tokens(tokens);
        debug_assert_eq!(tokens, flattened);

        let tokens = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 2,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 8,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
        ];

        let flattened = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 2,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 2,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 8,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
        ];

        let tokens = flatten_semantic_tokens(tokens);
        debug_assert_eq!(tokens, flattened);

        let tokens = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 2,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 6,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
        ];

        let flattened = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 2,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 2,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 4,
                    },
                    end: Position {
                        line: 0,
                        character: 6,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 6,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 8,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
        ];

        let tokens = flatten_semantic_tokens(tokens);
        debug_assert_eq!(tokens, flattened);

        let tokens = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 2,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 4,
                    },
                    end: Position {
                        line: 0,
                        character: 6,
                    },
                },
                r#type: 2,
                modifier: 2,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 10,
                    },
                    end: Position {
                        line: 0,
                        character: 12,
                    },
                },
                r#type: 3,
                modifier: 3,
            },
        ];

        let flattened = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 2,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 2,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 4,
                    },
                    end: Position {
                        line: 0,
                        character: 6,
                    },
                },
                r#type: 2,
                modifier: 2,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 6,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 8,
                    },
                    end: Position {
                        line: 0,
                        character: 10,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 10,
                    },
                    end: Position {
                        line: 0,
                        character: 12,
                    },
                },
                r#type: 3,
                modifier: 3,
            },
        ];

        let tokens = flatten_semantic_tokens(tokens);
        debug_assert_eq!(tokens, flattened);
    }

    #[test]
    fn can_split_multiline_tokens() {
        let textdoc = TextDoc::from(TextDocumentItem {
            uri: "file:///test.cmm".to_string(),
            language_id: LANGUAGE_ID.to_string(),
            version: 0,
            text: "Line one\nLine two\nLine three\nLine four\n".to_string(),
        });

        let tokens = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 5,
                    },
                    end: Position {
                        line: 2,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
        ];

        let expected = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 5,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 1,
                        character: 0,
                    },
                    end: Position {
                        line: 1,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 2,
                        character: 0,
                    },
                    end: Position {
                        line: 2,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
        ];

        let split_tokens = split_multiline_semantic_tokens(&textdoc, tokens);
        debug_assert_eq!(split_tokens, expected);

        let tokens = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 5,
                    },
                    end: Position {
                        line: 1,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 1,
                        character: 5,
                    },
                    end: Position {
                        line: 1,
                        character: 8,
                    },
                },
                r#type: 2,
                modifier: 2,
            },
        ];

        let expected = vec![
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 0,
                    },
                    end: Position {
                        line: 0,
                        character: 4,
                    },
                },
                r#type: 0,
                modifier: 0,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 0,
                        character: 5,
                    },
                    end: Position {
                        line: 0,
                        character: 8,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 1,
                        character: 0,
                    },
                    end: Position {
                        line: 1,
                        character: 4,
                    },
                },
                r#type: 1,
                modifier: 1,
            },
            SemanticToken {
                span: LRange {
                    start: Position {
                        line: 1,
                        character: 5,
                    },
                    end: Position {
                        line: 1,
                        character: 8,
                    },
                },
                r#type: 2,
                modifier: 2,
            },
        ];

        let split_tokens = split_multiline_semantic_tokens(&textdoc, tokens);
        debug_assert_eq!(split_tokens, expected);
    }
}
