eclipse-langium / langium

Next-gen language engineering / DSL framework
https://langium.org/
MIT License
725 stars 65 forks source link

Add validation against function call recursion #1019 #1296

Closed hpopov closed 10 months ago

hpopov commented 10 months ago

Resolves #1019. Recursion validation implemented using BFS algorithm for nested function calls as graph nodes.

Implemented scenarios:

  1. Function calls itself def fun1(x): fun1(x);
  2. Several functions calls each other in a cycle, e.g.:
def fun1(x):
    fun2(x) + fun2(x) + fun3(x);

def fun2(x):
    fun3(x) + fun4(x);

def fun3(x):
    3*x;

def fun4(x):
    fun3(x) + fun1(x);

Here every affected call in the cycle gets a validation error (fun1::fun2, fun2::fun4, and fun4::fun1). In case a function B is called several times from a function A, only first call instance is marked with error (e.g., only first fun1::fun2).

  1. If a Module has multiple recursion cycles, all of them are identified. See example scenarios in example/recursions.calc.