Why does readdir not return an alphabetized list?

[fasiha]

I ran into unexpected behavior in an app because LightningFS' readdir can return non-sorted strings. The following example shows the issue in Node.js (make sure you npm install --save-dev fake-indexeddb first), but the issue was first identified in the browser (Firefox and Safari):

require("fake-indexeddb/auto"); // HAS to come first for Node.js to have indexedDB
const FS = require('@isomorphic-git/lightning-fs');

const fs = new FS("testfs", {wipe: true});
const pfs = fs.promises;

(async function() {
  await pfs.mkdir('/hi');
  const max = 15;
  const randN = Array.from(Array(50), _ => Math.floor(Math.random() * max));
  // write & append fifteen files in random order with random data
  for (const r of randN) {
    const fname = `/hi/${r}`;
    pfs.writeFile(fname, Math.random());
  }
  const contents = await pfs.readdir('/hi');
  console.log(contents);
})();

The script above writes to a set of fifteen files (whose names are between '0' and '14') in random order, and then prints the output of readdir. Running this script several times shows the issue: an unsorted list of files:

$ node demo.js
[
  '13', '2', '14', '9',
  '4',  '3', '8',  '11',
  '0',  '1', '7',  '12',
  '10', '6', '5'
]
$ node demo.js
[
  '7',  '14', '4',  '1',
  '2',  '8',  '10', '3',
  '9',  '13', '11', '5',
  '12', '6',  '0'
]
$ node demo.js
[
  '8',  '11', '14', '0',
  '13', '3',  '4',  '5',
  '6',  '9',  '7',  '12',
  '10', '2'
]

This behavior persists whether I use numeric or alphanumeric filenames.

In contrast, if I use Node's fs module, readdir returns sorted strings.

Is this an IndexedDB limitation? If it is, a sort on each readdir may be too expensive. But if not, maybe there's a workaround in the library itself?

Loving the LightningFS + isomorphic-git lifestyle, thank you for your continued hard work on these projects!

[billiegoose]

Hmm. No I guess it returns them in the order they were added. Directories are stored as Maps, and we just call map.keys(), see:

lightning-fs/src/CacheFS.js

Line 163 in d3f78e8

return [...dir.keys()].filter(key => typeof key === "string");

My experience has been that Node's readdir returns different ordering on different operating systems... so I always sort the results anyway when it matters.

A quick googling shows some examples of the craziness in Node / libuv:

• file order is sorted on Linux (but not Windows) in 2015
• file order depends on OS locale settings (and the libc implementation Node is compiled with) in 2016

So the short answer is: it doesn't return a sorted list because isomorphic-git always sorts the results of readdir so I never noticed or thought about it. In a kind of sick twist then, if we add sorting to LightningFS, that means every readdir list will end up being sorted twice, and that could actually make performance worse, so I kinda hate to do that. :-( That sucks.

I'll make a note in the README, because that's a definite "gotcha".

[fasiha]

Makes sense, thank you!