summaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
...
* 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.
* Bugfix: incorrect appending to improper lists.Kaz Kylheku2019-09-091-9/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The list building framework underlying the list_collect_decl macro has a flaw: if the current list ends in an non-nil terminating atom, and the tail pointer isn't directly aiming at that atom, then a subsequent operation to add an item or append a suffix will just overwrite the atom. The correct behavior is to execute the same logic as if the tail pointer pointed at that atom on entry into the function: switch on the type of the atom, and append to it, if possible, or else throw an error. Thus, for instance, (append '(1 2 3 . 42) '(4)) wrongly returns (1 2 3 4), instead of producing an error. The 42 atom has disappeared. The example (append '(1 2 . "ab") "c") -> (1 2 . "abc") given in the man page doesn't work; it yields (1 2 . "c"). * lib.c (list_collect, list_collect_nconc, list_collect_append, list_collect_revappend, list_collect_nreconc): In the cases when the current tail object is a CONS and LCONS, and we move the tail, we must branch backwards and process the tail atom as if the tail had been that way on entry into the function. Doing this with a tail call would be nice, but in some of the functions, we hold a local resource already, so we simulate a local tail call by updating the tailobj variable and doing a backwards goto.
* list-builder: rewrite of basic methods.Kaz Kylheku2019-09-092-49/+86
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Rewriting be addition, pending and nconcing methods of list-builder to avoid loops and rely on lower list processing functions. This cleans up the semantics and error messages. Some examples of behavioral changes: (build (pend "abc") (add #\d)) now returns "abcd", consistent with (append "abc" '(#\d)). Previously it returned '(#\d). (build (add 1) (pend 2) (pend 3)) now produces a "cannot append to 2" error. Previously it produced "copy: cannot copy object of type fixnum". * share/txr/stdlib/build.tl (list-builder add): Don't use copy-list; rather the idiom for copying a sequence in preparation for appending to it is (append x nil). This will blow up nicely if x is an atom other than nil. We use this trick twice. (list-builder add*): Simplify with append. (pend, pend*, ncon): Rewrite. (ncon*): Use nconc once on a combined argument list: this is borrowed from the rewritten pend*. * txr.1: Documentation updated with clarifications, particularly in the area of the requirements regarding destructive manipulation and substructure sharing.
* digits/digpow: recycle temporary conses.Kaz Kylheku2019-09-071-2/+3
| | | | | | | * arith.c (digcommon): Improved termination test in the second loop to avoid wasteful pop when the list of powers is empty. Use rcyc_pop to recycle these conses; they will be immediately reused for building the output list.
* digits/digpow: wrong results for radix powers.Kaz Kylheku2019-09-061-1/+1
| | | | | | * arith.c (digcommon): Fix off-by-one test causing incorrect results for radix powers like (digits 10) (digits 100) ... and analogously in other radices. Reported by vapnik spaknik.
* digits/digpow: disallow base 1.Kaz Kylheku2019-09-061-1/+1
| | | | | * arith.c (digcommon): Fix wrong test that allows base 1 to be admitted, resulting in infinitely looping behavior.
* subtypep: structs with car or length method are sequences.Kaz Kylheku2019-09-064-0/+17
| | | | | | | | | | | | | * lib.c (subtypep): For the sequence supertype, check whether the subtype is a structure that has a length or car method, returning t if so. * struct.c (get_special_slot_by_type): New function. * struct.h (get_special_slot_by_type): Declared. * txr.1: Add <structures with cars or length methods> to the type hierarchy diagram.
* seq_info: bug: nil for objects with only length method.Kaz Kylheku2019-09-061-1/+1
| | | | | | * lib.c (seq_info): Add missing else, which makes the function return nil for objects that have a length method, but not a car method.
* subtypep: remove useless eq.Kaz Kylheku2019-09-061-1/+1
| | | | | | * lib.c (subtypep): The sub and sup parameters are compared for equality early in the function; byt the time we get here, we know they are not eq, so nil can be returned.
* lib: access special methods via special slot mechanism.Kaz Kylheku2019-09-065-32/+63
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | * ffi.c (ffi_flex_struct_in): Use get_special_slot to obtain length method. * lib.c (nullify_s, from_list_s, lambda_set_s): Definitions removed from here. (seq_info, car, cdr, rplaca, rplacd, make_like, nullify, replace_obj, length, empty, sub, ref, refset, dwim_set): Use get_special_slot to obtain special method from object, rather than maybe_slot. (obj_init): Remove initializations of nullify_s, from_list_s and lambda_set_s from here. * struct.c (enum special_slot): Definition removed from here. (nullify_s, from_list_s, lambda_set_s): Definitions moved here from lib.c. (special_sym): New static array. (struct_init): Initializations of nullify_s, from_list_s and lambda_set_s moved here from lib.c. (get_special_slot): New function. * struct.h (lambda_set_s): Declared. (enum special_slot): Definition moved here. (get_special_slot): Declared. * txr.1: Added compat note, since get_special_slot behaves like maybe_slot under 224 compatibility.
* struct: remove trivial static function.Kaz Kylheku2019-09-061-6/+1
| | | | | | * struct.c (get_equal_method): Static function removed. (struct_inst_equalsub): Replace one and only call to get_equal_method with direct call to get_special_static_slot.
* structs: lazily allocate special slots array.Kaz Kylheku2019-09-041-23/+30
| | | | | | | | | | | | | | | | | | | A type which we never ask for a special slot need not waste space the array. * struct.c (struct struct_type): Change spslot from array to pointer. (make_struct_type): Initialize spslot pointer to zero. (struct_type_destroy): Free the dynamic array. (invalidate_special_slot_nonexistence): Do nothing if the spslot pointer is null. (get_special_static_slot): Dynamically allocate the array if the spslot pointer is null, and update that pointer, before doing anything else. The parameter signature changes; instead of a pointer to an element of the stslot array, we pass the index. (get_equal_method): Pass the index of the equal method special slot, rather than the address of the array entry.
* seq_info: remove redundant car slot lookup.Kaz Kylheku2019-09-041-2/+0
| | | | | | * lib.c (seq_info): Due to a copy-paste error maybe_slot is being accidentally called here twice for the same slot. Removing.
* structs: special slot generalization.Kaz Kylheku2019-09-041-13/+34
| | | | | | | | | | | | | | | | | | | | | | | This lays the groundwork for optimizing access to more special slots. Currently the equal method is handled specially; if a type has an equal method, then this is cached for fast access, so we are not doing a slot lookup each time the method needs to be called. We would like a small array of such methods, with minimal code duplication. * struct.c (enum special_slot): New enum. (struct struct_type): Scalar member eqmslot replaced by spslot array. (make_struct_type): Initialize elements of new array to null; don't initialize removed eqmslot member. (invalidate_special_slot_nonexistence): New static function. (static_slot_set, static_slot_ens_rec): Use invalidate_special_slot_nonexistence instead of open code. (get_static_special_slot): General function for obtaining and caching a special slot. Based on implementation of get_equal_method. (get_equal_method): Rewritten as a simple call to get_special-static_slot.
* structs: move SLOT_CACHE_SIZE macro.Kaz Kylheku2019-09-042-2/+1
| | | | | | | | | | Only struct.c refers to this symbol, and so only struct.c needs to be recompiled when someone experiments with different values. * lib.h (SLOT_CACHE_SIZE): Macro deleted here. * struct.c (SLOT_CACHE_SIZE): Macro moved here.
* type: lcons and string are subtypes of sequence.Kaz Kylheku2019-09-041-1/+1
| | | | | | | Omissions reported by user vapnik spaknik. * lib.c (subtypepe): The lcons type and string type must report as subtypes of sequence.
* list-builder: use copy-list, not copy.Kaz Kylheku2019-09-031-6/+6
| | | | | | | * share/txr/stdlib/build.tl (list-buider add, list-builder add*, list-builder pend, list-builder pend*): Use copy-list rather than copy. This copies terminating atoms without complaining.
* list-builder: bugfix: broken self-appending.Kaz Kylheku2019-09-031-4/+7
| | | | | | | | | | | | | | | | | | | | The list builder is failing on the documented example (build (add 1 2) (pend (get)) (pend (get))) -> (1 2 1 2 1 2 1 2) wrongly constructing an infinite list. * share/txr/stdlib/build.tl (list-builder pend): When destructively appending the next argument, check whether the current tail is a tail of that object. If so, copy the object to prevent a cycle from forming. (list-builder pend*): When appending the old head to the catenated list, do the tail check and copy the object if necessary to prevent the creation of a cycle.
* New function: tailp.Kaz Kylheku2019-09-034-0/+65
| | | | | | | | | | * eval.c (eval_init): Register tailp intrinsic. * lib.c (tailp): New function. * lib.h (tailp): Declared. * txr.1: Documented.
* struct: recycle conses used for slot lookups.Kaz Kylheku2019-09-031-0/+12
| | | | | | | | | | | | When a slot is not found in a cache, and in other situations the object system conses up a key in order to search a the global slot_hash. We should be recycling these keys for reuse via rcyc_cons. This change makes recompilation of TXR's library (make clean-tlo; make) about 1.6% faster. * struct.c (lookup_slot, lookup_static_slot_desc, static_slot_p): Recycle the hash key cons cell via rcyc_cons, so it can be reused immediately.
* doc: fixes from vapnik spaknik.Kaz Kylheku2019-09-031-43/+80
| | | | | | | | | | | | | TXR user vapnik spaknik has found a swath of errors in the documentation. * txr.1: Fixed bugs in numerous examples, copy-and-paste errors in syntax sections, and other typos, including *stdin* mistyped as *std-input* in many places. A new executable code example is provided for expand-with-free-refs to calculate the result that was previously only verbally described. Fixed *stdin* mistyped as *std-input* (a non-existent symbol that imitates the internal C variable).
* doc: hyphenation of some compound words.Kaz Kylheku2019-09-031-4/+4
| | | | * txr.1: Hyphenate "heap-allocated" and "stack-allocated".
* interpreter: trivial let goes through let* case.Kaz Kylheku2019-08-311-1/+1
| | | | | | | * eval.c (bindings_helper): If there are no bindings or just one binding, then go through the sequential case. Thus trivial let is treated like let*. This avoids the continuation-related overheads incurred in the parallel case.
* interpreter: bug between let* and continuations.Kaz Kylheku2019-08-311-11/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | This was discovered by user vapnik spaknik. If a let* form is evaluated in a top-level expression such that the incoming environment is null, and a continuation is captured in the init-form of the first variable, when that continuation is invoked, an exception is thrown: "copy-env: nil is not of type env". Short repro: 1> (block nil (let* ((x (yield 42))))) ** copy-env: nil is not of type env In fact, the bug isn't that we're trying to copy nil. the problem is we are trying to copy an environment we should not be copying at all. In fact, for sequential binding, there is no need for that logic at all; it's only parallel binding which needs it, because all of the init-forms are inserting bindings into the same environment. * eval.c (bindings_helper): Don't bother with registering a copy handler for sequential binding logic, because we don't mutate environments. All of that code is moved into the parallel case.
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-22 10:17:02 +0000