starlark: new CallStack API (and Frame deprecation) (#192)
Prior to this CL, the interpreter stack was implemented as
a "spaghetti stack", a linked tree of Frames. This meant
that EvalError (for example) could make a copy of the stack
just by retaining a *Frame reference at its moment of creation,
but this forced every Starlark call to allocate a new Frame.
Also, in non-error cases (e.g. application built-ins that retain the
call stack), the retained references (linked lists of frames) were
pointers to Frames that were actively mutated by ongoing execution.
This change separates the internal and external data types for Frames.
Internal frames (type Frame) are still, for now, linked trees, but
the Frame type is deprecated and will soon be made private.
It may still be accessed through an interface, DebugFrame, for the
very few clients that need debugger-like powers of reflection.
DebugFrames must not be retained.
The external type for frames (as used by EvalError) is CallFrame,
a simple pair struct of name and position fields, a value type.
It does not reveal the Callable, as that would pin functions in memory.
And it does not lazily compute Position, as that would depend on Frame.pc,
which changes as execution continues.
A slice of CallFrame is represented by CallStack,
and it has various convenience methods.
Follow-up changes in two weeks will implement remove Frame and other
deprecated declarations, and implement two optimizations:
Frame recycling, by inline slice preallocation in the Thread, and
Frame.locals []Value recycling, by inline slice preallocation in the Frame.
New API:
+ type CallFrame -- a simple Name/Pos pair
+ type CallStack -- a list of CallFrame
+ type DebugFrame -- interface for (soon to be hidden) Frame
+ func (*Thread).CallStack
+ func (*Thread).CallStackDepth
+ func (*Thread).CallFrame
+ EvalError.CallStack field (NB: direction reversed from old Stack method)
Deprecations (will be removed in 2 weeks):
- Frame -- use CallFrame, or DebugFrame if you really must
- func (*EvalError).Stack -- use CallStack
- func NewFrame -- clients have no business here
- func (*Frame).Parent -- use slice operations on CallStack
- EvalError.Frame field -- use CallStack
- Frame.WriteBacktrace -- use CallStack.Backtrace(); don't start with Frame
diff --git a/starlark/debug.go b/starlark/debug.go
index c08197c..acda0c8 100644
--- a/starlark/debug.go
+++ b/starlark/debug.go
@@ -1,5 +1,7 @@
package starlark
+import "go.starlark.net/syntax"
+
// This file defines an experimental API for the debugging tools.
// Some of these declarations expose details of internal packages.
// (The debugger makes liberal use of exported fields of unexported types.)
@@ -16,3 +18,25 @@
//
// THIS API IS EXPERIMENTAL AND MAY CHANGE WITHOUT NOTICE.
func (fr *Frame) Local(i int) Value { return fr.locals[i] }
+
+// DebugFrame is the debugger API for a frame of the interpreter's call stack.
+//
+// Most applications have no need for this API; use CallFrame instead.
+//
+// Clients must not retain a DebugFrame nor call any of its methods once
+// the current built-in call has returned or execution has resumed
+// after a breakpoint as this may have unpredictable effects, including
+// but not limited to retention of object that would otherwise be garbage.
+type DebugFrame interface {
+ Callable() Callable // returns the frame's function
+ Local(i int) Value // returns the value of the (Starlark) frame's ith local variable
+ Position() syntax.Position // returns the current position of execution in this frame
+}
+
+// DebugFrame returns the debugger interface for
+// the specified frame of the interpreter's call stack.
+// Frame numbering is as for Thread.CallFrame.
+//
+// This function is intended for use in debugging tools.
+// Most applications should have no need for it; use CallFrame instead.
+func (thread *Thread) DebugFrame(depth int) DebugFrame { return thread.frameAt(depth) }
diff --git a/starlark/eval.go b/starlark/eval.go
index 4899827..112c441 100644
--- a/starlark/eval.go
+++ b/starlark/eval.go
@@ -30,8 +30,8 @@
// Name is an optional name that describes the thread, for debugging.
Name string
- // frame is the current Starlark execution frame.
- frame *Frame
+ // stack is the stack of (internal) call frames.
+ stack []*Frame
// Print is the client-supplied implementation of the Starlark
// 'print' function. If nil, fmt.Fprintln(os.Stderr, msg) is
@@ -70,10 +70,39 @@
// Caller returns the frame of the caller of the current function.
// It should only be used in built-ins called from Starlark code.
-func (thread *Thread) Caller() *Frame { return thread.frame.parent }
+//
+// Deprecated: use CallFrame(1), or CallStack().At(1) if you also need the rest of the stack.
+func (thread *Thread) Caller() *Frame { return thread.frameAt(1) }
+
+// CallFrame returns a copy of the specified frame of the callstack.
+// It should only be used in built-ins called from Starlark code.
+// Depth 0 means the frame of the built-in itself, 1 is its caller, and so on.
+//
+// It is equivalent to CallStack().At(depth), but more efficient.
+func (thread *Thread) CallFrame(depth int) CallFrame {
+ return thread.frameAt(depth).CallFrame()
+}
// TopFrame returns the topmost stack frame.
-func (thread *Thread) TopFrame() *Frame { return thread.frame }
+//
+// Deprecated: use the Thread.CallStack method to return a copy of the current call stack.
+func (thread *Thread) TopFrame() *Frame { return thread.frameAt(0) }
+
+func (thread *Thread) frameAt(depth int) *Frame {
+ return thread.stack[len(thread.stack)-1-depth]
+}
+
+// CallStack returns a new slice containing the thread's stack of call frames.
+func (thread *Thread) CallStack() CallStack {
+ frames := make([]CallFrame, len(thread.stack))
+ for i, fr := range thread.stack {
+ frames[i] = fr.CallFrame()
+ }
+ return frames
+}
+
+// CallStackDepth returns the number of frames in the current call stack.
+func (thread *Thread) CallStackDepth() int { return len(thread.stack) }
// A StringDict is a mapping from names to values, and represents
// an environment such as the global variables of a module.
@@ -116,19 +145,19 @@
// A Frame records a call to a Starlark function (including module toplevel)
// or a built-in function or method.
+//
+// Deprecated: use CallFrame instead. If you really must, use DebugFrame.
type Frame struct {
- parent *Frame // caller's frame (or nil)
- callable Callable // current function (or toplevel) or built-in
- posn syntax.Position // source position of PC, set during error
- pc uint32 // program counter (Starlark frames only)
- locals []Value // local variables, for debugger
- spanStart int64 // start time of current profiler span
+ parent *Frame // deprecated: use CallStack instead
+ callable Callable // current function (or toplevel) or built-in
+ pc uint32 // program counter (Starlark frames only)
+ locals []Value // local variables (Starlark frames only), for debugger
+ spanStart int64 // start time of current profiler span
}
// NewFrame returns a new frame with the specified parent and callable.
//
-// It may be used to synthesize stack frames for error messages.
-// Few clients should need to use this function.
+// Deprecated: clients should have no need for this function.
func NewFrame(parent *Frame, callable Callable) *Frame {
return &Frame{parent: parent, callable: callable}
}
@@ -137,17 +166,8 @@
// slice, so that an EvalError can copy a stack efficiently and immutably.
// In hindsight using a slice would have led to a more convenient API.
-func (fr *Frame) errorf(posn syntax.Position, format string, args ...interface{}) *EvalError {
- fr.posn = posn
- msg := fmt.Sprintf(format, args...)
- return &EvalError{Msg: msg, Frame: fr}
-}
-
// Position returns the source position of the current point of execution in this frame.
func (fr *Frame) Position() syntax.Position {
- if fr.posn.IsValid() {
- return fr.posn // leaf frame only (the error)
- }
switch c := fr.callable.(type) {
case *Function:
// Starlark function
@@ -166,12 +186,63 @@
func (fr *Frame) Callable() Callable { return fr.callable }
// Parent returns the frame of the enclosing function call, if any.
+//
+// Deprecated: use Thread.CallStack instead of Frame.
func (fr *Frame) Parent() *Frame { return fr.parent }
-// An EvalError is a Starlark evaluation error and its associated call stack.
+// A CallStack is a stack of call frames, outermost first.
+type CallStack []CallFrame
+
+// At returns a copy of the frame at depth i.
+// At(0) returns the topmost frame.
+func (stack CallStack) At(i int) CallFrame { return stack[len(stack)-1-i] }
+
+// Pop removes and returns the topmost frame.
+func (stack *CallStack) Pop() CallFrame {
+ last := len(*stack) - 1
+ top := (*stack)[last]
+ *stack = (*stack)[:last]
+ return top
+}
+
+// String returns a user-friendly description of the stack.
+func (stack CallStack) String() string {
+ out := new(strings.Builder)
+ fmt.Fprintf(out, "Traceback (most recent call last):\n")
+ for _, fr := range stack {
+ fmt.Fprintf(out, " %s: in %s\n", fr.Pos, fr.Name)
+ }
+ return out.String()
+}
+
+// An EvalError is a Starlark evaluation error and
+// a copy of the thread's stack at the moment of the error.
type EvalError struct {
- Msg string
- Frame *Frame
+ Msg string
+ CallStack CallStack
+ Frame *Frame // Deprecated: use CallStack instead
+}
+
+// A CallFrame represents the function name and current
+// position of execution of an enclosing call frame.
+type CallFrame struct {
+ Name string
+ Pos syntax.Position
+}
+
+func (fr *Frame) CallFrame() CallFrame {
+ return CallFrame{
+ Name: fr.Callable().Name(),
+ Pos: fr.Position(),
+ }
+}
+
+func (thread *Thread) evalError(err error) *EvalError {
+ return &EvalError{
+ Msg: err.Error(),
+ CallStack: thread.CallStack(),
+ Frame: thread.frameAt(0), // legacy
+ }
}
func (e *EvalError) Error() string { return e.Msg }
@@ -179,26 +250,28 @@
// Backtrace returns a user-friendly error message describing the stack
// of calls that led to this error.
func (e *EvalError) Backtrace() string {
- buf := new(strings.Builder)
- e.Frame.WriteBacktrace(buf)
- fmt.Fprintf(buf, "Error: %s", e.Msg)
- return buf.String()
+ return fmt.Sprintf("%sError: %s", e.CallStack, e.Msg)
}
// WriteBacktrace writes a user-friendly description of the stack to buf.
+//
+// Deprecated: use CallStack instead.
func (fr *Frame) WriteBacktrace(out *strings.Builder) {
- fmt.Fprintf(out, "Traceback (most recent call last):\n")
- var print func(fr *Frame)
- print = func(fr *Frame) {
+ var stack CallStack
+ var visit func(fr *Frame)
+ visit = func(fr *Frame) {
if fr != nil {
- print(fr.parent)
- fmt.Fprintf(out, " %s: in %s\n", fr.Position(), fr.Callable().Name())
+ visit(fr.parent)
+ stack = append(stack, fr.CallFrame())
}
}
- print(fr)
+ visit(fr)
+ out.WriteString(stack.String())
}
// Stack returns the stack of frames, innermost first.
+//
+// Deprecated: use CallStack instead.
func (e *EvalError) Stack() []*Frame {
var stack []*Frame
for fr := e.Frame; fr != nil; fr = fr.parent {
@@ -991,12 +1064,15 @@
return nil, fmt.Errorf("invalid call of non-function (%s)", fn.Type())
}
- fr := NewFrame(thread.frame, c)
- thread.frame = fr
+ var parent *Frame
+ if len(thread.stack) > 0 {
+ parent = thread.frameAt(0)
+ }
+ fr := NewFrame(parent, c)
+ thread.stack = append(thread.stack, fr) // push
thread.beginProfSpan()
result, err := c.CallInternal(thread, args, kwargs)
thread.endProfSpan()
- thread.frame = thread.frame.parent
// Sanity check: nil is not a valid Starlark value.
if result == nil && err == nil {
@@ -1006,10 +1082,13 @@
// Always return an EvalError with an accurate frame.
if err != nil {
if _, ok := err.(*EvalError); !ok {
- err = fr.errorf(fr.Position(), "%s", err.Error())
+ err = thread.evalError(err)
}
}
+ thread.stack[len(thread.stack)-1] = nil // aid GC
+ thread.stack = thread.stack[:len(thread.stack)-1] // pop
+
return result, err
}
diff --git a/starlark/eval_test.go b/starlark/eval_test.go
index 075e79b..69cbed3 100644
--- a/starlark/eval_test.go
+++ b/starlark/eval_test.go
@@ -135,8 +135,8 @@
switch err := err.(type) {
case *starlark.EvalError:
found := false
- for _, fr := range err.Stack() {
- posn := fr.Position()
+ for i := range err.CallStack {
+ posn := err.CallStack.At(i).Pos
if posn.Filename() == filename {
chunk.GotError(int(posn.Line), err.Error())
found = true
@@ -182,7 +182,7 @@
}
// TODO(adonovan): test load() using this execution path.
- filename := filepath.Join(filepath.Dir(thread.TopFrame().Position().Filename()), module)
+ filename := filepath.Join(filepath.Dir(thread.CallFrame(0).Pos.Filename()), module)
return starlark.ExecFile(thread, filename, nil, nil)
}
@@ -424,9 +424,8 @@
`
buf := new(bytes.Buffer)
print := func(thread *starlark.Thread, msg string) {
- caller := thread.Caller()
- fmt.Fprintf(buf, "%s: %s: %s\n",
- caller.Position(), caller.Callable().Name(), msg)
+ caller := thread.CallFrame(1)
+ fmt.Fprintf(buf, "%s: %s: %s\n", caller.Pos, caller.Name, msg)
}
thread := &starlark.Thread{Print: print}
if _, err := starlark.ExecFile(thread, "foo.star", src, nil); err != nil {
@@ -626,7 +625,8 @@
// values of calls to Starlark functions.
trace := func(thread *starlark.Thread) string {
buf := new(bytes.Buffer)
- for fr := thread.TopFrame(); fr != nil; fr = fr.Parent() {
+ for i := 0; i < thread.CallStackDepth(); i++ {
+ fr := thread.DebugFrame(i)
fmt.Fprintf(buf, "%s(", fr.Callable().Name())
if fn, ok := fr.Callable().(*starlark.Function); ok {
for i := 0; i < fn.NumParams(); i++ {
diff --git a/starlark/interp.go b/starlark/interp.go
index 4779d69..81f622d 100644
--- a/starlark/interp.go
+++ b/starlark/interp.go
@@ -23,7 +23,7 @@
func (fn *Function) CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Value, error) {
if !resolve.AllowRecursion {
// detect recursion
- for fr := thread.frame.parent; fr != nil; fr = fr.parent {
+ for _, fr := range thread.stack[:len(thread.stack)-1] {
// We look for the same function code,
// not function value, otherwise the user could
// defeat the check by writing the Y combinator.
@@ -34,7 +34,7 @@
}
f := fn.funcode
- fr := thread.frame
+ fr := thread.frameAt(0)
nlocals := len(f.Locals)
stack := make([]Value, nlocals+f.MaxStack)
locals := stack[:nlocals:nlocals] // local variables, starting with parameters
@@ -42,7 +42,7 @@
err := setArgs(locals, fn, args, kwargs)
if err != nil {
- return nil, fr.errorf(fr.Position(), "%v", err)
+ return nil, thread.evalError(err)
}
fr.locals = locals // for debugger
diff --git a/starlark/profile.go b/starlark/profile.go
index 22dd555..38da2b2 100644
--- a/starlark/profile.go
+++ b/starlark/profile.go
@@ -130,7 +130,7 @@
return // profiling not enabled
}
- thread.frame.spanStart = nanotime()
+ thread.frameAt(0).spanStart = nanotime()
}
// TODO(adonovan): experiment with smaller values,
@@ -143,7 +143,7 @@
}
// Add the span to the thread's accumulator.
- thread.proftime += time.Duration(nanotime() - thread.frame.spanStart)
+ thread.proftime += time.Duration(nanotime() - thread.frameAt(0).spanStart)
if thread.proftime < quantum {
return
}
@@ -159,7 +159,8 @@
time: n * quantum,
}
ev.stack = ev.stackSpace[:0]
- for fr := thread.frame; fr != nil; fr = fr.parent {
+ for i := range thread.stack {
+ fr := thread.frameAt(i)
ev.stack = append(ev.stack, profFrame{
pos: fr.Position(),
fn: fr.Callable(),
diff --git a/starlarktest/starlarktest.go b/starlarktest/starlarktest.go
index c93eaf9..5868ef0 100644
--- a/starlarktest/starlarktest.go
+++ b/starlarktest/starlarktest.go
@@ -105,8 +105,9 @@
return nil, fmt.Errorf("error: got %d arguments, want 1", len(args))
}
buf := new(strings.Builder)
- thread.Caller().WriteBacktrace(buf)
- buf.WriteString("Error: ")
+ stk := thread.CallStack()
+ stk.Pop()
+ fmt.Fprintf(buf, "%sError: ", stk)
if s, ok := starlark.AsString(args[0]); ok {
buf.WriteString(s)
} else {
