Desired application: vidir

[skeeto]

vidir is surprisingly useful, and it would be nice to have. Maybe some weekend I'll whip one up, but I haven't started it and don't plan to soon. So I'm opening it up to anyone who would like to take a shot. Since this command is optional and low importance, acceptance is exacting, i.e. I can afford to be picky. "Must" means required and "should" means optional.

• Must support Windows XP. (Note: This rules out a UTF-8 manifest.)

• Must support wide (Unicode) and long (> MAX_PATH) paths. The editor gets UTF-8-encoded paths. It must refuse to operate if it sees a path that cannot be represented as UTF-8. (I don't expect editors to handle WTF-8.)

• Must not link MSVCRT (e.g. cc -nostartfiles -o vidir vidir.c -lmemory).

• Must be a single source file, like vidir.c. C++ is acceptable, but mind the previous item.

• Must be dedicated to the public domain. Still put your name in it and take credit of course.

• Error messages must print correctly on the console, i.e. messages indicating paths.

There's a question for how to handle $EDITOR. In the original vidir it's sort of treated like a shell script fragment, except it doesn't use a real shell, and instead naively splits on spaces — almost the least useful behavior possible. You could perhaps pass it to busybox.exe sh, or maybe just pass it through as a Win32 command string fragment and let the other side parse it. I don't think there's a right answer, so consider the trade-offs. Compatibility with the original isn't important here.

[Peter0x44]

I decided to try using github copilot for this with claude sonnet 4 and it did actually spit something out which worked and meets the requirements at a basic scrutiny level. I don't think packaging it is a good idea, but I will attach it here in case anyone else is curious. The results were certainly better than I expected!

Full disclosure: I wrote none of this code.

vidir_ai.c.txt

[skeeto]

Interesting results, and better than expected as well. This is the start of something that would be acceptable. The Good: * Figured out wide paths, without a CRT, and without falling into the old TCHAR trap. Forbidding a CRT probably helped with the last part. * Overall it basically works, and even correctly handles swaps. It solves it slightly differently than I would/did, but it's right. The Bad: * It *really* wants to write a BOM, even though it's inconvenient. I'd just delete that part. * No error checks on WriteFile. Buffered output wasn't even attempted, which would trivially solve the error checking. * No handling for batch files. This is especially important for w64dk, where vim.bat, not notepad, should be the default. This would be a good reason to switch {g,}vim.bat over to command aliases. The LLM could not have possibly known any of this, so that's not its fault. * Swap handling is quadratic. This could be resolved easily with a hash table — a dozen lines of code (hash trie), but I expect no LLM currently knows how to do this well. Asking it not to use libc is already straining its capabilities. * Mingles Win32 calls and business logic, making testing and porting substantially more difficult. I'd prefer to parse the entire list, then create an action plan, then execute that plan. A dry run would print out this plan instead of executing. A test would validate the plan and never execute it, or execute it on a virtual file system. * It seems to have been confused by "must print correctly on the console" and does a silly WideCharToMultiByte followed by WriteConsoleA (!), which is exactly wrong. That instruction is about correctly displaying paths in error messages, which means carefully using WriteConsoleW to print paths (instead of WriteFile) *if* standard error is a console, which it might not be. * Missing some integer overflows checks. The Ugly (a slave to the awful, old C paradigms): * Implementing a mini libc, including sprintf, misses the point of not using it. Don't copy all those bad ideas. My experience has been LLMs simply cannot write C without something like libc. Virtually all training data is written in a libc-heavy style, and without libc it's like a new language for which it has no training, but which it can handle by turning it back into traditional C. * Null terminated strings everywhere for no reason. Ugh. * Reading a byte at a time instead of just slurping all the input. It's not a matter of using buffered input. It must all fit in memory anyway, so it doesn't need to be streamed in a line at a time into a fixed line buffer like a crummy fgets. (LLMs are currently poor at these kinds of bigger picture engineering trade-offs.) * A bad case of C programmer's disease (e.g. char line[32768]). Again, that's probably the only way LLMs know how to work. Long paths isn't just about using 1<<15 instead of MAX_PATH. * Lots of finicky general purpose allocation for no reason. This program's memory allocation needs are trivial. * Meticulously freeing memory before exit. Admittedly, for LLMs this is damned if you do, damned if you don't. LLMs have essentially been trained to write poor C because that's what users want and expect. If an LLM didn't pointlessly free, users would complain because they themselves don't know any better. In my experience, when given special instructions not to do this they all do it anyway. It's just too ingrained in the training. Ultimately this can be fixed quickly by hand, but it's annoying.

[Peter0x44]

I've decided to have a go at this in some spare time and I have some progress, but nothing worth sharing yet.
I'd like to ask for clarification on what exactly the Must support ... long (> MAX_PATH) paths. imples. Is it related to this setting in the registry?
https://learn.microsoft.com/en-us/windows/win32/fileio/maximum-file-path-limitation?tabs=registry#enable-long-paths-in-windows-10-version-1607-and-later

As far as I can tell this requires a manifest. Which I guess, as long as it is "linked" in optionally, should be okay. Windows XP is unlikely to be able to support this.

[skeeto]

That requirement is more about forcing a better design than an expectation that users actually need long paths in practice. It requires processing paths dynamically instead of mindlessly allocating MAX_PATH on the stack and manipulating a tiny array. (If you're working in UTF-8, it's actually something like MAX_PATH*3.) This didn't work with the AI version, which just used 32767 in place of MAX_PATH instead of going the dynamic route as I intended. Note on the linked page it says "32,767 is an approximate" so even hard coding that isn't quite right either. The registry and manifest thing I think it just about using these paths without a "\\?\" prefix. With the prefix you definitely can access long paths from any program. Here's something you can try yourself on Windows 10 or 11. First, a subst just so we can create an arbitrary absolute path without stomping on a real drive: $ mkdir test $ subst t: test It's a running theme that so many programs, including some of Windows itself, cannot handle long paths, which complicates testing. That includes busybox-w32 applets. So we'll use cmd.exe mkdir because busybox-w32 mkdir can't do it: $ LONG="$(printf '\\\\?\\T:\\%0250d\\%0250d' 0 0)" $ cmd /c mkdir "$LONG" Note that even for long paths, path segments are still limited to MAX_PATH (260 wchar_t), so here we have two segments of length 250, to form a path of length 504 with the drive, or 508 with the long prefix. Next use xxd to create a file in this long directory: $ echo hello | xxd - "$LONG\\hello" A few busybox-w32 applets can manage this, too. I'm unsure why. (Passes through argv[n] unchanged?) But do I know for sure rexxd can do it. So now we have a small text file of total path length 514. Note how you cannot open it in Vim, but it does work with cat and notepad, so you can inspect it with those. This all works without that registry entry or the manifest. So ultimately I expect this to (basically) work, too: $ vidir "$LONG" Internally vidir would dutifully pass this string to the various Win32 functions, appending whatever else to the end, never caring particularly about its length (MAX_PATH, 32,767, or otherwise). It doesn't need to be aware of long paths, just not limit itself. (Caveat: I just noticed that I must use backslash delimiters, because \\?\ paths don't work with slashes. Since I'm really aiming for the better core design side effects of this feature, don't worry about this detail.)

[Peter0x44]

Notepad has heuristics to guess the encoding, and it gets that wrong sometimes.
https://en.wikipedia.org/wiki/Bush_hid_the_facts

This problem is what the utf-8 BOM solves. Visual studio code also has this annoying behavior.
In a sane world with sane tools, it wouldn't be needed, but I think the benefits are worth it, despite being inconvenient.

On another note, the BOM actually breaks some things... I had to help someone once who had opengl shaders that wouldn't compile because the shaders had a utf-8 bom.

[skeeto]

That's a good point. Particularly on Windows where Encodings are more varied. Without a BOM even Vim will default to the system code page, typically latin1. (I should probably change this in Vim anyway. See ff695fc.) Since I expect w64devkit.ini to often, if not usually, to be opened in Notepad to manipulate before running w64dk, perhaps it should have a BOM, too, along with BOM handling in the w64devkit.c INI parser. Something to consider. I think it's funny vscode prefers UTF-8 while VS sticks to classic Windows code page stuff (probably out of compatibility). When users of these two Microsoft products collaborate in the most straightforward way, they stomp over each other's encodings, producing confusing errors, as the errors are themselves mojibaked. I've seen it happen on multiple, separate occasions, and I bet it affects thousands of people every day.

[Peter0x44]

• Swap handling is quadratic. This could be resolved easily with a hash
  table — a dozen lines of code (hash trie), but I expect no LLM currently
  knows how to do this well. Asking it not to use libc is already straining
  its capabilities.

I paid attention to this comment, and I noticed that the original perl moreutils also seems to have this same quadratic problem.
https://github.com/pgdr/moreutils/blob/e9a53e8922fbebe825f74ffbe309d4e57d6b09d5/vidir#L182-L186

I'm not sure exactly what you meant, so I figured it was a path string -> line number hash trie.
However, that causes a few problems, for one renaming directories still has to keep track of the names of the contents in the path map, and with the hash trie, the only way I could think to change the path to insert a freshly allocated entry with the updated path, but that would effectively leak the old path's entry, not ideal..
It also doesn't really help with the swap handling, where we are effectively asking "What line number has path X", but we also need to frequently ask "What was the original path for line Y".

How would you handle this? Two hash maps for both directions? It feels like the hash trie possibly isn't the correct data structure, but I don't know which would be more appropriate.

[skeeto]

Hmmm, it's been a long time with Perl, but it seems it's quadratic on the number of collisions? This seems to excite the worst case: $ pushd /tmp/$$ $ seq 10000 | xargs touch $ EDITOR='sed -i s#/.*#/x#' vidir That takes my system around ~40 seconds while pegging a CPU core despite only 10k files, and I gave up trying to time 100k files. (It was still going as I finished writing this message.) That's the sort of thing I want to avoid.

I'm not sure exactly what you meant, so I figured it was a path string -> line number hash trie.

So the AI code had this: for (int j = 0; j < count; j++) { if (wstr_cmp(files[j], new_name) == 0) { mem_free(files[j]); files[j] = wstr_dup(temp_name); } } Which is a linear scan over the file list searching for new_name. This is inside the outer loop going over each line, hence quadratic. (I mean, I'm pretty sure. This code is so deeply nested it's difficult to follow.) Any such linear scan could be reduced to a map lookup. You can have multiple such maps if you need to index over different properties, the same way in SQL you might have different indexes over different columns. If you need a multi-map, probably use a linked list for the "value" part. (And of course in your version you don't need any of that free/dup string handling crap when updating the entry.)

the only way I could think to change the path to insert a freshly allocated entry with the updated path - not ideal.

That's seems fine to me. Don't sweat having some extra hash trie nodes and some "dead" nodes. It should still ultimately be O(n) trie nodes.

We also need to frequently ask "What was the original path for line Y".

Sounds like that's just another map! In my criticism I said the AI "mingles Win32 calls and business logic" because I didn't like that it called file_exists() while working out its renames. The part processing the renames shouldn't care about the current state of the file system. It's pure, abstract bookkeeping problem. Its job is to work out the sequence of actions to achieve the result, assuming the original files all still exist (otherwise there's racing, and all bets are off). The part executing the produced plan is the part that's concerned with creating directories that don't yet exist, etc. I mention this just in case you think you need to do file system queries at this step. For temp files, the plan uses a placeholder dummy name that the executor fills in with a guaranteed non-existing temp file name. I believe only a single temp file is ever necessary. So for example, if the input is this: 1 a 2 b 3 c 4 d 5 e And the output is this: 1 b 2 c 3 a 4 x The computed plan might be: mv c $TMP mv b c mv a b mv $TMP a mv d x rm e When scanning the output, it starts by loading them all in a map. Then it starts at the top, sees the rename to "b", and consults the map. Oh, a collision, so that must be processed first (i.e. a dependency). That one has a collision, too. So you're building up a dependency graph. When there are loops, like this case, you need a temp file to break the loop.

[Peter0x44]

That's seems fine to me. Don't sweat having some extra hash trie nodes and
some "dead" nodes. It should still ultimately be O(n) trie nodes.

I think it could imply some badness if multiple directories are getting renamed, or a directory with many files within. all paths in a subdirectory need to be updated first before they get processed.

But anyway I should probably stop worrying and just publish it. It's 90% there and I'm sure it will be easier to iron out problems with a review.

[Peter0x44]

https://github.com/Peter0x44/vidir-c-portable
I got around to pushing it up. Let me know what you think (perhaps open issues there if there are any).
Should be functional, with possibly some architectural problems.

[skeeto]

Thanks! It's going to take some time to go through this thoroughly, and my first comments are going to be on the simpler stuff. I'm not going to get to everything at once, so the comments will be spread over time.

It seems you've used u-config as a guide, which is generally good, but has the unfortunate effect that I was still discovering these techniques for myself at the time I wrote it. I've found better ways to accomplish since. I'll comment on these things.

In some cases it will be easiest if I just comment directly on the source in your repository. Though I'll start here with a test that doesn't work:

#!/bin/sh
set -ex
rm -rf test/
mkdir test/
echo a >test/a
echo b >test/b
echo c >test/c
printf 'cat -- "$1" && tr abc bca <"$1" | tee tmp && mv tmp "$1"' >editor.sh
EDITOR=./editor.sh ./vidir test
tail test/*

This sets up a rename loop which fails because the final rename uses a file named /. I didn't dig into why, just noticed it during my initial testing.

---

Regarding zero-initialization, I notice your alloc doesn't, which seems like an intentional break from how I do things. Perhaps my arguments about code simplicity are unconvincing, and you're concerned about efficiency? This actually demonstrates an excellent point: The uninitialized form of hash tries in particular is observably less efficient this way! So because new/alloc doesn't initialize, it must be done manually after allocation:

    *m = new(perm, pathmap, 1);
    (*m)->child[0] = 0;
    (*m)->child[1] = 0;
    (*m)->child[2] = 0;
    (*m)->child[3] = 0;
    (*m)->key = key;
    (*m)->path = (s8){0}; // Initialize to empty

The problem is that there's potential aliasing between (*m)->child, etc., and *m itself. GCC and Clang treat all pointers as compatible regarding strict aliasing, so it doesn't matter they point to different types. (And compilers without aliasing analysis don't have a prayer.) Every store to child[N] potentially invalidates m, creating false dependencies between each store, preventing an efficient, wide SIMD zeroing. This is particularly troublesome in the presence of custom allocators, because unlike malloc and friends, the compiler doesn't understand the semantics, so it's paralyzed by fears of aliasing. (There are GNU function attributes for this, but not only will they not work here, they're dangerously broken in this situation and must not be used.)

Storing all fields simultaneously avoids this:

    *m = new(perm, pathmap, 1);
    **m = (Map){};

But not so fast! This kind of compound literal assignment is just another way to spell memset. Examine the generated code (i.e. at a sufficiently high optimization level) and it's practically the same as zero-initialized allocation. Remember this is a unity build. alloc is static and small. It's going to be inlined into this function. size and count fold into the function body as constants, memset evaporates into the same fixed, wide zero store as that compound literal, and the allocator melts away. So zero-initialization already produced exactly what we wanted, with simpler code, without having to think about it. Here's an isolated case to see for yourself:

#include <stddef.h>
#include <stdint.h>

#define assert(c)       while (!(c)) unreachable()
#define new(a, n, t)    (t *)alloc(a, n, sizeof(t), _Alignof(t))

typedef ptrdiff_t iz;
typedef size_t    uz;
typedef uint64_t  u64;

typedef struct { char *beg, *end; } Arena;

static void *alloc(Arena *a, iz count, iz size, iz align)
{
    iz pad = (iz)-(uz)a->beg & (align - 1);
    assert(count < (a->end - a->beg - pad)/size);
    void *r = a->beg + pad;
    a->beg += pad + count*size;
    #if UNINIT
    return r;
    #else
    return __builtin_memset(r, 0, count*size);
    #endif
}

typedef struct Map Map;
struct Map {
    Map *child[4];
    uz   key;
    uz   value;
};

u64 hash(uz);

uz *upsert(Map **m, uz key, Arena *a)
{
    for (u64 h = hash(key); *m; h <<= 2) {
        if (key == (*m)->key) {
            return &(*m)->value;
        }
        m = &(*m)->child[h>>62];
    }
    *m = new(a, 1, Map);
    (*m)->key = key;
    #if UNINIT
    #  if BYLITERAL
       **m = (Map){};
    #  else
       (*m)->child[0] = 0;
       (*m)->child[1] = 0;
       (*m)->child[2] = 0;
       (*m)->child[3] = 0;
       (*m)->value = 0;
    #  endif
    #endif
    return &(*m)->value;
}

With:

$ cc -S -O2                      -o zeroinit.s  demo.c
$ cc -S -O2 -DUNINIT             -o byfield.s   demo.c
$ cc -S -O2 -DUNINIT -DBYLITERAL -o byliteral.s demo.c

In particular look for movups.

[skeeto]

I hadn't yet discovered almighty string concatenation when I wrote u-config, and so I ended up with stuff like you've got here:

    i32 total_len = countof(L"busybox sh ") - 1 +  // "busybox sh " (exclude null)
                    countof(L"-c ") - 1 +          // "-c " (exclude null)
                    1 +                            // opening quote
                    editor.len +                   // editor name
                    1 +                            // space between editor and file
                    1 +                            // opening quote for tempfile
                    tempfile_len +                 // temp file path
                    1 +                            // closing quote for tempfile
                    1 +                            // closing quote for -c
                    1;                             // null terminator

Followed by a bunch of tedious copying. In this context, these + are unlikely to integer overflow and make a mess — an environment variable and a path — but wouldn't nice to write it in a way that this definitely couldn't happen? Enter s16concat:

s16 cmdline = {};
cmdline = s16concat(&scratch, cmdline, s16(L"busybox sh -c "));
cmdline = s16concat(&scratch, cmdline, s16(L"'"));
cmdline = s16concat(&scratch, cmdline, editor);
cmdline = s16concat(&scratch, cmdline, s16(L" \""));
cmdline = s16concat(&scratch, cmdline, tempfile);
cmdline = s16concat(&scratch, cmdline, s16(L"\"'\0"));

Bam! Done, including copying. No more fiddling with the length. Though on the other hand, the stuff between the quotes probably needs escaping, and some kind of "string builder" might be better for that.

[skeeto]

Regarding pathmap:

// Hash trie mapping line numbers to paths
typedef struct pathmap pathmap;
struct pathmap {
    pathmap *child[4];   // 4-way trie using bottom 2 bits of the key
    i32      key;
    s8       path;
};

// Insert or lookup a path by line number
static s8 *pathmap_insert(pathmap **m, i32 key, arena *perm);

C already comes with a built-in map type where the keys are densely-packed integers. It's called an array! A hash trie is the wrong data structure for this. However, it's great for the inverse: Keying on the path to find the original line number. That's what I was expecting to find.

But I don't see one. Curious. Looking further, it seems you're using the file system like a set. Sneaky! I hadn't anticipated that.

So here's the kind of shape I want to see:

// Parse the temporary file into a array of names. It's an error for a
// leading integer outside of [1, num_names]. Returns an array of exactly
// original_name_count items. Missing items (to be deleted) are null.
s8 *parse_temp_file(Arena *, s8, iz original_name_count);

typedef enum { 
    OP_DELETE,  // delete src (dst unused)
    OP_RENAME,  // clobbering move src to dst
    OP_STASH,   // rename src to the temp name (dst unused)
    OP_UNSTASH, // rename the temp name to dst (src unused)
} Op;

typedef struct {
    Op op;
    s8 src;
    s8 dst;
} Action;

typedef struct {
    Action *actions;
    iz      len;
} Plan;

// Produce a sequence of operations necessary to achieve the new name set.
Plan compute_plan(s8 *oldnames, s8 *newnames, s8 num_names, Arena *);

b32 execute_plan(Plan, Arena);

Where compute_plan does not talk to the operating system nor inspect the file system. It's purely working from the two lists. It doesn't matter if we're renaming a.txt to x/y/z.txt and have to create the intermediate directories. That's the plan executor's problem, which will be talking to the operating system, or just a facsimile if it's a test. I expect internally compute_plan constructs a temporary hash trie so it can efficiently answer questions like, "Does newname[i] correspond to an oldname?" in order to resolve dependencies, using OP_STASH to break loops as discussed.

If the new name corresponds to an existing file not in the old names, that's the executor's problem when it executes the plan. I didn't know it until now it does the ~ thing, and I was expecting it to either fail or clobber. Whatever the behavior, it's included in the OP_RENAME, and so it's not merely a rename(2)/MoveFileW.

So that example from before, would be represented as:

(Plan){
    .actions = {
        (Action){OP_STASH,   "c",  0 },
        (Action){OP_RENAME,  "b", "c"},
        (Action){OP_RENAME,  "a", "b"},
        (Action){OP_UNSTASH,  0 , "a"},
        (Action){OP_RENAME,  "d", "x"},
        (Action){OP_DELETE,  "e",  0 },
    },
    .len = 6,
}

That's created just from the inputs, and it can be tested and interrogated without touching any files. If the deletes are sorted to the end, up until that point we could potentially even "roll back" this plan (minus clobbering) if one of the operations fails in the middle. (Though of course that could fail too. File systems kind of suck…)