Cyclical "is-a" relationships between types causes stack overflow

[popematt]

When any number of types have a circular "is-a" relationship it results in a stack overflow when calling validate().

Observed behavior

Here is a minimal reproducible test case:

#[test]
fn stack_overflow_reproduction() {
    use ion_schema::authority::MapDocumentAuthority;
    use ion_rs::element::Element;
    use ion_schema::system::SchemaSystem;

    let authority = MapDocumentAuthority::new([(
        "foo",
        r#"
            $ion_schema_2_0
            type::{ name: a, type: b }
            type::{ name: b, type: a }
        "#,
    )]);
    let mut schema_system = SchemaSystem::new(vec![Box::new(authority)]);
    let schema = schema_system.load_schema("foo").unwrap();

    let isl_type_a = schema.get_type("a").unwrap();
    let value: Element = 5.into();
    let result = isl_type_a.validate(&value); // stack overflow
    result.unwrap();
}

This can be reproduced with both ISL 1.0 and 2.0. It can be reproduced using any of the "logical" constraints in any size of cycle. For example, attempting to validate any data with any of these types will also cause a stack overflow.

type::{ name: a, type: a }

type::{ name: b, all_of:[c] }
type::{ name: c, any_of:[d] }
type::{ name: d, one_of:[e] }
type::{ name: e, not: b }

Note the distinction between these examples and a recursive data type. A recursive data type references itself to define its constituent parts, whereas this issue is for types which are their own ancestor type. This toy example is a recursive data type, and is legal (even if it isn't particularly useful):

type::{
  name: a,
  element: a
}

Expected behavior

The correct behavior should be to detect cycles:

• For all logical constraints: type, not, one_of, all_of, any_of
• For undecorated types and for types that are decorated with nullable or $null_or
• When the cycle contains inline type definitions
• When the cycle contains types from more than one schema

Cycles should be detected when a schema is being loaded, and if a cycle is found, the load function must return Err.