ferricml 0.2.1

A lean, pure-Rust toolkit for classical machine learning
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
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
use crate::api::ModelError;
use crate::artifact::{ArtifactError, LogicalTreeNode};

pub(crate) const LEAF_FEATURE: u32 = u32::MAX;
pub(crate) const NO_CHILD: u32 = u32::MAX;
pub(crate) const LEFT_IS_LEAF: u32 = 1 << 31;
pub(crate) const RIGHT_IS_LEAF: u32 = 1 << 30;
pub(crate) const FEATURE_MASK: u32 = RIGHT_IS_LEAF - 1;

/// Temporary uniform node used while building a tree.
///
/// A leaf has `feature == u32::MAX`, no children, and stores its prediction in
/// `payload`. A branch stores its threshold in the same field and sends values
/// `<= threshold` left and other values right.
#[derive(Clone, Copy, Debug, PartialEq)]
#[repr(C)]
pub(crate) struct BuildNode {
    pub(crate) feature: u32,
    pub(crate) left: u32,
    pub(crate) right: u32,
    /// Split threshold for branches, prediction for leaves.
    pub(crate) payload: f32,
}

impl BuildNode {
    #[inline]
    pub(crate) fn is_leaf(&self) -> bool {
        self.feature == LEAF_FEATURE
    }

    #[inline]
    pub(crate) fn threshold(&self) -> f32 {
        debug_assert!(!self.is_leaf());
        self.payload
    }

    #[inline]
    pub(crate) fn value(&self) -> f32 {
        debug_assert!(self.is_leaf());
        self.payload
    }

    pub(crate) fn leaf(value: f32) -> Self {
        Self {
            feature: LEAF_FEATURE,
            left: NO_CHILD,
            right: NO_CHILD,
            payload: value,
        }
    }
}

/// One fixed-width inference branch. Two flag bits distinguish child branch
/// indices from inline leaf `f32` bits. This avoids fetching a second node or
/// array entry merely to discover a leaf.
#[derive(Clone, Copy, Debug, PartialEq)]
#[repr(C)]
pub(crate) struct PackedNode {
    pub(crate) left: u32,
    pub(crate) right: u32,
    pub(crate) threshold: f32,
    pub(crate) feature_and_flags: u32,
}

/// A compact decision tree optimized for inference.
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct PackedTree {
    pub(crate) nodes: Vec<PackedNode>,
    pub(crate) root_leaf: Option<f32>,
}

/// Packs validated build nodes into the inference layout.
///
/// `encode_leaf` turns a leaf into the `u32` its parent's child slot carries. A
/// scalar tree stores the leaf value's bits there; a class tree stores the
/// leaf's ordinal, because `classes` probabilities do not fit in a child slot.
/// Returning `None` means the root is itself a leaf, which has no parent slot
/// to be stored in.
///
/// Packing runs once per fitted tree and is deliberately shared: the encoding
/// of a leaf varies between tree flavours, but the pre-order token assignment
/// that keeps a parent adjacent to its left descendants must not.
///
/// The encoder receives the leaf **already loaded**, not just its index. That
/// is not a convenience: the scalar encoder then needs nothing from `build` at
/// all, so it captures no second reference to a buffer this function is also
/// writing near, and each child is read from `build` exactly once per branch
/// rather than once to classify it and again to encode it.
fn pack_topology(
    build: &[BuildNode],
    n_features: usize,
    mut encode_leaf: impl FnMut(usize, BuildNode) -> u32,
) -> Result<Option<Vec<PackedNode>>, ModelError> {
    validate_build_topology(build, n_features)?;
    if build[0].is_leaf() {
        return Ok(None);
    }
    let mut branch_indices = vec![NO_CHILD; build.len()];
    let mut nodes = Vec::new();
    // Assign tokens in the builder's pre-order so a parent and its left
    // descendants remain adjacent during inference.
    for (index, node) in build.iter().enumerate() {
        if !node.is_leaf() {
            let packed_index = u32::try_from(nodes.len()).map_err(|_| ModelError::TreeTooLarge)?;
            nodes.push(PackedNode {
                left: 0,
                right: 0,
                threshold: node.threshold(),
                feature_and_flags: node.feature,
            });
            branch_indices[index] = packed_index;
        }
    }
    for (index, node) in build.iter().enumerate().filter(|(_, node)| !node.is_leaf()) {
        let left = build[node.left as usize];
        let right = build[node.right as usize];
        let packed = &mut nodes[branch_indices[index] as usize];
        if left.is_leaf() {
            packed.feature_and_flags |= LEFT_IS_LEAF;
            packed.left = encode_leaf(node.left as usize, left);
        } else {
            packed.left = branch_indices[node.left as usize];
        }
        if right.is_leaf() {
            packed.feature_and_flags |= RIGHT_IS_LEAF;
            packed.right = encode_leaf(node.right as usize, right);
        } else {
            packed.right = branch_indices[node.right as usize];
        }
    }
    Ok(Some(nodes))
}

impl PackedTree {
    pub(crate) fn from_build_nodes(
        build: Vec<BuildNode>,
        n_features: usize,
    ) -> Result<Self, ModelError> {
        // The encoder reads nothing from `build`, so it captures nothing and
        // this borrows the buffer exactly once.
        let Some(nodes) = pack_topology(&build, n_features, |_, node| node.value().to_bits())?
        else {
            return Ok(Self {
                nodes: Vec::new(),
                root_leaf: Some(build[0].value()),
            });
        };
        let tree = Self {
            nodes,
            root_leaf: None,
        };
        debug_assert!(tree.has_valid_packed_topology(n_features));
        Ok(tree)
    }

    #[inline(always)]
    pub(crate) fn predict(&self, row: &[f32]) -> f32 {
        if let Some(value) = self.root_leaf {
            return value;
        }
        let mut index = 0usize;
        loop {
            // SAFETY: `index` is in bounds. Every packed buffer is produced by
            // `pack_topology`, which calls `validate_build_topology`
            // unconditionally — in release as in debug, on fitted and decoded
            // trees alike, since `from_logical_nodes` funnels into
            // `from_build_nodes` too. That validator rejects the tree unless
            // each node is reached from the root exactly once and every node is
            // reached (so the structure is a tree: no cycle, no shared subtree,
            // no unreachable record) and every branch has `left == index + 1`,
            // `right > left` and `right < build.len()`. Packing is a
            // pre-order relabelling of exactly those nodes, so each branch token
            // written below is an index into this buffer, and the strict
            // increase is also why this loop terminates. The `debug_assert!` in
            // `from_build_nodes` re-checks the packed form afterwards; it is a
            // redundant post-condition, not the check this relies on.
            //
            // The `debug_assert!` below is not the check this relies on either,
            // and it is not what detects a violation: `get_unchecked` carries
            // its own debug-mode precondition check, so an out-of-range index
            // already aborts a debug build with `unsafe precondition(s)
            // violated`. Measured, by removing these two lines under an injected
            // topology fault and watching the standard library report it
            // instead. What these add is *which* invariant broke and with what
            // values, at the point of the read.
            //
            // The half that was genuinely missing was neither: it was a test
            // that predicts. This reasoning is a composition — a decode-time
            // validator licensing a prediction-time read — and no assertion here
            // composes it, because an assertion on a line nothing executes is
            // not coverage. The hostile-artifact sweep in
            // `tests/artifact_hardening.rs` runs it now, and floors how much of
            // it it runs.
            debug_assert!(
                index < self.nodes.len(),
                "packed branch token {index} is outside a {}-node tree",
                self.nodes.len()
            );
            let node = unsafe { self.nodes.get_unchecked(index) };
            // SAFETY: the feature index is within `row`. The same validator
            // rejects any branch whose `feature` is not `< n_features`, and the
            // width it is given is the one the model then reports as its fitted
            // width — the decoded `n_features_in` on the artifact path — which
            // public prediction validates `row` against before traversal. A
            // hostile artifact therefore cannot declare a narrow width and pack
            // wide feature indices behind it — the clause of this chain that is
            // reachable from bytes an attacker wrote, and the one the sweep
            // demonstrably catches: handing the validator a width the model does
            // not report fails the sweep here with `packed feature 9 is outside
            // a 1-wide row`. The `debug_assert!` below is the same naming
            // measure as the one above, on this half of the chain.
            let feature = (node.feature_and_flags & FEATURE_MASK) as usize;
            debug_assert!(
                feature < row.len(),
                "packed feature {feature} is outside a {}-wide row",
                row.len()
            );
            let value = unsafe { *row.get_unchecked(feature) };
            if value <= node.threshold {
                if node.feature_and_flags & LEFT_IS_LEAF != 0 {
                    return f32::from_bits(node.left);
                }
                index = node.left as usize;
            } else {
                if node.feature_and_flags & RIGHT_IS_LEAF != 0 {
                    return f32::from_bits(node.right);
                }
                index = node.right as usize;
            }
        }
    }

    fn has_valid_packed_topology(&self, n_features: usize) -> bool {
        if self.root_leaf.is_some() {
            return self.nodes.is_empty() && self.root_leaf.is_some_and(f32::is_finite);
        }
        !self.nodes.is_empty()
            && self.nodes.iter().all(|node| {
                ((node.feature_and_flags & FEATURE_MASK) as usize) < n_features
                    && node.threshold.is_finite()
                    && child_is_valid(
                        node.left,
                        node.feature_and_flags & LEFT_IS_LEAF,
                        self.nodes.len(),
                    )
                    && child_is_valid(
                        node.right,
                        node.feature_and_flags & RIGHT_IS_LEAF,
                        self.nodes.len(),
                    )
            })
    }
}

/// Conversion between the private inference layout and the stable logical
/// tree records used by artifacts.
///
/// The packed layout is deliberately not a serialization format: it stores
/// leaves inline in their parent's child slots as flagged `f32` bits, and it
/// keeps only branch nodes in `nodes`. Encoding therefore *synthesizes* the
/// leaf records, and decoding never trusts the logical bytes — it rebuilds
/// [`BuildNode`]s and re-runs the same topology validator that fitting uses.
impl PackedTree {
    /// Number of records [`PackedTree::to_logical_nodes`] will produce.
    ///
    /// Every branch has exactly two children, so a tree with `b` stored
    /// branches expands to `b` branch records and `b + 1` synthesized leaves.
    pub(crate) fn logical_node_count(&self) -> usize {
        if self.root_leaf.is_some() {
            1
        } else {
            self.nodes.len() * 2 + 1
        }
    }

    /// Largest absolute leaf value, including inline and root leaves.
    pub(crate) fn max_abs_leaf(&self) -> f32 {
        if let Some(value) = self.root_leaf {
            return value.abs();
        }
        self.nodes.iter().fold(0.0_f32, |largest, node| {
            let mut largest = largest;
            if node.feature_and_flags & LEFT_IS_LEAF != 0 {
                largest = largest.max(f32::from_bits(node.left).abs());
            }
            if node.feature_and_flags & RIGHT_IS_LEAF != 0 {
                largest = largest.max(f32::from_bits(node.right).abs());
            }
            largest
        })
    }

    /// Expands the packed tree into pre-order logical records.
    ///
    /// The result satisfies the logical-tree contract: node `0` is the root,
    /// a branch's left child is always the next record, and a tree with `L`
    /// leaves has exactly `2L - 1` records. A `root_leaf` tree becomes the
    /// single-node logical tree.
    pub(crate) fn to_logical_nodes(&self) -> Vec<LogicalTreeNode> {
        if let Some(value) = self.root_leaf {
            return vec![LogicalTreeNode::Leaf { value }];
        }
        // Every branch contributes one record and every branch has exactly two
        // children, so a tree with `b` branches has `b + 1` leaves.
        let mut nodes = Vec::with_capacity(self.nodes.len() * 2 + 1);
        let mut pending = vec![Emit::Branch(0)];
        while let Some(task) = pending.pop() {
            match task {
                Emit::Leaf(bits) => nodes.push(LogicalTreeNode::Leaf {
                    value: f32::from_bits(bits),
                }),
                Emit::AttachRight(parent) => {
                    let right = u32::try_from(nodes.len()).expect("bounded node count");
                    match &mut nodes[parent] {
                        LogicalTreeNode::Branch { right: slot, .. } => *slot = right,
                        LogicalTreeNode::Leaf { .. } => unreachable!("branch record"),
                    }
                }
                Emit::Branch(packed_index) => {
                    let node = self.nodes[packed_index];
                    let index = nodes.len();
                    let left = u32::try_from(index + 1).expect("bounded node count");
                    nodes.push(LogicalTreeNode::Branch {
                        feature: node.feature_and_flags & FEATURE_MASK,
                        threshold: node.threshold,
                        left,
                        // Patched once the left subtree has been emitted.
                        right: 0,
                    });
                    // Popped in reverse: left subtree, then the right index
                    // patch, then the right subtree.
                    pending.push(child(node.right, node.feature_and_flags & RIGHT_IS_LEAF));
                    pending.push(Emit::AttachRight(index));
                    pending.push(child(node.left, node.feature_and_flags & LEFT_IS_LEAF));
                }
            }
        }
        nodes
    }

    /// Rebuilds a packed tree from validated logical records.
    ///
    /// Decoded records are turned back into [`BuildNode`]s and handed to
    /// [`PackedTree::from_build_nodes`], so an artifact goes through exactly
    /// the topology, feature-width, and finiteness checks that a freshly
    /// fitted tree does.
    pub(crate) fn from_logical_nodes(
        nodes: &[LogicalTreeNode],
        n_features: usize,
    ) -> Result<Self, ArtifactError> {
        let build = nodes
            .iter()
            .map(|&node| match node {
                LogicalTreeNode::Leaf { value } => BuildNode::leaf(value),
                LogicalTreeNode::Branch {
                    feature,
                    threshold,
                    left,
                    right,
                } => BuildNode {
                    feature,
                    left,
                    right,
                    payload: threshold,
                },
            })
            .collect();
        Self::from_build_nodes(build, n_features).map_err(|_| ArtifactError::InvalidPayload)
    }
}

/// A decision tree whose leaves store one probability per class.
///
/// The packed layout stores a scalar leaf inline in its parent's child slot,
/// which `classes` probabilities cannot fit in. The child slot therefore holds
/// the leaf's **ordinal** — a plain index into [`ClassTree::probabilities`],
/// not punned float bits — assigned in the same pre-order the branches are.
/// Traversal is otherwise identical, and inference returns a borrowed row of
/// probabilities so a forest can average without allocating.
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct ClassTree {
    nodes: Vec<PackedNode>,
    /// Row-major, one row of `classes` values per leaf ordinal. A tree whose
    /// root is a leaf has no branches and exactly one row.
    probabilities: Vec<f32>,
    classes: usize,
}

impl ClassTree {
    /// Builds a class tree from validated build nodes and their retained
    /// per-node class weights.
    ///
    /// `weights[i]` is the total weight reaching build node `i` and
    /// `class_weights[i * classes ..]` its per-class split, so a leaf's stored
    /// probability is one division of `f64` accumulations narrowed once.
    pub(crate) fn from_build_nodes(
        build: Vec<BuildNode>,
        class_weights: &[f64],
        weights: &[f64],
        classes: usize,
        n_features: usize,
    ) -> Result<Self, ModelError> {
        debug_assert_eq!(class_weights.len(), build.len() * classes);
        debug_assert_eq!(weights.len(), build.len());
        let mut probabilities = Vec::new();
        let mut push_leaf = |index: usize| {
            let total = weights[index];
            for class in 0..classes {
                probabilities.push((class_weights[index * classes + class] / total) as f32);
            }
        };
        let mut ordinal = 0_u32;
        let nodes = pack_topology(&build, n_features, |index, _| {
            push_leaf(index);
            let assigned = ordinal;
            ordinal += 1;
            assigned
        })?;
        let Some(nodes) = nodes else {
            push_leaf(0);
            return Ok(Self {
                nodes: Vec::new(),
                probabilities,
                classes,
            });
        };
        let tree = Self {
            nodes,
            probabilities,
            classes,
        };
        if !tree.has_valid_class_topology(n_features) {
            return Err(ModelError::TreeTooLarge);
        }
        Ok(tree)
    }

    /// Number of probability columns each leaf stores.
    #[inline]
    pub(crate) fn classes(&self) -> usize {
        self.classes
    }

    /// The leaf probabilities one row reaches.
    #[inline(always)]
    pub(crate) fn probabilities(&self, row: &[f32]) -> &[f32] {
        let ordinal = if self.nodes.is_empty() {
            0
        } else {
            self.leaf_ordinal(row) as usize
        };
        &self.probabilities[ordinal * self.classes..(ordinal + 1) * self.classes]
    }

    /// Traversal to a leaf ordinal, with ordinary checked indexing.
    ///
    /// The scalar tree next door elides its bounds checks, on measured
    /// evidence, for the crate's most benchmarked inference path. This path is
    /// new and unmeasured, and an unproven `unsafe` is a worse trade than a
    /// bounds check: construction already guarantees every index is in range,
    /// so the checks are provably redundant and can be removed later *with*
    /// evidence rather than in anticipation of it.
    #[inline(always)]
    fn leaf_ordinal(&self, row: &[f32]) -> u32 {
        let mut index = 0usize;
        loop {
            let node = self.nodes[index];
            let value = row[(node.feature_and_flags & FEATURE_MASK) as usize];
            if value <= node.threshold {
                if node.feature_and_flags & LEFT_IS_LEAF != 0 {
                    return node.left;
                }
                index = node.left as usize;
            } else {
                if node.feature_and_flags & RIGHT_IS_LEAF != 0 {
                    return node.right;
                }
                index = node.right as usize;
            }
        }
    }

    /// Every branch token is in range, every leaf ordinal addresses a stored
    /// probability row, and every stored probability is a finite `0..=1`.
    fn has_valid_class_topology(&self, n_features: usize) -> bool {
        let leaves = self.nodes.len() + 1;
        if self.probabilities.len() != leaves * self.classes || self.classes == 0 {
            return false;
        }
        if !self
            .probabilities
            .iter()
            .all(|value| value.is_finite() && (0.0..=1.0).contains(value))
        {
            return false;
        }
        self.nodes.iter().all(|node| {
            ((node.feature_and_flags & FEATURE_MASK) as usize) < n_features
                && node.threshold.is_finite()
                && class_child_is_valid(
                    node.left,
                    node.feature_and_flags & LEFT_IS_LEAF,
                    self.nodes.len(),
                    leaves,
                )
                && class_child_is_valid(
                    node.right,
                    node.feature_and_flags & RIGHT_IS_LEAF,
                    self.nodes.len(),
                    leaves,
                )
        })
    }
}

/// Conversion between the private class-tree layout and the stable artifact
/// records.
///
/// The topology is the *same* logical-tree contract a scalar tree uses, with
/// one difference: a class leaf has no scalar value, so its record carries a
/// reserved `+0.0` where a scalar leaf carries its prediction, and the leaf's
/// distribution lives in a separate per-tree probability block.
///
/// That block is ordered by the leaf's **pre-order rank**, not by the runtime
/// ordinal stored in the parent's child slot. The two are not the same order:
/// packing assigns ordinals branch by branch, so a branch's right leaf can be
/// numbered before leaves that precede it in pre-order. Storing the runtime
/// ordinals would also make the artifact malleable — permuting the ordinals and
/// the block together would name the same model twice — whereas pre-order rank
/// is determined by the topology alone, so a model has exactly one encoding.
impl ClassTree {
    /// Number of logical records [`Self::to_logical_nodes`] will produce.
    pub(crate) fn logical_node_count(&self) -> usize {
        if self.nodes.is_empty() {
            1
        } else {
            self.nodes.len() * 2 + 1
        }
    }

    /// Expands the tree into pre-order records and its pre-order leaf block.
    pub(crate) fn to_logical_nodes(&self) -> (Vec<LogicalTreeNode>, Vec<f32>) {
        let leaves = self.nodes.len() + 1;
        let mut probabilities = Vec::with_capacity(leaves * self.classes);
        if self.nodes.is_empty() {
            probabilities.extend_from_slice(&self.probabilities[..self.classes]);
            return (vec![LogicalTreeNode::Leaf { value: 0.0 }], probabilities);
        }
        let mut nodes = Vec::with_capacity(self.nodes.len() * 2 + 1);
        let mut pending = vec![Emit::Branch(0)];
        while let Some(task) = pending.pop() {
            match task {
                Emit::Leaf(ordinal) => {
                    let start = ordinal as usize * self.classes;
                    probabilities
                        .extend_from_slice(&self.probabilities[start..start + self.classes]);
                    nodes.push(LogicalTreeNode::Leaf { value: 0.0 });
                }
                Emit::AttachRight(parent) => {
                    let right = u32::try_from(nodes.len()).expect("bounded node count");
                    match &mut nodes[parent] {
                        LogicalTreeNode::Branch { right: slot, .. } => *slot = right,
                        LogicalTreeNode::Leaf { .. } => unreachable!("branch record"),
                    }
                }
                Emit::Branch(packed_index) => {
                    let node = self.nodes[packed_index];
                    let index = nodes.len();
                    let left = u32::try_from(index + 1).expect("bounded node count");
                    nodes.push(LogicalTreeNode::Branch {
                        feature: node.feature_and_flags & FEATURE_MASK,
                        threshold: node.threshold,
                        left,
                        right: 0,
                    });
                    pending.push(child(node.right, node.feature_and_flags & RIGHT_IS_LEAF));
                    pending.push(Emit::AttachRight(index));
                    pending.push(child(node.left, node.feature_and_flags & LEFT_IS_LEAF));
                }
            }
        }
        (nodes, probabilities)
    }

    /// Rebuilds a class tree from validated records and a pre-order leaf block.
    ///
    /// The records are turned back into [`BuildNode`]s and repacked through the
    /// same topology validator fitting uses, and the reconstructed model is
    /// re-checked against the same class-topology invariant a fitted tree
    /// satisfies, so the decoded bytes are never trusted.
    pub(crate) fn from_logical_nodes(
        nodes: &[LogicalTreeNode],
        leaf_probabilities: &[f32],
        classes: usize,
        n_features: usize,
    ) -> Result<Self, ArtifactError> {
        if classes == 0 {
            return Err(ArtifactError::InvalidPayload);
        }
        let mut build = Vec::with_capacity(nodes.len());
        // Pre-order rank of each leaf, indexed by its build-node position. The
        // build array is itself pre-order, so this is just a running count.
        let mut leaf_rank = vec![0_usize; nodes.len()];
        let mut leaves = 0_usize;
        for (index, &node) in nodes.iter().enumerate() {
            match node {
                LogicalTreeNode::Leaf { value } => {
                    // The scalar slot is reserved in a class tree; a nonzero
                    // value would be a second encoding of the same model.
                    if value.to_bits() != 0 {
                        return Err(ArtifactError::InvalidPayload);
                    }
                    leaf_rank[index] = leaves;
                    leaves += 1;
                    build.push(BuildNode::leaf(0.0));
                }
                LogicalTreeNode::Branch {
                    feature,
                    threshold,
                    left,
                    right,
                } => build.push(BuildNode {
                    feature,
                    left,
                    right,
                    payload: threshold,
                }),
            }
        }
        if leaves
            .checked_mul(classes)
            .is_none_or(|expected| expected != leaf_probabilities.len())
        {
            return Err(ArtifactError::InvalidPayload);
        }

        let mut probabilities = Vec::with_capacity(leaf_probabilities.len());
        let mut push_leaf = |index: usize| {
            let start = leaf_rank[index] * classes;
            probabilities.extend_from_slice(&leaf_probabilities[start..start + classes]);
        };
        let mut ordinal = 0_u32;
        let packed = pack_topology(&build, n_features, |index, _| {
            push_leaf(index);
            let assigned = ordinal;
            ordinal += 1;
            assigned
        })
        .map_err(|_| ArtifactError::InvalidPayload)?;
        let tree = match packed {
            None => {
                push_leaf(0);
                Self {
                    nodes: Vec::new(),
                    probabilities,
                    classes,
                }
            }
            Some(nodes) => Self {
                nodes,
                probabilities,
                classes,
            },
        };
        if !tree.has_valid_class_topology(n_features) {
            return Err(ArtifactError::InvalidPayload);
        }
        Ok(tree)
    }
}

fn class_child_is_valid(value: u32, leaf_flag: u32, node_count: usize, leaves: usize) -> bool {
    if leaf_flag != 0 {
        (value as usize) < leaves
    } else {
        (value as usize) < node_count
    }
}

/// One step of a pre-order walk over a packed tree.
///
/// A leaf carries the raw child slot rather than a decoded value, because the
/// two tree flavours store different things there: a scalar tree stores the
/// leaf value's bits, a class tree stores the leaf's ordinal. The walk itself
/// is the same either way, so only the interpretation differs.
enum Emit {
    Branch(usize),
    Leaf(u32),
    AttachRight(usize),
}

fn child(value: u32, leaf_flag: u32) -> Emit {
    if leaf_flag != 0 {
        Emit::Leaf(value)
    } else {
        Emit::Branch(value as usize)
    }
}

fn child_is_valid(value: u32, leaf_flag: u32, node_count: usize) -> bool {
    if leaf_flag != 0 {
        f32::from_bits(value).is_finite()
    } else {
        (value as usize) < node_count
    }
}

fn validate_build_topology(build: &[BuildNode], n_features: usize) -> Result<(), ModelError> {
    if build.is_empty() || n_features == 0 {
        return Err(ModelError::TreeTooLarge);
    }
    let mut seen = vec![false; build.len()];
    let mut stack = vec![0_usize];
    while let Some(index) = stack.pop() {
        if index >= build.len() || seen[index] {
            return Err(ModelError::TreeTooLarge);
        }
        seen[index] = true;
        let node = build[index];
        if !node.payload.is_finite() {
            return Err(ModelError::TreeTooLarge);
        }
        if node.is_leaf() {
            if node.left != NO_CHILD || node.right != NO_CHILD {
                return Err(ModelError::TreeTooLarge);
            }
            continue;
        }
        let left = node.left as usize;
        let right = node.right as usize;
        if node.feature as usize >= n_features
            || left != index + 1
            || right <= left
            || right >= build.len()
        {
            return Err(ModelError::TreeTooLarge);
        }
        stack.push(right);
        stack.push(left);
    }
    if seen.iter().any(|&visited| !visited) {
        return Err(ModelError::TreeTooLarge);
    }
    Ok(())
}

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

    #[test]
    fn rejects_invalid_builder_topologies_before_packing() {
        assert_eq!(
            PackedTree::from_build_nodes(Vec::new(), 1),
            Err(ModelError::TreeTooLarge)
        );
        assert_eq!(
            PackedTree::from_build_nodes(vec![BuildNode::leaf(0.0)], 0),
            Err(ModelError::TreeTooLarge)
        );

        let invalid_feature = vec![
            BuildNode {
                feature: 1,
                left: 1,
                right: 2,
                payload: 0.5,
            },
            BuildNode::leaf(0.0),
            BuildNode::leaf(1.0),
        ];
        assert_eq!(
            PackedTree::from_build_nodes(invalid_feature, 1),
            Err(ModelError::TreeTooLarge)
        );

        let cycle = vec![
            BuildNode {
                feature: 0,
                left: 0,
                right: 2,
                payload: 0.5,
            },
            BuildNode::leaf(0.0),
            BuildNode::leaf(1.0),
        ];
        assert_eq!(
            PackedTree::from_build_nodes(cycle, 1),
            Err(ModelError::TreeTooLarge)
        );
    }

    fn branch(feature: u32, threshold: f32, left: u32, right: u32) -> BuildNode {
        BuildNode {
            feature,
            left,
            right,
            payload: threshold,
        }
    }

    /// Pre-order build nodes for
    /// `f0 <= 1 ? (f1 <= 2 ? -1 : 3) : (f0 <= 5 ? 7 : (f1 <= 0 ? 11 : 13))`.
    fn mixed_depth_build() -> Vec<BuildNode> {
        vec![
            branch(0, 1.0, 1, 4),
            branch(1, 2.0, 2, 3),
            BuildNode::leaf(-1.0),
            BuildNode::leaf(3.0),
            branch(0, 5.0, 5, 6),
            BuildNode::leaf(7.0),
            branch(1, 0.0, 7, 8),
            BuildNode::leaf(11.0),
            BuildNode::leaf(13.0),
        ]
    }

    #[test]
    fn logical_records_synthesize_inline_leaves_and_round_trip_to_the_same_tree() {
        let build = mixed_depth_build();
        let tree = PackedTree::from_build_nodes(build.clone(), 2).unwrap();
        // Four branches are stored; the five leaves live inline in flag bits.
        assert_eq!(tree.nodes.len(), 4);

        let logical = tree.to_logical_nodes();
        assert_eq!(logical.len(), build.len());
        assert_eq!(
            logical
                .iter()
                .filter(|node| matches!(node, LogicalTreeNode::Leaf { .. }))
                .count(),
            5
        );
        for (index, (&logical_node, build_node)) in logical.iter().zip(&build).enumerate() {
            let expected = if build_node.is_leaf() {
                LogicalTreeNode::Leaf {
                    value: build_node.value(),
                }
            } else {
                LogicalTreeNode::Branch {
                    feature: build_node.feature,
                    threshold: build_node.threshold(),
                    left: build_node.left,
                    right: build_node.right,
                }
            };
            assert_eq!(logical_node, expected, "record {index}");
        }

        let restored = PackedTree::from_logical_nodes(&logical, 2).unwrap();
        assert_eq!(restored, tree);
        assert_eq!(restored.to_logical_nodes(), logical);
        for row in [[0.0, 0.0], [0.0, 9.0], [3.0, 0.0], [9.0, -1.0], [9.0, 9.0]] {
            assert_eq!(restored.predict(&row), tree.predict(&row));
        }
    }

    #[test]
    fn a_root_leaf_tree_maps_to_the_one_node_logical_tree() {
        let tree = PackedTree::from_build_nodes(vec![BuildNode::leaf(2.5)], 3).unwrap();
        assert!(tree.nodes.is_empty());
        let logical = tree.to_logical_nodes();
        assert_eq!(logical, vec![LogicalTreeNode::Leaf { value: 2.5 }]);
        let restored = PackedTree::from_logical_nodes(&logical, 3).unwrap();
        assert_eq!(restored.root_leaf, Some(2.5));
        assert_eq!(restored, tree);
    }

    #[test]
    fn logical_records_are_revalidated_instead_of_trusted() {
        let valid = PackedTree::from_build_nodes(mixed_depth_build(), 2)
            .unwrap()
            .to_logical_nodes();
        assert!(PackedTree::from_logical_nodes(&valid, 2).is_ok());

        let cases: [(&str, Vec<LogicalTreeNode>, usize); 5] = [
            ("empty", Vec::new(), 2),
            (
                "feature beyond the fitted width",
                vec![
                    LogicalTreeNode::Branch {
                        feature: 2,
                        threshold: 1.0,
                        left: 1,
                        right: 2,
                    },
                    LogicalTreeNode::Leaf { value: 0.0 },
                    LogicalTreeNode::Leaf { value: 1.0 },
                ],
                2,
            ),
            (
                "leaf sentinel smuggled in as a branch feature",
                vec![
                    LogicalTreeNode::Branch {
                        feature: LEAF_FEATURE,
                        threshold: 1.0,
                        left: 1,
                        right: 2,
                    },
                    LogicalTreeNode::Leaf { value: 0.0 },
                    LogicalTreeNode::Leaf { value: 1.0 },
                ],
                2,
            ),
            (
                "non-finite leaf value",
                vec![
                    LogicalTreeNode::Branch {
                        feature: 0,
                        threshold: 1.0,
                        left: 1,
                        right: 2,
                    },
                    LogicalTreeNode::Leaf {
                        value: f32::INFINITY,
                    },
                    LogicalTreeNode::Leaf { value: 1.0 },
                ],
                2,
            ),
            (
                "unreachable trailing record",
                vec![
                    LogicalTreeNode::Branch {
                        feature: 0,
                        threshold: 1.0,
                        left: 1,
                        right: 2,
                    },
                    LogicalTreeNode::Leaf { value: 0.0 },
                    LogicalTreeNode::Leaf { value: 1.0 },
                    LogicalTreeNode::Leaf { value: 2.0 },
                ],
                2,
            ),
        ];
        for (name, nodes, n_features) in cases {
            assert_eq!(
                PackedTree::from_logical_nodes(&nodes, n_features),
                Err(ArtifactError::InvalidPayload),
                "{name} was accepted"
            );
        }
        assert_eq!(
            PackedTree::from_logical_nodes(&valid, 0),
            Err(ArtifactError::InvalidPayload)
        );
    }

    /// Build nodes for the smallest shape whose pre-order leaf rank and runtime
    /// leaf ordinal disagree.
    ///
    /// The root's left child is a branch and its right child is a leaf:
    ///
    /// ```text
    ///           b0                     pre-order rank   runtime ordinal
    ///          /  \
    ///        b1    L2   (f0 > 1)       L2 -> 2          L2 -> 0
    ///       /  \
    ///     L0    L1                     L0 -> 0          L0 -> 1
    ///                                  L1 -> 1          L1 -> 2
    /// ```
    ///
    /// Pre-order rank counts leaves in the order the records appear. Packing
    /// assigns ordinals branch by branch — `b0` is visited first and encodes its
    /// right leaf before `b1` encodes either of its own — so the root's right
    /// leaf is ordinal `0` while it is the *last* leaf in pre-order. A balanced
    /// tree cannot show this: there the two orders coincide, which is why every
    /// shape used until now could not tell a correct implementation from one
    /// consistently wrong in both directions.
    fn skewed_class_build() -> Vec<BuildNode> {
        vec![
            branch(0, 1.0, 1, 4),
            branch(1, 2.0, 2, 3),
            BuildNode::leaf(0.0),
            BuildNode::leaf(0.0),
            BuildNode::leaf(0.0),
        ]
    }

    /// The leaf probability rows of [`skewed_class_build`], in pre-order rank.
    ///
    /// Every value is exactly representable in both `f64` and `f32`, so nothing
    /// below is a tolerance.
    const PRE_ORDER_BLOCK: [f32; 6] = [0.25, 0.75, 0.5, 0.5, 0.125, 0.875];

    /// A feature row reaching each leaf, in the same pre-order.
    const ROWS_BY_PRE_ORDER_RANK: [[f32; 2]; 3] = [[0.0, 0.0], [0.0, 9.0], [9.0, 0.0]];

    fn skewed_class_tree() -> ClassTree {
        let mut class_weights = vec![0.0_f64; 5 * 2];
        class_weights[2 * 2..2 * 2 + 2].copy_from_slice(&[0.25, 0.75]);
        class_weights[3 * 2..3 * 2 + 2].copy_from_slice(&[0.5, 0.5]);
        class_weights[4 * 2..4 * 2 + 2].copy_from_slice(&[0.125, 0.875]);
        ClassTree::from_build_nodes(skewed_class_build(), &class_weights, &[1.0; 5], 2, 2).unwrap()
    }

    /// The artifact's leaf block really is ordered by pre-order rank, on a shape
    /// where that is a different order from the one the tree stores.
    ///
    /// A round trip cannot establish this. Encoding and decoding are inverses,
    /// so a pair that agreed on the *runtime ordinal* instead would round-trip
    /// just as cleanly and write different bytes for the same model — the
    /// malleability the pre-order rule exists to prevent. Each direction is
    /// therefore anchored to something outside the pair: the encoder to what the
    /// tree returns at runtime for a row reaching each leaf, and the decoder to a
    /// block written out here by hand rather than taken from the encoder.
    ///
    /// Measured by making both directions read runtime ordinals: the round-trip
    /// test next door stays green, as do `tests/reference_semantics.rs` and
    /// `tests/artifact_fingerprints.rs`, and this test fails. One other test
    /// notices — `the_frozen_adversarial_corpus_decodes_exactly_as_recorded`,
    /// whose `multiclass-extra-trees-probability-out-of-range` fixture happens
    /// to hold a skewed class tree — but it reports only that checked-in bytes
    /// and rebuilt bytes disagree, which names no invariant and would be
    /// silenced by regenerating the corpus.
    #[test]
    fn the_class_leaf_block_is_ordered_by_pre_order_rank_not_by_runtime_ordinal() {
        let tree = skewed_class_tree();

        // The premise: the tree stores its rows in runtime-ordinal order, which
        // on this shape is the last leaf first. If this ever equals
        // `PRE_ORDER_BLOCK` the shape has stopped discriminating and everything
        // below would hold vacuously.
        assert_eq!(tree.probabilities, vec![0.125, 0.875, 0.25, 0.75, 0.5, 0.5]);
        assert_ne!(tree.probabilities, PRE_ORDER_BLOCK.to_vec());

        // The runtime anchor: which row reaches which distribution.
        for (rank, row) in ROWS_BY_PRE_ORDER_RANK.iter().enumerate() {
            assert_eq!(
                tree.probabilities(row),
                &PRE_ORDER_BLOCK[rank * 2..rank * 2 + 2],
                "row {row:?} does not reach pre-order leaf {rank}"
            );
        }

        // Encoding: the block is the runtime distributions in pre-order, and the
        // records place their leaves at the pre-order positions.
        let (records, block) = tree.to_logical_nodes();
        assert_eq!(block, PRE_ORDER_BLOCK.to_vec());
        assert_eq!(
            records
                .iter()
                .enumerate()
                .filter(|(_, node)| matches!(node, LogicalTreeNode::Leaf { .. }))
                .map(|(index, _)| index)
                .collect::<Vec<_>>(),
            vec![2, 3, 4]
        );

        // Decoding: from a block written here, in pre-order, not from `block`.
        let decoded = ClassTree::from_logical_nodes(&records, &PRE_ORDER_BLOCK, 2, 2).unwrap();
        assert_eq!(decoded, tree);
        for (rank, row) in ROWS_BY_PRE_ORDER_RANK.iter().enumerate() {
            assert_eq!(
                decoded.probabilities(row),
                &PRE_ORDER_BLOCK[rank * 2..rank * 2 + 2],
                "decoded row {row:?} does not reach pre-order leaf {rank}"
            );
        }

        // And the same block read as runtime ordinals would produce a different
        // model, which is what makes the choice of order observable rather than
        // a convention two symmetric halves could share.
        let as_ordinals: Vec<f32> = tree.probabilities.clone();
        let misread = ClassTree::from_logical_nodes(&records, &as_ordinals, 2, 2).unwrap();
        assert_ne!(misread, tree);
    }

    #[test]
    fn deep_left_spines_convert_without_recursing() {
        let depth = 4_096;
        let mut build = Vec::with_capacity(depth * 2 + 1);
        for index in 0..depth {
            build.push(branch(
                0,
                0.5,
                (index + 1) as u32,
                (depth * 2 - index) as u32,
            ));
        }
        build.push(BuildNode::leaf(7.0));
        build.extend((0..depth).map(|_| BuildNode::leaf(-1.0)));
        let tree = PackedTree::from_build_nodes(build, 1).unwrap();
        let logical = tree.to_logical_nodes();
        assert_eq!(logical.len(), depth * 2 + 1);
        assert_eq!(PackedTree::from_logical_nodes(&logical, 1).unwrap(), tree);
    }
}