From 572a0d65ade35a2488a85fc68149646af76caa79 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Fri, 29 Sep 2017 21:57:03 -0700 Subject: 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. --- lib.c | 68 +++++++++++----------------- txr.1 | 159 +++++++++++++++++++++++++++++++++++------------------------------- 2 files changed, 111 insertions(+), 116 deletions(-) diff --git a/lib.c b/lib.c index fbc46683..ee3f0e58 100644 --- a/lib.c +++ b/lib.c @@ -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)); } } diff --git a/txr.1 b/txr.1 index 6cae6db2..ec6e37c3 100644 --- a/txr.1 +++ b/txr.1 @@ -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)) -- cgit v1.2.3