Recent UI improvements

Over the last few months I've done a lot of work on Factor's UI toolkit, and the developer tools built on top. Here is an overview of what's changed.

Code cleanup

I've been working on the UI since 2005, and it has accumulated a lot of cruft since then. Language features have come and gone and not enough refactoring was done over time. Last year I rewrote the HTTP server and compiler using the latest language features and the result was very clean code. The UI is now written in the same style.

Improved font support

I've blogged about this:

• Mac OS X
• Windows
• X11

All UI gadgets that render text now use the appropriate platform-specific mechanism for rendering text. The ui.text vocabulary provides the cross-platform abstraction layer. The fonts vocabulary defines data types for fonts and font metrics. This replaces ad-hoc loosely-typed "font specifiers" that the UI used formerly, where a font was just a triple; { "sans-serif" plain 12 } for instance. Font metrics are now supported in a cross-platform manner too. All relevant gadgets now do baseline alignment.

Image support

The UI now supports an easy API for displaying images. The ui.images vocabulary defines some words which can be called from your gadget's draw-gadget* method. The ui.gadgets.icons vocabulary defines a simple gadget that renders an image and nothing else. This is all built on top of the images vocabulary, which implements BMP and TIFF loaders in pure Factor. Hopefully we'll get PNG and JPEG at some point too.

Editor gadget improvements

The ui.gadgets.editors vocabulary supports some new features:

• Undo and redo (Control-z, Control-Shift-z)
• Join lines (Control-j)
• Character and word navigation now uses unicode.breaks

Table gadget replaces list gadget

The ui.gadgets.tables vocabulary implements a new gadget which is a replacement for the old list gadget. It's functionality is a superset of what lists offered. Tables are used extensively by the new developer tools to display completion popups and such. Unlike lists, which would create a gadget for every row of data, tables do not have any children and render rows directly. This reduces memory consumption. Tables take the list of rows from an underlying model, and place the currently selected row in another model. The latter model can then be wrapped in an arrow model to compute a new list of rows, which can then be the model for another table. This way, multiple tables can be chained together for a 'drill down navigation'-style of interaction with very little code.

Scroller gadget improvements

Scroller gadgets, defined in the ui.gadgets.scrollers vocabulary, now provide a protocol that their children can implement. This protocol has two generic words:

• viewport-pref-dim - this allows the child to specify the preferred dimensions of the scroller surrounding the gadget. Tables and editors implement this generic word, allowing you to set various slots, such as min-rows and max-rows, which control the size of the scroller surrounding the gadget in character units.
• viewport-column-header - constructs a gadget which is displayed at the top of the scroller. This allows the table gadget to display column titles which are always visible, regardless of the vertical scroll position.

Frame layout improvements

The ui.gadgets.frames vocabulary is more flexible now. Instead of limiting frame layouts to a 3x3 grid with the center item stretched to fill available space, the grid can be of any size, and an arbitrary cell can be designated to take up available space.

Models API changes

The models vocabulary has undergone some cleanups. To avoid confusion with sequence functionality, filter models are now called arrow models. Compose models are now called product models, since really they represent a cartesian product of functions, not a composition of anything at all. The new models.arrow.smart vocabulary wrap an arrow around a product whose arity is the arity of the arrow's quotation.

Integration between event loop and I/O

Until Factor supports real native threads, any FFI call blocks all Factor threads until the call completes. I/O is done with non-blocking APIs on Unix (epoll, kqueue) and Windows (IO completion ports), so socket operations can proceed concurrently. However, until recently, the UI would have to poll for events because of this, because blocking calls to wait for events would prevent I/O and other Factor threads from running. This meant that even if you weren't doing anything in the Factor UI, it would use a little bit of CPU - 5% to 25%. This problem has been fixed. On Mac OS X, I use the CFFileDescriptor API to wait on a kqueue and GUI events at the same time; you can provide a callback which is invoked when file descriptors are ready for I/O, and call [NSApplication run] as usual. On X11, I use XConnectionNumber() to get a file descriptor out of a Display and call wait-for-fd to wait for events to arrive while also allowing other Factor threads to run. This solves the CPU usage problem and allows Factor threads to run concurrently with the event loop waiting for events.

Improvements to tooling

The main focus of my recent UI work, however, has been on improving UI developer tools. I plan on making a screencast to highlight the new improvements soon.

OpenGL textures and the power-of-two size restriction

Prior to version 2.0, the OpenGL specification required that texture dimensions be powers of two. This simplifies the implementation of texture mapping, because converting floating point texture co-ordinates (which are in the range 0..1) to texel coordinates is trivial; multiplying a floating point number by a power of two is essentially just adding a number to the exponent. Eventually, more capable drivers and graphics cards came along, and introduced the ability to use non-power-of-two texture dimensions. To signal this capability to GL applications, they report supporting the GL_ARGB_texture_non_power_of_two extension. OpenGL 2.0 implementations are required to support this extension.

In practice, the only major OpenGL implementations which don't provide this extension are older X11 drivers, and the Microsoft Windows software renderer, which is a very bare-bones OpenGL 1.1 implementation.

There is a trick for padding textures up to a power of two for implementations which don't support this extension, however it doesn't seem to work everywhere either. Instead of manipulating the bitmap in software before passing it onto a call to glTexImage2D(), it is permissible as of OpenGL 1.1 to pass a bitmap pointer of NULL. This creates a texture with uninitialized content. The glTexSubImage2D() function is used to fill it portions of the new texture. In particular, glTexSubImage2D() places no restriction on the width and height, even if GL_ARGB_texture_non_power_of_two is not supported.

The above trick works with the Windows software renderer. On the other hand, previous-generation MacBooks with Intel graphics suffer from a driver bug which results in artifacts appearing when this feature is used to render scaled textures. However, all OpenGL implementations in recent Mac OS X releases support non-power-of-2 textures, so on this platform, the workaround can be avoided entirely anyway.

In Factor, the opengl.capabilities vocabulary provides some utility words to check for extensions. For example, a common operation is checking for either a specific OpenGL version, or an extension (new versions of the GL spec frequently absorb existing extensions):

"2.0" { "GL_ARB_texture_non_power_of_two" } has-gl-version-or-extensions?

The gl-extensions word outputs a sequence of all supported extensions. Here is the output from the Mesa software renderer on Linux.

I replaced my old code in opengl.textures which padded bitmap image objects out to powers of two using sequence manipulation words, with the new way using texture sub-images instead. If the extension is present, no padding is performed, ensuring correct behavior on Mac OS X. This means that any code using opengl.textures, such as the UI's text rendering and image support, should now spend less CPU time running Factor code.

Factor's OpenGL binding has been in development for 4 years and has seen contribution from 4 developers. For a demo of what it can do, try "spheres" run in the UI listener. You will need a video driver that supports OpenGL 2.0 or GL_ARB_shader_objects.

Rendering text on Windows via Uniscribe

My original goal was to use Pango to render Unicode text in the Factor UI on Windows. This didn't pan out, for a number of reasons:

• Pango, Cairo and all of their dependencies add up to around 7Mb of DLLs that we'd need to ship with every Factor binary, as well as every standalone app binary deployed from Factor. That's too much when a 'Hello world' compiles down to a 500kb image.
• Pango has various bugs on 64-bit Windows.
• Pango doesn't play well with Microsoft's ClearType, and anti-aliased text is clipped for some reason.

I'm sure these problems will get fixed eventually (except for the first one perhaps) and Pango is open source so I could always send a patch, but I'd rather spend my time working on interesting things instead, so I've decided to bypass Pango on Windows altogether and use Microsoft's native Uniscribe API instead. Uniscribe ships as a standard part of Windows XP (actually it's been around since IE 5.0) and so Factor can depend on it being installed. On X11, I continue to use Pango; most *nix systems have at least part of the GNOME platform installed, so Pango and Cairo will be there, and I haven't seen any rendering issues in Pango with X11 either.

I'm using the Uniscribe script string API, which is intended to be used for laying out and rendering a piece of text with a single font and color. It is directly analogous to CTLine in Core Text and PangoLayout in Pango.

The function to create a script string, ScriptStringAnalyze, takes a device context handle as a parameter. The device context must be provided if the string is going to be rendered or measured.

Before creating the string, the font and text color are set in the device content. To set the font, I look up a font handle with CreateFont, and pass it to the SelectObject() function. There's an important caveat with CreateFont(); if you want your font size to be specified in points (rather than pixels), you must pass a negative size. I noticed that 12-point font was rendered way too small; changing the 12 to a -12 fixed the problem, so now the Factor UI does this for you on Windows.

The text color is set by calling SetTextColor, and the background color (which is only rendered if a flag is passed to ScriptStringOut(); see below) with SetBkColor.

For both fonts and colors, the Uniscribe text rendering uses Factor's cross-platform font and color types.

Size measurement is done by calling ScriptString_pSize(). Unlike Core Text and Pango, Windows Uniscribe makes no distinction between metric and ink bounds. There is a provision for oversize glyphs, such as those in the Zapfino font (see my blog post on ink and metric bounds), where each glyph has an associated ABC metrics structure. I'll implement support for this later.

When rendering to an offscreen context that is intended to be used as an OpenGL texture, as in the Factor UI, a bit of a chicken-and-egg problem occurs, because we need to know the size of the resulting text before we can create a bitmap. Fortunately, Windows GDI separates the process of creating a memory (off-screen) DC and allocating the bitmap storage for it, into two functions, CreateCompatibleDC() and CreateDIBSection(). The trick is to create a DC, create a script string, get its size, then allocate the bitmap for the DC, and finally render the string.

Script strings can be rendered to their underlying DC with the ScriptStringOut function. This function takes a number of parameters. For instance, it can render the text selection for you.

Font metrics -- the ascent, descent, and leading -- can be obtained by calling GetTextMetrics() on the DC.

Once the text has been rendered into a memory DC, the underlying bitmap needs to be obtained and the graphics object handles freed. This is the third time I implement a similar-looking make-bitmap-image combinator, so by now I've developed some utilities that I've abstracted out into the images.memory vocabulary. The bitmap is cached as a texture in the same way on all platforms; I've discussed OpenGL texture caching before.

Converting between x co-ordinates and line offsets, and vice versa, can be done with ScriptStringXToCP() and ScriptStringCpToX(). Watch out for the fact that passing the length of the string to ScriptStringCpToX() is invalid; if you want the X-offset of the trailing edge of the last code point, you have to pass length-1 instead, with the fTrailing parameter TRUE.

Finally, script strings are freed by calling ScriptStringFree(). When binding to the API from another language, watch out for the type of the input parameter; it's a pointer to a SCRIPT_STRING_ANALYSIS type, which is itself a pointer type. So you're passing a pointer to a pointer to a struct! I got the type wrong in my FFI declaration the first time around and was getting segfaults when deallocating stuff. Very annoying.

The code implementing this is split between four vocabularies:

• windows.offscreen - support code for creating GDI memory DCs. Originally written by Joe Groff for another purpose; I've generalized it and put it in a common location so that it can be used by both the Uniscribe code and offscreen gadget rendering.
• windows.fonts - looking up GDI font handles from Factor font descriptions
• windows.uniscribe - the bulk of the code; creating, rendering script strings, converting x co-ordinates to line offsets and vice versa
• ui.text.uniscribe - a backend for the UI's cross-platform text rendering support. Just a thin shim over the preceding vocabularies.

Here is what it looks like when all is said and done:

Sup dawg, we heard you like Smalltalk so we put Smalltalk in your Factor so you can send messages while you roll

A week ago, I went to the PyCon VM summit in Chicago. It was great fun and I got to meet various Internet celebrities such as John Rose (Sun JVM), Evan Phoenix (Rubinius), Charles Nutter (JRuby), Avi Bryant (Seaside), and Allison Randal (Parrot).

Factor's own Daniel Ehrenberg and Doug Coleman were also there, and I've heard rumors that the world-famous C++ programmer Joe Groff may have tagged along for the ride.

Every VM implementor gave a short 10 minute talk. Mine was an overview of the optimizations and implementation techniques used in Factor; you can look at the slides in a recent Factor by running "chicago-talk" run in the listener. A common theme at the summit was the distinction between platforms versus languages. The JVM, Parrot and PyPy people are all vying for language designers to implement their languages on top of these VMs. The idea is that the platform developers take care of the "hard" stuff such as the optimizing compiler, garbage collector, and libraries, whereas the language designer feeds a grammar into a parser generator, and bingo, instant programming language.

While discussing Smalltalk minutiae with Dan and Avi Bryant, we hit upon the idea of trying to compile Smalltalk down to Factor. After all, Factor already has everything you'd want in a platform for hosting languages. We have a great optimizing compiler, a generational garbage collector, C FFI, a ton of libraries, and so on; in theory we've already done most of the hard work for someone who wants to make a language without dealing with low-level details. So while we've written countless DSLs in Factor since the very beginning, why not try implementing a more complete language?

That's exactly what I did, and the code is in the repository under extra/smalltalk. Run it by issuing the following command in the Factor listener:

"smalltalk.listener" run

Then try a Smalltalk expression such as 1 to: 10 do: [:i|i print]., or look at extra/smalltalk/eval/fib.st for a more complete example. Incidentally, this Smalltalk fib runs much slower than a Factor fib, because of Smalltalk return semantics; I discuss the problem below as well as my planned solution to eliminate the overhead.

In theory, there is a simple mapping from Smalltalk to Factor:

• A Smalltalk class can be a Factor tuple class. Since ivars are pre-declared, the performance complications that Ruby and Python implementations must deal with are avoided.
• Every Smalltalk selector can map into a Factor generic word; all selectors will be defined in a single vocabulary.
• Every Smalltalk method can correspond to a Factor method on the selector's generic word, specializing on the class in question.
• Smalltalk local variables can be translated to Factor's locals. Again, Smalltalk has pretty static scoping semantics, and the fact that locals are pre-declared maps very well onto Factor's model.
• Smalltalk blocks can map onto Factor quotations.
• Non-local returns can be implemented using continuations.

I threw together a simple compiler on the car ride back from Chicago to Minneapolis (no, I wasn't the one driving). The compiler takes a Smalltalk AST as input and produces a Factor quotation. The AST is pretty simple:

SINGLETONS: nil self super ;

TUPLE: ast-comment { string string } ;
TUPLE: ast-block { arguments array } { temporaries array } { body array } ;
TUPLE: ast-message-send receiver { selector string } { arguments array } ;
TUPLE: ast-message { selector string } { arguments array } ;
TUPLE: ast-cascade receiver { messages array } ;
TUPLE: ast-name { name string } ;
TUPLE: ast-return value ;
TUPLE: ast-assignment { name ast-name } value ;
TUPLE: ast-local-variables { names array } ;
TUPLE: ast-method { name string } { body ast-block } ;
TUPLE: ast-class { name string } { superclass string } { ivars array } { methods array } ;
TUPLE: ast-foreign { class string } { name string } ;
TUPLE: ast-sequence { temporaries array } { body array } ;

The parser took more effort. I used Chris Double's PEG library to implement it, and followed the grammar from Smalltalk in one page as a guide. The grammar required some restructuring to parse with PEGs because of how the "ordered choice" works. Also sorting out some more obscure details such as message cacades took some experimentation with Squeak and back-and-forth on the PEG grammar. Contrary to popular belief, while Smalltalk has a relatively simple syntax, but its not as simple as Lisp or Forth.

Here is the finished PEG parser for Smalltalk. Most of the file is written in the PEG EBNF DSL (acronym soup!). There are bits of Factor here and there to construct ASTs.

One place I had to improvise was the syntax to define classes and methods. In traditional Smalltalk 80, there's no real concrete syntax for these definitions at all, since they're entered as distinct entities in the graphical browser. I invented a silly syntax which doesn't fit very well with the rest of the grammar; I might change it later.

Once I had the parser and compiler going, I threw together a simple real/eval/print loop and did more testing. Basic features work and there's a small set of built-in Smalltalk selectors mapped onto Factor words. What remains to be done? Quite a lot:

• Class methods and metaclasses.
• Adding methods to existing Smalltalk classes.
• Implementing super.
• More built-in selectors need to be provided.

All of the first three are easy to map to Factor features, and the last one is just busy-work.

The one language feature that doesn't translate so well is Smalltalk's non-local return. I convert usages of this feature into continuations, which are slow relative to how non-local returns are implemented in production Smalltalk VMs. Usages of continuations which are downward-only need to be optimized. A speedup here would make Factor's exception handling faster too, so it would be very valuable overall.

Because Smalltalk selectors are Factor generic words, and Smalltalk classes are Factor classes, Factor's optimizer can work its magic on Smalltalk code, which is nice. I have plans to speed up Factor's downward continuations and implement inline caching for Factor generic words, and this will directly benefit the Smalltalk implementation too.

Since this implementation is just a demo, I consider it mostly done, but I'll keep hacking on it from time to time. I don't intend to turn it into a serious Smalltalk implementation, but it would be great if someone else took over and did so.

It weighs in at only 1217 lines of code, and that includes 423 lines of unit tests. I'm not sure exactly how much time I spent on it, but I'm guessing around 24 hours in total over the last week, and the bulk of that was tweaking the parser to parse various odd syntax. In particular, the AST to Factor compiler was very easy to write.

So the moral of the story is that implementation-wise, Factor is a modern VM which has a lot of the features that scripting language people wish they had, and plan on implementing sometime next year. It is also very easy to target languages to Factor by parsing them with our PEG library and compiling the AST down to Factor quotations which are handed off to the optimizing compiler. If you want to experiment with language design but don't want to spend five years implementing a language like we did, you should consider using an existing system to host your language on, and Factor is one of several great choices in this regard.

Better static safety for higher-order code

Recently Daniel Ehrenberg and I implemented a new language feature which speeds up code calling that calls quotations which the compiler cannot inline.

Thew new language feature takes the form of syntax which is based on the call and execute words from the kernel vocabulary. These words call and execute a quotation, respectively. The new syntax allows for a stack effect declaration to be made at the call site. Suppose you have a hashtable of quotations in the dynamic variable foo, and you want to call the quotation stored at a given key. The traditional way is to use the call word:

"A key" foo get at call

Using the new call( syntax, you can call it but also assert that the quotation has a certain stack effect. For example,

"A key" foo get at call( a -- b )

The execute( syntax generalizes execute in a similar way. For example, here is some code from the parser which invokes parsing words. First it checks that the word was not defined in the same file (because if it was, it wouldn't be compiled yet); then it executes it using execute( to ensure it has exactly one input and one output:

ERROR: staging-violation word ;

: execute-parsing ( accum word -- accum )
    dup changed-definitions get key? [ staging-violation ] when
    execute( accum -- accum ) ;

The basic idea is that the code that uses call( and execute( is statically checked to ensure that the right number of parameters are passed around between words; and at runtime, the actual quotation or word is checked and if its stack effect is not what the code assumed statically, an error is thrown.

The call( and execute( words are parsing words which call parse-effect to read a stack effect object. This is the same underlying facility that the ( word uses. After parsing an effect, call( and execute( are transformed into calls to call-effect and execute-effect. So the following,

"A key" foo get at call( a -- b )

parses as, and is equivalent to

"A key" foo get at (( a -- b )) call-effect

Where call-effect should be thought of as "call a quotation with this effect".

These words complement call and execute. The call and execute words benefit from the compiler's lambda lifting optimization. If a literal quotation, the result of curry and compose, or a word, is only ever passed "downward", then the compiler will inline it at the call site of call and execute, effectively converting your program into a first-order program. This means that all kinds of iteration patterns become simple loops. Even if the iteration combinators are expressed as compositions of higher-order functions, where the quotation might be passed between several words and be operated on with curry and compose, things still work out pretty well.

However, not all code is first-order, and call( and execute( allow more code to be written in a style where Factor's stack checker can infer the stack effect. Whereas before, some 80% of the words in the library would have an inferred stack effect, now the figure is closer to 100%, after introducing the new language feature and refactoring code to use it.

The concept of compiler warnings always confused Factor beginners. In Factor, a compiler warning indicates that the compiler was unable to infer the stack effect of a word; this inhibits most optimizations because no assumptions about the positions of values on the stack can be made. So if you care about the performance of your code, it was good to write it in a way such that the stack effect would infer, but it wasn't possible to write code like this in all situations. Now it is, and compiler warnings are very rare; loading the Furnace web framework now produces less than 10 whereas before it would be a few hundred.

The implementation is pretty interesting. The call( parsing word expands into a call to the call-effect macro. The macro expects that the stack effect is a literal compile-time value. The macro expansion is specialized for calling a quotation with this effect. The quotation itself is only known at runtime, and so the code generated by the macro receives it as a parameter. It uses three strategies:

• Inline cache hit: If the quotation is the same as last time, call it without any further runtime checks using the call-effect-unsafe primitive.
• Inline cache miss: If the quotation is different from last time, then it checks the stack effect of the quotation against the declaration. The stack effect is computed lazily and stored in a slot in the quotation. If the declaration matches, the quotation is called using call-effect-unsafe.
• Slow case: if the quotation's stack effect cannot be inferred, a snapshot of the data stack is taken, the quotation is called, and the stack is compared to make sure the quotation didn't use more parameters than declared.

The execute( parsing word expands into a call of the execute-effect macro, which uses three similar strategies:

• Inline cache hit: If the word is the same as last time, call it without any further runtime checks using the execute-effect-unsafe primitive.
• Inline cache miss: If the word is different from last time, then it checks the stack effect of the word against the declaration. Stack effects of words are always available, because they are computed by the compiler. If the declaration matches, the quotation is called using execute-effect-unsafe.
• Slow case: if the word's stack effect is not known, then it creates a quotation with the word in it, and calls call-effect on it.

In most cases, the slow case should never be hit, and even if it is, the runtime checks are quite efficient. The inline caching ensures that if call( is used to invoke a quotation in a loop, it only has to check its effect once.

Factor is heading in an interesting direction. It generally offers more static checking and optimization than other dynamic languages. Here are the main differences; all of these things that Factor does at compile time, other dynamic languages leave until runtime:

• In Factor, calls to undefined words are parse-time errors. In most dynamic languages, a typo in a method name would not be caught until run time.
• In Factor, most code passes the stack effect checker. This means that calling a word with the wrong number of parameters is impossible.
• In Factor, most uses of higher-order functions are inlined by the compiler, and escape analysis eliminates most closure allocations. So there are less blocks being passed around at runtime, and less allocation.

However, the language is still dynamically typed; the types of values are not known until runtime (except when the compiler can infer them), and there is a lot of generic dispatch and ad-hoc polymorphism in the library.

Now call( and execute( will speed up code which cannot take advantage of the last optimization. Indeed, with inline caching, calling quotations a loop with call( is almost as fast as if everything has been inlined.

Rendering Unicode text with Pango and Cairo

I implemented a Pango backend for text rendering in the Factor UI. This means that new_ui now works on Windows and X11 (well, not quite; I have to fix an unrelated bug in the X11 backend), and so it's almost ready to merge.

My main reference for Pango was the API documentation on gnome.org. Conceptually, Pango is quite similar to Core Text, but there are some important differences I will outline below. Pango supports two primary rendering backends; Xft and Cairo. I use the Cairo backend to render to a Cairo offscreen surface, and make an OpenGL texture out of it.

Cairo offscreen surfaces and OpenGL

When I wrote the code to create an offscreen Cairo surface, and wrap the result in a Factor bitmap image object, the code turned out to look almost identical to a similar utility I cooked up for Core Graphics. So as any self-respecting programmer, I factored this duplication out into a images.memory vocabulary.

First, we have some code to allocate unmanaged memory for the bitmap data. This memory is unmanaged because Cairo (and Core Graphics) retain a pointer to it, and so it must not be moved by a GC:

: bitmap-size ( dim -- n ) product "uint" heap-size * ;

: malloc-bitmap-data ( dim -- alien ) bitmap-size 1 calloc &free ;

Note that destructors are used to ensure the memory is deallocated later. Now, we have some code copy data out of the unmanaged memory and into a Factor byte array, and wrap it in a bitmap image object:

: bitmap-data ( alien dim -- data ) bitmap-size memory>byte-array ;

: <bitmap-image> ( alien dim -- image )
    [ bitmap-data ] keep
    <image>
        swap >>dim
        swap >>bitmap ;

Putting everything together into a combinator:

: make-memory-bitmap ( dim quot -- image )
    '[
        [ malloc-bitmap-data ] keep _ [ <bitmap-image> ] 2bi
    ] with-destructors ; inline

So the quotation receives the image dimensions and a pointer to some unmanaged memory.

On the Cairo side, I have a word to create an offscreen bitmap:

: width>stride ( width -- stride ) "uint" heap-size * ; inline

: <image-surface> ( data dim -- surface )
    [ CAIRO_FORMAT_ARGB32 ] dip first2 over width>stride
    cairo_image_surface_create_for_data
    dup check-surface ;

: <cairo> ( surface -- cairo ) cairo_create dup check-cairo ; inline

And then I use make-memory-image together with this word to define a new make-bitmap-image combinator:

: make-bitmap-image ( dim quot -- image )
    '[
        <image-surface> &cairo_surface_destroy
        <cairo> &cairo_destroy
        @
    ] make-memory-bitmap
    BGRA >>component-order ; inline

This combinator makes the Cairo binding very pleasant to use. Once Factor's image library supports some more formats -- PNG comes to mind -- it will be possible to render some graphics in a web app and serve it up as a PNG to the client. Of course Cairo can write PNGs already, so alternatively someone could write a high-level wrapper for those APIs instead.

So the Pango text backend makes Pango calls inside a make-bitmap-image, then passes the result to the OpenGL texture caching code I talked about last time.

Fixed-point and floating-point numbers

Pango uses fixed-point arithmetic for sub-pixel co-ordinates. I convert everything to and from floats when calling Pango using a pair of words:

CONSTANT: PANGO_SCALE 1024

: pango>float ( n -- x ) PANGO_SCALE /f ; inline
: float>pango ( x -- n ) PANGO_SCALE * >integer ; inline

For example, here is some code to convert a fixed-point PangoRectangle into a Factor rect type:

C-STRUCT: PangoRectangle
    { "int" "x" }
    { "int" "y" }
    { "int" "width" }
    { "int" "height" } ;

: PangoRectangle>rect ( PangoRectangle -- rect )
    [ [ PangoRectangle-x pango>float ] [ PangoRectangle-y pango>float ] bi 2array ]
    [ [ PangoRectangle-width pango>float ] [ PangoRectangle-height pango>float ] bi 2array ] bi
    <rect> ;

UTF8 strings and string offsets

The documentation for a few functions, such as pango_layout_line_x_to_index(), uses the following phrase: "the byte index for the grapheme in which the user clicked." What they really mean is the index of the first code point comprising the grapheme the user clicked, inside the UTF8-encoded string that you passed in when creating the layout.

This works well in languages such as C and Ruby 1.8 where a string is just an array of UTF8-encoded bytes, but in Factor, strings are an abstract sequence of Unicode code points with the actual internal encoding hidden from the developer. The Factor FFI takes care of encoding and decoding strings for you, but in this case, I want to convert code point indices to byte indices and this requires some work.

Consider a Unicode string such as "παν語". This string has 4 Unicode code points, so in Factor, it is a sequence of length 4. However, the UTF8 encoding of this string has 9 bytes:

π	2 bytes
α	2 bytes
ν	2 bytes
語	3 bytes

So for example, byte index 4 corresponds to string index 2. To convert from a string index to a byte index, it suffices to take the head of the string, and UTF8 encode it, and look and the byte length of the result. Going in the other direction requires building a mapping from byte indices to string indices and doing a binary search on it. Here is the Factor code:

: code-point-length ( n -- x )
    log2 {
        { [ dup 0 7 between? ] [ 1 ] }
        { [ dup 8 11 between? ] [ 2 ] }
        { [ dup 12 16 between? ] [ 3 ] }
        { [ dup 17 21 between? ] [ 4 ] }
    } cond nip ;

: code-point-offsets ( string -- indices )
    0 [ code-point-length + ] accumulate swap suffix ;

: utf8-index> ( n string -- n' )
    code-point-offsets natural-search drop ;

: >utf8-index ( n string -- n' )
    code-point-offsets nth ;

Note that code-point-length could've been written as 1string utf8 encode length, but this implementation is slightly more efficient.

Font descriptions

Pango has a pretty elaborate set of APIs for working with fonts. At this point, I only need the bare minimum, so I'm working with the PangoFontDescription type. Font descriptions are allocated and deallocated using a pair of functions:

FUNCTION: PangoFontDescription*
pango_font_description_new ( ) ;

FUNCTION: void
pango_font_description_free ( PangoFontDescription* desc ) ;

DESTRUCTOR: pango_font_description_free

Unlike Core Text, which uses Apple's Core Foundation for memory management and thus every object is reference counted with CFRetain() and CFRelease() functions used to manage the reference count, Pango takes a more ad-hoc approach. Some objects are reference counted using GLib's gobject support, others have their own refcounting, and others still just have a deallocation function without a reference count.

Here is some code to create a PangoFontDescription from a Factor font instance:

MEMO: (cache-font-description) ( font -- description )
    [
        [ pango_font_description_new |pango_font_description_free ] dip {
            [ name>> pango_font_description_set_family ]
            [ size>> float>pango pango_font_description_set_size ]
            [ bold?>> PANGO_WEIGHT_BOLD PANGO_WEIGHT_NORMAL ? pango_font_description_set_weight ]
            [ italic?>> PANGO_STYLE_ITALIC PANGO_STYLE_NORMAL ? pango_font_description_set_style ]
            [ drop ]
        } 2cleave
    ] with-destructors ;

: cache-font-description ( font -- description )
    strip-font-colors (cache-font-description) ;

Some things to note about the above code:

• I'm using memoization to cache font descriptions
• I use an on-error destructor (|foo) to ensure that the font description is deallocated if anything inside the block fails
• Since Factor font instances store foreground and background colors, whereas Pango font descriptions do not, I don't want to pollute the cache with lots of duplicates where only the keys differ in color, so I strip the colors out first.
• Just like Core Text, Pango offers a lot more functionality than Factor's font objects can represent. I will look into exposing more of this functionality in a cross-platform manner over time.

Unlike Core Text, where font objects can be interrogated for metrics information, Pango's support for font metrics seems pretty simple in comparison; only getting the ascent and descent is supported, and the values reported here don't seem to match the text as it is actually rendered on-screen. Because of this, I only ever get metrics information from text layouts, and not from the fonts themselves, so creating font descriptions is the only thing I need to do here.

Layouts

Just as with Core Text, Pango has a data type representing a set of glyphs which have been laid out and positioned; you never draw strings directly. This recognizes the fact that glyph selection when rendering Unicode is a complex process and should be done ahead of time. Whereas in Core Text, the fundamental data type for this is the CTLine, Pango calls it a PangoLayout. Unlike Core Text, a PangoLayout can contain multiple lines of text, so it is more like a CTParagraph than a CTLine, but Factor's UI only renders single lines at a time so far.

The Pango backend uses a tuple to store the Pango layout, a bitmap rendering, and several related values:

TUPLE: layout font string layout metrics ink-rect logical-rect image disposed ;

The first step is fill in the layout slot, which stores a pointer to a PangoLayout.

Pango layouts can be created by calling pango_layout_new(), however when using the Cairo backend it is better to use pango_cairo_create_layout() instead. Once a layout has been created, you can set the text to render, and the font to render it with, by calling pango_layout_set_text() and pango_layout_set_font_description().

FUNCTION: PangoLayout*
pango_cairo_create_layout ( cairo_t* cr ) ;

FUNCTION: void
pango_layout_set_text ( PangoLayout* layout, char* text, int length ) ;

FUNCTION: void
pango_layout_set_font_description ( PangoLayout* layout, PangoFontDescription* desc ) ;

Unfortunately, pango_layout_set_text() takes a null-terminated UTF8 string, so to avoid problems if the user accidentally passes in a string containing embedded nulls, I substitute all nulls for a zero-width non-breaking space.

Here is the Factor code to create a Pango layout and set the text and font:

: set-layout-font ( font layout -- )
    swap cache-font-description pango_layout_set_font_description ;

: set-layout-text ( str layout -- )
    #! Replace nulls with something else since Pango uses null-terminated
    #! strings
    swap
    dup selection? [ string>> ] when
    { { 0 CHAR: zero-width-no-break-space } } substitute
    -1 pango_layout_set_text ;

: <PangoLayout> ( text font -- layout )
    dummy-cairo pango_cairo_create_layout |g_object_unref
    [ set-layout-font ] keep
    [ set-layout-text ] keep ;

Font metrics

Last time I blogged about how Core Text makes a distinction between image bounds and metric bounds. A similar situation exists in Pango; they're called ink and logical bounds. To get both bounds from a layout, use the pango_layout_get_extents() function.

FUNCTION: void
pango_layout_get_extents ( PangoLayout* layout, PangoRectangle* ink_rect, PangoRectangle* logical_rect ) ;

I showed the code to convert a PangoRectangle into a Factor rect above.

To compute the ascent and descent, it suffices to compute one of them, since their sum is the height of the logical bounds. Since a Pango layout can contain multiple lines, getting a baseline involves getting an iterator, which iterates over lines, first.

FUNCTION: PangoLayoutIter*
pango_layout_get_iter ( PangoLayout* layout ) ;

Now, the baseline of the first line can be obtained from the iterator:

FUNCTION: int
pango_layout_iter_get_baseline ( PangoLayoutIter* iter ) ;

Iterators must be deallocated using a special function.

FUNCTION: void
pango_layout_iter_free ( PangoLayoutIter* iter ) ;

Here is the Factor code that puts it all together:

: layout-baseline ( layout -- baseline )
    pango_layout_get_iter &pango_layout_iter_free
    pango_layout_iter_get_baseline
    pango>float ;

Since I only ever create single-line layouts, the descent is easy to compute; it is the height of the logical bounds minus the ascent.

The other two relevant metrics are the x-height and cap-height metrics that I talked about in an earlier post. Pango doesn't provide a way to get these from the font itself, so I just measure them by hand:

: glyph-height ( font string -- y )
    swap <PangoLayout> &g_object_unref layout-extents drop dim>> second ;

MEMO: missing-font-metrics ( font -- metrics )
    #! Pango doesn't provide x-height and cap-height but Core Text does, so we
    #! simulate them on Pango.
    [
        [ metrics new ] dip
        cache-font-description
        [ "x" glyph-height >>x-height ]
        [ "Y" glyph-height >>cap-height ] bi
    ] with-destructors ;

Rendering a layout

There are several steps involved in rendering text to a bitmap:

• Filling the background with the background color
• Filling the selection rectangle, if one is set
• Setting the foreground color
• Setting the text position
• Rendering the text layout

The only interesting part is setting the text position. In Core Text, text is drawn with the intersection of the baseline and the caret at the origin. Pango works differently here; the origin is the top-left corner of the text's logical bounds. Here is a screenshot illustrating the ink and logical bounds:

So we want to position the text so that the upper-left corner is at the origin relative to the logical bounds. Here is the Factor code to subtract the logical origin from the image origin:

: text-position ( layout -- loc )
    [ logical-rect>> ] [ ink-rect>> ] bi [ loc>> ] bi@ v- ;

: set-text-position ( cr loc -- )
    first2 cairo_move_to ;

Conclusion

Implementing Unicode text rendering via Core Text and Pango (and putting a cross-platform abstraction layer on top) was a fair amount of work, but now I've achieved one of my big goals for Factor 1.0, Unicode text rendering. There are still a few missing details before the Factor UI is truly Unicode-perfect, but this is an important step. Along with Daniel Ehrenberg's Unicode vocabulary and the large number of I/O encodings supported, Factor's Unicode support is better than most other languages, especially non-mainstream ones, and that is quite an accomplishment for a small team and a few years of work.

Metric bounds versus image bounds

With some fonts, the font glyphs exceed the font metric bounds. I wasn't aware of this fact until recently, and because of this some text would be chopped off at the edges.

The right way to do things is to compute the image bounds of the text and use that for creating the OpenGL texture, only using metric bounds to actually position the text.

To compute image bounds with Core Text, you're meant to use CTLineGetImageBounds(), but this function takes a CTLine as well as a CGContext, which creates a bit of a chicken and egg problem, because I need the image bounds to create the context. The solution I came up with is to keep a dummy 1x1 pixel bitmap context around globally and use that for text measurement.

Getting the text position right was a bit tricky; I must thank Joe Groff for helping me get this right.

Now, CTLineGetImageBounds() returns a rectangle. The origin of the rectangle is the point at the intersection of the baseline and the caret, and the dimension is the size of the glyphs. So the texture size should be the size of the rectangle (with appropriate rounding to ensure your texture has integral dimension).

Inside the texture, the text position should be set to the negation of the image bounds origin, by calling CGContextSetTextPosition. The text position is relative to the CGContext's text co-ordinate system, which has the origin at the bottom-left corner by default.

Now, once you've rendered the texture, you need to compute the texture position. Factor's UI uses a co-ordinate system where the origin is the top-left corner. Suppose you want to diplay the text such that the baseline is at (0,ascent) where ascent is the font ascent, and the image bounds are im.{x,y,w,h}. Then the texture quad should be positioned at (im.x,ascent - im.h - im.y).

I glossed over the details of rounding the texture dimensions and texture position to integral co-ordinates; this is important and a bit tricky to get right, but you can look at the code after I merge it in.

After some pixel tweaking, everything works now. In the below screenshot, I've created an editor gadget that displays text with the Zapfino font, and set a one-pixel black border around it. Also note that the text selection and caret positioning doesn't mess up ligatures.