Dlaczego ls-R nazywa się „rekurencyjnym” listowaniem?

Rozumiem, że ls -Rwyświetla listę katalogów. Ale dlaczego jest rekurencyjny? Jak w tym procesie wykorzystywana jest rekurencja?

Po pierwsze, zdefiniujmy dowolną strukturę folderów:

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

Gdy to zrobimy ls, otrzymamy tylko dane wyjściowe folderu podstawowego:

a1 a2 a3 a4

Jednak kiedy dzwonimy ls -R, otrzymujemy coś innego:

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

Jak widać, działa lsw folderze podstawowym, a następnie we wszystkich folderach podrzędnych. I wszystkie foldery wnuka, ad infinitum. W efekcie polecenie rekurencyjnie przechodzi przez każdy folder, aż dotrze do końca drzewa katalogów. W tym momencie wraca do gałęzi drzewa i robi to samo dla wszystkich podfolderów, jeśli takie istnieją.

Lub w pseudokodzie:

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

A ponieważ mogę, referencyjna implementacja Java tego samego.

W efekcie możesz zadać dwa ściśle powiązane pytania.

• Dlaczego proces przejścia do każdego wpisu w hierarchii systemu plików jest z natury procesem rekurencyjnym? Zajmują się tym inne odpowiedzi, takie jak Zanna i Kaz Wolfe .
• W jaki sposób stosuje się technikę rekurencji przy realizacji ls? Z twojego sformułowania („W jaki sposób rekursja jest wykorzystywana w tym procesie?”), Myślę, że jest to część tego, co chcesz wiedzieć. Ta odpowiedź odpowiada na to pytanie.

Dlaczego warto lszastosować technikę rekurencyjną:

FOLDOC definiuje rekurencję jako:

Gdy funkcja (lub procedura ) wywołuje się. Taka funkcja nazywa się „rekurencyjną”. Jeśli połączenie odbywa się za pośrednictwem jednej lub więcej innych funkcji, wówczas ta grupa funkcji nazywana jest „wzajemnie rekurencyjnymi”.

Naturalnym sposobem implementacji lsjest napisanie funkcji, która konstruuje listę pozycji systemu plików, które mają zostać wyświetlone, oraz innego kodu do przetwarzania argumentów ścieżki i opcji oraz do wyświetlania pozycji według potrzeb. Jest wysoce prawdopodobne, że ta funkcja zostanie zaimplementowana rekurencyjnie.

Podczas przetwarzania opcji lsokreśli, czy został poproszony o działanie rekurencyjne (przez wywołanie z -Rflagą). Jeśli tak, funkcja, która tworzy listę wpisów do wyświetlenia, wywoła się jeden raz dla każdego katalogu, który zawiera, z wyjątkiem .i ... Mogą istnieć osobne wersje rekurencyjne i nierekurencyjne tej funkcji lub funkcja może za każdym razem sprawdzać, czy ma działać rekurencyjnie.

Ubuntu /bin/ls, plik wykonywalny, który działa podczas uruchamiania ls, jest dostarczany przez GNU Coreutils i ma wiele funkcji. W rezultacie jego kod jest nieco dłuższy i bardziej skomplikowany niż można się spodziewać. Ale Ubuntu zawiera również prostszą wersję ls, dostarczoną przez BusyBox . Możesz uruchomić to, pisząc busybox ls.

Jak busybox lswykorzystuje rekurencję:

lsw BusyBox jest zaimplementowany w coreutils/ls.c. Zawiera scan_and_display_dirs_recur()funkcję wywoływaną w celu rekurencyjnego drukowania drzewa katalogów:

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

Linia, w której odbywa się wywołanie funkcji rekurencyjnej, to:

                    scan_and_display_dirs_recur(dnd, 0);

Obserwowanie wywoływanych funkcji rekurencyjnych:

Możesz zobaczyć, jak działa, jeśli uruchomisz busybox lsdebugger. Najpierw zainstaluj symbole debugowania , włączając pakiety -dbgsym.ddeb, a następnie instalując busybox-static-dbgsympakiet. Zainstaluj gdbrównież (to jest debugger).

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

Sugeruję debugowanie coreutils lsw prostym drzewie katalogów.

Jeśli nie masz jednej poręcznej, stwórz ją (działa to tak samo jak mkdir -ppolecenie w odpowiedzi WinEunuuchs2Unix ):

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

I wypełnij go niektórymi plikami:

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

Możesz zweryfikować busybox ls -R fooprace zgodnie z oczekiwaniami, generując ten wynik:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

Otwórz busyboxw debuggerze:

gdb busybox

GDB wydrukuje niektóre informacje o sobie. To powinno powiedzieć coś takiego:

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

(gdb)jest twój monit w debuggerze. Pierwszą rzeczą, którą powiesz GDB, aby zrobiła to w tym monicie, jest ustawienie punktu przerwania na początku scan_and_display_dirs_recur()funkcji:

b scan_and_display_dirs_recur

Kiedy to uruchomisz, GDB powinien powiedzieć ci coś takiego:

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

Teraz powiedz GDB, aby działał busyboxz (lub jakąkolwiek nazwą katalogu) jako argumentami:ls -R foo

run ls -R foo

Możesz zobaczyć coś takiego:

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.

Jeśli widzisz No such file or directory, jak wyżej, to w porządku. Celem tej demonstracji jest tylko sprawdzenie, kiedy scan_and_display_dirs_recur()funkcja została wywołana, więc GDB nie musi sprawdzać faktycznego kodu źródłowego.

Zauważ, że debugger osiągnął punkt przerwania nawet przed wydrukowaniem jakichkolwiek pozycji katalogu. Łamie na wejscie do tej funkcji, ale kod w tej funkcji musi działać na wszystkie katalogi mają być wyliczone przy drukowaniu.

Aby powiedzieć GDB, aby kontynuował, uruchom:

c

Za każdym razem, gdy scan_and_display_dirs_recur()zostanie wywołane, punkt przerwania zostanie ponownie trafiony, dzięki czemu zobaczysz rekurencję w akcji. Wygląda to tak (w tym (gdb)monit i twoje polecenia):

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

Funkcja ma recurw nazwie ... czy BusyBox używa jej tylko wtedy, gdy -Rpodana jest flaga? W debuggerze łatwo to znaleźć:

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

Nawet bez -Rtej konkretnej implementacji lsużywa tej samej funkcji, aby dowiedzieć się, jakie wpisy systemu plików istnieją i je wyświetlić.

Kiedy chcesz wyjść z debuggera, po prostu powiedz:

q

Skąd scan_and_display_dirs_recur()wie, czy powinien się nazywać:

W szczególności, jak to działa inaczej po przekazaniu -Rflagi? Analiza kodu źródłowego (która może nie być dokładną wersją w systemie Ubuntu) ujawnia, że ​​sprawdza wewnętrzną strukturę danych G.all_fmt, w której przechowuje opcje , z którymi został wywołany:

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

(Jeśli BusyBox został skompilowany bez obsługi -R, to również nie będzie próbował rekurencyjnie wyświetlać wpisów systemu plików; o to chodzi w tej ENABLE_FEATURE_LS_RECURSIVEczęści.)

Tylko wtedy, gdy G.all_fmt & DISP_RECURSIVEjest to prawda, uruchamiany jest kod zawierający rekurencyjne wywołanie funkcji.

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

W przeciwnym razie funkcja jest uruchamiana tylko raz (dla katalogu określonego w wierszu poleceń).

Kiedy się nad tym zastanowić, „rekurencyjne” ma sens dla poleceń, które działają na katalogi i ich pliki i katalogi oraz ich pliki i katalogi oraz ich pliki i katalogi i ich pliki .........

.... dopóki całe drzewo od określonego punktu w dół nie będzie obsługiwane przez komendę, w tym przypadku wyświetlając zawartość wszystkich podkatalogów dowolnych podkatalogów dowolnych podkatalogów .......... argument (y) polecenia

-R służy do rekurencji, którą można luźno nazwać „wielokrotnie”.

Weźmy na przykład ten kod:

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

-pW tworzeniu katalogów pozwala na masowe tworzenie katalogów za pomocą jednego polecenia. Jeśli istnieje już jeden lub więcej górnych środkowych katalogów, nie oznacza to błędu i tworzone są środkowe dolne katalogi.

Następnie ls -Rrekurencyjnie wyświetla każdy katalog zaczynający się od temp i działający w dół drzewa do wszystkich gałęzi.

Teraz spójrzmy na uzupełnienie ls -Rpolecenia, tj. treePolecenie:

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

6 directories, 0 files

Jak widać treeosiąga się to samo, co ls -Rz wyjątkiem tego, że jest bardziej zwięzłe i ośmielę się powiedzieć „ładniejsze”.

Teraz spójrzmy, jak rekurencyjnie usuwać katalogi, które właśnie utworzyliśmy za pomocą jednego prostego polecenia:

$ rm -r temp

To rekurencyjnie usuwa tempi wszystkie podkatalogi poniżej. tzn temp/a, temp/b/1a temp/c/1/2także środkowe katalogi pomiędzy.

Oto proste wyjaśnienie, które ma sens, ponieważ jeśli chodzi o wyświetlanie zawartości podkatalogów, ta sama funkcja już wie, co zrobić z katalogiem. Dlatego po prostu musi wywołać się w każdym podkatalogu, aby uzyskać ten wynik!

W pseudokodzie wygląda to tak:

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