Re: [PATCH RFC v3 2/2] Move libgit.a sources into separate "lib/" directory

On Thu, Aug 13, 2026 at 12:04 PM Michael Montalbo <[email protected]> wrote:
>
> One mechanical signal is how tightly a set of files shares the same
> internal headers: if two .c files include many of the same project
> headers (dropping the plumbing everything includes), they lean on the
> same machinery. Averaged over every pair in the group, that gives one
> cohesion number.
>

I spent some time trying to think about a stronger approach. I think the
following script[2] is a more promising approach to criticize:

- Read the Makefile. Collect the C files that it compiles into the git
  library. The count is 231.
- Read every non-merge commit in the history, up to HEAD. For each
  one, take its area name (the subject prefix, such as "diff:" or
  "refs:") and the library files it changed.
- Give each commit a weight of one divided by the number of library
  files it changed. A commit that changed two files counts more than a
  commit that changed forty.
- For each file, take the area name with the largest total weight. If
  that weight is small, the file has no area name.
- Read a 14-line table that groups area names into directories. Put
  each file into the directory for its area name, or, if it has none,
  the directory for its filename. A file that matches no directory
  stays ungrouped.
- Build a call graph with cscope, a cross-reference database that
  records which file uses functions defined in another file[1]. This is
  based on the code, not on file or commit names, so it is a second
  check independent of the first.
- Print each directory with its files, then the ungrouped files. Last,
  compare the call groups with the directories and show the groups
  that fall across more than one directory. Those mark the boundary
  files to check.

The 14-entry table that maps area names to directories is the
CHARTER block in the script below. Its output:

git library source files by directory  (HEAD c0c95f3229; 231 files)

odb/   21 files  (21 by commit label)
   blob commit fsck hash loose match-trees object object-file
   object-file-convert object-name odb oid-array oidmap oidset oidtree
   replace-object sha1dc_git tag tmp-objdir tree tree-walk

refs/   8 files  (7 by commit label)
   ls-refs pack-refs ref-filter reflog reflog-walk refs refspec
   worktree

pack/   27 files  (18 by commit label)
   bloom chunk-format commit-graph delta-islands diff-delta midx
   midx-write pack-bitmap pack-bitmap-write pack-check pack-mtimes
   pack-objects pack-revindex pack-write packfile packfile-list
   patch-delta prune-packed pseudo-merge reachable repack repack-cruft
   repack-filtered repack-geometry repack-midx repack-promisor
   server-info

diff/   16 files  (14 by commit label)
   combine-diff diff diff-lib diff-merges diff-no-index diffcore-break
   diffcore-delta diffcore-order diffcore-pickaxe diffcore-rename
   diffcore-rotate patch-ids range-diff tree-diff userdiff
   xdiff-interface

merge/   7 files  (7 by commit label)
   fmt-merge-msg merge merge-blobs merge-ll merge-ort
   merge-ort-wrappers rerere

revision/   14 files  (12 by commit label)
   bisect blame commit-reach decorate graph line-log line-range
   list-objects list-objects-filter list-objects-filter-options
   log-tree pretty revision shallow

index/   19 files  (18 by commit label)
   cache-tree checkout dir entry fsmonitor fsmonitor-ipc
   fsmonitor-settings name-hash parallel-checkout pathspec
   preload-index read-cache resolve-undo sparse-index split-index
   statinfo symlinks unpack-trees wt-status

setup/   9 files  (9 by commit label)
   alias config environment hook ident repo-settings repository setup
   version

convert/   3 files  (3 by commit label)
   attr convert ws

transport/   19 files  (17 by commit label)
   bundle bundle-uri connect connected fetch-negotiator
   fetch-object-info fetch-pack pkt-line promisor-remote protocol
   protocol-caps remote send-pack serve sideband transport
   transport-helper upload-pack walker

notes/   4 files  (3 by commit label)
   notes notes-cache notes-merge notes-utils

submodule/   2 files  (2 by commit label)
   submodule submodule-config

archive/   3 files  (3 by commit label)
   archive archive-tar archive-zip

sequencer/   11 files  (11 by commit label)
   add-interactive add-patch apply branch mailinfo mailmap rebase
   rebase-interactive replay reset sequencer

placed 163 files in 14 directories: 145 by commit label,
12 by filename, 6 by override. The table is 14 lines.

68 files match no subsystem and are left ungrouped:
   abspath advice alloc base85 cbtree chdir-notify color column
   common-exit common-init copy credential csum-file ctype date
   diagnose dir-iterator editor exec-cmd gettext git-zlib
   gpg-interface grep hash-lookup hashmap help hex hex-ll json-writer
   kwset levenshtein linear-assignment lockfile mem-pool pager parse
   parse-options parse-options-cb path path-walk prio-queue progress
   prompt quote run-command sigchain stable-qsort strbuf string-list
   strmap strvec sub-process tempfile thread-utils trace trace2
   trailer unix-socket unix-stream-server url urlmatch usage utf8
   varint versioncmp wildmatch wrapper write-or-die

[1] Detail: the call-graph check and the label-vs-filename comparison:

Second check. The call graph records which file uses functions from
another file, so it does not use names. Group the files that call each
other, then compare each group with the directories above. 57 files
fall into 12 call groups. The 12 sort into three kinds:
  5 groups: all placed files land in one directory (call graph agrees).
  6 groups: most files in one directory, plus one or two
     from another (the boundary cases to check).
  1 group: shared helpers that many files call (not shown).

Boundary groups, largest directory first. Each line is one
directory and its files in the group. Example: shallow is in
revision, but the call graph groups it with the transport files.

  transport (5): connect fetch-pack pkt-line send-pack upload-pack
  revision (1): shallow

  transport (3): remote transport transport-helper
  refs (1): refspec

  odb (2): hash object-file
  pack (1): pack-write

  pack (2): chunk-format commit-graph
  revision (2): commit-reach revision
  odb (1): commit

  sequencer (2): add-interactive add-patch
  index (1): wt-status

  setup (2): config setup
  refs (1): worktree

Commit label vs filename: both point to the same directory for 151 files
and disagree for 0 (the 8 overrides are separate). The commit
label and the filename follow the same naming rule, so the label
confirms the naming, not the grouping. Only the call graph is an
independent check.

[2] The script:

#!/usr/bin/env python3
"""subsystems.py: group git's libgit.a source files into directories.

Steps:
  membership : the Makefile lists the library source files (LIB_OBJS).
  label      : each file's directory is the area name used most often
               in its commit messages, weighted toward small commits.
  table      : 14 lines say which area names share a directory.
  check      : the call graph is a second, independent signal; it
               lists the files where the two signals disagree.

Run from a git.git checkout (uses HEAD).
"""
import re
import os
import shutil
import tempfile
import subprocess
import math
import textwrap
from collections import defaultdict, Counter

TOP = subprocess.check_output(
    ["git", "rev-parse", "--show-toplevel"], text=True).strip()
HEAD = subprocess.check_output(
    ["git", "-C", TOP, "rev-parse", "--short", "HEAD"],
    text=True).strip()


def git(*a):
    return subprocess.run(["git", "-C", TOP, *a],
                          capture_output=True, text=True).stdout


# membership: exactly what libgit.a archives (authoritative)
LIB = set()
for line in open(TOP + "/Makefile"):
    m = re.match(r"LIB_OBJS \+= ([\w-]+)\.o$", line.strip())
    if m and "/" not in m.group(1):
        LIB.add(m.group(1) + ".c")

# charter: the only hand input, which fine areas share a directory
CHARTER = {
    "odb": "object odb oid oidmap oidset oidtree loose blob tag "
           "commit tree replace match tmp fsck hash sha1dc",
    "refs": "refs refspec reflog ref ls worktree",
    "pack": "pack packfile midx delta prune reachable server bloom "
            "chunk pseudo repack",
    "diff": "diff diffcore combine range userdiff xdiff patch pickaxe",
    "merge": "merge rerere fmt",
    "revision": "revision log bisect shallow blame line graph "
                "decorate list pretty",
    "index": "read cache split sparse unpack name preload resolve "
             "statinfo entry parallel dir pathspec checkout symlinks "
             "fsmonitor wt",
    "setup": "config setup environment repository repo ident alias "
             "version hook",
    "convert": "attr convert ws whitespace",
    "transport": "transport remote connect connected send fetch "
                 "upload walker http protocol serve pkt sideband "
                 "bundle promisor",
    "notes": "notes", "submodule": "submodule", "archive": "archive",
    "sequencer": "sequencer rebase replay apply add reset branch "
                 "mailinfo mailmap",
}
OWNER = {t: s for s, toks in CHARTER.items() for t in toks.split()}
# per-file exceptions where the name or label points at the wrong dir
OVERRIDE = {"pack-refs.c": "refs", "commit-graph.c": "pack",
            "commit-reach.c": "revision", "tree-diff.c": "diff",
            "diff-delta.c": "pack", "patch-delta.c": "pack",
            "dir-iterator.c": "lib", "hash-lookup.c": "lib"}


def to_dir(token):
    return OWNER.get(token)


# signal A: focus-weighted modal commit "area:" label
# No noise list. A sweep label such as treewide or global appears only
# on commits that change many files. Small commit weight keeps those
# commits low, so a sweep label is never a file's top label; 0 seen.
PRE = re.compile(r"^([A-Za-z0-9][\w./-]*):")


def norm(p):
    p = p.lower()
    return p[:-2] if p.endswith((".c", ".h")) else p


# One pass over the log. A commit touching k libgit.a files adds 1/k to
# each file's tally for that commit's area label, so a 2-file commit is
# stronger evidence than a 40-file sweep. (History before a rename is
# under the old name; a --follow pass is a known refinement.)
commits = []
lab, files = None, []
log = git("log", "--no-merges", "--name-only", "--format=%x00%s")
for line in log.split("\n"):
    if line.startswith("\x00"):
        if lab and files:
            commits.append((lab, files))
        m = PRE.match(line[1:])
        lab = norm(m.group(1)) if m else None
        files = []
    elif line.endswith(".c") and "/" not in line and line in LIB:
        files.append(line)
if lab and files:
    commits.append((lab, files))

wt = defaultdict(lambda: defaultdict(float))
for lab, files in commits:
    w = 1.0 / len(files)
    for f in set(files):
        wt[f][lab] += w


def modal(f):
    """The top focus-weighted label, or None if history is thin."""
    c = wt.get(f)
    if not c:
        return None
    l, w = max(c.items(), key=lambda kv: (kv[1], kv[0]))  # tie: name
    tot = sum(c.values())
    if tot < 2.0 or w / tot < 0.34:   # <2 commits, or under 34%
        return None
    return l


def place(f):
    """(dir, how) for a file, or (None, ...) if it joins no subsystem.
    Precedence: override, commit label, filename."""
    if f in OVERRIDE:
        d = OVERRIDE[f]
        return (None if d == "lib" else d), "override"
    lab = modal(f)
    if lab:
        d = to_dir(lab.split("/")[0].split("-")[0])
        if d:
            return d, "label"
    d = to_dir(f[:-2].split("-")[0])     # fallback: filename token
    if d:
        return d, "name"
    return None, "ungrouped"


# signal B: the call graph. cscope, a cross-reference database, gives
# the call edges, so calls in comments, strings, and macros are not
# counted. The coding style gives the definitions: a column-0 line that
# names a function defines it; it is exported if it lacks "static".
CTRL = {"if", "for", "while", "switch", "return", "sizeof", "do",
        "else", "case", "typedef", "struct", "union", "enum", "extern",
        "static"}
text = {f: open(TOP + "/" + f, encoding="utf-8",
                errors="replace").read() for f in LIB}


def scan_defs(t):
    """(exported, all) function names a file defines at column 0."""
    exported, everything = set(), set()
    for ln in t.split("\n"):
        if not ln or ln[0] in " \t#}/*{)":
            continue
        if ("(" not in ln or ln.rstrip().endswith(";")
                or "=" in ln.split("(")[0]):
            continue
        m = re.match(r"^(static\b)?.*?([A-Za-z_]\w*)\s*\(", ln)
        if not m or m.group(2) in CTRL:
            continue
        everything.add(m.group(2))
        if not m.group(1):
            exported.add(m.group(2))
    return exported, everything


owner_fn, dup, allnames = {}, set(), set()
for f in LIB:
    exported, everything = scan_defs(text[f])
    allnames |= everything
    for name in exported:
        if name in owner_fn:
            dup.add(name)
        owner_fn[name] = f
for name in dup:
    owner_fn.pop(name, None)


def cscope_calls():
    """calls[a][b] = call sites in root .c file a that call a non-static
    function defined in root .c file b, using cscope. cscope type 2
    lists, per queried function, the functions it calls, one line per
    call site as 'caller_file callee_name line text'. The caller file
    and callee name are on each line, so no bookkeeping is needed."""
    if not shutil.which("cscope"):
        raise SystemExit("cscope not found on PATH; run under "
                         "'nix-shell -p cscope'.")
    tmp = tempfile.mkdtemp(prefix="subsys-cs-")
    try:
        flist = os.path.join(tmp, "files")
        out = os.path.join(tmp, "cscope.out")
        with open(flist, "w") as fh:
            fh.write("\n".join(sorted(LIB)) + "\n")
        subprocess.run(
            ["cscope", "-b", "-q", "-k", "-i", flist, "-f", out],
            cwd=TOP, check=True, stdout=subprocess.DEVNULL,
            stderr=subprocess.DEVNULL)
        query = "".join(f"2{n}\n" for n in sorted(allnames))
        res = subprocess.run(
            ["cscope", "-d", "-l", "-f", out], cwd=TOP, input=query,
            capture_output=True, text=True).stdout
    finally:
        shutil.rmtree(tmp, ignore_errors=True)
    calls = defaultdict(lambda: defaultdict(int))
    for line in res.split("\n"):
        if not line or line.startswith(">>"):   # blank or prompt line
            continue
        parts = line.split(" ", 3)   # caller_file callee line text
        if len(parts) < 4 or not parts[2].isdigit():
            continue   # marker or malformed line
        caller, callee = parts[0], parts[1]
        cf = owner_fn.get(callee)
        if caller in LIB and cf and cf != caller:
            calls[caller][cf] += 1
    return calls


calls = cscope_calls()
fanin = defaultdict(set)
for a in calls:
    for b in calls[a]:
        fanin[b].add(a)
N = len(LIB)
idf = {b: math.log(N / len(s)) for b, s in fanin.items()}
aff = defaultdict(dict)
for a in calls:
    for b in calls[a]:
        w = (calls[a].get(b, 0) * idf.get(b, 0)
             + calls.get(b, {}).get(a, 0) * idf.get(a, 0))
        if w > 0:
            aff[a][b] = aff[b][a] = w
idx = {f: i for i, f in enumerate(sorted(LIB))}
mem = {i: [f] for f, i in idx.items()}
size = {i: 1 for i in mem}
link = defaultdict(dict)
for a in aff:
    for b, w in aff[a].items():
        if idx[a] < idx[b]:
            link[idx[a]][idx[b]] = link[idx[b]][idx[a]] = w
act, nid = set(mem), len(LIB)
while True:
    best, bv = None, 15.0
    for i in act:
        for j, w in link[i].items():
            if i < j and w / (size[i] * size[j]) >= bv:
                bv, best = w / (size[i] * size[j]), (i, j)
    if not best:
        break
    i, j = best
    c = nid
    nid += 1
    mem[c], size[c] = mem[i] + mem[j], size[i] + size[j]
    for x in (set(link[i]) | set(link[j])) - {i, j}:
        link[c][x] = link[x][c] = link[i].get(x, 0) + link[j].get(x, 0)
    for x in list(link[i]):
        link[x].pop(i, None)
    for x in list(link[j]):
        link[x].pop(j, None)
    link.pop(i, None)
    link.pop(j, None)
    act.discard(i)
    act.discard(j)
    act.add(c)
clusters = [mem[c] for c in act if size[c] >= 3]

# report
pl = {f: place(f) for f in sorted(LIB)}
by_dir = defaultdict(list)
for f, (d, _how) in pl.items():
    by_dir[d].append(f)


def wrapped(names):
    return textwrap.wrap(" ".join(sorted(n[:-2] for n in names)), 70,
                         initial_indent="   ", subsequent_indent="   ",
                         break_long_words=False, break_on_hyphens=False)


mod = git("status", "--porcelain", "--",
          "*.c", "*.h", "Makefile").strip()
dirty = " plus local changes" if mod else ""
print(f"git library source files by directory  "
      f"(HEAD {HEAD}{dirty}; {len(LIB)} files)\n")
for d in list(CHARTER):
    fs = by_dir.get(d, [])
    if not fs:
        continue
    lab_n = sum(1 for f in fs if pl[f][1] == "label")
    print(f"{d}/   {len(fs)} files  ({lab_n} by commit label)")
    for w in wrapped(fs):
        print(w)
    print()

ung = by_dir.get(None, [])
placed = len(LIB) - len(ung)
how = Counter(pl[f][1] for f in LIB if pl[f][0] is not None)
print(f"placed {placed} files in {len(CHARTER)} directories: "
      f"{how['label']} by commit label,\n{how['name']} by filename, "
      f"{how['override']} by override. The table is 14 lines.")
print(f"\n{len(ung)} files match no subsystem and are left ungrouped:")
for w in wrapped(ung):
    print(w)

# Second check with the call graph. It records which file uses
# functions from which other file, so it does not use names and is
# independent of the labels. Group files that call each other, then
# compare each group with the directories. Leave ungrouped helpers out.
agree = loose = 0
boundary = []
for c in clusters:
    by = defaultdict(list)
    for f in c:
        if pl[f][0]:
            by[pl[f][0]].append(f[:-2])
    dirs = sorted(by, key=lambda d: (-len(by[d]), d))
    if len(dirs) <= 1:
        agree += 1
    elif len(by[dirs[0]]) >= 2:
        boundary.append((dirs, by))
    else:
        loose += 1
boundary.sort(key=lambda x: (-len(x[1][x[0][0]]), x[0][0]))
covered = sum(len(c) for c in clusters)


def plural(n):
    return "group" if n == 1 else "groups"


print("\nSecond check. The call graph records which file uses "
      "functions from")
print("another file, so it does not use names. Group the files that "
      "call each")
print(f"other, then compare each group with the directories above. "
      f"{covered} files\nfall into {len(clusters)} call groups. The "
      f"{len(clusters)} sort into three kinds:")
print(f"  {agree} {plural(agree)}: all placed files land in one "
      "directory (call graph agrees).")
print(f"  {len(boundary)} {plural(len(boundary))}: most files in one "
      "directory, plus one or two\n     from another (the boundary "
      "cases to check).")
print(f"  {loose} {plural(loose)}: shared helpers that many files call "
      "(not shown).")
if boundary:
    print("\nBoundary groups, largest directory first. Each line "
          "is one")
    print("directory and its files in the group. Example: shallow "
          "is in")
    print("revision, but the call graph groups it with the transport "
          "files.")
    for dirs, by in boundary:
        print()
        for d in dirs:
            label = f"  {d} ({len(by[d])}): "
            for w in textwrap.wrap(" ".join(sorted(by[d])), 70,
                                   initial_indent=label,
                                   subsequent_indent=" " * len(label),
                                   break_long_words=False,
                                   break_on_hyphens=False):
                print(w)

# Label vs filename: the honest circularity check.
same, diff = 0, []
for f in sorted(LIB):
    lab = modal(f)
    if not lab:
        continue
    dl = to_dir(lab.split("/")[0].split("-")[0])
    dn = to_dir(f[:-2].split("-")[0])
    if dl and dn:
        if dl == dn:
            same += 1
        elif f not in OVERRIDE:
            diff.append((f, dl, dn, lab))
print(f"\nCommit label vs filename: both point to the same directory "
      f"for {same} files\nand disagree for {len(diff)} (the "
      f"{len(OVERRIDE)} overrides are separate). The commit\nlabel and "
      "the filename follow the same naming rule, so the "
      "label\nconfirms the naming, not the grouping. Only the call "
      "graph is an\nindependent check.")
for f, dl, dn, lab in diff:
    print(f"  {f[:-2]:20} label->{dl:10} name->{dn:10} ('{lab}:')")