From a4635fb95235ba4bf077bd59957da0626fc5ba72 Mon Sep 17 00:00:00 2001 From: Benjamin Barenblat Date: Tue, 14 Dec 2021 12:34:06 -0500 Subject: EC, a terminal-based RPN calculator --- .gitignore | 26 ++++ .gitmodules | 4 + LICENSE | 202 ++++++++++++++++++++++++ README.md | 44 ++++++ build.ninja | 1 + buildconf/asan.ninja | 20 +++ buildconf/common.ninja | 389 ++++++++++++++++++++++++++++++++++++++++++++++ buildconf/dbg.ninja | 18 +++ buildconf/fastbuild.ninja | 17 ++ buildconf/release.ninja | 25 +++ src/Calculator.g4 | 68 ++++++++ src/builtin.cc | 180 +++++++++++++++++++++ src/builtin.h | 64 ++++++++ src/builtin_test.cc | 274 ++++++++++++++++++++++++++++++++ src/error.h | 30 ++++ src/language.cc | 95 +++++++++++ src/language.h | 230 +++++++++++++++++++++++++++ src/language_matchers.h | 52 +++++++ src/language_test.cc | 76 +++++++++ src/main.cc | 117 ++++++++++++++ src/parser_driver.cc | 71 +++++++++ src/parser_driver.h | 39 +++++ src/parser_driver_test.cc | 53 +++++++ src/ui.h | 30 ++++ src/ui/stream.cc | 84 ++++++++++ src/ui/stream.h | 56 +++++++ src/ui/terminal.cc | 184 ++++++++++++++++++++++ src/ui/terminal.h | 35 +++++ src/ui/terminal/line.cc | 206 ++++++++++++++++++++++++ src/ui/terminal/line.h | 101 ++++++++++++ src/util.cc | 32 ++++ src/util.h | 24 +++ third_party/abseil | 1 + 33 files changed, 2848 insertions(+) create mode 100644 .gitignore create mode 100644 .gitmodules create mode 100644 LICENSE create mode 100644 README.md create mode 120000 build.ninja create mode 100644 buildconf/asan.ninja create mode 100644 buildconf/common.ninja create mode 100644 buildconf/dbg.ninja create mode 100644 buildconf/fastbuild.ninja create mode 100644 buildconf/release.ninja create mode 100644 src/Calculator.g4 create mode 100644 src/builtin.cc create mode 100644 src/builtin.h create mode 100644 src/builtin_test.cc create mode 100644 src/error.h create mode 100644 src/language.cc create mode 100644 src/language.h create mode 100644 src/language_matchers.h create mode 100644 src/language_test.cc create mode 100644 src/main.cc create mode 100644 src/parser_driver.cc create mode 100644 src/parser_driver.h create mode 100644 src/parser_driver_test.cc create mode 100644 src/ui.h create mode 100644 src/ui/stream.cc create mode 100644 src/ui/stream.h create mode 100644 src/ui/terminal.cc create mode 100644 src/ui/terminal.h create mode 100644 src/ui/terminal/line.cc create mode 100644 src/ui/terminal/line.h create mode 100644 src/util.cc create mode 100644 src/util.h create mode 160000 third_party/abseil diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..0d4adcb --- /dev/null +++ b/.gitignore @@ -0,0 +1,26 @@ +# Copyright 2021 Benjamin Barenblat +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +.ninja_* + +*.interp +*.tokens +src/CalculatorBaseVisitor.* +src/CalculatorLexer.* +src/CalculatorParser.* +src/CalculatorVisitor.* +*.o + +*_test +ec diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..24868b3 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,4 @@ +[submodule "third_party/abseil"] + path = third_party/abseil + url = https://git.benjamin.barenblat.name/ec-abseil.git + ignore = dirty diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..d645695 --- /dev/null +++ b/LICENSE @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright [yyyy] [name of copyright owner] + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/README.md b/README.md new file mode 100644 index 0000000..372a089 --- /dev/null +++ b/README.md @@ -0,0 +1,44 @@ +EC, a terminal-based RPN calculator +=================================== + +EC (binary: `ec`) is a terminal-based RPN calculator inspired by +Hewlett-Packard’s venerable HP 48 line. It aims to be the calculator of +choice for the discriminating computer scientist. + +EC is ready for everyday use. It supports the four basic functions, powers and +roots (with `sq`/`sqrt` and `pow`/`xroot`), logarithms (`ln`/`exp` for base _e_, +`log`/`alog` for base 10), and trigonometry +(`sin`/`cos`/`tan`/`asin`/`acos`/`atan`). It is accessible via a batch mode (try +`echo 2 2 + | ec`), and if invoked interactively, it provides basic line +editing. On the other hand, arrow keys don’t work, the calculator is not +programmable, you can’t control the output format, there’s no undo support, +trigonometry is always in radians, there’s no support for complex numbers, and +the standard library is somewhat impoverished (e.g., `pick` is not yet +implemented). All of these will be fixed before we declare version 1.0; if you’d +like to help, please get in touch! + +**EC’s input language is not yet stable.** At some point before version 1.0 is +declared, the input language will become stable, but for the time being, any +scripts you write in the EC language may be broken by future releases. If you’d +like to take on any serious scripting in EC, please get in touch; we may be able +to provisionally stabilize certain language features to avoid breaking you. + +Currently, EC performs all computations with double-precision binary floats. +This means that all the ordinary issues with binary floating point come into +play; notably, many common decimal fractions (like 0.1) cannot be represented +exactly within EC. EC uses guard digits and conservative display settings to +prevent the most obvious roundoff errors (EC displays 0.1 as 0.1, not +0.10000000000000000555), and all told, EC’s precision is fairly close to that of +the original HP calculator line. Nonetheless, EC does not yet offer the same +level of precision as more recent calculators (e.g., the HP Prime) or true +computer mathematics systems (e.g., +[Xcas](https://www-fourier.ujf-grenoble.fr/~parisse/giac.html)). If you’re doing +heavy-duty numerical analysis, EC is not yet the tool for you. + +To build EC, you’ll need [our customized version of +Abseil](https://git.benjamin.barenblat.name/ec-abseil/), which is checked in as +a Git submodule. You’ll also need GCC, [Antlr 4](https://www.antlr.org/), +and [Ninja](https://ninja-build.org/), none of which is checked in; on a Debian +system, you can run `apt install build-essential ninja-build antlr4 +libantlr4-runtime-dev` to get the packages you need. Fire up `ninja`, wait a +bit, and you’ll soon have an `ec` binary in the repository root. Enjoy! diff --git a/build.ninja b/build.ninja new file mode 120000 index 0000000..d4e407e --- /dev/null +++ b/build.ninja @@ -0,0 +1 @@ +buildconf/fastbuild.ninja \ No newline at end of file diff --git a/buildconf/asan.ninja b/buildconf/asan.ninja new file mode 100644 index 0000000..8f79f9e --- /dev/null +++ b/buildconf/asan.ninja @@ -0,0 +1,20 @@ +# Copyright 2021 Google LLC +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +cxxflags = -fsanitize=address -Werror +third_party_cxxflags = -fsanitize=address + +ldflags = -fsanitize=address + +subninja buildconf/common.ninja diff --git a/buildconf/common.ninja b/buildconf/common.ninja new file mode 100644 index 0000000..d31a1b4 --- /dev/null +++ b/buildconf/common.ninja @@ -0,0 +1,389 @@ +# Copyright 2021 Google LLC +# Copyright 2021 Benjamin Barenblat +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +ninja_required_version = 1.3 + +absl = third_party/abseil/absl + +antlrflags = -no-listener -visitor -package ec + +common_cxxflags = -I. -isystem third_party/abseil -I/usr/include/antlr4-runtime -isystem /usr/include/antlr4-runtime -DGTEST_HAS_PTHREAD=1 -pipe -pthread + +cxxflags = $common_cxxflags -std=c++17 -Wall -Wextra -Wno-logical-op-parentheses -Wno-sign-compare -fdiagnostics-show-template-tree $cxxflags +third_party_cxxflags = $common_cxxflags -std=c++17 -fdiagnostics-show-template-tree $third_party_cxxflags + +third_party_cxxflags = $common_cxxflags $third_party_cxxflags + +rule antlr + command = antlr4 $antlrflags $in + description = Generating parser from $in + +rule antlrdep + command = gen/antlr4_dyndep $antlrflags $in >$out + description = Computing outputs from $in + +rule ar + command = rm -f $out && ar -rcs $out $in + description = Generating $out + +rule cxx + command = g++ -MD -MT $out -MF $out.d -c $in -o $out $cxxflags + description = Compiling $out + depfile = $out.d + deps = gcc + +rule link + command = g++ $ldflags -o $out $in $libs -pthread + description = Linking $out + +build | src/CalculatorBaseVisitor.cpp src/CalculatorBaseVisitor.h src/Calculator.interp src/CalculatorLexer.cpp src/CalculatorLexer.h src/CalculatorLexer.interp src/CalculatorLexer.tokens src/CalculatorParser.cpp src/CalculatorParser.h src/Calculator.tokens src/CalculatorVisitor.cpp src/CalculatorVisitor.h: antlr src/Calculator.g4 + +build src/CalculatorBaseVisitor.o: cxx src/CalculatorBaseVisitor.cpp + cxxflags = $third_party_cxxflags +build src/CalculatorLexer.o: cxx src/CalculatorLexer.cpp + cxxflags = $third_party_cxxflags +build src/CalculatorParser.o: cxx src/CalculatorParser.cpp + cxxflags = $third_party_cxxflags +build src/CalculatorVisitor.o: cxx src/CalculatorVisitor.cpp + cxxflags = $third_party_cxxflags +build src/builtin.o: cxx src/builtin.cc +build src/language.o: cxx src/language.cc +build src/main.o: cxx src/main.cc +build src/parser_driver.o: cxx src/parser_driver.cc || src/CalculatorBaseVisitor.h src/CalculatorLexer.h src/CalculatorParser.h +build src/ui/stream.o: cxx src/ui/stream.cc +build src/ui/terminal.o: cxx src/ui/terminal.cc +build src/ui/terminal/line.o: cxx src/ui/terminal/line.cc +build src/util.o: cxx src/util.cc + +build src/builtin_test.o: cxx src/builtin_test.cc +build src/builtin_test: link $ + src/builtin.o src/builtin_test.o src/language.o $ + $absl/strings/cord.a $absl/strings/cordz_info.a $absl/strings/cord_internal.a $absl/strings/cordz_functions.a $absl/strings/cordz_handle.a $absl/hash/hash.a $absl/hash/city.a $absl/types/bad_variant_access.a $absl/hash/low_level_hash.a $absl/container/raw_hash_set.a $absl/types/bad_optional_access.a $absl/container/hashtablez_sampler.a $absl/profiling/exponential_biased.a $absl/synchronization/synchronization.a $absl/synchronization/graphcycles_internal.a $absl/debugging/stacktrace.a $absl/debugging/symbolize.a $absl/debugging/debugging_internal.a $absl/debugging/demangle_internal.a $absl/base/malloc_internal.a third_party/abseil/time/time.a $absl/time/civil_time.a $absl/strings/strings.a $absl/strings/internal.a $absl/base/base.a $absl/base/spinlock_wait.a $absl/numeric/int128.a $absl/time/time_zone.a $absl/base/throw_delegate.a $absl/base/raw_logging_internal.a $absl/base/log_severity.a + libs = -lgmock_main -lgmock -lgtest -lm -lrt + +build src/language_test.o: cxx src/language_test.cc +build src/language_test: link $ + src/builtin.o src/language.o src/language_test.o $ + $absl/strings/cord.a $absl/strings/cordz_info.a $absl/strings/cord_internal.a $absl/strings/cordz_functions.a $absl/strings/cordz_handle.a $absl/hash/hash.a $absl/hash/city.a $absl/types/bad_variant_access.a $absl/hash/low_level_hash.a $absl/container/raw_hash_set.a $absl/types/bad_optional_access.a $absl/container/hashtablez_sampler.a $absl/profiling/exponential_biased.a $absl/synchronization/synchronization.a $absl/synchronization/graphcycles_internal.a $absl/debugging/stacktrace.a $absl/debugging/symbolize.a $absl/debugging/debugging_internal.a $absl/debugging/demangle_internal.a $absl/base/malloc_internal.a third_party/abseil/time/time.a $absl/time/civil_time.a $absl/strings/strings.a $absl/strings/internal.a $absl/base/base.a $absl/base/spinlock_wait.a $absl/numeric/int128.a $absl/time/time_zone.a $absl/base/throw_delegate.a $absl/base/raw_logging_internal.a $absl/base/log_severity.a + libs = -lgmock_main -lgmock -lgtest -lrt + +build src/parser_driver_test.o: cxx src/parser_driver_test.cc +build src/parser_driver_test: link $ + src/builtin.o src/CalculatorBaseVisitor.o src/CalculatorLexer.o src/CalculatorParser.o src/CalculatorVisitor.o src/language.o src/parser_driver.o src/parser_driver_test.o $ + $absl/strings/cord.a $absl/strings/cordz_info.a $absl/strings/cord_internal.a $absl/strings/cordz_functions.a $absl/strings/cordz_handle.a $absl/hash/hash.a $absl/hash/city.a $absl/types/bad_variant_access.a $absl/hash/low_level_hash.a $absl/container/raw_hash_set.a $absl/types/bad_optional_access.a $absl/container/hashtablez_sampler.a $absl/profiling/exponential_biased.a $absl/synchronization/synchronization.a $absl/synchronization/graphcycles_internal.a $absl/debugging/stacktrace.a $absl/debugging/symbolize.a $absl/debugging/debugging_internal.a $absl/debugging/demangle_internal.a $absl/base/malloc_internal.a third_party/abseil/time/time.a $absl/time/civil_time.a $absl/strings/strings.a $absl/strings/internal.a $absl/base/base.a $absl/base/spinlock_wait.a $absl/numeric/int128.a $absl/time/time_zone.a $absl/base/throw_delegate.a $absl/base/raw_logging_internal.a $absl/base/log_severity.a + libs = -lgmock_main -lgmock -lgtest -lantlr4-runtime -lrt + +build ec: link $ + src/CalculatorBaseVisitor.o src/CalculatorLexer.o src/CalculatorParser.o src/CalculatorVisitor.o src/builtin.o src/language.o src/main.o src/parser_driver.o src/util.o src/ui/stream.o src/ui/terminal.o src/ui/terminal/line.o $ + $absl/strings/cord.a $absl/strings/cordz_info.a $absl/strings/cord_internal.a $absl/strings/cordz_functions.a $absl/strings/cordz_handle.a $absl/hash/hash.a $absl/hash/city.a $absl/types/bad_variant_access.a $absl/hash/low_level_hash.a $absl/container/raw_hash_set.a $absl/types/bad_optional_access.a $absl/container/hashtablez_sampler.a $absl/profiling/exponential_biased.a $absl/synchronization/synchronization.a $absl/synchronization/graphcycles_internal.a $absl/debugging/stacktrace.a $absl/debugging/symbolize.a $absl/debugging/debugging_internal.a $absl/debugging/demangle_internal.a $absl/base/malloc_internal.a third_party/abseil/time/time.a $absl/time/civil_time.a $absl/strings/strings.a $absl/strings/internal.a $absl/base/base.a $absl/base/spinlock_wait.a $absl/numeric/int128.a $absl/time/time_zone.a $absl/base/throw_delegate.a $absl/base/raw_logging_internal.a $absl/base/log_severity.a + libs = -lantlr4-runtime -lm -lrt + +# //absl/base +build $absl/base/base.a: ar $ + $absl/base/internal/cycleclock.o $ + $absl/base/internal/spinlock.o $ + $absl/base/internal/sysinfo.o $ + $absl/base/internal/thread_identity.o $ + $absl/base/internal/unscaledcycleclock.o +build $absl/base/internal/cycleclock.o: cxx $absl/base/internal/cycleclock.cc + cxxflags = $third_party_cxxflags +build $absl/base/internal/spinlock.o: cxx $absl/base/internal/spinlock.cc + cxxflags = $third_party_cxxflags +build $absl/base/internal/sysinfo.o: cxx $absl/base/internal/sysinfo.cc + cxxflags = $third_party_cxxflags +build $absl/base/internal/thread_identity.o: cxx $absl/base/internal/thread_identity.cc + cxxflags = $third_party_cxxflags +build $absl/base/internal/unscaledcycleclock.o: cxx $absl/base/internal/unscaledcycleclock.cc + cxxflags = $third_party_cxxflags + +# //absl/base:log_severity +build $absl/base/log_severity.a: ar $absl/base/log_severity.o +build $absl/base/log_severity.o: cxx $absl/base/log_severity.cc + cxxflags = $third_party_cxxflags + +# //absl/base:malloc_internal +build $absl/base/malloc_internal.a: ar $absl/base/internal/low_level_alloc.o +build $absl/base/internal/low_level_alloc.o: cxx $absl/base/internal/low_level_alloc.cc + cxxflags = $third_party_cxxflags + +# //absl/base:raw_logging_internal +build $absl/base/raw_logging_internal.a: ar $absl/base/internal/raw_logging.o +build $absl/base/internal/raw_logging.o: cxx $absl/base/internal/raw_logging.cc + cxxflags = $third_party_cxxflags + +# //absl/base:spinlock_wait +build $absl/base/spinlock_wait.a: ar $absl/base/internal/spinlock_wait.o +build $absl/base/internal/spinlock_wait.o: cxx $absl/base/internal/spinlock_wait.cc | $absl/base/internal/spinlock_linux.inc + cxxflags = $third_party_cxxflags + +# //absl/base:throw_delegate +build $absl/base/throw_delegate.a: ar $absl/base/internal/throw_delegate.o +build $absl/base/internal/throw_delegate.o: cxx $absl/base/internal/throw_delegate.cc + cxxflags = $third_party_cxxflags + +# //absl/container:hashtablez_sampler +build $absl/container/hashtablez_sampler.a: ar $ + $absl/container/internal/hashtablez_sampler.o $ + $absl/container/internal/hashtablez_sampler_force_weak_definition.o +build $absl/container/internal/hashtablez_sampler.o: cxx $absl/container/internal/hashtablez_sampler.cc + cxxflags = $third_party_cxxflags +build $absl/container/internal/hashtablez_sampler_force_weak_definition.o: cxx $absl/container/internal/hashtablez_sampler_force_weak_definition.cc + cxxflags = $third_party_cxxflags + +# //absl/container:raw_hash_set +build $absl/container/raw_hash_set.a: ar $absl/container/internal/raw_hash_set.o +build $absl/container/internal/raw_hash_set.o: cxx $absl/container/internal/raw_hash_set.cc + cxxflags = $third_party_cxxflags + +# //absl/debugging:debugging_internal +build $absl/debugging/debugging_internal.a: ar $ + $absl/debugging/internal/address_is_readable.o $ + $absl/debugging/internal/elf_mem_image.o $ + $absl/debugging/internal/vdso_support.o +build $absl/debugging/internal/address_is_readable.o: cxx $absl/debugging/internal/address_is_readable.cc + cxxflags = $third_party_cxxflags +build $absl/debugging/internal/elf_mem_image.o: cxx $absl/debugging/internal/elf_mem_image.cc + cxxflags = $third_party_cxxflags +build $absl/debugging/internal/vdso_support.o: cxx $absl/debugging/internal/vdso_support.cc + cxxflags = $third_party_cxxflags + +# //absl:debugging:demangle_internal +build $absl/debugging/demangle_internal.a: ar $absl/debugging/internal/demangle.o +build $absl/debugging/internal/demangle.o: cxx $absl/debugging/internal/demangle.cc + cxxflags = $third_party_cxxflags + +# //absl/debugging:stacktrace +build $absl/debugging/stacktrace.a: ar $absl/debugging/stacktrace.o +build $absl/debugging/stacktrace.o: cxx $absl/debugging/stacktrace.cc | $absl/debugging/internal/stacktrace_config.h $absl/debugging/internal/stacktrace_x86-inl.inc + cxxflags = $third_party_cxxflags + +# //absl/debugging:symbolize +build $absl/debugging/symbolize.a: ar $absl/debugging/symbolize.o +build $absl/debugging/symbolize.o: cxx $absl/debugging/symbolize.cc | $absl/debugging/symbolize_elf.inc + cxxflags = $third_party_cxxflags + +# //absl/hash +build $absl/hash/hash.a: ar $absl/hash/internal/hash.o +build $absl/hash/internal/hash.o: cxx $absl/hash/internal/hash.cc + cxxflags = $third_party_cxxflags + +# //absl/hash:city +build $absl/hash/city.a: ar $absl/hash/internal/city.o +build $absl/hash/internal/city.o: cxx $absl/hash/internal/city.cc + cxxflags = $third_party_cxxflags + +# //absl/hash:low_level_hash +build $absl/hash/low_level_hash.a: ar $absl/hash/internal/low_level_hash.o +build $absl/hash/internal/low_level_hash.o: cxx $absl/hash/internal/low_level_hash.cc + cxxflags = $third_party_cxxflags + +# //absl/numeric:int128 +build $absl/numeric/int128.a: ar $absl/numeric/int128.o +build $absl/numeric/int128.o: cxx $absl/numeric/int128.cc | $absl/numeric/int128_have_intrinsic.inc $absl/numeric/int128_no_intrinsic.inc + cxxflags = $third_party_cxxflags + +# //absl/profiling:exponential_biased +build $absl/profiling/exponential_biased.a: ar $absl/profiling/internal/exponential_biased.o +build $absl/profiling/internal/exponential_biased.o: cxx $absl/profiling/internal/exponential_biased.cc + cxxflags = $third_party_cxxflags + +# //absl/strings +build $absl/strings/strings.a: ar $ + $absl/strings/ascii.o $ + $absl/strings/charconv.o $ + $absl/strings/escaping.o $ + $absl/strings/internal/charconv_bigint.o $ + $absl/strings/internal/charconv_parse.o $ + $absl/strings/internal/memutil.o $ + $absl/strings/match.o $ + $absl/strings/numbers.o $ + $absl/strings/str_cat.o $ + $absl/strings/str_replace.o $ + $absl/strings/str_split.o $ + $absl/strings/string_view.o $ + $absl/strings/substitute.o +build $absl/strings/ascii.o: cxx $absl/strings/ascii.cc + cxxflags = $third_party_cxxflags +build $absl/strings/charconv.o: cxx $absl/strings/charconv.cc + cxxflags = $third_party_cxxflags +build $absl/strings/escaping.o: cxx $absl/strings/escaping.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/charconv_bigint.o: cxx $absl/strings/internal/charconv_bigint.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/charconv_parse.o: cxx $absl/strings/internal/charconv_parse.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/memutil.o: cxx $absl/strings/internal/memutil.cc + cxxflags = $third_party_cxxflags +build $absl/strings/match.o: cxx $absl/strings/match.cc + cxxflags = $third_party_cxxflags +build $absl/strings/numbers.o: cxx $absl/strings/numbers.cc + cxxflags = $third_party_cxxflags +build $absl/strings/str_cat.o: cxx $absl/strings/str_cat.cc + cxxflags = $third_party_cxxflags +build $absl/strings/str_replace.o: cxx $absl/strings/str_replace.cc + cxxflags = $third_party_cxxflags +build $absl/strings/str_split.o: cxx $absl/strings/str_split.cc + cxxflags = $third_party_cxxflags +build $absl/strings/string_view.o: cxx $absl/strings/string_view.cc + cxxflags = $third_party_cxxflags +build $absl/strings/substitute.o: cxx $absl/strings/substitute.cc + cxxflags = $third_party_cxxflags + +# //absl/strings:cord +build $absl/strings/cord.a: ar $absl/strings/cord.o +build $absl/strings/cord.o: cxx $absl/strings/cord.cc + cxxflags = $third_party_cxxflags + +# //absl/strings:cord_internal +build $absl/strings/cord_internal.a: ar $ + $absl/strings/internal/cord_internal.o $ + $absl/strings/internal/cord_rep_btree.o $ + $absl/strings/internal/cord_rep_btree_navigator.o $ + $absl/strings/internal/cord_rep_btree_reader.o $ + $absl/strings/internal/cord_rep_consume.o $ + $absl/strings/internal/cord_rep_ring.o +build $absl/strings/internal/cord_internal.o: cxx $absl/strings/internal/cord_internal.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/cord_rep_btree.o: cxx $absl/strings/internal/cord_rep_btree.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/cord_rep_btree_navigator.o: cxx $absl/strings/internal/cord_rep_btree_navigator.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/cord_rep_btree_reader.o: cxx $absl/strings/internal/cord_rep_btree_reader.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/cord_rep_consume.o: cxx $absl/strings/internal/cord_rep_consume.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/cord_rep_ring.o: cxx $absl/strings/internal/cord_rep_ring.cc + cxxflags = $third_party_cxxflags + +# //absl/strings:cordz_functions +build $absl/strings/cordz_functions.a: ar $absl/strings/internal/cordz_functions.o +build $absl/strings/internal/cordz_functions.o: cxx $absl/strings/internal/cordz_functions.cc + cxxflags = $third_party_cxxflags + +# //absl/strings:cordz_handle +build $absl/strings/cordz_handle.a: ar $absl/strings/internal/cordz_handle.o +build $absl/strings/internal/cordz_handle.o: cxx $absl/strings/internal/cordz_handle.cc + cxxflags = $third_party_cxxflags + +# //absl/strings:cordz_info +build $absl/strings/cordz_info.a: ar $absl/strings/internal/cordz_info.o +build $absl/strings/internal/cordz_info.o: cxx $absl/strings/internal/cordz_info.cc + cxxflags = $third_party_cxxflags + +# //absl/strings:internal +build $absl/strings/internal.a: ar $ + $absl/strings/internal/escaping.o $ + $absl/strings/internal/ostringstream.o $ + $absl/strings/internal/utf8.o +build $absl/strings/internal/escaping.o: cxx $absl/strings/internal/escaping.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/ostringstream.o: cxx $absl/strings/internal/ostringstream.cc + cxxflags = $third_party_cxxflags +build $absl/strings/internal/utf8.o: cxx $absl/strings/internal/utf8.cc + cxxflags = $third_party_cxxflags + +# //absl/synchronization +build $absl/synchronization/synchronization.a: ar $ + $absl/synchronization/barrier.o $ + $absl/synchronization/blocking_counter.o $ + $absl/synchronization/internal/create_thread_identity.o $ + $absl/synchronization/internal/per_thread_sem.o $ + $absl/synchronization/internal/waiter.o $ + $absl/synchronization/notification.o $ + $absl/synchronization/mutex.o +build $absl/synchronization/barrier.o: cxx $absl/synchronization/barrier.cc + cxxflags = $third_party_cxxflags +build $absl/synchronization/blocking_counter.o: cxx $absl/synchronization/blocking_counter.cc + cxxflags = $third_party_cxxflags +build $absl/synchronization/internal/create_thread_identity.o: cxx $absl/synchronization/internal/create_thread_identity.cc + cxxflags = $third_party_cxxflags +build $absl/synchronization/internal/per_thread_sem.o: cxx $absl/synchronization/internal/per_thread_sem.cc + cxxflags = $third_party_cxxflags +build $absl/synchronization/internal/waiter.o: cxx $absl/synchronization/internal/waiter.cc + cxxflags = $third_party_cxxflags +build $absl/synchronization/notification.o: cxx $absl/synchronization/notification.cc + cxxflags = $third_party_cxxflags +build $absl/synchronization/mutex.o: cxx $absl/synchronization/mutex.cc + cxxflags = $third_party_cxxflags + +# //absl/synchronization:graphcycles_internal +build $absl/synchronization/graphcycles_internal.a: ar $absl/synchronization/internal/graphcycles.o +build $absl/synchronization/internal/graphcycles.o: cxx $absl/synchronization/internal/graphcycles.cc + cxxflags = $third_party_cxxflags + +# //absl/time +build third_party/abseil/time/time.a: ar $ + $absl/time/civil_time.o $ + $absl/time/clock.o $ + $absl/time/duration.o $ + $absl/time/format.o $ + $absl/time/absl/time.o +build $absl/time/civil_time.o: cxx $absl/time/civil_time.cc + cxxflags = $third_party_cxxflags +build $absl/time/clock.o: cxx $absl/time/clock.cc | $absl/time/internal/get_current_time_posix.inc + cxxflags = $third_party_cxxflags +build $absl/time/duration.o: cxx $absl/time/duration.cc + cxxflags = $third_party_cxxflags +build $absl/time/format.o: cxx $absl/time/format.cc + cxxflags = $third_party_cxxflags +build $absl/time/absl/time.o: cxx $absl/time/time.cc + cxxflags = $third_party_cxxflags + +# //absl/time:civil_time +build $absl/time/civil_time.a: ar $absl/time/internal/cctz/src/civil_time_detail.o +build $absl/time/internal/cctz/src/civil_time_detail.o: cxx $absl/time/internal/cctz/src/civil_time_detail.cc + cxxflags = $third_party_cxxflags + +# //absl/time:time_zone +build $absl/time/time_zone.a: ar $ + $absl/time/internal/cctz/src/time_zone_fixed.o $ + $absl/time/internal/cctz/src/time_zone_format.o $ + $absl/time/internal/cctz/src/time_zone_if.o $ + $absl/time/internal/cctz/src/time_zone_impl.o $ + $absl/time/internal/cctz/src/time_zone_info.o $ + $absl/time/internal/cctz/src/time_zone_libc.o $ + $absl/time/internal/cctz/src/time_zone_lookup.o $ + $absl/time/internal/cctz/src/time_zone_posix.o $ + $absl/time/internal/cctz/src/zone_info_source.o +build $absl/time/internal/cctz/src/time_zone_fixed.o: cxx $absl/time/internal/cctz/src/time_zone_fixed.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_format.o: cxx $absl/time/internal/cctz/src/time_zone_format.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_if.o: cxx $absl/time/internal/cctz/src/time_zone_if.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_impl.o: cxx $absl/time/internal/cctz/src/time_zone_impl.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_info.o: cxx $absl/time/internal/cctz/src/time_zone_info.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_libc.o: cxx $absl/time/internal/cctz/src/time_zone_libc.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_lookup.o: cxx $absl/time/internal/cctz/src/time_zone_lookup.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/time_zone_posix.o: cxx $absl/time/internal/cctz/src/time_zone_posix.cc + cxxflags = $third_party_cxxflags +build $absl/time/internal/cctz/src/zone_info_source.o: cxx $absl/time/internal/cctz/src/zone_info_source.cc + cxxflags = $third_party_cxxflags + +# // absl/types:bad_optional_access +build $absl/types/bad_optional_access.a: ar $absl/types/bad_optional_access.o +build $absl/types/bad_optional_access.o: cxx $absl/types/bad_optional_access.cc + cxxflags = $third_party_cxxflags + +# // absl/types:bad_variant_access +build $absl/types/bad_variant_access.a: ar $absl/types/bad_variant_access.o +build $absl/types/bad_variant_access.o: cxx $absl/types/bad_variant_access.cc + cxxflags = $third_party_cxxflags + +default ec diff --git a/buildconf/dbg.ninja b/buildconf/dbg.ninja new file mode 100644 index 0000000..cce13eb --- /dev/null +++ b/buildconf/dbg.ninja @@ -0,0 +1,18 @@ +# Copyright 2021 Google LLC +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +cxxflags = -Og -g3 -Werror +third_party_cxxflags = -Og -g3 + +subninja buildconf/common.ninja diff --git a/buildconf/fastbuild.ninja b/buildconf/fastbuild.ninja new file mode 100644 index 0000000..c321e30 --- /dev/null +++ b/buildconf/fastbuild.ninja @@ -0,0 +1,17 @@ +# Copyright 2021 Google LLC +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +cxxflags = -Werror + +subninja buildconf/common.ninja diff --git a/buildconf/release.ninja b/buildconf/release.ninja new file mode 100644 index 0000000..7b1281b --- /dev/null +++ b/buildconf/release.ninja @@ -0,0 +1,25 @@ +# Copyright 2021 Google LLC +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may not +# use this file except in compliance with the License. You may obtain a copy of +# the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations under +# the License. + +# Don't set -Werror in general; we don't want to risk future warnings appearing +# in GCC's -Wall/-Wextra and breaking the build. +# +# Most of these flags come from Debian's dpkg-buildflags, with the exception +# that we aim for correctness with -O3, rather than just -O2. +cxxflags = -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -O3 -DNDEBUG -DGLPLANET_DISABLE_EGL_THREAD_SAFETY_CHECKS -DGLPLANET_DISABLE_GL_THREAD_SAFETY_CHECKS -DGLPLANET_DISABLE_AGGRESSIVE_ERROR_CHECKING -fstack-protector-strong -ffunction-sections -fdata-sections -flto +third_party_cxxflags = -D_FORTIFY_SOURCE=2 -O3 -DNDEBUG -fstack-protector-strong -ffunction-sections -fdata-sections -flto + +ldflags = -flto -Wl,-O2 -Wl,-z,relro -Wl,--gc-sections -Wl,--as-needed + +subninja buildconf/common.ninja diff --git a/src/Calculator.g4 b/src/Calculator.g4 new file mode 100644 index 0000000..354a2e9 --- /dev/null +++ b/src/Calculator.g4 @@ -0,0 +1,68 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// The lexer and parser grammars for the EC language. + +grammar Calculator; + +options { + language = Cpp; +} + +@parser::postinclude { +#include +#include +#include + +#include "third_party/abseil/absl/strings/numbers.h" +} + +program : term* ; + +term : number | identifier | error ; + +number returns [double value] + : s=NUMBER { + if (!absl::SimpleAtod($s->getText(), &$value)) { + throw std::runtime_error("Calculator: parser produced an invalid double"); + } + } + ; + +identifier returns [std::string value] + : s=IDENTIFIER { + $value = std::move($s->getText()); + } + | SUGARED_ADD { $value = "add"; } + | SUGARED_SUB { $value = "sub"; } + | SUGARED_MUL { $value = "mul"; } + | SUGARED_DIV { $value = "div"; } + ; + +error : ERROR ; + +NUMBER : [+-]? (DIGIT+ '.'? DIGIT* | '.' DIGIT+) ('e' [+-]? DIGIT+)? ; + +IDENTIFIER : [\p{Alpha}\p{General_Category=Other_Letter}] [\p{Alnum}\p{General_Category=Other_Letter}]* ; + +SUGARED_ADD : '+' ; +SUGARED_SUB : '-' ; +SUGARED_MUL : '*' ; +SUGARED_DIV : '/' ; + +WS : [\p{White_Space}]+ -> skip ; + +ERROR : . ; + +fragment DIGIT : [0-9] ; diff --git a/src/builtin.cc b/src/builtin.cc new file mode 100644 index 0000000..e182edd --- /dev/null +++ b/src/builtin.cc @@ -0,0 +1,180 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/builtin.h" + +#include + +#include +#include +#include + +#include "src/language.h" +#include "third_party/abseil/absl/container/flat_hash_map.h" +#include "third_party/abseil/absl/memory/memory.h" +#include "third_party/abseil/absl/strings/string_view.h" + +namespace ec { + +namespace { + +// Requires the compiler to select the double-valued overload of its argument. +double (*DoubleOverload(double (*f)(double)) noexcept)(double) { return f; } +double (*DoubleOverload(double (*f)(double, double)) noexcept)(double, double) { + return f; +} + +// Pops the top of the stack and returns it as a GroundTerm; throws TypeError if +// it's not. +std::shared_ptr PopGroundTerm(absl::string_view op, + State& s) { + if (s.stack.empty()) { + throw StackUnderflow(op); + } + auto ground = std::dynamic_pointer_cast(s.stack.back()); + if (ground == nullptr) { + throw TypeError( + absl::StrCat("expected number; got ", s.stack.back()->Show())); + } + s.stack.pop_back(); + return ground; +} + +// Executes a unary operation on the top of the stack. +void Unop(absl::string_view op, std::function f, State& s) { + if (s.stack.empty()) { + throw StackUnderflow(op); + } + s.stack.push_back(GroundTerm::Make(f(PopGroundTerm(op, s)->value()))); +} + +// Executes a binary operation on the top of the stack. +void Binop(absl::string_view op, std::function f, + State& s) { + if (s.stack.size() < 2) { + throw StackUnderflow(op); + } + std::shared_ptr right, left; + right = PopGroundTerm(op, s); + left = PopGroundTerm(op, s); + s.stack.push_back(GroundTerm::Make(f(left->value(), right->value()))); +} + +} // namespace + +absl::flat_hash_map> +BuiltinEnvironment() noexcept { + return { + {"dup", ForeignProgramTerm::Make(BuiltinDup)}, // + {"drop", ForeignProgramTerm::Make(BuiltinDrop)}, // + {"swap", ForeignProgramTerm::Make(BuiltinSwap)}, + + {"pi", GroundTerm::Make(M_PI)}, // + {"e", GroundTerm::Make(M_E)}, + + {"neg", ForeignProgramTerm::Make(BuiltinNeg)}, // + {"inv", ForeignProgramTerm::Make(BuiltinInv)}, // + {"sq", ForeignProgramTerm::Make(BuiltinSq)}, // + {"sqrt", ForeignProgramTerm::Make(BuiltinSqrt)}, // + {"alog", ForeignProgramTerm::Make(BuiltinAlog)}, // + {"log", ForeignProgramTerm::Make(BuiltinLog)}, // + {"exp", ForeignProgramTerm::Make(BuiltinExp)}, // + {"ln", ForeignProgramTerm::Make(BuiltinLn)}, // + {"sin", ForeignProgramTerm::Make(BuiltinSin)}, // + {"cos", ForeignProgramTerm::Make(BuiltinCos)}, // + {"tan", ForeignProgramTerm::Make(BuiltinTan)}, // + {"asin", ForeignProgramTerm::Make(BuiltinAsin)}, // + {"acos", ForeignProgramTerm::Make(BuiltinAcos)}, // + {"atan", ForeignProgramTerm::Make(BuiltinAtan)}, // + {"abs", ForeignProgramTerm::Make(BuiltinAbs)}, + + {"add", ForeignProgramTerm::Make(BuiltinAdd)}, // + {"sub", ForeignProgramTerm::Make(BuiltinSub)}, // + {"mul", ForeignProgramTerm::Make(BuiltinMul)}, // + {"div", ForeignProgramTerm::Make(BuiltinDiv)}, // + {"pow", ForeignProgramTerm::Make(BuiltinPow)}, // + {"xroot", ForeignProgramTerm::Make(BuiltinXroot)}, + }; +} + +void BuiltinDup(State& s) { + if (s.stack.empty()) { + throw StackUnderflow("dup"); + } + s.stack.push_back(s.stack.back()->Clone()); +} + +void BuiltinDrop(State& s) { + if (s.stack.empty()) { + throw StackUnderflow("drop"); + } + s.stack.pop_back(); +} + +void BuiltinSwap(State& s) { + if (s.stack.size() < 2) { + throw StackUnderflow("swap"); + } + std::shared_ptr x, y; + x = s.stack.back(); + s.stack.pop_back(); + y = s.stack.back(); + s.stack.pop_back(); + s.stack.insert(s.stack.end(), {x, y}); +} + +void BuiltinNeg(State& s) { Unop("neg", std::negate(), s); } + +void BuiltinInv(State& s) { + Unop( + "inv", [](double d) { return 1 / d; }, s); +} + +void BuiltinSq(State& s) { + Unop( + "sq", [](double d) { return d * d; }, s); +} +void BuiltinSqrt(State& s) { Unop("sqrt", DoubleOverload(sqrt), s); } + +void BuiltinAlog(State& s) { + Unop( + "alog", [](double d) { return pow(10, d); }, s); +} +void BuiltinLog(State& s) { Unop("log", DoubleOverload(log10), s); } + +void BuiltinExp(State& s) { Unop("exp", DoubleOverload(exp), s); } +void BuiltinLn(State& s) { Unop("ln", DoubleOverload(log), s); } + +void BuiltinSin(State& s) { Unop("sin", DoubleOverload(sin), s); } +void BuiltinCos(State& s) { Unop("cos", DoubleOverload(cos), s); } +void BuiltinTan(State& s) { Unop("tan", DoubleOverload(tan), s); } + +void BuiltinAsin(State& s) { Unop("asin", DoubleOverload(asin), s); } +void BuiltinAcos(State& s) { Unop("acos", DoubleOverload(acos), s); } +void BuiltinAtan(State& s) { Unop("atan", DoubleOverload(atan), s); } + +void BuiltinAbs(State& s) { Unop("abs", DoubleOverload(fabs), s); } + +void BuiltinAdd(State& s) { Binop("add", std::plus(), s); } +void BuiltinSub(State& s) { Binop("sub", std::minus(), s); } +void BuiltinMul(State& s) { Binop("mul", std::multiplies(), s); } +void BuiltinDiv(State& s) { Binop("div", std::divides(), s); } + +void BuiltinPow(State& s) { Binop("div", DoubleOverload(pow), s); } +void BuiltinXroot(State& s) { + Binop( + "xroot", [](double y, double x) { return pow(y, 1 / x); }, s); +} + +} // namespace ec diff --git a/src/builtin.h b/src/builtin.h new file mode 100644 index 0000000..f17a58d --- /dev/null +++ b/src/builtin.h @@ -0,0 +1,64 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// Built-in functions. + +#ifndef EC_SRC_BUILTIN_H_ +#define EC_SRC_BUILTIN_H_ + +#include +#include + +#include "src/language.h" +#include "third_party/abseil/absl/container/flat_hash_map.h" + +namespace ec { + +// The initial environment. +absl::flat_hash_map> +BuiltinEnvironment() noexcept; + +// Stack operations. +void BuiltinDup(State&); +void BuiltinDrop(State&); +void BuiltinSwap(State&); + +// Basic unary operations. +void BuiltinNeg(State&); +void BuiltinInv(State&); +void BuiltinSq(State&); +void BuiltinSqrt(State&); +void BuiltinAlog(State&); +void BuiltinLog(State&); +void BuiltinExp(State&); +void BuiltinLn(State&); +void BuiltinSin(State&); +void BuiltinCos(State&); +void BuiltinTan(State&); +void BuiltinAsin(State&); +void BuiltinAcos(State&); +void BuiltinAtan(State&); +void BuiltinAbs(State&); + +// Basic binary operations. +void BuiltinAdd(State&); +void BuiltinSub(State&); +void BuiltinMul(State&); +void BuiltinDiv(State&); +void BuiltinPow(State&); +void BuiltinXroot(State&); + +} // namespace ec + +#endif // EC_SRC_BUILTIN_H_ diff --git a/src/builtin_test.cc b/src/builtin_test.cc new file mode 100644 index 0000000..0197c99 --- /dev/null +++ b/src/builtin_test.cc @@ -0,0 +1,274 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/builtin.h" + +#include +#include +#include + +#include "src/language.h" +#include "src/language_matchers.h" + +namespace ec { +namespace { + +using ::testing::ElementsAre; +using ::testing::IsEmpty; + +void PushFive(State& s) { s.stack.push_back(GroundTerm::Make(5)); } + +TEST(DupTest, UnderflowsOnEmpty) { + State s; + EXPECT_THROW(BuiltinDup(s), StackUnderflow); +} + +TEST(DupTest, GroundTerm) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + BuiltinDup(s); + EXPECT_THAT(s.stack, + ElementsAre(PointsToGroundTerm(42), PointsToGroundTerm(42))); +} + +TEST(DropTest, UnderflowsOnEmpty) { + State s; + EXPECT_THROW(BuiltinDrop(s), StackUnderflow); +} + +TEST(DropTest, GroundTerm) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + BuiltinDrop(s); + EXPECT_THAT(s.stack, IsEmpty()); +} + +TEST(SwapTest, Underflow0) { + State s; + EXPECT_THROW(BuiltinSwap(s), StackUnderflow); +} + +TEST(SwapTest, Underflow1) { + State s; + s.stack.push_back(GroundTerm::Make(1)); + EXPECT_THROW(BuiltinSwap(s), StackUnderflow); +} + +TEST(SwapTest, Swaps) { + State s; + s.stack.push_back(GroundTerm::Make(1)); + s.stack.push_back(GroundTerm::Make(2)); + BuiltinSwap(s); + EXPECT_THAT(s.stack, + ElementsAre(PointsToGroundTerm(2), PointsToGroundTerm(1))); +} + +TEST(UnaryTest, Underflow) { + State s; + EXPECT_THROW(BuiltinNeg(s), StackUnderflow); +} + +TEST(UnaryTest, ProgramFails) { + State s; + s.stack.push_back(ForeignProgramTerm::Make(PushFive)); + EXPECT_THROW(BuiltinNeg(s), TypeError); +} + +TEST(UnaryBuiltinTest, Neg) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + BuiltinNeg(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(-42))); +} + +TEST(UnaryBuiltinTest, Inv) { + State s; + s.stack.push_back(GroundTerm::Make(4)); + BuiltinInv(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(0.25))); +} + +TEST(UnaryBuiltinTest, Sq) { + State s; + s.stack.push_back(GroundTerm::Make(4)); + BuiltinSq(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(16))); +} + +TEST(UnaryBuiltinTest, Sqrt) { + State s; + s.stack.push_back(GroundTerm::Make(16)); + BuiltinSqrt(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(4))); +} + +TEST(UnaryBuiltinTest, Alog) { + State s; + s.stack.push_back(GroundTerm::Make(3)); + BuiltinAlog(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(1000))); +} + +TEST(UnaryBuiltinTest, Log) { + State s; + s.stack.push_back(GroundTerm::Make(1000)); + BuiltinLog(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(3))); +} + +TEST(UnaryBuiltinTest, Exp) { + State s; + s.stack.push_back(GroundTerm::Make(2)); + BuiltinExp(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(7.38905609893065))); +} + +TEST(UnaryBuiltinTest, Ln) { + State s; + s.stack.push_back(GroundTerm::Make(2)); + BuiltinLn(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(M_LN2))); +} + +TEST(UnaryBuiltinTest, Sin) { + State s; + s.stack.push_back(GroundTerm::Make(M_PI_2)); + BuiltinSin(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(1))); +} + +TEST(UnaryBuiltinTest, Cos) { + State s; + s.stack.push_back(GroundTerm::Make(M_PI)); + BuiltinCos(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(-1))); +} + +TEST(UnaryBuiltinTest, Tan) { + State s; + s.stack.push_back(GroundTerm::Make(M_PI_4)); + BuiltinTan(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(1))); +} + +TEST(UnaryBuiltinTest, Asin) { + State s; + s.stack.push_back(GroundTerm::Make(1)); + BuiltinAsin(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(M_PI_2))); +} + +TEST(UnaryBuiltinTest, Acos) { + State s; + s.stack.push_back(GroundTerm::Make(-1)); + BuiltinAcos(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(M_PI))); +} + +TEST(UnaryBuiltinTest, Atan) { + State s; + s.stack.push_back(GroundTerm::Make(1)); + BuiltinAtan(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(M_PI_4))); +} + +TEST(UnaryBuiltinTest, Abs) { + State s; + s.stack.push_back(GroundTerm::Make(-42)); + BuiltinAbs(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(42))); +} + +TEST(BinaryTest, Underflow0) { + State s; + EXPECT_THROW(BuiltinAdd(s), StackUnderflow); +} + +TEST(BinaryTest, Underflow1) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + EXPECT_THROW(BuiltinAdd(s), StackUnderflow); +} + +TEST(BinaryTest, ProgramProgramFails) { + State s; + s.stack.push_back(ForeignProgramTerm::Make(PushFive)); + s.stack.push_back(ForeignProgramTerm::Make(PushFive)); + EXPECT_THROW(BuiltinAdd(s), TypeError); +} + +TEST(BinaryTest, ProgramGroundFails) { + State s; + s.stack.push_back(ForeignProgramTerm::Make(PushFive)); + s.stack.push_back(GroundTerm::Make(42)); + EXPECT_THROW(BuiltinAdd(s), TypeError); +} + +TEST(BinaryTest, GroundProgramFails) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + s.stack.push_back(ForeignProgramTerm::Make(PushFive)); + EXPECT_THROW(BuiltinAdd(s), TypeError); +} + +TEST(BinaryBuiltinTest, Add) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + s.stack.push_back(GroundTerm::Make(42)); + BuiltinAdd(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(84))); +} + +TEST(BinaryBuiltinTest, Sub) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + s.stack.push_back(GroundTerm::Make(42)); + BuiltinSub(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(0))); +} + +TEST(BinaryBuiltinTest, Mul) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + s.stack.push_back(GroundTerm::Make(42)); + BuiltinMul(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(1764))); +} + +TEST(BinaryBuiltinTest, Div) { + State s; + s.stack.push_back(GroundTerm::Make(42)); + s.stack.push_back(GroundTerm::Make(42)); + BuiltinDiv(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(1))); +} + +TEST(BinaryBuiltinTest, Pow) { + State s; + s.stack.push_back(GroundTerm::Make(2)); + s.stack.push_back(GroundTerm::Make(10)); + BuiltinPow(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(1024))); +} + +TEST(BinaryBuiltinTest, Xroot) { + State s; + s.stack.push_back(GroundTerm::Make(27)); + s.stack.push_back(GroundTerm::Make(3)); + BuiltinXroot(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(3))); +} + +} // namespace +} // namespace ec diff --git a/src/error.h b/src/error.h new file mode 100644 index 0000000..bad4d03 --- /dev/null +++ b/src/error.h @@ -0,0 +1,30 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#ifndef EC_SRC_ERROR_H_ +#define EC_SRC_ERROR_H_ + +#include + +namespace ec { + +// The root of the ec exception hierarchy. +class Error : public std::runtime_error { + public: + using std::runtime_error::runtime_error; +}; + +} // namespace ec + +#endif // EC_SRC_ERROR_H_ diff --git a/src/language.cc b/src/language.cc new file mode 100644 index 0000000..277c545 --- /dev/null +++ b/src/language.cc @@ -0,0 +1,95 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/language.h" + +#include + +#include +#include +#include +#include + +#include "src/builtin.h" +#include "third_party/abseil/absl/strings/str_cat.h" + +namespace ec { + +State::State() noexcept : environment(BuiltinEnvironment()) {} + +void GroundTerm::Evaluate(State& state) const noexcept { + state.stack.push_back(Clone()); +} + +std::string GroundTerm::Show() const noexcept { + // A double-precision value has 13 decimal digits of precision. + std::ostringstream s; + s.precision(13); + s << value_; + return s.str(); +} + +std::string GroundTerm::DebugString() const noexcept { + return absl::StrCat("GroundTerm(", value_, ")"); +} + +GroundTerm* GroundTerm::CloneImpl() const noexcept { + return new GroundTerm(*this); +} + +void ForeignProgramTerm::Evaluate(State& state) const { impl_(state); } + +std::string ForeignProgramTerm::Show() const noexcept { return ""; } + +std::string ForeignProgramTerm::DebugString() const noexcept { + return absl::StrCat("ForeignProgramTerm(", reinterpret_cast(impl_), + ")"); +} + +ForeignProgramTerm* ForeignProgramTerm::CloneImpl() const noexcept { + return new ForeignProgramTerm(*this); +} + +void SymbolTerm::Evaluate(State& state) const { + auto it = state.environment.find(name_); + if (it == state.environment.end()) { + throw UndefinedName(name_); + } + it->second->Evaluate(state); +} + +std::string SymbolTerm::Show() const noexcept { + return absl::StrCat("'", name_); +} + +std::string SymbolTerm::DebugString() const noexcept { + return absl::StrCat("SymbolTerm(", name_, ")"); +} + +SymbolTerm* SymbolTerm::CloneImpl() const noexcept { + return new SymbolTerm(*this); +} + +void FormatStackElement(std::string* out, + std::shared_ptr term) noexcept { + out->append(term->Show()); +} + +void EvaluateAll(const Program& program, State& state) { + for (auto term : program) { + term->Evaluate(state); + } +} + +} // namespace ec diff --git a/src/language.h b/src/language.h new file mode 100644 index 0000000..75c191c --- /dev/null +++ b/src/language.h @@ -0,0 +1,230 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// The programming language implemented on the EC abstract machine. + +#ifndef EC_SRC_LANGUAGE_H_ +#define EC_SRC_LANGUAGE_H_ + +#include +#include +#include +#include +#include + +#include "src/error.h" +#include "third_party/abseil/absl/container/flat_hash_map.h" +#include "third_party/abseil/absl/strings/str_cat.h" +#include "third_party/abseil/absl/strings/string_view.h" + +namespace ec { + +class LanguageError : public Error { + public: + using Error::Error; +}; + +// The stack underflowed. +class StackUnderflow : public LanguageError { + public: + explicit StackUnderflow(absl::string_view op) + : LanguageError(absl::StrCat(op, ": too few arguments")) {} +}; + +// A lookup failed. +class UndefinedName : public LanguageError { + public: + explicit UndefinedName(absl::string_view name) + : LanguageError(absl::StrCat(name, ": undefined")) {} +}; + +// A function had a type error. +class TypeError : public LanguageError { + public: + using LanguageError::LanguageError; +}; + +class Term; + +// The EC abstract machine. The machine exclusively works with constant terms +// stored on the heap. This representation makes copying the machine state +// relatively cheap, which supports undo. +struct State { + // Initializes the machine to the "factory reset" state--an empty stack and an + // environment populated only by builtin operations. + State() noexcept; + + State(const State&) = default; + State& operator=(const State&) = default; + State(State&&) noexcept = default; + State& operator=(State&&) noexcept = default; + + std::vector> stack; // grows to the right + absl::flat_hash_map> environment; +}; + +// An abstract base class for language terms themselves. +class Term { + public: + virtual ~Term() = default; + + // Fully evaluates the term, mutating the state as necessary. + // + // This function is required only to provide the basic exception safety + // guarantee. You should thus save a copy of State before evaluation and + // restore it if an exception is thrown. This pushes some bookkeeping out to + // callers, but that probably already exists, since callers likely want to + // implement some form of undo feature. + virtual void Evaluate(State&) const = 0; + + std::shared_ptr Clone() const { + return std::shared_ptr(CloneImpl()); + } + + // Produces a human-readable representation of the term. This will be called + // to display it on the stack. + virtual std::string Show() const noexcept = 0; + + // Produces an engineer-readable representation of the term. This will be used + // in internal errors and for testing. + virtual std::string DebugString() const noexcept = 0; + + private: + // Duplicates the term onto the heap. + virtual Term* CloneImpl() const = 0; +}; + +inline std::ostream& operator<<(std::ostream& out, const Term& t) noexcept { + return out << t.DebugString(); +} + +// A self-evaluating term. Evaluating it pushes it. +class GroundTerm : public Term { + public: + // Convenience function to create a const GroundTerm on the heap. + static std::shared_ptr Make(double value) noexcept { + return std::make_shared(value); + } + + explicit GroundTerm(double value) noexcept : value_(value) {} + + GroundTerm(const GroundTerm&) noexcept = default; + GroundTerm& operator=(const GroundTerm&) noexcept = default; + GroundTerm(GroundTerm&&) noexcept = default; + GroundTerm& operator=(GroundTerm&&) noexcept = default; + + void Evaluate(State& state) const noexcept override; + + std::shared_ptr Clone() const noexcept { + return std::shared_ptr(CloneImpl()); + } + + std::string Show() const noexcept override; + + std::string DebugString() const noexcept override; + + bool operator==(const GroundTerm& other) const noexcept { + return value_ == other.value_; + } + + double value() const noexcept { return value_; } + + private: + GroundTerm* CloneImpl() const noexcept override; + + double value_; +}; + +// A term whose implementation is a C++ function. Evaluating it mutates the +// machine state by that function. +class ForeignProgramTerm : public Term { + public: + // Convenience function to create a const ForeignProgramTerm on the heap. + static std::shared_ptr Make( + void (*impl)(State&)) noexcept { + return std::make_shared(impl); + } + + explicit ForeignProgramTerm(void (*impl)(State&)) noexcept : impl_(impl) {} + + ForeignProgramTerm(const ForeignProgramTerm&) noexcept = default; + ForeignProgramTerm& operator=(const ForeignProgramTerm&) noexcept = default; + ForeignProgramTerm(ForeignProgramTerm&&) noexcept = default; + ForeignProgramTerm& operator=(ForeignProgramTerm&&) noexcept = default; + + void Evaluate(State&) const override; + + std::shared_ptr Clone() const noexcept { + return std::shared_ptr(CloneImpl()); + } + + std::string Show() const noexcept override; + + std::string DebugString() const noexcept override; + + private: + ForeignProgramTerm* CloneImpl() const noexcept override; + + void (*impl_)(State&); +}; + +// An identifier name. Evaluating it looks it up in the environment and pushes +// the result onto the stack. +class SymbolTerm : public Term { + public: + // Convenience function to create a const SymbolTerm on the heap. + static std::shared_ptr Make(std::string name) noexcept { + return std::make_shared(std::move(name)); + } + + explicit SymbolTerm(std::string name) noexcept : name_(std::move(name)) {} + + SymbolTerm(const SymbolTerm&) noexcept = default; + SymbolTerm& operator=(const SymbolTerm&) noexcept = default; + SymbolTerm(SymbolTerm&&) noexcept = default; + SymbolTerm& operator=(SymbolTerm&&) noexcept = default; + + void Evaluate(State&) const override; + + std::shared_ptr Clone() const noexcept { + return std::shared_ptr(CloneImpl()); + } + + std::string Show() const noexcept override; + + std::string DebugString() const noexcept override; + + bool operator==(const SymbolTerm& other) const noexcept { + return name_ == other.name_; + } + + private: + SymbolTerm* CloneImpl() const noexcept override; + + std::string name_; +}; + +// A convenience function for rendering stack elements. +void FormatStackElement(std::string*, std::shared_ptr) noexcept; + +// An EC program. +using Program = std::vector>; + +// A batch-mode evaluator for whole programs. Like Term::Evaluate, this function +// provides only the basic exception safety guarantee. +void EvaluateAll(const Program&, State&); + +} // namespace ec + +#endif // EC_SRC_LANGUAGE_H_ diff --git a/src/language_matchers.h b/src/language_matchers.h new file mode 100644 index 0000000..b230358 --- /dev/null +++ b/src/language_matchers.h @@ -0,0 +1,52 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// gMock matchers for Terms. + +#ifndef EC_SRC_LANGUAGE_MATCHERS_H_ +#define EC_SRC_LANGUAGE_MATCHERS_H_ + +#include + +#include "src/language.h" +#include "third_party/abseil/absl/strings/str_cat.h" + +namespace ec { + +MATCHER_P(PointsToGroundTerm, d, + absl::StrCat("points to GroundTerm(", d, ")")) { + using ::testing::DoubleEq; + using ::testing::Pointee; + using ::testing::Property; + using ::testing::WhenDynamicCastTo; + + return ExplainMatchResult(Pointee(WhenDynamicCastTo( + Property(&GroundTerm::value, DoubleEq(d)))), + arg, result_listener); +} + +MATCHER_P(PointsToSymbolTerm, s, + absl::StrCat("points to SymbolTerm(", s, ")")) { + using ::testing::Eq; + using ::testing::Pointee; + using ::testing::WhenDynamicCastTo; + + return ExplainMatchResult( + Pointee(WhenDynamicCastTo(Eq(SymbolTerm(s)))), arg, + result_listener); +} + +} // namespace ec + +#endif // EC_SRC_LANGUAGE_MATCHERS_H_ diff --git a/src/language_test.cc b/src/language_test.cc new file mode 100644 index 0000000..5add658 --- /dev/null +++ b/src/language_test.cc @@ -0,0 +1,76 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/language.h" + +#include +#include + +#include "src/language_matchers.h" +#include "third_party/abseil/absl/strings/str_cat.h" + +namespace ec { +namespace { + +using ::testing::ElementsAre; +using ::testing::IsEmpty; + +void PushFive(State& s) { s.stack.push_back(GroundTerm::Make(5)); } + +TEST(GroundTermTest, EvaluateMeansPushSelf) { + State s; + GroundTerm(42).Evaluate(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(42))); +} + +TEST(GroundTermTest, ShowsAsValue) { EXPECT_EQ(GroundTerm(42).Show(), "42"); } + +TEST(ForeignProgramTermTest, EvaluateCallsFunction) { + State s; + ForeignProgramTerm(PushFive).Evaluate(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(5))); +} + +TEST(ForeignProgramTermTest, ShowsAsOpaque) { + EXPECT_EQ(ForeignProgramTerm(PushFive).Show(), ""); +} + +TEST(SymbolTermTest, BadLookup) { + State s; + SymbolTerm t("push5"); + EXPECT_THROW(t.Evaluate(s), UndefinedName); +} + +TEST(SymbolTermTest, GoodLookup) { + State s; + s.environment["push5"] = ForeignProgramTerm::Make(PushFive); + SymbolTerm("push5").Evaluate(s); + EXPECT_THAT(s.stack, ElementsAre(PointsToGroundTerm(5))); +} + +TEST(EvaluateAllTest, EvaluatesNothing) { + State s; + EvaluateAll({}, s); + EXPECT_THAT(s.stack, IsEmpty()); +} + +TEST(EvaluateAllTest, EvaluatesMultiple) { + State s; + EvaluateAll({GroundTerm::Make(42), ForeignProgramTerm::Make(PushFive)}, s); + EXPECT_THAT(s.stack, + ElementsAre(PointsToGroundTerm(42), PointsToGroundTerm(5))); +} + +} // namespace +} // namespace ec diff --git a/src/main.cc b/src/main.cc new file mode 100644 index 0000000..959cda0 --- /dev/null +++ b/src/main.cc @@ -0,0 +1,117 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include +#include +#include + +#include +#include +#include + +#include "src/ui/stream.h" +#include "src/ui/terminal.h" +#include "src/util.h" +#include "third_party/abseil/absl/strings/string_view.h" + +namespace { + +constexpr absl::string_view kShortUsage = "Usage: ec [OPTION...] [FILENAME]\n"; + +constexpr absl::string_view kHelp = + R"( +A Reverse Polish scientific calculator. Invoked directly, ec launches an +interactive interpreter that displays the stack and accepts input. Invoked on a +file, ec processes the entire file; if the result stack is nonempty, ec prints +the stack in space-separated form. + +Options: + --help display this help and exit + --version display version information and exit +)"; + +constexpr absl::string_view kAskForHelp = + "Try 'ec --help' for more information.\n"; + +constexpr absl::string_view kVersionInfo = "ec development build\n"; + +enum { + kHelpLongOption = 128, + kVersionLongOption = 129, +}; + +int TerminalUi() { + if (isatty(STDIN_FILENO) && isatty(STDOUT_FILENO)) { + return ec::TerminalUi().Main(); + } else { + return ec::LineUi().Main(); + } +} + +int ProcessFile(const char* path) { + std::ifstream file(path); + if (!file.is_open()) { + std::cerr << "ec: failed to open file " << path << '\n'; + return 1; + } + return ec::StreamUi(file).Main(); +} + +} // namespace + +int main(int argc, char* argv[]) { + setlocale(LC_ALL, ""); + + static option long_options[] = { + {"help", no_argument, nullptr, kHelpLongOption}, + {"version", no_argument, nullptr, kVersionLongOption}, + {nullptr, 0, nullptr, 0}, + }; + while (true) { + int c = getopt_long(argc, argv, "", long_options, /*longindex=*/nullptr); + if (c == -1) { + break; + } + switch (c) { + case kHelpLongOption: + std::cout << kShortUsage << kHelp; + return 0; + case kVersionLongOption: + std::cout << kVersionInfo; + return 0; + case '?': + std::cerr << kAskForHelp; + return 1; + default: + std::cerr << "ec: internal error: unhandled getopt switch\nThis is a " + "bug! Please report it.\n"; + return 1; + } + } + + try { + if (optind == argc) { + TerminalUi(); + } else if (optind == argc - 1) { + return ProcessFile(argv[optind]); + } else { + std::cerr << kShortUsage << kAskForHelp; + return 1; + } + } catch (const std::exception& e) { + std::cerr << "ec: internal error: " << DemangleIfPossible(typeid(e).name()) + << ": " << e.what() << "\nThis is a bug! Please report it.\n"; + return 1; + } +} diff --git a/src/parser_driver.cc b/src/parser_driver.cc new file mode 100644 index 0000000..60e59ab --- /dev/null +++ b/src/parser_driver.cc @@ -0,0 +1,71 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/parser_driver.h" + +#include + +#include +#include + +#include "src/CalculatorBaseVisitor.h" +#include "src/CalculatorLexer.h" +#include "src/CalculatorParser.h" +#include "src/language.h" +#include "third_party/abseil/absl/strings/string_view.h" + +namespace ec { + +namespace { + +template +std::shared_ptr MakeTerm(Args... args) { + return std::static_pointer_cast(std::make_shared(args...)); +} + +class Visitor : public CalculatorBaseVisitor { + public: + antlrcpp::Any visitProgram(CalculatorParser::ProgramContext* ctx) override { + Program p; + for (CalculatorParser::TermContext* term : ctx->term()) { + p.push_back(visit(term)); + } + return p; + } + + antlrcpp::Any visitNumber(CalculatorParser::NumberContext* ctx) override { + return MakeTerm(ctx->value); + } + + antlrcpp::Any visitIdentifier( + CalculatorParser::IdentifierContext* ctx) override { + return MakeTerm(ctx->value); + } + + antlrcpp::Any visitError(CalculatorParser::ErrorContext*) override { + throw ParseError(); + } +}; + +} // namespace + +Program ParseFromString(absl::string_view text) { + antlr4::ANTLRInputStream input(text.data(), text.size()); + CalculatorLexer lexer(&input); + antlr4::CommonTokenStream tokens(&lexer); + CalculatorParser parser(&tokens); + return Visitor().visit(parser.program()); +} + +} // namespace ec diff --git a/src/parser_driver.h b/src/parser_driver.h new file mode 100644 index 0000000..12a65cf --- /dev/null +++ b/src/parser_driver.h @@ -0,0 +1,39 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// A driver for the Antlr-generated EC parser. + +#ifndef EC_SRC_PARSER_DRIVER_H_ +#define EC_SRC_PARSER_DRIVER_H_ + +#include +#include + +#include "src/error.h" +#include "src/language.h" +#include "third_party/abseil/absl/strings/string_view.h" + +namespace ec { + +class ParseError : public Error { + public: + explicit ParseError() : Error("parse error") {} +}; + +// Converts a bare string to an EC program. +Program ParseFromString(absl::string_view); + +} // namespace ec + +#endif // EC_SRC_PARSER_DRIVER_H_ diff --git a/src/parser_driver_test.cc b/src/parser_driver_test.cc new file mode 100644 index 0000000..69803df --- /dev/null +++ b/src/parser_driver_test.cc @@ -0,0 +1,53 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/parser_driver.h" + +#include +#include + +#include "src/language.h" +#include "src/language_matchers.h" + +namespace ec { +namespace { + +using ::testing::ElementsAre; +using ::testing::IsEmpty; + +TEST(ParserDriverTest, LexerError) { + EXPECT_THROW(ParseFromString("!!!"), ParseError); +} + +TEST(ParserDriverTest, EmptyProgram) { + EXPECT_THAT(ParseFromString(""), IsEmpty()); +} + +TEST(ParserDriverTest, ConvertsNumber) { + EXPECT_THAT(ParseFromString("12321"), ElementsAre(PointsToGroundTerm(12321))); +} + +TEST(ParserDriverTest, ConvertsIdentifier) { + EXPECT_THAT(ParseFromString("dup"), ElementsAre(PointsToSymbolTerm("dup"))); +} + +TEST(ParserDriverTest, ParsesMultipleTerms) { + EXPECT_THAT(ParseFromString("2 2 + 4 /"), + ElementsAre(PointsToGroundTerm(2), PointsToGroundTerm(2), + PointsToSymbolTerm("add"), PointsToGroundTerm(4), + PointsToSymbolTerm("div"))); +} + +} // namespace +} // namespace ec diff --git a/src/ui.h b/src/ui.h new file mode 100644 index 0000000..9f13bd2 --- /dev/null +++ b/src/ui.h @@ -0,0 +1,30 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#ifndef EC_SRC_UI_H_ +#define EC_SRC_UI_H_ + +namespace ec { + +// A UI for EC. +class Ui { + public: + virtual ~Ui() = default; + + virtual int Main() noexcept = 0; +}; + +} // namespace ec + +#endif // EC_SRC_UI_H_ diff --git a/src/ui/stream.cc b/src/ui/stream.cc new file mode 100644 index 0000000..74e34be --- /dev/null +++ b/src/ui/stream.cc @@ -0,0 +1,84 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/ui/stream.h" + +#include + +#include +#include +#include +#include + +#include "src/error.h" +#include "src/language.h" +#include "src/parser_driver.h" +#include "third_party/abseil/absl/strings/str_join.h" + +namespace ec { + +namespace { + +std::string ReadAll(std::istream& in) noexcept { + std::string result; + int bytes_read = 0; + while (in.good()) { + result.append(4096, '\0'); + in.read(result.data() + bytes_read, 4096); + bytes_read += in.gcount(); + } + assert(bytes_read <= result.size()); + result.resize(bytes_read); + return result; +} + +void ShowState(const State& state, std::ostream& out) noexcept { + if (state.stack.empty()) { + return; + } + out << absl::StrJoin(state.stack, " ", FormatStackElement) << '\n'; +} + +} // namespace + +int LineUi::Main() noexcept { + State state; + while (in_.good()) { + std::string line; + std::getline(in_, line); + try { + EvaluateAll(ParseFromString(line), state); + } catch (const Error& e) { + std::cerr << "ec: " << e.what() << '\n'; + return 1; + } + } + ShowState(state, out_); + return 0; +} + +int StreamUi::Main() noexcept { + State state; + std::string program = ReadAll(in_); + try { + EvaluateAll(ParseFromString(program), state); + } catch (const Error& e) { + std::cerr << "ec: " << e.what() << '\n'; + return 1; + } + ShowState(state, out_); + return 0; +} + +} // namespace ec diff --git a/src/ui/stream.h b/src/ui/stream.h new file mode 100644 index 0000000..106560b --- /dev/null +++ b/src/ui/stream.h @@ -0,0 +1,56 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// Stream-oriented interfaces to EC. + +#ifndef EC_SRC_UI_STREAM_H_ +#define EC_SRC_UI_STREAM_H_ + +#include +#include +#include + +#include "src/ui.h" + +namespace ec { + +// A line-mode interpreter working on streams. +class LineUi : public Ui { + public: + explicit LineUi(std::istream& in = std::cin, std::ostream& out = std::cout) + : in_(in), out_(out) {} + + int Main() noexcept override; + + private: + std::istream& in_; + std::ostream& out_; +}; + +// A batch-mode interpreter working on streams. +class StreamUi : public Ui { + public: + explicit StreamUi(std::istream& in = std::cin, std::ostream& out = std::cout) + : in_(in), out_(out) {} + + int Main() noexcept override; + + private: + std::istream& in_; + std::ostream& out_; +}; + +} // namespace ec + +#endif // EC_SRC_UI_STREAM_H_ diff --git a/src/ui/terminal.cc b/src/ui/terminal.cc new file mode 100644 index 0000000..ccb9c4d --- /dev/null +++ b/src/ui/terminal.cc @@ -0,0 +1,184 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/ui/terminal.h" + +#include +#include +#include + +#include "src/builtin.h" +#include "src/error.h" +#include "src/language.h" +#include "src/parser_driver.h" +#include "src/ui/terminal/line.h" +#include "third_party/abseil/absl/strings/str_cat.h" +#include "third_party/abseil/absl/strings/str_join.h" +#include "third_party/abseil/absl/strings/string_view.h" + +namespace ec { + +int TerminalUi::Main() noexcept { + BlockSigwinch(); + TerminalLine tty; + + State machine_state; + std::string input_buffer; + while (true) { + tty.SetLineImmediately(absl::StrCat( + absl::StrJoin(machine_state.stack, " ", FormatStackElement), " > ", + input_buffer)); + + char c = tty.GetChar(); + if (c == tty.interrupt_char() || c == tty.quit_char()) { + // Somebody hit Ctrl-C or Ctrl-\. + return 0; + } + switch (c) { + case kControlD: + if (input_buffer.empty()) { + return 0; + } + tty.Beep(); + break; + + case kControlU: + input_buffer.clear(); + break; + + case '\n': + case '\r': + case ' ': + try { + std::vector> program; + if (input_buffer.empty()) { + program = {std::make_shared(BuiltinDup)}; + } else { + program = ParseFromString(input_buffer); + } + + State s = machine_state; + EvaluateAll(program, s); + machine_state = s; + input_buffer.clear(); + } catch (const Error& e) { + tty.Beep(); + } + break; + + case '\x7f': + try { + if (input_buffer.empty()) { + State s = machine_state; + ForeignProgramTerm(BuiltinDrop).Evaluate(s); + machine_state = s; + } else { + input_buffer.pop_back(); + } + } catch (const Error& e) { + tty.Beep(); + } + break; + + case '+': + case '-': + case '*': + case '/': + try { + std::vector> program = + ParseFromString(absl::StrCat(input_buffer, std::string(1, c))); + State s = machine_state; + EvaluateAll(program, s); + machine_state = s; + input_buffer.clear(); + } catch (const Error& e) { + tty.Beep(); + } + break; + + case '.': + case '0': + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + case 'A': + case 'B': + case 'C': + case 'D': + case 'E': + case 'F': + case 'G': + case 'H': + case 'I': + case 'J': + case 'K': + case 'L': + case 'M': + case 'N': + case 'O': + case 'P': + case 'Q': + case 'R': + case 'S': + case 'T': + case 'U': + case 'V': + case 'W': + case 'X': + case 'Y': + case 'Z': + case '_': + case 'a': + case 'b': + case 'c': + case 'd': + case 'e': + case 'f': + case 'g': + case 'h': + case 'i': + case 'j': + case 'k': + case 'l': + case 'm': + case 'n': + case 'o': + case 'p': + case 'q': + case 'r': + case 's': + case 't': + case 'u': + case 'v': + case 'w': + case 'x': + case 'y': + case 'z': + input_buffer.push_back(c); + break; + + default: + tty.Beep(); + break; + } + } +} + +} // namespace ec diff --git a/src/ui/terminal.h b/src/ui/terminal.h new file mode 100644 index 0000000..22f5d01 --- /dev/null +++ b/src/ui/terminal.h @@ -0,0 +1,35 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#ifndef EC_SRC_UI_TERMINAL_H_ +#define EC_SRC_UI_TERMINAL_H_ + +#include "src/ui.h" + +namespace ec { + +// An interactive interpreter targeted at terminal sessions. +class TerminalUi : public Ui { + public: + explicit TerminalUi() = default; + + TerminalUi(const TerminalUi&) = delete; + TerminalUi& operator=(const TerminalUi&) = delete; + + int Main() noexcept override; +}; + +} // namespace ec + +#endif // EC_SRC_UI_TERMINAL_H_ diff --git a/src/ui/terminal/line.cc b/src/ui/terminal/line.cc new file mode 100644 index 0000000..8f156cb --- /dev/null +++ b/src/ui/terminal/line.cc @@ -0,0 +1,206 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/ui/terminal/line.h" + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#include "third_party/abseil/absl/strings/str_cat.h" +#include "third_party/abseil/absl/strings/string_view.h" +#include "third_party/abseil/absl/synchronization/mutex.h" + +namespace ec { + +namespace { + +constexpr absl::string_view kBeginningOfLine = "\r"; + +int CheckedCall(const char* what_arg, int r) { + if (r < 0) { + throw std::system_error(errno, std::generic_category(), what_arg); + } + return r; +} + +bool SigwinchBlocked() { + sigset_t current_blocked; + CheckedCall("pthread_sigmask", + pthread_sigmask(/*how=*/0, /*set=*/nullptr, ¤t_blocked)); + return CheckedCall("sigismember", sigismember(¤t_blocked, SIGWINCH)); +} + +sigset_t SigsetContaining(int signal) { + sigset_t set; + sigemptyset(&set); + CheckedCall("sigaddset", sigaddset(&set, signal)); + return set; +} + +int TerminalColumns() { + winsize size; + CheckedCall("ioctl", ioctl(STDOUT_FILENO, TIOCGWINSZ, &size)); + return size.ws_col; +} + +absl::string_view ClearToEol() noexcept { + static const std::string kSequence = + absl::StrCat("\x1b[K", std::string(3, '\0') /* VT100 padding */); + return kSequence; +} + +} // namespace + +TerminalLine::TerminalLine() { + if (!SigwinchBlocked()) { + throw std::logic_error("TerminalLine constructed without SIGWINCH blocked"); + } + + EnterRawMode(); + + sigwinch_watcher_ = std::thread([this] { + sigset_t sigwinch = SigsetContaining(SIGWINCH); + int received; + while (true) { + sigwait(&sigwinch, &received); + ReportSigwinch(); + } + }); + ReportSigwinch(); // initialize state reset on SIGWINCH +} + +TerminalLine::~TerminalLine() noexcept { + static_assert(std::is_same_v); + pthread_cancel(sigwinch_watcher_.native_handle()); + sigwinch_watcher_.join(); + + ExitRawMode(); + + // Move the cursor to the start of the next line. + std::cout << '\n'; +} + +void TerminalLine::SetLine(std::string text) { + absl::MutexLock lock(&mu_); + line_ = std::move(text); +} + +void TerminalLine::Refresh() { + absl::MutexLock lock(&mu_); + if (line_.size() < columns_) { + // We can fit the whole line and the cursor on the screen at once. + WriteRaw(absl::StrCat(kBeginningOfLine, line_, ClearToEol())); + } else { + auto to_display = std::min(line_.size(), columns_ - 4); + WriteRaw( + absl::StrCat(kBeginningOfLine, "...", + absl::string_view(&*line_.end() - to_display, to_display), + ClearToEol())); + } +} + +char TerminalLine::GetChar() { + while (true) { + char c; + int r = read(STDIN_FILENO, &c, 1); + if (r > 0) { + return c; + } else if (r == 0) { // EOF + return kControlD; + } else if (errno == EINTR) { + continue; + } else { + throw std::system_error(errno, std::generic_category(), "read"); + } + } +} + +void TerminalLine::Beep() { + absl::MutexLock lock(&mu_); + WriteRaw("\a"); +} + +void TerminalLine::PrintLine(absl::string_view message) { + { + absl::MutexLock lock(&mu_); + WriteRaw(absl::StrCat("\r\n", message, "\r\n")); + } + Refresh(); +} + +void TerminalLine::EnterRawMode() { + CheckedCall("tcgetattr", tcgetattr(STDIN_FILENO, &original_termios_)); + + current_termios_ = original_termios_; + current_termios_.c_iflag &= ~(BRKINT | ICRNL | INPCK | ISTRIP | IXON); + current_termios_.c_oflag &= ~(OPOST); + current_termios_.c_cflag |= CS8; + current_termios_.c_lflag &= ~(ECHO | ICANON | IEXTEN | ISIG); + CheckedCall("tcsetattr", + tcsetattr(STDIN_FILENO, TCSAFLUSH, ¤t_termios_)); + + // tcsetattr returns successfully if _any_ of its changes were successful, so + // check again to make sure everything went through. + termios actual; + CheckedCall("tcgetattr", tcgetattr(STDIN_FILENO, &actual)); + if (actual.c_iflag & (BRKINT | ICRNL | INPCK | ISTRIP | IXON) || + actual.c_oflag & OPOST || (actual.c_cflag & CS8) != CS8 || + actual.c_lflag & (ECHO | ICANON | IEXTEN | ISIG)) { + throw std::runtime_error("tcsetattr: could not apply all settings"); + } +} + +void TerminalLine::ExitRawMode() noexcept { + tcsetattr(STDIN_FILENO, TCSAFLUSH, &original_termios_); +} + +void TerminalLine::ReportSigwinch() { + { + absl::MutexLock lock(&mu_); + columns_ = TerminalColumns(); + } + Refresh(); +} + +void TerminalLine::WriteRaw(absl::string_view bytes) { + while (true) { + int r = write(STDOUT_FILENO, bytes.data(), bytes.size()); + if (r >= 0) { + return; + } else if (errno == EINTR) { + continue; + } else { + throw std::system_error(errno, std::generic_category(), "write"); + } + } +} + +void BlockSigwinch() { + sigset_t sigwinch = SigsetContaining(SIGWINCH); + CheckedCall("pthread_sigmask", + pthread_sigmask(SIG_BLOCK, &sigwinch, /*oldset=*/nullptr)); +} + +} // namespace ec diff --git a/src/ui/terminal/line.h b/src/ui/terminal/line.h new file mode 100644 index 0000000..a90e2b7 --- /dev/null +++ b/src/ui/terminal/line.h @@ -0,0 +1,101 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +// A terminal driver for single-line UIs. + +#ifndef EC_SRC_UI_TERMINAL_LINE_H_ +#define EC_SRC_UI_TERMINAL_LINE_H_ + +#include + +#include + +#include "third_party/abseil/absl/base/thread_annotations.h" +#include "third_party/abseil/absl/strings/string_view.h" +#include "third_party/abseil/absl/synchronization/mutex.h" + +namespace ec { + +// The driver itself. +// +// This class is thread-safe, but there are still some sharp edges. See the +// warning in the constructor documentation about additional steps required to +// use this class in a multi-threaded program. +class TerminalLine final { + public: + // Starts driving the standard input and standard output of the process. + // + // Multi-threading warning: You must block SIGWINCH in all your program's + // threads before constructing an instance of this class. This class detects + // failure to block SIGWINCH in the calling thread, but it cannot check all + // the threads. It is your responsibility to block SIGWINCH everywhere! + // (BlockSigwinch is a convenience function to do this in the current thread.) + explicit TerminalLine(); + + TerminalLine(const TerminalLine&) = delete; + TerminalLine& operator=(const TerminalLine&) = delete; + + ~TerminalLine() noexcept; + + void SetLine(std::string) ABSL_LOCKS_EXCLUDED(mu_); + void Refresh() ABSL_LOCKS_EXCLUDED(mu_); + + void SetLineImmediately(std::string text) { + SetLine(text); + Refresh(); + } + + char GetChar(); + char interrupt_char() const noexcept { return current_termios_.c_cc[VINTR]; } + char quit_char() const noexcept { return current_termios_.c_cc[VQUIT]; } + char suspend_char() const noexcept { return current_termios_.c_cc[VSUSP]; } +#ifdef VDSUSP + char delayed_suspend_char() const noexcept { + return current_termios_.c_cc[VDSUSP]; + } +#endif + + void Beep() ABSL_LOCKS_EXCLUDED(mu_); + + // Prints the specified message on a new line, and redisplays the original + // text on the line after that. + void PrintLine(absl::string_view) ABSL_LOCKS_EXCLUDED(mu_); + + private: + void EnterRawMode(); + void ExitRawMode() noexcept; + + void ReportSigwinch() ABSL_LOCKS_EXCLUDED(mu_); + + void WriteRaw(absl::string_view bytes) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mu_); + + termios original_termios_, current_termios_; + + std::thread sigwinch_watcher_; + + absl::Mutex mu_; + int columns_ ABSL_GUARDED_BY(mu_); + std::string line_ ABSL_GUARDED_BY(mu_); +}; + +// Names for control characters. +constexpr char kControlD = '\x04'; +constexpr char kControlU = '\x15'; + +// A convenience function to block SIGWINCH in the calling thread. +void BlockSigwinch(); + +} // namespace ec + +#endif // EC_SRC_UI_TERMINAL_LINE_H_ diff --git a/src/util.cc b/src/util.cc new file mode 100644 index 0000000..ef9cdef --- /dev/null +++ b/src/util.cc @@ -0,0 +1,32 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#include "src/util.h" + +#include +#include + +#include + +std::string DemangleIfPossible(const char* name) noexcept { + int status; + char* demangled_raw = abi::__cxa_demangle(name, /*output_buffer=*/nullptr, + /*length=*/0, &status); + std::string demangled; + if (demangled_raw != nullptr) { + demangled = std::string(demangled_raw); + } + free(demangled_raw); + return demangled; +} diff --git a/src/util.h b/src/util.h new file mode 100644 index 0000000..885986a --- /dev/null +++ b/src/util.h @@ -0,0 +1,24 @@ +// Copyright 2021 Benjamin Barenblat +// +// Licensed under the Apache License, Version 2.0 (the "License"); you may not +// use this file except in compliance with the License. You may obtain a copy of +// the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +// License for the specific language governing permissions and limitations under +// the License. + +#ifndef EC_SRC_UTIL_H_ +#define EC_SRC_UTIL_H_ + +#include + +// Attempts to demangle the specified name according to the current ABI. Returns +// the demangled name if successful, otherwise the mangled name. +std::string DemangleIfPossible(const char* name) noexcept; + +#endif // EC_SRC_UTIL_H_ diff --git a/third_party/abseil b/third_party/abseil new file mode 160000 index 0000000..385b5cc --- /dev/null +++ b/third_party/abseil @@ -0,0 +1 @@ +Subproject commit 385b5ccafdabf0ca91797ae3caa755ab7451c45d -- cgit v1.2.3