link_cli/protocol/
mapping.rs

1//! Lossless mapping between LiNo documents and [`LinksPacket`]s.
2//!
3//! The mapping only uses links, the way linksplatform represents data:
4//!
5//! - `()` is the null link `0`.
6//! - A numeric reference `n` is `(Number unary(n))`, where `unary(0)` is null,
7//!   `2^0` is the marker `One`, `2^k` is `(2^(k-1) 2^(k-1))` and other numbers
8//!   are right-nested sums of powers of two from the highest bit down. With
9//!   external references enabled, `n` is sent as an external reference instead.
10//! - Any other reference is `(String code points…)`; every code point is a
11//!   unary number, or an external reference when those are enabled.
12//! - A link without an id and with exactly two values is a plain doublet.
13//! - A link without an id and any other number of values is a list.
14//! - A link with an id is `(Identified id values…)`.
15//! - The document is a list of its top-level links, stored last (the root).
16//!
17//! A link with two values is always a doublet. A list or typed value with
18//! any other number of values is a single link of that many references when
19//! [`BinaryLinoOptions::arity`] allows it (`[marker, elements…]` for typed
20//! values, the bare elements for lists), and otherwise the doublet
21//! `(marker chain)`, where `chain` is the nil-terminated cons list
22//! `(e1 (e2 (… (en 0))))`. Identical sub-links are emitted once and shared,
23//! because links are content-addressed.
24//!
25//! Links are numbered so that every link only refers to earlier ones:
26//! doublets of plain doublets first, then the rest in creation order.
27
28use super::error::{ProtocolError, ProtocolResult};
29use super::packet::{
30    external_capacity, ArityRange, DecodeLimits, LinksPacket, Reference, FIRST_LINK_ADDRESS,
31    IDENTIFIED, LIST, NULL, NUMBER, ONE, STRING,
32};
33use links_notation::LiNo;
34use std::collections::HashMap;
35
36/// A LiNo document: the list of top-level links of a message.
37pub type LinoDocument = Vec<LiNo<String>>;
38
39/// Optional features of the binary LiNo protocol.
40///
41/// Every feature is off by default; each one can be switched on
42/// independently, like stacking a decorator.
43#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
44pub struct BinaryLinoOptions {
45    /// Send numbers and code points as Hybrid external references instead of
46    /// in-band unary links. Halves the internal address range of each width.
47    pub external_references: bool,
48    /// The link lengths the encoder may use. The default, exactly 2, sends
49    /// only doublets; `2..3` adds triplets and `1..` any length. The range
50    /// must include 2.
51    pub arity: ArityRange,
52    /// Give every section of the packet the narrowest width its links need
53    /// instead of one width for the whole packet.
54    pub packed_widths: bool,
55}
56
57impl BinaryLinoOptions {
58    /// Enables or disables external references.
59    pub fn with_external_references(mut self, enabled: bool) -> Self {
60        self.external_references = enabled;
61        self
62    }
63
64    /// Sets the link lengths the encoder may use.
65    pub fn with_arity(mut self, arity: ArityRange) -> Self {
66        self.arity = arity;
67        self
68    }
69
70    /// Enables or disables packed widths.
71    pub fn with_packed_widths(mut self, enabled: bool) -> Self {
72        self.packed_widths = enabled;
73        self
74    }
75
76    /// The options a peer most likely used to write `packet`, so a reply can
77    /// be written in the same style.
78    pub fn of_packet(packet: &LinksPacket) -> Self {
79        let (shortest, longest) = packet
80            .links()
81            .map(|(_, link)| link.len() as u64)
82            .fold((2, 2), |(shortest, longest), length| {
83                (shortest.min(length), longest.max(length))
84            });
85        let mut widths = packet.sections.iter().map(|section| section.width);
86        let first_width = widths.next();
87        Self {
88            external_references: packet.external_references,
89            arity: ArityRange::between(shortest, longest),
90            packed_widths: widths.any(|width| Some(width) != first_width),
91        }
92    }
93}
94
95/// Converts a document into a packet.
96pub fn encode_document(
97    document: &[LiNo<String>],
98    options: BinaryLinoOptions,
99) -> ProtocolResult<LinksPacket> {
100    if !options.arity.contains(2) {
101        return Err(ProtocolError::Unencodable(format!(
102            "arity {} does not include doublets (2)",
103            options.arity
104        )));
105    }
106    let mut encoder = Encoder::new(options);
107    if !document.is_empty() {
108        let items = document
109            .iter()
110            .map(|link| encoder.encode(link))
111            .collect::<Vec<_>>();
112        encoder.list(items);
113    }
114    encoder.finish()
115}
116
117/// Converts a packet back into a document.
118pub fn decode_document(
119    packet: &LinksPacket,
120    limits: &DecodeLimits,
121) -> ProtocolResult<LinoDocument> {
122    let decoder = Decoder::new(packet, limits)?;
123    let Some(root) = decoder.links.len().checked_sub(1) else {
124        return Ok(Vec::new());
125    };
126    let root = Reference::Internal(FIRST_LINK_ADDRESS + root as u64);
127    let items = match decoder.view(root) {
128        View::Link(&[Reference::Internal(LIST), chain]) => decoder.chain(chain)?,
129        View::Link(items) if !starts_with_marker(items) => items.to_vec(),
130        _ => return Err(ProtocolError::malformed("the root link is not a list")),
131    };
132    let mut budget = limits.max_nodes;
133    items
134        .into_iter()
135        .map(|item| decoder.decode(item, 0, &mut budget))
136        .collect()
137}
138
139/// Parses a canonical unsigned decimal number (no sign, no leading zeros).
140pub(crate) fn canonical_number(text: &str) -> Option<u64> {
141    let canonical = !text.is_empty()
142        && text.bytes().all(|byte| byte.is_ascii_digit())
143        && (text == "0" || !text.starts_with('0'));
144    canonical.then(|| text.parse().ok()).flatten()
145}
146
147#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
148enum Node {
149    Internal(u64),
150    External(u64),
151    /// A doublet of plain doublets, markers and externals.
152    Doublet(usize),
153    /// Any other link; numbered after every [`Node::Doublet`].
154    Tuple(usize),
155}
156
157struct Encoder {
158    options: BinaryLinoOptions,
159    doublets: Vec<Vec<Node>>,
160    tuples: Vec<Vec<Node>>,
161    created: HashMap<Vec<Node>, Node>,
162    powers: Vec<Node>,
163}
164
165impl Encoder {
166    fn new(options: BinaryLinoOptions) -> Self {
167        Self {
168            options,
169            doublets: Vec::new(),
170            tuples: Vec::new(),
171            created: HashMap::new(),
172            powers: vec![Node::Internal(ONE)],
173        }
174    }
175
176    fn link(&mut self, items: Vec<Node>) -> Node {
177        if let Some(&node) = self.created.get(&items) {
178            return node;
179        }
180        let refers_to_tuple = items.iter().any(|item| matches!(item, Node::Tuple(_)));
181        let node = if items.len() == 2 && !refers_to_tuple {
182            self.doublets.push(items.clone());
183            Node::Doublet(self.doublets.len() - 1)
184        } else {
185            self.tuples.push(items.clone());
186            Node::Tuple(self.tuples.len() - 1)
187        };
188        self.created.insert(items, node);
189        node
190    }
191
192    fn pair(&mut self, first: Node, second: Node) -> Node {
193        self.link(vec![first, second])
194    }
195
196    fn chain(&mut self, items: &[Node]) -> Node {
197        items
198            .iter()
199            .rev()
200            .fold(Node::Internal(NULL), |tail, &head| self.pair(head, tail))
201    }
202
203    /// One link of `items` when the arity allows it, except that two items
204    /// are always a doublet.
205    fn fits_one_link(&self, items: usize) -> bool {
206        items != 2 && self.options.arity.contains(items as u64)
207    }
208
209    fn typed(&mut self, marker: u64, elements: Vec<Node>) -> Node {
210        if self.fits_one_link(elements.len() + 1) {
211            let mut items = Vec::with_capacity(elements.len() + 1);
212            items.push(Node::Internal(marker));
213            items.extend(elements);
214            self.link(items)
215        } else {
216            let chain = self.chain(&elements);
217            self.pair(Node::Internal(marker), chain)
218        }
219    }
220
221    fn list(&mut self, elements: Vec<Node>) -> Node {
222        match elements.as_slice() {
223            [] => Node::Internal(NULL),
224            &[first, second] => self.pair(first, second),
225            _ if self.fits_one_link(elements.len()) => self.link(elements),
226            _ => self.typed(LIST, elements),
227        }
228    }
229
230    fn power(&mut self, exponent: usize) -> Node {
231        while self.powers.len() <= exponent {
232            let previous = *self.powers.last().expect("powers start with One");
233            let next = self.pair(previous, previous);
234            self.powers.push(next);
235        }
236        self.powers[exponent]
237    }
238
239    fn unary(&mut self, value: u64) -> Node {
240        let bits = (0..64).rev().filter(|bit| value & (1u64 << bit) != 0);
241        let powers = bits.map(|bit| self.power(bit)).collect::<Vec<_>>();
242        let Some((&last, rest)) = powers.split_last() else {
243            return Node::Internal(NULL);
244        };
245        rest.iter()
246            .rev()
247            .fold(last, |sum, &power| self.pair(power, sum))
248    }
249
250    fn scalar(&mut self, value: u64) -> Node {
251        if self.options.external_references && value <= external_capacity(8) {
252            Node::External(value)
253        } else {
254            self.unary(value)
255        }
256    }
257
258    fn reference(&mut self, text: &str) -> Node {
259        if let Some(value) = canonical_number(text) {
260            if self.options.external_references && value <= external_capacity(8) {
261                return Node::External(value);
262            }
263            let unary = self.unary(value);
264            return self.pair(Node::Internal(NUMBER), unary);
265        }
266        let code_points = text
267            .chars()
268            .map(|character| self.scalar(u64::from(u32::from(character))))
269            .collect();
270        self.typed(STRING, code_points)
271    }
272
273    fn encode(&mut self, link: &LiNo<String>) -> Node {
274        match link {
275            LiNo::Ref(text) => self.reference(text),
276            LiNo::Link { id: None, values } => {
277                let elements = values.iter().map(|value| self.encode(value)).collect();
278                self.list(elements)
279            }
280            LiNo::Link {
281                id: Some(id),
282                values,
283            } => {
284                let mut elements = Vec::with_capacity(values.len() + 1);
285                elements.push(self.reference(id));
286                elements.extend(values.iter().map(|value| self.encode(value)));
287                self.typed(IDENTIFIED, elements)
288            }
289        }
290    }
291
292    fn finish(self) -> ProtocolResult<LinksPacket> {
293        let doublet_count = self.doublets.len() as u64;
294        let resolve = |node: &Node| match *node {
295            Node::Internal(address) => Reference::Internal(address),
296            Node::External(value) => Reference::External(value),
297            Node::Doublet(index) => Reference::Internal(FIRST_LINK_ADDRESS + index as u64),
298            Node::Tuple(index) => {
299                Reference::Internal(FIRST_LINK_ADDRESS + doublet_count + index as u64)
300            }
301        };
302        let links: Vec<(u64, Vec<Reference>)> = self
303            .doublets
304            .iter()
305            .chain(&self.tuples)
306            .enumerate()
307            .map(|(index, items)| {
308                (
309                    FIRST_LINK_ADDRESS + index as u64,
310                    items.iter().map(resolve).collect(),
311                )
312            })
313            .collect();
314        LinksPacket::pack(
315            self.options.external_references,
316            &links,
317            self.options.packed_widths,
318        )
319    }
320}
321
322enum View<'a> {
323    Null,
324    Marker(u64),
325    External(u64),
326    Link(&'a [Reference]),
327}
328
329fn is_marker(reference: Reference) -> bool {
330    matches!(reference, Reference::Internal(address) if (ONE..FIRST_LINK_ADDRESS).contains(&address))
331}
332
333fn starts_with_marker(items: &[Reference]) -> bool {
334    items.first().copied().is_some_and(is_marker)
335}
336
337struct Decoder<'a> {
338    limits: &'a DecodeLimits,
339    /// `links[i]` is the link at address `FIRST_LINK_ADDRESS + i`.
340    links: Vec<&'a [Reference]>,
341    /// `unary[i]` is the number link `i` denotes, if it is a unary number.
342    unary: Vec<Option<u64>>,
343}
344
345impl<'a> Decoder<'a> {
346    fn new(packet: &'a LinksPacket, limits: &'a DecodeLimits) -> ProtocolResult<Self> {
347        let mut links: Vec<&'a [Reference]> = Vec::new();
348        let mut unary: Vec<Option<u64>> = Vec::new();
349        for (address, link) in packet.links() {
350            let expected = FIRST_LINK_ADDRESS + links.len() as u64;
351            if address != expected {
352                return Err(ProtocolError::malformed(format!(
353                    "a LiNo packet stores its links contiguously from address \
354                     {FIRST_LINK_ADDRESS}, found link {address} where {expected} belongs"
355                )));
356            }
357            if let Some(&target) = link.iter().find(
358                |&&reference| matches!(reference, Reference::Internal(target) if target >= address),
359            ) {
360                return Err(ProtocolError::malformed(format!(
361                    "link {address} refers to {target:?}, which is not an earlier link"
362                )));
363            }
364            // Links only refer backwards, so one forward pass evaluates every
365            // unary number without recursion.
366            let value_of = |reference: Reference| match reference {
367                Reference::Internal(NULL) => Some(0),
368                Reference::Internal(ONE) => Some(1),
369                Reference::Internal(address) if address >= FIRST_LINK_ADDRESS => {
370                    unary[(address - FIRST_LINK_ADDRESS) as usize]
371                }
372                _ => None,
373            };
374            let value = match *link {
375                [source, target] => value_of(source)
376                    .zip(value_of(target))
377                    .and_then(|(source, target)| source.checked_add(target)),
378                _ => None,
379            };
380            unary.push(value);
381            links.push(link);
382        }
383        Ok(Self {
384            limits,
385            links,
386            unary,
387        })
388    }
389
390    fn view(&self, reference: Reference) -> View<'a> {
391        match reference {
392            Reference::External(value) => View::External(value),
393            Reference::Internal(NULL) => View::Null,
394            Reference::Internal(address) if address < FIRST_LINK_ADDRESS => View::Marker(address),
395            Reference::Internal(address) => {
396                View::Link(self.links[(address - FIRST_LINK_ADDRESS) as usize])
397            }
398        }
399    }
400
401    fn number(&self, reference: Reference) -> ProtocolResult<u64> {
402        match reference {
403            Reference::External(value) => Ok(value),
404            Reference::Internal(NULL) => Ok(0),
405            Reference::Internal(ONE) => Ok(1),
406            Reference::Internal(address) if address >= FIRST_LINK_ADDRESS => self.unary
407                [(address - FIRST_LINK_ADDRESS) as usize]
408                .ok_or_else(|| ProtocolError::malformed("expected a unary number")),
409            _ => Err(ProtocolError::malformed("expected a unary number")),
410        }
411    }
412
413    /// The elements of the cons list `(e1 (e2 (… (en 0))))`.
414    fn chain(&self, mut tail: Reference) -> ProtocolResult<Vec<Reference>> {
415        let mut elements = Vec::new();
416        loop {
417            match self.view(tail) {
418                View::Null => return Ok(elements),
419                View::Link(&[head, next]) => {
420                    if elements.len() >= self.limits.max_nodes {
421                        return Err(ProtocolError::LimitExceeded("chain too long".into()));
422                    }
423                    elements.push(head);
424                    tail = next;
425                }
426                _ => return Err(ProtocolError::malformed("broken element chain")),
427            }
428        }
429    }
430
431    fn typed(
432        &self,
433        marker: u64,
434        elements: &[Reference],
435        depth: usize,
436        budget: &mut usize,
437    ) -> ProtocolResult<LiNo<String>> {
438        match marker {
439            NUMBER => match elements {
440                [value] => Ok(LiNo::Ref(self.number(*value)?.to_string())),
441                _ => Err(ProtocolError::malformed("a number needs exactly one value")),
442            },
443            STRING => {
444                let mut text = String::with_capacity(elements.len());
445                for &element in elements {
446                    let code_point = self.number(element)?;
447                    let character = u32::try_from(code_point)
448                        .ok()
449                        .and_then(char::from_u32)
450                        .ok_or_else(|| {
451                            ProtocolError::malformed(format!("invalid code point {code_point}"))
452                        })?;
453                    text.push(character);
454                }
455                Ok(LiNo::Ref(text))
456            }
457            LIST => self.list(elements, depth, budget),
458            IDENTIFIED => {
459                let (&id, values) = elements
460                    .split_first()
461                    .ok_or_else(|| ProtocolError::malformed("an identified link needs an id"))?;
462                let LiNo::Ref(id) = self.decode(id, depth + 1, budget)? else {
463                    return Err(ProtocolError::malformed("a link id must be a reference"));
464                };
465                Ok(LiNo::Link {
466                    id: Some(id),
467                    values: self.values(values, depth, budget)?,
468                })
469            }
470            _ => Err(ProtocolError::malformed(format!(
471                "marker {marker} cannot start a typed value"
472            ))),
473        }
474    }
475
476    fn list(
477        &self,
478        elements: &[Reference],
479        depth: usize,
480        budget: &mut usize,
481    ) -> ProtocolResult<LiNo<String>> {
482        Ok(LiNo::Link {
483            id: None,
484            values: self.values(elements, depth, budget)?,
485        })
486    }
487
488    fn values(
489        &self,
490        elements: &[Reference],
491        depth: usize,
492        budget: &mut usize,
493    ) -> ProtocolResult<Vec<LiNo<String>>> {
494        elements
495            .iter()
496            .map(|&element| self.decode(element, depth + 1, budget))
497            .collect()
498    }
499
500    fn decode(
501        &self,
502        reference: Reference,
503        depth: usize,
504        budget: &mut usize,
505    ) -> ProtocolResult<LiNo<String>> {
506        if depth >= self.limits.max_depth {
507            return Err(ProtocolError::LimitExceeded(format!(
508                "nesting deeper than {}",
509                self.limits.max_depth
510            )));
511        }
512        *budget = budget
513            .checked_sub(1)
514            .ok_or_else(|| ProtocolError::LimitExceeded("too many LiNo nodes".into()))?;
515        match self.view(reference) {
516            View::Null => Ok(LiNo::Link {
517                id: None,
518                values: Vec::new(),
519            }),
520            View::External(value) => Ok(LiNo::Ref(value.to_string())),
521            View::Marker(marker) => Err(ProtocolError::malformed(format!(
522                "marker {marker} used as a value"
523            ))),
524            View::Link(&[Reference::Internal(NUMBER), value]) => {
525                self.typed(NUMBER, &[value], depth, budget)
526            }
527            View::Link(&[Reference::Internal(marker), chain])
528                if is_marker(Reference::Internal(marker)) =>
529            {
530                let elements = self.chain(chain)?;
531                self.typed(marker, &elements, depth, budget)
532            }
533            View::Link(items) => match items.split_first() {
534                Some((&Reference::Internal(marker), elements)) if starts_with_marker(items) => {
535                    self.typed(marker, elements, depth, budget)
536                }
537                _ => self.list(items, depth, budget),
538            },
539        }
540    }
541}
link_cli/protocol/mapping.rs

link_cli/protocol/
mapping.rs
