새 트레이트 솔버의 캐싱
성능을 위해서는 트레이트 솔버의 결과를 캐싱해야 합니다. 이때 캐싱이 건전(sound)하도록 보장해야 합니다. 캐싱은 SearchGraph가 처리합니다.
전역 캐시
기본적으로 캐시는 상당히 단순합니다. 목표(goal)를 평가할 때 그 목표가 전역 캐시에 있는지 확인합니다. 있다면 해당 항목을 재사용합니다. 없다면 목표를 계산한 다음 그 결과를 캐시에 저장합니다.
증분 컴파일을 처리하기 위해 목표의 계산은 DepGraph::with_anon_task 내부에서 이루어지며, 이 함수는 해당 계산 내부에서 사용된 모든 쿼리에 의존하는 새로운 DepNode를 생성합니다. 그런 다음 전역 캐시에 접근할 때 이 DepNode를 읽어, 사용된 모든 쿼리에 대한 의존성 간선을 수동으로 추가합니다: 소스.
오버플로 처리
새 트레이트 솔버에서는 재귀 한도에 도달해도 치명적인 오류가 되지 않으며, 대신 단순히 모호성(ambiguity)을 반환합니다: 소스. 따라서 재귀 한도 도달 여부는 컴파일 실패를 일으키지 않으면서도 결과를 바꿀 수 있습니다. 즉, 캐시된 결과에 접근할 때 남아 있는 사용 가능한 깊이를 고려해야 합니다.
이를 위해 캐시 항목에 더 많은 정보를 저장합니다. 평가가 재귀 한도에 도달하지 않은 목표의 경우에는 도달한 깊이만 저장합니다: 소스. 이러한 결과는 현재의 available_depth가 해당 reached_depth보다 큰 한 자유롭게 사용할 수 있습니다: 소스. 그런 다음 전역 캐시 항목을 사용했는지 여부가 관찰되지 않도록 현재 목표의 도달 깊이를 갱신합니다: 소스.
재귀 한도에 도달한 목표의 경우, 현재는 사용 가능한 깊이가 항목의 깊이와 정확히 일치할 때에만 캐시된 결과를 사용합니다. 따라서 각 목표의 캐시 항목에는 남은 깊이마다 별도의 결과가 들어 있습니다: 소스.1
순환 처리
트레이트 솔버는 순환을 지원해야 합니다. 이러한 순환은 참여하는 목표에 따라 귀납적이거나 공귀납적입니다. 자세한 내용은 공귀납에 관한 장을 참고하십시오. 순환 헤드(cycle head)와 순환 루트(cycle root)는 서로 구분됩니다. 스택 항목이 재귀적으로 접근되면 그 항목은 순환 헤드입니다. 루트는 어떤 순환에든 관여하는 목표 중 스택에서 가장 깊은 목표입니다. 다음 의존성 트리에서 A와 B는 모두 순환 헤드이지만, 루트는 A뿐입니다.
graph TB
A --> B
B --> C
C --> B
C --> A
사이클 참여자의 결과는 아직 스택에 있는 목표의 결과에 따라 달라집니다. 그러나 지금 그 결과를 계산하는 중이므로 그 결과는 아직 알 수 없습니다. 이 문제는 고정점에 도달할 때까지 사이클 헤드를 평가하는 방식으로 처리합니다. 첫 번째 반복에서는 사이클이 공귀납적인지에 따라 제약 조건 없는 성공 또는 오버플로를 반환합니다: 소스. 사이클의 헤드를 평가한 뒤에는 그 provisional_result가 이번 반복의 결과와 같은지 확인합니다. 같다면 이 사이클의 평가를 마친 것이므로 그 결과를 반환합니다. 같지 않다면 임시 결과를 갱신하고 목표를 다시 평가합니다: 소스. 첫 번째 반복 이후에는 사이클이 공귀납적인지 귀납적인지가 중요하지 않습니다. 항상 임시 결과를 사용합니다.
사이클 루트만 캐싱하기
사이클 루트의 평가를 마치기 전까지는 어떤 사이클 참여자의 결과도 전역 캐시로 옮길 수 없습니다. 그러나 사이클을 완전히 평가한 뒤에도 루트 자신을 제외한 모든 참여자의 결과는 여전히 버려야 합니다.
모든 전역 캐시 항목의 쿼리 의존성을 추적합니다. 이 때문에 사이클 참여자를 캐싱하는 일은 간단하지 않습니다. 사이클 루트의 DepNode를 그대로 재사용할 수는 없습니다.2 사이클 A -> B -> A가 있다면 A에 대한 DepNode에는 A -> B 의존성이 포함됩니다. 이 항목을 B에 재사용하면 소스가 변경되었을 때 문제가 생길 수 있습니다. B -> A 간선이 더 이상 존재하지 않을 수도 있고, A가 완전히 제거되었을 수도 있습니다. 이는 쉽게 ICE로 이어질 수 있습니다.
그러나 어떤 목표가 루트인지에 따라 사이클의 결과가 달라질 수 있으므로 상황은 더 나쁩니다: 예제. 이 때문에 캐싱을 더욱 약화할 수밖에 없습니다. 어떤 사이클 루트가 포함된 사이클의 참여자였던 스택 항목이 존재한다면, 그 사이클 루트의 캐시 항목을 사용해서는 안 됩니다. 이를 위해 주어진 루트의 모든 사이클 참여자를 그 루트의 전역 캐시 항목에 저장하고, 그 항목에 스택의 원소가 하나도 포함되지 않았는지 확인합니다: 소스.
임시 캐시
TODO: 이 부분을 작성해야 합니다 :3
- 임시 결과의 스택 의존성
- 엣지 케이스: 임시 캐시가 동작에 영향을 미치는 경우