O.Path improvements (distribution, arrays)

[mcpower]

🍩 Feature Request

Is your feature request related to a problem?

See @leebenson's comment on #57.

Describe the solution you'd like

Something which can do something like this:

type Nested = {
    a?: NestedA | NestedA[] | null | number;
    z: 'z';
};
type NestedA = {
    b?: NestedB | NestedB[] | null | number;
    y: 'y';
};
type NestedB = {
    c: 'c';
};
// resolves to 'c'
type C = O.P.At<Nested, ['a', 'b', 'c']>;

This follows on from the discussion on #57. From the previous discussion:

This is surprisingly non-trivial when it comes to nested arrays in the path... To do this with infinite nesting, we need a utility type to get the (nested) inner type of an array. However, this is impossible - see this TS Playground for an example of why it's impossible to implement.

However, if we restrict nesting to something absurd like four dimensional nested arrays, it could work, like in this TS Playground.

As an update to that, I believe this feature is impossible to get "perfect", for similar reasons to why getting the nested inner type of an array is impossible. In a type definition, you can't directly refer to the type definition without some sort of indirection - see the TS 3.7 blog post for more details on that.

Here's the code I tried:

type _At<O, Path extends Tuple<Index>, I extends Iteration = IterationOf<'0'>> =
  Pos<I> extends Length<Path>
  ? O // target
  : O extends object
    ? O extends (infer A)[]
      ? _At<A, Path, I>
      : Path[Pos<I>] extends infer K
        ? K extends keyof O
          ? _At<O[K], Path, Next<I>>
          : never // not key
        : never // impossible
    : never; // dive into not object

TypeScript 3.7 complains that it's a circularly referenced type. Adding a type Lazy<T> = T doesn't help either - I think the type system eagerly evaluates all branches of a conditional type at runtime (without expanding nested types like objects and arrays). That means we need to add some level of indirection at every level we traverse.

The other way of doing it is manually "unrolling" the recursion many times, like the ArrayType example above:

// from
type ArrayType<T> = T extends (infer A)[] ? ArrayType<A> : T;
// to
type ArrayType4<T> = T extends (infer A)[] ? ArrayType3<A> : T;
type ArrayType3<T> = T extends (infer A)[] ? ArrayType2<A> : T;
type ArrayType2<T> = T extends (infer A)[] ? ArrayType1<A> : T;
type ArrayType1<T> = T extends (infer A)[] ? A : T;

If we were to do this in O.P.At, it would result in pretty unreadable code. Instead, we could "wrap" the return value of the unlimited depth O.P.At with something { __wrap: T } (we want this wrapping to be unique so we don't accidentally unwrap a user's type) and "unwrap" it at the end with something like ArrayType above.

In fact, I found a way of getting 2ⁿ levels of recursion with n "unrolls" (Playground link) - so we can pretty easily get lots of unrolling with little code:

// unrolls (2*3)+1 = 7
type ArrayType7<T> = T extends (infer A)[] ? ArrayType3<ArrayType3<A>> : T;
// unrolls (2*1)+1 = 3
type ArrayType3<T> = T extends (infer A)[] ? ArrayType1<ArrayType1<A>> : T;
// unrolls 1
type ArrayType1<T> = T extends (infer A)[] ? A : T;

// resolves to number[]
type EightDimensions = ArrayType7<number[][][][][][][][]>;

We nest the double-types inside a conditional to prevent TypeScript from expanding the types to the user... and filling their screen with ArrayType1s 😛.

Using this, we can write some code that works on TypeScript 3.6:

// unwraps 15 { __wrap: T } levels
type Unwrap<T>  = T extends { __wrap: infer U } ? Unwrap7<Unwrap7<U>> : T;
type Unwrap7<T> = T extends { __wrap: infer U } ? Unwrap3<Unwrap3<U>> : T;
type Unwrap3<T> = T extends { __wrap: infer U } ? Unwrap1<Unwrap1<U>> : T;
type Unwrap1<T> = T extends { __wrap: infer U } ? U : T;

type _At<O, Path extends Tuple<Index>, I extends Iteration = IterationOf<'0'>> =
  Pos<I> extends Length<Path>
  ? O // target
  : O extends object
    ? O extends (infer A)[]
      ? { __wrap: _At<A, Path, I> }
      : Path[Pos<I>] extends infer K
        ? K extends keyof O
          ? { __wrap: _At<O[K], Path, Next<I>> }
          : never // not key
        : never // impossible
    : never; // dive into not object

type At<O extends object, Path extends Tuple<Index>> = Unwrap<_At<O, Path>>

type Nested = {
  a?: NestedA | NestedA[] | null | number;
  z: 'z';
};
type NestedA = {
  b?: NestedB | NestedB[] | null | number;
  y: 'y';
};
type NestedB = {
  c: 'c';
};
// successfully evaluates to 'c'
type C = At<Nested, ['a', 'b', 'c']>;

@pirix-gh What do you think? The ArrayType utility type could also come in handy as well, so we may want to add that to ts-toolbox too.

[leebenson]

Thanks for your time and attention on this, @mcpower.

I feel like I'm actually pretty close to what I'm trying to achieve (for new readers: drilling into GraphQL responses, which can have T | T[] arbitrary levels deep), based on your examples in #57 + Object.At, with few minor changes and wrappers:

// Flatten arrays
type F<T> = T extends (infer U)[] ? (U extends object ? U : T) : T;

// Pick helper
type _Pick<
  O extends object,
  Path extends Tuple.Tuple<Any.Index>,
  I extends Iteration.Iteration = Iteration.IterationOf<"0">
> = O extends (infer A)[]
  ? A extends object
    ? _Pick<A, Path, I>[]
    : O
  : Object.Pick<O, Path[Iteration.Pos<I>]> extends infer Picked
  ? {
      [K in keyof Picked]: Picked[K] extends infer Prop
        ? Prop extends object
          ? Iteration.Pos<I> extends Tuple.LastIndex<Path>
            ? Prop
            : _Pick<F<Prop>, Path, Iteration.Next<I>>
          : Prop
        : never;
    }
  : never;

// Pick
export type Pick<O extends object, Path extends Tuple.Tuple> = _Pick<O, Path>;

// Pick + Object.At
type Query<TQuery extends object, TPath extends Tuple.Tuple> = Object.Path<
  Pick<TQuery, TPath>,
  TPath
>;

Usage example

GraphQL:

query OrganizationWorkspaces($slug: String!) {
  organization(slug: $slug) {
    id
    workspaces {
      edges {
        node {
          id
          name
        }
      }
    }
  }
}

GraphQL Code Generator generated query type:

export type OrganizationWorkspacesQuery = (
  { __typename?: 'Query' }
  & { organization: Maybe<(
    { __typename?: 'Organization' }
    & Pick<Organization, 'id'>
    & { workspaces: (
      { __typename?: 'WorkspaceConnection' }
      & { edges: Maybe<Array<(
        { __typename?: 'WorkspaceEdge' }
        & { node: (
          { __typename?: 'Workspace' }
          & Pick<Workspace, 'id' | 'name'>
        ) }
      )>> }
    ) }
  )> }
);

Getting the 'inner' node type:

type Workspace = Query<
  OrganizationWorkspacesQuery,
  ["organization", "workspaces", "edges", "node"]>

Intellisense:

TODOS

1. It'd be awesome to update Object.PathValid to allow array unnesting, which would enable moving from TPath extends Tuple.Tuple in Query, to TPath extends Object.PathValid<TQuery, TObject>, to provide some developer Intellisense when typing out path elements.

2. The types above implicitly handle scalar nullables, but Maybe<T>[] (Maybe is a generated alias for T | null) isn't unwound yet. This feels like it should be trivial to add, and would then handle GraphQL schema in the format of both [T]! as well as the (currently working) [T!]!.

---

The above may be a limited use-case for GraphQL types, although I think it might also be useful as a general 'lens' into arbitrary levels of an object.

This implementation probably needs a bit of refinement. Feel free to tweak and release as Object.Lens or similar, if you think it'd be useful to others.

Thanks again @mcpower!

[mcpower]

Silly me - I didn't realise Object.Path was in this library! Your Query implementation seems to be equivalent to an improved version of Object.Path.

I think improving Object.Path to fit this use case is probably better - in particular:

• distributing over O
• supporting arrays (should be gated behind a boolean flag in the library)

These two, in combination, should make Object.Path equivalent to your Query implementation.

This is relatively simple to implement, but writing tests / formatting / implementing the boolean flag is a bit tedious. Here's a modification of Object.Path which works as expected, without tests / the boolean flag:

import {Object, Iteration, Tuple, Any, Union} from 'ts-toolbelt'

type _Query<O, Path extends Tuple.Tuple<Any.Index>, I extends Iteration.Iteration = Iteration.IterationOf<'0'>> = {
  0:
    O extends object // distribution over O
    ? O extends (infer A)[] // supporting arrays
      ? _Query<A, Path, I>
      : _Query<Union.NonNullable<Object.At<O, Path[Iteration.Pos<I>]>>, Path, Iteration.Next<I>>
    : never
  1: O
}[
  Iteration.Pos<I> extends Tuple.Length<Path>
  ? 1
  : 0
]

export type Query<O extends object, Path extends Tuple.Tuple<Any.Index>> = _Query<O, Path>

type Maybe<T> = T | null;
type Organization = {id: 1}
type Workspace = {id: 2, name: string}
type OrganizationWorkspacesQuery = (
    { __typename?: 'Query' }
    & { organization: Maybe<(
      { __typename?: 'Organization' }
      & Pick<Organization, 'id'>
      & { workspaces: (
        { __typename?: 'WorkspaceConnection' }
        & { edges: Maybe<Array<(
          { __typename?: 'WorkspaceEdge' }
          & { node: (
            { __typename?: 'Workspace' }
            & Pick<Workspace, 'id' | 'name'>
          ) }
        )>> }
      ) }
    )> }
  );
// evaluates to { __typename?: "Workspace" | undefined } & Pick<Workspace, "id" | "name">
type Result = Query<OrganizationWorkspacesQuery, ['organization', 'workspaces', 'edges', 'node']>

Interestingly, in your given example Workspace is both the type of the result (Result in the code above) and a part of OrganizationWorkspacesQuery. Not sure how that works!

P.S. Object.Path is amazing - I'm impressed that something like it is possible in TypeScript's type system!

[millsp]

Hi all, I'm not into GraphQL, but I believe this should work:

import {IterationOf} from '../Iteration/IterationOf'
import {Iteration} from '../Iteration/Iteration'
import {Next} from '../Iteration/Next'
import {Pos} from '../Iteration/Pos'
import {Length} from '../Tuple/Length'
import {At} from './At'
import {Cast} from '../Any/Cast'
import {NonNullable as UNonNullable} from '../Union/NonNullable'
import {Index} from '../Any/Index'
import {Tuple} from '../Tuple/Tuple'

type _PathUp<O, Path extends Tuple<Index>, I extends Iteration = IterationOf<'0'>> = {
    0: At<O & {}, Path[Pos<I>]> extends infer OK
       ? OK extends unknown
         ? _PathUp<UNonNullable<OK>, Path, Next<I>>
         : never
       : never
    1: O // Use of `NonNullable` otherwise path cannot be followed #`undefined`
}[
    Pos<I> extends Length<Path>
    ? 1 // Stops before going too deep (last key) & check if it has it
    : 0 // Continue iterating and go deeper within the object with `At`
]

/** Get in **`O`** the type of nested properties
 * @param O to be inspected
 * @param Path to be followed
 * @returns **`any`**
 * @example
 * ```ts
 * ```
 */
export type PathUp<O extends object, Path extends Tuple<Index>> =
    _PathUp<O, Path> extends infer X
    ? Cast<X, any>
    : never

type Nested = {
    a?: NestedA | NestedA[] | null | number
    z: 'z';
};

type NestedA = {
    b?: NestedB | NestedB[] | null | number
    y: 'y';
};

type NestedB = {
    c: 'c';
    z: 'z';
};

// resolves to 'c' | 'z'
type CObject = PathUp<Nested, ['a', 'b', 'c' | 'z']>;
type CArray  = PathUp<Nested, ['a', 'b', number, 'c' | 'z']>;

[millsp]

@leebenson PathValid is a bit off topic, I think. The docs were mistakingly copied with the ones of Path. Here's what it does

[millsp]

PS @mcpower the PathUp implementation is able to go through unions while Path isn't able to do this. And I used number to go through the Array like you suggested.

What do you think?

[leebenson]

@pirix-gh - looks great!

I made a slight modification to drop the number requirement, which I think makes it a bit more readable in the case of a GraphQL 'lens':

type _PathUp<
  O,
  Path extends Tuple.Tuple<Any.Index>,
  I extends Iteration.Iteration = Iteration.IterationOf<"0">
> = {
  0: Object.At<O & {}, Path[Iteration.Pos<I>]> extends infer OK
    ? OK extends (infer U)[]
      ? _PathUp<NonNullable<U>, Path, Iteration.Next<I>>
      : OK extends unknown
      ? _PathUp<NonNullable<OK>, Path, Iteration.Next<I>>
      : never
    : never;
  1: O; // Use of `NonNullable` otherwise path cannot be followed #`undefined`
}[Iteration.Pos<I> extends Tuple.Length<Path>
  ? 1 // Stops before going too deep (last key) & check if it has it
  : 0]; // Continue iterating and go deeper within the object with `At`

/** Get in **`O`** the type of nested properties
 * @param O to be inspected
 * @param Path to be followed
 * @returns **`any`**
 * @example
 * ```ts
 * ```
 */
export type PathUp<
  O extends object,
  Path extends Tuple.Tuple<Any.Index>
> = _PathUp<O, Path> extends infer X ? Any.Cast<X, any> : never;

Thanks so much to you and @mcpower for indulging my specific use-case! Really appreciate your time.

[millsp]

@leebenson I can't add your modified type to this lib, unfortunately. I need to follow some rules about consitency. And since we are talking about Path, number here means that we're going to access an index number on an Array. If your array was a Tuple you would be able to use 0 | 1 | 2....

So by acessing number, we actually mean to access anything within that Array/Tuple

The second reason is that I don't see why we should treat Arrays/Tuples differently than Objects. I understand, that it makes your specific use-case more simple, but I don't see how consistent it is (for this lib). It is a pre-requisite for me to stay standard.

But if the number is the problem, you can probably use Index instead:

type CArray  = PathUp<Nested, ['a', 'b', Index, 'c' | 'z']>;
// we now know that we're accessing all indexes of an array/tuple

Maybe you could start a lib of your own for graphQL-related type helpers?

I'm glad we could help you. I'll probably proceed with publishing the PathUp in the next few days.

Let me know if there's anything else, before I close the issue :)

[millsp]

type Tuple = [
    [[[1]]],
    2,
    3
]

type test0 = PathUp<Tuple, [0, 0, 0, 0]>; // 1
type test1 = PathUp<Tuple, [Index]>;      // 3 | [[[1]]] | 2

[leebenson]

👍 totally cool, my version only really applies to this limited use-case. Having the more flexible/general purpose as part of the lib is great.

Thanks again!