cde/programs/dtinfo/DtMmdb/StyleSheet/PathTable.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 // $XConsortium: PathTable.cc /main/4 1996/06/11 17:07:57 cde-hal $
  24 #include "PathTable.h"
  25 #include "Debug.h"
  26 #include "Feature.h"
  27 #include "utility/debug.h"
  28
  29 extern SymbolTable* gElemSymTab;
  30
  31 unsigned int letterHash(const LetterType& x)
  32 {
  33    return x;
  34 }
  35
  36 EncodedPath::~EncodedPath()
  37 {
  38   delete [] f_array ;
  39   f_SVectors.clearAndDestroy();
  40   delete f_copyOfS;
  41 }
  42
  43 EncodedPath::EncodedPath(SSPath* p, unsigned int asPattern) :
  44    f_size(p -> entries()), f_patternSize(0), f_SVectors(letterHash),
  45    f_wildCard(gElemSymTab -> wildCardId()),
  46    f_unlimitedWildCard(gElemSymTab -> unlimitedWildCardId()),
  47    f_copyOfS(new BitVector(WORD_SIZE, 0))
  48 {
  49
  50     f_array = new LetterType[f_size];
  51
  52     CC_TPtrDlistIterator<PathTerm> l_pathIter(*p);
  53
  54     BitVector *l_bv = 0;
  55
  56     int i = 0;
  57
  58     while (++l_pathIter) {
  59
  60 //
  61 // Count pattern size, excluding "*".
  62 //
  63       f_array[i] = (LetterType)((l_pathIter.key() -> symbol()).id());
  64       if ( f_array[i] != f_unlimitedWildCard )
  65          f_patternSize++;
  66       i++;
  67     }
  68
  69     if ( asPattern == true ) {
  70
  71 //
  72 // Compute the S arrays.
  73 // Examples  pat = a b a c
  74 //           S(a) = 1 0 1 0
  75 //           S(b) = 0 0 0 0
  76 //           S(c) = 0 0 0 1
  77 //
  78 //           pat = a ? a c
  79 //           S(a) = 1 1 1 0
  80 //           S(c) = 0 1 0 1
  81 //           S(?) = 0 1 0 0
  82 //
  83 //           pat = a * a c
  84 //           S(a) = 1 1 0
  85 //           S(c) = 0 0 1
  86 //           S(*) = 1 0 0
  87 //
  88        l_pathIter.reset();
  89        int j = patternLength()-1;
  90
  91        LetterType l_id;
  92
  93 // i records each PathTerm position in the list
  94        int i=0;
  95
  96        while (++l_pathIter) {
  97          l_id = (LetterType)((l_pathIter.key() -> symbol()).id());
  98
  99          l_bv = f_SVectors.findValue(&l_id);
 100          if ( l_bv == 0 ) {
 101             l_bv = new BitVector(patternLength(), 0);
 102             f_SVectors.insertKeyAndValue(new LetterType(l_id), l_bv);
 103          }
 104
 105
 106 ///////////////////////////////////////////////////
 107 // reverse the order in the bit vector:
 108 //  MSB position ==> set LSB bit in the bit vector
 109 ///////////////////////////////////////////////////
 110          if ( l_id != f_unlimitedWildCard ) {
 111             l_bv -> setBitTo(j, 1);
 112
 113 //////////////////////////////////////////////////
 114 // only set position when an expr is attatched
 115 // to the term
 116 //////////////////////////////////////////////////
 117             if ( l_pathIter.key() -> pqexpr() && l_id != f_wildCard ) {
 118 /*
 119 MESSAGE(cerr, "==========");
 120 debug(cerr, (void*)l_bv);
 121 debug(cerr, *l_bv);
 122 debug(cerr, i);
 123 debug(cerr, j);
 124 */
 125                l_bv -> recordPositions(i, j);
 126
 127             }
 128
 129             j--;
 130
 131          } else {
 132 ///////////////////////////////////////////////////
 133 // do not set bits for unlimitedWildCards that
 134 // begin or end the pattern
 135 ///////////////////////////////////////////////////
 136             if ( j < patternLength() - 1 )
 137                l_bv -> setBitTo(j+1, 1);
 138          }
 139          i++;
 140       }
 141
 142
 143 ///////////////////////////////////////////////////
 144 // special treatment to the ? symbols:
 145 // OR S(?) back to each S's.
 146 ///////////////////////////////////////////////////
 147        BitVector* l_BitVectorWildCard = f_SVectors.findValue(&f_wildCard);
 148        hashTableIterator<LetterType, BitVector> l_SVIter(f_SVectors);
 149
 150        if ( l_BitVectorWildCard ) {
 151           while (++l_SVIter) {
 152              if ( *l_SVIter.key() != f_wildCard &&
 153                   *l_SVIter.key() != f_unlimitedWildCard
 154                 )
 155              {
 156                 (*l_SVIter.value()) |= (*l_BitVectorWildCard);
 157              }
 158           }
 159        }
 160 /*
 161 #ifdef DEBUG
 162        l_SVIter.reset();
 163        while (++l_SVIter) {
 164           debug(cerr, (*l_SVIter.key()));
 165           debug(cerr, (*l_SVIter.value()));
 166        }
 167 #endif
 168 */
 169     }
 170 }
 171
 172
 173
 174 unsigned int
 175 _match(LetterType* pattern, int n,
 176        LetterType* text, int m,
 177        LetterType wildCard,
 178        LetterType unlimitedWildCard
 179        )
 180 {
 181 // A naive (brute force) string matching algorithm that handles
 182 // wild card (?) and unlimited wild card (*) symbols.
 183    unsigned int findMisMatch = false;
 184
 185    for ( int i=0; i<n; i++ ) {  // over the "text" string
 186
 187       for ( int j=0; j<m; j++ ) {    // over the pattern
 188          if ( pattern[j] == wildCard ) {
 189             continue;
 190          } else
 191          if ( pattern[j] == unlimitedWildCard ) {
 192
 193              for (;;) {
 194
 195                j++;
 196
 197                if ( j == m )
 198                  return true;
 199
 200                if ( pattern[j] != unlimitedWildCard )
 201                  break;
 202              }
 203
 204              for ( int x=i+1; x<n; x++ ) {
 205                 if ( text[x] == pattern[j] )
 206                    if (
 207                    _match(
 208                         &pattern[j], m-j,
 209                         &text[x], n-x,
 210                         wildCard, unlimitedWildCard
 211                          ) == true
 212                       )
 213                       return true;
 214
 215              }
 216
 217          } else {
 218             if ( pattern[j] != text[i] ) {
 219                findMisMatch = true;
 220                break;
 221             }
 222          }
 223       }
 224       if ( findMisMatch == false )
 225          return true;
 226    }
 227    return false;
 228 }
 229
 230
 231 unsigned int
 232 EncodedPath::match(EncodedPath& text, SSPath* patternPath, SSPath* elementPath)
 233 {
 234 ////////////////////////////////////////////////
 235 // text: the encoded string for the element path
 236 // elementPath: the element path
 237 //
 238 // this: the encoded string for the pattern string
 239 // patternPath: the pattern path
 240 ////////////////////////////////////////////////
 241
 242
 243 ////////////////////////////////////////////////
 244 // the unlimited wildcard vector
 245 ////////////////////////////////////////////////
 246    BitVector* l_U = f_SVectors.findValue(&f_unlimitedWildCard);
 247
 248    if ( l_U && patternLength() == 0 )
 249      return true;
 250
 251 ////////////////////////////////////////////////
 252 // the wildcard vector
 253 ////////////////////////////////////////////////
 254    BitVector* l_W = f_SVectors.findValue(&f_wildCard);
 255
 256 // the S vector of each Letter, including that for '?'
 257    BitVector* l_S = 0;
 258
 259 // the accumulated result vector
 260    BitVector l_R(patternLength(), 0);
 261
 262 // placeholder for '*''s contribution
 263    BitVector l_I(patternLength(), 0);
 264
 265 // hole position record of each path term in the pattern path
 266    posRecord l_pr;
 267
 268 // expr pointer of each path term in the pattern path
 269    PQExpr* expr = 0;
 270
 271    CC_TPtrDlistIterator<PathTerm>* elementPathNextPtr = 0;
 272
 273    if ( elementPath )
 274       elementPathNextPtr = new CC_TPtrDlistIterator<PathTerm>(*elementPath);
 275
 276 // loop over text string
 277    for ( int i=0; i<text.length(); i++) {
 278
 279       if ( elementPath )
 280           ++(*elementPathNextPtr);
 281
 282         //MESSAGE(cerr, "===================");
 283         //debug(cerr, text.f_array[i]);
 284
 285 ////////////////////////////////////////////////
 286 // get this character's vector, including '?'s
 287 ////////////////////////////////////////////////
 288       l_S = f_SVectors.findValue(&text.f_array[i]);
 289
 290       if ( l_S ) {
 291         //debug(cerr, (void*)l_S);
 292         //debug(cerr, *l_S);
 293         //MESSAGE(cerr, "checking qualifies");
 294 //////////////////////
 295 // check qualifies.
 296 //////////////////////
 297          if ( patternPath && l_S -> positionArray() ) {
 298
 299 ////////////////////
 300 // get a copy of S
 301 ////////////////////
 302             f_copyOfS -> setTo(*l_S);
 303
 304             //debug(cerr, *patternPath);
 305
 306             positionArrayIteratorT l_positionNext(*(l_S -> positionArray()));
 307             while (++ l_positionNext) {
 308
 309                l_pr = l_positionNext.key();
 310
 311 //cerr <<  " calling patternPath -> fastGetAt():  " << (void*)patternPath << "l_pr.pathTermPos= " << l_pr.pathTermPos << endl;
 312
 313                expr = patternPath -> fastGetAt(l_pr.pathTermPos) -> pqexpr();
 314 /*
 315 debug(cerr, int(expr));
 316 if ( expr ) {
 317    MESSAGE(cerr, "qualify checking is needed.");
 318    debug(cerr, *(elementPathNext -> key()));
 319 }
 320 */
 321
 322                if ( expr &&
 323                     expr->evaluate(elementPathNextPtr->key()->element()) == PQFalse )
 324                {
 325                   //MESSAGE(cerr, form("set position %d to 0", l_pr.bitPos));
 326                   f_copyOfS -> setBitTo(l_pr.bitPos, 0);
 327                }
 328             }
 329 /////////////////////////////////////////
 330 // make l_S point at its modified copy
 331 /////////////////////////////////////////
 332             l_S = f_copyOfS;
 333          }
 334       } else
 335          l_S = l_W;
 336
 337 ////////////////////////////////////////////////
 338 // get unlimited wildcard's vector.
 339 ////////////////////////////////////////////////
 340       if ( l_U ) {
 341          l_I.setTo(l_R);
 342          l_I &= (*l_U);
 343          //MESSAGE(cerr, "l_I");
 344          //debug(cerr, l_I);
 345
 346       }
 347
 348 ////////////////////////////////////////////////
 349 // shift the partial result vector right once
 350 ////////////////////////////////////////////////
 351       l_R.shiftRightOneBit();
 352       //MESSAGE(cerr, "after l_R >> 1");
 353       //debug(cerr, l_R);
 354
 355 ////////////////////////////////////////////////
 356 // AND in this character's vector
 357 ////////////////////////////////////////////////
 358       if ( l_S ) {
 359          l_R &= (*l_S);
 360          //debug(cerr, *l_S);
 361          //MESSAGE(cerr, "after AND with l_S");
 362          //debug(cerr, l_R);
 363       } else {
 364 ///////////////////////////////////////////////
 365 // this branch is impossible to reach.
 366 ///////////////////////////////////////////////
 367          //MESSAGE(cerr, "l_R set all bits to 0");
 368          l_R.setAllBitsTo(0);
 369       }
 370
 371
 372 ///////////////////////////////////////////////
 373 // OR in unlimited wild char's vector.
 374 ///////////////////////////////////////////////
 375       if ( l_U ) {
 376          l_R |= l_I;
 377          //MESSAGE(cerr, "after OR with l_I");
 378          //debug(cerr, l_R);
 379       }
 380          //debug(cerr, l_R);
 381          //MESSAGE(cerr, "===================");
 382
 383 ///////////////////////////////////////////////
 384 // Use this test to get the first matched position
 385 //  if ( l_R.getBit(0) == 1 )
 386 //    return true;
 387 ///////////////////////////////////////////////
 388
 389    }
 390    delete elementPathNextPtr;
 391
 392 ///////////////////////////////////////////////
 393 //
 394 // the last symbol must match
 395 //
 396 ///////////////////////////////////////////////
 397    if ( l_R.getBit(0) == 1 )
 398       return true;
 399    else
 400       return false;
 401
 402 }
 403
 404 basePathFeature::~basePathFeature()
 405 {
 406    delete f_path;
 407    delete f_featureSet;
 408 }
 409
 410 PathFeature::~PathFeature()
 411 {
 412   delete f_encodedPath ;
 413 }
 414
 415 unsigned int basePathFeature::operator==(const basePathFeature& pf) const
 416 {
 417    cerr << "Warning: basePathFeature::operator==() called\n";
 418    return true;
 419 }
 420
 421 unsigned int PathFeature::operator==(const PathFeature& pf) const
 422 {
 423    cerr << "Warning: PathFeature::operator==() called\n";
 424    return true;
 425 }
 426
 427 void pathSelector(BitVector& bv)
 428 {
 429 }
 430
 431 unsigned int
 432 PathFeature::match(SSPath& p)
 433 {
 434    EncodedPath l_ep(&p);
 435
 436   if ( f_path -> containSelector() == false )
 437     return f_encodedPath -> match(l_ep, 0, 0);
 438   else
 439     return f_encodedPath -> match(l_ep, f_path, &p);
 440 }
 441
 442
 443 // /////////////////////////////////////////////////////////////////////////
 444 //
 445 //      class PathTable
 446 //
 447 // /////////////////////////////////////////////////////////////////////////
 448
 449
 450 unsigned symHashFunc(const Symbol& s)
 451 {
 452    return s.hash();
 453 }
 454
 455 PathTable::PathTable()
 456 : f_lastSymIndex(0),
 457   f_lastSymIndexCount(0)
 458 {
 459 }
 460
 461 PathTable::~PathTable()
 462 {
 463   f_pathFeatureList.clearAndDestroy();
 464   for (unsigned int i = 0 ; i < f_lastSymIndexCount; i++) {
 465     //f_lastSymIndex[i].clearAndDestroy();
 466     f_lastSymIndex[i] -> clear();
 467     delete f_lastSymIndex[i];
 468    }
 469    delete f_lastSymIndex;
 470 }
 471
 472 LetterType PathTable::findIndex(SSPath& p)
 473 {
 474   return (LetterType) ((p.last() -> symbol()).id());
 475 }
 476
 477 void PathTable::initLastSymIndex()
 478 {
 479    f_lastSymIndexCount = gElemSymTab -> IdsAssigned()+1;
 480    f_lastSymIndex = new CC_TPtrDlist_PathFeature_Ptr_T[f_lastSymIndexCount];
 481    for (unsigned int i=0; i<f_lastSymIndexCount; i++)
 482       f_lastSymIndex[i] = new CC_TPtrDlist<PathFeature>;
 483
 484
 485    CC_TPtrDlistIterator<PathFeature> l_pfIter(f_pathFeatureList);
 486    PathFeature* l_pathFeature = 0;
 487
 488    LetterType x;
 489
 490    while ( ++l_pfIter ) {
 491       l_pathFeature = l_pfIter.key();
 492       x = findIndex( *(l_pathFeature->path()) );
 493       //f_lastSymIndex[x] -> prepend(l_pathFeature); // backward order
 494       f_lastSymIndex[x] -> append(l_pathFeature); // select the matching rule
 495                                                   // in the same order rules
 496                                                   // appear in the
 497                                                   // stylesheet
 498    }
 499 }
 500
 501 FeatureSet* PathTable::getFeatureSet(SSPath& p)
 502 {
 503    if ( f_lastSymIndex == 0 ) {
 504      initLastSymIndex();
 505    }
 506
 507    int pids[3];
 508    FeatureSet* fs[3];
 509
 510    fs[0] = getFeatureSet(findIndex(p), p, pids[0]);
 511    fs[1] = getFeatureSet(gElemSymTab -> wildCardId(), p, pids[1]);
 512    fs[2] = getFeatureSet(gElemSymTab -> unlimitedWildCardId(), p, pids[2]);
 513
 514    int index = 0;
 515    int x = pids[0];
 516
 517    for ( int i=1; i<3; i++ ) {
 518      if ( pids[i] > x )
 519        index = i;
 520    }
 521
 522    return fs[index];
 523 }
 524
 525 FeatureSet*
 526 PathTable::getFeatureSet(int bucketIndex, SSPath& p, int& pathId)
 527 {
 528    CC_TPtrDlistIterator<PathFeature> l_pathFeatureIter(*f_lastSymIndex[bucketIndex]);
 529
 530    l_pathFeatureIter.reset();
 531
 532    PathFeature* l_pathFeature = 0;
 533
 534    while ( ++l_pathFeatureIter ) {
 535
 536       l_pathFeature = l_pathFeatureIter.key();
 537
 538 //debug(cerr, *(l_pathFeature->path()));
 539 //debug(cerr, *(l_pathFeature->featureSet()));
 540
 541       if ( l_pathFeature -> match(p) ) {
 542 //MESSAGE(cerr, "match");
 543          pathId = l_pathFeature -> id();
 544          return l_pathFeature -> featureSet();
 545       }
 546    }
 547
 548    pathId = 0;
 549    return 0;
 550 }
 551
 552 void PathTable::addPathFeatureSet(PathFeature* x)
 553 {
 554 //MESSAGE(cerr, "addPathFeatureSet():");
 555 //debug(cerr, *(x->path()));
 556 //debug(cerr, *(x->featureSet()));
 557
 558    if ( x -> path() -> containSelector() )
 559       x -> path() -> fastGetIndex();
 560
 561    EncodedPath* l_epath = new EncodedPath(x -> path(), true);
 562    unsigned int id = f_pathFeatureList.entries()+1;
 563
 564    x -> setEncodedPath(l_epath);
 565    x -> setID(id);
 566
 567    f_pathFeatureList.insert(x);
 568
 569 }
 570
 571 ostream& operator<<(ostream& out, PathTable& pt)
 572 {
 573    CC_TPtrDlistIterator<PathFeature> l_pfIter(pt.f_pathFeatureList);
 574    PathFeature* l_pathFeature = 0;
 575
 576    while ( ++l_pfIter ) {
 577       l_pathFeature = l_pfIter.key();
 578
 579       out << *(l_pathFeature)->path() << ' ' << *(l_pathFeature->featureSet())
 580           << endl;
 581
 582 #ifdef DEBUG
 583       // this will cause errors if gTopOfStack is not set properly
 584       FeatureSet *set = l_pathFeature->featureSet()->evaluate();
 585       out << *set << endl;
 586       delete set ;
 587 #endif
 588    }
 589
 590
 591    return out;
 592 }
 593
 594 void PathFeatureList::appendList(PathFeatureList& list)
 595 {
 596    PathFeatureListIterator l_Iter(list);
 597    while ( ++ l_Iter ) {
 598       append(l_Iter.key());
 599    }
 600 }
 601
 602 PathFeatureList::~PathFeatureList()
 603 {
 604   clearAndDestroy();
 605 }