isinstance narrowing of a generic container (set/dict) defaults the element type to int, corrupting element iteration

[plajjan]

Iterating a set (or dict) that has been narrowed from a value supertype via isinstance yields garbage for each element: str(x) / repr(x) on an element returns an internal tag (e.g. 4294967297 = 0x1_0000_0001) instead of the real element, even though the whole-container repr() renders correctly. This was found in the wild (a YANG bits leaf decoded into a set of bit-name strings, compared via sorted(list(a)) < sorted(list(b)), which silently returned False both directions because every sorted element was the same garbage tag).

Minimal reproducer (compile and run with a from-source build at v0.28.1-14-g0a9302956):

def show(v: value) -> None:
    if isinstance(v, set):
        parts = []
        for x in v:
            parts.append(str(x))
        print("per-element str() while iterating: " + ", ".join(parts))
        print("whole-set repr():                  " + repr(v))

actor main(env):
    s = set(["a", "b"])
    print("direct (set[str]) iteration:       " + ", ".join([str(x) for x in s]))
    show(s)
    env.exit(0)

Observed output:

direct (set[str]) iteration:       b, a
per-element str() while iterating: 4294967297, 4294967297
whole-set repr():                  {'b', 'a'}

The second line should be a, b in some order.

Testing list/set/dict side by side shows the bug is specific to the Hashable-bounded containers:

set per-elem:  4294967297, 4294967297   whole: {'b', 'a'}      (BROKEN)
list per-elem: a, b, c                   whole: ['a', 'b', 'c']  (ok)
dict per-key:  4294967297, 4294967297   whole: {'x':1, 'y':2}   (BROKEN)

And the bug only manifests when the actual element type differs from the type the solver picks: a value-narrowed set[int] / list[int] iterate fine, because the elements really are ints. Containers store boxed elements uniformly, so this is not a storage issue.

Root cause. inferTest for IsInstance (compiler/lib/src/Acton/Types.hs, around line 2351) narrows isinstance(v, set) to set[T] using a fresh univar for each of the class's type parameters:

inferTest env (IsInstance l e@(Var _ (NoQ n)) c)
    = case findQName c env of
         NClass q _ _ _ -> do
            (cs,t,e') <- infer env e
            ts <- newUnivars env [ tvkind v | v <- qbound q ]
            let tc = tCon (TC c ts)
            ...

The type argument cannot be recovered from the operand's static type (value), so T is an unconstrained univar. For set/dict the parameter is Hashable-bounded, so iterating the narrowed container produces a Hashable[T] constraint, and the solver defaults it to the oldest Hashable instance, which is int — an unboxable type. The boxing pass then unboxes each element as an int. The generated C for the show function makes it concrete:

B_Hashable W_show_66 = (B_Hashable)B_HashableD_intG_witness;   // element witness defaulted to int
...
int64_t x = ((B_int)__next__(N_iter))->val;                    // UNBOX a (boxed B_str) element as int
...append(parts, B_strG_new((B_value)toB_int(x)));             // re-box the garbage word

((B_int)elem)->val reads a B_str object through the B_int layout, yielding the 0x1_0000_0001 tag.

list is unaffected because its element parameter has no Hashable bound, so T stays free and the Cast T value arising from str(x) resolves it to value — the element stays boxed and str/repr dispatch dynamically (the loop variable is generated as B_value x, and str()/repr() take a value and dispatch on the real ->$class). The whole-container repr() works for the same reason: it uses each element's own stored witness rather than the static one.

So the only sound static element type for a value-narrowed generic container is value (dynamic dispatch), exactly like the working list path. The obstacle is that set/dict require A: Hashable, and value is not Hashable (the base value vtable has no __hash__/__eq__), so set[value] is rejected today:

def f(s: set[value]) -> int: return len(s)
# error: __builtin__.value must implement __builtin__.Hashable

set[Hashable] does work, but only as a function parameter, where the existential is opened at the call boundary and the caller supplies the element's Hashable witness as an extra argument. That has no analogue for an internal isinstance narrowing — a bare value carries no element witness — and the type checker rejects a protocol as a non-parameter (local) type ("Expected a type, actual kind is protocol").

Possible directions (looking for input on which is the right design):

1. Make value Hashable (and Eq) via identity hashing, reusing the runtime's existing B_HashableD_WORD machinery, and narrow Hashable-bounded isinstance parameters to value. This is the sound, general fix: set[value] / dict[value, _] iterate with dynamic dispatch. Cost: it is a base (Acton + C) and compiler change; it makes == on two statically-value operands resolve to identity equality and lets sets/dicts of arbitrary values typecheck; and it adds value to the Hashable/Eq instance set (registering its witnesses as newest keeps the oldest-first ambiguous defaulting unchanged, so other code still defaults to int). The semantic question — should value be hashable/comparable by identity, Python-style — is really the crux.

2. Decouple set/dict iteration from Hashable. The runtime set/dict iterators ignore the Hashable witness, so at the type level iteration arguably should not require it. Give the containers an Iterable path independent of the Hashable bound, so a value-narrowed container's element stays value like list does, with no need to make value Hashable. Risk: overlapping container extensions and changing how for over a set/dict resolves its witness everywhere.

3. Compiler-only: narrow Hashable-bounded isinstance parameters to a boxed concrete Hashable type (e.g. str) instead of int. Small and makes str/repr correct, but it is a type-lie — elements typed str would let str-specific operations compile and corrupt non-str elements. Least correct; noted only for completeness.

The downstream project already worked around this by deriving an ordering key from the whole-set repr() (which is correct), so there is no urgency, but the underlying behavior is a real correctness trap for any value-narrowed generic container.

[plajjan]

@sydow would you mind looking into this? feel free to ignore the wall of text and just focus on the reproduction case if that's easier :)

[nordlander]

So it's finally happened: the old short-cut I took with isinstance about 8 years ago has come back to bite us!👹

The core issue isn't about Hashable, str or set per se, but the fact that our type system allows a parameterized type like set[str] to be coerced into an oblivious type value and then downcasted (via isinstance) back to a set of any type, like set[X]. The correct downcasting would instead be to assume that X is not any type, but some existentially quantified type of which we know nothing except what's implied by its context – in this case that it must implement the Hashable protocol (which follows from being a valid parameter to set). Nothing else should be assumed about this unknown X. But our compiler erroneously believes the choice of X is free, so it gladly picks the first type in the environment that implements Hashable (which happens to be int).

This behavior of isinstance is a hack simply because we didn't have existential type back in 2018, yet both isinstance and value were essential to compensate for our lack of pattern-matching. Now we have the existential types under the hood but still no pattern-macthing, and I think it would be a mistake to implement the proper solution on top of the current isinstance implementation with its dead-end approach to narrowing. Because once we have pattern-matching in place we'll be able to reformulate isinstance as just a special matching case, and the rest will fall out beautifully.

Even so, there actually exists a workaround that should be enough to avoid the bad effects of isinstance in the interim. Whenever a variable is instance-tested against a parameterized type constructor, immediately assign it to a local variable of the correct expected type, and use that variable onwards. The example above would thus become

    if isinstance(v, set):
        v1: set[str] = v
        parts = []
        for x in v1:
            parts.append(str(x))

Of course this assumes that the "correct" expected type can be statically known, it won't work if v is a set[str] in one invocation and a set[int] in the next (that pattern would truly need the existential types!). But I feel hopeful the triggering use cases belong to the statically known sort.