diff options
author | Andy Wingo <wingo@pobox.com> | 2020-09-10 21:57:21 +0200 |
---|---|---|
committer | Andy Wingo <wingo@pobox.com> | 2020-09-10 21:57:21 +0200 |
commit | e9c5a1719bae94961ae40151f476a3e221e94b18 (patch) | |
tree | 49ec142e1f978565b8ddebd8ad349c9b8d73025b /libguile/trees.c | |
parent | 433b701a2339ac152ab0b7f42e8221c5163a9093 (diff) | |
download | guile-e9c5a1719bae94961ae40151f476a3e221e94b18.tar.gz |
Move copy-tree to (ice-9 copy-tree); deprecate main binding
* doc/ref/api-data.texi (List Constructors):
* doc/ref/api-utility.texi (Copying): Update docs to mention module.
* libguile.h: Remove trees.h inclusion.
* libguile/Makefile.am (libguile_@GUILE_EFFECTIVE_VERSION@_la_SOURCES):
(DOT_X_FILES, DOT_DOC_FILES, modinclude_HEADERS): Remove trees.c,
trees.h, and related files.
* libguile/init.c (scm_i_init_guile): Remove trees.h and the
scm_init_trees call.
* libguile/trees.c:
* libguile/trees.h: Remove.
* module/Makefile.am (SOURCES): Add ice-9/copy-tree.scm.
* module/ice-9/copy-tree.scm: New file.
* module/ice-9/deprecated.scm (copy-tree*): Export as copy-tree,
proxying to (ice-9 copy-tree).
* module/system/repl/common.scm:
* module/web/client.scm:
* test-suite/tests/elisp.test:
* test-suite/tests/srfi-1.test:
* module/oop/goops/save.scm: Use (ice-9 copy-tree).
* test-suite/Makefile.am (SCM_TESTS): Add copy-tree.test.
* test-suite/tests/copy-tree.test: New file; test pulled from
eval.test.
* libguile/deprecated.h:
* libguile/deprecated.c (scm_copy_tree): Deprecate.
Diffstat (limited to 'libguile/trees.c')
-rw-r--r-- | libguile/trees.c | 210 |
1 files changed, 0 insertions, 210 deletions
diff --git a/libguile/trees.c b/libguile/trees.c deleted file mode 100644 index 32ff984fa..000000000 --- a/libguile/trees.c +++ /dev/null @@ -1,210 +0,0 @@ -/* Copyright 1995-2010,2018 - Free Software Foundation, Inc. - - This file is part of Guile. - - Guile is free software: you can redistribute it and/or modify it - under the terms of the GNU Lesser General Public License as published - by the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - Guile 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 Lesser General Public - License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with Guile. If not, see - <https://www.gnu.org/licenses/>. */ - - - -#ifdef HAVE_CONFIG_H -# include <config.h> -#endif - -#include <stdarg.h> - -#include "eq.h" -#include "gsubr.h" -#include "list.h" -#include "pairs.h" -#include "srcprop.h" -#include "vectors.h" - -#include "trees.h" - - -/* scm_copy_tree creates deep copies of pairs and vectors, but not of any other - * data types. - * - * To avoid infinite recursion due to cyclic structures, the hare-and-tortoise - * pattern is used to detect cycles. In fact, the pattern is used in two - * dimensions, vertical (indicated in the code by the variable names 'hare' - * and 'tortoise') and horizontal ('rabbit' and 'turtle'). In both - * dimensions, the hare/rabbit will take two steps when the tortoise/turtle - * takes one. - * - * The vertical dimension corresponds to recursive calls to function - * copy_tree: This happens when descending into vector elements, into cars of - * lists and into the cdr of an improper list. In this dimension, the - * tortoise follows the hare by using the processor stack: Every stack frame - * will hold an instance of struct t_trace. These instances are connected in - * a way that represents the trace of the hare, which thus can be followed by - * the tortoise. The tortoise will always point to struct t_trace instances - * relating to SCM objects that have already been copied. Thus, a cycle is - * detected if the tortoise and the hare point to the same object, - * - * The horizontal dimension is within one execution of copy_tree, when the - * function cdr's along the pairs of a list. This is the standard - * hare-and-tortoise implementation, found several times in guile. */ - -struct t_trace { - struct t_trace *trace; /* These pointers form a trace along the stack. */ - SCM obj; /* The object handled at the respective stack frame.*/ -}; - -static SCM -copy_tree (struct t_trace *const hare, - struct t_trace *tortoise, - unsigned int tortoise_delay); - -SCM_DEFINE (scm_copy_tree, "copy-tree", 1, 0, 0, - (SCM obj), - "Recursively copy the data tree that is bound to @var{obj}, and return a\n" - "the new data structure. @code{copy-tree} recurses down the\n" - "contents of both pairs and vectors (since both cons cells and vector\n" - "cells may point to arbitrary objects), and stops recursing when it hits\n" - "any other object.") -#define FUNC_NAME s_scm_copy_tree -{ - /* Prepare the trace along the stack. */ - struct t_trace trace; - trace.obj = obj; - - /* In function copy_tree, if the tortoise makes its step, it will do this - * before the hare has the chance to move. Thus, we have to make sure that - * the very first step of the tortoise will not happen after the hare has - * really made two steps. This is achieved by passing '2' as the initial - * delay for the tortoise. NOTE: Since cycles are unlikely, giving the hare - * a bigger advantage may improve performance slightly. */ - return copy_tree (&trace, &trace, 2); -} -#undef FUNC_NAME - - -static SCM -copy_tree (struct t_trace *const hare, - struct t_trace *tortoise, - unsigned int tortoise_delay) -#define FUNC_NAME s_scm_copy_tree -{ - if (!scm_is_pair (hare->obj) && !scm_is_vector (hare->obj)) - { - return hare->obj; - } - else - { - /* Prepare the trace along the stack. */ - struct t_trace new_hare; - hare->trace = &new_hare; - - /* The tortoise will make its step after the delay has elapsed. Note - * that in contrast to the typical hare-and-tortoise pattern, the step - * of the tortoise happens before the hare takes its steps. This is, in - * principle, no problem, except for the start of the algorithm: Then, - * it has to be made sure that the hare actually gets its advantage of - * two steps. */ - if (tortoise_delay == 0) - { - tortoise_delay = 1; - tortoise = tortoise->trace; - if (SCM_UNLIKELY (scm_is_eq (hare->obj, tortoise->obj))) - scm_wrong_type_arg_msg (FUNC_NAME, 1, hare->obj, - "expected non-circular data structure"); - } - else - { - --tortoise_delay; - } - - if (scm_is_vector (hare->obj)) - { - size_t length = SCM_SIMPLE_VECTOR_LENGTH (hare->obj); - SCM new_vector = scm_c_make_vector (length, SCM_UNSPECIFIED); - - /* Each vector element is copied by recursing into copy_tree, having - * the tortoise follow the hare into the depths of the stack. */ - unsigned long int i; - for (i = 0; i < length; ++i) - { - SCM new_element; - new_hare.obj = SCM_SIMPLE_VECTOR_REF (hare->obj, i); - new_element = copy_tree (&new_hare, tortoise, tortoise_delay); - SCM_SIMPLE_VECTOR_SET (new_vector, i, new_element); - } - - return new_vector; - } - else /* scm_is_pair (hare->obj) */ - { - SCM result; - SCM tail; - - SCM rabbit = hare->obj; - SCM turtle = hare->obj; - - SCM copy; - - /* The first pair of the list is treated specially, in order to - * preserve a potential source code position. */ - result = tail = scm_cons_source (rabbit, SCM_EOL, SCM_EOL); - new_hare.obj = SCM_CAR (rabbit); - copy = copy_tree (&new_hare, tortoise, tortoise_delay); - SCM_SETCAR (tail, copy); - - /* The remaining pairs of the list are copied by, horizontally, - * having the turtle follow the rabbit, and, vertically, having the - * tortoise follow the hare into the depths of the stack. */ - rabbit = SCM_CDR (rabbit); - while (scm_is_pair (rabbit)) - { - new_hare.obj = SCM_CAR (rabbit); - copy = copy_tree (&new_hare, tortoise, tortoise_delay); - SCM_SETCDR (tail, scm_cons (copy, SCM_UNDEFINED)); - tail = SCM_CDR (tail); - - rabbit = SCM_CDR (rabbit); - if (scm_is_pair (rabbit)) - { - new_hare.obj = SCM_CAR (rabbit); - copy = copy_tree (&new_hare, tortoise, tortoise_delay); - SCM_SETCDR (tail, scm_cons (copy, SCM_UNDEFINED)); - tail = SCM_CDR (tail); - rabbit = SCM_CDR (rabbit); - - turtle = SCM_CDR (turtle); - if (SCM_UNLIKELY (scm_is_eq (rabbit, turtle))) - scm_wrong_type_arg_msg (FUNC_NAME, 1, rabbit, - "expected non-circular data structure"); - } - } - - /* We have to recurse into copy_tree again for the last cdr, in - * order to handle the situation that it holds a vector. */ - new_hare.obj = rabbit; - copy = copy_tree (&new_hare, tortoise, tortoise_delay); - SCM_SETCDR (tail, copy); - - return result; - } - } -} -#undef FUNC_NAME - - -void -scm_init_trees () -{ -#include "trees.x" -} |