Repository: oxidecomputer/typify
Pull request #410 (2023-09-24 21:01:39)

fix stack overflow; improve `not` subschema handling
A schema like this will recur infinitely:

```json
    {
      "type": "object",
      "properties": {
        "this": {},
        "that": {}
      },
      "not": {
        "required": [
          "that"
        ]
      }
    }
```

This includes logic to handle this type of `not` by "subtracting" it out from the other schema.

In addition, we now handle constructs like this:

```json
    {
      "type": "object",
      "properties": {
        "a": {},
        "b": {},
        "c": {}
      },
      "required": [
        "a"
      ],
      "not": {
        "anyOf": [
          {
            "required": [
              "b"
            ]
          },
          {
            "required": [
              "c"
            ]
          }
        ]
      }
    }
```

We reduce a `not` of `anyOf` to an `allOf` of `not` which we can then "subtract" out as above.


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index e1b63ea..7a582e0 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1176,6 +1176,7 @@ name = "typify"
 version = "0.0.13"
 dependencies = [
  "chrono",
+ "env_logger",
  "expectorate",
  "glob",
  "quote",
diff --git a/typify-impl/src/convert.rs b/typify-impl/src/convert.rs
index df48ed4..2d85b85 100644
--- a/typify-impl/src/convert.rs
+++ b/typify-impl/src/convert.rs
@@ -1237,6 +1237,16 @@ impl TypeSpace {
         metadata: &'a Option<Box<schemars::schema::Metadata>>,
         subschemas: &'a [Schema],
     ) -> Result<(TypeEntry, &'a Option<Box<Metadata>>)> {
+        // TODO it would probably be smart to do a pass through the schema
+        // given to us and either put it into some canonical form or move to
+        // some sort of intermediate representation.
+        //
+        // Each of the enum types does some similar exploration of each
+        // variant-schema--it should be possible to do that once. In addition
+        // the various enum types rely on some heuristics around how schemas
+        // are laid out; it would be nice to eliminate some of the guesswork,
+        // but putting schemas into a predictable form.
+
         let ty = self
             .maybe_option(type_name.clone(), metadata, subschemas)
             .or_else(|| self.maybe_externally_tagged_enum(type_name.clone(), metadata, subschemas))
diff --git a/typify-impl/src/merge.rs b/typify-impl/src/merge.rs
index ed86d03..42be322 100644
--- a/typify-impl/src/merge.rs
+++ b/typify-impl/src/merge.rs
@@ -5,6 +5,7 @@ use std::{
     iter::repeat,
 };
 
+use log::debug;
 use schemars::schema::{
     ArrayValidation, InstanceType, NumberValidation, ObjectValidation, Schema, SchemaObject,
     SingleOrVec, StringValidation, SubschemaValidation,
@@ -84,7 +85,7 @@ fn try_merge_schema(a: &Schema, b: &Schema, defs: &BTreeMap<RefKey, Schema>) ->
             try_merge_schema(resolved, other, defs)
         }
 
-        (Schema::Object(aa), Schema::Object(bb)) => merge_schema_object(aa, bb, defs),
+        (Schema::Object(aa), Schema::Object(bb)) => Ok(merge_schema_object(aa, bb, defs)?.into()),
     }
 }
 
@@ -92,7 +93,13 @@ fn merge_schema_object(
     a: &SchemaObject,
     b: &SchemaObject,
     defs: &BTreeMap<RefKey, Schema>,
-) -> Result<Schema, ()> {
+) -> Result<SchemaObject, ()> {
+    debug!(
+        "merging {}\n{}",
+        serde_json::to_string_pretty(a).unwrap(),
+        serde_json::to_string_pretty(b).unwrap(),
+    );
+
     assert!(a.reference.is_none());
     assert!(b.reference.is_none());
 
@@ -138,8 +145,13 @@ fn merge_schema_object(
         b.const_value.as_ref(),
     )?;
 
+    debug!(
+        "merged {}",
+        serde_json::to_string_pretty(&merged_schema).unwrap(),
+    );
+
     match enum_values {
-        None => Ok(merged_schema.into()),
+        None => Ok(merged_schema),
         Some(enum_values) => {
             let enum_values = enum_values
                 .into_iter()
@@ -154,8 +166,7 @@ fn merge_schema_object(
                 Ok(SchemaObject {
                     enum_values: Some(enum_values),
                     ..merged_schema
-                }
-                .into())
+                })
             }
         }
     }
@@ -206,11 +217,16 @@ pub(crate) fn merge_with_subschemas(
     try_merge_with_subschemas(schema_object, maybe_subschemas, defs).unwrap()
 }
 
+/// Merge the schema with a subschema validation object. It's important that
+/// the return value reduces the complexity of the problem so avoid infinite
+/// recursion.
 fn try_merge_with_subschemas(
     schema_object: SchemaObject,
     maybe_subschemas: Option<&SubschemaValidation>,
     defs: &BTreeMap<RefKey, Schema>,
 ) -> Result<SchemaObject, ()> {
+    // TODO conceivably these different subschema types could appear at the
+    // same time; maybe it's fine to just handle them distinctly?
     match maybe_subschemas {
         Some(SubschemaValidation {
             all_of: Some(all_of),
@@ -293,6 +309,16 @@ fn try_merge_with_subschemas(
             })
         }
 
+        Some(SubschemaValidation {
+            all_of: None,
+            any_of: None,
+            one_of: None,
+            not: Some(not),
+            if_schema: None,
+            then_schema: None,
+            else_schema: None,
+        }) => try_merge_schema_not(schema_object, not.as_ref(), defs),
+
         // If it's any of the subschemas we don't know how to handle here,
         // we'll try to leave them in place... probably to encounter an error
         // later when we try to convert them...
@@ -300,25 +326,12 @@ fn try_merge_with_subschemas(
             all_of: None,
             any_of: None,
             one_of: None,
-            not,
+            not: None,
             if_schema,
             then_schema,
             else_schema,
-        }) if not.is_some()
-            || if_schema.is_some()
-            || then_schema.is_some()
-            || else_schema.is_some() =>
-        {
-            if let Some(ss) = &schema_object.subschemas {
-                assert!(ss.not.is_none());
-                assert!(ss.if_schema.is_none());
-                assert!(ss.then_schema.is_none());
-                assert!(ss.else_schema.is_none());
-            }
-            Ok(SchemaObject {
-                subschemas: maybe_subschemas.cloned().map(Box::new),
-                ..schema_object
-            })
+        }) if if_schema.is_some() || then_schema.is_some() || else_schema.is_some() => {
+            unimplemented!("if/then/else schemas are not supported")
         }
 
         Some(unknown) => {
@@ -328,6 +341,130 @@ fn try_merge_with_subschemas(
     }
 }
 
+/// "Subtract" the "not" schema from the schema object.
+///
+/// TODO Exactly where and how we handle not constructions is... tricky! As we
+/// find and support more and more useful uses of not we will likely move some
+/// of this into the conversion methods.
+fn try_merge_schema_not(
+    mut schema_object: SchemaObject,
+    not_schema: &Schema,
+    defs: &BTreeMap<RefKey, Schema>,
+) -> Result<SchemaObject, ()> {
+    match not_schema {
+        // Subtracting everything leaves nothing...
+        Schema::Bool(true) => Err(()),
+        // ... whereas subtracting nothing leaves everything.
+        Schema::Bool(false) => Ok(schema_object),
+
+        Schema::Object(SchemaObject {
+            metadata: None,
+            instance_type: None,
+            format: None,
+            enum_values: None,
+            const_value: None,
+            subschemas: None,
+            number: None,
+            string: None,
+            array: None,
+            object: Some(not_object),
+            reference: None,
+            extensions: _,
+        }) => {
+            // TODO this is incomplete, but seems sufficient for the schemas
+            // we've seen in the wild.
+            if let Some(ObjectValidation {
+                required,
+                properties,
+                ..
+            }) = schema_object.object.as_deref_mut()
+            {
+                not_object.required.iter().for_each(|not_required| {
+                    let _ = required.remove(not_required);
+                    let _ = properties.remove(not_required);
+                });
+            }
+
+            Ok(schema_object)
+        }
+
+        Schema::Object(SchemaObject {
+            metadata: None,
+            instance_type: None,
+            format: None,
+            enum_values: None,
+            const_value: None,
+            subschemas: Some(not_subschemas),
+            number: None,
+            string: None,
+            array: None,
+            object: None,
+            reference: None,
+            extensions: _,
+        }) => try_merge_with_subschemas_not(schema_object, not_subschemas, defs),
+
+        // If we can't usefully reduce the complexity, leave it for the
+        // coversion pass.
+        _ => {
+            schema_object.subschemas().not = Some(Box::new(not_schema.clone()));
+            Ok(schema_object)
+        }
+    }
+}
+
+fn try_merge_with_subschemas_not(
+    schema_object: SchemaObject,
+    not_subschemas: &SubschemaValidation,
+    defs: &BTreeMap<RefKey, Schema>,
+) -> Result<SchemaObject, ()> {
+    match not_subschemas {
+        SubschemaValidation {
+            all_of: None,
+            any_of: Some(any_of),
+            one_of: None,
+            not: None,
+            if_schema: None,
+            then_schema: None,
+            else_schema: None,
+        } => {
+            // A not of anyOf is equivalent to an allOf of not... and the
+            // latter is easier to merge with other schemas by subtraction.
+            let all_of = any_of
+                .iter()
+                .map(|ss| {
+                    Schema::Object(SchemaObject {
+                        subschemas: Some(Box::new(SubschemaValidation {
+                            not: Some(Box::new(ss.clone())),
+                            ..Default::default()
+                        })),
+                        ..Default::default()
+                    })
+                })
+                .collect::<Vec<_>>();
+            let new_other = SchemaObject {
+                subschemas: Some(Box::new(SubschemaValidation {
+                    all_of: Some(all_of),
+                    ..Default::default()
+                })),
+                ..Default::default()
+            };
+            merge_schema_object(&schema_object, &new_other, defs)
+        }
+
+        SubschemaValidation {
+            all_of: None,
+            any_of: None,
+            one_of: None,
+            not: None,
+            if_schema: None,
+            then_schema: None,
+            else_schema: None,
+        } => Ok(schema_object),
+
+        _ => todo!(),
+    }
+}
+
 fn join_schema(a: &SchemaObject, b: &Schema) -> Schema {
     SchemaObject {
         subschemas: Some(Box::new(SubschemaValidation {
diff --git a/typify/Cargo.toml b/typify/Cargo.toml
index 1c892a8..0abc388 100644
--- a/typify/Cargo.toml
+++ b/typify/Cargo.toml
@@ -19,6 +19,7 @@ typify-impl = { version = "0.0.13", path = "../typify-impl" }
 
 [dev-dependencies]
 chrono = { version = "0.4.31", features = ["serde"] }
+env_logger = "0.10.0"
 expectorate = "1.0.7"
 glob = "0.3.1"
 quote = "1.0.33"


Test patch:
diff --git a/typify/tests/schemas.rs b/typify/tests/schemas.rs
index 57c0be3..3854d6e 100644
--- a/typify/tests/schemas.rs
+++ b/typify/tests/schemas.rs
@@ -12,6 +12,7 @@ use typify_impl::TypeSpaceImpl;
 
 #[test]
 fn test_schemas() {
+    env_logger::init();
     // Make sure output is up to date.
     for entry in glob("tests/schemas/*.json").expect("Failed to read glob pattern") {
         validate_schema(entry.unwrap()).unwrap();
diff --git a/typify/tests/schemas/merged-schemas.json b/typify/tests/schemas/merged-schemas.json
index a4b60bd..2a2d573 100644
--- a/typify/tests/schemas/merged-schemas.json
+++ b/typify/tests/schemas/merged-schemas.json
@@ -56,6 +56,158 @@
           }
         }
       ]
+    },
+    "but-not-that": {
+      "type": "object",
+      "properties": {
+        "this": {},
+        "that": {}
+      },
+      "not": {
+        "required": [
+          "that"
+        ]
+      }
+    },
+    "trim-fat": {
+      "type": "object",
+      "properties": {
+        "a": {},
+        "b": {},
+        "c": {}
+      },
+      "required": [
+        "a"
+      ],
+      "not": {
+        "anyOf": [
+          {
+            "required": [
+              "b"
+            ]
+          },
+          {
+            "required": [
+              "c"
+            ]
+          }
+        ]
+      }
+    },
+    "weird-enum": {
+      "type": "object",
+      "properties": {
+        "pattern": {
+          "type": "string"
+        },
+        "pattern-regex": {
+          "type": "string"
+        },
+        "patterns": {
+          "type": "string"
+        },
+        "pattern-either": {
+          "type": "string"
+        }
+      },
+      "oneOf": [
+        {
+          "required": [
+            "pattern"
+          ],
+          "not": {
+            "anyOf": [
+              {
+                "required": [
+                  "patterns"
+                ]
+              },
+              {
+                "required": [
+                  "pattern-either"
+                ]
+              },
+              {
+                "required": [
+                  "pattern-regex"
+                ]
+              }
+            ]
+          }
+        },
+        {
+          "required": [
+            "patterns"
+          ],
+          "not": {
+            "anyOf": [
+              {
+                "required": [
+                  "pattern"
+                ]
+              },
+              {
+                "required": [
+                  "pattern-either"
+                ]
+              },
+              {
+                "required": [
+                  "pattern-regex"
+                ]
+              }
+            ]
+          }
+        },
+        {
+          "required": [
+            "pattern-either"
+          ],
+          "not": {
+            "anyOf": [
+              {
+                "required": [
+                  "pattern"
+                ]
+              },
+              {
+                "required": [
+                  "patterns"
+                ]
+              },
+              {
+                "required": [
+                  "pattern-regex"
+                ]
+              }
+            ]
+          }
+        },
+        {
+          "required": [
+            "pattern-regex"
+          ],
+          "not": {
+            "anyOf": [
+              {
+                "required": [
+                  "pattern"
+                ]
+              },
+              {
+                "required": [
+                  "patterns"
+                ]
+              },
+              {
+                "required": [
+                  "pattern-either"
+                ]
+              }
+            ]
+          }
+        }
+      ]
     }
   }
 }
\ No newline at end of file
diff --git a/typify/tests/schemas/merged-schemas.rs b/typify/tests/schemas/merged-schemas.rs
index f6d9c01..29ceec3 100644
--- a/typify/tests/schemas/merged-schemas.rs
+++ b/typify/tests/schemas/merged-schemas.rs
@@ -1,6 +1,16 @@
 #[allow(unused_imports)]
 use serde::{Deserialize, Serialize};
 #[derive(Clone, Debug, Deserialize, Serialize)]
+pub struct ButNotThat {
+    #[serde(default, skip_serializing_if = "Option::is_none")]
+    pub this: Option<serde_json::Value>,
+}
+impl From<&ButNotThat> for ButNotThat {
+    fn from(value: &ButNotThat) -> Self {
+        value.clone()
+    }
+}
+#[derive(Clone, Debug, Deserialize, Serialize)]
 pub struct JsonResponseBase {
     #[serde(default, skip_serializing_if = "Option::is_none")]
     pub result: Option<String>,
@@ -172,4 +182,36 @@ impl ToString for NarrowNumber {
         self.0.to_string()
     }
 }
+#[derive(Clone, Debug, Deserialize, Serialize)]
+pub struct TrimFat {
+    pub a: serde_json::Value,
+}
+impl From<&TrimFat> for TrimFat {
+    fn from(value: &TrimFat) -> Self {
+        value.clone()
+    }
+}
+#[derive(Clone, Debug, Deserialize, Serialize)]
+#[serde(untagged)]
+pub enum WeirdEnum {
+    Variant0 {
+        pattern: String,
+    },
+    Variant1 {
+        patterns: String,
+    },
+    Variant2 {
+        #[serde(rename = "pattern-either")]
+        pattern_either: String,
+    },
+    Variant3 {
+        #[serde(rename = "pattern-regex")]
+        pattern_regex: String,
+    },
+}
+impl From<&WeirdEnum> for WeirdEnum {
+    fn from(value: &WeirdEnum) -> Self {
+        value.clone()
+    }
+}
 fn main() {}