graphql_tools/validation/rules/

no_fragments_cycle.rs

use super::ValidationRule;
use crate::ast::ext::AstNodeWithName;
use crate::ast::{OperationVisitor, OperationVisitorContext};
use crate::static_graphql::query::{FragmentDefinition, FragmentSpread};
use crate::validation::utils::{ValidationError, ValidationErrorContext};
use std::collections::{HashMap, HashSet};

/// No fragment cycles
///
/// The graph of fragment spreads must not form any cycles including spreading itself.
/// Otherwise an operation could infinitely spread or infinitely execute on cycles in the underlying data.
///
/// https://spec.graphql.org/draft/#sec-Fragment-spreads-must-not-form-cycles
pub struct NoFragmentsCycle {
    visited_fragments: HashSet<String>,
}

impl Default for NoFragmentsCycle {
    fn default() -> Self {
        Self::new()
    }
}

impl NoFragmentsCycle {
    pub fn new() -> Self {
        Self {
            visited_fragments: HashSet::new(),
        }
    }

    /// This does a straight-forward DFS to find cycles.
    /// It does not terminate when a cycle was found but continues to explore
    /// the graph to find all possible cycles.
    fn detect_cycles<'doc>(
        &mut self,
        root: &'doc FragmentDefinition,
        spread_paths: &mut Vec<&'doc FragmentSpread>,
        spread_path_index_by_name: &mut HashMap<&'doc str, usize>,
        known_fragments: &'doc HashMap<&'doc str, &'doc FragmentDefinition>,
        error_context: &mut ValidationErrorContext,
    ) {
        // iterative DFS to avoid stack overflow on deep acyclic chains.
        // Frame::EnterSpread pushes one spread onto spread_paths then either recurses into the
        // target fragment or reports a cycle, Frame::PopSpread undoes that push on the way back.
        enum Frame<'doc> {
            EnterFragment(&'doc FragmentDefinition),
            ExitFragment(&'doc str), // removes fragment from spread_path_index_by_name
            EnterSpread(&'doc FragmentSpread), // push spread onto spread_paths
            PopSpread,               // pop spread from spread_paths
        }

        let mut stack: Vec<Frame<'doc>> = vec![Frame::EnterFragment(root)];

        while let Some(frame) = stack.pop() {
            match frame {
                Frame::ExitFragment(name) => {
                    spread_path_index_by_name.remove(name);
                }
                Frame::PopSpread => {
                    spread_paths.pop();
                }
                Frame::EnterFragment(fragment) => {
                    if self.visited_fragments.contains(&fragment.name) {
                        continue;
                    }
                    self.visited_fragments.insert(fragment.name.clone());

                    let spread_nodes = fragment.selection_set.get_recursive_fragment_spreads();
                    if spread_nodes.is_empty() {
                        continue;
                    }

                    spread_path_index_by_name.insert(fragment.name.as_str(), spread_paths.len());
                    stack.push(Frame::ExitFragment(fragment.name.as_str()));

                    // push spreads in reverse so they execute left-to-right
                    for spread_node in spread_nodes.into_iter().rev() {
                        stack.push(Frame::EnterSpread(spread_node));
                    }
                }
                Frame::EnterSpread(spread_node) => {
                    let spread_name = &spread_node.fragment_name;

                    match spread_path_index_by_name.get(spread_name.as_str()) {
                        None => {
                            if let Some(spread_def) = known_fragments.get(spread_name.as_str()) {
                                // descend into the target; PopSpread restores spread_paths once the
                                // whole child subtree is explored.
                                spread_paths.push(spread_node);
                                stack.push(Frame::PopSpread);
                                stack.push(Frame::EnterFragment(spread_def));
                            }
                        }
                        Some(cycle_index) => {
                            // include the closing spread so the reported path ends where it loops.
                            spread_paths.push(spread_node);
                            let cycle_path = &spread_paths[*cycle_index..];
                            let via_path = match cycle_path.len() {
                                0 => vec![],
                                _ => cycle_path[0..cycle_path.len() - 1]
                                    .iter()
                                    .map(|s| {
                                        format!(
                                            "\"{}\"",
                                            s.node_name()
                                                .expect("fragment spread must have a name")
                                        )
                                    })
                                    .collect::<Vec<String>>(),
                            };

                            error_context.report_error(ValidationError {
                                error_code: self.error_code(),
                                locations: cycle_path.iter().map(|f| f.position).collect(),
                                message: match via_path.len() {
                                    0 => format!(
                                        "Cannot spread fragment \"{}\" within itself.",
                                        spread_name
                                    ),
                                    _ => format!(
                                        "Cannot spread fragment \"{}\" within itself via {}.",
                                        spread_name,
                                        via_path.join(", ")
                                    ),
                                },
                            });
                            spread_paths.pop();
                        }
                    }
                }
            }
        }
    }
}

impl<'doc> OperationVisitor<'doc, ValidationErrorContext> for NoFragmentsCycle {
    fn enter_fragment_definition(
        &mut self,
        visitor_context: &mut OperationVisitorContext,
        user_context: &mut ValidationErrorContext,
        fragment: &FragmentDefinition,
    ) {
        let mut spread_paths: Vec<&FragmentSpread> = vec![];
        let mut spread_path_index_by_name: HashMap<&str, usize> = HashMap::new();

        self.detect_cycles(
            fragment,
            &mut spread_paths,
            &mut spread_path_index_by_name,
            &visitor_context.known_fragments,
            user_context,
        );
    }
}

impl ValidationRule for NoFragmentsCycle {
    fn error_code(&self) -> &'static str {
        "NoFragmentsCycle"
    }

    fn visitor<'doc>(&self) -> super::ValidationVisitor<'doc> {
        Box::new(NoFragmentsCycle::new())
    }
}

#[test]
fn single_reference_is_valid() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Dog { ...fragB }
		fragment fragB on Dog { name }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors).len();
    assert_eq!(mes, 0);
}

#[test]
fn spreading_twice_is_not_circular() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Dog { ...fragB, ...fragB }
		fragment fragB on Dog { name }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors).len();
    assert_eq!(mes, 0);
}

#[test]
fn spreading_twice_indirectly_is_not_circular() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Dog { ...fragB, ...fragC }
		fragment fragB on Dog { ...fragC }
		fragment fragC on Dog { name }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors).len();
    assert_eq!(mes, 0);
}

#[test]
fn double_spread_within_abstract_types() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment nameFragment on Pet {
			... on Dog { name }
			... on Cat { name }
		      }

		      fragment spreadsInAnon on Pet {
			... on Dog { ...nameFragment }
			... on Cat { ...nameFragment }
		      }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors).len();
    assert_eq!(mes, 0);
}

#[test]
fn does_not_false_positive_on_unknown_fragment() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment nameFragment on Pet {
			...UnknownFragment
		      }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors).len();
    assert_eq!(mes, 0);
}

#[test]
fn spreading_recursively_within_field_fails() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Human { relatives { ...fragA } }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 1);
    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
}

#[test]
fn no_spreading_itself_directly() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "
        fragment fragA on Dog { ...fragA }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 1);
    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
}

#[test]
fn no_spreading_itself_directly_within_inline_fragment() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Pet {
			... on Dog {
			  ...fragA
			}
		      }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 1);
    assert_eq!(mes, vec!["Cannot spread fragment \"fragA\" within itself."]);
}

#[test]
fn no_spreading_itself_indirectly() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Dog { ...fragB }
		fragment fragB on Dog { ...fragA }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 1);
    assert_eq!(
        mes,
        vec!["Cannot spread fragment \"fragA\" within itself via \"fragB\"."]
    );
}

#[test]
fn no_spreading_itself_indirectly_reports_opposite_order() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragB on Dog { ...fragA }
		fragment fragA on Dog { ...fragB }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 1);
    assert_eq!(
        mes,
        vec!["Cannot spread fragment \"fragB\" within itself via \"fragA\"."]
    );
}

#[test]
fn no_spreading_itself_indirectly_within_inline_fragment() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Pet {
			... on Dog {
			  ...fragB
			}
		      }
		      fragment fragB on Pet {
			... on Dog {
			  ...fragA
			}
		      }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 1);
    assert_eq!(
        mes,
        vec!["Cannot spread fragment \"fragA\" within itself via \"fragB\"."]
    );
}

#[test]
fn no_spreading_itself_deeply() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Dog { ...fragB }
        fragment fragB on Dog { ...fragC }
        fragment fragC on Dog { ...fragO }
        fragment fragX on Dog { ...fragY }
        fragment fragY on Dog { ...fragZ }
        fragment fragZ on Dog { ...fragO }
        fragment fragO on Dog { ...fragP }
        fragment fragP on Dog { ...fragA, ...fragX }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 2);
    assert_eq!(
        mes,
        vec![
            "Cannot spread fragment \"fragA\" within itself via \"fragB\", \"fragC\", \"fragO\", \"fragP\".",
            "Cannot spread fragment \"fragO\" within itself via \"fragP\", \"fragX\", \"fragY\", \"fragZ\".",
        ]
    );
}

#[test]
fn no_spreading_itself_deeply_two_paths() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "fragment fragA on Dog { ...fragB, ...fragC }
	fragment fragB on Dog { ...fragA }
	fragment fragC on Dog { ...fragA }",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 2);
    assert_eq!(
        mes,
        vec![
            "Cannot spread fragment \"fragA\" within itself via \"fragB\".",
            "Cannot spread fragment \"fragA\" within itself via \"fragC\".",
        ]
    );
}

#[test]
fn no_spreading_itself_deeply_two_paths_alt_traverse_order() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "
        fragment fragA on Dog { ...fragC }
        fragment fragB on Dog { ...fragC }
        fragment fragC on Dog { ...fragA, ...fragB }
        ",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 2);
    assert_eq!(
        mes,
        vec![
            "Cannot spread fragment \"fragA\" within itself via \"fragC\".",
            "Cannot spread fragment \"fragC\" within itself via \"fragB\".",
        ]
    );
}

#[test]
fn acyclic_fragment_chain_does_not_overflow_stack() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));

    let n = 10_000;
    let mut doc = String::from("");
    for i in 1..n {
        doc.push_str(&format!("fragment F{i} on Dog {{ ...F{} }}\n", i + 1));
    }
    doc.push_str(&format!("fragment F{n} on Dog {{ name }}\n"));

    // must return without overflowing the stack
    let errors = test_operation_with_schema(&doc, TEST_SCHEMA, &mut plan);
    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 0);
}

#[test]
fn no_spreading_itself_deeply_and_immediately() {
    use crate::validation::test_utils::*;

    let mut plan = create_plan_from_rule(Box::new(NoFragmentsCycle::new()));
    let errors = test_operation_with_schema(
        "
          fragment fragA on Dog { ...fragB }
		      fragment fragB on Dog { ...fragB, ...fragC }
		      fragment fragC on Dog { ...fragA, ...fragB }
        ",
        TEST_SCHEMA,
        &mut plan,
    );

    let mes = get_messages(&errors);
    assert_eq!(mes.len(), 3);
    assert_eq!(
        mes,
        vec![
            "Cannot spread fragment \"fragB\" within itself.",
            "Cannot spread fragment \"fragA\" within itself via \"fragB\", \"fragC\".",
            "Cannot spread fragment \"fragB\" within itself via \"fragC\".",
        ]
    );
}