[PATCH v3 1/2] fc: Add support for comparing files with default options.

[Hans Leidekker]

From: Hans Leidekker

---
 programs/fc/fc.c | 374 ++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 370 insertions(+), 4 deletions(-)

diff --git a/programs/fc/fc.c b/programs/fc/fc.c
index 84ce886b9a2..2bc9111cf9e 100644
--- a/programs/fc/fc.c
+++ b/programs/fc/fc.c
@@ -1,5 +1,6 @@
 /*
  * Copyright 2018 Fabian Maurer
+ * Copyright 2024 Hans Leidekker for CodeWeavers
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -16,18 +17,383 @@
  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  */

+#include <stdarg.h>
+#include <unistd.h>
+
+#include <windef.h>
+#include <winbase.h>
+#include <winnls.h>
+#include <consoleapi.h>
+
 #include "wine/debug.h"
+#include "wine/list.h"

WINE_DEFAULT_DEBUG_CHANNEL(fc);

+enum section_type
+{
+    SECTION_TYPE_COPY,
+    SECTION_TYPE_DELETE,
+    SECTION_TYPE_INSERT
+};
+
+struct section
+{
+    struct list entry;
+    enum section_type type;
+    unsigned int start;     /* index in line array */
+    unsigned int len;       /* number of lines */
+};
+static struct list sections = LIST_INIT( sections );
+
+struct common_subseq
+{
+    unsigned int pos_first;  /* position in first file */
+    unsigned int pos_second;
+    unsigned int len;
+};
+
+struct line
+{
+    const char  *start;
+    unsigned int len;
+};
+
+struct lines
+{
+    unsigned int count;
+    unsigned int capacity;
+    struct line *entry;
+};
+static struct lines lines1, lines2;
+
+static void append_line( struct lines *lines, const char *start, unsigned int len )
+{
+    if (lines->count >= lines->capacity)
+    {
+        lines->capacity = max( 128, lines->capacity * 2 );
+        lines->entry = realloc( lines->entry, lines->capacity * sizeof(*lines->entry) );
+    }
+    lines->entry[lines->count].start = start;
+    lines->entry[lines->count].len = len;
+    lines->count++;
+}
+
+static void split_lines( struct lines *lines, const char *data, unsigned int len )
+{
+    const char *p = data, *q = data;
+
+    while (len)
+    {
+        if (p[0] == '\n' || (p[0] == '\r' && p[1] == '\n'))
+        {
+            append_line( lines, q, p - q );
+            if (p[0] == '\r') { p++; len--; }
+            q = p + 1;
+        }
+        p++; len--;
+    }
+    if (p != q) append_line( lines, q, p - q );
+}
+
+static char *data1, *data2;
+static unsigned int len_data1, len_data2;
+
+static int equal_lines( const struct line *line1, const struct line *line2 )
+{
+    if (line1->len != line2->len) return 0;
+    return !memcmp( line1->start, line2->start, line1->len );
+}
+
+/* return the number of equal lines at given ranges */
+static unsigned int common_length( unsigned int first_pos, unsigned int first_end,
+                                   unsigned int second_pos, unsigned int second_end )
+{
+    unsigned int len = 0;
+
+    while (first_pos < first_end && second_pos < second_end)
+    {
+        if (!equal_lines( &lines1.entry[first_pos++], &lines2.entry[second_pos++] )) break;
+        len++;
+    }
+    return len;
+}
+
+/* return the longest sequence of equal lines between given ranges */
+static int longest_common_subsequence( unsigned int first_start, unsigned int first_end,
+                                       unsigned int second_start, unsigned int second_end,
+                                       struct common_subseq *result )
+{
+    unsigned int i, j;
+    int ret = 0;
+
+    memset( result, 0, sizeof(*result) );
+
+    for (i = first_start; i < first_end; i++)
+    {
+        for (j = second_start; j < second_end; j++)
+        {
+            unsigned int len = common_length( i, first_end, j, second_end );
+            if (len > result->len)
+            {
+                result->len = len;
+                result->pos_first = i;
+                result->pos_second = j;
+                ret = 1;
+            }
+        }
+    }
+    return ret;
+}
+
+static struct section *alloc_section( enum section_type type, unsigned int start, unsigned int len )
+{
+    struct section *ret = malloc( sizeof(*ret) );
+
+    ret->type = type;
+    ret->start = start;
+    ret->len = len;
+    return ret;
+}
+
+static unsigned int non_matching_lines;
+
+static void diff( unsigned int first_start, unsigned int first_end,
+                  unsigned int second_start, unsigned int second_end )
+{
+    struct common_subseq subseq;
+    struct section *section;
+
+    if (longest_common_subsequence( first_start, first_end, second_start, second_end, &subseq ))
+    {
+        /* recursively find sections before this one */
+        diff( first_start, subseq.pos_first, second_start, subseq.pos_second );
+
+        section = alloc_section( SECTION_TYPE_COPY, subseq.pos_first, subseq.len );
+        list_add_tail( &sections, &section->entry );
+
+        /* recursively find sections after this one */
+        diff( subseq.pos_first + subseq.len, first_end, subseq.pos_second + subseq.len, second_end );
+        return;
+    }
+
+    if (first_start < first_end)
+    {
+        section = alloc_section( SECTION_TYPE_DELETE, first_start, first_end - first_start );
+        list_add_tail( &sections, &section->entry );
+        non_matching_lines++;
+    }
+
+    if (second_start < second_end)
+    {
+        section = alloc_section( SECTION_TYPE_INSERT, second_start, second_end - second_start );
+        list_add_tail( &sections, &section->entry );
+        non_matching_lines++;
+    }
+}
+
+static struct section *find_context_before( struct section *section )
+{
+    struct section *cursor = section;
+
+    while ((cursor = LIST_ENTRY( list_prev(&sections, &cursor->entry), struct section, entry )))
+    {
+        if (cursor->type == SECTION_TYPE_COPY) return cursor;
+    }
+    return NULL;
+}
+
+static struct section *find_context_after( struct section *section )
+{
+    struct section *cursor = section;
+
+    while ((cursor = LIST_ENTRY( list_next(&sections, &cursor->entry), struct section, entry )))
+    {
+        if (cursor->type == SECTION_TYPE_COPY) return cursor;
+    }
+    return NULL;
+}
+
+static void output_stringW( const WCHAR *str, int len )
+{
+    DWORD count;
+    int lenA;
+    char *strA;
+
+    if (len < 0) len = wcslen( str );
+    if (WriteConsoleW( GetStdHandle(STD_OUTPUT_HANDLE), str, len, &count, NULL )) return;
+
+    lenA = WideCharToMultiByte( GetOEMCP(), 0, str, len, NULL, 0, NULL, NULL );
+    if ((strA = malloc( lenA )))
+    {
+        WideCharToMultiByte( GetOEMCP(), 0, str, len, strA, lenA, NULL, NULL );
+        WriteFile( GetStdHandle(STD_OUTPUT_HANDLE), strA, lenA, &count, FALSE );
+        free( strA );
+    }
+}
+
+static void output_stringA( const char *str, int len )
+{
+    DWORD count;
+
+    if (len < 0) len = strlen( str );
+    if (WriteConsoleA( GetStdHandle(STD_OUTPUT_HANDLE), str, len, &count, NULL )) return;
+    WriteFile( GetStdHandle(STD_OUTPUT_HANDLE), str, len, &count, FALSE );
+}
+
+static void output_header( const WCHAR *filename )
+{
+    output_stringW( L"***** ", 6 );
+    output_stringW( filename, -1 );
+    output_stringW( L"\r\n", 2 );
+}
+
+static void output_line( const struct lines *lines, unsigned int index )
+{
+    output_stringA( lines->entry[index].start, lines->entry[index].len );
+    output_stringA( "\r\n", 2 );
+}
+
+static void output_context( unsigned int line )
+{
+    if (lines1.count < 2 || lines2.count < 2) return;
+    output_line( &lines1, line );
+}
+
+static char no_data[] = "";
+
+static char *map_file( HANDLE handle, unsigned int *size )
+{
+    HANDLE mapping;
+    char *ret;
+
+    if (!(*size = GetFileSize( handle, NULL ))) return no_data;
+    if (!(mapping = CreateFileMappingW( handle, NULL, PAGE_READONLY, 0, 0, NULL ))) return NULL;
+    ret = MapViewOfFile( mapping, FILE_MAP_READ, 0, 0, 0 );
+    CloseHandle( mapping );
+    return ret;
+}
+
+static int compare_files( const WCHAR *filename1, const WCHAR *filename2 )
+{
+    HANDLE handle1, handle2;
+    struct section *section;
+    unsigned int i;
+    int ret = 2;
+
+    handle1 = CreateFileW( filename1, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL );
+    if (handle1 == INVALID_HANDLE_VALUE) return 2;
+
+    handle2 = CreateFileW( filename2, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL );
+    if (handle2 == INVALID_HANDLE_VALUE)
+    {
+        CloseHandle( handle2 );
+        return 2;
+    }
+
+    if (!(data1 = map_file( handle1, &len_data1 ))) goto done;
+    if (!(data2 = map_file( handle2, &len_data2 ))) goto done;
+
+    split_lines( &lines1, data1, len_data1 );
+    split_lines( &lines2, data2, len_data2 );
+
+    diff( 0, lines1.count, 0, lines2.count );
+
+    output_stringW( L"Comparing files ", 16 );
+    output_stringW( filename1, -1 );
+    output_stringW( L" and ", 5 );
+    output_stringW( filename2, -1 );
+    output_stringW( L"\r\n", 2 );
+
+    if (!non_matching_lines)
+    {
+        output_stringW( L"FC: no differences encountered\r\n\r\n", -1 );
+        ret = 0;
+        goto done;
+    }
+
+    LIST_FOR_EACH_ENTRY( section, &sections, struct section, entry )
+    {
+        struct section *ctx_before = find_context_before( section ), *ctx_after = find_context_after( section );
+
+        if (section->type == SECTION_TYPE_DELETE)
+        {
+            struct section *next_section = LIST_ENTRY( list_next(&sections, &section->entry), struct section, entry );
+
+            output_header( filename1 );
+            if (ctx_before) output_context( ctx_before->start + ctx_before->len - 1 );
+            for (i = 0; i < section->len; i++) output_line( &lines1, section->start + i );
+            if (ctx_after) output_context( ctx_after->start );
+
+            if (next_section && next_section->type != SECTION_TYPE_INSERT)
+            {
+                output_header( filename2 );
+                if (ctx_before) output_context( ctx_before->start + ctx_before->len - 1 );
+                if (ctx_after) output_context( ctx_after->start );
+            }
+            else if (!next_section)
+            {
+                output_header( filename2 );
+                output_stringW( L"*****\r\n\r\n", 9 );
+            }
+        }
+        else if (section->type == SECTION_TYPE_INSERT)
+        {
+            struct section *prev_section = LIST_ENTRY( list_prev(&sections, &section->entry), struct section, entry );
+
+            if (prev_section && prev_section->type != SECTION_TYPE_DELETE)
+            {
+                output_header( filename1 );
+                if (ctx_before) output_context( ctx_before->start + ctx_before->len - 1 );
+                if (ctx_after) output_context( ctx_after->start );
+            }
+            else if (!prev_section) output_header( filename1 );
+
+            output_header( filename2 );
+            if (ctx_before) output_context( ctx_before->start + ctx_before->len - 1 );
+            for (i = 0; i < section->len; i++) output_line( &lines2, section->start + i );
+            if (ctx_after) output_context( ctx_after->start );
+            output_stringW( L"*****\r\n\r\n", 9 );
+        }
+    }
+
+    ret = 1;
+
+done:
+    if (data1 != no_data) UnmapViewOfFile( data1 );
+    if (data2 != no_data) UnmapViewOfFile( data2 );
+    CloseHandle( handle1 );
+    CloseHandle( handle2 );
+    return ret;
+}
+
 int __cdecl wmain(int argc, WCHAR *argv[])
 {
+    BOOL option = FALSE;
     int i;

-    WINE_FIXME("stub:");
     for (i = 0; i < argc; i++)
-        WINE_FIXME(" %s", wine_dbgstr_w(argv[i]));
-    WINE_FIXME("\n");
+    {
+        if (argv[i][0] == '/') option = TRUE;
+    }
+
+    if (option)
+    {
+        FIXME( "options not supported\n" );
+        return 2;
+    }
+
+    if (argc != 3)
+    {
+        wprintf( L"FC: Wrong number of files\n" );
+        return 2;
+    }
+
+    if (wcschr( argv[1], '?' ) || wcschr( argv[1], '*' ) || wcschr( argv[2], '?' ) || wcschr( argv[2], '*' ))
+    {
+        FIXME( "wildcards not supported\n" );
+        return 2;
+    }

-    return 0;
+    return compare_files( argv[1], argv[2] );
 }