Por que ls -R é chamado de listagem "recursiva"?

Question

Eu entendo que ls -R exibe uma listagem de diretórios. Mas por que é recursivo? Como a recursão é usada no processo?

    

Answer 1

Primeiro, vamos definir uma estrutura de pastas arbitrária:

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

Quando fazemos ls , obtemos apenas a saída da pasta base:

a1 a2 a3 a4

No entanto, quando chamamos ls -R , obtemos algo diferente:

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

Como você pode ver, ele está executando ls na pasta base e, em seguida, todas as pastas filhas. E todas as pastas netas, ad infinitum. Efetivamente, o comando está passando por cada pasta recursivamente até atingir o final da árvore de diretórios. Nesse ponto, ele volta por uma ramificação na árvore e faz o mesmo com qualquer subpasta, se houver.

Ou no pseudo-código:

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

E porque eu posso, uma referência à implementação Java do mesmo.

    

Answer 2

Existem, na verdade, duas perguntas bem parecidas que você pode estar fazendo.

• Por que o processo de caminhar para cada entrada em uma hierarquia de sistemas de arquivos é um processo inerentemente recursivo? Isto é endereçado pelas outras respostas, como Zanna's e Kaz Wolfe's .
• Como é a técnica de recursão usada na implementação de ls ? Do seu fraseado ("Como a recursão é usada no processo?"), Acho que isso é parte do que você quer saber. Esta resposta resolve essa questão.

Por que faz sentido que ls seja implementado com uma técnica recursiva:

FOLDOC define recursão como:

  

Quando uma função (ou procedimento ) chama-se. Tal função   é chamado de "recursivo". Se a chamada é através de uma ou mais outras funções   então este grupo de funções é chamado de "mutuamente recursivo".

A maneira natural de implementar ls é escrever uma função que construa uma lista de entradas do sistema de arquivos a serem exibidas e outro código para processar argumentos de caminho e opção e exibir as entradas conforme desejado. Essa função é altamente provável de ser implementada recursivamente.

Durante o processamento da opção, ls determinará se ele foi solicitado a operar recursivamente (sendo invocado com o sinalizador -R ). Nesse caso, a função que cria uma lista de entradas a serem exibidas se chamará uma vez para cada diretório listado, exceto . e .. . Pode haver versões recursivas e não-recursivas separadas desta função, ou a função pode verificar cada vez se é suposto estar operando recursivamente.

O /bin/ls do Ubuntu, o executável que é executado quando você executa ls , é fornecido por GNU Coreutils , e tem muitos recursos. Como resultado, seu código é um pouco mais longo e complicado do que você poderia esperar. Mas o Ubuntu também contém uma versão mais simples de ls , fornecida por BusyBox . Você pode executar isso digitando busybox ls .

Como busybox ls usa recursão:

ls no BusyBox é implementado em coreutils/ls.c . Ele contém uma função scan_and_display_dirs_recur() que é chamada para imprimir uma árvore de diretórios recursivamente:

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

A linha onde a chamada de função recursiva ocorre é:

                    scan_and_display_dirs_recur(dnd, 0);

Vendo as chamadas de função recursivas à medida que acontecem:

Você pode ver isso em operação se você executar busybox ls em um depurador. Primeiro instale os símbolos de depuração por ativando os pacotes -dbgsym.ddeb e instalando o pacote busybox-static-dbgsym . Instale gdb também (esse é o depurador).

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

Sugiro a depuração de coreutils ls em uma árvore de diretórios simples.

Se você não tiver um à mão, faça um (isso funciona da mesma maneira que o comando mkdir -p na resposta do WinEunuuchs2Unix ):

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

E preencha-o com alguns arquivos:

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

Você pode verificar se busybox ls -R foo funciona como esperado, produzindo esta saída:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

Abra busybox no depurador:

gdb busybox

O GDB imprimirá algumas informações sobre si mesmo. Então deveria dizer algo como:

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

(gdb) é o seu prompt no depurador. A primeira coisa que você vai dizer ao GDB para fazer neste prompt é definir um ponto de interrupção no início da função scan_and_display_dirs_recur() :

b scan_and_display_dirs_recur

Quando você executa isso, o GDB deve informar algo como:

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

Agora diga ao GDB para executar busybox com ls -R foo (ou qualquer nome de diretório que você queira) como seus argumentos:

run ls -R foo

Você pode ver algo assim:

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.

Se você vir No such file or directory , como acima, tudo bem. O objetivo desta demonstração é apenas para ver quando a função scan_and_display_dirs_recur() foi chamada, portanto, o GDB não precisa examinar o código-fonte real.

Observe que o depurador atingiu o ponto de interrupção mesmo antes de qualquer entrada de diretório ser impressa. Ele quebra na entrace para essa função, mas o código nessa função deve ser executado para quaisquer diretórios a serem enumerados para impressão.

Para dizer ao GDB para continuar, execute:

c

Sempre que scan_and_display_dirs_recur() for chamado, o ponto de interrupção será atingido novamente, assim você poderá ver a recursão em ação. Parece com isso (incluindo o prompt (gdb) e seus comandos):

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

A função tem recur em seu nome ... o BusyBox só usa quando o -R flag é dado?No depurador, isso é fácil de descobrir:

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

Mesmo sem -R , essa implementação específica de ls usa a mesma função para descobrir quais entradas do sistema de arquivos existem e mostrá-las.

Quando você quiser sair do depurador, basta informar:

q

Como o scan_and_display_dirs_recur() sabe se deve se chamar:

Especificamente, como funciona de maneira diferente quando o sinalizador -R é passado? Examinando o código fonte (que pode não ser o versão exata em seu sistema Ubuntu) revela que ele verifica sua estrutura de dados interna G.all_fmt , onde armazena as opções com as quais ele foi chamado:

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

(Se o BusyBox tiver sido compilado sem suporte para -R , ele também não tentará exibir as entradas do sistema de arquivos de forma recursiva; é disso que a parte ENABLE_FEATURE_LS_RECURSIVE é.)

Somente quando G.all_fmt & DISP_RECURSIVE é true, o código que contém a chamada de função recursiva é executado.

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

Caso contrário, a função é executada apenas uma vez (por diretório especificado na linha de comando).

    

Answer 3

Quando você pensa sobre isso, "recursivo" faz sentido para comandos que atuam em diretórios e seus arquivos e diretórios e seus arquivos e diretórios e seus arquivos e diretórios e seus arquivos .........

.... até que a árvore inteira do ponto especificado abaixo tenha sido operada pelo comando, neste caso listando o conteúdo de quaisquer subdiretórios de quaisquer subdiretórios de quaisquer subdiretórios .......... que existem sob o (s) argumento (s) do comando

    

Answer 4

-R é para recursão, que pode ser chamado de "repetidamente".

Pegue este código, por exemplo:

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

O -p em criar diretórios permite criar pastas em massa com um único comando. Se um ou mais dos diretórios top-middle já existirem, não é um erro e os diretórios do meio-baixo são criados.

Em seguida, o ls -R lista recursivamente todos os diretórios, começando com temp e trabalhando na árvore até todas as ramificações.

Agora vamos ver um complemento para o comando ls -R , ou seja, o comando tree :

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

6 directories, 0 files

Como você pode ver, tree realiza o mesmo que ls -R , exceto que é mais conciso e ouso dizer "mais bonito".

Agora vamos ver como remover recursivamente os diretórios que acabamos de criar em um comando simples:

$ rm -r temp

Isso recursivamente remove temp e todos os subdiretórios abaixo dele. ou seja, temp/a , temp/b/1 e temp/c/1/2 mais os diretórios intermediários entre eles.

    

Answer 5

Aqui está uma explicação simples, faz sentido, porque quando se trata de exibir o conteúdo de subdiretórios, a mesma função já sabe o que fazer com um diretório. Portanto, só precisa se chamar em cada subdiretório para obter esse resultado!

No pseudocódigo, parece algo assim:

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