Add LCS algorithm to @extend, and a big ol test file.

4 files changed, 268 insertions, 152 deletions

diff --git a/scss/__init__.py b/scss/__init__.py
index 56bd6f4..8202d74 100644
--- a/scss/__init__.py
+++ b/scss/__init__.py
@@ -1304,76 +1304,6 @@ class Scss(object):
 
         p_children.appendleft(_rule)
 
-    @print_timing(4)
-    def link_with_parents(self, grouped_rules, parent, c_selectors, c_rules):
-        """
-        Link with a parent for the current child rule.
-        If parents found, returns a list of parent rules to the child
-        """
-        parent_found = None
-        for (p_selectors, p_extends), p_rules in grouped_rules.items():
-            new_selectors = set()
-            found = False
-
-            # Finds all the parent selectors and parent selectors with another
-            # bind selectors behind. For example, if `.specialClass` extends `.baseClass`,
-            # and there is a `.baseClass` selector, the extension should create
-            # `.specialClass` for that rule, but if there's also a `.baseClass a`
-            # it also should create `.specialClass a`
-            for p_selector in p_selectors:
-                if parent not in p_selector:
-                    continue
-
-                # get the new child selector to add (same as the parent selector but with the child name)
-                # since selectors can be together, separated with # or . (i.e. something.parent) check that too:
-                for c_selector in c_selectors:
-                    # Get whatever is different between the two selectors:
-                    _c_selector, _parent = c_selector, parent
-                    lcp = self.longest_common_prefix(_c_selector, _parent)
-                    if lcp:
-                        _c_selector = _c_selector[lcp:]
-                        _parent = _parent[lcp:]
-                    lcs = self.longest_common_suffix(_c_selector, _parent)
-                    if lcs:
-                        _c_selector = _c_selector[:-lcs]
-                        _parent = _parent[:-lcs]
-                    if _c_selector and _parent:
-                        # Get the new selectors:
-                        prev_symbol = '(?<![%#.:])' if _parent[0] in ('%', '#', '.', ':') else r'(?<![-\w%#.:])'
-                        post_symbol = r'(?![-\w])'
-                        new_parent = re.sub(prev_symbol + _parent + post_symbol, _c_selector, p_selector)
-                        if p_selector != new_parent:
-                            new_selectors.add(new_parent)
-                            found = True
-
-            if found:
-                # add parent:
-                parent_found = parent_found or []
-                parent_found.extend(p_rules)
-
-            new_selectors = frozenset(new_selectors)
-            if new_selectors:
-                # Re-include parents
-                new_selectors |= p_selectors
-
-                # rename node:
-                if new_selectors != p_selectors:
-                    del grouped_rules[p_selectors, p_extends]
-                    new_key = new_selectors, p_extends
-                    grouped_rules[new_key].extend(p_rules)
-
-                deps = set()
-                # save child dependencies:
-                for c_rule in c_rules or []:
-                    assert c_rule.selectors == c_selectors
-                    deps.add(c_rule.position)
-
-                for p_rule in p_rules:
-                    p_rule.selectors = new_selectors  # re-set the SELECTORS for the rules
-                    p_rule.dependent_rules.update(deps)  # position is the "index" of the object
-
-        return parent_found
-
     @print_timing(3)
     def parse_extends(self):
         """
@@ -1423,7 +1353,6 @@ class Scss(object):
                 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:
@@ -1453,78 +1382,6 @@ class Scss(object):
                             # 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)
-        for rule in self.rules:
-            pos += 1
-            rule.position = pos
-
-            key = rule.selectors, frozenset(rule.extends_selectors)
-            grouped_rules[key].append(rule)
-
-        # To be able to manage multiple extends, you need to
-        # destroy the actual node and create many nodes that have
-        # mono extend. The first one gets all the css rules
-        for (selectors, parents), rules in list(grouped_rules.items()):
-            if len(parents) <= 1:
-                continue
-
-            del grouped_rules[selectors, parents]
-            for parent in parents:
-                new_key = selectors, frozenset((parent,))
-                grouped_rules[new_key].extend(rules)
-                rules = []  # further rules extending other parents will be empty
-
-        cnt = 0
-        parents_left = True
-        while parents_left and cnt < 10:
-            cnt += 1
-            parents_left = False
-            for key in list(grouped_rules.keys()):
-                if key not in grouped_rules:
-                    # Nodes might have been renamed while linking parents...
-                    continue
-
-                selectors, orig_parents = key
-                if not orig_parents:
-                    continue
-
-                parent, = orig_parents
-                parents_left = True
-
-                rules = grouped_rules.pop(key)
-                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)
-                    continue
-
-                # from the parent, inherit the context and the options:
-                from scss.rule import Namespace
-                parent_namespaces = [parent.namespace for parent in parents]
-                new_options = {}
-                for parent in parents:
-                    new_options.update(parent.options)
-                for rule in rules:
-                    rule.namespace = Namespace.derive_from(
-                        rule.namespace, *parent_namespaces)
-                    _new_options = new_options.copy()
-                    _new_options.update(rule.options)
-                    rule.options = _new_options
-
     @print_timing(3)
     def manage_order(self):
         # order rules according with their dependencies
diff --git a/scss/rule.py b/scss/rule.py
index 99a8c4f..1c669b2 100644
--- a/scss/rule.py
+++ b/scss/rule.py
@@ -391,15 +391,7 @@ class Selector(object):
             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]
+        befores = self._merge_trails(p_before, r_trail)
 
         return [Selector(None, before + focal_node + p_after) for before in befores]
 
@@ -434,10 +426,117 @@ class Selector(object):
         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:]
 
+    @staticmethod
+    def _merge_trails(left, right):
+        # XXX docs docs docs
+
+        if not left or not right:
+            # At least one is empty, so there are no conflicts; just
+            # return whichever isn't empty
+            return [left or right]
+
+        sequencer = LeastCommonSubsequencer(left, right, eq=_merge_selector_nodes)
+        lcs = sequencer.find()
+
+        ret = [[]]
+        left_last = 0
+        right_last = 0
+        for left_next, right_next, merged in lcs:
+            left_prefix = left[left_last:left_next]
+            right_prefix = right[right_last:right_next]
+
+            new_ret = [
+                node + left_prefix + right_prefix + [merged]
+                for node in ret]
+            if left_prefix and right_prefix:
+                new_ret.extend(
+                    node + right_prefix + left_prefix + [merged]
+                    for node in ret)
+            ret = new_ret
+
+            left_last = left_next + 1
+            right_last = right_next + 1
+
+        left_prefix = left[left_last:]
+        right_prefix = right[right_last:]
+        # TODO factor this out
+        new_ret = [
+            node + left_prefix + right_prefix
+            for node in ret]
+        if left_prefix and right_prefix:
+            new_ret.extend(
+                node + right_prefix + left_prefix
+                for node in ret)
+        ret = new_ret
+
+        return ret
+
     def render(self):
         return ''.join(''.join(node) for node in self._tree).lstrip()
 
 
+def _merge_selector_nodes(a, b):
+    # TODO document, turn me into a method on something
+    # TODO what about combinators
+    aset = frozenset(a[1:])
+    bset = frozenset(b[1:])
+    if aset <= bset:
+        return a + [token for token in b[1:] if token not in aset]
+    elif bset <= aset:
+        return b + [token for token in a[1:] if token not in bset]
+    else:
+        return None
+
+
+
+class LeastCommonSubsequencer(object):
+    # http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution
+    def __init__(self, a, b, eq=lambda a, b: a if a == b else None):
+        self.a = a
+        self.b = b
+        self.eq_matrix = dict()
+        self.length_matrix = dict()
+
+        self.init_eq_matrix(eq)
+        self.init_length_matrix()
+
+    def init_eq_matrix(self, eq):
+        for ai, aval in enumerate(self.a):
+            for bi, bval in enumerate(self.b):
+                self.eq_matrix[ai, bi] = eq(aval, bval)
+
+    def init_length_matrix(self):
+        for ai in range(-1, len(self.a)):
+            for bi in range(-1, len(self.b)):
+                if ai == -1 or bi == -1:
+                    l = 0
+                elif self.eq_matrix[ai, bi]:
+                    l = self.length_matrix[ai - 1, bi - 1] + 1
+                else:
+                    l = max(
+                        self.length_matrix[ai, bi - 1],
+                        self.length_matrix[ai - 1, bi])
+
+                self.length_matrix[ai, bi] = l
+
+    def backtrack(self, ai, bi):
+        if ai < 0 or bi < 0:
+            # Base case: backtracked beyond the beginning with no match
+            return []
+
+        merged = self.eq_matrix[ai, bi]
+        if merged is not None:
+            return self.backtrack(ai - 1, bi - 1) + [(ai, bi, merged)]
+
+        if self.length_matrix[ai, bi - 1] > self.length_matrix[ai - 1, bi]:
+            return self.backtrack(ai, bi - 1)
+        else:
+            return self.backtrack(ai - 1, bi)
+
+    def find(self):
+        return self.backtrack(len(self.a) - 1, len(self.b) - 1)
+
+
 class BlockHeader(object):
     """..."""
     # TODO doc me depending on how UnparsedBlock is handled...
diff --git a/scss/tests/files/bugs/extend-common-prefix-complex.css b/scss/tests/files/bugs/extend-common-prefix-complex.css
new file mode 100644
index 0000000..fdbfd9d
--- /dev/null
+++ b/scss/tests/files/bugs/extend-common-prefix-complex.css
@@ -0,0 +1,48 @@
+#one #two #three a, #one #two #three b {
+  key: value;
+}
+#one #three c, #one #two #three d {
+  key: value;
+}
+#one #two #three e, #one #two #three f {
+  key: value;
+}
+#one.x #two.y #three.z g, #one.x #two.y #three.z h {
+  key: value;
+}
+#one #two #three i, #one.x #two.y #three.z j {
+  key: value;
+}
+#one #two #three l, #one #two k {
+  key: value;
+}
+#one #two #three n, #two #three m {
+  key: value;
+}
+#one #two #three #four p, #one #two #three o {
+  key: value;
+}
+#one #two #three #four q, #one #two #three #four r {
+  key: value;
+}
+#one #three #two #four t, #one #two #four s, #one #two #three #four t {
+  key: value;
+}
+#one #three #five u, #one #two #three #five #four v, #one #two #three
+#four #five v, #two #one #three #five #four v, #two #one #three #four
+#five v {
+  key: value;
+}
+#one #three #two #four #five x, #one #two #four #five w, #one #two
+#three #four #five x {
+  key: value;
+}
+five one two one three one four one six z, five one two one three one
+six four one z, one two five one three one four one six z, one two
+five one three one six four one z, one two one three one four one y {
+  key: value;
+}
+five one three one six aa, five one two one three one four one six bb,
+one two five one three one four one six bb {
+  key: value;
+}
diff --git a/scss/tests/files/bugs/extend-common-prefix-complex.scss b/scss/tests/files/bugs/extend-common-prefix-complex.scss
new file mode 100644
index 0000000..aa2d94b
--- /dev/null
+++ b/scss/tests/files/bugs/extend-common-prefix-complex.scss
@@ -0,0 +1,112 @@
+#one #two #three a {
+    key: value;
+}
+#one #two #three b {
+    @extend a;
+}
+
+
+#one #three c {
+    key: value;
+}
+#one #two #three d {
+    @extend c;
+}
+
+
+#one #two #three e {
+    key: value;
+}
+#one #three f {
+    @extend e;
+}
+
+
+#one.x #two.y #three.z g {
+    key: value;
+}
+#one #two #three h {
+    @extend g;
+}
+
+
+#one #two #three i {
+    key: value;
+}
+#one.x #two.y #three.z j {
+    @extend i;
+}
+
+
+#one #two k {
+    key: value;
+}
+#two #three l {
+    @extend k;
+}
+
+
+#two #three m {
+    key: value;
+}
+#one #two n {
+    @extend m;
+}
+
+
+#one #two #three o {
+    key: value;
+}
+#one #two #three #four p {
+    @extend o;
+}
+
+
+#one #two #three #four q {
+    key: value;
+}
+#one #two #three r {
+    @extend q;
+}
+
+
+#one #two #four s {
+    key: value;
+}
+#one #three #four t {
+    @extend s;
+}
+
+
+#one #three #five u {
+    key: value;
+}
+#two #three #four v {
+    @extend u;
+}
+
+
+#one #two #four #five w {
+    key: value;
+}
+#one #three #four #five x {
+    @extend w;
+}
+
+
+// DEVIATION from ruby sass
+one two one three one four one y {
+    key: value;
+}
+five one three one six z {
+    @extend y;
+}
+
+
+// DEVIATION from ruby sass
+five one three one six aa {
+    key: value;
+}
+one two one three one four one bb {
+    @extend aa;
+}