Strange type checker bug …

[jonathanmarvens]

Can someone help me understand why I’m getting the following behavior from the TypeScript type checker? This seems like a bug to me, but is there something I’m missing here?

Thanks in advance.

- Jonathan

TypeScript version: 2.5.3

Code:

type LinkedListNode<T> =
  {
    data: T;
    next: LinkedListNode<T>;
  } |
  { next: null; }

type LinkedList<T> = { head: (LinkedListNode<T> | null); }

const createIterator = <T>(list: LinkedList<T>) => {
  let { head: node } = list
  return {
    [Symbol.iterator]: function* () {
      if (node !== null) {
        while (node.next !== null) {
          yield node.data
          node = node.next
        }
      }
    }
  }
}

Expected behavior:

No errors.

Actual behavior:

Line 16 of the code above (i.e., the line with yield node.data) generates the following TypeScript error:

Property 'data' does not exist on type 'LinkedListNode<T>'.
  Property 'data' does not exist on type '{ next: null; }'.

[ngolin]

This will work:

type LinkedListNode<T> = {
  data: T;
  next: LinkedListNode<T> | null
};

type LinkedList<T> = {
  head: LinkedListNode<T> | null
};

const createIterator = <T>(list: LinkedList<T>) => {
  let { head: node } = list;
  return {
    [Symbol.iterator]: function* () {
      if (node !== null) {
        while (node.next !== null) {
          yield node.data;
          node = node.next;
        }
      }
    }
  }
}

[jonathanmarvens]

Code snippet 1:

type LinkedListNode<T> =
  {
    data: T;
    next: LinkedListNode<T>;
  } |
  { next: null; }

Code snippet 2:

type LinkedListNode<T> = {
  data: T;
  next: LinkedListNode<T> | null;
};

@ngolin Thank you for the suggestion, but, unfortunately, I’m not simply looking for what would work. I’m trying to understand why the type checker doesn’t fully understand Code snippet 1. Also, semantically, Code snippet 1 and Code snippet 2 aren’t equivalent: Code snippet 2 semantically accepts a null value for LinkedListNode<T>::next when LinkedListNode<T>::data isn’t undefined, but Code snippet 1 should protect against this (the latter is the expected behavior).

[jonathanmarvens]

BTW, I kept the code examples tiny, but in case seeing some more code would be helpful, here’s some more (the module is still a bit longer, but hopefully this is enough to provide more context into the usage):

export type LinkedListNode<T> =
  {
    data: T;
    next: LinkedListNode<T>;
  } |
  { next: null; }

export type LinkedList<T> =
  ({
    head: LinkedListNode<T>;
    tail: LinkedListNode<T>;
  } |
  {
    head: null;
    tail: null;
  }) &
  { size: number; }

export const add = <T>(list: LinkedList<T>, element: T) => {
  const newNode = createNode<T>(element,
    createNode<T>())
  if ((list.head === null) ||
      (list.tail === null)) {
    list.head = newNode
    list.tail = newNode
  } else {
    list.tail.next = newNode
    list.tail = list.tail.next
  }
  list.size++
}

export const create = <T>() => {
  return {
    head: null,
    size: 0,
    tail: null
  }
}

export const createFrom = <T>(iterable: IterableIterator<T>) => {
  const list = create<T>()
  for (let element of iterable) {
    add(list, element)
  }
  return list
}

export const createIterable = <T>(list: LinkedList<T>) => {
  let { head: node } = list
  return {
    [Symbol.iterator]: function* () {
      if (node !== null) {
        while (node.next !== null) {
          yield node.data
          node = node.next
        }
      }
    }
  }
}

const createNode = <T>(data?: T, next?: LinkedListNode<T>) => {
  if ((typeof data !== 'undefined') &&
      (typeof next !== 'undefined')) {
    return {
      data,
      next
    }
  } else {
    return {next: null}
  }
}

export const size = <T>(list: LinkedList<T>) => list.size

[gcnew]

The problem is that next is not considered a discrimination property.

type List<T> = { value: T, next: List<T> }
             | { next: null }

declare const list: List<number>;

if (list.next !== null) {
    list; // still `{ value: T, next: List<T> } | { next: null }`
          // should have been narrowed to { value: T, next: List<T> }
}

Your original example seems like a bug to me. To workaround it now, you may use nulldirectly, instead of a custom "empty list".

type List<T> = { value: T, next: List<T> }
             | null

declare const list: List<number>;

if (list !== null) {
    list.value // works fine
}

[jonathanmarvens]

@gcnew Yes, I understand that there are alternative ways to write the code to make it work, but that misses the point. I’ve analyzed my code over and over again, and I disagree that my original example is a bug … there’s nothing about my original example that’s not correct (in terms of the expected behavior of the code, given the semantics). In fact, I’m actually quite surprised to see the TypeScript type checker choking on this one, given how correct and smart it usually is (even in some of the most complex/unintuitive scenarios that I’ve encountered).

[gcnew]

@jonathanmarvens Sure, I meant that the currently exhibited compiler behaviour is a bug. Hence, the comment in the reduced repro:

if (list.next !== null) {
    list; // still `{ value: T, next: List<T> } | { next: null }`
          // should have been narrowed to { value: T, next: List<T> }
}

[gcnew]

@jonathanmarvens

I’m trying to understand why the type checker doesn’t fully understand Code snippet 1.

As far as I remember, the problem is that TypeScript considers only properties that are unit types (i.e. literal types) or unions of unit types as discrimination properties. In the above case List is a regular, inhibited by many values type, thus next is not a discrimination property and no narrowing is being performed.

[mhegazy]

Automatically closing this issue for housekeeping purposes. The issue labels indicate that it is unactionable at the moment or has already been addressed.