jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, the SerenityOS developers.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/Assertions.h>
8#include <AK/DeprecatedString.h>
9#include <AK/GenericLexer.h>
10#include <AK/NonnullOwnPtr.h>
11#include <AK/OwnPtr.h>
12#include <AK/Queue.h>
13#include <AK/StringView.h>
14#include <LibCore/System.h>
15#include <LibMain/Main.h>
16#include <LibRegex/Regex.h>
17#include <stdio.h>
18#include <unistd.h>
19
20static void print_help_and_exit()
21{
22 outln(R"(
23Usage: expr EXPRESSION
24 expr [--help]
25
26Print the value of EXPRESSION to standard output.)");
27 exit(0);
28}
29
30template<typename Fmt, typename... Args>
31[[noreturn]] void fail(Fmt&& fmt, Args&&... args)
32{
33 warn("ERROR: \e[31m");
34 warnln(StringView { fmt, strlen(fmt) }, args...);
35 warn("\e[0m");
36 exit(2);
37}
38
39class Expression {
40public:
41 enum Precedence {
42 Or,
43 And,
44 Comp,
45 ArithS,
46 ArithM,
47 StringO,
48 Paren,
49 };
50 static NonnullOwnPtr<Expression> parse(Queue<StringView>& args, Precedence prec = Or);
51
52 enum class Type {
53 Integer,
54 String,
55 };
56
57 virtual bool truth() const = 0;
58 virtual int integer() const = 0;
59 virtual DeprecatedString string() const = 0;
60 virtual Type type() const = 0;
61 virtual ~Expression() = default;
62};
63
64class ValueExpression : public Expression {
65public:
66 ValueExpression(int v)
67 : as_integer(v)
68 , m_type(Type::Integer)
69 {
70 }
71
72 ValueExpression(DeprecatedString&& v)
73 : as_string(move(v))
74 , m_type(Type::String)
75 {
76 }
77
78 virtual ~ValueExpression() {};
79
80private:
81 virtual bool truth() const override
82 {
83 if (m_type == Type::String)
84 return !as_string.is_empty();
85 return integer() != 0;
86 }
87 virtual int integer() const override
88 {
89 switch (m_type) {
90 case Type::Integer:
91 return as_integer;
92 case Type::String:
93 if (auto converted = as_string.to_int(); converted.has_value())
94 return converted.value();
95 fail("Not an integer: '{}'", as_string);
96 }
97 VERIFY_NOT_REACHED();
98 }
99 virtual DeprecatedString string() const override
100 {
101 switch (m_type) {
102 case Type::Integer:
103 return DeprecatedString::formatted("{}", as_integer);
104 case Type::String:
105 return as_string;
106 }
107 VERIFY_NOT_REACHED();
108 }
109 virtual Type type() const override { return m_type; }
110
111 union {
112 int as_integer;
113 DeprecatedString as_string;
114 };
115 Type m_type { Type::String };
116};
117
118class BooleanExpression : public Expression {
119public:
120 enum class BooleanOperator {
121 And,
122 Or,
123 };
124 static BooleanOperator op_from(StringView sv)
125 {
126 if (sv == "&")
127 return BooleanOperator::And;
128 return BooleanOperator::Or;
129 }
130 BooleanExpression(BooleanOperator op, NonnullOwnPtr<Expression>&& left, NonnullOwnPtr<Expression>&& right)
131 : m_op(op)
132 , m_left(move(left))
133 , m_right(move(right))
134 {
135 if (m_op == BooleanOperator::Or)
136 m_left_truth = m_left->truth();
137 else
138 m_right_truth = m_right->truth();
139 }
140
141private:
142 virtual bool truth() const override
143 {
144 if (m_op == BooleanOperator::Or)
145 return m_left_truth ? true : m_right->truth();
146 return m_right_truth ? m_left->truth() : false;
147 }
148
149 virtual int integer() const override
150 {
151 switch (m_op) {
152 case BooleanOperator::And:
153 if (m_right_truth)
154 return m_left->integer();
155 return 0;
156 case BooleanOperator::Or:
157 if (m_left_truth)
158 return m_left->integer();
159 return m_right->integer();
160 }
161 VERIFY_NOT_REACHED();
162 }
163
164 virtual DeprecatedString string() const override
165 {
166 switch (m_op) {
167 case BooleanOperator::And:
168 if (m_right_truth)
169 return m_left->string();
170 return "0";
171 case BooleanOperator::Or:
172 if (m_left_truth)
173 return m_left->string();
174 return m_right->string();
175 }
176 VERIFY_NOT_REACHED();
177 }
178 virtual Type type() const override
179 {
180 switch (m_op) {
181 case BooleanOperator::And:
182 if (m_right_truth)
183 return m_left->type();
184 return m_right->type();
185 case BooleanOperator::Or:
186 if (m_left_truth)
187 return m_left->type();
188 return m_right->type();
189 }
190 VERIFY_NOT_REACHED();
191 }
192
193 BooleanOperator m_op { BooleanOperator::And };
194 NonnullOwnPtr<Expression> m_left, m_right;
195 bool m_left_truth { false }, m_right_truth { false };
196};
197
198class ComparisonExpression : public Expression {
199public:
200 enum class ComparisonOperation {
201 Less,
202 LessEq,
203 Eq,
204 Neq,
205 GreaterEq,
206 Greater,
207 };
208
209 static ComparisonOperation op_from(StringView sv)
210 {
211 if (sv == "<"sv)
212 return ComparisonOperation::Less;
213 if (sv == "<="sv)
214 return ComparisonOperation::LessEq;
215 if (sv == "="sv)
216 return ComparisonOperation::Eq;
217 if (sv == "!="sv)
218 return ComparisonOperation::Neq;
219 if (sv == ">="sv)
220 return ComparisonOperation::GreaterEq;
221 return ComparisonOperation::Greater;
222 }
223
224 ComparisonExpression(ComparisonOperation op, NonnullOwnPtr<Expression>&& left, NonnullOwnPtr<Expression>&& right)
225 : m_op(op)
226 , m_left(move(left))
227 , m_right(move(right))
228 {
229 }
230
231private:
232 template<typename T>
233 bool compare(T const& left, T const& right) const
234 {
235 switch (m_op) {
236 case ComparisonOperation::Less:
237 return left < right;
238 case ComparisonOperation::LessEq:
239 return left == right || left < right;
240 case ComparisonOperation::Eq:
241 return left == right;
242 case ComparisonOperation::Neq:
243 return left != right;
244 case ComparisonOperation::GreaterEq:
245 return !(left < right);
246 case ComparisonOperation::Greater:
247 return left != right && !(left < right);
248 }
249 VERIFY_NOT_REACHED();
250 }
251
252 virtual bool truth() const override
253 {
254 switch (m_left->type()) {
255 case Type::Integer:
256 return compare(m_left->integer(), m_right->integer());
257 case Type::String:
258 return compare(m_left->string(), m_right->string());
259 }
260 VERIFY_NOT_REACHED();
261 }
262 virtual int integer() const override { return truth(); }
263 virtual DeprecatedString string() const override { return truth() ? "1" : "0"; }
264 virtual Type type() const override { return Type::Integer; }
265
266 ComparisonOperation m_op { ComparisonOperation::Less };
267 NonnullOwnPtr<Expression> m_left, m_right;
268};
269
270class ArithmeticExpression : public Expression {
271public:
272 enum class ArithmeticOperation {
273 Sum,
274 Difference,
275 Product,
276 Quotient,
277 Remainder,
278 };
279 static ArithmeticOperation op_from(StringView sv)
280 {
281 if (sv == "+"sv)
282 return ArithmeticOperation::Sum;
283 if (sv == "-"sv)
284 return ArithmeticOperation::Difference;
285 if (sv == "*"sv)
286 return ArithmeticOperation::Product;
287 if (sv == "/"sv)
288 return ArithmeticOperation::Quotient;
289 return ArithmeticOperation::Remainder;
290 }
291 ArithmeticExpression(ArithmeticOperation op, NonnullOwnPtr<Expression>&& left, NonnullOwnPtr<Expression>&& right)
292 : m_op(op)
293 , m_left(move(left))
294 , m_right(move(right))
295 {
296 }
297
298private:
299 virtual bool truth() const override
300 {
301 switch (m_op) {
302 case ArithmeticOperation::Sum:
303 return m_left->truth() || m_right->truth();
304 default:
305 return integer() != 0;
306 }
307 }
308 virtual int integer() const override
309 {
310 auto right = m_right->integer();
311 if (right == 0) {
312 if (m_op == ArithmeticOperation::Product)
313 return 0;
314 if (m_op == ArithmeticOperation::Quotient || m_op == ArithmeticOperation::Remainder)
315 fail("Division by zero");
316 }
317
318 auto left = m_left->integer();
319 switch (m_op) {
320 case ArithmeticOperation::Product:
321 return right * left;
322 case ArithmeticOperation::Sum:
323 return right + left;
324 case ArithmeticOperation::Difference:
325 return left - right;
326 case ArithmeticOperation::Quotient:
327 return left / right;
328 case ArithmeticOperation::Remainder:
329 return left % right;
330 }
331 VERIFY_NOT_REACHED();
332 }
333 virtual DeprecatedString string() const override
334 {
335 return DeprecatedString::formatted("{}", integer());
336 }
337 virtual Type type() const override
338 {
339 return Type::Integer;
340 }
341
342 ArithmeticOperation m_op { ArithmeticOperation::Sum };
343 NonnullOwnPtr<Expression> m_left, m_right;
344};
345
346class StringExpression : public Expression {
347public:
348 enum class StringOperation {
349 Substring,
350 Index,
351 Length,
352 Match,
353 };
354
355 StringExpression(StringOperation op, NonnullOwnPtr<Expression> string, OwnPtr<Expression> pos_or_chars = {}, OwnPtr<Expression> length = {})
356 : m_op(op)
357 , m_str(move(string))
358 , m_pos_or_chars(move(pos_or_chars))
359 , m_length(move(length))
360 {
361 }
362
363private:
364 virtual bool truth() const override
365 {
366 if (type() == Expression::Type::String)
367 return !string().is_empty();
368 return integer() != 0;
369 }
370 virtual int integer() const override
371 {
372 if (m_op == StringOperation::Substring || m_op == StringOperation::Match) {
373 auto substr = string();
374 if (auto integer = substr.to_int(); integer.has_value())
375 return integer.value();
376 else
377 fail("Not an integer: '{}'", substr);
378 }
379
380 if (m_op == StringOperation::Index) {
381 if (auto idx = m_str->string().find(m_pos_or_chars->string()); idx.has_value())
382 return idx.value() + 1;
383 return 0;
384 }
385
386 if (m_op == StringOperation::Length)
387 return m_str->string().length();
388
389 VERIFY_NOT_REACHED();
390 }
391 static auto safe_substring(DeprecatedString const& str, int start, int length)
392 {
393 if (start < 1 || (size_t)start > str.length())
394 fail("Index out of range");
395 --start;
396 if (str.length() - start < (size_t)length)
397 fail("Index out of range");
398 return str.substring(start, length);
399 }
400 virtual DeprecatedString string() const override
401 {
402 if (m_op == StringOperation::Substring)
403 return safe_substring(m_str->string(), m_pos_or_chars->integer(), m_length->integer());
404
405 if (m_op == StringOperation::Match) {
406 auto match = m_compiled_regex->match(m_str->string(), PosixFlags::Global);
407 if (m_compiled_regex->parser_result.capture_groups_count == 0) {
408 if (!match.success)
409 return "0";
410
411 size_t count = 0;
412 for (auto& m : match.matches)
413 count += m.view.length();
414
415 return DeprecatedString::number(count);
416 } else {
417 if (!match.success)
418 return "";
419
420 StringBuilder result;
421 for (auto& e : match.capture_group_matches[0])
422 result.append(e.view.string_view());
423
424 return result.to_deprecated_string();
425 }
426 }
427
428 return DeprecatedString::number(integer());
429 }
430 virtual Type type() const override
431 {
432 if (m_op == StringOperation::Substring)
433 return Type::String;
434 if (m_op == StringOperation::Match) {
435 if (!m_pos_or_chars)
436 fail("'match' expects a string pattern");
437
438 ensure_regex();
439 if (m_compiled_regex->parser_result.capture_groups_count == 0)
440 return Type::Integer;
441
442 return Type::String;
443 }
444 return Type::Integer;
445 }
446
447 void ensure_regex() const
448 {
449 if (!m_compiled_regex) {
450 m_compiled_regex = make<regex::Regex<PosixBasic>>(m_pos_or_chars->string());
451 if (m_compiled_regex->parser_result.error != regex::Error::NoError)
452 fail("Regex error: {}", regex::get_error_string(m_compiled_regex->parser_result.error));
453 }
454 }
455
456 StringOperation m_op { StringOperation::Substring };
457 NonnullOwnPtr<Expression> m_str;
458 OwnPtr<Expression> m_pos_or_chars, m_length;
459 mutable OwnPtr<regex::Regex<PosixBasic>> m_compiled_regex;
460};
461
462NonnullOwnPtr<Expression> Expression::parse(Queue<StringView>& args, Precedence prec)
463{
464 switch (prec) {
465 case Or: {
466 auto left = parse(args, And);
467 while (!args.is_empty() && args.head() == "|") {
468 args.dequeue();
469 auto right = parse(args, And);
470 left = make<BooleanExpression>(BooleanExpression::BooleanOperator::Or, move(left), move(right));
471 }
472 return left;
473 }
474 case And: {
475 auto left = parse(args, Comp);
476 while (!args.is_empty() && args.head() == "&"sv) {
477 args.dequeue();
478 auto right = parse(args, Comp);
479 left = make<BooleanExpression>(BooleanExpression::BooleanOperator::And, move(left), move(right));
480 }
481 return left;
482 }
483 case Comp: {
484 auto left = parse(args, ArithS);
485 while (!args.is_empty() && args.head().is_one_of("<"sv, "<="sv, "="sv, "!="sv, "=>"sv, ">"sv)) {
486 auto op = args.dequeue();
487 auto right = parse(args, ArithM);
488 left = make<ComparisonExpression>(ComparisonExpression::op_from(op), move(left), move(right));
489 }
490 return left;
491 }
492 case ArithS: {
493 auto left = parse(args, ArithM);
494 while (!args.is_empty() && args.head().is_one_of("+"sv, "-"sv)) {
495 auto op = args.dequeue();
496 auto right = parse(args, ArithM);
497 left = make<ArithmeticExpression>(ArithmeticExpression::op_from(op), move(left), move(right));
498 }
499 return left;
500 }
501 case ArithM: {
502 auto left = parse(args, StringO);
503 while (!args.is_empty() && args.head().is_one_of("*"sv, "/"sv, "%"sv)) {
504 auto op = args.dequeue();
505 auto right = parse(args, StringO);
506 left = make<ArithmeticExpression>(ArithmeticExpression::op_from(op), move(left), move(right));
507 }
508 return left;
509 }
510 case StringO: {
511 if (args.is_empty())
512 fail("Expected a term");
513
514 OwnPtr<Expression> left;
515
516 while (!args.is_empty()) {
517 auto& op = args.head();
518 if (op == "+"sv) {
519 args.dequeue();
520 left = make<ValueExpression>(args.dequeue());
521 } else if (op == "substr"sv) {
522 args.dequeue();
523 auto str = parse(args, Paren);
524 auto pos = parse(args, Paren);
525 auto len = parse(args, Paren);
526 left = make<StringExpression>(StringExpression::StringOperation::Substring, move(str), move(pos), move(len));
527 } else if (op == "index"sv) {
528 args.dequeue();
529 auto str = parse(args, Paren);
530 auto chars = parse(args, Paren);
531 left = make<StringExpression>(StringExpression::StringOperation::Index, move(str), move(chars));
532 } else if (op == "match"sv) {
533 args.dequeue();
534 auto str = parse(args, Paren);
535 auto pattern = parse(args, Paren);
536 left = make<StringExpression>(StringExpression::StringOperation::Match, move(str), move(pattern));
537 } else if (op == "length"sv) {
538 args.dequeue();
539 auto str = parse(args, Paren);
540 left = make<StringExpression>(StringExpression::StringOperation::Length, move(str));
541 } else if (!left) {
542 left = parse(args, Paren);
543 }
544
545 if (!args.is_empty() && args.head() == ":"sv) {
546 args.dequeue();
547 auto right = parse(args, Paren);
548 left = make<StringExpression>(StringExpression::StringOperation::Match, left.release_nonnull(), move(right));
549 } else {
550 return left.release_nonnull();
551 }
552 }
553
554 return left.release_nonnull();
555 }
556 case Paren: {
557 if (args.is_empty())
558 fail("Expected a term");
559
560 if (args.head() == "("sv) {
561 args.dequeue();
562 auto expr = parse(args);
563 if (args.head() != ")")
564 fail("Expected a close paren");
565 args.dequeue();
566 return expr;
567 }
568
569 return make<ValueExpression>(args.dequeue());
570 }
571 }
572
573 fail("Invalid expression");
574}
575
576ErrorOr<int> serenity_main(Main::Arguments arguments)
577{
578 TRY(Core::System::pledge("stdio"sv));
579 TRY(Core::System::unveil(nullptr, nullptr));
580
581 if ((arguments.strings.size() == 2 && "--help"sv == arguments.strings[1]) || arguments.strings.size() == 1)
582 print_help_and_exit();
583
584 Queue<StringView> args;
585 for (size_t i = 1; i < arguments.strings.size(); ++i)
586 args.enqueue(arguments.strings[i]);
587
588 auto expression = Expression::parse(args);
589 if (!args.is_empty())
590 fail("Extra tokens at the end of the expression");
591
592 switch (expression->type()) {
593 case Expression::Type::Integer:
594 outln("{}", expression->integer());
595 break;
596 case Expression::Type::String:
597 outln("{}", expression->string());
598 break;
599 }
600 return expression->truth() ? 0 : 1;
601}