Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612/* * PROJECT: ReactOS FC Command * LICENSE: GPL-2.0-or-later (https://spdx.org/licenses/GPL-2.0-or-later) * PURPOSE: Comparing text files * COPYRIGHT: Copyright 2021 Katayama Hirofumi MZ (katayama.hirofumi.mz@gmail.com) */
#include "fc.h"
#define IS_SPACE(ch) ((ch) == TEXT(' ') || (ch) == TEXT('\t'))
#ifdef UNICODE #define NODE NODE_W #define PrintLine PrintLineW #define TextCompare TextCompareW#else #define NODE NODE_A #define PrintLine PrintLineA #define TextCompare TextCompareA#endif
static LPTSTR AllocLine(LPCTSTR pch, DWORD cch){ LPTSTR pszNew = malloc((cch + 1) * sizeof(TCHAR)); if (!pszNew) return NULL; memcpy(pszNew, pch, cch * sizeof(TCHAR)); pszNew[cch] = 0; return pszNew;}
static NODE *AllocNode(LPTSTR psz, DWORD lineno){ NODE *node; if (!psz) return NULL; node = calloc(1, sizeof(NODE)); if (!node) { free(psz); return NULL; } node->pszLine = psz; node->lineno = lineno; return node;}
static __inline VOID DeleteNode(NODE *node){ if (node) { free(node->pszLine); free(node->pszComp); free(node); }}
static VOID DeleteList(struct list *list){ struct list *ptr; NODE *node; while ((ptr = list_head(list)) != NULL) { list_remove(ptr); node = LIST_ENTRY(ptr, NODE, entry); DeleteNode(node); }}
static __inline LPCTSTR SkipSpace(LPCTSTR pch){ while (IS_SPACE(*pch)) ++pch; return pch;}
static __inline LPCTSTR FindLastNonSpace(LPCTSTR pch){ LPCTSTR pchLast = NULL; while (*pch) { if (!IS_SPACE(*pch)) pchLast = pch; ++pch; } return pchLast;}
static VOID DeleteDuplicateSpaces(LPTSTR psz){ LPTSTR pch0, pch1; for (pch0 = pch1 = psz; *pch0; ++pch0) { *pch1++ = *pch0; if (IS_SPACE(*pch0)) { do { ++pch0; } while (IS_SPACE(*pch0)); --pch0; } } *pch1 = 0;}
static LPTSTR CompressSpace(LPCTSTR line){ LPTSTR pszNew; LPCTSTR pchLast;
line = SkipSpace(line); pchLast = FindLastNonSpace(line); if (pchLast == NULL) return AllocLine(NULL, 0);
pszNew = AllocLine(line, (DWORD)(pchLast - line) + 1); if (!pszNew) return NULL;
DeleteDuplicateSpaces(pszNew); return pszNew;}
#define TAB_WIDTH 8
static INT ExpandTabLength(LPCTSTR line){ LPCTSTR pch; INT cch = 0; for (pch = line; *pch; ++pch) { if (*pch == TEXT('\t')) cch += TAB_WIDTH - (cch % TAB_WIDTH); else ++cch; } return cch;}
static LPTSTR ExpandTab(LPCTSTR line){ INT spaces, cch = ExpandTabLength(line), ich; LPTSTR pszNew = malloc((cch + 1) * sizeof(TCHAR)); LPCTSTR pch; if (!pszNew) return NULL; ich = 0; for (pch = line; *pch; ++pch) { if (*pch == TEXT('\t')) { spaces = TAB_WIDTH - (ich % TAB_WIDTH); while (spaces-- > 0) { pszNew[ich++] = TEXT(' '); } } else { pszNew[ich++] = *pch; } } pszNew[ich] = 0; return pszNew;}
#define HASH_EOF 0xFFFFFFFF#define HASH_MASK 0x7FFFFFFF
static DWORD GetHash(LPCTSTR psz, BOOL bIgnoreCase){ DWORD ret = 0xDEADFACE; while (*psz) { ret += (bIgnoreCase ? towupper(*psz) : *psz); ret <<= 2; ++psz; } return (ret & HASH_MASK);}
static NODE *AllocEOFNode(DWORD lineno){ NODE *node = AllocNode(AllocLine(NULL, 0), 0); if (node == NULL) return NULL; node->pszComp = AllocLine(NULL, 0); if (node->pszComp == NULL) { DeleteNode(node); return NULL; } node->lineno = lineno; node->hash = HASH_EOF; return node;}
static __inline BOOL IsEOFNode(NODE *node){ return !node || node->hash == HASH_EOF;}
static BOOL ConvertNode(const FILECOMPARE *pFC, NODE *node){ if (!(pFC->dwFlags & FLAG_T)) { LPTSTR tmp = ExpandTab(node->pszLine); if (!tmp) return FALSE; free(node->pszLine); node->pszLine = tmp; if (!(pFC->dwFlags & FLAG_W)) node->hash = GetHash(node->pszLine, !!(pFC->dwFlags & FLAG_C)); } if (pFC->dwFlags & FLAG_W) { node->pszComp = CompressSpace(node->pszLine); if (!node->pszComp) return FALSE; node->hash = GetHash(node->pszComp, !!(pFC->dwFlags & FLAG_C)); } return TRUE;}
static FCRET CompareNode(const FILECOMPARE *pFC, const NODE *node0, const NODE *node1){ DWORD dwCmpFlags; LPTSTR psz0, psz1; INT ret; if (node0->hash != node1->hash) return FCRET_DIFFERENT;
psz0 = (pFC->dwFlags & FLAG_W) ? node0->pszComp : node0->pszLine; psz1 = (pFC->dwFlags & FLAG_W) ? node1->pszComp : node1->pszLine; dwCmpFlags = ((pFC->dwFlags & FLAG_C) ? NORM_IGNORECASE : 0); ret = CompareString(LOCALE_USER_DEFAULT, dwCmpFlags, psz0, -1, psz1, -1); return (ret == CSTR_EQUAL) ? FCRET_IDENTICAL : FCRET_DIFFERENT;}
static BOOL FindNextLine(LPCTSTR pch, DWORD ich, DWORD cch, LPDWORD pich){ while (ich < cch) { if (pch[ich] == TEXT('\n') || pch[ich] == TEXT('\0')) { *pich = ich; return TRUE; } ++ich; } *pich = cch; return FALSE;}
static FCRETParseLines(const FILECOMPARE *pFC, HANDLE *phMapping, LARGE_INTEGER *pib, const LARGE_INTEGER *pcb, struct list *list){ DWORD lineno = 1, ich, cch, ichNext, cbView, cchNode; LPTSTR psz, pszLine; BOOL fLast, bCR; NODE *node;
if (*phMapping == NULL) return FCRET_NO_MORE_DATA;
if (pib->QuadPart >= pcb->QuadPart) { CloseHandle(*phMapping); *phMapping = NULL; return FCRET_NO_MORE_DATA; }
cbView = (DWORD)min(pcb->QuadPart - pib->QuadPart, MAX_VIEW_SIZE); psz = MapViewOfFile(*phMapping, FILE_MAP_READ, pib->HighPart, pib->LowPart, cbView); if (!psz) { return OutOfMemory(); }
ich = 0; cch = cbView / sizeof(TCHAR); fLast = (pib->QuadPart + cbView >= pcb->QuadPart); while (ich < cch && (FindNextLine(psz, ich, cch, &ichNext) || (ichNext == cch && (fLast || ich == 0)))) { bCR = (ichNext > 0) && (psz[ichNext - 1] == TEXT('\r')); cchNode = ichNext - ich - bCR; pszLine = AllocLine(&psz[ich], cchNode); node = AllocNode(pszLine, lineno++); if (!node || !ConvertNode(pFC, node)) { DeleteNode(node); UnmapViewOfFile(psz); return OutOfMemory(); } list_add_tail(list, &node->entry); ich = ichNext + 1; }
UnmapViewOfFile(psz);
pib->QuadPart += ichNext * sizeof(WCHAR);
if (pib->QuadPart < pcb->QuadPart) return FCRET_IDENTICAL;
// append EOF node node = AllocEOFNode(lineno); if (!node) return OutOfMemory(); list_add_tail(list, &node->entry);
return FCRET_NO_MORE_DATA;}
static VOIDShowDiff(FILECOMPARE *pFC, INT i, struct list *begin, struct list *end){ NODE* node; struct list *list = &pFC->list[i]; struct list *first = NULL, *last = NULL; PrintCaption(pFC->file[i]); if (begin && end && list_prev(list, begin)) begin = list_prev(list, begin); while (begin != end) { node = LIST_ENTRY(begin, NODE, entry); if (IsEOFNode(node)) break; if (!first) first = begin; last = begin; if (!(pFC->dwFlags & FLAG_A)) PrintLine(pFC, node->lineno, node->pszLine); begin = list_next(list, begin); } if ((pFC->dwFlags & FLAG_A) && first) { node = LIST_ENTRY(first, NODE, entry); PrintLine(pFC, node->lineno, node->pszLine); first = list_next(list, first); if (first != last) { if (list_next(list, first) == last) { node = LIST_ENTRY(first, NODE, entry); PrintLine(pFC, node->lineno, node->pszLine); } else { PrintDots(); } } node = LIST_ENTRY(last, NODE, entry); PrintLine(pFC, node->lineno, node->pszLine); }}
static VOIDSkipIdentical(FILECOMPARE *pFC, struct list **pptr0, struct list **pptr1){ struct list *ptr0 = *pptr0, *ptr1 = *pptr1; while (ptr0 && ptr1) { NODE *node0 = LIST_ENTRY(ptr0, NODE, entry); NODE *node1 = LIST_ENTRY(ptr1, NODE, entry); if (CompareNode(pFC, node0, node1) != FCRET_IDENTICAL) break; ptr0 = list_next(&pFC->list[0], ptr0); ptr1 = list_next(&pFC->list[1], ptr1); } *pptr0 = ptr0; *pptr1 = ptr1;}
static DWORDSkipIdenticalN(FILECOMPARE *pFC, struct list **pptr0, struct list **pptr1, DWORD nnnn, DWORD lineno0, DWORD lineno1){ struct list *ptr0 = *pptr0, *ptr1 = *pptr1; DWORD count = 0; while (ptr0 && ptr1) { NODE *node0 = LIST_ENTRY(ptr0, NODE, entry); NODE *node1 = LIST_ENTRY(ptr1, NODE, entry); if (node0->lineno >= lineno0) break; if (node1->lineno >= lineno1) break; if (CompareNode(pFC, node0, node1) != FCRET_IDENTICAL) break; ptr0 = list_next(&pFC->list[0], ptr0); ptr1 = list_next(&pFC->list[1], ptr1); ++count; if (count >= nnnn) break; } *pptr0 = ptr0; *pptr1 = ptr1; return count;}
static FCRETScanDiff(FILECOMPARE *pFC, struct list **pptr0, struct list **pptr1, DWORD lineno0, DWORD lineno1){ struct list *ptr0 = *pptr0, *ptr1 = *pptr1, *tmp0, *tmp1; NODE *node0, *node1; INT count; while (ptr0 && ptr1) { node0 = LIST_ENTRY(ptr0, NODE, entry); node1 = LIST_ENTRY(ptr1, NODE, entry); if (node0->lineno >= lineno0) return FCRET_DIFFERENT; if (node1->lineno >= lineno1) return FCRET_DIFFERENT; tmp0 = ptr0; tmp1 = ptr1; count = SkipIdenticalN(pFC, &tmp0, &tmp1, pFC->nnnn, lineno0, lineno1); if (count >= pFC->nnnn) break; if (count > 0) { ptr0 = tmp0; ptr1 = tmp1; } else { ptr0 = list_next(&pFC->list[0], ptr0); ptr1 = list_next(&pFC->list[1], ptr1); } } *pptr0 = ptr0; *pptr1 = ptr1; return FCRET_IDENTICAL;}
static FCRETResync(FILECOMPARE *pFC, struct list **pptr0, struct list **pptr1){ FCRET ret; struct list *ptr0, *ptr1, *save0 = NULL, *save1 = NULL; NODE *node0, *node1; struct list *list0 = &pFC->list[0], *list1 = &pFC->list[1]; DWORD lineno0, lineno1; INT penalty, i0, i1, min_penalty = MAXLONG;
node0 = LIST_ENTRY(*pptr0, NODE, entry); node1 = LIST_ENTRY(*pptr1, NODE, entry); lineno0 = node0->lineno + pFC->n; lineno1 = node1->lineno + pFC->n;
// ``If the files that you are comparing have more than pFC->n consecutive // differing lines, FC cancels the comparison,, // ``If the number of matching lines in the files is less than pFC->nnnn, // FC displays the matching lines as differences,, for (ptr1 = list_next(list1, *pptr1), i1 = 0; ptr1; ptr1 = list_next(list1, ptr1), ++i1) { node1 = LIST_ENTRY(ptr1, NODE, entry); if (node1->lineno >= lineno1) break; for (ptr0 = list_next(list0, *pptr0), i0 = 0; ptr0; ptr0 = list_next(list0, ptr0), ++i0) { node0 = LIST_ENTRY(ptr0, NODE, entry); if (node0->lineno >= lineno0) break; if (CompareNode(pFC, node0, node1) == FCRET_IDENTICAL) { penalty = min(i0, i1) + abs(i1 - i0); if (min_penalty > penalty) { min_penalty = penalty; save0 = ptr0; save1 = ptr1; } } } }
if (save0 && save1) { *pptr0 = save0; *pptr1 = save1; ret = ScanDiff(pFC, &save0, &save1, lineno0, lineno1); if (save0 && save1) { *pptr0 = save0; *pptr1 = save1; } return ret; }
for (ptr0 = *pptr0; ptr0; ptr0 = list_next(list0, ptr0)) { node0 = LIST_ENTRY(ptr0, NODE, entry); if (node0->lineno == lineno0) break; } for (ptr1 = *pptr1; ptr1; ptr1 = list_next(list1, ptr1)) { node1 = LIST_ENTRY(ptr1, NODE, entry); if (node1->lineno == lineno1) break; } *pptr0 = ptr0; *pptr1 = ptr1; return FCRET_DIFFERENT;}
static FCRETFinalize(FILECOMPARE* pFC, struct list *ptr0, struct list* ptr1, BOOL fDifferent){ if (!ptr0 && !ptr1) { if (fDifferent) return Different(pFC->file[0], pFC->file[1]); return NoDifference(); } else { ShowDiff(pFC, 0, ptr0, NULL); ShowDiff(pFC, 1, ptr1, NULL); PrintEndOfDiff(); return FCRET_DIFFERENT; }}
// FIXME: "cmd_apitest fc" has some failures.FCRET TextCompare(FILECOMPARE *pFC, HANDLE *phMapping0, const LARGE_INTEGER *pcb0, HANDLE *phMapping1, const LARGE_INTEGER *pcb1){ FCRET ret, ret0, ret1; struct list *ptr0, *ptr1, *save0, *save1, *next0, *next1; NODE* node0, * node1; BOOL fDifferent = FALSE; LARGE_INTEGER ib0 = { .QuadPart = 0 }, ib1 = { .QuadPart = 0 }; struct list *list0 = &pFC->list[0], *list1 = &pFC->list[1]; list_init(list0); list_init(list1);
do { ret0 = ParseLines(pFC, phMapping0, &ib0, pcb0, list0); if (ret0 == FCRET_INVALID) { ret = ret0; goto cleanup; } ret1 = ParseLines(pFC, phMapping1, &ib1, pcb1, list1); if (ret1 == FCRET_INVALID) { ret = ret1; goto cleanup; }
ptr0 = list_head(list0); ptr1 = list_head(list1); for (;;) { if (!ptr0 || !ptr1) goto quit;
// skip identical (sync'ed) SkipIdentical(pFC, &ptr0, &ptr1); if (ptr0 || ptr1) fDifferent = TRUE; node0 = LIST_ENTRY(ptr0, NODE, entry); node1 = LIST_ENTRY(ptr1, NODE, entry); if (IsEOFNode(node0) || IsEOFNode(node1)) goto quit;
// try to resync save0 = ptr0; save1 = ptr1; ret = Resync(pFC, &ptr0, &ptr1); if (ret == FCRET_INVALID) goto cleanup; if (ret == FCRET_DIFFERENT) { // resync failed ret = ResyncFailed(); // show the difference ShowDiff(pFC, 0, save0, ptr0); ShowDiff(pFC, 1, save1, ptr1); PrintEndOfDiff(); goto cleanup; }
// show the difference fDifferent = TRUE; next0 = ptr0 ? list_next(list0, ptr0) : ptr0; next1 = ptr1 ? list_next(list1, ptr1) : ptr1; ShowDiff(pFC, 0, save0, (next0 ? next0 : ptr0)); ShowDiff(pFC, 1, save1, (next1 ? next1 : ptr1)); PrintEndOfDiff();
// now resync'ed } } while (ret0 != FCRET_NO_MORE_DATA || ret1 != FCRET_NO_MORE_DATA);
quit: ret = Finalize(pFC, ptr0, ptr1, fDifferent);cleanup: DeleteList(list0); DeleteList(list1); return ret;}