Path 1: 1181 calls (0.33)

→ alo 21 (60) 6 (29) 1 (27) 3 (23) 0 (16) 13 (6) 16 (5) 31 (4) 9 (4) 5 (3)

→ ahi 23 (55) 4 (24) 10 (22) 2 (16) 1 (11) 7 (11) 5 (8) 3 (8) 35 (6) 22 (6)

→ blo 21 (54) 6 (29) 1 (25) 3 (22) 0 (16) 13 (9) 9 (7) 2 (6) 16 (5) 31 (4)

→ bhi 23 (55) 7 (29) 4 (24) 2 (15) 1 (12) 14 (9) 5 (8) 3 (8) 10 (7) 35 (5)

↩ return Match (1181)

19 run 18 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 2: 1011 calls (0.28)

→ alo 0 (10) 6 (2) 2 (1) 4 (1) 8 (1) 10 (1) 12 (1) 14 (1) 16 (1) 18 (1)

→ ahi 2000 (999) 45 (4) 39 (3) 41 (3) 10 (2)

→ blo 0 (10) 6 (2) 20 (2) 2 (1) 4 (1) 8 (1) 10 (1) 12 (1) 14 (1) 16 (1)

→ bhi 2000 (999) 45 (4) 41 (3) 10 (2) 35 (2) 38 (1)

↩ return Match (1011)

27 run 10 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 3: 137 calls (0.04)

→ alo 40 (38) 23 (36) 13 (34) 46 (6) 34 (4) 38 (4) 48 (4) 57 (3) 54 (3) 29 (2)

→ ahi 41 (38) 27 (36) 15 (34) 55 (7) 43 (4) 48 (4) 60 (4) 58 (4) 31 (2) 47 (2)

→ blo 25 (36) 17 (36) 15 (34) 34 (8) 40 (8) 38 (4) 42 (3) 48 (3) 29 (2) 39 (2)

→ bhi 41 (40) 29 (36) 17 (34) 43 (11) 50 (9) 48 (4) 31 (2) 101 (1)

↩ return Match (137)

22 run 15 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 4: 110 calls (0.03)

→ alo 16 (102) 5 (6) 29 (2)

→ ahi 36 (52) 30 (51) 14 (6) 40 (1)

→ blo 16 (102) 5 (6) 29 (2)

→ bhi 36 (51) 30 (51) 14 (6) 35 (2)

↩ return Match (110)

26 run 11 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 5: 108 calls (0.03)

→ alo 0 (106) 5 (2)

→ ahi 5 (88) 16 (18) 11 (2)

→ blo 0 (106) 5 (2)

→ bhi 5 (54) 7 (34) 13 (18) 11 (2)

↩ return Match (108)

26 run 11 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 6: 103 calls (0.03)

→ alo 0 (103)

→ ahi 27 (36) 30 (36) 23 (11) 35 (9) 25 (5) 13 (4) 8 (2)

→ blo 0 (103)

→ bhi 29 (36) 7 (36) 23 (8) 15 (7) 25 (6) 13 (4) 27 (4) 10 (2)

↩ return Match (103)

30 run 7 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 7: 102 calls (0.03)

→ alo 21 (54) 29 (18) 13 (12) 31 (7) 33 (4) 11 (3) 14 (3) 41 (1)

→ ahi 25 (54) 41 (21) 16 (18) 45 (4) 36 (3) 55 (1) 39 (1)

→ blo 21 (54) 26 (18) 13 (12) 31 (7) 11 (3) 14 (3) 37 (3) 41 (1) 34 (1)

→ bhi 25 (54) 33 (18) 16 (18) 45 (4) 36 (3) 41 (3) 55 (1) 38 (1)

↩ return Match (102)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 8: 102 calls (0.03)

→ alo 0 (102)

→ ahi 36 (55) 41 (20) 55 (7) 43 (4) 48 (4) 60 (4) 58 (4) 47 (2) 50 (1) 40 (1)

→ blo 0 (102)

→ bhi 36 (54) 33 (18) 43 (11) 50 (9) 48 (4) 41 (4) 35 (2)

↩ return Match (102)

29 run 8 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 9: 85 calls (0.02)

→ alo 16 (54) 24 (18) 5 (3) 25 (2) 34 (2) 21 (2) 31 (2) 40 (2)

→ ahi 25 (54) 41 (22) 47 (4) 22 (3) 36 (1) 40 (1)

→ blo 16 (54) 21 (20) 25 (4) 34 (4) 5 (3)

→ bhi 25 (54) 33 (18) 41 (8) 22 (3) 35 (2)

↩ return Match (85)

26 run 11 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 10: 69 calls (0.02)

→ alo 0 (32) 33 (15) 5 (6) 23 (5) 21 (4) 2 (3) 13 (2) 40 (1) 3 (1)

→ ahi 35 (15) 2 (12) 6 (7) 4 (7) 3 (5) 5 (5) 25 (5) 23 (4) 45 (2) 15 (2)

→ blo 0 (32) 21 (11) 25 (7) 23 (6) 5 (6) 2 (3) 15 (2) 40 (1) 3 (1)

→ bhi 23 (11) 4 (8) 27 (7) 2 (6) 25 (6) 6 (6) 1 (6) 3 (4) 9 (3) 5 (3)

↩ return Match (69)

21 run 16 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 11: 64 calls (0.02)

→ alo 6 (36) 21 (9) 42 (6) 11 (5) 9 (4) 5 (2) 0 (2)

→ ahi 30 (36) 23 (9) 13 (5) 11 (4) 46 (3) 45 (3) 7 (2) 4 (2)

→ blo 6 (36) 9 (8) 11 (6) 13 (4) 30 (3) 34 (3) 5 (2) 0 (2)

→ bhi 7 (38) 11 (8) 13 (6) 15 (4) 31 (3) 39 (3) 6 (2)

↩ return Match (64)

22 run 15 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 12: 57 calls (0.02)

→ alo 19 (54) 33 (3)

→ ahi 25 (54) 39 (3)

→ blo 19 (54) 37 (3)

→ bhi 25 (54) 39 (3)

↩ return Match (57)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 13: 48 calls (0.01)

→ alo 29 (19) 13 (6) 8 (6) 11 (3) 14 (3) 21 (3) 31 (3) 38 (3) 33 (1) 2 (1)

→ ahi 37 (19) 15 (12) 9 (6) 22 (3) 32 (3) 39 (3) 30 (1) 5 (1)

→ blo 26 (18) 13 (6) 8 (6) 11 (3) 14 (3) 21 (3) 31 (3) 38 (3) 34 (1) 29 (1)

→ bhi 29 (18) 15 (12) 9 (6) 22 (3) 32 (3) 39 (3) 36 (1) 31 (1) 5 (1)

↩ return Match (48)

21 run 16 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 14: 46 calls (0.01)

→ alo 0 (37) 5 (9)

→ ahi 2 (15) 7 (9) 5 (8) 6 (3) 16 (3) 4 (3) 55 (1) 81 (1) 100 (1) 13 (1)

→ blo 0 (37) 5 (9)

→ bhi 2 (15) 7 (9) 5 (7) 4 (5) 6 (3) 16 (3) 55 (1) 80 (1) 101 (1) 13 (1)

↩ return Match (46)

24 run 13 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 15: 40 calls (0.01)

→ alo 0 (40)

→ ahi 36 (36) 28 (3) 29 (1)

→ blo 0 (40)

→ bhi 38 (37) 28 (3)

↩ return Match (40)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 16: 36 calls (0.01)

→ alo 0 (36)

→ ahi 41 (36)

→ blo 0 (36)

→ bhi 41 (36)

↩ return Match (36)

27 run 10 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 17: 34 calls (0.01)

→ alo 13 (34)

→ ahi 27 (34)

→ blo 15 (34)

→ bhi 29 (34)

↩ return Match (34)

31 run 6 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 18: 31 calls (0.01)

→ alo 0 (31)

→ ahi 4 (22) 16 (4) 12 (4) 6 (1)

→ blo 0 (31)

→ bhi 4 (29) 6 (2)

↩ return Match (31)

20 run 17 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 19: 28 calls (0.01)

→ alo 2 (13) 0 (11) 9 (4)

→ ahi 16 (10) 4 (8) 12 (7) 10 (2) 6 (1)

→ blo 2 (13) 0 (11) 9 (4)

→ bhi 4 (22) 10 (4) 6 (2)

↩ return Match (28)

19 run 18 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 20: 26 calls (0.01)

→ alo 0 (18) 3 (2) 1 (2) 1998 (1) 34 (1) 19 (1) 2 (1)

→ ahi 4 (11) 6 (8) 36 (2) 2000 (1) 13 (1) 39 (1) 27 (1) 5 (1)

→ blo 0 (18) 2 (4) 1998 (1) 3 (1) 30 (1) 20 (1)

→ bhi 4 (11) 5 (7) 38 (2) 6 (2) 2000 (1) 13 (1) 35 (1) 23 (1)

↩ return Match (26)

24 run 13 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 21: 25 calls (0.01)

→ alo 11 (21) 7 (2) 5 (1) 0 (1)

→ ahi 13 (18) 12 (3) 8 (2) 7 (1) 2 (1)

→ blo 8 (18) 15 (3) 9 (2) 5 (1) 0 (1)

→ bhi 10 (21) 16 (3) 2 (1)

↩ return Match (25)

22 run 15 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 22: 21 calls (0.01)

→ alo 5 (12) 33 (6) 10 (3)

→ ahi 16 (12) 60 (3) 55 (3) 22 (3)

→ blo 5 (12) 21 (3) 25 (3) 10 (3)

→ bhi 16 (12) 43 (3) 50 (3) 22 (3)

↩ return Match (21)

29 run 8 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 23: 20 calls (0.01)

→ alo 0 (20)

→ ahi 13 (18) 15 (2)

→ blo 0 (20)

→ bhi 10 (18) 17 (2)

↩ return Match (20)

29 run 8 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 24: 19 calls (0.01)

→ alo 6 (18) 5 (1)

→ ahi 13 (19)

→ blo 6 (18) 5 (1)

→ bhi 10 (18) 13 (1)

↩ return Match (19)

28 run 9 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 25: 18 calls (0.0)

→ alo 0 (18)

→ ahi 16 (12) 14 (6)

→ blo 0 (18)

→ bhi 16 (12) 14 (6)

↩ return Match (18)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 26: 17 calls (0.0)

→ alo 0 (13) 5 (4)

→ ahi 7 (3) 22 (3) 13 (2) 10 (2) 11 (2) 19 (2) 16 (2) 14 (1)

→ blo 0 (13) 5 (4)

→ bhi 13 (4) 10 (4) 7 (3) 22 (3) 11 (2) 23 (1)

↩ return Match (17)

26 run 11 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 27: 16 calls (0.0)

→ alo 16 (4) 3 (3) 5 (3) 9 (3) 11 (1) 26 (1) 29 (1)

→ ahi 16 (9) 45 (4) 55 (2) 39 (1)

→ blo 16 (4) 3 (3) 5 (3) 9 (3) 11 (1) 26 (1) 29 (1)

→ bhi 16 (9) 45 (4) 55 (2) 38 (1)

↩ return Match (16)

28 run 9 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 28: 13 calls (0.0)

→ alo 0 (8) 10 (3) 6 (2)

→ ahi 12 (6) 5 (4) 8 (2) 13 (1)

→ blo 0 (8) 10 (3) 6 (2)

→ bhi 16 (6) 5 (4) 10 (2) 13 (1)

↩ return Match (13)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 29: 13 calls (0.0)

→ alo 0 (13)

→ ahi 23 (8) 11 (4) 13 (1)

→ blo 0 (13)

→ bhi 11 (11) 13 (2)

↩ return Match (13)

29 run 8 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 30: 9 calls (0.0)

→ alo 21 (6) 42 (3)

→ ahi 23 (6) 48 (3)

→ blo 30 (3) 9 (3) 13 (3)

→ bhi 33 (3) 11 (3) 15 (3)

↩ return Match (9)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 31: 6 calls (0.0)

→ alo 33 (6)

→ ahi 48 (3) 45 (3)

→ blo 21 (3) 25 (3)

→ bhi 33 (3) 39 (3)

↩ return Match (6)

30 run 7 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 32: 6 calls (0.0)

→ alo 5 (6)

→ ahi 9 (6)

→ blo 5 (6)

→ bhi 9 (6)

↩ return Match (6)

26 run 11 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 33: 5 calls (0.0)

→ alo 0 (5)

→ ahi 0 (5)

→ blo 0 (5)

→ bhi 0 (5)

↩ return Match (5)

12 run 25 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 34: 4 calls (0.0)

→ alo 5 (4)

→ ahi 13 (2) 19 (2)

→ blo 5 (4)

→ bhi 13 (4)

↩ return Match (4)

25 run 12 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 35: 4 calls (0.0)

→ alo 10 (3) 8 (1)

→ ahi 12 (3) 14 (1)

→ blo 10 (3) 8 (1)

→ bhi 12 (3) 23 (1)

↩ return Match (4)

23 run 14 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 36: 3 calls (0.0)

→ alo 0 (3)

→ ahi 16 (3)

→ blo 0 (3)

→ bhi 16 (3)

↩ return Match (3)

28 run 9 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 37: 3 calls (0.0)

→ alo 10 (3)

→ ahi 16 (3)

→ blo 10 (3)

→ bhi 16 (3)

↩ return Match (3)

27 run 10 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 38: 3 calls (0.0)

→ alo 16 (3)

→ ahi 36 (3)

→ blo 16 (3)

→ bhi 36 (3)

↩ return Match (3)

30 run 7 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 39: 1 calls (0.0)

→ alo 0 (1)

→ ahi None (1)

→ blo 0 (1)

→ bhi None (1)

↩ return Match (1)

26 run 11 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 40: 1 calls (0.0)

→ alo 2 (1)

→ ahi None (1)

→ blo 4 (1)

→ bhi None (1)

↩ return Match (1)

27 run 10 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 41: 1 calls (0.0)

→ alo 0 (1)

→ ahi None (1)

→ blo 1 (1)

→ bhi 5 (1)

↩ return Match (1)

24 run 13 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 42: 1 calls (0.0)

→ alo 0 (1)

→ ahi 5 (1)

→ blo 0 (1)

→ bhi 203 (1)

↩ return Match (1)

27 run 10 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 43: 1 calls (0.0)

→ alo 2 (1)

→ ahi 13 (1)

→ blo 2 (1)

→ bhi 13 (1)

↩ return Match (1)

29 run 8 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)
            

Path 44: 1 calls (0.0)

→ alo 9 (1)

→ ahi 13 (1)

→ blo 12 (1)

→ bhi 13 (1)

↩ return Match (1)

23 run 14 not run

1def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):
2        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
3
4        By default it will find the longest match in the entirety of a and b.
5
6        If isjunk is not defined:
7
8        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
9            alo <= i <= i+k <= ahi
10            blo <= j <= j+k <= bhi
11        and for all (i',j',k') meeting those conditions,
12            k >= k'
13            i <= i'
14            and if i == i', j <= j'
15
16        In other words, of all maximal matching blocks, return one that
17        starts earliest in a, and of all those maximal matching blocks that
18        start earliest in a, return the one that starts earliest in b.
19
20        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
21        >>> s.find_longest_match(0, 5, 0, 9)
22        Match(a=0, b=4, size=5)
23
24        If isjunk is defined, first the longest matching block is
25        determined as above, but with the additional restriction that no
26        junk element appears in the block.  Then that block is extended as
27        far as possible by matching (only) junk elements on both sides.  So
28        the resulting block never matches on junk except as identical junk
29        happens to be adjacent to an "interesting" match.
30
31        Here's the same example as before, but considering blanks to be
32        junk.  That prevents " abcd" from matching the " abcd" at the tail
33        end of the second sequence directly.  Instead only the "abcd" can
34        match, and matches the leftmost "abcd" in the second sequence:
35
36        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
37        >>> s.find_longest_match(0, 5, 0, 9)
38        Match(a=1, b=0, size=4)
39
40        If no blocks match, return (alo, blo, 0).
41
42        >>> s = SequenceMatcher(None, "ab", "c")
43        >>> s.find_longest_match(0, 2, 0, 1)
44        Match(a=0, b=0, size=0)
45        """
46
47        # CAUTION:  stripping common prefix or suffix would be incorrect.
48        # E.g.,
49        #    ab
50        #    acab
51        # Longest matching block is "ab", but if common prefix is
52        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
53        # strip, so ends up claiming that ab is changed to acab by
54        # inserting "ca" in the middle.  That's minimal but unintuitive:
55        # "it's obvious" that someone inserted "ac" at the front.
56        # Windiff ends up at the same place as diff, but by pairing up
57        # the unique 'b's and then matching the first two 'a's.
58
59        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__
60        if ahi is None:
61            ahi = len(a)
62        if bhi is None:
63            bhi = len(b)
64        besti, bestj, bestsize = alo, blo, 0
65        # find longest junk-free match
66        # during an iteration of the loop, j2len[j] = length of longest
67        # junk-free match ending with a[i-1] and b[j]
68        j2len = {}
69        nothing = []
70        for i in range(alo, ahi):
71            # look at all instances of a[i] in b; note that because
72            # b2j has no junk keys, the loop is skipped if a[i] is junk
73            j2lenget = j2len.get
74            newj2len = {}
75            for j in b2j.get(a[i], nothing):
76                # a[i] matches b[j]
77                if j < blo:
78                    continue
79                if j >= bhi:
80                    break
81                k = newj2len[j] = j2lenget(j-1, 0) + 1
82                if k > bestsize:
83                    besti, bestj, bestsize = i-k+1, j-k+1, k
84            j2len = newj2len
85
86        # Extend the best by non-junk elements on each end.  In particular,
87        # "popular" non-junk elements aren't in b2j, which greatly speeds
88        # the inner loop above, but also means "the best" match so far
89        # doesn't contain any junk *or* popular non-junk elements.
90        while besti > alo and bestj > blo and \
91              not isbjunk(b[bestj-1]) and \
92              a[besti-1] == b[bestj-1]:
93            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
94        while besti+bestsize < ahi and bestj+bestsize < bhi and \
95              not isbjunk(b[bestj+bestsize]) and \
96              a[besti+bestsize] == b[bestj+bestsize]:
97            bestsize += 1
98
99        # Now that we have a wholly interesting match (albeit possibly
100        # empty!), we may as well suck up the matching junk on each
101        # side of it too.  Can't think of a good reason not to, and it
102        # saves post-processing the (possibly considerable) expense of
103        # figuring out what to do with it.  In the case of an empty
104        # interesting match, this is clearly the right thing to do,
105        # because no other kind of match is possible in the regions.
106        while besti > alo and bestj > blo and \
107              isbjunk(b[bestj-1]) and \
108              a[besti-1] == b[bestj-1]:
109            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
110        while besti+bestsize < ahi and bestj+bestsize < bhi and \
111              isbjunk(b[bestj+bestsize]) and \
112              a[besti+bestsize] == b[bestj+bestsize]:
113            bestsize = bestsize + 1
114
115        return Match(besti, bestj, bestsize)