Table Definition

Lua's table is externally represented as a unified hash table, and its index can be a number, a string, or all other Value types except nil and Nan. However, for performance considerations, there is a special treatment for numeric types, that is, an array is used to store items indexed by consecutive numbers. So in the implementation, the table is actually composed of two parts: an array and a hash table. For this we define the table:

pub struct Table {
    pub array: Vec<Value>,
    pub map: HashMap<Value, Value>,
}

In order to support the characteristics of the meta table, other fields will be added in the future, which will be ignored here.

The table (and thread, UserData, etc. introduced later) type in the Lua language does not represent the object data itself, but just a reference to the object data, all operations on table types are references to operations. For example, the assignment of a table only copies the reference of the table, rather than "deep copying" the data of the entire table. So the table type defined in Value cannot be Table, but must be a reference or a pointer. When the string type was defined in the previous chapter, Rc was introduced and references and pointers were discussed. For the same reason, the pointer Rc is also used to encapsulate Table this time. In addition, RefCell needs to be introduced here to provide internal mutability. In summary, the table type is defined as follows:

pub enum Value {
     Table(Rc<RefCell<Table>>),

The definition of the hash table part in Table is HashMap<Value, Value>, that is, the type of index and value are Value both. The index type of HashMap is required to implement the two traits Eq and Hash. This is also easy to understand. The working principle of the hash table is to quickly locate by calculating the hash value (Hash) of the index when inserting and searching, and to handle hash conflicts by comparing the index (Eq). Next, implement these two traits.

Eq trait

We have implemented the PartialEq trait for Value before, which compares whether two Values are equal, or we can use the == operator on the Value type. The requirement of Eq is higher, which requires reflexivity on the basis of PartialEq, that is, it is required to satisfy x==x for any value x of this type. In most cases, it is reflexive, but there are also counterexamples. For example, in floating-point numbers, Nan != Nan, so although the floating-point type implements PartialEq, it does not implement Eq. Although our Value type includes floating-point numbers, since the Lua language prohibits the use of Nan as an index (specifically, we will judge whether the index is Nan when the virtual machine performs a table insertion operation), it can be considered that Value type satisfies reflexivity. For types that satisfy reflexivity, we just tell Rust that it does, no special implementation is required:

impl Eq for Value {}

Hash trait

Most of the basic types in Rust have already implemented the Hash trait, and we only need to call .hash() for each type according to the semantics.

The code to implement the Hash trait is as follows:

impl Hash for Value {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            Value::Nil => (),
            Value::Boolean(b) => b.hash(state),
            Value::Integer(i) => i.hash(state),
            Value::Float(f) => // TODO try to convert to integer
                unsafe {
                    mem::transmute::<f64, i64>(*f).hash(state)
                }
            Value::ShortStr(len, buf) => buf[..*len as usize].hash(state),
            Value::MidStr(s) => s.1[..s.0 as usize].hash(state),
            Value::LongStr(s) => s.hash(state),
            Value::Table(t) => Rc::as_ptr(t).hash(state),
            Value::Function(f) => (*f as *const usize).hash(state),
        }
    }
}

Many types, such as bool, Rc pointers, etc., have already implemented the hash method, but the floating-point type f64 does not. The reason is also because of Nan. Here is a detailed [discussion](https: //internals.rust-lang.org/t/f32-f64-should-implement-hash/5436/2). It has been stated in the Eq trait section that Lua prohibits the use of Nan as an index, we can ignore Nan and the default floating-point type can be hashed. One way is to treat the floating-point number as a piece of memory for hashing. Here we choose to convert to the simpler integer i64 for hashing.

This conversion uses the mem::transmute() function of the standard library, and this function is unsafe. We can clearly know that this conversion is safe (really?), so we can use this unsafe with confidence.

When I first learned the Rust language, I saw that the description of some libraries clearly stated that "unsafe code is not included", and I felt that this is a very proud feature. So when I started this project, I also hoped not to have any unsafe code. But now it seems that unsafe is not a scourge. It may be similar to goto in C language. As long as it is used reasonably, it can bring great convenience.

For the string type, the hash needs to be calculated for the string content. For the table type, only the hash of the pointer needs to be calculated, and the contents of the table are ignored. This is because string comparisons are content comparisons, and table comparisons are comparisons of table references.

Debug and Display traits

Because Rust's matches are exhaustive, so the compiler will remind us to add the Table type in the Debug trait:

     Value::Table(t) => {
         let t = t.borrow();
         write!(f, "table:{}:{}", t.array.len(), t.map.len())
     }

There are 2 lines in the code block. Line 1 uses borrow(), which is a dynamic reference to RefCell type, to ensure that there are no other variable references. This dynamic reference introduces additional runtime overhead relative to most compile-time checks in Rust.

In the official implementation of Lua, the output format of the table type is the address of the table, which can be used for simple debugging. We have increased the length of the array and hash table parts of the table here, which is more convenient for debugging. In addition, we implement the Display trait for Value, which is used for the official output of print:

impl fmt::Display for Value {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         match self {
             Value::Table(t) => write!(f, "table: {:?}", Rc::as_ptr(t)),