Обнаружение клонов кода

Обнаружение клонов кода

Движок обнаружения клонов на основе AST, который находит дублированные и похожие фрагменты кода. Определяет 4 типа клонов — от точных копий до семантических клонов — используя сравнение токенов, структуры AST и потока управления.

Обзор

Обнаружение клонов находит скопированный или структурно похожий код в кодовой базе: - Безопасность: поиск скопированного уязвимого кода (например, небезопасные шаблоны strcpy) - Качество: снижение дублирования для упрощения поддержки - Рефакторинг: выявление кандидатов для извлечения общих функций

Типы клонов

Тип Название Метод обнаружения Порог по умолчанию
Тип 1 Точные Сходство токенов (Жаккар) 0.95
Тип 2 Переименованные Нормализованные токены (переменные/типы заменены заглушками) 0.80
Тип 3 Структурные Сходство последовательности структур AST 0.65
Тип 4 Семантические Сходство последовательности потока управления 0.60

Обнаружение выполняется по порядку — для каждой пары возвращается наивысший совпавший тип.

Справочник API

CloneResult

@dataclass
class CloneResult:
    method1_id: int              # ID первого метода в CPG
    method1_name: str            # Имя первого метода
    method1_file: str            # Файл:строка первого метода
    method2_id: int              # ID второго метода в CPG
    method2_name: str            # Имя второго метода
    method2_file: str            # Файл:строка второго метода
    similarity: float            # Оценка сходства 0.0-1.0
    clone_type: str              # 'exact', 'renamed', 'structural', 'semantic'
    shared_patterns: List[str]   # Общие шаблоны, например ['error_handling']
    line_count1: int             # Строк в первом методе
    line_count2: int             # Строк во втором методе

ASTCloneDetector

class ASTCloneDetector:
    def __init__(self, cpg_service):
        """Инициализация с CPGQueryService для доступа к базе данных."""

    def detect_clones(
        self,
        min_similarity: Optional[float] = None,  # По умолчанию: 0.7
        category: str = None,                     # Фильтр по категории
        max_methods: Optional[int] = None,        # По умолчанию: 200
        min_lines: Optional[int] = None,          # По умолчанию: 5
    ) -> List[CloneResult]:
        """
        Обнаружить клоны во всей кодовой базе.

        Возвращает:
            Список CloneResult, отсортированный по убыванию сходства
        """

    def detect_clones_for_category(
        self,
        category: str,
        min_similarity: Optional[float] = None,  # По умолчанию: 0.6
    ) -> List[CloneResult]:
        """
        Обнаружить клоны в рамках конкретной категории шаблонов.

        Аргументы:
            category: категория (например, 'error_handling', 'null_check')
        """

Использование

Базовое обнаружение

from src.analysis.clone_detector import ASTCloneDetector

detector = ASTCloneDetector(cpg_service)
clones = detector.detect_clones(min_similarity=0.7)

for clone in clones:
    print(f"[{clone.clone_type}] {clone.similarity:.0%}")
    print(f"  {clone.method1_name} ({clone.method1_file})")
    print(f"  {clone.method2_name} ({clone.method2_file})")
    print(f"  Общие шаблоны: {', '.join(clone.shared_patterns)}")

Обнаружение по категории

# Найти дублированный код обработки ошибок
clones = detector.detect_clones_for_category(
    category="error_handling",
    min_similarity=0.6
)

В рабочем процессе (сценарий S05 Рефакторинг)

Обнаружение клонов автоматически вызывается в сценарии рефакторинга, когда запрос упоминает дубликаты или клоны:

from src.analysis.clone_detector import ASTCloneDetector, detect_duplicate_category

# Автоопределение категории из запроса пользователя
category, patterns = detect_duplicate_category(query)
detector = ASTCloneDetector(cpg)
clones = detector.detect_clones_for_category(category, min_similarity=0.6)

Конфигурация

# config.yaml
clone_detection:
  min_similarity_strict: 0.7        # Порог общего обнаружения
  min_similarity_relaxed: 0.6       # Порог для категорий
  max_methods_standard: 200          # Анализируемых методов (стандартный режим)
  max_methods_extended: 300          # Анализируемых методов (расширенный режим)
  min_lines_for_clone: 5            # Минимальный размер метода (строки)
  patterns_limit: 3                  # Шаблонов на категорию
  clones_limit: 20                   # Максимум возвращаемых клонов

Категории шаблонов

Категория Примеры функций
null_check Проверки NULL/nullptr, ассерты
string_operations strlen, strcmp, strncpy, snprintf
error_handling Коды ошибок, исключения, errno
memory_allocation Шаблоны malloc, free, realloc
lock_management Мьютексы, атомарные операции
buffer_operations Чтение/запись буферов, memcpy

Категории загружаются из активного доменного плагина через domain.get_operation_categories(), что делает обнаружение клонов доменно-независимым.

Алгоритм

  1. Загрузка методов из CPG (фильтрация по min_lines, необязательной category)
  2. Попарное сравнение (O(n^2), ограничено max_methods): - Извлечение токенов, нормализованных токенов, структуры AST, потока управления - Вычисление метрик сходства по порядку:
    • Токены (Жаккар) > 0.95 → Тип 1 (точный)
    • Нормализованные токены > 0.80 → Тип 2 (переименованный)
    • Структура AST > 0.65 → Тип 3 (структурный)
    • Поток управления > 0.60 → Тип 4 (семантический)
  3. Фильтрация по порогу min_similarity
  4. Поиск общих шаблонов между методами
  5. Сортировка по убыванию сходства, ограничение clones_limit

Метрики сходства

Jaccard(A, B) = |A ∩ B| / |A ∪ B|          # Для множеств токенов
Sequence(A, B) = |Counter(A) ∩ Counter(B)| / |Counter(A) ∪ Counter(B)|  # Для последовательностей

Пример вывода

[renamed] 85% сходства
  validate_user (auth.c:45, 20 строк)
  verify_admin (admin.c:120, 22 строки)
  Общие шаблоны: null_check, error_handling

[structural] 72% сходства
  process_request (handler.c:89, 35 строк)
  handle_event (event.c:201, 38 строк)
  Общие шаблоны: error_handling, buffer_operations

Ограничения

  1. Сложность O(n^2) — ограничена max_methods (по умолчанию 200)
  2. Только на уровне методов — сравниваются целые методы, не произвольные блоки
  3. Разбор на основе шаблонов — токенизация через регулярные выражения
  4. Без межъязыкового анализа — клоны обнаруживаются только в пределах одного языка

Связанная документация

Модуль: src/analysis/clone_detector.py Последнее обновление: февраль 2026