graphql_query/validate/rules/
no_fragment_cycles.rs

1use hashbrown::HashMap;
2
3use super::super::{ValidationContext, ValidationRule};
4use crate::{ast::*, visit::*};
5
6/// Validate that a document does not contain fragments that are spread within themselves, creating a loop.
7///
8/// See [`ValidationRule`]
9/// [Reference](https://spec.graphql.org/October2021/#sec-Fragment-spreads-must-not-form-cycles)
10#[derive(Default)]
11pub struct NoFragmentCycles<'a> {
12    fragment_edges: HashMap<&'a str, Vec<&'a str>>,
13    used_fragments: Vec<&'a str>,
14}
15
16impl<'a> ValidationRule<'a> for NoFragmentCycles<'a> {}
17
18impl<'a> Visitor<'a, ValidationContext<'a>> for NoFragmentCycles<'a> {
19    fn enter_operation(
20        &mut self,
21        _ctx: &mut ValidationContext<'a>,
22        _operation: &'a OperationDefinition<'a>,
23        _info: &VisitInfo,
24    ) -> VisitFlow {
25        VisitFlow::Skip
26    }
27
28    fn enter_fragment(
29        &mut self,
30        _ctx: &mut ValidationContext<'a>,
31        _fragment: &'a FragmentDefinition,
32        _info: &VisitInfo,
33    ) -> VisitFlow {
34        self.used_fragments.clear();
35        VisitFlow::Next
36    }
37
38    fn leave_fragment(
39        &mut self,
40        _ctx: &mut ValidationContext<'a>,
41        fragment: &'a FragmentDefinition<'a>,
42        _info: &VisitInfo,
43    ) -> VisitFlow {
44        let name = fragment.name.name;
45        self.fragment_edges
46            .insert(name, self.used_fragments.clone());
47        self.used_fragments.clear();
48        VisitFlow::Next
49    }
50
51    fn enter_fragment_spread(
52        &mut self,
53        _ctx: &mut ValidationContext<'a>,
54        spread: &'a FragmentSpread<'a>,
55        _info: &VisitInfo,
56    ) -> VisitFlow {
57        self.used_fragments.push(spread.name.name);
58        VisitFlow::Skip
59    }
60
61    fn leave_document(
62        &mut self,
63        ctx: &mut ValidationContext<'a>,
64        _document: &'a Document<'a>,
65        _info: &VisitInfo,
66    ) -> VisitFlow {
67        let mut visited: Vec<&'a str> = Vec::default();
68        for (name, _) in self.fragment_edges.iter() {
69            if contains_edge(&mut visited, name, name, &self.fragment_edges) {
70                ctx.add_error("Cannot spread fragments within themselves");
71                return VisitFlow::Break;
72            }
73            visited.clear();
74        }
75        VisitFlow::Next
76    }
77
78    fn enter_variable_definition(
79        &mut self,
80        _ctx: &mut ValidationContext<'a>,
81        _var_def: &'a VariableDefinition,
82        _info: &VisitInfo,
83    ) -> VisitFlow {
84        VisitFlow::Skip
85    }
86
87    fn enter_argument(
88        &mut self,
89        _ctx: &mut ValidationContext<'a>,
90        _argument: &'a Argument,
91        _info: &VisitInfo,
92    ) -> VisitFlow {
93        VisitFlow::Skip
94    }
95
96    fn enter_directive(
97        &mut self,
98        _ctx: &mut ValidationContext<'a>,
99        _directive: &'a Directive,
100        _info: &VisitInfo,
101    ) -> VisitFlow {
102        VisitFlow::Skip
103    }
104}
105
106fn contains_edge<'a>(
107    visited: &mut Vec<&'a str>,
108    toplevel_name: &'a str,
109    current_name: &'a str,
110    fragment_edges: &HashMap<&'a str, Vec<&'a str>>,
111) -> bool {
112    if visited.contains(&current_name) {
113        true
114    } else if let Some(edges) = fragment_edges.get(current_name) {
115        visited.push(current_name);
116        if edges.contains(&toplevel_name) {
117            true
118        } else {
119            for next_name in edges {
120                if contains_edge(visited, toplevel_name, next_name, fragment_edges) {
121                    return true;
122                }
123            }
124            false
125        }
126    } else {
127        false
128    }
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134
135    #[test]
136    fn valid_fragment_spreads() {
137        let ctx = ASTContext::new();
138        let document = Document::parse(
139            &ctx,
140            "fragment A on A { ...B } fragment B on B { __typename }",
141        )
142        .unwrap();
143        NoFragmentCycles::validate(&ctx, document).unwrap();
144    }
145
146    #[test]
147    fn cycling_fragment_spreads() {
148        let ctx = ASTContext::new();
149        let document =
150            Document::parse(&ctx, "fragment A on A { ...B } fragment B on B { ...A }").unwrap();
151        NoFragmentCycles::validate(&ctx, document).unwrap_err();
152        let document = Document::parse(
153            &ctx,
154            "fragment A on A { ...B } fragment B on B { ...C } fragment C on C { ...A }",
155        )
156        .unwrap();
157        NoFragmentCycles::validate(&ctx, document).unwrap_err();
158        let document = Document::parse(&ctx, "fragment D on D { ...C } fragment A on A { ...B } fragment B on B { ...C } fragment C on C { ...A }").unwrap();
159        NoFragmentCycles::validate(&ctx, document).unwrap_err();
160        let document = Document::parse(&ctx, "fragment D on D { ...E } fragment A on A { ...B } fragment B on B { ...C } fragment C on C { ...A } fragment E on E { __typename }").unwrap();
161        NoFragmentCycles::validate(&ctx, document).unwrap_err();
162    }
163}
graphql_query/validate/rules/no_fragment_cycles.rs

graphql_query/validate/rules/
no_fragment_cycles.rs
