[BUG] candidate not viable: argument #0 cannot be converted from 'Set[Int]' to 'Set[Int]'

[mzaks]

Bug description

This bug is a blocker for PR #3701

It is a compiler bug where compiler can't identify that assert_true(any(Set(-1))) should pick fn any[T: BoolableKeyElement](set: Set[T]) -> Bool: function. It the compiler tells candidate not viable: argument #0 cannot be converted from 'Set[Int]' to 'Set[Int]'

Full Error log:

RUN: at line 13: mojo -D ASSERT=all /Users/mzaks/dev/mojo/stdlib/test/builtin/test_any_all.mojo
+ mojo -D ASSERT=all /Users/mzaks/dev/mojo/stdlib/test/builtin/test_any_all.mojo
/Users/mzaks/dev/mojo/stdlib/test/builtin/test_any_all.mojo:73:20: error: no matching function in call to 'any'
    assert_true(any(Set(-1)))
                ~~~^~~~~~~~~
/Users/mzaks/dev/mojo/stdlib/src/builtin/bool.mojo:548:4: note: candidate not viable: could not deduce parameter 'T' of callee 'any'
fn any[T: BoolableCollectionElement](list: List[T, *_]) -> Bool:
   ^
/Users/mzaks/dev/mojo/stdlib/test/builtin/test_any_all.mojo:73:20: note: failed to infer parameter 'T', parameter isn't used in any argument
    assert_true(any(Set(-1)))
                ~~~^~~~~~~~~
/Users/mzaks/dev/mojo/stdlib/src/builtin/bool.mojo:566:4: note: candidate not viable: argument #0 cannot be converted from 'Set[Int]' to 'Set[Int]'
fn any[T: BoolableKeyElement](set: Set[T]) -> Bool:
   ^
/Users/mzaks/dev/mojo/stdlib/src/builtin/bool.mojo:584:4: note: candidate not viable: failed to infer implicit parameter 'type' of argument 'value' type 'SIMD'
fn any(value: SIMD) -> Bool:
   ^
/Users/mzaks/dev/mojo/stdlib/test/builtin/test_any_all.mojo:73:20: note: failed to infer parameter #0, parameter isn't used in any argument
    assert_true(any(Set(-1)))
                ~~~^~~~~~~~~
mojo: error: failed to parse the provided Mojo source module

--

Steps to reproduce

See PR #3701 you can uncomment lines followed by marker # TODO: this was working before

System information

- What OS did you do install Mojo on ?
Apple m1, macOS 14.5 (23F79)
- Provide version information for Mojo by pasting the output of `mojo -v`
mojo 2024.10.2406 (54f70ee8)
- Provide Magic CLI version by pasting the output of `magic -V` or `magic --version` 
magic 0.3.1 - (based on pixi 0.29.0)
- Optionally, provide more information with `magic info`.

      Pixi version: 0.29.0
          Platform: osx-arm64
  Virtual packages: __unix=0=0
                  : __osx=14.5=0
                  : __archspec=1=m1
         Cache dir: /Users/mzaks/Library/Caches/rattler/cache
      Auth storage: /Users/mzaks/.rattler/credentials.json
  Config locations: No config files found

Project
------------
              Name: Mojo
     Manifest file: /Users/mzaks/dev/mojo/pixi.toml
      Last updated: 24-10-2024 14:12:43

Environments
------------
       Environment: default
          Features: default
          Channels: conda-forge, https://conda.modular.com/max-nightly
  Dependency count: 2
      Dependencies: python, max
  Target platforms: osx-arm64, linux-64, linux-aarch64
             Tasks: examples, benchmarks, tests

[JoeLoser]

I suspect this is a generic type-checking bug. If you try a memory-only type wrapper workaround like in

mojo/stdlib/src/builtin/sort.mojo

Line 34 in 5babce6

struct _SortWrapper[type: CollectionElement](CollectionElement):

, does that work? Note that this pattern of MemoryOnlyWrapper could be generalized.

[soraros]

@JoeLoser I don't think it's reg-type causing problem here. Somehow Int in Set[Int] is not recognised as BoolableKeyElement (under the updated definition of Hashable that is).

@value
struct S[T: KeyElement]:
  ...

fn f[T: BoolableKeyElement](set: S[T]) -> Bool:
  return False

fn g[T: KeyElement](set: S[T]) -> Bool:
  return False

fn main():
  s = S[Int]()
  f(s)  # invalid call to 'f': argument #0 cannot be converted from 'S[Int]' to 'S[Int]'
  g(s)

Update: no longer reproduce on mojo 2024.11.1105.

[lattner]

FYI, I tried this out just now and the example directly above appears to be fixed. Can you take a look to see if this is still broken, and if so, include an updated small example? Thanks!

[soraros]

@mzaks I tried rebasing your PR onto nightly, and the original problem does seem to have gone away.

[mzaks]

@lattner Sadly the bug is not resolved yet, I kept two failing statements around in my PR branch
https://github.com/modularml/mojo/actions/runs/11779927544/job/32809415138?pr=3701#step:6:33

Would this be enough for the team to easily reproduce the error? I can try to write a smaller example, but I think it is not that trivial as it seems to be related to the Int type conforming to a different Hashable trait through KeyElement trait. Please let me know if the branch above is not enough, so I will try to create a smaller PR.

[soraros]

Actually, I think Joe was right and it might be reg-type related after all.

trait T1:
  fn __hash__[H: AnyType](self):
    ...

trait T2(T1):
  pass

@register_passable("trivial")  # comment this line out and the problem goes away
struct I(T1):
  fn __hash__[H: AnyType](self):
    pass

@value
struct S[T: T1]:
  ...

fn f[U: T2](self: S[U]):
  ...

fn main():
  s = S[I]()
  f(s)

[lattner]

Yes, I think that is likely to be the root of it. We have some logic that tries to make regpassable trivial types conform to copyable/anytype etc by using a wrapper struct struct __MLIRType in the stdlib, and the logic to do it looks quite busted. I'm not sure if you're interested in htis @VerdagonModular but there are a cluster of bugs around it.