Use rust types in xdiff.
PATCH v5 9/13 xdiff: delete chastore from xdfile_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
xdfile_t currently uses chastore_t which is an arena allocator. I think that xrecord_t used to be a linked list and recs didn't exist originally. When recs was added I think they forgot to remove xdfile_t.next, but was overlooked. This dual data structure setup makes the code somewhat confusing.
Additionally the C type chastore_t isn't FFI friendly, and provides little to no performance benefit over using realloc to grow an array.
Performance impact of deleting fields from xdfile_t:
Deleting ha is about 5% slower.
Deleting cha is about 5% faster.
Delete ha, but keep cha
time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_ha/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.269 s ± 0.017 s [User: 1.135 s, System: 0.128 s]
Range (min … max): 1.249 s … 1.286 s 10 runs Benchmark 2: build_delete_ha/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.339 s ± 0.017 s [User: 1.234 s, System: 0.099 s]
Range (min … max): 1.320 s … 1.358 s 10 runs
Summary
build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran
1.06 ± 0.02 times faster than build_delete_ha/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/nullDelete cha, but keep ha
time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_chastore/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.290 s ± 0.001 s [User: 1.154 s, System: 0.130 s]
Range (min … max): 1.288 s … 1.292 s 10 runs Benchmark 2: build_delete_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.232 s ± 0.017 s [User: 1.105 s, System: 0.121 s]
Range (min … max): 1.205 s … 1.249 s 10 runs
Summary
build_delete_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran
1.05 ± 0.01 times faster than build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/nullDelete ha AND chastore
time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_ha_and_chastore/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.291 s ± 0.002 s [User: 1.156 s, System: 0.129 s]
Range (min … max): 1.287 s … 1.295 s 10 runs Benchmark 2: build_delete_ha_and_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.306 s ± 0.001 s [User: 1.195 s, System: 0.105 s]
Range (min … max): 1.305 s … 1.308 s 10 runs
Summary
build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran
1.01 ± 0.00 times faster than build_delete_ha_and_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/nullBest-viewed-with: --color-words
--- xdiff/xdiffi.c | 24 ++++++++++---------- xdiff/xemit.c | 6 ++--- xdiff/xhistogram.c | 2 +- xdiff/xmerge.c | 56 +++++++++++++++++++++++----------------------- xdiff/xpatience.c | 10 ++++----- xdiff/xprepare.c | 19 ++++++---------- xdiff/xtypes.h | 3 +-- xdiff/xutils.c | 12 +++++----- 8 files changed, 63 insertions(+), 69 deletions(-)
xdiff/xdiffi.c +12 -12
@@ -24,7 +24,7 @@static unsigned long get_hash (xdfile_t *xdf,long index) { -return xdf->recs[xdf->rindex[index]]->ha; +return xdf->recs[xdf->rindex[index]].ha; }#define XDL_MAX_COST_MIN 256
@@ -489,13 +489,13 @@ static void measure_split(const xdfile_t *xdf, long split, m->indent =-1 ; }else { m->end_of_file =0 ; - m->indent =get_indent (xdf->recs[split]); + m->indent =get_indent (&xdf->recs[split]); } m->pre_blank =0 ; m->pre_indent =-1 ;for (i = split -1 ; i >=0 ; i--) { - m->pre_indent =get_indent (xdf->recs[i]); + m->pre_indent =get_indent (&xdf->recs[i]);if (m->pre_indent !=-1 )break ; m->pre_blank +=1 ;
@@ -508,7 +508,7 @@ static void measure_split(const xdfile_t *xdf, long split, m->post_blank =0 ; m->post_indent =-1 ;for (i = split +1 ; i < xdf->nrec; i++) { - m->post_indent =get_indent (xdf->recs[i]); + m->post_indent =get_indent (&xdf->recs[i]);if (m->post_indent !=-1 )break ; m->post_blank +=1 ;
@@ -752,7 +752,7 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)static int group_slide_down (xdfile_t *xdf,struct xdlgroup *g) {if (g->end < xdf->nrec && -recs_match (xdf->recs[g->start], xdf->recs[g->end])) { +recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { xdf->rchg[g->start++] =0 ; xdf->rchg[g->end++] =1 ;
@@ -773,7 +773,7 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g)static int group_slide_up (xdfile_t *xdf,struct xdlgroup *g) {if (g->start >0 && -recs_match (xdf->recs[g->start -1 ], xdf->recs[g->end -1 ])) { +recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { xdf->rchg[--g->start] =1 ; xdf->rchg[--g->end] =0 ;
@@ -988,16 +988,16 @@ static void xdl_mark_ignorable_lines(xdchange_t *xscr, xdfenv_t *xe, long flags)for (xch = xscr; xch; xch = xch->next) {int ignore =1 ; -xrecord_t **rec; +xrecord_t *rec;long i; rec = &xe->xdf1.recs[xch->i1];for (i =0 ; i < xch->chg1 && ignore; i++) - ignore =xdl_blankline (rec[i]->ptr, rec[i]->size, flags); + ignore =xdl_blankline (rec[i].ptr, rec[i].size, flags); rec = &xe->xdf2.recs[xch->i2];for (i =0 ; i < xch->chg2 && ignore; i++) - ignore =xdl_blankline (rec[i]->ptr, rec[i]->size, flags); + ignore =xdl_blankline (rec[i].ptr, rec[i].size, flags); xch->ignore = ignore; }
@@ -1021,7 +1021,7 @@ static void xdl_mark_ignorable_regex(xdchange_t *xscr, const xdfenv_t *xe,xdchange_t *xch;for (xch = xscr; xch; xch = xch->next) { -xrecord_t **rec; +xrecord_t *rec;int ignore =1 ;long i;
@@ -1033,11 +1033,11 @@ static void xdl_mark_ignorable_regex(xdchange_t *xscr, const xdfenv_t *xe, rec = &xe->xdf1.recs[xch->i1];for (i =0 ; i < xch->chg1 && ignore; i++) - ignore =record_matches_regex (rec[i], xpp); + ignore =record_matches_regex (&rec[i], xpp); rec = &xe->xdf2.recs[xch->i2];for (i =0 ; i < xch->chg2 && ignore; i++) - ignore =record_matches_regex (rec[i], xpp); + ignore =record_matches_regex (&rec[i], xpp); xch->ignore = ignore; }
xdiff/xemit.c +3 -3
@@ -25,7 +25,7 @@static int xdl_emit_record (xdfile_t *xdf,long ri,char const *pre,xdemitcb_t *ecb) { -xrecord_t *rec = xdf->recs[ri]; +xrecord_t *rec = &xdf->recs[ri];if (xdl_emit_diffrec (rec->ptr, rec->size, pre,strlen (pre), ecb) <0 )return -1 ;
@@ -110,7 +110,7 @@ static long def_ff(const char *rec, long len, char *buf, long sz)static long match_func_rec (xdfile_t *xdf,xdemitconf_t const *xecfg,long ri,char *buf,long sz) { -xrecord_t *rec = xdf->recs[ri]; +xrecord_t *rec = &xdf->recs[ri];if (!xecfg->find_func)return def_ff (rec->ptr, rec->size, buf, sz);
@@ -150,7 +150,7 @@ static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg,static int is_empty_rec (xdfile_t *xdf,long ri) { -xrecord_t *rec = xdf->recs[ri]; +xrecord_t *rec = &xdf->recs[ri];long i =0 ;for (; i < rec->size &&XDL_ISSPACE (rec->ptr[i]); i++);
xdiff/xhistogram.c +1 -1
@@ -86,7 +86,7 @@ struct region { ((LINE_MAP(index, ptr))->cnt)#define REC (env, s, l) \ - (env->xdf##s.recs[l - 1]) + (&env->xdf##s.recs[l - 1])static int cmp_recs (xrecord_t *r1,xrecord_t *r2) {
xdiff/xmerge.c +28 -28
123 lines not on this page · raw message
xdiff/xpatience.c +5 -5
@@ -88,9 +88,9 @@ static int is_anchor(xpparam_t const *xpp, const char *line)static void insert_record (xpparam_t const *xpp,int line,struct hashmap *map,int pass) { -xrecord_t **records = pass ==1 ? +xrecord_t *records = pass ==1 ? map->env->xdf1.recs : map->env->xdf2.recs; -xrecord_t *record = records[line -1 ]; +xrecord_t *record = &records[line -1 ];/* * After xdl_prepare_env() (or more precisely, due to * xdl_classify_record()), the "ha" member of the records (AKA lines)
@@ -121,7 +121,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,return ; map->entries[index].line1 = line; map->entries[index].hash = record->ha; - map->entries[index].anchor =is_anchor (xpp, map->env->xdf1.recs[line -1 ]->ptr); + map->entries[index].anchor =is_anchor (xpp, map->env->xdf1.recs[line -1 ].ptr);if (!map->first) map->first = map->entries + index;if (map->last) {
@@ -246,8 +246,8 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)static int match (struct hashmap *map,int line1,int line2) { -xrecord_t *record1 = map->env->xdf1.recs[line1 -1 ]; -xrecord_t *record2 = map->env->xdf2.recs[line2 -1 ]; +xrecord_t *record1 = &map->env->xdf1.recs[line1 -1 ]; +xrecord_t *record2 = &map->env->xdf2.recs[line2 -1 ];return record1->ha == record2->ha; }
xdiff/xprepare.c +7 -12
@@ -128,7 +128,6 @@ static void xdl_free_ctx(xdfile_t *xdf)xdl_free (xdf->rindex);xdl_free (xdf->rchg -1 );xdl_free (xdf->recs); -xdl_cha_free (&xdf->rcha); }
@@ -143,8 +142,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ xdf->rchg =NULL ; xdf->recs =NULL ; -if (xdl_cha_init (&xdf->rcha,sizeof (xrecord_t), narec /4 +1 ) <0 ) - goto abort;if (!XDL_ALLOC_ARRAY (xdf->recs, narec)) goto abort;
@@ -155,12 +152,10 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ hav =xdl_hash_record (&cur, top, xpp->flags);if (XDL_ALLOC_GROW (xdf->recs, xdf->nrec +1 , narec)) goto abort; -if (!(crec =xdl_cha_alloc (&xdf->rcha))) - goto abort; + crec = &xdf->recs[xdf->nrec++]; crec->ptr = prev; crec->size = (long ) (cur - prev); crec->ha = hav; - xdf->recs[xdf->nrec++] = crec;if (xdl_classify_record (pass, cf, crec) <0 ) goto abort; }
@@ -260,7 +255,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {*/ static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2) {long i, nm, nreff, mlim; -xrecord_t **recs; +xrecord_t *recs;xdlclass_t *rcrec;char *dis, *dis1, *dis2;int need_min = !!(cf->flags &XDF_NEED_MINIMAL );
@@ -273,7 +268,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif ((mlim =xdl_bogosqrt (xdf1->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { - rcrec = cf->rcrecs[(*recs)->ha]; + rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len2 :0 ; dis1[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; }
@@ -281,7 +276,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif ((mlim =xdl_bogosqrt (xdf2->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { - rcrec = cf->rcrecs[(*recs)->ha]; + rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len1 :0 ; dis2[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; }
@@ -317,13 +312,13 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd*/ static int xdl_trim_ends (xdfile_t *xdf1,xdfile_t *xdf2) {long i, lim; -xrecord_t **recs1, **recs2; +xrecord_t *recs1, *recs2; recs1 = xdf1->recs; recs2 = xdf2->recs;for (i =0 , lim =XDL_MIN (xdf1->nrec, xdf2->nrec); i < lim; i++, recs1++, recs2++) -if ((*recs1)->ha != (*recs2)->ha) +if (recs1->ha != recs2->ha)break ; xdf1->dstart = xdf2->dstart = i;
@@ -331,7 +326,7 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) { recs1 = xdf1->recs + xdf1->nrec -1 ; recs2 = xdf2->recs + xdf2->nrec -1 ;for (lim -= i, i =0 ; i < lim; i++, recs1--, recs2--) -if ((*recs1)->ha != (*recs2)->ha) +if (recs1->ha != recs2->ha)break ; xdf1->dend = xdf1->nrec - i -1 ;
xdiff/xtypes.h +1 -2
@@ -45,10 +45,9 @@ typedef struct s_xrecord { } xrecord_t; typedef struct s_xdfile { - chastore_t rcha; + xrecord_t *recs; long nrec; long dstart, dend; - xrecord_t **recs; char *rchg; long *rindex; long nreff;
xdiff/xutils.c +6 -6
@@ -416,12 +416,12 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,mmfile_t subfile1, subfile2;xdfenv_t env; - subfile1.ptr = (char *)diff_env->xdf1.recs[line1 -1 ]->ptr; - subfile1.size = diff_env->xdf1.recs[line1 + count1 -2 ]->ptr + - diff_env->xdf1.recs[line1 + count1 -2 ]->size - subfile1.ptr; - subfile2.ptr = (char *)diff_env->xdf2.recs[line2 -1 ]->ptr; - subfile2.size = diff_env->xdf2.recs[line2 + count2 -2 ]->ptr + - diff_env->xdf2.recs[line2 + count2 -2 ]->size - subfile2.ptr; + subfile1.ptr = (char *)diff_env->xdf1.recs[line1 -1 ].ptr; + subfile1.size = diff_env->xdf1.recs[line1 + count1 -2 ].ptr + + diff_env->xdf1.recs[line1 + count1 -2 ].size - subfile1.ptr; + subfile2.ptr = (char *)diff_env->xdf2.recs[line2 -1 ].ptr; + subfile2.size = diff_env->xdf2.recs[line2 + count2 -2 ].ptr + + diff_env->xdf2.recs[line2 + count2 -2 ].size - subfile2.ptr;if (xdl_do_diff (&subfile1, &subfile2, xpp, &env) <0 )return -1 ;
Signature · 1 line
gitgitgadget
PATCH v5 10/13 xdiff: delete rchg aliasing
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
Best-viewed-with: --color-words
--- xdiff/xdiffi.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
xdiff/xdiffi.c +3 -4
@@ -932,16 +932,15 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {int xdl_build_script (xdfenv_t *xe,xdchange_t **xscr) {xdchange_t *cscr =NULL , *xch; -char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;long i1, i2, l1, l2;/* * Trivial. Collects "groups" of changes and creates an edit script. */ for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >=0 || i2 >=0 ; i1--, i2--) -if (rchg1[i1 -1 ] || rchg2[i2 -1 ]) { -for (l1 = i1; rchg1[i1 -1 ]; i1--); -for (l2 = i2; rchg2[i2 -1 ]; i2--); +if (xe->xdf1.rchg[i1 -1 ] || xe->xdf2.rchg[i2 -1 ]) { +for (l1 = i1; xe->xdf1.rchg[i1 -1 ]; i1--); +for (l2 = i2; xe->xdf2.rchg[i2 -1 ]; i2--);if (!(xch =xdl_add_change (cscr, i1, i2, l1 - i1, l2 - i2))) {xdl_free_script (cscr);
Signature · 1 line
gitgitgadget
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
The commit message should explain why this change is being made
Thanks
Phillip
Quoted 30 lines
Best-viewed-with: --color-words
Signed-off-by Ezekiel Newren <[email protected]>--- xdiff/xdiffi.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)xdiff/xdiffi.c +3
-4@@ -932,16 +932,15 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {int xdl_build_script (xdfenv_t *xe,xdchange_t **xscr) {xdchange_t *cscr =NULL , *xch; -char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;long i1, i2, l1, l2;/* * Trivial. Collects "groups" of changes and creates an edit script. */ for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >=0 || i2 >=0 ; i1--, i2--) -if (rchg1[i1 -1 ] || rchg2[i2 -1 ]) { -for (l1 = i1; rchg1[i1 -1 ]; i1--); -for (l2 = i2; rchg2[i2 -1 ]; i2--); +if (xe->xdf1.rchg[i1 -1 ] || xe->xdf2.rchg[i2 -1 ]) { +for (l1 = i1; xe->xdf1.rchg[i1 -1 ]; i1--); +for (l2 = i2; xe->xdf2.rchg[i2 -1 ]; i2--);if (!(xch =xdl_add_change (cscr, i1, i2, l1 - i1, l2 - i2))) {xdl_free_script (cscr);
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 5 lines · Phillip Wood
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
The commit message should explain why this change is being made
Reasons to delete local variable aliasing:
* Usage tracking: Tools are better able to follow the usage.
* Refactor churn: Later commits will refactor rchg.
* No additional meaning: The local variables express the same meaning as the struct field itself.
Would that suffice?
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 7 lines · Ezekiel Newren
Quoted 5 lines · Phillip Wood
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
The commit message should explain why this change is being made
Quoted 7 lines
Reasons to delete local variable aliasing:
* Usage tracking: Tools are better able to follow the usage.
* Refactor churn: Later commits will refactor rchg.
* No additional meaning: The local variables express the same meaning as the struct field itself.Would that suffice?
In general, I do not view the first one is a good excuse.
When using a separate local variable enhannces readability of the code (which often is true, with a pointer that points deep into a nested structure member) to humans, we shouldn't blindly bend the code to cater to less intelligent tools; it needs balancing.
The third one alone is not a good excuse for the same reason. It (and the first one) depends on how much benefit we are gaining from having a short-and-sweet local variables that may make the expressions and statements they are involved in easier to read.
For this particular change, I would think it is on borderline, and subjective. I would be OK with the third point if you rephrase it to additionally say that the conditional and the inner loop is easy enough to follow without using the local aliases to make the code shorter (which of course is the commit author's opinion, but they deserve to have and express their opinion as part of the rationale for a change).
Thanks.
- char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
long i1, i2, l1, l2;
/*
* Trivial. Collects "groups" of changes and creates an edit script. */
for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
- if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
- for (l1 = i1; rchg1[i1 - 1]; i1--);
- for (l2 = i2; rchg2[i2 - 1]; i2--);
+ if (xe->xdf1.rchg[i1 - 1] || xe->xdf2.rchg[i2 - 1]) {
+ for (l1 = i1; xe->xdf1.rchg[i1 - 1]; i1--);
+ for (l2 = i2; xe->xdf2.rchg[i2 - 1]; i2--);
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 30 lines · Junio C Hamano
Quoted 7 lines · Ezekiel Newren
Quoted 5 lines · Phillip Wood
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
The commit message should explain why this change is being made
Quoted 7 lines
Reasons to delete local variable aliasing:
* Usage tracking: Tools are better able to follow the usage.
* Refactor churn: Later commits will refactor rchg.
* No additional meaning: The local variables express the same meaning as the struct field itself.Would that suffice?
In general, I do not view the first one is a good excuse.
When using a separate local variable enhances readability of the code (which often is true, with a pointer that points deep into a nested structure member) to humans, we shouldn't blindly bend the code to cater to less intelligent tools; it needs balancing.
The third one alone is not a good excuse for the same reason. It (and the first one) depends on how much benefit we are gaining from having a short-and-sweet local variables that may make the expressions and statements they are involved in easier to read.
Quoted 7 lines
For this particular change, I would think it is borderline, and subjective. I would be OK with the third point if you rephrase it to additionally say that the conditional and the inner loop is easy enough to follow without using the local aliases to make the code shorter (which of course is the commit author's opinion, but they deserve to have and express their opinion as part of the rationale for a change).
Ok, I can see that.
I have a question for everyone: Does preparing C code to be translated into Rust count as a valid reason for changing it? Provided that there is no violation of the Git style (or very small in some cases).
If my intent was to keep this as C code forever I'd agree, but... My other reason is that it more closely follows Rust paradigms. Creating multiple pointers to the same memory in Rust subverts the borrow checker's ability to keep track of who owns the memory. Since C doesn't have a concept of borrowing, I decided to delete the aliasing here, and in many other places. I'm removing as much aliasing from the code as I can because it makes it easier to translate into idiomatic Rust later. Using ctags and modern IDE's to follow variable usage is convenient, but safe Rust refuses to compile in many cases where C aliasing is common. We could use unsafe Rust to make literal translations of C to Rust, but then we'd forfeit the reasons and benefits of why we want to add Rust to Git in the first place.
Translating C to Rust has been difficult because many styles in Git's C flat out won't compile in Rust. Many places need a little tweaking, others need major overhauls. In all of my C cleanups I am keeping idiomatic Rust in mind.
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 5 lines · Ezekiel Newren
I have a question for everyone: Does preparing C code to be translated into Rust count as a valid reason for changing it? Provided that there is no violation of the Git style (or very small in some cases).
If my intent was to keep this as C code forever I'd agree, but...
You'd agree that "I am preparing this for eventual rewrite" would be a valid reason? Or you are agreeing with something else?
Quoted 4 lines
My
other reason is that it more closely follows Rust paradigms. Creating multiple pointers to the same memory in Rust subverts the borrow checker's ability to keep track of who owns the memory.
Sure. But looking at the use of rchg[12] in xdl_build_script(), if they were "const char *", combined with the fact that they are local and their addresses are never taken (to be leaked to our callers), you wouldn't have much trouble with the current code, or would you still have issues?
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 11 lines · Junio C Hamano
Quoted 5 lines · Ezekiel Newren
I have a question for everyone: Does preparing C code to be translated into Rust count as a valid reason for changing it? Provided that there is no violation of the Git style (or very small in some cases).
If my intent was to keep this as C code forever I'd agree, but...
You'd agree that "I am preparing this for eventual rewrite" would be a valid reason? Or you are agreeing with something else?
I'd agree that my reasons for making this change are insufficient. I think usage tracking tools _is_ a weak argument, but perhaps not quite as weak as what you're thinking. For example, when I renamed the rchg field to changed, it was as simple as right-clicking the field, choosing Rename, typing 'changed', and letting the IDE update every use. Patch 11/13, "xdiff: rename rchg -> changed in xdfile_t", was generated directly from that one action. That patch was clean because I had already gone through and removed all the aliases of that field.
Quoted 10 lines
Quoted 4 lines
My
other reason is that it more closely follows Rust paradigms. Creating multiple pointers to the same memory in Rust subverts the borrow checker's ability to keep track of who owns the memory.Sure. But looking at the use of rchg[12] in
xdl_build_script(), if they were "const char *", combined with the fact that they are local and their addresses are never taken (to be leaked to our callers), you wouldn't have much trouble with the current code, or would you still have issues?
For xdl_build_script() specifically it would work just fine keeping the local variable aliasing in. I think this is another case of personal preference vs established style. Which path would you prefer that I take?
1. Drop this commit and remember to refactor rchg1, rchg2 to changed1, and changed2.
2. Keep this commit with reasons like this:
* Refactor churn: Later commits will refactor rchg.
* No additional meaning: The local variables express the same
meaning as the struct field itself. Also, the conditional and the inner loop is easy enough to follow without using the local aliases to make the code shorter.
My preference is number 2.
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 8 lines · Ezekiel Newren
I'd agree that my reasons for making this change are insufficient. I think usage tracking tools _is_ a weak argument, but perhaps not quite as weak as what you're thinking. For example, when I renamed the rchg field to changed, it was as simple as right-clicking the field, choosing Rename, typing 'changed', and letting the IDE update every use. Patch 11/13, "xdiff: rename rchg -> changed in
xdfile_t", was generated directly from that one action. That patch was clean because I had already gone through and removed all the aliases of that field.
If I am reading you correctly, you are describing IDE's syntax-aware editor's symbol renaming feature; I am not quite sure what it has to do with "usage tracking", which would be more of static analysis thing, no?
Surely, IDE makes these symbol renaming easy and that would be one reason that makes "because we will change this part of the code in later commit" less relevant, isn't it? Whether the struct member rchg is accessed directly in the conditional and loop, or is used as the source of an assignment to a local variable, it needs to be renamed either way. And with tools, it is not as bad.
Quoted 8 lines
Quoted 5 lines
Sure. But looking at the use of rchg[12] in
xdl_build_script(), if they were "const char *", combined with the fact that they are local and their addresses are never taken (to be leaked to our callers), you wouldn't have much trouble with the current code, or would you still have issues?For
xdl_build_script()specifically it would work just fine keeping the local variable aliasing in.
And transliterating that directly to Rust would not cause the borrow issue as you described? Then it would be great. One less thing to worry about when we need to look at C and then write an equivalent in Rust.
Quoted 6 lines
2. Keep this commit with reasons like this:
* Refactor churn: Later commits will refactor rchg.
* No additional meaning: The local variables express the same
meaning as the struct field itself. Also, the conditional and the inner loop is easy enough to follow without using the local aliases to make the code shorter.
If you have to go route #2, I can live with it, but "No additional meaning" is _not_ a valid reason to remove aliasing variables.
By definition, a local variable that aliases something like a deeply nested structure member should *not* introduce any additional meaning (in other words, if the code modifies that local variable making it out of sync with the underlying structure, the variable is not without "addtional meaning" and is no longer an alias).
The whole reason I asked you to justify removal of the local variable on the basis of lack of readability improvement ("the original is simple enough to read without shorter variables") was just that. "This variable is merely an alias to something else", aka "There is no meaning added by the presence of this variable", is *not* a valid reason to remove it by itself.
So, with the same code but with a better justification like "the original uses a few local variables to shorten the code, but open coding the access to underlying members of nested structure without these local variables is not all that hard to read, so let's do so", would probably be an acceptable explanation with no need for other excuses, I would think.
Thanks.
Re: [PATCH v5 10/13] xdiff: delete rchg aliasing
Quoted 6 lines · Junio C Hamano
So, with the same code but with a better justification like "the original uses a few local variables to shorten the code, but open coding the access to underlying members of nested structure without these local variables is not all that hard to read, so let's do so", would probably be an acceptable explanation with no need for other excuses, I would think.
I've changed my opinion. I'm going to drop this commit because I found myself using this design pattern in other functions, which would make me a hypocrite if this commit stays.
PATCH v5 11/13 xdiff: rename rchg -> changed in xdfile_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
Best-viewed-with: --color-words
--- xdiff/xdiffi.c | 28 ++++++++++++++-------------- xdiff/xhistogram.c | 8 ++++---- xdiff/xpatience.c | 8 ++++---- xdiff/xprepare.c | 12 ++++++------ xdiff/xtypes.h | 2 +- xdiff/xutils.c | 4 ++-- 6 files changed, 31 insertions(+), 31 deletions(-)
xdiff/xdiffi.c +14 -14
@@ -278,10 +278,10 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,*/ if (off1 == lim1) {for (; off2 < lim2; off2++) - xdf2->rchg[xdf2->rindex[off2]] =1 ; + xdf2->changed[xdf2->rindex[off2]] =1 ; }else if (off2 == lim2) {for (; off1 < lim1; off1++) - xdf1->rchg[xdf1->rindex[off1]] =1 ; + xdf1->changed[xdf1->rindex[off1]] =1 ; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;
@@ -708,7 +708,7 @@ struct xdlgroup {static void group_init (xdfile_t *xdf,struct xdlgroup *g) { g->start = g->end =0 ; -while (xdf->rchg[g->end]) +while (xdf->changed[g->end]) g->end++; }
@@ -722,7 +722,7 @@ static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)return -1 ; g->start = g->end +1 ; -for (g->end = g->start; xdf->rchg[g->end]; g->end++) +for (g->end = g->start; xdf->changed[g->end]; g->end++) ;return 0 ;
@@ -738,7 +738,7 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)return -1 ; g->end = g->start -1 ; -for (g->start = g->end; xdf->rchg[g->start -1 ]; g->start--) +for (g->start = g->end; xdf->changed[g->start -1 ]; g->start--) ;return 0 ;
@@ -753,10 +753,10 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) {if (g->end < xdf->nrec &&recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { - xdf->rchg[g->start++] =0 ; - xdf->rchg[g->end++] =1 ; + xdf->changed[g->start++] =0 ; + xdf->changed[g->end++] =1 ; -while (xdf->rchg[g->end]) +while (xdf->changed[g->end]) g->end++;return 0 ;
@@ -774,10 +774,10 @@ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) {if (g->start >0 &&recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { - xdf->rchg[--g->start] =1 ; - xdf->rchg[--g->end] =0 ; + xdf->changed[--g->start] =1 ; + xdf->changed[--g->end] =0 ; -while (xdf->rchg[g->start -1 ]) +while (xdf->changed[g->start -1 ]) g->start--;return 0 ;
@@ -938,9 +938,9 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {* Trivial. Collects "groups" of changes and creates an edit script. */ for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >=0 || i2 >=0 ; i1--, i2--) -if (xe->xdf1.rchg[i1 -1 ] || xe->xdf2.rchg[i2 -1 ]) { -for (l1 = i1; xe->xdf1.rchg[i1 -1 ]; i1--); -for (l2 = i2; xe->xdf2.rchg[i2 -1 ]; i2--); +if (xe->xdf1.changed[i1 -1 ] || xe->xdf2.changed[i2 -1 ]) { +for (l1 = i1; xe->xdf1.changed[i1 -1 ]; i1--); +for (l2 = i2; xe->xdf2.changed[i2 -1 ]; i2--);if (!(xch =xdl_add_change (cscr, i1, i2, l1 - i1, l2 - i2))) {xdl_free_script (cscr);
xdiff/xhistogram.c +4 -4
@@ -318,11 +318,11 @@ redo:if (!count1) {while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;return 0 ; }
@@ -335,9 +335,9 @@ redo:else {if (lcs.begin1 ==0 && lcs.begin2 ==0 ) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ; result =0 ; }else { result = histogram_diff(xpp, env,
xdiff/xpatience.c +4 -4
@@ -331,11 +331,11 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* trivial case: one side is empty */ if (!count1) {while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;return 0 ; }
@@ -347,9 +347,9 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* are there any matching lines at all? */ if (!map.has_matches) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;xdl_free (map.entries);return 0 ; }
xdiff/xprepare.c +6 -6
@@ -126,7 +126,7 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_tstatic void xdl_free_ctx (xdfile_t *xdf) {xdl_free (xdf->rindex); -xdl_free (xdf->rchg -1 ); +xdl_free (xdf->changed -1 );xdl_free (xdf->recs); }
@@ -139,7 +139,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_xrecord_t *crec; xdf->rindex =NULL ; - xdf->rchg =NULL ; + xdf->changed =NULL ; xdf->recs =NULL ;if (!XDL_ALLOC_ARRAY (xdf->recs, narec))
@@ -161,7 +161,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ } } -if (!XDL_CALLOC_ARRAY (xdf->rchg, xdf->nrec +2 )) +if (!XDL_CALLOC_ARRAY (xdf->changed, xdf->nrec +2 )) goto abort; if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
@@ -170,7 +170,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ goto abort; } - xdf->rchg +=1 ; + xdf->changed +=1 ; xdf->nreff =0 ; xdf->dstart =0 ; xdf->dend = xdf->nrec -1 ;
@@ -287,7 +287,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; } else - xdf1->rchg[i] = 1; + xdf1->changed[i] = 1; } xdf1->nreff = nreff;
@@ -297,7 +297,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; } else - xdf2->rchg[i] = 1; + xdf2->changed[i] = 1; } xdf2->nreff = nreff;
xdiff/xtypes.h +1 -1
@@ -48,7 +48,7 @@ typedef struct s_xdfile {xrecord_t *recs;long nrec;long dstart, dend; -char *rchg; +char *changed;long *rindex;long nreff; } xdfile_t;
xdiff/xutils.c +2 -2
@@ -425,8 +425,8 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,if (xdl_do_diff (&subfile1, &subfile2, xpp, &env) <0 )return -1 ; -memcpy (diff_env->xdf1.rchg + line1 -1 , env.xdf1.rchg, count1); -memcpy (diff_env->xdf2.rchg + line2 -1 , env.xdf2.rchg, count2); +memcpy (diff_env->xdf1.changed + line1 -1 , env.xdf1.changed, count1); +memcpy (diff_env->xdf2.changed + line2 -1 , env.xdf2.changed, count2);xdl_free_env (&env);
Signature · 1 line
gitgitgadget
Re: [PATCH v5 11/13] xdiff: rename rchg -> changed in xdfile_t
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
I agree "changed" is a better name but the commit message should explain what "rchg" is used for so that someone who is not familiar with the code can understand why the change in name is desirable.
Thanks
Phillip
Quoted 242 lines
Best-viewed-with: --color-words
Signed-off-by Ezekiel Newren <[email protected]>--- xdiff/xdiffi.c | 28 ++++++++++++++-------------- xdiff/xhistogram.c | 8 ++++---- xdiff/xpatience.c | 8 ++++---- xdiff/xprepare.c | 12 ++++++------ xdiff/xtypes.h | 2 +- xdiff/xutils.c | 4 ++-- 6 files changed, 31 insertions(+), 31 deletions(-)xdiff/xdiffi.c +14
-14@@ -278,10 +278,10 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,*/ if (off1 == lim1) {for (; off2 < lim2; off2++) - xdf2->rchg[xdf2->rindex[off2]] =1 ; + xdf2->changed[xdf2->rindex[off2]] =1 ; }else if (off2 == lim2) {for (; off1 < lim1; off1++) - xdf1->rchg[xdf1->rindex[off1]] =1 ; + xdf1->changed[xdf1->rindex[off1]] =1 ; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;@@ -708,7 +708,7 @@ struct xdlgroup {static void group_init (xdfile_t *xdf,struct xdlgroup *g) { g->start = g->end =0 ; -while (xdf->rchg[g->end]) +while (xdf->changed[g->end]) g->end++; }@@ -722,7 +722,7 @@ static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)return -1 ; g->start = g->end +1 ; -for (g->end = g->start; xdf->rchg[g->end]; g->end++) +for (g->end = g->start; xdf->changed[g->end]; g->end++) ;return 0 ;@@ -738,7 +738,7 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)return -1 ; g->end = g->start -1 ; -for (g->start = g->end; xdf->rchg[g->start -1 ]; g->start--) +for (g->start = g->end; xdf->changed[g->start -1 ]; g->start--) ;return 0 ;@@ -753,10 +753,10 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) {if (g->end < xdf->nrec &&recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { - xdf->rchg[g->start++] =0 ; - xdf->rchg[g->end++] =1 ; + xdf->changed[g->start++] =0 ; + xdf->changed[g->end++] =1 ; -while (xdf->rchg[g->end]) +while (xdf->changed[g->end]) g->end++;return 0 ;@@ -774,10 +774,10 @@ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) {if (g->start >0 &&recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { - xdf->rchg[--g->start] =1 ; - xdf->rchg[--g->end] =0 ; + xdf->changed[--g->start] =1 ; + xdf->changed[--g->end] =0 ; -while (xdf->rchg[g->start -1 ]) +while (xdf->changed[g->start -1 ]) g->start--;return 0 ;@@ -938,9 +938,9 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {* Trivial. Collects "groups" of changes and creates an edit script. */ for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >=0 || i2 >=0 ; i1--, i2--) -if (xe->xdf1.rchg[i1 -1 ] || xe->xdf2.rchg[i2 -1 ]) { -for (l1 = i1; xe->xdf1.rchg[i1 -1 ]; i1--); -for (l2 = i2; xe->xdf2.rchg[i2 -1 ]; i2--); +if (xe->xdf1.changed[i1 -1 ] || xe->xdf2.changed[i2 -1 ]) { +for (l1 = i1; xe->xdf1.changed[i1 -1 ]; i1--); +for (l2 = i2; xe->xdf2.changed[i2 -1 ]; i2--);if (!(xch =xdl_add_change (cscr, i1, i2, l1 - i1, l2 - i2))) {xdl_free_script (cscr);xdiff/xhistogram.c +4
-4@@ -318,11 +318,11 @@ redo:if (!count1) {while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;return 0 ; }@@ -335,9 +335,9 @@ redo:else {if (lcs.begin1 ==0 && lcs.begin2 ==0 ) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ; result =0 ; }else { result = histogram_diff(xpp, env,xdiff/xpatience.c +4
-4@@ -331,11 +331,11 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* trivial case: one side is empty */ if (!count1) {while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;return 0 ; }@@ -347,9 +347,9 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* are there any matching lines at all? */ if (!map.has_matches) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;xdl_free (map.entries);return 0 ; }xdiff/xprepare.c +6
-6@@ -126,7 +126,7 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_tstatic void xdl_free_ctx (xdfile_t *xdf) {xdl_free (xdf->rindex); -xdl_free (xdf->rchg -1 ); +xdl_free (xdf->changed -1 );xdl_free (xdf->recs); }@@ -139,7 +139,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_xrecord_t *crec; xdf->rindex =NULL ; - xdf->rchg =NULL ; + xdf->changed =NULL ; xdf->recs =NULL ;if (!XDL_ALLOC_ARRAY (xdf->recs, narec))@@ -161,7 +161,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ } } -if (!XDL_CALLOC_ARRAY (xdf->rchg, xdf->nrec +2 )) +if (!XDL_CALLOC_ARRAY (xdf->changed, xdf->nrec +2 )) goto abort; if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&@@ -170,7 +170,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ goto abort; } - xdf->rchg +=1 ; + xdf->changed +=1 ; xdf->nreff =0 ; xdf->dstart =0 ; xdf->dend = xdf->nrec -1 ;@@ -287,7 +287,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; } else - xdf1->rchg[i] = 1; + xdf1->changed[i] = 1; } xdf1->nreff = nreff;@@ -297,7 +297,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; } else - xdf2->rchg[i] = 1; + xdf2->changed[i] = 1; } xdf2->nreff = nreff;xdiff/xtypes.h +1
-1@@ -48,7 +48,7 @@ typedef struct s_xdfile {xrecord_t *recs;long nrec;long dstart, dend; -char *rchg; +char *changed;long *rindex;long nreff; } xdfile_t;xdiff/xutils.c +2
-2@@ -425,8 +425,8 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,if (xdl_do_diff (&subfile1, &subfile2, xpp, &env) <0 )return -1 ; -memcpy (diff_env->xdf1.rchg + line1 -1 , env.xdf1.rchg, count1); -memcpy (diff_env->xdf2.rchg + line2 -1 , env.xdf2.rchg, count2); +memcpy (diff_env->xdf1.changed + line1 -1 , env.xdf1.changed, count1); +memcpy (diff_env->xdf2.changed + line2 -1 , env.xdf2.changed, count2);xdl_free_env (&env);
Re: [PATCH v5 11/13] xdiff: rename rchg -> changed in xdfile_t
Quoted 7 lines · Phillip Wood
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
I agree "changed" is a better name but the commit message should explain what "rchg" is used for so that someone who is not familiar with the code can understand why the change in name is desirable.
The field rchg (now 'changed') declares if a line in a file is changed or not. A later commit will change it's type from 'char' to 'bool' to make its purpose even more clear.
Something like that?
Re: [PATCH v5 11/13] xdiff: rename rchg -> changed in xdfile_t
Quoted 9 lines · Ezekiel Newren
Quoted 7 lines · Phillip Wood
Quoted 1 line · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
I agree "changed" is a better name but the commit message should explain what "rchg" is used for so that someone who is not familiar with the code can understand why the change in name is desirable.
Quoted 5 lines
The field rchg (now 'changed') declares if a line in a file is changed or not. A later commit will change it's type from 'char' to 'bool' to make its purpose even more clear.
Something like that?
That's great
Phillip
PATCH v5 12/13 xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
Rename dis1, dis2 to matches1, matches2.
Define macros NONE(0), SOME(1), TOO_MANY(2) as the enum values for matches1 and matches2. These states will influence whether changed[i] is set to 1 or kept as 0.
Best-viewed-with: --color-words
--- xdiff/xprepare.c | 90 ++++++++++++++++++++++++++++++++---------------- 1 file changed, 60 insertions(+), 30 deletions(-)
xdiff/xprepare.c +60 -30
@@ -29,6 +29,9 @@#define XDL_GUESS_NLINES1 256#define XDL_GUESS_NLINES2 20 +#define NONE 0 +#define SOME 1 +#define TOO_MANY 2 typedef struct s_xdlclass { struct s_xdlclass *next;
@@ -190,12 +193,12 @@ void xdl_free_env(xdfenv_t *xe) { } -static int xdl_clean_mmatch (char const *dis,long i,long s,long e) { +static bool xdl_clean_mmatch (uint8_t const *matches,long i,long s,long e) {long r, rdis0, rpdis0, rdis1, rpdis1;/* -* Limits the window the is examined during the similar-lines -* scan. The loops below stops when dis[i - r] == 1 (line that +* Limits the window that is examined during the similar-lines +* scan. The loops below stops when matches[i - r] == SOME (line that * has no match), but there are corner cases where the loop * proceed all the way to the extremities by causing huge * performance penalties in case of big files.
@@ -207,40 +210,44 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {/* * Scans the lines before 'i' to find a run of lines that either -* have no match (dis[j] == 0) or have multiple matches (dis[j] > 1). -* Note that we always call this function with dis[i] > 1, so the +* have no match (matches[j] == NONE) or have multiple matches (matches[j] == TOO_MANY). +* Note that we always call this function with matches[i] == TOO_MANY, so the * current line (i) is already a multimatch line. */ for (r =1 , rdis0 =0 , rpdis0 =1 ; (i - r) >= s; r++) { -if (!dis[i - r]) +if (matches[i - r] ==NONE ) rdis0++; -else if (dis[i - r] ==2 ) +else if (matches[i - r] ==TOO_MANY ) rpdis0++; -else +else if (matches[i - r] ==SOME )break ; +else +BUG ("Illegal value for matches[i - r]" ); }/* * If the run before the line 'i' found only multimatch lines, we -* return 0 and hence we don't make the current line (i) discarded. +* return false and hence we don't make the current line (i) discarded. * We want to discard multimatch lines only when they appear in the -* middle of runs with nomatch lines (dis[j] == 0). +* middle of runs with nomatch lines (matches[j] == NONE). */ if (rdis0 ==0 )return 0 ;for (r =1 , rdis1 =0 , rpdis1 =1 ; (i + r) <= e; r++) { -if (!dis[i + r]) +if (matches[i + r] ==NONE ) rdis1++; -else if (dis[i + r] ==2 ) +else if (matches[i + r] ==TOO_MANY ) rpdis1++; -else +else if (matches[i + r] ==SOME )break ; +else +BUG ("Illegal value for matches[i + r]" ); }/* * If the run after the line 'i' found only multimatch lines, we -* return 0 and hence we don't make the current line (i) discarded. +* return false and hence we don't make the current line (i) discarded. */ if (rdis1 ==0 ) -return 0 ; +return false; rdis1 += rdis0; rpdis1 += rpdis0;
@@ -251,26 +258,41 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {/* * Try to reduce the problem complexity, discard records that have no * matches on the other file. Also, lines that have multiple matches -* might be potentially discarded if they happear in a run of discardable. +* might be potentially discarded if they appear in a run of discardable. */ static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2) {long i, nm, nreff, mlim;xrecord_t *recs;xdlclass_t *rcrec; -char *dis, *dis1, *dis2; -int need_min = !!(cf->flags &XDF_NEED_MINIMAL ); +uint8_t *matches1, *matches2; +int status =0 ; +bool need_min = !!(cf->flags &XDF_NEED_MINIMAL ); -if (!XDL_CALLOC_ARRAY (dis, xdf1->nrec + xdf2->nrec +2 )) -return -1 ; - dis1 = dis; - dis2 = dis1 + xdf1->nrec +1 ; + matches1 =NULL ; + matches2 =NULL ; + +/* +* Create temporary arrays that will help us decide if +* changed[i] should remain 0 or become 1. +*/ +if (!XDL_CALLOC_ARRAY (matches1, xdf1->nrec +1 )) { + status =-1 ; + goto cleanup; + } +if (!XDL_CALLOC_ARRAY (matches2, xdf2->nrec +1 )) { + status =-1 ; + goto cleanup; + } +/* +* Initialize temporary arrays with NONE, SOME, or TOO_MANY. +*/ if ((mlim =xdl_bogosqrt (xdf1->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len2 :0 ; - dis1[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; + matches1[i] = (nm ==0 ) ?NONE : (nm >= mlim && !need_min) ?TOO_MANY :SOME ; }if ((mlim =xdl_bogosqrt (xdf2->nrec)) >XDL_MAX_EQLIMIT )
@@ -278,14 +300,19 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len1 :0 ; - dis2[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; + matches2[i] = (nm ==0 ) ?NONE : (nm >= mlim && !need_min) ?TOO_MANY :SOME ; } +/* +* Use temporary arrays to decide if changed[i] should remain +* 0 or become 1. +*/ for (nreff =0 , i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { -if (dis1[i] ==1 || - (dis1[i] ==2 && !xdl_clean_mmatch (dis1, i, xdf1->dstart, xdf1->dend))) { +if (matches1[i] ==SOME || + (matches1[i] ==TOO_MANY && !xdl_clean_mmatch (matches1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; +/* changed[i] remains 0 */ }else xdf1->changed[i] =1 ; }
@@ -293,17 +320,20 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdfor (nreff =0 , i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { -if (dis2[i] ==1 || - (dis2[i] ==2 && !xdl_clean_mmatch (dis2, i, xdf2->dstart, xdf2->dend))) { +if (matches2[i] ==SOME || + (matches2[i] ==TOO_MANY && !xdl_clean_mmatch (matches2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; +/* changed[i] remains 0 */ }else xdf2->changed[i] =1 ; } xdf2->nreff = nreff; -xdl_free (dis); +cleanup: +xdl_free (matches1); +xdl_free (matches2); -return 0 ; +return status; }
Signature · 1 line
gitgitgadget
Re: [PATCH v5 12/13] xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
Quoted 7 lines · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
Rename dis1, dis2 to matches1, matches2.
Define macros NONE(0), SOME(1),
TOO_MANY(2)as the enum values for matches1 and matches2. These states will influence whether changed[i] is set to 1 or kept as 0.
This message also says what is being changed rather than why it is being changed. I think the rename here is a good idea but I'm not sure what "rdis[01]" and "rpdis[01]" are used for and whether they should be renamed if we're renaming "dis[01]"
xdiff/xprepare.c void xdl_free_env(xdfenv_t *xe) { · line 201
Quoted 5 lines
/*
xdiff/xprepare.c +2
-2-* Limits the window the is examined during the similar-lines -* scan. The loops below stops when dis[i - r] == 1 (line that +* Limits the window that is examined during the similar-lines +* scan. The loops below stops when matches[i - r] == SOME (line that
Thanks for updating the comments. Not reflowing the lines makes the diff easier to read but leaves the comments in a rather strange state with random long lines.
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 214
Quoted 11 lines
* has no match), but there are corner cases where the loop
* proceed all the way to the extremities by causing huge
* performance penalties in case of big files.xdiff/xprepare.c +2
-2@@ -207,40 +210,44 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {/* * Scans the lines before 'i' to find a run of lines that either -* have no match (dis[j] == 0) or have multiple matches (dis[j] > 1). -* Note that we always call this function with dis[i] > 1, so the +* have no match (matches[j] == NONE) or have multiple matches (matches[j] == TOO_MANY). +* Note that we always call this function with matches[i] == TOO_MANY, so the
especially here
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 243
Quoted 11 lines
xdiff/xprepare.c +5
-3-if (!dis[i + r]) +if (matches[i + r] ==NONE ) rdis1++; -else if (dis[i + r] ==2 ) +else if (matches[i + r] ==TOO_MANY ) rpdis1++; -else +else if (matches[i + r] ==SOME )break ; +else +BUG ("Illegal value for matches[i + r]" );
Nice addition
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 267
Quoted 7 lines
xdiff/xprepare.c +1
-2static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2) {long i, nm, nreff, mlim;xrecord_t *recs;xdlclass_t *rcrec; -char *dis, *dis1, *dis2; -int need_min = !!(cf->flags &XDF_NEED_MINIMAL ); +uint8_t *matches1, *matches2;
Let's initialize these where they're declared rather than later on
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 268
Quoted 1 line
xdiff/xprepare.c +1
-0+int status =0 ;
I think we typically we call this "ret" or "res" in the rest of the code base.
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 269
Quoted 1 line
xdiff/xprepare.c +1
-0+bool need_min = !!(cf->flags &XDF_NEED_MINIMAL );
Nice use of bool, strictly speaking I don't think we need the !! if we're changing the type from int. I think Junio recently suggested that we might start using (bool) instead of !! for cases like this.
Everything below this looks good, though some of the lines are getting quite long with the renamed variables and symbolic values so we might want to break them.
Thanks
Phillip
Quoted 81 lines
xdiff/xprepare.c +34
-12-if (!XDL_CALLOC_ARRAY (dis, xdf1->nrec + xdf2->nrec +2 )) -return -1 ; - dis1 = dis; - dis2 = dis1 + xdf1->nrec +1 ; + matches1 =NULL ; + matches2 =NULL ; + +/* +* Create temporary arrays that will help us decide if +* changed[i] should remain 0 or become 1. +*/ +if (!XDL_CALLOC_ARRAY (matches1, xdf1->nrec +1 )) { + status =-1 ; + goto cleanup; + } +if (!XDL_CALLOC_ARRAY (matches2, xdf2->nrec +1 )) { + status =-1 ; + goto cleanup; + } +/* +* Initialize temporary arrays with NONE, SOME, or TOO_MANY. +*/ if ((mlim =xdl_bogosqrt (xdf1->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len2 :0 ; - dis1[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; + matches1[i] = (nm ==0 ) ?NONE : (nm >= mlim && !need_min) ?TOO_MANY :SOME ; }if ((mlim =xdl_bogosqrt (xdf2->nrec)) >XDL_MAX_EQLIMIT )@@ -278,14 +300,19 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len1 :0 ; - dis2[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; + matches2[i] = (nm ==0 ) ?NONE : (nm >= mlim && !need_min) ?TOO_MANY :SOME ; } +/* +* Use temporary arrays to decide if changed[i] should remain +* 0 or become 1. +*/ for (nreff =0 , i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { -if (dis1[i] ==1 || - (dis1[i] ==2 && !xdl_clean_mmatch (dis1, i, xdf1->dstart, xdf1->dend))) { +if (matches1[i] ==SOME || + (matches1[i] ==TOO_MANY && !xdl_clean_mmatch (matches1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; +/* changed[i] remains 0 */ }else xdf1->changed[i] =1 ; }@@ -293,17 +320,20 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdfor (nreff =0 , i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { -if (dis2[i] ==1 || - (dis2[i] ==2 && !xdl_clean_mmatch (dis2, i, xdf2->dstart, xdf2->dend))) { +if (matches2[i] ==SOME || + (matches2[i] ==TOO_MANY && !xdl_clean_mmatch (matches2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; +/* changed[i] remains 0 */ }else xdf2->changed[i] =1 ; } xdf2->nreff = nreff; -xdl_free (dis); +cleanup: +xdl_free (matches1); +xdl_free (matches2); -return 0 ; +return status; }
Re: [PATCH v5 12/13] xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
Quoted 6 lines · Phillip Wood
Quoted 4 lines · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
Rename dis1, dis2 to matches1, matches2.
Quoted 8 lines
Quoted 3 lines
Define macros NONE(0), SOME(1),
TOO_MANY(2)as the enum values for matches1 and matches2. These states will influence whether changed[i] is set to 1 or kept as 0.This message also says what is being changed rather than why it is being changed. I think the rename here is a good idea but I'm not sure what "rdis[01]" and "rpdis[01]" are used for and whether they should be renamed if we're renaming "dis[01]"
"Rename dis1, dis2 to matches1, matches2 to give the variable names a more obvious meaning."
Would something like that work, or do I need to refine it further? I would love to rename rdis, rpdis, etc... except that I don't understand what is happening or why. Could someone explain the purpose of these variables?
Quoted 9 lines
xdiff/xprepare.c void xdl_free_env(xdfenv_t *xe) { · line 201
Quoted 5 lines
/*xdiff/xprepare.c +2
-2-* Limits the window the is examined during the similar-lines -* scan. The loops below stops when dis[i - r] == 1 (line that +* Limits the window that is examined during the similar-lines +* scan. The loops below stops when matches[i - r] == SOME (line that Thanks for updating the comments. Not reflowing the lines makes the diff easier to read but leaves the comments in a rather strange state with random long lines.
What is the reflow limit for comments? 72? 80?
Quoted 26 lines
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 214
Quoted 11 lines
* has no match), but there are corner cases where the loop
* proceed all the way to the extremities by causing huge
* performance penalties in case of big files.xdiff/xprepare.c +2
-2@@ -207,40 +210,44 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {/* * Scans the lines before 'i' to find a run of lines that either -* have no match (dis[j] == 0) or have multiple matches (dis[j] > 1). -* Note that we always call this function with dis[i] > 1, so the +* have no match (matches[j] == NONE) or have multiple matches (matches[j] == TOO_MANY). +* Note that we always call this function with matches[i] == TOO_MANY, so the especially here
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 243
Quoted 11 lines
xdiff/xprepare.c +5
-3-if (!dis[i + r]) +if (matches[i + r] ==NONE ) rdis1++; -else if (dis[i + r] ==2 ) +else if (matches[i + r] ==TOO_MANY ) rpdis1++; -else +else if (matches[i + r] ==SOME )break ; +else +BUG ("Illegal value for matches[i + r]" );
Quoted 1 line
Nice addition
Thanks.
Quoted 9 lines
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 267
Quoted 7 lines
xdiff/xprepare.c +1
-2static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2) {long i, nm, nreff, mlim;xrecord_t *recs;xdlclass_t *rcrec; -char *dis, *dis1, *dis2; -int need_min = !!(cf->flags &XDF_NEED_MINIMAL ); +uint8_t *matches1, *matches2;Let's initialize these where they're declared rather than later on
I can do that.
Quoted 6 lines
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 268
Quoted 1 line
xdiff/xprepare.c +1
-0+int status =0 ;I think we typically we call this "ret" or "res" in the rest of the code base.
xdiff/xprepare.c static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { · line 269
Quoted 1 line
xdiff/xprepare.c +1
-0+bool need_min = !!(cf->flags &XDF_NEED_MINIMAL );
Quoted 7 lines
Nice use of bool, strictly speaking I don't think we need the !! if we're changing the type from int. I think Junio recently suggested that we might start using (bool) instead of !! for cases like this.
Everything below this looks good, though some of the lines are getting quite long with the renamed variables and symbolic values so we might want to break them.
I didn't add !! and thought it looked funny myself. I didn't remove it because I wasn't sure if I should.
Re: [PATCH v5 12/13] xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
Quoted 16 lines · Ezekiel Newren
Quoted 6 lines · Phillip Wood
Quoted 4 lines · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
Rename dis1, dis2 to matches1, matches2.
Quoted 8 lines
Quoted 3 lines
Define macros NONE(0), SOME(1),
TOO_MANY(2)as the enum values for matches1 and matches2. These states will influence whether changed[i] is set to 1 or kept as 0.This message also says what is being changed rather than why it is being changed. I think the rename here is a good idea but I'm not sure what "rdis[01]" and "rpdis[01]" are used for and whether they should be renamed if we're renaming "dis[01]"
Quoted 4 lines
"Rename dis1, dis2 to matches1, matches2 to give the variable names a more obvious meaning."
Would something like that work, or do I need to refine it further?
I'd maybe add a sentence before that to explain that "dis1 and dis2 are used to record if a line has zero, one or many matches on the other side of the diff". I don't think any of these patches need huge commit messages but a couple of sentences explaining the reasoning would be helpful for anyone looking at them it the future.
Quoted 4 lines
I
would love to rename rdis, rpdis, etc... except that I don't understand what is happening or why. Could someone explain the purpose of these variables?
Good question, I'm not sure anyone has an intimate knowledge of this code. My understanding is that the code aims to remove runs of common lines when they occur between unique lines in order to reduce the number of lines we need to look at when we're calculating the diff. I haven't worked through the code in detail though.
Quoted 11 lines
Quoted 9 lines
xdiff/xprepare.c void xdl_free_env(xdfenv_t *xe) { · line 201
Quoted 5 lines
/*xdiff/xprepare.c +2
-2-* Limits the window the is examined during the similar-lines -* scan. The loops below stops when dis[i - r] == 1 (line that +* Limits the window that is examined during the similar-lines +* scan. The loops below stops when matches[i - r] == SOME (line that Thanks for updating the comments. Not reflowing the lines makes the diff easier to read but leaves the comments in a rather strange state with random long lines.
What is the reflow limit for comments? 72? 80?
For code it's 80 columns with a little leaway if that makes things clearer. For comments I'd match whatever it is using at the moment.
Quoted 7 lines
Quoted 7 lines
Quoted 2 lines
+ bool
need_min= !!(cf->flags &XDF_NEED_MINIMAL);Nice use of bool, strictly speaking I don't think we need the !! if we're changing the type from int. I think Junio recently suggested that we might start using (bool) instead of !! for cases like this.
Quoted 6 lines
Quoted 3 lines
Everything below this looks good, though some of the lines are getting quite long with the renamed variables and symbolic values so we might want to break them.
I didn't add !! and thought it looked funny myself. I didn't remove it because I wasn't sure if I should.
Our coding guidelines say not to use "!!x" (I assume we're supposed to do "x != 0" instead) but in practice it's pretty common to see it in our codebase. I'd maybe try a (bool) cast and see what people say.
Thanks for cleaning up the xdiff code, it is much appreciated
Phillip
Re: [PATCH v5 12/13] xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
Quoted 3 lines · Phillip Wood
Our coding guidelines say not to use "!!x" (I assume we're supposed to do "x != 0" instead) but in practice it's pretty common to see it in our codebase. I'd maybe try a (bool) cast and see what people say.
Offtopic. I am perfectly fine to remove the "avoid !!x, as it is too clever and confusing to others" entry from the guidelines. As we have many of them and it is a fairly well understood idiom in C, I would imagine that it have become less confusing already since the entry was written.
Quoted 1 line
Thanks for cleaning up the xdiff code, it is much appreciated
Hear, hear.
Re: [PATCH v5 12/13] xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
In reply to Phillip WoodQuoted 34 lines · Phillip Wood
Quoted 16 lines · Ezekiel Newren
Quoted 6 lines · Phillip Wood
Quoted 4 lines · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
Rename dis1, dis2 to matches1, matches2.
Quoted 8 lines
Quoted 3 lines
Define macros NONE(0), SOME(1),
TOO_MANY(2)as the enum values for matches1 and matches2. These states will influence whether changed[i] is set to 1 or kept as 0.This message also says what is being changed rather than why it is being changed. I think the rename here is a good idea but I'm not sure what "rdis[01]" and "rpdis[01]" are used for and whether they should be renamed if we're renaming "dis[01]"
Quoted 4 lines
"Rename dis1, dis2 to matches1, matches2 to give the variable names a more obvious meaning."
Would something like that work, or do I need to refine it further?
I'd maybe add a sentence before that to explain that "dis1 and dis2 are used to record if a line has zero, one or many matches on the other side of the diff". I don't think any of these patches need huge commit messages but a couple of sentences explaining the reasoning would be helpful for anyone looking at them it the future.
Quoted 4 lines
I
would love to rename rdis, rpdis, etc... except that I don't understand what is happening or why. Could someone explain the purpose of these variables?
Quoted 5 lines
Good question, I'm not sure anyone has an intimate knowledge of this code. My understanding is that the code aims to remove runs of common lines when they occur between unique lines in order to reduce the number of lines we need to look at when we're calculating the diff. I haven't worked through the code in detail though.
I'm really struggling with how to write this commit message. I would very much appreciate suggestions. Here is what I have so far:
--- commit message start ---
xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
The local variables dis1 and dis2 describe how a line should be treated based on how many lines, in the other file, match this line. NONE means the other file does not have any matches to this line. SOME means that there are more than 0 matches, but less than some heuristic threshold. TOO_MANY is when there are more matches than that heuristic threshold.
Note: When need_min is true, matches[i] is always set to SOME when the number of matches is greater than 0.
The names dis1 and dis2 don't convey what they mean, so let's rename them to matches1 and matches2.
Define macros NONE(0), SOME(1), TOO_MANY(2) as the enum values for matches1 and matches2. These states will influence whether changed[i] is set to 1 or kept as 0.
The variables r, rdis0, rpdis0, rdis1, rpdis1 in xdl_clean_mmatch() have not been renamed because I don't understand their purpose. --- commit message end ---
I'll explain the parts of the code that are relevant to the commit message with an example. The following snippet goes through every line (matches1[i]) of file1 to determine what matches1[i] should be by looking at the number of times that line shows up in file2.
if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
mlim = XDL_MAX_EQLIMIT;
for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <=
xdf1->dend; i++, recs++) {
rcrec = cf->rcrecs[recs->ha];
nm = rcrec ? rcrec->len2 : 0;
matches1[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ?
TOO_MANY: SOME;
}The lines:
rcrec = cf->rcrecs[recs->ha];
nm = rcrec ? rcrec->len2 : 0;
gets the number of matches from file2 (i.e. rcrec->len2), and then this line:
matches1[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME;Is the logic to set matches1[i] (the line in question of file1) to NONE, SOME, or TOO_MANY.
mlim seems to be some heuristic threshold based on the XDL_MAX_EQLIMIT constant which is set to 1024.
Re: [PATCH v5 12/13] xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
Quoted 5 lines · Ezekiel Newren
I'm really struggling with how to write this commit message. I would very much appreciate suggestions. Here is what I have so far:
--- commit message start ---
xdiff: use enum macros NONE(0), SOME(1),TOO_MANY(2)inxprepare.c
...
I think I understand what is happening now. The macros I should be using are: DISCARD(0), KEEP(1), INVESTIGATE(2). The comments in and around xdl_cleanup_records() and xdl_clean_mmatch() uses the term discard, and not discarded. I think what DISCARD means is discard this line from consideration in the diff algorithm, and KEEP means the diff algorithm is going to look at that line. INVESTIGATE means that the current line has more matches in the other file than some threshold, so we need to do some more work to decide if the line should be kept or discarded.
xdl_cleanup_records() does not belong in xprepare.c because it is only used by the classic diff (myers/minimal). It should be moved to xdiffi.c, but it depends on the classifier which is only defined in xprepare.c. So I can't move xdl_cleanup_records() until more of the code has been cleaned up.
I'll work on the commit, and hopefully publish the next version soon.
PATCH v5 13/13 xdiff: change type of xdfile_t.changed from char to bool
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
The only values possible for 'changed' is 1 and 0, which exactly maps to a bool type. It might not look like this is the case because matches1 and matches2 (which use to be dis1, and dis2) were also char and were assigned numerical values within a few lines of 'changed' (what used to be rchg).
Using NONE, SOME, TOO_MANY for matches1[i]/matches2[j], and true/false for changed[k] makes it clear to future readers that these are logically separate concepts.
Best-viewed-with: --color-words
--- xdiff/xdiffi.c | 12 ++++++------ xdiff/xhistogram.c | 8 ++++---- xdiff/xpatience.c | 8 ++++---- xdiff/xprepare.c | 12 ++++++------ xdiff/xtypes.h | 2 +- 5 files changed, 21 insertions(+), 21 deletions(-)
xdiff/xdiffi.c +6 -6
@@ -278,10 +278,10 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,*/ if (off1 == lim1) {for (; off2 < lim2; off2++) - xdf2->changed[xdf2->rindex[off2]] =1 ; + xdf2->changed[xdf2->rindex[off2]] = true; }else if (off2 == lim2) {for (; off1 < lim1; off1++) - xdf1->changed[xdf1->rindex[off1]] =1 ; + xdf1->changed[xdf1->rindex[off1]] = true; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;
@@ -753,8 +753,8 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) {if (g->end < xdf->nrec &&recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { - xdf->changed[g->start++] =0 ; - xdf->changed[g->end++] =1 ; + xdf->changed[g->start++] = false; + xdf->changed[g->end++] = true;while (xdf->changed[g->end]) g->end++;
@@ -774,8 +774,8 @@ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) {if (g->start >0 &&recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { - xdf->changed[--g->start] =1 ; - xdf->changed[--g->end] =0 ; + xdf->changed[--g->start] = true; + xdf->changed[--g->end] = false;while (xdf->changed[g->start -1 ]) g->start--;
xdiff/xhistogram.c +4 -4
@@ -318,11 +318,11 @@ redo:if (!count1) {while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;return 0 ; }
@@ -335,9 +335,9 @@ redo:else {if (lcs.begin1 ==0 && lcs.begin2 ==0 ) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true; result =0 ; }else { result = histogram_diff(xpp, env,
xdiff/xpatience.c +4 -4
@@ -331,11 +331,11 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* trivial case: one side is empty */ if (!count1) {while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;return 0 ; }
@@ -347,9 +347,9 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* are there any matching lines at all? */ if (!map.has_matches) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;xdl_free (map.entries);return 0 ; }
xdiff/xprepare.c +6 -6
@@ -273,7 +273,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd/* * Create temporary arrays that will help us decide if -* changed[i] should remain 0 or become 1. +* changed[i] should remain false, or become true. */ if (!XDL_CALLOC_ARRAY (matches1, xdf1->nrec +1 )) { status =-1 ;
@@ -305,16 +305,16 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd/* * Use temporary arrays to decide if changed[i] should remain -* 0 or become 1. +* false, or become true. */ for (nreff =0 , i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {if (matches1[i] ==SOME || (matches1[i] ==TOO_MANY && !xdl_clean_mmatch (matches1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; -/* changed[i] remains 0 */ +/* changed[i] remains false */ }else - xdf1->changed[i] =1 ; + xdf1->changed[i] = true; } xdf1->nreff = nreff;
@@ -323,9 +323,9 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif (matches2[i] ==SOME || (matches2[i] ==TOO_MANY && !xdl_clean_mmatch (matches2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; -/* changed[i] remains 0 */ +/* changed[i] remains false */ }else - xdf2->changed[i] =1 ; + xdf2->changed[i] = true; } xdf2->nreff = nreff;
xdiff/xtypes.h +1 -1
@@ -48,7 +48,7 @@ typedef struct s_xdfile {xrecord_t *recs;long nrec;long dstart, dend; -char *changed; +bool *changed;long *rindex;long nreff; } xdfile_t;
Signature · 1 line
gitgitgadget
Re: [PATCH v5 13/13] xdiff: change type of xdfile_t.changed from char to bool
Quoted 11 lines · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
The only values possible for 'changed' is 1 and 0, which exactly maps to a bool type. It might not look like this is the case because matches1 and matches2 (which use to be dis1, and dis2) were also char and were assigned numerical values within a few lines of 'changed' (what used to be rchg).
Using NONE, SOME,
TOO_MANYfor matches1[i]/matches2[j], and true/false for changed[k] makes it clear to future readers that these are logically separate concepts.
Nicely explained - I think this change is a very good idea and separating it out like this makes it much clearer what's going on compared to V4.
Thanks
Phillip
Quoted 167 lines
Best-viewed-with: --color-words
Signed-off-by Ezekiel Newren <[email protected]>--- xdiff/xdiffi.c | 12 ++++++------ xdiff/xhistogram.c | 8 ++++---- xdiff/xpatience.c | 8 ++++---- xdiff/xprepare.c | 12 ++++++------ xdiff/xtypes.h | 2 +- 5 files changed, 21 insertions(+), 21 deletions(-)xdiff/xdiffi.c +6
-6@@ -278,10 +278,10 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,*/ if (off1 == lim1) {for (; off2 < lim2; off2++) - xdf2->changed[xdf2->rindex[off2]] =1 ; + xdf2->changed[xdf2->rindex[off2]] = true; }else if (off2 == lim2) {for (; off1 < lim1; off1++) - xdf1->changed[xdf1->rindex[off1]] =1 ; + xdf1->changed[xdf1->rindex[off1]] = true; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;@@ -753,8 +753,8 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) {if (g->end < xdf->nrec &&recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { - xdf->changed[g->start++] =0 ; - xdf->changed[g->end++] =1 ; + xdf->changed[g->start++] = false; + xdf->changed[g->end++] = true;while (xdf->changed[g->end]) g->end++;@@ -774,8 +774,8 @@ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) {if (g->start >0 &&recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { - xdf->changed[--g->start] =1 ; - xdf->changed[--g->end] =0 ; + xdf->changed[--g->start] = true; + xdf->changed[--g->end] = false;while (xdf->changed[g->start -1 ]) g->start--;xdiff/xhistogram.c +4
-4@@ -318,11 +318,11 @@ redo:if (!count1) {while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;return 0 ; }@@ -335,9 +335,9 @@ redo:else {if (lcs.begin1 ==0 && lcs.begin2 ==0 ) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true; result =0 ; }else { result = histogram_diff(xpp, env,xdiff/xpatience.c +4
-4@@ -331,11 +331,11 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* trivial case: one side is empty */ if (!count1) {while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;return 0 ; }@@ -347,9 +347,9 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* are there any matching lines at all? */ if (!map.has_matches) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;xdl_free (map.entries);return 0 ; }xdiff/xprepare.c +6
-6@@ -273,7 +273,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd/* * Create temporary arrays that will help us decide if -* changed[i] should remain 0 or become 1. +* changed[i] should remain false, or become true. */ if (!XDL_CALLOC_ARRAY (matches1, xdf1->nrec +1 )) { status =-1 ;@@ -305,16 +305,16 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd/* * Use temporary arrays to decide if changed[i] should remain -* 0 or become 1. +* false, or become true. */ for (nreff =0 , i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {if (matches1[i] ==SOME || (matches1[i] ==TOO_MANY && !xdl_clean_mmatch (matches1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; -/* changed[i] remains 0 */ +/* changed[i] remains false */ }else - xdf1->changed[i] =1 ; + xdf1->changed[i] = true; } xdf1->nreff = nreff;@@ -323,9 +323,9 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif (matches2[i] ==SOME || (matches2[i] ==TOO_MANY && !xdl_clean_mmatch (matches2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; -/* changed[i] remains 0 */ +/* changed[i] remains false */ }else - xdf2->changed[i] =1 ; + xdf2->changed[i] = true; } xdf2->nreff = nreff;xdiff/xtypes.h +1
-1@@ -48,7 +48,7 @@ typedef struct s_xdfile {xrecord_t *recs;long nrec;long dstart, dend; -char *changed; +bool *changed;long *rindex;long nreff; } xdfile_t;
Re: [PATCH v5 13/13] xdiff: change type of xdfile_t.changed from char to bool
Quoted 10 lines · Phillip Wood
Quoted 8 lines · Ezekiel Newren via GitGitGadget
From: Ezekiel Newren <[email protected]>
The only values possible for 'changed' is 1 and 0, which exactly maps to a bool type. It might not look like this is the case because matches1 and matches2 (which use to be dis1, and dis2) were also char and were assigned numerical values within a few lines of 'changed' (what used to be rchg).
Quoted 7 lines
Quoted 3 lines
Using NONE, SOME,
TOO_MANYfor matches1[i]/matches2[j], and true/false for changed[k] makes it clear to future readers that these are logically separate concepts.Nicely explained - I think this change is a very good idea and separating it out like this makes it much clearer what's going on compared to V4.
Thank you! It was obvious to me because I've been refactoring xdiff for many months now, but I wasn't doing a good job of expressing why these 2 concepts are closely related, but distinct.
v6 cover Cleanup xdfile_t and xrecord_t in xdiff.
In reply to Ezekiel Newren via GitGitGadgetChanges since v5.
* Address review feedback on commit messages.
* Drop commit "xdiff: delete rchg aliasing"
* Use DISCARD/KEEP/INVESTIGATE instead of NONE/SOME/TOO_MANY
* Fix the word wrapping in the comments of xprepare.c
Cleanup of the functions xdl_cleanup_records() and xdl_clean_mmatch() is out of scope for this patch series. The changes to them are incidental to explaining why 'char rchg' is refactored to 'bool changed'.
Changes since v4.
* Make it clear that the field xdfile_t.rchg (now 'xdfile_t.changed') is distinct from the local variables dis1, dis2 (now 'matches1', 'matches2').
* Use NONE, SOME, TOO_MANY instead of NO, YES, MAYBE.
* Use bool literals for xdfile_t.changed.
Changes since v3.
* Address review feedback.
* Split the deletion of xdl_get_rec() into 2 commits.
* Move NO, YES, MAYBE into xprepare.c, and use bool literals.
* refactor 'char rchg' to 'bool changed'
Changes since v2.
* No patch changes, just resending to get patch 9 to show up on the mailing list.
* A few tweaks to the cover letter.
Changes since v1, to address review feedback.
* Only include the clean up patches; The remaining patches will be split into a separate series.
* Commit message clarifications.
* Minor style cleanups.
* Performance impacts included in commit message of patch 8.
Relevant part of the original cover letter follows:
===================================================
Before:
typedef struct s_xrecord {
struct s_xrecord *next;
char const *ptr;
long size;
unsigned long ha;
} xrecord_t;typedef struct s_xdfile {
chastore_t rcha;
long nrec;
unsigned int hbits;
xrecord_t **rhash;
long dstart, dend;
xrecord_t **recs;
char *rchg;
long *rindex;
long nreff;
unsigned long *ha;
} xdfile_t;After cleanup:
typedef struct s_xrecord {
char const *ptr;
long size;
unsigned long ha;
} xrecord_t;typedef struct s_xdfile {
xrecord_t *recs;
long nrec;
long dstart, dend;
bool *changed;
long *rindex;
long nreff;
} xdfile_t;===
Ezekiel Newren (12):
xdiff: delete static forward declarations in xprepare
xdiff: delete local variables and initialize/free xdfile_t directly
xdiff: delete unnecessary fields from xrecord_t and xdfile_t
xdiff: delete superfluous function xdl_get_rec() in xemit
xdiff: delete local variables that alias fields in xrecord_t
xdiff: delete struct diffdata_t
xdiff: delete redundant array xdfile_t.ha
xdiff: delete fields ha, line, size in xdlclass_t in favor of an
xrecord_t
xdiff: delete chastore from xdfile_t
xdiff: rename rchg -> changed in xdfile_t
xdiff: add macros DISCARD(0), KEEP(1), INVESTIGATE(2) in xprepare.c
xdiff: change type of xdfile_t.changed from char to bool
xdiff/xdiffi.c | 102 ++++++------- xdiff/xdiffi.h | 11 +- xdiff/xemit.c | 38 ++--- xdiff/xhistogram.c | 10 +- xdiff/xmerge.c | 56 ++++---- xdiff/xpatience.c | 18 +-- xdiff/xprepare.c | 346 ++++++++++++++++++++------------------------- xdiff/xtypes.h | 9 +- xdiff/xutils.c | 16 +-- 9 files changed, 269 insertions(+), 337 deletions(-)
base-commit: c44beea485f0f2feaf460e2ac87fdd5608d63cf0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2048%2Fezekielnewren%2Fuse_rust_types_in_xdiff-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2048/ezekielnewren/use_rust_types_in_xdiff-v6
Pull-Request: https://github.com/git/git/pull/2048
Range-diff vs v5:
1: 890e508000 = 1: 890e508000 xdiff: delete static forward declarations in xprepare 2: 0cfd75b1ff = 2: 0cfd75b1ff xdiff: delete local variables and initialize/free xdfile_t directly 3: 92c81d2ff6 = 3: 92c81d2ff6 xdiff: delete unnecessary fields from xrecord_t and xdfile_t 4: 7d3a7e617c = 4: 7d3a7e617c xdiff: delete superfluous function xdl_get_rec() in xemit 5: 1d550cf308 ! 5: 7a9380328e xdiff: delete superfluous local variables that alias fields in xrecord_t
@@ Metadata
Author: Ezekiel Newren <[email protected]>
## Commit message ##
- xdiff: delete superfluous local variables that alias fields in xrecord_t
+ xdiff: delete local variables that alias fields in xrecord_t
Use the type xrecord_t as the local variable for the functions in the
- file xdiff/xemit.c.
+ file xdiff/xemit.c. Most places directly reference the fields inside of
+ this struct, doing that here makes it more consistent with the rest of
+ the code.
6: 2a3a1b657e ! 6: 6dce41cd3d xdiff: delete struct diffdata_t
@@ Commit message
diffdata_t.rindex -> xdfile_t.rindex
diffdata_t.rchg -> xdfile_t.rchg
+ I think this struct existed before xdfile_t, and was kept for backward
+ compatibility reasons. I think xdiffi should have been refactored to
+ use the new (xdfile_t) struct, but was easier to alias it instead.
+
+ The local variables rchg* and rindex* don't shorten the lines by much,
+ nor do they really need to be there to make the code more readable.
+ Delete them.
+
## xdiff/xdiffi.c ##
7: 4c6543cbe3 = 7: 637d1032ab xdiff: delete redundant array xdfile_t.ha
8: 21bf4b5a20 = 8: 738daab090 xdiff: delete fields ha, line, size in xdlclass_t in favor of an xrecord_t
9: ef6ae7d29c = 9: 59b00b63b8 xdiff: delete chastore from xdfile_t
10: 7b0856108a < -: ---------- xdiff: delete rchg aliasing
11: 570ab9f898 ! 10: 5702ca6912 xdiff: rename rchg -> changed in xdfile_t
@@ Metadata
## Commit message ##
xdiff: rename rchg -> changed in xdfile_t
+ The field rchg (now 'changed') declares if a line in a file is changed
+ or not. A later commit will change it's type from 'char' to 'bool'
+ to make its purpose even more clear.
+
Best-viewed-with: --color-words
Signed-off-by: Ezekiel Newren <[email protected]>
@@ xdiff/xdiffi.c: static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g)
g->start--;
return 0;
-@@ xdiff/xdiffi.c: int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
+@@ xdiff/xdiffi.c: int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
+
+ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
+ xdchange_t *cscr = NULL, *xch;
+- char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
++ char *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;
+ long i1, i2, l1, l2;
+
+ /*
* Trivial. Collects "groups" of changes and creates an edit script.
*/
for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
-- if (xe->xdf1.rchg[i1 - 1] || xe->xdf2.rchg[i2 - 1]) {
-- for (l1 = i1; xe->xdf1.rchg[i1 - 1]; i1--);
-- for (l2 = i2; xe->xdf2.rchg[i2 - 1]; i2--);
-+ if (xe->xdf1.changed[i1 - 1] || xe->xdf2.changed[i2 - 1]) {
-+ for (l1 = i1; xe->xdf1.changed[i1 - 1]; i1--);
-+ for (l2 = i2; xe->xdf2.changed[i2 - 1]; i2--);
+- if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
+- for (l1 = i1; rchg1[i1 - 1]; i1--);
+- for (l2 = i2; rchg2[i2 - 1]; i2--);
++ if (changed1[i1 - 1] || changed2[i2 - 1]) {
++ for (l1 = i1; changed1[i1 - 1]; i1--);
++ for (l2 = i2; changed2[i2 - 1]; i2--);
if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
xdl_free_script(cscr);
12: 08a0fceb72 ! 11: f08782a977 xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
@@ Metadata
Author: Ezekiel Newren <[email protected]>
## Commit message ##
- xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
+ xdiff: add macros DISCARD(0), KEEP(1), INVESTIGATE(2) in xprepare.c
- Rename dis1, dis2 to matches1, matches2.
+ This commit is refactor-only; no behavior is changed. A future commit
+ will use bool literals for changed[i].
- Define macros NONE(0), SOME(1), TOO_MANY(2) as the enum values for
- matches1 and matches2. These states will influence whether changed[i]
- is set to 1 or kept as 0.
+ The functions xdl_clean_mmatch() and xdl_cleanup_records() will be
+ cleaned up more in a future patch series. The changes to
+ xdl_cleanup_records(), in this patch, is just to make it clear why
+ `char rchg` is refactored to `bool changed`.
+
+ Rename dis* to action* and replace literal numericals with macros.
+ The old names came from when dis* (which I think was short for discard)
+ was treated like a boolean, but over time it grew into a ternary state
+ machine. The result was confusing because dis* and rchg* both used 0/1
+ values with different meanings.
+
+ The new names and macros make the states explicit. nm is short for
+ number of matches, and mlim is a heuristic limit:
+
+ nm == 0 -> action[i] = DISCARD -> changed[i] = true
+ 0 < nm < mlim -> action[i] = KEEP -> changed[i] = false
+ nm >= mlim -> action[i] = INVESTIGATE -> changed[i] = xdl_clean_mmatch()
+
+ When need_min is true, only DISCARD and KEEP occur because the limit
+ is effectively infinite.
Best-viewed-with: --color-words
Signed-off-by: Ezekiel Newren <[email protected]>
@@ xdiff/xprepare.c
#define XDL_GUESS_NLINES1 256
#define XDL_GUESS_NLINES2 20
-+#define NONE 0
-+#define SOME 1
-+#define TOO_MANY 2
++#define DISCARD 0
++#define KEEP 1
++#define INVESTIGATE 2
typedef struct s_xdlclass {
struct s_xdlclass *next;
@@ xdiff/xprepare.c: void xdl_free_env(xdfenv_t *xe) {
-static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
-+static bool xdl_clean_mmatch(uint8_t const *matches, long i, long s, long e) {
++static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) {
long r, rdis0, rpdis0, rdis1, rpdis1;
/*
- * Limits the window the is examined during the similar-lines
- * scan. The loops below stops when dis[i - r] == 1 (line that
+- * has no match), but there are corner cases where the loop
+- * proceed all the way to the extremities by causing huge
+- * performance penalties in case of big files.
+ * Limits the window that is examined during the similar-lines
-+ * scan. The loops below stops when matches[i - r] == SOME (line that
- * has no match), but there are corner cases where the loop
- * proceed all the way to the extremities by causing huge
- * performance penalties in case of big files.
++ * scan. The loops below stops when action[i - r] == KEEP
++ * (line that has no match), but there are corner cases where
++ * the loop proceed all the way to the extremities by causing
++ * huge performance penalties in case of big files.
+ */
+ if (i - s > XDL_SIMSCAN_WINDOW)
+ s = i - XDL_SIMSCAN_WINDOW;
@@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
/*
* Scans the lines before 'i' to find a run of lines that either
- * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
- * Note that we always call this function with dis[i] > 1, so the
-+ * have no match (matches[j] == NONE) or have multiple matches (matches[j] == TOO_MANY).
-+ * Note that we always call this function with matches[i] == TOO_MANY, so the
- * current line (i) is already a multimatch line.
+- * current line (i) is already a multimatch line.
++ * have no match (action[j] == DISCARD) or have multiple matches
++ * (action[j] == INVESTIGATE). Note that we always call this
++ * function with action[i] == INVESTIGATE, so the current line
++ * (i) is already a multimatch line.
*/
for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
- if (!dis[i - r])
-+ if (matches[i - r] == NONE)
++ if (action[i - r] == DISCARD)
rdis0++;
- else if (dis[i - r] == 2)
-+ else if (matches[i - r] == TOO_MANY)
++ else if (action[i - r] == INVESTIGATE)
rpdis0++;
- else
-+ else if (matches[i - r] == SOME)
++ else if (action[i - r] == KEEP)
break;
+ else
-+ BUG("Illegal value for matches[i - r]");
++ BUG("Illegal value for action[i - r]");
}
/*
- * If the run before the line 'i' found only multimatch lines, we
+- * If the run before the line 'i' found only multimatch lines, we
- * return 0 and hence we don't make the current line (i) discarded.
-+ * return false and hence we don't make the current line (i) discarded.
- * We want to discard multimatch lines only when they appear in the
+- * We want to discard multimatch lines only when they appear in the
- * middle of runs with nomatch lines (dis[j] == 0).
-+ * middle of runs with nomatch lines (matches[j] == NONE).
++ * If the run before the line 'i' found only multimatch lines,
++ * we return false and hence we don't make the current line (i)
++ * discarded. We want to discard multimatch lines only when
++ * they appear in the middle of runs with nomatch lines
++ * (action[j] == DISCARD).
*/
if (rdis0 == 0)
return 0;
for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
- if (!dis[i + r])
-+ if (matches[i + r] == NONE)
++ if (action[i + r] == DISCARD)
rdis1++;
- else if (dis[i + r] == 2)
-+ else if (matches[i + r] == TOO_MANY)
++ else if (action[i + r] == INVESTIGATE)
rpdis1++;
- else
-+ else if (matches[i + r] == SOME)
++ else if (action[i + r] == KEEP)
break;
+ else
-+ BUG("Illegal value for matches[i + r]");
++ BUG("Illegal value for action[i + r]");
}
/*
- * If the run after the line 'i' found only multimatch lines, we
+- * If the run after the line 'i' found only multimatch lines, we
- * return 0 and hence we don't make the current line (i) discarded.
-+ * return false and hence we don't make the current line (i) discarded.
++ * If the run after the line 'i' found only multimatch lines,
++ * we return false and hence we don't make the current line (i)
++ * discarded.
*/
if (rdis1 == 0)
- return 0;
@@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, l
xdlclass_t *rcrec;
- char *dis, *dis1, *dis2;
- int need_min = !!(cf->flags & XDF_NEED_MINIMAL);
-+ uint8_t *matches1, *matches2;
-+ int status = 0;
++ uint8_t *action1 = NULL, *action2 = NULL;
+ bool need_min = !!(cf->flags & XDF_NEED_MINIMAL);
++ int ret = 0;
- if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
- return -1;
- dis1 = dis;
- dis2 = dis1 + xdf1->nrec + 1;
-+ matches1 = NULL;
-+ matches2 = NULL;
-+
+ /*
+ * Create temporary arrays that will help us decide if
+ * changed[i] should remain 0 or become 1.
+ */
-+ if (!XDL_CALLOC_ARRAY(matches1, xdf1->nrec + 1)) {
-+ status = -1;
++ if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {
++ ret = -1;
+ goto cleanup;
+ }
-+ if (!XDL_CALLOC_ARRAY(matches2, xdf2->nrec + 1)) {
-+ status = -1;
++ if (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {
++ ret = -1;
+ goto cleanup;
+ }
+ /*
-+ * Initialize temporary arrays with NONE, SOME, or TOO_MANY.
++ * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
+ */
if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
mlim = XDL_MAX_EQLIMIT;
@@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, l
rcrec = cf->rcrecs[recs->ha];
nm = rcrec ? rcrec->len2 : 0;
- dis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;
-+ matches1[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME;
++ action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
}
if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
rcrec = cf->rcrecs[recs->ha];
nm = rcrec ? rcrec->len1 : 0;
- dis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;
-+ matches2[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME;
++ action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
}
+ /*
@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
i <= xdf1->dend; i++, recs++) {
- if (dis1[i] == 1 ||
- (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) {
-+ if (matches1[i] == SOME ||
-+ (matches1[i] == TOO_MANY && !xdl_clean_mmatch(matches1, i, xdf1->dstart, xdf1->dend))) {
++ if (action1[i] == KEEP ||
++ (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
xdf1->rindex[nreff++] = i;
-+ /* changed[i] remains 0 */
++ /* changed[i] remains 0, i.e. keep */
} else
xdf1->changed[i] = 1;
++ /* i.e. discard */
}
-@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
+ xdf1->nreff = nreff;
for (nreff = 0, i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart];
i <= xdf2->dend; i++, recs++) {
- if (dis2[i] == 1 ||
- (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) {
-+ if (matches2[i] == SOME ||
-+ (matches2[i] == TOO_MANY && !xdl_clean_mmatch(matches2, i, xdf2->dstart, xdf2->dend))) {
++ if (action2[i] == KEEP ||
++ (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
xdf2->rindex[nreff++] = i;
-+ /* changed[i] remains 0 */
++ /* changed[i] remains 0, i.e. keep */
} else
xdf2->changed[i] = 1;
++ /* i.e. discard */
}
xdf2->nreff = nreff;
- xdl_free(dis);
+cleanup:
-+ xdl_free(matches1);
-+ xdl_free(matches2);
++ xdl_free(action1);
++ xdl_free(action2);
- return 0;
-+ return status;
++ return ret;
} 13: 975e845bfa ! 12: 83e1ace5bd xdiff: change type of xdfile_t.changed from char to bool
@@ Commit message
xdiff: change type of xdfile_t.changed from char to bool
The only values possible for 'changed' is 1 and 0, which exactly maps
- to a bool type. It might not look like this is the case because
- matches1 and matches2 (which use to be dis1, and dis2) were also char
- and were assigned numerical values within a few lines of 'changed'
- (what used to be rchg).
+ to a bool type. It might not look like this because action1 and action2
+ (which use to be dis1, and dis2) were also of type char and were
+ assigned numerical values within a few lines of 'changed' (what used to
+ be rchg).
- Using NONE, SOME, TOO_MANY for matches1[i]/matches2[j], and true/false
+ Using DISCARD/KEEP/INVESTIGATE for action1[i]/action2[j], and true/false
for changed[k] makes it clear to future readers that these are logically separate concepts.
@@ xdiff/xdiffi.c: static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g)
while (xdf->changed[g->start - 1])
g->start--;
+@@ xdiff/xdiffi.c: int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { +
+ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
+ xdchange_t *cscr = NULL, *xch;
+- char *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;
++ bool *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;
+ long i1, i2, l1, l2;
+
+ /*
## xdiff/xhistogram.c ##
@@ xdiff/xhistogram.c: redo:
@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
- * changed[i] should remain 0 or become 1.
+ * changed[i] should remain false, or become true.
*/
- if (!XDL_CALLOC_ARRAY(matches1, xdf1->nrec + 1)) {
- status = -1;
+ if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {
+ ret = -1;
@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
/*
@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
*/
for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
i <= xdf1->dend; i++, recs++) {
- if (matches1[i] == SOME ||
- (matches1[i] == TOO_MANY && !xdl_clean_mmatch(matches1, i, xdf1->dstart, xdf1->dend))) {
+ if (action1[i] == KEEP ||
+ (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
xdf1->rindex[nreff++] = i;
-- /* changed[i] remains 0 */
-+ /* changed[i] remains false */
+- /* changed[i] remains 0, i.e. keep */
++ /* changed[i] remains false, i.e. keep */
} else
- xdf1->changed[i] = 1;
+ xdf1->changed[i] = true;
+ /* i.e. discard */
}
xdf1->nreff = nreff;
-
@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
- if (matches2[i] == SOME ||
- (matches2[i] == TOO_MANY && !xdl_clean_mmatch(matches2, i, xdf2->dstart, xdf2->dend))) {
+ if (action2[i] == KEEP ||
+ (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
xdf2->rindex[nreff++] = i;
-- /* changed[i] remains 0 */
-+ /* changed[i] remains false */
+- /* changed[i] remains 0, i.e. keep */
++ /* changed[i] remains false, i.e. keep */
} else
- xdf2->changed[i] = 1;
+ xdf2->changed[i] = true;
+ /* i.e. discard */
}
xdf2->nreff = nreff;
-
## xdiff/xtypes.h ##
@@ xdiff/xtypes.h: typedef struct s_xdfile {
Signature · 1 line
gitgitgadget
PATCH v6 1/12 xdiff: delete static forward declarations in xprepare
From: Ezekiel Newren <[email protected]>
Move xdl_prepare_env() later in the file to avoid the need for static forward declarations.
Best-viewed-with: --color-moved
--- xdiff/xprepare.c | 116 ++++++++++++++++++++--------------------------- 1 file changed, 50 insertions(+), 66 deletions(-)
xdiff/xprepare.c +50 -66
@@ -53,21 +53,6 @@ typedef struct s_xdlclassifier { -static int xdl_init_classifier (xdlclassifier_t *cf,long size,long flags); -static void xdl_free_classifier (xdlclassifier_t *cf); -static int xdl_classify_record (unsigned int pass,xdlclassifier_t *cf,xrecord_t **rhash, -unsigned int hbits,xrecord_t *rec); -static int xdl_prepare_ctx (unsigned int pass,mmfile_t *mf,long narec,xpparam_t const *xpp, -xdlclassifier_t *cf,xdfile_t *xdf); -static void xdl_free_ctx (xdfile_t *xdf); -static int xdl_clean_mmatch (char const *dis,long i,long s,long e); -static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2); -static int xdl_trim_ends (xdfile_t *xdf1,xdfile_t *xdf2); -static int xdl_optimize_ctxs (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2); - - - -static int xdl_init_classifier (xdlclassifier_t *cf,long size,long flags) { cf->flags = flags;
@@ -242,57 +227,6 @@ static void xdl_free_ctx(xdfile_t *xdf) { } -int xdl_prepare_env (mmfile_t *mf1,mmfile_t *mf2,xpparam_t const *xpp, -xdfenv_t *xe) { -long enl1, enl2, sample; -xdlclassifier_t cf; - -memset (&cf,0 ,sizeof (cf)); - -/* -* For histogram diff, we can afford a smaller sample size and -* thus a poorer estimate of the number of lines, as the hash -* table (rhash) won't be filled up/grown. The number of lines -* (nrecs) will be updated correctly anyway by -* xdl_prepare_ctx(). -*/ - sample = (XDF_DIFF_ALG (xpp->flags) ==XDF_HISTOGRAM_DIFF - ?XDL_GUESS_NLINES2 :XDL_GUESS_NLINES1 ); - - enl1 =xdl_guess_lines (mf1, sample) +1 ; - enl2 =xdl_guess_lines (mf2, sample) +1 ; - -if (xdl_init_classifier (&cf, enl1 + enl2 +1 , xpp->flags) <0 ) -return -1 ; - -if (xdl_prepare_ctx (1 , mf1, enl1, xpp, &cf, &xe->xdf1) <0 ) { - -xdl_free_classifier (&cf); -return -1 ; - } -if (xdl_prepare_ctx (2 , mf2, enl2, xpp, &cf, &xe->xdf2) <0 ) { - -xdl_free_ctx (&xe->xdf1); -xdl_free_classifier (&cf); -return -1 ; - } - -if ((XDF_DIFF_ALG (xpp->flags) !=XDF_PATIENCE_DIFF ) && - (XDF_DIFF_ALG (xpp->flags) !=XDF_HISTOGRAM_DIFF ) && -xdl_optimize_ctxs (&cf, &xe->xdf1, &xe->xdf2) <0 ) { - -xdl_free_ctx (&xe->xdf2); -xdl_free_ctx (&xe->xdf1); -xdl_free_classifier (&cf); -return -1 ; - } - -xdl_free_classifier (&cf); - -return 0 ; -} - -void xdl_free_env (xdfenv_t *xe) {xdl_free_ctx (&xe->xdf2);
@@ -460,3 +394,53 @@ static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2return 0 ; } + +int xdl_prepare_env (mmfile_t *mf1,mmfile_t *mf2,xpparam_t const *xpp, +xdfenv_t *xe) { +long enl1, enl2, sample; +xdlclassifier_t cf; + +memset (&cf,0 ,sizeof (cf)); + +/* +* For histogram diff, we can afford a smaller sample size and +* thus a poorer estimate of the number of lines, as the hash +* table (rhash) won't be filled up/grown. The number of lines +* (nrecs) will be updated correctly anyway by +* xdl_prepare_ctx(). +*/ + sample = (XDF_DIFF_ALG (xpp->flags) ==XDF_HISTOGRAM_DIFF + ?XDL_GUESS_NLINES2 :XDL_GUESS_NLINES1 ); + + enl1 =xdl_guess_lines (mf1, sample) +1 ; + enl2 =xdl_guess_lines (mf2, sample) +1 ; + +if (xdl_init_classifier (&cf, enl1 + enl2 +1 , xpp->flags) <0 ) +return -1 ; + +if (xdl_prepare_ctx (1 , mf1, enl1, xpp, &cf, &xe->xdf1) <0 ) { + +xdl_free_classifier (&cf); +return -1 ; + } +if (xdl_prepare_ctx (2 , mf2, enl2, xpp, &cf, &xe->xdf2) <0 ) { + +xdl_free_ctx (&xe->xdf1); +xdl_free_classifier (&cf); +return -1 ; + } + +if ((XDF_DIFF_ALG (xpp->flags) !=XDF_PATIENCE_DIFF ) && + (XDF_DIFF_ALG (xpp->flags) !=XDF_HISTOGRAM_DIFF ) && +xdl_optimize_ctxs (&cf, &xe->xdf1, &xe->xdf2) <0 ) { + +xdl_free_ctx (&xe->xdf2); +xdl_free_ctx (&xe->xdf1); +xdl_free_classifier (&cf); +return -1 ; + } + +xdl_free_classifier (&cf); + +return 0 ; +}
Signature · 1 line
gitgitgadget
PATCH v6 2/12 xdiff: delete local variables and initialize/free xdfile_t directly
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
These local variables are essentially a hand-rolled additional implementation of xdl_free_ctx() inlined into xdl_prepare_ctx(). Modify the code to use the existing xdl_free_ctx() function so there aren't two ways to free such variables.
--- xdiff/xprepare.c | 78 +++++++++++++++++++----------------------------- 1 file changed, 30 insertions(+), 48 deletions(-)
xdiff/xprepare.c +30 -48
@@ -134,99 +134,81 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t } +static void xdl_free_ctx (xdfile_t *xdf) +{ +xdl_free (xdf->rhash); +xdl_free (xdf->rindex); +xdl_free (xdf->rchg -1 ); +xdl_free (xdf->ha); +xdl_free (xdf->recs); +xdl_cha_free (&xdf->rcha); +} + +static int xdl_prepare_ctx (unsigned int pass,mmfile_t *mf,long narec,xpparam_t const *xpp,xdlclassifier_t *cf,xdfile_t *xdf) { -unsigned int hbits; -long nrec, hsize, bsize; +long bsize;unsigned long hav;char const *blk, *cur, *top, *prev;xrecord_t *crec; -xrecord_t **recs; -xrecord_t **rhash; -unsigned long *ha; -char *rchg; -long *rindex; - ha =NULL ; - rindex =NULL ; - rchg =NULL ; - rhash =NULL ; - recs =NULL ; + xdf->ha =NULL ; + xdf->rindex =NULL ; + xdf->rchg =NULL ; + xdf->rhash =NULL ; + xdf->recs =NULL ;if (xdl_cha_init (&xdf->rcha,sizeof (xrecord_t), narec /4 +1 ) <0 ) goto abort; -if (!XDL_ALLOC_ARRAY (recs, narec)) +if (!XDL_ALLOC_ARRAY (xdf->recs, narec)) goto abort; - hbits =xdl_hashbits ((unsigned int ) narec); - hsize =1 << hbits; -if (!XDL_CALLOC_ARRAY (rhash, hsize)) + xdf->hbits =xdl_hashbits ((unsigned int ) narec); +if (!XDL_CALLOC_ARRAY (xdf->rhash,1 << xdf->hbits)) goto abort; - nrec =0 ; + xdf->nrec =0 ;if ((cur = blk =xdl_mmfile_first (mf, &bsize))) {for (top = blk + bsize; cur < top; ) { prev = cur; hav =xdl_hash_record (&cur, top, xpp->flags); -if (XDL_ALLOC_GROW (recs, nrec +1 , narec)) +if (XDL_ALLOC_GROW (xdf->recs, xdf->nrec +1 , narec)) goto abort;if (!(crec =xdl_cha_alloc (&xdf->rcha))) goto abort; crec->ptr = prev; crec->size = (long ) (cur - prev); crec->ha = hav; - recs[nrec++] = crec; -if (xdl_classify_record (pass, cf, rhash, hbits, crec) <0 ) + xdf->recs[xdf->nrec++] = crec; +if (xdl_classify_record (pass, cf, xdf->rhash, xdf->hbits, crec) <0 ) goto abort; } } -if (!XDL_CALLOC_ARRAY (rchg, nrec +2 )) +if (!XDL_CALLOC_ARRAY (xdf->rchg, xdf->nrec +2 )) goto abort;if ((XDF_DIFF_ALG (xpp->flags) !=XDF_PATIENCE_DIFF ) && (XDF_DIFF_ALG (xpp->flags) !=XDF_HISTOGRAM_DIFF )) { -if (!XDL_ALLOC_ARRAY (rindex, nrec +1 )) +if (!XDL_ALLOC_ARRAY (xdf->rindex, xdf->nrec +1 )) goto abort; -if (!XDL_ALLOC_ARRAY (ha, nrec +1 )) +if (!XDL_ALLOC_ARRAY (xdf->ha, xdf->nrec +1 )) goto abort; } - xdf->nrec = nrec; - xdf->recs = recs; - xdf->hbits = hbits; - xdf->rhash = rhash; - xdf->rchg = rchg +1 ; - xdf->rindex = rindex; + xdf->rchg +=1 ; xdf->nreff =0 ; - xdf->ha = ha; xdf->dstart =0 ; - xdf->dend = nrec -1 ; + xdf->dend = xdf->nrec -1 ;return 0 ; abort: -xdl_free (ha); -xdl_free (rindex); -xdl_free (rchg); -xdl_free (rhash); -xdl_free (recs); -xdl_cha_free (&xdf->rcha); +xdl_free_ctx (xdf);return -1 ; } -static void xdl_free_ctx (xdfile_t *xdf) { - -xdl_free (xdf->rhash); -xdl_free (xdf->rindex); -xdl_free (xdf->rchg -1 ); -xdl_free (xdf->ha); -xdl_free (xdf->recs); -xdl_cha_free (&xdf->rcha); -} - -void xdl_free_env (xdfenv_t *xe) {xdl_free_ctx (&xe->xdf2);
Signature · 1 line
gitgitgadget
PATCH v6 3/12 xdiff: delete unnecessary fields from xrecord_t and xdfile_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
xrecord_t.next, xdfile_t.hbits, xdfile_t.rhash are initialized, but never used for anything by the code. Remove them.
Best-viewed-with: --color-words
--- xdiff/xprepare.c | 15 ++------------- xdiff/xtypes.h | 3 --- 2 files changed, 2 insertions(+), 16 deletions(-)
xdiff/xprepare.c +2 -13
@@ -91,8 +91,7 @@ static void xdl_free_classifier(xdlclassifier_t *cf) { } -static int xdl_classify_record (unsigned int pass,xdlclassifier_t *cf,xrecord_t **rhash, -unsigned int hbits,xrecord_t *rec) { +static int xdl_classify_record (unsigned int pass,xdlclassifier_t *cf,xrecord_t *rec) {long hi;char const *line;xdlclass_t *rcrec;
@@ -126,17 +125,12 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t rec->ha = (unsigned long ) rcrec->idx; - hi = (long )XDL_HASHLONG (rec->ha, hbits); - rec->next = rhash[hi]; - rhash[hi] = rec; -return 0 ; }static void xdl_free_ctx (xdfile_t *xdf) { -xdl_free (xdf->rhash);xdl_free (xdf->rindex);xdl_free (xdf->rchg -1 );xdl_free (xdf->ha);
@@ -155,7 +149,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ xdf->ha =NULL ; xdf->rindex =NULL ; xdf->rchg =NULL ; - xdf->rhash =NULL ; xdf->recs =NULL ;if (xdl_cha_init (&xdf->rcha,sizeof (xrecord_t), narec /4 +1 ) <0 )
@@ -163,10 +156,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_if (!XDL_ALLOC_ARRAY (xdf->recs, narec)) goto abort; - xdf->hbits =xdl_hashbits ((unsigned int ) narec); -if (!XDL_CALLOC_ARRAY (xdf->rhash,1 << xdf->hbits)) - goto abort; - xdf->nrec =0 ;if ((cur = blk =xdl_mmfile_first (mf, &bsize))) {for (top = blk + bsize; cur < top; ) {
@@ -180,7 +169,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ crec->size = (long ) (cur - prev); crec->ha = hav; xdf->recs[xdf->nrec++] = crec; -if (xdl_classify_record (pass, cf, xdf->rhash, xdf->hbits, crec) <0 ) +if (xdl_classify_record (pass, cf, crec) <0 ) goto abort; } }
xdiff/xtypes.h +0 -3
@@ -39,7 +39,6 @@ typedef struct s_chastore { } chastore_t; typedef struct s_xrecord { - struct s_xrecord *next; char const *ptr; long size; unsigned long ha;
@@ -48,8 +47,6 @@ typedef struct s_xrecord { typedef struct s_xdfile { chastore_t rcha; long nrec; - unsigned int hbits; - xrecord_t **rhash; long dstart, dend; xrecord_t **recs; char *rchg;
Signature · 1 line
gitgitgadget
PATCH v6 4/12 xdiff: delete superfluous function xdl_get_rec() in xemit
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
When xrecord_t was a linked list, and recs didn't exist, I assume this function walked the list until it found the right record. Accessing a contiguous array is so trival that this function is now superfluous. Delete it.
--- xdiff/xemit.c | 23 +++++++---------------- 1 file changed, 7 insertions(+), 16 deletions(-)
xdiff/xemit.c +7 -16
@@ -22,23 +22,14 @@#include "xinclude.h" -static long xdl_get_rec (xdfile_t *xdf,long ri,char const **rec) { - - *rec = xdf->recs[ri]->ptr; - -return xdf->recs[ri]->size; -} -static int xdl_emit_record (xdfile_t *xdf,long ri,char const *pre,xdemitcb_t *ecb) {long size, psize =strlen (pre); -char const *rec; - - size =xdl_get_rec (xdf, ri, &rec); -if (xdl_emit_diffrec (rec, size, pre, psize, ecb) <0 ) { +char const *rec = xdf->recs[ri]->ptr; + size = xdf->recs[ri]->size; +if (xdl_emit_diffrec (rec, size, pre, psize, ecb) <0 )return -1 ; - }return 0 ; }
@@ -120,8 +111,8 @@ static long def_ff(const char *rec, long len, char *buf, long sz)static long match_func_rec (xdfile_t *xdf,xdemitconf_t const *xecfg,long ri,char *buf,long sz) { -const char *rec; -long len =xdl_get_rec (xdf, ri, &rec); +const char *rec = xdf->recs[ri]->ptr; +long len = xdf->recs[ri]->size;if (!xecfg->find_func)return def_ff (rec, len, buf, sz);return xecfg->find_func (rec, len, buf, sz, xecfg->find_func_priv);
@@ -160,8 +151,8 @@ static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg,static int is_empty_rec (xdfile_t *xdf,long ri) { -const char *rec; -long len =xdl_get_rec (xdf, ri, &rec); +const char *rec = xdf->recs[ri]->ptr; +long len = xdf->recs[ri]->size;while (len >0 &&XDL_ISSPACE (*rec)) { rec++;
Signature · 1 line
gitgitgadget
PATCH v6 5/12 xdiff: delete local variables that alias fields in xrecord_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
Use the type xrecord_t as the local variable for the functions in the file xdiff/xemit.c. Most places directly reference the fields inside of this struct, doing that here makes it more consistent with the rest of the code.
--- xdiff/xemit.c | 29 +++++++++++++---------------- 1 file changed, 13 insertions(+), 16 deletions(-)
xdiff/xemit.c +13 -16
@@ -23,12 +23,11 @@#include "xinclude.h" -static int xdl_emit_record (xdfile_t *xdf,long ri,char const *pre,xdemitcb_t *ecb) { -long size, psize =strlen (pre); -char const *rec = xdf->recs[ri]->ptr; +static int xdl_emit_record (xdfile_t *xdf,long ri,char const *pre,xdemitcb_t *ecb) +{ +xrecord_t *rec = xdf->recs[ri]; - size = xdf->recs[ri]->size; -if (xdl_emit_diffrec (rec, size, pre, psize, ecb) <0 ) +if (xdl_emit_diffrec (rec->ptr, rec->size, pre,strlen (pre), ecb) <0 )return -1 ;return 0 ;
@@ -111,11 +110,11 @@ static long def_ff(const char *rec, long len, char *buf, long sz)static long match_func_rec (xdfile_t *xdf,xdemitconf_t const *xecfg,long ri,char *buf,long sz) { -const char *rec = xdf->recs[ri]->ptr; -long len = xdf->recs[ri]->size; +xrecord_t *rec = xdf->recs[ri]; +if (!xecfg->find_func) -return def_ff (rec, len, buf, sz); -return xecfg->find_func (rec, len, buf, sz, xecfg->find_func_priv); +return def_ff (rec->ptr, rec->size, buf, sz); +return xecfg->find_func (rec->ptr, rec->size, buf, sz, xecfg->find_func_priv); }static int is_func_rec (xdfile_t *xdf,xdemitconf_t const *xecfg,long ri)
@@ -151,14 +150,12 @@ static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg,static int is_empty_rec (xdfile_t *xdf,long ri) { -const char *rec = xdf->recs[ri]->ptr; -long len = xdf->recs[ri]->size; +xrecord_t *rec = xdf->recs[ri]; +long i =0 ; -while (len >0 &&XDL_ISSPACE (*rec)) { - rec++; - len--; - } -return !len; +for (; i < rec->size &&XDL_ISSPACE (rec->ptr[i]); i++); + +return i == rec->size; } int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
Signature · 1 line
gitgitgadget
PATCH v6 6/12 xdiff: delete struct diffdata_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
Every field in this struct is an alias for a certain field in xdfile_t.
diffdata_t.nrec -> xdfile_t.nreff
diffdata_t.ha -> xdfile_t.ha
diffdata_t.rindex -> xdfile_t.rindex
diffdata_t.rchg -> xdfile_t.rchg
I think this struct existed before xdfile_t, and was kept for backward compatibility reasons. I think xdiffi should have been refactored to use the new (xdfile_t) struct, but was easier to alias it instead.
The local variables rchg* and rindex* don't shorten the lines by much, nor do they really need to be there to make the code more readable. Delete them.
--- xdiff/xdiffi.c | 32 ++++++++------------------------ xdiff/xdiffi.h | 11 ++--------- 2 files changed, 10 insertions(+), 33 deletions(-)
xdiff/xdiffi.c +8 -24
@@ -257,10 +257,10 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,* sub-boxes by calling the box splitting function. Note that the real job * (marking changed lines) is done in the two boundary reaching checks. */ -int xdl_recs_cmp (diffdata_t *dd1,long off1,long lim1, -diffdata_t *dd2,long off2,long lim2, +int xdl_recs_cmp (xdfile_t *xdf1,long off1,long lim1, +xdfile_t *xdf2,long off2,long lim2,long *kvdf,long *kvdb,int need_min,xdalgoenv_t *xenv) { -unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha; +unsigned long const *ha1 = xdf1->ha, *ha2 = xdf2->ha;/* * Shrink the box by walking through each diagonal snake (SW and NE).
@@ -273,17 +273,11 @@ int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,* be obviously changed. */ if (off1 == lim1) { -char *rchg2 = dd2->rchg; -long *rindex2 = dd2->rindex; -for (; off2 < lim2; off2++) - rchg2[rindex2[off2]] =1 ; + xdf2->rchg[xdf2->rindex[off2]] =1 ; }else if (off2 == lim2) { -char *rchg1 = dd1->rchg; -long *rindex1 = dd1->rindex; -for (; off1 < lim1; off1++) - rchg1[rindex1[off1]] =1 ; + xdf1->rchg[xdf1->rindex[off1]] =1 ; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;
@@ -300,9 +294,9 @@ int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,/* * ... et Impera. */ -if (xdl_recs_cmp (dd1, off1, spl.i1, dd2, off2, spl.i2, +if (xdl_recs_cmp (xdf1, off1, spl.i1, xdf2, off2, spl.i2, kvdf, kvdb, spl.min_lo, xenv) <0 || -xdl_recs_cmp (dd1, spl.i1, lim1, dd2, spl.i2, lim2, +xdl_recs_cmp (xdf1, spl.i1, lim1, xdf2, spl.i2, lim2, kvdf, kvdb, spl.min_hi, xenv) <0 ) {return -1 ;
@@ -318,7 +312,6 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,long ndiags;long *kvd, *kvdf, *kvdb;xdalgoenv_t xenv; -diffdata_t dd1, dd2;int res;if (xdl_prepare_env (mf1, mf2, xpp, xe) <0 )
@@ -357,16 +350,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xenv.snake_cnt =XDL_SNAKE_CNT ; xenv.heur_min =XDL_HEUR_MIN_COST ; - dd1.nrec = xe->xdf1.nreff; - dd1.ha = xe->xdf1.ha; - dd1.rchg = xe->xdf1.rchg; - dd1.rindex = xe->xdf1.rindex; - dd2.nrec = xe->xdf2.nreff; - dd2.ha = xe->xdf2.ha; - dd2.rchg = xe->xdf2.rchg; - dd2.rindex = xe->xdf2.rindex; - - res =xdl_recs_cmp (&dd1,0 , dd1.nrec, &dd2,0 , dd2.nrec, + res =xdl_recs_cmp (&xe->xdf1,0 , xe->xdf1.nreff, &xe->xdf2,0 , xe->xdf2.nreff, kvdf, kvdb, (xpp->flags &XDF_NEED_MINIMAL ) !=0 , &xenv);xdl_free (kvd);
xdiff/xdiffi.h +2 -9
@@ -24,13 +24,6 @@#define XDIFFI_H -typedef struct s_diffdata { -long nrec; -unsigned long const *ha; -long *rindex; -char *rchg; -}diffdata_t ; - typedef struct s_xdalgoenv { long mxcost; long snake_cnt;
@@ -46,8 +39,8 @@ typedef struct s_xdchange { -int xdl_recs_cmp (diffdata_t *dd1,long off1,long lim1, -diffdata_t *dd2,long off2,long lim2, +int xdl_recs_cmp (xdfile_t *xdf1,long off1,long lim1, +xdfile_t *xdf2,long off2,long lim2,long *kvdf,long *kvdb,int need_min,xdalgoenv_t *xenv);int xdl_do_diff (mmfile_t *mf1,mmfile_t *mf2,xpparam_t const *xpp,xdfenv_t *xe);
Signature · 1 line
gitgitgadget
PATCH v6 7/12 xdiff: delete redundant array xdfile_t.ha
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
When 0 <= i < xdfile_t.nreff the following is true:
xdfile_t.ha[i] == xdfile_t.recs[xdfile_t.rindex[i]]
This makes the code about 5% slower. The fields rindex and ha are specific to the classic diff (myers and minimal). I plan on creating a struct for classic diff, but there's a lot of cleanup that needs to be done before that can happen and leaving ha in would make those cleanups harder to follow.
A subsequent commit will delete the chastore cha from xdfile_t. That later commit will investigate deleting ha and cha independently and together.
--- xdiff/xdiffi.c | 24 ++++++++++++++---------- xdiff/xprepare.c | 12 ++---------- xdiff/xtypes.h | 1 - 3 files changed, 16 insertions(+), 21 deletions(-)
xdiff/xdiffi.c +14 -10
@@ -22,6 +22,11 @@#include "xinclude.h" +static unsigned long get_hash (xdfile_t *xdf,long index) +{ +return xdf->recs[xdf->rindex[index]]->ha; +} +#define XDL_MAX_COST_MIN 256#define XDL_HEUR_MIN_COST 256#define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1)
@@ -42,8 +47,8 @@ typedef struct s_xdpsplit {* using this algorithm, so a little bit of heuristic is needed to cut the * search and to return a suboptimal point. */ -static long xdl_split (unsigned long const *ha1,long off1,long lim1, -unsigned long const *ha2,long off2,long lim2, +static long xdl_split (xdfile_t *xdf1,long off1,long lim1, +xdfile_t *xdf2,long off2,long lim2,long *kvdf,long *kvdb,int need_min,xdpsplit_t *spl,xdalgoenv_t *xenv) {long dmin = off1 - lim2, dmax = lim1 - off2;
@@ -87,7 +92,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1, i1 = kvdf[d +1 ]; prev1 = i1; i2 = i1 - d; -for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++); +for (; i1 < lim1 && i2 < lim2 &&get_hash (xdf1, i1) ==get_hash (xdf2, i2); i1++, i2++);if (i1 - prev1 > xenv->snake_cnt) got_snake =1 ; kvdf[d] = i1;
@@ -124,7 +129,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1, i1 = kvdb[d +1 ] -1 ; prev1 = i1; i2 = i1 - d; -for (; i1 > off1 && i2 > off2 && ha1[i1 -1 ] == ha2[i2 -1 ]; i1--, i2--); +for (; i1 > off1 && i2 > off2 &&get_hash (xdf1, i1 -1 ) ==get_hash (xdf2, i2 -1 ); i1--, i2--);if (prev1 - i1 > xenv->snake_cnt) got_snake =1 ; kvdb[d] = i1;
@@ -159,7 +164,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,if (v >XDL_K_HEUR * ec && v > best && off1 + xenv->snake_cnt <= i1 && i1 < lim1 && off2 + xenv->snake_cnt <= i2 && i2 < lim2) { -for (k =1 ; ha1[i1 - k] == ha2[i2 - k]; k++) +for (k =1 ;get_hash (xdf1, i1 - k) ==get_hash (xdf2, i2 - k); k++)if (k == xenv->snake_cnt) { best = v; spl->i1 = i1;
@@ -183,7 +188,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,if (v >XDL_K_HEUR * ec && v > best && off1 < i1 && i1 <= lim1 - xenv->snake_cnt && off2 < i2 && i2 <= lim2 - xenv->snake_cnt) { -for (k =0 ; ha1[i1 + k] == ha2[i2 + k]; k++) +for (k =0 ;get_hash (xdf1, i1 + k) ==get_hash (xdf2, i2 + k); k++)if (k == xenv->snake_cnt -1 ) { best = v; spl->i1 = i1;
@@ -260,13 +265,12 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,int xdl_recs_cmp (xdfile_t *xdf1,long off1,long lim1,xdfile_t *xdf2,long off2,long lim2,long *kvdf,long *kvdb,int need_min,xdalgoenv_t *xenv) { -unsigned long const *ha1 = xdf1->ha, *ha2 = xdf2->ha;/* * Shrink the box by walking through each diagonal snake (SW and NE). */ -for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++); -for (; off1 < lim1 && off2 < lim2 && ha1[lim1 -1 ] == ha2[lim2 -1 ]; lim1--, lim2--); +for (; off1 < lim1 && off2 < lim2 &&get_hash (xdf1, off1) ==get_hash (xdf2, off2); off1++, off2++); +for (; off1 < lim1 && off2 < lim2 &&get_hash (xdf1, lim1 -1 ) ==get_hash (xdf2, lim2 -1 ); lim1--, lim2--);/* * If one dimension is empty, then all records on the other one must
@@ -285,7 +289,7 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,/* * Divide ... */ -if (xdl_split (ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb, +if (xdl_split (xdf1, off1, lim1, xdf2, off2, lim2, kvdf, kvdb, need_min, &spl, xenv) <0 ) {return -1 ;
xdiff/xprepare.c +2 -10
@@ -133,7 +133,6 @@ static void xdl_free_ctx(xdfile_t *xdf) {xdl_free (xdf->rindex);xdl_free (xdf->rchg -1 ); -xdl_free (xdf->ha);xdl_free (xdf->recs);xdl_cha_free (&xdf->rcha); }
@@ -146,7 +145,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_char const *blk, *cur, *top, *prev;xrecord_t *crec; - xdf->ha =NULL ; xdf->rindex =NULL ; xdf->rchg =NULL ; xdf->recs =NULL ;
@@ -181,8 +179,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {if (!XDL_ALLOC_ARRAY (xdf->rindex, xdf->nrec +1 )) goto abort; -if (!XDL_ALLOC_ARRAY (xdf->ha, xdf->nrec +1 )) - goto abort; } xdf->rchg +=1 ;
@@ -300,9 +296,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd i <= xdf1->dend; i++, recs++) {if (dis1[i] ==1 || (dis1[i] ==2 && !xdl_clean_mmatch (dis1, i, xdf1->dstart, xdf1->dend))) { - xdf1->rindex[nreff] = i; - xdf1->ha[nreff] = (*recs)->ha; - nreff++; + xdf1->rindex[nreff++] = i; }else xdf1->rchg[i] =1 ; }
@@ -312,9 +306,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd i <= xdf2->dend; i++, recs++) {if (dis2[i] ==1 || (dis2[i] ==2 && !xdl_clean_mmatch (dis2, i, xdf2->dstart, xdf2->dend))) { - xdf2->rindex[nreff] = i; - xdf2->ha[nreff] = (*recs)->ha; - nreff++; + xdf2->rindex[nreff++] = i; }else xdf2->rchg[i] =1 ; }
xdiff/xtypes.h +0 -1
@@ -52,7 +52,6 @@ typedef struct s_xdfile {char *rchg;long *rindex;long nreff; -unsigned long *ha; } xdfile_t; typedef struct s_xdfenv {
Signature · 1 line
gitgitgadget
PATCH v6 8/12 xdiff: delete fields ha, line, size in xdlclass_t in favor of an xrecord_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
The fields from xdlclass_t are aliases of xrecord_t:
xdlclass_t.line -> xrecord_t.ptr xdlclass_t.size -> xrecord_t.size
xdlclass_t.ha -> xrecord_t.ha
xdlclass_t carries a copy of the data in xrecord_t, but instead of embedding xrecord_t it duplicates the individual fields. A future commit will change the types used in xrecord_t so embed it in xdlclass_t first, so we don't have to remember to change the types here as well.
Best-viewed-with: --color-words
--- xdiff/xprepare.c | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-)
xdiff/xprepare.c +4 -10
@@ -32,9 +32,7 @@typedef struct s_xdlclass {struct s_xdlclass *next; -unsigned long ha; -char const *line; -long size; +xrecord_t rec;long idx;long len1, len2; }xdlclass_t ;
@@ -93,14 +91,12 @@ static void xdl_free_classifier(xdlclassifier_t *cf) {static int xdl_classify_record (unsigned int pass,xdlclassifier_t *cf,xrecord_t *rec) {long hi; -char const *line;xdlclass_t *rcrec; - line = rec->ptr; hi = (long )XDL_HASHLONG (rec->ha, cf->hbits);for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next) -if (rcrec->ha == rec->ha && -xdl_recmatch (rcrec->line, rcrec->size, +if (rcrec->rec.ha == rec->ha && +xdl_recmatch (rcrec->rec.ptr, rcrec->rec.size, rec->ptr, rec->size, cf->flags))break ;
@@ -113,9 +109,7 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_tif (XDL_ALLOC_GROW (cf->rcrecs, cf->count, cf->alloc))return -1 ; cf->rcrecs[rcrec->idx] = rcrec; - rcrec->line = line; - rcrec->size = rec->size; - rcrec->ha = rec->ha; + rcrec->rec = *rec; rcrec->len1 = rcrec->len2 =0 ; rcrec->next = cf->rchash[hi]; cf->rchash[hi] = rcrec;
Signature · 1 line
gitgitgadget
PATCH v6 9/12 xdiff: delete chastore from xdfile_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
xdfile_t currently uses chastore_t which is an arena allocator. I think that xrecord_t used to be a linked list and recs didn't exist originally. When recs was added I think they forgot to remove xdfile_t.next, but was overlooked. This dual data structure setup makes the code somewhat confusing.
Additionally the C type chastore_t isn't FFI friendly, and provides little to no performance benefit over using realloc to grow an array.
Performance impact of deleting fields from xdfile_t:
Deleting ha is about 5% slower.
Deleting cha is about 5% faster.
Delete ha, but keep cha
time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_ha/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.269 s ± 0.017 s [User: 1.135 s, System: 0.128 s]
Range (min … max): 1.249 s … 1.286 s 10 runs Benchmark 2: build_delete_ha/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.339 s ± 0.017 s [User: 1.234 s, System: 0.099 s]
Range (min … max): 1.320 s … 1.358 s 10 runs
Summary
build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran
1.06 ± 0.02 times faster than build_delete_ha/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/nullDelete cha, but keep ha
time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_chastore/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.290 s ± 0.001 s [User: 1.154 s, System: 0.130 s]
Range (min … max): 1.288 s … 1.292 s 10 runs Benchmark 2: build_delete_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.232 s ± 0.017 s [User: 1.105 s, System: 0.121 s]
Range (min … max): 1.205 s … 1.249 s 10 runs
Summary
build_delete_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran
1.05 ± 0.01 times faster than build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/nullDelete ha AND chastore
time hyperfine --warmup 3 -L exe build_v2.51.0/git,build_delete_ha_and_chastore/git '{exe} log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null' Benchmark 1: build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.291 s ± 0.002 s [User: 1.156 s, System: 0.129 s]
Range (min … max): 1.287 s … 1.295 s 10 runs Benchmark 2: build_delete_ha_and_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null
Time (mean ± σ): 1.306 s ± 0.001 s [User: 1.195 s, System: 0.105 s]
Range (min … max): 1.305 s … 1.308 s 10 runs
Summary
build_v2.51.0/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/null ran
1.01 ± 0.00 times faster than build_delete_ha_and_chastore/git log --oneline --shortstat --diff-algorithm=myers -3000 v2.39.1 >/dev/nullBest-viewed-with: --color-words
--- xdiff/xdiffi.c | 24 ++++++++++---------- xdiff/xemit.c | 6 ++--- xdiff/xhistogram.c | 2 +- xdiff/xmerge.c | 56 +++++++++++++++++++++++----------------------- xdiff/xpatience.c | 10 ++++----- xdiff/xprepare.c | 19 ++++++---------- xdiff/xtypes.h | 3 +-- xdiff/xutils.c | 12 +++++----- 8 files changed, 63 insertions(+), 69 deletions(-)
xdiff/xdiffi.c +12 -12
@@ -24,7 +24,7 @@static unsigned long get_hash (xdfile_t *xdf,long index) { -return xdf->recs[xdf->rindex[index]]->ha; +return xdf->recs[xdf->rindex[index]].ha; }#define XDL_MAX_COST_MIN 256
@@ -489,13 +489,13 @@ static void measure_split(const xdfile_t *xdf, long split, m->indent =-1 ; }else { m->end_of_file =0 ; - m->indent =get_indent (xdf->recs[split]); + m->indent =get_indent (&xdf->recs[split]); } m->pre_blank =0 ; m->pre_indent =-1 ;for (i = split -1 ; i >=0 ; i--) { - m->pre_indent =get_indent (xdf->recs[i]); + m->pre_indent =get_indent (&xdf->recs[i]);if (m->pre_indent !=-1 )break ; m->pre_blank +=1 ;
@@ -508,7 +508,7 @@ static void measure_split(const xdfile_t *xdf, long split, m->post_blank =0 ; m->post_indent =-1 ;for (i = split +1 ; i < xdf->nrec; i++) { - m->post_indent =get_indent (xdf->recs[i]); + m->post_indent =get_indent (&xdf->recs[i]);if (m->post_indent !=-1 )break ; m->post_blank +=1 ;
@@ -752,7 +752,7 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)static int group_slide_down (xdfile_t *xdf,struct xdlgroup *g) {if (g->end < xdf->nrec && -recs_match (xdf->recs[g->start], xdf->recs[g->end])) { +recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { xdf->rchg[g->start++] =0 ; xdf->rchg[g->end++] =1 ;
@@ -773,7 +773,7 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g)static int group_slide_up (xdfile_t *xdf,struct xdlgroup *g) {if (g->start >0 && -recs_match (xdf->recs[g->start -1 ], xdf->recs[g->end -1 ])) { +recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { xdf->rchg[--g->start] =1 ; xdf->rchg[--g->end] =0 ;
@@ -988,16 +988,16 @@ static void xdl_mark_ignorable_lines(xdchange_t *xscr, xdfenv_t *xe, long flags)for (xch = xscr; xch; xch = xch->next) {int ignore =1 ; -xrecord_t **rec; +xrecord_t *rec;long i; rec = &xe->xdf1.recs[xch->i1];for (i =0 ; i < xch->chg1 && ignore; i++) - ignore =xdl_blankline (rec[i]->ptr, rec[i]->size, flags); + ignore =xdl_blankline (rec[i].ptr, rec[i].size, flags); rec = &xe->xdf2.recs[xch->i2];for (i =0 ; i < xch->chg2 && ignore; i++) - ignore =xdl_blankline (rec[i]->ptr, rec[i]->size, flags); + ignore =xdl_blankline (rec[i].ptr, rec[i].size, flags); xch->ignore = ignore; }
@@ -1021,7 +1021,7 @@ static void xdl_mark_ignorable_regex(xdchange_t *xscr, const xdfenv_t *xe,xdchange_t *xch;for (xch = xscr; xch; xch = xch->next) { -xrecord_t **rec; +xrecord_t *rec;int ignore =1 ;long i;
@@ -1033,11 +1033,11 @@ static void xdl_mark_ignorable_regex(xdchange_t *xscr, const xdfenv_t *xe, rec = &xe->xdf1.recs[xch->i1];for (i =0 ; i < xch->chg1 && ignore; i++) - ignore =record_matches_regex (rec[i], xpp); + ignore =record_matches_regex (&rec[i], xpp); rec = &xe->xdf2.recs[xch->i2];for (i =0 ; i < xch->chg2 && ignore; i++) - ignore =record_matches_regex (rec[i], xpp); + ignore =record_matches_regex (&rec[i], xpp); xch->ignore = ignore; }
xdiff/xemit.c +3 -3
@@ -25,7 +25,7 @@static int xdl_emit_record (xdfile_t *xdf,long ri,char const *pre,xdemitcb_t *ecb) { -xrecord_t *rec = xdf->recs[ri]; +xrecord_t *rec = &xdf->recs[ri];if (xdl_emit_diffrec (rec->ptr, rec->size, pre,strlen (pre), ecb) <0 )return -1 ;
@@ -110,7 +110,7 @@ static long def_ff(const char *rec, long len, char *buf, long sz)static long match_func_rec (xdfile_t *xdf,xdemitconf_t const *xecfg,long ri,char *buf,long sz) { -xrecord_t *rec = xdf->recs[ri]; +xrecord_t *rec = &xdf->recs[ri];if (!xecfg->find_func)return def_ff (rec->ptr, rec->size, buf, sz);
@@ -150,7 +150,7 @@ static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg,static int is_empty_rec (xdfile_t *xdf,long ri) { -xrecord_t *rec = xdf->recs[ri]; +xrecord_t *rec = &xdf->recs[ri];long i =0 ;for (; i < rec->size &&XDL_ISSPACE (rec->ptr[i]); i++);
xdiff/xhistogram.c +1 -1
@@ -86,7 +86,7 @@ struct region { ((LINE_MAP(index, ptr))->cnt)#define REC (env, s, l) \ - (env->xdf##s.recs[l - 1]) + (&env->xdf##s.recs[l - 1])static int cmp_recs (xrecord_t *r1,xrecord_t *r2) {
xdiff/xmerge.c +28 -28
123 lines not on this page · raw message
xdiff/xpatience.c +5 -5
@@ -88,9 +88,9 @@ static int is_anchor(xpparam_t const *xpp, const char *line)static void insert_record (xpparam_t const *xpp,int line,struct hashmap *map,int pass) { -xrecord_t **records = pass ==1 ? +xrecord_t *records = pass ==1 ? map->env->xdf1.recs : map->env->xdf2.recs; -xrecord_t *record = records[line -1 ]; +xrecord_t *record = &records[line -1 ];/* * After xdl_prepare_env() (or more precisely, due to * xdl_classify_record()), the "ha" member of the records (AKA lines)
@@ -121,7 +121,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,return ; map->entries[index].line1 = line; map->entries[index].hash = record->ha; - map->entries[index].anchor =is_anchor (xpp, map->env->xdf1.recs[line -1 ]->ptr); + map->entries[index].anchor =is_anchor (xpp, map->env->xdf1.recs[line -1 ].ptr);if (!map->first) map->first = map->entries + index;if (map->last) {
@@ -246,8 +246,8 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)static int match (struct hashmap *map,int line1,int line2) { -xrecord_t *record1 = map->env->xdf1.recs[line1 -1 ]; -xrecord_t *record2 = map->env->xdf2.recs[line2 -1 ]; +xrecord_t *record1 = &map->env->xdf1.recs[line1 -1 ]; +xrecord_t *record2 = &map->env->xdf2.recs[line2 -1 ];return record1->ha == record2->ha; }
xdiff/xprepare.c +7 -12
@@ -128,7 +128,6 @@ static void xdl_free_ctx(xdfile_t *xdf)xdl_free (xdf->rindex);xdl_free (xdf->rchg -1 );xdl_free (xdf->recs); -xdl_cha_free (&xdf->rcha); }
@@ -143,8 +142,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ xdf->rchg =NULL ; xdf->recs =NULL ; -if (xdl_cha_init (&xdf->rcha,sizeof (xrecord_t), narec /4 +1 ) <0 ) - goto abort;if (!XDL_ALLOC_ARRAY (xdf->recs, narec)) goto abort;
@@ -155,12 +152,10 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ hav =xdl_hash_record (&cur, top, xpp->flags);if (XDL_ALLOC_GROW (xdf->recs, xdf->nrec +1 , narec)) goto abort; -if (!(crec =xdl_cha_alloc (&xdf->rcha))) - goto abort; + crec = &xdf->recs[xdf->nrec++]; crec->ptr = prev; crec->size = (long ) (cur - prev); crec->ha = hav; - xdf->recs[xdf->nrec++] = crec;if (xdl_classify_record (pass, cf, crec) <0 ) goto abort; }
@@ -260,7 +255,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {*/ static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2) {long i, nm, nreff, mlim; -xrecord_t **recs; +xrecord_t *recs;xdlclass_t *rcrec;char *dis, *dis1, *dis2;int need_min = !!(cf->flags &XDF_NEED_MINIMAL );
@@ -273,7 +268,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif ((mlim =xdl_bogosqrt (xdf1->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { - rcrec = cf->rcrecs[(*recs)->ha]; + rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len2 :0 ; dis1[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; }
@@ -281,7 +276,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif ((mlim =xdl_bogosqrt (xdf2->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { - rcrec = cf->rcrecs[(*recs)->ha]; + rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len1 :0 ; dis2[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; }
@@ -317,13 +312,13 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd*/ static int xdl_trim_ends (xdfile_t *xdf1,xdfile_t *xdf2) {long i, lim; -xrecord_t **recs1, **recs2; +xrecord_t *recs1, *recs2; recs1 = xdf1->recs; recs2 = xdf2->recs;for (i =0 , lim =XDL_MIN (xdf1->nrec, xdf2->nrec); i < lim; i++, recs1++, recs2++) -if ((*recs1)->ha != (*recs2)->ha) +if (recs1->ha != recs2->ha)break ; xdf1->dstart = xdf2->dstart = i;
@@ -331,7 +326,7 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) { recs1 = xdf1->recs + xdf1->nrec -1 ; recs2 = xdf2->recs + xdf2->nrec -1 ;for (lim -= i, i =0 ; i < lim; i++, recs1--, recs2--) -if ((*recs1)->ha != (*recs2)->ha) +if (recs1->ha != recs2->ha)break ; xdf1->dend = xdf1->nrec - i -1 ;
xdiff/xtypes.h +1 -2
@@ -45,10 +45,9 @@ typedef struct s_xrecord { } xrecord_t; typedef struct s_xdfile { - chastore_t rcha; + xrecord_t *recs; long nrec; long dstart, dend; - xrecord_t **recs; char *rchg; long *rindex; long nreff;
xdiff/xutils.c +6 -6
@@ -416,12 +416,12 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,mmfile_t subfile1, subfile2;xdfenv_t env; - subfile1.ptr = (char *)diff_env->xdf1.recs[line1 -1 ]->ptr; - subfile1.size = diff_env->xdf1.recs[line1 + count1 -2 ]->ptr + - diff_env->xdf1.recs[line1 + count1 -2 ]->size - subfile1.ptr; - subfile2.ptr = (char *)diff_env->xdf2.recs[line2 -1 ]->ptr; - subfile2.size = diff_env->xdf2.recs[line2 + count2 -2 ]->ptr + - diff_env->xdf2.recs[line2 + count2 -2 ]->size - subfile2.ptr; + subfile1.ptr = (char *)diff_env->xdf1.recs[line1 -1 ].ptr; + subfile1.size = diff_env->xdf1.recs[line1 + count1 -2 ].ptr + + diff_env->xdf1.recs[line1 + count1 -2 ].size - subfile1.ptr; + subfile2.ptr = (char *)diff_env->xdf2.recs[line2 -1 ].ptr; + subfile2.size = diff_env->xdf2.recs[line2 + count2 -2 ].ptr + + diff_env->xdf2.recs[line2 + count2 -2 ].size - subfile2.ptr;if (xdl_do_diff (&subfile1, &subfile2, xpp, &env) <0 )return -1 ;
Signature · 1 line
gitgitgadget
PATCH v6 10/12 xdiff: rename rchg -> changed in xdfile_t
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
The field rchg (now 'changed') declares if a line in a file is changed or not. A later commit will change it's type from 'char' to 'bool' to make its purpose even more clear.
Best-viewed-with: --color-words
--- xdiff/xdiffi.c | 30 +++++++++++++++--------------- xdiff/xhistogram.c | 8 ++++---- xdiff/xpatience.c | 8 ++++---- xdiff/xprepare.c | 12 ++++++------ xdiff/xtypes.h | 2 +- xdiff/xutils.c | 4 ++-- 6 files changed, 32 insertions(+), 32 deletions(-)
xdiff/xdiffi.c +15 -15
@@ -278,10 +278,10 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,*/ if (off1 == lim1) {for (; off2 < lim2; off2++) - xdf2->rchg[xdf2->rindex[off2]] =1 ; + xdf2->changed[xdf2->rindex[off2]] =1 ; }else if (off2 == lim2) {for (; off1 < lim1; off1++) - xdf1->rchg[xdf1->rindex[off1]] =1 ; + xdf1->changed[xdf1->rindex[off1]] =1 ; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;
@@ -708,7 +708,7 @@ struct xdlgroup {static void group_init (xdfile_t *xdf,struct xdlgroup *g) { g->start = g->end =0 ; -while (xdf->rchg[g->end]) +while (xdf->changed[g->end]) g->end++; }
@@ -722,7 +722,7 @@ static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)return -1 ; g->start = g->end +1 ; -for (g->end = g->start; xdf->rchg[g->end]; g->end++) +for (g->end = g->start; xdf->changed[g->end]; g->end++) ;return 0 ;
@@ -738,7 +738,7 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)return -1 ; g->end = g->start -1 ; -for (g->start = g->end; xdf->rchg[g->start -1 ]; g->start--) +for (g->start = g->end; xdf->changed[g->start -1 ]; g->start--) ;return 0 ;
@@ -753,10 +753,10 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) {if (g->end < xdf->nrec &&recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { - xdf->rchg[g->start++] =0 ; - xdf->rchg[g->end++] =1 ; + xdf->changed[g->start++] =0 ; + xdf->changed[g->end++] =1 ; -while (xdf->rchg[g->end]) +while (xdf->changed[g->end]) g->end++;return 0 ;
@@ -774,10 +774,10 @@ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) {if (g->start >0 &&recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { - xdf->rchg[--g->start] =1 ; - xdf->rchg[--g->end] =0 ; + xdf->changed[--g->start] =1 ; + xdf->changed[--g->end] =0 ; -while (xdf->rchg[g->start -1 ]) +while (xdf->changed[g->start -1 ]) g->start--;return 0 ;
@@ -932,16 +932,16 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {int xdl_build_script (xdfenv_t *xe,xdchange_t **xscr) {xdchange_t *cscr =NULL , *xch; -char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg; +char *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;long i1, i2, l1, l2;/* * Trivial. Collects "groups" of changes and creates an edit script. */ for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >=0 || i2 >=0 ; i1--, i2--) -if (rchg1[i1 -1 ] || rchg2[i2 -1 ]) { -for (l1 = i1; rchg1[i1 -1 ]; i1--); -for (l2 = i2; rchg2[i2 -1 ]; i2--); +if (changed1[i1 -1 ] || changed2[i2 -1 ]) { +for (l1 = i1; changed1[i1 -1 ]; i1--); +for (l2 = i2; changed2[i2 -1 ]; i2--);if (!(xch =xdl_add_change (cscr, i1, i2, l1 - i1, l2 - i2))) {xdl_free_script (cscr);
xdiff/xhistogram.c +4 -4
@@ -318,11 +318,11 @@ redo:if (!count1) {while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;return 0 ; }
@@ -335,9 +335,9 @@ redo:else {if (lcs.begin1 ==0 && lcs.begin2 ==0 ) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ; result =0 ; }else { result = histogram_diff(xpp, env,
xdiff/xpatience.c +4 -4
@@ -331,11 +331,11 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* trivial case: one side is empty */ if (!count1) {while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;return 0 ; }
@@ -347,9 +347,9 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* are there any matching lines at all? */ if (!map.has_matches) {while (count1--) - env->xdf1.rchg[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] =1 ;while (count2--) - env->xdf2.rchg[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] =1 ;xdl_free (map.entries);return 0 ; }
xdiff/xprepare.c +6 -6
@@ -126,7 +126,7 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_tstatic void xdl_free_ctx (xdfile_t *xdf) {xdl_free (xdf->rindex); -xdl_free (xdf->rchg -1 ); +xdl_free (xdf->changed -1 );xdl_free (xdf->recs); }
@@ -139,7 +139,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_xrecord_t *crec; xdf->rindex =NULL ; - xdf->rchg =NULL ; + xdf->changed =NULL ; xdf->recs =NULL ;if (!XDL_ALLOC_ARRAY (xdf->recs, narec))
@@ -161,7 +161,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ } } -if (!XDL_CALLOC_ARRAY (xdf->rchg, xdf->nrec +2 )) +if (!XDL_CALLOC_ARRAY (xdf->changed, xdf->nrec +2 )) goto abort; if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
@@ -170,7 +170,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ goto abort; } - xdf->rchg +=1 ; + xdf->changed +=1 ; xdf->nreff =0 ; xdf->dstart =0 ; xdf->dend = xdf->nrec -1 ;
@@ -287,7 +287,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; } else - xdf1->rchg[i] = 1; + xdf1->changed[i] = 1; } xdf1->nreff = nreff;
@@ -297,7 +297,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; } else - xdf2->rchg[i] = 1; + xdf2->changed[i] = 1; } xdf2->nreff = nreff;
xdiff/xtypes.h +1 -1
@@ -48,7 +48,7 @@ typedef struct s_xdfile {xrecord_t *recs;long nrec;long dstart, dend; -char *rchg; +char *changed;long *rindex;long nreff; } xdfile_t;
xdiff/xutils.c +2 -2
@@ -425,8 +425,8 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,if (xdl_do_diff (&subfile1, &subfile2, xpp, &env) <0 )return -1 ; -memcpy (diff_env->xdf1.rchg + line1 -1 , env.xdf1.rchg, count1); -memcpy (diff_env->xdf2.rchg + line2 -1 , env.xdf2.rchg, count2); +memcpy (diff_env->xdf1.changed + line1 -1 , env.xdf1.changed, count1); +memcpy (diff_env->xdf2.changed + line2 -1 , env.xdf2.changed, count2);xdl_free_env (&env);
Signature · 1 line
gitgitgadget
PATCH v6 11/12 xdiff: add macros DISCARD(0), KEEP(1), INVESTIGATE(2) in xprepare.c
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
This commit is refactor-only; no behavior is changed. A future commit will use bool literals for changed[i].
The functions xdl_clean_mmatch() and xdl_cleanup_records() will be cleaned up more in a future patch series. The changes to xdl_cleanup_records(), in this patch, is just to make it clear why char rchg is refactored to bool changed.
Rename dis* to action* and replace literal numericals with macros. The old names came from when dis* (which I think was short for discard) was treated like a boolean, but over time it grew into a ternary state machine. The result was confusing because dis* and rchg* both used 0/1 values with different meanings.
The new names and macros make the states explicit. nm is short for number of matches, and mlim is a heuristic limit:
nm == 0 -> action[i] = DISCARD -> changed[i] = true
0 < nm < mlim -> action[i] = KEEP -> changed[i] = false
nm >= mlim -> action[i] = INVESTIGATE -> changed[i] = xdl_clean_mmatch()
When need_min is true, only DISCARD and KEEP occur because the limit is effectively infinite.
Best-viewed-with: --color-words
--- xdiff/xprepare.c | 106 ++++++++++++++++++++++++++++++----------------- 1 file changed, 69 insertions(+), 37 deletions(-)
xdiff/xprepare.c +69 -37
@@ -29,6 +29,9 @@#define XDL_GUESS_NLINES1 256#define XDL_GUESS_NLINES2 20 +#define DISCARD 0 +#define KEEP 1 +#define INVESTIGATE 2 typedef struct s_xdlclass { struct s_xdlclass *next;
@@ -190,15 +193,15 @@ void xdl_free_env(xdfenv_t *xe) { } -static int xdl_clean_mmatch (char const *dis,long i,long s,long e) { +static bool xdl_clean_mmatch (uint8_t const *action,long i,long s,long e) {long r, rdis0, rpdis0, rdis1, rpdis1;/* -* Limits the window the is examined during the similar-lines -* scan. The loops below stops when dis[i - r] == 1 (line that -* has no match), but there are corner cases where the loop -* proceed all the way to the extremities by causing huge -* performance penalties in case of big files. +* Limits the window that is examined during the similar-lines +* scan. The loops below stops when action[i - r] == KEEP +* (line that has no match), but there are corner cases where +* the loop proceed all the way to the extremities by causing +* huge performance penalties in case of big files. */ if (i - s >XDL_SIMSCAN_WINDOW ) s = i -XDL_SIMSCAN_WINDOW ;
@@ -207,40 +210,47 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {/* * Scans the lines before 'i' to find a run of lines that either -* have no match (dis[j] == 0) or have multiple matches (dis[j] > 1). -* Note that we always call this function with dis[i] > 1, so the -* current line (i) is already a multimatch line. +* have no match (action[j] == DISCARD) or have multiple matches +* (action[j] == INVESTIGATE). Note that we always call this +* function with action[i] == INVESTIGATE, so the current line +* (i) is already a multimatch line. */ for (r =1 , rdis0 =0 , rpdis0 =1 ; (i - r) >= s; r++) { -if (!dis[i - r]) +if (action[i - r] ==DISCARD ) rdis0++; -else if (dis[i - r] ==2 ) +else if (action[i - r] ==INVESTIGATE ) rpdis0++; -else +else if (action[i - r] ==KEEP )break ; +else +BUG ("Illegal value for action[i - r]" ); }/* -* If the run before the line 'i' found only multimatch lines, we -* return 0 and hence we don't make the current line (i) discarded. -* We want to discard multimatch lines only when they appear in the -* middle of runs with nomatch lines (dis[j] == 0). +* If the run before the line 'i' found only multimatch lines, +* we return false and hence we don't make the current line (i) +* discarded. We want to discard multimatch lines only when +* they appear in the middle of runs with nomatch lines +* (action[j] == DISCARD). */ if (rdis0 ==0 )return 0 ;for (r =1 , rdis1 =0 , rpdis1 =1 ; (i + r) <= e; r++) { -if (!dis[i + r]) +if (action[i + r] ==DISCARD ) rdis1++; -else if (dis[i + r] ==2 ) +else if (action[i + r] ==INVESTIGATE ) rpdis1++; -else +else if (action[i + r] ==KEEP )break ; +else +BUG ("Illegal value for action[i + r]" ); }/* -* If the run after the line 'i' found only multimatch lines, we -* return 0 and hence we don't make the current line (i) discarded. +* If the run after the line 'i' found only multimatch lines, +* we return false and hence we don't make the current line (i) +* discarded. */ if (rdis1 ==0 ) -return 0 ; +return false; rdis1 += rdis0; rpdis1 += rpdis0;
@@ -251,26 +261,38 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {/* * Try to reduce the problem complexity, discard records that have no * matches on the other file. Also, lines that have multiple matches -* might be potentially discarded if they happear in a run of discardable. +* might be potentially discarded if they appear in a run of discardable. */ static int xdl_cleanup_records (xdlclassifier_t *cf,xdfile_t *xdf1,xdfile_t *xdf2) {long i, nm, nreff, mlim;xrecord_t *recs;xdlclass_t *rcrec; -char *dis, *dis1, *dis2; -int need_min = !!(cf->flags &XDF_NEED_MINIMAL ); +uint8_t *action1 =NULL , *action2 =NULL ; +bool need_min = !!(cf->flags &XDF_NEED_MINIMAL ); +int ret =0 ; -if (!XDL_CALLOC_ARRAY (dis, xdf1->nrec + xdf2->nrec +2 )) -return -1 ; - dis1 = dis; - dis2 = dis1 + xdf1->nrec +1 ; +/* +* Create temporary arrays that will help us decide if +* changed[i] should remain 0 or become 1. +*/ +if (!XDL_CALLOC_ARRAY (action1, xdf1->nrec +1 )) { + ret =-1 ; + goto cleanup; + } +if (!XDL_CALLOC_ARRAY (action2, xdf2->nrec +1 )) { + ret =-1 ; + goto cleanup; + } +/* +* Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE. +*/ if ((mlim =xdl_bogosqrt (xdf1->nrec)) >XDL_MAX_EQLIMIT ) mlim =XDL_MAX_EQLIMIT ;for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len2 :0 ; - dis1[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; + action1[i] = (nm ==0 ) ?DISCARD : (nm >= mlim && !need_min) ?INVESTIGATE :KEEP ; }if ((mlim =xdl_bogosqrt (xdf2->nrec)) >XDL_MAX_EQLIMIT )
@@ -278,32 +300,42 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len1 :0 ; - dis2[i] = (nm ==0 ) ?0 : (nm >= mlim && !need_min) ?2 :1 ; + action2[i] = (nm ==0 ) ?DISCARD : (nm >= mlim && !need_min) ?INVESTIGATE :KEEP ; } +/* +* Use temporary arrays to decide if changed[i] should remain +* 0 or become 1. +*/ for (nreff =0 , i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { -if (dis1[i] ==1 || - (dis1[i] ==2 && !xdl_clean_mmatch (dis1, i, xdf1->dstart, xdf1->dend))) { +if (action1[i] ==KEEP || + (action1[i] ==INVESTIGATE && !xdl_clean_mmatch (action1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; +/* changed[i] remains 0, i.e. keep */ }else xdf1->changed[i] =1 ; +/* i.e. discard */ } xdf1->nreff = nreff;for (nreff =0 , i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { -if (dis2[i] ==1 || - (dis2[i] ==2 && !xdl_clean_mmatch (dis2, i, xdf2->dstart, xdf2->dend))) { +if (action2[i] ==KEEP || + (action2[i] ==INVESTIGATE && !xdl_clean_mmatch (action2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; +/* changed[i] remains 0, i.e. keep */ }else xdf2->changed[i] =1 ; +/* i.e. discard */ } xdf2->nreff = nreff; -xdl_free (dis); +cleanup: +xdl_free (action1); +xdl_free (action2); -return 0 ; +return ret; }
Signature · 1 line
gitgitgadget
PATCH v6 12/12 xdiff: change type of xdfile_t.changed from char to bool
In reply to Ezekiel Newren via GitGitGadgetFrom: Ezekiel Newren <[email protected]>
The only values possible for 'changed' is 1 and 0, which exactly maps to a bool type. It might not look like this because action1 and action2 (which use to be dis1, and dis2) were also of type char and were assigned numerical values within a few lines of 'changed' (what used to be rchg).
Using DISCARD/KEEP/INVESTIGATE for action1[i]/action2[j], and true/false for changed[k] makes it clear to future readers that these are logically separate concepts.
Best-viewed-with: --color-words
--- xdiff/xdiffi.c | 14 +++++++------- xdiff/xhistogram.c | 8 ++++---- xdiff/xpatience.c | 8 ++++---- xdiff/xprepare.c | 12 ++++++------ xdiff/xtypes.h | 2 +- 5 files changed, 22 insertions(+), 22 deletions(-)
xdiff/xdiffi.c +7 -7
@@ -278,10 +278,10 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,*/ if (off1 == lim1) {for (; off2 < lim2; off2++) - xdf2->changed[xdf2->rindex[off2]] =1 ; + xdf2->changed[xdf2->rindex[off2]] = true; }else if (off2 == lim2) {for (; off1 < lim1; off1++) - xdf1->changed[xdf1->rindex[off1]] =1 ; + xdf1->changed[xdf1->rindex[off1]] = true; }else {xdpsplit_t spl; spl.i1 = spl.i2 =0 ;
@@ -753,8 +753,8 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) {if (g->end < xdf->nrec &&recs_match (&xdf->recs[g->start], &xdf->recs[g->end])) { - xdf->changed[g->start++] =0 ; - xdf->changed[g->end++] =1 ; + xdf->changed[g->start++] = false; + xdf->changed[g->end++] = true;while (xdf->changed[g->end]) g->end++;
@@ -774,8 +774,8 @@ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) {if (g->start >0 &&recs_match (&xdf->recs[g->start -1 ], &xdf->recs[g->end -1 ])) { - xdf->changed[--g->start] =1 ; - xdf->changed[--g->end] =0 ; + xdf->changed[--g->start] = true; + xdf->changed[--g->end] = false;while (xdf->changed[g->start -1 ]) g->start--;
@@ -932,7 +932,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {int xdl_build_script (xdfenv_t *xe,xdchange_t **xscr) {xdchange_t *cscr =NULL , *xch; -char *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed; +bool *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;long i1, i2, l1, l2;/*
xdiff/xhistogram.c +4 -4
@@ -318,11 +318,11 @@ redo:if (!count1) {while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;return 0 ; }
@@ -335,9 +335,9 @@ redo:else {if (lcs.begin1 ==0 && lcs.begin2 ==0 ) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true; result =0 ; }else { result = histogram_diff(xpp, env,
xdiff/xpatience.c +4 -4
@@ -331,11 +331,11 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* trivial case: one side is empty */ if (!count1) {while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;return 0 ; }else if (!count2) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;return 0 ; }
@@ -347,9 +347,9 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,/* are there any matching lines at all? */ if (!map.has_matches) {while (count1--) - env->xdf1.changed[line1++ -1 ] =1 ; + env->xdf1.changed[line1++ -1 ] = true;while (count2--) - env->xdf2.changed[line2++ -1 ] =1 ; + env->xdf2.changed[line2++ -1 ] = true;xdl_free (map.entries);return 0 ; }
xdiff/xprepare.c +6 -6
@@ -273,7 +273,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd/* * Create temporary arrays that will help us decide if -* changed[i] should remain 0 or become 1. +* changed[i] should remain false, or become true. */ if (!XDL_CALLOC_ARRAY (action1, xdf1->nrec +1 )) { ret =-1 ;
@@ -305,16 +305,16 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd/* * Use temporary arrays to decide if changed[i] should remain -* 0 or become 1. +* false, or become true. */ for (nreff =0 , i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {if (action1[i] ==KEEP || (action1[i] ==INVESTIGATE && !xdl_clean_mmatch (action1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; -/* changed[i] remains 0, i.e. keep */ +/* changed[i] remains false, i.e. keep */ }else - xdf1->changed[i] =1 ; + xdf1->changed[i] = true;/* i.e. discard */ } xdf1->nreff = nreff;
@@ -324,9 +324,9 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdif (action2[i] ==KEEP || (action2[i] ==INVESTIGATE && !xdl_clean_mmatch (action2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; -/* changed[i] remains 0, i.e. keep */ +/* changed[i] remains false, i.e. keep */ }else - xdf2->changed[i] =1 ; + xdf2->changed[i] = true;/* i.e. discard */ } xdf2->nreff = nreff;
xdiff/xtypes.h +1 -1
@@ -48,7 +48,7 @@ typedef struct s_xdfile {xrecord_t *recs;long nrec;long dstart, dend; -char *changed; +bool *changed;long *rindex;long nreff; } xdfile_t;
Signature · 1 line
gitgitgadget
Re: [PATCH v6 00/12] Cleanup xdfile_t and xrecord_t in xdiff.
In reply to Ezekiel Newren via GitGitGadgetHi Ezekiel
Quoted 6 lines · Ezekiel Newren via GitGitGadget
Changes since v5.
* Address review feedback on commit messages.
* Drop commit "xdiff: delete rchg aliasing"
* Use DISCARD/KEEP/INVESTIGATE instead of NONE/SOME/TOO_MANY
* Fix the word wrapping in the comments ofxprepare.c
Thanks for expanding the commit messages, I think the range diff looks good. There's a typo in patch 12 (see below) but its not worth re-rolling just for that.
Quoted 14 lines
Range-diff vs v5:
[...]
12:08a0fceb72! 11:f08782a977xdiff: use enum macros NONE(0), SOME(1),TOO_MANY(2)inxprepare.c
@@ Metadata
Author: Ezekiel Newren <[email protected]>## Commit message ##
- xdiff: use enum macros NONE(0), SOME(1),TOO_MANY(2)inxprepare.c
+ xdiff: add macros DISCARD(0), KEEP(1), INVESTIGATE(2) inxprepare.c- Rename dis1, dis2 to matches1, matches2.
+ This commit is refactor-only; no behavior is changed. A future commit
+ will use bool literals for changed[i].
Quoted 6 lines
- Define macros NONE(0), SOME(1),
TOO_MANY(2)as the enum values for
- matches1 and matches2. These states will influence whether changed[i]
- is set to 1 or kept as 0.
+ The functionsxdl_clean_mmatch()andxdl_cleanup_records()will be
+ cleaned up more in a future patch series. The changes to
+xdl_cleanup_records(), in this patch, is just to make it clear why
Not worth a re-roll on its own s/is/are/
Thanks for working on this
Phillip
Quoted 329 lines
+ `char rchg` is refactored to `bool changed`. + + Rename dis* to action* and replace literal numericals with macros. + The old names came from when dis* (which I think was short for discard) + was treated like a boolean, but over time it grew into a ternary state + machine. The result was confusing because dis* and rchg* both used 0/1 + values with different meanings. + + The new names and macros make the states explicit. nm is short for + number of matches, and mlim is a heuristic limit: + + nm == 0 -> action[i] = DISCARD -> changed[i] = true + 0 < nm < mlim -> action[i] = KEEP -> changed[i] = false + nm >= mlim -> action[i] = INVESTIGATE -> changed[i] = xdl_clean_mmatch() + + When need_min is true, only DISCARD and KEEP occur because the limit + is effectively infinite. Best-viewed-with: --color-words Signed-off-by: Ezekiel Newren <[email protected]> @@ xdiff/xprepare.c #define XDL_GUESS_NLINES1 256 #define XDL_GUESS_NLINES2 20 -+#define NONE 0 -+#define SOME 1 -+#define TOO_MANY 2 ++#define DISCARD 0 ++#define KEEP 1 ++#define INVESTIGATE 2 typedef struct s_xdlclass { struct s_xdlclass *next; @@ xdiff/xprepare.c: void xdl_free_env(xdfenv_t *xe) { -static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { -+static bool xdl_clean_mmatch(uint8_t const *matches, long i, long s, long e) { ++static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) { long r, rdis0, rpdis0, rdis1, rpdis1; /* - * Limits the window the is examined during the similar-lines - * scan. The loops below stops when dis[i - r] == 1 (line that +- * has no match), but there are corner cases where the loop +- * proceed all the way to the extremities by causing huge +- * performance penalties in case of big files. + * Limits the window that is examined during the similar-lines -+ * scan. The loops below stops when matches[i - r] == SOME (line that - * has no match), but there are corner cases where the loop - * proceed all the way to the extremities by causing huge - * performance penalties in case of big files. ++ * scan. The loops below stops when action[i - r] == KEEP ++ * (line that has no match), but there are corner cases where ++ * the loop proceed all the way to the extremities by causing ++ * huge performance penalties in case of big files. + */ + if (i - s > XDL_SIMSCAN_WINDOW) + s = i - XDL_SIMSCAN_WINDOW; @@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { /* * Scans the lines before 'i' to find a run of lines that either - * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1). - * Note that we always call this function with dis[i] > 1, so the -+ * have no match (matches[j] == NONE) or have multiple matches (matches[j] == TOO_MANY). -+ * Note that we always call this function with matches[i] == TOO_MANY, so the - * current line (i) is already a multimatch line. +- * current line (i) is already a multimatch line. ++ * have no match (action[j] == DISCARD) or have multiple matches ++ * (action[j] == INVESTIGATE). Note that we always call this ++ * function with action[i] == INVESTIGATE, so the current line ++ * (i) is already a multimatch line. */ for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) { - if (!dis[i - r]) -+ if (matches[i - r] == NONE) ++ if (action[i - r] == DISCARD) rdis0++; - else if (dis[i - r] == 2) -+ else if (matches[i - r] == TOO_MANY) ++ else if (action[i - r] == INVESTIGATE) rpdis0++; - else -+ else if (matches[i - r] == SOME) ++ else if (action[i - r] == KEEP) break; + else -+ BUG("Illegal value for matches[i - r]"); ++ BUG("Illegal value for action[i - r]"); } /* - * If the run before the line 'i' found only multimatch lines, we +- * If the run before the line 'i' found only multimatch lines, we - * return 0 and hence we don't make the current line (i) discarded. -+ * return false and hence we don't make the current line (i) discarded. - * We want to discard multimatch lines only when they appear in the +- * We want to discard multimatch lines only when they appear in the - * middle of runs with nomatch lines (dis[j] == 0). -+ * middle of runs with nomatch lines (matches[j] == NONE). ++ * If the run before the line 'i' found only multimatch lines, ++ * we return false and hence we don't make the current line (i) ++ * discarded. We want to discard multimatch lines only when ++ * they appear in the middle of runs with nomatch lines ++ * (action[j] == DISCARD). */ if (rdis0 == 0) return 0; for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) { - if (!dis[i + r]) -+ if (matches[i + r] == NONE) ++ if (action[i + r] == DISCARD) rdis1++; - else if (dis[i + r] == 2) -+ else if (matches[i + r] == TOO_MANY) ++ else if (action[i + r] == INVESTIGATE) rpdis1++; - else -+ else if (matches[i + r] == SOME) ++ else if (action[i + r] == KEEP) break; + else -+ BUG("Illegal value for matches[i + r]"); ++ BUG("Illegal value for action[i + r]"); } /* - * If the run after the line 'i' found only multimatch lines, we +- * If the run after the line 'i' found only multimatch lines, we - * return 0 and hence we don't make the current line (i) discarded. -+ * return false and hence we don't make the current line (i) discarded. ++ * If the run after the line 'i' found only multimatch lines, ++ * we return false and hence we don't make the current line (i) ++ * discarded. */ if (rdis1 == 0) - return 0; @@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, l xdlclass_t *rcrec; - char *dis, *dis1, *dis2; - int need_min = !!(cf->flags & XDF_NEED_MINIMAL); -+ uint8_t *matches1, *matches2; -+ int status = 0; ++ uint8_t *action1 = NULL, *action2 = NULL; + bool need_min = !!(cf->flags & XDF_NEED_MINIMAL); ++ int ret = 0; - if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2)) - return -1; - dis1 = dis; - dis2 = dis1 + xdf1->nrec + 1; -+ matches1 = NULL; -+ matches2 = NULL; -+ + /* + * Create temporary arrays that will help us decide if + * changed[i] should remain 0 or become 1. + */ -+ if (!XDL_CALLOC_ARRAY(matches1, xdf1->nrec + 1)) { -+ status = -1; ++ if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) { ++ ret = -1; + goto cleanup; + } -+ if (!XDL_CALLOC_ARRAY(matches2, xdf2->nrec + 1)) { -+ status = -1; ++ if (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) { ++ ret = -1; + goto cleanup; + } + /* -+ * Initialize temporary arrays with NONE, SOME, or TOO_MANY. ++ * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE. + */ if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT) mlim = XDL_MAX_EQLIMIT; @@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, l rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len2 : 0; - dis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1; -+ matches1[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME; ++ action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; } if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT) @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t * rcrec = cf->rcrecs[recs->ha]; nm = rcrec ? rcrec->len1 : 0; - dis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1; -+ matches2[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME; ++ action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; } + /* @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t * i <= xdf1->dend; i++, recs++) { - if (dis1[i] == 1 || - (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) { -+ if (matches1[i] == SOME || -+ (matches1[i] == TOO_MANY && !xdl_clean_mmatch(matches1, i, xdf1->dstart, xdf1->dend))) { ++ if (action1[i] == KEEP || ++ (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) { xdf1->rindex[nreff++] = i; -+ /* changed[i] remains 0 */ ++ /* changed[i] remains 0, i.e. keep */ } else xdf1->changed[i] = 1; ++ /* i.e. discard */ } -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd + xdf1->nreff = nreff; for (nreff = 0, i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { - if (dis2[i] == 1 || - (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) { -+ if (matches2[i] == SOME || -+ (matches2[i] == TOO_MANY && !xdl_clean_mmatch(matches2, i, xdf2->dstart, xdf2->dend))) { ++ if (action2[i] == KEEP || ++ (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) { xdf2->rindex[nreff++] = i; -+ /* changed[i] remains 0 */ ++ /* changed[i] remains 0, i.e. keep */ } else xdf2->changed[i] = 1; ++ /* i.e. discard */ } xdf2->nreff = nreff; - xdl_free(dis); +cleanup: -+ xdl_free(matches1); -+ xdl_free(matches2); ++ xdl_free(action1); ++ xdl_free(action2); - return 0; -+ return status; ++ return ret; }13:
975e845bfa! 12:83e1ace5bdxdiff: change type of xdfile_t.changed from char to bool
@@ Commit message
xdiff: change type of xdfile_t.changed from char to boolThe only values possible for 'changed' is 1 and 0, which exactly maps
- to a bool type. It might not look like this is the case because
- matches1 and matches2 (which use to be dis1, and dis2) were also char
- and were assigned numerical values within a few lines of 'changed'
- (what used to be rchg).
+ to a bool type. It might not look like this because action1 and action2
+ (which use to be dis1, and dis2) were also of type char and were
+ assigned numerical values within a few lines of 'changed' (what used to
+ be rchg).- Using NONE, SOME,
TOO_MANYfor matches1[i]/matches2[j], and true/false
+ Using DISCARD/KEEP/INVESTIGATE for action1[i]/action2[j], and true/false
for changed[k] makes it clear to future readers that these are logically separate concepts.@@
xdiff/xdiffi.c: static intgroup_slide_up(xdfile_t *xdf, struct xdlgroup *g)while (xdf->changed[g->start - 1])
g->start--;
+@@xdiff/xdiffi.c: intxdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags){ +
+ intxdl_build_script(xdfenv_t *xe, xdchange_t **xscr){
+xdchange_t*cscr = NULL, *xch;
+- char *changed1 =xe->xdf1.changed, *changed2 =xe->xdf2.changed;
++ bool *changed1 =xe->xdf1.changed, *changed2 =xe->xdf2.changed;
+ long i1, i2, l1, l2;
+
+ /*##
xdiff/xhistogram.c##
@@xdiff/xhistogram.c: redo:
@@xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf,xdfile_t*
- * changed[i] should remain 0 or become 1.
+ * changed[i] should remain false, or become true.
*/
- if (!XDL_CALLOC_ARRAY(matches1,xdf1->nrec+ 1)) {
- status = -1;
+ if (!XDL_CALLOC_ARRAY(action1,xdf1->nrec+ 1)) {
+ ret = -1;
@@xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf,xdfile_t*xdf1,xdfile_t*xd/*
@@xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf,xdfile_t*
*/
for (nreff = 0, i =xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
i <=xdf1->dend; i++, recs++) {
- if (matches1[i] == SOME ||
- (matches1[i] ==TOO_MANY&& !xdl_clean_mmatch(matches1, i,xdf1->dstart,xdf1->dend))) {
+ if (action1[i] == KEEP ||
+ (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i,xdf1->dstart,xdf1->dend))) {
xdf1->rindex[nreff++] = i;
-- /* changed[i] remains 0 */
-+ /* changed[i] remains false */
+- /* changed[i] remains 0, i.e. keep */
++ /* changed[i] remains false, i.e. keep */
} else
- xdf1->changed[i] = 1;
+ xdf1->changed[i] = true;
+ /* i.e. discard */
}
xdf1->nreff= nreff;
-
@@xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf,xdfile_t*xdf1,xdfile_t*xd
- if (matches2[i] == SOME ||
- (matches2[i] ==TOO_MANY&& !xdl_clean_mmatch(matches2, i,xdf2->dstart,xdf2->dend))) {
+ if (action2[i] == KEEP ||
+ (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i,xdf2->dstart,xdf2->dend))) {
xdf2->rindex[nreff++] = i;
-- /* changed[i] remains 0 */
-+ /* changed[i] remains false */
+- /* changed[i] remains 0, i.e. keep */
++ /* changed[i] remains false, i.e. keep */
} else
- xdf2->changed[i] = 1;
+ xdf2->changed[i] = true;
+ /* i.e. discard */
}
xdf2->nreff= nreff;
-##
xdiff/xtypes.h##
@@xdiff/xtypes.h: typedef structs_xdfile{