Abstract:

This presentation outlines JJ's novel approach to tracking file copies and renames within a version control system. The speaker, Josh from Google, begins by reviewing the historical evolution of this feature, contrasting the explicit-but-flawed tracking in systems like Subversion with Git's reliance on expensive, un-cached runtime heuristics. The core of JJ's proposed solution is a backend-agnostic "copy history graph" that exists independently of the commit history. Each file is assigned a Copy ID based on its path and its parent files' Copy IDs. This graph is not directly persisted in the underlying backend (e.g., as part of a Git commit object). Instead, it is generated heuristically and cached locally in the user's repository upon clone or fetch. This "local-first" design allows for fast, cached lookups for operations like diff, log, and blame, while avoiding the need to alter backend data structures. This makes the solution resilient and performant, offering a significant improvement over Git's repeated heuristic calculations, and allows backends with native support (like Piper) to provide an exactly shared graph.

JJ's Novel Approach to Copy Tracking: A Backend-Agnostic, Locally Cached Graph

• 0:00:07 The Core Problem: Tracking file copies and renames is essential for maintaining a coherent project history. It allows developers to follow a file's evolution across name changes (for log and blame) and ensures that merges and rebases correctly apply changes to moved files.
• 03:04 Historical Solutions and Their Trade-offs: The talk reviews various version control systems:
  • RCS/CVS: Handled renames by simply renaming history files, effectively rewriting history rather than recording the event.
  • Subversion: Explicitly tracked copies, but its implementation was a known weak spot that could lead to incorrect merges.
  • Git: Does not explicitly track copies. Instead, it uses expensive runtime heuristics to detect them on-demand for commands like diff and merge. This is flexible but can be slow and is not cached between commands.
  • Mercurial/Sapling: Explicitly record copy metadata, creating a file ancestry graph that must be traversed alongside the commit history.
• 10:13 JJ's Solution: An Independent Copy History Graph: JJ proposes a backend-agnostic system built on a "copy history graph" that is separate from the commit graph. This allows for fast lookups without traversing thousands of commits.
• 11:36 Copy ID Data Structure: Every file is assigned a Copy ID, which is a hash of its copy history. This history contains the file's current path and a list of its parent files' Copy IDs, creating a directed acyclic graph (DAG) of file ancestry.
• 13:12 A Local-First, Cached Approach: A key innovation is that this copy history graph is not directly shared through the backend (e.g., it doesn't change Git commit hashes).
  • For backends like Git, the graph is built using heuristics and cached in a local database when a user clones or fetches changes. This avoids Git's expensive, repetitive runtime detection.
  • Because the graph is local, different users might have slightly different versions, but this doesn't break functionality—it just improves the local user experience.
  • Backends that natively support copy tracking (like Google's Piper) can populate an exact, shared graph for all users.
• 17:02 Fast, Copy-Aware Diffs: When performing a diff, JJ's algorithm traverses the small, efficient copy history graph to find a file's true ancestor. This allows it to correctly identify a file as modified, copied, or renamed, independent of the number of commits between the two states.
• 21:55 Development Roadmap: The initial implementation is focused on building the backend API and a copy-aware diff command. Future work will include implementing copy-aware merging, blame, and logs, as well as adding CLI commands for users to manually annotate copies.
• 23:22 Directory Renames Remain a Challenge: In the Q&A, it was noted that handling directory-level renames and merges is a known difficult problem that is not yet addressed by this design.