surrealdb / vart Goto Github PK

The range scan does not produce keys in an ordered format. Linked to surrealkv issue. Can be seen in this test case

    #[test]
    fn range_scan_order() {
        let mut tree = Tree::<VariableKey, i32>::new();

        let insert_words = [
            "test6", "test5", "test3", "test4", "test1",
        ];
        
        let entries: Vec<KV<VariableKey, i32>> = insert_words.iter()
        .map(|word| KV {
            key: VariableKey::from_str(word).unwrap(),
            value: 1,
            version: 1,
            ts: 1,
        })
        .collect(); 

        tree.bulk_insert(&entries).unwrap();


        // Test inclusive range
        let range = VariableKey::from("test1".as_bytes().to_vec())..=VariableKey::from("test7".as_bytes().to_vec());    
        for p in tree.range(range) {
            println!("{:?}", p);
        }
    }

Description:

Rust strings can freely contain null bytes. For example, "foo\0bar" is allowed in Rust and has a length of 7. Adding a null byte in Rust might result in a prefixed string.

As an alternative, consider using something like 0b10111111. All Rust strings are valid UTF-8, and a UTF-8 character can never begin with a 10-bit pattern, as this is the starting pattern of a continuation byte. Utilizing 0b10111111 in Rust strings would ensure that no byte slice derived from a string serves as a prefix for another.

Action Items:

• Evaluate the possibility of using 0b10111111 as an alternative to null bytes.

Additional Context:

This consideration aims to prevent unintended string prefixing when adding bytes in Rust. This was raised by @DelSkayn here

Firstly, thanks for sharing this repo. Recently I learn about surrealdb use ART in production and created versioned ART, I am very curious about vart and have some question: is it thread safe or how vart is used in production, I can not found vart usage in surrealdb main repo

          Just a note that rust strings can freely contain null bytes. `"foo\0bar"` is allowed in rust and will have a lenght of 7. So in rust adding a null byte you might still end up with a prefixed string.

Maybe instead of a null byte you could add something like 0b10111111? All rust strings are valid UTF-8 and a UTF-8 character can never begin with a 10 bit pattern as this the start pattern of a continuation byte. So for rust strings this would ensure that no byte slice derived from a string is a prefix of another.

Originally posted by @DelSkayn in surrealdb/surrealkv#5 (comment)