lutra-compiler 0.6.0

Compiler for Lutra query 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
128
129
130
131
132
133
134
135
136
137
138
139
140
141

use crate::diagnostic::{Diagnostic, WithErrorInfo};
use crate::pr;
use crate::utils::toposort;
use crate::{Project, Result};

/// Checks project for bad recursive type references
/// and computes [pr::Ty::variants_force_ptr].
// #[tracing::instrument(skip_all, name = "recursive_check")]
pub fn check(mut project: Project) -> Result<Project, Vec<Diagnostic>> {
    let mut diagnostics = Vec::new();

    for group in &project.ordering {
        // task 1: mark all potentially recursive enum variants
        for ident in group {
            let def = project.root_module.get_mut(ident).unwrap();
            let pr::DefKind::Ty(ty_def) = &mut def.kind else {
                continue;
            };
            mark_recursive(&mut ty_def.ty, group);
        }

        // task2: find bad recursive references

        // collect refs between group members
        // (these refs include only refs that affect type layout)
        let mut deps = Vec::with_capacity(group.len());
        for ident in group {
            let def = project.root_module.get(ident).unwrap();
            let pr::DefKind::Ty(ty_def) = &def.kind else {
                continue;
            };

            let mut refs = Vec::new();
            collect_refs(&ty_def.ty, &mut refs);

            if refs.contains(ident) {
                diagnostics.push(
                    Diagnostic::new_custom("type has infinite size")
                        .with_span(def.span)
                        .push_hint("self references are allowed only from within arrays or enums"),
                );
            }

            deps.push((ident.clone(), refs));
        }

        let order = toposort(&deps);

        for subgroup in order {
            if subgroup.len() == 1 {
                continue;
            }
            let def = project.root_module.get(subgroup[0]).unwrap();
            diagnostics.push(
                Diagnostic::new_custom("type has infinite size")
                    .with_span(def.span)
                    .push_hint("recursive references are allowed only from within arrays or enums"),
            );
        }
    }

    if !diagnostics.is_empty() {
        Err(diagnostics)
    } else {
        Ok(project)
    }
}

/// Returns true for types whose layout depends on layout of some type-def from current group.
fn mark_recursive(ty: &mut pr::Ty, group: &[pr::Path]) -> bool {
    match &mut ty.kind {
        pr::TyKind::Ident(_) => {
            let target = ty.target.as_ref().unwrap();
            let pr::Ref::Global(fq) = target else {
                return false;
            };

            group.contains(fq)
        }
        pr::TyKind::Primitive(_) => false,
        pr::TyKind::Tuple(fields) => {
            // tuples don't have pointers, so they propagate is_recursive status
            let mut is_recursive = false;
            for f in fields {
                if mark_recursive(&mut f.ty, group) {
                    is_recursive = true;
                }
            }
            is_recursive
        }
        pr::TyKind::Array(_) => {
            // arrays have an pointer, so they are never recursive
            false
        }
        pr::TyKind::Option(_) => unreachable!(), // desugared
        pr::TyKind::Enum(variants) => {
            // enums: the interesting part

            for (i, variant) in variants.iter_mut().enumerate() {
                let is_recursive = mark_recursive(&mut variant.ty, group);

                if is_recursive {
                    ty.variants_force_ptr.push(i as u16);
                }
            }

            false
        }
        pr::TyKind::Func(_) => false,
        pr::TyKind::TupleComprehension(_) => false, // ???
    }
}

fn collect_refs(ty: &pr::Ty, refs: &mut Vec<pr::Path>) {
    match &ty.kind {
        pr::TyKind::Ident(_) => {
            let target = ty.target.as_ref().unwrap();
            let pr::Ref::Global(fq) = target else {
                return;
            };

            refs.push(fq.clone());
        }
        pr::TyKind::Primitive(_) => {}
        pr::TyKind::Tuple(fields) => {
            // tuples don't have pointers, so they always depend on layout of inner type
            for f in fields {
                collect_refs(&f.ty, refs);
            }
        }
        pr::TyKind::Array(_) => {
            // arrays have an pointer, so their layout never depends on the inner type
        }
        pr::TyKind::Option(_) => unreachable!(), // desugared
        pr::TyKind::Enum(_) => {
            // enums have a pointer (if we will determine it is needed)
        }
        pr::TyKind::Func(_) => {}
        pr::TyKind::TupleComprehension(_) => {} // ???
    }
}