Friday, March 20, 2009

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.

Tuesday, March 03, 2009

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.

Friday, February 20, 2009

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.

Thursday, February 19, 2009

A note about libdl functions on NetBSD and the "Service unavailable" error

On NetBSD, dlopen(), dlsym(), dlerror() and other such functions are implemented as stubs in libc, and the stubs just return an error, "Service unavailable". The ELF loader patches references to these symbols inside binaries to point at the real definitions. Trouble is, if you look up one of these symbols at runtime using dlsym() itself, it will return the address of the stub function and not the correct definition.

So amusingly enough, this won't work in Factor on NetBSD:
FUNCTION: void* dlopen ( char* path, int flags ) ;
"libX11.so" dlopen .

Of course you'd never do the above, but it can come up legitimately if you try calling dlerror() via FFI and expect to get a useful error message for the most recent failed dynamic linker operation. Instead, you'll always get the undescriptive "Service unavailable".

Tuesday, February 17, 2009

Font metrics and baseline alignment

I implemented some algorithms for horizontally positioning text and graphics within lines in an aesthetically-pleasing manner. Until now, the Factor UI did all font rendering with FreeType and only really supports a small, fixed set of fonts, all from the Bitstream Vera family, which I bundle with Factor. These fonts have similar metrics and baselines and so the UI layout issues I describe below were not as severe, but were still noticable. Now that Factor is doing native font rendering on Mac OS X with Core Text, and soon Pango on X11 and Windows, I decided to address these issues properly instead of hacking around them. Doing so involved implementing some new layout algorithms and abstractions in the Factor UI.

This blog post is a continuation of my previous entry on texture caching; now that the technical details of rendering are done, its time to make the result look good.

I tried to make reasonable diagrams to illustrate some of the concepts here, but I didn't try too hard, and this is by no means an authoritative account of the topic. It is just a brain dump of my incomplete understanding of the subject.

Identifying the problem


Suppose you want to position some gadgets next to each other, but they use different fonts. If you use a shelf parent with default settings, you get something like this, which looks terrible, because the text does not line up:

In this particular case you can change the alignment of the shelf so that gadgets are aligned relative to the bottom edge instead of the top, by setting the align slot to 1, instead of the default of 0:

This happens to fix the above case, but now this will look stupid if one of the fonts has a bigger point size than the other:

Here is another example. We have two gadgets side by side, where the second one has a border around it. Notice that the two pieces of text don't look right next to each other; the second one looks a few pixels "off".

Clearly, a simplistic alignment strategy, where a single constant determines where each child is positioned in between the top and bottom edge, is insufficient for text. Instead, we have to look at the fonts being used and different measurements used by those fonts to make the above examples look right.

Font metrics


When text is rendered, the bottom of each glyph is aligned along a baseline. This is like the lines on note paper, but of course it's invisible. Some letters, like lowercase "j" in most fonts, will descend below the baseline.

In addition to the font's point size, and its height, there are a number of additional metrics which are important. They are,
  • The ascent, which is the distance from the baseline to the top edge of the tallest glyph.
  • The descent, which is the distance from the baseline to the bottom edge of the tallest glyph. Sometimes, the descent is taken to be a negative value, but I don't use this convention in Factor's code since Core Text doesn't either.
  • The x height, which is the height of a lower-case x.
  • The cap height, which is the cap height of an upper case Y.
  • The font height is just the sum of the ascent and descent.
  • The leading, which is the gap between lines of text.
  • The line height is ascent + descent + leading.
  • The em, which is the width of a lower-case m.
  • The en, which is half an em.

Here is a diagram showing some of the above:

To understand why the previous examples look bad, let's make the baselines and borders visible:

Notice that the baselines of the two gadgets don't line up. If they lined up, the result would look nice.

Baseline alignment


I added support for baseline alignment to shelf gadgets; you set the align slot to the special symbol +baseline+. Setting it to a number between 0 and 1 is still supported, and setting it to +baseline+ activates totally different logic in the implementation.

Two things change when a shelf has baseline alignment enabled; the preferred size calculation, the layout algorithm itself.

If a shelf does not have baseline alignment, then its preferred height is just the maximum of the preferred heights of all of its children. This no longer works with baseline alignment. For example, consider the case where two gadgets with different baselines are nested inside a shelf:

Clearly, the preferred height of the shelf exceeds the maximum of the heights of the two gadgets. Here is a pseudo-code algorithm for computing the height:
For every gadget g in the shelf,
set ascent[g] = b.baseline
set descent[g] = g.height - g.baseline

max_ascent = maximum(ascent)
max_descent = maximum(descent)

height = max_ascent + max_descent

The algorithm for layout is similar:
For every gadget g in the shelf,
set ascent[g] = b.baseline
set descent[g] = g.height - g.baseline

max_ascent = maximum(ascent)
max_descent = maximum(descent)

For every gadget g in the shelf,
set g.y = max_ascent - g.baseline

Note that if every gadget in the shelf has a baseline equal to its height, the descent will always be zero and the above algorithms degenerate to the standard shelf layout algorithm with align = 1.

Graphics baseline alignment


For lines containing a mix of text and graphics, where the graphics are icons with similar height to the text, I came up with a nice trick for positioning them in a pleasing manner. Trying to use the standard alignment for icons and text doesn't work; here are three different layouts, with alignment of 0, 1/2, and 1, respectively:

Note that I increased the font size to make the effect more noticable, but even at smaller font sizes that are closer to the icon size, the results look less than ideal. Using baseline alignment where the baseline of the image is equal to its height doesn't produce the right results either.

The trick with images, then, is to define a "graphics baseline" that runs horizontally at the y co-ordinate equal to half of the image's height. For text, the graphics baseline runs half-way between the cap height and baseline. Here is what it looks like:

Generalizing the algorithm in the previous section to support a graphics baseline is easy.

First, we allow the baseline and cap-height of a gadget to be set to some unspecified value, distinct from any number. This indicates that graphics baseline alignment should be used for this gadget.

Then, we compute layout for the text children first, followed by the graphics children, and position the graphics children so that their graphics baseline lines up with half of the cap height from the text children.

I can't be bothered writing out pseudocode; you can look at the Factor implementation after its checked in if you're interested.

Font metrics implementation


The fonts vocabulary now defines a metrics tuple:
TUPLE: metrics width ascent descent height leading cap-height x-height ;

Various words in the UI output metrics tuples:
  • font-metrics ( font -- metrics )
  • line-metrics ( font string -- metrics )

The Core Text implementation of these is completely trivial, since the required information can be obtained by a series of API calls, and I expect the eventual Pango implementation to be similar.

Baseline alignment implementation


The ui.baseline-alignment vocabulary contains all the code. To start with, it needs to be able to get the baseline and cap height for a gadget:
GENERIC: baseline ( gadget -- y )

M: gadget baseline drop f ;

GENERIC: cap-height ( gadget -- y )

M: gadget cap-height drop f ;

The default implementations return f for both, which means the graphics baseline will be used.

I implemented a generalized version of this algorithm as the measure-metrics word in the ui.baseline-alignment vocabulary. It outputs the new ascent and descent, and adding them together gives the height of the shelf.

Labels implement these generic words in the obvious way, by looking up font metrics. Borders, packs, paragraphs and other compound gadgets implement these operations by computing the baseline and cap height of their children and combining them in various ways.

The UI tries to use baseline alignment by default in as many places as it makes sense, so in most cases you do not need to worry about the details of this.

Here is some help text rendering demonstrating the text baseline alignment in the values table and the description paragraph:

The astute observer will notice the table lines are missing a pixel in the bottom-right corner; this is a recent regression that I need to look into.

Here is an example demonstrating baseline alignment of a text label with a text field next to it, as well as graphics baseline alignment, with checkboxes and radio buttons:

More about font metrics


I haven't talked about line spacing yet, because this part is tricky. There's more to it than just adding the leading between each line. I'll figure it out in the near future and do a write-up most likely.

Sunday, February 15, 2009

Implementing OpenGL texture caching and bitmap image support in the Factor UI

Last time, I talked about how I implemented Unicode text rendering using Apple's Core Text API. In this blog entry I'll discuss some implementation details I omitted last time, and I'll also talk about a new feature I added a few days ago to the new_ui branch: support for bitmap images.

Note that Core Text is OS X-specific, and Factor will only use it on that platform; on other platforms, it will use Pango to render text (and maybe Uniscribe on Windows, leaving Pango for X11 only). The image support is cross-platform and indeed is entirely written in Factor.

A general cache abstraction


With Core Text, you never operate on strings of text directly, instead you construct a CTLine object and interrogate it for metrics, or ask it to render itself to a Core Graphics context. To avoid constructing CTLines over and over again, and to expose a straightforward API that only involves strings, the UI caches the CTLine objects. Using MEMO: or the cache combinator with a hashtable is insufficient here, since I don't want to retain every CTLine forever. Instead, I want each CTLine to be disposed and removed from the cache if it is not used for a fixed period of time.

To handle this use case, along with another one that I describe later on in this post, I implemented a simple cache abstraction.

The new cache vocabulary defines a new assoc type which wraps an existing assoc, and has a single configuration parameter, max-age:
TUPLE: cache-assoc assoc max-age disposed ;

: <cache-assoc> ( -- cache )
H{ } clone 10 f cache-assoc boa ;

INSTANCE: cache-assoc assoc

The values in the underlying assoc are all instances of cache-value:
TUPLE: cache-entry value age ;

: <cache-entry> ( value -- entry ) 0 cache-entry boa ; inline

The age of a value starts at zero, and is incremented at fixed intervals. Whenever a key is looked up in the cache, the age is reset to zero. Because I don't want to expose the user of a cache to these cache-entry tuples (they're just implementation detail), the cache-assoc type implements at* to unwrap the cache entry before returning the value to the user. Also note that I reset the age here:
M: cache-assoc at* assoc>> at* [ dup [ 0 >>age value>> ] when ] dip ;

Storing an entry into the cache first checks to see if the cache has been disposed of yet or not, and then wraps the value in a cache entry before passing it down to the underlying assoc:
M: cache-assoc set-at
[ check-disposed ] keep
[ <cache-entry> ] 2dip
assoc>> set-at ;

Converting a cache to an alist unwraps each value:
M: cache-assoc >alist assoc>> [ value>> ] { } assoc-map-as ;

The remaining important assoc methods simply delegate to the underlying assoc:
M: cache-assoc assoc-size assoc>> assoc-size ;

M: cache-assoc clear-assoc assoc>> clear-assoc ;

Caches also support one additional operation: disposal. When you call dispose on a cache, all values in the cache are disposed and the cache cannot be used again:
M: cache-entry dispose value>> dispose ;

M: cache-assoc dispose*
[ values dispose-each ] [ clear-assoc ] bi ;

This is the important part, that makes caches useful for managing external resources such as OpenGL textures.

Now, here is a word which ages each entry, and deletes those entries whose age exceeds the cache's max-age slot value. It uses the assoc-partition combinator, which splits an assoc into two, sorting key/value pairs based on whether they satisfy a predicate or not.
: purge-cache ( cache -- )
dup max-age>> '[
[ nip [ 1+ ] change-age age>> _ >= ] assoc-partition
[ values dispose-each ] dip
] change-assoc drop ;

I cheat a little here; because assoc-partition iterates over all key/value pairs exactly once, I can perform side effects in the predicate quotation; I increment the age and then immediately check if it exceeds the maximum. Note the use of '[ syntax with the _ directive, which places the max-age exactly where its needed without having to pass it around on the stack explicitly. The values which exceed the maximum age -- these make up the first return value of assoc-partition -- are all disposed of.

This cache vocabulary, which is currently in the new_ui branch and will be merged into the trunk soon, demonstrates the Factor equivalent of the "decorator" OO design pattern.

Images


Doug Coleman has been working on a Factor library for working with bitmap images for quite some time; you can find it in the repository, in the images vocabulary. Recently it received a major facelift, as well as support for TIFF images (including LZW compression) in addition to Windows BMP. All of this is written entirely in Factor, and Doug also plans on supporting PNG, GIF and JPEG images, also with pure Factor code. When complete, this library will be quite a showcase for implementing complex algorithms in a concatenative language.

Also, Joe Groff designed some nice icons for the Factor UI. To make use of both of these great contributions, I wrote some code which caches images in OpenGL textures and renders these textures.

The load-image word in the images.loader vocabulary defines a data type for images:
TUPLE: image dim component-order bitmap ;

The component-order slot is one of a series of singletons,
SINGLETONS: BGR RGB BGRA RGBA ABGR ARGB RGBX XRGB BGRX XBGR
R16G16B16 R32G32B32 R16G16B16A16 R32G32B32A32 ;

the dim slot is a pair of integers (the width and the height) and the bitmap slot is a byte array with the image data, where each pixel's size and format is determined by component-order.

OpenGL textures


In my last blog post, I showed some ad-hoc code for rendering a Core Graphics bitmap to a texture. I refactored this code to be independent of Core Graphics and Core Text, and put it in the opengl.textures vocabulary. There is a new texture data type:
TUPLE: texture texture display-list disposed ;

To create a texture from an image, I have to pass a format and a type to OpenGL. A generic word maps component order singletons into OpenGL constants; the implementation is incomplete, but it suffices for now:
GENERIC: component-order>format ( component-order -- format type )

M: RGBA component-order>format drop GL_RGBA GL_UNSIGNED_BYTE ;
M: ARGB component-order>format drop GL_BGRA_EXT GL_UNSIGNED_INT_8_8_8_8_REV ;
M: BGRA component-order>format drop GL_BGRA_EXT GL_UNSIGNED_INT_8_8_8_8 ;

Using this word, I implemented a <texture> constructor word, which creates an OpenGL texture from a bitmap image, and wraps the relevant data into a tuple:
: <texture> ( image -- texture )
[
[ dim>> ]
[ bitmap>> ]
[ component-order>> component-order>format ]
tri make-texture
] [ dim>> ] bi
over make-texture-display-list f texture boa ;

The code that wraps the glTexImage2D call, as well as creating a display list that renders a textured quad, is very similar to what I showed in my previous post, just slightly more general, so I won't reproduce it here.

To be useful cache keys, textures must be disposable:
M: texture dispose*
[ texture>> delete-texture ]
[ display-list>> delete-dlist ] bi ;

High-level abstraction for images


The ui.images vocabulary builds on top of the lower-level libraries: images, images.loader, opengl.textures and to provide an easy-to-use, simple, high-level interface for displaying icons in the UI.

The relevant data type is an image path, which is just a string wrapped in a tuple,
TUPLE: image-name path ;

C: <image-name> image-name

A fundamental word takes an image path, and loads the image that it names, if it has not been loaded already:
MEMO: cached-image ( image-name -- image ) path>> load-image ;

Note that I'm not using a cache-assoc to cache the bitmaps themselves. This is because bitmaps are objects in the Factor heap, not external resources, and so they don't have a dispose method, hence a simple MEMO: word suffices.

The next step is implementing the image texture cache. I added a new images slot to world gadgets. A world is the top-level gadget inside a native OS window, and since each world has its own OpenGL context, it is natural to associate the image texture cache with a world.
<PRIVATE

: image-texture-cache ( world -- texture-cache )
[ [ <cache-assoc> ] unless* ] change-images images>> ;

PRIVATE>

The image-texture-cache word assumes that there is a dynamically-scoped variable named world holding a world gadget. This is the case inside the dynamic extent of the draw-gadget word, and so textures can only be cached and looked up while a gadget is being rendered; a reasonable restriction.

The rendered-image word looks up a bitmap image texture in the cache, and adds it if its not already present:
: rendered-image ( path -- texture )
world get image-texture-cache [ cached-image <texture> ] cache ;

Note the two levels of caching here. First, it looks for an available texture associated with an image path. If there is no texture, it looks for a cached bitmap image and makes a texture from that. If there is no cached bitmap image, then cached-image loads it by calling load-image inside images.loader.

Now, drawing an image named by an image path is easy; this word draws the image at the origin, and code which wants to draw it at another position can simply translate the model view matrix first:
: draw-image ( image-name -- )
rendered-image display-list>> glCallList ;

Getting cached image dimensions is easy too, and does not involve the texture cache, only the bitmap cache:
: image-dim ( image-name -- dim )
cached-image dim>> ;

Caching rendered Core Text lines


In the last post, I presented the with-bitmap-context combinator in the core-graphics vocabulary which created a Core Graphics bitmap context, rendered to it by calling a quotation, and output a byte array when finished. I refactored this combinator and renamed it to make-bitmap-image. Instead of outputting a raw byte array, it creates an image tuple, which wraps the byte array together with dimensions and a component order. This means that anyone who doesn't care about portability and wishes to use the core-graphics vocabulary directly can do so very easily, and render graphics to an image object which works with a number of other Factor libraries.

Indeed, by changing the core-text code to call make-bitmap-image, I was able to very easily hook up texture caching for rendered lines of text.
: rendered-line ( font string -- texture )
world get text-handle>> [ cached-line image>> <texture> ] 2cache ;

M: core-text-renderer draw-string ( font string -- )
rendered-line display-list>> glCallList ;

Again, the user benefits because they don't have to concern themselves with "lines" (strings with layout) or GL textures; they just draw strings whenever and everything works out behind the scenes.

On code re-use


I'm a big fan of avoiding redundant data types in the Factor library. Over the years, parts of the Factor UI which were UI-specific have been split off, cleaned up and generalized. We now have some very nice vocabularies, such as colors, fonts and images which do not depend on OpenGL or the UI, and are hopefully general enough that no Factor programmer will have to re-invent the concepts of fonts, colors and bitmap images again.

Also, as much as possible of the Factor UI's rendering code is now abstracted off into sub-vocabularies of the opengl vocabulary; these define many utility words and types, and for instance something like opengl.textures can be used independently of the Factor UI, if you're doing OpenGL rendering with some other toolkit.

The introduction of the cache-assoc abstraction and generalized texture caching and bitmaps has simplified the Core Text text rendering backend considerably. It is now only a couple of hundred lines of code. This will make implementing a Pango backend easier.

Icons for definitions


To spruce up Factor's vocabulary browser and code completion, I cooked up a little vocabulary which, given a word or vocabulary, outputs an appropriate icon. For words, there are many types of icons corresponding to different types of words, and for vocabularies the icons distinguish loaded, unloaded and runnable vocabs.

The definitions.icons vocabulary defines a generic word:
GENERIC: definition-icon ( definition -- path )

Since all the icons are in a single directory, and in TIFF format, I define a utility word which takes an icon file name without the extension and outputs a full pathname:
: definition-icon-path ( string -- string' )
"resource:basis/definitions/icons/" prepend-path ".tiff" append ;

Now, I'd want to define a bunch of methods,
M: predicate-class definition-icon drop "class-predicate-word" definition-icon-path ;
M: generic definition-icon drop "generic-word" definition-icon-path ;
M: macro definition-icon drop "macro-word" definition-icon-path ;
...

However this is too verbose. The only really important part of each method line is the class name, and the icon name, without quotes. Everything else is boilerplate. Well, this is Factor, and we can factor it out. There are many different ways to do this. You can write a parsing word, or you can use my "functor" hack, which is just a syntax sugar for a particularly simple class of parsing words. Here is a solution using parsing words:
<<

: ICON:
scan-word \ definition-icon create-method
scan '[ drop _ definition-icon-path ]
define ; parsing

>>

And here is a solution using functors:
<<

FUNCTOR: define-icon ( class icon -- ) WHERE
M: class definition-icon drop icon definition-icon-path ;
;FUNCTOR

: ICON: scan-word scan define-icon ; parsing

>>

The functor actually expands into code that is very similar to the parsing word. Both are straightforward. The main difference is that the parsing word has to explicitly call the run-time equivalents of M:; create-method and define.

Note that I wrap the parsing word in a compilation unit << ... >> so that it is compiled before the other words in the file. This allows the parsing word to be used in the same file where it is defined; otherwise usages of ICON: would attempt to call a parsing word that wasn't compiled yet, which throws an error.

Now new icons are very easy to define,
ICON: predicate-class class-predicate-word
ICON: generic generic-word
ICON: macro macro-word
ICON: parsing-word parsing-word
ICON: primitive primitive-word
ICON: symbol symbol-word
ICON: constant constant-word
ICON: word normal-word
ICON: vocab-link unopen-vocab

For vocabularies, the situation is simpler,
M: vocab definition-icon
vocab-main "runnable-vocab" "open-vocab" ? definition-icon-path ;

Thursday, January 29, 2009

Rendering Unicode text to an OpenGL texture using Mac OS X CoreText

This post is really a follow-up to my previous post where I bragged about Factor supporting Unicode font rendering on Mac OS X. After writing that post I realized that there is not much information online about the particular use-case I implemented: rendering text to an offscreen bitmap context, and then making it into an OpenGL texture. So I decided to write up a blog post collecting the gory details in one place. This information should be useful to programmers who use any language on Mac OS X, but all the code examples are in Factor.

The code examples below are not self-contained; they use the FFI bindings I defined in the core-graphics and core-text vocabularies in the new_ui branch in the Factor GIT repository. Factor's FFI is very easy to use, for example here are some Core Graphics functions:
FUNCTION: CGContextRef CGBitmapContextCreate (
void* data,
size_t width,
size_t height,
size_t bitsPerComponent,
size_t bytesPerRow,
CGColorSpaceRef colorspace,
CGBitmapInfo bitmapInfo
) ;

FUNCTION: void CGContextSetRGBFillColor (
CGContextRef c,
CGFloat red,
CGFloat green,
CGFloat blue,
CGFloat alpha
) ;

Once the FFI bindings are in place, a lot of higher-level wrapper code has to be written, because these are low-level, C APIs. The first step is creating a bitmap context; after that, I'll discuss creating the various Core Text data types and rendering strings to a bitmap context. Finally, I'll discuss creating an OpenGL texture from a bitmap context.

Creating a bitmap context


The first step is to create a CoreGraphics bitmap context using CGBitmapContextCreate. When creating a bitmap context, you supply a byte array to render to. There are two main caveats here.

First, the memory backing the context should not move while the context is active. This means in GC languages with copying collectors, such as Factor, you have to pin your byte array (Factor doesn't support this) or allocate it in unmanaged memory (using malloc or similar). This is of course obvious (if the GC moves the object, it has no way of notifying Core Graphics that it moved) but its something to watch out for when using an FFI from a high-level language.

The second caveat, that took me a long time to figure out, is that you have to use a specific bitmap format if you want sub-pixel font smoothing to be enabled on LCD screens. The bitmapInfo parameter to CGBitmapContextCreate specifies the format of the bitmap in memory. The code path for sub-pixel font smoothing is only used if the following two flags are set in the bitmap info:
  • kCGImageAlphaPremultipliedFirst - put the alpha component first in each quadruple
  • kCGBitmapByteOrder32Host - use native endian to pack the ARGB quads, instead of the default which seems to be big-endian.

If these two values are not passed, then sub-pixel smoothing will not be enabled even if the user is using an LCD monitor and has requested that it be performed.

Below is the Factor code for creating a bitmap context, with some comments.

First, we make a word which constructs the flags mentioned above:
<PRIVATE

: bitmap-flags ( -- flags )
{ kCGImageAlphaPremultipliedFirst kCGBitmapByteOrder32Host } flags ;

Now, a word to compute the size of the bitmap in memory. This is used twice, when malloc'ing the bitmap, and after rendering, when copying it back to managed memory:
: bitmap-size ( dim -- n )
product "uint" heap-size * ;

Now, a word to malloc the bitmap. We add it the innermost destructor scope using &free; this ensures its deallocated when we're done with it, either after successfully rendering our text, or if an error is thrown:
: malloc-bitmap-data ( dim -- alien )
bitmap-size malloc &free ;

We also have to pass a color space; the default RGB space is sufficient for my purposes, and once again we define a destructor:
: bitmap-color-space ( -- color-space )
CGColorSpaceCreateDeviceRGB &CGColorSpaceRelease ;

Now, a word which uses the above to create a context backed by unmanaged memory:
: <CGBitmapContext> ( dim -- context )
[ malloc-bitmap-data ] [ first2 8 ] [ first 4 * ] tri
bitmap-color-space bitmap-flags CGBitmapContextCreate
[ "CGBitmapContextCreate failed" throw ] unless* ;

Once we're done rendering, we have to get the bitmap data from the context and copy it to managed memory, so that we can return a byte array object to the user. This is done with the below word:
: bitmap-data ( bitmap dim -- data )
[ CGBitmapContextGetData ] [ bitmap-size ] bi*
memory>byte-array ;

PRIVATE>

This ends the implementation detail. The last word here is a high-level word that is called by other code. This word completely hides the resource allocation and deallocation by establishing a destructor scope, creating a bitmap context, calling a quotation with the bitmap context, then copying the bitmap data back to managed memory and returning a byte array. All the external resources allocated during this operation -- the memory buffer, the color space, the context -- are deallocated for us as soon as with-destructors returns:
: with-bitmap-context ( dim quot -- data )
[
[ [ <CGBitmapContext> &CGContextRelease ] keep ] dip
[ nip call ] [ drop bitmap-data ] 3bi
] with-destructors ; inline

Now, higher-level code can simply wrap some Core Graphics rendering calls in a with-bitmap-context, and receive a Factor byte array as the result.

Creating a CTFont


Core Text defines the CTFont opaque type to represent a specific instance of a font with a style and size applied. I create CTFont instances with CTFontCreateWithName, and then apply bold and italic styles by calling CTFontCreateCopyWithSymbolicTraits. There is another API to do this in one shot, CTFontCreateWithFontDescriptor, but for some reason it ignores any set symbolic traits. Perhaps its a bug, or operator error, but it took me a lot of futzing around to get Core Text to respect my choice in font style. Another caveat to watch out for is that CTFontCreateCopyWithSymbolicTraits returns null if the traits could not be applied; for example, Apple's "Monaco" font does not have a bold variant, so if the user requests bold Monaco, you just have to return the original Monaco without the traits. There might be a way to synthetically increase the font weight, but I haven't discovered it yet.

Creating a CTLine from a string and a font


One of the central abstractions in Core Text is a CTLine. You create a CTLine from a CFAttributedString with CTLineCreateFromAttributedString, and render it to a CGContext with CTLineDraw.

Creating the CFAttributedString is an adventure in itself. For now, I'm only interested in rendering a string with a single font style and color, so I can use the CFAttributedStringCreate function to create the attributed string. It takes a CFString and CFDictionary. The dictionary can contain a number of keys, the two I'm using are kCTFontAttributeName and kCTForegroundColorAttributeName. These are global variables holding CFString references. Factor's FFI doesn't have a way to access global variables right now, so I made a quick hack specific to the core-text vocabulary. It lets you access global vars that hold void* values. Soon I'll generalize it and put it in alien.syntax, but for now it can live as a private utility in core-text:
: C-GLOBAL:
CREATE-WORD
dup name>> '[ _ f dlsym *void* ]
(( -- value )) define-declared ; parsing

Using this utility is easy:
C-GLOBAL: kCTFontAttributeName
C-GLOBAL: kCTForegroundColorAttributeName

Because I found myself constructing lots and lots of CF types: strings, numbers, dictionaries, colors, and so on, I made a utility word, >cf which converts a Factor object into a Core Foundation object. Using this word, I can define a <:CFAttributedString> that constructs a CFAttributedString from a Factor string and assoc:
: <CFAttributedString> ( string assoc -- alien )
[
[ >cf &CFRelease ] bi@
[ kCFAllocatorDefault ] 2dip CFAttributedStringCreate
] with-destructors ;

Again, notice the destructor usage: we want to release the string and dictionary after we return, since the attributed string retains them for us.

Now, we can create the CTLine, finally. Notice how we take a Factor string, a CTFont, and a color, and make the attributes as a Factor assoc; the <CFAttributedString> word takes care of converting it to Core Foundation types. And again, we use destructors for deterministic resource cleanup:
: <CTLine> ( string font color -- line )
[
[
kCTForegroundColorAttributeName set
kCTFontAttributeName set
] H{ } make-assoc <CFAttributedString> &CFRelease
CTLineCreateWithAttributedString
] with-destructors ;

Rendering a CTLine to a bitmap context


Now we can put some things together and write a word which renders a Unicode string to a Factor byte array.

First, we make a data type to hold the CTLine, the rendered bitmap, the typographic bounds, and some other things:
TUPLE: line font line bounds dim bitmap age refs disposed ;

The refs and age slots are used for caching lines so that the UI doesn't have to render them over and over again; I'll discuss this in another blog post, maybe.

Now, we have some code which computes the typographic bounds of a CTLine, and packages the values up into a Factor tuple; there's also a word to compute the size of the bitmap to create. This doesn't take leading into account, I haven't decided how to handle that yet:
TUPLE: typographic-bounds width ascent descent leading ;

: line-typographic-bounds ( line -- typographic-bounds )
0 <CGFloat> 0 <CGFloat> 0 <CGFloat>
[ CTLineGetTypographicBounds ] 3keep [ *CGFloat ] tri@
typographic-bounds boa ;

: bounds>dim ( bounds -- dim )
[ width>> ] [ [ ascent>> ] [ descent>> ] bi + ] bi
[ ceiling >fixnum ]
bi@ 2array ;

Now that we have the above utilities, as well as all the code defined earlier, we can write a <line> constructor word which constructs a line tuple. Part of the construction involves rendering the text to a bitmap, and storing the resulting byte array in the line's bitmap slot. We're going to use the with-bitmap-context word written above here. There are a few steps to rendering a CTLine to a bitmap context:
  • First, you must fill the context with a background color, using CGContextSetRGBFillColor and CGContextFillRect. Leaving it transparent will disable sub-pixel rendering, so the line constructor takes a background color as a parameter.
  • You must set the text position with CGContextSetTextPosition.
  • Finally, you can render the text with CTLineDraw.

This word manipulates a lot of intermediate values, makes a fair number of Core Graphics calls, and has complex data flow, so I chose to implement it using locals. Notice the [let* "serial-binding" form; successive definitions can reference previously-defined values:
:: <line> ( string font foreground background -- line )
[
[let* | font [ font CFRetain |CFRelease ]
line [ string font foreground <CTLine> |CFRelease ]
bounds [ line line-typographic-bounds ]
dim [ bounds bounds>dim ] |
dim [
{
[ background >rgba-components CGContextSetRGBFillColor ]
[ 0 0 dim first2 <CGRect> CGContextFillRect ]
[ 0 bounds descent>> CGContextSetTextPosition ]
[ line swap CTLineDraw ]
} cleave
] with-bitmap-context
[ font line bounds dim ] dip 0 0 f
]
line boa
] with-destructors ;

Notice how it uses "on-error" destructors, named |foo. This means that if the construction fails for whatever reason, the CTLine and CTFont objects are released, but if construction succeeds, they are retained. This is done so that we can hold on to these objects and store them in the new tuple's slots. The tuple itself has a dispose* method which releases the font and line objects:
M: line dispose* [ font>> CFRelease ] [ line>> CFRelease ] bi ;

The Factor UI uses all the slots in the line object to perform operations such as measuring text, caching textures, and so on. For the purpose of this blog post, the only interesting slots are dim and bitmap. The bitmap slots holds a byte array with the rendered text, in the format we specified when creating the bitmap context; ARGB with native byte order.

Creating an OpenGL texture from a Core Graphics bitmap


Standard OpenGL does not support ARGB bitmaps, however Apple's implementation supports the GL_BGRA_ext extension. To use this extension, I had to add a couple of constants to our opengl.gl vocabulary:
! GL_BGRA_ext: http://www.opengl.org/registry/specs/EXT/bgra.txt
CONSTANT: GL_BGR_EXT HEX: 80E0
CONSTANT: GL_BGRA_EXT HEX: 80E1

Now, we can pass CL_BGRA_EXT to glTexImage2D. Here is a utility word to ease creation of textures. Since glTexImage2D takes 9 parameters (!) I use locals so that I can name them:
:: make-texture ( dim pixmap format type -- id )
gen-texture [
GL_TEXTURE_BIT [
GL_TEXTURE_2D swap glBindTexture
GL_TEXTURE_2D
0
GL_RGBA
dim first2
0
format
type
pixmap
glTexImage2D
] do-attribs
] keep ;

Once the texture has been created, we can display the text on the screen by binding the texture and rendering a quad. It is also important to call glEnable with GL_TEXTURE_2D, otherwise the quad won't be textured. I forgot this the first time and spent some 20 minutes looking at my code -- OpenGL is very picky like that.

Keen readers will observe that I make no attempt to ensure the texture dimensions are powers of 2. This is because all Macs capable of running OS X 10.5 support the GL_ARB_texture_non_power_of_two, so at least in this case, you don't have to worry about padding the bitmap out anymore.

I wrap all of this in a display list so that a previously-rendered piece of text can be displayed anywhere by performing a translation and calling the display list. Here is the code that does this:
: make-line-display-list ( rendered-line texture -- dlist )
GL_COMPILE [
GL_TEXTURE_2D [
GL_TEXTURE_BIT [
GL_TEXTURE_COORD_ARRAY [
white gl-color
GL_TEXTURE_2D swap glBindTexture
init-texture rect-texture-coords
dim>> fill-rect-vertices (gl-fill-rect)
GL_TEXTURE_2D 0 glBindTexture
] do-enabled-client-state
] do-attribs
] do-enabled
] make-dlist ;

All the rest


I won't discuss the details of the remaining parts of the font rendering implementation here, but briefly, they are:
  • A texture cache where frequently-used textures are held to avoid rendering the same text over and over again; text expires from the cache if its not used for five consecutive rendering runs
  • Code for measuring text, converting logical positions to screen co-ordinates, and vice versa
  • The high-level platform-independent text API in Factor's UI, and the mapping between this API and the abstractions I described here
  • The FreeType implementation of the high-level layer, for use on other platforms

If you want to dig deeper, feel free to peruse the core-text, core-graphics, ui.text and ui.text.core-text vocabularies in the new_ui branch in the GIT repository.

Appendix: alien destructors


For background about Factor's destructors, see the following:

With destructors, you can wrap some code in a with-destructors scope, and call &dispose on external resources; when the with-destructors form returns, dispose is called on all the resources marked for disposal with &dispose. This is very handy for working with such things as Factor streams, database connections, and so on, but its a problem for bare C references; they're all instances of alien, and there's no meaningful dispose method that works on all of them. Our idiom until recently has been to wrap the alien in a one-tuple slot, which defines a custom dispose method, but this is just boilerplate. Factor supports meta-programming, and this could be taken care of with parsing words and macros; but the functors abstraction I implemented a while ago, which basically gives you a very easy way to implement a certain type of parsing word, works really well here, and it becomes completely trivial to abstract out the creation of the one-slot class with a custom dispose method. The alien.destructors vocabulary defines a single parsing word, DESTRUCTOR:. Here is an example of its use from the core-foundation vocabulary; first we define an FFI binding to the Core Foundation CFRelease function, then we define it to be a destructor:
FUNCTION: void CFRelease ( CFTypeRef cf ) ;

DESTRUCTOR: CFRelease

The DESTRUCTOR: word defines two new words for us; &CFRelease and |CFRelease. You can see examples of their usage previously in this post. Here is the implementation of DESTRUCTOR: -- I won't go into the details, but you can see it looks like a template of what you'd write out every time if you didn't have the abstraction:
FUNCTOR: define-destructor ( F -- )

F-destructor DEFINES ${F}-destructor
<F-destructor> DEFINES <${F}-destructor>
&F DEFINES &${F}
|F DEFINES |${F}

WHERE

TUPLE: F-destructor alien disposed ;

: <F-destructor> ( alien -- destructor ) f F-destructor boa ; inline

M: F-destructor dispose* alien>> F ;

: &F ( alien -- alien ) dup <F-destructor> &dispose drop ; inline

: |F ( alien -- alien ) dup <F-destructor> |dispose drop ; inline

;FUNCTOR

: DESTRUCTOR: scan-word define-destructor ; parsing

Functors are just a hack and everything they do can be achieved using parsing words, but the code with functors, in the cases that they can handle, is simpler and more declarative.