From d45a5b21de22438c004e1db96a8f154da09cdc0e Mon Sep 17 00:00:00 2001 From: Oskari Timperi Date: Wed, 14 May 2014 22:27:34 +0300 Subject: Initial commit - tokenizing, parsing and basic eval support - arithmetic (+, -, *, /) - quote - atom for checking if the arg is an atom (i.e. not a list) - eq for checking equality - > for checking order - if - some unit testing - simple repl - mem management needs improvement :-) --- .gitignore | 1 + Makefile | 27 ++ atom.c | 100 ++++++ atom.h | 57 ++++ eval.c | 291 ++++++++++++++++ eval.h | 7 + linenoise.c | 1090 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ linenoise.h | 66 ++++ list.c | 99 ++++++ list.h | 19 ++ parse.c | 184 ++++++++++ parse.h | 12 + repl.c | 27 ++ test_util.h | 93 +++++ tokens.c | 188 +++++++++++ tokens.h | 24 ++ tst_main.c | 2 + 17 files changed, 2287 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 atom.c create mode 100644 atom.h create mode 100644 eval.c create mode 100644 eval.h create mode 100644 linenoise.c create mode 100644 linenoise.h create mode 100644 list.c create mode 100644 list.h create mode 100644 parse.c create mode 100644 parse.h create mode 100644 repl.c create mode 100644 test_util.h create mode 100644 tokens.c create mode 100644 tokens.h create mode 100644 tst_main.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..5761abc --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +*.o diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..f53a3f0 --- /dev/null +++ b/Makefile @@ -0,0 +1,27 @@ +SOURCES = parse.c list.c atom.c eval.c tokens.c +OBJECTS = $(SOURCES:.c=.o) + +CFLAGS = -Wall -g +LDFLAGS = + +CC = gcc +LD = gcc + +# ifneq ($(BUILD_TEST),) + +test: CFLAGS := $(CFLAGS) -DBUILD_TEST +test: $(OBJECTS) tst_main.o + $(LD) $(LDFLAGS) -o $@ $^ + +# else + +repl: $(OBJECTS) repl.o linenoise.o + $(LD) $(LDFLAGS) -o $@ $^ + +# endif + +.PHONY: clean +clean: + rm -f *.o + rm -f test + rm -f repl diff --git a/atom.c b/atom.c new file mode 100644 index 0000000..73ecd7e --- /dev/null +++ b/atom.c @@ -0,0 +1,100 @@ +#include "atom.h" +#include "list.h" + +#include +#include + +struct atom true_atom; +struct atom false_atom; +struct atom nil_atom; + +struct atom *atom_new(char type) +{ + struct atom *atom = calloc(1, sizeof(*atom)); + atom->type = type; + return atom; +} + +struct atom *atom_new_int(long l) +{ + struct atom *atom = atom_new(ATOM_INT); + atom->l = l; + return atom; +} + +struct atom *atom_new_str(const char *str, int len) +{ + struct atom *atom = atom_new(ATOM_STR); + atom->str.str = strndup(str, len); + atom->str.len = len; + return atom; +} + +struct atom *atom_new_sym(const char *sym, int len) +{ + struct atom *atom = atom_new_str(sym, len); + atom->type = ATOM_SYMBOL; + return atom; +} + +struct atom *atom_new_list(struct list *list) +{ + struct atom *atom = atom_new(ATOM_LIST); + atom->list = list; + return atom; +} + +#ifdef BUILD_TEST + +#include "test_util.h" + +TEST(atom_new) +{ + struct atom *atom = atom_new(ATOM_STR); + ASSERT_TRUE(atom != NULL); + ASSERT_EQ(ATOM_STR, atom->type); +} + +TEST(atom_new_int) +{ + struct atom *atom = atom_new_int(42); + ASSERT_TRUE(atom != NULL); + ASSERT_EQ(42, atom->l); +} + +TEST(atom_new_str) +{ + struct atom *atom = atom_new_str("foobar", 6); + ASSERT_TRUE(atom != NULL); + ASSERT_STREQ("foobar", atom->str.str); + + atom = atom_new_str("foobar", 3); + ASSERT_TRUE(atom != NULL); + ASSERT_STREQ("foo", atom->str.str); + + ASSERT_EQ(ATOM_STR, atom->type); +} + +TEST(atom_new_sym) +{ + struct atom *atom = atom_new_sym("foobar", 6); + ASSERT_TRUE(atom != NULL); + ASSERT_STREQ("foobar", atom->str.str); + + atom = atom_new_sym("foobar", 3); + ASSERT_TRUE(atom != NULL); + ASSERT_STREQ("foo", atom->str.str); + + ASSERT_EQ(ATOM_SYMBOL, atom->type); +} + +TEST(atom_new_list) +{ + struct list list; + struct atom *atom = atom_new_list(&list); + ASSERT_TRUE(atom != NULL); + ASSERT_EQ(&list, atom->list); + ASSERT_EQ(ATOM_LIST, atom->type); +} + +#endif diff --git a/atom.h b/atom.h new file mode 100644 index 0000000..3b716fa --- /dev/null +++ b/atom.h @@ -0,0 +1,57 @@ +#ifndef ATOM_H +#define ATOM_H + +#define LIST_GET_ATOM(LIST) ((struct atom *) (LIST)->data) + +#define ATOM_TYPE(LIST) ((LIST_GET_ATOM(LIST))->type) +#define IS_INT(LIST) ((ATOM_TYPE(LIST)) == ATOM_INT) +#define IS_STR(LIST) ((ATOM_TYPE(LIST)) == ATOM_STR) +#define IS_SYM(LIST) ((ATOM_TYPE(LIST)) == ATOM_SYMBOL) +#define IS_LIST(LIST) ((ATOM_TYPE(LIST)) == ATOM_LIST) + +#define IS_TRUE(LIST) (LIST_GET_ATOM(LIST) == &true_atom) +#define IS_FALSE(LIST) (LIST_GET_ATOM(LIST) == &false_atom) +#define IS_NIL(LIST) (LIST_GET_ATOM(LIST) == &nil_atom) + +#define CAR(LIST) LIST + +#define CDR(LIST) ((LIST) != NULL ? (LIST)->next : NULL) +#define CDDR(LIST) CDR(CDR(LIST)) + +enum +{ + ATOM_NIL, + ATOM_INT, + ATOM_STR, + ATOM_SYMBOL, + ATOM_LIST +}; + +struct atom +{ + union + { + long l; + struct + { + char *str; + int len; + } str; + struct list *list; + }; + char type; +}; + +struct list; + +struct atom *atom_new(char type); +struct atom *atom_new_int(long l); +struct atom *atom_new_str(const char *str, int len); +struct atom *atom_new_sym(const char *sym, int len); +struct atom *atom_new_list(struct list *list); + +extern struct atom true_atom; +extern struct atom false_atom; +extern struct atom nil_atom; + +#endif diff --git a/eval.c b/eval.c new file mode 100644 index 0000000..43e1e05 --- /dev/null +++ b/eval.c @@ -0,0 +1,291 @@ +#include "eval.h" +#include "list.h" +#include "atom.h" +#include "parse.h" + +#include + +static int atom_cmp(struct list *a, struct list *b) +{ + if (ATOM_TYPE(a) != ATOM_TYPE(b)) + return 0; + + if (IS_TRUE(a) && !IS_TRUE(b)) + return 0; + + if (IS_FALSE(a) && !IS_FALSE(b)) + return 0; + + if (IS_TRUE(b) && !IS_TRUE(a)) + return 0; + + if (IS_FALSE(b) && !IS_FALSE(a)) + return 0; + + if (IS_NIL(a) && !IS_NIL(b)) + return 0; + + if (IS_NIL(b) && !IS_NIL(a)) + return 0; + + int result = 1; + + switch (ATOM_TYPE(a)) + { + case ATOM_INT: + if (LIST_GET_ATOM(a)->l != LIST_GET_ATOM(b)->l) + result = 0; + break; + + case ATOM_STR: + case ATOM_SYMBOL: + if (strcmp(LIST_GET_ATOM(a)->str.str, LIST_GET_ATOM(b)->str.str) != 0) + result = 0; + break; + + case ATOM_LIST: + { + struct list *ai = LIST_GET_ATOM(a)->list; + struct list *bi = LIST_GET_ATOM(b)->list; + + while (ai && bi) + { + if (!atom_cmp(ai, bi)) + { + result = 0; + break; + } + + ai = ai->next; + bi = bi->next; + } + + if (ai != NULL || bi != NULL) + result = 0; + + break; + } + } + + return result; +} + +struct list *eval(struct list *list) +{ + if (!IS_LIST(list)) + return list; + + struct list *l = LIST_GET_ATOM(list)->list; + + if (IS_SYM(l)) + { + const char *sym = LIST_GET_ATOM(l)->str.str; + + if (strcmp(sym, "quote") == 0) + { + return l->next; + } + else if (strcmp(sym, "atom") == 0) + { + if (IS_LIST(l->next)) + { + return list_append(NULL, &false_atom); + } + else + { + return list_append(NULL, &true_atom); + } + } + else if (strcmp(sym, "eq") == 0) + { + struct list *a = l->next; + if (!a) + return list_append(NULL, &false_atom); + + struct list *b = a->next; + if (!b) + return list_append(NULL, &false_atom); + + a = eval(a); + b = eval(b); + + if (atom_cmp(a, b)) + return list_append(NULL, &true_atom); + + return list_append(NULL, &false_atom); + } + else if (strncmp(sym, "+", 1) == 0 || + strncmp(sym, "-", 1) == 0 || + strncmp(sym, "/", 1) == 0 || + strncmp(sym, "*", 1) == 0) + { + struct list *oper = CAR(l); + struct list *a = CDR(oper); + struct list *b = CDDR(oper); + + if (!a || !b) + return list_append(NULL, &nil_atom); + + a = eval(a); + b = eval(b); + + if (!(ATOM_TYPE(a) == ATOM_TYPE(b) && ATOM_TYPE(a) == ATOM_INT)) + return list_append(NULL, &nil_atom); + + long numa = LIST_GET_ATOM(a)->l; + long numb = LIST_GET_ATOM(b)->l; + long numr; + + switch (*sym) + { + case '+': + numr = numa + numb; + break; + case '-': + numr = numa - numb; + break; + case '/': + numr = numa / numb; + break; + case '*': + numr = numa * numb; + break; + } + + struct list *result = list_append(NULL, atom_new_int(numr)); + + return result; + } + else if (strncmp(sym, ">", 1) == 0) + { + struct list *oper = CAR(l); + struct list *a = CDR(oper); + struct list *b = CDDR(oper); + + if (!a || !b) + return list_append(NULL, &nil_atom); + + a = eval(a); + b = eval(b); + + if (!(ATOM_TYPE(a) == ATOM_TYPE(b) && ATOM_TYPE(a) == ATOM_INT)) + return list_append(NULL, &nil_atom); + + long numa = LIST_GET_ATOM(a)->l; + long numb = LIST_GET_ATOM(b)->l; + + if (numa > numb) + return list_append(NULL, &true_atom); + else + return list_append(NULL, &false_atom); + } + else if (strcmp(sym, "if") == 0) + { + struct list *predicate = CDR(l); + struct list *true_case = CDR(predicate); + struct list *false_case = CDR(true_case); + + if (!predicate || !true_case || !false_case) + return list_append(NULL, &nil_atom); + + predicate = eval(predicate); + + if (IS_TRUE(predicate)) + return eval(true_case); + else + return eval(false_case); + } + } + else if (IS_LIST(l)) + { + return eval(l); + } + + return list_append(NULL, &nil_atom); +} + +struct list *eval_str(const char *str) +{ + struct list *result; + int pos = 0; + + result = eval(parse(str, &pos)); + + return result; +} + +#ifdef BUILD_TEST + +#include "test_util.h" + +TEST(eval) +{ + struct list *result; + int pos; + +#define EVAL(EXPR) \ + pos = 0; \ + result = eval(parse((EXPR), &pos)) + +#define ARITHMETIC_TEST(EXPR, RESULT) \ + EVAL(EXPR); \ + ASSERT_EQ(ATOM_INT, ATOM_TYPE(result)); \ + ASSERT_EQ(RESULT, LIST_GET_ATOM(result)->l) + + ARITHMETIC_TEST("(+ 1 2)", 3); + ARITHMETIC_TEST("(- 5 10)", -5); + ARITHMETIC_TEST("(/ 42 2)", 21); + ARITHMETIC_TEST("(* 5 10)", 50); + ARITHMETIC_TEST("(* (* 2 (+ 1 1)) 2)", 8); + +#undef ARITHMETIC_TEST + +#define EQ_TEST(EXPR, RESULT) \ + EVAL(EXPR); \ + ASSERT_EQ(result, RESULT) + +#define EQ_TEST_T(EXPR) EVAL(EXPR); ASSERT(IS_TRUE(result)) +#define EQ_TEST_F(EXPR) EVAL(EXPR); ASSERT(IS_FALSE(result)) + + EQ_TEST_T("(eq 1 1)"); + EQ_TEST_T("(eq (+ 1 1) 2)"); + EQ_TEST_T("(eq (quote (1 2 3)) (quote (1 2 3)))"); + + EQ_TEST_T("(eq \"eka\" \"eka\""); + EQ_TEST_F("(eq \"eka\" eka)"); + EQ_TEST_F("(eq \"eka\" 100)"); + EQ_TEST_F("(eq \"eka\" \"toka\""); + + EQ_TEST_T("(eq eka eka)"); + EQ_TEST_F("(eq eka toka)"); + + EQ_TEST_F("(eq 1 2)"); + EQ_TEST_F("(eq 1 (- 1 1))"); + EQ_TEST_F("(eq (quote (1)) (quote (1 2 3)))"); + + EQ_TEST_T("(eq (quote (1 2)) '(1 2))"); + EQ_TEST_T("(eq 'bar 'bar)"); + EQ_TEST_F("(eq 'foo 'bar)"); + EQ_TEST_T("(eq (quote bar) 'bar)"); + EQ_TEST_F("(eq (quote foo) 'bar)"); + + EQ_TEST_F("(> 1 2)"); + EQ_TEST_T("(> 2 1)"); + +#undef EQ_TEST_F +#undef EQ_TEST_T +#undef EQ_TEST + + EVAL("(if #t 1 2)"); + ASSERT_EQ(1, LIST_GET_ATOM(result)->l); + + EVAL("(if #t (+ 1 1) (* 2 2))"); + ASSERT_EQ(2, LIST_GET_ATOM(result)->l); + + EVAL("(if #f (+ 1 1) (* 2 2))"); + ASSERT_EQ(4, LIST_GET_ATOM(result)->l); + +#undef EVAL +} + +#endif /* BUILD_TEST */ diff --git a/eval.h b/eval.h new file mode 100644 index 0000000..d22355b --- /dev/null +++ b/eval.h @@ -0,0 +1,7 @@ +#ifndef EVAL_H +#define EVAL_H + +struct list *eval(struct list *list); +struct list *eval_str(const char *str); + +#endif diff --git a/linenoise.c b/linenoise.c new file mode 100644 index 0000000..aef5cdd --- /dev/null +++ b/linenoise.c @@ -0,0 +1,1090 @@ +/* linenoise.c -- guerrilla line editing library against the idea that a + * line editing lib needs to be 20,000 lines of C code. + * + * You can find the latest source code at: + * + * http://github.com/antirez/linenoise + * + * Does a number of crazy assumptions that happen to be true in 99.9999% of + * the 2010 UNIX computers around. + * + * ------------------------------------------------------------------------ + * + * Copyright (c) 2010-2013, Salvatore Sanfilippo + * Copyright (c) 2010-2013, Pieter Noordhuis + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "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 COPYRIGHT + * HOLDER OR CONTRIBUTORS 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. + * + * ------------------------------------------------------------------------ + * + * References: + * - http://invisible-island.net/xterm/ctlseqs/ctlseqs.html + * - http://www.3waylabs.com/nw/WWW/products/wizcon/vt220.html + * + * Todo list: + * - Filter bogus Ctrl+ combinations. + * - Win32 support + * + * Bloat: + * - History search like Ctrl+r in readline? + * + * List of escape sequences used by this program, we do everything just + * with three sequences. In order to be so cheap we may have some + * flickering effect with some slow terminal, but the lesser sequences + * the more compatible. + * + * CHA (Cursor Horizontal Absolute) + * Sequence: ESC [ n G + * Effect: moves cursor to column n + * + * EL (Erase Line) + * Sequence: ESC [ n K + * Effect: if n is 0 or missing, clear from cursor to end of line + * Effect: if n is 1, clear from beginning of line to cursor + * Effect: if n is 2, clear entire line + * + * CUF (CUrsor Forward) + * Sequence: ESC [ n C + * Effect: moves cursor forward of n chars + * + * When multi line mode is enabled, we also use an additional escape + * sequence. However multi line editing is disabled by default. + * + * CUU (Cursor Up) + * Sequence: ESC [ n A + * Effect: moves cursor up of n chars. + * + * CUD (Cursor Down) + * Sequence: ESC [ n B + * Effect: moves cursor down of n chars. + * + * The following are used to clear the screen: ESC [ H ESC [ 2 J + * This is actually composed of two sequences: + * + * cursorhome + * Sequence: ESC [ H + * Effect: moves the cursor to upper left corner + * + * ED2 (Clear entire screen) + * Sequence: ESC [ 2 J + * Effect: clear the whole screen + * + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "linenoise.h" + +#define LINENOISE_DEFAULT_HISTORY_MAX_LEN 100 +#define LINENOISE_MAX_LINE 4096 +static char *unsupported_term[] = {"dumb","cons25","emacs",NULL}; +static linenoiseCompletionCallback *completionCallback = NULL; + +static struct termios orig_termios; /* In order to restore at exit.*/ +static int rawmode = 0; /* For atexit() function to check if restore is needed*/ +static int mlmode = 0; /* Multi line mode. Default is single line. */ +static int atexit_registered = 0; /* Register atexit just 1 time. */ +static int history_max_len = LINENOISE_DEFAULT_HISTORY_MAX_LEN; +static int history_len = 0; +static char **history = NULL; + +/* The linenoiseState structure represents the state during line editing. + * We pass this state to functions implementing specific editing + * functionalities. */ +struct linenoiseState { + int ifd; /* Terminal stdin file descriptor. */ + int ofd; /* Terminal stdout file descriptor. */ + char *buf; /* Edited line buffer. */ + size_t buflen; /* Edited line buffer size. */ + const char *prompt; /* Prompt to display. */ + size_t plen; /* Prompt length. */ + size_t pos; /* Current cursor position. */ + size_t oldpos; /* Previous refresh cursor position. */ + size_t len; /* Current edited line length. */ + size_t cols; /* Number of columns in terminal. */ + size_t maxrows; /* Maximum num of rows used so far (multiline mode) */ + int history_index; /* The history index we are currently editing. */ +}; + +enum KEY_ACTION{ + KEY_NULL = 0, /* NULL */ + CTRL_A = 1, /* Ctrl+a */ + CTRL_B = 2, /* Ctrl-b */ + CTRL_C = 3, /* Ctrl-c */ + CTRL_D = 4, /* Ctrl-d */ + CTRL_E = 5, /* Ctrl-e */ + CTRL_F = 6, /* Ctrl-f */ + CTRL_H = 8, /* Ctrl-h */ + TAB = 9, /* Tab */ + CTRL_K = 11, /* Ctrl+k */ + CTRL_L = 12, /* Ctrl+l */ + ENTER = 13, /* Enter */ + CTRL_N = 14, /* Ctrl-n */ + CTRL_P = 16, /* Ctrl-p */ + CTRL_T = 20, /* Ctrl-t */ + CTRL_U = 21, /* Ctrl+u */ + CTRL_W = 23, /* Ctrl+w */ + ESC = 27, /* Escape */ + BACKSPACE = 127 /* Backspace */ +}; + +static void linenoiseAtExit(void); +int linenoiseHistoryAdd(const char *line); +static void refreshLine(struct linenoiseState *l); + +/* Debugging macro. */ +#if 0 +FILE *lndebug_fp = NULL; +#define lndebug(...) \ + do { \ + if (lndebug_fp == NULL) { \ + lndebug_fp = fopen("/tmp/lndebug.txt","a"); \ + fprintf(lndebug_fp, \ + "[%d %d %d] p: %d, rows: %d, rpos: %d, max: %d, oldmax: %d\n", \ + (int)l->len,(int)l->pos,(int)l->oldpos,plen,rows,rpos, \ + (int)l->maxrows,old_rows); \ + } \ + fprintf(lndebug_fp, ", " __VA_ARGS__); \ + fflush(lndebug_fp); \ + } while (0) +#else +#define lndebug(fmt, ...) +#endif + +/* ======================= Low level terminal handling ====================== */ + +/* Set if to use or not the multi line mode. */ +void linenoiseSetMultiLine(int ml) { + mlmode = ml; +} + +/* Return true if the terminal name is in the list of terminals we know are + * not able to understand basic escape sequences. */ +static int isUnsupportedTerm(void) { + char *term = getenv("TERM"); + int j; + + if (term == NULL) return 0; + for (j = 0; unsupported_term[j]; j++) + if (!strcasecmp(term,unsupported_term[j])) return 1; + return 0; +} + +/* Raw mode: 1960 magic shit. */ +static int enableRawMode(int fd) { + struct termios raw; + + if (!isatty(STDIN_FILENO)) goto fatal; + if (!atexit_registered) { + atexit(linenoiseAtExit); + atexit_registered = 1; + } + if (tcgetattr(fd,&orig_termios) == -1) goto fatal; + + raw = orig_termios; /* modify the original mode */ + /* input modes: no break, no CR to NL, no parity check, no strip char, + * no start/stop output control. */ + raw.c_iflag &= ~(BRKINT | ICRNL | INPCK | ISTRIP | IXON); + /* output modes - disable post processing */ + raw.c_oflag &= ~(OPOST); + /* control modes - set 8 bit chars */ + raw.c_cflag |= (CS8); + /* local modes - choing off, canonical off, no extended functions, + * no signal chars (^Z,^C) */ + raw.c_lflag &= ~(ECHO | ICANON | IEXTEN | ISIG); + /* control chars - set return condition: min number of bytes and timer. + * We want read to return every single byte, without timeout. */ + raw.c_cc[VMIN] = 1; raw.c_cc[VTIME] = 0; /* 1 byte, no timer */ + + /* put terminal in raw mode after flushing */ + if (tcsetattr(fd,TCSAFLUSH,&raw) < 0) goto fatal; + rawmode = 1; + return 0; + +fatal: + errno = ENOTTY; + return -1; +} + +static void disableRawMode(int fd) { + /* Don't even check the return value as it's too late. */ + if (rawmode && tcsetattr(fd,TCSAFLUSH,&orig_termios) != -1) + rawmode = 0; +} + +/* Use the ESC [6n escape sequence to query the horizontal cursor position + * and return it. On error -1 is returned, on success the position of the + * cursor. */ +static int getCursorPosition(int ifd, int ofd) { + char buf[32]; + int cols, rows; + unsigned int i = 0; + + /* Report cursor location */ + if (write(ofd, "\x1b[6n", 4) != 4) return -1; + + /* Read the response: ESC [ rows ; cols R */ + while (i < sizeof(buf)-1) { + if (read(ifd,buf+i,1) != 1) break; + if (buf[i] == 'R') break; + i++; + } + buf[i] = '\0'; + + /* Parse it. */ + if (buf[0] != ESC || buf[1] != '[') return -1; + if (sscanf(buf+2,"%d;%d",&rows,&cols) != 2) return -1; + return cols; +} + +/* Try to get the number of columns in the current terminal, or assume 80 + * if it fails. */ +static int getColumns(int ifd, int ofd) { + struct winsize ws; + + if (ioctl(1, TIOCGWINSZ, &ws) == -1 || ws.ws_col == 0) { + /* ioctl() failed. Try to query the terminal itself. */ + int start, cols; + + /* Get the initial position so we can restore it later. */ + start = getCursorPosition(ifd,ofd); + if (start == -1) goto failed; + + /* Go to right margin and get position. */ + if (write(ofd,"\x1b[999C",6) != 6) goto failed; + cols = getCursorPosition(ifd,ofd); + if (cols == -1) goto failed; + + /* Restore position. */ + if (cols > start) { + char seq[32]; + snprintf(seq,32,"\x1b[%dD",cols-start); + if (write(ofd,seq,strlen(seq)) == -1) { + /* Can't recover... */ + } + } + return cols; + } else { + return ws.ws_col; + } + +failed: + return 80; +} + +/* Clear the screen. Used to handle ctrl+l */ +void linenoiseClearScreen(void) { + if (write(STDOUT_FILENO,"\x1b[H\x1b[2J",7) <= 0) { + /* nothing to do, just to avoid warning. */ + } +} + +/* Beep, used for completion when there is nothing to complete or when all + * the choices were already shown. */ +static void linenoiseBeep(void) { + fprintf(stderr, "\x7"); + fflush(stderr); +} + +/* ============================== Completion ================================ */ + +/* Free a list of completion option populated by linenoiseAddCompletion(). */ +static void freeCompletions(linenoiseCompletions *lc) { + size_t i; + for (i = 0; i < lc->len; i++) + free(lc->cvec[i]); + if (lc->cvec != NULL) + free(lc->cvec); +} + +/* This is an helper function for linenoiseEdit() and is called when the + * user types the key in order to complete the string currently in the + * input. + * + * The state of the editing is encapsulated into the pointed linenoiseState + * structure as described in the structure definition. */ +static int completeLine(struct linenoiseState *ls) { + linenoiseCompletions lc = { 0, NULL }; + int nread, nwritten; + char c = 0; + + completionCallback(ls->buf,&lc); + if (lc.len == 0) { + linenoiseBeep(); + } else { + size_t stop = 0, i = 0; + + while(!stop) { + /* Show completion or original buffer */ + if (i < lc.len) { + struct linenoiseState saved = *ls; + + ls->len = ls->pos = strlen(lc.cvec[i]); + ls->buf = lc.cvec[i]; + refreshLine(ls); + ls->len = saved.len; + ls->pos = saved.pos; + ls->buf = saved.buf; + } else { + refreshLine(ls); + } + + nread = read(ls->ifd,&c,1); + if (nread <= 0) { + freeCompletions(&lc); + return -1; + } + + switch(c) { + case 9: /* tab */ + i = (i+1) % (lc.len+1); + if (i == lc.len) linenoiseBeep(); + break; + case 27: /* escape */ + /* Re-show original buffer */ + if (i < lc.len) refreshLine(ls); + stop = 1; + break; + default: + /* Update buffer and return */ + if (i < lc.len) { + nwritten = snprintf(ls->buf,ls->buflen,"%s",lc.cvec[i]); + ls->len = ls->pos = nwritten; + } + stop = 1; + break; + } + } + } + + freeCompletions(&lc); + return c; /* Return last read character */ +} + +/* Register a callback function to be called for tab-completion. */ +void linenoiseSetCompletionCallback(linenoiseCompletionCallback *fn) { + completionCallback = fn; +} + +/* This function is used by the callback function registered by the user + * in order to add completion options given the input string when the + * user typed . See the example.c source code for a very easy to + * understand example. */ +void linenoiseAddCompletion(linenoiseCompletions *lc, const char *str) { + size_t len = strlen(str); + char *copy, **cvec; + + copy = malloc(len+1); + if (copy == NULL) return; + memcpy(copy,str,len+1); + cvec = realloc(lc->cvec,sizeof(char*)*(lc->len+1)); + if (cvec == NULL) { + free(copy); + return; + } + lc->cvec = cvec; + lc->cvec[lc->len++] = copy; +} + +/* =========================== Line editing ================================= */ + +/* We define a very simple "append buffer" structure, that is an heap + * allocated string where we can append to. This is useful in order to + * write all the escape sequences in a buffer and flush them to the standard + * output in a single call, to avoid flickering effects. */ +struct abuf { + char *b; + int len; +}; + +static void abInit(struct abuf *ab) { + ab->b = NULL; + ab->len = 0; +} + +static void abAppend(struct abuf *ab, const char *s, int len) { + char *new = realloc(ab->b,ab->len+len); + + if (new == NULL) return; + memcpy(new+ab->len,s,len); + ab->b = new; + ab->len += len; +} + +static void abFree(struct abuf *ab) { + free(ab->b); +} + +/* Single line low level line refresh. + * + * Rewrite the currently edited line accordingly to the buffer content, + * cursor position, and number of columns of the terminal. */ +static void refreshSingleLine(struct linenoiseState *l) { + char seq[64]; + size_t plen = strlen(l->prompt); + int fd = l->ofd; + char *buf = l->buf; + size_t len = l->len; + size_t pos = l->pos; + struct abuf ab; + + while((plen+pos) >= l->cols) { + buf++; + len--; + pos--; + } + while (plen+len > l->cols) { + len--; + } + + abInit(&ab); + /* Cursor to left edge */ + snprintf(seq,64,"\x1b[0G"); + abAppend(&ab,seq,strlen(seq)); + /* Write the prompt and the current buffer content */ + abAppend(&ab,l->prompt,strlen(l->prompt)); + abAppend(&ab,buf,len); + /* Erase to right */ + snprintf(seq,64,"\x1b[0K"); + abAppend(&ab,seq,strlen(seq)); + /* Move cursor to original position. */ + snprintf(seq,64,"\x1b[0G\x1b[%dC", (int)(pos+plen)); + abAppend(&ab,seq,strlen(seq)); + if (write(fd,ab.b,ab.len) == -1) {} /* Can't recover from write error. */ + abFree(&ab); +} + +/* Multi line low level line refresh. + * + * Rewrite the currently edited line accordingly to the buffer content, + * cursor position, and number of columns of the terminal. */ +static void refreshMultiLine(struct linenoiseState *l) { + char seq[64]; + int plen = strlen(l->prompt); + int rows = (plen+l->len+l->cols-1)/l->cols; /* rows used by current buf. */ + int rpos = (plen+l->oldpos+l->cols)/l->cols; /* cursor relative row. */ + int rpos2; /* rpos after refresh. */ + int old_rows = l->maxrows; + int fd = l->ofd, j; + struct abuf ab; + + /* Update maxrows if needed. */ + if (rows > (int)l->maxrows) l->maxrows = rows; + + /* First step: clear all the lines used before. To do so start by + * going to the last row. */ + abInit(&ab); + if (old_rows-rpos > 0) { + lndebug("go down %d", old_rows-rpos); + snprintf(seq,64,"\x1b[%dB", old_rows-rpos); + abAppend(&ab,seq,strlen(seq)); + } + + /* Now for every row clear it, go up. */ + for (j = 0; j < old_rows-1; j++) { + lndebug("clear+up"); + snprintf(seq,64,"\x1b[0G\x1b[0K\x1b[1A"); + abAppend(&ab,seq,strlen(seq)); + } + + /* Clean the top line. */ + lndebug("clear"); + snprintf(seq,64,"\x1b[0G\x1b[0K"); + abAppend(&ab,seq,strlen(seq)); + + /* Write the prompt and the current buffer content */ + abAppend(&ab,l->prompt,strlen(l->prompt)); + abAppend(&ab,l->buf,l->len); + + /* If we are at the very end of the screen with our prompt, we need to + * emit a newline and move the prompt to the first column. */ + if (l->pos && + l->pos == l->len && + (l->pos+plen) % l->cols == 0) + { + lndebug(""); + abAppend(&ab,"\n",1); + snprintf(seq,64,"\x1b[0G"); + abAppend(&ab,seq,strlen(seq)); + rows++; + if (rows > (int)l->maxrows) l->maxrows = rows; + } + + /* Move cursor to right position. */ + rpos2 = (plen+l->pos+l->cols)/l->cols; /* current cursor relative row. */ + lndebug("rpos2 %d", rpos2); + + /* Go up till we reach the expected positon. */ + if (rows-rpos2 > 0) { + lndebug("go-up %d", rows-rpos2); + snprintf(seq,64,"\x1b[%dA", rows-rpos2); + abAppend(&ab,seq,strlen(seq)); + } + + /* Set column. */ + lndebug("set col %d", 1+((plen+(int)l->pos) % (int)l->cols)); + snprintf(seq,64,"\x1b[%dG", 1+((plen+(int)l->pos) % (int)l->cols)); + abAppend(&ab,seq,strlen(seq)); + + lndebug("\n"); + l->oldpos = l->pos; + + if (write(fd,ab.b,ab.len) == -1) {} /* Can't recover from write error. */ + abFree(&ab); +} + +/* Calls the two low level functions refreshSingleLine() or + * refreshMultiLine() according to the selected mode. */ +static void refreshLine(struct linenoiseState *l) { + if (mlmode) + refreshMultiLine(l); + else + refreshSingleLine(l); +} + +/* Insert the character 'c' at cursor current position. + * + * On error writing to the terminal -1 is returned, otherwise 0. */ +int linenoiseEditInsert(struct linenoiseState *l, char c) { + if (l->len < l->buflen) { + if (l->len == l->pos) { + l->buf[l->pos] = c; + l->pos++; + l->len++; + l->buf[l->len] = '\0'; + if ((!mlmode && l->plen+l->len < l->cols) /* || mlmode */) { + /* Avoid a full update of the line in the + * trivial case. */ + if (write(l->ofd,&c,1) == -1) return -1; + } else { + refreshLine(l); + } + } else { + memmove(l->buf+l->pos+1,l->buf+l->pos,l->len-l->pos); + l->buf[l->pos] = c; + l->len++; + l->pos++; + l->buf[l->len] = '\0'; + refreshLine(l); + } + } + return 0; +} + +/* Move cursor on the left. */ +void linenoiseEditMoveLeft(struct linenoiseState *l) { + if (l->pos > 0) { + l->pos--; + refreshLine(l); + } +} + +/* Move cursor on the right. */ +void linenoiseEditMoveRight(struct linenoiseState *l) { + if (l->pos != l->len) { + l->pos++; + refreshLine(l); + } +} + +/* Move cursor to the start of the line. */ +void linenoiseEditMoveHome(struct linenoiseState *l) { + if (l->pos != 0) { + l->pos = 0; + refreshLine(l); + } +} + +/* Move cursor to the end of the line. */ +void linenoiseEditMoveEnd(struct linenoiseState *l) { + if (l->pos != l->len) { + l->pos = l->len; + refreshLine(l); + } +} + +/* Substitute the currently edited line with the next or previous history + * entry as specified by 'dir'. */ +#define LINENOISE_HISTORY_NEXT 0 +#define LINENOISE_HISTORY_PREV 1 +void linenoiseEditHistoryNext(struct linenoiseState *l, int dir) { + if (history_len > 1) { + /* Update the current history entry before to + * overwrite it with the next one. */ + free(history[history_len - 1 - l->history_index]); + history[history_len - 1 - l->history_index] = strdup(l->buf); + /* Show the new entry */ + l->history_index += (dir == LINENOISE_HISTORY_PREV) ? 1 : -1; + if (l->history_index < 0) { + l->history_index = 0; + return; + } else if (l->history_index >= history_len) { + l->history_index = history_len-1; + return; + } + strncpy(l->buf,history[history_len - 1 - l->history_index],l->buflen); + l->buf[l->buflen-1] = '\0'; + l->len = l->pos = strlen(l->buf); + refreshLine(l); + } +} + +/* Delete the character at the right of the cursor without altering the cursor + * position. Basically this is what happens with the "Delete" keyboard key. */ +void linenoiseEditDelete(struct linenoiseState *l) { + if (l->len > 0 && l->pos < l->len) { + memmove(l->buf+l->pos,l->buf+l->pos+1,l->len-l->pos-1); + l->len--; + l->buf[l->len] = '\0'; + refreshLine(l); + } +} + +/* Backspace implementation. */ +void linenoiseEditBackspace(struct linenoiseState *l) { + if (l->pos > 0 && l->len > 0) { + memmove(l->buf+l->pos-1,l->buf+l->pos,l->len-l->pos); + l->pos--; + l->len--; + l->buf[l->len] = '\0'; + refreshLine(l); + } +} + +/* Delete the previosu word, maintaining the cursor at the start of the + * current word. */ +void linenoiseEditDeletePrevWord(struct linenoiseState *l) { + size_t old_pos = l->pos; + size_t diff; + + while (l->pos > 0 && l->buf[l->pos-1] == ' ') + l->pos--; + while (l->pos > 0 && l->buf[l->pos-1] != ' ') + l->pos--; + diff = old_pos - l->pos; + memmove(l->buf+l->pos,l->buf+old_pos,l->len-old_pos+1); + l->len -= diff; + refreshLine(l); +} + +/* This function is the core of the line editing capability of linenoise. + * It expects 'fd' to be already in "raw mode" so that every key pressed + * will be returned ASAP to read(). + * + * The resulting string is put into 'buf' when the user type enter, or + * when ctrl+d is typed. + * + * The function returns the length of the current buffer. */ +static int linenoiseEdit(int stdin_fd, int stdout_fd, char *buf, size_t buflen, const char *prompt) +{ + struct linenoiseState l; + + /* Populate the linenoise state that we pass to functions implementing + * specific editing functionalities. */ + l.ifd = stdin_fd; + l.ofd = stdout_fd; + l.buf = buf; + l.buflen = buflen; + l.prompt = prompt; + l.plen = strlen(prompt); + l.oldpos = l.pos = 0; + l.len = 0; + l.cols = getColumns(stdin_fd, stdout_fd); + l.maxrows = 0; + l.history_index = 0; + + /* Buffer starts empty. */ + l.buf[0] = '\0'; + l.buflen--; /* Make sure there is always space for the nulterm */ + + /* The latest history entry is always our current buffer, that + * initially is just an empty string. */ + linenoiseHistoryAdd(""); + + if (write(l.ofd,prompt,l.plen) == -1) return -1; + while(1) { + char c; + int nread; + char seq[3]; + + nread = read(l.ifd,&c,1); + if (nread <= 0) return l.len; + + /* Only autocomplete when the callback is set. It returns < 0 when + * there was an error reading from fd. Otherwise it will return the + * character that should be handled next. */ + if (c == 9 && completionCallback != NULL) { + c = completeLine(&l); + /* Return on errors */ + if (c < 0) return l.len; + /* Read next character when 0 */ + if (c == 0) continue; + } + + switch(c) { + case ENTER: /* enter */ + history_len--; + free(history[history_len]); + return (int)l.len; + case CTRL_C: /* ctrl-c */ + errno = EAGAIN; + return -1; + case BACKSPACE: /* backspace */ + case 8: /* ctrl-h */ + linenoiseEditBackspace(&l); + break; + case CTRL_D: /* ctrl-d, remove char at right of cursor, or of the + line is empty, act as end-of-file. */ + if (l.len > 0) { + linenoiseEditDelete(&l); + } else { + history_len--; + free(history[history_len]); + return -1; + } + break; + case CTRL_T: /* ctrl-t, swaps current character with previous. */ + if (l.pos > 0 && l.pos < l.len) { + int aux = buf[l.pos-1]; + buf[l.pos-1] = buf[l.pos]; + buf[l.pos] = aux; + if (l.pos != l.len-1) l.pos++; + refreshLine(&l); + } + break; + case CTRL_B: /* ctrl-b */ + linenoiseEditMoveLeft(&l); + break; + case CTRL_F: /* ctrl-f */ + linenoiseEditMoveRight(&l); + break; + case CTRL_P: /* ctrl-p */ + linenoiseEditHistoryNext(&l, LINENOISE_HISTORY_PREV); + break; + case CTRL_N: /* ctrl-n */ + linenoiseEditHistoryNext(&l, LINENOISE_HISTORY_NEXT); + break; + case ESC: /* escape sequence */ + /* Read the next two bytes representing the escape sequence. + * Use two calls to handle slow terminals returning the two + * chars at different times. */ + if (read(l.ifd,seq,1) == -1) break; + if (read(l.ifd,seq+1,1) == -1) break; + + /* ESC [ sequences. */ + if (seq[0] == '[') { + if (seq[1] >= '0' && seq[1] <= '9') { + /* Extended escape, read additional byte. */ + if (read(l.ifd,seq+2,1) == -1) break; + if (seq[2] == '~') { + switch(seq[1]) { + case '3': /* Delete key. */ + linenoiseEditDelete(&l); + break; + } + } + } else { + switch(seq[1]) { + case 'A': /* Up */ + linenoiseEditHistoryNext(&l, LINENOISE_HISTORY_PREV); + break; + case 'B': /* Down */ + linenoiseEditHistoryNext(&l, LINENOISE_HISTORY_NEXT); + break; + case 'C': /* Right */ + linenoiseEditMoveRight(&l); + break; + case 'D': /* Left */ + linenoiseEditMoveLeft(&l); + break; + case 'H': /* Home */ + linenoiseEditMoveHome(&l); + break; + case 'F': /* End*/ + linenoiseEditMoveEnd(&l); + break; + } + } + } + + /* ESC O sequences. */ + else if (seq[0] == 'O') { + switch(seq[1]) { + case 'H': /* Home */ + linenoiseEditMoveHome(&l); + break; + case 'F': /* End*/ + linenoiseEditMoveEnd(&l); + break; + } + } + break; + default: + if (linenoiseEditInsert(&l,c)) return -1; + break; + case CTRL_U: /* Ctrl+u, delete the whole line. */ + buf[0] = '\0'; + l.pos = l.len = 0; + refreshLine(&l); + break; + case CTRL_K: /* Ctrl+k, delete from current to end of line. */ + buf[l.pos] = '\0'; + l.len = l.pos; + refreshLine(&l); + break; + case CTRL_A: /* Ctrl+a, go to the start of the line */ + linenoiseEditMoveHome(&l); + break; + case CTRL_E: /* ctrl+e, go to the end of the line */ + linenoiseEditMoveEnd(&l); + break; + case CTRL_L: /* ctrl+l, clear screen */ + linenoiseClearScreen(); + refreshLine(&l); + break; + case CTRL_W: /* ctrl+w, delete previous word */ + linenoiseEditDeletePrevWord(&l); + break; + } + } + return l.len; +} + +/* This special mode is used by linenoise in order to print scan codes + * on screen for debugging / development purposes. It is implemented + * by the linenoise_example program using the --keycodes option. */ +void linenoisePrintKeyCodes(void) { + char quit[4]; + + printf("Linenoise key codes debugging mode.\n" + "Press keys to see scan codes. Type 'quit' at any time to exit.\n"); + if (enableRawMode(STDIN_FILENO) == -1) return; + memset(quit,' ',4); + while(1) { + char c; + int nread; + + nread = read(STDIN_FILENO,&c,1); + if (nread <= 0) continue; + memmove(quit,quit+1,sizeof(quit)-1); /* shift string to left. */ + quit[sizeof(quit)-1] = c; /* Insert current char on the right. */ + if (memcmp(quit,"quit",sizeof(quit)) == 0) break; + + printf("'%c' %02x (%d) (type quit to exit)\n", + isprint(c) ? c : '?', (int)c, (int)c); + printf("\x1b[0G"); /* Go left edge manually, we are in raw mode. */ + fflush(stdout); + } + disableRawMode(STDIN_FILENO); +} + +/* This function calls the line editing function linenoiseEdit() using + * the STDIN file descriptor set in raw mode. */ +static int linenoiseRaw(char *buf, size_t buflen, const char *prompt) { + int count; + + if (buflen == 0) { + errno = EINVAL; + return -1; + } + if (!isatty(STDIN_FILENO)) { + /* Not a tty: read from file / pipe. */ + if (fgets(buf, buflen, stdin) == NULL) return -1; + count = strlen(buf); + if (count && buf[count-1] == '\n') { + count--; + buf[count] = '\0'; + } + } else { + /* Interactive editing. */ + if (enableRawMode(STDIN_FILENO) == -1) return -1; + count = linenoiseEdit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt); + disableRawMode(STDIN_FILENO); + printf("\n"); + } + return count; +} + +/* The high level function that is the main API of the linenoise library. + * This function checks if the terminal has basic capabilities, just checking + * for a blacklist of stupid terminals, and later either calls the line + * editing function or uses dummy fgets() so that you will be able to type + * something even in the most desperate of the conditions. */ +char *linenoise(const char *prompt) { + char buf[LINENOISE_MAX_LINE]; + int count; + + if (isUnsupportedTerm()) { + size_t len; + + printf("%s",prompt); + fflush(stdout); + if (fgets(buf,LINENOISE_MAX_LINE,stdin) == NULL) return NULL; + len = strlen(buf); + while(len && (buf[len-1] == '\n' || buf[len-1] == '\r')) { + len--; + buf[len] = '\0'; + } + return strdup(buf); + } else { + count = linenoiseRaw(buf,LINENOISE_MAX_LINE,prompt); + if (count == -1) return NULL; + return strdup(buf); + } +} + +/* ================================ History ================================= */ + +/* Free the history, but does not reset it. Only used when we have to + * exit() to avoid memory leaks are reported by valgrind & co. */ +static void freeHistory(void) { + if (history) { + int j; + + for (j = 0; j < history_len; j++) + free(history[j]); + free(history); + } +} + +/* At exit we'll try to fix the terminal to the initial conditions. */ +static void linenoiseAtExit(void) { + disableRawMode(STDIN_FILENO); + freeHistory(); +} + +/* This is the API call to add a new entry in the linenoise history. + * It uses a fixed array of char pointers that are shifted (memmoved) + * when the history max length is reached in order to remove the older + * entry and make room for the new one, so it is not exactly suitable for huge + * histories, but will work well for a few hundred of entries. + * + * Using a circular buffer is smarter, but a bit more complex to handle. */ +int linenoiseHistoryAdd(const char *line) { + char *linecopy; + + if (history_max_len == 0) return 0; + + /* Initialization on first call. */ + if (history == NULL) { + history = malloc(sizeof(char*)*history_max_len); + if (history == NULL) return 0; + memset(history,0,(sizeof(char*)*history_max_len)); + } + + /* Don't add duplicated lines. */ + if (history_len && !strcmp(history[history_len-1], line)) return 0; + + /* Add an heap allocated copy of the line in the history. + * If we reached the max length, remove the older line. */ + linecopy = strdup(line); + if (!linecopy) return 0; + if (history_len == history_max_len) { + free(history[0]); + memmove(history,history+1,sizeof(char*)*(history_max_len-1)); + history_len--; + } + history[history_len] = linecopy; + history_len++; + return 1; +} + +/* Set the maximum length for the history. This function can be called even + * if there is already some history, the function will make sure to retain + * just the latest 'len' elements if the new history length value is smaller + * than the amount of items already inside the history. */ +int linenoiseHistorySetMaxLen(int len) { + char **new; + + if (len < 1) return 0; + if (history) { + int tocopy = history_len; + + new = malloc(sizeof(char*)*len); + if (new == NULL) return 0; + + /* If we can't copy everything, free the elements we'll not use. */ + if (len < tocopy) { + int j; + + for (j = 0; j < tocopy-len; j++) free(history[j]); + tocopy = len; + } + memset(new,0,sizeof(char*)*len); + memcpy(new,history+(history_len-tocopy), sizeof(char*)*tocopy); + free(history); + history = new; + } + history_max_len = len; + if (history_len > history_max_len) + history_len = history_max_len; + return 1; +} + +/* Save the history in the specified file. On success 0 is returned + * otherwise -1 is returned. */ +int linenoiseHistorySave(const char *filename) { + FILE *fp = fopen(filename,"w"); + int j; + + if (fp == NULL) return -1; + for (j = 0; j < history_len; j++) + fprintf(fp,"%s\n",history[j]); + fclose(fp); + return 0; +} + +/* Load the history from the specified file. If the file does not exist + * zero is returned and no operation is performed. + * + * If the file exists and the operation succeeded 0 is returned, otherwise + * on error -1 is returned. */ +int linenoiseHistoryLoad(const char *filename) { + FILE *fp = fopen(filename,"r"); + char buf[LINENOISE_MAX_LINE]; + + if (fp == NULL) return -1; + + while (fgets(buf,LINENOISE_MAX_LINE,fp) != NULL) { + char *p; + + p = strchr(buf,'\r'); + if (!p) p = strchr(buf,'\n'); + if (p) *p = '\0'; + linenoiseHistoryAdd(buf); + } + fclose(fp); + return 0; +} diff --git a/linenoise.h b/linenoise.h new file mode 100644 index 0000000..e22ebd3 --- /dev/null +++ b/linenoise.h @@ -0,0 +1,66 @@ +/* linenoise.h -- guerrilla line editing library against the idea that a + * line editing lib needs to be 20,000 lines of C code. + * + * See linenoise.c for more information. + * + * ------------------------------------------------------------------------ + * + * Copyright (c) 2010, Salvatore Sanfilippo + * Copyright (c) 2010, Pieter Noordhuis + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "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 COPYRIGHT + * HOLDER OR CONTRIBUTORS 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. + */ + +#ifndef __LINENOISE_H +#define __LINENOISE_H + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct linenoiseCompletions { + size_t len; + char **cvec; +} linenoiseCompletions; + +typedef void(linenoiseCompletionCallback)(const char *, linenoiseCompletions *); +void linenoiseSetCompletionCallback(linenoiseCompletionCallback *); +void linenoiseAddCompletion(linenoiseCompletions *, const char *); + +char *linenoise(const char *prompt); +int linenoiseHistoryAdd(const char *line); +int linenoiseHistorySetMaxLen(int len); +int linenoiseHistorySave(const char *filename); +int linenoiseHistoryLoad(const char *filename); +void linenoiseClearScreen(void); +void linenoiseSetMultiLine(int ml); +void linenoisePrintKeyCodes(void); + +#ifdef __cplusplus +} +#endif + +#endif /* __LINENOISE_H */ diff --git a/list.c b/list.c new file mode 100644 index 0000000..58510ac --- /dev/null +++ b/list.c @@ -0,0 +1,99 @@ +#include "list.h" + +#include +#include + +void list_init(struct list *list) +{ + memset(list, 0, sizeof(*list)); +} + +struct list *list_new(void *data) +{ + struct list *list = calloc(1, sizeof(*list)); + list->data = data; + return list; +} + +struct list *list_append(struct list *list, void *data) +{ + if (list == NULL) + { + return list_new(data); + } + + struct list *last = list_get_last(list); + list = list_new(data); + last->next = list; + + return list; +} + +struct list *list_get_last(struct list *list) +{ + while (list && list->next) + list = list->next; + return list; +} + +struct list *list_pop_front(struct list **list) +{ + struct list *popped = *list; + + if (!popped) + return NULL; + + *list = popped->next; + popped->next = NULL; + + return popped; +} + +void list_free(struct list *list, list_free_cb free_cb, void *userdata) +{ + struct list *popped; + + while ((popped = list_pop_front(&list)) != NULL) + { + if (free_cb) + free_cb(popped->data, userdata); + free(popped); + } +} + +#ifdef BUILD_TEST + +#include "test_util.h" + +TEST(list_init) +{ + +} + +TEST(list_new) +{ + +} + +TEST(list_append) +{ + +} + +TEST(list_get_last) +{ + +} + +TEST(list_pop_front) +{ + +} + +TEST(list_free) +{ + +} + + +#endif diff --git a/list.h b/list.h new file mode 100644 index 0000000..ea82440 --- /dev/null +++ b/list.h @@ -0,0 +1,19 @@ +#ifndef LIST_H +#define LIST_H + +struct list +{ + void *data; + struct list *next; +}; + +typedef void (*list_free_cb)(void *data, void *userdata); + +void list_init(struct list *list); +struct list *list_new(void *data); +struct list *list_append(struct list *list, void *data); +struct list *list_get_last(struct list *list); +struct list *list_pop_front(struct list **list); +void list_free(struct list *list, list_free_cb free_cb, void *userdata); + +#endif diff --git a/parse.c b/parse.c new file mode 100644 index 0000000..b5101e1 --- /dev/null +++ b/parse.c @@ -0,0 +1,184 @@ +#include "parse.h" +#include "tokens.h" +#include "list.h" +#include "atom.h" + +#include +#include +#include +#include + +void print_list(struct list *list, int level) +{ + while (list) + { + struct atom *atom = LIST_GET_ATOM(list); + + if (IS_TRUE(list)) + { + printf("#t"); + } + else if (IS_FALSE(list)) + { + printf("#f"); + } + else if (IS_NIL(list)) + { + printf("nil"); + } + else + { + switch (atom->type) + { + case ATOM_SYMBOL: + printf("%.*s", atom->str.len, atom->str.str); + break; + + case ATOM_LIST: + printf("("); + print_list(atom->list, level+1); + printf(")"); + break; + + case ATOM_STR: + printf("\"%.*s\"", atom->str.len, atom->str.str); + break; + + case ATOM_INT: + printf("%ld", atom->l); + } + } + + if (list->next) + printf(" "); + + list = list->next; + } + + if (level == 0) + printf("\n"); +} + +int parse_next(const char *src, int *pos, struct atom **result) +{ + struct token token; + int rc; + + if ((rc = get_next_token(src, pos, &token)) > 0) + { + switch (token.type) + { + case TOKEN_INT: + *result = atom_new_int(strtol(token.s, NULL, 10)); + break; + + case TOKEN_STR: + *result = atom_new_str(token.s, token.len); + break; + + case TOKEN_SYMBOL: + if (strncmp(token.s, "#t", 2) == 0) + *result = &true_atom; + else if (strncmp(token.s, "#f", 2) == 0) + *result = &false_atom; + else + *result = atom_new_sym(token.s, token.len); + break; + + case TOKEN_LPAREN: + { + struct list *l = parse(src, pos); + *result = atom_new_list(l); + break; + } + + case TOKEN_RPAREN: + return -2; + + case TOKEN_QUOTE: + { + struct atom *quoted = NULL; + + parse_next(src, pos, "ed); + + struct list *qlist = list_append(NULL, + atom_new_sym("quote", 5)); + + list_append(qlist, quoted); + + *result = atom_new_list(qlist); + + break; + } + } + } + + return rc; +} + +struct list *parse(const char *src, int *pos) +{ + int rc; + struct atom *atom; + struct list root, *last = &root; + + list_init(last); + + while ((rc = parse_next(src, pos, &atom))) + { + if (rc < 0) + break; + + last = list_append(last, atom); + } + + if (rc < 0 && rc != -2) + return NULL; + + return root.next; +} + +#ifdef BUILD_TEST + +#include "test_util.h" + +static const char *test_src_fact = + "(define fact\n" + " ;; Factorial function\n" + " (lambda (n)\n" + " (if (eq n 0)\n" + " 1 ; Factorial of 0 is 1\n" + " (* n (fact (- n 1))))))\n" + "(fact 5) ;; this should evaluate to 120\n"; + +#define ASSERT_SYM(LIST, SYM) \ + ASSERT_TRUE(IS_SYM(LIST)); \ + ASSERT_STREQ(SYM, LIST_GET_ATOM(LIST)->str.str) + +TEST(test_parse) +{ + int pos = 0; + struct list *list; + + list = parse(test_src_fact, &pos); + + ASSERT_TRUE(list != NULL); + + ASSERT_TRUE(IS_LIST(list)); + + list = LIST_GET_ATOM(list)->list; + + ASSERT_TRUE(list != NULL); + ASSERT_SYM(list, "define"); + + list = list->next; + + ASSERT_TRUE(list != NULL); + ASSERT_SYM(list, "fact"); + + list = list->next; + + ASSERT_TRUE(list != NULL); +} + +#endif diff --git a/parse.h b/parse.h new file mode 100644 index 0000000..94d6fa8 --- /dev/null +++ b/parse.h @@ -0,0 +1,12 @@ +#ifndef PARSER_H +#define PARSER_H + +struct atom; +struct list; + +int parse_next(const char *src, int *pos, struct atom **result); +struct list *parse(const char *src, int *pos); + +void print_list(struct list *list, int level); + +#endif diff --git a/repl.c b/repl.c new file mode 100644 index 0000000..c9ddb6a --- /dev/null +++ b/repl.c @@ -0,0 +1,27 @@ +#include +#include + +#include "parse.h" +#include "eval.h" +#include "list.h" +#include "linenoise.h" + +int main(int argc, char **argv) +{ + char *line; + + linenoiseSetMultiLine(0); + + while ((line = linenoise("> ")) != NULL) + { + linenoiseHistoryAdd(line); + + struct list *result = eval_str(line); + + print_list(result, 0); + + free(line); + } + + return 0; +} diff --git a/test_util.h b/test_util.h new file mode 100644 index 0000000..1ebf696 --- /dev/null +++ b/test_util.h @@ -0,0 +1,93 @@ +#ifndef TEST_UTIL_H +#define TEST_UTIL_H + +#include +#include +#include + +#ifdef _MSC_VER + +#define CCALL __cdecl +#pragma section(".CRT$XCU",read) +#define INITIALIZER(f) \ + static void __cdecl f(void); \ + __declspec(allocate(".CRT$XCU")) void (__cdecl*f##_)(void) = f; \ + static void __cdecl f(void) + +#elif defined(__GNUC__) + +#define CCALL +#define INITIALIZER(f) \ + static void f(void) __attribute__((constructor)); \ + static void f(void) + +#endif + +// __attribute__((constructor)) static void test_##NAME##_init() + +#define TEST(NAME) \ + static void test_##NAME(); \ + void test_util_add_test(const char *name, void (*func)()); \ + INITIALIZER(test_##NAME##_init) \ + { \ + test_util_add_test(#NAME, &test_##NAME); \ + } \ + static void test_##NAME() + +#define TEST_MAIN() \ + typedef void (*test_func)(); \ + struct test_def { \ + const char *name; \ + test_func func; \ + struct test_def *next; \ + }; \ + static struct test_def test_defs; \ + void test_util_add_test(const char *name, void (*func)()) \ + { \ + struct test_def *def = calloc(1, sizeof(*def)); \ + struct test_def *last = &test_defs; \ + while (last && last->next) last = last->next; \ + last->next = def; \ + def->name = strdup(name); \ + def->func = func; \ + } \ + int main() \ + { \ + struct test_def *def = test_defs.next; \ + while (def) \ + { \ + printf("running test %s\n", def->name); \ + def->func(); \ + def = def->next; \ + } \ + return 0; \ + } + +#define ASSERT(X) \ + do { \ + if (!(X)) { \ + fprintf(stderr, "assertion %s failed at %s:%d\n", \ + #X, __FILE__, __LINE__); \ + exit(1); \ + } \ + } while (0) + +#define ASSERT_MSG(X, FMT, ...) \ + do { \ + if (!(X)) { \ + fprintf(stderr, "assertion %s failed at %s:%d (" FMT ")\n", \ + #X, __FILE__, __LINE__, ##__VA_ARGS__); \ + exit(1); \ + } \ + } while (0) + +#define ASSERT_TRUE(X) ASSERT(X) +#define ASSERT_FALSE(X) ASSERT(!(X)) + +#define ASSERT_EQ(EXPECTED, ACTUAL) ASSERT(((EXPECTED) == (ACTUAL))) +#define ASSERT_NEQ(EXPECTED, ACTUAL) ASSERT(((EXPECTED) != (ACTUAL))) + +#define ASSERT_STREQ(EXPECTED, ACTUAL) ASSERT(strcmp((EXPECTED), (ACTUAL)) == 0) +#define ASSERT_STREQ_N(EXPECTED, ACTUAL, N) ASSERT(strncmp((EXPECTED), (ACTUAL), (N)) == 0) + +#endif diff --git a/tokens.c b/tokens.c new file mode 100644 index 0000000..d249393 --- /dev/null +++ b/tokens.c @@ -0,0 +1,188 @@ +#include "tokens.h" + +#include + +int get_next_token(const char *src, int *pos, struct token *token) +{ + char c; + +start: + + while (isspace(src[*pos])) + { + *pos += 1; + } + + c = src[*pos]; + + if (!c) + return 0; + + if (c == ';') + { + *pos += 1; + while (src[*pos] != '\n') + { + *pos += 1; + } + + goto start; + } + + if (c == '(') + { + token->type = TOKEN_LPAREN; + token->s = &src[*pos]; + token->len = 1; + *pos += 1; + } + else if (c == ')') + { + token->type = TOKEN_RPAREN; + token->s = &src[*pos]; + token->len = 1; + *pos += 1; + } + else if (c == '.') + { + token->type = TOKEN_PERIOD; + token->s = &src[*pos]; + token->len = 1; + *pos += 1; + } + else if (c == '\'') + { + token->type = TOKEN_QUOTE; + token->s = &src[*pos]; + token->len = 1; + *pos += 1; + } + else if (isdigit(c)) + { + token->type = TOKEN_INT; + token->s = &src[*pos]; + + while (!isspace(src[*pos])) + { + if (isdigit(src[*pos])) + { + *pos += 1; + } + else + { + c = src[*pos]; + + if (c == '(' || c == ')') + { + break; + } + + return -1; + } + } + + token->len = &src[*pos] - token->s; + } + else if (c == '"') + { + *pos += 1; + token->type = TOKEN_STR; + token->s = &src[*pos]; + + while (src[*pos] != '"') + { + *pos += 1; + } + + token->len = &src[*pos] - token->s; + + *pos += 1; + } + else if (isalnum(c) || ispunct(c)) + { + token->type = TOKEN_SYMBOL; + token->s = &src[*pos]; + *pos += 1; + + while ((isalnum(src[*pos]) || ispunct(src[*pos])) && src[*pos] != '(' && src[*pos] != ')') + { + *pos += 1; + } + + token->len = &src[*pos] - token->s; + } + else + { + return -1; + } + + return 1; +} + +#ifdef BUILD_TEST + +#include "test_util.h" + +static const char *test_src_fact = + "(define fact\n" + " ;; Factorial function\n" + " (lambda (n)\n" + " (if (eq n 0)\n" + " 1 ; Factorial of 0 is 1\n" + " (* n (fact (- n 1))))))\n" + "(fact 5) ;; this should evaluate to 120\n"; + +TEST(test_get_next_token) +{ + int pos = 0; + + struct token token; + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_LPAREN, token.type); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_SYMBOL, token.type); + ASSERT_STREQ_N("define", token.s, 6); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_SYMBOL, token.type); + ASSERT_STREQ_N("fact", token.s, 4); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_LPAREN, token.type); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_SYMBOL, token.type); + ASSERT_STREQ_N("lambda", token.s, 6); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_LPAREN, token.type); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_SYMBOL, token.type); + ASSERT_STREQ_N("n", token.s, 1); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_RPAREN, token.type); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_INT, token.type); + ASSERT_STREQ_N("0", token.s, 1); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + + ASSERT_EQ(1, get_next_token(test_src_fact, &pos, &token)); + ASSERT_EQ(TOKEN_SYMBOL, token.type); + ASSERT_STREQ_N("*", token.s, 1); +} + +#endif /* BUILD_TEST */ diff --git a/tokens.h b/tokens.h new file mode 100644 index 0000000..8b06454 --- /dev/null +++ b/tokens.h @@ -0,0 +1,24 @@ +#ifndef TOKENS_H +#define TOKENS_H + +enum +{ + TOKEN_INT, + TOKEN_STR, + TOKEN_SYMBOL, + TOKEN_LPAREN, + TOKEN_RPAREN, + TOKEN_PERIOD, + TOKEN_QUOTE +}; + +struct token +{ + const char *s; + int len; + int type; +}; + +int get_next_token(const char *src, int *pos, struct token *token); + +#endif diff --git a/tst_main.c b/tst_main.c new file mode 100644 index 0000000..6e99cac --- /dev/null +++ b/tst_main.c @@ -0,0 +1,2 @@ +#include "test_util.h" +TEST_MAIN() -- cgit v1.2.3