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 --- 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 ++++ 22 files changed, 2101 insertions(+) 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 (limited to 'src') 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_ -- cgit v1.2.3