summaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
* hash: strengthen type mutual exclusion check.Kaz Kylheku2019-10-111-8/+13
| | | | | | | | | | * hash.c (equal_based_p): Take additional argument eq indicating that :eq-based has been specified. Check all three exclusive combinations. (hashv): Call equal_based_p unconditionally, even when :eq-based is specified and we don't use this function's return value so we benefit from that function's exclusion check. Pass the eq boolean, as required.
* parser: use eq-based hash for source location info.Kaz Kylheku2019-10-111-1/+1
| | | | | * parser.l (parser_l_init): Assign an eq-based hash to form_to_ln_hash.
* parser: use eq-based hash for circular notation.Kaz Kylheku2019-10-111-1/+1
| | | | | * parser.c (parser_circ_def): Instantiate p->circ_ref_hash as eq-based hash, not eql-based.
* printer: obj_hash must be eq-based.Kaz Kylheku2019-10-111-2/+2
| | | | | | | | | The printer must use an eq-based hash table for detecting circularity, otherwise it blows up on circular range objects. * lib.c (obj_print): instantiate ctx->obj_hash as an eq-based hash table, not eql-based.
* expander: origin_hash must be eq-based.Kaz Kylheku2019-10-111-1/+1
| | | | | | | * eval.c (eval_init): Initialize origin_hash as eq-based hash table, not eql-based. The main culprit are range #R(x y) objects. eql equality recurses over these, and if it encounters a circular one like #R(#1# #1#), it crashes.
* hash: implement :eq-based.Kaz Kylheku2019-10-112-8/+120
| | | | | | | | | | | | | | | | | | | | | We need eq based hash tables to fix a problem in *print-circle*. * hash.c (enum hash_type, hash_type_t): New enum type. (eq_based_k): New keyword variable. (eq_hash, eq_hash_op): New static functions. (hash_print_op): Ensure we print eq-based hashes with the correct keyword. (hash_assq, hash_aconsq_new_c): New static functions. (hash_eq_ops): New static structure. (do_make_hash): New function, made from previous contents of make_seeded_hash. (make_seeded_hash): Wrapper around do_make_hash now. (make_eq_hash): New function. (hashv): Parse out :eq-based argument. Use make_eq_hash if it is present. (hash_init): Initialize eq_based_k. * hash.h (eq_based_k, make_eq_hash): Declared.
* sort: remove obsolete comments.Kaz Kylheku2019-10-081-10/+1
| | | | | | * lib.c (sort_list, sort): Remove comments about dangerous mutation; these pertain to some explicit logic which existed in previous versions of the code to handle those situations.
* tree: circular notation support.Kaz Kylheku2019-10-072-0/+30
| | | | | | * lib.c (populate_obj_hash): Handle tree object. * parser.c (circ_backpatch): Likewise.
* tree: add tree-clear function.Kaz Kylheku2019-10-072-0/+12
| | | | | | | * tree.c (tree_clear): New function. (tree_init): tree-clear intrinsic registered. * tree.h (tree_clear): Declared.
* tree: make node insertion external.Kaz Kylheku2019-10-072-1/+2
| | | | | | * tree.c (tree_insert_node): Change to external linkage. * tree.h (tree_insert_node): Declared.
* tree: insert must clear left/right links.Kaz Kylheku2019-10-071-0/+3
| | | | | * tree.c (tree_insert_node): A node being inserted might not have null left and right links; we must clear them.
* circle notation: bugfix for hash_userdata.Kaz Kylheku2019-10-071-0/+3
| | | | | | * parser.c (circ_backpatch): Fix neglect to recurse into hash table's userdata object to look for circle notation references.
* op: new features for anonymous recursion.Kaz Kylheku2019-10-032-40/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | Within the op syntax, the new implicit variable @rec now refers to the function itself. There is also @(rec ...) for calling the function through a function binding. For instance, here is Fibonacci: (do if (> @1 1) (+ @(rec (pred @1)) @(rec (ppred @1))) 1) * share/txr/stdlib/op.tl (sys:op-ctx): New slots rec and recvar. (sys:op-rec-p, sys:op-ensure-rec): New functions. (sys:op-alpha-rename): Check for the new syntaxes and translate to appropriate gensymed expressions, while updating the context structure, so the expander is informed about the @rec or @(rec ...) activity in the expression. (sys:op-expand): Check whether @rec or @(rec ...) has been used in the expression, and generate the necessary variants to support it. We need to bind the lambda to a recursive binding using the same mechanism that labels uses, and possibly to bind the gensym underneat @rec to the value of that function binding. * txr.1: op documentation extended to cover the new feature, plus some wording improvements.
* symbol-function: don't break existing compiled code.Kaz Kylheku2019-10-031-2/+2
| | | | | | | | | | | | | | | | | When a symbol-function form is used as a syntactic place, the generated code makes a run-time call to sys:get-fun-getter-setter. A recent commit changed the interface of this function, which means that such code which has been previously comipled (or somehow retained in macro-expanded form) will break. * share/txr/stdlib/place.tl (sys:get-fun-setter-getter): Change the interface so it's backward compatible with the old one: the first argument is the symbol, like before, and thanks to optional arguments, it can be called with just that argument. (defplace symbol-function): Generate code to call sys:get-fun-setter-getter accordingly.
* tree: tree iterators.Kaz Kylheku2019-10-032-1/+56
| | | | | | | | | | | | * tree.c (struct tree_diter): New struct type. (tree_iter_s): New symbol variable. (tree_iter_mark): New static function. (tree_iter_ops): New static struct. (tree_begin, tree_next): New functions. (tree_init): Initialize tree_iter_s; register tree-begin and tree-next intrinsics. * tree.h (tree_begin, tree_next): Declared.
* tree: bug in key handling in insertion.Kaz Kylheku2019-10-011-16/+17
| | | | | | | | | | | | | * tree.c (tr_insert): We must apply the key_fn to the key of the node which we are inserting, not only to the tree node being searched. This is different from delete, where the key argument is just the key value to be searched for, not a key object from which the key function extracts the key value. Variable naming is hereby adjusted: let's use tr_key for the key from the tree, and tn_key for the key extracted from the argument node. (tn_lookup, tr_delete): Rename the tn_key local variable to tr_key, for consistency with the naming inside tr_insert.
* tree: crash when root is to be replaced.Kaz Kylheku2019-10-011-4/+9
| | | | | | | | * tree.c (tr_insert): When the inserted key matches the root node, then there is nothing in ti->path and ti->depth is zero. We are accessing ti->path[-1] to get a root node. We must test for zero depth and install the new node as the tree root in that case.
* safety: fix type tests that code can subvert.Kaz Kylheku2019-09-307-12/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes numerous instances of a safety hole which involves the type of a COBJ object being tested to be of a given class using logic that can be subverted by the definition of a like-named struct. Specifically logic like (typeof(obj) == hash_s) is broken, because if a struct type called hash is defined, then the test will yield true for instances of that struct type. Those instances can then be passed into code that only works on COBJ hashes, and relies on this test to reject invalid objects. * ffi.c (make_carray): Replace fragile test with strong one, using new cobjclassp function. * hash.c (hashp): Likewise. * lib.c (class_check): The expression used here for the type test moves into the new function cobjclassp and so is replaced by a call to that function. (cobjclassp): New function. * lib.h (cobjclassp): Declared. * rand.c (random_state_p): Replace fragile test using cobjclassp. * regex.c (char_set_compile): Replace fragile typeof tests for character type with is_chr. (reg_derivative, regexp): Replace fragile test with cobjclassp. * struct.c (struct_type_p): Replace fragile test with cobjclassp.
* tree: add treep predicate.Kaz Kylheku2019-09-302-0/+7
| | | | | * tree.c (treep): new function. (tree_init): Registered treep intrinsic.
* tree: allow quasiquoting into #T syntax.Kaz Kylheku2019-09-284-11/+46
| | | | | | | | | | | | | | | | | * eval.c (tree_lit_s, tree_construct_s): New symbol variables. (expand_qquote_rec): Handle sys:tree-lit syntax generated by quasi-quoted #T notaton by expanding and converting to sys:tree-constuct call. (eval_init): Initialize tree_lit_s and tree_construct_s. * eval.h (tree_lit_s, tree_construct_s): Declared. * parser.y (tree): Produce sys:tree-lit syntax when #T is quasi-quoted, and unquotes occur inside it. * tree.c (tree_construct_fname, tree_construct): New static functions. (tree_init): Register sys:tree-construct intrinsic function.
* symbol-function: support lambda expressions.Kaz Kylheku2019-09-273-15/+33
| | | | | | | | | | | | | | | | | * eval.c (lookup_fun): Check for a lambda expression and return a faked binding containing the interpreted function. (do_eval, op_fun): Remove checks for lambda that are now being done in lookup_fun. In many other places where lookup_fun is used, we still need lambda checks, like in the expander. * share/txr/stdlib/place.tl (sys:get-fun-getter-setter): Take form argument. Diagnose assignments to lambda, and to unknown function place syntax. (defplace symbol-function): Pass sys:*pl-form* to sys:get-fun-getter-setter as form argument. * txr.1: fboundp and symbol-function doc updated.
* stdlib: fix incorrect uses of compile-error.Kaz Kylheku2019-09-274-40/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Oops! We have many instances of compile-error being called in the old way with a format string as its first agument, instead of a context argument. * share/txr/stdlib/ifa.tl (ifa): Take :form argument, pass to compile-error. Let's call this "fix M". (sys:if-to-cond): Add form parameter, pass to compile-error. Let's call this let's call this "fix F". (conda, condlet): Fix M. * share/txr/stdlib/place.tl (sys:*pl-form*): New special variable. We need this in order to communicate the real place form to the place expander, similarly to how we communicate the original environment using sys:*pl-env*. (call-update-expander, call-clobber-expander, call-delete-expander): Bind sys:*pl-form* to the unexpanded place. (shift, lset): Fix M. (defplace fun): Arrange for value of sys:*pl-form* to be passed to compile-error. Let's call this "Fix P". (sys:get-mb): Fix F. (defplace symbol-macro): Fix P. (placelet*, placelet): Fix M. * share/txr/stdlib/txr-case.tl (txr-case-impl): Fix M. * share/txr/stdlib/with-resources.tl (with-resources): Fix M.
* fun operator: don't cons binding when handling lambda.Kaz Kylheku2019-09-261-4/+4
| | | | | | * eval.c (op_fun): Don't cons up a fake fbinding when processing lambda; just return result of func_interp. Test for null fbinding consolidated, too.
* Use put_char for single character output.Kaz Kylheku2019-09-262-8/+8
| | | | | | | * hash.c (hash_print_op): Replace length 1 put_string calls with put_char. * lib.c (obj_print_impl): Likewise.
* lookup_fun: eliminate recursion.Kaz Kylheku2019-09-261-24/+24
| | | | | | | | * eval.c (lookup_fun); Use iteration to search the nested environments. Put this code ahead of the global search so we fall back on it. Also, let's check for a compound function name first, so we don't search the environments for this.
* func-get-name: fix bogus return for nil argument.Kaz Kylheku2019-09-261-10/+15
| | | | | | | | | | | | * eval.c (func_get_name): when func_get_name has a nil function argument and nil env, it falls back on method_name, which naively searches its space and finds some static slots with a nil value which is then returned as a method name. Let's put in a type check that the argument must be a function. Also, let's drop the recursion in the nested environment search and switch to iteration, so we don't do these wasteful sanity checks on multiple re-entries of the function.
* New data structure: binary search trees.Kaz Kylheku2019-09-257-6/+549
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Adding binary search trees based on the new tnode cell. The scapegoat algorithm is used, which requires no additional storage in a cell. In the future we may go to something else, like red-black trees, and carve out a bit in the tag field of the cell for the red/black color. Tree cells store only single key objects, not key/value pairs. However, which part of the key object is compared is determined by a custom key function stored in the tree container. For instance, tree nodes can be cons cells, and car can be used as the key function; the cdr then stores an associated value. Trees have a printed notation #T(<props> <key>*) where <props> is a list of up to three items: <props> ::= ([<key-fn> [<less-fn> [<equal-fn>]]]) key-fn, less-fn and equal-fn are function names. If they are missing or nil, they default, respectively, to identity, less and equal. For security, the printed notation is machine-readable only if these options are symbols, not lambda expressions. Furthermore, the symbols must be listed in the special variable *tree-fun-whitelist*. * eval.c (less_s): New symbol variable. (eval_init): Initialize less_s. * eval.h (less_s): Declard. * parser.h (grammar): New #T token recognized, mapped to HASH_T. * parser.y (HASH_T): New terminal symbol. (tree): New non-terminal symbol. (i_expr, n_expr): Add tree to productions. (fname_helper): New static function. (yybadtoken): Map HASH_T to "#T". * protsym.c: Tweaked accidentally; remove. * tree.c (TREE_DEPTH_MAX): New macro. (struct tree): New struct type. (enum tree_iter_state): New enumeration. (struct tree_iter): New struct type. (tree_iter_init): New macro. (tree_s, tree_fun_whitelist_s): New symbol variables. (tn_size, tn_size_one_child, tn_lookup, tn_find_next, tn_flatten, tn_build_tree, tr_rebuild, tr_find_rebuild_scapegoat, tr_insert, tr_lookup, tr_do_delete, tr_delete, tree_insert_node, tree_insert, tree_lookup_node, tree_lookup, tree_delete, tree_root, tree_equal_op, tree_print_op, tree_mark, tree_hash_op): New static functions. (tree_ops): New static struct. (tree): New function. (tree_init): Initialize tree_s and tree_fun_whitelist_s symbol variables. Register intrinsic functions tree, tree-insert-node, tree-insert, tree-lookup-node, tree-lookup, tree-delete, tree-root. Register special variable *tree-fun-whitelist*. * tree.h (tree_s, tree_fun_whitelist_s, tree): Declared. (tree_fun_whitelist): New macro.
* New data type: tnode.Kaz Kylheku2019-09-2211-5/+220
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Binary search tree nodes are being added as a basic heap data type. The C type tag is TNOD, and the Lisp type is tnode. Binary search tree nodes have three elements: a key, a left child and a right child. The printed notation is #N(key left right). Quasiquoting is supported: ^#N(,foo ,bar) but not splicing. Because tnodes have three elements, they they fit into TXR's four-word heap cell, not requiring any additional memory allocation. These nodes are going to be the basis for a binary search tree container, which will use the scapegoat tree algorithm for maintaining balance. * tree.c, tree.h: New files. * Makefile (OBJS): Adding tree.o. * eval.c (expand_qquote_rec): Recurse through tnode cells, so unquotes work inside #N syntax. * gc.c (finalize): Add TNOD to no-op case in switch; tnodes don't require finalization. (mark_obj): Traverse tnode cell. * hash.c (equal_hash): Add TNOD case. * lib.c (tnode_s): New symbol variable. (seq_kind_tab): New entry for TNOD, mapping to SEQ_NOTSEQ. (code2type, equal): Handle TNOD. (obj_init): Initialize tnode_s variable. (obj_print_impl, populate_obj_hash): Handle TNOD. (init): Call tree_init function in tree.c. * lib.h (enum type, type_t): New enumeration TNOD. (struct tnod): New struct type. (union obj, obj_t): New union member tn of type struct tnod. (tnode_s): Declard. * parserc.c (circ_backpatch): Handle TNOD, so circular notation works through tnode cells. * parser.l (grammar): Recognize #N prefix, mapping to HASH_N token. * parser.y (HASH_N): New grammar terminal symbol. (tnode): New nonterminal symbol. (i_expr, n_expr): Add tnode cases to productions. (yybadtoken): Map HASH_N to "#N" string.
* hashing: take advantage of seed when hashing aggregates.Kaz Kylheku2019-09-201-11/+12
| | | | | | | | | | * hash.c (equal_hash): When hashing conses and ranges, perturb the seed going into the hash for the second element, rather than hashing it the same way, and then multiplying it. When hashing the elements of a vector, perturb the seed of each one by multiplying by the index. For the CHR, NUM, BGNUM, FLNUM and several types hashed like pointers, we now mix the seed into the hash.
* equal: reduce type checking for conses.Kaz Kylheku2019-09-201-3/+22
| | | | | | | | * lib.c (equal): Since we have switched on the type of the left and right argument, we can access the object directly instead of going through car and cdr. Except that for a lazy conses, we need at least one such access to force the object first.
* buffers: allow inequality comparison with less.Kaz Kylheku2019-09-202-3/+21
| | | | | | | | * lib.c (less_tab_init): Assign category 6 to BUF type, so buffers are sorted after other types. (less): Add BUF case. * txr.1: Documented.
* doc: eval-only: article agreement.Kaz Kylheku2019-09-201-1/+1
| | | | * txr.1: Fix "a eval-only" in definition of top-level form.
* op: eliminate useless quasiquote.Kaz Kylheku2019-09-151-1/+1
| | | | | * share/txr/stdlib/op.tl (sys:op-expand): Replace ^(,*args) with just args.
* gc: align objects more strictly.Kaz Kylheku2019-09-123-4/+80
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In this commit, we ensure that objects in the heap are aligned to at east eight byte boundaries (the minimum alignment from most malloc implementations on 32 and 64 bit systems). If possible, we align objects to a multiple of their size, sizeof (obj_t), which is 16 bytes on 32 bit platforms and 32 bytes on 64 bit platforms. We do this by making the object array the first field of the heap structure, and by allocating it with an aligned allocator function, if possible. * configure: detect memory alignment function: either memalign (preferred) or else posix_memalign (ugly duckling). We conditionally add either HAVE_MEMALIGN or HAVE_POSIX_MEMALIGN into config.h. * gc.c (OBJ_ALIGN): New macro. (struct heap, heap_t): Put the block member first, so objects are aligned with the containing heap. (in_heap): If the pointer is not aligned to a multiple of OBJ_ALIGN, it can't be a heap object; return zero. If allocations of the heap are aligned, then we don't need the additional alignment check in the loop body; if the pointer lands in the array, then the earlier OBJ_ALIGN check assures us it must be aligned. If we have only malloc alignment, we must do the check; the pointer could be to an address divisible by 8 which is in the middle of an obj_t. * lib.c: If HAVE_MEMALIGN is true, then include <malloc.h> so we have it declared. (memalign): If HAVE_POSIX_MEMALIGN is true, this static function is defined; it's compatible with the Glibc memalign. If HAVE_MEMALIGN and HAVE_POSIX_MEMALIGN are false, then memalign is defined as a malloc wrapper which doesn't align. (chk_malloc_gc_more): Use memalign instead of malloc. If aligned allocation is available, this will cause the heap to be aligned to a multiple of the object size.
* All HAVE_* macros should be tested with #if, not #ifdef.Kaz Kylheku2019-09-127-12/+12
| | | | | | | | | | | | | | | | | * configure: In several config tests, test HAVE_SUPERLONG_T, HAVE_LONGLONG_T and HAVE_SYS_WAIT with #if. * lib.c: Test HAVE_GETENVIRONMENTSTRINGS with #if. * lib.h: Test HAVE_DOUBLE_INTPTR_T with #if. * mpi/mpi.c: Likewise. * mpi/mpi.h: Likewise. * socket.c: Test HAVE_GETADDRINFO with #if in three places. * stream.c: Test HAVE_SYS_WAIT and HAVE_SOCKETS with #if.
* gc: bug in determining tight heap bounding box.Kaz Kylheku2019-09-121-2/+2
| | | | | | | | * gc.c (more): The heap_max_bound and heap_min_bound variables are initialized to null. We must update them unconditionally if they are in that state. What's happening otherwise is that heap_min_bound stays null and so we unnecessarily process false positives in the in_heap function.
* Improve overflow checks in string catenation.Kaz Kylheku2019-09-121-8/+8
| | | | | | | | * lib.c (cat_str, vscat): Use size_t type for the total, so that the wrapping behavior we depend on for overflow detection is well-defined. Also, there was an overflow check missing for the total + 1 beign passed to chk_wmalloc. Instead of adding that overflow check, let's just start the total at 1.
* Add forgotten alloca header under version control.Kaz Kylheku2019-09-121-0/+38
| | | | | | | | | | | | I had this file locally for the better part of a year! Commit 5e4c74dfd5927b3829b4f5e04a7964dbac6a4f34 made on December 31, 2018 claims that alloca.h was added. In fact, it was not. Things work without it because the #include "alloca.h" directives in the code end up resolving to <alloca.h>. This is widely available so nobody has seen a problem. * alloca.h: New file.
* linenoise: add copyright note.Kaz Kylheku2019-09-112-0/+2
| | | | * linenoise.c: due to extensive changes, asserting own copyright.
* ftw: forgotten copyright bump.Kaz Kylheku2019-09-111-1/+1
| | | | * ftw.c: Bump copyright to 2019.
* md5: unused variable on big endian.Kaz Kylheku2019-09-111-1/+0
| | | | * md5.c (encode): Remove unused op variable.
* Version 225.txr-225Kaz Kylheku2019-09-116-119/+156
| | | | | | | | | | * RELNOTES: Updated. * configure, txr.1: Bumped version and date. * share/txr/stdlib/ver.tl: Likewise. * txr.vim, tl.vim: Regenerated.
* list-builder: remove wasteful slot accesses.Kaz Kylheku2019-09-101-11/+11
| | | | | | | * share/txr/stdlib/build.tl (list-builder add, list-builder pend, list-builder pend): Refer to previously cached variable holding self.head or self.tail, instead of re-accessing the slot.
* list-builder: simplify circularity check in pend.Kaz Kylheku2019-09-101-4/+1
| | | | | * share/txr/stdlib/build.tl (list-builder pend): Use tailp instead of last and eq.
* printer: put out BOM character as #\xFEFF.Kaz Kylheku2019-09-101-1/+4
| | | | | | | | | * lib.c (obj_print_impl): The Unicode BOM is also a zero width non-breaking space, which causes it to look like the incomplete #\ syntax. Let's instead render it as #\xFEFF. A few other hex cases are moved up into the surrounding switch, and a little goto takes care of avoiding code duplication.
* bracket: bug: wrong result when function is applied.Kaz Kylheku2019-09-102-4/+18
| | | | | | | | | | | | Reported by user vapnik spaknik. * lib.c (bracket): Don't rely on the index variable to step through the arguments, because it only counts fixed arguments. The args_get function doesn't increment the index beyond args->fill; when popping arguments from args->list, index stays unmodified. * tests/016/arith.tl: Tests for bracket added.
* tests: add tests for list-builder and fix bug.Kaz Kylheku2019-09-102-1/+11
| | | | | | | * share/txr/stdlib/build.tl (list-buider pend*): Fix typo: apply should be append. Funny, this didn't propagate to ncon*. * tests/012/seq.tl: Some list-builder tests via build macro.
* tests: add tests for digits function.Kaz Kylheku2019-09-091-0/+18
| | | | * tests/016/arith.tl: Add various digits tests.
* New tests for sequence manipulation.Kaz Kylheku2019-09-092-0/+9
| | | | | | | | Just a few append cases with improper lists here to start with. * tests/012/seq.tl: New file. * tests/012/seq.expected: New file
* build: clean target should remove run.shKaz Kylheku2019-09-091-2/+2
| | | | | * Makefile (clean): If it exists, remove the temporary run.sh that is generated by the install-tests target.
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-20 18:21:09 +0000