<p>Errors are a lot easier to troubleshoot if the language reports precise source locations. In case of runtime errors, the <em>stack trace</em> is probably important, showing each function in the call stack and why they were called.</p>
<p>For example, in Python:</p>
<pre class="lang-python prettyprint-override"><code>def divide_by(divisor):
    print('Starting division')
    print(10 / divisor)

def do():
    divide_by(0)

do()
</code></pre>
<pre><code>Traceback (most recent call last):
  File &quot;main.py&quot;, line 8, in &lt;module&gt;
    do()
  File &quot;main.py&quot;, line 6, in do
    divide_by(0)
  File &quot;main.py&quot;, line 3, in divide_by
    print(10 / divisor)

ZeroDivisionError: division by zero
</code></pre>
<p>Note that it includes both the function names (<code>divide_by</code>, <code>do</code>, and <code>&lt;module&gt;</code>), and the source code line that called the next function in the stack (<code>divide_by(10)</code>, <code>do()</code>).</p>
<p><strong>How can I generate such stack traces?</strong></p>
<hr />
<p>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:</p>
<pre class="lang-python prettyprint-override"><code>def divide_by(divisor, _stacktrace):
    print('Starting division', _stacktrace=_stacktrace+[(2, &quot;print('Starting division')&quot;])
    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()')])
</code></pre>
<p>Then all the information required to print a formatted stack trace is in the <code>_stacktrace</code> argument, without even analyzing stack frames. This works, but is obviously slow, even using constants for the (line, source) tuples.</p>
<p>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:</p>
<pre class="lang-python prettyprint-override"><code>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 = '&lt;module&gt;'
_line = 8
do()
</code></pre>
<p>Then, on error, I walk through the stack and locate the <code>_line</code> and <code>_function_name</code> 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.</p>
<p><strong>Is there a more efficient way to generate stack traces?</strong> I'm also interested in solutions like <code>_stacktrace</code> that don't require analyzing stack frames, because some compilation targets and execution models don't expose this information.</p>

<untagged>
How to efficiently generate stack traces
CC BY-SA 4.0
2023-09-01T19:17:23.647Z
in your example the hidden arguments are added automatically by the interpreter/compiler, not manually by the developer, right?
coredump
CC BY-SA 4.0
2023-09-01T20:27:07.913Z
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?
kaya3
CC BY-SA 4.0
2023-09-01T20:27:09.850Z
@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.
BoppreH
CC BY-SA 4.0
2023-09-01T20:31:05.130Z
@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.
BoppreH
CC BY-SA 4.0
2023-09-01T20:32:37.863Z
If it's about a compiler to an intermediate language, then I'm not sure how stack traces come into it. Whatever compiles or interprets the intermediate language will have to generate stack traces.
kaya3
CC BY-SA 4.0
2023-09-01T20:43:32.117Z
@kaya3 You're right that the intermediate language will have its own stack trace. But nothing stops the first compiler from generating code that handles its own errors and reports "logical" stack traces, disregarding the intermediate language. That's what the two alternatives are doing in the question.
BoppreH
CC BY-SA 4.0
2023-09-02T12:41:48.643Z
Just as a question, do you need to handle cases like tail calls, promises/futures, or lazy evaluation? They can complicate how you present the call graph enormously.
Pseudonym
CC BY-SA 4.0
2023-09-02T14:01:37.480Z
@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.
BoppreH
<blockquote>
<p>Is there a more efficient way to generate stack traces?</p>
</blockquote>
<p>Yes, there are other approaches.</p>
<p>Are you asking what compiled languages do to facilitate the generation of stack traces?</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.)</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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, <a href="https://learn.microsoft.com/en-us/cpp/cpp/structured-exception-handling-c-cpp?view=msvc-170" rel="nofollow noreferrer">Structured Exception Handling</a>, for example, though it is rather involved.</p>

CC BY-SA 4.0
2023-09-01T21:46:54.153Z
2023-09-04T15:04:18.480Z
2023-09-04T15:04:18.480Z
Erik Eidt
CC BY-SA 4.0
2023-09-02T11:23:39.267Z
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](https://pkg.go.dev/runtime#Callers) [lifting](https://pkg.go.dev/runtime#CallersFrames). And if anybody else has alternative solutions, even if they only apply to niche scenarios, those are also welcome.
BoppreH
# How to efficiently generate stack traces
Posted by: username_0 on 2023-09-01
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 
    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 ), 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 = ''
_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.
**Tags:** untagged
> **Comments:**
> **username_1**: in your example the hidden arguments are added automatically by the interpreter/compiler, not manually by the developer, right?  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_2**: If it's about a compiler to an intermediate language, then I'm not sure how stack traces come into it. Whatever compiles or interprets the intermediate language will have to generate stack traces.  
> **username_0**: @kaya3 You're right that the intermediate language will have its own stack trace. But nothing stops the first compiler from generating code that handles its own errors and reports "logical" stack traces, disregarding the intermediate language. That's what the two alternatives are doing in the question.  
> **username_3**: Just as a question, do you need to handle cases like tail calls, promises/futures, or lazy evaluation? They can complicate how you present the call graph enormously.  
> **username_0**: @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.  
---
## 1 answers
### Answer by username_4 on 2023-09-01. Score: 6 | Accepted answer
> 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](https://learn.microsoft.com/en-us/cpp/cpp/structured-exception-handling-c-cpp?view=msvc-170), for example, though it is rather involved.
> **Comments:**
> **username_0** (2023-09-02): 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](https://pkg.go.dev/runtime#Callers) [lifting](https://pkg.go.dev/runtime#CallersFrames). And if anybody else has alternative solutions, even if they only apply to niche scenarios, those are also welcome.  
---
