stav 0.1.0

A statically typed, eager and total configuration language
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
127

//! The call graph: no function may call itself, directly or through other
//! functions, top-level `let` values or the defaults of types.

use std::collections::BTreeMap;

use super::Checker;
use super::decls::GlobalKind;
use super::graph;
use super::load::FileId;
use super::types::{GlobalId, StructId, SumId};
use crate::diagnostic::Diagnostic;
use crate::span::Span;

/// A declaration whose evaluation may evaluate other declarations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) enum Node {
    /// A top-level function or `let`.
    Global(GlobalId),
    /// The field defaults of a struct, evaluated when a complete value of
    /// the struct is built.
    StructDefaults(StructId),
    /// The payload defaults of a sum type, evaluated when a variant is
    /// built.
    SumDefaults(SumId),
}

/// The edges of the call graph, each with the place of its first
/// occurrence.
#[derive(Debug, Clone, Default)]
pub(crate) struct CallGraph {
    pub(crate) edges: BTreeMap<(Node, Node), (FileId, Span)>,
}

impl CallGraph {
    /// Records that evaluating `from` may evaluate `to`.
    pub(crate) fn depend(&mut self, from: Node, to: Node, file: FileId, span: Span) {
        self.edges.entry((from, to)).or_insert((file, span));
    }
}

impl Checker<'_> {
    fn node_index(&self, node: Node) -> usize {
        let (globals, structs) = (self.globals.len(), self.types.structs.len());
        match node {
            Node::Global(g) => g.index(),
            Node::StructDefaults(s) => globals + s.index(),
            Node::SumDefaults(s) => globals + structs + s.index(),
        }
    }

    fn index_node(&self, index: usize) -> Node {
        let (globals, structs) = (self.globals.len(), self.types.structs.len());
        if index < globals {
            Node::Global(GlobalId::new(index))
        } else if index < globals + structs {
            Node::StructDefaults(StructId::new(index - globals))
        } else {
            Node::SumDefaults(SumId::new(index - globals - structs))
        }
    }

    fn node_name(&self, node: Node) -> String {
        match node {
            Node::Global(g) => format!("`{}`", self.globals[g.index()].name),
            Node::StructDefaults(s) => {
                format!("the defaults of `{}`", self.types.structure(s).name)
            }
            Node::SumDefaults(s) => format!("the defaults of `{}`", self.types.sum(s).name),
        }
    }

    /// Reports cycles of the call graph and orders the top-level `let`
    /// declarations so that each comes after everything it uses.
    pub(super) fn check_totality(&mut self) {
        let total = self.globals.len() + self.types.structs.len() + self.types.sums.len();
        let mut adj = vec![Vec::new(); total];
        for &(from, to) in self.calls.edges.keys() {
            adj[self.node_index(from)].push(self.node_index(to));
        }
        for list in &mut adj {
            list.sort_unstable();
            list.dedup();
        }
        for cycle in graph::cycles(&adj) {
            let nodes: Vec<Node> = cycle.iter().map(|&i| self.index_node(i)).collect();
            let is_let = |n: &Node| match n {
                Node::Global(g) => matches!(self.globals[g.index()].kind, GlobalKind::Let(_)),
                _ => false,
            };
            let named = nodes.iter().position(is_let);
            let at = named.unwrap_or(0);
            let (from, to) = (nodes[at], nodes[(at + 1) % nodes.len()]);
            let Some(&(file, span)) = self.calls.edges.get(&(from, to)) else {
                continue;
            };
            let mut chain: Vec<String> = nodes.iter().map(|n| self.node_name(*n)).collect();
            chain.push(self.node_name(nodes[0]));
            let note = format!("cycle: {}", chain.join(" -> "));
            let diagnostic = if named.is_some() {
                Diagnostic::error(
                    "E0305",
                    span,
                    format!("{} depends on itself", self.node_name(from)),
                )
                .with_note(note)
            } else {
                let message = if nodes.len() == 1 {
                    format!("{} calls itself", self.node_name(from))
                } else {
                    "functions may not call each other in a cycle".to_owned()
                };
                Diagnostic::error("E0610", span, message)
                    .with_note(note)
                    .with_note("evaluation must terminate, so functions cannot recurse")
                    .with_help("iterate with `fold` over `range(...)`, for example `fold(range(1, n + 1), 1, fn(acc: Int, i: Int) = acc * i)`")
            };
            self.error(file, diagnostic);
        }
        self.let_order = graph::components(&adj)
            .into_iter()
            .flatten()
            .filter(|&i| i < self.globals.len())
            .map(GlobalId::new)
            .filter(|g| matches!(self.globals[g.index()].kind, GlobalKind::Let(_)))
            .collect();
    }
}