Odin: Mutual Recursion Analyzer

# Odin: Mutual Recursion Analyzer The analyzer is capable of detecting mutual recursion caused by method redefinition during inheritance. ## Identifiable patterns Only the following patterns are recognized by the algorithm: ### 1. Object declarations: ``` [] > name {0 or 1 decoratee} {>= 0 method declarations} {>= 0 object declarations} ``` ### 2. Decoratee ``` simple_name > @ or an.attribute.of.some.object > @ ``` ### 3. Method declarations: ``` [self {>= 0 params}] > methodName {>= 0 method calls} > @ ``` ### 4. Method calls: ``` self.methodName self {>= 0 params} ``` ## Known Shortcomings ### 1. Some decorations are ignored. The algorithm supports only two kinds of decorations: simple applications, like `fruit > @`, and attribute decorations, like `fruits.citrus.orange > @`. **All the other patterns are ignored, thus an object containing such pattern is considered to not have a `@` attribute at all!** For example, in this program: ``` [] > baobab 1.add 2 > @ [self] > stall ``` the statement `1.add 2 > @` is ignored so, the algorithm 'sees' this program like so: ``` [] > baobab [self] > stall ``` ### 2. Unreachable code The algorithm takes into consideration every possible method call that is present in the body, whether it is actually called does not matter. For example, in method `zen`: ``` [self] > zen if. > @ false self.no self self.yes self ``` The algorithm will consider both `no` and `yes` method calls, even though `no` is never called. The same goes for unused local definitions. In EO, "method" is an object containing a special `@` (phi) attribute. When the method is called: ``` self.method self ``` it is the object labelled by `@` that gets executed. Any other local bindings that are not used in the binding associated with `@` are ignored. For example: ``` [self] > m fib 100000 > huge_computation! 1.add 1 > @ ``` Only `1.add 1` will be computed when method `m` is called. The `huge_computatuion` will never be performed (since it is never called in the declaration of `@`). That being said, if `huge_computation` is a method call, say: ``` [self] > m # a valid method call now! self.fib self 100000 > huge_computation! 1.add 1 > @ ``` The algorithm would still consider it as "called". In other words, it will be a part of the analyzer output if it is a part of some mutual recursion chain. Furthermore, the algorithm does not run any checks for the presence of `@` attribute. As a result, a method that would produce a runtime error when called, like: ``` [self] > m self.fib self 100000 > huge_computation! # this is no longer `@` 1.add 1 > two ``` is still considered by the algorithm. ### 3. Inheritance chains with cycles Even though the following code is perfectly valid in EO: ``` [] > a b > @ [] > b a > @ ``` This code (and the similar variations) will cause the analyzer to fail with `StackOverflowError`. ## Algorithm description 1. Parse the source code to build its AST. 2. Create a tree of partial objects that preserves the object nestedness. Basically, collect all the information that can be collect within a single pass. 3. This tree is then refined to create a complete representation of the program, with method redefinition. 4. Traverse the callgraphs finding cycles that involve methods coming from multiple objects. For example, the callchain ***a.f -> a.g -> a.f*** will not be in the output, meanwhile the callchain ***a.f -> b.g -> a.f*** will be a part of it. ## Expected output Example input: ``` [] > a b > @ [self] > f self > @ [] > b [] > d a > @ [self] > g self > @ [] > c [] > e a > @ [self] > h self.f self > @ [] > t c.e > @ [self] > f self.h self > @ ``` Example output (prettified): ``` t: t.h (was last redefined in "c.e") -> t.f -> t.h (was last redefined in "c.e") ``` ## Possible errors The analyzer can fail with the following errors: 1. The analyzer encounters decoratee objects that are not defined. ``` [] > a b > @ ``` > <span style="color:red"> `Exception in thread "main" java.lang.Exception: Parent (or decoratee) object "b" of object "a" is specified, but not defined in the program!` </span>. 2. The analyzer encounters calls of non-existent methods. ``` [] > a [self] > f self.non_existent self > @ ``` > <span style="color:red"> `Exception in thread "main" java.lang.Exception: Method "non_existent" was called from the object "a", although it is not defined there!` </span>.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.