Rewrite @extend logic. Add a Selector class.

This passes all the tests, but could use some considerable cleaning up,
documenting, testing/handling of edge cases, etc.

7 files changed, 280 insertions, 7 deletions

diff --git a/scss/__init__.py b/scss/__init__.py
index 685057f..56bd6f4 100644
--- a/scss/__init__.py
+++ b/scss/__init__.py
@@ -1379,6 +1379,82 @@ class Scss(object):
         """
         For each part, create the inheritance parts from the @extends
         """
+        # Boy I wish I hadn't lost whatever work I'd done on this so far.
+        # TODO: clean up variable names, method names (cross product?!), etc.
+        # TODO: make Rules always contain Selectors, not strings.
+        # TODO: fix the Selector rendering to put the right amount of space in
+        # the right places
+        # TODO: child/sibling/etc selectors aren't handled correctly
+        # TODO: %foo may not be handled correctly
+        # TODO: a whole bunch of unit tests for Selector parsing
+        # TODO: make sure this all works for kronuz
+        # TODO: steal a TONNNNNN of tests from ruby and sassc for this
+
+
+
+        # Game plan: for each rule that has an @extend, add its selectors to
+        # every rule that matches that @extend.
+        # First, rig a way to find arbitrary selectors quickly.  Most selectors
+        # revolve around elements, classes, and IDs, so parse those out and use
+        # them as a rough key.  Ignore order and duplication for now.
+        from scss.rule import Selector
+        key_to_selectors = defaultdict(set)
+        selector_to_rules = defaultdict(list)
+        pos = 0
+        for rule in self.rules:
+            rule.position = pos
+            pos += 1
+
+            for selector in rule.selectors:
+                selobj, = Selector.parse(selector)
+                for key in selobj.lookup_key():
+                    key_to_selectors[key].add(selector)
+                selector_to_rules[selector].append(rule)
+
+        # Now go through all the rules with an @extends and find their parent
+        # rules.
+        for rule in self.rules:
+            for selector in rule.extends_selectors:
+                extends_selectors = []
+
+                selobj, = Selector.parse(selector)
+                import operator
+                candidates = reduce(operator.and_, (key_to_selectors[key] for key in selobj.lookup_key()))
+                for cand in candidates:
+                    extend_selector_obj, = Selector.parse(cand)
+                    if extend_selector_obj.is_superset_of(selobj):
+                        print("looks like a match to me", selector, cand)
+                        extends_selectors.append(extend_selector_obj)
+
+                if not extends_selectors:
+                    log.warn("no match found")
+                    continue
+
+                # do magic here
+                for extend_selector_obj in extends_selectors:
+                    for parent_rule in selector_to_rules[extend_selector_obj.original_selector]:
+                        rule_selector, = rule.selectors  # TODO
+                        new_parents = extend_selector_obj.substitute(
+                            Selector.parse(selector)[0],
+                            Selector.parse(rule_selector)[0],
+                        )
+
+                        existing_parent_selectors = list(parent_rule.selectors)
+                        for parent in new_parents:
+                            existing_parent_selectors.append(parent.render())
+                        parent_rule.selectors = frozenset(existing_parent_selectors)
+                        parent_rule.dependent_rules.add(rule.position)
+
+                        # Update indices, in case any later rules try to extend
+                        # this one
+                        for parent in new_parents:
+                            key_to_selectors[parent.lookup_key()].add(parent.render())
+                            # TODO this could lead to duplicates?  maybe should
+                            # be a set too
+                            selector_to_rules[parent.render()].append(parent_rule)
+
+        return
+
         # First group rules by a tuple of (selectors, @extends)
         pos = 0
         grouped_rules = defaultdict(list)
@@ -1423,7 +1499,14 @@ class Scss(object):
                 new_key = selectors, frozenset()
                 grouped_rules[new_key].extend(rules)
 
+                print()
+                print("calling link_with_parents.")
+                print(grouped_rules)
+                print(parent)
+                print(selectors)
+                print(rules)
                 parents = self.link_with_parents(grouped_rules, parent, selectors, rules)
+                print("got back:", parents)
 
                 if parents is None:
                     log.warn("Parent rule not found: %s", parent)
diff --git a/scss/rule.py b/scss/rule.py
index a2694a8..99a8c4f 100644
--- a/scss/rule.py
+++ b/scss/rule.py
@@ -247,6 +247,197 @@ class SassRule(object):
         )
 
 
+class Selector(object):
+    """A single CSS selector."""
+
+    def __init__(self, selector, tree):
+        """Private; please use parse()."""
+        self.original_selector = selector
+        self._tree = tree
+
+    @classmethod
+    def parse(cls, selector):
+        # Super dumb little selector parser
+
+        # Yes, yes, this is a regex tokenizer.  The actual meaning of the
+        # selector doesn't matter; the parts are just important for matching up
+        # during @extend.
+        import re
+        tokenizer = re.compile(
+        r'''
+            # Colons introduce pseudo-selectors, sometimes with parens
+            # TODO doesn't handle quoted )
+            [:]+ [-\w]+ (?: [(] .+? [)] )?
+
+            # Square brackets are attribute tests
+            # TODO: this doesn't handle ] within a string
+            | [[] .+? []]
+
+            # Dot and pound start class/id selectors.  Percent starts a Sass
+            # extend-target faux selector.
+            | [.#%] [-\w]+
+
+            # Plain identifiers, or single asterisks, are element names
+            | [-\w]+
+            | [*]
+
+            # These guys are combinators -- note that a single space counts too
+            | \s* [ +>~] \s*
+
+            # And as a last-ditch effort for something really outlandish (e.g.
+            # percentages as faux-selectors in @keyframes), just eat up to the
+            # next whitespace
+            | (\S+)
+        ''', re.VERBOSE | re.MULTILINE)
+
+        # Selectors have three levels: simple, combinator, comma-delimited.
+        # Each combinator can only appear once as a delimiter between simple
+        # selectors, so it can be thought of as a prefix.
+        # So this:
+        #     a.b + c, d#e
+        # parses into two Selectors with these structures:
+        #     [[' ', 'a', '.b'], ['+', 'c']]
+        #     [[' ', 'd', '#e']]
+        # Note that the first simple selector has an implied descendant
+        # combinator -- i.e., it is a descendant of the root element.
+        trees = [[[' ']]]
+        pos = 0
+        while pos < len(selector):
+            # TODO i don't think this deals with " + " correctly.  anywhere.
+            m = tokenizer.match(selector, pos)
+            if not m:
+                # TODO prettify me
+                raise SyntaxError("Couldn't parse selector: %r" % (selector,))
+
+            token = m.group(0)
+            if token == ',':
+                trees.append([[' ']])
+            elif token in ' +>~':
+                trees[-1].append([token])
+            else:
+                trees[-1][-1].append(token)
+
+            pos += len(token)
+
+        # TODO this passes the whole selector, not just the part
+        return [cls(selector, tree) for tree in trees]
+
+    def __repr__(self):
+        return "<%s: %r>" % (type(self).__name__, self._tree)
+
+    def lookup_key(self):
+        """Build a key from the "important" parts of a selector: elements,
+        classes, ids.
+        """
+        # TODO how does this work with multiple selectors
+        parts = set()
+        for node in self._tree:
+            for token in node[1:]:
+                if token[0] not in ':[':
+                    parts.add(token)
+
+        if not parts:
+            # Should always have at least ONE key; selectors with no elements,
+            # no classes, and no ids can be indexed as None to avoid a scan of
+            # every selector in the entire document
+            parts.add(None)
+
+        return frozenset(parts)
+
+    def is_superset_of(self, other):
+        assert isinstance(other, Selector)
+
+        idx = 0
+        for other_node in other._tree:
+            if idx >= len(self._tree):
+                return False
+
+            while idx < len(self._tree):
+                node = self._tree[idx]
+                idx += 1
+
+                if node[0] == other_node[0] and set(node[1:]) <= set(other_node[1:]):
+                    break
+
+        return True
+
+    def substitute(self, target, replacement):
+        """Return a list of selectors obtained by replacing the `target`
+        selector with `replacement`.
+
+        Herein lie the guts of the Sass @extend directive.
+
+        In general, for a selector ``a X b Y c``, a target ``X Y``, and a
+        replacement ``q Z``, return the selectors ``a q X b Z c`` and ``q a X b
+        Z c``.  Note in particular that no more than two selectors will be
+        returned, and the permutation of ancestors will never insert new simple
+        selectors "inside" the target selector.
+        """
+
+        # Find the hinge in the parent selector, and split it into before/after
+        p_before, p_extras, p_after = self.break_around(target._tree)
+
+        # The replacement has no hinge; it only has the most specific simple
+        # selector (which is the part that replaces "self" in the parent) and
+        # whatever preceding simple selectors there may be
+        r_trail = replacement._tree[:-1]
+        r_extras = replacement._tree[-1]
+
+        # TODO is this the right order?
+        # TODO what if the prefix doesn't match?  who wins?  should we even get
+        # this far?
+        focal_node = [p_extras[0]]
+        focal_node.extend(sorted(
+            p_extras[1:] + r_extras[1:],
+            key=lambda token: {'#':1,'.':2,':':3}.get(token[0], 0)))
+
+        if p_before and r_trail:
+            # Two conflicting "preceding" parts.  Rather than try to cross-join
+            # them, just generate two possibilities: P R and R P.
+            befores = [p_before + r_trail, r_trail + p_before]
+        else:
+            # At least one of them is empty, so just concatenate
+            befores = [p_before + r_trail]
+
+        ret = [before + focal_node for before in befores]
+
+        return [Selector(None, before + focal_node + p_after) for before in befores]
+
+    def break_around(self, hinge):
+        """Given a simple selector node contained within this one (a "hinge"),
+        break it in half and return a parent selector, extra specifiers for the
+        hinge, and a child selector.
+
+        That is, given a hinge X, break the selector A + X.y B into A, + .y,
+        and B.
+        """
+        hinge_start = hinge[0]
+        for i, node in enumerate(self._tree):
+            # TODO does first combinator have to match?  maybe only if the
+            # hinge has a non-descendant combinator?
+            if set(hinge_start[1:]) <= set(node[1:]):
+                start_idx = i
+                break
+        else:
+            raise ValueError("Couldn't find hinge %r in compound selector %r", (hinge_start, self._tree))
+
+        for i, hinge_node in enumerate(hinge):
+            self_node = self._tree[start_idx + i]
+            if hinge_node[0] == self_node[0] and set(hinge_node[1:]) <= set(self_node[1:]):
+                continue
+
+            # TODO this isn't true; consider finding `a b` in `a c a b`
+            raise TypeError("no match")
+
+        end_idx = start_idx + len(hinge) - 1
+        focal_node = self._tree[end_idx]
+        extras = [focal_node[0]] + [token for token in focal_node[1:] if token not in hinge[-1]]
+        return self._tree[:start_idx], extras, self._tree[end_idx + 1:]
+
+    def render(self):
+        return ''.join(''.join(node) for node in self._tree).lstrip()
+
+
 class BlockHeader(object):
     """..."""
     # TODO doc me depending on how UnparsedBlock is handled...
diff --git a/scss/tests/files/original-doctests/007-extends-3.scss b/scss/tests/files/original-doctests/007-extends-3.scss
index f5d1890..a9b1d5c 100644
--- a/scss/tests/files/original-doctests/007-extends-3.scss
+++ b/scss/tests/files/original-doctests/007-extends-3.scss
@@ -12,4 +12,4 @@
     a {
         text-decoration: none;
     }
-}
\ No newline at end of file
+}
diff --git a/scss/tests/files/original-doctests/021-extend.css b/scss/tests/files/original-doctests/021-extend.css
index 86beaaa..2fd31be 100644
--- a/scss/tests/files/original-doctests/021-extend.css
+++ b/scss/tests/files/original-doctests/021-extend.css
@@ -2,7 +2,7 @@
   border: 1px #f00;
   background-color: #fdd;
 }
-.error.intrusion, .seriousError.intrusion {
+.error.intrusion, .intrusion.seriousError {
   background-image: url("/image/hacked.png");
 }
 .seriousError {
diff --git a/scss/tests/files/original-doctests/037-test-7.scss b/scss/tests/files/original-doctests/037-test-7.scss
index 73b614a..3c5c81c 100644
--- a/scss/tests/files/original-doctests/037-test-7.scss
+++ b/scss/tests/files/original-doctests/037-test-7.scss
@@ -4,4 +4,4 @@
 a {
   color: blue;
   &:hover {text-decoration: underline}
-}
\ No newline at end of file
+}
diff --git a/scss/tests/files/original-doctests/039-hover-extend.css b/scss/tests/files/original-doctests/039-hover-extend.css
index 56cab86..2a83480 100644
--- a/scss/tests/files/original-doctests/039-hover-extend.css
+++ b/scss/tests/files/original-doctests/039-hover-extend.css
@@ -1,4 +1,3 @@
-.comment a.user:hover,
-.comment .hoverlink.user {
+.comment .user.hoverlink, .comment a.user:hover {
   font-weight: bold;
 }
diff --git a/scss/tests/files/original-doctests/040-complex-sequence-extend.css b/scss/tests/files/original-doctests/040-complex-sequence-extend.css
index 8277881..4317ca7 100644
--- a/scss/tests/files/original-doctests/040-complex-sequence-extend.css
+++ b/scss/tests/files/original-doctests/040-complex-sequence-extend.css
@@ -1,4 +1,4 @@
-#admin .tabbar #demo .overview .fakelink, #admin .tabbar a,
-#demo .overview #admin .tabbar .fakelink {
+#admin .tabbar #demo .overview .fakelink, #admin .tabbar a, #demo
+.overview #admin .tabbar .fakelink {
   font-weight: bold;
 }