cairo_lang_lowering/graph_algorithms/
strongly_connected_components.rs

1use cairo_lang_defs::ids::UnstableSalsaId;
2use cairo_lang_utils::graph_algos::strongly_connected_components::compute_scc;
3use salsa::Database;
4
5use super::concrete_function_node::ConcreteFunctionWithBodyNode;
6use crate::db::{ConcreteSCCRepresentative, LoweringGroup};
7use crate::ids::ConcreteFunctionWithBodyId;
8use crate::{DependencyType, LoweringStage};
9
10/// Query implementation of
11/// [crate::db::LoweringGroup::lowered_scc_representative].
12#[salsa::tracked]
13pub fn lowered_scc_representative<'db>(
14    db: &'db dyn Database,
15    function: ConcreteFunctionWithBodyId<'db>,
16    dependency_type: DependencyType,
17    stage: LoweringStage,
18) -> ConcreteSCCRepresentative<'db> {
19    ConcreteSCCRepresentative(
20        db.lowered_scc(function, dependency_type, stage)
21            .into_iter()
22            .min_by(|x, y| x.get_internal_id().cmp(&y.get_internal_id()))
23            .unwrap_or(function),
24    )
25}
26
27/// Query implementation of [crate::db::LoweringGroup::lowered_scc].
28#[salsa::tracked]
29pub fn lowered_scc<'db>(
30    db: &'db dyn Database,
31    function_id: ConcreteFunctionWithBodyId<'db>,
32    dependency_type: DependencyType,
33    stage: LoweringStage,
34) -> Vec<ConcreteFunctionWithBodyId<'db>> {
35    compute_scc(&ConcreteFunctionWithBodyNode { function_id, db, dependency_type, stage })
36}