CDE/cde/programs/nsgmls/ContentToken.C

/*
 * CDE - Common Desktop Environment
 *
 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
 *
 * These libraries and programs are free software; you can
 * redistribute them and/or modify them under the terms of the GNU
 * Lesser General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * These libraries and programs are distributed in the hope that
 * they will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with these libraries and programs; if not, write
 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
 * Floor, Boston, MA 02110-1301 USA
 */
/* $XConsortium: ContentToken.C /main/2 1996/08/13 13:59:08 drk $ */
// Copyright (c) 1994 James Clark
// See the file COPYING for copying permission.

#ifdef __GNUG__
#pragma implementation
#endif
#include "splib.h"
#include <stdlib.h>
#include "ContentToken.h"
#include "macros.h"
#include "ElementType.h"
#include "Vector.h"
#include "Dtd.h"
#include "MessageArg.h"

#ifdef SP_NAMESPACE
namespace SP_NAMESPACE {
#endif

AndModelGroup::AndModelGroup(NCVector<Owner<ContentToken> > &v,
			     ContentToken::OccurrenceIndicator oi)
: ModelGroup(v, oi), andDepth_(0), andIndex_(0), andGroupIndex_(0),
  andAncestor_(NULL)
{
}

ModelGroup::Connector AndModelGroup::connector() const
{
  return andConnector;
}

OrModelGroup::OrModelGroup(NCVector<Owner<ContentToken> > &v,
			   ContentToken::OccurrenceIndicator oi)
: ModelGroup(v, oi)
{
  setOrGroup();
}

ModelGroup::Connector OrModelGroup::connector() const
{
  return orConnector;
}


SeqModelGroup::SeqModelGroup(NCVector<Owner<ContentToken> > &v,
			     ContentToken::OccurrenceIndicator oi)
: ModelGroup(v, oi)
{
}

ModelGroup::Connector SeqModelGroup::connector() const
{
  return seqConnector;
}


ModelGroup::ModelGroup(NCVector<Owner<ContentToken> > &v,
		       OccurrenceIndicator oi)
: ContentToken(oi)
{
  members_.swap(v);
}

unsigned long ModelGroup::grpgtcnt() const
{
  unsigned long cnt = 1;
  for (size_t i = 0; i < members_.size(); i++)
    cnt += members_[i]->grpgtcnt();
  return cnt;
}

void ModelGroup::setOrGroup()
{
  for (size_t i = 0; i < members_.size(); i++)
    members_[i]->setOrGroupMember();
}

const ModelGroup *ModelGroup::asModelGroup() const
{
  return this;
}

ElementToken::ElementToken(const ElementType *element, OccurrenceIndicator oi)
: LeafContentToken(element, oi)
{
}

ContentToken::ContentToken(OccurrenceIndicator oi)
: occurrenceIndicator_(oi),
inherentlyOptional_(0)
{
}

unsigned long ContentToken::grpgtcnt() const
{
  return 1;
}

void ContentToken::setOrGroupMember()
{
}

const ModelGroup *ContentToken::asModelGroup() const
{
  return 0;
}

const LeafContentToken *ContentToken::asLeafContentToken() const
{
  return 0;
}

LeafContentToken::LeafContentToken(const ElementType *element,
				   OccurrenceIndicator oi)
: element_(element), ContentToken(oi), isFinal_(0), orGroupMember_(0),
  requiredIndex_(size_t(-1)), leafIndex_(0), typeIndex_(0), pcdataTransitionType_(0),
  simplePcdataTransition_(NULL)
{
}

Boolean LeafContentToken::isInitial() const
{
  return 0;
}

void LeafContentToken::setOrGroupMember()
{
  orGroupMember_ = 1;
}

const LeafContentToken *LeafContentToken::asLeafContentToken() const
{
  return this;
}

PcdataToken::PcdataToken()
: LeafContentToken(0, rep)
{
}

InitialPseudoToken::InitialPseudoToken()
: LeafContentToken(0, none)
{
}

Boolean InitialPseudoToken::isInitial() const
{
  return 1;
}

DataTagGroup::DataTagGroup(NCVector<Owner<ContentToken> > &vec,
			   OccurrenceIndicator oi)
: SeqModelGroup(vec, oi)
{
}

DataTagElementToken::DataTagElementToken(const ElementType *element,
					 Vector<Text> &templates,
					 Text &paddingTemplate)
: ElementToken(element, ContentToken::none),
  havePaddingTemplate_(1)
{
  templates.swap(templates_);
  paddingTemplate.swap(paddingTemplate_);
}

DataTagElementToken::DataTagElementToken(const ElementType *element,
					 Vector<Text> &templates)
: ElementToken(element, ContentToken::none),
  havePaddingTemplate_(0)
{
  templates.swap(templates_);
}

ContentToken::~ContentToken()
{
}

struct GroupInfo {
  unsigned nextLeafIndex;
  PackedBoolean containsPcdata;
  unsigned andStateSize;
  Vector<unsigned> nextTypeIndex;
  GroupInfo(size_t);
};


GroupInfo::GroupInfo(size_t nType)
: nextTypeIndex(nType, 0), nextLeafIndex(0), containsPcdata(0), andStateSize(0)
{
}

CompiledModelGroup::CompiledModelGroup(Owner<ModelGroup> &modelGroup)
: modelGroup_(modelGroup.extract()), andStateSize_(0), containsPcdata_(false)
{
}

void CompiledModelGroup::compile(size_t nElementTypeIndex,
				 Vector<ContentModelAmbiguity> &ambiguities,
				 Boolean &pcdataUnreachable)
{
  FirstSet first;
  LastSet last;
  GroupInfo info(nElementTypeIndex);
  modelGroup_->analyze(info, 0, 0, first, last);
  for (unsigned i = 0; i < last.size(); i++)
    last[i]->setFinal();
  andStateSize_ = info.andStateSize;
  containsPcdata_ = info.containsPcdata;
  initial_ = new InitialPseudoToken;
  LastSet initialSet(1);
  initialSet[0] = initial_.pointer();
  ContentToken::addTransitions(initialSet, first, 1, 0, 0);
  if (modelGroup_->inherentlyOptional())
    initial_->setFinal();
  pcdataUnreachable = 0;
  Vector<unsigned> minAndDepth(info.nextLeafIndex);
  Vector<size_t> elementTransition(nElementTypeIndex);
  initial_->finish(minAndDepth, elementTransition, ambiguities,
		   pcdataUnreachable);
  modelGroup_->finish(minAndDepth, elementTransition, ambiguities,
		      pcdataUnreachable);
  if (!containsPcdata_)
    pcdataUnreachable = 0;
}

void ModelGroup::finish(Vector<unsigned> &minAndDepth,
			Vector<size_t> &elementTransition,
			Vector<ContentModelAmbiguity> &ambiguities,
			Boolean &pcdataUnreachable)
{
  for (unsigned i = 0; i < nMembers(); i++)
    member(i).finish(minAndDepth, elementTransition, ambiguities,
		     pcdataUnreachable);
}

void LeafContentToken::finish(Vector<unsigned> &minAndDepthVec,
			      Vector<size_t> &elementTransitionVec,
			      Vector<ContentModelAmbiguity> &ambiguities,
			      Boolean &pcdataUnreachable)
{
  if (andInfo_) {
    andFinish(minAndDepthVec, elementTransitionVec, ambiguities,
	      pcdataUnreachable);
    return;
  }
  Vector<size_t>::iterator elementTransition = elementTransitionVec.begin();
  Vector<unsigned>::iterator minAndDepth = minAndDepthVec.begin();
  minAndDepthVec.assign(minAndDepthVec.size(), unsigned(-1));
  elementTransitionVec.assign(elementTransitionVec.size(), size_t(-1));
  pcdataTransitionType_ = 0;
  simplePcdataTransition_ = 0;
  // follow_ is in decreasing order of andDepth because of how it's
  // constructed.
  size_t n = follow_.size();
  Vector<LeafContentToken *>::iterator follow = follow_.begin();
  size_t j = 0;
  for (size_t i = 0; i < n; i++) {
    unsigned &minDepth = minAndDepth[follow[i]->index()];
    if (minDepth) {
      minDepth = 0;
      if (j != i)
	follow[j] = follow[i];
      if (i == requiredIndex_)
	requiredIndex_ = j;
      const ElementType *e = follow[i]->elementType();
      unsigned ei;
      if (e == 0) {
	if (!follow[i]->andInfo_) {
	  simplePcdataTransition_ = follow[i];
	  pcdataTransitionType_ = 1;
	}
	else
	  pcdataTransitionType_ = 2;
	ei = 0;
      }
      else
	ei = e->index();
      if (elementTransition[ei] != size_t(-1)) {
	const LeafContentToken *prev = follow[elementTransition[ei]];
	// This might not be true: consider (a & b?)*; after the
	// a there are two different ways to get to the same b,
	// with the same and depth.
	if (follow[i] != prev) {
	  ambiguities.resize(ambiguities.size() + 1);
	  ContentModelAmbiguity &a = ambiguities.back();
	  a.from = this;
	  a.to1 = prev;
	  a.to2 = follow[i];
	  a.andDepth = 0;
	}
      }
      elementTransition[ei] = j;
      j++;
    }
  }
  if (pcdataTransitionType_ == 0)
    pcdataUnreachable = 1;
  follow_.resize(j);
}

void LeafContentToken::andFinish(Vector<unsigned> &minAndDepthVec,
				 Vector<size_t> &elementTransitionVec,
				 Vector<ContentModelAmbiguity> &ambiguities,
				 Boolean &pcdataUnreachable)
{
  // Vector mapping element type index to index of leaf content token
  // of that type to which there is a transition, which is the "worst"
  // from the point of view of ambiguity.
  Vector<size_t>::iterator elementTransition = elementTransitionVec.begin();
  // Vector mapping index of leaf content token
  // to minimum AND depth of transition to that token.
  Vector<unsigned>::iterator minAndDepth = minAndDepthVec.begin();
  minAndDepthVec.assign(minAndDepthVec.size(), unsigned(-1));
  elementTransitionVec.assign(elementTransitionVec.size(), size_t(-1));
  pcdataTransitionType_ = 0;
  simplePcdataTransition_ = 0;
  unsigned pcdataMinCovered = 0;
  
  // follow_ is in decreasing order of andDepth because of how it's
  // constructed.
  size_t n = follow_.size();
  size_t j = 0;
  Vector<Transition>::iterator andFollow = andInfo_->follow.begin();
  for (size_t i = 0; i < n; i++) {
    unsigned &minDepth = minAndDepth[follow_[i]->index()];
    // ignore transitions to the same token with the same and depth.
    if (andFollow[i].andDepth < minDepth) {
      minDepth = andFollow[i].andDepth;
      if (j != i) {
	follow_[j] = follow_[i];
	andFollow[j] = andFollow[i];
      }
      if (i == requiredIndex_)
	requiredIndex_ = j;
      const ElementType *e = follow_[i]->elementType();
      unsigned ei;
      if (e == 0) {
	if (pcdataTransitionType_ == 0) {
	  const AndModelGroup *andAncestor = andInfo_->andAncestor;
	  unsigned groupIndex = andInfo_->andGroupIndex;
	  do {
	    Boolean hasNonNull = 0;
	    for (unsigned k = 0; k < andAncestor->nMembers(); k++)
	      if (k != groupIndex
		  && !andAncestor->member(k).inherentlyOptional()) {
		hasNonNull = 1;
		break;
	      }
	    if (hasNonNull) {
	      if (minDepth <= andAncestor->andDepth())
		pcdataUnreachable = 1;
	      break;
	    }
	    groupIndex = andAncestor->andGroupIndex();
	    andAncestor = andAncestor->andAncestor();
	  } while (andAncestor);
	  if (andFollow[i].isolated)
	    pcdataMinCovered = minDepth;
	  pcdataTransitionType_ = 2;
	}
	else {
	  if (pcdataMinCovered > minDepth + 1)
	    pcdataUnreachable = 1;
	  pcdataMinCovered = andFollow[i].isolated ? minDepth : 0;
	}
	ei = 0;
      }
      else
	ei = e->index();
      // If we have transitions t1, t2, ... tN to tokens having
      // the same element type, with
      // and-depths d1, d2, ... dN, where d1 >= d2 >= ... >= dN,
      // then there is an ambiguity unless
      // d1 > d2 > ... > dN and t1, t2, ... , tN-1 are all isolated.
      size_t previ = elementTransition[ei];
      if (previ != size_t(-1)) {
	const LeafContentToken *prev = follow_[previ];
	// This might not be true: consider (a & b?)*; after the
	// a there are two different ways to get to the same b,
	// with the same and depth.
	if (follow_[i] != prev
	    && (andFollow[previ].andDepth == andFollow[i].andDepth
		|| !andFollow[previ].isolated)) {
	  ambiguities.resize(ambiguities.size() + 1);
	  ContentModelAmbiguity &a = ambiguities.back();
	  a.from = this;
	  a.to1 = prev;
	  a.to2 = follow_[i];
	  a.andDepth = andFollow[i].andDepth;
	}
	if (andFollow[previ].isolated)
	  elementTransition[ei] = j;
      }
      else
	elementTransition[ei] = j;
      j++;
    }
  }
  if (pcdataMinCovered > 0 || pcdataTransitionType_ == 0)
    pcdataUnreachable = 1;
  follow_.resize(j);
  andInfo_->follow.resize(j);
}

void ContentToken::analyze(GroupInfo &info,
			   const AndModelGroup *andAncestor,
			   unsigned andGroupIndex,
			   FirstSet &first,
			   LastSet &last)
{
  analyze1(info, andAncestor, andGroupIndex, first, last);
  if (occurrenceIndicator_ & opt)
    inherentlyOptional_ = 1;
  if (inherentlyOptional_)
    first.setNotRequired();
  if (occurrenceIndicator_ & plus)
    addTransitions(last, first, 0,
		   andIndex(andAncestor), andDepth(andAncestor));
}

void LeafContentToken::analyze1(GroupInfo &info,
				const AndModelGroup *andAncestor,
				unsigned andGroupIndex,
				FirstSet &first,
				LastSet &last)
{
  leafIndex_ = info.nextLeafIndex++;
  typeIndex_ = info.nextTypeIndex[element_ ? element_->index() : 0]++;
  if (andAncestor) {
    andInfo_ = new AndInfo;
    andInfo_->andAncestor = andAncestor;
    andInfo_->andGroupIndex = andGroupIndex;
  }
  first.init(this);
  last.assign(1, this);
  inherentlyOptional_ = 0;
}

void PcdataToken::analyze1(GroupInfo &info,
			   const AndModelGroup *andAncestor,
			   unsigned andGroupIndex,
			   FirstSet &first,
			   LastSet &last)
{
  info.containsPcdata = 1;
  LeafContentToken::analyze1(info, andAncestor, andGroupIndex, first, last);
}

void OrModelGroup::analyze1(GroupInfo &info,
			    const AndModelGroup *andAncestor,
			    unsigned andGroupIndex,
			    FirstSet &first,
			    LastSet &last)
{
  member(0).analyze(info, andAncestor, andGroupIndex, first, last);
  first.setNotRequired();
  inherentlyOptional_ = member(0).inherentlyOptional();
  for (unsigned i = 1; i < nMembers(); i++) {
    FirstSet tempFirst;
    LastSet tempLast;
    member(i).analyze(info, andAncestor, andGroupIndex, tempFirst, tempLast);
    first.append(tempFirst);
    first.setNotRequired();
    last.append(tempLast);
    inherentlyOptional_ |= member(i).inherentlyOptional();
  }
}

void SeqModelGroup::analyze1(GroupInfo &info,
			     const AndModelGroup *andAncestor,
			     unsigned andGroupIndex,
			     FirstSet &first,
			     LastSet &last)
{
  member(0).analyze(info, andAncestor, andGroupIndex, first, last);
  inherentlyOptional_ = member(0).inherentlyOptional();
  for (unsigned i = 1; i < nMembers(); i++) {
    FirstSet tempFirst;
    LastSet tempLast;
    member(i).analyze(info, andAncestor, andGroupIndex, tempFirst, tempLast);
    addTransitions(last, tempFirst, 1,
		   andIndex(andAncestor), andDepth(andAncestor));
    if (inherentlyOptional_)
      first.append(tempFirst);
    if (member(i).inherentlyOptional())
      last.append(tempLast);
    else
      tempLast.swap(last);
    inherentlyOptional_ &= member(i).inherentlyOptional();
  }
}

void AndModelGroup::analyze1(GroupInfo &info,
			     const AndModelGroup *andAncestor,
			     unsigned andGroupIndex,
			     FirstSet &first,
			     LastSet &last)
{
  andDepth_ = ContentToken::andDepth(andAncestor);
  andIndex_ = ContentToken::andIndex(andAncestor);
  andAncestor_ = andAncestor;
  andGroupIndex_ = andGroupIndex;
  if (andIndex_ + nMembers() > info.andStateSize)
    info.andStateSize = andIndex_ + nMembers();
  Vector<FirstSet> firstVec(nMembers());
  Vector<LastSet> lastVec(nMembers());
  member(0).analyze(info, this, 0, firstVec[0], lastVec[0]);
  first = firstVec[0];
  first.setNotRequired();
  last = lastVec[0];
  inherentlyOptional_ = member(0).inherentlyOptional();
  unsigned i;
  for (i = 1; i < nMembers(); i++) {
    member(i).analyze(info, this, i, firstVec[i], lastVec[i]);
    first.append(firstVec[i]);
    first.setNotRequired();
    last.append(lastVec[i]);
    inherentlyOptional_ &= member(i).inherentlyOptional();
  }
  for (i = 0; i < nMembers(); i++) {
    for (unsigned j = 0; j < nMembers(); j++)
      if (j != i)
	addTransitions(lastVec[i], firstVec[j], 0,
		       andIndex() + nMembers(),
		       andDepth() + 1,
		       !member(j).inherentlyOptional(),
		       andIndex() + j, andIndex() + i);
  }
}

void ContentToken::addTransitions(const LastSet &from,
				  const FirstSet &to,
				  Boolean maybeRequired,
				  unsigned andClearIndex,
				  unsigned andDepth,
				  Boolean isolated,
				  unsigned requireClear,
				  unsigned toSet)
{
  size_t length = from.size();
  for (unsigned i = 0; i < length; i++)
    from[i]->addTransitions(to,
			    maybeRequired,
			    andClearIndex,
			    andDepth,
			    isolated,
			    requireClear,
			    toSet);
}

void LeafContentToken::addTransitions(const FirstSet &to,
				      Boolean maybeRequired,
				      unsigned andClearIndex,
				      unsigned andDepth,
				      Boolean isolated,
				      unsigned requireClear,
				      unsigned toSet)
{
  if (maybeRequired && to.requiredIndex() != size_t(-1)) {
    ASSERT(requiredIndex_ == size_t(-1));
    requiredIndex_ = to.requiredIndex() + follow_.size();
  }
  size_t length = follow_.size();
  size_t n = to.size();
  follow_.resize(length + n);
  for (size_t i = 0; i < n; i++)
    follow_[length + i] = to.token(i);
  if (andInfo_) {
    andInfo_->follow.resize(length + n);
    for (size_t i = 0; i < n; i++) {
      Transition &t = andInfo_->follow[length + i];
      t.clearAndStateStartIndex = andClearIndex;
      t.andDepth = andDepth;
      t.isolated = isolated;
      t.requireClear = requireClear;
      t.toSet = toSet;
    }
  }
}

AndState::AndState(unsigned n)
: v_(n, PackedBoolean(0)), clearFrom_(0)
{
}

void AndState::clearFrom1(unsigned i)
{
  while (clearFrom_ > i)
    v_[--clearFrom_] = 0;
}

MatchState::MatchState()
: andState_(0), pos_(NULL), minAndDepth_(0)
{
}

MatchState::MatchState(const CompiledModelGroup *model)
: pos_(model ? model->initial() : 0),
  andState_(model ? model->andStateSize() : 0),
  minAndDepth_(0)
{
}

const LeafContentToken *MatchState::invalidExclusion(const ElementType *e)
     const
{
  const LeafContentToken *token = pos_->transitionToken(e, andState_,
							minAndDepth_);
  if (token && !token->inherentlyOptional() && !token->orGroupMember())
    return token;
  else
    return 0;
}

Boolean MatchState::operator==(const MatchState &state) const
{
  return (pos_ == state.pos_ && andState_ == state.andState_
	  && minAndDepth_ == state.minAndDepth_);
}

Boolean AndState::operator==(const AndState &state) const
{
  ASSERT(v_.size() == state.v_.size());
  for (size_t i = 0; i < v_.size(); i++) {
    if (i >= clearFrom_ && i >= state.clearFrom_)
      break;
    if (v_[i] != state.v_[i])
      return 0;
  }
  return 1;
}

const LeafContentToken *
LeafContentToken::transitionToken(const ElementType *to,
				  const AndState &andState,
				  unsigned minAndDepth) const
{
  Vector<LeafContentToken *>::const_iterator p = follow_.begin();
  if (!andInfo_) {
    for (size_t n = follow_.size(); n > 0; n--, p++)
      if ((*p)->elementType() == to)
	return *p;
  }
  else {
    Vector<Transition>::const_iterator q = andInfo_->follow.begin();
    for (size_t n = follow_.size(); n > 0; n--, p++, q++)
      if ((*p)->elementType() == to
	  && ((q->requireClear == unsigned(Transition::invalidIndex)
	       || andState.isClear(q->requireClear))
	      && q->andDepth >= minAndDepth))
	return (*p);
  }
  return 0;
}

Boolean
LeafContentToken::tryTransition(const ElementType *to,
				AndState &andState,
				unsigned &minAndDepth,
				const LeafContentToken *&newpos) const
{
  Vector<LeafContentToken *>::const_iterator p = follow_.begin();
  if (!andInfo_) {
    for (size_t n = follow_.size(); n > 0; n--, p++) {
      if ((*p)->elementType() == to) {
	newpos = *p;
	minAndDepth = newpos->computeMinAndDepth(andState);
	return 1;
      }
    }
  }
  else {
    Vector<Transition>::const_iterator q = andInfo_->follow.begin();
    for (size_t n = follow_.size(); n > 0; n--, p++, q++) {
    if ((*p)->elementType() == to
	&& ((q->requireClear == unsigned(Transition::invalidIndex)
	     || andState.isClear(q->requireClear))
	    && q->andDepth >= minAndDepth)) {
	if (q->toSet != unsigned(Transition::invalidIndex))
	  andState.set(q->toSet);
	andState.clearFrom(q->clearAndStateStartIndex);
	newpos = *p;
	minAndDepth = newpos->computeMinAndDepth(andState);
	return 1;
      }
    }
  }
  return 0;
}

void
LeafContentToken::possibleTransitions(const AndState &andState,
				      unsigned minAndDepth,
				      Vector<const ElementType *> &v) const
{
  Vector<LeafContentToken *>::const_iterator p = follow_.begin();
  if (!andInfo_) {
    for (size_t n = follow_.size(); n > 0; n--, p++) 
      v.push_back((*p)->elementType());
  }
  else {
    Vector<Transition>::const_iterator q = andInfo_->follow.begin();
    for (size_t n = follow_.size(); n > 0; n--, p++, q++)
      if ((q->requireClear == unsigned(Transition::invalidIndex)
	   || andState.isClear(q->requireClear))
	&& q->andDepth >= minAndDepth)
	v.push_back((*p)->elementType());
  }
}

unsigned LeafContentToken::computeMinAndDepth1(const AndState &andState) const
{
  ASSERT(andInfo_);
  unsigned groupIndex = andInfo_->andGroupIndex;
  for (const AndModelGroup *group = andInfo_->andAncestor;
       group;
       groupIndex = group->andGroupIndex(), group = group->andAncestor())
    for (unsigned i = 0; i < group->nMembers(); i++)
      if (i != groupIndex && !group->member(i).inherentlyOptional()
	  && andState.isClear(group->andIndex() + i))
	return group->andDepth() + 1;
  return 0;
}

const LeafContentToken *
LeafContentToken::impliedStartTag(const AndState &andState,
				  unsigned minAndDepth) const
{
  if (requiredIndex_ != size_t(-1)) {
    if (!andInfo_)
      return follow_[requiredIndex_];
    const Transition &t = andInfo_->follow[requiredIndex_];
    if ((t.requireClear == unsigned(Transition::invalidIndex)
	 || andState.isClear(t.requireClear))
	&& t.andDepth >= minAndDepth)
      return follow_[requiredIndex_];
  }
  return 0;
}

void LeafContentToken::doRequiredTransition(AndState &andState,
					    unsigned &minAndDepth,
					    const LeafContentToken *&newpos)
     const
{
  ASSERT(requiredIndex_ != size_t(-1));
  if (andInfo_) {
    const Transition &t = andInfo_->follow[requiredIndex_];
    if (t.toSet != unsigned(Transition::invalidIndex))
      andState.set(t.toSet);
    andState.clearFrom(t.clearAndStateStartIndex);
  }
  newpos = follow_[requiredIndex_];
  minAndDepth = newpos->computeMinAndDepth(andState);
}

FirstSet::FirstSet()
: requiredIndex_(size_t(-1))
{
}

void FirstSet::init(LeafContentToken *p)
{
  v_.assign(1, p);
  v_.reserve(256);
  requiredIndex_ = 0;
}

void FirstSet::append(const FirstSet &set)
{
  if (set.requiredIndex_ != size_t(-1)) {
    ASSERT(requiredIndex_ == size_t(-1));
    requiredIndex_ = set.requiredIndex_ + v_.size();
  }
  size_t oldSize = v_.size();
  v_.resize(v_.size() + set.v_.size());
  for (size_t i = 0; i < set.v_.size(); i++)
    v_[oldSize + i] = set.v_[i];
}

void LastSet::append(const LastSet &set)
{
  size_t oldSize = size();
  resize(size() + set.size());
  for (size_t i = 0; i < set.size(); i++)
    (*this)[oldSize + i] = set[i];
}

#ifdef SP_NAMESPACE
}
#endif