/* Line Discipline: what a terminal in canonical mode does between the key and
 * the read().
 *
 * Four stages, each consuming the last one's output. A key makes a byte. The
 * byte is classified against a handful of special characters and either edits
 * the line waiting in the kernel or joins it. Two of those characters release
 * the line: newline, which goes with it, and the end-of-file character, which
 * does not. And read() takes released lines, at most one per call, as many
 * bytes of it as it asked for.
 *
 * The point the page rests on is in the third stage. Ctrl-D does not send an
 * end of file. It releases whatever is waiting, and a read() of nothing is
 * what a program calls the end of a file. The Seventh Edition manual says so
 * in 1979 and POSIX says it in nearly the same words.
 *
 * What is modelled is what a Linux pty does, because that is what the oracle
 * in scripts/line-discipline-pty.py can ask. Every result this file produces
 * for the keys the page offers is compared in tests/line-discipline.test.mjs
 * with a real kernel's read() results, in order. What a Linux terminal does
 * that this file does not model is refused by name rather than guessed at.
 */
(function () {
  "use strict";

  /* ---- stage 1: the key and the byte ------------------------------------- */

  /* Ctrl with a letter sends the letter's code with the top two of its seven
   * bits cleared. That rule is the ASCII bit's subject and is not argued here;
   * it is applied, so Ctrl-D and Ctrl-U are computed rather than typed. */
  function ctrl(letter) { return letter.toUpperCase().charCodeAt(0) & 0x1f; }

  var DEL = 0x7f, BS = ctrl("H"), CR = ctrl("M"), NL = ctrl("J");

  /* The keys the page offers. Backspace has no byte of its own: the terminal
   * decides, and the two it can send are DEL and BS. Enter sends a carriage
   * return, which the line discipline turns into a newline (ICRNL). */
  var KEYS = [
    { id: "h", label: "h", byte: 0x68 },
    { id: "i", label: "i", byte: 0x69 },
    { id: "o", label: "o", byte: 0x6f },
    { id: "x", label: "x", byte: 0x78 },
    { id: "backspace", label: "Backspace", byte: null },
    { id: "ctrl-u", label: "Ctrl-U", byte: ctrl("U") },
    { id: "ctrl-d", label: "Ctrl-D", byte: ctrl("D") },
    { id: "enter", label: "Enter", byte: CR }
  ];
  var BACKSPACE_SENDS = [DEL, BS];
  /* The read sizes the page offers, largest first. */
  var READ_SIZES = [4096, 2, 1];

  function key(id) {
    for (var i = 0; i < KEYS.length; i += 1) if (KEYS[i].id === id) return KEYS[i];
    return null;
  }

  /** The byte a key sends, given what this terminal's Backspace sends. */
  function byteOf(id, backspaceSends) {
    var k = key(id);
    if (!k) return null;
    if (k.byte !== null) return k.byte;
    return BACKSPACE_SENDS.indexOf(backspaceSends) >= 0 ? backspaceSends : null;
  }

  /* ---- stage 2: the special characters ---------------------------------- */

  /* A new Linux pty's defaults, the ones this page models. The fixture records
   * the kernel's own c_cc, and the test compares these against it. ERASE is
   * the one a reader can change, because it is the one that disagrees with a
   * keyboard: some terminals send BS for Backspace, and `stty erase ^H` is how
   * the line discipline is told. */
  var DEFAULTS = { erase: DEL, kill: ctrl("U"), eof: ctrl("D") };

  /* Seventh Edition's defaults, from its tty.h and tty(4). Not modelled: they
   * are here so the page prints them from one place. In 1979 DEL was the
   * interrupt key, not the erase key. */
  var SEVENTH = { erase: 0x23, kill: 0x40, eof: ctrl("D"), intr: DEL,
                  line: 256 };

  /* Characters a new Linux pty treats specially that this page does NOT model,
   * and what each does instead, plus NUL, which Linux reads as ordinary but
   * the page does not offer. A sequence containing one is refused, never
   * run as if the byte were ordinary. ^O (VDISCARD) is not here because Linux
   * does not implement it and passes it through; the oracle confirms that. */
  var NOT_MODELLED = {};
  NOT_MODELLED[ctrl("C")] = "INTR: sends SIGINT to the foreground process group (ISIG)";
  NOT_MODELLED[0x1c] = "QUIT: sends SIGQUIT (ISIG)";
  NOT_MODELLED[ctrl("Z")] = "SUSP: sends SIGTSTP (ISIG)";
  NOT_MODELLED[ctrl("Q")] = "START: resumes output (IXON)";
  NOT_MODELLED[ctrl("S")] = "STOP: suspends output (IXON)";
  NOT_MODELLED[ctrl("W")] = "WERASE: erases a word (Linux, IEXTEN)";
  NOT_MODELLED[ctrl("R")] = "REPRINT: reprints the line (Linux, IEXTEN)";
  NOT_MODELLED[ctrl("V")] = "LNEXT: makes the next byte literal (Linux, IEXTEN)";
  NOT_MODELLED[0x00] = "NUL: Linux reads it as an ordinary byte, but it is also the value that "
    + "disables a special character, and this page does not offer it";

  function settings(s) {
    var o = s || {};
    return {
      erase: o.erase === undefined ? DEFAULTS.erase : o.erase,
      kill: DEFAULTS.kill,
      eof: DEFAULTS.eof
    };
  }

  /** What the line discipline does with one input byte. */
  function classify(b, s) {
    var t = settings(s);
    if (typeof b !== "number" || b < 0 || b > 0x7f) {
      return { kind: "refused", reason: "not a seven-bit byte; multibyte erase (IUTF8) is not modelled" };
    }
    // ICRNL comes first: a carriage return is a newline by the time anything
    // else looks at it, so it is classified as one.
    var input = b === CR ? NL : b;
    // An ERASE set to a byte in NOT_MODELLED is refused outright: Linux acts on
    // INTR, QUIT, SUSP, START and STOP before ERASE, and an ERASE of NUL is
    // disabled, so running it as an erase would be wrong.
    if (Object.prototype.hasOwnProperty.call(NOT_MODELLED, t.erase)) {
      return { kind: "refused", reason: "ERASE is set to " + NOT_MODELLED[t.erase].split(":")[0]
        + ", which this page does not model" };
    }
    // ERASE is checked before KILL, EOF and newline, as Linux does.
    if (input === t.erase) return { kind: "erase", input: input };
    if (input === t.kill) return { kind: "kill", input: input };
    if (input === t.eof) return { kind: "eof", input: input };
    if (input === NL) return { kind: "newline", input: input, mapped: b === CR };
    if (Object.prototype.hasOwnProperty.call(NOT_MODELLED, input)) {
      return { kind: "refused", reason: NOT_MODELLED[input] };
    }
    return { kind: "ordinary", input: input };
  }

  /* ---- stages 2 and 3: edit the line, and release it --------------------- */

  /** Feed bytes through the discipline. Lines released, and what is waiting. */
  function type(bytes, s) {
    var buf = [], lines = [], steps = [], refused = null;
    for (var i = 0; i < bytes.length; i += 1) {
      var c = classify(bytes[i], s);
      var before = buf.slice();
      if (c.kind === "refused") { refused = { at: i, byte: bytes[i], reason: c.reason }; break; }
      var released = null;
      if (c.kind === "erase") {
        // Not beyond the start of the line: a released line is gone.
        if (buf.length) buf.pop();
      } else if (c.kind === "kill") {
        buf = [];
      } else if (c.kind === "eof") {
        // The EOF character is discarded. What was waiting goes, as it is.
        released = { data: buf, by: "eof" };
        lines.push(released);
        buf = [];
      } else if (c.kind === "newline") {
        buf.push(NL);
        released = { data: buf, by: "newline" };
        lines.push(released);
        buf = [];
      } else {
        buf.push(c.input);
      }
      steps.push({ byte: bytes[i], kind: c.kind, mapped: !!c.mapped,
                   before: before, after: buf.slice(),
                   released: released ? released.data.slice() : null });
    }
    return { steps: steps, lines: lines, pending: buf, refused: refused };
  }

  /* ---- stage 4: read() ---------------------------------------------------- */

  /** Every read(fd, buf, size) that returns before one would wait. At most one
   * line per call, and as many of its bytes as were asked for; a line released
   * by EOF with nothing in it is a read of zero bytes. */
  function reads(lines, size) {
    var n = Math.floor(size);
    var out = [];
    if (!(n >= 1)) return out;
    for (var li = 0; li < lines.length; li += 1) {
      var data = lines[li].data, pos = 0;
      do {
        var take = Math.min(n, data.length - pos);
        out.push({ bytes: data.slice(pos, pos + take), line: li, by: lines[li].by });
        pos += take;
      } while (pos < data.length);
    }
    return out;
  }

  function run(bytes, s, size) {
    var t = type(bytes, s);
    return { steps: t.steps, lines: t.lines, pending: t.pending,
             refused: t.refused, reads: reads(t.lines, size || 4096) };
  }

  /** The same thing from key ids, which is what the page's buttons hold. */
  function press(ids, opts) {
    var o = opts || {};
    var bs = o.backspace === undefined ? DEL : o.backspace;
    var bytes = [];
    for (var i = 0; i < ids.length; i += 1) {
      var b = byteOf(ids[i], bs);
      if (b === null) return { refused: { at: i, key: ids[i], reason: "no such key" },
                               steps: [], lines: [], pending: [], reads: [], bytes: bytes };
      bytes.push(b);
    }
    var r = run(bytes, { erase: o.erase }, o.read);
    r.bytes = bytes;
    return r;
  }

  /* ---- printing ------------------------------------------------------------ */

  var NAMES = {};
  NAMES[DEL] = "DEL"; NAMES[BS] = "BS"; NAMES[CR] = "CR"; NAMES[NL] = "NL";
  NAMES[ctrl("D")] = "EOT"; NAMES[ctrl("U")] = "NAK";

  function hex(b) { return "0x" + (b < 16 ? "0" : "") + b.toString(16); }

  /** Bytes as a reader would write them: printable as is, the rest as ^X. */
  function show(bytes) {
    var s = "";
    for (var i = 0; i < bytes.length; i += 1) {
      var b = bytes[i];
      if (b === NL) s += "\\n";
      else if (b === 0x5c) s += "\\\\";
      else if (b >= 0x20 && b < 0x7f) s += String.fromCharCode(b);
      else s += "^" + String.fromCharCode(b === DEL ? 0x3f : b + 0x40);
    }
    return s;
  }

  /* ---- the claims, measured when the page loads --------------------------- */

  function same(a, b) {
    if (a.length !== b.length) return false;
    for (var i = 0; i < a.length; i += 1) if (a[i] !== b[i]) return false;
    return true;
  }
  function text(s) {
    var out = [];
    for (var i = 0; i < s.length; i += 1) out.push(s.charCodeAt(i));
    return out;
  }
  function readsOf(ids, opts) {
    var r = press(ids, opts);
    return r.refused ? null : r.reads.map(function (x) { return x.bytes; });
  }
  function readsAre(got, want) {
    return !!got && got.length === want.length
      && want.every(function (w, i) { return same(got[i], text(w)); });
  }
  function said(got) {
    if (!got) return "refused";
    if (!got.length) return "no read() returns";
    return got.map(function (b) { return b.length ? '"' + show(b) + '"' : "0 bytes"; })
      .join(", then ");
  }

  /* Every sequence of up to `longest` keys from the page's own keyboard. */
  function sweep(longest, opts, visit) {
    var ids = KEYS.map(function (k) { return k.id; });
    var seq = [];
    function walk(depth) {
      if (seq.length) visit(seq, press(seq, opts));
      if (depth === longest) return;
      for (var i = 0; i < ids.length; i += 1) {
        seq.push(ids[i]); walk(depth + 1); seq.pop();
      }
    }
    walk(0);
  }

  function verify() {
    var out = [];

    // The two witnesses the roster was admitted on.
    var empty = readsOf(["ctrl-d"]);
    out.push({
      claim: "Ctrl-D on an empty line makes read() return zero bytes",
      ok: readsAre(empty, [""]),
      detail: said(empty)
    });
    var hi = readsOf(["h", "i", "ctrl-d"]);
    out.push({
      claim: "after hi, the same key makes read() return the two bytes hi, and no end of file",
      ok: readsAre(hi, ["hi"]),
      detail: said(hi)
    });
    var twice = readsOf(["h", "i", "ctrl-d", "ctrl-d"]);
    out.push({
      claim: "pressed twice after hi, the second Ctrl-D is the one a program reads as the end",
      ok: readsAre(twice, ["hi", ""]),
      detail: said(twice)
    });
    var nl = readsOf(["h", "i", "enter", "ctrl-d"]);
    out.push({
      claim: "after Enter, one Ctrl-D is enough, because the line it would flush is empty",
      ok: readsAre(nl, ["hi\n", ""]),
      detail: said(nl)
    });

    // Over every sequence of up to five keys, counted two ways: zero-byte
    // reads from the read() side, and EOFs that found the line empty from the
    // keystroke side.
    var seqs = 0, zeroReads = 0, emptyFlushes = 0, eofLeaks = 0, editLeaks = 0,
        multiLine = 0, bigEqualsSmall = 0, notRun = 0;
    sweep(5, {}, function (ids, r) {
      seqs += 1;
      if (r.refused) { notRun += 1; return; }
      r.reads.forEach(function (x) {
        if (!x.bytes.length) zeroReads += 1;
        if (x.bytes.indexOf(DEFAULTS.eof) >= 0) eofLeaks += 1;
        if (x.bytes.indexOf(DEFAULTS.erase) >= 0 || x.bytes.indexOf(DEFAULTS.kill) >= 0) editLeaks += 1;
      });
      // Every size the page offers, since the claim is about all of them.
      READ_SIZES.forEach(function (n) {
        (n === 4096 ? r.reads : reads(r.lines, n)).forEach(function (x) {
          var nlAt = x.bytes.indexOf(NL);
          if (nlAt >= 0 && nlAt !== x.bytes.length - 1) multiLine += 1;
        });
      });
      r.steps.forEach(function (st) {
        if (st.kind === "eof" && st.before.length === 0) emptyFlushes += 1;
      });
      // One byte at a time gives the same bytes, and the same ends of file.
      var one = reads(r.lines, 1);
      var flat = function (list) {
        return list.reduce(function (acc, x) { return acc.concat(x.bytes); }, []);
      };
      var zeros = function (list) {
        return list.filter(function (x) { return !x.bytes.length; }).length;
      };
      if (same(flat(one), flat(r.reads)) && zeros(one) === zeros(r.reads)) bigEqualsSmall += 1;
    });
    out.push({
      claim: "over all " + seqs.toLocaleString("en-US") + " sequences of up to five keys, a read() "
        + "returns zero bytes exactly when Ctrl-D found the line empty",
      ok: zeroReads > 0 && zeroReads === emptyFlushes && notRun === 0,
      untested: zeroReads === 0,
      detail: zeroReads.toLocaleString("en-US") + " zero-byte reads, "
        + emptyFlushes.toLocaleString("en-US") + " empty flushes"
    });
    out.push({
      claim: "and in none of them does the program receive the Ctrl-D, the erase or the kill byte",
      ok: seqs > 0 && notRun === 0 && eofLeaks === 0 && editLeaks === 0,
      untested: seqs === 0,
      detail: eofLeaks + " reads hold 0x04, " + editLeaks + " hold an editing byte"
    });
    out.push({
      claim: "no read() returns more than one line, however many bytes it asks for",
      ok: seqs > 0 && multiLine === 0,
      untested: seqs === 0,
      detail: multiLine + " reads run past a newline, asking for "
        + READ_SIZES.join(", ").replace(/, (\d+)$/, " or $1") + " bytes"
    });
    out.push({
      claim: "asking for one byte at a time loses nothing: the same bytes and the same ends of file",
      ok: seqs > 0 && bigEqualsSmall === seqs - notRun && notRun === 0,
      untested: seqs === 0,
      detail: bigEqualsSmall.toLocaleString("en-US") + " of " + seqs.toLocaleString("en-US") + " agree"
    });

    // Erase and kill, and the walls they stop at.
    var erased = readsOf(["h", "i", "x", "backspace", "enter"]);
    out.push({
      claim: "Backspace takes the x back before any program sees it",
      ok: readsAre(erased, ["hi\n"]),
      detail: said(erased)
    });
    var wall = readsOf(["h", "i", "ctrl-d", "backspace", "backspace", "enter"]);
    out.push({
      claim: "and cannot reach back past a line Ctrl-D has already released",
      ok: readsAre(wall, ["hi", "\n"]),
      detail: said(wall)
    });
    var killed = readsOf(["x", "o", "x", "ctrl-u", "h", "i", "enter"]);
    out.push({
      claim: "Ctrl-U throws the whole waiting line away",
      ok: readsAre(killed, ["hi\n"]),
      detail: said(killed)
    });

    // Enter is a carriage return until the discipline says otherwise.
    var enter = press(["enter"]);
    out.push({
      claim: "Enter sends a carriage return, 0x0d, and the program reads a newline, 0x0a",
      ok: !enter.refused && same(enter.bytes, [0x0d]) && readsAre(enter.reads.map(function (x) {
        return x.bytes; }), ["\n"]),
      detail: hex(enter.bytes[0]) + " typed, " + said(enter.reads.map(function (x) { return x.bytes; })) + " read"
    });

    // The mismatch: a Backspace that sends BS to a terminal whose ERASE is DEL.
    var bsIn = readsOf(["h", "i", "backspace", "enter"], { backspace: BS });
    out.push({
      claim: "a Backspace that sends BS to a line discipline expecting DEL puts a ^H in the line",
      ok: readsAre(bsIn, ["hi\b\n"]),
      detail: said(bsIn)
    });
    var bsFixed = readsOf(["h", "i", "backspace", "enter"], { backspace: BS, erase: BS });
    out.push({
      claim: "and after stty erase ^H the same key erases",
      ok: readsAre(bsFixed, ["h\n"]),
      detail: said(bsFixed)
    });

    // Ctrl-D is computed from the ASCII rule, so check it lands on EOT.
    out.push({
      claim: "Ctrl-D is 0x04 and Ctrl-U is 0x15: each letter with its top two bits cleared",
      ok: ctrl("D") === 0x04 && ctrl("U") === 0x15 && DEFAULTS.eof === 0x04,
      detail: "D is 0x44 and U is 0x55; the ASCII bit explains the rule"
    });

    return out;
  }

  window.LineDiscipline = {
    KEYS: KEYS,
    BACKSPACE_SENDS: BACKSPACE_SENDS,
    READ_SIZES: READ_SIZES,
    DEFAULTS: DEFAULTS,
    SEVENTH: SEVENTH,
    NOT_MODELLED: NOT_MODELLED,
    DEL: DEL, BS: BS, CR: CR, NL: NL,
    ctrl: ctrl,
    key: key,
    byteOf: byteOf,
    classify: classify,
    type: type,
    reads: reads,
    run: run,
    press: press,
    hex: hex,
    show: show,
    sweep: sweep,
    verify: verify
  };
})();