mdtablefix 0.6.1

//! Property cover for the pull-request closure.
//!
//! The named cases pin one chain and one fan-out. The closure's claim is
//! wider: over any graph of local calls, including branches, cycles and
//! self-calls, it returns exactly the workflows reachable from one that a
//! pull request starts. These properties generate small call graphs, write
//! each as real workflow YAML with a randomly chosen call spelling, and
//! compare the closure with an independent reachability computed on the
//! adjacency matrix.

use std::{collections::BTreeSet, fmt::Write as _};

use proptest::prelude::*;

use super::{pull_request_cases::parse, reader};

/// The largest graph generated. Small enough to keep a case cheap, large
/// enough for chains, branches and cycles several calls long.
const MAX_WORKFLOWS: usize = 6;

/// The spellings a local call may take, all of which must reach the file.
const CALL_PREFIXES: [&str; 3] = ["./", "$/", ""];

/// A generated call graph: which workflows a pull request starts, which
/// workflow calls which, and the spelling each call uses.
#[derive(Debug, Clone)]
struct CallGraph {
    /// Whether workflow `i` is triggered by a pull request.
    starts_on_pull_request: Vec<bool>,
    /// Whether workflow `i` calls workflow `j`, at `i * n + j`.
    calls: Vec<bool>,
    /// The prefix index each call uses, at `i * n + j`.
    spellings: Vec<usize>,
}

impl CallGraph {
    /// Returns the number of workflows in the graph.
    fn len(&self) -> usize { self.starts_on_pull_request.len() }

    /// Renders workflow `i` as YAML.
    fn workflow(&self, i: usize) -> String {
        let n = self.len();
        let trigger = if self.starts_on_pull_request[i] {
            "pull_request"
        } else {
            "workflow_call"
        };
        let jobs: String =
            (0..n)
                .filter(|j| self.calls[i * n + j])
                .fold(String::new(), |mut jobs, j| {
                    let prefix = CALL_PREFIXES[self.spellings[i * n + j]];
                    let _ = writeln!(
                        jobs,
                        "  call_{j}:\n    uses: {prefix}.github/workflows/w{j}.yml"
                    );
                    jobs
                });
        if jobs.is_empty() {
            format!("on: {trigger}\njobs: {{}}\n")
        } else {
            format!("on: {trigger}\njobs:\n{jobs}")
        }
    }

    /// Returns the workflows reachable from a pull-request trigger, computed
    /// by transitive closure over the adjacency matrix rather than by search.
    fn expected_closure(&self) -> BTreeSet<String> {
        let n = self.len();
        let mut reach = self.calls.clone();
        for i in 0..n {
            reach[i * n + i] = true;
        }
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    if reach[i * n + k] && reach[k * n + j] {
                        reach[i * n + j] = true;
                    }
                }
            }
        }
        (0..n)
            .filter(|&j| (0..n).any(|i| self.starts_on_pull_request[i] && reach[i * n + j]))
            .map(|j| format!("w{j}.yml"))
            .collect()
    }
}

/// Generates a call graph of one to [`MAX_WORKFLOWS`] workflows.
fn call_graph() -> impl Strategy<Value = CallGraph> {
    (1..=MAX_WORKFLOWS).prop_flat_map(|n| {
        (
            prop::collection::vec(any::<bool>(), n),
            prop::collection::vec(prop::bool::weighted(0.3), n * n),
            prop::collection::vec(0..CALL_PREFIXES.len(), n * n),
        )
            .prop_map(|(starts_on_pull_request, calls, spellings)| CallGraph {
                starts_on_pull_request,
                calls,
                spellings,
            })
    })
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(256))]

    /// Scenario: an arbitrary graph of local calls, in any spelling.
    ///
    /// Invariant: the closure is exactly the set of workflows reachable from
    /// one a pull request starts, cycles and self-calls included.
    #[test]
    fn the_closure_is_exactly_what_a_pull_request_can_reach(graph in call_graph()) {
        let mut all = reader::Workflows::new();
        for i in 0..graph.len() {
            let parsed = parse(&graph.workflow(i));
            prop_assert!(parsed.is_ok(), "workflow {i} did not parse: {:?}", parsed.err());
            if let Ok(workflow) = parsed {
                all.insert(format!("w{i}.yml"), workflow);
            }
        }
        prop_assert_eq!(reader::pull_request_closure(&all), graph.expected_closure());
    }
}