영찬 블로그
About

CRTP Bomb
Nested Curiously Recurring Template Pattern
2021-01-22

다음 다섯줄의 C# 코드를 컴파일하는데 33초가 걸리며 바이너리 사이즈는 170메가바이트가량 나온다. 세번째 줄에서 Y.YY.Y.Y.Y로 늘리면 컴파일이 아예 불가능해진다.

class X<A, B, C, D, E, F> {
    class Y : X<Y, Y, Y, Y, Y, Y> {
        Y.Y value;
    }
}

일단 어떻게 된 모양인지 분석해보자.

준비

class X {
    class Y {
    }
}

C#에서 중첩 클래스는 위와 같이 클래스 안의 클래스를 만들 수 있게 한다. 여기서 클래스 X 안에 Y가 있으며, 접근은 X.Y 로 할 수 있다.

그렇다면 다음과 같은 꼴을 생각해보자.

class X {
    class Y : X {
    }
}

중첩 클래스 Y는 바깥쪽 클래스 X를 상속한다. 즉, Y 안에 또 Y 클래스가 있다. 여기서 재밌는건, X.Y 클래스와 X.Y.Y 클래스는 동일하다는 것이다. 계속 내려가 X.Y.Y.Y 등도 같다.

이부분을 좀 더 확실하게 이해해보자. 클래스, 즉 타입을 객체(=값)처럼 표기한다면 다음 수도코드처럼 표현할 수 있겠다.

X = {};
X.Y = X;

// X.Y = X.Y.Y = X.Y.Y.Y

그리고 살짝 다른 꼴을 보자.

제너릭 클래스 안에 있는 static, 그리고 중첩 클래스는 제너릭 타입마다 생성된다. 예시를 들자면

class X<T> {
    public static string Value;
}

X<int>.Value = "1";
X<string>.Value = "2";
// X<int>.Value != X<string>.Value

다른 타입 T에 대해 클래스 X<T>는 완전 다른, 독립적인 클래스로 처리된다. 이는 당연히 중첩 클래스에도 적용이 된다.

class X<T> {
    class Y {
    }
}

// X<int>.Y != X<string>.Y

위 코드에서 클래스 X<int>.YX<string>.Y는 다른 클래스라는 것을 알 수 있다.

class X<T> {
    class Y {
        Y inner;
    }
}
X<T>.Y outer;

여기서 클래스 Y에서 선언한 필드 inner의 타입 Y와, 클래스 바깥쪽에서 선언한 outer의 타입 X<T>.Y는 같다고 할 수 있다.

마지막으로 한 케이스만 더 보자.

class X<T> {}
class Y : X<Y> {}

클래스 Y는 클래스 X를 상속하는데, 타입 파라미터로 자기 자신 Y를 패스한다. 별 특별할 건 없지만, 이 케이스를 포함해 위 세개의 케이스를 합쳐 다음과 같은 꼴을 생각해보자.

class X<T> {
    class Y : X<Y> {
    }
}

시작

여기부터가 정말 재밌는 부분이다. 중첩 클래스 Y는, 바깥 클래스 X<T>를 상속하는데, 타입 파라미터로 Y를 넘긴다. 그렇다면 이 Y는 임의의 타입 T에 대해서 X<T>.Y로 접근할 수 있다. 그렇다면 X<T>.YX<>꼴이니 X<T>.Y.Y라는 타입 역시 존재한다. 그렇다면 클래스 Y 내부에서 다음과 같이 Y.Y 타입의 변수를 선언할 수 있다.

class X<T> {
    class Y : X<Y> {
        Y.Y value;
    }
}

여기서 Y.Y 타입은 바깥쪽에서 봤을 때, 위에서 설명한 것처럼 X<T>.Y.Y 이다.

그리고 여기서 C# 컴파일러의 제너릭 타입 처리에 대한 이해가 필요하다. JIT 컴파일러는 제너릭 클래스의 타입이 필요할 때 마다 새롭게 생성된다.

class X<T> {}

X<int> a;       -> class X_Int {}    X_Int a;
X<string> b;    -> class X_String {} X_String b;

실제로 위와 동일하진 않지만, 매우 비슷하게 제너릭 클래스를 사용할 때 다른 타입에 대해 미리 컴파일타임에 클래스를 새롭게 선언해준다. 이게 위 코드에서 문제되는게 무엇일까? 바로 Y.Y 에서 두번째 .Y 타입은 새롭게 선언되는 제너릭 타입이라는 것이다.

Y클래스 내부에서 생각을 한다. Y.Y 타입은 X<Y.Y> 타입을 상속해야 한다. 이는 원래 코드에서는 없던 새로운 제너릭 타입이고, 컴파일러는 이 타입을 미리 계산해둬야 한다. 그래서 아까의 코드는 먼저 다음과 같이 컴파일된다.

class X<T> {
    class Y : X<Y> {
        X<Y>.Y value;
    }
}

여기서 신기한건, 내부에서의 Y.Y 타입이 아까, 내부 타입 Y가 바깥쪽에서 X<T>.Y와 같은 형상을 한다는 것이다. 그렇다면 다음과 같은 코드는 어떨까?

class X<T> {
    class Y : X<Y> {
        Y.Y.Y value;
    }
}

Y.Y.Y 타입에서 Y.Y는 결국 Y 임으로 (Y.Y).Y로 묶어서 생각할 수 있다. 그리고 Y는 순수 클래스이고 람다 대수 연산으로 이를 Y.(Y.Y)로 묶을 수도 있다. 그렇다면 다음과 같이 전개가 된다.

Y.Y.Y
Y.(Y.Y)
X<Y.Y>.Y
X<X<Y>.Y>.Y

여기서 어떤 Y는 펼쳐지고 어떤 Y는 펼쳐지지 않는다고 헷갈릴 수 있는데, 간단하다. 마지막에 붙는 Y는 펼쳐질 수 없는 심볼 정도로 생각할 수 있다. 펼쳐질 수 없는 심볼 Y를 강조해서 다시 보자.

Y.Y.*Y*
Y.(Y.*Y*)
X<Y.*Y*>.*Y*
X<X<*Y*>.*Y*>.*Y*

이렇게 마지막 표현식에서는 모든 표시되는 Y가 더 전개할 수 없는 형태로 되었다는걸 알 수 있다. 컴파일러는 이런 꼴로 타입을 컴파일한다. 다시 원래 문제로 돌아와, Y.Y.Y 타입을 선언한 코드는 다음과 같이 컴파일된다.

class X<T> {
    class Y : X<Y> {
        X<X<Y>.Y>.Y value;
    }
}

여기까지 빌드업은 끝났다. 이제 정말정말정말 본론이다.

class X<A, B> {
    class Y : X<Y, Y> {
        Y.Y value;
    }
}

이제 제너릭 클래스 X는 타입 파라미터를 두개 받는다. 그리고 YX<Y, Y>를 상속한다. 이 때 Y.Y를 전개하면 다음처럼 된다.

class X<A, B> {
    class Y : X<Y, Y> {
        X<Y, Y>.Y value;
    }
}

타입 Y.YX<Y, Y>.Y로 전개되며, 이는 더 전개할 수 없는 표현식이다. 여기에 한번더 Y를 중첩시켜보자.

class X<A, B> {
    class Y : X<Y, Y> {
        Y.Y.Y value;
    }
}

타입 Y.Y.Y을 아까와 같은 방법으로 전개해보자.

Y.Y.Y
Y.(Y.Y)
X<Y.Y, Y.Y>.Y
X<X<Y, Y>.Y, X<Y, Y>.Y>.Y
class X<A, B> {
    class Y : X<Y, Y> {
        X<X<Y, Y>.Y, X<Y, Y>.Y>.Y value;
    }
}

Y.Y.Y.Y는 다음과 같이 전개된다.

class X<A, B> {
    class Y : X<Y, Y> {
        X<X<X<Y, Y>.Y, X<Y, Y>.Y>.Y, X<X<Y, Y>.Y, X<Y, Y>.Y>.Y>.Y value;
    }
}

이 타입 전개는 굉장히 재귀적이다. 타입 Y가 중첩되는 횟수로 타입 Y(n)Y.Y..가 n번 중첩되는 타입이라고 정의하자. 그렇다면 Y(n)을 다음과 같은 점화식으로 표현할 수 있다.

Y(1) = Y
Y(2) = X<Y(1), Y(1)>.Y
Y(n) = X<Y(n-1), Y(n-1)>.Y

그렇다면 제너릭 클래스 X의 타입 파라미터 개수를 늘린다면?

class X<A, B, C> {
    class Y : X<Y, Y, Y> {
    }
}
Y(1) = Y
Y(2) = X<Y(1), Y(1), Y(1)>.Y
Y(n) = X<Y(n-1), Y(n-1), Y(n-1)>.Y

마무리

이제 제너럴하게 타입 파라미터의 개수와 Y 중첩 횟수를 가지고 전개식을 충분히 만들 수 있다. 그렇다면 복잡도 또한 충분히 계산 가능해진다. n개의 타입 파라미터를 가지고, m번 중첩된다면 심볼 Y가 나타나는 개수는 y(m) = n * y(m - 1) + 1이라는 점화식으로 계산되어, 일반항은 다음과 같다.

y(m) = (n^m - 1) / (n - 1)

타입 파라미터가 6개라고 하고, 중첩되는 개수로 심볼 Y의 개수를 계산해보면

5   1555
6   9331
7   55987
8   335923
9   2015539
10  12093235

그리고 실제로 이 코드를 컴파일 했을 때 나온 바이너리 파일의 크기는 (컴파일 타임도 볼 수 있지만 일단 제쳐놓고)

단위는 바이트
5   135680
6   788992
7   4707840
8   28222464
9   169310208
10  CRASH

그렇다면 심볼의 개수로 용량을 적당히 예측할 수 있다. 심볼 Y와 바이너리의 크기의 비율은 84로 점점 수렴하니 그렇다면 크래시나서 컴파일에 실패한 코드도 바이너리파일의 크기를 비교적 꽤 정확히 계산할 수 있다. 그렇다면 중첩 횟수가 10일때의 바이너리 파일 크기는 1015831740바이트. 즉 1기가바이트에 달한다.

그렇다면... 타입 파라미터가 8개고 20번 중첩된다면? 다음 코드의 바이너리 크기는?

class X<A, B, C, D, E, F, G, H> {
    class Y : X<Y, Y, Y, Y, Y, Y, Y, Y> {
        Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y value;
    }
}
약 13835058055282163712 바이트
약 13835058055 기가바이트
약 13835058 테라바이트
약 13835 페타바이트

컴파일 시간은 86106년

레퍼런스

번외

이 주제는 2018년 위 레퍼런스 아티클을 읽고 관심이 생겨 분석해보자 마음을 먹었지만 성공하지 못했던 문제이다. 그런데 갑자기 삘받아서 제대로 하니까 생각보다 쉽게 풀려버렸고 2년만에 멋진 솔루션을 만들어버렸다.

MathIsh-CRTP

2년만에 이슈를 닫을 수 있어서 기쁘다.

©20chan 2024, Built with Gatsby