ifc_lite_landxml/plan/numeric/
parcel_probe.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use super::{
6    measure::{finite_measure, finite_sum},
7    parcel_measure::probe_loop,
8    topology::{point_in_loop, segments_intersect},
9    LandXmlParcel, LandXmlParcelProbe, LandXmlParcelState, LandXmlPlanDocument,
10    LandXmlPlanGeometry, LandXmlPlanPoint, LandXmlPlanPointLocation, LandXmlPlanResolver,
11    ParcelProbeWork,
12};
13use crate::plan::parser::area_scale;
14
15const MAX_PARCEL_TOPOLOGY_EDGES: usize = 700;
16const MAX_PARCEL_TOPOLOGY_WORK: usize = 1_000_000;
17
18struct TopologyBudget<'a> {
19    work: usize,
20    max_work: usize,
21    cancelled: Option<&'a dyn crate::LandXmlCancellation>,
22}
23
24impl TopologyBudget<'_> {
25    fn check(&mut self) -> std::result::Result<(), crate::LandXmlError> {
26        if self
27            .cancelled
28            .is_some_and(crate::LandXmlCancellation::is_cancelled)
29        {
30            return Err(crate::LandXmlError::new(
31                crate::LandXmlDiagnosticCode::Cancelled,
32                "parcel probe cancelled",
33            ));
34        }
35        self.work = self.work.checked_add(1).ok_or_else(|| {
36            crate::LandXmlError::new(
37                crate::LandXmlDiagnosticCode::LimitExceeded,
38                "parcel topology work limit exceeded",
39            )
40        })?;
41        if self.work > self.max_work {
42            return Err(crate::LandXmlError::new(
43                crate::LandXmlDiagnosticCode::LimitExceeded,
44                "parcel topology work limit exceeded",
45            ));
46        }
47        Ok(())
48    }
49}
50
51impl ParcelProbeWork for TopologyBudget<'_> {
52    fn check(&mut self) -> std::result::Result<(), crate::LandXmlError> {
53        TopologyBudget::check(self)
54    }
55
56    fn resolve(
57        &mut self,
58        document: &LandXmlPlanDocument,
59        scope: Option<&crate::LandXmlSourceId>,
60        location: &LandXmlPlanPointLocation,
61    ) -> std::result::Result<Option<LandXmlPlanPoint>, crate::LandXmlError> {
62        document.resolve_point_with_work(scope, location, self)
63    }
64}
65
66/// Combines the document-wide reference cache with a deliberately local parcel
67/// topology budget. A complex parcel cannot spend the resolver work reserved
68/// for later monuments, geometry, or sibling parcels.
69struct BulkParcelProbe<'resolver, 'document> {
70    resolver: &'resolver mut LandXmlPlanResolver<'document>,
71    topology: TopologyBudget<'static>,
72    topology_exhausted: bool,
73}
74
75impl<'resolver, 'document> BulkParcelProbe<'resolver, 'document> {
76    fn new(resolver: &'resolver mut LandXmlPlanResolver<'document>, max_work: usize) -> Self {
77        Self {
78            resolver,
79            topology: TopologyBudget {
80                work: 0,
81                max_work,
82                cancelled: None,
83            },
84            topology_exhausted: false,
85        }
86    }
87}
88
89impl ParcelProbeWork for BulkParcelProbe<'_, '_> {
90    fn check(&mut self) -> std::result::Result<(), crate::LandXmlError> {
91        let result = self.topology.check();
92        if result
93            .as_ref()
94            .is_err_and(|error| error.code == crate::LandXmlDiagnosticCode::LimitExceeded)
95        {
96            self.topology_exhausted = true;
97        }
98        result
99    }
100
101    fn resolve(
102        &mut self,
103        _document: &LandXmlPlanDocument,
104        scope: Option<&crate::LandXmlSourceId>,
105        location: &LandXmlPlanPointLocation,
106    ) -> std::result::Result<Option<LandXmlPlanPoint>, crate::LandXmlError> {
107        self.resolver.resolve(scope, location)
108    }
109}
110
111impl LandXmlPlanDocument {
112    /// Probe a parcel in authored units with the default topology work bound.
113    pub fn probe_parcel(&self, parcel: &LandXmlParcel) -> LandXmlParcelProbe {
114        self.probe_parcel_with_cancel(parcel, 1_000_000, None)
115            .unwrap_or_else(|error| preserved(parcel, &error.message))
116    }
117
118    /// Probe a parcel while polling cancellation inside pairwise topology work.
119    pub fn probe_parcel_with_cancel(
120        &self,
121        parcel: &LandXmlParcel,
122        max_topology_work: usize,
123        cancelled: Option<&dyn crate::LandXmlCancellation>,
124    ) -> std::result::Result<LandXmlParcelProbe, crate::LandXmlError> {
125        let mut budget = TopologyBudget {
126            work: 0,
127            max_work: max_topology_work,
128            cancelled,
129        };
130        probe_parcel_with_work(self, parcel, &mut budget)
131    }
132
133    /// Probe many parcels through one document-scoped resolver. Alias
134    /// resolution is aggregate and path-compressed across the document, while
135    /// each parcel gets a checked topology bound. This keeps a pathological
136    /// boundary local to its source record rather than starving its siblings.
137    pub fn probe_parcels_with_resolver(
138        &self,
139        parcels: &[LandXmlParcel],
140        resolver: &mut LandXmlPlanResolver<'_>,
141    ) -> std::result::Result<Vec<LandXmlParcelProbe>, crate::LandXmlError> {
142        let mut probes = Vec::with_capacity(parcels.len());
143        for parcel in parcels {
144            let Some(max_topology_work) = parcel_topology_budget(parcel) else {
145                probes.push(preserved(parcel, "parcel topology work limit exceeded"));
146                continue;
147            };
148            let mut work = BulkParcelProbe::new(resolver, max_topology_work);
149            match probe_parcel_with_work(self, parcel, &mut work) {
150                Ok(probe) => probes.push(probe),
151                Err(_) if work.topology_exhausted => {
152                    probes.push(preserved(parcel, "parcel topology work limit exceeded"));
153                }
154                // Resolver limits and cancellation are document-level states:
155                // never mislabel them as an individual parcel refusal.
156                Err(error)
157                    if matches!(
158                        error.code,
159                        crate::LandXmlDiagnosticCode::LimitExceeded
160                            | crate::LandXmlDiagnosticCode::Cancelled
161                    ) =>
162                {
163                    return Err(error);
164                }
165                Err(error) => probes.push(preserved(parcel, &error.message)),
166            }
167        }
168        Ok(probes)
169    }
170}
171
172/// Bound the existing exact pairwise topology checks before they allocate or
173/// traverse an adversarial boundary. Two scans cost at most `2n² + 3n` for n
174/// generated edges; extra slack covers loop bookkeeping. Curve edges are
175/// deterministically capped at 64, while irregular-line vertices are counted
176/// exactly. A checked cap keeps this arithmetic and the later edge vectors
177/// bounded even for malformed, enormous input.
178fn parcel_topology_budget(parcel: &LandXmlParcel) -> Option<usize> {
179    let mut edges = 0usize;
180    for geometry in parcel.loops.iter().flatten() {
181        let geometry_edges = match geometry.kind {
182            super::LandXmlGeometryKind::Line => 1,
183            super::LandXmlGeometryKind::Curve => 64,
184            super::LandXmlGeometryKind::IrregularLine => {
185                geometry.intermediate_points.len().checked_add(1)?
186            }
187        };
188        edges = edges.checked_add(geometry_edges)?;
189        if edges > MAX_PARCEL_TOPOLOGY_EDGES {
190            return None;
191        }
192    }
193    let work = edges
194        .checked_mul(edges)?
195        .checked_mul(2)?
196        .checked_add(edges.checked_mul(4)?)?
197        .checked_add(64)?;
198    (work <= MAX_PARCEL_TOPOLOGY_WORK).then_some(work)
199}
200
201fn probe_parcel_with_work<W: ParcelProbeWork>(
202    document: &LandXmlPlanDocument,
203    parcel: &LandXmlParcel,
204    work: &mut W,
205) -> std::result::Result<LandXmlParcelProbe, crate::LandXmlError> {
206    if let Some(reason) = &parcel.preservation_reason {
207        return Ok(preserved(parcel, reason));
208    }
209    // Curve edges are sampled only to reject self-intersection within the one
210    // supported arc-plus-chord loop. Those chords are not an exact predicate
211    // for crossings against another loop, so never fabricate a filled parcel
212    // from multi-loop curve topology. A future analytic line/arc and arc/arc
213    // intersection kernel may relax this deliberately conservative boundary.
214    if parcel.loops.len() > 1
215        && parcel
216            .loops
217            .iter()
218            .flatten()
219            .any(|geometry| geometry.kind == super::LandXmlGeometryKind::Curve)
220    {
221        return Ok(preserved(parcel, "multi-loop boundary with curves"));
222    }
223    let mut perimeter = 0.0;
224    // Per loop: |twice signed area| and its edge range in `all_segments`.
225    let mut loop_areas = Vec::with_capacity(parcel.loops.len());
226    let mut all_segments = Vec::new();
227    for loop_geometry in &parcel.loops {
228        if !supports_analytic_curve_loop(loop_geometry) {
229            return Ok(preserved(parcel, "unsupported curved boundary topology"));
230        }
231        let Some(loop_probe) = probe_loop(document, loop_geometry, work)? else {
232            return Ok(preserved(parcel, "open or unresolved boundary"));
233        };
234        if loop_probe.self_intersects {
235            return Ok(preserved(parcel, "self-intersecting boundary"));
236        }
237        perimeter = finite_sum(perimeter, loop_probe.perimeter)?;
238        if segments_intersect(&all_segments, &loop_probe.segments, work)? {
239            return Ok(preserved(parcel, "cross-loop or retraced boundary"));
240        }
241        let start = all_segments.len();
242        all_segments.extend(loop_probe.segments);
243        loop_areas.push((loop_probe.twice_area.abs(), start..all_segments.len()));
244    }
245    if parcel.loops.is_empty() {
246        return Ok(preserved(parcel, "missing CoordGeom boundary"));
247    }
248    // #5179 (maintainer ruling): winding carries no meaning for parcel loops.
249    // Loops cannot cross or touch (checked above), so each lies wholly inside
250    // or outside every other. A loop nested inside an odd number of the
251    // parcel's other loops is a hole; every other loop is a filled part, so
252    // disjoint loops add whatever their winding.
253    let mut twice_area = 0.0;
254    for (index, (area, range)) in loop_areas.iter().enumerate() {
255        let probe_point = all_segments[range.start].0;
256        let mut is_hole = false;
257        for (other_index, (_, other)) in loop_areas.iter().enumerate() {
258            if other_index != index
259                && point_in_loop(probe_point, &all_segments[other.clone()], work)?
260            {
261                is_hole = !is_hole;
262            }
263        }
264        let signed = if is_hole { -*area } else { *area };
265        twice_area = finite_sum(twice_area, signed)?;
266    }
267    if twice_area <= 0.0 {
268        return Ok(preserved(parcel, "zero-area boundary"));
269    }
270    let coordinate_area = finite_measure(twice_area.abs() * 0.5)?;
271    let (perimeter_in_meters, area_in_square_meters, area_in_declared_square_units) =
272        match &document.units {
273            Some(units) => {
274                let square_meters =
275                    finite_measure(coordinate_area * units.linear_scale_to_meters.powi(2))?;
276                let declared_scale = match parcel.declared_area_unit.as_deref() {
277                    Some(unit) => match area_scale(unit) {
278                        Ok(scale) => scale,
279                        Err(_) => return Ok(preserved(parcel, "unsupported parcel area unit")),
280                    },
281                    None => document
282                        .area_scale_to_square_meters
283                        .unwrap_or(units.linear_scale_to_meters.powi(2)),
284                };
285                if !declared_scale.is_finite() || declared_scale <= 0.0 {
286                    return Ok(preserved(parcel, "invalid declared area unit scale"));
287                }
288                (
289                    Some(finite_measure(perimeter * units.linear_scale_to_meters)?),
290                    Some(square_meters),
291                    Some(finite_measure(square_meters / declared_scale)?),
292                )
293            }
294            None if parcel.declared_area_unit.is_some() => {
295                return Ok(preserved(
296                    parcel,
297                    "parcel area unit requires document linear units",
298                ));
299            }
300            None => (None, None, Some(coordinate_area)),
301        };
302    Ok(LandXmlParcelProbe {
303        state: LandXmlParcelState::Analytic,
304        perimeter_in_declared_linear_units: Some(perimeter),
305        area_in_declared_square_units,
306        declared_area: parcel.declared_area,
307        declared_perimeter: parcel.declared_perimeter,
308        perimeter_in_meters,
309        area_in_square_meters,
310    })
311}
312
313/// Curved parcel measurement is exact only for a circular arc and its one
314/// straight closing chord. An `IrregularLine` may expand to arbitrary segments
315/// that sampled curve edges cannot validate, so it is intentionally never a
316/// fill-capable companion to a curve. Resolved endpoint continuity is checked
317/// by `probe_loop`, which accepts either authored record order/direction.
318fn supports_analytic_curve_loop(geometry: &[LandXmlPlanGeometry]) -> bool {
319    let curve_count = geometry
320        .iter()
321        .filter(|item| item.kind == super::LandXmlGeometryKind::Curve)
322        .count();
323    curve_count == 0
324        || (geometry.len() == 2
325            && curve_count == 1
326            && geometry
327                .iter()
328                .any(|item| item.kind == super::LandXmlGeometryKind::Line))
329}
330
331fn preserved(parcel: &LandXmlParcel, reason: &str) -> LandXmlParcelProbe {
332    LandXmlParcelProbe {
333        state: LandXmlParcelState::PreservedOnly {
334            reason: reason.to_owned(),
335        },
336        perimeter_in_declared_linear_units: None,
337        area_in_declared_square_units: None,
338        declared_area: parcel.declared_area,
339        declared_perimeter: parcel.declared_perimeter,
340        perimeter_in_meters: None,
341        area_in_square_meters: None,
342    }
343}
ifc_lite_landxml/plan/numeric/parcel_probe.rs

ifc_lite_landxml/plan/numeric/
parcel_probe.rs
