source: mainline/uspace/app/sbi/src/lex.c@ 051b3db8

/*
 * Copyright (c) 2011 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @file Lexer (lexical analyzer).
 *
 * Consumes a text file and produces a sequence of lexical elements (lems).
 */

#include <stdio.h>
#include <stdlib.h>
#include "bigint.h"
#include "cspan.h"
#include "mytypes.h"
#include "input.h"
#include "os/os.h"
#include "strtab.h"

#include "lex.h"

#define TAB_WIDTH 8

typedef enum {
        cs_chr,
        cs_str
} chr_str_t;

static void lex_touch(lex_t *lex);
static bool_t lex_read_try(lex_t *lex);

static void lex_skip_comment(lex_t *lex);
static void lex_skip_ws(lex_t *lex);
static bool_t is_wstart(char c);
static bool_t is_wcont(char c);
static bool_t is_digit(char c);
static void lex_word(lex_t *lex);
static void lex_char(lex_t *lex);
static void lex_number(lex_t *lex);
static void lex_string(lex_t *lex);
static void lex_char_string_core(lex_t *lex, chr_str_t cs);
static int digit_value(char c);

/* Note: This imposes an implementation limit on identifier length. */
#define IBUF_SIZE 128
static char ident_buf[IBUF_SIZE + 1];

/* XXX This imposes an implementation limit on string literal length. */
#define SLBUF_SIZE 128
static char strlit_buf[SLBUF_SIZE + 1];

/** Lclass-string pair */
struct lc_name {
        lclass_t lclass;
        const char *name;
};

/** Keyword names. Used both for printing and recognition. */
static struct lc_name keywords[] = {
        { lc_and,       "and" },
        { lc_as,        "as" },
        { lc_bool,      "bool" },
        { lc_break,     "break" },
        { lc_builtin,   "builtin" },
        { lc_char,      "char" },
        { lc_class,     "class" },
        { lc_deleg,     "deleg" },
        { lc_do,        "do" },
        { lc_elif,      "elif" },
        { lc_else,      "else" },
        { lc_end,       "end" },
        { lc_enum,      "enum" },
        { lc_except,    "except" },
        { lc_false,     "false" },
        { lc_finally,   "finally" },
        { lc_for,       "for" },
        { lc_fun,       "fun" },
        { lc_get,       "get" },
        { lc_if,        "if" },
        { lc_in,        "in" },
        { lc_int,       "int" },
        { lc_interface, "interface" },
        { lc_is,        "is" },
        { lc_new,       "new" },
        { lc_not,       "not" },
        { lc_nil,       "nil" },
        { lc_or,        "or" },
        { lc_override,  "override" },
        { lc_packed,    "packed" },
        { lc_private,   "private" },
        { lc_prop,      "prop" },
        { lc_protected, "protected" },
        { lc_public,    "public" },
        { lc_raise,     "raise" },
        { lc_resource,  "resource" },
        { lc_return,    "return" },
        { lc_self,      "self" },
        { lc_set,       "set" },
        { lc_static,    "static" },
        { lc_string,    "string" },
        { lc_struct,    "struct" },
        { lc_switch,    "switch" },
        { lc_then,      "then" },
        { lc_this,      "this" },
        { lc_true,      "true" },
        { lc_var,       "var" },
        { lc_with,      "with" },
        { lc_when,      "when" },
        { lc_while,     "while" },
        { lc_yield,     "yield" },

        { 0,            NULL }
};

/** Other simple lclasses. Only used for printing. */
static struct lc_name simple_lc[] = {
        { lc_invalid,   "INVALID" },
        { lc_eof,       "EOF" },

        /* Operators */
        { lc_period,    "." },
        { lc_slash,     "/" },
        { lc_lparen,    "(" },
        { lc_rparen,    ")" },
        { lc_lsbr,      "[" },
        { lc_rsbr,      "]" },
        { lc_equal,     "==" },
        { lc_notequal,  "!=" },
        { lc_lt,        "<" },
        { lc_gt,        ">" },
        { lc_lt_equal,  "<=" },
        { lc_gt_equal,  ">=" },
        { lc_assign,    "=" },
        { lc_plus,      "+" },
        { lc_minus,     "-" },
        { lc_mult,      "*" },
        { lc_increase,  "+=" },

        /* Punctuators */
        { lc_comma,     "," },
        { lc_colon,     ":" },
        { lc_scolon,    ";" },

        { 0,            NULL },
};

/** Print lclass value.
 *
 * Prints lclass (lexical element class) value in human-readable form
 * (for debugging).
 *
 * @param lclass        Lclass value for display.
 */
void lclass_print(lclass_t lclass)
{
        struct lc_name *dp;

        dp = keywords;
        while (dp->name != NULL) {
                if (dp->lclass == lclass) {
                        printf("%s", dp->name);
                        return;
                }
                ++dp;
        }

        dp = simple_lc;
        while (dp->name != NULL) {
                if (dp->lclass == lclass) {
                        printf("%s", dp->name);
                        return;
                }
                ++dp;
        }

        switch (lclass) {
        case lc_ident:
                printf("ident");
                break;
        case lc_lit_int:
                printf("int_literal");
                break;
        case lc_lit_string:
                printf("string_literal");
                break;
        default:
                printf("<unknown?>");
                break;
        }
}

/** Print lexical element.
 *
 * Prints lexical element in human-readable form (for debugging).
 *
 * @param lem           Lexical element for display.
 */
void lem_print(lem_t *lem)
{
        lclass_print(lem->lclass);

        switch (lem->lclass) {
        case lc_ident:
                printf("('%s')", strtab_get_str(lem->u.ident.sid));
                break;
        case lc_lit_int:
                printf("(");
                bigint_print(&lem->u.lit_int.value);
                printf(")");
                break;
        case lc_lit_string:
                printf("(\"%s\")", lem->u.lit_string.value);
        default:
                break;
        }
}

/** Print lem coordinates.
 *
 * Print the coordinates (line number, column number) of a lexical element.
 *
 * @param lem           Lexical element for coordinate printing.
 */
void lem_print_coords(lem_t *lem)
{
        cspan_print(lem->cspan);
}

/** Initialize lexer instance.
 *
 * @param lex           Lexer object to initialize.
 * @param input         Input to associate with lexer.
 */
void lex_init(lex_t *lex, struct input *input)
{
        int rc;

        lex->input = input;

        rc = input_get_line(lex->input, &lex->inbuf);
        if (rc != EOK) {
                printf("Error reading input.\n");
                exit(1);
        }

        lex->ibp = lex->inbuf;
        lex->col_adj = 0;
        lex->prev_valid = b_false;
        lex->current_valid = b_true;
}

/** Advance to next lexical element.
 *
 * The new element is read in lazily then it is actually accessed.
 *
 * @param lex           Lexer object.
 */
void lex_next(lex_t *lex)
{
        /* Make sure the current lem has already been read in. */
        lex_touch(lex);

        /* Force a new lem to be read on next access. */
        lex->current_valid = b_false;
}

/** Get current lem.
 *
 * The returned pointer is invalidated by next call to lex_next()
 *
 * @param lex           Lexer object.
 * @return              Pointer to current lem. Owned by @a lex and only valid
 *                      until next call to lex_xxx().
 */
lem_t *lex_get_current(lex_t *lex)
{
        lex_touch(lex);
        return &lex->current;
}

/** Get previous lem if valid.
 *
 * The returned pointer is invalidated by next call to lex_next()
 *
 * @param lex           Lexer object.
 * @return              Pointer to previous lem. Owned by @a lex and only valid
 *                      until next call to lex_xxx().
 */
lem_t *lex_peek_prev(lex_t *lex)
{
        if (lex->current_valid == b_false) {
                /*
                 * This means the head is advanced but next lem was not read.
                 * Thus the previous lem is still in @a current.
                 */
                return &lex->current;
        }

        if (lex->prev_valid != b_true) {
                /* Looks like we are still at the first lem. */
                return NULL;
        }

        /*
         * Current lem has been read in. Thus the previous lem was moved to
         * @a previous.
         */
        return &lex->prev;
}

/** Read in the current lexical element (unless already read in).
 *
 * @param lex           Lexer object.
 */
static void lex_touch(lex_t *lex)
{
        bool_t got_lem;

        if (lex->current_valid == b_true)
                return;

        /* Copy previous lem */
        lex->prev = lex->current;
        lex->prev_valid = b_true;

        do {
                got_lem = lex_read_try(lex);
        } while (got_lem == b_false);

        lex->current_valid = b_true;
}

/** Try reading next lexical element.
 *
 * Attemps to read the next lexical element. In some cases (such as a comment)
 * this function will need to give it another try and returns @c b_false
 * in such case.
 *
 * @param lex           Lexer object.
 * @return              @c b_true on success or @c b_false if it needs
 *                      restarting. On success the lem is stored to
 *                      the current lem in @a lex.
 */
static bool_t lex_read_try(lex_t *lex)
{
        char *bp, *lsp;
        int line0, col0;

        lex_skip_ws(lex);

        /*
         * Record lem coordinates. Line number we already have. For column
         * number we start with position in the input buffer. This works
         * for all characters except tab. Thus we keep track of tabs
         * separately using col_adj.
         */
        line0 = input_get_line_no(lex->input);
        col0 = 1 + lex->col_adj + (lex->ibp - lex->inbuf);

        lex->current.cspan = cspan_new(lex->input, line0, col0, line0, col0);

        lsp = lex->ibp;
        bp = lex->ibp;

        if (bp[0] == '\0') {
                /* End of input */
                lex->current.lclass = lc_eof;
                goto finish;
        }

        if (is_wstart(bp[0])) {
                lex_word(lex);
                goto finish;
        }

        if (bp[0] == '\'') {
                lex_char(lex);
                goto finish;
        }

        if (is_digit(bp[0])) {
                lex_number(lex);
                goto finish;
        }

        if (bp[0] == '"') {
                lex_string(lex);
                goto finish;
        }

        if (bp[0] == '-' && bp[1] == '-') {
                lex_skip_comment(lex);

                /* Compute ending column number */
                lex->current.cspan->col1 = col0 + (lex->ibp - lsp) - 1;

                /* Try again */
                return b_false;
        }

        switch (bp[0]) {
        case ',': lex->current.lclass = lc_comma; ++bp; break;
        case ':': lex->current.lclass = lc_colon; ++bp; break;
        case ';': lex->current.lclass = lc_scolon; ++bp; break;

        case '.': lex->current.lclass = lc_period; ++bp; break;
        case '/': lex->current.lclass = lc_slash; ++bp; break;
        case '(': lex->current.lclass = lc_lparen; ++bp; break;
        case ')': lex->current.lclass = lc_rparen; ++bp; break;
        case '[': lex->current.lclass = lc_lsbr; ++bp; break;
        case ']': lex->current.lclass = lc_rsbr; ++bp; break;

        case '=':
                if (bp[1] == '=') {
                        lex->current.lclass = lc_equal; bp += 2; break;
                }
                lex->current.lclass = lc_assign; ++bp; break;

        case '!':
                if (bp[1] == '=') {
                        lex->current.lclass = lc_notequal; bp += 2; break;
                }
                goto invalid;

        case '+':
                if (bp[1] == '=') {
                        lex->current.lclass = lc_increase; bp += 2; break;
                }
                lex->current.lclass = lc_plus; ++bp; break;

        case '-':
                lex->current.lclass = lc_minus; ++bp; break;

        case '*':
                lex->current.lclass = lc_mult; ++bp; break;

        case '<':
                if (bp[1] == '=') {
                        lex->current.lclass = lc_lt_equal; bp += 2; break;
                }
                lex->current.lclass = lc_lt; ++bp; break;

        case '>':
                if (bp[1] == '=') {
                        lex->current.lclass = lc_gt_equal; bp += 2; break;
                }
                lex->current.lclass = lc_gt; ++bp; break;

        default:
                goto invalid;
        }

        lex->ibp = bp;

finish:
        /* Compute ending column number */
        lex->current.cspan->col1 = col0 + (lex->ibp - lsp) - 1;
        return b_true;

invalid:
        lex->current.lclass = lc_invalid;
        ++bp;
        lex->ibp = bp;

        return b_true;
}

/** Lex a word (identifier or keyword).
 *
 * Read in a word. This may later turn out to be a keyword or a regular
 * identifier. It is stored in the current lem in @a lex.
 *
 * @param lex           Lexer object.
 */
static void lex_word(lex_t *lex)
{
        struct lc_name *dp;
        char *bp;
        int idx;

        bp = lex->ibp;
        ident_buf[0] = bp[0];
        idx = 1;

        while (is_wcont(bp[idx])) {
                if (idx >= IBUF_SIZE) {
                        printf("Error: Identifier too long.\n");
                        exit(1);
                }

                ident_buf[idx] = bp[idx];
                ++idx;
        }

        lex->ibp = bp + idx;

        ident_buf[idx] = '\0';

        dp = keywords;
        while (dp->name != NULL) {
                if (os_str_cmp(ident_buf, dp->name) == 0) {
                        /* Match */
                        lex->current.lclass = dp->lclass;
                        return;
                }
                ++dp;
        }

        /* No matching keyword -- it must be an identifier. */
        lex->current.lclass = lc_ident;
        lex->current.u.ident.sid = strtab_get_sid(ident_buf);
}

/** Lex a character literal.
 *
 * Reads in a character literal and stores it in the current lem in @a lex.
 *
 * @param lex           Lexer object.
 */
static void lex_char(lex_t *lex)
{
        size_t len;
        int char_val;

        lex_char_string_core(lex, cs_chr);

        len = os_str_length(strlit_buf);
        if (len != 1) {
                printf("Character literal should contain one character, "
                    "but contains %u characters instead.\n", (unsigned) len);
                exit(1);
        }

        os_str_get_char(strlit_buf, 0, &char_val);
        lex->current.lclass = lc_lit_char;
        bigint_init(&lex->current.u.lit_char.value, char_val);
}

/** Lex a numeric literal.
 *
 * Reads in a numeric literal and stores it in the current lem in @a lex.
 *
 * @param lex           Lexer object.
 */
static void lex_number(lex_t *lex)
{
        char *bp;
        bigint_t value;
        bigint_t dgval;
        bigint_t base;
        bigint_t tprod;

        bp = lex->ibp;

        bigint_init(&value, 0);
        bigint_init(&base, 10);

        while (is_digit(*bp)) {
                bigint_mul(&value, &base, &tprod);
                bigint_init(&dgval, digit_value(*bp));

                bigint_destroy(&value);
                bigint_add(&tprod, &dgval, &value);
                bigint_destroy(&tprod);
                bigint_destroy(&dgval);

                ++bp;
        }

        bigint_destroy(&base);

        lex->ibp = bp;

        lex->current.lclass = lc_lit_int;
        bigint_shallow_copy(&value, &lex->current.u.lit_int.value);
}

/** Lex a string literal.
 *
 * Reads in a string literal and stores it in the current lem in @a lex.
 *
 * @param lex           Lexer object.
 */
static void lex_string(lex_t *lex)
{
        lex_char_string_core(lex, cs_str);

        lex->current.lclass = lc_lit_string;
        lex->current.u.lit_string.value = os_str_dup(strlit_buf);
}

static void lex_char_string_core(lex_t *lex, chr_str_t cs)
{
        char *bp;
        int sidx, didx;
        char term;
        const char *descr, *cap_descr;
        char spchar;

        /* Make compiler happy */
        term = '\0';
        descr = NULL;
        cap_descr = NULL;

        switch (cs) {
        case cs_chr:
                term = '\'';
                descr = "character";
                cap_descr = "Character";
                break;
        case cs_str:
                term = '"';
                descr = "string";
                cap_descr = "String";
                break;
        }

        bp = lex->ibp + 1;
        sidx = didx = 0;

        while (bp[sidx] != term) {
                if (didx >= SLBUF_SIZE) {
                        printf("Error: %s literal too long.\n", cap_descr);
                        exit(1);
                }

                if (bp[sidx] == '\0') {
                        printf("Error: Unterminated %s literal.\n", descr);
                        exit(1);
                }

                if (bp[sidx] == '\\') {
                        switch (bp[sidx + 1]) {
                        case '\\':
                                spchar = '\\';
                                break;
                        case '\'':
                                spchar = '\'';
                                break;
                        case '"':
                                spchar = '"';
                                break;
                        case 'n':
                                spchar = '\n';
                                break;
                        case 't':
                                spchar = '\t';
                                break;
                        default:
                                printf("Error: Unknown character escape sequence.\n");
                                exit(1);
                        }

                        strlit_buf[didx] = spchar;
                        ++didx;
                        sidx += 2;
                } else {
                        strlit_buf[didx] = bp[sidx];
                        ++sidx; ++didx;
                }
        }

        lex->ibp = bp + sidx + 1;

        strlit_buf[didx] = '\0';
}

/** Lex a single-line comment.
 *
 * This does not produce any lem. The comment is just skipped.
 *
 * @param lex           Lexer object.
 */
static void lex_skip_comment(lex_t *lex)
{
        char *bp;

        bp = lex->ibp + 2;

        while (*bp != '\n' && *bp != '\0') {
                ++bp;
        }

        lex->ibp = bp;
}

/** Skip whitespace characters.
 *
 * This does not produce any lem. The whitespace is just skipped.
 *
 * @param lex           Lexer object.
 */
static void lex_skip_ws(lex_t *lex)
{
        char *bp;
        int rc;

        bp = lex->ibp;

        while (b_true) {
                while (*bp == ' ' || *bp == '\t') {
                        if (*bp == '\t') {
                                /* XXX This is too simplifed. */
                                lex->col_adj += (TAB_WIDTH - 1);
                        }
                        ++bp;
                }

                if (*bp != '\n')
                        break;

                /* Read next line */
                rc = input_get_line(lex->input, &lex->inbuf);
                if (rc != EOK) {
                        printf("Error reading input.\n");
                        exit(1);
                }

                bp = lex->inbuf;
                lex->col_adj = 0;
        }

        lex->ibp = bp;
}

/** Determine if character can start a word.
 *
 * @param c     Character.
 * @return      @c b_true if @a c can start a word, @c b_false otherwise.
 */
static bool_t is_wstart(char c)
{
        return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z')) ||
            (c == '_');
}

/** Determine if character can continue a word.
 *
 * @param c     Character.
 * @return      @c b_true if @a c can start continue word, @c b_false
 *              otherwise.
 */
static bool_t is_wcont(char c)
{
        return is_digit(c) || is_wstart(c);
}

/** Determine if character is a numeric digit.
 *
 * @param c     Character.
 * @return      @c b_true if @a c is a numeric digit, @c b_false otherwise.
 */
static bool_t is_digit(char c)
{
        return ((c >= '0') && (c <= '9'));
}

/** Determine numeric value of digit character.
 *
 * @param c     Character, must be a valid decimal digit.
 * @return      Value of the digit (0-9).
 */
static int digit_value(char c)
{
        return (c - '0');
}