1
\$\begingroup\$

I'm writing a plugin to a text editor that will perform indexing of large code bases. The indexer will retrieve all function calls for a certain function (much like the functionality of full featured IDEs).

I know that using regex to parse languages is a terrible idea. However:

  • It should be as simple as possible, I'm not interested in the whole parse tree.
  • No external dependencies
  • It should be generic and apply to any language (at least any language with func(arg) syntax).

In addition, I thought it would be nice project to experiment with. I've wrote the following:

class Indexer(object):
    Entry = namedtuple('Entry', 'file line_number')
    def __init__(self):
        self.timestamp = 0
        self.file_index = defaultdict(list)
        self.index_pattern = re.compile(r'(\w+)(\([^\)]*\)?)')

    def index_folder(self, folder_path):
        file_generator = self.generate_files(folder_path)
        for file in file_generator:
            self.index_file(file)

    def generate_files(self, folder_path):
        for current_dir, subdirs, files in os.walk(folder_path):
            for file in files:
                current_file = os.path.join(current_dir, file)
                if os.path.getmtime(current_file) > self.timestamp:
                    yield current_file

    def index_file(self, file, reindex=False):
        with open(file, 'r') as input_file:
            try:
                for line_number, line in enumerate(input_file,1):
                    symbols = self.get_symbols_in_line(line)
                    file_entry = Indexer.Entry(file=file, line_number=line_number)
                    self.add_symbols_to_index(symbols, file_entry, reindex)
            except UnicodeDecodeError as excp:
                pass
                # no handling right now

    def get_symbols_in_line(self, line):
        matches = re.finditer(self.index_pattern, line)
        symbols = []
        for match in matches:
            symbols += self.recursive_match(match)
        return symbols

    def recursive_match(self, match):
        symbols = [match.group(1)]
        symbol_args = match.group(2)
        match = re.search(self.index_pattern, symbol_args)
        if not match:
            return symbols
        symbols += self.recursive_match(match)
        return symbols

    def add_symbols_to_index(self, symbols, file_entry, reindex=False):
        if reindex:
            remove_old_entries(symbols, file_entry)
        for symbol in symbols:
            self.file_index[symbol].append(file_entry)

    def remove_old_entries(self, symbol, file_entry):
        for symbol in symbols:                            
            filtred_list = [entry for entry in self.file_index[symbol]
                                if entry.file is not file_entry.file]
            self.file_index[symbol] = filtred_list

What I'm doing:

  1. Walking the directory
  2. Retrieving files that have been modified since the last timestamp
  3. Iterate lines on file, for each line regex out the function calls
  4. Update main index with symbols
  5. has support for reindexing on changes, let's leave it for now.

main index is a dict that holds lists of entries (tuples) like:

entry_tuple = (file, line_number)

    {
        symbol1: [entry_tuple1, entry_tuple2],
        symbol2: [entry_tuple3, entry_tuple4, entry_tuple5]
    }

After writing this working version I want to optimize it. Since I want it to perform well in my working environment (code base of ~70K files) I thought a good benchmark would be the linux kernel (~60K files).

It takes about 478 seconds to parse https://github.com/torvalds/linux I would happy for input about whether this a reasonable time to perform such a task and if my code has some eye-catching optimizations that could be done.

This is the cProfile output:

         233047655 function calls (232822795 primitive calls) in 479.651 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
 23940903  208.912    0.000  317.977    0.000 Indexer.py:60(get_line_symbols)
    59833   76.475    0.001  453.015    0.008 Indexer.py:37(index_file)
 28536924   40.481    0.000   43.472    0.000 re.py:273(_compile)
    59833   29.168    0.000   29.659    0.000 {built-in method open}
  4595915   21.966    0.000   21.966    0.000 {method 'search' of '_sre.SRE_Pattern' objects}
 23940903   18.539    0.000   18.539    0.000 {method 'finditer' of '_sre.SRE_Pattern' objects}
 23940903   14.066    0.000   66.482    0.000 re.py:210(finditer)
    60074   12.799    0.000   12.799    0.000 {built-in method stat}
 23940903    9.218    0.000   10.064    0.000 Indexer.py:48(add_symbols_to_index)
 23940903    9.153    0.000   16.337    0.000 <string>:12(__new__)
 23940921    7.184    0.000    7.184    0.000 {built-in method __new__ of type object at 0x000000001D92FD50}
    64038    6.148    0.000    6.148    0.000 {built-in method _isdir}
4595915/4392368    6.102    0.000   42.582    0.000 Indexer.py:67(recursive_match)
 29946141    3.456    0.000    3.457    0.000 {built-in method isinstance}
\$\endgroup\$
  • \$\begingroup\$ There's a problem with the indentation, please fix it. \$\endgroup\$ – Daniel Jun 26 '17 at 11:15
  • \$\begingroup\$ What is the problem? I'm using tab identation (4 spaces) \$\endgroup\$ – susdu Jun 26 '17 at 11:17
  • \$\begingroup\$ The code is indented correctly at base level, but your class contents are not indented further than base. \$\endgroup\$ – Daniel Jun 26 '17 at 11:19
  • \$\begingroup\$ OK, I've fixed it. \$\endgroup\$ – susdu Jun 26 '17 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.