diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2017-09-29 21:57:03 -0700 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2017-09-29 21:57:03 -0700 |
| commit | 389df91392be85e2b30150e20c5c2a98ec6fd05b (patch) | |
| tree | 05253cbde059ec0bcfb04a774e300f3aa3b8b551 | |
| parent | f021a78368b5ba841d8d88fec74d75f9f398d647 (diff) | |
| download | txr-389df91392be85e2b30150e20c5c2a98ec6fd05b.tar.gz txr-389df91392be85e2b30150e20c5c2a98ec6fd05b.tar.bz2 txr-389df91392be85e2b30150e20c5c2a98ec6fd05b.zip | |
Fixes in partition, partition*, split and split*.
Bunch of issues here: broken pre-171 compatibility,
non-termination on lazy infinite lists of indices,
doc issues.
* lib.c (partition_func, split_func, split_star_func): Do the
check for negative index values here, with the compat handling
for 170 or older.
(partition_split_common): Remove code that tries to adjust
negative indices, and delete zeros or indices that are still
negative after adjustment. The code consumes the entire list
of prefixes, so chokes on lazy lists. Also in the compat case,
there is complete breakage: the loop doesn't execute, and so
out is just nil, and it is taken as the index list.
(partition_star_func): Similar change like in partition_func.
(partition_star): Similarly to partition_split_common, take
out the bogus loop. Also take out loop that tries to remove
leading negatives: we cannot do that because we haven't
normalized them.
* txr.1: Revised doc. Condensed by describing index-list
argument in detail under partition. For the other functions,
we refer to that one. Conditions for safely handling infinite
list of indices spelled out.
| -rw-r--r-- | lib.c | 68 | ||||
| -rw-r--r-- | txr.1 | 159 |
2 files changed, 111 insertions, 116 deletions
@@ -2158,10 +2158,14 @@ static val partition_func(val env, val lcons) { cons_bind (seq, indices_base, env); cons_bind (indices, base, indices_base); + val len = nil; for (;;) { if (indices) { - val index = pop(&indices); + val raw_index = pop(&indices); + val index = if3((!opt_compat || opt_compat > 170) && minusp(raw_index), + plus(raw_index, if3(len, len, len = length(seq))), + raw_index); val index_rebased = minus(index, base); if (le(index_rebased, zero)) { @@ -2192,10 +2196,14 @@ static val split_func(val env, val lcons) { cons_bind (seq, indices_base, env); cons_bind (indices, base, indices_base); + val len = nil; for (;;) { if (indices) { - val index = pop(&indices); + val raw_index = pop(&indices); + val index = if3((!opt_compat || opt_compat > 170) && minusp(raw_index), + plus(raw_index, if3(len, len, len = length(seq))), + raw_index); val index_rebased = minus(index, base); if (lt(index_rebased, zero)) { @@ -2228,10 +2236,14 @@ static val split_star_func(val env, val lcons) { cons_bind (seq, indices_base, env); cons_bind (indices, base, indices_base); + val len = nil; for (;;) { if (indices) { - val index = pop(&indices); + val raw_index = pop(&indices); + val index = if3((!opt_compat || opt_compat > 170) && minusp(raw_index), + plus(raw_index, if3(len, len, len = length(seq))), + raw_index); val index_rebased = minus(index, base); if (lt(index_rebased, zero)) { @@ -2279,23 +2291,7 @@ static val partition_split_common(val seq, val indices, if (!seqp(indices)) indices = cons(indices, nil); - { - val len = nil; - list_collect_decl (out, ptail); - - if (!opt_compat || opt_compat > 170) { - for (; indices; indices = cdr(indices)) { - val idx_raw = car(indices); - val idx = if3(minusp(idx_raw), - plus(idx_raw, if3(len, len, len = length(seq))), - idx_raw); - if (!minusp(idx)) - ptail = list_collect(ptail, idx); - } - } - - return make_lazy_cons(func_f1(cons(seq, cons(out, zero)), split_fptr)); - } + return make_lazy_cons(func_f1(cons(seq, cons(indices, zero)), split_fptr)); } val partition(val seq, val indices) @@ -2315,12 +2311,17 @@ val split_star(val seq, val indices) static val partition_star_func(val env, val lcons) { + val len = nil; + for (;;) { cons_bind (seq, indices_base, env); cons_bind (indices, base, indices_base); if (indices) { - val index = pop(&indices); + val raw_index = pop(&indices); + val index = if3((!opt_compat || opt_compat > 170) && minusp(raw_index), + plus(raw_index, if3(len, len, len = length(seq))), + raw_index); val index_rebased = minus(index, base); val first = nullify(sub(seq, zero, index_rebased)); @@ -2377,35 +2378,18 @@ val partition_star(val seq, val indices) indices = cons(indices, nil); { - val len = nil; - list_collect_decl (tindices, ptail); - - if (!opt_compat || opt_compat > 170) { - for (; indices; indices = cdr(indices)) { - val idx_raw = car(indices); - val idx = if3(minusp(idx_raw), - plus(idx_raw, if3(len, len, len = length(seq))), - idx_raw); - if (!minusp(idx)) - ptail = list_collect(ptail, idx); - } - } - - while (tindices && lt(car(tindices), zero)) - pop(&tindices); - - while (tindices && eql(car(tindices), base)) { + while (indices && eql(car(indices), base)) { seq = nullify(cdr(seq)); if (!seq) return nil; base = plus(base, one); - pop(&tindices); + pop(&indices); } - if (!tindices) + if (!indices) return cons(seq, nil); - return make_lazy_cons(func_f1(cons(seq, cons(tindices, base)), + return make_lazy_cons(func_f1(cons(seq, cons(indices, base)), partition_star_func)); } } @@ -27181,25 +27181,24 @@ to the original is produced. If the second argument is of the form .metn index-list , -it shall be a sequence of -strictly non-decreasing, integers. - -First, the length of -.meta sequence -is added to every value in +or if an .meta index-list -that is negative. -Then, any leading negative or zero values are dropped. -The -.code partition -function then divides +was produced from the +.meta index +or +.meta function +arguments, each value in that list must be an integer. Each integer +value which is non-negative specifies the index position +given by its value. Each integer value which is negative +specifies an index position given by adding the length of .meta sequence -according to the -indices in index list. The first partition begins with the first element of -.metn sequence . -The second partition begins at the first position in -.metn index-list , -and so on. Indices beyond the length of the sequence are ignored. +to its value. The sequence index positions thus denoted by +.meta index-list +shall be strictly non-decreasing. Each successive element +is expected to designate an index position at least as high +as all previous elements, otherwise the behavior is unspecified. +Leading index positions which are (still) negative, or zero, are effectively +ignored. If .meta index-list @@ -27207,20 +27206,47 @@ is empty then a one-element list containing the entire .meta sequence is returned. +If +.meta index-list +is an infinite lazy list, the function shall terminate if that +list eventually produces an index position which is greater than or equal to +the length of +.metn sequence . + If the second argument is a function, then this function is applied to .metn sequence , and the return value of this call is then used in place of the -second argument, which must be an +second argument, which must be a single index value, which is then +taken as if it were the .meta index -or -.metn index-list . +argument, or else a list of indices, which are taken as the +.meta index-list +argument. If the second argument is an atom other than a function, it is assumed to be an integer index, and is turned into an .meta index-list of one element. +After the +.meta index-list +is obtained as an argument, or determined from the +.meta index +or +.meta function +arguments, the +.code partition +function then divides +.meta sequence +according to the indices given by that list. +The first partition begins with the first element of +.metn sequence . +The second partition begins at the first position in +.metn index-list , +and so on. Indices beyond the length of the sequence are ignored, +as are indices less than or equal to zero. + .TP* Examples: .cblk (partition '(1 2 3) 1) -> ((1) (2 3)) @@ -27266,22 +27292,37 @@ function differs from .code split in that the elements indicated by the split indices are removed. +The +.metn index , +.metn index-list , +and +.meta function +arguments are subject to the same restrictions and treatment +as the corresponding arguments of the +.code partition +function, with the following difference: the index positions indicated by +.code index-list +are required to be strictly increasing, rather than non-decreasing. + If the second argument is of the form .metn index-list , -it shall be a sequence of increasing integers. -The +or if an +.meta index-list +was produced from the +.meta index +or +.meta function +arguments, then the .code split function divides .meta sequence -according to the -indices in index list. The first piece always begins with the first -element of +according to the indices indicated in the list. The first piece always begins +with the first element of .metn sequence . Each subsequent piece begins with the position indicated by an element of .metn index-list . -Negative indices are ignored. Repeated values give rise to empty -pieces. +Negative indices are ignored. If .meta index-list includes index zero, @@ -27297,26 +27338,6 @@ The length of is added to any negative indices. An index which is still negative after being thus displaced is discarded. -If -.meta index-list -is empty then a one-element list containing the entire -.meta sequence -is returned. - -If the second argument is a function, then this function is applied -to -.metn sequence , -and the return value of this call is then used in place of the -second argument, which must be an -.meta index -or -.metn index-list . - -If the second argument is an atom other than a function, it is assumed to be -an integer index, and is turned into an -.meta index-list -of one element. - .TP* Examples: .cblk (split '(1 2 3) 1) -> ((1) (2 3)) @@ -27350,22 +27371,32 @@ second argument is ignored; if it is .metn function , it is not called. +The +.metn index , +.metn index-list , +and +.meta function +arguments are subject to the same restrictions and treatment +as the corresponding arguments of the +.code partition +function, with the following difference: the index positions indicated by +.code index-list +are required to be strictly increasing, rather than non-decreasing. + If the second argument is of the form .metn index-list , -which is a sequence -of strictly increasing non-negative integers, then +then .code partition* produces a lazy list of pieces taken from .metn sequence . -The pieces are formed by -deleting from +The pieces are formed by deleting from .meta sequence the elements at the positions given in -.metn index-list . -The pieces are the non-empty sub-strings between -the deleted elements. +.metn index-list , +such that the pieces are the remaining non-empty sub-strings from +between the deleted elements, maintaining their order. If .meta index-list @@ -27373,26 +27404,6 @@ is empty then a one-element list containing the entire .meta sequence is returned. -If -.meta index-list -contains negative values, these are displaced by adding to them -the length of -.metn sequence . - -If the second argument is a function, then this function is applied -to -.metn sequence , -and the return value of this call is then used in place of the -second argument, which must be an -.meta index -or -.metn index-list . - -If the second argument is an atom other than a function, it is assumed to be -an integer index, and is turned into an -.meta index-list -of one element. - .TP* Examples: .cblk (partition* '(1 2 3 4 5) '(0 2 4)) -> ((1) (3) (5)) |