use crate::cache::CacheKey;
use crate::geom::{Bounds3, Transform};
use crate::model::{Include, InstanceRecord, ModelData, ModelId, ModelSummary, SceneRecord};
use crate::semantic::{SemanticEvent, SemanticSink, TraversalContext};
use crate::types::{
    Diagnostic, DiagnosticCode, LimitCounters, LimitKind, ParseError, ParseOptions, add_diag,
    limit_error,
};
use std::collections::{HashMap, HashSet, VecDeque};

#[derive(Clone, Copy)]
struct DefinitionVisit {
    index: usize,
    transform: Transform,
    depth: u64,
    reflected: bool,
    colour: crate::ColourCode,
}

struct ResolvedInclude<'src> {
    target: Option<usize>,
    include: Include<'src>,
}

fn emit_definition(
    model: &ModelData<'_>,
    definition_id: ModelId,
    model_id: smol_str::SmolStr,
    transform: Transform,
    depth: u64,
    colour: crate::ColourCode,
    summaries: &mut Vec<ModelSummary>,
    sink: &mut impl SemanticSink,
) -> Result<(), ParseError> {
    sink.on_event(
        &SemanticEvent::ModelBoundary {
            name: model.path.as_str().into(),
            root: model.key.clone(),
        },
        &TraversalContext::for_model(
            transform,
            colour,
            model.bfc,
            model.texmap_state,
            model.texmap_descriptor.as_ref(),
            model.file_id,
            None,
        ),
    );
    for geometry in &model.geometry {
        let event = SemanticEvent::GeometryEmitted {
            primitive_id: geometry.primitive_id,
            source: geometry.source.clone(),
            span: geometry.span,
            line_type: geometry.line_type,
            colour: geometry.colour,
            vertices: geometry.vertices.as_slice(),
            bfc: geometry.bfc,
            texmap: geometry.texmap.as_ref(),
            inverted: geometry.inverted,
        };
        sink.on_event(
            &event,
            &TraversalContext::for_model(
                transform,
                colour,
                geometry.bfc,
                model.texmap_state,
                model.texmap_descriptor.as_ref(),
                model.file_id,
                Some(geometry.span),
            ),
        );
    }
    for _ in &model.step_ends {
        sink.on_event(
            &SemanticEvent::StepBoundary,
            &TraversalContext::for_model(
                transform,
                colour,
                model.bfc,
                model.texmap_state,
                model.texmap_descriptor.as_ref(),
                model.file_id,
                None,
            ),
        );
    }
    let step_ends = model
        .step_ends
        .iter()
        .map(|offset| usize::try_from(*offset).map_err(|_| ParseError::Overflow("step end offset")))
        .collect::<Result<Vec<_>, _>>()?;
    summaries.push(ModelSummary {
        model: definition_id,
        id: model_id,
        path: model.path.as_str().into(),
        cache_key: model.key.clone(),
        depth,
        include_spans: model.includes.iter().map(|include| include.span).collect(),
        includes: model
            .includes
            .iter()
            .map(|include| include.name.as_ref().into())
            .collect(),
        triangles: model.triangles,
        quads: model.quads,
        lines: model.lines,
        conditional_lines: model.conditional_lines,
        step_ends,
        bfc: model.bfc.state,
    });
    Ok(())
}

fn target_index(
    models: &[ModelData<'_>],
    source: &ModelData<'_>,
    include: &crate::model::Include<'_>,
    selections: Option<&HashMap<(CacheKey, crate::types::Span), CacheKey>>,
    metrics: &mut super::parser::ParseMetrics,
    by_key: &HashMap<CacheKey, usize>,
    by_path: &HashMap<crate::cache::NormalizedPath, Vec<usize>>,
) -> Result<Option<usize>, ParseError> {
    let path = crate::cache::NormalizedPath::new(include.name.as_ref()).ok();
    let Some(path) = path else {
        return Ok(None);
    };
    if let Some(selections) = selections {
        metrics.selection_lookups += 1;
        if let Some(target) = selections.get(&(source.key.clone(), include.span)) {
            metrics.selection_hits += 1;
            return by_key
                .get(target)
                .copied()
                .ok_or_else(|| {
                    ParseError::Diagnostic(Diagnostic {
                        code: DiagnosticCode::UnresolvedReference,
                        severity: crate::types::Severity::Error,
                        message: "resolver-selected target identity was not materialized".into(),
                        span: Some(include.span),
                    })
                })
                .map(Some);
        }
    }
    let candidates = by_path.get(&path).map(Vec::as_slice).unwrap_or(&[]);
    if candidates.is_empty() {
        return Ok(None);
    }
    let best_root = candidates
        .iter()
        .map(|index| &models[*index].key)
        .find(|key| key.resolved_root == source.key.resolved_root)
        .map(|key| key.resolved_root)
        .or_else(|| {
            candidates
                .iter()
                .map(|index| models[*index].key.resolved_root)
                .min()
        });
    let rooted = candidates
        .iter()
        .copied()
        .filter(|index| Some(models[*index].key.resolved_root) == best_root)
        .collect::<Vec<_>>();
    if rooted.len() > 1 {
        return Err(ParseError::Diagnostic(Diagnostic {
            code: DiagnosticCode::AmbiguousMaterialization,
            severity: crate::types::Severity::Error,
            message: format!(
                "include target {} has multiple content hashes; resolver selection required",
                path
            ),
            span: Some(include.span),
        }));
    }
    Ok(rooted.first().copied())
}

pub(crate) fn traverse(
    models: &[ModelData<'_>],
    options: &ParseOptions<'_>,
    counters: &mut LimitCounters,
    diagnostics: &mut Vec<Diagnostic>,
    metrics: &mut super::parser::ParseMetrics,
    sink: &mut impl SemanticSink,
) -> Result<(SceneRecord, Vec<ModelSummary>), ParseError> {
    if models.is_empty() {
        return Ok((
            SceneRecord {
                model_id: smol_str::SmolStr::new_static(""),
                instance_ids: Vec::new(),
                instances: Vec::new(),
                triangles: 0,
                quads: 0,
                lines: 0,
                conditional_lines: 0,
                bounds: None,
                reflection: false,
            },
            Vec::new(),
        ));
    }

    #[derive(Clone)]
    enum Visit {
        Enter {
            index: usize,
            transform: Transform,
            depth: u64,
            reflected: bool,
            colour: crate::ColourCode,
            parent_instance: Option<usize>,
        },
        Exit {
            index: usize,
        },
    }

    let selection_index = if options.target_selections.is_empty() {
        None
    } else {
        Some(
            options
                .target_selections
                .iter()
                .map(|selection| {
                    (
                        (selection.source.clone(), selection.span),
                        selection.target.clone(),
                    )
                })
                .collect::<HashMap<_, _>>(),
        )
    };
    let by_key = models
        .iter()
        .enumerate()
        .map(|(index, model)| (model.key.clone(), index))
        .collect::<HashMap<_, _>>();
    let mut by_path = HashMap::<crate::cache::NormalizedPath, Vec<usize>>::new();
    for (index, model) in models.iter().enumerate() {
        by_path.entry(model.path.clone()).or_default().push(index);
    }
    let mut resolved_includes = Vec::with_capacity(models.len());
    for model in models {
        let mut edges = Vec::with_capacity(model.includes.len());
        for include in &model.includes {
            edges.push(ResolvedInclude {
                target: target_index(
                    models,
                    model,
                    include,
                    selection_index.as_ref(),
                    metrics,
                    &by_key,
                    &by_path,
                )?,
                include: include.clone(),
            });
        }
        resolved_includes.push(edges);
    }
    let mut ids = HashMap::<ModelId, smol_str::SmolStr>::new();
    let mut definition_ids = HashMap::<CacheKey, ModelId>::new();
    let mut next_definition_id = 1_u32;
    for model in models {
        if !definition_ids.contains_key(&model.key) {
            definition_ids.insert(model.key.clone(), ModelId(next_definition_id));
            next_definition_id = next_definition_id
                .checked_add(1)
                .ok_or(ParseError::Overflow("model definition id"))?;
        }
    }
    let mut next_model_id = 1_u64;
    let mut next_instance_id = 1_u64;
    let mut summaries = Vec::new();
    let mut summarized = HashSet::<ModelId>::new();
    let root_definition_id = *definition_ids
        .get(&models[0].key)
        .ok_or(ParseError::Overflow("model definition id"))?;
    ids.insert(
        root_definition_id,
        smol_str::format_smolstr!("model-{next_model_id:08}"),
    );
    next_model_id = next_model_id
        .checked_add(1)
        .ok_or(ParseError::Overflow("model id"))?;

    let mut definition_stack = vec![DefinitionVisit {
        index: 0,
        transform: Transform::default(),
        depth: 0,
        reflected: false,
        colour: models[0].colour,
    }];
    while let Some(visit) = definition_stack.pop() {
        if options.cancellation.checkpoint() {
            return Err(ParseError::Cancelled);
        }
        let model = &models[visit.index];
        let definition_id = *definition_ids
            .get(&model.key)
            .ok_or(ParseError::Overflow("model definition id"))?;
        if !summarized.insert(definition_id) {
            continue;
        }
        metrics.definition_visits += 1;
        let model_id = if let Some(model_id) = ids.get(&definition_id) {
            model_id.clone()
        } else {
            let model_id = smol_str::format_smolstr!("model-{next_model_id:08}");
            next_model_id = next_model_id
                .checked_add(1)
                .ok_or(ParseError::Overflow("model id"))?;
            ids.insert(definition_id, model_id.clone());
            model_id
        };
        emit_definition(
            model,
            definition_id,
            model_id,
            visit.transform,
            visit.depth,
            visit.colour,
            &mut summaries,
            sink,
        )?;
        for edge in resolved_includes[visit.index].iter().rev() {
            let Some(target) = edge.target else { continue };
            let child_depth = visit
                .depth
                .checked_add(1)
                .ok_or(ParseError::Overflow("include depth"))?;
            if child_depth > options.limits.include_depth {
                continue;
            }
            definition_stack.push(DefinitionVisit {
                index: target,
                transform: visit
                    .transform
                    .compose(&edge.include.transform)
                    .ok_or(ParseError::Overflow("include transform arithmetic"))?,
                depth: child_depth,
                reflected: visit.reflected
                    ^ edge.include.inverted
                    ^ edge.include.transform.reflection(),
                colour: if edge.include.colour == crate::ColourCode::from(16_u16) {
                    visit.colour
                } else {
                    edge.include.colour
                },
            });
        }
    }

    let mut visiting = HashSet::<usize>::new();
    let mut stack = VecDeque::<Visit>::new();
    let mut child_scratch = Vec::<Visit>::new();
    let mut instance_ids = Vec::new();
    let mut instances = Vec::<InstanceRecord>::new();
    let mut scene_bounds: Option<Bounds3> = None;
    let mut scene_triangles = 0u64;
    let mut scene_quads = 0u64;
    let mut scene_lines = 0u64;
    let mut scene_conditional_lines = 0u64;
    let mut scene_reflection = false;
    let mut charged_instances = 0_u64;
    let timing = std::env::var_os("POLYMODEL_LDRAW_TIMING").is_some();

    stack.push_back(Visit::Enter {
        index: 0,
        transform: Transform::default(),
        depth: 0,
        reflected: false,
        colour: models[0].colour,
        parent_instance: None,
    });

    while let Some(visit) = stack.pop_back() {
        if options.cancellation.checkpoint() {
            return Err(ParseError::Cancelled);
        }
        match visit {
            Visit::Exit { index } => {
                visiting.remove(&index);
            }
            Visit::Enter {
                index,
                transform,
                depth,
                reflected,
                colour,
                parent_instance,
            } => {
                let model = &models[index];
                metrics.subtree_occurrences_traversed += 1;
                if !visiting.insert(index) {
                    continue;
                }
                let bounds_started = timing.then(web_time::Instant::now);
                if let Some(model_bounds) = model.bounds {
                    let transformed = transform
                        .apply_bounds(model_bounds)
                        .ok_or(ParseError::Overflow("scene transform arithmetic"))?;
                    if let Some(bounds) = scene_bounds.as_mut() {
                        bounds.add(transformed.min);
                        bounds.add(transformed.max);
                    } else {
                        scene_bounds = Some(transformed);
                    }
                }
                if let Some(started) = bounds_started {
                    metrics.traversal_bounds_ns += started.elapsed().as_nanos();
                }
                let occurrence_triangles = model
                    .quads
                    .checked_mul(2)
                    .and_then(|quads| model.triangles.checked_add(quads))
                    .ok_or(ParseError::Overflow("occurrence triangles"))?;
                counters
                    .add(LimitKind::Triangles, occurrence_triangles, &options.limits)
                    .map_err(|name| limit_error(name, None))?;
                let occurrence_lines = model
                    .lines
                    .checked_add(model.conditional_lines)
                    .ok_or(ParseError::Overflow("occurrence lines"))?;
                counters
                    .add(LimitKind::Lines, occurrence_lines, &options.limits)
                    .map_err(|name| limit_error(name, None))?;
                scene_triangles = scene_triangles
                    .checked_add(model.triangles)
                    .ok_or(ParseError::Overflow("scene triangles"))?;
                scene_quads = scene_quads
                    .checked_add(model.quads)
                    .ok_or(ParseError::Overflow("scene quads"))?;
                scene_lines = scene_lines
                    .checked_add(model.lines)
                    .ok_or(ParseError::Overflow("scene lines"))?;
                scene_conditional_lines = scene_conditional_lines
                    .checked_add(model.conditional_lines)
                    .ok_or(ParseError::Overflow("scene conditional_lines"))?;
                scene_reflection |= reflected;
                let children_started = timing.then(web_time::Instant::now);
                debug_assert!(child_scratch.is_empty());
                for edge in &resolved_includes[index] {
                    let include = &edge.include;
                    metrics.include_edges += 1;
                    if options.cancellation.checkpoint() {
                        return Err(ParseError::Cancelled);
                    }
                    counters
                        .add(LimitKind::Instances, 1, &options.limits)
                        .map_err(|name| limit_error(name, Some(include.span)))?;
                    charged_instances = charged_instances
                        .checked_add(1)
                        .ok_or(ParseError::Overflow("instance count overflow"))?;
                    let Some(target) = edge.target else {
                        add_diag(
                            options.profile,
                            diagnostics,
                            counters,
                            &options.limits,
                            DiagnosticCode::UnresolvedReference,
                            include.span,
                            "include target not found in model set",
                            false,
                        )?;
                        continue;
                    };
                    let child = &models[target];
                    if visiting.contains(&target) {
                        add_diag(
                            options.profile,
                            diagnostics,
                            counters,
                            &options.limits,
                            DiagnosticCode::GraphCycle,
                            include.span,
                            "include cycle cut at active graph key",
                            false,
                        )?;
                        continue;
                    }
                    let child_depth = depth
                        .checked_add(1)
                        .ok_or(ParseError::Overflow("include depth"))?;
                    if child_depth > options.limits.include_depth {
                        add_diag(
                            options.profile,
                            diagnostics,
                            counters,
                            &options.limits,
                            DiagnosticCode::IncludeDepthLimit,
                            include.span,
                            "include depth limit exceeded",
                            false,
                        )?;
                        continue;
                    }
                    let instance_id = smol_str::format_smolstr!("instance-{next_instance_id:08}");
                    next_instance_id = next_instance_id
                        .checked_add(1)
                        .ok_or(ParseError::Overflow("instance id"))?;
                    let composed_transform = transform
                        .compose(&include.transform)
                        .ok_or(ParseError::Overflow("include transform arithmetic"))?;
                    let inverted = reflected ^ include.inverted ^ include.transform.reflection();
                    let child_colour = if include.colour == crate::ColourCode::from(16_u16) {
                        colour
                    } else {
                        include.colour
                    };
                    sink.on_event(
                        &SemanticEvent::IncludeInstantiated {
                            target: child.path.as_str().into(),
                            transform: composed_transform,
                            colour: child_colour,
                            bfc: include.bfc,
                            texmap: include.texmap_association.clone(),
                        },
                        &TraversalContext::for_model(
                            composed_transform,
                            child_colour,
                            include.bfc,
                            include.texmap_state,
                            include.texmap.as_ref(),
                            model.file_id,
                            Some(include.span),
                        ),
                    );
                    let instance_started = timing.then(web_time::Instant::now);
                    let parent = parent_instance
                        .map(|parent| {
                            u32::try_from(parent)
                                .map_err(|_| ParseError::Overflow("parent instance index"))
                        })
                        .transpose()?;
                    instance_ids.push(instance_id.clone());
                    let instance_index = instances.len();
                    instances.push(InstanceRecord {
                        model: *definition_ids
                            .get(&child.key)
                            .ok_or(ParseError::Overflow("model definition id"))?,
                        instance_id: instance_id.clone(),
                        parent,
                        source_model: model.path.as_str().into(),
                        target_model: child.path.as_str().into(),
                        source_span: Some(include.span),
                        target_key: Some(child.key.clone()),
                        transform: composed_transform,
                        inverted,
                        bfc: Some(include.bfc),
                        direct_colour: Some(include.colour),
                        colour: Some(child_colour),
                        texmap_state: Some(include.texmap_state),
                        texmap_reference: include
                            .texmap
                            .as_ref()
                            .map(|descriptor| descriptor.pngfile.to_string()),
                        texmap: include.texmap_association.clone(),
                    });
                    child_scratch.push(Visit::Enter {
                        index: target,
                        transform: composed_transform,
                        depth: child_depth,
                        reflected: inverted,
                        colour: child_colour,
                        parent_instance: Some(instance_index),
                    });
                    if let Some(started) = instance_started {
                        metrics.traversal_instances_ns += started.elapsed().as_nanos();
                    }
                }
                if let Some(started) = children_started {
                    metrics.traversal_children_ns += started.elapsed().as_nanos();
                }
                stack.push_back(Visit::Exit { index });
                while let Some(child) = child_scratch.pop() {
                    stack.push_back(child);
                }
            }
        }
    }
    let scene = SceneRecord {
        model_id: ids
            .get(&root_definition_id)
            .cloned()
            .unwrap_or_else(|| models[0].path.as_str().into()),
        instance_ids,
        instances,
        triangles: scene_triangles,
        quads: scene_quads,
        lines: scene_lines,
        conditional_lines: scene_conditional_lines,
        bounds: scene_bounds,
        reflection: scene_reflection,
    };
    Ok((scene, summaries))
}