cm_graph/
lib.rs

Help
1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use directed_graph::DirectedGraph;
6use fidl_fuchsia_component_decl as fdecl;
7use std::fmt;
8
9#[cfg(fuchsia_api_level_at_least = "25")]
10macro_rules! get_source_dictionary {
11    ($decl:ident) => {
12        $decl.source_dictionary.as_ref()
13    };
14}
15#[cfg(fuchsia_api_level_less_than = "25")]
16macro_rules! get_source_dictionary {
17    ($decl:ident) => {
18        None
19    };
20}
21
22/// A node in the DependencyGraph. The first string describes the type of node and the second
23/// string is the name of the node.
24#[derive(Copy, Clone, Hash, Ord, Debug, PartialOrd, PartialEq, Eq)]
25pub enum DependencyNode<'a> {
26    Self_,
27    Child(&'a str, Option<&'a str>),
28    Collection(&'a str),
29    Environment(&'a str),
30    Capability(&'a str),
31}
32
33impl<'a> fmt::Display for DependencyNode<'a> {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            DependencyNode::Self_ => write!(f, "self"),
37            DependencyNode::Child(name, None) => write!(f, "child {}", name),
38            DependencyNode::Child(name, Some(collection)) => {
39                write!(f, "child {}:{}", collection, name)
40            }
41            DependencyNode::Collection(name) => write!(f, "collection {}", name),
42            DependencyNode::Environment(name) => write!(f, "environment {}", name),
43            DependencyNode::Capability(name) => write!(f, "capability {}", name),
44        }
45    }
46}
47
48fn ref_to_dependency_node<'a>(ref_: Option<&'a fdecl::Ref>) -> Option<DependencyNode<'a>> {
49    match ref_? {
50        fdecl::Ref::Self_(_) => Some(DependencyNode::Self_),
51        fdecl::Ref::Child(fdecl::ChildRef { name, collection }) => {
52            Some(DependencyNode::Child(name, collection.as_ref().map(|s| s.as_str())))
53        }
54        fdecl::Ref::Collection(fdecl::CollectionRef { name }) => {
55            Some(DependencyNode::Collection(name))
56        }
57        fdecl::Ref::Capability(fdecl::CapabilityRef { name }) => {
58            Some(DependencyNode::Capability(name))
59        }
60        fdecl::Ref::Framework(_)
61        | fdecl::Ref::Parent(_)
62        | fdecl::Ref::Debug(_)
63        | fdecl::Ref::VoidType(_) => None,
64        #[cfg(fuchsia_api_level_at_least = "HEAD")]
65        fdecl::Ref::Environment(_) => None,
66        _ => None,
67    }
68}
69
70// Generates the edges of the graph that are from a components `uses`.
71fn get_dependencies_from_uses<'a>(
72    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
73    decl: &'a fdecl::Component,
74) {
75    if let Some(uses) = decl.uses.as_ref() {
76        for use_ in uses.iter() {
77            #[allow(unused_variables)]
78            let (dependency_type, source, source_name, dict) = match use_ {
79                fdecl::Use::Service(u) => {
80                    (u.dependency_type, &u.source, &u.source_name, get_source_dictionary!(u))
81                }
82                fdecl::Use::Protocol(u) => {
83                    (u.dependency_type, &u.source, &u.source_name, get_source_dictionary!(u))
84                }
85                fdecl::Use::Directory(u) => {
86                    (u.dependency_type, &u.source, &u.source_name, get_source_dictionary!(u))
87                }
88                fdecl::Use::EventStream(u) => (
89                    Some(fdecl::DependencyType::Strong),
90                    &u.source,
91                    &u.source_name,
92                    None::<&String>,
93                ),
94                #[cfg(fuchsia_api_level_at_least = "HEAD")]
95                fdecl::Use::Runner(u) => (
96                    Some(fdecl::DependencyType::Strong),
97                    &u.source,
98                    &u.source_name,
99                    get_source_dictionary!(u),
100                ),
101                #[cfg(fuchsia_api_level_at_least = "HEAD")]
102                fdecl::Use::Config(u) => (
103                    Some(fdecl::DependencyType::Strong),
104                    &u.source,
105                    &u.source_name,
106                    get_source_dictionary!(u),
107                ),
108                // Storage can only be used from parent, which we don't track.
109                fdecl::Use::Storage(_) => continue,
110                _ => continue,
111            };
112            if dependency_type != Some(fdecl::DependencyType::Strong) {
113                continue;
114            }
115
116            let dependency_nodes = match &source {
117                Some(fdecl::Ref::Child(fdecl::ChildRef { name, collection })) => {
118                    vec![DependencyNode::Child(name, collection.as_ref().map(|s| s.as_str()))]
119                }
120                Some(fdecl::Ref::Self_(_)) => {
121                    #[cfg(fuchsia_api_level_at_least = "25")]
122                    if dict.as_ref().is_some() {
123                        if let Some(source_name) = source_name.as_ref() {
124                            vec![DependencyNode::Capability(source_name)]
125                        } else {
126                            vec![]
127                        }
128                    } else {
129                        vec![]
130                    }
131
132                    #[cfg(fuchsia_api_level_less_than = "25")]
133                    vec![]
134                }
135                Some(fdecl::Ref::Collection(fdecl::CollectionRef { name })) => {
136                    let mut nodes = vec![];
137                    if let Some(children) = decl.children.as_ref() {
138                        for child in children {
139                            if let Some(child_name) = child.name.as_ref() {
140                                nodes.push(DependencyNode::Child(child_name, Some(name)));
141                            }
142                        }
143                    }
144                    nodes
145                }
146                _ => vec![],
147            };
148
149            for source_node in dependency_nodes {
150                strong_dependencies.add_edge(source_node, DependencyNode::Self_);
151            }
152        }
153    }
154}
155
156fn get_dependencies_from_capabilities<'a>(
157    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
158    decl: &'a fdecl::Component,
159) {
160    if let Some(capabilities) = decl.capabilities.as_ref() {
161        for cap in capabilities {
162            match cap {
163                #[cfg(fuchsia_api_level_at_least = "25")]
164                fdecl::Capability::Dictionary(dictionary) => {
165                    if dictionary.source_path.as_ref().is_some() {
166                        if let Some(name) = dictionary.name.as_ref() {
167                            // If `source_path` is set that means the dictionary is provided by the program,
168                            // which implies a dependency from `self` to the dictionary declaration.
169                            strong_dependencies
170                                .add_edge(DependencyNode::Self_, DependencyNode::Capability(name));
171                        }
172                    }
173                }
174                fdecl::Capability::Storage(storage) => {
175                    if let (Some(name), Some(_backing_dir)) =
176                        (storage.name.as_ref(), storage.backing_dir.as_ref())
177                    {
178                        if let Some(source_node) = ref_to_dependency_node(storage.source.as_ref()) {
179                            strong_dependencies
180                                .add_edge(source_node, DependencyNode::Capability(name));
181                        }
182                    }
183                }
184                _ => continue,
185            }
186        }
187    }
188}
189
190fn get_dependencies_from_environments<'a>(
191    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
192    decl: &'a fdecl::Component,
193) {
194    if let Some(environment) = decl.environments.as_ref() {
195        for environment in environment {
196            if let Some(name) = &environment.name {
197                let target = DependencyNode::Environment(name);
198                if let Some(debugs) = environment.debug_capabilities.as_ref() {
199                    for debug in debugs {
200                        if let fdecl::DebugRegistration::Protocol(o) = debug {
201                            if let Some(source_node) = ref_to_dependency_node(o.source.as_ref()) {
202                                strong_dependencies.add_edge(source_node, target);
203                            }
204                        }
205                    }
206                }
207                if let Some(runners) = environment.runners.as_ref() {
208                    for runner in runners {
209                        if let Some(source_node) = ref_to_dependency_node(runner.source.as_ref()) {
210                            strong_dependencies.add_edge(source_node, target);
211                        }
212                    }
213                }
214                if let Some(resolvers) = environment.resolvers.as_ref() {
215                    for resolver in resolvers {
216                        if let Some(source_node) = ref_to_dependency_node(resolver.source.as_ref())
217                        {
218                            strong_dependencies.add_edge(source_node, target);
219                        }
220                    }
221                }
222            }
223        }
224    }
225}
226
227fn get_dependencies_from_children<'a>(
228    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
229    decl: &'a fdecl::Component,
230) {
231    if let Some(children) = decl.children.as_ref() {
232        for child in children {
233            if let Some(name) = child.name.as_ref() {
234                if let Some(env) = child.environment.as_ref() {
235                    let source = DependencyNode::Environment(env.as_str());
236                    let target = DependencyNode::Child(name, None);
237                    strong_dependencies.add_edge(source, target);
238                }
239            }
240        }
241    }
242}
243
244fn get_dependencies_from_collections<'a>(
245    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
246    decl: &'a fdecl::Component,
247) {
248    if let Some(collections) = decl.collections.as_ref() {
249        for collection in collections {
250            if let Some(env) = collection.environment.as_ref() {
251                if let Some(name) = collection.name.as_ref() {
252                    let source = DependencyNode::Environment(env.as_str());
253                    let target = DependencyNode::Collection(name.as_str());
254                    strong_dependencies.add_edge(source, target);
255                }
256            }
257        }
258    }
259}
260
261fn find_offer_node<'a>(
262    offer: &'a fdecl::Offer,
263    source: Option<&'a fdecl::Ref>,
264    source_name: &'a Option<String>,
265    _dictionary: Option<&'a String>,
266) -> Option<DependencyNode<'a>> {
267    if source.is_none() {
268        return None;
269    }
270
271    match source? {
272        fdecl::Ref::Child(fdecl::ChildRef { name, collection }) => {
273            Some(DependencyNode::Child(name, collection.as_ref().map(|s| s.as_str())))
274        }
275        #[cfg(fuchsia_api_level_at_least = "25")]
276        fdecl::Ref::Self_(_) if _dictionary.is_some() => {
277            let root_dict = _dictionary.unwrap().split('/').next().unwrap();
278            return Some(DependencyNode::Capability(root_dict));
279        }
280        fdecl::Ref::Self_(_) => {
281            if let Some(source_name) = source_name {
282                #[cfg(fuchsia_api_level_at_least = "25")]
283                if matches!(offer, fdecl::Offer::Dictionary(_)) {
284                    return Some(DependencyNode::Capability(source_name));
285                }
286                if matches!(offer, fdecl::Offer::Storage(_)) {
287                    return Some(DependencyNode::Capability(source_name));
288                }
289            }
290
291            Some(DependencyNode::Self_)
292        }
293        fdecl::Ref::Collection(fdecl::CollectionRef { name }) => {
294            Some(DependencyNode::Collection(name))
295        }
296        fdecl::Ref::Capability(fdecl::CapabilityRef { name }) => {
297            Some(DependencyNode::Capability(name))
298        }
299        fdecl::Ref::Parent(_) | fdecl::Ref::Framework(_) | fdecl::Ref::VoidType(_) => None,
300        _ => None,
301    }
302}
303
304fn dynamic_children_in_collection<'a>(
305    dynamic_children: &Vec<(&'a str, &'a str)>,
306    collection: &'a str,
307) -> Vec<&'a str> {
308    dynamic_children
309        .iter()
310        .filter_map(|(n, c)| if *c == collection { Some(*n) } else { None })
311        .collect()
312}
313
314fn add_offer_edges<'a>(
315    source_node: Option<DependencyNode<'a>>,
316    target_node: Option<DependencyNode<'a>>,
317    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
318    dynamic_children: &Vec<(&'a str, &'a str)>,
319) {
320    if source_node.is_none() {
321        return;
322    }
323
324    let source = source_node.unwrap();
325
326    if let DependencyNode::Collection(name) = source {
327        for child_name in dynamic_children_in_collection(dynamic_children, &name) {
328            strong_dependencies.add_edge(
329                DependencyNode::Child(&child_name, Some(&name)),
330                DependencyNode::Collection(name),
331            );
332        }
333    }
334
335    if target_node.is_none() {
336        return;
337    }
338
339    let target = target_node.unwrap();
340
341    strong_dependencies.add_edge(source, target);
342
343    if let DependencyNode::Collection(name) = target {
344        for child_name in dynamic_children_in_collection(dynamic_children, &name) {
345            strong_dependencies.add_edge(source, DependencyNode::Child(child_name, Some(&name)));
346        }
347    }
348}
349
350// Populates a dependency graph of a component's `offers`.
351fn get_dependencies_from_offers<'a>(
352    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
353    decl: &'a fdecl::Component,
354    dynamic_children: &Vec<(&'a str, &'a str)>,
355    dynamic_offers: Option<&'a Vec<fdecl::Offer>>,
356) {
357    let mut all_offers: Vec<&fdecl::Offer> = vec![];
358
359    if let Some(dynamic_offers) = dynamic_offers.as_ref() {
360        for dynamic_offer in dynamic_offers.iter() {
361            all_offers.push(dynamic_offer);
362        }
363    }
364
365    if let Some(offers) = decl.offers.as_ref() {
366        for offer in offers.iter() {
367            all_offers.push(offer);
368        }
369    }
370
371    for offer in all_offers {
372        let (source_node, target_node) = match offer {
373            fdecl::Offer::Protocol(o) => {
374                let source_node = find_offer_node(
375                    offer,
376                    o.source.as_ref(),
377                    &o.source_name,
378                    get_source_dictionary!(o),
379                );
380
381                if let Some(fdecl::DependencyType::Strong) = o.dependency_type.as_ref() {
382                    let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
383
384                    (source_node, target_node)
385                } else {
386                    continue;
387                }
388            }
389            #[cfg(fuchsia_api_level_at_least = "25")]
390            fdecl::Offer::Dictionary(o) => {
391                let source_node = find_offer_node(
392                    offer,
393                    o.source.as_ref(),
394                    &o.source_name,
395                    get_source_dictionary!(o),
396                );
397
398                if let Some(fdecl::DependencyType::Strong) = o.dependency_type.as_ref() {
399                    let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
400
401                    (source_node, target_node)
402                } else {
403                    continue;
404                }
405            }
406            fdecl::Offer::Directory(o) => {
407                let source_node = find_offer_node(
408                    offer,
409                    o.source.as_ref(),
410                    &o.source_name,
411                    get_source_dictionary!(o),
412                );
413                if let Some(fdecl::DependencyType::Strong) = o.dependency_type.as_ref() {
414                    let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
415
416                    (source_node, target_node)
417                } else {
418                    continue;
419                }
420            }
421            fdecl::Offer::Service(o) => {
422                let source_node = find_offer_node(
423                    offer,
424                    o.source.as_ref(),
425                    &o.source_name,
426                    get_source_dictionary!(o),
427                );
428
429                #[cfg(fuchsia_api_level_at_least = "HEAD")]
430                {
431                    if &fdecl::DependencyType::Strong
432                        == o.dependency_type.as_ref().unwrap_or(&fdecl::DependencyType::Strong)
433                    {
434                        let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
435
436                        (source_node, target_node)
437                    } else {
438                        continue;
439                    }
440                }
441
442                #[cfg(fuchsia_api_level_less_than = "HEAD")]
443                {
444                    let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
445
446                    (source_node, target_node)
447                }
448            }
449            fdecl::Offer::Storage(o) => {
450                let source_node = find_offer_node(offer, o.source.as_ref(), &o.source_name, None);
451
452                let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
453
454                (source_node, target_node)
455            }
456            fdecl::Offer::Runner(o) => {
457                let source_node = find_offer_node(
458                    offer,
459                    o.source.as_ref(),
460                    &o.source_name,
461                    get_source_dictionary!(o),
462                );
463
464                let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
465
466                (source_node, target_node)
467            }
468            fdecl::Offer::Resolver(o) => {
469                let source_node = find_offer_node(
470                    offer,
471                    o.source.as_ref(),
472                    &o.source_name,
473                    get_source_dictionary!(o),
474                );
475
476                let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
477
478                (source_node, target_node)
479            }
480            fdecl::Offer::Config(o) => {
481                let source_node = find_offer_node(
482                    offer,
483                    o.source.as_ref(),
484                    &o.source_name,
485                    get_source_dictionary!(o),
486                );
487
488                let target_node = find_offer_node(offer, o.target.as_ref(), &None, None);
489
490                (source_node, target_node)
491            }
492            _ => continue,
493        };
494
495        add_offer_edges(source_node, target_node, strong_dependencies, dynamic_children);
496    }
497}
498
499// Populates a dependency graph of the disjoint sets of graphs.
500pub fn generate_dependency_graph<'a>(
501    strong_dependencies: &mut DirectedGraph<DependencyNode<'a>>,
502    decl: &'a fdecl::Component,
503    dynamic_children: &Vec<(&'a str, &'a str)>,
504    dynamic_offers: Option<&'a Vec<fdecl::Offer>>,
505) {
506    get_dependencies_from_uses(strong_dependencies, decl);
507    get_dependencies_from_offers(strong_dependencies, decl, dynamic_children, dynamic_offers);
508    get_dependencies_from_capabilities(strong_dependencies, decl);
509    get_dependencies_from_environments(strong_dependencies, decl);
510    get_dependencies_from_children(strong_dependencies, decl);
511    get_dependencies_from_collections(strong_dependencies, decl);
512}
cm_graph/lib.rs

cm_graph/
lib.rs
