Xen / learn v0.1.0-demo.2

Box와 재귀 자료구조

연결 리스트나 트리처럼 같은 종류의 값을 다시 포함하는 자료구조에는 재귀 연결이 필요합니다. 구조체·enum과 소유권을 읽은 뒤 진행하세요.

직접 포함할 수 없는 이유

다음 정의는 의도적인 오류입니다. xen check recursive_size_error.xen으로 확인하세요.

struct Node { value: Int, next: Node }
fn main() {}

recursive value layout involving 'Node'

Node 하나의 크기를 알려면 내부의 next: Node 크기를 알아야 하고, 그 안에도 다시 Node가 필요합니다. 유한한 값 배치를 만들 수 없습니다. 재귀 연결에는 Box 또는 Vec 경계가 필요합니다.

연결과 끝을 각각 표현하기

Box<Node>는 다음 노드의 소유권을 가진 연결을 표현합니다. Option<Box<Node>>에서 Some은 다음 노드가 있음을, None은 리스트의 끝을 나타냅니다. 상자만 추가하는 것과 리스트의 종료 조건을 표현하는 것은 별개의 문제입니다.

다음을 recursive_ownership.xen으로 저장하세요. prepend로 노드를 추가하고 sum으로 리스트를 소비합니다.

struct Node { value: Int, next: Option<Box<Node>> }
fn prepend(value: Int, tail: Option<Box<Node>>) -> Option<Box<Node>> {
    return Option.Some(box(Node { value: value, next: tail }));
}
fn sum(list: Option<Box<Node>>) -> Int {
    return match list {
        Option.Some(link) => {
            let node = link.into_inner();
            node.value + sum(node.next)
        },
        Option.None => 0,
    };
}
fn main() {
    let empty: Option<Box<Node>> = Option.None;
    let tail = prepend(20, empty);
    let list = prepend(10, tail);
    println(sum(list));
}

xen check recursive_ownership.xen
xen run recursive_ownership.xen

소유권이 이동하는 순서

empty는 원소 타입이 명시된 None입니다. 값이 없으므로 Option<Box<Node>>를 직접 적습니다.
prepend(20, empty)가 노드를 상자에 넣고 Some으로 감쌉니다.
prepend(10, tail)이 기존 꼬리의 소유권을 새 노드의 next 필드로 옮깁니다. 호출 뒤 tail을 다시 사용하지 않습니다.
sum(list)이 리스트를 넘겨받습니다. Some(link)에서 link.into_inner()는 상자를 소비하고 Node를 꺼냅니다.
현재 정수 값에 sum(node.next)를 더합니다. None에서는 0을 반환해 재귀를 끝냅니다.

Box는 안에 Int처럼 복사 가능한 값을 담아도 이동 전용입니다. Option<Box<Node>>처럼 상자를 포함한 타입도 이동 전용입니다. 이 예제의 sum은 리스트를 빌리는 함수가 아니라 소유권을 받는 함수입니다.

이동한 값을 다시 쓰면

다음은 xen check moved_box_error.xen에서 실패합니다.

fn main() {
    let original = box(42);
    let transferred = original;
    println(original.into_inner());
}

value moved here

마지막 줄을 println(transferred.into_inner());로 바꾸면 42를 출력합니다. 다른 이름에 대입했다고 상자가 두 개 생긴 것이 아닙니다.

상자를 소비하지 않고 읽으려면 as_ref(), 변경하려면 as_mut()와 대여 규칙을 검토하세요. Box 안에는 참조·슬라이스·포인터를 담을 수 없습니다. 단순히 같은 타입의 값을 여러 개 저장하려면 연결 리스트보다 Vec<T>가 필요한 표현에 맞을 수도 있습니다.

종료와 정리

소유 값은 블록을 나갈 때 정리되며 return, break, continue, ?로 나갈 때도 정상 정리가 이뤄집니다. panic이나 런타임 오류는 정상 정리 없이 즉시 종료합니다.

재귀 호출 깊이에는 제한이 있습니다. 이 예제는 작은 연결 구조를 설명하기 위한 것이며, 길이를 제한할 수 없는 입력에 그대로 확장하면 안 됩니다. 긴 입력에는 반복문과 벡터를 사용하는 설계도 검토하세요. 함수와 제어 흐름과 소유권 레퍼런스에서 관련 규칙을 확인할 수 있습니다.

직접 확인하기

prepend(5, list)로 새 머리를 만든 뒤 그 반환값을 sum에 넘겨 35가 나오는지 확인하세요. 그다음 이전의 list를 다시 사용해 보고, 어느 호출에서 소유권이 이동했는지 설명해 보세요.