Pourquoi ls -R est-il appelé liste «récursive»?

Je comprends que ls -Raffiche une liste de répertoires. Mais pourquoi est-ce récursif? Comment la récursivité est-elle utilisée dans le processus?

Tout d’abord, définissons une structure de dossiers arbitraire:

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

Lorsque nous le faisons ls, nous obtenons la sortie du dossier de base uniquement:

a1 a2 a3 a4

Cependant, lorsque nous appelons ls -R, nous obtenons quelque chose de différent:

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

Comme vous pouvez le constater, il s’exécute lssur le dossier de base, puis sur tous les dossiers enfants. Et tous les dossiers de petits-enfants, ad infinitum. En réalité, la commande parcourt chaque dossier de manière récursive jusqu'à ce qu'il atteigne la fin de l'arborescence. À ce stade, il revient dans une branche de l'arborescence et fait la même chose pour tous les sous-dossiers, le cas échéant.

Ou, en 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
        }
    }
}

Et parce que je peux, une implémentation Java de référence de la même chose.

En réalité, vous pouvez poser deux questions étroitement liées.

• Pourquoi le processus consistant à accéder à chaque entrée dans une hiérarchie de système de fichiers est-il un processus intrinsèquement récursif? Ceci est traité par les autres réponses, telles que celles de Zanna et de Kaz Wolfe .
• Comment la technique de récursion est-elle utilisée dans la mise en œuvre ls? D'après votre phrasé ("Comment la récursion est-elle utilisée dans le processus?"), Je pense que cela fait partie de ce que vous voulez savoir. Cette réponse répond à cette question.

Pourquoi il est logique lsde mettre en œuvre avec une technique récursive:

FOLDOC définit la récursion comme:

Quand une fonction (ou une procédure ) s’appelle. Une telle fonction est appelée "récursive". Si l'appel se fait via une ou plusieurs autres fonctions, ce groupe de fonctions est appelé "mutuellement récursif".

La manière naturelle d'implémenter lsest d'écrire une fonction qui construit une liste d'entrées du système de fichiers à afficher, ainsi qu'un autre code permettant de traiter les arguments de chemin et d'option et d'afficher les entrées à votre guise. Cette fonction est hautement susceptible d'être implémentée de manière récursive.

Pendant le traitement des options, lsdéterminera s'il a été demandé à l'opération récursive (en étant appelé avec l' -Rindicateur). Si tel est le cas, la fonction qui crée une liste d'entrées à afficher s'appellera une fois pour chaque répertoire répertorié, à l'exception de .et ... Il peut y avoir des versions distinctes récursives et non récursives de cette fonction, ou la fonction peut vérifier chaque fois si elle est supposée fonctionner de manière récursive.

Ubuntu /bin/ls, l'exécutable qui s'exécute lorsque vous l'exécutez ls, est fourni par GNU Coreutils et comporte de nombreuses fonctionnalités. En conséquence, son code est un peu plus long et plus compliqué que prévu. Mais Ubuntu contient également une version simplifiée de ls, fournie par BusyBox . Vous pouvez exécuter ceci en tapant busybox ls.

Comment busybox lsutilise la récursivité:

lsdans BusyBox est implémenté dans coreutils/ls.c. Il contient une scan_and_display_dirs_recur()fonction appelée pour imprimer une arborescence de répertoires de manière récursive:

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

La ligne où l'appel de fonction récursif a lieu est la suivante:

                    scan_and_display_dirs_recur(dnd, 0);

Voir les appels de fonction récursifs au fur et à mesure qu'ils se produisent:

Vous pouvez le voir en opération si vous exécutez busybox lsun débogueur. Commencez par installer les symboles de débogage en activant les packages -dbgsym.ddeb, puis en installant le busybox-static-dbgsympackage. Installez gdbaussi bien (c'est le débogueur).

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

Je suggère de déboguer coreutils lssur une arborescence de répertoires simple.

Si vous n'en avez pas, créez-en un (cela fonctionne de la même manière que la mkdir -pcommande dans la réponse de WinEunuuchs2Unix ):

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

Et remplissez-le avec quelques fichiers:

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

Vous pouvez vérifier les busybox ls -R footravaux comme prévu en produisant cette sortie:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

Ouvrir busyboxdans le débogueur:

gdb busybox

GDB imprimera des informations sur lui-même. Ensuite, il devrait dire quelque chose comme:

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

(gdb)est votre invite dans le débogueur. La première chose à faire à GDB à cette invite est de définir un point d'arrêt au début de la scan_and_display_dirs_recur()fonction:

b scan_and_display_dirs_recur

Lorsque vous lancez cela, GDB devrait vous dire quelque chose comme:

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

Maintenant, indiquez à GDB de s’exécuter busyboxavec (ou le nom de répertoire de votre choix) comme arguments:ls -R foo

run ls -R foo

Vous pouvez voir quelque chose comme ça:

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.

Si vous voyez No such file or directory, comme ci-dessus, c'est bon. Le but de cette démonstration est simplement de voir quand la scan_and_display_dirs_recur()fonction a été appelée, ainsi GDB n'a pas besoin d'examiner le code source réel.

Notez que le débogueur a atteint le point d'arrêt avant même que les entrées du répertoire aient été imprimées. Il se rompt sur l' entrée de cette fonction, mais le code de cette fonction doit être exécuté pour que tous les répertoires soient énumérés pour l'impression.

Pour dire à GDB de continuer, exécutez:

c

Chaque fois que vous scan_and_display_dirs_recur()appelez, le point d'arrêt sera touché à nouveau afin que vous puissiez voir la récursion en action. Cela ressemble à ceci (y compris l' (gdb)invite et vos commandes):

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

La fonction a recurdans son nom ... BusyBox ne l'utilise-t-elle que lorsque le -Rdrapeau est donné? Dans le débogueur, il est facile de savoir:

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

Même sans -R, cette implémentation particulière de lsutilise la même fonction pour rechercher les entrées de système de fichiers existantes et les afficher.

Lorsque vous voulez quitter le débogueur, dites-lui simplement:

q

Comment scan_and_display_dirs_recur()savoir s'il devrait s'appeler lui-même:

En particulier, comment cela fonctionne-t-il différemment lorsque le -Rdrapeau est passé? L'examen du code source (qui peut ne pas être la version exacte sur votre système Ubuntu) révèle qu'il vérifie sa structure de données interne G.all_fmt, où il stocke les options avec lesquelles il a été appelé:

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

(Si BusyBox a été compilé sans support -R, il ne tentera pas non plus d'afficher les entrées du système de fichiers de manière récursive; c'est ce dont il s'agit dans la ENABLE_FEATURE_LS_RECURSIVEpartie.)

Le G.all_fmt & DISP_RECURSIVEcode contenant l'appel de fonction récursif n'est exécuté que lorsque true est utilisé.

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

Sinon, la fonction ne s'exécute qu'une fois (par répertoire spécifié sur la ligne de commande).

Quand vous y réfléchissez, "récursif" est logique pour les commandes qui agissent sur les répertoires et leurs fichiers et les répertoires et leurs fichiers et répertoires et leurs fichiers et répertoires et leurs fichiers .........

.... jusqu’à ce que l’arbre entier, à partir du point spécifié, ait été utilisé par la commande, répertoriant dans ce cas le contenu des sous-répertoires de tous les sous-répertoires de tous les sous-répertoires .......... existant sous le répertoire argument (s) de la commande

-R est pour la récursion, qui pourrait être appelé "à plusieurs reprises".

Prenons ce code par exemple:

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

La -pcréation de répertoires vous permet de créer en masse des répertoires avec une seule commande. Si un ou plusieurs des répertoires du milieu en haut existent déjà, ce n'est pas une erreur et les répertoires du milieu en bas sont créés.

Ensuite, la ls -Rliste récursive répertorie chaque répertoire, en commençant par temp, puis en descendant dans l’arbre, jusqu’à toutes les branches.

Regardons maintenant un complément à la ls -Rcommande, c’est-à-dire la treecommande:

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

6 directories, 0 files

Comme vous pouvez le voir, treela même chose ls -Rest faite, sauf que c'est plus concis et que j'ose dire "plus joli".

Voyons maintenant comment supprimer de manière récursive les répertoires que nous venons de créer en une seule commande:

$ rm -r temp

Cela supprime récursivement tempet tous les sous-répertoires qu'il contient. c'est-à temp/a- dire , temp/b/1et temp/c/1/2plus les répertoires intermédiaires entre les deux.

Voici une explication simple, qui a du sens, car lorsqu’il s’agit d’afficher le contenu des sous-répertoires, la même fonction sait déjà quoi faire avec un répertoire. Par conséquent, il suffit de s’appeler sur chaque sous-répertoire pour obtenir ce résultat!

En pseudo-code, cela ressemble à ceci:

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