AoC 2018 – Day 10 Retro

Today is day 10 of Advent of Code 2018, the fun daily coding challenge I mentioned I was taking part in this year, and I thought it a good time to take a quick look back at my story so far.

I’ve still not managed to rank globally for any of the challenges (the closest I came was on day 5 when I completed part two 696th) but things are going reasonably well on our private BJSS leaderboard, and the challenges have mostly been fun. So far I’ve stuck with Ruby as my language of choice, although I almost broke out Unity 2D for today’s graphical challenge (Early-morning me obviously had grand ideas which were quickly set aside when I realised I could zoom out my terminal and stick with Ruby).

Here’s a quick rundown (with possible mild spoilers) of the challenges to date. The links take you to my solutions on GitLab, which obviously do contain spoilers, so don’t click them if you haven’t already done the puzzle for that day.

  • Day 1 was a very simple problem involving summing a list of numbers, and finding the first duplicated number. Nothing much to say here, nice and quick.
  • Day 2 involved finding characters duplicated two- and three-times in a string, with part two focusing on finding strings that differed by one character. I went with hash-based solutions for this one.
  • Day 3 was about finding overlapping rectangles. I made a simulation for this as the maths escaped me. This was the first solution that was properly object-oriented Ruby, and I got stuck for a while because I accidentally transposed my X and Y coordinates in one of the methods!
  • Day 4 involved finding the guard who slept the most, and (in part two) the minute in which they were most often asleep. Another simulation (I quite enjoyed this one).
  • Day 5 was about reducing a string by removing pairs until none remained. Regex and recursion to the rescue here – a really quick solution.
  • Day 6 was, frankly, a nightmare. I couldn’t really visualise the problem at first, and it took me a lot longer than it should have to really get to grips with it. Solved in the end, but after many hours on-and-off. I did learn something new though 🙂
  • Day 7 involved a dependency graph and another simulation. I had a lot of fun with this, and even made an ANSI-based visual mode so you could watch the simulation unfold in the terminal. Great fun.
  • Day 8 was a simple tree problem involving both breadth-first and depth-first traversal. The depth-first part had a little twist that meant it took a little thinking about.
  • Day 9 caused me a few problems – partly due to some vague wording in the puzzle, and partly due to my not understanding the problem properly for a while. It was made worse by the fact that I initially decided to write it with the wrong data-structure because I felt it would be quicker. After a few false starts I gave up on that and finally made it work using circular linked lists.
  • Day 10 was another fun one involving points and velocities to work out when the points (stars) align to display a message. Initially I planned to switch to something with proper graphical support (in a fit of complete overkill, I fired up Unity) but settled in the end on a Ruby solution after I realised I could make the output fit in a terminal.

And that’s it so far! The most fun I’ve had so far was probably on day 7, while my least favourite has been day 6.

Taking part? Let me know in the comments what your favourite puzzle has been thus far.

Advertisements

Advent of Code 2018

This year I’m taking part in the awesome Advent of Code, and because I haven’t done a lot of Ruby over the past couple of years I thought this would be an excellent opportunity to refresh my skills.  In case you’re unfamiliar, AoC is a series of twenty-five coding challenges. Each day leading up to Christmas a new challenge is posted on the site, and there’s a global leaderboard. You can also have local leaderboards (We have one at BJSS for example).

I did originally consider using the opportunity to learn a new language, but the desire to get back to Ruby proved too strong. In truth, I’m glad it did – every time I come back to Ruby after a break, I’m pleasantly surprised by both the bits I’d forgotten and the bits that have been added.

Advent of Code 2018 is at https://adventofcode.com/2018 . In case you’re interested, I’m posting my solutions day-by-day on GitLab here: https://gitlab.com/rosco.peco/aoc-2018 (they’re only spoilers if you decide to look!)

There’s also a subreddit where you can follow the discussion and see some very cool solutions.

In short, if you haven’t already, you should check it out.

Using GCC as cross-compiler with x86_64 target

This post is a little rough, and is intended both as a memory aid for myself and as an example for anyone else who needs to know this stuff. I’ve recently decided to push toward x86_64 support in my toy/research OS project, and needed to build a GCC cross compiler for that target. In my case I already had an x86 cross compiler built, but I’ve tried to make the steps general for those that don’t.

These steps are tested with binutils 2.26.1 and GCC 6.1.0. I’m using those versions as they match the version of my x86 cross compiler – These steps might work with the more recent versions, but I can’t guarantee it. I will at some point update my cross compilers, at which point I’ll update these steps.

1. Go to your $HOME/src. Create first if needed.

# mkdir ~/src
# cd ~/src

2. Set up prefixes. PATH is only needed if not already set (e.g. this is your first cross compiler on this system).

# export PREFIX="$HOME/opt/cross"
# export TARGET=x86_64-elf
# export PATH="$PREFIX/bin:$PATH"

3. Configure, build and install binutils

# tar xf /path/to/downloaded/binutils-2.26.1.tar.gz
# mkdir build-binutils-x86_64
# cd build-binutils-x86_64
# ../binutils-2.26.1/configure --target=$TARGET --prefix="$PREFIX" --with-sysroot --disable-nls --disable-werror
# make && make install

4. Extract GCC

# cd ..
# tar xf /path/to/downloaded/gcc-6.1.0.tar.gz

Ensure libgcc is built with no redzone – Add this:

MULTILIB_OPTIONS += mno-red-zone
MULTILIB_DIRNAMES += no-red-zone

to the following (new) file:

gcc-6.1.0/gcc/config/i386/t-x86_64-elf

And then make sure GCC configure knows about the new config:

# vim gcc-6.1.0/gcc/config.gcc
/x86_64-\*-elf\*)

And insert:

tmake_file="${tmake_file} i386/t-x86_64-elf"

above the tm_file line.

5. Configure GCC

# mkdir build-gcc-x86_64
# cd build-gcc-x86_64
# ../gcc-x.y.z/configure --target=$TARGET --prefix="$PREFIX" --disable-nls --enable-languages=c,c++ --without-headers

6. Build GCC

# make all-gcc

Go make coffee/eat out at a restaurant/vacation in Barbados…

Note: If building with newer GCC (Found with 7.3.1), there’s an issue in the 6.1.0 source. If you see error:

error: ISO C++ forbids comparison between pointer and integer [-fpermissive]

relating to gcc/ubsan.c, then you’ll need to edit that file, and change line 1473 from:

|| xloc.file == '\0' || xloc.file[0] == '\xff'

to:

|| xloc.file[0] == '\0' || xloc.file[0] == '\xff'

7. Build libgcc

# make all-target-libgcc

8. Install GCC and libgcc

# make install-gcc
# make install-target-libgcc

9. Check the no-redzone libgcc is being used properly when -mno-red-zone is passed:

# x86_64-elf-gcc -mno-red-zone -print-libgcc-file-name

Should print (note the no-red-zone in the path):

$HOME/opt/cross/lib/gcc/x86_64-elf/6.1.0/no-red-zone/libgcc.a

10. Don’t forget to pass -mno-red-zone in LDFLAGS in the actual build!

Generate less bytecode with default methods

Java’s default methods (introduced back in Java 8) are one of those features that solve the intended problem reasonably well, while at the same time allowing all kinds of nasty code and weird inheritance stuff when used in a general-purpose kind of way. Indeed, they’ve been the subject of a ton of posts and the way they (fail to) work still surprises people. They’ve been around for a while now, and there’s a lot of good advice out there on how they should and shouldn’t be used, so that’s not what I’m going to talk about in this post.

What I am going to talk about, however, is the way I’m using them in Moxy, as a way to do a lot less work in runtime-generated bytecode.

A bit of background

Moxy is a mock framework, and it does it’s job by generating mock classes at runtime. These mock classes naturally use a fair bit of bytecode generation, replacing real method implementations with new methods that implement the mock behaviour.

These mock methods do the standard mock thing of recording their invocation, and then they implement behaviour that has been set-up on the mock beforehand.

The problem

In order to implement this behaviour, mock objects need access to all kinds of state that’s specific to the instance – stubbed return values, exceptions they should throw, and more. They also need to have easy access to the mock engine that created them (so they can record invocations, for example).

This is often implemented via static methods on some class somewhere whose job it is to store state. The generated code will typically be peppered with a ton of invokestatic instructions that calls out to methods on those classes in order to get things done.

This works, but it has a few problems:

  • Some kind of mapping between instances and their state must be maintained.
  • It can make it difficult to swap out mock strategies in a clean fashion.
  • It can make testing (of the framework) difficult.

The Moxy approach

Instead of storing state statically, Moxy stores it right there in the mock, and all interaction with the state is done with instance methods. These methods can’t be inherited from a superclass (since mocks usually subclass the mocked class), and I really don’t want to generate them (I like to keep generated code to a minimum, as it’s harder to maintain and test that regular Java), so instead Moxy abuses default methods.

It works like this:

  • All mocks implement an interface, ASMMockSupport.
  • This interface defines one abstract method, __moxy_asm_ivars(). This method is implemented in generated code (since interfaces don’t have instance variables, the mocks hold the variables and expose them via this method)*.
  • The support interfaces defines a ton of default methods that do various kinds of work based on those instance variables.
  • The actual generated code for mocked methods uses invokeinterface calls on this to get stuff done as needed.
  • Other parts of the framework that interact with the mocks (e.g. stubbers) simple cast the mock instance to ASMMockSupport and call the methods they need.

* Yes, that’s a strange name for a method. Moxy does this to lessen the chances of its built-in methods clashing with methods being mocked.

 

The default methods on the support interface handle things like finding the engine that created the mock, adding stubbing, finding appropriate stubbing for a given invocation, running delegate methods and actions, and determining whether the current thread is currently in what Moxy calls a monitored invocation (used for recording purposes only, when mock behaviour is disabled).

This has the benefit that a whole lot of fairly-complex code that would otherwise be either generated, or stuffed into static methods, is now implemented, in Java, as instance methods. They’re easy to unit-test, and they’re easy to maintain. The added bonus is the generated bytecode is also easier to maintain, since it’s as short as possible.

Is this the intended use of default methods? Not at all. Is it correct, or appropriate? I’ll leave that to you to decide. I firmly believe, however, that in this very limited use-case it’s a good solution to a tricky problem, all things considered.

If you’re interested in looking at the code, you’ll find it here.

Mocking v2.0

We all love to use mocks in our Java tests, right? Add the usual mock framework to your test dependencies, sprinkle a few mock, when and thenWhatever calls in to your code, and happy days. You’re able to test things in isolation, and as an added bonus ensure your code is actually calling the stuff it’s supposed to be calling by verifying the mock afterwards. The sun is shining, life is good, and your code is tested to perfection.

But then the clouds roll in, and you have to test a final class. Or you need to mock out a static method in some legacy code. Or, horror, some code that directly calls new on a class you want to mock.

You could hit up StackOverflow, where you’ll find that all these things are possible with existing frameworks, assuming you’re prepared to add in another dependency, use a ton of boilerplate, and refactor your code a bit. Depending on which framework you’re currently using there are a ton of different ways you can kind of achieve what you need.

By now you’ve sunk another hour or two, and it’s still not quite working.

What if there was another way?

The other way

What if I told you there was a framework out there that let you take a final class, and just do this?

mockClasses(FinalClass.class);

FinalClass sc = new FinalClass();

assertThat(sc.returnHello()).isNull();

assertMock(() -> sc.returnHello()).wasCalledOnce();

when(() -> sc.returnHello()).thenReturn("Goodbye");

assertThat(sc.returnHello()).isEqualTo("Goodbye");

assertMock(() -> sc.returnHello()).wasCalledTwice();

What if it also did statics, with the same API, and no extra dependencies?

mockClasses(ClassWithStatic.class);

assertThat(ClassWithStatic.returnHello()).isNull();

when(() -> ClassWithStatic.returnHello()).thenReturn("Goodbye");

assertThat(ClassWithStatic.returnHello()).isEqualTo("Goodbye");

What if it even let you mock out constructors?

final RuntimeException rte = new RuntimeException("MARKER");

mockClasses(FinalClass.class);

when(() -> new FinalClass()).thenThrow(rte);

assertThatThrownBy(() -> new FinalClass()).isSameAs(rte);

What if we put all our arguments about whether we should be doing this kind of mocking to one side for now, because sometimes in life, you’re faced with a nail.

And when you’re faced with a nail, you need a hammer.

There’s one here: https://github.com/roscopeco/moxy

Or grab it with Maven:

<dependency>
	<groupId>com.roscopeco.moxy</groupId>
	<artifactId>moxy-core</artifactId>
	<version>0.90.1</version>
</dependency>

Curb FFI – FFI port of Curb

I believe I mentioned that I’m back at work on the Curb project. In case you missed that, Curb is a ruby extension that provides bindings to the libcurl library. I started it way back, left to concentrate on other things (having kids, making money, etc) and now I’m involved again, working with Todd Fisher who took over maintaining the project when I bowed out. I’ll be fixing bugs, answering questions and generally helping out.

In the meantime, I’ve also started work on porting (if that’s the right word) Curb to FFI, with a view to moving away from the existing C code. The motivations are manifold:

  • As it stands, Curb is pretty much tied to MRI. In the modern Ruby world, where you’ve got JRuby and Rubinius and who-knows-what-next, this is recognised as a bad thing.
  • It’s a nightmare to get it working on Windows. This is because, and I can speak with some authority here as someone who develops on Windows every day, Windows sucks for development. Unless you’re using all-Microsoft tooling, in which case it’s pretty awesome. But for interoperability with portable code, and libraries targeted primarily at other platforms, it sucks.
  • FFI is probably the right way to do these things these days. 10+ years ago, when Curb was first hacked together in about six hours, C extensions were the shizz. Now, not so much. Unless you really need the level of hardware hackery and performance you can get with C, things are better off in Ruby code.

So to sum up, this port is about future-proofing Curb, making it easier to develop, easier to use cross-platform, and (in the long run) safer, probably more performant, and ensuring it can run on all Rubies, including whatever whizz-bang next-gen thing comes out next week (my bet is it’ll be written in Rust. Or Go. Or something…).

Check it out (or clone it, as the cool kids say nowadays) at https://github.com/roscopeco/curb/tree/ffi.

Building Curb on Windows

man with laptop over his head
At first I was like…

As I mentioned in my previous post, I’m now working on Curb again, and currently on Windows. Back in 2006 when I wrote the original Curb, I wouldn’t go near a Windows box for religious reasons, and the project has never officially supported the platform. There are plenty of bugs and posts around about people having mixed success with getting it to work.

Since then, my views have mellowed, partly I think because I’ve come to appreciate that there’s no room for religion in software engineering – you use the right tool for the job. Partly that, and partly by my desire to, you know, get paid and own stuff and whatnot. These days I do as much work on Windows as I do on *nix, and my bank balance is all the better for it. So anyway, back to the point of this post.

Building Curb on Windows is a bit of a nightmare. It took me a fair while to figure it out, and I wrote the damn thing. If it got me feeling like the guy in the picture above, then how must the everyday user trying to get the gem going feel? If they’re just trying to install it and write some code, I’m guessing they immediately give up and go with another library. But what if they are trying to use something else that depends on the Curb gem? I’m guessing that’s when they get so frustrated they file shouty bug reports with the project. And I don’t blame them. It would have been nice to have someone to shout at while I was trying to get it working.

In the end, I did get it going, but it required me to build libcurl from source. I posted an answer to the bug report I mentioned above with the how-to of it, and the poor person who filed it reported back that it worked. You could click through, but I’ll reproduce the steps below to save your finger.

Most likely, your compiled libcurl is incompatible with the ruby devkit compiler. You can verify this by running (this is on my machine, obviously change your paths):


> c:\Ruby200Devkit\mingw\bin\gcc.exe -L. -lcurl
# c:/[...]/ld.exe: skipping incompatible ./libcurl.dll when searching for -lcurl
# c:/[...]/ld.exe: skipping incompatible ./libcurl.dll when searching for -lcurl
# c:/[...]/bin/ld.exe: cannot find -lcurl
# collect2.exe: error: ld returned 1 exit status

Notice the lines about “Skipping incompatible” before the final “cannot find lcurl”. Try grabbing the curl source from https://curl.haxx.se/download/curl-7.54.0.tar.gz , extract it somewhere, and then open up a terminal and try the following:


> c:\path-to-your-ruby-devkit\devkitvars.sh
> which gcc
# important - verify here that the gcc is the one from your ruby devkit!
> cd 
> sh configure --with-winssl     # and whatever other options you require
> make
> make install

It’s very important that you don’t have any other mingw/msys/cygwin compilers in your path, and that you do this in a windows terminal, not msys/cygwin sh. Otherwise, you’ll probably just build another incompatible library.

You should now have libcurl-4.dll in c:\path-to-your-ruby-devkit\local\bin. Now it gets a bit messy, so hang in there. This part is probably a bug in the build, but easy to work around.


> cd c:\path-to-your-ruby-devkit\local\bin
> copy libcurl-4.dll libcurl.dll

The build needs libcurl.dll (it won’t compile with libcurl-4.dll, but the extension won’t run without the -4 suffix, so we’ll have to manually copy the dll later on).


> gem install curb -- --with-curl-lib=c:\path-to-your-ruby-devkit\local\bin --with-curl-include=c:\path-to-your-ruby-devkit\local\include

Assuming the build goes well (it should, though it might take a while), you now just need to copy the curl dll to the appropriate place:


> copy c:\path-to-your-ruby-devkit\local\bin\libcurl-4.dll C:\Ruby22-x64\lib\ruby\gems\2.2.0\gems\curb-0.9.3\ext

Now run irb -rcurl and, all being well, you should be good to go.

I’m back on the Curb team!

curl / libcurl
curl lives at https://curl.haxx.se/

Way back in 2006, after reading on ruby-talk about people’s problems using libcurl with Ruby, I put together a basic C extension to replace the (by-then-unmaintained) bindings that already existed. Little did I know then that it would end up being some of the most popular open-source code I’ve written.

In time, pressures of family, work, and life in general meant I didn’t have a lot of time to devote to my open-source works, and so Todd Fisher took over as maintainer of the project, and did some awesome work improving it, building the multi interface code, and generally making Curb more and more useful. The project is still going strong over ten years later.

I came back to Curb via some work I was doing on a Windows-based system, and after a few hiccups building the library I found myself patching things up a bit to make them work on Windows (which isn’t officially a supported platform for Curb), and a couple of pull requests later Todd got in touch and asked if I’d like to be added to the project on Github. I thought this over for, oh, about ten seconds, and then said yes. I have more time these days for Open Source work, and I don’t have anything currently on the front-burner, so I’m now back on Curb. Todd’s still the boss (after all, he has more code in there than I do!) but I’ll be happily working away, fixing bugs where I can, and trying to make life easier for people out there wanting to use Curb on Windows.

Here’s the original announcement of Curb, from November of 2006.

From: Ross Bamford
Date: November 17, 2006 1:25:05 PM CST
To: ruby-talk_at_ruby-lang.org (ruby-talk ML)
Subject: [ANN] Curb 0.0.1 – New ruby libcurl bindings
Reply-To: ruby-talk_at_ruby-lang.org

Curb 0.0.1 is now available from http://curb.rubyforge.org. Curb
provides nice, easy to use bindings to the libcurl URL transfer
library.

This is the first release, and Curb is still a work-in-progress.
Currently, it supports the curl_easy interface, and can handle the
most common usages for libcurl.

The project is now seeking user feedback, testers on various
platforms, and requests for the features you need the most.

Blog Reboot

Just a quick note to say that the blog is now back online, but sadly missing quite a few posts that were lost by my old webhost.

The last post I’ve been able to restore is from almost two years ago, when I was just starting out on the drone project. Here’s a quick summary of what’s been happening since then:

  • The drone project is still unfinished, and has fallen by the wayside a bit if I’m honest. I still plan to get it going, someday.
  • I’ve recently found time to resume work on my minimal experimental kernel, Mink. (Find it on github if you’re interested).
  • I have a new day-job – I’m now working for a small non-IT company, putting together a brand new bespoke MRP system for them using Java EE, with a Vaadin front end. In between times, I’m also the entire IT department, which is kinda stressful but also fun.

So all in all you’ve not missed a great deal, and now the blog has a new home, I’ll be regularly updating here with new posts.