maxminddb/
within.rs

1//! Network iteration types.
2
3use std::cmp::Ordering;
4use std::net::{IpAddr, Ipv6Addr};
5
6use crate::decoder;
7use crate::error::MaxMindDbError;
8use crate::reader::Reader;
9use crate::result::{LookupResult, LookupSource, NetworkKind};
10
11/// Options for network iteration.
12///
13/// Controls which networks are yielded when iterating over the database
14/// with [`Reader::within()`] or [`Reader::networks()`].
15///
16/// # Example
17///
18/// ```
19/// use maxminddb::WithinOptions;
20///
21/// // Default options (skip aliases, skip networks without data, include empty values)
22/// let opts = WithinOptions::default();
23///
24/// // Include aliased networks (IPv4 networks via IPv6 aliases)
25/// let opts = WithinOptions::default().include_aliased_networks();
26///
27/// // Skip empty values and include networks without data
28/// let opts = WithinOptions::default()
29///     .skip_empty_values()
30///     .include_networks_without_data();
31/// ```
32#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
33pub struct WithinOptions {
34    /// Include IPv4 networks multiple times when accessed via IPv6 aliases.
35    include_aliased_networks: bool,
36    /// Include networks that have no associated data record.
37    include_networks_without_data: bool,
38    /// Skip networks whose data is an empty map or empty array.
39    skip_empty_values: bool,
40}
41
42impl WithinOptions {
43    /// Include IPv4 networks multiple times when accessed via IPv6 aliases.
44    ///
45    /// In IPv6 databases, IPv4 networks are stored at `::0/96`. However, the
46    /// same data is accessible through several IPv6 prefixes (e.g.,
47    /// `::ffff:0:0/96` for IPv4-mapped IPv6). By default, these aliases are
48    /// skipped to avoid yielding the same network multiple times.
49    ///
50    /// When enabled, the iterator will yield these aliased networks.
51    #[must_use]
52    pub fn include_aliased_networks(mut self) -> Self {
53        self.include_aliased_networks = true;
54        self
55    }
56
57    /// Include networks that have no associated data record.
58    ///
59    /// Some tree nodes point to "no data" (the node_count sentinel). By default
60    /// these are skipped. When enabled, these networks are yielded and
61    /// [`LookupResult::has_data()`] returns `false` for them.
62    #[must_use]
63    pub fn include_networks_without_data(mut self) -> Self {
64        self.include_networks_without_data = true;
65        self
66    }
67
68    /// Skip networks whose data is an empty map or empty array.
69    ///
70    /// Some databases store empty maps `{}` or empty arrays `[]` for records
71    /// without meaningful data. This option filters them out.
72    #[must_use]
73    pub fn skip_empty_values(mut self) -> Self {
74        self.skip_empty_values = true;
75        self
76    }
77}
78
79#[derive(Debug)]
80pub(crate) struct WithinNode {
81    pub(crate) node: usize,
82    pub(crate) ip_int: IpInt,
83    pub(crate) prefix_len: usize,
84}
85
86/// Iterator over database networks matching a CIDR range.
87///
88/// Created by [`Reader::within()`](crate::Reader::within) or
89/// [`Reader::networks()`](crate::Reader::networks). Yields
90/// [`LookupResult`] for matching networks, subject to [`WithinOptions`].
91/// Matching uses the database's search-tree address space. Results are not
92/// clipped to the requested range and can include an enclosing database network.
93/// Returned networks can use a different address family than the requested CIDR.
94/// See [`Reader::within()`](crate::Reader::within) for IPv4/IPv6 representation rules.
95///
96/// Networks are yielded in depth-first order through the search tree.
97/// Use [`LookupResult::decode()`](crate::LookupResult::decode) to
98/// deserialize the data for each result.
99///
100/// # Example
101///
102/// ```
103/// use maxminddb::{Reader, WithinOptions, geoip2};
104///
105/// let reader = Reader::open_readfile("test-data/test-data/GeoIP2-City-Test.mmdb").unwrap();
106/// for result in reader.within("89.160.20.0/24".parse().unwrap(), Default::default()).unwrap() {
107///     let lookup = result.unwrap();
108///     if let Some(city) = lookup.decode::<geoip2::City>().unwrap() {
109///         println!("{}: {:?}", lookup.network().unwrap(), city.city.names.english);
110///     }
111/// }
112/// ```
113#[derive(Debug)]
114pub struct Within<'de, S: AsRef<[u8]>> {
115    pub(crate) reader: &'de Reader<S>,
116    pub(crate) node_count: usize,
117    pub(crate) has_ipv4_subtree: bool,
118    pub(crate) stack: Vec<WithinNode>,
119    pub(crate) options: WithinOptions,
120}
121
122#[derive(Debug, Clone, Copy, PartialEq, Eq)]
123pub(crate) enum IpInt {
124    V4(u32),
125    V6(u128),
126}
127
128impl IpInt {
129    pub(crate) fn new(ip_addr: IpAddr) -> Self {
130        match ip_addr {
131            IpAddr::V4(v4) => IpInt::V4(v4.into()),
132            IpAddr::V6(v6) => IpInt::V6(v6.into()),
133        }
134    }
135
136    #[inline(always)]
137    pub(crate) fn get_bit(&self, index: usize) -> bool {
138        match self {
139            IpInt::V4(ip) => (ip >> (31 - index)) & 1 == 1,
140            IpInt::V6(ip) => (ip >> (127 - index)) & 1 == 1,
141        }
142    }
143
144    #[inline(always)]
145    pub(crate) fn set_bit(&mut self, index: usize) {
146        match self {
147            IpInt::V4(ip) => *ip |= 1 << (31 - index),
148            IpInt::V6(ip) => *ip |= 1 << (127 - index),
149        }
150    }
151
152    pub(crate) fn bit_count(&self) -> usize {
153        match self {
154            IpInt::V4(_) => 32,
155            IpInt::V6(_) => 128,
156        }
157    }
158
159    pub(crate) fn is_ipv4_in_ipv6(&self) -> bool {
160        match self {
161            IpInt::V4(_) => false,
162            IpInt::V6(ip) => *ip <= 0xFFFFFFFF,
163        }
164    }
165}
166
167impl<'de, S: AsRef<[u8]>> Iterator for Within<'de, S> {
168    type Item = Result<LookupResult<'de, S>, MaxMindDbError>;
169
170    fn next(&mut self) -> Option<Self::Item> {
171        while let Some(current) = self.stack.pop() {
172            let bit_count = current.ip_int.bit_count();
173
174            // Only internal IPv4 subtrees have aliases. Terminal records can be shared.
175            if !self.options.include_aliased_networks
176                && self.has_ipv4_subtree
177                && self.reader.ipv4_start != 0
178                && current.node == self.reader.ipv4_start
179                && bit_count == 128
180                && !current.ip_int.is_ipv4_in_ipv6()
181            {
182                continue;
183            }
184
185            match current.node.cmp(&self.node_count) {
186                Ordering::Greater => {
187                    // This is a data node, emit it and we're done (until the following next call)
188                    // Resolve the pointer to a data offset
189                    let data_offset = match self.reader.resolve_data_pointer(current.node) {
190                        Ok(offset) => offset,
191                        Err(e) => return Some(Err(e)),
192                    };
193
194                    // Check if we should skip empty values
195                    if self.options.skip_empty_values {
196                        match self.is_empty_value_at(data_offset) {
197                            Ok(true) => continue, // Skip empty value
198                            Ok(false) => {}       // Not empty, proceed
199                            Err(e) => return Some(Err(e)),
200                        }
201                    }
202
203                    let network_kind = self.network_kind(&current);
204                    let ip_addr = network_ip_addr(network_kind, current.ip_int);
205
206                    return Some(Ok(LookupResult::new_found(
207                        self.reader,
208                        data_offset,
209                        current.prefix_len as u8,
210                        ip_addr,
211                        LookupSource::Iter,
212                        network_kind,
213                    )));
214                }
215                Ordering::Equal => {
216                    // Dead end (no data) - include if option is set
217                    if self.options.include_networks_without_data {
218                        let network_kind = self.network_kind(&current);
219                        let ip_addr = network_ip_addr(network_kind, current.ip_int);
220                        return Some(Ok(LookupResult::new_not_found(
221                            self.reader,
222                            current.prefix_len as u8,
223                            ip_addr,
224                            LookupSource::Iter,
225                            network_kind,
226                        )));
227                    }
228                    // Otherwise skip (current behavior)
229                }
230                Ordering::Less => {
231                    if current.prefix_len >= bit_count {
232                        return Some(Err(MaxMindDbError::invalid_database(
233                            "search tree appears to have a cycle or invalid structure (traversal exceeded the address bit length)",
234                        )));
235                    }
236                    // In order traversal of our children
237                    // right/1-bit
238                    let mut right_ip_int = current.ip_int;
239
240                    if current.prefix_len < bit_count {
241                        right_ip_int.set_bit(current.prefix_len);
242                    }
243
244                    self.push_child(current.node, 1, right_ip_int, current.prefix_len + 1);
245                    // left/0-bit
246                    self.push_child(current.node, 0, current.ip_int, current.prefix_len + 1);
247                }
248            }
249        }
250        None
251    }
252}
253
254impl<'de, S: AsRef<[u8]>> Within<'de, S> {
255    #[inline(always)]
256    fn network_kind(&self, node: &WithinNode) -> NetworkKind {
257        match node.ip_int {
258            IpInt::V4(_) if self.reader.metadata().ip_version == 6 && !self.has_ipv4_subtree => {
259                NetworkKind::V6
260            }
261            IpInt::V4(_) => NetworkKind::V4,
262            IpInt::V6(_)
263                if node.ip_int.is_ipv4_in_ipv6()
264                    && self.has_ipv4_subtree
265                    && node.prefix_len >= self.reader.ipv4_start_bit_depth =>
266            {
267                NetworkKind::V4InV6Subtree
268            }
269            IpInt::V6(_) => NetworkKind::V6,
270        }
271    }
272
273    fn push_child(
274        &mut self,
275        parent_node: usize,
276        direction: usize,
277        ip_int: IpInt,
278        prefix_len: usize,
279    ) {
280        let node = self.reader.read_node(parent_node, direction);
281        self.stack.push(WithinNode {
282            node,
283            ip_int,
284            prefix_len,
285        });
286    }
287
288    /// Check if the value at the given data offset is an empty map or array.
289    fn is_empty_value_at(&self, data_offset: usize) -> Result<bool, MaxMindDbError> {
290        let buf = &self.reader.buf.as_ref()[self.reader.pointer_base..];
291        let mut dec =
292            decoder::Decoder::new_with_limit(buf, data_offset, self.reader.data_section_len);
293        let (size, type_num) = dec
294            .peek_type()
295            .map_err(|error| error.with_invalid_database_offset_base(self.reader.pointer_base))?;
296        match type_num {
297            decoder::TYPE_MAP | decoder::TYPE_ARRAY => Ok(size == 0),
298            _ => Ok(false), // Non-container types are never "empty"
299        }
300    }
301}
302
303#[inline(always)]
304fn network_ip_addr(network_kind: NetworkKind, ip_int: IpInt) -> IpAddr {
305    let ip_addr = ip_int_to_addr(&ip_int);
306    match (network_kind, ip_int, ip_addr) {
307        // Low IPv6 tree keys are normally formatted as IPv4 addresses for IPv4
308        // subtree records. When the record is really IPv6, preserve the low
309        // IPv6 bits instead of collapsing the network to ::.
310        (NetworkKind::V6, IpInt::V6(ip), IpAddr::V4(_)) => IpAddr::V6(ip.into()),
311        // Defensive fallback for IPv4 CIDR iteration in IPv6 databases without
312        // an IPv4 subtree. Reader::within() should seed those as IpInt::V6(0).
313        (NetworkKind::V6, IpInt::V4(_), IpAddr::V4(_)) => IpAddr::V6(Ipv6Addr::UNSPECIFIED),
314        (_, _, ip_addr) => ip_addr,
315    }
316}
317
318/// Convert IpInt to IpAddr
319#[inline(always)]
320pub(crate) fn ip_int_to_addr(ip_int: &IpInt) -> IpAddr {
321    match ip_int {
322        IpInt::V4(ip) => IpAddr::V4((*ip).into()),
323        IpInt::V6(ip) => {
324            // Check if this is an IPv4-mapped IPv6 address.
325            if *ip <= 0xFFFFFFFF {
326                IpAddr::V4((*ip as u32).into())
327            } else {
328                IpAddr::V6((*ip).into())
329            }
330        }
331    }
332}
333
334#[cfg(test)]
335mod tests {
336    use std::net::{IpAddr, Ipv4Addr, Ipv6Addr};
337
338    use crate::result::NetworkKind;
339
340    use super::{network_ip_addr, IpInt};
341
342    #[test]
343    fn network_ip_addr_preserves_low_ipv6_bits() {
344        assert_eq!(
345            network_ip_addr(NetworkKind::V6, IpInt::V6(1)),
346            IpAddr::V6(Ipv6Addr::from(1_u128))
347        );
348    }
349
350    #[test]
351    fn network_ip_addr_formats_ipv4_subtree_records_as_ipv4() {
352        assert_eq!(
353            network_ip_addr(NetworkKind::V4InV6Subtree, IpInt::V6(1)),
354            IpAddr::V4(Ipv4Addr::from(1_u32))
355        );
356    }
357}
maxminddb/within.rs

maxminddb/
within.rs
