Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Re: Broken Sort Code in StdLib #2364

Closed
vicuna opened this issue Jan 27, 2000 · 1 comment
Closed

Re: Broken Sort Code in StdLib #2364

vicuna opened this issue Jan 27, 2000 · 1 comment
Labels

Comments

@vicuna
Copy link

vicuna commented Jan 27, 2000

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

@vicuna
Copy link
Author

vicuna commented Apr 17, 2000

Comment author: administrator

Fixed in 3.00 (Sort.array checks for reflexive ordering relation; code
superceded by Array.sort)

@vicuna vicuna closed this as completed Apr 17, 2000
@vicuna vicuna added the bug label Mar 19, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant