Handle StackFrameFormat in DAP

DAP specifies a StackFrameFormat object that can be used to change how
the "name" part of a stack frame is constructed.  While this output
can already be done in a nicer way (and also letting the client choose
the formatting), nevertheless it is in the spec, so I figured I'd
implement it.

While implementing this, I discovered that the current code does not
correctly preserve frame IDs across requests.  I rewrote frame
iteration to preserve this, and it turned out to be simpler to combine
these patches.

Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=30475

6 files changed, 453 insertions, 47 deletions

diff --git a/gdb/python/lib/gdb/dap/bt.py b/gdb/python/lib/gdb/dap/bt.py
index 982d501edf5..c63ca6d13b5 100644
--- a/gdb/python/lib/gdb/dap/bt.py
+++ b/gdb/python/lib/gdb/dap/bt.py
@@ -16,37 +16,68 @@
 import gdb
 import os
 
-from gdb.frames import frame_iterator
-from .frames import frame_id
+# This is deprecated in 3.9, but required in older versions.
+from typing import Optional
+
+from .frames import dap_frame_generator
 from .modules import module_id
+from .scopes import symbol_value
 from .server import request, capability
 from .sources import make_source
 from .startup import send_gdb_with_response, in_gdb_thread
 from .state import set_thread
+from .typecheck import type_check
 from .varref import apply_format
 
 
+# Helper function to compute parameter information for a stack frame.
+@in_gdb_thread
+def _compute_parameters(frame, stack_format):
+    arg_iter = frame.frame_args()
+    if arg_iter is None:
+        return ""
+    result = []
+    for arg in arg_iter:
+        desc = []
+        name, val = symbol_value(arg, frame)
+        # We don't try to use any particular language's syntax for the
+        # output here.
+        if stack_format["parameterTypes"]:
+            desc.append("[" + str(val.type) + "]")
+        if stack_format["parameterNames"]:
+            desc.append(name)
+            # If both the name and the value are requested, insert an
+            # '=' for clarity.
+            if stack_format["parameterValues"]:
+                desc.append("=")
+        if stack_format["parameterValues"]:
+            desc.append(val.format_string(summary=True))
+        result.append(" ".join(desc))
+    return ", ".join(result)
+
+
 # Helper function to compute a stack trace.
 @in_gdb_thread
-def _backtrace(thread_id, levels, startFrame, value_format):
-    with apply_format(value_format):
+def _backtrace(thread_id, levels, startFrame, stack_format):
+    with apply_format(stack_format):
         set_thread(thread_id)
         frames = []
-        if levels == 0:
-            # Zero means all remaining frames.
-            high = -1
-        else:
-            # frame_iterator uses an inclusive range, so subtract one.
-            high = startFrame + levels - 1
-        try:
-            frame_iter = frame_iterator(gdb.newest_frame(), startFrame, high)
-        except gdb.error:
-            frame_iter = ()
-        for current_frame in frame_iter:
+        frame_iter = dap_frame_generator(startFrame, levels, stack_format["includeAll"])
+        for frame_id, current_frame in frame_iter:
             pc = current_frame.address()
+            # The stack frame format affects the name, so we build it up
+            # piecemeal and assign it at the end.
+            name = current_frame.function()
+            # The meaning of StackFrameFormat.parameters was clarified
+            # in https://github.com/microsoft/debug-adapter-protocol/issues/411.
+            if stack_format["parameters"] and (
+                stack_format["parameterTypes"]
+                or stack_format["parameterNames"]
+                or stack_format["parameterValues"]
+            ):
+                name += "(" + _compute_parameters(current_frame, stack_format) + ")"
             newframe = {
-                "id": frame_id(current_frame),
-                "name": current_frame.function(),
+                "id": frame_id,
                 # This must always be supplied, but we will set it
                 # correctly later if that is possible.
                 "line": 0,
@@ -54,15 +85,20 @@ def _backtrace(thread_id, levels, startFrame, value_format):
                 "column": 0,
                 "instructionPointerReference": hex(pc),
             }
-            objfile = gdb.current_progspace().objfile_for_address(pc)
-            if objfile is not None:
-                newframe["moduleId"] = module_id(objfile)
             line = current_frame.line()
             if line is not None:
                 newframe["line"] = line
+                if stack_format["line"]:
+                    name += ", line " + str(line)
+            objfile = gdb.current_progspace().objfile_for_address(pc)
+            if objfile is not None:
+                newframe["moduleId"] = module_id(objfile)
+                if stack_format["module"]:
+                    name += ", module " + objfile.username
             filename = current_frame.filename()
             if filename is not None:
                 newframe["source"] = make_source(filename, os.path.basename(filename))
+            newframe["name"] = name
             frames.append(newframe)
         # Note that we do not calculate totalFrames here.  Its absence
         # tells the client that it may simply ask for frames until a
@@ -72,11 +108,45 @@ def _backtrace(thread_id, levels, startFrame, value_format):
         }
 
 
+# A helper function that checks the types of the elements of a
+# StackFrameFormat, and converts this to a dict where all the members
+# are set.  This simplifies the implementation code a bit.
+@type_check
+def check_stack_frame(
+    *,
+    # Note that StackFrameFormat extends ValueFormat, which is why
+    # "hex" appears here.
+    hex: Optional[bool] = False,
+    parameters: Optional[bool] = False,
+    parameterTypes: Optional[bool] = False,
+    parameterNames: Optional[bool] = False,
+    parameterValues: Optional[bool] = False,
+    line: Optional[bool] = False,
+    module: Optional[bool] = False,
+    includeAll: Optional[bool] = False,
+    **rest
+):
+    return {
+        "hex": hex,
+        "parameters": parameters,
+        "parameterTypes": parameterTypes,
+        "parameterNames": parameterNames,
+        "parameterValues": parameterValues,
+        "line": line,
+        "module": module,
+        "includeAll": includeAll,
+    }
+
+
 @request("stackTrace")
 @capability("supportsDelayedStackTraceLoading")
 def stacktrace(
     *, levels: int = 0, startFrame: int = 0, threadId: int, format=None, **extra
 ):
+    # It's simpler if the format is always set.
+    if format is None:
+        format = {}
+    format = check_stack_frame(**format)
     return send_gdb_with_response(
         lambda: _backtrace(threadId, levels, startFrame, format)
     )
diff --git a/gdb/python/lib/gdb/dap/frames.py b/gdb/python/lib/gdb/dap/frames.py
index 1d2d1371354..669e73f34c5 100644
--- a/gdb/python/lib/gdb/dap/frames.py
+++ b/gdb/python/lib/gdb/dap/frames.py
@@ -14,6 +14,9 @@
 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
 import gdb
+import itertools
+
+from gdb.frames import frame_iterator
 
 from .startup import in_gdb_thread
 
@@ -24,11 +27,17 @@ from .startup import in_gdb_thread
 _all_frames = []
 
 
+# Map from a global thread ID to a memoizing frame iterator.
+_iter_map = {}
+
+
 # Clear all the frame IDs.
 @in_gdb_thread
 def _clear_frame_ids(evt):
     global _all_frames
     _all_frames = []
+    global _iter_map
+    _iter_map = {}
 
 
 # Clear the frame ID map whenever the inferior runs.
@@ -36,18 +45,6 @@ gdb.events.cont.connect(_clear_frame_ids)
 
 
 @in_gdb_thread
-def frame_id(frame):
-    """Return the frame identifier for FRAME."""
-    global _all_frames
-    for i in range(0, len(_all_frames)):
-        if _all_frames[i] == frame:
-            return i
-    result = len(_all_frames)
-    _all_frames.append(frame)
-    return result
-
-
-@in_gdb_thread
 def frame_for_id(id):
     """Given a frame identifier ID, return the corresponding frame."""
     global _all_frames
@@ -59,3 +56,95 @@ def select_frame(id):
     """Given a frame identifier ID, select the corresponding frame."""
     frame = frame_for_id(id)
     frame.inferior_frame().select()
+
+
+# A simple memoizing iterator.  Note that this is not very robust.
+# For example, you can't start two copies of the iterator and then
+# alternate fetching items from each.  Instead, it implements just
+# what is needed for the current callers.
+class _MemoizingIterator:
+    def __init__(self, iterator):
+        self.iterator = iterator
+        self.seen = []
+
+    def __iter__(self):
+        # First the memoized items.
+        for item in self.seen:
+            yield item
+        # Now memoize new items.
+        for item in self.iterator:
+            self.seen.append(item)
+            yield item
+
+
+# A generator that fetches frames and pairs them with a frame ID.  It
+# yields tuples of the form (ID, ELIDED, FRAME), where ID is the
+# generated ID, ELIDED is a boolean indicating if the frame should be
+# elided, and FRAME is the frame itself.  This approach lets us
+# memoize the result and assign consistent IDs, independent of how
+# "includeAll" is set in the request.
+@in_gdb_thread
+def _frame_id_generator():
+    try:
+        base_iterator = frame_iterator(gdb.newest_frame(), 0, -1)
+    except gdb.error:
+        base_iterator = ()
+
+    # Helper function to assign an ID to a frame.
+    def get_id(frame):
+        global _all_frames
+        num = len(_all_frames)
+        _all_frames.append(frame)
+        return num
+
+    def yield_frames(iterator, for_elided):
+        for frame in iterator:
+            # Unfortunately the frame filter docs don't describe
+            # whether the elided frames conceptually come before or
+            # after the eliding frame.  Here we choose after.
+            yield (get_id(frame), for_elided, frame)
+
+            elided = frame.elided()
+            if elided is not None:
+                yield from yield_frames(frame.elided(), True)
+
+    yield from yield_frames(base_iterator, False)
+
+
+# Return the memoizing frame iterator for the selected thread.
+@in_gdb_thread
+def _get_frame_iterator():
+    thread_id = gdb.selected_thread().global_num
+    global _iter_map
+    if thread_id not in _iter_map:
+        _iter_map[thread_id] = _MemoizingIterator(_frame_id_generator())
+    return _iter_map[thread_id]
+
+
+# A helper function that creates an iterable that returns (ID, FRAME)
+# pairs.  It uses the memoizing frame iterator, but also handles the
+# "includeAll" member of StackFrameFormat.
+@in_gdb_thread
+def dap_frame_generator(frame_low, levels, include_all):
+    """A generator that yields identifiers and frames.
+
+    Each element is a pair of the form (ID, FRAME).
+    ID is the internally-assigned frame ID.
+    FRAME is a FrameDecorator of some kind.
+
+    Arguments are as to the stackTrace request."""
+
+    base_iterator = _get_frame_iterator()
+
+    if not include_all:
+        base_iterator = itertools.filterfalse(lambda item: item[1], base_iterator)
+
+    if levels == 0:
+        # Zero means all remaining frames.
+        frame_high = None
+    else:
+        frame_high = frame_low + levels
+    base_iterator = itertools.islice(base_iterator, frame_low, frame_high)
+
+    for ident, _, frame in base_iterator:
+        yield (ident, frame)
diff --git a/gdb/python/lib/gdb/dap/scopes.py b/gdb/python/lib/gdb/dap/scopes.py
index 13c35817fb6..e526dfb518a 100644
--- a/gdb/python/lib/gdb/dap/scopes.py
+++ b/gdb/python/lib/gdb/dap/scopes.py
@@ -36,6 +36,29 @@ def clear_scopes(event):
 gdb.events.cont.connect(clear_scopes)
 
 
+# A helper function to compute the value of a symbol.  SYM is either a
+# gdb.Symbol, or an object implementing the SymValueWrapper interface.
+# FRAME is a frame wrapper, as produced by a frame filter.  Returns a
+# tuple of the form (NAME, VALUE), where NAME is the symbol's name and
+# VALUE is a gdb.Value.
+@in_gdb_thread
+def symbol_value(sym, frame):
+    inf_frame = frame.inferior_frame()
+    # Make sure to select the frame first.  Ideally this would not
+    # be needed, but this is a way to set the current language
+    # properly so that language-dependent APIs will work.
+    inf_frame.select()
+    name = str(sym.symbol())
+    val = sym.value()
+    if val is None:
+        # No synthetic value, so must read the symbol value
+        # ourselves.
+        val = sym.symbol().value(inf_frame)
+    elif not isinstance(val, gdb.Value):
+        val = gdb.Value(val)
+    return (name, val)
+
+
 class _ScopeReference(BaseReference):
     def __init__(self, name, hint, frame, var_list):
         super().__init__(name)
@@ -67,21 +90,7 @@ class _ScopeReference(BaseReference):
 
     @in_gdb_thread
     def fetch_one_child(self, idx):
-        # Make sure to select the frame first.  Ideally this would not
-        # be needed, but this is a way to set the current language
-        # properly so that language-dependent APIs will work.
-        self.inf_frame.select()
-        # Here SYM will conform to the SymValueWrapper interface.
-        sym = self.var_list[idx]
-        name = str(sym.symbol())
-        val = sym.value()
-        if val is None:
-            # No synthetic value, so must read the symbol value
-            # ourselves.
-            val = sym.symbol().value(self.inf_frame)
-        elif not isinstance(val, gdb.Value):
-            val = gdb.Value(val)
-        return (name, val)
+        return symbol_value(self.var_list[idx], self.frame)
 
 
 class _RegisterReference(_ScopeReference):
diff --git a/gdb/testsuite/gdb.dap/stack-format.c b/gdb/testsuite/gdb.dap/stack-format.c
new file mode 100644
index 00000000000..80759e541a7
--- /dev/null
+++ b/gdb/testsuite/gdb.dap/stack-format.c
@@ -0,0 +1,41 @@
+/* Copyright 2023 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+int function (int x, char y)
+{
+  return y - x - 1;			/* BREAK */
+}
+
+int z_1 (int x, char y)
+{
+  return function (x, y);
+}
+
+int z_2 (int x, char y)
+{
+  return z_1 (x, y);
+}
+
+int z_3 (int x, char y)
+{
+  return z_2 (x, y);
+}
+
+int main ()
+{
+  return z_3 (64, 'A');
+}
diff --git a/gdb/testsuite/gdb.dap/stack-format.exp b/gdb/testsuite/gdb.dap/stack-format.exp
new file mode 100644
index 00000000000..caa1266797b
--- /dev/null
+++ b/gdb/testsuite/gdb.dap/stack-format.exp
@@ -0,0 +1,133 @@
+# Copyright 2023 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test DAP stack format options.
+
+require allow_dap_tests
+
+load_lib dap-support.exp
+
+standard_testfile
+
+if {[build_executable ${testfile}.exp $testfile] == -1} {
+    return
+}
+
+set remote_python_file [gdb_remote_download host \
+			    ${srcdir}/${subdir}/${testfile}.py]
+
+save_vars GDBFLAGS {
+    append GDBFLAGS " -iex \"source $remote_python_file\""
+
+    if {[dap_launch $testfile] == ""} {
+	return
+    }
+}
+
+set line [gdb_get_line_number "BREAK"]
+set obj [dap_check_request_and_response "set breakpoint by line number" \
+	     setBreakpoints \
+	     [format {o source [o path [%s]] breakpoints [a [o line [i %d]]]} \
+		  [list s $srcfile] $line]]
+set line_bpno [dap_get_breakpoint_number $obj]
+
+dap_check_request_and_response "start inferior" configurationDone
+
+dap_wait_for_event_and_check "stopped at line breakpoint" stopped \
+    "body reason" breakpoint \
+    "body hitBreakpointIds" $line_bpno
+
+
+# Each request should return the same frame ID.  Store it here,
+# indexed by requested frame.
+array set frame_id {}
+
+# Request a single frame of the stack trace and check it.  NAME is the
+# name of the test.  FRAME is the number of the frame to request.
+# FORMAT is contents of the StackFrameFormat object to use.  It is in
+# TON form.  EXPECTED is the expected 'name' value of the resulting
+# frame.  If REGEXP is set, then EXPECTED is a regular expression;
+# otherwise it is treated as the exact string result.
+proc check_stack_frame {name frame format expected {regexp 0}} {
+    with_test_prefix $name {
+	set args [format {o startFrame [i %d] levels [i 1] threadId [i 1]} \
+		      $frame]
+	if {$format != ""} {
+	    append args " format \[o $format\]"
+	}
+
+	set bt [lindex [dap_check_request_and_response "backtrace" \
+			    stackTrace $args] \
+		    0]
+	set frame_info [lindex [dict get $bt body stackFrames] 0]
+
+	# Each request at this level should return the same frame ID.
+	set this_id [dict get $frame_info id]
+	global frame_id
+	if {[info exists frame_id($frame)]} {
+	    gdb_assert {$frame_id($frame) == $this_id} "unchanging frame id"
+	} else {
+	    set frame_id($frame) $this_id
+	}
+
+	if {$regexp} {
+	    gdb_assert {[regexp $expected [dict get $frame_info name]]} \
+		"got expected name"
+	} else {
+	    gdb_assert {[dict get $frame_info name] == $expected} \
+		"got expected name"
+	}
+    }
+}
+
+check_stack_frame empty 0 {} "function"
+
+check_stack_frame parameters 0 {parameters [l true] \
+				    parameterTypes [l true] \
+				    parameterNames [l true] \
+				    parameterValues [l true]} \
+    {function([int] x = 64, [char] y = 65 'A')}
+
+# When 'parameters' is false, it disables the other parameter*
+# options.  This was clarified in
+# https://github.com/microsoft/debug-adapter-protocol/issues/411
+check_stack_frame noparams 0 {parameters [l false] \
+				  parameterTypes [l true] \
+				  parameterNames [l true] \
+				  parameterValues [l true]} \
+    "function"
+
+check_stack_frame line 0 {line [l true] module [l true]} \
+    "function, line $line, module .*stack-format" \
+    1
+
+check_stack_frame hex 0 \
+    {parameters [l true] parameterValues [l true] hex [l true]} \
+    "function(0x40, 0x41)"
+
+check_stack_frame elided-main 1 {} "main"
+
+# The next requests will ask for all frames, so the old frame 1 will
+# be the new frame 4.  Update the map to check this.
+set frame_id(4) $frame_id(1)
+unset frame_id(1)
+
+check_stack_frame no-elide 0 {includeAll [l true]} "function"
+check_stack_frame z-frame-1 1 {includeAll [l true]} "z_1"
+check_stack_frame z-frame-2 2 {includeAll [l true]} "z_2"
+check_stack_frame z-frame-3 3 {includeAll [l true]} "z_3"
+check_stack_frame main-include-all 4 {includeAll [l true]} "main"
+
+dap_shutdown
diff --git a/gdb/testsuite/gdb.dap/stack-format.py b/gdb/testsuite/gdb.dap/stack-format.py
new file mode 100644
index 00000000000..b15cb8adb42
--- /dev/null
+++ b/gdb/testsuite/gdb.dap/stack-format.py
@@ -0,0 +1,64 @@
+# Copyright (C) 2023 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+
+import gdb
+import itertools
+
+from gdb.FrameDecorator import DAPFrameDecorator
+
+
+class ElidingFrameDecorator(DAPFrameDecorator):
+    def __init__(self, frame, elided_frames):
+        super(ElidingFrameDecorator, self).__init__(frame)
+        self.elided_frames = elided_frames
+
+    def elided(self):
+        return iter(self.elided_frames)
+
+
+class ElidingIterator:
+    def __init__(self, ii):
+        self.input_iterator = ii
+
+    def __iter__(self):
+        return self
+
+    def __next__(self):
+        frame = next(self.input_iterator)
+        if str(frame.function()) != "function":
+            return frame
+
+        # Elide the next three frames.
+        elided = []
+        elided.append(next(self.input_iterator))
+        elided.append(next(self.input_iterator))
+        elided.append(next(self.input_iterator))
+
+        return ElidingFrameDecorator(frame, elided)
+
+
+class FrameElider:
+    def __init__(self):
+        self.name = "Elider"
+        self.priority = 900
+        self.enabled = True
+        gdb.frame_filters[self.name] = self
+
+    def filter(self, frame_iter):
+        return ElidingIterator(frame_iter)
+
+
+FrameElider()