Operator overloading and mysterious object dereferencing?

[botevmg]

I'll just post the code as otherwise it will take me far too long to explain (which I won't be that good at anyway). Note that if you want to reproduce it all you need is to have Eigen installed.

This is the main header with three classes, in summary ADNodeInstance is a data holder, ADNode is encapsulating a pointer to ADNodeInstance, and ADGraphBuilder is a main class which holds all the ADNodeInstances and manages them.:

#ifndef ADVIBE_STACK_H
#define ADVIBE_STACK_H

#include "memory"
#include "iostream"
#include "fstream"
#include "Eigen/Dense"

typedef Eigen::MatrixXd Matrix;

enum class OPERATOR {
    NONE,
    ADD,
    UNNARY_NEGATION,
    MULTIPLY,
    DOT_MULTIPLY, // Linear algebra
    VERTICAL_CONCATENATION,
    TRANSPOSE,
    SUBINDEX,
    TANH
};


enum TYPE{
    CONSTANT,
    INPUT,
    INPUT_DERIVED,
    GRADIENT
};


/**
 * Main graph classes
 */

class ADNodeInstance {
public:
    TYPE type;
    int id;
    OPERATOR op;
    int dim1, dim2;
    std::string name;
    Matrix value;
    std::vector<std::weak_ptr<ADNodeInstance>> parents;
    std::vector<std::weak_ptr<ADNodeInstance>> children;

    ADNodeInstance(TYPE type, int id, OPERATOR op, int dim1, int dim2, std::string name) :
            type(type), id(id), op(op), dim1(dim1), dim2(dim2), name(name) { };

    ADNodeInstance(TYPE type, int id, OPERATOR op, const Matrix value) :
            type(type), id(id), op(op), dim1(value.rows()), dim2(value.cols()), value(value) { };

    ADNodeInstance(TYPE type, int id, OPERATOR op, int dim1, int dim2) :
            type(type), id(id), op(op), dim1(dim1), dim2(dim2) { }

    ~ADNodeInstance() { };
};

class ADGraphBuilder;

class ADNode{
public:
    ADGraphBuilder* builder;
    std::shared_ptr<ADNodeInstance> pointer;
    ADNode(){};
    ADNode(ADGraphBuilder* builder):
            builder(builder){};
    ADNode(const ADNode& node):
            builder(node.builder), pointer(node.pointer){};
    ~ADNode() {};// std::cout << "Destroying " << pointer->id << " " << pointer.use_count() << std::endl;};

    inline ADNode getVariable(OPERATOR op, const int dim1, const int dim2) const;

    inline ADNode apply(OPERATOR op) const{
        ADNode result = getVariable(op, this->pointer->dim1, this->pointer->dim2);
        result.pointer->parents.push_back(pointer);
        pointer->children.push_back(result.pointer);
        return result;
    };

    inline ADNode tanh() const{
        return apply(OPERATOR::TANH);
    }

    inline ADNode transpose() const{
        ADNode result = getVariable(OPERATOR::TRANSPOSE, this->pointer->dim2, this->pointer->dim1);
        result.pointer->parents.push_back(pointer);
        pointer->children.push_back(result.pointer);
        return result;
    }

    inline ADNode  operator-() const{
        std::cout << pointer->id << " U " << std::endl;
        std::cout << "NEG: " << builder << " - " << pointer->id << std::endl;
        ADNode node = apply(OPERATOR::UNNARY_NEGATION);
        std::cout << "NEG2: " << builder << " - " << pointer->id << std::endl;
        std::cout << "NEGRES: " << node.pointer->id << std::endl;
        return node;
    };

    inline ADNode block(const int loc1, const int loc2, const int dim1, const int dim2) const {
        ADNode result = getVariable(OPERATOR::SUBINDEX, dim1, dim2);
        result.pointer->parents.push_back(pointer);
        pointer->children.push_back(result.pointer);
        return result;
    }
};



class ADGraphBuilder{
protected:
    int counter;
public:
    std::vector<ADNode> nodes;
    ADGraphBuilder():
            counter(0){};
    ~ADGraphBuilder(){};

    std::vector<ADNode> gradient(const ADNode& target, const ADNode& param);
    ADNode createGradientMessage(const ADNode& child, const ADNode& parent, const ADNode& directGradient);

    inline ADNode createInternalVariable(const TYPE type, const OPERATOR op, const int dim1, const int dim2) {
        ADNode result = ADNode(this);
        result.pointer = std::make_shared<ADNodeInstance>(type, counter++, op, dim1, dim2);
        nodes.push_back(result);
        return result;
    }

    inline ADNode createInternalVariable(const TYPE type, const OPERATOR op, const int dim1, const int dim2, const std::string name) {
        ADNode result = ADNode(this);
        result.pointer = std::make_shared<ADNodeInstance>(type, counter++, op, dim1, dim2, name);
        nodes.push_back(result);
        return result;
    }

    inline ADNode createConstantVariable(const Matrix value){
        ADNode result = ADNode(this);
        result.pointer = std::make_shared<ADNodeInstance>(TYPE::CONSTANT, counter++, OPERATOR::NONE , value);
        nodes.push_back(result);
        return result;
    }

    inline ADNode createVariable(const int dim1, const int dim2){
        ADNode result = ADNode(this);
        result.pointer = std::make_shared<ADNodeInstance>(TYPE::INPUT, counter++, OPERATOR::NONE , dim1, dim2);
        nodes.push_back(result);
        return result;
    }

};

inline ADNode ADNode::getVariable(OPERATOR op, const int dim1, const int dim2) const{
    if(this->pointer->type == GRADIENT)
        return builder->createInternalVariable(GRADIENT, op, dim1, dim2);
    else
        return builder->createInternalVariable(INPUT_DERIVED, op, dim1, dim2);
}

/**
 * Concatenation
 */

inline ADNode vertCat(const ADNode& lhs, const ADNode& rhs) {
    if (lhs.builder != rhs.builder) {
        std::cerr << "Can not operate with notes from different builder instances!" << std::endl;
        throw 1;
    }
    if (lhs.pointer->dim2 != rhs.pointer->dim2) {
        std::cerr << "Can not perform vertical concatanation on nodes with different size in dimension 2." << std::endl;
        throw 2;
    }

    ADNode result = lhs.builder->createInternalVariable(INPUT_DERIVED, OPERATOR::VERTICAL_CONCATENATION,
                                                        lhs.pointer->dim1 + rhs.pointer->dim1, lhs.pointer->dim2);
    result.pointer->parents.push_back(lhs.pointer);
    result.pointer->parents.push_back(rhs.pointer);
    lhs.pointer->children.push_back(result.pointer);
    rhs.pointer->children.push_back(result.pointer);
    return result;
}

inline ADNode vertCat(const ADNode& lhs, const double rhs) {
    return vertCat(lhs, lhs.builder->createConstantVariable(Matrix::Constant(1,1, rhs)));
}

/**
 * Joining nodes
 */
ADNode joinNodes(const OPERATOR op, const ADNode& lhs, const ADNode& rhs){
    if(lhs.builder != rhs.builder){
        std::cerr << "Different builders " << std::endl;
        throw 5;
    }
    std::cout << "Joyning " << lhs.pointer->id << " and " << rhs.pointer->id  << std::endl;
    ADNode  result = lhs.builder->createInternalVariable(INPUT_DERIVED, op , 1, 1);
    result.pointer->parents.push_back(lhs.pointer);
    result.pointer->parents.push_back(rhs.pointer);
    lhs.pointer->children.push_back(result.pointer);
    rhs.pointer->children.push_back(result.pointer);
    return result;
}

inline ADNode dot(const ADNode& lhs, const ADNode& rhs){
    return joinNodes(OPERATOR::DOT_MULTIPLY, lhs, rhs);
}

inline ADNode tanh(const ADNode& lhs){
    return lhs.tanh();
}

inline ADNode operator*(const ADNode& lhs, const ADNode& rhs){
    std::cout << "MULT: " << lhs.pointer->id << " - " << rhs.builder << " - " << rhs.pointer->id << std::endl;
    ADNode node = joinNodes(OPERATOR::MULTIPLY, lhs, rhs);
    std::cout << "MULT2: " << lhs.pointer->id << " - " << rhs.builder << " - " << rhs.pointer->id << std::endl;
    std::cout << "MULTRES: " << node.pointer->id << std::endl;
    return node;
}

inline ADNode operator+(const ADNode& lhs, const ADNode& rhs){
    std::cout << "ADD: " << lhs.pointer->id << " - " <<  rhs.builder << " - " << rhs.pointer->id << std::endl;
    ADNode node = joinNodes(OPERATOR::ADD, lhs, rhs);
    std::cout << "ADD2: " << lhs.pointer->id << " - " << rhs.builder << " - " << rhs.pointer->id << std::endl;
    std::cout << "ADDRES: " << node.pointer->id << std::endl;
    return node;
}

inline ADNode operator-(const double lhs, const ADNode& rhs){
    return rhs.builder->createConstantVariable(Matrix::Constant(1,1,lhs)) + (-rhs);
}

inline int getIndex(const std::vector<std::weak_ptr<ADNodeInstance>> vector, const ADNode& target){
    for (int i = 0; i < vector.size(); ++i) {
        auto item = vector[i].lock();
        if (item->id == target.pointer->id)
            return i;
    }
    return -1;
}


std::vector<ADNode> ADGraphBuilder::gradient(const ADNode &target, const ADNode& params) {
    std::vector<ADNode> results{1, this};
    // Will contain information about the subtree that effects the target node
    bool subtree[nodes.size()];
    std::vector<std::vector<ADNode>> childrenGradients(nodes.size(), std::vector<ADNode>{});
    std::vector<ADNode> directGradients{nodes.size(), this};
    subtree[target.pointer->id] = true;
    for (int i = target.pointer->id; i >= 0; i--) {
        std::cout << "passed " << i << std::endl;
        if(subtree[i]){
            // Create a new gradient node summing up all incoming gradient messages
            if(i == target.pointer->id) {
                directGradients[i] = createConstantVariable(Matrix::Ones(target.pointer->dim1, target.pointer->dim2));
                directGradients[i].pointer->name = "Gradient[" + std::to_string(i) + "]";
            }
            else
                directGradients[i] = createInternalVariable(GRADIENT, OPERATOR::ADD,
                                                            nodes[i].pointer->dim1, nodes[i].pointer->dim2, std::to_string(i));
            for (auto child : childrenGradients[i]) {
                directGradients[i].pointer->parents.push_back(child.pointer);
                child.pointer->children.push_back(directGradients[i].pointer);
            }
            for (auto item : nodes[i].pointer->parents) {
                auto parent = item.lock();
                // Check if parent is not constant
                if(parent->type != CONSTANT) {
                    // Mark parent as node to traverse
                    subtree[parent->id] = true;
                    // Create the corresponding message as a new node and add it to the parents list
                    // of gradient incoming messages
                    ADNode capsule = ADNode(this);
                    capsule.pointer = parent;
                    //childrenGradients[parent->id].push_back(createConstantVariable(Matrix::Constant(1,1,1)));
                    std::cout << "Capsule: " << capsule.builder << " - " << capsule.pointer->id << std::endl;
                    childrenGradients[parent->id].push_back(createGradientMessage(nodes[i], capsule, directGradients[i]));
                    std::cout << "Capsule: " << capsule.builder << " - " << capsule.pointer->id << std::endl;
                    //childrenGradients[parent->id].back().pointer->name = "Gradinet[" + childrenGradients[parent->id].back().pointer->name + "]";
                }
            }
        }
    }
    return results;
};

ADNode ADGraphBuilder::createGradientMessage(const ADNode& child, const ADNode& parent, const ADNode& directGradient){
    switch (child.pointer->op){
        case(OPERATOR::NONE):
                std::cout << "Making gradient of an INPUT node? Are you serious?";
            return createInternalVariable(CONSTANT, OPERATOR::NONE, child.pointer->dim1,child.pointer->dim2,
                                          std::to_string(child.pointer->id) + "->" + std::to_string(parent.pointer->id));
        case(OPERATOR::ADD):
            return directGradient;
        case(OPERATOR::UNNARY_NEGATION):
            return -directGradient;
        case(OPERATOR::DOT_MULTIPLY):
            if(child.pointer->parents.size() == 2){
                int index = getIndex(child.pointer->parents, parent);
                ADNode otherParent(child.builder);
                otherParent.pointer = child.pointer->parents[1-index].lock();
                if(index == 0)
                    return dot(directGradient,otherParent.transpose());
                else
                    return dot(otherParent.transpose(),directGradient);
            }
            else{
                std::cerr<< "Unimplemented" << std::endl;
                return NULL;
            }
        case(OPERATOR::VERTICAL_CONCATENATION): {
            int index = getIndex(child.pointer->parents, parent);
            int start = 0;
            for (int i = 0; i < index; ++i) {
                auto parent = child.pointer->parents[i].lock();
                start += parent->dim1;
            }
            return directGradient.block(start, 0, parent.pointer->dim1, parent.pointer->dim2);
        }
        case(OPERATOR::TANH):
            return directGradient * child * (1 - child);
    }
}


#endif //ADVIBE_STACK_H

The main function I ran is:

#include <iostream>
#include "Eigen/Dense"
#include "stack.h"

int main() {

    ADGraphBuilder builder;
    ADNode param1 = builder.createVariable(2,1);
    ADNode param2 = builder.createVariable(2,3);
    ADNode h = tanh(dot(param2, vertCat(param1,1)));
    for (int i = 0; i < 0; ++i) {
        h = tanh(dot(param2,vertCat(h,1)));
    }
    ADNode e = dot(h.transpose(), h);
    auto grad = builder.gradient(e, param2);
    std::cout << "(" << e.pointer->dim1 << ", " << e.pointer->dim2 << ")" << std::endl;
    return 0;
}

And the result is:

/media/hdd/work/c/adVibe/executables/adVibe
Joyning 1 and 3
Joyning 6 and 5
passed 7
Capsule: 0x7fffba09ebd0 - 6
Joyning 8 and 9
Capsule: 0x7fffba09ebd0 - 6
Capsule: 0x7fffba09ebd0 - 5
Joyning 11 and 8
Capsule: 0x7fffba09ebd0 - 5
passed 6
Capsule: 0x7fffba09ebd0 - 5
Capsule: 0x7fffba09ebd0 - 5
passed 5
Capsule: 0x7fffba09ebd0 - 4
5 U 
NEG: 0x7fffba09ebd0 - 5
NEG2: 0x7fffba09ebd0 - 5
NEGRES: 15
ADD: 16 - 0x7fffba09ebd0 - 15
Joyning 16 and 15
ADD2: 16 - 0x7fffba09ebd0 - 15
ADDRES: 17
MULT: 14 - 0 - 5
Different builders 
terminate called after throwing an instance of 'int'

Process finished with exit code 134

From this all I could infer is that in the funcreateGradientMessage on the switch for TANH the segfault occurs for the expression: directGradient * child * (1 - child). From the output I can see that this is what happens in order:

1. Unary negation on node 5 resulting in 15
2. Addition of node 16 and 15 (e.g. the brackets) resulting in 17
3. trying to multiply 14 and 5 - SEGFAULT something wrong with 5

So my question is what exactly is happening? I tried to understand but can't.

[GCDEF]

Your debugger should show you everything that's going on. Did you try it?

[botevmg]

Your debugger should show you everything that's going on. Did you try it?

Yes I tried, but still did not show me when, how or what is happening so that the 'child' variable is invalid.