Commit | Line | Data |
---|---|---|
aa3f6951 | 1 | /* A stack holds a frame chain |
8de051da | 2 | * Copyright (C) 1996,1997,2000,2001, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014 Free Software Foundation |
782d171c | 3 | * |
73be1d9e | 4 | * This library is free software; you can redistribute it and/or |
53befeb7 NJ |
5 | * modify it under the terms of the GNU Lesser General Public License |
6 | * as published by the Free Software Foundation; either version 3 of | |
7 | * the License, or (at your option) any later version. | |
782d171c | 8 | * |
53befeb7 NJ |
9 | * This library is distributed in the hope that it will be useful, but |
10 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
73be1d9e MV |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | * Lesser General Public License for more details. | |
782d171c | 13 | * |
73be1d9e MV |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library; if not, write to the Free Software | |
53befeb7 NJ |
16 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
17 | * 02110-1301 USA | |
73be1d9e | 18 | */ |
1bbd0b84 | 19 | |
1bbd0b84 | 20 | |
782d171c | 21 | \f |
dbb605f5 LC |
22 | #ifdef HAVE_CONFIG_H |
23 | # include <config.h> | |
24 | #endif | |
782d171c | 25 | |
a0599745 | 26 | #include "libguile/_scm.h" |
06dcb9df | 27 | #include "libguile/control.h" |
a0599745 MD |
28 | #include "libguile/eval.h" |
29 | #include "libguile/debug.h" | |
30 | #include "libguile/continuations.h" | |
31 | #include "libguile/struct.h" | |
32 | #include "libguile/macros.h" | |
33 | #include "libguile/procprop.h" | |
34 | #include "libguile/modules.h" | |
35 | #include "libguile/root.h" | |
36 | #include "libguile/strings.h" | |
b1b942b7 AW |
37 | #include "libguile/vm.h" /* to capture vm stacks */ |
38 | #include "libguile/frames.h" /* vm frames */ | |
a0599745 MD |
39 | |
40 | #include "libguile/validate.h" | |
41 | #include "libguile/stacks.h" | |
22fc179a HWN |
42 | #include "libguile/private-options.h" |
43 | ||
782d171c | 44 | |
06dcb9df AW |
45 | static SCM scm_sys_stacks; |
46 | ||
782d171c | 47 | \f |
aa3f6951 | 48 | /* {Stacks} |
782d171c | 49 | * |
aa3f6951 AW |
50 | * The stack is represented as a struct that holds a frame. The frame itself is |
51 | * linked to the next frame, or #f. | |
782d171c MD |
52 | * |
53 | * Stacks | |
54 | * Constructor | |
55 | * make-stack | |
7115d1e4 MD |
56 | * Selectors |
57 | * stack-id | |
782d171c MD |
58 | * stack-ref |
59 | * Inspector | |
60 | * stack-length | |
aa3f6951 | 61 | */ |
782d171c MD |
62 | |
63 | \f | |
64 | ||
aa3f6951 | 65 | /* Count number of debug info frames on a stack, beginning with FRAME. |
782d171c | 66 | */ |
b1b942b7 | 67 | static long |
3b14dd2f | 68 | stack_depth (enum scm_vm_frame_kind kind, const struct scm_frame *frame) |
782d171c | 69 | { |
3b14dd2f AW |
70 | struct scm_frame tmp; |
71 | long n = 1; | |
72 | memcpy (&tmp, frame, sizeof tmp); | |
73 | while (scm_c_frame_previous (kind, &tmp)) | |
93dbc31b | 74 | ++n; |
782d171c MD |
75 | return n; |
76 | } | |
77 | ||
c3a6c6f9 MD |
78 | /* Narrow STACK by cutting away stackframes (mutatingly). |
79 | * | |
80 | * Inner frames (most recent) are cut by advancing the frames pointer. | |
81 | * Outer frames are cut by decreasing the recorded length. | |
82 | * | |
83 | * Cut maximally INNER inner frames and OUTER outer frames using | |
84 | * the keys INNER_KEY and OUTER_KEY. | |
85 | * | |
86 | * Frames are cut away starting at the end points and moving towards | |
87 | * the center of the stack. The key is normally compared to the | |
88 | * operator in application frames. Frames up to and including the key | |
89 | * are cut. | |
90 | * | |
91 | * If INNER_KEY is #t a different scheme is used for inner frames: | |
92 | * | |
93 | * Frames up to but excluding the first source frame originating from | |
94 | * a user module are cut, except for possible application frames | |
95 | * between the user frame and the last system frame previously | |
96 | * encountered. | |
97 | */ | |
98 | ||
0bca90aa | 99 | static scm_t_ptrdiff |
06dcb9df AW |
100 | find_prompt (SCM key) |
101 | { | |
0bca90aa | 102 | scm_t_ptrdiff fp_offset; |
9ede013f AW |
103 | |
104 | if (!scm_dynstack_find_prompt (&SCM_I_CURRENT_THREAD->dynstack, key, | |
0bca90aa | 105 | NULL, &fp_offset, NULL, NULL, NULL)) |
9ede013f AW |
106 | scm_misc_error ("make-stack", "Prompt tag not found while narrowing stack", |
107 | scm_list_1 (key)); | |
108 | ||
0bca90aa | 109 | return fp_offset; |
06dcb9df AW |
110 | } |
111 | ||
3b14dd2f AW |
112 | static long |
113 | narrow_stack (long len, enum scm_vm_frame_kind kind, struct scm_frame *frame, | |
114 | SCM inner_cut, SCM outer_cut) | |
7115d1e4 | 115 | { |
7115d1e4 | 116 | /* Cut inner part. */ |
99d7688b | 117 | if (scm_is_true (scm_procedure_p (inner_cut))) |
c3a6c6f9 | 118 | { |
06dcb9df | 119 | /* Cut until the given procedure is seen. */ |
99d7688b | 120 | for (; len ;) |
aa3f6951 | 121 | { |
3b14dd2f | 122 | SCM proc = scm_c_frame_closure (kind, frame); |
aa3f6951 | 123 | len--; |
3b14dd2f | 124 | scm_c_frame_previous (kind, frame); |
99d7688b | 125 | if (scm_is_eq (proc, inner_cut)) |
06dcb9df | 126 | break; |
aa3f6951 | 127 | } |
c3a6c6f9 | 128 | } |
99d7688b | 129 | else if (scm_is_integer (inner_cut)) |
c3a6c6f9 | 130 | { |
06dcb9df | 131 | /* Cut specified number of frames. */ |
99d7688b NL |
132 | long inner = scm_to_int (inner_cut); |
133 | ||
06dcb9df | 134 | for (; inner && len; --inner) |
aa3f6951 | 135 | { |
aa3f6951 | 136 | len--; |
3b14dd2f | 137 | scm_c_frame_previous (kind, frame); |
aa3f6951 | 138 | } |
c3a6c6f9 | 139 | } |
99d7688b NL |
140 | else |
141 | { | |
142 | /* Cut until the given prompt tag is seen. */ | |
0bca90aa | 143 | scm_t_ptrdiff fp_offset = find_prompt (inner_cut); |
3b14dd2f AW |
144 | for (; len; len--, scm_c_frame_previous (kind, frame)) |
145 | if (fp_offset == frame->fp_offset) | |
99d7688b NL |
146 | break; |
147 | } | |
aa3f6951 | 148 | |
7115d1e4 | 149 | /* Cut outer part. */ |
99d7688b | 150 | if (scm_is_true (scm_procedure_p (outer_cut))) |
aa3f6951 | 151 | { |
3b14dd2f AW |
152 | long i, new_len; |
153 | struct scm_frame tmp; | |
154 | ||
155 | memcpy (&tmp, frame, sizeof tmp); | |
156 | ||
06dcb9df | 157 | /* Cut until the given procedure is seen. */ |
3b14dd2f AW |
158 | for (new_len = i = 0; i < len; i++, scm_c_frame_previous (kind, &tmp)) |
159 | if (scm_is_eq (scm_c_frame_closure (kind, &tmp), outer_cut)) | |
160 | new_len = i; | |
161 | ||
162 | len = new_len; | |
06dcb9df | 163 | } |
99d7688b NL |
164 | else if (scm_is_integer (outer_cut)) |
165 | { | |
166 | /* Cut specified number of frames. */ | |
167 | long outer = scm_to_int (outer_cut); | |
168 | ||
169 | if (outer < len) | |
170 | len -= outer; | |
171 | else | |
172 | len = 0; | |
173 | } | |
174 | else | |
06dcb9df | 175 | { |
99d7688b | 176 | /* Cut until the given prompt tag is seen. */ |
3b14dd2f AW |
177 | long i; |
178 | struct scm_frame tmp; | |
0bca90aa | 179 | scm_t_ptrdiff fp_offset = find_prompt (outer_cut); |
3b14dd2f AW |
180 | |
181 | memcpy (&tmp, frame, sizeof tmp); | |
182 | ||
183 | for (i = 0; i < len; i++, scm_c_frame_previous (kind, &tmp)) | |
184 | if (tmp.fp_offset == fp_offset) | |
185 | break; | |
186 | ||
187 | if (i < len) | |
188 | len = i; | |
189 | else | |
190 | len = 0; | |
06dcb9df | 191 | } |
7115d1e4 | 192 | |
3b14dd2f | 193 | return len; |
7115d1e4 MD |
194 | } |
195 | ||
782d171c MD |
196 | \f |
197 | ||
198 | /* Stacks | |
199 | */ | |
200 | ||
762e289a | 201 | SCM scm_stack_type; |
66f45472 | 202 | |
a1ec6916 | 203 | SCM_DEFINE (scm_stack_p, "stack?", 1, 0, 0, |
1bbd0b84 | 204 | (SCM obj), |
b380b885 | 205 | "Return @code{#t} if @var{obj} is a calling stack.") |
1bbd0b84 | 206 | #define FUNC_NAME s_scm_stack_p |
66f45472 | 207 | { |
7888309b | 208 | return scm_from_bool(SCM_STACKP (obj)); |
66f45472 | 209 | } |
1bbd0b84 | 210 | #undef FUNC_NAME |
66f45472 | 211 | |
af45e3b0 DH |
212 | SCM_DEFINE (scm_make_stack, "make-stack", 1, 0, 1, |
213 | (SCM obj, SCM args), | |
67941e3c MG |
214 | "Create a new stack. If @var{obj} is @code{#t}, the current\n" |
215 | "evaluation stack is used for creating the stack frames,\n" | |
216 | "otherwise the frames are taken from @var{obj} (which must be\n" | |
06dcb9df AW |
217 | "a continuation or a frame object).\n" |
218 | "\n" | |
baffb19f | 219 | "@var{args} should be a list containing any combination of\n" |
06dcb9df AW |
220 | "integer, procedure, prompt tag and @code{#t} values.\n" |
221 | "\n" | |
baffb19f NJ |
222 | "These values specify various ways of cutting away uninteresting\n" |
223 | "stack frames from the top and bottom of the stack that\n" | |
224 | "@code{make-stack} returns. They come in pairs like this:\n" | |
225 | "@code{(@var{inner_cut_1} @var{outer_cut_1} @var{inner_cut_2}\n" | |
06dcb9df AW |
226 | "@var{outer_cut_2} @dots{})}.\n" |
227 | "\n" | |
b7e64f8b | 228 | "Each @var{inner_cut_i} can be @code{#t}, an integer, a prompt\n" |
06dcb9df AW |
229 | "tag, or a procedure. @code{#t} means to cut away all frames up\n" |
230 | "to but excluding the first user module frame. An integer means\n" | |
231 | "to cut away exactly that number of frames. A prompt tag means\n" | |
232 | "to cut away all frames that are inside a prompt with the given\n" | |
233 | "tag. A procedure means to cut away all frames up to but\n" | |
234 | "excluding the application frame whose procedure matches the\n" | |
235 | "specified one.\n" | |
236 | "\n" | |
b7e64f8b | 237 | "Each @var{outer_cut_i} can be an integer, a prompt tag, or a\n" |
06dcb9df AW |
238 | "procedure. An integer means to cut away that number of frames.\n" |
239 | "A prompt tag means to cut away all frames that are outside a\n" | |
240 | "prompt with the given tag. A procedure means to cut away\n" | |
241 | "frames down to but excluding the application frame whose\n" | |
242 | "procedure matches the specified one.\n" | |
243 | "\n" | |
b7e64f8b | 244 | "If the @var{outer_cut_i} of the last pair is missing, it is\n" |
baffb19f | 245 | "taken as 0.") |
1bbd0b84 | 246 | #define FUNC_NAME s_scm_make_stack |
782d171c | 247 | { |
aa3f6951 | 248 | long n; |
af45e3b0 | 249 | SCM inner_cut, outer_cut; |
3b14dd2f AW |
250 | enum scm_vm_frame_kind kind; |
251 | struct scm_frame frame; | |
f6f88e0d MD |
252 | |
253 | /* Extract a pointer to the innermost frame of whatever object | |
254 | scm_make_stack was given. */ | |
bc36d050 | 255 | if (scm_is_eq (obj, SCM_BOOL_T)) |
782d171c | 256 | { |
aa3f6951 AW |
257 | SCM cont; |
258 | struct scm_vm_cont *c; | |
259 | ||
9ede013f | 260 | cont = scm_i_capture_current_stack (); |
8de051da | 261 | c = SCM_VM_CONT_DATA (cont); |
3b14dd2f AW |
262 | |
263 | kind = SCM_VM_FRAME_KIND_CONT; | |
264 | frame.stack_holder = c; | |
265 | frame.fp_offset = (c->fp + c->reloc) - c->stack_base; | |
266 | frame.sp_offset = (c->sp + c->reloc) - c->stack_base; | |
267 | frame.ip = c->ra; | |
13dcb666 | 268 | } |
b1b942b7 | 269 | else if (SCM_VM_FRAME_P (obj)) |
3b14dd2f AW |
270 | { |
271 | kind = SCM_VM_FRAME_KIND (obj); | |
272 | memcpy (&frame, SCM_VM_FRAME_DATA (obj), sizeof frame); | |
273 | } | |
13dcb666 | 274 | else if (SCM_CONTINUATIONP (obj)) |
06dcb9df AW |
275 | /* FIXME: Narrowing to prompt tags should narrow with respect to the prompts |
276 | that were in place when the continuation was captured. */ | |
3b14dd2f AW |
277 | { |
278 | kind = SCM_VM_FRAME_KIND_CONT; | |
279 | if (!scm_i_continuation_to_frame (obj, &frame)) | |
280 | return SCM_BOOL_F; | |
281 | } | |
4cfa92d6 AW |
282 | else if (SCM_PROGRAM_P (obj) && SCM_PROGRAM_IS_PARTIAL_CONTINUATION (obj)) |
283 | { | |
284 | kind = SCM_VM_FRAME_KIND_CONT; | |
285 | if (!scm_i_vm_cont_to_frame (SCM_PROGRAM_FREE_VARIABLE_REF (obj, 0), | |
286 | &frame)) | |
287 | return SCM_BOOL_F; | |
288 | } | |
13dcb666 DH |
289 | else |
290 | { | |
291 | SCM_WRONG_TYPE_ARG (SCM_ARG1, obj); | |
292 | /* not reached */ | |
782d171c MD |
293 | } |
294 | ||
3b14dd2f AW |
295 | /* Skip initial boot frame, if any. This is possible if the frame |
296 | originates from a captured continuation. */ | |
297 | if (SCM_PROGRAM_P (scm_c_frame_closure (kind, &frame)) | |
298 | && SCM_PROGRAM_IS_BOOT (scm_c_frame_closure (kind, &frame)) | |
299 | && !scm_c_frame_previous (kind, &frame)) | |
14aa25e4 AW |
300 | return SCM_BOOL_F; |
301 | ||
f6f88e0d MD |
302 | /* Count number of frames. Also get stack id tag and check whether |
303 | there are more stackframes than we want to record | |
304 | (SCM_BACKTRACE_MAXDEPTH). */ | |
3b14dd2f | 305 | n = stack_depth (kind, &frame); |
782d171c | 306 | |
f6f88e0d | 307 | /* Narrow the stack according to the arguments given to scm_make_stack. */ |
af45e3b0 | 308 | SCM_VALIDATE_REST_ARGUMENT (args); |
d2e53ed6 | 309 | while (n > 0 && !scm_is_null (args)) |
f6f88e0d MD |
310 | { |
311 | inner_cut = SCM_CAR (args); | |
312 | args = SCM_CDR (args); | |
d2e53ed6 | 313 | if (scm_is_null (args)) |
af45e3b0 | 314 | { |
13dcb666 | 315 | outer_cut = SCM_INUM0; |
af45e3b0 DH |
316 | } |
317 | else | |
f6f88e0d MD |
318 | { |
319 | outer_cut = SCM_CAR (args); | |
320 | args = SCM_CDR (args); | |
321 | } | |
f6f88e0d | 322 | |
3b14dd2f | 323 | n = narrow_stack (n, kind, &frame, inner_cut, outer_cut); |
f6f88e0d MD |
324 | } |
325 | ||
7115d1e4 | 326 | if (n > 0) |
3b14dd2f AW |
327 | { |
328 | /* Make the stack object. */ | |
329 | SCM stack = scm_make_struct (scm_stack_type, SCM_INUM0, SCM_EOL); | |
330 | SCM_SET_STACK_LENGTH (stack, n); | |
331 | SCM_SET_STACK_ID (stack, scm_stack_id (obj)); | |
332 | SCM_SET_STACK_FRAME (stack, scm_c_make_frame (kind, &frame)); | |
333 | return stack; | |
334 | } | |
7115d1e4 MD |
335 | else |
336 | return SCM_BOOL_F; | |
782d171c | 337 | } |
1bbd0b84 | 338 | #undef FUNC_NAME |
782d171c | 339 | |
a1ec6916 | 340 | SCM_DEFINE (scm_stack_id, "stack-id", 1, 0, 0, |
1bbd0b84 | 341 | (SCM stack), |
b380b885 | 342 | "Return the identifier given to @var{stack} by @code{start-stack}.") |
1bbd0b84 | 343 | #define FUNC_NAME s_scm_stack_id |
66f45472 | 344 | { |
06dcb9df AW |
345 | if (scm_is_eq (stack, SCM_BOOL_T) |
346 | /* FIXME: frame case assumes frame still live on the stack, and no | |
347 | intervening start-stack. Hmm... */ | |
348 | || SCM_VM_FRAME_P (stack)) | |
7115d1e4 | 349 | { |
06dcb9df AW |
350 | /* Fetch most recent start-stack tag. */ |
351 | SCM stacks = scm_fluid_ref (scm_sys_stacks); | |
352 | return scm_is_pair (stacks) ? scm_caar (stacks) : SCM_BOOL_F; | |
13dcb666 DH |
353 | } |
354 | else if (SCM_CONTINUATIONP (stack)) | |
06dcb9df AW |
355 | /* FIXME: implement me */ |
356 | return SCM_BOOL_F; | |
4cfa92d6 AW |
357 | else if (SCM_PROGRAM_P (stack) && SCM_PROGRAM_IS_PARTIAL_CONTINUATION (stack)) |
358 | /* FIXME: implement me */ | |
359 | return SCM_BOOL_F; | |
13dcb666 DH |
360 | else |
361 | { | |
14aa25e4 AW |
362 | SCM_WRONG_TYPE_ARG (SCM_ARG1, stack); |
363 | /* not reached */ | |
13dcb666 | 364 | } |
66f45472 | 365 | } |
1bbd0b84 | 366 | #undef FUNC_NAME |
66f45472 | 367 | |
a1ec6916 | 368 | SCM_DEFINE (scm_stack_ref, "stack-ref", 2, 0, 0, |
13dcb666 DH |
369 | (SCM stack, SCM index), |
370 | "Return the @var{index}'th frame from @var{stack}.") | |
1bbd0b84 | 371 | #define FUNC_NAME s_scm_stack_ref |
782d171c | 372 | { |
13dcb666 | 373 | unsigned long int c_index; |
aa3f6951 | 374 | SCM frame; |
13dcb666 DH |
375 | |
376 | SCM_VALIDATE_STACK (1, stack); | |
a55c2b68 | 377 | c_index = scm_to_unsigned_integer (index, 0, SCM_STACK_LENGTH(stack)-1); |
aa3f6951 AW |
378 | frame = SCM_STACK_FRAME (stack); |
379 | while (c_index--) | |
93dbc31b | 380 | frame = scm_frame_previous (frame); |
aa3f6951 | 381 | return frame; |
782d171c | 382 | } |
1bbd0b84 | 383 | #undef FUNC_NAME |
782d171c | 384 | |
3b3b36dd | 385 | SCM_DEFINE (scm_stack_length, "stack-length", 1, 0, 0, |
67941e3c MG |
386 | (SCM stack), |
387 | "Return the length of @var{stack}.") | |
1bbd0b84 | 388 | #define FUNC_NAME s_scm_stack_length |
782d171c | 389 | { |
34d19ef6 | 390 | SCM_VALIDATE_STACK (1, stack); |
aa3f6951 | 391 | return scm_from_long (SCM_STACK_LENGTH (stack)); |
782d171c | 392 | } |
1bbd0b84 | 393 | #undef FUNC_NAME |
782d171c MD |
394 | |
395 | \f | |
396 | ||
397 | void | |
398 | scm_init_stacks () | |
399 | { | |
06dcb9df AW |
400 | scm_sys_stacks = scm_make_fluid (); |
401 | scm_c_define ("%stacks", scm_sys_stacks); | |
402 | ||
f39448c5 AW |
403 | scm_stack_type = scm_make_vtable (scm_from_locale_string (SCM_STACK_LAYOUT), |
404 | SCM_UNDEFINED); | |
cc95e00a | 405 | scm_set_struct_vtable_name_x (scm_stack_type, |
4a655e50 | 406 | scm_from_latin1_symbol ("stack")); |
a0599745 | 407 | #include "libguile/stacks.x" |
782d171c | 408 | } |
89e00824 ML |
409 | |
410 | /* | |
411 | Local Variables: | |
412 | c-file-style: "gnu" | |
413 | End: | |
414 | */ |