dymokomi/luce-base
Source of release 0.43.0
0.43.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}")