pag_parser/type_system/
mod.rs

1// Copyright (c) 2023 Paguroidea Developers
2//
3// Licensed under the Apache License, Version 2.0
4// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
5// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. All files in the project carrying such notice may not be copied,
7// modified, or distributed except according to those terms.
8
9use crate::core_syntax::{BindingContext, Term};
10use crate::frontend::WithSpan;
11use crate::utilities::Symbol;
12use std::collections::HashSet;
13use std::fmt::Debug;
14use std::vec;
15
16use crate::type_system::context::TypeContext;
17use pest::Span;
18use thiserror::Error;
19
20use self::binding_proxy::BindingProxy;
21
22pub mod binding_proxy;
23pub mod context;
24
25#[derive(Error, Debug)]
26pub enum TypeError<'a> {
27    #[error("sequential uniqueness requirement volidation")]
28    SequentialUniquenessViolation {
29        lhs: (Span<'a>, Type<'a>),
30        rhs: (Span<'a>, Type<'a>),
31        total: Span<'a>,
32    },
33    #[error("disjunctive uniqueness requirement volidation")]
34    DisjunctiveUniquenessViolation {
35        lhs: (Span<'a>, Type<'a>),
36        rhs: (Span<'a>, Type<'a>),
37        total: Span<'a>,
38    },
39    #[error("unguarded fixpoint {0}")]
40    UnguardedFixpoint(Symbol<'a>, Span<'a>),
41    #[error("unresolved reference {0}")]
42    UnresolvedReference(Symbol<'a>, Span<'a>),
43}
44
45#[derive(PartialEq, Eq, Debug, Clone)]
46pub struct Type<'src> {
47    pub first: HashSet<Symbol<'src>>,
48    pub follow: HashSet<Symbol<'src>>,
49    pub nullable: bool,
50    pub guarded: bool,
51}
52
53impl<'src> Type<'src> {
54    fn sequential_uniqueness(&self, other: &Self) -> bool {
55        !self.nullable && self.follow.is_disjoint(&other.first)
56    }
57    fn disjunctive_uniqueness(&self, other: &Self) -> bool {
58        !(self.nullable && other.nullable) && self.first.is_disjoint(&other.first)
59    }
60    fn epsilon() -> Self {
61        Self {
62            first: HashSet::new(),
63            follow: HashSet::new(),
64            nullable: true,
65            guarded: true,
66        }
67    }
68    fn token(token: Symbol<'src>) -> Self {
69        Self {
70            first: HashSet::from([token]),
71            follow: HashSet::new(),
72            nullable: false,
73            guarded: true,
74        }
75    }
76
77    fn sequence(
78        t1: &Self,
79        t2: &Self,
80        lhs: Span<'src>,
81        rhs: Span<'src>,
82        total: Span<'src>,
83    ) -> Result<Self, Box<TypeError<'src>>> {
84        if t1.sequential_uniqueness(t2) {
85            Ok(Self {
86                first: t1.first.clone(),
87                follow: if t2.nullable {
88                    t2.follow
89                        .union(&t2.first)
90                        .chain(t1.follow.iter())
91                        .cloned()
92                        .collect()
93                } else {
94                    t2.follow.clone()
95                },
96                nullable: false,
97                guarded: t1.guarded,
98            })
99        } else {
100            // it is fine to return large error here, they will be stored in vectors anyway
101            Err(Box::new(TypeError::SequentialUniquenessViolation {
102                lhs: (lhs, t1.clone()),
103                rhs: (rhs, t2.clone()),
104                total,
105            }))
106        }
107    }
108    fn bottom() -> Self {
109        Self {
110            first: HashSet::new(),
111            follow: HashSet::new(),
112            nullable: false,
113            guarded: true,
114        }
115    }
116
117    fn alternative(
118        t1: &Self,
119        t2: &Self,
120        lhs: Span<'src>,
121        rhs: Span<'src>,
122        total: Span<'src>,
123    ) -> Result<Self, Box<TypeError<'src>>> {
124        if t1.disjunctive_uniqueness(t2) {
125            Ok(Self {
126                first: t1.first.union(&t2.first).cloned().collect(),
127                follow: t1.follow.union(&t2.follow).cloned().collect(),
128                nullable: t1.nullable || t2.nullable,
129                guarded: t1.guarded && t2.guarded,
130            })
131        } else {
132            // it is fine to return large error here, they will be stored in vectors anyway
133            Err(Box::new(TypeError::DisjunctiveUniquenessViolation {
134                lhs: (lhs, t1.clone()),
135                rhs: (rhs, t2.clone()),
136                total,
137            }))
138        }
139    }
140    fn minimum() -> Self {
141        Self {
142            first: HashSet::new(),
143            follow: HashSet::new(),
144            nullable: false,
145            guarded: false,
146        }
147    }
148    fn fixpoint<F>(mut f: F) -> (Self, Vec<TypeError<'src>>)
149    where
150        F: FnMut(&Self) -> (Self, Vec<TypeError<'src>>),
151    {
152        let mut last = Self::minimum();
153        loop {
154            let (next, errs) = f(&last);
155            if !errs.is_empty() || next == last {
156                return (next, errs);
157            }
158            last = next;
159        }
160    }
161}
162
163fn type_check_impl<'src, 'a>(
164    typing_ctx: &mut TypeContext<'src>,
165    binding_ctx: &mut BindingProxy<'src, 'a>,
166    term: &'a WithSpan<'src, Term<'src, 'a>>,
167) -> (Type<'src>, Vec<TypeError<'src>>) {
168    match &term.node {
169        Term::Epsilon => (Type::epsilon(), vec![]),
170        Term::Sequence(x, y) => {
171            let (x_type, x_errors) = type_check_impl(typing_ctx, binding_ctx, x);
172            let (y_type, y_errors) = typing_ctx.guarded(|ctx| type_check_impl(ctx, binding_ctx, y));
173            let (r#type, err) = match Type::sequence(&x_type, &y_type, x.span, y.span, term.span) {
174                Ok(r#type) => (r#type, None),
175                Err(err) => (Type::bottom(), Some(err)),
176            };
177            (
178                r#type,
179                x_errors
180                    .into_iter()
181                    .chain(y_errors)
182                    .chain(err.map(|e| *e))
183                    .collect(),
184            )
185        }
186        Term::LexerRef(name) => (Type::token(*name), vec![]),
187        Term::Bottom => (Type::bottom(), vec![]),
188        Term::Alternative(x, y) => {
189            let (x_type, x_errors) = type_check_impl(typing_ctx, binding_ctx, x);
190            let (y_type, y_errors) = type_check_impl(typing_ctx, binding_ctx, y);
191            let (r#type, err) = match Type::alternative(&x_type, &y_type, x.span, y.span, term.span)
192            {
193                Ok(r#type) => (r#type, None),
194                Err(err) => (Type::bottom(), Some(err)),
195            };
196            (
197                r#type,
198                x_errors
199                    .into_iter()
200                    .chain(y_errors)
201                    .chain(err.map(|e| *e))
202                    .collect(),
203            )
204        }
205        Term::ParserRef(name) => {
206            // first check if name is already typed in the context.
207            // if so return that type directly.
208            if let Some(ty) = typing_ctx.lookup(*name) {
209                return (ty.as_ref().clone(), vec![]);
210            }
211            // otherwise, we need to type check the parser definition.
212            if let Some(target) = binding_ctx.lookup(name) {
213                // we should not cache the result, since it can be recursive and changed during the calculation of the fixpoint.
214                let (r#type, errors) = binding_ctx.with_hiding(*name, |binding_ctx| {
215                    type_check_impl(typing_ctx, binding_ctx, target)
216                });
217                (r#type, errors)
218            } else {
219                (
220                    Type::bottom(),
221                    vec![TypeError::UnresolvedReference(*name, term.span)],
222                )
223            }
224        }
225        Term::Fix(var, body) => {
226            if let Some(ty) = typing_ctx.lookup(*var) {
227                return (ty.as_ref().clone(), vec![]);
228            }
229            let (r#type, errs) = Type::fixpoint(|x| {
230                typing_ctx.with(*var, x.clone(), |ctx| {
231                    type_check_impl(ctx, binding_ctx, body)
232                })
233            });
234            if !errs.is_empty() {
235                return (r#type, errs);
236            }
237            if r#type.guarded {
238                typing_ctx.with(*var, r#type.clone(), |ctx| {
239                    type_check_impl(ctx, binding_ctx, body)
240                })
241            } else {
242                (
243                    Type::bottom(),
244                    vec![TypeError::UnguardedFixpoint(*var, term.span)],
245                )
246            }
247        }
248    }
249}
250
251pub fn type_check<'src, 'a>(
252    binding_ctx: &BindingContext<'src, 'a>,
253    term: &'a WithSpan<'src, Term<'src, 'a>>,
254    name: Symbol<'src>,
255) -> Vec<TypeError<'src>> {
256    let mut typing_ctx = TypeContext::new();
257    let mut proxy = BindingProxy::proxy(binding_ctx);
258    proxy.with_hiding(name, |binding_ctx| {
259        type_check_impl(&mut typing_ctx, binding_ctx, term).1
260    })
261}
pag_parser/type_system/mod.rs

pag_parser/type_system/
mod.rs
