use crate::{BufferSnapshot, Point, ToPoint, ToTreeSitterPoint};
use fuzzy_nucleo::{Case, LengthPenalty, StringMatch, StringMatchCandidate};
use gpui::{BackgroundExecutor, HighlightStyle, SharedString};
use std::ops::Range;

/// An outline of all the symbols contained in a buffer.
#[derive(Debug)]
pub struct Outline<T> {
    pub items: Vec<OutlineItem<T>>,
    /// Candidates contain the full path of each item, used for matching.
    candidates: Vec<StringMatchCandidate>,
    /// leaf_offsets stores the byte offset within that full path where the
    /// item's own text starts. Anything before this offset is ancestor
    /// path text used purely as match context.
    leaf_offsets: Vec<usize>,
}

#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
pub struct OutlineItem<T> {
    pub depth: usize,
    pub range: Range<T>,
    pub selection_range: Range<T>,
    pub source_range_for_text: Range<T>,
    pub text: SharedString,
    pub highlight_ranges: Vec<(Range<usize>, HighlightStyle)>,
    pub name_ranges: Vec<Range<usize>>,
    pub body_range: Option<Range<T>>,
    pub annotation_range: Option<Range<T>>,
}

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct SymbolPath(pub SharedString);

/// Result of [`Outline::search`]. Real fuzzy matches are `Match`; `Ancestor`
/// rows are synthetic entries pointing at parent items, included so callers can
/// show the full path of each match (Even when the ancestor has been filtered
/// out due to not matching) but treat those synthetic ancestors differently
/// from an entry that actually matched (e.g. they are not eligible for
/// auto-selection).
#[derive(Clone, Debug)]
pub enum OutlineSearchEntry {
    Match(StringMatch),
    Ancestor { candidate_id: usize },
}

impl OutlineSearchEntry {
    pub fn candidate_id(&self) -> usize {
        match self {
            Self::Match(m) => m.candidate_id,
            Self::Ancestor { candidate_id } => *candidate_id,
        }
    }

    pub fn as_match(&self) -> Option<&StringMatch> {
        match self {
            Self::Match(m) => Some(m),
            Self::Ancestor { .. } => None,
        }
    }

    pub fn into_match(self) -> Option<StringMatch> {
        match self {
            Self::Match(m) => Some(m),
            Self::Ancestor { .. } => None,
        }
    }
}

impl<T: ToPoint> OutlineItem<T> {
    /// Converts to an equivalent outline item, but with parameterized over Points.
    pub fn to_point(&self, buffer: &BufferSnapshot) -> OutlineItem<Point> {
        OutlineItem {
            depth: self.depth,
            range: self.range.start.to_point(buffer)..self.range.end.to_point(buffer),
            selection_range: self.selection_range.start.to_point(buffer)
                ..self.selection_range.end.to_point(buffer),
            source_range_for_text: self.source_range_for_text.start.to_point(buffer)
                ..self.source_range_for_text.end.to_point(buffer),
            text: self.text.clone(),
            highlight_ranges: self.highlight_ranges.clone(),
            name_ranges: self.name_ranges.clone(),
            body_range: self
                .body_range
                .as_ref()
                .map(|r| r.start.to_point(buffer)..r.end.to_point(buffer)),
            annotation_range: self
                .annotation_range
                .as_ref()
                .map(|r| r.start.to_point(buffer)..r.end.to_point(buffer)),
        }
    }

    pub fn body_range(&self, buffer: &BufferSnapshot) -> Option<Range<Point>> {
        if let Some(range) = self.body_range.as_ref() {
            return Some(range.start.to_point(buffer)..range.end.to_point(buffer));
        }

        let range = self.range.start.to_point(buffer)..self.range.end.to_point(buffer);
        let start_indent = buffer.indent_size_for_line(range.start.row);
        let node = buffer.syntax_ancestor(range.clone())?;

        let mut cursor = node.walk();
        loop {
            let node = cursor.node();
            if node.start_position() >= range.start.to_ts_point()
                && node.end_position() <= range.end.to_ts_point()
            {
                break;
            }
            // If we can't descend further, the current node is the most specific
            // ancestor that contains `range.start`. Bail out rather than spinning
            // forever re-checking the same node.
            if cursor
                .goto_first_child_for_point(range.start.to_ts_point())
                .is_none()
            {
                return None;
            }
        }

        if !cursor.goto_last_child() {
            return None;
        }
        let body_node = loop {
            let node = cursor.node();
            if node.child_count() > 0 {
                break node;
            }
            if !cursor.goto_previous_sibling() {
                return None;
            }
        };

        let mut start_row = body_node.start_position().row as u32;
        let mut end_row = body_node.end_position().row as u32;

        while start_row < end_row && buffer.indent_size_for_line(start_row) == start_indent {
            start_row += 1;
        }
        while start_row < end_row && buffer.indent_size_for_line(end_row - 1) == start_indent {
            end_row -= 1;
        }
        if start_row < end_row {
            return Some(Point::new(start_row, 0)..Point::new(end_row, 0));
        }
        None
    }
}

impl<T> Outline<T> {
    pub fn new(items: Vec<OutlineItem<T>>) -> Self {
        let mut candidates = Vec::with_capacity(items.len());
        let mut leaf_offsets = Vec::with_capacity(items.len());
        let mut path_text = String::new();
        let mut path_stack = Vec::new();

        for (id, item) in items.iter().enumerate() {
            if item.depth < path_stack.len() {
                path_stack.truncate(item.depth);
                path_text.truncate(path_stack.last().copied().unwrap_or(0));
            }
            if !path_text.is_empty() {
                path_text.push(' ');
            }
            leaf_offsets.push(path_text.len());
            path_text.push_str(&item.text);
            path_stack.push(path_text.len());
            candidates.push(StringMatchCandidate::new(id, &path_text));
        }

        Self {
            items,
            candidates,
            leaf_offsets,
        }
    }

    /// Find the most similar symbol to the provided query using normalized Levenshtein distance.
    pub fn find_most_similar(&self, query: &str) -> Option<(SymbolPath, &OutlineItem<T>)> {
        const SIMILARITY_THRESHOLD: f64 = 0.6;

        let (position, similarity) = self
            .candidates
            .iter()
            .enumerate()
            .map(|(index, candidate)| {
                let similarity = strsim::normalized_levenshtein(&candidate.string, query);
                (index, similarity)
            })
            .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap())?;

        if similarity >= SIMILARITY_THRESHOLD {
            self.candidates
                .get(position)
                .map(|candidate| SymbolPath(candidate.string.clone()))
                .zip(self.items.get(position))
        } else {
            None
        }
    }

    /// Find all outline symbols that match with the nucleo fuzzy matcher, ordered by tree position.
    /// Each real match is preceded by [`OutlineSearchEntry::Ancestor`] rows carrying parent
    /// `candidate_id`s, so callers can render tree context above the match.
    pub async fn search(
        &self,
        query: &str,
        executor: BackgroundExecutor,
    ) -> Vec<OutlineSearchEntry> {
        let query = query.trim_start();
        if query.is_empty() {
            return Vec::new();
        }
        let mut matches = fuzzy_nucleo::match_strings_async(
            &self.candidates,
            query,
            Case::Smart,
            LengthPenalty::On,
            100,
            &Default::default(),
            executor,
        )
        .await;
        matches.sort_unstable_by_key(|m| m.candidate_id);

        // Single-atom queries (no whitespace) require *all* matched chars to
        // land in the leaf — typing "drop" should only surface leaves that
        // actually contain "drop", not items whose ancestor path happens to.
        // We can rely on that behavior because nucleo prefers matches at the
        // end of the haystack, so the leafiest part of the candidate.
        //
        // Multi-atom queries (whitespace-separated) use the ancestor path
        // for scoping. Rows whose entire match landed in an ancestor are
        // kept as context, with empty positions and zero score, so
        // descendants of a matched container surface alongside it. The
        // picker's score-based auto-select skips them so they never steal
        // focus from a row with real highlights.
        let single_atom = !query.contains(char::is_whitespace);
        matches.retain_mut(|string_match| {
            let leaf_offset = self.leaf_offsets[string_match.candidate_id];
            let total = string_match.positions.len();
            string_match
                .positions
                .retain(|position| *position >= leaf_offset);
            let kept = string_match.positions.len();
            if single_atom && kept != total {
                return false;
            }
            if kept == 0 {
                string_match.score = 0.0;
            }
            for position in &mut string_match.positions {
                *position -= leaf_offset;
            }
            string_match
                .string
                .clone_from(&self.items[string_match.candidate_id].text);
            true
        });

        expand_tree(|i| self.items[i].depth, matches)
    }
}

/// Interleaves synthetic [`OutlineSearchEntry::Ancestor`] rows before each match so callers
/// can render the parent chain as tree context above the match.
///
/// `matches` must be sorted ascending by `candidate_id` (which is what
/// [`Outline::search`] produces), this is so that we preserve the tree
/// structure of the outline. `depth_at` returns the tree depth for the item at
/// a given candidate index. Ancestors that already appear earlier in the output
/// either as their own match or as an ancestor of an earlier match, are not
/// duplicated.
fn expand_tree(
    depth_at: impl Fn(usize) -> usize,
    matches: Vec<StringMatch>,
) -> Vec<OutlineSearchEntry> {
    debug_assert!(matches.is_sorted_by_key(|m| m.candidate_id));
    let mut out = Vec::with_capacity(matches.len());
    let mut prev_item_ix = 0;
    for string_match in matches {
        let insertion_ix = out.len();
        let mut cur_depth = depth_at(string_match.candidate_id);
        for ix in (prev_item_ix..string_match.candidate_id).rev() {
            if cur_depth == 0 {
                break;
            }
            if depth_at(ix) == cur_depth - 1 {
                out.insert(
                    insertion_ix,
                    OutlineSearchEntry::Ancestor { candidate_id: ix },
                );
                cur_depth -= 1;
            }
        }
        prev_item_ix = string_match.candidate_id + 1;
        out.push(OutlineSearchEntry::Match(string_match));
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{Buffer, rust_lang};
    use gpui::{AppContext as _, TestAppContext};

    #[gpui::test]
    fn test_body_range_hangs_when_outline_range_is_inside_leaf_node(cx: &mut TestAppContext) {
        let text = "fn main() { let completion = 1; }";
        let buffer = cx.new(|cx| Buffer::local(text, cx).with_language(rust_lang(), cx));
        let snapshot = buffer.update(cx, |buffer, _| buffer.snapshot());
        let identifier_start = text.find("completion").unwrap() + 1;
        let identifier_end = identifier_start + 1;
        let range =
            snapshot.offset_to_point(identifier_start)..snapshot.offset_to_point(identifier_end);

        let item = OutlineItem {
            depth: 0,
            range: range.clone(),
            selection_range: range.clone(),
            source_range_for_text: range,
            text: "completion".into(),
            highlight_ranges: Vec::new(),
            name_ranges: Vec::new(),
            body_range: None,
            annotation_range: None,
        };

        assert_eq!(item.body_range(&snapshot), None);
    }

    #[gpui::test]
    async fn test_entries_with_no_names(cx: &mut TestAppContext) {
        let outline = Outline::new(vec![
            OutlineItem {
                depth: 0,
                range: Point::new(0, 0)..Point::new(5, 0),
                selection_range: Point::new(0, 6)..Point::new(0, 9),
                source_range_for_text: Point::new(0, 0)..Point::new(0, 9),
                text: "class Foo".into(),
                highlight_ranges: vec![],
                name_ranges: vec![6..9],
                body_range: None,
                annotation_range: None,
            },
            OutlineItem {
                depth: 0,
                range: Point::new(2, 0)..Point::new(2, 7),
                selection_range: Point::new(2, 0)..Point::new(2, 7),
                source_range_for_text: Point::new(0, 0)..Point::new(0, 7),
                text: "private".into(),
                highlight_ranges: vec![],
                name_ranges: vec![],
                body_range: None,
                annotation_range: None,
            },
        ]);
        assert!(
            outline.search("", cx.executor()).await.is_empty(),
            "empty queries return no matches; the picker handles 'show all' itself",
        );
        assert_eq!(
            outline
                .search("foo", cx.executor())
                .await
                .into_iter()
                .filter_map(OutlineSearchEntry::into_match)
                .map(|m| m.string)
                .collect::<Vec<SharedString>>(),
            vec![SharedString::from("class Foo")],
            "'private' (empty name_ranges) is correctly excluded; only the matching 'class Foo' is returned",
        );
    }

    #[test]
    fn test_find_most_similar_with_low_similarity() {
        let outline = Outline::new(vec![
            OutlineItem {
                depth: 0,
                range: Point::new(0, 0)..Point::new(5, 0),
                selection_range: Point::new(0, 3)..Point::new(0, 10),
                source_range_for_text: Point::new(0, 0)..Point::new(0, 10),
                text: "fn process".into(),
                highlight_ranges: vec![],
                name_ranges: vec![3..10],
                body_range: None,
                annotation_range: None,
            },
            OutlineItem {
                depth: 0,
                range: Point::new(7, 0)..Point::new(12, 0),
                selection_range: Point::new(0, 7)..Point::new(0, 20),
                source_range_for_text: Point::new(0, 0)..Point::new(0, 20),
                text: "struct DataProcessor".into(),
                highlight_ranges: vec![],
                name_ranges: vec![7..20],
                body_range: None,
                annotation_range: None,
            },
        ]);
        assert_eq!(
            outline.find_most_similar("pub fn process"),
            Some((SymbolPath("fn process".into()), &outline.items[0]))
        );
        assert_eq!(
            outline.find_most_similar("async fn process"),
            Some((SymbolPath("fn process".into()), &outline.items[0])),
        );
        assert_eq!(
            outline.find_most_similar("struct Processor"),
            Some((SymbolPath("struct DataProcessor".into()), &outline.items[1]))
        );
        assert_eq!(outline.find_most_similar("struct User"), None);
        assert_eq!(outline.find_most_similar("struct"), None);
    }
}