ann.crk

# Copyright 2011-2012 Google Inc.
# Copyright 2012 Conrad Steenberg <conrad.steenberg@gmail.com>
# Copyright 2012 Arno Rehn <arno@arnorehn.de>
#
#   This Source Code Form is subject to the terms of the Mozilla Public
#   License, v. 2.0. If a copy of the MPL was not distributed with this
#   file, You can obtain one at http://mozilla.org/MPL/2.0/.
#
# Implements some basic annotations that no one should be without.  Included
# are:
# @define name(arg, ...) { contents }
#   defines a macro with the specified arguments (you can then use the macro
#   as @name(args...))
# @interface I { ... }
#   Defines a class as an interface, allowing you to safely do multiple
#   inheritence.
# class A : Object @implements I, J { ... }
#   Makes a class implement the list of interfaces that follows them (this
#   mainly entails doing normal class derivation and implementing the
#   'get<interface>Object()' method.
# class A @impl I, J { ... }
#   Equivalent to "class A : Object I, J { ... }".  Shorthand for the most
#   common case.

import crack.compiler CrackContext, Location, Token, TokSerializer,
    TOK_BREAKKW, TOK_CLASSKW, TOK_COMMA, TOK_CONTINUEKW, TOK_ELSEKW, TOK_FORKW,
    TOK_IFKW, TOK_IMPORTKW, TOK_INKW, TOK_ISKW, TOK_LBRACKET, TOK_LCURLY,
    TOK_LPAREN, TOK_NULLKW, TOK_ONKW, TOK_OPERKW, TOK_POPERRCTX, TOK_RBRACKET,
    TOK_RCURLY, TOK_RETURNKW, TOK_RPAREN, TOK_STRING, TOK_WHILEKW;
import crack.cont.array Array;
import crack.cont.treemap TreeMap;
import crack.io cerr, FStr, Reader, StandardFormatter, StringFormatter,
    StringWriter, Writer;
import crack.lang die, AssertionError, CString, Exception, Formatter,
    IndexError, InvalidArgumentError, InvalidStateError;
import crack.runtime free;
import crack.serial SerialReader, SerialWriter;

const NOT_FOUND := 0xFFFFFFFF;

## Serial writer with some additional facilities to simplify macro
## serialization.
class MacroSerializer : SerialWriter {
    TreeMap[String, uint] sourceNames = {};
    uint lastIdx;

    oper init(Writer dst) : SerialWriter(dst) {}

    void writeSrcName(String name) {
        idx := sourceNames.get(name, NOT_FOUND);
        if (idx != NOT_FOUND) {
            write(idx);
        } else {
            # new name, write the index and the
            sourceNames[name] = lastIdx;
            write(lastIdx++);
            write(name);
        }
    }

    void writeLocation(Location loc) {
        writeSrcName(String(loc.getName()));
        write(uint(loc.getLineNumber()));
    }
}

## Serial reader with some additional facilities to simplify macro
## deserialization.
class MacroDeserializer : SerialReader {
    CrackContext ctx;
    Array[String] sourceNames = {4};

    oper init(CrackContext ctx, Reader src) : SerialReader(src), ctx = ctx {}

    String readSrcName() {
        # read the index
        idx := readUInt();
        count := sourceNames.count();
        if (idx > count) {
            throw IndexError(FStr() `Invalid source name index: $idx\n`);
        } else if (idx == count) {
            name := readString();
            sourceNames.append(name);
            return name;
        } else {
            return sourceNames[idx];
        }
    }

    Location readLocation() {
        return ctx.getLocation(readSrcName().buffer, int(readUInt()));
    }
}

class Node;
class NodeIter;

@abstract class NodeList {
    @abstract void pushHead(Node node);
    @abstract void append(Node node);
    @abstract Node popHead();
    @abstract void writeTo(MacroSerializer dst);
    @abstract NodeIter iter();
    @abstract Node getLast();
    @abstract Node getFirst();
    @abstract void expand(CrackContext ctx, Array[NodeList] args);
    @abstract String toString(Array[NodeList] args);
    @abstract Location getLocation();
}

@abstract class Node {
    Node next;

    void expand(CrackContext ctx, Array[NodeList] args) {}
    String toString(Array[NodeList] args) {return null;}
    @abstract Location getLocation();
    @abstract void writeTo(MacroSerializer dst);
}

class NodeIter {
    Node node;
    oper init(Node node) : node = node {}
    void next() { node = node.next; }
    bool isTrue() { return node; }
    Node elem() { return node; }
}

Node _readNode(MacroDeserializer src);

## A list of tokens.  These are typically stored in reverse order of the
## actual order of the tokens so that they can be easily "put back" into the
## token stream (after putBack() they will be in the correct order once again)
class NodeListImpl : NodeList {
    Node first, last;
    Location loc;

    oper init() {}
    oper init(Location loc) : loc = loc {}

    void pushHead(Node node) {
        if (first) {
            node.next = first;
            first = node;
        } else {
            first = last = node;
        }
    }

    void append(Node node) {
        if (last) {
            last.next = node;
            last = node;
        } else {
            first = last = node;
        }
    }

    Node popHead() {
        if (first) {
            if (last is first)
                last = null;
            result := first;
            first = first.next;
            return result;
        } else {
            return null;
        }
    }

    oper init(MacroDeserializer src) {
        # get the number of nodes in the list
        count := src.readUInt();
        while (count--) {
            append(_readNode(src));
            #cout `remaining = $count\n`;
        }
    }

    void writeTo(MacroSerializer dst) {

        # count the nodes and write the count
        node := first;
        uint count;
        while (node) {
            ++count;
            node = node.next;
        }
        #cout `writing count $count\n`;
        dst.write(count);

        # write all of the nodes
        node = first;
        while (node) {
            node.writeTo(dst);
            node = node.next;
        }
    }

    void __write(Formatter fmt, Node node) {
        if (node.next)
            __write(fmt, node.next);
        node.formatTo(fmt);
    }

    void formatTo(Formatter fmt) {
        __write(fmt, first);
    }

    void writeTo(Writer out) {
        StandardFormatter fmt = {out};
        __write(fmt, first);
    }

    NodeIter iter() { return NodeIter(first); }

    ## Node lists are true if they have any contents.
    bool isTrue() { return first; }

    Node getLast() { return last; }
    Node getFirst() { return first; }

    void expand(CrackContext context, Array[NodeList] args) {
        for (node :in this)
            node.expand(context, args);
    }

    String toString(Array[NodeList] args) {
        StringFormatter sf = {};
        Array[Node] nodeArray = {};
        for (node :in this)
            nodeArray.append(node);

        bool first = true;
        for (int i = nodeArray.count() - 1; i >= 0; --i) {
            if (first)
                first = false;
            else
                sf ` `;
            sf `$(nodeArray[i].toString(args))`;
        }

        return sf.string();
    }

    Location getLocation() {
        if (loc !is null)
            return loc;
        else if (first)
            return first.getLocation();
        else
            throw AssertionError('Location undefined.');
    }
}

class Tok : Node {
    Token tok;

    oper init(Token tok) : tok = tok {}

    oper init() {}

    void expand(CrackContext ctx, Array[NodeList] args) {
        ctx.putBack(tok);
    }

    String toString(Array[NodeList] args) {
        type := tok.getType();
        if (tok.isString()) {
            return String(tok.getText()).getRepr();
        } else if (type == TOK_BREAKKW) {
            return 'break';
        } else if (type == TOK_CLASSKW) {
            return 'class';
        } else if (type == TOK_CONTINUEKW) {
            return 'continue';
        } else if (type == TOK_FORKW) {
            return 'for';
        } else if (type == TOK_ELSEKW) {
            return 'else';
        } else if (type == TOK_IFKW) {
            return 'if';
        } else if (type == TOK_IMPORTKW) {
            return 'import';
        } else if (type == TOK_INKW) {
            return 'in';
        } else if (type == TOK_ISKW) {
            return 'is';
        } else if (type == TOK_NULLKW) {
            return 'null';
        } else if (type == TOK_ONKW) {
            return 'on';
        } else if (type == TOK_OPERKW) {
            return 'oper';
        } else if (type == TOK_RETURNKW) {
            return 'return';
        } else if (type == TOK_WHILEKW) {
            return 'while';
        } else {
            return String(tok.getText());
        }
    }

    Location getLocation() {
        return tok.getLocation();
    }

    void formatTo(Formatter fmt) {
        if (tok.isString()) {
            fmt.format(' ');
            fmt.format(String(tok.getText()).getRepr());
        } else {
            fmt.format(' ');
            fmt.format(StaticString(tok.getText()));
        }
    }

    void writeTo(Writer out) {
        if (tok.isString()) {
            out.write(' ');
            out.write(String(tok.getText()).getRepr());
        } else {
            out.write(' ');
            out.write(StaticString(tok.getText()));
        }
    }


    void writeTo(MacroSerializer dst) {

        # my node type
        dst.write(0);

        # the token
        dst.write(uint(tok.getType()));
        dst.write(String(tok.getText()));

        dst.writeLocation(tok.getLocation());
    }

    oper init(MacroDeserializer src) {
        type := int(src.readUInt());
        text := src.readString();
        locName := src.readSrcName();
        locLineNum := src.readUInt();

        #cout `read token: $type, $text, $locName, $locLineNum\n`;
        tok = Token(type, text.buffer,
                    src.ctx.getLocation(locName.buffer, int(locLineNum))
                    );
    }
}

class Arg : Node {
    uint argIndex;
    Location loc;

    oper init(Location loc, uint argIndex) :
        loc = loc,
        argIndex = argIndex {
    }

    oper init() {}

    void expand(CrackContext ctx, Array[NodeList] args) {
        for (node :in NodeList.cast(args[argIndex]))
            node.expand(ctx, args);
    }

    String toString(Array[NodeList] args) {
        StringFormatter sf = {};
        argVal := NodeList.cast(args[argIndex]);

        # do the last node so we can add a whitespace separator for every
        # subsequent node.
        if (last := argVal.getLast())
            sf.format(last.toString(args));

        # do the rest of the nodes
        void reverseNodeList(Array[NodeList] args1, StringFormatter out,
                             Node node
                             ) {

            # stop recursing before the last node
            if (node.next) {
                reverseNodeList(args1, out, node.next);
                out ` $(node.toString(args1))`;
            }
        }

        reverseNodeList(args, sf, argVal.getFirst());
        return sf.cString();
    }

    void formatTo(Formatter fmt) { fmt `arg: $argIndex\n`; }
    Location getLocation() { return loc; }

    oper init(MacroDeserializer src) {
        argIndex = src.readUInt();
        loc = src.readLocation();
        #cout `read arg $argIndex\n`;
    }

    void writeTo(MacroSerializer dst) {

        # write my type id
        dst.write(1);

        # write the arg id and location fields
        dst.write(argIndex);
        dst.writeLocation(loc);
    }
}

## Concat nodes concatenate a set of tokens into a single token.  The type and
## location come from the first non-argument token.
class Concat : Node {
    NodeList list;
    int type;
    Location loc;

    oper init(NodeList list, Location loc) :
        loc = loc,
        list = list {
    }

    oper init() {}

    void expand(CrackContext ctx, Array[NodeList] args) {
        StringFormatter concat = {};
        for (item :in list)
            concat.format(item.toString(args));
        concat.format(' \0');

        s := concat.string();
        ctx.inject(@FILE.buffer, @LINE, s.buffer);
    }

    String toString(Array[NodeList] args) {
        die('Concat.toString() called.');
        return null;
    }

    Location getLocation() {
        return loc;
    }

    oper init(MacroDeserializer src) {
        list = NodeListImpl(src);
        type = int(src.readUInt());
        loc = src.readLocation();
    }

    void writeTo(MacroSerializer dst) {
        dst.write(2);

        list.writeTo(dst);
        dst.write(uint(type));
        dst.writeLocation(loc);
    }
}

## A Node that converts its arguments to a string.
class Stringify : Node {
    Node node;

    oper init(Node node) : node = node {}

    void expand(CrackContext ctx, Array[NodeList] args) {
        ctx.putBack(Token(TOK_STRING, node.toString(args).buffer,
                          node.getLocation()
                          )
                    );
    }

    String toString(Array[NodeList] args) {
        die('Stringify.toString called.');
        return null;
    }

    Location getLocation() {
        return node.getLocation();
    }

    oper init(MacroDeserializer src) {
        node = _readNode(src);
    }

    void writeTo(MacroSerializer dst) {

        # write my type id.
        dst.write(3);

        node.writeTo(dst);
    }
}

Node _readNode(MacroDeserializer src) {
    type := src.readUInt();
    Node node;
    if (type == 0)
        node = Tok(src);
    else if (type == 1)
        node = Arg(src);
    else if (type == 2)
        node = Concat(src);
    else if (type == 3)
        node = Stringify(src);
    else
        throw AssertionError(FStr() `bogus node $type\n`);

    return node;
}

## Parse the rest of the i-string (after the ISTR_BEGIN token) into 'result'
## (backwards, of course).
void parseIString(CrackContext ctx, NodeList result) {
    int parenCount = 0;
    while (true) {
        tok := ctx.getToken();
        result.pushHead(Tok(tok));
        if (tok.isLParen()) {
            parenCount++;
        } else if (!parenCount && tok.isIdent()) {
            ctx.continueIString();
        } else if (tok.isRParen()) {
            if (!--parenCount)
                ctx.continueIString();
        } else if (tok.isIstrEnd()) {
            break;
        }
    }
}

## Parse macro arguments, returns them as an array of NodeList objects.
Array[NodeList] parseArgs(CrackContext ctx, uint argCount) {
    # extract the arguments from the following tokens
    tok := ctx.getToken();
    if (!tok.isLParen())
        ctx.error(tok, 'left paren expected in macro expansion'.buffer);

    const byte PAREN = 1, BRACK = 2, CURL = 3;

    uint nesting = 1;
    argTokList := NodeListImpl();
    Array[NodeList] args = {argCount};
    Array[byte] brackStack = {4};

    # pop everything on the bracket stack up to the matching value.  This
    # behavior lets us both respect existing balanced delimiters and ignore
    # unbalanced ones.
    void popTo(Array[byte] brackStack, byte val) {
        for (int i = brackStack.count() - 1; i >= 0; --i) {
            if (brackStack[i] == val) {
                while (brackStack.count() > i) {
                    brackStack.delete(brackStack.count() - 1);
                }
                break;
            }
        }
    }

    while (true) {
        tok = ctx.getToken();
        if (!brackStack && tok.isComma()) {
            args.append(argTokList);
            argTokList = NodeListImpl();
        } else {
            if (tok.isLParen()) {
                brackStack.append(PAREN);
            } else if (tok.isLBracket()) {
                brackStack.append(BRACK);
            } else if (tok.isLCurly()) {
                brackStack.append(CURL);
            } else if (tok.isRParen()) {
                if (!brackStack)
                    break;
                else
                    popTo(brackStack, PAREN);
            } else if (tok.isRBracket() && brackStack) {
                popTo(brackStack, BRACK);
            } else if (tok.isRCurly() && brackStack) {
                popTo(brackStack, CURL);
            } else if (tok.isIstrBegin()) {
                argTokList.pushHead(Tok(tok));
                parseIString(ctx, argTokList);
                continue;
            }

            argTokList.pushHead(Tok(tok));
        }
    }

    # if we got a non-empty element left over, add it to the list.
    if (argTokList.getFirst())
        args.append(argTokList);

    # verify that the number of arguments provided was correct
    if (args.count() != argCount) {
        fmt := StringFormatter();
        fmt `Incorrect number of arguments for macro: expected \
$(argCount), got $(args.count())\0`;
        ctx.error(tok, fmt.string().buffer);
    }

    return args;
}

class Macro : NodeListImpl {
    String name;
    uint argCount;

    oper init() {}
    oper init(MacroDeserializer src) : NodeListImpl(src) {
        name = src.readString();
        argCount = src.readUInt();
    }

    void writeTo(MacroSerializer dst) {
        NodeListImpl.writeTo(dst);
        dst.write(name);
        dst.write(argCount);
    }

    void expand(CrackContext ctx) {
        # hold onto the last location
        loc := ctx.getLocation();

        # parse the args.
        args := parseArgs(ctx, argCount);

        # install the "pop error context" token so that our error context only
        # shows up for the expansion of the macro.
        ctx.putBack(Token(TOK_POPERRCTX, '[pop error context]'.buffer,
                          loc
                          )
                    );

        # expand the macro
        Node node = first;
        while (node) {
            node.expand(ctx, args);
            node = node.next;
        }

        # push an error context
        StringFormatter fmt = {};
        fmt `expanded from macro at $(loc.getName()):$(loc.getLineNumber())`;
        ctx.pushErrorContext(fmt.cString().buffer);
    }
}

## Annotation to expand a macro.  This expects a Macro instance as user data.
void expand(CrackContext ctx) {
    mac := Macro.unsafeCast(ctx.getUserData());
    mac.expand(ctx);
}

# macro parser states
ST_NONE := 0;
ST_ESC := 1;   # got a dollar-sign escape
ST_CONCAT := 2;  # got a double-dollar-sign concatenation operator
ST_ISTR := 3; # MUST BE THE HIGHEST VALUE STATE.  Values greater than this
              # indicate levels of nested parens in an i-string.

void define(CrackContext ctx) {
    Macro mac = {};
    TreeMap[String, uint] args = {};
    uint index;
    tok := ctx.getToken();

    if (!tok.isIdent())
        ctx.error(tok, 'Macro name expected after define.'.buffer);
    mac.name = String(tok.getText());

    # parse the '(' that begins the argument list
    tok = ctx.getToken();
    if (!tok.isLParen())
        ctx.error(tok, 'Left paren expected after macro definition'.buffer);

    # read all of the arguments
    while (true) {
        tok = ctx.getToken();
        if (tok.isRParen())
            break;

        if (!tok.isIdent())
            ctx.error(tok, 'identifier expected'.buffer);

        args[String(tok.getText())] = index++;

        tok = ctx.getToken();
        if (tok.isRParen())
            break;
        else if (!tok.isComma())
            ctx.error('comma or end paren expected in macro def'.buffer);
    }
    mac.argCount = index;

    # read the body of the macro
    tok = ctx.getToken();
    if (!tok.isLCurly())
        ctx.error('Expected left bracket'.buffer);

    # read everything until the end bracket
    uint bracketCount = 1;
    int state = ST_NONE;
    NodeListImpl lastConcat = {};  # last concatenation sequence.
    Node node;  # the last node
    while (true) {
        tok = ctx.getToken();
        uint argIndex;

        if (tok.isEnd()) {
            ctx.error(
                'End of file before the end of a macro definition'.buffer
            );
        } else if (state >= ST_ISTR) {
            # keep track of the parens.
            if (tok.isLParen())
                ++state;
            else if (tok.isRParen() && --state == ST_ISTR)
                # we have to tell the tokenizer to continue parsing the
                # i-string.
                ctx.continueIString();
            else if (tok.isIstrBegin())
                ctx.error('Nested interpolation strings may not be used '
                           'in macros.'.buffer
                          );
            else if (tok.isDollar())
                ctx.error('Nested concatenations and stringifications may not '
                           'be used in a macro.'.buffer
                          );
            else if (tok.isIstrEnd())
                state = ST_NONE;
            else if (state == ST_ISTR && tok.isIdent())
                # an identifier takes us immediately back into the i-string
                ctx.continueIString();
        } else if (tok.isIstrBegin()) {
            if (state != ST_NONE)
                ctx.error('An interpolation string may not be used with '
                           'stringification or concatenation.'.buffer
                          );
            state = ST_ISTR;
        # check for brackets, increment or decrement the bracket count.
        } else if (tok.isRCurly()) {
            if (!--bracketCount)
                break;
        } else if (tok.isLCurly()) {
            ++bracketCount;
        } else if (tok.isDollar()) {
            if (state == ST_NONE) {
                state = ST_ESC;
            } else if (state == ST_ESC) {
                if (!node)
                    ctx.error('The macro may not begin with a concatenation '
                               'operator'.buffer
                              );
                else if (node.isa(Tok) &&
                         Tok.cast(node).tok.isIstrEnd()
                         )
                    ctx.error('An interpolation string may not be used with '
                               'stringification or concatenation'.buffer
                              );

                # if we're starting off a new concatenation sequence, add the
                # last node and store the sequence as a new node in the macro.
                if (!lastConcat) {
                    lastConcat.append(node);
                    mac.popHead();
                    mac.pushHead(Concat(lastConcat, tok.getLocation()));
                }

                state = ST_CONCAT;
            } else {
                ctx.error('One two many dollar signs\n'.buffer);
            }
            continue;
        }

        # replace arguments with indices
        if (tok.isIdent() &&
            (argIndex = args.get(String(tok.getText()), NOT_FOUND)) !=
             NOT_FOUND
            )
            node = Arg(tok.getLocation(), argIndex);
        else
            node = Tok(tok);

        # handle special states
        if (state == ST_CONCAT) {

            # concatenation state - add the new node to the concatenation
            # sequence.
            lastConcat.append(node);
            state = ST_NONE;
        } else if (state == ST_ESC) {

            # stringify state - add a stringify node.
            mac.pushHead(Stringify(node));
            state = ST_NONE;
        } else {
            mac.pushHead(node);

            # reset any last concatenation sequence that we've accumulated
            if (lastConcat)
                lastConcat = NodeListImpl();
        }
    }

    # store a new annotation for expanding the macro
    ctx.storeAnnotation(mac.name.buffer, expand, mac);
    mac.oper bind();
}

void export(CrackContext ctx) {

    # get the next token, make sure it's an annotation.
    tok := ctx.getToken();
    if (!tok.isIdent())
        ctx.error(tok, 'Identifier expected'.buffer);
    name := CString(tok.getText(), false);
    ann := ctx.getAnnotation(name.buffer);
    Macro mac;
    if (ann is null) {
        StringFormatter fmt = {};
        fmt `$name is not an annotation.\0`;
        ctx.error(tok, fmt.string().buffer);
    } else {
        mac = Macro.unsafeCast(ann.getUserData());
    }

    # serialize the macro into a string
    flatMac := StringWriter();
    mac.writeTo(MacroSerializer(flatMac));

    StringFormatter code = {};
    f := @FILE; l := @LINE; code `

        void $name(CrackContext ctx) {
            userData :=
                ctx.getUserData();
            Macro mac;
            if (userData is null) {
                StringReader reader = { $(flatMac.string().getRepr()) };
                mac = Macro(MacroDeserializer(ctx, reader));
                ctx.storeAnnotation($(name.getRepr()).buffer, $name,
                                    mac
                                    );
                mac.oper bind();
            } else {
                mac = Macro.unsafeCast(userData);
            }

            mac.expand(ctx);
        }
    \n\0`;
    ctx.inject(f.buffer, l, code.string().buffer);
}

## Call this annotation at the top of your file if you want to export macros.
## It will import everything you need.
void exporter(CrackContext ctx) {
    StringFormatter f = {};
    f `import crack.ann Macro, MacroDeserializer, Node, NodeList, Tok, Arg,
        Stringify, Concat;
       import crack.compiler CrackContext, Token, TOK_STRING;
       import crack.io StringReader;`;
    ctx.inject(@FILE.buffer, @LINE,
               f.cString().buffer);
}

void readIStr(CrackContext ctx, NodeList nodes) {
    depth := 0;

    while (true) {
        tok := ctx.getToken();
        nodes.pushHead(Tok(tok));
        if (tok.isLParen())
            ++depth;
        else if (tok.isRParen() && !--depth)
            ctx.continueIString();
        else if (tok.isIdent() && !depth)
            ctx.continueIString();
        else if (tok.isIstrEnd())
            return;
    }
}

## Just like the other readDelimited() except that it passes in the 'result'
## list instead of returning it, allowing you to compose on an existing list.
void readDelimited(CrackContext ctx, int left, int right,
                   bool storeDelimiters,
                   NodeList result
                   ) {
    # get the opening delimiter.
    Token tok;
    Location start;
    if (storeDelimiters) {
        tok = ctx.getToken();
        start = tok.getLocation();
        if (tok.getType() != left)
            ctx.error(tok, 'Opening delimiter expected.'.buffer);
        result.pushHead(Tok(tok));
    }

    depth := 1;
    while (depth) {
        tok = ctx.getToken();
        if (start is null)
            start = tok.getLocation();
        if (tok.isEnd())
            ctx.error(
                tok,
                FStr() `Premature end of file (in block starting at $(
                        start.getName()):$(start.getLineNumber()))`.buffer
            );
        if (tok.getType() == left)
            ++depth;
        else if (tok.getType() == right)
            --depth;

        if (depth || storeDelimiters)
            result.pushHead(Tok(tok));
        else if (!depth)
            # If we're not storing the delimiters, put the last token back.
            ctx.putBack(tok);

        if (tok.isIstrBegin())
            readIStr(ctx, result);
    }
}

## Reads a sequence of tokens between a specified left and right delimiter
## which can be nested.  For example, if left and right are TOK_LPAREN and
## TOK_RPAREN this function would read the following sequence:
##    ( 1 + 2 + (3 + 4) )
##   ^                   ^
##
## if storeDelimiters is true, parses and processes the beginning and ending
## delimiter and adds them to the returned node list, otherwise the next
## available token should be the one immediately following the opening
## delimiter and the last token will be put back.
NodeList readDelimited(CrackContext ctx, int left, int right,
                       bool storeDelimiters
                       ) {
    NodeListImpl result = {};
    readDelimited(ctx, left, right, storeDelimiters, result);
    return result;
}

## Read a curly-bracket delimited block.  See readDelimited() for details
NodeList readBlock(CrackContext ctx) {
    return readDelimited(ctx, TOK_LCURLY, TOK_RCURLY, true);
}

void _parseGenericArgs(CrackContext ctx, NodeList tokens) {
    while (true) {
        tok := ctx.getToken();
        if (!tok.isIdent())
            ctx.error(tok, 'Identifier expected in generic definition'.buffer);
        tokens.append(Tok(tok));

        tok = ctx.getToken();
        tokens.append(Tok(tok));
        if (tok.isRBracket())
            return;
        else if (!tok.isComma())
            ctx.error(tok,
                      'Comma or closing bracket expected in generic definition'.
                       buffer
                      );
    }
}

## Writes a NodeList to an output stream separated by whitespace.
class TokenWriter {
    NodeList tokens;
    oper init(NodeList tokens) : tokens = tokens {}
    void formatTo(Formatter fmt) {
        for (tok :in tokens) {
            fmt.format(tok.toString(null));
            fmt.format(' ');
        }
    }

    void writeTo(Writer out) {
        for (tok :in tokens) {
            out.write(tok.toString(null));
            out.write(' ');
        }
    }
}

void warn(CrackContext ctx) {
    tok := ctx.getToken();
    if (!tok.isString())
        ctx.error(tok, "String expected after @warn annotation".buffer);
    ctx.warn(tok, tok.getText());
}

## A node whose expand() method injects raw text into the token stream.
## This avoids the need to painstakingly reconstruct the code token by toke.
class _InjectionNode : Node {
    Location __loc;
    String __code;

    oper init(Location loc, String code) : __loc = loc, __code = code {}

    void expand(CrackContext ctx, Array[NodeList] args) {
        ctx.inject(__loc.getName(), __loc.getLineNumber(), __code.buffer);
    }

    String toString(Array[NodeList] args) { return __code; }
    Location getLocation() {
        return __loc;
    }

    void writeTo(MacroSerializer dst) {
        throw Exception('Unsupported operation');
    }
}

## Represents an arbitrary type.
##
## Note: this doesn't yet deal with "typeof()" expressions.
class Type {
    String name;
    Array[Type] params;

    oper init(String name, Array[Type] params) :
        name = name,
        params = params {
    }

    void formatTo(Formatter out) {
        out `$name`;
        if (params) {
            out `$params`;
        }
    }

    ## Parse a type out of the following tokens.
    ##
    ## result: nullable.  If present, this is a node list into which to inject
    ##     the type tokens.
    @static Type parse(CrackContext ctx, NodeList result) {
        tok := ctx.getToken();
        if (!tok.isIdent())
            ctx.error(tok, 'Identifier expected for type name'.buffer);
        String name = {tok.getText()};
        if (result !is null)
            result.pushHead(Tok(tok));

        Array[Type] params;
        tok = ctx.getToken();
        if (tok.isLBracket()) {

            # got a left bracket, parse the type parameters
            params = Array[Type]();
            if (result !is null)
                result.pushHead(Tok(tok));
            while (true) {
                params.append(Type.parse(ctx, result));
                tok = ctx.getToken();
                if (result !is null)
                    result.pushHead(Tok(tok));
                if (tok.isRBracket()) {
                    break;
                } else if (!tok.isComma()) {
                    text := 'Comma or right bracket expected in type definition';
                    ctx.error(tok, text.buffer)
                }
            }

        } else {
            ctx.putBack(tok);
        }

        return Type(name, params);
    }
}

class Field {
    Type type;
    String name;
    oper init(Type type, String name) : type = type, name = name {}

    @static void parse(CrackContext ctx, Array[Field] fields, NodeList result) {
        type := Type.parse(ctx, result);

        # parse each of the variables
        while (true) {
            tok := ctx.getToken();
            if (!tok.isIdent()) {
                msg := 'Identifier expected after type in field definition.';
                ctx.error(tok, msg.buffer);
            }
            result.pushHead(Tok(tok));

            name := String(tok.getText());
            f := Field(type, name);
            fields.append(f);

            # check for a comma or semicolon
            tok = ctx.getToken();
            result.pushHead(Tok(tok));
            if (tok.isSemi())
                return;
            else if (!tok.isComma())
                ctx.error(tok,
                          I'Comma or semicolon expected after field \
                            definition'.buffer);
        }
    }
}

Array[Field] _parseStructFields(NodeList nodes, CrackContext ctx) {
    Array[Field] fields = {};

    # parse fields
    while (true) {

        tok := ctx.getToken();

        # Stuff doc-comments into the node list.
        while (tok.isDoc()) {
            nodes.pushHead(Tok(tok));
            tok = ctx.getToken();
        }

        if (tok.isRCurly()) {
            ctx.putBack(tok);
            break;
        }

        # put it back and parse a field
        ctx.putBack(tok);
        Field.parse(ctx, fields, nodes);
    }

    return fields;
}

void _emitStructContents(CrackContext ctx, NodeListImpl nodes,
                         Array[Field] fields
                         ) {
    # create the constructor.

    nodes.pushHead(_InjectionNode(ctx.getLocation(@FILE.buffer,
                                                  @LINE),
                                  'oper init('
                                  )
                   );

    # arg list
    first := true;
    pfx := '';
    for (field :in fields) {
        nodes.pushHead(_InjectionNode(ctx.getLocation(@FILE.buffer,
                                                      @LINE),
                                      FStr() I`$pfx$(field.type) \
                                               $(field.name) \0`
                                      )
                       );
        if (first) {
            pfx = ', ';
            first = false;
        }
    }

    nodes.pushHead(_InjectionNode(ctx.getLocation(@FILE.buffer,
                                                  @LINE),
                                  ') : '
                                  )
                   );

    # initializers
    first = true;
    pfx = '';
    for (field :in fields) {

        nodes.pushHead(_InjectionNode(ctx.getLocation(@FILE.buffer,
                                                      @LINE),
                                      FStr() I`$pfx$(field.name) =
                                               $(field.name) \0`
                                      )
                       );

        if (first) {
            pfx = ', ';
            first = false;
        }
    }

    nodes.pushHead(_InjectionNode(ctx.getLocation(@FILE.buffer, @LINE), '{}'));
}

void struct(CrackContext ctx) {
    tok := ctx.getToken();
    if (!tok.isIdent())
        ctx.error(tok, 'Identifier expexted after @struct annotation'.buffer);


    className := String(tok.getText());

    # start the result token list with "class <tok>"
    NodeListImpl result = {};
    result.pushHead(_InjectionNode(ctx.getLocation(@FILE.buffer, @LINE),
                                   'class \0'
                                   )
                    );
    result.pushHead(Tok(tok));

    # parse a curly
    tok = ctx.getToken();
    if (!tok.isLCurly())
        ctx.error(tok, 'Curly brace expected after struct name.'.buffer);
    result.pushHead(Tok(tok));

    fields := _parseStructFields(result, ctx);
    _emitStructContents(ctx, result, fields);

    # push the closing bracket for the class
    result.pushHead(Tok(ctx.getToken()));

    # finally, expand the result
    for (node :in result)
        node.expand(ctx, null);
}

## Constructed variables.  Expands a block containing field definitions to a
## list of variable definitions and a constructor that initiallizes them.
void cvars(CrackContext ctx) {
    tok := ctx.getToken();
    if (!tok.isLCurly())
        ctx.error(tok, 'Curly brace expected.'.buffer);

    NodeListImpl result = {};
    fields := _parseStructFields(result, ctx);
    ctx.getToken();
    _emitStructContents(ctx, result, fields);

    for (node :in result)
        node.expand(ctx, null);
}

void assert(CrackContext ctx) {
    expr := readDelimited(ctx, TOK_LPAREN, TOK_RPAREN, true);
    loc := expr.getFirst().getLocation();
    message := expr.toString(null);
    ctx.inject(@FILE.buffer, @LINE,
               FStr() I`)) {
                    import crack.lang AssertionError;
                    import crack.io FStr;
                    throw AssertionError(
                        FStr() \`$(loc.getName()):$(loc.getLineNumber()): \
                            Assertion failed: \
                            \$($(message.getRepr()))\\n\`
                    );
               } \0`.buffer
               );
    expr.expand(ctx, null);
    ctx.inject(@FILE.buffer, @LINE, 'if (!('.buffer)
}

# capitalizes the first letter of 'str'
String _capitalize(String str) {
    if (str[0] >= b'a' && str[0] <= b'z') {
        String copy = String(str);  # create a copy
        copy.buffer[0] = b'A' + str[0] - b'a';
        return copy;
    }

    return str;
}

# quickly create property accessors, inspired by Ruby's attr_accessor and
# C#'s properties.
void property(CrackContext ctx) {
    readonlyAttr := ctx.getToken();
    ctx.putBack(readonlyAttr);

    if (readonlyAttr.isLParen()) {
        readonlyAttr = null;

        NodeList attrList = readDelimited(ctx, TOK_LPAREN, TOK_RPAREN, true);

        for (node :in attrList) {
            tok := Tok.cast(node);
            if (tok.tok.isLParen() || tok.tok.isRParen() || tok.tok.isComma()) {
                continue;
            }

            tokText := StaticString(tok.tok.getText());
            if (tokText == 'ro' || tokText == 'readonly') {
                readonlyAttr = tok.tok;
            } else {
                ctx.error(tok.tok, FStr() `Unknown property attribute$(tok)`.buffer);
            }
        }
    } else {
        readonlyAttr = null;
    }

    NodeListImpl typeNodes = {};
    type := Type.parse(ctx, typeNodes);

    nameToken := ctx.getToken();
    if (!nameToken.isIdent()) {
        ctx.error(nameToken, 'Identifier expected after property type'.buffer);
    }

    tok := ctx.getToken();

    NodeList getter = null;
    NodeList setter = null;

    # user defined accessors
    if (tok.isLCurly()) {
        tok = ctx.getToken();

        while (!tok.isRCurly()) {
            if (StaticString(tok.getText()) == "get") {
                getter = readBlock(ctx);
            } else if (StaticString(tok.getText()) == "set") {
                if (readonlyAttr !is null) {
                    ctx.error(tok, "readonly properties cannot have setters defined".buffer);
                }
                setter = readBlock(ctx);
            } else if (!tok.isSemi()) {
                ctx.error(tok, FStr() `Unknown identifier$(Tok(tok))`.buffer);
            }
            tok = ctx.getToken();
        }
    } else if (!tok.isSemi()) {
        ctx.error(tok, 'semicolon or opening curly brace expected after property definition'.buffer);
    }

    # setter
    if (readonlyAttr is null) {
        if (setter is null) {
            # default setter
            ctx.inject(@FILE.buffer, @LINE, FStr() `{ _$(nameToken.getText()) = value; } \0`.buffer);
        } else {
            setter.expand(ctx, null);
        }

        ctx.inject(@FILE.buffer, @LINE, ' value) \0'.buffer);

        typeNodes.expand(ctx, null);

        ctx.inject(@FILE.buffer, @LINE, FStr() `void set$(_capitalize(StaticString(nameToken.getText()))) ( \0`.buffer);
    }

    # getter
    if (getter is null) {
        # default getter
        ctx.inject(@FILE.buffer, @LINE, FStr() `{ return _$(nameToken.getText()); } \0`.buffer);
    } else {
        getter.expand(ctx, null);
    }
    ctx.inject(@FILE.buffer, @LINE, FStr() `$(nameToken.getText())() \0`.buffer);
    typeNodes.expand(ctx, null);

    # field
    ctx.inject(@FILE.buffer, @LINE, FStr() `_$(nameToken.getText()); \0`.buffer);
    typeNodes.expand(ctx, null);
}

## An annotation that defines an interface.
void interface(CrackContext ctx) {
    nameTok := ctx.getToken();
    if (!nameTok.isIdent())
        ctx.error(nameTok, 'identifier expected for interface name'.buffer);

    # check for generic arguments
    tok := ctx.getToken();
    NodeListImpl genericArgs = {};
    if (tok.isLBracket()) {
        genericArgs.append(Tok(tok));
        _parseGenericArgs(ctx, genericArgs);
    } else {
        ctx.putBack(tok);
    }

    # for injecting the bind(), release() and get*Object() methods
    StringFormatter f = {};

    # True if we have explicit base classes.
    bool hasBaseClasses;

    # We'll use this to store the location of the initial curly bracket.
    Location loc;

    # check for base interfaces
    NodeListImpl interfaces = {};
    tok = ctx.getToken();
    if (tok.isColon()) {
        # copied from the @implements annotation below:
        Array[Type] ifaces = {4};
        Token firstTok;
        while (true) {

            tok := ctx.getToken();

            if (firstTok is null)
                firstTok = tok;

            if (tok.isLCurly()) {
                loc = tok.getLocation();
                break;

            # store types in an array so we can generate the "oper from *()"
            # methods.
            } else if (tok.isIdent()) {
                ctx.putBack(tok);
                ifaces.append(Type.parse(ctx, interfaces));
                continue;
            }
            interfaces.pushHead(Tok(tok));
        }

        f `{ @abstract Object oper from $(nameTok.getText())();\n`;
        for (iface :in ifaces)
            f I`    Object oper from $(iface) () {
                        return this.oper from $(nameTok.getText())();
                    }\n`;

        hasBaseClasses = true;

    } else {
        # Store the location of the left curly.
        loc = tok.getLocation();

        # The set of functions that an interface must provide to work with
        # objects.  This is also defined as a macro in crack.lang to allow us
        # to define some of the low-level types as interfaces before we can
        # parse this module.  These definitions must be kept in sync with that
        # file.
        f `{
        @abstract Object oper from $(nameTok.getText())();
        @final oper bind() {
            if (this !is null)
                this.oper from $(nameTok.getText())().oper bind();
        }
        @final oper release() {
            if (this !is null)
                this.oper from $(nameTok.getText())().oper release();
        }
        @final oper to Object() {
            if (this !is null)
                return this.oper from $(nameTok.getText())();
            else
                return null;
        }
        @final oper to bool() {
            return this !is null &&
                this.oper from $(nameTok.getText())().isTrue();
        }
        `;
    }

    # read the body, excluding the delimiters.
    body := readDelimited(ctx, TOK_LCURLY, TOK_RCURLY, false);

    # Expand the rewritten class (backwards, as always).

    # We don't need to inject the closing bracket, readDelimited() has left
    # that on the token queue.  We can just expand the body.
    body.expand(ctx, null);

    # Emit the special functions up front.
    ctx.inject(loc.getName(), loc.getLineNumber(), f.cString().buffer);

    # expand the base interface list
    interfaces.expand(ctx, null);

    # inject the class definition
    loc = nameTok.getLocation();
    f = StringFormatter();
    f `@abstract class $(nameTok.getText())$(TokenWriter(genericArgs)) :
        $(interfaces ? String() : "VTableBase")\0`;
    ctx.inject(loc.getName(), loc.getLineNumber(), f.cString().buffer);
}

void _implements(CrackContext ctx, bool emitObject) {
    # parse the list of interfaces
    NodeListImpl interfaces = {};
    Array[Type] ifaces = {4};

    Token firstTok;
    while (true) {
        tok := ctx.getToken();

        if (firstTok is null)
            firstTok = tok;

        if (tok.isLCurly()) {
            ctx.putBack(tok);
            break;

        # store identifiers in an array so we can generate the oper from *()
        # methods.
        } else if (tok.isIdent()) {
            ctx.putBack(tok);
            ifaces.append(Type.parse(ctx, interfaces));
            continue;
        }
        interfaces.pushHead(Tok(tok));
    }

    # add a comma to the end of the list (so it will show up at the beginning
    # of the list when we expand it)
    interfaces.append(
        Tok(Token(TOK_COMMA, ",".buffer, firstTok.getLocation()))
    );

    # Parse an opening brace.
    openingBrace := ctx.getToken();
    if (!openingBrace.isLCurly())
        ctx.error(openingBrace, 'opening curly bracket expected.'.buffer);
    loc := openingBrace.getLocation();

    # inject the get*Object() implementations.
    StringFormatter f = {};
    for (iface :in ifaces)
        f `    Object oper from $iface() { return this; }\n`;
    f `\0`;
    ctx.inject(loc.getName(), loc.getLineNumber(), f.string().buffer);
    ctx.putBack(openingBrace);

    # inject the interfaces
    for (node :in interfaces)
        node.expand(ctx, null);

    # emit ": Object" for @impl
    if (emitObject) {
        loc = firstTok.getLocation();
        ctx.inject(loc.getName(), loc.getLineNumber(), ': Object'.buffer);
    }
}

## An annotation to be used before the list of interfaces that a class
## implements, e.g.
void implements(CrackContext ctx) {
    _implements(ctx, false);
}

## Shorthand so we can say "class A @impl IFace" instead of
## "class A : Object @implements IFace"
void impl(CrackContext ctx) {
    _implements(ctx, true);
}

## Read a sequence of tokens delimited by the next token and it's closing
## counterpart.  Consumes the closing delimiter and doesn't return the
## delimiters. Delimiters can be curly brackets, square brackets or
## parenthesis.
NodeList readAnyDelimited(CrackContext ctx) {
    delim := ctx.getToken();
    ttype := delim.getType();
    NodeListImpl result = {delim.getLocation()};
    if (ttype == TOK_LPAREN)
        readDelimited(ctx, TOK_LPAREN, TOK_RPAREN, false, result);
    else if (ttype == TOK_LBRACKET)
        readDelimited(ctx, TOK_LBRACKET, TOK_RBRACKET, false, result);
    else if (ttype == TOK_LCURLY)
        readDelimited(ctx, TOK_LCURLY, TOK_RCURLY, false, result);

    # Read the closing delimiter.
    ctx.getToken();

    return result;
}

## Returns the node list serialized to a string token.
Token serializeNodeList(NodeList list) {
    ser := TokSerializer();
    ser.setLocation(list.getLocation());
    for (node :in list) {
        tok := Tok.cast(node).tok;
        ser.insert(tok);
    }

    serialized := ser.serialize();
    size := array[uint32](serialized)[0];
    tok := Token(TOK_STRING, serialized + 4, size, list.getLocation());
    free(serialized);
    return tok;
}

## Converts a delimited stream of tokens to a string that can be converted
## back to a NodeList at runtime with deserializeNodeList().
##
## Example:
##
##   code := deserializeNodeList(@token_str {
##       if ($1 == $2)
##           cout `values are equal!\n`;
##   });
##   code.expand(ctx, params);
##
## The delimiters ('{' and '}' in the example) are not included in the list.
## Curly brackets, square brackets and parenthesis may be used as delimiters.
## The only restriction is that if a delimiter is nested, it must be balanced
## within the list.  For example, @tokens ( class Foo { ) is legal, @tokens {
## class foo { } is not.
void token_str(CrackContext ctx) {
    list := readAnyDelimited(ctx);
    first := list.getFirst();
    ctx.putBack(serializeNodeList(list));
}

## Given a serialized list of tokens created from the tokens() annotation,
## return the deserialized NodeList.
NodeList deserializeNodeList(String tokens) {
    ser := TokSerializer(tokens.buffer, tokens.size);
    list := NodeListImpl(ser.getLocation());
    while ((tok := ser.getToken()) !is null)
        list.pushHead(Tok(tok));
    return list;
}

## @tokens is shorthand for "deserializeNodeList(@token_str { ... })"
## For example, we could do:
##
##   import crack.ann deserializeNodeList;
##
##   void hello(CrackContext ctx) {
##       (@tokens { cerr `hello world!\n` }).expand(ctx, null);
##   }
void tokens(CrackContext ctx) {
    tokStr := serializeNodeList(readAnyDelimited(ctx));
    ctx.inject(@FILE.buffer, @LINE, ')'.buffer);
    ctx.putBack(tokStr);
    ctx.inject(@FILE.buffer, @LINE, 'deserializeNodeList('.buffer);
}

## An argument definition, for use with x-macs.
class _ArgDef {
    ## The argument variable name.
    String name;

    ## The index of the argument in the macro's arg list.
    int index;

    ## The node list to be expanded into the argument of the macro's arg list.
    NodeList nodes;

    oper init(String name, int index, NodeList nodes) :
        name = name,
        index = index,
        nodes = nodes {
    }

    @final void expand(CrackContext ctx, Array[NodeList] args) {
        nodes.expand(ctx, args);
    }
}

class _ParseError : Exception {
    Token tok;
    oper init(Token tok, String text) : Exception(text), tok = tok {}
}

@final class XMacro {
    NodeList __nodes;
    TreeMap[String, _ArgDef] __defs;
    Array[NodeList] __args;

    oper init(NodeList nodes, TreeMap[String, _ArgDef] defs) :
        __nodes = nodes,
        __defs = defs,
        __args = Array[NodeList](defs.count(), null) {
    }

    ## Set the macro variable to the value.  Throws KeyError if varName is not
    ## defined.
    ## Returns 'this' to allow method chaining.
    XMacro set(String varName, NodeList value) {
        __args[__defs[varName].index] = value;
        return this;
    }

    ## Set the macro variable to the value, converting the token to a node
    ## list.  Throws KeyError if varName is not defined.
    ## Returns 'this' to allow method chaining.
    XMacro set(String varName, Token tok) {
        return set(varName, NodeListImpl![Tok(tok)]);
    }

    void __checkArgsDefined() {
        # Make sure all arguments are defined.
        for (def :in __defs) {
            if (__args[def.val.index] is null)
                throw InvalidStateError(
                    FStr() I`XMacro argument $(def.val.name) has not been \
                             defined`
                );
        }
    }

    ## A No-args version of expand, uses the argument array that we've already
    ## defined.
    void expand(CrackContext ctx) {
        __checkArgsDefined();
        __nodes.expand(ctx, __args);
    }

    NodeList expand() {
        NodeListImpl result = {};
        __checkArgsDefined();
        for (node :in __nodes) {
            if (arg := Arg.cast(node, null)) {
                # An arg value must be comprised entirely of Tok nodes, add
                # then to the result.
                for (child :in __args[arg.argIndex])
                    result.append(Tok(Tok.cast(child).tok));
            } else {
                result.append(Tok(Tok.cast(node).tok));
            }
        }

        return result;
    }

}

XMacro deserializeXMac(String tokens) {
    ser := TokSerializer(tokens.buffer, tokens.size);
    list := NodeListImpl(ser.getLocation());
    TreeMap[String, _ArgDef] vars = {};
    bool gotDollar;
    int lastArgIndex;
    while ((tok := ser.getToken()) !is null) {
        if (gotDollar) {
            if (tok.isIdent()) {

                # Get the argument def for the variable or create a new one.
                id := String(tok.getText());
                argDef := vars.get(id);
                if (!argDef) {
                    vars[id] = argDef = _ArgDef(id,
                                                lastArgIndex++,
                                                NodeListImpl![Tok(tok)]
                                                );
                }

                list.pushHead(Arg(tok.getLocation(), argDef.index));
            } else {
                throw _ParseError(tok, "Identifier expected after '$'");
            }
            gotDollar = false;
        } else if (tok.isDollar()) {
            gotDollar = true;
        } else {
            list.pushHead(Tok(tok));
        }
    }

    return XMacro(list, vars);
}

## Get the variable names given a _reversed_ list of tokens.
TreeMap[String, uint] _getVarNames(NodeList nodes) {
    bool gotDollar;
    TreeMap[String, uint] result = {};

    # Since the list is backwards, when we get a dollar sign, we need to check
    # and record the last token.
    Token lastTok;
    for (node :in nodes) {
        tok := (t := Tok.cast(node, null)) ? t.tok : null;
        if (tok !is null && tok.isDollar()) {
            if (lastTok !is null && lastTok.isIdent())
                result[String(lastTok.getText())] = 1;
            else
                throw _ParseError(lastTok, "Identifier expected after '$'");
        }
        lastTok = tok;
    }
    return result;
}

## "xmacs" are a cross between @tokens sequences and macros.  They're mainly
## useful for doing code generation from annotations.  Like @tokens, @xmac
## creates a string literal encoding of the delimited list of tokens that
## follow it.  However, it unpacks them using deserializeXMac(), which
## understands simple variable expansions of the form "$identifier".
##
## You can set these variables to NodeList values using the set() method:
##
##     m := @xmac { cerr.format($val) };
##     m.set('val', makeNodeList(tok));  # Where 'tok' is a crack.compiler.Token
##
## You can also use the @xmac* variation of the macro to interpolate local
## variables of the same name:
##
##     val := nodeList(tok);
##     m := @xmac* { cerr.format($val) };
##
## The xmac can then be expanded into a context as follows:
##
##     m.expand(ctx);
##
## Required imports:
##     import crack.ann deserializeXMac;
void xmac(CrackContext ctx) {
    # See if the next token is '*', indicating that we should interpolate
    # variables.
    bool interpolate;
    tok := ctx.getToken();
    if (tok.isAsterisk())
        interpolate = true;
    else
        ctx.putBack(tok);

    nodeList := readAnyDelimited(ctx);
    TreeMap[String, uint] varNames =
        interpolate ? _getVarNames(nodeList) : null;

    tokStr := serializeNodeList(nodeList);
    try {
        TreeMap[String, _ArgDef] args = {};

        if (interpolate) {
            for (var :in varNames)
                ctx.inject(@FILE.buffer, @LINE,
                           FStr() `.set('$(var.key)', $(var.key))\0`.buffer
                           );
        }

        # We deserialize the XMac once here to obtain the arg list.  Then we
        # generate code to deserialize and expand it in the client code.
        ctx.inject(@FILE.buffer, @LINE, ')'.buffer);
        ctx.putBack(tokStr);
        ctx.inject(@FILE.buffer, @LINE, 'deserializeXMac('.buffer);
    } catch (_ParseError ex) {
        ctx.error(ex.tok, CString(ex.text).buffer);
    }
}

## Returns a node list wrapping a single token.
NodeList makeNodeList(Token tok) {
    return NodeListImpl![Tok(tok)];
}

## Get an identifier, give a parse error if we got something else.
Token getIdent(CrackContext ctx) {
    tok := ctx.getToken();
    if (!tok.isIdent())
        ctx.error(tok, 'Identifier expected.'.buffer);
    return tok;
}

String _getParentNS(CrackContext ctx) {
    nsName := CString(ctx.getNamespaceName(), true);
    if ((pos := nsName.rfind(b'.')) != -1)
        return nsName.substr(0, pos);
    else
        return nsName;
}

Token _parseModuleName(CrackContext ctx) {
    modNameFmt := StringFormatter();
    modFirstTok := ctx.getToken();
    Token tok;
    if (modFirstTok.isDot()) {
        # If the first token is a dot, append the parent scope of the
        # auto-imports module - we'll want these imports relative to that.
        modNameFmt `$(_getParentNS(ctx)).`;
        tok = getIdent(ctx);
    } else if (modFirstTok.isIdent()) {
        tok = modFirstTok;
    } else {
        ctx.error(modFirstTok, 'Identifier or period expected.'.buffer);
    }
    modNameFmt.format(tok.getText());

    while (true) {
        tok = ctx.getToken();
        if (!tok.isDot()) {
            ctx.putBack(tok);
            break;
        }

        modNameFmt `.$(getIdent(ctx).getText())`;
    }
    modNameFmt `\0`;
    return Token(TOK_STRING, modNameFmt.string().buffer,
                 modFirstTok.getLocation()
                 );
}

## Auto imports.  This generates an "auto_import" annotation function that
## registers lazy imports for all of the names defined in it.
##
## Names and modules are identified with the syntax of the "import" statement,
## minus the "import" keyword itself:
##
##  @auto_imports {
##      module.name Import, OtherImport;
##      other.module AnotherName, AliasedName = Name;
##  }
##
## To use it, simply @import the module and use the auto_import annotation:
##
##  @import imports auto_import; @auto_import
void auto_imports(CrackContext ctx) {
    tok := ctx.getToken();
    if (!tok.isLCurly())
        ctx.error(tok, 'Curly brace expected.'.buffer);

    class Import {
        Token moduleName, localName, sourceName;
        oper init(Token moduleName, Token localName, Token sourceName) :
            moduleName = moduleName,
            localName = localName,
            sourceName = sourceName {
        }
    }
    imports := Array[Import]();

    while (true) {
        moduleName := _parseModuleName(ctx);

        while (true) {
            sourceName := localName := getIdent(ctx);
            tok = ctx.getToken();
            if (tok.isAssign()) {
                sourceName = getIdent(ctx);
                tok = ctx.getToken();
            }

            imports.append(
                Import(
                    moduleName,
                    Token(TOK_STRING, localName.getText(),
                          localName.getLocation()),
                    Token(TOK_STRING, sourceName.getText(),
                          sourceName.getLocation())
                )
            );

            if (tok.isSemi())
                break;
            else if (!tok.isComma())
                ctx.error(tok, 'Semicolon or comma expected'.buffer);
        }

        # Parse the closing curly.
        tok = ctx.getToken();
        if (tok.isRCurly())
            break;
        ctx.putBack(tok);
    }

    ctx.inject(@FILE.buffer, @LINE, '}'.buffer);
    for (imp :in imports) {
        # "ctx.addLazyImport($module.buffer, $localName.buffer, $sourceName.buffer,
        #                    false);
        ctx.inject(@FILE.buffer, @LINE, '.buffer, false);'.buffer);
        ctx.putBack(imp.sourceName);
        ctx.inject(@FILE.buffer, @LINE, '.buffer, '.buffer);
        ctx.putBack(imp.localName);
        ctx.inject(@FILE.buffer, @LINE, '.buffer, '.buffer);
        ctx.putBack(imp.moduleName);
        ctx.inject(@FILE.buffer, @LINE, 'ctx.addLazyImport('.buffer);
    }
    ctx.inject(@FILE.buffer, @LINE,
               'void auto_import(CrackContext ctx) {'.buffer
               );
}

## Expands the sanitized scope name as a string.
## This converts the "main script" scope name to simply ".main".
void SCOPE_NAME(CrackContext ctx) {
    result := CString(ctx.getNamespaceName(), true);
    if (result.startsWith('.main.'))
        result = '.main';
    ctx.putBack(Token(TOK_STRING, result.buffer, ctx.getLocation()));
}

## Expands the true (unsanitized) scope name.
void REAL_SCOPE_NAME(CrackContext ctx) {
    result := CString(ctx.getNamespaceName(), true);
    ctx.putBack(Token(TOK_STRING, result.buffer, ctx.getLocation()));
}