diff options
Diffstat (limited to 'corebinutils/expr/expr.c')
| -rw-r--r-- | corebinutils/expr/expr.c | 923 |
1 files changed, 923 insertions, 0 deletions
diff --git a/corebinutils/expr/expr.c b/corebinutils/expr/expr.c new file mode 100644 index 0000000000..6783f6afaf --- /dev/null +++ b/corebinutils/expr/expr.c @@ -0,0 +1,923 @@ +/* + * SPDX-License-Identifier: Apache-2.0 + * + * Copyright (c) 2026 Project Tick + * + * 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. + * + * Linux/musl-native port of FreeBSD expr(1). + * The original parser was expressed in yacc grammar form; this port keeps + * the same operator precedence and value semantics but uses a local + * recursive-descent parser so the standalone build does not depend on the + * FreeBSD build system or generated sources. + */ + +#define _POSIX_C_SOURCE 200809L + +#include <ctype.h> +#include <errno.h> +#include <inttypes.h> +#include <limits.h> +#include <locale.h> +#include <regex.h> +#include <stdarg.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define ERR_EXIT 2 + +enum value_type { + VALUE_INTEGER, + VALUE_NUMERIC_STRING, + VALUE_STRING, +}; + +struct value { + enum value_type type; + union { + intmax_t integer; + char *string; + } data; +}; + +struct parser { + const char *program; + char **argv; + int argc; + int index; + bool compat_mode; +}; + +static void usage(void) __attribute__((noreturn)); +static void vfail(struct parser *parser, bool with_errno, const char *fmt, + va_list ap) __attribute__((noreturn)); +static void fail(struct parser *parser, const char *fmt, ...) + __attribute__((format(printf, 2, 3), noreturn)); +static void fail_errno(struct parser *parser, const char *fmt, ...) + __attribute__((format(printf, 2, 3), noreturn)); +static void *xmalloc(struct parser *parser, size_t size); +static char *xstrdup(struct parser *parser, const char *text); +static bool is_operator_token(const char *token); +static bool is_integer_literal(const char *text, bool compat_mode); +static struct value value_from_integer(intmax_t integer); +static struct value value_from_argument(struct parser *parser, const char *text); +static void value_dispose(struct value *value); +static struct value value_move(struct value *value); +static bool value_try_to_integer(struct value *value); +static void value_require_integer(struct parser *parser, struct value *value); +static void value_require_string(struct parser *parser, struct value *value); +static bool value_is_zero_or_null(struct value *value); +static int compare_values(struct parser *parser, struct value *left, + struct value *right); +static bool add_overflow(intmax_t left, intmax_t right, intmax_t *result); +static bool sub_overflow(intmax_t left, intmax_t right, intmax_t *result); +static uintmax_t intmax_magnitude(intmax_t value); +static bool mul_overflow(intmax_t left, intmax_t right, intmax_t *result); +static struct value value_or(struct value *left, struct value *right); +static struct value value_and(struct value *left, struct value *right); +static struct value value_compare_eq(struct parser *parser, struct value *left, + struct value *right); +static struct value value_compare_ne(struct parser *parser, struct value *left, + struct value *right); +static struct value value_compare_lt(struct parser *parser, struct value *left, + struct value *right); +static struct value value_compare_le(struct parser *parser, struct value *left, + struct value *right); +static struct value value_compare_gt(struct parser *parser, struct value *left, + struct value *right); +static struct value value_compare_ge(struct parser *parser, struct value *left, + struct value *right); +static struct value value_add(struct parser *parser, struct value *left, + struct value *right); +static struct value value_sub(struct parser *parser, struct value *left, + struct value *right); +static struct value value_mul(struct parser *parser, struct value *left, + struct value *right); +static struct value value_div(struct parser *parser, struct value *left, + struct value *right); +static struct value value_rem(struct parser *parser, struct value *left, + struct value *right); +static char *dup_substring(struct parser *parser, const char *text, regoff_t start, + regoff_t end); +static struct value value_match(struct parser *parser, struct value *left, + struct value *right); +static const char *peek_token(const struct parser *parser); +static bool match_token(struct parser *parser, const char *token); +static struct value parse_expression(struct parser *parser); +static struct value parse_or(struct parser *parser); +static struct value parse_and(struct parser *parser); +static struct value parse_compare(struct parser *parser); +static struct value parse_add(struct parser *parser); +static struct value parse_mul(struct parser *parser); +static struct value parse_match_expr(struct parser *parser); +static struct value parse_primary(struct parser *parser); +static void write_result(struct parser *parser, const struct value *value); + +static void +usage(void) +{ + fprintf(stderr, "usage: expr [-e] [--] expression\n"); + exit(ERR_EXIT); +} + +static void +vfail(struct parser *parser, bool with_errno, const char *fmt, va_list ap) +{ + int saved_errno; + + saved_errno = errno; + fprintf(stderr, "%s: ", parser->program); + vfprintf(stderr, fmt, ap); + if (with_errno) { + fprintf(stderr, ": %s", + saved_errno == 0 ? "I/O error" : strerror(saved_errno)); + } + fputc('\n', stderr); + exit(ERR_EXIT); +} + +static void +fail(struct parser *parser, const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vfail(parser, false, fmt, ap); + va_end(ap); +} + +static void +fail_errno(struct parser *parser, const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vfail(parser, true, fmt, ap); + va_end(ap); +} + +static void * +xmalloc(struct parser *parser, size_t size) +{ + void *memory; + + if (size == 0) { + size = 1; + } + memory = malloc(size); + if (memory == NULL) { + fail(parser, "malloc failed"); + } + return (memory); +} + +static char * +xstrdup(struct parser *parser, const char *text) +{ + size_t length; + char *copy; + + length = strlen(text) + 1; + copy = xmalloc(parser, length); + memcpy(copy, text, length); + return (copy); +} + +static bool +is_operator_token(const char *token) +{ + static const char *const operators[] = { + "|", + "&", + "=", + ">", + "<", + ">=", + "<=", + "!=", + "+", + "-", + "*", + "/", + "%", + ":", + "(", + ")", + }; + size_t i; + + for (i = 0; i < sizeof(operators) / sizeof(operators[0]); i++) { + if (strcmp(token, operators[i]) == 0) { + return (true); + } + } + return (false); +} + +static bool +is_integer_literal(const char *text, bool compat_mode) +{ + const unsigned char *cursor; + + cursor = (const unsigned char *)text; + if (compat_mode) { + if (*cursor == '\0') { + return (true); + } + while (isspace(*cursor) != 0) { + cursor++; + } + } + if (*cursor == '-' || (compat_mode && *cursor == '+')) { + cursor++; + } + if (*cursor == '\0') { + return (false); + } + while (isdigit(*cursor) != 0) { + cursor++; + } + return (*cursor == '\0'); +} + +static struct value +value_from_integer(intmax_t integer) +{ + struct value value; + + value.type = VALUE_INTEGER; + value.data.integer = integer; + return (value); +} + +static struct value +value_from_argument(struct parser *parser, const char *text) +{ + struct value value; + + value.data.string = xstrdup(parser, text); + value.type = is_integer_literal(text, parser->compat_mode) ? + VALUE_NUMERIC_STRING : VALUE_STRING; + return (value); +} + +static void +value_dispose(struct value *value) +{ + if (value->type == VALUE_NUMERIC_STRING || value->type == VALUE_STRING) { + free(value->data.string); + } + value->type = VALUE_INTEGER; + value->data.integer = 0; +} + +static struct value +value_move(struct value *value) +{ + struct value moved; + + moved = *value; + value->type = VALUE_INTEGER; + value->data.integer = 0; + return (moved); +} + +static bool +value_try_to_integer(struct value *value) +{ + intmax_t parsed; + char *end; + + if (value->type == VALUE_INTEGER) { + return (true); + } + if (value->type != VALUE_NUMERIC_STRING) { + return (false); + } + + errno = 0; + end = NULL; + parsed = strtoimax(value->data.string, &end, 10); + if (errno == ERANGE || end == NULL || *end != '\0') { + return (false); + } + + free(value->data.string); + value->type = VALUE_INTEGER; + value->data.integer = parsed; + return (true); +} + +static void +value_require_integer(struct parser *parser, struct value *value) +{ + if (value->type == VALUE_STRING) { + fail(parser, "not a decimal number: '%s'", value->data.string); + } + if (!value_try_to_integer(value)) { + fail(parser, "operand too large: '%s'", value->data.string); + } +} + +static void +value_require_string(struct parser *parser, struct value *value) +{ + int length; + size_t size; + char *buffer; + + if (value->type != VALUE_INTEGER) { + return; + } + + length = snprintf(NULL, 0, "%jd", value->data.integer); + if (length < 0) { + fail(parser, "failed to format integer result"); + } + size = (size_t)length + 1; + buffer = xmalloc(parser, size); + if (snprintf(buffer, size, "%jd", value->data.integer) != length) { + free(buffer); + fail(parser, "failed to format integer result"); + } + value->type = VALUE_STRING; + value->data.string = buffer; +} + +static bool +value_is_zero_or_null(struct value *value) +{ + if (value->type == VALUE_INTEGER) { + return (value->data.integer == 0); + } + if (value->data.string[0] == '\0') { + return (true); + } + return (value_try_to_integer(value) && value->data.integer == 0); +} + +static int +compare_values(struct parser *parser, struct value *left, struct value *right) +{ + int result; + + if (left->type == VALUE_STRING || right->type == VALUE_STRING) { + value_require_string(parser, left); + value_require_string(parser, right); + result = strcoll(left->data.string, right->data.string); + } else { + value_require_integer(parser, left); + value_require_integer(parser, right); + if (left->data.integer > right->data.integer) { + result = 1; + } else if (left->data.integer < right->data.integer) { + result = -1; + } else { + result = 0; + } + } + + value_dispose(left); + value_dispose(right); + return (result); +} + +static bool +add_overflow(intmax_t left, intmax_t right, intmax_t *result) +{ + if (right > 0 && left > INTMAX_MAX - right) { + return (true); + } + if (right < 0 && left < INTMAX_MIN - right) { + return (true); + } + *result = left + right; + return (false); +} + +static bool +sub_overflow(intmax_t left, intmax_t right, intmax_t *result) +{ + if (right > 0 && left < INTMAX_MIN + right) { + return (true); + } + if (right < 0 && left > INTMAX_MAX + right) { + return (true); + } + *result = left - right; + return (false); +} + +static uintmax_t +intmax_magnitude(intmax_t value) +{ + if (value >= 0) { + return ((uintmax_t)value); + } + return ((uintmax_t)(-(value + 1)) + 1U); +} + +static bool +mul_overflow(intmax_t left, intmax_t right, intmax_t *result) +{ + uintmax_t left_abs; + uintmax_t right_abs; + uintmax_t limit; + uintmax_t product; + bool negative; + + if (left == 0 || right == 0) { + *result = 0; + return (false); + } + + left_abs = intmax_magnitude(left); + right_abs = intmax_magnitude(right); + negative = ((left < 0) != (right < 0)); + limit = negative ? ((uintmax_t)INTMAX_MAX + 1U) : (uintmax_t)INTMAX_MAX; + + if (right_abs > limit / left_abs) { + return (true); + } + + product = left_abs * right_abs; + if (!negative) { + *result = (intmax_t)product; + return (false); + } + if (product == (uintmax_t)INTMAX_MAX + 1U) { + *result = INTMAX_MIN; + return (false); + } + *result = -(intmax_t)product; + return (false); +} + +static struct value +value_or(struct value *left, struct value *right) +{ + if (!value_is_zero_or_null(left)) { + value_dispose(right); + return (value_move(left)); + } + value_dispose(left); + if (!value_is_zero_or_null(right)) { + return (value_move(right)); + } + value_dispose(right); + return (value_from_integer(0)); +} + +static struct value +value_and(struct value *left, struct value *right) +{ + if (value_is_zero_or_null(left) || value_is_zero_or_null(right)) { + value_dispose(left); + value_dispose(right); + return (value_from_integer(0)); + } + value_dispose(right); + return (value_move(left)); +} + +static struct value +value_compare_eq(struct parser *parser, struct value *left, struct value *right) +{ + return (value_from_integer(compare_values(parser, left, right) == 0)); +} + +static struct value +value_compare_ne(struct parser *parser, struct value *left, struct value *right) +{ + return (value_from_integer(compare_values(parser, left, right) != 0)); +} + +static struct value +value_compare_lt(struct parser *parser, struct value *left, struct value *right) +{ + return (value_from_integer(compare_values(parser, left, right) < 0)); +} + +static struct value +value_compare_le(struct parser *parser, struct value *left, struct value *right) +{ + return (value_from_integer(compare_values(parser, left, right) <= 0)); +} + +static struct value +value_compare_gt(struct parser *parser, struct value *left, struct value *right) +{ + return (value_from_integer(compare_values(parser, left, right) > 0)); +} + +static struct value +value_compare_ge(struct parser *parser, struct value *left, struct value *right) +{ + return (value_from_integer(compare_values(parser, left, right) >= 0)); +} + +static struct value +value_add(struct parser *parser, struct value *left, struct value *right) +{ + intmax_t result; + + value_require_integer(parser, left); + value_require_integer(parser, right); + if (add_overflow(left->data.integer, right->data.integer, &result)) { + fail(parser, "overflow"); + } + value_dispose(left); + value_dispose(right); + return (value_from_integer(result)); +} + +static struct value +value_sub(struct parser *parser, struct value *left, struct value *right) +{ + intmax_t result; + + value_require_integer(parser, left); + value_require_integer(parser, right); + if (sub_overflow(left->data.integer, right->data.integer, &result)) { + fail(parser, "overflow"); + } + value_dispose(left); + value_dispose(right); + return (value_from_integer(result)); +} + +static struct value +value_mul(struct parser *parser, struct value *left, struct value *right) +{ + intmax_t result; + + value_require_integer(parser, left); + value_require_integer(parser, right); + if (mul_overflow(left->data.integer, right->data.integer, &result)) { + fail(parser, "overflow"); + } + value_dispose(left); + value_dispose(right); + return (value_from_integer(result)); +} + +static struct value +value_div(struct parser *parser, struct value *left, struct value *right) +{ + intmax_t result; + + value_require_integer(parser, left); + value_require_integer(parser, right); + if (right->data.integer == 0) { + fail(parser, "division by zero"); + } + if (left->data.integer == INTMAX_MIN && right->data.integer == -1) { + fail(parser, "overflow"); + } + result = left->data.integer / right->data.integer; + value_dispose(left); + value_dispose(right); + return (value_from_integer(result)); +} + +static struct value +value_rem(struct parser *parser, struct value *left, struct value *right) +{ + intmax_t result; + + value_require_integer(parser, left); + value_require_integer(parser, right); + if (right->data.integer == 0) { + fail(parser, "division by zero"); + } + result = left->data.integer % right->data.integer; + value_dispose(left); + value_dispose(right); + return (value_from_integer(result)); +} + +static char * +dup_substring(struct parser *parser, const char *text, regoff_t start, regoff_t end) +{ + size_t length; + char *result; + + if (start < 0 || end < start) { + fail(parser, "regular expression returned an invalid capture range"); + } + length = (size_t)(end - start); + result = xmalloc(parser, length + 1); + memcpy(result, text + start, length); + result[length] = '\0'; + return (result); +} + +static struct value +value_match(struct parser *parser, struct value *left, struct value *right) +{ + regex_t regex; + regmatch_t matches[2]; + struct value result; + size_t error_length; + char *error_text; + int regcomp_result; + int regexec_result; + + value_require_string(parser, left); + value_require_string(parser, right); + + regcomp_result = regcomp(®ex, right->data.string, 0); + if (regcomp_result != 0) { + error_length = regerror(regcomp_result, ®ex, NULL, 0); + error_text = xmalloc(parser, error_length); + (void)regerror(regcomp_result, ®ex, error_text, error_length); + fail(parser, "regular expression error: %s", error_text); + } + + regexec_result = regexec(®ex, left->data.string, + (size_t)(sizeof(matches) / sizeof(matches[0])), matches, 0); + if (regexec_result == 0 && matches[0].rm_so == 0) { + if (matches[1].rm_so >= 0) { + result.type = VALUE_STRING; + result.data.string = dup_substring(parser, left->data.string, + matches[1].rm_so, matches[1].rm_eo); + } else { + result = value_from_integer(matches[0].rm_eo); + } + } else if (regexec_result == REG_NOMATCH || + (regexec_result == 0 && matches[0].rm_so != 0)) { + if (regex.re_nsub == 0) { + result = value_from_integer(0); + } else { + result.type = VALUE_STRING; + result.data.string = xstrdup(parser, ""); + } + } else { + error_length = regerror(regexec_result, ®ex, NULL, 0); + error_text = xmalloc(parser, error_length); + (void)regerror(regexec_result, ®ex, error_text, error_length); + regfree(®ex); + fail(parser, "regular expression execution failed: %s", error_text); + } + + regfree(®ex); + value_dispose(left); + value_dispose(right); + return (result); +} + +static const char * +peek_token(const struct parser *parser) +{ + if (parser->index >= parser->argc) { + return (NULL); + } + return (parser->argv[parser->index]); +} + +static bool +match_token(struct parser *parser, const char *token) +{ + const char *current; + + current = peek_token(parser); + if (current == NULL || strcmp(current, token) != 0) { + return (false); + } + parser->index++; + return (true); +} + +static struct value +parse_expression(struct parser *parser) +{ + return (parse_or(parser)); +} + +static struct value +parse_or(struct parser *parser) +{ + struct value left; + struct value right; + + left = parse_and(parser); + while (match_token(parser, "|")) { + right = parse_and(parser); + left = value_or(&left, &right); + } + return (left); +} + +static struct value +parse_and(struct parser *parser) +{ + struct value left; + struct value right; + + left = parse_compare(parser); + while (match_token(parser, "&")) { + right = parse_compare(parser); + left = value_and(&left, &right); + } + return (left); +} + +static struct value +parse_compare(struct parser *parser) +{ + struct value left; + struct value right; + + left = parse_add(parser); + for (;;) { + if (match_token(parser, "=")) { + right = parse_add(parser); + left = value_compare_eq(parser, &left, &right); + } else if (match_token(parser, "!=")) { + right = parse_add(parser); + left = value_compare_ne(parser, &left, &right); + } else if (match_token(parser, ">=")) { + right = parse_add(parser); + left = value_compare_ge(parser, &left, &right); + } else if (match_token(parser, "<=")) { + right = parse_add(parser); + left = value_compare_le(parser, &left, &right); + } else if (match_token(parser, ">")) { + right = parse_add(parser); + left = value_compare_gt(parser, &left, &right); + } else if (match_token(parser, "<")) { + right = parse_add(parser); + left = value_compare_lt(parser, &left, &right); + } else { + break; + } + } + return (left); +} + +static struct value +parse_add(struct parser *parser) +{ + struct value left; + struct value right; + + left = parse_mul(parser); + for (;;) { + if (match_token(parser, "+")) { + right = parse_mul(parser); + left = value_add(parser, &left, &right); + } else if (match_token(parser, "-")) { + right = parse_mul(parser); + left = value_sub(parser, &left, &right); + } else { + break; + } + } + return (left); +} + +static struct value +parse_mul(struct parser *parser) +{ + struct value left; + struct value right; + + left = parse_match_expr(parser); + for (;;) { + if (match_token(parser, "*")) { + right = parse_match_expr(parser); + left = value_mul(parser, &left, &right); + } else if (match_token(parser, "/")) { + right = parse_match_expr(parser); + left = value_div(parser, &left, &right); + } else if (match_token(parser, "%")) { + right = parse_match_expr(parser); + left = value_rem(parser, &left, &right); + } else { + break; + } + } + return (left); +} + +static struct value +parse_match_expr(struct parser *parser) +{ + struct value left; + struct value right; + + left = parse_primary(parser); + while (match_token(parser, ":")) { + right = parse_primary(parser); + left = value_match(parser, &left, &right); + } + return (left); +} + +static struct value +parse_primary(struct parser *parser) +{ + const char *token; + struct value value; + + token = peek_token(parser); + if (token == NULL) { + fail(parser, "syntax error"); + } + if (match_token(parser, "(")) { + value = parse_expression(parser); + if (!match_token(parser, ")")) { + value_dispose(&value); + fail(parser, "syntax error"); + } + return (value); + } + if (is_operator_token(token)) { + fail(parser, "syntax error"); + } + parser->index++; + return (value_from_argument(parser, token)); +} + +static void +write_result(struct parser *parser, const struct value *value) +{ + int rc; + + if (value->type == VALUE_INTEGER) { + rc = fprintf(stdout, "%jd\n", value->data.integer); + } else { + rc = fprintf(stdout, "%s\n", value->data.string); + } + if (rc < 0 || fflush(stdout) == EOF) { + fail_errno(parser, "write failed"); + } +} + +int +main(int argc, char *argv[]) +{ + struct parser parser; + struct value result; + const char *arg; + int i; + + (void)setlocale(LC_ALL, ""); + + parser.program = argv[0] == NULL ? "expr" : argv[0]; + if (strrchr(parser.program, '/') != NULL) { + parser.program = strrchr(parser.program, '/') + 1; + } + parser.compat_mode = false; + parser.index = 0; + parser.argv = NULL; + parser.argc = 0; + + i = 1; + while (i < argc) { + arg = argv[i]; + if (strcmp(arg, "--") == 0) { + i++; + break; + } + if (strcmp(arg, "-e") == 0) { + parser.compat_mode = true; + i++; + continue; + } + if (arg[0] == '-' && arg[1] != '\0') { + usage(); + } + break; + } + + parser.argv = argv + i; + parser.argc = argc - i; + if (parser.argc == 0) { + usage(); + } + + result = parse_expression(&parser); + if (peek_token(&parser) != NULL) { + value_dispose(&result); + fail(&parser, "syntax error"); + } + + write_result(&parser, &result); + i = value_is_zero_or_null(&result) ? 1 : 0; + value_dispose(&result); + return (i); +} |
