Поиск копипасты и дублирования кода

Я тут подумал про zip. Там алгоритм тоже вроде повторяющиеся куски ищет.

Нагуглилось всякое, попробуй

simian

ccfinder

Первое проприетарное и нельзя коммерческое использования без покупки странных лицензий.

А второе пробовал, но оно странно работает. Похоже что вообще пропускает файлы больше определённого размера...

Первое проприетарное и нельзя коммерческое использования без покупки странных лицензий.

И что? Можно обнаружить использование этого инструмента в конечном коде? Если нет, то что мешает его поставить на свой комп? И да, его можно засунуть в виртуалку или в AppArmor/TOMOYO, если боишься side-эффектов.

а если самому навелосипедить?

грубо говоря:
1) проходим по всем исходникам, выдираем из них блоки { ... } в отдельные файлы
2) делаем diff -s каждого с каждым

делаем diff -s каждого с каждым

Ты серьёзно? Квадрат количества будет. А блоков много.

Вот здеаь http://stackoverflow.com/questions/546487/tools-to-identify-code-duplications

аналогичный вопрос и пачка неплохих ответов. http://sourceforge.net/projects/same/ — практически аналог решения на diff'ах, но правильно реализованное.

Вполне, я прекрасно себе представляю что это дофига сравнивать, но тем не менее.

да и не так много блоков. допустим проект: 50000 строк, каждая функция по 20 строк в среднем - 2500 функций, в каждой функции по десятку блоков, то есть 27500 блоков примерно. жить можно. много - миллионы и миллиарды.

27500^2 / 2 = 376 миллионов diff -s на 10-20 строк даёт 0.01 секунды.

Итого около 3 миллионов секунд.

И чо? Ты после такой тулзы будешь код рефакторить?

Код надо знать. Наизусть.

Ok. Я квадрат забыл в своих «расчётах», да.

Никто не говорит что надо обязательно diff -s делать :) я лишь принцип написал не претендующий на идел. У меня 0.002 секунды на файлах по 30 строк в среднем.

У тебя есть другой вариант?
Очевидно можно более оптимально сравнивать, не диффом, но принципиально будет то же. В любом случае будет сложность O(n^2), если дубликатов нет.

Кстати не n^2, а n*(n-1)/2 потому что если ты сравнил A и B, то B и A тебе сравнивать не надо, очевидно.

В любом случае будет сложность O(n^2), если дубликатов нет.

Неа.

1. Сортировка по размеру n log n 2. Сравниваем соседние с одинаковыми размерами (если таких много можно размер + crc32). Получаем порядка n сравнений.

согласен, тоже появлялись такие мысли оптимизировать. конечно нет смысла ВСЁ сравнивать.

Для Java довольно неплохая искалка есть в IDEA

diff то зачем запускать? Запуск процесса это дорогое удовольствие.

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

А вообще спросите у gadfly - он должен знать;-)

Смотри тулзы по анализу кода, там обычно куча всяких функций, должен быть и поиск копипасты, cppcheck например. Можешь посмотреть sonar, под него вроде есть и c++ плагин.

Хм, а вы какой IDE пользуетесь?