Antoine Pietri
email: antoine.pietri@inria.fr

Guillaume Rousseau
email: guillaume.rousseau@univ-paris-diderot.fr

Stefano Zacchiroli

Determining the Intrinsic Structure of Public Software Development History

Keywords: source code, version control system, network topology, graph structure, statistical mechanics

Background. Collaborative software development has produced a wealth of version control system (VCS) data that can now be analyzed in full. Little is known about the intrinsic structure of the entire corpus of publicly available VCS as an interconnected graph. Understanding its structure is needed to determine the best approach to analyze it in full and to avoid methodological pitfalls when doing so.

Objective. We intend to determine the most salient network topology properties of public software development history as captured by VCS. We will explore: degree distributions, determining whether they are scale-free or not; distribution of connect component sizes; distribution of shortest path lengths.

Method. We will use Software Heritage-which is the largest corpus of public VCS data-compress it using webgraph compression techniques, and analyze it in-memory using classic graph algorithms. Analyses will be performed both on the full graph and on relevant subgraphs.

Limitations. The study is exploratory in nature; as such no hypotheses on the findings is stated at this time. Chosen graph algorithms are expected to scale to the corpus size, but it will need to be confirmed experimentally. External validity will depend on how representative Software Heritage is of the software commons.

INTRODUCTION

The rise in popularity of Free/Open Source Software (FOSS) and collaborative development platforms [START_REF] Kalliamvakou | The promises and perils of mining GitHub[END_REF] over the past decades has made publicly available a wealth of software source code artifacts (source code files, commits with all associated metadata, tagged released, etc.), which have in turn benefited empirical software engineering (ESE) and mining software repository (MSR) research. Version control systems (VCS) in particular have been frequently analyzed [START_REF] Kagdi | A survey and taxonomy of approaches for mining software repositories in the context of software evolution[END_REF] due to the rich view they provide on software evolution and their ease of exploitation since the advent of distributed version control systems.

Only very recently systematic initiatives [START_REF] Abramatic | Building the Universal Archive of Source Code[END_REF][START_REF] Di | Software Heritage: Why and How to Preserve Software Source Code[END_REF][START_REF] Ma | World of code: an infrastructure for mining the universe of open source VCS data[END_REF] have been established to gather as much public VCS data as possible in a single logical place, enabling ESE research at the scale of, ideally, all publicly available source code artifacts-i.e., our entire software commons [START_REF] Kranich | Information Commons[END_REF]. In this paper we describe how we will conduct the first systematic exploratory study on the intrinsic structure of source code artifacts stored in publicly available version control systems.

As corpus we will use Software Heritage and its dataset [START_REF] Abramatic | Building the Universal Archive of Source Code[END_REF][START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF], which is the largest and most diverse collection of source code artifacts, spanning more than 5 billion unique source code files and 1 billion unique commits, collected from more than 80 million software projects.

The data model of our corpus is in Figure 1. It is a Merkle DAG [START_REF] Ralph | A Digital Signature Based on a Conventional Encryption Function[END_REF], fully deduplicated, linking together in a single giant graph the development histories of all publicly available VCSs. Actual source code files are represented as blob nodes, their grouping in source code trees as directory nodes; commit nodes are linked together by ancestry, supporting forks and N-ary merges; releases (or "tags") are also supported; the full states of VCSs is recorded periodically (similarly to what the Internet Archive wayback machine does for web pages) and associated to where it has been observed (a software origin, identified by an URL). We refer the reader to [START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF] for full details on the data model.

The study we will conduct will assess the most salient network topology properties [START_REF] Albert | Statistical mechanics of complex networks[END_REF] of the Software Heritage corpus as a graph. Such a systematic analysis is still missing in the literature and is needed for further empirical software engineering research for several reasons: a) Determine the most appropriate large-scale analysis approach. Most "large-scale" studies of VCSs fall short of the full body of publicly available source code artifacts and either resort to random sampling or focus on popular repositories. This is a potential source of bias, but is understandable for practical reasons. To enable studies on the entire software commons we need, in addition to platforms [START_REF] Abramatic | Building the Universal Archive of Source Code[END_REF][START_REF] Ma | World of code: an infrastructure for mining the universe of open source VCS data[END_REF], an understanding of its intrinsic structure, to choose the most appropriate large-scale analysis approach [START_REF] Dyer | Boa: A language and infrastructure for analyzing ultra-large-scale software repositories[END_REF][START_REF] Rousseau | Growth and Duplication of Public Source Code over Time: Provenance Tracking at Scale[END_REF] depending on the study needs. For instance, if the graph is easy to partition into loosely connected components, then a scale-out approach with several compute nodes holding in memory graph quasi-partitions would be best; if the graph is highly connected a scale-up approach relying on graph compression [START_REF] Boldi | Ultra-Large-Scale Repository Analysis via Graph Compression[END_REF] would be preferable. Similarly, knowing that most nodes are part of a single gigantic connect component (CC) would help in avoiding algorithmic approaches with high complexity on the size of the largest CC. b) Avoid methodological pitfalls. The same understanding is needed to avoid making strong assumptions on what constitutes "typical" VCS data. These pitfalls have been warned against since the early days of GitHub [START_REF] Kalliamvakou | The promises and perils of mining GitHub[END_REF], but that have not been quantified yet. The extent to which repositories on popular forges correspond to "well behaved" development repositories, as opposed to be outliers that are not used for software development or are built just to test the limits of hosting platforms or VCS technology is unknown. In our experience GitHub alone contains repositories with very weird artifacts (commits with one million parents or mimicking bitcoin mining in their IDs, the longest possible paths, bogus timestamps [START_REF] Rousseau | Growth and Duplication of Public Source Code over Time: Provenance Tracking at Scale[END_REF], etc.). How many statistically relevant outliers of this kind exist is unknown and needs to be documented as reference knowledge to help researchers in the interpretation of their empirical findings. c) Improve our understanding of our daily objects of study. More generally, in empirical software engineering we are collectively studying artifacts that naturally emerge from the human activity of software development. As it is commonplace in other sciences (and most notably physics), we want to study the intrinsic network properties of the development history of our software commons just because the corpus exists, it is available, and it is challenging to do so. The resulting findings might be also practically useful, but in spite of that we will obtain a more deep understanding of the nature of objects we study daily than what is known today.

VARIABLES

We define the following subsets of the starting corpus:

• full corpus: the entire Software Heritage graph dataset • filesystem layer: full corpus subset consisting of file and directory nodes only, and edges between them • history layer: full corpus subset consisting of commit and releases only, and edges between them • commit layer: subset of the history layer consisting of commit nodes only, and edges between them • hosting layer: full corpus subset consisting of origins and snapshost nodes only, and edges between them

For each corpus we will measure the following variables:

• indegree distribution: for each node the number of edges pointing to it • outdegree distribution: for each node the number of edges starting from it • local undirected clustering distribution: for each node the number of edges between nodes pointing to or from it (= local clustering coefficient without dividing it by the number of possible egdes between its neighbors) • CC size distribution: the size, in number of nodes, of each connected component in the underlying undirected graph of the input corpus • (for the filesystem and commit layers only) path length distribution: distribution of the length of shortest paths between all root (indegree=0) nodes and all leave (outdegree=0) nodes

MATERIAL

Dataset. We intend to the Software Heritage graph dataset [START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF] as corpus for the planned experiments. The main reasons for this choice are that: (1) it is the largest dataset about publicly software development history (see Table 1 for its size characteristics as a graph); (2) it is available as open data in various formats, 1 including a simple nodes/edges graph representation; (3) it has been chosen as topic for the MSR 2020 Mining Challenge, 2 hence we expect that by the time experiments will be run the body of related work around it will be substantial.

Software. We will use swh-graph [START_REF] Boldi | Ultra-Large-Scale Repository Analysis via Graph Compression[END_REF] and WebGraph [START_REF] Boldi | The webgraph framework I: compression techniques[END_REF] to produce and exploit compressed graph representations of the input corpus (see Section 5 for details). Statistical analyses will be performed using popular SciPy [START_REF] Mckinney | Python for data analysis: Data wrangling with Pandas, NumPy, and IPython[END_REF] components (NumPy, Pandas, . . . ). All developed custom code and derived data will be released as a complete replication package.

Hardware. We expect to be able to run all experiments on a single server equipped with 24 Intel Xeon 2.20 GHz CPUs and 750 GB of RAM, which is already available to us.

EXECUTION PLAN

We will follow the experiment protocol described below.

a. Retrieve the most recent version of the Software Heritage graph dataset [START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF] available, falling back to the one available at the time of writing (2018-09-25) if no newer releases have been published.

b. Compress the textual node/graph representation of the full dataset to a compact representation of its structure (which ignores all node metadata except node types) using swh-graph. Repeat for each subgraph of interest (see Section 3 for details). This step is expected to take about a week for the full graph and proportionally less time for the various subgraphs. c. (RQ1) Compute indegrees, outdegrees and local clustering for all nodes in the graph, for all relevant (sub)graphs, exploiting the WebGraph [START_REF] Boldi | The webgraph framework I: compression techniques[END_REF] API with custom Java code. d. (RQ2) Compute all connected components on all relevant (sub)graphs using well known algorithms [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF] that can be implemented with custom Java code as visits (BFS or DFS) on the Web-Graph graph representations. A full graph visit is expected to take a few hours, scaling down linearly for subgraphs. [START_REF] Boldi | Ultra-Large-Scale Repository Analysis via Graph Compression[END_REF] e. (RQ3) For each subgraph of interest (e.g., the file system layer composed only of files and directory nodes), for all root nodes (e.g., source code root directories), create a shortest path spanning tree to all leaves (e.g. file or directory nodes with no children). Then export all path lengths. This can be implemented with custom Java code realizing Dijkstra's algorithm on top of the WebGraph API. We have no precise estimate of how long this step will take; it will take more than a single full graph visit, due to paths that will be re-explored, but it should remain manageable. Thread-base parallelization is an option in case we need to speed up this step.

ANALYSIS PLAN 6.1 Descriptive statistics

We will analyze the raw data obtained from the execution plan according to the following analysis protocol.

a. (RQ1) We will plot indegree/outdegree/local clustering distributions as histograms, one histogram per distribution and per (sub)graph (see Section 3 for details).

• One figure per distribution and graph will be produced, showing both the raw histogram (i.e., for each degree/clustering value observed, the number of nodes with that value) as well as the cumulative distribution function (CDF) given by the number of nodes whose degree/clustering is greater than or equal to a given value. One or more scales among lin-lin, lin-log, log-lin, log-log scales will be used, depending on presentation needs. • Each distribution will be qualitatively discussed by comparing it with a generic distribution functions (power law, exponential law, Poisson law). • In case they arise, the presence of outliers or other statistical anomalies with respect to more regular regions of the distribution will be highlighted (e.g., change of law, change of slope, . . . ), and may lead to specific investigations to determine their nature.

b. (RQ1) The nature of the tail of each distribution will be systematically analyzed and discussed.

• The first observed criterion will be the amplitude of the range of degree values, expressed in decades. • Then, we will use the discrete maximum likelihood estimator (MLE) to determine the scaling parameter [START_REF] Clauset | Power-law distributions in empirical data[END_REF]Eq. 3.7].

𝛼 (𝑑 𝑚𝑖𝑛 ) = 1 + 𝑛 𝑛 ∑ 𝑖=1 ln 𝑑 𝑖 𝑑 𝑚𝑖𝑛 -1
where 𝑑 𝑖 , 𝑖 = 1, . . . , 𝑛 are the observed degree values such that 𝑑 𝑖 ≥ 𝑑 𝑚𝑖𝑛 . Without prejudging, nor speculating whether the distributions will match power laws or not, we limit ourselves to the first step of the methodology proposed in [5, Box 1], using the above estimator which depends on an arbitrary degree threshold 𝑑 𝑚𝑖𝑛 , beyond which the behaviour of the distribution is ignored, like a probe through the whole range of degrees. The plot is displayed in log-lin scale over the degree range. Lacking precise information on the results at this stage, as well as knowledge about the impact of possible atypical events in the observed distributions, it is premature to plan to implement the subsequent steps of the aforementioned methodology.

c. (RQ2) We will display connected component size, focusing on VCS origins that contain at least one commit, as a set of histograms.

• As above, both raw distribution functions and cumulative distributions will be displayed. • To characterize the aggregation process into connected components as nodes of different types, or at different depths, are added to the corpus:

-We will produce histograms showing the raw distribution and CDF, for each layer depth within each layer. -For each of them, we will produce a table summarizing the number of isolated origins and size of the largest connected component. -We will quantitatively compare the distribution functions by displaying the Kolmogorv-Smirnov distance between them, weighted by connected component sizes expressed as the number of origin nodes they contain.

d. (RQ3) We will display the distribution of root-leaf shortest path lengths for the recursive layers of the public VCS corpus (commit and filesystem layers), as a pair of histograms.

• As before, both raw and cumulative distribution functions will be displayed and discussed.

6.2 Practical significance of the findings RQ1's answers will provide information on how the public VCS graph compares with other naturally occurring graphs in collaboration, such as the social network graphs or the graph of the Web. While seemingly only of theoretical significance, degree distributions and derived properties such as graph density directly impact on the practical exploitability of graphs of this scale. For instance graphs with fat-tailed degree distributions compress better than others. We know from previous work [START_REF] Boldi | Ultra-Large-Scale Repository Analysis via Graph Compression[END_REF][START_REF] Rousseau | Growth and Duplication of Public Source Code over Time: Provenance Tracking at Scale[END_REF] how well the full VCS graph compress, but a systematic study of related properties for the subgraphs we intend to address here is still missing. Findings related to RQ2 will directly tell how to best approach full-scale analyses of the various corpuses. If, for instance, it will turn out that 80% of the nodes are part of a gigantic component, than distributed approaches will be generally difficult to implement, due to entanglement and the pseudo-random nature of identifiers in Merkle DAG. Opposite considerations will apply for a more uniform distribution of CC sizes.

Finally, RQ3's answers will tell what's the average path depths in the recursive layers of the public VCS corpus, which is practically useful for several analysis needs. The average commit length is a limiting factor in analyses based on git blame, as we need to travel back development history to attribute files (if not SLOC) contributions. Similar considerations apply to average path lengths (in the filesystem layer), when we need to attribute files or directories to originating commits, for analysis or provenance tracking needs.

LIMITATIONS

Exploratory nature of the study. The study we propose is exploratory in nature, hence we state no hypotheses on the findings at this stage. This is intended, as the intrinsic structure of the public VCS corpus has never been characterized before at the extent we propose.

Algorithmic feasibility. With its 10+ B nodes and 160+ B edges the corpus we plan to study is a substantial graph for graph practitioners standards; not as big as the graph of the Web, but significantly larger than most benchmarks used in the field. At this scale, algorithms with super-linear complexity are generally considered non practically applicable.

Our algorithmic approaches for RQ1 and RQ2 have linear complexity; the approach for RQ3 is super linear, but we are restricting it to selected subgraphs and we expect it to exhibit enough sharing/caching to be practically treatable. We do not expect it to be the case but if, due to either algorithmic of technological considerations, any specific sub-experiment will turn out to be not practically feasible, we will resort to uniform random sampling.

External validity. Due to organic crawling lag, Software Heritage does not capture the full extent of publicly available VCSs. Hence we do not claim being able to characterize the intrinsic structure of the entire history of publicly available software development. The chosen dataset is nonetheless the best publicly accessible option available today to researchers. It is also well representative of the most popular development forge(s) in use today. As such we expect that the network topology findings of this study will provide useful insights to researchers and practitioners in the field.

Figure 1 :

 1 Figure 1: model: a Merkle DAG linking together source code artifacts commonly found in version control systems.

Table 1 :

 1 Corpus size as a graph (release: 2018-09-25). Specifically we will perform an exploratory study, with no predetermined hypotheses, and answer the following research questions: RQ1 What is the distribution of indegrees, outdegrees and local clustering of the public VCS history graph? Which laws do they fit? How do such distributions vary across the different graph layers-file system layer (files + directories) v. history layer (commits + releases) v. origin layer. RQ2 What is the distribution of connected component sizes for the public VCS history graph? How does it vary across graph layers? RQ3 What is the distribution of shortest path lengths from roots to leaves in the recursive layers (commits and directories) of public VCS history graph.

	Nodes		Edges
	origins (ori)	85 M	ori→snp	74 M
	snapshots (snp)	57 M	snp→cmt	616 M
	releases (rel)	9.9 M	cmt→cmt	1.2 B
	commits (cmt)	1.1 B	cmt→dir	1.2 B
	directories (dir)	4.4 B	dir→dir	49 B
	files	5.0 B	dir→file	113 B
		≈ 11 B	≈ 165 B
	2 RESEARCH QUESTIONS

https://annex.softwareheritage.org/public/dataset/graph/, retrieved

2020-01-09 2 https://2020.msrconf.org/track/msr-2020-mining-challenge, retrieved 2020-01-09


Antoine Pietri
email: antoine.pietri@inria.fr

Guillaume Rousseau
email: guillaume.rousseau@u-paris.fr

Stefano Zacchiroli

Forking Without Clicking: on How to Identify Software Repository Forks

Keywords: software evolution, source code, software fork, open source, free software, version control system

The notion of software "fork" has been shifting over time from the (negative) phenomenon of community disagreements that result in the creation of separate development lines and ultimately software products, to the (positive) practice of using distributed version control system (VCS) repositories to collaboratively improve a single product without stepping on each others toes. In both cases the VCS repositories participating in a fork share parts of a common development history.

Studies of software forks generally rely on hosting platform metadata, such as GitHub, as the source of truth for what constitutes a fork. These "forge forks" however can only identify as forks repositories that have been created on the platform, e.g., by clicking a "fork" button on the platform user interface. The increased diversity in code hosting platforms (e.g., GitLab) and the habits of significant development communities (e.g., the Linux kernel, which is not primarily hosted on any single platform) call into question the reliability of trusting code hosting platforms to identify forks. Doing so might introduce selection and methodological biases in empirical studies.

In this article we explore various definitions of "software forks", trying to capture forking workflows that exist in the real world. We quantify the differences in how many repositories would be identified as forks on GitHub according to the various definitions, confirming that a significant number could be overlooked by only considering forge forks. We study the structure and size of fork networks, observing how they are affected by the proposed definitions and discuss the potential impact on empirical research.

INTRODUCTION

How developers and software communities work on their projects, and how this relationship evolves over time, have been topics of interest in software engineering research for many decades.

Historically, software "forking" [START_REF] Nyman | Notes on the History of Fork and Join[END_REF] has been intended as the practice of taking the source code and development history of an existing software product to create a new, competing product, whose development will happen elsewhere and taken to different directions. This kind of "hard fork" is enabled by free/open source software (FOSS) licensing [START_REF] Fogel | Producing open source software: How to run a successful free software project[END_REF] and its possibility is an asset that guarantees freedom of development; while the actual occurrence of a hard fork has generally been considered a liability [START_REF] Robles | A Comprehensive Study of Software Forks: Dates, Reasons and Outcomes[END_REF] for project sustainability [START_REF] Nyman | Hackers on Forking[END_REF][START_REF] Nyman | To Fork or Not to Fork: Fork Motivations in SourceForge Projects[END_REF][START_REF] Rastogi | Forking and the Sustainability of the Developer Community Participation-An Empirical Investigation on Outcomes and Reasons[END_REF].

In the past decade the rise in popularity of distributed version control systems (DVCS) [START_REF] Spinellis | Version control systems[END_REF] introduced a significant shift of paradigm and terminology. The expression "fork" is now generally intended [START_REF] Zhou | What the fork: a study of inefficient and efficient forking practices in social coding[END_REF] to refer to the mere technical act of creating a new VCS repository that contains the full history (at the time of fork) of a preexisting repository, without an implicit negative connotation (also called "development forks" [START_REF] Fogel | Producing open source software: How to run a successful free software project[END_REF]). Repository forks can be created on social coding platforms [START_REF] Dabbish | Social coding in GitHub: transparency and collaboration in an open software repository[END_REF][START_REF] Thung | Network structure of social coding in GitHub[END_REF] with as little as a click on a button. Then, while a forked repository can be used to hard fork a project, often it is just a way to work on software improvements that will be eventually sent back to the originating project as pull requests [START_REF] Gousios | An exploratory study of the pull-based software development model[END_REF] for integration.

Likely as a consequence of the prevalence of social coding platforms, recent literature on forks has focused on a single source of truth to determine what constitutes a fork: metadata provided by code hosting providers, and most notably GitHub. Clicking the fork button on GitHub indeed, in addition to cloning development history into a new repository, also registers a "is forked from" relationship between the new repository and its parent. This relationship forms an ancestry graph that GitHub makes available through its API and that is what has traditionally been studied as a large, easily exploitable fork network.

The first drawback of trusting platform metadata as source of truth for what repository is a fork is that it is platform-specific. One cannot identify as forks repositories hosted on GitHub that has been forked from, say, GitLab, or more generally non-GitHub hosted repositories, and vice-versa. Similarly, although arguably less relevant from a quantitative point of view, one cannot recognize as forks, say, Git repositories used to collaborate with Subversion repositories via git-svn. For a fork ecosystem to be properly studied via the current approach, all the parallel development must happen using the same VCS and on the same platform. While the prevalence of Git does not seem to be waning, Git code hosting diversity is increasing, making the platform-specific part of this problem potentially severe.

A second, more subtle methodological drawback is that trusting platform metadata introduces a selection bias on both the amount and type of forks that are considered. The fact that social coding platform strongly encourage, and sometimes even automate, the creation of forked repositories as the main way to contribute even the smallest one-liner change, inflates the number of forks. Many of these (soft) forks will be short-lived in terms of development activity. Hard forks will comparatively be more long lived and will not necessarily reside on the same code hosting platform. The example of the Linux kernel community is revealing in this respect: several copies of the full development history of Linux exist on GitHub, but are not recognizable as forks of torvalds/linux according to platform metadata, because kernel development does not primarily happen on GitHub and kernel developers create their repositories using git clone.

Fork inflation also results in increased duplication of software artifacts (source code files or directories, commits, . . . ) across repositories [START_REF] Rousseau | Growth and Duplication of Public Source Code over Time: Provenance Tracking at Scale[END_REF], which has a significant impact on fork studies that rely on metrics as simple as repository size (measured as the number of hosted commits). Filtering out forked repository is a common solution to this problem, which calls into question how to properly identify forks.

The absence of extensive, homogeneous fork research has been pointed out in the past as a missing piece [START_REF] Robles | A Comprehensive Study of Software Forks: Dates, Reasons and Outcomes[END_REF] in the literature. In this paper we try to provide methodological tools to enable fork studies that do not restrict themselves to platform metadata to recognize forks, thereby removing the constraint of analyzing a single platform and mitigating the risk of selection biases.

As an alternative to relying on platform metadata to recognize forks we propose to compare the content of VCS and consider as forks repositories that share artifacts such as commits or entire source trees. We will explore the impact of different such definitions and compare their impact in terms of the amount and structure of forks identified using platform metadata. Specifically, we will answer the following research questions: RQ1: how do code hosting platform information about which VCS repositories are forks compare to the presence of shared source code artifacts in repositories? RQ2: how are (a) the amount of forks and (b) the structure of fork networks affected by fork definitions based on VCS artifact sharing? RQ1 will intuitively assess the level of trustworthiness of platform fork metadata: if many repositories, e.g., share commits but are not identified as fork by platform metadata, then relying on those metadata alone would appear to be methodologically dangerous. As one might consider different types of shared VCS artifacts (commits, source tree directories, individual files, . . . ) as fork evidence, RQ2 will provide an empirical evaluation of the effects of basing fork definitions on one or the other.

Paper structure. Section 2 explores the spectrum of fork definitions considered in the paper. Section 3 presents the experimental methodology and used datasets. Results are discussed in Section 4, threats to their validity in Section 5. Before concluding, related work is discussed in Section 6.

Replication package. A replication package for this paper is available from Zenodo at https://zenodo.org/record/3610708.

WHAT IS A FORK?

In this section we explore the spectrum of possible definitions of what constitutes a fork. In the following we will use the term "fork" to mean a forked software repository, without discriminating between "hostile" (or hard forks, according to the terminology of [START_REF] Zhou | What the fork: a study of inefficient and efficient forking practices in social coding[END_REF]) and development forks. We propose three definitions, corresponding to three types of forks-type 1 to 3, reminiscent of code clone classification [START_REF] Dhavleesh Rattan | Software clone detection: A systematic review[END_REF][START_REF] Kumar | A survey on software clone detection research[END_REF]-along a spectrum of increased sharing of artifacts commonly found in version control systems (VCS), such as commits and source code directories.

The first definition, of type 1 forks, relies solely on code hosting platform information and requires no explicit VCS artifact sharing between repositories to be considered forks (although it allows it): Definition 2.1 (Type 1 fork, or forge fork). A repository 𝐵 hosted on code hosting platform 𝑃 is a type 1 fork (or forge fork) of repository 𝐴 hosted on the same platform, written 𝐴 ⇝ 1 𝐵, if 𝐵 has been created with an explicit "fork repository 𝐴" action on platform 𝑃.

Although informal and seemingly trivial, this definition is both meaningful and actionable on current major code hosting platforms. For example, GitHub stores an explicit "forked from" relationship and makes it available via its repositories API: 1The parent and source objects are present when the repository is a fork. parent is the repository this repository was forked from, source is the ultimate source for the network. GitLab does the same and exposes type 1 fork information via its projects API: 2 If the project is a fork, and you provide a valid token to authenticate, the forked_from_project field will appear in the response. which corresponds to exploitable JSON metadata such as:

{ " id " : 3 , ... " forked_from_project " : { " id " : 1 3 0 8 3 , " description " : " GitLab Community Edition " , " name " : " GitLab Community Edition " , ... " path " : " gitlab -foss " , " path_with_namespace " : " gitlab -org / gitlab -foss ", " created_at " : " 2 0 1 3 -0 9 -2 6 T 0 6 : 0 2 : 3 6 . 0 0 0 Z " , ... Without getting too formal we observe that each repository is the forge fork of at most one repository (its parent) and that the relation of being a forge fork is: not reflexive (𝐴 ̸ ⇝ 1 𝐴), not symmetric (𝐴 ⇝ 1 𝐵 does not imply-and, in fact, excludes-that 𝐵 ⇝ 1 𝐴), not transitive (𝐴 ⇝ 1 𝐵 and 𝐵 ⇝ 1 𝐶 does not implyand in fact, due to parent uniqueness, excludes-that 𝐴 ⇝ 1 𝐶). The latter might seem surprising at first but is consistent with the definition, because the action resulting on the creation of 𝐶 happened on 𝐵, not 𝐴. (We will introduce later a related notion of repository relationship that captures transitivity.)

Forge forks induce a global directed graph on repositories, specifically a forest of disjoint fork-labeled trees, as depicted in Figure 1.

Type 2 forks, or shared commit forks, are based on the ability offered by most VCS (and all distributed VCS) of globally identifying commits across any number of repositories, usually by the means of intrinsic commit identifiers based on cryptographic hashes [START_REF] Di | Identifiers for Digital Objects: the Case of Software Source Code Preservation[END_REF][START_REF] Spinellis | Version control systems[END_REF]. Given the ability to identify commits across different repositories we can define type 2 forks as follows: Definition 2.2 (Type 2 fork, or shared commit fork). A repository 𝐵 is a type 2 fork (or shared commit fork) of repository 𝐴, written 𝐴 ⇝ 2 𝐵 if it exists a commit 𝑐 contained in the development histories of both 𝐴 and 𝐵. Figure 2 shows an example of 2 repositories, 𝐴 and 𝐵 that are type 2 forks of each other, due to the fact they have in common commit 1, the initial commit; their respective development histories diverged immediately after that commit and never shared any other commits. In the general case shared commit forks will share many more commits: all the commits that were available at the time of the most recent development history divergence.

Differently from type 1 forks, the relation of being a type 2 fork is symmetric (𝐴 ⇝ 2 𝐵 implies 𝐵 ⇝ 2 𝐴), but still not transitive (as three repositories 𝐴, 𝐵 and 𝐶 can have shared artifacts between 𝐴 and 𝐵 and between 𝐵 and 𝐶 without there necessarily being a shared artifact between 𝐴 and 𝐶). Intuitively, the notion of shared commit forks is more robust than that of forge forks because it allows to recognize as forks-in the broad sense of "repositories that collaborate with one another"repositories that are hosted on different platforms. A repository hosted on GitLab.com, or your personal git repository on your homepage, can be recognized as a fork of a another hosted on GitHub. The price to pay is that, due to symmetry, the definition alone is not enough to orientate the relation; it does not capture which repository "came first".

We can push this idea further, trying to make it even more robust, and capable of recognizing as forks repositories that have no recognizable shared commits, but do share entire source trees. That is of interest when, for example, collaboration happens using different version control systems (e.g., a developer using git-svn to participate into the development of a Subversion based project). Type 3 forks, or shared root (directory) forks, allow to capture those situations: Definition 2.3 (Type 3 fork, or shared root fork). A repository 𝐵 is a type 3 fork (or shared root fork) of a repository 𝐴, written 𝐴 ⇝ 3 𝐵, if there exist a commit 𝑐 𝐴 in the development history of 𝐴 and a commit 𝑐 𝐵 in that of 𝐵 such that the full source code trees of the two commits are identical.

The intuition behind type 3 forks is depicted in Figure 3. Note that it is not enough for the two repositories to share any arbitrary sub-directory to be considered forks, as that would consider as forks repositories that embed third-party libraries, an arguably undesired consequence; we need the root directories of two commits to be (recursively) equal for establishing a shared root fork relationship.

The same properties of type 2 forks apply to type 3 forks: the shared root fork relation is also symmetric. In most VCS, and in all modern DVCS, type 2 forks is also a strictly larger relation than type 3 forks: 𝐴 ⇝ 2 𝐵 implies 𝐴 ⇝ 3 𝐵, because if there exists a shared commit 𝑐 that makes 𝐴 and 𝐵 shared commit forks, then the root directory pointed by 𝑐 also makes 𝐴 and 𝐵 shared root forks (due to the cryptographic properties of intrinsic commit identifiers in DVCS). This property of inclusion, in the sense of one definition implying the other, is at the heart of the analysis made in section 4.3, studying the aggregation processes of networks and cliques.

In theory we could go further, and introduce an even more lax notion of fork, that equates repositories sharing as little as a single file, but that would exacerbate the problematic behavior we discussed for sharing sub-directories.

Armed with these definitions we will be able to answer RQ1, by comparing the number of forks identified by Definition 2.1 with those identified by Definition 2.2 and/or 2.3 (that we refer to as intrinsic forks). To fully address RQ2 on the other hand we need to capture the notion of "community" of repositories used for collaboration, as follows: Definition 2.4 (Type 𝑇 fork network). The type 𝑇 fork network of a repository 𝐴 is the smallest set N 𝑇 𝐴 such that:

• 𝐴 ∈ N 𝑇 𝐴 • ∀𝐵 ∈ N 𝑇 𝐴 , 𝐵 ⇝ 𝑇 𝐶 =⇒ 𝐶 ∈ N 𝑇 𝐴 • ∀𝐵 ∈ N 𝑇 𝐴 , 𝐶 ⇝ 𝑇 𝐵 =⇒ 𝐶 ∈ N 𝑇 𝐴
That is, a fork network is the set of all repositories reachable from a given one, following both forked from (parents) and forked to repositories (children). The definition is parametric in the type of forks, so we have type 1 fork networks (N 1 ), type 2 fork networks (N 2 ), and type 3 fork networks (N3 ).

A stricter notion that will come in handy is that of repository cliques, sets of repositories that are all direct forks (i.e., neither transitive nor reverse transitive) of each other: Definition 2.5 (Type 𝑇 fork clique). The type 𝑇 fork clique of a repository 𝐴 is the largest set C 𝑇 𝐴 such that:

• 𝐴 ∈ C 𝑇 𝐴 • ∀𝐶, (∀𝐵 ∈ C 𝑇 𝐴 , 𝐵 ⇝ 𝑇 𝐶 ∧ 𝐶 ⇝ 𝑇 𝐵) =⇒ 𝐶 ∈ C 𝑇 𝐴
Note that, while this definition is parametric in the type of forks too, fork cliques make intuitive sense only for type 2 and type 3 forks; type 1 forks (forge forks) only have singleton cliques as the relation is not symmetric.

METHODOLOGY 3.1 Dataset

Our goal is to experimentally determine the amount and structure of forks for the various definitions we have introduced. To do so we will use two datasets: the Software Heritage Graph Dataset [START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF], which contains the development history needed to find intrinsic fork relationships, and a reference forge-specific dataset, GHTorrent [START_REF] Gousios | GHTorrent: Github's data from a firehose[END_REF], which contains the fork ancestry relationships as captured by GitHub.

GHTorrent. GitHub is the largest public software forge, and is therefore the candidate of choice to study forge forks (type 1). GHTorrent [START_REF] Gousios | GHTorrent: Github's data from a firehose[END_REF] crawls and archives GitHub via its REST API and makes periodical data dumps available in a relational table format. In its database schema, the project table contains a unique identifier for each repository, and a forked_from column contains the ID of the repository it has been forked from if the repository is considered to be a forge forks. A single SQL query on this table allows to extract the full graph of GitHub-declared forks, e.g.: 3 B origins ("repositories") snapshots releases ("tags") revisions ("commits") directories ("trees") contents ("blobs") Software Heritage Graph Dataset. Software Heritage [START_REF] Abramatic | Building the Universal Archive of Source Code[END_REF][START_REF] Di | Software Heritage: Why and How to Preserve Software Source Code[END_REF] is the largest publicly accessible archive of software source code and accompanying development history, spanning more than 90 million software projects retrieved from major development forges including GitHub and GitLab.com. The Software Heritage Graph Dataset [START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF] is an offline dataset containing the development history of all the projects in Software Heritage in a tabular representation of a unified directed acyclic graph (DAG). As the archive encompasses a substantial portion of all the public GitHub repositories, it is possible to cross-reference the origins contained in this dataset with the ones in GitHub, our reference for forge forks.

The Software Heritage Graph Dataset data model maps the traditional concepts of VCS as nodes in a Merkle DAG [START_REF] Ralph | A Digital Signature Based on a Conventional Encryption Function[END_REF], as shown in Figure 4. As a consequence, all the development artifacts, including commits and source trees, are natively deduplicated within and across projects. This property is particularly useful to find intrinsic forks, as it enables tracking the relevant artifacts (revisions and directories) across the entire dataset and link them back to their source repositories.

The dataset contains two intermediate layers between repositories and the commit graph they point to: snapshots, which are point in time captures of the state of a repository; and releases (or "tags"), which are revisions (or commits) labeled with a specific name. As none of our fork definitions depend on these artifacts, the two layers can be flattened out so that the origins point directly to the revision graph. Likewise, the blob layer and the directory layer are not needed to find shared commit forks (Definition 2.2), while shared root forks (Definition 2.3) only require the root directory of each revision. Filtering out the unnecessary nodes reduces the graph to a more reasonable size of 2 billion nodes (down from 10 billion), which makes it easier to process on a single machine. The structure of the resulting subgraph closely matches the examples in Figure 2 and Figure 3, making it easy to verify the intrinsic definitions. We run the experiments on the compressed version of the two graph datasets, using the WebGraph framework [START_REF] Boldi | The webgraph framework I: compression techniques[END_REF][START_REF] Boldi | The WebGraph Framework II: Codes For The World-Wide Web[END_REF]. The Software Heritage Graph Dataset is already distributed as a compressed BVGraph, along with the swh-graph helper library [START_REF] Boldi | Ultra-Large-Scale Repository Analysis via Graph Compression[END_REF] to run traversal algorithms easily. The GHTorrent can be compressed from its relational database format using the swh-graph compress utility.

Fork networks

The easiest way to get a first sense of the amount and structure of forks according to the various definitions is to find all fork networks, as per Definition 2.4. This can be done in linear time with a simple graph traversal with linear complexity: two repositories are in the same network if and only if there exists a path between them in the undirected subgraph of origins and revisions. (We recall from the dataset section that we have removed the snapshot and revision layers, so that root commits are directly pointed by repository nodes.) Finding all the fork networks is therefore equivalent to computing the connected components on this subgraph, as exemplified in Figure 5.

Using fork networks has the advantage of allowing easy interpretations of the results. First, it is trivial to quantify how many repositories are forks by counting the number of repositories that belong to non-singleton networks. Besides, a direct comparison can be made between the distribution of forge forks and shared commit or root forks, as networks provide a partition method for both graphs. The sizes of the networks can be directly compared between the three definitions while keeping the invariant of number of total repositories. This is not the case when looking at fork cliques, since the same repository can be found in multiple cliques, which makes comparison harder. Here, repositories A and C are in the same network because there is a path between them, even though they do not share common development history.

In GHTorrent origins are already linked together in a global graph where the edges represent the forge-level forking relationships. We can partition this forge fork graph in fork networks similarly by computing all its connected components.

Our experimental design is therefore as follows: first, we list the common non-empty repositories between the Software Heritage Graph Dataset and GHTorrent. We then extract the aforementioned subgraphs: the development history graph for Software Heritage (origins → {revisions, releases} → commits) and the fork graph for GHTorrent (origins → origins). We then compute the connected components of each graph using a simple depth-first traversal algorithm, then output the origins contained in each component.

Fork cliques

While partitioning the corpus in fork networks gives a good idea of how intrinsic forks are linked together, it can group together repositories that are not forks of each other, as the intrinsic fork relationship is not transitive. Figure 6 shows a pattern, that we have verified as commonly found in the wild, where two different cliques will be merged in the same fork network-A and B are part of the same clique as they share development history; the same applies to B and C; whereas A and C do not share any part of their respective development histories but will end up in the same network. We expect this effect to merge cliques into giant components, that will make the size of the largest networks hard to interpret.

The other interesting metric that can be looked at is the distribution of fork cliques, as defined in Definition 2.5. While cliques do not provide a partition function for the graph, they allow to narrow down the actual extent of forking relationships within large fork networks.

Due to the fact that shared commit fork cliques are defined pairwise, the naive algorithm to find all the inclusion-maximal cliques is superlinear: for each repository, walk through its commit history and add all the commits to a queue, then take the transposed graph to walk through the commit history backwards and list all repository leaves. The time complexity of this algorithm is highly unpractical: in the worst case, if all the repositories are forks of each other, is has time complexity of O (𝑅 × 𝐶) where 𝐶 is the number of commits and 𝑅 the number of repositories in the graph.

However, clever use of some properties on the DAG structure of the commit graph can substantially speed up the algorithm. First, fork cliques can be generated by iterating on the common ancestors instead of the repositories: for each commit 𝑐, if it has more than one repository leave when doing a traversal on the transposed graph, then 𝑐 was a common commit ancestor, and the generated set of repositories is a fork clique. Besides, since the ancestry relationship is transitive, the clique with commit 𝑐 as a common ancestor is the same as the clique generated by running the traversal on its parents. By induction, it is possible to compute all the cliques simply by doing one traversal per "root" commit.

The resulting algorithm is Algorithm 1: for each root commit with no parents, we generate the clique of all repositories that contain it. We use a cryptographic hash fingerprint to avoid adding multiple times the same clique if it has multiple root commits. While this algorithm technically does not change the worst case complexity on arbitrary graphs, it is still a huge speed improvement in our case, as commit chains tend to be degenerate (i.e., very long chains with indegrees and outdegrees close to 1 on average). Algorithm 1 has a best-case complexity of Θ(𝐶), equivalent to a single DFS traversal. The commit graph is largely close to this bestcase scenario, making the algorithm run in just a few hours on the entire corpus.

While Algorithm 1 works well for shared commit forks, the speedup does not apply to shared root forks: the induction property no longer works for root directories, as they are not organised in nearly-degenerate chains. The time complexity for type 3 forks is closer to the worst case of O (𝐶 × 𝑅), which makes the clique analysis impractical for this kind of forks. P-clique partition function. While cliques do not directly provide a way to partition the corpus in several fork clusters (because a single origin can be contained in multiple cliques), it is possible to define a partition function based on them, e.g., by always assigning repositories to the largest clique they belong to. As repositories belonging to multiple cliques appear to be a quite rare occurrence (as they require the equivalent of a git merge --allow-unrelated-histories on two completely different repositories), the arbitrary criterion choice is not expected to be a significant caveat to interpret the results.

We use the Algorithm 2 to generate the partition function of the graph based on cliques. To implement the criterion of attributing repositories to their largest cliques, cliques are processed in decreasing order of size. Building a reverse index of "repository → clique it belongs to" allows direct access to the subsequent occurrences of repositories in smaller cliques to remove them. After doing so, the cliques left empty are removed and the newly generated graph partition can be returned.

The output of this algorithm generate a set of sets of origins that are subsets of the input fork cliques. We call this set "fork p-cliques" to emphasize the fact that they form a partition of the repository set in which all the groups are fork cliques.

Once this p-clique graph partition is established, the fork definition can once again be compared with the forge definition, by looking at the difference between the size distribution of the partitioned cliques of type 2 forks and the size distribution of networks for type 1 forks.

RESULTS

We identified 71.9 M repositories in common between the Software Heritage Graph Dataset and GHTorrent, 41.4 M of which are nonempty. We focused our experiments on these repositories.

Fork networks

In the GHTorrent graph, we found 25.3 M different connected components, among which 22.9 M repositories isolated in their own component, which means they are not forge forks (type 1) of other repositories. The other 2.4 M connected components contain the remaining 18.5 M repositories, which are all in fork networks. These forge forks represent 44.74% of all repositories.

In the Software Heritage Graph Dataset, we found 24.0 M connected components, among which 21.3 M isolated repositories. The remaining 2.6 M components contain 20.1 M shared commit forks (type 2), i.e., 48.44% of all repositories. We have hence almost 9% more shared commit forks than forge forks, which is a significant divergence for the most strict definition of forks based on shared VCS artifacts.

For shared root forks (type 3), we found 18.5 M connected components, among which 16.1 M isolated repositories and 25.3 intrinsic forks (61.08% of all repositories), which is almost 37% more than the forge forks. These results are summarized in Table 1. They suggest that in between 1.6 M (3.8% of total) and 6.8 M (16%) repositories might be overlooked when studying forks using only GitHub metadata as a source of truth for what is a fork.

Figure 7 shows the cumulative frequency distribution of fork networks for intrinsic forks and forge forks. That is, for each fork network size 𝑥, the number of repositories in networks of size ≥ 𝑥 is shown. At first glance, the distribution of forge forks and shared commit forks appear to be pretty similar (although the log scale minimizes the differences between the two), which is a good sign that the two definitions are not returning vastly different results. The average size of fork networks is also about the same (≈ 7.6 for type 2 forks, ≈ 7.7 for type 1). The situation appears to be quite different for shared root forks, where the average size is ≈ 10.5 and the frequency distribution is significantly farther from the reference distribution of forge forks.

One distinguishing feature of each distribution of type 2 and type 3 forks is the size of the largest connected component, which is significantly larger than the largest networks of forge forks (by a factor of 17 for shared revision forks, and 157 for shared root forks). As discussed in Section 3.3, this is an expected outcome of our use of network as a quantification metric and confirms the need for further analysis through fork cliques. This does not however have any implications on the quantification aspect of the experiment, as partitioning this network further using fork cliques would still yield the same number of non-isolated repositories.

Fork cliques

As expected, running Algorithm 1 to generate the shared-revision cliques on the compressed graph does not take more than an hour, which is the same order of magnitude as the time needed for a simple full traversal of the revision graph [START_REF] Boldi | Ultra-Large-Scale Repository Analysis via Graph Compression[END_REF]. This confirms our prediction that in the shared-revision case, the average-case runtime of the algorithm is close to Θ(𝑅).

The algorithm finds 24.5 M cliques, although the results are difficult to interpret in this current state as the cliques overlap together. A few key observations can nevertheless already be made, notably the absence of very large cliques: the largest clique contains 92.4 M repositories, which is very similar to the largest forge fork network (which contains 90.2 M repositories). This is consistent with our intuition expressed in Section 3.3 that the largest intrinsic fork networks are a specific feature of networks (as seen in Figure 6), and that these artifacts disappear when looking at the cliques. It is also possible to measure how the cliques overlap: 28 M repositories are present in a single clique, while the remaining 13.3 M appear two times or more. On average, each repository appears in ≈ 1.47 cliques.

Computing the p-clique partition function using Algorithm 2 removes this overlap to allow a direct comparison with the forge fork networks. This algorithm takes a few minutes to process the 24 million cliques and returns the p-clique partition directly, restoring the invariant of total number of repositories (41.5 M).

There are 24.0 M of p-cliques partitioning the graph, which is pretty close to the number of forge fork networks in GitHub (25.3 M). 21.3 M repositories are isolated in their own p-clique (51.6%), and the remaining 48.4% are in cliques of size larger than one, which is consistent with the findings of Section 4.1 which uses fork networks as a quantification mechanism.

Figure 8 shows the cumulative frequency distribution of the sizes of the shared-commit fork cliques, compared to the baseline of forge fork networks. As before, the graph can be read as: "for each clique (resp. forge fork network) of size 𝑥, the number of repositories found in cliques (resp. networks) of size ≥ 𝑥".

The visual similarity between the two distributions is striking: while the shared-commit p-clique distribution seems to be consistently above the forge-fork network baseline for groups of size ≥ 2, they always appear to be very close to each other, even farther in the tail. This suggests that type 2 forks capture well what developers typically recognize as forks. To formally assess this similarity, the graph also exhibits the cumulative difference between the clique distribution and the baseline. This is in essence, the cumulative size distribution of the cliques of forks overlooked when using only the GitHub metadata. This cumulative distribution mostly stays positive, suggesting that using DVCS data to identify forks is overall a net gain in coverage. It also appears that the difference is typically at least one order of magnitude less than the size of the clusters, emphasizing the proximity between the two definitions.

1×10 -1 1×10 0 1×10 1 1×10 2 1×10 3 1×10 4 1×10 5 1×10 6 1×10 7 1×10 8 1×10 -1 1×10 0 1×10 1 1×10 2 1×10 3 1×10 4 1×10 5 1×10 6

Aggregation process

Two repositories having a common commit ancestor necessarily have a common root source tree (the root source tree of that common commit ancestor), so all the repositories that belong to the same shared-commit network also belong to the same shared-directory network. Similarly, we expect that most origins declared as forge forks will be in the same shared commit and shared root source tree fork networks. By switching from one definition to another, we expect the clusters to aggregate together smaller clusters from the previous definitions.

To characterize this aggregation process into fork clusters at different granularities, we compute the Kolmogorov-Smirnov (KS) distance between the weighted cumulative distributions function of the clique or network size.

We note 𝛿𝑂 the KS difference between a fork definition A and a fork definition B, and represent it as a function of the size of the network (or partitioned clique). By definition 𝛿𝑂 is always equal to zero for sizes 𝑠 = 1 (as all the forks are in clusters of size 𝑠 ≥ 1) and 𝑠 = max(cluster sizes) (as there are no clusters larger than this size).

Because the total number of repositories is invariant, we can plot the KS distance weighted by repositories to see how the repositories found in fork networks (or cliques) of a given size will progressively aggregate into fork networks (or cliques) of different sizes. Figure 9 represents 𝛿𝑂 between the forge fork definition baseline and: shared commit fork networks (top), shared commit p-cliques (bottom), and shared root tree fork networks (middle)). While this analysis shows the flux of repositories between clusters identified by the different definitions, it can mask some compensating phenomena by merging independent processes, as some repositories can migrate from larger to smaller clusters, sometimes leading to 𝛿𝑂 < 0 (Figure 9, bottom, 𝑠𝑖𝑧𝑒 ∼ 10 5 ). To narrow down this phenomenon, we specifically focus on the largest shared-commit fork network to see how it contributes to the global flux. By taking the repositories in this network and the size distribution of the forge fork networks, we show in Figure 10 the repository flux, as defined above, and compare it to the corresponding global flux.

Several points are noteworthy. First, only 15% (200 k origins over 1.53 M (red dotted)) of the origins that were isolated (blue dot for 𝑠𝑖𝑧𝑒 = 2) in forge fork network are aggregated in the giant network of shared commit fork. This shows that the aggregation mechanism is not only to this "giant" network, since ∼ 85% of the origins are aggregated within smaller networks.

Then, the flux for the 6 largest networks (isolated blue and orange dots around 10 5 that overlap) is almost the same whether we restrict ourselves to the origins of the giant network (orange line) or to all the networks (blue line). We conclude that aggregation for the large network sizes is dominated by absorption into the giant cluster, without any redistribution to smaller networks.

This confirms that the "aggregation/merge" mechanism which happens when changing the definition is not just an absorption phenomenon into a "super attractor", but concerns all network sizes, with larger networks absorbing networks of any size.

THREATS TO VALIDITY

Internal validity. Aside from forge forks (type 1) we have no certainty on how well the proposed fork definitions capture what developers would recognize as forks. While shared commit (type 2) and shared root (type 3) forks make intuitive sense, the sheer volume of data to be analyzed makes it very hard to rule out the existence of pathological cases. Certainly type 2 and type 3 fork definitions can be "gamed", making unrelated repositories appear as forks when they intuitively are not. Unusual development workflows might also induce topology in the global development graph that merge together repositories that would not be considered forks by developers. There exists an apparent trade-off here between fully automatable definitions based on VCS artifact sharing, and qualitative assessment by developers that does not scale to datasets like the one studied here.

Also as a consequence of the above we do not feel confident at this stage in making a methodological judgment call on whether type 2 or type 3 fork definitions "better" capture the essence of a fork. We simply warn scholars about the extent of the discrepancies between the number of forks detectable via shared VCS artifacts and forge-level metadata. Further work, of both statistical nature (looking for outliers) and based on structured interviews with developers (to review uncommon cases), is needed to improve over this point.

External validity. The datasets used in this study do not capture the full extent of publicly available development history, notably due to their snapshot nature and their assembly through periodic crawling processes. The Software Heritage Graph Dataset only contains data from various forges to the extent of what is covered by the Software Heritage archive, which might lag behind the tracked forges, and GHTorrent is GitHub-specific. As we need comparable samples we were limited by the intersection of the two datasets in this study, which composes these limitations. Still, to the best of our knowledge this is one of the largest quantitative fork study to date, having considered more than 40 M public version control system repositories.

In the future it would be interesting to extend this approach to forges that are raising in popularity, and most notably GitLab. For that we would need a GHTorrent equivalent (or corresponding ad hoc crawling of that forge for the purposes of the study only).

RELATED WORK

Accounts of the history of forking have been given by Nyman [START_REF] Nyman | Notes on the History of Fork and Join[END_REF] and Zhou et al. [START_REF] Zhou | What the fork: a study of inefficient and efficient forking practices in social coding[END_REF]Section 2]. The latter also covers the terminological and cultural shift from hard forks (to be avoided) to forking as the mere technical act of duplicating VCS history, possibly as basis for future collaboration. The present work is agnostic to which interpretation prevails, as in both cases the main observable effect of forking are VCS repositories that share parts of an initially common development history.

Hard forks. Hard forks have been studied extensively in seminal work by Nyman [START_REF] Nyman | Hackers on Forking[END_REF][START_REF] Nyman | Notes on the History of Fork and Join[END_REF][START_REF] Nyman | To Fork or Not to Fork: Fork Motivations in SourceForge Projects[END_REF][START_REF] Nyman | Perspectives on Code Forking and Sustainability in Open Source Software[END_REF], covering historical origins, motivations for forking (or not), and sustainability considerations in the socioeconomic context of free/open source software (FOSS) development. Robles and Barahona [START_REF] Robles | A Comprehensive Study of Software Forks: Dates, Reasons and Outcomes[END_REF] give a detailed account of famous hard forks, covering history, reasons, and outcomes.

These and other studies of hard forks are qualitative and focused in nature. This paper is complementary to them as it proposes tools to identify and quantitatively measure and observe forks, addressing the need of more extensive and homogeneous fork research already observed in [START_REF] Robles | A Comprehensive Study of Software Forks: Dates, Reasons and Outcomes[END_REF]. As far as we could determine without fully replicating the corresponding studies, the VCS repositories involved in the hard fork cases cited thus far would be correctly identified as either type 2 or type 3 forks.

Development forks.

With the advent of DVCS and social coding [START_REF] Lima | Coding together at scale: GitHub as a collaborative social network[END_REF], a significant amount of empirical research has been devoted to development forks. Motivations for forking on GitHub have been studied by Jiang et al. [START_REF] Jiang | Why and how developers fork what from whom in GitHub[END_REF].

The structure of forks on GitHub has been analyzed in several studies. Thung et al. [START_REF] Thung | Network structure of social coding in GitHub[END_REF] have characterized the network structure of social coding of GitHub, including forks. Padhye [START_REF] Rohan Padhye | A study of external community contribution to open-source projects on GitHub[END_REF] have measured external contributions from non-core developers. Biazzini and Baudry have proposed metrics to quantify and classify collaboration in GitHub repositories pertaining to the same fork tree [START_REF] Biazzini | May the fork be with you: novel metrics to analyze collaboration on GitHub[END_REF]. Rastogi and Nagappan [START_REF] Rastogi | Forking and the Sustainability of the Developer Community Participation-An Empirical Investigation on Outcomes and Reasons[END_REF]-as well as Stanciulescu et al. [START_REF] Stanciulescu | Forked and integrated variants in an open-source firmware project[END_REF] for firmware projects-have characterized forks on GitHub based on the flow of commits between them and the originating repository.

Various performance aspects of the pull request development model [START_REF] Gousios | An exploratory study of the pull-based software development model[END_REF][START_REF] Gousios | Work practices and challenges in pull-based development: the integrator's perspective[END_REF] have been also studied. Latency in acceptance has been a popular one [START_REF] Tsay | Influence of social and technical factors for evaluating contribution in GitHub[END_REF][START_REF] Yu | Wait for it: determinants of pull request evaluation latency on GitHub[END_REF]; the amount of generated community engagement [START_REF] Dabbish | Leveraging transparency[END_REF][START_REF] Dabbish | Social coding in GitHub: transparency and collaboration in an open software repository[END_REF] another one. A more general accounting of efficient forking patterns has recently been given by Zhou et al. [START_REF] Zhou | What the fork: a study of inefficient and efficient forking practices in social coding[END_REF].

To the extent we could determine it without full replication, all aforementioned studies on forking for social coding purposes rely on platform (and more specifically GitHub's) metadata to determine which repository is a fork (of which other). As such, involved repositories would be recognized as type 1 forks, and non type 1 forks (but nonetheless type 2 or 3 forks) might have been overlooked in the studies. To be clear: we have no reason to believe that the findings in those studies would turn out to be different by enlarging the set of considered forks using the alternative definitions. We simply propose to acknowledge fork type discrepancy as an internal validity threat in future studies.

Fork definitions. Aside from the already discussed hard forks v. development forks distinction, the only other work we are aware of on formal or semi-formal fork characterization is [START_REF] Rousseau | Growth and Duplication of Public Source Code over Time: Provenance Tracking at Scale[END_REF], which introduces the notion of most fit fork: a repository that, within a group of VCS repositories that share commits, contain the largest number of commits. The notion is proposed as a long-term approximation of the main development line of a forked (hardly or otherwise) project. Our notion of type 2 fork clique captures the same idea; additionally we show how to use it to partition the global set of VCS repositories into independent clusters instead of partitioning the global set of commits.

Methodology. Methodological issues and risks in analyzing GitHub were pointed out by Kalliamvakou et al. [START_REF] Kalliamvakou | The promises and perils of mining GitHub[END_REF]. While not directly addressed as an explicit risk, forks not recognized as such are echoed by perils "I: A repository is not necessarily a project" and "IX: Many active projects do not conduct all their software development in GitHub" in that article. Proposed mitigations were, respectively, "consider the activity in both the base repository and all associated forked repositories" and "Avoid projects that have a high number of committers who are not registered GitHub users and projects which explicitly state that they are mirrors in their description".

Half a decade later it is arguably less of a risk that development happens elsewhere and that a high number of committers are not registered GitHub users (due to the current marked dominance of GitHub). But it is still not zero and might be about to increase again due to push back against centralized services among FOSS developers. In this paper we provide methodological tools and improve upon the mitigation techniques proposed back then. Instead of avoiding projects, one can start from cross-platform datasets [START_REF] Abramatic | Building the Universal Archive of Source Code[END_REF][START_REF] Ma | World of code: an infrastructure for mining the universe of open source VCS data[END_REF][START_REF] Pietri | The Software Heritage graph dataset: public software development under one roof[END_REF][START_REF] Rousseau | Growth and Duplication of Public Source Code over Time: Provenance Tracking at Scale[END_REF] and measure the amount of shared VCS artifacts in the available repositories.

CONCLUSION

When relying only on forge-specific features and metadata to identify forked repositories, empirical studies on software forks might incur into selection and methodological biases. This is because repository forking can happen exogenously to any specific code hosting platform and out of band, especially when using distributed version control system (DVCS), which are currently very popular among developers.

To mitigate these risks we proposed two different ways to identify software forks solely based on intrinsic VCS data and development history: a shared commit forks (type 2) and a shared root directory forks (type 3) definition of software forks, as opposed to forge forks (type 1) which are identifiable only when created on specific code hosting platforms by, e.g., clicking on a "fork" UI element. We also introduced the notions of fork cliques (set of repositories that share parts of a common development history) and fork networks (repositories linked together by pairwise fork relationships) as ways to understand and quantify larger sets of forks when using non-transitive definitions of forking.

Via empirical analysis of 40+ M repositories using the GHTorrent and Software Heritage datasets we quantified the amount of type 2 and type 3 forks that are not recognizable as type 1 forks on GitHub, which appears to be substantial: +9% forks for type 2 forks, +37% more for type 3.

We also showed that the aggregation/merge dynamics into larger clusters of related repositories upon changing fork definitions is not just an absorption phenomenon into a "super attractor" cluster, but that it concerns all clusters: smaller ones are absorbed into larger ones of any size.

The methodological implications of our findings are that:

• Empirical software engineering studies on software forks aiming to be exhaustive in their coverage of forked repositories should consider using fork definitions based on shared VCS history rather than trusting forge-specific metadata. • Depending on the research question at hand, the objects of studies to consider when looking at repositories involved in forks are either fork networks or fork cliques. The latter have the advantage of excluding cases that exist in the wild (e.g., on GitHub) in which repositories that do not share VCS artifacts might end up in the same fork network due to transitiveness. • Any set of repositories can be partitioned in accordance with its relevant shared commit fork cliques by computing its fork p-clique partition function. This way of grouping together repositories that are all type 2 forks of each other is easily substitutable to partition approaches based on forge fork metadata.

Figure 1 :Figure 2 :

 12 Figure 1: Type 1 forks, or forge forks, as declared on code hosting platforms. Repository 𝐵 is a forge fork of 𝐴, 𝐶 and 𝐷 are forge fork of 𝐵, 𝐹 of 𝐸, while no repository is a forge fork of 𝐺. Note how this definition induces a global, directed, forge fork graph (specifically: a forest of disjoint trees).

Figure 3 :

 3 Figure 3: Type 3 fork, or shared root fork. Repository 𝐴 is a fork of 𝐵 and vice versa, since they share root directory 1. As per shared commit forks, type shared root forks are symmetric.

Figure 4 :

 4 Figure 4: The Software Heritage Graph Dataset data model

Figure 5 :

 5 Figure5: Fork networks identified as connected components, for the case of shared commit (type 2) forks. Connected components are computed on the undirected version of the shown Merkle DAG. Measuring network sizes as the number of contained repository nodes we obtain that: repositories A and B are forks of each other and members of a network of size 2, while repository C is in its own singleton network.

Figure 6 :

 6 Figure 6: Example of misleading clustering of fork networks.Here, repositories A and C are in the same network because there is a path between them, even though they do not share common development history.

Figure 7 :

 7 Figure 7: Cumulative frequency distribution of fork network sizes

Figure 8 :

 8 Figure 8: Cumulative frequency distribution of intrinsic fork p-cliques compared to forge fork networks

Figure 9 :

 9 Figure 9: Complementary Cumulative Weighted Distribution Functions Differences between forge fork network and shared-commit fork network (top), shared root source tree fork network (middle), and p-cliques based fork network (bottom).

  forge fork -shared commit fork O: restricted to the giant network Size of the giant network Difference of isolated origins

Figure 10 :

 10 Figure 10: Contribution (orange dots) of the giant (largest) network that appear using shared commit fork definition w.r.t. 𝜹𝑶 : forge forkshared commit fork (Same as Fig. 9, Top)

  Algorithm 1 Find all the fork cliques 𝑆 𝐹 ← empty set 𝑆 𝐶 ← empty set for all 𝑛 ∈ 𝐺 do if type(𝑛) = REVISION and 𝑛 has no parents then 𝑐 ← FindOriginLeaves(𝑛) 𝑓 𝑐 ← Fingerprint(𝑐) if 𝑓 𝑐 ̸ ∈ 𝑆 𝐹 then add 𝑓 𝑐 to 𝑆 𝐹 add 𝑐 to 𝑆 𝐶

	function FindOriginLeaves(r)
	𝑆 𝑂 ← empty set
	for all 𝑛 ∈ AncestorsDFS(𝑟 ) do
	if type(n) = ORIGIN then
	add 𝑛 to 𝑆 𝑂
	end if
	end for
	return 𝑆 𝑂
	end function
	function FindCliqes(𝐺)
	end if
	end if
	end for
	return 𝑆 𝐶
	end function

  Algorithm 2 Compute the p-cliques partition function function CliqesToPartition(𝐿 𝐶 ) ReverseSizeSort(𝐿 𝐶 ) ⊲ Process larger cliques first 𝐼 ← empty map ⊲ Build reverse index for all 𝑐 𝑖 ∈ 𝐿 𝐶 do add {𝑖 → 𝑐 𝑖 } to 𝐼 end for for all 𝑐 𝑖 ∈ 𝐿 𝐶 do for all 𝑟 𝑗 ∈ 𝑐 𝑖 do for all 𝑠 ∈ 𝐼 [𝑟 𝑗 ] do

		⊲ Remove subsequent
	if 𝑘 > 𝑖 then	occurrences of 𝑟 𝑗
	remove 𝑟 𝑗 from 𝑠
	end if
	end for
	end for
	end for
	𝐿 𝐶 ← RemoveEmptySets(𝐿 𝐶 ) ⊲ Remove cliques left empty
	return 𝐿 𝐶
	end function

Table 1 :

 1 Number of forks and networks by fork type

	Fork type	# forks	# networks
	Forge forks (type 1)	18.5 M (44.7%)	25.3 M
	Shared commit forks (type 2) 20.1 M (48.4%)	24.0 M
	Shared root forks (type 3)	25.3 M (61.1%)	18.5 M
	Cumulative frequency (network size ≤ x)	1×10 0 1×10 1 1×10 2 1×10 3 1×10 4 1×10 5 1×10 6 1×10 7 1×10 8	Forge forks Intrinsic shared commit forks Intrinsic shared root tree forks
		1×10 -1 1×10 -1 1×10 0 1×10 1 1×10 2 1×10 3 1×10 4 1×10 5 1×10 6 1×10 7
			Network size

https://developer.github.com/v3/repos/, retrieved

2020-01-13. 2 https://docs.gitlab.com/ee/api/projects.html, retrieved 2020-01-13

Additional URL gymnastic is needed in the query to cross-reference GHTorrent project URLs with Software Heritage ones; we refer to the replication package for this kind of details.

ACKNOWLEDGMENTS

The authors would like to thank Théo Zimmermann for his careful review and comments on an early version of this paper.


Antoine Pietri
email: antoine.pietri@inria.fr

Diomidis Spinellis

Stefano Zacchiroli

The Software Heritage Graph Dataset: Large-scale Analysis of Public Software Development History

published or not. The documents may come

INTRODUCTION

Analyses of software development history have historically focused on crawling specific "forges" [START_REF] Squire | The Lives and Deaths of Open Source Code Forges[END_REF] such as GitHub or GitLab, or language specific package managers [START_REF] Abate | Mining Component Repositories for Installability Issues[END_REF][START_REF] Kikas | Structure and evolution of package dependency networks[END_REF], usually by retrieving a selection of popular repositories ("most starred") and analyzing them individually. This approach has limitations in scope: (1) it works on subsets of the complete corpus of publicly available software, (2) it makes cross-repository history analysis hard, (3) it makes cross-VCS history analysis hard by not being VCS-agnostic.

The Software Heritage project [START_REF] Abramatic | Building the Universal Archive of Source Code[END_REF][START_REF] Di | Software Heritage: Why and How to Preserve Software Source Code[END_REF] aims to collect, preserve and share all the publicly available software source code, together with the associated development history as captured by modern VCSs [START_REF] Spinellis | Version control systems[END_REF]. In 2019, we presented the Software Heritage Graph Dataset, a graph representation of all the source code artifacts archived by Software Heritage [START_REF] Pietri | The Software Heritage Graph Dataset: Public software development under one roof[END_REF]. The graph is a fully deduplicated Merkle dag [START_REF] Ralph | A Digital Signature Based on a Conventional Encryption Function[END_REF] that contains the source code files, directories, commits and releases of all the repositories in the archive.

The dataset captures the state of the Software Heritage archive on September 25th 2018, spanning a full mirror of Github and GitLab.com, the Debian distribution, Gitorious, Google Code, and the PyPI repository. Quantitatively it corresponds to 5 billion unique file contents and 1.1 billion unique commits, harvested from more than 80 million software origins (see Section C for detailed figures).

We expect the dataset to significantly expand the scope of software analysis by lifting the restrictions outlined above: (1) it provides the best approximation of the entire corpus of publicly available software, (2) it blends together related development histories in a single data model, and (3) it abstracts over VCS and package differences, offering a canonical representation (see Section C) of source code artifacts.

RESEARCH QUESTIONS AND CHALLENGES

The dataset allows to tackle currently under-explored research questions, and presents interesting engineering challenges. There are different categories of research questions suited for this dataset.

• Coverage: Can known software mining experiments be replicated when taking the distribution tail into account? Is language detection possible on an unbounded number of languages, each file having potentially multiple extensions? Can generic tokenizers and code embedding analyzers [START_REF] Alon | Code2Vec: Learning Distributed Representations of Code[END_REF] be built without knowing their language a priori? • Graph structure: How tightly coupled are the different layers of the graph? What is the deduplication efficiency across different programming languages? When do contents or directories tend to be reused? • Cross-repository analysis: How can forking and duplication patterns inform us on software health and risks? How can community forks be distinguished from personal-use forks? What are good predictors of the success of a community fork? • Cross-origin analysis: Is software evolution consistent across different VCS? Are there VCS-specific development patterns? How does a migration from a VCS to another affect development patterns? Is there a relationship between development cycles and package manager releases?

The scale of the dataset makes tackling some questions also an engineering challenge: the sheer volume of data calls for distributed computation, while analyzing a graph of this size requires state of the art graph algorithms, being on the same order of magnitude as WebGraph [START_REF] Boldi | Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks[END_REF][START_REF] Boldi | The WebGraph Framework I: Compression Techniques[END_REF] in terms of edge and node count. Releases (or "tags") are revisions that have been marked as noteworthy with a specific, usually mnemonic, name (e.g., a version number). Each release points to a revision and might include additional descriptive metadata.

Snapshots are point-in-time captures of the full state of a project development repository. As revisions capture the state of a single development line (or "branch"), snapshots capture the state of all branches in a repository and allow to deduplicate unmodified forks across the archive.

Deduplication happens implicitly, automatically tracking byteidentical clones. If a file or a directory is copied to another project, both projects will point to the same node in the graph. Similarly for revisions, if a project is forked on a different hosting platform, the past development history will be deduplicated as the same nodes in the graph. Likewise for snapshots, each "fork" that creates an identical copy of a repository on a code host, will point to the same snapshot node. By walking the graph bottom-up, it is hence possible to find all occurrences of a source code artifact in the archive (e.g., all projects that have ever shipped a specific file content).

The Merkle dag is encoded in the dataset as a set of relational tables. In addition to the nodes and edges of the graph, the dataset also contains crawling information, as a set of triples capturing where (an origin url) and when (a timestamp) a given snapshot has been encountered. A simplified view of the corresponding database schema is shown in Figure 3; the full schema is available as part of the dataset distribution. Listing 1 shows a simple query that finds the most frequent file name across all the revisions. The result, obtained by scanning 151gb in 3 ′ 40 ′′ , is index.html, which occurs in the dataset 182 million times. As an example of a query useful in software evolution research, consider the Listing 2. It is based on the convention dictating that commit messages should start with a summary expressed in the imperative mood [13, 3.3.2.1]. Based on that idea, the query uses a regular expression to extract the first word of each commit message and then tallies words by frequency. By scanning 37 gb in 30 ′′ it gives us that commits concern the following common actions ordered by descending order of frequency: add, fix, update, remove, merge, initial, create.

sql queries can also be used to express more complex tasks. Consider the research hypothesis that weekend work on open source projects is decreasing over the years as evermore development work is done by companies rather than volunteers. The corresponding data can be obtained by finding the ratio between revisions committed on the weekends of each year and the total number of that year's revisions (see Listing 3). The results, obtained by scanning 14 gb in 7 ′′ are inconclusive, and point to the need for further analysis.

Figure 2 :

 2 Figure 2: Data model: a uniform Merkle DAG containing source code artifacts and their development history

Listing 2 :

 2 Most common commit operations SELECT COUNT (*) AS c , word FROM ( SELECT LOWER ( REGEXP_EXTRACT ( FROM_UTF8 ( message ), '^\ w+ ' )) AS word FROM revision ) WHERE word != '' GROUP BY word ORDER BY COUNT (*) DESC LIMIT 20;

Listing 4 :

 4 Average number of a revision's parents SELECT AVG ( fork_size ) FROM ( SELECT COUNT (*) AS fork_size FROM revision_history GROUP BY parent_id );

  Simplified schema of the Software Heritage Graph Dataset and the number of artifacts in it Appendix D SAMPLE SQL QUERIES To further illustrate the dataset's affordances and as motivating examples regarding the research possibilities it opens, below are some sample sql queries that can be executed with the dataset on aws Athena.

	releases			revisions
	author comment bytea bigint name bytea release id sha1_git target sha1_git date timestamp	revision_history sha1_git parent_id id sha1_git parent_rank integer	revision sha1_git timestamp committer_date timestamp id date directory message author committer bigint bigint bytea sha1_git	id bigserial person
		snapshots			directories
			snapshot_branch			directory_entry_rev
			object_id	bigserial			id	bigserial
			name	bytea			target sha1_git
	snapshot_branches snapshot_id bigint	target target_type snapshot_target bytea			name unix_path perms file_perms
	branch_id	bigint				directory
			snapshot object_id bigserial		id dir_entries bigint[] sha1_git	directory_entry_dir id bigserial	content
			id	sha1_git		rev_entries bigint[] file_entries bigint[]	name unix_path target sha1_git	content
		origins					perms file_perms	sha1_git sha1_git sha1 sha1
								length	bigint
	origin_visit		origin			directory_entry_file
	origin visit	bigint bigint	id type text bigserial			id target sha1_git bigserial	skipped_content
	date	timestamp	url	text			name unix_path	sha1	sha1
	snapshot_id bigint					perms file_perms	sha1_git sha1_git
								length	bigint
	Figure 3: Listing 1: Most frequent file name
	SELECT FROM_UTF8 ( name , '? ') AS name ,
	COUNT ( DISTINCT target ) AS cnt
	FROM directory_entry_file
	GROUP BY name
	ORDER BY cnt DESC
	LIMIT 1;

  Listing 3: Ratio of commits performed during each year's weekends

WITH revision_date AS ( SELECT FROM_UNIXTIME ( date / 1000000) AS date FROM revision ) SELECT yearly_rev.year AS year , CAST ( yearly_weekend_rev.number AS DOUBLE ) / yearly_rev.number * 100.0 AS weekend_pc FROM ( SELECT YEAR ( date ) AS year , COUNT (*) AS number FROM revision_date WHERE YEAR ( date ) BETWEEN 1971 AND 2018 GROUP BY YEAR ( date ) ) AS yearly_rev JOIN ( SELECT YEAR ( date ) AS year , COUNT (*) AS number FROM revision_date WHERE DAY_OF_WEEK ( date ) >= 6 AND YEAR ( date ) BETWEEN 1971 AND 2018 GROUP BY YEAR ( date ) ) AS yearly_weekend_rev ON yearly_rev.year = yearly_weekend_rev.year ORDER BY year DESC;

https://archive.softwareheritage.org/api/

Appendix A FIGURES

The dataset contains more than 11B software artifacts, as shown in Figure 1.

Appendix B AVAILABILITY

The dataset is available for download from Zenodo [START_REF] Pietri | The Software Heritage Graph Dataset: Public software development under one roof[END_REF] in two different formats (≈1 tb each):

• a Postgres [START_REF] Stonebraker | The POSTGRES next generation database management system[END_REF] database dump in csv format (for the data) and ddl queries (for recreating the DB schema), suitable for local processing on a single server; • a set of Apache Parquet files [START_REF]Apache Parquet[END_REF] suitable for loading into columnar storage and scale-out processing solutions, e.g., Apache Spark [START_REF] Zaharia | Apache Spark: a unified engine for big data processing[END_REF]. In addition, the dataset is ready to use on two different distributed cloud platforms for live usage:

• on Amazon Athena, [1] which uses PrestoDB to distribute SQL queries. • on Azure Databricks; [START_REF]Azure Databricks[END_REF] which runs Apache Spark and can be queried in Python, Scala or Spark SQL.

Appendix C DATA MODEL

The Software Heritage Graph Dataset exploits the fact that source code artifacts are massively duplicated across hosts and projects [START_REF] Di | Software Heritage: Why and How to Preserve Software Source Code[END_REF] to enable tracking of software artifacts across projects, and reduce the storage size of the graph. This is achieved by storing the graph as a Merkle directed acyclic graph (DAG) [START_REF] Ralph | A Digital Signature Based on a Conventional Encryption Function[END_REF]. By using persistent, cryptographically-strong hashes as node identifiers [START_REF] Di | Identifiers for Digital Objects: the Case of Software Source Code Preservation[END_REF], the graph is deduplicated by sharing all identical nodes. As shown in Figure 2, the Software Heritage DAG is organized in five logical layers, which we describe from bottom to top.

Contents (or "blobs") form the graph's leaves, and contain the raw content of source code files, not including their filenames (which are context-dependent and stored only as part of directory entries). The dataset contains cryptographic checksums for all contents though, that can be used to retrieve the actual files from any Software Heritage mirror using a Web api 1 and cross-reference files encountered in the wild, including other datasets.

Directories are lists of named directory entries. Each entry can point to content objects ("file entries"), revisions ("revision entries"), or other directories ("directory entries").

Revisions (or "commits") are point-in-time captures of the entire source tree of a development project. Each revision points to the root directory of the project source tree, and a list of its parent revisions. The provided dataset forms a graph, which can be difficult query with sql. Therefore, questions associated with the graph's characteristics, such as closeness, distance, and centrality, will require the use of other methods, like Spark (see Section E). Yet, interesting metrics can be readily obtained by limiting scans to specific cases, such as merge commits. As an example, Listing 4 calculates the average number of parents of each revision (1.088, after scanning 23 gb in 22 ′′ ) by grouping revisions by their parent identifier. Such queries can be used to examine in depth the characteristics of merge operations.

Although the performance of Athena can be impressive, there are cases where the available memory resources will be exhausted causing an expensive query to fail. This typically happens when joining two equally large tables consisting of hundreds of millions of records. This restriction can be overcome by sampling the corresponding tables. Listing 5 demonstrates such a case. The objective here is to determine the modularity at the level of files among diverse programming languages, by examining the size of popular file types. The query joins two 5 billion row tables: the file names and the content metadata. To reduce the number of joined rows a 1% sample of the rows is processed, thus scanning 317 gb in 1 ′ 20 ′′ . The order of the resulting language files (JavaScript>C>C++>Python>php>C#> Ruby) hints that, with the exception of JavaScript, languages offering more abstraction facilities are associated with smaller source code files.

Appendix E SPARK USAGE

For a more fine-grained control of the computing resources, it is also possible to use the dataset on Spark, through a local install or using the public dataset on Azure Databricks.

Once the tables are loaded in Spark, the query in Listing 6 can be used to generate an outdegree distribution of the directories. To analyze the graph structure, the GraphFrames library [START_REF] Dave | Graphframes: an integrated api for mixing graph and relational queries[END_REF] can also be used to perform common operations on the graph. Listing 7 demonstrates how one can load the edges and nodes of the revision tables as a GraphFrame object, then compute the distribution of the connected component sizes in this graph.

Listing 7: Connected components of the revision graph from graphframes import GraphFrame revision_nodes = spark . sql (" SELECT id FROM revision ") revision_edges = spark . sql (" SELECT id as src , parent_id as dst " " FROM revision_history ") revision_graph = GraphFrame ( revision_nodes , revision_edges ) revision_cc = revision_graph . connectedComponents () distribution = ( revision_cc .

groupby ([ ' component ' ]). count () . withColumnRenamed ( ' count ', ' component_size ') . groupby ([ ' component_size ' ]). count ()) display ( distribution )

By allowing users to choose the amount of resources in the cluster, Spark lifts the constraints imposed by limits in Athena, such as timeouts and limited scale-out factor. This is important for computationally intensive experiments or very large join operations, which can only be achieved through sampling in Athena.

Spark is also more flexible in terms of the computations it can perform, thanks to User-Defined Functions [START_REF]User-Defined Functions (UDFs) • The Internals of Spark SQL[END_REF] that can be used to specify arbitrary operations to be performed on the rows, which isn't possible with Athena.

Appendix F DATA SAMPLE

A sample of the data as well as instructions to run live queries on the dataset using Amazon Athena can be found at: https://annex. softwareheritage.org/public/dataset/graph/2018-09-25/