## 0.1 `package.xml` 의존성 선언 파싱을 통한 위상 정렬 정규화 모델 구성

## 0.1 package.xml 의존성 선언 파싱을 통한 위상 정렬 정규화 모델 구성

ROS 2 빌드 파이프라인에서 Colcon이 다수의 패키지를 안전하게 병렬 처리하기 위해서는 워크스페이스 내에 존재하는 모든 패키지들 간의 상호 의존 관계를 수학적인 위상 정렬(Topological Sort) 모델로 정규화하는 과정이 선행되어야 한다. 이 과정의 핵심 인터페이스 역할을 수행하는 것이 메타데이터 명세서인 package.xml 파일이다. Colcon은 package.xml을 파싱하여 정적 분석(Static Analysis)을 수행하고, 이를 기반으로 전체 시스템의 빌드 스케줄링 기초 모델인 방향성 비순환 그래프(DAG)를 구성한다.

0.1.1 패키지 메타데이터 추상화 및 파싱 파이프라인

작업 스케줄링의 1단계는 파일 시스템 순회(Filesystem Traversal)를 통한 패키지 디스커버리 체계에서 시작된다. Colcon 코어는 지정된 디렉터리 하의 모든 package.xml 문서를 식별하고, 내장된 XML 파서(Parser)를 통해 문서 객체 모델(DOM)을 생성한다.

파서는 모델 구축을 위해 다음의 핵심 태그 정보들을 추출한다:

  • <name>: 패키지의 고유 식별자(Identifier)
  • <build_depend>: 컴파일 시점(Compile-time)에 헤더 파일 포함(Header inclusion) 및 라이브러리 심볼 링크를 위해 요구되는 하위 패키지 노드
  • <test_depend>: 단위 테스트 및 통합 테스트 단계에서 요구되는 패키지 체인
  • <exec_depend>: 런타임 시점(Runtime)에 공유 라이브러리(Shared library) 동적 링킹 및 파이썬 모듈 임포트(Import) 시 요구되는 의존성

이러한 태그들은 패키지가 시스템 내에서 맺고 있는 의존성의 성격을 규명하며, 추출된 정보는 그래프의 간선(Edge) 가중치와 성격을 결정짓는 스칼라 데이터로 변환된다.

0.1.2 의존성 엣지 맵핑 및 DAG 토폴로지 인스턴스화

개별 패키지의 메타데이터 파싱이 완료되면, Colcon 스케줄러는 이를 통합하여 메모리 상에 논리적인 DAG 구조체를 인스턴스화한다. 구체적인 동작 원리는 다음과 같다.

  1. 노드 풀(Node Pool) 초기화: 파싱된 각 패키지명(예: 패키지 A, 패키지 B)을 정점(Vertex) 세트 V의 원소로 추가한다.
  2. 그래프 간선 할당(Edge Allocation): 패키지 A의 package.xml에 패키지 B가 <build_depend>로 선언되어 있다면, 이는 정점 세트 내에서 방향성을 지닌 간선 e = (B, A)로 모델링된다. 즉, 화살표의 방향은 “선행되어야 할 작업“에서 “후행되어야 할 작업“으로 향하는 선후 관계의 위상 구조(Topological Structure)를 형성한다.
  3. 외부 종속성 필터링 체계: 워크스페이스 내부에 존재하지 않고 시스템(OS 레벨)에 사전 설치되어야 하는 패키지(예: rosdep이 관리하는 우분투 기반 시스템 라이브러리)에 대한 의존성은 DAG의 스케줄링 큐에서 즉각 배제된다. 이는 Colcon 모델이 워크스페이스 내부의 패키지들만 빌드 스케줄링 대상으로 국한함으로써 연산 복잡도(Computational Complexity)를 최적화하기 위함이다.

0.1.3 위상 정렬 정규화 및 레벨 지정(Level Assignment)

생성된 초기 DAG 모델은 위상 정렬 알고리즘(Topological Sorting Algorithm)을 거쳐 빌드 단계를 정규화(Normalization)한다. 이 정규화의 본질은 그래프 상의 노드들을 진입 차수(In-degree)에 기반하여 계층적인 레벨(Level)로 분할하는 것이다.

스케줄러는 진입 차수가 0인 노드(즉, 현재 시점에서 선행 의존성이 모두 충족되거나 애초에 의존성이 없는 패키지)들을 탐색하여 ‘Level 0’ 그룹으로 묶는다. 이 그룹에 속한 패키지들의 빌드 프로세스가 시뮬레이션 상에서 완료되었다고 가정하고, 해당 노드들로부터 뻗어 나가는 모든 진출 간선(Out-going edges)을 소거한다. 간선 소거로 인해 새롭게 진입 차수가 0이 된 노드들은 다음 스케줄링 계층인 ‘Level 1’ 그룹으로 편입된다.

이러한 위상 정렬의 재귀적 평가 과정은 시스템의 모든 패키지가 특정 레벨 그룹에 할당될 때까지 반복되며, 결과적으로 도출된 이산적인 레벨 그룹의 집합은 Colcon의 병렬 워커(Worker) 스레드가 실제로 작업을 분배받는 정형화된 스케줄 모델로 활용된다. 이렇듯 package.xml에 텍스트 형태로 선언된 정적 메타데이터는 위상 공간(Topological Space) 상의 엄밀한 계산 과정을 거쳐 동적인 실행 제어 파이프라인의 핵심 토대로 탈바꿈한다.