Sophia

Oops I forgot to devlog for a while!

I found an annoying bug in the SSA optimisation pass where the type stack was discarded when an if/else block was encountered. This makes sense in normal execution, (because if/elses only occur when the stack is empty), but some list reporters use if/elses internally (because their output depends on the input moreso than usual - they need to check for inputs like “random” which has special behaviour). So, I rewrote how stacks are handled in the SSA; now, rather than at each node in the graph storing the type stack and also which variables to pop into from the stack, each node stores a single instruction: push something to the stack, or pop from the stack (or drop from the stack). This results in way more nodes, but it’s much simpler and doesn’t have the same problem as before. Success!

I’ve also implemented a couple more blocks - data_listcontainsitem, pen_changePenColorParamBy, and motion_movesteps.

Today’s attachment: a stack overflow when there are too many SSA nodes. Woops! Maybe time to turn some recursive calls into loops.

Okidokes it’s been a long 1h47m!

I’ve added the get/set/change x/y blocks which was pretty simple. The majority (or what felt like the majority) of this time was spent diagnosing an annoying bug where sometimes a loop condition was being overwritten by the loop body. Mighty strange! Turns out that the list of ‘inline steps’ within the list block returned different things depending on whether you wanted mutable access or not - I forgot to update the immutable accessor when I added a ‘pre-body’ field to accommodate control_foreach. It took an age to find this but it was a simple fix when it was found; along the way I also cleaned up some other code though, so I think it was worth it.

No visible changes introduced here really so have an image of all the supported blocks thus far.

I’ve been working on a bunch of miscellaneous stuff recently. Here’s a quick list:

• I’ve implemented some new blocks: control_for_each (required some annoying changes to the loop IR!), sensing_mousex/mousey/mousedown, and operator_round, as well as implementing the ‘name’ option of the looks_costumenamenumber block (attachment: a sprite saying its costume name). The latter is a bit rough and ready in its implementation at the moment, but it definitely works.
• I’ve moved the compilation process into a web worker so that if it gets stuck in a long loop it shouldn’t hang the main thread. This was super annoying to get working because vite’s HMR was behaving strangely, but I think it is working acceptably now, including error handling etc
• I noticed that larger projects were either taking an extremely long time to compile, or getting stuck in an infinite loop (i’m not sure which) - this seemed to be happening when there were deeply nested if/else blocks. I’ve changed how these are handled to delay compilation a bit longer if we can guarantee the step is warped, which seemed to fix most of the issues I was observing, but definitely not all (in particular I think it still hangs for non-warped steps D: )
• and i also now allow nonexistant procedures to be called, as noops - this is often used in “comment” blocks or with the scratchaddons debugger blocks.

A couple of things done since the last devlog:

• “stop all” is now implemented, although i think it throws an error when there are multiple threads running at the same time - luckily this does indeed terminate the project, but not in the way we’d like it to
• the greater than & less than blocks now correctly handle string/number comparisons - strings need to be converted to numbers first, so that “10” > “9” is true
• const folding now considers that variables may be overwritten in loop bodies - if that’s the case, the variable values are set to be unknown, so that we don’t end up ignoring any mutations that have happened in the loop bodies.

The last two points together made it quite difficult to diagnose a problem with the attached script - as sometimes it would return 90, and sometimes 0! This was especially tricky as the const-folding bug was dependent on if loop unrolling was enabled or not - since if/else blocks didn’t have this problem.

I have discovered some bugs which have been seemingly hanging around for a while (according to my rough bisection), and have been working on fixing some of them. One of them involved reference cycles being creates when nested non-yielding loops were created, with no block between the ends of the loops - the function that dealt with the ends of loops failed to consider the case where we might need to yield (e.g. in between iterations of an outer loop), so just tried to inline everything which is a bad idea. The other bug was that the procedure that deals with global variable propagation surrounding procedure calls wasn’t visiting every step; this was a simple fix. I have added test cases for these bugs so we now have 47 tests passing (as shown in today’s attachment - sorry I have nothing better to show!)

I’ve fixed a bug where things that were set up at the beginning of project running were not torn down correctly, so that if you navigated to a different project without reload, things would break (because things were imported from a module only once, at page load); I now tear things down gracefully when the project runner component is unmounted.

I’ve also implemented the data_showvariable and data_hidevariable blocks, which required a bit of exploration into how best to store monitors internally; I concluded that it’s probably best to leave most of the work to the JS side, because the WASM doesn’t actually need to know anything about monitors other than if they exist and are used.

The attachment shows a variable monitor being shown and hidden and changing value

I have now added backdrop switching and related blocks; this was incredibly frustrating as the backdrop was simply not being rendered and I couldn’t figure out why; turns out that I mistyped isStage as is_stage. I love javascript!

The code for the actual blocks was very similar to the equivalent costume blocks, with the caveat that we need to figure out which target the stage is, rather than just saying ‘yup just do it for the current target!’ which took a bit of time but not too much.

With this, we can now play super advanced projects like the one attached

I have now implemented the ‘when this sprite clicked’ and ‘when stage clicked’ events, which involved a small amount of wrangling with the current event handling which is… not designed for this sort of thing (because the only event it really handles at this stage is the green flag, because broadcasts can’t be triggered externally). But I bashed something together that worked, because I couldn’t think of a better way of doing it at the moment.

Attachment: me clicking a sprite to make it change size, how exciting

I have rejigged the project running code (on the javascript side) to make things a bit nicer to read; rather than passing functions around all over the place and defining lots of local functions referenceing local variables that are then returned, etc etc, a project runner is now represented as a class extending EventTarget, so we can register event handlers as and when we need to, and functions are defined at a higher scope than they were previously (yay!).

I don’t know what to put as the image, so have a screenshot of an example of event handling being used in a real world scenario i guess

I’ve worked on some ✨aesthetics✨ so that now the whole question asking thing looks a bit more like vanilla scratch: the text box appears over the stage, and, unless the sprite asking the question is the stage, the question appears as a say bubble. How nice! I have also added some comments to some code that briefly confused me yesterday, so hopefully it doesn’t confuse me as much in the future.

I’m focusing for a little bit on adding some blocks that are likely to be used in real-world projects rather than just benchmarks: things that allow interaction with the outside world, like mouse events and that sort of stuff. I’ve got a nice rudimentary implement of the “ask and wait” and “answer” blocks, that are functional (aesthetics can come later!), which was a little bit fiddly to get working due to the interaction between the JS and WASM worlds, but it does seem to work ok.

This also means that the attachment for today’s devlog can be something meaningful!! Today it is a video of ask and wait working. (Disclaimer: I am not a cat)

Turns out that the previous changes actually made an extra 2 tests pass that i hadn’t noticed - because 2 tests also regressed. I’ve fixed these (and hopefully preemptively fixed some future bugs), although i’m not entirely sure why the changes I made fixed the bugs. The main thing was changing how loop unrolling works to eagerly clone the loop body - which is what the big refactor was trying to avoid. but somehow that made things worked (the bug was essentially that during loop unrolling, variables were created that were read from but never initialised).

But that means we now have 45 tests passing which is nice (and now up to 400 commits! [do bear in mind the first commit was some time in 2023 i think])

The recent work to revamp how steps are stored internally is now complete, which means that loops containing blocks that yield now work correctly! I’ve added two tests for this to catch any regressions in the future. I feel like the code is now even less readable than it was - there is more indirection than there was previously I think - but it should be easy to make it nicer in the future. But the basis is there!

Today’s image: 2 extra tests passing (but both ones that i added)

I’ve been working on a large refactor, which should help resolve some fundamental problems with the IR.

Currently, all steps are stored as Rcs. When a step is used in multiple places in the IR, it is deeply cloned (i.e. the underlying Step is cloned and assigned a new ID, rather than just cloning the Rc). This causes problems where a step needs mutating, but it’s been cloned: some versions lag behind and are never updated. For instance, when we encounter a loop in which the last block yields, or doesn’t continue the opcode stack linearly (think: non-warped proc calls, broadcast and wait), the loop isnt properly constructed and we end up terminating after only one iteration.

To fix this, I’m trying to give steps types that reflect their use. Non-inlined steps (those that are started at the top-level by the scheduler) are stored as RefCells in a central map, and referenced elsewhere by a StepIndex (a wrapper around usize). Inlined steps - e.g. if/else statement bodies - are stored everywhere as Rc<RefCell>s and not stored centrally. When inlined steps are used in multiple places, they are cloned lazily, i.e. only when they need context-aware mutation.

I have done most of this and am now left with another small problem, to do with newly introduced polymorphisms over the two kinds of steps. In such contexts, when I want to reason about all steps - e.g. in the SSA pass, where each step is associated with a graph - it’s not clear how steps should be stored. To sort this out I’ll probably create some sort of Step trait implemented for the relevant types, backed by the current Step struct, with some sort of dynamic dispatch for hashing. Or, I might change some algorithms to avoid needing such a collection of steps - I have yet to decide. Regardless, now seemed like a good place to make a commit before I make yet more big changes.

Today’s image is the latest commit summary (I’ve nothing else to give as it doesn’t compile yet)

I’ve now implemented control_wait, which was very similar to event_broadcastandwait and should have been simpler, but I managed to really confused myself with when threads should terminate and when they shouldn’t… but I managed to get my brain working eventually. Similarly to broadcast and waiting, this spawns a thread in the same thread stack as the current thread (I told you I needed to come up with better words for the different types of thread), with the struct argument having a single float argument, which is the value of the timer after which the thread should resume. This value is then compared to the timer value in subsequent steps.

Today’s image: 2 more tests passing (and more failing, but that’s ok I think)

Taking a brief detour from broadcast-related stuff, I slightly altered the project loading system so that it can now load projects that weren’t uploaded from the online editor - turns out that for these, https://projects.scratch.mit.edu/[id]/ (with a trailing slash) returns 404, but without the trailing slash it’s all good (but returns the zip instead of just the project.json. but that’s fine).

I’ve also implemented the timer blocks in a fairly rudimentary manner - I think they drift a bit more than they should, but that’s something I’m happy to deal with at a later date.

I have also now reached 20,000 lines of code (but only 900 lines of comments! shocking)

Today’s image: another test is passing (which is nice because it means I don’t need to be creative about what image to use)

I have now implemented the broadcast and wait block, which was actually quite fun to implement. It works like so:

• the relevant threads are spawned, and their thread indices added to a GC array

• the step that comes after the broadcast and wait is inserted in the relevant place

• a new thread is spawned in the same stack, which polls the aforementioned array of indices to check which threads have terminated, and if they have all terminated, yields to the next step

which all works quite nicely. Alas this doesn’t cause any new tests to pass because they all either need other blocks to be implemented, or rely on execution ordering which hyperquark doesn’t respect yet. So for today’s image, you can get my lines of code report from cloc - we’re rapidly approaching 20k which is astonishing. (as a reminder, much of those 20k lines of code were written before flavortown)

I’m getting better at writing devlogs after fewer hours of work! In preparation for implementing the broadcast and wait block, I split the WASM for spawning a new thread in the same stack into its own function, in much the same manner as spawning a brand new thread was split previously. (I think I need to come up with some better terminology, because I’m using thread both to mean a stack of blocks headed by a hat block, and a structure keeping track of a currently running block).

I also changed some rustfmt settings (joyous!) to make some things a bit nicer - now imports are grouped nicely depending on whether they’re from the crate, std, or external. That’s been bugging me for ages so I’m glad I did that.

No more tests are passing so the image this time is of a totally unrelated script that I discovered turbowarp intentionally breaks compared to scratch. Fun! (see: https://github.com/HyperQuark/hyperquark/issues/46)

the broadcast block has now been implemented; broadcast and wait shouldn’t be too difficult following these changes.

The most time-consuming and thought-provoking change here was that I wanted to move the thread spawning logic into its own static function so it could be used in multiple places. I already had code in place to supply static functions (but only when used), but this required the instructions to be able to be generated inside of a const block. Alas, the thread spawning function needed type indices that aren’t available at compile time, so I had to rejig this such that the functions are generated at the module generation time instead, which was a bit fiddly but some closures did the trick.

Attached image: the usual (one more test passes! yay! [but i think it might pass due to a bug, because execution order isn’t fully scratch-compatible yet])

Since my last devlog I’ve tidied up some small bugs around loop unrolling and const folding, and have also addressed some very long-standing TODOs in operator_equals; now, strings are compared to numbers correctly, so that “1”==“1.0” is true (yippee). Also, ln can actually return NaN now.

Next up: broadcasts?

Today’s image: 1 more test passing.

I have no idea how I managed to accrue nearly 22 hours of undevlogged time - I think hackatime must be having a bit of a silly moment (or the time that’s displayed when I write the devlog is just wrong).

I have been working on some new optimisations which should counteract a big ol’ performance regression that I had to introduce recently to maintain scratch compatibility. Now, the first few iterations of each loop are unrolled (in the hope that the types of any variables stabilise to a single basic type after a few iterations), and I’ve implemented a little bit of const folding to help wasm-opt out, as it can’t optimise string operations.

I have no suitable images today as the only thing this changes is performance, which is tricky to take a picture of, so have a picture of a llama.

More bugs fixed, primarily surrounding procedures; in particular, non-warped procedures are now called with return_call_ref to avoid annoying fallthroughs, global variables are backed up before non-warped procedure calls, and procedure return variables are now boxed where necessary (this might be necessary because of control_stop). 36 tests passing!

Woops! I forgot to devlog when I last committed so I’ve now got 2 things to devlog about, and quite a lot of time!

The more interesting thing is that non-warped procedures (custom blocks without “run without screen refresh” enabled) are now supported; this required large changes to the scheduler which I expected to have a very large performance impact, but it seems to be ok for now. Will keep an eye on it.

I also redid the JS that actually runs the project, both to make it cleaner (it basically hasn’t changed since I first wrote it awfully 3 years ago), and to be able to reuse the same project runner in the integration tests. This all works nicely, and we now have 33% of tests passing which I think is very exciting!

Ok so 5h48m is a long time to go without a devlog but I was working very hard to fix many annoying bugs! I have now implemented data_insertatlist, data_removeitemoflist and data_listcontents. The latter was mighty annoying, because its behaviour differs depending on if all of its elements are single-character strings, which is annoying to test for and also means that strings can no longer be proactively converted to floats - this has put const-folding higher up in my list of priorities!

New milestones reached: 17,000 lines of code (!) and 23 integration tests passing (and also, wow look at all those unit tests!) (see images)

A bunch of other msicellaneous bugs fixed, but the most interesting thing is not a bug fix but a rework of how lists are initialised. Originally, i was using the array.new_fixed instruction, which requires you to list every member of the list in order to instantiate it. This is nice because it is useable in extended const contexts, so you can get away with immutable lists being actually immutable. However, I then realised that I was initialising lists with a maximum length of 2000, rather than 200,000 (which is what it should be), and I didn’t really want to generate 200,000 instructions for lists that are going to be mostly empty. Instead, I’m now initialising the lists with the required amount of elements, in some sort of sensible default state (i.e. 0 or “”), and then in the WASM start function, using the array.init_data or array.init_elem (for strings) functions, which svaes quite a lot of space in the generated WASM. Yay! 21 tests pass now :)

The promised fixes of IR type system bugs have arrived:

Some list blocks take more arguments than the equivalent(ish) variable blocks, which was causing confusion in the SSA optimisation - these are now ignored and things work as expected.

When new SSA variables were created, they were created with a dummy initial value of false. This was artificially inflating their type to include Boolean, which was causing problems; new SSA variables are now created with an empty type, as expected.

We now have 20 tests passing - I wasn’t sure what to put as the attachment so I’ll just give you an image of the test summary again. You’re welcome :)

Ok so apparently time is counted since the 15th of December, not from when you sign up to flavortown - so I’ve got 17 hours to devlog for. Sorry ‘bout that. I have so much to say that it ends up going over the character limit, so I’ll have to be quite concise.

So, a summary of what I’ve been working on in the last 5 days:

• variable type analysis has been rewritten to be less buggy and more maintainable - the main difference is that, rather than each step being responsible for writing any variable changes to the outer scope at the end, the outer step is responsible for this (this is inspired by the idea of ‘phi nodes’ in tradition SSA optimisations, which I’ve only recently become aware of). This makes life a lot easier, as steps don’t need to keep track of multiple different states - they just focus on themselves, and when an inner step (in a loop or if/else block, for example) needs optimised, it can compare the state of the inner step to its own state, and react accordingly.
• I’ve taken some of turbowarp’s (another scratch mod, that compiles scratch projects to javascript)’s integration tests so I can do more automated tracking of feature parity with upstream. At the time of writing, ~18% of eligible tests pass, which isn’t bad.
• This highlighted a lot of project loading issues which are now fixed, including that sb2 files (from projects created using Scratch 2) couldn’t be loaded as they were never converted to sb3s. There are still a couple more bits and bobs which need ironing out, but they seem to be mostly quite obscure things (like having a null variable ID…. why does scratch allow that?!)
• A lot of housekeeping to do with dependencies and CI
• Variables are now generated with their initial values intact
• Most list operations are now supported, using wasm GC arrays for now.
• And some other small fixes.

Wow, that’s quite a lot!

Next up are some bug-fixes in the IR type system, and then more list stuff.

The current thing I’m working on in hyperquark is lists. The changes are looking quite chunky at the moment.