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