topos 0.13.1

An autodiff compiler stack in Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

use super::candidates::Candidates;
use super::pattern::Pattern;

/// One consumer's election over the plan's candidate pool: the pattern
/// this consumer acts on at each root, and the skip mask of interior
/// and named nodes those actions replace.
///
/// A catalog serves exactly one consumer. The home consumer (a
/// forward run) elects the patterns it fuses; the emission consumer
/// elects the patterns it raises. Electing is claiming: entries never
/// overlap within one catalog, while two catalogs may elect the same
/// pool differently.
#[derive(Debug, Clone)]
pub(crate) struct Catalog {
    at: Vec<Option<Pattern>>,
    interior: Vec<bool>,
}

impl Catalog {
    /// Elects a consumer's catalog from the pool: walks the candidates
    /// in priority order and claims, first-wins, every candidate the
    /// repertoire supports whose nodes are all still free.
    ///
    /// `supports` is the consumer's repertoire — the patterns it can
    /// act on. Unsupported candidates do not claim, so their regions
    /// stay free for later supported candidates; an unelected region
    /// simply runs or lowers its recorded primitives, which is always
    /// sound. Electing an entry commits the consumer to producing the
    /// root and every named result while skipping the whole claim set.
    pub(crate) fn elect(candidates: &Candidates, supports: impl Fn(&Pattern) -> bool) -> Self {
        let length = candidates.length();
        let mut catalog = Self {
            at: vec![None; length],
            interior: vec![false; length],
        };
        let mut claimed = vec![false; length];
        for candidate in candidates.iter() {
            if !supports(&candidate.pattern) || claimed[candidate.root] {
                continue;
            }
            if candidate
                .interiors
                .iter()
                .chain(candidate.named.iter())
                .any(|&node| claimed[node])
            {
                continue;
            }
            claimed[candidate.root] = true;
            for &node in candidate.interiors.iter().chain(candidate.named.iter()) {
                claimed[node] = true;
                catalog.interior[node] = true;
            }
            catalog.at[candidate.root] = Some(candidate.pattern.clone());
        }
        catalog
    }

    /// Returns the pattern this consumer acts on at `index`, if any.
    /// Consumers read elected entries and never rematch.
    pub(crate) fn at(&self, index: usize) -> Option<&Pattern> {
        self.at[index].as_ref()
    }

    /// Returns whether this consumer's actions replace node `index`:
    /// an interior or named result of some elected entry.
    pub(crate) fn interior(&self, index: usize) -> bool {
        self.interior[index]
    }

    /// Returns how many entries this consumer elected.
    pub(crate) fn groups(&self) -> usize {
        self.at.iter().flatten().count()
    }

    /// Returns the elected entries in root order: each root and the
    /// pattern this consumer acts on there.
    pub(crate) fn entries(&self) -> impl Iterator<Item = (usize, &Pattern)> {
        self.at
            .iter()
            .enumerate()
            .filter_map(|(index, pattern)| pattern.as_ref().map(|pattern| (index, pattern)))
    }
}

#[cfg(test)]
#[path = "tests/catalog_tests.rs"]
mod tests;