How to convert a tree structure to a map at the compilation-time?

I would like to convert a tree-like structure to a map at the compilation time. All the inputs are static, but I haven't found a way do build map out of it. I played with phf but without any luck. Is it event possible?

Here is the pseudocode:

enum Node<'a> {
    Leaf(&'static [u8]),
    Node2(&'static [u8], &'a Node<'a>, &'a Node<'a>),
}

const L1: Node = Node::Leaf(b"l1");
const L2: Node = Node::Leaf(b"l2");
const N1: Node = Node::Node2(b"n1", &L1, &L2);

const TARGET: phf::Map<u8, &'static [u8]> = phf::phf_map! {
    0x01u8 => b"n1",
    0x02u8 => b"n1_l1",
    0x03u8 => b"n1_l2",
};

const fn tree_to_map(tree: Node<'static>) -> phf::Map<u8, &'static [u8]> {
    todo!()
}

#[cfg(test)]
#[test]
fn test() {
    assert_eq!(tree_to_map(N1), TARGET);
}

Convert, but how? It's not at all obvious what correspondence you want between the two structures.

Sorry for the ambiguity.
I want to produce a static log of a tree traversal. In my example it would be:

  1. Visit N1, append the map with 1 => n1 value.
  2. Visit left node of N1 which is L1. Its name is l1 so add full path from root to this node to the map, which is appending the with 2 => n1_l1. It's a leaf, so finish traversing this branch.
  3. Visit right node of N1 which is L2. Same as above and append the map with 3 => n1_l2.

The runtime version would look like this:

#[derive(Clone)]
enum Node<'a> {
    Leaf(&'static [u8]),
    Node2(&'static [u8], &'a Node<'a>, &'a Node<'a>),
}

impl<'a> Node<'a> {
    fn name(&self) -> &'static [u8] {
        match self {
            Node::Leaf(name) => name,
            Node::Node2(name, _, _) => name,
        }
    }
}

const L1: Node = Node::Leaf(b"l1");
const L2: Node = Node::Leaf(b"l2");
const N1: Node = Node::Node2(b"n1", &L1, &L2);

fn tree_to_map(tree: Node<'static>) -> HashMap<u8, Vec<u8>> {
    let mut map = HashMap::new();
    traverse(tree, &mut map, Vec::new());
    map
}

fn traverse(tree: Node<'static>, map: &mut HashMap<u8, Vec<u8>>, mut parent_path: Vec<u8>) {
    let len = map.len() + 1;
    if !parent_path.is_empty() {
        parent_path.extend(b"_");
    }
    parent_path.extend(tree.name());
    map.insert(len as u8, parent_path.clone());
    match tree {
        Node::Leaf(_) => (),
        Node::Node2(_, left, right) => {
            traverse(left.clone(), map, parent_path.clone());
            traverse(right.clone(), map, parent_path);
        }
    }
}

#[cfg(test)]
#[test]
fn test() {
    let map = tree_to_map(N1);
    assert_eq!(map.get(&1).unwrap(), b"n1");
    assert_eq!(map.get(&2).unwrap(), b"n1_l1");
    assert_eq!(map.get(&3).unwrap(), b"n1_l2");
    assert!(map.get(&4).is_none());
}

You can use the code you have, slightly adapted to use phf_codegen and run it in build.rs. It will generate a file map.rs that contains the definition of the map, like static MAP: phf::Map<u8, &[u8]> = .... You then include that file inside you code, for example in main.rs with include!(concat!(env!("OUT_DIR"), "/map.rs"));. This method is described in the documentation of phf

build.rs:

use std::env;
use std::fs::File;
use std::io::BufWriter;
use std::path::Path;
use std::io::Write as _;
use phf_codegen::Map;

#[derive(Clone)]
pub enum Node<'a> {
    Leaf(&'static [u8]),
    Node2(&'static [u8], &'a Node<'a>, &'a Node<'a>),
}

impl<'a> Node<'a> {
    fn name(&self) -> &'static [u8] {
        match self {
            Node::Leaf(name) => name,
            Node::Node2(name, _, _) => name,
        }
    }
}

const L1: Node = Node::Leaf(b"l1");

const L2: Node = Node::Leaf(b"l2");

pub const N1: Node = Node::Node2(b"n1", &L1, &L2);

fn tree_to_map(tree: &Node<'static>) -> Map<u8> {
    let mut map = Map::new();
    traverse(tree, &mut 1, &mut map, Vec::new());
    map
}

fn traverse(tree: &Node<'static>, id: &mut u8, map: &mut Map<u8>, mut parent_path: Vec<u8>) {
    if !parent_path.is_empty() {
        parent_path.extend(b"_");
    }
    let path = [&parent_path, tree.name()].concat();
    // we need the rust code that compiles to the correct byte array
    let byte_array_code = format!("&{path:?}");
    map.entry(*id, &byte_array_code);
    *id += 1;
    match tree {
        Node::Leaf(_) => (),
        Node::Node2(_, left, right) => {
            traverse(left, id, map, path.clone());
            traverse(right, id, map, path);
        }
    }
}

fn main() {
    let root = N1;

    let path = Path::new(&env::var("OUT_DIR").unwrap()).join("map.rs");
    let mut file = BufWriter::new(File::create(path).unwrap());

    write!(
        &mut file,
        "static MAP: phf::Map<u8, &[u8]> = {};",
        tree_to_map(&root).build()
    ).unwrap();
}

I know this is possible. I my case, Node instances are defined in the same crate I'm writing (the one with build.rs), so I have this issue: Problems With Using include!() in build.rs for .rs Code - Rust Internals

While you can hack something with include! where you include files from both build.rs and main.rs, the best solution would be to have a seperate crate for the data. In that crate, you'd only define Node and its impl blocks, as well as the constants for the nodes. This way, you can use it from build.rs and main.rs.

This is not a solution for me, as I'm building this as part of a library for embedded system and I don't want my users to create two crates.

You can reexport the data crate from the lib. That way, everything is accessible from one crate.

The problem with doing this with a const fn is that it also needs to be valid to be called with a runtime value, which greatly complicates the implementation. There's no common way of creating 'static values at runtime and compile time, hence there's no way to do this in a const fn. What you can do though is to not create 'static values in the const fn, but instead create all you need outside and then reference it inside the const fn, essentially splitting the solution in two phases. Another problem is that `const fn's can't return data whose size is dependent on the input, but again you can split this into two steps: calculate the size needed and then compute the actual function using an array of that size where needed.

Here's a proof of concept of your tree_to_map made into a macro (because the user would otherwise have to write each step individually): Rust Playground

This is exactly what I need :slight_smile: Thank you all the work you had to do to prepare the code.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.