Token *
consume_token(Tokens *tokens) {
    if (tokens->n == 0) {
        return NULL;
    }
    Token *ret = tokens->start;
    tokens->start = &tokens->start[1];
    tokens->n--;
    return ret;
}

Object *
parse(Tokens *tokens) {
    while (tokens->n > 0) {
        Token *token = consume_token(tokens);
        if (token == NULL) {
            return NULL;
        }

        switch (token->type) {
            case TOKEN_FIXNUM: {
                ssize_t num = 0;
                int sign = 1;
                for (size_t i = 0; i < token->value.n; i++) {
                    char c = token->value.start[i];
                    if (c == '-') {
                        sign = -1;
                        continue;
                    }
                    num = num * 10 + (c - '0');
                }
                return make_fixnum(num * sign);
            } break;
            case TOKEN_BOOL: {
                if (sv_equal(token->value, TRUE_TOKEN)) {
                    return obj_true;
                }
                if (sv_equal(token->value, FALSE_TOKEN)) {
                    return obj_false;
                }
            } break;
            case TOKEN_RPAREN: {
                return NULL;
            } break;
            case TOKEN_LPAREN: {
                if (tokens->n > 0 && tokens->start[0].type == TOKEN_RPAREN) {
                    return obj_nil;
                }

                Object *next_obj = parse(tokens);
                if (next_obj == NULL) {
                    return NULL;
                }
                Object *root = make_pair(next_obj, obj_nil);
                Object *list = root;
                while (tokens->n > 0 && (next_obj = parse(tokens)) != NULL) {
                    list->cdr = make_pair(next_obj, obj_nil);
                    list = list->cdr;
                }
                return root;
            } break;
            case TOKEN_STRING: {
                Object *obj = make_empty_string();
                append_string(obj, token->value);
                return obj;
            } break;
            case TOKEN_SYMBOL: {
                return make_symbol(token->value.start, token->value.n);
            } break;
            default: {
                fprintf(stderr, "error: unknown token\n");
            } break;
        }
    }

    return NULL;
}