lib-src/rete/retenet.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 /////////////////////////////////////////////////////////////////
  26 //  This file implements the memorization and token propagation
  27 //  routines used by the Rete matching algorithm.
  28 /////////////////////////////////////////////////////////////////
  29 #include <AD/rete/retenet.h>
  30 #include <AD/memory/boundtag.h>
  31
  32 /////////////////////////////////////////////////////////////////
  33 //  A description of the data structures:
  34 //  There are 3 kinds of nodes within the network.
  35 //  (1) And nodes: these nodes have a left and a right input.
  36 //      A new token, computed as the concatention of the
  37 //      two inputs, is propagate to its output node if the new
  38 //      token satisfies the node test.
  39 //  (2) Not nodes: these nodes also have a left and a right input.
  40 //      The token from the left node is propagated only if
  41 //      there is no input from the right.
  42 //  (3) Terminal nodes: when a token arrives at these nodes it
  43 //      will be added to the conflict set.
  44 /////////////////////////////////////////////////////////////////
  45
  46 /////////////////////////////////////////////////////////////////
  47 // Make hidden types visible at top level
  48 /////////////////////////////////////////////////////////////////
  49 typedef ReteNet::NodeId NodeId;
  50 typedef ReteNet::RuleId RuleId;
  51 typedef ReteNet::Token  Token;
  52 typedef ReteNet::Node   Node;
  53
  54 /////////////////////////////////////////////////////////////////
  55 //  Constructor for class
  56 /////////////////////////////////////////////////////////////////
  57 ReteNet::ReteNet(int N, const Node net[])
  58    : mem     (* new BoundaryTag(4096)),  // create new memory manager
  59      number_of_nodes (N),
  60      network (net)
  61    {
  62       // set up alpha and beta memory.
  63       alpha = (AlphaMemo*) mem.c_alloc(sizeof(AlphaMemo) * N);
  64       beta  = (BetaMemo*)  mem.c_alloc(sizeof(BetaMemo) * N);
  65    }
  66
  67 /////////////////////////////////////////////////////////////////
  68 //  Destructor for class
  69 /////////////////////////////////////////////////////////////////
  70 ReteNet::~ReteNet() { delete (&mem); }
  71
  72 /////////////////////////////////////////////////////////////////
  73 //  Clears all alpha/beta memory
  74 /////////////////////////////////////////////////////////////////
  75 void ReteNet::clear()
  76 {  mem.clear();  // reset the memory manager
  77    // reallocate all alpha/beta memory
  78    alpha = (AlphaMemo*) mem.c_alloc(sizeof(AlphaMemo) * number_of_nodes);
  79    beta  = (BetaMemo*)  mem.c_alloc(sizeof(BetaMemo) * number_of_nodes);
  80 }
  81
  82 /////////////////////////////////////////////////////////////////
  83 //  Fast inlined copy
  84 /////////////////////////////////////////////////////////////////
  85 template<class T>
  86    inline void copy (register T * dest, register T * src, register int n)
  87    {  for ( ; n > 0; n--) *dest++ = *src++; }
  88
  89 /////////////////////////////////////////////////////////////////
  90 //  Routines for memorization management
  91 /////////////////////////////////////////////////////////////////
  92
  93 /////////////////////////////////////////////////////////////////
  94 //  Method: memorize_beta(...)
  95 //    This method addes a new token ``facts'' to the beta memory
  96 //  of a node; the beta memory is resized if necessary.
  97 /////////////////////////////////////////////////////////////////
  98 inline void ReteNet::memorize_beta(NodeId n, Fact ** facts)
  99 {  register BetaMemo& memo = beta[n];
 100    if (memo.count == memo.capacity) {
 101       int new_capacity  = memo.capacity * 3 / 2 + 2;
 102       Token * new_facts = (Token *)mem.m_alloc(new_capacity * sizeof(Token));
 103       if (memo.tokens) {
 104          copy(new_facts,memo.tokens,memo.capacity);
 105          mem.free(memo.tokens);
 106       }
 107       memo.capacity = new_capacity;
 108       memo.tokens   = new_facts;
 109    }
 110    Fact ** new_token = (Fact **)mem.m_alloc(network[n].arity * sizeof(Fact *));
 111    copy(new_token,facts,(int)network[n].arity);
 112    memo.tokens[memo.count++] = new_token;
 113 }
 114
 115 /////////////////////////////////////////////////////////////////
 116 //  Method: memorize_alpha(...)
 117 //    This method addes a new token ``facts'' to the alpha memory
 118 //  of a node; the alpha memory is resized if necessary.
 119 /////////////////////////////////////////////////////////////////
 120 inline void ReteNet::memorize_alpha(NodeId n, Fact * fact)
 121 {  register AlphaMemo& memo = alpha[n];
 122    if (memo.count == memo.capacity) {
 123       int new_capacity  = memo.capacity * 3 / 2 + 2;
 124       Fact ** new_facts = (Fact **)mem.m_alloc(new_capacity * sizeof(Fact *));
 125       if (memo.facts) {
 126          copy(new_facts,memo.facts,memo.capacity);
 127          mem.free(memo.facts);
 128       }
 129       memo.capacity = new_capacity;
 130       memo.facts    = new_facts;
 131    }
 132    memo.facts[memo.count++] = fact;
 133 }
 134
 135 /////////////////////////////////////////////////////////////////
 136 //  Method: memorize_not_on_beta(...)
 137 //    This method addes a new token ``facts'' to the beta memory
 138 //  of a negation node; the beta memory is resized if necessary.
 139 /////////////////////////////////////////////////////////////////
 140 inline void ReteNet::memorize_not_on_beta(NodeId n, int matches, Fact ** facts)
 141 {  register BetaMemo& memo = beta[n];
 142    if (memo.count == memo.capacity) {
 143       int new_capacity  = memo.capacity * 3 / 2 + 2;
 144       Token * new_facts = (Token *)mem.m_alloc(new_capacity * sizeof(Token));
 145       int * new_matches = (int *)mem.c_alloc(new_capacity * sizeof(int));
 146       if (memo.tokens) {
 147          copy(new_facts,memo.tokens,memo.capacity);
 148          copy(new_matches,memo.matches,memo.capacity);
 149          mem.free(memo.tokens);
 150          mem.free(memo.matches);
 151       }
 152       memo.capacity = new_capacity;
 153       memo.tokens   = new_facts;
 154       memo.matches  = new_matches;
 155    }
 156    Fact ** new_token = (Fact **)mem.m_alloc(network[n].arity * sizeof(Fact *));
 157    copy(new_token,facts,(int)network[n].arity);
 158    memo.matches[memo.count]  = matches;
 159    memo.tokens[memo.count++] = new_token;
 160 }
 161
 162 //////////////////////////////////////////////////////////////////////////
 163 //  Insert a partially constructed token into a node from the beta side
 164 //////////////////////////////////////////////////////////////////////////
 165 void ReteNet::insert_beta(NodeId n, Fact * facts[])
 166 {  register const Node& node = network[n];
 167    register int i;
 168
 169    switch (node.kind) {
 170       ////////////////////////////////////////////////////////////////////
 171       // Testing node; just apply the test and propagate the token
 172       //   if the test is satisfied.
 173       ////////////////////////////////////////////////////////////////////
 174       case Node::Fork:
 175          insert_beta(node.child,facts); insert_beta(n+1,facts); break;
 176       case Node::Test:
 177          if (node.join == 0 || beta_test(node.join,facts))
 178             insert_beta(node.child,facts);
 179          break;
 180       ////////////////////////////////////////////////////////////////////
 181       // Conjunctive node:
 182       //   Concatenate the new fact with every alpha input memorized;
 183       //   apply the join on this new token, and propagate the token
 184       //   if it is satisfied.   Also, memorize the new beta input.
 185       ////////////////////////////////////////////////////////////////////
 186       case Node::And:
 187       {  register AlphaMemo& memo = alpha[n];
 188          for (i = memo.count - 1; i >= 0; i--) {
 189             facts[node.beta_arity] = memo.facts[i];
 190             if (node.join == 0 || beta_test(node.join,facts))
 191                insert_beta(node.child,facts);
 192          }
 193          memorize_beta(n,facts);
 194       }  break;
 195       ////////////////////////////////////////////////////////////////////
 196       // Negation node:
 197       //   Concatenate the new fact with every alpha input memorized;
 198       //   apply the join on this new token, and propagate the token
 199       //   if *none* of the join is satisfied.
 200       //   Also, memorize the new beta input.
 201       ////////////////////////////////////////////////////////////////////
 202       case Node::Not:
 203       {  register AlphaMemo& memo = alpha[n];
 204          int match_count;
 205          for (match_count = 0, i = memo.count - 1; i >= 0; i--) {
 206             facts[node.beta_arity] = memo.facts[i];
 207             if (node.join == 0 || beta_test(node.join,facts)) match_count++;
 208          }
 209          memorize_not_on_beta(n,match_count,facts);
 210          if (match_count == 0) insert_beta(node.child,facts);
 211       }  break;
 212       ////////////////////////////////////////////////////////////////////
 213       //  Terminal node: when we get here we call activate(...)
 214       //  to add the token into the conflict set.
 215       ////////////////////////////////////////////////////////////////////
 216       case Node::Bot: activate(node.child,node.arity,facts); break;
 217       default: break;
 218    }
 219 }
 220
 221 //////////////////////////////////////////////////////////////////////////
 222 //  Insert a partially constructed token into a node from the alpha side
 223 //////////////////////////////////////////////////////////////////////////
 224 void ReteNet::insert_alpha(NodeId n, Fact * fact)
 225 {  register const Node& node = network[n];
 226    register int i;
 227
 228    switch (node.kind) {
 229       case Node::Alpha:
 230          memorize_alpha(n,fact);
 231          insert_alpha(node.child, fact);
 232          break;
 233       ////////////////////////////////////////////////////////////////////
 234       // Conjunctive node:
 235       //   Concatenate the new fact with every beta input memorized;
 236       //   apply the join on this new token, and propagate the token
 237       //   if it is satisfied.   Also, memorize the new alpha input.
 238       ////////////////////////////////////////////////////////////////////
 239       case Node::And:
 240       {  register BetaMemo& memo = beta[n];
 241          for (i = memo.count - 1; i >= 0; i--) {
 242             Fact ** facts = memo.tokens[i];
 243             facts[node.beta_arity] = fact;
 244             if (node.join == 0 || beta_test(node.join,facts))
 245                insert_beta(node.child,facts);
 246          }
 247          memorize_alpha(n,fact);
 248       } break;
 249       ////////////////////////////////////////////////////////////////////
 250       // Negation node:
 251       //   Concatenate the new fact with every beta input memorized;
 252       //   apply the join on this new token, and propagate the token
 253       //   to be removed if the join is not satisfied when previously
 254       //   none was.
 255       //   Also, memorize the new alpha input.
 256       ////////////////////////////////////////////////////////////////////
 257       case Node::Not:
 258       {  register BetaMemo& memo = beta[n];
 259          for (i = memo.count - 1; i >= 0; i--) {
 260             Fact ** facts = memo.tokens[i];
 261             facts[node.beta_arity] = fact;
 262             if (node.join == 0 || beta_test(node.join,facts))
 263                if (memo.matches[i]++ == 0) remove_beta(node.child,facts);
 264          }
 265          memorize_alpha(n,fact);
 266       } break;
 267       ////////////////////////////////////////////////////////////////////
 268       // Terminal node.
 269       ////////////////////////////////////////////////////////////////////
 270       case Node::Bot:
 271       {  Fact * facts[1];
 272          facts[0] = fact;
 273          activate(node.child,1,facts);
 274       } break;
 275       default: break;
 276    }
 277 }
 278
 279 //////////////////////////////////////////////////////////////////////////
 280 //  Remove a token from a node from the beta side
 281 //////////////////////////////////////////////////////////////////////////
 282 void ReteNet::remove_beta(NodeId n, Fact * facts[])
 283 {  register const Node& node = network[n];
 284    register int i;
 285
 286    switch (node.kind) {
 287       ////////////////////////////////////////////////////////////////////
 288       //  Testing node: apply the join and if it is satisfied
 289       //    propagate the token to be removed.
 290       ////////////////////////////////////////////////////////////////////
 291       case Node::Fork:
 292          remove_beta(node.child,facts); remove_beta(n+1,facts); break;
 293       case Node::Test:
 294          if (node.join == 0 || beta_test(node.join,facts))
 295             remove_beta(node.child,facts);
 296          break;
 297       ////////////////////////////////////////////////////////////////////
 298       // Conjunctive, Negation node:
 299       //   Concatenate the new fact with every beta input memorized;
 300       //   apply the join on this new token, and propagate the token
 301       //   to be removed if it is satisfied.   Also, remove the token
 302       //   from the beta memory.
 303       ////////////////////////////////////////////////////////////////////
 304       case Node::And:
 305       case Node::Not:
 306       {  register BetaMemo&  l = beta[n];
 307          register AlphaMemo& r = alpha[n];
 308          for (i = l.count - 1; i >= 0; i--) {
 309             int j;
 310             for (j = node.beta_arity - 1; j >= 0; j--)
 311                if (l.tokens[i][j] != facts[j]) goto next;
 312             for (j = r.count - 1; j >= 0; j--) {
 313                facts[node.beta_arity] = r.facts[j];
 314                if (node.join == 0 || beta_test(node.join,facts))
 315                   remove_beta(node.child,facts);
 316             }
 317             l.tokens[i] = l.tokens[--l.count];
 318             l.matches[i] = l.matches[l.count];
 319             mem.free(l.tokens[i]);
 320          next: ;
 321          }
 322       } break;
 323       case Node::Bot: deactivate(node.child,node.arity,facts); break;
 324       default: break;
 325    }
 326 }
 327
 328 //////////////////////////////////////////////////////////////////////////
 329 //  Remove a token from a node from the alpha side
 330 //////////////////////////////////////////////////////////////////////////
 331 void ReteNet::remove_alpha(NodeId n, Fact * fact)
 332 {  register const Node& node = network[n];
 333    register int i;
 334
 335    switch (node.kind) {
 336       case Node::Alpha:
 337       {  register AlphaMemo& r = alpha[n];
 338          for (i = r.count - 1; i >= 0; i--) {
 339             if (r.facts[i] == fact) {
 340                remove_alpha(node.child, fact);
 341                mem.free(r.facts[i]);
 342                r.facts[i] = r.facts[--r.count];
 343             }
 344          }
 345          break;
 346       }
 347       ////////////////////////////////////////////////////////////////////
 348       // Conjunctive node:
 349       //   Concatenate the new fact with every alpha input memorized;
 350       //   apply the join on this new token, and propagate the token
 351       //   to be removed if it is satisfied.   Also, remove the token
 352       //   from the alpha memory.
 353       ////////////////////////////////////////////////////////////////////
 354       case Node::And:
 355       {  register AlphaMemo& r = alpha[n];
 356          register BetaMemo&  l = beta[n];
 357          for (i = r.count - 1; i >= 0; i--) {
 358             if (r.facts[i] == fact) {
 359                for (int j = l.count - 1; j >= 0; j--) {
 360                   Fact ** facts = l.tokens[j];
 361                   facts[node.beta_arity] = fact;
 362                   if (node.join == 0 || beta_test(node.join,facts))
 363                      remove_beta(node.child,facts);
 364                }
 365                mem.free(r.facts[i]);
 366                r.facts[i] = r.facts[--r.count];
 367             }
 368          }
 369       } break;
 370       ////////////////////////////////////////////////////////////////////
 371       // Negation node:
 372       //   Concatenate the new fact with every beta input memorized;
 373       //   apply the join on this new token, and propagate the token
 374       //   to be removed if it is satisfied.   Also, remove the token
 375       //   from the alpha memory.
 376       ////////////////////////////////////////////////////////////////////
 377       case Node::Not:
 378       {  register AlphaMemo& r = alpha[n];
 379          /////////////////////////////////////////////////////////////////
 380          // Search for the given fact from the alpha side.  If it is found,
 381          // we'll run the join with the beta side.
 382          /////////////////////////////////////////////////////////////////
 383          for (i = r.count - 1; i >= 0; i--) {
 384             if (r.facts[i] == fact) {
 385                register BetaMemo& l = beta[n];
 386                for (int j = l.count - 1; j >= 0; j--) {
 387                   Fact ** facts = l.tokens[j];
 388                   facts[node.beta_arity] = fact;
 389                   ///////////////////////////////////////////////////////////
 390                   // If the join is good, we'll decrement the matching count.
 391                   // When this count reaches 0, the beta token is propagated.
 392                   ///////////////////////////////////////////////////////////
 393                   if (node.join == 0 || beta_test(node.join,facts)) {
 394                      if (--l.matches[j] == 0) {
 395                         insert_beta(node.child,facts);
 396                         mem.free(facts);
 397                         l.tokens[j] = l.tokens[--l.count];
 398                         l.matches[j] = l.matches[l.count];
 399                      }
 400                   }
 401                }
 402                r.facts[i] = r.facts[--r.count];
 403             }
 404          }
 405       }  break;
 406       default: break;
 407    }
 408 }