Fleet  0.0.9
Inference in the LOT
Node.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include <functional>
4 #include <stack>
5 
6 #include "IO.h"
7 #include "Miscellaneous.h"
8 #include "Rule.h"
9 #include "Program.h"
10 #include "BaseNode.h"
11 #include "Builtins.h"
12 
22 class Node : public BaseNode<Node> {
23  friend class BaseNode<Node>;
24 
25 public:
26 
27  // These are used in parseable to delimit nodes nonterminals and multiple nodes in a tree
28  const static char NTDelimiter = ':'; // delimit nt:format
29  const static char RuleDelimiter = ';'; // delimit a sequence of nt:format;nt:format; etc
30 
31 public:
32  const Rule* rule; // which rule did I use?
33  double lp;
34  bool can_resample;
35 
36  Node(const Rule* r=nullptr, double _lp=0.0, bool cr=true) :
37  BaseNode(r==nullptr?0:r->N), rule(r==nullptr ? NullRule : r), lp(_lp), can_resample(cr) {
38  // NOTE: We don't allow parent to be set here bcause that maeks pi hard to set. We shuold only be placed
39  // in trees with set_child
40  if(r != nullptr)
41  children.resize(r->N);
42  }
43 
44  /* We must define our own copy and move since parent can't just be simply copied */
45  Node(const Node& n) :
46  BaseNode(n), rule(n.rule), lp(n.lp), can_resample(n.can_resample) {
47  }
48  Node(Node&& n) :
49  BaseNode(n), rule(n.rule), lp(n.lp), can_resample(n.can_resample) {
50  }
51 
52  virtual ~Node() {}
53 
59  void assign(Node& n) {
60  children = n.children;
61  this->rule = n.rule;
62  this->lp = n.lp;
63  this->can_resample = n.can_resample;
64  fix_child_info(); // update the children so they point to the right parent
65  }
66  void assign(Node&& n) {
67  children = std::move(n.children);
68  this->rule = n.rule;
69  this->lp = n.lp;
70  this->can_resample = n.can_resample;
72  }
73 
74  const std::string& format() const {
75  return this->rule->format;
76  }
77 
78  nonterminal_t type(const size_t i) const {
85  return rule->type(i);
86  }
87 
88  void set_child(const size_t i, Node& n) {
94  assert(i < rule->N);
95  assert(n.rule == NullRule or n.nt() == rule->type(i)); // no type checking when the rule is null
97  }
98  void set_child(const size_t i, Node&& n) {
104  assert(i < rule->N);
105  assert(n.rule == NullRule or n.nt() == rule->type(i)); // no type checking when the rule is null
106  BaseNode<Node>::set_child(i,std::move(n));
107  }
108 
109 
110  void operator=(const Node& n) {
111  // Here in the assignment operator we don't set the parent to n.parent, otherwise the parent pointers get broken
112  // (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)
113 
115 
116  this->rule = n.rule;
117  this->lp = n.lp;
118  this->can_resample = n.can_resample;
119  }
120 
121  void operator=(Node&& n) {
122 
124 
125  this->rule = n.rule;
126  this->lp = n.lp;
127  this->can_resample = n.can_resample;
128  }
129 
130  bool operator<(const Node& n) const {
131  // We will sort based on the rules, except we recurse when they are unequal.
132  // This therefore sorts by the uppermost-leftmost rule that doesn't match. We are less than
133  // if we have fewer children
134  if(*rule < *n.rule) {
135  return true;
136  }
137  else if(*n.rule < *rule) {
138  return false;
139  }
140  else {
141 
142  if(this->children.size() != n.children.size()) {
143  return this->children.size() < n.children.size();
144  }
145 
146  for(size_t i=0;i<n.children.size();i++) {
147  if(this->child(i) < n.child(i))
148  return true;
149  else if (n.child(i) < this->child(i)) {
150  return false;
151  }
152  }
153 
154  return false;
155  }
156  }
157 
158  nonterminal_t nt() const {
164  return this->rule->nt;
165  }
166 
167  bool is_null() const {
173  return this->rule == NullRule;
174  }
175 
176  virtual size_t count_nonnull() const {
182  size_t n = 1*(not this->is_null()); // me
183  for(auto& c : children) {
184  n += c.count_nonnull();
185  }
186  return n;
187  }
188 
189 
190  virtual bool is_complete() const {
196  if(this->is_null()) return false;
197 
198  // does this have any subnodes below that are null?
199  for(auto& c: this->children) {
200  if(c.is_null()) return false;
201  if(not c.is_complete()) return false;
202  }
203  return this->children.size() == rule->N; // must have all my kids
204  }
205 
206 
207  virtual std::string string(bool usedot=true) const override {
214  // Be careful to process the arguments in the right orders
215 
216  if(this->rule->N == 0) {
217  assert(this->children.size() == 0 && "*** Should have zero children -- did you accidentally add children to a null node (that doesn't have a format)?");
218  return this->rule->format;
219  }
220  else {
221 
222  std::vector<std::string> childStrings(this->children.size());
223 
224  for(size_t i=0;i<this->rule->N;i++) {
225  childStrings[i] = this->children[i].string();
226  }
227 
228  // now substitute the children into the format
229  std::string s = this->rule->format;
230  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
231 
232  for(size_t i=0;i<this->rule->N;i++) {
233  // Here we put the i'th child by first trying position i, otherwise
234  // we search for %S
235  // NOTE: This change might be a bit slower since it matches each %i, but hopefully that doesn't matter...
236  std::string numstr = "%"+str(i+1); // This indexing is 1-based for some reason
237  auto numpos = s.find(numstr);
238  if(numpos != std::string::npos){
239  s.replace(numpos, numstr.length(), childStrings[i]);
240  }
241  else { // match via %s
242  auto pos = s.find(Rule::ChildStr);
243  if(pos == std::string::npos) {
244  CERR "# Error on " TAB this->rule->format ENDL;
245  assert(false && "Node format must contain one ChildStr (typically='%s') for each argument"); // must contain the ChildStr for all children all children
246  }
247  s.replace(pos, Rule::ChildStr.length(), childStrings[i] );
248  }
249  }
250  return s;
251  }
252  }
253 
254 
255  virtual std::string parseable() const {
261  // get a string like one we could parse
262  std::string out = str(this->nt()) + NTDelimiter + this->rule->format;
263  for(auto& c: this->children) {
264  out += RuleDelimiter + c.parseable();
265  }
266  return out;
267  }
268 
269 
270  /********************************************************
271  * Operaitons for running programs
272  ********************************************************/
273 
274  template<typename VirtualMachineState_t, typename Grammar_t>
275  inline int linearize(Program<VirtualMachineState_t> &program) const {
291  // NOTE: If you change the order here ever, you have to change how string() works so that
292  // string order matches evaluation order
293 
294  // and just a little checking here
295  assert(rule != NullRule && "*** Cannot linearize if there is a null rule");
296  for(size_t i=0;i<this->rule->N;i++) {
297  assert(not this->children[i].is_null() && "Cannot linearize a Node with null children");
298  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
299  }
300 
301  // If we are an if, then we must do some fancy short-circuiting
302  if( rule->is_a(Op::If) ) {
303  assert(rule->N == 3 && "BuiltinOp::op_IF require three arguments"); // must have 3 parts
304 
305  int ysize = children[2].linearize<VirtualMachineState_t,Grammar_t>(program);
306 
307  // encode the jump
308  program.push(Builtins::Jmp<Grammar_t>.makeInstruction(ysize));
309 
310  int xsize = children[1].linearize<VirtualMachineState_t,Grammar_t>(program)+1; // must be +1 in order to skip over the JMP too
311 
312  // encode the if
313  program.push(rule->makeInstruction(xsize));
314 
315  // evaluate the bool first so its on the stack when we get to if
316  int boolsize = children[0].linearize<VirtualMachineState_t,Grammar_t>(program);
317 
318  return ysize + xsize + boolsize + 1; // +1 for if
319  }
320  else if( rule->is_a(Op::And) or rule->is_a(Op::Or)) {
321  // short circuit forms of and(x,y) and or(x,y)
322  assert(rule->N == 2 and children.size() == 2 && "BuiltinOp::op_AND and BuiltinOp::op_OR require two arguments");
323 
324  // second arg pushed on first, on the bottom
325  int ysize = children[1].linearize<VirtualMachineState_t,Grammar_t>(program);
326 
327  if(rule->is_a(Op::And)) {
328  program.push(rule->makeInstruction(ysize));
329  }
330  else if(rule->is_a(Op::Or)) {
331  program.push(rule->makeInstruction(ysize));
332  }
333  else assert(false);
334 
335  return children[0].linearize<VirtualMachineState_t,Grammar_t>(program)+ysize+1;
336  }
337  else {
338  /* Else we just process a normal child.
339  * Here we push the children in increasing order. Then, when we pop rightmost first (as Primitive does), it
340  * assigns the correct index. */
341  program.push(this->rule->makeInstruction());
342 
343  int mysize = 1; // one for my own instruction
344  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
345  mysize += this->children[i].linearize<VirtualMachineState_t,Grammar_t>(program);
346  }
347  return mysize;
348  }
349  }
350 
351 
352  virtual bool operator==(const Node& n) const override {
359  if(not (*rule == *n.rule))
360  return false;
361 
362  if(this->children.size() != n.children.size())
363  return false;
364 
365  for(size_t i=0;i<this->children.size();i++){
366  if(not (this->children[i] == n.children[i])) return false;
367  }
368  return true;
369  }
370 
371  virtual size_t hash(size_t depth=0) const {
378  size_t ret = rule->get_hash(); // tunrs out, this is actually important to prevent hash collisions when rule_id and i are small
379  for(size_t i=0;i<this->children.size();i++) {
380  hash_combine(ret, depth, this->children[i].hash(depth+1), i); // modifies output
381  }
382  return ret;
383  }
384 
389  virtual void fullprint(size_t tab=0) {
390 
391  std::string tb;
392  for(size_t i=0;i<tab;i++) tb += "\t";
393 
394  print(tb, "this="+str(this), "parent="+str(parent), pi, children.size() == rule->N, rule->format);
395  for(size_t i=0;i<children.size();i++) {
396  children[i].fullprint(tab+1);
397  if(children[i].parent != this) print("*** Warning child above does not have correct parent pointer.");
398  if(children[i].pi != i) print("*** Warning child above does not have correct parent index.");
399 
400  }
401  }
402 
403 
404 };
The Builtin type just stores a function pointer and an Op command. This makes it a bit handier to def...
void operator=(const Node &n)
Definition: Node.h:110
double lp
Definition: Node.h:33
virtual ~Node()
Definition: Node.h:52
void push(const Instruction &val)
Push val onto the stack.
Definition: Stack.h:49
size_t pi
Definition: BaseNode.h:27
void set_child(const size_t i, Node &&n)
Definition: Node.h:98
Definition: Node.h:22
void assign(Node &&n)
Definition: Node.h:66
std::vector< Node > children
Definition: BaseNode.h:23
void operator=(Node &&n)
Definition: Node.h:121
This is a general tree class, which we are adding because there are currently at least 3 different tr...
void hash_combine(std::size_t &seed)
Definition: Miscellaneous.h:54
const std::string & format() const
Definition: Node.h:74
virtual std::string string(bool usedot=true) const override
Definition: Node.h:207
void fix_child_info()
Definition: BaseNode.h:229
#define TAB
Definition: IO.h:19
bool is_a(Op o) const
Definition: Rule.h:73
nonterminal_t type(size_t i) const
Definition: Rule.h:147
virtual std::string parseable() const
Definition: Node.h:255
void set_child(const size_t i, this_t &n)
Definition: BaseNode.h:274
Definition: Rule.h:21
nonterminal_t type(const size_t i) const
Definition: Node.h:78
static const std::string ChildStr
Definition: Rule.h:24
size_t get_hash() const
Definition: Rule.h:134
const Rule * NullRule
Definition: Rule.h:181
std::string str(BindingTree *t)
Definition: BindingTree.h:195
virtual bool is_complete() const
Definition: Node.h:190
static const char RuleDelimiter
Definition: Node.h:29
size_t N
Definition: Rule.h:28
void print(FIRST f, ARGS... args)
Lock output_lcok and print to std:cout.
Definition: IO.h:53
bool is_null() const
Definition: Node.h:167
Definition: BaseNode.h:20
static const char NTDelimiter
Definition: Node.h:28
std::string format
Definition: Rule.h:27
void assign(Node &n)
Assign will set everything to n BUT it will not copy the parent points etc since we&#39;re assuming this ...
Definition: Node.h:59
#define CERR
Definition: IO.h:23
nonterminal_t nt() const
Definition: Node.h:158
Node & child(const size_t i)
Definition: BaseNode.h:166
const Rule * rule
Definition: Node.h:32
unsigned short nonterminal_t
Definition: Nonterminal.h:4
A Rule stores one possible expansion in the grammar, specifying a nonterminal type, an instruction that gets executed, a forma string, a number of children, and an array of types of each child. Here we "emulate" a type system using t_nonterminal to store an integer for the types. *.
void set_child(const size_t i, Node &n)
Definition: Node.h:88
Node * parent
Definition: BaseNode.h:26
virtual void fullprint(size_t tab=0)
A function to print out everything, for debugging purposes.
Definition: Node.h:389
int linearize(Program< VirtualMachineState_t > &program) const
Definition: Node.h:275
#define ENDL
Definition: IO.h:21
virtual size_t count_nonnull() const
Definition: Node.h:176
virtual bool operator==(const Node &n) const override
Definition: Node.h:352
void operator=(const this_t &t)
Definition: BaseNode.h:51
bool can_resample
Definition: Node.h:34
nonterminal_t nt
Definition: Rule.h:26
size_t depth() const
Definition: BaseNode.h:221
Node(const Rule *r=nullptr, double _lp=0.0, bool cr=true)
Definition: Node.h:36
Definition: Program.h:6
Instruction makeInstruction(int a) const
Definition: Rule.h:91
A program here stores just a stack of instructions which can be executed by the VirtualMachineState_t...
Node(const Node &n)
Definition: Node.h:45
Node(Node &&n)
Definition: Node.h:48
virtual size_t hash(size_t depth=0) const
Definition: Node.h:371
bool operator<(const Node &n) const
Definition: Node.h:130