cde/programs/dtinfo/dtinfo/src/Basic/ParseTree.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  * $XConsortium: ParseTree.cc /main/3 1996/06/11 16:21:40 cde-hal $
  25  *
  26  * Copyright (c) 1991 HaL Computer Systems, Inc.  All rights reserved.
  27  * UNPUBLISHED -- rights reserved under the Copyright Laws of the United
  28  * States.  Use of a copyright notice is precautionary only and does not
  29  * imply publication or disclosure.
  30  *
  31  * This software contains confidential information and trade secrets of HaL
  32  * Computer Systems, Inc.  Use, disclosure, or reproduction is prohibited
  33  * without the prior express written permission of HaL Computer Systems, Inc.
  34  *
  35  *                         RESTRICTED RIGHTS LEGEND
  36  * Use, duplication, or disclosure by the Government is subject to
  37  * restrictions as set forth in subparagraph (c)(l)(ii) of the Rights in
  38  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  39  *                        HaL Computer Systems, Inc.
  40  *                  1315 Dell Avenue, Campbell, CA  95008
  41  *
  42  */
  43
  44 #define C_ParseTree
  45 #define L_Basic
  46
  47 #include "../Prelude.h"
  48 #include <string.h>
  49 #include <stdlib.h>
  50
  51 #ifdef SUN_CPP
  52 #define InitBase(T) \
  53   const ClassType T::T/**/Class = (ClassType *) &T::T/**/Class
  54 #else
  55 #define InitBase(T) \
  56   const ClassType T::T##Class = (ClassType *) &T::T##Class
  57 #endif
  58
  59 #define InitLeaf(T,P) \
  60   InitBase (T); const int T::f_precedence = P
  61 #define InitLeafS(T,P,S) \
  62   InitBase (T); const int T::f_precedence = P; char *T::f_symbol = S
  63
  64 bool PNode::f_recursive_delete = FALSE;
  65
  66 InitBase  (PNode);
  67 InitBase  (PBooleanOp);
  68 InitBase  (PRelation);
  69 InitBase  (PPrefixOp);
  70 InitBase  (PPostfixOp);
  71 InitBase  (PText);
  72 InitBase  (PRoot);
  73
  74 InitLeafS (PWeight,     7,  " weight "  );
  75 InitLeafS (PProximity,  7,  " within "  );
  76 InitLeafS (PNotBoth,    7,  " not_both" );
  77 InitLeafS (PStart,      0,  "("         );
  78 InitLeafS (PEnd,        0,  ")"         );
  79 InitLeaf  (PGroup,      0               );
  80 InitLeafS (PNot,        5,  "not "      );
  81 InitLeafS (PNear,       4,  " near "    );
  82 InitLeafS (PBefore,     4,  " before "  );
  83 InitLeafS (PAnd,        3,  " and "     );
  84 InitLeafS (POr,         2,  " or "      );
  85 InitLeaf  (PString,     8               );
  86 InitLeaf  (PNumber,     8               );
  87
  88 // /////////////////////////////////////////////////////////////////
  89 // Constructors
  90 // /////////////////////////////////////////////////////////////////
  91
  92 PNode::PNode (PNode *parent, PNode *previous, PNode *next)
  93 : f_parent (parent), f_previous (previous), f_next (next)
  94 {
  95   /* Modify previous and next links of previous and next */
  96   if (f_previous != NULL)
  97     f_previous->f_next = this;
  98   if (f_next != NULL)
  99     f_next->f_previous = this;
 100 }
 101
 102 PText::PText (PNode *parent, PNode *previous, PNode *next, char *str)
 103 : PNode (parent, previous, next)
 104 {
 105   if (str[1] == '?')
 106     f_empty = TRUE;
 107   else
 108     f_empty = FALSE;
 109
 110   f_symbol_len = strlen (str);
 111   if (f_symbol_len < 32)
 112     f_symbol_space = 32;
 113   else
 114     f_symbol_space = f_symbol_len;
 115
 116   int len = sizeof(char) * f_symbol_space;
 117   f_symbol = (char *) malloc (len + sizeof(char));
 118   *((char *) memcpy(f_symbol, str, len) + len) = '\0';
 119 }
 120
 121
 122 PString::PString (PNode *parent, PNode *previous, PNode *next, char *str)
 123 : PText (parent, previous, next, str)
 124 {
 125 }
 126
 127 PString::PString (char *str)
 128 : PText (NULL, NULL, NULL, str)
 129 { }
 130
 131 PNumber::PNumber (PNode *parent, PNode *previous, PNode *next, char *str)
 132 : PText (parent, previous, next, str)
 133 { }
 134
 135 PGroup::PGroup (PNode *parent, PNode *previous, PNode *next, PNode *subexpr)
 136 : PNode (parent, NULL, NULL),
 137   f_left (new PStart (this, previous, subexpr)),
 138   f_subexpr (subexpr),
 139   f_right (new PEnd (this, subexpr, next))
 140 {
 141   subexpr->f_parent = this;
 142 }
 143
 144 PRoot::PRoot (PNode *subexpr)
 145 : PGroup (NULL, NULL, NULL, subexpr), f_length (0)
 146 {
 147   f_space = 16;
 148   f_char_of = (char *) malloc (sizeof (char) * (f_space + 1));
 149   f_node_of_real = (PNode **) malloc (sizeof (PNode *) * (f_space + 2));
 150   f_node_of = f_node_of_real + 1;
 151 }
 152
 153 PPrefixOp::PPrefixOp (PNode *rhs)
 154 : PNode (rhs->f_parent, rhs->f_previous, rhs)
 155 {
 156   /* fix up the parent and previous of rhs */
 157   rhs->f_parent = this;
 158 }
 159
 160 PNot::PNot (PNode *rhs)
 161 : PPrefixOp (rhs)
 162 {
 163   f_operand = rhs;
 164 }
 165
 166 PBooleanOp::PBooleanOp ()
 167 : PNode (NULL, NULL, NULL)
 168 {}
 169
 170 // NOTE: clean up PNode constructors later (make NULL constructor, etc.)
 171 void
 172 PBooleanOp::init (PRoot *root, long pos)
 173 {
 174   PNode *lhs = root->f_node_of[pos-1];
 175   PNode *rhs = root->f_node_of[pos];
 176
 177   /* Expects eother lhs or rhs to be NULL, to indicate where to insert
 178      a blank string. */
 179   /* The new string will be on the lhs of the op and it's
 180      previous will become the previous of the existing rhs.
 181      Eg:
 182           previous-thing <cursor> rhs                <--- Before
 183           previous-thing new-lhs op <cursor> rhs     <--- After
 184
 185      The next of rhs does not change.  The next of the new-lhs
 186      and the previous of rhs will be set in the PNode constructor
 187      when the op is created.  The second case below is exactly
 188      opposite to this one, eg:
 189
 190           lhs <cursor> next-thing                <--- Before
 191           lhs op new-rhs <cursor> next-thing     <--- After
 192   */
 193
 194   // First check to see of right side is valid operand
 195   if (rhs->isa (PString::PStringClass))
 196     {
 197       // Create lhs string
 198       f_left = new PString (this, rhs->f_previous, this);
 199
 200       // Make rhs a child and fix next/previous pointers.
 201       f_next = rhs;
 202       rhs->f_previous = this;
 203
 204       // Become a child of the rhs' parent
 205       rhs->f_parent->replace_child (rhs, this);
 206
 207       // Make rhs a child of this
 208       rhs->f_parent = this;
 209       f_right = rhs;
 210     }
 211   // Now see if left side is valid operand
 212   else if (lhs->isa (PString::PStringClass))
 213     {
 214       // Create rhs string
 215       f_right = new PString (this, this, lhs->f_next);
 216
 217       // Make lhs a child and fix previous/next pointers.
 218       f_previous = lhs;
 219       lhs->f_next = this;
 220
 221       // Become a child of the lhs' parent
 222       lhs->f_parent->replace_child (lhs, this);
 223
 224       // Make the lhs a child of this
 225       lhs->f_parent = this;
 226       f_left = lhs;
 227     }
 228   else
 229     {
 230       puts ("ERROR: lhs and rhs both non NULL in Boolean Op constructor");
 231       abort ();
 232     }
 233
 234   /* -------- Handle precedence -------- */
 235
 236   while (f_parent->isa (PBooleanOp::PBooleanOpClass) &&
 237          (f_parent->precedence() > precedence()))
 238
 239     {
 240       // Reparent based on the side of parent this is on
 241       PBooleanOp *old_parent = (PBooleanOp *) f_parent;
 242       // My f_parent pointer changed by next function call
 243       old_parent->f_parent->replace_child (old_parent, this);
 244
 245       if (old_parent->f_left == this)
 246         {
 247           old_parent->replace_child (this, f_right);
 248           f_right = old_parent;
 249           old_parent->f_parent = this;
 250         }
 251       else if (old_parent->f_right == this)
 252         {
 253           old_parent->replace_child (this, f_left);
 254           f_left = old_parent;
 255           old_parent->f_parent = this;
 256         }
 257       else
 258         {
 259           puts ("ERROR: bogousity in precedence handling");
 260           abort ();
 261         }
 262     }
 263 }
 264
 265
 266 // /////////////////////////////////////////////////////////////////
 267 // Desctructors
 268 // /////////////////////////////////////////////////////////////////
 269
 270 PNode::~PNode ()
 271 {
 272   /* fix up next / previous links */
 273   if (f_previous)
 274     f_previous->f_next = f_next;
 275   if (f_next)
 276     f_next->f_previous = f_previous;
 277 }
 278
 279 PString::~PString ()
 280 {
 281   if (f_symbol)
 282     free (f_symbol);
 283 }
 284
 285 PGroup::~PGroup ()
 286 {
 287   delete f_left;
 288   delete f_right;
 289   if (f_recursive_delete)
 290     delete f_subexpr;
 291 }
 292
 293 PRoot::~PRoot ()
 294 {
 295   if (f_space > 0)
 296     {
 297       free ((char *) f_char_of);
 298       free ((char *) f_node_of_real);
 299     }
 300 }
 301
 302 PNot::~PNot ()
 303 {
 304   // Stick the child of not in not's parent (in not's slot)
 305   f_parent->replace_child (this, f_operand);
 306 }
 307
 308 void
 309 PNot::delete_self (delete_request_t request)
 310 {
 311   PNode *previous = f_previous;
 312   delete this;
 313   if (request == OBJECT_REQUEST)
 314     previous->delete_self (OBJECT_REQUEST);
 315 }
 316
 317 PText::~PText ()
 318 {
 319   // Don't let parent keep a pointer to me
 320   f_parent->replace_child (this, NULL);
 321 }
 322
 323
 324 // NOTE: need to add check for deleting first thing before a group.
 325 // NOTE: may need a way to return "failed"
 326 void
 327 PText::delete_self (delete_request_t request)
 328 {
 329   PNode *previous = f_previous;
 330   delete this;
 331   if (request == USER_REQUEST)
 332     previous->delete_self (OBJECT_REQUEST);
 333 }
 334
 335 void
 336 PBooleanOp::delete_self (delete_request_t request)
 337 {
 338   if (request == USER_REQUEST)
 339     f_previous->delete_self (OBJECT_REQUEST);
 340
 341   // Take this out of next/previous chain
 342   f_next->f_previous = f_previous;
 343   f_previous->f_next = f_next;
 344   // f_parent->replace_child (this, NULL);
 345
 346   /* When an operator is deleted part of the parse tree is split.
 347      To reconstruct the parse tree, the former left and right side
 348      must be merged.  */
 349
 350   // The first operator needing a child will be the parent of the
 351   // deleted operand.
 352
 353   // (Yes, operater is spelled wrong, but only because the correct spelling
 354   //  is a C++ reserved word...)
 355
 356   PNode  *operater, *operand;
 357
 358   /* -------- Figure out operand and operators. -------- */
 359
 360   if (f_left == NULL)
 361     operand = f_right;
 362   else if (f_right == NULL)
 363     operand = f_left;
 364   else
 365     {
 366       if (f_next->isa (PBooleanOp::PBooleanOpClass))
 367         {
 368           operater = f_next;
 369           // operand was on left of operater, find new operand
 370           operand = this->f_left;
 371           while (operand->isa (PBooleanOp::PBooleanOpClass))
 372             operand = ((PBooleanOp *) operand)->f_right;
 373         }
 374       else if (f_previous->isa (PBooleanOp::PBooleanOpClass))
 375         {
 376           operater = f_previous;
 377           // operand was on right of operater, find new operand
 378           operand = this->f_right;
 379           while (operand->isa (PBooleanOp::PBooleanOpClass))
 380             operand = ((PBooleanOp *) operand)->f_left;
 381         }
 382     }
 383
 384
 385   /* -------- Merge subtrees until only one tree remains -------- */
 386
 387   while (f_left != NULL && f_right != NULL)
 388     {
 389       // Now find enclosing subtree of operand based on precedence.
 390       // We can't move the operand to the operator if it is already
 391       // under an operator with higher precedence.
 392       while (operand->f_parent != this
 393              && operand->f_parent->precedence() >= operater->precedence())
 394         // Move up the tree
 395         operand = operand->f_parent;
 396
 397       // Now operand points to the subtree we can safely reparent
 398       PNode *old_parent = operand->f_parent;
 399
 400       // Empty the spot where the subtree was
 401       operand->f_parent->replace_child (operand, NULL);
 402
 403       // Replace hole in operator with this subtree
 404       operater->replace_child (NULL, operand);
 405
 406       // The new operand is the old operator...
 407       operand = operater->f_parent;
 408
 409       // and the new operator is the old operand because it just lost a subtree
 410       operater = old_parent;
 411     }
 412
 413   // Finally get rid of this
 414   if (f_left == NULL)
 415     f_parent->replace_child (this, f_right);
 416   else
 417     f_parent->replace_child (this, f_left);
 418   f_previous = f_next = NULL;
 419   delete this;
 420 }
 421
 422 // /////////////////////////////////////////////////////////////////
 423 // PText functions
 424 // /////////////////////////////////////////////////////////////////
 425
 426 void
 427 PText::insert_chars (int where, char *text, int length)
 428 {
 429   int new_len = f_symbol_len + length;
 430   f_empty = FALSE;
 431
 432   /* -------- allocate memory if necessary -------- */
 433   if (new_len > f_symbol_space)
 434     {
 435       // keep doubling until we have enough space
 436       while (new_len > f_symbol_space)
 437         f_symbol_space *= 2;
 438       // NOTE: check malloc result
 439       f_symbol = (char *) realloc ((char *) f_symbol,
 440                                    sizeof (char) * (f_symbol_space + 1));
 441     }
 442
 443   /* -------- make room for new stuff -------- */
 444   bcopy (&f_symbol[where],              // from
 445          &f_symbol[where+length],       // to
 446          f_symbol_len - where + 1);     // length
 447
 448   /* -------- insert new stuff -------- */
 449   bcopy (text, &f_symbol[where], length);
 450   f_symbol_len += length;
 451 }
 452
 453 void
 454 PText::remove_chars (int where, int len)
 455 {
 456   /* Just copy stuff after hole back over it. */
 457   bcopy (&f_symbol[where+len], &f_symbol[where],
 458          f_symbol_len - (where + len) + 1);
 459   f_symbol_len -= len;
 460   if (f_symbol_len == 2)  // ie: just two quotes
 461     f_empty = TRUE;
 462 }
 463
 464 // /////////////////////////////////////////////////////////////////
 465 // self insert code
 466 // /////////////////////////////////////////////////////////////////
 467
 468 #define LEFT_SIDE  (root->f_node_of[pos-1])
 469 #define RIGHT_SIDE (root->f_node_of[pos])
 470 #define LEFT_ISA(X) ((root->f_node_of[pos-1])->isa (X))
 471 #define RIGHT_ISA(X) ((root->f_node_of[pos])->isa (X))
 472
 473 void
 474 PNot::insert (PRoot *root, long pos)
 475 {
 476   puts ("Inserting a not");
 477   PNode *rhs = RIGHT_SIDE;
 478   PNot *not = new PNot (rhs);
 479   not->f_parent->replace_child (rhs, not);
 480 }
 481
 482 void
 483 POr::insert (PRoot *root, long pos)
 484 {
 485   new POr (root, pos);
 486 }
 487
 488 void
 489 PAnd::insert (PRoot *root, long pos)
 490 {
 491   new PAnd (root, pos);
 492 }
 493
 494 void
 495 PNear::insert (PRoot *root, long pos)
 496 {
 497   new PNear (root, pos);
 498 }
 499
 500 void
 501 PBefore::insert (PRoot *root, long pos)
 502 {
 503   new PBefore (root, pos);
 504 }
 505
 506 void
 507 PNode::insert (PRoot *, long)
 508 {
 509   puts ("Tried to insert something with no insert method.");
 510 }
 511
 512 // /////////////////////////////////////////////////////////////////
 513 // can_insert
 514 // /////////////////////////////////////////////////////////////////
 515
 516 bool
 517 PNode::can_insert (PRoot *, long)
 518 {
 519   return (FALSE);
 520 }
 521
 522 bool
 523 PBooleanOp::can_insert (PRoot *root, long pos)
 524 {
 525   /* If one side or the other is text, but not both, can do */
 526   if ((LEFT_ISA (PText::PTextClass) && !RIGHT_ISA (PText::PTextClass)) ||
 527       (!LEFT_ISA (PText::PTextClass) && RIGHT_ISA (PText::PTextClass)))
 528     return (TRUE);
 529   return (FALSE);
 530 }
 531
 532 bool
 533 PWeight::can_insert (PRoot *root, long pos)
 534 {
 535   return (FALSE);// tmp fix
 536   /* If left side is string and the right side isn't can do */
 537   if (LEFT_ISA (PString::PStringClass) &&
 538       !RIGHT_ISA (PText::PTextClass) &&
 539       !RIGHT_ISA (PWeight::PWeightClass))
 540     return (TRUE);
 541
 542   return (FALSE);
 543 }
 544
 545 bool
 546 PNot::can_insert (PRoot *root, long pos)
 547 {
 548   /* "not" insertable if rhs is a string and lhs isn't */
 549   if (LEFT_ISA (PText::PTextClass) || LEFT_ISA (PNot::PNotClass))
 550     return (FALSE);
 551   if (RIGHT_ISA (PString::PStringClass) || RIGHT_ISA (PStart::PStartClass))
 552     return (TRUE);
 553   return (FALSE);
 554 }
 555
 556 // /////////////////////////////////////////////////////////////////
 557 // replace child functions
 558 // /////////////////////////////////////////////////////////////////
 559
 560 void
 561 PBooleanOp::replace_child (PNode *old, PNode *replacement)
 562 {
 563   if (f_left == old)
 564     f_left = replacement;
 565   else if (f_right == old)
 566     f_right = replacement;
 567   else
 568     {
 569       puts ("ERROR: invalid old child passed to PBooleanOp::replace_child");
 570       abort ();
 571     }
 572   if (replacement != NULL)
 573     replacement->f_parent = this;
 574 }
 575
 576 // /////////////////////////////////////////////////////////////////
 577 // Other stuff
 578 // /////////////////////////////////////////////////////////////////
 579
 580 void
 581 PRoot::generate ()
 582 {
 583   PNode *p;
 584   static char *s;
 585   int pos = 0;
 586
 587   /* go through the list of displayable elements */
 588   for (p = f_left->f_next; p != f_right; p = p->f_next)
 589     {
 590       /* add the symbol for this element to the string */
 591       printf ("adding symbol: <%s>\n", p->symbol());
 592       for (s = p->symbol(); *s != '\0'; s++)
 593         {
 594           if (pos >= f_space)
 595             {
 596               f_space *= 2;
 597               f_char_of = (char *)
 598                 realloc ((char *) f_char_of, sizeof(char) * (f_space + 1));
 599               f_node_of_real = (PNode **)
 600                 realloc ((char *) f_node_of_real,
 601                          sizeof(PNode *) * (f_space + 2));
 602               f_node_of = f_node_of_real + 1;
 603             }
 604           f_char_of[pos] = *s;
 605           f_node_of[pos] = p;
 606           pos++;
 607         }
 608     }
 609   /* fill in boundries */
 610   f_char_of[pos] = '\0';
 611   f_node_of[-1] = f_left;
 612   f_node_of[pos] = f_right;
 613   f_old_length = f_length;
 614   f_length = pos;
 615   // ON_DEBUG (printf ("Generated: <%s>\n", f_char_of);)
 616 }