Carrot

Parser design

2009-10-01T22:35:00.000-07:00

The Lexer used a sort of trie-lite to do its work. The parser will be driven by a full-blown trie. Here's a graphviz diagram of it:

As you can see, the tag markup structure, which looks like

[thing]

is the most overloaded, but that's Huffman coding for you :)

Anyhow, the key to understanding this diagram is knowing that everywhere you see "printable", "whitespace", or "hex", that means "any number of these characters, consecutively". The only exception is "printable-1", which is read "one printable character".

That and the unicode entity stuff look like they create some really hairy exceptions, but the truth is that due to the way the reference implementation (spefically, the Lexer) operates, it'll all come in as one wad. A simple regex, combined with the lookahead token, will tell if it's a entity or not. It's shown exploded here, but those subtrees may be optimized completely out of the live trie.

Message passing

2009-09-13T17:16:00.000-07:00

I'm working on a primitive message-passing mechanism to allow objects to request that other objects execute methods on demand. Sort of a remote procedure call, you might say. The basics are as follows:

Every object which inherits from Carrot::Universal has a 'children' slot and a 'rpc_ok' slot. The first stores a reference to every object that the present object "owns", or has created. The second is a list of methods in the present object which are allowed to be called by this mechanism.
There's a 'pass' method, which creates a standard Carrot::Msg object and uses it as an argument to the 'catch' method of each object in the present object's 'children' slot.
The message created by 'pass' has a hashref instead of a string as its content. This hashref contains
1. The caller object's classname
2. The intended recipient class's name (will be matched as an ending regex, not a strict string equivalence, so 'Lexer' will work as well as Carrot::Lexer)
3. The method to be called
4. Arguments to the method
If the recipient classname matches the name of the called object, and if the given method is on the recipient's 'rpc_ok' list, then thy will be done.
Matching or not, the recipient object will pass the message on to all of its children.

Why? This is the mechanism that lets (definitely some, possible all of) the pragmas work. In the new design, the level at which pragmas are recognized (the Parser) is, for instance, 2 levels removed from where markup characters are tokenized as such (the Tokenizer). The possible solutions were

to implement a custom pass-along method for EVERY method that ends up being at greater than one remove from where it ends up being needed
to pass handles to objects to all other objects (AKA "the last design, to an extent")
to implement a generic message passing mechanism

The last one seems cleanest, most maintainable, and most useful in the long-term to me.

The Way Forward

2009-09-09T22:12:00.000-07:00

I don't mean how to complete Carrot. Though that is distressingly far from a fait accompli, I have somehow managed to convince myself that I'm capable of cracking all the remaining problems -- if by no other mechanism, then my letting it be ugly where it must in order to be done.

What I've been thinking of lately is the larger problem; the one that comes after Carrot; the one which Carrot is a gateway to solving. The archival and publishing problem. I've been thinking on it for years, and today I got a flash of insight which threatens to make the whole thing far, far simpler.

Every chunk gets a UUID.

This provides a system/implementation independent way to point at any piece of content in any document. It does explicitly make the chunk the smallest addressible portion, but it was already that way implicitly.

Another possibility: each chunk gets a SHA1 hash as well, enabling version-to-version delta compression at the chunk level. This way, you don't have to care where chunks might get moved to in a doc restructuring; so long as the hash is the same, the content is the same, and it can be mapped to transparently.

Parallel Development

2008-12-22T04:09:00.000-08:00

Now that I'm using git, I have powerful new options available for working on projects, like spawning as many single-feature development branches as I feel like. Today I spun one off and started overhauling the Carrot status system.

The first problem was that there were a lot of statuses, and while referring to them by numeric id sounds cool (it works for Apache), it's a little less than ideal when you're reusing ids between modules. I wrote the damn thing, and I was constantly having to refer to a wiki page to tell me what statuses meant. This has been (partly) fixed by moving the lists of statuses into the modules themselves, in a __DATA__ segment which populates a hashref at constructor time.

The other part of the fix is that statuses are no longer set by passing the 'status' method a number and having that be that. This had all the problems from the above paragraph, plus a complete lack of validity checking. Now statuses are set by passing the short "name" value which acts as a key on the statuses hashref. This makes status changes much more clear (status('EBADPERMS') vs. status(103)), and now passing an undefined name to status causes an abend.

A side-effect of this is that the code is now self-documenting with respect to its statuses, and the list of statuses can't get out-of-sync without the code exploding.

Lastly, the notion of a status being set has been divorced from the notion of something having gone wrong. Several of the Carrot modules now have non-error statuses beyond '0' for "still running" and '1' for "all done" (and, as a side note, '1' is no longer consistent for that -- this needs cleanup and '99' should be the new standard for "ops complete"). Since error statuses start at code 100, the status method now sets an error flag when a code above 99 is set. Soon, all modules will be updated to halt and return undef on error instead of on status.

EDIT: ONE YEAR ANNIVERSARY OF CARROT BLOG AND THE RESTART OF SERIOUS DEVELOPMENT

(...so far yet to go...)

DOM Update 1

2008-12-14T23:38:00.000-08:00

'nukenode' is no more. This is good. If a call to 'add' fails, that's really a fatal error -- there is no reason to cruft up the module with code which sloppily backs out the partial changes. I'm still hoping to factor away the partial changes bit and get back to having adds be atomic with respect to the datastore.

Movement

2008-12-13T02:17:00.000-08:00

First off, I'm now using git for local revision control.

Secondly, I've spent some time recently thinking about what the DOM should do -- oppose thinking about what's wrong with it right now -- and how to most efficiently make those things happen. I believe the result will be much slimmer code which is much more capable.

The DOM as it exists now has 2 fundamental problems. First, as noted previously, it was written over two years in advance of the Grammarian, so it's filled with bad guesses about how things would eventually work out. Second, I wrote it while having a fit of needing to prove to myself that I could write something like this, so it's full of questionable and/or mildly baroque design choices.

It'll be better soon.

Speaking of refactoring

2008-11-02T07:26:00.000-08:00

The stuff in the last post is all AFTER fixing the hash/hashref argument problem.

Also, Handler/Commenter.pm is no more. Its code and a genericized status() have been folded into Util.pm.

DOM problems in bringing Grammarian online

2008-11-02T07:09:00.000-08:00

As I'm 99% sure I've mentioned before, the DOM was the 2nd component of the Grammarian stack to be written. It got a syntax-wise overhaul approximately a year ago(!), but its capabilities were laid down in spring/summer of 2005.

Turns out I wrote in all kinds of crap that Carrot will never use. Perhaps I was thinking "this will be an awesome, general-purpose structured document framework which everyone will want to use", but that was a stupid thing to think. More likely I think I was simply doing everything I could figure out how to do, to make myself feel better about the enormity of the task. And I've ended up with all sorts of crufty special cases and exceptions which are now interfering with the proper operation of the system as it has ended up being in reality.

Interestingly, the test suite has been an accomplice of the problem in this issue, because a lot of the tests were written just to exercise those edge cases rather than to simulate actual system usage. I can forgive myself for this (this time) because I didn't know exactly what the system would end up doing, but there's still a really good lesson in here.

Also, the DOM TODO has exploded to fill a 4x6" index card. Looks like a severe refactoring is in order.

I knew this was going to happen

2008-10-19T11:56:00.000-07:00

Really, I did. I've been waiting on it since February, when I started work on the Handlers. At that point it had been about 2 years since the design of the DOM was laid down, though I had only just completed a code-wise and testing overhaul of it.

Long story short, the DOM was built at a time when I had no idea if my ideas for Carrot would ever work out, much less exactly how they would work out, and the Handlers were created with a far better understanding of how things should hook together. As a result, the DOM wants to have things added to it like this:

$dom->add( type    => $node_type,
           finfo   => \@fileinfo,
           element => $element_name,
           id      => $user_identifier,
           parent  => $pid,
           attrs   => \@attributes,
           content => $content );

while the Grammarian (being fed by the Handlers) wants to add things to the DOM like this:

$dom->add($node);

I'm not entirely braindead; '$node' contains everything that '$dom->add' wants, but it's packaged as a single hashref instead of a unravelled hash. This is far from calamitous, but it is irritating because simply passing '$node' is the right thing to do. This means that the DOM's test suite needs some rewriting.

And I'm still thinking of splitting the DOM in two.

And the DOM's POD needs a lot of rewriting.

And I should probably produce a dedicated POD which describes all the datastructures in the system.

Grammarian First Light

2008-09-26T23:13:00.000-07:00

At 02:14, 27 September 2008, Grammarian.pm successfully parsed the document pragma trigger of this document:

;;; hello, world
;;;
;;; simplest correct document

[[document title;'hello.carrot']]

hello, world! ;;; document plaintext

With this, 3 years of effort comes to fruition, and Carrot takes a giant step towards being real. Here's what happened:

A Grammarian object is instantiated
A Lexer object is instantiated within the Grammarian
The Grammarian, controlling the Lexer, reads through the document until something that isn't a comment or whitespace comes along
A Document pragma handler is instantiated
The Document handler is asked if it handles the token the Grammarian is looking at
If not, the document is nonconformant, a status is set, and processing terminates here
Else, the Document handler is passed control of the Lexer
If all goes well, the Document handler parses the contents of the document trigger into a datastructure, which is returned to the Grammarian
The Grammarian then instantiates a DOM object, giving it the results of the Document handlers's work as the root node of the new document
I do a little dance because it works It Works IT WORKS!!

Tomorrow I'll be writing (lots) more tests, and I hope to have a demo online by Wednesday, 1 October.

Grammarian Begin!

2008-09-16T16:09:00.000-07:00

There's real code in there now. Not much (just enough to generate comically bad coverage numbers), but it's a start. With the Handler tests' minigrammarian routine already proving the basic idea, lashing that together in a production sort of way should be pretty easy.

The worry for me is hooking it up to the DOM, which I haven't touched in quite a while now. My irrational mind fears there has been some drift in document node format between last-working-on-DOM and writing-flock-of-Handlers. My logical mind thinks "not so much", but even if it's wrong, that's a fairly minor issue.

A much larger change would be the thought I had the other night; that the DOM should be split into a storage access layer and the actual DOM accessor/traversal methods. This feels right, but it could well be premature optimization.

It'd be a good way to get the tests for it rewritten, tho :)

300

2008-09-14T22:40:00.000-07:00

Changeset 300 was just committed to the Carrot repo. It was a minor change to Handler.pm with decently large consequences. Following on from the last post, I was worried about another untested case: immediately nested tags, like this...

[foo [bar a;b blah blah]]

i was worried this might turn up an edge case in valid_ending_pos -- and it did, but not in the manner I had anticipated. I thought the immediate nesting, with no intervening attributes or content, might break something. That part worked just fine, but the cuddled terminators weren't behaving properly at all.

What should happen is

The Text handler sees ']]', quits processing, and returns
The Tag handler is called, sees ']]', which begins with its markup terminator, and claims responsibility
Tag consumes its terminating markup (']'), and pushes the remainder (also ']') back on to the Lexer's next-token stack
Tag is called again and the final ] is consumed

Instead, the first call to Tag was seeing ']]' and seemingly consuming both brackets. But only seemingly; what actually happened requires a little more granularity

Text sees ']]', pushes it onto the Lexer's next-token stack, quits processing, and returns
Lexer, knowing that it is at physical EOF, sets its status to 1 (EOF, but I have synthetic tokens in stack)
Tag is called, consuming a token from the stack, which happens to be the only token in the stack.
Lexer gives Tag the token and sets its status to 99 (EOF, no synthetic tokens)
Tag calls valid_ending_pos which has the statement 'return 1 if $l->status == 99' right up top. This is meant to let Triggers and Verbatim contexts always have a valid ending at EOF.
Lexer's status is 99
Tag does not execute the code at the bottom of valid_ending_pos, which performs the separation of terminating markup from the current token and the subsequent injection of the remainder onto Lexer's next-token stack (which would have reset its status to 1), allowing for cuddled terminators (and sloppiness like 'foo]bar').
The current token, containing the terminators for both open tags, is thrown away
The test suite calls Tag again to process the second terminator.
Lexer returns undef; tests fail

Any sufficiently complex system will always be able to bite you in the ass. Testing is your only defense. So write more tests, today! Buy war bonds! Victory!

Stopper?

2008-09-14T21:10:00.000-07:00

Some months in the past, back in April-June when I was dealing with the foo]] problem, I made a note to myself:

Handler valid_ending_pos woefully inadequate for Tags

But by the time I got around to reading my note, I couldn't fathom what the problem was. Clearly past-me had seen something, but present-me didn't see anything.

Today-me found it. On the Grammarian status code list, there is only one code specific to Tags. In section 3000:

400 Trigger or verbatim found in tag content

There is no testing for status 400 anywhere in the current suite. There is also no code which sets a status 400. Consider the following.

Lorem ipsum [foo bar;baz [[quux dolor sit amet, consectetuer
adipiscing]] elit.] Sed massa mi, dapibus.

This is doubly-illegal. It's forbidden by the grammar rule embodied in status 3400 as well as the rule which says that the opening markup of triggers must be the first thing on a line. Well, the trigger-specific infringement will be caught (status 3200, as it happens), but the 3400 violation isn't caught by any code at all. And what about...

Lorem ipsum [foo bar;baz
[[quux dolor sit amet, consectetuer
adipiscing]]
elit.] Sed massa mi, dapibus.

There. Now the 3200 violation goes away (this code is well-formed) AND the 3400 violation isn't caught. Problem! Isn't it?

That depends on whose job it is to know what's inside of what. This specific example could be caught by Tag handling code, but moving the word dolor outside the trigger...

Lorem ipsum [foo bar;baz dolor
[[quux sit amet, consectetuer
adipiscing]]
elit.] Sed massa mi, dapibus.

changes all that, because now the trigger is seen by the Text handler, not the Tag handler.

Now we see that, at its root, this problem is the same as the problem which led to the creation of the VerbatimText handler: a handler must be able to introspect the layers "above" it to make the correct decision in one specific case. And now, like then, I feel the proper thing to do is to stick with the design as it stands.

This means that the proper place for code to detect this grammar violation and throw the associated status code is the Grammarian itself. The Grammarian must be responsible for all such issues where knowledge of the node context stack is needed to make the right decision (just as it is in the case of VerbatimText, which the Grammarian will explicitly call instead of the regular Text handler when a Verbatim context is atop the stack).

Grammarian stub-out

2008-09-13T12:42:00.000-07:00

I just typed this:

use Firepear::Carrot::DOM;
use Firepear::Carrot::Lexer;
use Firepear::Carrot::Pragma::Document;
use Firepear::Carrot::Pragma::Include;
use Firepear::Carrot::Handler::Comment;
use Firepear::Carrot::Handler::Tag;
use Firepear::Carrot::Handler::Text;
use Firepear::Carrot::Handler::Trigger;
use Firepear::Carrot::Handler::Verbatim;
use Firepear::Carrot::Handler::VerbatimText;

It made me a little tingly. It's finally coming together.

857 tests, 911 LOC

2008-09-11T23:24:00.000-07:00

On the eve of beginning work on the Grammarian, this is where I stand.

Tonight tests were dropped in for the 600, 701, and 702 handlers in Document; VerbatimText got its own test suite (largely a copy of Text's, which it works almost-but-not-quite-exactly like, making for very good regression testing, I think); coverage went up on Handler and VerbatimText -- it's almost all greens now, and no only one orange block in the "real" modules.

Document pragma validation

2008-09-09T23:00:00.000-07:00

Finally getting back to work. As always, it's simpler than I thought it would be. Testing tomorrow. Then, the Grammarian

Tricksy

2008-08-21T16:24:00.000-07:00

After my last post I sat around thinking about the implementation of various things, and I started to come up with some pretty clever ways of doing things. Of course, we all know how I feel about clever, so I'm really thinking hard about these. Also, how would it look if the Voice of Dissent hauled off and started doing things just because he could?

Magic Document Triggers

The first thing I thought about was the document trigger. Since the day I thought of the mechanism which it embodies, it's been declared Mandatory; you can't have a Carrot document without a document trigger. But also on the plan from early times is a tiered configuration system, and I realized that this combined with the fact that the processor can treat arbitrary strings as files to be decomposed into tokens (thanks to PerlIO) meant that a synthetic file could be assembled which contained a document pragma, built on-the-fly from a user's personal configuration.

This synthetic file would then be injected into the input list before processing began, putting it right where it should have been all along. Document export would take care of generating proper, sharable source files, and authors wouldn't have to type the same block into the beginning of every document they wrote. The problem comes when people don't export before sharing, and the person on the other end gets a document which contains entities their system doesn't recognize, or is written against a version of Carrot they don't have installed or...

Decision: if implemented, this should not be default behavior. It should be a power user feature which must be enabled in one's configuration.

Positionally Independent Data Pragma

The data pragma is an interesting thing, I think. It's basically the mechanism through which BLOB-equivalents are streamed into Carrot documents. As such, I've considered many uses for it but the two which will see use first are really different sides of the same coin: embedding media files and embedding Carrot extensions (both tied to Document Export).

The idea is that when you want to share a document, you tell Carrot to "export" you a copy -- to generate a version for the use of other people, who may not have access to all the resources you have locally. Since the system knows what's "stock", it examines the document for everything that isn't, and these bits are turned into data pragma which are written into the new copy of the document, and references to the original resources are rewritten to point at the data segments (where applicable).

The data segments themselves, whether they contain an image or an audio file or a Radish module, are compressed (again, where applicable) and BASE64 encoded. The BASE64 representation is then stowed as the content of a data pragma -- and so all resources become local to the document, at the cost of storage (but who cares about that these days?)

Here's the new bit: I realized a good while back that since the Grammarian has to read the document pragma before the rest of its processing chain can be instantiated (because the document pragma contains directives which may affect those tools). I realized this morning that I could use that delay to actually do 2 full passes over the document, scanning only for document and data pragma on the first pass. This would remove the requirement that data pragma appear before (that is: physically above in the source) any references to their content.

This sounds pretty sweet, but it increases processing time, and it brings up the new wrinkle of how not to hit the data pragma on the second pass. Do you special-case them and ignore? Do you physically remove them from the file during the first pass by doing a copy-on-read and excepting the pragma you're catching the first time 'round?

Decision: too big a problem for too small a win. Not gonna do it, for now.

Frighteningly close

2008-08-20T21:14:00.000-07:00

Phase I of Carrot development is, I have realized, very close to completion. The only things left undone are the document pragma and the Grammarian -- and both of these have been at least partially implemented or prototyped already.

On the one hand, this is a very pleasant thought. On the other, it means that the rough, unyeilding wall of language design -- which had, to this point, merely been staring me in the face -- is now pressing hard against my shoulders.

The pragma, due to the way they operate (at the Grammarian level), must have their validation routines hardcoded. And, as the document pragma's job is to set data about the document itself and to modify the initial behavior of the Carrot processing chain, its contents and their validation have a lot of bearing on everything that follows.

This will all make more sense when (1) there's a demo and (2) Radish comes along in Phase II, I swear :)

Problem solved; next up

2008-08-15T22:46:00.001-07:00

I chose to create a new class, VerbatimText, which is solely responsible for handling text inside Verbatim chunks. This adds a small amount of simple special-casing to the Grammarian, but the alternative was to add probably-complex special-casing to the Text handler and coming up with a mechanism for it to know what's going on at the Grammarian's level.

This felt like the far poorer choice, because as things stand, no modules are aware of what's happening "above" them in the stack -- things can only see down into the modules they're using. I think this is Good.

Anyway, that's done, and it's tested and working. Onward to the Pragma!

Oops (smaller)

2008-08-12T17:54:00.000-07:00

Integration testing has revealed that I forgot to tell the text handler how to parse things inside Verbatim chunks.

I can think of a number of ways to handle this, mostly kludgey, but it strikes me just this moment that a pretty clean way would be the creation of a second Text handler, with modified opening (undef) and closing (Verbatim close) markups, to be called from the Grammarian whenever Verbatim is atop the context stack.

Hmmmmmmmmmm

Huge step forward

2008-08-09T23:46:00.000-07:00

Carrot now has a small set of handler integration tests, and they all pass. This neccessitated the creation of a "minigrammarian", which, while having no document intelligence as the real Grammarian will, validates the concept of the Grammarian -- and the tests validate the "flock of handlers" concept.

The test was to parse the string

"preceeding text [tag content content content]]]\nNew para"

which was properly rendered into

A TEXT chunk, 'preceding text'
A TAG
A second TEXT chunk, 'content content content'
A terminal TAG markup (']')
A terminal TRIGGER markup (']]')
And a third TEXT chunk, 'New para'

This is awesome.

Small progress is better than no progress

2008-07-26T00:21:00.000-07:00

One more ticket closed: #17, which pointed out that there was, until 2 days ago, insufficient checking on the markups being passed to Handlers, and no tests on what checking there was (much less everything there should have been).

This has now been rectified, and one more barrier in the way of the Grammarian demo has been pushed aside.

On the topic of the demo itself, I've gone crazy enough to talk myself into creating a vizualizer in SVG. Making simple SVG is really, really easy, so I'm hopeful that given a month of noodling about I can create a basic-but-fun datastructure browser. Because let's face it, a demo whose only product is some debug text and a datastructure is not exactly what captivates the kids these days. We're not working on TRS-80s anymore :(

All tests passing (again)!

2008-07-17T18:47:00.001-07:00

Finicky, finicky stuff, but everything is a go again, and the codebase as a whole is better for it.

Yay, correctness!

This weekend I plan to push coverage back to 100% on all "finished" modules before restarting work on the Include pragma.

Oops

2008-07-04T21:22:00.000-07:00

No, all tests are not passing.

The Text handler had a spurious 'exit;' in it, which was choking off all the REAL tests, nearly all of which were failing.

Looks like its problems are also being caused by 'endnode' -- but that's a well understood problem at this point, and the interactions here are far, far simpler than in Handler.pm. I'm hoping to have it fixed by tomorrow night.

All Tests Passing

2008-07-01T11:57:00.000-07:00

Finally, all the original tests for Carrot (as of April!) are passing again. New coverage reports have been generated, and will continue to be as work progresses.

There are a lot of new tests that need writing before work on the Pragma is begun again, and not just because some existing modules are below 100% coverage due to rewrites -- during this long process I noticed several ways in which the existing suite was flawed. Having test coverage is excellent, but it's still no guarantee that you're testing for everything that can go wrong (of course!).

A great success!

2008-06-22T20:37:00.000-07:00

Failed Test               Stat Wstat Total Fail  Failed  List of Failed
-------------------------------------------------------------------------------
t/03.Handler-3-Verbatim.t    5  1280    56    5   8.93%  19 29-30 55-56
t/03.Handler-4-Tag.t         4  1024    42    4   9.52%  17 20 29-30
t/03.Handler-5-Text.t        1   256    15    1   6.67%  1
t/04.Pragma-2-Include.t      6  1536    34    6  17.65%  3 13-14 24 33-34
Failed 4/13 test scripts, 69.23% okay. 16/608 subtests failed, 97.37% okay.

This is down from about 30% (per-test) failure, peaking at over 60% for some modules, 2 days ago. I believe I have largely fixed the problem.

Almost there

2008-06-01T22:56:00.001-07:00

See the previous post for details and linkage. Tomorrow evening I hope to wrap up work on Handler->lex, and after that there's just cleanup and the writing of many more tests in an attempt to abuse more bugs into surfacing.

After this, it's time to write the document and include pragma, which should be comparitively simple, and then it'll finally be the Grammarian's turn. Once that's done, there's just building the demo and the 0.2 release.

Then the hard problems start again :)

Beginnings of a solution

2008-05-26T08:24:00.000-07:00

After spending most of yesterday studying the three methods in Handler.pm which, together, create the error condition described in the previous few posts, I began to see a way out.

Day-to-day specifics on this can be seen at the project issue tracker, Issue 21 specifically.

I Can Has Logo!

2008-05-07T06:00:00.001-07:00

Thanks to Dan, as usual, for his excellent work.

Problem (Cont'd)

2008-04-18T23:41:00.001-07:00

This has turned out to be rather thorny, if only because I'd like to try and solve it logically rather than just shuffle code around until oit works.

The actual problem is in an interaction of the lex(), buildattr(), and endnode() methods of the original Handler. This code was written rather hastily, and without much forethought, and it shows now that I have an edge case problem to fix.

My plan is to sit down tomorrow, carefully plot my way through the code (on paper) adn then come up with a solution before typing anything. I've been doing a lot more of this paper prototyping lately, and it's been serving me really well.

Edge case problem

2008-04-14T21:01:00.000-07:00

Tonight I found a flaw in chunk termination parsing. This doesn't do the right thing:

[[foo bar;baz quux]]

The problem is that the method which detects the ends of chunks which are currently being processed declares this chunk to be completely parsed when the terminator is seen. It isn't, though, as "quux" is trigger content, and is not handled by the trigger handler -- it is taken care of by the text handler.

The proper thing to do is to declare the chunk incomplete, return the node as it stands, and for the Grammarian's processing loop to take back over (and then hand off to the text handler).

This issue survived so long because... well, I'm not sure how I managed to not have a test case like this in my suite of almost 650 tests, but I didn't, so that was problem number one. Problem number two is that integration testing of the handlers has not yet begun, though it is perilously close.

The correct implementation of the solution to this problem is not yet known.

Mood: :-/

How Carrot Works -- I: Overview

2008-03-15T21:42:00.000-07:00

Welcome to the first article in an ongoing series, in which I attempt to actually explain the stuff that I usually blather on about without backreference or elucidation of any sort.

This is a high-level overview of the extant design for the Carrot processing flow. For a basic overview of the language itself, see the 10km document.

The Grammarian
Compilation of a Carrot document is a 2 phase process. In the first phase, a subsystem called the Grammarian examines the document for well-formedness. That is, it examines the document to make sure that it is written in a grammar of Carrot. The Grammarian proper is a message-passer/traffic cop between a small flock of components which handle the majority of the actual work of this phase of processing.

The Lexer does all input filehandling and decomposes the resultant stream of text into tokens. There are only three kinds of tokens: whitespace strings, nonwhitespace strings, and newlines.

Tokens from the lexer are examined by a group of Handler components. There is one handler for each type of Carrot markup, and one each for special cases like the document and include triggers (the pragma). These handlers construct nodes from the tokens, with each node being a lexical chunk of the document and all available metadata for it.

These nodes are then passed to the DOM (Document Object Model) component, which does the bulk of well-formedness checking and then stows properly constructed nodes into the document tree (which the DOM also provides read access to).

Assuming all goes well, the entire source document will be transformed into a datastructure which encodes the content and structure of the original, along with explicit and inferred metadata for later processing and (possible) error reporting.

The Ontologist
Phase 2 begins with another subsystem, called the Ontologist, beginning a directed walk of the DOM's tree. It is the Ontologist's job to make sure that the document is written in a valid dialect of Carrot. This is neccessary because, in its purest form, Carrot is, like XML, a language construction kit.

In any event, the Ontologist examines each node in isolation (This node says it's a trigger and its element type is "foobar". Is there a foobar trigger in my current dialect? This node contains an attribute "baz". Is that attribute valid for this element, and is its value of the defined type and within any defined bounds?) and in relation to other nodes (Is this element allowed within the current scope(s)?).

The Ontologist's validity rules are expressed in a Carrot grammar called Radish, which will be the topic of an entire post later on. (Yes, Carrot bootstraps itself, using itself.)

If the Ontologist successfully walks the entire tree, then the document is both well-formed and valid, and compilation is complete. From this point on, it's about what the user wants to do with the document. And that'll be the topic of the next How Carrot Works post.

Generic Handlers complete. Next up: Pragma

2008-03-14T22:03:00.000-07:00

The regular Handlers are complete and tested (though not (quite) yet tested to 100% code coverage). Text.pm is 36 lines, according to sloccount. Maybe I'm finally getting good at estimating things relating to code.

In my next update, to be written when I'm more awake, I shall talk at some length about exactly what the hell is going on here.

I'm seeing weirdness with Devel::Cover and subclasses. It refuses to believe that I'm testing methods which subclasses redefine. This is very unhappy-making :(

Shock and Awe

2008-03-11T22:38:00.000-07:00

When I started work on the handlers, I figured I could get maybe three-quarters of the code for Triggers and Verbatims shared through the generic Handler, and maybe half of what Tags would need, and perhaps one-quarter of Text chunks.

As it turns out, with not much effort, and very little in the way of redundancy or special-casing, 100% of the code for Triggers, Verbatims, and Tags is shared. Their modules are bare subclasses of the Handler superclass. The empty modules are still neccessary, though, because of the handful of places where the shared code does behave differently based on what class it's executing as (and it leaves a clean, clear maintenance path for when I start finding the things I've missed and the second, customized parsing stage becomes neccessary).

So all my careful work in designing that two-stage parsing pass was either wasted or wildly successful, depending on your point of view :)

The Text handler does actually get rewritten methods -- two of them -- and one unique to itself, but it's far simpler than the other handlers, so the loccount for these additions will still be under 50, I think.

All the handlers except Text are testing clean right now as well. Handler.pm's coverage is up to 91% overall. In a scarily short time, it will be time to lash the handlers to the Grammarian (which is really to say: to the DOM).

Subclasses ahoy

2008-03-07T23:22:00.000-08:00

Since my last post, the generic Handler has been tested about as far as it can be in a standalone more, and coding has begun on the specific subclass handlers (Trigger, Tag, Verbatim, Text, Document).

I'm not entirely sure yet, but I think the Use and Import pragmas will be implemented as subclassed handlers, acting in the same way as the Document trigger.

At the moment, things are moving quickly. I'm not sure how long this will last.

Following up on that last note

2008-02-10T16:35:00.000-08:00

The generic (superclass) Handler is finally shaping up, with no significant changes to its design. As of right now, it successfully parses this trigger:

[[document;quux ;;; multiline with comments
title;Foobar date;now;;;multiple comments, actually
author;'Shawn Boyette's Dog, Esq.' ]]

Though I shouldn't be surprised, I'm very happy that things like "date;now;;;multiple" are being handled correctly. This batch of hard problems is nearly solved, which is both a relief and worrisome, because there are so many more to tackle :)

It's also up to 68% test coverage, but that's being inflated by sub coverage, and there's a lot of exception catches yet to be written.

First Node

2008-02-09T23:48:00.000-08:00

Much work to be done yet, but:

http://code.google.com/p/carrot/source/detail?r=67

Another "breakthrough"

2008-02-07T09:21:00.000-08:00

In which I continue to realize things long after they should have become apparent

Of late, though I have been working (which is to say: coding) on the Handlers, I have been working (which is to say: thinking) on Radish. Tied directly to radish is the problem of how to parse the structured text occuring inside some triggers.

I've done so much deferral of solving this problem that my thinking was still stuck in the pre-2004 era, when everything was line-oriented and based around decomposition of lines with regexes. Not until this morning's shower did I realize that I have a perfectly good LALR lexer -- which can be fed arbitrary strings as well as files -- already coded and waiting to be used.

What this means is that structured text doesn't have to be ridgidly line-oriented the way many wiki dialects are; whitespace can be insignificant, as it is with most programming languages. A table, for instance, could (hypothetically) look like

r1c1 ;; r1c2 --- r2c1 ;; r2c2

r1c1 ;; r1c2
---
r2c1 ;; r2c2

and so on. Duh.

Also, it strikes me just now that Handler->lex should perhaps use substr() where possible instead of regexes. This would cut down on the need for escaping and possible complications arising from it.

Software Engineering

2008-01-25T08:33:00.000-08:00

The core routines of the Handler superclass have been in place for a week (with under a week left to deadline), but I produced no useful work this week. Eventually I realized it was because I was fretting about the quality of the code in the Handler. It works, sure, but it works in a way that I've come to view as lacking, and which is unacceptible in this project.

It has no engineering in it. It's just sketched out and working, but it ONLY minimally works, and there is NO error handling, and... It's simply not on par, quality and reliability-wise with the Lexer and DOM code (not that I'm pretending they're perfect).

To fix this, I sat down and added a huge new section to the status codes list. Now that the Handler works, this list (section 3000 of it) is the spec for making it properly engineered code. It's also the roadmap for a test suite. I believe I might do my first bit of actual test-driven development, contra my more usual "Okay, this new little chunk works; time to write a test for it" method. (What's a good, marketable term for that, anyway? Would know-nothing trendwhore coders buy into "Test-backed Microdevelopment"? Would management pay $3500 to send their dev leads to a 2-day seminar on TBM?)

Lexer again?

2008-01-16T20:53:00.000-08:00

Working on the Handler made me realize that the Lexer needed some teensy-tiny functionality adds. They are in now, and tested already. In addition to making the calls to the handlers cleaner, they should actually make error reporting nicer in at least some cases.

Away we go

2008-01-14T05:55:00.000-08:00

I admit it: I was worrying that my holiday burst of inspiration and work ethic was an abberration which wouldn't soon be repeated. Having overhauled the Lexer and DOM and gotten them both up to 100% test coverage, I couldn't seem to get going on actual new code.

Sure, I'd spend a couple of hours every day or two of the last week-ish writing down bulleted lists or flowcharts of logic flow in my trusty quadrille notebooks, but I was frozen up as far as coding went. It just didn't all gel in my head yet.

Saturday night I felt like I'd gotten it all (where "it all" is the interactions between the Grammarian and its flock of subclassed Handler modules) worked out, and part of me was very much wanting to get going on the code, but another part of me was decidedly disinterested and just wanted to play video games. So that's what I did Saturday and most of Sunday, but I wasn't enjoying it all that much, because the part of me that wanted to be coding was busily yelling at the rest of me that I was a gigantic slacker who was going to completely fail on a self-imposed deadline and new year's resolution and god I just suck so bad why do I even bother talking to me?

I was exceptionally grumpy on the drive back to Atlanta.

But just before bedtime I finally managed to scrap together just enough code in the Handler superclass to write the first few tests for it. And then I subclassed it into the beginnings of the Comment handler, and wrote a handful more tests for that.

The game, once more, is afoot.

Today's Progress

2008-01-09T22:29:00.000-08:00

The DOM is up to 98.9% coverage, with the remaining misses waiting on specific fixes to come along later.

I've started on a series of small, lightweight introductions to Carrot. That's way harder than the design and coding.

And finally, not something I did but something I realized today: It's time to start designing the language, and not just the compiler.

Planning, Testing

2008-01-09T06:57:00.000-08:00

I've been working (slowly) on pulling coverage up. Just this morning, Lexer finally hit 100% across the board. The DOM still has some way to go, mostly in the coverage of repetitive checks on statuses and the like.

I haven't written much Handler code yet. Despite having some good ideas about things, once I started to code those ideas I realized that they might be good but they were also complex. At this layer, modules can't stand alone anymore (unlike the Lexer and DOM, which are dumb functional units that sit below everything, operating free of external context). Now things are starting to pass data back and forth in ways that affect each other's operation. Given that, I've been doing a lot of work in a quadrille notebook and rather little in Emacs, but it's all good and it's very valid progress.

The thing I'm happiest about is the (apparent) power of the framework I'm building. Though there are many, many, many things left to be done, it is becoming easier and easier to see how to implement things I once thought would be very difficult. I'm almost ready to believe this was all a good idea :)

Rewrites complete

2008-01-03T23:39:00.000-08:00

The DOM and Lexer mdifications are complete, barring a tiny bit of Devel::Cover-fueled test writing on the DOM. I've also written a wrapper around D::C and upload its report to the Carrot site.

This weekend work on Handlers begins.

Resolution

2008-01-01T14:21:00.001-08:00

In the past 4 days I've driven all over the state and still managed to get tons of work done on Carrot. What started as minor fixup on the DOM module ended up being a wholesale, in situ rewrite. The resulting code is much more regular and has a lot less special cases, and should be generally more maintainable in the future. My tendancy to view writing test suites which are as complete as possible as a sort of software engineering minigame paid off bigtime in this effort Even though it needed many (repetitive) modifications itself, the existing test suite was invaluable for turning up regression errors as well as plain old dumb mistakes made while coding in the pre-dawn hours.

Though there is a small amount of cleanup left before this effort can really be called "done", it's very close, and I know what comes next: The Grammarian and its attendant Handlers, which are pretty well planned out.

I'm only going to make one resolution for 2008 -- we'll see if there's a need for others to follow. I hereby resolve to have a public Carrot grammar validator in operation by midnight, 1February, 2008.

DOM, take two

2007-12-28T07:20:00.000-08:00

Last night at Too Damn Late[TM], I got some really good ideas which amount to a refactoring of the DOM.

The accessors should be smart get/set types
VERBATIM chunks should be containers in the manner of TRIGGERS rather than special cases of TEXT chunks
I was misusing the 0E0 value; it should be replaced with 'undef'
Now that both the DOM tree and the text stowage structure are arrays instead of hashes, their additive methods can be rewritten with simple push()es instead of index accesses
...and the associated node tracking scalars can be gotten rid of

And then a lot of little things auxilliary to these points. And rewrites of the POD to match it all. And a likely painful overhaul of the test suite.

Oh well. That's progress. The Grammarian and its Handlers follow this.

Grammarian flowcharts

2007-12-25T13:32:00.000-08:00

Last night, as I finished up porting issues from the old Trac install to googlecode, I began pondering one of them, and ended up with some really good ideas. It was all about the Grammarian, and the new strategy of it doing its work through independent modules rather than a giant wodge of code in the Grammarian module itself.

Basically the Grammarian acts as a traffic cop and crossing guard for the Lexer and DOM while a series of Handler modules hands off the heavy lifting between themselves. I sat there, into the wee hours of Xmas morning, drawing revision after revision of a logic flowchart for the design. It seems like pretty good stuff at this point -- now I just have to get the DOM back on its feet so I can move on to this work.

And after that, it'll finally be possible to show off a Carrot validator!

DBM::Deep

2007-12-23T18:14:00.000-08:00

It turns out that NDBM key/value pairs can have a maximum length of 1023 characters, combined. This is, to say the least, unsuitable for my purposes, as I had been using NDBM for storage of document text chunks.

I asked for alternatives a while ago on #perl, and one person mentioned DBD::Deep. At the time I was leaning towards SQLite or a custom tie() job, but decided to give D::D a look before making a decision. I'm glad I did. Today I'm refactoring the DOM to use it instead of NDBM (which only ever worked because the Lexer and DOM test files are so minimal).

Yay!

2007-12-21T07:02:00.001-08:00

I've been awarded the project name "carrot" over at googlecode, and now things are ready to roll.

Here we go!