Como procurar eficientemente por uma lista de strings em um diretório de código grande

Question

Eu tenho uma lista de strings, para cada uma dessas strings, quero verificar se ocorre em um grande diretório de código fonte.

Eu vim para uma solução grep do GNU que me dá o que eu quero:

for key in $(cat /tmp/listOfKeys.txt); do
    if [ "$(grep -rio -m 1 "$key" . | wc -l)" = "0" ]; then
        echo "$key has no occurence"; 
    fi
done

No entanto, ele não é eficiente, pois sempre usa todos os arquivos do diretório, mesmo que encontre uma correspondência no início. Como há muitas chaves para pesquisar e praticamente arquivos para pesquisar, não é utilizável como está.

Você conhece uma maneira de fazer isso de forma eficiente com uma ferramenta unix "padrão"?

    

Answer 1

Pode pelo menos ser simplificado para:

set -f # needed if you're using the split+glob operator and don't want the
       # glob part

for key in $(cat /tmp/listOfKeys.txt); do
   grep -riFqe "$key" . ||
    printf '%s\n' "$key has no occurrence"
done

O qual pararia de pesquisar após a primeira ocorrência do key e não consideraria a chave como uma expressão regular (ou possível opção para grep ).

Para evitar a necessidade de ler arquivos várias vezes, e supondo que sua lista de chaves seja uma chave por linha (ao contrário de espaço / tabulação / nova linha separada no código acima), você poderia fazer com ferramentas GNU:

find . -type f -size +0 -printf '%p
find . -type f -size +0 -exec printf '%s
set -f # needed if you're using the split+glob operator and don't want the
       # glob part

for key in $(cat /tmp/listOfKeys.txt); do
   grep -riFqe "$key" . ||
    printf '%s\n' "$key has no occurrence"
done
' {} + | awk '
  step == 1 {ARGV[ARGC++] = $0; next}
  step == 2 {a[tolower($0)]; n++; next}
  {
    l = tolower($0)
    for (i in a) if (index(l, i)) {
      delete a[i]
      if (!--n) exit
    }
  }
  END {
    for (i in a) print i, "has no occurrence"
  }' step=1 RS='
find . -type f -size +0 -printf '%p
find . -type f -size +0 -exec printf '%s%pre%' {} + | awk '
  step == 1 {ARGV[ARGC++] = $0; next}
  step == 2 {a[tolower($0)]; n++; next}
  {
    l = tolower($0)
    for (i in a) if (index(l, i)) {
      delete a[i]
      if (!--n) exit
    }
  }
  END {
    for (i in a) print i, "has no occurrence"
  }' step=1 RS='%pre%' - step=2 RS='\n' /tmp/listOfKeys.txt step=3
' | awk '
  ARGIND == 2 {ARGV[ARGC++] = $0; next}
  ARGIND == 4 {a[tolower($0)]; n++; next}
  {
    l = tolower($0)
    for (i in a) if (index(l, i)) {
      delete a[i]
      if (!--n) exit
    }
  }
  END {
    for (i in a) print i, "has no occurrence"
  }' RS='%pre%' - RS='\n' /tmp/listOfKeys.txt
' - step=2 RS='\n' /tmp/listOfKeys.txt step=3
' | awk '
  ARGIND == 2 {ARGV[ARGC++] = $0; next}
  ARGIND == 4 {a[tolower($0)]; n++; next}
  {
    l = tolower($0)
    for (i in a) if (index(l, i)) {
      delete a[i]
      if (!--n) exit
    }
  }
  END {
    for (i in a) print i, "has no occurrence"
  }' RS='%pre%' - RS='\n' /tmp/listOfKeys.txt

Ele é otimizado porque irá parar de procurar por key assim que for visto e parará assim que todas as chaves forem encontradas e lerá os arquivos apenas uma vez.

Ele assume que as chaves são exclusivas em listOfKeys.txt . Ele irá mostrar as chaves em letras minúsculas.

Os GNUisms acima são -printf '%pARGIND' , awk e a capacidade de %code% de manipular registros delimitados por NUL. Os dois primeiros podem ser abordados com:

%pre%

O terceiro pode ser tratado com truques como este , mas provavelmente não vale a pena o esforço. Veja a solução de E / S de Descalços para uma maneira de contornar o problema completamente.

    

Answer 2

O GNU grep (assim como a maioria das variantes que eu conheço) oferece uma opção -f , que faz exatamente o que você precisa. A variante fgrep trata as linhas de entrada como strings comuns simples em vez de regexs.

fgrep -rio -f /tmp/listOfKeys.txt .

E se você quiser testar apenas se pelo menos uma correspondência for encontrada, adicione a opção -q . Por comentário de Stéphane, se você precisa saber quais strings não foram , adicione a opção -h e então canalize através deste idioma awk comum:

fgrep -h -rio -f /tmp/listOfKeys.txt . |
awk '{$0=tolower($0)}; !seen[$0]++' |
fgrep -v -i -x -f - /tmp/listOfKeys.txt

O segundo fgrep agora usa a primeira saída de fgrep (insira o caso uniqued), inverte o sentido e mostra sequências não correspondentes do arquivo de chaves.

    

Answer 3

Uma tradução portátil, em conformidade com POSIX, da abordagem gawk de Stéphane Chazelas:

find . -type f -exec cat {} + |
awk '
    FNR==NR {keys[tolower($0)]; n++; next}
    {
        s = tolower($0)
        for (k in keys) 
            if (index(s, k)) {
                delete keys[k]
                if (!--n)
                    exit
            }
    }
    END {
        for (k in keys) print k, "has no occurrence"
    }
' /tmp/listOfKeys.txt -

A menos que seus arquivos fonte sejam incomuns, pois seus nomes são consistentemente mais longos que seu conteúdo, a solução de Stéphane deve ser mais eficiente porque menos dados são canalizados (o que envolve a cópia entre buffers em dois processos via kernel).