graphql_tools/validation/rules/
no_fragments_cycle.rs

1use super::ValidationRule;
2use crate::ast::ext::AstNodeWithName;
3use crate::ast::{visit_document, OperationVisitor, OperationVisitorContext};
4use crate::static_graphql::query::{FragmentDefinition, FragmentSpread};
5use crate::validation::utils::{ValidationError, ValidationErrorContext};
6use std::collections::{HashMap, HashSet};
7
8/// No fragment cycles
9///
10/// The graph of fragment spreads must not form any cycles including spreading itself.
11/// Otherwise an operation could infinitely spread or infinitely execute on cycles in the underlying data.
12///
13/// https://spec.graphql.org/draft/#sec-Fragment-spreads-must-not-form-cycles
14pub struct NoFragmentsCycle {
15    visited_fragments: HashSet<String>,
16}
17
18impl Default for NoFragmentsCycle {
19    fn default() -> Self {
20        Self::new()
21    }
22}
23
24impl NoFragmentsCycle {
25    pub fn new() -> Self {
26        Self {
27            visited_fragments: HashSet::new(),
28        }
29    }
30
31    /// This does a straight-forward DFS to find cycles.
32    /// It does not terminate when a cycle was found but continues to explore
33    /// the graph to find all possible cycles.
34    fn detect_cycles<'a>(
35        &mut self,
36        root: &'a FragmentDefinition,
37        spread_paths: &mut Vec<&'a FragmentSpread>,
38        spread_path_index_by_name: &mut HashMap<&'a str, usize>,
39        known_fragments: &'a HashMap<&'a str, &'a FragmentDefinition>,
40        error_context: &mut ValidationErrorContext,
41    ) {
42        // iterative DFS to avoid stack overflow on deep acyclic chains.
43        // Frame::EnterSpread pushes one spread onto spread_paths then either recurses into the
44        // target fragment or reports a cycle, Frame::PopSpread undoes that push on the way back.
45        enum Frame<'a> {
46            EnterFragment(&'a FragmentDefinition),
47            ExitFragment(&'a str), // removes fragment from spread_path_index_by_name
48            EnterSpread(&'a FragmentSpread), // push spread onto spread_paths
49            PopSpread,             // pop spread from spread_paths
50        }
51
52        let mut stack: Vec<Frame<'a>> = vec![Frame::EnterFragment(root)];
53
54        while let Some(frame) = stack.pop() {
55            match frame {
56                Frame::ExitFragment(name) => {
57                    spread_path_index_by_name.remove(name);
58                }
59                Frame::PopSpread => {
60                    spread_paths.pop();
61                }
62                Frame::EnterFragment(fragment) => {
63                    if self.visited_fragments.contains(&fragment.name) {
64                        continue;
65                    }
66                    self.visited_fragments.insert(fragment.name.clone());
67
68                    let spread_nodes = fragment.selection_set.get_recursive_fragment_spreads();
69                    if spread_nodes.is_empty() {
70                        continue;
71                    }
72
73                    spread_path_index_by_name.insert(fragment.name.as_str(), spread_paths.len());
74                    stack.push(Frame::ExitFragment(fragment.name.as_str()));
75
76                    // push spreads in reverse so they execute left-to-right
77                    for spread_node in spread_nodes.into_iter().rev() {
78                        stack.push(Frame::EnterSpread(spread_node));
79                    }
80                }
81                Frame::EnterSpread(spread_node) => {
82                    let spread_name = &spread_node.fragment_name;
83
84                    match spread_path_index_by_name.get(spread_name.as_str()) {
85                        None => {
86                            if let Some(spread_def) = known_fragments.get(spread_name.as_str()) {
87                                // descend into the target; PopSpread restores spread_paths once the
88                                // whole child subtree is explored.
89                                spread_paths.push(spread_node);
90                                stack.push(Frame::PopSpread);
91                                stack.push(Frame::EnterFragment(spread_def));
92                            }
93                        }
94                        Some(cycle_index) => {
95                            // include the closing spread so the reported path ends where it loops.
96                            spread_paths.push(spread_node);
97                            let cycle_path = &spread_paths[*cycle_index..];
98                            let via_path = match cycle_path.len() {
99                                0 => vec![],
100                                _ => cycle_path[0..cycle_path.len() - 1]
101                                    .iter()
102                                    .map(|s| {
103                                        format!(
104                                            "\"{}\"",
105                                            s.node_name()
106                                                .expect("fragment spread must have a name")
107                                        )
108                                    })
109                                    .collect::<Vec<String>>(),
110                            };
111
112                            error_context.report_error(ValidationError {
113                                error_code: self.error_code(),
114                                locations: cycle_path.iter().map(|f| f.position).collect(),
115                                message: match via_path.len() {
116                                    0 => format!(
117                                        "Cannot spread fragment \"{}\" within itself.",
118                                        spread_name
119                                    ),
120                                    _ => format!(
121                                        "Cannot spread fragment \"{}\" within itself via {}.",
122                                        spread_name,
123                                        via_path.join(", ")
124                                    ),
125                                },
126                            });
127                            spread_paths.pop();
128                        }
129                    }
130                }
131            }
132        }
133    }
134}
135
136impl<'a> OperationVisitor<'a, ValidationErrorContext> for NoFragmentsCycle {
137    fn enter_fragment_definition(
138        &mut self,
139        visitor_context: &mut OperationVisitorContext,
140        user_context: &mut ValidationErrorContext,
141        fragment: &FragmentDefinition,
142    ) {
143        let mut spread_paths: Vec<&FragmentSpread> = vec![];
144        let mut spread_path_index_by_name: HashMap<&str, usize> = HashMap::new();
145
146        self.detect_cycles(
147            fragment,
148            &mut spread_paths,
149            &mut spread_path_index_by_name,
150            &visitor_context.known_fragments,
151            user_context,
152        );
153    }
154}
155
156impl ValidationRule for NoFragmentsCycle {
157    fn error_code<'a>(&self) -> &'a str {
158        "NoFragmentsCycle"
159    }
160
161    fn validate(
162        &self,
163        ctx: &mut OperationVisitorContext,
164        error_collector: &mut ValidationErrorContext,
165    ) {
166        visit_document(
167            &mut NoFragmentsCycle::new(),
168            ctx.operation,
169            ctx,
170            error_collector,
171        );
172    }
173}
174
175#[test]
176fn single_reference_is_valid() {
177    use crate::validation::test_utils::*;
178
179    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
180    let errors = test_operation_with_schema(
181        "fragment fragA on Dog { ...fragB }
182		fragment fragB on Dog { name }",
183        TEST_SCHEMA,
184        &mut plan,
185    );
186
187    let mes = get_messages(&errors).len();
188    assert_eq!(mes, 0);
189}
190
191#[test]
192fn spreading_twice_is_not_circular() {
193    use crate::validation::test_utils::*;
194
195    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
196    let errors = test_operation_with_schema(
197        "fragment fragA on Dog { ...fragB, ...fragB }
198		fragment fragB on Dog { name }",
199        TEST_SCHEMA,
200        &mut plan,
201    );
202
203    let mes = get_messages(&errors).len();
204    assert_eq!(mes, 0);
205}
206
207#[test]
208fn spreading_twice_indirectly_is_not_circular() {
209    use crate::validation::test_utils::*;
210
211    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
212    let errors = test_operation_with_schema(
213        "fragment fragA on Dog { ...fragB, ...fragC }
214		fragment fragB on Dog { ...fragC }
215		fragment fragC on Dog { name }",
216        TEST_SCHEMA,
217        &mut plan,
218    );
219
220    let mes = get_messages(&errors).len();
221    assert_eq!(mes, 0);
222}
223
224#[test]
225fn double_spread_within_abstract_types() {
226    use crate::validation::test_utils::*;
227
228    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
229    let errors = test_operation_with_schema(
230        "fragment nameFragment on Pet {
231			... on Dog { name }
232			... on Cat { name }
233		      }
234
235		      fragment spreadsInAnon on Pet {
236			... on Dog { ...nameFragment }
237			... on Cat { ...nameFragment }
238		      }",
239        TEST_SCHEMA,
240        &mut plan,
241    );
242
243    let mes = get_messages(&errors).len();
244    assert_eq!(mes, 0);
245}
246
247#[test]
248fn does_not_false_positive_on_unknown_fragment() {
249    use crate::validation::test_utils::*;
250
251    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
252    let errors = test_operation_with_schema(
253        "fragment nameFragment on Pet {
254			...UnknownFragment
255		      }",
256        TEST_SCHEMA,
257        &mut plan,
258    );
259
260    let mes = get_messages(&errors).len();
261    assert_eq!(mes, 0);
262}
263
264#[test]
265fn spreading_recursively_within_field_fails() {
266    use crate::validation::test_utils::*;
267
268    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
269    let errors = test_operation_with_schema(
270        "fragment fragA on Human { relatives { ...fragA } }",
271        TEST_SCHEMA,
272        &mut plan,
273    );
274
275    let mes = get_messages(&errors);
276    assert_eq!(mes.len(), 1);
277    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
278}
279
280#[test]
281fn no_spreading_itself_directly() {
282    use crate::validation::test_utils::*;
283
284    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
285    let errors = test_operation_with_schema(
286        "
287        fragment fragA on Dog { ...fragA }",
288        TEST_SCHEMA,
289        &mut plan,
290    );
291
292    let mes = get_messages(&errors);
293    assert_eq!(mes.len(), 1);
294    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
295}
296
297#[test]
298fn no_spreading_itself_directly_within_inline_fragment() {
299    use crate::validation::test_utils::*;
300
301    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
302    let errors = test_operation_with_schema(
303        "fragment fragA on Pet {
304			... on Dog {
305			  ...fragA
306			}
307		      }",
308        TEST_SCHEMA,
309        &mut plan,
310    );
311
312    let mes = get_messages(&errors);
313    assert_eq!(mes.len(), 1);
314    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
315}
316
317#[test]
318fn no_spreading_itself_indirectly() {
319    use crate::validation::test_utils::*;
320
321    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
322    let errors = test_operation_with_schema(
323        "fragment fragA on Dog { ...fragB }
324		fragment fragB on Dog { ...fragA }",
325        TEST_SCHEMA,
326        &mut plan,
327    );
328
329    let mes = get_messages(&errors);
330    assert_eq!(mes.len(), 1);
331    assert_eq!(
332        mes,
333        vec!["Cannot spread fragment \"fragA\" within itself via \"fragB\"."]
334    );
335}
336
337#[test]
338fn no_spreading_itself_indirectly_reports_opposite_order() {
339    use crate::validation::test_utils::*;
340
341    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
342    let errors = test_operation_with_schema(
343        "fragment fragB on Dog { ...fragA }
344		fragment fragA on Dog { ...fragB }",
345        TEST_SCHEMA,
346        &mut plan,
347    );
348
349    let mes = get_messages(&errors);
350    assert_eq!(mes.len(), 1);
351    assert_eq!(
352        mes,
353        vec!["Cannot spread fragment \"fragB\" within itself via \"fragA\"."]
354    );
355}
356
357#[test]
358fn no_spreading_itself_indirectly_within_inline_fragment() {
359    use crate::validation::test_utils::*;
360
361    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
362    let errors = test_operation_with_schema(
363        "fragment fragA on Pet {
364			... on Dog {
365			  ...fragB
366			}
367		      }
368		      fragment fragB on Pet {
369			... on Dog {
370			  ...fragA
371			}
372		      }",
373        TEST_SCHEMA,
374        &mut plan,
375    );
376
377    let mes = get_messages(&errors);
378    assert_eq!(mes.len(), 1);
379    assert_eq!(
380        mes,
381        vec!["Cannot spread fragment \"fragA\" within itself via \"fragB\"."]
382    );
383}
384
385#[test]
386fn no_spreading_itself_deeply() {
387    use crate::validation::test_utils::*;
388
389    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
390    let errors = test_operation_with_schema(
391        "fragment fragA on Dog { ...fragB }
392        fragment fragB on Dog { ...fragC }
393        fragment fragC on Dog { ...fragO }
394        fragment fragX on Dog { ...fragY }
395        fragment fragY on Dog { ...fragZ }
396        fragment fragZ on Dog { ...fragO }
397        fragment fragO on Dog { ...fragP }
398        fragment fragP on Dog { ...fragA, ...fragX }",
399        TEST_SCHEMA,
400        &mut plan,
401    );
402
403    let mes = get_messages(&errors);
404    assert_eq!(mes.len(), 2);
405    assert_eq!(
406        mes,
407        vec![
408            "Cannot spread fragment \"fragA\" within itself via \"fragB\", \"fragC\", \"fragO\", \"fragP\".",
409            "Cannot spread fragment \"fragO\" within itself via \"fragP\", \"fragX\", \"fragY\", \"fragZ\".",
410        ]
411    );
412}
413
414#[test]
415fn no_spreading_itself_deeply_two_paths() {
416    use crate::validation::test_utils::*;
417
418    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
419    let errors = test_operation_with_schema(
420        "fragment fragA on Dog { ...fragB, ...fragC }
421	fragment fragB on Dog { ...fragA }
422	fragment fragC on Dog { ...fragA }",
423        TEST_SCHEMA,
424        &mut plan,
425    );
426
427    let mes = get_messages(&errors);
428    assert_eq!(mes.len(), 2);
429    assert_eq!(
430        mes,
431        vec![
432            "Cannot spread fragment \"fragA\" within itself via \"fragB\".",
433            "Cannot spread fragment \"fragA\" within itself via \"fragC\".",
434        ]
435    );
436}
437
438#[test]
439fn no_spreading_itself_deeply_two_paths_alt_traverse_order() {
440    use crate::validation::test_utils::*;
441
442    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
443    let errors = test_operation_with_schema(
444        "
445        fragment fragA on Dog { ...fragC }
446        fragment fragB on Dog { ...fragC }
447        fragment fragC on Dog { ...fragA, ...fragB }
448        ",
449        TEST_SCHEMA,
450        &mut plan,
451    );
452
453    let mes = get_messages(&errors);
454    assert_eq!(mes.len(), 2);
455    assert_eq!(
456        mes,
457        vec![
458            "Cannot spread fragment \"fragA\" within itself via \"fragC\".",
459            "Cannot spread fragment \"fragC\" within itself via \"fragB\".",
460        ]
461    );
462}
463
464#[test]
465fn acyclic_fragment_chain_does_not_overflow_stack() {
466    use crate::validation::test_utils::*;
467
468    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
469
470    let n = 10_000;
471    let mut doc = String::from("");
472    for i in 1..n {
473        doc.push_str(&format!("fragment F{i} on Dog {{ ...F{} }}\n", i + 1));
474    }
475    doc.push_str(&format!("fragment F{n} on Dog {{ name }}\n"));
476
477    // must return without overflowing the stack
478    let errors = test_operation_with_schema(&doc, TEST_SCHEMA, &mut plan);
479    let mes = get_messages(&errors);
480    assert_eq!(mes.len(), 0);
481}
482
483#[test]
484fn no_spreading_itself_deeply_and_immediately() {
485    use crate::validation::test_utils::*;
486
487    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
488    let errors = test_operation_with_schema(
489        "
490          fragment fragA on Dog { ...fragB }
491		      fragment fragB on Dog { ...fragB, ...fragC }
492		      fragment fragC on Dog { ...fragA, ...fragB }
493        ",
494        TEST_SCHEMA,
495        &mut plan,
496    );
497
498    let mes = get_messages(&errors);
499    assert_eq!(mes.len(), 3);
500    assert_eq!(
501        mes,
502        vec![
503            "Cannot spread fragment \"fragB\" within itself.",
504            "Cannot spread fragment \"fragA\" within itself via \"fragB\", \"fragC\".",
505            "Cannot spread fragment \"fragB\" within itself via \"fragC\".",
506        ]
507    );
508}
graphql_tools/validation/rules/no_fragments_cycle.rs

graphql_tools/validation/rules/
no_fragments_cycle.rs
