py_ast/semantic/
generator.rs

1use super::mangle::Mangle;
2use super::*;
3use crate::parse;
4use either::Either;
5use py_declare::mir::IntoIR;
6use py_declare::*;
7use py_lex::PU;
8use terl::*;
9
10py_ir::custom_ir_variable!(pub IR<py_ir::value::Value>);
11
12pub trait Generate<Item: ?Sized> {
13    type Forward;
14
15    fn generate(&mut self, item: &Item) -> Self::Forward;
16}
17
18type Errors = Either<Error, Vec<Error>>;
19
20type ItemsGenerateResult = Result<Vec<Item>, Either<Vec<Error>, Vec<Vec<Error>>>>;
21
22#[derive(Debug, Clone)]
23struct Results<T, E> {
24    inner: Result<Vec<T>, Vec<E>>,
25}
26
27impl<T, E> Default for Results<T, E> {
28    fn default() -> Self {
29        Self { inner: Ok(vec![]) }
30    }
31}
32
33impl<T, E> Results<T, E> {
34    fn new() -> Self {
35        Self::default()
36    }
37
38    fn add_ok(&mut self, item: T) -> Result<(), T> {
39        match &mut self.inner {
40            Ok(state) => {
41                state.push(item);
42                Ok(())
43            }
44            _ => Err(item),
45        }
46    }
47
48    fn add_err(&mut self, err: E) {
49        match &mut self.inner {
50            Ok(_) => self.inner = Err(vec![err]),
51            Err(errs) => errs.push(err),
52        }
53    }
54
55    fn add_result(&mut self, result: Result<T, E>) {
56        match result {
57            Ok(ok) => _ = self.add_ok(ok),
58            Err(err) => self.add_err(err),
59        }
60    }
61
62    fn take(self) -> Result<Vec<T>, Vec<E>> {
63        self.inner
64    }
65}
66
67impl<T, E> Extend<Result<T, E>> for Results<T, E> {
68    fn extend<I>(&mut self, iter: I)
69    where
70        I: IntoIterator<Item = Result<T, E>>,
71    {
72        for item in iter {
73            self.add_result(item);
74        }
75    }
76}
77
78impl<T, E> FromIterator<Result<T, E>> for Results<T, E> {
79    fn from_iter<I>(iter: I) -> Self
80    where
81        I: IntoIterator<Item = Result<T, E>>,
82    {
83        let mut results = Self::new();
84        results.extend(iter);
85        results
86    }
87}
88
89fn fn_define_task<'d, M: Mangle>(
90    define: &mut Defines<M>,
91    fn_define: &'d parse::FnDefine,
92) -> Result<impl FnOnce(&'d Defines<M>) -> Result<FnDefine, Vec<Error>>, Error> {
93    let ty = fn_define.ty.to_mir_ty()?;
94
95    let params = fn_define
96        .params
97        .iter()
98        .try_fold(Vec::new(), |mut vec, pu| {
99            let name = pu.name.to_string();
100            let ty = pu.ty.to_mir_ty()?;
101            vec.push(defs::Parameter { name, ty });
102            Result::Ok(vec)
103        })?;
104
105    let fn_sign = defs::FnSign::new(
106        ty.clone(),
107        params.clone(),
108        fn_define.retty_span,
109        fn_define.sign_span,
110    );
111
112    let mangled_name = define.regist_fn(fn_define, fn_sign)?;
113
114    Ok(|define: &Defines<M>| -> Result<FnDefine, Vec<Error>> {
115        let mut statement_transmuter = {
116            let scopes = BasicScopes::default();
117            let spans = fn_define.params.iter().map(WithSpan::get_span);
118            let fn_scope = FnScope::new(&mangled_name, params.iter(), spans);
119            StatementGenerator::new(&define.defs, fn_scope, scopes)
120        };
121
122        let body = match statement_transmuter.generate(&fn_define.codes) {
123            Err(error) => Err(vec![error]),
124            Ok(body) if !body.returned => {
125                let reason = format!("function `{}` is never return", fn_define.name);
126                let error = fn_define.sign_span.make_error(reason);
127                Err(vec![error])
128            }
129
130            Ok(body) => Ok(body),
131        }?;
132
133        statement_transmuter.fn_scope.declare_map.declare_all()?;
134
135        let export = fn_define.export.is_some();
136        let mir_fn = mir::FnDefine {
137            export,
138            ty,
139            body,
140            params,
141            name: mangled_name,
142        };
143        Ok(mir_fn.into_ir(&statement_transmuter.fn_scope.declare_map))
144    })
145}
146
147#[cfg(feature = "parallel")]
148mod parallel {
149    use super::*;
150    use rayon::prelude::*;
151
152    impl<T, E> FromParallelIterator<Result<T, E>> for Results<T, E>
153    where
154        T: Send + 'static,
155        E: Send + 'static,
156    {
157        fn from_par_iter<I>(iter: I) -> Self
158        where
159            I: IntoParallelIterator<Item = Result<T, E>>,
160        {
161            let (result_s, result_r) = std::sync::mpsc::channel();
162            let state = std::thread::spawn(move || {
163                let mut items = Self::new();
164                while let Ok(result) = result_r.recv() {
165                    items.add_result(result);
166                }
167                items
168            });
169            iter.into_par_iter()
170                .for_each_with(result_s, |sender, item| {
171                    sender.send(item).unwrap();
172                });
173            state.join().unwrap()
174        }
175    }
176
177    impl<M: Mangle> Generate<[parse::Item]> for Defines<M> {
178        type Forward = ItemsGenerateResult;
179
180        fn generate(&mut self, items: &[parse::Item]) -> Self::Forward {
181            items
182                .iter()
183                .filter_map(|item| match item {
184                    parse::Item::FnDefine(fn_define) => Some(fn_define),
185                    parse::Item::Comment(_) => None,
186                })
187                .map(|fn_define| fn_define_task(self, fn_define).map(Box::new))
188                .collect::<Results<_, _>>()
189                .take()
190                .map_err(Either::Left)?
191                .into_par_iter()
192                .map(|task| task(self).map(Into::into))
193                .collect::<Results<_, _>>()
194                .take()
195                .map_err(Either::Right)
196        }
197    }
198}
199
200#[cfg(not(feature = "parallel"))]
201mod normal {
202    use super::*;
203    impl<M: Mangle> Generate<[parse::Item]> for Defines<M> {
204        type Forward = ItemsGenerateResult;
205
206        fn generate(&mut self, items: &[parse::Item]) -> Self::Forward {
207            items
208                .iter()
209                .filter_map(|item| match item {
210                    parse::Item::FnDefine(fn_define) => Some(fn_define),
211                    parse::Item::Comment(_) => None,
212                })
213                .map(|fn_define| fn_define_task(self, fn_define).map(Box::new))
214                .collect::<Results<_, _>>()
215                .take()
216                .map_err(Either::Left)?
217                .into_iter()
218                .map(|task| task(self).map(Into::into))
219                .collect::<Results<_, _>>()
220                .take()
221                .map_err(Either::Right)
222        }
223    }
224}
225
226impl<M: Mangle> Generate<parse::Item> for Defines<M> {
227    type Forward = Result<Option<Item>, Errors>;
228
229    fn generate(&mut self, item: &parse::Item) -> Self::Forward {
230        match item {
231            parse::Item::FnDefine(fn_define) => self.generate(fn_define).map(Into::into).map(Some),
232            parse::Item::Comment(..) => Ok(None),
233        }
234    }
235}
236
237impl<M: Mangle> Generate<parse::FnDefine> for Defines<M> {
238    type Forward = Result<FnDefine, Errors>;
239
240    fn generate(&mut self, fn_define: &parse::FnDefine) -> Self::Forward {
241        fn_define_task(self, fn_define).map_err(Either::Left)?(self).map_err(Either::Right)
242    }
243}
244
245struct StatementGenerator<'w> {
246    pub defs: &'w Defs,
247    pub fn_scope: FnScope,
248    pub scopes: BasicScopes,
249    stmts: mir::Statements,
250}
251
252struct VarDeineLoc(usize);
253
254impl StatementGenerator<'_> {
255    fn new(defs: &Defs, fn_scope: FnScope, scopes: BasicScopes) -> StatementGenerator<'_> {
256        StatementGenerator {
257            defs,
258            fn_scope,
259            scopes,
260            stmts: Default::default(),
261        }
262    }
263
264    #[inline]
265    fn push_stmt(&mut self, stmt: impl Into<mir::Statement>) {
266        self.stmts.push(stmt.into());
267    }
268
269    fn temp_var_define<I>(
270        &mut self,
271        param_ty: GroupIdx,
272        result_ty: GroupIdx,
273        init: I,
274    ) -> ValueHandle
275    where
276        I: Into<mir::AssignValue>,
277    {
278        let init = mir::Undeclared::new(init.into(), param_ty);
279        let temp_name = self.fn_scope.temp_name();
280        let loc = self.push_var_define(mir::VarDefine {
281            ty: param_ty,
282            name: temp_name.clone(),
283            init: Some(init),
284            is_temp: true,
285        });
286        let handle = mir::Undeclared::new(mir::Value::Variable(temp_name), result_ty);
287        ValueHandle::new(loc, handle)
288    }
289
290    fn push_var_define(&mut self, var_define: mir::VarDefine) -> VarDeineLoc {
291        let loc = VarDeineLoc(self.stmts.len());
292        self.stmts.push(mir::Statement::VarDefine(var_define));
293        loc
294    }
295
296    fn rename_var_define(&mut self, loc: VarDeineLoc, new_name: &str) {
297        match &mut self.stmts[loc.0] {
298            py_ir::Statement::VarDefine(define) => {
299                define.name = new_name.to_owned();
300                define.is_temp = false;
301            }
302            _ => unreachable!(),
303        }
304    }
305
306    fn take_stmts(&mut self) -> mir::Statements {
307        std::mem::take(&mut self.stmts)
308    }
309
310    fn replace_stmts(&mut self, new: mir::Statements) -> mir::Statements {
311        std::mem::replace(&mut self.stmts, new)
312    }
313
314    fn search_value(&mut self, name: &str) -> Option<defs::VarDef> {
315        self.fn_scope
316            .search_parameter(name)
317            .or_else(|| self.scopes.search_variable(name))
318    }
319
320    fn in_new_basic_scope<R>(&mut self, active: impl FnOnce(&mut Self) -> R) -> R {
321        self.scopes.push(Default::default());
322        let r = active(self);
323        self.scopes.pop();
324        r
325    }
326}
327
328impl Generate<parse::Statement> for StatementGenerator<'_> {
329    type Forward = Result<Option<mir::Statement>>;
330
331    fn generate(&mut self, stmt: &parse::Statement) -> Self::Forward {
332        match stmt {
333            parse::Statement::VarStoreStmt(stmt) => self.generate(&****stmt).map(Into::into),
334            parse::Statement::If(stmt) => self.generate(&**stmt).map(Into::into),
335            parse::Statement::While(stmt) => self.generate(&**stmt).map(Into::into),
336            parse::Statement::Return(stmt) => self.generate(&**stmt).map(Into::into),
337            parse::Statement::CodeBlock(stmt) => self.generate(&**stmt).map(Into::into),
338            parse::Statement::VarDefineStmt(stmt) => match self.generate(&****stmt)? {
339                Some(var_define) => Ok(var_define.into()),
340                None => return Ok(None),
341            },
342            parse::Statement::FnCallStmt(stmt) => {
343                self.generate(&****stmt)?;
344                return Ok(None);
345            }
346            parse::Statement::Comment(..) => return Ok(None),
347        }
348        .map(Some)
349    }
350}
351
352struct ValueHandle {
353    loc: Option<VarDeineLoc>,
354    handle: mir::Undeclared<mir::Value>,
355}
356
357impl std::ops::Deref for ValueHandle {
358    type Target = mir::Undeclared<mir::Value>;
359
360    fn deref(&self) -> &Self::Target {
361        &self.handle
362    }
363}
364
365impl ValueHandle {
366    fn new(loc: VarDeineLoc, handle: mir::Undeclared<mir::Value>) -> Self {
367        Self {
368            loc: Some(loc),
369            handle,
370        }
371    }
372}
373
374impl From<mir::Undeclared<mir::Value>> for ValueHandle {
375    fn from(handle: mir::Undeclared<mir::Value>) -> Self {
376        Self { loc: None, handle }
377    }
378}
379
380impl Generate<parse::FnCall> for StatementGenerator<'_> {
381    type Forward = Result<ValueHandle>;
382
383    fn generate(&mut self, fn_call: &parse::FnCall) -> Self::Forward {
384        let args = fn_call.args.iter().try_fold(vec![], |mut args, expr| {
385            args.push(self.generate(expr)?.handle);
386            Result::Ok(args)
387        })?;
388
389        let Some(overloads) = self.defs.get_unmangled(&fn_call.fn_name) else {
390            return Err(fn_call.make_error(format!("call undefinded function {}", fn_call.fn_name)));
391        };
392
393        let args_spans = fn_call
394            .args
395            .iter()
396            .map(|pu| pu.get_span())
397            .collect::<Vec<_>>();
398
399        let overload_len_filter =
400            filters::FnParamLen::new(Some(&fn_call.fn_name), args.len(), fn_call.get_span());
401
402        let branch_builder = |overload: &Overload| {
403            let mut branch_builder = BranchesBuilder::new(Type::Overload(overload.clone()));
404            if branch_builder.filter_self(self.defs, &overload_len_filter) {
405                // length of overload.params are equal to arg's
406                for ((param, arg), span) in overload.params.iter().zip(&args).zip(&args_spans) {
407                    let filter = filters::TypeEqual::new(&param.ty, *span);
408                    let declare_map = &mut self.fn_scope.declare_map;
409                    branch_builder = branch_builder.new_depend::<Directly, _>(
410                        declare_map,
411                        self.defs,
412                        arg.ty,
413                        &filter,
414                    );
415                }
416            }
417            branch_builder
418        };
419
420        let branch_builders = overloads.iter().map(branch_builder).collect();
421        let overload = self
422            .fn_scope
423            .declare_map
424            .build_group(GroupBuilder::new(fn_call.get_span(), branch_builders));
425
426        Ok(self.temp_var_define(overload, overload, mir::FnCall { args }))
427    }
428}
429
430impl Generate<parse::VarStore> for StatementGenerator<'_> {
431    type Forward = Result<mir::VarStore>;
432
433    fn generate(&mut self, var_store: &parse::VarStore) -> Self::Forward {
434        let name = var_store.name.to_string();
435        let val = self.generate(&var_store.assign.val)?.handle;
436
437        let val_at = var_store.assign.val.get_span();
438
439        let Some(var_def) = self.search_value(&name) else {
440            return Err(val_at.make_error(format!("use of undefined variable {}", name)));
441        };
442        if !var_def.mutable {
443            return Err(val_at.make_error(format!("cant assign to a immmutable variable {}", name)));
444        }
445
446        self.fn_scope
447            .declare_map
448            .merge_group(val_at, var_def.ty, val.ty);
449
450        Ok(mir::VarStore { name, val })
451    }
452}
453
454impl Generate<parse::VarDefine> for StatementGenerator<'_> {
455    type Forward = Result<Option<mir::VarDefine>>;
456
457    fn generate(&mut self, var_define: &parse::VarDefine) -> Self::Forward {
458        let ty = var_define.ty.to_mir_ty()?;
459        let ty = self
460            .fn_scope
461            .declare_map
462            .new_static_group(var_define.ty.get_span(), std::iter::once(ty.into()));
463        self.scopes
464            .regist_variable(&var_define.name, defs::VarDef { ty, mutable: true });
465
466        let init = match &var_define.init {
467            Some(var_assign) => {
468                let init = self.generate(&var_assign.val)?;
469
470                if let Some(loc) = init.loc {
471                    self.rename_var_define(loc, &var_define.name);
472                    return Ok(None);
473                }
474                let at = var_assign.val.get_span();
475                self.fn_scope.declare_map.merge_group(at, ty, init.ty);
476
477                Some(mir::Undeclared::new(init.handle.val.into(), init.handle.ty))
478            }
479            None => None,
480        };
481
482        let name = var_define.name.to_string();
483        Ok(Some(mir::VarDefine {
484            ty,
485            name,
486            init,
487            is_temp: false,
488        }))
489    }
490}
491
492impl Generate<parse::If> for StatementGenerator<'_> {
493    type Forward = Result<mir::If>;
494
495    fn generate(&mut self, if_: &parse::If) -> Self::Forward {
496        let branches = if_
497            .branches
498            .iter()
499            .try_fold(vec![], |mut branches, branch| {
500                branches.push(self.generate(branch)?);
501                Ok(branches)
502            })?;
503        let else_ = match &if_.else_ {
504            Some(else_) => Some(self.generate(&else_.block)?),
505            None => None,
506        };
507        Ok(mir::If { branches, else_ })
508    }
509}
510
511impl Generate<parse::While> for StatementGenerator<'_> {
512    type Forward = Result<mir::While>;
513
514    fn generate(&mut self, while_: &parse::While) -> Self::Forward {
515        let cond = self.generate(&while_.conds)?;
516        let body = self.generate(&while_.block)?;
517        Ok(mir::While { cond, body })
518    }
519}
520
521impl Generate<parse::IfBranch> for StatementGenerator<'_> {
522    type Forward = Result<mir::IfBranch>;
523
524    fn generate(&mut self, branch: &parse::IfBranch) -> Self::Forward {
525        let cond = self.generate(&branch.conds)?;
526        let body = self.generate(&branch.body)?;
527        Ok(mir::IfBranch { cond, body })
528    }
529}
530
531impl Generate<parse::Return> for StatementGenerator<'_> {
532    type Forward = Result<mir::Return>;
533
534    fn generate(&mut self, ret: &parse::Return) -> Self::Forward {
535        let val = match &ret.val {
536            Some(expr) => {
537                let val = self.generate(expr)?;
538                let mangled_fn = self.defs.get_mangled(&self.fn_scope.fn_name);
539                self.fn_scope
540                    .declare_map
541                    .declare_type(expr.get_span(), val.ty, &mangled_fn.ty);
542                Some(val.handle)
543            }
544            None => None,
545        };
546        Ok(mir::Return { val })
547    }
548}
549
550impl Generate<parse::CodeBlock> for StatementGenerator<'_> {
551    type Forward = Result<mir::Statements>;
552
553    fn generate(&mut self, item: &parse::CodeBlock) -> Self::Forward {
554        self.in_new_basic_scope(|g| {
555            let current_scope = g.take_stmts();
556            for stmt in &item.stmts {
557                if let Some(stmt) = g.generate(stmt)? {
558                    g.push_stmt(stmt);
559                }
560            }
561            Ok(g.replace_stmts(current_scope))
562        })
563    }
564}
565
566impl Generate<parse::Conditions> for StatementGenerator<'_> {
567    type Forward = Result<mir::Condition>;
568
569    fn generate(&mut self, conds: &parse::Conditions) -> Self::Forward {
570        let (compute, val) = self.in_new_basic_scope(|g| {
571            let mut last_condition = g.generate(&conds[0])?;
572            for arg in conds.iter().skip(1) {
573                last_condition = g.generate(arg)?;
574            }
575            Ok((g.take_stmts(), last_condition.handle))
576        })?;
577
578        // type check
579        let bool = py_ir::types::PrimitiveType::Bool.into();
580        let last_cond_span = conds.last().unwrap().get_span();
581        self.fn_scope
582            .declare_map
583            .declare_type(last_cond_span, val.ty, &bool);
584        Ok(mir::Condition { val, compute })
585    }
586}
587
588impl Generate<parse::Expr> for StatementGenerator<'_> {
589    type Forward = Result<ValueHandle>;
590
591    fn generate(&mut self, expr: &parse::Expr) -> Self::Forward {
592        let mut vals = Vec::new();
593        for item in expr.iter() {
594            match item {
595                parse::ExprItem::AtomicExpr(atomic) => vals.push(self.generate(atomic)?),
596                parse::ExprItem::Operators(op) => match op.associativity() {
597                    py_lex::ops::OperatorAssociativity::Binary => {
598                        let r = vals.pop().unwrap();
599                        let l = vals.pop().unwrap();
600                        self.fn_scope
601                            .declare_map
602                            .merge_group(expr.get_span(), l.ty, r.ty);
603                        use py_ir::types::PrimitiveType;
604                        use py_lex::ops::OperatorTypes::CompareOperator;
605
606                        // for compare operators(like == != < >), the result will be a boolean value,
607                        // not parameters' type
608                        let param_ty = l.ty;
609                        let result_ty = if op.op_ty() == CompareOperator {
610                            self.fn_scope
611                                .declare_map
612                                .new_static_group(expr.get_span(), [PrimitiveType::Bool.into()])
613                        } else {
614                            l.ty
615                        };
616
617                        let init = mir::Operate::Binary(**op, l.handle, r.handle);
618                        vals.push(self.temp_var_define(param_ty, result_ty, init));
619                    }
620                    py_lex::ops::OperatorAssociativity::Unary => {
621                        let v = vals.pop().unwrap();
622                        let ty = v.ty;
623
624                        let init = mir::Operate::Unary(**op, v.handle);
625                        vals.push(self.temp_var_define(ty, ty, init));
626                    }
627
628                    py_lex::ops::OperatorAssociativity::None => unreachable!(),
629                },
630            }
631        }
632        vals.pop().ok_or_else(|| unreachable!())
633    }
634}
635
636impl Generate<PU<parse::AtomicExpr>> for StatementGenerator<'_> {
637    type Forward = Result<ValueHandle>;
638
639    fn generate(&mut self, atomic: &PU<parse::AtomicExpr>) -> Self::Forward {
640        let literal = match &**atomic {
641            // atomics
642            // 解析
643            parse::AtomicExpr::CharLiteral(char) => py_ir::value::Literal::Char(char.parsed),
644            parse::AtomicExpr::NumberLiteral(n) => match n {
645                parse::NumberLiteral::Float(number) => py_ir::value::Literal::Float(*number),
646                parse::NumberLiteral::Digit(number) => py_ir::value::Literal::Integer(*number),
647            },
648
649            parse::AtomicExpr::StringLiteral(_str) => {
650                // TODO: init for array
651                todo!("a VarDefine statement will be generate...")
652            }
653            parse::AtomicExpr::FnCall(fn_call) => return self.generate(fn_call),
654            parse::AtomicExpr::Variable(name) => {
655                let Some(def) = self.search_value(name) else {
656                    return Err(atomic.make_error("use of undefined variable"));
657                };
658
659                let val = mir::Value::Variable(name.to_string());
660                return Ok(mir::Undeclared::new(val, def.ty).into());
661            }
662            parse::AtomicExpr::Array(ref _array) => {
663                // elements in arrray must be same type
664                todo!()
665            }
666        };
667
668        let ty = self.fn_scope.declare_map.build_group({
669            let branches = mir::Undeclared::literal_branches(&literal);
670            GroupBuilder::new(atomic.get_span(), branches)
671        });
672        Ok(mir::Undeclared::new(literal.into(), ty).into())
673    }
674}
py_ast/semantic/generator.rs

py_ast/semantic/
generator.rs
