# Brace pairing ({}[]()<>) cleanup/speedup

This is working as expected, except in the speed area + I need to make it more readable and shorter if possible, I probably have lot's of things I don't need :).

Edit it is working now

charset = dict(opening='{[(<',\
closing='}])>',\
string = ('"', "'"),\
comment=(('<!--', '-->'), ('"""', '"""'), ('#', '\n')))

allowed = ''.join([x[0][0] + x[1][0] for x in charset['comment']])
allowed += ''.join(charset['string'])
allowed += charset['opening']
allowed += charset['closing']

def brace_check(text):
o = []
c = []
notr = []
found = []
busy = False
last_pos = None
for i in xrange(len(text)):
ch = text[i]
if not busy:
cont = True
for comment in charset['comment']:
if ch == comment[0][0]:
como = text[i:len(comment[0])]
if como == comment[0]:
busy = comment[1]
if ch in charset['opening']:
last_pos = i
cont = False
break
if cont:
if ch in charset['string']:
busy = ch
elif ch in charset['opening']:
o.append((ch, i))
elif  ch in charset['closing']:
c.append((ch, i))
else:
if ch == busy[0]:
if len(busy) == 1:
comc = ch
else:
comc = text[i:i + len(busy)]
if comc == busy:
if last_pos is not None:
if busy[-1] in charset['closing']:
found.append((last_pos, i))
last_pos = None
text = text[:i] + '\n' * len(comc) +\
text[i + len(comc):]
busy = not busy
elif busy in charset['string']:
if ch == '\n':
busy = not busy
for t, e in reversed(o):
try:
n = next((b, v) for b, v in c\
if b == charset['closing'][\
charset['opening'].find(t)] and v > e)
c.remove(n)
n = n[1]
if found != []:
if e < found[-1][0] and n > found[-1][0] and n < found[-1][1]\
or e < found[-1][1] and n > found[-1][1] and e > found[-1][0]:
found.append((n, False))
n = False
except StopIteration:
n = False
found.append((e, n))
for t, e in c:
found.append((e, False))
return found


def brace_check(string):


string is the name of a python module, it might be best to avoid it

    # Imports
import re


imports should be done at the module level not inside a function

    # Configuration
charset = dict(opening='{[(<',\
closing='}])>',\
string = ['"', "'"],\
single=['#', '//'],\
multi=[['/*', '*/'], '"""', ['<!--', '-->']])


Constant values should be at the module level not inside the function

    found = []# found objects


found isn't used until way later. Declare it way later.

    notr = []# busy locations


notr and its comment don't suggest anything the same.

    temp = {}# temporary holding for opening braces
end = {}# temporary holding for closing braces


All variables are temporary. Don't give names or comments that tell me such obvious things

    # Find all ocurrances and its position
newline = [m.start() for m in re.finditer('\n', string)] # every newline

for mn in charset['multi']:# find every multiline comment
if type(mn) == type(str()):# if there only is one element
op = [m.start() for m in re.finditer(re.escape(mn), string)]
cl = op[1::2]
op = op[0::2]
mn = (mn, mn)

else:
op = [m.start() for m in re.finditer(re.escape(mn[0]), string)]
cl = [m.start() for m in re.finditer(re.escape(mn[1]), string)]


These short cryptic variables name are asking for confusion.

        for i in xrange(len(op)):# find and close every comment
om = op[i]


Use the enumerate function. It lets you use a foreach loop and get the indexes at the same time try: cm = next(v for v in cl if v > om) + len(mn[1])

add a line like: start_comment, end_comment = mn, that way you can avoid the indexes are your code will be clearer.

                if mn[0][0] in charset['opening'] and\
mn[1][-1] in charset['closing']:
for i in xrange(om + 1, cm - 1):
if i not in notr:
notr.append(i)


Rather the constantly checking whether a value is in notr, use a set. Then the last three lines can simply be notr.add( xrange(om + 1, cm - 1) )

                else:
for i in xrange(om, cm):
if i not in notr:
notr.append(i)


Did we really need that special case?

            except:


Don't catch all exceptions, you'll hide bugs that way. Instead, catch only the specific type of exception you are interested in. Also, you want as little code in the try block as possible to avoid catching other stray exceptions

                for i in xrange(om, len(string)):
if i not in notr:
notr.append(i)


You at least need a comment explaining why this make sense.

        del op, cl


Don't del variables, its rarely useful.

    for sn in charset['single']:
rep = [m.start() for m in re.finditer(re.escape(sn), string)]
for s in rep:
try:
new = next(v for v in newline if v > s)
except:
new = len(string)
newline.append(len(string))


Why not use the string search functions rather then having built a newline list? Also, if you need to treat the end of input as a newline, put that in when you create the list not in an exception handler.

            if not s in notr:
for i in xrange(s, new):
if i not in notr:
notr.append(i)
newline.remove(new)
del rep

for sn in charset['string']:
rep = [m.start() for m in re.finditer(re.escape(sn), string)]
last = False
for i in xrange(len(rep)):
if not last:
s = rep[i]
if s not in notr:
try:
new = next(v for v in newline if v > s)
except:
new = len(string)
newline.append(len(string))


If code repeats, you need a function.

                    try:
n = next(v for v in rep if v > s)
except:
n = new + 1
if n < new:
last = True
for i in xrange(s, n + 1):
if i not in notr:
notr.append(i)
else:
for i in xrange(s, new):
if i not in notr:
notr.append(i)
newline.remove(new)
else:
last = False
del rep

for cn in charset['closing']:
on = charset['opening'][charset['closing'].find(cn)]
end[on] = [m.start() for m in re.finditer(re.escape(cn), string)\
if m.start() not in notr]


Given the cn is a single character, use of a regular expression to find it is overkill.

    for on in charset['opening']:
op = [m.start() for m in re.finditer(re.escape(on), string)\
if m.start() not in notr]
for i in xrange(len(op)):
temp[op[i]] = on

for k in sorted(temp.keys(), reverse=True):
try:
c = next(v for v in end[temp[k]] if v > k and v not in notr)
end[temp[k]].remove(c)
for i in xrange(k, c + 1):
if i not in notr:
notr.append(i)
except:
c = False
found.append((k, c))


It seems to me that using a stack would be simpler then what you are doing here.

    for v in end.values():
for c in v:
found.append((c, False))


No explanation is given for what you are putting inside found. I have no idea what the return value means. return found

General thoughts:

The code is complicated, it really should be split up into a lot of functions.

Rather then all that code matching different types of comments and strings, have a set of ignore regexes. The regex should match an entire comment or string which can then be removed.

Your code builds lists of everything which would only serve to complicate what is going on. Lists can be great, but they aren't the solution to every problem.

from nose.tools import assert_equal
import re

class SimpleTokenizer(object):
"""
The constructor takes a dictionary of keys which should be regular
expression strings to arbitrary value. The tokenize method will produce
all the substrings in the text which match the regular expression.
It will return the value provided in the original dictionary
to identify which expression was matched
"""
def __init__(self, data):
# I need a consistent order from data, so I dump the dictionary
# into a list
data = list(data.items())
self.values = [value for key, value in data]
# this regular expression matches any key
self.expression = '|'.join('(%s)' % key for key, value in data)

def tokenize(self, text):
for match in re.finditer(self.expression, text):
# group 0 is the whole string, we subtract one
# to make up for that
yield match.start(), self.values[match.lastindex - 1]

CLOSER = 0
OPENER = 1
IGNORE = 2
class Language(object):
"""
Provides brace checking
"""
def __init__(self, opening, closing, ignore = ()):
"""
opening and closing should be sequences of the same size denoting
the start and end symbols that should matched. Ignore should be a
sequence of regular expression which should be ignored for the
purpose of matching such as comments, strings, etc.
"""

data = {}
for opener, closer in zip(opening, closing):
data[re.escape(opener)] = (OPENER, closer)
data[re.escape(closer)] = (CLOSER, closer)
for ignore in ignore:
data[ignore] = (IGNORE, None)
self._tokenizer = SimpleTokenizer(data)

def check(self, text):
"""
Given text produces the location of the various braces
returns a list of tuple, start, end where a pair of matches
braces exist. If either brace is missing it will be recorded
as None.
"""

braces = []

waiting = []
# waiting is a stack holding the braces which have been opened
# but not yet closed
for idx, (category, extra) in self._tokenizer.tokenize(text):
if category == OPENER:
waiting.append( (extra, len(braces)) )
# we start with None as the end of a brace, it'll be
# updated if we find it
braces.append( (idx, None) )
elif category == CLOSER:
# find the last entry that matches
index = None
for element, element_index in reversed(waiting):
if element == extra:
index = element_index
break

if index is None:
# no matches found
# in that case, record the start as None
braces.append( (None, idx) )
else:
# we found the match, replace the existing record
# with a new one
position, waste = braces[index]
braces[index] = (position, idx)
# elminate anything we had to ignore
del waiting[index:]

return braces

LANGUAGE_TESTS = [
("[()]", [(0, 3), (1, 2)]),
("[(a)]", [(0, 4), (1, 3)]),
("[(]", [(0, 2), (1, None)]),
("[()", [(0, None), (1, 2)]),
("[(])", [(0, 2), (1, None), (None,3)]),
("])", [(None, 0), (None, 1)]),
("(])", [(0, 2), (None, 1)]),
]

def test_basic_language():
language = Language(
opening = '[(',
closing = '])')
def inner(text, expected):
result = language.check(text)
assert_equal(list(result), expected)

for text, expected in LANGUAGE_TESTS:
yield inner, text, expected

STRING_LANGUAGE = [
('[(")]")]', [(0, 7), (1, 6)])
]
def test_string_language():
language = Language(
opening = '[(',
closing = '])',
ignore = [r'"[^"]*"']
)
def inner(text, expected):
result = language.check(text)
assert_equal(list(result), expected)

for text, expected in STRING_LANGUAGE:
yield inner, text, expected

• notr is the range where there are comments, other braces and strings. I don't understand what you mean with to use a set and to use a for loop for checking is what I already have done but it was slower on large text. Found returns the position of opening and closing braces, if there isn't a opeing/closing brace to pair with or it is nested wrongly it returns the position and false. Jul 20, 2011 at 14:05
• @thabubble, don't tell me what you variables are for, give them better names. With a set you don't need a for loop for checking. I'd be surprised if using the set like that was slower, can your provide the code/data you tested with? Don't tell me what found contains, document it in your function. (Also, what is position? character index? line number?) Jul 20, 2011 at 22:42
• @thabubble, I added my own version of the code. Jul 21, 2011 at 2:55
• thanks, but I just got it working, will check yours too, bet there is a lot to learn from there:) Thank you for your help! Jul 21, 2011 at 2:59
• Wow your code looks really neat! :) Jul 21, 2011 at 3:01

You can drop the del statements. They don't help much.

It's much easier to break this into separate functions and simply allow Python's ordinary namespace rules handle the deletes.

The if type(mn) == type(str()):# if there only is one element is a needless volume of code for one special case that isn't really special.

Make the '"""' completely separate from multi and remove the needless if statement. Process it in a separate pass with no if statement in the loop.

Golden Rule: If statements are expensive. Find ways to remove them.

Two "nearly the same" loops for multi and for the """ case avoids an if statement, and improves speed.

Also. multi, single and string aren't proper lists. They're immutable tuples. Eliminate a tiny bit of potential overhead by making them proper tuples.

newline = [m.start() for m in re.finditer('\n', string)] # every newline may be needless complexity. In the single case, a newline character is the implicit "closing" for both of the "single" comments. Perhaps single should be ( ('#','\n'), ('//','\n') ) so that it can be just the same as multi.

Also, if not last at the top of a loop usually means that the last= True line should have been a break statement instead.

In this case, however, it's worse than that. If if not last at the top of the loop is there to step to the next item in the iterator (xrange(len(rep)))

There are two better ways to handle this, both with explicit iterator objects.

This is minimally disruptive

range_iter= iter( xrange( len( rep ) ) )
for i in range_iter:
s= rep[i]
... much logic ...
next( range_iter ) # Skip the next item.  No last=True business.
... more logic ...


This is what you meant. To assign s from rep directly.

rep_iter = iter( rep )
for s in rep_iter:
... much logic ...
next( rep_iter ) # Skip the next item.  No last=True
... more logic ...

• I had the '"""' the same as the others before, but since it is the same on both ends, op and cl had the same values and it got screwed up :/. Any idea how to fix that? Jul 20, 2011 at 10:21
• @thabubble: finditer() is -- obviously -- a bad choice of ways to find comment punctuation in general. It's easily fooled by "nested" comments that should not be paired up. #"""\n is a legal #...\n with a partial comment hidden in the middle. I'll update my answer. Jul 20, 2011 at 10:59
• doesn't "break" break the whole loop so that any other can't be checked? if last = False, previous haven't been paired properly for example '(")\n")\n)' should show "[(0, 7)]" but the only thing I can think that not using last will result in "[(0, 5), (7, False)]" Jul 20, 2011 at 14:33
• "doesn't break break the whole loop"? What do you think you mean by whole loop? When you set last = True, you're going to exit the loop, right? Isn't that the point of setting last = True? Jul 20, 2011 at 15:11
• Nope, sorry, it is there for the pairing of the strings, for example if there is a newline between two supposedly paired quotes, i.e "\n" then they aren't paired, the newline invalidates it. So if the last two quotes where paired correctly then it selects a new, before I had "for i in xrange(0, len(rep), 2):" to select every other, but if there was a newline between it broke it. Jul 20, 2011 at 15:35