aria2-protocol 0.3.4

Multi-protocol networking stack for aria2-rust: HTTP/HTTPS client, FTP/SFTP, full BitTorrent (DHT/PEX/MSE), and Metalink V3/V4 parser
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
//! DHT bucket tree — binary tree routing table structure.
//!
//! The C++ implementation uses `DHTBucketTreeNode` as a binary tree where leaf
//! nodes hold buckets and internal nodes hold min/max ID ranges. When a bucket
//! is full and contains our local node ID, it can be split into two child
//! buckets. This is the core of the Kademlia routing table structure per BEP 5.
//!
//! The Rust version uses `Box` for tree ownership (replacing C++ `unique_ptr`).
//! Buckets are owned directly (not behind `Arc`) since the tree is the sole
//! owner, allowing mutable access through the tree structure.

use super::bucket::Bucket;
use super::node::DhtNode;
use std::collections::BinaryHeap;

/// K-bucket constant: maximum nodes per bucket.
const K: usize = 8;

/// A node in the DHT routing table's binary tree.
///
/// Leaf nodes hold a [`Bucket`] containing up to K [`DhtNode`]s.
/// Internal nodes hold left/right children and the min/max ID range
/// they collectively cover.
///
/// This is the Rust equivalent of C++ `DHTBucketTreeNode`.
pub enum BucketTreeNode {
    /// Internal (branch) node with two children.
    Internal {
        left: Box<BucketTreeNode>,
        right: Box<BucketTreeNode>,
        /// Minimum ID in this subtree (inclusive).
        min_id: [u8; 20],
        /// Maximum ID in this subtree (inclusive).
        max_id: [u8; 20],
    },
    /// Leaf node holding a bucket.
    Leaf { bucket: Bucket },
}

impl BucketTreeNode {
    /// Create a new leaf node wrapping the given bucket.
    pub fn new_leaf(bucket: Bucket) -> Self {
        Self::Leaf { bucket }
    }

    /// Create a new internal node from two children.
    ///
    /// The min/max ID range is derived from the children.
    fn new_internal(left: Box<BucketTreeNode>, right: Box<BucketTreeNode>) -> Self {
        let min_id = left.min_id();
        let max_id = right.max_id();
        Self::Internal {
            left,
            right,
            min_id,
            max_id,
        }
    }

    /// Returns `true` if this is a leaf node.
    pub fn is_leaf(&self) -> bool {
        matches!(self, Self::Leaf { .. })
    }

    /// Returns the minimum ID covered by this subtree.
    pub fn min_id(&self) -> [u8; 20] {
        match self {
            Self::Internal { min_id, .. } => *min_id,
            Self::Leaf { bucket } => *bucket.min_id(),
        }
    }

    /// Returns the maximum ID covered by this subtree.
    pub fn max_id(&self) -> [u8; 20] {
        match self {
            Self::Internal { max_id, .. } => *max_id,
            Self::Leaf { bucket } => *bucket.max_id(),
        }
    }

    /// Returns the child (left or right) that contains the given key.
    ///
    /// Returns `None` if this is a leaf node.
    fn dig(&self, key: &[u8; 20]) -> Option<&BucketTreeNode> {
        match self {
            Self::Internal { left, right, .. } => {
                if left.is_in_range(key) {
                    Some(left)
                } else {
                    Some(right)
                }
            }
            Self::Leaf { .. } => None,
        }
    }

    /// Returns the mutable child (left or right) that contains the given key.
    fn dig_mut(&mut self, key: &[u8; 20]) -> Option<&mut BucketTreeNode> {
        match self {
            Self::Internal { left, right, .. } => {
                if left.is_in_range(key) {
                    Some(left)
                } else {
                    Some(right)
                }
            }
            Self::Leaf { .. } => None,
        }
    }

    /// Returns `true` if `key` falls within this node's [min, max] range.
    pub fn is_in_range(&self, key: &[u8; 20]) -> bool {
        let min = self.min_id();
        let max = self.max_id();
        // key >= min AND key <= max (lexicographic comparison)
        key.as_slice() >= min.as_slice() && key.as_slice() <= max.as_slice()
    }

    /// Get a reference to the bucket if this is a leaf node.
    pub fn bucket(&self) -> Option<&Bucket> {
        match self {
            Self::Leaf { bucket } => Some(bucket),
            Self::Internal { .. } => None,
        }
    }

    /// Get a mutable reference to the bucket if this is a leaf node.
    pub fn bucket_mut(&mut self) -> Option<&mut Bucket> {
        match self {
            Self::Leaf { bucket } => Some(bucket),
            Self::Internal { .. } => None,
        }
    }

    /// Get the left child (internal nodes only).
    pub fn left(&self) -> Option<&BucketTreeNode> {
        match self {
            Self::Internal { left, .. } => Some(left),
            Self::Leaf { .. } => None,
        }
    }

    /// Get the right child (internal nodes only).
    pub fn right(&self) -> Option<&BucketTreeNode> {
        match self {
            Self::Internal { right, .. } => Some(right),
            Self::Leaf { .. } => None,
        }
    }

    /// Split this leaf node's bucket into two child buckets.
    ///
    /// This converts the leaf node into an internal node with two children:
    /// - Left: the existing bucket (mutated in-place to become left half)
    /// - Right: the new bucket returned by `Bucket::split()`
    ///
    /// Panics if called on an internal node.
    pub fn split(&mut self, local_id: &[u8; 20]) {
        match self {
            Self::Leaf { bucket } => {
                // Check if splitting is allowed.
                if !bucket.split_allowed() {
                    tracing::debug!("Bucket split rejected: not allowed");
                    return;
                }

                // Split the bucket in-place: self becomes the left half,
                // right_bucket is the new right half.
                let right_bucket = bucket.split();

                // Create the two child leaf nodes.
                // We need to extract the mutated left bucket since we're about to
                // replace self with an Internal node.
                let left_bucket = std::mem::replace(
                    bucket,
                    Bucket::new_for_range(0, [0u8; 20], [0xFFu8; 20], *local_id),
                );

                let left_node = Box::new(BucketTreeNode::new_leaf(left_bucket));
                let right_node = Box::new(BucketTreeNode::new_leaf(right_bucket));

                *self = Self::new_internal(left_node, right_node);

                tracing::debug!(
                    "Bucket split: left prefix={}, right prefix={}",
                    match self.left() {
                        Some(BucketTreeNode::Leaf { bucket }) => bucket.prefix_length(),
                        _ => 0,
                    },
                    match self.right() {
                        Some(BucketTreeNode::Leaf { bucket }) => bucket.prefix_length(),
                        _ => 0,
                    }
                );
            }
            Self::Internal { .. } => {
                panic!("split() called on non-leaf node");
            }
        }
    }
}

// ---------------------------------------------------------------------------
// Tree-level query functions (equivalent to C++ dht namespace functions)
// ---------------------------------------------------------------------------

/// Find the leaf tree node whose bucket range contains `key`.
///
/// Equivalent to C++ `dht::findTreeNodeFor()`.
pub fn find_tree_node_for<'a>(root: &'a BucketTreeNode, key: &[u8; 20]) -> &'a BucketTreeNode {
    match root {
        BucketTreeNode::Leaf { .. } => root,
        BucketTreeNode::Internal { .. } => {
            let child = root.dig(key).expect("internal node must have children");
            find_tree_node_for(child, key)
        }
    }
}

/// Find the mutable leaf tree node whose bucket range contains `key`.
pub fn find_tree_node_for_mut<'a>(
    root: &'a mut BucketTreeNode,
    key: &[u8; 20],
) -> &'a mut BucketTreeNode {
    match root {
        BucketTreeNode::Leaf { .. } => root,
        BucketTreeNode::Internal { .. } => {
            let child = root.dig_mut(key).expect("internal node must have children");
            find_tree_node_for_mut(child, key)
        }
    }
}

/// Find the bucket whose range contains `key`.
///
/// Equivalent to C++ `dht::findBucketFor()`.
pub fn find_bucket_for<'a>(root: &'a BucketTreeNode, key: &[u8; 20]) -> &'a Bucket {
    let leaf = find_tree_node_for(root, key);
    match leaf {
        BucketTreeNode::Leaf { bucket } => bucket,
        BucketTreeNode::Internal { .. } => unreachable!("find_tree_node_for returned internal"),
    }
}

/// Find the mutable bucket whose range contains `key`.
pub fn find_bucket_for_mut<'a>(root: &'a mut BucketTreeNode, key: &[u8; 20]) -> &'a mut Bucket {
    let leaf = find_tree_node_for_mut(root, key);
    match leaf {
        BucketTreeNode::Leaf { bucket } => bucket,
        BucketTreeNode::Internal { .. } => unreachable!("find_tree_node_for returned internal"),
    }
}

/// Collect up to K closest good nodes to `key` from the routing tree.
///
/// This is the tree-based equivalent of C++ `dht::findClosestKNodes()`.
/// It traverses the tree to find the leaf bucket containing `key`,
/// then collects nodes from the parent's subtree and walks upward
/// until K nodes are found.
pub fn find_closest_k_nodes(root: &BucketTreeNode, key: &[u8; 20]) -> Vec<DhtNode> {
    let mut nodes = BinaryHeap::with_capacity(K);
    collect_closest_from_tree(root, key, &mut nodes);
    let mut result: Vec<DhtNode> = nodes.into_iter().map(|candidate| candidate.node).collect();
    result.sort_by(|a, b| {
        a.distance_to(key)
            .cmp(&b.distance_to(key))
            .then_with(|| a.id.cmp(&b.id))
    });
    result
}

/// Candidate retained by the fixed-size top-K heap.
///
/// `BinaryHeap` keeps the farthest retained node at its root, so a new node
/// can replace it in O(log K) without sorting the complete routing table.
struct ClosestCandidate {
    distance: usize,
    node: DhtNode,
}

impl PartialEq for ClosestCandidate {
    fn eq(&self, other: &Self) -> bool {
        self.distance == other.distance && self.node.id == other.node.id
    }
}

impl Eq for ClosestCandidate {}

impl PartialOrd for ClosestCandidate {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for ClosestCandidate {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.distance
            .cmp(&other.distance)
            .then_with(|| self.node.id.cmp(&other.node.id))
    }
}

/// Collect closest nodes by walking the bucket tree and retaining only K.
///
/// The tree still has to visit each leaf because XOR distance does not map to
/// the lexicographic bucket ranges directly. The bounded heap changes the
/// expensive selection step from O(N log N) plus a full temporary node list to
/// O(N log K) with at most K retained node clones.
fn collect_closest_from_tree(
    root: &BucketTreeNode,
    key: &[u8; 20],
    nodes: &mut BinaryHeap<ClosestCandidate>,
) {
    match root {
        BucketTreeNode::Leaf { bucket } => {
            for node in bucket.nodes() {
                if node.is_bad() {
                    continue;
                }
                let candidate = ClosestCandidate {
                    distance: node.distance_to(key),
                    node: node.clone(),
                };
                if nodes.len() < K {
                    nodes.push(candidate);
                } else if nodes.peek().is_some_and(|farthest| candidate < *farthest) {
                    nodes.pop();
                    nodes.push(candidate);
                }
            }
        }
        BucketTreeNode::Internal { left, right, .. } => {
            collect_closest_from_tree(left, key, nodes);
            collect_closest_from_tree(right, key, nodes);
        }
    }
}

/// Enumerate all leaf buckets in the tree (in-order traversal).
///
/// Equivalent to C++ `dht::enumerateBucket()`.
pub fn enumerate_buckets<'a>(root: &'a BucketTreeNode, buckets: &mut Vec<&'a Bucket>) {
    match root {
        BucketTreeNode::Leaf { bucket } => {
            buckets.push(bucket);
        }
        BucketTreeNode::Internal { left, right, .. } => {
            enumerate_buckets(left, buckets);
            enumerate_buckets(right, buckets);
        }
    }
}

/// Count the total number of leaf buckets in the tree.
pub fn count_buckets(root: &BucketTreeNode) -> usize {
    match root {
        BucketTreeNode::Leaf { .. } => 1,
        BucketTreeNode::Internal { left, right, .. } => count_buckets(left) + count_buckets(right),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::net::SocketAddr;

    fn make_local_node() -> DhtNode {
        DhtNode::new([0u8; 20], "127.0.0.1:6881".parse::<SocketAddr>().unwrap())
    }

    #[test]
    fn test_leaf_node_creation() {
        let local = make_local_node();
        let bucket = Bucket::new(&local);
        let node = BucketTreeNode::new_leaf(bucket);

        assert!(node.is_leaf());
        assert!(node.bucket().is_some());
        assert!(node.left().is_none());
        assert!(node.right().is_none());
    }

    #[test]
    fn test_is_in_range() {
        let local = make_local_node();
        let bucket = Bucket::new(&local);
        let node = BucketTreeNode::new_leaf(bucket);

        // The initial bucket covers the full ID space [0x00..0xFF]
        let zero_id = [0u8; 20];
        let max_id = [0xFFu8; 20];
        assert!(node.is_in_range(&zero_id));
        assert!(node.is_in_range(&max_id));
    }

    #[test]
    fn test_find_tree_node_for() {
        let local = make_local_node();
        let bucket = Bucket::new(&local);
        let root = BucketTreeNode::new_leaf(bucket);

        let key = [0x42u8; 20];
        let found = find_tree_node_for(&root, &key);
        assert!(found.is_leaf());
    }

    #[test]
    fn test_enumerate_buckets_single() {
        let local = make_local_node();
        let bucket = Bucket::new(&local);
        let root = BucketTreeNode::new_leaf(bucket);

        let mut buckets = Vec::new();
        enumerate_buckets(&root, &mut buckets);
        assert_eq!(buckets.len(), 1);
    }

    #[test]
    fn test_count_buckets() {
        let local = make_local_node();
        let bucket = Bucket::new(&local);
        let root = BucketTreeNode::new_leaf(bucket);
        assert_eq!(count_buckets(&root), 1);
    }
}