Skip to main content

wa_wire_codec/
node.rs

1//! Parsing a frame into a navigable node tree.
2//!
3//! A node is `[list tag][size][tag][attr pairs...][content?]`. The size counts
4//! every slot after the list header, so an even remainder means attributes
5//! only and an odd one means a trailing body.
6//!
7//! Nothing is copied and nothing is allocated. A [`NodeRef`] holds the slice
8//! starting at its own list tag and re-walks it on demand; the encoding is
9//! self-delimiting, so a node does not need to know where it ends. Parsing
10//! validates the whole tree up front, which is what makes every accessor
11//! afterwards infallible.
12
13use crate::error::ParseError;
14use crate::jid::{Jid, User};
15use crate::packed::{Alphabet, Packed};
16use crate::reader::Reader;
17use crate::token::{
18    self, BINARY_8, BINARY_20, BINARY_32, DICTIONARY_0, DICTIONARY_3, HEX_8, JID_FB, JID_INTEROP,
19    JID_PAIR, JID_USER, LIST_8, LIST_16, LIST_EMPTY, NIBBLE_8, TokenTable,
20};
21use crate::value::Value;
22
23/// How deep a frame may nest before the parser refuses it.
24///
25/// Real stanzas reach depth 9 at the extreme, so this is generous. It exists to
26/// bound recursion on a hostile frame, not to constrain real ones.
27pub const DEFAULT_MAX_DEPTH: usize = 64;
28
29/// What a node carries after its attributes.
30///
31/// Not `Copy`: the child variant holds an iterator, and a silently duplicated
32/// iterator is a bug waiting to happen.
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub enum Content<'a> {
35    /// No body at all.
36    None,
37    /// A scalar body.
38    Value(Value<'a>),
39    /// Child nodes.
40    Children(Children<'a>),
41}
42
43impl<'a> Content<'a> {
44    /// Whether the node has no body.
45    #[must_use]
46    pub const fn is_none(&self) -> bool {
47        matches!(self, Self::None)
48    }
49
50    /// The scalar body, if there is one.
51    #[must_use]
52    pub const fn as_value(&self) -> Option<Value<'a>> {
53        match self {
54            Self::Value(value) => Some(*value),
55            _ => None,
56        }
57    }
58
59    /// The body's bytes, when it is a raw payload — the `<enc>` case.
60    #[must_use]
61    pub const fn as_bytes(&self) -> Option<&'a [u8]> {
62        match self {
63            Self::Value(value) => value.as_bytes(),
64            _ => None,
65        }
66    }
67
68    /// The children, if the body is a list.
69    #[must_use]
70    pub fn as_children(self) -> Option<Children<'a>> {
71        match self {
72            Self::Children(children) => Some(children),
73            _ => None,
74        }
75    }
76}
77
78/// A node, borrowing from the frame it was parsed from.
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
80pub struct NodeRef<'a> {
81    table: TokenTable<'a>,
82    /// From this node's list tag to the end of the buffer. The encoding is
83    /// self-delimiting, so the tail beyond this node is harmless.
84    bytes: &'a [u8],
85    tag: Value<'a>,
86    attr_count: usize,
87    has_content: bool,
88    depth_budget: usize,
89}
90
91impl<'a> NodeRef<'a> {
92    /// The node's tag.
93    #[must_use]
94    pub const fn tag(&self) -> Value<'a> {
95        self.tag
96    }
97
98    /// How many attributes the node carries.
99    #[must_use]
100    pub const fn attr_count(&self) -> usize {
101        self.attr_count
102    }
103
104    /// Whether the node has a body.
105    #[must_use]
106    pub const fn has_content(&self) -> bool {
107        self.has_content
108    }
109
110    /// The attributes, in the order the frame carried them.
111    #[must_use]
112    pub fn attrs(&self) -> Attrs<'a> {
113        let mut reader = Reader::new(self.bytes);
114        // The tree was validated at parse time, so re-walking the header
115        // cannot fail. A zeroed count on the impossible branch yields an empty
116        // iterator rather than a panic.
117        let remaining = skip_header(&mut reader, self.table).map_or(0, |()| self.attr_count);
118        Attrs {
119            table: self.table,
120            reader,
121            remaining,
122        }
123    }
124
125    /// The first value for `key`.
126    ///
127    /// Attribute keys are tokens or short strings, so a linear scan over the
128    /// handful a stanza carries beats building an index.
129    #[must_use]
130    pub fn attr(&self, key: &str) -> Option<Value<'a>> {
131        self.attrs()
132            .find(|(name, _)| name.eq_str(key))
133            .map(|(_, value)| value)
134    }
135
136    /// Whether an attribute equals `expected` — the comparison L1 derivation
137    /// leans on, done without allocating.
138    #[must_use]
139    pub fn attr_eq(&self, key: &str, expected: &str) -> bool {
140        self.attr(key).is_some_and(|value| value.eq_str(expected))
141    }
142
143    /// The node's body.
144    #[must_use]
145    pub fn content(&self) -> Content<'a> {
146        self.content_inner().unwrap_or(Content::None)
147    }
148
149    fn content_inner(&self) -> Option<Content<'a>> {
150        if !self.has_content {
151            return Some(Content::None);
152        }
153        let mut reader = Reader::new(self.bytes);
154        skip_header(&mut reader, self.table).ok()?;
155        for _ in 0..self.attr_count {
156            skip_value(&mut reader, self.table).ok()?;
157            skip_value(&mut reader, self.table).ok()?;
158        }
159        parse_content(&mut reader, self.table, self.depth_budget).ok()
160    }
161
162    /// The child nodes, or an empty iterator when the body is not a list.
163    #[must_use]
164    pub fn children(&self) -> Children<'a> {
165        self.content().as_children().unwrap_or(Children::empty())
166    }
167
168    /// The child at `index`.
169    #[must_use]
170    pub fn child_at(&self, index: usize) -> Option<NodeRef<'a>> {
171        self.children().nth(index)
172    }
173
174    /// The first child whose tag is `tag`.
175    #[must_use]
176    pub fn child(&self, tag: &str) -> Option<NodeRef<'a>> {
177        self.children().find(|child| child.tag().eq_str(tag))
178    }
179
180    /// Follow a path of child indices from this node.
181    ///
182    /// This is how an envelope's plaintext entries find the node they belong
183    /// to: the path in a [`PlaintextEntry`] addresses exactly this walk.
184    ///
185    /// [`PlaintextEntry`]: https://docs.rs/wa-wire-contract
186    #[must_use]
187    pub fn at_path<I>(&self, path: I) -> Option<NodeRef<'a>>
188    where
189        I: IntoIterator<Item = u16>,
190    {
191        let mut node = *self;
192        for component in path {
193            node = node.child_at(usize::from(component))?;
194        }
195        Some(node)
196    }
197}
198
199/// Iterator over a node's attributes.
200#[derive(Debug, Clone, PartialEq, Eq)]
201pub struct Attrs<'a> {
202    table: TokenTable<'a>,
203    reader: Reader<'a>,
204    remaining: usize,
205}
206
207impl<'a> Iterator for Attrs<'a> {
208    type Item = (Value<'a>, Value<'a>);
209
210    fn next(&mut self) -> Option<Self::Item> {
211        self.remaining = self.remaining.checked_sub(1)?;
212        // Validated at parse time; the `ok()` arms are unreachable from a
213        // parsed tree and are exercised directly in this module's tests.
214        let key = parse_value_next(&mut self.reader, self.table).ok()?;
215        let value = parse_value_next(&mut self.reader, self.table).ok()?;
216        Some((key, value))
217    }
218
219    fn size_hint(&self) -> (usize, Option<usize>) {
220        (self.remaining, Some(self.remaining))
221    }
222}
223
224impl ExactSizeIterator for Attrs<'_> {}
225
226/// Iterator over a node's children.
227#[derive(Debug, Clone, PartialEq, Eq)]
228pub struct Children<'a> {
229    table: TokenTable<'a>,
230    reader: Reader<'a>,
231    remaining: usize,
232    depth_budget: usize,
233}
234
235impl Children<'_> {
236    const fn empty() -> Self {
237        Self {
238            table: TokenTable::empty(),
239            reader: Reader::new(&[]),
240            remaining: 0,
241            depth_budget: 0,
242        }
243    }
244
245    /// How many children are left.
246    #[must_use]
247    pub const fn len(&self) -> usize {
248        self.remaining
249    }
250
251    /// Whether there are no children left.
252    #[must_use]
253    pub const fn is_empty(&self) -> bool {
254        self.remaining == 0
255    }
256}
257
258impl<'a> Iterator for Children<'a> {
259    type Item = NodeRef<'a>;
260
261    fn next(&mut self) -> Option<Self::Item> {
262        self.remaining = self.remaining.checked_sub(1)?;
263        let node = parse_node(&mut self.reader, self.table, self.depth_budget).ok()?;
264        // Skipping past the child leaves the cursor on its sibling.
265        skip_node_body(&mut self.reader, self.table, &node).ok()?;
266        Some(node)
267    }
268
269    fn size_hint(&self) -> (usize, Option<usize>) {
270        (self.remaining, Some(self.remaining))
271    }
272}
273
274impl ExactSizeIterator for Children<'_> {}
275
276/// Parses frames into node trees.
277#[derive(Debug, Clone, Copy, PartialEq, Eq)]
278pub struct Parser<'a> {
279    table: TokenTable<'a>,
280    max_depth: usize,
281}
282
283impl<'a> Parser<'a> {
284    /// A parser over `table`, at the default depth limit.
285    #[must_use]
286    pub const fn new(table: TokenTable<'a>) -> Self {
287        Self {
288            table,
289            max_depth: DEFAULT_MAX_DEPTH,
290        }
291    }
292
293    /// Set how deep a frame may nest.
294    #[must_use]
295    pub const fn with_max_depth(mut self, max_depth: usize) -> Self {
296        self.max_depth = max_depth;
297        self
298    }
299
300    /// The token table in use.
301    #[must_use]
302    pub const fn table(&self) -> TokenTable<'a> {
303        self.table
304    }
305
306    /// The depth limit in use.
307    #[must_use]
308    pub const fn max_depth(&self) -> usize {
309        self.max_depth
310    }
311
312    /// Parse one node from `frame`, requiring it to consume the whole buffer.
313    ///
314    /// The whole tree is validated here, so every accessor on the result is
315    /// infallible.
316    pub fn parse(&self, frame: &'a [u8]) -> Result<NodeRef<'a>, ParseError> {
317        let mut reader = Reader::new(frame);
318        let node = parse_node(&mut reader, self.table, self.max_depth)?;
319        skip_node_body(&mut reader, self.table, &node)?;
320        if !reader.is_empty() {
321            return Err(ParseError::TrailingBytes(reader.remaining()));
322        }
323        Ok(node)
324    }
325
326    /// Parse the first node in `frame`, allowing bytes to follow.
327    ///
328    /// Useful when a caller frames several nodes back to back and wants to
329    /// handle the remainder itself.
330    pub fn parse_prefix(&self, frame: &'a [u8]) -> Result<(NodeRef<'a>, &'a [u8]), ParseError> {
331        let mut reader = Reader::new(frame);
332        let node = parse_node(&mut reader, self.table, self.max_depth)?;
333        skip_node_body(&mut reader, self.table, &node)?;
334        Ok((node, reader.tail()))
335    }
336}
337
338// ---------------------------------------------------------------------------
339// Parsing primitives
340// ---------------------------------------------------------------------------
341
342/// Read a node's list header and tag, leaving the cursor on its attributes.
343fn parse_node<'a>(
344    reader: &mut Reader<'a>,
345    table: TokenTable<'a>,
346    depth_budget: usize,
347) -> Result<NodeRef<'a>, ParseError> {
348    let depth_budget = depth_budget
349        .checked_sub(1)
350        .ok_or(ParseError::DepthLimitExceeded {
351            limit: DEFAULT_MAX_DEPTH,
352        })?;
353
354    let bytes = reader.tail();
355    let size = parse_list_size(reader)?;
356    let slots = size.checked_sub(1).ok_or(ParseError::EmptyNode)?;
357
358    let tag = parse_value_next(reader, table)?;
359    if !tag.is_textual() {
360        return Err(ParseError::NonStringTag);
361    }
362
363    let attr_count = slots / 2;
364    let has_content = slots % 2 == 1;
365
366    Ok(NodeRef {
367        table,
368        bytes,
369        tag,
370        attr_count,
371        has_content,
372        depth_budget,
373    })
374}
375
376/// Consume a node's attributes and body, leaving the cursor on its sibling.
377fn skip_node_body<'a>(
378    reader: &mut Reader<'a>,
379    table: TokenTable<'a>,
380    node: &NodeRef<'a>,
381) -> Result<(), ParseError> {
382    for _ in 0..node.attr_count {
383        let key = parse_value_next(reader, table)?;
384        let value = parse_value_next(reader, table)?;
385        if !key.is_textual() || !value.is_textual() {
386            return Err(ParseError::NonStringAttr);
387        }
388    }
389    if node.has_content {
390        match parse_content(reader, table, node.depth_budget)? {
391            Content::Children(children) => {
392                // Walked here rather than through `Children`'s iterator so a
393                // malformed child is reported instead of ending iteration.
394                let mut cursor = children.reader;
395                for _ in 0..children.remaining {
396                    let child = parse_node(&mut cursor, table, children.depth_budget)?;
397                    skip_node_body(&mut cursor, table, &child)?;
398                }
399                *reader = cursor;
400            }
401            Content::None | Content::Value(_) => {}
402        }
403    }
404    Ok(())
405}
406
407/// Re-read a node's list header and tag without producing them.
408fn skip_header<'a>(reader: &mut Reader<'a>, table: TokenTable<'a>) -> Result<(), ParseError> {
409    parse_list_size(reader)?;
410    parse_value_next(reader, table)?;
411    Ok(())
412}
413
414fn skip_value<'a>(reader: &mut Reader<'a>, table: TokenTable<'a>) -> Result<(), ParseError> {
415    parse_value_next(reader, table)?;
416    Ok(())
417}
418
419fn parse_list_size(reader: &mut Reader<'_>) -> Result<usize, ParseError> {
420    let tag = reader.u8()?;
421    match tag {
422        LIST_8 => Ok(usize::from(reader.u8()?)),
423        LIST_16 => Ok(usize::from(reader.u16()?)),
424        found => Err(ParseError::ExpectedList { found }),
425    }
426}
427
428fn parse_content<'a>(
429    reader: &mut Reader<'a>,
430    table: TokenTable<'a>,
431    depth_budget: usize,
432) -> Result<Content<'a>, ParseError> {
433    let tag = reader.u8()?;
434    match tag {
435        LIST_EMPTY => Ok(Content::None),
436        LIST_8 | LIST_16 => {
437            let count = if tag == LIST_8 {
438                usize::from(reader.u8()?)
439            } else {
440                usize::from(reader.u16()?)
441            };
442            Ok(Content::Children(Children {
443                table,
444                reader: *reader,
445                remaining: count,
446                depth_budget,
447            }))
448        }
449        other => Ok(Content::Value(parse_value(reader, table, other)?)),
450    }
451}
452
453fn parse_value_next<'a>(
454    reader: &mut Reader<'a>,
455    table: TokenTable<'a>,
456) -> Result<Value<'a>, ParseError> {
457    let tag = reader.u8()?;
458    parse_value(reader, table, tag)
459}
460
461fn parse_value<'a>(
462    reader: &mut Reader<'a>,
463    table: TokenTable<'a>,
464    tag: u8,
465) -> Result<Value<'a>, ParseError> {
466    match tag {
467        LIST_EMPTY => Ok(Value::Nil),
468        JID_PAIR => Ok(Value::Jid(parse_jid_pair(reader, table)?)),
469        JID_USER => Ok(Value::Jid(parse_jid_user(reader, table)?)),
470        JID_INTEROP => Ok(Value::Jid(parse_jid_interop(reader, table)?)),
471        JID_FB => Ok(Value::Jid(parse_jid_messenger(reader, table)?)),
472        BINARY_8 | BINARY_20 | BINARY_32 => Ok(Value::Bytes(parse_binary(reader, tag)?)),
473        NIBBLE_8 => Ok(Value::Packed(parse_packed(reader, Alphabet::Nibble)?)),
474        HEX_8 => Ok(Value::Packed(parse_packed(reader, Alphabet::Hex)?)),
475        _ => Ok(Value::Token(parse_token(reader, table, tag)?)),
476    }
477}
478
479fn parse_token<'a>(
480    reader: &mut Reader<'a>,
481    table: TokenTable<'a>,
482    tag: u8,
483) -> Result<&'a str, ParseError> {
484    if (DICTIONARY_0..=DICTIONARY_3).contains(&tag) {
485        let dictionary = tag.wrapping_sub(DICTIONARY_0);
486        let index = reader.u8()?;
487        return table
488            .dictionary(dictionary, index)
489            .ok_or(ParseError::UnknownToken {
490                dictionary: Some(dictionary),
491                index: u16::from(index),
492            });
493    }
494    table.single_byte(tag).ok_or(ParseError::UnknownToken {
495        dictionary: None,
496        index: u16::from(tag),
497    })
498}
499
500fn parse_binary<'a>(reader: &mut Reader<'a>, tag: u8) -> Result<&'a [u8], ParseError> {
501    let length = match tag {
502        BINARY_8 => u32::from(reader.u8()?),
503        BINARY_20 => reader.u20()?,
504        // `parse_value` only routes the three binary tags here.
505        _ => reader.u32()?,
506    };
507    reader.take(length as usize)
508}
509
510fn parse_packed<'a>(reader: &mut Reader<'a>, alphabet: Alphabet) -> Result<Packed<'a>, ParseError> {
511    let length_byte = reader.u8()?;
512    let (count, odd) = Packed::split_length_byte(length_byte)?;
513    let bytes = reader.take(count)?;
514    Ok(Packed::new(alphabet, bytes, odd))
515}
516
517/// A JID's user slot, which may be absent.
518fn parse_jid_user_part<'a>(
519    reader: &mut Reader<'a>,
520    table: TokenTable<'a>,
521) -> Result<User<'a>, ParseError> {
522    let tag = reader.u8()?;
523    match parse_value(reader, table, tag)? {
524        Value::Nil => Ok(User::None),
525        Value::Token(token) => Ok(User::Token(token)),
526        Value::Packed(packed) => Ok(User::Packed(packed)),
527        Value::Bytes(bytes) => Ok(User::Bytes(bytes)),
528        Value::Jid(_) => Err(ParseError::UnexpectedTag { tag }),
529    }
530}
531
532/// A JID's server, in any form the wire may carry it.
533///
534/// Not every server is in a dictionary. `newsletter`, `bot`, `interop` and
535/// `hosted.lid` are in none of the five, so each arrives spelled out — and a
536/// reader that only resolves tokens refuses a `@newsletter` JID, which is
537/// ordinary current traffic. The client reads this position with
538/// `decodeString` (`WA/Wap.js`, `ge()`), which takes a token or a string
539/// indifferently, and so does every other engine.
540fn parse_server<'a>(reader: &mut Reader<'a>, table: TokenTable<'a>) -> Result<&'a str, ParseError> {
541    let tag = reader.u8()?;
542    match parse_value(reader, table, tag)? {
543        Value::Token(token) => Ok(token),
544        Value::Bytes(bytes) => core::str::from_utf8(bytes).map_err(|_| ParseError::NonStringAttr),
545        // A server is neither digits nor hexadecimal, and a JID cannot be one.
546        Value::Packed(_) | Value::Jid(_) | Value::Nil => Err(ParseError::UnexpectedTag { tag }),
547    }
548}
549
550fn parse_jid_pair<'a>(
551    reader: &mut Reader<'a>,
552    table: TokenTable<'a>,
553) -> Result<Jid<'a>, ParseError> {
554    let user = parse_jid_user_part(reader, table)?;
555    let server = parse_server(reader, table)?;
556    Ok(Jid::pair(user, server))
557}
558
559fn parse_jid_user<'a>(
560    reader: &mut Reader<'a>,
561    table: TokenTable<'a>,
562) -> Result<Jid<'a>, ParseError> {
563    let domain_type = reader.u8()?;
564    let device = u16::from(reader.u8()?);
565    let user = parse_jid_user_part(reader, table)?;
566    Ok(Jid::with_device(user, server_for(domain_type), device))
567}
568
569const fn server_for(domain_type: u8) -> &'static str {
570    if domain_type == token::DOMAIN_TYPE_LID {
571        token::SERVER_LID
572    } else if domain_type == token::DOMAIN_TYPE_HOSTED_LID {
573        token::SERVER_HOSTED_LID
574    } else if domain_type & token::DOMAIN_TYPE_HOSTED_MASK != 0
575        && domain_type & token::DOMAIN_TYPE_LID_MASK == 0
576    {
577        token::SERVER_HOSTED
578    } else {
579        token::SERVER_PN
580    }
581}
582
583fn parse_jid_interop<'a>(
584    reader: &mut Reader<'a>,
585    table: TokenTable<'a>,
586) -> Result<Jid<'a>, ParseError> {
587    let user = parse_jid_user_part(reader, table)?;
588    let device = reader.u16()?;
589    let integrator = reader.u16()?;
590    // The trailing server token is on the wire *inbound* and must be consumed.
591    //
592    // The two directions of this JID genuinely differ, which is easy to get
593    // backwards. The client's reader takes user, device, integrator and then a
594    // string it discards (`WA/Wap.js`, `be()`); its writer emits user, device,
595    // integrator and stops (`ne()`, the `JID_INTEROP` arm). Reading the writer
596    // and concluding the token does not exist breaks every inbound interop JID
597    // by one attribute. `whatsapp-rust`, `whatsmeow`, `zapo` and Baileys all
598    // read it, and `whatsapp-rust`'s own marshal tests say why they must.
599    parse_server(reader, table)?;
600    Ok(Jid::interop(user, device, integrator))
601}
602
603fn parse_jid_messenger<'a>(
604    reader: &mut Reader<'a>,
605    table: TokenTable<'a>,
606) -> Result<Jid<'a>, ParseError> {
607    let user = parse_jid_user_part(reader, table)?;
608    let device = reader.u16()?;
609    parse_server(reader, table)?;
610    Ok(Jid::messenger(user, device))
611}
612
613#[cfg(test)]
614#[path = "node_tests.rs"]
615mod tests;