cm_graph/
lib.rs

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

cm_graph/
lib.rs
