Adding closure support for circular types

[ahdinosaur]

hi 😺

i was getting amongst computed-types for a side project i'm playing with, and then i realized the types i want to validate are circular, e.g. a tree data structure. i was wondering if it might be possible to use computed-types with circular types.

i made a simplified example to show what i mean, and what i have working so far: https://repl.it/talk/share/circular-computed-types/43342

// mod.ts

import Schema, { Type, string, array } from 'https://denoporter.sirjosh.workers.dev/v1/deno.land/x/computed_types/src/index.ts'

// lazy due to circular evaluation
let _NodeSchema: any = null
export const NodeSchema: any = function (...args: Array<any>): any {
  if (_NodeSchema == null) throw new Error('programmer error')
  return _NodeSchema(...args)
}

export type Node = Branch | Leaf

export const BranchSchema = Schema({
  name: string.trim().normalize(),
  nodes: array.of(NodeSchema),
})

export type Branch = Type<typeof BranchSchema>

export const LeafSchema = Schema({
  name: string.trim().normalize()
})

export type Leaf = Type<typeof LeafSchema>

_NodeSchema = Schema.either(BranchSchema, LeafSchema)

import { NodeSchema } from './mod.ts'

const node = NodeSchema({
  name: 'a',
  nodes: [
    {
      name: 'b'
    },
    {
      name: 'c',
      nodes: [
        {
          name: 'd',
          nodes: [
            {
              name: 'e'
            }
          ]
        },
        {
          name: 'f'
        }
      ]
    }
  ]
})

console.log(JSON.stringify(node, null, 2))

i'm able to get the runtime to work with a silly hack, but i'm stuck on getting the types to work.

was wondering, is this something that might be possible to do?

cheers! 💜

[moshest]

Thanks! It's a nice use-case and we definitely want to support it more in the future.

For now, I managed to solve it by explicitly define the type and create a function validator:

type Node = {
  name: string;
  nodes: Node[];
};

const NodeSchema = (node: Node): Node => {
  return Schema({
    name: string.trim().normalize(),
    nodes: array.of(NodeSchema),
  })(node);
};

I added a test for it here: d77a442, 31c38e6

This NodeSchema is a regular type now so you can even use it on other schemas:

const MainSchema = Schema({
  type: string,
  node: NodeSchema,
});

[calummoore]

One way to handle this could be to pass in a function which will be called to evaluated the type:

const NodeSchema =  Schema({
    name: string.trim().normalize(),
    nodes: (self) => array.of(self),
  })

And the function could also help in situations where you have circular types across multiple types:

 const SourceFilterOrSchema = Schema({
  operator: 'or',
  left: () => SourceFilterSchema,
  right: () => SourceFilterSchema,
})

const SourceFilterSchema = Schema.either(
  SourceFilterAndSchema,
  SourceFilterOrSchema,
  SourceFilterComparisonSchema,
)

[calummoore]

In case it helps, this is the schema I've created. This works, but as you can see in the comments, I'm unable to use the auto-typing for SourceFilterAndOr as typescript complains of a circular reference.

import Schema, {
  Type, string, number, boolean,
} from 'computed-types'

const SourceFilterSchema = (node: SourceFilter): SourceFilter => {
  return Schema.either(
    SourceFilterAndOrSchema,
    SourceFilterComparisonSchema,
  )(node)
}

export const SouceFilterPrimitiveSchema = Schema.either(string, number, boolean)

export const SourceFilterAndOrSchema = Schema({
  operator: Schema.either('and' as const, 'or' as const),
  left: SourceFilterSchema,
  right: SourceFilterSchema,
})

export const SchemaFilterComparisonOperatorsSchema = Schema.either(
  'eq' as const,
  'gte' as const,
  'gt' as const, 
  'lt' as const, 
  'lte' as const,
)

export const SourceFilterComparisonSchema = Schema({
  operator: SchemaFilterComparisonOperatorsSchema,
  value: SouceFilterPrimitiveSchema,
})

export type SourceFilter =  SourceFilterAndOr | SourceFilterComparison
export type SourceFilterAndOr = {
  operator: 'and'|'or'
  left: SourceFilter
  right: SourceFilter
}

// If I try to use this instead of the above, typescript errors with: Type alias 'SourceFilterAndOr' circularly references itself.
// export type SourceFilterAndOr = Type<typeof SourceFilterAndOrSchema>
export type SourceFilterComparison = Type<typeof SourceFilterComparisonSchema>
export type SchemaFilterComparisonOperators = Type<typeof SchemaFilterComparisonOperatorsSchema>

[calummoore]

Also, with this approach I'm unable to mark the schema as optional.

const SourceFilterSchema = (node: SourceFilter): SourceFilter => {
  return Schema.either(
    SourceFilterAndOrSchema,
    SourceFilterComparisonSchema,
  )(node)
}

const AltSchema = Schema({
  filter: SourceFilterSchema.optional() // this does not work
})

[moshest]

I think recursive functions will break TypeScript validation and require type definition from the user, but I really like this idea!

We can create Schema.recursive helper for that:

const Node = Schema.recursive<T>((self: T) => ({
  name: string,
  children: array.of(self),
}));

I will play with it when I have some time.

[calummoore]

That looks good! I think your approach makes sense for a recursive fn.

The other use case is to enable SchemaA to reference SchemaB and vice versa (as below). In that case, we don't actually need the self variable - we're just using the fn to make sure we have a reference to later defined schema variable.

const SchemaA = Schema({ 
  b: SchemaB // ERROR: SchemaB is not defined
})

const SchemaB = Schema({
  a: SchemaA
})

To solve the above, you could again use the .recursive() utility (although you wouldn't need the self parameter).

const SchemaA = Schema.recursive(() => Schema({ 
  b: SchemaB // Now it works!
}))

const SchemaB = Schema({
  a: SchemaA
})

I wonder if the recursive() name makes sense for this use case though - perhaps the name wrap() would fit both use cases better? Just minor semantics though.

The other difference between recursive and wrap might be that .recursive() works as a replacement to Schema({}) (so you return a plain object) but .wrap() would wrap any Schema (e.g. Schema.merge, Schema.either, etc).

[moshest]

maybe Schema.closure is a better name then.

I liked your example. Function closure is really a strong concept in JavaScript. I wonder how TypeScript will handle that.