Mengapa ls -R disebut daftar "rekursif"?

Saya mengerti bahwa ls -Rmenampilkan daftar direktori. Tetapi mengapa itu bersifat rekursif? Bagaimana rekursi digunakan dalam proses?

Pertama, mari kita tentukan struktur folder arbitrer:

.
├── a1 [D]
│   ├── b1 [D]
│   │   ├── c1
│   │   ├── c2 [D]
│   │   │   ├── d1
│   │   │   ├── d2
│   │   │   └── d3
│   │   ├── c3
│   │   ├── c4
│   │   └── c5
│   └── b2 [D]
│       ├── c6
│       └── c7
├── a2 [D]
│   ├── b3 [D]
│   │   ├── c8
│   │   └── c9
│   └── b4 [D]
│       ├── c10 
│       └── c11
├── a3 [D]
│   ├── b5
│   ├── b6
│   └── b7
└── a4 [D]

Ketika kami melakukannya ls, kami mendapatkan output dari folder dasar saja:

a1 a2 a3 a4

Namun, ketika kita menelepon ls -R, kita mendapatkan sesuatu yang berbeda:

.:
a1  a2  a3  a4

./a1:
b1  b2

./a1/b1:
c1  c2  c3  c4  c5

./a1/b1/c2:
d1  d2  d3

./a1/b2:
c6  c7

./a2:
b3  b4

./a2/b3:
c8  c9

./a2/b4:
c10  c11

./a3:
b5  b6  b7

./a4:

Seperti yang Anda lihat, itu berjalan lsdi folder dasar, dan kemudian semua folder anak. Dan semua folder cucu, tak terhingga. Secara efektif, perintah akan melalui setiap folder secara rekursif hingga menyentuh akhir pohon direktori. Pada titik itu, muncul kembali cabang di pohon dan melakukan hal yang sama untuk setiap sub-folder, jika ada.

Atau, dalam pseudo-code:

recursivelyList(directory) {
    files[] = listDirectory(directory)              // Get all files in the directory
    print(directory.name + ":\n" + files.join(" ")) // Print the "ls" output
    for (file : files) {                            // Go through all the files in the directory
        if (file.isDirectory()) {                   // Check if the current file being looked at is a directory
            recursivelyList(directory)              // If so, recursively list that directory
        }
    }
}

Dan karena saya bisa, referensi implementasi Java sama.

Sebenarnya, ada dua pertanyaan yang digabungkan erat yang mungkin Anda tanyakan.

• Mengapa proses berjalan ke setiap entri dalam hierarki sistem file merupakan proses yang bersifat rekursif? Ini ditujukan oleh jawaban lain, seperti Zanna dan Kaz Wolfe .
• Bagaimana teknik rekursi yang digunakan dalam implementasi ls? Dari ungkapan Anda ("Bagaimana rekursi digunakan dalam proses?"), Saya pikir ini adalah bagian dari apa yang ingin Anda ketahui. Jawaban ini menjawab pertanyaan itu.

Mengapa masuk akal untuk lsdiimplementasikan dengan teknik rekursif:

FOLDOC mendefinisikan rekursi sebagai:

Ketika suatu fungsi (atau prosedur ) memanggil dirinya sendiri. Fungsi seperti ini disebut "rekursif". Jika panggilan itu melalui satu atau lebih fungsi lain maka kelompok fungsi ini disebut "saling recursive".

Cara alami untuk mengimplementasikannya lsadalah dengan menulis fungsi yang membangun daftar entri sistem file yang akan ditampilkan, dan kode lain untuk memproses jalur dan argumen opsi dan untuk menampilkan entri yang diinginkan. Fungsi itu sangat mungkin diimplementasikan secara rekursif.

Selama pemrosesan opsi, lsakan menentukan apakah telah diminta untuk beroperasi secara rekursif (dengan dipanggil dengan -Rbendera). Jika demikian, fungsi yang membangun daftar entri yang akan ditampilkan akan memanggil dirinya sendiri satu kali untuk setiap direktori yang dicantumkannya, kecuali .dan ... Mungkin ada versi rekursif dan non rekursif yang terpisah dari fungsi ini, atau fungsi dapat memeriksa setiap kali jika seharusnya beroperasi secara rekursif.

Ubuntu /bin/ls, executable yang berjalan saat Anda menjalankan ls, disediakan oleh GNU Coreutils , dan memiliki banyak fitur. Akibatnya, kodenya agak lebih panjang dan lebih rumit dari yang Anda harapkan. Tetapi Ubuntu juga mengandung versi yang lebih sederhana ls, yang disediakan oleh BusyBox . Anda dapat menjalankan ini dengan mengetik busybox ls.

Cara busybox lsmenggunakan rekursi:

lsdi BusyBox diimplementasikan dalam coreutils/ls.c. Ini berisi scan_and_display_dirs_recur()fungsi yang dipanggil untuk mencetak pohon direktori secara rekursif:

static void scan_and_display_dirs_recur(struct dnode **dn, int first)
{
    unsigned nfiles;
    struct dnode **subdnp;

    for (; *dn; dn++) {
        if (G.all_fmt & (DISP_DIRNAME | DISP_RECURSIVE)) {
            if (!first)
                bb_putchar('\n');
            first = 0;
            printf("%s:\n", (*dn)->fullname);
        }
        subdnp = scan_one_dir((*dn)->fullname, &nfiles);
#if ENABLE_DESKTOP
        if ((G.all_fmt & STYLE_MASK) == STYLE_LONG || (G.all_fmt & LIST_BLOCKS))
            printf("total %"OFF_FMT"u\n", calculate_blocks(subdnp));
#endif
        if (nfiles > 0) {
            /* list all files at this level */
            sort_and_display_files(subdnp, nfiles);

            if (ENABLE_FEATURE_LS_RECURSIVE
             && (G.all_fmt & DISP_RECURSIVE)
            ) {
                struct dnode **dnd;
                unsigned dndirs;
                /* recursive - list the sub-dirs */
                dnd = splitdnarray(subdnp, SPLIT_SUBDIR);
                dndirs = count_dirs(subdnp, SPLIT_SUBDIR);
                if (dndirs > 0) {
                    dnsort(dnd, dndirs);
                    scan_and_display_dirs_recur(dnd, 0);
                    /* free the array of dnode pointers to the dirs */
                    free(dnd);
                }
            }
            /* free the dnodes and the fullname mem */
            dfree(subdnp);
        }
    }
}

Garis di mana panggilan fungsi rekursif berlangsung adalah:

                    scan_and_display_dirs_recur(dnd, 0);

Melihat fungsi rekursif panggilan saat terjadi:

Anda dapat melihat ini beroperasi jika Anda menjalankan busybox lsdebugger. Pertama instal simbol debug dengan mengaktifkan paket -dbgsym.ddeb dan kemudian instal busybox-static-dbgsympaket tersebut. Instal gdbjuga (itulah debugger).

sudo apt-get update
sudo apt-get install gdb busybox-static-dbgsym

Saya sarankan debugging coreutils lspada pohon direktori sederhana.

Jika Anda tidak memiliki satu yang berguna, buat satu (ini bekerja dengan cara yang sama seperti mkdir -pperintah dalam jawaban WinEunuuchs2Unix ):

mkdir -pv foo/{bar/foobar,baz/quux}

Dan isi dengan beberapa file:

(shopt -s globstar; for d in foo/**; do touch "$d/file$((i++))"; done)

Anda dapat memverifikasi busybox ls -R foopekerjaan seperti yang diharapkan, menghasilkan output ini:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

Buka busyboxdi debugger:

gdb busybox

GDB akan mencetak beberapa informasi tentang dirinya sendiri. Maka itu harus mengatakan sesuatu seperti:

Reading symbols from busybox...Reading symbols from /usr/lib/debug/.build-id/5c/e436575b628a8f54c2a346cc6e758d494c33fe.debug...done.
done.
(gdb)

(gdb)adalah prompt Anda di debugger. Hal pertama yang harus Anda beri tahu GDB untuk dilakukan pada prompt ini adalah mengatur breakpoint di awal scan_and_display_dirs_recur()fungsi:

b scan_and_display_dirs_recur

Saat Anda menjalankannya, GDB harus memberi tahu Anda sesuatu seperti:

Breakpoint 1 at 0x5545b4: file coreutils/ls.c, line 1026.

Sekarang beri tahu GDB untuk menjalankan busyboxdengan (atau nama direktori apa pun yang Anda inginkan) sebagai argumennya:ls -R foo

run ls -R foo

Anda mungkin melihat sesuatu seperti ini:

Starting program: /bin/busybox ls -R foo

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6c60, first=1) at coreutils/ls.c:1026
1026    coreutils/ls.c: No such file or directory.

Jika Anda melihat No such file or directory, seperti di atas, tidak apa-apa. Tujuan dari demonstrasi ini adalah hanya untuk melihat kapan scan_and_display_dirs_recur()fungsi telah dipanggil, jadi GDB tidak perlu memeriksa kode sumber yang sebenarnya.

Perhatikan bahwa debugger mencapai breakpoint bahkan sebelum entri direktori dicetak. Rusak di entrace untuk fungsi itu, tapi kode dalam fungsi yang harus dijalankan untuk setiap direktori yang akan dicacah untuk mencetak.

Untuk memberi tahu GDB untuk melanjutkan, jalankan:

c

Setiap kali scan_and_display_dirs_recur()dipanggil, breakpoint akan dipukul lagi, sehingga Anda akan melihat rekursi beraksi. Sepertinya ini (termasuk (gdb)prompt dan perintah Anda):

(gdb) c
Continuing.
foo:
bar    baz    file0

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cb0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/bar:
file1   foobar

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cf0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/bar/foobar:
file2

foo/baz:
file3  quux

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cf0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/baz/quux:
file4
[Inferior 1 (process 2321) exited normally]

Fungsi ini ada recurdalam namanya ... apakah BusyBox hanya menggunakannya ketika -Rbendera diberikan? Dalam debugger, ini mudah ditemukan:

(gdb) run ls foo
Starting program: /bin/busybox ls foo

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6c60, first=1) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.
bar    baz    file0
[Inferior 1 (process 2327) exited normally]

Bahkan tanpa -R, implementasi khusus ini lsmenggunakan fungsi yang sama untuk mencari tahu entri sistem file apa yang ada dan menunjukkannya.

Saat Anda ingin keluar dari debugger, katakan saja:

q

Bagaimana scan_and_display_dirs_recur()tahu jika itu harus menyebut dirinya:

Secara khusus bagaimana cara kerjanya berbeda ketika -Rbendera dilewatkan? Memeriksa kode sumber (yang mungkin bukan versi yang tepat pada sistem Ubuntu Anda) mengungkapkan bahwa ia memeriksa struktur data internal G.all_fmt, tempat ia menyimpan opsi apa yang telah dipanggil dengan:

            if (ENABLE_FEATURE_LS_RECURSIVE
             && (G.all_fmt & DISP_RECURSIVE)

(Jika BusyBox telah dikompilasi tanpa dukungan untuk -R, maka BusyBox juga tidak akan mencoba menampilkan entri sistem file secara rekursif; itulah ENABLE_FEATURE_LS_RECURSIVEbagian dari itu.)

Hanya ketika G.all_fmt & DISP_RECURSIVEbenar kode yang berisi panggilan fungsi rekursif dijalankan.

                struct dnode **dnd;
                unsigned dndirs;
                /* recursive - list the sub-dirs */
                dnd = splitdnarray(subdnp, SPLIT_SUBDIR);
                dndirs = count_dirs(subdnp, SPLIT_SUBDIR);
                if (dndirs > 0) {
                    dnsort(dnd, dndirs);
                    scan_and_display_dirs_recur(dnd, 0);
                    /* free the array of dnode pointers to the dirs */
                    free(dnd);
                }

Jika tidak, fungsi hanya berjalan sekali (per direktori ditentukan pada baris perintah).

Ketika Anda memikirkannya, "rekursif" masuk akal untuk perintah yang bekerja pada direktori dan file dan direktori mereka serta file dan direktori mereka serta file dan direktori serta file mereka .........

.... sampai seluruh pohon dari titik yang ditentukan turun telah dioperasikan oleh perintah, dalam hal ini daftar isi setiap subdirektori dari setiap subdirektori dari setiap subdirektori .......... yang ada di bawah argumen dari perintah

-R adalah untuk rekursi, yang secara longgar dapat disebut "berulang kali".

Ambil kode ini misalnya:

───────────────────────────────────────────────────────────────────────────────
$ mkdir -p temp/a
───────────────────────────────────────────────────────────────────────────────
$ mkdir -p temp/b/1
───────────────────────────────────────────────────────────────────────────────
$ mkdir -p temp/c/1/2
───────────────────────────────────────────────────────────────────────────────
$ ls -R temp
temp:
a  b  c

temp/a:

temp/b:
1

temp/b/1:

temp/c:
1

temp/c/1:
2

temp/c/1/2:

The -pdalam membuat direktori memungkinkan Anda untuk massa membuat direktori dengan satu perintah. Jika satu atau lebih direktori menengah atas sudah ada, itu bukan kesalahan dan direktori menengah bawah dibuat.

Kemudian ls -Rdaftar secara rekursif setiap direktori tunggal dimulai dengan temp dan bekerja dengan cara menuruni pohon ke semua cabang.

Sekarang mari kita lihat pelengkap ls -Rperintah, yaitu treeperintah:

$ tree temp
temp
├── a
├── b
│   └── 1
└── c
    └── 1
        └── 2

6 directories, 0 files

Seperti yang Anda lihat, treehasil yang sama dengan ls -Rkecuali lebih ringkas dan berani saya katakan "lebih cantik".

Sekarang mari kita lihat cara menghapus direktori yang baru saja kita buat dalam satu perintah sederhana:

$ rm -r temp

Ini secara rekursif menghapus tempdan semua sub-direktori di bawahnya. yaitu temp/a, temp/b/1dan temp/c/1/2ditambah direktori tengah di antaranya.

Inilah penjelasan sederhana, masuk akal karena ketika datang untuk menampilkan isi subdirektori, fungsi yang sama sudah tahu apa yang harus dilakukan dengan direktori. Oleh karena itu hanya perlu memanggil dirinya sendiri pada setiap subdirektori untuk mendapatkan hasil itu!

Dalam pseudocode terlihat seperti ini:

recursive_ls(dir)
    print(files and directories)
    foreach (directoriy in dir)
        recursive_ls(directory)
    end foreach
end recursive_ls