Магия Python в задаче вычисления количества строк комментариев в коде

Python - один из немногих языков программирования, в котором лаконичность и простота гармонирует с мощью кода, который можно на нем написать. Хотя по сути Python является императивным языком, в нем есть функциональные элементы, упрощающие разработку и придающие коду больше выразительности. И чтобы не быть голословным, хочу это показать на примере простой задачи.

Итак, есть следующая задача - подсчитать количество строк в C++ коде, в которых есть комментарии. Есть два метода решения этой задачи:

  1. Разработка state-машины, которая анализирует текущее состояние кода (комментарий это или нет) и ведет подсчет числа строчек, в которых состояние кода было "комментарий".
  2. Использовать регулярные выражения и подсчитать количество строк кода, которые удовлятворяли условиям в регулярном выражении.

Мы рассмотрим второе решение, т.к. оно будет более лаконично и читабельно. Плюс к тому же это может быть неплохой задачкой для собеседования. Если разработчик сможет написать решение примерно в таком же стиле, как будет описано ниже (и если, конечно, он не читал этот блог), то его можно смело принимать на работу :-)

Сначала приведу код, а потом мы его рассмотрим по шагам - от алгоритма до конкретных конструкций с необходимыми пояснениями:

""" C++ code comments parser module. """
import re


class CppCodeCommentsParser:
    """ C++ code comments parser class. """

    def __init__(self, code):
        self._code = code + '\n'
        self._lines = set()

    @property
    def comment_lines_count(self):
        """ Returns count of lines with comments in 'self._code'."""
        match_to_set = lambda m: set(xrange(*m.span()))
        re_iter = lambda expr: re.finditer(expr, self._code)

        code = list(enumerate(match_to_set(m) for m in re_iter('.*\n')))
        for m in re_iter('//(.*\\\s*\n)+.*\n|//.*\n|/\*(\n|.)*?\*/'):
            self._lines |= set(s[0] for s in code if match_to_set(m) & s[1])
        return len(self._lines)

Алгоритм решения данной задачи можно расписать по следующим шагам:

  1. Создаем массив множеств позиций символов в коде. Каждый элемент массива соответствует строчке кода.
  2. Проходимся регулярным выражением и находим все множества позиций символов в коде, которые являются комментариями.
  3. Считаем все строчки, которые имеют непустое пересечение с предыдущими множествами.

Это может звучать немного тяжеловато и заумно, но на самом деле все просто - мы просто считаем в каких строчках у нас появляются комментарии. Использование множеств для этого - достаточно логичное решение, т.к. если перейти от исходных сущностей (строчки кода и комментарии) к математической формализации (оперирировать позициями символов), то задача очень просто алгоритмизуется и программируется. Далее на примерах это будет рассмотрено более подробно.

Итак, первый шаг - конструирование объекта. Предполагается, что класс используется для анализа комментариев в коде, и одной из его функций является подсчет количества строчек с комментариями. Хотя, конечно, окончательно класс выглядел бы иначе, мы, основываясь на принципах TDD, не создаем лишних сущностей без надобности. Поэтому в конструкторе мы делаем всего лишь две вещи:

  • self._code = code + '\n' - Присваем члену класса нормализированную версию кода (под нормализацией подразумевается приведение кода к такому виду, когда последняя строчка в нем обязательно завершается символом перехода на новую строку).
  • self._lines = set() - Создаем пустое множество, которое потом заполним номерами строчек кода, в которых есть комментарии.

Теперь собственно, переходим к интересующему нас методу. Он оформлен в виде свойства, чтобы к нему можно было прозрачно обращаться (например, в будущем можно было бы кэшировать результат и не вычислять все заново - в таком случае семантика вызова не изменится, т.к. название свойства сохранило бы свой смысл).

В начале метода объявляются две лямбды - они позволяют избежать дублирования кода и сократить размер модуля. Лямбда - это анонимная функция, и в ней не могут содержаться императивные команды типа присваивания. Ближайший аналог лямбды - классическая функция в математике. Лямбда - это конструкция для создания анонимных функций, которые возвращают результат вычисления выражения, заданного в теле лямбды. Подробности см. в документации.

Первая лямбда match_to_set преобразует результат соответствия регулярного выражения в множество позиций символов. Приведу пример ее работы:

In [1]: m = type('', (object,), dict(span = lambda self: (1, 10)))()

In [2]: match_to_set = lambda m: set(xrange(*m.span()))

In [3]: match_to_set(m)
Out[3]: set([1, 2, 3, 4, 5, 6, 7, 8, 9])

Т.е. у нас есть объект (в данном случае m), у которого метод span() возвращает пару чисел. Лямбда разворачивает эту пару в последовательность и объединяет в множество.

Следующая лямбда re_iter просто возвращает итератор соответствий регулярного выражения в self._code. Например:

In [1]: import re

In [2]: code = '//first_line\n//second_line\nthird_line\n'

In [3]: re_iter = lambda expr: re.finditer(expr, code)

In [4]: [m.group() for m in re_iter('.*\n')]
Out[4]: ['//first_line\n', '//second_line\n', 'third_line\n']

Теперь собственно код. Сначала мы создаем массив множеств позиций символов в коде. Далее все будем рассматривать на примере вышеприведенной строчки кода:

In [1]: import re

In [2]: code = '//first_line\n//second_line\nthird_line\n'

In [3]: match_to_set = lambda m: set(xrange(*m.span()))

In [4]: re_iter = lambda expr: re.finditer(expr, code)

In [5]: list(enumerate(match_to_set(m) for m in re_iter('.*\n')))
Out[5]:
[(0, set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])),
 (1, set([13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26])),
 (2, set([32, 33, 34, 35, 36, 37, 27, 28, 29, 30, 31]))]

Как видите, мы получили массив из двухэлементных кортежей. В первом элементе кортежа хранится номер строчки (фактически, это номер соответствия регулярного выражения в исходной строке). Во втором элементе кортежа хранится собственно множество позиций символов.

Далее мы вычисляем позиции символов с комментариями. Код практически такой же, только другое регулярное выражение и выходные данные:

In [6]: [m.group() for m in re_iter('//(.*\\\s*\n)+.*\n|//.*\n|/\*(\n|.)*?\*/')]
Out[6]: ['//first_line\n', '//second_line\n']

Ну и наконец, пересечение множеств. Здесь на самом деле одновременно выполняется много операций, поэтому просто распишу по порядку:

  1. s[0] for s in code - Выбираем все номера строк из первых элементов кортежей code.
  2. if match_to_set(m) & s[1] - Дополняем выборку условием, что пересечение множеств соответствия регулярного выражения и символов в строке непустое.
  3. set(s[0] for s in code if match_to_set(m) & s[1]) - Объединяем все выбранные номера строк в множество.
  4. self._lines |= set(...) - Объединяем два множества.

В результате всей этой магии и шаманства мы получаем искомый результат - количество строк кода с комментариями (len(self._lines)).

Если у вас возникнут вопросы, замечания или предложения - пишите. Удачного программирования!

DOWNLOAD: parser.zip (1,37KB)

Comments

  1. У тебя небольшая терминологическая путаница:

    > Лямбда - это анонимная функция, и в ней не могут содержаться
    > императивные команды типа присваивания.

    Прекрасно могут:

    >>> def f(a):
    ... print a
    ... return a
    ...
    >>> (lambda x: f(x))(1)
    1
    1

    Правильнее сказать, что тело (питоновской) лямбды должно состоять
    из (питоновского) выражения (expression). Поэтому например
    'lambda x : print x' нелегальна чисто грамматически, поскольку
    'print x' это statement (см. language reference). К сайд-эффектам
    и императивности это всё отношения не имеет. В Лиспе и Руби и
    этого ограничения нет, лямбды это просто анонимные функции.

    > Ближайший аналог лямбды - классическая функция в математике.

    Ненене, аналог математической функции это чистая(pure) функция
    без посторонних эффектов (side effects), причем ей ничто не
    мешает быть именованной.

    ReplyDelete
  2. Да, что-то я намудрил - посыпаю голову пеплом. Вообще, адекватное и простое объяснение термина лямбды как-то даже не приходит в голову, хотя само по себе это элементарнейшая вещь :-) В документации и то какое-то не особо внятное объяснение.

    Я немного подправил текст, может теперь более ясно будет. По сути, можно было вообще не писать расшифровку термина - предполагается более или менее нормальное знание питона. Я уж не говорю о конструкции вида:

    m = type('', (object,), dict(span = lambda self: (1, 10)))()

    Те, кто смог разобраться что она делает, честь и хвала - им уж точно не нужно объяснять что такое лямбды :-)

    ReplyDelete

Post a Comment

Popular posts from this blog

Web application framework comparison by memory consumption

Trac Ticket Workflow

Shellcode detection using libemu