Representing the ActionScript 3 semantics in Rust

[hydroper]

A verifier, or symbol solver, which reports verify errors and warnings, attaches meaning (symbols) to syntactic nodes, and builds control flow graphs for activations, consists of a semantic module defining the available symbols.

In usual compiler infrastructures, the miscellaneous symbols (packages, namespaces, types, slots, and value variations) are unified into a single type that delegates high-level accesses to specific symbol variant structures.

That single type, usually called Symbol, may be represented as simply a class or interface in Java, .NET, or ActionScript 3.

In Rust, there's no equivalent class to these high-level languages, so you might have thought of depending on the alpha-phase gc crate from crates.io, which provides Rust with a limited form of garbage collection, so that you could represent the Symbol type. But actually, with gc you won't be able to use the as3_parser crate since it uses reference counting (Rc) within nodes instead.

The Arena

The best solution I found is to use an arena container that uses reference counting and define Symbol as a structure consisting of a Weak reference pointing back to memory in that arena.

This guide allows for circular references without memory leak, since Symbol holds a weak reference rather than a strong reference, and upgrades it to a strong reference upon access methods, such as is_variable_slot(), prototype(), et cetera.

An arena is a container consisting of a possibly large collection of reference counted objects that get deallocated upon the arena's deallocation, that is, usually when a compiler terminates.

Here is how you would define Arena in Rust:

use std::{cell::RefCell, rc::{Rc, Weak}};

// Vec = heap allocated list
// RefCell = mutable memory location for heap allocated resources
// Rc = reference counted object
pub struct Arena<T> {
    data: RefCell<Vec<Rc<T>>>,
}

impl<T> Arena<T> {
    pub fn new() -> Self {
        Self {
            data: RefCell::new(vec![]),
        }
    }

    pub fn allocate(&self, value: T) -> Weak<T> {
        let obj = Rc::new(value);
        self.data.borrow_mut().push(obj.clone());
        Rc::downgrade(&obj)
    }
}

You can then allocate multiple resources, receiving a weak reference that is always set as long as you hold the arena somewhere.

You would usually use that arena in a symbol factory.

The Symbol type

The Symbol type can be defined as a tuple structure consisting of solely a weak reference to memory in your arena.

use std::rc::{Rc, Weak};
use std::hash::Hash;
use std::ops::Deref;

/// An union data type that represents one of several symbols of the
/// ActionScript 3 language, such as classes, variable slots, virtual slots, methods, and values.
#[derive(Clone)]
pub struct Symbol(Weak<Symbol1>);

You may make the tuple's Weak element public by inserting pub or pub(crate) before it (visible within the entire crate).

Deriving the Clone trait for Symbol will make it such that writing symbol.clone() clones the symbol reference (not its actual contents).

You can also implement equality comparison between two Symbol references, as well as hashing for use in containers such as HashMap:

impl Eq for Symbol {}

// self.0 = Weak<Symbol1>

impl PartialEq for Symbol {
    fn eq(&self, other: &Self) -> bool {
        self.0.ptr_eq(&other.0)
    }
}

impl Hash for Symbol {
    /// Performs hashing of the symbol by reference.
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.0.as_ptr().hash(state)
    }
}

In the Symbol structure, you can define Symbol1 as an enumeration describing the various possibilities of what is the actual symbol:

enum Symbol1 {
    Unresolved,
    VariableSlot(Rc<VariableSlot1>),
    MethodSlot(Rc<MethodSlot1>),
}

You can now define methods like is_variable_slot() at the Symbol structure to facilitate checking whether a symbol is a variable slot:

impl Symbol {
    // self.0 = Weak<Symbol1>
    // upgrade() = upgrades from "Weak" to "Rc"
    // unwrap() = makes sure the base is not None and returns its inner value
    // as_ref() = allow pattern matching in Rc's inner value
    // matches!() = a macro for testing a Rust matching pattern at a Rust value
    pub fn is_variable_slot(&self) -> bool {
        matches!(self.0.upgrade().unwrap().as_ref(), Symbol1::VariableSlot(_))
    }
}

The only thing you saw verbose so far is the fact that you have to usually write self.0.upgrade().unwrap().as_ref() within all your Symbol methods. If you find that verbose, you may define a declarative macro:

macro_rules! access_symbol {
    ($symbol:expr) => { $symbol.0.upgrade().unwrap().as_ref() };
}

You can then simplify the above is_variable_slot() definition:

impl Symbol {
    pub fn is_variable_slot(&self) -> bool {
        matches!(access_symbol!(self), Symbol1::VariableSlot(_))
    }
}

For better documenting and using the miscellaneous symbols, you may define structures for each, delegating accesses to Symbol:

/// A variable slot.
/// 
/// # Supported methods
/// 
/// * `is_variable_slot()` — Returns `true`.
#[derive(Clone, Hash, PartialEq, Eq)]
pub struct VariableSlot(pub Symbol);

// Deref = delegates to "Symbol"
impl Deref for VariableSlot {
    type Target = Symbol;
    fn deref(&self) -> &Self::Target {
        assert!(self.0.is_variable_slot());
        &self.0
    }
}

Extra tips:

impl ToString for Symbol {
    fn to_string(&self) -> String {
        match access_symbol!(self) {
            Symbol1::VariableSlot(_) => "a variable".into(),
            _ => "anything else".into(),
        }
    }
}

Full example: Rust playground

Tree semantics

In a verifier, you will want to attach symbol references to nodes. Do so using the TreeSemantics structure:

use as3_parser::ns::*;

// Construct a TreeSemantics structure, where ExampleMeaning
// is any type that implements Clone.
let semantics = TreeSemantics::<ExampleMeaning>::new();

// Retrieve the meaning of a node.
let meaning = semantics.get(&node);

// Assign meaning to a node.
semantics.set(&node, meaning);

// Delete the meaning of a node.
semantics.delete(&node);

// Check whether a node has a meaning.
let has_meaning = semantics.has(&node);

It is essentially just a way to attach meaning to nodes.

Compiler Host

It would make sense to hold the arena (the factory) and several possibly deferred references to the global objects such as RegExp, inside a container that may be called CompilerHost. When you try to lookup a global object and you find out that it is still undefined, you defer verification by returning an Unresolved symbol.

Shared Containers

The Vec and HashMap types as they are may not be useful at all within the Symbol internal structures, so you may use these two helper types: SharedArray and SharedMap.

Shared containers

Put this at the top of your crate's main file:

#![feature(decl_macro)]

SharedArray and shared_array! [ ... ] macro

use std::cell::RefCell;
use std::hash::Hash;
use std::rc::Rc;

/// A shared mutable array of `T` managed by reference counting.
///
/// # Cloning
/// 
/// The `Clone` trait implements cloning of the array by reference.
/// Use the `clone_content()` method to clone the array by content.
/// 
/// # Equality
/// 
/// The `PartialEq` trait performs reference comparison of two arrays.
/// 
/// # Hashing
/// 
/// The `Hash` trait performs hashing of the array by reference.
#[derive(Clone)]
pub struct SharedArray<T>(Rc<RefCell<Vec<T>>>);

impl<T> PartialEq for SharedArray<T> {
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}

impl<T> Eq for SharedArray<T> {}

impl<T> Hash for SharedArray<T> {
    /// Performs hashing of the array by reference.
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.0.as_ptr().hash(state)
    }
}

impl<T> SharedArray<T> {
    pub fn new() -> Self {
        Self(Rc::new(RefCell::new(vec![])))
    }

    pub fn get(&self, index: usize) -> Option<T> where T: Clone {
        self.0.borrow().get(index).map(|v| v.clone())
    }

    pub fn set(&mut self, index: usize, value: T) where T: Clone {
        self.0.borrow_mut()[index] = value.clone();
    }

    pub fn remove(&mut self, index: usize) {
        self.0.borrow_mut().remove(index);
    }

    pub fn includes(&self, value: &T) -> bool where T: PartialEq {
        self.0.borrow().contains(value)
    }

    pub fn index_of(&self, value: &T) -> Option<usize> where T: PartialEq {
        let this = self.0.borrow();
        for i in 0..self.length() {
            let value_2 = this.get(i).unwrap();
            if value == value_2 {
                return Some(i);
            }
        }
        None
    }

    pub fn length(&self) -> usize {
        self.0.borrow().len()
    }

    pub fn push(&mut self, value: T) {
        self.0.borrow_mut().push(value);
    }

    pub fn iter(&self) -> SharedArrayIterator<T> where T: Clone {
        SharedArrayIterator {
            array: &self,
            index: 0,
        }
    }

    pub fn clone_content(&self) -> Self where T: Clone {
        let mut r = Self::new();
        for v in self.iter() {
            r.push(v);
        }
        r
    }
}

pub struct SharedArrayIterator<'a, T> {
    array: &'a SharedArray<T>,
    index: usize,
}

impl<'a, T> Iterator for SharedArrayIterator<'a, T> where T: Clone {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        let v = self.array.get(self.index);
        if v.is_some() {
            self.index += 1;
            v
        } else {
            None
        }
    }
}

impl<const N: usize, T> From<[T; N]> for SharedArray<T> where T: Clone {
    fn from(value: [T; N]) -> Self {
        Self::from_iter(value)
    }
}

impl<T> From<Vec<T>> for SharedArray<T> where T: Clone {
    fn from(value: Vec<T>) -> Self {
        Self::from_iter(value)
    }
}

impl<T> FromIterator<T> for SharedArray<T> where T: Clone {
    fn from_iter<T2: IntoIterator<Item = T>>(iter: T2) -> Self {
        let mut r = Self::new();
        for v in iter {
            r.push(v.clone());
        }
        r
    }
}

impl<A> Extend<A> for SharedArray<A> {
    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
        for v in iter.into_iter() {
            self.push(v);
        }
    }
}

pub macro shared_array {
    ($($element:expr),*) => {
        SharedArray::from([$($element),*])
    },
    ($($element:expr),+ ,) => {
        SharedArray::from([$($element),+])
    },
}

SharedMap and shared_map! { ... } macro

use std::cell::RefCell;
use std::collections::HashMap;
use std::hash::Hash;
use std::rc::Rc;

/// A shared mutable hash map managed by reference counting.
/// 
/// # Cloning
/// 
/// The `Clone` trait implements cloning of the map by reference.
/// Use the `clone_content()` method to clone the map by content.
/// 
/// # Equality
/// 
/// The `PartialEq` trait performs reference comparison of two maps.
///
/// # Hashing
/// 
/// The `Hash` trait performs hashing of the map by reference.
///
/// # Iteration
/// 
/// To iterate a `SharedMap`, it is required to invoke the `borrow()` method,
/// as in the following snippet:
/// 
/// ```ignore
/// map_object.borrow().iter(|(k, v)| {
///     // k: &K
///     // v: &V
/// });
/// ```
#[derive(Clone)]
pub struct SharedMap<K, V>(Rc<RefCell<HashMap<K, V>>>);

impl<K, V> PartialEq for SharedMap<K, V> {
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}

impl<K, V> Eq for SharedMap<K, V> {}

impl<K, V> Hash for SharedMap<K, V> {
    /// Performs hashing of the map by reference.
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.0.as_ptr().hash(state)
    }
}

impl<K, V> SharedMap<K, V> {
    pub fn new() -> Self {
        Self(Rc::new(RefCell::new(HashMap::new())))
    }

    pub fn get(&self, key: &K) -> Option<V> where K: Eq + Hash, V: Clone {
        self.0.borrow().get(key).map(|v| v.clone())
    }

    pub fn set(&mut self, key: K, value: V) where K: Eq + Hash {
        self.0.borrow_mut().insert(key, value);
    }

    pub fn remove(&mut self, key: &K) -> Option<V> where K: Eq + Hash {
        self.0.borrow_mut().remove(key)
    }

    pub fn has(&self, key: &K) -> bool where K: Eq + Hash {
        self.0.borrow().contains_key(key)
    }

    pub fn length(&self) -> usize {
        self.0.borrow().len()
    }

    pub fn clone_content(&self) -> Self where K: Clone + Eq + Hash, V: Clone {
        let mut r = Self::new();
        for (k, v) in self.borrow().iter() {
            r.set(k.clone(), v.clone());
        }
        r
    }

    pub fn borrow(&self) -> std::cell::Ref<HashMap<K, V>> {
        self.0.borrow()
    }
}

impl<const N: usize, K: Eq + Hash, V> From<[(K, V); N]> for SharedMap<K, V> {
    fn from(value: [(K, V); N]) -> Self {
        Self::from_iter(value)
    }
}

impl<K: Eq + Hash, V> From<Vec<(K, V)>> for SharedMap<K, V> {
    fn from(value: Vec<(K, V)>) -> Self {
        Self::from_iter(value)
    }
}

impl<K: Eq + Hash, V> From<HashMap<K, V>> for SharedMap<K, V> {
    fn from(value: HashMap<K, V>) -> Self {
        Self::from_iter(value)
    }
}

impl<K: Eq + Hash, V> FromIterator<(K, V)> for SharedMap<K, V> {
    fn from_iter<T2: IntoIterator<Item = (K, V)>>(iter: T2) -> Self {
        let mut r = Self::new();
        for (k, v) in iter {
            r.set(k, v);
        }
        r
    }
}

impl<'a, K: Eq + Hash + Clone, V: Clone> FromIterator<(&'a K, &'a V)> for SharedMap<K, V> {
    fn from_iter<T2: IntoIterator<Item = (&'a K, &'a V)>>(iter: T2) -> Self {
        let mut r = Self::new();
        for (k, v) in iter {
            r.set(k.clone(), v.clone());
        }
        r
    }
}

impl<K, V> Extend<(K, V)> for SharedMap<K, V> where K: Eq + Hash {
    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
        for (k, v) in iter.into_iter() {
            self.set(k, v);
        }
    }
}

pub macro shared_map {
    ($($key:expr => $value:expr),*) => {
        SharedMap::from([$(($key, $value)),*])
    },
    ($($key:expr => $value:expr),+ ,) => {
        SharedMap::from([$(($key, $value)),+])
    },
}

Pattern Matching in Rust

The ref and borrow terms are way mixed in Rust, and mut sometimes is related to &mut (muttable borrows). Borrow types (&T) are transitively immutable reference types, while mutable borrow types (&mut T) are transitively mutable reference types.

Specially, within pattern matching in Rust you may use a ref prefix sometimes to destructure a value by borrowing it rather than copying it (escaping out of compile-time errors).

Throwing errors

Examples:

fn f1(symbol: &Symbol) -> Result<(), DeferVerificationError> {
    if symbol.is_unresolved() {
        Err(DeferVerificationError)
    } else {
        Ok(())
    }
}

// The postfix ? operator (error propagation)
// propagates (throws) the DeferVerificationError thrown by f1
fn f2(symbol: &Symbol) -> Result<(), DeferVerificationError> {
    f1(symbol)?;
    Ok(())
}

struct DeferVerificationError;

Borrows and Lifetimes

Borrow types (&T and &mut T) consist of a lifetime, although it's inferred by default. The lifetime is expressed by the 'id token (note the apostrophe), as in &'a T. It's usually named as a lowercase letter, but any lifetime name is available in Rust, such as in &'long_name_lifetime T. The reserved 'static lifetime means the entire program's lifetime.

Lifetimes may be explicitly declared in Rust types and functions, as in:

fn f<'my_lifetime>(a: &'my_lifetime T) {}

It's often not needed as it's done implicitly for functions.

Owned or borrowed

There are a range of types that are owned and others that are borrowed. Examples:

• &str is a slice of an existing string
• String is a string that you "own", which is always heap-allocated
• &String is similiar to &str, but not a slice, but a borrow of a String

Traits

Traits (what you know as "interfaces") are non opaque types in Rust, which means you can't use them like structures at all. Trait objects is where you run type erasure in Rust, which explicitly requires the dyn keyword.

• &dyn YourTrait
• Box<dyn YourTrait>
• Rc<dyn YourTrait>

Conclusion

This is very simplified and I've just shown mostly empty structures, but this may give some pointers as how you can use Rust with as3_parser to build a compiler.

As things are moving ahead with ActionScript 3, I'm feeling afraid of working in a verifier and being backwards in terms of semantics. For example, Apache Royale recently introduced basic type inference for function signatures; I've not tested it, but if it just infers for the result type, then it might not be that much trouble.

It might also be difficult to handle embedding fonts like in the Flex compiler! I'm not really sure how would be the procedure to convert a TTF file to font glyphs in a SWF. There might be many things to take into consideration when handling the Embed meta-data.

[hydroper]

There's a TTF parser for Rust already, so less problems, but glyph mathematics might not be easy for me

Summing up the tough parts might be handling all of MXML together (components, style sheets, data bindings, and the exact same processing of MXML). There are additional things I'm not mentioning about Flex because I'm not familiar, like external AJAX resources.

What I think is that MXML translates to ActionScript 3 syntactic nodes and later are applied Flex specific verifications over these nodes.

[hydroper]

(I've added the TreeSemantics structure and this discussion popped up again.)