1// sass.hpp must go before all system headers to get the
2// __EXTENSIONS__ fix on Solaris.
3#include "sass.hpp"
4
5#include "ast.hpp"
6#include "permutate.hpp"
7#include "dart_helpers.hpp"
8
9namespace Sass {
10
11 // ##########################################################################
12 // Returns whether or not [compound] contains a `::root` selector.
13 // ##########################################################################
14 bool hasRoot(const CompoundSelector* compound)
15 {
16 // Libsass does not yet know the root selector
17 return false;
18 }
19 // EO hasRoot
20
21 // ##########################################################################
22 // Returns whether a [CompoundSelector] may contain only
23 // one simple selector of the same type as [simple].
24 // ##########################################################################
25 bool isUnique(const SimpleSelector* simple)
26 {
27 if (Cast<IDSelector>(ptr: simple)) return true;
28 if (const PseudoSelector * pseudo = Cast<PseudoSelector>(ptr: simple)) {
29 if (pseudo->is_pseudo_element()) return true;
30 }
31 return false;
32 }
33 // EO isUnique
34
35 // ##########################################################################
36 // Returns whether [complex1] and [complex2] need to be unified to
37 // produce a valid combined selector. This is necessary when both
38 // selectors contain the same unique simple selector, such as an ID.
39 // ##########################################################################
40 bool mustUnify(
41 const sass::vector<SelectorComponentObj>& complex1,
42 const sass::vector<SelectorComponentObj>& complex2)
43 {
44
45 sass::vector<const SimpleSelector*> uniqueSelectors1;
46 for (const SelectorComponent* component : complex1) {
47 if (const CompoundSelector * compound = component->getCompound()) {
48 for (const SimpleSelector* sel : compound->elements()) {
49 if (isUnique(simple: sel)) {
50 uniqueSelectors1.push_back(x: sel);
51 }
52 }
53 }
54 }
55 if (uniqueSelectors1.empty()) return false;
56
57 // ToDo: unsure if this is correct
58 for (const SelectorComponent* component : complex2) {
59 if (const CompoundSelector * compound = component->getCompound()) {
60 for (const SimpleSelector* sel : compound->elements()) {
61 if (isUnique(simple: sel)) {
62 for (auto check : uniqueSelectors1) {
63 if (*check == *sel) return true;
64 }
65 }
66 }
67 }
68 }
69
70 return false;
71
72 }
73 // EO isUnique
74
75 // ##########################################################################
76 // Helper function used by `weaveParents`
77 // ##########################################################################
78 bool cmpGroups(
79 const sass::vector<SelectorComponentObj>& group1,
80 const sass::vector<SelectorComponentObj>& group2,
81 sass::vector<SelectorComponentObj>& select)
82 {
83
84 if (group1.size() == group2.size() && std::equal(first1: group1.begin(), last1: group1.end(), first2: group2.begin(), binary_pred: PtrObjEqualityFn<SelectorComponent>)) {
85 select = group1;
86 return true;
87 }
88
89 if (!Cast<CompoundSelector>(ptr: group1.front())) {
90 select = {};
91 return false;
92 }
93 if (!Cast<CompoundSelector>(ptr: group2.front())) {
94 select = {};
95 return false;
96 }
97
98 if (complexIsParentSuperselector(complex1: group1, complex2: group2)) {
99 select = group2;
100 return true;
101 }
102 if (complexIsParentSuperselector(complex1: group2, complex2: group1)) {
103 select = group1;
104 return true;
105 }
106
107 if (!mustUnify(complex1: group1, complex2: group2)) {
108 select = {};
109 return false;
110 }
111
112 sass::vector<sass::vector<SelectorComponentObj>> unified
113 = unifyComplex(complexes: { group1, group2 });
114 if (unified.empty()) return false;
115 if (unified.size() > 1) return false;
116 select = unified.front();
117 return true;
118 }
119 // EO cmpGroups
120
121 // ##########################################################################
122 // Helper function used by `weaveParents`
123 // ##########################################################################
124 template <class T>
125 bool checkForEmptyChild(const T& item) {
126 return item.empty();
127 }
128 // EO checkForEmptyChild
129
130 // ##########################################################################
131 // Helper function used by `weaveParents`
132 // ##########################################################################
133 bool cmpChunkForEmptySequence(
134 const sass::vector<sass::vector<SelectorComponentObj>>& seq,
135 const sass::vector<SelectorComponentObj>& group)
136 {
137 return seq.empty();
138 }
139 // EO cmpChunkForEmptySequence
140
141 // ##########################################################################
142 // Helper function used by `weaveParents`
143 // ##########################################################################
144 bool cmpChunkForParentSuperselector(
145 const sass::vector<sass::vector<SelectorComponentObj>>& seq,
146 const sass::vector<SelectorComponentObj>& group)
147 {
148 return seq.empty() || complexIsParentSuperselector(complex1: seq.front(), complex2: group);
149 }
150 // EO cmpChunkForParentSuperselector
151
152 // ##########################################################################
153 // Returns all orderings of initial subseqeuences of [queue1] and [queue2].
154 // The [done] callback is used to determine the extent of the initial
155 // subsequences. It's called with each queue until it returns `true`.
156 // Destructively removes the initial subsequences of [queue1] and [queue2].
157 // For example, given `(A B C | D E)` and `(1 2 | 3 4 5)` (with `|` denoting
158 // the boundary of the initial subsequence), this would return `[(A B C 1 2),
159 // (1 2 A B C)]`. The queues would then contain `(D E)` and `(3 4 5)`.
160 // ##########################################################################
161 template <class T>
162 sass::vector<sass::vector<T>> getChunks(
163 sass::vector<T>& queue1, sass::vector<T>& queue2,
164 const T& group, bool(*done)(const sass::vector<T>&, const T&)
165 ) {
166
167 sass::vector<T> chunk1;
168 while (!done(queue1, group)) {
169 chunk1.push_back(queue1.front());
170 queue1.erase(queue1.begin());
171 }
172
173 sass::vector<T> chunk2;
174 while (!done(queue2, group)) {
175 chunk2.push_back(queue2.front());
176 queue2.erase(queue2.begin());
177 }
178
179 if (chunk1.empty() && chunk2.empty()) return {};
180 else if (chunk1.empty()) return { chunk2 };
181 else if (chunk2.empty()) return { chunk1 };
182
183 sass::vector<T> choice1(chunk1), choice2(chunk2);
184 std::move(std::begin(chunk2), std::end(chunk2),
185 std::inserter(choice1, std::end(choice1)));
186 std::move(std::begin(chunk1), std::end(chunk1),
187 std::inserter(choice2, std::end(choice2)));
188 return { choice1, choice2 };
189 }
190 // EO getChunks
191
192 // ##########################################################################
193 // If the first element of [queue] has a `::root`
194 // selector, removes and returns that element.
195 // ##########################################################################
196 CompoundSelectorObj getFirstIfRoot(sass::vector<SelectorComponentObj>& queue) {
197 if (queue.empty()) return {};
198 SelectorComponent* first = queue.front();
199 if (CompoundSelector* sel = Cast<CompoundSelector>(ptr: first)) {
200 if (!hasRoot(compound: sel)) return {};
201 queue.erase(position: queue.begin());
202 return sel;
203 }
204 return {};
205 }
206 // EO getFirstIfRoot
207
208 // ##########################################################################
209 // Returns [complex], grouped into sub-lists such that no sub-list
210 // contains two adjacent [ComplexSelector]s. For example,
211 // `(A B > C D + E ~ > G)` is grouped into `[(A) (B > C) (D + E ~ > G)]`.
212 // ##########################################################################
213 sass::vector<sass::vector<SelectorComponentObj>> groupSelectors(
214 const sass::vector<SelectorComponentObj>& components)
215 {
216 bool lastWasCompound = false;
217 sass::vector<SelectorComponentObj> group;
218 sass::vector<sass::vector<SelectorComponentObj>> groups;
219 for (size_t i = 0; i < components.size(); i += 1) {
220 if (CompoundSelector* compound = components[i]->getCompound()) {
221 if (lastWasCompound) {
222 groups.push_back(x: group);
223 group.clear();
224 }
225 group.push_back(x: compound);
226 lastWasCompound = true;
227 }
228 else if (SelectorCombinator* combinator = components[i]->getCombinator()) {
229 group.push_back(x: combinator);
230 lastWasCompound = false;
231 }
232 }
233 if (!group.empty()) {
234 groups.push_back(x: group);
235 }
236 return groups;
237 }
238 // EO groupSelectors
239
240 // ##########################################################################
241 // Extracts leading [Combinator]s from [components1] and [components2]
242 // and merges them together into a single list of combinators.
243 // If there are no combinators to be merged, returns an empty list.
244 // If the combinators can't be merged, returns `null`.
245 // ##########################################################################
246 bool mergeInitialCombinators(
247 sass::vector<SelectorComponentObj>& components1,
248 sass::vector<SelectorComponentObj>& components2,
249 sass::vector<SelectorComponentObj>& result)
250 {
251
252 sass::vector<SelectorComponentObj> combinators1;
253 while (!components1.empty() && Cast<SelectorCombinator>(ptr: components1.front())) {
254 SelectorCombinatorObj front = Cast<SelectorCombinator>(ptr: components1.front());
255 components1.erase(position: components1.begin());
256 combinators1.push_back(x: front);
257 }
258
259 sass::vector<SelectorComponentObj> combinators2;
260 while (!components2.empty() && Cast<SelectorCombinator>(ptr: components2.front())) {
261 SelectorCombinatorObj front = Cast<SelectorCombinator>(ptr: components2.front());
262 components2.erase(position: components2.begin());
263 combinators2.push_back(x: front);
264 }
265
266 // If neither sequence of combinators is a subsequence
267 // of the other, they cannot be merged successfully.
268 sass::vector<SelectorComponentObj> LCS = lcs<SelectorComponentObj>(X: combinators1, Y: combinators2);
269
270 if (ListEquality(lhs: LCS, rhs: combinators1, cmp: PtrObjEqualityFn<SelectorComponent>)) {
271 result = combinators2;
272 return true;
273 }
274 if (ListEquality(lhs: LCS, rhs: combinators2, cmp: PtrObjEqualityFn<SelectorComponent>)) {
275 result = combinators1;
276 return true;
277 }
278
279 return false;
280
281 }
282 // EO mergeInitialCombinators
283
284 // ##########################################################################
285 // Extracts trailing [Combinator]s, and the selectors to which they apply,
286 // from [components1] and [components2] and merges them together into a
287 // single list. If there are no combinators to be merged, returns an
288 // empty list. If the sequences can't be merged, returns `null`.
289 // ##########################################################################
290 bool mergeFinalCombinators(
291 sass::vector<SelectorComponentObj>& components1,
292 sass::vector<SelectorComponentObj>& components2,
293 sass::vector<sass::vector<sass::vector<SelectorComponentObj>>>& result)
294 {
295
296 if (components1.empty() || !Cast<SelectorCombinator>(ptr: components1.back())) {
297 if (components2.empty() || !Cast<SelectorCombinator>(ptr: components2.back())) {
298 return true;
299 }
300 }
301
302 sass::vector<SelectorComponentObj> combinators1;
303 while (!components1.empty() && Cast<SelectorCombinator>(ptr: components1.back())) {
304 SelectorCombinatorObj back = Cast<SelectorCombinator>(ptr: components1.back());
305 components1.erase(position: components1.end() - 1);
306 combinators1.push_back(x: back);
307 }
308
309 sass::vector<SelectorComponentObj> combinators2;
310 while (!components2.empty() && Cast<SelectorCombinator>(ptr: components2.back())) {
311 SelectorCombinatorObj back = Cast<SelectorCombinator>(ptr: components2.back());
312 components2.erase(position: components2.end() - 1);
313 combinators2.push_back(x: back);
314 }
315
316 // reverse now as we used push_back (faster than new alloc)
317 std::reverse(first: combinators1.begin(), last: combinators1.end());
318 std::reverse(first: combinators2.begin(), last: combinators2.end());
319
320 if (combinators1.size() > 1 || combinators2.size() > 1) {
321 // If there are multiple combinators, something hacky's going on. If one
322 // is a supersequence of the other, use that, otherwise give up.
323 auto LCS = lcs<SelectorComponentObj>(X: combinators1, Y: combinators2);
324 if (ListEquality(lhs: LCS, rhs: combinators1, cmp: PtrObjEqualityFn<SelectorComponent>)) {
325 result.push_back(x: { combinators2 });
326 }
327 else if (ListEquality(lhs: LCS, rhs: combinators2, cmp: PtrObjEqualityFn<SelectorComponent>)) {
328 result.push_back(x: { combinators1 });
329 }
330 else {
331 return false;
332 }
333 return true;
334 }
335
336 // This code looks complicated, but it's actually just a bunch of special
337 // cases for interactions between different combinators.
338 SelectorCombinatorObj combinator1, combinator2;
339 if (!combinators1.empty()) combinator1 = combinators1.back();
340 if (!combinators2.empty()) combinator2 = combinators2.back();
341
342 if (!combinator1.isNull() && !combinator2.isNull()) {
343
344 CompoundSelector* compound1 = Cast<CompoundSelector>(ptr: components1.back());
345 CompoundSelector* compound2 = Cast<CompoundSelector>(ptr: components2.back());
346
347 components1.pop_back();
348 components2.pop_back();
349
350 if (combinator1->isGeneralCombinator() && combinator2->isGeneralCombinator()) {
351
352 if (compound1->isSuperselectorOf(sub: compound2)) {
353 result.push_back(x: { { compound2, combinator2 } });
354 }
355 else if (compound2->isSuperselectorOf(sub: compound1)) {
356 result.push_back(x: { { compound1, combinator1 } });
357 }
358 else {
359 sass::vector<sass::vector<SelectorComponentObj>> choices;
360 choices.push_back(x: { compound1, combinator1, compound2, combinator2 });
361 choices.push_back(x: { compound2, combinator2, compound1, combinator1 });
362 if (CompoundSelector* unified = compound1->unifyWith(rhs: compound2)) {
363 choices.push_back(x: { unified, combinator1 });
364 }
365 result.push_back(x: choices);
366 }
367 }
368 else if ((combinator1->isGeneralCombinator() && combinator2->isAdjacentCombinator()) ||
369 (combinator1->isAdjacentCombinator() && combinator2->isGeneralCombinator())) {
370
371 CompoundSelector* followingSiblingSelector = combinator1->isGeneralCombinator() ? compound1 : compound2;
372 CompoundSelector* nextSiblingSelector = combinator1->isGeneralCombinator() ? compound2 : compound1;
373 SelectorCombinator* followingSiblingCombinator = combinator1->isGeneralCombinator() ? combinator1 : combinator2;
374 SelectorCombinator* nextSiblingCombinator = combinator1->isGeneralCombinator() ? combinator2 : combinator1;
375
376 if (followingSiblingSelector->isSuperselectorOf(sub: nextSiblingSelector)) {
377 result.push_back(x: { { nextSiblingSelector, nextSiblingCombinator } });
378 }
379 else {
380 CompoundSelectorObj unified = compound1->unifyWith(rhs: compound2);
381 sass::vector<sass::vector<SelectorComponentObj>> items;
382
383 if (!unified.isNull()) {
384 items.push_back(x: {
385 unified, nextSiblingCombinator
386 });
387 }
388
389 items.insert(position: items.begin(), x: {
390 followingSiblingSelector,
391 followingSiblingCombinator,
392 nextSiblingSelector,
393 nextSiblingCombinator,
394 });
395
396 result.push_back(x: items);
397 }
398
399 }
400 else if (combinator1->isChildCombinator() && (combinator2->isAdjacentCombinator() || combinator2->isGeneralCombinator())) {
401 result.push_back(x: { { compound2, combinator2 } });
402 components1.push_back(x: compound1);
403 components1.push_back(x: combinator1);
404 }
405 else if (combinator2->isChildCombinator() && (combinator1->isAdjacentCombinator() || combinator1->isGeneralCombinator())) {
406 result.push_back(x: { { compound1, combinator1 } });
407 components2.push_back(x: compound2);
408 components2.push_back(x: combinator2);
409 }
410 else if (*combinator1 == *combinator2) {
411 CompoundSelectorObj unified = compound1->unifyWith(rhs: compound2);
412 if (unified.isNull()) return false;
413 result.push_back(x: { { unified, combinator1 } });
414 }
415 else {
416 return false;
417 }
418
419 return mergeFinalCombinators(components1, components2, result);
420
421 }
422 else if (!combinator1.isNull()) {
423
424 if (combinator1->isChildCombinator() && !components2.empty()) {
425 const CompoundSelector* back1 = Cast<CompoundSelector>(ptr: components1.back());
426 const CompoundSelector* back2 = Cast<CompoundSelector>(ptr: components2.back());
427 if (back1 && back2 && back2->isSuperselectorOf(sub: back1)) {
428 components2.pop_back();
429 }
430 }
431
432 result.push_back(x: { { components1.back(), combinator1 } });
433
434 components1.pop_back();
435
436 return mergeFinalCombinators(components1, components2, result);
437
438 }
439
440 if (combinator2->isChildCombinator() && !components1.empty()) {
441 const CompoundSelector* back1 = Cast<CompoundSelector>(ptr: components1.back());
442 const CompoundSelector* back2 = Cast<CompoundSelector>(ptr: components2.back());
443 if (back1 && back2 && back1->isSuperselectorOf(sub: back2)) {
444 components1.pop_back();
445 }
446 }
447
448 result.push_back(x: { { components2.back(), combinator2 } });
449
450 components2.pop_back();
451
452 return mergeFinalCombinators(components1, components2, result);
453
454 }
455 // EO mergeFinalCombinators
456
457 // ##########################################################################
458 // Expands "parenthesized selectors" in [complexes]. That is, if
459 // we have `.A .B {@extend .C}` and `.D .C {...}`, this conceptually
460 // expands into `.D .C, .D (.A .B)`, and this function translates
461 // `.D (.A .B)` into `.D .A .B, .A .D .B`. For thoroughness, `.A.D .B`
462 // would also be required, but including merged selectors results in
463 // exponential output for very little gain. The selector `.D (.A .B)`
464 // is represented as the list `[[.D], [.A, .B]]`.
465 // ##########################################################################
466 sass::vector<sass::vector<SelectorComponentObj>> weave(
467 const sass::vector<sass::vector<SelectorComponentObj>>& complexes) {
468
469 sass::vector<sass::vector<SelectorComponentObj>> prefixes;
470
471 prefixes.push_back(x: complexes.at(n: 0));
472
473 for (size_t i = 1; i < complexes.size(); i += 1) {
474
475 if (complexes[i].empty()) {
476 continue;
477 }
478 const sass::vector<SelectorComponentObj>& complex = complexes[i];
479 SelectorComponent* target = complex.back();
480 if (complex.size() == 1) {
481 for (auto& prefix : prefixes) {
482 prefix.push_back(x: target);
483 }
484 continue;
485 }
486
487 sass::vector<SelectorComponentObj> parents(complex);
488
489 parents.pop_back();
490
491 sass::vector<sass::vector<SelectorComponentObj>> newPrefixes;
492 for (sass::vector<SelectorComponentObj> prefix : prefixes) {
493 sass::vector<sass::vector<SelectorComponentObj>>
494 parentPrefixes = weaveParents(parents1: prefix, parents2: parents);
495 if (parentPrefixes.empty()) continue;
496 for (auto& parentPrefix : parentPrefixes) {
497 parentPrefix.push_back(x: target);
498 newPrefixes.push_back(x: parentPrefix);
499 }
500 }
501 prefixes = newPrefixes;
502
503 }
504 return prefixes;
505
506 }
507 // EO weave
508
509 // ##########################################################################
510 // Interweaves [parents1] and [parents2] as parents of the same target
511 // selector. Returns all possible orderings of the selectors in the
512 // inputs (including using unification) that maintain the relative
513 // ordering of the input. For example, given `.foo .bar` and `.baz .bang`,
514 // this would return `.foo .bar .baz .bang`, `.foo .bar.baz .bang`,
515 // `.foo .baz .bar .bang`, `.foo .baz .bar.bang`, `.foo .baz .bang .bar`,
516 // and so on until `.baz .bang .foo .bar`. Semantically, for selectors A
517 // and B, this returns all selectors `AB_i` such that the union over all i
518 // of elements matched by `AB_i X` is identical to the intersection of all
519 // elements matched by `A X` and all elements matched by `B X`. Some `AB_i`
520 // are elided to reduce the size of the output.
521 // ##########################################################################
522 sass::vector<sass::vector<SelectorComponentObj>> weaveParents(
523 sass::vector<SelectorComponentObj> queue1,
524 sass::vector<SelectorComponentObj> queue2)
525 {
526
527 sass::vector<SelectorComponentObj> leads;
528 sass::vector<sass::vector<sass::vector<SelectorComponentObj>>> trails;
529 if (!mergeInitialCombinators(components1&: queue1, components2&: queue2, result&: leads)) return {};
530 if (!mergeFinalCombinators(components1&: queue1, components2&: queue2, result&: trails)) return {};
531 // list comes out in reverse order for performance
532 std::reverse(first: trails.begin(), last: trails.end());
533
534 // Make sure there's at most one `:root` in the output.
535 // Note: does not yet do anything in libsass (no root selector)
536 CompoundSelectorObj root1 = getFirstIfRoot(queue&: queue1);
537 CompoundSelectorObj root2 = getFirstIfRoot(queue&: queue2);
538
539 if (!root1.isNull() && !root2.isNull()) {
540 CompoundSelectorObj root = root1->unifyWith(rhs: root2);
541 if (root.isNull()) return {}; // null
542 queue1.insert(position: queue1.begin(), x: root);
543 queue2.insert(position: queue2.begin(), x: root);
544 }
545 else if (!root1.isNull()) {
546 queue2.insert(position: queue2.begin(), x: root1);
547 }
548 else if (!root2.isNull()) {
549 queue1.insert(position: queue1.begin(), x: root2);
550 }
551
552 // group into sub-lists so no sub-list contains two adjacent ComplexSelectors.
553 sass::vector<sass::vector<SelectorComponentObj>> groups1 = groupSelectors(components: queue1);
554 sass::vector<sass::vector<SelectorComponentObj>> groups2 = groupSelectors(components: queue2);
555
556 // The main array to store our choices that will be permutated
557 sass::vector<sass::vector<sass::vector<SelectorComponentObj>>> choices;
558
559 // append initial combinators
560 choices.push_back(x: { leads });
561
562 sass::vector<sass::vector<SelectorComponentObj>> LCS =
563 lcs<sass::vector<SelectorComponentObj>>(X: groups1, Y: groups2, select: cmpGroups);
564
565 for (auto group : LCS) {
566
567 // Create junks from groups1 and groups2
568 sass::vector<sass::vector<sass::vector<SelectorComponentObj>>>
569 chunks = getChunks<sass::vector<SelectorComponentObj>>(
570 queue1&: groups1, queue2&: groups2, group, done: cmpChunkForParentSuperselector);
571
572 // Create expanded array by flattening chunks2 inner
573 sass::vector<sass::vector<SelectorComponentObj>>
574 expanded = flattenInner(vec: chunks);
575
576 // Prepare data structures
577 choices.push_back(x: expanded);
578 choices.push_back(x: { group });
579 if (!groups1.empty()) {
580 groups1.erase(position: groups1.begin());
581 }
582 if (!groups2.empty()) {
583 groups2.erase(position: groups2.begin());
584 }
585
586 }
587
588 // Create junks from groups1 and groups2
589 sass::vector<sass::vector<sass::vector<SelectorComponentObj>>>
590 chunks = getChunks<sass::vector<SelectorComponentObj>>(
591 queue1&: groups1, queue2&: groups2, group: {}, done: cmpChunkForEmptySequence);
592
593 // Append chunks with inner arrays flattened
594 choices.emplace_back(args: flattenInner(vec: chunks));
595
596 // append all trailing selectors to choices
597 std::move(first: std::begin(cont&: trails), last: std::end(cont&: trails),
598 result: std::inserter(x&: choices, i: std::end(cont&: choices)));
599
600 // move all non empty items to the front, then erase the trailing ones
601 choices.erase(first: std::remove_if(first: choices.begin(), last: choices.end(), pred: checkForEmptyChild
602 <sass::vector<sass::vector<SelectorComponentObj>>>), last: choices.end());
603
604 // permutate all possible paths through selectors
605 sass::vector<sass::vector<SelectorComponentObj>>
606 results = flattenInner(vec: permutate(in: choices));
607
608 return results;
609
610 }
611 // EO weaveParents
612
613 // ##########################################################################
614 // ##########################################################################
615
616}
617

source code of gtk/subprojects/libsass/src/ast_sel_weave.cpp