← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/cdv/cdvdifflib.py

  • Committer: John Arbash Meinel
  • Date: 2005-11-10 18:35:38 UTC
  • mto: This revision was merged to the branch mainline in revision 1727.
  • Revision ID: john@arbash-meinel.com-20051110183538-80788dec92cd91c1
Found some edge cases that weren't being matched.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/cdv/cdvdifflib.py
30
30
                                      ' isjunk for sequence matching')
31
31
        difflib.SequenceMatcher.__init__(self, isjunk, a, b)
32
32
 
 
33
    def _check_with_diff(self, alo, ahi, blo, bhi, answer):
 
34
        """Use the original diff algorithm on an unmatched section.
 
35
 
 
36
        This will check to make sure the range is worth checking,
 
37
        before doing any work.
 
38
 
 
39
        :param alo: The last line that actually matched
 
40
        :param ahi: The next line that actually matches
 
41
        :param blo: Same as alo, only for the 'b' set
 
42
        :param bhi: Same as ahi
 
43
        :param answer: An array which will have the new ranges appended to it
 
44
        :return: None
 
45
        """
 
46
        # WORKAROUND
 
47
        # recurse_matches has an implementation design
 
48
        # which does not match non-unique lines in the
 
49
        # if they do not touch matching unique lines
 
50
        # so we rerun the regular diff algorithm
 
51
        # if find a large enough chunk.
 
52
 
 
53
        # recurse_matches already looked at the direct
 
54
        # neighbors, so we only need to run if there is
 
55
        # enough space to do so
 
56
        if ahi - alo > 2 and bhi - blo > 2:
 
57
            a = self.a[alo+1:bhi-1]
 
58
            b = self.b[blo+1:bhi-1]
 
59
            m = difflib.SequenceMatcher(None, a, b)
 
60
            new_blocks = m.get_matching_blocks()
 
61
            # difflib always adds a final match
 
62
            new_blocks.pop()
 
63
            for blk in new_blocks:
 
64
                answer.append((blk[0]+alo+1,
 
65
                               blk[1]+blo+1,
 
66
                               blk[2]))
 
67
 
33
68
    def __helper(self, alo, ahi, blo, bhi, answer):
34
69
        matches = []
35
70
        a = self.a[alo:ahi]
47
82
                length += 1
48
83
            else:
49
84
                # New block
50
 
                if start_a is not None:
 
85
                if start_a is None:
 
86
                    # We need to check from 0,0 until the current match
 
87
                    self._check_with_diff(alo-1, i_a+alo, blo-1, i_b+blo, answer)
 
88
                else:
51
89
                    answer.append((start_a+alo, start_b+blo, length))
52
 
                    # WORKAROUND
53
 
                    # recurse_matches has an implementation design
54
 
                    # which does not match non-unique lines in the
55
 
                    # if they do not touch matching unique lines
56
 
                    # so we rerun the regular diff algorithm
57
 
                    # if find a large enough chunk.
 
90
                    self._check_with_diff(start_a+alo+length, i_a+alo,
 
91
                                          start_b+blo+length, i_b+blo,
 
92
                                          answer)
58
93
 
59
 
                    last_match_a = start_a + length
60
 
                    last_match_b = start_b + length
61
 
                    # recurse_matches already looked at the direct
62
 
                    # neighbors, so we only need to run if there is
63
 
                    # enough space to do so
64
 
                    if (i_a - last_match_a > 2
65
 
                        and i_b - last_match_b > 2):
66
 
                        m = SequenceMatcher(None,
67
 
                                            a[last_match_a+1:i_a-1],
68
 
                                            b[last_match_b+1:i_b-1])
69
 
                        new_blocks = m.get_matching_blocks()
70
 
                        # difflib always adds a final match
71
 
                        new_blocks.pop()
72
 
                        for blk in new_blocks:
73
 
                            answer.append((blk[0]+last_match_a+1,
74
 
                                           blk[1]+last_match_b+1,
75
 
                                           blk[2]))
76
94
                start_a = i_a
77
95
                start_b = i_b
78
96
                length = 1
79
97
 
80
98
        if length != 0:
81
 
            answer.append((start_a+blo, start_b+blo, length))
 
99
            answer.append((start_a+alo, start_b+blo, length))
 
100
            self._check_with_diff(start_a+alo+length, ahi+1,
 
101
                                  start_b+blo+length, bhi+1,
 
102
                                  answer)
 
103
        if not matches:
 
104
            # Nothing matched, so we need to send the complete text
 
105
            self._check_with_diff(alo-1, ahi+1, blo-1, bhi+1, answer)
82
106
 
83
107
# This is a version of unified_diff which only adds a factory parameter
84
108
# so that you can override the default SequenceMatcher