Node.h

Go to the documentation of this file.

#pragma once

#include <functional>
#include <stack>

#include "IO.h"
#include "Miscellaneous.h"
#include "Rule.h"
#include "Program.h"
#include "BaseNode.h"
#include "Builtins.h"

class Node : public BaseNode<Node> {
    friend class BaseNode<Node>;
    
public:

    // These are used in parseable to delimit nodes nonterminals and multiple nodes in a tree
    const static char NTDelimiter = ':'; // delimit nt:format 
    const static char RuleDelimiter = ';'; // delimit a sequence of nt:format;nt:format; etc

public:
    const Rule*  rule; // which rule did I use?
    double       lp; 
    bool         can_resample;  

    Node(const Rule* r=nullptr, double _lp=0.0, bool cr=true) : 
        BaseNode(r==nullptr?0:r->N), rule(r==nullptr ? NullRule : r), lp(_lp), can_resample(cr) {   
        // NOTE: We don't allow parent to be set here bcause that maeks pi hard to set. We shuold only be placed
        // in trees with set_child
        if(r != nullptr)
            children.resize(r->N);
    }
    
    /* We must define our own copy and move since parent can't just be simply copied */ 
    Node(const Node& n) :
        BaseNode(n), rule(n.rule), lp(n.lp), can_resample(n.can_resample) {
    }
    Node(Node&& n) :
        BaseNode(n), rule(n.rule), lp(n.lp), can_resample(n.can_resample) {
    }
    
    virtual ~Node() {}
    
    void assign(Node& n) {
        children = n.children;
        this->rule = n.rule;
        this->lp = n.lp;
        this->can_resample = n.can_resample;    
        fix_child_info(); // update the children so they point to the right parent
    }
    void assign(Node&& n) {
        children = std::move(n.children);
        this->rule = n.rule;
        this->lp = n.lp;
        this->can_resample = n.can_resample;    
        fix_child_info();
    }
    
    const std::string& format() const {
        return this->rule->format;
    }
    
    nonterminal_t type(const size_t i) const {
        return rule->type(i);
    }
    
    void set_child(const size_t i, Node& n) {
        assert(i < rule->N);
        assert(n.rule == NullRule or n.nt() == rule->type(i)); // no type checking when the rule is null
        BaseNode<Node>::set_child(i,n);
    }
    void set_child(const size_t i, Node&& n) {
        assert(i < rule->N);
        if(n.rule != NullRule and n.nt() != rule->type(i)) {
            print("### Error in set_child: ", n.string(), " does not match required type", rule->type(i), n.nt(), string());
            assert(false);
        }
        assert(n.rule == NullRule or n.nt() == rule->type(i)); // no type checking when the rule is null
        BaseNode<Node>::set_child(i,std::move(n));
    }


    void operator=(const Node& n) {
        // Here in the assignment operator we don't set the parent to n.parent, otherwise the parent pointers get broken
        // (nor pi). This leaves them in their place in a tree (so e.g. we can set a node of a tree and it still works)
        
        BaseNode<Node>::operator=(n);
        
        this->rule = n.rule;
        this->lp = n.lp;
        this->can_resample = n.can_resample;
    }

    void operator=(Node&& n) {
        
        BaseNode<Node>::operator=(n);
        
        this->rule = n.rule;
        this->lp = n.lp;
        this->can_resample = n.can_resample;
    }
    
    auto operator<=>(const Node& other) const {
        // We will sort based on the rules, except we recurse when they are unequal. 
        // This therefore sorts by the uppermost-leftmost rule that doesn't match. We are less than 
        // if we have fewer children
        if(*rule != *other.rule) {
            return (*rule) <=> (*other.rule);
        }
        else {
            
            if(this->children.size() != other.children.size()) {
                return this->children.size() <=> other.children.size();
            }

            for(size_t i=0;i<other.children.size();i++) {
                if(this->child(i) != other.child(i)) 
                    return this->child(i) <=> other.child(i);
            }
            
            return std::strong_ordering::equal;
        }
    }
    
    nonterminal_t nt() const {
        return this->rule->nt;
    }
    
    bool is_null() const { 
        return this->rule == NullRule;
    }
        
    virtual size_t count_nonnull() const {
        size_t n = 1*(not this->is_null()); // me
        for(auto& c : children) {
            n += c.count_nonnull();         
        }
        return n;
    }

    
    virtual bool is_complete() const {
        if(this->is_null()) return false;
        
        // does this have any subnodes below that are null?
        for(auto& c: this->children) {
            if(c.is_null()) return false; 
            if(not c.is_complete()) return false;
        }
        return this->children.size() == rule->N; // must have all my kids
    }
        
    
    virtual std::string string(bool usedot=true) const override { 
        // Be careful to process the arguments in the right orders
        
        if(this->rule->N == 0) {
            assert(this->children.size() == 0 && "*** Should have zero children -- did you accidentally add children to a null node (that doesn't have a format)?");
            return this->rule->format;
        }
        else {
            
            std::vector<std::string> childStrings(this->children.size());
        
            for(size_t i=0;i<this->rule->N;i++) {
                childStrings[i] = this->children[i].string();
            }
            
            // now substitute the children into the format
            std::string s = this->rule->format;
            if(usedot and not this->can_resample) s = "\u2022"+s; // just to help out in some cases, we'll add this to nodes that we can't resample

            for(size_t i=0;i<this->rule->N;i++) {
                
                // Here we put the i'th child by first trying position i, otherwise 
                // we search for %S
                // NOTE: This change might be a bit slower since it matches each %i, but hopefully that doesn't matter...
                std::string numstr = "%"+str(i+1); // This indexing is 1-based for some reason
                auto numpos = s.find(numstr);
                if(numpos != std::string::npos){
                    s.replace(numpos, numstr.length(), childStrings[i]);
                }
                else { // match via %s or %!s
                    auto pos    = s.find(Rule::ChildStr); // position of the next real match (typically matched)
                    auto silpos = s.find(Rule::SilentChildStr); // position of the next silent match
                    
                    if(pos == std::string::npos and silpos == std::string::npos) {
                        CERR "# Error on " TAB this->rule->format ENDL;
                        assert(false && "Node format must contain one ChildStr (typically='%s') for each argument"); // must contain the ChildStr for all children all children
                    }
                    
                    if(pos < silpos or silpos == std::string::npos) {
                        // if the next thing to substitute is a real string
                        assert(pos != std::string::npos);                       
                        s.replace(pos, Rule::ChildStr.length(), childStrings[i] );  
                    }
                    else {
                        // else we we do a "silent" replacement, matching silpos
                        assert(silpos != std::string::npos);
                        s.replace(silpos, Rule::SilentChildStr.length(), "");                           
                    }
                    
                                    
                }
            }
            return s;
        }
    }
    
    
    virtual std::string parseable() const {
        // get a string like one we could parse
        std::string out = str(this->nt()) + NTDelimiter + this->rule->format;
        for(auto& c: this->children) {
            out += RuleDelimiter + c.parseable();
        }
        return out;
    }
    

    /********************************************************
     * Operaitons for running programs
     ********************************************************/

    template<typename VirtualMachineState_t, typename Grammar_t>
    inline int linearize(Program<VirtualMachineState_t> &program) const { 
        // NOTE: If you change the order here ever, you have to change how string() works so that 
        //       string order matches evaluation order
        
        // and just a little checking here
        assert(rule != NullRule && "*** Cannot linearize if there is a null rule");
        for(size_t i=0;i<this->rule->N;i++) {
            assert(not this->children[i].is_null() && "Cannot linearize a Node with null children");
            assert(this->children[i].rule->nt == rule->type(i) && "Somehow the child has incorrect types -- this is bad news for you."); // make sure my kids types are what they should be
        }
        
        // If we are an if, then we must do some fancy short-circuiting
        if( rule->is_a(Op::If) ) {
            [[unlikely]]
            assert(rule->N == 3 && "BuiltinOp::op_IF require three arguments"); // must have 3 parts
            
            int ysize = children[2].linearize<VirtualMachineState_t,Grammar_t>(program);
            
            // encode the jump
            program.push(Builtins::Jmp<Grammar_t>.makeInstruction(ysize));
            
            int xsize = children[1].linearize<VirtualMachineState_t,Grammar_t>(program)+1; // must be +1 in order to skip over the JMP too
            
            // encode the if
            program.push(rule->makeInstruction(xsize));
            
            // evaluate the bool first so its on the stack when we get to if
            int boolsize = children[0].linearize<VirtualMachineState_t,Grammar_t>(program);
            
            return ysize + xsize + boolsize + 1; // +1 for if
        }
        else if( rule->is_a(Op::And) or rule->is_a(Op::Or)) {
            [[unlikely]]
            
            // short circuit forms of and(x,y) and or(x,y)
            assert(rule->N == 2 and children.size() == 2 && "BuiltinOp::op_AND and BuiltinOp::op_OR require two arguments");
            
            // second arg pushed on first, on the bottom
            int ysize = children[1].linearize<VirtualMachineState_t,Grammar_t>(program);
            
            if(rule->is_a(Op::And)) {
                program.push(rule->makeInstruction(ysize));
            }
            else if(rule->is_a(Op::Or)) {
                program.push(rule->makeInstruction(ysize));
            }
            else assert(false);
            
            return children[0].linearize<VirtualMachineState_t,Grammar_t>(program)+ysize+1;         
        }
        else {
            [[likely]]
            
            /* Else we just process a normal child. 
             * Here we push the children in increasing order. Then, when we pop rightmost first (as Primitive does), it 
             * assigns the correct index.  */
            program.push(this->rule->makeInstruction()); 
            
            int mysize = 1; // one for my own instruction
            for(int i=this->rule->N-1;i>=0;i--) { // here we linearize right to left so that when we call right to left, it matches string order            
                mysize += this->children[i].linearize<VirtualMachineState_t,Grammar_t>(program);
            }
            return mysize; 
        }
    }
        
    
    virtual bool operator==(const Node& n) const override {
        if(not (*rule == *n.rule))
            return false;
            
        if(this->children.size() != n.children.size())
            return false; 
    
        for(size_t i=0;i<this->children.size();i++){
            if(not (this->children[i] == n.children[i])) 
                return false;
        }
        return true;
    }
    
    virtual size_t hash(size_t depth=0) const {
        size_t ret = rule->get_hash(); // tunrs out, this is actually important to prevent hash collisions when rule_id and i are small
        for(size_t i=0;i<this->children.size();i++) {
            hash_combine(ret, depth, this->children[i].hash(depth+1), i); // modifies output
        }
        return ret;
    }

    virtual void fullprint(size_t tab=0) {
        
        std::string tb;
        for(size_t i=0;i<tab;i++) tb += "\t";
        
        print(tb, "this="+str(this), "parent="+str(parent), pi, children.size() == rule->N, rule->format);
        for(size_t i=0;i<children.size();i++) {
            children[i].fullprint(tab+1);
            if(children[i].parent != this) print("*** Warning child above does not have correct parent pointer.");
            if(children[i].pi != i) print("*** Warning child above does not have correct parent index.");
            
        }
    }

    
};