Why am I getting memory errors with valgrind? (C++, abstract syntax tree evaluation)

Question

I am currently doing an assignment for a course I'm doing. I have what seems to be a fully working program (I get the right output for all my test data), however when I run with valgrind it says that I have memory errors. Here is the minimal code to reproduce the error (which is still quite a bit sorry):

note: this assignment is about evaluating abstract syntax trees (not parsing, just evaluating)

header file: (provided by my tutor - I can't change this)

struct env {
  //will be used to store the values of variables in a stack. This is one 'node' of the stack
  string var;
  int value;
  env *next;
};

class Exp {
  //general expression - eval will be overridden.
 public:
  virtual int eval(env*) = 0;
};

class Constant : public Exp {
  int n;
 public:
  Constant(int n) {this->n = n; }
  int eval(env*);
};

class Var : public Exp {
  string name;
 public:
  Var(string s) { this->name = s; }
  int eval(env*);
};

class Let : public Exp {
  //let binding. (let bvar = bexp in body)
  //used to assign a value to variables
  string bvar;
  Exp *bexp;
  Exp *body;
 public:
  Let(string v, Exp *e, Exp *b)
    {
      bvar = v; bexp = e; body = b;
    }
  int eval(env*);
};

This is the code that I have written to evaluate this subset of the syntax:

#include <string>
using namespace std;
#include "evalobj2.h"

int Constant::eval(env *env) {
  return this->n;
}

int Var::eval(env *env) {
  while(env) {
    if ((env->var).compare(this->name) == 0) return env->value;
    env = env->next;
  }
  //give up - variable not found in env
  throw 1;
}

int Let::eval(env *env) {
  //make a new struct env to be pushed to the environment stack
  struct env* newEnv = (struct env*)malloc(sizeof(struct env));

  //copy data into new env struct
  newEnv->var = this->bvar;
  newEnv->value = this->bexp->eval(env);

  //make it the head of the "environment" so that it is seen first when looking up a value
  newEnv->next = env; 

  //evaluate
  int valToReturn = this->body->eval(newEnv);
  free(newEnv);

  return valToReturn;
}

When I run the following from a main method I get "6 errors from 6 contexts" from valgrind:

Exp *e = new Let("x",new Constant(1),new Var("x"));
cout << e2->eval(nullptr) << endl;

Even though I get the right result. I have tested on bigger data structures with the rest of the syntax that I have to evaluate, all of which give correct results.

I don't understand what Valgrind is complaining about! It says "Conditional jump or move depends on uninitialised values" at "operator delete(void*)" .... by some other stuff that isn't mine... by Let::eval(env*) ... which is mine.

I will get 0 marks for a program with memory errors.

In addition to using malloc instead of new[], your Exp class requires a virtual destructor. If you attempted to deallocate the memory here using Exp *e = new Let(...) ... delete e; -- the behavior is undefined. — PaulMcKenzie
header file: (provided by my tutor - I can't change this) -- Your tutor needs a tutor. If you're supposed to dynamically create objects derived from Exp using a base class pointer, and (as should be required), deallocate the memory, your tutor's header file has a serious problem, as it cannot be done without introducing undefined behavior, with more than likely, that undefined behavior is a memory leak. The reason is mentioned in my first comment above. A grade of F for your tutor. — PaulMcKenzie

Sam Varshavchik Sam Varshavchik · Accepted Answer · 2017-03-05T19:48:29

struct env {
  //will be used to store the values of variables in a stack. This is one 'node' of the stack
  string var;
  int value;
  env *next;
};

// ...

struct env* newEnv = (struct env*)malloc(sizeof(struct env));

You are allocating env, a structure with C++ classes, namely a std::string, using the C library's malloc(), which knows absolutely nothing about C++ classes.

This is undefined behavior. C++ classes must be allocated and destroyed with new and delete. It's surprising that your code survives long enough to produce any results, instead of crashing and burning, right from the get-go.

Why am I getting memory errors with valgrind? (C++, abstract syntax tree evaluation)

2 Answers