Module Asllib.TopoSortSource

Topological sorting of ASTs.

In the following, dependencies are understood in the ASL declaration level. For example, in the following ASL code:

   constant x: integer = 4;
   constant y: integer = x + 1;

the type-checker should first type-check x and put it in the environment, before type-checking y, which would otherwise complain about x not being defined.

We also need strongly connected components analysis for mutually recursive functions, which are allowed in ASL. For example, the following example should be legal:

   func f (x: integer) => integer
   begin return 2 * g (x - 1); end

   func g (x: integer) => integer
   begin return if x <= 0 then -x else 1 + f(x); end

Those two function should be handled by the type-checker at the same time: both need the declaration of the other to be correctly type-checked.

Abstract implementation of topological sorting