diff --git a/src/lib_mir/prototype/Cargo.lock b/src/lib_mir/prototype/Cargo.lock new file mode 100644 index 0000000000000000000000000000000000000000..f4f39f2e668e8265bbafee8d1ddf8dc36081f180 --- /dev/null +++ b/src/lib_mir/prototype/Cargo.lock @@ -0,0 +1,690 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aho-corasick" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6748e8def348ed4d14996fa801f4122cd763fff530258cdc03f64b25f89d3a5a" +dependencies = [ + "memchr", +] + +[[package]] +name = "ascii" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d92bec98840b8f03a5ff5413de5293bfcd8bf96467cf5452609f939ec6f5de16" + +[[package]] +name = "ascii-canvas" +version = "3.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8824ecca2e851cec16968d54a01dd372ef8f95b244fb84b84e70128be347c3c6" +dependencies = [ + "term", +] + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "bit-set" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0700ddab506f33b20a03b13996eccd309a48e5ff77d0d95926aa0210fb4e95f1" +dependencies = [ + "bit-vec", +] + +[[package]] +name = "bit-vec" +version = "0.6.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "349f9b6a179ed607305526ca489b34ad0a41aed5f7980fa90eb03160b69598fb" + +[[package]] +name = "bitflags" +version = "1.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" + +[[package]] +name = "bitflags" +version = "2.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b4682ae6287fcf752ecaabbfcc7b6f9b72aa33933dc23a554d853aea8eea8635" + +[[package]] +name = "cc" +version = "1.0.83" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f1174fb0b6ec23863f8b971027804a42614e347eafb0a95bf0b12cdae21fc4d0" +dependencies = [ + "libc", +] + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "crunchy" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7a81dae078cea95a014a339291cec439d2f232ebe854a9d672b796c6afafa9b7" + +[[package]] +name = "derive-where" +version = "1.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "875a0460143f2dbcc71fd8a63f34b7c83ac66f14bead94054e7cd619c57bbb27" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "diff" +version = "0.1.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "56254986775e3233ffa9c4d7d3faaf6d36a2c09d30b20687e9f88bc8bafc16c8" + +[[package]] +name = "dirs-next" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b98cf8ebf19c3d1b223e151f99a4f9f0690dca41414773390fc824184ac833e1" +dependencies = [ + "cfg-if", + "dirs-sys-next", +] + +[[package]] +name = "dirs-sys-next" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ebda144c4fe02d1f7ea1a7d9641b6fc6b580adcfa024ae48797ecdeb6825b4d" +dependencies = [ + "libc", + "redox_users", + "winapi", +] + +[[package]] +name = "either" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07" + +[[package]] +name = "ena" +version = "0.14.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c533630cf40e9caa44bd91aadc88a75d75a4c3a12b4cfde353cbed41daa1e1f1" +dependencies = [ + "log", +] + +[[package]] +name = "equivalent" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5" + +[[package]] +name = "errno" +version = "0.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6b30f669a7961ef1631673d2766cc92f52d64f7ef354d4fe0ddfd30ed52f0f4f" +dependencies = [ + "errno-dragonfly", + "libc", + "windows-sys", +] + +[[package]] +name = "errno-dragonfly" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "aa68f1b12764fab894d2755d2518754e71b4fd80ecfb822714a1206c2aab39bf" +dependencies = [ + "cc", + "libc", +] + +[[package]] +name = "fixedbitset" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80" + +[[package]] +name = "getrandom" +version = "0.2.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "be4136b2a15dd319360be1c07d9933517ccf0be8f16bf62a3bee4f0d618df427" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "hashbrown" +version = "0.14.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2c6201b9ff9fd90a5a3bac2e56a830d0caa509576f0e503818ee82c181b3437a" + +[[package]] +name = "hermit-abi" +version = "0.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "443144c8cdadd93ebf52ddb4056d257f5b52c04d3c804e657d19eb73fc33668b" + +[[package]] +name = "hex" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7f24254aa9a54b5c858eaee2f5bccdb46aaf0e486a595ed5fd8f86ba55232a70" + +[[package]] +name = "indexmap" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d5477fe2230a79769d8dc68e0eabf5437907c0457a5614a9e8dddb67f65eb65d" +dependencies = [ + "equivalent", + "hashbrown", +] + +[[package]] +name = "is-terminal" +version = "0.4.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cb0889898416213fab133e1d33a0e5858a48177452750691bde3666d0fdbaf8b" +dependencies = [ + "hermit-abi", + "rustix", + "windows-sys", +] + +[[package]] +name = "itertools" +version = "0.10.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0fd2260e829bddf4cb6ea802289de2f86d6a7a690192fbe91b3f46e0f2c8473" +dependencies = [ + "either", +] + +[[package]] +name = "lalrpop" +version = "0.20.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "da4081d44f4611b66c6dd725e6de3169f9f63905421e8626fcb86b6a898998b8" +dependencies = [ + "ascii-canvas", + "bit-set", + "diff", + "ena", + "is-terminal", + "itertools", + "lalrpop-util", + "petgraph", + "pico-args", + "regex", + "regex-syntax", + "string_cache", + "term", + "tiny-keccak", + "unicode-xid", +] + +[[package]] +name = "lalrpop-util" +version = "0.20.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3f35c735096c0293d313e8f2a641627472b83d01b937177fe76e5e2708d31e0d" +dependencies = [ + "regex", +] + +[[package]] +name = "libc" +version = "0.2.147" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b4668fb0ea861c1df094127ac5f1da3409a82116a4ba74fca2e58ef927159bb3" + +[[package]] +name = "linux-raw-sys" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "57bcfdad1b858c2db7c38303a6d2ad4dfaf5eb53dfeb0910128b2c26d6158503" + +[[package]] +name = "lock_api" +version = "0.4.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c1cc9717a20b1bb222f333e6a92fd32f7d8a18ddc5a3191a11af45dcbf4dcd16" +dependencies = [ + "autocfg", + "scopeguard", +] + +[[package]] +name = "log" +version = "0.4.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5e6163cb8c49088c2c36f57875e58ccd8c87c7427f7fbd50ea6710b2f3f2e8f" + +[[package]] +name = "memchr" +version = "2.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2dffe52ecf27772e601905b7522cb4ef790d2cc203488bbd0e2fe85fcb74566d" + +[[package]] +name = "new_debug_unreachable" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e4a24736216ec316047a1fc4252e27dabb04218aa4a3f37c6e7ddbf1f9782b54" + +[[package]] +name = "num-bigint" +version = "0.4.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "608e7659b5c3d7cba262d894801b9ec9d00de989e8a82bd4bef91d08da45cdc0" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.45" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "225d3389fb3509a24c93f5c29eb6bde2586b98d9f016636dff58d7c6f7569cd9" +dependencies = [ + "autocfg", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f30b0abd723be7e2ffca1272140fac1a2f084c77ec3e123c192b66af1ee9e6c2" +dependencies = [ + "autocfg", +] + +[[package]] +name = "once_cell" +version = "1.18.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dd8b5dd2ae5ed71462c540258bedcb51965123ad7e7ccf4b9a8cafaa4a63576d" + +[[package]] +name = "parking_lot" +version = "0.12.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3742b2c103b9f06bc9fff0a37ff4912935851bee6d36f3c02bcc755bcfec228f" +dependencies = [ + "lock_api", + "parking_lot_core", +] + +[[package]] +name = "parking_lot_core" +version = "0.9.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93f00c865fe7cabf650081affecd3871070f26767e7b2070a3ffae14c654b447" +dependencies = [ + "cfg-if", + "libc", + "redox_syscall 0.3.5", + "smallvec", + "windows-targets", +] + +[[package]] +name = "petgraph" +version = "0.6.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e1d3afd2628e69da2be385eb6f2fd57c8ac7977ceeff6dc166ff1657b0e386a9" +dependencies = [ + "fixedbitset", + "indexmap", +] + +[[package]] +name = "phf_shared" +version = "0.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b6796ad771acdc0123d2a88dc428b5e38ef24456743ddb1744ed628f9815c096" +dependencies = [ + "siphasher", +] + +[[package]] +name = "pico-args" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5be167a7af36ee22fe3115051bc51f6e6c7054c9348e28deb4f49bd6f705a315" + +[[package]] +name = "precomputed-hash" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "925383efa346730478fb4838dbe9137d2a47675ad789c546d150a6e1dd4ab31c" + +[[package]] +name = "proc-macro2" +version = "1.0.66" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "18fb31db3f9bddb2ea821cde30a9f70117e3f119938b5ee630b7403aa6e2ead9" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "prototype" +version = "0.1.0" +dependencies = [ + "ascii", + "derive-where", + "hex", + "lalrpop", + "lalrpop-util", + "num-bigint", + "seq-macro", +] + +[[package]] +name = "quote" +version = "1.0.33" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5267fca4496028628a95160fc423a33e8b2e6af8a5302579e322e4b520293cae" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "redox_syscall" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fb5a58c1855b4b6819d59012155603f0b22ad30cad752600aadfcb695265519a" +dependencies = [ + "bitflags 1.3.2", +] + +[[package]] +name = "redox_syscall" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "567664f262709473930a4bf9e51bf2ebf3348f2e748ccc50dea20646858f8f29" +dependencies = [ + "bitflags 1.3.2", +] + +[[package]] +name = "redox_users" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b033d837a7cf162d7993aded9304e30a83213c648b6e389db233191f891e5c2b" +dependencies = [ + "getrandom", + "redox_syscall 0.2.16", + "thiserror", +] + +[[package]] +name = "regex" +version = "1.9.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "12de2eff854e5fa4b1295edd650e227e9d8fb0c9e90b12e7f36d6a6811791a29" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata", + "regex-syntax", +] + +[[package]] +name = "regex-automata" +version = "0.3.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "49530408a136e16e5b486e883fbb6ba058e8e4e8ae6621a77b048b314336e629" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-syntax" +version = "0.7.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dbb5fb1acd8a1a18b3dd5be62d25485eb770e05afb408a9627d14d451bae12da" + +[[package]] +name = "rustix" +version = "0.38.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9bfe0f2582b4931a45d1fa608f8a8722e8b3c7ac54dd6d5f3b3212791fedef49" +dependencies = [ + "bitflags 2.4.0", + "errno", + "libc", + "linux-raw-sys", + "windows-sys", +] + +[[package]] +name = "rustversion" +version = "1.0.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7ffc183a10b4478d04cbbbfc96d0873219d962dd5accaff2ffbd4ceb7df837f4" + +[[package]] +name = "scopeguard" +version = "1.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49" + +[[package]] +name = "seq-macro" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a3f0bf26fd526d2a95683cd0f87bf103b8539e2ca1ef48ce002d67aad59aa0b4" + +[[package]] +name = "siphasher" +version = "0.3.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38b58827f4464d87d377d175e90bf58eb00fd8716ff0a62f80356b5e61555d0d" + +[[package]] +name = "smallvec" +version = "1.11.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "62bb4feee49fdd9f707ef802e22365a35de4b7b299de4763d44bfea899442ff9" + +[[package]] +name = "string_cache" +version = "0.8.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f91138e76242f575eb1d3b38b4f1362f10d3a43f47d182a5b359af488a02293b" +dependencies = [ + "new_debug_unreachable", + "once_cell", + "parking_lot", + "phf_shared", + "precomputed-hash", +] + +[[package]] +name = "syn" +version = "2.0.29" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c324c494eba9d92503e6f1ef2e6df781e78f6a7705a0202d9801b198807d518a" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "term" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c59df8ac95d96ff9bede18eb7300b0fda5e5d8d90960e76f8e14ae765eedbf1f" +dependencies = [ + "dirs-next", + "rustversion", + "winapi", +] + +[[package]] +name = "thiserror" +version = "1.0.47" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "97a802ec30afc17eee47b2855fc72e0c4cd62be9b4efe6591edde0ec5bd68d8f" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.47" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6bb623b56e39ab7dcd4b1b98bb6c8f8d907ed255b18de254088016b27a8ee19b" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "tiny-keccak" +version = "2.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2c9d3793400a45f954c52e73d068316d76b6f4e36977e3fcebb13a2721e80237" +dependencies = [ + "crunchy", +] + +[[package]] +name = "unicode-ident" +version = "1.0.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "301abaae475aa91687eb82514b328ab47a211a533026cb25fc3e519b86adfc3c" + +[[package]] +name = "unicode-xid" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f962df74c8c05a667b5ee8bcf162993134c104e96440b663c8daa176dc772d8c" + +[[package]] +name = "wasi" +version = "0.11.0+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" + +[[package]] +name = "windows-sys" +version = "0.48.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "677d2418bec65e3338edb076e806bc1ec15693c5d0104683f2efe857f61056a9" +dependencies = [ + "windows-targets", +] + +[[package]] +name = "windows-targets" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9a2fa6e2155d7247be68c096456083145c183cbbbc2764150dda45a87197940c" +dependencies = [ + "windows_aarch64_gnullvm", + "windows_aarch64_msvc", + "windows_i686_gnu", + "windows_i686_msvc", + "windows_x86_64_gnu", + "windows_x86_64_gnullvm", + "windows_x86_64_msvc", +] + +[[package]] +name = "windows_aarch64_gnullvm" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2b38e32f0abccf9987a4e3079dfb67dcd799fb61361e53e2882c3cbaf0d905d8" + +[[package]] +name = "windows_aarch64_msvc" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dc35310971f3b2dbbf3f0690a219f40e2d9afcf64f9ab7cc1be722937c26b4bc" + +[[package]] +name = "windows_i686_gnu" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a75915e7def60c94dcef72200b9a8e58e5091744960da64ec734a6c6e9b3743e" + +[[package]] +name = "windows_i686_msvc" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8f55c233f70c4b27f66c523580f78f1004e8b5a8b659e05a4eb49d4166cca406" + +[[package]] +name = "windows_x86_64_gnu" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "53d40abd2583d23e4718fddf1ebec84dbff8381c07cae67ff7768bbf19c6718e" + +[[package]] +name = "windows_x86_64_gnullvm" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0b7b52767868a23d5bab768e390dc5f5c55825b6d30b86c844ff2dc7414044cc" + +[[package]] +name = "windows_x86_64_msvc" +version = "0.48.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ed94fce61571a4006852b7389a063ab983c02eb1bb37b47f8272ce92d06d9538" diff --git a/src/lib_mir/prototype/Cargo.toml b/src/lib_mir/prototype/Cargo.toml new file mode 100644 index 0000000000000000000000000000000000000000..7857d6da129f7318a7706fd5b09adf29f395cb0d --- /dev/null +++ b/src/lib_mir/prototype/Cargo.toml @@ -0,0 +1,17 @@ +[package] +name = "prototype" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[build-dependencies] +lalrpop = { version = "0.20.0", features = ["lexer"] } + +[dependencies] +lalrpop-util = { version = "0.20.0", features = ["lexer"] } +num-bigint = "0.4" +ascii = "1.1" +hex = "0.4" +seq-macro = "0.3" +derive-where = "1" diff --git a/src/lib_mir/prototype/README.md b/src/lib_mir/prototype/README.md new file mode 100644 index 0000000000000000000000000000000000000000..25cbae802428fd946b95ad491dbcbea996b7311d --- /dev/null +++ b/src/lib_mir/prototype/README.md @@ -0,0 +1,15 @@ +# Michelson in Rust prototype + +This is a rough prototype for MIR, primarily intended as a proof of concept, and +testing grounds for exploring possible designs. At the time of writing, large +parts of Michelson are not implemented, but it can run some basic code. + +In particular, it can run code from `../test/fixtures/`, although it can't parse +`tzt` files. In order to run those, assuming you have Rust toolchain installed, you can do something like this: + +```bash +pcregrep -o1 --multiline 'code\s*{((?:\n|.)*?)}\s*;\ninput' ../test/fixtures/factorial.tzt | cargo run nat 30 +``` + +The code to run is accepted at stdin, and input type and value are accepted as +the first and the second command line arguments respectively. diff --git a/src/lib_mir/prototype/build.rs b/src/lib_mir/prototype/build.rs new file mode 100644 index 0000000000000000000000000000000000000000..a8813c78d0382c05fae4751e2166142cc5b9d5b0 --- /dev/null +++ b/src/lib_mir/prototype/build.rs @@ -0,0 +1,28 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +fn main() { + lalrpop::process_root().unwrap(); +} diff --git a/src/lib_mir/prototype/src/ast.rs b/src/lib_mir/prototype/src/ast.rs new file mode 100644 index 0000000000000000000000000000000000000000..059979c45bf13752ea593b51eb0f37ffa8a335a0 --- /dev/null +++ b/src/lib_mir/prototype/src/ast.rs @@ -0,0 +1,39 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +pub mod ext; +pub mod instr; +mod macros; +pub mod tvalue; +pub mod ty; +pub mod uvalue; +pub mod void; + +pub use ext::{Parsed, Typechecked}; +pub use instr::{Instr, InstrExt}; +pub use tvalue::{TValue, TValueExt}; +pub use ty::{Type, TypeExt}; +pub use uvalue::{UValue, UValueExt}; +pub use void::Void; diff --git a/src/lib_mir/prototype/src/ast/ext.rs b/src/lib_mir/prototype/src/ast/ext.rs new file mode 100644 index 0000000000000000000000000000000000000000..5dd2e20a1ca4e6c4f1a20db6f3b3c0785c5e5003 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/ext.rs @@ -0,0 +1,30 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +pub mod parsed; +pub mod typechecked; + +pub use parsed::Parsed; +pub use typechecked::Typechecked; diff --git a/src/lib_mir/prototype/src/ast/ext/parsed.rs b/src/lib_mir/prototype/src/ast/ext/parsed.rs new file mode 100644 index 0000000000000000000000000000000000000000..6cc6aa05f72c4cd3e1b480e5c6562890eb979db5 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/ext/parsed.rs @@ -0,0 +1,112 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use crate::ast::{InstrExt, Type, TypeExt, UValue, UValueExt, Void}; + +pub enum Parsed {} + +impl UValueExt for Parsed { + type Int = (); + type String = (); + type Bytes = (); + type Unit = (); + type True = (); + type False = (); + type Pair = (); + type Left = (); + type Right = (); + type Some = (); + type None = (); + type Seq = (); + type LambdaRec = (); + type Instr = (); + type Ext = Void; +} + +impl InstrExt for Parsed { + type Car = (); + type Cdr = (); + type Pair = (); + type Push = (Type, Box>); + type Nil = Type; + type Add = (); + type Drop = (); + type DropN = (); + type Dup = (); + type DupN = (); + type Dip = (); + type DipN = (); + type Swap = (); + type Compare = (); + type PairN = (); + type Unpair = (); + type UnpairN = (); + type Dig = (); + type Dug = (); + type Failwith = (); + type Never = (); + type If = (); + type Nest = (); + type Unit = (); + type Loop = (); + type Gt = (); + type Le = (); + type Int = (); + type Mul = (); +} + +impl TypeExt for Parsed { + type Key = (); + type Unit = (); + type Signature = (); + type ChainId = (); + type Option = (); + type List = (); + type Set = (); + type Operation = (); + type Contract = (); + type Ticket = (); + type Pair = (); + type Or = (); + type Lambda = (); + type Map = (); + type BigMap = (); + type Int = (); + type Nat = (); + type String = (); + type Bytes = (); + type Mutez = (); + type Bool = (); + type KeyHash = (); + type Bls12381Fr = (); + type Bls12381G1 = (); + type Bls12381G2 = (); + type Timestamp = (); + type Address = (); + type SaplingState = (); + type SaplingTransaction = (); + type Never = (); + type Ext = Void; +} diff --git a/src/lib_mir/prototype/src/ast/ext/typechecked.rs b/src/lib_mir/prototype/src/ast/ext/typechecked.rs new file mode 100644 index 0000000000000000000000000000000000000000..3ec3c7e2a10a63be2d43b5442d62f541cf28f296 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/ext/typechecked.rs @@ -0,0 +1,98 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use crate::ast::{InstrExt, TValue, TValueExt}; + +pub enum Typechecked {} + +impl InstrExt for Typechecked { + type Car = (); + type Cdr = (); + type Pair = (); + type Push = TValue; + type Nil = (); + type Add = fn(TValue, TValue) -> TValue; + type Drop = (); + type DropN = (); + type Dup = (); + type DupN = (); + type Dip = (); + type DipN = (); + type Swap = (); + type Compare = (); + type PairN = (); + type Unpair = (); + type UnpairN = (); + type Dig = (); + type Dug = (); + type Failwith = (); + type Never = (); + type If = (); + type Nest = (); + type Unit = (); + type Loop = (); + type Gt = (); + type Le = (); + type Int = (); + type Mul = fn(TValue, TValue) -> TValue; +} + +impl TValueExt for Typechecked { + type Key = (); + type Unit = (); + type Signature = (); + type ChainId = (); + type Option = TValueMeta; + type List = (); + type Set = (); + type Operation = (); + type Contract = (); + type Ticket = (); + type Pair = TValueMeta; + type Or = TValueMeta; + type Lambda = (); + type Map = (); + type BigMap = (); + type Int = (); + type Nat = (); + type String = (); + type Bytes = (); + type Mutez = (); + type Bool = (); + type KeyHash = (); + type Bls12381Fr = (); + type Bls12381G1 = (); + type Bls12381G2 = (); + type Timestamp = (); + type Address = (); + type SaplingState = (); + type SaplingTransaction = (); + type Never = (); +} + +#[derive(Debug, Eq, PartialEq, Clone, Copy)] +pub struct TValueMeta { + pub comparable: bool, +} diff --git a/src/lib_mir/prototype/src/ast/instr.rs b/src/lib_mir/prototype/src/ast/instr.rs new file mode 100644 index 0000000000000000000000000000000000000000..8c6d69b6481e17c61f214d1120db721e3635b587 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/instr.rs @@ -0,0 +1,59 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +super::macros::ttg_extend!( + @derive(Debug, Clone, PartialEq, Eq) + pub enum Instr { + Car(), + Cdr(), + Pair(), + Push(), + Nil(), + Add(), + Drop(), + DropN(usize), + Dup(), + DupN(usize), + Dip(Vec), + DipN(usize, Vec), + Swap(), + Compare(), + PairN(usize), + Unpair(), + UnpairN(usize), + Dig(usize), + Dug(usize), + Failwith(), + Never(), + If(Vec, Vec), + Nest(Vec), + Unit(), + Loop(Vec), + Gt(), + Le(), + Int(), + Mul(), + } +); diff --git a/src/lib_mir/prototype/src/ast/macros.rs b/src/lib_mir/prototype/src/ast/macros.rs new file mode 100644 index 0000000000000000000000000000000000000000..6de912fe7aac4e55f3932234a62f2c5038663999 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/macros.rs @@ -0,0 +1,55 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +macro_rules! ttg_extend { + ( $(#[$($ann:tt)*])* + $(@derive($($traits:ident),* $(,)*))? + $pub:vis $enum:ident $mainTy:ident <$extname:ident: $ext:tt $(+ $exts:tt)*> { + $($name:ident ( $($ty:ty),* $(,)*)),* $(,)* + } $(; $($extra:tt)*)?) => { + $(#[$($ann)*])* + $(#[derive_where::derive_where($($traits),*)])? + $pub $enum $mainTy<$extname: $ext $(+ $exts)*> { + $( + $name(<$extname as $ext>::$name, $($ty),*) + ),* + } + + use std::fmt::Debug; + $crate::ast::macros::ttg_extend!(@trait $pub $ext; $($name)*; {$($(+ $traits)*)?}; $($($extra)*)?); + }; + (@trait $pub:vis $ext:ident; $($name:ident)* ; $traits:tt; $($extra:tt)*) => { + $pub trait $ext + { + $($crate::ast::macros::ttg_extend!(@type $name; $traits);)* + $($extra)* + } + }; + (@type $name:ident; { $(+ $($traits:tt)+)? }) => { + type $name$(: $($traits)*)?; + }; +} + +pub(crate) use ttg_extend; diff --git a/src/lib_mir/prototype/src/ast/tvalue.rs b/src/lib_mir/prototype/src/ast/tvalue.rs new file mode 100644 index 0000000000000000000000000000000000000000..b7d0833bd4d74e225ee915c43f0539850bf4796d --- /dev/null +++ b/src/lib_mir/prototype/src/ast/tvalue.rs @@ -0,0 +1,126 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use ascii::AsciiString; +use num_bigint::{BigInt, BigUint}; +use std::collections::BTreeSet; + +use crate::ast::{Instr, InstrExt}; + +pub mod comparable; +pub mod typechecked; + +pub use comparable::Comparable; + +super::macros::ttg_extend!( + #[repr(u8)] // required as we're doing some unsafe shenanigans + #[allow(dead_code)] + @derive(Debug, Clone, PartialEq, Eq) + pub enum TValue { + Unit(), + Option(Option>), + List(Vec), + Set(BTreeSet>), + Pair(Pair, Box>), + Or(Or, Box>), + Lambda(Vec>), + Int(BigInt), + Nat(BigUint), + String(AsciiString), + Bytes(Vec), + Mutez(u64), + Bool(bool), + + Key(), // todo + Signature(), // todo + ChainId(), // todo + Operation(), // todo + Contract(), // todo + Ticket(), // todo + Map(), // todo + BigMap(), // todo + KeyHash(), // todo + Bls12381Fr(), // todo + Bls12381G1(), // todo + Bls12381G2(), // todo + Timestamp(), // todo + Address(), // todo + SaplingState(), // todo + SaplingTransaction(), // todo + Never(), // todo + } +); + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +pub enum Or { + Left(L), + Right(R), +} + +impl Or { + pub fn map U>(self, f: F) -> Or { + use Or::*; + match self { + Left(x) => Left(f(x)), + Right(x) => Right(f(x)), + } + } + + pub fn as_ref(&self) -> Or<&T, &T> { + use Or::*; + match self { + Left(x) => Left(x), + Right(x) => Right(x), + } + } +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +pub struct Pair(pub L, pub R); + +impl Pair { + pub fn map U>(self, f: F) -> Pair { + Pair(f(self.0), f(self.1)) + } + + pub fn as_ref(&self) -> Pair<&T, &T> { + Pair(&self.0, &self.1) + } +} + +impl TValue { + pub fn new_pair(meta: ::Pair, l: Self, r: Self) -> Self { + Self::Pair(meta, Pair(Box::new(l), Box::new(r))) + } + + pub fn new_list(meta: ::List, val: Vec) -> Self { + Self::List(meta, val) + } + + pub fn discriminant(&self) -> u8 { + // https://doc.rust-lang.org/reference/items/enumerations.html#pointer-casting + unsafe { *(self as *const Self as *const u8) } + } +} diff --git a/src/lib_mir/prototype/src/ast/tvalue/comparable.rs b/src/lib_mir/prototype/src/ast/tvalue/comparable.rs new file mode 100644 index 0000000000000000000000000000000000000000..e6e75fd91f260c5ad969e8760abef7296946bb17 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/tvalue/comparable.rs @@ -0,0 +1,177 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use crate::ast::{TValue, Typechecked}; + +#[repr(transparent)] +#[derive(Debug, Clone, Copy, Eq, PartialEq)] +pub struct Comparable(T); + +impl PartialOrd for Comparable<&TValue> { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } +} + +macro_rules! transparent_impl { + (($($ty:tt)*); ($($pre_acc:tt)*)($($acc:tt)*)) => { + impl PartialOrd for Comparable<$($ty)*> { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } + } + + impl Ord for Comparable<$($ty)*> { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + Comparable($($pre_acc)*self.0$($acc)*).cmp(&Comparable($($pre_acc)*other.0$($acc)*)) + } + } + }; +} + +transparent_impl!((TValue); (&) ()); +transparent_impl!((Box>); () (.as_ref())); +transparent_impl!((&Box>); () (.as_ref())); + +impl Ord for Comparable<&TValue> { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + use std::cmp::Ordering::*; + use TValue::*; + macro_rules! cmp_het { + () => { + self.0.discriminant().cmp(&other.0.discriminant()) + }; + } + match (&self.0, &other.0) { + (Address(_), Address(_)) => todo!(), + (Address(..), _) => cmp_het!(), + + (Bool(_, v1), Bool(_, v2)) => v1.cmp(v2), + (Bool(..), _) => cmp_het!(), + + (Bytes(_, v1), Bytes(_, v2)) => v1.cmp(v2), + (Bytes(..), _) => cmp_het!(), + + (ChainId(..), ChainId(..)) => todo!(), + (ChainId(..), _) => cmp_het!(), + + (Int(_, v1), Int(_, v2)) => v1.cmp(v2), + (Int(..), _) => cmp_het!(), + + (Key(..), Key(..)) => todo!(), + (Key(..), _) => cmp_het!(), + + (KeyHash(..), KeyHash(..)) => todo!(), + (KeyHash(..), _) => cmp_het!(), + + (Mutez(_, v1), Mutez(_, v2)) => v1.cmp(v2), + (Mutez(..), _) => cmp_het!(), + + (Nat(_, v1), Nat(_, v2)) => v1.cmp(v2), + (Nat(..), _) => cmp_het!(), + + (Never(..), Never(..)) => Equal, + (Never(..), _) => cmp_het!(), + + (Option(_, v1), Option(_, v2)) => v1 + .as_ref() + .map(Comparable) + .cmp(&v2.as_ref().map(Comparable)), + (Option(..), _) => cmp_het!(), + + (Or(_, v1), Or(_, v2)) => v1 + .as_ref() + .map(Comparable) + .cmp(&v2.as_ref().map(Comparable)), + (Or(..), _) => cmp_het!(), + + (Pair(_, v1), Pair(_, v2)) => v1 + .as_ref() + .map(Comparable) + .cmp(&v2.as_ref().map(Comparable)), + (Pair(..), _) => cmp_het!(), + + (Signature(..), Signature(..)) => todo!(), + (Signature(..), _) => cmp_het!(), + + (String(_, v1), String(_, v2)) => v1.cmp(v2), + (String(..), _) => cmp_het!(), + + (Timestamp(..), Timestamp(..)) => todo!(), + (Timestamp(..), _) => cmp_het!(), + + (Unit(..), Unit(..)) => Equal, + (Unit(..), _) => cmp_het!(), + + // non-comparable + (List(..), _) => unreachable!(), + (Set(..), _) => unreachable!(), + (Operation(..), _) => unreachable!(), + (Contract(..), _) => unreachable!(), + (Ticket(..), _) => unreachable!(), + (Lambda(..), _) => unreachable!(), + (Map(..), _) => unreachable!(), + (BigMap(..), _) => unreachable!(), + (Bls12381Fr(..), _) => unreachable!(), + (Bls12381G1(..), _) => unreachable!(), + (Bls12381G2(..), _) => unreachable!(), + (SaplingState(..), _) => unreachable!(), + (SaplingTransaction(..), _) => unreachable!(), + } + } +} + +#[derive(Debug)] +pub struct ComparableError; + +impl TryFrom> for Comparable> { + type Error = ComparableError; + + fn try_from(value: TValue) -> Result { + if value.is_comparable() { + Ok(Comparable(value)) + } else { + Err(ComparableError) + } + } +} + +impl<'a> TryFrom<&'a TValue> for Comparable<&'a TValue> { + type Error = ComparableError; + + fn try_from(value: &'a TValue) -> Result { + if value.is_comparable() { + Ok(Comparable(value)) + } else { + Err(ComparableError) + } + } +} + +impl From>> for TValue { + fn from(value: Comparable>) -> Self { + value.0 + } +} diff --git a/src/lib_mir/prototype/src/ast/tvalue/typechecked.rs b/src/lib_mir/prototype/src/ast/tvalue/typechecked.rs new file mode 100644 index 0000000000000000000000000000000000000000..79663d0c7edbf50adce55a77751380f76efbe383 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/tvalue/typechecked.rs @@ -0,0 +1,65 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use crate::ast::{ext::typechecked::TValueMeta, tvalue::Pair, TValue, Typechecked}; + +impl TValue { + pub fn is_comparable(&self) -> bool { + use TValue::*; + match self { + Address(..) => true, + Bool(..) => true, + Bytes(..) => true, + ChainId(..) => true, + Int(..) => true, + Key(..) => true, + KeyHash(..) => true, + Mutez(..) => true, + Nat(..) => true, + Never(..) => true, + Signature(..) => true, + String(..) => true, + Timestamp(..) => true, + Unit(..) => true, + Option(meta, ..) => meta.comparable, + Or(meta, ..) => meta.comparable, + Pair(meta, ..) => meta.comparable, + _ => false, + } + } + + pub fn new_pair_tc(l: Self, r: Self) -> Self { + TValue::Pair( + TValueMeta { + comparable: l.is_comparable() && r.is_comparable(), + }, + Pair(Box::new(l), Box::new(r)), + ) + } + + pub fn new_list_tc(elts: Vec) -> Self { + TValue::new_list((), elts) + } +} diff --git a/src/lib_mir/prototype/src/ast/ty.rs b/src/lib_mir/prototype/src/ast/ty.rs new file mode 100644 index 0000000000000000000000000000000000000000..9b3d329aeafd2cd01334b94910eeb75eb63dd668 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/ty.rs @@ -0,0 +1,105 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use num_bigint::BigUint; + +pub mod comparable; +pub mod packable; + +super::macros::ttg_extend!( + @derive(Debug, Clone, PartialEq, Eq) + pub enum Type { + Key(), + Unit(), + Signature(), + ChainId(), + Option(Box), + List(Box), + Set(Box), + Operation(), + Contract(Box), + Ticket(Box), + Pair(Box, Box), + Or(Box, Box), + Lambda(Box, Box), + Map(Box, Box), + BigMap(Box, Box), + Int(), + Nat(), + String(), + Bytes(), + Mutez(), + Bool(), + KeyHash(), + Bls12381Fr(), + Bls12381G1(), + Bls12381G2(), + Timestamp(), + Address(), + SaplingState(BigUint), + SaplingTransaction(BigUint), + Never(), + Ext(), + } +); + +impl Type { + pub fn new_pair(meta: Ext::Pair, l: Self, r: Self) -> Self { + Self::Pair(meta, Box::new(l), Box::new(r)) + } + + pub fn new_or(meta: Ext::Or, l: Self, r: Self) -> Self { + Self::Or(meta, Box::new(l), Box::new(r)) + } + pub fn new_lambda(meta: Ext::Lambda, l: Self, r: Self) -> Self { + Self::Lambda(meta, Box::new(l), Box::new(r)) + } + pub fn new_map(meta: Ext::Map, l: Self, r: Self) -> Self { + Self::Map(meta, Box::new(l), Box::new(r)) + } + pub fn new_big_map(meta: Ext::BigMap, l: Self, r: Self) -> Self { + Self::BigMap(meta, Box::new(l), Box::new(r)) + } + + pub fn new_list(meta: Ext::List, ty: Self) -> Self { + Self::List(meta, Box::new(ty)) + } + + pub fn new_option(meta: Ext::Option, ty: Self) -> Self { + Self::Option(meta, Box::new(ty)) + } + + pub fn new_set(meta: Ext::Set, ty: Self) -> Self { + Self::Set(meta, Box::new(ty)) + } + + pub fn new_ticket(meta: Ext::Ticket, ty: Self) -> Self { + Self::Ticket(meta, Box::new(ty)) + } + + pub fn new_contract(meta: Ext::Contract, ty: Self) -> Self { + Self::Contract(meta, Box::new(ty)) + } +} diff --git a/src/lib_mir/prototype/src/ast/ty/comparable.rs b/src/lib_mir/prototype/src/ast/ty/comparable.rs new file mode 100644 index 0000000000000000000000000000000000000000..089264dc5b7743e75c83f78cd8878cbfbc6e45e9 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/ty/comparable.rs @@ -0,0 +1,52 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use super::{Type, TypeExt}; + +impl Type { + pub fn is_comparable(&self) -> bool { + use Type::*; + match self { + Address(_) => true, + Bool(_) => true, + Bytes(_) => true, + ChainId(_) => true, + Int(_) => true, + Key(_) => true, + KeyHash(_) => true, + Mutez(_) => true, + Nat(_) => true, + Never(_) => true, + Option(_, ty) => ty.is_comparable(), + Or(_, l, r) => l.is_comparable() && r.is_comparable(), + Pair(_, l, r) => l.is_comparable() && r.is_comparable(), + Signature(_) => true, + String(_) => true, + Timestamp(_) => true, + Unit(_) => true, + _ => false, + } + } +} diff --git a/src/lib_mir/prototype/src/ast/ty/packable.rs b/src/lib_mir/prototype/src/ast/ty/packable.rs new file mode 100644 index 0000000000000000000000000000000000000000..c5bc6deddac9c7e03aeab84fe0c397d3040db531 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/ty/packable.rs @@ -0,0 +1,65 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use super::{Type, TypeExt}; + +impl Type { + pub fn is_packable(&self) -> bool { + use Type::*; + match self { + Address(_) => true, + Bls12381Fr(_) => true, + Bls12381G1(_) => true, + Bls12381G2(_) => true, + Bool(_) => true, + Bytes(_) => true, + ChainId(_) => true, + Contract(_, _) => true, + Int(_) => true, + Key(_) => true, + KeyHash(_) => true, + Lambda(_, _, _) => true, + List(_, ty) => ty.is_packable(), + Map(_, _, ty) => ty.is_packable(), + Mutez(_) => true, + Nat(_) => true, + Never(_) => true, + Option(_, ty) => ty.is_packable(), + Or(_, ty1, ty2) => ty1.is_packable() && ty2.is_packable(), + Pair(_, ty1, ty2) => ty1.is_packable() && ty2.is_packable(), + SaplingTransaction(_, _) => true, + Set(_, ty) => ty.is_packable(), + Signature(_) => true, + String(_) => true, + Timestamp(_) => true, + Unit(_) => true, + Operation(..) => false, + Ticket(..) => false, + BigMap(..) => false, + SaplingState(..) => false, + Ext(..) => false, + } + } +} diff --git a/src/lib_mir/prototype/src/ast/uvalue.rs b/src/lib_mir/prototype/src/ast/uvalue.rs new file mode 100644 index 0000000000000000000000000000000000000000..c509d308f2b434b973767d11638d9dc05ff876c6 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/uvalue.rs @@ -0,0 +1,68 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use ascii::AsciiString; +use num_bigint::BigInt; + +use crate::ast::instr::{Instr, InstrExt}; + +super::macros::ttg_extend!( + @derive(Debug, Clone, PartialEq, Eq) + pub enum UValue { + Int(BigInt), + String(AsciiString), + Bytes(Vec), + Unit(), + True(), + False(), + Pair(Box, Box), + Left(Box), + Right(Box), + Some(Box), + None(), + Seq(Vec), + LambdaRec(Vec>), + Instr(Instr), + Ext(), + } +); + +impl UValue { + pub fn new_pair(meta: ::Pair, l: Self, r: Self) -> Self { + Self::Pair(meta, Box::new(l), Box::new(r)) + } + + pub fn new_left(meta: Ext::Left, ty: Self) -> Self { + Self::Left(meta, Box::new(ty)) + } + + pub fn new_right(meta: Ext::Right, ty: Self) -> Self { + Self::Right(meta, Box::new(ty)) + } + + pub fn new_some(meta: Ext::Some, ty: Self) -> Self { + Self::Some(meta, Box::new(ty)) + } +} diff --git a/src/lib_mir/prototype/src/ast/void.rs b/src/lib_mir/prototype/src/ast/void.rs new file mode 100644 index 0000000000000000000000000000000000000000..601f9eea7cd422f9f3bc6c999b00b017df022291 --- /dev/null +++ b/src/lib_mir/prototype/src/ast/void.rs @@ -0,0 +1,33 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +#[derive(Debug, Clone, PartialEq, Eq)] +pub enum Void {} + +impl Void { + pub fn absurd(&self) -> ! { + match *self {} + } +} diff --git a/src/lib_mir/prototype/src/interpreter.rs b/src/lib_mir/prototype/src/interpreter.rs new file mode 100644 index 0000000000000000000000000000000000000000..b69e44a048d4096e0cd96f1aadd9c43e7accd3df --- /dev/null +++ b/src/lib_mir/prototype/src/interpreter.rs @@ -0,0 +1,32 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +pub mod interpret; +mod macros; +pub mod stack; +pub mod typecheck; + +pub use interpret::interpret; +pub use typecheck::{typecheck, typecheck_value}; diff --git a/src/lib_mir/prototype/src/interpreter/interpret.rs b/src/lib_mir/prototype/src/interpreter/interpret.rs new file mode 100644 index 0000000000000000000000000000000000000000..3bf8a16c7310b8e5c69616fc797b93a28f1d4a82 --- /dev/null +++ b/src/lib_mir/prototype/src/interpreter/interpret.rs @@ -0,0 +1,203 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use num_bigint::BigInt; + +use super::stack::Stack; +use crate::ast::{tvalue, Instr, TValue, Typechecked}; + +pub fn interpret( + code: &Vec>, + inp: &mut Stack>, +) -> Result<(), RuntimeError> { + for instr in code { + interpret_one(instr, inp)?; + } + Ok(()) +} + +#[derive(Debug, PartialEq, Eq)] +pub enum RuntimeError { + Failed(TValue), +} + +fn interpret_one( + i: &Instr, + inp: &mut Stack>, +) -> Result<(), RuntimeError> { + use Instr::*; + super::macros::match_instr!(; unreachable!(); i; inp: TValue; + simp Car(_) [1] => { [TValue::Pair(_, tvalue::Pair(l, _))] => [*l] }, + simp Cdr(_) [1] => { [TValue::Pair(_, tvalue::Pair(_, r))] => [*r] }, + simp Pair(_) [2] => { [l, r] => [TValue::new_pair_tc(l, r)] }, + simp Unpair(_) [1] => { [TValue::Pair(_, tvalue::Pair(l, r))] => [*l, *r] }, + simp Push(val) [0] => { [] => [val.clone()] }, + simp Nil(_) [0] => { [] => [TValue::new_list_tc(vec![])] }, + simp Add(func) [2] => { [l, r] => [func(l, r)] }, + simp Mul(func) [2] => { [l, r] => [func(l, r)] }, + simp Int(_) [1] => { [TValue::Nat((), val)] => [TValue::Int((), val.into())] }, + simp Drop(_) [1] => { [_] => [] }, + simp Swap(_) [2] => { [l, r] => [r, l] }, + simp Compare(_) [2] => { + [l, r] => [compare_impl(&l, &r)] + }, + simp Gt(_) [1] => { [TValue::Int(_, val)] => [TValue::Bool((), val > 0.into())] }, + simp Le(_) [1] => { [TValue::Int(_, val)] => [TValue::Bool((), val <= 0.into())] }, + raw DropN(_, n) [*n] => { + inp.drain_top(*n); + }, + raw Dup(_) [1] => { inp.push(inp.top().unwrap().clone()) }, + raw DupN(_, n) [*n] => { + inp.push(inp.get(*n).unwrap().clone()); + }, + raw Dip(_, instrs) [1] => { + inp.protect(1, |inp1| interpret(instrs, inp1)).unwrap()? + }, + raw DipN(_, n, instrs) [*n] => { + inp.protect(*n, |inp1| interpret(instrs, inp1)).unwrap()? + }, + raw PairN(_, n) [*n] => { + let res = inp.drain_top(*n).reduce(|acc, e| TValue::new_pair_tc(e, acc)).unwrap(); + inp.push(res); + }, + raw UnpairN(_, n) [1] => { + let pair = inp.pop().unwrap(); + inp.reserve(*n); + fill_unpair_n(n - 1, inp, pair)?; + }, + raw Dig(_, 0) [0] => { }, // nop + raw Dig(_, n) [*n] => { + let elt = inp.remove(*n); + inp.push(elt); + }, + raw Dug(_, 0) [0] => { }, // nop + raw Dug(_, n) [*n] => { + let elt = inp.pop().unwrap(); + inp.insert(*n, elt); + }, + raw Failwith(_) [1] => { + Err(RuntimeError::Failed(inp.pop().unwrap()))? + }, + raw Never(..) [1] => { + unreachable!(); + }, + simp Unit(..) [0] => { [] => [TValue::Unit(())] }, + raw If(_, b_true, b_false) [1] => { + if let TValue::Bool(_, b) = inp.pop().unwrap() { + if b { + interpret(b_true, inp)?; + } else { + interpret(b_false, inp)?; + } + } else { + unreachable!(); + } + }, + raw Nest(_, content) [0] => { + interpret(content, inp)?; + }, + raw Loop(_, body) [1] => { + while let Some(TValue::Bool(_, true)) = inp.pop() { + interpret(body, inp)?; + } + } + ); + Ok(()) +} + +fn compare_impl(one: &TValue, other: &TValue) -> TValue { + use std::cmp::Ordering::*; + use tvalue::Comparable; + let cmp_one = Comparable::try_from(one).expect(&format!("{:?} is comparable", one)); + let cmp_other = other + .try_into() + .expect(&format!("{:?} is comparable", other)); + match cmp_one.cmp(&cmp_other) { + Equal => TValue::Int((), 0.into()), + Less => TValue::Int((), (-1).into()), + Greater => TValue::Int((), 1.into()), + } +} + +fn fill_unpair_n( + n: usize, + inp: &mut Stack>, + pair: TValue, +) -> Result<(), RuntimeError> { + if n == 0 { + inp.push(pair); + } else if let TValue::Pair(_, tvalue::Pair(el, rest)) = pair { + fill_unpair_n(n - 1, inp, *rest)?; + inp.push(*el); + } else { + unreachable!(); + } + Ok(()) +} + +macro_rules! unsafe_match { + ($pat:pat = $expr:expr => $($rest:tt)*) => { + if let $pat = $expr { + $($rest)* + } else { + unreachable!(); + } + } +} + +pub mod add { + use super::{BigInt, TValue, Typechecked}; + use TValue::*; + + pub fn int_int(a: TValue, b: TValue) -> TValue { + unsafe_match!((Int(_, av), Int(_, bv)) = (a, b) => Int((), av + bv)) + } + pub fn nat_int(a: TValue, b: TValue) -> TValue { + unsafe_match!((Nat(_, av), Int(_, bv)) = (a, b) => Int((), BigInt::from(av) + bv)) + } + pub fn int_nat(a: TValue, b: TValue) -> TValue { + unsafe_match!((Int(_, av), Nat(_, bv)) = (a, b) => Int((), av + BigInt::from(bv))) + } + pub fn nat_nat(a: TValue, b: TValue) -> TValue { + unsafe_match!((Nat(_, av), Nat(_, bv)) = (a, b) => Nat((), av + bv)) + } +} +pub mod mul { + use super::{BigInt, TValue, Typechecked}; + use TValue::*; + + pub fn int_int(a: TValue, b: TValue) -> TValue { + unsafe_match!((Int(_, av), Int(_, bv)) = (a, b) => Int((), av * bv)) + } + pub fn nat_int(a: TValue, b: TValue) -> TValue { + unsafe_match!((Nat(_, av), Int(_, bv)) = (a, b) => Int((), BigInt::from(av) * bv)) + } + pub fn int_nat(a: TValue, b: TValue) -> TValue { + unsafe_match!((Int(_, av), Nat(_, bv)) = (a, b) => Int((), av * BigInt::from(bv))) + } + pub fn nat_nat(a: TValue, b: TValue) -> TValue { + unsafe_match!((Nat(_, av), Nat(_, bv)) = (a, b) => Nat((), av * bv)) + } +} diff --git a/src/lib_mir/prototype/src/interpreter/macros.rs b/src/lib_mir/prototype/src/interpreter/macros.rs new file mode 100644 index 0000000000000000000000000000000000000000..1c0f1ec4763c5b8c45cd41937b28a1553c9a5e52 --- /dev/null +++ b/src/lib_mir/prototype/src/interpreter/macros.rs @@ -0,0 +1,113 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +macro_rules! match_instr { + + (@simp_body $id:ident; $args:tt; $inp:expr; copy; $tail:tt) => { + { + let res = $id$args; + $crate::interpreter::macros::match_instr!(@simp_body_cont $inp; $tail; res) + } + }; + (@simp_body $id:ident; $args:tt; $inp:expr; $attr:tt; $tail:tt) => { + { + let res = $id$attr; + $crate::interpreter::macros::match_instr!(@simp_body_cont $inp; $tail; res) + } + }; + (@simp_body $id:ident; $args:tt; $inp:expr ; $tail:block) => { + { + let (res, arr) = $tail; + $crate::interpreter::macros::match_instr!(@simp_body_cont $inp; arr; res); + } + }; + (@simp_body $id:ident; $args:tt; $inp:expr ; $tail:tt) => { + { + $crate::interpreter::macros::match_instr!(@simp_body_cont $inp; $tail;); + } + }; + (@simp_body_cont $inp:expr; [!]; $($res:expr)?) => { + { + $inp.fail(); + $(Ok($res))? + } + }; + (@simp_body_cont $inp:expr; $new_stk:expr; $($res:expr)?) => { + { + let it = $new_stk.into_iter().rev(); + $inp.extend(it); + $(Ok($res))? + } + }; + (@helper { $no_overload:expr; $item_ty:ty; $inp:expr; $sz:literal } + simp $id:ident $args:tt => { $( $stk:pat $(if $cond:expr)? => + $tail1:tt $([$($tail2:tt)*])? ),* $(,)* + } + ) => { + { + use $crate::interpreter::macros::match_instr; + let bx: [$item_ty; $sz] = seq_macro::seq!(N in 0..$sz { [ #($inp.pop().unwrap(),)* ] }); + #[allow(unreachable_patterns)] + match bx { + $( + $stk $(if $cond)? => + match_instr!(@simp_body $id; $args; $inp; $tail1 $(; [$($tail2)*])?), + )* + _ => $no_overload, + } + } + }; + (@helper {$($_:tt)*} raw $id:ident $args:tt => ($($attr:expr),* $(,)*) ; $blk:block) => { + { $blk; Ok($id($($attr),*)) } + }; + (@helper {$($_:tt)*} raw $id:ident $args:tt => copy ; $blk:block) => { + { $blk; Ok($id$args) } + }; + (@helper {$($_:tt)*} raw $id:ident $args:tt => $blk:block) => { $blk }; + (@one_instr $no_stk_err:expr; $no_overload:expr; $i:ident; $inp:ident: $item_ty:ty; $($kind:ident $id:ident $args:tt [$sz:expr] $(if $cond:expr)? => $($blk:tt);*),* $(,)*) => { + match $i { + $( + $id$args $(if $cond)? => { + use $crate::interpreter::macros::match_instr; + if $sz as usize > $inp.len() { + $no_stk_err; + } + match_instr!(@helper {$no_overload; $item_ty; $inp; $sz} $kind $id $args => $($blk);*) + } + ),* + } + }; + (; $($defn:tt)*) => { + $crate::interpreter::macros::match_instr!(@one_instr {}; $($defn)*) + }; + ($no_stk_err:expr; $($defn:tt)*) => { + $crate::interpreter::macros::match_instr!(@one_instr + return Err($no_stk_err); + $($defn)* + ) + }; +} + +pub(super) use match_instr; diff --git a/src/lib_mir/prototype/src/interpreter/stack.rs b/src/lib_mir/prototype/src/interpreter/stack.rs new file mode 100644 index 0000000000000000000000000000000000000000..47e6e8612fd806e7da070898aa5bf9909a5fdd71 --- /dev/null +++ b/src/lib_mir/prototype/src/interpreter/stack.rs @@ -0,0 +1,243 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use std::vec::Drain; + +macro_rules! stk { + (;; $acc:tt) => { + crate::interpreter::stack::Stack::new(vec!$acc) + }; + ($e:expr $(, $es:expr)* $(,)* ;; [ $($acc:expr),* ]) => { + crate::interpreter::stack::stk!($($es),* ;; [$e $(, $acc)*]) + }; + ($($es:expr),* $(,)*) => { + crate::interpreter::stack::stk!($($es),* ;; []) + }; + ($e:expr; $n:literal) => { + crate::interpreter::stack::Stack::new(vec![$e; $n]) + }; +} + +pub(crate) use stk; + +#[cfg(test)] +pub mod test { + #[test] + fn test() { + assert!(stk![1, 2, 3, 4, 5].access() == &vec![5, 4, 3, 2, 1]) + } +} + +#[derive(Debug)] +pub struct Stack { + data: Vec, + failed: bool, +} + +#[inline] +fn guard(cond: bool, res: R) -> Option { + if cond { + Some(res) + } else { + None + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct FailedStackAccess; + +impl Stack { + #[inline] + pub fn new(data: Vec) -> Stack { + Stack::from(data) + } + + #[inline] + pub fn is_ok(&self) -> bool { + !self.failed + } + + #[inline] + pub fn is_failed(&self) -> bool { + self.failed + } + + #[inline] + pub fn fail(&mut self) { + self.failed = true; + } + + #[inline] + pub fn access(&self) -> &Vec { + debug_assert!(self.is_ok()); + &self.data + } + + #[inline] + pub fn access_val(self) -> Vec { + debug_assert!(self.is_ok()); + self.data + } + + #[inline] + pub fn access_mut(&mut self) -> &mut Vec { + debug_assert!(self.is_ok()); + &mut self.data + } + + #[inline] + pub fn try_access(&self) -> Option<&Vec> { + guard(self.is_ok(), &self.data) + } + + #[inline] + pub fn try_access_val(self) -> Option> { + guard(self.is_ok(), self.data) + } + + #[inline] + pub fn try_access_mut(&mut self) -> Option<&mut Vec> { + guard(self.is_ok(), &mut self.data) + } + + #[inline] + pub fn push(&mut self, elt: T) { + self.access_mut().push(elt) + } + + #[inline] + pub fn pop(&mut self) -> Option { + self.access_mut().pop() + } + + #[inline] + pub fn get(&self, depth: usize) -> Option<&T> { + self.access().get(self.len() - depth) + } + + #[inline] + pub fn get_mut(&mut self, depth: usize) -> Option<&mut T> { + let len = self.len(); + self.access_mut().get_mut(len - depth) + } + + #[inline] + pub fn len(&self) -> usize { + self.access().len() + } + + #[inline] + pub fn drain_top(&mut self, size: usize) -> Drain<'_, T> { + let len = self.len(); + self.access_mut().drain(len - size..) + } + + pub fn protect R>(&mut self, depth: usize, f: F) -> Option { + debug_assert!(depth < self.len()); + if depth == 1 { + // small optimization that avoids unnecessary allocations + let protected = self.pop().unwrap(); + let res = f(self); + self.try_access_mut()?.push(protected); + Some(res) + } else { + let len = self.len(); + let mut protected = self.access_mut().split_off(len - depth); + let res = f(self); + self.try_access_mut()?.append(&mut protected); + Some(res) + } + } + + #[inline] + pub fn reserve(&mut self, n: usize) { + self.access_mut().reserve(n) + } + + #[inline] + pub fn remove(&mut self, i: usize) -> T { + let len = self.len(); + self.access_mut().remove(len - i - 1) + } + + #[inline] + pub fn insert(&mut self, i: usize, elt: T) { + let len = self.len(); + self.access_mut().insert(len - i, elt) + } + + #[inline] + pub fn top(&self) -> Option<&T> { + self.access().last() + } + + #[inline] + pub fn top_mut(&mut self) -> Option<&mut T> { + self.access_mut().last_mut() + } +} + +impl Extend for Stack { + #[inline] + fn extend>(&mut self, iter: I) { + self.access_mut().extend(iter) + } +} + +impl Clone for Stack { + #[inline] + fn clone(&self) -> Self { + Stack { + data: self.data.clone(), + failed: self.failed, + } + } +} + +impl From> for Stack { + #[inline] + fn from(data: Vec) -> Self { + Stack { + data, + failed: false, + } + } +} + +impl TryFrom> for Vec { + type Error = FailedStackAccess; + + #[inline] + fn try_from(value: Stack) -> Result { + value.try_access_val().ok_or(FailedStackAccess) + } +} + +impl PartialEq for Stack { + #[inline] + fn eq(&self, other: &Self) -> bool { + self.failed == other.failed && self.data == other.data + } +} diff --git a/src/lib_mir/prototype/src/interpreter/typecheck.rs b/src/lib_mir/prototype/src/interpreter/typecheck.rs new file mode 100644 index 0000000000000000000000000000000000000000..41309f8ea128b2faddf39fa73789e741986d6df9 --- /dev/null +++ b/src/lib_mir/prototype/src/interpreter/typecheck.rs @@ -0,0 +1,341 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +use num_bigint::BigInt; +use num_bigint::TryFromBigIntError; + +use super::stack::{stk, Stack}; +use crate::ast::tvalue::comparable::ComparableError; +use crate::ast::{ + ext::typechecked::TValueMeta, tvalue, tvalue::Or, Instr, InstrExt, Parsed, TValue, Type, + Typechecked, UValue, UValueExt, +}; +use crate::interpreter::interpret::{add, mul}; + +pub fn typecheck( + code: Vec>, + inp: &mut Stack>, +) -> Result>, TcError> { + code.into_iter() + .map(|instr| typecheck_one(instr, inp)) + .collect() +} + +#[derive(Debug, PartialEq, Eq)] +pub enum TcError { + NotEnoughItemsOnStack, + NoMatchingOverload, + BadInstr(BadInstr), + ValueError, + DeadCode, + TypeMismatch, +} + +#[derive(Debug, PartialEq, Eq)] +pub enum BadInstr { + Dup0, + Pair0, + Pair1, + Unpair0, + Unpair1, +} + +fn typecheck_one( + i: Instr, + inp: &mut Stack>, +) -> Result, TcError> { + use Instr::*; + if inp.is_failed() { + Err(TcError::DeadCode)? + } + super::macros::match_instr!(TcError::NotEnoughItemsOnStack; Err(TcError::NoMatchingOverload); i; + inp: Type; + simp Car(meta) [1] => { [Type::Pair((), l, _)] => copy [*l] }, + simp Cdr(meta) [1] => { [Type::Pair((), _, r)] => copy [*r] }, + simp Pair(meta) [2] => { [l, r] => copy [Type::new_pair((), l, r)] }, + simp Unpair(meta) [1] => { [Type::Pair(_, l, r)] => copy [*l, *r] }, + simp Push((ty, val)) [0] => { [] => (typecheck_value(*val, &ty)?) [ty] }, + simp Nil(ty) [0] => { [] => (()) [Type::new_list((), ty)] }, + simp Add(_) [2] => { + [Type::Int(_), Type::Int(_)] => (add::int_int as _) [Type::Int(())], + [Type::Nat(_), Type::Int(_)] => (add::nat_int as _) [Type::Int(())], + [Type::Int(_), Type::Nat(_)] => (add::int_nat as _) [Type::Int(())], + [Type::Nat(_), Type::Nat(_)] => (add::nat_nat as _) [Type::Nat(())], + }, + simp Mul(_) [2] => { + [Type::Int(_), Type::Int(_)] => (mul::int_int as _) [Type::Int(())], + [Type::Nat(_), Type::Int(_)] => (mul::nat_int as _) [Type::Int(())], + [Type::Int(_), Type::Nat(_)] => (mul::int_nat as _) [Type::Int(())], + [Type::Nat(_), Type::Nat(_)] => (mul::nat_nat as _) [Type::Nat(())], + }, + simp Int(meta) [1] => { [Type::Nat(())] => copy [Type::Int(())] }, + simp Drop(meta) [1] => { [_] => copy [] }, + simp Swap(meta) [2] => { [l, r] => copy [r, l] }, + simp Compare(meta) [2] => { + [l, r] if l == r && l.is_comparable() => copy [Type::Int(())] + }, + simp Gt(meta) [1] => { [Type::Int(..)] => copy [Type::Bool(())] }, + simp Le(meta) [1] => { [Type::Int(..)] => copy [Type::Bool(())] }, + raw DropN(meta, n) [n] => copy; { + inp.drain_top(n); + }, + raw Dup(meta) [1] => copy; { inp.push(inp.top().unwrap().clone()) }, + raw DupN(_, 0) [0] => { Err(TcError::BadInstr(BadInstr::Dup0)) }, + raw DupN(meta, n) [n] => copy; { + inp.push(inp.get(n).unwrap().clone()); + }, + raw Dip(meta, instrs) [1] => { + let tc_instrs = inp.protect(1, |inp1| typecheck(instrs, inp1)).ok_or(TcError::DeadCode)??; + Ok(Dip(meta, tc_instrs)) + }, + raw DipN(meta, n, instrs) [n] => { + let tc_instrs = inp.protect(n, |inp1| typecheck(instrs, inp1)).ok_or(TcError::DeadCode)??; + Ok(DipN(meta, n, tc_instrs)) + }, + raw PairN(_, 0) [0] => { Err(TcError::BadInstr(BadInstr::Pair0)) }, + raw PairN(_, 1) [0] => { Err(TcError::BadInstr(BadInstr::Pair1)) }, + raw PairN(meta, n) [n] => copy; { + let res = inp.drain_top(n).reduce(|acc, e| Type::new_pair((), e, acc)).unwrap(); + inp.push(res); + }, + raw UnpairN(_, 0) [0] => { Err(TcError::BadInstr(BadInstr::Unpair0)) }, + raw UnpairN(_, 1) [0] => { Err(TcError::BadInstr(BadInstr::Unpair1)) }, + raw UnpairN(meta, n) [1] => copy; { + let pair = inp.pop().unwrap(); + inp.reserve(n); + fill_unpair_n(n - 1, inp, pair)?; + }, + raw Dig(meta, 0) [0] => copy; { }, // nop + raw Dig(meta, n) [n] => copy; { + let elt = inp.remove(n); + inp.push(elt); + }, + raw Dug(meta, 0) [0] => copy; { }, // nop + raw Dug(meta, n) [n] => copy; { + let elt = inp.pop().unwrap(); + inp.insert(n, elt); + }, + simp Failwith(meta) [1] => { [v] if v.is_packable() => copy [!] }, + simp Never(meta) [1] => { [Type::Never(..)] => copy [!] }, + simp Unit(meta) [0] => { [] => copy [Type::Unit(())] }, + raw If(meta, b_true, b_false) [1] => { + let cond = inp.pop().unwrap(); + match cond { + Type::Bool(_) => (), + _ => Err(TcError::NoMatchingOverload)?, + } + let mut inp_copy = inp.clone(); + let b_true_tc = typecheck(b_true, &mut inp_copy)?; + let b_false_tc = typecheck(b_false, inp)?; + if inp.is_ok() && inp_copy.is_ok() && inp != &inp_copy { + Err(TcError::TypeMismatch)?; + } + Ok(If(meta, b_true_tc, b_false_tc)) + }, + raw Nest(meta, content) [0] => { + Ok(Nest(meta, typecheck(content, inp)?)) + }, + raw Loop(meta, body) [1] => { + // this may look strange, but typing rules are as thus: + // instr :: A => bool : A + // --------------------------- + // LOOP instr :: bool : A => A + // Notice output stack of instr is the input stack of LOOP instr. + // Hence we save the input stack to compare against later. + let inp_copy = inp.clone(); + let b = inp.pop().unwrap(); + match b { + Type::Bool(..) => (), + _ => Err(TcError::NoMatchingOverload)?, + }; + let body_tc = typecheck(body, inp)?; + if &inp_copy != inp { + Err(TcError::TypeMismatch)?; + } + inp.pop(); // pops the bool left on the stack after typechecking body + Ok(Loop(meta, body_tc)) + } + ) +} + +fn fill_unpair_n( + n: usize, + inp: &mut Stack>, + pair: Type, +) -> Result<(), TcError> { + if n == 0 { + inp.push(pair); + } else if let Type::Pair(_, el, rest) = pair { + fill_unpair_n(n - 1, inp, *rest)?; + inp.push(*el); + } else { + Err(TcError::NoMatchingOverload)?; + } + Ok(()) +} + +macro_rules! tc_val { + (rec2; $tyname:ident; $res:block) => { $res }; + (rec2; $tyname:ident; $res:tt) => { TValue::$tyname$res }; + (rec1; $val:expr; $tyname:ident; raw $($rest:tt)*) => { + $($rest)* + }; + (rec1; $val:expr; $tyname:ident; $($vname:ident $vargs:tt $(if $cond:expr)? => $res:tt ),* $(,)*) => { + match $val { + $(UValue::$vname $vargs $(if $cond)? => tc_val!(rec2; $tyname; $res) ,)* + _ => Err(TcError::ValueError)?, + } + }; + ($ty:expr; $val:expr; $( $tyname:ident $tyargs:tt => { $($body:tt)* } ),* $(,)* ) => { + match $ty { + $( Type::$tyname $tyargs => tc_val!(rec1; $val; $tyname; $($body)*) ),* + } + }; +} + +impl From> for TcError { + fn from(_: TryFromBigIntError) -> Self { + TcError::ValueError + } +} + +impl From for TcError { + fn from(_: ComparableError) -> Self { + TcError::ValueError + } +} + +fn meta(comparable: bool) -> TValueMeta { + TValueMeta { comparable } +} + +pub fn typecheck_value( + val: UValue, + ty: &Type, +) -> Result, TcError> { + let res = tc_val!(ty; val; + Ext(meta) => { raw meta.absurd() }, + Never(..) => { raw Err(TcError::ValueError)? }, + Int(..) => { Int(_, val) => ((), val) }, + Nat(..) => { Int(_, val) => ((), val.try_into()?) }, + Unit(..) => { Unit(..) => (()) }, + Option(_, ty) => { + Some(_, val) => { + let val_ = typecheck_value(*val, ty)?; + TValue::Option(meta(val_.is_comparable()), Some(Box::new(val_))) + }, + None(..) => (TValueMeta{comparable: ty.is_comparable()}, None), + }, + Pair(_, tl, tr) => { + Pair(_, l, r) => { + let tcl = typecheck_value(*l, tl)?; + let tcr = typecheck_value(*r, tr)?; + let meta = meta(tcl.is_comparable() && tcr.is_comparable()); + TValue::new_pair(meta, tcl, tcr) + }, + }, + Or(_, tl, tr) => { + Left(_, v) => { + let tcl = typecheck_value(*v, tl)?; + let cmp = tr.is_comparable() && tcl.is_comparable(); + TValue::Or(meta(cmp), Or::Left(Box::new(tcl))) + }, + Right(_, v) => { + let tcr = typecheck_value(*v, tr)?; + let cmp = tl.is_comparable() && tcr.is_comparable(); + TValue::Or(meta(cmp), Or::Right(Box::new(tcr))) + }, + }, + String(..) => { String(_, v) => ((), v) }, + Bytes(..) => { Bytes(_, v) => ((), v) }, + Mutez(..) => { Int(_, v) => ((), v.try_into()?) }, + Bool(..) => { + True(..) => ((), true), + False(..) => ((), false), + }, + List(_, ty) => { + Seq(_, elts) => { + let res = elts + .into_iter() + .map(|elt| typecheck_value(elt, ty)) + .collect::>()?; + TValue::List((), res) + } + }, + Set(_, ty) => { + Seq(_, elts) => { + let res = elts + .into_iter() + .map(|elt| Ok(tvalue::Comparable::try_from(typecheck_value(elt, ty)?)?) ) + .collect::>()?; + TValue::Set((), res) + } + }, + Lambda(_, arg, res) => { + Seq(_, elts) => { + let mut tystk = stk![arg.as_ref().clone()]; + let tc_body = typecheck(to_instr_seq(elts)?, &mut tystk)?; + if !tystk.is_failed() && (tystk.len() != 1 || tystk.top().unwrap() != &**res) { + Err(TcError::ValueError)?; + } + TValue::Lambda((), tc_body) + }, + LambdaRec(..) => { todo!() }, + }, + // todo + Key(..) => { raw todo!() }, + Signature(..) => { raw todo!() }, + ChainId(..) => { raw todo!() }, + Operation(..) => { raw todo!() }, + Contract(..) => { raw todo!() }, + Ticket(..) => { raw todo!() }, + Map(..) => { raw todo!() }, + BigMap(..) => { raw todo!() }, + KeyHash(..) => { raw todo!() }, + Bls12381Fr(..) => { raw todo!() }, + Bls12381G1(..) => { raw todo!() }, + Bls12381G2(..) => { raw todo!() }, + Timestamp(..) => { raw todo!() }, + Address(..) => { raw todo!() }, + SaplingState(..) => { raw todo!() }, + SaplingTransaction(..) => { raw todo!() }, + ); + Ok(res) +} + +fn to_instr_seq( + elts: Vec>, +) -> Result>, TcError> +where + Ext::Nest: Default, +{ + elts.into_iter() + .map(|elt| match elt { + UValue::Instr(_, i) => Ok(i), + UValue::Seq(_, els) => Ok(Instr::Nest(Ext::Nest::default(), to_instr_seq(els)?)), + _ => Err(TcError::ValueError), + }) + .collect() +} diff --git a/src/lib_mir/prototype/src/main.rs b/src/lib_mir/prototype/src/main.rs new file mode 100644 index 0000000000000000000000000000000000000000..02baba16d5dffad9c9c457b4c399ebcccf998489 --- /dev/null +++ b/src/lib_mir/prototype/src/main.rs @@ -0,0 +1,72 @@ +/******************************************************************************/ +/* */ +/* MIT License */ +/* Copyright (c) 2023 Serokell */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a */ +/* copy of this software and associated documentation files (the "Software"), */ +/* to deal in the Software without restriction, including without limitation */ +/* the rights to use, copy, modify, merge, publish, distribute, sublicense, */ +/* and/or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included */ +/* in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR */ +/* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, */ +/* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL */ +/* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER */ +/* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ +/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER */ +/* DEALINGS IN THE SOFTWARE. */ +/* */ +/******************************************************************************/ + +mod ast; +mod interpreter; +use interpreter::{interpret, stack::stk, typecheck, typecheck_value}; + +use lalrpop_util::lalrpop_mod; + +lalrpop_mod!(pub syntax); + +fn main() -> Result<(), typecheck::TcError> { + let args: Vec<_> = std::env::args().collect(); + if args.len() != 3 { + println!("Usage: {} ", args[0]); + println!("Code is accepted at standard input"); + return Ok(()); + } + let stdin: String = std::io::stdin().lines().flatten().collect(); + + let parse_time = std::time::Instant::now(); + let code = syntax::InstrSeqParser::new().parse(&stdin).unwrap(); + let vty = syntax::NakedTypeParser::new().parse(&args[1]).unwrap(); + let val = syntax::NakedValueParser::new().parse(&args[2]).unwrap(); + dbg!(parse_time.elapsed()); + + let mut ty_stk = stk![vty.clone()]; + + let tc_time = std::time::Instant::now(); + let tc_code = typecheck(code, &mut ty_stk)?; + dbg!(tc_time.elapsed()); + + dbg!(ty_stk); + + let tc_val_time = std::time::Instant::now(); + let tc_val = typecheck_value(val, &vty)?; + dbg!(tc_val_time.elapsed()); + + let mut stk = stk![tc_val]; + let int_time = std::time::Instant::now(); + let int_res = interpret::interpret(&tc_code, &mut stk); + dbg!(int_time.elapsed()); + + #[allow(unused_must_use)] + { + dbg!(int_res); + } + dbg!(stk); + Ok(()) +} diff --git a/src/lib_mir/prototype/src/syntax.lalrpop b/src/lib_mir/prototype/src/syntax.lalrpop new file mode 100644 index 0000000000000000000000000000000000000000..f7e811406919e6759ab7e70ae295f1036af95c5a --- /dev/null +++ b/src/lib_mir/prototype/src/syntax.lalrpop @@ -0,0 +1,195 @@ +//****************************************************************************// +// // +// MIT License // +// Copyright (c) 2023 Serokell // +// // +// Permission is hereby granted, free of charge, to any person obtaining a // +// copy of this software and associated documentation files (the "Software"), // +// to deal in the Software without restriction, including without limitation // +// the rights to use, copy, modify, merge, publish, distribute, sublicense, // +// and/or sell copies of the Software, and to permit persons to whom the // +// Software is furnished to do so, subject to the following conditions: // +// // +// The above copyright notice and this permission notice shall be included // +// in all copies or substantial portions of the Software. // +// // +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL // +// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER // +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING // +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER // +// DEALINGS IN THE SOFTWARE. // +// // +//****************************************************************************// + +use ascii::AsciiString; +use num_bigint::{BigInt, BigUint, Sign}; +use std::str::FromStr; + +use crate::ast::{Parsed, Type, Instr, UValue}; + +grammar; + +match { + r"(?-u:\s)+" => {}, // more or less same as default, but required to build w/o unicode + _ +} + +pub NakedValue: UValue = { + PrimValue => <>, + CompValue => <>, + "(" ")" => <>, +} + +pub ParValue: UValue = { + PrimValue => <>, + "(" ")" => <>, + "(" ")" => <>, +} + +pub CompValue: UValue = { + r"Pair" => UValue::new_pair((), <>), + r"Left" => UValue::new_left((), <>), + r"Right" => UValue::new_right((), <>), + r"Some" => UValue::new_some((), <>), + Instr => UValue::Instr((), <>), +} + +pub PairValArgs: UValue = { + ParValue => <>, + => UValue::new_pair((), <>), +} + +pub PrimValue: UValue = { + Int => UValue::Int((), <>), + r#""[^"]*""# => UValue::String((), AsciiString::from_str(&<>[1..<>.len()-1]).unwrap()), + r"0x([0-9a-fA-F]{2})*" => UValue::Bytes((), hex::decode(&(<>[2..])).unwrap()), + r"Unit" => UValue::Unit(()), + r"True" => UValue::True(()), + r"False" => UValue::False(()), + r"None" => UValue::None(()), + "{" "}" => UValue::Seq((), <>), +} + +pub SeqValue = Seq; + +pub PrimType: Type = { + r"key" => Type::Key(()), + r"unit" => Type::Unit(()), + r"signature" => Type::Signature(()), + r"chain_id" => Type::ChainId(()), + r"operation" => Type::Operation(()), + r"int" => Type::Int(()), + r"nat" => Type::Nat(()), + r"string" => Type::String(()), + r"bytes" => Type::Bytes(()), + r"mutez" => Type::Mutez(()), + r"bool" => Type::Bool(()), + r"key_hash" => Type::KeyHash(()), + r"bls_12381_fr" => Type::Bls12381Fr(()), + r"bls_12381_g1" => Type::Bls12381G1(()), + r"bls_12381_g2" => Type::Bls12381G2(()), + r"timestamp" => Type::Timestamp(()), + r"address" => Type::Address(()), + r"sapling_state" => Type::SaplingState((), <>), + r"sapling_transaction" => Type::SaplingTransaction((), <>), + r"never" => Type::Never(()), +} + +pub CompType: Type = { + r"option" => Type::new_option((), <>), + r"list" => Type::new_list((), <>), + r"set" => Type::new_set((), <>), + r"contract" => Type::new_contract((), <>), + r"ticket" => Type::new_ticket((), <>), + r"pair" => Type::new_pair((), <>), + r"or" => Type::new_or((), <>), + r"lambda" => Type::new_lambda((), <>), + r"map" => Type::new_map((), <>), + r"big_map" => Type::new_big_map((), <>), +} + +pub PairArgs: Type = { + ParType => <>, + => Type::new_pair((), <>) +} + +pub ParType: Type = { + PrimType => <>, + "(" ")" => <>, + "(" ")" => <>, +} + +pub NakedType: Type = { + PrimType => <>, + CompType => <>, + "(" ")" => <>, +} + +pub UInt: BigUint = { + r"[0-9]+" => BigUint::from_str(<>).unwrap(), +} + +pub Int: BigInt = { + => BigInt::from_biguint(<>), +} + +pub Sign: Sign = { + "+" => Sign::Plus, + "-" => Sign::Minus, + => Sign::Plus, +} + +pub InstrSeq = Seq; + +pub InstrNest: Instr = { + Instr => <>, + "{" "}" => Instr::Nest((), <>) +} + +pub Instr: Instr = { + "CAR" => Instr::Car(()), + "CDR" => Instr::Cdr(()), + "PAIR" => Instr::Pair(()), + "PUSH" + => Instr::Push((ty, Box::new(v))), + "NIL" => Instr::Nil(<>), + "ADD" => Instr::Add(()), + "DUP" => Instr::Dup(()), + "DUP" => Instr::DupN((), <>), + "DROP" => Instr::Drop(()), + "DROP" => Instr::DropN((), <>), + "DIP" => Instr::Dip((), <>), + "DIP" => Instr::DipN((), <>), + "SWAP" => Instr::Swap(()), + "COMPARE" => Instr::Compare(()), + "PAIR" => Instr::PairN((), <>), + "UNPAIR" => Instr::Unpair(()), + "UNPAIR" => Instr::UnpairN((), <>), + "DIG" => Instr::Dig((), <>), + "DUG" => Instr::Dug((), <>), + "FAILWITH" => Instr::Failwith(()), + "NEVER" => Instr::Never(()), + "IF" => Instr::If((), <>), + "UNIT" => Instr::Unit(()), + "LOOP" => Instr::Loop((), <>), + "GT" => Instr::Gt(()), + "LE" => Instr::Le(()), + "INT" => Instr::Int(()), + "MUL" => Instr::Mul(()), +} + +BIS = "{" "}"; + +pub USize: usize = { UInt => <>.try_into().unwrap() } + +Seq: Vec = { + ";")*> => match e { + None => v, + Some(e) => { + v.push(e); + v + } + } +}; diff --git a/src/lib_mir/test/fixtures/factorial.tzt b/src/lib_mir/test/fixtures/factorial.tzt new file mode 100644 index 0000000000000000000000000000000000000000..2f1f604d3fdebfb11b8e00940f07200dd2882d0d --- /dev/null +++ b/src/lib_mir/test/fixtures/factorial.tzt @@ -0,0 +1,32 @@ +############################################################################## +# +# MIT License +# Copyright (c) 2023 Serokell +# +# Permission is hereby granted, free of charge, to any person obtaining a +# copy of this software and associated documentation files (the "Software"), +# to deal in the Software without restriction, including without limitation +# the rights to use, copy, modify, merge, publish, distribute, sublicense, +# and/or sell copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following conditions: +# +# The above copyright notice and this permission notice shall be included +# in all copies or substantial portions of the Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +# DEALINGS IN THE SOFTWARE. +# +############################################################################## + +code { INT; DUP; LE; + IF { DROP; PUSH int 1 } + { DUP; PUSH int -1; ADD; DUP; GT; + LOOP { DUP; DIP { MUL }; PUSH int -1; ADD; DUP; GT } ; + DROP } }; +input { Stack_elt nat 30 } ; +output { Stack_elt int 265252859812191058636308480000000 } ; diff --git a/src/lib_mir/test/fixtures/fibonacci.tzt b/src/lib_mir/test/fixtures/fibonacci.tzt new file mode 100644 index 0000000000000000000000000000000000000000..e9e4a44cfeae94327aeb511fc0572b2a1743f539 --- /dev/null +++ b/src/lib_mir/test/fixtures/fibonacci.tzt @@ -0,0 +1,35 @@ +############################################################################## +# +# MIT License +# Copyright (c) 2023 Serokell +# +# Permission is hereby granted, free of charge, to any person obtaining a +# copy of this software and associated documentation files (the "Software"), +# to deal in the Software without restriction, including without limitation +# the rights to use, copy, modify, merge, publish, distribute, sublicense, +# and/or sell copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following conditions: +# +# The above copyright notice and this permission notice shall be included +# in all copies or substantial portions of the Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +# DEALINGS IN THE SOFTWARE. +# +############################################################################## + +code { INT ; PUSH int 0 ; DUP 2 ; GT ; + IF { DIP { PUSH int -1 ; ADD } ; + PUSH int 1 ; + DUP 3 ; + GT ; + LOOP { SWAP ; DUP 2 ; ADD ; DIP 2 { PUSH int -1 ; ADD } ; DUP 3 ; GT } ; + DIP { DROP 2 } } + { DIP { DROP } } } ; +input { Stack_elt nat 100 } ; +output { Stack_elt int 354224848179261915075 } ;