From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
This patch series implements a new iteration paradigm for iterating
over references using iterators. This approach was proposed earlier as
an RFC [1].
The justification for this change is laid out in the RFC [1] and in
the commit message for patch 09/13 [2]. Please refer to those, as I
won't repeat them here.
There are several obvious followup steps that are not included in this
patch series (because they don't help with the initial transition to
pluggable reference backends). I've written prototypes of several of
these:
* The iterator interface could be made public and callers could start
using it directly.
* A filter_ref_iterator could let references be filtered based on a
callback function (this would be useful, for example, for
for_each_glob_ref()).
* A single_ref_iterator could "iterate" over a single reference (e.g.,
HEAD).
* A series_ref_iterator could iterate over multiple iterators, for
callers that want to operate on, say, HEAD plus all branches.
* The ref_cache could be fed from an iterator, to better decouple
caching from reading packed and loose references, and to make it
easy to use caching with other reference storage backends.
* Per-worktree refs could be overlaid on top of shared references
using merge_ref_iterator rather than mixing them up in the same
ref_cache.
* The dir_iterator could be used in more places; for example, when
reading loose references from disk.
Table of contents of changes:
* The first eight patches are cleanups.
* Patch 05/13 fixes a code path that unlinks symrefs directly
instead of using the refs API.
* Patch 09/13 is the most important part of this series. It introduces
not only reference iterators, but also (1) a pattern that other
iterator interfaces can follow (along with some useful constants in
iterator.h), and (2) a pattern for building OO code with
inheritance.
* Patch 10/13 actually uses the new reference iteration mechanism.
* Patch 11/13 avoids aborting reflog iterations if an unexpected file
is found under `$GIT_DIR/logs`. This fixes a bug that could cause
objects needed by reflogs to be pruned, breaking the reflogs.
* Patch 12/13 adds an iterator interface for iterating over
directories (using the same model as patch 09/13).
* Patch 13/13 implements for_each_reflog() on top of an iterator
interface (essentially the analogue of patch 10/13, but for
reflogs).
Note that it is not necessary to rebuild for_each_reflog_ent() on top
of iterators at this time, because that function deals with only a
single reference at a time. Therefore, composability is not important
here (for example, it won't have to deal with multiple refs backends
at the same time).
This patch series applies on top of mh/split-under-lock. It is also
available from my GitHub repository [3] as branch "ref-iterators".
I haven't yet completely rebased the ref-store changes (virtualization
of the refs API) on top of all of these changes, but I will work on
that next.
Michael
[1] http://thread.gmane.org/gmane.comp.version-control.git/290409
[2] http://mid.gmane.org/89634d216544d1102dafd5d18247bff2581d48a8.1464537050.git.mhagger@alum.mit.edu
[3] https://github.com/mhagger/git
Michael Haggerty (13):
refs: remove unnecessary "extern" keywords
do_for_each_ref(): move docstring to the header file
refs: use name "prefix" consistently
delete_refs(): add a flags argument
remote rm: handle symbolic refs correctly
get_ref_cache(): only create an instance if there is a submodule
entry_resolves_to_object(): rename function from
ref_resolves_to_object()
ref_resolves_to_object(): new function
refs: introduce an iterator interface
do_for_each_ref(): reimplement using reference iteration
for_each_reflog(): don't abort for bad references
dir_iterator: new API for iterating over a directory tree
for_each_reflog(): reimplement using iterators
Makefile | 2 +
builtin/fetch.c | 2 +-
builtin/remote.c | 8 +-
dir-iterator.c | 180 +++++++++++++++
dir-iterator.h | 86 +++++++
iterator.h | 81 +++++++
refs.c | 20 ++
refs.h | 139 +++++++-----
refs/files-backend.c | 630 +++++++++++++++++++++++++++++++--------------------
refs/iterator.c | 376 ++++++++++++++++++++++++++++++
refs/refs-internal.h | 225 +++++++++++++++++-
11 files changed, 1427 insertions(+), 322 deletions(-)
create mode 100644 dir-iterator.c
create mode 100644 dir-iterator.h
create mode 100644 iterator.h
create mode 100644 refs/iterator.c
--
2.8.1
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
There's continuing work in this area, so clean up unneeded "extern"
keywords rather than schlepping them around. Also split up some overlong
lines and add parameter names in a couple of places.
Signed-off-by: Michael Haggerty <redacted>
---
refs.h | 132 +++++++++++++++++++++++++++++++++++------------------------------
1 file changed, 72 insertions(+), 60 deletions(-)
@@ -74,24 +74,25 @@ extern int is_branch(const char *refname);*Symbolicreferencesareconsideredunpeelable,evenifthey*ultimatelyresolvetoapeelabletag.*/-externintpeel_ref(constchar*refname,unsignedchar*sha1);+intpeel_ref(constchar*refname,unsignedchar*sha1);/***Resolverefnameinthenested"gitlink"repositorythatislocated*atpath.Iftheresolutionissuccessful,return0andsetsha1to*thenameoftheobject;otherwise,returnanon-zerovalue.*/-externintresolve_gitlink_ref(constchar*path,constchar*refname,unsignedchar*sha1);+intresolve_gitlink_ref(constchar*path,constchar*refname,+unsignedchar*sha1);/**Returntrueiffabbrev_nameisapossibleabbreviationfor*full_nameaccordingtotherulesdefinedbyref_rev_parse_rulesin*refs.c.*/-externintrefname_match(constchar*abbrev_name,constchar*full_name);+intrefname_match(constchar*abbrev_name,constchar*full_name);-externintdwim_ref(constchar*str,intlen,unsignedchar*sha1,char**ref);-externintdwim_log(constchar*str,intlen,unsignedchar*sha1,char**ref);+intdwim_ref(constchar*str,intlen,unsignedchar*sha1,char**ref);+intdwim_log(constchar*str,intlen,unsignedchar*sha1,char**ref);/**Aref_transactionrepresentsacollectionofrefupdates
@@ -182,38 +183,45 @@ typedef int each_ref_fn(const char *refname,*modifiesthereferencealsoreturnsanonzerovaluetoimmediately*stoptheiteration.*/-externinthead_ref(each_ref_fnfn,void*cb_data);-externintfor_each_ref(each_ref_fnfn,void*cb_data);-externintfor_each_ref_in(constchar*prefix,each_ref_fnfn,void*cb_data);-externintfor_each_fullref_in(constchar*prefix,each_ref_fnfn,void*cb_data,unsignedintbroken);-externintfor_each_tag_ref(each_ref_fnfn,void*cb_data);-externintfor_each_branch_ref(each_ref_fnfn,void*cb_data);-externintfor_each_remote_ref(each_ref_fnfn,void*cb_data);-externintfor_each_replace_ref(each_ref_fnfn,void*cb_data);-externintfor_each_glob_ref(each_ref_fnfn,constchar*pattern,void*cb_data);-externintfor_each_glob_ref_in(each_ref_fnfn,constchar*pattern,constchar*prefix,void*cb_data);+inthead_ref(each_ref_fnfn,void*cb_data);+intfor_each_ref(each_ref_fnfn,void*cb_data);+intfor_each_ref_in(constchar*prefix,each_ref_fnfn,void*cb_data);+intfor_each_fullref_in(constchar*prefix,each_ref_fnfn,void*cb_data,+unsignedintbroken);+intfor_each_tag_ref(each_ref_fnfn,void*cb_data);+intfor_each_branch_ref(each_ref_fnfn,void*cb_data);+intfor_each_remote_ref(each_ref_fnfn,void*cb_data);+intfor_each_replace_ref(each_ref_fnfn,void*cb_data);+intfor_each_glob_ref(each_ref_fnfn,constchar*pattern,void*cb_data);+intfor_each_glob_ref_in(each_ref_fnfn,constchar*pattern,+constchar*prefix,void*cb_data);-externinthead_ref_submodule(constchar*submodule,each_ref_fnfn,void*cb_data);-externintfor_each_ref_submodule(constchar*submodule,each_ref_fnfn,void*cb_data);-externintfor_each_ref_in_submodule(constchar*submodule,constchar*prefix,+inthead_ref_submodule(constchar*submodule,each_ref_fnfn,void*cb_data);+intfor_each_ref_submodule(constchar*submodule,+each_ref_fnfn,void*cb_data);+intfor_each_ref_in_submodule(constchar*submodule,constchar*prefix,each_ref_fnfn,void*cb_data);-externintfor_each_tag_ref_submodule(constchar*submodule,each_ref_fnfn,void*cb_data);-externintfor_each_branch_ref_submodule(constchar*submodule,each_ref_fnfn,void*cb_data);-externintfor_each_remote_ref_submodule(constchar*submodule,each_ref_fnfn,void*cb_data);+intfor_each_tag_ref_submodule(constchar*submodule,+each_ref_fnfn,void*cb_data);+intfor_each_branch_ref_submodule(constchar*submodule,+each_ref_fnfn,void*cb_data);+intfor_each_remote_ref_submodule(constchar*submodule,+each_ref_fnfn,void*cb_data);-externinthead_ref_namespaced(each_ref_fnfn,void*cb_data);-externintfor_each_namespaced_ref(each_ref_fnfn,void*cb_data);+inthead_ref_namespaced(each_ref_fnfn,void*cb_data);+intfor_each_namespaced_ref(each_ref_fnfn,void*cb_data);/* can be used to learn about broken ref and symref */-externintfor_each_rawref(each_ref_fnfn,void*cb_data);+intfor_each_rawref(each_ref_fnfn,void*cb_data);staticinlineconstchar*has_glob_specials(constchar*pattern){returnstrpbrk(pattern,"?*[");}-externvoidwarn_dangling_symref(FILE*fp,constchar*msg_fmt,constchar*refname);-externvoidwarn_dangling_symrefs(FILE*fp,constchar*msg_fmt,conststructstring_list*refnames);+voidwarn_dangling_symref(FILE*fp,constchar*msg_fmt,constchar*refname);+voidwarn_dangling_symrefs(FILE*fp,constchar*msg_fmt,+conststructstring_list*refnames);/**Flagsforcontrollingbehaviourofpack_refs()
@@ -245,13 +253,13 @@ int pack_refs(unsigned int flags);intsafe_create_reflog(constchar*refname,intforce_create,structstrbuf*err);/** Reads log for the value of ref during at_time. **/-externintread_ref_at(constchar*refname,unsignedintflags,-unsignedlongat_time,intcnt,-unsignedchar*sha1,char**msg,-unsignedlong*cutoff_time,int*cutoff_tz,int*cutoff_cnt);+intread_ref_at(constchar*refname,unsignedintflags,+unsignedlongat_time,intcnt,+unsignedchar*sha1,char**msg,+unsignedlong*cutoff_time,int*cutoff_tz,int*cutoff_cnt);/** Check if a particular reflog exists */-externintreflog_exists(constchar*refname);+intreflog_exists(constchar*refname);/**Deletethespecifiedreference.Ifold_sha1isnon-NULL,then
@@ -260,21 +268,25 @@ extern int reflog_exists(const char *refname);*exists,regardlessofitsoldvalue.Itisanerrorforold_sha1to*beNULL_SHA1.flagsispassedthroughtoref_transaction_delete().*/-externintdelete_ref(constchar*refname,constunsignedchar*old_sha1,-unsignedintflags);+intdelete_ref(constchar*refname,constunsignedchar*old_sha1,+unsignedintflags);/**Deletethespecifiedreferences.Ifthereareanyproblems,emit*errorsbutattempttokeepgoing(i.e.,thedeletesarenotdonein*anall-or-nothingtransaction).*/-externintdelete_refs(structstring_list*refnames);+intdelete_refs(structstring_list*refnames);/** Delete a reflog */-externintdelete_reflog(constchar*refname);+intdelete_reflog(constchar*refname);/* iterate over reflog entries */-typedefinteach_reflog_ent_fn(unsignedchar*osha1,unsignedchar*nsha1,constchar*,unsignedlong,int,constchar*,void*);+typedefinteach_reflog_ent_fn(+unsignedchar*old_sha1,unsignedchar*new_sha1,+constchar*committer,unsignedlongtimestamp,+inttz,constchar*msg,void*cb_data);+intfor_each_reflog_ent(constchar*refname,each_reflog_ent_fnfn,void*cb_data);intfor_each_reflog_ent_reverse(constchar*refname,each_reflog_ent_fnfn,void*cb_data);
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
In the context of the for_each_ref() functions, call the prefix that
references must start with "prefix". (In some places it was called
"base".) This is clearer, and also prevents confusion with another
planned use of the word "base".
Signed-off-by: Michael Haggerty <redacted>
---
refs/files-backend.c | 24 ++++++++++++------------
refs/refs-internal.h | 14 +++++++-------
2 files changed, 19 insertions(+), 19 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
Use the reference iterator interface to implement do_for_each_ref().
Delete a bunch of code supporting the old for_each_ref() implementation.
And now that do_for_each_ref() is generic code (it is no longer tied to
the files backend), move it to refs.c.
The implementation is via a new function, do_for_each_ref_iterator(),
which takes a reference iterator as argument and calls a callback
function for each of the references in the iterator.
This change requires the current_ref performance hack for peel_ref() to
be implemented via ref_iterator_peel() rather than peel_entry() because
we don't have a ref_entry handy (it is hidden under three layers:
file_ref_iterator, merge_ref_iterator, and cache_ref_iterator). So:
* do_for_each_ref_iterator() records the active iterator in
current_ref_iter while it is running.
* peel_ref() checks whether current_ref_iter is pointing at the
requested reference. If so, it asks the iterator to peel the
reference (which it can do efficiently via its "peel" virtual
function). For extra safety, we do the optimization only if the
refname *addresses* are the same, not only if the refname *strings*
are the same, to forestall possible mixups between refnames that come
from different ref_iterators.
Please note that this optimization of peel_ref() is only available when
iterating via do_for_each_ref_iterator() (including all of the
for_each_ref() functions, which call it indirectly). It would be
complicated to implement a similar optimization when iterating directly
using a reference iterator, because multiple reference iterators can be
in use at the same time, with interleaved calls to
ref_iterator_advance(). (In fact we do exactly that in
merge_ref_iterator.)
But that is not necessary. peel_ref() is only called while iterating
over references. Callers who iterate using the for_each_ref() functions
benefit from the optimization described above. Callers who iterate using
reference iterators directly have access to the ref_iterator, so they
can call ref_iterator_peel() themselves to get an analogous optimization
in a more straightforward manner.
If we rewrite all callers to use the reference iteration API, then we
can remove the current_ref_iter hack permanently.
Signed-off-by: Michael Haggerty <redacted>
---
refs.c | 20 +++++
refs/files-backend.c | 206 ++-------------------------------------------------
refs/iterator.c | 29 ++++++++
refs/refs-internal.h | 33 ++++++---
4 files changed, 76 insertions(+), 212 deletions(-)
@@ -542,53 +542,8 @@ static int entry_resolves_to_object(struct ref_entry *entry)&entry->u.value.oid,entry->flag);}-/*-*current_refisaperformancehack:wheniteratingoverreferences-*usingthefor_each_ref*()functions,current_refissettothe-*currentreference'sentrybeforecallingthecallbackfunction.If-*thecallbackfunctioncallspeel_ref(),thenpeel_ref()first-*checkswhetherthereferencetobepeeledisthecurrentreference-*(itusuallyis)andifso,returnsthatreference'speeledversion-*ifitisavailable.Thisavoidsarefnamelookupinacommoncase.-*/-staticstructref_entry*current_ref;-typedefinteach_ref_entry_fn(structref_entry*entry,void*cb_data);-structref_entry_cb{-constchar*prefix;-inttrim;-intflags;-each_ref_fn*fn;-void*cb_data;-};--/*-*Handleonereferenceinado_for_each_ref*()-styleiteration,-*callinganeach_ref_fnforeachentry.-*/-staticintdo_one_ref(structref_entry*entry,void*cb_data)-{-structref_entry_cb*data=cb_data;-structref_entry*old_current_ref;-intretval;--if(!starts_with(entry->name,data->prefix))-return0;--if(!(data->flags&DO_FOR_EACH_INCLUDE_BROKEN)&&-!entry_resolves_to_object(entry))-return0;--/* Store the old value, in case this is a recursive call: */-old_current_ref=current_ref;-current_ref=entry;-retval=data->fn(entry->name+data->trim,&entry->u.value.oid,-entry->flag,data->cb_data);-current_ref=old_current_ref;-returnretval;-}-/**Callfnforeachreferenceindirthathasindexintherange*offset<=index<dir->nr.Recurseintosubdirectoriesthatarein
@@ -618,78 +573,6 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,}/*-*Callfnforeachreferenceintheunionofdir1anddir2,inorder-*byrefname.Recurseintosubdirectories.Ifavalueentryappears-*inbothdir1anddir2,thenonlyprocesstheversionthatisin-*dir2.Theinputdirsmustalreadybesorted,butsubdirswillbe-*sortedasneeded.fniscalledforallreferences,including-*brokenones.-*/-staticintdo_for_each_entry_in_dirs(structref_dir*dir1,-structref_dir*dir2,-each_ref_entry_fnfn,void*cb_data)-{-intretval;-inti1=0,i2=0;--assert(dir1->sorted==dir1->nr);-assert(dir2->sorted==dir2->nr);-while(1){-structref_entry*e1,*e2;-intcmp;-if(i1==dir1->nr){-returndo_for_each_entry_in_dir(dir2,i2,fn,cb_data);-}-if(i2==dir2->nr){-returndo_for_each_entry_in_dir(dir1,i1,fn,cb_data);-}-e1=dir1->entries[i1];-e2=dir2->entries[i2];-cmp=strcmp(e1->name,e2->name);-if(cmp==0){-if((e1->flag&REF_DIR)&&(e2->flag&REF_DIR)){-/* Both are directories; descend them in parallel. */-structref_dir*subdir1=get_ref_dir(e1);-structref_dir*subdir2=get_ref_dir(e2);-sort_ref_dir(subdir1);-sort_ref_dir(subdir2);-retval=do_for_each_entry_in_dirs(-subdir1,subdir2,fn,cb_data);-i1++;-i2++;-}elseif(!(e1->flag&REF_DIR)&&!(e2->flag&REF_DIR)){-/* Both are references; ignore the one from dir1. */-retval=fn(e2,cb_data);-i1++;-i2++;-}else{-die("conflict between reference and directory: %s",-e1->name);-}-}else{-structref_entry*e;-if(cmp<0){-e=e1;-i1++;-}else{-e=e2;-i2++;-}-if(e->flag&REF_DIR){-structref_dir*subdir=get_ref_dir(e);-sort_ref_dir(subdir);-retval=do_for_each_entry_in_dir(-subdir,0,fn,cb_data);-}else{-retval=fn(e,cb_data);-}-}-if(retval)-returnretval;-}-}--/**Loadalloftherefsfromthedirintoourin-memorycache.Thehardwork*ofloadinglooserefsisdonebyget_ref_dir(),sowejustneedtorecurse*throughallofthesub-directories.Wedonotevenneedtocareabout
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
Extract new function ref_resolves_to_object() from
entry_resolves_to_object(). It can be used even if there is no ref_entry
at hand.
Signed-off-by: Michael Haggerty <redacted>
---
refs/files-backend.c | 33 +++++++++++++++++++++++----------
1 file changed, 23 insertions(+), 10 deletions(-)
@@ -513,19 +513,32 @@ static void sort_ref_dir(struct ref_dir *dir)}/*-*Returntrueiffthereferencedescribedbyentrycanberesolvedto-*anobjectinthedatabase.Emitawarningifthereferred-to-*objectdoesnotexist.+*Returntrueifrefname,whichhasthespecifiedoidandflags,can+*beresolvedtoanobjectinthedatabase.Ifthereferred-toobject+*doesnotexist,emitawarningandreturnfalse.+*/+staticintref_resolves_to_object(constchar*refname,+conststructobject_id*oid,+unsignedintflags)+{+if(flags&REF_ISBROKEN)+return0;+if(!has_sha1_file(oid->hash)){+error("%s does not point to a valid object!",refname);+return0;+}+return1;+}++/*+*Returntrueifthereferencedescribedbyentrycanberesolvedto+*anobjectinthedatabase;otherwise,emitawarningandreturn+*false.*/staticintentry_resolves_to_object(structref_entry*entry){-if(entry->flag&REF_ISBROKEN)-return0;-if(!has_sha1_file(entry->u.value.oid.hash)){-error("%s does not point to a valid object!",entry->name);-return0;-}-return1;+returnref_resolves_to_object(entry->name,+&entry->u.value.oid,entry->flag);}/*
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
If there is not a nonbare repository where a submodule is supposedly
located, then don't instantiate a ref_cache for it.
The analogous check can be removed from resolve_gitlink_ref().
Signed-off-by: Michael Haggerty <redacted>
---
This doesn't actually reduce the number of ref_cache instances
generated by out test suite, but it is a more logical place for
the check that was added in
a2d5156c resolve_gitlink_ref: ignore non-repository paths
refs/files-backend.c | 33 ++++++++++++++++++++++-----------
1 file changed, 22 insertions(+), 11 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
Free up the old name for a more general purpose.
Signed-off-by: Michael Haggerty <redacted>
---
refs/files-backend.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
@@ -563,7 +563,7 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)return0;if(!(data->flags&DO_FOR_EACH_INCLUDE_BROKEN)&&-!ref_resolves_to_object(entry))+!entry_resolves_to_object(entry))return0;/* Store the old value, in case this is a recursive call: */
@@ -2228,7 +2228,7 @@ static int pack_if_possible_fn(struct ref_entry *entry, void *cb_data)return0;/* Do not pack symbolic or broken refs: */-if((entry->flag&REF_ISSYMREF)||!ref_resolves_to_object(entry))+if((entry->flag&REF_ISSYMREF)||!entry_resolves_to_object(entry))return0;/* Add a packed ref cache entry equivalent to the loose entry. */
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
If there is a file under "$GIT_DIR/logs" with no corresponding
reference, the old code was emitting an error message, aborting the
reflog iteration, and returning -1. But
* None of the callers was checking the exit value
* The callers all want to find all legitimate reflogs (sometimes for the
purpose of determining object reachability!) and wouldn't benefit from
a truncated iteration anyway.
So instead, emit an error message and skip the "broken" reflog, but
continue with the iteration.
Signed-off-by: Michael Haggerty <redacted>
---
refs/files-backend.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
Allow references with reflogs to be iterated over using a ref_iterator.
The latter is implemented as a files_reflog_iterator, which in turn uses
dir_iterator to read the "logs" directory.
Note that reflog iteration doesn't correctly handle per-worktree
reflogs (either before or after this patch).
Signed-off-by: Michael Haggerty <redacted>
---
refs/files-backend.c | 113 ++++++++++++++++++++++++++++++++-------------------
refs/refs-internal.h | 7 ++++
2 files changed, 78 insertions(+), 42 deletions(-)
@@ -3292,60 +3293,88 @@ int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_datstrbuf_release(&sb);returnret;}-/*-*Callfnforeachrefloginthenamespaceindicatedbyname.name-*mustbeemptyorendwith'/'.Namewillbeusedasascratch-*space,butitscontentswillberestoredbeforereturn.-*/-staticintdo_for_each_reflog(structstrbuf*name,each_ref_fnfn,void*cb_data)++structfiles_reflog_iterator{+structref_iteratorbase;++structdir_iterator*dir_iterator;+structobject_idoid;+};++staticintfiles_reflog_iterator_advance(structref_iterator*ref_iterator){-DIR*d=opendir(git_path("logs/%s",name->buf));-intretval=0;-structdirent*de;-intoldlen=name->len;+structfiles_reflog_iterator*iter=+(structfiles_reflog_iterator*)ref_iterator;+structdir_iterator*diter=iter->dir_iterator;+intok;-if(!d)-returnname->len?errno:0;+while((ok=dir_iterator_advance(diter))==ITER_OK){+intflags;-while((de=readdir(d))!=NULL){-structstatst;--if(de->d_name[0]=='.')+if(!S_ISREG(diter->st.st_mode))+continue;+if(diter->basename[0]=='.')continue;-if(ends_with(de->d_name,".lock"))+if(ends_with(diter->basename,".lock"))continue;-strbuf_addstr(name,de->d_name);-if(stat(git_path("logs/%s",name->buf),&st)<0){-;/* silently ignore */-}else{-if(S_ISDIR(st.st_mode)){-strbuf_addch(name,'/');-retval=do_for_each_reflog(name,fn,cb_data);-}else{-structobject_idoid;-if(read_ref_full(name->buf,0,oid.hash,NULL))-error("bad ref for %s",name->buf);-else-retval=fn(name->buf,&oid,0,cb_data);-}-if(retval)-break;+if(read_ref_full(diter->relative_path,0,+iter->oid.hash,&flags)){+error("bad ref for %s",diter->path.buf);+continue;}-strbuf_setlen(name,oldlen);++iter->base.refname=diter->relative_path;+iter->base.oid=&iter->oid;+iter->base.flags=flags;+returnITER_OK;}-closedir(d);-returnretval;++iter->dir_iterator=NULL;+if(ref_iterator_abort(ref_iterator)==ITER_ERROR)+ok=ITER_ERROR;+returnok;+}++staticintfiles_reflog_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+die("BUG: ref_iterator_peel() called for reflog_iterator");+}++staticintfiles_reflog_iterator_abort(structref_iterator*ref_iterator)+{+structfiles_reflog_iterator*iter=+(structfiles_reflog_iterator*)ref_iterator;+intok=ITER_DONE;++if(iter->dir_iterator)+ok=dir_iterator_abort(iter->dir_iterator);++base_ref_iterator_free(ref_iterator);+returnok;+}++structref_iterator_vtablefiles_reflog_iterator_vtable={+files_reflog_iterator_advance,+files_reflog_iterator_peel,+files_reflog_iterator_abort+};++structref_iterator*files_reflog_iterator_begin(void)+{+structfiles_reflog_iterator*iter=xcalloc(1,sizeof(*iter));+structref_iterator*ref_iterator=&iter->base;++base_ref_iterator_init(ref_iterator,&files_reflog_iterator_vtable);+iter->dir_iterator=dir_iterator_begin(git_path("logs"));+returnref_iterator;}intfor_each_reflog(each_ref_fnfn,void*cb_data){-intretval;-structstrbufname;-strbuf_init(&name,PATH_MAX);-retval=do_for_each_reflog(&name,fn,cb_data);-strbuf_release(&name);-returnretval;+returndo_for_each_ref_iterator(files_reflog_iterator_begin(),+fn,cb_data);}staticintref_update_reject_duplicates(structstring_list*refnames,
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
Currently, the API for iterating over references is via a family of
for_each_ref()-type functions that invoke a callback function for each
selected reference. All of these eventually call do_for_each_ref(),
which knows how to do one thing: iterate in parallel through two
ref_caches, one for loose and one for packed refs, giving loose
references precedence over packed refs. This is rather complicated code,
and is quite specialized to the files backend. It also requires callers
to encapsulate their work into a callback function, which often means
that they have to define and use a "cb_data" struct to manage their
context.
The current design is already bursting at the seams, and will become
even more awkward in the upcoming world of multiple reference storage
backends:
* Per-worktree vs. shared references are currently handled via a kludge
in git_path() rather than iterating over each part of the reference
namespace separately and merging the results. This kludge will cease
to work when we have multiple reference storage backends.
* The current scheme is inflexible. What if we sometimes want to bypass
the ref_cache, or use it only for packed or only for loose refs? What
if we want to store symbolic refs in one type of storage backend and
non-symbolic ones in another?
In the future, each reference backend will need to define its own way of
iterating over references. The crux of the problem with the current
design is that it is impossible to compose for_each_ref()-style
iterations, because the flow of control is owned by the for_each_ref()
function. There is nothing that a caller can do but iterate through all
references in a single burst, so there is no way for it to interleave
references from multiple backends and present the result to the rest of
the world as a single compound backend.
This commit introduces a new iteration primitive for references: a
ref_iterator. A ref_iterator is a polymorphic object that a reference
storage backend can be asked to instantiate. There are three functions
that can be applied to a ref_iterator:
* ref_iterator_advance(): move to the next reference in the iteration
* ref_iterator_abort(): end the iteration before it is exhausted
* ref_iterator_peel(): peel the reference currently being looked at
Iterating using a ref_iterator leaves the flow of control in the hands
of the caller, which means that ref_iterators from multiple
sources (e.g., loose and packed refs) can be composed and presented to
the world as a single compound ref_iterator.
It also means that the backend code for implementing reference iteration
will sometimes be more complicated. For example, the
cache_ref_iterator (which iterates over a ref_cache) can't use the C
stack to recurse; instead, it must manage its own stack internally as
explicit data structures. There is also a lot of boilerplate connected
with object-oriented programming in C.
Eventually, end-user callers will be able to be written in a more
natural way—managing their own flow of control rather than having to
work via callbacks. Since there will only be a few reference backends
but there are many consumers of this API, this is a good tradeoff.
More importantly, we gain composability, and especially the possibility
of writing interchangeable parts that can work with any ref_iterator.
For example, merge_ref_iterator implements a generic way of merging the
contents of any two ref_iterators. It is used to merge loose + packed
refs as part of the implementation of the files_ref_iterator. But it
will also be possible to use it to merge other pairs of reference
sources (e.g., per-worktree vs. shared refs).
Another example is prefix_ref_iterator, which can be used to trim a
prefix off the front of reference names before presenting them to the
caller (e.g., "refs/heads/master" -> "master").
In this patch, we introduce the iterator abstraction and many utilities,
and implement a reference iterator for the files ref storage backend.
(I've written several other obvious utilities, for example a generic way
to filter references being iterated over. These will probably be useful
in the future. But they are not needed for this patch series, so I am
not including them at this time.)
In a moment we will rewrite do_for_each_ref() to work via reference
iterators (allowing some special-purpose code to be discarded), and do
something similar for reflogs. In future patch series, we will expose
the ref_iterator abstraction in the public refs API so that callers can
use it directly.
Implementation note: I tried abstracting this a layer further to allow
generic iterators (over arbitrary types of objects) and generic
utilities like a generic merge_iterator. But the implementation in C was
very cumbersome, involving (in my opinion) too much boilerplate and too
much unsafe casting, some of which would have had to be done on the
caller side. However, I did put a few iterator-related constants in a
top-level header file, iterator.h, as they will be useful in a moment to
implement iteration over directory trees and possibly other types of
iterators in the future.
Signed-off-by: Michael Haggerty <redacted>
---
Makefile | 1 +
iterator.h | 81 ++++++++++++
refs.h | 4 +-
refs/files-backend.c | 282 +++++++++++++++++++++++++++++++++++++++++
refs/iterator.c | 347 +++++++++++++++++++++++++++++++++++++++++++++++++++
refs/refs-internal.h | 193 ++++++++++++++++++++++++++++
6 files changed, 907 insertions(+), 1 deletion(-)
create mode 100644 iterator.h
create mode 100644 refs/iterator.c
@@ -0,0 +1,81 @@+#ifndef ITERATOR_H+#define ITERATOR_H++/*+*Genericconstantsrelatedtoiterators.+*/++/*+*Theattempttoadvancetheiteratorwassuccessful;theiterator+*reflectsthenewcurrententry.+*/+#define ITER_OK 0++/*+*Theiteratorisexhaustedandhasbeenfreed.+*/+#define ITER_DONE -1++/*+*Theiteratorexperiencedanerror.Theiterationhasbeenaborted+*andtheiteratorhasbeenfreed.+*/+#define ITER_ERROR -2++/*+*Returnvaluesforselectorfunctionsformergeiterators.The+*numericalvaluesoftheseconstantsareimportantandmustbe+*compatiblewithITER_DONEandITER_ERROR.+*/+enumiterator_selection{+/* End the iteration without an error: */+ITER_SELECT_DONE=ITER_DONE,++/* Report an error and abort the iteration: */+ITER_SELECT_ERROR=ITER_ERROR,++/*+*Thenextgroupofconstantsaremasksthatareuseful+*mainlyinternally.+*/++/* The LSB selects whether iter0/iter1 is the "current" iterator: */+ITER_CURRENT_SELECTION_MASK=0x01,++/* iter0 is the "current" iterator this round: */+ITER_CURRENT_SELECTION_0=0x00,++/* iter1 is the "current" iterator this round: */+ITER_CURRENT_SELECTION_1=0x01,++/* Yield the value from the current iterator? */+ITER_YIELD_CURRENT=0x02,++/* Discard the value from the secondary iterator? */+ITER_SKIP_SECONDARY=0x04,++/*+*Theconstantsthataselectorfunctionshouldusually+*return.+*/++/* Yield the value from iter0: */+ITER_SELECT_0=ITER_CURRENT_SELECTION_0|ITER_YIELD_CURRENT,++/* Yield the value from iter0 and discard the one from iter1: */+ITER_SELECT_0_SKIP_1=ITER_SELECT_0|ITER_SKIP_SECONDARY,++/* Discard the value from iter0 without yielding anything this round: */+ITER_SKIP_0=ITER_CURRENT_SELECTION_1|ITER_SKIP_SECONDARY,++/* Yield the value from iter1: */+ITER_SELECT_1=ITER_CURRENT_SELECTION_1|ITER_YIELD_CURRENT,++/* Yield the value from iter1 and discard the one from iter0: */+ITER_SELECT_1_SKIP_0=ITER_SELECT_1|ITER_SKIP_SECONDARY,++/* Discard the value from iter1 without yielding anything this round: */+ITER_SKIP_1=ITER_CURRENT_SELECTION_0|ITER_SKIP_SECONDARY+};++#endif /* ITERATOR_H */
@@ -141,7 +141,9 @@ int dwim_log(const char *str, int len, unsigned char *sha1, char **ref);structref_transaction;/*-*Bitvaluessetintheflagsargumentpassedtoeach_ref_fn():+*Bitvaluessetintheflagsargumentpassedtoeach_ref_fn()and+*storedinref_iterator::flags.Otherbitsareforinternaluse+*only:*//* Reference is a symbolic reference. */
@@ -704,6 +705,154 @@ static void prime_ref_dir(struct ref_dir *dir)}}+/*+*Alevelinthereferencehierarchythatiscurrentlybeingiterated+*through.+*/+structcache_ref_iterator_level{+/*+*Theref_dirbeingiteratedoveratthislevel.Theref_dir+*issortedbeforebeingstoredhere.+*/+structref_dir*dir;++/*+*Theindexofthecurrententrywithindir(whichmight+*itselfbeadirectory).Ifindex==-1,thentheiteration+*hasn'tyetbegun.Ifindex==dir->nr,thentheiteration+*throughthislevelisover.+*/+intindex;+};++/*+*Representaniterationthrougharef_dirinthememorycache.The+*iterationrecursesthroughsubdirectories.+*/+structcache_ref_iterator{+structref_iteratorbase;++/*+*Thenumberoflevelscurrentlyonthestack.Thisisalways+*atleast1,becausewhenitbecomeszerotheiterationis+*endedandthisstructisfreed.+*/+size_tlevels_nr;++/* The number of levels that have been allocated on the stack */+size_tlevels_alloc;++/*+*Astackoflevels.levels[0]istheuppermostlevelthatis+*beingiteratedoverinthisiteration.(Thisisnot+*necessarythetoplevelinthereferenceshierarchy.Ifwe+*areiteratingthroughasubtree,thenlevels[0]willhold+*theref_dirforthatsubtree,andsubsequentlevelswillgo+*onfromthere.)+*/+structcache_ref_iterator_level*levels;+};++staticintcache_ref_iterator_advance(structref_iterator*ref_iterator)+{+structcache_ref_iterator*iter=+(structcache_ref_iterator*)ref_iterator;++while(1){+structcache_ref_iterator_level*level=+&iter->levels[iter->levels_nr-1];+structref_dir*dir=level->dir;+structref_entry*entry;++if(level->index==-1)+sort_ref_dir(dir);++if(++level->index==level->dir->nr){+/* This level is exhausted; pop up a level */+if(--iter->levels_nr==0)+returnref_iterator_abort(ref_iterator);++continue;+}++entry=dir->entries[level->index];++if(entry->flag&REF_DIR){+/* push down a level */+ALLOC_GROW(iter->levels,iter->levels_nr+1,+iter->levels_alloc);++level=&iter->levels[iter->levels_nr++];+level->dir=get_ref_dir(entry);+sort_ref_dir(level->dir);+level->index=-1;+}else{+iter->base.refname=entry->name;+iter->base.oid=&entry->u.value.oid;+iter->base.flags=entry->flag;+returnITER_OK;+}+}+}++staticenumpeel_statuspeel_entry(structref_entry*entry,intrepeel);++staticintcache_ref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+structcache_ref_iterator*iter=+(structcache_ref_iterator*)ref_iterator;+structcache_ref_iterator_level*level;+structref_entry*entry;++level=&iter->levels[iter->levels_nr-1];++if(level->index==-1)+die("BUG: peel called before advance for cache iterator");++entry=level->dir->entries[level->index];++if(peel_entry(entry,0))+return-1;+hashcpy(peeled->hash,entry->u.value.peeled.hash);+return0;+}++staticintcache_ref_iterator_abort(structref_iterator*ref_iterator)+{+structcache_ref_iterator*iter=+(structcache_ref_iterator*)ref_iterator;++free(iter->levels);+base_ref_iterator_free(ref_iterator);+returnITER_DONE;+}++structref_iterator_vtablecache_ref_iterator_vtable={+cache_ref_iterator_advance,+cache_ref_iterator_peel,+cache_ref_iterator_abort+};++staticstructref_iterator*cache_ref_iterator_begin(structref_dir*dir)+{+structcache_ref_iterator*iter;+structref_iterator*ref_iterator;+structcache_ref_iterator_level*level;++iter=xcalloc(1,sizeof(*iter));+ref_iterator=&iter->base;+base_ref_iterator_init(ref_iterator,&cache_ref_iterator_vtable);+ALLOC_GROW(iter->levels,10,iter->levels_alloc);++iter->levels_nr=1;+level=&iter->levels[0];+level->index=-1;+level->dir=dir;++returnref_iterator;+}+structnonmatching_ref_data{conststructstring_list*skip;constchar*conflicting_refname;
@@ -1843,6 +1992,139 @@ int peel_ref(const char *refname, unsigned char *sha1)returnpeel_object(base,sha1);}+structfiles_ref_iterator{+structref_iteratorbase;++structpacked_ref_cache*packed_ref_cache;+structref_iterator*iter0;+unsignedintflags;+};++staticintfiles_ref_iterator_advance(structref_iterator*ref_iterator)+{+structfiles_ref_iterator*iter=+(structfiles_ref_iterator*)ref_iterator;+intok;++while((ok=ref_iterator_advance(iter->iter0))==ITER_OK){+if(!(iter->flags&DO_FOR_EACH_INCLUDE_BROKEN)&&+!ref_resolves_to_object(iter->iter0->refname,+iter->iter0->oid,+iter->iter0->flags))+continue;++iter->base.refname=iter->iter0->refname;+iter->base.oid=iter->iter0->oid;+iter->base.flags=iter->iter0->flags;+returnITER_OK;+}++iter->iter0=NULL;+if(ref_iterator_abort(ref_iterator)!=ITER_DONE)+ok=ITER_ERROR;++returnok;+}++staticintfiles_ref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+structfiles_ref_iterator*iter=+(structfiles_ref_iterator*)ref_iterator;++returnref_iterator_peel(iter->iter0,peeled);+}++staticintfiles_ref_iterator_abort(structref_iterator*ref_iterator)+{+structfiles_ref_iterator*iter=+(structfiles_ref_iterator*)ref_iterator;+intok=ITER_DONE;++if(iter->iter0)+ok=ref_iterator_abort(iter->iter0);++release_packed_ref_cache(iter->packed_ref_cache);+base_ref_iterator_free(ref_iterator);+returnok;+}++structref_iterator_vtablefiles_ref_iterator_vtable={+files_ref_iterator_advance,+files_ref_iterator_peel,+files_ref_iterator_abort+};++structref_iterator*files_ref_iterator_begin(+constchar*submodule,+constchar*prefix,unsignedintflags)+{+structref_cache*refs=get_ref_cache(submodule);+structref_dir*loose_dir,*packed_dir;+structref_iterator*loose_iter,*packed_iter;+structfiles_ref_iterator*iter;+structref_iterator*ref_iterator;++if(!refs)+returnempty_ref_iterator_begin();++if(ref_paranoia<0)+ref_paranoia=git_env_bool("GIT_REF_PARANOIA",0);+if(ref_paranoia)+flags|=DO_FOR_EACH_INCLUDE_BROKEN;++iter=xcalloc(1,sizeof(*iter));+ref_iterator=&iter->base;+base_ref_iterator_init(ref_iterator,&files_ref_iterator_vtable);++/*+*Wemustmakesurethatalllooserefsarereadbefore+*accessingthepacked-refsfile;thisavoidsarace+*conditioniflooserefsaremigratedtothepacked-refs+*filebyasimultaneousprocess,butourin-memoryviewis+*frombeforethemigration.Weensurethisasfollows:+*First,wecallprime_ref_dir(),whichpre-readstheloose+*referencesforthesubtreeintothecache.(Ifthey've+*alreadybeenread,that'sOK;weonlyneedtoguarantee+*thatthey'rereadbeforethepackedrefs,not*howmuch*+*before.)Afterthat,wecallget_packed_ref_cache(),which+*internallycheckswhetherthepacked-refcacheisupto+*datewithwhatisondisk,andre-readsitifnot.+*/++loose_dir=get_loose_refs(refs);++if(prefix&&*prefix)+loose_dir=find_containing_dir(loose_dir,prefix,0);++if(loose_dir){+prime_ref_dir(loose_dir);+loose_iter=cache_ref_iterator_begin(loose_dir);+}else{+/* There's nothing to iterate over. */+loose_iter=empty_ref_iterator_begin();+}++iter->packed_ref_cache=get_packed_ref_cache(refs);+acquire_packed_ref_cache(iter->packed_ref_cache);+packed_dir=get_packed_ref_dir(iter->packed_ref_cache);++if(prefix&&*prefix)+packed_dir=find_containing_dir(packed_dir,prefix,0);++if(packed_dir){+packed_iter=cache_ref_iterator_begin(packed_dir);+}else{+/* There's nothing to iterate over. */+packed_iter=empty_ref_iterator_begin();+}++iter->iter0=overlay_ref_iterator_begin(packed_iter,loose_iter);+iter->flags=flags;++returnref_iterator;+}+/**Callfnforeachreferenceinthespecifiedref_cache,omitting*referencesnotinthecontaining_dirofprefix.Callfnforall
@@ -0,0 +1,347 @@+/*+*Genericreferenceiteratorinfrastructure.Seerefs-internal.hfor+*documentationaboutthedesignanduseofreferenceiterators.+*/++#include"cache.h"+#include"refs.h"+#include"refs/refs-internal.h"+#include"iterator.h"++intref_iterator_advance(structref_iterator*ref_iterator)+{+returnref_iterator->vtable->advance(ref_iterator);+}++intref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+returnref_iterator->vtable->peel(ref_iterator,peeled);+}++intref_iterator_abort(structref_iterator*ref_iterator)+{+returnref_iterator->vtable->abort(ref_iterator);+}++voidbase_ref_iterator_init(structref_iterator*iter,+structref_iterator_vtable*vtable)+{+iter->vtable=vtable;+iter->refname=NULL;+iter->oid=NULL;+iter->flags=0;+}++voidbase_ref_iterator_free(structref_iterator*iter)+{+/* Help make use-after-free bugs fail quickly: */+iter->vtable=NULL;+free(iter);+}++structempty_ref_iterator{+structref_iteratorbase;+};++staticintempty_ref_iterator_advance(structref_iterator*ref_iterator)+{+returnref_iterator_abort(ref_iterator);+}++staticintempty_ref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+die("BUG: peel called for empty iterator");+}++staticintempty_ref_iterator_abort(structref_iterator*ref_iterator)+{+base_ref_iterator_free(ref_iterator);+returnITER_DONE;+}++staticstructref_iterator_vtableempty_ref_iterator_vtable={+empty_ref_iterator_advance,+empty_ref_iterator_peel,+empty_ref_iterator_abort+};++structref_iterator*empty_ref_iterator_begin(void)+{+structempty_ref_iterator*iter=xcalloc(1,sizeof(*iter));+structref_iterator*ref_iterator=&iter->base;++base_ref_iterator_init(ref_iterator,&empty_ref_iterator_vtable);+returnref_iterator;+}++intis_empty_ref_iterator(structref_iterator*ref_iterator)+{+returnref_iterator->vtable==&empty_ref_iterator_vtable;+}++structmerge_ref_iterator{+structref_iteratorbase;++structref_iterator*iter0,*iter1;++ref_iterator_select_fn*select;+void*cb_data;++/*+*Apointertoiter0oriter1(whicheverissupplyingthe+*currentvalue),orNULLifadvancehasnotyetbeencalled.+*/+structref_iterator**current;+};++staticintmerge_ref_iterator_advance(structref_iterator*ref_iterator)+{+structmerge_ref_iterator*iter=+(structmerge_ref_iterator*)ref_iterator;+intok;++if(!iter->current){+/* Initialize: advance both iterators to their first entries */+if((ok=ref_iterator_advance(iter->iter0))!=ITER_OK){+iter->iter0=NULL;+if(ok==ITER_ERROR)+gotoerror;+}+if((ok=ref_iterator_advance(iter->iter1))!=ITER_OK){+iter->iter1=NULL;+if(ok==ITER_ERROR)+gotoerror;+}+}else{+/*+*Advancethecurrentiteratorpastthejust-used+*entry:+*/+if((ok=ref_iterator_advance(*iter->current))!=ITER_OK){+*iter->current=NULL;+if(ok==ITER_ERROR)+gotoerror;+}+}++/* Loop until we find an entry that we can yield. */+while(1){+structref_iterator**secondary;+enumiterator_selectionselection=+iter->select(iter->iter0,iter->iter1,iter->cb_data);++if(selection==ITER_SELECT_DONE){+returnref_iterator_abort(ref_iterator);+}elseif(selection==ITER_SELECT_ERROR){+ref_iterator_abort(ref_iterator);+returnITER_ERROR;+}++if((selection&ITER_CURRENT_SELECTION_MASK)==0){+iter->current=&iter->iter0;+secondary=&iter->iter1;+}else{+iter->current=&iter->iter1;+secondary=&iter->iter0;+}++if(selection&ITER_SKIP_SECONDARY){+if((ok=ref_iterator_advance(*secondary))!=ITER_OK){+*secondary=NULL;+if(ok==ITER_ERROR)+gotoerror;+}+}++if(selection&ITER_YIELD_CURRENT){+iter->base.refname=(*iter->current)->refname;+iter->base.oid=(*iter->current)->oid;+iter->base.flags=(*iter->current)->flags;+returnITER_OK;+}+}++error:+ref_iterator_abort(ref_iterator);+returnITER_ERROR;+}++staticintmerge_ref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+structmerge_ref_iterator*iter=+(structmerge_ref_iterator*)ref_iterator;++if(!iter->current){+die("BUG: peel called before advance for merge iterator");+}+returnref_iterator_peel(*iter->current,peeled);+}++staticintmerge_ref_iterator_abort(structref_iterator*ref_iterator)+{+structmerge_ref_iterator*iter=+(structmerge_ref_iterator*)ref_iterator;+intok=ITER_DONE;++if(iter->iter0){+if(ref_iterator_abort(iter->iter0)!=ITER_DONE)+ok=ITER_ERROR;+}+if(iter->iter1){+if(ref_iterator_abort(iter->iter1)!=ITER_DONE)+ok=ITER_ERROR;+}+base_ref_iterator_free(ref_iterator);+returnok;+}++staticstructref_iterator_vtablemerge_ref_iterator_vtable={+merge_ref_iterator_advance,+merge_ref_iterator_peel,+merge_ref_iterator_abort+};++structref_iterator*merge_ref_iterator_begin(+structref_iterator*iter0,structref_iterator*iter1,+ref_iterator_select_fn*select,void*cb_data)+{+structmerge_ref_iterator*iter=xcalloc(1,sizeof(*iter));+structref_iterator*ref_iterator=&iter->base;++base_ref_iterator_init(ref_iterator,&merge_ref_iterator_vtable);+iter->iter0=iter0;+iter->iter1=iter1;+iter->select=select;+iter->cb_data=cb_data;+iter->current=NULL;+returnref_iterator;+}++/*+*Aref_iterator_select_fnthatoverlaystheitemsfromiter1ontop+*ofthosefromiter0(likelooserefsoverpackedrefs).See+*overlay_ref_iterator_begin().+*/+staticenumiterator_selectionoverlay_iterator_select(+structref_iterator*iter0,structref_iterator*iter1,+void*cb_data)+{+intcmp;++if(!iter0)+returniter1?ITER_SELECT_1:ITER_SELECT_DONE;+elseif(!iter1)+returnITER_SELECT_0;++cmp=strcmp(iter0->refname,iter1->refname);++if(cmp<0)+returnITER_SELECT_0;+elseif(cmp>0)+returnITER_SELECT_1;+else+returnITER_SELECT_1_SKIP_0;+}++structref_iterator*overlay_ref_iterator_begin(structref_iterator*iter0,+structref_iterator*iter1)+{+/*+*Optimization:ifoneoftheiteratorsisempty,returnthe+*otheroneratherthanincurringtheoverheadofwrapping+*them.+*/+if(is_empty_ref_iterator(iter0)){+ref_iterator_abort(iter0);+returniter1;+}elseif(is_empty_ref_iterator(iter1)){+ref_iterator_abort(iter1);+returniter0;+}++returnmerge_ref_iterator_begin(iter0,iter1,+overlay_iterator_select,NULL);+}++structprefix_ref_iterator{+structref_iteratorbase;++structref_iterator*iter0;+char*prefix;+inttrim;+};++staticintprefix_ref_iterator_advance(structref_iterator*ref_iterator)+{+structprefix_ref_iterator*iter=+(structprefix_ref_iterator*)ref_iterator;+intok;++while((ok=ref_iterator_advance(iter->iter0))==ITER_OK){+if(!starts_with(iter->iter0->refname,iter->prefix))+continue;++iter->base.refname=iter->iter0->refname+iter->trim;+iter->base.oid=iter->iter0->oid;+iter->base.flags=iter->iter0->flags;+returnITER_OK;+}++iter->iter0=NULL;+if(ref_iterator_abort(ref_iterator)!=ITER_DONE)+returnITER_ERROR;+returnok;+}++staticintprefix_ref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled)+{+structprefix_ref_iterator*iter=+(structprefix_ref_iterator*)ref_iterator;++returnref_iterator_peel(iter->iter0,peeled);+}++staticintprefix_ref_iterator_abort(structref_iterator*ref_iterator)+{+structprefix_ref_iterator*iter=+(structprefix_ref_iterator*)ref_iterator;+intok=ITER_DONE;++if(iter->iter0)+ok=ref_iterator_abort(iter->iter0);+free(iter->prefix);+base_ref_iterator_free(ref_iterator);+returnok;+}++staticstructref_iterator_vtableprefix_ref_iterator_vtable={+prefix_ref_iterator_advance,+prefix_ref_iterator_peel,+prefix_ref_iterator_abort+};++structref_iterator*prefix_ref_iterator_begin(structref_iterator*iter0,+constchar*prefix,+inttrim)+{+structprefix_ref_iterator*iter;+structref_iterator*ref_iterator;++if(!*prefix&&!trim)+returniter0;/* optimization: no need to wrap iterator */++iter=xcalloc(1,sizeof(*iter));+ref_iterator=&iter->base;++base_ref_iterator_init(ref_iterator,&prefix_ref_iterator_vtable);++iter->iter0=iter0;+iter->prefix=xstrdup(prefix);+iter->trim=trim;++returnref_iterator;+}
@@ -249,6 +249,199 @@ int rename_ref_available(const char *oldname, const char *newname);#define DO_FOR_EACH_INCLUDE_BROKEN 0x01/*+*Referenceiterators+*+*Areferenceiteratorencapsulatesthestateofanin-progress+*iterationoverreferences.Createaninstanceof`struct+*ref_iterator`viaoneofthefunctionsinthismodule.+*+*Afreshly-createdref_iteratordoesn'tyetpointatareference.To+*advancetheiterator,callref_iterator_advance().Ifsuccessful,+*thissetstheiterator'srefname,oid,andflagsfieldstodescribe+*thenextreferenceandreturnsITER_OK.Thedatapointedatby+*refnameandoidbelongtotheiterator;ifyouwanttoretainthem+*aftercallingref_iterator_advance()againorcalling+*ref_iterator_abort(),youmustmakeacopy.Whentheiterationhas+*beenexhausted,ref_iterator_advance()releasesanyresources+*assocatedwiththeiteration,freestheref_iteratorobject,and+*returnsITER_DONE.Ifyouwanttoaborttheiterationearly,call+*ref_iterator_abort(),whichalsofreestheref_iteratorobjectand+*anyassociatedresources.Iftherewasaninternalerroradvancing+*tothenextentry,ref_iterator_advance()abortstheiteration,+*freestheref_iterator,andreturnsITER_ERROR.+*+*Thereferencecurrentlybeinglookedatcanbepeeledbycalling+*ref_iterator_peel().Thisfunctionisoftenfasterthanpeel_ref(),+*soitshouldbepreferredwheniteratingoverreferences.+*+*Puttingitalltogether,atypicaliterationlookslikethis:+*+*intok;+*structref_iterator*iter=...;+*+*while((ok=ref_iterator_advance(iter))==ITER_OK){+*if(want_to_stop_iteration()){+*ok=ref_iterator_abort(iter);+*break;+*}+*+*// Access information about the current reference:+*if(!(iter->flags&REF_ISSYMREF))+*printf("%s is %s\n",iter->refname,oid_to_hex(&iter->oid));+*+*// If you need to peel the reference:+*ref_iterator_peel(iter,&oid);+*}+*+*if(ok!=ITER_DONE)+*handle_error();+*/+structref_iterator{+structref_iterator_vtable*vtable;+constchar*refname;+conststructobject_id*oid;+unsignedintflags;+};++/*+*AdvancetheiteratortothefirstornextitemandreturnITER_OK.+*Iftheiterationisexhausted,freetheresourcesassociatedwith+*theref_iteratorandreturnITER_DONE.Onerrors,freetheiterator+*resourcesandreturnITER_ERROR.Itisabugtouseref_iteratoror+*callthisfunctionagainafterithasreturnedfalse.+*/+intref_iterator_advance(structref_iterator*ref_iterator);++/*+*Ifpossible,peelthereferencecurrentlybeingviewedbythe+*iterator.Return0onsuccess.+*/+intref_iterator_peel(structref_iterator*ref_iterator,+structobject_id*peeled);++/*+*Endtheiterationbeforeithasbeenexhausted,freeingthe+*referenceiteratorandanyassociatedresourcesandreturning+*ITER_DONE.Iftheabortitselffailed,returnITER_ERROR.+*/+intref_iterator_abort(structref_iterator*ref_iterator);++/*+*Aniteratorovernothing(itsfirstref_iterator_advance()call+*returns0).+*/+structref_iterator*empty_ref_iterator_begin(void);++/*+*Returntrueiffref_iteratorisanempty_ref_iterator.+*/+intis_empty_ref_iterator(structref_iterator*ref_iterator);++/*+*Acallbackfunctionusedtoinstructmerge_ref_iteratorhowto+*interleavetheentriesfromiter0anditer1.Thefunctionshould+*returnoneoftheconstantsdefinedinenumiterator_selection.It+*mustnotadvanceeitheroftheiteratorsitself.+*+*Thefunctionmustbepreparedtohandlethecasethatiter0and/or+*iter1isNULL,whichindicatesthatthecorrespondingsub-iterator+*hasbeenexhausted.Itsreturnvaluemustbeconsistentwiththe+*currentstatesoftheiterators;e.g.,itmustnotreturn+*ITER_SKIP_1ifiter1hasalreadybeenexhausted.+*/+typedefenumiterator_selectionref_iterator_select_fn(+structref_iterator*iter0,structref_iterator*iter1,+void*cb_data);++/*+*Iterateovertheintriesfromiter0anditer1,withthevalues+*interleavedasdirectedbytheselectfunction.Theiteratortakes+*ownershipofiter0anditer1andfreesthemwhentheiterationis+*over.+*/+structref_iterator*merge_ref_iterator_begin(+structref_iterator*iter0,structref_iterator*iter1,+ref_iterator_select_fn*select,void*cb_data);++/*+*Aniteratorconsistingoftheunionoftheentriesfromiter0and+*iter1.Ifthereareentriescommontothetwosub-iterators,use+*theonefromiter1.Eachiteratormustiterateoveritsentriesin+*strcmp()orderbyrefnameforthistowork.+*+*Thenewiteratortakesownershipofitsargumentsandfreesthem+*whentheiterationisover.Asaconveniencetocallers,ifiter0+*oriter1is_empty_ref_iterator(),thenabortthatoneimmediately+*andreturntheotheriteratordirectly,withoutwrappingit.+*/+structref_iterator*overlay_ref_iterator_begin(structref_iterator*iter0,+structref_iterator*iter1);++/*+*Wrapiter0,onlylettingthroughthereferenceswhosenamesstart+*withprefix.Iftrimisset,setiter->refnametothenameofthe+*referencewiththatmanycharacterstrimmedoffthefront;+*otherwisesetittothefullrefname.Thenewiteratortakesover+*ownershipofiter0andfreesitwheniterationisover.Itmakes+*itsowncopyofprefix.+*+*Asanconveniencetocallers,ifprefixistheemptystringand+*trimiszero,thisfunctionreturnsiter0directly,without+*wrappingit.+*/+structref_iterator*prefix_ref_iterator_begin(structref_iterator*iter0,+constchar*prefix,+inttrim);++/*+*Iterateoverthepackedandloosereferencesinthespecified+*submodulethatarewithinfind_containing_dir(prefix).Ifprefixis+*NULLortheemptystring,iterateoverallreferencesinthe+*submodule.+*/+structref_iterator*files_ref_iterator_begin(constchar*submodule,+constchar*prefix,+unsignedintflags);++/* Internal implementation of reference iteration: */++/*+*Baseclassconstructorforref_iterators.Initializethe+*ref_iteratorpartofiter,settingitsvtablepointerasspecified.+*Thisismeanttobecalledonlybytheinitializersofderived+*classes.+*/+voidbase_ref_iterator_init(structref_iterator*iter,+structref_iterator_vtable*vtable);++/*+*Baseclassdestructorforref_iterators.Destroytheref_iterator+*partofiterandshallow-freetheobject.Thisismeanttobe+*calledonlybythedestructorsofderivedclasses.+*/+voidbase_ref_iterator_free(structref_iterator*iter);++/* Virtual function declarations for ref_iterators: */++typedefintref_iterator_advance_fn(structref_iterator*ref_iterator);++typedefintref_iterator_peel_fn(structref_iterator*ref_iterator,+structobject_id*peeled);++/*+*Implementationsofthisfunctionshouldfreeanyresourcesspecific+*tothederivedclass,thencallbase_ref_iterator_free()toclean+*upandfreetheref_iteratorobject.+*/+typedefintref_iterator_abort_fn(structref_iterator*ref_iterator);++structref_iterator_vtable{+ref_iterator_advance_fn*advance;+ref_iterator_peel_fn*peel;+ref_iterator_abort_fn*abort;+};++/**Callfnforeachreferenceinthespecifiedsubmoduleforwhichthe*refnamebeginswithprefix.Iftrimisnon-zero,thentrimthat*manycharactersoffthebeginningofeachrefnamebeforepassing
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:38
The iterator interface is modeled on that for references, though no
vtable is necessary because there is (so far?) only one type of
dir_iterator.
There are obviously a lot of features that could easily be added to this
class:
* Skip/include directory paths in the iteration
* Shallow/deep iteration
* Letting the caller decide which subdirectories to recurse into (e.g.,
via a dir_iterator_advance_into() function)
* Option to iterate in sorted order
* Option to iterate over directory paths before vs. after their contents
But these are not needed for the current patch series, so I refrain.
Signed-off-by: Michael Haggerty <redacted>
---
Makefile | 1 +
dir-iterator.c | 180 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dir-iterator.h | 86 +++++++++++++++++++++++++++
3 files changed, 267 insertions(+)
create mode 100644 dir-iterator.c
create mode 100644 dir-iterator.h
@@ -0,0 +1,180 @@+#include"cache.h"+#include"dir.h"+#include"iterator.h"+#include"dir-iterator.h"++structdir_iterator_level{+intinitialized;++DIR*dir;++/*+*Thelengthofthedirectorypartofrefnameatthislevel+*(includingthetrailing'/'):+*/+size_tprefix_len;++/*+*Thelastactionthathasbeentakenwiththecurrententry+*(neededfordirectories,whichhavetobeincludedinthe+*iterationandalsoiteratedinto):+*/+enum{+DIR_STATE_ITER,+DIR_STATE_RECURSE+}dir_state;+};++/*+*Thefulldatastructureusedtomanagetheinternaldirectory+*iterationstate.Itincludesmembersthatarenotpartofthe+*publicinterface.+*/+structdir_iterator_int{+structdir_iteratorbase;++/*+*Thenumberoflevelscurrentlyonthestack.Thisisalways+*atleast1,becausewhenitbecomeszerotheiterationis+*endedandthisstructisfreed.+*/+size_tlevels_nr;++/* The number of levels that have been allocated on the stack */+size_tlevels_alloc;++/*+*Astackoflevels.levels[0]istheuppermostdirectory+*thatwillbeincludedinthisiteration.+*/+structdir_iterator_level*levels;+};++intdir_iterator_advance(structdir_iterator*dir_iterator)+{+structdir_iterator_int*iter=+(structdir_iterator_int*)dir_iterator;++while(1){+structdir_iterator_level*level=+&iter->levels[iter->levels_nr-1];+structdirent*de;++if(!level->initialized){+if(!is_dir_sep(iter->base.path.buf[iter->base.path.len-1]))+strbuf_addch(&iter->base.path,'/');+level->prefix_len=iter->base.path.len;++/* opendir() errors are handled below */+level->dir=opendir(iter->base.path.buf);++level->initialized=1;+}elseif(S_ISDIR(iter->base.st.st_mode)){+if(level->dir_state==DIR_STATE_ITER){+/*+*Thedirectorywasjustiterated+*over;nowpreparetoiterateinto+*it.+*/+level->dir_state=DIR_STATE_RECURSE;+ALLOC_GROW(iter->levels,iter->levels_nr+1,+iter->levels_alloc);+level=&iter->levels[iter->levels_nr++];+level->initialized=0;+continue;+}else{+/*+*Thedirectoryhasalreadybeen+*iteratedoveranditeratedinto;+*we'redonewithit.+*/+}+}++if(!level->dir){+/*+*Thislevelisexhausted(orwasn'topened+*successfully);popupalevel.+*/+if(--iter->levels_nr==0){+returndir_iterator_abort(dir_iterator);+}+continue;+}++/*+*Loopuntilwefindanentrythatwecangiveback+*tothecaller:+*/+while(1){+strbuf_setlen(&iter->base.path,level->prefix_len);+de=readdir(level->dir);++if(!de){+/* This level is exhausted; pop up a level. */+closedir(level->dir);+level->dir=NULL;+if(--iter->levels_nr==0)+returndir_iterator_abort(dir_iterator);+break;+}++if(is_dot_or_dotdot(de->d_name))+continue;++strbuf_addstr(&iter->base.path,de->d_name);+if(lstat(iter->base.path.buf,&iter->base.st)<0)+continue;/* silently skip */++/*+*Wehavetosettheseeachtimebecause+*thepathstrbufmighthavebeenrealloc()ed.+*/++iter->base.relative_path=+iter->base.path.buf+iter->levels[0].prefix_len;+iter->base.basename=+iter->base.path.buf+level->prefix_len;+level->dir_state=DIR_STATE_ITER;++returnITER_OK;+}+}+}++intdir_iterator_abort(structdir_iterator*dir_iterator)+{+structdir_iterator_int*iter=(structdir_iterator_int*)dir_iterator;++while(iter->levels_nr){+structdir_iterator_level*level=+&iter->levels[--iter->levels_nr];++if(level->dir)+closedir(level->dir);+}++free(iter->levels);+strbuf_release(&iter->base.path);+free(iter);+returnITER_DONE;+}++structdir_iterator*dir_iterator_begin(constchar*path)+{+structdir_iterator_int*iter=xcalloc(1,sizeof(*iter));+structdir_iterator*dir_iterator=&iter->base;++if(!path||!*path)+die("BUG: empty path passed to dir_iterator_begin()");++strbuf_init(&iter->base.path,PATH_MAX);+strbuf_addstr(&iter->base.path,path);++ALLOC_GROW(iter->levels,10,iter->levels_alloc);++iter->levels_nr=1;+iter->levels[0].initialized=0;++returndir_iterator;+}
@@ -0,0 +1,86 @@+#ifndef DIR_ITERATOR_H+#define DIR_ITERATOR_H++/*+*Iterateoveradirectorytree.+*+*Iterateoveradirectorytree,recursively,includingpathsofall+*typesandhiddenpaths.Skip"."and".."entriesanddon'tfollow+*symlinksexceptfortheoriginalpath.+*+*Everytimedir_iterator_advance()iscalled,updatethemembersof+*thedir_iteratorstructuretoreflectthenextpathinthe+*iteration.Theorderthatpathsareiteratedoverwithina+*directoryisundefined,butdirectorypathsarealwaysiterated+*overbeforethesubdirectorycontents.+*+*Atypicaliterationlookslikethis:+*+*intok;+*structiterator*iter=dir_iterator_begin(path);+*+*while((ok=dir_iterator_advance(iter))==ITER_OK){+*if(want_to_stop_iteration()){+*ok=dir_iterator_abort(iter);+*break;+*}+*+*// Access information about the current path:+*if(S_ISDIR(iter->st.st_mode))+*printf("%s is a directory\n",iter->relative_path);+*}+*+*if(ok!=ITER_DONE)+*handle_error();+*+*Callersareallowedtomodifyiter->pathwhiletheyareworking,+*buttheymustrestoreittoitsoriginalcontentsbeforecalling+*dir_iterator_advance()again.+*/++structdir_iterator{+/* The current path: */+structstrbufpath;++/*+*Thecurrentpathrelativetothestartingpath.Thispart+*ofthepathalwaysuses"/"characterstoseparatepath+*components:+*/+constchar*relative_path;++/* The current basename: */+constchar*basename;++/* The result of calling lstat() on path: */+structstatst;+};++/*+*Startadirectoryiterationoverpath.Returnadir_iteratorthat+*holdstheinternalstateoftheiteration.+*+*Theiterationincludesallpathsunderpath,notincludingpath+*itselfandnotincluding"."or".."entries.+*+*pathisthestartingdirectory.Aninternalcopywillbemade.+*/+structdir_iterator*dir_iterator_begin(constchar*path);++/*+*AdvancetheiteratortothefirstornextitemandreturnITER_OK.+*Iftheiterationisexhausted,freetheresourcesassociatedwith+*theiteratorandreturnITER_DONE.Onerror,returnITER_ERROR.It+*isabugtouseiteratororcallthisfunctionagainafterithas+*returnedfalse.+*/+intdir_iterator_advance(structdir_iterator*iterator);++/*+*Endtheiterationbeforeithasbeenexhausted.Freethereference+*iteratorandanyassociatedresourcesandreturnITER_DONE.Return+*ITER_ERRORonerror.+*/+intdir_iterator_abort(structdir_iterator*iterator);++#endif
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:39
In the modern world of reference backends, it is not OK to delete a
symref by unlink()ing the file directly. This must be done via the refs
API.
We do so by adding the symref to the list of references to delete along
with the non-symbolic references, then calling delete_refs() with the
new flags option set to REF_NODEREF.
Signed-off-by: Michael Haggerty <redacted>
---
builtin/remote.c | 6 +-----
1 file changed, 1 insertion(+), 5 deletions(-)
@@ -539,10 +539,6 @@ static int add_branch_for_removal(const char *refname,return0;}-/* make sure that symrefs are deleted */-if(flags&REF_ISSYMREF)-returnunlink(git_path("%s",refname));-string_list_append(branches->branches,refname);return0;
@@ -704,6 +705,154 @@ static void prime_ref_dir(struct ref_dir *dir)}}+/*+*Alevelinthereferencehierarchythatiscurrentlybeingiterated+*through.+*/+structcache_ref_iterator_level{+/*+*Theref_dirbeingiteratedoveratthislevel.Theref_dir+*issortedbeforebeingstoredhere.+*/+structref_dir*dir;++/*+*Theindexofthecurrententrywithindir(whichmight+*itselfbeadirectory).Ifindex==-1,thentheiteration+*hasn'tyetbegun.Ifindex==dir->nr,thentheiteration+*throughthislevelisover.+*/+intindex;+};++/*+*Representaniterationthrougharef_dirinthememorycache.The+*iterationrecursesthroughsubdirectories.+*/+structcache_ref_iterator{+structref_iteratorbase;++/*+*Thenumberoflevelscurrentlyonthestack.Thisisalways+*atleast1,becausewhenitbecomeszerotheiterationis+*endedandthisstructisfreed.+*/+size_tlevels_nr;++/* The number of levels that have been allocated on the stack */+size_tlevels_alloc;++/*+*Astackoflevels.levels[0]istheuppermostlevelthatis+*beingiteratedoverinthisiteration.(Thisisnot+*necessarythetoplevelinthereferenceshierarchy.Ifwe+*areiteratingthroughasubtree,thenlevels[0]willhold+*theref_dirforthatsubtree,andsubsequentlevelswillgo+*onfromthere.)+*/+structcache_ref_iterator_level*levels;+};++staticintcache_ref_iterator_advance(structref_iterator*ref_iterator)+{+structcache_ref_iterator*iter=+(structcache_ref_iterator*)ref_iterator;++while(1){+structcache_ref_iterator_level*level=+&iter->levels[iter->levels_nr-1];+structref_dir*dir=level->dir;+structref_entry*entry;++if(level->index==-1)+sort_ref_dir(dir);
do you need to sort here ...
+
+ if (++level->index == level->dir->nr) {
+ /* This level is exhausted; pop up a level */
+ if (--iter->levels_nr == 0)
+ return ref_iterator_abort(ref_iterator);
+
+ continue;
+ }
+
+ entry = dir->entries[level->index];
+
+ if (entry->flag & REF_DIR) {
+ /* push down a level */
+ ALLOC_GROW(iter->levels, iter->levels_nr + 1,
+ iter->levels_alloc);
+
+ level = &iter->levels[iter->levels_nr++];
+ level->dir = get_ref_dir(entry);
+ sort_ref_dir(level->dir);
@@ -704,6 +705,154 @@ static void prime_ref_dir(struct ref_dir *dir)}}+/*+*Alevelinthereferencehierarchythatiscurrentlybeingiterated+*through.+*/+structcache_ref_iterator_level{+/*+*Theref_dirbeingiteratedoveratthislevel.Theref_dir+*issortedbeforebeingstoredhere.+*/+structref_dir*dir;++/*+*Theindexofthecurrententrywithindir(whichmight+*itselfbeadirectory).Ifindex==-1,thentheiteration+*hasn'tyetbegun.Ifindex==dir->nr,thentheiteration+*throughthislevelisover.+*/+intindex;+};++/*+*Representaniterationthrougharef_dirinthememorycache.The+*iterationrecursesthroughsubdirectories.+*/+structcache_ref_iterator{+structref_iteratorbase;++/*+*Thenumberoflevelscurrentlyonthestack.Thisisalways+*atleast1,becausewhenitbecomeszerotheiterationis+*endedandthisstructisfreed.+*/+size_tlevels_nr;++/* The number of levels that have been allocated on the stack */+size_tlevels_alloc;++/*+*Astackoflevels.levels[0]istheuppermostlevelthatis+*beingiteratedoverinthisiteration.(Thisisnot+*necessarythetoplevelinthereferenceshierarchy.Ifwe+*areiteratingthroughasubtree,thenlevels[0]willhold+*theref_dirforthatsubtree,andsubsequentlevelswillgo+*onfromthere.)+*/+structcache_ref_iterator_level*levels;+};++staticintcache_ref_iterator_advance(structref_iterator*ref_iterator)+{+structcache_ref_iterator*iter=+(structcache_ref_iterator*)ref_iterator;++while(1){+structcache_ref_iterator_level*level=+&iter->levels[iter->levels_nr-1];+structref_dir*dir=level->dir;+structref_entry*entry;++if(level->index==-1)+sort_ref_dir(dir);
do you need to sort here ...
quoted
+
+ if (++level->index == level->dir->nr) {
+ /* This level is exhausted; pop up a level */
+ if (--iter->levels_nr == 0)
+ return ref_iterator_abort(ref_iterator);
+
+ continue;
+ }
+
+ entry = dir->entries[level->index];
+
+ if (entry->flag & REF_DIR) {
+ /* push down a level */
+ ALLOC_GROW(iter->levels, iter->levels_nr + 1,
+ iter->levels_alloc);
+
+ level = &iter->levels[iter->levels_nr++];
+ level->dir = get_ref_dir(entry);
+ sort_ref_dir(level->dir);
... given that you sort here?
I had intended to say 'or vice versa' here. When I wrote this, I had not
finished reading this patch (let alone the series). Now, I suspect that
you can simply drop this 'sort_ref_dir()' call site. Unless I've misread
the code, of course! ;-)
ATB,
Ramsay Jones
I had intended to say 'or vice versa' here. When I wrote this, I had not
finished reading this patch (let alone the series). Now, I suspect that
you can simply drop this 'sort_ref_dir()' call site. Unless I've misread
the code, of course! ;-)
Yes, you are right. Thanks for catching this! I'll fix it in v2.
Michael
From: Eric Sunshine <hidden> Date: 2016-06-16 02:19:39
On Mon, May 30, 2016 at 3:55 AM, Michael Haggerty [off-list ref] wrote:
quoted hunk
[...]
This commit introduces a new iteration primitive for references: a
ref_iterator. A ref_iterator is a polymorphic object that a reference
storage backend can be asked to instantiate. There are three functions
that can be applied to a ref_iterator:
* ref_iterator_advance(): move to the next reference in the iteration
* ref_iterator_abort(): end the iteration before it is exhausted
* ref_iterator_peel(): peel the reference currently being looked at
[...]
Signed-off-by: Michael Haggerty <redacted>
---
@@ -249,6 +249,199 @@ int rename_ref_available(const char *oldname, const char *newname);+/*+ * Advance the iterator to the first or next item and return ITER_OK.+ * If the iteration is exhausted, free the resources associated with+ * the ref_iterator and return ITER_DONE. On errors, free the iterator+ * resources and return ITER_ERROR. It is a bug to use ref_iterator or+ * call this function again after it has returned false.+ */
Either:
s/false/something other than ITER_OK/
or:
s/false/ITER_DONE or ITER_ERROR/
+int ref_iterator_advance(struct ref_iterator *ref_iterator);
+
+/*
+ * An iterator over nothing (its first ref_iterator_advance() call
+ * returns 0).
+ */
s/0/ITER_DONE/
+struct ref_iterator *empty_ref_iterator_begin(void);
+
+/*
+ * Return true iff ref_iterator is an empty_ref_iterator.
+ */
+int is_empty_ref_iterator(struct ref_iterator *ref_iterator);
I can see that you used this function as an optimization or
convenience in overlay_ref_iterator_begin(), but do you expect it to
be generally useful otherwise? Is it worth publishing? Do you have
other use-cases in mind?
Also, can you explain why the merge iterator doesn't also perform the
optimization/convenience of checking if one iterator is an empty
iterator?
+/*
+ * Iterate over the intries from iter0 and iter1, with the values
s/intries/entries/
+ * interleaved as directed by the select function. The iterator takes
+ * ownership of iter0 and iter1 and frees them when the iteration is
+ * over.
+ */
+struct ref_iterator *merge_ref_iterator_begin(
+ struct ref_iterator *iter0, struct ref_iterator *iter1,
+ ref_iterator_select_fn *select, void *cb_data);
+
+/*
+ * An iterator consisting of the union of the entries from iter0 and
+ * iter1. If there are entries common to the two sub-iterators, use
+ * the one from iter1. Each iterator must iterate over its entries in
+ * strcmp() order by refname for this to work.
+ *
+ * The new iterator takes ownership of its arguments and frees them
+ * when the iteration is over. As a convenience to callers, if iter0
+ * or iter1 is_empty_ref_iterator(), then abort that one immediately
+ * and return the other iterator directly, without wrapping it.
+ */
+struct ref_iterator *overlay_ref_iterator_begin(struct ref_iterator *iter0,
+ struct ref_iterator *iter1);
When reading about the overlay iterator (both code and documentation),
my expectation was that iter0 would shadow iter1, not the other way
around as implemented here. Of course, that's entirely subjective, but
the generic names don't provide any useful clues as to which shadows
which. Perhaps giving them more meaningful names would help.
+/*
+ * Wrap iter0, only letting through the references whose names start
+ * with prefix. If trim is set, set iter->refname to the name of the
+ * reference with that many characters trimmed off the front;
+ * otherwise set it to the full refname. The new iterator takes over
+ * ownership of iter0 and frees it when iteration is over. It makes
+ * its own copy of prefix.
+ *
+ * As an convenience to callers, if prefix is the empty string and
+ * trim is zero, this function returns iter0 directly, without
+ * wrapping it.
+ */
+struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
+ const char *prefix,
+ int trim);
Minor: Similarly, when reading the code and documentation, I wondered
why this was named 'iter0' when no 'iter1' was in sight. Perhaps name
it simply 'iter'.
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:40
On 05/31/2016 07:29 AM, Eric Sunshine wrote:
On Mon, May 30, 2016 at 3:55 AM, Michael Haggerty [off-list ref] wrote:
quoted
[...]
[...]
Either:
s/false/something other than ITER_OK/
or:
s/false/ITER_DONE or ITER_ERROR/
Thanks.
quoted
+int ref_iterator_advance(struct ref_iterator *ref_iterator);
+
+/*
+ * An iterator over nothing (its first ref_iterator_advance() call
+ * returns 0).
+ */
s/0/ITER_DONE/
Thanks. I guess you can guess what an earlier draft of this interface
looked like :-)
quoted
+struct ref_iterator *empty_ref_iterator_begin(void);
+
+/*
+ * Return true iff ref_iterator is an empty_ref_iterator.
+ */
+int is_empty_ref_iterator(struct ref_iterator *ref_iterator);
I can see that you used this function as an optimization or
convenience in overlay_ref_iterator_begin(), but do you expect it to
be generally useful otherwise? Is it worth publishing? Do you have
other use-cases in mind?
It is only "published" within the refs module, in refs/refs-internal.h.
This header file is not meant to be used by code outside of the refs module.
My thinking was that it might be useful to other reference backends. The
function is pretty safe for anybody to call, though I admit that it is
not very general.
I don't have a strong feeling either way. If nobody else chimes in, I'll
remove it from the header file as you suggested. We can always add it
back if somebody needs it.
Also, can you explain why the merge iterator doesn't also perform the
optimization/convenience of checking if one iterator is an empty
iterator?
That's because the merge iterator doesn't know what its select function
will do. For example, you could imagine an "intersect" select function
that only lets through references that were in *both* sub-iterators. In
that case, your suggested "optimization" would be incorrect.
Incidentally, that's also why I decided to leave the select function in
charge even after one or both of the sub-iterators is exhausted—because
it lets merge_ref_iterator implement more diverse behavior.
quoted
+/*
+ * Iterate over the intries from iter0 and iter1, with the values
s/intries/entries/
Thanks.
quoted
+ * interleaved as directed by the select function. The iterator takes
+ * ownership of iter0 and iter1 and frees them when the iteration is
+ * over.
+ */
+struct ref_iterator *merge_ref_iterator_begin(
+ struct ref_iterator *iter0, struct ref_iterator *iter1,
+ ref_iterator_select_fn *select, void *cb_data);
+
+/*
+ * An iterator consisting of the union of the entries from iter0 and
+ * iter1. If there are entries common to the two sub-iterators, use
+ * the one from iter1. Each iterator must iterate over its entries in
+ * strcmp() order by refname for this to work.
+ *
+ * The new iterator takes ownership of its arguments and frees them
+ * when the iteration is over. As a convenience to callers, if iter0
+ * or iter1 is_empty_ref_iterator(), then abort that one immediately
+ * and return the other iterator directly, without wrapping it.
+ */
+struct ref_iterator *overlay_ref_iterator_begin(struct ref_iterator *iter0,
+ struct ref_iterator *iter1);
When reading about the overlay iterator (both code and documentation),
my expectation was that iter0 would shadow iter1, not the other way
around as implemented here. Of course, that's entirely subjective, but
the generic names don't provide any useful clues as to which shadows
which. Perhaps giving them more meaningful names would help.
That's a good idea. I also found myself having to refer back to the
documentation to remind myself which was which.
How about I rename them "back" and "front"? I will also reverse the
order of the arguments.
(But I will leave the names "iter0" and "iter1" in merge_ref_iterator,
and also the constants like ITER_SELECT_0, because these don't
necessarily have the interpretation of "back" and "front".)
quoted
+/*
+ * Wrap iter0, only letting through the references whose names start
+ * with prefix. If trim is set, set iter->refname to the name of the
+ * reference with that many characters trimmed off the front;
+ * otherwise set it to the full refname. The new iterator takes over
+ * ownership of iter0 and frees it when iteration is over. It makes
+ * its own copy of prefix.
+ *
+ * As an convenience to callers, if prefix is the empty string and
+ * trim is zero, this function returns iter0 directly, without
+ * wrapping it.
+ */
+struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
+ const char *prefix,
+ int trim);
Minor: Similarly, when reading the code and documentation, I wondered
why this was named 'iter0' when no 'iter1' was in sight. Perhaps name
it simply 'iter'.
I found that it got a little bit confusing, because the constructor and
method implementations all use `iter` as a local variable. In particular
in the constructor there would want to be an argument "iter" and also
the local variable "iter" for the iterator being constructed, so a new
name would otherwise have to be invented for one or the other. Between
all the "iter" and "iter" and "iter->iter", I found that naming the
sub-iterator "iter0" made things a little bit less bewildering.
If you don't like that, we could name the embedded iterators something
like "subiter", "subiter0", and "subiter1". But the current convention
is a bit more succinct so I slightly prefer it.
Thanks for all your comments!
Michael
From: Eric Sunshine <hidden> Date: 2016-06-16 02:19:40
On Tue, May 31, 2016 at 3:59 AM, Michael Haggerty [off-list ref] wrote:
On 05/31/2016 07:29 AM, Eric Sunshine wrote:
quoted
On Mon, May 30, 2016 at 3:55 AM, Michael Haggerty [off-list ref] wrote:
quoted
+struct ref_iterator *empty_ref_iterator_begin(void);
+
+/*
+ * Return true iff ref_iterator is an empty_ref_iterator.
+ */
+int is_empty_ref_iterator(struct ref_iterator *ref_iterator);
I can see that you used this function as an optimization or
convenience in overlay_ref_iterator_begin(), but do you expect it to
be generally useful otherwise? Is it worth publishing? Do you have
other use-cases in mind?
It is only "published" within the refs module, in refs/refs-internal.h.
This header file is not meant to be used by code outside of the refs module.
Ah, I forgot about that. In that case, it's probably less of an issue.
My thinking was that it might be useful to other reference backends. The
function is pretty safe for anybody to call, though I admit that it is
not very general.
I don't have a strong feeling either way. If nobody else chimes in, I'll
remove it from the header file as you suggested. We can always add it
back if somebody needs it.
I don't feel strongly about it either.
quoted
Also, can you explain why the merge iterator doesn't also perform the
optimization/convenience of checking if one iterator is an empty
iterator?
That's because the merge iterator doesn't know what its select function
will do. For example, you could imagine an "intersect" select function
that only lets through references that were in *both* sub-iterators. In
that case, your suggested "optimization" would be incorrect.
Makes sense. Thanks for explaining. I wonder if this deserves a
comment somewhere in code or commit message to make the situation
clear to a future developer who might think it a good idea to promote
the "optimization" to the merge iterator.
quoted
quoted
+/*
+ * An iterator consisting of the union of the entries from iter0 and
+ * iter1. If there are entries common to the two sub-iterators, use
+ * the one from iter1. Each iterator must iterate over its entries in
+ * strcmp() order by refname for this to work.
+ *
+ * The new iterator takes ownership of its arguments and frees them
+ * when the iteration is over. As a convenience to callers, if iter0
+ * or iter1 is_empty_ref_iterator(), then abort that one immediately
+ * and return the other iterator directly, without wrapping it.
+ */
+struct ref_iterator *overlay_ref_iterator_begin(struct ref_iterator *iter0,
+ struct ref_iterator *iter1);
When reading about the overlay iterator (both code and documentation),
my expectation was that iter0 would shadow iter1, not the other way
around as implemented here. Of course, that's entirely subjective, but
the generic names don't provide any useful clues as to which shadows
which. Perhaps giving them more meaningful names would help.
That's a good idea. I also found myself having to refer back to the
documentation to remind myself which was which.
How about I rename them "back" and "front"? I will also reverse the
order of the arguments.
I had a hard time coming up with better names, which is why I didn't
suggest any in my review. The best I had was "shadower" and
"shadowee", but they are far too similar (and long) for my tastes.
"back" and "front" feel a bit off, but are better than anything I
thought of.
As for the argument order, I can't explain why my expectation was that
it would be the other way around, so I certainly don't insist that
they be swapped.
(But I will leave the names "iter0" and "iter1" in merge_ref_iterator,
and also the constants like ITER_SELECT_0, because these don't
necessarily have the interpretation of "back" and "front".)
Yes, those names are fine in the merge iterator.
quoted
quoted
+/*
+ * Wrap iter0, only letting through the references whose names start
+ * with prefix. If trim is set, set iter->refname to the name of the
+ * reference with that many characters trimmed off the front;
+ * otherwise set it to the full refname. The new iterator takes over
+ * ownership of iter0 and frees it when iteration is over. It makes
+ * its own copy of prefix.
+ *
+ * As an convenience to callers, if prefix is the empty string and
+ * trim is zero, this function returns iter0 directly, without
+ * wrapping it.
+ */
+struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
+ const char *prefix,
+ int trim);
Minor: Similarly, when reading the code and documentation, I wondered
why this was named 'iter0' when no 'iter1' was in sight. Perhaps name
it simply 'iter'.
I found that it got a little bit confusing, because the constructor and
method implementations all use `iter` as a local variable. In particular
in the constructor there would want to be an argument "iter" and also
the local variable "iter" for the iterator being constructed, so a new
name would otherwise have to be invented for one or the other. Between
all the "iter" and "iter" and "iter->iter", I found that naming the
sub-iterator "iter0" made things a little bit less bewildering.
If you don't like that, we could name the embedded iterators something
like "subiter", "subiter0", and "subiter1". But the current convention
is a bit more succinct so I slightly prefer it.
I'd probably have called the sub-iterator "child" (which is the same
length as "iter0") or "wrapped". If you're not interested changing the
name in the code, perhaps in the header alone you could call it simply
"iter" or omit the name altogether, but this a very minor issue and
probably not worth much time or effort to address.
On Mon, May 30, 2016 at 2:55 PM, Michael Haggerty [off-list ref] wrote:
Currently, the API for iterating over references is via a family of
for_each_ref()-type functions that invoke a callback function for each
selected reference. All of these eventually call do_for_each_ref(),
which knows how to do one thing: iterate in parallel through two
ref_caches, one for loose and one for packed refs, giving loose
references precedence over packed refs. This is rather complicated code,
and is quite specialized to the files backend. It also requires callers
to encapsulate their work into a callback function, which often means
that they have to define and use a "cb_data" struct to manage their
context.
The current design is already bursting at the seams, and will become
even more awkward in the upcoming world of multiple reference storage
backends:
* Per-worktree vs. shared references are currently handled via a kludge
in git_path() rather than iterating over each part of the reference
namespace separately and merging the results. This kludge will cease
to work when we have multiple reference storage backends.
Question from a refs user. Right now worktree.c:get_worktrees() peeks
directly to "$GIT_DIR/worktrees/xxx/HEAD" and parses the content
itself, something that I promised to fix but never got around to do
it. Will we have an iterator to go through all worktrees' HEAD, or
will there be an API to say "resolve ref HEAD from worktree XYZ"?
--
Duy
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:42
On 06/02/2016 12:08 PM, Duy Nguyen wrote:
On Mon, May 30, 2016 at 2:55 PM, Michael Haggerty [off-list ref] wrote:
quoted
Currently, the API for iterating over references is via a family of
for_each_ref()-type functions that invoke a callback function for each
selected reference. All of these eventually call do_for_each_ref(),
which knows how to do one thing: iterate in parallel through two
ref_caches, one for loose and one for packed refs, giving loose
references precedence over packed refs. This is rather complicated code,
and is quite specialized to the files backend. It also requires callers
to encapsulate their work into a callback function, which often means
that they have to define and use a "cb_data" struct to manage their
context.
The current design is already bursting at the seams, and will become
even more awkward in the upcoming world of multiple reference storage
backends:
* Per-worktree vs. shared references are currently handled via a kludge
in git_path() rather than iterating over each part of the reference
namespace separately and merging the results. This kludge will cease
to work when we have multiple reference storage backends.
Question from a refs user. Right now worktree.c:get_worktrees() peeks
directly to "$GIT_DIR/worktrees/xxx/HEAD" and parses the content
itself, something that I promised to fix but never got around to do
it. Will we have an iterator to go through all worktrees' HEAD, or
will there be an API to say "resolve ref HEAD from worktree XYZ"?
My preference is that there is a way to say "create a ref_store object
representing the loose references stored physically under
"$GIT_DIR/worktrees/xxx". Then that ref_store could be asked to read its
`HEAD` (or iterate over all of the refs under that path or whatever).
You could even write `HEAD` through the same ref_store.
Michael
From: Michael Haggerty <hidden> Date: 2016-06-16 02:19:43
On 06/01/2016 01:12 AM, Eric Sunshine wrote:
On Tue, May 31, 2016 at 3:59 AM, Michael Haggerty [off-list ref] wrote:
quoted
On 05/31/2016 07:29 AM, Eric Sunshine wrote:
quoted
On Mon, May 30, 2016 at 3:55 AM, Michael Haggerty [off-list ref] wrote:
quoted
+struct ref_iterator *empty_ref_iterator_begin(void);
+
+/*
+ * Return true iff ref_iterator is an empty_ref_iterator.
+ */
+int is_empty_ref_iterator(struct ref_iterator *ref_iterator);
I can see that you used this function as an optimization or
convenience in overlay_ref_iterator_begin(), but do you expect it to
be generally useful otherwise? Is it worth publishing? Do you have
other use-cases in mind?
It is only "published" within the refs module, in refs/refs-internal.h.
This header file is not meant to be used by code outside of the refs module.
Ah, I forgot about that. In that case, it's probably less of an issue.
quoted
My thinking was that it might be useful to other reference backends. The
function is pretty safe for anybody to call, though I admit that it is
not very general.
I don't have a strong feeling either way. If nobody else chimes in, I'll
remove it from the header file as you suggested. We can always add it
back if somebody needs it.
I don't feel strongly about it either.
OK then, I'll leave it as-is.
quoted
quoted
Also, can you explain why the merge iterator doesn't also perform the
optimization/convenience of checking if one iterator is an empty
iterator?
That's because the merge iterator doesn't know what its select function
will do. For example, you could imagine an "intersect" select function
that only lets through references that were in *both* sub-iterators. In
that case, your suggested "optimization" would be incorrect.
Makes sense. Thanks for explaining. I wonder if this deserves a
comment somewhere in code or commit message to make the situation
clear to a future developer who might think it a good idea to promote
the "optimization" to the merge iterator.