Warum heißt ls -R "rekursive" Auflistung?

Ich verstehe, dass ls -Reine Liste von Verzeichnissen anzeigt. Aber warum ist es rekursiv? Wie wird dabei die Rekursion eingesetzt?

Definieren wir zunächst eine beliebige Ordnerstruktur:

.
├── 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]

In diesem lsFall erhalten wir nur die Ausgabe des Basisordners:

a1 a2 a3 a4

Wenn wir jedoch anrufen ls -R, bekommen wir etwas anderes:

.:
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:

Wie Sie sehen können, wird es lsauf dem Basisordner und dann auf allen untergeordneten Ordnern ausgeführt. Und alle Enkelordner, unendlich. Tatsächlich durchläuft der Befehl jeden Ordner rekursiv, bis er das Ende der Verzeichnisstruktur erreicht. Zu diesem Zeitpunkt wird ein Zweig in der Struktur wiederhergestellt und das Gleiche für alle Unterordner, sofern vorhanden.

Oder in Pseudocode:

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
        }
    }
}

Und weil ich kann, eine Referenz Java-Implementierung des gleichen.

Tatsächlich gibt es zwei eng gekoppelte Fragen, die Sie möglicherweise stellen.

• Warum ist der Prozess, zu jedem Eintrag in einer Dateisystemhierarchie zu gehen, von Natur aus ein rekursiver Prozess? Dies wird durch die anderen Antworten, wie Zanna's und Kaz Wolfe's, angesprochen .
• Wie wird die Technik der Rekursion bei der Umsetzung verwendet ls? Nach Ihrer Formulierung ("Wie wird die Rekursion in diesem Prozess verwendet?") Ist dies ein Teil dessen, was Sie wissen möchten. Diese Antwort beantwortet diese Frage.

Warum es sinnvoll lsist, mit einer rekursiven Technik implementiert zu werden:

FOLDOC definiert Rekursion als:

Wenn eine Funktion (oder Prozedur ) sich selbst aufruft. Eine solche Funktion heißt "rekursiv". Wenn der Aufruf über eine oder mehrere andere Funktionen erfolgt, wird diese Gruppe von Funktionen als "wechselseitig rekursiv" bezeichnet.

Die natürliche Art der Implementierung lsbesteht darin, eine Funktion zu schreiben, die eine Liste der anzuzeigenden Dateisystemeinträge und anderen Code erstellt, um Pfad- und Optionsargumente zu verarbeiten und die Einträge wie gewünscht anzuzeigen. Diese Funktion wird höchstwahrscheinlich rekursiv implementiert.

lsBestimmt während der Optionsverarbeitung, ob eine rekursive Operation angefordert wurde (durch Aufrufen mit dem -RFlag). In diesem Fall ruft sich die Funktion, die eine Liste der anzuzeigenden Einträge erstellt, einmal für jedes aufgeführte Verzeichnis auf, mit Ausnahme von .und ... Es kann separate rekursive und nicht rekursive Versionen dieser Funktion geben, oder die Funktion überprüft jedes Mal, ob sie rekursiv arbeiten soll.

Ubuntu's /bin/ls, die ausführbare Datei, die beim Ausführen ausgeführt wird ls, wird von GNU Coreutils bereitgestellt und verfügt über viele Funktionen. Infolgedessen ist der Code etwas länger und komplizierter als erwartet. Ubuntu enthält jedoch auch eine einfachere Version lsvon BusyBox . Sie können dies durch Eingabe ausführen busybox ls.

Wie busybox lsbenutzt man Rekursion:

lsin BusyBox ist implementiert in coreutils/ls.c. Es enthält eine scan_and_display_dirs_recur()Funktion, die aufgerufen wird, um einen Verzeichnisbaum rekursiv zu drucken:

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);
        }
    }
}

Die Zeile, in der der rekursive Funktionsaufruf stattfindet, lautet:

                    scan_and_display_dirs_recur(dnd, 0);

Anzeigen der rekursiven Funktionsaufrufe, wenn sie auftreten:

Sie können dies in Betrieb sehen, wenn Sie busybox lsin einem Debugger ausgeführt werden. Installieren Sie zuerst die Debugsymbole, indem Sie die Pakete -dbgsym.ddeb aktivieren und dann das busybox-static-dbgsymPaket installieren . Installieren Sie gdbauch (das ist der Debugger).

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

Ich empfehle das Debuggen coreutils lsin einem einfachen Verzeichnisbaum.

Wenn Sie keinen zur Hand haben, erstellen Sie einen (dies funktioniert genauso wie der mkdir -pBefehl in der Antwort von WinEunuuchs2Unix ):

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

Und füllen Sie es mit einigen Dateien:

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

Sie können überprüfen, ob die busybox ls -R fooArbeit wie erwartet ausgeführt wird, und die folgende Ausgabe erstellen:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

busyboxIm Debugger öffnen :

gdb busybox

GDB gibt einige Informationen über sich selbst aus. Dann sollte es ungefähr so ​​lauten:

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

(gdb)ist Ihre Eingabeaufforderung im Debugger. Das Erste, was Sie GDB an dieser Eingabeaufforderung mitteilen, ist das Festlegen eines Haltepunkts beim Start der scan_and_display_dirs_recur()Funktion:

b scan_and_display_dirs_recur

Wenn Sie das ausführen, sollte Ihnen GDB Folgendes mitteilen:

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

Nun teilen Sie GDB mit, dass es busyboxmit den folgenden Argumenten ausgeführt werden soll (oder mit welchem ​​Verzeichnisnamen auch immer):ls -R foo

run ls -R foo

Möglicherweise sehen Sie Folgendes:

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.

Wenn Sie No such file or directorywie oben sehen, ist das in Ordnung. Der Zweck dieser Demonstration ist nur zu sehen, wann die scan_and_display_dirs_recur()Funktion aufgerufen wurde, sodass GDB den tatsächlichen Quellcode nicht untersuchen muss.

Beachten Sie, dass der Debugger den Haltepunkt erreicht hat, noch bevor Verzeichniseinträge gedruckt wurden. Es bricht beim Zugriff auf diese Funktion ab, aber der Code in dieser Funktion muss ausgeführt werden, damit Verzeichnisse zum Drucken aufgelistet werden.

Führen Sie Folgendes aus, um GDB anzuweisen, fortzufahren:

c

Bei jedem scan_and_display_dirs_recur()Aufruf wird der Haltepunkt erneut erreicht, sodass Sie die Rekursion in Aktion sehen können. Es sieht so aus (einschließlich der (gdb)Eingabeaufforderung und Ihrer Befehle):

(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]

Die Funktion hat recurin ihrem Namen ... verwendet BusyBox sie nur, wenn das -RFlag gegeben ist? Im Debugger ist dies leicht herauszufinden:

(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]

Auch ohne -Rdiese spezielle Implementierung von lswird dieselbe Funktion verwendet, um herauszufinden, welche Dateisystemeinträge vorhanden sind, und um sie anzuzeigen.

Wenn Sie den Debugger beenden möchten, sagen Sie es einfach:

q

Woher scan_and_display_dirs_recur()weiß, ob es sich selbst nennen sollte:

Insbesondere wie funktioniert es anders, wenn das -RFlag übergeben wird? Das Untersuchen des Quellcodes (der möglicherweise nicht die genaue Version auf Ihrem Ubuntu-System ist) zeigt, dass er die interne Datenstruktur überprüft G.all_fmtund dort speichert, mit welchen Optionen er aufgerufen wurde:

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

(Wenn BusyBox ohne Unterstützung für kompiliert wurde -R, wird auch nicht versucht, Dateisystemeinträge rekursiv anzuzeigen. Darum geht es in diesem ENABLE_FEATURE_LS_RECURSIVETeil.)

Nur wenn G.all_fmt & DISP_RECURSIVEtrue ist, wird der Code ausgeführt, der den rekursiven Funktionsaufruf enthält.

                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);
                }

Andernfalls wird die Funktion nur einmal ausgeführt (pro in der Befehlszeile angegebenem Verzeichnis).

Wenn Sie darüber nachdenken, macht "rekursiv" Sinn für Befehle, die auf Verzeichnisse und deren Dateien und Verzeichnisse und deren Dateien und Verzeichnisse und deren Dateien und Verzeichnisse und deren Dateien wirken.

.... bis der gesamte Baum ab dem angegebenen Punkt vom Befehl bearbeitet wurde. In diesem Fall wird der Inhalt aller Unterverzeichnisse aller Unterverzeichnisse aller Unterverzeichnisse aufgeführt, die unter dem Befehl existieren Argument (e) des Befehls

-R steht für eine Rekursion, die locker "wiederholt" genannt werden könnte.

Nehmen Sie diesen Code zum Beispiel:

───────────────────────────────────────────────────────────────────────────────
$ 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:

Das -pErstellen von Verzeichnissen ermöglicht es Ihnen, Verzeichnisse mit einem einzigen Befehl zu erstellen. Wenn eines oder mehrere der Top-Middle-Verzeichnisse bereits vorhanden sind, liegt kein Fehler vor und die Middle-Lower-Verzeichnisse werden erstellt.

Dann ls -Rlistet das rekursiv jedes einzelne Verzeichnis auf, beginnend mit temp, und arbeitet es sich durch den Baum bis zu allen Zweigen.

Betrachten wir nun eine Ergänzung zum ls -RBefehl, dh den treeBefehl:

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

6 directories, 0 files

Wie Sie sehen können, treeleistet das Gleiche, als ls -Rsei es prägnanter und wage ich zu sagen "hübscher".

Schauen wir uns nun an, wie Sie die soeben erstellten Verzeichnisse mit einem einfachen Befehl rekursiv entfernen:

$ rm -r temp

Dadurch werden rekursiv tempalle darunter liegenden Unterverzeichnisse entfernt . dh temp/a, temp/b/1und temp/c/1/2zuzüglich der Mitte Verzeichnisse dazwischen.

Hier ist eine einfache Erklärung, die sinnvoll ist, da bei der Anzeige des Inhalts von Unterverzeichnissen dieselbe Funktion bereits weiß, was mit einem Verzeichnis zu tun ist. Daher muss es sich nur in jedem Unterverzeichnis selbst aufrufen, um dieses Ergebnis zu erhalten!

Im Pseudocode sieht es ungefähr so ​​aus:

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