2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
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.
28 #pragma implementation
32 #include "ContentToken.h"
34 #include "ElementType.h"
37 #include "MessageArg.h"
40 namespace SP_NAMESPACE {
43 AndModelGroup::AndModelGroup(NCVector<Owner<ContentToken> > &v,
44 ContentToken::OccurrenceIndicator oi)
45 : ModelGroup(v, oi), andDepth_(0), andIndex_(0), andGroupIndex_(0),
50 ModelGroup::Connector AndModelGroup::connector() const
55 OrModelGroup::OrModelGroup(NCVector<Owner<ContentToken> > &v,
56 ContentToken::OccurrenceIndicator oi)
62 ModelGroup::Connector OrModelGroup::connector() const
68 SeqModelGroup::SeqModelGroup(NCVector<Owner<ContentToken> > &v,
69 ContentToken::OccurrenceIndicator oi)
74 ModelGroup::Connector SeqModelGroup::connector() const
80 ModelGroup::ModelGroup(NCVector<Owner<ContentToken> > &v,
81 OccurrenceIndicator oi)
87 unsigned long ModelGroup::grpgtcnt() const
89 unsigned long cnt = 1;
90 for (size_t i = 0; i < members_.size(); i++)
91 cnt += members_[i]->grpgtcnt();
95 void ModelGroup::setOrGroup()
97 for (size_t i = 0; i < members_.size(); i++)
98 members_[i]->setOrGroupMember();
101 const ModelGroup *ModelGroup::asModelGroup() const
106 ElementToken::ElementToken(const ElementType *element, OccurrenceIndicator oi)
107 : LeafContentToken(element, oi)
111 ContentToken::ContentToken(OccurrenceIndicator oi)
112 : occurrenceIndicator_(oi),
113 inherentlyOptional_(0)
117 unsigned long ContentToken::grpgtcnt() const
122 void ContentToken::setOrGroupMember()
126 const ModelGroup *ContentToken::asModelGroup() const
131 const LeafContentToken *ContentToken::asLeafContentToken() const
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)
144 Boolean LeafContentToken::isInitial() const
149 void LeafContentToken::setOrGroupMember()
154 const LeafContentToken *LeafContentToken::asLeafContentToken() const
159 PcdataToken::PcdataToken()
160 : LeafContentToken(0, rep)
164 InitialPseudoToken::InitialPseudoToken()
165 : LeafContentToken(0, none)
169 Boolean InitialPseudoToken::isInitial() const
174 DataTagGroup::DataTagGroup(NCVector<Owner<ContentToken> > &vec,
175 OccurrenceIndicator oi)
176 : SeqModelGroup(vec, oi)
180 DataTagElementToken::DataTagElementToken(const ElementType *element,
181 Vector<Text> &templates,
182 Text &paddingTemplate)
183 : ElementToken(element, ContentToken::none),
184 havePaddingTemplate_(1)
186 templates.swap(templates_);
187 paddingTemplate.swap(paddingTemplate_);
190 DataTagElementToken::DataTagElementToken(const ElementType *element,
191 Vector<Text> &templates)
192 : ElementToken(element, ContentToken::none),
193 havePaddingTemplate_(0)
195 templates.swap(templates_);
198 ContentToken::~ContentToken()
203 unsigned nextLeafIndex;
204 PackedBoolean containsPcdata;
205 unsigned andStateSize;
206 Vector<unsigned> nextTypeIndex;
211 GroupInfo::GroupInfo(size_t nType)
212 : nextTypeIndex(nType, 0), nextLeafIndex(0), containsPcdata(0), andStateSize(0)
216 CompiledModelGroup::CompiledModelGroup(Owner<ModelGroup> &modelGroup)
217 : modelGroup_(modelGroup.extract()), andStateSize_(0), containsPcdata_(false)
221 void CompiledModelGroup::compile(size_t nElementTypeIndex,
222 Vector<ContentModelAmbiguity> &ambiguities,
223 Boolean &pcdataUnreachable)
227 GroupInfo info(nElementTypeIndex);
228 modelGroup_->analyze(info, 0, 0, first, last);
229 for (unsigned i = 0; i < last.size(); i++)
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,
244 modelGroup_->finish(minAndDepth, elementTransition, ambiguities,
246 if (!containsPcdata_)
247 pcdataUnreachable = 0;
250 void ModelGroup::finish(Vector<unsigned> &minAndDepth,
251 Vector<size_t> &elementTransition,
252 Vector<ContentModelAmbiguity> &ambiguities,
253 Boolean &pcdataUnreachable)
255 for (unsigned i = 0; i < nMembers(); i++)
256 member(i).finish(minAndDepth, elementTransition, ambiguities,
260 void LeafContentToken::finish(Vector<unsigned> &minAndDepthVec,
261 Vector<size_t> &elementTransitionVec,
262 Vector<ContentModelAmbiguity> &ambiguities,
263 Boolean &pcdataUnreachable)
266 andFinish(minAndDepthVec, elementTransitionVec, ambiguities,
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
278 size_t n = follow_.size();
279 Vector<LeafContentToken *>::iterator follow = follow_.begin();
281 for (size_t i = 0; i < n; i++) {
282 unsigned &minDepth = minAndDepth[follow[i]->index()];
286 follow[j] = follow[i];
287 if (i == requiredIndex_)
289 const ElementType *e = follow[i]->elementType();
292 if (!follow[i]->andInfo_) {
293 simplePcdataTransition_ = follow[i];
294 pcdataTransitionType_ = 1;
297 pcdataTransitionType_ = 2;
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();
316 elementTransition[ei] = j;
320 if (pcdataTransitionType_ == 0)
321 pcdataUnreachable = 1;
325 void LeafContentToken::andFinish(Vector<unsigned> &minAndDepthVec,
326 Vector<size_t> &elementTransitionVec,
327 Vector<ContentModelAmbiguity> &ambiguities,
328 Boolean &pcdataUnreachable)
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;
343 // follow_ is in decreasing order of andDepth because of how it's
345 size_t n = follow_.size();
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;
354 follow_[j] = follow_[i];
355 andFollow[j] = andFollow[i];
357 if (i == requiredIndex_)
359 const ElementType *e = follow_[i]->elementType();
362 if (pcdataTransitionType_ == 0) {
363 const AndModelGroup *andAncestor = andInfo_->andAncestor;
364 unsigned groupIndex = andInfo_->andGroupIndex;
366 Boolean hasNonNull = 0;
367 for (unsigned k = 0; k < andAncestor->nMembers(); k++)
369 && !andAncestor->member(k).inherentlyOptional()) {
374 if (minDepth <= andAncestor->andDepth())
375 pcdataUnreachable = 1;
378 groupIndex = andAncestor->andGroupIndex();
379 andAncestor = andAncestor->andAncestor();
380 } while (andAncestor);
381 if (andFollow[i].isolated)
382 pcdataMinCovered = minDepth;
383 pcdataTransitionType_ = 2;
386 if (pcdataMinCovered > minDepth + 1)
387 pcdataUnreachable = 1;
388 pcdataMinCovered = andFollow[i].isolated ? minDepth : 0;
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();
413 a.andDepth = andFollow[i].andDepth;
415 if (andFollow[previ].isolated)
416 elementTransition[ei] = j;
419 elementTransition[ei] = j;
423 if (pcdataMinCovered > 0 || pcdataTransitionType_ == 0)
424 pcdataUnreachable = 1;
426 andInfo_->follow.resize(j);
429 void ContentToken::analyze(GroupInfo &info,
430 const AndModelGroup *andAncestor,
431 unsigned andGroupIndex,
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));
445 void LeafContentToken::analyze1(GroupInfo &info,
446 const AndModelGroup *andAncestor,
447 unsigned andGroupIndex,
451 leafIndex_ = info.nextLeafIndex++;
452 typeIndex_ = info.nextTypeIndex[element_ ? element_->index() : 0]++;
454 andInfo_ = new AndInfo;
455 andInfo_->andAncestor = andAncestor;
456 andInfo_->andGroupIndex = andGroupIndex;
459 last.assign(1, this);
460 inherentlyOptional_ = 0;
463 void PcdataToken::analyze1(GroupInfo &info,
464 const AndModelGroup *andAncestor,
465 unsigned andGroupIndex,
469 info.containsPcdata = 1;
470 LeafContentToken::analyze1(info, andAncestor, andGroupIndex, first, last);
473 void OrModelGroup::analyze1(GroupInfo &info,
474 const AndModelGroup *andAncestor,
475 unsigned andGroupIndex,
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++) {
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();
493 void SeqModelGroup::analyze1(GroupInfo &info,
494 const AndModelGroup *andAncestor,
495 unsigned andGroupIndex,
499 member(0).analyze(info, andAncestor, andGroupIndex, first, last);
500 inherentlyOptional_ = member(0).inherentlyOptional();
501 for (unsigned i = 1; i < nMembers(); i++) {
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);
513 inherentlyOptional_ &= member(i).inherentlyOptional();
517 void AndModelGroup::analyze1(GroupInfo &info,
518 const AndModelGroup *andAncestor,
519 unsigned andGroupIndex,
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]);
533 first.setNotRequired();
535 inherentlyOptional_ = member(0).inherentlyOptional();
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();
544 for (i = 0; i < nMembers(); i++) {
545 for (unsigned j = 0; j < nMembers(); j++)
547 addTransitions(lastVec[i], firstVec[j], 0,
548 andIndex() + nMembers(),
550 !member(j).inherentlyOptional(),
551 andIndex() + j, andIndex() + i);
555 void ContentToken::addTransitions(const LastSet &from,
557 Boolean maybeRequired,
558 unsigned andClearIndex,
561 unsigned requireClear,
564 size_t length = from.size();
565 for (unsigned i = 0; i < length; i++)
566 from[i]->addTransitions(to,
575 void LeafContentToken::addTransitions(const FirstSet &to,
576 Boolean maybeRequired,
577 unsigned andClearIndex,
580 unsigned requireClear,
583 if (maybeRequired && to.requiredIndex() != size_t(-1)) {
584 ASSERT(requiredIndex_ == size_t(-1));
585 requiredIndex_ = to.requiredIndex() + follow_.size();
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);
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;
605 AndState::AndState(unsigned n)
606 : v_(n, PackedBoolean(0)), clearFrom_(0)
610 void AndState::clearFrom1(unsigned i)
612 while (clearFrom_ > i)
613 v_[--clearFrom_] = 0;
616 MatchState::MatchState()
617 : andState_(0), pos_(NULL), minAndDepth_(0)
621 MatchState::MatchState(const CompiledModelGroup *model)
622 : pos_(model ? model->initial() : 0),
623 andState_(model ? model->andStateSize() : 0),
628 const LeafContentToken *MatchState::invalidExclusion(const ElementType *e)
631 const LeafContentToken *token = pos_->transitionToken(e, andState_,
633 if (token && !token->inherentlyOptional() && !token->orGroupMember())
639 Boolean MatchState::operator==(const MatchState &state) const
641 return (pos_ == state.pos_ && andState_ == state.andState_
642 && minAndDepth_ == state.minAndDepth_);
645 Boolean AndState::operator==(const AndState &state) const
647 ASSERT(v_.size() == state.v_.size());
648 for (size_t i = 0; i < v_.size(); i++) {
649 if (i >= clearFrom_ && i >= state.clearFrom_)
651 if (v_[i] != state.v_[i])
657 const LeafContentToken *
658 LeafContentToken::transitionToken(const ElementType *to,
659 const AndState &andState,
660 unsigned minAndDepth) const
662 Vector<LeafContentToken *>::const_iterator p = follow_.begin();
664 for (size_t n = follow_.size(); n > 0; n--, p++)
665 if ((*p)->elementType() == to)
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))
681 LeafContentToken::tryTransition(const ElementType *to,
683 unsigned &minAndDepth,
684 const LeafContentToken *&newpos) const
686 Vector<LeafContentToken *>::const_iterator p = follow_.begin();
688 for (size_t n = follow_.size(); n > 0; n--, p++) {
689 if ((*p)->elementType() == to) {
691 minAndDepth = newpos->computeMinAndDepth(andState);
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);
707 minAndDepth = newpos->computeMinAndDepth(andState);
716 LeafContentToken::possibleTransitions(const AndState &andState,
717 unsigned minAndDepth,
718 Vector<const ElementType *> &v) const
720 Vector<LeafContentToken *>::const_iterator p = follow_.begin();
722 for (size_t n = follow_.size(); n > 0; n--, p++)
723 v.push_back((*p)->elementType());
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());
735 unsigned LeafContentToken::computeMinAndDepth1(const AndState &andState) const
738 unsigned groupIndex = andInfo_->andGroupIndex;
739 for (const AndModelGroup *group = andInfo_->andAncestor;
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;
749 const LeafContentToken *
750 LeafContentToken::impliedStartTag(const AndState &andState,
751 unsigned minAndDepth) const
753 if (requiredIndex_ != size_t(-1)) {
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_];
765 void LeafContentToken::doRequiredTransition(AndState &andState,
766 unsigned &minAndDepth,
767 const LeafContentToken *&newpos)
770 ASSERT(requiredIndex_ != size_t(-1));
772 const Transition &t = andInfo_->follow[requiredIndex_];
773 if (t.toSet != unsigned(Transition::invalidIndex))
774 andState.set(t.toSet);
775 andState.clearFrom(t.clearAndStateStartIndex);
777 newpos = follow_[requiredIndex_];
778 minAndDepth = newpos->computeMinAndDepth(andState);
782 : requiredIndex_(size_t(-1))
786 void FirstSet::init(LeafContentToken *p)
793 void FirstSet::append(const FirstSet &set)
795 if (set.requiredIndex_ != size_t(-1)) {
796 ASSERT(requiredIndex_ == size_t(-1));
797 requiredIndex_ = set.requiredIndex_ + v_.size();
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];
805 void LastSet::append(const LastSet &set)
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];