← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/globbing.py

  • Committer: John Arbash Meinel
  • Date: 2008-10-04 14:10:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3805.
  • Revision ID: john@arbash-meinel.com-20081004141013-yskxjlwtuy2k18ue
Playing around with expanding requests for btree index nodes into neighboring nodes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/globbing.py
1
 
# Copyright (C) 2006-2011 Canonical Ltd
 
1
# Copyright (C) 2006, 2008 Canonical Ltd
2
2
 
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
"""Tools for converting globs to regular expressions.
18
18
 
22
22
 
23
23
import re
24
24
 
25
 
from bzrlib import (
26
 
    errors,
27
 
    lazy_regex,
28
 
    )
29
25
from bzrlib.trace import (
30
 
    mutter,
31
 
    warning,
 
26
    warning
32
27
    )
33
28
 
34
29
 
41
36
    must not contain capturing groups.
42
37
    """
43
38
 
44
 
    _expand = lazy_regex.lazy_compile(ur'\\&')
 
39
    _expand = re.compile(ur'\\&')
45
40
 
46
41
    def __init__(self, source=None):
47
42
        self._pat = None
57
52
 
58
53
        The pattern must not contain capturing groups.
59
54
        The replacement might be either a string template in which \& will be
60
 
        replaced with the match, or a function that will get the matching text
61
 
        as argument. It does not get match object, because capturing is
 
55
        replaced with the match, or a function that will get the matching text  
 
56
        as argument. It does not get match object, because capturing is 
62
57
        forbidden anyway.
63
58
        """
64
59
        self._pat = None
77
72
 
78
73
    def __call__(self, text):
79
74
        if not self._pat:
80
 
            self._pat = lazy_regex.lazy_compile(
 
75
            self._pat = re.compile(
81
76
                    u'|'.join([u'(%s)' % p for p in self._pats]),
82
77
                    re.UNICODE)
83
78
        return self._pat.sub(self._do_sub, text)
165
160
 
166
161
    Patterns are translated to regular expressions to expidite matching.
167
162
 
168
 
    The regular expressions for multiple patterns are aggregated into
169
 
    a super-regex containing groups of up to 99 patterns.
 
163
    The regular expressions for multiple patterns are aggregated into 
 
164
    a super-regex containing groups of up to 99 patterns.  
170
165
    The 99 limitation is due to the grouping limit of the Python re module.
171
166
    The resulting super-regex and associated patterns are stored as a list of
172
167
    (regex,[patterns]) in _regex_patterns.
173
 
 
 
168
    
174
169
    For performance reasons the patterns are categorised as extension patterns
175
170
    (those that match against a file extension), basename patterns
176
171
    (those that match against the basename of the filename),
177
172
    and fullpath patterns (those that match against the full path).
178
 
    The translations used for extensions and basenames are relatively simpler
 
173
    The translations used for extensions and basenames are relatively simpler 
179
174
    and therefore faster to perform than the fullpath patterns.
180
175
 
181
 
    Also, the extension patterns are more likely to find a match and
 
176
    Also, the extension patterns are more likely to find a match and 
182
177
    so are matched first, then the basename patterns, then the fullpath
183
178
    patterns.
184
179
    """
185
 
    # We want to _add_patterns in a specific order (as per type_list below)
186
 
    # starting with the shortest and going to the longest.
187
 
    # As some Python version don't support ordered dicts the list below is
188
 
    # used to select inputs for _add_pattern in a specific order.
189
 
    pattern_types = [ "extension", "basename", "fullpath" ]
190
 
 
191
 
    pattern_info = {
192
 
        "extension" : {
193
 
            "translator" : _sub_extension,
194
 
            "prefix" : r'(?:.*/)?(?!.*/)(?:.*\.)'
195
 
        },
196
 
        "basename" : {
197
 
            "translator" : _sub_basename,
198
 
            "prefix" : r'(?:.*/)?(?!.*/)'
199
 
        },
200
 
        "fullpath" : {
201
 
            "translator" : _sub_fullpath,
202
 
            "prefix" : r''
203
 
        },
204
 
    }
205
 
 
206
180
    def __init__(self, patterns):
207
181
        self._regex_patterns = []
208
 
        pattern_lists = {
209
 
            "extension" : [],
210
 
            "basename" : [],
211
 
            "fullpath" : [],
212
 
        }
 
182
        path_patterns = []
 
183
        base_patterns = []
 
184
        ext_patterns = []
213
185
        for pat in patterns:
214
186
            pat = normalize_pattern(pat)
215
 
            pattern_lists[Globster.identify(pat)].append(pat)
216
 
        pi = Globster.pattern_info
217
 
        for t in Globster.pattern_types:
218
 
            self._add_patterns(pattern_lists[t], pi[t]["translator"],
219
 
                pi[t]["prefix"])
 
187
            if pat.startswith(u'RE:') or u'/' in pat:
 
188
                path_patterns.append(pat)
 
189
            elif pat.startswith(u'*.'):
 
190
                ext_patterns.append(pat)
 
191
            else:
 
192
                base_patterns.append(pat)
 
193
        self._add_patterns(ext_patterns,_sub_extension,
 
194
            prefix=r'(?:.*/)?(?!.*/)(?:.*\.)')
 
195
        self._add_patterns(base_patterns,_sub_basename, 
 
196
            prefix=r'(?:.*/)?(?!.*/)')
 
197
        self._add_patterns(path_patterns,_sub_fullpath) 
220
198
 
221
199
    def _add_patterns(self, patterns, translator, prefix=''):
222
200
        while patterns:
223
 
            grouped_rules = [
224
 
                '(%s)' % translator(pat) for pat in patterns[:99]]
 
201
            grouped_rules = ['(%s)' % translator(pat) for pat in patterns[:99]]
225
202
            joined_rule = '%s(?:%s)$' % (prefix, '|'.join(grouped_rules))
226
 
            # Explicitly use lazy_compile here, because we count on its
227
 
            # nicer error reporting.
228
 
            self._regex_patterns.append((
229
 
                lazy_regex.lazy_compile(joined_rule, re.UNICODE),
 
203
            self._regex_patterns.append((re.compile(joined_rule, re.UNICODE), 
230
204
                patterns[:99]))
231
205
            patterns = patterns[99:]
232
206
 
233
207
    def match(self, filename):
234
208
        """Searches for a pattern that matches the given filename.
235
 
 
 
209
        
236
210
        :return A matching pattern or None if there is no matching pattern.
237
211
        """
238
 
        try:
239
 
            for regex, patterns in self._regex_patterns:
240
 
                match = regex.match(filename)
241
 
                if match:
242
 
                    return patterns[match.lastindex -1]
243
 
        except errors.InvalidPattern, e:
244
 
            # We can't show the default e.msg to the user as thats for
245
 
            # the combined pattern we sent to regex. Instead we indicate to
246
 
            # the user that an ignore file needs fixing.
247
 
            mutter('Invalid pattern found in regex: %s.', e.msg)
248
 
            e.msg = "File ~/.bazaar/ignore or .bzrignore contains error(s)."
249
 
            bad_patterns = ''
250
 
            for _, patterns in self._regex_patterns:
251
 
                for p in patterns:
252
 
                    if not Globster.is_pattern_valid(p):
253
 
                        bad_patterns += ('\n  %s' % p)
254
 
            e.msg += bad_patterns
255
 
            raise e
 
212
        for regex, patterns in self._regex_patterns:
 
213
            match = regex.match(filename)
 
214
            if match:
 
215
                return patterns[match.lastindex -1]
256
216
        return None
257
217
 
258
 
    @staticmethod
259
 
    def identify(pattern):
260
 
        """Returns pattern category.
261
 
 
262
 
        :param pattern: normalized pattern.
263
 
        Identify if a pattern is fullpath, basename or extension
264
 
        and returns the appropriate type.
265
 
        """
266
 
        if pattern.startswith(u'RE:') or u'/' in pattern:
267
 
            return "fullpath"
268
 
        elif pattern.startswith(u'*.'):
269
 
            return "extension"
270
 
        else:
271
 
            return "basename"
272
 
 
273
 
    @staticmethod
274
 
    def is_pattern_valid(pattern):
275
 
        """Returns True if pattern is valid.
276
 
 
277
 
        :param pattern: Normalized pattern.
278
 
        is_pattern_valid() assumes pattern to be normalized.
279
 
        see: globbing.normalize_pattern
280
 
        """
281
 
        result = True
282
 
        translator = Globster.pattern_info[Globster.identify(pattern)]["translator"]
283
 
        tpattern = '(%s)' % translator(pattern)
284
 
        try:
285
 
            re_obj = lazy_regex.lazy_compile(tpattern, re.UNICODE)
286
 
            re_obj.search("") # force compile
287
 
        except errors.InvalidPattern, e:
288
 
            result = False
289
 
        return result
290
 
 
291
 
 
292
 
class ExceptionGlobster(object):
293
 
    """A Globster that supports exception patterns.
294
 
    
295
 
    Exceptions are ignore patterns prefixed with '!'.  Exception
296
 
    patterns take precedence over regular patterns and cause a 
297
 
    matching filename to return None from the match() function.  
298
 
    Patterns using a '!!' prefix are highest precedence, and act 
299
 
    as regular ignores. '!!' patterns are useful to establish ignores
300
 
    that apply under paths specified by '!' exception patterns.
301
 
    """
302
 
    
303
 
    def __init__(self,patterns):
304
 
        ignores = [[], [], []]
305
 
        for p in patterns:
306
 
            if p.startswith(u'!!'):
307
 
                ignores[2].append(p[2:])
308
 
            elif p.startswith(u'!'):
309
 
                ignores[1].append(p[1:])
310
 
            else:
311
 
                ignores[0].append(p)
312
 
        self._ignores = [Globster(i) for i in ignores]
313
 
        
314
 
    def match(self, filename):
315
 
        """Searches for a pattern that matches the given filename.
316
 
 
317
 
        :return A matching pattern or None if there is no matching pattern.
318
 
        """
319
 
        double_neg = self._ignores[2].match(filename)
320
 
        if double_neg:
321
 
            return "!!%s" % double_neg
322
 
        elif self._ignores[1].match(filename):
323
 
            return None
324
 
        else:
325
 
            return self._ignores[0].match(filename)
326
218
 
327
219
class _OrderedGlobster(Globster):
328
220
    """A Globster that keeps pattern order."""
336
228
        self._regex_patterns = []
337
229
        for pat in patterns:
338
230
            pat = normalize_pattern(pat)
339
 
            t = Globster.identify(pat)
340
 
            self._add_patterns([pat], Globster.pattern_info[t]["translator"],
341
 
                Globster.pattern_info[t]["prefix"])
342
 
 
343
 
 
344
 
_slashes = lazy_regex.lazy_compile(r'[\\/]+')
 
231
            if pat.startswith(u'RE:') or u'/' in pat:
 
232
                self._add_patterns([pat], _sub_fullpath) 
 
233
            elif pat.startswith(u'*.'):
 
234
                self._add_patterns([pat], _sub_extension,
 
235
                    prefix=r'(?:.*/)?(?!.*/)(?:.*\.)')
 
236
            else:
 
237
                self._add_patterns([pat], _sub_basename, 
 
238
                    prefix=r'(?:.*/)?(?!.*/)')
 
239
 
 
240
 
345
241
def normalize_pattern(pattern):
346
242
    """Converts backslashes in path patterns to forward slashes.
347
 
 
 
243
    
348
244
    Doesn't normalize regular expressions - they may contain escapes.
349
245
    """
350
 
    if not (pattern.startswith('RE:') or pattern.startswith('!RE:')):
351
 
        pattern = _slashes.sub('/', pattern)
352
 
    if len(pattern) > 1:
353
 
        pattern = pattern.rstrip('/')
354
 
    return pattern
 
246
    if not pattern.startswith('RE:'):
 
247
        pattern = pattern.replace('\\','/')
 
248
    return pattern.rstrip('/')