Showing posts with label javascript. Show all posts
Showing posts with label javascript. Show all posts

Friday, April 7, 2023

Some considerations for using closures in Rust/WASM

Here are a couple of things I learned while trying to pass a Rust closure to a JavaScript function. Some of these notes are a result of my lack of experience with Rust and Rust/WASM.

Passing a closure that is going to outlive the current function call

Passing a Rust function that exists in the stack to JavaScript is easy for example, here is a call to Array.map:

#[wasm_bindgen]
pub fn square_elements(a : &js_sys::Array) -> js_sys::Array {
    a.map(&mut |value:JsValue, idx: u32, arr: js_sys::Array| {
        let value = value.as_f64().unwrap();
        JsValue::from_f64(value * value)
    })
}

In this case the function used as argument to map exists only for the time of the invocation of the square_elements function. You need to do something extra when passing a closure is going to outlive the current call. This section of the Rust WASM documentation: https://rustwasm.github.io/wasm-bindgen/reference/passing-rust-closures-to-js.html#heap-allocated-closures has details on how to call a JavaScript function that receives a closure that “survives” the current method or function call. A typical example is calling requestAnimationFrame .

It has a very important note that I overlooked at first:

Once a Closure is dropped, it will deallocate its internal memory and invalidate the corresponding JavaScript function so that any further attempts to invoke it raise an exception…https://rustwasm.github.io/wasm-bindgen/reference/passing-rust-closures-to-js.html#heap-allocated-closures

One thing that I want to do in Rust with WASM is to write a “requestAnimationFrame loop” which allows me to write code that performs a repetitive task without blocking the UI thread of the browser. Here is an example of how this looks in JavaScript

// JavaScript
let i = 0;
let action = () => {
   if (i < 3) {
      console.log(`Calling with ${i}`);
      // do something interesting...
      requestAnimationFrame(action);
   }
   i++;
};
requestAnimationFrame(action);

I found a nice example on how to do this loop in Rust here: https://rustwasm.github.io/docs/wasm-bindgen/examples/request-animation-frame.html . The example has a lot of documentation that explains its functionality in the comments. The code looks a little bit intimidating for a Rust newbie (like me). Here is a small reduced code with the most important parts of the example:

let f = Rc::new(RefCell::new(None));
let g = f.clone();

let mut i = 0;
*g.borrow_mut() = Some(Closure::wrap(Box::new(move || {
   if i > 300 {
       ...
       let _ = f.borrow_mut().take(); 
       return;
   }

   i += 1;
   ...
   request_animation_frame(f.borrow().as_ref().unwrap());
}))
...
request_animation_frame(g.borrow().as_ref().unwrap());

As described in the source of the example, this code uses Rc and RefCell to keep the Closure instance alive while the sequence of requestAnimationFrame calls do its work. In this case when the i counter reaches 300 the closure will return and finish the loop.

Each part in this code is very important. I did some mistakes that I’m going to detail in the next sections.

The closure is dropped before ‘requestAnimationFrame’ does its job

The goal of the two Rc/RefCell references to the same closure is to keep the Closure alive before finishing the call to the current function. This is an example of the error that is raised when you fail to do that:

// this example is incomplete
pub fn greet() {
    let f = Rc::new(RefCell::new(None));
    let g = f.clone();
    
    let mut i  = 0;
    *g.borrow_mut() = Some(Closure::new(move || {
         log("At the end of the closure");
    }));
    log(&format!("Before quitting 'greet' {}", Rc::strong_count(&g)));
    request_animation_frame(g.borrow().as_ref().unwrap());
}    

Notice that here we don’t pass f into the closure. Hence at the end of the function both g and f are going to be dropped along with the Closure instance. Running this code shows the following errors in the browser console:

...
Before quitting 'greet' 2 wasm_loop_bg.js:259:13
Uncaught Error: closure invoked recursively or after being dropped
...

To fix this issue in the incomplete example I just need to move the f instance to the closure so it will be captured:

// this example is incomplete
pub fn greet() {
    let f = Rc::new(RefCell::new(None));
    let g = f.clone();
    
    let mut i  = 0;
    *g.borrow_mut() = Some(Closure::new(move || {
         let _ = f; /// Now 'f' is moved inside!
         log("At the end of the closure");
    }));
    log(&format!("Before quitting 'greet' {}", Rc::strong_count(&g)));
    request_animation_frame(g.borrow().as_ref().unwrap());
}    

Resources not being released

After writing the complete loop, I also found that I was not doing the complete cleanup for the closure.

Here is an example that shows the problematic code:

#[derive(Debug)]
struct MyStruct {
    x: i32
}

impl Drop for MyStruct {
    fn drop(&mut self) {
        write_debug(format!("Calling `drop` on MyStruct: {}", self.x).as_str());
    }
}

#[wasm_bindgen]
pub fn greet() {
    let f = Rc::new(RefCell::new(None));
    let g = f.clone();
    let captured = MyStruct { x: 100 };

    let mut i  = 0;
    *g.borrow_mut() = Some(Closure::new(move || {
        log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
        if i != 2 {
           request_animation_frame(f.borrow().as_ref().unwrap());
        }
        } else {
            log("Finished");                                                                                                        return;
        }
        i += 1;
    }));

    request_animation_frame(g.borrow().as_ref().unwrap());
    log("Before finishing 'greet'");
}

In this example I created a dummy struct called MyStruct . This structure implements the Drop trait to display a message in the console when the structured is being dropped. An instance of this structure is being captured by the closure passed to the requestAnimationFrame call.

When running this code we see the following messages in the console:

Before finishing 'greet' wasm_loop_bg.js:267:13
Counter: 0 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 1 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 2 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Finished

Notice that we don’t see the message logged in the drop method of MyStruct. The reason for this is that I forgot to release the value inside the Rc/RefCell wrapper.

Here is the corrected code:

...
#[wasm_bindgen]
pub fn greet() {
    let f = Rc::new(RefCell::new(None));
    let g = f.clone();
    let captured = MyStruct { x: 100 };

    let mut i  = 0;
    *g.borrow_mut() = Some(Closure::new(move || {
        log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
        if i != 2 {
           request_animation_frame(f.borrow().as_ref().unwrap());
        } else {
            log("Finished");
            let _ = f.take();
            return;
        }
        i += 1;
    }));

    request_animation_frame(g.borrow().as_ref().unwrap());
    log("Before finishing 'greet'");
}

And now here is the output of the code:

Before finishing 'greet' wasm_loop_bg.js:267:13
Counter: 0 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 1 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 2 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Finished wasm_loop_bg.js:267:13
Calling `drop` on MyStruct: 100

As with the original example the take method is used to move the Closure out of the Rc/RefCell reference. The value will be dropped at the end of the call.

Not following the requirement of using FnMut for the closure

This is another case of not following the rules and not taking the time to read the error message. I did a small change to the code as follows:

fn my_dummy_function_requiring_move(ms: MyStruct) {
   log(format!("-- {:?}", &ms).as_str());
}
...

#[wasm_bindgen]
pub fn greet() {
    let f = Rc::new(RefCell::new(None));
    let g = f.clone();
    let captured = MyStruct { x: 100 };

    let mut i  = 0;
    *g.borrow_mut() = Some(Closure::new(move || {
        my_dummy_function_requiring_move(captured);
        log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
        if i != 2 {
           request_animation_frame(f.borrow().as_ref().unwrap());
        } else {
            log("Finished");
            let _ = f.take();
            return;
        }
        i += 1;
    }));

    request_animation_frame(g.borrow().as_ref().unwrap());
    log("Before finishing 'greet'");
}

When introducing this code the compiles shows the following error:

error[E0525]: expected a closure that implements the `FnMut` trait, but this closure only implements `FnOnce`
   --> src\lib.rs:74:41
    |
74  |       *g.borrow_mut() = Some(Closure::new(move || {
    |                              ------------ -^^^^^^
    |                              |            |
    |  ____________________________|____________this closure implements `FnOnce`, not `FnMut`
    | |                            |
    | |                            required by a bound introduced by this call
75  | |
76  | |         my_dummy_function_requiring_move(captured);
    | |                                          -------- closure is `FnOnce` because it moves the variable `captured` out of its environment
77  | |         log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
...   |
85  | |         i += 1;
86  | |     }));
    | |_____- the requirement to implement `FnMut` derives from here
    |
    = note: required for `[closure@src\lib.rs:74:41: 74:48]` to implement `IntoWasmClosure<dyn FnMut()>`
note: required by a bound in `wasm_bindgen::prelude::Closure::<T>::new`
   --> C:\Users\ldfallasu2\.cargo\registry\src\github.com-1ecc6299db9ec823\wasm-bindgen-0.2.84\src\closure.rs:271:12
    |
271 |         F: IntoWasmClosure<T> + 'static,
    |            ^^^^^^^^^^^^^^^^^^ required by this bound in `wasm_bindgen::prelude::Closure::<T>::new`

It is really impressive to see how to compiler shows the location of the error and the related areas. As the error message says, the problem here is that we are moving a value out of the closure. This fact prevents the compiler from assuming that our closure implements the FnMut trait (More information here https://doc.rust-lang.org/stable/book/ch13-01-closures.html#moving-captured-values-out-of-closures-and-the-fn-traits ).

The solution in this case is simple, since the move was not really required I created an alternative version of the function that do not require a “move”:

fn my_dummy_function_requiring_ref(ms: &MyStruct) {
   write_debug(format!("-- {:?}", ms).as_str());
}

The call is changed to my_dummy_function_requiring_ref(&s); which removes the compilation error.

The examples created in this post use the following utility functions and declarations:

fn window() -> web_sys::Window {
    web_sys::window().expect("not global 'window'")
}

fn request_animation_frame(f: &Closure<dyn FnMut()>) {
    window()
        .request_animation_frame(f.as_ref().unchecked_ref())
        .expect("Call to request animation frame ");
}

#[wasm_bindgen]
extern {
    #[wasm_bindgen(js_namespace = console)]
    fn log(s: &str);
}

Conclusions

I think there are two main conclusions for this post:

  1. Read the documentation carefully!
  2. Take time to read the compiler errors. The Rust compiler team put a lot of effort explain the error and help you locate the origin of the problem.

Friday, April 15, 2022

Exploring a Webpack stats file with Prolog

A couple of days ago I was reading about the Webpack statistics file created using the following command line options:

npx webpack --profile --json

This file contains a lot of information collected by Webpack about the project being processed. The information in this file is used by nice visualization tools like Webpack Bundle Analyzer.

The dependency graph is included in this file. That is, all the dependencies between modules of the project. Being able to perform queries on this data could be useful to get insights into the code.

There are many tools to process JSON, but I wanted to try to use SWI-Prolog to see if I can get information from this file.

The information I am looking for is the module dependency information. By taking a look at the Module Object we can get this information using the reasons property.

We can start by parsing the stats.json file using SWI-Prolog builtin library for reading JSON:


:- use_module(library(http/json)).

read_json_file(FileName, Terms) :-
    open(FileName, read, Stream),
    json_read(Stream, Terms),
    close(Stream).

For convenience, I'm adding the loaded file to the Prolog database using assert/1:


?- read_json_file('c:\\smallexample\\stats.json',F), assert(testfile(F)).
F = json([hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json(...), ... = ...|...]).

Now that we can load the stats file we can start by performing simple queries. For example we can start by looking at top-level properties:


?- testfile(json(Contents)), member(Name=_,Contents).
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = hash ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = version ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = time ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = builtAt ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = publicPath ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
...

Here notice, that I'm using member/2 to get the name of the properties in the main file.

By the way, as a side note, yesterday I learned that you can exclude variables from Prolog results using the following (Stack overflow question here) goal:


set_prolog_flag(toplevel_print_anon, false).

With this nice tip, we can exclude variables that start with underscore from the results:


?- testfile(json(_Contents)), member(Name=_, _Contents).
Name = hash ;
Name = version ;
Name = time ;
Name = builtAt ;
Name = publicPath ;
Name = outputPath ;
Name = assetsByChunkName ;
Name = assets ;
Name = chunks ;
Name = modules ;
Name = entrypoints ;
Name = namedChunkGroups ;
Name = errors ;
Name = errorsCount ;
Name = warnings ;
Name = warningsCount ;
Name = children.

Now I can access the modules section to extract the reasons property. This property has information on modules that depend on the current module. For example say that we have a small TypeScript program that have the following structure:

 



We can start the exploration of this project by looking at the contents of the modules objects.


?- testfile(json(_Contents)),
|    member( ('modules'=_Modules), _Contents),
|    member( json(_ModulePropsList), _Modules),
|    member( ('name'=ModuleName), _ModulePropsList).
ModuleName = './src/index.ts' ;
ModuleName = './src/parser.ts' ;
ModuleName = './src/FuncApply.ts' ;
ModuleName = './src/NumLiteral.ts' ;
ModuleName = './src/SymbolObj.ts' ;
ModuleName = './src/BaseObject.ts' ;
ModuleName = 'webpack/runtime/define property getters' ;
ModuleName = 'webpack/runtime/hasOwnProperty shorthand' ;
ModuleName = 'webpack/runtime/make namespace object' ;

We can create a new goal with the code above which we can use later:


module_name(json(ContentsList), Name) :-
    member(('modules'=Modules), ContentsList),
    member(json(ModulePropertiesList), Modules),
    member('name'=Name, ModulePropertiesList).


module_properties_by_name(json(ContentsList), Name, ModulePropertiesList) :-
    member(('modules'=Modules), ContentsList),
    member(json(ModulePropertiesList), Modules),
    member('name'=Name, ModulePropertiesList).

Now that we located the modules, we can get the contents of the reasons property.


?- testfile(_Json),
|    module_properties_by_name(_Json, './src/BaseObject.ts', _Props),
|    member((reasons=_Reasons), _Props),
|    member(json([_|[RefModName|_]]), _Reasons).
RefModName =  (module='./src/FuncApply.ts') ;
RefModName =  (module='./src/FuncApply.ts') ;
RefModName =  (module='./src/NumLiteral.ts') ;
RefModName =  (module='./src/NumLiteral.ts') ;
RefModName =  (module='./src/SymbolObj.ts') ;
RefModName =  (module='./src/SymbolObj.ts') ;
false.

(Repeated results seem to indicate different "reasons")

With this data we can generate Graphviz representation (for example the one used in the graph above).


name_modules([], [], _).
name_modules([ModName|Rest], [ModNamePair|RestResult], Counter) :-
    number_string(Counter, CounterStr),
    string_concat('M', CounterStr, ModuleId),
    ModNamePair = ModName - ModuleId,
    NewCounter is Counter + 1,
    name_modules(Rest, RestResult, NewCounter).

module_dependencies_by_reason(File, (Name-Referencer)) :-
    module_name(File, Name),
    module_properties_by_name(File, Name,Props),
    member((reasons=R), Props),
    member(json([_|[(module=Referencer)|_]]),R).

generate_node_descriptions([],Result, Result).
generate_node_descriptions([(Name-Id)|Rest],TmpResult, OutStr) :-
    format(atom(Tmp3), '~a[label="~a"];\n', [Id, Name]),
    string_concat(TmpResult, Tmp3, OutStrTmp),
    generate_node_descriptions(Rest, OutStrTmp, OutStr).

generate_node_relations([], _, Result, Result).
generate_node_relations([(Target-Src)|Rest], NodeIds, TmpResult, Result) :-
    get_assoc(Src, NodeIds , SrcCode),
    get_assoc(Target, NodeIds , TargetCode),
    format(atom(RelationStr), '~a -> ~a;\n', [SrcCode, TargetCode]),
    string_concat(TmpResult, RelationStr, NewTmpResult),
    generate_node_relations(Rest, NodeIds, NewTmpResult, Result), !.
generate_node_relations([_|Rest], NodeIds, TmpResult, Result) :-
    generate_node_relations(Rest, NodeIds, TmpResult, Result),!.


dot_file_from_reasons(File, DotFileStr) :-
    findall(Name, module_name(File, Name), NameList),
    name_modules(NameList, CodedList, 0),
    list_to_assoc(CodedList, AssocNameModList),!,
    setof(Pairs, module_dependencies_by_reason(File, Pairs), PairList),
    generate_node_descriptions(CodedList, 'digraph G {\n', DotFileStrTmp1),
    generate_node_relations(PairList, AssocNameModList, DotFileStrTmp1, DotFileStrTmp2),
    string_concat(DotFileStrTmp2, '}', DotFileStr).

I am impressed by the power of Prolog. I have always admired the way it works differently dependending on how you use it. For example the way member/2 was used above to extract internal elements from terms. One would assume that this predicate is only used to test list membership. However by the power of Prolog unification and backtracking we can used to explore the contents of a list.

Monday, November 23, 2009

Adding automatic semicolon insertion to a Javascript parser

A couple of weeks ago I wrote a blog post about a Javascript parser written using the Newspeak parsing combinators. As mentioned in that post, no semicolon insertion was supported. This post shows how the feature was added.

Automatic semicolon insertion



As detailed in section 7.9 of the ECMA 262 document[PDF], in Javascript you can use newline as statement separator in some scenarios. For example a semicolon is "implicitly inserted" if expression-statements are separated by line terminators:


if (condition) {
print("A")
print("B")
}


This code snippet is equivalent to:



if (condition) {
print("A");
print("B");
}


Solution



In the a original post about the parser, espin pointed me out to a paper[PDF] by A. Warth that mentions how the semicolon insertion problem was solved in a Javascript parser written in OMeta. The solution presented is this post is based on the one from the paper.


I wanted to isolate the code that performs this function. So in order to add this functionality I created a subclass that overrides the productions that get involved in this process. This way we can have both a parser with and without the feature. Here's the code:


class JSGrammarWithSemicolonInsertion = JSGrammar (
"Parser features that add automatic semicolon insertion"
|

specialStatementTermination = ((( cr | lf ) not & whitespace ) star,
(semicolon | comment | lf | cr | (peek: $})) )
wrapper: [ :ws :terminator | | t | t:: Token new. t token: $;. t].

returnStatement = return, (specialStatementTermination |
(expression , specialStatementTermination)).

breakStatement = break, (specialStatementTermination |
(identifier , specialStatementTermination)).

continueStatement = continue, (specialStatementTermination |
(identifier , specialStatementTermination)).

whitespaceNoEOL = (( cr | lf ) not & whitespace ) star,
(((peek: (Character cr)) | (peek: (Character lf))) not) .

throwStatement = throw, whitespaceNoEOL , expression , specialStatementTermination.

expressionStatement = (((function | leftbrace) not) & expression), specialStatementTermination.

variableStatement = var, variableDeclarationList, specialStatementTermination.
|
)


The result of parsing the following code:


var x = 0
while (true) {
x++
document.write(x)
if ( x > 10)
break
else continue
}


... is presented using the utility created for the previous post:



Code for this post is available here.

Thursday, October 1, 2009

Parsing Javascript using Newspeak parsing combinators

I've been working on a parser for Javascript/Ecmascript using Newspeak parsing combinators. The parser is based on the grammar presented in the ECMAScript Language Specification [PDF] document. It is still incomplete, however it can parse simple statements.

The grammar looks like this:


class JSGrammar = ExecutableGrammar (
"Experiment for JS grammar based on the description from http://www.ecma-international.org/publications/standards/Ecma-262.htm"
|
doubleQuote = (char: $").
backslash = (char: $\).
str = doubleQuote,((backslash, ( char: $" )) |
(backslash, ( char: $/ )) |
(backslash, backslash) |
(backslash, ( char: $r )) |
(backslash, ( char: $n )) |
(backslash, ( char: $t )) |
(charExceptFor: $")) star, doubleQuote.
string = tokenFor: str.

tilde = char: $~.
exclamation = char: $!.
starChar = char: $*.
slash = char: $/.
modulo = char: $%.
pipe = char: $|.
amp = char: $&.
cir = char: $^.
question = char: $?.
colon = char: $:.
semicolon = char: $;.

negSign = (char: $-).
plusSign = (char: $+).
digit = (charBetween: $0 and: $9).
dot = (char: $. ) .
lt = char: $&lt;.
gt = char: $&gt;.
eq = char: $=.
num = negSign opt, digit, digit star, dot opt,digit star, ((char: $e) | (char: $E)) opt, (plusSign | negSign) opt,digit star.
number = tokenFor: num.

tQuestion = tokenFor: question.
tColon = tokenFor: colon.
tplusSign = tokenFor: plusSign.
tnegSign = tokenFor: negSign.
tmodulo = tokenFor: modulo.
tslash = tokenFor: slash.
tstarChar = tokenFor: starChar.
texclamation = tokenFor:exclamation.
tdot = tokenFor:dot.
tLt = tokenFor: lt.
tGt = tokenFor: gt.
tEq = tokenFor: eq.
tAmp = tokenFor: amp.
tPipe = tokenFor: pipe.
tCir = tokenFor: cir.
tSlash = tokenFor: slash.
tSemicolon = tokenFor: semicolon.

tStarEq = tstarChar,eq.
tModEq = tmodulo,eq.
tSlashEq = tSlash,eq.
tPlusEq = tplusSign,eq.
tMinusEq = tnegSign,eq.
tAmpAmp = tAmp,amp.
tPipePipe = tPipe,pipe.
tLtEq = tLt,eq.
tGtEq = tGt,eq.
tleftShift = tLt,lt.
trightShift = tGt,gt.
tsRightShift = tGt,gt,gt.
tEqEq = tEq,eq.
tEqEqEq = tEq,eq,eq.
tNotEq = texclamation,eq.
tNotEqEq = texclamation,eq,eq.
tleftShiftEq = tleftShift,eq.
trightShiftEq = trightShift,eq.
tsRightShiftEq = tsRightShift,eq.
tAmpEq = tAmp,eq.
tPipeEq = tPipe,eq.
tCirEq = tCir,eq.

lineTerminator = (char: (Character lf)) | (char: (Character cr)).

regularExpressionLiteral =
tslash,
( ((backslash, ( charExceptForCharIn: { (Character lf). (Character cr). })) |
(charExceptForCharIn: { (Character lf). (Character cr). $/.})) plus),
slash, (identifierStart star).

leftparen = tokenFromChar: $(.
rightparen =tokenFromChar: $).

leftbrace = tokenFromChar: ${.
rightbrace =tokenFromChar: $}.
comma = tokenFromChar: $,.
propertyName = string | identifier | number.
propertyNameAndValue = propertyName,tColon,value.
obj = leftbrace, (propertyNameAndValue starSeparatedBy: comma),rightbrace.
object = obj.

leftbracket = tokenFromChar: $[.
rightbracket = tokenFromChar: $].
arr = leftbracket, (value starSeparatedBy: comma), rightbracket.
array = tokenFor: arr.

comment = (slash,starChar,blockCommentBody,starChar,slash) | (slash,slash, lineCommentBody).


ttrue = tokenFromSymbol: #true.
tfalse = tokenFromSymbol: #false.
null = tokenFromSymbol: #null.
function = tokenFromSymbol: #function.
tnew = tokenFromSymbol: #new.
break = tokenFromSymbol: #break.
case = tokenFromSymbol: #case.
catch = tokenFromSymbol: #catch.
continue = tokenFromSymbol: #continue.
default = tokenFromSymbol: #default.
delete = tokenFromSymbol: #delete.
do = tokenFromSymbol: #do.
else = tokenFromSymbol: #else.
finally = tokenFromSymbol: #finally.
for = tokenFromSymbol: #for.
if = tokenFromSymbol: #if.
in = tokenFromSymbol: #in.
instanceof = tokenFromSymbol: #instanceof.
return = tokenFromSymbol: #return.
switch = tokenFromSymbol: #switch.
this = tokenFromSymbol: #this.
throw = tokenFromSymbol: #throw.
try = tokenFromSymbol: #try.
typeof = tokenFromSymbol: #typeof.
var = tokenFromSymbol: #var.
void = tokenFromSymbol: #void.
while = tokenFromSymbol: #while.
with = tokenFromSymbol: #with.



letter = (charBetween: $a and: $z) | (charBetween: $A and: $Z).
identifierStart = letter | (char: $$) | (char: $_).
identifier = accept: (tokenFor: (identifierStart), (identifierStart | digit) star) ifNotIn: keywords .

value = assignmentExpression .

literal = null | ttrue | tfalse | number | string | regularExpressionLiteral.

primaryexpression = this | literal | identifier | array | object | parenthesized.

parenthesized = leftparen,expression,rightparen.

functionexpression = function , identifier opt,
leftparen,formalParameterList , rightparen ,
leftbrace,sourceElements,rightbrace.
formalParameterList = identifier starSeparatedBy: comma.

memberexpression = (simplememberexpression ),
(( leftbracket, expression, rightbracket) | ( tdot, identifier)) star.

simplememberexpression = primaryexpression |
functionexpression |
simpleNewExpression.
simpleNewExpression = tnew,memberexpression, arguments.



callExpression = (simplememberexpression ),
( arguments |
( leftbracket, expression, rightbracket) |
( tdot, identifier) ) star.
simpleCallExpression = memberexpression , arguments.
arguments = leftparen ,
(assignmentExpression, (comma, assignmentExpression) star) opt,
rightparen.

newExpression = memberexpression | simpleNewMemberExpression.
simpleNewMemberExpression = tnew, memberexpression.

plusPlus = plusSign,plusSign.
minusMinus = negSign,negSign.

leftHandSideExpression = callExpression | newExpression .
postfixExpression = leftHandSideExpression ,
((plusPlus | minusMinus) star).


unaryExpression = postfixExpression | complexUnaryExpression.

complexUnaryExpression =
(typeof, unaryExpression) |
(delete, unaryExpression) |
(void, unaryExpression) |
(plusPlus, unaryExpression) |
(minusMinus, unaryExpression) |
((tokenFor: ( plusSign | negSign | tilde | exclamation )), unaryExpression).

multiplicativeExpression =
unaryExpression, ((tstarChar | tslash | tmodulo), unaryExpression) star.

additiveExpression =
multiplicativeExpression, ((tplusSign | tnegSign), multiplicativeExpression) star.

shiftExpression =
additiveExpression, ((tsRightShift | tleftShift | trightShift), additiveExpression) star.

relationalExpression =
shiftExpression, (( tLtEq | tGtEq | tLt | tGt | instanceof | in) , shiftExpression) star.

relationalExpressionNoIn =
shiftExpression, (( tLtEq | tGtEq | tLt | tGt | instanceof ) , shiftExpression) star.

equalityExpression =
relationalExpression, ((tEqEqEq | tEqEq | tNotEqEq | tNotEq ), relationalExpression) star.

equalityExpressionNoIn =
relationalExpressionNoIn, ((tEqEqEq | tEqEq | tNotEqEq | tNotEq ), relationalExpressionNoIn) star.

bitwiseANDExpression =
equalityExpression,(tAmp, equalityExpression) star.

bitwiseANDExpressionNoIn =
equalityExpressionNoIn,(tAmp, equalityExpressionNoIn) star.

bitwiseXORExpression =
bitwiseANDExpression,(tCir, bitwiseANDExpression) star.

bitwiseXORExpressionNoIn =
bitwiseANDExpressionNoIn,(tCir, bitwiseANDExpressionNoIn) star.

bitwiseORExpression =
bitwiseXORExpression,(tPipe, bitwiseXORExpression) star.

bitwiseORExpressionNoIn =
bitwiseXORExpressionNoIn,(tPipe, bitwiseXORExpressionNoIn) star.

logicalAndExpression =
bitwiseORExpression, (tAmpAmp,bitwiseORExpression) star.

logicalAndExpressionNoIn =
bitwiseORExpressionNoIn, (tAmpAmp,bitwiseORExpressionNoIn) star.

logicalOrExpression =
logicalAndExpression, (tPipePipe,logicalAndExpression) star.

logicalOrExpressionNoIn =
logicalAndExpressionNoIn, (tPipePipe,logicalAndExpressionNoIn) star.

assignmentOperator =
tEq | tStarEq | tSlashEq | tModEq | tPlusEq | tMinusEq |
tleftShiftEq | tsRightShiftEq | trightShiftEq | tAmpEq | tPipeEq |
tCirEq.

conditionalExpression =
logicalOrExpression, (tQuestion, assignmentExpression,tColon,assignmentExpression) opt.

assignmentExpression =
conditionalExpression, (assignmentOperator,conditionalExpression) star.

conditionalExpressionNoIn =
logicalOrExpressionNoIn, (tQuestion, assignmentExpressionNoIn,tColon,assignmentExpressionNoIn) opt.

assignmentExpressionNoIn =
conditionalExpressionNoIn, (assignmentOperator,conditionalExpressionNoIn) star.

expression = assignmentExpression, (comma , assignmentExpression) star.

expressionNoIn = assignmentExpressionNoIn, (comma , assignmentExpressionNoIn) star.


statement = block | variableStatement | emptyStatement | expressionStatement |
ifStatement | iterationStatement | withStatement | switchStatement |
labelledStatement | tryStatement | throwStatement |
breakStatement | returnStatement.

block = leftbrace, statementList , rightbrace.

statementList = statement star.
variableStatement = var, variableDeclarationList, tSemicolon.

variableDeclarationList = (variableDeclaration plusSeparatedBy: comma).
variableDeclaration = identifier, (tEq,assignmentExpression) opt.

variableDeclarationListNoIn = (variableDeclarationNoIn plusSeparatedBy: comma).
variableDeclarationNoIn = identifier, (tEq,assignmentExpressionNoIn) opt.

emptyStatement = tSemicolon.

expressionStatement = (((function | leftbrace) not) & expression), tSemicolon.

ifStatement = if, leftparen,expression,rightparen,statement,(else,statement) opt.

iterationStatement = doStatement | forStatement | forStatementNoVar |
whileStatement | forInStatement | forInStatementNoVar.

doStatement = do, statement, while, leftparen,expression,rightparen,tSemicolon.

forStatement = for, leftparen,
var, variableDeclarationListNoIn ,
tSemicolon,
(expression opt),
tSemicolon,
(expression opt),
rightparen, statement.

forStatementNoVar = for, leftparen,
(expression opt),
tSemicolon,
(expression opt),
tSemicolon,
(expression opt),
rightparen, statement.


forInStatement = for, leftparen,
var, variableDeclarationListNoIn ,
in,
expression ,
rightparen, statement.

forInStatementNoVar = for, leftparen,
leftHandSideExpression ,
in,
expression ,
rightparen, statement.
whileStatement = while,leftparen,expression,rightparen,statement.

continueStatement = continue, (identifier opt), tSemicolon.

breakStatement = break, (identifier opt), tSemicolon.

returnStatement = return, (expression opt), tSemicolon.

withStatement = with, leftparen, expression ,rightparen, statement.

switchStatement = switch ,leftparen,expression,rightparen, clauseBlock.

clauseBlock = leftbrace,(clause star),(defaultClause opt),rightbrace.

clause = case, expression, tColon,statementList.

defaultClause = default,tColon, statementList.

labelledStatement = identifier,tColon,statement.

throwStatement = throw,expression,tSemicolon.

tryStatement = try, block, (catchBlock opt), (finallyBlock opt).

catchBlock = catch, leftparen, identifier,rightparen, block.

finallyBlock = finally, block.

functionDeclaration = function,identifier,
leftparen,formalParameterList,rightparen,
leftbrace,sourceElements,rightbrace.



sourceElements = (statement | functionDeclaration ) star.

program = sourceElements.
|
)

...


I really like the way you can separate the grammar from the AST creation (as described in the Executable Grammars[PDF] paper). As you can see there's no code specified for this purpose. Along with the source code there's is a 'testing AST' and a parser that inherits from this grammar which is used by the unit tests .

Almost all the grammar was written using the parser combinators from the library. Only charExceptFor: and accept: ifNotIn: were created.

There are still a lot work to do with this parser:

  1. Clean up the code
  2. Work on performance issues
  3. Find a solution for the "Automatic Semicolon Insertion" feature (see section 7.9) of the Ecma document)
  4. Get rid of some repetition (for example the 'NoVar' productions which are also present in the document)
  5. Better AST creation
  6. See if unicode support is possible
  7. More tests!


In order to see the result of using this parser I created a little program to display the 'testing AST'. For example:



The parser with tests and the other code mentioned can be found here .

Friday, November 21, 2008

Using the Canvas Html element

In this post I'm going to show a little example of using the HTML 5 Canvas element.

The Canvas element provides a way to draw graphics using Javascript. It is currently supported in browsers such as Safari, Firefox, Opera and Chrome. Sadly it is not supported in IE.

There's a lot of documentation on how to use this element. The Mozilla Developer Center provides a nice tutorial: Canvas tutorial. Also the HTML 5 specification document provides a detailed description of the element in The canvas element section.

The Example



In order to play learn about this element I decided to create a toy program that takes an image and creates a little Jigsaw Puzzle of it.

Here's how the page looks:



The running version of this program can be found here.

The Code



The code to create this little program is very simple. First the canvas element is specified as follows:


...
<body onload="init();" >
<p>Canvas Object Tests</p>
<canvas id="myCanvas" width="700" height="600"
onmousemove="moveHandler(event);"
onmousedown="mouseDownHandler(event);"
onmouseup="mouseUpHandler(event);"
onmouseout="mouseUpHandler(event);"></canvas>
<hr/>
<div id="notSup" ></div>

</body>
...


Four event handlers are added to the canvas element to handle mouse interactions to move the pieces of the puzzle.

The init function is called in the "load" event of the body element.


var imageName = 'http://farm3.static.flickr.com/2161/2543461722_a68f3d1e2e_m.jpg';
...
function init() {
img = new Image();

img.onload = function() {
imageLoaded = true;
draw();
}
img.src = imageName;

theObjects = createImageSegments(3,3,{width:240,height:180},{x:5,y:10});

draw();
}


The createImageSegments function creates the pieces of the puzzle.


function createImageSegments(lines,cols,imageSize,basePosition)
{
var incrY = imageSize.height/lines;
var incrX = imageSize.width/cols;
var theX = basePosition.x;
var theY = basePosition.y;
var result = new Array();
for(var i = 0;i < lines;i++) {
for(var j = 0;j < cols;j++) {
result.push(new ImageSegment(this.img,
{x:theX,y:theY},
{width:incrX,height:incrY},
{x:(j*incrX),y:(i*incrY)},
{width:incrX,height:incrY}));
theY += 2 + incrY;
}
}
return shuffleArray(result);
}


The ImageSegment objects are defined by the following function:


function ImageSegment(image,position,size,insidePoint,insideSize){
this.image = image;
this.position = position;
this.size = size;
this.insidePoint = insidePoint;
this.insideSize = insideSize;

this.draw = function(context) {
context.drawImage(
this.image,
this.insidePoint.x,
this.insidePoint.y,
this.insideSize.width,
this.insideSize.height,
this.position.x,
this.position.y,
this.size.width,this.size.height);
};

this.isInside = function(point) {
return (this.position.x <= point.x &&
this.position.y <= point.y &&
this.position.x + this.size.width >= point.x &&
this.position.y + this.size.height >= point.y);
}
}



Two methods are defined: one to draw the section of the image and one to determine of a given point hits the current object.

In order to draw the image the following function is defined:


function draw() {
var myCanvas = document.getElementById("myCanvas");
if(myCanvas.getContext) {

var ctxt = myCanvas.getContext('2d');
ctxt.clearRect(0,0,myCanvas.width,myCanvas.height);
if (imageLoaded) {
for(var i = 0;i < theObjects.length;i++) {
theObjects[i].draw(ctxt);
}
}

// Draw the frame
...


In order to allow the user to drag the pieces of the puzzle across the canvas the following mouse event handlers were added to the canvas.


function mouseDownHandler(e)
{
var x = e.pageX - e.target.offsetLeft;
var y = e.pageY - e.target.offsetTop;
for(var i = 0; i < theObjects.length;i++) {
var theObject = theObjects[i];
if (theObject.isInside({x:x,y:y})) {
dragging = true;
lastPoint.x = x;
lastPoint.y = y;
currentDragObject = theObject;
}
}
}

function mouseUpHandler(e)
{
dragging = false;
lastPoint.x = -1;
lastPoint.y = -1;
}

function moveHandler(e) {
if (dragging) {
var x = e.pageX - e.target.offsetLeft;
var y = e.pageY - e.target.offsetTop;
var deltaX = x - lastPoint.x;
var deltaY = y - lastPoint.y;


currentDragObject.position.x += deltaX;
currentDragObject.position.y += deltaY;


lastPoint.x = x;
lastPoint.y = y;
draw();
}
}



Basically what these event handlers do is to calculate the new position of the image being dragged and update the canvas.

Conclusion




The Html Canvas object provides a nice way to draw custom graphics in a web page using Javascript. For future posts I'm going to try to rewrite the example from the
JavaFX Script, Silverlight and Flex posts using Javascript and Canvas.