What should be done?

After this PR (#33), we use the OnceLock API to create static variables shared by the program. OnceLock is the less-ergonomic brother of the cooler LazyLock, which is not yet stable (issue tracker).

Using OnceLock, we create helper methods (see buffers(), features() or interned_symbols() on the PR):

pub(crate) fn features() -> &'static Mutex<HashSet<Symbol<'static>>> {
    FEATURES.get_or_init(|| Mutex::new(HashSet::default()))
}

Once LazyLock stabilizes, we can migrate the code from OnceLock to LazyLock, and benefit from some code removals: we'll remove the helper methods created to access them (using get_or_init). The code above would turn into something like:

/// Rust translation of the `features` variable: A list of symbols are the features
/// of the executing Emacs. Used by [`featurep`] and [`require`], altered by [`provide`].
pub(crate) static FEATURES: LazyLock<Mutex<HashSet<Symbol<'static>>>> =
    LazyLock::new(|| Mutex::new(HashSet::default()));

Why this task should be completed?

It reduces the need of using helper functions, which just saves a handful lines of code. OnceLock will work the same way with the same guarantees, paired with the helper functions.

Acceptance Criteria

• You have verified the code can run on the beta channel: rustup default beta
• You have made sure the stabilization issue is closed and merged: issue tracker.
• You have tested the integration works with cargo build --release, cargo t, cargo clippy.

Who are the POCs or Stakeholders?

• @CeleritasCelery , @Qkessler

i just came to know about this great projects while i tried to compile it in my machine it caused stack overflow.

```Loading emacs-lisp/debug-early...
Loading emacs-lisp/debug-early Done
Loading emacs-lisp/byte-run...
Loading emacs-lisp/byte-run Done
Loading emacs-lisp/backquote...
Loading emacs-lisp/backquote Done
Loading subr...
Loading subr Done
Loading keymap...
Loading keymap Done
Loading version...
Loading version Done
Loading widget...
Loading widget Done
Loading custom...
Loading custom Done
Loading emacs-lisp/map-ynp...
Loading emacs-lisp/map-ynp Done
Loading env...
Loading env Done
Loading format...
Loading format Done
Loading window...
Loading window Done
Loading files...
Loading pcase...
Loading macroexp...
Loading macroexp Done
Loading pcase Done
Loading easy-mmode...

thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\debug\rune.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)`

In order to map between the Rust and Lisp worlds, we have to handle aliasing. Data structures must be both mutable and aliasable. The "simple" solution to this is to use the a RefCell. However we also need to support the maphash function, which iterates over a hashmap taking a closure.
We need to iterate through a hashmap while also mutating it. Current iterators don't allow this, they expect to borrow the hashmap for the duration of the iteration, meaning we can't borrow it mutabley, even with RefCell.

1 - current solution only get's us half way

The current solution is only a stop gap approach to bootstrap. It allows us to mutate individual values, but we can't add or remove elements from the hashmap. This is done by making the value of a hashmap a Cell.

    pub(crate) type HashTableView<'ob, T> = HashMap<GcObj<'ob>, T>;
    pub(crate) struct LispHashTable {
        gc: GcMark,
        is_const: bool,
        inner: RefCell<HashTableView<'static, ObjCell>>,
    }

2 - create a hashmap that is backed by indexes, then use the index for iteration

Instead of using the hashmap iterator, if we had a hashmap that was indexable, we could use the index for iteration instead of holding a reference. Not sure if a crate exists, or if we would need to implement our own hashmap.

This is similar to #2. We have bind function for Arena.

This relies on a safe trait ConstrainLifetime which let's us take object and "bind" it's lifetime to the Arena. We use this in case were an object may have root lifetime.

Why this is sound

It may seem odd that ConstrainLifetime is a safe trait, but you can't implement it in a way that would be unsound without unsafe code, so calling the trait is safe. All implementation would need to be unsafe, and by writing that unsafe code you have to uphold the invariant of ConstrainLifetime. This requires that the implementer is gc managed type.

impl<'old, 'new> ConstrainLifetime<'new, Object<'new>> for Object<'old> {
    fn constrain_lifetime<const C: bool>(self, _cx: &'new Block<C>) -> Object<'new> {
        // Lifetime is bound to borrow of Block, so it is safe to extend
        unsafe { transmute::<Object<'old>, Object<'new>>(self) }
    }
}

It is safe to call bind because so long as we are borrowing from Arena then garbage_collect can't be called, meaning the object cannot be freed even if the root it came from goes out of scope.

(First, very cool project, I hope I'll be able to contribute in the future!)

Hi, I was looking at LCellOwner after your recent blog post and noticed the comparison on the LCell's pointers in rw2 to avoid aliasing mutable borrows, and I was wondering if you had taken into consideration pointer provenance?

I wouldn't do a good job at explaining the concept so I'll refer you to some articles (series, really) from very smart people and the nightly docs:

• https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html
• https://gankra.github.io/blah/fix-rust-pointers/#distinguish-pointers-and-addresses
• rust-lang/rust#95228
• https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance

But in short pointers shouldn't be casted to integers directly and .addr should be used instead (or the stable polyfill's)

Emacs regex is similar to PCRE regex. In that case we could use the fancy-regex crate (which implements a backtracking engine), once #84 is fixed. However there are still several differences that would need to be handled.

meta characters

Emacs regex meta characters are backwards from what most regex use. For example () represent literal parens, and \(\) is a capture group. Also | is literal, and \| is alternation. This is easy enough to fix with pre-processing the regex.

syntax aware matches

Several of the regex patterns match on the syntax definition of characters.

• \w: word character
• \s: match syntax class

"Word" and "symbol" are defined by the major modes syntax table. You could transform these into general character classes ([...]) for the rust regex engine.

There is also the special character \=, which matches the point. To handle this you could split the buffer into two parts; before point and after point. Then match each half separately.

boundaries

Emacs defines a regex for the boundary of words and symbols.

• \<: beginning of word
• \>: end of word
• \_<: beginning of symbol
• \_>: end of symbol

these will need to be implemented with look-arounds. You can’t even build them into the regex engine because they can change per major mode.

Buffer Gap

Most performance oriented regex libraries expect to operate on contiguous data. However a gap buffer will have a gap of garbage data somewhere in the buffer. This becomes a problem when the span of the regex search crosses the gap. The simplest solution here is to move the gap outside of the range of the search. This could performance issues if the lines are really long. We also have to consider how to match multiline regex. Not sure of a good way to handle that. Here are some notes from the remacs project.

I see there is a TypeError defined in core/error.rs. However, the Emacs C code often has something like:

return wrong_type_argument (Qchar_or_string_p, obj);

Does that mean the Type enum needs to learn about "CharOrString" and all the other permutations of this?
I bumped into this while exploring what it would take to implement downcase.

In our wrapper code around native functions we something that looks similar to this

let val = native_func(objects[0], objects[1], &mut arena)?;
Ok(crate::object::IntoObject::into_obj(val, arena))

we are calling some native function and then converting the return value into an object using arena. However we have the same problem here that we have in #2 with rebind!; val is now bound to the mutable borrow of arena, meaning we can't use arena for into_obj. We can't use the rebind! macro here because val is not yet an object. So instead we insert the following work around:

let ptr = arena as *mut Arena;
let val = func(objects[0], objects[1], &mut arena)?;
let arena: &'ob mut Arena = unsafe {&mut *ptr};
Ok(IntoObject::into_obj(val, arena))

here we are creating a raw pointer to Arena then using that pointer to later create a new "shadow arena" that is not borrowed from and can be used for into_obj. See the actual code below.

Why this is sound

the original &mut Arena is not used again in this scope, so we don't have overlapping mutable borrows. We really don't want arena to be mutably borrowed here, but we don't have a choice due to limitation in the type system. The new "shadow" arena has the same lifetime constraints, but is free to be used. We know the object is still valid because we don't call garbage_collect here.

I believe that --repo here should be --repl

The plan for the garbage collector is to be generational, copying collector. The old generation will use Immix style mark region collector, which Jon Harrop calls a breakthrough in gc design. I don't fully understand yet why it is so great, but the rust interpreter folks used immix for their project as well. Our current implementation already allows for copying object pointers via indirection, so we have the ability to implement this.

When to promote objects to the Major heap?

A typical generational GC will promote objects after the survive N minor heap collections, where N is usually 1. However we can take advantage of the execution patterns of Emacs. Commands in Emacs are usually run in short bursts with lots of waiting. Everytime you type a character or run a command, emacs will evaluate some code. The best time to run GC is after the command completes and the display has been updated. This is also the best time to promote objects, because anything that is still live will typically live for a long time. If the current command generates so much garbage that it fills the minor (nursery) heap, then we could use Chenny's Semi-space copying approach to remove dead objects, without promotion.

There is some discussion of my thoughts on multi-threaded Emacs here. Read that first. This project gives us a unique opportunity to make the interpreter thread safe. I am generally of two minds about how to handle multi-threading.

idea 1 - CSP all the way

CSP or "communicating sequential processes" is the most flexible way to implement parallelism. This is the approach used by languages like go and clojure. You essentially create first-class channels that can be passed around to other threads, and then only communicate through those channels. This let you build a topology of "communicating processes" that can sequence with each other as desired. It is very simple, flexible, and powerful.

However, you run into the issue that this method could not be made backwards compatible with existing GNU Emacs runtime. That runtime has no ability to suspend and resume threads of execution in the way that would be needed to mimic CSP. You could in theory do this with existing Emacs threading API, but is very unstable and will crash your Emacs, so it is not ready to be used. However if the threading library was ever made robust, then you could in theory model CSP in GNU Emacs.

Idea 2 - coroutine style

GNU Emacs supports stackless coroutines (called generators), which allow for basic concurrency. If you limited your multi-threading API, you could have it map to coroutines as a polyfill. This would mean you would not have to write code twice, once for multi-threading, and once for not. I imagine it looking something like this.

(let ((num 0)
      (go (goroutine (lambda (x) (yield (1+ x))))))
  (setq num (resume go num))
  (message "%d" num) ;; prints 1
  (setq num (resume go (+ num 2)))
  (message "%d" num)) ;; prints 4

This would limit thread to only communicating with the thread that spawned them, and only yielding values in the top level function (since Emacs coroutines are stackless). But you would not need an explicit channel type, and it would be easy to create polyfill version of goroutine, yield, and resume so that the same code would work in GNU Emacs and a multi-threaded Emacs. I don't like this solution as well as just using CSP. But maybe the backwards compatibility would be worth it.

why not use async/await for the backend?

I don’t think using Tokio or any other async await platform would be worthwhile. Fundamentally, they don’t offer any feature that you wouldn’t already get with threads. Plus async brings its own problems.

First is that you have to introduce function coloring into codebase. Everything needs to have two versions. Plus async code is messier and harder to reason about. We are not writing a web server, so we don’t need that complexity.

The only real advantage of async is lower resources usage. Green threads take significantly less space compared to system threads. But this is only really a concern when you want thousands of threads or are memory constrained.

The other advantage is that they can switch context a little faster because they pin threads to cores. However I see this as a disadvantage. In tokio you need to tell the runtime upfront if something is going to be compute heavy or IO heavy. But since the threads are in elisp, we can’t know that ahead of time. Many modern CPU’s have both performance cores and efficiency cores. The kernel will try to move compute heavy tasks to the p-cores and IO heavy tasks to the e-cores. But tokio can’t do that because the threads are pinned!

Also async only supports cooperative multitasking, which means a task that doesn’t play by the rules can starve others. But OS threads are preemptive, so that can’t happen.

What should be shared and what should be thread-local?

Things that are going to change only rarely such as functions can be shared between threads. However most other things like variable bindings and properties will be thread local. However to better support integration with existing elisp, thread local types will be copied to a thread as needed. This ensures that users don't have to worry about "is this variable defined in this thread or not", but still protects us from data races and other nasty concurrency bugs.

how to handle variable bindings?

As described in the previous section, the current idea is have variable bindings and symbol properites copied to other threads "on demand". Essentially when a thread first tries to access a variable that it does not have defined locally, it will send a message to the it's parent thread and ask for the current value via a channel. The parent thread will copy send a message back with the value, or message indicating that the variable is undefined. The child thread will wait until it receives a message back before continuing execution.

how to handle errors

When an error occurs in another thread, what do you do? Any channels connected to that thread would become poisoned, and would signal an error if you tried to read from them. But what about threads that don’t communicate with the main thread. Maybe you wanted to delete a file in the background or something. Raising it randomly back to the mail thread seems really disruptive. But it could also be a foot gun if it just silently ignores the error. Maybe it just prints it as s message.

Executive Summary: I propose that it would be worth while to have Rune dump it's serialized state into a binary file that could be reloaded at a later time to cut down on load times. Usage being that I evaluate a large amount of elisp, dump to a file, and load my VM using that dump'd elisp to cut down on load time. Creating this binary file may require a special mode when creating the VM (depending on implementation), but loading the file would not require any special mode. Loading the file would be done at VM initialization and would not be expected to be done "mid run"

For a long time, part of emacs build process was it's famous "unexec" flow, where you would load a minimal version of emacs, evaluate a large amount of elisp, and if I recall correctly, then dump part of your process heap into a binary that would be loaded into emacs BSS memory area. Eventually emacs replaced unexec with the portable dumper (https://github.com/emacs-mirror/emacs/blob/master/src/pdumper.h) which isn't as fast, but is much more maintainable.

v8 (Google's Javascript engine) also has a somewhat similar functionality for it's Isolates - this is how Deno is able to load the typescript interpreter so quickly. They actually load the interpreter in v8 with their hooks during build time, and dump the binary state that is loaded at run time.

Advantages are a notable speedup for targeted applications that load a large amount of elisp. The downside is complexity, but I think with Rust's great serialization libraries and support, this could be done with moderate effort.

A step further (and more similar to v8) is that instead of seeing the entire VM with this file, we can seed a thread with this file containing binary state, so that I can have separate threads loaded up very quickly with pre-seeded memory content with minimal overhead.

This uses the same principle as the root_struct! macro. So if this is sound I expect that will be as well.

We create a new StackRoot using an unsafe method. We then set the stack root, which will push the object on the RootSet. This will be popped when root drops. If the this stack like behavior of the drop glue does not happen, this will lead to UB.

Why this is sound

The new method on Root is unsafe to call, and requires that root is dropped in stack order (i.e. does not move).

impl<'rt> Drop for StackRoot<'rt> {
    fn drop(&mut self) {
        self.root_set.roots.borrow_mut().pop();
    }
}

Similar constraint as pin_mut macro. We make sure of this by never exposing the binding of root. We also require that set is called before the object is used, which is part of the macro code. Set has the follow definition ensuring that the object is borrowed for the lifetime of root.

    pub(crate) fn set<'root>(&'root mut self, obj: Object<'_>) -> Object<'root> {
        ...
    }

Emacs ships with over 7000 elisp tests. Bootstrapping these tests would make a good milestone and help ensure correctness. These tests can be run with make check in GNU Emacs.

The two main options for a buffer struct is a gap buffer, or a rope. They both come with different tradeoffs. I really like this comment from the author of a Rust rope crate.

I don't think the tradeoff between gap buffers and ropes is really about file size. At small file sizes anything will work. You could just use a plain contiguous string if you wanted, and it would be totally fine. The whole point of using something like a gap buffer or rope or piece table or whatever is to avoid the shortcomings of something like a contiguous string as files get larger.

Gap buffers are actually great for large files, as long as the editing patterns are favorable. Specifically, for localized edits gap buffers are O(1), which is amazing. And for single-cursor editors, localized edits are pretty much the only case that needs to be handled interactively. So gap buffers are great (even with huge files) for such editors. However, gap buffers degrade to O(N) as edits get less and less localized. So if you want your editor to support non-localized editing patterns, gap buffers probably aren't great.

Ropes make a different performance trade-off, being a sort of "jack of all trades". They're not amazing at anything, but they're always solidly good with O(log N) performance. They're not the best choice for an editor that only supports local editing patterns, since they leave a lot of performance on the table compared to gap buffers in that case (again, even for huge documents). But for an editor that encourages non-localized edits, or just wants flexibility in that regard, they're a great choice because they always have good performance, whereas gap buffers degrade poorly with unfavorable editing patterns.

In other words, regardless of file size, gap buffers have both a better best case and worse worst case compared to ropes.

It's worth noting, however, that even multiple cursors are frequently quite localized. Most of the time I use them, for example, all cursors are still in view (or nearly so). It's really only with editors that are built around multiple cursors as the way to edit things that you commonly do interactive non-local edits.

So for something like emacs, I suspect any real arguments in favor of ropes or piece tables (or whatever else) aren't going to be about editing performance, but rather are going to be about secondary features like cheaply taking "snapshots" of a document to save it asynchronously, etc.

Like the author said, gap buffers have great performance. And they are much simpler then other data structures like ropes. It also makes things like regex much more performant.

Given all that, I think sticking with a gap buffer is the right choice. Most of complaints about Gap buffers is just misunderstanding.

edit: fixed misquote

The question is in the title.

What are some good easy issues that I can help tackle?.

This one is a beast.

Essentially what we need to do here is create a iterator where the returned value is rooted on each iteration and can only live for that iteration. This is because Cons cells are globally mutable and elements of the list could become unreachable at any point. So if the objects outlive their iteration cycle they could potentially get collected and lead to use-after-free. The only way to do this without GAT's is to use the streaming-iterator crate. This redefines the Iterator next method to bind the lifetime to the borrow of the iterator like this.

    fn next(&mut self) -> Option<&Self::Item> {
        self.advance();
        (*self).get()
    }

So this means we need a way to root the Item on every cycle. So we declare two new roots (one for the item, one for the cons we are using for iteration).

let mut gc_root_elem = unsafe { $crate::arena::RootStruct::new($gc.get_root_set()) };
let mut gc_root_cons = unsafe { $crate::arena::RootStruct::new($gc.get_root_set()) };

However we have to handle the case where the iterator is empty. In that case we can't set the root because we don't have anything to set it with (see #3 for the invariant of rooting). So we declare some Option types that will hold our pinned location on the stack.

let mut root_elem = None;
let mut root_cons = None;

Then we can conditionally set the value of those Option types of our cons is not nil. If it is nil then we simply call forget on the roots so that the drop glue is not called. If the drop glue was called it would pop items off the root stack that we never pushed on.

if let $crate::object::List::Cons(x) = list {
    root_elem =
        unsafe { Some($crate::arena::Root::new($crate::arena::RootObj::default())) };
    root_cons = unsafe { Some($crate::arena::Root::new($crate::arena::RootCons::new(!x))) };
    gc_root_elem.set(root_elem.as_mut().unwrap());
    gc_root_cons.set(root_cons.as_mut().unwrap());
} else {
    std::mem::forget(gc_root_elem);
    std::mem::forget(gc_root_cons);
}

Why this is sound

We are using streaming-iterator to make sure objects can't escape an iteration cycle. During that iteration cycle, we ensure that both item and cons are rooted. The root locations cannot move and store an Option, which allows us to conditionally set them. If the cons we are going to iterator over is nil then we make sure to forget the root so drop glue is not called.

Emacs has a unique scheme for representing strings.

src/character.h

  character code	1st byte   byte sequence
  --------------	--------   -------------
       0-7F		00..7F	   0xxxxxxx
      80-7FF		C2..DF	   110yyyyx 10xxxxxx
     800-FFFF		E0..EF	   1110yyyy 10yxxxxx 10xxxxxx
   10000-1FFFFF	F0..F7	   11110yyy 10yyxxxx 10xxxxxx 10xxxxxx
  200000-3FFF7F	F8	       11111000 1000yxxx 10xxxxxx 10xxxxxx 10xxxxxx
  3FFF80-3FFFFF	C0..C1	   1100000x 10xxxxxx (for eight-bit-char)
  400000-...		invalid

  invalid 1st byte	80..BF	   10xxxxxx
           F9..FF	   11111yyy

  In each bit pattern, 'x' and 'y' each represent a single bit of the
  character code payload, and at least one 'y' must be a 1 bit.
  In the 5-byte sequence, the 22-bit payload cannot exceed 3FFF7F.

Raw 8-bit bytes are represented by codepoints 0x3FFF80 to 0x3FFFFF. However, in the UTF-8 like encoding, where they should be represented by a 5-byte sequence starting with 0xF8, they are instead represented by a 2-byte sequence starting with 0xC0 or 0xC1. These 2-byte sequences are disallowed in UTF-8, because they would form a duplicate encoding for the 1-byte ASCII range.

Raw bytes are either plain ascii or if they are over the ascii range of 127, they are encoded using extended unicode codepoints. These extended code points don't follow the normal rules, and therefore will ocuppy two bytes in the space between the 1 byte and two byte range. For example if I wanted to encode 137 (#o211 #x89) as a raw byte, it would be code point 0x3FFF89. Notice that the hex value is the last byte of the code point. However I would lay it out in memory like this

• Original binary :: 1000 1001 (0x89)
• remove eighth bit :: 000 1001
• encode using the table above :: 1100_0000 1000_1001

This encoding scheme is clever and flexible, but is unique to Emacs. It means that you can't reuse any string processing libraries that are expecting unicode, because Emacs supports a superset of unicode. We would like to avoid this limitation if at all possible.

Currently the plan is two have two types of string; unibyte and multibyte. unibyte strings are raw byte arrays ([u8]) and multibyte are valid utf8 (str). There is no concept of a "raw byte" in a multibyte string. Adding one will automatically convert it unibyte.

So far the only places I have seen unibyte strings used in the bytecompiler (for opcodes) and when viewing non text files (like a binary). Given this, I think we can get away with changing the behavior with regards to string and bytes. 99% of users will only ever work with valid multibyte strings. There may be more edge case that we need to work around in the future, but I think that effort is better then the effort of re implementing all text processing to handle a unique encoding. Hopefully this is the right trade-off. We will try to use byte arrays throughout the code when valid unicode is not needed.

Buffers will also need to come in two flavors, a UTF8 one and a raw byte version. Or we could use the same buffer type but convert all non-ascii bytes to their equivalent codepoint. We would need to make sure to handle this specially in search though.

Emacs docs
github comment with explanation
Emacs uses an extended UTF-8 internally. It uses code points beyond the extended plane and can therefore use up to 5 bytes instead of the normal 4 for unicode. It also has a special "raw byte" encoding that is used for 128-255 encoding.

raw byte encoding

src/character.h

character code	1st byte   byte sequence
--------------	--------   -------------
     0-7F		00..7F	   0xxxxxxx
    80-7FF		C2..DF	   110yyyyx 10xxxxxx
   800-FFFF		E0..EF	   1110yyyy 10yxxxxx 10xxxxxx
 10000-1FFFFF	F0..F7	   11110yyy 10yyxxxx 10xxxxxx 10xxxxxx
200000-3FFF7F	F8	       11111000 1000yxxx 10xxxxxx 10xxxxxx 10xxxxxx
3FFF80-3FFFFF	C0..C1	   1100000x 10xxxxxx (for eight-bit-char)
400000-...		invalid

invalid 1st byte	80..BF	   10xxxxxx
         F9..FF	   11111yyy

In each bit pattern, 'x' and 'y' each represent a single bit of the
character code payload, and at least one 'y' must be a 1 bit.
In the 5-byte sequence, the 22-bit payload cannot exceed 3FFF7F.

remacs source

Raw 8-bit bytes are represented by codepoints 0x3FFF80 to 0x3FFFFF. However, in the UTF-8 like encoding, where they should be represented by a 5-byte sequence starting with 0xF8, they are instead represented by a 2-byte sequence starting with 0xC0 or 0xC1. These 2-byte sequences are disallowed in UTF-8, because they would form a duplicate encoding for the the 1-byte
ASCII range.

Raw bytes are either plain ascii of if they are over the ascii range of 127, they are encoded using extended unicode codepoints. These extended code points don't follow the normal rules, and therefore will ocuppy two bytes in the space between the 1 byte and two byte range. For example if I wanted to encode 137 (#o211 #x89) as a raw byte, it would be code point 0x3FFF89. Notice that the hex value is the last byte of the code point. However I would lay it out in memory like this

• Original binary: 1000 1001 (0x89)
• remove eight bit: 000 1001
• encode using the table above: 1100000 0 10 00 1001

00000 0000_1001

display

One tricky thing about this layout is that the same display representation can have two meanings. For example if I see

\211

It can either be codepoint 0x89, or codepoint 0x3FFF89, the former being a normal unprintable unicode character, the second being a raw byte from Emacs extended UTF8. This can be confusing.

solution 1 - Create custom Encoding format

This is the approach that Remacs has done. They basically have to reimplement all the string primitives on the new encoded format. This has the disadvantage that you can't reuse existing Rust libraries for strings. Things like regex will probably be okay, because they operate on &[u8] directly. But it will fail to match raw bytes, because they have a different representation.

Solution 2 - Use bstr and assume conventional UTF-8

We still allow inserting any byte value into the buffer, but if it invalid we just leave it. String will use the bstr approach of validing the UTF-8 as needed. This is useful there is a community of crates that support "conventional UTF-8" instead of "always UTF-8" that normal rust string follow. So long as crate takes [u8] or bstr, we can use it.

Hey! I found your project some weeks ago and found it super interesting - I am doing something similar, but in Go: https://github.com/federicotdn/pimacs.

Your project is more active than mine, but I thought it would be interesting to share ideas. Go and Rust are very different languages of course but some challenges are more or less the same regardless of the language. Some of the conversations For example I've seen the following topics discussed on this repo, that I've also thought about!

• Handling if strings, multibyte vs. unibyte, using plain UTF-8 vs. Emacs' custom UTF-8-like encoding
• Importing Elisp files from the Emacs codebase into Rune
• Concurrency! (a fun one to tackle in Go, given goroutines + channels)
• Implementation of an Elisp reader, bytecode interpreter and/or JIT compiler
• Testing in general (using Emacs' ERT?)

I've written about some of my design decisions here: https://github.com/federicotdn/pimacs/blob/main/etc/design.md. As a part of the project, I've written a Python script called extract.py that creates a JSON file with information about all the subroutine decalarations in Emacs, perhaps that could be useful for Rune as well! (https://github.com/federicotdn/pimacs/blob/main/test/data/emacs_subroutines.json)

I'm aware that a GitHub issue is not a great medium for these types of discussions, so please feel free to close it, as it is not really an "issue" with Rune itself. Cheers!

cargo build
error: failed to get get-size as a dependency of package text-buffer v0.1.0 (/home/declan/src/Rust/rune/crates/text-buffer)
... which satisfies path dependency text-buffer (locked to 0.1.0) of package rune v0.1.0 (/home/declan/src/Rust/rune)

Caused by:
failed to load source for dependency get-size

Caused by:
Unable to update /Users/troyhinckley/repos/get-size

Caused by:
failed to read /Users/troyhinckley/repos/get-size/Cargo.toml

Caused by:
No such file or directory (os error 2)

Hey,

this is a nice project. I had also thought before about creating an elisp runtime from scratch. One idea I had was to move as much as possible to Elisp, since Elisp is the substrate which ultimately makes Emacs hackable. The interpreter could be a metacircular interpreter written in Elisp itself (eval.c but in Elisp). The one needs a compiler which turns Elisp into native code, either precompiled or jit (cranelift?). In order to bootstrap one could use Emacs itself to produce a compiled version of the Elisp interpreter. The part in Rust would be as minimal as possible, only GC, basic primitives and maybe some higher level functions of critical for performance. Did you also consider such an approach?

"The defun macro is applied to any normal Rust function and it then becomes callable from lisp."

What does "any normal Rust function" mean? If I have a function that takes a Rust struct as a parameter (or which is a method of my own Rust object), will it work?

What should be done?

Publish a github.io page with the Cargo doc documentation from Rune or alternatively find a way to publish the docs without the crate being published to crates.io. It's not currently published and there are naming conflicts if we were to publish it as is (don't think this is something we should look into now)
​

Why this task should be completed?

​I have seen other crates / languages do that as well (see more details section), which makes the documentation easily consumable, not only directly in the code. That simplifies checking the documentation, as one would not need to do: cargo doc --workspace --no-deps to get all the crates documented.

Acceptance Criteria

• You have searched through alternatives to publish the cargo doc documentation online.
• If the suggested solution is the right one, publish a github.io page with the cargo doc --workspace --no-deps behaviour.
• The github page should be built with CI, so whenever a new commit happens, we don't need to manually publish the index.html pages. Create a job for it, to run on pushes to master, no need to run it on PRs.

Where can I find more details?

• Nice example, crate called rune (yeah, right): https://github.com/rune-rs/rune/blob/main/.github/workflows/site.yml
• Better example, the tracing crate: https://tracing-rs.netlify.app/tracing/
• Our current CI documentation: https://github.com/CeleritasCelery/rune/blob/master/.github/DOCS.md

Who are the POCs/stakeholders?

• @Qkessler
• @CeleritasCelery

With the moving GC, we have an issue where the hash values of keys can change during garbage collection. The hash of an object is taken from its value, which is just a tagged pointer. So when the pointer moves, so does the hash. There are a couple possible solutions to this.

1. store the hash value in the object header

This is what other dynamic languages like C# and Java do. This is easy because we only need to calculate the hash once and it will never change. However this also takes more memory, at least 4 bytes if we want a good hash. This is especially problematic for Cons, which are very common and should only be 2 words wide. This would require them to have a header, which they currently don't need.

2. rehash the keys during GC

This is the path we are going to take for now until we can think of a better solution. Every GC the hashmap keys will have to be recalculated and inserted. This is costly. The way we do this now is via RefCell that let's us mutate a HashMap during collection. But this means we could also have runtime panics if there exists a root to one of the hashmap values. Not ideal. Here is paper about how to handle this issue and make it lest costly.

Ideally we should define a custom HashMap that let's us rehash all the keys without moving the values. I think this might be possible, but it might also require us forking either HashMap or IndexMap.

3. Is there a possible third option?

• This works

fn main() {
    defvar!(SCRIPT_REPRESENTATIVE_CHARS);
...

• This does not work

defvar!(SCRIPT_REPRESENTATIVE_CHARS);
fn main() {

...

This really needs to be proc macro to auto derive since implementing is unsafe, but that is not yet implemented.

We get a RootRef by using RootOwner on Root. Root projection let's take a RootRef of a struct and get RootRef of the fields. This is similar to pin-project with a few big differences. First is that a Pin<P> hold a pointer to some data, but our type RootRef<T> hold the data itself. This means we can never return an owned RootRef (like you can we Pin) but instead return only references from our projections.

For example here is what is implemented for hashmap

We get the interior value which does not have RootRef on it (similar to how we would get a &mut T from a Pin<P> with get_mut_unchecked. Then we call the function we need (like get) and cast the return value &V directly to &RootRef<V>. This let's us use Root-only methods on V because we have transitively rooted it.

Why this is sound

RootRef is repr(transparent) so it is safe to cast it a wrapper, since we know the parent is rooted. The "child" reference borrows from the "parent", so it will follow rusts normal borrowing rules. This is the same logic that std::cell::Cell's as_slice_of_cells uses.

Several functions in this crate transmute integers to and from Data-containing enums. However, this is unsound, since both Data and the enums containing it are repr(Rust), which has no layout guarantees. To fix this, additional repr attributes must be added:

• In src/object/data.rs, Data must have #![repr(transparent)].
• In src/object/mod.rs, Object must have #![repr(u8, align(8))].
• In src/object/sub_type.rs, FuncCell must have #![repr(u8, align(8))].
• In src/object/sub_type.rs, IntOrMarker must have #![repr(C)].
• In src/object/sub_type.rs, Number must have #![repr(u8, align(8))].

Also, Data::from_raw() should really be marked unsafe. For a Data<&'a T> value to be valid, its data must be derived from an &'a T reference, and Data::from_raw() is unable to check this. Three new unsafe blocks should be added to the call sites: UNUSED, which is sound since a Data<()> is always valid; Data::<&'a T>::from_ref(), which is sound since ptr is derived from an &'a T reference; and Data::<i64>::from_int(), which is sound since a Data<i64> is always valid.

Finally, I have a minor question: Why is LCellOwner::new() marked unsafe? Is there any unchecked precondition or invariant it depends on?

as mentioned in #12, The current way of representing an Object as Rust Enum containing Data cannot comply with strict provenance because we have to convert a type to a int to convert it to an array. We need some better way to represent this.

My initial idea is to use generics. We define a new type Gc<T> where T is some object. if you have a Gc you can call .get() to return the enum inside. This enum will not contain Data but will instead be 2 words wide (i.e. not tagged). This enum will be used for matching the values.

Under the hood Gc<T> can implementing the tagging however it wants. Currently we are restricted to whatever layout rust picks for us. Also we will have some base object Object that contains all the tags. Because it is superset of all other objects you can always convert as Gc<T> to a Gc<Object>. We would also define conversion methods between all the object types. Maybe with proc macros.

This would also fix the problem we currently have where we need to convert a type to an object and then cast it back just to use it in certain functions. Now we will just make those functions generic so they work with all types.

I think we might be able to work around this by introducing a new trait. Right now the generated Deref for Env would look like this.

impl std::ops::Deref for crate::core::gc::Rt<Env> {
    type Target = __Rooted_Env;
    fn deref(&self) -> &Self::Target {
        unsafe { &*(self as *const Self).cast::<Self::Target>() }
    }
}
impl std::ops::DerefMut for crate::core::gc::Rt<Env> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { &mut *(self as *mut Self).cast::<Self::Target>() }
    }
}

We are always just doing a transmute (via pointer cast) to get the Rooted type. If we defined another trait like this:

pub trait RootedDeref {
    type Target;
    fn rooted_deref(&Rt<Self>) -> &Self::Target;
}

Then we could define a blanket Deref impl like this:

impl<T: RootedDeref> Deref for Rt<T> {
    type Target =  <T as RootedDeref>::Target;
    fn deref(&self) -> &Self::Target {
        RootedDeref::rooted_deref(self)
        
    }
}

Then in the proc macro we could define an impl like this:

impl RootedDeref for Env {
    type Target = __Rooted_Env;
    fn rooted_deref(rt: &Rt<Self>) -> &Self::Target {
        unsafe { &*(rt as *const Rt<Self>).cast::<Self::Target>() }
    }
}

That would avoid the orphan rule because we are not using a foreign type anymore. That would let us keep Rt in the core but still #[derive(Trace)] outside of the core.

Due to not having GAT's on stable, we have to define IntoObject with a lifetime parameter as part of the trait definition. This trait takes some type Self and converts into a gc object T with lifetime 'ob.

However when defining a generic method to check the interpreter we have to constraint 'ob to &'ob mut Arena.

    fn check_interpreter<'ob, T>(test_str: &str, expect: T, arena: &'ob mut Arena)
    where
        T: IntoObject<'ob, Object<'ob>>,
    {
         ....
    }

This requires that any new objects created in this function have the lifetime 'ob (per the trait definition), which means these objects have to live as long as Arena, which can't happen. So we work around this by creating a new Arena from the raw pointer.

Why is this sound

We don't actually need the lifetime 'ob to be part of the IntoObject trait, but we can't work around it without GAT's, which are still unstable. This is just a fundamental limitation of the lifetime and generic systems interacting. The new temporary arena we create just does not have to unify with 'ob, but is still safe to use since it upholds all other variants.

Opening this issue to discuss whether we can optimize the directory structure that we have on the project. The reasoning is that the lisp files are not something that will ever be modified as part of this project, but rather just a "fleeting" directory, where we add the files that are ready to be bootstrapped or similar.

I know that we have the bootstrap.el file with the tag RUNE_BOOTSTRAP and certainly that can stay, but what about having a git submodule of the Emacs core? That way, we can pull the changes that we need and even have a fork/branch with only the files working with Rune.

What do you think? Open to suggestions.

test core::env::test::test_init_variables ... FAILED

failures:

---- core::env::test::test_init_variables stdout ----
thread 'core::env::test::test_init_variables' panicked at 'called `Option::unwrap()` on a `None` value', /home/declan/src/Rust/rune/target/debug/build/rune-5da9fb7d4c9d8a64/out/sym.rs:656:62
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    core::env::test::test_init_variables

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 71 filtered out; finished in 0.00s

rustc 1.71.1 (eb26296b5 2023-08-03)

fn alloc<'b, 'a>(cx: &'a mut Context, token: &'b Token) -> Object<'b>
fn garbage_collect<'b, 'a>(cx: &'a mut Context, token: &'b mut Token) {}

This way we don't need to rebind! as the objects will borrow from the token instead.
a root will take a &Object and produce something not borrowed from token.
when we garbage_collect, we take a &mut token ensuring we rooted any pointers to the gc heap.

Hmm ig this doesn't actually work. didn't really thought this through

Normally an object has a lifetime parameter like object<'a>. However When an object is rooted in a struct there is no good value to set this parameter to. Really it should be something like 'self but that doesn't exist yet. So we store objects in a RawObj form that has no lifetime. It is similar to storing a raw pointer. The only way to safely get a normal object back out is if RootObj is wrapped in RootRef. This ensures that the object is rooted and safe to use.

Why this is sound

We don't have any methods with RootRef that expose the RawObj directly. We only create them from objects with lifetimes since those are guaranteed to be valid. So long as we can use root projection to get a raw object, we know the base struct it is part of is rooted and will be traced. Therefore it is safe to "dereference".

Hi! Recently I've been trying to understand the emacs display engine and write a simple front-end, then I found this project, which looks interesting. I want to share some of my thoughts on this, and learn about your idea of the ui system of rune.

the current state of emacs

Details can be found in dispextern.c and xdisp.c(has a decent documentation in its comments). To summarize, emacs build a glyph_matrix for each frame, and a sub matrix for each window. How these glyphs should be displayed is defined in text-properties, including face, display or invisible. Emacs will construct an iterator it over a buffer or string, finding these text-props, to build the desired glyph_matrix.
The major task of a display engine is /redisplay/. Emacs calls the C redisplay code all from lisp, as described in xdisp.c:

At its highest level, redisplay can be divided into 3 distinct
steps, all of which are visible in `redisplay_internal':

. decide which frames need their windows to be considered for redisplay
. for each window whose display might need to be updated, compute
  a structure, called "glyph matrix", which describes how it
  should look on display
. actually update the display of windows on the glass where the
  newly obtained glyph matrix differs from the one produced by the
  previous redisplay cycle

We can use sth like the fontified text prop to controll redisplay, as in font-lock-mode and jit-lock-mode, or just call redisplay or sit-for.

my thoughts

The first part, building the glyph matrix, is effcient enough. The problem is that we cannot separate the UI part from emacs, as the redisplay is part of the lisp VM itself. Moverover, user input will be blocked during redisplay, which leads to signficant lag on C-u or C-d sometimes. As you said in TODOs, a MVP editor model is desired, thus the display engine must be redesigned, both C side and elisp side. This is also mentioned in mailing list.

My question is,

1. how should the display API organized from lisp? We already have a huge codebase of setting faces and display props in elisp, which is powerful and flexible. For instance, the tex-mode make use of ascent and descent property to display suscripts, and prettify-symbols-mode is awesome either. How to perform these operations in a non-blocking way? My idea is that make put-text-property and other functions directly interact with the ui layer, as a lisp subprocess. But I dont know if this is possible, or the proper way of doing so.

2. Should emacs adopt a server-client mode, i.e. a separate process like NeoVim does? Neovim use RPC to implement the client-server communication, but I don't think this is the proper way for emacs. Here the same question appears once more: what should the ui part do? Just give the ui thread a buffer and text-prop maps, then let it do the rest? Or should we compute the glyph matrix in the backend, and send it to the ui?

3. The text buffer structure. I've learnt from your articles that gap buffer is fast, but indexing line numbers would be a problem. If I understant correctly, that means commands like consult-lines or swiper is easier to implement in rope or piece table? Or can I say that the latter 2 data structures is more feature-rich than rope buffers? How about incremental redisplay, emacs implement inc redisplay in a pretty complex appoarch, Idk if this will be better if we have more buffer apis.

I'm just start learning things about text editor's design and implementation these days, so many of my thoughts could go naive or wrong. Would be glad to hear your response!

Emacs already offers AOT compilation via native compilation. By doing so you can remove the overhead of the bytecode interpreter and optimizing the code as a single compilation unit (which results in better code).

However there are a few things you loose by compiling ahead-of-time:

1. You don’t have any type information. Since elisp is dynamically typed, you have to assume that your input arguments can be any type. Sometimes you can do type inference because the built-in function usually have type requirements, but it is limited in the elisp world.
2. You don’t know what code paths are most important. Since the code has never been run when it is compiled, you don’t know what code paths are “hot”. So everything is compiled the same.
3. You have limited ability to inline. Only builtin function can be inlined, because any function in elisp can be dynamically updated.

Both of these can be solved with a little run time information. If you are able to profile the code as it runs, you can see what types it gets called with (which is usually the only types it will use) and you know which functions get called frequently. This allows for more aggressive optimizations then AOT and let’s you only compile the functions that actually matter, because 95% of them are not worth the effort.

tracing vs method JIT's

tracing JIT's start by looking for backwards jumps (i.e. the end of loops). They then trace every instruction until the same point is hit again, essentially make a "trace" of the loop body. This trace is then JIT compiled and spliced into the program stream. Since most hot code is in loops this tends to work very well. It also has the advantage that the trace has no branches and so better take advantage of code motion. Also you don't need to worry about inlining, because methods are automatically inlined in the trace.

The other camp is method JITs. Here you just look for "hot" methods, record type information about the arguments and branches, and then JIT compile the method.

From what I understand of the real world use cases, tracing JIT's can have better peak performance, but also tend to have more pathological cases that are harder to debug. Tracing JIT's are very sensitive to parameter tuning. method JIT's don't have the same max speedup but are more consistent and less pitfalls. Overall I see them as simpler to comprehend and debug.

We are striving to be “bug compatible” with GNU Emacs, in so far as it makes sense to do so. We might break with some behavior if it is obscure enough or adds enough value to justify it. But the right answer to “what should this function do?” Is almost always “whatever GNU Emacs does”.

Given that, we would like to have a way to test against Emacs and compare behavior. This issue is to brainstorm the best way to do that.

Currently the plan is to create a new rust binary that can feed a test file into Rune and GNU Emacs and make sure they get the same output. If one throws an error, so does the other. And the result of each expression is the same.

This can be expanded to include fuzzing/property testing. There could be some code to parse each built in function in Rune and get the type signature. We could then test the arity, accepted types, and random values against GNU Emacs. This would help flush out edge cases and differences in behavior. It could also help us catching changes between major version upgrades of GNU Emacs.

We could also create dedicated fuzzers for specific functionality. For example we have some code to convert a lisp regex to a rust regex. We could send in random regex and ensure that if Emacs considers it valid, then it is also converted to valid rust regex. Another example is printing; ensuring that printed representation of everything is the same.

This suggestion uses a little extra memory to save a little bit of time.

Change the type of mark from a boolean to an integer, and add an integer gc_count which keeps track of how many times garbage collection has happened.

When marking objects as being accessible, assign the value of gc_count to the 'mark' of every reachable object.

Objects whose mark is not equal to gc_count can be freed.

For objects being kept, the mark can be left as is.

If you come across an object whose mark is not gc_cur or gc_cur-1, panic.

If you think corruption is inconceivable, leave mark as a bool, but on alternate GCs, cycle between assigning true and false to it

The WithLifetime trait is a unsafe trait that let's us be generic over changing the lifetime of some type. This is equivalent to

let x: &'old = &T;
&'new *(x as *const T)

However lifetimes can also be type parameters of generic types. For example T could be a Vec<&'a i32>, but in generic code you don't have access to the lifetime parameters. So we create this new trait that lets us transmute the lifetime. However the problem with this trait is that the output type is different then the input type, even though they are really the same type but with different lifetime parameters.

For example here is the implementation for a GcManaged reference.

why this is sound

This trait is only safe to implement for types that are managed by the GC. The output type must only be the input type with the lifetime set to 'new. And even then we have to take care when calling it. The Out GAT is constrained to the 'new lifetime, and that lifetime is a parameter of the trait bounds. Here is an example usage

    pub(crate) fn bind<'ob>(&self, _: &'ob Context) -> <T as WithLifetime<'ob>>::Out
    where
        T: WithLifetime<'ob> + Copy,
    {
        // SAFETY: We are holding a reference to the context
        unsafe { self.inner.with_lifetime() }
    }

Here the output of this functions is <T as WithLifetime<'ob>>::Out and the trait bounds specify the lifetime we want to transmute it to. Since T implements WithLifetime we know that is is safe to bind to the lifetime of the Context because it will not be dropped as long as that immutable reference exists.

This is the issue tracking my work to move the core out to the workspace crate rune-core. I have the code in my fork, almost ready to PR, though I had some issues with Miri. I wanted to create the issue to get some ideas over ways to resolve the problems, and introduce @CeleritasCelery to the different changes on my PR first to get some early feedback. Here's the commit.

It's key to note that in the process, we include different changes that guide the build process of the crates, in order
to arrive at a place that is both ergonomic and easy to maintain:

We removed the defvar, defvar_bool and defsym macros. They were not adding that much regarding work saved (just
create a constant and initialize it) and they were convoluting the dependency graph between the crates. It's key that
the core crate can use the symbols that were previously generated on the build.rs file, but it does not need to know the
defuns.

For that, we moved the variables and symbols (not the defun symbols) to a static file env/sym.rs. That file contains
all the required constants for the variables and symbols.

// Symbols without the defuns
pub static BUILTIN_SYMBOLS: [SymbolCell; 84] = [
    SymbolCell::new_const("nil"),
    SymbolCell::new_const("t"),
    SymbolCell::new(":test"),
    SymbolCell::new(":documentation"),
    SymbolCell::new("md5"),
    SymbolCell::new("sha1"),
    SymbolCell::new("sha224"),
    SymbolCell::new("sha256"),
    ...
];

// also include init_variables.

On the other hand, the defun symbols and constants are still generated with the build script, to avoid loosing the
convenience of defining the functions with the defun proc macro.

/// Contains all the dynamically generated symbols for `#[defun]` marked functions.
pub(super) static DEFUN_SYMBOLS: [SymbolCell; 202] = [
    SymbolCell::new("floor"),
    SymbolCell::new("float"),
    SymbolCell::new("make-keymap"),
    SymbolCell::new("make-sparse-keymap"),
    SymbolCell::new("use-global-map"),
    SymbolCell::new("set-keymap-parent"),
    SymbolCell::new("define-key"),
    SymbolCell::new("message"),
    SymbolCell::new("format"),
    SymbolCell::new("format-message"),
    ...
];

// init_defun now does not need to take a range on the array.
pub(crate) fn init_defun() {
    for (sym, func) in DEFUN_SYMBOLS.iter().zip(SUBR_DEFS.iter()) {
        unsafe { sym.set_func((*func).into()).unwrap(); }
    }
}

The issue is that Symbol::get makes a ptr dereference over the BUILTIN_SYMBOLS (which now don't include the defuns) so if we try to get a defun symbol, we UB. Here's the test triggering it:

#[test]
fn test_bytecode_call() {
    use OpCode::*;
    let roots = &RootSet::default();
    let cx = &mut Context::new(roots);
    defun::init_defun();

    // (lambda (x) (symbol-name x))
    make_bytecode!(
        bytecode,
        257,
        [Constant0, StackRef1, Call1, Return],
        [defun::SYMBOL_NAME],
        cx
    );
    check_bytecode!(bytecode, [defun::SYMBOL_NAME], "symbol-name", cx);
}

There we check the bytecode for defun::SYMBOL_NAME, which is no longer part of BUILTIN_SYMBOLS. What do you think? What could potentially be a solution?

Given Emacs already small community it would be best if you were explicit with contributors about whether you ever wanted to contribute any of this code upstream.

Ie in the contributors landing area either say -

"I haven't assigned copyright to the FSF and do not expect contributors to, so be aware this can never be part of Emacs"

or

"I've assigned copyright (or will be) to the FSF and ask contributors to do so so that we could someday think about making some of this part of Emacs"

Both Remacs and Emacs-ng didn't do the copyright assignment (which is fine) but they also failed to mention this to their contributors and potential contributors (which is not fine, as I think people deserve a simple warning).

@Ki11erRabbit I was adding some more tests for string-distance and I found a case the causes a panic.

 assert_eq!(3, levenshtein_distance("kitten".chars(), "sitting".chars()));

Currently the core object type is represented as a raw point *const u8. A value of nil is represented by a null pointer. If we changed this to a NonNull<u8>, it would enable types like Option<Object> to be only a single word. However we would have to change the value of nil to something else (most likely 1). Not sure if this would be worth it, because we use nil a lot more than we do Option<Object>, but if changing nil to 1 instead of 0 had no real effect then it could be worth while.

Currently all allocation are part of a big enum. This is very space inefficient, since each enum instance has to be the size of the largest variant. We need to create an object header that contains the size of the object in it, which will be much more space efficient.

Solution 1 - Embedded the header directly in the objects

Since all the object types are gc-only, we could keep the header directly in the object struct. Something like this:

struct LispString {
    header: ObjectHeader,
    // other fields
};

However in order to make this work, the struct would need to be #[repr(c)]. I don't like that because it means that the compiler can't optimize the layout, and we would need to do it by hand. However it would probably be the easiest solution.

Solution 2 - Store the header separately

Instead of storing the header in the object struct, we could store it only in the heap. The pointer to an object would have provenance over both the Header and the object.

struct ObjectHeader {
    type: Type,
    size: usize,
}

One problem with this approach is that if you take a reference to the Object itself (references only have provenance to the thing they reference), you loose the ability to access the header. Solution 1 is probably simpler.

The rebind macro has this definition:

We are casting the object into a raw form that removes the lifetime. Then we call an unsafe function to create a new object from that raw pointer

Why this is safe

We are not actually changing the &mut reference to Arena. Instead we are releasing it then reborrowing it immutabley. We make sure to shadow the name so the old binding is no longer available.

There is conflict between the Rust world and the elisp world. Rust expects types to have explicit compile time alias checking, and elisp says you can alias anything you want. We need solution to make both of these worlds happy.

Elisp string are mutable. This might not be such a big deal except for the fact that since not all characters (code points) are the same size, you may need to reallocate the string when mutating it. So we need some way to mutate aliasing strings in Rust.

Take the following code sample:

    let str1 = "foo".into_obj();
    let str2 = str1;
    mutate(str1.untag(), str2.untag());
    
    fn mutate(str1: &LispString, str2: &LispString) -> &str {
        let slice: &str = str1.get(); // take a immutable reference through str1
        str2.set_at(0, 'å'); // mutate the string through str2, requiring a reallocation. This will drop slice
        slice // return the now ivalidated slice
    }

We need to find some way to handle this situation.

1 - current solution: RefCell

The easiest way to handle this from and implementation point of view is using RefCell. This is how thing are currently setup. However this comes with some big downsides. For one, we add overhead to all string access, including immutable access. Second, and probably most important, is that we open up the opportunity for runtime panics. Mutating a string should never be an error (unless it is const).

2 - copy on write

Since the problem is that all references to the string get invalidated on mutation, we could just make a copy instead. So anytime you mutate a string, it keeps the old string buffer valid until the next garbage collection. It would just update the "current" string buffer to point to the new copy.

This has the advantage of being simple implementation wise, but makes the mutation expensive. Probably the only reason you would be using mutation from elisp is to because of performance, now that is gone. This might be okay, because string mutation is a relatively rare operation in elisp.

3 - unsafe

There are only a few function that actually mutate string from elisp:

• aref
• store-substring
• clear-string

Maybe it would be worth it to just mark mutation as unsafe, and require the user to ensure no aliasing happens? There would not be that many unsafe blocks to inspect. This would be fine so long as the mutation subr's are only called from elisp, but if another rust function calls them, all bets are off.

Currently the reader has a defined type for errors, but it is stored as part of the Token enum. This is not idiomatic Rust. A better way to handle this would be to have the reader functions return a Result<Token, Error>. This would let us take advantage of the try operator (?) and have more idiomatic code.

The soundness of the code heavily relies on the fact that only one Arena exists in a thread at a time. Otherwise you might have code that borrows from an Arena that it does not own. And could then get collected and have use after free.

let arena1 = Arena::new();
let arena2 = Arena::new();
let foo = arena1.add("foo"); # arena1 owns foo
rebind!(foo, arena2); # foo now borrows from arena2
arena1.garbage_collect(); # foo will be freed but still accessible

To guarantee this we have singleton check that makes sure two can't be created at the same time.

Why this is sound

We can only have one global Block (part of Arena) and one thread local one. The global version is already created in our global symbol intern struct so any attempt to create another would panic. This global Block is not exposed to user unless they are editing the symbol intern struct.

If we attempt to create two thread local arena's it will panic, which is safe. However if these checks could ever be circumvented it would be unsound. But I think that is impossible.

To this point, all values associated with a global function were marked read-only. They are shared between threads so mutation would not be safe. However when working on bootstrapping cl-generic I ran into an issue where the function is actually a closure that closes over the value of the method-cache variable. When a generic function is dispatched, the value is first looked for in the cache, and if not found it is added. However this causes a problem with our assumption that function data is not mutated.

possible solutions

1. Make function thread local. This would make the issue go away, but would also mean that we have to copy every function that a thread needs to that thread. That will be a lot copying that we don't normally need (the vast majority of functions can be treated as immutable). It also means that function lookup will be more expensive because we can't use a stable address but instead need to do a hash lookup for each symbol.

2. Make LispHashTable thread safe. We could wrap it in an Arc and therefore make is safe to access from multiple threads. However this would make code harder to reason about because we could have hash-table mutated under the hood and we get spooky "action at a distance". It will also probably make hash table access slower. This also would do nothing to help if some other data type was used that is not a hashtable.

3. Make closure values thread local. We could treat data inside the function as immutable, but closed over variables are handled just like normal variables (thread local and copied on read to other threads). The key for lookup would be a tuple (function-name variable-name). For the global function we would have some sort of marker value (can't be any existing value) to indicate it needs to be looked up. for generic functions, this means that the first time we call one we have to copy the entire method-cache to the thread (even though we only care about that one method). Also if a function is bytecompiled we don't have a way of determining which constants are closed over values and which are "normal".