Typer thrown into infinite loop over some type definitions.

[rcano]

Compiler version

3.3.0-RC4 (but also versions prior)

Minimized code

import scala.compiletime.ops.int.*
import scala.compiletime.ops.boolean.*

object Sudoku {
  object blank
  type x = blank.type

  type Range[Min <: Int, Max <: Int] <: Tuple = Min match {
    case Max => EmptyTuple
    case _ => Min *: Range[Min + 1, Max]
  }
  type IncRange[Min <: Int, Max <: Int] = Range[Min, Max + 1]

  type _TupleDedupAux[Tup <: Tuple, Mask] <: Tuple = Tup match {
    case EmptyTuple => EmptyTuple
    case h *: t =>
      h match {
        case Mask => _TupleDedupAux[t, Mask]
        case _ => h *: _TupleDedupAux[t, h | Mask]
      }
  }
  type TupleDedup[Tup <: Tuple] = _TupleDedupAux[Tup, Nothing]
  type TupleIntersect[Tup1 <: Tuple, Tup2 <: Tuple] = Tuple.Filter[Tup1, [e] =>> _TupleIntersectAux[e, Tuple.Union[Tup2]]]
  type _TupleIntersectAux[E, Mask] <: Boolean = E match {
    case Mask => true
    case _ => false
  }
  type CoordToPos[r <: Int, c <: Int] = r * 9 + c
  type Cell[r <: Int, c <: Int, Board <: Tuple] = Tuple.Elem[Board, CoordToPos[r, c]]
  type Row[r <: Int, Board <: Tuple] = Tuple.Take[Tuple.Drop[Board, r * 9], 9]
  type Col[c <: Int, Board <: Tuple] = Tuple.Map[Range[0, 9], [r <: Int] =>> Cell[r, c, Board]]
  type SubRegion[minr <: Int, maxr <: Int, minc <: Int, maxc <: Int, Board <: Tuple] = Tuple.Map[
    Tuple.FlatMap[Range[minr, maxr], [row] =>> Tuple.Map[Range[minc, maxc], [col] =>> (row, col)]],
    [x] =>> x match { case (row, col) => Cell[row, col, Board] }
  ]
  // this can probaly be done nicerly, but MEH!
  type Quadrant[q <: Int, Board <: Tuple] <: Tuple = q match {
    case 0 => SubRegion[0, 3, 0, 3, Board]
    case 1 => SubRegion[0, 3, 3, 6, Board]
    case 2 => SubRegion[0, 3, 6, 9, Board]
    case 3 => SubRegion[3, 6, 0, 3, Board]
    case 4 => SubRegion[3, 6, 3, 6, Board]
    case 5 => SubRegion[3, 6, 6, 9, Board]
    case 6 => SubRegion[6, 9, 0, 3, Board]
    case 7 => SubRegion[6, 9, 3, 6, Board]
    case 8 => SubRegion[6, 9, 6, 9, Board]
  }

  type AvailableOptions[Taken] = Tuple.FlatMap[Range[1, 10], [e] =>> _AvailableOptionsAux[e, Taken]]
  type _AvailableOptionsAux[T, Taken] <: Tuple = T match {
    case Taken => EmptyTuple
    case _ => T *: EmptyTuple
  }
  type AvailableOptionsFromTuple[Taken <: Tuple] = AvailableOptions[Tuple.Union[Taken]]

  type RowFromPos[Pos <: Int] = Pos / 9
  type ColFromPos[Pos <: Int] = Pos % 9
  type QuadrantFromPos[Pos <: Int] = (Pos / 27) * 3 + ColFromPos[Pos] / 3
  type Board = Tuple

  type Candidates[B <: Board, Pos <: Int] = TupleIntersect[
    AvailableOptions[Tuple.Union[Row[RowFromPos[Pos], B]]],
    TupleIntersect[
      AvailableOptions[Tuple.Union[Col[ColFromPos[Pos], B]]],
      AvailableOptions[Tuple.Union[Quadrant[QuadrantFromPos[Pos], B]]]
    ]
  ]
  type PickCandidate[B <: Board, Pos <: Int] = Candidates[B, Pos] match {
    case EmptyTuple => x
    case h *: _ => h
  }

  type Patch[B <: Board, At <: Int, E] = Tuple.Concat[
    Tuple.Take[B, At],
    E *: Tuple.Drop[B, At + 1]
  ]

  // this Solve definition should be equivalent to the Tuple.Fold one in AlternativeSolve, and indeed both throw the compiler into a seemingly infinite loop

  type _SolveAux[B <: Board, Pos <: Int] <: Board = Pos match {
    case 81 => B
    case _ => _SolveAux[Patch[B, Pos, PickCandidate[B, Pos]], Pos + 1]
  }

  type Solve[B <: Board] = _SolveAux[B, 0]

  // type AlternativeSolve[B <: Board] = Tuple.Fold[Range[0, 81], B, [ord, board] =>> Patch[board, ord, PickCandidate[board, ord]]]

}

Output

The compiler goes into an seemingly infinite loop, as it never ends. If you comment out the Solve type at the bottom, then it compiles pretty quickly (but if you switch the Solve for the AlternativeSolve, you also get the infinite recursion). Also note that all the intermediate step work fine (as tested elsewhere). I don't understand why the last recursion seems to kill it when the type itself, is not even being used, it's just being defined (i.e, not applied over an actual Board in a way that it would have to run all the type matches).

Expectation

The typer should at least return. Can't even say the typer is correct or wrong, because it just doesn't produce a result ever.

[sjrd]

I don't understand why the last recursion seems to kill it when the type itself, is not even being used, it's just being defined (i.e, not applied over an actual Board in a way that it would have to run all the type matches).

Some element of answer: that match can actually be expanded quite a lot, because Pos is known, and the recursion can unfold 81 times without looking at B, internally creating a gigantic type in the process. That may be what's killing the typechecker.

[rcano]

I originally tried with a much smaller number, like 10, same result. I can try with a much a smaller number.

[rcano]

So with a limit of 2 cells in Solve, it completed in something less than 20 seconds, with a limit of 4 it's been 10 minutes compiling and no result. What I don't quite understand is that there's a fixed number of iterations per cell, so when you go from 2 cells to 4, I'd expect an extra compilation time that's proportional, instead of this seemingly exponential situation. JVisualVm doesn't show the compiler going crazy with allocation rates, just cpu spinning.