1 // Copyright (c) 1997 James Clark
2 // See the file copying.txt for copying permission.
3
4 #include "stylelib.h"
5 #include "Pattern.h"
6 #include "macros.h"
7 #include "Vector.h"
8 #include "Interpreter.h"
9
10 #ifdef DSSSL_NAMESPACE
11 namespace DSSSL_NAMESPACE {
12 #endif
13
Pattern()14 Pattern::Pattern()
15 : trivial_(0)
16 {
17 }
18
Pattern(IList<Element> & ancestors)19 Pattern::Pattern(IList<Element> &ancestors)
20 : trivial_(computeTrivial(ancestors))
21 {
22 ancestors_.swap(ancestors);
23 }
24
computeTrivial(const IList<Element> & ancestors)25 bool Pattern::computeTrivial(const IList<Element> &ancestors)
26 {
27 IListIter<Element> iter(ancestors);
28 if (iter.done())
29 return 1;
30 if (!iter.cur()->trivial())
31 return 0;
32 iter.next();
33 if (!iter.done())
34 return 0;
35 return 1;
36 }
37
Element(const StringC & gi)38 Pattern::Element::Element(const StringC &gi)
39 : gi_(gi), minRepeat_(1), maxRepeat_(1)
40 {
41 }
42
matches(const NodePtr & nd,MatchContext & context) const43 bool Pattern::Element::matches(const NodePtr &nd, MatchContext &context) const
44 {
45 if (gi_.size()) {
46 if (!nd->hasGi(GroveString(gi_.data(), gi_.size())))
47 return 0;
48 }
49 else {
50 GroveString tem;
51 if (nd->getGi(tem) != accessOK)
52 return 0;
53 }
54 for (IListIter<Qualifier> iter(qualifiers_); !iter.done(); iter.next())
55 if (!iter.cur()->satisfies(nd, context))
56 return 0;
57 return 1;
58 }
59
trivial() const60 bool Pattern::Element::trivial() const
61 {
62 if (minRepeat_ > 1)
63 return 0;
64 for (IListIter<Qualifier> iter(qualifiers_); !iter.done(); iter.next())
65 if (!iter.cur()->vacuous())
66 return 0;
67 return 1;
68 }
69
contributeSpecificity(int * s) const70 void Pattern::Element::contributeSpecificity(int *s) const
71 {
72 if (gi_.size())
73 s[giSpecificity] += minRepeat_;
74 for (IListIter<Qualifier> iter(qualifiers_); !iter.done(); iter.next())
75 iter.cur()->contributeSpecificity(s);
76 if (minRepeat_ != maxRepeat_)
77 s[repeatSpecificity] -= 1;
78 }
79
~Qualifier()80 Pattern::Qualifier::~Qualifier()
81 {
82 }
83
vacuous() const84 bool Pattern::Qualifier::vacuous() const
85 {
86 return 0;
87 }
88
matchAttribute(const StringC & name,const StringC & value,const NodePtr & nd,MatchContext & context)89 bool Pattern::Qualifier::matchAttribute(const StringC &name,
90 const StringC &value,
91 const NodePtr &nd,
92 MatchContext &context)
93 {
94 NamedNodeListPtr atts;
95 if (nd->getAttributes(atts) != accessOK)
96 return 0;
97 NodePtr att;
98 if (atts->namedNode(GroveString(name.data(), name.size()), att) != accessOK)
99 return 0;
100 bool implied;
101 if (att->getImplied(implied) == accessOK && implied)
102 return 0;
103 GroveString tokens;
104 if (att->tokens(tokens) == accessOK) {
105 if (tokens.size() != value.size())
106 return 0;
107 NodePtr node;
108 NamedNodeListPtr normalizer;
109 if (att->firstChild(node) != accessOK
110 || node->getEntity(node) != accessOK
111 || node->getGroveRoot(node) != accessOK
112 || node->getEntities(normalizer) != accessOK)
113 normalizer = atts;
114 StringC tem(value);
115 tem.resize(normalizer->normalize(&tem[0], tem.size()));
116 if (tokens != GroveString(tem.data(), tem.size()))
117 return 0;
118 }
119 else {
120 NodePtr tem;
121 StringC s;
122 if (att->firstChild(tem) == accessOK) {
123 do {
124 GroveString chunk;
125 if (tem->charChunk(context, chunk) == accessOK)
126 s.append(chunk.data(), chunk.size());
127 } while (tem.assignNextChunkSibling() == accessOK);
128 }
129 if (s != value)
130 return 0;
131 }
132 return 1;
133 }
134
ChildrenQualifier(IList<Element> & children)135 Pattern::ChildrenQualifier::ChildrenQualifier(IList<Element> &children)
136 {
137 children.swap(children_);
138 }
139
satisfies(const NodePtr & nd,MatchContext & context) const140 bool Pattern::ChildrenQualifier::satisfies(const NodePtr &nd,
141 MatchContext &context) const
142 {
143 ASSERT(!children_.empty());
144 NodePtr child;
145 if (nd->firstChild(child) != accessOK)
146 return 0;
147 Vector<const Element *> toMatch;
148 for (IListIter<Element> iter(children_); !iter.done(); iter.next())
149 toMatch.push_back(iter.cur());
150 do {
151 size_t j = 0;
152 for (size_t i = 0; i < toMatch.size(); i++) {
153 if (!toMatch[i]->matches(child, context)) {
154 if (j != i)
155 toMatch[j] = toMatch[i];
156 j++;
157 }
158 }
159 if (j == 0)
160 return 1;
161 toMatch.resize(j);
162 } while (child.assignNextChunkSibling() == accessOK);
163 return 0;
164 }
165
contributeSpecificity(int * s) const166 void Pattern::ChildrenQualifier::contributeSpecificity(int *s) const
167 {
168 for (IListIter<Element> iter(children_); !iter.done(); iter.next())
169 iter.cur()->contributeSpecificity(s);
170 }
171
IdQualifier(const StringC & id)172 Pattern::IdQualifier::IdQualifier(const StringC &id)
173 : id_(id)
174 {
175 }
176
satisfies(const NodePtr & nd,MatchContext & context) const177 bool Pattern::IdQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
178 {
179 GroveString nodeId;
180 if (nd->getId(nodeId) == accessOK) {
181 size_t len = id_.size();
182 if (nodeId.size() == len) {
183 StringC tem(id_);
184 Interpreter::normalizeGeneralName(nd, tem);
185 GroveString patternId(tem.data(), tem.size());
186 if (patternId == nodeId)
187 return 1;
188 }
189 }
190 const Vector<StringC> &idAtts = context.idAttributeNames();
191 for (size_t i = 0; i < idAtts.size(); i++)
192 if (matchAttribute(idAtts[i], id_, nd, context))
193 return 1;
194 return 0;
195 }
196
contributeSpecificity(int * s) const197 void Pattern::IdQualifier::contributeSpecificity(int *s) const
198 {
199 s[idSpecificity] += 1;
200 }
201
ClassQualifier(const StringC & cls)202 Pattern::ClassQualifier::ClassQualifier(const StringC &cls)
203 : class_(cls)
204 {
205 }
206
satisfies(const NodePtr & nd,MatchContext & context) const207 bool Pattern::ClassQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
208 {
209 const Vector<StringC> &classAtts = context.classAttributeNames();
210 for (size_t i = 0; i < classAtts.size(); i++)
211 if (matchAttribute(classAtts[i], class_, nd, context))
212 return 1;
213 return 0;
214 }
215
contributeSpecificity(int * s) const216 void Pattern::ClassQualifier::contributeSpecificity(int *s) const
217 {
218 s[classSpecificity] += 1;
219 }
220
AttributeHasValueQualifier(const StringC & name)221 Pattern::AttributeHasValueQualifier::AttributeHasValueQualifier(const StringC &name)
222 : name_(name)
223 {
224 }
225
satisfies(const NodePtr & nd,MatchContext & context) const226 bool Pattern::AttributeHasValueQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
227 {
228 NamedNodeListPtr atts;
229 if (nd->getAttributes(atts) != accessOK)
230 return 0;
231 NodePtr att;
232 if (atts->namedNode(GroveString(name_.data(), name_.size()), att) != accessOK)
233 return 0;
234 bool implied;
235 if (att->getImplied(implied) == accessOK && implied)
236 return 0;
237 return 1;
238 }
239
contributeSpecificity(int * s) const240 void Pattern::AttributeHasValueQualifier::contributeSpecificity(int *s) const
241 {
242 s[attributeSpecificity] += 1;
243 }
244
AttributeMissingValueQualifier(const StringC & name)245 Pattern::AttributeMissingValueQualifier::AttributeMissingValueQualifier(const StringC &name)
246 : name_(name)
247 {
248 }
249
satisfies(const NodePtr & nd,MatchContext & context) const250 bool Pattern::AttributeMissingValueQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
251 {
252 NamedNodeListPtr atts;
253 if (nd->getAttributes(atts) != accessOK)
254 return 1;
255 NodePtr att;
256 if (atts->namedNode(GroveString(name_.data(), name_.size()), att) != accessOK)
257 return 1;
258 bool implied;
259 if (att->getImplied(implied) == accessOK && implied)
260 return 1;
261 return 0;
262 }
263
contributeSpecificity(int * s) const264 void Pattern::AttributeMissingValueQualifier::contributeSpecificity(int *s) const
265 {
266 s[attributeSpecificity] += 1;
267 }
268
AttributeQualifier(const StringC & name,const StringC & value)269 Pattern::AttributeQualifier::AttributeQualifier(const StringC &name, const StringC &value)
270 : name_(name), value_(value)
271 {
272 }
273
satisfies(const NodePtr & nd,MatchContext & context) const274 bool Pattern::AttributeQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
275 {
276 return matchAttribute(name_, value_, nd, context);
277 }
278
contributeSpecificity(int * s) const279 void Pattern::AttributeQualifier::contributeSpecificity(int *s) const
280 {
281 s[attributeSpecificity] += 1;
282 }
283
contributeSpecificity(int * s) const284 void Pattern::PositionQualifier::contributeSpecificity(int *s) const
285 {
286 s[positionSpecificity] += 1;
287 }
288
satisfies(const NodePtr & nd,MatchContext & context) const289 bool Pattern::FirstOfTypeQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
290 {
291 GroveString ndType;
292 nd->getGi(ndType);
293 NodePtr tem;
294 if (nd->firstSibling(tem) != accessOK)
295 return 1; // must be document element
296 while (*tem != *nd) {
297 GroveString temType;
298 if (tem->getGi(temType) == accessOK && temType == ndType)
299 return 0;
300 tem.assignNextChunkSibling();
301 }
302 return 1;
303 }
304
satisfies(const NodePtr & nd,MatchContext & context) const305 bool Pattern::LastOfTypeQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
306 {
307 NodePtr tem;
308 if (nd->nextChunkSibling(tem) != accessOK)
309 return 1;
310 GroveString ndType;
311 nd->getGi(ndType);
312 do {
313 GroveString temType;
314 if (tem->getGi(temType) == accessOK && temType == ndType)
315 return 0;
316 } while (tem.assignNextChunkSibling() == accessOK);
317 return 1;
318 }
319
satisfies(const NodePtr & nd,MatchContext &) const320 bool Pattern::FirstOfAnyQualifier::satisfies(const NodePtr &nd, MatchContext &) const
321 {
322 NodePtr tem;
323 if (nd->firstSibling(tem) != accessOK)
324 return 1; // must be document element
325 while (*tem != *nd) {
326 GroveString temType;
327 if (tem->getGi(temType) == accessOK)
328 return 0;
329 tem.assignNextChunkSibling();
330 }
331 return 1;
332 }
333
satisfies(const NodePtr & nd,MatchContext & context) const334 bool Pattern::LastOfAnyQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
335 {
336 NodePtr tem;
337 if (nd->nextChunkSibling(tem) != accessOK)
338 return 1;
339 GroveString ndType;
340 nd->getGi(ndType);
341 do {
342 GroveString temType;
343 if (tem->getGi(temType) == accessOK)
344 return 0;
345 } while (tem.assignNextChunkSibling() == accessOK);
346 return 1;
347 }
348
contributeSpecificity(int * s) const349 void Pattern::OnlyQualifier::contributeSpecificity(int *s) const
350 {
351 s[onlySpecificity] += 1;
352 }
353
satisfies(const NodePtr & nd,MatchContext & context) const354 bool Pattern::OnlyOfTypeQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
355 {
356 GroveString ndType;
357 nd->getGi(ndType);
358 NodePtr tem;
359 if (nd->firstSibling(tem) != accessOK)
360 return 1; // must be document element
361 unsigned count = 0;
362 do {
363 GroveString temType;
364 if (tem->getGi(temType) == accessOK && temType == ndType) {
365 if (count++)
366 return 0;
367 }
368 } while (tem.assignNextChunkSibling() == accessOK);
369 return 1;
370 }
371
satisfies(const NodePtr & nd,MatchContext & context) const372 bool Pattern::OnlyOfAnyQualifier::satisfies(const NodePtr &nd, MatchContext &context) const
373 {
374 NodePtr tem;
375 if (nd->firstSibling(tem) != accessOK)
376 return 1; // must be document element
377 unsigned count = 0;
378 do {
379 GroveString temType;
380 if (tem->getGi(temType) == accessOK) {
381 if (count++)
382 return 0;
383 }
384 } while (tem.assignNextChunkSibling() == accessOK);
385 return 1;
386 }
387
vacuous() const388 bool Pattern::VacuousQualifier::vacuous() const
389 {
390 return 1;
391 }
392
PriorityQualifier(long n)393 Pattern::PriorityQualifier::PriorityQualifier(long n)
394 : n_(n)
395 {
396 }
397
contributeSpecificity(int * s) const398 void Pattern::PriorityQualifier::contributeSpecificity(int *s) const
399 {
400 s[prioritySpecificity] += n_;
401 }
402
satisfies(const NodePtr &,MatchContext &) const403 bool Pattern::PriorityQualifier::satisfies(const NodePtr &, MatchContext &) const
404 {
405 return 1;
406 }
407
ImportanceQualifier(long n)408 Pattern::ImportanceQualifier::ImportanceQualifier(long n)
409 : n_(n)
410 {
411 }
412
contributeSpecificity(int * s) const413 void Pattern::ImportanceQualifier::contributeSpecificity(int *s) const
414 {
415 s[importanceSpecificity] += n_;
416 }
417
satisfies(const NodePtr &,MatchContext &) const418 bool Pattern::ImportanceQualifier::satisfies(const NodePtr &, MatchContext &) const
419 {
420 return 1;
421 }
422
matchAncestors1(const IListIter<Element> & ancestors,const NodePtr & node,MatchContext & context)423 bool Pattern::matchAncestors1(const IListIter<Element> &ancestors,
424 const NodePtr &node,
425 MatchContext &context)
426 {
427 const Element &r = *ancestors.cur();
428 NodePtr tem(node);
429 for (Repeat i = 0; i < r.minRepeat(); i++) {
430 if (!tem || !r.matches(tem, context))
431 return 0;
432 if (tem->getParent(tem) != accessOK)
433 tem.clear();
434 }
435 Repeat i = r.minRepeat();
436 for (;;) {
437 IListIter<Element> up(ancestors);
438 up.next();
439 if (matchAncestors(up, tem, context))
440 break;
441 if (i == r.maxRepeat() || !tem || !r.matches(tem, context))
442 return 0;
443 i++;
444 if (tem->getParent(tem) != accessOK)
445 tem.clear();
446 }
447 return 1;
448 }
449
computeSpecificity(int * s) const450 void Pattern::computeSpecificity(int *s) const
451 {
452 for (int i = 0; i < nSpecificity; i++)
453 s[i] = 0;
454 for (IListIter<Element> iter(ancestors_); !iter.done(); iter.next())
455 iter.cur()->contributeSpecificity(s);
456 }
457
compareSpecificity(const Pattern & pattern1,const Pattern & pattern2)458 int Pattern::compareSpecificity(const Pattern &pattern1, const Pattern &pattern2)
459 {
460 int s1[nSpecificity];
461 int s2[nSpecificity];
462 int i; // declare here to avoid gcc bug
463 pattern1.computeSpecificity(s1);
464 pattern2.computeSpecificity(s2);
465 for (i = 0; i < nSpecificity; i++) {
466 if (s1[i] != s2[i])
467 return s1[i] > s2[i] ? -1 : 1;
468 }
469 return 0;
470 }
471
472 #ifdef DSSSL_NAMESPACE
473 }
474 #endif
475