idris-lang / Idris2

A purely functional programming language with first class types
https://idris-lang.org/
Other
2.46k stars 368 forks source link

fixed bugs that caused compiler to hang forever when there is `%tcinline` pragma #3257

Closed AntonPing closed 2 months ago

AntonPing commented 2 months ago

Description

The cause of looping in total026 is pretty complicated. Consider such an example:

%tcinline
incAll' : Stream Nat -> Stream Nat
incAll' = \(x::xs) => S x :: incAll' xs

The lambda function with pattern matching \(x::xs) => ... is actually encoded in such way(f is a fresh variable):

incAll' = f
f (x::xs) => S x :: incAll' xs

In CallGraph.idr, such f is called a case function, and they are treated specially: each time findSCall meets a case function, it will jump to the definition of the case function, and it won't be treated as regular function call. After tcinlining, f becomes a recursive definition:

incAll' = f
f (x::xs) => S x :: f xs

In such way, findSCall in CallGraph.idr will loop forever here, since it corresponds to a program of infinite length:

incAll' =  \(x::xs) => S x :: (\(x::xs) => S x :: (\(x::xs) => S x :: (\(x::xs) =>  ... ))) ...)

The fix in CallGraph.idr introduce a new parameter cbs. Each time findSCall enters a case function, it appends the function name to cbs. If it's already there, findSCall then will treat it as a regular function call.

gallais commented 2 months ago

Was the fix invalid or?

buzden commented 2 months ago

Was the fix invalid or?

As a superviser of this work, I can say that this fix is okay, but still leaves some cases where some total functions that can be checked as total, are not checked as total. That's why another PR that this one relies on is being prepared. This PR should have been converted to a draft rather than being closed.

AntonPing commented 2 months ago

This pull request is moved to #3272, since github doesn't allow me to reopen it.