두 함수의 비대칭으로 “잘못 prune 한 적 없음” 을 알고리즘 단계에서 증명한다. NFA/DFA 없이 정적 prefix 비교만으로 충분하다. PR #5425 가 4년 끝에 못 풀고 죽은 회귀 케이스 — --exclude '*' --include '*.py' — 가 이 알고리즘의 step 1 에서 자동으로 잡힌다.

(1편 에서 9년 된 #1138 과 두 번 close 된 PR, 그리고 회귀 0 을 알고리즘 단계에서 증명 해야 한다는 결론을 봤다. 이번 글이 그 알고리즘이다.)

Part 1. rsync 스타일 — traverse 와 match 분리

PR #5425 의 침몰 원인은 traverse 결정에 match 의 trick 을 끼워 넣은 것 이었다. include 패턴의 부모 prefix 를 자동으로 추가해서 traverse 를 허용하려 했지만 *.py 같은 패턴은 안 잡혔다.

대신 채택한 분리:

질문 1 (파일):  "이 파일을 전송할까?"      → Filter.call (지금 그대로)
질문 2 (디렉터리): "이 디렉터리에 들어갈까?" → Filter.can_skip_directory (신규)

질문 2 는 질문 1 과 독립적이다. 사용자 패턴 리스트를 변형하지 않는다. --exclude '*' --include 'a/b/c' 같은 케이스도 패턴 그대로 두고, 디렉터리 단위로만 “들어갈까 말까” 만 답한다.

의미론 복습

함수를 정의하기 전에 매칭 의미론을 복습하자. awscli/customizations/s3/filters.py:109-163 에 있다.

1. 모든 파일은 기본 include 상태로 시작.
2. 필터를 cmdline 등장 순서대로 평가. 매칭되는 필터가 있으면 그 action 으로 상태 업데이트.
3. 마지막으로 매칭된 필터의 action 이 최종 상태. 매칭 없으면 default include.
4. 패턴은 _full_path_patterns 에서 source rootdir 이 prefix 로 붙어 절대화. 매칭은 fnmatch.fnmatch 로 수행되며, fnmatch 의 * 는 / 도 포함해 모든 문자에 매칭 (Python fnmatch 동작; shell glob 과 다름).

따라서 --exclude '*' 는 단순히 “현재 디렉터리의 파일” 이 아니라 모든 깊이의 모든 경로 를 매칭. 이게 알고리즘이 활용하는 핵심 사실이다.

Part 2. can_skip_directory(D) — 핵심 함수

can_skip_directory(D):
    1. 모든 include 패턴 P_i 에 대해:
         pattern_can_match_under(P_i, D) 가 True 이면 → return False
    2. 어떤 exclude 패턴 P_e 가 존재하여
         pattern_matches_all_under(P_e, D) 가 True 이면 → return True
    3. 그 외 → return False

3줄짜리 알고리즘이지만 안에 두 함수의 비대칭이 들어 있다.

%%{init: {'flowchart': {'nodeSpacing': 25, 'rankSpacing': 30}}}%%
flowchart TD
    D([D]) --> S1{모든 include<br/>매칭 불가?}
    S1 -->|No| T([traverse])
    S1 -->|Yes| S2{exclude 가<br/>모두 덮음?}
    S2 -->|No| T
    S2 -->|Yes| Sk([skip])
    style Sk fill:#c8e6c9,stroke:#2e7d32
    style T fill:#ffe0b2,stroke:#e65100

skip 으로 가는 path 가 단 하나뿐이다 — step 1 통과 + step 2 True. 이 두 강한 주장이 동시에 성립할 때만 prune. 어느 한쪽이라도 약하면 traverse.

명제: True 결과는 항상 안전하다

can_skip_directory(D) == True 이면 D 의 모든 자손 P 는 최종 exclude 된다.

증명:

• step 1 을 통과 → 모든 include 패턴은 D 의 어떤 자손도 매칭하지 못함 (pattern_can_match_under 의 False 가 확정이므로). 즉 D 의 자손에 대해 매칭되는 필터는 모두 exclude.
• step 2 가 True → 어떤 exclude 패턴 P_e 가 D 의 모든 자손을 매칭.
• 따라서 D 의 임의 자손 P 는 최소 하나의 매칭 필터 (=P_e, exclude) 를 가짐. 다른 exclude 도 매칭할 수 있음. include 는 매칭 못 함.
• 마지막 매칭 필터의 action 은 exclude.
• ∴ 모든 자손이 exclude. ∎

증명이 성립하려면 두 함수가 각각 한 방향만 확정해 줘야 한다.

pattern_can_match_under — False 만 확정

“패턴 pat 이 D 의 어떤 자손이라도 매칭할 가능성이 있는가?”

False 는 확정 (“절대 매칭 못 함”), True 는 보수적.

이 함수의 False 가 step 1 에서 “모든 include 가 자손을 매칭 못 한다” 는 강한 주장을 만든다. False 가 잘못 나오면 안 된다 — 매칭 가능한 include 를 놓치면 회귀 발생.

def _literal_prefix(pat):
    """첫 메타문자(*, ?, [) 직전까지의 prefix."""
    for i, c in enumerate(pat):
        if c in '*?[':
            return pat[:i]
    return pat

def pattern_can_match_under(pat, target_dir_with_sep):
    lit = _literal_prefix(pat)
    n = min(len(lit), len(target_dir_with_sep))
    if lit[:n] != target_dir_with_sep[:n]:
        return False                              # literal divergence
    if len(target_dir_with_sep) <= len(lit):
        return True                               # target ⊂ lit, pattern continues past target
    # lit 이 target 보다 짧음 + 일치
    if lit == pat:
        return False                              # 메타문자 없는 순수 리터럴 → 더 못 늘어남
    return True

%%{init: {'flowchart': {'nodeSpacing': 25, 'rankSpacing': 30}}}%%
flowchart TD
    Q1{lit prefix 일치?} -->|No| A[A<br/>False 확정]
    Q1 -->|Yes| Q2{target ⊆ lit?}
    Q2 -->|Yes| B[B<br/>True 가능]
    Q2 -->|No| Q3{메타 있음?}
    Q3 -->|No| C[C<br/>False 확정]
    Q3 -->|Yes| D[D<br/>True 가능]
    style A fill:#c8e6c9,stroke:#2e7d32
    style C fill:#c8e6c9,stroke:#2e7d32
    style B fill:#ffe0b2,stroke:#e65100
    style D fill:#ffe0b2,stroke:#e65100

녹색 (A, C) 은 False 확정 — 매칭 절대 불가능. 주황 (B, D) 은 True 보수적 — 매칭 가능성 있음. 정확성 논증을 분기별로 본다.

분기 A (literal divergence). pattern 이 매칭하는 모든 문자열은 lit 로 시작해야 한다. target 도 prefix 여야 하므로, lit 과 target 이 어느 위치에서든 어긋나면 둘 다를 prefix 로 갖는 문자열은 없다. 따라서 D 자손과 매칭 불가.

분기 B (len(target) <= len(lit) 일치). pattern 이 매칭하는 모든 문자열은 lit 로 시작. target ⊂ lit 이므로 그 문자열들은 target 으로도 시작. lit 이 target 보다 길거나 패턴 뒤에 메타가 있으면 매칭 문자열은 target 보다 길어 자손이 됨. 가능성 있음.

분기 C (lit 이 target 보다 짧음, 순수 리터럴). pattern == lit 은 단 하나의 문자열만 매칭하고 그 길이는 len(lit) < len(target). 즉 target 보다 짧음 → 자손 아님. 매칭 불가.

분기 D (lit 이 target 보다 짧음, 메타 있음). lit 뒤의 메타문자 (*, ?, [) 가 target 의 나머지 문자들을 흡수 가능. * 은 임의 길이라 결과 매칭 문자열을 target 보다 길게 만들 수 있음. 가능성 있음.

pattern_matches_all_under — True 만 확정

“패턴 pat 이 D 의 모든 자손을 매칭하는가?”

True 는 확정 (“정말로 모든 자손을 덮음”), False 는 보수적.

이 함수의 True 가 step 2 에서 “exclude 가 모든 자손을 덮는다” 는 강한 주장을 만든다. True 가 잘못 나오면 안 된다 — 안 덮는데 덮는다고 잘못 답하면 회귀.

def pattern_matches_all_under(pat, target_dir_with_sep):
    lit = _literal_prefix(pat)
    if not target_dir_with_sep.startswith(lit):
        return False                              # lit 이 target prefix 가 아니면 어떤 자손에도 매칭 못 할 가능성
    rest = pat[len(lit):]
    if not rest:
        return False                              # 순수 리터럴 → 단 하나만 매칭
    return all(c == '*' for c in rest)            # 나머지가 모두 '*' 이어야 임의 자손 흡수 가능

%%{init: {'flowchart': {'nodeSpacing': 25, 'rankSpacing': 30}}}%%
flowchart TD
    Q1{target startswith lit?} -->|No| F1[False 보수]
    Q1 -->|Yes| Q2{rest 비어 있음?}
    Q2 -->|Yes| F2[False 보수]
    Q2 -->|No| Q3{rest = 모두 *?}
    Q3 -->|Yes| T[True 확정]
    Q3 -->|No| F3[False 보수]
    style T fill:#c8e6c9,stroke:#2e7d32
    style F1 fill:#ffe0b2,stroke:#e65100
    style F2 fill:#ffe0b2,stroke:#e65100
    style F3 fill:#ffe0b2,stroke:#e65100

녹색 (T) 은 True 확정 — exclude 가 모든 자손을 덮음을 증명. 주황 (F1, F2, F3) 은 False 보수적 — 모를 때 안전 쪽으로. 정확성 논증.

True 반환 조건: lit 이 target_dir_with_sep 의 prefix 이고 rest 가 * 만으로 구성.

임의의 자손 s = target_dir_with_sep + tail (tail 비어있지 않음) 을 보자.

• s 는 lit 로 시작 (∵ lit ⊆ target). 따라서 패턴의 리터럴 prefix 가 s 의 prefix 와 일치.
• 패턴의 나머지는 * (또는 **, ***…). fnmatch 에서 * 는 임의 길이의 임의 문자열을 흡수.
• 흡수 대상: s[len(lit):] = (target 의 lit 이후 부분) + tail. * 이 이걸 통째로 흡수.
• ∴ pattern 은 s 를 매칭. ∎

False 반환 시 자손이 매칭 안 될 수도 있고 될 수도 있음 — 보수적으로 “skip 안 함” 으로 결정 → 회귀 위험 없음.

비대칭의 정체

두 함수를 한 줄로 요약하면:

can_skip_directory 가 True 가 되려면 두 강한 주장이 동시에 성립해야 한다. step 1 에서 “include 절대 매칭 못 함” + step 2 에서 “exclude 가 모두 덮음” 이 모두 한쪽 방향으로 확정되면, 그 디렉터리는 진짜 안전하게 prune 할 수 있다.

각 함수가 한 방향만 확정해도 되는 게 핵심이다. 양쪽 다 확정하는 건 일반 fnmatch 분석으로 어렵다 — ? 나 [seq] 가 들어오면 NFA/DFA 가 필요해진다. 한 방향만 보장하면 보수적 분석으로 충분하고 구현이 짧아진다.

Part 3. 케이스 검증표

알고리즘이 설계대로 작동하는지 9개 대표 케이스로 본다. R = source rootdir.

케이스 #3 — PR #5425 를 죽인 회귀 케이스

aws s3 cp . s3://b --recursive --exclude '*' --include '*.py'

이게 1편에서 본 그 회귀 케이스다. 알고리즘이 어떻게 자동으로 traverse 를 결정하는지 보자.

디렉터리 R/foo/ 에 대해:

• step 1: include 패턴 R/*.py 의 literal prefix 는 R/. target R/foo/ 은 lit 의 prefix 와 일치하고 lit 뒤에 *.py (메타 + 리터럴) 가 있어 흡수 가능 → _pattern_can_match_under = True
• step 1 이 True 이므로 can_skip_directory = False → 디렉터리 traverse

bugfood 의 자동 부모 include 트릭이 못 풀던 케이스가 알고리즘의 자연스러운 동작으로 통과한다. 추가 코드 없이.

케이스 #5, #6 — auto-insert parent include 가 풀던 시나리오

aws s3 cp . s3://b --recursive --exclude 'src/*' --include 'src/included/*'

PR #5425 가 자동 부모 include 패턴 (include 'src/included') 을 추가해서 풀려고 했던 케이스다. 본 알고리즘은 그 트릭 없이 정확히 같은 결과를 산출한다.

• R/src/included/ (#6): step 1 에서 include 패턴 R/src/included/* 의 lit (R/src/included/) 가 target 과 같음 → target ⊆ lit → True → traverse
• R/src/other/ (#5): step 1 에서 같은 include 패턴의 lit 와 target 이 12번째 문자에서 다름 (‘i’ vs ‘o’) → False. step 2 에서 exclude R/src/* 가 target 을 덮음 → True → skip

filters.py 에 신규 변환 로직 0줄. kyleknap 의 “filters.py 손대지 마라” 를 자동으로 만족.

케이스 #7 — 보수적 traverse

aws s3 cp . s3://b --recursive --exclude '*.tmp'

.tmp 파일만 제외. 알고리즘은 어떤 디렉터리도 prune 못 한다.

• step 2: exclude R/*.tmp 의 lit 는 R/, rest 는 *.tmp. rest 가 순수 * 가 아니므로 (.tmp 리터럴 있음) → False
• 결과: traverse

이게 옳은 동작이다. R/foo/ 안에 .tmp 가 아닌 파일이 있을 수 있으니까. 보수적으로 traverse 해서 per-file 필터링에 맡긴다. 잃은 것 없음.

Part 4. 알고리즘이 만족시키는 세 제약

1편 에서 본 세 제약을 다시 보자.

Conservative 가 잃는 것

정확성 우선이라 다음 케이스에서는 prune 못 한다 (보수적으로 traverse):

틀린 prune 은 절대 없음 — 미세한 성능 손실 vs 회귀 안전성의 트레이드오프에서 후자 우선.

OS 구분자 / Windows case 처리

Filter 내부 패턴은 _full_path_patterns 에서 os.path.join 결과로 저장된다. 매칭 시점에 _match_pattern 이 path_pattern.replace('/', os.sep) (local) 또는 replace(os.sep, '/') (s3) 로 변환. can_skip_directory 도 동일 변환을 매칭 직전에 수행 해야 일관됨.

def can_skip_directory(self, dir_path, src_type='local', use_dst_patterns=False):
    patterns = self.dst_patterns if use_dst_patterns else self.patterns
    if not patterns:
        return False
    sep = os.sep if src_type == 'local' else '/'
    target = dir_path.rstrip(sep) + sep
    if src_type == 'local':
        target = os.path.normcase(target)
    normalized = []
    for pattern_type, pat in patterns:
        if src_type == 'local':
            pat = os.path.normcase(pat.replace('/', os.sep))
        else:
            pat = pat.replace(os.sep, '/')
        normalized.append((pattern_type, pat))
    for pattern_type, pat in normalized:
        if pattern_type == 'include' and \
                _pattern_can_match_under(pat, target):
            return False
    for pattern_type, pat in normalized:
        if pattern_type == 'exclude' and \
                _pattern_matches_all_under(pat, target):
            return True
    return False

Windows 에서는 os.path.normcase 가 lowercase 정규화. POSIX 에서는 identity. 기존 _match_pattern 동작과 정확히 같은 정규화가 들어간다.

use_dst_patterns 인자는 sync --delete 의 dst 측 prune 을 위한 것. Filter 가 src/dst 두 패턴 세트를 보유하므로, 어느 쪽을 써서 판정할지 선택. (구현 디테일은 다음 글에서.)

느낀 점

한 방향만 확정하면 충분하다. 처음엔 “fnmatch 패턴이 매칭하는 집합” 을 정확히 분석하려 했다. 그건 일반적으로 NFA/DFA 가 필요하고 코드량이 폭증한다. 그런데 자세히 보면 알고리즘이 True 일 때만 안전하면 된다 — 두 함수를 각각 한 방향만 확정하게 만들면 충분. 이 비대칭이 코드를 1/10 로 줄여 준다.

제약을 만족하는 안은 한 가지 모양으로 수렴한다. 1편의 세 제약 (회귀 0, filters.py 안 건드리기, 머지 분량) 을 다 만족하려고 하면 결국 “별도 함수 + 보수적 분석” 이라는 한 가지 모양밖에 안 남는다. PR #5425 가 4년에 걸쳐 발견한 것도 같은 답이었을지 모른다 — 다만 거기까지 못 갔다.

다음 글은 구현, 그리고 100만 파일에서 이 알고리즘이 실제로 어떻게 동작하는지의 벤치마크다. 67초가 0.055초가 되고, 13개 엣지 케이스에서 결과 정합성 100% 유지. 그리고 그 와중에 9년 된 또 하나의 이슈가 부수효과로 풀리는 걸 발견한다.

Issue: aws/aws-cli#1138 PR #5425 결정적 리뷰 코멘트: discussion_r883991435