cairo-lang-lowering 2.21.0

Cairo lowering phase.
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

use std::cmp::Ordering;

use cairo_lang_defs::stable_order::{cmp_elements, cmp_nodes};
use cairo_lang_semantic::stable_order::{StableOrd, cmp_slices};
use cairo_lang_syntax::node::TypedStablePtr;
use cairo_lang_utils::graph_algos::strongly_connected_components::compute_scc;
use salsa::Database;

use super::concrete_function_node::ConcreteFunctionWithBodyNode;
use crate::db::{ConcreteSCCRepresentative, LoweringGroup};
use crate::ids::{
    ConcreteFunctionWithBodyId, ConcreteFunctionWithBodyLongId, GeneratedFunctionKey,
};
use crate::specialization::SpecializationArg;
use crate::{DependencyType, LoweringStage};

/// Query implementation of
/// [crate::db::LoweringGroup::lowered_scc_representative].
#[salsa::tracked(returns(clone))]
pub fn lowered_scc_representative<'db>(
    db: &'db dyn Database,
    function: ConcreteFunctionWithBodyId<'db>,
    dependency_type: DependencyType,
    stage: LoweringStage,
) -> ConcreteSCCRepresentative<'db> {
    ConcreteSCCRepresentative(
        db.lowered_scc(function, dependency_type, stage)
            .into_iter()
            .min_by(|a, b| a.stable_cmp(b, db))
            .unwrap_or(function),
    )
}

/// Query implementation of [crate::db::LoweringGroup::lowered_scc].
#[salsa::tracked(returns(clone))]
pub fn lowered_scc<'db>(
    db: &'db dyn Database,
    function_id: ConcreteFunctionWithBodyId<'db>,
    dependency_type: DependencyType,
    stage: LoweringStage,
) -> Vec<ConcreteFunctionWithBodyId<'db>> {
    compute_scc(&ConcreteFunctionWithBodyNode { function_id, db, dependency_type, stage })
}

/// Lowering functions are ordered by the semantic function they come from, then by kind, so a
/// function precedes the functions generated from it, and those precede its specializations.
impl<'db> StableOrd<'db> for ConcreteFunctionWithBodyId<'db> {
    fn stable_cmp(&self, other: &Self, db: &'db dyn Database) -> Ordering {
        use ConcreteFunctionWithBodyLongId::*;
        let kind = |function: &ConcreteFunctionWithBodyLongId<'db>| match function {
            Semantic(_) => 0,
            Generated(_) => 1,
            Specialized(_) => 2,
        };
        let (a, b) = (self.long(db), other.long(db));
        a.base_semantic_function(db)
            .stable_cmp(&b.base_semantic_function(db), db)
            .then_with(|| kind(a).cmp(&kind(b)))
            .then_with(|| match (a, b) {
                (Generated(a), Generated(b)) => a.key.stable_cmp(&b.key, db),
                (Specialized(a), Specialized(b)) => {
                    let (a, b) = (a.long(db), b.long(db));
                    a.base.stable_cmp(&b.base, db).then_with(|| cmp_slices(db, &a.args, &b.args))
                }
                _ => Ordering::Equal,
            })
    }
}

/// Loops precede trait functions; each is compared by the syntax it is generated for.
impl<'db> StableOrd<'db> for GeneratedFunctionKey<'db> {
    fn stable_cmp(&self, other: &Self, db: &'db dyn Database) -> Ordering {
        use GeneratedFunctionKey::*;
        match (self, other) {
            (Loop(a), Loop(b)) => cmp_nodes(db, a.untyped(), b.untyped()),
            (TraitFunc(a_function, a), TraitFunc(b_function, b)) => {
                cmp_nodes(db, a.stable_ptr(), b.stable_ptr())
                    .then_with(|| cmp_elements(db, a_function, b_function))
            }
            (Loop(_), TraitFunc(..)) => Ordering::Less,
            (TraitFunc(..), Loop(_)) => Ordering::Greater,
        }
    }
}

/// Compared by variant, then by the specialized values.
impl<'db> StableOrd<'db> for SpecializationArg<'db> {
    fn stable_cmp(&self, other: &Self, db: &'db dyn Database) -> Ordering {
        use SpecializationArg::*;
        let kind = |arg: &Self| match arg {
            Const { .. } => 0,
            Snapshot(_) => 1,
            Array(..) => 2,
            Struct(_) => 3,
            Enum { .. } => 4,
            NotSpecialized => 5,
        };
        match (self, other) {
            (Const { value: a, boxed: a_boxed }, Const { value: b, boxed: b_boxed }) => {
                a.stable_cmp(b, db).then_with(|| a_boxed.cmp(b_boxed))
            }
            (Snapshot(a), Snapshot(b)) => a.stable_cmp(b, db),
            (Array(a_ty, a), Array(b_ty, b)) => {
                a_ty.stable_cmp(b_ty, db).then_with(|| cmp_slices(db, a, b))
            }
            (Struct(a), Struct(b)) => cmp_slices(db, a, b),
            (Enum { variant: a, payload: a_payload }, Enum { variant: b, payload: b_payload }) => {
                a.stable_cmp(b, db).then_with(|| a_payload.stable_cmp(b_payload, db))
            }
            (NotSpecialized, NotSpecialized) => Ordering::Equal,
            (a, b) => kind(a).cmp(&kind(b)),
        }
    }
}