Displaying Newsletter
Issue 6, 01 Dec 2001

  In This Issue:
Cash: color coding source files by Daniel Reinhold 
If you've ever used the CVS browser for OpenBeOS (or other projects), you will notice that the individual files can be viewed in a web browser with color coding (just click on the file's version number). This is pretty cool. In fact, a lot of websites dedicated to programming in one way or another having factilities for viewing source code files in color coded html format.

So how hard would it be to implement this feature? Not too difficult. And kind of fun. I wrote one awhile back and decided recently to update it a bit. It's called cash -- that means C as html -- cute, no? Ahem, well anyway...

Though the program is simple, it has a few interesting ideas in it. We cover some basics of parsing and the concept of table-driven programming. The output of cash isn't too sophisticated, but it could be easily modified to more fancy formatting if you are so inclined.

The program takes a C source file as input and writes out an new html file (just the source file name with ".html" appended). It is, in effect, a translator. A translator, generally, has at least two main parts: a parser and a generator. The parser reads the input and breaks it up into a stream of "tokens". The generator reads these tokens and writes them out in the output format. A full blown translator would have more intermediate steps and internal formats than this, but we needn't be concerned about that for our purposes.

Let's consider the generation first. Because the output is html, you don't have to do much of anything. A browser can display any text file (which includes C programs) as is. However, it would be nice to at least put in the standard html header and footer -- i.e. the 'html' and 'body' tags at the top and then the closing tags for these at the bottom.

As for the text, all we mainly want to do is color code individual words or groups of words: make keywords blue, comment blocks green, etc. (well, those are the colors that I like). Since the parser has already identified these basic elements, generation is not much more than intercepting these cases and bracketing the text, when needed, with html tags. This is called 'marking up' text. After all, that's where html got its name -- hypertext markup language.

Now, you could do some fancy stuff in terms of pretty printing. You could use different fonts for different token types (one for keywords, one for comments, etc.) You could put certain code sections in different colored blocks, etc. There's no end to how fancy you might want to go. However, I take the easy road. I just place all the text within pre-formatted tags (i.e. <pre>...</pre>). This preserves the newlines and spacing as the original author intended. It also forces the text to be displayed in a fixed-width font, which is somewhat limiting. I don't mind, however; in my experience, code displayed in variable-width fonts never looks right.

The only other issue for generation is expanding meta-characters. Since html uses certain characters for syntactic elements, they have to be expanded into special strings called "entities". For example, the less than character '<' must be expanded to "&lt;" in order to display properly. Spaces and tabs don't need to be expanded because the text is inside the <pre> tag. However, I expand tabs anyway because I like four-space tabs and NetPositive displays eight-space tabs (which drives me crazy).

Now to the parsing. Parsing can be as complex as you want. Entire volumes have been written on parsing and formal language theory. There is top-level parsing using recursive descent and bottom-up parsing using action tables. There are even programs that write translators for you, such as yacc. My own preference has always been to hand code the parsing. However, the use of tables to automate the parsing process does lead to an interesting style of programming that I have been moving towards over time: table-driven programming.

All programmers are familiar with holding data in tables and then writing code to acess and modify the data. But in table-driven programming, you put the code itself into tables. Instead of embedding the logic across different functions, you encapsulate the common behavior into a collection of operations and keep a table of pointers to access those operations.

For example, instead of writing:

if (conditionX)
    do_X (a, b);
else if (conditionY)
    do_Y (a, b);
    do_Z (a, b);
You could write:
n = condition ();
DoOperation[n](a, b);
Here, condition is a routine that figures out the which operation is needed and returns an index into a table of function pointers for carrying out the operation. This function is then called.

It might not seem like the table-driven approach buys you much. But, in fact, it is much easier to add and change functionality through the table entries than thru the source code. Factoring out common functionality is one of the wise programming practices that we all strive for, and putting your program logic into function tables often forces you to do exactly that. I've grown fond of this approach and try to use it whenever it makes sense.

Table-driven programming is particularly appropriate when the number of operations is relatively fixed and have a standard interface (i.e. input parameters and output values). Parsing text often falls into this category. I use this technique for parsing the input in cash. For example, here's the markup function:

markup ()
    // read and output the source text with all necessary markups
    // method:
    //   each beginning character uniquely identifies a handler...
    //   each handler reads in a particular token type from the
    //   source file and outputs the text with any needed html tags
    int   c;
    outfn output;
    while ((c = fgetc (Source)) != EOF)
        output = Handler[Token[c]];
        output (c);
This references a global table of "handlers", that is, functions that know how to read and output a particular token type. Here's the definition:
typedef void (*outfn)(int);
. . .
static outfn Handler[] = {expand,  preproc,  comment,  literal,  word,  number};
The default function (at index 0) is expand, which simply expands the character to an html entity when needed, otherwise just writes the character as is. The remaining functions handle the cases for preprocessor directives, comment blocks, string and character literals, words (including keywords), and numeric literals. These are the only tokens that cash knows about.

The simplicity of the markup routine is that each handler can be immediately identified by a single character. When a '#' is read, preproc is called. When a '/' is read, comment is called. And so on. The Token table maps the input character to a handler index.

Although the parsing in cash is relatively simple, this is because it needs to know only about a few types of tokens to properly do the color coding. It is not a limitation of the table technique -- this could be expanded to handle as complex a parsing task as you care to undertake.

Still, there are improvements that could be made. You might want to add additional keywords and logic for handling C++ files. It would also be useful for the preprocessor routine to recognize special cases such as "#if 0 ... #endif" and color code the entire block as red, for example. You might even want to generalize the process to handle any language as input. These improvements are left as exercises for the reader (grin).

Source Code:

High speed BMessages via S-COW by Michael Phipps 
Warning: This article is more a thought process than a design spec. Count on its details at your peril.

Recently, I was told an interesting detail about Be's implementation of BMessage: namely, the process of sending a BMessage requires 5 copies. My educated guess is that those copies are a result of a process that looks like this:

BMessage => archive => port => archive => BMessage
Furthermore, I was told that this was so implemented for stability; there was a different, more efficient design at one point in time, but that it was abandoned to improve the stability of the BeOS kernel.

A different, more efficient design would require fewer copies. One way that this can be accomplished is via COW -- copy on write. To understand COW, you must understand a little about memory management, kernels and MMUs.

When an application allocates memory (create_area, not malloc), the kernel tells the virtual memory (VM) that it needs space. The VM makes an entry for the space. As soon as the application tries to access the space (either read or write), real memory is used. COW works a little differently.

With COW, you tell the VM that you want a copy of a particular object. The VM does't copy the physical memory (or the disk space, it the memory is swapped out), but instead makes that memory available to you, with a footnote. That footnote is that this memory is write protected. When the copy is written to, the VM intercepts that write, physically copies the page, then does the write. The untouched pages still have one copy, but the altered page(s) now exist as their own memory.

There are 2 flavors of COW (no, not teriyaki and barbeque) - asymmetrical and symmetrical. Symmetrical COW says that ANYONE who has a "copy" of this memory and writes to it makes a new copy.

Implementing BMessage using S-COW seems like a fairly trivial exercise. When a BMessage is created, it needs a custom new and custom delete that put its data in an area. When a BMessenger wants to send a BMessage, it gets the area name from the BMessage and calls the kernel, telling it to put a "copy", an S-COW pointer, if you will, into the recipient's queue.

Wait, you cry! Doesn't that require a trip into kernel land? Isn't that *SLOW*?

Maybe. But before I propose a solution to that, let me point out that it *seems* (since I have not read the Be implementation) that any way you do this would require a trip to kernel land. Otherwise, you would be writing into some other processes memory when you call write_port (which is how BMessage is implemented, I would guess). So it shouldn't be *slower* than what exists today. And (at least for large messages) it should be faster.

So what about this avoiding the trip to kernel land idea? Well, there are a couple of times that we have to go to kernel land. Let's talk about each on their own:

1) When you create or free a BMessage. Create_area and delete_area call the kernel. What I would propose here is some TLS - thread local storage. Create 3 or 4 pointers in thread local storage. Allocate maybe one or two blocks of memory. Most allocation and freeing issues could be handled this way. When the thread is not running (i.e. it goes to the kernel for rescheduling), the kernel looks to see how many of those slots are NULL. If there are less areas than there should be, create one for next time. If there are too many, free one or two. Protect these pointers with an atomic_add (benaphore, IIRC) semaphore wannabe, and we are OK.

2) Sending messages is a different story. Synchronous messages are replied to (i.e. the target app gets the message, does its thing, then preps a response) before your app moves. That would indicate to me that a reschedule is required, anyway. No big deal. Asynchronous messages, then, are also not a big deal. Just a little more TLS. A queue, for the thread, that holds messages and their destination, with a protecting variable. Not a whole lot of space here. Maybe 4 slots. 32 bytes, if my math is correct (4 sets of message and destination), plus a byte for the protecting benaphore. When the app gives up its time (reschedule), the kernel checks the queue. If there is anything there, they are sent set as S-COW and delivered.

Cleanup is the final issue, here. What if an app crashes? Well, any memory that the app had is now freed. If the app had memory that was set as S-COW, the "other" owner(s) of that memory now become the only owners. This implies some sort of reference counting. This sort of an issue, though, is happening throughout the kernel, with other things (e.g. application images should be reference counted). This should not be too much of a problem.

All in all, if this works as well as I think that it will, some of the methodologies that Be used to implement kits could be improved. Networking would not need to go into the kernel -- it could use BMessages to deliver packet data. It would be "free". Likewise, instead of inventing our own buffered messaging protocol between the app_server and the C++ classes, we could use standard BMessages, since they should be fast enough.

Putting stuff on screen: dreams of the perfect UI platform by Michael Phipps 
In my travels at work and at home, I have come to realize that many people in the industry have the same problem:

They need to put stuff on screen.

I understand that is a pretty vague statement. Let me develop a bit further...

Web developers have all but abandoned pure HTML. Shockwave, Flash, Java applets, Active X controls and (last but not least) JavaScript rule the web scene. Why is this the case? Web developers need to impress their clients and their audiences. They can no longer do so with tables, frames or blinking text. They need to play animations, precisely arrange the layout, provide interactivity and so on.

GUI developers have some similar issues. Many people have criticized the Interface Kit for its lack of font sensitivity and hard coded "pixel" values. Another criticism of the IK API is that you almost have to subclass any element whose events you need to catch. While this is not completely true, it is still true enough to allow me to say that the web designer and the GUI builder for BeOS have many of the same issues. Combine this with the corporate trend of requiring application to be web based (don't ask me -- I disagree, too), and the droplets of this concept start to come together.

What if, just dreaming for a moment, there were an application that I could use to "put stuff on screen". It would allow any of the following:

I can specify, for each element, scaling ([scale] [scale just so far] [don't scale]), attachment (our left side is attached to widget foo's right side, plus 10% of our size), and so on.

I can drag and drop an animation onto the page. With or without play controls. I can have a background picture or animation. I can have music that plays when this "screen" was displayed.

I can associate events with a function without subclassing. For that matter, I can write the code in anything that will take a BMessage, either via a network OR via BMessenger.

Menus (application and context) are all easy to set up. I can customize the messages sent out, if I wish, so if I want to interface with something (maybe it has a scripting interface), I can.

Imagine this. GUIs designed completely outside of the realm of the application. Something like, say, SoundPlayer, coming with a default interface. You can do more than "make a skin", you can redesign the whole UI, so long as you send the right messages.

Applications basically become servers. The GUI becomes a client. It shouldn't be too hard to make an add-on to a web browser that could display this hypothetical solution. And, if BMessages could be sent across a network, one could run their apps from anywhere in the world.

Imagine that.