TypeScript - Recursive generics and leaf branch-like problem (Ultimate TicTacToe)

Question

I'm making an Ultimate Tic-Tac-Toe game and I'm creating the grid/board.

How do I use generics recursively to make my grid have other grids inside of it (in its cells)? The depth level is unknown, this might have more than depth of 2... It could be a grid of a grid of a grid of a grid of cells i.e.

It's about the same thing as the leaf/branch problem. A branch can have leaves or other branches (not both at the same time in this case).

I've already tried a few things (using interfaces, defining custom types, etc..) but it was always giving the same errors (see below, in the errors part).

Here is the code I ended up with...

Cell.ts

import { CellValue } from "./CellValue";

export class Cell {
    private value: CellValue;
    constructor() {

    }

    public getValue(): CellValue {
        return this.value;
    }
}

TicTacToeGrid.ts

import { Cell } from "./Cell";

/**
 * Represents the Tic Tac Toe grid.
 */
export class TicTacToeGrid<T = TicTacToeGrid|Cell> {

    /**
     * The grid can contain cells or other grids
     * making it a grid of grids.
     */
    private grid: Array<Array<T>> = [];

    /**
     * Creates a new grid and initiailzes it.
     * @param {[number, number][]} sizes an array containing the sizes of each grid.
     * The first grid has the size defined in the first element of the array. i.e. [3, 3] for a 3x3 grid.
     * The others elements are the sizes for the sub-grids.
     */
    constructor(sizes: [number, number][]) {
        const size: [number, number] = sizes.splice(-1)[0]; // Get the size of this grid

        for(let y = 0; y < size[1]; y++) {
            this.grid.push();
            for(let x = 0; x < size[0]; x++) {
                this.grid[y].push();

                this.grid[y][x] = sizes.length > 0 ? new TicTacToeGrid(sizes) : new Cell(); // if there still are size left in the array, create a new sub-grid with these sizes
            }
        }

    }

    /**
     * Returns the content of the specified cell
     * @param {number} x the x position of the cell whose content wants to be retrieved
     * @param {number} y the y position of the cell whose content wants to be retrieved
     */
    public getElement(x: number, y: number): T {
        return this.grid[y][x];
    }
}

index.ts

import { TicTacToeGrid } from "./TicTacToeGrid ";
import { Cell } from "./Cell";

const board: TicTacToeGrid<TicTacToeGrid<Cell>> = new TicTacToeGrid<TicTacToeGrid<Cell>>([[3, 3], [5, 5]]);

const value: number= board.getElement(2, 2).getElement(1, 1).getValue();

Everything works fine except the compiler throws 2 errors in TicTacToeGrid.js:

1. Type parameter 'T' has a circular default.

-> Ok, but how do I solve this?

2. Type 'Cell | TicTacToeGrid<unknown>' is not assignable to type 'T'. 'Cell | TicTacToeGrid<unknown>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'. Type 'Cell' is not assignable to type 'T'. 'Cell' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.

-> How do I deal with this? What does it exactly mean?

Answer 1

Issue #1: circular default

The declaration class TicTacToeGrid<T = TicTacToeGrid|Cell> {} means that T can be anything, but that if you just write the type TicTacToeGrid without specifying the type parameter, it will use TicTacToeGrid|Cell. This is circular in a bad way, since the compiler is being asked to eagerly evaluate the type TicTacToeGrid<TicTacToeGrid<TicTacToeGrid<...|Cell>|Cell>|Cell>, which it doesn't know how to do. You can fix that by changing it to class TicTacToeGrid<T = TicTacToeGrid<any>|Cell> {}, which breaks the cycle.

However, you don't actually want a default generic parameter at all, I think. You don't want T to be possibly, say, string, right? What you're looking for is a generic constraint, using the extends keyword instead:

class TicTacToeGrid<T extends TicTacToeGrid<any> | Cell> { ... }

That will now behave more reasonably for you.

---

Issue #2: 'Cell | TicTacToeGrid<...>' is not assignable to type 'T'

This is due to a longstanding issue (see microsoft/TypeScript#24085) wherein generic type parameters that extend union types are not narrowed via control flow analysis. If you have a concrete union type like string | number, you can check a variable sn of that type like (typeof sn === "string") ? sn.charAt(0) : sn.toFixed() and inside the branches of the ternary operator, the type of sn will be narrowed either to string or number. But if sn is a value of a generic type like T extends string | number, then checking (typeof sn === "string") will not do anything to the type T. In your case, you'd like to check sizes.length and have it narrow T either to Cell or to some TicTacToeGrid. But this does not happen automatically, and the compiler warns you that it can't be sure that you are assigning the right value to the grid element. It sees you assigning a Cell | TicTacToeGrid<XXX>, and warns you that T might be narrower than that, and it's not safe.

The easiest fix here is to just tell the compiler that you are sure what you are doing is acceptable, via a type assertion:

this.grid[y][x] = (sizes.length > 0 ? new TicTacToeGrid(sizes) : new Cell()) as T;

That as T at the end tells the compiler that you are responsible for ensuring that the preceding expression is going to be a valid T. If at runtime it turns out that you were wrong about that, then you have lied to the compiler with the assertion, and that's your problem to deal with. In fact this problem can fairly easily happen the way you've defined the constructor, since there is no way for T to be inferred from the sizes argument... so lying to the compiler is as simple as:

const lyingBoard: TicTacToeGrid<
  TicTacToeGrid<TicTacToeGrid<Cell>>
> = new TicTacToeGrid([[3, 3]]); // no error

lyingBoard
  .getElement(0, 0)
  .getElement(0, 0)
  .getElement(0, 0)
  .getValue(); // no error at compile time, kablooey at runtime

But presumably you're not going to do that. There may be a way to make sure the sizes parameter matches up with T, or even have T be inferrable from the sizes parameter, but that takes us farther afield from your question and this answer is already long enough.

---

Link to code