3
\$\begingroup\$

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
\$\endgroup\$

2 Answers 2

6
\$\begingroup\$
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.

My rewrite of your code: (I didn't start with your code, but it should support the same features:)

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
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – thabubble
    Jul 20, 2011 at 14:05
  • \$\begingroup\$ @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?) \$\endgroup\$ Jul 20, 2011 at 22:42
  • \$\begingroup\$ @thabubble, I added my own version of the code. \$\endgroup\$ Jul 21, 2011 at 2:55
  • \$\begingroup\$ 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! \$\endgroup\$
    – thabubble
    Jul 21, 2011 at 2:59
  • \$\begingroup\$ Wow your code looks really neat! :) \$\endgroup\$
    – thabubble
    Jul 21, 2011 at 3:01
2
\$\begingroup\$

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 ...
\$\endgroup\$
6
  • \$\begingroup\$ 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? \$\endgroup\$
    – thabubble
    Jul 20, 2011 at 10:21
  • \$\begingroup\$ @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. \$\endgroup\$
    – S.Lott
    Jul 20, 2011 at 10:59
  • \$\begingroup\$ 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)]" \$\endgroup\$
    – thabubble
    Jul 20, 2011 at 14:33
  • \$\begingroup\$ "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? \$\endgroup\$
    – S.Lott
    Jul 20, 2011 at 15:11
  • \$\begingroup\$ 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. \$\endgroup\$
    – thabubble
    Jul 20, 2011 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.