asc_engine/
compact.rs

1//! Text-only `find_refs` rows ([`Engine::find_refs_text`]): each DEX's rows
2//! rendered straight into one block, for the CLI's default output. A broad
3//! query (`string a`) has hundreds of thousands of rows; building a
4//! [`RefResult`](crate::RefResult) for each only to print it dominates such a search.
5//!
6//! [`Engine::find_refs_text`]: crate::Engine::find_refs_text
7
8use crate::{FindOptions, Result, matched_name, results_from_hits, rows_compiled};
9use asc_dex::Dex;
10use asc_findrefs::{CompiledQuery, FieldAccess, FindRefs, Hit, RefKind};
11use std::collections::hash_map::Entry;
12use std::collections::{HashMap, HashSet};
13use std::ops::Range;
14use std::sync::Arc;
15
16/// Rows of one DEX entry as text, one per line, each ending in `\n`: what
17/// [`RefResult::line`](crate::RefResult::line) would print for them, in the same order.
18#[derive(Clone, Default)]
19pub struct TextRows {
20    text: Text,
21    /// The offset of each row's `\n`: a row may itself hold one (a DEX entry
22    /// name with a newline), so the rows are not told apart by splitting.
23    ends: Vec<usize>,
24}
25
26/// The bytes behind [`TextRows`]: built in memory, or a validated range of
27/// an L3 file replayed without a copy.
28#[derive(Clone)]
29enum Text {
30    Owned(String),
31    Shared { bytes: Arc<dyn AsRef<[u8]> + Send + Sync>, range: Range<usize> },
32}
33
34impl Default for Text {
35    fn default() -> Self {
36        Text::Owned(String::new())
37    }
38}
39
40impl TextRows {
41    /// Every row, each followed by `\n`.
42    ///
43    /// # Panics
44    ///
45    /// Never: shared bytes are checked to be UTF-8 when the rows are built.
46    pub fn as_str(&self) -> &str {
47        match &self.text {
48            Text::Owned(s) => s,
49            // `shared` checked the range is UTF-8.
50            Text::Shared { bytes, range } => std::str::from_utf8(&(**bytes).as_ref()[range.clone()]).expect("validated UTF-8"),
51        }
52    }
53
54    /// The number of rows.
55    pub fn len(&self) -> usize {
56        self.ends.len()
57    }
58
59    /// Whether there are no rows.
60    pub fn is_empty(&self) -> bool {
61        self.ends.is_empty()
62    }
63
64    /// The rows, without their `\n`.
65    pub fn lines(&self) -> impl Iterator<Item = &str> {
66        let text = self.as_str();
67        let starts = std::iter::once(0).chain(self.ends.iter().map(|&e| e + 1));
68        starts.zip(&self.ends).map(move |(start, &end)| &text[start..end])
69    }
70
71    pub(crate) fn ends(&self) -> &[usize] {
72        &self.ends
73    }
74
75    /// Rows viewed in `bytes[range]`; `None` unless the range is UTF-8 and
76    /// `ends` are increasing `\n` offsets, the last one ending the range.
77    pub(crate) fn shared(bytes: Arc<dyn AsRef<[u8]> + Send + Sync>, range: Range<usize>, ends: Vec<usize>) -> Option<TextRows> {
78        let text = std::str::from_utf8((*bytes).as_ref().get(range.clone())?).ok()?;
79        let valid = ends.windows(2).all(|w| w[0] < w[1])
80            && ends.iter().all(|&e| text.as_bytes().get(e) == Some(&b'\n'))
81            && ends.last().map_or(text.is_empty(), |&e| e + 1 == text.len());
82        valid.then_some(TextRows { text: Text::Shared { bytes, range }, ends })
83    }
84
85    /// The text to append rows to (a shared block is copied first).
86    fn owned(&mut self) -> &mut String {
87        if let Text::Shared { .. } = self.text {
88            self.text = Text::Owned(self.as_str().to_string());
89        }
90        match &mut self.text {
91            Text::Owned(s) => s,
92            Text::Shared { .. } => unreachable!("converted above"),
93        }
94    }
95
96    /// End the row written since the last one.
97    fn end_row(&mut self) {
98        let text = self.owned();
99        let end = text.len();
100        text.push('\n');
101        self.ends.push(end);
102    }
103
104    /// Append the rows of `other`.
105    pub(crate) fn append(&mut self, other: &TextRows) {
106        let base = self.owned().len();
107        self.owned().push_str(other.as_str());
108        self.ends.extend(other.ends.iter().map(|&e| base + e));
109    }
110}
111
112impl std::fmt::Debug for TextRows {
113    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
114        f.debug_struct("TextRows").field("rows", &self.len()).field("bytes", &self.as_str().len()).finish()
115    }
116}
117
118impl PartialEq for TextRows {
119    fn eq(&self, other: &Self) -> bool {
120        self.ends == other.ends && self.as_str() == other.as_str()
121    }
122}
123
124impl Eq for TextRows {}
125
126/// The text rows of `query` over the DEX `fr` searches, aggregated per
127/// method with no context. Plain code queries are rendered straight from
128/// their hits; anything else (class relations, compounds, definition
129/// predicates, call-site notes) as the lines of its [`RefResult`](crate::RefResult)s.
130pub(crate) fn text_rows(fr: &FindRefs<'_, '_, '_>, query: &CompiledQuery) -> Result<TextRows> {
131    let plain = query.relation().is_none() && query.compound().is_none() && query.defined().is_none();
132    let rows = if plain {
133        let hits = fr.find_ref_compiled(query)?;
134        if hits.iter().all(|h| h.note.is_none()) {
135            return rows_from_hits(fr.dex(), query.kind(), &hits);
136        }
137        results_from_hits(fr.dex(), query.kind(), &hits, true)?
138    } else {
139        rows_compiled(fr, query, FindOptions::default())?
140    };
141    let mut out = TextRows::default();
142    for r in &rows {
143        out.owned().push_str(&r.line());
144        out.end_row();
145    }
146    Ok(out)
147}
148
149/// [`results_from_hits`] (aggregated, without notes) rendered as text: one
150/// row per method in method order, its distinct constants in index order.
151fn rows_from_hits(dex: &Dex<'_>, kind: RefKind, hits: &[Hit]) -> Result<TextRows> {
152    // Method ids index a dense table: a broad search touches most methods,
153    // and this needs neither a map entry per method nor a final sort.
154    let mut grouped = vec![SmallIdxSet::default(); dex.method_count() as usize];
155    for hit in hits {
156        for &m in hit.methods.iter().flat_map(|ms| ms.ids()) {
157            if let Some(idxs) = grouped.get_mut(m as usize) {
158                idxs.insert(hit_key(hit));
159            }
160        }
161    }
162    let mut out = TextRows::default();
163    // One constant is often matched in many methods: render it once.
164    let mut matched: HashMap<u32, String> = HashMap::new();
165    for (m, idxs) in grouped.into_iter().enumerate() {
166        if let SmallIdxSet::Empty = idxs {
167            continue;
168        }
169        let m = u32::try_from(m).expect("method ids are u32");
170        let text = out.owned();
171        text.push_str(dex.name());
172        text.push_str(" | ");
173        text.push_str(&asc_smali::method_signature(dex, m)?);
174        text.push_str(" | ");
175        for (i, key) in idxs.into_sorted().into_iter().enumerate() {
176            if i != 0 {
177                text.push_str(", ");
178            }
179            let value = match matched.entry(key) {
180                Entry::Occupied(e) => e.into_mut(),
181                Entry::Vacant(e) => {
182                    let (idx, access) = split_hit_key(key);
183                    let mut value = matched_name(dex, kind, idx)?.to_string();
184                    if let Some(access) = access {
185                        value.push_str(&format!(" [{}]", access.as_str()));
186                    }
187                    e.insert(value)
188                }
189            };
190            text.push_str(value);
191        }
192        out.end_row();
193    }
194    Ok(out)
195}
196
197fn hit_key(hit: &Hit) -> u32 {
198    // FindRefs bounds matched indexes below DEX bytes / 4, so the shift
199    // cannot discard bits even for jumbo string indexes.
200    (hit.matched_idx << 2)
201        | match hit.field_access {
202            None => 0,
203            Some(FieldAccess::Read) => 1,
204            Some(FieldAccess::Write) => 2,
205        }
206}
207
208fn split_hit_key(key: u32) -> (u32, Option<FieldAccess>) {
209    let access = match key & 3 {
210        1 => Some(FieldAccess::Read),
211        2 => Some(FieldAccess::Write),
212        _ => None,
213    };
214    (key >> 2, access)
215}
216
217/// A method's distinct matched indexes. Most methods match one or two
218/// constants: those stay inline, a set is allocated only for a third.
219#[derive(Clone, Default)]
220enum SmallIdxSet {
221    #[default]
222    Empty,
223    One(u32),
224    Two(u32, u32),
225    // Boxed so the table of one slot per method stays three words a slot.
226    #[allow(clippy::box_collection)]
227    Many(Box<HashSet<u32>>),
228}
229
230impl SmallIdxSet {
231    fn insert(&mut self, idx: u32) {
232        match self {
233            SmallIdxSet::Empty => *self = SmallIdxSet::One(idx),
234            SmallIdxSet::One(a) if *a == idx => {}
235            SmallIdxSet::One(a) => *self = SmallIdxSet::Two(*a, idx),
236            SmallIdxSet::Two(a, b) if *a == idx || *b == idx => {}
237            SmallIdxSet::Two(a, b) => *self = SmallIdxSet::Many(Box::new(HashSet::from([*a, *b, idx]))),
238            SmallIdxSet::Many(set) => {
239                set.insert(idx);
240            }
241        }
242    }
243
244    fn into_sorted(self) -> Vec<u32> {
245        let mut out = match self {
246            SmallIdxSet::Empty => Vec::new(),
247            SmallIdxSet::One(a) => vec![a],
248            SmallIdxSet::Two(a, b) => vec![a, b],
249            SmallIdxSet::Many(set) => set.into_iter().collect(),
250        };
251        out.sort_unstable();
252        out
253    }
254}
255
256#[cfg(test)]
257mod tests {
258    use super::*;
259
260    fn rows(lines: &[&str]) -> TextRows {
261        let mut out = TextRows::default();
262        for l in lines {
263            out.owned().push_str(l);
264            out.end_row();
265        }
266        out
267    }
268
269    #[test]
270    fn rows_keep_their_boundaries_through_append_and_sharing() {
271        let mut a = rows(&["x | a", "y\nz | b"]);
272        a.append(&rows(&["w | c"]));
273        assert_eq!(a.lines().collect::<Vec<_>>(), ["x | a", "y\nz | b", "w | c"]);
274        assert_eq!((a.len(), a.as_str()), (3, "x | a\ny\nz | b\nw | c\n"));
275
276        let bytes: Arc<dyn AsRef<[u8]> + Send + Sync> = Arc::new(format!("##{}##", a.as_str()).into_bytes());
277        let range = 2..2 + a.as_str().len();
278        let shared = TextRows::shared(bytes.clone(), range.clone(), a.ends().to_vec()).unwrap();
279        assert_eq!(shared, a);
280        // Ends that miss a newline, run past the range or leave text after
281        // the last row are refused.
282        for ends in [vec![0, 9, 15], vec![5, 11, 99], vec![5, 11]] {
283            assert!(TextRows::shared(bytes.clone(), range.clone(), ends).is_none());
284        }
285        assert!(TextRows::shared(bytes, 0..0, Vec::new()).unwrap().is_empty());
286    }
287
288    #[test]
289    fn small_sets_sort_and_dedup() {
290        let mut s = SmallIdxSet::default();
291        for i in [5, 3, 5, 9, 3, 1] {
292            s.insert(i);
293        }
294        assert_eq!(s.into_sorted(), [1, 3, 5, 9]);
295        let mut s = SmallIdxSet::default();
296        s.insert(2);
297        s.insert(2);
298        assert_eq!(s.into_sorted(), [2]);
299    }
300}
asc_engine/compact.rs

asc_engine/
compact.rs
