From patchwork Tue Oct 8 14:11:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826556 Received: from mail-lf1-f54.google.com (mail-lf1-f54.google.com [209.85.167.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 339BC16BE2A for ; Tue, 8 Oct 2024 14:12:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396731; cv=none; b=YpFKPxpFc/mScUawLTBrV9722p9bN7Z2WDP01o7wiXs/FEhchXOLAksHwb1JBsyyg/y9vIJFgniXfhDWXUY5j17KPGbN/uvuuWHfwocx4UalykCmLGN+8NJsJCWYyvXog3n9idrW5GVMa7qs5PbWfIHWdm0cIHVAhmNTOUIe7cE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396731; c=relaxed/simple; bh=3RFrCpMyIeHwWLPS6FhFaejRqzgyAuxob4aFUYg9mHg=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=lL5nWaZkNTgitEMfEXHNc2XttJ56Bbv3c2FtT2VZ3EFXVlP/S1hLz78hb/dil17mzke/QGqOlzkdkx/IGFLfg3T3gmRjKmuuIs+rbrE73koMQfyYxCT7PWqE/oyPyomIIZM24cMo48JcRy3RdKyspgwDpNNzX8SQTjs/ifhN5Mo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=A64xFwFr; arc=none smtp.client-ip=209.85.167.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="A64xFwFr" Received: by mail-lf1-f54.google.com with SMTP id 2adb3069b0e04-539973829e7so5703139e87.0 for ; Tue, 08 Oct 2024 07:12:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396727; x=1729001527; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=iVcW7vVL9aO5GkPyipqtIhpIRCh8ACMxU0E0nCA63JA=; b=A64xFwFrWjuoW9OEoeKEqQhWf9AOHQlHn4rKchlylxmGPvvH/O0+JQGAb635gSR5vU QJWaxs7JFfbWP+w9jwYaDHyHDliWY0XqDtP31W4IfrEb6qCAlpZu12BXdTj2/pGDbvu3 wA/9gG5XToUDgjughHsYH67oeBmgvbLgtlEVBTt/LSUJ6GcBefvYJvPAdeq2n44tO04p EM8bvwXOvL5mms356WO+2eFDCnfK4/pb+bPONo9z4oG1IdQvVzxy2rVMagk5n2k6Az7k Fwl5Ue6IMV6Oa5PPMhbVwa8uyc2uRSfin3oGRWCQrrl5KQjTPZk6k0kWG7HVTBAFRGZm kZDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396727; x=1729001527; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=iVcW7vVL9aO5GkPyipqtIhpIRCh8ACMxU0E0nCA63JA=; b=QqEYRLPNd336ukiCjy2T1l92AFs5VZp+KG0HEUxZBt0OtUYPEKPMrp4+cFYtcUMOmU jYwMEuoSzWpFS7EZ3A0e+KrfNXuPLugO3E8GrSGkEIl9BSsQB7G1AqrpvJberpsNUxAx OK8fBVgVXx/mbiuHn3aV2zvgtHy2x9z6sc5uCcF2igMaZJ96IpNUiJ3EzPVVFs//uJjC vrOVy9lbniKNaKJMn8AtxvdOl8sMnJ1y621g8OPEVhsA0pYUb1hEzgvjXf9rwHfsxSse pS5NVI710Vz1qrThvc8UjAKP2efcVL3i821i37K46lf3izc/dGjhuNEd3L7lt6LSHsTe mzUg== X-Gm-Message-State: AOJu0YzlIIqnfAZg5nbMAVeE4yBuiyYGgDLArxbAZwvAF+jVrE/6uMLE Od9mrebEJLVBPQDou7zNLodSPiDxkQLswD8S64+43v6/hxFz54P4x/TvgQ== X-Google-Smtp-Source: AGHT+IGN2NDwUWsZGxysW6//x8EDVoZbsEDQPEPt9Qzo02UdDJfZCKf+wpJ65mOTImxg7LH96yn5Kg== X-Received: by 2002:a05:6512:23a0:b0:530:ae22:a6f0 with SMTP id 2adb3069b0e04-539ab84e575mr8366453e87.5.1728396726220; Tue, 08 Oct 2024 07:12:06 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a992e784012sm514024766b.109.2024.10.08.07.12.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:05 -0700 (PDT) Message-Id: <98bdc94a773d797152bebfbfda88fa1bb0707821.1728396724.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:47 +0000 Subject: [PATCH 01/17] path-walk: introduce an object walk by path Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee In anticipation of a few planned applications, introduce the most basic form of a path-walk API. It currently assumes that there are no UNINTERESTING objects and does not include any complicated filters. It calls a function pointer on groups of tree and blob objects as grouped by path. This only includes objects the first time they are discovered, so an object that appears at multiple paths will not be included in two batches. There are many future adaptations that could be made, but they are left for future updates when consumers are ready to take advantage of those features. Signed-off-by: Derrick Stolee --- Documentation/technical/api-path-walk.txt | 54 +++++ Makefile | 1 + path-walk.c | 241 ++++++++++++++++++++++ path-walk.h | 43 ++++ 4 files changed, 339 insertions(+) create mode 100644 Documentation/technical/api-path-walk.txt create mode 100644 path-walk.c create mode 100644 path-walk.h diff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt new file mode 100644 index 00000000000..6472222ae6d --- /dev/null +++ b/Documentation/technical/api-path-walk.txt @@ -0,0 +1,54 @@ +Path-Walk API +============= + +The path-walk API is used to walk reachable objects, but to visit objects +in batches based on a common path they appear in, or by type. + +For example, all reachable commits are visited in a group. All tags are +visited in a group. Then, all root trees are visited. At some point, all +blobs reachable via a path `my/dir/to/A` are visited. When there are +multiple paths possible to reach the same object, then only one of those +paths is used to visit the object. + +When walking a range of commits with some `UNINTERESTING` objects, the +objects with the `UNINTERESTING` flag are included in these batches. In +order to walk `UNINTERESTING` objects, the `--boundary` option must be +used in the commit walk in order to visit `UNINTERESTING` commits. + +Basics +------ + +To use the path-walk API, include `path-walk.h` and call +`walk_objects_by_path()` with a customized `path_walk_info` struct. The +struct is used to set all of the options for how the walk should proceed. +Let's dig into the different options and their use. + +`path_fn` and `path_fn_data`:: + The most important option is the `path_fn` option, which is a + function pointer to the callback that can execute logic on the + object IDs for objects grouped by type and path. This function + also receives a `data` value that corresponds to the + `path_fn_data` member, for providing custom data structures to + this callback function. + +`revs`:: + To configure the exact details of the reachable set of objects, + use the `revs` member and initialize it using the revision + machinery in `revision.h`. Initialize `revs` using calls such as + `setup_revisions()` or `parse_revision_opt()`. Do not call + `prepare_revision_walk()`, as that will be called within + `walk_objects_by_path()`. ++ +It is also important that you do not specify the `--objects` flag for the +`revs` struct. The revision walk should only be used to walk commits, and +the objects will be walked in a separate way based on those starting +commits. ++ +If you want the path-walk API to emit `UNINTERESTING` objects based on the +commit walk's boundary, be sure to set `revs.boundary` so the boundary +commits are emitted. + +Examples +-------- + +See example usages in future changes. diff --git a/Makefile b/Makefile index 7344a7f7257..d0d8d6888e3 100644 --- a/Makefile +++ b/Makefile @@ -1094,6 +1094,7 @@ LIB_OBJS += parse-options.o LIB_OBJS += patch-delta.o LIB_OBJS += patch-ids.o LIB_OBJS += path.o +LIB_OBJS += path-walk.o LIB_OBJS += pathspec.o LIB_OBJS += pkt-line.o LIB_OBJS += preload-index.o diff --git a/path-walk.c b/path-walk.c new file mode 100644 index 00000000000..66840187e28 --- /dev/null +++ b/path-walk.c @@ -0,0 +1,241 @@ +/* + * path-walk.c: implementation for path-based walks of the object graph. + */ +#include "git-compat-util.h" +#include "path-walk.h" +#include "blob.h" +#include "commit.h" +#include "dir.h" +#include "hashmap.h" +#include "hex.h" +#include "object.h" +#include "oid-array.h" +#include "revision.h" +#include "string-list.h" +#include "strmap.h" +#include "trace2.h" +#include "tree.h" +#include "tree-walk.h" + +struct type_and_oid_list +{ + enum object_type type; + struct oid_array oids; +}; + +#define TYPE_AND_OID_LIST_INIT { \ + .type = OBJ_NONE, \ + .oids = OID_ARRAY_INIT \ +} + +struct path_walk_context { + /** + * Repeats of data in 'struct path_walk_info' for + * access with fewer characters. + */ + struct repository *repo; + struct rev_info *revs; + struct path_walk_info *info; + + /** + * Map a path to a 'struct type_and_oid_list' + * containing the objects discovered at that + * path. + */ + struct strmap paths_to_lists; + + /** + * Store the current list of paths in a stack, to + * facilitate depth-first-search without recursion. + */ + struct string_list path_stack; +}; + +static int add_children(struct path_walk_context *ctx, + const char *base_path, + struct object_id *oid) +{ + struct tree_desc desc; + struct name_entry entry; + struct strbuf path = STRBUF_INIT; + size_t base_len; + struct tree *tree = lookup_tree(ctx->repo, oid); + + if (!tree) { + error(_("failed to walk children of tree %s: not found"), + oid_to_hex(oid)); + return -1; + } else if (parse_tree_gently(tree, 1)) { + die("bad tree object %s", oid_to_hex(oid)); + } + + strbuf_addstr(&path, base_path); + base_len = path.len; + + parse_tree(tree); + init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size); + while (tree_entry(&desc, &entry)) { + struct type_and_oid_list *list; + struct object *o; + /* Not actually true, but we will ignore submodules later. */ + enum object_type type = S_ISDIR(entry.mode) ? OBJ_TREE : OBJ_BLOB; + + /* Skip submodules. */ + if (S_ISGITLINK(entry.mode)) + continue; + + if (type == OBJ_TREE) { + struct tree *child = lookup_tree(ctx->repo, &entry.oid); + o = child ? &child->object : NULL; + } else if (type == OBJ_BLOB) { + struct blob *child = lookup_blob(ctx->repo, &entry.oid); + o = child ? &child->object : NULL; + } else { + /* Wrong type? */ + continue; + } + + if (!o) /* report error?*/ + continue; + + /* Skip this object if already seen. */ + if (o->flags & SEEN) + continue; + o->flags |= SEEN; + + strbuf_setlen(&path, base_len); + strbuf_add(&path, entry.path, entry.pathlen); + + /* + * Trees will end with "/" for concatenation and distinction + * from blobs at the same path. + */ + if (type == OBJ_TREE) + strbuf_addch(&path, '/'); + + if (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) { + CALLOC_ARRAY(list, 1); + list->type = type; + strmap_put(&ctx->paths_to_lists, path.buf, list); + string_list_append(&ctx->path_stack, path.buf); + } + oid_array_append(&list->oids, &entry.oid); + } + + free_tree_buffer(tree); + strbuf_release(&path); + return 0; +} + +/* + * For each path in paths_to_explore, walk the trees another level + * and add any found blobs to the batch (but only if they exist and + * haven't been added yet). + */ +static int walk_path(struct path_walk_context *ctx, + const char *path) +{ + struct type_and_oid_list *list; + int ret = 0; + + list = strmap_get(&ctx->paths_to_lists, path); + + /* Evaluate function pointer on this data. */ + ret = ctx->info->path_fn(path, &list->oids, list->type, + ctx->info->path_fn_data); + + /* Expand data for children. */ + if (list->type == OBJ_TREE) { + for (size_t i = 0; i < list->oids.nr; i++) { + ret |= add_children(ctx, + path, + &list->oids.oid[i]); + } + } + + oid_array_clear(&list->oids); + strmap_remove(&ctx->paths_to_lists, path, 1); + return ret; +} + +static void clear_strmap(struct strmap *map) +{ + struct hashmap_iter iter; + struct strmap_entry *e; + + hashmap_for_each_entry(&map->map, &iter, e, ent) { + struct type_and_oid_list *list = e->value; + oid_array_clear(&list->oids); + } + strmap_clear(map, 1); + strmap_init(map); +} + +/** + * Given the configuration of 'info', walk the commits based on 'info->revs' and + * call 'info->path_fn' on each discovered path. + * + * Returns nonzero on an error. + */ +int walk_objects_by_path(struct path_walk_info *info) +{ + const char *root_path = ""; + int ret = 0; + size_t commits_nr = 0, paths_nr = 0; + struct commit *c; + struct type_and_oid_list *root_tree_list; + struct path_walk_context ctx = { + .repo = info->revs->repo, + .revs = info->revs, + .info = info, + .path_stack = STRING_LIST_INIT_DUP, + .paths_to_lists = STRMAP_INIT + }; + + trace2_region_enter("path-walk", "commit-walk", info->revs->repo); + + /* Insert a single list for the root tree into the paths. */ + CALLOC_ARRAY(root_tree_list, 1); + root_tree_list->type = OBJ_TREE; + strmap_put(&ctx.paths_to_lists, root_path, root_tree_list); + + if (prepare_revision_walk(info->revs)) + die(_("failed to setup revision walk")); + + while ((c = get_revision(info->revs))) { + struct object_id *oid = get_commit_tree_oid(c); + struct tree *t = lookup_tree(info->revs->repo, oid); + commits_nr++; + + if (t) { + if (t->object.flags & SEEN) + continue; + t->object.flags |= SEEN; + oid_array_append(&root_tree_list->oids, oid); + } else { + warning("could not find tree %s", oid_to_hex(oid)); + } + } + + trace2_data_intmax("path-walk", ctx.repo, "commits", commits_nr); + trace2_region_leave("path-walk", "commit-walk", info->revs->repo); + + string_list_append(&ctx.path_stack, root_path); + + trace2_region_enter("path-walk", "path-walk", info->revs->repo); + while (!ret && ctx.path_stack.nr) { + char *path = ctx.path_stack.items[ctx.path_stack.nr - 1].string; + ctx.path_stack.nr--; + paths_nr++; + + ret = walk_path(&ctx, path); + + free(path); + } + trace2_data_intmax("path-walk", ctx.repo, "paths", paths_nr); + trace2_region_leave("path-walk", "path-walk", info->revs->repo); + + clear_strmap(&ctx.paths_to_lists); + string_list_clear(&ctx.path_stack, 0); + return ret; +} diff --git a/path-walk.h b/path-walk.h new file mode 100644 index 00000000000..c9e94a98bc8 --- /dev/null +++ b/path-walk.h @@ -0,0 +1,43 @@ +/* + * path-walk.h : Methods and structures for walking the object graph in batches + * by the paths that can reach those objects. + */ +#include "object.h" /* Required for 'enum object_type'. */ + +struct rev_info; +struct oid_array; + +/** + * The type of a function pointer for the method that is called on a list of + * objects reachable at a given path. + */ +typedef int (*path_fn)(const char *path, + struct oid_array *oids, + enum object_type type, + void *data); + +struct path_walk_info { + /** + * revs provides the definitions for the commit walk, including + * which commits are UNINTERESTING or not. + */ + struct rev_info *revs; + + /** + * The caller wishes to execute custom logic on objects reachable at a + * given path. Every reachable object will be visited exactly once, and + * the first path to see an object wins. This may not be a stable choice. + */ + path_fn path_fn; + void *path_fn_data; +}; + +#define PATH_WALK_INFO_INIT { 0 } + +/** + * Given the configuration of 'info', walk the commits based on 'info->revs' and + * call 'info->path_fn' on each discovered path. + * + * Returns nonzero on an error. + */ +int walk_objects_by_path(struct path_walk_info *info); From patchwork Tue Oct 8 14:11:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826557 Received: from mail-ed1-f45.google.com (mail-ed1-f45.google.com [209.85.208.45]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EBC4E1DF971 for ; Tue, 8 Oct 2024 14:12:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.45 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396731; cv=none; b=Qu6Onzlt4sq5f00UPj1eBvYguKs7P8im74YV70Sgk5pE1jYh1/dQf1G0rzDc1YPejn++gDqeeZ4iF3LjS8jae1mixNu4XMSdOQv4jkqfsY07Y2NaD4gSwvFnRsQ6Anl7jFDPtNll8NjptcjSc1LjBf61JzxhFvA2AJklKZAOoWY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396731; c=relaxed/simple; bh=+no2Fsg3ePTOblpujd50sIirScNQ4vEq4mZNIMf11zc=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=ewUnHAreR9WWBcm1ffVqmbJtOe5Zk9iSHtm47q/S2sV878wTOfHEga1lK+hnWLsdmIULCLXNs+LR8DU10Vf3t0ViFv8XL0+hj+Nxst/nsUzN6Douc4JXJNX90cef9VHVLrqLutZ4Na8LRwk8ig9By0Ci0z7RVSmWGu87WNaDhwQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lwlKMmhu; arc=none smtp.client-ip=209.85.208.45 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lwlKMmhu" Received: by mail-ed1-f45.google.com with SMTP id 4fb4d7f45d1cf-5c721803a89so7679588a12.1 for ; Tue, 08 Oct 2024 07:12:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396728; x=1729001528; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=Z8e37B+OfdvykHAq8461cA43BBv4rorwVpoDJOIItyw=; b=lwlKMmhu7DsH3OqXowNZ4o+6WboEudLz/4gGxTqi7bRCwFtytPkXzDBxcYycHfhO/s LovC+0KB5PdC4eg5ecyWwBKAOiVfB4ONlOoHsnbyyCsJn8pRXD17M1EWP9sJ04+9VGdl ge4eNmSqbbq3rwGbM1jIoc/lbDUNLq2bV62Gk6anzyi8IFj5I17tFotylPNK3O1cYYyM ADfN36je4lSSlzZ/RennwljbWZ1sHF0Gtz9HW/ISQYI/Jzb/l0UJl++1FVN1k1GJW+Wc 1LU0AW7KNFG4ECjWQTvKQRU8AEzojxCVag372vK6qPed6o1DBplRSb9/bKCQIgGmtex3 WoPw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396728; x=1729001528; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Z8e37B+OfdvykHAq8461cA43BBv4rorwVpoDJOIItyw=; b=adybQAKZyWwRGPDmBL0jTZQgoXNj5YAggZOk0KmHQ0+x3aidgmFH3AiY9JjfUKwyWa KaVP0ebVnX8aphZsu8viDOCaRvpGK0Ed5QOPt3/3QUm8MebNpFamW/1QTavP6C6EGQ8p R66rGLjP+CZy9qRIifhE+pL8JGVwb1oF//rWKQfykS3fWP2T7XqMmHBKSUhcom18cCmA s2OmFTTFFuuIAFfm5yeXzZfpZy6vpEU9SXBu9NF7ZNC85QCkqwHiWvJKMstf46o4+KGb 050n562fifKtgfRbanrLbeuZ5tTrwvUM1JFg9mPp3zjOT3Vq2ImXnkD75ddTRu1TR19/ 5NoQ== X-Gm-Message-State: AOJu0Yx1jwXXJMBNqeD3g7DjeSt7kci10VPivOgczWf/YGqmko22eob2 zzSt3qAudmH3xY1qZpQ4ghyC8Pl/CKQJKr1EeqOLzE/0UedpTyb+tYA9wA== X-Google-Smtp-Source: AGHT+IG00+ISIcjYgxbAaUp7K82/EE47P5755JKOCm11xYug3v7NUZG3iC4phSuMggoNREkZEIc05g== X-Received: by 2002:a05:6402:354f:b0:5c8:8626:e41 with SMTP id 4fb4d7f45d1cf-5c8d2d005c6mr10709526a12.4.1728396727366; Tue, 08 Oct 2024 07:12:07 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5c911978839sm384908a12.46.2024.10.08.07.12.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:06 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:48 +0000 Subject: [PATCH 02/17] t6601: add helper for testing path-walk API Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee Add some tests based on the current behavior, doing interesting checks for different sets of branches, ranges, and the --boundary option. This sets a baseline for the behavior and we can extend it as new options are introduced. Signed-off-by: Derrick Stolee --- Documentation/technical/api-path-walk.txt | 3 +- Makefile | 1 + t/helper/test-path-walk.c | 86 ++++++++++++++ t/helper/test-tool.c | 1 + t/helper/test-tool.h | 1 + t/t6601-path-walk.sh | 130 ++++++++++++++++++++++ 6 files changed, 221 insertions(+), 1 deletion(-) create mode 100644 t/helper/test-path-walk.c create mode 100755 t/t6601-path-walk.sh diff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt index 6472222ae6d..e588897ab8d 100644 --- a/Documentation/technical/api-path-walk.txt +++ b/Documentation/technical/api-path-walk.txt @@ -51,4 +51,5 @@ commits are emitted. Examples -------- -See example usages in future changes. +See example usages in: + `t/helper/test-path-walk.c` diff --git a/Makefile b/Makefile index d0d8d6888e3..50413d96492 100644 --- a/Makefile +++ b/Makefile @@ -818,6 +818,7 @@ TEST_BUILTINS_OBJS += test-parse-options.o TEST_BUILTINS_OBJS += test-parse-pathspec-file.o TEST_BUILTINS_OBJS += test-partial-clone.o TEST_BUILTINS_OBJS += test-path-utils.o +TEST_BUILTINS_OBJS += test-path-walk.o TEST_BUILTINS_OBJS += test-pcre2-config.o TEST_BUILTINS_OBJS += test-pkt-line.o TEST_BUILTINS_OBJS += test-proc-receive.o diff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c new file mode 100644 index 00000000000..3c48f017fa0 --- /dev/null +++ b/t/helper/test-path-walk.c @@ -0,0 +1,86 @@ +#define USE_THE_REPOSITORY_VARIABLE + +#include "test-tool.h" +#include "environment.h" +#include "hex.h" +#include "object-name.h" +#include "object.h" +#include "pretty.h" +#include "revision.h" +#include "setup.h" +#include "parse-options.h" +#include "path-walk.h" +#include "oid-array.h" + +static const char * const path_walk_usage[] = { + N_("test-tool path-walk -- "), + NULL +}; + +struct path_walk_test_data { + uintmax_t tree_nr; + uintmax_t blob_nr; +}; + +static int emit_block(const char *path, struct oid_array *oids, + enum object_type type, void *data) +{ + struct path_walk_test_data *tdata = data; + const char *typestr; + + switch (type) { + case OBJ_TREE: + typestr = "TREE"; + tdata->tree_nr += oids->nr; + break; + + case OBJ_BLOB: + typestr = "BLOB"; + tdata->blob_nr += oids->nr; + break; + + default: + BUG("we do not understand this type"); + } + + for (size_t i = 0; i < oids->nr; i++) + printf("%s:%s:%s\n", typestr, path, oid_to_hex(&oids->oid[i])); + + return 0; +} + +int cmd__path_walk(int argc, const char **argv) +{ + int res; + struct rev_info revs = REV_INFO_INIT; + struct path_walk_info info = PATH_WALK_INFO_INIT; + struct path_walk_test_data data = { 0 }; + struct option options[] = { + OPT_END(), + }; + + initialize_repository(the_repository); + setup_git_directory(); + revs.repo = the_repository; + + argc = parse_options(argc, argv, NULL, + options, path_walk_usage, + PARSE_OPT_KEEP_UNKNOWN_OPT | PARSE_OPT_KEEP_ARGV0); + + if (argc > 1) + setup_revisions(argc, argv, &revs, NULL); + else + usage(path_walk_usage[0]); + + info.revs = &revs; + info.path_fn = emit_block; + info.path_fn_data = &data; + + res = walk_objects_by_path(&info); + + printf("trees:%" PRIuMAX "\n" + "blobs:%" PRIuMAX "\n", + data.tree_nr, data.blob_nr); + + return res; +} diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c index 1ebb69a5dc4..43676e7b93a 100644 --- a/t/helper/test-tool.c +++ b/t/helper/test-tool.c @@ -52,6 +52,7 @@ static struct test_cmd cmds[] = { { "parse-subcommand", cmd__parse_subcommand }, { "partial-clone", cmd__partial_clone }, { "path-utils", cmd__path_utils }, + { "path-walk", cmd__path_walk }, { "pcre2-config", cmd__pcre2_config }, { "pkt-line", cmd__pkt_line }, { "proc-receive", cmd__proc_receive }, diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h index 21802ac27da..9cfc5da6e57 100644 --- a/t/helper/test-tool.h +++ b/t/helper/test-tool.h @@ -45,6 +45,7 @@ int cmd__parse_pathspec_file(int argc, const char** argv); int cmd__parse_subcommand(int argc, const char **argv); int cmd__partial_clone(int argc, const char **argv); int cmd__path_utils(int argc, const char **argv); +int cmd__path_walk(int argc, const char **argv); int cmd__pcre2_config(int argc, const char **argv); int cmd__pkt_line(int argc, const char **argv); int cmd__proc_receive(int argc, const char **argv); diff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh new file mode 100755 index 00000000000..ca18b61c3f1 --- /dev/null +++ b/t/t6601-path-walk.sh @@ -0,0 +1,130 @@ +#!/bin/sh + +test_description='direct path-walk API tests' + +. ./test-lib.sh + +test_expect_success 'setup test repository' ' + git checkout -b base && + + mkdir left && + mkdir right && + echo a >a && + echo b >left/b && + echo c >right/c && + git add . && + git commit -m "first" && + + echo d >right/d && + git add right && + git commit -m "second" && + + echo bb >left/b && + git commit -a -m "third" && + + git checkout -b topic HEAD~1 && + echo cc >right/c && + git commit -a -m "topic" +' + +test_expect_success 'all' ' + test-tool path-walk -- --all >out && + + cat >expect <<-EOF && + TREE::$(git rev-parse topic^{tree}) + TREE::$(git rev-parse base^{tree}) + TREE::$(git rev-parse base~1^{tree}) + TREE::$(git rev-parse base~2^{tree}) + TREE:left/:$(git rev-parse base:left) + TREE:left/:$(git rev-parse base~2:left) + TREE:right/:$(git rev-parse topic:right) + TREE:right/:$(git rev-parse base~1:right) + TREE:right/:$(git rev-parse base~2:right) + trees:9 + BLOB:a:$(git rev-parse base~2:a) + BLOB:left/b:$(git rev-parse base~2:left/b) + BLOB:left/b:$(git rev-parse base:left/b) + BLOB:right/c:$(git rev-parse base~2:right/c) + BLOB:right/c:$(git rev-parse topic:right/c) + BLOB:right/d:$(git rev-parse base~1:right/d) + blobs:6 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + +test_expect_success 'topic only' ' + test-tool path-walk -- topic >out && + + cat >expect <<-EOF && + TREE::$(git rev-parse topic^{tree}) + TREE::$(git rev-parse base~1^{tree}) + TREE::$(git rev-parse base~2^{tree}) + TREE:left/:$(git rev-parse base~2:left) + TREE:right/:$(git rev-parse topic:right) + TREE:right/:$(git rev-parse base~1:right) + TREE:right/:$(git rev-parse base~2:right) + trees:7 + BLOB:a:$(git rev-parse base~2:a) + BLOB:left/b:$(git rev-parse base~2:left/b) + BLOB:right/c:$(git rev-parse base~2:right/c) + BLOB:right/c:$(git rev-parse topic:right/c) + BLOB:right/d:$(git rev-parse base~1:right/d) + blobs:5 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + +test_expect_success 'topic, not base' ' + test-tool path-walk -- topic --not base >out && + + cat >expect <<-EOF && + TREE::$(git rev-parse topic^{tree}) + TREE:left/:$(git rev-parse topic:left) + TREE:right/:$(git rev-parse topic:right) + trees:3 + BLOB:a:$(git rev-parse topic:a) + BLOB:left/b:$(git rev-parse topic:left/b) + BLOB:right/c:$(git rev-parse topic:right/c) + BLOB:right/d:$(git rev-parse topic:right/d) + blobs:4 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + +test_expect_success 'topic, not base, boundary' ' + test-tool path-walk -- --boundary topic --not base >out && + + cat >expect <<-EOF && + TREE::$(git rev-parse topic^{tree}) + TREE::$(git rev-parse base~1^{tree}) + TREE:left/:$(git rev-parse base~1:left) + TREE:right/:$(git rev-parse topic:right) + TREE:right/:$(git rev-parse base~1:right) + trees:5 + BLOB:a:$(git rev-parse base~1:a) + BLOB:left/b:$(git rev-parse base~1:left/b) + BLOB:right/c:$(git rev-parse base~1:right/c) + BLOB:right/c:$(git rev-parse topic:right/c) + BLOB:right/d:$(git rev-parse base~1:right/d) + blobs:5 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + +test_done From patchwork Tue Oct 8 14:11:49 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826558 Received: from mail-lj1-f176.google.com (mail-lj1-f176.google.com [209.85.208.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0B0C11DF98F for ; Tue, 8 Oct 2024 14:12:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396733; cv=none; b=kryfJbZVa2VyluwQlpS7zj5kn2rHNOHaz3Kk7w52pfWQb4CSL21lV5S29nWy8ualKzroS4uM43aKom4uIGwaHgpOd1HIPFNrNg9HXvMB9LAXOW9GWy3UdyDRdOTQywNuP9PvBU/QUU4vPO05+tbIFSx+dt949LTDaK1EZU8A2vU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396733; c=relaxed/simple; bh=DhMtzSLbO6KQGxfjDhkLvwejR8ALzzAtYNlSP5BIt78=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=IOtVAX11GtmUDYEIk/cngvLxXnme848wyxpS9N4JC64K90l7hqZxHsWk9f9dpj0MQJbJ0m2qdcvKpWQgAY+14iI5U5DofsjmAVmkqX/Y2v8lrf9UnKao9NZUuycI3Reyjs4Sl6n4fAGtK3Bcq0aiNU/ZjMnQ1AZV50tRBXF8P5c= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=mK+HzVHY; arc=none smtp.client-ip=209.85.208.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="mK+HzVHY" Received: by mail-lj1-f176.google.com with SMTP id 38308e7fff4ca-2facaa16826so48791371fa.0 for ; Tue, 08 Oct 2024 07:12:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396729; x=1729001529; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=SQmhKbdfkRQZrIpJL7j3+j8/w3CoauY10DEagaqdgY4=; b=mK+HzVHYxih/w7TMGb/+i3bm/6ICi6huqOEjGOwQEJdjjVYJ4oXLHVUCrRIK/jR8JQ t42eO/MPepGqghcEnqMjA8mZ/7whPcC634qfh2RGbv9s5YXPrftWo7fOK2IL0O7A15vT DkPXFtKD6tu9jOzv3uvhIGh503MqFpKKpHzpnyPVdXrY6hW5okPpO+upTh8iueMzeDZy YAJ+ibQvcRJZkr0IvuqOnIEyNEKVzoaTFUkF2jpesugnaUzirJtC2iGP0Yoxul7AI12A VYXzTJwnAN13/RNLpnEJUD44kS1gxO7ZHI96d1B1OltmkEt1qcmuxCvhOohnqnxGgh58 C8aA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396729; x=1729001529; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=SQmhKbdfkRQZrIpJL7j3+j8/w3CoauY10DEagaqdgY4=; b=sHlNn8CRS03Tx7wU42TYNsGujiF5foTvcaPibvhgwbU0tyc+oTx0N8wAS0F5NFFLTc /ASc7jiKfrsx3osaiUT8zw6jvPYi5JoaRWQpxc3mibYmHSex9zYQ72qqpjI+mW84e44u PUYubWvRDRXuDLf2zvTK+H3KjtnY+w95bhkX2yAFuuySlyaPvyX5izUskQmFCMPier6S 8amtHh5cYXdF/MuWiOgjyEfhTrwwJArKn6WCLcykXc5dAAu79pjnNtUwrTiP40kiE3Z2 RCIwMHQ2xSe7dX+S12eipqMM4WXcqRlCiSym3iQSmVgn7IAKJxkrKLSoWbIEEV6rW9yz U9qw== X-Gm-Message-State: AOJu0YyVGJjtbFXoRh0+WwcgC2cWDsaKGKE1oFQF4OieUgXNjpiihkhq E1o0VD7YSY9nStGOSX6ODWEVK9qwwlfS64Ay4T5FwD1cffOwNOzBFa0IRg== X-Google-Smtp-Source: AGHT+IE5qpJ3O13B7Dj3nRowIfd325QcUwnOhSV1k2Uh+t0mvyQtiCzr6tQgbkXx3VEPA65ma+wwjA== X-Received: by 2002:a2e:be9d:0:b0:2f7:ad6b:a31e with SMTP id 38308e7fff4ca-2faf3d75b0dmr63879161fa.31.1728396728469; Tue, 08 Oct 2024 07:12:08 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5c8e05a7e87sm4322495a12.24.2024.10.08.07.12.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:07 -0700 (PDT) Message-Id: <14375d19392c406d903f6cb26be5a39c4c2ff1e9.1728396724.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:49 +0000 Subject: [PATCH 03/17] path-walk: allow consumer to specify object types Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee We add the ability to filter the object types in the path-walk API so the callback function is called fewer times. This adds the ability to ask for the commits in a list, as well. Future changes will add the ability to visit annotated tags. Signed-off-by: Derrick Stolee --- Documentation/technical/api-path-walk.txt | 9 +++ path-walk.c | 39 ++++++++++-- path-walk.h | 13 +++- t/helper/test-path-walk.c | 17 +++++- t/t6601-path-walk.sh | 72 +++++++++++++++++++++++ 5 files changed, 141 insertions(+), 9 deletions(-) diff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt index e588897ab8d..b7ae476ea0a 100644 --- a/Documentation/technical/api-path-walk.txt +++ b/Documentation/technical/api-path-walk.txt @@ -48,6 +48,15 @@ If you want the path-walk API to emit `UNINTERESTING` objects based on the commit walk's boundary, be sure to set `revs.boundary` so the boundary commits are emitted. +`commits`, `blobs`, `trees`:: + By default, these members are enabled and signal that the path-walk + API should call the `path_fn` on objects of these types. Specialized + applications could disable some options to make it simpler to walk + the objects or to have fewer calls to `path_fn`. ++ +While it is possible to walk only commits in this way, consumers would be +better off using the revision walk API instead. + Examples -------- diff --git a/path-walk.c b/path-walk.c index 66840187e28..22e1aa13f31 100644 --- a/path-walk.c +++ b/path-walk.c @@ -84,6 +84,10 @@ static int add_children(struct path_walk_context *ctx, if (S_ISGITLINK(entry.mode)) continue; + /* If the caller doesn't want blobs, then don't bother. */ + if (!ctx->info->blobs && type == OBJ_BLOB) + continue; + if (type == OBJ_TREE) { struct tree *child = lookup_tree(ctx->repo, &entry.oid); o = child ? &child->object : NULL; @@ -140,9 +144,11 @@ static int walk_path(struct path_walk_context *ctx, list = strmap_get(&ctx->paths_to_lists, path); - /* Evaluate function pointer on this data. */ - ret = ctx->info->path_fn(path, &list->oids, list->type, - ctx->info->path_fn_data); + /* Evaluate function pointer on this data, if requested. */ + if ((list->type == OBJ_TREE && ctx->info->trees) || + (list->type == OBJ_BLOB && ctx->info->blobs)) + ret = ctx->info->path_fn(path, &list->oids, list->type, + ctx->info->path_fn_data); /* Expand data for children. */ if (list->type == OBJ_TREE) { @@ -184,6 +190,7 @@ int walk_objects_by_path(struct path_walk_info *info) size_t commits_nr = 0, paths_nr = 0; struct commit *c; struct type_and_oid_list *root_tree_list; + struct type_and_oid_list *commit_list; struct path_walk_context ctx = { .repo = info->revs->repo, .revs = info->revs, @@ -194,19 +201,32 @@ int walk_objects_by_path(struct path_walk_info *info) trace2_region_enter("path-walk", "commit-walk", info->revs->repo); + CALLOC_ARRAY(commit_list, 1); + commit_list->type = OBJ_COMMIT; + /* Insert a single list for the root tree into the paths. */ CALLOC_ARRAY(root_tree_list, 1); root_tree_list->type = OBJ_TREE; strmap_put(&ctx.paths_to_lists, root_path, root_tree_list); - if (prepare_revision_walk(info->revs)) die(_("failed to setup revision walk")); while ((c = get_revision(info->revs))) { - struct object_id *oid = get_commit_tree_oid(c); - struct tree *t = lookup_tree(info->revs->repo, oid); + struct object_id *oid; + struct tree *t; commits_nr++; + if (info->commits) + oid_array_append(&commit_list->oids, + &c->object.oid); + + /* If we only care about commits, then skip trees. */ + if (!info->trees && !info->blobs) + continue; + + oid = get_commit_tree_oid(c); + t = lookup_tree(info->revs->repo, oid); + if (t) { if (t->object.flags & SEEN) continue; @@ -220,6 +240,13 @@ int walk_objects_by_path(struct path_walk_info *info) trace2_data_intmax("path-walk", ctx.repo, "commits", commits_nr); trace2_region_leave("path-walk", "commit-walk", info->revs->repo); + /* Track all commits. */ + if (info->commits) + ret = info->path_fn("", &commit_list->oids, OBJ_COMMIT, + info->path_fn_data); + oid_array_clear(&commit_list->oids); + free(commit_list); + string_list_append(&ctx.path_stack, root_path); trace2_region_enter("path-walk", "path-walk", info->revs->repo); diff --git a/path-walk.h b/path-walk.h index c9e94a98bc8..6ef372d8942 100644 --- a/path-walk.h +++ b/path-walk.h @@ -30,9 +30,20 @@ struct path_walk_info { */ path_fn path_fn; void *path_fn_data; + /** + * Initialize which object types the path_fn should be called on. This + * could also limit the walk to skip blobs if not set. + */ + int commits; + int trees; + int blobs; }; -#define PATH_WALK_INFO_INIT { 0 } +#define PATH_WALK_INFO_INIT { \ + .blobs = 1, \ + .trees = 1, \ + .commits = 1, \ +} /** * Given the configuration of 'info', walk the commits based on 'info->revs' and diff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c index 3c48f017fa0..37c5e3e31e8 100644 --- a/t/helper/test-path-walk.c +++ b/t/helper/test-path-walk.c @@ -18,6 +18,7 @@ static const char * const path_walk_usage[] = { }; struct path_walk_test_data { + uintmax_t commit_nr; uintmax_t tree_nr; uintmax_t blob_nr; }; @@ -29,6 +30,11 @@ static int emit_block(const char *path, struct oid_array *oids, const char *typestr; switch (type) { + case OBJ_COMMIT: + typestr = "COMMIT"; + tdata->commit_nr += oids->nr; + break; + case OBJ_TREE: typestr = "TREE"; tdata->tree_nr += oids->nr; @@ -56,6 +62,12 @@ int cmd__path_walk(int argc, const char **argv) struct path_walk_info info = PATH_WALK_INFO_INIT; struct path_walk_test_data data = { 0 }; struct option options[] = { + OPT_BOOL(0, "blobs", &info.blobs, + N_("toggle inclusion of blob objects")), + OPT_BOOL(0, "commits", &info.commits, + N_("toggle inclusion of commit objects")), + OPT_BOOL(0, "trees", &info.trees, + N_("toggle inclusion of tree objects")), OPT_END(), }; @@ -78,9 +90,10 @@ int cmd__path_walk(int argc, const char **argv) res = walk_objects_by_path(&info); - printf("trees:%" PRIuMAX "\n" + printf("commits:%" PRIuMAX "\n" + "trees:%" PRIuMAX "\n" "blobs:%" PRIuMAX "\n", - data.tree_nr, data.blob_nr); + data.commit_nr, data.tree_nr, data.blob_nr); return res; } diff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh index ca18b61c3f1..e4788664f93 100755 --- a/t/t6601-path-walk.sh +++ b/t/t6601-path-walk.sh @@ -31,6 +31,11 @@ test_expect_success 'all' ' test-tool path-walk -- --all >out && cat >expect <<-EOF && + COMMIT::$(git rev-parse topic) + COMMIT::$(git rev-parse base) + COMMIT::$(git rev-parse base~1) + COMMIT::$(git rev-parse base~2) + commits:4 TREE::$(git rev-parse topic^{tree}) TREE::$(git rev-parse base^{tree}) TREE::$(git rev-parse base~1^{tree}) @@ -60,6 +65,10 @@ test_expect_success 'topic only' ' test-tool path-walk -- topic >out && cat >expect <<-EOF && + COMMIT::$(git rev-parse topic) + COMMIT::$(git rev-parse base~1) + COMMIT::$(git rev-parse base~2) + commits:3 TREE::$(git rev-parse topic^{tree}) TREE::$(git rev-parse base~1^{tree}) TREE::$(git rev-parse base~2^{tree}) @@ -86,6 +95,8 @@ test_expect_success 'topic, not base' ' test-tool path-walk -- topic --not base >out && cat >expect <<-EOF && + COMMIT::$(git rev-parse topic) + commits:1 TREE::$(git rev-parse topic^{tree}) TREE:left/:$(git rev-parse topic:left) TREE:right/:$(git rev-parse topic:right) @@ -103,10 +114,71 @@ test_expect_success 'topic, not base' ' test_cmp expect.sorted out.sorted ' +test_expect_success 'topic, not base, only blobs' ' + test-tool path-walk --no-trees --no-commits \ + -- topic --not base >out && + + cat >expect <<-EOF && + commits:0 + trees:0 + BLOB:a:$(git rev-parse topic:a) + BLOB:left/b:$(git rev-parse topic:left/b) + BLOB:right/c:$(git rev-parse topic:right/c) + BLOB:right/d:$(git rev-parse topic:right/d) + blobs:4 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + +# No, this doesn't make a lot of sense for the path-walk API, +# but it is possible to do. +test_expect_success 'topic, not base, only commits' ' + test-tool path-walk --no-blobs --no-trees \ + -- topic --not base >out && + + cat >expect <<-EOF && + COMMIT::$(git rev-parse topic) + commits:1 + trees:0 + blobs:0 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + +test_expect_success 'topic, not base, only trees' ' + test-tool path-walk --no-blobs --no-commits \ + -- topic --not base >out && + + cat >expect <<-EOF && + commits:0 + TREE::$(git rev-parse topic^{tree}) + TREE:left/:$(git rev-parse topic:left) + TREE:right/:$(git rev-parse topic:right) + trees:3 + blobs:0 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + test_expect_success 'topic, not base, boundary' ' test-tool path-walk -- --boundary topic --not base >out && cat >expect <<-EOF && + COMMIT::$(git rev-parse topic) + COMMIT::$(git rev-parse base~1) + commits:2 TREE::$(git rev-parse topic^{tree}) TREE::$(git rev-parse base~1^{tree}) TREE:left/:$(git rev-parse base~1:left) From patchwork Tue Oct 8 14:11:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826559 Received: from mail-ej1-f50.google.com (mail-ej1-f50.google.com [209.85.218.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 747C71DDA15 for ; Tue, 8 Oct 2024 14:12:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396733; cv=none; b=PF86M9i1+W5Njr7gp3uB53WxYKz3BGoTKMbLLtc/CMVJlodGuqBedZPi14kU7MdV5Hp/Q32IS2H48OuT2+SnaEG0m3/heEMXsgxESfKY8PN5SnS0RuKeFypxD6Vz5k786vQStPqVHUQvoE8wqANODvY8s5FkVVEUF6VNWcURVGk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396733; c=relaxed/simple; bh=uXduckztd3PZE/RnGEPYQ8ai4OnDRgIcdaDbV3djYWk=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=tuO6O8Dt9LPQY4eAdaIOepdSXo6A8uu2+R1l32V02JHe+qy7+CNSqvTRLtXh++XwKBfegFlAxINRFAIT86gWTC27+C29k0DOM6P1/trXmtY68/iAu1dFfISpF3VUsviqchORWY/fTZ7IgK/n7XtfnAN3F01AgrtFanIpjcrbOT0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lnF044lp; arc=none smtp.client-ip=209.85.218.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lnF044lp" Received: by mail-ej1-f50.google.com with SMTP id a640c23a62f3a-a994277b38bso229312166b.2 for ; Tue, 08 Oct 2024 07:12:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396729; x=1729001529; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=Z3eAeDdt/7zLXTBEgPtnxnwp/4c3sd4okG7PblAnepA=; b=lnF044lpRBmSvcoF5ZcoTwh8Qc2hRXy6iz9r25DmafIwUU+jMxuM0ZXqx5CCcftEx1 EkUleEqWRen0keSgZs3+S9cUuCHncPT+gBbvj2Hl6RJbYes0Mvd/hgyOEglLVTWWLmdw T4Ov+gH7ezt+saT7sWJODgmpkLckIGN33nrzPW6Gg12WWhXEO59vI9Rj7gZrz0u8MuID TubbW2XxSE7aNKFBY3xUut5Qjh+A4mfzZbfKMh8dFsGhXeYsZ7n0BhD1b6mLviKVXdH1 Fh8PSQjywfwkQINlIySqacJeMspDJPziuGYsCfnnjNDe3NxDohl1y0a3YNhe9oJvkcHp s0dQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396729; x=1729001529; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Z3eAeDdt/7zLXTBEgPtnxnwp/4c3sd4okG7PblAnepA=; b=igdeZ33jK7vL/l6VEzG3XodEcokegF2iTV0WIu5L06go1INXkaO1m6v8KDiwDrk8vi WbDYrrmmmTmgdjnkFc+rNWJbXQHxaKWOAF92GgbU0sjUE5l9gWP4Q3MESJdb/aK8tWPY JUlFDfVeCbJQMnnBqJgbaeGkWkqcQAKpXcD7/VW/LMGE07qsGHpK6P9Mqybe2/Hqw3tt 4jxmtEJBEtf3pkLA89X9we5YmXMs6H1qio/pLy91x8tjG/B6/JUIgQJYvoNxR2A4oJk6 qznRTXSPUuYmUzCD3Rr47GBiITnBKBS5PUXBbv9I3Z2WzBZQfEwMX2omJU6ICfjDkvUK Xa7g== X-Gm-Message-State: AOJu0YxcKNOk3C4mAMrK/67Ra8Tof3/KYePW8+UJAYo8LFmUx3RJVfd6 dskcX26SV9MGv7O3+KVyhWk1PAinu+iNVBEvoIL+acgAswE3vqsCXMb0DA== X-Google-Smtp-Source: AGHT+IH3JjttUYRM1umBC0YTB4+kaJAAfCb3mvLVUC+xdRJq8vwr05+OaCQFU+GtlgirJiZBC3pdcw== X-Received: by 2002:a05:6402:388b:b0:5c8:8381:bb8f with SMTP id 4fb4d7f45d1cf-5c8d2ea06aamr17185760a12.24.1728396729271; Tue, 08 Oct 2024 07:12:09 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5c8e0594f55sm4368812a12.13.2024.10.08.07.12.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:08 -0700 (PDT) Message-Id: <6f48cddadc0ad1a6dc3caec9d81e014b668c1f03.1728396724.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:50 +0000 Subject: [PATCH 04/17] path-walk: allow visiting tags Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee In anticipation of using the path-walk API to analyze tags or include them in a pack-file, add the ability to walk the tags that were included in the revision walk. When these tag objects point to blobs or trees, we need to make sure those objects are also visited. Treat tagged trees as root trees, but put the tagged blobs in their own category. Be careful about objects that are referred to by multiple references. Co-authored-by: Johannes Schindelin Signed-off-by: Johannes Schindelin Signed-off-by: Derrick Stolee --- Documentation/technical/api-path-walk.txt | 2 +- path-walk.c | 76 ++++++++++++++++++++ path-walk.h | 2 + t/helper/test-path-walk.c | 13 +++- t/t6601-path-walk.sh | 85 +++++++++++++++++++++-- 5 files changed, 170 insertions(+), 8 deletions(-) diff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt index b7ae476ea0a..5fea1d1db17 100644 --- a/Documentation/technical/api-path-walk.txt +++ b/Documentation/technical/api-path-walk.txt @@ -48,7 +48,7 @@ If you want the path-walk API to emit `UNINTERESTING` objects based on the commit walk's boundary, be sure to set `revs.boundary` so the boundary commits are emitted. -`commits`, `blobs`, `trees`:: +`commits`, `blobs`, `trees`, `tags`:: By default, these members are enabled and signal that the path-walk API should call the `path_fn` on objects of these types. Specialized applications could disable some options to make it simpler to walk diff --git a/path-walk.c b/path-walk.c index 22e1aa13f31..7cd461adf47 100644 --- a/path-walk.c +++ b/path-walk.c @@ -13,6 +13,7 @@ #include "revision.h" #include "string-list.h" #include "strmap.h" +#include "tag.h" #include "trace2.h" #include "tree.h" #include "tree-walk.h" @@ -204,13 +205,88 @@ int walk_objects_by_path(struct path_walk_info *info) CALLOC_ARRAY(commit_list, 1); commit_list->type = OBJ_COMMIT; + if (info->tags) + info->revs->tag_objects = 1; + /* Insert a single list for the root tree into the paths. */ CALLOC_ARRAY(root_tree_list, 1); root_tree_list->type = OBJ_TREE; strmap_put(&ctx.paths_to_lists, root_path, root_tree_list); + + /* + * Set these values before preparing the walk to catch + * lightweight tags pointing to non-commits. + */ + info->revs->blob_objects = info->blobs; + info->revs->tree_objects = info->trees; + if (prepare_revision_walk(info->revs)) die(_("failed to setup revision walk")); + info->revs->blob_objects = info->revs->tree_objects = 0; + + if (info->tags) { + struct oid_array tagged_blob_list = OID_ARRAY_INIT; + struct oid_array tags = OID_ARRAY_INIT; + + trace2_region_enter("path-walk", "tag-walk", info->revs->repo); + + /* + * Walk any pending objects at this point, but they should only + * be tags. + */ + for (size_t i = 0; i < info->revs->pending.nr; i++) { + struct object_array_entry *pending = info->revs->pending.objects + i; + struct object *obj = pending->item; + + if (obj->type == OBJ_COMMIT || obj->flags & SEEN) + continue; + + obj->flags |= SEEN; + + while (obj->type == OBJ_TAG) { + struct tag *tag = lookup_tag(info->revs->repo, + &obj->oid); + if (oid_array_lookup(&tags, &obj->oid) < 0) + oid_array_append(&tags, &obj->oid); + obj = tag->tagged; + } + + switch (obj->type) { + case OBJ_TREE: + if (info->trees && + oid_array_lookup(&root_tree_list->oids, &obj->oid) < 0) + oid_array_append(&root_tree_list->oids, &obj->oid); + break; + + case OBJ_BLOB: + if (info->blobs && + oid_array_lookup(&tagged_blob_list, &obj->oid) < 0) + oid_array_append(&tagged_blob_list, &obj->oid); + break; + + case OBJ_COMMIT: + /* Make sure it is in the object walk */ + add_pending_object(info->revs, obj, ""); + break; + + default: + BUG("should not see any other type here"); + } + } + + info->path_fn("", &tags, OBJ_TAG, info->path_fn_data); + + if (tagged_blob_list.nr && info->blobs) + info->path_fn("/tagged-blobs", &tagged_blob_list, OBJ_BLOB, + info->path_fn_data); + + trace2_data_intmax("path-walk", ctx.repo, "tags", tags.nr); + trace2_region_leave("path-walk", "tag-walk", info->revs->repo); + oid_array_clear(&tags); + oid_array_clear(&tagged_blob_list); + } + while ((c = get_revision(info->revs))) { struct object_id *oid; struct tree *t; diff --git a/path-walk.h b/path-walk.h index 6ef372d8942..3f3b63180ef 100644 --- a/path-walk.h +++ b/path-walk.h @@ -37,12 +37,14 @@ struct path_walk_info { int commits; int trees; int blobs; + int tags; }; #define PATH_WALK_INFO_INIT { \ .blobs = 1, \ .trees = 1, \ .commits = 1, \ + .tags = 1, \ } /** diff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c index 37c5e3e31e8..c6c60d68749 100644 --- a/t/helper/test-path-walk.c +++ b/t/helper/test-path-walk.c @@ -21,6 +21,7 @@ struct path_walk_test_data { uintmax_t commit_nr; uintmax_t tree_nr; uintmax_t blob_nr; + uintmax_t tag_nr; }; static int emit_block(const char *path, struct oid_array *oids, @@ -45,6 +46,11 @@ static int emit_block(const char *path, struct oid_array *oids, tdata->blob_nr += oids->nr; break; + case OBJ_TAG: + typestr = "TAG"; + tdata->tag_nr += oids->nr; + break; + default: BUG("we do not understand this type"); } @@ -66,6 +72,8 @@ int cmd__path_walk(int argc, const char **argv) N_("toggle inclusion of blob objects")), OPT_BOOL(0, "commits", &info.commits, N_("toggle inclusion of commit objects")), + OPT_BOOL(0, "tags", &info.tags, + N_("toggle inclusion of tag objects")), OPT_BOOL(0, "trees", &info.trees, N_("toggle inclusion of tree objects")), OPT_END(), @@ -92,8 +100,9 @@ int cmd__path_walk(int argc, const char **argv) printf("commits:%" PRIuMAX "\n" "trees:%" PRIuMAX "\n" - "blobs:%" PRIuMAX "\n", - data.commit_nr, data.tree_nr, data.blob_nr); + "blobs:%" PRIuMAX "\n" + "tags:%" PRIuMAX "\n", + data.commit_nr, data.tree_nr, data.blob_nr, data.tag_nr); return res; } diff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh index e4788664f93..7758e2529ee 100755 --- a/t/t6601-path-walk.sh +++ b/t/t6601-path-walk.sh @@ -7,24 +7,55 @@ test_description='direct path-walk API tests' test_expect_success 'setup test repository' ' git checkout -b base && + # Make some objects that will only be reachable + # via non-commit tags. + mkdir child && + echo file >child/file && + git add child && + git commit -m "will abandon" && + git tag -a -m "tree" tree-tag HEAD^{tree} && + echo file2 >file2 && + git add file2 && + git commit --amend -m "will abandon" && + git tag tree-tag2 HEAD^{tree} && + + echo blob >file && + blob_oid=$(git hash-object -t blob -w --stdin file2 && + blob2_oid=$(git hash-object -t blob -w --stdin a && echo b >left/b && echo c >right/c && git add . && - git commit -m "first" && + git commit --amend -m "first" && + git tag -m "first" first HEAD && echo d >right/d && git add right && git commit -m "second" && + git tag -a -m "second (under)" second.1 HEAD && + git tag -a -m "second (top)" second.2 second.1 && + # Set up file/dir collision in history. + rm a && + mkdir a && + echo a >a/a && echo bb >left/b && - git commit -a -m "third" && + git add a left && + git commit -m "third" && + git tag -a -m "third" third && git checkout -b topic HEAD~1 && echo cc >right/c && - git commit -a -m "topic" + git commit -a -m "topic" && + git tag -a -m "fourth" fourth ' test_expect_success 'all' ' @@ -40,19 +71,35 @@ test_expect_success 'all' ' TREE::$(git rev-parse base^{tree}) TREE::$(git rev-parse base~1^{tree}) TREE::$(git rev-parse base~2^{tree}) + TREE::$(git rev-parse refs/tags/tree-tag^{}) + TREE::$(git rev-parse refs/tags/tree-tag2^{}) + TREE:a/:$(git rev-parse base:a) TREE:left/:$(git rev-parse base:left) TREE:left/:$(git rev-parse base~2:left) TREE:right/:$(git rev-parse topic:right) TREE:right/:$(git rev-parse base~1:right) TREE:right/:$(git rev-parse base~2:right) - trees:9 + TREE:child/:$(git rev-parse refs/tags/tree-tag^{}:child) + trees:13 BLOB:a:$(git rev-parse base~2:a) + BLOB:file2:$(git rev-parse refs/tags/tree-tag2^{}:file2) BLOB:left/b:$(git rev-parse base~2:left/b) BLOB:left/b:$(git rev-parse base:left/b) BLOB:right/c:$(git rev-parse base~2:right/c) BLOB:right/c:$(git rev-parse topic:right/c) BLOB:right/d:$(git rev-parse base~1:right/d) - blobs:6 + BLOB:/tagged-blobs:$(git rev-parse refs/tags/blob-tag^{}) + BLOB:/tagged-blobs:$(git rev-parse refs/tags/blob-tag2^{}) + BLOB:child/file:$(git rev-parse refs/tags/tree-tag^{}:child/file) + blobs:10 + TAG::$(git rev-parse refs/tags/first) + TAG::$(git rev-parse refs/tags/second.1) + TAG::$(git rev-parse refs/tags/second.2) + TAG::$(git rev-parse refs/tags/third) + TAG::$(git rev-parse refs/tags/fourth) + TAG::$(git rev-parse refs/tags/tree-tag) + TAG::$(git rev-parse refs/tags/blob-tag) + tags:7 EOF sort expect >expect.sorted && @@ -83,6 +130,7 @@ test_expect_success 'topic only' ' BLOB:right/c:$(git rev-parse topic:right/c) BLOB:right/d:$(git rev-parse base~1:right/d) blobs:5 + tags:0 EOF sort expect >expect.sorted && @@ -106,6 +154,7 @@ test_expect_success 'topic, not base' ' BLOB:right/c:$(git rev-parse topic:right/c) BLOB:right/d:$(git rev-parse topic:right/d) blobs:4 + tags:0 EOF sort expect >expect.sorted && @@ -126,6 +175,7 @@ test_expect_success 'topic, not base, only blobs' ' BLOB:right/c:$(git rev-parse topic:right/c) BLOB:right/d:$(git rev-parse topic:right/d) blobs:4 + tags:0 EOF sort expect >expect.sorted && @@ -145,6 +195,7 @@ test_expect_success 'topic, not base, only commits' ' commits:1 trees:0 blobs:0 + tags:0 EOF sort expect >expect.sorted && @@ -164,6 +215,7 @@ test_expect_success 'topic, not base, only trees' ' TREE:right/:$(git rev-parse topic:right) trees:3 blobs:0 + tags:0 EOF sort expect >expect.sorted && @@ -191,6 +243,7 @@ test_expect_success 'topic, not base, boundary' ' BLOB:right/c:$(git rev-parse topic:right/c) BLOB:right/d:$(git rev-parse base~1:right/d) blobs:5 + tags:0 EOF sort expect >expect.sorted && @@ -199,4 +252,26 @@ test_expect_success 'topic, not base, boundary' ' test_cmp expect.sorted out.sorted ' +test_expect_success 'trees are reported exactly once' ' + test_when_finished "rm -rf unique-trees" && + test_create_repo unique-trees && + ( + cd unique-trees && + mkdir initial && + test_commit initial/file && + + git switch -c move-to-top && + git mv initial/file.t ./ && + test_tick && + git commit -m moved && + + git update-ref refs/heads/other HEAD + ) && + + test-tool -C unique-trees path-walk -- --all >out && + tree=$(git -C unique-trees rev-parse HEAD:) && + grep "$tree" out >out-filtered && + test_line_count = 1 out-filtered +' + test_done From patchwork Tue Oct 8 14:11:51 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826560 Received: from mail-ed1-f48.google.com (mail-ed1-f48.google.com [209.85.208.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 307631DFD80 for ; Tue, 8 Oct 2024 14:12:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396733; cv=none; b=s+n/fwbu3bdRxhFf72hr2obKzK92sRcfDp2JWEEY6cnwCm7vrMLm+Nl0JuPO9dhCcC4w8StRJT++vRGApkoonnZMmv7aXsVI3H+oD0bOj3K8MumDD7n2h+ql8i+D3PNMO5roBqnQi4TqNVZihhzj2YT8g+0QP8mx8V5V7musd94= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396733; c=relaxed/simple; bh=8/c/yA7Z4chcFAC86FyGgWEKtP39z4MIdZaXvM2xvd8=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=Wrz+tjHVIOD0Uhgy1NMNtzPs00aohAYYtpDyIJe/AlmGPxVQg2PpaJ1QAKSwuRLl3oL/1h1w31hDbORhhiu4XPT25egYQZDcwZmFcYLqi5e4bnvly+FAUA3mDT6zcsWOj2xcgxmcoE6r4FHyTP0q18I1uRhdn+0mOGgITEARKUE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=cPjCICX0; arc=none smtp.client-ip=209.85.208.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="cPjCICX0" Received: by mail-ed1-f48.google.com with SMTP id 4fb4d7f45d1cf-5c883459b19so6651029a12.2 for ; Tue, 08 Oct 2024 07:12:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396730; x=1729001530; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=CiRsSr9N+34ulobRz7mRSLnLQayzsrwlctft/WmYog0=; b=cPjCICX0ND+0CXmyyDV5gAAp9jc9VE5crWDOjX2ARO1+0Ghd+5O727lHQ7kSs/veGk LoaAspR60DrL67W81qyDpQsoCN9Wvt4kk7x/b8qloMYJxV5m9aMXXCTV8UquNqid7IyT aVZVocXUGK/Brabg4G4KdagwTMYYq0ZC3GiXtNJzOZQM/DHS7VY8xO2M5bv2wQUKK9nn NdEOsYvJyoJRSnze8D7oztZ9e04GsBXgpQvHpUD/67yjMCWFMAc1df8ShBTea7L36CdG BrZTVFg2sSqShPwFaZpZKn3h2kZaT2f6EwO56iK2EJWsTYcSYfETXErA3c9QxfBqul0G CrJg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396730; x=1729001530; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=CiRsSr9N+34ulobRz7mRSLnLQayzsrwlctft/WmYog0=; b=IurLnr01g457YadigpfecRr1KYbLNOVy/5DR0ZnEctsTVPAZxiTa1iQ/sKdm3sC552 z+HLr6iGLa15KRo6KDKqgbjDP/JM/C8jb37ccOTSdmJQBhTmktla8dH9GRxh2cNlZJsT 4oouWlu9qh0pqS7xdM3uDw8FwfxWrme9Pp2EM/WBbH3uTjDXvkVIndZG827tPUwihSb5 oXGfPbUAgapD0G6LH/Ir7DqGCarIoZGZ+AfadoqIWFCIYn3uqO7Gq28DCl4AeIbglqW7 h+mEfi2yutTd/LuW2Y/4+zXB1MnytbccmX9BK19YiDV2la16mh3XSyOmZ5t7zt6ML5B1 tSnQ== X-Gm-Message-State: AOJu0YzxfBwXNcHLxnRbkPszQf+uiQBI0loEIvVOsZnVkdyJsfmRZQj7 k+s4NxH36nYFCZ0+oAeS0mtdLX9D3C6aR7L0DfiS20RrRKBXukYuYnV5XQ== X-Google-Smtp-Source: AGHT+IHdyxgrIvZJO1bq0O8x5SVr4As+IXvRs5UVUwK3Yd1TwFPLEYATMSnCv+/fJ4/j9e3Xr/N67g== X-Received: by 2002:a17:907:94cd:b0:a99:8629:603a with SMTP id a640c23a62f3a-a998629621bmr4927766b.57.1728396729937; Tue, 08 Oct 2024 07:12:09 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a99384f8258sm481489466b.16.2024.10.08.07.12.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:09 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:51 +0000 Subject: [PATCH 05/17] revision: create mark_trees_uninteresting_dense() Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee The sparse tree walk algorithm was created in d5d2e93577e (revision: implement sparse algorithm, 2019-01-16) and involves using the mark_trees_uninteresting_sparse() method. This method takes a repository and an oidset of tree IDs, some of which have the UNINTERESTING flag and some of which do not. Create a method that has an equivalent set of preconditions but uses a "dense" walk (recursively visits all reachable trees, as long as they have not previously been marked UNINTERESTING). This is an important difference from mark_tree_uninteresting(), which short-circuits if the given tree has the UNINTERESTING flag. A use of this method will be added in a later change, with a condition set whether the sparse or dense approach should be used. Signed-off-by: Derrick Stolee --- revision.c | 15 +++++++++++++++ revision.h | 1 + 2 files changed, 16 insertions(+) diff --git a/revision.c b/revision.c index 2d7ad2bddff..bdc312f1538 100644 --- a/revision.c +++ b/revision.c @@ -219,6 +219,21 @@ static void add_children_by_path(struct repository *r, free_tree_buffer(tree); } +void mark_trees_uninteresting_dense(struct repository *r, + struct oidset *trees) +{ + struct object_id *oid; + struct oidset_iter iter; + + oidset_iter_init(trees, &iter); + while ((oid = oidset_iter_next(&iter))) { + struct tree *tree = lookup_tree(r, oid); + + if (tree && (tree->object.flags & UNINTERESTING)) + mark_tree_contents_uninteresting(r, tree); + } +} + void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees) { diff --git a/revision.h b/revision.h index 71e984c452b..8938b2db112 100644 --- a/revision.h +++ b/revision.h @@ -487,6 +487,7 @@ void put_revision_mark(const struct rev_info *revs, void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit); void mark_tree_uninteresting(struct repository *r, struct tree *tree); +void mark_trees_uninteresting_dense(struct repository *r, struct oidset *trees); void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees); void show_object_with_name(FILE *, struct object *, const char *); From patchwork Tue Oct 8 14:11:52 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826561 Received: from mail-wr1-f47.google.com (mail-wr1-f47.google.com [209.85.221.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0AA4F1DFD93 for ; Tue, 8 Oct 2024 14:12:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396735; cv=none; b=iPOTUZekLuFQw77j7sGSJVYBskD6T008L+OPinSfUKp90bou8P1U6XilMd+LSKjXJKwcjvKrNZExgNyBi5f3ckFHLe7fCCdrqmBKwsoSXx3dzU7wjJp1uD3bqgvYGKGnFObaaOxYG99XlcqMGod7LP10eoAZTWiOHznw4g+E604= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396735; c=relaxed/simple; bh=BoKhgtXj+pbg6nk7X9eIImJEzODSnxFKUTr9gUCJjzg=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=AGZyufvQ8vhkCbTkyp7r/qd3mRIjkFynVjodPy9D9iVZnG44qOR1bfPKjleOkVUzlEy1ksr69iyFTBT4fsZBIAn1AcP9hWT7iJHIuuf1JD7mE8eOo0GLZwe5JX2G2Z38RaJJE0c4kKWvx1E9Yfd766FUsiQonQ3NhCcFKqjGY30= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=gQD7kPea; arc=none smtp.client-ip=209.85.221.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="gQD7kPea" Received: by mail-wr1-f47.google.com with SMTP id ffacd0b85a97d-37cdac05af9so5358044f8f.0 for ; Tue, 08 Oct 2024 07:12:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396731; x=1729001531; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=ha8ay8iahD6cLsog+hMHVmsKjX2VkLvrBK4KVcz2BfU=; b=gQD7kPealFplePTcJhYBgTk3Hl1SQOH8BoG3JzXllzdgL/FRsr3miH/+Z0LzVwoS5n dBe0mkmRp1r9Qzdt/WzKlicImI6o5hkVrUXeECbuWZ7ujBmeifftEeKQJa67fa0v5F98 Bp9iawq2ig5r510TyznwvDY0YiIbHVRiqQOhDGdjpfCsZ8yqSp5cWXIbMZGWMUI0R8vy N1uYjBMfFl8/bBVafepao/Ia1Hlj89GOkrrDYr+DGNVUW3FxVIMzqeA9DdUKmFKSNxx9 W2FRW8y2dcyFMbCo/qbnNJs4si2OjTij8NYDnOAp7PMDa036B3Ne3dcRhKF/QEuamI4X dsnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396731; x=1729001531; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ha8ay8iahD6cLsog+hMHVmsKjX2VkLvrBK4KVcz2BfU=; b=EXcqtRrkPSad78HlbrIvBoWnnveZIWVj3joLigsaQPB8JcFbLWbBaG94lZGYkDwobM Pqj5twxCw6qE7D9F90PD4Jdoy6bIjo6qF+Ym0FrxDPQkHx5s6k0l3/nNXtH7pjJVKLm0 3yHM0HUgLVT7QSwp4LX2MZchpU5pdCykttwNhS4LQszuxx97WkkyicTGq18LFW0n/1yV SZfmC5ErMFra3AewA+n9ily6xPE36PUpJQKh2Bh43+g8I7Joz10CpiCp5Cb59i5VAFhL DBWPs4HLpA57XLueAmYyWGrfr5jtSTn0gE9pAZu10MO5otL9HymXjj/21QwTnRgoK42o J4bA== X-Gm-Message-State: AOJu0YyKN3pPmJlpTq7zr9jCRzxpdpfjKI4Ab/KbOcsi8RiAjJB0kWP0 mnFd2fpeiZNgN+LHr/PuJAWMHTZ9tw+Cw0RtdiMN/rcXeKbvYRWq8tQnPQ== X-Google-Smtp-Source: AGHT+IGuy3fOVxko9PAGWgKNMOrEjypjWn13Fp2QXOtrojGxX/OyP3wLce4u2s1WauUbZhrXQNpUjw== X-Received: by 2002:a5d:4408:0:b0:37c:d18e:6463 with SMTP id ffacd0b85a97d-37d0e8da581mr12915095f8f.47.1728396730674; Tue, 08 Oct 2024 07:12:10 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9941a697cesm430119366b.173.2024.10.08.07.12.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:10 -0700 (PDT) Message-Id: <214e10a99841f09361081a6a0f182f66f420aa09.1728396724.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:52 +0000 Subject: [PATCH 06/17] path-walk: add prune_all_uninteresting option Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee This option causes the path-walk API to act like the sparse tree-walk algorithm implemented by mark_trees_uninteresting_sparse() in list-objects.c. Starting from the commits marked as UNINTERESTING, their root trees and all objects reachable from those trees are UNINTERSTING, at least as we walk path-by-path. When we reach a path where all objects associated with that path are marked UNINTERESTING, then do no continue walking the children of that path. We need to be careful to pass the UNINTERESTING flag in a deep way on the UNINTERESTING objects before we start the path-walk, or else the depth-first search for the path-walk API may accidentally report some objects as interesting. Signed-off-by: Derrick Stolee --- Documentation/technical/api-path-walk.txt | 8 +++ path-walk.c | 64 ++++++++++++++++++++++- path-walk.h | 8 +++ t/helper/test-path-walk.c | 10 +++- t/t6601-path-walk.sh | 40 +++++++++++--- 5 files changed, 118 insertions(+), 12 deletions(-) diff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt index 5fea1d1db17..c51f92cd649 100644 --- a/Documentation/technical/api-path-walk.txt +++ b/Documentation/technical/api-path-walk.txt @@ -57,6 +57,14 @@ commits are emitted. While it is possible to walk only commits in this way, consumers would be better off using the revision walk API instead. +`prune_all_uninteresting`:: + By default, all reachable paths are emitted by the path-walk API. + This option allows consumers to declare that they are not + interested in paths where all included objects are marked with the + `UNINTERESTING` flag. This requires using the `boundary` option in + the revision walk so that the walk emits commits marked with the + `UNINTERESTING` flag. + Examples -------- diff --git a/path-walk.c b/path-walk.c index 7cd461adf47..dce0840937e 100644 --- a/path-walk.c +++ b/path-walk.c @@ -22,6 +22,7 @@ struct type_and_oid_list { enum object_type type; struct oid_array oids; + int maybe_interesting; }; #define TYPE_AND_OID_LIST_INIT { \ @@ -124,6 +125,8 @@ static int add_children(struct path_walk_context *ctx, strmap_put(&ctx->paths_to_lists, path.buf, list); string_list_append(&ctx->path_stack, path.buf); } + if (!(o->flags & UNINTERESTING)) + list->maybe_interesting = 1; oid_array_append(&list->oids, &entry.oid); } @@ -145,6 +148,40 @@ static int walk_path(struct path_walk_context *ctx, list = strmap_get(&ctx->paths_to_lists, path); + if (ctx->info->prune_all_uninteresting) { + /* + * This is true if all objects were UNINTERESTING + * when added to the list. + */ + if (!list->maybe_interesting) + return 0; + + /* + * But it's still possible that the objects were set + * as UNINTERESTING after being added. Do a quick check. + */ + list->maybe_interesting = 0; + for (size_t i = 0; + !list->maybe_interesting && i < list->oids.nr; + i++) { + if (list->type == OBJ_TREE) { + struct tree *t = lookup_tree(ctx->repo, + &list->oids.oid[i]); + if (t && !(t->object.flags & UNINTERESTING)) + list->maybe_interesting = 1; + } else { + struct blob *b = lookup_blob(ctx->repo, + &list->oids.oid[i]); + if (b && !(b->object.flags & UNINTERESTING)) + list->maybe_interesting = 1; + } + } + + /* We have confirmed that all objects are UNINTERESTING. */ + if (!list->maybe_interesting) + return 0; + } + /* Evaluate function pointer on this data, if requested. */ if ((list->type == OBJ_TREE && ctx->info->trees) || (list->type == OBJ_BLOB && ctx->info->blobs)) @@ -187,7 +224,7 @@ static void clear_strmap(struct strmap *map) int walk_objects_by_path(struct path_walk_info *info) { const char *root_path = ""; - int ret = 0; + int ret = 0, has_uninteresting = 0; size_t commits_nr = 0, paths_nr = 0; struct commit *c; struct type_and_oid_list *root_tree_list; @@ -199,6 +236,7 @@ int walk_objects_by_path(struct path_walk_info *info) .path_stack = STRING_LIST_INIT_DUP, .paths_to_lists = STRMAP_INIT }; + struct oidset root_tree_set = OIDSET_INIT; trace2_region_enter("path-walk", "commit-walk", info->revs->repo); @@ -211,6 +249,7 @@ int walk_objects_by_path(struct path_walk_info *info) /* Insert a single list for the root tree into the paths. */ CALLOC_ARRAY(root_tree_list, 1); root_tree_list->type = OBJ_TREE; + root_tree_list->maybe_interesting = 1; strmap_put(&ctx.paths_to_lists, root_path, root_tree_list); /* @@ -304,10 +343,16 @@ int walk_objects_by_path(struct path_walk_info *info) t = lookup_tree(info->revs->repo, oid); if (t) { + if ((c->object.flags & UNINTERESTING)) { + t->object.flags |= UNINTERESTING; + has_uninteresting = 1; + } + if (t->object.flags & SEEN) continue; t->object.flags |= SEEN; - oid_array_append(&root_tree_list->oids, oid); + if (!oidset_insert(&root_tree_set, oid)) + oid_array_append(&root_tree_list->oids, oid); } else { warning("could not find tree %s", oid_to_hex(oid)); } @@ -323,6 +368,21 @@ int walk_objects_by_path(struct path_walk_info *info) oid_array_clear(&commit_list->oids); free(commit_list); + /* + * Before performing a DFS of our paths and emitting them as interesting, + * do a full walk of the trees to distribute the UNINTERESTING bit. Use + * the sparse algorithm if prune_all_uninteresting was set. + */ + if (has_uninteresting) { + trace2_region_enter("path-walk", "uninteresting-walk", info->revs->repo); + if (info->prune_all_uninteresting) + mark_trees_uninteresting_sparse(ctx.repo, &root_tree_set); + else + mark_trees_uninteresting_dense(ctx.repo, &root_tree_set); + trace2_region_leave("path-walk", "uninteresting-walk", info->revs->repo); + } + oidset_clear(&root_tree_set); + string_list_append(&ctx.path_stack, root_path); trace2_region_enter("path-walk", "path-walk", info->revs->repo); diff --git a/path-walk.h b/path-walk.h index 3f3b63180ef..3e44c4b8a58 100644 --- a/path-walk.h +++ b/path-walk.h @@ -38,6 +38,14 @@ struct path_walk_info { int trees; int blobs; int tags; + + /** + * When 'prune_all_uninteresting' is set and a path has all objects + * marked as UNINTERESTING, then the path-walk will not visit those + * objects. It will not call path_fn on those objects and will not + * walk the children of such trees. + */ + int prune_all_uninteresting; }; #define PATH_WALK_INFO_INIT { \ diff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c index c6c60d68749..06b103d8760 100644 --- a/t/helper/test-path-walk.c +++ b/t/helper/test-path-walk.c @@ -55,8 +55,12 @@ static int emit_block(const char *path, struct oid_array *oids, BUG("we do not understand this type"); } - for (size_t i = 0; i < oids->nr; i++) - printf("%s:%s:%s\n", typestr, path, oid_to_hex(&oids->oid[i])); + for (size_t i = 0; i < oids->nr; i++) { + struct object *o = lookup_unknown_object(the_repository, + &oids->oid[i]); + printf("%s:%s:%s%s\n", typestr, path, oid_to_hex(&oids->oid[i]), + o->flags & UNINTERESTING ? ":UNINTERESTING" : ""); + } return 0; } @@ -76,6 +80,8 @@ int cmd__path_walk(int argc, const char **argv) N_("toggle inclusion of tag objects")), OPT_BOOL(0, "trees", &info.trees, N_("toggle inclusion of tree objects")), + OPT_BOOL(0, "prune", &info.prune_all_uninteresting, + N_("toggle pruning of uninteresting paths")), OPT_END(), }; diff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh index 7758e2529ee..943adc6c8f1 100755 --- a/t/t6601-path-walk.sh +++ b/t/t6601-path-walk.sh @@ -229,19 +229,19 @@ test_expect_success 'topic, not base, boundary' ' cat >expect <<-EOF && COMMIT::$(git rev-parse topic) - COMMIT::$(git rev-parse base~1) + COMMIT::$(git rev-parse base~1):UNINTERESTING commits:2 TREE::$(git rev-parse topic^{tree}) - TREE::$(git rev-parse base~1^{tree}) - TREE:left/:$(git rev-parse base~1:left) + TREE::$(git rev-parse base~1^{tree}):UNINTERESTING + TREE:left/:$(git rev-parse base~1:left):UNINTERESTING TREE:right/:$(git rev-parse topic:right) - TREE:right/:$(git rev-parse base~1:right) + TREE:right/:$(git rev-parse base~1:right):UNINTERESTING trees:5 - BLOB:a:$(git rev-parse base~1:a) - BLOB:left/b:$(git rev-parse base~1:left/b) - BLOB:right/c:$(git rev-parse base~1:right/c) + BLOB:a:$(git rev-parse base~1:a):UNINTERESTING + BLOB:left/b:$(git rev-parse base~1:left/b):UNINTERESTING + BLOB:right/c:$(git rev-parse base~1:right/c):UNINTERESTING BLOB:right/c:$(git rev-parse topic:right/c) - BLOB:right/d:$(git rev-parse base~1:right/d) + BLOB:right/d:$(git rev-parse base~1:right/d):UNINTERESTING blobs:5 tags:0 EOF @@ -252,6 +252,30 @@ test_expect_success 'topic, not base, boundary' ' test_cmp expect.sorted out.sorted ' +test_expect_success 'topic, not base, boundary with pruning' ' + test-tool path-walk --prune -- --boundary topic --not base >out && + + cat >expect <<-EOF && + COMMIT::$(git rev-parse topic) + COMMIT::$(git rev-parse base~1):UNINTERESTING + commits:2 + TREE::$(git rev-parse topic^{tree}) + TREE::$(git rev-parse base~1^{tree}):UNINTERESTING + TREE:right/:$(git rev-parse topic:right) + TREE:right/:$(git rev-parse base~1:right):UNINTERESTING + trees:4 + BLOB:right/c:$(git rev-parse base~1:right/c):UNINTERESTING + BLOB:right/c:$(git rev-parse topic:right/c) + blobs:2 + tags:0 + EOF + + sort expect >expect.sorted && + sort out >out.sorted && + + test_cmp expect.sorted out.sorted +' + test_expect_success 'trees are reported exactly once' ' test_when_finished "rm -rf unique-trees" && test_create_repo unique-trees && From patchwork Tue Oct 8 14:11:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826562 Received: from mail-lf1-f51.google.com (mail-lf1-f51.google.com [209.85.167.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 03D3C1DFDAD for ; Tue, 8 Oct 2024 14:12:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396735; cv=none; b=s5iWChSljrcTH1k4Y6Haap8H55TfEPHBoMjEl+V0rmVzaMamVEL+GOoiZKtr/QjgpLOO64VClydlBmOAogBWcGJMpvdEM3lT5sERuckGJVAqxpog284PmvNCBuA5zLt32HiDey9wwElXys0LmmMNtOKCOWxCX2GCXGqAYueEjME= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396735; c=relaxed/simple; bh=FWW0Yk4EjQQ1LYFwR1ffznyINczb6AXTwXpT8uITqmI=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=i4GK2ofcxQ48ciXIXiRKCqALZgdennyAaqXflnnrV1iqWdmBMbEEeGR3M8UiLsrTUV0jUYJBZaBClxDyz5gO4bKxTLE31yVIcz06UoO60A44vUdnwft+dcCtIZ/mfMen5s5f4T/OU2Sl3rhCo3kTTfFCFpPYYYwApuD22Cfy+fE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=SwSxFzLQ; arc=none smtp.client-ip=209.85.167.51 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="SwSxFzLQ" Received: by mail-lf1-f51.google.com with SMTP id 2adb3069b0e04-5398df2c871so6073185e87.1 for ; Tue, 08 Oct 2024 07:12:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396732; x=1729001532; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=k+vaodEh/Yx/Ff4Tz8iCfMqaXhTzdOjL/w83oLvkHm4=; b=SwSxFzLQNAxKVG/NnKtJMTkfV5XITF4HuKESgl8W2X4JX1Hraecna8WW6UXwsyXuhy QAwWxEaNIttOdJy1MWwsLD3UFzZ17BIenWGZH5sQbgDWsuTUnqPnPraSjagOqRcuHUFa OTRdWoxaatjoP2GYMVmpjBk8Tmwa0nChYVwpDfO/58c6BzRgje2T//adPBislYjJzqFP W/avrU7SZzb7IhGYlwn7hAXshWb4Qe7Aq7XPgswyXdfVkOvyzCLArihqbSmn5JvLX0jV +BS3QwZdB1qjvp1lMwcfJ1MhRT5X6yKvbJz/Pc3/vdfmVedSRuqga1mF7Kl2xbU5zTRX 8dgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396732; x=1729001532; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=k+vaodEh/Yx/Ff4Tz8iCfMqaXhTzdOjL/w83oLvkHm4=; b=UcdwkZisY91+qeYAzZ8WeIRqU2DpkpzHHoVJFY98qyx7AZ8XWCdIKQN6zuz23UbFQj q9eGAzwhPLydMLJplc6Agi2DVUHFQuJNdCmbcILzy1doMUXHbX+e8goHl9nNjeAuwZA3 +nLVQI6mRLXWImcr0Fv2Uq5dz/8SXy4J+YnbLg4ssMXJ4u5NYwZDkzSNki2sa/JCojAb aKECEGaG6pbMerfH9bsDcAQLJ9N22x9hoGv4jqWl5v5ohsHZ/IrjdKFJW+jjHitAMX62 lH72rwdFuNd3O6SG3koOAeA5Gnp5gBAtDCXhK0MkahjNj+vaFYBmIxLI6hPEkdCoWEAf duig== X-Gm-Message-State: AOJu0Yy+bajlU+TjNNJpDD6dX9g3gYqzBaUHdWooPdnUkGjpBBYmxrLs Wwmy36kZZsCghHOn4rbgT1MZpqF0cF4q+ehzBSdzLrXldz6DIl5Dj3lMLg== X-Google-Smtp-Source: AGHT+IGb95U3hBZxv4DA6Ht9rVKOCGzC1q6O9f48+blfcxt1AeqgKzdJ2dfVhcJW1N+Bf5zqGQRIPg== X-Received: by 2002:a05:6512:1589:b0:539:93b2:1372 with SMTP id 2adb3069b0e04-539ab8c218emr6584004e87.51.1728396731410; Tue, 08 Oct 2024 07:12:11 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a997ee645fbsm44872366b.133.2024.10.08.07.12.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:11 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:53 +0000 Subject: [PATCH 07/17] pack-objects: extract should_attempt_deltas() Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee This will be helpful in a future change that introduces a new way to compute deltas. Be careful to preserve the nr_deltas counting logic in the existing method, but take the rest of the logic wholesale. Signed-off-by: Derrick Stolee --- builtin/pack-objects.c | 53 +++++++++++++++++++++++------------------- 1 file changed, 29 insertions(+), 24 deletions(-) diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 0fc0680b402..82f4ca04000 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -3167,6 +3167,33 @@ static int add_ref_tag(const char *tag UNUSED, const char *referent UNUSED, cons return 0; } +static int should_attempt_deltas(struct object_entry *entry) +{ + if (DELTA(entry)) + return 0; + + if (!entry->type_valid || + oe_size_less_than(&to_pack, entry, 50)) + return 0; + + if (entry->no_try_delta) + return 0; + + if (!entry->preferred_base) { + if (oe_type(entry) < 0) + die(_("unable to get type of object %s"), + oid_to_hex(&entry->idx.oid)); + } else if (oe_type(entry) < 0) { + /* + * This object is not found, but we + * don't have to include it anyway. + */ + return 0; + } + + return 1; +} + static void prepare_pack(int window, int depth) { struct object_entry **delta_list; @@ -3197,33 +3224,11 @@ static void prepare_pack(int window, int depth) for (i = 0; i < to_pack.nr_objects; i++) { struct object_entry *entry = to_pack.objects + i; - if (DELTA(entry)) - /* This happens if we decided to reuse existing - * delta from a pack. "reuse_delta &&" is implied. - */ - continue; - - if (!entry->type_valid || - oe_size_less_than(&to_pack, entry, 50)) + if (!should_attempt_deltas(entry)) continue; - if (entry->no_try_delta) - continue; - - if (!entry->preferred_base) { + if (!entry->preferred_base) nr_deltas++; - if (oe_type(entry) < 0) - die(_("unable to get type of object %s"), - oid_to_hex(&entry->idx.oid)); - } else { - if (oe_type(entry) < 0) { - /* - * This object is not found, but we - * don't have to include it anyway. - */ - continue; - } - } delta_list[n++] = entry; } From patchwork Tue Oct 8 14:11:54 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13826563 Received: from mail-ed1-f54.google.com (mail-ed1-f54.google.com [209.85.208.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 21B791DFE0D for ; Tue, 8 Oct 2024 14:12:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396737; cv=none; b=Fay8Zfte7NyANfi4wH884tqpcDwzApw3iAeCUnrYtuH+C0advJS3u+njNBXwbx2ecjOVRU7MIoCiyVC7+eUV0lQVjswCxu7hnbMWwkUJ29CwhRDEQaoS/FdATsRrwBjWMZ0no7IO2ZvygEysRpX440f87n1M91QZYsfnz11tYIs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728396737; c=relaxed/simple; bh=gH/98lVyPPiKwu8q/MqA+CPSSvQp8qmW1wOySMXepYw=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=llm/FfJ1ITZTDLdjVgg0XlpfkexPl3HU0v4jwZk3u4ZcUMPTEc4lKJx1psw/ydeRShzEmarMt57/FlQbcYOv9KJhEsMV9cES7br/oVpb6Xc6g4dSygXa4nWfGisUtqM2nf7ykmfJpKwncMqYblPSJj5Z6tuLAS18FqrkpYLCzeA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=iasJJ3Jw; arc=none smtp.client-ip=209.85.208.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="iasJJ3Jw" Received: by mail-ed1-f54.google.com with SMTP id 4fb4d7f45d1cf-5c915308486so478751a12.0 for ; Tue, 08 Oct 2024 07:12:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728396733; x=1729001533; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=ZL33WxIVg/i1aIggp6yQ/0v5qyXw7yClyCM1pjCQmlc=; b=iasJJ3JwK0rJWhTha7moZLx1G7AKBCHMSu8lak9mVettVaA+soNRuid7rmN12HHkil XtdVbTlOhTUO/mPQlAVMzxjI9gg7f6BBJFVseQs8xYlkpEHQ4/Z/+nzwTt/FNdRpAeSd zBsP0+OdVc131FPKjteFjMvL+dRxz6hYAjpIQqEU5IvVbJfPUEhmQZeQCz1scULMlFTg Y/XpDRlGWrVFz2ErxMiG5hX9H8OuOAG2rps5Y16aeT0MS15bwziEpRJarYCymSyEhec6 lYosSdQLn0zOjh/C23Wu6QkFPjKY0ozIHvGo57VabQ2VFG4/HzF7AxQVdcZjgzTFFJwt KGQg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728396733; x=1729001533; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ZL33WxIVg/i1aIggp6yQ/0v5qyXw7yClyCM1pjCQmlc=; b=JrRnt7HhXVKhB9M4T4hmYSDZXdk4IY0bHiGXxgIjGtBl2ny1zCDL+P7VwYbYlr5bmT DM4O0rlMipxvJr4sRbiXoq+aWTSZh3Rok4LuHTH4SWrTPJR2qmPS83Lo2M7N6cENrCRR P7Ce4TFHySOrOE/LL5/rKGrspTpPXvLka1pSNAK8U9heq8kVDffjmf+QjOIZaBDIwe3q oITKa9olj91lvg9XeT/fzTK0BlSSlJjFb32S1z7LGniQN8aqkI7xo4Qic01P12X7c43J QaHNksH+2UH3cZJSC+f0LoPkrzDnLf6mjtqixigwd3/1Cq2bGy3RzP1nph6qbaNTvVXK onVQ== X-Gm-Message-State: AOJu0YxoSD+Xq9RWn3yVrsBH6XBS784yW9vT4gAt/e64AZ+6QNjvYJjT hPR/B4+Zskj92WHJBY5SyTbnprhhCJ0Ipq1uLvpgHujLv26T1DEaVJxfrw== X-Google-Smtp-Source: AGHT+IHwbTybGZFamT7HdC68JzCSFOMOYCS/cK6FTYdZzc2UCzfObCIW6yTSU8CP3sb1M+nDzC0tEA== X-Received: by 2002:a05:6402:520b:b0:5c2:439d:2042 with SMTP id 4fb4d7f45d1cf-5c8d2dfbf37mr14392123a12.5.1728396732938; Tue, 08 Oct 2024 07:12:12 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5c8e05eb7f0sm4359171a12.72.2024.10.08.07.12.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Oct 2024 07:12:11 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Tue, 08 Oct 2024 14:11:54 +0000 Subject: [PATCH 08/17] pack-objects: add --path-walk option Fcc: Sent Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, christian.couder@gmail.com, kristofferhaugsbakk@fastmail.com, Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee In order to more easily compute delta bases among objects that appear at the exact same path, add a --path-walk option to 'git pack-objects'. This option will use the path-walk API instead of the object walk given by the revision machinery. Since objects will be provided in batches representing a common path, those objects can be tested for delta bases immediately instead of waiting for a sort of the full object list by name-hash. This has multiple benefits, including avoiding collisions by name-hash. The objects marked as UNINTERESTING are included in these batches, so we are guaranteeing some locality to find good delta bases. After the individual passes are done on a per-path basis, the default name-hash is used to find other opportunistic delta bases that did not match exactly by the full path name. The current implementation performs delta calculations while walking objects, which is not ideal for a few reasons. First, this will cause the "Enumerating objects" phase to be much longer than usual. Second, it does not take advantage of threading during the path-scoped delta calculations. Even with this lack of threading, the path-walk option is sometimes faster than the usual approach. Future changes will refactor this code to allow for threading, but that complexity is deferred until later to keep this patch as simple as possible. This new walk is incompatible with some features and is ignored by others: * Object filters are not currently integrated with the path-walk API, such as sparse-checkout or tree depth. A blobless packfile could be integrated easily, but that is deferred for later. * Server-focused features such as delta islands, shallow packs, and using a bitmap index are incompatible with the path-walk API. * The path walk API is only compatible with the --revs option, not taking object lists or pack lists over stdin. These alternative ways to specify the objects currently ignores the --path-walk option without even a warning. Future changes will create performance tests that demonstrate the power of this approach. Signed-off-by: Derrick Stolee --- Documentation/git-pack-objects.txt | 13 +- Documentation/technical/api-path-walk.txt | 3 +- builtin/pack-objects.c | 147 ++++++++++++++++++++-- t/t5300-pack-object.sh | 17 +++ 4 files changed, 169 insertions(+), 11 deletions(-) diff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt index e32404c6aae..f2fda800a43 100644 --- a/Documentation/git-pack-objects.txt +++ b/Documentation/git-pack-objects.txt @@ -15,7 +15,8 @@ SYNOPSIS [--revs [--unpacked | --all]] [--keep-pack=] [--cruft] [--cruft-expiration=