How to search efficiently for a list of strings in a big code directory

Question

I have a list of strings, for every of those strings, I want to check if it occurs in a big source code directory.

I came to a GNU grep solution that gives me what I want:

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

However, it's not efficient at all since it always grep every file of the directory, even if it finds a match early. Since there are a lot of keys to lookup, and pretty much files to search in, it is not usable as-is.

Do you know a way to do this efficiently with a "standard" unix tool?

Answer 1

It can at least be simplified to:

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

Which would stop searching after the first occurrence of the key and not consider the key as a regular expression (or possible option to grep).

To avoid having to read files several times, and assuming your list of keys is one key per line (as opposed to space/tab/newline separated in the code above), you could do with GNU tools:

find . -type f -size +0 -printf '%p\0' | 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='\0' - RS='\n' /tmp/listOfKeys.txt

It's optimised in that it will stop looking for a key as soon as it's seen it and will stop as soon as all the keys have been found and will read the files only once.

It assumes keys are unique in listOfKeys.txt. It will output the keys in lower case.

The GNUisms above are -printf '%p\0', ARGIND and the ability of awk to handle NUL delimited records. The first two can be addressed with:

find . -type f -size +0 -exec printf '%s\0' {} + | 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='\0' - step=2 RS='\n' /tmp/listOfKeys.txt step=3

The third one could be addressed with tricks like this one, but that's probably not worth the effort. See Barefoot IO's solution for a way to bypass the problem altogether.

Answer 2

GNU grep (as well as most variants I know of) offer a -f option, which does exactly what you need. The fgrep variant treats the input lines as plain ordinary strings instead of regex's.

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

And if you just want to test if at least one match is found, add -q option. Per Stéphane's comment, if you need to know which strings that were not found, add the -h option and then pipe through this common awk idiom:

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

The second fgrep now uses the first fgrep's ouput (uniqued case insensitively), inverts the sense, and shows non-matching strings from the keyfile.

Answer 3

A portable, POSIX-compliant translation of Stéphane Chazelas' gawk approach:

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 -

Unless your source files are unusual, in that their names are consistently longer than their content, Stéphane's solution should be more efficient because less data is piped (which involves copying between buffers in two processes via the kernel).