Git: Is this path ignored?

Implement the core rules of .gitignore.

What to build

A program that decides whether paths are ignored by a list of .gitignore patterns.

Requirements

  • Rules: skip blank lines and # comments; ! negates; a trailing / matches only directories (the folders in a path); a pattern containing a slash elsewhere is anchored: matched against the path's leading folders and the path itself, from the root (a leading / is removed first); otherwise the pattern is matched against each folder name and the file name. * matches any characters except /, ? one character except /. A path is ignored if the last pattern that matches it is not negated.
  • Print ignored PATH or kept PATH for each path.

Input

Line 1: p. Then p pattern lines. Then n and n file paths.

Output

n lines.

Constraints

p, n ≤ 100; no ** in patterns.

Example

Input:

3
*.log
!keep.log
build/
5
app.log
keep.log
logs/old.log
src/build/out.o
build.py

Output:

ignored app.log
kept keep.log
ignored logs/old.log
ignored src/build/out.o
kept build.py

Why it works

Checking every pattern in order and remembering the last match reproduces how Git lets later lines override earlier ones.

Examples

Example 1 · Input
3
*.log
!keep.log
build/
5
app.log
keep.log
logs/old.log
src/build/out.o
build.py
Expected output
ignored app.log
kept keep.log
ignored logs/old.log
ignored src/build/out.o
kept build.py
Example 2 · Input
3
# secrets
/secret.txt
docs/*.tmp
4
secret.txt
src/secret.txt
docs/a.tmp
docs/deep/b.tmp
Expected output
ignored secret.txt
kept src/secret.txt
ignored docs/a.tmp
kept docs/deep/b.tmp

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

A pattern without a slash (apart from a trailing one) is compared with every part of the path; a pattern with a slash is compared with the path from the root.

Hint 2

A trailing slash means the pattern only matches directories, so only the path's folders count; the last matching pattern decides.

Solution

Show one correct solution (try it yourself first)
import re


def to_regex(pattern):
    out = ""
    for ch in pattern:
        out += "[^/]*" if ch == "*" else "[^/]" if ch == "?" else re.escape(ch)
    return re.compile(out + r"\Z")


rules = []
for _ in range(int(input())):
    line = input().strip()
    if not line or line.startswith("#"):
        continue
    negate = line.startswith("!")
    line = line[1:] if negate else line
    directory_only = line.endswith("/")
    line = line.rstrip("/")
    anchored = "/" in line
    rules.append((negate, directory_only, anchored, to_regex(line.lstrip("/"))))


def matches(rule, path):
    _, directory_only, anchored, regex = rule
    parts = path.split("/")
    candidates = ["/".join(parts[: i + 1]) for i in range(len(parts))] if anchored else parts
    if directory_only:
        candidates = candidates[:-1]
    return any(regex.match(c) for c in candidates)


for _ in range(int(input())):
    path = input().strip()
    ignored = False
    for rule in rules:
        if matches(rule, path):
            ignored = not rule[0]
    print(("ignored " if ignored else "kept ") + path)

Lesson: .gitignore and GitHub Actions →