shithub: fm

Download patch

ref: 2570196868ca6d317b882c7c64b114b178a3b75c
author: phil9 <telephil9@gmail.com>
date: Fri Nov 12 14:25:28 EST 2021 

initial import


--- /dev/null
+++ b/LICENSE
@@ -1,0 +1,21 @@
+MIT License
+
+Copyright (c) 2021 phil9 <telephil9@gmail.com>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
--- /dev/null
+++ b/README
@@ -1,0 +1,21 @@
+fm
+===
+fm provides a gui to select an item from a list using a fuzzy matching algorithm.
+When an item is selected, it is sent to the plumber `send` port unless the `-p` option
+is used in which case the item name is printed on standard output and the application exits.
+
+Usage:
+-------
+Install with usual ``mk install``
+Sample use: ``walk -f | fm``
+
+The provided `b` script gives a usage example.
+
+Credits:
+---------
+The fuzzy matching algorithm has been ported from: 
+* https://github.com/forrestthewoods/lib_fts/
+
+Bugs:
+------
+Obviously!
--- /dev/null
+++ b/a.h
@@ -1,0 +1,10 @@
+typedef struct Match Match;
+
+struct Match
+{
+	char *n;
+	int s;
+};
+
+int fuzzymatch(char *pat, char *s);
+ 
\ No newline at end of file
--- /dev/null
+++ b/b
@@ -1,0 +1,6 @@
+#!/bin/rc
+
+suffixes='\.([bcChlmsy]|asm|awk|cc|cgi|cpp|cs|go|goc|hs|java|lua|lx|mk|ml|mli|ms|myr|pl|py|rc|sh|tex|xy)$'
+fullnames='(^|/)mkfile$'
+
+walk -f |grep -v .git |grep -e $fullnames -e $suffixes |fm
--- /dev/null
+++ b/fm.c
@@ -1,0 +1,111 @@
+#include <u.h>
+#include <libc.h>
+#include <ctype.h>
+#include "a.h"
+
+/* code ported from https://github.com/forrestthewoods/lib_fts */
+
+enum
+{
+	Reclimit = 10,
+
+	/* score modifiers */
+	Bseq = 15,
+	Bsep = 30,
+	Bcamel = 30,
+	Bfirst = 15,
+	Plead = -5,
+	Pmaxlead = -15,
+	Punmatched = -1,
+};
+
+int
+fuzzymatchrec(char *pat, char *s, char *ss, 
+			  u8int *smatches, u8int *matches, int maxmatches, int nextmatch, 
+			  int *reccount, int reclimit)
+{
+	int score, penalty, i, curridx, previdx, recmatch, bestrecscore, recscore, firstmatch, matched, unmatched;
+	char neighbor, curr;
+	u8int bestrecmatches[256], recmatches[256];
+
+	*reccount += 1;
+	if(*reccount >= reclimit)
+		return -1;
+
+	if(*pat == '\0' || *s == '\0')
+		return -1;
+
+	recmatch = 0;
+	bestrecscore = 0;
+	firstmatch = 1;
+	while(*pat != '\0' && *s != '\0'){
+		if(tolower(*pat) == tolower(*s)){
+			if(nextmatch > maxmatches)
+				return -1;
+			if(firstmatch && smatches){
+				memcpy(matches, smatches, nextmatch);
+				firstmatch = 0;
+			}
+			recscore = fuzzymatchrec(pat, s + 1, ss, matches, recmatches, sizeof(recmatches), nextmatch, reccount, reclimit);
+			if(recscore >= 0){
+				if(!recmatch || recscore > bestrecscore){
+					memcpy(bestrecmatches, recmatches, 256);
+					bestrecscore = recscore;
+				}
+				recmatch = 1;
+			}
+			matches[nextmatch++] = (u8int)(s - ss);
+			++pat;
+		}
+		++s;
+	}
+
+	score = -1;
+	matched = *pat == '\0';
+	if(matched){
+		while(*s != '\0')
+			++s;
+		score = 100;
+		penalty = Plead * matches[0];
+		if(penalty < Pmaxlead)
+			penalty = Pmaxlead;
+		score += penalty;
+		unmatched = (int)(s - ss) - nextmatch;
+		score += Punmatched * unmatched;
+		for(i = 0; i < nextmatch; i++){
+			curridx = matches[i];
+			if(i > 0){
+				previdx = matches[i - 1];
+				if(curridx == (previdx + 1))
+					score += Bseq;
+			}
+			if(curridx > 0){
+				neighbor = ss[curridx - 1];
+				curr = ss[curridx];
+				if(islower(neighbor) && isupper(curr))
+					score += Bcamel;
+				if(neighbor == '_' || neighbor == ' ')
+					score += Bsep;
+			}else
+				score += Bfirst;
+		}
+	}
+
+	if(recmatch && (!matched || bestrecscore > score)){
+		memcpy(matches, bestrecmatches, maxmatches);
+		return bestrecscore;
+	}else if(matched)
+		return score;
+		
+	return -1;
+}
+
+int
+fuzzymatch(char *pat, char *s)
+{
+	u8int m[256];
+	int r;
+
+	r = 0;
+	return fuzzymatchrec(pat, s, s, nil, m, sizeof(m), 0, &r, Reclimit);
+}
--- /dev/null
+++ b/main.c
@@ -1,0 +1,276 @@
+#include <u.h>
+#include <libc.h>
+#include <ctype.h>
+#include <bio.h>
+#include <thread.h>
+#include <draw.h>
+#include <mouse.h>
+#include <keyboard.h>
+#include <plumb.h>
+#include "a.h"
+
+enum
+{
+	Emouse,
+	Eresize,
+	Ekeyboard,
+};
+
+enum
+{
+	Maxlines = 4096,
+	Padding = 4,
+};
+
+Mousectl *mctl;
+Keyboardctl *kctl;
+Image *selbg;
+Rectangle ir;
+Rectangle lr;
+int lh;
+int lcount;
+int loff;
+int lsel;
+int pmode;
+int plumbfd;
+char* lines[Maxlines];
+int nlines;
+Match matches[Maxlines];
+int nmatches;
+char input[255] = {0};
+int ninput = 0;
+char pwd[255] = {0};
+
+int
+matchcmp(void *a, void *b)
+{
+	Match m, n;
+
+	m = *(Match*)a;
+	n = *(Match*)b;
+	return n.s - m.s;
+}
+
+void
+match(char *pat)
+{
+	int i, s;
+
+	nmatches = 0;
+	for(i = 0; i < nlines; i++){
+		s = fuzzymatch(pat, lines[i]);
+		if(s >= 0){
+			matches[nmatches].n = lines[i];
+			matches[nmatches].s = s;
+			nmatches++;
+		}
+	}
+	if(nmatches > 0)
+		qsort(matches, nmatches, sizeof(Match), matchcmp);
+}
+
+void
+loadlines(void)
+{
+	Biobuf *bp;
+	char *s;
+
+	nlines = 0;
+	bp = Bfdopen(0, OREAD);
+	for(;;){
+		s = Brdstr(bp, '\n', 1);
+		if(s == nil)
+			break;
+		lines[nlines++] = s;
+		matches[nmatches++].n = s;
+		if(nlines >= Maxlines)
+			break;
+	}
+	Bterm(bp);
+}
+
+Rectangle
+linerect(int i)
+{
+	Rectangle r;
+
+	r.min.x = 0;
+	r.min.y = i * (font->height + Padding);
+	r.max.x = lr.max.x;
+	r.max.y = (i + 1) * (font->height + Padding);
+	r = rectaddpt(r, lr.min);
+	return r;
+}
+
+void
+redraw(void)
+{
+	Point p;
+	int i, n;
+	Match m;
+
+	draw(screen, screen->r, display->white, nil, ZP);
+	p = string(screen, addpt(screen->r.min, Pt(Padding, Padding)), display->black, ZP, font, "> ");
+	stringn(screen, p, display->black, ZP, font, input, ninput);
+
+	for(i = 0; i < lcount; i++){
+		n = loff + i;
+		if(n >= nmatches)
+			break;
+		m = matches[n];
+		p = addpt(lr.min, Pt(0, i * (font->height + Padding)));
+		if(lsel == i)
+			draw(screen, linerect(i), selbg, nil, ZP);
+		string(screen, p, display->black, ZP, font, matches[i].n);
+	}
+	flushimage(display, 1);
+}
+
+void
+eresize(void)
+{
+	ir = Rect(Padding, Padding, screen->r.max.x - Padding, Padding + font->height + Padding);
+	ir = rectaddpt(ir, screen->r.min);
+	lr = Rect(screen->r.min.x + Padding, ir.max.y, ir.max.x, screen->r.max.y - Padding);
+	lh = font->height + Padding;
+	lcount = Dy(lr) / lh;
+	redraw();
+}
+
+void
+emouse(Mouse *m)
+{
+	USED(m);
+}
+
+void
+inputchanged(void)
+{
+	int i;
+
+	input[ninput] = 0;
+	if(ninput > 0){
+		match(input);
+	}else{
+		nmatches = 0;
+		for(i = 0; i < nlines; i++)
+			matches[nmatches++].n = lines[i];
+	}
+	if(lsel >= (nmatches - 1))
+		lsel = 0;
+	if(nmatches == 0)
+		lsel = -1;
+	redraw();
+}
+
+void
+ekeyboard(Rune k)
+{
+	Match m;
+
+	switch(k){
+	case Kdel:
+		threadexitsall(nil);
+		break;
+	case Kup:
+		if(lsel > 0)
+			--lsel;
+		redraw();
+		break;
+	case Kdown:
+		if(lsel < (nmatches - 1))
+			++lsel;
+		redraw();
+		break;
+	case '\n':
+		if(lsel >= 0){
+			m = matches[lsel + loff];
+			if(pmode){
+				print("%s", m.n);
+				threadexitsall(nil);
+			}else
+				plumbsendtext(plumbfd, argv0, nil, pwd, m.n);
+		}
+		break;
+	case Kbs:
+		if(ninput > 0){
+			ninput--;
+			inputchanged();
+		}
+		break;
+	case Knack: /* ^U */
+		if(ninput > 0){
+			ninput = 0;
+			inputchanged();
+		}
+	default:
+		if(isalnum(k)){
+			input[ninput++] = (char)k; /* XXX */
+			inputchanged();
+		}
+	}
+}
+
+void
+usage(void)
+{
+	fprint(2, "usage: %s [-p]\n", argv0);
+	exits("usage");
+}
+
+void
+threadmain(int argc, char **argv)
+{
+	Mouse m;
+	Rune k;
+	Alt a[] = {
+		{ nil, &m, CHANRCV },
+		{ nil, nil, CHANRCV },
+		{ nil, &k, CHANRCV },
+		{ nil, nil, CHANEND },
+	};
+
+	pmode = 0;
+	ARGBEGIN{
+	case 'p':
+		pmode = 1;
+		break;
+	default:
+		usage();
+	}ARGEND;
+	getwd(pwd, sizeof pwd);
+	if(pmode == 0){
+		plumbfd = plumbopen("send", OWRITE|OCEXEC);
+		if(plumbfd < 0)
+			sysfatal("plumbopen: %r");
+	}
+	loadlines();
+	if(initdraw(nil, nil, "fm") < 0)
+		sysfatal("initdraw: %r");
+	display->locking = 0;
+	if((mctl = initmouse(nil, screen)) == nil)
+		sysfatal("initmouse: %r");
+	if((kctl = initkeyboard(nil)) == nil)
+		sysfatal("initkeyboard: %r");
+	a[Emouse].c = mctl->c;
+	a[Eresize].c = mctl->resizec;
+	a[Ekeyboard].c = kctl->c;
+	selbg = allocimage(display, Rect(0,0,1,1), screen->chan, 1, 0xEFEFEFFF);
+	loff = 0;
+	lsel = 0;
+	eresize();
+	for(;;){
+		switch(alt(a)){
+		case Emouse:
+			emouse(&m);
+			break;
+		case Eresize:
+			if(getwindow(display, Refnone) < 0)
+				sysfatal("getwindow: %r");
+			eresize();
+		case Ekeyboard:
+			ekeyboard(k);
+			break;
+		}
+	}
+}
--- /dev/null
+++ b/mkfile
@@ -1,0 +1,8 @@
+</$objtype/mkfile
+
+BIN=/$objtype/bin
+TARG=fm
+OFILES=main.$O fm.$O
+HFILES=a.h
+
+</sys/src/cmd/mkone