srvn_reader.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_LANG_LQN_SRVN_READER_H
#define LINE_LANG_LQN_SRVN_READER_H
 
/**
 * @file
 * @ingroup line_lang
 * SRVN input format (the LQNS `.in` / `.lqn` text grammar) for layered models,
 * the C++ twin of python/line_solver/io/srvn_io.py, MATLAB srvn2lqnx.m and the
 * JAR's jline.io.SRVN2LQNX.
 *
 * The reader TRANSLATES an SRVN document into the LQN XML interchange and hands
 * that to `read_lqnx_model`, so loading `model.in` builds exactly the model that
 * loading the `.lqnx` written by `lqn2xml -Oxml model.in` builds. The
 * translation is deterministic and BYTE-IDENTICAL across the four codebases:
 * test/testsLQNS/srvn/expected in line-test.git is the shared golden.
 *
 * Grammar covered (LQNS 6): the `G`, `P`, `U`, `T`, `E`, `A` and `R` sections;
 * processor, task, group, entry and activity declarations with every option
 * LQNS accepts; fan-in/fan-out (`I`/`O`); semaphore and rwlock entries; activity
 * precedence (sequence, AND/OR fork and join, quorum join, loop, reply lists);
 * `#pragma` lines; and SPEX scalar parameters (`$x = expr`), which are
 * substituted. A SPEX sweep (`$x = [ ... ]`) used by the model is refused
 * (`LINE:unsupported:Format`), since one layered model carries one value per
 * parameter. SPEX observations (`%u $U`), histogram requests (`H`) and the `R`
 * result list are requests for output, not model content, and are skipped.
 *
 * NUMBERS ARE COPIED AS WRITTEN: an attribute carries the source token, leading
 * '+' stripped, so the document never depends on how a codebase prints a
 * double. Only a COMPUTED parameter (`$x = 2 * $y`) is printed, by
 * `format_number`, whose rule the four codebases share.
 */
 
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
 
#include "line/lang/lqn/lqn_reader.h"
#include "line/util/error.h"
 
namespace line {
namespace lqn {
 
namespace srvn_detail {
 
/** Python's `str.isspace` over ASCII, which also counts the four separators 0x1c-0x1f. */
inline bool is_space(char c) {
    return c == ' ' || (c >= '\t' && c <= '\r') || (c >= '\x1c' && c <= '\x1f');
}
 
inline bool is_digit(char c) { return c >= '0' && c <= '9'; }
 
inline bool is_alnum(char c) {
    return is_digit(c) || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}
 
/** `[A-Za-z0-9_.$@]`, the characters of a name. */
inline bool is_ident(char c) { return is_alnum(c) || c == '_' || c == '.' || c == '$' || c == '@'; }
 
inline std::string strip(const std::string& s) {
    std::size_t a = 0, b = s.size();
    while (a < b && is_space(s[a])) ++a;
    while (b > a && is_space(s[b - 1])) --b;
    return s.substr(a, b - a);
}
 
/** Python's `repr` of an ASCII string, so messages read as the reference's do. */
inline std::string py_repr(const std::string& s) {
    const bool dq = s.find('\'') != std::string::npos && s.find('"') == std::string::npos;
    const char q = dq ? '"' : '\'';
    std::string r(1, q);
    for (unsigned char c : s) {
        if (c == '\\') r += "\\\\";
        else if (c == static_cast<unsigned char>(q)) { r += '\\'; r += static_cast<char>(c); }
        else if (c == '\n') r += "\\n";
        else if (c == '\r') r += "\\r";
        else if (c == '\t') r += "\\t";
        else if (c < 0x20 || c == 0x7f) {
            char buf[8];
            std::snprintf(buf, sizeof(buf), "\\x%02x", c);
            r += buf;
        } else r += static_cast<char>(c);
    }
    return r + q;
}
 
inline InputError err(const std::string& msg, int line = -1) {
    std::string where = line < 0 ? std::string() : " (line " + std::to_string(line) + ")";
    return InputError(ErrorKind{"Format"}, "SRVN" + where + ": " + msg);
}
 
inline std::string esc(const std::string& s) {
    std::string r;
    r.reserve(s.size());
    for (char c : s) {
        if (c == '&') r += "&amp;";
        else if (c == '<') r += "&lt;";
        else if (c == '>') r += "&gt;";
        else if (c == '"') r += "&quot;";
        else r += c;
    }
    return r;
}
 
enum class TK { STR, NUM, ID, VAR, OBS, P };
 
struct Tok {
    TK kind;
    std::string text;
    int line;
};
 
/** A number as written: its source spelling and its value. `has` false is Python's None. */
struct Val {
    bool has = false;
    std::string text;
    double value = 0.0;
    Val() {}
    Val(std::string t, double v) : has(true), text(std::move(t)), value(v) {}
};
 
inline bool nz(const Val& v) { return v.has && v.value != 0; }
 
inline std::string lstrip_plus(const std::string& s) {
    std::size_t a = 0;
    while (a < s.size() && s[a] == '+') ++a;
    return s.substr(a);
}
 
inline double to_double(const std::string& s) { return std::strtod(s.c_str(), NULL); }
 
/** End of `[-+]?(?:[0-9]+\.?[0-9]*|\.[0-9]+)(?:[eE][-+]?[0-9]+)?` matched at `i`, or npos. */
inline std::size_t match_number(const std::string& src, std::size_t i) {
    const std::size_t n = src.size();
    std::size_t k = i;
    if (k < n && (src[k] == '-' || src[k] == '+')) ++k;
    if (k < n && is_digit(src[k])) {
        while (k < n && is_digit(src[k])) ++k;
        if (k < n && src[k] == '.') ++k;
        while (k < n && is_digit(src[k])) ++k;
    } else if (k + 1 < n && src[k] == '.' && is_digit(src[k + 1])) {
        ++k;
        while (k < n && is_digit(src[k])) ++k;
    } else {
        return std::string::npos;
    }
    if (k < n && (src[k] == 'e' || src[k] == 'E')) {
        std::size_t e = k + 1;
        if (e < n && (src[e] == '-' || src[e] == '+')) ++e;
        if (e < n && is_digit(src[e])) {
            while (e < n && is_digit(src[e])) ++e;
            k = e;
        }
    }
    return k;
}
 
/** `#\s*pragma\s+(.*)$` on a stripped comment line: the body, or false. */
inline bool pragma_body(const std::string& line, std::string& body) {
    if (line.empty() || line[0] != '#') return false;
    std::size_t k = 1;
    while (k < line.size() && is_space(line[k])) ++k;
    if (line.compare(k, 6, "pragma") != 0) return false;
    k += 6;
    if (k >= line.size() || !is_space(line[k])) return false;
    while (k < line.size() && is_space(line[k])) ++k;
    body = strip(line.substr(k));
    return true;
}
 
inline void tokenize(const std::string& src, std::vector<Tok>& toks,
                     std::vector<std::pair<std::string, std::string>>& pragmas) {
    std::size_t i = 0;
    const std::size_t n = src.size();
    int line = 1;
    while (i < n) {
        const char c = src[i];
        if (c == '\n') {
            ++line;
            ++i;
        } else if (is_space(c)) {
            ++i;
        } else if (c == '#') {
            std::size_t j = src.find('\n', i);
            if (j == std::string::npos) j = n;
            std::string body;
            if (pragma_body(strip(src.substr(i, j - i)), body)) {
                std::size_t k = 0;
                while (k < body.size()) {
                    while (k < body.size() && is_space(body[k])) ++k;
                    if (k >= body.size()) break;
                    std::size_t e = k;
                    while (e < body.size() && !is_space(body[e])) ++e;
                    const std::string item = body.substr(k, e - k);
                    const std::size_t eq = item.find('=');
                    if (eq == std::string::npos) pragmas.emplace_back(item, std::string());
                    else pragmas.emplace_back(item.substr(0, eq), item.substr(eq + 1));
                    k = e;
                }
            }
            i = j;
        } else if (c == '"') {
            const std::size_t j = src.find('"', i + 1);
            if (j == std::string::npos) throw err("unterminated string", line);
            toks.push_back(Tok{TK::STR, src.substr(i + 1, j - i - 1), line});
            for (std::size_t k = i; k < j; ++k)
                if (src[k] == '\n') ++line;
            i = j + 1;
        } else if (src.compare(i, 2, "->") == 0) {
            toks.push_back(Tok{TK::P, "->", line});
            i += 2;
        } else if (c == '%') {
            std::size_t j = i + 1;
            while (j < n && (is_alnum(src[j]) || src[j] == '_')) ++j;
            toks.push_back(Tok{TK::OBS, src.substr(i, j - i), line});
            i = j;
        } else if (is_digit(c) || (c == '.' && i + 1 < n && is_digit(src[i + 1])) ||
                   ((c == '-' || c == '+') && i + 1 < n &&
                    (is_digit(src[i + 1]) || (src[i + 1] == '.' && i + 2 < n && is_digit(src[i + 2]))))) {
            std::size_t j = match_number(src, i);
            if (j < n && is_ident(src[j]) && c != '-' && c != '+') {
                while (j < n && is_ident(src[j])) ++j;
                toks.push_back(Tok{TK::ID, src.substr(i, j - i), line});
            } else {
                toks.push_back(Tok{TK::NUM, src.substr(i, j - i), line});
            }
            i = j;
        } else if (std::string("&;:()[],*=/^{}+-").find(c) != std::string::npos) {
            toks.push_back(Tok{TK::P, std::string(1, c), line});
            ++i;
        } else if (is_ident(c)) {
            std::size_t j = i;
            while (j < n && is_ident(src[j])) ++j;
            std::string text = src.substr(i, j - i);
            const TK k = text[0] == '$' ? TK::VAR : TK::ID;
            toks.push_back(Tok{k, std::move(text), line});
            i = j;
        } else {
            throw err("unexpected character " + py_repr(std::string(1, c)), line);
        }
    }
}
 
struct Call {
    std::string kind;  ///< synch-call | asynch-call
    std::string dst;
    Val v;
};
 
/** An entry phase or an activity: the s, c, f, Z, M values and the calls. */
struct Work {
    std::string name;
    Val s, c, f, Z, M;
    std::vector<Call> calls;
    Val& field(char k) {
        switch (k) {
            case 's': return s;
            case 'c': return c;
            case 'f': return f;
            case 'Z': return Z;
            default: return M;
        }
    }
};
 
struct Proc {
    std::string name, sched;
    Val quantum, mult, repl, speed;
    std::vector<std::size_t> groups;  ///< into Model::groups
    std::vector<std::size_t> tasks;   ///< into Model::tasks
};
 
struct Group {
    std::string name;
    Val share;
    bool cap = false;
    std::vector<std::size_t> tasks;
};
 
struct Task {
    std::string name, sched;
    std::vector<std::string> entries;
    std::string proc;
    Val prio, think, mult, repl, qlen;
    bool has_group = false;
    std::string group;
    std::vector<std::pair<std::string, Val>> fanin, fanout;
};
 
struct Entry {
    std::string name, task;
    std::map<int, Work> phases;
    bool has_start = false;
    std::string start;
    Val arrival, prio;
    std::string sem, rw;  ///< empty when not declared
    std::vector<std::pair<std::string, Val>> fwd;
};
 
struct Conn {
    std::string pre_kind;
    std::vector<std::string> pre;
    Val quorum;
    bool has_post = false;
    std::string post_kind;
    std::vector<std::pair<std::string, Val>> items;
    bool has_end = false;
    std::string end;
};
 
struct Acts {
    std::vector<Work> defs;
    std::map<std::string, std::size_t> by;
    std::vector<std::vector<std::string>> prec;
    std::vector<std::pair<std::string, std::string>> replies;  ///< (entry, activity)
    std::vector<Conn> conns;
};
 
struct Model {
    std::string comment;
    std::vector<std::pair<std::string, Val>> solver;
    std::vector<Proc> procs;
    std::map<std::string, std::size_t> proc_by;
    std::vector<Group> groups;
    std::vector<Task> tasks;
    std::map<std::string, std::size_t> task_by;
    std::map<std::string, Entry> entries;
    std::vector<std::string> entry_order;
    std::map<std::string, Acts> acts;
};
 
inline const char* proc_sched(const std::string& k) {
    static const std::map<std::string, const char*> t = {
        {"f", "fcfs"}, {"h", "hol"}, {"p", "pri"}, {"r", "rand"}, {"i", "inf"}, {"c", "cfs"}, {"s", "ps"}};
    std::map<std::string, const char*>::const_iterator it = t.find(k);
    return it == t.end() ? NULL : it->second;
}
 
inline const char* task_sched(const std::string& k) {
    static const std::map<std::string, const char*> t = {
        {"r", "ref"}, {"n", "fcfs"}, {"f", "fcfs"}, {"h", "hol"}, {"p", "pri"}, {"i", "inf"},
        {"P", "poll"}, {"b", "burst"}, {"u", "uniform"}, {"S", "semaphore"}, {"W", "rwlock"}};
    std::map<std::string, const char*>::const_iterator it = t.find(k);
    return it == t.end() ? NULL : it->second;
}
 
inline const char* rwlock_kind(const std::string& k) {
    if (k == "R") return "r-lock";
    if (k == "U") return "r-unlock";
    if (k == "W") return "w-lock";
    if (k == "X") return "w-unlock";
    return NULL;
}
 
}  // namespace srvn_detail
 
/**
 * Shortest C `%g` spelling that round-trips `x`; the four codebases share this rule.
 *
 * An integer below 1e15 in magnitude prints as `%d`; anything else as the
 * shortest `%.{p}g`, p = 1..17, that `strtod` reads back as `x`.
 *
 * @throws InputError (`LINE:input:Format`) when `x` is not finite (every caller checks first)
 */
inline std::string format_number(double x) {
    if (!std::isfinite(x)) throw InputError(ErrorKind{"Format"}, "format_number: the value is not finite");
    char buf[40];
    if (x == std::trunc(x) && std::fabs(x) < 1e15) {
        std::snprintf(buf, sizeof(buf), "%lld", static_cast<long long>(x));
        return buf;
    }
    for (int p = 1; p < 18; ++p) {
        std::snprintf(buf, sizeof(buf), "%.*g", p, x);
        if (std::strtod(buf, NULL) == x) return buf;
    }
    std::snprintf(buf, sizeof(buf), "%.17g", x);
    return buf;
}
 
namespace srvn_detail {
 
class Parser {
public:
    explicit Parser(const std::string& src) { tokenize(src, toks, pragmas); }
 
    std::vector<Tok> toks;
    std::vector<std::pair<std::string, std::string>> pragmas;
 
    Model parse() {
        Model m;
        parameters();
        expect("G");
        general(m);
        if (!at("P")) throw err("expected the processor section \"P\"", line());
        next();
        next();  // declared count, informational
        processors(m);
        if (at("U")) {
            next();
            next();
            groups(m);
        }
        expect("T");
        next();
        tasks(m);
        expect("E");
        next();
        entries(m);
        while (at("A")) {
            next();
            activities(m);
        }
        if (at("R")) {
            next();
            int depth = 0;
            while (true) {
                const Tok& t = next();
                if (t.text == "[" || t.text == "(") ++depth;
                else if (t.text == "]" || t.text == ")") --depth;
                else if (depth == 0 && t.kind == TK::NUM && t.text == "-1") break;
            }
        }
        // observation pairs may trail the document
        peek();
        if (pos < toks.size()) {
            const Tok& t = toks[pos];
            throw err("unexpected " + py_repr(t.text) + " after the last section", t.line);
        }
        if (!used_sweeps.empty()) {
            std::string names;
            for (std::size_t i = 0; i < used_sweeps.size(); ++i) names += (i ? ", " : "") + used_sweeps[i];
            throw UnsupportedError(ErrorKind{"Format"},
                "SRVN: the model uses the SPEX sweep parameter(s) " + names +
                "; LINE reads one value per parameter, so give each a scalar value (e.g. \"" +
                used_sweeps[0] + " = 1\")");
        }
        return m;
    }
 
private:
    std::size_t pos = 0;
    std::map<std::string, Val> params;
    std::map<std::string, int> sweeps;
    std::vector<std::string> used_sweeps;
 
    // -- token stream -----------------------------------------------------
    void skip_obs() {
        while (pos < toks.size() && toks[pos].kind == TK::OBS) {
            ++pos;
            if (pos < toks.size() && toks[pos].kind == TK::VAR) ++pos;
        }
    }
 
    const Tok* peek(int k = 0) {
        skip_obs();
        std::size_t p = pos;
        while (k > 0) {
            ++p;
            while (p < toks.size() && toks[p].kind == TK::OBS) {
                ++p;
                if (p < toks.size() && toks[p].kind == TK::VAR) ++p;
            }
            --k;
        }
        return p < toks.size() ? &toks[p] : NULL;
    }
 
    const Tok& next() {
        const Tok* t = peek();
        if (!t) throw err("unexpected end of input");
        ++pos;
        return *t;
    }
 
    int line() {
        const Tok* t = peek();
        return t ? t->line : (toks.empty() ? 1 : toks.back().line);
    }
 
    bool at(const char* text) {
        const Tok* t = peek();
        return t && t->text == text;
    }
 
    bool at_end_list() {
        const Tok* t = peek();
        return t && t->kind == TK::NUM && t->text == "-1";
    }
 
    void expect(const char* text) {
        const Tok& t = next();
        if (t.text != text) throw err("expected " + py_repr(text) + ", found " + py_repr(t.text), t.line);
    }
 
    void expect_end_list() {
        const Tok& t = next();
        if (!(t.kind == TK::NUM && t.text == "-1"))
            throw err("expected end of list \"-1\", found " + py_repr(t.text), t.line);
    }
 
    std::string ident(const std::string& what) {
        const Tok& t = next();
        if (t.kind != TK::ID && t.kind != TK::NUM)
            throw err("expected " + what + " name, found " + py_repr(t.text), t.line);
        return t.text;
    }
 
    // -- values -----------------------------------------------------------
    Val value(const std::string& what = "value") {
        const Tok& t = next();
        if (t.kind == TK::NUM) return Val(lstrip_plus(t.text), to_double(t.text));
        if (t.kind == TK::VAR) return lookup(t);
        throw err("expected a number for " + what + ", found " + py_repr(t.text), t.line);
    }
 
    bool is_value(int k = 0) {
        const Tok* t = peek(k);
        return t && (t->kind == TK::NUM || t->kind == TK::VAR) && !(t->kind == TK::NUM && t->text == "-1");
    }
 
    Val lookup(const Tok& t) {
        const std::string& name = t.text;
        if (sweeps.count(name)) {
            bool seen = false;
            for (const std::string& u : used_sweeps) seen = seen || u == name;
            if (!seen) used_sweeps.push_back(name);
            return Val("0", 0.0);
        }
        std::map<std::string, Val>::const_iterator it = params.find(name);
        if (it == params.end()) throw err("parameter " + name + " is used but not defined", t.line);
        return it->second;
    }
 
    std::vector<Val> value_list(const std::string& what) {
        std::vector<Val> vals;
        while (!at_end_list()) vals.push_back(value(what));
        expect_end_list();
        return vals;
    }
 
    // -- SPEX parameters ---------------------------------------------------
    void parameters() {
        while (true) {
            const Tok* a = peek();
            if (!a || a->kind != TK::VAR) break;
            const Tok* b = peek(1);
            if (!b || b->text != "=") break;
            const Tok vt = next();
            next();
            if (at("[")) {
                sweeps[vt.text] = vt.line;
                int depth = 0;
                while (true) {
                    const Tok& t = next();
                    if (t.text == "[") ++depth;
                    else if (t.text == "]") {
                        --depth;
                        if (depth == 0) break;
                    }
                }
                continue;
            }
            const std::size_t start = pos;
            const double v = expr();
            // pow overflow and domain errors, and overflowing products, all land here
            if (!std::isfinite(v)) throw err("parameter " + vt.text + " evaluates to a non-finite value", vt.line);
            const bool single = pos - start == 1 && toks[start].kind == TK::NUM;
            params[vt.text] = Val(single ? lstrip_plus(toks[start].text) : format_number(v), v);
        }
    }
 
    double expr() {
        double v = term();
        while (true) {
            const Tok* t = peek();
            if (t && t->kind == TK::P && (t->text == "+" || t->text == "-")) {
                const bool plus = next().text == "+";
                const double r = term();
                v = plus ? v + r : v - r;
            } else if (t && t->kind == TK::NUM && (t->text[0] == '+' || t->text[0] == '-')) {
                // "$y -1" tokenizes the operator into the number; parameter definitions are followed by
                // another "$x =" or by "G", never by a number, so a signed number here is a subtraction
                const double r = to_double(t->text);
                next();
                v = v + r;
            } else {
                return v;
            }
        }
    }
 
    double term() {
        double v = factor();
        while (at("*") || at("/")) {
            const Tok& ot = next();
            const bool mul = ot.text == "*";
            const double r = factor();
            if (!mul && r == 0) throw err("division by zero in a parameter expression", ot.line);
            v = mul ? v * r : v / r;
        }
        return v;
    }
 
    double factor() {
        const double b = unary();
        if (at("^")) {
            next();
            return std::pow(b, factor());
        }
        return b;
    }
 
    double unary() {
        if (at("-")) {
            next();
            return -unary();
        }
        if (at("+")) {
            next();
            return unary();
        }
        if (at("(")) {
            next();
            const double v = expr();
            expect(")");
            return v;
        }
        const Tok& t = next();
        if (t.kind == TK::NUM) return to_double(t.text);
        if (t.kind == TK::VAR) {
            if (sweeps.count(t.text))
                throw UnsupportedError(ErrorKind{"Format"},
                    "SRVN (line " + std::to_string(t.line) + "): a parameter expression uses the SPEX sweep " +
                    t.text + "; LINE reads one value per parameter, so give it a scalar value");
            return lookup(t).value;
        }
        throw err("malformed parameter expression at " + py_repr(t.text), t.line);
    }
 
    // -- document ---------------------------------------------------------
    void general(Model& m) {
        const Tok* t = peek();
        if (t && t->kind == TK::STR) m.comment = next().text;
        static const char* names[] = {"conv_val", "it_limit", "print_int", "underrelax_coeff"};
        std::size_t k = 0;
        while (!at_end_list()) {
            if (k >= 4) throw err("too many values in the general section", line());
            m.solver.emplace_back(names[k], value(names[k]));
            ++k;
        }
        expect_end_list();
    }
 
    void processors(Model& m) {
        while (!at_end_list()) {
            const int ln = line();
            expect("p");
            const std::string name = ident("processor");
            if (m.proc_by.count(name)) throw err("processor \"" + name + "\" is declared twice", ln);
            const Tok& t = next();
            const char* sched = proc_sched(t.text);
            if (!sched)
                throw err("unknown processor scheduling flag " + py_repr(t.text) + " for \"" + name + "\"", t.line);
            Proc p;
            p.name = name;
            p.sched = sched;
            if (t.text == "c" || t.text == "s") p.quantum = value("quantum");
            while (true) {
                if (at("m")) {
                    next();
                    p.mult = value("multiplicity");
                } else if (at("i")) {
                    next();
                    p.sched = "inf";
                } else if (at("r")) {
                    next();
                    p.repl = value("replication");
                } else if (at("R")) {
                    next();
                    p.speed = value("speed factor");
                } else {
                    break;
                }
            }
            m.proc_by[name] = m.procs.size();
            m.procs.push_back(p);
        }
        expect_end_list();
    }
 
    void groups(Model& m) {
        while (!at_end_list()) {
            const int ln = line();
            expect("g");
            const std::string name = ident("group");
            const Val share = value("share");
            bool cap = false;
            if (at("c")) {
                next();
                cap = true;
            }
            const std::string proc = ident("processor");
            if (!m.proc_by.count(proc))
                throw err("group \"" + name + "\" names the undeclared processor \"" + proc + "\"", ln);
            Group g;
            g.name = name;
            g.share = share;
            g.cap = cap;
            m.procs[m.proc_by[proc]].groups.push_back(m.groups.size());
            m.groups.push_back(g);
        }
        expect_end_list();
    }
 
    struct Fan {
        std::string kind, src, dst;
        Val v;
        int line;
    };
 
    void tasks(Model& m) {
        std::vector<Fan> fans;
        while (!at_end_list()) {
            const int ln = line();
            const Tok& t = next();
            if (t.text == "I" || t.text == "O") {
                Fan f;
                f.kind = t.text;
                f.line = t.line;
                f.src = ident("task");
                f.dst = ident("task");
                f.v = value("fan value");
                fans.push_back(f);
                continue;
            }
            if (t.text != "t") throw err("expected a task declaration \"t\", found " + py_repr(t.text), t.line);
            const std::string name = ident("task");
            if (m.task_by.count(name)) throw err("task \"" + name + "\" is declared twice", ln);
            const Tok& st = next();
            const char* sched = task_sched(st.text);
            if (!sched)
                throw err("unknown task scheduling flag " + py_repr(st.text) + " for \"" + name + "\"", st.line);
            Task task;
            task.name = name;
            task.sched = sched;
            while (!at_end_list()) task.entries.push_back(ident("entry"));
            expect_end_list();
            task.proc = ident("processor");
            if (!m.proc_by.count(task.proc))
                throw err("task \"" + name + "\" runs on the undeclared processor \"" + task.proc + "\"", ln);
            while (true) {
                if (is_value()) {
                    task.prio = value("priority");
                } else if (at("z")) {
                    next();
                    task.think = value("think time");
                } else if (at("m")) {
                    next();
                    task.mult = value("multiplicity");
                } else if (at("i")) {
                    next();
                    task.sched = "inf";
                } else if (at("r")) {
                    next();
                    task.repl = value("replication");
                } else if (at("g")) {
                    next();
                    task.has_group = true;
                    task.group = ident("group");
                } else if (at("q")) {
                    next();
                    task.qlen = value("queue length");
                } else {
                    break;
                }
            }
            for (const std::string& e : task.entries) {
                if (m.entries.count(e)) throw err("entry \"" + e + "\" is declared twice", ln);
                Entry en;
                en.name = e;
                en.task = name;
                m.entries[e] = en;
                m.entry_order.push_back(e);
            }
            const std::size_t ti = m.tasks.size();
            m.tasks.push_back(task);
            m.task_by[name] = ti;
            Proc& proc = m.procs[m.proc_by[task.proc]];
            if (task.has_group) {
                bool found = false;
                for (std::size_t gi : proc.groups) {
                    if (m.groups[gi].name == task.group) {
                        m.groups[gi].tasks.push_back(ti);
                        found = true;
                        break;
                    }
                }
                if (!found)
                    throw err("task \"" + name + "\" names group \"" + task.group + "\", which processor \"" +
                              proc.name + "\" does not declare", ln);
            } else {
                proc.tasks.push_back(ti);
            }
        }
        expect_end_list();
        for (const Fan& f : fans) {
            for (const std::string* nm : {&f.src, &f.dst})
                if (!m.task_by.count(*nm))
                    throw err(std::string("fan-") + (f.kind == "I" ? "in" : "out") + " names the undeclared task \"" +
                              *nm + "\"", f.line);
            if (f.kind == "O") m.tasks[m.task_by[f.src]].fanout.emplace_back(f.dst, f.v);
            else m.tasks[m.task_by[f.dst]].fanin.emplace_back(f.src, f.v);
        }
    }
 
    Entry& entry(Model& m, const std::string& name, int ln) {
        std::map<std::string, Entry>::iterator it = m.entries.find(name);
        if (it == m.entries.end()) throw err("entry \"" + name + "\" is not declared by any task", ln);
        return it->second;
    }
 
    static Work& phase(Entry& e, int k) { return e.phases[k]; }
 
    void entries(Model& m) {
        while (!at_end_list()) {
            const Tok t = next();
            const int ln = t.line;
            const std::string& k = t.text;
            if (k == "s" || k == "c" || k == "f" || k == "Z" || k == "M") {
                Entry& e = entry(m, ident("entry"), ln);
                const std::vector<Val> vals = value_list("phase value");
                for (std::size_t ph = 0; ph < vals.size(); ++ph) phase(e, static_cast<int>(ph + 1)).field(k[0]) = vals[ph];
            } else if (k == "y" || k == "z") {
                Entry& e = entry(m, ident("entry"), ln);
                const std::string dst = ident("entry");
                entry(m, dst, ln);
                const std::vector<Val> vals = value_list("call count");
                for (std::size_t ph = 0; ph < vals.size(); ++ph)
                    phase(e, static_cast<int>(ph + 1))
                        .calls.push_back(Call{k == "y" ? "synch-call" : "asynch-call", dst, vals[ph]});
            } else if (k == "F") {
                Entry& e = entry(m, ident("entry"), ln);
                const std::string dst = ident("entry");
                entry(m, dst, ln);
                e.fwd.emplace_back(dst, value("forwarding probability"));
                if (at_end_list()) next();
            } else if (k == "a") {
                Entry& e = entry(m, ident("entry"), ln);
                e.arrival = value("arrival rate");
            } else if (k == "A") {
                Entry& e = entry(m, ident("entry"), ln);
                e.has_start = true;
                e.start = ident("activity");
            } else if (k == "p") {
                Entry& e = entry(m, ident("entry"), ln);
                e.prio = value("priority");
            } else if (k == "P" || k == "V") {
                Entry& e = entry(m, ident("entry"), ln);
                e.sem = k == "P" ? "signal" : "wait";
            } else if (rwlock_kind(k)) {
                Entry& e = entry(m, ident("entry"), ln);
                e.rw = rwlock_kind(k);
            } else if (k == "H") {
                entry(m, ident("entry"), ln);
                value("phase");
                histogram();
            } else {
                throw err("unknown entry declaration " + py_repr(k), ln);
            }
        }
        expect_end_list();
    }
 
    /** `min : max nbins [type]`; a request for output, so it is read and dropped. */
    void histogram() {
        value("histogram minimum");
        expect(":");
        value("histogram maximum");
        value("histogram bins");
        if (at("log") || at("sqrt") || at("linear")) next();
    }
 
    void activities(Model& m) {
        const int ln = line();
        const std::string tname = ident("task");
        if (!m.task_by.count(tname)) throw err("activity section for the undeclared task \"" + tname + "\"", ln);
        if (m.acts.count(tname)) throw err("task \"" + tname + "\" has two activity sections", ln);
        Acts& A = m.acts[tname];
        while (!(at_end_list() || at(":"))) {
            const Tok t = next();
            const std::string& k = t.text;
            if (!(k == "s" || k == "c" || k == "f" || k == "Z" || k == "M" || k == "y" || k == "z" || k == "H"))
                throw err("unknown activity declaration " + py_repr(k) + " in task \"" + tname + "\"", t.line);
            const std::size_t ai = act(A, ident("activity"));
            if (k == "y" || k == "z") {
                const std::string dst = ident("entry");
                entry(m, dst, t.line);
                const Val v = value("call count");
                A.defs[ai].calls.push_back(Call{k == "y" ? "synch-call" : "asynch-call", dst, v});
            } else if (k == "H") {
                histogram();
            } else {
                const Val v = value("activity value");
                A.defs[ai].field(k[0]) = v;
            }
        }
        if (at(":")) {
            next();
            while (true) {
                connection(A, m, tname);
                if (at(";")) {
                    next();
                    continue;
                }
                break;
            }
        }
        expect_end_list();
        for (const std::vector<std::string>& names : A.prec)
            for (const std::string& nm : names)
                if (!A.by.count(nm))
                    throw err("activity \"" + nm + "\" of task \"" + tname +
                              "\" is used in the precedence graph but not defined", ln);
    }
 
    static std::size_t act(Acts& A, const std::string& name) {
        std::map<std::string, std::size_t>::const_iterator it = A.by.find(name);
        if (it != A.by.end()) return it->second;
        Work a;
        a.name = name;
        A.by[name] = A.defs.size();
        A.defs.push_back(a);
        return A.defs.size() - 1;
    }
 
    std::string actref(Acts& A, Model& m) {
        const std::string name = ident("activity");
        if (at("[")) {
            next();
            while (true) {
                const std::string e = ident("entry");
                entry(m, e, line());
                A.replies.emplace_back(e, name);
                if (at(",")) {
                    next();
                    continue;
                }
                break;
            }
            expect("]");
        }
        return name;
    }
 
    void connection(Acts& A, Model& m, const std::string& tname) {
        Conn rec;
        rec.pre.push_back(actref(A, m));
        rec.pre_kind = "pre";
        if (at("&")) {
            rec.pre_kind = "pre-AND";
            while (at("&")) {
                next();
                rec.pre.push_back(actref(A, m));
            }
            if (at("(")) {
                next();
                rec.quorum = value("quorum");
                expect(")");
            }
        } else if (at("+")) {
            rec.pre_kind = "pre-OR";
            while (at("+")) {
                next();
                rec.pre.push_back(actref(A, m));
            }
        }
        A.prec.push_back(rec.pre);
        if (at("->")) {
            next();
            rec.has_post = true;
            if (at("(")) {
                while (true) {
                    expect("(");
                    const Val p = value("branch probability");
                    expect(")");
                    const std::string a = actref(A, m);
                    rec.items.emplace_back(a, p);
                    if (at("+")) {
                        next();
                        continue;
                    }
                    break;
                }
                rec.post_kind = "post-OR";
            } else if (is_value() && peek(1) && peek(1)->text == "*") {
                const Val count = value("loop count");
                expect("*");
                const std::string body = actref(A, m);
                if (at(",")) {
                    next();
                    rec.has_end = true;
                    rec.end = actref(A, m);
                }
                rec.post_kind = "post-LOOP";
                rec.items.emplace_back(body, count);
            } else {
                std::vector<std::string> post;
                post.push_back(actref(A, m));
                std::string kind = "post";
                if (at("&")) {
                    kind = "post-AND";
                    while (at("&")) {
                        next();
                        post.push_back(actref(A, m));
                    }
                } else if (at("+")) {
                    throw err("an OR fork in task \"" + tname + "\" needs a probability on each branch, \"(p) act\"",
                              line());
                }
                rec.post_kind = kind;
                for (const std::string& x : post) rec.items.emplace_back(x, Val());
            }
            std::vector<std::string> names;
            for (const std::pair<std::string, Val>& it : rec.items) names.push_back(it.first);
            if (rec.has_end && !rec.end.empty()) names.push_back(rec.end);
            A.prec.push_back(names);
        }
        A.conns.push_back(rec);
    }
};
 
inline std::string attr(const char* name, const Val& v) {
    return std::string(" ") + name + "=\"" + esc(v.text) + "\"";
}
 
inline std::string activity_attrs(const Work& a, std::vector<const Call*>& calls) {
    // lqn-core.xsd requires host-demand-mean, and parseXML reads an absent one as NaN, not 0, so it is always written
    std::string s = a.s.has ? attr("host-demand-mean", a.s) : std::string(" host-demand-mean=\"0\"");
    if (a.c.has && nz(a.s)) s += attr("host-demand-cvsq", a.c);
    if (nz(a.Z)) s += attr("think-time", a.Z);
    if (nz(a.M)) s += attr("max-service-time", a.M);
    for (const Call& c : a.calls)
        if (c.v.value != 0) calls.push_back(&c);
    if (nz(a.f) && !calls.empty()) s += " call-order=\"DETERMINISTIC\"";
    return s;
}
 
inline void emit_activity(std::vector<std::string>& out, const std::string& ind, const std::string& head,
                          const Work& a) {
    std::vector<const Call*> calls;
    const std::string attrs = activity_attrs(a, calls);
    if (calls.empty()) {
        out.push_back(ind + "<activity" + head + attrs + "/>");
        return;
    }
    out.push_back(ind + "<activity" + head + attrs + ">");
    for (const Call* c : calls)
        out.push_back(ind + "  <" + c->kind + " dest=\"" + esc(c->dst) + "\" calls-mean=\"" + esc(c->v.text) + "\"/>");
    out.push_back(ind + "</activity>");
}
 
inline void emit_task(std::vector<std::string>& out, const std::string& ind, const Task& t, const Model& m) {
    std::string s = ind + "<task name=\"" + esc(t.name) + "\" scheduling=\"" + t.sched + "\"";
    if (t.mult.has && t.sched != "inf" && t.mult.value != 1) s += attr("multiplicity", t.mult);
    if (t.repl.has && t.repl.value != 1) s += attr("replication", t.repl);
    if (nz(t.think)) s += attr("think-time", t.think);
    if (t.prio.has) s += attr("priority", t.prio);
    if (t.qlen.has) s += attr("queue-length", t.qlen);
    out.push_back(s + ">");
    const std::string i2 = ind + "  ";
    for (const std::pair<std::string, Val>& f : t.fanin)
        out.push_back(i2 + "<fan-in source=\"" + esc(f.first) + "\" value=\"" + esc(f.second.text) + "\"/>");
    for (const std::pair<std::string, Val>& f : t.fanout)
        out.push_back(i2 + "<fan-out dest=\"" + esc(f.first) + "\" value=\"" + esc(f.second.text) + "\"/>");
    for (const std::string& en : t.entries) {
        const Entry& e = m.entries.at(en);
        if (e.has_start && !e.phases.empty())
            throw err("entry \"" + en + "\" declares both a start activity and phase parameters");
        s = i2 + "<entry name=\"" + esc(en) + "\" type=\"" + (e.has_start ? "NONE" : "PH1PH2") + "\"";
        if (nz(e.arrival)) s += attr("open-arrival-rate", e.arrival);
        if (e.prio.has) s += attr("priority", e.prio);
        if (!e.sem.empty()) s += " semaphore=\"" + e.sem + "\"";
        if (!e.rw.empty()) s += " rwlock=\"" + e.rw + "\"";
        std::vector<std::string> body;
        const std::string i3 = i2 + "  ";
        for (const std::pair<std::string, Val>& f : e.fwd)
            body.push_back(i3 + "<forwarding dest=\"" + esc(f.first) + "\" prob=\"" + esc(f.second.text) + "\"/>");
        if (!e.has_start) {
            std::vector<std::pair<int, const Work*>> phases;
            for (const std::pair<const int, Work>& kv : e.phases) {
                const Work& ph = kv.second;
                bool call = false;
                for (const Call& c : ph.calls) call = call || c.v.value != 0;
                if (nz(ph.s) || nz(ph.Z) || call) phases.emplace_back(kv.first, &ph);
            }
            if (!phases.empty()) {
                body.push_back(i3 + "<entry-phase-activities>");
                for (const std::pair<int, const Work*>& ph : phases) {
                    const std::string k = std::to_string(ph.first);
                    const std::string head = " name=\"" + esc(en + "_" + k) + "\" phase=\"" + k + "\"";
                    emit_activity(body, i3 + "  ", head, *ph.second);
                }
                body.push_back(i3 + "</entry-phase-activities>");
            }
        }
        if (!body.empty()) {
            out.push_back(s + ">");
            out.insert(out.end(), body.begin(), body.end());
            out.push_back(i2 + "</entry>");
        } else {
            out.push_back(s + "/>");
        }
    }
    std::map<std::string, Acts>::const_iterator ait = m.acts.find(t.name);
    if (ait != m.acts.end()) {
        const Acts& A = ait->second;
        std::map<std::string, std::string> bound;
        for (const std::string& en : t.entries) {
            const Entry& e = m.entries.at(en);
            if (e.has_start && !bound.count(e.start)) bound[e.start] = en;
        }
        out.push_back(i2 + "<task-activities>");
        const std::string i3 = i2 + "  ";
        for (const Work& a : A.defs) {
            std::string head = " name=\"" + esc(a.name) + "\"";
            std::map<std::string, std::string>::const_iterator b = bound.find(a.name);
            if (b != bound.end()) head += " bound-to-entry=\"" + esc(b->second) + "\"";
            emit_activity(out, i3, head, a);
        }
        const std::string i4 = i3 + "  ", i5 = i3 + "    ";
        for (const Conn& rec : A.conns) {
            out.push_back(i3 + "<precedence>");
            std::string q;
            if (rec.quorum.has && rec.quorum.value != static_cast<double>(rec.pre.size())) q = attr("quorum", rec.quorum);
            out.push_back(i4 + "<" + rec.pre_kind + q + ">");
            for (const std::string& nm : rec.pre) out.push_back(i5 + "<activity name=\"" + esc(nm) + "\"/>");
            out.push_back(i4 + "</" + rec.pre_kind + ">");
            if (rec.has_post) {
                const std::string e = rec.has_end ? " end=\"" + esc(rec.end) + "\"" : std::string();
                out.push_back(i4 + "<" + rec.post_kind + e + ">");
                for (const std::pair<std::string, Val>& it : rec.items) {
                    if (rec.post_kind == "post-OR")
                        out.push_back(i5 + "<activity name=\"" + esc(it.first) + "\"" + attr("prob", it.second) + "/>");
                    else if (rec.post_kind == "post-LOOP")
                        out.push_back(i5 + "<activity name=\"" + esc(it.first) + "\"" + attr("count", it.second) + "/>");
                    else
                        out.push_back(i5 + "<activity name=\"" + esc(it.first) + "\"/>");
                }
                out.push_back(i4 + "</" + rec.post_kind + ">");
            }
            out.push_back(i3 + "</precedence>");
        }
        std::vector<std::string> order;
        for (const std::pair<std::string, std::string>& r : A.replies) {
            bool seen = false;
            for (const std::string& o : order) seen = seen || o == r.first;
            if (!seen) order.push_back(r.first);
        }
        for (const std::string& en : order) {
            const Entry& e = m.entries.at(en);
            if (e.task != t.name)
                throw err("activity of task \"" + t.name + "\" replies to entry \"" + en + "\" of task \"" + e.task +
                          "\"");
            out.push_back(i3 + "<reply-entry name=\"" + esc(en) + "\">");
            std::vector<std::string> seen;
            for (const std::pair<std::string, std::string>& r : A.replies) {
                if (r.first != en) continue;
                bool dup = false;
                for (const std::string& x : seen) dup = dup || x == r.second;
                if (dup) continue;
                seen.push_back(r.second);
                out.push_back(i4 + "<reply-activity name=\"" + esc(r.second) + "\"/>");
            }
            out.push_back(i3 + "</reply-entry>");
        }
        out.push_back(i2 + "</task-activities>");
    } else {
        for (const std::string& en : t.entries) {
            const Entry& e = m.entries.at(en);
            if (e.has_start)
                throw err("entry \"" + en + "\" starts at activity \"" + e.start + "\", but task \"" + t.name +
                          "\" has no activity section");
        }
    }
    out.push_back(ind + "</task>");
}
 
/** Python's `os.path.splitext(os.path.basename(path))[0]`. */
inline std::string stem(const std::string& path) {
    const std::size_t slash = path.find_last_of('/');
    const std::string base = slash == std::string::npos ? path : path.substr(slash + 1);
    const std::size_t dot = base.rfind('.');
    const std::size_t first = base.find_first_not_of('.');
    if (dot == std::string::npos || first == std::string::npos || dot < first) return base;
    return base.substr(0, dot);
}
 
/** The file as Python's text mode reads it: universal newlines, so `\r\n` and `\r` become `\n`. */
inline std::string read_text(const std::string& path) {
    std::ifstream f(path.c_str(), std::ios::binary);
    if (!f) throw InputError(ErrorKind{"File"}, "File cannot be found: " + path);
    std::ostringstream ss;
    ss << f.rdbuf();
    const std::string raw = ss.str();
    std::string s;
    s.reserve(raw.size());
    for (std::size_t i = 0; i < raw.size(); ++i) {
        if (raw[i] == '\r') {
            s += '\n';
            if (i + 1 < raw.size() && raw[i + 1] == '\n') ++i;
        } else {
            s += raw[i];
        }
    }
    return s;
}
 
}  // namespace srvn_detail
 
/**
 * Translate SRVN text into an LQN XML document.
 *
 * @param src   the SRVN document text
 * @param name  the model name written to `<lqn-model name=...>`
 * @return      the `.lqnx` document, newline-terminated
 * @throws InputError (`LINE:input:Format`) on a syntax or reference error
 * @throws UnsupportedError (`LINE:unsupported:Format`) when the model uses a SPEX sweep
 */
inline std::string srvn2lqnx(const std::string& src, const std::string& name = std::string("model")) {
    using namespace srvn_detail;
    Parser p(src);
    const Model m = p.parse();
    std::vector<std::string> out;
    out.push_back("<?xml version=\"1.0\"?>");
    out.push_back("<lqn-model name=\"" + esc(name) + "\" description=\"srvn2lqnx\">");
    std::string s = "  <solver-params comment=\"" + esc(m.comment) + "\"";
    for (const std::pair<std::string, Val>& kv : m.solver) s += attr(kv.first.c_str(), kv.second);
    if (!p.pragmas.empty()) {
        out.push_back(s + ">");
        for (const std::pair<std::string, std::string>& kv : p.pragmas)
            out.push_back("    <pragma param=\"" + esc(kv.first) + "\" value=\"" + esc(kv.second) + "\"/>");
        out.push_back("  </solver-params>");
    } else {
        out.push_back(s + "/>");
    }
    for (const Proc& proc : m.procs) {
        s = "  <processor name=\"" + esc(proc.name) + "\" scheduling=\"" + proc.sched + "\"";
        if (proc.quantum.has) s += attr("quantum", proc.quantum);
        if (proc.mult.has && proc.sched != "inf" && proc.mult.value != 1) s += attr("multiplicity", proc.mult);
        if (proc.repl.has && proc.repl.value != 1) s += attr("replication", proc.repl);
        if (proc.speed.has && proc.speed.value != 1) s += attr("speed-factor", proc.speed);
        out.push_back(s + ">");
        for (std::size_t gi : proc.groups) {
            const Group& g = m.groups[gi];
            out.push_back("    <group name=\"" + esc(g.name) + "\"" + attr("share", g.share) +
                          (g.cap ? " cap=\"true\"" : "") + ">");
            for (std::size_t ti : g.tasks) emit_task(out, "      ", m.tasks[ti], m);
            out.push_back("    </group>");
        }
        for (std::size_t ti : proc.tasks) emit_task(out, "    ", m.tasks[ti], m);
        out.push_back("  </processor>");
    }
    out.push_back("</lqn-model>");
    std::string doc;
    for (const std::string& l : out) {
        doc += l;
        doc += '\n';
    }
    return doc;
}
 
/**
 * True when `path` holds SRVN text rather than XML: its first non-blank
 * character is not '<'. An empty file counts as SRVN, as in the reference.
 *
 * @throws InputError (`LINE:input:File`) when the file cannot be opened
 */
inline bool is_srvn_file(const std::string& path) {
    std::ifstream f(path.c_str(), std::ios::binary);
    if (!f) throw InputError(ErrorKind{"File"}, "File cannot be found: " + path);
    char buf[4096];
    f.read(buf, sizeof(buf));
    const std::streamsize got = f.gcount();
    for (std::streamsize i = 0; i < got; ++i)
        if (!srvn_detail::is_space(buf[i])) return buf[i] != '<';
    return true;
}
 
/**
 * Whether `path` should be read as SRVN: a `.in` file, or a `.lqn` file that is
 * not XML. This is the line-cli and loader rule; `.lqnx` and `.xml` are never SRVN.
 */
inline bool is_srvn_path(const std::string& path) {
    const std::size_t dot = path.find_last_of('.');
    const std::size_t slash = path.find_last_of('/');
    if (dot == std::string::npos || (slash != std::string::npos && dot < slash)) return false;
    std::string ext = path.substr(dot + 1);
    for (char& c : ext) c = static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
    if (ext == "in") return true;
    if (ext != "lqn") return false;
    std::ifstream f(path.c_str(), std::ios::binary);
    return !f || is_srvn_file(path);
}
 
/**
 * Translate the SRVN file `path` to `.lqnx` text, model name = its basename
 * without extension. Errors name the file: "SRVN <path> (line n): ...".
 */
inline std::string srvn_file_to_lqnx(const std::string& path) {
    const std::string src = srvn_detail::read_text(path);
    const std::string name = srvn_detail::stem(path);
    try {
        return srvn2lqnx(src, name);
    } catch (const UnsupportedError& e) {
        std::string msg = e.what();
        if (msg.compare(0, 4, "SRVN") == 0) msg = "SRVN " + path + msg.substr(4);
        throw UnsupportedError(ErrorKind{e.kind()}, msg);
    } catch (const InputError& e) {
        std::string msg = e.what();
        if (msg.compare(0, 4, "SRVN") == 0) msg = "SRVN " + path + msg.substr(4);
        throw InputError(ErrorKind{e.kind()}, msg);
    }
}
 
/**
 * Read an SRVN file (`.in`, or a `.lqn` that is not XML) into the intermediate
 * `LqnModel`, via its `.lqnx` translation.
 */
template <class T>
LqnModel<T> read_srvn_model(const std::string& path) {
    return read_lqnx_model_text<T>(srvn_file_to_lqnx(path));
}
 
/** `read_srvn_model` followed by `lqn_finalize`: the struct SolverLN consumes, as `read_lqnx` is. */
template <class T>
LqnStruct<T> read_srvn(const std::string& path) {
    return lqn_finalize(read_srvn_model<T>(path));
}
 
}  // namespace lqn
}  // namespace line
 
#endif  // LINE_LANG_LQN_SRVN_READER_H