graphql_query/validate/rules/
no_fragment_cycles.rs

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

graphql_query/validate/rules/
no_fragment_cycles.rs
