Original bug ID: 33
Reporter: administrator
Status: closed
Resolution: fixed
Priority: normal
Severity: minor
Category: ~DO NOT USE (was: OCaml general)

Bug description

Hi,

Thank you for your message to the Caml mailing list.

However your message seems to be a bug report; hence I send it to the
relevant mailing list

caml-bugs@inria.fr

Thank again for your interest in Caml.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Dear Caml Crowd...

There still appears to be a problem with the Standard Library Sort.array
routine. Violation of boundary conditions occur on some occaisions that
manifest an invalid page fault runtime error.

I have copied the code from the source, modified to explicitly check for
boundary violations and this appears to fix the problem. My fix is probably
non-optimal.

The original code fragment is

...
  let pivot = unsafe_get arr mid in
  let i = ref (lo + 1) and j = ref (hi - 1) in
  while !i < !j do
    while not (cmp pivot (unsafe_get arr !i)) do incr i done;
    while not (cmp (unsafe_get arr !j) pivot) do decr j done;
    if !i < !j then swap arr !i !j;
    incr i; decr j
  done;
...

The modified code fragment is:
(Note the explicit checks in the innermost while loops.)

  let pivot = unsafe_get arr hi in
  let i = ref lo and j = ref hi in
  while !i < !j do
    while !i < hi && order (unsafe_get arr !i) pivot do incr i done;
    while !j > lo && order pivot (unsafe_get arr !j) do decr j done;
    if !i < !j then swap arr !i !j
  done;

This problem was first noticed in OCaml 2.03 and has been verified to exist
in OCaml 2.99.

David McClain, Sr. Scientist
Raytheon Systems Co.
Tucson, AZ