Exercise: Protobuf Parsing

In this exercise, you will build a parser for the protobuf binary encoding. Don’t worry, it’s simpler than it seems! This illustrates a common parsing pattern, passing slices of data. The underlying data itself is never copied.

Fully parsing a protobuf message requires knowing the types of the fields, indexed by their field numbers. That is typically provided in a proto file. In this exercise, we’ll encode that information into match statements in functions that get called for each field.

We’ll use the following proto:

  1. message PhoneNumber {
  2.   optional string number = 1;
  3.   optional string type = 2;
  4. }
  6. message Person {
  7.   optional string name = 1;
  8.   optional int32 id = 2;
  9.   repeated PhoneNumber phones = 3;
  10. }

A proto message is encoded as a series of fields, one after the next. Each is implemented as a “tag” followed by the value. The tag contains a field number (e.g., 2 for the id field of a Person message) and a wire type defining how the payload should be determined from the byte stream.

Integers, including the tag, are represented with a variable-length encoding called VARINT. Luckily, parse_varint is defined for you below. The given code also defines callbacks to handle Person and PhoneNumber fields, and to parse a message into a series of calls to those callbacks.

What remains for you is to implement the parse_field function and the ProtoMessage trait for Person and PhoneNumber.

  1. /// A wire type as seen on the wire.
  2. enum WireType {
  3.     /// The Varint WireType indicates the value is a single VARINT.
  4.     Varint,
  5.     /// The I64 WireType indicates that the value is precisely 8 bytes in
  6.     /// little-endian order containing a 64-bit signed integer or double type.
  7.     //I64,  -- not needed for this exercise
  8.     /// The Len WireType indicates that the value is a length represented as a
  9.     /// VARINT followed by exactly that number of bytes.
  10.     Len,
  11.     // The I32 WireType indicates that the value is precisely 4 bytes in
  12.     // little-endian order containing a 32-bit signed integer or float type.
  13.     //I32,  -- not needed for this exercise
  14. }
  16. #[derive(Debug)]
  17. /// A field's value, typed based on the wire type.
  18. enum FieldValue<'a> {
  19.     Varint(u64),
  20.     //I64(i64),  -- not needed for this exercise
  21.     Len(&'a [u8]),
  22.     //I32(i32),  -- not needed for this exercise
  23. }
  25. #[derive(Debug)]
  26. /// A field, containing the field number and its value.
  27. struct Field<'a> {
  28.     field_num: u64,
  29.     value: FieldValue<'a>,
  30. }
  32. trait ProtoMessage<'a>: Default {
  33.     fn add_field(&mut self, field: Field<'a>);
  34. }
  36. impl From<u64> for WireType {
  37.     fn from(value: u64) -> Self {
  38.         match value {
  39.             0 => WireType::Varint,
  40.             //1 => WireType::I64,  -- not needed for this exercise
  41.             2 => WireType::Len,
  42.             //5 => WireType::I32,  -- not needed for this exercise
  43.             _ => panic!("Invalid wire type: {value}"),
  44.         }
  45.     }
  46. }
  48. impl<'a> FieldValue<'a> {
  49.     fn as_str(&self) -> &'a str {
  50.         let FieldValue::Len(data) = self else {
  51.             panic!("Expected string to be a `Len` field");
  52.         };
  53.         std::str::from_utf8(data).expect("Invalid string")
  54.     }
  56.     fn as_bytes(&self) -> &'a [u8] {
  57.         let FieldValue::Len(data) = self else {
  58.             panic!("Expected bytes to be a `Len` field");
  59.         };
  60.         data
  61.     }
  63.     fn as_u64(&self) -> u64 {
  64.         let FieldValue::Varint(value) = self else {
  65.             panic!("Expected `u64` to be a `Varint` field");
  66.         };
  67.         *value
  68.     }
  69. }
  71. /// Parse a VARINT, returning the parsed value and the remaining bytes.
  72. fn parse_varint(data: &[u8]) -> (u64, &[u8]) {
  73.     for i in 0..7 {
  74.         let Some(b) = data.get(i) else {
  75.             panic!("Not enough bytes for varint");
  76.         };
  77.         if b & 0x80 == 0 {
  78.             // This is the last byte of the VARINT, so convert it to
  79.             // a u64 and return it.
  80.             let mut value = 0u64;
  81.             for b in data[..=i].iter().rev() {
  82.                 value = (value << 7) | (b & 0x7f) as u64;
  83.             }
  84.             return (value, &data[i + 1..]);
  85.         }
  86.     }
  88.     // More than 7 bytes is invalid.
  89.     panic!("Too many bytes for varint");
  90. }
  92. /// Convert a tag into a field number and a WireType.
  93. fn unpack_tag(tag: u64) -> (u64, WireType) {
  94.     let field_num = tag >> 3;
  95.     let wire_type = WireType::from(tag & 0x7);
  96.     (field_num, wire_type)
  97. }
  99. /// Parse a field, returning the remaining bytes
  100. fn parse_field(data: &[u8]) -> (Field, &[u8]) {
  101.     let (tag, remainder) = parse_varint(data);
  102.     let (field_num, wire_type) = unpack_tag(tag);
  103.     let (fieldvalue, remainder) = match wire_type {
  104.         _ => todo!("Based on the wire type, build a Field, consuming as many bytes as necessary.")
  105.     };
  106.     todo!("Return the field, and any un-consumed bytes.")
  107. }
  109. /// Parse a message in the given data, calling `T::add_field` for each field in
  110. /// the message.
  111. ///
  112. /// The entire input is consumed.
  113. fn parse_message<'a, T: ProtoMessage<'a>>(mut data: &'a [u8]) -> T {
  114.     let mut result = T::default();
  115.     while !data.is_empty() {
  116.         let parsed = parse_field(data);
  117.         result.add_field(parsed.0);
  118.         data = parsed.1;
  119.     }
  120.     result
  121. }
  123. #[derive(Debug, Default)]
  124. struct PhoneNumber<'a> {
  125.     number: &'a str,
  126.     type_: &'a str,
  127. }
  129. #[derive(Debug, Default)]
  130. struct Person<'a> {
  131.     name: &'a str,
  132.     id: u64,
  133.     phone: Vec<PhoneNumber<'a>>,
  134. }
  136. // TODO: Implement ProtoMessage for Person and PhoneNumber.
  138. fn main() {
  139.     let person: Person = parse_message(&[
  140.         0x0a, 0x07, 0x6d, 0x61, 0x78, 0x77, 0x65, 0x6c, 0x6c, 0x10, 0x2a, 0x1a,
  141.         0x16, 0x0a, 0x0e, 0x2b, 0x31, 0x32, 0x30, 0x32, 0x2d, 0x35, 0x35, 0x35,
  142.         0x2d, 0x31, 0x32, 0x31, 0x32, 0x12, 0x04, 0x68, 0x6f, 0x6d, 0x65, 0x1a,
  143.         0x18, 0x0a, 0x0e, 0x2b, 0x31, 0x38, 0x30, 0x30, 0x2d, 0x38, 0x36, 0x37,
  144.         0x2d, 0x35, 0x33, 0x30, 0x38, 0x12, 0x06, 0x6d, 0x6f, 0x62, 0x69, 0x6c,
  145.         0x65,
  146.     ]);
  147.     println!("{:#?}", person);
  148. }

This slide and its sub-slides should take about 30 minutes.

  • In this exercise there are various cases where protobuf parsing might fail, e.g. if you try to parse an i32 when there are fewer than 4 bytes left in the data buffer. In normal Rust code we’d handle this with the Result enum, but for simplicity in this exercise we panic if any errors are encountered. On day 4 we’ll cover error handling in Rust in more detail.