Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / front / source.lucb

#==============================================================================================
#
#   source - Source text and positions
#
#   DESCRIPTION:
#       The bytes of one file, the encoding gate of base.md §3.1, and line/column positions
#       for diagnostics. A `Source` never owns its bytes; the caller's allocator does, so a
#       whole compilation can live in one arena.
#
#==============================================================================================

import c
import memory
import support.cache as cache
import support.in_arena
import strings
## The source is not valid UTF-8, or holds a disallowed control or bidi character.
pub let bad_encoding: ErrorCode = ErrorCode.package(1)
## The source file could not be read.
pub let unreadable: ErrorCode = ErrorCode.package(2)

# mark: Sources and directives ================================================================

## A position directive (§3.3): a line holding only `#: file:line:column` says that the
## lines after it, until the next directive, were compiled from that position of another
## source, and a trap on them reports it (§11.5); a bare `#:` restores the file's own
## positions (`file` empty).
pub struct Directive:
    ## The line the directive itself is on.
    pub var base_line: u32
    ## The source the following lines are attributed to; empty restores the file's own.
    pub var file: str
    ## The line of `file` the following lines start at.
    pub var line: u32
    ## The column of `file` the following lines start at.
    pub var column: u32

## One source file, or a module assembled from fragments: its bytes and the line,
## directive and segment maps that positions use.
pub struct Source:
    ## The source's path, as diagnostics name it.
    pub var path: str
    ## The source bytes.
    pub var bytes: const u8[]
    ## The position directives, in order.
    pub var directives: Directive*?
    ## How many directives.
    pub var directive_count: usize
    ## Where each line begins, for the positions traps name (§11.5)
    pub var lines: usize*?
    ## How many lines.
    pub var line_count: usize
    ## A module assembled from fragments: each fragment's path and the line it begins at,
    ## so a position names the fragment file (`mapped`); empty for one file.
    pub var segment_paths: str*?
    ## The line each fragment begins at.
    pub var segment_starts: u32*?
    ## How many fragments.
    pub var segment_count: usize

    ## The fragments a directory's `ORDER` lists, in order, as one source at `path`: each
    ## fragment is one segment, ending with a newline of its own.
    pub static func assembled(path: str, names: str[], texts: str[]) -> Source!:
        var total: usize = 0
        for text in texts:
            total += text.length + 1
        let data = try new u8[total] ---
        let paths = try new str[names.length] ---
        let starts = try new u32[names.length] ---
        var at: usize = 0
        var line: u32 = 1
        var k: usize = 0
        while k < names.length:
            paths[k] = names[k]
            starts[k] = line
            let text = texts[k].bytes
            memory.copy(data[at..], text, text.length)
            at += text.length
            for b in text:
                if b == '\n':
                    line += 1
            if text.length == 0 or text[text.length - 1] != '\n':
                data[at] = '\n'
                at += 1
                line += 1
            k += 1
        var src = try Source.over(path, data[..<at])
        src.segment_paths = &paths[0] if names.length > 0 else none
        src.segment_starts = &starts[0] if names.length > 0 else none
        src.segment_count = names.length
        return src

    ## The file, line, and column a diagnostic names for a byte offset: the fragment's when
    ## the module was assembled, else this source's own. Directives are for traps (`mapped`):
    ## a diagnostic names the Base text the checker read.
    pub func located(offset: usize) -> (str, u32, u32):
        let (line, column) = self.position(offset)
        return self.fragment_of(line, column)

    ## The fragment file and line a line of an assembled module came from; this source's own
    ## for a module read from one file.
    pub func fragment_of(line: u32, column: u32) -> (str, u32, u32):
        if let paths = self.segment_paths:
            if let starts = self.segment_starts:
                if self.segment_count > 0:
                    let found = self.segment_of(line)
                    return (paths[found], line - starts[found] + 1, column)
        return (self.path, line, column)

    ## Which fragment a line of an assembled module belongs to; 0 for one file.
    func segment_of(line: u32) -> usize:
        var found: usize = 0
        if let starts = self.segment_starts:
            var k: usize = 0
            while k < self.segment_count:
                if starts[k] <= line:
                    found = k
                k += 1
        return found

    ## Spell this source's path, and its fragments', under `replacement` instead of the
    ## directory `prefix` (relative to it when `replacement` is empty): a standard module's
    ## positions name `std/core.lucb`, the same on every machine, not the directory the
    ## library was read from (§11.5). The build cache's key names them so too.
    pub func rebase(prefix: str, replacement: str) -> !:
        let path = try rebased(self.path, prefix, replacement)
        cache.rename_input(self.path, path)
        self.path = path
        if let paths = self.segment_paths:
            var k: usize = 0
            while k < self.segment_count:
                let fragment = try rebased(paths[k], prefix, replacement)
                cache.rename_input(paths[k], fragment)
                paths[k] = fragment
                k += 1

    ## Load a file into the current allocator and check it is UTF-8 without NUL.
    pub static func load(path: c.str) -> Source!:
        let data = try in_arena.read(path)
        cache.note_input((str)path, data)
        return try Source.over((str)path, data)

    ## Adopt bytes already in memory (tests, and the driver's own strings). A byte-order
    ## mark at byte zero is dropped (§3.1); the text must be UTF-8 free of controls.
    pub static func over(path: str, data: const u8[]) -> Source!:
        let body = data[3..] if has_bom(data) else data
        try refuse_controls(path, body)
        _ = str(body) catch:
            error(bad_encoding, try located(path, body, first_invalid(body), "invalid UTF-8 in source"))
        var line_count: usize = 1
        for b in body:
            if b == '\n':
                line_count += 1
        let starts = try new usize[line_count] ---
        starts[0] = 0
        var k: usize = 1
        var i: usize = 0
        while i < body.length:
            if body[i] == '\n' and k < line_count:
                starts[k] = i + 1
                k += 1
            i += 1
        # a directive is a line of its own that begins `#:`, so only the line starts are read
        let count = count_directives(body, starts)
        var directives: Directive*? = none
        if count > 0:
            let room = try new Directive[count] ---
            fill_directives(body, starts, room)
            directives = &room[0]
        return Source(path = path, bytes = body, directives = directives, directive_count = count, lines = &starts[0], line_count = line_count, segment_paths = none, segment_starts = none, segment_count = 0)

    ## One-based column of the first non-blank byte of a line: where the statement on it
    ## begins, which is what a trap names (§11.5).
    pub func statement_column(line: u32) -> u32:
        let starts = self.lines else return 1
        if line == 0 or (usize)line > self.line_count:
            return 1
        var i = starts[(usize)line - 1]
        var column: u32 = 1
        while i < self.bytes.length and self.bytes[i] == ' ':
            i += 1
            column += 1
        return column

    ## What a line of this file was compiled from (§3.3): the position the last directive
    ## above it names, or the file's own `path:line:column`.
    pub func mapped(line: u32, column: u32) -> (str, u32, u32):
        if let d = self.directive_for(line):
            return (d.file, d.line, d.column)
        return self.fragment_of(line, column)

    ## Whether a directive names where `line` was compiled from (`mapped`).
    pub func directed(line: u32) -> bool:
        return self.directive_for(line) != none

    ## The directive above `line` that names a file, if the last one does.
    func directive_for(line: u32) -> Directive?:
        let all = self.directives else return none
        # the directives stand in line order: the last at or above `line`, by halves
        var low: usize = 0
        var high = self.directive_count
        while low < high:
            let middle = (low + high) // 2
            if all[middle].base_line <= line:
                low = middle + 1
            else:
                high = middle
        if low == 0:
            return none
        let d = all[low - 1]
        if d.file.length == 0:
            return none
        return d

    ## One-based line and column of a byte offset, counting columns in bytes.
    pub func position(offset: usize) -> (u32, u32):
        let at = offset if offset < self.bytes.length else self.bytes.length
        let starts = self.lines else return scanned_position(self.bytes, at)
        # the last line that starts at or before the offset
        var low: usize = 0
        var high = self.line_count
        while high - low > 1:
            let middle = (low + high) // 2
            if starts[middle] <= at:
                low = middle
            else:
                high = middle
        return ((u32)(low + 1), (u32)(at - starts[low] + 1))

    ## The source text between byte offsets `start` and `end`.
    pub func text(start: usize, end: usize) -> str:
        return (str)self.bytes[start..<end]

## The line and column of `offset`, counted from the start, for a source with no line map.
func scanned_position(bytes: const u8[], offset: usize) -> (u32, u32):
    var line: u32 = 1
    var column: u32 = 1
    for i in 0..<offset:
        if bytes[i] == '\n':
            line += 1
            column = 1
        else:
            column += 1
    return (line, column)

## The UTF-8 byte-order mark, accepted only at byte zero.
# mark: Reading and validation ================================================================

## Whether `data` starts with a UTF-8 byte-order mark.
func has_bom(data: const u8[]) -> bool:
    return data.length >= 3 and data[0] == 0xEF and data[1] == 0xBB and data[2] == 0xBF

## NUL, a byte-order mark past byte zero, and the Unicode bidirectional format
## characters (U+202A to U+202E and U+2066 to U+2069) are refused in source (§3.1), each
## at the line and column it stands at.
func refuse_controls(path: str, data: const u8[]) -> !:
    var i: usize = 0
    while i < data.length:
        # eight bytes at a time while they hold no NUL and nothing past ASCII, as most do
        while i + 8 <= data.length:
            let word = memory.read[u64](&data[i])
            let zero = (word -% 0x0101010101010101) & ~word & 0x8080808080808080
            if ((word & 0x8080808080808080) | zero) != 0:
                break
            i += 8
        if i >= data.length:
            break
        let b = data[i]
        if b == 0:
            error(bad_encoding, try located(path, data, i, "NUL byte in source"))
        if b == 0xEF and i + 2 < data.length and data[i + 1] == 0xBB and data[i + 2] == 0xBF:
            error(bad_encoding, try located(path, data, i, "a byte-order mark is accepted only at byte zero"))
        if b == 0xE2 and i + 2 < data.length:
            let second = data[i + 1]
            let third = data[i + 2]
            let embedding = second == 0x80 and third >= 0xAA and third <= 0xAE
            let isolate = second == 0x81 and third >= 0xA6 and third <= 0xA9
            if embedding or isolate:
                error(bad_encoding, try located(path, data, i, "bidirectional format characters are not allowed in source"))
        i += 1

## `path:line:column: what` for byte `offset` of `data`, in an allocation of its own, since
## the message outlives the call; the column counts bytes from the line's start, as the
## lexer counts.
func located(path: str, data: const u8[], offset: usize, what: str) -> str!:
    var line: usize = 1
    var column: usize = 1
    var i: usize = 0
    while i < offset and i < data.length:
        if data[i] == '\n':
            line += 1
            column = 1
        else:
            column += 1
        i += 1
    let room = try new u8[path.length + what.length + 48] ---
    return try strings.format(room, f"{path}:{line}:{column}: {what}")

## The offset of the first byte that is not part of well-formed UTF-8, or the length.
func first_invalid(data: const u8[]) -> usize:
    var i: usize = 0
    while i < data.length:
        while i + 8 <= data.length and (memory.read[u64](&data[i]) & 0x8080808080808080) == 0:
            i += 8
        if i >= data.length:
            break
        let b = data[i]
        var need: usize = 0
        if b < 0x80:
            need = 0
        elif b >= 0xC2 and b <= 0xDF:
            need = 1
        elif b >= 0xE0 and b <= 0xEF:
            need = 2
        elif b >= 0xF0 and b <= 0xF4:
            need = 3
        else:
            return i
        if need > 0:
            # the second byte's range excludes overlong forms, surrogates, and code points
            # past U+10FFFF (RFC 3629)
            if i + 1 >= data.length:
                return i
            let second = data[i + 1]
            let low: u8 = 0xA0 if b == 0xE0 else (0x90 if b == 0xF0 else 0x80)
            let high: u8 = 0x9F if b == 0xED else (0x8F if b == 0xF4 else 0xBF)
            if second < low or second > high:
                return i
        var k: usize = 1
        while k <= need:
            if i + k >= data.length or (data[i + k] & 0xC0) != 0x80:
                return i
            k += 1
        i += need + 1
    return data.length

## The directive on the line beginning at `at`, if the line is one: `#:` first after
## spaces, then nothing, or `file:line:column` with two numbers; anything else is a
## comment like any other. The line's end is answered through `stop`.
func directive_at(body: const u8[], at: usize, base_line: u32, stop: usize*) -> Directive?:
    var end = at
    while end < body.length and body[end] != '\n':
        end += 1
    *stop = end
    var i = at
    while i < end and body[i] == ' ':
        i += 1
    if i + 1 >= end or body[i] != '#' or body[i + 1] != ':':
        return none
    var s = i + 2
    while s < end and body[s] == ' ':
        s += 1
    var e = end
    while e > s and (body[e - 1] == ' ' or body[e - 1] == '\r'):
        e -= 1
    if s == e:
        return Directive(base_line = base_line + 1, file = "", line = 0, column = 0)
    # the two numbers from the right, the file being whatever precedes them
    var c2 = e
    while c2 > s and body[c2 - 1] != ':':
        c2 -= 1
    if c2 <= s + 1:
        return none
    var c1 = c2 - 1
    while c1 > s and body[c1 - 1] != ':':
        c1 -= 1
    if c1 <= s + 1:
        return none
    let line = directive_number(body, c1, c2 - 1) else return none
    let column = directive_number(body, c2, e) else return none
    return Directive(base_line = base_line + 1, file = (str)body[s..<c1 - 1], line = line, column = column)

func directive_number(body: const u8[], start: usize, end: usize) -> u32?:
    if start >= end:
        return none
    var n: u64 = 0
    var i = start
    while i < end:
        let digit = body[i]
        if digit < '0' or digit > '9' or n > 100000000:
            return none
        n = n * 10 + (u64)(digit - '0')
        i += 1
    return u32(n)

## How many lines, each starting at one of `starts`, are directives.
func count_directives(body: const u8[], starts: const usize[]) -> usize:
    var count: usize = 0
    for line in 0..<starts.length:
        var stop: usize = 0
        if opens_directive(body, starts[line]) and directive_at(body, starts[line], u32(line + 1), &stop) != none:
            count += 1
    return count

## The directives among the lines starting at `starts`, in order, into `room`.
func fill_directives(body: const u8[], starts: const usize[], room: Directive[]):
    var k: usize = 0
    for line in 0..<starts.length:
        if k == room.length:
            return
        var stop: usize = 0
        if not opens_directive(body, starts[line]):
            continue
        if let d = directive_at(body, starts[line], u32(line + 1), &stop):
            room[k] = d
            k += 1

## Whether the line at `at` begins, after its indentation, with `#:`: the test that rules
## out every other line before `directive_at` reads one through.
func opens_directive(body: const u8[], at: usize) -> bool:
    var i = at
    while i < body.length and body[i] == ' ':
        i += 1
    return i + 1 < body.length and body[i] == '#' and body[i + 1] == ':'

test "a control character and invalid UTF-8 are refused at their line and column":
    let bidi = Source.over("t.lucb", "ab\n  \u{202e}x".bytes) catch failure:
        assert(failure.message == "t.lucb:2:3: bidirectional format characters are not allowed in source")
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(bidi.path == "")
    var bad: u8[6] = [97, 10, 98, 255, 99, 10]
    let broken = Source.over("t.lucb", bad) catch failure:
        assert(failure.message == "t.lucb:2:2: invalid UTF-8 in source")
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(broken.path == "")
    var nul: u8[3] = [97, 0, 98]
    let zero = Source.over("t.lucb", nul) catch failure:
        assert(failure.message == "t.lucb:1:2: NUL byte in source")
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(zero.path == "")

test "a byte-order mark is dropped at byte zero and refused elsewhere":
    let bom: u8[6] = [0xEF, 0xBB, 0xBF, 'a', 'b', 'c']
    let src = Source.over("t", bom) catch failure:
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(src.bytes.length == 3)
    let inside: u8[5] = ['a', 0xEF, 0xBB, 0xBF, 'b']
    var refused = false
    _ = Source.over("t", inside) catch failure:
        refused = true
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(refused)

test "a bidirectional control is refused":
    let text: u8[5] = ['a', 0xE2, 0x80, 0xAE, 'b']
    var refused = false
    _ = Source.over("t", text) catch failure:
        refused = true
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(refused)

test "position counts lines and columns":
    let src = Source.over("t", "ab\ncd".bytes) catch failure:
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    let (line, column) = src.position(4)
    assert(line == 2)
    assert(column == 2)

test "NUL is refused":
    var raw: u8[3] = [97, 0, 98]
    var refused = false
    _ = Source.over("t", raw) catch failure:
        refused = failure.code == bad_encoding
        recover Source(path = "", bytes = "".bytes, directives = none, directive_count = 0, lines = none, line_count = 0)
    assert(refused)

test "position directives map the lines after them":
    let text = "func f():\n    #: main.luc:12:8\n    let a = 1\n    let b = 2\n    #:\n    let c = 3\n    #: not one\n    let d = 4\n"
    let src = try Source.over("t.lucb", text.bytes)
    assert(src.directive_count == 2)
    let (f1, l1, c1) = src.mapped(3, 5)
    assert(f1 == "main.luc" and l1 == 12 and c1 == 8)
    let (f2, l2, c2) = src.mapped(4, 5)
    assert(f2 == "main.luc" and l2 == 12 and c2 == 8)
    let (f3, l3, c3) = src.mapped(6, 5)
    assert(f3 == "t.lucb" and l3 == 6 and c3 == 5)
    let (f4, l4, c4) = src.mapped(8, 5)
    assert(f4 == "t.lucb" and l4 == 8 and c4 == 5)
    let (f0, l0, c0) = src.mapped(1, 1)
    assert(f0 == "t.lucb" and l0 == 1 and c0 == 1)
    assert(src.statement_column(1) == 1)
    assert(src.statement_column(3) == 5)
    assert(src.statement_column(8) == 5)
    assert(src.statement_column(9) == 1)

## `path` with a leading `prefix/` replaced by `replacement/`; unchanged without the prefix.
func rebased(path: str, prefix: str, replacement: str) -> str!:
    if path.length <= prefix.length or (str)path.bytes[..<prefix.length] != prefix or path.bytes[prefix.length] != '/':
        return path
    let rest = (str)path.bytes[prefix.length + 1..]
    if replacement.length == 0:
        return rest
    let room = try new u8[replacement.length + rest.length + 1] ---
    return try strings.format(room, f"{replacement}/{rest}")