Bug in make-shared-array.

Bug in make-shared-array.

[Steve Juranich]

I tried posting this on Friday, but it doesn't look like it went through. 
Here we go again...

I've found a bug in the guile 1.8.0 release such that one of the examples on
the info page about shared arrays doesn't work in guile.  The example in
question is:

(make-shared-array #1(a b c d e f g h i j k l)
                             (lambda (i j) (list (+ (* i 3) j)))
                             4 3)

The expected result is:  #2((a b c) (d e f) (g h i) (j k l)), which is what
I get for guile 1.6.7.  However, running the example in guile 1.8.0, I get
a backtrace.  Specifically:

guile> (make-shared-array #1(a b c d e f g h i j k l)
...                              (lambda (i j) (list (+ (* i 3) j)))
...                              4 3)

Backtrace:
In current input:
   1: 0* [make-shared-array #(a b c d e f g h i ...) #<procedure #f (i j)> 4
3]

<unnamed port>:1:1: In procedure make-shared-array in expression
(make-shared-array (quote #) (lambda # #) ...):
<unnamed port>:1:1: mapping out of range
ABORT: (misc-error)

I've done a little poking around and can isolate the problem to a call to
SCM_I_ARRAY_BASE at libguile/unif.c:912.

When SCM_I_ARRAY_BASE gets called on a 1-d array, things seem to work okay,
but when SCM_I_ARRAY_BASE is called on a 2-d array things seem to go
sideways.

I'd like to be able to patch this myself, but I'm not sure how fast I'd be
able to come up to speed on how the API works to be able to do that.

Any help here would be very much appreciated.

Thanks.
-- 
Steve Juranich
Tucson, AZ
USA



_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Bug in make-shared-array.

[Steve Juranich]

I've tried posting a couple of messages about this via gmane.org, but
they still haven't posted to the list, that I can see.  Sorry if
people are seeing multiple versions of this.

There is a bug in scm_make_shared_array that causes things to break
when the input array is 1-d.  I thought I had a working patch for
this, but I don't.  Anyway, the offending line is libguile/unif.c:912:

  SCM_I_ARRAY_BASE (ra) = new_min = new_max = i + SCM_I_ARRAY_BASE (oldra);

As far as I can tell, there is a bug somewhere in the SCM_I_ARRAY_BASE
macro that causes things to break when oldra is a 1d uniform array. 
The value of the array base seems to be sane for multi-dimensional
arrays, but is something very strange for 1d arrays.

Here's the proof:

<buggy.c>
#include <stdio.h>
#include <libguile.h>

SCM
show_base_wrap(SCM ra) {
  size_t base = SCM_I_ARRAY_BASE(ra);
  printf("base = %d.\n", base);
  return SCM_UNSPECIFIED;
}

void
init_buggy () {
  scm_c_define_gsubr("show-base", 1, 0, 0, show_base_wrap);
}
</buggy.c>

Then the scheme code that shows this off would be:
<proof.scm>
#! /bin/bash
exec guile -s "$0" "$@"
!#

(use-modules (ice-9 format))

(setenv "LD_LIBRARY_PATH" (string-append ".:" (getenv "LD_LIBRARY_PATH")))

(load-extension "buggy" "init_buggy")

(define good #2((a b c) (d e f) (g h i)))
(define bad  #1(a b c d e f g h i))

(format #t "This one should work:~%~!")
(show-base good)

(format #t "While this one should be weird.~%~!")
(show-base bad)
</proof.scm>

Are there any workarounds for this?

BTW:
GCC 3.4.4
libtool-1.5.2
SuSE 9.3 everything else.

Thanks a bunch.
--
Steve Juranich
Tucson, AZ
USA


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Kevin Ryde]

"Steve Juranich" <sjuranic@gmail.com> writes:
>
> Are there any workarounds for this?

There's something evil happening, I can't tell what it is.  Marius was
the last to give the array bits a prod, he might be able to say.


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Neil Jerram]

Kevin Ryde <user42@zip.com.au> writes:

> "Steve Juranich" <sjuranic@gmail.com> writes:
>>
>> Are there any workarounds for this?
>
> There's something evil happening, I can't tell what it is.  Marius was
> the last to give the array bits a prod, he might be able to say.

I've fixed this in CVS now:

	* unif.c (scm_make_shared_array): Don't use SCM_I_ARRAY_BASE when
	oldra is not an array.  (Reported by Steve Juranich.)

But there's more dodgy-looking code in the same function: in lines
872-893, this -

	  if (s[k].inc > 0)
	    old_max += (s[k].ubnd - s[k].lbnd) * s[k].inc;
	  else
	    old_min += (s[k].ubnd - s[k].lbnd) * s[k].inc;

- suggests that (old_min, old_max) will be (inclusive, exclusive),
whereas in the non-array case this -

      old_base = old_min = 0;
      old_max = scm_c_generalized_vector_length (oldra) - 1;

- suggests (inclusive, inclusive).  And at line 899 this code -

      if (s[k].ubnd < s[k].lbnd)
	{
	  if (1 == SCM_I_ARRAY_NDIM (ra))
	    ra = make_typed_vector (scm_array_type (ra), 0);
	  else
	    SCM_I_ARRAY_V (ra) = make_typed_vector (scm_array_type (ra), 0);
	  scm_array_handle_release (&old_handle);
	  return ra;
	}

- suggests that the function will do something completely different if
one of the dimensions of the new array has a negative increment.

Anyone care to comment or to concoct new tests to explore these?

     Neil



_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://mail.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Marius Vollmer]

Neil Jerram <neil@ossau.uklinux.net> writes:

> Anyone care to comment or to concoct new tests to explore these?

Everything is possible with out array code.  It is too clever for its
own good and needs to be rewritten.  Looking at the code makes you
think that something really sophisticated must be going on, but I
guess when rewriting it, we get something simple, elegant and
efficient without too much effort...

Also, my recent API overhaul has likely made things worse...

Anyway: the array bounds are supposed to be (inclusive,inclusive).
I'll have a closer look at scm_make_shared_array...

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Marius Vollmer]

Neil Jerram <neil@ossau.uklinux.net> writes:

> And at line 899 this code -
> 
>       if (s[k].ubnd < s[k].lbnd)
> 	{
> 	  if (1 == SCM_I_ARRAY_NDIM (ra))
> 	    ra = make_typed_vector (scm_array_type (ra), 0);
> 	  else
> 	    SCM_I_ARRAY_V (ra) = make_typed_vector (scm_array_type (ra), 0);
> 	  scm_array_handle_release (&old_handle);
> 	  return ra;
> 	}
> 
> - suggests that the function will do something completely different if
> one of the dimensions of the new array has a negative increment.

No, ubnd < lbnd does not mean that the increment is negative.  Ubnd
and lbnd are always sorted so that the smallest legal index is lbnd
and the largest legal index is ubnd (for the dimension at hand).  When
ubnd is smaller than lbnd, the index range in that dimension is emtpy
and the whole array has zero elements, consequently.  The test in your
snippet 'optimizes' for that case.  (Makes me cringe.)

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Marius Vollmer]

Neil Jerram <neil@ossau.uklinux.net> writes:

> in lines
> 872-893, this -
> 
> 	  if (s[k].inc > 0)
> 	    old_max += (s[k].ubnd - s[k].lbnd) * s[k].inc;
> 	  else
> 	    old_min += (s[k].ubnd - s[k].lbnd) * s[k].inc;
> 
> - suggests that (old_min, old_max) will be (inclusive, exclusive),

Hmm, no, this loop computes the range of valid indices into the
underlying storage vector and is not concerned with the number of
elements.  Thus, all valid indices i must satisfy old_min <= i <=
old_max.

However, trying to condense the range checking of the shared array
into just comparing the valid index ranges in the underlying vector
will not catch all violations.  For example, given a 2x2 matrix that
is stored in elements 0,1,2, and 3 of a vector

    (define a #2((0 1) (2 3)))

we can make a shared array for its first row like this:

    (define r0 (make-shared-array a (lambda (i) (list 0 i)) 2))

This array refers to elements 0,1 of the vector that stores a.

We can also make a row that has three elements:

    (define r1 (make-shared-array a (lambda (i) (list 0 i)) 3))
    r1 => #1(1 2 3)

This row wraps around and its third element is the first element of
the second row of a.

The checking done by make-shared-array will never allow accesses
outside of the storage vector, but it might allow accesses to elements
that are not part of the original array passed to make-shared-array.

This behavior might or might not be a feature, but if you really want
it, it is probably better to use array-contents explicitely.

I'm inclined not to do anything about this until starting a bigger,
more general cleanup of the code.  Thoughts?

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> This behavior might or might not be a feature, but if you really want
> it, it is probably better to use array-contents explicitely.

Yep, that should be an error.


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Steve Juranich]

Marius Vollmer wrote:

> The checking done by make-shared-array will never allow accesses
> outside of the storage vector, but it might allow accesses to elements
> that are not part of the original array passed to make-shared-array.
> 
> This behavior might or might not be a feature, but if you really want
> it, it is probably better to use array-contents explicitely.
> 
> I'm inclined not to do anything about this until starting a bigger,
> more general cleanup of the code.  Thoughts?

Okay.  So maybe I missed something here.  Is there a workaround in place so
that the examples in the info page work?  Because right now, not all of
them do:

>From the info page:
<info>
     Dimensions can be increased by for instance considering portions
     of a one dimensional array as rows in a two dimensional array.
     (`array-contents' below can do the opposite, flattening an array.)

          (make-shared-array #1(a b c d e f g h i j k l)
                             (lambda (i j) (list (+ (* i 3) j)))
                             4 3)
          => #2((a b c) (d e f) (g h i) (j k l))
</info>

But in a guile process...
<process>
guile> (make-shared-array #1(a b c d e f g h i j k l)
                             (lambda (i j) (list (+ (* i 3) j)))
                             4 3)

Backtrace:
In standard input:
   8: 0* [make-shared-array #(a b c d e f g h i ...) #<procedure #f (i j)> 4
3]

standard input:8:1: In procedure make-shared-array in expression
(make-shared-array (quote #) (lambda # #) ...):
standard input:8:1: mapping out of range
ABORT: (misc-error)
</process>

My opinion would be that this would be higher priority as long as the info
page examples don't work (then again, I'm not a developer).  I guess an
easier fix would be to change the info page examples. ;-)

Thanks for making sure this doesn't slip through the cracks.

Gratefully,
-- 
Steve Juranich
Tucson, AZ
USA



_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Marius Vollmer]

Steve Juranich <sjuranic@gmail.com> writes:

> Okay.  So maybe I missed something here.  Is there a workaround in place so
> that the examples in the info page work?

That was fixed with Neil's change, I believe:

2006-03-10  Neil Jerram  <neil@ossau.uklinux.net>

	* unif.c (scm_make_shared_array): Don't use SCM_I_ARRAY_BASE when
	oldra is not an array.  (Reported by Steve Juranich.)

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Re: Bug in make-shared-array.

[Neil Jerram]

Marius Vollmer <mvo@zagadka.de> writes:

> Neil Jerram <neil@ossau.uklinux.net> writes:
>
>> in lines
>> 872-893, this -
>> 
>> 	  if (s[k].inc > 0)
>> 	    old_max += (s[k].ubnd - s[k].lbnd) * s[k].inc;
>> 	  else
>> 	    old_min += (s[k].ubnd - s[k].lbnd) * s[k].inc;
>> 
>> - suggests that (old_min, old_max) will be (inclusive, exclusive),
>
> Hmm, no, this loop computes the range of valid indices into the
> underlying storage vector and is not concerned with the number of
> elements.  Thus, all valid indices i must satisfy old_min <= i <=
> old_max.

Thanks for explaining this.  (And sorry for this late reply.)

> I'm inclined not to do anything about this until starting a bigger,
> more general cleanup of the code.  Thoughts?

Agreed.

Regards,
     Neil



_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile

Bug in make-shared-array.

[Steve Juranich]

I tried posting this on Friday, but it doesn't look like it went through. 
Here we go again...

I've found a bug in the guile 1.8.0 release such that one of the examples on
the info page about shared arrays doesn't work in guile.  The example in
question is:

(make-shared-array #1(a b c d e f g h i j k l)
                             (lambda (i j) (list (+ (* i 3) j)))
                             4 3)

The expected result is:  #2((a b c) (d e f) (g h i) (j k l)), which is what
I get for guile 1.6.7.  However, running the example in guile 1.8.0, I get
a backtrace.  Specifically:

guile> (make-shared-array #1(a b c d e f g h i j k l)
...                              (lambda (i j) (list (+ (* i 3) j)))
...                              4 3)

Backtrace:
In current input:
   1: 0* [make-shared-array #(a b c d e f g h i ...) #<procedure #f (i j)> 4
3]

<unnamed port>:1:1: In procedure make-shared-array in expression
(make-shared-array (quote #) (lambda # #) ...):
<unnamed port>:1:1: mapping out of range
ABORT: (misc-error)

I've done a little poking around and can isolate the problem to a call to
SCM_I_ARRAY_BASE at libguile/unif.c:912.

I'm working on this problem right now and hope to have a patch by the end of
the day, but any help would be greatly appreciated.

Thanks.
-- 
Steve Juranich
Tucson, AZ
USA



_______________________________________________
Bug-guile mailing list
Bug-guile@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-guile