everscale_types/dict/ops/
get.rs

1use crate::cell::*;
2use crate::dict::{make_leaf, read_label, split_edge, Branch};
3use crate::error::Error;
4
5/// Returns a `CellSlice` of the value corresponding to the key.
6pub fn dict_get<'a: 'b, 'b>(
7    dict: Option<&'a Cell>,
8    key_bit_len: u16,
9    mut key: CellSlice<'b>,
10    context: &mut dyn CellContext,
11) -> Result<Option<CellSlice<'a>>, Error> {
12    if key.size_bits() != key_bit_len {
13        return Err(Error::CellUnderflow);
14    }
15
16    let mut data = match dict {
17        Some(data) => ok!(context
18            .load_dyn_cell(data.as_ref(), LoadMode::Full)
19            .and_then(CellSlice::new)),
20        None => return Ok(None),
21    };
22
23    // Try to find the required leaf
24    let is_key_empty = loop {
25        // Read the key part written in the current edge
26        let prefix = ok!(read_label(&mut data, key.size_bits()));
27
28        // Remove this prefix from the key
29        match key.strip_data_prefix(&prefix) {
30            Some(stripped_key) => {
31                if stripped_key.is_data_empty() {
32                    // All key parts were collected <=> value found
33                    break true;
34                } else if data.size_refs() < 2 {
35                    // Reached leaf while key was not fully constructed
36                    return Ok(None);
37                } else {
38                    key = stripped_key;
39                }
40            }
41            None => break key.is_data_empty(),
42        }
43
44        // Load next child based on the next bit
45        let child_index = ok!(key.load_bit()) as u8;
46        data = match data.cell().reference(child_index) {
47            Some(cell) => ok!(context
48                .load_dyn_cell(cell, LoadMode::Full)
49                .and_then(CellSlice::new)),
50            None => return Err(Error::CellUnderflow),
51        };
52    };
53
54    // Return the last slice as data
55    Ok(if is_key_empty { Some(data) } else { None })
56}
57
58/// Returns cell slice parts of the value corresponding to the key.
59pub fn dict_get_owned(
60    dict: Option<&Cell>,
61    key_bit_len: u16,
62    mut key: CellSlice<'_>,
63    context: &mut dyn CellContext,
64) -> Result<Option<CellSliceParts>, Error> {
65    if key.size_bits() != key_bit_len {
66        return Err(Error::CellUnderflow);
67    }
68
69    let root = match dict {
70        Some(cell) => ok!(context.load_cell(cell.clone(), LoadMode::Full)),
71        None => return Ok(None),
72    };
73    let mut data = ok!(root.as_slice());
74    let mut prev = None;
75
76    // Try to find the required leaf
77    let is_key_empty = loop {
78        // Read the key part written in the current edge
79        let prefix = ok!(read_label(&mut data, key.size_bits()));
80
81        // Remove this prefix from the key
82        match key.strip_data_prefix(&prefix) {
83            Some(stripped_key) => {
84                if stripped_key.is_data_empty() {
85                    // All key parts were collected <=> value found
86                    break true;
87                } else if data.size_refs() < 2 {
88                    // Reached leaf while key was not fully constructed
89                    return Ok(None);
90                } else {
91                    key = stripped_key;
92                }
93            }
94            None => break key.is_data_empty(),
95        }
96
97        // Load next child based on the next bit
98        let child_index = ok!(key.load_bit()) as u8;
99        prev = Some((data.cell(), child_index));
100        data = match data.cell().reference(child_index) {
101            Some(cell) => ok!(context
102                .load_dyn_cell(cell, LoadMode::Full)
103                .and_then(CellSlice::new)),
104            None => return Err(Error::CellUnderflow),
105        };
106    };
107
108    // Return the last slice as data
109    Ok(if is_key_empty {
110        Some(match prev {
111            Some((prev, child_index)) => {
112                let cell = match prev.reference_cloned(child_index) {
113                    Some(cell) => ok!(context.load_cell(cell, LoadMode::Resolve)),
114                    None => return Err(Error::CellUnderflow),
115                };
116                (cell, data.range())
117            }
118            None => {
119                let range = data.range();
120                (root, range)
121            }
122        })
123    } else {
124        None
125    })
126}
127
128/// Gets subdictionary by specified prefiex
129/// Returns optional dictionary as Cell representation if specified prefix is present in dictionary
130pub fn dict_get_subdict<'a: 'b, 'b>(
131    dict: Option<&'a Cell>,
132    key_bit_len: u16,
133    prefix: &mut CellSlice<'b>,
134    context: &mut dyn CellContext,
135) -> Result<Option<Cell>, Error> {
136    match dict {
137        None => Ok(None),
138        Some(cell) => {
139            let prefix_len = prefix.size_bits();
140            if prefix_len == 0 || key_bit_len < prefix_len {
141                return Ok(Some(cell.clone()));
142            }
143
144            let mut data = match dict {
145                Some(data) => ok!(context
146                    .load_dyn_cell(data.as_ref(), LoadMode::Full)
147                    .and_then(CellSlice::new)),
148                None => return Ok(None),
149            };
150
151            // Try to find the required root
152            let subtree = loop {
153                // Read the key part written in the current edge
154                let label = &mut ok!(read_label(&mut data, prefix.size_bits()));
155                let lcp = prefix.longest_common_data_prefix(label);
156                match lcp.size_bits().cmp(&prefix.size_bits()) {
157                    std::cmp::Ordering::Equal => {
158                        // Found exact key
159                        let new_leaf = ok!(make_leaf(label, lcp.size_bits(), &data, context));
160                        break new_leaf;
161                    }
162                    std::cmp::Ordering::Less if lcp.size_bits() < label.size_bits() => {
163                        // Have to split edge
164                        let value = ok!(CellBuilder::new().build_ext(context));
165                        let split_edge =
166                            ok!(split_edge(&data, label, &lcp, prefix, &value, context));
167                        break split_edge;
168                    }
169                    std::cmp::Ordering::Less => {
170                        if data.cell().reference_count() != 2 {
171                            return Err(Error::CellUnderflow);
172                        }
173                        prefix.skip_first(lcp.size_bits(), 0).ok();
174                        let next_branch = match prefix.load_bit() {
175                            Ok(bit) => Branch::from(bit),
176                            Err(e) => return Err(e),
177                        };
178
179                        let child = match data.cell().reference(next_branch as u8) {
180                            // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok
181                            Some(cell) => ok!(context
182                                .load_dyn_cell(cell, LoadMode::Full)
183                                .and_then(CellSlice::new)),
184                            None => return Err(Error::CellUnderflow),
185                        };
186                        data = child;
187                    }
188                    std::cmp::Ordering::Greater => {
189                        debug_assert!(false, "LCP of prefix and key can't be greater than key");
190                        unsafe { std::hint::unreachable_unchecked() };
191                    }
192                }
193            };
194
195            Ok(Some(subtree))
196        }
197    }
198}
everscale_types/dict/ops/get.rs

everscale_types/dict/ops/
get.rs
