This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 27712 - IndexedDB: Array comparison algorithm doesn't handle empty arrays
Summary: IndexedDB: Array comparison algorithm doesn't handle empty arrays
Status: RESOLVED FIXED
Alias: None
Product: WebAppsWG
Classification: Unclassified
Component: Indexed Database API (show other bugs)
Version: unspecified
Hardware: PC Windows NT
: P2 normal
Target Milestone: ---
Assignee: Joshua Bell
QA Contact: public-webapps-bugzilla
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-12-28 19:58 UTC by n210241048576
Modified: 2015-01-13 23:47 UTC (History)
4 users (show)

See Also:

Attachments

Description n210241048576 2014-12-28 19:58:12 UTC 
The array comparison algorithm says to compare the first element of the arrays before checking the length, which means that it doesn't work for empty arrays, despite empty arrays being valid keys.


Let A be the first Array value and B be the second Array value.
Let length be the lesser of A's length and B's length.
Let i be 0.
If the ith value of A is less than the ith value of B, then A is less than B. Skip the remaining steps.
If the ith value of A is greater than the ith value of B, then A is greater than B. Skip the remaining steps.
Increase i by 1.
If i is not equal to length, go back to step 4. Otherwise continue to next step.
If A's length is less than B's length, then A is less than B. If A's length is greater than B's length, then A is greater than B. Otherwise A and B are equal.
Comment 1 Joshua Bell 2015-01-07 18:52:06 UTC 
Simplest fix: insert new step 3 and update 4->5

1. Let A be the first Array value and B be the second Array value.
2. Let length be the lesser of A's length and B's length.
3. If length is 0, go to step 9.
4. Let i be 0.
5. If the ith value of A is less than the ith value of B, then A is less than B. Skip the remaining steps.
6. If the ith value of A is greater than the ith value of B, then A is greater than B. Skip the remaining steps.
7. Increase i by 1.
8. If i is not equal to length, go back to step 5. Otherwise continue to next step.
9. If A's length is less than B's length, then A is less than B. If A's length is greater than B's length, then A is greater than B. Otherwise A and B are equal.

Alternately:

1. Let A be the first Array value and B be the second Array value.
2. Let length be the lesser of A's length and B's length.
3. Let i be 0.
4. If i is equal to length, go to step 9. Otherwise continue to next step.
5. If the ith value of A is less than the ith value of B, then A is less than B. Skip the remaining steps.
6. If the ith value of A is greater than the ith value of B, then A is greater than B. Skip the remaining steps.
7. Increase i by 1.
8. Go back to step 4.
9. If A's length is less than B's length, then A is less than B. If A's length is greater than B's length, then A is greater than B. Otherwise A and B are equal.

Or using a 'while' loop:

1. Let A be the first Array value and B be the second Array value.
2. Let length be the lesser of A's length and B's length.
3. Let i be 0.
4. While i is less than length:
  1. If the ith value of A is less than the ith value of B, then A is less than B. Skip the remaining steps.
  2. If the ith value of A is greater than the ith value of B, then A is greater than B. Skip the remaining steps.
  3. Increase i by 1.
5. If A's length is less than B's length, then A is less than B. If A's length is greater than B's length, then A is greater than B. Otherwise A and B are equal.

I can fix in the ED if someone wants to select and sanity-check one of the above.