Repository: apollographql/apollo-rs
Pull request #518 (2023-04-06 07:40:03)

feat(compiler): validate fragment definitions do not contain cycles
Previously i added a test in the `ok` folder that asserted the opposite of this PR, because I was looking at a different part of the spec, where fragments are applied. When fragment spreads are used you just need to account for recursion so you don't overflow the stack, there's no check for recursive spreads there. That check is instead done when *defining* a fragment, and that's what this PR adds 😄 

It works the same as other recursion validations, with a `RecursionStack` and only reporting a validation error if the first item matches (so you only get relevant errors).


Patch:
diff --git a/crates/apollo-compiler/src/database/hir.rs b/crates/apollo-compiler/src/database/hir.rs
index d623760..c6fa110 100644
--- a/crates/apollo-compiler/src/database/hir.rs
+++ b/crates/apollo-compiler/src/database/hir.rs
@@ -420,6 +420,19 @@ impl FragmentDefinition {
     pub fn loc(&self) -> HirNodeLocation {
         self.loc
     }
+
+    /// Get the location information for the "head" of the fragment definition, namely the
+    /// `fragment` keyword and the name.
+    pub(crate) fn head_loc(&self) -> HirNodeLocation {
+        self.name_src()
+            .loc()
+            .map(|name_loc| HirNodeLocation {
+                // Adjust the node length to include the name
+                node_len: name_loc.end_offset() - self.loc.offset(),
+                ..self.loc
+            })
+            .unwrap_or(self.loc)
+    }
 }
 
 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
diff --git a/crates/apollo-compiler/src/diagnostics.rs b/crates/apollo-compiler/src/diagnostics.rs
index 987a3a9..36ae99a 100644
--- a/crates/apollo-compiler/src/diagnostics.rs
+++ b/crates/apollo-compiler/src/diagnostics.rs
@@ -201,6 +201,8 @@ pub enum DiagnosticData {
     RecursiveInterfaceDefinition { name: String },
     #[error("`{name}` input object cannot reference itself")]
     RecursiveInputObjectDefinition { name: String },
+    #[error("`{name}` fragment cannot reference itself")]
+    RecursiveFragmentDefinition { name: String },
     #[error("values in an Enum Definition should be capitalized")]
     CapitalizedValue { value: String },
     #[error("fields must be unique in a definition")]
diff --git a/crates/apollo-compiler/src/validation/fragment.rs b/crates/apollo-compiler/src/validation/fragment.rs
index d20fb5c..c0e7f4d 100644
--- a/crates/apollo-compiler/src/validation/fragment.rs
+++ b/crates/apollo-compiler/src/validation/fragment.rs
@@ -1,6 +1,8 @@
 use crate::{
     diagnostics::{ApolloDiagnostic, DiagnosticData, Label},
-    hir, FileId, ValidationDatabase,
+    hir,
+    validation::RecursionStack,
+    FileId, ValidationDatabase,
 };
 use std::sync::Arc;
 
@@ -48,7 +50,72 @@ pub fn validate_fragment_definitions(
             db.validate_fragment_type_condition(Some(def.type_condition().to_string()), def.loc()),
         );
         diagnostics.extend(db.validate_selection_set(def.selection_set().clone()));
-        diagnostics.extend(db.validate_fragment_used(def.as_ref().clone(), file_id));
+        diagnostics.extend(db.validate_fragment_used(Arc::clone(def), file_id));
+
+        diagnostics.extend(db.validate_fragment_cycles(Arc::clone(def)));
+    }
+
+    diagnostics
+}
+
+pub fn validate_fragment_cycles(
+    db: &dyn ValidationDatabase,
+    def: Arc<hir::FragmentDefinition>,
+) -> Vec<ApolloDiagnostic> {
+    let mut diagnostics = Vec::new();
+
+    fn detect_fragment_cycles(
+        db: &dyn ValidationDatabase,
+        selection_set: &hir::SelectionSet,
+        visited: &mut RecursionStack<'_>,
+    ) -> Result<(), hir::Selection> {
+        for selection in selection_set.selection() {
+            match selection {
+                hir::Selection::FragmentSpread(spread) => {
+                    if visited.contains(spread.name()) {
+                        if visited.first() == Some(spread.name()) {
+                            return Err(selection.clone());
+                        }
+                        continue;
+                    }
+
+                    if let Some(fragment) =
+                        db.find_fragment_by_name(spread.loc().file_id(), spread.name().to_string())
+                    {
+                        detect_fragment_cycles(
+                            db,
+                            fragment.selection_set(),
+                            &mut visited.push(fragment.name().to_string()),
+                        )?;
+                    }
+                }
+                hir::Selection::InlineFragment(inline) => {
+                    detect_fragment_cycles(db, inline.selection_set(), visited)?;
+                }
+                _ => {}
+            }
+        }
+
+        Ok(())
+    }
+
+    // Split RecursionStack initialisation for lifetime reasons
+    let mut visited = vec![];
+    let mut visited = RecursionStack(&mut visited);
+    let mut visited = visited.push(def.name().to_string());
+
+    if let Err(cycle) = detect_fragment_cycles(db, def.selection_set(), &mut visited) {
+        diagnostics.push(
+            ApolloDiagnostic::new(
+                db,
+                def.loc().into(),
+                DiagnosticData::RecursiveFragmentDefinition {
+                    name: def.name().to_string(),
+                },
+            )
+            .label(Label::new(def.head_loc(), "recursive fragment definition"))
+            .label(Label::new(cycle.loc(), "refers to itself here")),
+        );
     }
 
     diagnostics
@@ -127,7 +194,7 @@ pub fn validate_fragment_type_condition(
 
 pub fn validate_fragment_used(
     db: &dyn ValidationDatabase,
-    def: hir::FragmentDefinition,
+    def: Arc<hir::FragmentDefinition>,
     file_id: FileId,
 ) -> Vec<ApolloDiagnostic> {
     let mut diagnostics = Vec::new();
diff --git a/crates/apollo-compiler/src/validation/validation_db.rs b/crates/apollo-compiler/src/validation/validation_db.rs
index accf309..159d986 100644
--- a/crates/apollo-compiler/src/validation/validation_db.rs
+++ b/crates/apollo-compiler/src/validation/validation_db.rs
@@ -173,6 +173,9 @@ pub trait ValidationDatabase:
     #[salsa::invoke(fragment::validate_fragment_definitions)]
     fn validate_fragment_definitions(&self, file_id: FileId) -> Vec<ApolloDiagnostic>;
 
+    #[salsa::invoke(fragment::validate_fragment_cycles)]
+    fn validate_fragment_cycles(&self, def: Arc<FragmentDefinition>) -> Vec<ApolloDiagnostic>;
+
     #[salsa::invoke(fragment::validate_fragment_type_condition)]
     fn validate_fragment_type_condition(
         &self,
@@ -183,7 +186,7 @@ pub trait ValidationDatabase:
     #[salsa::invoke(fragment::validate_fragment_used)]
     fn validate_fragment_used(
         &self,
-        def: FragmentDefinition,
+        def: Arc<FragmentDefinition>,
         file_id: FileId,
     ) -> Vec<ApolloDiagnostic>;
 


Test patch:
diff --git a/crates/apollo-compiler/test_data/ok/0023_recursive_fragment.graphql b/crates/apollo-compiler/test_data/diagnostics/0092_recursive_fragment_spread.graphql
similarity index 100%
rename from crates/apollo-compiler/test_data/ok/0023_recursive_fragment.graphql
rename to crates/apollo-compiler/test_data/diagnostics/0092_recursive_fragment_spread.graphql
diff --git a/crates/apollo-compiler/test_data/diagnostics/0092_recursive_fragment_spread.txt b/crates/apollo-compiler/test_data/diagnostics/0092_recursive_fragment_spread.txt
new file mode 100644
index 0000000..0fd22ac
--- /dev/null
+++ b/crates/apollo-compiler/test_data/diagnostics/0092_recursive_fragment_spread.txt
@@ -0,0 +1,119 @@
+[
+    ApolloDiagnostic {
+        cache: {
+            0: "built_in_types.graphql",
+            87: "0092_recursive_fragment_spread.graphql",
+        },
+        location: DiagnosticLocation {
+            file_id: FileId {
+                id: 87,
+            },
+            offset: 104,
+            length: 42,
+        },
+        labels: [
+            Label {
+                location: DiagnosticLocation {
+                    file_id: FileId {
+                        id: 87,
+                    },
+                    offset: 104,
+                    length: 14,
+                },
+                text: "recursive fragment definition",
+            },
+            Label {
+                location: DiagnosticLocation {
+                    file_id: FileId {
+                        id: 87,
+                    },
+                    offset: 222,
+                    length: 8,
+                },
+                text: "refers to itself here",
+            },
+        ],
+        help: None,
+        data: RecursiveFragmentDefinition {
+            name: "fragA",
+        },
+    },
+    ApolloDiagnostic {
+        cache: {
+            0: "built_in_types.graphql",
+            87: "0092_recursive_fragment_spread.graphql",
+        },
+        location: DiagnosticLocation {
+            file_id: FileId {
+                id: 87,
+            },
+            offset: 147,
+            length: 42,
+        },
+        labels: [
+            Label {
+                location: DiagnosticLocation {
+                    file_id: FileId {
+                        id: 87,
+                    },
+                    offset: 147,
+                    length: 14,
+                },
+                text: "recursive fragment definition",
+            },
+            Label {
+                location: DiagnosticLocation {
+                    file_id: FileId {
+                        id: 87,
+                    },
+                    offset: 136,
+                    length: 8,
+                },
+                text: "refers to itself here",
+            },
+        ],
+        help: None,
+        data: RecursiveFragmentDefinition {
+            name: "fragB",
+        },
+    },
+    ApolloDiagnostic {
+        cache: {
+            0: "built_in_types.graphql",
+            87: "0092_recursive_fragment_spread.graphql",
+        },
+        location: DiagnosticLocation {
+            file_id: FileId {
+                id: 87,
+            },
+            offset: 190,
+            length: 42,
+        },
+        labels: [
+            Label {
+                location: DiagnosticLocation {
+                    file_id: FileId {
+                        id: 87,
+                    },
+                    offset: 190,
+                    length: 14,
+                },
+                text: "recursive fragment definition",
+            },
+            Label {
+                location: DiagnosticLocation {
+                    file_id: FileId {
+                        id: 87,
+                    },
+                    offset: 179,
+                    length: 8,
+                },
+                text: "refers to itself here",
+            },
+        ],
+        help: None,
+        data: RecursiveFragmentDefinition {
+            name: "fragC",
+        },
+    },
+]
diff --git a/crates/apollo-compiler/test_data/ok/0023_recursive_fragment.txt b/crates/apollo-compiler/test_data/ok/0023_recursive_fragment.txt
deleted file mode 100644
index 172f525..0000000
--- a/crates/apollo-compiler/test_data/ok/0023_recursive_fragment.txt
+++ /dev/null
@@ -1,159 +0,0 @@
-- DOCUMENT@0..233
-    - COMMENT@0..8 "# Schema"
-    - WHITESPACE@8..9 "\n"
-    - OBJECT_TYPE_DEFINITION@9..39
-        - type_KW@9..13 "type"
-        - WHITESPACE@13..14 " "
-        - NAME@14..19
-            - IDENT@14..19 "Human"
-        - WHITESPACE@19..20 " "
-        - FIELDS_DEFINITION@20..39
-            - L_CURLY@20..21 "{"
-            - WHITESPACE@21..24 "\n  "
-            - FIELD_DEFINITION@24..37
-                - NAME@24..28
-                    - IDENT@24..28 "name"
-                - COLON@28..29 ":"
-                - WHITESPACE@29..30 " "
-                - NON_NULL_TYPE@30..37
-                    - NAMED_TYPE@30..36
-                        - NAME@30..36
-                            - IDENT@30..36 "String"
-                    - BANG@36..37 "!"
-            - WHITESPACE@37..38 "\n"
-            - R_CURLY@38..39 "}"
-    - WHITESPACE@39..40 "\n"
-    - OBJECT_TYPE_DEFINITION@40..69
-        - type_KW@40..44 "type"
-        - WHITESPACE@44..45 " "
-        - NAME@45..50
-            - IDENT@45..50 "Query"
-        - WHITESPACE@50..51 " "
-        - FIELDS_DEFINITION@51..69
-            - L_CURLY@51..52 "{"
-            - WHITESPACE@52..55 "\n  "
-            - FIELD_DEFINITION@55..67
-                - NAME@55..60
-                    - IDENT@55..60 "human"
-                - COLON@60..61 ":"
-                - WHITESPACE@61..62 " "
-                - NAMED_TYPE@62..67
-                    - NAME@62..67
-                        - IDENT@62..67 "Human"
-            - WHITESPACE@67..68 "\n"
-            - R_CURLY@68..69 "}"
-    - WHITESPACE@69..71 "\n\n"
-    - COMMENT@71..78 "# Query"
-    - WHITESPACE@78..79 "\n"
-    - OPERATION_DEFINITION@79..103
-        - SELECTION_SET@79..103
-            - L_CURLY@79..80 "{"
-            - WHITESPACE@80..83 "\n  "
-            - FIELD@83..101
-                - NAME@83..88
-                    - IDENT@83..88 "human"
-                - WHITESPACE@88..89 " "
-                - SELECTION_SET@89..101
-                    - L_CURLY@89..90 "{"
-                    - WHITESPACE@90..91 " "
-                    - FRAGMENT_SPREAD@91..99
-                        - SPREAD@91..94 "..."
-                        - FRAGMENT_NAME@94..99
-                            - NAME@94..99
-                                - IDENT@94..99 "fragA"
-                    - WHITESPACE@99..100 " "
-                    - R_CURLY@100..101 "}"
-            - WHITESPACE@101..102 "\n"
-            - R_CURLY@102..103 "}"
-    - WHITESPACE@103..104 "\n"
-    - FRAGMENT_DEFINITION@104..146
-        - fragment_KW@104..112 "fragment"
-        - WHITESPACE@112..113 " "
-        - FRAGMENT_NAME@113..118
-            - NAME@113..118
-                - IDENT@113..118 "fragA"
-        - WHITESPACE@118..119 " "
-        - TYPE_CONDITION@119..127
-            - on_KW@119..121 "on"
-            - WHITESPACE@121..122 " "
-            - NAMED_TYPE@122..127
-                - NAME@122..127
-                    - IDENT@122..127 "Human"
-        - WHITESPACE@127..128 " "
-        - SELECTION_SET@128..146
-            - L_CURLY@128..129 "{"
-            - WHITESPACE@129..130 " "
-            - FIELD@130..134
-                - NAME@130..134
-                    - IDENT@130..134 "name"
-            - COMMA@134..135 ","
-            - WHITESPACE@135..136 " "
-            - FRAGMENT_SPREAD@136..144
-                - SPREAD@136..139 "..."
-                - FRAGMENT_NAME@139..144
-                    - NAME@139..144
-                        - IDENT@139..144 "fragB"
-            - WHITESPACE@144..145 " "
-            - R_CURLY@145..146 "}"
-    - WHITESPACE@146..147 "\n"
-    - FRAGMENT_DEFINITION@147..189
-        - fragment_KW@147..155 "fragment"
-        - WHITESPACE@155..156 " "
-        - FRAGMENT_NAME@156..161
-            - NAME@156..161
-                - IDENT@156..161 "fragB"
-        - WHITESPACE@161..162 " "
-        - TYPE_CONDITION@162..170
-            - on_KW@162..164 "on"
-            - WHITESPACE@164..165 " "
-            - NAMED_TYPE@165..170
-                - NAME@165..170
-                    - IDENT@165..170 "Human"
-        - WHITESPACE@170..171 " "
-        - SELECTION_SET@171..189
-            - L_CURLY@171..172 "{"
-            - WHITESPACE@172..173 " "
-            - FIELD@173..177
-                - NAME@173..177
-                    - IDENT@173..177 "name"
-            - COMMA@177..178 ","
-            - WHITESPACE@178..179 " "
-            - FRAGMENT_SPREAD@179..187
-                - SPREAD@179..182 "..."
-                - FRAGMENT_NAME@182..187
-                    - NAME@182..187
-                        - IDENT@182..187 "fragC"
-            - WHITESPACE@187..188 " "
-            - R_CURLY@188..189 "}"
-    - WHITESPACE@189..190 "\n"
-    - FRAGMENT_DEFINITION@190..232
-        - fragment_KW@190..198 "fragment"
-        - WHITESPACE@198..199 " "
-        - FRAGMENT_NAME@199..204
-            - NAME@199..204
-                - IDENT@199..204 "fragC"
-        - WHITESPACE@204..205 " "
-        - TYPE_CONDITION@205..213
-            - on_KW@205..207 "on"
-            - WHITESPACE@207..208 " "
-            - NAMED_TYPE@208..213
-                - NAME@208..213
-                    - IDENT@208..213 "Human"
-        - WHITESPACE@213..214 " "
-        - SELECTION_SET@214..232
-            - L_CURLY@214..215 "{"
-            - WHITESPACE@215..216 " "
-            - FIELD@216..220
-                - NAME@216..220
-                    - IDENT@216..220 "name"
-            - COMMA@220..221 ","
-            - WHITESPACE@221..222 " "
-            - FRAGMENT_SPREAD@222..230
-                - SPREAD@222..225 "..."
-                - FRAGMENT_NAME@225..230
-                    - NAME@225..230
-                        - IDENT@225..230 "fragA"
-            - WHITESPACE@230..231 " "
-            - R_CURLY@231..232 "}"
-    - WHITESPACE@232..233 "\n"
-recursion limit: 4096, high: 3