clipasm 0.2.1

A strict, typed, stack-based programmatic video compiler
Documentation
use crate::diagnostic::{Diagnostic, Result};
use crate::source::{SourcePackage, SourceSpan, SourceUnitId};

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum VisitState {
    Unvisited,
    Visiting,
    Complete,
}

struct VisitFrame {
    unit: SourceUnitId,
    next_import: usize,
}

pub(super) fn source_unit_order(package: &SourcePackage) -> Result<Vec<SourceUnitId>> {
    let unit_count = package.units().len();
    if package.root.index() >= unit_count {
        return Err(invalid_root(package));
    }

    let mut states = vec![VisitState::Unvisited; unit_count];
    let mut positions = vec![None; unit_count];
    let mut path = Vec::<SourceUnitId>::new();
    let mut order = Vec::with_capacity(unit_count);

    for index in 0..unit_count {
        let root = SourceUnitId(index);
        if states[index] != VisitState::Unvisited {
            continue;
        }

        states[index] = VisitState::Visiting;
        positions[index] = Some(path.len());
        path.push(root);
        let mut stack = vec![VisitFrame {
            unit: root,
            next_import: 0,
        }];

        while let Some(frame) = stack.last_mut() {
            let unit = &package.units()[frame.unit.index()];
            let Some(import) = unit.imports.get(frame.next_import) else {
                let completed = stack.pop().expect("active source-unit visit frame");
                let popped = path.pop().expect("active source-unit visit path");
                debug_assert_eq!(popped, completed.unit);
                positions[completed.unit.index()] = None;
                states[completed.unit.index()] = VisitState::Complete;
                order.push(completed.unit);
                continue;
            };
            frame.next_import += 1;

            let target = import.target;
            if target.index() >= unit_count {
                return Err(Diagnostic::new(
                    "E_INTERNAL_PROGRAM_LINK",
                    format!(
                        "import `{}` refers to missing source unit {}",
                        import.alias.value,
                        target.index()
                    ),
                    import.alias.span.clone(),
                ));
            }

            match states[target.index()] {
                VisitState::Unvisited => {
                    states[target.index()] = VisitState::Visiting;
                    positions[target.index()] = Some(path.len());
                    path.push(target);
                    stack.push(VisitFrame {
                        unit: target,
                        next_import: 0,
                    });
                }
                VisitState::Visiting => {
                    let start = positions[target.index()]
                        .expect("visiting source unit has an active path position");
                    let mut cycle = path[start..]
                        .iter()
                        .map(|unit| unit_label(package, *unit))
                        .collect::<Vec<_>>();
                    cycle.push(unit_label(package, target));
                    return Err(Diagnostic::new(
                        "E_PROGRAM_IMPORT_CYCLE",
                        format!("program import cycle: {}", cycle.join(" -> ")),
                        import.alias.span.clone(),
                    ));
                }
                VisitState::Complete => {}
            }
        }
    }

    Ok(order)
}

fn invalid_root(package: &SourcePackage) -> Diagnostic {
    let span = package.units().first().map_or_else(
        || SourceSpan::file_start("<source-package>"),
        |unit| SourceSpan::source_start(unit.source().clone()),
    );
    Diagnostic::new(
        "E_INTERNAL_PROGRAM_LINK",
        format!(
            "source package root refers to missing source unit {}",
            package.root.index()
        ),
        span,
    )
}

fn unit_label(package: &SourcePackage, unit: SourceUnitId) -> String {
    package.units()[unit.index()]
        .source()
        .display_path()
        .display()
        .to_string()
}

#[cfg(test)]
mod tests {
    use std::fs;
    use std::path::Path;

    use super::*;
    use crate::source::{ResolvedImport, Spanned};

    fn write(directory: &Path, name: &str, source: &str) {
        fs::write(directory.join(name), source).expect("write source fixture");
    }

    fn chain_package() -> SourcePackage {
        let directory = tempfile::tempdir().expect("temporary directory");
        write(
            directory.path(),
            "leaf.clipasm",
            "clipasm 1\ninput video: Video\nrepeat($video, 2)\n",
        );
        write(
            directory.path(),
            "middle.clipasm",
            "clipasm 1\nimport \"leaf.clipasm\" as leaf\ninput video: Video\nleaf($video)\n",
        );
        write(
            directory.path(),
            "root.clipasm",
            "clipasm 1\nimport \"middle.clipasm\" as middle\nimage(\"missing.ppm\", 1s)\nmiddle\n",
        );
        crate::language::parse_file(&directory.path().join("root.clipasm"))
            .expect("linked source package")
    }

    fn reorder(package: &SourcePackage, old_indices: &[usize]) -> SourcePackage {
        assert_eq!(old_indices.len(), package.units.len());
        let mut old_to_new = vec![usize::MAX; package.units.len()];
        for (new, old) in old_indices.iter().copied().enumerate() {
            assert!(old < package.units.len());
            assert_eq!(old_to_new[old], usize::MAX);
            old_to_new[old] = new;
        }

        let units = old_indices
            .iter()
            .map(|old| {
                let mut unit = package.units[*old].clone();
                for import in &mut unit.imports {
                    import.target = SourceUnitId(old_to_new[import.target.index()]);
                }
                unit
            })
            .collect();
        SourcePackage {
            root: SourceUnitId(old_to_new[package.root.index()]),
            units,
        }
    }

    #[test]
    fn dependency_order_is_independent_of_unit_storage() {
        let ordered = chain_package();
        assert_eq!(
            source_unit_order(&ordered).expect("ordered package"),
            vec![SourceUnitId(0), SourceUnitId(1), SourceUnitId(2)]
        );

        let root_first = reorder(&ordered, &[2, 1, 0]);
        assert_eq!(
            source_unit_order(&root_first).expect("root-first package"),
            vec![SourceUnitId(2), SourceUnitId(1), SourceUnitId(0)]
        );

        let ordered = crate::compiler::compile(&ordered).expect("ordered compile");
        let root_first = crate::compiler::compile(&root_first).expect("root-first compile");
        assert_eq!(ordered.structure_hash(), root_first.structure_hash());
        assert_eq!(
            ordered.compiled_json().expect("ordered JSON"),
            root_first.compiled_json().expect("root-first JSON")
        );
    }

    #[test]
    fn compiler_checks_disconnected_source_units() {
        let mut package = chain_package();
        let disconnected = crate::language::parse_str(
            Path::new("disconnected.clipasm"),
            "clipasm 1\nparam count: Integer = nope\nimage(\"unused.ppm\", 1s)\n",
        )
        .expect("disconnected source unit");
        package.units.push(disconnected.root().clone());

        let error = crate::compiler::compile(&package).expect_err("invalid disconnected program");
        assert_eq!(error.code, "E_INVALID_ARGUMENT_TYPE");
        assert!(error.span.file().ends_with("disconnected.clipasm"));
    }

    #[test]
    fn compiler_rejects_a_linked_package_cycle() {
        let mut package = chain_package();
        let root = package.root;
        let leaf = SourceUnitId(0);
        let span = SourceSpan::source_start(package.units[leaf.index()].source().clone());
        package.units[leaf.index()].imports.push(ResolvedImport {
            alias: Spanned::new("root".to_owned(), span),
            target: root,
        });

        let error = crate::compiler::compile(&package).expect_err("cyclic linked package");
        assert_eq!(error.code, "E_PROGRAM_IMPORT_CYCLE");
        assert!(error.message.contains("leaf.clipasm"));
        assert!(error.message.contains("middle.clipasm"));
        assert!(error.message.contains("root.clipasm"));
    }

    #[test]
    fn compiler_rejects_missing_source_unit_targets() {
        let mut package = chain_package();
        package.units[package.root.index()].imports[0].target = SourceUnitId(99);

        let error = crate::compiler::compile(&package).expect_err("missing import target");
        assert_eq!(error.code, "E_INTERNAL_PROGRAM_LINK");
        assert!(error.message.contains("missing source unit 99"));
    }

    #[test]
    fn compiler_rejects_a_missing_root_source_unit() {
        let mut package = chain_package();
        package.root = SourceUnitId(99);

        let error = crate::compiler::compile(&package).expect_err("missing package root");
        assert_eq!(error.code, "E_INTERNAL_PROGRAM_LINK");
        assert!(error.message.contains("missing source unit 99"));
    }
}