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 librararies 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)
49 ModelGroup::Connector AndModelGroup::connector() const
54 OrModelGroup::OrModelGroup(NCVector<Owner<ContentToken> > &v,
55 ContentToken::OccurrenceIndicator oi)
61 ModelGroup::Connector OrModelGroup::connector() const
67 SeqModelGroup::SeqModelGroup(NCVector<Owner<ContentToken> > &v,
68 ContentToken::OccurrenceIndicator oi)
73 ModelGroup::Connector SeqModelGroup::connector() const
79 ModelGroup::ModelGroup(NCVector<Owner<ContentToken> > &v,
80 OccurrenceIndicator oi)
86 unsigned long ModelGroup::grpgtcnt() const
88 unsigned long cnt = 1;
89 for (size_t i = 0; i < members_.size(); i++)
90 cnt += members_[i]->grpgtcnt();
94 void ModelGroup::setOrGroup()
96 for (size_t i = 0; i < members_.size(); i++)
97 members_[i]->setOrGroupMember();
100 const ModelGroup *ModelGroup::asModelGroup() const
105 ElementToken::ElementToken(const ElementType *element, OccurrenceIndicator oi)
106 : LeafContentToken(element, oi)
110 ContentToken::ContentToken(OccurrenceIndicator oi)
111 : occurrenceIndicator_(oi)
115 unsigned long ContentToken::grpgtcnt() const
120 void ContentToken::setOrGroupMember()
124 const ModelGroup *ContentToken::asModelGroup() const
129 const LeafContentToken *ContentToken::asLeafContentToken() const
134 LeafContentToken::LeafContentToken(const ElementType *element,
135 OccurrenceIndicator oi)
136 : element_(element), ContentToken(oi), isFinal_(0), orGroupMember_(0),
137 requiredIndex_(size_t(-1))
141 Boolean LeafContentToken::isInitial() const
146 void LeafContentToken::setOrGroupMember()
151 const LeafContentToken *LeafContentToken::asLeafContentToken() const
156 PcdataToken::PcdataToken()
157 : LeafContentToken(0, rep)
161 InitialPseudoToken::InitialPseudoToken()
162 : LeafContentToken(0, none)
166 Boolean InitialPseudoToken::isInitial() const
171 DataTagGroup::DataTagGroup(NCVector<Owner<ContentToken> > &vec,
172 OccurrenceIndicator oi)
173 : SeqModelGroup(vec, oi)
177 DataTagElementToken::DataTagElementToken(const ElementType *element,
178 Vector<Text> &templates,
179 Text &paddingTemplate)
180 : ElementToken(element, ContentToken::none),
181 havePaddingTemplate_(1)
183 templates.swap(templates_);
184 paddingTemplate.swap(paddingTemplate_);
187 DataTagElementToken::DataTagElementToken(const ElementType *element,
188 Vector<Text> &templates)
189 : ElementToken(element, ContentToken::none),
190 havePaddingTemplate_(0)
192 templates.swap(templates_);
195 ContentToken::~ContentToken()
200 unsigned nextLeafIndex;
201 PackedBoolean containsPcdata;
202 unsigned andStateSize;
203 Vector<unsigned> nextTypeIndex;
208 GroupInfo::GroupInfo(size_t nType)
209 : nextTypeIndex(nType, 0), nextLeafIndex(0), containsPcdata(0), andStateSize(0)
213 CompiledModelGroup::CompiledModelGroup(Owner<ModelGroup> &modelGroup)
214 : modelGroup_(modelGroup.extract())
218 void CompiledModelGroup::compile(size_t nElementTypeIndex,
219 Vector<ContentModelAmbiguity> &ambiguities,
220 Boolean &pcdataUnreachable)
224 GroupInfo info(nElementTypeIndex);
225 modelGroup_->analyze(info, 0, 0, first, last);
226 for (unsigned i = 0; i < last.size(); i++)
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,
241 modelGroup_->finish(minAndDepth, elementTransition, ambiguities,
243 if (!containsPcdata_)
244 pcdataUnreachable = 0;
247 void ModelGroup::finish(Vector<unsigned> &minAndDepth,
248 Vector<size_t> &elementTransition,
249 Vector<ContentModelAmbiguity> &ambiguities,
250 Boolean &pcdataUnreachable)
252 for (unsigned i = 0; i < nMembers(); i++)
253 member(i).finish(minAndDepth, elementTransition, ambiguities,
257 void LeafContentToken::finish(Vector<unsigned> &minAndDepthVec,
258 Vector<size_t> &elementTransitionVec,
259 Vector<ContentModelAmbiguity> &ambiguities,
260 Boolean &pcdataUnreachable)
263 andFinish(minAndDepthVec, elementTransitionVec, ambiguities,
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
275 size_t n = follow_.size();
276 Vector<LeafContentToken *>::iterator follow = follow_.begin();
278 for (size_t i = 0; i < n; i++) {
279 unsigned &minDepth = minAndDepth[follow[i]->index()];
283 follow[j] = follow[i];
284 if (i == requiredIndex_)
286 const ElementType *e = follow[i]->elementType();
289 if (!follow[i]->andInfo_) {
290 simplePcdataTransition_ = follow[i];
291 pcdataTransitionType_ = 1;
294 pcdataTransitionType_ = 2;
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();
313 elementTransition[ei] = j;
317 if (pcdataTransitionType_ == 0)
318 pcdataUnreachable = 1;
322 void LeafContentToken::andFinish(Vector<unsigned> &minAndDepthVec,
323 Vector<size_t> &elementTransitionVec,
324 Vector<ContentModelAmbiguity> &ambiguities,
325 Boolean &pcdataUnreachable)
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;
340 // follow_ is in decreasing order of andDepth because of how it's
342 size_t n = follow_.size();
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;
351 follow_[j] = follow_[i];
352 andFollow[j] = andFollow[i];
354 if (i == requiredIndex_)
356 const ElementType *e = follow_[i]->elementType();
359 if (pcdataTransitionType_ == 0) {
360 const AndModelGroup *andAncestor = andInfo_->andAncestor;
361 unsigned groupIndex = andInfo_->andGroupIndex;
363 Boolean hasNonNull = 0;
364 for (unsigned k = 0; k < andAncestor->nMembers(); k++)
366 && !andAncestor->member(k).inherentlyOptional()) {
371 if (minDepth <= andAncestor->andDepth())
372 pcdataUnreachable = 1;
375 groupIndex = andAncestor->andGroupIndex();
376 andAncestor = andAncestor->andAncestor();
377 } while (andAncestor);
378 if (andFollow[i].isolated)
379 pcdataMinCovered = minDepth;
380 pcdataTransitionType_ = 2;
383 if (pcdataMinCovered > minDepth + 1)
384 pcdataUnreachable = 1;
385 pcdataMinCovered = andFollow[i].isolated ? minDepth : 0;
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();
410 a.andDepth = andFollow[i].andDepth;
412 if (andFollow[previ].isolated)
413 elementTransition[ei] = j;
416 elementTransition[ei] = j;
420 if (pcdataMinCovered > 0 || pcdataTransitionType_ == 0)
421 pcdataUnreachable = 1;
423 andInfo_->follow.resize(j);
426 void ContentToken::analyze(GroupInfo &info,
427 const AndModelGroup *andAncestor,
428 unsigned andGroupIndex,
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));
442 void LeafContentToken::analyze1(GroupInfo &info,
443 const AndModelGroup *andAncestor,
444 unsigned andGroupIndex,
448 leafIndex_ = info.nextLeafIndex++;
449 typeIndex_ = info.nextTypeIndex[element_ ? element_->index() : 0]++;
451 andInfo_ = new AndInfo;
452 andInfo_->andAncestor = andAncestor;
453 andInfo_->andGroupIndex = andGroupIndex;
456 last.assign(1, this);
457 inherentlyOptional_ = 0;
460 void PcdataToken::analyze1(GroupInfo &info,
461 const AndModelGroup *andAncestor,
462 unsigned andGroupIndex,
466 info.containsPcdata = 1;
467 LeafContentToken::analyze1(info, andAncestor, andGroupIndex, first, last);
470 void OrModelGroup::analyze1(GroupInfo &info,
471 const AndModelGroup *andAncestor,
472 unsigned andGroupIndex,
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++) {
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();
490 void SeqModelGroup::analyze1(GroupInfo &info,
491 const AndModelGroup *andAncestor,
492 unsigned andGroupIndex,
496 member(0).analyze(info, andAncestor, andGroupIndex, first, last);
497 inherentlyOptional_ = member(0).inherentlyOptional();
498 for (unsigned i = 1; i < nMembers(); i++) {
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);
510 inherentlyOptional_ &= member(i).inherentlyOptional();
514 void AndModelGroup::analyze1(GroupInfo &info,
515 const AndModelGroup *andAncestor,
516 unsigned andGroupIndex,
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]);
530 first.setNotRequired();
532 inherentlyOptional_ = member(0).inherentlyOptional();
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();
541 for (i = 0; i < nMembers(); i++) {
542 for (unsigned j = 0; j < nMembers(); j++)
544 addTransitions(lastVec[i], firstVec[j], 0,
545 andIndex() + nMembers(),
547 !member(j).inherentlyOptional(),
548 andIndex() + j, andIndex() + i);
552 void ContentToken::addTransitions(const LastSet &from,
554 Boolean maybeRequired,
555 unsigned andClearIndex,
558 unsigned requireClear,
561 size_t length = from.size();
562 for (unsigned i = 0; i < length; i++)
563 from[i]->addTransitions(to,
572 void LeafContentToken::addTransitions(const FirstSet &to,
573 Boolean maybeRequired,
574 unsigned andClearIndex,
577 unsigned requireClear,
580 if (maybeRequired && to.requiredIndex() != size_t(-1)) {
581 ASSERT(requiredIndex_ == size_t(-1));
582 requiredIndex_ = to.requiredIndex() + follow_.size();
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);
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;
602 AndState::AndState(unsigned n)
603 : v_(n, PackedBoolean(0)), clearFrom_(0)
607 void AndState::clearFrom1(unsigned i)
609 while (clearFrom_ > i)
610 v_[--clearFrom_] = 0;
613 MatchState::MatchState()
618 MatchState::MatchState(const CompiledModelGroup *model)
619 : pos_(model ? model->initial() : 0),
620 andState_(model ? model->andStateSize() : 0),
625 const LeafContentToken *MatchState::invalidExclusion(const ElementType *e)
628 const LeafContentToken *token = pos_->transitionToken(e, andState_,
630 if (token && !token->inherentlyOptional() && !token->orGroupMember())
636 Boolean MatchState::operator==(const MatchState &state) const
638 return (pos_ == state.pos_ && andState_ == state.andState_
639 && minAndDepth_ == state.minAndDepth_);
642 Boolean AndState::operator==(const AndState &state) const
644 ASSERT(v_.size() == state.v_.size());
645 for (size_t i = 0; i < v_.size(); i++) {
646 if (i >= clearFrom_ && i >= state.clearFrom_)
648 if (v_[i] != state.v_[i])
654 const LeafContentToken *
655 LeafContentToken::transitionToken(const ElementType *to,
656 const AndState &andState,
657 unsigned minAndDepth) const
659 Vector<LeafContentToken *>::const_iterator p = follow_.begin();
661 for (size_t n = follow_.size(); n > 0; n--, p++)
662 if ((*p)->elementType() == to)
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))
678 LeafContentToken::tryTransition(const ElementType *to,
680 unsigned &minAndDepth,
681 const LeafContentToken *&newpos) const
683 Vector<LeafContentToken *>::const_iterator p = follow_.begin();
685 for (size_t n = follow_.size(); n > 0; n--, p++) {
686 if ((*p)->elementType() == to) {
688 minAndDepth = newpos->computeMinAndDepth(andState);
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);
704 minAndDepth = newpos->computeMinAndDepth(andState);
713 LeafContentToken::possibleTransitions(const AndState &andState,
714 unsigned minAndDepth,
715 Vector<const ElementType *> &v) const
717 Vector<LeafContentToken *>::const_iterator p = follow_.begin();
719 for (size_t n = follow_.size(); n > 0; n--, p++)
720 v.push_back((*p)->elementType());
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());
732 unsigned LeafContentToken::computeMinAndDepth1(const AndState &andState) const
735 unsigned groupIndex = andInfo_->andGroupIndex;
736 for (const AndModelGroup *group = andInfo_->andAncestor;
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;
746 const LeafContentToken *
747 LeafContentToken::impliedStartTag(const AndState &andState,
748 unsigned minAndDepth) const
750 if (requiredIndex_ != size_t(-1)) {
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_];
762 void LeafContentToken::doRequiredTransition(AndState &andState,
763 unsigned &minAndDepth,
764 const LeafContentToken *&newpos)
767 ASSERT(requiredIndex_ != size_t(-1));
769 const Transition &t = andInfo_->follow[requiredIndex_];
770 if (t.toSet != unsigned(Transition::invalidIndex))
771 andState.set(t.toSet);
772 andState.clearFrom(t.clearAndStateStartIndex);
774 newpos = follow_[requiredIndex_];
775 minAndDepth = newpos->computeMinAndDepth(andState);
779 : requiredIndex_(size_t(-1))
783 void FirstSet::init(LeafContentToken *p)
790 void FirstSet::append(const FirstSet &set)
792 if (set.requiredIndex_ != size_t(-1)) {
793 ASSERT(requiredIndex_ == size_t(-1));
794 requiredIndex_ = set.requiredIndex_ + v_.size();
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];
802 void LastSet::append(const LastSet &set)
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];