Apakah POSIX ls -R menentukan urutan traversal tertentu? Jika tidak, asumsi manakah yang lebih portabel: yang mengutamakan kedalaman atau yang mengutamakan keluasan?

Saya sedang mengerjakan sistem yang menyimpan sesuatu yang sangat mirip dengan pohon inode sistem file. Ini sudah memiliki setara dengan perintah ls, tetapi belum mendukung opsi rekursif. Saya sedang menyelidiki pilihan implementasi untuk menambahkan opsi rekursif. Saya ingin memaksimalkan keakraban bagi pengguna yang mengetahui POSIX ls dan memaksimalkan portabilitas untuk skrip apa pun yang ditulis untuk menggunakan keluaran POSIX ls -R.

Tampaknya ls -R dapat diimplementasikan dengan traversal depth-first atau broadth-first traversal. Namun, saya belum dapat menemukan jawaban pasti apakah urutan traversal tertentu ditentukan oleh spesifikasi atau dibiarkan sebagai pilihan implementasi.

Dalam dokumentasi POSIX untuk ls, saya tidak dapat menemukan jawaban spesifik. Ini adalah satu-satunya pernyataan yang saya dapat temukan terkait dengan implementasi rekursi:

Implementasi diharapkan melintasi kedalaman yang berubah-ubah saat memproses opsi -R. Satu-satunya batasan pada kedalaman harus didasarkan pada kehabisan penyimpanan fisik untuk melacak direktori yang belum dilintasi.

Saya juga mencoba meninjau dokumentasi untuk nftw. Sekali lagi, saya tidak menemukan pernyataan spesifik tentang urutan traversal di sana.

Untuk beberapa pengukuran empiris, saya menjalankan tes pada kotak CentOS, dan perilaku di sana jelas merupakan traversal yang mendalam.

> 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

Saya tidak tahu apakah ini perilaku yang ditentukan oleh spesifikasi atau hanya detail implementasi GNU coreutils.

Pengamatan saya sendiri adalah bahwa struktur direktori dalam sistem file cenderung lebih luas daripada kedalamannya. Hal ini menunjukkan bahwa depth-first umumnya merupakan pilihan implementasi yang lebih hemat memori, meskipun ada kemungkinan untuk memberikan contoh tandingan di mana breadth-first akan lebih hemat memori.

Apakah urutan traversal ditentukan di bagian mana pun dalam spesifikasi? Jika tidak, apakah depth-first traversal banyak digunakan dalam implementasi, dan oleh karena itu merupakan asumsi yang lebih aman dibandingkan dengan broadth-first?


algorithm posix ls gnu-coreutils
person Chris Nauroth    schedule 11.01.2016    source sumber
comment
nftw() memiliki FTW_DEPTH bendera.   -  person gavv    schedule 12.01.2016

Jawaban (1)


arrow_upward
2
arrow_downward

coreutils memang mengutamakan kedalaman. busybox mengutamakan kedalaman. BSD/OS X adalah yang paling mendalam (secara eksperimental; sumbernya tidak dapat dibaca). Saya berharap sebagian besar implementasi harus mendalam terlebih dahulu, karena mudah dilakukan secara rekursif dan karena batas POSIX pada panjang jalur membatasi penggunaan memori/tumpukan traversal kedalaman pertama dengan cukup ketat.

person David Eisenstat    schedule 12.01.2016
comment
Terima kasih atas balasannya. Pada titik ini, sepertinya tidak mungkin kita akan menemukan poin dalam spesifikasi yang secara langsung menyatakan bahwa hal tersebut harus mengutamakan kedalaman, namun argumen bahwa ini adalah pilihan praktis masuk akal. Saya akan menerima jawaban ini. - person Chris Nauroth; 01.02.2016