I have made some minor site tweaks today.
The last point was the one which required the most work. I realise that there are parsers out there which do the job, but I wanted something that was restrictive to the point of being puritanical so that my precious valid XHTML can't be disrupted by commenters who don't know how to mark stuff up. The new parser can handle any legitimate combination of the <p>, <em> and <strong> tags, as well as the HTML character entities for <, > and &, namely <, > and & respectively - nothing else whatsoever is permissible. By only allowing a whitelist of tags and entities rather than blacklisting exploits as and when I find them, I find there's much less logical room to manoeuvre for inserting malicious markup and code. In particular, tag attributes are not permitted (you can't even add extra whitespace inside your tags, which is legal in XHTML - sorry, but this cuts out malicious CSS like style="font-size: 3000%").
I make no apology for how punishingly restrictive the new parser is. You can still, naturally, use the simple old one, which just turns your line breaks into <br />s, but doesn't allow bold or italicised text. Meanwhile, any of you who fancy trying to crack this thing open are welcome to try to poke holes in the new code, using the discussion below. Hope it holds up!
Okay, I have fixed a bug which was double-escaping special characters. Amazingly, it turned out that characters were being put through htmlspecialchars() somewhere between being POSTed as form data and being available to PHP's $_POST global variable. Being completely unable to find any kind of documentation or bug explaining this behaviour, I eventually magically solved the problem by putting header('Content-type: text/html; charset=UTF-8'); at the beginning of each page load. Why this worked, I don't really know.
It is also now impossible to submit certain special characters which are not permitted in XHTML documents, those between hex codes 0 and 1F. Unfortunately, I have discovered that PHP's Unicode support is extremely poor, varying between experimental and non-existent, so the treatment of special characters is not currently to my liking. There's no function to, for example, turn a single character into its hex sequence and back again, or to check that a specific hex sequence is defined in Unicode or not.
The HTML parser I had written was a little unwieldy and it looked like it was going to be surprisingly difficult to maintain. I did some research into formal grammars, formal languages, context-free grammars and languages (which HTML is), regular grammars and languages (which HTML is not), formal language parsing and parsers. I formulated the small permissible subset of HTML which makes up comments on this site as a context-free grammar, and then rendered it into Chomsky Normal Form which allowed me to implement the CYK algorithm. Unfortunately, this algorithm has two major drawbacks: it operates in O(n3) time (a comment twice as long takes eight times as long to parse) and it has absolutely no capability to tell the user how, exactly, parsing has failed.
I didn't release this new parser "into the wild" while I mulled over this problem. I quickly realised that the interesting thing about HTML is that there is only a single precise parse tree - while it is possible for the same HTML string can be correctly produced in many different ways, the parse tree arising from this production is always identical. I realised that the reason for this is that all the possible non-terminal characters in this CFG are either left-handed / producers or right-handed / productions - in rules of the form A → BC, any given non-terminal character either always appears as B or always appears as C. This sets much greater constraints on how a string can be formed. For example, if the string begins with a right-handed character C, then you know that the string cannot be formed because there is no left-handed B to produce at the same time.
In addition, if the rules are formulated so that BC is a unique key in production rules, then each two-character combination can only be formed in one way, from A (or not at all). So, when parsing, if you encounter BC, you KNOW you can INSTANTLY reduce that to A and continue to parse, no questions asked, no problems raised. Or, if you encounter a combination DE, where the handednesses match but there is no production rule, you KNOW that that combination can NEVER be produced, so you can instantly throw an error. As a result, you can now parse the string in linear time.
I implemented this last night. I can pin this down in more specific terms if anybody cares, but I'm pretty sure I've simply independently discovered one of these (though at first glance it's not easy to tell which one).
You can now use <br /> line breaks, and adding more formatting rules is now trivial for me (if I ever decide to).
I've also added some cunning .htaccess and PHP redirection rules to harmonise and homogenise URLs. URLs of the form "http://qntm.org/index.php?destroy" and "http://qntm.org/?destroy" will still work, but give permanent redirects to the canonical "http://qntm.org/destroy" page. This little niggling extra character in URLs has been something I've wanted to excise for at least a year, but never got around to it.
The secret? Use .htaccess to redirect to a PHP script, then handle the request URI using nice easy PHP. Much easier than grappling with Apache directives.
Discussion (63)
2010-01-10 18:10:18 by Ejl:
2010-01-10 19:09:33 by Eskivole:
2010-01-10 19:11:43 by qntm:
2010-01-11 00:17:37 by Raphfrk:
2010-01-11 01:32:28 by Thrack:
2010-01-11 01:38:29 by Lucas:
2010-01-11 02:54:51 by dankuck:
2010-01-11 03:03:07 by dankuck:
2010-01-11 03:33:34 by dankuck:
2010-01-11 03:35:56 by dankuck:
2010-01-11 03:46:58 by Sgeo:
2010-01-11 03:47:00 by dankuck:
2010-01-11 03:48:09 by Sgeo:
2010-01-11 03:57:41 by Thrack:
2010-01-11 04:03:09 by Thrack:
2010-01-11 04:05:03 by dankuck:
2010-01-11 04:06:04 by dankuck:
2010-01-11 04:10:56 by Thrack:
2010-01-11 04:16:40 by Thrack:
2010-01-11 09:20:06 by qntm:
2010-01-11 10:15:58 by qntm:
2010-01-11 14:57:03 by Warrigal:
2010-01-12 10:22:44 by David:
2010-01-12 10:30:55 by David:
2010-01-12 10:48:13 by qntm:
2010-01-12 18:06:06 by ejl:
2010-01-12 18:41:11 by qntm:
2010-01-14 01:01:39 by ejl:
2010-01-14 01:02:11 by ejl:
2010-01-16 17:15:28 by qntm:
2010-01-16 17:19:16 by qntm:
2010-01-20 12:19:35 by CapnBaht:
2010-01-20 20:20:06 by Sgeo:
2010-01-20 20:21:56 by qntm:
2010-01-21 14:51:53 by qntm:
2010-02-04 19:12:02 by qntm:
2010-02-04 19:12:56 by qntm:
2010-02-04 22:58:09 by Samm:
2010-02-05 10:42:26 by qntm:
2010-02-05 14:04:18 by Robin:
2010-02-05 14:20:56 by qntm:
2010-02-06 00:08:17 by frymaster:
2010-02-06 00:13:37 by qntm:
2010-02-06 00:15:16 by frymaster:
2010-02-06 02:43:26 by YarKramer:
2010-02-06 07:24:42 by Lar:
2010-02-06 09:56:32 by Samm:
2010-02-08 04:10:20 by Lar:
2010-02-08 07:38:28 by Ken:
2010-02-08 09:12:01 by qntm:
2010-02-08 09:14:11 by qntm:
2010-02-08 23:01:18 by qntm:
2010-02-12 10:02:50 by test:
2010-02-12 10:04:34 by test:
2010-02-12 10:42:39 by qntm:
2010-02-17 23:47:42 by Lar:
2010-02-18 00:41:44 by Lar:
2010-02-18 09:19:08 by qntm:
2010-02-18 14:55:56 by tute:
2010-02-18 15:01:18 by qntm:
2010-02-18 15:11:35 by Lar:
2010-02-18 18:07:50 by qntm:
2010-02-22 08:08:20 by test: