Git: .gitignore with ** and ignored directories

Handle the two rules that surprise most people: **, and files inside ignored directories.

What to build

A program that decides whether paths are ignored, including ** patterns and Git's rule about ignored directories.

Requirements

  • All rules of the previous exercise apply, plus: **/ at the start matches any leading folders (including none); /** at the end matches everything inside; /**/ in the middle matches zero or more folders; a pattern containing ** is anchored like one with a slash.
  • A path is ignored if any of its folders is ignored (checked from the top, treating each folder as a directory path), or else if the last pattern matching the file is not negated. Print ignored PATH or kept PATH.

Input

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

Output

n lines.

Constraints

p, n ≤ 100.

Example

Input:

2
logs/
!logs/keep.txt
2
logs/a.txt
logs/keep.txt

Output:

ignored logs/a.txt
ignored logs/keep.txt

Why it works

Git stops looking inside a directory once it is ignored, so a later ! cannot bring back a file inside it, while ** lets one pattern reach any depth.

Examples

Example 1 · Input
2
logs/
!logs/keep.txt
2
logs/a.txt
logs/keep.txt
Expected output
ignored logs/a.txt
ignored logs/keep.txt
Example 2 · Input
2
**/cache
docs/**
4
cache
lib/cache
src/cache/x.bin
docs/a/b.md
Expected output
ignored cache
ignored lib/cache
ignored src/cache/x.bin
ignored docs/a/b.md

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

Hints

Hint 1

Check the folders of a path from the top: if a folder is ignored (by the last pattern matching it as a directory), everything inside is ignored, whatever later patterns say.

Hint 2

For `**`: a leading `**/` matches in any folder, a trailing `/**` matches everything inside, and `/**/` matches zero or more folders.

Solution

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


def to_regex(pattern):
    out, i = "", 0
    while i < len(pattern):
        if pattern.startswith("**/", i):
            out += "(?:.*/)?"
            i += 3
        elif pattern.startswith("/**", i) and i + 3 == len(pattern):
            out += "/.*"
            i += 3
        elif pattern.startswith("**", i):
            out += ".*"
            i += 2
        elif pattern[i] == "*":
            out += "[^/]*"
            i += 1
        elif pattern[i] == "?":
            out += "[^/]"
            i += 1
        else:
            out += re.escape(pattern[i])
            i += 1
    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 or "**" in line
    rules.append((negate, directory_only, anchored, to_regex(line.lstrip("/"))))


def decide(path, is_directory):
    name = path.split("/")[-1]
    result = None
    for negate, directory_only, anchored, regex in rules:
        if directory_only and not is_directory:
            continue
        if regex.match(path if anchored else name):
            result = not negate
    return bool(result)


for _ in range(int(input())):
    path = input().strip()
    parts = path.split("/")
    ignored = any(decide("/".join(parts[: i + 1]), True) for i in range(len(parts) - 1))
    if not ignored:
        ignored = decide(path, False)
    print(("ignored " if ignored else "kept ") + path)

Lesson: .gitignore and GitHub Actions →