cairo_lang_lowering/graph_algorithms/
strongly_connected_components.rs

1use std::cmp::Ordering;
2
3use cairo_lang_defs::stable_order::{cmp_elements, cmp_nodes};
4use cairo_lang_semantic::stable_order::{StableOrd, cmp_slices};
5use cairo_lang_syntax::node::TypedStablePtr;
6use cairo_lang_utils::graph_algos::strongly_connected_components::compute_scc;
7use salsa::Database;
8
9use super::concrete_function_node::ConcreteFunctionWithBodyNode;
10use crate::db::{ConcreteSCCRepresentative, LoweringGroup};
11use crate::ids::{
12    ConcreteFunctionWithBodyId, ConcreteFunctionWithBodyLongId, GeneratedFunctionKey,
13};
14use crate::specialization::SpecializationArg;
15use crate::{DependencyType, LoweringStage};
16
17/// Query implementation of
18/// [crate::db::LoweringGroup::lowered_scc_representative].
19#[salsa::tracked(returns(clone))]
20pub fn lowered_scc_representative<'db>(
21    db: &'db dyn Database,
22    function: ConcreteFunctionWithBodyId<'db>,
23    dependency_type: DependencyType,
24    stage: LoweringStage,
25) -> ConcreteSCCRepresentative<'db> {
26    ConcreteSCCRepresentative(
27        db.lowered_scc(function, dependency_type, stage)
28            .into_iter()
29            .min_by(|a, b| a.stable_cmp(b, db))
30            .unwrap_or(function),
31    )
32}
33
34/// Query implementation of [crate::db::LoweringGroup::lowered_scc].
35#[salsa::tracked(returns(clone))]
36pub fn lowered_scc<'db>(
37    db: &'db dyn Database,
38    function_id: ConcreteFunctionWithBodyId<'db>,
39    dependency_type: DependencyType,
40    stage: LoweringStage,
41) -> Vec<ConcreteFunctionWithBodyId<'db>> {
42    compute_scc(&ConcreteFunctionWithBodyNode { function_id, db, dependency_type, stage })
43}
44
45/// Lowering functions are ordered by the semantic function they come from, then by kind, so a
46/// function precedes the functions generated from it, and those precede its specializations.
47impl<'db> StableOrd<'db> for ConcreteFunctionWithBodyId<'db> {
48    fn stable_cmp(&self, other: &Self, db: &'db dyn Database) -> Ordering {
49        use ConcreteFunctionWithBodyLongId::*;
50        let kind = |function: &ConcreteFunctionWithBodyLongId<'db>| match function {
51            Semantic(_) => 0,
52            Generated(_) => 1,
53            Specialized(_) => 2,
54        };
55        let (a, b) = (self.long(db), other.long(db));
56        a.base_semantic_function(db)
57            .stable_cmp(&b.base_semantic_function(db), db)
58            .then_with(|| kind(a).cmp(&kind(b)))
59            .then_with(|| match (a, b) {
60                (Generated(a), Generated(b)) => a.key.stable_cmp(&b.key, db),
61                (Specialized(a), Specialized(b)) => {
62                    let (a, b) = (a.long(db), b.long(db));
63                    a.base.stable_cmp(&b.base, db).then_with(|| cmp_slices(db, &a.args, &b.args))
64                }
65                _ => Ordering::Equal,
66            })
67    }
68}
69
70/// Loops precede trait functions; each is compared by the syntax it is generated for.
71impl<'db> StableOrd<'db> for GeneratedFunctionKey<'db> {
72    fn stable_cmp(&self, other: &Self, db: &'db dyn Database) -> Ordering {
73        use GeneratedFunctionKey::*;
74        match (self, other) {
75            (Loop(a), Loop(b)) => cmp_nodes(db, a.untyped(), b.untyped()),
76            (TraitFunc(a_function, a), TraitFunc(b_function, b)) => {
77                cmp_nodes(db, a.stable_ptr(), b.stable_ptr())
78                    .then_with(|| cmp_elements(db, a_function, b_function))
79            }
80            (Loop(_), TraitFunc(..)) => Ordering::Less,
81            (TraitFunc(..), Loop(_)) => Ordering::Greater,
82        }
83    }
84}
85
86/// Compared by variant, then by the specialized values.
87impl<'db> StableOrd<'db> for SpecializationArg<'db> {
88    fn stable_cmp(&self, other: &Self, db: &'db dyn Database) -> Ordering {
89        use SpecializationArg::*;
90        let kind = |arg: &Self| match arg {
91            Const { .. } => 0,
92            Snapshot(_) => 1,
93            Array(..) => 2,
94            Struct(_) => 3,
95            Enum { .. } => 4,
96            NotSpecialized => 5,
97        };
98        match (self, other) {
99            (Const { value: a, boxed: a_boxed }, Const { value: b, boxed: b_boxed }) => {
100                a.stable_cmp(b, db).then_with(|| a_boxed.cmp(b_boxed))
101            }
102            (Snapshot(a), Snapshot(b)) => a.stable_cmp(b, db),
103            (Array(a_ty, a), Array(b_ty, b)) => {
104                a_ty.stable_cmp(b_ty, db).then_with(|| cmp_slices(db, a, b))
105            }
106            (Struct(a), Struct(b)) => cmp_slices(db, a, b),
107            (Enum { variant: a, payload: a_payload }, Enum { variant: b, payload: b_payload }) => {
108                a.stable_cmp(b, db).then_with(|| a_payload.stable_cmp(b_payload, db))
109            }
110            (NotSpecialized, NotSpecialized) => Ordering::Equal,
111            (a, b) => kind(a).cmp(&kind(b)),
112        }
113    }
114}
cairo_lang_lowering/graph_algorithms/strongly_connected_components.rs

cairo_lang_lowering/graph_algorithms/
strongly_connected_components.rs
