3 ms·

If you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to termi

If you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to terminate at all.

olliej 4y ago
What are you talking about? This is in a JS engine, where by design all code is untrusted. If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.
- ErikCorry 4y ago
  Obviously it may never crash, and it never did, even with a bad comparison function. But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that? Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.
  - olliej 4y ago
    Prior to chrome every browser had a “terminate js after x seconds” option that didn’t mean “kill the process”. But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario. Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer. As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
    - ErikCorry 4y ago
      V8's Quicksort was written in JS so going out of bounds on an array access did the same as it would in any other JS program. As I recall, JS isn't super helpful about out of bounds accesses, but there's nothing memory-unsafe about it.

If you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to terminate at all.

olliej 4y ago

What are you talking about? This is in a JS engine, where by design all code is untrusted. If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.

ErikCorry 4y ago
Obviously it may never crash, and it never did, even with a bad comparison function. But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that? Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.
- olliej 4y ago
  Prior to chrome every browser had a “terminate js after x seconds” option that didn’t mean “kill the process”. But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario. Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer. As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
  - ErikCorry 4y ago
    V8's Quicksort was written in JS so going out of bounds on an array access did the same as it would in any other JS program. As I recall, JS isn't super helpful about out of bounds accesses, but there's nothing memory-unsafe about it.