import data; struct Parser { pos: i64, end: i64, source: Span, depth: i64 = 0, declarations: i64 = 0, offset: i64 = 0, line: i64 = 1, path: Span = Span { 0, 0 }, } enum ListMode { Line, Multiline } var parse_incomplete = false; var parse_continued = false; const MAX_PARSE_DEPTH = 256; const UTF8_CONT_MASK = 0xc0; const UTF8_CONT_TAG = 0x80; struct Here { token: i64, delimiter: Span, quoted: i64 } var here_pending: Here[>..] = []; fn syntax_error(message: u8[:]) -> i64 { parse_error = save(message); return -1 from parse; } fn special(c: u8) -> bool { contains(" \t\r\n#;&|^$=`'{}()<>", c) } fn name_char(c: u8) -> bool { ascii::is_alnum(c) || c == '_' || c == '*' } fn emit(kind: TokenKind, s: u8[:], start: i64, end: i64) { tokens.push(Token { kind, save(s), start, end }); } fn lex(s: u8[:]) { if contains(s, 0) { syntax_error("NUL byte in source"); } var i = 0; var here_op = false; var pending = here_pending.len; while i < s.len { let start = i; let c = s[i]; i += 1; if c == ' ' || c == '\t' || c == '\r' { continue; } if c == '\\' && i < s.len && s[i] == '\n' { i += 1; if i == s.len { parse_continued = true; } continue; } if c == '#' { while i < s.len && s[i] != '\n' { i += 1; } continue; } if c == '\'' { let out = text.len; var closed = false; while i < s.len { let q = s[i]; i += 1; if q != '\'' { text.push(q); continue; } if i < s.len && s[i] == '\'' { text.push('\''); i += 1; continue; } closed = true; break; } if !closed { parse_incomplete = true; syntax_error("unterminated quote"); } tokens.push(Token { TokenKind.Quoted, Span { out, text.len - out }, start, i }); if here_op { here_pending.push(Here { tokens.len - 1, tokens[tokens.len - 1].text, 1 }); tokens[tokens.len - 1].kind = TokenKind.HereQuoted; here_op = false; } continue; } if c == '$' { var kind = TokenKind.Var; if i < s.len && s[i] == '#' { kind = TokenKind.Count; i += 1; } else if i < s.len && s[i] == '"' { kind = TokenKind.Join; i += 1; } let begin = i; while i < s.len && name_char(s[i]) { i += 1; } if i == begin && kind == TokenKind.Var { kind = TokenKind.Dollar; } emit(kind, s[begin..i], start, i); continue; } var kind = TokenKind.Word; match c { '\n' => { kind = TokenKind.Semi; }, ';' => { kind = TokenKind.Semi; }, '(' => { kind = TokenKind.Lparen; }, ')' => { kind = TokenKind.Rparen; }, '{' => { kind = TokenKind.Lbrace; }, '}' => { kind = TokenKind.Rbrace; }, '^' => { kind = TokenKind.Caret; }, '=' => { kind = TokenKind.Equal; }, '`' => { kind = TokenKind.Backtick; }, '&' => { kind = TokenKind.Amp; if i < s.len && s[i] == '&' { kind = TokenKind.And; i += 1; } }, '|' => { kind = TokenKind.Pipe; if i < s.len && s[i] == '|' { kind = TokenKind.Or; i += 1; } }, '<' => { kind = TokenKind.Redir; if i < s.len && (s[i] == '<' || s[i] == '>') { i += 1; } }, '>' => { kind = TokenKind.Redir; if i < s.len && s[i] == '>' { i += 1; } }, _ => {}, } if (kind == TokenKind.Redir || kind == TokenKind.Pipe) && i < s.len && s[i] == '[' { i += 1; while i < s.len && s[i] != ']' { i += 1; } if i == s.len { parse_incomplete = true; syntax_error("unterminated descriptor qualifier"); } i += 1; } if kind == TokenKind.Word { while i < s.len && !special(s[i]) { if s[i] == '\\' && i + 1 < s.len && s[i + 1] == '\n' { break; } i += 1; } } emit(kind, s[start..i], start, i); if here_op && kind == TokenKind.Word { here_pending.push(Here { tokens.len - 1, tokens[tokens.len - 1].text, 0 }); tokens[tokens.len - 1].kind = TokenKind.Here; here_op = false; } if kind == TokenKind.Redir && starts_with(s[start..i], "<<") { here_op = true; } if c == '\n' { while pending < here_pending.len { let h = here_pending[pending]; pending += 1; let body = i; var found = false; while i < s.len { let line = i; while i < s.len && s[i] != '\n' { i += 1; } if s[line..i] == view(h.delimiter) { tokens[h.token].text = save(s[body..line]); if i < s.len { i += 1; } found = true; break; } if i < s.len { i += 1; } } if !found { parse_incomplete = true; syntax_error("unterminated here document"); } } } } if here_op || pending < here_pending.len { parse_incomplete = true; syntax_error("missing here document"); } emit(TokenKind.End, "", i, i); } fn peek(p: Parser&) -> Token { tokens[p.pos] } fn at(p: Parser&, kind: TokenKind) -> bool { peek(p).kind == kind } fn keyword(p: Parser&, name: u8[:]) -> bool { return at(p, TokenKind.Word) && view(peek(p).text) == name; } fn take(p: Parser&) -> Token { let t = peek(p); if p.pos < p.end { p.pos += 1; } return t; } fn expect(p: Parser&, kind: TokenKind) { if !at(p, kind) { if at(p, TokenKind.End) { parse_incomplete = true; } syntax_error("unexpected token"); } take(p); } fn newlines(p: Parser&) { while at(p, TokenKind.Semi) && view(peek(p).text) == "\n" { take(p); } } fn word_start(p: Parser&) -> bool { let k = peek(p).kind; return k == TokenKind.Word || k == TokenKind.Quoted || k == TokenKind.Var || k == TokenKind.Count || k == TokenKind.Join || k == TokenKind.Dollar || k == TokenKind.Lparen || k == TokenKind.Backtick || (k == TokenKind.Redir && p.pos + 1 <= p.end && tokens[p.pos + 1].kind == TokenKind.Lbrace && peek(p).end == tokens[p.pos + 1].start); } fn link(first: i64&, last: i64&, n: i64) { if first < 0 { first = n; } else { nodes[last].next = n; } last = n; } fn locate(p: Parser&, offset: i64) { // Track source lines across skipped tokens and multiline words. let source = view(p.source); while p.offset < offset { let c = source[p.offset]; p.offset += 1; if c == '\n' { p.line += 1; } } } recursive fn word_list(p: Parser&, mode: ListMode = ListMode.Line) -> i64 { var first = -1; var last = -1; loop { if mode == ListMode.Multiline { newlines(p); } if !word_start(p) { break; } link(first, last, word(p)); } return first; } recursive fn primary(p: Parser&) -> i64 { p.depth += 1; if p.depth > MAX_PARSE_DEPTH { syntax_error("syntax nesting limit exceeded"); } let t = take(p); locate(p, t.start); let line = p.line; var n = -1; match t.kind { Word => { n = literal(t.text); }, Quoted => { n = literal(t.text, QuoteMode.Quoted); }, Var => { n = node(Kind.Variable, literal(t.text, QuoteMode.Quoted)); }, Count => { n = node(Kind.Count, if t.text.len > 0 { literal(t.text, QuoteMode.Quoted) } else { primary(p) }); }, Join => { n = node(Kind.Join, if t.text.len > 0 { literal(t.text, QuoteMode.Quoted) } else { primary(p) }); }, Dollar => { n = node(Kind.Variable, primary(p)); }, Lparen => { n = node(Kind.List, word_list(p, ListMode.Multiline)); expect(p, TokenKind.Rparen); }, Backtick => { expect(p, TokenKind.Lbrace); n = node(Kind.Capture, sequence(p)); expect(p, TokenKind.Rbrace); }, Redir => { expect(p, TokenKind.Lbrace); n = node(if view(t.text) == "<" { Kind.InputPipe } else { Kind.OutputPipe }, sequence(p)); expect(p, TokenKind.Rbrace); }, _ => { if t.kind == TokenKind.End { parse_incomplete = true; } syntax_error("expected a word"); }, } if (nodes[n].kind == Kind.Variable) && at(p, TokenKind.Lparen) && tokens[p.pos - 1].end == peek(p).start { take(p); nodes[n].b = word_list(p, ListMode.Multiline); nodes[n].c = 1; expect(p, TokenKind.Rparen); } nodes[n].line = line; nodes[n].source = p.source; nodes[n].path = p.path; nodes[n].offset = t.start; p.depth -= 1; return n; } recursive fn word(p: Parser&) -> i64 { var n = primary(p); let first = nodes[n]; loop { if at(p, TokenKind.Caret) { take(p); n = node(Kind.Concat, n, primary(p)); continue; } let prev = tokens[p.pos - 1]; let next = peek(p); if prev.end == next.start && word_start(p) && next.kind != TokenKind.Lparen { n = node(Kind.Concat, n, primary(p)); continue; } break; } nodes[n].line = first.line; nodes[n].source = first.source; nodes[n].path = first.path; nodes[n].offset = first.offset; return n; } recursive fn braced(p: Parser&) -> i64 { expect(p, TokenKind.Lbrace); let n = sequence(p); expect(p, TokenKind.Rbrace); return if n < 0 { node(Kind.Empty) } else { n }; } recursive fn condition(p: Parser&) -> i64 { expect(p, TokenKind.Lparen); let n = sequence(p); expect(p, TokenKind.Rparen); newlines(p); return if n < 0 { node(Kind.Empty) } else { n }; } recursive fn unit(p: Parser&) -> i64 { p.depth += 1; if p.depth > MAX_PARSE_DEPTH { syntax_error("syntax nesting limit exceeded"); } locate(p, peek(p).start); let line = p.line; let offset = peek(p).start; var n = unit_inner(p); // A redirection after a compound command wraps the whole command. var prefix = -1; var tail = -1; while at(p, TokenKind.Redir) && !word_start(p) { let r = redirection(p); if prefix < 0 { prefix = r; } else { nodes[tail].c = r; } tail = r; } if prefix >= 0 { nodes[tail].c = n; n = prefix; } nodes[n].line = line; nodes[n].source = p.source; nodes[n].path = p.path; nodes[n].offset = offset; p.depth -= 1; return n; } recursive fn redirection(p: Parser&) -> i64 { let t = take(p); var target = -1; var quoted = -1; if starts_with(view(t.text), "<<") { let body = take(p); if body.kind != TokenKind.Here && body.kind != TokenKind.HereQuoted { syntax_error("expected a here document"); } target = literal(body.text, QuoteMode.Quoted); quoted = if body.kind == TokenKind.HereQuoted { HERE_LITERAL } else { HERE_EXPAND }; } else if !contains(view(t.text), '=') { target = word(p); } let r = node(Kind.Redirect, target, quoted); nodes[r].text = t.text; return r; } fn argument_block(p: Parser&) -> bool { return keyword(p, "args") && p.pos + 1 <= p.end && tokens[p.pos + 1].kind == TokenKind.Lbrace; } recursive fn unit_inner(p: Parser&) -> i64 { if argument_block(p) { take(p); p.declarations += 1; let body = braced(p); p.declarations -= 1; return node(Kind.Args, body); } if p.declarations > 0 && keyword(p, "command") { take(p); let name = word(p); return node(Kind.ArgCommand, name, braced(p)); } if at(p, TokenKind.Lbrace) { return braced(p); } if keyword(p, "if") { take(p); if keyword(p, "not") { take(p); return node(Kind.IfNot, unit(p)); } let c = condition(p); return node(Kind.If, c, unit(p)); } if keyword(p, "while") { take(p); let c = condition(p); return node(Kind.While, c, unit(p)); } if keyword(p, "for") { take(p); expect(p, TokenKind.Lparen); let name = word(p); var args = -1; if keyword(p, "in") { take(p); args = node(Kind.List, word_list(p)); } expect(p, TokenKind.Rparen); newlines(p); let n = node(Kind.For, args, unit(p)); nodes[n].c = name; return n; } if keyword(p, "fn") { take(p); let names = word_list(p); var body = -1; var source = Span { 0, 0 }; if at(p, TokenKind.Lbrace) { let start = peek(p).start + 1; let first = nodes.len; body = braced(p); // Function here-documents are an extension. Preserve their invocation-time values. for i in first..nodes.len { if nodes[i].kind == Kind.Redirect && nodes[i].b == HERE_EXPAND { nodes[i].b = HERE_FUNCTION; } } source = save(view(p.source)[start..tokens[p.pos - 1].start]); } let result = node(Kind.Function, names, body); nodes[result].text = source; return result; } if keyword(p, "switch") { take(p); expect(p, TokenKind.Lparen); let subject = word(p); expect(p, TokenKind.Rparen); newlines(p); return node(Kind.Switch, subject, braced(p)); } var first = -1; var last = -1; var prefix = -1; var tail = -1; while word_start(p) || at(p, TokenKind.Redir) { if first < 0 && prefix >= 0 && compound_start(p) { break; } if at(p, TokenKind.Redir) && !word_start(p) { let r = redirection(p); if prefix < 0 { prefix = r; } else { nodes[tail].c = r; } tail = r; continue; } let w = word(p); if first < 0 && at(p, TokenKind.Equal) { take(p); let a = node(Kind.Assign, w, word(p)); if prefix < 0 { prefix = a; } else { nodes[tail].c = a; } tail = a; continue; } link(first, last, w); } var cmd = -1; if first >= 0 { cmd = node(Kind.Simple, first); } else if prefix >= 0 && (at(p, TokenKind.Lbrace) || compound_start(p)) { cmd = unary(p); } if prefix >= 0 { nodes[tail].c = cmd; var i = prefix; while i >= 0 && i != cmd { nodes[i].d = cmd; i = nodes[i].c; } return prefix; } if cmd < 0 { if at(p, TokenKind.End) { parse_incomplete = true; } syntax_error("expected a command"); } return cmd; } fn compound_start(p: Parser&) -> bool { return keyword(p, "if") || keyword(p, "for") || keyword(p, "while") || keyword(p, "switch") || keyword(p, "fn") || keyword(p, "!") || keyword(p, "@") || argument_block(p); } recursive fn pipeline(p: Parser&) -> i64 { var n = unit(p); while at(p, TokenKind.Pipe) { let t = take(p); newlines(p); n = node(Kind.Pipe, n, unit(p)); nodes[n].text = t.text; } return n; } recursive fn unary(p: Parser&) -> i64 { if keyword(p, "!") || keyword(p, "@") { let t = take(p); let k = if view(t.text) == "!" { Kind.Not } else { Kind.Subshell }; return node(k, unary(p)); } return pipeline(p); } recursive fn command(p: Parser&) -> i64 { var n = unary(p); while at(p, TokenKind.And) || at(p, TokenKind.Or) { let t = take(p); newlines(p); let k = if t.kind == TokenKind.And { Kind.And } else { Kind.Or }; n = node(k, n, unary(p)); } return n; } recursive fn sequence(p: Parser&) -> i64 { var result = -1; var tail = -1; while !at(p, TokenKind.End) && !at(p, TokenKind.Rbrace) && !at(p, TokenKind.Rparen) { if at(p, TokenKind.Semi) { take(p); continue; } var n = command(p); if at(p, TokenKind.Amp) { take(p); n = node(Kind.Background, n); } else if at(p, TokenKind.Semi) { take(p); } else if !at(p, TokenKind.End) && !at(p, TokenKind.Rbrace) && !at(p, TokenKind.Rparen) { syntax_error("expected a command separator"); } let entry = node(Kind.Sequence, n); if result < 0 { result = entry; } else { nodes[tail].b = entry; } tail = entry; } return result; } fn parse(source: u8[:], line: i64 = 1, path: Span = Span { 0, 0 }) -> i64 { parse_error = Span { 0, 0 }; parse_incomplete = false; parse_continued = false; let start = tokens.len; lex(source); var p = Parser { start, tokens.len - 1, save(source) }; p.line = line; p.path = path; let n = sequence(p); expect(p, TokenKind.End); return n; }