"unable to type-check this expression in reasonable time" for a 'simple' expression

Development Compiler
1

Given the following code, the compiler gave up after several minutes with:

"The compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions"

public typealias CategoryID = Int16

var usedCats = NSCountedSet()

usedCats.add(CategoryID(1))
usedCats.add(CategoryID(7))
usedCats.add(CategoryID(99))
usedCats.add(CategoryID(99))

// Sort the used categories by use count
struct CatWithCount {
    let cat: CategoryID
    let count: Int
}

let countedCats = usedCats.allObjects.map { CatWithCount(cat: $0 as! CategoryID, count: usedCats.count(for: $0)) }
    .sorted { $0.count > $1.count ? true : $0.count == $1.count ? $0.cat < $1.cat : false }

s = ""
for i in countedCats {
    s += " {\(i.cat): \(i.count)}"
}
print(s)

Is complaining about the .sorted { ...

Easy enough to fix myself by changing it to:

let countedCats = usedCats.allObjects.map { CatWithCount(cat: $0 as! CategoryID, count: usedCats.count(for: $0)) }
    .sorted {
        if $0.count > $1.count {
            return true
        }
        if $0.count == $1.count {
            return $0.cat < $1.cat
        }
        return false
    }

But to me it doesn't seem that complicated an expression, but I'm no compiler engineer :slight_smile:

2

I don't know exactly what is happening and didn't look into any debug output but it looks like for ternary expression closure the compiler is having trouble inferring $0 and $1 as CatWithCount. Type annotate the closure may workaround the issue

let countedCats = usedCats.allObjects.map { CatWithCount(cat: $0 as! CategoryID, count: usedCats.count(for: $0)) }
    .sorted { (c1: CatWithCount, c2: CatWithCount) in c1.count > c2.count ? true : c1.count == c2.count ? c1.cat < c2.cat : false }

Maybe worth opening an issue?
cc @xedin @hborla

3

Slowness of the ternary infamous unfortunately, it was even recently mentioned during review of if/switch expressions. There just be an issue open for that already on GitHub, but if you can't find one please feel free to open it.

3 Likes
4

Also, this is just

($0.count, $1.cat) > ($1.count, $0.cat)

And .allObjects isn't necessary because NSCountedSet is itself a Sequence.

3 Likes
5

($0.count, $1.cat) > ($1.count, $0.cat). That doesn't work for me as if the counts are equal, I want the one with the lowest category ID to sort first. But thanks as I didn't know you could do that with tuples.

What would be nice is the ability to creates sorts like this (with totally fictitious syntax)

.sorted { (>(\count), <(\cat)) }

allObjects - Thanks - I lived in the Objective C world for too long :grinning:

6

Sadly that didn't help. Still just as slow.

7

Depending on if you fulfil the platform requirements (e.g iOS 15+, macOS 12.0+) you could use sorted(using:).

let countedCats = usedCats.allObjects.map { CatWithCount(cat: $0 as! CategoryID, count: usedCats.count(for: $0)) }
    .sorted(using: [
        KeyPathComparator(\.count, order: .reverse),
        KeyPathComparator(\.cat, order: .forward)
    ])

I tried it out in playgrounds and it prints the following:

{99: 2} {1: 1} {7: 1}
1 Like
8

Which version of compiler are you using? 5.7 compiles relatively quick. See Compiler Explorer where the original just timeout.

9

Yes, that is how it works. The later tuple element comparisons are the same idea as ThenBy in C#, for example.

10

I'm confused as yes, that produces the expected result, but it doesn't seem to match what the documentation says for the tuple > operator:
" Given two tuples (a1, a2, ..., aN) and (b1, b2, ..., bN) , the first tuple is after the second tuple if and only if a1 > b1 or (a1 == b1 and (a2, ..., aN) > (b2, ..., bN) )."

11

In ($0.count, $1.cat) > ($1.count, $0.cat),
Note that $0 and $1 are swapped in the second element, providing the reversal you want.

1 Like