Merge branch 'main' into main

6 files changed, 170 insertions, 0 deletions

diff --git a/entries/skairunner/.gitignore b/entries/skairunner/.gitignore
new file mode 100644
index 0000000..4ca5251
--- /dev/null
+++ b/entries/skairunner/.gitignore
@@ -0,0 +1,2 @@
+target/*
+*.proto
diff --git a/entries/skairunner/Cargo.lock b/entries/skairunner/Cargo.lock
new file mode 100644
index 0000000..71dd1ab
--- /dev/null
+++ b/entries/skairunner/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "skairunner"
+version = "0.1.0"
diff --git a/entries/skairunner/Cargo.toml b/entries/skairunner/Cargo.toml
new file mode 100644
index 0000000..4b3d98c
--- /dev/null
+++ b/entries/skairunner/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "skairunner"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/entries/skairunner/README.md b/entries/skairunner/README.md
new file mode 100644
index 0000000..1d98b17
--- /dev/null
+++ b/entries/skairunner/README.md
@@ -0,0 +1,24 @@
+# What is it
+
+A Fibonacci generator that produces a valid Protobuf3 file.
+
+Each message is Fibonacci#, where # is the number in the sequence (i.e. f(#)).
+The field "number" has a field number corresponding to the value of f(#) and a random type.
+
+The field `prevprev` has the type of the message corresponding to f(n-2) and has a field number of the value of f(n-2).
+Similarly, the field "prev" has the type of the message for f(n-1) and the field number of f(n-1).
+
+Fibonacci1 does not have `prevprev`/`prev` because field numbers have to be greater than 0.
+Fibonacci2 does not have `prevprev` for the same reason, while `prev` is omitted because duplicate field numbers are forbidden and f(1) = f(2).
+Fibonacci3 does not have `prevprev` either.
+
+The last sequence number generated is 43, because after that the field numbers become too large and are illegal.
+
+## Running
+With `cargo` installed on your system, `cargo run` will compile and output the protobuf file to stdout.
+
+To verify that the protobuf compiles, something like
+```
+cargo run > fib.proto && protoc -odescriptors.proto fib.proto
+```
+should work. Note that you will need `protoc` to do that.
\ No newline at end of file
diff --git a/entries/skairunner/src/main.rs b/entries/skairunner/src/main.rs
new file mode 100644
index 0000000..f9a5b4f
--- /dev/null
+++ b/entries/skairunner/src/main.rs
@@ -0,0 +1,117 @@
+use std::collections::HashMap;
+
+/// According to the protobuf specifications, 2^29-1 is the largest field number allowed.
+/// 1 is the smallest field number allowed.
+const MAX_FIELD_NUMBER: i32 = 536_870_911;
+
+const PROTOBUF_TYPES: &[&'static str] = &[
+    "double", "float", "int32", "int64", "uint32", "uint64", "sint64", "fixed32", "fixed64",
+    "sfixed32", "sfixed64", "bool", "string", "bytes",
+];
+
+/// According to protobuf specifications,
+/// fields 19000 thru 19999 are used by the compiler
+/// and are therefore illegal.
+fn field_number_is_illegal(n: i32) -> bool {
+    19000 <= n && n <= 19999 || n <= 0
+}
+
+/// Create a valid memo object initialized with f(0) and f(1)
+fn init_memo() -> HashMap<i32, i32> {
+    let mut memo = HashMap::new();
+    memo.insert(0, 0);
+    memo.insert(1, 1);
+    memo
+}
+
+/// Generate the fibonacci sequence number of f(n),
+/// referencing the memo and updating it if needed.
+fn fib(n: i32, memo: &mut HashMap<i32, i32>) -> Option<i32> {
+    if let Some(number) = memo.get(&n) {
+        return Some(*number);
+    }
+    let f_n = memo.get(&(n - 1))? + memo.get(&(n - 2))?;
+    memo.insert(n, f_n);
+
+    Some(f_n)
+}
+
+/// Format prev and prevprev
+fn format_submessage(n: i32, memo: &mut HashMap<i32, i32>, name: &str) -> String {
+    let number = fib(n, memo);
+    match number {
+        None => String::new(),
+        Some(number) => {
+            if field_number_is_illegal(number) {
+                String::new()
+            } else {
+                format!("    Fibonacci{} {} = {};\n", n, name, number)
+            }
+        }
+    }
+}
+
+/// Generate a Fibonacci message.
+fn message_frame(n: i32, memo: &mut HashMap<i32, i32>) -> String {
+    let n_0 = fib(n, memo)
+        .map(|number| {
+            if field_number_is_illegal(number) {
+                format!(
+                    "    // There should be a fibonacci number here, but {} is illegal",
+                    number
+                )
+            } else {
+                // Pick a semi-random type for the fib field
+                let type_name = PROTOBUF_TYPES[number as usize % PROTOBUF_TYPES.len()];
+                format!("    {} number = {};", type_name, number)
+            }
+        })
+        .unwrap_or_default();
+
+    let (n_minus_2, n_minus_1) = if n == 3 {
+        (String::new(), format_submessage(n - 1, memo, "prev"))
+    } else if n != 2 {
+        (
+            format_submessage(n - 2, memo, "prevprev"),
+            format_submessage(n - 1, memo, "prev"),
+        )
+    } else {
+        (String::new(), String::new())
+    };
+
+    format!(
+        "message Fibonacci{} {{\n\
+    {}{}{}
+}}",
+        n, n_minus_2, n_minus_1, n_0
+    )
+}
+
+fn main() {
+    let mut memo = init_memo();
+    let mut i = 1;
+    println!("syntax = \"proto3\";\n");
+    loop {
+        if fib(i, &mut memo) >= Some(MAX_FIELD_NUMBER) {
+            break;
+        }
+        println!("{}\n", message_frame(i, &mut memo));
+        i += 1;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_small_fibs() {
+        let mut memo = init_memo();
+        assert_eq!(fib(0, &mut memo), Some(0));
+        assert_eq!(fib(1, &mut memo), Some(1));
+        assert_eq!(fib(2, &mut memo), Some(1));
+        assert_eq!(fib(3, &mut memo), Some(2));
+        assert_eq!(fib(4, &mut memo), Some(3));
+        assert_eq!(fib(5, &mut memo), Some(5));
+    }
+}
diff --git a/people.json b/people.json
index b142fec..f1b99d4 100644
--- a/people.json
+++ b/people.json
@@ -676,6 +676,7 @@
 		]
 	},
 	{
+
 		"github": "themaskedtaquito",
 		"name": "Mari Allison",
 		"title": "MASLIS, UBC",
@@ -685,5 +686,16 @@
 				"link": "./entries/themaskedtaquito/fib.js"
 			}
 		]
+	},
+  {
+		"github": "skairunner",
+		"name": "Skye Im",
+		"title": "Software Engineer",
+		"entries": [
+			{
+				"name": "protobuf with rust",
+				"link": "./entries/skairunner/src/main.rs"
+			}
+		]
 	}
 ]