Указывает ли POSIX ls -R конкретный порядок обхода? Если нет, то какое предположение с большей вероятностью будет переносимым: в глубину или в ширину?

Я работаю над системой, которая хранит нечто очень похожее на дерево индексных дескрипторов файловой системы. В нем уже есть эквивалент команды ls, но он еще не поддерживает рекурсивный параметр. Я исследую варианты реализации для добавления рекурсивной опции. Я хотел бы сделать так, чтобы пользователи, которые знают POSIX ls, были максимально знакомы, и максимизировать переносимость любых сценариев, написанных для использования выходных данных POSIX ls -R.

Кажется, ls -R можно реализовать либо с обходом в глубину, либо с обходом в ширину. Однако мне не удалось найти однозначного ответа на вопрос, диктуется ли конкретный порядок обхода спецификацией или он остается вариантом реализации.

В документации POSIX для ls я не могу найти конкретного ответа. Это единственное утверждение, которое я смог найти, связанное с реализацией рекурсии:

Ожидается, что реализации будут проходить произвольную глубину при обработке опции -R. Единственное ограничение на глубину должно быть основано на исчерпании физической памяти для отслеживания непросмотренных каталогов.

Я также попытался просмотреть документацию для nftw. Опять же, я не нашел там конкретного заявления о порядке обхода.

Для некоторых эмпирических измерений я провел тест на компьютере с CentOS, и его поведение явно прослеживается в глубину.

> uname -a
Linux centos 3.10.0-229.el7.x86_64 #1 SMP Fri Mar 6 11:36:42 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

> yum info coreutils
Loaded plugins: fastestmirror
Repodata is over 2 weeks old. Install yum-cron? Or run: yum makecache fast
Loading mirror speeds from cached hostfile
 * base: mirror.pac-12.org
 * elrepo: ftp.osuosl.org
 * epel: linux.mirrors.es.net
 * extras: repos.lax.quadranet.com
 * updates: ftp.osuosl.org
Installed Packages
Name        : coreutils
Arch        : x86_64
Version     : 8.22
Release     : 11.el7
Size        : 14 M
Repo        : installed
From repo   : anaconda
Summary     : A set of basic GNU tools commonly used in shell scripts
URL         : http://www.gnu.org/software/coreutils/
License     : GPLv3+
Description : These are the GNU core utilities.  This package is the combination of
            : the old GNU fileutils, sh-utils, and textutils packages.

> tree testTraversal/
testTraversal/
├── dir1
│   └── dir8
│       └── dir9
│           └── dir10
├── dir2
│   ├── dir4
│   │   └── dir5
│   ├── dir6
│   ├── file1
│   └── file2
├── dir3
└── dir4
    └── dir5
        └── dir6
            └── dir7
                ├── file3
                ├── file4
                └── file5

> ls -R testTraversal/
testTraversal/:
dir1/  dir2/  dir3/  dir4/

testTraversal/dir1:
dir8/

testTraversal/dir1/dir8:
dir9/

testTraversal/dir1/dir8/dir9:
dir10/

testTraversal/dir1/dir8/dir9/dir10:

testTraversal/dir2:
dir4/  dir6/  file1  file2

testTraversal/dir2/dir4:
dir5/

testTraversal/dir2/dir4/dir5:

testTraversal/dir2/dir6:

testTraversal/dir3:

testTraversal/dir4:
dir5/

testTraversal/dir4/dir5:
dir6/

testTraversal/dir4/dir5/dir6:
dir7/

testTraversal/dir4/dir5/dir6/dir7:
file3  file4  file5

Я не знаю, продиктовано ли это поведением спецификацией или просто деталями реализации GNU coreutils.

Мое собственное наблюдение состоит в том, что структуры каталогов в файловой системе, как правило, шире, чем глубже. Это будет означать, что приоритет в глубину обычно является более эффективным с точки зрения памяти вариантом реализации, хотя можно придумать контрпримеры, в которых приоритет в ширину был бы более эффективным с точки зрения памяти.

Продиктован ли порядок обхода где-нибудь в спецификациях? Если нет, то широко ли используется в реализации обход в глубину и, следовательно, более безопасное предположение, чем в ширину?