graphql_tools/validation/rules/
no_fragments_cycle.rs

1use super::ValidationRule;
2use crate::ast::ext::{AstNodeWithName, FragmentSpreadExtraction};
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        fragment: &'a FragmentDefinition,
37        spread_paths: &mut Vec<&'a FragmentSpread>,
38        spread_path_index_by_name: &mut HashMap<String, usize>,
39        known_fragments: &'a HashMap<&'a str, &'a FragmentDefinition>,
40        error_context: &mut ValidationErrorContext,
41    ) {
42        if self.visited_fragments.contains(&fragment.name) {
43            return;
44        }
45
46        self.visited_fragments.insert(fragment.name.clone());
47
48        let spread_nodes = fragment.selection_set.get_recursive_fragment_spreads();
49
50        if spread_nodes.is_empty() {
51            return;
52        }
53
54        spread_path_index_by_name.insert(fragment.name.clone(), spread_paths.len());
55
56        for spread_node in spread_nodes {
57            let spread_name = spread_node.fragment_name.clone();
58            spread_paths.push(spread_node);
59
60            match spread_path_index_by_name.get(&spread_name) {
61                None => {
62                    if let Some(spread_def) = known_fragments.get(spread_name.as_str()) {
63                        self.detect_cycles(
64                            spread_def,
65                            spread_paths,
66                            spread_path_index_by_name,
67                            known_fragments,
68                            error_context,
69                        );
70                    }
71                }
72                Some(cycle_index) => {
73                    let cycle_path = &spread_paths[*cycle_index..];
74                    let via_path = match cycle_path.len() {
75                        0 => vec![],
76                        _ => cycle_path[0..cycle_path.len() - 1]
77                            .iter()
78                            .map(|s| format!("\"{}\"", s.node_name().unwrap()))
79                            .collect::<Vec<String>>(),
80                    };
81
82                    error_context.report_error(ValidationError {
83                        error_code: self.error_code(),
84                        locations: cycle_path.iter().map(|f| f.position).collect(),
85                        message: match via_path.len() {
86                            0 => {
87                                format!("Cannot spread fragment \"{}\" within itself.", spread_name)
88                            }
89                            _ => format!(
90                                "Cannot spread fragment \"{}\" within itself via {}.",
91                                spread_name,
92                                via_path.join(", ")
93                            ),
94                        },
95                    })
96                }
97            }
98
99            spread_paths.pop();
100        }
101
102        spread_path_index_by_name.remove(&fragment.name);
103    }
104}
105
106impl<'a> OperationVisitor<'a, ValidationErrorContext> for NoFragmentsCycle {
107    fn enter_fragment_definition(
108        &mut self,
109        visitor_context: &mut OperationVisitorContext,
110        user_context: &mut ValidationErrorContext,
111        fragment: &FragmentDefinition,
112    ) {
113        let mut spread_paths: Vec<&FragmentSpread> = vec![];
114        let mut spread_path_index_by_name: HashMap<String, usize> = HashMap::new();
115
116        self.detect_cycles(
117            fragment,
118            &mut spread_paths,
119            &mut spread_path_index_by_name,
120            &visitor_context.known_fragments,
121            user_context,
122        );
123    }
124}
125
126impl ValidationRule for NoFragmentsCycle {
127    fn error_code<'a>(&self) -> &'a str {
128        "NoFragmentsCycle"
129    }
130
131    fn validate(
132        &self,
133        ctx: &mut OperationVisitorContext,
134        error_collector: &mut ValidationErrorContext,
135    ) {
136        visit_document(
137            &mut NoFragmentsCycle::new(),
138            ctx.operation,
139            ctx,
140            error_collector,
141        );
142    }
143}
144
145#[test]
146fn single_reference_is_valid() {
147    use crate::validation::test_utils::*;
148
149    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
150    let errors = test_operation_with_schema(
151        "fragment fragA on Dog { ...fragB }
152		fragment fragB on Dog { name }",
153        TEST_SCHEMA,
154        &mut plan,
155    );
156
157    let mes = get_messages(&errors).len();
158    assert_eq!(mes, 0);
159}
160
161#[test]
162fn spreading_twice_is_not_circular() {
163    use crate::validation::test_utils::*;
164
165    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
166    let errors = test_operation_with_schema(
167        "fragment fragA on Dog { ...fragB, ...fragB }
168		fragment fragB on Dog { name }",
169        TEST_SCHEMA,
170        &mut plan,
171    );
172
173    let mes = get_messages(&errors).len();
174    assert_eq!(mes, 0);
175}
176
177#[test]
178fn spreading_twice_indirectly_is_not_circular() {
179    use crate::validation::test_utils::*;
180
181    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
182    let errors = test_operation_with_schema(
183        "fragment fragA on Dog { ...fragB, ...fragC }
184		fragment fragB on Dog { ...fragC }
185		fragment fragC on Dog { name }",
186        TEST_SCHEMA,
187        &mut plan,
188    );
189
190    let mes = get_messages(&errors).len();
191    assert_eq!(mes, 0);
192}
193
194#[test]
195fn double_spread_within_abstract_types() {
196    use crate::validation::test_utils::*;
197
198    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
199    let errors = test_operation_with_schema(
200        "fragment nameFragment on Pet {
201			... on Dog { name }
202			... on Cat { name }
203		      }
204
205		      fragment spreadsInAnon on Pet {
206			... on Dog { ...nameFragment }
207			... on Cat { ...nameFragment }
208		      }",
209        TEST_SCHEMA,
210        &mut plan,
211    );
212
213    let mes = get_messages(&errors).len();
214    assert_eq!(mes, 0);
215}
216
217#[test]
218fn does_not_false_positive_on_unknown_fragment() {
219    use crate::validation::test_utils::*;
220
221    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
222    let errors = test_operation_with_schema(
223        "fragment nameFragment on Pet {
224			...UnknownFragment
225		      }",
226        TEST_SCHEMA,
227        &mut plan,
228    );
229
230    let mes = get_messages(&errors).len();
231    assert_eq!(mes, 0);
232}
233
234#[test]
235fn spreading_recursively_within_field_fails() {
236    use crate::validation::test_utils::*;
237
238    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
239    let errors = test_operation_with_schema(
240        "fragment fragA on Human { relatives { ...fragA } }",
241        TEST_SCHEMA,
242        &mut plan,
243    );
244
245    let mes = get_messages(&errors);
246    assert_eq!(mes.len(), 1);
247    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
248}
249
250#[test]
251fn no_spreading_itself_directly() {
252    use crate::validation::test_utils::*;
253
254    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
255    let errors = test_operation_with_schema(
256        "
257        fragment fragA on Dog { ...fragA }",
258        TEST_SCHEMA,
259        &mut plan,
260    );
261
262    let mes = get_messages(&errors);
263    assert_eq!(mes.len(), 1);
264    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
265}
266
267#[test]
268fn no_spreading_itself_directly_within_inline_fragment() {
269    use crate::validation::test_utils::*;
270
271    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
272    let errors = test_operation_with_schema(
273        "fragment fragA on Pet {
274			... on Dog {
275			  ...fragA
276			}
277		      }",
278        TEST_SCHEMA,
279        &mut plan,
280    );
281
282    let mes = get_messages(&errors);
283    assert_eq!(mes.len(), 1);
284    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
285}
286
287#[test]
288fn no_spreading_itself_indirectly() {
289    use crate::validation::test_utils::*;
290
291    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
292    let errors = test_operation_with_schema(
293        "fragment fragA on Dog { ...fragB }
294		fragment fragB on Dog { ...fragA }",
295        TEST_SCHEMA,
296        &mut plan,
297    );
298
299    let mes = get_messages(&errors);
300    assert_eq!(mes.len(), 1);
301    assert_eq!(
302        mes,
303        vec!["Cannot spread fragment \"fragA\" within itself via \"fragB\"."]
304    );
305}
306
307#[test]
308fn no_spreading_itself_indirectly_reports_opposite_order() {
309    use crate::validation::test_utils::*;
310
311    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
312    let errors = test_operation_with_schema(
313        "fragment fragB on Dog { ...fragA }
314		fragment fragA on Dog { ...fragB }",
315        TEST_SCHEMA,
316        &mut plan,
317    );
318
319    let mes = get_messages(&errors);
320    assert_eq!(mes.len(), 1);
321    assert_eq!(
322        mes,
323        vec!["Cannot spread fragment \"fragB\" within itself via \"fragA\"."]
324    );
325}
326
327#[test]
328fn no_spreading_itself_indirectly_within_inline_fragment() {
329    use crate::validation::test_utils::*;
330
331    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
332    let errors = test_operation_with_schema(
333        "fragment fragA on Pet {
334			... on Dog {
335			  ...fragB
336			}
337		      }
338		      fragment fragB on Pet {
339			... on Dog {
340			  ...fragA
341			}
342		      }",
343        TEST_SCHEMA,
344        &mut plan,
345    );
346
347    let mes = get_messages(&errors);
348    assert_eq!(mes.len(), 1);
349    assert_eq!(
350        mes,
351        vec!["Cannot spread fragment \"fragA\" within itself via \"fragB\"."]
352    );
353}
354
355#[test]
356fn no_spreading_itself_deeply() {
357    use crate::validation::test_utils::*;
358
359    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
360    let errors = test_operation_with_schema(
361        "fragment fragA on Dog { ...fragB }
362        fragment fragB on Dog { ...fragC }
363        fragment fragC on Dog { ...fragO }
364        fragment fragX on Dog { ...fragY }
365        fragment fragY on Dog { ...fragZ }
366        fragment fragZ on Dog { ...fragO }
367        fragment fragO on Dog { ...fragP }
368        fragment fragP on Dog { ...fragA, ...fragX }",
369        TEST_SCHEMA,
370        &mut plan,
371    );
372
373    let mes = get_messages(&errors);
374    assert_eq!(mes.len(), 2);
375    assert_eq!(
376        mes,
377        vec![
378            "Cannot spread fragment \"fragA\" within itself via \"fragB\", \"fragC\", \"fragO\", \"fragP\".",
379            "Cannot spread fragment \"fragO\" within itself via \"fragP\", \"fragX\", \"fragY\", \"fragZ\".",
380        ]
381    );
382}
383
384#[test]
385fn no_spreading_itself_deeply_two_paths() {
386    use crate::validation::test_utils::*;
387
388    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
389    let errors = test_operation_with_schema(
390        "fragment fragA on Dog { ...fragB, ...fragC }
391	fragment fragB on Dog { ...fragA }
392	fragment fragC on Dog { ...fragA }",
393        TEST_SCHEMA,
394        &mut plan,
395    );
396
397    let mes = get_messages(&errors);
398    assert_eq!(mes.len(), 2);
399    assert_eq!(
400        mes,
401        vec![
402            "Cannot spread fragment \"fragA\" within itself via \"fragB\".",
403            "Cannot spread fragment \"fragA\" within itself via \"fragC\".",
404        ]
405    );
406}
407
408#[test]
409fn no_spreading_itself_deeply_two_paths_alt_traverse_order() {
410    use crate::validation::test_utils::*;
411
412    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
413    let errors = test_operation_with_schema(
414        "
415        fragment fragA on Dog { ...fragC }
416        fragment fragB on Dog { ...fragC }
417        fragment fragC on Dog { ...fragA, ...fragB }
418        ",
419        TEST_SCHEMA,
420        &mut plan,
421    );
422
423    let mes = get_messages(&errors);
424    assert_eq!(mes.len(), 2);
425    assert_eq!(
426        mes,
427        vec![
428            "Cannot spread fragment \"fragA\" within itself via \"fragC\".",
429            "Cannot spread fragment \"fragC\" within itself via \"fragB\".",
430        ]
431    );
432}
433
434#[test]
435fn no_spreading_itself_deeply_and_immediately() {
436    use crate::validation::test_utils::*;
437
438    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
439    let errors = test_operation_with_schema(
440        "
441          fragment fragA on Dog { ...fragB }
442		      fragment fragB on Dog { ...fragB, ...fragC }
443		      fragment fragC on Dog { ...fragA, ...fragB }
444        ",
445        TEST_SCHEMA,
446        &mut plan,
447    );
448
449    let mes = get_messages(&errors);
450    assert_eq!(mes.len(), 3);
451    assert_eq!(
452        mes,
453        vec![
454            "Cannot spread fragment \"fragB\" within itself.",
455            "Cannot spread fragment \"fragA\" within itself via \"fragB\", \"fragC\".",
456            "Cannot spread fragment \"fragB\" within itself via \"fragC\".",
457        ]
458    );
459}
graphql_tools/validation/rules/no_fragments_cycle.rs

graphql_tools/validation/rules/
no_fragments_cycle.rs
