9
$\begingroup$

Errors are a lot easier to troubleshoot if the language reports precise source locations. In case of runtime errors, the stack trace is probably important, showing each function in the call stack and why they were called.

For example, in Python:

def divide_by(divisor):
    print('Starting division')
    print(10 / divisor)

def do():
    divide_by(0)

do()
Traceback (most recent call last):
  File "main.py", line 8, in <module>
    do()
  File "main.py", line 6, in do
    divide_by(0)
  File "main.py", line 3, in divide_by
    print(10 / divisor)

ZeroDivisionError: division by zero

Note that it includes both the function names (divide_by, do, and <module>), and the source code line that called the next function in the stack (divide_by(10), do()).

How can I generate such stack traces?


My first naive attempt was to keep the stack trace as a hidden argument for every function. So the compiler/interpreter would automatically insert code like this:

def divide_by(divisor, _stacktrace):
    print('Starting division', _stacktrace=_stacktrace+[(2, "print('Starting division')"])
    print(10 / divisor, _stacktrace=_stacktrace+[(3, 'print(10 / divisor)'])

def do(_stacktrace):
    divide_by(0, _stacktrace=_stacktrace+[(6, 'divide_by(0)')])

do(_stacktrace=[(8, 'do()')])

Then all the information required to print a formatted stack trace is in the _stacktrace argument, without even analyzing stack frames. This works, but is obviously slow, even using constants for the (line, source) tuples.

Another way that occurred to me is to keep track of what source line is being executed at each function, automatically adding variables like so:

def divide_by(divisor):
    _function_name = 'divide_by'
    _line = 2
    print('Starting division')
    _line = 3
    print(10 / divisor)

def do():
    _function_name = 'do'
    _line = 6
    divide_by(0)

_function_name = '<module>'
_line = 8
do()

Then, on error, I walk through the stack and locate the _line and _function_name variables of each function to generate the stack trace. I think this would work, but it'd still add a new operation for every line of code executed.

Is there a more efficient way to generate stack traces? I'm also interested in solutions like _stacktrace that don't require analyzing stack frames, because some compilation targets and execution models don't expose this information.

$\endgroup$
8
  • $\begingroup$ in your example the hidden arguments are added automatically by the interpreter/compiler, not manually by the developer, right? $\endgroup$
    – coredump
    Sep 1, 2023 at 19:17
  • $\begingroup$ You give Python as an example but then mention compilation targets. Is your question about implementing this in an interpreter (if so, tree-walking or bytecode?) or a compiler? $\endgroup$
    – kaya3
    Sep 1, 2023 at 20:27
  • $\begingroup$ @coredump Yes, sorry if it was unclear. The source code, as written by the programmer, is the first snippet. Everything else is the "equivalent translation" for what the compiler/interpreter actually does. $\endgroup$
    – BoppreH
    Sep 1, 2023 at 20:27
  • $\begingroup$ @kaya3 Personally, I'm interested in compilation to intermediary languages, but I'd like this question to be broader, so solutions for other scenarios are welcome. $\endgroup$
    – BoppreH
    Sep 1, 2023 at 20:31
  • 1
    $\begingroup$ @Pseudonym I'm more interested in gathering answers useful to the community than solving my specific problem. If you post an answer on these cases, you'll have my vote. $\endgroup$
    – BoppreH
    Sep 2, 2023 at 14:01

1 Answer 1

6
$\begingroup$

Is there a more efficient way to generate stack traces?

Yes, there are other approaches.

Are you asking what compiled languages do to facilitate the generation of stack traces?

The idea is to make normal execution efficient even at the expense of actual stack trace generation.  One solution is static data tables that correlate machine code program counter values with lines in source files.  These tables are not consulted during normal execution, and instead only when a trace is required.

Static tables can also be used to enable stack unwind without requiring frame pointers, so you can get from callee to caller, and the generated machine code can use modern, efficient function calling; however making the generated code consistently use frame pointers can simplify things here.

There's a lot of complexity here depending on what runtime errors you want to capture, so a good approach to start is to limit use of features that complicate things.

A possible scenarios are: a thread suspended at some random point (i.e. between any two machine code instructions), and we want a stack trace.  This means handling asynchronous exceptions, which greatly complicates stack unwind, so you may consider doing without that feature for starters.

Foreign function calling (i.e. calling C library code) means you can have code generated from different sources on mixed on the stack (your code, along with C code together on the stack).  This complicates tracing, especially if you also handle asynchronous tracing.  A possible solution here is to use something like your stacking _line/_file variables approach whenever your code leaves to call C code (or C code calls your code) slowing down foreign function calling, though making it so you can identify and contain the C code (without necessarily using their tables or stack unwind).  (Stack traces could be complete for your code but simply identify one called C function.)

At a next level might be handling stack overflow.  Since that typically happens in function prologue rather than normal function body execution that complicates things as well, but at least this is a synchronous scenario.

To be able to capture synchronous runtime errors that happen during execution of function bodies (e.g. outside of prologue), then you need to capture the information that the stack unwind needs to identify the caller's environment, which is first and foremost to locate the return address of the caller within the current function (the callee).  Once you have the return address, you can use the program counter to source lines table to identify the source code line.  Then identify the caller's caller, and repeat.  If your generated code sticks to some regular rules, then table entry to locate the return address can be fairly simple.

To make this work, whoever generates the actual machine code needs to also generate the static data tables, so if there is an intermediary, then the source line information needs to be propagated though that.  You might want some kind of association of intermediate code with line numbers, and then the final code generator can make the tables for the generated machine code.

Stack tracing / stack unwind is also involved in exception handling.  So, as an alternative you can support the C-style stack unwind mechanisms, when they are available on platforms of interest.  Windows has such, Structured Exception Handling, for example, though it is rather involved.

$\endgroup$
1
  • $\begingroup$ Great answer, very throughout and helped me on a practical level. Like you said, it takes a bit of trickery to map inlined calls and the like, but luckily for me the host language did the heavy lifting. And if anybody else has alternative solutions, even if they only apply to niche scenarios, those are also welcome. $\endgroup$
    – BoppreH
    Sep 2, 2023 at 11:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .