Kompilator - sprawdzanie powrotu

12 Marca 2019

W językach imperatywnych rozróżniamy dwa rodzaje funkcji - takie, które zwracają wartość i takie, które nic nie zwracają (void). Chcielibyśmy się upewnić, że jeśli funkcja ma coś zwracać to zwraca wartość na każdej ścieżce wykonania.

W moim kompilatorze moduł ReturnChecker jest jednym z mniejszych. Ten moduł odpowiada za trzy rzeczy:

  1. sprawdzanie czy funkcja zwraca wartość na wszystkich ścieżkach
  2. dodawanie domyślnego return na koniec funkcji void, które go nie mają
  3. usuwanie martwego kodu po return w bloku

Zaczynam od zejścia po drzewie AST do funkcji i metod, a następnie dla każdej z nich uruchamiam usuwanie martwego kodu. Przechodzimy blok kodu i w miejscu polecenia return oznaczamy koniec listy poleceń. Możemy robić to rekurencyjnie dla podbloków, wyrażeń warunkowych i pętli.

Następnie patrzę na typ funkcji. Jeśli zwraca nic nie zwraca, to patrzę czy ostatnie polecenie to return, a jak nie to takie dopisuję na koniec.

Jeśli funkcja zwraca to zaczynam przechodzić jej ciało. Powiemy że blok poleceń zwraca, jeśli posiada polecenie, które zwraca. Polecenie, które zawsze zwraca to return x. Wyrażenie warunkowe if..else.. zwraca jeśli obie gałęzie zwracają. Pętla while, która kręci się w nieskończoność (w języku bez break) zawsze zwraca, bo albo wyjdziemy z funkcji przez return x, albo będziemy się kręcić w nieskończoność i wtedy brak zwrotu nam nie przeszkadza. Pętla while z warunkiem zwraca wtedy jej ciało zwraca.

Co w moim kodzie wygląda tak:

checkS (ReturnValue _ _) = return True
checkS (IfElse _ (Lit _ (Bool _ True)) s1 _) = checkS s1
checkS (IfElse _ (Lit _ (Bool _ False)) _ s2) = checkS s2
checkS (IfElse _ _ s1 s2) = do
    b1 <- checkS s1
    b2 <- checkS s2
    return (b1 && b2)
checkS (While _ (Lit _ (Bool _ True)) _) = return True
checkS (While _ _ s) = checkS s
checkS (BlockStmt _ b) = checkB b
checkS _ = return False

Podczas pisania kompilatora, nie mogłem znaleźć właśnie takiego prostego opisu i to było powodem, dlaczego zacząłem pisać te posty.

Co jeśli mamy break lub continue w naszej pętli? Z tego co rozumiem, to taka pętla zwraca, wtedy gdy przed return nie występuje break ani continue na żadnej ścieżce, bo inaczej można ten return ominąć.