cde/programs/nsgmls/ContentToken.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: ContentToken.C /main/2 1996/08/13 13:59:08 drk $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #ifdef __GNUG__
  28 #pragma implementation
  29 #endif
  30 #include "splib.h"
  31 #include <stdlib.h>
  32 #include "ContentToken.h"
  33 #include "macros.h"
  34 #include "ElementType.h"
  35 #include "Vector.h"
  36 #include "Dtd.h"
  37 #include "MessageArg.h"
  38
  39 #ifdef SP_NAMESPACE
  40 namespace SP_NAMESPACE {
  41 #endif
  42
  43 AndModelGroup::AndModelGroup(NCVector<Owner<ContentToken> > &v,
  44                              ContentToken::OccurrenceIndicator oi)
  45 : ModelGroup(v, oi)
  46 {
  47 }
  48
  49 ModelGroup::Connector AndModelGroup::connector() const
  50 {
  51   return andConnector;
  52 }
  53
  54 OrModelGroup::OrModelGroup(NCVector<Owner<ContentToken> > &v,
  55                            ContentToken::OccurrenceIndicator oi)
  56 : ModelGroup(v, oi)
  57 {
  58   setOrGroup();
  59 }
  60
  61 ModelGroup::Connector OrModelGroup::connector() const
  62 {
  63   return orConnector;
  64 }
  65
  66
  67 SeqModelGroup::SeqModelGroup(NCVector<Owner<ContentToken> > &v,
  68                              ContentToken::OccurrenceIndicator oi)
  69 : ModelGroup(v, oi)
  70 {
  71 }
  72
  73 ModelGroup::Connector SeqModelGroup::connector() const
  74 {
  75   return seqConnector;
  76 }
  77
  78
  79 ModelGroup::ModelGroup(NCVector<Owner<ContentToken> > &v,
  80                        OccurrenceIndicator oi)
  81 : ContentToken(oi)
  82 {
  83   members_.swap(v);
  84 }
  85
  86 unsigned long ModelGroup::grpgtcnt() const
  87 {
  88   unsigned long cnt = 1;
  89   for (size_t i = 0; i < members_.size(); i++)
  90     cnt += members_[i]->grpgtcnt();
  91   return cnt;
  92 }
  93
  94 void ModelGroup::setOrGroup()
  95 {
  96   for (size_t i = 0; i < members_.size(); i++)
  97     members_[i]->setOrGroupMember();
  98 }
  99
 100 const ModelGroup *ModelGroup::asModelGroup() const
 101 {
 102   return this;
 103 }
 104
 105 ElementToken::ElementToken(const ElementType *element, OccurrenceIndicator oi)
 106 : LeafContentToken(element, oi)
 107 {
 108 }
 109
 110 ContentToken::ContentToken(OccurrenceIndicator oi)
 111 : occurrenceIndicator_(oi)
 112 {
 113 }
 114
 115 unsigned long ContentToken::grpgtcnt() const
 116 {
 117   return 1;
 118 }
 119
 120 void ContentToken::setOrGroupMember()
 121 {
 122 }
 123
 124 const ModelGroup *ContentToken::asModelGroup() const
 125 {
 126   return 0;
 127 }
 128
 129 const LeafContentToken *ContentToken::asLeafContentToken() const
 130 {
 131   return 0;
 132 }
 133
 134 LeafContentToken::LeafContentToken(const ElementType *element,
 135                                    OccurrenceIndicator oi)
 136 : element_(element), ContentToken(oi), isFinal_(0), orGroupMember_(0),
 137   requiredIndex_(size_t(-1))
 138 {
 139 }
 140
 141 Boolean LeafContentToken::isInitial() const
 142 {
 143   return 0;
 144 }
 145
 146 void LeafContentToken::setOrGroupMember()
 147 {
 148   orGroupMember_ = 1;
 149 }
 150
 151 const LeafContentToken *LeafContentToken::asLeafContentToken() const
 152 {
 153   return this;
 154 }
 155
 156 PcdataToken::PcdataToken()
 157 : LeafContentToken(0, rep)
 158 {
 159 }
 160
 161 InitialPseudoToken::InitialPseudoToken()
 162 : LeafContentToken(0, none)
 163 {
 164 }
 165
 166 Boolean InitialPseudoToken::isInitial() const
 167 {
 168   return 1;
 169 }
 170
 171 DataTagGroup::DataTagGroup(NCVector<Owner<ContentToken> > &vec,
 172                            OccurrenceIndicator oi)
 173 : SeqModelGroup(vec, oi)
 174 {
 175 }
 176
 177 DataTagElementToken::DataTagElementToken(const ElementType *element,
 178                                          Vector<Text> &templates,
 179                                          Text &paddingTemplate)
 180 : ElementToken(element, ContentToken::none),
 181   havePaddingTemplate_(1)
 182 {
 183   templates.swap(templates_);
 184   paddingTemplate.swap(paddingTemplate_);
 185 }
 186
 187 DataTagElementToken::DataTagElementToken(const ElementType *element,
 188                                          Vector<Text> &templates)
 189 : ElementToken(element, ContentToken::none),
 190   havePaddingTemplate_(0)
 191 {
 192   templates.swap(templates_);
 193 }
 194
 195 ContentToken::~ContentToken()
 196 {
 197 }
 198
 199 struct GroupInfo {
 200   unsigned nextLeafIndex;
 201   PackedBoolean containsPcdata;
 202   unsigned andStateSize;
 203   Vector<unsigned> nextTypeIndex;
 204   GroupInfo(size_t);
 205 };
 206
 207
 208 GroupInfo::GroupInfo(size_t nType)
 209 : nextTypeIndex(nType, 0), nextLeafIndex(0), containsPcdata(0), andStateSize(0)
 210 {
 211 }
 212
 213 CompiledModelGroup::CompiledModelGroup(Owner<ModelGroup> &modelGroup)
 214 : modelGroup_(modelGroup.extract())
 215 {
 216 }
 217
 218 void CompiledModelGroup::compile(size_t nElementTypeIndex,
 219                                  Vector<ContentModelAmbiguity> &ambiguities,
 220                                  Boolean &pcdataUnreachable)
 221 {
 222   FirstSet first;
 223   LastSet last;
 224   GroupInfo info(nElementTypeIndex);
 225   modelGroup_->analyze(info, 0, 0, first, last);
 226   for (unsigned i = 0; i < last.size(); i++)
 227     last[i]->setFinal();
 228   andStateSize_ = info.andStateSize;
 229   containsPcdata_ = info.containsPcdata;
 230   initial_ = new InitialPseudoToken;
 231   LastSet initialSet(1);
 232   initialSet[0] = initial_.pointer();
 233   ContentToken::addTransitions(initialSet, first, 1, 0, 0);
 234   if (modelGroup_->inherentlyOptional())
 235     initial_->setFinal();
 236   pcdataUnreachable = 0;
 237   Vector<unsigned> minAndDepth(info.nextLeafIndex);
 238   Vector<size_t> elementTransition(nElementTypeIndex);
 239   initial_->finish(minAndDepth, elementTransition, ambiguities,
 240                    pcdataUnreachable);
 241   modelGroup_->finish(minAndDepth, elementTransition, ambiguities,
 242                       pcdataUnreachable);
 243   if (!containsPcdata_)
 244     pcdataUnreachable = 0;
 245 }
 246
 247 void ModelGroup::finish(Vector<unsigned> &minAndDepth,
 248                         Vector<size_t> &elementTransition,
 249                         Vector<ContentModelAmbiguity> &ambiguities,
 250                         Boolean &pcdataUnreachable)
 251 {
 252   for (unsigned i = 0; i < nMembers(); i++)
 253     member(i).finish(minAndDepth, elementTransition, ambiguities,
 254                      pcdataUnreachable);
 255 }
 256
 257 void LeafContentToken::finish(Vector<unsigned> &minAndDepthVec,
 258                               Vector<size_t> &elementTransitionVec,
 259                               Vector<ContentModelAmbiguity> &ambiguities,
 260                               Boolean &pcdataUnreachable)
 261 {
 262   if (andInfo_) {
 263     andFinish(minAndDepthVec, elementTransitionVec, ambiguities,
 264               pcdataUnreachable);
 265     return;
 266   }
 267   Vector<size_t>::iterator elementTransition = elementTransitionVec.begin();
 268   Vector<unsigned>::iterator minAndDepth = minAndDepthVec.begin();
 269   minAndDepthVec.assign(minAndDepthVec.size(), unsigned(-1));
 270   elementTransitionVec.assign(elementTransitionVec.size(), size_t(-1));
 271   pcdataTransitionType_ = 0;
 272   simplePcdataTransition_ = 0;
 273   // follow_ is in decreasing order of andDepth because of how it's
 274   // constructed.
 275   size_t n = follow_.size();
 276   Vector<LeafContentToken *>::iterator follow = follow_.begin();
 277   size_t j = 0;
 278   for (size_t i = 0; i < n; i++) {
 279     unsigned &minDepth = minAndDepth[follow[i]->index()];
 280     if (minDepth) {
 281       minDepth = 0;
 282       if (j != i)
 283         follow[j] = follow[i];
 284       if (i == requiredIndex_)
 285         requiredIndex_ = j;
 286       const ElementType *e = follow[i]->elementType();
 287       unsigned ei;
 288       if (e == 0) {
 289         if (!follow[i]->andInfo_) {
 290           simplePcdataTransition_ = follow[i];
 291           pcdataTransitionType_ = 1;
 292         }
 293         else
 294           pcdataTransitionType_ = 2;
 295         ei = 0;
 296       }
 297       else
 298         ei = e->index();
 299       if (elementTransition[ei] != size_t(-1)) {
 300         const LeafContentToken *prev = follow[elementTransition[ei]];
 301         // This might not be true: consider (a & b?)*; after the
 302         // a there are two different ways to get to the same b,
 303         // with the same and depth.
 304         if (follow[i] != prev) {
 305           ambiguities.resize(ambiguities.size() + 1);
 306           ContentModelAmbiguity &a = ambiguities.back();
 307           a.from = this;
 308           a.to1 = prev;
 309           a.to2 = follow[i];
 310           a.andDepth = 0;
 311         }
 312       }
 313       elementTransition[ei] = j;
 314       j++;
 315     }
 316   }
 317   if (pcdataTransitionType_ == 0)
 318     pcdataUnreachable = 1;
 319   follow_.resize(j);
 320 }
 321
 322 void LeafContentToken::andFinish(Vector<unsigned> &minAndDepthVec,
 323                                  Vector<size_t> &elementTransitionVec,
 324                                  Vector<ContentModelAmbiguity> &ambiguities,
 325                                  Boolean &pcdataUnreachable)
 326 {
 327   // Vector mapping element type index to index of leaf content token
 328   // of that type to which there is a transition, which is the "worst"
 329   // from the point of view of ambiguity.
 330   Vector<size_t>::iterator elementTransition = elementTransitionVec.begin();
 331   // Vector mapping index of leaf content token
 332   // to minimum AND depth of transition to that token.
 333   Vector<unsigned>::iterator minAndDepth = minAndDepthVec.begin();
 334   minAndDepthVec.assign(minAndDepthVec.size(), unsigned(-1));
 335   elementTransitionVec.assign(elementTransitionVec.size(), size_t(-1));
 336   pcdataTransitionType_ = 0;
 337   simplePcdataTransition_ = 0;
 338   unsigned pcdataMinCovered = 0;
 339
 340   // follow_ is in decreasing order of andDepth because of how it's
 341   // constructed.
 342   size_t n = follow_.size();
 343   size_t j = 0;
 344   Vector<Transition>::iterator andFollow = andInfo_->follow.begin();
 345   for (size_t i = 0; i < n; i++) {
 346     unsigned &minDepth = minAndDepth[follow_[i]->index()];
 347     // ignore transitions to the same token with the same and depth.
 348     if (andFollow[i].andDepth < minDepth) {
 349       minDepth = andFollow[i].andDepth;
 350       if (j != i) {
 351         follow_[j] = follow_[i];
 352         andFollow[j] = andFollow[i];
 353       }
 354       if (i == requiredIndex_)
 355         requiredIndex_ = j;
 356       const ElementType *e = follow_[i]->elementType();
 357       unsigned ei;
 358       if (e == 0) {
 359         if (pcdataTransitionType_ == 0) {
 360           const AndModelGroup *andAncestor = andInfo_->andAncestor;
 361           unsigned groupIndex = andInfo_->andGroupIndex;
 362           do {
 363             Boolean hasNonNull = 0;
 364             for (unsigned k = 0; k < andAncestor->nMembers(); k++)
 365               if (k != groupIndex
 366                   && !andAncestor->member(k).inherentlyOptional()) {
 367                 hasNonNull = 1;
 368                 break;
 369               }
 370             if (hasNonNull) {
 371               if (minDepth <= andAncestor->andDepth())
 372                 pcdataUnreachable = 1;
 373               break;
 374             }
 375             groupIndex = andAncestor->andGroupIndex();
 376             andAncestor = andAncestor->andAncestor();
 377           } while (andAncestor);
 378           if (andFollow[i].isolated)
 379             pcdataMinCovered = minDepth;
 380           pcdataTransitionType_ = 2;
 381         }
 382         else {
 383           if (pcdataMinCovered > minDepth + 1)
 384             pcdataUnreachable = 1;
 385           pcdataMinCovered = andFollow[i].isolated ? minDepth : 0;
 386         }
 387         ei = 0;
 388       }
 389       else
 390         ei = e->index();
 391       // If we have transitions t1, t2, ... tN to tokens having
 392       // the same element type, with
 393       // and-depths d1, d2, ... dN, where d1 >= d2 >= ... >= dN,
 394       // then there is an ambiguity unless
 395       // d1 > d2 > ... > dN and t1, t2, ... , tN-1 are all isolated.
 396       size_t previ = elementTransition[ei];
 397       if (previ != size_t(-1)) {
 398         const LeafContentToken *prev = follow_[previ];
 399         // This might not be true: consider (a & b?)*; after the
 400         // a there are two different ways to get to the same b,
 401         // with the same and depth.
 402         if (follow_[i] != prev
 403             && (andFollow[previ].andDepth == andFollow[i].andDepth
 404                 || !andFollow[previ].isolated)) {
 405           ambiguities.resize(ambiguities.size() + 1);
 406           ContentModelAmbiguity &a = ambiguities.back();
 407           a.from = this;
 408           a.to1 = prev;
 409           a.to2 = follow_[i];
 410           a.andDepth = andFollow[i].andDepth;
 411         }
 412         if (andFollow[previ].isolated)
 413           elementTransition[ei] = j;
 414       }
 415       else
 416         elementTransition[ei] = j;
 417       j++;
 418     }
 419   }
 420   if (pcdataMinCovered > 0 || pcdataTransitionType_ == 0)
 421     pcdataUnreachable = 1;
 422   follow_.resize(j);
 423   andInfo_->follow.resize(j);
 424 }
 425
 426 void ContentToken::analyze(GroupInfo &info,
 427                            const AndModelGroup *andAncestor,
 428                            unsigned andGroupIndex,
 429                            FirstSet &first,
 430                            LastSet &last)
 431 {
 432   analyze1(info, andAncestor, andGroupIndex, first, last);
 433   if (occurrenceIndicator_ & opt)
 434     inherentlyOptional_ = 1;
 435   if (inherentlyOptional_)
 436     first.setNotRequired();
 437   if (occurrenceIndicator_ & plus)
 438     addTransitions(last, first, 0,
 439                    andIndex(andAncestor), andDepth(andAncestor));
 440 }
 441
 442 void LeafContentToken::analyze1(GroupInfo &info,
 443                                 const AndModelGroup *andAncestor,
 444                                 unsigned andGroupIndex,
 445                                 FirstSet &first,
 446                                 LastSet &last)
 447 {
 448   leafIndex_ = info.nextLeafIndex++;
 449   typeIndex_ = info.nextTypeIndex[element_ ? element_->index() : 0]++;
 450   if (andAncestor) {
 451     andInfo_ = new AndInfo;
 452     andInfo_->andAncestor = andAncestor;
 453     andInfo_->andGroupIndex = andGroupIndex;
 454   }
 455   first.init(this);
 456   last.assign(1, this);
 457   inherentlyOptional_ = 0;
 458 }
 459
 460 void PcdataToken::analyze1(GroupInfo &info,
 461                            const AndModelGroup *andAncestor,
 462                            unsigned andGroupIndex,
 463                            FirstSet &first,
 464                            LastSet &last)
 465 {
 466   info.containsPcdata = 1;
 467   LeafContentToken::analyze1(info, andAncestor, andGroupIndex, first, last);
 468 }
 469
 470 void OrModelGroup::analyze1(GroupInfo &info,
 471                             const AndModelGroup *andAncestor,
 472                             unsigned andGroupIndex,
 473                             FirstSet &first,
 474                             LastSet &last)
 475 {
 476   member(0).analyze(info, andAncestor, andGroupIndex, first, last);
 477   first.setNotRequired();
 478   inherentlyOptional_ = member(0).inherentlyOptional();
 479   for (unsigned i = 1; i < nMembers(); i++) {
 480     FirstSet tempFirst;
 481     LastSet tempLast;
 482     member(i).analyze(info, andAncestor, andGroupIndex, tempFirst, tempLast);
 483     first.append(tempFirst);
 484     first.setNotRequired();
 485     last.append(tempLast);
 486     inherentlyOptional_ |= member(i).inherentlyOptional();
 487   }
 488 }
 489
 490 void SeqModelGroup::analyze1(GroupInfo &info,
 491                              const AndModelGroup *andAncestor,
 492                              unsigned andGroupIndex,
 493                              FirstSet &first,
 494                              LastSet &last)
 495 {
 496   member(0).analyze(info, andAncestor, andGroupIndex, first, last);
 497   inherentlyOptional_ = member(0).inherentlyOptional();
 498   for (unsigned i = 1; i < nMembers(); i++) {
 499     FirstSet tempFirst;
 500     LastSet tempLast;
 501     member(i).analyze(info, andAncestor, andGroupIndex, tempFirst, tempLast);
 502     addTransitions(last, tempFirst, 1,
 503                    andIndex(andAncestor), andDepth(andAncestor));
 504     if (inherentlyOptional_)
 505       first.append(tempFirst);
 506     if (member(i).inherentlyOptional())
 507       last.append(tempLast);
 508     else
 509       tempLast.swap(last);
 510     inherentlyOptional_ &= member(i).inherentlyOptional();
 511   }
 512 }
 513
 514 void AndModelGroup::analyze1(GroupInfo &info,
 515                              const AndModelGroup *andAncestor,
 516                              unsigned andGroupIndex,
 517                              FirstSet &first,
 518                              LastSet &last)
 519 {
 520   andDepth_ = ContentToken::andDepth(andAncestor);
 521   andIndex_ = ContentToken::andIndex(andAncestor);
 522   andAncestor_ = andAncestor;
 523   andGroupIndex_ = andGroupIndex;
 524   if (andIndex_ + nMembers() > info.andStateSize)
 525     info.andStateSize = andIndex_ + nMembers();
 526   Vector<FirstSet> firstVec(nMembers());
 527   Vector<LastSet> lastVec(nMembers());
 528   member(0).analyze(info, this, 0, firstVec[0], lastVec[0]);
 529   first = firstVec[0];
 530   first.setNotRequired();
 531   last = lastVec[0];
 532   inherentlyOptional_ = member(0).inherentlyOptional();
 533   unsigned i;
 534   for (i = 1; i < nMembers(); i++) {
 535     member(i).analyze(info, this, i, firstVec[i], lastVec[i]);
 536     first.append(firstVec[i]);
 537     first.setNotRequired();
 538     last.append(lastVec[i]);
 539     inherentlyOptional_ &= member(i).inherentlyOptional();
 540   }
 541   for (i = 0; i < nMembers(); i++) {
 542     for (unsigned j = 0; j < nMembers(); j++)
 543       if (j != i)
 544         addTransitions(lastVec[i], firstVec[j], 0,
 545                        andIndex() + nMembers(),
 546                        andDepth() + 1,
 547                        !member(j).inherentlyOptional(),
 548                        andIndex() + j, andIndex() + i);
 549   }
 550 }
 551
 552 void ContentToken::addTransitions(const LastSet &from,
 553                                   const FirstSet &to,
 554                                   Boolean maybeRequired,
 555                                   unsigned andClearIndex,
 556                                   unsigned andDepth,
 557                                   Boolean isolated,
 558                                   unsigned requireClear,
 559                                   unsigned toSet)
 560 {
 561   size_t length = from.size();
 562   for (unsigned i = 0; i < length; i++)
 563     from[i]->addTransitions(to,
 564                             maybeRequired,
 565                             andClearIndex,
 566                             andDepth,
 567                             isolated,
 568                             requireClear,
 569                             toSet);
 570 }
 571
 572 void LeafContentToken::addTransitions(const FirstSet &to,
 573                                       Boolean maybeRequired,
 574                                       unsigned andClearIndex,
 575                                       unsigned andDepth,
 576                                       Boolean isolated,
 577                                       unsigned requireClear,
 578                                       unsigned toSet)
 579 {
 580   if (maybeRequired && to.requiredIndex() != size_t(-1)) {
 581     ASSERT(requiredIndex_ == size_t(-1));
 582     requiredIndex_ = to.requiredIndex() + follow_.size();
 583   }
 584   size_t length = follow_.size();
 585   size_t n = to.size();
 586   follow_.resize(length + n);
 587   for (size_t i = 0; i < n; i++)
 588     follow_[length + i] = to.token(i);
 589   if (andInfo_) {
 590     andInfo_->follow.resize(length + n);
 591     for (size_t i = 0; i < n; i++) {
 592       Transition &t = andInfo_->follow[length + i];
 593       t.clearAndStateStartIndex = andClearIndex;
 594       t.andDepth = andDepth;
 595       t.isolated = isolated;
 596       t.requireClear = requireClear;
 597       t.toSet = toSet;
 598     }
 599   }
 600 }
 601
 602 AndState::AndState(unsigned n)
 603 : v_(n, PackedBoolean(0)), clearFrom_(0)
 604 {
 605 }
 606
 607 void AndState::clearFrom1(unsigned i)
 608 {
 609   while (clearFrom_ > i)
 610     v_[--clearFrom_] = 0;
 611 }
 612
 613 MatchState::MatchState()
 614 : andState_(0)
 615 {
 616 }
 617
 618 MatchState::MatchState(const CompiledModelGroup *model)
 619 : pos_(model ? model->initial() : 0),
 620   andState_(model ? model->andStateSize() : 0),
 621   minAndDepth_(0)
 622 {
 623 }
 624
 625 const LeafContentToken *MatchState::invalidExclusion(const ElementType *e)
 626      const
 627 {
 628   const LeafContentToken *token = pos_->transitionToken(e, andState_,
 629                                                         minAndDepth_);
 630   if (token && !token->inherentlyOptional() && !token->orGroupMember())
 631     return token;
 632   else
 633     return 0;
 634 }
 635
 636 Boolean MatchState::operator==(const MatchState &state) const
 637 {
 638   return (pos_ == state.pos_ && andState_ == state.andState_
 639           && minAndDepth_ == state.minAndDepth_);
 640 }
 641
 642 Boolean AndState::operator==(const AndState &state) const
 643 {
 644   ASSERT(v_.size() == state.v_.size());
 645   for (size_t i = 0; i < v_.size(); i++) {
 646     if (i >= clearFrom_ && i >= state.clearFrom_)
 647       break;
 648     if (v_[i] != state.v_[i])
 649       return 0;
 650   }
 651   return 1;
 652 }
 653
 654 const LeafContentToken *
 655 LeafContentToken::transitionToken(const ElementType *to,
 656                                   const AndState &andState,
 657                                   unsigned minAndDepth) const
 658 {
 659   Vector<LeafContentToken *>::const_iterator p = follow_.begin();
 660   if (!andInfo_) {
 661     for (size_t n = follow_.size(); n > 0; n--, p++)
 662       if ((*p)->elementType() == to)
 663         return *p;
 664   }
 665   else {
 666     Vector<Transition>::const_iterator q = andInfo_->follow.begin();
 667     for (size_t n = follow_.size(); n > 0; n--, p++, q++)
 668       if ((*p)->elementType() == to
 669           && ((q->requireClear == unsigned(Transition::invalidIndex)
 670                || andState.isClear(q->requireClear))
 671               && q->andDepth >= minAndDepth))
 672         return (*p);
 673   }
 674   return 0;
 675 }
 676
 677 Boolean
 678 LeafContentToken::tryTransition(const ElementType *to,
 679                                 AndState &andState,
 680                                 unsigned &minAndDepth,
 681                                 const LeafContentToken *&newpos) const
 682 {
 683   Vector<LeafContentToken *>::const_iterator p = follow_.begin();
 684   if (!andInfo_) {
 685     for (size_t n = follow_.size(); n > 0; n--, p++) {
 686       if ((*p)->elementType() == to) {
 687         newpos = *p;
 688         minAndDepth = newpos->computeMinAndDepth(andState);
 689         return 1;
 690       }
 691     }
 692   }
 693   else {
 694     Vector<Transition>::const_iterator q = andInfo_->follow.begin();
 695     for (size_t n = follow_.size(); n > 0; n--, p++, q++) {
 696     if ((*p)->elementType() == to
 697         && ((q->requireClear == unsigned(Transition::invalidIndex)
 698              || andState.isClear(q->requireClear))
 699             && q->andDepth >= minAndDepth)) {
 700         if (q->toSet != unsigned(Transition::invalidIndex))
 701           andState.set(q->toSet);
 702         andState.clearFrom(q->clearAndStateStartIndex);
 703         newpos = *p;
 704         minAndDepth = newpos->computeMinAndDepth(andState);
 705         return 1;
 706       }
 707     }
 708   }
 709   return 0;
 710 }
 711
 712 void
 713 LeafContentToken::possibleTransitions(const AndState &andState,
 714                                       unsigned minAndDepth,
 715                                       Vector<const ElementType *> &v) const
 716 {
 717   Vector<LeafContentToken *>::const_iterator p = follow_.begin();
 718   if (!andInfo_) {
 719     for (size_t n = follow_.size(); n > 0; n--, p++)
 720       v.push_back((*p)->elementType());
 721   }
 722   else {
 723     Vector<Transition>::const_iterator q = andInfo_->follow.begin();
 724     for (size_t n = follow_.size(); n > 0; n--, p++, q++)
 725       if ((q->requireClear == unsigned(Transition::invalidIndex)
 726            || andState.isClear(q->requireClear))
 727         && q->andDepth >= minAndDepth)
 728         v.push_back((*p)->elementType());
 729   }
 730 }
 731
 732 unsigned LeafContentToken::computeMinAndDepth1(const AndState &andState) const
 733 {
 734   ASSERT(andInfo_);
 735   unsigned groupIndex = andInfo_->andGroupIndex;
 736   for (const AndModelGroup *group = andInfo_->andAncestor;
 737        group;
 738        groupIndex = group->andGroupIndex(), group = group->andAncestor())
 739     for (unsigned i = 0; i < group->nMembers(); i++)
 740       if (i != groupIndex && !group->member(i).inherentlyOptional()
 741           && andState.isClear(group->andIndex() + i))
 742         return group->andDepth() + 1;
 743   return 0;
 744 }
 745
 746 const LeafContentToken *
 747 LeafContentToken::impliedStartTag(const AndState &andState,
 748                                   unsigned minAndDepth) const
 749 {
 750   if (requiredIndex_ != size_t(-1)) {
 751     if (!andInfo_)
 752       return follow_[requiredIndex_];
 753     const Transition &t = andInfo_->follow[requiredIndex_];
 754     if ((t.requireClear == unsigned(Transition::invalidIndex)
 755          || andState.isClear(t.requireClear))
 756         && t.andDepth >= minAndDepth)
 757       return follow_[requiredIndex_];
 758   }
 759   return 0;
 760 }
 761
 762 void LeafContentToken::doRequiredTransition(AndState &andState,
 763                                             unsigned &minAndDepth,
 764                                             const LeafContentToken *&newpos)
 765      const
 766 {
 767   ASSERT(requiredIndex_ != size_t(-1));
 768   if (andInfo_) {
 769     const Transition &t = andInfo_->follow[requiredIndex_];
 770     if (t.toSet != unsigned(Transition::invalidIndex))
 771       andState.set(t.toSet);
 772     andState.clearFrom(t.clearAndStateStartIndex);
 773   }
 774   newpos = follow_[requiredIndex_];
 775   minAndDepth = newpos->computeMinAndDepth(andState);
 776 }
 777
 778 FirstSet::FirstSet()
 779 : requiredIndex_(size_t(-1))
 780 {
 781 }
 782
 783 void FirstSet::init(LeafContentToken *p)
 784 {
 785   v_.assign(1, p);
 786   v_.reserve(256);
 787   requiredIndex_ = 0;
 788 }
 789
 790 void FirstSet::append(const FirstSet &set)
 791 {
 792   if (set.requiredIndex_ != size_t(-1)) {
 793     ASSERT(requiredIndex_ == size_t(-1));
 794     requiredIndex_ = set.requiredIndex_ + v_.size();
 795   }
 796   size_t oldSize = v_.size();
 797   v_.resize(v_.size() + set.v_.size());
 798   for (size_t i = 0; i < set.v_.size(); i++)
 799     v_[oldSize + i] = set.v_[i];
 800 }
 801
 802 void LastSet::append(const LastSet &set)
 803 {
 804   size_t oldSize = size();
 805   resize(size() + set.size());
 806   for (size_t i = 0; i < set.size(); i++)
 807     (*this)[oldSize + i] = set[i];
 808 }
 809
 810 #ifdef SP_NAMESPACE
 811 }
 812 #endif