Je comprends que ls -R affiche 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 faisons ls , nous n'obtenons que la sortie du dossier de base:
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 voir, il exécute ls sur le dossier de base, puis tous les dossiers enfants. Et tous les dossiers de petits-enfants, à l'infini. Effectivement, la commande parcourt chaque dossier de manière récursive jusqu’à la fin de l’arborescence. À ce stade, il crée une branche dans l’arbre 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 référence à l’implémentation Java de la même manière.
Il y a en fait deux questions étroitement liées que vous vous posez peut-être.
ls ? D'après votre formulation ("Comment la récursivité 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. ls soit implémenté avec une technique récursive: FOLDOC définit récursivité as:
Lorsqu'une fonction (ou procédure ) appelle lui-même. Une telle fonction est appelé "récursif". Si l'appel passe par une ou plusieurs autres fonctions alors ce groupe de fonctions est appelé "mutuellement récursif".
La manière naturelle d'implémenter ls est d'écrire une fonction qui construit une liste d'entrées de système de fichiers à afficher, et un autre code pour traiter les arguments de chemin d'accès et d'option et pour afficher les entrées souhaitées. Cette fonction est très susceptible d'être implémentée de manière récursive.
Au cours du traitement de l’option, ls déterminera s’il a été invité à fonctionner de manière récursive (en étant appelé avec l’indicateur -R ). Si tel est le cas, la fonction qui crée une liste d'entrées à afficher se nommera une fois pour chaque répertoire qu'elle répertorie, sauf . et .. . Il peut exister des versions récursives et non récursives distinctes de cette fonction, ou la fonction peut vérifier à chaque fois si elle est supposée fonctionner de manière récursive.
/bin/ls d'Ubuntu, l'exécutable qui s'exécute lorsque vous exécutez ls , est fourni par GNU Coreutils , et il a plusieurs fonctionnalités. Par conséquent, son code est un peu plus long et plus compliqué que vous. pourrait s'attendre. Mais Ubuntu contient également une version simplifiée de ls , fournie par BusyBox . vous pouvez exécuter ceci en tapant busybox ls .
busybox ls utilise la récursivité: ls dans BusyBox est implémenté dans coreutils/ls.c . Il contient une fonction scan_and_display_dirs_recur() appelée pour imprimer récursivement une arborescence de répertoires:
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écursive a lieu est:
scan_and_display_dirs_recur(dnd, 0);
Vous pouvez voir cela en fonctionnement si vous exécutez busybox ls dans un débogueur. Installez d’abord les symboles de débogage en activation des packages -dbgsym.ddeb , puis installation du package busybox-static-dbgsym . Installez également gdb (c'est le débogueur).
sudo apt-get update
sudo apt-get install gdb busybox-static-dbgsym
Je suggère de déboguer coreutils ls sur une arborescence de répertoires simple.
Si vous n'en avez pas à portée de main, créez-en un (cela fonctionne de la même manière que la commande mkdir -p dans la réponse de WinEunuuchs2Unix ):
mkdir -pv foo/{bar/foobar,baz/quux}
Et le remplir avec des fichiers:
(shopt -s globstar; for d in foo/**; do touch "$d/file$((i++))"; done)
Vous pouvez vérifier que busybox ls -R foo fonctionne 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
Ouvrez busybox dans le débogueur:
gdb busybox
GDB imprimera des informations sur lui-même. Alors ça 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 que vous demanderez à GDB de faire à cette invite est de définir un point d'arrêt au début de la fonction scan_and_display_dirs_recur() :
b scan_and_display_dirs_recur
Lorsque vous exécutez cela, GDB devrait vous dire quelque chose comme:
Breakpoint 1 at 0x5545b4: file coreutils/ls.c, line 1026.
Dites maintenant à GDB d’exécuter busybox avec ls -R foo (ou tout autre nom de répertoire que vous voulez) comme arguments:
run ls -R foo
Vous pouvez voir quelque chose comme ceci:
Starting program: /bin/busybox ls -R foo
Breakpoint 1, scan_and_display_dirs_recur ([email protected]=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, ça va. Le but de cette démonstration est juste de voir quand la fonction scan_and_display_dirs_recur() a été appelée, donc 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 l’impression des entrées du répertoire. Il brise l’entrée sur cette fonction, mais le code de cette fonction doit être exécuté pour que tous les répertoires soient énumérés pour impression.
Pour dire à GDB de continuer, lancez:
c
Chaque fois que scan_and_display_dirs_recur() est appelé, le point d'arrêt sera frappé à nouveau, vous verrez donc la récursivité en action. Cela ressemble à ceci (y compris l'invite (gdb) et vos commandes):
(gdb) c
Continuing.
foo:
bar baz file0
Breakpoint 1, scan_and_display_dirs_recur ([email protected]=0x7e6cb0, [email protected]=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 ([email protected]=0x7e6cf0, [email protected]=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 ([email protected]=0x7e6cf0, [email protected]=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 recur dans son nom ... BusyBox l’utilise-t-elle uniquement lorsque l’indicateur -R 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 ([email protected]=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 ls utilise la même fonction pour trouver les entrées du système de fichiers et les afficher.
Lorsque vous souhaitez quitter le débogueur, dites-le simplement:
q
scan_and_display_dirs_recur() sait s’il doit se nommer: En particulier, comment cela fonctionne-t-il différemment lorsque l’indicateur -R est passé? Examiner le code source (qui peut ne pas être le la version exacte de votre système Ubuntu) révèle qu’elle vérifie sa structure de données interne G.all_fmt , où sont stockées les options avec lesquelles elle a été appelée:
if (ENABLE_FEATURE_LS_RECURSIVE
&& (G.all_fmt & DISP_RECURSIVE)
(Si BusyBox a été compilé sans la prise en charge de -R , il ne tentera pas non plus d’afficher les entrées du système de fichiers de manière récursive, ce qui correspond à la partie ENABLE_FEATURE_LS_RECURSIVE .)
Ce n’est que lorsque G.all_fmt & DISP_RECURSIVE est vrai que le code contenant l’appel à la fonction récursive est exécuté.
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 s'exécute juste une fois (par répertoire spécifié sur la ligne de commande).
Quand on y pense, "récursif" a du sens pour les commandes qui agissent sur les répertoires et leurs fichiers et répertoires et leurs fichiers et répertoires ainsi que leurs fichiers et répertoires et leurs fichiers .........
… jusqu’à ce que l’arborescence complète à partir du point spécifié ait été activée par la commande, dans ce cas la liste du contenu de tous les sous-répertoires de tous les sous-répertoires de tous les sous-répertoires .......... existe sous les arguments de la commande
-R est pour la récursivité, ce qui pourrait être appelé "plusieurs fois".
Prenez 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:
Le -p dans la cré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 de premier niveau existent déjà, ce n'est pas une erreur et les répertoires intermédiaires sont créés.
Ensuite, ls -R répertorie de manière récursive tous les répertoires commençant par temp et fonctionnant de manière descendante dans toutes les branches.
Maintenant, regardons le complément de la commande ls -R , c’est-à-dire la commande tree :
$ tree temp
temp
├── a
├── b
│ └── 1
└── c
└── 1
└── 2
6 directories, 0 files
Comme vous pouvez le voir, tree accomplit la même chose que ls -R , sauf qu’il est plus concis et ose que je dis plus joli.
Voyons maintenant comment supprimer de manière récursive les répertoires que nous venons de créer en une simple commande:
$ rm -r temp
Cela supprime récursivement temp et tous les sous-répertoires situés en dessous. c.-à-d. temp/a , temp/b/1 et temp/c/1/2 plus les répertoires intermédiaires entre les deux.
Voici une explication simple, cela a du sens car quand 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, il ressemble à ceci:
recursive_ls(dir)
print(files and directories)
foreach (directoriy in dir)
recursive_ls(directory)
end foreach
end recursive_ls
Lire d'autres questions sur les étiquettes command-line ls