mlt_core/encoder/
optimizer.rs

1use bitvec::vec::BitVec;
2
3use crate::decoder::Morton;
4use crate::encoder::model::{CurveParams, StagedLayer};
5use crate::encoder::{
6    Codecs, Encoder, EncoderConfig, SortStrategy, encode01, spatial_sort_likely_to_help,
7};
8#[cfg(feature = "unstable-v2")]
9use crate::encoder::{WireVersion, encode02};
10use crate::tile::{PropKind, TileLayer};
11use crate::{MltError, MltResult, PropValue};
12
13impl StagedLayer {
14    /// Encode and serialize the layer directly into `enc`, without creating any
15    /// intermediate representation.
16    ///
17    /// This is the hot path inside `TileLayer::encode`: each sort-strategy
18    /// trial calls this method on its own fresh `Encoder`, and only the
19    /// `Encoder` with the smallest `total_len()` is kept.
20    #[hotpath::measure]
21    pub fn encode_into(self, enc: Encoder, codecs: &mut Codecs) -> MltResult<Encoder> {
22        if self.name.is_empty() {
23            return Err(MltError::MissingLayerName);
24        }
25        #[cfg(feature = "unstable-v2")]
26        match enc.config().wire_version() {
27            WireVersion::V01 => encode01::encode_into01(self, enc, codecs),
28            WireVersion::V02 => encode02::encode_into02(self, enc, codecs),
29        }
30        #[cfg(not(feature = "unstable-v2"))]
31        encode01::encode_into01(self, enc, codecs)
32    }
33}
34
35/// Seed the encoder's curve-derived caches so the Hilbert/Morton dictionary
36/// builders skip their min/max scan. `Morton::new` returns `Err` when bits > 16;
37/// `dict_may_be_beneficial` reads `morton_cache.is_none()` and falls back to
38/// a Vec2-only path in that case.
39fn seed_curve_caches(enc: &mut Encoder, curve_params: CurveParams) {
40    enc.hilbert_cache = Some(curve_params);
41    enc.morton_cache = Morton::new(curve_params.bits, curve_params.shift).ok();
42}
43
44/// Feature-count threshold above which the spatial trial is subject to the
45/// bounding-box pruning heuristic.
46const SORT_TRIAL_THRESHOLD: usize = 512;
47
48impl TileLayer {
49    /// Encode a [`TileLayer`] to bytes, automatically optimizing all encoding choices.
50    ///
51    /// This is the primary encoding entry point. It:
52    /// 1. Determines which sort strategies to try based on `cfg`
53    /// 2. Tries each sort strategy, encoding and measuring the output size
54    /// 3. Returns the smallest encoding as a complete layer record (including tag and length prefix)
55    ///
56    /// All encoding choices - sort order, per-stream integer encodings, string compression,
57    /// vertex buffer layout - are selected automatically to minimize output size.
58    #[hotpath::measure]
59    pub fn encode(self, cfg: EncoderConfig) -> MltResult<Vec<u8>> {
60        if self.name().is_empty() {
61            return Err(MltError::MissingLayerName);
62        }
63        if self.features().is_empty() {
64            return Ok(Vec::new());
65        }
66
67        let mut sort_by = vec![SortStrategy::Unsorted];
68        let try_spatial_sort =
69            cfg.attempt_spatial_morton_sort() || cfg.attempt_spatial_hilbert_sort();
70        if try_spatial_sort
71            && (self.feature_count() < SORT_TRIAL_THRESHOLD || spatial_sort_likely_to_help(&self))
72        {
73            if cfg.attempt_spatial_morton_sort() {
74                sort_by.push(SortStrategy::SpatialMorton);
75            }
76            if cfg.attempt_spatial_hilbert_sort() {
77                sort_by.push(SortStrategy::SpatialHilbert);
78            }
79        }
80        if cfg.attempt_id_sort() {
81            sort_by.push(SortStrategy::Id);
82        }
83
84        let stats = self.analyze(cfg.allow_shared_dict())?;
85        // Bounds are order-invariant, so this scan is shared across every
86        // sort trial and the encoder's Hilbert/Morton dictionary builders.
87        let curve_params = self.curve_params();
88
89        // `Encoder::preserve_results` clears caches only on the moved-out
90        // archive, so a single seeding here serves every trial that reuses
91        // `enc`.
92        let mut enc = Encoder::new(cfg);
93        seed_curve_caches(&mut enc, curve_params);
94
95        let (last, init) = sort_by.split_last().expect("at least one strategy");
96        if init.is_empty() {
97            let mut codecs = Codecs::default();
98            StagedLayer::from_tile(self, *last, &stats, cfg.tessellate(), curve_params)
99                .encode_into(enc, &mut codecs)?
100        } else {
101            let mut codecs = Codecs::default();
102            enc = {
103                let first = init[0];
104                StagedLayer::from_tile(self.clone(), first, &stats, cfg.tessellate(), curve_params)
105                    .encode_into(enc, &mut codecs)?
106            };
107            let mut best = enc.preserve_results();
108            // Clone for all-but-last strategies
109            for &sort in &init[1..] {
110                let layer = StagedLayer::from_tile(
111                    self.clone(),
112                    sort,
113                    &stats,
114                    cfg.tessellate(),
115                    curve_params,
116                );
117                enc = layer.encode_into(enc, &mut codecs)?;
118                if enc.total_len() < best.total_len() {
119                    best = enc.preserve_results();
120                } else {
121                    // Drop the losing trial's bytes, or the next trial would append to them and overcount its total_len.
122                    enc.clear_results();
123                }
124            }
125            // Last strategy: consume self, no clone
126            let layer = StagedLayer::from_tile(self, *last, &stats, cfg.tessellate(), curve_params);
127            enc = layer.encode_into(enc, &mut codecs)?;
128            if enc.total_len() < best.total_len() {
129                best = enc.preserve_results();
130            }
131            best
132        }
133        .into_layer_bytes()
134    }
135}
136
137/// Row-order-independent presence classification for IDs and properties.
138#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139pub enum Presence {
140    /// No feature has a value for this logical column.
141    AllNull,
142    /// Every feature has a value for this logical column.
143    AllPresent,
144    /// Some, but not all, features have a value for this logical column.
145    Mixed,
146    /// Mixed presence with the same per-feature mask as an earlier property column.
147    ///
148    /// Only tells the stager the column is nullable, same as [`Self::Mixed`]. Which
149    /// columns actually end up sharing one presence bitfield is decided per wire
150    /// format at write time, from the staged masks - see `SharedPresence` in
151    /// `encoder::encode02`.
152    SameAsProp(usize),
153}
154impl Presence {
155    /// Create presence value
156    #[must_use]
157    pub fn from_bits(bits: &BitVec<u8>, existing: &[(BitVec<u8>, usize)]) -> Self {
158        if bits.not_any() {
159            Self::AllNull
160        } else if bits.all() {
161            Self::AllPresent
162        } else if let Some((_, idx)) = existing.iter().find(|(v, _)| v == bits) {
163            Self::SameAsProp(*idx)
164        } else {
165            Self::Mixed
166        }
167    }
168}
169
170/// How a property participates in a shared dictionary group.
171#[derive(Debug, Clone, PartialEq, Eq)]
172pub enum SharedDictRole {
173    /// The property is encoded as a standalone column.
174    None,
175    /// The property is the first column in this group and emits the shared dictionary with this prefix.
176    Owner(String),
177    /// The property is emitted by the group owner at this property index.
178    Member(usize),
179}
180
181/// Row-order-independent facts for a single property column.
182#[derive(Debug, Clone, PartialEq, Eq)]
183pub struct PropertyStats {
184    pub presence: Presence,
185    pub stats: PropertyTypedStats,
186}
187
188/// Row-order-independent layer facts computed once before sort trials.
189#[derive(Debug, Clone, PartialEq, Eq)]
190pub struct LayerStats {
191    pub id: Option<PropertyStats>,
192    pub properties: Vec<PropertyStats>,
193}
194
195/// Row-order-independent value statistics for a property column.
196#[derive(Debug, Clone, Default, PartialEq, Eq)]
197pub enum PropertyTypedStats {
198    /// No present values.
199    #[default]
200    None,
201    Bool,
202    Signed {
203        min: i64,
204        max: i64,
205    },
206    Unsigned {
207        min: u64,
208        max: u64,
209    },
210    F32,
211    F64,
212    String {
213        shared_dict: SharedDictRole,
214    },
215}
216
217impl PropertyTypedStats {
218    #[must_use]
219    pub fn values_fit_u32(&self) -> bool {
220        match self {
221            Self::None | Self::Bool | Self::F32 | Self::F64 | Self::String { .. } => false,
222            Self::Signed { min, max } => *min >= 0 && u32::try_from(*max).is_ok(),
223            Self::Unsigned { max, .. } => u32::try_from(*max).is_ok(),
224        }
225    }
226
227    /// Returns `true` if every value fits in an `i32`.
228    /// Unlike [`Self::values_fit_u32`] this admits negative values.
229    #[must_use]
230    pub fn values_fit_i32(&self) -> bool {
231        match self {
232            Self::None | Self::Bool | Self::F32 | Self::F64 | Self::String { .. } => false,
233            Self::Signed { min, max } => i32::try_from(*min).is_ok() && i32::try_from(*max).is_ok(),
234            Self::Unsigned { max, .. } => i32::try_from(*max).is_ok(),
235        }
236    }
237
238    #[must_use]
239    pub fn shared_dict(&self) -> SharedDictRole {
240        match self {
241            Self::String { shared_dict, .. } => shared_dict.clone(),
242            Self::None
243            | Self::Bool
244            | Self::Signed { .. }
245            | Self::Unsigned { .. }
246            | Self::F32
247            | Self::F64 => SharedDictRole::None,
248        }
249    }
250
251    pub(crate) fn set_shared_dict(&mut self, role: SharedDictRole) {
252        match self {
253            Self::String { shared_dict, .. } => *shared_dict = role,
254            Self::None
255            | Self::Bool
256            | Self::Signed { .. }
257            | Self::Unsigned { .. }
258            | Self::F32
259            | Self::F64 => debug_assert_eq!(role, SharedDictRole::None),
260        }
261    }
262
263    pub(crate) fn push(
264        &mut self,
265        prop: &PropValue,
266        column_idx: usize,
267        property_name: &str,
268    ) -> MltResult<bool> {
269        match prop {
270            PropValue::Bool(Some(_)) => {
271                self.merge_same_kind(Self::Bool, column_idx, property_name)?;
272            }
273            PropValue::I8(Some(v)) => {
274                self.merge_signed(i64::from(*v), column_idx, property_name)?;
275            }
276            PropValue::U8(Some(v)) => {
277                self.merge_unsigned(u64::from(*v), column_idx, property_name)?;
278            }
279            PropValue::I32(Some(v)) => {
280                self.merge_signed(i64::from(*v), column_idx, property_name)?;
281            }
282            PropValue::U32(Some(v)) => {
283                self.merge_unsigned(u64::from(*v), column_idx, property_name)?;
284            }
285            PropValue::I64(Some(v)) => self.merge_signed(*v, column_idx, property_name)?,
286            PropValue::U64(Some(v)) => self.merge_unsigned(*v, column_idx, property_name)?,
287            PropValue::F32(Some(_)) => {
288                self.merge_same_kind(Self::F32, column_idx, property_name)?;
289            }
290            PropValue::F64(Some(_)) => {
291                self.merge_same_kind(Self::F64, column_idx, property_name)?;
292            }
293            PropValue::Str(Some(_)) => self.merge_string(column_idx, property_name)?,
294            PropValue::Bool(None)
295            | PropValue::I8(None)
296            | PropValue::U8(None)
297            | PropValue::I32(None)
298            | PropValue::U32(None)
299            | PropValue::I64(None)
300            | PropValue::U64(None)
301            | PropValue::F32(None)
302            | PropValue::F64(None)
303            | PropValue::Str(None) => return Ok(false),
304        }
305        Ok(true)
306    }
307
308    fn merge_signed(
309        &mut self,
310        value: i64,
311        column_idx: usize,
312        property_name: &str,
313    ) -> MltResult<()> {
314        match self {
315            Self::None => {
316                *self = Self::Signed {
317                    min: value,
318                    max: value,
319                };
320            }
321            Self::Signed { min, max } => {
322                *min = (*min).min(value);
323                *max = (*max).max(value);
324            }
325            Self::Bool | Self::Unsigned { .. } | Self::F32 | Self::F64 | Self::String { .. } => {
326                return mixed_prop_err(column_idx, property_name);
327            }
328        }
329        Ok(())
330    }
331
332    fn merge_unsigned(
333        &mut self,
334        value: u64,
335        column_idx: usize,
336        property_name: &str,
337    ) -> MltResult<()> {
338        match self {
339            Self::None => {
340                *self = Self::Unsigned {
341                    min: value,
342                    max: value,
343                };
344            }
345            Self::Unsigned { min, max } => {
346                *min = (*min).min(value);
347                *max = (*max).max(value);
348            }
349            Self::Bool | Self::Signed { .. } | Self::F32 | Self::F64 | Self::String { .. } => {
350                return mixed_prop_err(column_idx, property_name);
351            }
352        }
353        Ok(())
354    }
355
356    fn merge_string(&mut self, column_idx: usize, property_name: &str) -> MltResult<()> {
357        match self {
358            Self::None => {
359                *self = Self::String {
360                    shared_dict: SharedDictRole::None,
361                };
362            }
363            Self::String { .. } => {}
364            Self::Bool | Self::Signed { .. } | Self::Unsigned { .. } | Self::F32 | Self::F64 => {
365                return mixed_prop_err(column_idx, property_name);
366            }
367        }
368        Ok(())
369    }
370
371    fn merge_same_kind(
372        &mut self,
373        kind: Self,
374        column_idx: usize,
375        property_name: &str,
376    ) -> MltResult<()> {
377        match self {
378            Self::None => *self = kind,
379            Self::Bool if matches!(kind, Self::Bool) => {}
380            Self::F32 if matches!(kind, Self::F32) => {}
381            Self::F64 if matches!(kind, Self::F64) => {}
382            Self::Bool
383            | Self::Signed { .. }
384            | Self::Unsigned { .. }
385            | Self::F32
386            | Self::F64
387            | Self::String { .. } => return mixed_prop_err(column_idx, property_name),
388        }
389        Ok(())
390    }
391}
392
393impl TileLayer {
394    /// Analyze a [`TileLayer`] and return reusable ID/property facts for the optimizer.
395    #[hotpath::measure]
396    pub(crate) fn analyze(&self, allow_shared_dict: bool) -> MltResult<LayerStats> {
397        let mut property_bits = Vec::with_capacity(self.property_names().len());
398        let mut properties = self.analyze_properties(&mut property_bits)?;
399        let id = self.analyze_ids(&property_bits);
400        if allow_shared_dict {
401            self.group_string_properties(&mut properties);
402        }
403        Ok(LayerStats { id, properties })
404    }
405
406    fn analyze_ids(&self, property_bits: &[(BitVec<u8>, usize)]) -> Option<PropertyStats> {
407        let mut min = u64::MAX;
408        let mut max = 0u64;
409        let mut bits = BitVec::<u8>::with_capacity(self.feature_count());
410        for feature in self.features() {
411            if let Some(id) = feature.id() {
412                min = min.min(id);
413                max = max.max(id);
414                bits.push(true);
415            } else {
416                bits.push(false);
417            }
418        }
419        let presence = Presence::from_bits(&bits, property_bits);
420        if presence == Presence::AllNull {
421            None
422        } else {
423            Some(PropertyStats {
424                presence,
425                stats: PropertyTypedStats::Unsigned { min, max },
426            })
427        }
428    }
429
430    fn analyze_properties(
431        &self,
432        property_bits: &mut Vec<(BitVec<u8>, usize)>,
433    ) -> MltResult<Vec<PropertyStats>> {
434        self.property_names()
435            .iter()
436            .enumerate()
437            .map(|(col_idx, name)| -> MltResult<PropertyStats> {
438                let mut kind = None;
439                let mut stats = PropertyTypedStats::default();
440                let mut bits = BitVec::<u8>::with_capacity(self.feature_count());
441                for feature in self.features() {
442                    let prop = feature.properties().get(col_idx);
443                    if let Some(prop_kind) = prop.map(PropKind::from) {
444                        match kind {
445                            Some(kind) if kind != prop_kind => {
446                                return mixed_prop_err(col_idx, name.as_str());
447                            }
448                            None => kind = Some(prop_kind),
449                            _ => {}
450                        }
451                    }
452                    if let Some(prop) = prop
453                        && stats.push(prop, col_idx, name)?
454                    {
455                        bits.push(true);
456                    } else {
457                        bits.push(false);
458                    }
459                }
460
461                let presence = Presence::from_bits(&bits, property_bits);
462                if presence == Presence::Mixed {
463                    property_bits.push((bits, col_idx));
464                }
465                Ok(PropertyStats { presence, stats })
466            })
467            .collect()
468    }
469}
470
471#[inline]
472fn mixed_prop_err<T>(column_idx: usize, property_name: &str) -> MltResult<T> {
473    Err(MltError::MixedPropertyTypes(
474        column_idx,
475        property_name.to_owned(),
476    ))
477}
mlt_core/encoder/optimizer.rs

mlt_core/encoder/
optimizer.rs
