False positive [union-attr]

[asarkar]

Solving LeetCode 23. Merge k Sorted Lists locally.

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

To Reproduce

import heapq
from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = [(ll.val, i) for i, ll in enumerate(lists) if ll is not None]
    heapq.heapify(heap)
    head = ListNode(0)
    node: Optional[ListNode] = head
    while heap:
        _, i = heapq.heappop(heap)
        if lists[i] is None:
            continue
        assert node is not None
        node.next = lists[i]
        node = lists[i]
        if lists[i].next is not None:  # type: ignore[union-attr]
            lists[i] = lists[i].next  # type: ignore[union-attr]
            heapq.heappush(heap, (lists[i].val, i))  # type: ignore[union-attr]
    return head.next

Expected Behavior
No violations. Suppression shouldn't be required.

Actual Behavior

linked_lists/functions.py:123: error: Item "None" of "ListNode | None" has no attribute "next"  [union-attr]
linked_lists/functions.py:124: error: Item "None" of "ListNode | None" has no attribute "next"  [union-attr]
linked_lists/functions.py:125: error: Item "None" of "ListNode | None" has no attribute "val"  [union-attr]

These lines correspond to the if lists[i].next is not None block. Note that lists[i] has already been checked, and even if lists[i] is not None is added to the if condition, the errors don't go away.

Your Environment

• Mypy version used: 1.6.1
• Mypy command-line flags: --strict
• Mypy configuration options from mypy.ini (and other config files):

  [tool.mypy]
  exclude = [
    'venv'
  ]
  ignore_errors = 'False'
  

• Python version used: 3.11

[JelleZijlstra]

The problem here is that mypy doesn't narrow expressions of the form a[b] where b isn't a literal. I believe there are lots of similar issues but couldn't immediately find one.

[erictraut]

I think issues like this have previously been closed because mypy is working as intended here. As you said, mypy doesn't support narrowing of index expressions with dynamic (non-literal) subscripts. This is also true of other Python type checkers — and static type checkers and compilers in other languages. It's difficult (impossible in the general case) to statically prove that a dynamic subscript expression refers to the same element when that expression appears in multiple places within a function.

The recommended approach is to use an assignment expression (walrus operator) to assign the element to a local variable.

def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = [(ll.val, i) for i, ll in enumerate(lists) if ll is not None]
    heapq.heapify(heap)
    head = ListNode(0)
    node: Optional[ListNode] = head
    while heap:
        _, i = heapq.heappop(heap)
        if (item := lists[i]) is None:
            continue
        assert node is not None
        node.next = item
        node = item
        if item.next is not None:
            lists[i] = item.next
            heapq.heappush(heap, (item.next.val, i))
    return head.next

[asarkar]

Thanks for your comments. I quickly checked that @erictraut's updated code indeed doesn't have the violations, although I've to say that writing item.next.val instead of lists[i].next looks like a clever hack to fool the checker.

To a human, this workaround isn't an improvement, but I understand the reasoning "It's difficult to statically prove that a dynamic subscript expression refers to the same element" for a machine. Perhaps this issue can be documented as a known limitation with a workaround available?

[JelleZijlstra]

Duplicate of #7339