CVE-2022-31173: Uncontrolled Recursion (CWE-674)
value: Juniper is a GraphQL server library for Rust. Affected versions of Juniper are vulnerable to uncontrolled recursion resulting in a program crash. This issue has been addressed in version 0.15.10. Users are advised to upgrade. Users unable to upgrade should limit the recursion depth manually.
CWE description: The product does not properly control the amount of recursion that takes place,  consuming excessive resources, such as allocated memory or the program stack.
CVSS v3 base score: 7.5
Published: 2022-08-01T19:15Z
Repository: https://github.com/graphql-rust/juniper
Language: Rust
Files changed: juniper/src/validation/rules/no_fragment_cycles.rs, juniper/src/validation/rules/no_undefined_variables.rs, juniper/src/validation/rules/no_unused_fragments.rs, juniper/src/validation/rules/no_unused_variables.rs, juniper/src/validation/rules/overlapping_fields_can_be_merged.rs, juniper/src/validation/rules/variables_in_allowed_position.rs, tests/integration/Cargo.toml, tests/integration/tests/cve_2022_31173.rs
Commit date: 2022-07-28 14:33:16 +0300
Commit message: Merge pull request from GHSA-4rx6-g5vg-5f3j

* Replace recursions with heap allocations

* Some corrections [skip ci]

* Add recursive nested fragments test case

* Docs and small corrections

* Corrections

Co-authored-by: Kai Ren <tyranron@gmail.com>
Diff: diff --git a/juniper/src/validation/rules/no_fragment_cycles.rs b/juniper/src/validation/rules/no_fragment_cycles.rs
index 3a6782a7..0845f820 100644
--- a/juniper/src/validation/rules/no_fragment_cycles.rs
+++ b/juniper/src/validation/rules/no_fragment_cycles.rs
@@ -5,49 +5,40 @@ use crate::{
     parser::Spanning,
     validation::{RuleError, ValidatorContext, Visitor},
     value::ScalarValue,
 };
 
-pub struct NoFragmentCycles<'a> {
-    current_fragment: Option<&'a str>,
-    spreads: HashMap<&'a str, Vec<Spanning<&'a str>>>,
-    fragment_order: Vec<&'a str>,
-}
-
-struct CycleDetector<'a> {
-    visited: HashSet<&'a str>,
-    spreads: &'a HashMap<&'a str, Vec<Spanning<&'a str>>>,
-    path_indices: HashMap<&'a str, usize>,
-    errors: Vec<RuleError>,
-}
-
 pub fn factory<'a>() -> NoFragmentCycles<'a> {
     NoFragmentCycles {
         current_fragment: None,
         spreads: HashMap::new(),
         fragment_order: Vec::new(),
     }
 }
 
+pub struct NoFragmentCycles<'a> {
+    current_fragment: Option<&'a str>,
+    spreads: HashMap<&'a str, Vec<Spanning<&'a str>>>,
+    fragment_order: Vec<&'a str>,
+}
+
 impl<'a, S> Visitor<'a, S> for NoFragmentCycles<'a>
 where
     S: ScalarValue,
 {
     fn exit_document(&mut self, ctx: &mut ValidatorContext<'a, S>, _: &'a Document<S>) {
         assert!(self.current_fragment.is_none());
 
         let mut detector = CycleDetector {
             visited: HashSet::new(),
             spreads: &self.spreads,
-            path_indices: HashMap::new(),
             errors: Vec::new(),
         };
 
         for frag in &self.fragment_order {
             if !detector.visited.contains(frag) {
-                let mut path = Vec::new();
-                detector.detect_from(frag, &mut path);
+                detector.detect_from(frag);
             }
         }
 
         ctx.append_errors(detector.errors);
     }
@@ -89,41 +80,68 @@ where
                 ));
         }
     }
 }
 
+type CycleDetectorState<'a> = (&'a str, Vec<&'a Spanning<&'a str>>, HashMap<&'a str, usize>);
+
+struct CycleDetector<'a> {
+    visited: HashSet<&'a str>,
+    spreads: &'a HashMap<&'a str, Vec<Spanning<&'a str>>>,
+    errors: Vec<RuleError>,
+}
+
 impl<'a> CycleDetector<'a> {
-    fn detect_from(&mut self, from: &'a str, path: &mut Vec<&'a Spanning<&'a str>>) {
+    fn detect_from(&mut self, from: &'a str) {
+        let mut to_visit = Vec::new();
+        to_visit.push((from, Vec::new(), HashMap::new()));
+
+        while let Some((from, path, path_indices)) = to_visit.pop() {
+            to_visit.extend(self.detect_from_inner(from, path, path_indices));
+        }
+    }
+
+    /// This function should be called only inside [`Self::detect_from()`], as
+    /// it's a recursive function using heap instead of a stack. So, instead of
+    /// the recursive call, we return a [`Vec`] that is visited inside
+    /// [`Self::detect_from()`].
+    fn detect_from_inner(
+        &mut self,
+        from: &'a str,
+        path: Vec<&'a Spanning<&'a str>>,
+        mut path_indices: HashMap<&'a str, usize>,
+    ) -> Vec<CycleDetectorState<'a>> {
         self.visited.insert(from);
 
         if !self.spreads.contains_key(from) {
-            return;
+            return Vec::new();
         }
 
-        self.path_indices.insert(from, path.len());
+        path_indices.insert(from, path.len());
 
+        let mut to_visit = Vec::new();
         for node in &self.spreads[from] {
-            let name = &node.item;
-            let index = self.path_indices.get(name).cloned();
+            let name = node.item;
+            let index = path_indices.get(name).cloned();
 
             if let Some(index) = index {
                 let err_pos = if index < path.len() {
                     path[index]
                 } else {
                     node
                 };
 
                 self.errors
                     .push(RuleError::new(&error_message(name), &[err_pos.start]));
-            } else if !self.visited.contains(name) {
+            } else {
+                let mut path = path.clone();
                 path.push(node);
-                self.detect_from(name, path);
-                path.pop();
+                to_visit.push((name, path, path_indices.clone()));
             }
         }
 
-        self.path_indices.remove(from);
+        to_visit
     }
 }
 
 fn error_message(frag_name: &str) -> String {
     format!(r#"Cannot spread fragment "{frag_name}""#)
diff --git a/juniper/src/validation/rules/no_undefined_variables.rs b/juniper/src/validation/rules/no_undefined_variables.rs
index 18287c49..6e382b23 100644
--- a/juniper/src/validation/rules/no_undefined_variables.rs
+++ b/juniper/src/validation/rules/no_undefined_variables.rs
@@ -10,36 +10,62 @@ use std::collections::{HashMap, HashSet};
 pub enum Scope<'a> {
     Operation(Option<&'a str>),
     Fragment(&'a str),
 }
 
-pub struct NoUndefinedVariables<'a> {
-    defined_variables: HashMap<Option<&'a str>, (SourcePosition, HashSet<&'a str>)>,
-    used_variables: HashMap<Scope<'a>, Vec<Spanning<&'a str>>>,
-    current_scope: Option<Scope<'a>>,
-    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
-}
-
 pub fn factory<'a>() -> NoUndefinedVariables<'a> {
     NoUndefinedVariables {
         defined_variables: HashMap::new(),
         used_variables: HashMap::new(),
         current_scope: None,
         spreads: HashMap::new(),
     }
 }
 
+pub struct NoUndefinedVariables<'a> {
+    defined_variables: HashMap<Option<&'a str>, (SourcePosition, HashSet<&'a str>)>,
+    used_variables: HashMap<Scope<'a>, Vec<Spanning<&'a str>>>,
+    current_scope: Option<Scope<'a>>,
+    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
+}
+
 impl<'a> NoUndefinedVariables<'a> {
     fn find_undef_vars(
         &'a self,
         scope: &Scope<'a>,
         defined: &HashSet<&'a str>,
         unused: &mut Vec<&'a Spanning<&'a str>>,
         visited: &mut HashSet<Scope<'a>>,
     ) {
+        let mut to_visit = Vec::new();
+        if let Some(spreads) = self.find_undef_vars_inner(scope, defined, unused, visited) {
+            to_visit.push(spreads);
+        }
+        while let Some(spreads) = to_visit.pop() {
+            for spread in spreads {
+                if let Some(spreads) =
+                    self.find_undef_vars_inner(&Scope::Fragment(spread), defined, unused, visited)
+                {
+                    to_visit.push(spreads);
+                }
+            }
+        }
+    }
+
+    /// This function should be called only inside [`Self::find_undef_vars()`],
+    /// as it's a recursive function using heap instead of a stack. So, instead
+    /// of the recursive call, we return a [`Vec`] that is visited inside
+    /// [`Self::find_undef_vars()`].
+    fn find_undef_vars_inner(
+        &'a self,
+        scope: &Scope<'a>,
+        defined: &HashSet<&'a str>,
+        unused: &mut Vec<&'a Spanning<&'a str>>,
+        visited: &mut HashSet<Scope<'a>>,
+    ) -> Option<&'a Vec<&'a str>> {
         if visited.contains(scope) {
-            return;
+            return None;
         }
 
         visited.insert(scope.clone());
 
         if let Some(used_vars) = self.used_variables.get(scope) {
@@ -48,15 +74,11 @@ impl<'a> NoUndefinedVariables<'a> {
                     unused.push(var);
                 }
             }
         }
 
-        if let Some(spreads) = self.spreads.get(scope) {
-            for spread in spreads {
-                self.find_undef_vars(&Scope::Fragment(spread), defined, unused, visited);
-            }
-        }
+        self.spreads.get(scope)
     }
 }
 
 impl<'a, S> Visitor<'a, S> for NoUndefinedVariables<'a>
 where
diff --git a/juniper/src/validation/rules/no_unused_fragments.rs b/juniper/src/validation/rules/no_unused_fragments.rs
index 38a360b5..8ac7f8ae 100644
--- a/juniper/src/validation/rules/no_unused_fragments.rs
+++ b/juniper/src/validation/rules/no_unused_fragments.rs
@@ -11,40 +11,55 @@ use crate::{
 pub enum Scope<'a> {
     Operation(Option<&'a str>),
     Fragment(&'a str),
 }
 
-pub struct NoUnusedFragments<'a> {
-    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
-    defined_fragments: HashSet<Spanning<&'a str>>,
-    current_scope: Option<Scope<'a>>,
-}
-
 pub fn factory<'a>() -> NoUnusedFragments<'a> {
     NoUnusedFragments {
         spreads: HashMap::new(),
         defined_fragments: HashSet::new(),
         current_scope: None,
     }
 }
 
+pub struct NoUnusedFragments<'a> {
+    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
+    defined_fragments: HashSet<Spanning<&'a str>>,
+    current_scope: Option<Scope<'a>>,
+}
+
 impl<'a> NoUnusedFragments<'a> {
-    fn find_reachable_fragments(&self, from: &Scope<'a>, result: &mut HashSet<&'a str>) {
+    fn find_reachable_fragments(&'a self, from: &Scope<'a>, result: &mut HashSet<&'a str>) {
+        let mut to_visit = Vec::new();
         if let Scope::Fragment(name) = *from {
-            if result.contains(name) {
-                return;
-            } else {
-                result.insert(name);
-            }
+            to_visit.push(name);
         }
 
-        if let Some(spreads) = self.spreads.get(from) {
-            for spread in spreads {
-                self.find_reachable_fragments(&Scope::Fragment(spread), result)
+        while let Some(from) = to_visit.pop() {
+            if let Some(next) = self.find_reachable_fragments_inner(from, result) {
+                to_visit.extend(next);
             }
         }
     }
+
+    /// This function should be called only inside
+    /// [`Self::find_reachable_fragments()`], as it's a recursive function using
+    /// heap instead of a stack. So, instead of the recursive call, we return a
+    /// [`Vec`] that is visited inside [`Self::find_reachable_fragments()`].
+    fn find_reachable_fragments_inner(
+        &'a self,
+        from: &'a str,
+        result: &mut HashSet<&'a str>,
+    ) -> Option<&'a Vec<&'a str>> {
+        if result.contains(from) {
+            return None;
+        } else {
+            result.insert(from);
+        }
+
+        self.spreads.get(&Scope::Fragment(from))
+    }
 }
 
 impl<'a, S> Visitor<'a, S> for NoUnusedFragments<'a>
 where
     S: ScalarValue,
diff --git a/juniper/src/validation/rules/no_unused_variables.rs b/juniper/src/validation/rules/no_unused_variables.rs
index 811acde5..81b7dfb3 100644
--- a/juniper/src/validation/rules/no_unused_variables.rs
+++ b/juniper/src/validation/rules/no_unused_variables.rs
@@ -10,36 +10,62 @@ use std::collections::{HashMap, HashSet};
 pub enum Scope<'a> {
     Operation(Option<&'a str>),
     Fragment(&'a str),
 }
 
-pub struct NoUnusedVariables<'a> {
-    defined_variables: HashMap<Option<&'a str>, HashSet<&'a Spanning<&'a str>>>,
-    used_variables: HashMap<Scope<'a>, Vec<&'a str>>,
-    current_scope: Option<Scope<'a>>,
-    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
-}
-
 pub fn factory<'a>() -> NoUnusedVariables<'a> {
     NoUnusedVariables {
         defined_variables: HashMap::new(),
         used_variables: HashMap::new(),
         current_scope: None,
         spreads: HashMap::new(),
     }
 }
 
+pub struct NoUnusedVariables<'a> {
+    defined_variables: HashMap<Option<&'a str>, HashSet<&'a Spanning<&'a str>>>,
+    used_variables: HashMap<Scope<'a>, Vec<&'a str>>,
+    current_scope: Option<Scope<'a>>,
+    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
+}
+
 impl<'a> NoUnusedVariables<'a> {
     fn find_used_vars(
-        &self,
+        &'a self,
         from: &Scope<'a>,
         defined: &HashSet<&'a str>,
         used: &mut HashSet<&'a str>,
         visited: &mut HashSet<Scope<'a>>,
     ) {
+        let mut to_visit = Vec::new();
+        if let Some(spreads) = self.find_used_vars_inner(from, defined, used, visited) {
+            to_visit.push(spreads);
+        }
+        while let Some(spreads) = to_visit.pop() {
+            for spread in spreads {
+                if let Some(spreads) =
+                    self.find_used_vars_inner(&Scope::Fragment(spread), defined, used, visited)
+                {
+                    to_visit.push(spreads);
+                }
+            }
+        }
+    }
+
+    /// This function should be called only inside [`Self::find_used_vars()`],
+    /// as it's a recursive function using heap instead of a stack. So, instead
+    /// of the recursive call, we return a [`Vec`] that is visited inside
+    /// [`Self::find_used_vars()`].
+    fn find_used_vars_inner(
+        &'a self,
+        from: &Scope<'a>,
+        defined: &HashSet<&'a str>,
+        used: &mut HashSet<&'a str>,
+        visited: &mut HashSet<Scope<'a>>,
+    ) -> Option<&'a Vec<&'a str>> {
         if visited.contains(from) {
-            return;
+            return None;
         }
 
         visited.insert(from.clone());
 
         if let Some(used_vars) = self.used_variables.get(from) {
@@ -48,15 +74,11 @@ impl<'a> NoUnusedVariables<'a> {
                     used.insert(var);
                 }
             }
         }
 
-        if let Some(spreads) = self.spreads.get(from) {
-            for spread in spreads {
-                self.find_used_vars(&Scope::Fragment(spread), defined, used, visited);
-            }
-        }
+        self.spreads.get(from)
     }
 }
 
 impl<'a, S> Visitor<'a, S> for NoUnusedVariables<'a>
 where
diff --git a/juniper/src/validation/rules/overlapping_fields_can_be_merged.rs b/juniper/src/validation/rules/overlapping_fields_can_be_merged.rs
index 5a9260b1..efacd1ce 100644
--- a/juniper/src/validation/rules/overlapping_fields_can_be_merged.rs
+++ b/juniper/src/validation/rules/overlapping_fields_can_be_merged.rs
@@ -272,34 +272,65 @@ impl<'a, S: Debug> OverlappingFieldsCanBeMerged<'a, S> {
         mutually_exclusive: bool,
         ctx: &ValidatorContext<'a, S>,
     ) where
         S: ScalarValue,
     {
-        let fragment = match self.named_fragments.get(fragment_name) {
-            Some(f) => f,
-            None => return,
-        };
+        let mut to_check = Vec::new();
+        if let Some(fragments) = self.collect_conflicts_between_fields_and_fragment_inner(
+            conflicts,
+            field_map,
+            fragment_name,
+            mutually_exclusive,
+            ctx,
+        ) {
+            to_check.push((fragment_name, fragments))
+        }
+
+        while let Some((fragment_name, fragment_names2)) = to_check.pop() {
+            for fragment_name2 in fragment_names2 {
+                // Early return on fragment recursion, as it makes no sense.
+                // Fragment recursions are prevented by `no_fragment_cycles` validator.
+                if fragment_name == fragment_name2 {
+                    return;
+                }
+                if let Some(fragments) = self.collect_conflicts_between_fields_and_fragment_inner(
+                    conflicts,
+                    field_map,
+                    fragment_name2,
+                    mutually_exclusive,
+                    ctx,
+                ) {
+                    to_check.push((fragment_name2, fragments));
+                };
+            }
+        }
+    }
+
+    /// This function should be called only inside
+    /// [`Self::collect_conflicts_between_fields_and_fragment()`], as it's a
+    /// recursive function using heap instead of a stack. So, instead of the
+    /// recursive call, we return a [`Vec`] that is visited inside
+    /// [`Self::collect_conflicts_between_fields_and_fragment()`].
+    fn collect_conflicts_between_fields_and_fragment_inner(
+        &self,
+        conflicts: &mut Vec<Conflict>,
+        field_map: &AstAndDefCollection<'a, S>,
+        fragment_name: &str,
+        mutually_exclusive: bool,
+        ctx: &ValidatorContext<'a, S>,
+    ) -> Option<Vec<&'a str>>
+    where
+        S: ScalarValue,
+    {
+        let fragment = self.named_fragments.get(fragment_name)?;
 
         let (field_map2, fragment_names2) =
             self.get_referenced_fields_and_fragment_names(fragment, ctx);
 
         self.collect_conflicts_between(conflicts, mutually_exclusive, field_map, &field_map2, ctx);
 
-        for fragment_name2 in fragment_names2 {
-            // Early return on fragment recursion, as it makes no sense.
-            // Fragment recursions are prevented by `no_fragment_cycles` validator.
-            if fragment_name == fragment_name2 {
-                return;
-            }
-            self.collect_conflicts_between_fields_and_fragment(
-                conflicts,
-                field_map,
-                fragment_name2,
-                mutually_exclusive,
-                ctx,
-            );
-        }
+        Some(fragment_names2)
     }
 
     fn collect_conflicts_between(
         &self,
         conflicts: &mut Vec<Conflict>,
diff --git a/juniper/src/validation/rules/variables_in_allowed_position.rs b/juniper/src/validation/rules/variables_in_allowed_position.rs
index 550b47a8..776f12db 100644
--- a/juniper/src/validation/rules/variables_in_allowed_position.rs
+++ b/juniper/src/validation/rules/variables_in_allowed_position.rs
@@ -15,37 +15,67 @@ use crate::{
 pub enum Scope<'a> {
     Operation(Option<&'a str>),
     Fragment(&'a str),
 }
 
-pub struct VariableInAllowedPosition<'a, S: fmt::Debug + 'a> {
-    spreads: HashMap<Scope<'a>, HashSet<&'a str>>,
-    variable_usages: HashMap<Scope<'a>, Vec<(Spanning<&'a String>, Type<'a>)>>,
-    #[allow(clippy::type_complexity)]
-    variable_defs: HashMap<Scope<'a>, Vec<&'a (Spanning<&'a str>, VariableDefinition<'a, S>)>>,
-    current_scope: Option<Scope<'a>>,
-}
-
 pub fn factory<'a, S: fmt::Debug>() -> VariableInAllowedPosition<'a, S> {
     VariableInAllowedPosition {
         spreads: HashMap::new(),
         variable_usages: HashMap::new(),
         variable_defs: HashMap::new(),
         current_scope: None,
     }
 }
 
+pub struct VariableInAllowedPosition<'a, S: fmt::Debug + 'a> {
+    spreads: HashMap<Scope<'a>, HashSet<&'a str>>,
+    variable_usages: HashMap<Scope<'a>, Vec<(Spanning<&'a String>, Type<'a>)>>,
+    #[allow(clippy::type_complexity)]
+    variable_defs: HashMap<Scope<'a>, Vec<&'a (Spanning<&'a str>, VariableDefinition<'a, S>)>>,
+    current_scope: Option<Scope<'a>>,
+}
+
 impl<'a, S: fmt::Debug> VariableInAllowedPosition<'a, S> {
-    fn collect_incorrect_usages(
-        &self,
+    fn collect_incorrect_usages<'me>(
+        &'me self,
         from: &Scope<'a>,
         var_defs: &[&'a (Spanning<&'a str>, VariableDefinition<S>)],
         ctx: &mut ValidatorContext<'a, S>,
         visited: &mut HashSet<Scope<'a>>,
     ) {
+        let mut to_visit = Vec::new();
+        if let Some(spreads) = self.collect_incorrect_usages_inner(from, var_defs, ctx, visited) {
+            to_visit.push(spreads);
+        }
+
+        while let Some(spreads) = to_visit.pop() {
+            for spread in spreads {
+                if let Some(spreads) = self.collect_incorrect_usages_inner(
+                    &Scope::Fragment(spread),
+                    var_defs,
+                    ctx,
+                    visited,
+                ) {
+                    to_visit.push(spreads);
+                }
+            }
+        }
+    }
+
+    /// This function should be called only inside
+    /// [`Self::collect_incorrect_usages()`], as it's a recursive function using
+    /// heap instead of a stack. So, instead of the recursive call, we return a
+    /// [`Vec`] that is visited inside [`Self::collect_incorrect_usages()`].
+    fn collect_incorrect_usages_inner<'me>(
+        &'me self,
+        from: &Scope<'a>,
+        var_defs: &[&'a (Spanning<&'a str>, VariableDefinition<S>)],
+        ctx: &mut ValidatorContext<'a, S>,
+        visited: &mut HashSet<Scope<'a>>,
+    ) -> Option<&'me HashSet<&'a str>> {
         if visited.contains(from) {
-            return;
+            return None;
         }
 
         visited.insert(from.clone());
 
         if let Some(usages) = self.variable_usages.get(from) {
@@ -72,15 +102,11 @@ impl<'a, S: fmt::Debug> VariableInAllowedPosition<'a, S> {
                     }
                 }
             }
         }
 
-        if let Some(spreads) = self.spreads.get(from) {
-            for spread in spreads {
-                self.collect_incorrect_usages(&Scope::Fragment(spread), var_defs, ctx, visited);
-            }
-        }
+        self.spreads.get(from)
     }
 }
 
 impl<'a, S> Visitor<'a, S> for VariableInAllowedPosition<'a, S>
 where
diff --git a/tests/integration/Cargo.toml b/tests/integration/Cargo.toml
index 041edf23..f339a718 100644
--- a/tests/integration/Cargo.toml
+++ b/tests/integration/Cargo.toml
@@ -8,10 +8,11 @@ publish = false
 async-trait = "0.1.39"
 chrono = "0.4"
 derive_more = "0.99"
 fnv = "1.0"
 futures = "0.3"
+itertools = "0.10"
 juniper = { path = "../../juniper" }
 juniper_subscriptions = { path = "../../juniper_subscriptions" }
 serde = { version = "1.0", features = ["derive"] }
 serde_json = "1.0"
 tokio = { version = "1.0", features = ["rt", "macros", "time"] }
diff --git a/tests/integration/tests/cve_2022_31173.rs b/tests/integration/tests/cve_2022_31173.rs
new file mode 100644
index 00000000..332306a3
--- /dev/null
+++ b/tests/integration/tests/cve_2022_31173.rs
@@ -0,0 +1,56 @@
+//! Checks that long looping chain of fragments doesn't cause a stack overflow.
+//!
+//! ```graphql
+//! # Fragment loop example
+//! query {
+//!     ...a
+//! }
+//!
+//! fragment a on Query {
+//!     ...b
+//! }
+//!
+//! fragment b on Query {
+//!     ...a
+//! }
+//! ```
+
+use std::iter;
+
+use itertools::Itertools as _;
+use juniper::{graphql_object, graphql_vars, EmptyMutation, EmptySubscription};
+
+struct Query;
+
+#[graphql_object]
+impl Query {
+    fn dummy() -> bool {
+        false
+    }
+}
+
+type Schema = juniper::RootNode<'static, Query, EmptyMutation, EmptySubscription>;
+
+#[tokio::test]
+async fn test() {
+    const PERM: &str = "abcefghijk";
+    const CIRCLE_SIZE: usize = 7500;
+
+    let query = iter::once(format!("query {{ ...{PERM} }} "))
+        .chain(
+            PERM.chars()
+                .permutations(PERM.len())
+                .map(|vec| vec.into_iter().collect::<String>())
+                .take(CIRCLE_SIZE)
+                .collect::<Vec<_>>()
+                .into_iter()
+                .circular_tuple_windows::<(_, _)>()
+                .map(|(cur, next)| format!("fragment {cur} on Query {{ ...{next} }} ")),
+        )
+        .collect::<String>();
+
+    let schema = Schema::new(Query, EmptyMutation::new(), EmptySubscription::new());
+    let _ = juniper::execute(&query, None, &schema, &graphql_vars! {}, &())
+        .await
+        .unwrap_err();
+}

Vulnerable code: pub struct NoFragmentCycles<'a> {
    current_fragment: Option<&'a str>,
    spreads: HashMap<&'a str, Vec<Spanning<&'a str>>>,
    fragment_order: Vec<&'a str>,
}

struct CycleDetector<'a> {
    visited: HashSet<&'a str>,
    spreads: &'a HashMap<&'a str, Vec<Spanning<&'a str>>>,
    path_indices: HashMap<&'a str, usize>,
    errors: Vec<RuleError>,
}

            path_indices: HashMap::new(),
                let mut path = Vec::new();
                detector.detect_from(frag, &mut path);
    fn detect_from(&mut self, from: &'a str, path: &mut Vec<&'a Spanning<&'a str>>) {
            return;
        self.path_indices.insert(from, path.len());
            let name = &node.item;
            let index = self.path_indices.get(name).cloned();
            } else if !self.visited.contains(name) {
                self.detect_from(name, path);
                path.pop();
        self.path_indices.remove(from);
pub struct NoUndefinedVariables<'a> {
    defined_variables: HashMap<Option<&'a str>, (SourcePosition, HashSet<&'a str>)>,
    used_variables: HashMap<Scope<'a>, Vec<Spanning<&'a str>>>,
    current_scope: Option<Scope<'a>>,
    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
}

            return;
        if let Some(spreads) = self.spreads.get(scope) {
            for spread in spreads {
                self.find_undef_vars(&Scope::Fragment(spread), defined, unused, visited);
            }
        }
pub struct NoUnusedFragments<'a> {
    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
    defined_fragments: HashSet<Spanning<&'a str>>,
    current_scope: Option<Scope<'a>>,
}

    fn find_reachable_fragments(&self, from: &Scope<'a>, result: &mut HashSet<&'a str>) {
            if result.contains(name) {
                return;
            } else {
                result.insert(name);
            }
        if let Some(spreads) = self.spreads.get(from) {
            for spread in spreads {
                self.find_reachable_fragments(&Scope::Fragment(spread), result)
pub struct NoUnusedVariables<'a> {
    defined_variables: HashMap<Option<&'a str>, HashSet<&'a Spanning<&'a str>>>,
    used_variables: HashMap<Scope<'a>, Vec<&'a str>>,
    current_scope: Option<Scope<'a>>,
    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
}

        &self,
            return;
        if let Some(spreads) = self.spreads.get(from) {
            for spread in spreads {
                self.find_used_vars(&Scope::Fragment(spread), defined, used, visited);
            }
        }
        let fragment = match self.named_fragments.get(fragment_name) {
            Some(f) => f,
            None => return,
        };
        for fragment_name2 in fragment_names2 {
            // Early return on fragment recursion, as it makes no sense.
            // Fragment recursions are prevented by `no_fragment_cycles` validator.
            if fragment_name == fragment_name2 {
                return;
            }
            self.collect_conflicts_between_fields_and_fragment(
                conflicts,
                field_map,
                fragment_name2,
                mutually_exclusive,
                ctx,
            );
        }
pub struct VariableInAllowedPosition<'a, S: fmt::Debug + 'a> {
    spreads: HashMap<Scope<'a>, HashSet<&'a str>>,
    variable_usages: HashMap<Scope<'a>, Vec<(Spanning<&'a String>, Type<'a>)>>,
    #[allow(clippy::type_complexity)]
    variable_defs: HashMap<Scope<'a>, Vec<&'a (Spanning<&'a str>, VariableDefinition<'a, S>)>>,
    current_scope: Option<Scope<'a>>,
}

    fn collect_incorrect_usages(
        &self,
            return;
        if let Some(spreads) = self.spreads.get(from) {
            for spread in spreads {
                self.collect_incorrect_usages(&Scope::Fragment(spread), var_defs, ctx, visited);
            }
        }
Fixed code: pub struct NoFragmentCycles<'a> {
    current_fragment: Option<&'a str>,
    spreads: HashMap<&'a str, Vec<Spanning<&'a str>>>,
    fragment_order: Vec<&'a str>,
}

                detector.detect_from(frag);
type CycleDetectorState<'a> = (&'a str, Vec<&'a Spanning<&'a str>>, HashMap<&'a str, usize>);

struct CycleDetector<'a> {
    visited: HashSet<&'a str>,
    spreads: &'a HashMap<&'a str, Vec<Spanning<&'a str>>>,
    errors: Vec<RuleError>,
}

    fn detect_from(&mut self, from: &'a str) {
        let mut to_visit = Vec::new();
        to_visit.push((from, Vec::new(), HashMap::new()));

        while let Some((from, path, path_indices)) = to_visit.pop() {
            to_visit.extend(self.detect_from_inner(from, path, path_indices));
        }
    }

    /// This function should be called only inside [`Self::detect_from()`], as
    /// it's a recursive function using heap instead of a stack. So, instead of
    /// the recursive call, we return a [`Vec`] that is visited inside
    /// [`Self::detect_from()`].
    fn detect_from_inner(
        &mut self,
        from: &'a str,
        path: Vec<&'a Spanning<&'a str>>,
        mut path_indices: HashMap<&'a str, usize>,
    ) -> Vec<CycleDetectorState<'a>> {
            return Vec::new();
        path_indices.insert(from, path.len());
        let mut to_visit = Vec::new();
            let name = node.item;
            let index = path_indices.get(name).cloned();
            } else {
                let mut path = path.clone();
                to_visit.push((name, path, path_indices.clone()));
        to_visit
pub struct NoUndefinedVariables<'a> {
    defined_variables: HashMap<Option<&'a str>, (SourcePosition, HashSet<&'a str>)>,
    used_variables: HashMap<Scope<'a>, Vec<Spanning<&'a str>>>,
    current_scope: Option<Scope<'a>>,
    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
}

        let mut to_visit = Vec::new();
        if let Some(spreads) = self.find_undef_vars_inner(scope, defined, unused, visited) {
            to_visit.push(spreads);
        }
        while let Some(spreads) = to_visit.pop() {
            for spread in spreads {
                if let Some(spreads) =
                    self.find_undef_vars_inner(&Scope::Fragment(spread), defined, unused, visited)
                {
                    to_visit.push(spreads);
                }
            }
        }
    }

    /// This function should be called only inside [`Self::find_undef_vars()`],
    /// as it's a recursive function using heap instead of a stack. So, instead
    /// of the recursive call, we return a [`Vec`] that is visited inside
    /// [`Self::find_undef_vars()`].
    fn find_undef_vars_inner(
        &'a self,
        scope: &Scope<'a>,
        defined: &HashSet<&'a str>,
        unused: &mut Vec<&'a Spanning<&'a str>>,
        visited: &mut HashSet<Scope<'a>>,
    ) -> Option<&'a Vec<&'a str>> {
            return None;
        self.spreads.get(scope)
pub struct NoUnusedFragments<'a> {
    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
    defined_fragments: HashSet<Spanning<&'a str>>,
    current_scope: Option<Scope<'a>>,
}

    fn find_reachable_fragments(&'a self, from: &Scope<'a>, result: &mut HashSet<&'a str>) {
        let mut to_visit = Vec::new();
            to_visit.push(name);
        while let Some(from) = to_visit.pop() {
            if let Some(next) = self.find_reachable_fragments_inner(from, result) {
                to_visit.extend(next);

    /// This function should be called only inside
    /// [`Self::find_reachable_fragments()`], as it's a recursive function using
    /// heap instead of a stack. So, instead of the recursive call, we return a
    /// [`Vec`] that is visited inside [`Self::find_reachable_fragments()`].
    fn find_reachable_fragments_inner(
        &'a self,
        from: &'a str,
        result: &mut HashSet<&'a str>,
    ) -> Option<&'a Vec<&'a str>> {
        if result.contains(from) {
            return None;
        } else {
            result.insert(from);
        }

        self.spreads.get(&Scope::Fragment(from))
    }
pub struct NoUnusedVariables<'a> {
    defined_variables: HashMap<Option<&'a str>, HashSet<&'a Spanning<&'a str>>>,
    used_variables: HashMap<Scope<'a>, Vec<&'a str>>,
    current_scope: Option<Scope<'a>>,
    spreads: HashMap<Scope<'a>, Vec<&'a str>>,
}

        &'a self,
        let mut to_visit = Vec::new();
        if let Some(spreads) = self.find_used_vars_inner(from, defined, used, visited) {
            to_visit.push(spreads);
        }
        while let Some(spreads) = to_visit.pop() {
            for spread in spreads {
                if let Some(spreads) =
                    self.find_used_vars_inner(&Scope::Fragment(spread), defined, used, visited)
                {
                    to_visit.push(spreads);
                }
            }
        }
    }

    /// This function should be called only inside [`Self::find_used_vars()`],
    /// as it's a recursive function using heap instead of a stack. So, instead
    /// of the recursive call, we return a [`Vec`] that is visited inside
    /// [`Self::find_used_vars()`].
    fn find_used_vars_inner(
        &'a self,
        from: &Scope<'a>,
        defined: &HashSet<&'a str>,
        used: &mut HashSet<&'a str>,
        visited: &mut HashSet<Scope<'a>>,
    ) -> Option<&'a Vec<&'a str>> {
            return None;
        self.spreads.get(from)
        let mut to_check = Vec::new();
        if let Some(fragments) = self.collect_conflicts_between_fields_and_fragment_inner(
            conflicts,
            field_map,
            fragment_name,
            mutually_exclusive,
            ctx,
        ) {
            to_check.push((fragment_name, fragments))
        }

        while let Some((fragment_name, fragment_names2)) = to_check.pop() {
            for fragment_name2 in fragment_names2 {
                // Early return on fragment recursion, as it makes no sense.
                // Fragment recursions are prevented by `no_fragment_cycles` validator.
                if fragment_name == fragment_name2 {
                    return;
                }
                if let Some(fragments) = self.collect_conflicts_between_fields_and_fragment_inner(
                    conflicts,
                    field_map,
                    fragment_name2,
                    mutually_exclusive,
                    ctx,
                ) {
                    to_check.push((fragment_name2, fragments));
                };
            }
        }
    }

    /// This function should be called only inside
    /// [`Self::collect_conflicts_between_fields_and_fragment()`], as it's a
    /// recursive function using heap instead of a stack. So, instead of the
    /// recursive call, we return a [`Vec`] that is visited inside
    /// [`Self::collect_conflicts_between_fields_and_fragment()`].
    fn collect_conflicts_between_fields_and_fragment_inner(
        &self,
        conflicts: &mut Vec<Conflict>,
        field_map: &AstAndDefCollection<'a, S>,
        fragment_name: &str,
        mutually_exclusive: bool,
        ctx: &ValidatorContext<'a, S>,
    ) -> Option<Vec<&'a str>>
    where
        S: ScalarValue,
    {
        let fragment = self.named_fragments.get(fragment_name)?;
        Some(fragment_names2)
pub struct VariableInAllowedPosition<'a, S: fmt::Debug + 'a> {
    spreads: HashMap<Scope<'a>, HashSet<&'a str>>,
    variable_usages: HashMap<Scope<'a>, Vec<(Spanning<&'a String>, Type<'a>)>>,
    #[allow(clippy::type_complexity)]
    variable_defs: HashMap<Scope<'a>, Vec<&'a (Spanning<&'a str>, VariableDefinition<'a, S>)>>,
    current_scope: Option<Scope<'a>>,
}

    fn collect_incorrect_usages<'me>(
        &'me self,
        let mut to_visit = Vec::new();
        if let Some(spreads) = self.collect_incorrect_usages_inner(from, var_defs, ctx, visited) {
            to_visit.push(spreads);
        }

        while let Some(spreads) = to_visit.pop() {
            for spread in spreads {
                if let Some(spreads) = self.collect_incorrect_usages_inner(
                    &Scope::Fragment(spread),
                    var_defs,
                    ctx,
                    visited,
                ) {
                    to_visit.push(spreads);
                }
            }
        }
    }

    /// This function should be called only inside
    /// [`Self::collect_incorrect_usages()`], as it's a recursive function using
    /// heap instead of a stack. So, instead of the recursive call, we return a
    /// [`Vec`] that is visited inside [`Self::collect_incorrect_usages()`].
    fn collect_incorrect_usages_inner<'me>(
        &'me self,
        from: &Scope<'a>,
        var_defs: &[&'a (Spanning<&'a str>, VariableDefinition<S>)],
        ctx: &mut ValidatorContext<'a, S>,
        visited: &mut HashSet<Scope<'a>>,
    ) -> Option<&'me HashSet<&'a str>> {
            return None;
        self.spreads.get(from)
itertools = "0.10"
//! Checks that long looping chain of fragments doesn't cause a stack overflow.
//!
//! ```graphql
//! # Fragment loop example
//! query {
//!     ...a
//! }
//!
//! fragment a on Query {
//!     ...b
//! }
//!
//! fragment b on Query {
//!     ...a
//! }
//! ```

use std::iter;

use itertools::Itertools as _;
use juniper::{graphql_object, graphql_vars, EmptyMutation, EmptySubscription};

struct Query;

#[graphql_object]
impl Query {
    fn dummy() -> bool {
        false
    }
}

type Schema = juniper::RootNode<'static, Query, EmptyMutation, EmptySubscription>;

#[tokio::test]
async fn test() {
    const PERM: &str = "abcefghijk";
    const CIRCLE_SIZE: usize = 7500;

    let query = iter::once(format!("query {{ ...{PERM} }} "))
        .chain(
            PERM.chars()
                .permutations(PERM.len())
                .map(|vec| vec.into_iter().collect::<String>())
                .take(CIRCLE_SIZE)
                .collect::<Vec<_>>()
                .into_iter()
                .circular_tuple_windows::<(_, _)>()
                .map(|(cur, next)| format!("fragment {cur} on Query {{ ...{next} }} ")),
        )
        .collect::<String>();

    let schema = Schema::new(Query, EmptyMutation::new(), EmptySubscription::new());
    let _ = juniper::execute(&query, None, &schema, &graphql_vars! {}, &())
        .await
        .unwrap_err();
}