summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--Cargo.lock201
-rw-r--r--Cargo.toml10
-rw-r--r--src/main.rs8
-rw-r--r--src/nfa.rs151
5 files changed, 371 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..e0477bc
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,201 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 4
+
+[[package]]
+name = "block-buffer"
+version = "0.10.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3078c7629b62d3f0439517fa394996acacc5cbc91c5a20d8c658e77abd503a71"
+dependencies = [
+ "generic-array",
+]
+
+[[package]]
+name = "cfg-if"
+version = "1.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9330f8b2ff13f34540b44e946ef35111825727b38d33286ef986142615121801"
+
+[[package]]
+name = "cpufeatures"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "59ed5838eebb26a2bb2e58f6d5b5316989ae9d08bab10e0e6d103e656d1b0280"
+dependencies = [
+ "libc",
+]
+
+[[package]]
+name = "crypto-common"
+version = "0.1.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "78c8292055d1c1df0cce5d180393dc8cce0abec0a7102adb6c7b1eef6016d60a"
+dependencies = [
+ "generic-array",
+ "typenum",
+]
+
+[[package]]
+name = "digest"
+version = "0.10.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9ed9a281f7bc9b7576e61468ba615a66a5c8cfdff42420a70aa82701a3b1e292"
+dependencies = [
+ "block-buffer",
+ "crypto-common",
+]
+
+[[package]]
+name = "folly"
+version = "0.1.0"
+dependencies = [
+ "nom",
+ "pest",
+ "pest_derive",
+ "recursion",
+]
+
+[[package]]
+name = "generic-array"
+version = "0.14.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "85649ca51fd72272d7821adaf274ad91c288277713d9c18820d8499a7ff69e9a"
+dependencies = [
+ "typenum",
+ "version_check",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.183"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b5b646652bf6661599e1da8901b3b9522896f01e736bad5f723fe7a3a27f899d"
+
+[[package]]
+name = "memchr"
+version = "2.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f8ca58f447f06ed17d5fc4043ce1b10dd205e060fb3ce5b979b8ed8e59ff3f79"
+
+[[package]]
+name = "nom"
+version = "8.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "df9761775871bdef83bee530e60050f7e54b1105350d6884eb0fb4f46c2f9405"
+dependencies = [
+ "memchr",
+]
+
+[[package]]
+name = "pest"
+version = "2.8.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e0848c601009d37dfa3430c4666e147e49cdcf1b92ecd3e63657d8a5f19da662"
+dependencies = [
+ "memchr",
+ "ucd-trie",
+]
+
+[[package]]
+name = "pest_derive"
+version = "2.8.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "11f486f1ea21e6c10ed15d5a7c77165d0ee443402f0780849d1768e7d9d6fe77"
+dependencies = [
+ "pest",
+ "pest_generator",
+]
+
+[[package]]
+name = "pest_generator"
+version = "2.8.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8040c4647b13b210a963c1ed407c1ff4fdfa01c31d6d2a098218702e6664f94f"
+dependencies = [
+ "pest",
+ "pest_meta",
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "pest_meta"
+version = "2.8.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "89815c69d36021a140146f26659a81d6c2afa33d216d736dd4be5381a7362220"
+dependencies = [
+ "pest",
+ "sha2",
+]
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.106"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8fd00f0bb2e90d81d1044c2b32617f68fcb9fa3bb7640c23e9c748e53fb30934"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.45"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "41f2619966050689382d2b44f664f4bc593e129785a36d6ee376ddf37259b924"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "recursion"
+version = "0.5.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9dba2197bf7b1d87b4dd460c195f4edeb45a94e82e8054f8d5f317c1f0e93ca1"
+
+[[package]]
+name = "sha2"
+version = "0.10.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a7507d819769d01a365ab707794a4084392c824f54a7a6a7862f8c3d0892b283"
+dependencies = [
+ "cfg-if",
+ "cpufeatures",
+ "digest",
+]
+
+[[package]]
+name = "syn"
+version = "2.0.117"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e665b8803e7b1d2a727f4023456bbbbe74da67099c585258af0ad9c5013b9b99"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "typenum"
+version = "1.19.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "562d481066bde0658276a35467c4af00bdc6ee726305698a55b86e61d7ad82bb"
+
+[[package]]
+name = "ucd-trie"
+version = "0.1.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2896d95c02a80c6d6a5d6e953d479f5ddf2dfdb6a244441010e373ac0fb88971"
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.24"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6e4313cd5fcd3dad5cafa179702e2b244f760991f45397d14d4ebf38247da75"
+
+[[package]]
+name = "version_check"
+version = "0.9.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0b928f33d975fc6ad9f86c8f283853ad26bdd5b10b7f1542aa2fa15e2289105a"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..2c92766
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "folly"
+version = "0.1.0"
+edition = "2024"
+
+[dependencies]
+nom = "8.0.0"
+pest = "2.8.6"
+pest_derive = "2.8.6"
+recursion = "0.5.4"
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..9218791
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,8 @@
+mod nfa;
+
+
+fn main() {
+ let mp_rule = "rule MP [A: formula, B: formula] { A } { A -> B } |- { B }";
+
+ println!("Hello, world!");
+}
diff --git a/src/nfa.rs b/src/nfa.rs
new file mode 100644
index 0000000..953e823
--- /dev/null
+++ b/src/nfa.rs
@@ -0,0 +1,151 @@
+use std::collections::HashMap;
+
+enum RegexParseError {
+
+}
+
+/// guaranteed to have at least 2 states
+/// state 0 is always the start state
+/// state 1 is always the accept state
+struct Nfa {
+ num_states: usize,
+ transitions: HashMap<(usize, char), Vec<usize>>
+}
+
+/// Nfa builder using Thompson's construction
+/// Invariant: state 0 is always the start state
+/// Invariant: state 1 is always the end state
+/// Invariant: start state has no incoming edges
+/// Invariant: end state has no outgoing edges
+impl Nfa {
+
+ fn from_regex(pattern: &str) -> Result<Self, RegexParseError> {
+ todo!();
+ }
+
+ fn empty() -> Self {
+ Self {
+ num_states: 2,
+ transitions: HashMap::from_iter([ ((0, '\0'), vec![1]) ])
+ }
+ }
+
+ fn from_literals(cs: impl IntoIterator<Item=char>) -> Self {
+ Self {
+ num_states: 2,
+ transitions: HashMap::from_iter(
+ cs.into_iter().map(|c| ((0, c), vec![1]))
+ )
+ }
+ }
+
+ fn from_union(lhs: Self, rhs: Self) -> Self {
+ let offset_lhs = 2;
+ let offset_rhs = 2 + lhs.num_states;
+
+ let new_transitions = [
+ ((0, '\0'), vec![offset_lhs, offset_rhs]),
+ ((offset_lhs + 1, '\0'), vec![1]),
+ ((offset_rhs + 1, '\0'), vec![1])
+ ].into_iter();
+
+ let lhs_transitions = lhs.transitions.into_iter()
+ .map(|((q_old, c), qs_new)| {
+ let new_input = (q_old + offset_lhs, c);
+ let new_output = qs_new.into_iter().map(|q| q + offset_lhs).collect();
+ (new_input, new_output)
+ });
+
+ let rhs_transitions = rhs.transitions.into_iter()
+ .map(|((q_old, c), qs_new)| {
+ let new_input = (q_old + offset_rhs, c);
+ let new_output = qs_new.into_iter().map(|q| q + offset_rhs).collect();
+ (new_input, new_output)
+ });
+
+ Self {
+ num_states: lhs.num_states + rhs.num_states + 2,
+ transitions: HashMap::from_iter(
+ new_transitions.chain(lhs_transitions).chain(rhs_transitions)
+ )
+ }
+ }
+
+ fn from_concat(lhs: Self, rhs: Self) -> Self {
+ let offset_lhs = 2;
+ let offset_rhs = 2 + lhs.num_states;
+
+ let new_transitions = [
+ ((0, '\0'), vec![offset_lhs]),
+ ((offset_lhs + 1, '\0'), vec![offset_rhs]),
+ ((offset_rhs + 1, '\0'), vec![1]),
+ ].into_iter();
+
+ let lhs_transitions = lhs.transitions.into_iter()
+ .map(|((q_old, c), qs_new)| {
+ let new_input = (q_old + offset_lhs, c);
+ let new_output = qs_new.into_iter().map(|q| q + offset_lhs).collect();
+ (new_input, new_output)
+ });
+
+ let rhs_transitions = rhs.transitions.into_iter()
+ .map(|((q_old, c), qs_new)| {
+ let new_input = (q_old + offset_rhs, c);
+ let new_output = qs_new.into_iter().map(|q| q + offset_rhs).collect();
+ (new_input, new_output)
+ });
+
+ Self {
+ num_states: lhs.num_states + rhs.num_states + 2,
+ transitions: HashMap::from_iter(
+ new_transitions.chain(lhs_transitions).chain(rhs_transitions)
+ )
+ }
+ }
+
+ fn from_star(inner: Self) -> Self {
+ const INNER_OFFSET: usize = 2;
+
+ let new_transitions = [
+ ((0, '\0'), vec![1, INNER_OFFSET]),
+ ((INNER_OFFSET + 1, '\0'), vec![INNER_OFFSET, 1]),
+ ].into_iter();
+
+ let inner_transitions = inner.transitions.into_iter()
+ .map(|((q_old, c), qs_new)| {
+ let new_input = (q_old + INNER_OFFSET, c);
+ let new_output = qs_new.into_iter().map(|q| q + INNER_OFFSET).collect();
+ (new_input, new_output)
+ });
+
+ Self {
+ num_states: inner.num_states + 2,
+ transitions: HashMap::from_iter(
+ new_transitions.chain(inner_transitions)
+ )
+ }
+ }
+
+ fn from_plus(inner: Self) -> Self {
+ const INNER_OFFSET: usize = 2;
+
+ let new_transitions = [
+ ((0, '\0'), vec![INNER_OFFSET]),
+ ((INNER_OFFSET + 1, '\0'), vec![INNER_OFFSET, 1]),
+ ].into_iter();
+
+ let inner_transitions = inner.transitions.into_iter()
+ .map(|((q_old, c), qs_new)| {
+ let new_input = (q_old + INNER_OFFSET, c);
+ let new_output = qs_new.into_iter().map(|q| q + INNER_OFFSET).collect();
+ (new_input, new_output)
+ });
+
+ Self {
+ num_states: inner.num_states + 2,
+ transitions: HashMap::from_iter(
+ new_transitions.chain(inner_transitions)
+ )
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-11 13:00:49 +0000