Pourquoi ls -R est-il appelé "recursive" listing?

34

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?

    
posée Mint.K 23.01.2017 - 19:50
la source

5 réponses

66

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.

    
réponse donnée Kaz Wolfe 23.01.2017 - 19:59
la source
22

Il y a en fait deux questions étroitement liées que vous vous posez peut-être.

  • Pourquoi le processus de passage à chaque entrée d’une hiérarchie de systèmes de fichiers est-il intrinsèquement récursif? Ceci est abordé par les autres réponses, telles que Zanna et Kaz Wolfe's .
  • Comment la technique de récursivité est-elle utilisée dans l'implémentation de 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.

Pourquoi il est logique que 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 .

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

Voir les appels de fonction récursifs comme ils se produisent:

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

Comment 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).

    
réponse donnée Eliah Kagan 24.01.2017 - 08:48
la source
16

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éponse donnée Zanna 23.01.2017 - 19:58
la source
7

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

    
réponse donnée WinEunuuchs2Unix 24.01.2017 - 02:07
la source
5

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
    
réponse donnée TommyD 24.01.2017 - 21:55
la source

Lire d'autres questions sur les étiquettes