## 0.1 패키지 계층 구조 무결성을 위협하는 순환 참조 탐지 알고리즘 구체화

## 0.1 패키지 계층 구조 무결성을 위협하는 순환 참조 탐지 알고리즘 구체화

수십, 수백 개의 마이크로서비스 및 컴포넌트로 분할된 다중 패키지 아키텍처(Multi-package Architecture)에서는 개발자의 설계 오류나 모듈 간의 강결합(Tight Coupling)으로 인하여 패키지 간 순환 참조(Circular Dependency)가 발생할 위험성이 상존한다. 순환 참조란 패키지 A가 패키지 B에 의존하고, 패키지 B가 직간접적으로 다시 패키지 A에 의존하는 폐곡선(Closed Loop) 형태의 의존성 위상(Topological Phase)을 의미한다. 방향성 비순환 그래프(DAG) 기반 스케줄러인 Colcon 빌드 시스템에서 이러한 순환 참조가 탐지되지 못한 채 실행될 경우, 무한 대기 상태(Deadlock)에 빠져 시스템 전체의 빌드 파이프라인이 영구적으로 블로킹(Blocking)되는 치명적인 결함으로 이어진다.

0.1.1 강력한 연결 요소(Strongly Connected Component, SCC)의 정의

그래프 이론에서 순환 참조가 발생하는 부분 그래프(Subgraph)는 강력한 연결 요소(SCC, Strongly Connected Component)로 정의된다. 방향성 그래프 G = (V, E) 내에서 임의의 두 정점 u, v \in V에 대하여 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재한다면, 이 두 정점은 동일한 SCC에 속하게 된다.
Colcon 빌드 시스템의 스케줄링 모델은 정의상 순환 경로가 없는 DAG이어야 하므로, 모델 검증의 핵심은 스케줄러가 구성한 그래프 내에 크기가 2 이상인 SCC가 존재하는지 여부를 판별하는 수학적 증명 과정이다.

0.1.2 타잔 알고리즘(Tarjan’s Algorithm) 기반의 SCC 탐지 파이프라인

Colcon 코어는 위상 정렬을 수행하기 직전, 혹은 위상 정렬과 병행하여 그래프 내의 순환 구조를 효과적으로 탐지하기 위해 깊이 우선 탐색(DFS, Depth-First Search) 기반의 타잔 알고리즘(Tarjan’s strongly connected components algorithm) 또는 칸 알고리즘(Kahn’s algorithm)의 변형을 활용한다. 순환 참조 탐지의 구체적인 연산 과정은 다음과 같다.

  1. 방문(Visitation) 및 재귀적 추적:
    알고리즘은 임의의 시작 노드에서부터 출발하여 DFS를 재귀적으로 수행한다. 각 노드를 방문할 때마다 노드에 고유한 도착 시간(Discovery Time) 인덱스와 함께 ‘탐색 중(Visiting)’ 상태 플래그를 변이(State Mutation)시킨다.
  2. 역방향 간선(Back-edge) 식별:
    특정 노드 u에서 간선을 따라 다음 노드 v를 탐색할 때, 만일 v가 이미 재귀 호출 스택(Call Stack) 상에 존재하는, 즉 ’탐색 중’인 상태라면 해당 간선 (u, v)는 역방향 간선(Back-edge)으로 판별된다.
  3. 순환 그래프 격리 및 통지:
    역방향 간선이 단 하나라도 발견되는 순간, 이론적으로 해당 그래프는 DAG 모델이 될 수 없으며 하나 이상의 사이클을 포함하고 있음이 수학적으로 증명된다. Colcon은 발견 즉시 해당 DFS 호출 스택을 역추적(Backtracking)하여 순환 구조에 편입된 구체적인 패키지 명단(예: pkg_A -> pkg_B -> pkg_C -> pkg_A)을 수집하고, 빌드 초기화(Initialization) 단계를 강제 중단(Abort)함과 동시에 상세한 에러 트레이스백(Traceback)을 터미널 콘솔에 출력한다.

0.1.3 아키텍처 결함 판정 시의 해결 방법론(Resolution Methodology)

순환 참조 탐지 알고리즘에 의해 에러가 보고될 경우, 이는 시스템의 컴파일러 스택이나 Colcon 프레임워크 자체의 오류가 아니며, 사용자 워크스페이스 내 패키지 간의 아키텍처 설계 결함(Architectural Flaw)임을 의미한다. 이를 해결하기 위한 소프트웨어 공학적 접근은 크게 세 가지로 요약된다.

  • 메타데이터 명세 오류 수정: package.xml 내 <build_depend>와 <exec_depend>의 무분별한 선언 여부를 점검한다. 단순 헤더 참조만 필요한 경우 인터페이스 패키지를 분리하여 의존성 방향을 단방향(Unidirectional)으로 쇄신해야 한다.
  • 인터페이스(메시지/서비스) 패키지 분리: 두 기능적 패키지가 상호 참조하는 경우, 두 패키지가 공통으로 사용하는 msg, srv, action 파일이나 순수 가상 클래스(Pure Virtual Class)를 제3의 독립된 패키지로 분할하여 의존성 그래프의 진점(Sink Node)으로 계층화(Layering)하는 것이 ROS 2의 아키텍처 표준이다.
  • 플러그인 아키텍처 활용: 디자인 패턴 상의 제어 역전(IoC, Inversion of Control) 모델을 활용하여, C++의 pluginlib이나 Python의 entry_points 기반 동적 로딩으로 컴파일 시점(Compile-time)의 강결합을 런타임(Runtime) 시점의 느슨한 결합(Loose Coupling) 구조로 변환하여 순환 참조를 해소한다.

이처럼 Colcon의 순환 참조 탐지 알고리즘은 단순한 에러 검출 기능을 넘어, 개발자가 ROS 2의 분산 컴포넌트 철학에 부합하는 계층적 시스템 무결성을 유지하도록 유도하는 분석적 역할을 수행한다.