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

asc_engine/
compact.rs
