mago-analyzer 1.18.1

use std::borrow::Cow;
use std::collections::BTreeMap;
use std::rc::Rc;
use std::sync::Arc;
use std::sync::LazyLock;

use foldhash::HashSet;
use indexmap::IndexMap;
use regex::Regex;

use mago_algebra::assertion_set::AssertionSet;
use mago_atom::Atom;
use mago_atom::AtomMap;
use mago_atom::AtomSet;
use mago_atom::atom;
use mago_atom::concat_atom;
use mago_codex::assertion::Assertion;
use mago_codex::metadata::CodebaseMetadata;
use mago_codex::ttype::add_optional_union_type;
use mago_codex::ttype::add_union_type;
use mago_codex::ttype::atomic::TAtomic;
use mago_codex::ttype::atomic::array::TArray;
use mago_codex::ttype::atomic::array::key::ArrayKey;
use mago_codex::ttype::atomic::array::keyed::TKeyedArray;
use mago_codex::ttype::atomic::array::list::TList;
use mago_codex::ttype::atomic::generic::TGenericParameter;
use mago_codex::ttype::atomic::object::TObject;
use mago_codex::ttype::atomic::scalar::TScalar;
use mago_codex::ttype::combiner::CombinerOptions;
use mago_codex::ttype::expander;
use mago_codex::ttype::expander::StaticClassType;
use mago_codex::ttype::expander::TypeExpansionOptions;
use mago_codex::ttype::get_arraykey;
use mago_codex::ttype::get_iterable_value_parameter;
use mago_codex::ttype::get_mixed;
use mago_codex::ttype::get_mixed_maybe_from_loop;
use mago_codex::ttype::get_never;
use mago_codex::ttype::get_null;
use mago_codex::ttype::get_string;
use mago_codex::ttype::intersect_union_types;
use mago_codex::ttype::union::TUnion;
use mago_codex::ttype::wrap_atomic;
use mago_reporting::Annotation;
use mago_reporting::Issue;
use mago_span::Span;

use crate::code::IssueCode;
use crate::context::Context;
use crate::context::block::BlockContext;
use crate::context::scope::var_has_root;

pub mod assertion_reconciler;
pub mod negated_assertion_reconciler;
pub mod simple_assertion_reconciler;
pub mod simple_negated_assertion_reconciler;

mod macros;

pub fn reconcile_keyed_types<'ctx>(
    context: &mut Context<'ctx, '_>,
    new_types: &IndexMap<Atom, AssertionSet>,
    mut active_new_types: IndexMap<Atom, HashSet<usize>>,
    block_context: &mut BlockContext<'ctx>,
    changed_var_ids: &mut AtomSet,
    referenced_var_ids: &AtomSet,
    span: &Span,
    can_report_issues: bool,
    negated: bool,
) {
    if new_types.is_empty() {
        return;
    }

    let mut reference_graph: AtomMap<AtomSet> = AtomMap::default();
    if !block_context.references_in_scope.is_empty() {
        // PHP behaves oddly when passing an array containing references: https://bugs.php.net/bug.php?id=20993
        // To work around the issue, if there are any references, we have to recreate the array and fix the
        // references so they're properly scoped and won't affect the caller. Starting with a new array is
        // required for some unclear reason, just cloning elements of the existing array doesn't work properly.
        let old_locals = std::mem::take(&mut block_context.locals);

        let mut cloned_references: AtomSet = AtomSet::default();
        for (reference, referenced) in &block_context.references_in_scope {
            if cloned_references.contains(referenced) {
                block_context.locals.insert(*referenced, old_locals[referenced].clone());
                cloned_references.insert(*reference);
            }
        }

        block_context.locals.extend(old_locals);
        for (reference, referenced) in &block_context.references_in_scope {
            reference_graph.entry(*reference).or_default().insert(*referenced);

            let referenced_graph = reference_graph.get(referenced).cloned().unwrap_or_default();
            for existing_referenced in referenced_graph {
                reference_graph.entry(existing_referenced).or_default().insert(*reference);
                reference_graph.entry(*reference).or_default().insert(existing_referenced);
            }

            reference_graph.entry(*referenced).or_default().insert(*reference);
        }
    }

    let inside_loop = block_context.flags.inside_loop();
    let old_new_types = new_types.clone();
    let mut new_types = new_types.clone();

    add_nested_assertions(&mut new_types, &mut active_new_types, block_context);

    for (key, new_type_parts) in &new_types {
        let key_str = key.as_str();
        if key_str.contains("::") && !key_str.contains('$') && !key_str.contains('[') {
            continue;
        }

        let mut has_negation = false;
        let mut has_isset = false;
        let mut has_inverted_isset = false;
        let mut has_inverted_key_exists = false;
        let mut has_truthy_or_falsy_or_empty = false;
        let mut has_count_check = false;
        let mut has_empty = false;
        let is_real = old_new_types.get(key).is_some_and(|v| v.eq(new_type_parts));
        let mut is_equality = is_real;

        for new_type_part_parts in new_type_parts {
            for assertion in new_type_part_parts {
                if assertion.is_negation() {
                    has_negation = true;
                }

                has_isset = has_isset || assertion.has_isset();
                has_truthy_or_falsy_or_empty = has_truthy_or_falsy_or_empty
                    || matches!(
                        assertion,
                        Assertion::Truthy | Assertion::Falsy | Assertion::Empty | Assertion::NonEmpty
                    );
                is_equality = is_equality && matches!(assertion, Assertion::IsIdentical(_));
                has_empty = has_empty || matches!(assertion, Assertion::Empty);
                has_inverted_isset = has_inverted_isset || matches!(assertion, Assertion::IsNotIsset);
                has_inverted_key_exists =
                    has_inverted_key_exists || matches!(assertion, Assertion::ArrayKeyDoesNotExist);
                has_count_check = has_count_check || matches!(assertion, Assertion::NonEmptyCountable(_));
            }
        }

        let did_type_exist = block_context.locals.contains_key(key);
        let mut has_object_array_access = false;

        let mut result_type = block_context.locals.get(key).map(|t| t.as_ref().clone()).or_else(|| {
            get_value_for_key(
                context,
                *key,
                block_context,
                &new_types,
                has_isset,
                has_inverted_isset,
                has_inverted_key_exists,
                false,
                inside_loop,
                &mut has_object_array_access,
            )
        });

        let before_adjustment = result_type.clone();
        for (i, new_type_part_parts) in new_type_parts.iter().enumerate() {
            let mut orred_type: Option<TUnion> = None;

            for assertion in new_type_part_parts {
                let result_type_candidate = assertion_reconciler::reconcile(
                    context,
                    assertion,
                    result_type.as_ref(),
                    Some(key_str),
                    inside_loop,
                    Some(span),
                    can_report_issues
                        && new_type_part_parts.len() == 1
                        && referenced_var_ids.contains(key)
                        && active_new_types.get(key).is_some_and(|active_new_type| active_new_type.contains(&i)),
                    negated,
                );

                orred_type =
                    Some(add_optional_union_type(result_type_candidate, orred_type.as_ref(), context.codebase));
            }

            result_type = orred_type;
        }

        let result_type = result_type.unwrap_or_else(get_never);

        let key_parts = break_up_path_into_parts(key_str);

        if !did_type_exist && result_type.is_never() {
            // Even when the type doesn't exist and result is never, we still need to
            // update parent array types for negated isset/key_exists to remove the key
            if key_str.ends_with(']') && (has_inverted_isset || has_inverted_key_exists) {
                adjust_array_type_remove_key(key_parts.clone(), block_context, changed_var_ids, context.codebase);
            }

            continue;
        }

        let type_changed =
            if let Some(before_adjustment) = &before_adjustment { &result_type != before_adjustment } else { true };

        if type_changed {
            changed_var_ids.insert(*key);
            if key_str.ends_with(']') && !has_inverted_isset && !has_inverted_key_exists && !has_empty && !is_equality {
                adjust_array_type(key_parts.clone(), block_context, changed_var_ids, &result_type, context.codebase);
            } else if key_str.ends_with(']') && (has_inverted_isset || has_inverted_key_exists) {
                adjust_array_type_remove_key(key_parts.clone(), block_context, changed_var_ids, context.codebase);
            } else if key_str.contains("->") && !is_equality {
                adjust_object_property_type(key_parts.clone(), block_context, changed_var_ids, &result_type, context);
            }

            if key_str != "$this" {
                let mut removable_keys: Vec<Atom> = Vec::new();
                let local_keys = block_context.locals.keys().copied().collect::<Vec<_>>();
                for new_key in local_keys {
                    if new_key == *key {
                        continue;
                    }

                    if is_real && !new_types.contains_key(&new_key) && var_has_root(new_key, *key) {
                        if let Some(references_map) = reference_graph.get(&new_key) {
                            let references_to_fix = references_map.iter().copied().collect::<Vec<_>>();

                            match references_to_fix.len() {
                                0 => {}
                                1 => {
                                    let reference_to_fix = references_to_fix[0];
                                    reference_graph.remove(&reference_to_fix);
                                    if block_context.references_in_scope.contains_key(&reference_to_fix) {
                                        block_context.decrement_reference_count(reference_to_fix.as_str());
                                        block_context.references_in_scope.remove(&reference_to_fix);
                                    }
                                }
                                _ => {
                                    for reference in &references_to_fix {
                                        if let Some(inner_set) = reference_graph.get_mut(reference) {
                                            inner_set.remove(&new_key);
                                        }
                                    }

                                    if let Some(new_primary_reference) = reference_graph
                                        .get(&references_to_fix[0])
                                        .and_then(|inner_set| inner_set.iter().next().copied())
                                    {
                                        if block_context.references_in_scope.contains_key(&new_primary_reference) {
                                            block_context.decrement_reference_count(new_primary_reference.as_str());
                                            block_context.references_in_scope.remove(&new_primary_reference);
                                        }

                                        for referenced_value in block_context.references_in_scope.values_mut() {
                                            if *referenced_value == new_key {
                                                *referenced_value = new_primary_reference;
                                            }
                                        }
                                    }
                                }
                            }
                        }

                        reference_graph.remove(&new_key);
                        removable_keys.push(new_key);
                        if block_context.references_in_scope.contains_key(&new_key) {
                            block_context.decrement_reference_count(new_key.as_str());
                            block_context.references_in_scope.remove(&new_key);
                        }
                    }
                }

                for new_key in removable_keys {
                    block_context.locals.remove(&new_key);
                }
            }
        } else if !has_negation && !has_truthy_or_falsy_or_empty && !has_isset {
            changed_var_ids.insert(*key);
        }

        if !has_object_array_access {
            block_context.locals.insert(*key, Rc::new(result_type));
        }

        let key_parts_0_atom = atom(&key_parts[0]);
        if let Some(existing_type) = block_context.locals.get(key).cloned()
            && !did_type_exist
            && reference_graph.contains_key(&key_parts_0_atom)
        {
            // If key is new, create references for other variables that reference the root variable.
            let mut reference_key_parts = key_parts.clone();
            for reference in &reference_graph[&key_parts_0_atom] {
                reference.as_str().clone_into(&mut reference_key_parts[0]);
                let reference_key = atom(&reference_key_parts.join(""));
                block_context.locals.insert(reference_key, existing_type.clone());
            }
        }
    }
}

fn adjust_array_type(
    mut key_parts: Vec<String>,
    context: &mut BlockContext<'_>,
    changed_var_ids: &mut AtomSet,
    result_type: &TUnion,
    codebase: &CodebaseMetadata,
) {
    key_parts.pop();
    let Some(array_key) = key_parts.pop() else {
        return;
    };
    key_parts.pop();

    let base_key = key_parts.join("");
    let base_key_atom = atom(&base_key);

    if array_key.starts_with('$') {
        // When the key is a variable, we can't narrow to a specific key,
        // but we CAN remove empty array variants since isset proves the array is non-empty.
        if let Some(existing_type) = context.locals.get(&base_key_atom).cloned()
            && existing_type.types.iter().any(|t| matches!(t, TAtomic::Array(a) if a.is_empty()))
        {
            let mut narrowed = (*existing_type).clone();
            narrowed.types.to_mut().retain(|t| !matches!(t, TAtomic::Array(a) if a.is_empty()));
            if !narrowed.types.is_empty() {
                context.locals.insert(base_key_atom, Rc::new(narrowed));
                changed_var_ids.insert(atom(&format!("{}[{}]", base_key, array_key)));
            }
        }
        return;
    }

    let mut has_string_offset = false;

    let arraykey_offset = if array_key.starts_with('\'') || array_key.starts_with('\"') {
        has_string_offset = true;
        array_key[1..(array_key.len() - 1)].to_string()
    } else {
        array_key.clone()
    };

    let mut existing_type = if let Some(existing_type) = context.locals.get(&base_key_atom) {
        (**existing_type).clone()
    } else {
        return;
    };

    let atomic_types = std::mem::take(existing_type.types.to_mut());
    let mut compatible_types = Vec::with_capacity(atomic_types.len());

    for mut base_atomic_type in atomic_types {
        match &mut base_atomic_type {
            TAtomic::Array(TArray::Keyed(TKeyedArray { known_items, .. })) => {
                let dictkey = if has_string_offset {
                    ArrayKey::String(atom(&arraykey_offset))
                } else if let Ok(arraykey_value) = arraykey_offset.parse::<i64>() {
                    ArrayKey::Integer(arraykey_value)
                } else {
                    compatible_types.push(base_atomic_type);
                    continue;
                };

                if let Some(known_items) = known_items {
                    if let Some((existing_optional, existing_item_type)) = known_items.get(&dictkey) {
                        match intersect_union_types(result_type, existing_item_type, codebase) {
                            Some(intersected) if !intersected.is_never() => {
                                known_items.insert(dictkey, (*existing_optional, intersected));
                            }
                            _ => {
                                continue;
                            }
                        }
                    } else {
                        known_items.insert(dictkey, (false, result_type.clone()));
                    }
                } else {
                    *known_items = Some(BTreeMap::from([(dictkey, (false, result_type.clone()))]));
                }
            }
            TAtomic::Array(TArray::List(TList { known_elements, .. })) => {
                if let Ok(arraykey_offset) = arraykey_offset.parse::<usize>() {
                    if let Some(known_elements) = known_elements {
                        if let Some((_, existing_item_type)) = known_elements.get(&arraykey_offset) {
                            match intersect_union_types(result_type, existing_item_type, codebase) {
                                Some(intersected) if !intersected.is_never() => {
                                    known_elements.insert(arraykey_offset, (false, intersected));
                                }
                                _ => {
                                    continue;
                                }
                            }
                        } else {
                            known_elements.insert(arraykey_offset, (false, result_type.clone()));
                        }
                    } else {
                        *known_elements = Some(BTreeMap::from([(arraykey_offset, (false, result_type.clone()))]));
                    }
                }
            }
            TAtomic::Mixed(_) => {
                let key = if has_string_offset {
                    ArrayKey::String(atom(&arraykey_offset))
                } else if let Ok(arraykey_value) = arraykey_offset.parse::<i64>() {
                    ArrayKey::Integer(arraykey_value)
                } else {
                    compatible_types.push(base_atomic_type);
                    continue;
                };

                base_atomic_type = TAtomic::Array(TArray::Keyed(TKeyedArray {
                    known_items: Some(BTreeMap::from([(key, (false, result_type.clone()))])),
                    parameters: Some((Arc::new(get_arraykey()), Arc::new(get_mixed()))),
                    non_empty: true,
                }));
            }
            _ => {
                if base_atomic_type.is_object_type()
                    || base_atomic_type.is_string()
                    || base_atomic_type.is_generic_parameter()
                    || matches!(base_atomic_type, TAtomic::Variable(_))
                {
                    compatible_types.push(base_atomic_type);
                }

                continue;
            }
        }

        changed_var_ids.insert(concat_atom!(&base_key, "[", &array_key, "]"));

        if let Some(last_part) = key_parts.last()
            && last_part == "]"
        {
            adjust_array_type(
                key_parts.clone(),
                context,
                changed_var_ids,
                &wrap_atomic(base_atomic_type.clone()),
                codebase,
            );
        }

        compatible_types.push(base_atomic_type);
    }

    if !compatible_types.is_empty() {
        *existing_type.types.to_mut() = compatible_types;
    }

    context.locals.insert(base_key_atom, Rc::new(existing_type));
}

fn adjust_array_type_remove_key(
    mut key_parts: Vec<String>,
    context: &mut BlockContext<'_>,
    changed_var_ids: &mut AtomSet,
    codebase: &CodebaseMetadata,
) {
    key_parts.pop();
    let Some(array_key) = key_parts.pop() else {
        return;
    };

    key_parts.pop();

    if array_key.starts_with('$') {
        return;
    }

    let mut has_string_offset = false;

    let arraykey_offset = if array_key.starts_with('\'') || array_key.starts_with('\"') {
        has_string_offset = true;
        array_key[1..(array_key.len() - 1)].to_string()
    } else {
        array_key.clone()
    };

    let base_key = key_parts.join("");
    let base_key_atom = atom(&base_key);

    let mut existing_type = if let Some(existing_type) = context.locals.get(&base_key_atom) {
        (**existing_type).clone()
    } else {
        return;
    };

    for base_atomic_type in existing_type.types.to_mut() {
        match base_atomic_type {
            TAtomic::Array(TArray::Keyed(TKeyedArray { known_items, .. })) => {
                let dictkey = if has_string_offset {
                    ArrayKey::String(atom(&arraykey_offset))
                } else if let Ok(arraykey_value) = arraykey_offset.parse::<i64>() {
                    ArrayKey::Integer(arraykey_value)
                } else {
                    continue;
                };

                if let Some(known_items) = known_items {
                    known_items.remove(&dictkey);
                }
            }
            TAtomic::Array(TArray::List(TList { known_elements, .. })) => {
                if let Ok(arraykey_offset) = arraykey_offset.parse::<usize>()
                    && let Some(known_elements) = known_elements
                {
                    known_elements.remove(&arraykey_offset);
                }
            }
            _ => {
                continue;
            }
        }

        changed_var_ids.insert(concat_atom!(&base_key, "[", &array_key, "]"));

        if let Some(last_part) = key_parts.last()
            && last_part == "]"
        {
            adjust_array_type(
                key_parts.clone(),
                context,
                changed_var_ids,
                &wrap_atomic(base_atomic_type.clone()),
                codebase,
            );
        }
    }

    context.locals.insert(base_key_atom, Rc::new(existing_type));
}

/// Filters a union of object types based on a narrowed property type.
///
/// When `$input->myProp` is narrowed (e.g., via `is_string()`), this function
/// checks each object variant to see if its declared property type is compatible
/// with the narrowed type, and removes incompatible variants.
fn adjust_object_property_type(
    mut key_parts: Vec<String>,
    block_context: &mut BlockContext<'_>,
    changed_var_ids: &mut AtomSet,
    result_type: &TUnion,
    context: &Context<'_, '_>,
) {
    let Some(property_name) = key_parts.pop() else {
        return;
    };

    let Some(divider) = key_parts.pop() else {
        return;
    };

    if divider != "->" {
        return;
    }

    let base_key = key_parts.join("");
    let base_key_atom = atom(&base_key);

    let mut existing_type = if let Some(existing_type) = block_context.locals.get(&base_key_atom) {
        (**existing_type).clone()
    } else {
        return;
    };

    let atomic_types = std::mem::take(existing_type.types.to_mut());
    let original_len = atomic_types.len();
    let mut compatible_types = Vec::with_capacity(original_len);

    for base_atomic_type in atomic_types {
        let should_check = match &base_atomic_type {
            TAtomic::Object(TObject::Named(named)) => {
                let fq_class_name = named.get_name();
                if fq_class_name.eq_ignore_ascii_case("stdClass")
                    || !context.codebase.class_or_interface_exists(&fq_class_name)
                {
                    None
                } else {
                    get_property_type(context, named.get_name(), &property_name)
                }
            }
            _ => None,
        };

        if let Some(declared_property_type) = should_check {
            match intersect_union_types(result_type, &declared_property_type, context.codebase) {
                Some(intersected) if !intersected.is_never() => {
                    compatible_types.push(base_atomic_type);
                }
                _ => {
                    continue;
                }
            }
        } else {
            compatible_types.push(base_atomic_type);
        }
    }

    if !compatible_types.is_empty() && compatible_types.len() < original_len {
        *existing_type.types.to_mut() = compatible_types;
        block_context.locals.insert(base_key_atom, Rc::new(existing_type));
        changed_var_ids.insert(base_key_atom);
    }
}

fn refine_array_key(key_type: &TUnion) -> TUnion {
    fn refine_array_key_inner(key_type: &TUnion) -> Option<TUnion> {
        let mut refined = false;
        let mut types = vec![];

        for cat in key_type.types.as_ref() {
            match cat {
                TAtomic::GenericParameter(param) => {
                    if let Some(as_type) = refine_array_key_inner(&param.constraint) {
                        refined = true;
                        types.push(TAtomic::GenericParameter(param.with_constraint(as_type)));
                    } else {
                        types.push(cat.clone());
                    }
                }
                TAtomic::Scalar(TScalar::ArrayKey | TScalar::String(_) | TScalar::Integer(_)) => {
                    types.push(cat.clone());
                }
                _ => {
                    refined = true;
                    types.push(TAtomic::Scalar(TScalar::ArrayKey));
                }
            }
        }

        if refined { Some(TUnion::from_vec(types)) } else { None }
    }

    refine_array_key_inner(key_type).unwrap_or_else(|| key_type.clone())
}

static INTEGER_REGEX: LazyLock<Regex> = LazyLock::new(|| unsafe {
    // SAFETY: `unwrap_unchecked` is safe here because the regex is valid and will not panic.
    Regex::new(r"^[0-9]+$").unwrap_unchecked()
});

fn add_nested_assertions(
    new_types: &mut IndexMap<Atom, AssertionSet>,
    active_new_types: &mut IndexMap<Atom, HashSet<usize>>,
    context: &BlockContext<'_>,
) {
    let mut keys_to_remove = vec![];

    'outer: for (nk, new_type) in new_types.clone() {
        let nk_str = nk.as_str();
        if (nk_str.contains('[') || nk_str.contains("->"))
            && (new_type[0][0] == Assertion::IsEqualIsset || new_type[0][0] == Assertion::IsIsset)
        {
            let mut key_parts = break_up_path_into_parts(nk_str);
            key_parts.reverse();

            let mut nesting = 0;
            let mut base_key;

            unsafe {
                // SAFETY: `pop` will always return a value because we checked that the key contains either `[` or `->`.
                base_key = key_parts.pop().unwrap_unchecked();

                if !&base_key.starts_with('$') && key_parts.len() > 2 && key_parts.last().unwrap_unchecked() == "::$" {
                    base_key += key_parts.pop().unwrap_unchecked().as_str();
                    base_key += key_parts.pop().unwrap_unchecked().as_str();
                }
            };

            let base_key_atom = atom(&base_key);
            let base_key_set = if let Some(base_key_type) = context.locals.get(&base_key_atom) {
                !base_key_type.is_nullable()
            } else {
                false
            };

            if !base_key_set {
                new_types.insert(
                    base_key_atom,
                    if let Some(mut existing_entry) = new_types.get(&base_key_atom).cloned() {
                        existing_entry.push(vec![Assertion::IsEqualIsset]);
                        existing_entry
                    } else {
                        vec![vec![Assertion::IsEqualIsset]]
                    },
                );
            }

            while let Some(divider) = key_parts.pop() {
                if divider == "[" {
                    let array_key = unsafe {
                        // SAFETY: we know that after `[` there is always an array key, so `pop` will not panic.
                        key_parts.pop().unwrap_unchecked()
                    };

                    key_parts.pop();

                    let new_base_key = base_key.clone() + "[" + array_key.as_str() + "]";
                    let base_key_atom = atom(&base_key);

                    let entry = new_types.entry(base_key_atom).or_default();

                    let new_key = if array_key.starts_with('\'') {
                        Some(ArrayKey::String(atom(&array_key[1..(array_key.len() - 1)])))
                    } else if array_key.starts_with('$') {
                        None
                    } else if let Ok(arraykey_value) = array_key.parse::<i64>() {
                        Some(ArrayKey::Integer(arraykey_value))
                    } else {
                        continue 'outer;
                    };

                    if let Some(new_key) = new_key {
                        entry.push(vec![Assertion::HasNonnullEntryForKey(new_key)]);

                        if key_parts.is_empty() {
                            // Only remove the nested key if it contains ONLY isset-related assertions
                            // If it has other assertions (e.g., IsType from is_string()), keep them
                            let only_isset_assertions = new_type.iter().all(|clause| {
                                clause
                                    .iter()
                                    .all(|assertion| matches!(assertion, Assertion::IsIsset | Assertion::IsEqualIsset))
                            });

                            if only_isset_assertions {
                                keys_to_remove.push(nk);

                                if nesting == 0 && base_key_set && active_new_types.swap_remove(&nk).is_some() {
                                    active_new_types.entry(base_key_atom).or_default().insert(entry.len() - 1);
                                }

                                continue 'outer;
                            }
                        }
                    } else {
                        entry.push(vec![Assertion::HasIntOrStringArrayAccess]);
                    }

                    base_key = new_base_key;
                    nesting += 1;
                    continue;
                }

                if divider == "->" {
                    let property_name = unsafe {
                        // SAFETY: we know that after `->` there is always a property name, so `pop` will not panic.
                        key_parts.pop().unwrap_unchecked()
                    };

                    let new_base_key = base_key.clone() + "->" + property_name.as_str();
                    let base_key_atom = atom(&base_key);

                    if !new_types.contains_key(&base_key_atom) {
                        new_types.insert(base_key_atom, vec![vec![Assertion::IsIsset]]);
                    }

                    base_key = new_base_key;
                } else {
                    break;
                }

                if key_parts.is_empty() {
                    break;
                }
            }
        }
    }

    new_types.retain(|k, _| !keys_to_remove.contains(k));
}

pub fn break_up_path_into_parts(path: &str) -> Vec<String> {
    if path.is_empty() {
        return vec![String::new()];
    }

    let mut parts: Vec<String> = Vec::with_capacity(path.len() / 4 + 1);
    parts.push(String::with_capacity(16));

    let mut chars = path.chars().peekable();

    let mut string_char: Option<char> = None;
    let mut escape_char = false;
    let mut brackets: i32 = 0;

    while let Some(c) = chars.next() {
        if let Some(quote) = string_char {
            // SAFETY: the `parts` vector will always contain at least 1 string.
            unsafe {
                parts.last_mut().unwrap_unchecked().push(c);
            }

            if c == quote && !escape_char {
                string_char = None;
            }

            escape_char = c == '\\' && !escape_char;
        } else {
            let mut token_found: Option<&'static str> = None;
            match c {
                '[' => {
                    if brackets == 0 {
                        token_found = Some("[");
                    } else {
                        unsafe {
                            parts.last_mut().unwrap_unchecked().push(c);
                        }
                    }
                    brackets += 1;
                }
                ']' => {
                    brackets -= 1;
                    if brackets == 0 {
                        token_found = Some("]");
                    } else {
                        unsafe {
                            parts.last_mut().unwrap_unchecked().push(c);
                        }
                    }
                }
                '\'' | '"' => {
                    string_char = Some(c);
                    unsafe {
                        // SAFETY: the `parts` vector will always contain at least 1 string.
                        parts.last_mut().unwrap_unchecked().push(c);
                    }
                }
                ':' if brackets == 0 && chars.peek() == Some(&':') => {
                    let mut lookahead = chars.clone();
                    lookahead.next();
                    if lookahead.peek() == Some(&'$') {
                        chars.next();
                        chars.next();
                        token_found = Some("::$");
                    } else {
                        unsafe {
                            // SAFETY: the `parts` vector will always contain at least 1 string.
                            parts.last_mut().unwrap_unchecked().push(c);
                        }
                    }
                }
                '-' if brackets == 0 && chars.peek() == Some(&'>') => {
                    chars.next();
                    token_found = Some("->");
                }
                _ => {
                    unsafe {
                        // SAFETY: the `parts` vector will always contain at least 1 string.
                        parts.last_mut().unwrap_unchecked().push(c);
                    }
                }
            }

            if let Some(token) = token_found {
                if let Some(last_part) = parts.last_mut()
                    && last_part.is_empty()
                {
                    *last_part = token.to_string();
                } else {
                    parts.push(token.to_string());
                }

                parts.push(String::new());
            }
        }
    }

    // If the path does not end with a token, the last added empty string will be unused.
    // We remove it before returning.
    if let Some(last_part) = parts.last()
        && last_part.is_empty()
    {
        parts.pop();
    }

    parts
}

fn get_value_for_key(
    context: &mut Context<'_, '_>,
    key: Atom,
    block_context: &mut BlockContext<'_>,
    new_assertions: &IndexMap<Atom, AssertionSet>,
    has_isset: bool,
    has_inverted_isset: bool,
    has_inverted_key_exists: bool,
    has_empty: bool,
    inside_loop: bool,
    has_object_array_access: &mut bool,
) -> Option<TUnion> {
    let key_str = key.as_str();
    let mut key_parts = break_up_path_into_parts(key_str);
    if key_parts.is_empty() {
        return None;
    }

    if key_parts.len() == 1 {
        if let Some(t) = block_context.locals.get(&key) {
            return Some((**t).clone());
        }

        return None;
    }

    key_parts.reverse();

    let mut base_key;

    unsafe {
        // SAFETY: `pop` will always return a value because we checked that the key has more than one part.
        base_key = key_parts.pop().unwrap_unchecked();

        if !base_key.starts_with('$')
            && key_parts.len() > 2
            && key_parts.last().is_some_and(|part| part.starts_with("::$"))
        {
            // SAFETY: `pop` will always return a value because we checked that the key has more than two parts.
            base_key += key_parts.pop().unwrap_unchecked().as_str();
            base_key += key_parts.pop().unwrap_unchecked().as_str();
        }
    };

    let base_key_atom = atom(&base_key);
    if let std::collections::hash_map::Entry::Vacant(e) = block_context.locals.entry(base_key_atom) {
        if base_key.contains("::") {
            let base_key_parts = &base_key.split("::").collect::<Vec<&str>>();
            let fq_class_name = &base_key_parts[0];
            let const_name = &base_key_parts[1];

            if !context.codebase.class_like_exists(fq_class_name) {
                return None;
            }

            let class_constant = context.codebase.get_class_constant_type(fq_class_name, const_name);

            if let Some(class_constant) = class_constant {
                let class_constant = Rc::new(match class_constant {
                    Cow::Borrowed(t) => t.clone(),
                    Cow::Owned(t) => t,
                });

                e.insert(class_constant);
            } else {
                return None;
            }
        } else {
            return None;
        }
    }

    let mut base_key_atom = atom(&base_key);
    while let Some(divider) = key_parts.pop() {
        let base_key_type = block_context.locals.get(&base_key_atom)?;

        if divider == "[" {
            let array_key = key_parts.pop()?;

            key_parts.pop();

            let array_key_offset = if INTEGER_REGEX.is_match(&array_key)
                && let Ok(integer) = array_key.parse::<usize>()
            {
                Some(integer)
            } else {
                None
            };

            let array_key_type = if let Some(array_key_offset) = array_key_offset {
                ArrayKey::Integer(array_key_offset as i64)
            } else {
                ArrayKey::String(atom(&array_key.replace('\'', "")))
            };

            let new_base_key = base_key.clone() + "[" + array_key.as_str() + "]";
            let new_base_key_atom = atom(&new_base_key);

            if !block_context.locals.contains_key(&new_base_key_atom) {
                let mut new_base_type: Option<Rc<TUnion>> = None;
                let mut atomic_types = base_key_type.types.to_vec();

                atomic_types.reverse();
                while let Some(existing_key_type_part) = atomic_types.pop() {
                    if let TAtomic::GenericParameter(TGenericParameter { constraint, .. }) = existing_key_type_part {
                        atomic_types.extend(Arc::unwrap_or_clone(constraint).types.into_owned());
                        continue;
                    }

                    let mut new_base_type_candidate;

                    if let TAtomic::Array(TArray::Keyed(TKeyedArray { known_items, .. })) = &existing_key_type_part {
                        if has_empty {
                            return None;
                        }

                        let known_item = if !array_key.starts_with('$')
                            && let Some(known_items) = known_items
                        {
                            known_items.get(&array_key_type)
                        } else {
                            None
                        };

                        if let Some(known_item) = known_item {
                            let known_item = known_item.clone();

                            new_base_type_candidate = known_item.1.clone();

                            if known_item.0 {
                                new_base_type_candidate.set_possibly_undefined(true, None);
                            }
                        } else {
                            if has_empty {
                                return None;
                            }

                            new_base_type_candidate =
                                get_iterable_value_parameter(&existing_key_type_part, context.codebase)?;

                            if new_base_type_candidate.is_mixed()
                                && !has_isset
                                && !has_inverted_isset
                                && !has_inverted_key_exists
                            {
                                return Some(new_base_type_candidate);
                            }

                            if (has_isset || has_inverted_isset || has_inverted_key_exists)
                                && new_assertions.contains_key(&new_base_key_atom)
                            {
                                if has_inverted_isset && new_base_key_atom == key {
                                    new_base_type_candidate = add_union_type(
                                        new_base_type_candidate,
                                        &get_null(),
                                        context.codebase,
                                        CombinerOptions::default(),
                                    );
                                }

                                new_base_type_candidate.set_possibly_undefined(true, None);
                            }
                        }
                    } else if let TAtomic::Array(TArray::List(TList { known_elements, .. })) = &existing_key_type_part {
                        if has_empty {
                            return None;
                        }

                        let known_item = if let Some(known_items) = known_elements
                            && let Some(array_key_offset) = array_key_offset
                        {
                            known_items.get(&array_key_offset)
                        } else {
                            None
                        };

                        if let Some(known_item) = known_item {
                            new_base_type_candidate = known_item.1.clone();

                            if known_item.0 {
                                new_base_type_candidate.set_possibly_undefined(true, None);
                            }
                        } else {
                            new_base_type_candidate =
                                get_iterable_value_parameter(&existing_key_type_part, context.codebase)?;

                            if (has_isset || has_inverted_isset || has_inverted_key_exists)
                                && new_assertions.contains_key(&new_base_key_atom)
                            {
                                if has_inverted_isset && new_base_key_atom == key {
                                    new_base_type_candidate = add_union_type(
                                        new_base_type_candidate,
                                        &get_null(),
                                        context.codebase,
                                        CombinerOptions::default(),
                                    );
                                }

                                new_base_type_candidate.set_possibly_undefined(true, None);
                            }
                        }
                    } else if matches!(existing_key_type_part, TAtomic::Scalar(TScalar::String(_))) {
                        return Some(get_string());
                    } else if existing_key_type_part.is_never() || existing_key_type_part.is_mixed_isset_from_loop() {
                        return Some(get_mixed_maybe_from_loop(inside_loop));
                    } else if let TAtomic::Object(TObject::Named(_named_object)) = &existing_key_type_part {
                        if has_isset || has_inverted_isset || has_inverted_key_exists {
                            *has_object_array_access = true;
                            block_context.locals.remove(&new_base_key_atom);

                            return None;
                        }

                        return Some(get_mixed());
                    } else {
                        return Some(get_mixed());
                    }

                    let resulting_type = Rc::new(if let Some(new_base_type) = &new_base_type {
                        add_union_type(
                            new_base_type_candidate,
                            new_base_type,
                            context.codebase,
                            CombinerOptions::default(),
                        )
                    } else {
                        new_base_type_candidate.clone()
                    });

                    new_base_type = Some(resulting_type.clone());
                    block_context.locals.insert(new_base_key_atom, resulting_type);
                }
            }

            base_key = new_base_key;
            base_key_atom = new_base_key_atom;
        } else if divider == "->" || divider == "::$" {
            let property_name = key_parts.pop()?;
            let new_base_key = base_key.clone() + "->" + property_name.as_str();
            let new_base_key_atom = atom(&new_base_key);

            if !block_context.locals.contains_key(&new_base_key_atom) {
                let mut new_base_type: Option<Rc<TUnion>> = None;
                let mut atomic_types = base_key_type.types.to_vec();

                while let Some(existing_key_type_part) = atomic_types.pop() {
                    if let TAtomic::GenericParameter(TGenericParameter { constraint, .. }) = existing_key_type_part {
                        atomic_types.extend(Arc::unwrap_or_clone(constraint).types.into_owned());
                        continue;
                    }

                    let class_property_type: TUnion;

                    if let TAtomic::Null = existing_key_type_part {
                        class_property_type = get_null();
                        // TODO(azjezz): maybe we should exclude mixed from isset in loop?
                    } else if let TAtomic::Mixed(_) | TAtomic::GenericParameter(_) | TAtomic::Object(TObject::Any) =
                        existing_key_type_part
                    {
                        class_property_type = get_mixed();
                    } else if let TAtomic::Object(TObject::Named(named_object)) = existing_key_type_part {
                        let fq_class_name = named_object.get_name();

                        if fq_class_name.eq_ignore_ascii_case("stdClass")
                            || !context.codebase.class_or_interface_exists(&fq_class_name)
                        {
                            class_property_type = get_mixed();
                        } else {
                            class_property_type = get_property_type(context, fq_class_name, &property_name)?;
                        }
                    } else {
                        class_property_type = get_mixed();
                    }

                    let resulting_type = Rc::new(add_optional_union_type(
                        class_property_type,
                        new_base_type.as_deref(),
                        context.codebase,
                    ));

                    new_base_type = Some(resulting_type.clone());
                    block_context.locals.insert(new_base_key_atom, resulting_type);
                }
            }

            base_key = new_base_key;
            base_key_atom = new_base_key_atom;
        } else {
            return None;
        }
    }

    block_context.locals.get(&base_key_atom).map(|t| (**t).clone())
}

fn get_property_type(context: &Context<'_, '_>, classlike_name: Atom, property_name_str: &str) -> Option<TUnion> {
    // Add `$` prefix
    let property_name = concat_atom!("$", property_name_str);

    let declaring_property_class = context.codebase.get_declaring_property_class(&classlike_name, &property_name)?;
    let property_metadata = context.codebase.get_property(&classlike_name, &property_name)?;
    let property_type = property_metadata.type_metadata.as_ref().map(|metadata| metadata.type_union.clone());

    let property_type = if let Some(mut property_type) = property_type {
        expander::expand_union(
            context.codebase,
            &mut property_type,
            &TypeExpansionOptions {
                self_class: Some(declaring_property_class),
                static_class_type: StaticClassType::Name(declaring_property_class),
                ..Default::default()
            },
        );

        property_type
    } else {
        get_mixed()
    };

    Some(property_type)
}

pub(crate) fn trigger_issue_for_impossible(
    context: &mut Context<'_, '_>,
    old_var_type_string: Atom,
    key: &str,
    assertion: &Assertion,
    redundant: bool,
    negated: bool,
    span: &Span,
) {
    let mut assertion_atom = assertion.to_atom();
    let mut not_operator = assertion_atom.starts_with('!');

    if not_operator {
        assertion_atom = atom(&assertion_atom[1..]);
    }

    let mut redundant = redundant;
    if negated {
        not_operator = !not_operator;
        redundant = !redundant;
    }

    if redundant {
        if not_operator {
            if assertion_atom == "falsy" {
                not_operator = false;
                assertion_atom = atom("truthy");
            } else if assertion_atom == "truthy" {
                not_operator = false;
                assertion_atom = atom("falsy");
            }
        }

        if not_operator {
            report_impossible_issue(context, assertion, assertion_atom, key, span, old_var_type_string);
        } else {
            report_redundant_issue(context, assertion, assertion_atom, key, span, old_var_type_string);
        }
    } else if not_operator {
        report_redundant_issue(context, assertion, assertion_atom, key, span, old_var_type_string);
    } else {
        report_impossible_issue(context, assertion, assertion_atom, key, span, old_var_type_string);
    }
}

fn report_impossible_issue(
    context: &mut Context<'_, '_>,
    assertion: &Assertion,
    assertion_atom: Atom,
    key: &str,
    span: &Span,
    old_var_type_string: Atom,
) {
    let subject_desc = if old_var_type_string.is_empty() || old_var_type_string.len() > 50 {
        format!("`{key}`")
    } else {
        format!("`{key}` (type `{old_var_type_string}`)")
    };

    let (issue_kind, main_message_verb, specific_note, specific_help) = match assertion {
        Assertion::Truthy => (
            IssueCode::ImpossibleCondition,
            "will always evaluate to false".to_owned(),
            format!("Variable {subject_desc} is always falsy and can never satisfy a truthiness check."),
            "Review the logic or type of the variable; this condition will never pass.".to_string(),
        ),
        Assertion::Falsy => (
            IssueCode::ImpossibleCondition,
            "will always evaluate to false".to_owned(),
            format!("Variable {subject_desc} is always truthy, so asserting it is falsy will always be false."),
            "Review the logic or type of the variable; this condition will never pass.".to_string(),
        ),
        Assertion::IsType(TAtomic::Null) => (
            IssueCode::ImpossibleNullTypeComparison,
            "can never be `null`".to_owned(),
            format!("Variable {subject_desc} does not include `null`."),
            format!(
                "The condition checking if `{key}` is `null` will always be false. Remove or refactor the condition.",
            ),
        ),
        Assertion::IsNotType(TAtomic::Null) => (
            IssueCode::ImpossibleNullTypeComparison,
            "will always be `null`".to_owned(),
            format!("Variable {subject_desc} is already known to be `null`, so asserting it's not `null` is impossible."),
            format!("The condition checking if `{key}` is not `null` will always be false. Review the variable's state or condition."),
        ),
        Assertion::HasArrayKey(array_key_assertion) => (
            IssueCode::ImpossibleKeyCheck,
            format!("can never have the key `{array_key_assertion}`"),
            format!("Variable {subject_desc} is known to not contain the key `{array_key_assertion}`. This check will always be false."),
            "Ensure the array structure and key are correct, or remove this condition.".to_owned(),
        ),
        Assertion::DoesNotHaveArrayKey(array_key_assertion) => (
            IssueCode::ImpossibleKeyCheck,
            format!("will always have the key `{array_key_assertion}`"),
            format!("Variable {subject_desc} is known to always contain the key `{array_key_assertion}`. Asserting it doesn't have this key will always be false."),
            "Review the logic; this negative key check will always fail.".to_owned(),
        ),
        Assertion::HasNonnullEntryForKey(dict_key_name) => (
            IssueCode::ImpossibleNonnullEntryCheck,
            format!("can never have a non-null entry for key `{dict_key_name}`"),
            format!("Variable {subject_desc} is known to either not have the key `{dict_key_name}` or its value is always `null`. This check for a non-null entry will always be false."),
            "Verify the array/object structure or remove this `!empty()` style check.".to_owned(),
        ),
        _ => (
            IssueCode::ImpossibleTypeComparison,
            format!("can never be `{assertion_atom}`"),
            format!("The type of variable {subject_desc} is incompatible with the assertion that it is `{assertion_atom}`."),
            "This condition is impossible and the associated code block will never execute. Review the types and condition logic.".to_owned(),
        ),
    };

    context.collector.report_with_code(
        issue_kind,
        Issue::warning(format!("Impossible condition: variable {subject_desc} {main_message_verb}."))
            .with_annotation(
                Annotation::primary(*span).with_message("This condition always evaluates to false".to_string()),
            )
            .with_note(specific_note)
            .with_help(specific_help),
    );
}

fn report_redundant_issue(
    context: &mut Context<'_, '_>,
    assertion: &Assertion,
    assertion_atom: Atom,
    key: &str,
    span: &Span,
    old_var_type_string: Atom,
) {
    let subject_desc = if old_var_type_string.is_empty() || old_var_type_string.len() > 50 {
        format!("`{key}`")
    } else {
        format!("`{key}` (type `{old_var_type_string}`)")
    };

    let (issue_kind, main_message_verb, specific_note, specific_help) = match assertion {
        Assertion::IsIsset | Assertion::IsEqualIsset => (
            IssueCode::RedundantIssetCheck,
            "is always considered set (not null)".to_owned(),
            format!("Variable {subject_desc} is already known to be non-null, making the `isset()` check redundant."),
            "Remove the redundant `isset()` check.".to_owned()
        ),
        Assertion::Truthy => (
            IssueCode::RedundantCondition,
            "will always evaluate to true".to_owned(),
            format!("Variable {subject_desc} is always truthy. This condition is redundant and the code block will always execute if reached."),
            "Simplify or remove the redundant condition if the guarded code should always run.".to_owned()
        ),
        Assertion::Falsy => (
            IssueCode::RedundantCondition,
            "will always evaluate to true".to_owned(),
            format!("Variable {subject_desc} is always falsy, so asserting it's falsy is always true and redundant."),
            "Simplify or remove the redundant condition if the guarded code should always run.".to_owned()
        ),
        Assertion::HasArrayKey(array_key_assertion) => (
            IssueCode::RedundantKeyCheck,
            format!("will always have the key `{array_key_assertion}`"),
            format!("Variable {subject_desc} is known to always contain the key `{array_key_assertion}`. This check is redundant."),
            "Remove the redundant `array_key_exists()` or key check.".to_owned()
        ),
        Assertion::DoesNotHaveArrayKey(array_key_assertion) => (
            IssueCode::RedundantKeyCheck,
            format!("will never have the key `{array_key_assertion}`"),
            format!("Variable {subject_desc} is known to never contain the key `{array_key_assertion}`. This negative check is redundant."),
            "Remove the redundant negative key check.".to_owned()
        ),
        Assertion::HasNonnullEntryForKey(dict_key_name) => (
            IssueCode::RedundantNonnullEntryCheck,
            format!("will always have a non-null entry for key `{dict_key_name}`"),
            format!("Variable {subject_desc} is known to always have a non-null value for key `{dict_key_name}`. This `!empty()` style check is redundant."),
            "Remove the redundant non-null entry check.".to_owned()
        ),
        Assertion::IsType(TAtomic::Mixed(mixed)) if mixed.is_non_null() => (
            IssueCode::RedundantNonnullTypeComparison,
            "is already known to be non-null".to_owned(),
            format!("Variable {subject_desc} is already non-null. Checking against `mixed (not null)` is redundant."),
            "Remove the redundant non-null check.".to_owned()
        ),
        Assertion::IsNotType(TAtomic::Mixed(mixed)) if mixed.is_non_null() => (
            IssueCode::RedundantTypeComparison,
            "comparison with `mixed (not null)` is redundant".to_owned(),
            format!("The check against `mixed (not null)` for variable {subject_desc} might be overly broad or redundant depending on context."),
            "Verify if a more specific type check is needed.".to_owned()
        ),
        _ => (
            IssueCode::RedundantTypeComparison,
            format!("is already known to be `{assertion_atom}`"),
            format!("The type of variable {subject_desc} already satisfies the condition that it is `{assertion_atom}`. This check is redundant."),
            "This condition is always true and the associated code block will always execute if reached. Consider simplifying.".to_owned()
        ),
    };

    context.collector.report_with_code(
        issue_kind,
        Issue::help(format!("Redundant condition: variable {subject_desc} {main_message_verb}."))
            .with_annotation(
                Annotation::primary(*span).with_message("This condition always evaluates to true".to_string()),
            )
            .with_note(specific_note)
            .with_help(specific_help),
    );
}

fn map_generic_constraint<F>(generic_parameter: &TGenericParameter, f: F) -> Option<TAtomic>
where
    F: FnOnce(&TUnion) -> TUnion,
{
    let parameter = generic_parameter.with_constraint(f(&generic_parameter.constraint));

    if parameter.constraint.is_never() { None } else { Some(TAtomic::GenericParameter(parameter)) }
}

fn map_concrete_generic_constraint<F>(generic_parameter: &TGenericParameter, f: F) -> Option<TAtomic>
where
    F: FnOnce(&TUnion) -> TUnion,
{
    let parameter = if generic_parameter.constraint.is_mixed() {
        generic_parameter.clone()
    } else {
        generic_parameter.with_constraint(f(&generic_parameter.constraint))
    };

    if parameter.constraint.is_never() { None } else { Some(TAtomic::GenericParameter(parameter)) }
}

pub(crate) fn map_generic_constraint_or_else<F, D>(generic_parameter: &TGenericParameter, d: D, f: F) -> Option<TAtomic>
where
    F: FnOnce(&TUnion) -> TUnion,
    D: FnOnce() -> TUnion,
{
    let parameter = if generic_parameter.constraint.is_mixed() {
        generic_parameter.with_constraint(d())
    } else {
        generic_parameter.with_constraint(f(&generic_parameter.constraint))
    };

    if parameter.constraint.is_never() { None } else { Some(TAtomic::GenericParameter(parameter)) }
}

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

    #[test]
    fn test_consecutive_tokens() {
        let path = "$service_name->prop[0]->foo::$prop";
        let expected: Vec<&str> = vec!["$service_name", "->", "prop", "[", "0", "]", "->", "foo", "::$", "prop"];
        let result = break_up_path_into_parts(path);
        assert_eq!(result, expected);
    }
}