Skip to main content

dive_liveness/analyze/
periodic.rs

1//! Deterministic checks over borrowed graphs at committed expansion boundaries.
2//!
3//! Capture limits apply cumulatively to the run. Formula planning happens once;
4//! label and product bounds retain their per-property, per-check scope. Repeated
5//! checks are additional work, without a total-run work or byte guarantee.
6
7use super::{
8    Analysis, AnalysisError, CandidateWord, DetailedFailure, EvaluationErrors, ExplorationEvidence,
9    Failure, GraphLabelPolicy, Limits, Stage, analyze_captured, prepare, validate_analysis_context,
10};
11use crate::product::AcceptancePolicy;
12use dive_eval::next::StateVals;
13use dive_model::Model;
14use dive_runtime::{CheckOptions, Stats, capture};
15
16/// When a completed, nonexhausted level is checked in dive's default profile;
17/// the TLC profile checks once, at the end.
18///
19/// A level is checked once the graph has at least `min_states` distinct states
20/// and at least `growth_factor` times as many as at the previous check. With
21/// the default doubling, all prefix checks together cost about one final check.
22/// The schedule depends only on the graph, so results are the same at every
23/// worker count. TLC's wall-clock trigger has no deterministic equivalent; the
24/// TLC-equivalent setting is final checking (`-lncheck final`).
25///
26/// ```
27/// use dive_liveness::analyze::periodic::Schedule;
28/// let schedule = Schedule::DEFAULT;
29/// assert!(!schedule.due(65_535, 0));
30/// assert!(schedule.due(65_536, 0));
31/// assert!(!schedule.due(100_000, 65_536));
32/// assert!(schedule.due(131_072, 65_536));
33/// ```
34#[derive(Clone, Copy, Debug, PartialEq, Eq)]
35pub struct Schedule {
36    /// Smallest distinct-state count at which a prefix is checked.
37    pub min_states: u64,
38    /// Required growth factor over the previous check's distinct-state count.
39    pub growth_factor: u64,
40}
41
42impl Schedule {
43    /// The documented default: at least 2^16 states, doubling between checks.
44    pub const DEFAULT: Self = Self {
45        min_states: 1 << 16,
46        growth_factor: 2,
47    };
48
49    /// Whether a completed level with `distinct` states is due, given the
50    /// distinct-state count `last` at the previous check (zero before any).
51    #[must_use]
52    pub fn due(self, distinct: u64, last: u64) -> bool {
53        distinct >= self.min_states.max(1)
54            && distinct > last
55            && distinct >= last.saturating_mul(self.growth_factor)
56    }
57}
58
59impl Default for Schedule {
60    fn default() -> Self {
61        Self::DEFAULT
62    }
63}
64
65/// Actual deterministic-check execution facts; not evidence of a holding verdict.
66#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
67pub struct Checks {
68    /// The schedule that selected the checks.
69    pub schedule: Schedule,
70    /// Number of completed-level analysis calls, excluding the final check.
71    pub prefixes: u64,
72    /// Last level at which a nonexhausted graph was checked.
73    pub last_level: Option<u64>,
74    /// Distinct-state count at that check, zero before any.
75    pub last_size: u64,
76    /// Whether exploration actually exhausted its frontier.
77    pub exhausted: bool,
78    /// Whether the complete graph's final analysis was attempted.
79    pub final_check: bool,
80}
81
82/// A candidate found on a real committed prefix. Independent validation is required.
83#[derive(Clone, Debug)]
84pub struct PrefixCandidate {
85    /// Original property whose negation selected the word.
86    pub target_property: String,
87    /// Complete directly attributed false-property set.
88    pub properties: Vec<String>,
89    /// Actual graph states along the word.
90    pub states: Vec<StateVals>,
91    /// Zero-based closing target.
92    pub back_to: usize,
93    /// Actual transitions, including the closing edge.
94    pub edges: Vec<capture::Edge>,
95    /// Producer-owned prefix; never complete exploration.
96    pub exploration: capture::Prefix,
97}
98
99/// Analysis with explicit prefix versus complete evidence.
100#[derive(Clone, Debug)]
101pub enum PeriodicAnalysis {
102    /// Real exhaustion followed by the existing final analysis.
103    Final(Analysis),
104    /// An unvalidated word found before exploration finished.
105    Prefix(PrefixCandidate),
106}
107
108impl PeriodicAnalysis {
109    /// Releases the graph storage while retaining the actual complete or
110    /// prefix facts and any selected word. It does not validate a candidate or
111    /// promote incomplete exploration to a holding result.
112    ///
113    /// ```
114    /// use dive_liveness::analyze::periodic::{PeriodicAnalysis, PeriodicFailure, Checks};
115    /// use dive_liveness::analyze::periodic::external::NativeAnalysis;
116    /// fn release_graph(result: Result<(PeriodicAnalysis, Checks), PeriodicFailure>)
117    ///     -> Result<(NativeAnalysis, Checks), PeriodicFailure> {
118    ///     result.map(|(analysis, checks)| (analysis.into_native(), checks))
119    /// }
120    /// ```
121    #[must_use]
122    pub fn into_native(self) -> external::NativeAnalysis {
123        match self {
124            Self::Final(analysis) => external::NativeAnalysis::Final(analysis.into_native()),
125            Self::Prefix(candidate) => external::NativeAnalysis::Prefix(super::finish::Prefix {
126                word: super::finish::NativeWord {
127                    target_property: candidate.target_property,
128                    properties: candidate.properties,
129                    states: candidate.states,
130                    back_to: candidate.back_to,
131                    edges: candidate.edges,
132                },
133                exploration: candidate.exploration.into_evidence(),
134            }),
135        }
136    }
137}
138
139/// A failure with explicit capture-completion truth and actual scheduling facts.
140#[derive(Clone, Debug)]
141pub struct PeriodicFailure {
142    /// Original analysis error and typed action cause, where applicable.
143    pub failure: Box<DetailedFailure>,
144    /// Actual prefix facts, separate from the completed-exploration evidence.
145    pub prefix: Option<Box<ExplorationEvidence>>,
146    /// Whether capture completed; a lost thread remains unknown.
147    pub capture_completed: Option<bool>,
148    /// Actual checks attempted before the failure.
149    pub checks: Checks,
150}
151
152/// The fixed inputs of a level or final check.
153#[derive(Clone, Copy)]
154struct Inputs<'a> {
155    budget: &'a dive_runtime::budget::Budget,
156    control: &'a std::sync::Arc<dive_runtime::budget::EvaluationControl>,
157    model: &'a Model,
158    plans: &'a [super::PreparedProperty],
159    limits: Limits,
160    policy: AcceptancePolicy,
161    graph_labels: GraphLabelPolicy,
162}
163
164/// What the checks of one run have done and decided so far.
165struct Decisions {
166    checks: Checks,
167    stage: Stage,
168    evaluations: EvaluationErrors,
169    decision: Option<Result<CandidateWord, AnalysisError>>,
170}
171
172impl Decisions {
173    fn new(checks: Checks) -> Self {
174        Self {
175            checks,
176            stage: Stage::Capture,
177            evaluations: EvaluationErrors {
178                periodic: true,
179                ..EvaluationErrors::default()
180            },
181            decision: None,
182        }
183    }
184
185    /// Checks the graph after the completed `level`, if the schedule says so.
186    fn level(
187        &mut self,
188        inputs: Inputs<'_>,
189        level: u64,
190        graph: &capture::BehaviorGraph,
191        stats: Stats,
192    ) {
193        if stats.left_on_queue == 0
194            || !self
195                .checks
196                .schedule
197                .due(stats.distinct, self.checks.last_size)
198        {
199            return;
200        }
201        self.checks.prefixes += 1;
202        self.checks.last_level = Some(level);
203        self.checks.last_size = stats.distinct;
204        // Capture invokes this callback on its own thread. Thread-local run
205        // budgets do not cross that boundary; install the same armed signal
206        // only while a due prefix analysis runs.
207        let _scope = crate::budget::enter(inputs.budget);
208        // Due prefixes retain the frontier labels and attribution. A row
209        // cache covers expanded sources only and cannot replace that demand.
210        // Only the first property can decide a prefix: a word for it on a
211        // subgraph is a word on the complete graph, which the final search
212        // would also report first. Later properties wait for the final check.
213        match analyze_captured(
214            inputs.model,
215            inputs.plans,
216            1,
217            graph,
218            inputs.limits,
219            inputs.policy,
220            inputs.graph_labels,
221            &mut self.stage,
222            &mut self.evaluations,
223            inputs.control,
224        ) {
225            Ok(None) => {}
226            Ok(Some(word)) => self.decision = Some(Ok(word)),
227            Err(error) => self.decision = Some(Err(error)),
228        }
229    }
230
231    /// The result of a stop after a completed level, with the kept decision.
232    fn prefix(
233        self,
234        prefix: capture::Prefix,
235    ) -> Result<(PeriodicAnalysis, Checks), PeriodicFailure> {
236        let word = self.decision.unwrap_or_else(|| {
237            Err(AnalysisError::Inconsistent(
238                "prefix stopped without an analysis decision",
239            ))
240        });
241        let result = super::finish::prefix(word, prefix.evidence().clone()).map_err(|error| {
242            failure(
243                error,
244                self.stage,
245                Some(Box::new((&prefix).into())),
246                self.evaluations,
247                Some(false),
248                self.checks,
249            )
250        })?;
251        Ok((
252            PeriodicAnalysis::Prefix(result.reference(prefix)),
253            self.checks,
254        ))
255    }
256
257    /// The final check of a complete exploration.
258    fn complete(
259        mut self,
260        inputs: Inputs<'_>,
261        complete: capture::Complete,
262    ) -> Result<(PeriodicAnalysis, Checks), PeriodicFailure> {
263        let _control = inputs.control.enter(&inputs.model.evaluator).map_err(|_| {
264            failure(
265                AnalysisError::Inconsistent("another driver owns evaluator control"),
266                Stage::Product,
267                Some(Box::new((&complete).into())),
268                EvaluationErrors::default(),
269                Some(true),
270                self.checks,
271            )
272        })?;
273        self.checks.exhausted = true;
274        self.checks.final_check = true;
275        self.evaluations.periodic = false;
276        let word = analyze_captured(
277            inputs.model,
278            inputs.plans,
279            usize::MAX,
280            &complete.graph,
281            inputs.limits,
282            inputs.policy,
283            inputs.graph_labels,
284            &mut self.stage,
285            &mut self.evaluations,
286            inputs.control,
287        );
288        let result =
289            super::finish::complete(word, complete.evidence().clone()).map_err(|error| {
290                failure(
291                    error,
292                    self.stage,
293                    Some(Box::new((&complete).into())),
294                    self.evaluations,
295                    Some(true),
296                    self.checks,
297                )
298            })?;
299        let analysis = result.reference(complete);
300        Ok((PeriodicAnalysis::Final(analysis), self.checks))
301    }
302}
303
304impl From<&capture::Prefix> for ExplorationEvidence {
305    fn from(prefix: &capture::Prefix) -> Self {
306        Self {
307            stats: prefix.stats,
308            workers: prefix.workers.clone(),
309            collision: prefix.collision.clone(),
310            output: prefix.output.clone(),
311            warnings: prefix.warnings.clone(),
312        }
313    }
314}
315
316fn failure(
317    error: AnalysisError,
318    stage: Stage,
319    exploration: Option<Box<ExplorationEvidence>>,
320    evaluations: EvaluationErrors,
321    capture_completed: Option<bool>,
322    checks: Checks,
323) -> PeriodicFailure {
324    let (exploration, prefix) = if capture_completed == Some(false) {
325        (None, exploration)
326    } else {
327        (exploration, None)
328    };
329    PeriodicFailure {
330        prefix,
331        failure: Box::new(DetailedFailure {
332            failure: Failure {
333                error,
334                stage,
335                exploration,
336            },
337            evaluations,
338        }),
339        capture_completed,
340        checks,
341    }
342}
343
344/// The run's final budget check for the entry point that armed it: a
345/// result is replaced by a stop when the budget ran out while finishing.
346fn close_budget(
347    watchdog: Option<&mut dive_runtime::budget::Watchdog>,
348    result: Result<(PeriodicAnalysis, Checks), PeriodicFailure>,
349) -> Result<(PeriodicAnalysis, Checks), PeriodicFailure> {
350    if let Some(watchdog) = watchdog {
351        let finished = watchdog.finish();
352        if let Ok((analysis, checks)) = &result {
353            let error = match finished {
354                Err(error) => Some(AnalysisError::BudgetMeasurement(error)),
355                Ok(Some(exhausted)) => Some(AnalysisError::Stopped(Box::new(
356                    exhausted.during(dive_runtime::budget::Phase::Finalization),
357                ))),
358                Ok(None) => None,
359            };
360            if let Some(error) = error {
361                let (evidence, completed) = match analysis {
362                    PeriodicAnalysis::Final(Analysis::Holds(capture)) => {
363                        (ExplorationEvidence::from(capture), true)
364                    }
365                    PeriodicAnalysis::Final(Analysis::Candidate(candidate)) => {
366                        (ExplorationEvidence::from(&candidate.exploration), true)
367                    }
368                    PeriodicAnalysis::Prefix(candidate) => {
369                        let capture = &candidate.exploration;
370                        (
371                            ExplorationEvidence {
372                                stats: capture.stats,
373                                workers: capture.workers.clone(),
374                                collision: capture.collision.clone(),
375                                output: capture.output.clone(),
376                                warnings: capture.warnings.clone(),
377                            },
378                            false,
379                        )
380                    }
381                };
382                return Err(failure(
383                    error,
384                    Stage::Finalization,
385                    Some(Box::new(evidence)),
386                    EvaluationErrors::default(),
387                    Some(completed),
388                    *checks,
389                ));
390            }
391        }
392    }
393    result
394}
395
396fn budget_failure(
397    mut failure: PeriodicFailure,
398    budget: &dive_runtime::budget::Budget,
399) -> PeriodicFailure {
400    if super::budget_limit(&failure.failure.failure.error) {
401        match budget.poll() {
402            Ok(Some(exhausted)) => {
403                failure.failure.failure.error = AnalysisError::Stopped(Box::new(
404                    exhausted.during(dive_runtime::budget::Phase::Temporal),
405                ));
406            }
407            Err(error) => failure.failure.failure.error = AnalysisError::BudgetMeasurement(error),
408            Ok(None) => return failure,
409        }
410        failure.failure.evaluations = EvaluationErrors::default();
411    }
412    failure
413}
414
415/// Validates the context and plans every property once, before capture.
416fn planned(
417    model: &Model,
418    options: &CheckOptions,
419    limits: Limits,
420    checks: Checks,
421) -> Result<
422    (
423        std::sync::Arc<dive_runtime::budget::EvaluationControl>,
424        Vec<super::PreparedProperty>,
425    ),
426    PeriodicFailure,
427> {
428    // Before lowering, touching bound scopes or starting a capture host.
429    validate_analysis_context(model).map_err(|error| {
430        failure(
431            error,
432            Stage::Planning,
433            None,
434            EvaluationErrors::default(),
435            Some(false),
436            checks,
437        )
438    })?;
439    let control = super::evaluator_control(options).map_err(|error| {
440        failure(
441            error,
442            Stage::Planning,
443            None,
444            EvaluationErrors::default(),
445            Some(false),
446            checks,
447        )
448    })?;
449    let plans = {
450        let _scope = control.enter(&model.evaluator).map_err(|_| {
451            failure(
452                AnalysisError::Inconsistent("another driver owns evaluator control"),
453                Stage::Planning,
454                None,
455                EvaluationErrors::default(),
456                Some(false),
457                checks,
458            )
459        })?;
460        prepare(model, limits, &control).map_err(|error| {
461            failure(
462                error,
463                Stage::Planning,
464                None,
465                EvaluationErrors::default(),
466                Some(false),
467                checks,
468            )
469        })?
470    };
471    Ok((control, plans))
472}
473
474#[allow(
475    clippy::too_many_lines,
476    reason = "keep producer outcomes and their distinct failure evidence together"
477)]
478pub mod external;