Printing Expressions

[nohwnd]

Hello I am following the code in the book and in this chapter I am getting Segmentation fault: 11, I read on the internet that is caused by uninitialized access to data. I went through the code in the book few times and I can't spot the error. Could you check my code please? This is the output from LLDB:

nbook:repl nohwnd$ lldb ./program 
(lldb) target create "./program"
Current executable set to './program' (x86_64).
(lldb) run
Process 5671 launched: './program' (x86_64)
Lispy Version
Press Ctrl+C to exit

lispy> + 2 2
Process 5671 stopped
* thread #1: tid = 0x34b02, 0x0000000100001164 program`lval_add + 20, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x20)
    frame #0: 0x0000000100001164 program`lval_add + 20
program`lval_add + 20:
-> 0x100001164:  movl   0x20(%rsi), %eax
   0x100001167:  addl   $0x1, %eax
   0x10000116c:  movl   %eax, 0x20(%rsi)
   0x10000116f:  movq   -0x8(%rbp), %rsi

The problem is likely in lval_read where NULL is assigned to x pointer. If I change that line to lval* x = lval_sexpr(); the code works correctly.

This is my full code:

#include "mpc.h"

/* if we compile on windows compile these functions */
#ifdef _WIN32
  #include <string.h>

  static char buffer[2048];

  /* fake readline function */
  char* readline (char* prompt) {
    fputs(prompt, stdout);
    fgets(buffer, 2048, stdin);
    char* cpy = malloc(strlen(buffer)+1);
    strcpy(cpy, buffer);
    cpy[strlen(cpy)-1] = '\0';

    return cpy;
  }

  /*fake history function*/
  void add_history(char*) {}
#else
  /*compiling on mac */
  #include <editline/readline.h>
#endif

typedef struct lval {
  int type;
  long num;
  /* Errors and Symbols have some string data */
  char* err;
  char* sym;

  int count;
  struct lval** cell;
} lval;

/* Possible lval types */
enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR };

/* Possible error types */
enum { LERR_DIV_ZERO, LERR_BAD_OP, LERR_BAD_NUM };

/* Add lval as a child to SExpression */
lval* lval_add(lval* v, lval* x) {
  v->count++;
  v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  v->cell[v->count-1] = x;

  return v;
}

/* Create pointer to new Number lval */
lval* lval_num(long x) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_NUM;
  v->num = x;

  return v;
}

/* Create pointer to new Error val */
lval* lval_err(char* m) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_ERR;
  v->err = malloc(strlen(m) + 1);
  strcpy(v->err, m);

  return v;
}

/* Create pointer to new Symbol lval */
lval* lval_sym(char* s) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SYM;
  v->sym = malloc(strlen(s) + 1);
  strcpy(v->sym, s);

  return v;
}

/* Create pointer to new empty SExpression lval */
lval* lval_sexpr(void) {
  lval* v = malloc(sizeof(lval));
  v->type = LVAL_SEXPR;
  v->count = 0;
  v->cell = NULL;

  return v;
}
/* Delete the lval and all it linked fields */
void lval_del(lval* v) {
  switch(v->type) {
    /* Do nothing special for number type */
    case LVAL_NUM:
      break;
    case LVAL_ERR:
      free(v->err);
      break;
    case LVAL_SYM:
      free(v->sym);
      break;
    case LVAL_SEXPR:
      for (int i = 0;  i < v->count; i++) {
        lval_del(v->cell[i]);
      }
      /* Free the memory allocated to hold the pointers as well */
      free(v->cell);
      break;
  }

  free(v);
}

lval* lval_read_num(mpc_ast_t* t) {
  errno = 0;
  long x = strtol(t->contents, NULL, 10);
  return errno != ERANGE ? lval_num(x) : lval_err("Invalid number");
}

lval* lval_read(mpc_ast_t* t) {
  /* If Symbol or Number return conversion to that type */
  if (strstr(t->tag, "number")) { return lval_read_num(t);}
  if (strstr(t->tag, "symbol")) { return lval_sym(t->contents); }
  /* If root (>) or sexpr then create empty list */
  lval* x = NULL;
  //lval* x = lval_sexpr();
  if(strstr(t->tag, ">") == 0) { x = lval_sexpr(); }
  if(strstr(t->tag, "sexpr")) { x = lval_sexpr(); }

  /* Fill this list with any valid expression contained within */
  for ( int i = 0; i < t->children_num; i++) {
    if (strcmp(t->children[i]->contents, "(") == 0 ) { continue; }
    if (strcmp(t->children[i]->contents, ")") == 0 ) { continue; }
    if (strcmp(t->children[i]->contents, "}") == 0 ) { continue; }
    if (strcmp(t->children[i]->contents, "{") == 0 ) { continue; }
    if (strcmp(t->children[i]->tag, "regex") == 0 ) { continue; }

    x = lval_add(x, lval_read(t->children[i]));
  }

  return x;
}

/* Forward define funciton that has circular reference */
void lval_expr_print(lval* v, char open, char close);

/* Print an lval */
void lval_print(lval* v) {
  switch (v->type) {
    /* In case the type is a number print it */
    /* Then break out of the switch */
    case LVAL_NUM:
      printf ("%li", v->num);
      break;

    /* In case the type is error find what error
    it is and print it */
    case LVAL_ERR:
      printf("Error: %s", v->err);
      break;
    case LVAL_SYM:
      printf("%s", v->sym);
      break;
    case LVAL_SEXPR:
      lval_expr_print(v,'(', ')');
      break;
  }
}

void lval_println(lval* v) {
  /* Print lval followed by new line */
  lval_print(v);
  putchar('\n');
}

void lval_expr_print(lval* v, char open, char close) {
  putchar(open);
  for (int i = 0; i < v->count; i++) {
    lval_print(v->cell[i]);

    /* Don't print trailing space if this is the last element */
    if (i != (v->count-1)) {
      putchar(' ');
    }
  }
  putchar(close);
}

int main (int argc, char** argv) {
  /* Create some parsers */
  mpc_parser_t* Number        = mpc_new("number");
  mpc_parser_t* Symbol        = mpc_new("symbol");
  mpc_parser_t* SExpression   = mpc_new("sexpression");
  mpc_parser_t* Expression    = mpc_new("expression");
  mpc_parser_t* Lispy         = mpc_new("lispy");

  /* Define the with the following language */
  mpca_lang(MPCA_LANG_DEFAULT,
  "number: /-?[0-9]+/; \
  symbol: '+'|'-'|'*'|'/'; \
  sexpression: '(' <expression>* ')'; \
  expression: <number> | <symbol> | <sexpression>; \
  lispy: /^/ <expression>* /$/;",
  Number, Symbol, SExpression, Expression, Lispy);

  /*Print Version and Exit information*/
  printf("Lispy Version\n");
  puts("Press Ctrl+C to exit\n");

  mpc_result_t r;

  /*In neverending loop */
  while(1){
    /*output our prompt and get input*/
    char* input = readline("lispy> ");
    /*Add input to history*/
    add_history(input);

    if (mpc_parse("<stdin>", input, Lispy, &r))
    {
      lval* x = lval_read(r.output);
      lval_println(x);
      lval_del(x);
    }
    else{
      /*Ohterwise print the error */
      mpc_err_print(r.error);
      mpc_err_delete(r.error);
    }

    free(input);
  }

  /* Undefine and delete the parsers */
  mpc_cleanup(4, Number, Symbol, SExpression, Expression, Lispy);
  return 0;
}

[orangeduck]

Hi nohwd,

You're basically right in your assessment of the error. The function lval_add is getting the variable x when x is NULL. This is causing the segfault. But x shouldn't be NULL when it is passed to lval_add because of the following lines of code:

if (strcmp(t->tag, ">") == 0) { x = lval_sexpr(); } 
if (strstr(t->tag, "sexpr"))  { x = lval_sexpr(); }

So it looks like these two if statements are both failing, which means that the tag field is not the string ">" (strcmp(t->tag, ">") == 0) and that "sexpr" is not a substring of the tag field (strstr(t->tag, "sexpr")).

Why might this be?

Well if you print the AST using mpc_ast_print() you can probably find out. I've not checked but my guess is that you're s-expressions are not tagged with the string "sexpr", but are instead tagged with the string "sexpression", because this is the name of your rule in the mpc grammar. If you change the rule name to sexpr, or change the substring check to sexpression, I think it should work.

I hope that helps,

Dan

[nohwnd]

Thanks for the prompt answer. The actual error was that I was using strstr in both if instead of strcmp in the first if. Took me good couple of hours before asking for help and now it is solved in few minutes. :)

[orangeduck]

Glad you managed to fix it!