comparison mercurial/match.py @ 43076:2372284d9457

formatting: blacken the codebase

This is using my patch to black
(https://github.com/psf/black/pull/826) so we don't un-wrap collection
literals.

Done with:

  hg files 'set:**.py - mercurial/thirdparty/** - "contrib/python-zstandard/**"' | xargs black -S

# skip-blame mass-reformatting only

# no-check-commit reformats foo_bar functions

Differential Revision: https://phab.mercurial-scm.org/D6971

43075:57875cf423c9

    pathutil,
    policy,
    pycompat,
    util,
)
from .utils import (
    stringutil,
)

rustmod = policy.importrust(r'filepatterns')

allpatternkinds = ('re', 'glob', 'path', 'relglob', 'relpath', 'relre',
                   'rootglob',
                   'listfile', 'listfile0', 'set', 'include', 'subinclude',
                   'rootfilesin')
cwdrelativepatternkinds = ('relpath', 'glob')

propertycache = util.propertycache

def _rematcher(regex):
    '''compile the regexp with the best available regexp engine and return a
    matcher function'''
    m = util.re.compile(regex)

        # slightly faster, provided by facebook's re2 bindings
        return m.test_match
    except AttributeError:
        return m.match

def _expandsets(kindpats, ctx=None, listsubrepos=False, badfn=None):
    '''Returns the kindpats list with the 'set' patterns expanded to matchers'''
    matchers = []
    other = []

    for kind, pat, source in kindpats:
        if kind == 'set':
            if ctx is None:
                raise error.ProgrammingError("fileset expression with no "
                                             "context")
            matchers.append(ctx.matchfileset(pat, badfn=badfn))

            if listsubrepos:
                for subpath in ctx.substate:
                    sm = ctx.sub(subpath).matchfileset(pat, badfn=badfn)

                    matchers.append(pm)

            continue
        other.append((kind, pat, source))
    return matchers, other

def _expandsubinclude(kindpats, root):
    '''Returns the list of subinclude matcher args and the kindpats without the
    subincludes in it.'''
    relmatchers = []

            relmatchers.append((prefix, matcherargs))
        else:
            other.append((kind, pat, source))

    return relmatchers, other

def _kindpatsalwaysmatch(kindpats):
    """"Checks whether the kindspats match everything, as e.g.
    'relpath:.' does.
    """
    for kind, pat, source in kindpats:
        if pat != '' or kind not in ['relpath', 'glob']:
            return False
    return True

def _buildkindpatsmatcher(matchercls, root, kindpats, ctx=None,
                          listsubrepos=False, badfn=None):
    matchers = []
    fms, kindpats = _expandsets(kindpats, ctx=ctx,
                                listsubrepos=listsubrepos, badfn=badfn)
    if kindpats:
        m = matchercls(root, kindpats, badfn=badfn)
        matchers.append(m)
    if fms:
        matchers.extend(fms)

        return nevermatcher(badfn=badfn)
    if len(matchers) == 1:
        return matchers[0]
    return unionmatcher(matchers)

def match(root, cwd, patterns=None, include=None, exclude=None, default='glob',
          auditor=None, ctx=None, listsubrepos=False, warn=None,
          badfn=None, icasefs=False):
    r"""build an object to match a set of file patterns

    arguments:
    root - the canonical root of the tree you're matching against
    cwd - the current working directory, if relevant

    if patterns:
        kindpats = normalize(patterns, default, root, cwd, auditor, warn)
        if _kindpatsalwaysmatch(kindpats):
            m = alwaysmatcher(badfn)
        else:
            m = _buildkindpatsmatcher(patternmatcher, root, kindpats, ctx=ctx,
                                      listsubrepos=listsubrepos, badfn=badfn)
    else:
        # It's a little strange that no patterns means to match everything.
        # Consider changing this to match nothing (probably using nevermatcher).
        m = alwaysmatcher(badfn)

    if include:
        kindpats = normalize(include, 'glob', root, cwd, auditor, warn)
        im = _buildkindpatsmatcher(includematcher, root, kindpats, ctx=ctx,
                                   listsubrepos=listsubrepos, badfn=None)
        m = intersectmatchers(m, im)
    if exclude:
        kindpats = normalize(exclude, 'glob', root, cwd, auditor, warn)
        em = _buildkindpatsmatcher(includematcher, root, kindpats, ctx=ctx,
                                   listsubrepos=listsubrepos, badfn=None)
        m = differencematcher(m, em)
    return m

def exact(files, badfn=None):
    return exactmatcher(files, badfn=badfn)

def always(badfn=None):
    return alwaysmatcher(badfn)

def never(badfn=None):
    return nevermatcher(badfn)

def badmatch(match, badfn):
    """Make a copy of the given matcher, replacing its bad method with the given
    one.
    """
    m = copy.copy(match)
    m.bad = badfn
    return m

def _donormalize(patterns, default, root, cwd, auditor=None, warn=None):
    '''Convert 'kind:pat' from the patterns list to tuples with kind and
    normalized and rooted patterns and with listfiles expanded.'''
    kindpats = []

                else:
                    files = files.splitlines()
                files = [f for f in files if f]
            except EnvironmentError:
                raise error.Abort(_("unable to read file list (%s)") % pat)
            for k, p, source in _donormalize(files, default, root, cwd,
                                             auditor, warn):
                kindpats.append((k, p, pat))
            continue
        elif kind == 'include':
            try:
                fullpath = os.path.join(root, util.localpath(pat))
                includepats = readpatternfile(fullpath, warn)
                for k, p, source in _donormalize(includepats, default,
                                                 root, cwd, auditor, warn):
                    kindpats.append((k, p, source or pat))
            except error.Abort as inst:
                raise error.Abort('%s: %s' % (pat, inst[0]))
            except IOError as inst:
                if warn:
                    warn(_("skipping unreadable pattern file '%s': %s\n") %
                         (pat, stringutil.forcebytestr(inst.strerror)))
            continue
        # else: re or relre - which cannot be normalized
        kindpats.append((kind, pat, ''))
    return kindpats

class basematcher(object):

    def __init__(self, badfn=None):
        if badfn is not None:
            self.bad = badfn

    def __call__(self, fn):
        return self.matchfn(fn)
    # Callbacks related to how the matcher is used by dirstate.walk.
    # Subscribers to these events must monkeypatch the matcher object.
    def bad(self, f, msg):
        '''Callback from dirstate.walk for each explicit file that can't be
        found/accessed, with an error message.'''

    def anypats(self):
        '''None of .always(), .isexact(), and .prefix() is true --
        optimizations will be difficult.'''
        return not self.always() and not self.isexact() and not self.prefix()

class alwaysmatcher(basematcher):
    '''Matches everything.'''

    def __init__(self, badfn=None):
        super(alwaysmatcher, self).__init__(badfn)

    def visitchildrenset(self, dir):
        return 'all'

    def __repr__(self):
        return r'<alwaysmatcher>'

class nevermatcher(basematcher):
    '''Matches nothing.'''

    def __init__(self, badfn=None):

        return set()

    def __repr__(self):
        return r'<nevermatcher>'

class predicatematcher(basematcher):
    """A matcher adapter for a simple boolean function"""

    def __init__(self, predfn, predrepr=None, badfn=None):
        super(predicatematcher, self).__init__(badfn)
        self.matchfn = predfn
        self._predrepr = predrepr

    @encoding.strmethod
    def __repr__(self):
        s = (stringutil.buildrepr(self._predrepr)
             or pycompat.byterepr(self.matchfn))
        return '<predicatenmatcher pred=%s>' % s

def normalizerootdir(dir, funcname):
    if dir == '.':
        util.nouideprecwarn("match.%s() no longer accepts "
                            "'.', use '' instead." % funcname, '5.1')
        return ''
    return dir


class patternmatcher(basematcher):

    def visitdir(self, dir):
        dir = normalizerootdir(dir, 'visitdir')
        if self._prefix and dir in self._fileset:
            return 'all'
        return (dir in self._fileset or
                dir in self._dirs or
                any(parentdir in self._fileset
                    for parentdir in util.finddirs(dir)))

    def visitchildrenset(self, dir):
        ret = self.visitdir(dir)
        if ret is True:
            return 'this'

    def prefix(self):
        return self._prefix

    @encoding.strmethod
    def __repr__(self):
        return ('<patternmatcher patterns=%r>' % pycompat.bytestr(self._pats))

# This is basically a reimplementation of util.dirs that stores the children
# instead of just a count of them, plus a small optional optimization to avoid
# some directories we don't need.
class _dirchildren(object):

        # Unlike manifest._splittopdir, this does not suffix `dirname` with a
        # slash.
        oldpos = len(path)
        pos = path.rfind('/')
        while pos != -1:
            yield path[:pos], path[pos + 1:oldpos]
            oldpos = pos
            pos = path.rfind('/', 0, pos)
        yield '', path[:oldpos]

    def get(self, path):
        return self._dirs.get(path, set())

class includematcher(basematcher):

    def __init__(self, root, kindpats, badfn=None):
        super(includematcher, self).__init__(badfn)

        self._pats, self.matchfn = _buildmatch(kindpats, '(?:/|$)', root)
        self._prefix = _prefix(kindpats)

    def visitdir(self, dir):
        dir = normalizerootdir(dir, 'visitdir')
        if self._prefix and dir in self._roots:
            return 'all'
        return (dir in self._roots or
                dir in self._dirs or
                dir in self._parents or
                any(parentdir in self._roots
                    for parentdir in util.finddirs(dir)))

    @propertycache
    def _allparentschildren(self):
        # It may seem odd that we add dirs, roots, and parents, and then
        # restrict to only parents. This is to catch the case of:
        #   dirs = ['foo/bar']
        #   parents = ['foo']
        # if we asked for the children of 'foo', but had only added
        # self._parents, we wouldn't be able to respond ['bar'].
        return _dirchildren(
                itertools.chain(self._dirs, self._roots, self._parents),
                onlyinclude=self._parents)

    def visitchildrenset(self, dir):
        if self._prefix and dir in self._roots:
            return 'all'
        # Note: this does *not* include the 'dir in self._parents' case from
        # visitdir, that's handled below.
        if ('' in self._roots or
            dir in self._roots or
            dir in self._dirs or
            any(parentdir in self._roots
                for parentdir in util.finddirs(dir))):
            return 'this'

        if dir in self._parents:
            return self._allparentschildren.get(dir) or set()
        return set()

    @encoding.strmethod
    def __repr__(self):
        return ('<includematcher includes=%r>' % pycompat.bytestr(self._pats))

class exactmatcher(basematcher):
    r'''Matches the input files exactly. They are interpreted as paths, not
    patterns (so no kind-prefixes).

            return set()

        candidates = self._fileset | self._dirs - {''}
        if dir != '':
            d = dir + '/'
            candidates = set(c[len(d):] for c in candidates if
                             c.startswith(d))
        # self._dirs includes all of the directories, recursively, so if
        # we're attempting to match foo/bar/baz.txt, it'll have '', 'foo',
        # 'foo/bar' in it. Thus we can safely ignore a candidate that has a
        # '/' in it, indicating a it's for a subdir-of-a-subdir; the
        # immediate subdir will be in there without a slash.

    def isexact(self):
        return True

    @encoding.strmethod
    def __repr__(self):
        return ('<exactmatcher files=%r>' % self._files)

class differencematcher(basematcher):
    '''Composes two matchers by matching if the first matches and the second
    does not.

    The second matcher's non-matching-attributes (bad, explicitdir,
    traversedir) are ignored.
    '''
    def __init__(self, m1, m2):
        super(differencematcher, self).__init__()
        self._m1 = m1
        self._m2 = m2
        self.bad = m1.bad

    def isexact(self):
        return self._m1.isexact()

    @encoding.strmethod
    def __repr__(self):
        return ('<differencematcher m1=%r, m2=%r>' % (self._m1, self._m2))

def intersectmatchers(m1, m2):
    '''Composes two matchers by matching if both of them match.

    The second matcher's non-matching-attributes (bad, explicitdir,

    if m2.always():
        m = copy.copy(m1)
        return m
    return intersectionmatcher(m1, m2)

class intersectionmatcher(basematcher):
    def __init__(self, m1, m2):
        super(intersectionmatcher, self).__init__()
        self._m1 = m1
        self._m2 = m2

    def isexact(self):
        return self._m1.isexact() or self._m2.isexact()

    @encoding.strmethod
    def __repr__(self):
        return ('<intersectionmatcher m1=%r, m2=%r>' % (self._m1, self._m2))

class subdirmatcher(basematcher):
    """Adapt a matcher to work on a subdirectory only.

    The paths are remapped to remove/insert the path as needed:

        super(subdirmatcher, self).__init__()
        self._path = path
        self._matcher = matcher
        self._always = matcher.always()

        self._files = [f[len(path) + 1:] for f in matcher._files
                       if f.startswith(path + "/")]

        # If the parent repo had a path to this subrepo and the matcher is
        # a prefix matcher, this submatcher always matches.
        if matcher.prefix():
            self._always = any(f == path for f in matcher._files)

    def prefix(self):
        return self._matcher.prefix() and not self._always

    @encoding.strmethod
    def __repr__(self):
        return ('<subdirmatcher path=%r, matcher=%r>' %
                (self._path, self._matcher))

class prefixdirmatcher(basematcher):
    """Adapt a matcher to work on a parent directory.

    The matcher's non-matching-attributes (bad, explicitdir, traversedir) are

        return [self._pathprefix + f for f in self._matcher._files]

    def matchfn(self, f):
        if not f.startswith(self._pathprefix):
            return False
        return self._matcher.matchfn(f[len(self._pathprefix):])

    @propertycache
    def _pathdirs(self):
        return set(util.finddirs(self._path))

    def visitdir(self, dir):
        if dir == self._path:
            return self._matcher.visitdir('')
        if dir.startswith(self._pathprefix):
            return self._matcher.visitdir(dir[len(self._pathprefix):])
        return dir in self._pathdirs

    def visitchildrenset(self, dir):
        if dir == self._path:
            return self._matcher.visitchildrenset('')
        if dir.startswith(self._pathprefix):
            return self._matcher.visitchildrenset(dir[len(self._pathprefix):])
        if dir in self._pathdirs:
            return 'this'
        return set()

    def isexact(self):

    def prefix(self):
        return self._matcher.prefix()

    @encoding.strmethod
    def __repr__(self):
        return ('<prefixdirmatcher path=%r, matcher=%r>'
                % (pycompat.bytestr(self._path), self._matcher))

class unionmatcher(basematcher):
    """A matcher that is the union of several matchers.

    The non-matching-attributes (bad, explicitdir, traversedir) are taken from

            return 'this'
        return r

    @encoding.strmethod
    def __repr__(self):
        return ('<unionmatcher matchers=%r>' % self._matchers)

def patkind(pattern, default=None):
    '''If pattern is 'kind:pat' with a known kind, return kind.

    >>> patkind(br're:.*\.c$')

    >>> patkind(b'main.py', default=b're')
    're'
    '''
    return _patsplit(pattern, default)[0]

def _patsplit(pattern, default):
    """Split a string into the optional pattern kind prefix and the actual
    pattern."""
    if ':' in pattern:
        kind, pat = pattern.split(':', 1)
        if kind in allpatternkinds:
            return kind, pat
    return default, pattern

def _globre(pat):
    r'''Convert an extended glob string to a regexp string.

    >>> from . import pycompat

    '''
    i, n = 0, len(pat)
    res = ''
    group = 0
    escape = util.stringutil.regexbytesescapemap.get
    def peek():
        return i < n and pat[i:i + 1]
    while i < n:
        c = pat[i:i + 1]
        i += 1
        if c not in '*?[{},\\':
            res += escape(c, c)
        elif c == '*':
            if peek() == '*':

                res += '[^/]*'
        elif c == '?':
            res += '.'
        elif c == '[':
            j = i
            if j < n and pat[j:j + 1] in '!]':
                j += 1
            while j < n and pat[j:j + 1] != ']':
                j += 1
            if j >= n:
                res += '\\['
            else:
                stuff = pat[i:j].replace('\\','\\\\')
                i = j + 1
                if stuff[0:1] == '!':
                    stuff = '^' + stuff[1:]
                elif stuff[0:1] == '^':
                    stuff = '\\' + stuff

                res += escape(c, c)
        else:
            res += escape(c, c)
    return res

def _regex(kind, pat, globsuffix):
    '''Convert a (normalized) pattern of any kind into a
    regular expression.
    globsuffix is appended to the regexp of globs.'''

    if rustmod is not None:
        try:
            return rustmod.build_single_regex(
                kind,
                pat,
                globsuffix
            )
        except rustmod.PatternError:
            raise error.ProgrammingError(
                'not a regex pattern: %s:%s' % (kind, pat)
            )

    if kind == 'relglob':
        globre = _globre(pat)
        if globre.startswith('[^/]*'):
            # When pat has the form *XYZ (common), make the returned regex more
            # legible by returning the regex for **XYZ instead of **/*XYZ.
            return '.*' + globre[len('[^/]*'):] + globsuffix
        return '(?:|.*/)' + globre + globsuffix
    if kind == 'relre':
        if pat.startswith('^'):
            return pat
        return '.*' + pat
    if kind in ('glob', 'rootglob'):
        return _globre(pat) + globsuffix
    raise error.ProgrammingError('not a regex pattern: %s:%s' % (kind, pat))

def _buildmatch(kindpats, globsuffix, root):
    '''Return regexp string and a matcher function for kindpats.
    globsuffix is appended to the regexp of globs.'''
    matchfuncs = []

    subincludes, kindpats = _expandsubinclude(kindpats, root)
    if subincludes:
        submatchers = {}
        def matchsubinclude(f):
            for prefix, matcherargs in subincludes:
                if f.startswith(prefix):
                    mf = submatchers.get(prefix)
                    if mf is None:
                        mf = match(*matcherargs)
                        submatchers[prefix] = mf

                    if mf(f[len(prefix):]):
                        return True
            return False
        matchfuncs.append(matchsubinclude)

    regex = ''
    if kindpats:
        if all(k == 'rootfilesin' for k, p, s in kindpats):
            dirs = {p for k, p, s in kindpats}
            def mf(f):
                i = f.rfind('/')
                if i >= 0:
                    dir = f[:i]
                else:
                    dir = '.'
                return dir in dirs
            regex = b'rootfilesin: %s' % stringutil.pprint(list(sorted(dirs)))
            matchfuncs.append(mf)
        else:
            regex, mf = _buildregexmatch(kindpats, globsuffix)
            matchfuncs.append(mf)

    if len(matchfuncs) == 1:
        return regex, matchfuncs[0]
    else:
        return regex, lambda f: any(mf(f) for mf in matchfuncs)

MAX_RE_SIZE = 20000

def _joinregexes(regexps):
    """gather multiple regular expressions into a single one"""
    return '|'.join(regexps)

def _buildregexmatch(kindpats, globsuffix):
    """Build a match function from a list of kinds and kindpats,
    return regexp string and a matcher function.

        for k, p, s in kindpats:
            try:
                _rematcher(_regex(k, p, globsuffix))
            except re.error:
                if s:
                    raise error.Abort(_("%s: invalid pattern (%s): %s") %
                                      (s, k, p))
                else:
                    raise error.Abort(_("invalid pattern (%s): %s") % (k, p))
        raise error.Abort(_("invalid pattern"))

def _patternrootsanddirs(kindpats):
    '''Returns roots and directories corresponding to each pattern.

    This calculates the roots and directories exactly matching the patterns and

    directories.
    '''
    r = []
    d = []
    for kind, pat, source in kindpats:
        if kind in ('glob', 'rootglob'): # find the non-glob prefix
            root = []
            for p in pat.split('/'):
                if '[' in p or '{' in p or '*' in p or '?' in p:
                    break
                root.append(p)

            r.append(pat)
        elif kind in ('rootfilesin',):
            if pat == '.':
                pat = ''
            d.append(pat)
        else: # relglob, re, relre
            r.append('')
    return r, d

def _roots(kindpats):
    '''Returns root directories to match recursively from the given patterns.'''
    roots, dirs = _patternrootsanddirs(kindpats)
    return roots

def _rootsdirsandparents(kindpats):
    '''Returns roots and exact directories from patterns.

    `roots` are directories to match recursively, `dirs` should

    # returning.
    # FIXME: all uses of this function do not need anything in 'roots' and
    # 'dirs' to also be in 'parents', consider removing them before returning.
    return r, d, p

def _explicitfiles(kindpats):
    '''Returns the potential explicit filenames from the patterns.

    >>> _explicitfiles([(b'path', b'foo/bar', b'')])
    ['foo/bar']

    # Keep only the pattern kinds where one can specify filenames (vs only
    # directory names).
    filable = [kp for kp in kindpats if kp[0] not in ('rootfilesin',)]
    return _roots(filable)

def _prefix(kindpats):
    '''Whether all the patterns match a prefix (i.e. recursively)'''
    for kind, pat, source in kindpats:
        if kind not in ('path', 'relpath'):
            return False
    return True

_commentre = None

def readpatternfile(filepath, warn, sourceinfo=False):
    '''parse a pattern file, returning a list of
    patterns. These patterns should be given to compile()
    to be validated and converted into a match function.

    This is useful to debug ignore patterns.
    '''

    if rustmod is not None:
        result, warnings = rustmod.read_pattern_file(
            filepath,
            bool(warn),
            sourceinfo,
        )

        for warning_params in warnings:
            # Can't be easily emitted from Rust, because it would require
            # a mechanism for both gettext and calling the `warn` function.

            if not _commentre:
                _commentre = util.re.compile(br'((?:^|[^\\])(?:\\\\)*)#.*')
            # remove comments prefixed by an even number of escapes
            m = _commentre.search(line)
            if m:
                line = line[:m.end(1)]
            # fixup properly escaped comments that survived the above
            line = line.replace("\\#", "#")
        line = line.rstrip()
        if not line:
            continue

            s = line[7:].strip()
            try:
                syntax = syntaxes[s]
            except KeyError:
                if warn:
                    warn(_("%s: ignoring invalid syntax '%s'\n") %
                         (filepath, s))
            continue

        linesyntax = syntax
        for s, rels in syntaxes.iteritems():
            if line.startswith(rels):
                linesyntax = rels
                line = line[len(rels):]
                break
            elif line.startswith(s+':'):
                linesyntax = rels
                line = line[len(s) + 1:]
                break
        if sourceinfo:
            patterns.append((linesyntax + line, lineno, line))
        else:
            patterns.append(linesyntax + line)

43076:2372284d9457

    pathutil,
    policy,
    pycompat,
    util,
)
from .utils import stringutil

rustmod = policy.importrust(r'filepatterns')

allpatternkinds = (
    're',
    'glob',
    'path',
    'relglob',
    'relpath',
    'relre',
    'rootglob',
    'listfile',
    'listfile0',
    'set',
    'include',
    'subinclude',
    'rootfilesin',
)
cwdrelativepatternkinds = ('relpath', 'glob')

propertycache = util.propertycache


def _rematcher(regex):
    '''compile the regexp with the best available regexp engine and return a
    matcher function'''
    m = util.re.compile(regex)

        # slightly faster, provided by facebook's re2 bindings
        return m.test_match
    except AttributeError:
        return m.match


def _expandsets(kindpats, ctx=None, listsubrepos=False, badfn=None):
    '''Returns the kindpats list with the 'set' patterns expanded to matchers'''
    matchers = []
    other = []

    for kind, pat, source in kindpats:
        if kind == 'set':
            if ctx is None:
                raise error.ProgrammingError(
                    "fileset expression with no " "context"
                )
            matchers.append(ctx.matchfileset(pat, badfn=badfn))

            if listsubrepos:
                for subpath in ctx.substate:
                    sm = ctx.sub(subpath).matchfileset(pat, badfn=badfn)

                    matchers.append(pm)

            continue
        other.append((kind, pat, source))
    return matchers, other


def _expandsubinclude(kindpats, root):
    '''Returns the list of subinclude matcher args and the kindpats without the
    subincludes in it.'''
    relmatchers = []

            relmatchers.append((prefix, matcherargs))
        else:
            other.append((kind, pat, source))

    return relmatchers, other


def _kindpatsalwaysmatch(kindpats):
    """"Checks whether the kindspats match everything, as e.g.
    'relpath:.' does.
    """
    for kind, pat, source in kindpats:
        if pat != '' or kind not in ['relpath', 'glob']:
            return False
    return True


def _buildkindpatsmatcher(
    matchercls, root, kindpats, ctx=None, listsubrepos=False, badfn=None
):
    matchers = []
    fms, kindpats = _expandsets(
        kindpats, ctx=ctx, listsubrepos=listsubrepos, badfn=badfn
    )
    if kindpats:
        m = matchercls(root, kindpats, badfn=badfn)
        matchers.append(m)
    if fms:
        matchers.extend(fms)

        return nevermatcher(badfn=badfn)
    if len(matchers) == 1:
        return matchers[0]
    return unionmatcher(matchers)


def match(
    root,
    cwd,
    patterns=None,
    include=None,
    exclude=None,
    default='glob',
    auditor=None,
    ctx=None,
    listsubrepos=False,
    warn=None,
    badfn=None,
    icasefs=False,
):
    r"""build an object to match a set of file patterns

    arguments:
    root - the canonical root of the tree you're matching against
    cwd - the current working directory, if relevant

    if patterns:
        kindpats = normalize(patterns, default, root, cwd, auditor, warn)
        if _kindpatsalwaysmatch(kindpats):
            m = alwaysmatcher(badfn)
        else:
            m = _buildkindpatsmatcher(
                patternmatcher,
                root,
                kindpats,
                ctx=ctx,
                listsubrepos=listsubrepos,
                badfn=badfn,
            )
    else:
        # It's a little strange that no patterns means to match everything.
        # Consider changing this to match nothing (probably using nevermatcher).
        m = alwaysmatcher(badfn)

    if include:
        kindpats = normalize(include, 'glob', root, cwd, auditor, warn)
        im = _buildkindpatsmatcher(
            includematcher,
            root,
            kindpats,
            ctx=ctx,
            listsubrepos=listsubrepos,
            badfn=None,
        )
        m = intersectmatchers(m, im)
    if exclude:
        kindpats = normalize(exclude, 'glob', root, cwd, auditor, warn)
        em = _buildkindpatsmatcher(
            includematcher,
            root,
            kindpats,
            ctx=ctx,
            listsubrepos=listsubrepos,
            badfn=None,
        )
        m = differencematcher(m, em)
    return m


def exact(files, badfn=None):
    return exactmatcher(files, badfn=badfn)


def always(badfn=None):
    return alwaysmatcher(badfn)


def never(badfn=None):
    return nevermatcher(badfn)


def badmatch(match, badfn):
    """Make a copy of the given matcher, replacing its bad method with the given
    one.
    """
    m = copy.copy(match)
    m.bad = badfn
    return m


def _donormalize(patterns, default, root, cwd, auditor=None, warn=None):
    '''Convert 'kind:pat' from the patterns list to tuples with kind and
    normalized and rooted patterns and with listfiles expanded.'''
    kindpats = []

                else:
                    files = files.splitlines()
                files = [f for f in files if f]
            except EnvironmentError:
                raise error.Abort(_("unable to read file list (%s)") % pat)
            for k, p, source in _donormalize(
                files, default, root, cwd, auditor, warn
            ):
                kindpats.append((k, p, pat))
            continue
        elif kind == 'include':
            try:
                fullpath = os.path.join(root, util.localpath(pat))
                includepats = readpatternfile(fullpath, warn)
                for k, p, source in _donormalize(
                    includepats, default, root, cwd, auditor, warn
                ):
                    kindpats.append((k, p, source or pat))
            except error.Abort as inst:
                raise error.Abort('%s: %s' % (pat, inst[0]))
            except IOError as inst:
                if warn:
                    warn(
                        _("skipping unreadable pattern file '%s': %s\n")
                        % (pat, stringutil.forcebytestr(inst.strerror))
                    )
            continue
        # else: re or relre - which cannot be normalized
        kindpats.append((kind, pat, ''))
    return kindpats


class basematcher(object):
    def __init__(self, badfn=None):
        if badfn is not None:
            self.bad = badfn

    def __call__(self, fn):
        return self.matchfn(fn)

    # Callbacks related to how the matcher is used by dirstate.walk.
    # Subscribers to these events must monkeypatch the matcher object.
    def bad(self, f, msg):
        '''Callback from dirstate.walk for each explicit file that can't be
        found/accessed, with an error message.'''

    def anypats(self):
        '''None of .always(), .isexact(), and .prefix() is true --
        optimizations will be difficult.'''
        return not self.always() and not self.isexact() and not self.prefix()


class alwaysmatcher(basematcher):
    '''Matches everything.'''

    def __init__(self, badfn=None):
        super(alwaysmatcher, self).__init__(badfn)

    def visitchildrenset(self, dir):
        return 'all'

    def __repr__(self):
        return r'<alwaysmatcher>'


class nevermatcher(basematcher):
    '''Matches nothing.'''

    def __init__(self, badfn=None):

        return set()

    def __repr__(self):
        return r'<nevermatcher>'


class predicatematcher(basematcher):
    """A matcher adapter for a simple boolean function"""

    def __init__(self, predfn, predrepr=None, badfn=None):
        super(predicatematcher, self).__init__(badfn)
        self.matchfn = predfn
        self._predrepr = predrepr

    @encoding.strmethod
    def __repr__(self):
        s = stringutil.buildrepr(self._predrepr) or pycompat.byterepr(
            self.matchfn
        )
        return '<predicatenmatcher pred=%s>' % s


def normalizerootdir(dir, funcname):
    if dir == '.':
        util.nouideprecwarn(
            "match.%s() no longer accepts " "'.', use '' instead." % funcname,
            '5.1',
        )
        return ''
    return dir


class patternmatcher(basematcher):

    def visitdir(self, dir):
        dir = normalizerootdir(dir, 'visitdir')
        if self._prefix and dir in self._fileset:
            return 'all'
        return (
            dir in self._fileset
            or dir in self._dirs
            or any(
                parentdir in self._fileset for parentdir in util.finddirs(dir)
            )
        )

    def visitchildrenset(self, dir):
        ret = self.visitdir(dir)
        if ret is True:
            return 'this'

    def prefix(self):
        return self._prefix

    @encoding.strmethod
    def __repr__(self):
        return '<patternmatcher patterns=%r>' % pycompat.bytestr(self._pats)


# This is basically a reimplementation of util.dirs that stores the children
# instead of just a count of them, plus a small optional optimization to avoid
# some directories we don't need.
class _dirchildren(object):

        # Unlike manifest._splittopdir, this does not suffix `dirname` with a
        # slash.
        oldpos = len(path)
        pos = path.rfind('/')
        while pos != -1:
            yield path[:pos], path[pos + 1 : oldpos]
            oldpos = pos
            pos = path.rfind('/', 0, pos)
        yield '', path[:oldpos]

    def get(self, path):
        return self._dirs.get(path, set())


class includematcher(basematcher):
    def __init__(self, root, kindpats, badfn=None):
        super(includematcher, self).__init__(badfn)

        self._pats, self.matchfn = _buildmatch(kindpats, '(?:/|$)', root)
        self._prefix = _prefix(kindpats)

    def visitdir(self, dir):
        dir = normalizerootdir(dir, 'visitdir')
        if self._prefix and dir in self._roots:
            return 'all'
        return (
            dir in self._roots
            or dir in self._dirs
            or dir in self._parents
            or any(parentdir in self._roots for parentdir in util.finddirs(dir))
        )

    @propertycache
    def _allparentschildren(self):
        # It may seem odd that we add dirs, roots, and parents, and then
        # restrict to only parents. This is to catch the case of:
        #   dirs = ['foo/bar']
        #   parents = ['foo']
        # if we asked for the children of 'foo', but had only added
        # self._parents, we wouldn't be able to respond ['bar'].
        return _dirchildren(
            itertools.chain(self._dirs, self._roots, self._parents),
            onlyinclude=self._parents,
        )

    def visitchildrenset(self, dir):
        if self._prefix and dir in self._roots:
            return 'all'
        # Note: this does *not* include the 'dir in self._parents' case from
        # visitdir, that's handled below.
        if (
            '' in self._roots
            or dir in self._roots
            or dir in self._dirs
            or any(parentdir in self._roots for parentdir in util.finddirs(dir))
        ):
            return 'this'

        if dir in self._parents:
            return self._allparentschildren.get(dir) or set()
        return set()

    @encoding.strmethod
    def __repr__(self):
        return '<includematcher includes=%r>' % pycompat.bytestr(self._pats)


class exactmatcher(basematcher):
    r'''Matches the input files exactly. They are interpreted as paths, not
    patterns (so no kind-prefixes).

            return set()

        candidates = self._fileset | self._dirs - {''}
        if dir != '':
            d = dir + '/'
            candidates = set(c[len(d) :] for c in candidates if c.startswith(d))
        # self._dirs includes all of the directories, recursively, so if
        # we're attempting to match foo/bar/baz.txt, it'll have '', 'foo',
        # 'foo/bar' in it. Thus we can safely ignore a candidate that has a
        # '/' in it, indicating a it's for a subdir-of-a-subdir; the
        # immediate subdir will be in there without a slash.

    def isexact(self):
        return True

    @encoding.strmethod
    def __repr__(self):
        return '<exactmatcher files=%r>' % self._files


class differencematcher(basematcher):
    '''Composes two matchers by matching if the first matches and the second
    does not.

    The second matcher's non-matching-attributes (bad, explicitdir,
    traversedir) are ignored.
    '''

    def __init__(self, m1, m2):
        super(differencematcher, self).__init__()
        self._m1 = m1
        self._m2 = m2
        self.bad = m1.bad

    def isexact(self):
        return self._m1.isexact()

    @encoding.strmethod
    def __repr__(self):
        return '<differencematcher m1=%r, m2=%r>' % (self._m1, self._m2)


def intersectmatchers(m1, m2):
    '''Composes two matchers by matching if both of them match.

    The second matcher's non-matching-attributes (bad, explicitdir,

    if m2.always():
        m = copy.copy(m1)
        return m
    return intersectionmatcher(m1, m2)


class intersectionmatcher(basematcher):
    def __init__(self, m1, m2):
        super(intersectionmatcher, self).__init__()
        self._m1 = m1
        self._m2 = m2

    def isexact(self):
        return self._m1.isexact() or self._m2.isexact()

    @encoding.strmethod
    def __repr__(self):
        return '<intersectionmatcher m1=%r, m2=%r>' % (self._m1, self._m2)


class subdirmatcher(basematcher):
    """Adapt a matcher to work on a subdirectory only.

    The paths are remapped to remove/insert the path as needed:

        super(subdirmatcher, self).__init__()
        self._path = path
        self._matcher = matcher
        self._always = matcher.always()

        self._files = [
            f[len(path) + 1 :]
            for f in matcher._files
            if f.startswith(path + "/")
        ]

        # If the parent repo had a path to this subrepo and the matcher is
        # a prefix matcher, this submatcher always matches.
        if matcher.prefix():
            self._always = any(f == path for f in matcher._files)

    def prefix(self):
        return self._matcher.prefix() and not self._always

    @encoding.strmethod
    def __repr__(self):
        return '<subdirmatcher path=%r, matcher=%r>' % (
            self._path,
            self._matcher,
        )


class prefixdirmatcher(basematcher):
    """Adapt a matcher to work on a parent directory.

    The matcher's non-matching-attributes (bad, explicitdir, traversedir) are

        return [self._pathprefix + f for f in self._matcher._files]

    def matchfn(self, f):
        if not f.startswith(self._pathprefix):
            return False
        return self._matcher.matchfn(f[len(self._pathprefix) :])

    @propertycache
    def _pathdirs(self):
        return set(util.finddirs(self._path))

    def visitdir(self, dir):
        if dir == self._path:
            return self._matcher.visitdir('')
        if dir.startswith(self._pathprefix):
            return self._matcher.visitdir(dir[len(self._pathprefix) :])
        return dir in self._pathdirs

    def visitchildrenset(self, dir):
        if dir == self._path:
            return self._matcher.visitchildrenset('')
        if dir.startswith(self._pathprefix):
            return self._matcher.visitchildrenset(dir[len(self._pathprefix) :])
        if dir in self._pathdirs:
            return 'this'
        return set()

    def isexact(self):

    def prefix(self):
        return self._matcher.prefix()

    @encoding.strmethod
    def __repr__(self):
        return '<prefixdirmatcher path=%r, matcher=%r>' % (
            pycompat.bytestr(self._path),
            self._matcher,
        )


class unionmatcher(basematcher):
    """A matcher that is the union of several matchers.

    The non-matching-attributes (bad, explicitdir, traversedir) are taken from

            return 'this'
        return r

    @encoding.strmethod
    def __repr__(self):
        return '<unionmatcher matchers=%r>' % self._matchers


def patkind(pattern, default=None):
    '''If pattern is 'kind:pat' with a known kind, return kind.

    >>> patkind(br're:.*\.c$')

    >>> patkind(b'main.py', default=b're')
    're'
    '''
    return _patsplit(pattern, default)[0]


def _patsplit(pattern, default):
    """Split a string into the optional pattern kind prefix and the actual
    pattern."""
    if ':' in pattern:
        kind, pat = pattern.split(':', 1)
        if kind in allpatternkinds:
            return kind, pat
    return default, pattern


def _globre(pat):
    r'''Convert an extended glob string to a regexp string.

    >>> from . import pycompat

    '''
    i, n = 0, len(pat)
    res = ''
    group = 0
    escape = util.stringutil.regexbytesescapemap.get

    def peek():
        return i < n and pat[i : i + 1]

    while i < n:
        c = pat[i : i + 1]
        i += 1
        if c not in '*?[{},\\':
            res += escape(c, c)
        elif c == '*':
            if peek() == '*':

                res += '[^/]*'
        elif c == '?':
            res += '.'
        elif c == '[':
            j = i
            if j < n and pat[j : j + 1] in '!]':
                j += 1
            while j < n and pat[j : j + 1] != ']':
                j += 1
            if j >= n:
                res += '\\['
            else:
                stuff = pat[i:j].replace('\\', '\\\\')
                i = j + 1
                if stuff[0:1] == '!':
                    stuff = '^' + stuff[1:]
                elif stuff[0:1] == '^':
                    stuff = '\\' + stuff

                res += escape(c, c)
        else:
            res += escape(c, c)
    return res


def _regex(kind, pat, globsuffix):
    '''Convert a (normalized) pattern of any kind into a
    regular expression.
    globsuffix is appended to the regexp of globs.'''

    if rustmod is not None:
        try:
            return rustmod.build_single_regex(kind, pat, globsuffix)
        except rustmod.PatternError:
            raise error.ProgrammingError(
                'not a regex pattern: %s:%s' % (kind, pat)
            )

    if kind == 'relglob':
        globre = _globre(pat)
        if globre.startswith('[^/]*'):
            # When pat has the form *XYZ (common), make the returned regex more
            # legible by returning the regex for **XYZ instead of **/*XYZ.
            return '.*' + globre[len('[^/]*') :] + globsuffix
        return '(?:|.*/)' + globre + globsuffix
    if kind == 'relre':
        if pat.startswith('^'):
            return pat
        return '.*' + pat
    if kind in ('glob', 'rootglob'):
        return _globre(pat) + globsuffix
    raise error.ProgrammingError('not a regex pattern: %s:%s' % (kind, pat))


def _buildmatch(kindpats, globsuffix, root):
    '''Return regexp string and a matcher function for kindpats.
    globsuffix is appended to the regexp of globs.'''
    matchfuncs = []

    subincludes, kindpats = _expandsubinclude(kindpats, root)
    if subincludes:
        submatchers = {}

        def matchsubinclude(f):
            for prefix, matcherargs in subincludes:
                if f.startswith(prefix):
                    mf = submatchers.get(prefix)
                    if mf is None:
                        mf = match(*matcherargs)
                        submatchers[prefix] = mf

                    if mf(f[len(prefix) :]):
                        return True
            return False

        matchfuncs.append(matchsubinclude)

    regex = ''
    if kindpats:
        if all(k == 'rootfilesin' for k, p, s in kindpats):
            dirs = {p for k, p, s in kindpats}

            def mf(f):
                i = f.rfind('/')
                if i >= 0:
                    dir = f[:i]
                else:
                    dir = '.'
                return dir in dirs

            regex = b'rootfilesin: %s' % stringutil.pprint(list(sorted(dirs)))
            matchfuncs.append(mf)
        else:
            regex, mf = _buildregexmatch(kindpats, globsuffix)
            matchfuncs.append(mf)

    if len(matchfuncs) == 1:
        return regex, matchfuncs[0]
    else:
        return regex, lambda f: any(mf(f) for mf in matchfuncs)


MAX_RE_SIZE = 20000


def _joinregexes(regexps):
    """gather multiple regular expressions into a single one"""
    return '|'.join(regexps)


def _buildregexmatch(kindpats, globsuffix):
    """Build a match function from a list of kinds and kindpats,
    return regexp string and a matcher function.

        for k, p, s in kindpats:
            try:
                _rematcher(_regex(k, p, globsuffix))
            except re.error:
                if s:
                    raise error.Abort(
                        _("%s: invalid pattern (%s): %s") % (s, k, p)
                    )
                else:
                    raise error.Abort(_("invalid pattern (%s): %s") % (k, p))
        raise error.Abort(_("invalid pattern"))


def _patternrootsanddirs(kindpats):
    '''Returns roots and directories corresponding to each pattern.

    This calculates the roots and directories exactly matching the patterns and

    directories.
    '''
    r = []
    d = []
    for kind, pat, source in kindpats:
        if kind in ('glob', 'rootglob'):  # find the non-glob prefix
            root = []
            for p in pat.split('/'):
                if '[' in p or '{' in p or '*' in p or '?' in p:
                    break
                root.append(p)

            r.append(pat)
        elif kind in ('rootfilesin',):
            if pat == '.':
                pat = ''
            d.append(pat)
        else:  # relglob, re, relre
            r.append('')
    return r, d


def _roots(kindpats):
    '''Returns root directories to match recursively from the given patterns.'''
    roots, dirs = _patternrootsanddirs(kindpats)
    return roots


def _rootsdirsandparents(kindpats):
    '''Returns roots and exact directories from patterns.

    `roots` are directories to match recursively, `dirs` should

    # returning.
    # FIXME: all uses of this function do not need anything in 'roots' and
    # 'dirs' to also be in 'parents', consider removing them before returning.
    return r, d, p


def _explicitfiles(kindpats):
    '''Returns the potential explicit filenames from the patterns.

    >>> _explicitfiles([(b'path', b'foo/bar', b'')])
    ['foo/bar']

    # Keep only the pattern kinds where one can specify filenames (vs only
    # directory names).
    filable = [kp for kp in kindpats if kp[0] not in ('rootfilesin',)]
    return _roots(filable)


def _prefix(kindpats):
    '''Whether all the patterns match a prefix (i.e. recursively)'''
    for kind, pat, source in kindpats:
        if kind not in ('path', 'relpath'):
            return False
    return True


_commentre = None


def readpatternfile(filepath, warn, sourceinfo=False):
    '''parse a pattern file, returning a list of
    patterns. These patterns should be given to compile()
    to be validated and converted into a match function.

    This is useful to debug ignore patterns.
    '''

    if rustmod is not None:
        result, warnings = rustmod.read_pattern_file(
            filepath, bool(warn), sourceinfo,
        )

        for warning_params in warnings:
            # Can't be easily emitted from Rust, because it would require
            # a mechanism for both gettext and calling the `warn` function.

            if not _commentre:
                _commentre = util.re.compile(br'((?:^|[^\\])(?:\\\\)*)#.*')
            # remove comments prefixed by an even number of escapes
            m = _commentre.search(line)
            if m:
                line = line[: m.end(1)]
            # fixup properly escaped comments that survived the above
            line = line.replace("\\#", "#")
        line = line.rstrip()
        if not line:
            continue

            s = line[7:].strip()
            try:
                syntax = syntaxes[s]
            except KeyError:
                if warn:
                    warn(
                        _("%s: ignoring invalid syntax '%s'\n") % (filepath, s)
                    )
            continue

        linesyntax = syntax
        for s, rels in syntaxes.iteritems():
            if line.startswith(rels):
                linesyntax = rels
                line = line[len(rels) :]
                break
            elif line.startswith(s + ':'):
                linesyntax = rels
                line = line[len(s) + 1 :]
                break
        if sourceinfo:
            patterns.append((linesyntax + line, lineno, line))
        else:
            patterns.append(linesyntax + line)