dymokomi/luce-base
Source of release 0.43.0
0.43.0 / src / support / cache.lucb
#==============================================================================================
#
# cache - The build cache: an object kept under the hash of everything that made it
#
# DESCRIPTION:
# A build's object is a function of the sources read (every standard module, the
# program's modules, the manifest), the target and its level, the backend and the
# flags, and the compiler itself. The driver notes each source as the checker reads
# it, asks for the key once the program is checked, and links the cached object when
# one is there, translating and assembling nothing (base.md §19.7). The cache is
# `--cache-dir DIR`, else `LUCE_CACHE`, else the project-local `build/.cache` beside the
# build output (so `rm -rf build` clears it and no two projects share one); `none` off.
#
# A question whose answer is a function of the files it reads (`describe-closure`) is
# answered from a record: the answer, each file read with the hash of its bytes, and
# each path a lookup found absent. The record answers again while every file hashes
# the same and every absent path is still absent, without reading or checking
# anything else; a file added where a lookup would now find it makes it stale.
#
#==============================================================================================
import c
import luce_std.files
import io
import memory
import os
import luce_std.paths
import support.buffer
import support.hashed
import support.list
import support.in_arena
import strings
# mark: The cache's settings ==================================================================
## The build cache could not be read or written.
pub let failed: ErrorCode = ErrorCode.package(42)
## `--cache-dir`: the directory the driver was told, before any default; `none` for no cache.
pub var override: str = ""
## The project root (the directory holding `package.prisma`, with a trailing slash, or empty for
## none), so the default cache lands in that project's `build/.cache` rather than a shared one.
pub var default_root: str = ""
## `--cache-report`: say on standard error whether the object came from the cache.
pub var report: bool = false
## Whether the sources read are noted at all. A checker embedded in another program builds
## nothing and checks again and again, so it keeps no notes (`embed.check_root`).
pub var noting: bool = true
var compiler_hash: u64 = 0
# mark: The key ===============================================================================
## The sources noted so far, in the order read: the path each is named by and the hash of
## its bytes. Kept until the key is asked, since the project root that names them is known
## only once the manifest has been read. Grown by doubling, in the heap.
var noted_paths: str[]
var noted_bytes: u64[]
var noted_count: usize = 0
## Each noted source's path as it was read, which `rename_input` leaves: what a record
## reads again.
var read_paths: str[]
## The paths a lookup found absent (`note_absent`), each once.
var absent_paths: str[]
var absent_count: usize = 0
## Note a source the build read, in the order it was read: its path and its bytes. A note
## that cannot be kept (no memory) leaves the build uncached rather than failing it. A
## source named by something other than the file read (a directory module, by its
## `ORDER`) gives the file as `read_as`, which a record reads again.
pub func note_input(path: str, bytes: const u8[], read_as: str = ""):
if not noting:
return
with memory.heap:
if noted_count == noted_paths.length:
grow_notes()
if lost:
return
let copied = try_copy(path)
if copied == none:
lost = true
return
noted_paths[noted_count] = copied else return
read_paths[noted_count] = copied else return
if read_as.length > 0:
read_paths[noted_count] = try_copy(read_as) else return
noted_bytes[noted_count] = digest(bytes)
noted_count += 1
## Whether a file is at `path`, for a lookup: an absence is noted (`note_absent`). While
## `remembering`, the answer is the first one for the path since `forget_lookups`.
pub func exists(path: c.str) -> bool:
var found = false
if let known = remembered(path):
found = known
else:
found = files.exists(path)
if remembering:
remember_lookup(path, found)
if not found:
note_absent((str)path)
return found
## Note that a lookup found nothing at `path` (a module, a manifest, an `ORDER`): a file
## that appears there later could change what the lookup finds, so a record that saw it
## absent is stale once it is not.
pub func note_absent(path: str):
if not noting:
return
with memory.heap:
for i in 0..<absent_count:
if absent_paths[i] == path:
return
if absent_count == absent_paths.length:
grow_absent()
if lost:
return
if let copied = try_copy(path):
absent_paths[absent_count] = copied
absent_count += 1
else:
lost = true
## A noted source the object shows by another name: a standard module's `std/...`, a
## dependency's `<package>/...` (`Source.rebase`). The key names it so too.
pub func rename_input(path: str, shown_as: str):
if not noting:
return
with memory.heap:
for i in 0..<noted_count:
if noted_paths[i] == path:
let copied = try_copy(shown_as)
if copied == none:
lost = true
return
noted_paths[i] = copied else return
func grow_absent():
let size = 64 if absent_paths.length == 0 else absent_paths.length * 2
let room = new str[size] --- catch:
lost = true
return
for i in 0..<absent_count:
room[i] = absent_paths[i]
if absent_paths.length > 0:
free(absent_paths)
absent_paths = room
func grow_notes():
let size = 64 if noted_paths.length == 0 else noted_paths.length * 2
let paths_room = new str[size] --- catch:
lost = true
return
let bytes_room = new u64[size] --- catch:
free(paths_room)
lost = true
return
let read_room = new str[size] --- catch:
free(paths_room)
free(bytes_room)
lost = true
return
for i in 0..<noted_count:
paths_room[i] = noted_paths[i]
bytes_room[i] = noted_bytes[i]
read_room[i] = read_paths[i]
if noted_paths.length > 0:
free(noted_paths)
free(noted_bytes)
free(read_paths)
noted_paths = paths_room
noted_bytes = bytes_room
read_paths = read_room
## Whether a note was lost, so the inputs are not all known and there is no key.
var lost: bool = false
func try_copy(text: str) -> str?:
let room = new u8[text.length] --- catch:
return none
memory.copy(room, text.bytes, text.length)
return (str)room
## A hash of `bytes`, what the cache tells a source's contents by.
pub func digest(bytes: const u8[]) -> u64:
return mix(1469598103934665603, bytes)
## `bytes` mixed into `h` eight at a time (a multiply and a shift per word, since a build
## hashes every source it reads), then the length, so two inputs never run together.
func mix(h: u64, bytes: const u8[]) -> u64:
var r = h
var i: usize = 0
while i + 8 <= bytes.length:
r = step(r, memory.read[u64](&bytes[i]))
i += 8
var tail: u64 = 0
var shift: u64 = 0
while i < bytes.length:
tail = tail | ((u64)bytes[i] << shift)
shift += 8
i += 1
r = step(r, tail)
return step(r, (u64)bytes.length)
func step(h: u64, word: u64) -> u64:
let r = (h ^ word) *% 11400714819323198485
return r ^ (r >> 29)
## Start a build's digest afresh.
pub func begin():
noted_count = 0
absent_count = 0
lost = false
## The key of a build: the inputs noted so far, `settings` (the target, backend and flags
## as text), and the compiler's own bytes, as sixteen hex digits.
##
## A source is named as the object names it in its trap positions: relative to the project
## root when under it, so the same project built from another directory (luce builds each
## program in a new workspace) has the same key; a standard module as `std/...` and a
## dependency's as `<package>/...` (`rename_input`). When `located` (a debug build, which
## records the root as its compilation directory, or any C object), the object names the
## program's sources as they were read, and so does the key, with the root itself.
pub func key(settings: str, located: bool = true) -> str!:
var h: u64 = 1469598103934665603
var count: u64 = 0
for i in 0..<noted_count:
h = mix(h, (noted_paths[i] if located else relative(noted_paths[i])).bytes)
h = (h ^ noted_bytes[i]) *% 1099511628211
count += 1
if located:
h = mix(h, default_root.bytes)
h = mix(h, settings.bytes)
h = (h ^ (try compiler())) *% 1099511628211
h = (h ^ count) *% 1099511628211
return try digits_of(h)
## `h` as sixteen hex digits.
func digits_of(h: u64) -> str!:
let room = try new u8[16] ---
let digits = "0123456789abcdef"
var i: usize = 0
while i < 16:
room[i] = digits.bytes[(usize)((h >> (60 - 4 * i)) & 15)]
i += 1
return (str)room[..<16]
## `path` without the project root in front of it, when it is under the root: how the key,
## and an object not `located`, name a source.
pub func relative(path: str) -> str:
let root = default_root
if root.length > 0 and path.length > root.length and (str)path.bytes[..<root.length] == root:
return (str)path.bytes[root.length..]
return path
## The hash of the running compiler's file (`compiler`).
pub func compiler_digest() -> u64!:
return try compiler()
## Whether this build has a cache at all.
pub func on() -> bool!:
if lost:
return false
return (try directory()) != none
## The hash of the running compiler's file, read once: a different compiler is a
## different build.
func compiler() -> u64!:
if compiler_hash != 0:
return compiler_hash
let exe = try os.executable()
let bytes = try files.read((c.str)exe)
defer bytes.release()
compiler_hash = mix(14695981039346656037, bytes.value)
return compiler_hash
# mark: Lookups remembered ===================================================================
## Whether a lookup's answer is kept for the lookups of the same path after it, until
## `forget_lookups`. A host's check (`embed.Library`) asks whether the same manifests and
## modules are there thousands of times: 6800 lookups of 250 paths for a script importing
## luce-geocore, each a call to the system, 13 µs on Windows. A check takes the files as it
## first finds them, as a build does.
pub var remembering: bool = false
## A path a lookup asked about while `remembering`, and whether a file was there.
struct Lookup:
var path: str
var found: bool
## The lookups remembered, in the heap, and an index from path to place in that list; made
## at the first.
var lookups: list.List[Lookup]? = none
var lookup_index: hashed.Table[str]? = none
## The answer remembered for `path`, when there is one.
func remembered(path: c.str) -> bool?:
if not remembering:
return none
let index = lookup_index else return none
let found = lookups else return none
let at = index.find((str)path) else return none
return found.get(at).found
## Keep `found` as the answer for `path`; a memo that cannot grow keeps nothing, which costs
## time only.
func remember_lookup(path: c.str, found: bool):
with memory.heap:
keep_lookup((str)path, found) catch ignored:
_ = ignored
func keep_lookup(path: str, found: bool) -> !:
var kept = lookups else try list.List[Lookup].create(256)
var index = lookup_index else try hashed.Table[str].create(256)
let copy = try strings.copy(path)
try kept.push(Lookup(path = copy, found = found))
_ = try index.add(copy, kept.count - 1)
lookups = kept
lookup_index = index
## Forget every lookup remembered: the next lookup of each path asks the system again.
pub func forget_lookups():
with memory.heap:
if let index = lookup_index:
var held = index
held.destroy()
if let kept = lookups:
var held = kept
for lookup in held.span():
strings.release(lookup.path)
held.destroy()
lookup_index = none
lookups = none
# mark: Objects in the cache ==================================================================
## Whether a cache was named, by `--cache-dir` or `LUCE_CACHE`: a record is kept only in a
## cache the caller chose, never in a project's default `build/.cache`.
pub func named() -> bool:
if override.length > 0:
return override != "none"
let chosen = os.env("LUCE_CACHE") else return false
return chosen.length > 0 and chosen != "none"
## The cache directory, created when missing; none when the cache is off or nowhere.
pub func directory() -> str?!:
var chosen = override
if chosen.length == 0:
if let environment = os.env("LUCE_CACHE"):
chosen = environment
if chosen == "none":
return none
if chosen.length == 0:
# The default cache is project-local: `<project>/build/.cache`, beside the build
# output, so `rm -rf build` clears it and each project keeps its own (§19.7).
let base_room = try new u8[default_root.length + 8] ---
let base = try strings.format(base_room, f"{default_root}build")
try ensure((c.str)base)
let room = try new u8[default_root.length + 16] ---
chosen = try strings.format(room, f"{default_root}build/.cache")
try ensure((c.str)chosen)
return chosen
func ensure(path: c.str) -> !:
if files.exists(path):
return
files.create_directory(path, 493u32) catch failure:
if files.exists(path):
return
error(failure.code, failure.message)
## The cached object for the key `entry` and `suffix` (`-n.o` native, `-c.o` C, `-p.o` a
## piece of a split assembly), when it is there; `quiet` leaves it out of the report.
pub func find(entry: str, suffix: str, quiet: bool = false) -> str?!:
if lost:
return none
let dir = try directory() else return none
let room = try new u8[dir.length + entry.length + suffix.length + 2] ---
let path = try strings.format(room, f"{dir}/{entry}{suffix}")
if not files.exists((c.str)path):
if report and not quiet:
try io.stderr().write(f"luce-base: cache miss {entry}{suffix}\n")
return none
if report and not quiet:
try io.stderr().write(f"luce-base: cache hit {entry}{suffix}\n")
refresh((c.str)path)
return path
## The cached object for the key `entry` and `suffix`, taken into the build's workspace `dir`
## under the same name, when the cache has it: a hard link, or a copy where the two cannot
## share a file. A build links what it took, never the cache's own file, which a build
## trimming the shared cache (luce's `trim`) may remove at any moment; one removed before it
## was taken is a miss. The cache never writes a file in place (`keep` renames a whole new
## one over the name), so what a build took never changes under it.
pub func take(entry: str, suffix: str, dir: str, quiet: bool = false) -> str?!:
let found = try find(entry, suffix, quiet) else return none
let room = try new u8[dir.length + entry.length + suffix.length + 2] ---
let path = try strings.format(room, f"{dir}/{entry}{suffix}")
if files.exists((c.str)path):
# an earlier build's, in a workspace kept between builds
files.remove_file((c.str)path) catch ignored:
_ = ignored
files.create_hard_link((c.str)found, (c.str)path) catch:
_ = files.copy_file((c.str)found, (c.str)path, replace = true) catch:
return none
return path
## The bytes of the cached file for `entry` and `suffix`, when the cache has it; none when it
## is missing or goes before it is read, as a trim of the shared cache may make it.
pub func read(entry: str, suffix: str, quiet: bool = false) -> u8[]?!:
let found = try find(entry, suffix, quiet) else return none
return in_arena.read((c.str)found) catch:
return none
## A hit is a use: the file's modified time becomes now. A cache shared by many builds is kept
## within its size by removing the files modified longest ago (luce's `trim`), so this keeps
## what builds use and spares what a build in flight has just found. A file that cannot be
## touched is used as it is.
func refresh(path: c.str):
files.touch(path) catch ignored:
_ = ignored
## The key of a piece of a split assembly (`support.pieces`): its text, which is all the
## assembler reads, and the architecture it assembles for.
pub func piece_key(prelude: str, middle: str, closing: str, arch: str) -> str!:
var h = mix(1469598103934665603, prelude.bytes)
h = mix(h, middle.bytes)
h = mix(h, closing.bytes)
h = mix(h, arch.bytes)
return try digits_of(h)
## Keep `bytes` under the key `entry` and `suffix`, as `keep` keeps an object's.
pub func keep_bytes_as(entry: str, suffix: str, bytes: const u8[]):
keep_named(entry, suffix, bytes) catch ignored:
_ = ignored
func keep_named(entry: str, suffix: str, bytes: const u8[]) -> !:
if lost:
return
let dir = try directory() else return
try keep_bytes(dir, entry, suffix, bytes)
## Keep `object` under the key `entry` and `suffix`: written beside its place, then renamed, so a
## reader never sees a partial file. A cache that cannot be written is no cache.
pub func keep(entry: str, suffix: str, object: str):
keep_object(entry, suffix, object) catch ignored:
_ = ignored
func keep_object(entry: str, suffix: str, object: str) -> !:
if lost:
return
let dir = try directory() else return
let bytes = try files.read((c.str)object)
defer bytes.release()
try keep_bytes(dir, entry, suffix, bytes.value)
# mark: Records ===============================================================================
let record_header: str = "luce-base-record-v1\n"
## The name of the record that answers `question` (the command and its arguments, as
## text) from this compiler: sixteen hex digits.
pub func record_key(question: str) -> str!:
return try digits_of(step(mix(1469598103934665603, question.bytes), try compiler()))
## The answer the record `record` keeps, when the cache has it and it is current: every
## file it lists hashes as it did, and every absent path is still absent.
pub func recall(record: str) -> u8[]?!:
let dir = try directory() else return none
let room = try new u8[dir.length + record.length + 4] ---
let record_path = try strings.format(room, f"{dir}/{record}-r")
let record_bytes = files.read((c.str)record_path) catch: return none
defer record_bytes.release()
let text = (str)record_bytes.value
if not starts(text, record_header):
return none
var at = record_header.length
while at < text.length:
var end = at
while end < text.length and text.bytes[end] != '\n':
end += 1
let line = (str)text.bytes[at..<end]
at = end + 1
if line.length > 19 and line.bytes[0] == 'f' and line.bytes[18] == ' ':
let path = (str)line.bytes[19..]
let bytes = files.read((c.str)try copy_terminated(path)) catch: return none
defer bytes.release()
if (str)line.bytes[2..<18] != try digits_of(digest(bytes.value)):
return none
elif line.length > 2 and line.bytes[0] == 'a':
if files.exists((c.str)try copy_terminated((str)line.bytes[2..])):
return none
else:
return none
let answer_room = try new u8[dir.length + record.length + 4] ---
let answer = in_arena.read((c.str)try strings.format(answer_room, f"{dir}/{record}-o")) catch: return none
if report:
try io.stderr().write(f"luce-base: record hit {record}\n")
return answer
## Keep `answer` under the record `record`, with the files this run read and the paths it
## found absent. A record that cannot be written, or a run whose notes were lost, is none.
pub func remember(record: str, answer: const u8[]):
remember_answer(record, answer) catch ignored:
_ = ignored
func remember_answer(record: str, answer: const u8[]) -> !:
if lost:
return
let dir = try directory() else return
var text = try buffer.Buffer.create(4096)
try text.put(record_header)
for i in 0..<noted_count:
try text.put("f ")
try text.put(try digits_of(noted_bytes[i]))
try text.put(" ")
try text.put(read_paths[i])
try text.put("\n")
for i in 0..<absent_count:
try text.put("a ")
try text.put(absent_paths[i])
try text.put("\n")
# the answer first, so a record is never there without it
try keep_bytes(dir, record, "-o", answer)
try keep_bytes(dir, record, "-r", text.bytes())
## Write `bytes` as `dir/name+suffix`, beside it first and then renamed into place: a
## reader never sees a partial file.
func keep_bytes(dir: str, name: str, suffix: str, bytes: const u8[]) -> !:
let final_room = try new u8[dir.length + name.length + suffix.length + 2] ---
let final = try strings.format(final_room, f"{dir}/{name}{suffix}")
# a directory of this run's own, so two runs keeping one name never share a file
let staging = try files.create_temporary_directory((c.str)dir, 448u32)
defer staging.release()
defer files.remove_tree((c.str)staging.value) catch ignored:
_ = ignored
let temp_room = try new u8[staging.value.length + 8] ---
let temp = try strings.format(temp_room, f"{staging.value}/object")
try files.write((c.str)temp, bytes)
try files.rename((c.str)temp, (c.str)final, true)
func starts(text: str, prefix: str) -> bool:
return text.length >= prefix.length and (str)text.bytes[..<prefix.length] == prefix
func copy_terminated(text: str) -> str!:
let room = try new u8[text.length + 1] ---
memory.copy(room, text.bytes, text.length)
room[text.length] = 0
return (str)room[..<text.length]
test "a build takes a cached object into its workspace, and one gone before it is taken is a miss":
let scratch = try in_arena.temporary_directory(".")
defer files.remove_tree((c.str)scratch) catch ignored:
_ = ignored
let cache_dir = try in_arena.join(scratch, "cache")
let workspace = try in_arena.join(scratch, "work")
try files.create_directory((c.str)cache_dir)
try files.create_directory((c.str)workspace)
let saved = override
defer override = saved
override = cache_dir
try keep_bytes(cache_dir, "0123456789abcdef", "-p.o", "object")
let taken = try take("0123456789abcdef", "-p.o", workspace, true) else return assert(false)
# a trim of the shared cache removes the cache's file; the build still has its own
try files.remove_file((c.str)try in_arena.join(cache_dir, "0123456789abcdef-p.o"))
assert((str)(try in_arena.read((c.str)taken)) == "object")
assert(try take("0123456789abcdef", "-p.o", workspace, true) == none)
assert(try read("0123456789abcdef", "-p.o", true) == none)