Simon Wright

Building a markup language: part two

Previously, I've talked in general terms about Whirlcode 2, which is a mark-up language tailored for use on whirlpool.net.au, and coded in JavaScript.

One of the most challenging part of the code was to ensure reliable handling of excessively long strings of characters, which — if allowed to pass unfiltered — can play havoc with HTML page layouts. Not difficult, you might think: just search for long words and litter them with breakable characters? Not so fast — you're dealing with text that contains mark-up.

• Mark-up shouldn't count towards the size of a word. If the word length limit is 25, then we don't want to penalise "un<b><i>flapping</i></b>believable". So we can't count them. And HTML entities (such as "é") should only count as a single character.
• Similarly, mark-up shouldn't act as an escape sequence for long string handling. A space within an <a href> tag shouldn't be treated as a space within the document.
• And when we get around to littering these long words with breakable characters, we need to be absolutely sure we're not inserting them inside mark-up, HTML, or entities.
• Finally, we need performance to be good. You can brute-force just about any rationally solvable problem, but we want this code to run frequently, both on the server and on client machines.

Here's what I came up with:

var inputString = txt;
var outputArray = [];
var maxColumns = 30;
var spaceMatchRegexp = /^((<[^>]+>|[^<\s]){0,30}\s+)+/;
var ptagMatchRegexp = /^<\/?[p|h1|h2|h3|ul|ol|li|hr|br]>/;
var entityMatchRegexp = /^&\w+?;/;
var charCount = 0;
var howMuchToGrab = 0;
while(inputString.length) {

    // Short-circuit where near/at end
    if(inputString.length < maxColumns) {
        outputArray.push(inputString);
        break;
    }

    var spaceMatches = inputString.match(spaceMatchRegexp);
    var ptagMatches = inputString.match(ptagMatchRegexp);

    // skip to next candidate area
    if(spaceMatches && spaceMatches[0]) {
        howMuchToGrab = spaceMatches[0].length;
        charCount = 0;
    // jump html tags
    } else if(inputString.charAt(0) == "<" && inputString.indexOf(">") > -1) {
        howMuchToGrab = inputString.indexOf(">");
        if (inputString.match(ptagMatchRegexp)) charCount = 0; // if it's a paragraph tag, reset the character count
    // jump entities
    } else if(inputString.match(entityMatchRegexp) ) { 
        howMuchToGrab = (inputString.indexOf(";") > -1) ? 1+inputString.indexOf(";") : inputString.length;
        charCount++;
    // normal character
    } else {
        howMuchToGrab = 1;
        charCount++;
    }

    // move chunk from input to output 
    outputArray.push(inputString.substring(0, howMuchToGrab));
    inputString = inputString.substring(howMuchToGrab);

    // if the limit is hit, add a word break
    if(charCount >= maxColumns) {
        outputArray.push("<wbr>");
        charCount = 2; // not sure why but testing bares this out
    }

}
txt = outputArray.join("");

The little gem in this code is the following regular expression: ^((<[^>]+>|[^<\s]){0,30}\s+)+. It knows how to skip across large tracts of acceptable content, while intelligently ignoring HTML tags. It's the optimisation that makes the rest of the code go fast.

When this regexp isn't matched, the code loops over each printable character, periodically dropping <wbr> tags as it goes.

Read comments (5)

Building a markup language: part one

User-generated content sites like Wikipedia and Whirlpool rely heavily on the ability for users to submit richly and contextually marked up content; everything from references to quotations, from links to lists. And this ability needs to be given to a large array of users who don't know HTML, or worse still, know too much. So we build syntax that gives users the ability to provide rich content within the parameters we set — without opening the doors to unwanted, nuisance or malicious mark-up.

Wikipedia's answer is wikitext, a comprehensive (though occasionally bewildering) syntax which makes it possible to have a generally consistent feel to most articles. It still requires authors to follow the guidelines, but a lot of heavy lifting and boilerplate is handled by the parser.

Whirlpool has a similar need. We've got thousands of new posts every day, hundreds of private messages, a job board and our own Wiki — all needing rich text handling of one sort or another. It's an important component to get right.

Up till now, Whirlpool's answer was Whirlcode. It's a fairly simple mark-up that is also difficult to trigger accidentally. Tags like [*bold*], [/italics/] and ["quotes"] aren't necessarily intuitive, but once observed are easily learned and retyped. However over the past couple of weeks I've been hard at work on Whirlcode 2, a major rewrite of the parser that handles this mark-up. And yes, I've written it in JavaScript.

What features could a parser support? Here's a list of the ones I've specifically dealt with in the development of Whirlcode 2:

• Manage white-space. Users should not be able to post large chunks of blank space. Whirlcode 2 does this by differentiating between line breaks and paragraph breaks, and not allowing consecutive usage.
• Permit a limited subset of HTML. This must be done in a whitelisting fashion, as there is practically no limit to the variety of ways unmanaged HTML could screw up your pages. Whirlcode achieves this by escaping all HTML tags then progressively un-escaping tags which are permitted.
• Implement a custom syntax. Sure, HTML can do bold and italics, but you'll need your own mark-up for special items like quotations, wiki links, and colouring. We've got some fun ones as well, such as a tag to turn a string of words into a linked google search.
• Bulleted and numbered lists are nice to have. You can either let the correct HTML through, or support your own short-hand such as that offered by Textile.
• Break long words. If someone posts a ridiculously long word, it can often stretch and sometime break the page layout. Identifying and safely handling this is a particularly difficult thing to do, as you need to make sure you're not going to ruin mark-up in the process, nor have mark-up bypassing the long word test. I'll have more to say on this in a future post.
• You can detect common ascii-isms and replace them with more suitable mark-up. For example, (c) could be replaced with ©
• Users will frequently paste URLs and email addresses straight into their content. Automatically linking up these addresses is a useful convenience.
• Censor certain words. No regular expression can match every insult, and context often plays a larger part than we realise, but you can pick out the most egregious for special treatment. Generally, you'd replace the identified words with stars or #^%@ing ascii. I like to replace them with different, harmless words.
• Strip out unwanted unicode. Yes, it's wonderful how text strings can now contain every character from every language. But there are some which are only used to irritate.

Check out this live-in-browser example:

= Features of Whirlcode 2 ----- * [/Traditional/] ["Whirl"]['code'] [#support#] * <b>Limited</b> <small>HTML</small> * http://automatic.link/parsing *# Nested lists *#* Up to three levels *# And it creates good HTML * (c) 2008 Entity Recognition(tm) -- not 1/2 bad! * Plus headings, lines, blockquotes and more

I will be writing more about the specific algorithms developed as part of Whirlcode 2 in a future post.

Read comments (17)

ColdFusion and server side javascript

Whirlpool has its own forum mark-up language which we call Whirlcode; it's analogous to, but not the same as BBCode. In recent weeks I've been considering how to improve the Whirlcode syntax, particularly now that it's being used to mark up more complex documents such as entries in the Whirlpool wiki.

My first instinct was to see what's already out there — and the short-list of candidates were Textile and Markdown. However neither have complete ColdFusion implementations, and from what I can tell the javascript implementations aren't exactly complete either — certainly not consistent with their server-side brethren.

I realised that more than anything else, I needed a mark-up language with 100% compatible server and client-side implementations, otherwise client-side previews could not be useful. And given the existing ‘investment’ in Whirlcode across the site, building my own ‘Whirlcode 2.0’ seemed the way to go. I took some ideas gleaned from Textile, combined them with traditional Whirlcode syntax, wrote a specification, and then built the first implementation in javascript.

My original plan was to port the javascript version to <cfscript>, but was also thinking about Rhino, an implementation of javascript in Java. I wondered how easy it could be to get my javascript parsed server-side, within my ColdFusion code.

Rhino in ColdFusion isn't new territory. Barney Boisvert cracked the puzzle six months ago, though his code uses Rhino to power a whole development framework. All I needed was to proxy one javascript function as a ColdFusion function, a very different, much simpler task.

So I started with Rhino's examples, and got a class working within NetBeans that worked for a very simple javascript function. I then turned it into a Java CFX tag (CFX tags have many limitations, but compiling a class meant easier debugging).

Here is a snippet of the Java:

import org.mozilla.javascript.*;
...
Context context = ContextFactory.getGlobal().enterContext();
try {
   Scriptable scope = context.initStandardObjects();
   Object result1 = context.evaluateString(scope, javascript_as_string, "somelabel", 1, null);
   Object theFunction = scope.get(function_name_as_string, scope);
   Object functionArgs[] = arguments_as_array;
   Function f = (Function)theFunction;
   Object output = f.call(cx, scope, scope, functionArgs);
} finally {
   Context.exit();
}

Finally, I transcoded it into <cfscript>. The following is the simplest possible code for executing a javascript function within ColdFusion. I have stripped out the error handling and function wrapping to show the underlying concept as clearly as possible — a more featureful implementation is left as an exercise for the reader.

<cfscript>
   script = FileRead(path_to_your_script.js);
   try {
      context = CreateObject("java", "org.mozilla.javascript.ContextFactory")
         .getGlobal().enterContext(); // Get the context object 
      try {
         scope = context.initStandardObjects(); // Prep the environment 
         context.evaluateString(scope, script, "somelabel", 1, javacast("null",0)); // Eval script 
         output = scope.get(function_name_as_string, scope)
            .call(context, scope, scope, arguments_as_array)
            .toString(); // Execute the function and return the result as a string
      }
      catch (any excpt) { }
      context.exit(); // Clean up
   }
   catch(any excpt) { }
</cfscript>

There are two alternative points where caching could be applied. Either cache the FileRead so you're not hitting the file system every time, or don't exit the context and cache it (and 'scope') somewhere.

Before this will work, you'll probably need to update the copy of Rhino embedded in ColdFusion. (Does anyone know why it's there at all?) Download the latest version, and to ensure this version loads first, copy js.jar into \ColdFusion8\runtime\servers\lib\. Packages in this directory load before any other.

Read comments (4)

What makes a good site search?

Search is the dominant form of navigation on the internet; when it works, it's the fastest way to get where you want to go. Yet when it comes to site search, many websites really phone it in. As a result, users have started ignoring site search boxes entirely.

So, how do you do site search properly?

Before you begin, ask yourself if building or deploying anything is really necessary. Do you need something that Google or Yahoo's public site search features can't manage for you? Do you have domain-specific knowledge that you can apply to your specific situation?

Perhaps you've got information that Google can't, won't, or is not permitted to index. Perhaps your website is all about search such as it is with online classifieds. Perhaps your needs don't align with the behaviours of the public search engines, for example, when your content has an extremely short shelf life.

Doing search right is all about achieving good results and communicating them well. There are many techniques you can use to tune your site search algorithm. Common ones include:

• Keyword relevance. This is the meat and potatoes of any text-based search, yet it's often poorly implemented. Make sure you're not capturing content that isn't relevant. If possible, exclude navigation, related links and other elements that don't describe the page's unique meaning.
• Identify the core elements on a page and weight their content more highly. For example, the content's title is important, while the names and home towns of satisfied customers probably aren't. Excess content can lead to false positives which pull attention away from relevant pages.
• Not all high-value content is on your page. You can sometimes find high-value keywords in unexpected places. For example, if you capture the keywords in google referrals to each page, these could be used to automatically populate your keyword meta data. These are keywords used by real people who in all likelihood wanted to find that page.
• Build a keyword thesaurus, but use it cautiously. If possible, define the strength of each keyword relationship. Consider the following pairs: footwear and shoes; pills and drugs; knife and cutlery. Clearly not all of these relationships are as relevant as each other; in many cases the relevance only goes in one direction. Often these relationships follow a taxonomical structure; be aware of this.
• Link graph analysis. This was Google's secret weapon when they burst onto the scene in 1999, but is generally not useful for site search algorithms. You should be able to determine the relative importance of each page on your site with more objective methods.
• Content popularity. You can determine this in many ways, but it generally involves counting the number of hits the content receives. Frequently viewed pages are more likely to be what someone is looking for. You can refine this further by looking at what's popular this hour versus this month, for example.
• Age of content. When dealing with timely information such as news reports, you could assign higher importance to new content. Ask yourself how many searches you'd likely get for current versus back catalogue material.
• Removing outdated content. Increase your signal to noise ratio by making sure expired content isn't cluttering up good current content.
• Contextual relevance. If you can ascertain the country a user is in, you could tailor the results to their locale. In a similar vein, you could identify the user's computer platform and target results that way — this might be useful for a shareware library, for example. There's no hard and fast rules here; even the time of day could be used to improve search results for some niche.
• Active personalisation. Anything you might know about a user can prove useful. A makeup company might ask users to set their skin colour within their user profile; then in turn subtly change search results to favour products compatible with that complexion. Many sites could benefit from knowing the age or sex of a user. Even ethnicity isn't out of the question — yes, there really is a search engine whose algorithm favours 'black' related content.
• Passive personalisation. If you know what the user has viewed or interacted with in the past, you can bias the choices towards (or away) from the same or similar items.

Okay, so now you have great search results that consistently find exactly what they're looking for. Don't screw things up in the last innings by not conveying the content well on the results page.

• You can have exactly the page they're looking for come up first in the results, but if the result doesn't look like what they're after, they might overlook it. Make sure your titles are clear and concise, and ensure descriptions take a relevant quote from the page.
• Highlight the user's terms within the search results. This greatly improves the user's comprehension of the results.
• Don't over-complicate the page design for search results. People are used to Google; don't be afraid to let its design help to inform your own.

How do you know if you've made any real-world improvements to the search quality? Measure it.

• For each search, log which results they click on, and whether it was the first, second or 43rd result. If you graph the lowest position for every search, you should see an upward trend as the algorithm is improved.
• Log whenever a search fails to produce any results, or fails to produce any clickthroughs. Individual cases can be looked at for possible new thesaurus entries — you'll learn about many common spelling mistakes this way.
• Log whenever the user went to page two. In particular, when they never clicked on any page one results. This can be a sign that results aren't sufficiently relevant.
• What are people finding via Google versus your own search engine? Reporting this can often prove insightful about how users interact with your search, and what they expect it to be capable of.

In a future article I'll talk about some practical implementations for many of these ideas.

Read comments (5)

A case study of performance optimisation

I run what could quite possibly be the highest trafficked ColdFusion/MySQL website out there, and while our web hosting benefactors have been gracious, we really don't have the computing power needed to competently handle the million or so page views we get each day. So I spend a lot of time looking for ways to do more with less, server-wise.

There's a lot you can do to identify bottlenecks and poorly performing code in your environment. Even after you've picked the low hanging fruit, there can be a lot of small wins that mean a great deal particularly when the server is running hot 18 hours a day. Some of the techniques I use include:

• Monitor ColdFusion for slow-running or blockage-inducing templates using its built-in monitoring facility or a third party tool such as SeeFusion. This method not only lets you quickly identify rogue templates, it also gives you a sense where in your code general performance improvements could be sought.
• Time suspicious pieces of code, follow the trail, and don't be afraid to believe what might at first seem improbable. Session variables, locking and array declarations conspire to make innocuous looking code decidedly malevolent.
• Watch various critical metrics with Windows Performance Monitor such as memory and processor usage, average execution times and disk activity. Investigate suspicious variations with tools like Process Monitor from Sysinternals. We've used this to discover numerous problems including a performance-sapping virus scanner and a misbehaving backup process.
• Keep debugging completely switched off in Administrator! Even when the debug output is suppressed in code, it's still doing a lot of extra work that it does not need to do. Just moving the mouse near that checkbox causes the Whirlpool server to haemorrhage.
• Watch the health of your SQL server. Is your query cache being effective, or even enabled? What about the key buffer? MySQL users now have the excellent Administrator tool, which charts some very useful live metrics including the query cache hitrate.
• Monitor your database server for slow running queries. Microsoft SQL Server has a tool called Profiler that can be configured to show queries that exceed a threshold, although it has limitations (particularly, it can't show slow queries as they're running). With MySQL, run a SHOW FULL PROCESSLIST to discover what's happening in that moment. This becomes particularly handy in a GUI tool where you can refresh this multiple times per second, effectively animating current execution behaviour. You can learn a lot this way.

The case study

Back in January 2007, we upgraded to ColdFusion 7 and MySQL 5... and immediately started seeing a whole bunch of queries running in the MySQL process list which I didn't write. SHOW FULL COLUMNS FROM tablename? I wanted to know where these mysterious queries were coming from, as we were having performance problems with the new configuration and I was sure this was the cause... or at least the symptom.

Step one — make sure it's not my fault. Does it happen on a freshly installed copy of ColdFusion? I had one on my local computer, and it was causing the same symptom: whenever a query is run, SHOW FULL COLUMNS followed like a shadow. Similarly, a freshly installed copy of MySQL with a carefully recreated database schema didn't change anything.

Step two — try regressing versions. My gut assumption was that ColdFusion 7 was innocent, as I had recently upgraded a swath of machines to version 7 at work and didn't see these queries popping up on our MSSQL servers. After many hours of installing and reinstalling, it turned out that it was neither program's fault: it was the combination! Regress either back to their previous versions and the problem went away.

Step three — identify the culprit. After tracing network activity between the servers, it quickly became apparent that these queries were being generated on ColdFusion's end... but how? As I was restoring the configuration for the umpteenth time, the answer hit me: Connector/J! I had been dutifully swapping versions of this jar every time I changed versions of MySQL. So I tried connecting to MySQL 5 with an older version of the connector, and magically, the rogue queries disappeared.

Now this presented an awkward situation. The previous connector did fix things, but it didn't support a number of MySQL 5 features I wanted to take advantage of. And I don't like being forced into avoiding upgrades; certainly not for something as trivial as this. So I downloaded the Java source code to see if I couldn't figure this one out for myself.

One download, unzip and search later, I had my answer. The query string existed in the getCollation() method of com.mysql.jdbc.Field, which in turn was exclusively called by isCaseSensitive() in com.mysql.jdbc.ResultSetMetaData. Immediately I made the logical connection to ColdFusion 7's new result attribute for <cfquery>, which returns such metadata as, you guessed it, case sensitivity.

It turns out ColdFusion was asking Connector/J for the metadata on every field, which in turn triggered a SHOW FULL COLUMNS query for every varchar and text column returned. Since I was using case insensitive collation exclusively throughout my database schema (and I wasn't using the result attribute anywhere), I was able to recompile the connector with the isCaseSensitive() method neutered. Problem solved.

I filed a bug report with MySQL, and it has been resolved as of version 5.0.7 of Connector/J.

Read comments (14)