diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Cargo.lock | 201 | ||||
| -rw-r--r-- | Cargo.toml | 10 | ||||
| -rw-r--r-- | src/main.rs | 8 | ||||
| -rw-r--r-- | src/nfa.rs | 151 |
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) + ) + } + } +} |