30 Years of Decompilation and the Unsolved Structuring Problem: Part 1

30 Years of Decompilation and the Unsolved Structuring Problem: Part 1
mahaloz.re

(Why? Just for fun, https://github.com/albertz/PyCParser, even more just-for-fun goal was this: https://github.com/albertz/PyCPython).

It literally would translate the C code in equivalent Python code, using ctypes heavily. It was mostly straight-forward, except for mapping goto (thus related to this control flow structuring problem).

Of course, there are some hacks to introduce goto in Python, which in many cases would operate on the Python bytecode, which actually has the JUMP_ABSOLUTE op, but there are also other ways (https://stackoverflow.com/questions/6959360/goto-in-python).

I could also have translated C directly to equivalent Python bytecode and not Python source code, but I really wanted to have Python source code.

My ugly solution worked basically like this: Whenever there was some goto in a function, it would translate it as follows:

First, we flatten any Python AST into a series of statements, with even more goto's added for while/for loops, if's, etc. (We can avoid doing this for all sub-ASTs where there are no no goto-labels. The goal is to have all goto-labels at the top-level, not inside a sub-AST.)

Only conditional goto's can stay. All Gotos and Goto-labels are marked somehow as special elements. So, we end up with sth like:

    x()
    y()
    
    z()
    
    w()
    if v(): 
    q()

- Add a big endless loop around it. After the final statement, a break would leave the loop.

- Before the loop, we add the statement `goto = None`.

- The goto-labels will split the code into multiple part, where we add some `if goto is None:` before each part (excluding the goto-labels).

- For the goto-labels itself, we add this code:

    if goto == : goto = None

    goto = ; continue