~leon_plickat/nfm

nfm: [WIP] Rewrite tab completion v2 PROPOSED

Hugo Machet: 1
 [WIP] Rewrite tab completion

 4 files changed, 394 insertions(+), 107 deletions(-)
#915117 alpine.yml success
Export patchset (mbox)
How do I use this?

Copy & paste the following snippet into your terminal to import this patchset into git:

curl -s https://lists.sr.ht/~leon_plickat/nfm/patches/37892/mbox | git am -3
Learn more about email & git

[PATCH nfm v2] [WIP] Rewrite tab completion Export this patch

---
v1 -> v2
Just rebased against current master since there was some conflicts, to make it
easier for the review.

Also changes the few things noted in the first review.

And as said on IRC I moved as much code I could out mode.zig to Completion.zig.

 src/Completion.zig         | 146 +++++++++++++++++++++++++++++++++++++
 src/Context.zig            |  93 +----------------------
 src/EditableUTF8String.zig | 141 +++++++++++++++++++++++++++++++----
 src/mode.zig               | 121 ++++++++++++++++++++++++++++--
 4 files changed, 394 insertions(+), 107 deletions(-)
 create mode 100644 src/Completion.zig

diff --git a/src/Completion.zig b/src/Completion.zig
new file mode 100644
index 000000000000..b66132238c72
--- /dev/null
+++ b/src/Completion.zig
@@ -0,0 +1,146 @@
// This file is part of nfm, the neat file manager.
//
// Copyright © 2022 Hugo Machet
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License version 3 as published
// by the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.

const std = @import("std");
const ascii = std.ascii;
const debug = std.debug;
const fs = std.fs;
const heap = std.heap;
const mem = std.mem;
const unicode = std.unicode;
const log = std.log.scoped(.completion);

const Self = @This();

const Dir = @import("Dir.zig");
const File = @import("File.zig");

const context = &@import("nfm.zig").context;

pub const DirsList = struct {
    dirs: std.TailQueue(Dir) = .{},

    pub fn deinit(self: *DirsList) void {
        while (self.dirs.pop()) |node| {
            node.data.deinit();
            context.gpa.allocator().destroy(node);
        }
    }

    /// Add a new dir to DirsList.dirs if needed
    pub fn addDir(self: *DirsList, path: []const u8, fname: []const u8) !void {
        // TODO: More reliable way to compare them than using name?
        if (self.dirs.len > 0) {
            const last_name = fs.path.basename(self.dirs.last.?.data.name);
            if (mem.eql(u8, fname, last_name)) return;
        }

        const alloc = context.gpa.allocator();
        const abspath = try fs.path.join(alloc, &[_][]const u8{ path, "/", fname });
        errdefer alloc.free(abspath);
        log.debug("completion path: {s}", .{abspath});
        debug.assert(fs.path.isAbsolute(abspath));
        var dir = try fs.openIterableDirAbsolute(abspath, .{});
        defer dir.close();

        var node = try alloc.create(std.TailQueue(Dir).Node);
        try node.data.init(&context.dirmap, alloc, dir, abspath);
        self.dirs.append(node);
    }

    pub fn maybeRemoveLast(self: *DirsList) void {
        if (self.dirs.len == 0) return;
        const last = self.dirs.pop() orelse unreachable;
        last.data.deinit();
        context.gpa.allocator().destroy(last);
    }
};

arena: heap.ArenaAllocator,
completions: std.TailQueue(*File) = .{},
max_name_len: usize = 0,

/// Amount of codepoints in the compare token. Used for offsetting the menu.
compare_len: usize = 0,

pub fn newFromDir(dir: *Dir) !Self {
    var ret = Self{
        .arena = heap.ArenaAllocator.init(context.gpa.allocator()),
    };
    errdefer ret.arena.deinit();
    const alloc = ret.arena.allocator();
    for (dir.files.items) |*file| {
        const node = try alloc.create(std.TailQueue(*File).Node);
        node.data = file;
        ret.completions.append(node);
    }
    return ret;
}

pub fn deinit(self: *const Self) void {
    self.arena.deinit();
}

pub fn compare(self: *Self, str: []const u8) usize {
    var it = self.completions.first;
    while (it) |node| : (it = node.next) {
        if (!ascii.startsWithIgnoreCase(node.data.*.name, str)) {
            self.completions.remove(node);
        }
    }
    self.setMaxStringLen();

    return self.completions.len;
}

fn setMaxStringLen(self: *Self) void {
    var len: usize = 0;
    var it = self.completions.first;
    while (it) |node| : (it = node.next) {
        const l = unicode.utf8CountCodepoints(node.data.*.name) catch return;
        if (l > len) len = l;
    }
    self.max_name_len = len;
}

pub fn getFirst(self: *Self) ?*File {
    if (self.completions.len == 0) return null;
    return self.completions.first.?.data;
}

pub fn getCommonStart(self: *Self) ?[]const u8 {
    if (self.completions.len == 0) return null;

    var common: []const u8 = self.completions.first.?.data.name;
    var it = self.completions.first;
    while (it) |node| : (it = node.next) {
        common = commonStart(common, node.data.*.name);
    }
    return common;
}

/// Compare two strings and return the common beginning part.
/// Case insensitive.
fn commonStart(a: []const u8, b: []const u8) []const u8 {
    const len: usize = if (a.len < b.len) a.len else b.len;

    var offset: usize = 0;
    while (offset < len) : (offset += 1) {
        if (ascii.toLower(a[offset]) != ascii.toLower(b[offset])) break;
    }

    return a[0..offset];
}
diff --git a/src/Context.zig b/src/Context.zig
index 05a17f0758f7..a1fa7ac873f5 100644
--- a/src/Context.zig
+++ b/src/Context.zig
@@ -509,21 +509,17 @@ fn handleSpoonInputUserInput(self: *Self, in: spoon.Input) !void {
                try self.handleReturnUserInput();
                return;
            },
            '\t' => {
                var token = buffer.getCompletionToken() orelse return;
                if (try self.completion(token)) |compl| {
                    buffer.killCompletionToken();
                    try buffer.insertQuotedSliceAtCursor(compl);
                    defer self.gpa.allocator().free(compl);
                }
            },
            '\t' => try self.ui_mode.user_input.updateCompletion(.force),
            127 => { // Backspace.
                if (self.ui_mode.user_input.history_index != null) return;
                buffer.deleteOneBackward();
                self.ui_mode.user_input.maybeGoPrevCmpDir();
                try self.ui_mode.user_input.updateCompletion(.passive);
            },
            else => {
                if (self.ui_mode.user_input.history_index != null) return;
                try buffer.insertCodepointAtCursor(in.content.codepoint);
                try self.ui_mode.user_input.updateCompletion(.passive);
            },
        }
    }
@@ -695,84 +691,3 @@ fn mouseClickPathFromTitle(self: *Self, _x: usize) !void {
        }
    }
}

/// Compare current input with files/directories names. Complete the name if
/// there is only one match else only complete the common part.
/// Case insensitive.
fn completion(self: *Self, input: []const u8) !?[]const u8 {
    const alloc = self.gpa.allocator();

    var found: std.ArrayListUnmanaged(*File) = .{};
    defer found.deinit(alloc);

    const fdv = self.dirmap.focusedDirView() orelse return null;
    for (fdv.dir.files.items) |*file| {
        if (file.name.len <= input.len) continue;
        if (ascii.startsWithIgnoreCase(file.name, input)) {
            try found.append(alloc, file);
        }
    }

    if (found.items.len == 0) {
        self.completion_count = null;
        return null;
    } else if (found.items.len == 1) {
        self.completion_count = null;
        const escaped = try self.escapeSpecialChar(found.items[0].name);
        return escaped;
    } else {
        self.completion_count = found.items.len;
        var common: []const u8 = found.items[0].name;
        var i: usize = 1;
        while (i < found.items.len) : (i += 1) {
            common = commonStart(common, found.items[i].name);
        }
        const escaped = try self.escapeSpecialChar(common);
        return escaped;
    }
}

/// Compare two strings and return the common beginning part.
/// Case insensitive.
fn commonStart(a: []const u8, b: []const u8) []const u8 {
    const len: usize = if (a.len < b.len) a.len else b.len;

    var offset: usize = 0;
    while (offset < len) : (offset += 1) {
        if (ascii.toLower(a[offset]) != ascii.toLower(b[offset])) break;
    }

    return a[0..offset];
}

/// Escape special characters in file names.
///   foo bar -> foo\ bar
///   foo\ bar -> foo\\\ bar
///   foo"bar -> foo\"bar
///   foo'bar -> foo"'"bar
fn escapeSpecialChar(self: *Self, s: []const u8) ![]const u8 {
    const alloc = self.gpa.allocator();
    var ret: std.ArrayListUnmanaged(u8) = .{};

    var i: usize = 0;
    while (i < s.len) : (i += 1) {
        if (s[i] == '\\') {
            if (s[i + 1] == ' ') {
                try ret.appendSlice(alloc, "\\\\\\ ");
                i += 1;
            } else {
                try ret.append(alloc, s[i]);
            }
        } else if (s[i] == ' ') {
            try ret.appendSlice(alloc, "\\ ");
        } else if (s[i] == '"') {
            try ret.appendSlice(alloc, "\\\"");
        } else if (s[i] == '\'') {
            try ret.appendSlice(alloc, "\"'\"");
        } else {
            try ret.append(alloc, s[i]);
        }
    }

    return ret.toOwnedSlice(alloc);
}
diff --git a/src/EditableUTF8String.zig b/src/EditableUTF8String.zig
index fdb2ffd51562..d98723da2a35 100644
--- a/src/EditableUTF8String.zig
+++ b/src/EditableUTF8String.zig
@@ -878,18 +878,75 @@ test "EditableUTF8String: killToEndOfLine()" {
    }
}

pub const CompletionToken = struct {
    const Kind = enum { cwd, absolute };
    kind: Kind = .cwd,
    bytes: ?[]const u8 = null,
    cursor: ?Cursor = null,
};

// TODO a line may be 'word "word %c word', in which case the completion token should be 'word '
// TODO escaped spaces
pub fn getCompletionToken(self: *Self) ?[]const u8 {
    if (self.cursor.byte == 0) return null;
    if (ascii.isWhitespace(self.buffer.items[self.cursor.byte - 1])) return null;
    const c = self.prevWordStart(self.cursor) orelse return null;
    return self.buffer.items[c.byte..self.cursor.byte];
pub fn getCompletionToken(self: *Self) CompletionToken {
    var tok = CompletionToken{};
    if (self.cursor.byte == 0) return tok;
    if (ascii.isWhitespace(self.buffer.items[self.cursor.byte - 1])) {
        return tok;
    } else if (self.buffer.items[self.cursor.byte - 1] == '/') {
        tok.kind = .absolute;
        return tok;
    }
    tok = self.completionStart(self.cursor);
    if (tok.cursor) |c| {
        tok.bytes = self.buffer.items[c.byte..self.cursor.byte];
    }
    return tok;
}

// TODO update this when improving getCompletionToken()
pub fn killCompletionToken(self: *Self) void {
    self.killToPrevWordStart();
    const tok = self.completionStart(self.cursor);
    if (tok.cursor) |c| {
        var to_remove = self.cursor.byte - c.byte; // TODO this is inefficient
        while (to_remove > 0) : (to_remove -= 1) _ = self.buffer.orderedRemove(c.byte);
        self.codepoint_len -= self.cursor.codepoint - c.codepoint;
        self.cursor = c;
    } else return;
}

/// Find the start of the word to complete in the buffer.
/// Delimiter: whitespace /
fn completionStart(self: *Self, cursor: Cursor) CompletionToken {
    var tok = CompletionToken{};
    tok.cursor = cursor;

    // The cursor may be at the end of the line or we may already be at a completion start.
    if (tok.cursor.?.byte == self.buffer.items.len or !ascii.isWhitespace(self.buffer.items[tok.cursor.?.byte]) or
        self.buffer.items[tok.cursor.?.byte] != '/')
    {
        tok.cursor = self.cursorLeftOf(tok.cursor.?) orelse return tok;
    }

    // Skip delimiter.
    while (self.cursorLeftOf(tok.cursor.?)) |c| {
        if (!ascii.isWhitespace(self.buffer.items[tok.cursor.?.byte]) or self.buffer.items[tok.cursor.?.byte] != '/') {
            break;
        }
        tok.cursor = c;
    } else return tok;

    // Skip non delimiter.
    while (self.cursorLeftOf(tok.cursor.?)) |c| {
        if (ascii.isWhitespace(self.buffer.items[c.byte])) {
            break;
        } else if (self.buffer.items[c.byte] == '/') {
            tok.kind = .absolute;
            break;
        }
        tok.cursor = c;
    }

    return tok;
}

test "EditableUTF8String: getCompletionToken()" {
@@ -899,7 +956,7 @@ test "EditableUTF8String: getCompletionToken()" {
        a.moveCursorOneBackward();
        a.moveCursorOneForward();
        const token = a.getCompletionToken();
        try std.testing.expect(token == null);
        try std.testing.expect(token.bytes == null);
        a.deinit();
    }

@@ -907,8 +964,8 @@ test "EditableUTF8String: getCompletionToken()" {
        const str = "word   word";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token != null);
        try std.testing.expectEqualSlices(u8, "word", token.?);
        try std.testing.expect(token.bytes != null);
        try std.testing.expectEqualSlices(u8, "word", token.bytes.?);
        a.deinit();
    }

@@ -917,8 +974,8 @@ test "EditableUTF8String: getCompletionToken()" {
        var a = try Self.from(str);
        a.moveCursorOneBackward();
        const token = a.getCompletionToken();
        try std.testing.expect(token != null);
        try std.testing.expectEqualSlices(u8, "öäü", token.?);
        try std.testing.expect(token.bytes != null);
        try std.testing.expectEqualSlices(u8, "öäü", token.bytes.?);
        a.deinit();
    }

@@ -926,7 +983,7 @@ test "EditableUTF8String: getCompletionToken()" {
        const str = "word   ";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token == null);
        try std.testing.expect(token.bytes == null);
        a.deinit();
    }

@@ -935,7 +992,65 @@ test "EditableUTF8String: getCompletionToken()" {
        var a = try Self.from(str);
        a.moveCursorOneBackward();
        const token = a.getCompletionToken();
        try std.testing.expect(token == null);
        try std.testing.expect(token.bytes == null);
        a.deinit();
    }

    {
        const str = "/word";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token.bytes != null);
        try std.testing.expect(token.kind == .absolute);
        try std.testing.expectEqualSlices(u8, "word", token.bytes.?);
        a.deinit();
    }

    {
        const str = "word/foo";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token.bytes != null);
        try std.testing.expect(token.kind == .absolute);
        try std.testing.expectEqualSlices(u8, "foo", token.bytes.?);
        a.deinit();
    }

    {
        const str = "word/";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token.kind == .absolute);
        try std.testing.expect(token.bytes == null);
        a.deinit();
    }

    {
        const str = "/word";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token.bytes != null);
        try std.testing.expect(token.kind == .absolute);
        try std.testing.expectEqualSlices(u8, "word", token.bytes.?);
        a.deinit();
    }

    {
        const str = "word/foo";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token.bytes != null);
        try std.testing.expect(token.kind == .absolute);
        try std.testing.expectEqualSlices(u8, "foo", token.bytes.?);
        a.deinit();
    }

    {
        const str = "word/";
        var a = try Self.from(str);
        const token = a.getCompletionToken();
        try std.testing.expect(token.kind == .absolute);
        try std.testing.expect(token.bytes == null);
        a.deinit();
    }
}
diff --git a/src/mode.zig b/src/mode.zig
index 55154dc07e37..40d2aecdf284 100644
--- a/src/mode.zig
+++ b/src/mode.zig
@@ -15,14 +15,18 @@
// along with this program. If not, see <https://www.gnu.org/licenses/>.

const spoon = @import("spoon");
const build_options = @import("build_options");
const std = @import("std");
const ascii = std.ascii;
const debug = std.debug;
const fs = std.fs;
const math = std.math;
const mem = std.mem;
const logger = std.log.scoped(.mode);
const log = std.log.scoped(.mode);

const EditableUTF8String = @import("EditableUTF8String.zig");
const Dir = @import("Dir.zig");
const File = @import("File.zig");
const Completion = @import("Completion.zig");

const context = &@import("nfm.zig").context;

@@ -54,21 +58,125 @@ pub const UIMode = union(enum) {

    /// User input mode: Title bar is mini-editor for user input.
    user_input: struct {
        const UpdateCompletionMode = enum { force, passive };

        const UserInput = @This();
        operation: UserInputOperation,
        buffer: EditableUTF8String,
        history_index: ?usize,
        completion: ?Completion = null,
        cmp_dirs: Completion.DirsList,

        /// Wrapper around UserInput.complete() to handle files errors.
        pub fn updateCompletion(self: *UserInput, mode: UpdateCompletionMode) !void {
            self.complete(mode) catch |err| switch (err) {
                error.AccessDenied => return,
                else => return err,
            };
        }

        fn complete(self: *UserInput, mode: UpdateCompletionMode) !void {
            const token = self.buffer.getCompletionToken();
            log.debug("token kind: {s}, bytes: {?s}", .{ @tagName(token.kind), token.bytes });
            if (self.completion == null) {
                if (self.cmp_dirs.dirs.len > 0) {
                    self.completion = try Completion.newFromDir(&self.cmp_dirs.dirs.last.?.data);
                } else {
                    switch (token.kind) {
                        .cwd => {
                            if (context.dirmap.focusedDirView()) |fdv| {
                                self.completion = try Completion.newFromDir(fdv.dir);
                            }
                        },
                        .absolute => {
                            try self.cmp_dirs.addDir("/", "");
                            self.completion = try Completion.newFromDir(&self.cmp_dirs.dirs.last.?.data);
                        },
                    }
                }
            }

            if (token.bytes) |b| {
                self.completion.?.compare_len = b.len;
                switch (mode) {
                    .force => try self.forceCompletion(b),
                    .passive => try self.passiveCompletion(b),
                }
            }
        }

        pub fn abortCompletion(self: *UserInput) void {
            if (self.completion) |cmp| {
                cmp.deinit();
                self.completion = null;
            }
        }

        /// Remove the last dir from the cmp_dirs list if we are at the begining
        /// of the token.
        // TODO: Find a better way to know when we need to remove a child dir
        // For example, having 'foo/bar', removing bar will work correctly but then
        // adding 'b' and deleting 'b' will remove 'foo' from childs
        pub fn maybeGoPrevCmpDir(self: *UserInput) void {
            const token = self.buffer.getCompletionToken();
            if (token.bytes == null) self.cmp_dirs.maybeRemoveLast();
            self.abortCompletion();
        }

        /// Update the completion on 'Tab' and insert the suggestion in the input buffer.
        fn forceCompletion(self: *UserInput, bytes: []const u8) !void {
            switch (context.ui_mode.user_input.completion.?.compare(bytes)) {
                0 => self.abortCompletion(),
                1 => {
                    self.buffer.killCompletionToken();
                    const compl = self.completion.?.getFirst() orelse unreachable;
                    try self.buffer.insertQuotedSliceAtCursor(compl.name);
                    if (compl.kind == .Directory) try self.cmp_dirs.addDir(compl.dir.name, compl.name);
                    self.abortCompletion();
                },
                else => {
                    self.buffer.killCompletionToken();
                    const compl = self.completion.?.getCommonStart() orelse unreachable;
                    try self.buffer.insertQuotedSliceAtCursor(compl);
                    context.completion_count = self.completion.?.completions.len;
                    self.abortCompletion();
                },
            }
        }

        /// Only update the count of suggestions without inserting anything in
        /// the input buffer.
        // TODO: Diplay the suggestions
        fn passiveCompletion(self: *UserInput, bytes: []const u8) !void {
            switch (context.ui_mode.user_input.completion.?.compare(bytes)) {
                0 => self.abortCompletion(),
                1 => {
                    const compl = self.completion.?.getFirst() orelse unreachable;
                    if (compl.kind == .Directory and mem.eql(u8, bytes, compl.name)) {
                        try self.cmp_dirs.addDir(compl.dir.name, compl.name);
                    }
                    context.completion_count = self.completion.?.completions.len;
                },
                else => {
                    // TODO: Should use the full file name instead of the
                    // common start to use in a widget.
                    _ = self.completion.?.getCommonStart() orelse unreachable;
                    context.completion_count = self.completion.?.completions.len;
                    self.abortCompletion();
                },
            }
        }
    },

    pub fn setNormal(self: *Self) void {
        if (self.* == .normal) return;
        logger.debug("normal mode", .{});
        log.debug("normal mode", .{});
        self.reset();
        self.* = .normal;
    }

    pub fn setMessage(self: *Self, comptime level: MessageLevel, comptime message: []const u8) void {
        logger.debug("message mode: {}, '{s}'", .{ level, message });
        log.debug("message mode: {}, '{s}'", .{ level, message });
        self.reset();
        self.* = .{ .message = .{
            .message = message,
@@ -77,12 +185,13 @@ pub const UIMode = union(enum) {
    }

    pub fn setUserInput(self: *Self, operation: UserInputOperation) !void {
        logger.debug("user input mode mode: {}", .{operation});
        log.debug("user input mode mode: {}", .{operation});
        self.reset();
        self.* = .{ .user_input = .{
            .operation = operation,
            .buffer = try EditableUTF8String.newWithCapacity(1024),
            .history_index = null,
            .cmp_dirs = .{},
        } };
    }

@@ -90,6 +199,8 @@ pub const UIMode = union(enum) {
        context.ui.title_dirty = true;
        if (self.* == .user_input) {
            self.user_input.buffer.deinit();
            if (self.user_input.completion) |cmp| cmp.deinit();
            self.user_input.cmp_dirs.deinit();
        }
    }
};
-- 
2.39.0
nfm/patches/alpine.yml: SUCCESS in 50s

[[WIP] Rewrite tab completion][0] v2 from [Hugo Machet][1]

[0]: https://lists.sr.ht/~leon_plickat/nfm/patches/37892
[1]: mailto:mail@hmachet.com

✓ #915117 SUCCESS nfm/patches/alpine.yml https://builds.sr.ht/~leon_plickat/job/915117