Home /Modules/sleela-terminal/expand.cpp

expand.cpp

sleela-terminal/expand.cpp · 539 line(s) · c

// SleelaTerminal(TM) shell -- L4 expansion implementation.
// Original SLeeLa work (see NOTICE).

#include "expand.hpp"
#include "arith.hpp"

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <limits>
#include <dirent.h>
#include <pwd.h>
#include <sys/stat.h>
#include <unistd.h>

namespace sleela::sh {

namespace {

constexpr std::size_t kMaxBraceResults = 4096;
constexpr std::size_t kMaxBraceDepth = 64;

// Recursive brace expansion is deliberately bounded: expansion is user input
// and must not be able to exhaust memory or the process stack.
thread_local std::size_t braceDepth = 0;
struct BraceDepthGuard {
    BraceDepthGuard() { ++braceDepth; }
    ~BraceDepthGuard() { --braceDepth; }
};

bool isNameStart(char c) {
    return std::isalpha(static_cast<unsigned char>(c)) || c == '_';
}
bool isNameChar(char c) {
    return std::isalnum(static_cast<unsigned char>(c)) || c == '_';
}

std::string lookupParam(const std::string& name, const Environment& env) {
    if (name == "?") return std::to_string(env.lastStatus());
    if (name == "#") return std::to_string(env.positionalCount());
    // $1..$9 etc.
    if (!name.empty() && std::all_of(name.begin(), name.end(),
            [](char c){ return std::isdigit(static_cast<unsigned char>(c)); })) {
        return env.getPositional(static_cast<std::size_t>(Value(name).asInt()));
    }
    return env.get(name);
}

// ---------------------------------------------------------------------------
// Pass 1-3: expand $ sequences of a word into a single string. We do NOT split
// or glob here; that happens after. Returns the expanded string.
// ---------------------------------------------------------------------------
std::string expandDollar(const std::string& word, Environment& env,
                         const CommandRunner& run);

// Apply a ${name OP word} parameter operator. `content` is the text between the
// braces (operators and the trailing word); `env`/`run` allow the operator's
// word to itself be expanded, and := to assign back. Returns the resulting
// string; sets `err` non-empty on ${x:?msg} when x is unset/empty.
std::string applyParamBraces(const std::string& content, Environment& env,
                             const CommandRunner& run, std::string& err) {
    // ${#name} -> length of the value
    if (!content.empty() && content[0] == '#' && content.size() > 1) {
        const std::string name = content.substr(1);
        return std::to_string(lookupParam(name, env).size());
    }

    // find an operator: :- := :? :+ (with the ':' meaning "unset or empty")
    // or the bare forms - = ? + ("unset" only). We support the ':' forms and
    // treat the bare forms the same for this milestone.
    std::size_t op = std::string::npos;
    char opc = 0;
    bool colon = false;
    for (std::size_t k = 0; k < content.size(); ++k) {
        const char ch = content[k];
        if (ch == '-' || ch == '=' || ch == '?' || ch == '+') {
            op = k; opc = ch;
            colon = (k > 0 && content[k - 1] == ':');
            break;
        }
    }
    if (op == std::string::npos) {
        // plain ${name}
        return lookupParam(content, env);
    }

    const std::size_t nameEnd = colon ? op - 1 : op;
    const std::string name = content.substr(0, nameEnd);
    const std::string argRaw = content.substr(op + 1);
    const std::string arg = expandDollar(argRaw, env, run);  // recursive expand

    const std::string cur = lookupParam(name, env);
    const bool unsetOrEmpty = colon ? cur.empty() : !env.has(name);

    switch (opc) {
        case '-':  // use default if unset/empty
            return unsetOrEmpty ? arg : cur;
        case '=':  // assign default if unset/empty, then use it
            if (unsetOrEmpty) { env.set(name, arg); return arg; }
            return cur;
        case '?':  // error if unset/empty
            if (unsetOrEmpty) { err = name + ": " + (arg.empty() ? "parameter null or not set" : arg); return {}; }
            return cur;
        case '+':  // use alternate if set/non-empty
            return unsetOrEmpty ? std::string() : arg;
        default:
            return cur;
    }
}

std::string expandDollar(const std::string& word, Environment& env,
                         const CommandRunner& run) {
    std::string out;
    const std::size_t n = word.size();
    std::size_t i = 0;

    auto varLookup = [&env](const std::string& id) -> long {
        // arithmetic sees $1.. and named vars alike
        if (!id.empty() && std::all_of(id.begin(), id.end(),
                [](char c){ return std::isdigit(static_cast<unsigned char>(c)); })) {
            return Value(id).asInt();
        }
        return Value(env.get(id)).asInt();
    };

    while (i < n) {
        const char c = word[i];
        if (c != '$') { out.push_back(c); ++i; continue; }
        if (i + 1 >= n) { out.push_back('$'); ++i; break; }
        const char d = word[i + 1];

        // $(( expr )) arithmetic
        if (d == '(' && i + 2 < n && word[i + 2] == '(') {
            std::size_t j = i + 3;
            int depth = 1;
            std::string expr;
            while (j < n) {
                if (word[j] == '(') { ++depth; expr.push_back(word[j]); ++j; }
                else if (word[j] == ')') {
                    if (j + 1 < n && word[j + 1] == ')' && depth == 1) { j += 2; depth = 0; break; }
                    --depth; expr.push_back(word[j]); ++j;
                } else { expr.push_back(word[j]); ++j; }
            }
            if (depth != 0) { out.append(word, i, std::string::npos); break; }
            ArithResult r = evalArith(expr, varLookup);
            out += r.ok ? std::to_string(r.value) : std::string("0");
            i = j;
            continue;
        }

        // $( ... ) command substitution
        if (d == '(') {
            std::size_t j = i + 2;
            int depth = 1;
            std::string cmd;
            while (j < n && depth > 0) {
                if (word[j] == '(') { ++depth; cmd.push_back(word[j]); ++j; }
                else if (word[j] == ')') { --depth; if (depth > 0) cmd.push_back(word[j]); ++j; }
                else { cmd.push_back(word[j]); ++j; }
            }
            if (depth != 0) { out.append(word, i, std::string::npos); break; }
            std::string captured = run ? run(cmd) : std::string();
            // trailing newlines are stripped by command substitution
            while (!captured.empty() && (captured.back() == '\n' || captured.back() == '\r'))
                captured.pop_back();
            out += captured;
            i = j;
            continue;
        }

        // ${name} and ${name OP word} parameter expansion (nested { } allowed
        // in the operator word).
        if (d == '{') {
            std::size_t j = i + 2;
            std::string content;
            int depth = 1;
            while (j < n && depth > 0) {
                if (word[j] == '{') { ++depth; content.push_back(word[j]); ++j; }
                else if (word[j] == '}') { --depth; if (depth > 0) content.push_back(word[j]); ++j; }
                else { content.push_back(word[j]); ++j; }
            }
            if (depth != 0) { out.append(word, i, std::string::npos); break; }
            std::string err;
            out += applyParamBraces(content, env, run, err);
            // (an ${x:?msg} error is reported by the caller path in a fuller
            // shell; here we surface it via stderr and continue.)
            if (!err.empty()) std::fprintf(stderr, "slsh: %s\n", err.c_str());
            i = j;
            continue;
        }

        // $? $$ $# specials
        if (d == '?') { out += std::to_string(env.lastStatus()); i += 2; continue; }
        if (d == '#') { out += std::to_string(env.positionalCount()); i += 2; continue; }
        if (d == '$') { out += std::to_string(static_cast<long>(::getpid())); i += 2; continue; }

        // $@ -> all positionals joined by space (this pass; splitting later)
        if (d == '@') {
            const auto ps = env.positionals();
            for (std::size_t k = 0; k < ps.size(); ++k) {
                if (k) out.push_back(' ');
                out += ps[k];
            }
            i += 2;
            continue;
        }

        // $1..$9 (single digit positionals)
        if (std::isdigit(static_cast<unsigned char>(d))) {
            std::size_t j = i + 1;
            std::string num;
            while (j < n && std::isdigit(static_cast<unsigned char>(word[j]))) { num.push_back(word[j]); ++j; }
            out += env.getPositional(static_cast<std::size_t>(Value(num).asInt()));
            i = j;
            continue;
        }

        // $name
        if (isNameStart(d)) {
            std::size_t j = i + 1;
            std::string name;
            while (j < n && isNameChar(word[j])) { name.push_back(word[j]); ++j; }
            out += lookupParam(name, env);
            i = j;
            continue;
        }

        out.push_back('$');
        ++i;
    }
    return out;
}

// ---------------------------------------------------------------------------
// Pass 4: split on unquoted whitespace. This milestone splits the whole
// expanded string (quotes were removed by the lexer, so we cannot know which
// spaces were quoted; we treat the *original word* having had no spaces as a
// hint by only splitting fields that arose from expansion). To keep behaviour
// predictable and safe, we split on runs of spaces/tabs/newlines.
// ---------------------------------------------------------------------------
std::vector<std::string> fieldSplit(const std::string& s) {
    std::vector<std::string> fields;
    std::string cur;
    bool inField = false;
    for (char c : s) {
        if (c == ' ' || c == '\t' || c == '\n') {
            if (inField) { fields.push_back(cur); cur.clear(); inField = false; }
        } else {
            cur.push_back(c);
            inField = true;
        }
    }
    if (inField) fields.push_back(cur);
    return fields;
}

// ---------------------------------------------------------------------------
// Pass 5: glob matching. globMatch implements * ? [..]; globPattern walks a
// path segment-by-segment against the current directory tree.
// ---------------------------------------------------------------------------

// Match text against pattern with * ? and [set] (supporting [a-z] and [!..]).
bool matchHere(const char* p, const char* t);

bool matchClass(const char*& p, char ch, bool& matched) {
    // p points just after '['
    bool negate = false;
    if (*p == '!' || *p == '^') { negate = true; ++p; }
    matched = false;
    bool first = true;
    while (*p && (*p != ']' || first)) {
        first = false;
        if (p[0] && p[1] == '-' && p[2] && p[2] != ']') {
            char lo = p[0], hi = p[2];
            if (ch >= lo && ch <= hi) matched = true;
            p += 3;
        } else {
            if (*p == ch) matched = true;
            ++p;
        }
    }
    if (*p == ']') ++p;  // consume closing ]
    if (negate) matched = !matched;
    return true;
}

bool matchHere(const char* p, const char* t) {
    while (*p) {
        if (*p == '*') {
            ++p;
            if (*p == '\0') return true;  // trailing * matches the rest
            for (const char* s = t; ; ++s) {
                if (matchHere(p, s)) return true;
                if (*s == '\0') return false;
            }
        }
        if (*t == '\0') return false;
        if (*p == '?') { ++p; ++t; continue; }
        if (*p == '[') {
            const char* pp = p + 1;
            bool matched = false;
            matchClass(pp, *t, matched);
            if (!matched) return false;
            p = pp; ++t;
            continue;
        }
        if (*p != *t) return false;
        ++p; ++t;
    }
    return *t == '\0';
}

bool hasGlobMeta(const std::string& s) {
    return s.find_first_of("*?[") != std::string::npos;
}

// --- tilde expansion ---------------------------------------------------------
// Expand a leading ~ or ~user in a word. Only the prefix up to the first '/'
// (or end) is a tilde-prefix. ~ -> $HOME; ~user -> that user's home directory.
std::string tildeExpand(const std::string& word, const Environment& env) {
    if (word.empty() || word[0] != '~') return word;
    const std::size_t slash = word.find('/');
    const std::string prefix = (slash == std::string::npos) ? word : word.substr(0, slash);
    const std::string rest = (slash == std::string::npos) ? std::string() : word.substr(slash);

    std::string home;
    if (prefix == "~") {
        home = env.get("HOME");
        if (home.empty()) {
            if (const passwd* pw = ::getpwuid(::getuid())) home = pw->pw_dir;
        }
    } else {
        const std::string user = prefix.substr(1);  // after '~'
        if (const passwd* pw = ::getpwnam(user.c_str())) home = pw->pw_dir;
        else return word;  // unknown user -> leave literal
    }
    if (home.empty()) return word;
    return home + rest;
}

// --- brace expansion ---------------------------------------------------------
// Expand the first {..} group in `word` into fields, recursing so multiple
// groups combine. Supports comma lists {a,b,c} and numeric ranges {m..n}.
// If no valid group, returns {word}.
std::vector<std::string> braceExpand(const std::string& word) {
    BraceDepthGuard guard;
    if (braceDepth > kMaxBraceDepth || word.size() > (1u << 20)) return {word};

    // find a top-level '{'
    const std::size_t open = word.find('{');
    if (open == std::string::npos) return {word};

    // find its matching '}', tracking nesting
    std::size_t close = std::string::npos;
    int depth = 0;
    for (std::size_t k = open; k < word.size(); ++k) {
        if (word[k] == '{') ++depth;
        else if (word[k] == '}') { --depth; if (depth == 0) { close = k; break; } }
    }
    if (close == std::string::npos) return {word};

    const std::string pre = word.substr(0, open);
    const std::string body = word.substr(open + 1, close - open - 1);
    const std::string post = word.substr(close + 1);

    // collect the alternatives from `body`
    std::vector<std::string> alts;

    // numeric range {m..n}
    const std::size_t dots = body.find("..");
    bool numericRange = false;
    if (dots != std::string::npos && body.find(',') == std::string::npos) {
        const std::string a = body.substr(0, dots);
        const std::string b = body.substr(dots + 2);
        auto isInt = [](const std::string& s) {
            if (s.empty()) return false;
            std::size_t i = (s[0] == '-' || s[0] == '+') ? 1 : 0;
            if (i >= s.size()) return false;
            for (; i < s.size(); ++i) if (!std::isdigit(static_cast<unsigned char>(s[i]))) return false;
            return true;
        };
        if (isInt(a) && isInt(b)) {
            numericRange = true;
            try {
                const long lo = std::stol(a), hi = std::stol(b);
                // Avoid signed overflow in span calculations and loop increments.
                const unsigned long long span = lo <= hi
                    ? static_cast<unsigned long long>(hi) - static_cast<unsigned long long>(lo)
                    : static_cast<unsigned long long>(lo) - static_cast<unsigned long long>(hi);
                if (span >= kMaxBraceResults) return {word};
                if (lo <= hi) {
                    for (long v = lo;; ++v) {
                        alts.push_back(std::to_string(v));
                        if (v == hi) break;
                    }
                } else {
                    for (long v = lo;; --v) {
                        alts.push_back(std::to_string(v));
                        if (v == hi) break;
                    }
                }
            } catch (const std::exception&) {
                // Out-of-range numeric syntax is not allowed to escape as an
                // uncaught exception from a shell expansion.
                return {word};
            }
        }
    }

    if (!numericRange) {
        // comma list (respecting nested braces); a single element (no comma)
        // is NOT a brace expansion -> treat literally.
        std::vector<std::string> parts;
        int d = 0;
        std::string cur;
        for (char ch : body) {
            if (ch == '{') { ++d; cur.push_back(ch); }
            else if (ch == '}') { --d; cur.push_back(ch); }
            else if (ch == ',' && d == 0) { parts.push_back(cur); cur.clear(); }
            else cur.push_back(ch);
        }
        parts.push_back(cur);
        if (parts.size() < 2) return {word};  // no real expansion
        alts = std::move(parts);
    }

    // combine pre + each alt (recursively brace-expanded) + brace-expanded post
    std::vector<std::string> out;
    std::vector<std::string> posts = braceExpand(post);
    for (const auto& alt : alts) {
        for (const auto& altExpanded : braceExpand(alt)) {
            for (const auto& p : posts) {
                if (out.size() >= kMaxBraceResults) return {word};
                out.push_back(pre + altExpanded + p);
            }
        }
    }
    return out;
}

} // namespace

bool globMatch(const std::string& pattern, const std::string& text) {
    return matchHere(pattern.c_str(), text.c_str());
}

std::vector<std::string> globPattern(const std::string& pattern) {
    if (!hasGlobMeta(pattern)) return {pattern};

    // M5: expand one pathname component at a time. Matches remain argv data;
    // they are never rewritten into shell source and reparsed.
    const bool absolute = !pattern.empty() && pattern.front() == '/';
    const bool dotPrefix = !absolute && pattern.rfind("./", 0) == 0;
    const std::size_t begin = absolute ? 1 : (dotPrefix ? 2 : 0);
    std::vector<std::string> parts;
    std::size_t p = begin;
    while (p <= pattern.size()) {
        const std::size_t slash = pattern.find('/', p);
        parts.push_back(pattern.substr(p, slash == std::string::npos ? pattern.size() - p : slash - p));
        if (slash == std::string::npos) break;
        p = slash + 1;
    }

    std::vector<std::string> matches;
    std::function<void(const std::string&, std::size_t)> walk =
        [&](const std::string& base, std::size_t index) {
            if (index == parts.size()) {
                matches.push_back(base.empty() ? (absolute ? "/" : (dotPrefix ? "./" : ".")) : base);
                return;
            }
            const std::string& seg = parts[index];
            const std::string dir = base.empty() ? (absolute ? "/" : ".") : base;

            if (!hasGlobMeta(seg)) {
                const std::string next = base.empty()
                    ? (absolute ? "/" + seg : (dotPrefix ? "./" + seg : seg))
                    : (base == "/" ? "/" + seg : base + "/" + seg);
                struct stat st{};
                if (::stat(next.c_str(), &st) == 0) walk(next, index + 1);
                return;
            }

            DIR* dp = ::opendir(dir.c_str());
            if (!dp) return;
            struct dirent* de;
            while ((de = ::readdir(dp)) != nullptr) {
                const std::string name = de->d_name;
                if (name == "." || name == "..") continue;
                if (!name.empty() && name[0] == '.' && (seg.empty() || seg[0] != '.')) continue;
                if (!globMatch(seg, name)) continue;
                const std::string next = (base.empty()
                    ? (absolute ? "/" + name : (dotPrefix ? "./" + name : name))
                    : (base == "/" ? "/" + name : base + "/" + name));
                walk(next, index + 1);
            }
            ::closedir(dp);
        };

    walk("", 0);
    if (matches.empty()) return {pattern};
    std::sort(matches.begin(), matches.end());
    return matches;
}

std::vector<std::string> expandWord(const std::string& word,
                                    Environment& env,
                                    const CommandRunner& run) {
    std::vector<std::string> out;
    // Pass 1: brace expansion -> multiple raw words.
    for (const std::string& braced : braceExpand(word)) {
        // Pass 2: tilde expansion (word-start prefix).
        const std::string tilded = tildeExpand(braced, env);
        // Passes 3-5: command/arith/parameter expansion.
        const std::string expanded = expandDollar(tilded, env, run);
        // Pass 6: field splitting.
        std::vector<std::string> fields = fieldSplit(expanded);
        if (fields.empty()) {
            if (!expanded.empty()) fields.push_back(expanded);
            else continue;  // fully empty expansion contributes no field
        }
        // Pass 7: glob each field.
        for (const auto& f : fields) {
            auto g = globPattern(f);
            out.insert(out.end(), g.begin(), g.end());
        }
    }
    return out;
}

std::string expandWordSingle(const std::string& word,
                             Environment& env,
                             const CommandRunner& run) {
    // One string: tilde then $-expansion; no brace/split/glob multiplication.
    const std::string tilded = tildeExpand(word, env);
    return expandDollar(tilded, env, run);
}

} // namespace sleela::sh