cde/programs/nsgmls/ContentToken.h

   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 libraries 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: ContentToken.h /main/1 1996/07/29 16:48:40 cde-hp $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #ifndef ContentToken_INCLUDED
  28 #define ContentToken_INCLUDED 1
  29 #ifdef __GNUG__
  30 #pragma interface
  31 #endif
  32
  33 #include "Owner.h"
  34 #include "Text.h"
  35 #include "Vector.h"
  36 #include "NCVector.h"
  37 #include "Boolean.h"
  38
  39 #ifdef SP_NAMESPACE
  40 namespace SP_NAMESPACE {
  41 #endif
  42
  43 class LeafContentToken;
  44
  45 struct SP_API Transition {
  46   Transition() { }
  47   ~Transition() { }
  48   enum { invalidIndex = -1 };
  49   // When performing this transition, reset all andState with index >= this.
  50   unsigned clearAndStateStartIndex;
  51   // This transition is possible only if all AND groups whose AND depth
  52   // is >= this (and contains the LeafContentToken that this transition is
  53   // from) have had all their non-nullable members matched.
  54   unsigned andDepth;
  55   // If this is 1, then this transition requires that the AND group
  56   // whose AND depth is andDepth - 1 have a non-nullable member unmatched,
  57   // and thus this transition is not ambiguous with a transition whose
  58   // AND depth is < andDepth.
  59   PackedBoolean isolated;
  60   // Index in andState that must be clear for this transition to be
  61   // allowed.
  62   unsigned requireClear;
  63   // Index in andState that is to be set after performing this transition.
  64   unsigned toSet;
  65 };
  66
  67 class SP_API FirstSet {
  68 public:
  69   FirstSet();
  70   void init(LeafContentToken *);
  71   void append(const FirstSet &);
  72   size_t size() const;
  73   LeafContentToken *token(size_t i) const;
  74   size_t requiredIndex() const;
  75   void setNotRequired();
  76 private:
  77   Vector<LeafContentToken *> v_;
  78   // index of contextually required token or -1 if none
  79   size_t requiredIndex_;
  80 };
  81
  82 class SP_API LastSet : public Vector<LeafContentToken *> {
  83 public:
  84   LastSet() { }
  85   LastSet(size_t n) : Vector<LeafContentToken *>(n) { }
  86   void append(const LastSet &);
  87 };
  88
  89 class ElementType;
  90 class AndModelGroup;
  91 struct GroupInfo;
  92
  93 struct SP_API ContentModelAmbiguity {
  94   ContentModelAmbiguity () { }
  95   ~ContentModelAmbiguity () { }
  96   const LeafContentToken *from;
  97   const LeafContentToken *to1;
  98   const LeafContentToken *to2;
  99   unsigned andDepth;
 100 };
 101
 102 class ModelGroup;
 103
 104 class SP_API ContentToken {
 105 public:
 106   enum OccurrenceIndicator { none = 0, opt = 01, plus = 02, rep = 03 };
 107   ContentToken(OccurrenceIndicator);
 108   virtual ~ContentToken();
 109   OccurrenceIndicator occurrenceIndicator() const;
 110   Boolean inherentlyOptional() const;
 111   static unsigned andDepth(const AndModelGroup *);
 112   static unsigned andIndex(const AndModelGroup *);
 113   void analyze(GroupInfo &, const AndModelGroup *, unsigned,
 114                FirstSet &, LastSet &);
 115   static void addTransitions(const LastSet &from,
 116                              const FirstSet &to,
 117                              Boolean maybeRequired,
 118                              unsigned andClearIndex,
 119                              unsigned andDepth,
 120                              Boolean isolated = 0,
 121                              unsigned requireClear
 122                                = (unsigned)Transition::invalidIndex,
 123                              unsigned toSet
 124                                = (unsigned)Transition::invalidIndex);
 125   virtual void finish(Vector<unsigned> &minAndDepth,
 126                       Vector<size_t> &elementTransition,
 127                       Vector<ContentModelAmbiguity> &,
 128                       Boolean &pcdataUnreachable) = 0;
 129   virtual unsigned long grpgtcnt() const;
 130   virtual void setOrGroupMember();
 131   unsigned andGroupIndex() const;
 132   virtual const ModelGroup *asModelGroup() const;
 133   virtual const LeafContentToken *asLeafContentToken() const;
 134 protected:
 135   PackedBoolean inherentlyOptional_;
 136 private:
 137   ContentToken(const ContentToken &); // undefined
 138   void operator=(const ContentToken &); // undefined
 139   virtual void analyze1(GroupInfo &, const AndModelGroup *, unsigned,
 140                         FirstSet &, LastSet &) = 0;
 141   OccurrenceIndicator occurrenceIndicator_;
 142 };
 143
 144 class SP_API ModelGroup : public ContentToken {
 145 public:
 146   enum Connector { andConnector, orConnector, seqConnector };
 147   ModelGroup(NCVector<Owner<ContentToken> > &, OccurrenceIndicator);
 148   virtual Connector connector() const = 0;
 149   unsigned nMembers() const;
 150   void finish(Vector<unsigned> &minAndDepth,
 151               Vector<size_t> &elementTransition,
 152               Vector<ContentModelAmbiguity> &,
 153               Boolean &pcdataUnreachable);
 154   ContentToken &member(unsigned i);
 155   const ContentToken &member(unsigned i) const;
 156   unsigned long grpgtcnt() const;
 157   const ModelGroup *asModelGroup() const;
 158 protected:
 159   void setOrGroup();
 160 private:
 161   ModelGroup(const ModelGroup &); // undefined
 162   void operator=(const ModelGroup &); // undefined
 163   NCVector<Owner<ContentToken> > members_;
 164 };
 165
 166 class AndModelGroup : public ModelGroup {
 167 public:
 168   AndModelGroup(NCVector<Owner<ContentToken> > &, OccurrenceIndicator);
 169   Connector connector() const;
 170   unsigned andDepth() const;
 171   unsigned andIndex() const;
 172   unsigned andGroupIndex() const;
 173   const AndModelGroup *andAncestor() const;
 174 private:
 175   AndModelGroup(const AndModelGroup &); // undefined
 176   void operator=(const AndModelGroup &); // undefined
 177   unsigned andDepth_;           // number of and groups that contain this
 178   unsigned andIndex_;
 179   unsigned andGroupIndex_;
 180   const AndModelGroup *andAncestor_;
 181   void analyze1(GroupInfo &, const AndModelGroup *, unsigned,
 182                 FirstSet &, LastSet &);
 183 };
 184
 185 class OrModelGroup : public ModelGroup {
 186 public:
 187   OrModelGroup(NCVector<Owner<ContentToken> > &, OccurrenceIndicator);
 188   Connector connector() const;
 189 private:
 190   OrModelGroup(const OrModelGroup &); // undefined
 191   void operator=(const OrModelGroup &); // undefined
 192   void analyze1(GroupInfo &, const AndModelGroup *, unsigned,
 193                 FirstSet &, LastSet &);
 194 };
 195
 196 class SeqModelGroup : public ModelGroup {
 197 public:
 198   SeqModelGroup(NCVector<Owner<ContentToken> > &, OccurrenceIndicator);
 199   Connector connector() const;
 200 private:
 201   SeqModelGroup(const SeqModelGroup &); // undefined
 202   void operator=(const SeqModelGroup &); // undefined
 203   void analyze1(GroupInfo &, const AndModelGroup *, unsigned,
 204                 FirstSet &, LastSet &);
 205 };
 206
 207 class AndState;
 208
 209 class SP_API AndInfo {
 210 public:
 211   AndInfo() : andAncestor(NULL), andGroupIndex(0) { }
 212   const AndModelGroup *andAncestor;
 213   unsigned andGroupIndex;
 214   Vector<Transition> follow;
 215 private:
 216   AndInfo(const AndInfo &);     // undefined
 217   void operator=(const AndInfo &); // undefined
 218 };
 219
 220 // A LeafContentToken is not quite the same as a primitive content token.
 221 // A data tag group is a primitive content token but not a LeafContentToken.
 222
 223 class SP_API LeafContentToken : public ContentToken {
 224 public:
 225   LeafContentToken(const ElementType *, OccurrenceIndicator);
 226   unsigned index() const;
 227   unsigned typeIndex() const;
 228   const ElementType *elementType() const;
 229   virtual Boolean isInitial() const;
 230   void addTransitions(const FirstSet &to,
 231                       Boolean maybeRequired,
 232                       unsigned andClearIndex,
 233                       unsigned andDepth,
 234                       Boolean isolated,
 235                       unsigned requireClear,
 236                       unsigned toSet);
 237   void setFinal();
 238   void finish(Vector<unsigned> &minAndDepth,
 239               Vector<size_t> &elementTransition,
 240               Vector<ContentModelAmbiguity> &,
 241               Boolean &pcdataUnreachable);
 242   Boolean isFinal() const;
 243   Boolean tryTransition(const ElementType *, AndState &,
 244                         unsigned &minAndDepth,
 245                         const LeafContentToken *&newpos) const;
 246   Boolean tryTransitionPcdata(AndState &, unsigned &minAndDepth,
 247                               const LeafContentToken *&newpos) const;
 248   void possibleTransitions(const AndState &, unsigned minAndDepth, Vector<const ElementType *> &) const;
 249   const LeafContentToken *impliedStartTag(const AndState &andpos,
 250                                           unsigned minAndDepth) const;
 251   const LeafContentToken *transitionToken(const ElementType *to,
 252                                           const AndState &andState,
 253                                           unsigned minAndDepth) const;
 254   void doRequiredTransition(AndState &andState,
 255                             unsigned &minAndDepth,
 256                             const LeafContentToken *&newpos) const;
 257   unsigned computeMinAndDepth(const AndState&) const;
 258   Boolean orGroupMember() const;
 259   void setOrGroupMember();
 260   const AndModelGroup *andAncestor() const;
 261   unsigned andDepth() const;
 262   const LeafContentToken *asLeafContentToken() const;
 263 protected:
 264   void analyze1(GroupInfo &, const AndModelGroup *, unsigned,
 265                 FirstSet &, LastSet &);
 266   const ElementType *element_;
 267 private:
 268   LeafContentToken(const LeafContentToken &); // undefined
 269   void operator=(const LeafContentToken &);   // undefined
 270   void andFinish(Vector<unsigned> &minAndDepth,
 271                  Vector<size_t> &elementTransition,
 272                  Vector<ContentModelAmbiguity> &,
 273                  Boolean &pcdataUnreachable);
 274   unsigned computeMinAndDepth1(const AndState&) const;
 275   unsigned leafIndex_;
 276   unsigned typeIndex_;
 277   Vector<LeafContentToken *> follow_;
 278   PackedBoolean isFinal_;
 279   PackedBoolean orGroupMember_;
 280   // 0 none, 1 yes - simple, 2 - compled
 281   char pcdataTransitionType_;
 282   const LeafContentToken *simplePcdataTransition_;
 283   size_t requiredIndex_;
 284   Owner<AndInfo> andInfo_;
 285 };
 286
 287 class PcdataToken : public LeafContentToken {
 288 public:
 289   PcdataToken();
 290   void analyze1(GroupInfo &, const AndModelGroup *, unsigned,
 291                 FirstSet &, LastSet &);
 292 private:
 293   PcdataToken(const PcdataToken &); // undefined
 294   void operator=(const PcdataToken &); // undefined
 295 };
 296
 297 class InitialPseudoToken : public LeafContentToken {
 298 public:
 299   InitialPseudoToken();
 300   Boolean isInitial() const;
 301 private:
 302   InitialPseudoToken(const InitialPseudoToken &); // undefined
 303   void operator=(const InitialPseudoToken &); // undefined
 304 };
 305
 306 class ElementToken : public LeafContentToken {
 307 public:
 308   ElementToken(const ElementType *, OccurrenceIndicator);
 309 private:
 310   ElementToken(const ElementToken &); // undefined
 311   void operator=(const ElementToken &); // undefined
 312 };
 313
 314 class DataTagGroup : public SeqModelGroup {
 315 public:
 316   // first content token is a DataTagElementToken, second is PcdataToken
 317   DataTagGroup(NCVector<Owner<ContentToken> > &, OccurrenceIndicator);
 318 private:
 319   DataTagGroup(const DataTagGroup &); // undefined
 320   void operator=(const DataTagGroup &); // undefined
 321 };
 322
 323 class DataTagElementToken : public ElementToken {
 324 public:
 325   DataTagElementToken(const ElementType *, Vector<Text> &templates);
 326   DataTagElementToken(const ElementType *, Vector<Text> &templates,
 327                       Text &paddingTemplate);
 328 private:
 329   DataTagElementToken(const DataTagElementToken &); // undefined
 330   void operator=(const DataTagElementToken &); // undefined
 331   Vector<Text> templates_;
 332   Boolean havePaddingTemplate_;
 333   Text paddingTemplate_;
 334 };
 335
 336 class SP_API CompiledModelGroup {
 337 public:
 338   CompiledModelGroup(Owner<ModelGroup> &);
 339   void compile(size_t nElementTypeIndex,
 340                Vector<ContentModelAmbiguity> &,
 341                Boolean &pcdataUnreachable);
 342   CompiledModelGroup *copy() const;
 343   const LeafContentToken *initial() const;
 344   unsigned andStateSize() const;
 345   Boolean containsPcdata() const;
 346   const ModelGroup *modelGroup() const;
 347 private:
 348   CompiledModelGroup(const CompiledModelGroup &); // undefined
 349   void operator=(const CompiledModelGroup &);     // undefined
 350   Owner<ModelGroup> modelGroup_;
 351   Owner<LeafContentToken> initial_;
 352   unsigned andStateSize_;
 353   Boolean containsPcdata_;
 354 };
 355
 356 class SP_API AndState {
 357 public:
 358   AndState(unsigned);
 359   Boolean isClear(unsigned) const;
 360   void clearFrom(unsigned);
 361   void set(unsigned);
 362   Boolean operator==(const AndState &) const;
 363   Boolean operator!=(const AndState &) const;
 364 private:
 365   void clearFrom1(unsigned);
 366   unsigned clearFrom_;
 367   Vector<PackedBoolean> v_;
 368 };
 369
 370 class SP_API MatchState {
 371 public:
 372   MatchState();
 373   MatchState(const CompiledModelGroup *); // may be 0
 374   Boolean tryTransition(const ElementType *);
 375   Boolean tryTransitionPcdata();
 376   void possibleTransitions(Vector<const ElementType *> &) const;
 377   Boolean isFinished() const;
 378   const LeafContentToken *impliedStartTag() const;
 379   const LeafContentToken *invalidExclusion(const ElementType *) const;
 380   void doRequiredTransition();
 381   const LeafContentToken *currentPosition() const;
 382   Boolean operator==(const MatchState &) const;
 383   Boolean operator!=(const MatchState &) const;
 384 private:
 385   const LeafContentToken *pos_;
 386   AndState andState_;
 387   unsigned minAndDepth_;
 388 };
 389
 390 inline
 391 ContentToken::OccurrenceIndicator ContentToken::occurrenceIndicator() const
 392 {
 393   return occurrenceIndicator_;
 394 }
 395
 396 inline
 397 unsigned LeafContentToken::index() const
 398 {
 399   return leafIndex_;
 400 }
 401
 402 inline
 403 unsigned LeafContentToken::typeIndex() const
 404 {
 405   return typeIndex_;
 406 }
 407
 408 inline
 409 Boolean ContentToken::inherentlyOptional() const
 410 {
 411   return inherentlyOptional_;
 412 }
 413
 414 inline
 415 const ElementType *LeafContentToken::elementType() const
 416 {
 417   return element_;
 418 }
 419
 420 inline
 421 unsigned AndModelGroup::andDepth() const
 422 {
 423   return andDepth_;
 424 }
 425
 426 inline
 427 unsigned AndModelGroup::andIndex() const
 428 {
 429   return andIndex_;
 430 }
 431
 432 inline
 433 unsigned ModelGroup::nMembers() const
 434 {
 435   return members_.size();
 436 }
 437
 438 inline
 439 unsigned ContentToken::andDepth(const AndModelGroup *andAncestor)
 440 {
 441   return andAncestor ? andAncestor->andDepth() + 1 : 0;
 442 }
 443
 444 inline
 445 unsigned ContentToken::andIndex(const AndModelGroup *andAncestor)
 446 {
 447   return (andAncestor
 448           ? andAncestor->andIndex() + andAncestor->nMembers()
 449           : 0);
 450 }
 451
 452 inline
 453 ContentToken &ModelGroup::member(unsigned i)
 454 {
 455   return *members_[i];
 456 }
 457
 458 inline
 459 const ContentToken &ModelGroup::member(unsigned i) const
 460 {
 461   return *members_[i];
 462 }
 463
 464 inline
 465 void LeafContentToken::setFinal()
 466 {
 467   isFinal_ = 1;
 468 }
 469
 470 inline
 471 Boolean LeafContentToken::isFinal() const
 472 {
 473   return isFinal_;
 474 }
 475
 476 inline
 477 Boolean LeafContentToken::orGroupMember() const
 478 {
 479   return orGroupMember_;
 480 }
 481
 482 inline
 483 unsigned CompiledModelGroup::andStateSize() const
 484 {
 485   return andStateSize_;
 486 }
 487
 488 inline
 489 Boolean CompiledModelGroup::containsPcdata() const
 490 {
 491   return containsPcdata_;
 492 }
 493
 494 inline
 495 const AndModelGroup *AndModelGroup::andAncestor() const
 496 {
 497   return andAncestor_;
 498 }
 499
 500 inline
 501 unsigned AndModelGroup::andGroupIndex() const
 502 {
 503   return andGroupIndex_;
 504 }
 505
 506 inline
 507 const LeafContentToken *CompiledModelGroup::initial() const
 508 {
 509   return initial_.pointer();
 510 }
 511
 512 inline
 513 const ModelGroup *CompiledModelGroup::modelGroup() const
 514 {
 515   return modelGroup_.pointer();
 516 }
 517
 518 inline
 519 const AndModelGroup *LeafContentToken::andAncestor() const
 520 {
 521   return andInfo_ ? andInfo_->andAncestor : 0;
 522 }
 523
 524 inline
 525 unsigned LeafContentToken::andDepth() const
 526 {
 527   return andInfo_ ? ContentToken::andDepth(andInfo_->andAncestor) : 0;
 528 }
 529
 530 inline
 531 unsigned LeafContentToken::computeMinAndDepth(const AndState &andState) const
 532 {
 533   return andInfo_ ? computeMinAndDepth1(andState) : 0;
 534 }
 535
 536 inline
 537 Boolean LeafContentToken::tryTransitionPcdata(AndState &andState,
 538                                               unsigned &minAndDepth,
 539                                               const LeafContentToken *&newpos)
 540      const
 541 {
 542   if (pcdataTransitionType_ == 1) {
 543     newpos = simplePcdataTransition_;
 544     return 1;
 545   }
 546   else if (pcdataTransitionType_ == 0)
 547     return 0;
 548   else
 549     return tryTransition(0, andState, minAndDepth, newpos);
 550 }
 551
 552 inline
 553 Boolean MatchState::tryTransition(const ElementType *to)
 554 {
 555   return pos_->tryTransition(to, andState_, minAndDepth_, pos_);
 556 }
 557
 558 inline
 559 Boolean MatchState::tryTransitionPcdata()
 560 {
 561   return pos_->tryTransitionPcdata(andState_, minAndDepth_, pos_);
 562 }
 563
 564 inline
 565 void MatchState::possibleTransitions(Vector<const ElementType *> &v) const
 566 {
 567   pos_->possibleTransitions(andState_, minAndDepth_, v);
 568 }
 569
 570 inline
 571 Boolean MatchState::isFinished() const
 572 {
 573   return pos_->isFinal() && minAndDepth_ == 0;
 574 }
 575
 576 inline
 577 const LeafContentToken *
 578 MatchState::impliedStartTag() const
 579 {
 580   return pos_->impliedStartTag(andState_, minAndDepth_);
 581 }
 582
 583 inline
 584 void MatchState::doRequiredTransition()
 585 {
 586   pos_->doRequiredTransition(andState_, minAndDepth_, pos_);
 587 }
 588
 589 inline
 590 const LeafContentToken *MatchState::currentPosition() const
 591 {
 592   return pos_;
 593 }
 594
 595 inline
 596 Boolean MatchState::operator!=(const MatchState &state) const
 597 {
 598   return !(*this == state);
 599 }
 600
 601 inline
 602 Boolean AndState::isClear(unsigned i) const
 603 {
 604   return v_[i] == 0;
 605 }
 606
 607 inline
 608 void AndState::set(unsigned i)
 609 {
 610   v_[i] = 1;
 611   if (i >= clearFrom_)
 612     clearFrom_ = i + 1;
 613 }
 614
 615 inline
 616 void AndState::clearFrom(unsigned i)
 617 {
 618   if (i < clearFrom_)
 619     clearFrom1(i);
 620 }
 621
 622 inline
 623 Boolean AndState::operator!=(const AndState &state) const
 624 {
 625   return !(*this == state);
 626 }
 627
 628
 629 inline
 630 size_t FirstSet::size() const
 631 {
 632   return v_.size();
 633 }
 634
 635 inline
 636 LeafContentToken *FirstSet::token(size_t i) const
 637 {
 638   return v_[i];
 639 }
 640
 641 inline
 642 size_t FirstSet::requiredIndex() const
 643 {
 644   return requiredIndex_;
 645 }
 646
 647 inline
 648 void FirstSet::setNotRequired()
 649 {
 650   requiredIndex_ = size_t(-1);
 651 }
 652
 653 #ifdef SP_NAMESPACE
 654 }
 655 #endif
 656
 657 #endif /* not ContentToken_INCLUDED */