Overview
SHA1 Hash: | 0523983440b0cd26366d924a3674eab30e93e1f1 |
---|---|
Date: | 2008-02-03 01:36:14 |
User: | aku |
Comment: | Merged importer to mainline. |
Timelines: | ancestors | descendants | both | trunk |
Other Links: | files | ZIP archive | manifest |
Tags And Properties
- branch=trunk inherited from [a28c83647d]
- sym-trunk inherited from [a28c83647d]
Changes
[hide diffs]Modified src/diff.c from [ec5d799613] to [62a5d65904].
@@ -42,29 +42,53 @@ ** line. If any line is longer than 1048575 characters, ** the file is considered binary. */ typedef struct DLine DLine; struct DLine { - const char *z; /* The text of the line */ - unsigned int h; /* Hash of the line */ + const char *z; /* The text of the line */ + unsigned int h; /* Hash of the line */ + unsigned int iNext; /* Index+1 of next line with same the same hash */ + + /* an array of DLine elements services two purposes. The fields + ** above are one per line of input text. But each entry is also + ** a bucket in a hash table. */ + unsigned int iHash; /* First entry+1 in the hash array */ }; -#define LENGTH_MASK 0x000fffff +/* +** Maximum length of a line in a text file. (8192) +*/ +#define LENGTH_MASK_SZ 13 +#define LENGTH_MASK ((1<<LENGTH_MASK_SZ)-1) + +/* +** A context for running a diff. +*/ +typedef struct DContext DContext; +struct DContext { + int *aEdit; /* Array of copy/delete/insert triples */ + int nEdit; /* Number of integers (3x num of triples) in aEdit[] */ + int nEditAlloc; /* Space allocated for aEdit[] */ + DLine *aFrom; /* File on left side of the diff */ + int nFrom; /* Number of lines in aFrom[] */ + DLine *aTo; /* File on right side of the diff */ + int nTo; /* Number of lines in aTo[] */ +}; /* ** Return an array of DLine objects containing a pointer to the ** start of each line and a hash of that line. The lower ** bits of the hash store the length of each line. ** ** Trailing whitespace is removed from each line. ** ** Return 0 if the file is binary or contains a line that is -** longer than 1048575 bytes. +** too long. */ static DLine *break_into_lines(char *z, int *pnLine){ int nLine, i, j, k, x; - unsigned int h; + unsigned int h, h2; DLine *a; /* Count the number of lines. Allocate space to hold ** the returned array. */ @@ -73,31 +97,35 @@ if( c==0 ){ return 0; } if( c=='\n' && z[i+1]!=0 ){ nLine++; - if( j>1048575 ){ + if( j>LENGTH_MASK ){ return 0; } j = 0; } } - if( j>1048575 ){ + if( j>LENGTH_MASK ){ return 0; } a = malloc( nLine*sizeof(a[0]) ); if( a==0 ) fossil_panic("out of memory"); + memset(a, 0, nLine*sizeof(a[0]) ); /* Fill in the array */ for(i=0; i<nLine; i++){ a[i].z = z; for(j=0; z[j] && z[j]!='\n'; j++){} for(k=j; k>0 && isspace(z[k-1]); k--){} for(h=0, x=0; x<k; x++){ h = h ^ (h<<2) ^ z[x]; } - a[i].h = (h<<20) | k;; + a[i].h = h = (h<<LENGTH_MASK_SZ) | k;; + h2 = h % nLine; + a[i].iNext = a[h2].iHash; + a[h2].iHash = i+1; z += j+1; } /* Return results */ *pnLine = nLine; @@ -118,10 +146,336 @@ blob_append(pOut, zPrefix, 1); blob_append(pOut, pLine->z, pLine->h & LENGTH_MASK); blob_append(pOut, "\n", 1); } +/* +** Expand the size of aEdit[] array to hold nEdit elements. +*/ +static void expandEdit(DContext *p, int nEdit){ + int *a; + a = realloc(p->aEdit, nEdit*sizeof(int)); + if( a==0 ){ + free( p->aEdit ); + p->nEdit = 0; + nEdit = 0; + } + p->aEdit = a; + p->nEditAlloc = nEdit; +} + +/* +** Append a new COPY/DELETE/INSERT triple. +*/ +static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){ + /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */ + if( p->nEdit>=3 ){ + if( p->aEdit[p->nEdit-1]==0 ){ + if( p->aEdit[p->nEdit-2]==0 ){ + p->aEdit[p->nEdit-3] += nCopy; + p->aEdit[p->nEdit-2] += nDel; + p->aEdit[p->nEdit-1] += nIns; + return; + } + if( nCopy==0 ){ + p->aEdit[p->nEdit-2] += nDel; + p->aEdit[p->nEdit-1] += nIns; + return; + } + } + if( nCopy==0 && nDel==0 ){ + p->aEdit[p->nEdit-1] += nIns; + return; + } + } + if( p->nEdit+3>p->nEditAlloc ){ + expandEdit(p, p->nEdit*2 + 15); + if( p->aEdit==0 ) return; + } + p->aEdit[p->nEdit++] = nCopy; + p->aEdit[p->nEdit++] = nDel; + p->aEdit[p->nEdit++] = nIns; +} + + +/* +** Given a diff context in which the aEdit[] array has been filled +** in, compute a context diff into pOut. +*/ +static void contextDiff(DContext *p, Blob *pOut, int nContext){ + DLine *A; /* Left side of the diff */ + DLine *B; /* Right side of the diff */ + int a = 0; /* Index of next line in A[] */ + int b = 0; /* Index of next line in B[] */ + int *R; /* Array of COPY/DELETE/INSERT triples */ + int r; /* Index into R[] */ + int nr; /* Number of COPY/DELETE/INSERT triples to process */ + int mxr; /* Maximum value for r */ + int na, nb; /* Number of lines shown from A and B */ + int i, j; /* Loop counters */ + int m; /* Number of lines to output */ + int skip; /* Number of lines to skip */ + + A = p->aFrom; + B = p->aTo; + R = p->aEdit; + mxr = p->nEdit; + if( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; } + for(r=0; r<mxr; r += 3*nr){ + /* Figure out how many triples to show in a single block */ + for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<nContext*2; nr++){} + DEBUG( printf("r=%d nr=%d\n", r, nr); ) + + /* For the current block comprising nr triples, figure out + ** how many lines of A and B are to be displayed + */ + if( R[r]>nContext ){ + na = nb = nContext; + skip = R[r] - nContext; + }else{ + na = nb = R[r]; + skip = 0; + } + for(i=0; i<nr; i++){ + na += R[r+i*3+1]; + nb += R[r+i*3+2]; + } + if( R[r+nr*3]>nContext ){ + na += nContext; + nb += nContext; + }else{ + na += R[r+nr*3]; + nb += R[r+nr*3]; + } + for(i=1; i<nr; i++){ + na += R[r+i*3]; + nb += R[r+i*3]; + } + blob_appendf(pOut,"@@ -%d,%d +%d,%d @@\n", a+skip+1, na, b+skip+1, nb); + + /* Show the initial common area */ + a += skip; + b += skip; + m = R[r] - skip; + for(j=0; j<m; j++){ + appendDiffLine(pOut, " ", &A[a+j]); + } + a += m; + b += m; + + /* Show the differences */ + for(i=0; i<nr; i++){ + m = R[r+i*3+1]; + for(j=0; j<m; j++){ + appendDiffLine(pOut, "-", &A[a+j]); + } + a += m; + m = R[r+i*3+2]; + for(j=0; j<m; j++){ + appendDiffLine(pOut, "+", &B[b+j]); + } + b += m; + if( i<nr-1 ){ + m = R[r+i*3+3]; + for(j=0; j<m; j++){ + appendDiffLine(pOut, " ", &B[b+j]); + } + b += m; + a += m; + } + } + + /* Show the final common area */ + assert( nr==i ); + m = R[r+nr*3]; + if( m>nContext ) m = nContext; + for(j=0; j<m; j++){ + appendDiffLine(pOut, " ", &B[b+j]); + } + } +} + +/* +** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[] +** file and lines iS2 through iE2-1 of the aTo[] file. Locate a sequence +** of lines in these two blocks that are exactly the same. Return +** the bounds of the matching sequence. +*/ +static void longestCommonSequence( + DContext *p, + int iS1, int iE1, + int iS2, int iE2, + int *piSX, int *piEX, + int *piSY, int *piEY +){ + int bestScore = -1000000000; + int i, j; + int iSX, iSY, iEX, iEY; + int score, skew, dist, mid; + + *piSX = iS1; + *piEX = iS1; + *piSY = iS2; + *piEY = iS2; + mid = (iE1 + iS1)/2; + for(i=iS1; i<iE1; i++){ + int limit = 0; + j = p->aTo[p->aFrom[i].h % p->nTo].iHash; + while( j>0 + && (j-1<iS2 || j>=iE2 || !same_dline(&p->aFrom[i], &p->aTo[j-1])) + ){ + if( limit++ > 10 ){ + j = 0; + break; + } + j = p->aTo[j-1].iNext; + } + if( j==0 ) continue; + iSX = i; + iSY = j-1; + while( iSX>iS1 && iSY>iS2 && same_dline(&p->aFrom[iSX-1],&p->aTo[iSY-1]) ){ + iSX--; + iSY--; + } + iEX = i+1; + iEY = j; + while( iEX<iE1 && iEY<iE2 && same_dline(&p->aFrom[iEX],&p->aTo[iEY]) ){ + iEX++; + iEY++; + } + skew = (iSX-iS1) - (iSY-iS2); + if( skew<0 ) skew = -skew; + dist = (iSX+iEX)/2 - mid; + if( dist<0 ) dist = -dist; + score = (iEX - iSX) - 0.05*skew - 0.05*dist; + if( score>bestScore ){ + bestScore = score; + *piSX = iSX; + *piSY = iSY; + *piEX = iEX; + *piEY = iEY; + } + } + /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n", + iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY); */ +} + +/* +** Do a single step in the difference. Compute a sequence of +** copy/delete/insert steps that will convert lines iS1 through iE1-1 of +** the input into lines iS2 through iE2-1 of the output and write +** that sequence into the difference context. +*/ +static void diff_step(DContext *p, int iS1, int iE1, int iS2, int iE2){ + int iSX, iEX, iSY, iEY; + + if( iE1<=iS1 ){ + if( iE2>iS2 ){ + appendTriple(p, 0, 0, iE2-iS2); + } + return; + } + if( iE2<=iS2 ){ + appendTriple(p, 0, iE1-iS1, 0); + return; + } + + /* Find the longest matching segment between the two sequences */ + longestCommonSequence(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY); + + if( iEX>iSX ){ + /* Recursively diff either side of the matching segment */ + diff_step(p, iS1, iSX, iS2, iSY); + if( iEX>iSX ){ + appendTriple(p, iEX - iSX, 0, 0); + } + diff_step(p, iEX, iE1, iEY, iE2); + }else{ + appendTriple(p, 0, iE1-iS1, iE2-iS2); + } +} + +/* +** Generate a report of the differences between files pA and pB. +** If pOut is not NULL then a unified diff is appended there. It +** is assumed that pOut has already been initialized. If pOut is +** NULL, then a pointer to an array of integers is returned. +** The integers come in triples. For each triple, +** the elements are the number of lines copied, the number of +** lines deleted, and the number of lines inserted. The vector +** is terminated by a triple of all zeros. +** +** This diff utility does not work on binary files. If a binary +** file is encountered, 0 is returned and pOut is written with +** text "cannot compute difference between binary files". +*/ +int *text_diff( + Blob *pA_Blob, /* FROM file */ + Blob *pB_Blob, /* TO file */ + Blob *pOut, /* Write unified diff here if not NULL */ + int nContext /* Amount of context to unified diff */ +){ + DContext c; + int mnE, iS, iE1, iE2; + + memset(&c, 0, sizeof(c)); + c.aFrom = break_into_lines(blob_str(pA_Blob), &c.nFrom); + c.aTo = break_into_lines(blob_str(pB_Blob), &c.nTo); + if( c.aFrom==0 || c.aTo==0 ){ + free(c.aFrom); + free(c.aTo); + if( pOut ){ + blob_appendf(pOut, "cannot compute difference between binary files\n"); + } + return 0; + } + + /* Carve off the common header and footer */ + iE1 = c.nFrom; + iE2 = c.nTo; + while( iE1>0 && iE2>0 && same_dline(&c.aFrom[iE1-1], &c.aTo[iE2-1]) ){ + iE1--; + iE2--; + } + mnE = iE1<iE2 ? iE1 : iE2; + for(iS=0; iS<mnE && same_dline(&c.aFrom[iS],&c.aTo[iS]); iS++){} + + /* do the difference */ + if( iS>0 ){ + appendTriple(&c, iS, 0, 0); + } + diff_step(&c, iS, iE1, iS, iE2); + if( iE1<c.nFrom ){ + appendTriple(&c, c.nFrom - iE1, 0, 0); + } + + expandEdit(&c, c.nEdit+3); + if( c.aEdit ){ + c.aEdit[c.nEdit++] = 0; + c.aEdit[c.nEdit++] = 0; + c.aEdit[c.nEdit++] = 0; + } + + if( pOut ){ + /* Compute a context diff if requested */ + contextDiff(&c, pOut, nContext); + free(c.aFrom); + free(c.aTo); + free(c.aEdit); + return 0; + }else{ + /* If a context diff is not requested, then return the + ** array of COPY/DELETE/INSERT triples after terminating the + ** array with a triple of all zeros. + */ + free(c.aFrom); + free(c.aTo); + return c.aEdit; + } +} + +#if 0 /********** Disabled and replaced by code above ************/ /* ** Generate a report of the differences between files pA and pB. ** If pOut is not NULL then a unified diff is appended there. It ** is assumed that pOut has already been initialized. If pOut is @@ -472,10 +826,11 @@ free(B); /* Return the result */ return R; } +#endif /***************** End of the Wagner/Myers algorithm ************/ /* ** COMMAND: test-rawdiff */ void test_rawdiff_cmd(void){
Modified src/tagview.c from [475277fbb2] to [0d0a9751aa].
@@ -1,7 +1,8 @@ /* ** Copyright (c) 2007 D. Richard Hipp +** Copyright (c) 2008 Stephan Beal ** ** This program is free software; you can redistribute it and/or ** modify it under the terms of the GNU General Public ** License as published by the Free Software Foundation; either ** version 2 of the License, or (at your option) any later version. @@ -40,60 +41,195 @@ const char *zLink, const char *zDesc ){ @ <tr><td valign="top" align="right"> if( zLink && zLink[0] ){ - @ <a href="%s(zLink)">%h(zTitle)</a> + @ <a href="%s(g.zBaseURL)/%s(zLink)">%h(zTitle)</a> }else{ @ %h(zTitle) } @ </td><td valign="top">%h(zDesc)</td></tr> } -/* -** WEBPAGE: /tagview -*/ -void tagview_page(void){ +static void tagview_page_list_tags( char const * like ) +{ Stmt st; - - login_check_credentials(); - if( !g.okSetup ){ - login_needed(); + char * likeclause = 0; + const int limit = 10; + char * limitstr = 0; + if( like && strlen(like) ) + { + likeclause = mprintf( "AND t.tagname LIKE '%%%%%q%%%%'", like ); + @ <h2>Tags matching [%s(likeclause)]:</h2> } - style_header("Tags List"); + else + { + limitstr = mprintf( "LIMIT %d", limit ); + @ <h2>%d(limit) most recent tags:</h2> + } @ <table cellpadding='4px' border='1'><tbody> - @ <tr><th>Tag name</th><th>Timestamp</th><th>Version</th></tr> - db_prepare( &st, - "select t.tagname, DATETIME(tx.mtime), b.uuid " - "FROM tag t, tagxref tx, blob b " - "WHERE t.tagid=tx.tagid and tx.rid=b.rid " - "AND tx.tagtype != 0 " - "ORDER BY tx.mtime DESC" - ); - while( SQLITE_ROW == db_step(&st) ) - { - char const * tagname = db_column_text( &st, 0 ); - char const * tagtime = db_column_text( &st, 1 ); - char const * uuid = db_column_text( &st, 2 ); - const int offset = 10; - char shortname[offset+1]; - shortname[offset] = '\0'; - memcpy( shortname, uuid, offset ); - @ <tr> - @ <td><tt>%s(tagname)</tt></td> - @ <td align='center'><tt>%s(tagtime)</tt></td> - @ <td><tt> - @ <a href='/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a></tt> - @ </td></tr> + @ <tr> + @ <th>Tag ID</th> + @ <th>Tag name</th> + @ <th>Timestamp</th> + @ <th>Version</th> + @ </tr> + char * sql = mprintf( + "SELECT t.tagid, t.tagname, DATETIME(tx.mtime), b.uuid " + "FROM tag t, tagxref tx, blob b " + "WHERE (t.tagid=tx.tagid) and (tx.srcid=b.rid) " + "AND (tx.tagtype != 0) %s " + "ORDER BY tx.mtime DESC %s", + likeclause ? likeclause : " ", + limitstr ? limitstr : " " + ); + db_prepare( &st, sql ); + if( likeclause ) free( likeclause ); + free( sql ); + while( SQLITE_ROW == db_step(&st) ){ + int tagid = db_column_int( &st, 0 ); + char const * tagname = db_column_text( &st, 1 ); + char const * tagtime = db_column_text( &st, 2 ); + char const * uuid = db_column_text( &st, 3 ); + const int offset = 10; + char shortname[offset+1]; + shortname[offset] = '\0'; + memcpy( shortname, uuid, offset ); + @ <tr> + @ <td><tt> + @ <a href='%s(g.zBaseURL)/tagview?tagid=%d(tagid)'>%d(tagid)</a> + @ </tt></td> + @ <td><tt><a href='%s(g.zBaseURL)/tagview/%q(tagname)'>%s(tagname)</a></tt></td> + @ <td align='center'><tt>%s(tagtime)</tt></td> + @ <td><tt> + @ <a href='%s(g.zBaseURL)/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a> + @ </tt></td></tr> } db_finalize( &st ); @ </tbody></table> @ <hr/>TODOs include: @ <ul> @ <li>Page through long tags lists.</li> - @ <li>Format the timestamp field.</li> + @ <li>Refactor the internal report routines to be reusable.</li> @ <li>Allow different sorting.</li> + @ <li>Selectively filter out wiki/ticket/baseline</li> @ <li>?</li> @ </ul> - style_footer(); + +} + +static void tagview_page_search_miniform(void){ + char const * like = P("like"); + @ <div style='font-size:smaller'> + @ <form action='/tagview' method='post'> + @ Search for tags: + @ <input type='text' name='like' value='%s((like?like:""))' size='10'/> + @ <input type='submit'/> + @ </form> + @ </div> +} + + +static void tagview_page_default(void){ + tagview_page_list_tags( 0 ); +} + +static void tagview_page_tag_by_id( int tagid ) +{ + Stmt st; + char * sql = mprintf( + "SELECT DISTINCT (t.tagname), DATETIME(tx.mtime), b.uuid " + "FROM tag t, tagxref tx, blob b " + "WHERE (t.tagid=%d) AND (t.tagid=tx.tagid) AND (tx.srcid=b.rid) " + "ORDER BY tx.mtime DESC", + tagid); + db_prepare( &st, sql ); + free( sql ); + @ <h2>Tag ID %d(tagid):</h2> + @ <table cellpadding='4px' border='1'><tbody> + @ <tr><th>Tag name</th><th>Timestamp</th><th>Version</th></tr> + while( SQLITE_ROW == db_step(&st) ) + { + char const * tagname = db_column_text( &st, 0 ); + char const * tagtime = db_column_text( &st, 1 ); + char const * uuid = db_column_text( &st, 2 ); + const int offset = 10; + char shortname[offset+1]; + shortname[offset] = '\0'; + memcpy( shortname, uuid, offset ); + @ <tr> + @ <td><tt><a href='%s(g.zBaseURL)/tagview/%q(tagname)'>%s(tagname)</a></tt></td> + @ <td align='center'><tt>%s(tagtime)</tt></td> + @ <td><tt> + @ <a href='%s(g.zBaseURL)/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a> + @ </tt></td></tr> + } + @ </tbody></table> + db_finalize( &st ); +} + +static void tagview_page_tag_by_name( char const * tagname ) +{ + Stmt st; + char * sql = mprintf( + "SELECT DISTINCT t.tagid, DATETIME(tx.mtime), b.uuid " + "FROM tag t, tagxref tx, blob b " + "WHERE (t.tagname='%q') AND (t.tagid=tx.tagid) AND (tx.srcid=b.rid) " + "ORDER BY tx.mtime DESC", + tagname); + db_prepare( &st, sql ); + free( sql ); + @ <h2>Tag '%s(tagname)':</h2> + @ <table cellpadding='4px' border='1'><tbody> + @ <tr><th>Tag ID</th><th>Timestamp</th><th>Version</th></tr> + while( SQLITE_ROW == db_step(&st) ) + { + int tagid = db_column_int( &st, 0 ); + char const * tagtime = db_column_text( &st, 1 ); + char const * uuid = db_column_text( &st, 2 ); + const int offset = 10; + char shortname[offset+1]; + shortname[offset] = '\0'; + memcpy( shortname, uuid, offset ); + @ <tr> + @ <td><tt><a href='%s(g.zBaseURL)/tagview?tagid=%d(tagid)'>%d(tagid)</a></tt></td> + @ <td align='center'><tt>%s(tagtime)</tt></td> + @ <td><tt> + @ <a href='%s(g.zBaseURL)/vinfo/%s(uuid)'><strong>%s(shortname)</strong>%s(uuid+offset)</a> + @ </tt></td></tr> + } + @ </tbody></table> + db_finalize( &st ); } + +/* +** WEBPAGE: /tagview +*/ +void tagview_page(void){ + + login_check_credentials(); + if( !g.okSetup ){ + login_needed(); + } + style_header("Tags"); + tagview_page_search_miniform(); + @ <hr/> + char const * check = 0; + if( 0 != (check = P("tagid")) ) + { + tagview_page_tag_by_id( atoi(check) ); + } + else if( 0 != (check = P("like")) ) + { + tagview_page_list_tags( check ); + } + else if( 0 != (check = P("name")) ) + { + tagview_page_tag_by_name( check ); + } + else + { + tagview_page_default(); + } + style_footer(); +}