아래의 깔끔한 파이썬 코드를 보자.


s = "카르페디엠"
print(s[-3:])


페디엠


위 코드는 문자열 s의 마지막 3글자를 출력하는 코드이다. 러스트에서도 흉내내면 다음과 같다.


fn main() {
let s = "카르페디엠";
println!("{}", s.chars().rev().take(3).rev().collect::<String>());
}


러스트 코드는 못생겼는데 작동도 하지 않는다.


error[E0277]: the trait bound `Chars<'_>: ExactSizeIterator` is not satisfied --> src/main.rs:3:44 | 3 | println!("{}", s.chars().rev().take(3).rev().collect::<String>()); | ^^^ the trait `ExactSizeIterator` is not implemented for `Chars<'_>` | = note: required because of the requirements on the impl of `ExactSizeIterator` for `Rev<Chars<'_>>` = note: required because of the requirements on the impl of `DoubleEndedIterator` for `std::iter::Take<Rev<Chars<'_>>>`


왜 작동하지 않는지 이해하려면 러스트의 반복자(iterator)가 어떻게 작동하는지 알아야 한다. 그러기 위해 러스트의 반복자가 가질 수 있는 3가지 중요한 트레잇을 알아야 한다.


Iterator : 모든 반복자가 가지는 트레잇이다. 다음 아이템을 가져오는 next() 메서드가 핵심인 트레잇이다.

DoubleEndedIterator : 거꾸로도 반복이 가능한 반복자가 가지는 트레잇이다. 뒤에서 아이템을 가져오는 next_back() 메서드가 핵심인 트레잇이다.

ExactSizeIterator : 반복자를 처음부터 순회하지 않고도 전체 크기를 알 수 있는 반복자가 가지는 트레잇이다.


예를 들어 슬라이스([T])의 iter() 메서드에서 반환하는 반복자는 Iterator + DoubleEndedIterator + ExactSizeIterator 트레잇을 가진다. 하지만 문자열 슬라이스(str)의 chars() 메서드에서 반환하는 반복자는 Iterator + DoubleEndedIterator를 가진다. 왜냐하면 러스트의 문자열은 UTF-8로 인코딩 되어있어 문자열의 글자수를 알기 위해서는 처음부터 순회하는 방법밖에 없기 때문이다.


한편 러스트에서 반복자에 s.chars().rev().take(3) 와 같이 메서드 rev, take, filter, map, skip, step_by 등이 연달아 붙으면서 비용없는 추상화(zero-cost abstraction)을 한다고 하는데 그것이 어떻게 구현되는지는 타입을 보면 알 수 있다.

s.chars()의 타입은 Char<'a> 이고 트레잇은 Iterator + DoubleEndedIterator를 가진다.

s.chars().rev()의 타입은 Rev<Char<'a>> 이고 트레잇은 Iterator + DoubleEndedIterator를 가진다.

s.chars().rev().take(3)의 타입은 Take<Rev<Char<'a>>> 이고 트레잇은 Iterator를 가진다.


타입의 변화를 관찰하면 제너릭이 연쇄(chain)되는 것을 볼 수 있다. 마지막에 take를 취하면서 DoubleEndedIterator가 사라진 이유는 Take<T> 타입이 DoubleEndedIterator 트레잇을 가지기 위해서 T가 DoubleEndedIterator + ExactSizeIterator를 가질 것을 요구하기 때문이다. 이경우 s.chars().rev() 가 ExactSizeIterator를 안 가지니까 s.chars().rev().take(3)는 DoubleEndedIterator를 가지지 못한다. 즉 DoubleEndedIterator가 없으면 rev에 감싸질 수 없어서 러스트 코드에서 에러가 난 것이다.


반복자가 처음부터 Iterator + DoubleEndedIterator + ExactSizeIterator 를 가지고 있으면 take, skip, step_by, rev, map을 거쳐도 처음 세 트레잇을 잃지 않고 유지된다. 이것을 위해서 반복자 타입 T에 대해 Exact<T> 타입을 만들어보자. 반복자 T가 무엇이든 상관없이 Exact<T>는 ExactSizeIterator 트레잇을 가지도록 만들 것이다. 방법은 간단하다. 딱 한번 clone한 것을 count로 순회에서 전체 크기를 구한 다음 next가 호출될 때마다 1씩 줄이면 된다. 이를 위해 먼저 반복자 T를 포함하는 껍데기(wrapper) 타입을 만들어보자.


#[derive(Clone, Debug)]
pub struct Exact<T> {
iter: T
}
impl<T> Exact<T> where
T : Iterator
{
pub fn new(iter: T) -> Self {
Exact{iter}
}
}
impl<T> Iterator for Exact<T> where
T : Iterator
{
type Item = <T as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
#[inline]
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.iter.nth(n)
}
}
impl<T> DoubleEndedIterator for Exact<T> where
T : DoubleEndedIterator
{
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back()
}
#[inline]
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
self.iter.nth_back(n)
}
}
impl<T> ExactSizeIterator for Exact<T> where T : ExactSizeIterator {}


fn main() {
let iter = "Yassas".chars(); // Hello in greek
let iter = Exact::new(iter);
println!("{}", iter.skip(1).step_by(2).collect::<String>());
}


위 코드에서 아직 Exact<T>는 단지 껍데기(wrapper)일 뿐이다. 러스트에서는 상속이 없으므로 이런 껍데기를 먼저 만들어야지 새로운 멤버변수를 추가한다거나, orphan rule을 피해 외부의 트레잇을 구현할 수 있다. wrapper 타입은 자신이 가지고 있는 원래 타입의 메서드를 밖에서 호출할 수 있도록 메서드를 각각 구현해주어야 한다. 껍데기 타입을 만들 때 단순히 Deref 트레잇을 구현해서 강제 역참조를 통해 메서드를 호출하도록 만들 수도 있지만 self consume하는 메서드를 호출할 수 없고, 원래 타입의 트레잇을 갖추지 못한다는 단점이 있다. 그래서 이렇게 하나하나 구현을 새로 써주어야 한다.


Iterator 트레잇을 구현하기 위해서는 모든 메서드를 구현할 필요 없이 next()만 구현해도 된다. 왜냐하면 nth, fold, count, 등등 나머지 메서드는 모두 next를 사용하여 자동으로 구현되기 때문이다. 하지만 n번째 아이템을 반환하는 nth를 따로 구현하지 않을 경우 next()를 n번 호출하도록 되어 있는데, 슬라이스의 반복자 같은 경우에 굳이 next를 여러번 호출하지 않고 포인터 더하기 연산을 통해 바로 n번째 아이템을 반환할 수 있다. 그러므로 성능과 관련있는 nth는 안쪽 타입의 nth를 호출할 수 있도록 따로 구현해주었다. 마찬가지로 성능을 위해 nth_back도 구현해주었다.


ExactSizeIterator 트레잇은 구현을 따로 하지 않았다. 왜냐하면 트레잇이 요구하는 길이를 반환하는 메서드 len은 Iterator의 size_hint 메서드를 통해서 자동구현되기 때문이다. size_hint는 반복자 크기의 하한 L과 상한 R을 (L, Some(R))의 형식으로 반환한다. L=R인 경우가 바로 길이가 정해진 경우이다.


이제 Exact가 길이를 저장하기 위해 멤버 변수 size를 추가한다. 그리고 next, nth, next_back, nth_back이 호출될 때마다 size를 감소시키도록 코드를 작성해보자.


#[derive(Clone, Debug)]
pub struct Exact<T> {
iter: T, size: usize
}
impl<T> Exact<T> where
T : Iterator + Clone
{
pub fn new(iter: T) -> Self {
let size = iter.clone().count();
Exact{iter, size}
}
}
impl<T> Iterator for Exact<T> where
T : Iterator
{
type Item = <T as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.size = self.size.checked_sub(1).unwrap_or(0);
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
#[inline]
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.size = self.size.checked_sub(n+1).unwrap_or(0);
self.iter.nth(n)
}
}
impl<T> DoubleEndedIterator for Exact<T> where
T : DoubleEndedIterator
{
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.size = self.size.checked_sub(1).unwrap_or(0);
self.iter.next_back()
}
#[inline]
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
self.size = self.size.checked_sub(n+1).unwrap_or(0);
self.iter.nth_back(n)
}
}
impl<T> ExactSizeIterator for Exact<T> where T : Iterator {} // 항상 가짐


size를 1 감소시키는 코드가 self.size = self.size.checked_sub(1).unwrap_or(0);로 checked_sub를 하고 있다. usize끼리 뺄셈을 하면 계산 결과가 음수가 나와 오버플로우가 생길 수 있다. checked_sub는 오버플로우가 발생하면 None을 문제가 없으면 Some을 반환하는 함수이다. 이제 이것을 rev, skip 등등 처럼 반복자 뒤에 이어붙일 수 있도록 트레잇을 만들어보자.


pub trait IterIntoExact : Iterator + Clone + Sized
{
fn exact(self) -> Exact<Self> {
Exact::new(self)
}
}
impl<T> IterIntoExact for T where T: Iterator + Clone + Sized {}


이제 처음 에러난 러스트 코드도 exact를 처음에 붙여서 문제없이 작동시킬 수 있다.


fn main() {
let s = "카르페디엠";
println!("{}", s.chars().exact().rev().take(3).rev().collect::<String>()); // exact가 추가됨!
}


페디엠


문제는 해결됐다. 하지만 파이썬의 강력한 슬라이싱 기능이 부럽기도 하다.


a = sum(range(100)[1::2][:12])
print(a)
b = "sum(range(100)[1::2][:12])"[4:-6][::-1]
print(b)


144
]2::1[)001(egnar


다음엔 이것과 비슷한 기능을 흉내낼 것이다. 다음에 계속...