knave 0.12.1

A Lisp programming language for humans and agents that infers types and ownership and compiles to readable 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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

use rustc_hash::FxHashSet;

use crate::core::BindingId;

#[derive(Default)]
pub struct Refusals {
    refused: FxHashSet<BindingId>,
    followings: Vec<Following>,
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Following {
    leader: BindingId,
    follower: BindingId,
}

impl Refusals {
    pub fn refuse(&mut self, binding: BindingId) {
        self.refused.insert(binding);
    }

    pub fn follow(&mut self, follower: BindingId, leader: BindingId) {
        self.followings.push(Following { leader, follower });
    }

    pub fn spread(mut self) -> FxHashSet<BindingId> {
        self.followings.sort_unstable();
        let mut pending: Vec<BindingId> = self.refused.iter().copied().collect();
        while let Some(leader) = pending.pop() {
            for follower in Self::followers(&self.followings, leader) {
                if self.refused.insert(follower) {
                    pending.push(follower);
                }
            }
        }
        self.refused
    }

    fn followers(sorted: &[Following], leader: BindingId) -> impl Iterator<Item = BindingId> + '_ {
        let first = sorted.partition_point(|following| following.leader < leader);
        sorted[first..]
            .iter()
            .take_while(move |following| following.leader == leader)
            .map(|following| following.follower)
    }
}

#[cfg(test)]
mod tests {
    use rustc_hash::FxHashSet;

    use super::Refusals;
    use crate::core::{BindingArena, BindingId, BindingInfo, BindingKind};

    struct RefusalFixture {
        bindings: BindingArena,
        refusals: Refusals,
    }

    impl RefusalFixture {
        fn new() -> Self {
            Self {
                bindings: BindingArena::default(),
                refusals: Refusals::default(),
            }
        }

        fn parameter(&mut self, name: &str) -> BindingId {
            self.bindings
                .add(BindingInfo::new(name.into(), BindingKind::Local, None))
        }

        fn spread(self) -> FxHashSet<BindingId> {
            self.refusals.spread()
        }
    }

    #[test]
    fn a_refusal_reaches_every_follower_down_a_chain() {
        let mut fixture = RefusalFixture::new();
        let inner = fixture.parameter("inner");
        let middle = fixture.parameter("middle");
        let outer = fixture.parameter("outer");
        fixture.refusals.follow(outer, middle);
        fixture.refusals.follow(middle, inner);
        fixture.refusals.refuse(inner);
        assert_eq!(
            fixture.spread(),
            FxHashSet::from_iter([inner, middle, outer])
        );
    }

    #[test]
    fn a_cycle_that_nothing_refuses_keeps_every_member() {
        let mut fixture = RefusalFixture::new();
        let even = fixture.parameter("even");
        let odd = fixture.parameter("odd");
        fixture.refusals.follow(even, odd);
        fixture.refusals.follow(odd, even);
        assert_eq!(fixture.spread(), FxHashSet::default());
    }

    #[test]
    fn a_refusal_that_enters_a_cycle_refuses_every_member() {
        let mut fixture = RefusalFixture::new();
        let pad = fixture.parameter("pad");
        let fill = fixture.parameter("fill");
        let push = fixture.parameter("push");
        fixture.refusals.follow(pad, fill);
        fixture.refusals.follow(fill, pad);
        fixture.refusals.follow(pad, push);
        fixture.refusals.refuse(push);
        assert_eq!(fixture.spread(), FxHashSet::from_iter([pad, fill, push]));
    }

    #[test]
    fn a_leader_that_is_not_refused_keeps_its_follower() {
        let mut fixture = RefusalFixture::new();
        let refused = fixture.parameter("refused");
        let leader = fixture.parameter("leader");
        let follower = fixture.parameter("follower");
        fixture.refusals.follow(follower, leader);
        fixture.refusals.refuse(refused);
        assert_eq!(fixture.spread(), FxHashSet::from_iter([refused]));
    }
}