Adding a lint for Unconditional Recursion: checking the statements that appear before the recursive call

Eesha Shekhar · facebook-github-bot · commit 5c8e50640e68 · 2022-07-15T08:16:38.000-07:00
Summary:
This produces a lint error of unconditional recursion when there is a top level recursive call and there is no return or throw statement to break out of the recursion before the recursive call. The return or throw statement could be within multiple nested conditionals. The expression following the return/throw statement is checked to ensure that it is anything other than a recursive call. If there are mutliple base cases, then it is considered unconditional recursion if each of the return or throw statements in the base cases are recursive function calls.
The function/method may or may not have arguments.
The different types of function/method calls detected by linter are:
1) return statements
2) throw statements
3) static methods
4) instance methods
5) Await

Reviewed By: Wilfred

Differential Revision: D37754411

fbshipit-source-id: c2767d1df54350072b8663de5705d786b7aa5313
diff --git a/hphp/hack/src/lints/linter_unconditional_recursion.ml b/hphp/hack/src/lints/linter_unconditional_recursion.ml
@@ -8,86 +8,126 @@
 open Aast
 open Hh_prelude
 
+type method_prop = {
+  method_name: string;
+  class_name: string;
+  pos: Pos.t;
+}
+
+type fun_prop = {
+  fun_name: string;
+  pos: Pos.t;
+}
+
+type is_fun_or_method =
+  | Is_fun of fun_prop
+  | Is_method of method_prop
+
 let same_name_ignoring_ns (name1 : string) (name2 : string) =
   String.equal (Utils.strip_ns name1) (Utils.strip_ns name2)
 
-let check_expr_fun (expr_ : Tast.expr_) (fun_name : string) =
-  match expr_ with
-  | Aast.Call ((_, _, Aast.Id (_, name)), _, _, _) ->
-    same_name_ignoring_ns name fun_name
-  | _ -> false
-
-let check_expr_method
-    (expr_ : Tast.expr_) (method_name : string) (c_name : string) =
-  match expr_ with
-  | Aast.Call
-      ( ( _,
+let check_expr (expr_ : Tast.expr_) (is_fun_or_method : is_fun_or_method) =
+  match is_fun_or_method with
+  | Is_fun f_prop ->
+    (match expr_ with
+    | Aast.Call ((_, _, Aast.Id (_, name)), _, _, _) ->
+      same_name_ignoring_ns name f_prop.fun_name
+    | _ -> false)
+  | Is_method m_prop ->
+    (match expr_ with
+    | Aast.Call
+        ( ( _,
+            _,
+            Aast.Obj_get
+              ((_, _, Aast.This), (_, _, Aast.Id (_, name)), _, Aast.Is_method)
+          ),
           _,
-          Aast.Obj_get
-            ((_, _, Aast.This), (_, _, Aast.Id (_, name)), _, Aast.Is_method) ),
-        _,
-        _,
-        _ ) ->
-    same_name_ignoring_ns name method_name
-  | Aast.Call
-      ( (_, _, Aast.Class_const ((_, _, Aast.CI (_, name_of_class)), (_, name))),
-        _,
-        _,
-        _ )
-    when same_name_ignoring_ns name_of_class c_name ->
-    same_name_ignoring_ns name method_name
-  | Aast.Call
-      ((_, _, Aast.Class_const ((_, _, Aast.CIstatic), (_, name))), _, _, _) ->
-    same_name_ignoring_ns name method_name
-  | Aast.Call
-      ((_, _, Aast.Class_const ((_, _, Aast.CIself), (_, name))), _, _, _) ->
-    same_name_ignoring_ns name method_name
-  | _ -> false
+          _,
+          _ ) ->
+      same_name_ignoring_ns name m_prop.method_name
+    | Aast.Call
+        ( ( _,
+            _,
+            Aast.Class_const ((_, _, Aast.CI (_, name_of_class)), (_, name)) ),
+          _,
+          _,
+          _ )
+      when same_name_ignoring_ns name_of_class m_prop.class_name ->
+      same_name_ignoring_ns name m_prop.method_name
+    | Aast.Call
+        ((_, _, Aast.Class_const ((_, _, Aast.CIstatic), (_, name))), _, _, _)
+      ->
+      same_name_ignoring_ns name m_prop.method_name
+    | Aast.Call
+        ((_, _, Aast.Class_const ((_, _, Aast.CIself), (_, name))), _, _, _) ->
+      same_name_ignoring_ns name m_prop.method_name
+    | _ -> false)
 
-let is_recursion_in_fun ((_, stmt_) : Tast.stmt) (fun_name : string) =
+let is_recursive_call
+    ((_, stmt_) : Tast.stmt) (is_fun_or_method : is_fun_or_method) =
   match stmt_ with
   | Aast.Return (Some (_, _, Aast.Await (_, _, await_exp))) ->
-    check_expr_fun await_exp fun_name
-  | Aast.Return (Some (_, _, e)) -> check_expr_fun e fun_name
+    check_expr await_exp is_fun_or_method
+  | Aast.Return (Some (_, _, e)) -> check_expr e is_fun_or_method
+  | Aast.Throw (_ty, _pos, expr_) -> check_expr expr_ is_fun_or_method
   | Aast.Expr (_ty, _pos, Aast.Await (_, _, await_exp)) ->
-    check_expr_fun await_exp fun_name
-  | Aast.Expr (_ty, _pos, expr_) -> check_expr_fun expr_ fun_name
+    check_expr await_exp is_fun_or_method
+  | Aast.Expr (_ty, _pos, expr_) -> check_expr expr_ is_fun_or_method
   | _ -> false
 
-let is_recursion_in_method
-    ((_, stmt_) : Tast.stmt) (method_name : string) (c_name : string) =
-  match stmt_ with
-  | Aast.Return (Some (_, _, Aast.Await (_, _, await_exp))) ->
-    check_expr_method await_exp method_name c_name
-  | Aast.Return (Some (_, _, e)) -> check_expr_method e method_name c_name
-  | Aast.Expr (_ty, _pos, Aast.Await (_, _, await_exp)) ->
-    check_expr_method await_exp method_name c_name
-  | Aast.Expr (_ty, _pos, expr_) -> check_expr_method expr_ method_name c_name
-  | _ -> false
+(* This function returns true if the recursion can be terminated. This occurs when we find at least one return or throw statment that is followed by any expression other than a recursive call*)
+let can_terminate_visitor is_fun_or_method =
+  object
+    inherit [_] Aast.reduce as super
 
-let check_unconditional_recursion m c_name =
-  match m.m_body.fb_ast with
-  | head :: _ ->
-    if is_recursion_in_method head (snd m.m_name) c_name then
-      Lints_errors.unconditional_recursion m.m_span
-    else
+    method zero = false
+
+    method plus = ( || )
+
+    method! on_stmt env s =
+      match snd s with
+      | Aast.Return _ -> not (is_recursive_call s is_fun_or_method)
+      | Aast.Throw _ -> not (is_recursive_call s is_fun_or_method)
+      | _ -> super#on_stmt env s
+  end
+
+let can_terminate (s : Tast.stmt) (is_fun_or_method : is_fun_or_method) : bool =
+  (can_terminate_visitor is_fun_or_method)#on_stmt () s
+
+let rec check_unconditional_recursion
+    (stmt_list : Tast.stmt list) (is_fun_or_method : is_fun_or_method) =
+  match stmt_list with
+  | head :: tail ->
+    if can_terminate head is_fun_or_method then
       ()
+    else if is_recursive_call head is_fun_or_method then
+      match is_fun_or_method with
+      | Is_fun f_prop -> Lints_errors.unconditional_recursion f_prop.pos
+      | Is_method m_prop -> Lints_errors.unconditional_recursion m_prop.pos
+    else
+      check_unconditional_recursion tail is_fun_or_method
   | [] -> ()
 
 let handler =
   object
     inherit Tast_visitor.handler_base
 
     method! at_fun_def _env f =
-      match f.fd_fun.f_body.fb_ast with
-      | head :: _ ->
-        if is_recursion_in_fun head (snd f.fd_fun.f_name) then
-          Lints_errors.unconditional_recursion f.fd_fun.f_span
-        else
-          ()
-      | [] -> ()
+      let f_properties : fun_prop =
+        { fun_name = snd f.fd_fun.f_name; pos = f.fd_fun.f_span }
+      in
+      let is_f_or_m : is_fun_or_method = Is_fun f_properties in
+      check_unconditional_recursion f.fd_fun.f_body.fb_ast is_f_or_m
 
     method! at_class_ _env c =
       List.iter c.c_methods ~f:(fun c_method ->
-          check_unconditional_recursion c_method (snd c.c_name))
+          let m_properties : method_prop =
+            {
+              method_name = snd c_method.m_name;
+              class_name = snd c.c_name;
+              pos = c_method.m_span;
+            }
+          in
+          let is_f_or_m : is_fun_or_method = Is_method m_properties in
+          check_unconditional_recursion c_method.m_body.fb_ast is_f_or_m)
   end
diff --git a/hphp/hack/test/lint/recursion_no_base_case.php b/hphp/hack/test/lint/recursion_no_base_case.php
@@ -1,14 +1,15 @@
 <?hh
+// @format
 
 function foo1(): void {
-  foo1(); // stack overflow, produces lint
+  foo1(); //should produce lint
 }
 function foo2(): void {
-  foo2(); // stack overflow, produces lint
+  foo2(); //should produce lint
   $x = 1;
 }
 function foo3(): void {
-  $x = 1; //should not produce lint
+  $x = 1; //should produce lint
   foo3();
 }
 function foo4(int $x): void {
@@ -21,6 +22,102 @@ function foo5(): void {
   await foo6(); //should produce lint
 }
 
+function test_throw_lint(): Error {
+  throw test_throw_lint(); // should produce lint
+}
+
+//Testing for conditionals
+
+function test_if_return(): int {
+  $x1 = 2;
+  if ($x1 == 2) {
+    return $x1;
+  }
+  return test_if_return(); //should not produce lint
+}
+function test_if_void(): void {
+  $x1 = 2;
+  if ($x1 == 2) {
+    return;
+  }
+  test_if_void(); //should not produce lint
+}
+
+function test_multiple_base_cases_lint(int $x): int {
+  if ($x == 1) {
+    return test_multiple_base_cases_lint($x);
+  } else if ($x == 2) {
+    return test_multiple_base_cases_lint(1);
+  }
+  return test_multiple_base_cases_lint($x); //should produce lint
+}
+
+function test_multiple_base_cases_no_lint(int $x): int {
+  if ($x == 1) {
+    return 1;
+  } else if ($x == 2) {
+    return test_multiple_base_cases_no_lint(1);
+  }
+  return test_multiple_base_cases_no_lint($x); //should not produce lint
+}
+
+function test_multiple_base_cases_no_lint_throw(int $x): int {
+  if ($x == 1) {
+    throw new Error('error');
+  } else if ($x == 2) {
+    return test_multiple_base_cases_no_lint_throw(1);
+  }
+  return test_multiple_base_cases_no_lint_throw($x); //should not produce lint
+}
+
+function test_multiple_base_cases_lint_throw(int $x): Error {
+  if ($x == 1) {
+    throw test_multiple_base_cases_lint_throw($x);
+  } else if ($x == 2) {
+    return test_multiple_base_cases_lint_throw(1);
+  }
+  return test_multiple_base_cases_lint_throw($x); //should produce lint
+}
+
+function test_return_in_else_no_lint(int $x): int {
+  if ($x == 1) {
+    return test_return_in_else_no_lint(1);
+    ;
+  } else if ($x == 2) {
+    return 2;
+  }
+  return test_return_in_else_no_lint($x); //should not produce lint
+}
+
+function test_nested_ifs_lint(int $x): int {
+  if ($x == 1) {
+    if ($x == 2) {
+      return test_nested_ifs_lint($x);
+    }
+  } else if ($x == 2) {
+    return test_nested_ifs_lint(1);
+  }
+  return test_nested_ifs_lint($x); //should produce lint
+}
+
+function test_nested_ifs_no_lint(int $x): int {
+  if ($x == 1) {
+    if ($x == 2) {
+      return $x;
+    }
+  } else if ($x == 2) {
+    return test_nested_ifs_no_lint(1);
+  }
+  return test_nested_ifs_no_lint($x); //should not produce lint
+}
+
+function test_no_return_no_lint(int $i): void {
+  if ($i > 0) {
+    echo "$i";
+    test_no_return_no_lint($i - 1); //should not produce lint
+  }
+}
+
 class Foo {
   public static function bar(): void {
     Foo::bar(); //should produce lint
@@ -29,10 +126,10 @@ public static function bar2(): void {
     static::bar2(); //should produce lint
   }
   public function bar4(): void {
-     $this->bar4(); //should produce lint
+    $this->bar4(); //should produce lint
   }
   public static function bar5(int $x): void {
-    Foo::bar5(123); //should produce lint
+    Foo::bar5($x); //should produce lint
   }
   public static function returnBar(): int {
     return Foo::returnBar(); //should produce lint
@@ -44,13 +141,68 @@ public static function returnBar2(): int {
   public static function returnBar3(): int {
     return self::returnBar3(); //should produce lint
   }
-
   public function returnBar4(): int {
-     return $this->returnBar4(); //should produce lint
+    return $this->returnBar4(); //should produce lint
   }
 
   public async function returnAwaitExpr(): Awaitable<void> {
-     return await $this->returnAwaitExpr(); //should produce lint
+    return await $this->returnAwaitExpr(); //should produce lint
+  }
+  public function returnBar5(): int {
+    $x1 = 2;
+    if ($x1 == 2) {
+      return $x1;
+    }
+    return $this->returnBar5(); //should not produce lint
+  }
+  public function testMultipleBaseCasesLint(int $x): int {
+    if ($x == 1) {
+      return $this->testMultipleBaseCasesLint($x);
+    } else if ($x == 2) {
+      return $this->testMultipleBaseCasesLint(1);
+    }
+    return $this->testMultipleBaseCasesLint($x); //should produce lint
+  }
+
+  public function testMultipleBaseCasesNoLint(int $x): int {
+    if ($x == 1) {
+      return 1;
+    } else if ($x == 2) {
+      return $this->testMultipleBaseCasesNoLint(1);
+    }
+    return $this->testMultipleBaseCasesNoLint($x); //should not produce lint
+  }
+
+  public function testReturnInElseNoLint(int $x): int {
+    if ($x == 1) {
+      return $this->testReturnInElseNoLint(1);
+      ;
+    } else if ($x == 2) {
+      return 2;
+    }
+    return $this->testReturnInElseNoLint($x); //should not produce lint
+  }
+
+  public function testNestedIfsLint(int $x): int {
+    if ($x == 1) {
+      if ($x == 2) {
+        return $this->testNestedIfsLint($x);
+      }
+    } else if ($x == 2) {
+      return $this->testNestedIfsLint(1);
+    }
+    return $this->testNestedIfsLint($x); //should produce lint
+  }
+
+  public function testNestedIfsNoLint(int $x): int {
+    if ($x == 1) {
+      if ($x == 2) {
+        return $x;
+      }
+    } else if ($x == 2) {
+      return $this->testNestedIfsNoLint(1);
+    }
+    return $this->testNestedIfsNoLint($x); //should not produce lint
   }
 }
 
diff --git a/hphp/hack/test/lint/recursion_no_base_case.php.exp b/hphp/hack/test/lint/recursion_no_base_case.php.exp
