summaryrefslogtreecommitdiffstats
path: root/tests
Commit message (Collapse)AuthorAgeFilesLines
* ref: bugfix in deletion of ref place.Kaz Kylheku2023-11-111-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The ref function is not defined in the documentation as an accessor, but there is a ref place. Unfortunately, deletion is broken: (del (ref x y)) does not store the new sequence back into place x, and so it does not work correctly for lists; if x is a list, it doesn't change. Various accessors are defined in terms of ref, as place macros, such as the first, second, third, ... accessors. This fixes the bug for them also; (del (second list)) must update list. * stdlib/place.tl (ref): Fix the delete-expander to fetch the clobber expander of the sequence place, and use the simple setter to put the edited sequence into that place. * tests/012/seq.tl: Test case, which breaks without this fix. Test the (second ...) place also, which is defined in terms of ref. * txr.1: Split documentation for ref and refset, mainly because one is an Accessor and one is a Function. Removing some discussions about the equivalences between DWIM brackets and ref; there are subtleties there not worth going into. Description of refset is simplified. We mention the possibility of del over a ref place; only in that case is the sequence itself required to be a place.
* New macro: tap.Kaz Kylheku2023-11-081-0/+12
| | | | | | | | | | | * autoload.c (op_set_entries): Add tap symbol as autoload trigger for op module. * stdlib/op.tl (tap): New macro. * tests/012/op.tl: New test. * txr.1: Documented.
* New: length-list-<, length-<Kaz Kylheku2023-10-051-0/+20
| | | | | | | | | | | | | | | | | | | | | | These are functions for testing whether a list or sequence is shorter than a given integer. This is cheaper than calculating the length of lists, which is in some cases impossible if they are infinite. A length-str-< function already exists, useful with lazy strings. length-< uses length-list-< or length-str-< as appropriate * lib.[ch] (length_list_lt, length_lt): New functions. * eval.c (eval_init): length-list-< and length-< intrinsics registered. * tests/012/seq.tl: New tests. * txr.1: Documented.
* tests for flatcar and flatcar*.Kaz Kylheku2023-10-011-0/+24
| | | | * tests/012/seq.tl: New tests.
* flatten*: fix two bugs.Kaz Kylheku2023-09-301-1/+57
| | | | | | | | | | | | | | | | | | | | | | | | | | * lib.c (lazy_flatten_scan): Fix a problem which results in cases like (()), ((())) ... to incorrectly flatten to (nil). The do loop in this function which iteratively descends into a nested left-nesting of a list does not handle all cases, and therefore the function may not return at that point. Removing the return fixes the problem, but so does removing the loop so that in that case we just descend one level into the nested list, and continue in the main loop. What is incorrect is that when the consp(a) test fails and the do loop terminates, we need to distinguish the cases off a being an atom versus nil. Continuing in the loop does that. This bug was spotted by a reviewer in the comp.lang.c Usenet newsgroup. (lazy_flatten): We neglect to handle the case here that the input is an empty list, resulting in (flatten* nil) returning (nil) rather than nil. The flatten function is correct. * tests/012/seq.tl: New tests. * txr.1: Documentation improved. In particular, these functions don't handle improper lists. Also, it needs to be documented that the argument may be an atom.
* Integration with setjmp/longjmp.Kaz Kylheku2023-09-272-0/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Defining libpng bindings, with longjmp catching, is now possible. * autoload.c (ffi_set_entries): Add setjmp symbol, which is a new macro in stdlib/ffi.tl. * ffi.c (jmp_buf_s): New symbol variable. (mk_jmp_buf, rt_setjmp, longjmp_wrap): New functions. (ffi_init): Initialize jmp_buf_s. Register sys:rt-setjmp and longjmp intrinsics. * ffi.h (jmp_buf_s): Declared. * stdlib/ffi.h (setjmp): New macro. Rather than introducing a new special operator, we use a run-time support function called sys:rt-setjmp, which takes functional arguments. * unwind.[ch] (uw_snapshot, uw_restore): New functions. The rt_setjmp function needs these to restore our unwind frame stack into a sane state after catching a longjmp, which bails without unwinding it, leaving the pointers referring to frames that no longer exist. * tests/017/setjmp.tl, * tests/017/setjmp.expected: New files. * txr.1: Documented.
* New hist-sort function.Kaz Kylheku2023-09-251-0/+5
| | | | | | | | | | | | | | | * eval.c (eval_init): Register hist-sort intrinsic. * lib.c (gt_f): New global variable. (hist_succ_f): New static variable. (hist_succ): New static function. (hist_sort): New function. * lib.h (gt_f, hist_sort): Declared. * tests/012/sort.tl: New tests. * txr.1: Documented.
* New functions: nested-vec-of and nested-vec.Kaz Kylheku2023-09-211-0/+21
| | | | | | | | | | | | | | | * eval.c (eval_init): Register nestd-vec-of and nested-vec intrinsics. * lib.[ch] (vec_allocate, vec_own, vec_init): New static functions. (vector, copy_vec): Expressed in terms of new functions. (nested_vec_of_v, nested_vec_v): New functions. * args.[ch] (args_cat_from): New function. * tests/010/vec.tl: New tests. * txr.1: Documented.
* glob*: Solaris fixes.Kaz Kylheku2023-09-131-25/+26
| | | | | | | | | | | | | * glob.c (glob_wrap): #ifdef GLOB_BRACE around code that removes the flag. (super_glob_find_inner): Initialize pst. The older compiler I'm using on Solaris 10. isn't smart enough to figure out that it is not used uninitialized. * tests/018/glob.t: Skip the ...\/** test on Solaris. It takes a long time, and produces nil in the end. We don't care how it behaves, only that we pass through that pattern to glob without interpreting it as a double star.
* glob*: skip tests on Cygwin.Kaz Kylheku2023-09-131-0/+4
| | | | * tests/018/glob.tl: exit successfully on Cygwin.
* glob*: fix buggy sort comparison function.Kaz Kylheku2023-09-131-88/+89
| | | | | | | | * glob.c (glob_path_cmp): Compare bytes as unsigned. After the loop, don't test whether the pointer are null; they never are. Test whether they point to null. * tests/018/glob.tl: Expected data replaced.
* glob*: do not recognize trailing \/**.Kaz Kylheku2023-09-131-0/+25
| | | | | | | * glob.c (super_glob_rec): Do not recognize a trailing /** if it is preceded by a backslash. * tests/018/glob.tl: Test case added.
* New glob* function.Kaz Kylheku2023-09-122-0/+120
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The glob* function supports brace expansion, the ** pattern for matching zero or more path components, as well as a sane sort for path names. glob* relies on brace expansion written in Lisp; the ** processing and sorting is done by a glob-compatible C function called super_glob that uses glob. * autoload.c (glob_set_entries, glob_instantiate): New static functions. (autoload_init): Register autoload of stdlib/glob module. * glob.c (GLOB_XNOBRACE, GLOB_XSTAR): New macros. (glob_wrap): Call super_glob instead of glob if GLOB_XSTAR is present in flags. Avoid passing extension flags to glob. (super_glob_find_inner, super_glob_rec, glob_path_cmp, glob_str_cmp, super_glob): New static functions. (glob_init): Register sys:glob-xstar, and glob-xnobrace. sys:glob-xstar is used by glob* to request support for the ** pattern from glob. * stdlib/glob.tl: New file. * tests/018/glob.tl: New file. * txr.1: Documented.
* crypt: newly proposed test still fails on Musl.Kaz Kylheku2023-09-031-1/+1
| | | | | | | | * tests/018/crypt.tl: replace (crypt "a" "*$") test with (crypt "a" "::"). Musl's crypt treats all unrecognized hashes through DES, and the DES module accepts almost anything as salt characters, except '\0', '\n' and ':', since those characters would wreck the password file.
* json: allow integers and lists.Kaz Kylheku2023-09-031-0/+5
| | | | | | | | | | | | * lib.c (out_json_rec): Handle NUM and BGNUM cases same as FLNUM so integers get printed. The restriction against integers has been largely unhelpful and bothersome. Handle LCONS together with CONS. Lists that are not special notation fall through to the VEC case, which now uses seq_iter_t iteration to handle vectors and lists. * tests/010/json.tl: New tests. * txr.1: Documented support for printing integers and lists.
* crypt: detect error tokens more weakly; drop some tests.Kaz Kylheku2023-09-031-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | It has been reported by user cielesti that some of our crypt tests fail on the Musl library. Musl has some additional agorithms so it yields a meaningful hash for a "$0$" salt, as well as for "$9$". Musl uses "*" and "x" as error tokens rather than "*0" and "*1". We need to change how we detect error tokens. * sysif.c (crypt_wrap): Detect error tokens only by their length: if a string emerges from crypt or crypt_r, whose length is less than 13, it's an error token. * tests/018/crypt.tl: Drop the tests that require :error for salts "$0$" and "$9$", replacing them with a test for a salt that is almost certainly invalid in all C libraries on Linux. * txr.1: Document that crypt throws an error exception and under what circumstances (when the C library function does what).
* New functions for shell escaping.Kaz Kylheku2023-09-011-0/+11
| | | | | | | | | | | * stream.c (sh_esc, sh_esc_all, sh_esc_dq, sh_esc_sq): New static functions. (stream_init): sh-esc, sh-esc-all, sh-esc-dq, sh-esc-sq: Intrinsics registered. * tests/018/sh-esc.tl: New file. * txr.1: Documented.
* New function: str-esc.Kaz Kylheku2023-09-011-0/+39
| | | | | | | | | | * lib.[ch] (str_esc): New function. * eval.c (eval_init): str-esc intrinsic registered. * tests/015/esc.tl: New file. * txr.1: Documented.
* awk: prn returns nil.Kaz Kylheku2023-08-261-0/+10
| | | | | | | | | * stdlib/awk.tl (awk-state prn): Return nil in the no-argument case instead of returning whatever put-string returns. * tests/015/awk-misc.tl: New file. * txr.1: Documented.
* New macros opf and lopf.Kaz Kylheku2023-08-231-0/+4
| | | | | | | | | | | | | | These remove repetitive (op ...) syntax from the arguments of functional combinators. * stdlib/opt.tl (opf, lopf): New macros. * autoload.c (op_set_entries): Register opf and lopf as autoload triggers. * tests/012/op.tl: New tests. * txr.1: Documented.
* New function: csort-group.Kaz Kylheku2023-08-171-0/+10
| | | | | | | | | | | | | * autoload.c (csort_set_entries): Register csort-group as autoload trigger for stdlib/csort.tl. * stdlib/csort.tl (csort-group): New function. * tests/012/sort.tl: Tests for sort-group and csort-group. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* math: tofloat and toint in user-defined arithmetic.Kaz Kylheku2023-08-141-1/+5
| | | | | | | | | | | | | | | | | | * arith.c (tofloat_s, toint_s): New symbol variables. (tofloat, toint): If the argument is a COBJ, handle it via do_unary_method. (arith_init): Initialize new symbol variables. The functions tofloat, toint, tofloatz and tointz. are now registered here, rather than eval_init. * eval.c (eval_init): Remove registrations of tofloat, toint, tofloatz and tointz. * tests/016/ud-arith.tl: New tests. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* math: add tests for new user-defined arith functions.Kaz Kylheku2023-08-141-1/+89
| | | | | | * tests/016/ud-arith.tl (numbase): Add methods for the newer functions: cbrt, erf, ... Add tests covering these.
* tree: bug: tree-delete-specific-node doesn't use key funKaz Kylheku2023-08-141-1/+7
| | | | | | | | | | | * tree.c (tr_delete_specific): We cant' juse use key(node) as the search key; we must apply the tree's key function to the node key field to retrieve the correct search key. * tests/010/tree.tl: New test case which fails without this bugfix: a node which is the left subtree of the root node doesn't get deleted since the search is led astray by the wrong key object.
* unuse-sym: fix in face of use-sym-as.Kaz Kylheku2023-08-101-0/+8
| | | | | | | | | | | | | * lib.c (unuse_sym): A used symbol may now appear in a package under a different name. So if we don't find a symbol under the symbol's name, or find a different symbol, we must try a reverse hash search before giving up. * txr.1: Add notes to use-sym-as that unuse-sym must be used to undo its effect. Add notes to unuse-sym discussing similarities and differences versus unintern. * tests/012/use-as.tl: New test cases.
* New feature: local symbol renaming.Kaz Kylheku2023-08-101-0/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The new function use-sym-as can bring a foreign symbol into a package under a different name, which is not that symbol's name. This is also featured in a new defpackage clause, :use-syms-as. With this simple relaxation in the package system, we don't require package local nicknames, which is more complicated to implement and less ergonomic, because it doesn't actually vanquish the use of ugly package prefixes on clashing symbols. * eval.c (eval_init): Register use-syms-as. * lib.c (use_sym_as): New function, made out of use_sym. (use_sym): Now a wrapper for use_sym_as. * lib.h (use_sym_as): Declared. * stdlib/package.tl (defpackage): Implement :use-syms-as clause. * tests/012/use-as.tl: New file. * txr.1: Documented, * stdlib/doc-syms.tl: Updated.
* new: left-inserting pipeline operators.Kaz Kylheku2023-08-081-0/+4
| | | | | | | | | | | | | | | | | | | * stdlib/op.tl (opip-expand): Take arguments which specify the op and do operators to be inserted. Pass these through the recursive calls. (opip, oand): Pass op and do for the new arguments. (lopip, loand): New macros like opip and oand, but passing lop and ldo to the expander. (lflow): New macro. * autoload.c (op_set_entries): Add autoload entries for lopip, loand and lflow. * tests/012/op.tl: A few new tests. * txr.1: Documented. * stdlib/doc-syms.tl: Regenerated.
* close-stream: new : protocol from close method.Kaz Kylheku2023-08-072-1/+24
| | | | | | | | | | | | | * stream.c (close_stream): If the underlying method returns the colon symbol :, then keep the cached close_result as nil, so that the method can be called again, but return t to the caller to indicate success. * tests/018/close-delegate.tl: Test case added. * tests/018/close-delegate.expected: Updated. * txr.1: Documented.
* streams: close-stream only caches non-nil result.Kaz Kylheku2023-08-072-0/+23
| | | | | | | | | | | | | | | | | | | | This is motivated by trying to implement a struct delegate stream which performs reference counting in close, in order to close the real stream when the count hits zero. The caching behavior of close-stream is a problem. * stream.c (strm_base_init): Initialize close_result to nil, rather than nao. (strm_base_mark): Don't check close_result for nao. (close_stream): Suppress the call to op->close if close_result has a non-nil value, rather than a value other than nao. * tests/018/close-delegate.tl, * tests/018/close-delegate.expected: New files. * txr.1: Document that only a non-nil return is cached by close-stream.
* opip: new special handling of (let ...).Kaz Kylheku2023-08-031-0/+6
| | | | | | | | | | | | | * stdlib/op.tl (sys:opip-single-let-p, sys:opip-let-p): New functions. (sys:opip-expand): Restructure from collect loop to car/cdr recursive form, because the new let operators in opip need access to the rest of the pipeline. Implement let operators. * tests/012/op.tl: New tests. * txr.1: Documented.
* bug: :vars not usable with :counter in @(repeat).Kaz Kylheku2023-08-022-0/+9
| | | | | | | | | | | | | | | | | | | | | | This is a regression due to a March 2016 commit which introduced the ability for :vars in an output-side @(repeat) block to have initial values. The bug has the effect that all arguments in @(repeat) which are conses/lists get duplicated, which messes up the property list structure. * parser.y (expand_repeat_rep_args): Do not unconditionally add reg to the output at the bottom of the loop. A few cases above in the consp(arg) case handle that themselves, and do not continue the loop, so control ends up at the bottom, adding a spurious item. By removing this list_collect, we have to introduce it to just one case which relies on it. * tests/008/repeat.txr, * tests/008/repeat.expected: New files. * y.tab.c.shipped: Updated.
* match: bug: lexical symbol macros neglectedKaz Kylheku2023-07-271-0/+19
| | | | | | | | | | | | | | | | | | When a pattern variable match like @foo references a global symbol macro, that's treated as an existing expression to match, and not a new binding. However, local symbol macros are not treated this way; they are invisible to variable patterns. That is an unintended inconsistency. * stdlib/match.tl (var-list exists): Use lexical-binding-kind rather than lexical-var-p. This returns true for lexical symbol macros also. * tests/011/patmatch.tl: New test cases. * txr.1: Documentation revised to clarify that both global and local symbol macros are considered to be existing variable bindings by pattern matching.
* tests: match: move file compiling step to end.Kaz Kylheku2023-07-261-6/+6
| | | | | | * tests/011/patmatch.tl: Move the form which compiles the entire file to the end of the file, so that all the interpreted test cases complete before we compile.
* rel-path: treat empty paths as relative.Kaz Kylheku2023-07-251-1/+4
| | | | | | | | | | | | | * stdlib/path-test.tl (path-volume): Don't return :abs for a path whose empty first component isn't followed by any more items. Otherwise we return :abs for a path formed by splitting the empty string, and then calls like (rel-path "" "a") complain about a mixture of absolute and relative. With this change, empty paths given to rel-path behave as if they were ".". * tests/018/rel-path.tl: New test cases.
* del/replace with index-list: fix semantics.Kaz Kylheku2023-07-182-1/+92
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit does two things. The replace function, implemented under the hood by four specializations: replace-list, replace-vec, replace-str and replace-buf, will handle the index-list case a little differently. This is needed to fix the ability of the del macro work on place designated by an index list, such as: (del [sequence '(1 3 5 6)] which now deletes elements 1, 3, 5 and 6 from the sequence, and returns a sequence of those items. The underlying implementation uses replace with an index-list, which is now capable of deleting items. Previously, replace would stop processing the index list when the replacement-sequence corresponding to the index list ran out of items. Now, when the replacement-sequence runs out of items, the remaining index-list sequence elements specify items to be deleted. For instance if str holds "abcdefg" then: (set [str '(1 3 5)] "xy") will change str to "axcyeg". Elements 1 and 3 are replaced by x and y, respectively. Element 5, the letter f, is deleted, because the replacement "xy" has no element corresponding to 5. * lib.c (replace_list, replace_str, replace_vec): Implement new deleteion semantics for the case when the replacement sequence runs out of items. * buf.c (replace_buf): Likewise. * tests/010/seq.txr: Some new test cases here for deletion. * tests/010/seq.expected: Updated. * txr.1: Documented new semantics of replace, including a new restriction that if elements are being deleted, the indices should be monotonically increasing regardless of the type of the sequence (not only list). A value of 289 for the -C option documented, which restores the previous behavior of replace (breaking deletion by index-list, unfortunately: you don't always get to simulate an old version of TXR while using new features.)
* bug: compiled code keeps seeing var clobbered by symacro.Kaz Kylheku2023-07-171-0/+4
| | | | | | | | * eval.c (op_defsymacro, rt_defsymacro): We must call vm_invalidate_binding so the VM forgets a cached binding for this variable. * tests/019/redef.tl: Test added.
* Bug exposed due to to environment changes.Kaz Kylheku2023-07-171-0/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There was a bug in rt_defun in that it was not calling vm_invalidate_binding. This mean that compiled functions were not picking up redefinitions. This bug is fixed now because rt_defun now calls sethash on the top_fb directly, which modifies the existing binding cell; it is not allocating a new cell. We put in new test cases to confirm the proper redefinition behaviors. The proper redefinition behavior exposes an issue in pattern matching. * tests/019/redef.tl: New file. * stdlib/match.tl (transform-quote): This function's compiled image, when deposited into a .tlo file, becomes incorrect because (sys:hash-lit) turns into #H() syntax, which reads back as something else. In other words (sys:hash-lit) deosn't have print-read consistency and so doesn't externalize. To fix this right we would need a print mode which ensures machine readability rather than human readability, like in Common Lisp. For now, we just break up the pattern so that it's not a literal match. This bug was hidden due to theredefinition issue. When match.tl is being compiled, it defines non-triv-pat-p twice. Due to redefinitions not kicking in properly, the first definition of non-triv-pat-p remains in effect for some functions. When transform-qquote is being expanded, the (sys:hash-lit) pattern is treated as non-trivial, even though it is is trivial, and so it is turned into pattern matching code. The code doesn't contain a (sys:hash-lit) literal and so the issue doesn't occur.
* compiler: constant folding in optimizer.Kaz Kylheku2023-07-151-15/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The compiler handles trivial constant folding over the source code, as a source to source transformation. However, there are more opportunities for constant folding after data flow optimizations of the VM code. Early constant folding will not fold, for instance, (let ((a 2) (b 3)) (* a b)) but we can reduce this to an end instruction that returns the value of a D register that holds 6. Data flow optimizations will propagate the D registers for 2 and 3 into the gcall instruction. We can then recognize that we have a gcall with nothing but D register operands, calling a constant-foldable function. We can allocate a new D register to hold the result of that calculation and just move that D register's value into the target register of the original gcall. * stdlib/compiler.tl (compiler get-dreg): When allocating a new D reg, we must invalidate the datavec slot which is calculated from the data hash. This didn't matter before, because until now, get-datavec was called after compilation, at which point no new D regs will exist. That is changing; the optimizer can allocate D regs. (compiler null-dregs, compiler null-stab): New methods. (compiler optimize): Pass self to constructor for basic-blocks. basic-blocks now references back to the compiler. At optimization level 5 or higher, constant folding can now happen, so we call the new method in the optimizer to null the unused data. This overwrites unused D registers and unused parts of the symbol vector with nil. * stdlib/optimize (basic-blocks): Boa constructor now takes a new leftmost param, the compiler. (basic-blocks do-peephole-block): New optimization case: gcall instruction invoking const-foldable function, with all arguments being dregs. (basic-blocks null-unused-data): New method.
* Tests for checksum functions.Kaz Kylheku2023-07-081-0/+40
| | | | * tests/013/chksum.tl: New file.
* Callable integers become assignable places.Kaz Kylheku2023-06-301-0/+8
| | | | | | | | | * lib.c (dwim_set): Handle seq argument being an integer or range. * tests/012/callable.tl: A few tests. * txr.1: Documented.
* New: callable integers and ranges.Kaz Kylheku2023-06-282-2/+25
| | | | | | | | | | | | | | | | | * lib.c (do_generic_funcall): Allow integers and ranges to be function callable. They take one argument and index into it or extract a slice. In the case of ranges, this is a breaking change. Ranges can already be used in the function position in some limited ways that are not worth preserving. * tests/012/callable.tl: New file. * tests/012/iter.tl: Here we fix two instances of breakage. Using txr -C 288 will restore the behaviors previously tested here. * txr.1: Documented.
* New cached sorting functions.Kaz Kylheku2023-06-281-2/+23
| | | | | | | | | | | | | | | | | | These functions are useful when sorting a sequence using an expensive keyfun. * autoload.c (csort_set_entries, csort_instantiate): New static functions. (autlod_init): Register autoloading of csort module via new functions. * stdlib/csort.tl: New file. * tests/012/sort.tl: csort functions included in tests. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* New function: hash-map.Kaz Kylheku2023-06-281-0/+3
| | | | | | | | | | | | | | | | | | | | hash-map converts a function mapping over a sequence into a hash table. * hash.[ch] (hash_map): New function. * tests/010/hash.tl: Test case. * genman.txr: The hash-map identifier introduces a hash collision. We have to deal with that somehow now. (colli): We put the conflicting entries into a new hash called colli which maps them to an increment value. (hash-title): Increment the hash code h by the amount indicated in colli, if the title is found there. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* equal: bug: broken equality substitution.Kaz Kylheku2023-06-281-0/+8
| | | | | | | | | | | | | * lib.c (equal): Several cases which react to the type of the left argument have a default path which wrongly short-circuits to an early return. All these cases must break through to the logic at the end of the function which tests the right side for a possible equality substitution. * tests/012/struct.tl: One breaking test cases added. equal was found to return nil for two structures that have equal lists as their equality substitute.
* hash: support existing mutation+iteration semantics.Kaz Kylheku2023-06-201-0/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The original chained hashing scheme makes certain guarantees in situation when a hash table that is being iterated is also undergoing insertions or deletions. The original scheme meets these requirements simply, by putting a freeze against hash table growth while there are outstanding iterations. Chained hashing gracefully handles load factors above 1. Load factors above 1 are not possible under open addressing (and we don't even want to approach 1) but we would like to preserve the requirements. The requirements are: 1. If an iterator has already visited an item, it will not see that item again, regardless of insertions which cause the table to be reorganized. 2. It is not specified/required that an iterator will visit newly inserted items. It may visit some of those items, but not others. 3. If an iterator has not yet visited an item, and that item is deleted, it will not see that item, regardless of any insertions that reorganize the table. In this commit, we implement a "table stack" scheme. 1. When a table is resized due to insertions, and it is being iterated (h->usecount > 0), in that situation it will push the existing small table onto a stack, the h->tblstack (table stack). 2. Iterators take a hash table's current table and its size, and work with that snapshot of the table. If the original hash table grows, existing iterators work with the original table as it existed just before the reorganization. So after that they do not see any new insertions. 3. Whenever the delete operation (hash_remove) finds the item and removes it from the current table, it also walks the table stack, searches for the item in every table in the stack and nulls it out. This search is oblivious to nil; it's a blind search that goes around the table starting at the first probe position, looking for the identical cons cell to take out. This algorithm ensures that iterators will not see a deleted item, unless they already visited it before the deletion, of course. * hash.h (struct hash_iter): New members table, and mask. * hash.c (struct hash): New member, tblstack. (hash_grow): We drop the vec argument and recreate it locally (not essential to this commit). If we find that the usecount is positive, we push the existing table onto the table stack. Otherwise, we take the opportunity to obliterate the table stack. (hash_insert): Drop the restriction that hash_grow is only called when the use count is zero. Adjust calls to hash_grow to drop the vec argument. (hash_remove): When an item is found and deleted, and the table is in use by iterators, walk the table stack and delete it from each previous table. Otherwise, if the table is not in use by iterators, obliterate the table stack. (hash_mark): Exit early also if there is a table stack, and mark that stack. (do_make_hash, make_similar_hash, copy_hash): Initialize table stack in new hash. (hash_iter_mark): Mark the iterator's table. This is likely not necessary since we also mark the hash table, which should have a pointer to that same table. That wouldn't be defensive programming, though. (hash_iter_init, us_hash_iter_init): Initialize table and mask. (hash_iter_next_impl, hash_iter_peek): These functions have to walk the table snapshot taken by the iterator, using the captured mask, and not the current table. (has_reset): If the target table's use count drops to zero, obliterate its table stack. We add a missing setcheck here; this operation potentially stores a different hash into an existing iterator. It's not being done safely with regard to generational GC. * tests/010/hash.tl: New tests.
* New macro: match-cond.Kaz Kylheku2023-06-121-0/+14
| | | | | | | | | | | | | * stdlib/match.tl (match-cond): New macro. * autoload.c (match_set_entries): match-cond triggers autoload of match module. * tests/011/patmatch.tl: Tests. * txr.1: Documented. * stdlib/doc.tl: Updated.
* New functions keep-keys-if, separate-keys.Kaz Kylheku2023-06-071-0/+15
| | | | | | | | | | | * lib.[ch] (keep_keys_if, separate_keys): New functions. * eval.c (eval_init): keep-keys-if, separate-keys intrinsics registered. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* clean-file: tests.Kaz Kylheku2023-06-052-0/+110
| | | | | | * tests/018/clean.tl: New file. * tests/018/clean.expected: New file.
* New functions load-args-recurse and load-args-processKaz Kylheku2023-06-051-0/+72
| | | | | | | | | | | | * autoload.c (load_args_set_entries, load_args_instantiate): New static functions. (autoload_init): Register new auto-loaded module "load-args". * stdlib/load-args.tl: New file. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* load: now passes args via *load-args*Kaz Kylheku2023-05-313-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We can give additional arguments to load, which become arguments of the script, which it can retrieve via the *load-args* special variable. * eval.c (load_args_s): New symbol variable. (loadv): New function, taking over the implementation of load. This takes variadic arguments. Loadv binds the *load-args* variable from the list of variadic arguments. (load): Reduced to wrapper around loadv. (rt_load_for): Each clause in load for can now have arguments after the target name. If that file needs to be loaded, then the arguments are passed. (me_load_for): The macro expander for the load-for macro needs to allow for the load-arg expressions and generate code which passes them to sys:rt-load-for. They all get evaluated. (eval-init): Initialize load_args_s and register the *load-args* variable. Update registration of intrinsic function load to use loadv. * tests/019/load-ret.tl, * tests/019/load-ret/module.tl, * tests/019/load-ret/module2.tl: New files. * txr.1: Documented.
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-19 10:01:52 +0000