https://nessuent.net/epilys blog2022-10-22T13:38:25.114018+00:00epilysmanos@pitsidianak.iscc-bycode etc tidbitshttps://nessuent.net/posts/2022-10-22_open2_mode_gotcha.htmlA minor gotcha in open(2)2022-10-22T13:38:25.114229+00:00<p>A test I was writing in C was causing a panic in Rust code that was called via FFI. The panicking line of Rust code was something of the sort:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode rust"><code class="sourceCode rust"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true"></a><span class="kw">use</span> <span class="pp">nix::sys::stat::</span>Mode<span class="op">;</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true"></a></span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true"></a><span class="kw">fn</span> foo(mode<span class="op">:</span> <span class="pp">libc::</span><span class="dt">mode_t</span>) <span class="op">{</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true"></a> <span class="kw">let</span> mode<span class="op">:</span> Mode <span class="op">=</span> <span class="pp">Mode::</span>from_bits(mode)<span class="op">.</span>unwrap()<span class="op">;</span></span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true"></a> <span class="op">..</span></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true"></a><span class="op">}</span></span></code></pre></div>
<p><code>nix</code><a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref"><sup>1</sup></a> fails to handle a valid (I thought) mode value? There’s gotta be a simpler explanation: the mode value is invalid. Indeed looking at the C code:</p>
<figure>
<div class="sourceCode" id="cb2"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true"></a><span class="dt">char</span> *file = <span class="st">"/tmp/file"</span>;</span>
<span id="cb2-2"><a href="#cb2-2" aria-hidden="true"></a>...</span>
<span id="cb2-3"><a href="#cb2-3" aria-hidden="true"></a>fd = open(file, O_WRONLY | O_CREAT | O_TRUNC);</span>
<span id="cb2-4"><a href="#cb2-4" aria-hidden="true"></a>...</span></code></pre></div>
<figcaption>
<small>example taken from POSIX <code>open</code> specification<a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref"><sup>2</sup></a></small>
</figcaption>
</figure>
<p>I had forgotten to specify the <code>mode</code> argument in <code>open</code>. However that’s legal behavior in POSIX, and it doesn’t define what happens when you call the variadic<a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref"><sup>3</sup></a> function <code>open</code> without the <code>mode</code> argument.</p>
<p>The glibc+Linux <code>open(2)</code> manual page with <code>man 2 open</code> explains what happens in their implementation:</p>
<pre class="text"><code>The mode argument must be supplied if O_CREAT
or O_TMPFILE is specified in flags; if it is
not supplied, some arbitrary bytes from the
stack will be applied as the file mode [..]</code></pre>
<p>Why am I not surprised! This should not be considered acceptable behavior for a standard library.</p>
<section class="footnotes" role="doc-endnotes">
<hr />
<ol>
<li id="fn1" role="doc-endnote"><p><q cite="https://crates.io/crates/nix">Rust friendly bindings to *nix APIs</q> <a href="https://crates.io/crates/nix" class="uri">https://crates.io/crates/nix</a><a href="#fnref1" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn2" role="doc-endnote"><p><a href="https://pubs.opengroup.org/onlinepubs/007904875/functions/open.html" class="uri">https://pubs.opengroup.org/onlinepubs/007904875/functions/open.html</a><a href="#fnref2" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn3" role="doc-endnote"><p><dfn title="Variadic functions are functions (e.g. printf) which take a variable number of arguments. The declaration of a variadic function uses an ellipsis as the last parameter, e.g. int printf(const char* format, ...);.">variadic</dfn> means it accepts a non fixed number of arguments, like <code>printf</code>. Its function signature is</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true"></a><span class="dt">int</span> open(<span class="dt">const</span> <span class="dt">char</span> *path, <span class="dt">int</span> oflag, ... );</span></code></pre></div>
<p>Without historical context, my guess this was to avoid having a different function when you want to specify the <code>mode</code>. Adding extra functions for extra arguments is an acceptable pattern in other <code>libc</code> functions, though.<a href="#fnref3" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
</ol>
</section>
2022-10-22T00:00:00+03:00https://nessuent.net/posts/2022-03-26_Django_jobs.htmlRunning minor tasks with a simple job system in Django2022-10-22T13:38:25.114219+00:00<p>Suppose you have a Django website that needs to run jobs and when exactly it runs and idempotence are not important, as long as it eventually runs soon enough.</p>
<p>Examples:</p>
<ul>
<li>run and collect statistics on data</li>
<li>send or process received <a href="https://www.w3.org/TR/webmention/">Webmentions</a></li>
<li>cache remote URL contents</li>
</ul>
<p>You can encode a generic job function as a Django model and store it in the database. The job’s function is a plain text field that must include a valid Python dotted path of a function, that is, on runtime we must be able to import the function by using its path from the given string.</p>
<pre class="python3"><code>from django.db import models
from django.utils.timezone import make_aware
from django.utils.module_loading import import_string
class JobKind(models.Model):
id = models.AutoField(primary_key=True)
dotted_path = models.TextField(null=False, blank=False, unique=True)
created = models.DateTimeField(auto_now_add=True, null=False, blank=False)
last_modified = models.DateTimeField(auto_now_add=True, null=False, blank=False)
def __str__(self):
return self.dotted_path
@staticmethod
def from_func(func):
if isinstance(func, types.FunctionType):
dotted_path = f"{func.__module__}.{func.__name__}"
ret, _ = JobKind.objects.get_or_create(dotted_path=dotted_path)
return ret
else:
raise TypeError
def run(self, job):
try:
func = import_string(self.dotted_path)
return func(job)
except ImportError:
logging.error(f"Could not resolve job dotted_path: {self.dotted_path}")
raise ImportError</code></pre>
<p>You can implement a <code>Job</code> Django model that can run a <code>JobKind</code> as follows:</p>
<pre class="python3"><code>class Job(models.Model):
id = models.AutoField(primary_key=True)
kind = models.ForeignKey(JobKind, null=True, on_delete=models.SET_NULL)
created = models.DateTimeField(auto_now_add=True)
active = models.BooleanField(default=True, null=False, blank=False)
periodic = models.BooleanField(default=False, null=False, blank=False)
failed = models.BooleanField(default=False, null=False, blank=False)
last_run = models.DateTimeField(default=None, null=True, blank=True)
logs = models.TextField(null=True, blank=True)
data = models.JSONField(null=True, blank=True)
def __str__(self):
return f"{self.kind} {self.data}"
def run(self):
if not self.kind_id:
return
self.last_run = make_aware(datetime.now())
try:
res = self.kind.run(self)
if res and not self.periodic:
self.active = False
if isinstance(res, str):
if self.logs is None:
self.logs = ""
self.logs += res
self.failed = False
self.save(update_fields=["last_run", "failed", "active", "logs"])
except Exception as exc:
if self.logs is None:
self.logs = ""
self.logs += str(exc)
self.failed = True
self.save(update_fields=["last_run", "failed", "logs"])
return</code></pre>
<p>Now you can run pending jobs with cron by making a Django management command:</p>
<pre class="python3"><code># my_project/management/commands/run_jobs.py
from django.core.management.base import BaseCommand
from my_project.jobs import Job
class Command(BaseCommand):
help = "Run pending jobs"
def handle(self, *args, **kwargs):
for job in Job.objects.filter(active=True):
job.run()</code></pre>
<p>You can also setup a thread that sleeps and periodically wakes up to run any pending tasks by overriding the <code>ready</code> method on your <code>django.apps.AppConfig</code>:</p>
<pre class="python3"><code># my_project/apps.py
import threading
def ready(self):
import my_project.jobs
def sched_jobs():
from my_project.jobs import Job
import sched
import time
def exec_fn():
for job in Job.objects.filter(active=True, failed=False):
job.run()
s = sched.scheduler(time.time, time.sleep)
while True:
s.enter(15 * 60, 1, exec_fn)
s.run(blocking=True)
self.scheduling_thread = threading.Thread(target=sched_jobs, daemon=True)
self.scheduling_thread.name = "scheduling_thread"
self.scheduling_thread.start()</code></pre>
<table>
<tr>
<td>
<p><a href="/static/images/job_kinds.png"><img src="/static/images/job_kinds.png" alt="JobKind django admin panel" /></a></p>
</td>
<td>
<p><a href="/static/images/job_admin.png"><img src="/static/images/job_admin.png" alt="Job django admin panel" /></a></p>
</td>
</tr>
</table>
<p>You can easily inspect jobs from the Django admin panel by registering the models to the admin app:</p>
<pre class="python3"><code>@admin.action(description="Run jobs")
def run_jobs(modeladmin, request, queryset):
for job in queryset.all():
job.run()
class JobAdmin(ModelAdmin):
def success(self, obj):
if obj.last_run is None:
return None
return not obj.failed
readonly_fields = (
"json_pprint",
)
@admin.display(description="JSON pretty print")
def json_pprint(self, instance):
import json
return mark_safe(
f"""<pre>{json.dumps(instance.data, sort_keys=True, indent=4)}</pre>"""
)
success.boolean = True
ordering = ["-created", "-last_run"]
actions = [run_jobs]
list_display = ["__str__", "created", "active", "periodic", "success", "last_run"]
list_filter = [
"kind",
"active",
"failed",
]
class JobKindAdmin(ModelAdmin):
def resolves(self, obj):
from django.utils.module_loading import import_string
try:
_ = import_string(obj.dotted_path)
return True
except ImportError:
return False
resolves.boolean = True
ordering = ["-created", "-last_modified"]
list_display = ["__str__", "created", "last_modified", "resolves"]</code></pre>
<p>Now you can create new jobs from the admin panel and from code elsewhere in your app. Suppose you have an API endpoint to receive Webmentions. You can avoid blocking the HTTP response by scheduling the processing for later in the view:</p>
<pre class="python3"><code>from my_project.jobs import Job, JobKind
# schedule job
kind = JobKind.from_func(webmention_receive)
_job_obj, _ = Job.objects.get_or_create(
kind=kind, periodic=False, data={"source": source, "target": target}
)</code></pre>
<h2 id="improvements">Improvements</h2>
<ul>
<li>Make a job to periodically delete/cleanup old jobs</li>
<li>override <code>Job</code>’s <code>save</code> method to limit the maximum amount of jobs in the database</li>
</ul>
<h2 id="real-life-example">Real life example</h2>
<p>This pattern is used in the <code>sic.pm</code> link aggregator community: <a href="https://github.com/epilys/sic/blob/158284451097ab94da0efe5cbdfae14b0bb3a1a8/sic/jobs.py" class="uri">https://github.com/epilys/sic/blob/158284451097ab94da0efe5cbdfae14b0bb3a1a8/sic/jobs.py</a></p>
2022-03-26T00:00:00+03:00https://nessuent.net/posts/2021-09-09_buke_full_text_search_manpages.htmlbuke full text search manpages2022-10-22T13:38:25.114208+00:00<p>Repository: <a href="https://github.com/epilys/buke" class="uri">https://github.com/epilys/buke</a></p>
<ul>
<li><code>cargo run --release -- --build</code> builds an sqlite3 database out of all manpages in your <code>$MANPATH</code></li>
<li><code>cargo run --release -- "query"</code> searches for “query” in the index</li>
</ul>
<p>The <code>sqlite3</code> C bindings were generated with <code>bindgen</code>. The sqlite3 database is gzipped in blocks with a custom <a href="https://sqlite.org/vfs.html"><code>VFS</code> layer</a> extension located in <a href="./src/db/vfs.rs"><code>src/db/vfs.rs</code></a>.</p>
<p>The gzip version is 42MiB compared to 117MiB uncompressed.</p>
<h2 id="use">Use</h2>
<p>First, build the database:</p>
<pre class="shell"><code>% ./target/release/buke --build
Wait patiently, this part wasn't optimized (or bothered with)
306/10689 done..^C</code></pre>
<p>Then query:</p>
<pre class="shell"><code>% ./target/release/buke socket
systemd-socket-proxyd.8 - systemd-socket-proxyd - Bidirectionally proxy local soc
socket.7 - socket - Linux socket interface
systemd.socket.5 - systemd.socket - Socket unit configuration
systemd-socket-activate.1 - systemd-socket-activate - Test socket activation of dae
socketcall.2 - socketcall - socket system calls
socket.2 - socket - create an endpoint for communication
dbus-cleanup-sockets.1 - dbus-cleanup-sockets - clean up leftover sockets in a d
socketpair.2 - socketpair - create a pair of connected sockets
modbus_set_socket.3 - modbus_set_socket - set socket of the context
tipc-socket.8 - tipc-socket - show TIPC socket (port) information
modbus_get_socket.3 - modbus_get_socket - get the current socket of the conte
socketmap_table.5 - socketmap_table - Postfix socketmap table lookup client
systemd-journald.socket.8 - systemd-journald.service, systemd-journald.socket, syst
systemd-journald@.socket.8 - systemd-journald.service, systemd-journald.socket, syst
systemd-journald-audit.socket.8 - systemd-journald.service, systemd-journald.socket, syst
content matches:
packet.7 - packet - packet interface on device level
unix.7 - unix - sockets for local interprocess communication
raw.7 - raw - Linux IPv4 raw sockets
connect.2 - connect - initiate a connection on a socket
ss.8 - ss - another utility to investigate sockets
udp.7 - udp - User Datagram Protocol for IPv4
netstat.8 - netstat - Print network connections, routing tables, in
sock_diag.7 - sock_diag - obtaining information about sockets
vsock.7 - vsock - Linux VSOCK address family</code></pre>
<p>Regular expression match if build with <code>re</code> feature (default) or if your sqlite3 version includes a <code>REGEXP</code> implementation:</p>
<pre class="shell"><code>% target/release/buke -r 'system_[^_]*_types'
system_data_types.7 - system_data_types - overview of system data types
content matches:
FILE.3 - system_data_types - overview of system data types
time_t.3 - system_data_types - overview of system data types
fenv_t.3 - system_data_types - overview of system data types
uint64_t.3 - system_data_types - overview of system data types
va_list.3 - system_data_types - overview of system data types
dev_t.3 - system_data_types - overview of system data types
size_t.3 - system_data_types - overview of system data types
float_t.3 - system_data_types - overview of system data types
uintN_t.3 - system_data_types - overview of system data types
ptrdiff_t.3 - system_data_types - overview of system data types
int16_t.3 - system_data_types - overview of system data types
ftm.7 - feature_test_macros - feature test macros
clockid_t.3 - system_data_types - overview of system data types
off_t.3 - system_data_types - overview of system data types
div_t.3 - system_data_types - overview of system data types</code></pre>
2021-09-09T00:00:00+03:00https://nessuent.net/posts/2021-09-06_nntpserver.py:_nodependency_single_file_NNTP_server_library.htmlnntpserver.py: no-dependency single file NNTP server library2022-10-22T13:38:25.114197+00:00<p>Repository: <a href="https://github.com/epilys/nntpserver.py" class="uri">https://github.com/epilys/nntpserver.py</a></p>
<p>No-dependency, single file NNTP server library for developing modern, rfc3977-compliant (bridge) NNTP servers for python >=3.7. Developed as part of <a href="https://github.com/epilys/tade"><code>tade</code></a>, a web discussion forum with mailing list/NNTP interfaces which powers the <a href="https://sic.pm" class="uri">https://sic.pm</a> link aggregator.</p>
<p>Included example servers are:</p>
<ul>
<li><code>example_server.py</code> returning hard-coded articles</li>
<li><code>hnnntp.py</code> querying <a href="https://news.ycombinator.com" class="uri">https://news.ycombinator.com</a> (hackernews) API and caching results in an sqlite3 database. A public instance <em>might</em> be online at nessuent.xyz:564 (TLS only)</li>
</ul>
<table align="center">
<tbody>
<tr>
<td>
<p align="center">
<kbd ><img src="/static/images/commodore-amiga.png" alt="screenshot of nntp server accessed via commodore amiga" title="screenshot of nntp server accessed via commodore amiga" height="300" style="width: 100%; height: auto; " /></kbd>
</p>
</td>
</tr>
<tr>
<th>
<sup>https://sic.pm NNTP server that uses <code>nntpserver.py</code> <br />accessed on a Commodore Amiga with <a href="http://newscoaster.sourceforge.net/">NewsCoaster</a> client</sup>
</th>
</tr>
</tbody>
</table>
<p>Running <code>example_server.py</code>:</p>
<pre class="shell"><code>$ python3 example_server.py --connect-with-nntplib
Listening on localhost:9999
Connecting with nntplib...
New connection.
sending 201 NNTP Service Ready, posting prohibited
got: CAPABILITIES
sending 101 Capability list:
sending VERSION 2
sending READER
sending HDR
sending LIST ACTIVE NEWSGROUPS OVERVIEW.FMT SUBSCRIPTIONS
sending OVER
sending .
got: GROUP example.all
Group name example.all
sending 211 1 1 1 example.all
got: XOVER 1-1
sending 224 Overview information follows (multi-line)
sending 1 Hello world! epilys <epilys@example.com> Wed, 01 Sep 2021 15:06:01 +0000 <unique@example.com> 16 1
sending .
got: LIST OVERVIEW.FMT
sending 215 Order of fields in overview database.
sending Subject:
sending From:
sending Date:
sending Message-ID:
sending References:
sending Bytes:
sending Lines:
sending .
1 epilys <epilys@example.com> Hello world! (1)
Done with nntplib.</code></pre>
2021-09-06T00:00:00+03:00https://nessuent.net/posts/2021-10-07_Example_sqlite3_Dynamic_Loadable_Extension_in_Rust_vfs_and_vtab.htmlExample sqlite3 Dynamic Loadable Extension in Rust (vfs and vtab)2022-10-22T13:38:25.114185+00:00<p>Repository: <a href="https://github.com/epilys/vfsstat.rs" class="uri">https://github.com/epilys/vfsstat.rs</a></p>
<p>This is an example of how to create a dynamic loadable extension for <code>sqlite3</code> in Rust with its FFI capabilities by calling into the C <code>sqlite3</code> API directly. As a proof of concept it implements a VFS and a VTAB.</p>
<h2 id="vfs-and-virtual-tables">VFS and virtual tables</h2>
<p>A VFS is an OS interface for <code>sqlite3</code>; it handles IO with the system. For example, the <code>unix</code> vfs handles all the read, write, lock operations by translating them to appropriate libc, systemcall etc calls. Since we can chain VFSes, we can create a tree where the leafs are the default VFS (<code>unix</code> etc) and the intermediate nodes process all the information before passing them on to the next in the chain. The <code>sqlite3</code> source distribution contains the <code>vfsstat</code> extension which implements a VFS that keeps track of all read/write etc operations, and puts them in a virtual SQL table using the <code>vtab</code> interface of <code>sqlite3</code>. Just like the original, <code>vfsstat.rs</code> keeps IO statistics.</p>
<p>The code was a port of the official <a href="https://www.sqlite.org/src/file?name=ext/misc/vfsstat.c&ci=tip"><code>ext/misc/vfsstat.c</code></a> sqlite3 extension.</p>
<h2 id="build">Build</h2>
<pre class="shell"><code>cargo build --release</code></pre>
<p>Output will be located at <code>target/release/libvfsstat_rs.so</code></p>
<h2 id="use">Use</h2>
<p>Note: Query the virtual table by issuing <code>SELECT * FROM vtabstat</code>.</p>
<p>Assuming <code>libvfsstat_rs.so</code> is in current directory,</p>
<pre class="shell"><code>$ sqlite3
sqlite> .load ./libvfsstat_rs
sqlite> .open ../../test.db
sqlite> .schema
CREATE TABLE person (
id INTEGER PRIMARY KEY,
name TEXT NOT NULL UNIQUE,
data BLOB
);
sqlite> select * from person;
id name data
-- -------------------------------- -------------
1 Steven NULL
2 05504B041661AAD1320A8537EB8234D2 zÔ];[^;H
3 4967EEDBF69420D82C6B1BCFB31397DD ?BiΘI
4 19D0F5974A48AA561B7097CDA39E4047
l!Xk- 5
5 1F1FFD477777F5AA5CBFF916A4AF9593 + 텸vy\Y
6 0925676226D46FB4EC6DAEB11D130350 <</jޏ
7 5D6F4F219D2E3FAF7D61CA5237F106F8 (nlZ
8 FFD140BD25C1CA899446F2C9C2631A51 ,9^< p
9 F9F66F44D64FC54FDFAEBD3750FD3513 [C@E
sqlite> select * from vtabstat;
file stat count
-------------- ----------- -----
main bytesIn 12388
main bytesOut 0
main read 4
main write 0
main sync 0
main open 1
main lock 1
main access 0
main delete 0
main fullPath 0
main random 0
main sleep 0
main currentTime 0
journal bytesIn 0
journal bytesOut 0
journal read 0
journal write 0
journal sync 0
journal open 0
journal lock 0
journal access 0
journal delete 0
journal fullPath 0
journal random 0
journal sleep 0
journal currentTime 0
wal bytesIn 0
wal bytesOut 0
wal read 0
wal write 0
wal sync 0
wal open 1
wal lock 0
wal access 0
wal delete 0
wal fullPath 0
wal random 0
wal sleep 0
wal currentTime 0
master-journal bytesIn 0
master-journal bytesOut 0
master-journal read 0
master-journal write 0
master-journal sync 0
master-journal open 0
master-journal lock 0
master-journal access 0
master-journal delete 0
master-journal fullPath 0
master-journal random 0
master-journal sleep 0
master-journal currentTime 0
sub-journal bytesIn 0
sub-journal bytesOut 0
sub-journal read 0
sub-journal write 0
sub-journal sync 0
sub-journal open 0
sub-journal lock 0
sub-journal access 0
sub-journal delete 0
sub-journal fullPath 0
sub-journal random 0
sub-journal sleep 0
sub-journal currentTime 0
temp-database bytesIn 0
temp-database bytesOut 0
temp-database read 0
temp-database write 0
temp-database sync 0
temp-database open 0
temp-database lock 0
temp-database access 0
temp-database delete 0
temp-database fullPath 0
temp-database random 0
temp-database sleep 0
temp-database currentTime 0
temp-journal bytesIn 0
temp-journal bytesOut 0
temp-journal read 0
temp-journal write 0
temp-journal sync 0
temp-journal open 0
temp-journal lock 0
temp-journal access 0
temp-journal delete 0
temp-journal fullPath 0
temp-journal random 0
temp-journal sleep 0
temp-journal currentTime 0
transient-db bytesIn 0
transient-db bytesOut 0
transient-db read 0
transient-db write 0
transient-db sync 0
transient-db open 0
transient-db lock 0
transient-db access 0
transient-db delete 0
transient-db fullPath 0
transient-db random 0
transient-db sleep 0
transient-db currentTime 0
* bytesIn 0
* bytesOut 0
* read 0
* write 0
* sync 0
* open 0
* lock 0
* access 2
* delete 0
* fullPath 1
* random 0
* sleep 0</code></pre>
2021-10-07T00:00:00+03:00https://nessuent.net/posts/2021-11-26_kitkat.htmlkitkat from scratch2022-10-22T13:38:25.114171+00:00<p>The now iconic <code>catclock</code> from plan9 implemented from scratch in Rust. The only dependency is a raw framebuffer window drawing library, <code>minifb</code>. Install with</p>
<pre><code>cargo install kitkat</code></pre>
<ul>
<li><a href="https://github.com/epilys/kitkat" class="uri">https://github.com/epilys/kitkat</a></li>
<li><a href="https://crates.io/crates/kitkat" class="uri">https://crates.io/crates/kitkat</a></li>
</ul>
<p>The source of plan9’s <code>catclock</code> is located <a href="https://github.com/plan9foundation/plan9/blob/main/sys/src/games/catclock.c">here</a></p>
<pre class="shell"><code>$ kitkat --help
Usage: kitkat [--hook|--crazy|--offset OFFSET|--borderless|--resize|--sunmoon|--moon|--date]
Displays a kit kat clock with the system time, or the system time with given offset if the --offset
argument is provided.
--hook show a hooked tail instead of the default drop shaped one
--crazy go faster for each time this argument is invoked
--offset OFFSET add OFFSET to current system time (only the first given
offset will be used)
--borderless
--resize
--sunmoon show sun or moon phase depending on the hour
--moon show only moon phase
--date show month date
--dog show an italian greyhound named Gaius Octavius Maximus instead of a cat
OFFSET format is [+-]{0,1}\d\d:\d\d, e.g: 02:00 or -03:45 or +00:00</code></pre>
<table>
<tr>
<td>
<p><img src="/static/images/kitkat-round.gif" /></p>
</td>
<td>
<p><img src="/static/images/kitkat-hook.gif" /></p>
</td>
<td>
<p><img src="/static/images/kitkat-resized.jpg" /></p>
</td>
<td>
<p><img src="/static/images/dogkat.gif" /></p>
</td>
</tr>
<tr>
<th>
Default drop shaped tail.
</th>
<th>
Hooked tail with <code>--hook</code>.
</th>
<th>
Resizable window with <code>--resize</code>.
</th>
<th>
Dog instead of cat with <code>--dog</code>.
</th>
</tr>
<tr>
<td>
<p><img src="/static/images/kitkat-date-and-sun.jpg" /></p>
</td>
<td>
<p><img src="/static/images/kitkat-moon-phase-only.jpg" /></p>
</td>
<td>
</td>
<td>
</td>
</tr>
<tr>
<th>
Showing current date and sun/moon phase status.
</th>
<th>
Showing just moon phase status.
</th>
</tr>
</table>
2021-11-26T00:00:00+03:00https://nessuent.net/posts/2019-04-19_t420s_fuse.htmlReplacing backlight fuse on t420s2022-10-22T13:38:25.114161+00:00<figure>
<img src="https://nessuent.xyz/t420s_fuse/1.jpg" alt="" /><figcaption>the perpetrator</figcaption>
</figure>
<p>It is on the upper left of the monitor connection, testing the local fuses with a multimeter led to it quickly.</p>
<p>time for the dirtiest repair job ever. I have never done tiny SMD soldering in my life. I had no flux, small solder or a fine soldering tip and they are expensive to get in this forsaken part of the world. I usually order stuff online but I didn’t want to wait.</p>
<p>I ordered 5 fuses (for redundancy) from digi-key with express shipping and they arrived in 2 days. It was only afterwards that I realised I could have ordered solder, tips and flux from digikey as well.</p>
<p>I needed to protect the laptop from ESD. I am far from the actual ground (1st floor) so I connected the</p>
<figure>
<img src="https://nessuent.xyz/t420s_fuse/esd.jpg" width="250" alt="" /><figcaption>anti-static wrist wrap (stock photo)</figcaption>
</figure>
<p>on my oscilloscope.</p>
<p>The fuse is 0402, ie 0.4mm x 0.2mm. Smaller than a flea, and</p>
<figure>
<img src="https://nessuent.xyz/t420s_fuse/2.jpg" alt="" /><figcaption>it looks like a breadcrumb unless you look at it with a magnifying lens.</figcaption>
</figure>
<p>Removing the old fuse was out of the question because a safer way exists: applying the new one over the old one. By the way, I’ve read people online saying you could short it as well, but if another high load passes through you would probably do permanent damage.</p>
<figure>
<img src="https://nessuent.xyz/t420s_fuse/3.jpg" alt="" /><figcaption>Aligning the fuses is incredibly frustrating.</figcaption>
</figure>
<p>Flux would make it easier because it wouldn’t be pushed around by my breath or accidental pushes with my tweezers (nervousness and caffeine shouldn’t mix!).</p>
<figure>
<img src="https://nessuent.xyz/t420s_fuse/4.jpg" alt="" /><figcaption>I also had to cut very very thin pieces of solder with a hobby knife.</figcaption>
</figure>
<p>It was annoying to cut pieces with guesswork only to see that even though you cut it in half 3 times it’s still bigger than the fuse.</p>
<figure>
<img src="https://nessuent.xyz/t420s_fuse/5.jpg" alt="" /><figcaption>It took me ages to properly align <em>and</em> apply the first solder</figcaption>
</figure>
<p>(dry tacking was impossible). Plus you can’t touch the actual fuse with the soldering iron or it’s busted. I was getting anxious because my 10 Hours Classical Music for Concentration video was reaching the end.</p>
<figure>
<img src="https://nessuent.xyz/t420s_fuse/6.jpg" alt="" /><figcaption>fiat lux!</figcaption>
</figure>
2019-04-19T00:00:00+03:00https://nessuent.net/posts/2021-08-17_concept_to_color.htmlMapping concepts to colors (terribly) with the Oklab perceptual colospace2022-10-22T13:38:25.114150+00:00<h2 id="tldr">TL;DR</h2>
<ul>
<li><em>What?</em> I wanted a way to semi-automate associating colors to topic tags stories posted on <a href="https://sic.pm" class="uri">https://sic.pm</a>.</li>
<li><em>Why not any color?</em> I was curious to see what was reasonable within this approach.</li>
<li><em>What’s the approach?</em> I had no idea about colorspaces or image processing before I started. My strategy would be to download the top results of a query using DuckDuckGo image search, calculate their dominant colors, and then calculate the overall dominant colors. Any suggestions/corrections are most welcome!</li>
<li><em>Show me the result</em>:</li>
</ul>
<figure>
<style>
.results {
display: flex;
gap: 2px;
max-width: 402px;
width: 100%;
flex-flow: row wrap;
justify-content: space-between;
}
.colors figure {
padding: 0px;
}
.results figure {
border: 3px solid black;
padding: 14px;
border-radius: 4px;
display: grid;
grid-template-rows: auto 1fr;
grid-template-columns: 1fr;
max-width: 200px !important;
max-width: min(200px,calc(var(--max-width) / 2.05)) !important;
max-height: max-content;
margin: 0px;
}
.results table {
table-layout: fixed;
width: 100%;
word-break: break-all;
font-size: 70%;
height: min-content;
}
.results figcaption {
display: table-caption;
padding: 11px;
text-align: center;
word-break: break-all;
padding: 11px;
text-align: center;
border: 2px solid black;
}
.results figure div {
display: flex;
flex-flow: row wrap;
}
.results caption {
font-size: 1rem;
}
</style>
<div class="results colors">
<figure style="background-color: #2d5b76; --red: 45.78248429808607; --green: 91.8769631030122; --blue: 118.32691000698078; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.45’, ‘-0.04’, ‘-0.06’]</code>
</td>
<td>
<code>[‘200.00’, ‘0.44’, ‘0.32’]</code>
</td>
<td>
<code>[‘46.00’, ‘92.00’, ‘120.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #2d5b76;">
#2d5b76
</figcaption>
</figure>
<figure style="background-color: #d73e5f; --red: 215.41961837894783; --green: 62.36380170387439; --blue: 95.07985352814016; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.60’, ‘0.18’, ‘0.04’]</code>
</td>
<td>
<code>[‘350.00’, ‘0.66’, ‘0.54’]</code>
</td>
<td>
<code>[‘220.00’, ‘62.00’, ‘95.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #d73e5f;">
#d73e5f
</figcaption>
</figure>
<figure style="background-color: #338193; --red: 51.156000630968656; --green: 129.21135730256776; --blue: 147.67130242125629; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.56’, ‘-0.07’, ‘-0.05’]</code>
</td>
<td>
<code>[‘190.00’, ‘0.49’, ‘0.39’]</code>
</td>
<td>
<code>[‘51.00’, ‘130.00’, ‘150.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #338193;">
#338193
</figcaption>
</figure>
<figure style="background-color: #1e4eaf; --red: 30.489464307028793; --green: 78.70887638338755; --blue: 175.99797510122806; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.45’, ‘-0.02’, ‘-0.16’]</code>
</td>
<td>
<code>[‘220.00’, ‘0.70’, ‘0.40’]</code>
</td>
<td>
<code>[‘30.00’, ‘79.00’, ‘180.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #1e4eaf;">
#1e4eaf
</figcaption>
</figure>
<figure style="background-color: #3a7c59; --red: 58.932726729736224; --green: 124.57603231390945; --blue: 89.32705127504498; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.53’, ‘-0.08’, ‘0.03’]</code>
</td>
<td>
<code>[‘150.00’, ‘0.36’, ‘0.36’]</code>
</td>
<td>
<code>[‘59.00’, ‘120.00’, ‘89.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #3a7c59;">
#3a7c59
</figcaption>
</figure>
<figure style="background-color: #16217e; --red: 22.588571936125955; --green: 33.64672997706896; --blue: 126.99057383737028; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.32’, ‘-0.00’, ‘-0.15’]</code>
</td>
<td>
<code>[‘230.00’, ‘0.70’, ‘0.29’]</code>
</td>
<td>
<code>[‘23.00’, ‘34.00’, ‘130.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #16217e;">
#16217e
</figcaption>
</figure>
<figure style="background-color: #89c658; --red: 137.46747549189422; --green: 198.43482094174996; --blue: 88.30022101081092; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.76’, ‘-0.11’, ‘0.11’]</code>
</td>
<td>
<code>[‘93.00’, ‘0.49’, ‘0.56’]</code>
</td>
<td>
<code>[‘140.00’, ‘200.00’, ‘88.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #89c658;">
#89c658
</figcaption>
</figure>
<figure style="background-color: #e9a156; --red: 233.23661180948883; --green: 161.34857047951013; --blue: 86.39521525767827; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.77’, ‘0.05’, ‘0.11’]</code>
</td>
<td>
<code>[‘31.00’, ‘0.77’, ‘0.63’]</code>
</td>
<td>
<code>[‘230.00’, ‘160.00’, ‘86.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #e9a156;">
#e9a156
</figcaption>
</figure>
</div>
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “programming”
</figcaption>
</figure>
<h2 id="whats-a-colorspace-and-whats-perceptually-uniform">What’s a colorspace and what’s “Perceptually uniform”?</h2>
<p>A <em>colorspace</em> is basically a way to model colors to attributes. The well known RGB colorspace maps colors to <em>Red</em>, <em>Green</em> and <em>Blue</em>.</p>
<p>If that space has three attributes, we can view them as coordinates on a 3D space (Any <em>n</em> attributes can be viewed as an <em>n</em>-dimensional vector space). Then we define color distance as the usual Euclidean distance we use for tangible stuff in the real world.</p>
<p>A uniformly perceptual colorspace aims to have the following identity: “identical spatial distance between two colors equals identical amount of perceived color difference”. The actual definitions of those terms can be found in color science books and research.</p>
<p><a href="https://bottosson.github.io/posts/oklab/">Oklab</a> is a perceptual color space designed by Björn Ottosson to make working with colors in image processing easier. After reading the introductory blog post, I wondered if I could apply it to finding dominant colors of an image.</p>
<p>Oklab has three coordinates:</p>
<ul>
<li><em>L</em> perceived lightness</li>
<li><em>a</em> how green/red the color is</li>
<li><em>b</em> how blue/yellow the color is</li>
</ul>
<figure>
<img src="/static/images/n8.svg" alt="" loading="lazy">
<figcaption>
Uniformly sampling the Oklab colorspace in 8 parts per coordinate.
</figcaption>
</figure>
<figure>
<img src="/static/images/n16.svg" alt="" loading="lazy">
<figcaption>
Uniformly sampling the Oklab colorspace in 16 parts per coordinate.
</figcaption>
</figure>
<h2 id="dominant-colors">Dominant colors</h2>
<p>I guess we would take an image and average all colors. What would that produce?</p>
<figure>
<img src="/static/images/avg_d2c6b6.jpg" alt="" loading="lazy">
<figcaption>
<span style="background-color: #d2c6b6;">#d2c6b6</span>
</figcaption>
</figure>
<p>Terrible. Obviously the approach can’t work with multiple colors apparent in a picture. If the picture was mostly one color it’d be somewhat useful:</p>
<figure>
<img src="/static/images/avg_94706f.jpg" alt="" loading="lazy">
<figcaption>
<span style="background-color: #94706f;">#94706f</span>
</figcaption>
</figure>
<h2 id="k-means-clustering"><em>k</em>-means clustering</h2>
<p>From signal processing comes this dazzling technique: Given a set of colors <em>c</em>, partition them to <em>k</em> buckets as follows:</p>
<ol type="1">
<li>Initially assign <span class="math inline"><em>k</em></span> average colors somehow. You can pick them randomly for example. We will incrementally improve on those averages to arrive to a <em>centroid</em> color, or the mean (average) color of a cluster.</li>
<li>Assign every color <em>c</em> to the average closest to it <em>m</em><sub>κ</sub> by calculating Euclidean distances to each <em>m</em>.</li>
<li>Recalculate <em>m</em><sub>κ</sub> as the average of the updated cluster <em>κ</em>.</li>
<li>Repeat until assignments are the same as the previous step; we’ve reached convergence which is not necessarily correct/optimal.</li>
</ol>
<p>Since we will use a perceptually uniform colorspace, we expect each cluster to be perceivably close to the actual colors it contains.</p>
<p>And since we will be working with lots of sample images, we can calculate the overall dominant colors by putting all the colors together.</p>
<h2 id="implementation">Implementation</h2>
<p>To visualize the results, I chose to calculate the dominant colors for each image, then calculate the overall dominant colors from those.</p>
<p>I also uniformly split the Oklab colorspace into colors and clustered all the dominant colors again, in order to see the difference of the calculated dominant colors and the uniformly sampled ones:</p>
<figure style="width: 100%;max-width: 100% !important;">
<img style="width: 100%;object-fit: scale-down;max-width: unset;" width="402" src="/static/images/clusters.html.svg" alt="" loading="lazy">
<figcaption>
Uniformly partitioning dominant colors.
</figcaption>
</figure>
<p>The image results for most queries are stock photos or text, hence there is a lot of black and white. We can deduce how black or greyscale looking is a color by looking at its coordinates. In Oklab, the <em>a</em>, <em>b</em> coordinates will be close to zero. In <em>HSL</em> (Hue-Saturation-Lightness) a low <em>L</em> value means the color is close to black. We can discard such colors by checking those values.</p>
<h2 id="results">Results</h2>
<p>Searching for non abstract things such as fruits returns pictures of the things themselves so we get good results:</p>
<figure>
<img src="/static/images/banana.html.svg" alt="" loading="lazy">
<div class="results colors">
<figure style="background-color: #c4ab46;--red: 196.28318248390545; --green: 171.22987781738678; --blue: 70.06462577833034; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.74’, ‘-0.01’, ‘0.12’]</code>
</td>
<td>
<code>[‘48.00’, ‘0.52’, ‘0.52’]</code>
</td>
<td>
<code>[‘200.00’, ‘170.00’, ‘70.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #c4ab46;">
#c4ab46
</figcaption>
</figure>
<figure style="background-color: #46451f;--red: 70.11154443210407; --green: 69.33670729746845; --blue: 31.23333262699616; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.38’, ‘-0.02’, ‘0.05’]</code>
</td>
<td>
<code>[‘59.00’, ‘0.38’, ‘0.20’]</code>
</td>
<td>
<code>[‘70.00’, ‘69.00’, ‘31.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #46451f;">
#46451f
</figcaption>
</figure>
<figure style="background-color: #e1e27f;--red: 225.90423044792516; --green: 226.05870308646374; --blue: 127.41786090109363; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.89’, ‘-0.04’, ‘0.12’]</code>
</td>
<td>
<code>[‘60.00’, ‘0.63’, ‘0.69’]</code>
</td>
<td>
<code>[‘230.00’, ‘230.00’, ‘130.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #e1e27f;">
#e1e27f
</figcaption>
</figure>
<figure style="background-color: #1c190c;--red: 28.56983700260185; --green: 25.626647567386716; --blue: 12.551556034953945; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.22’, ‘-0.00’, ‘0.02’]</code>
</td>
<td>
<code>[‘49.00’, ‘0.39’, ‘0.08’]</code>
</td>
<td>
<code>[‘29.00’, ‘26.00’, ‘13.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #1c190c;">
#1c190c
</figcaption>
</figure>
<figure style="background-color: #9d8433;--red: 157.89721444994035; --green: 132.77263694561853; --blue: 51.19642464048814; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.62’, ‘-0.00’, ‘0.10’]</code>
</td>
<td>
<code>[‘46.00’, ‘0.51’, ‘0.41’]</code>
</td>
<td>
<code>[‘160.00’, ‘130.00’, ‘51.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #9d8433;">
#9d8433
</figcaption>
</figure>
<figure style="background-color: #7c6732;--red: 124.84816474230027; --green: 103.04763841029607; --blue: 50.675136743583494; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.52’, ‘0.00’, ‘0.08’]</code>
</td>
<td>
<code>[‘42.00’, ‘0.42’, ‘0.34’]</code>
</td>
<td>
<code>[‘120.00’, ‘100.00’, ‘51.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #7c6732;">
#7c6732
</figcaption>
</figure>
</div>
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “banana” (is that an impostor?)
</figcaption>
</figure>
<p>Searching for <em>pharmaceuticals</em> returns lots of pictures of colorful pills:</p>
<figure>
<img src="/static/images/pharma.html.svg" alt="" loading="lazy">
<div class="results colors">
<figure style="background-color: #4d81ae;--red: 77.33534012784165; --green: 129.27371312709678; --blue: 174.63535437467024; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.59’, ‘-0.04’, ‘-0.08’]</code>
</td>
<td>
<code>[‘210.00’, ‘0.39’, ‘0.49’]</code>
</td>
<td>
<code>[‘77.00’, ‘130.00’, ‘170.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #4d81ae;">
#4d81ae
</figcaption>
</figure>
<figure style="background-color: #4d585a;--red: 77.65747619972743; --green: 88.33947901269752; --blue: 90.7305623996395; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.45’, ‘-0.01’, ‘-0.01’]</code>
</td>
<td>
<code>[‘190.00’, ‘0.08’, ‘0.33’]</code>
</td>
<td>
<code>[‘78.00’, ‘88.00’, ‘91.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #4d585a;">
#4d585a
</figcaption>
</figure>
<figure style="background-color: #20479d;--red: 32.66844241679075; --green: 71.85160453317006; --blue: 157.05401304300975; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.43’, ‘-0.02’, ‘-0.15’]</code>
</td>
<td>
<code>[‘220.00’, ‘0.66’, ‘0.37’]</code>
</td>
<td>
<code>[‘33.00’, ‘72.00’, ‘160.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #20479d;">
#20479d
</figcaption>
</figure>
<figure style="background-color: #b1cfea;--red: 177.11718514939957; --green: 207.1476864074912; --blue: 234.6288950167034; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.84’, ‘-0.02’, ‘-0.05’]</code>
</td>
<td>
<code>[‘210.00’, ‘0.59’, ‘0.81’]</code>
</td>
<td>
<code>[‘180.00’, ‘210.00’, ‘230.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #b1cfea;">
#b1cfea
</figcaption>
</figure>
<figure style="background-color: #ba3d3e;--red: 186.1693599015324; --green: 61.36541273761866; --blue: 62.32060313682186; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.54’, ‘0.15’, ‘0.07’]</code>
</td>
<td>
<code>[‘360.00’, ‘0.50’, ‘0.49’]</code>
</td>
<td>
<code>[‘190.00’, ‘61.00’, ‘62.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #ba3d3e;">
#ba3d3e
</figcaption>
</figure>
<figure style="background-color: #418b58;--red: 65.61860176956954; --green: 139.66843518364155; --blue: 88.30085126039629; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.58’, ‘-0.10’, ‘0.05’]</code>
</td>
<td>
<code>[‘140.00’, ‘0.36’, ‘0.40’]</code>
</td>
<td>
<code>[‘66.00’, ‘140.00’, ‘88.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #418b58;">
#418b58
</figcaption>
</figure>
</div>
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “pharmaceuticals”
</figcaption>
</figure>
<p>Searching for <em>ethics</em> returns pictures of signs that point to stuff such as “Right” and “Wrong” and “Principles”:</p>
<figure>
<img src="/static/images/ethics.html.svg" alt="" loading="lazy">
<div class="results colors">
<figure style="background-color: #99b757;--red: 153.5850942678971; --green: 183.40548984857804; --blue: 87.99736877215766; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.74’, ‘-0.07’, ‘0.11’]</code>
</td>
<td>
<code>[‘79.00’, ‘0.40’, ‘0.53’]</code>
</td>
<td>
<code>[‘150.00’, ‘180.00’, ‘88.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #99b757;">
#99b757
</figcaption>
</figure>
<figure style="background-color: #76a6c8;--red: 118.38853932231477; --green: 166.55909717803968; --blue: 200.02588785203736; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.71’, ‘-0.04’, ‘-0.06’]</code>
</td>
<td>
<code>[‘200.00’, ‘0.43’, ‘0.62’]</code>
</td>
<td>
<code>[‘120.00’, ‘170.00’, ‘200.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #76a6c8;">
#76a6c8
</figcaption>
</figure>
<figure style="background-color: #edede6;--red: 237.0745909259664; --green: 237.5089358669673; --blue: 230.94915954330384; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.95’, ‘-0.00’, ‘0.01’]</code>
</td>
<td>
<code>[‘64.00’, ‘0.16’, ‘0.92’]</code>
</td>
<td>
<code>[‘240.00’, ‘240.00’, ‘230.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #edede6;">
#edede6
</figcaption>
</figure>
<figure style="background-color: #a99387;--red: 169.9109720706113; --green: 147.2605959334244; --blue: 135.91314618149732; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.68’, ‘0.02’, ‘0.02’]</code>
</td>
<td>
<code>[‘20.00’, ‘0.17’, ‘0.60’]</code>
</td>
<td>
<code>[‘170.00’, ‘150.00’, ‘140.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #a99387;">
#a99387
</figcaption>
</figure>
</div>
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “ethics”
</figcaption>
</figure>
<p>Searching for <em>design</em> returns a boring sea of brown and beige thanks to interior design trends:</p>
<figure>
<img src="/static/images/design.html.svg" alt="" loading="lazy">
<div class="results colors">
<figure style="background-color: #93887b;--red: 147.44032737387627; --green: 136.9791971867938; --blue: 123.48551940720034; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.64’, <‘0.01’, ‘0.02’]</code>
</td>
<td>
<code>[‘34.00’, ‘0.10’, ‘0.53’]</code>
</td>
<td>
<code>[‘150.00’, ‘140.00’, ‘120.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #93887b;">
#93887b
</figcaption>
</figure>
<figure style="background-color: #c2b7a9;--red: 194.24663181106135; --green: 183.9096475302234; --blue: 169.81091557028293; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.79’, ‘0.01’, ‘0.02’]</code>
</td>
<td>
<code>[‘35.00’, ‘0.17’, ‘0.71’]</code>
</td>
<td>
<code>[‘190.00’, ‘180.00’, ‘170.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #c2b7a9;">
#c2b7a9
</figcaption>
</figure>
<figure style="background-color: #cbc8c2;--red: 203.32969762370587; --green: 200.8009366157517; --blue: 194.45173078411435; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.84’, ‘0.00’, ‘0.01’]</code>
</td>
<td>
<code>[‘43.00’, ‘0.08’, ‘0.78’]</code>
</td>
<td>
<code>[‘200.00’, ‘200.00’, ‘190.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #cbc8c2;">
#cbc8c2
</figcaption>
</figure>
<figure style="background-color: #74675c;--red: 116.99319983117225; --green: 103.74989161529457; --blue: 92.26608788946902; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.53’, ‘0.01’, ‘0.02’]</code>
</td>
<td>
<code>[‘28.00’, ‘0.12’, ‘0.41’]</code>
</td>
<td>
<code>[‘120.00’, ‘100.00’, ‘92.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #74675c;">
#74675c
</figcaption>
</figure>
</div>
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “design”
</figcaption>
</figure>
<p>Searching for <em>programming</em> identifies the classic green terminal color along with other syntax highlighting palettes:</p>
<figure>
<img src="/static/images/programming.html.svg" alt="" loading="lazy">
<div class="results colors">
<figure style="background-color: #d73e5f; --red: 215.41961837894783; --green: 62.36380170387439; --blue: 95.07985352814016; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.60’, ‘0.18’, ‘0.04’]</code>
</td>
<td>
<code>[‘350.00’, ‘0.66’, ‘0.54’]</code>
</td>
<td>
<code>[‘220.00’, ‘62.00’, ‘95.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #d73e5f;">
#d73e5f
</figcaption>
</figure>
<figure style="background-color: #1e4eaf; --red: 30.489464307028793; --green: 78.70887638338755; --blue: 175.99797510122806; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.45’, ‘-0.02’, ‘-0.16’]</code>
</td>
<td>
<code>[‘220.00’, ‘0.70’, ‘0.40’]</code>
</td>
<td>
<code>[‘30.00’, ‘79.00’, ‘180.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #1e4eaf;">
#1e4eaf
</figcaption>
</figure>
<figure style="background-color: #89c658; --red: 137.46747549189422; --green: 198.43482094174996; --blue: 88.30022101081092; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.76’, ‘-0.11’, ‘0.11’]</code>
</td>
<td>
<code>[‘93.00’, ‘0.49’, ‘0.56’]</code>
</td>
<td>
<code>[‘140.00’, ‘200.00’, ‘88.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #89c658;">
#89c658
</figcaption>
</figure>
<figure style="background-color: #e9a156; --red: 233.23661180948883; --green: 161.34857047951013; --blue: 86.39521525767827; --aa-brightness: ((var(--red) * 299) + (var(--green) * 587) + (var(--blue) * 114)) / 1000; --aa-color: calc((var(--aa-brightness) - 128) * -1000); color: rgb(var(--aa-color), var(--aa-color), var(--aa-color));">
<table>
<thead>
<tr>
<th>
Oklab
</th>
<th>
HSL
</th>
<th>
RGB
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<code>[‘0.77’, ‘0.05’, ‘0.11’]</code>
</td>
<td>
<code>[‘31.00’, ‘0.77’, ‘0.63’]</code>
</td>
<td>
<code>[‘230.00’, ‘160.00’, ‘86.00’]</code>
</td>
</tr>
</tbody>
</table>
<figcaption style="background-color: #e9a156;">
#e9a156
</figcaption>
</figure>
</div>
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “programming”
</figcaption>
</figure>
<p>Finally, <em>philosophy</em> returns pictures of books and statues, so the results are predictable and omitted:</p>
<figure>
<img width="402" src="/static/images/philosophy.html.svg" alt="" loading="lazy">
<figcaption style="caption-side: top; border-radius: 0px; border-top-left-radius: 5px; border-top-right-radius: 5px;">
Results for “philosophy”
</figcaption>
</figure>
<h2 id="improving-the-sample-source">Improving the sample source</h2>
<p>I’ve had some luck getting “better” results by searching for “book about {query}” and “book about {query} cover” expecting topical books to share color schemes, like the distinctive palettes O’Reilly uses in its programming books.</p>
<p>I found Google Images to show less junk results but they have no API you can use without an account.</p>
<h2 id="conclusions-and-notes">Conclusions and notes</h2>
<p>As expected, this doesn’t produce particularly mind blowing results since abstract concepts lack color association in general. Even if you have any type of vision synesthesia, the colors you see are usually unique for each person.</p>
<p>To get back to the original motivation behind this experiment, which was associating post tags with colors: you can achieve this by clustering existing colors and for each new tag calculate dominant colors, and choose one that belongs to the smallest cluster. That way you can avoid common colors like black/white/blue/orange saturating your tag cloud.</p>
<h2 id="sample-code">Sample code</h2>
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true"></a><span class="im">import</span> decimal</span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true"></a><span class="im">import</span> itertools</span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true"></a><span class="im">from</span> wand.image <span class="im">import</span> Image</span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true"></a><span class="im">import</span> numpy <span class="im">as</span> np</span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true"></a><span class="im">from</span> scipy.cluster.vq <span class="im">import</span> vq, kmeans</span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true"></a><span class="im">import</span> colorio</span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true"></a></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true"></a>wand_color_to_arr <span class="op">=</span> <span class="kw">lambda</span> c: np.array([c.red_int8, c.green_int8, c.blue_int8])</span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true"></a></span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true"></a>OKLAB <span class="op">=</span> colorio.cs.OKLAB()</span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true"></a>color_abs <span class="op">=</span> <span class="kw">lambda</span> v: <span class="bn">0xFF</span> <span class="cf">if</span> v <span class="op">></span> <span class="bn">0xFF</span> <span class="cf">else</span> v <span class="cf">if</span> v <span class="op">>=</span> <span class="dv">0</span> <span class="cf">else</span> <span class="dv">0</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true"></a></span>
<span id="cb1-13"><a href="#cb1-13" aria-hidden="true"></a>oklab_to_rgb255 <span class="op">=</span> <span class="kw">lambda</span> o: OKLAB.to_rgb255(o)</span>
<span id="cb1-14"><a href="#cb1-14" aria-hidden="true"></a>rgb_to_hex <span class="op">=</span> <span class="kw">lambda</span> rgb: <span class="st">"#</span><span class="sc">%s</span><span class="st">"</span> <span class="op">%</span> <span class="st">""</span>.join((<span class="st">"</span><span class="sc">%02x</span><span class="st">"</span> <span class="op">%</span> p <span class="cf">for</span> p <span class="kw">in</span> rgb))</span>
<span id="cb1-15"><a href="#cb1-15" aria-hidden="true"></a>oklab_to_hex <span class="op">=</span> <span class="kw">lambda</span> o: rgb_to_hex(<span class="bu">map</span>(color_abs, <span class="bu">map</span>(<span class="bu">int</span>, oklab_to_rgb255(o))))</span>
<span id="cb1-16"><a href="#cb1-16" aria-hidden="true"></a></span>
<span id="cb1-17"><a href="#cb1-17" aria-hidden="true"></a>dec_ctx <span class="op">=</span> decimal.Context(prec<span class="op">=</span><span class="dv">2</span>, rounding<span class="op">=</span>decimal.ROUND_HALF_DOWN)</span>
<span id="cb1-18"><a href="#cb1-18" aria-hidden="true"></a>arr_display <span class="op">=</span> <span class="kw">lambda</span> arr: [<span class="st">"</span><span class="sc">%.2f</span><span class="st">"</span> <span class="op">%</span> dec_ctx.create_decimal_from_float(i) <span class="cf">for</span> i <span class="kw">in</span> arr]</span>
<span id="cb1-19"><a href="#cb1-19" aria-hidden="true"></a></span>
<span id="cb1-20"><a href="#cb1-20" aria-hidden="true"></a></span>
<span id="cb1-21"><a href="#cb1-21" aria-hidden="true"></a><span class="kw">def</span> image_to_colors(img: Image):</span>
<span id="cb1-22"><a href="#cb1-22" aria-hidden="true"></a> img.thumbnail(<span class="dv">200</span>, <span class="dv">200</span>)</span>
<span id="cb1-23"><a href="#cb1-23" aria-hidden="true"></a> colors <span class="op">=</span> <span class="bu">set</span>(c <span class="cf">for</span> row <span class="kw">in</span> img <span class="cf">for</span> c <span class="kw">in</span> row)</span>
<span id="cb1-24"><a href="#cb1-24" aria-hidden="true"></a> ret <span class="op">=</span> []</span>
<span id="cb1-25"><a href="#cb1-25" aria-hidden="true"></a> <span class="cf">for</span> c <span class="kw">in</span> colors:</span>
<span id="cb1-26"><a href="#cb1-26" aria-hidden="true"></a> ret.append(OKLAB.from_rgb255(wand_color_to_arr(c)))</span>
<span id="cb1-27"><a href="#cb1-27" aria-hidden="true"></a> <span class="cf">return</span> ret</span>
<span id="cb1-28"><a href="#cb1-28" aria-hidden="true"></a></span>
<span id="cb1-29"><a href="#cb1-29" aria-hidden="true"></a></span>
<span id="cb1-30"><a href="#cb1-30" aria-hidden="true"></a><span class="kw">class</span> Bucket:</span>
<span id="cb1-31"><a href="#cb1-31" aria-hidden="true"></a> <span class="kw">def</span> <span class="fu">__init__</span>(<span class="va">self</span>, rep):</span>
<span id="cb1-32"><a href="#cb1-32" aria-hidden="true"></a> <span class="va">self</span>.rep <span class="op">=</span> rep</span>
<span id="cb1-33"><a href="#cb1-33" aria-hidden="true"></a> <span class="va">self</span>.colors <span class="op">=</span> []</span>
<span id="cb1-34"><a href="#cb1-34" aria-hidden="true"></a></span>
<span id="cb1-35"><a href="#cb1-35" aria-hidden="true"></a> <span class="kw">def</span> <span class="fu">__len__</span>(<span class="va">self</span>):</span>
<span id="cb1-36"><a href="#cb1-36" aria-hidden="true"></a> <span class="cf">return</span> <span class="bu">len</span>(<span class="va">self</span>.colors)</span>
<span id="cb1-37"><a href="#cb1-37" aria-hidden="true"></a></span>
<span id="cb1-38"><a href="#cb1-38" aria-hidden="true"></a> <span class="kw">def</span> append(<span class="va">self</span>, color):</span>
<span id="cb1-39"><a href="#cb1-39" aria-hidden="true"></a> <span class="va">self</span>.colors.append(color)</span>
<span id="cb1-40"><a href="#cb1-40" aria-hidden="true"></a></span>
<span id="cb1-41"><a href="#cb1-41" aria-hidden="true"></a></span>
<span id="cb1-42"><a href="#cb1-42" aria-hidden="true"></a><span class="kw">def</span> dominant_colors(oks, n<span class="op">=</span><span class="dv">20</span>):</span>
<span id="cb1-43"><a href="#cb1-43" aria-hidden="true"></a> _r, _ <span class="op">=</span> kmeans(oks, <span class="bu">min</span>(n, <span class="bu">len</span>(oks)))</span>
<span id="cb1-44"><a href="#cb1-44" aria-hidden="true"></a> <span class="co"># sort dominant colors by cluster size</span></span>
<span id="cb1-45"><a href="#cb1-45" aria-hidden="true"></a> buckets <span class="op">=</span> [Bucket(rep) <span class="cf">for</span> rep <span class="kw">in</span> _r]</span>
<span id="cb1-46"><a href="#cb1-46" aria-hidden="true"></a> _s, _ <span class="op">=</span> vq(oks, _r)</span>
<span id="cb1-47"><a href="#cb1-47" aria-hidden="true"></a> <span class="cf">for</span> idx, c <span class="kw">in</span> <span class="bu">enumerate</span>(oks):</span>
<span id="cb1-48"><a href="#cb1-48" aria-hidden="true"></a> bucket_idx <span class="op">=</span> _s[idx]</span>
<span id="cb1-49"><a href="#cb1-49" aria-hidden="true"></a> buckets[bucket_idx].append(c)</span>
<span id="cb1-50"><a href="#cb1-50" aria-hidden="true"></a> buckets.sort(key<span class="op">=</span><span class="kw">lambda</span> b: <span class="bu">len</span>(b), reverse<span class="op">=</span><span class="va">True</span>)</span>
<span id="cb1-51"><a href="#cb1-51" aria-hidden="true"></a> <span class="cf">return</span> [b.rep <span class="cf">for</span> b <span class="kw">in</span> buckets]</span>
<span id="cb1-52"><a href="#cb1-52" aria-hidden="true"></a></span>
<span id="cb1-53"><a href="#cb1-53" aria-hidden="true"></a></span>
<span id="cb1-54"><a href="#cb1-54" aria-hidden="true"></a><span class="kw">def</span> make_uniform_clusters(oks, n<span class="op">=</span><span class="dv">20</span>):</span>
<span id="cb1-55"><a href="#cb1-55" aria-hidden="true"></a> <span class="kw">def</span> make_grid(n<span class="op">=</span><span class="dv">20</span>):</span>
<span id="cb1-56"><a href="#cb1-56" aria-hidden="true"></a> code_steps <span class="op">=</span> np.linspace(<span class="op">-</span><span class="fl">1.0</span>, <span class="fl">1.0</span>, num<span class="op">=</span>n)</span>
<span id="cb1-57"><a href="#cb1-57" aria-hidden="true"></a> <span class="cf">return</span> <span class="bu">list</span>(itertools.product(code_steps, code_steps, code_steps))</span>
<span id="cb1-58"><a href="#cb1-58" aria-hidden="true"></a></span>
<span id="cb1-59"><a href="#cb1-59" aria-hidden="true"></a> prod <span class="op">=</span> make_grid(n)</span>
<span id="cb1-60"><a href="#cb1-60" aria-hidden="true"></a> buckets <span class="op">=</span> [Bucket(rep) <span class="cf">for</span> rep <span class="kw">in</span> prod]</span>
<span id="cb1-61"><a href="#cb1-61" aria-hidden="true"></a> _r, _ <span class="op">=</span> vq(oks, prod)</span>
<span id="cb1-62"><a href="#cb1-62" aria-hidden="true"></a> <span class="cf">for</span> idx, c <span class="kw">in</span> <span class="bu">enumerate</span>(oks):</span>
<span id="cb1-63"><a href="#cb1-63" aria-hidden="true"></a> bucket_idx <span class="op">=</span> _r[idx]</span>
<span id="cb1-64"><a href="#cb1-64" aria-hidden="true"></a> buckets[bucket_idx].append(c)</span>
<span id="cb1-65"><a href="#cb1-65" aria-hidden="true"></a> buckets.sort(key<span class="op">=</span><span class="kw">lambda</span> b: <span class="bu">len</span>(b), reverse<span class="op">=</span><span class="va">True</span>)</span>
<span id="cb1-66"><a href="#cb1-66" aria-hidden="true"></a> <span class="cf">return</span> buckets</span></code></pre></div>
2021-08-17T00:00:00+03:00https://nessuent.net/posts/2021-07-15_link_aggregator.htmlsic.pm is a no-javascript tagged link aggregator community2022-10-22T13:38:25.114139+00:00<p><a href="https://sic.pm/" class="uri">https://sic.pm/</a></p>
<p><a href="https://github.com/epilys/sic" class="uri">https://github.com/epilys/sic</a></p>
2021-07-15T00:00:00+03:00https://nessuent.net/posts/2021-08-14_tag-wasm-rust.htmlTag input assistant for <select> elements in Rust/wasm2022-10-22T13:38:25.114127+00:00<p>Choosing multiple options with the plain HTML <code><select></code> element limits you to what the browser chooses to display it as. This is necessary because it has to be accessible to assistive technologies that would choose to render it differently. Here’s how <code><select></code> looks in my browser (Firefox):</p>
<p><img src="/static/images/wasm1.png" /></p>
<p>In the post submission form of the <a href="https://sic.pm" class="uri">https://sic.pm</a> link aggregator community you can select tags to categorise your post. I wrote a small “input assistant” module in Rust and Webassembly that enhances but not replaces the <code><select></code> element. The dynamic usage is not required since the <code><select></code> element works always even with javascript disabled. Here’s the finished result:</p>
<figure>
<video controls loop="true" autoplay="true" src="/static/images/wasm2.webm">
<a href="/static/images/wasm2.webm">View video</a>
</video>
</figure>
<p>The code is AGPL-3.0 licensed and is located <a href="https://github.com/epilys/sic/tree/main/tools/tag-input-wasm">here</a>.</p>
<h2 id="project-setup">Project setup</h2>
<p>I followed the <a href="https://rustwasm.github.io/book/game-of-life/hello-world.html">hello world</a> example from the official <code>rustwasm</code> guide. It uses the <code>wasm-pack</code> tool to compile your Rust project to a <code>wasm</code> module. I chose not to use <code>npm</code> and any javascript other than what’s strictly necessary.</p>
<p>The browser and javascript APIs are exposed to Rust via the <code>js-sys</code> and <code>web-sys</code> crates, so we can do what we would normally do in Javascript: set up event callbacks and manipulate the DOM. For inspiration, I followed the general idea outlined in this logrocket.com guide: <a href="https://blog.logrocket.com/building-a-tag-input-field-component-for-react/">Building a tag input field component for React</a>.</p>
<p>The <code>web-sys</code> crate exposes each API as different crate features. By default, it has none. We explicitly enable the features we end up needing:</p>
<pre class="toml"><code>[dependencies]
wasm-bindgen = "0.2.63"
js-sys = "0.3.52"
web-sys = { version = "0.3.52", features = ["Document", "Text", "Window", "HtmlElement", "Element", "console", "HtmlInputElement", "KeyboardEvent", "Node", "NodeList", "HtmlOptionElement", "EventTarget", "HtmlSpanElement", "HtmlSelectElement"] }</code></pre>
<h2 id="design-considerations">Design considerations</h2>
<p>We will need a way to track the state of the <code><select></code> field so we create a <code>State</code> struct singleton that we put behind a <code>Mutex</code> and then an <code>Arc</code>. This way when registering the event callbacks we can pass around a cloned state reference and access it from there. Every callback will have its own <code>Arc<Mutex<State>></code>.</p>
<p>(Note: this is the general design pattern I followed when porting my terminal e-mail client <a href="https://github.com/meli/meli">meli</a> to wasm for <a href="https://meli.delivery/wasm2.html">an interactive web demo</a>. The terminal is simulated by rendering an <code><svg></code> element with each terminal cell.)</p>
<p>We need a way to know what options are valid. One could just read the options from <code><select></code> but I chose to read them from a <code>json</code> script element in order to include associated colors for each tag. The <code>json</code> <code><script></code> element should contain a dictionary of valid options as keys and hex colors as values and render as:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode html"><code class="sourceCode html"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true"></a><span class="kw"><script</span><span class="ot"> id=</span><span class="st">"tags_json"</span><span class="ot"> type=</span><span class="st">"application/json"</span><span class="kw">></span>{<span class="st">"programming languages"</span><span class="op">:</span> <span class="st">"#ffffff"</span><span class="op">,</span> <span class="st">"python"</span><span class="op">:</span> <span class="st">"#3776ab"</span><span class="op">,</span> }<span class="kw"></script></span></span></code></pre></div>
<p>Finally, a <code><datalist></code> element will be used to enable autocomplete for the input.</p>
<h2 id="implementation">Implementation</h2>
<p>The <code>State</code> definition:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode rust"><code class="sourceCode rust"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true"></a><span class="kw">struct</span> State <span class="op">{</span></span>
<span id="cb3-2"><a href="#cb3-2" aria-hidden="true"></a> tags<span class="op">:</span> <span class="dt">Vec</span><span class="op"><</span><span class="dt">String</span><span class="op">>,</span></span>
<span id="cb3-3"><a href="#cb3-3" aria-hidden="true"></a> is_key_released<span class="op">:</span> <span class="dt">bool</span><span class="op">,</span> <span class="co">// Track key release (see below)</span></span>
<span id="cb3-4"><a href="#cb3-4" aria-hidden="true"></a> valid_tags_set<span class="op">:</span> <span class="dt">Vec</span><span class="op"><</span><span class="dt">String</span><span class="op">>,</span></span>
<span id="cb3-5"><a href="#cb3-5" aria-hidden="true"></a> current_input<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-6"><a href="#cb3-6" aria-hidden="true"></a> valid_tags_map<span class="op">:</span> HashMap<span class="op"><</span><span class="dt">String</span><span class="op">,</span> (<span class="dt">u8</span><span class="op">,</span> <span class="dt">u8</span><span class="op">,</span> <span class="dt">u8</span>)<span class="op">>,</span></span>
<span id="cb3-7"><a href="#cb3-7" aria-hidden="true"></a> remove_tag_cb<span class="op">:</span> <span class="pp">js_sys::</span>Function<span class="op">,</span></span>
<span id="cb3-8"><a href="#cb3-8" aria-hidden="true"></a> field_name<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-9"><a href="#cb3-9" aria-hidden="true"></a> select_element_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-10"><a href="#cb3-10" aria-hidden="true"></a> tag_list_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-11"><a href="#cb3-11" aria-hidden="true"></a> input_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-12"><a href="#cb3-12" aria-hidden="true"></a> datalist_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-13"><a href="#cb3-13" aria-hidden="true"></a> msg_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb3-14"><a href="#cb3-14" aria-hidden="true"></a> singular_name<span class="op">:</span> <span class="dt">String</span><span class="op">,</span> <span class="co">/* The singular name of what the user calls the options,</span></span>
<span id="cb3-15"><a href="#cb3-15" aria-hidden="true"></a><span class="co"> so that we can display it in error messages */</span></span>
<span id="cb3-16"><a href="#cb3-16" aria-hidden="true"></a><span class="op">}</span></span></code></pre></div>
<p>with the following methods:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode rust"><code class="sourceCode rust"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true"></a> add_tag(<span class="op">&</span><span class="kw">mut</span> <span class="kw">self</span><span class="op">,</span> tag<span class="op">:</span> <span class="dt">String</span>) <span class="op">-></span> <span class="pp">std::result::</span><span class="dt">Result</span><span class="op"><</span>()<span class="op">,</span> JsValue<span class="op">></span></span>
<span id="cb4-2"><a href="#cb4-2" aria-hidden="true"></a> pop(<span class="op">&</span><span class="kw">mut</span> <span class="kw">self</span>) <span class="op">-></span> <span class="dt">Option</span><span class="op"><</span><span class="dt">String</span><span class="op">></span> <span class="op">:</span> method</span>
<span id="cb4-3"><a href="#cb4-3" aria-hidden="true"></a> remove_tag(<span class="op">&</span><span class="kw">mut</span> <span class="kw">self</span><span class="op">,</span> event<span class="op">:</span> <span class="pp">web_sys::</span>Event) <span class="op">-></span> <span class="pp">std::result::</span><span class="dt">Result</span><span class="op"><</span>()<span class="op">,</span> JsValue<span class="op">></span></span>
<span id="cb4-4"><a href="#cb4-4" aria-hidden="true"></a> update_datalist(<span class="op">&</span><span class="kw">mut</span> <span class="kw">self</span>) <span class="op">-></span> <span class="pp">std::result::</span><span class="dt">Result</span><span class="op"><</span>()<span class="op">,</span> JsValue<span class="op">></span></span>
<span id="cb4-5"><a href="#cb4-5" aria-hidden="true"></a> update_dom(<span class="op">&</span><span class="kw">mut</span> <span class="kw">self</span>) <span class="op">-></span> <span class="pp">std::result::</span><span class="dt">Result</span><span class="op"><</span>()<span class="op">,</span> JsValue<span class="op">></span></span>
<span id="cb4-6"><a href="#cb4-6" aria-hidden="true"></a> update_from_select(<span class="op">&</span><span class="kw">mut</span> <span class="kw">self</span>) <span class="op">-></span> <span class="pp">std::result::</span><span class="dt">Result</span><span class="op"><</span>()<span class="op">,</span> JsValue<span class="op">></span></span></code></pre></div>
<p>The following elements are rendered in the DOM just before the <code><select></code> element:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode html"><code class="sourceCode html"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true"></a><span class="kw"><div</span><span class="ot"> id=</span><span class="st">"id_tags-tag-wasm"</span><span class="ot"> class=</span><span class="st">"tag-wasm"</span><span class="ot"> aria-hidden=</span><span class="st">"true"</span><span class="kw">><div</span><span class="ot"> id=</span><span class="st">"id_tags-tag-wasm-tag-list"</span><span class="ot"> class=</span><span class="st">"tag-wasm-tag-list"</span><span class="kw">></div></span> <span class="kw"><input</span><span class="ot"> id=</span><span class="st">"id_tags-tag-wasm-input"</span><span class="ot"> class=</span><span class="st">"tag-wasm-input"</span><span class="ot"> list=</span><span class="st">"id_tags-tag-wasm-datalist"</span><span class="ot"> type=</span><span class="st">"text"</span><span class="ot"> placeholder=</span><span class="st">"tag name…"</span><span class="kw">></div></span></span>
<span id="cb5-2"><a href="#cb5-2" aria-hidden="true"></a><span class="kw"><div</span><span class="ot"> id=</span><span class="st">"id_tags-tag-wasm-msg"</span><span class="ot"> class=</span><span class="st">"tag-wasm-msg"</span><span class="kw">></div></span></span>
<span id="cb5-3"><a href="#cb5-3" aria-hidden="true"></a><span class="kw"><p</span><span class="ot"> class=</span><span class="st">"after help-text"</span><span class="ot"> aria-hidden=</span><span class="st">"true"</span><span class="kw">></span>Or, <span class="kw"></p></span></span></code></pre></div>
<p>The following events will be monitored:</p>
<ul>
<li><code>onclick</code> event for the outer container <code><div></code>, that will focus the <code>input</code> element inside.</li>
<li><code>oninput</code> event for the <code><select></code>, so that we can synchronise <code>State</code> when it changes</li>
<li><code>onkeydown</code> event for <code><input></code> so that we can detect when a tag name is terminated (I chose the comma character or Enter/Return) or when Backspace is pressed on an empty input which will “pop” the previous tag</li>
<li><code>onkeyup</code> event for <code><input></code> so we can track when a key is released. If Backspace is pressed and released, the user has pressed it repeatedly.</li>
</ul>
<p>Finally, we’ll add a little ‘x’ button to each tag to enable quick removal and register <code>onclick</code> and <code>onkeydown</code> for it. This is where <code>State.remove_tag_cb</code> is needed: we keep one copy of the callback and register it for every rendered tag.</p>
<h3 id="setting-up-the-module-from-javascript">Setting up the module from Javascript</h3>
<p>We register a setup function in the module by annotating it with <code>#[wasm_bindgen]</code>:</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode rust"><code class="sourceCode rust"><span id="cb6-1"><a href="#cb6-1" aria-hidden="true"></a><span class="at">#[</span>wasm_bindgen<span class="at">]</span></span>
<span id="cb6-2"><a href="#cb6-2" aria-hidden="true"></a><span class="kw">pub</span> <span class="kw">fn</span> setup(</span>
<span id="cb6-3"><a href="#cb6-3" aria-hidden="true"></a> singular_name<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb6-4"><a href="#cb6-4" aria-hidden="true"></a> field_name<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb6-5"><a href="#cb6-5" aria-hidden="true"></a> select_element_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb6-6"><a href="#cb6-6" aria-hidden="true"></a> tags_json_id<span class="op">:</span> <span class="dt">String</span><span class="op">,</span></span>
<span id="cb6-7"><a href="#cb6-7" aria-hidden="true"></a>) <span class="op">-></span> <span class="pp">std::result::</span><span class="dt">Result</span><span class="op"><</span>()<span class="op">,</span> JsValue<span class="op">></span> <span class="op">{</span></span>
<span id="cb6-8"><a href="#cb6-8" aria-hidden="true"></a><span class="op">...</span></span></code></pre></div>
<h3 id="interacting-with-the-dom">Interacting with the DOM</h3>
<p>The browser API symbols in <code>web_sys</code> are generally the equivalent Javascript symbols but not in snake-case. This part is mostly the tedious process of setting up elements, attributes and callbacks:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode rust"><code class="sourceCode rust"><span id="cb7-1"><a href="#cb7-1" aria-hidden="true"></a> <span class="kw">let</span> window <span class="op">=</span> <span class="pp">web_sys::</span>window()<span class="op">.</span>expect(<span class="st">"no global `window` exists"</span>)<span class="op">;</span></span>
<span id="cb7-2"><a href="#cb7-2" aria-hidden="true"></a> <span class="kw">let</span> document <span class="op">=</span> window<span class="op">.</span>document()<span class="op">.</span>expect(<span class="st">"should have a document on window"</span>)<span class="op">;</span></span>
<span id="cb7-3"><a href="#cb7-3" aria-hidden="true"></a> <span class="kw">let</span> tag_list_id <span class="op">=</span> <span class="pp">format!</span>(<span class="st">"{}-{}"</span><span class="op">,</span> <span class="op">&</span>select_element_id<span class="op">,</span> TAG_LIST_ID)<span class="op">;</span></span>
<span id="cb7-4"><a href="#cb7-4" aria-hidden="true"></a> <span class="kw">let</span> input_id <span class="op">=</span> <span class="pp">format!</span>(<span class="st">"{}-{}"</span><span class="op">,</span> <span class="op">&</span>select_element_id<span class="op">,</span> INPUT_ID)<span class="op">;</span></span>
<span id="cb7-5"><a href="#cb7-5" aria-hidden="true"></a> <span class="kw">let</span> datalist_id <span class="op">=</span> <span class="pp">format!</span>(<span class="st">"{}-{}"</span><span class="op">,</span> <span class="op">&</span>select_element_id<span class="op">,</span> DATALIST_ID)<span class="op">;</span></span>
<span id="cb7-6"><a href="#cb7-6" aria-hidden="true"></a> <span class="kw">let</span> msg_id <span class="op">=</span> <span class="pp">format!</span>(<span class="st">"{}-{}"</span><span class="op">,</span> <span class="op">&</span>select_element_id<span class="op">,</span> MSG_ID)<span class="op">;</span></span>
<span id="cb7-7"><a href="#cb7-7" aria-hidden="true"></a> <span class="kw">let</span> root_el <span class="op">=</span> document</span>
<span id="cb7-8"><a href="#cb7-8" aria-hidden="true"></a> <span class="op">.</span>get_element_by_id(<span class="op">&</span>select_element_id)</span>
<span id="cb7-9"><a href="#cb7-9" aria-hidden="true"></a> <span class="op">.</span>expect(<span class="st">"could not find tag element"</span>)<span class="op">;</span></span>
<span id="cb7-10"><a href="#cb7-10" aria-hidden="true"></a> <span class="kw">let</span> tag_container <span class="op">=</span> document<span class="op">.</span>create_element(<span class="st">"div"</span>)<span class="op">?;</span></span>
<span id="cb7-11"><a href="#cb7-11" aria-hidden="true"></a> tag_container<span class="op">.</span>set_id(<span class="op">&</span><span class="pp">format!</span>(<span class="st">"{}-tag-wasm"</span><span class="op">,</span> <span class="op">&</span>select_element_id))<span class="op">;</span></span>
<span id="cb7-12"><a href="#cb7-12" aria-hidden="true"></a> tag_container<span class="op">.</span>set_attribute(<span class="st">"class"</span><span class="op">,</span> <span class="st">"tag-wasm"</span>)<span class="op">?;</span></span>
<span id="cb7-13"><a href="#cb7-13" aria-hidden="true"></a> tag_container<span class="op">.</span>set_attribute(<span class="st">"aria-hidden"</span><span class="op">,</span> <span class="st">"true"</span>)<span class="op">?;</span></span></code></pre></div>
<p>To create a callback from Rust, we wrap a closure in <code>Callback</code> and we <a href="https://www.youtube.com/watch?v=Hzh9koy7b1E"><code>forget</code> about it</a>, meaning that we tell Rust not to call <code>Drop</code> on it because otherwise when it’s called from the browser it won’t exist.</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode rust"><code class="sourceCode rust"><span id="cb8-1"><a href="#cb8-1" aria-hidden="true"></a> <span class="op">{</span></span>
<span id="cb8-2"><a href="#cb8-2" aria-hidden="true"></a> <span class="kw">let</span> input_id <span class="op">=</span> input_id<span class="op">.</span>clone()<span class="op">;</span></span>
<span id="cb8-3"><a href="#cb8-3" aria-hidden="true"></a> <span class="kw">let</span> onclick_db <span class="op">=</span> <span class="pp">Closure::</span>wrap(<span class="dt">Box</span><span class="pp">::</span>new(<span class="kw">move</span> <span class="op">|</span>_event<span class="op">:</span> <span class="pp">web_sys::</span>Event<span class="op">|</span> <span class="op">{</span></span>
<span id="cb8-4"><a href="#cb8-4" aria-hidden="true"></a> <span class="pp">JsCast::unchecked_into::</span><span class="op"><</span><span class="pp">web_sys::</span>HtmlElement<span class="op">></span>(</span>
<span id="cb8-5"><a href="#cb8-5" aria-hidden="true"></a> document<span class="op">.</span>get_element_by_id(<span class="op">&</span>input_id)<span class="op">.</span>expect(<span class="st">""</span>)<span class="op">,</span></span>
<span id="cb8-6"><a href="#cb8-6" aria-hidden="true"></a> )</span>
<span id="cb8-7"><a href="#cb8-7" aria-hidden="true"></a> <span class="op">.</span>focus()</span>
<span id="cb8-8"><a href="#cb8-8" aria-hidden="true"></a> <span class="op">.</span>unwrap()<span class="op">;</span></span>
<span id="cb8-9"><a href="#cb8-9" aria-hidden="true"></a> <span class="op">}</span>) <span class="kw">as</span> <span class="dt">Box</span><span class="op"><</span><span class="kw">dyn</span> <span class="bu">FnMut</span>(_)<span class="op">></span>)<span class="op">;</span></span>
<span id="cb8-10"><a href="#cb8-10" aria-hidden="true"></a> tag_container<span class="op">.</span>set_onclick(<span class="cn">Some</span>(onclick_db<span class="op">.</span>as_ref()<span class="op">.</span>unchecked_ref()))<span class="op">;</span></span>
<span id="cb8-11"><a href="#cb8-11" aria-hidden="true"></a> onclick_db<span class="op">.</span>forget()<span class="op">;</span></span>
<span id="cb8-12"><a href="#cb8-12" aria-hidden="true"></a> <span class="op">}</span></span></code></pre></div>
<p>Casting javascript objects and elements with <code>JsCast</code> is necessary to call the appropriate functions from each interface. The casting can be unchecked or checked on runtime.</p>
<h3 id="putting-it-all-together">Putting it all together</h3>
<p>We build the module by running <code>wasm-pack build --target web --release</code></p>
<p>This creates a <code>pkg</code> directory with a <code>.wasm</code> module and a <code>.js</code> file which does the loading and symbol export for us.</p>
<p>In the HTML page we dynamically import the module to avoid any errors showing up if it’s missing or something doesn’t work. We can just print a warning instead, since the <code><select></code> element still works. This is the graceful degradation part of this design: the user experience is not limited by the enhanced workflow.</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode html"><code class="sourceCode html"><span id="cb9-1"><a href="#cb9-1" aria-hidden="true"></a> <span class="kw"><script></span></span>
<span id="cb9-2"><a href="#cb9-2" aria-hidden="true"></a> <span class="kw">var</span> error <span class="op">=</span> <span class="kw">null</span><span class="op">;</span></span>
<span id="cb9-3"><a href="#cb9-3" aria-hidden="true"></a> <span class="im">import</span>(<span class="st">"tag_input_wasm.js"</span>)</span>
<span id="cb9-4"><a href="#cb9-4" aria-hidden="true"></a> <span class="op">.</span><span class="fu">then</span>((module) <span class="kw">=></span> {</span>
<span id="cb9-5"><a href="#cb9-5" aria-hidden="true"></a> <span class="kw">async</span> <span class="kw">function</span> <span class="fu">run</span>() {</span>
<span id="cb9-6"><a href="#cb9-6" aria-hidden="true"></a> <span class="kw">let</span> _ <span class="op">=</span> <span class="cf">await</span> module<span class="op">.</span><span class="fu">default</span>(<span class="st">"tag_input_wasm_bg.wasm"</span>)<span class="op">;</span></span>
<span id="cb9-7"><a href="#cb9-7" aria-hidden="true"></a> <span class="co">//module.setup({singular_name}, {field_name_attribute}, {field_id_attribute}, {json_id_attribute});</span></span>
<span id="cb9-8"><a href="#cb9-8" aria-hidden="true"></a> module<span class="op">.</span><span class="fu">setup</span>(<span class="st">"tag"</span><span class="op">,</span> <span class="st">"tags"</span><span class="op">,</span> <span class="st">"id_tags"</span><span class="op">,</span> <span class="st">"tags_json"</span>)<span class="op">;</span></span>
<span id="cb9-9"><a href="#cb9-9" aria-hidden="true"></a> }</span>
<span id="cb9-10"><a href="#cb9-10" aria-hidden="true"></a> <span class="cf">return</span> <span class="fu">run</span>()<span class="op">;</span></span>
<span id="cb9-11"><a href="#cb9-11" aria-hidden="true"></a> })<span class="op">.</span><span class="fu">catch</span>(err <span class="kw">=></span> {</span>
<span id="cb9-12"><a href="#cb9-12" aria-hidden="true"></a> <span class="bu">console</span><span class="op">.</span><span class="fu">warn</span>(<span class="st">"Could not load tag input .wasm file.</span><span class="sc">\n\n</span><span class="st">The error is saved in the global variable `error` for more details. The page and submission form will still work.</span><span class="sc">\n\n</span><span class="st">You can use `console.dir(error)` to see what happened."</span>)<span class="op">;</span></span>
<span id="cb9-13"><a href="#cb9-13" aria-hidden="true"></a> error <span class="op">=</span> err<span class="op">;</span></span>
<span id="cb9-14"><a href="#cb9-14" aria-hidden="true"></a> })<span class="op">;</span></span>
<span id="cb9-15"><a href="#cb9-15" aria-hidden="true"></a> <span class="kw"></script></span></span>
<span id="cb9-16"><a href="#cb9-16" aria-hidden="true"></a><span class="kw"><script</span><span class="ot"> id=</span><span class="st">"tags_json"</span><span class="ot"> type=</span><span class="st">"application/json"</span><span class="kw">></span>{<span class="st">"programming languages"</span><span class="op">:</span> <span class="st">"#ffffff"</span><span class="op">,</span> <span class="st">"python"</span><span class="op">:</span> <span class="st">"#3776ab"</span><span class="op">,</span> }<span class="kw"></script></span></span></code></pre></div>
2021-08-14T00:00:00+03:00https://nessuent.net/posts/2021-04-19_anatomy_of_melancholy.htmlTypesetting the 17th century book "The Anatomy Of Melancholy" by Robert Burton2022-10-22T13:38:25.114114+00:00<p>Project website: <a href="https://epilys.github.io/anatomy-of-melancholy-latex" class="uri">https://epilys.github.io/anatomy-of-melancholy-latex</a></p>
<p>Technical document: <a href="https://epilys.github.io/anatomy-of-melancholy-latex/style.pdf">‘The Anatomy of the “Anatomy of Melancholy”’</a></p>
<p>Page thumbnails:</p>
<figure>
<img src="/static/images/anatomy_spread.png" alt="" /><figcaption>Pages 15-16</figcaption>
</figure>
<figure>
<img src="/static/images/65-66.png" alt="" /><figcaption>Pages 65-66</figcaption>
</figure>
<figure>
<img src="/static/images/163-164.png" alt="" /><figcaption>Pages 163-164</figcaption>
</figure>
<figure>
<img src="/static/images/241-242.png" alt="" /><figcaption>Pages 241-242</figcaption>
</figure>
<figure>
<img src="/static/images/307-308.png" alt="" /><figcaption>Pages 307-308</figcaption>
</figure>
<figure>
<img src="/static/images/595-596.png" alt="" /><figcaption>Pages 595-596</figcaption>
</figure>
<figure>
<img src="/static/images/lycanthropia.png" alt="" /><figcaption>Lycanthropia</figcaption>
</figure>
<figure>
<img src="/static/images/output-872.png" alt="" /><figcaption>Page 872</figcaption>
</figure>
<figure>
<img src="/static/images/1479-1480.png" alt="" /><figcaption>Pages 1479-1480</figcaption>
</figure>
<figure>
<img src="/static/images/1493-1494.png" alt="" /><figcaption>Pages 1493-1494</figcaption>
</figure>
2021-04-19T00:00:00+03:00https://nessuent.net/posts/2021-06-29-using_sqlite3_as_a_notekeeping_graph.htmlUsing sqlite3 as a notekeeping document graph with automatic reference indexing2022-10-22T13:38:25.114101+00:00<p>Article located at:</p>
<p><a href="https://epilys.github.io/bibliothecula/notekeeping.html" class="uri">https://epilys.github.io/bibliothecula/notekeeping.html</a></p>
2021-06-29T00:00:00+03:00https://nessuent.net/posts/2017-08-28_completed_gsoc.htmlCompleted GSOC with QEMU project on "Moving I/O throttling and write notifiers into block filter drivers"2022-10-22T13:38:25.114084+00:00<p>(<em>Note</em>: this is a copy of my completion report on the <code>qemu</code> mailing list: <a href="https://lists.nongnu.org/archive/html/qemu-devel/2017-08/msg05371.html" class="uri">https://lists.nongnu.org/archive/html/qemu-devel/2017-08/msg05371.html</a>)</p>
<p>This is a GSOC project summary required for the project’s final submission. As part of GSOC 2017, I took the project of moving two hard coded block layer features into filter drivers. I/O Throttling is implemented in <code>block/throttle.c</code> and before write notifiers are split into a driver for each user of the before write notifier API: <code>block/backup.c</code> and <code>block/write-threshold.c</code>. Furthermore, work began on <code>block-insert-node</code> and <code>block-remove-noder</code> commands for the QMP interface to allow runtime insertion and removal of filter drivers. [0]</p>
<p>A lot of thanks to my mentors for their help: Alberto Garcia, Stefan Hajnoczi and Kevin Wolf.</p>
<h2 id="terms">Terms</h2>
<p>The <code>BlockBackend</code> struct (<code>block/block-backend.c</code>) represents the backend part of a storage device that a VM sees in the QEMU environment. The <code>BlockBackend</code> has the responsibility to forward I/O requests from the VM down to the actual underlying storage; a network block device, a qcow2 image etc.</p>
<p>In order to allow for polymorphic storage, a <code>BlockBackend</code> forwards the requests to an acyclic graph in which the leaves are the terminal I/O destination, a file or network connection. The <code>BlockDriverState</code> struct represents a node in this graph, and each node is governed by a specific driver. Above the leaf-nodes we have format drivers that translate requests for each format (ie a qcow2 driver, or a raw driver). Backing files are implemented as chains of nodes that forward read requests to their children but keep write requests to themselves. This setup allows different node drivers to intercept requests before they reach their destination by being inserted into points of interest in the graph. We call these block filter drivers.</p>
<p>An existing filter driver for example is <code>block/blkverify.c</code> which compares two children for content parity and reports content mismatches.</p>
<h2 id="io-throttling">I/O Throttling</h2>
<p>I/O throttling is done by intercepting I/O requests and throttling them based on the configured limits (docs/throttle.txt). The interface was refactored into the throttle driver [1] while the throttling primitives were left unchanged. The already existing interface of setting limits on a BlockBackend device is simulated [2] by inserting a hidden to the user throttle filter node at the root of the BlockBackend with the user’s set limits. Implicitly created filter nodes is not a good solution since some of the QEMU internals are written without considering filter nodes. Some patches in the throttle-remove-legacy branch are dedicated to changing existing behaviour to match the new concept of implicit filters. In the future management tools should be expected to explicitly add and remove filter nodes like throttle (except for transient block job filters which may remain implicit) and there should be no surprises about the state of the block layer graph for the user.</p>
<p>Throttle groups are categories of drives sharing the same limits with a round-robin algorithm. Additional effort was spent on making throttle groups easier to configure by turning them into a separately creatable object (with -object syntax on command line invocation or object-add in QMP). Their properties can be set with ‘qom-set’ commands and retrieved with ‘qom-get’.</p>
<h2 id="write-notifiers">Write Notifiers</h2>
<p>While a backup block job is running, it is important to have knowledge of writes to the relevant image. Before write notifiers pass the write requests to the backup job to perform copy on write on the target image with the new data. Currently this is done on the BlockBackend level. Other block jobs (commit/mirror) already create implicit nodes in the BDS chain and this approach was copied and a backup filter driver was created [3], internal to block/backup.c</p>
<p>The write-threshold feature once enabled via QMP, watches passing write requests and compares them to a user-given threshold offset. When that threshold is exceeded an event is delivered to the user and the feature disables itself. This is used for management tools that need to know when they have to resize their images. Like backup, this was done in the BlockBackend level. However it wasn’t easy to replace the existing interface with an implicit filter node like in throttling, so only a separate driver was created [4] in block/write-threshold.c. Like other filter drivers, it can be inserted on runtime and removed once it delivers the event and is spent and should be removed or replaced.</p>
<h2 id="branches-patches">Branches / Patches</h2>
<p>The ‘throttle’ and ‘throttle-remove-legacy’ patches should be merged soon after master unfreezes from the 2.10 release. The rest of the patch series are in final stages of review on qemu-devel except for block-insert-node which is an RFC [5].</p>
<p>Already merged patches in 2.10 https://github.com/qemu/qemu/commits/v2.10.0-rc4?author=epilys Already merged patches for 2.11 https://www.mail-archive.com/address@hidden/msg470461.html</p>
<p>[0] [insert-node] block-insert-node and block-remove-node commands https://github.com/epilys/qemu/commits/insert-node?author=epilys</p>
<p>[1] [throttle] add throttle filter driver https://github.com/epilys/qemu/commits/throttle?author=epilys Message-ID: <a href="mailto:address@hidden" class="email">address@hidden</a> https://www.mail-archive.com/address@hidden/msg476047.html</p>
<p>[2] [throttle-remove-legacy] remove legacy throttling interface https://github.com/epilys/qemu/commits/throttle-remove-legacy?author=epilys</p>
<p>[3] [4] [notify] https://github.com/epilys/qemu/commits/notify?author=epilys</p>
<p>[5] block-insert-node RFC Message-ID: <a href="mailto:address@hidden" class="email">address@hidden</a> https://www.mail-archive.com/address@hidden/msg473619.html</p>
2017-08-28T00:00:00+03:00https://nessuent.net/posts/2021-07-18_detecting_cycles.htmlDetecting cycles in tag parent-child relationship in sqlite32022-10-22T13:38:25.114061+00:00<h2 id="problem-statement">Problem statement</h2>
<p>Story tags can have multiple parents. This establishes a hierarchy where a tag can have a tree of descendants. We want this directed graph to be acyclic (<em>DAG</em>) because cycles don’t make sense in a topical hierarchy, and when we query the graph we would have to be extra cautious to not fall in infinite loops.</p>
<h3 id="database-schema">Database schema</h3>
<p>Here are the tables created by django:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true"></a><span class="kw">CREATE</span> <span class="kw">TABLE</span> <span class="cf">IF</span> <span class="kw">NOT</span> <span class="kw">EXISTS</span> <span class="ot">"sic_tag"</span> (</span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true"></a> <span class="ot">"id"</span> <span class="dt">integer</span> <span class="kw">NOT</span> <span class="kw">NULL</span> <span class="kw">PRIMARY</span> <span class="kw">KEY</span> AUTOINCREMENT,</span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true"></a> <span class="ot">"name"</span> <span class="dt">varchar</span>(<span class="dv">40</span>) <span class="kw">NOT</span> <span class="kw">NULL</span> <span class="kw">UNIQUE</span>,</span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true"></a> <span class="ot">"created"</span> datetime <span class="kw">NOT</span> <span class="kw">NULL</span>,</span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true"></a> <span class="ot">"hex_color"</span> <span class="dt">varchar</span>(<span class="dv">7</span>) <span class="kw">NULL</span></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true"></a>);</span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true"></a></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true"></a><span class="kw">CREATE</span> <span class="kw">TABLE</span> <span class="cf">IF</span> <span class="kw">NOT</span> <span class="kw">EXISTS</span> <span class="ot">"sic_tag_parents"</span> (</span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true"></a> <span class="ot">"id"</span> <span class="dt">integer</span> <span class="kw">NOT</span> <span class="kw">NULL</span> <span class="kw">PRIMARY</span> <span class="kw">KEY</span> AUTOINCREMENT,</span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true"></a> <span class="ot">"from_tag_id"</span> <span class="dt">integer</span> <span class="kw">NOT</span> <span class="kw">NULL</span> <span class="kw">REFERENCES</span> <span class="ot">"sic_tag"</span> (<span class="ot">"id"</span>) <span class="kw">DEFERRABLE</span> <span class="kw">INITIALLY</span> <span class="kw">DEFERRED</span>,</span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true"></a> <span class="ot">"to_tag_id"</span> <span class="dt">integer</span> <span class="kw">NOT</span> <span class="kw">NULL</span> <span class="kw">REFERENCES</span> <span class="ot">"sic_tag"</span> (<span class="ot">"id"</span>) <span class="kw">DEFERRABLE</span> <span class="kw">INITIALLY</span> <span class="kw">DEFERRED</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true"></a>);</span></code></pre></div>
<p>The table <code>sic_tag_parents</code> contains one row for each directed edge.</p>
<h2 id="recursive-common-table-expression-cte-to-the-rescue">Recursive Common Table Expression (CTE) to the rescue</h2>
<p><code>sqlite3</code> provides us with the ability to perform recursive queries with Common Table Expressions. We can use this to write a query that returns all paths within the graph. Then, when we insert a new parent-child relationship, we check if there already exists a directed path from the child to its parent.</p>
<p>Unfortunately it’s not possible to make a table <code>CHECK CONSTRAINT</code> since the constraint must refer to the table, which exists only after the <code>CREATE TABLE</code> statement is finished. We can instead make the check in a <code>BEFORE INSERT</code> trigger and <code>RAISE(ABORT)</code> if a cycle is detected, thus preventing the insertion.</p>
<p>Firstly, the trigger shall execute a <code>SELECT</code> query for each inserted row. In order to raise an exception, we have to <code>SELECT</code> it:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true"></a><span class="kw">CREATE</span> <span class="kw">TRIGGER</span> cycle_check</span>
<span id="cb2-2"><a href="#cb2-2" aria-hidden="true"></a><span class="kw">BEFORE</span> <span class="kw">INSERT</span> <span class="kw">ON</span> sic_tag_parents</span>
<span id="cb2-3"><a href="#cb2-3" aria-hidden="true"></a><span class="cf">FOR</span> <span class="kw">EACH</span> <span class="kw">ROW</span></span>
<span id="cb2-4"><a href="#cb2-4" aria-hidden="true"></a><span class="cf">BEGIN</span></span>
<span id="cb2-5"><a href="#cb2-5" aria-hidden="true"></a> <span class="kw">SELECT</span> RAISE(ABORT, <span class="st">'Cycle detected'</span>);</span>
<span id="cb2-6"><a href="#cb2-6" aria-hidden="true"></a><span class="cf">END</span></span></code></pre></div>
<p>Secondly, in order to abort only when a specific condition is met, we can use a <code>WHERE EXISTS</code>:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true"></a><span class="kw">CREATE</span> <span class="kw">TRIGGER</span> cycle_check</span>
<span id="cb3-2"><a href="#cb3-2" aria-hidden="true"></a><span class="kw">BEFORE</span> <span class="kw">INSERT</span> <span class="kw">ON</span> sic_tag_parents</span>
<span id="cb3-3"><a href="#cb3-3" aria-hidden="true"></a><span class="cf">FOR</span> <span class="kw">EACH</span> <span class="kw">ROW</span></span>
<span id="cb3-4"><a href="#cb3-4" aria-hidden="true"></a><span class="cf">BEGIN</span></span>
<span id="cb3-5"><a href="#cb3-5" aria-hidden="true"></a> <span class="kw">SELECT</span> RAISE(ABORT, <span class="st">'Cycle detected'</span>) <span class="kw">WHERE</span> <span class="kw">EXISTS</span> (<span class="op">..</span>.);</span>
<span id="cb3-6"><a href="#cb3-6" aria-hidden="true"></a><span class="cf">END</span></span></code></pre></div>
<p>In the <code>EXISTS</code> expression we shall put a recursive CTE that returns something (anything) if a cycle exists. If anything is returned, <code>EXISTS</code> evaluates to true and <code>RAISE</code> is selected.</p>
<p>This is the CTE query:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true"></a><span class="kw">WITH</span> RECURSIVE w(<span class="kw">parent</span>, last_visited, already_visited, <span class="kw">cycle</span>) <span class="kw">AS</span> (</span>
<span id="cb4-2"><a href="#cb4-2" aria-hidden="true"></a> <span class="kw">SELECT</span> <span class="kw">DISTINCT</span> to_tag_id <span class="kw">AS</span> <span class="kw">parent</span>, from_tag_id <span class="kw">AS</span> last_visited, to_tag_id <span class="kw">AS</span> already_visited, <span class="dv">0</span> <span class="kw">AS</span> <span class="kw">cycle</span> <span class="kw">FROM</span> sic_tag_parents</span>
<span id="cb4-3"><a href="#cb4-3" aria-hidden="true"></a></span>
<span id="cb4-4"><a href="#cb4-4" aria-hidden="true"></a> <span class="kw">UNION</span> <span class="kw">ALL</span></span>
<span id="cb4-5"><a href="#cb4-5" aria-hidden="true"></a></span>
<span id="cb4-6"><a href="#cb4-6" aria-hidden="true"></a> <span class="kw">SELECT</span> t.to_tag_id <span class="kw">AS</span> <span class="kw">parent</span>, t.from_tag_id <span class="kw">AS</span> last_visited, already_visited <span class="op">||</span> <span class="st">', '</span> <span class="op">||</span> t.to_tag_id, already_visited <span class="kw">LIKE</span> <span class="st">'%'</span><span class="op">||</span>t.to_tag_id<span class="op">||</span><span class="ot">"%"</span> <span class="kw">FROM</span> sic_tag_parents <span class="kw">AS</span> t <span class="kw">JOIN</span> w <span class="kw">ON</span> w.last_visited <span class="op">=</span> t.to_tag_id</span>
<span id="cb4-7"><a href="#cb4-7" aria-hidden="true"></a> <span class="kw">WHERE</span> <span class="kw">NOT</span> <span class="kw">cycle</span></span>
<span id="cb4-8"><a href="#cb4-8" aria-hidden="true"></a>)</span>
<span id="cb4-9"><a href="#cb4-9" aria-hidden="true"></a><span class="kw">SELECT</span> already_visited, <span class="kw">cycle</span> <span class="kw">FROM</span> w <span class="kw">WHERE</span> last_visited <span class="op">=</span> <span class="kw">NEW</span>.to_tag_id <span class="kw">AND</span> already_visited <span class="kw">LIKE</span> <span class="st">'%'</span><span class="op">||</span><span class="kw">NEW</span>.from_tag_id<span class="op">||</span><span class="st">'%'</span></span></code></pre></div>
<p>Line-by-line:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true"></a><span class="kw">WITH</span> RECURSIVE w(<span class="kw">parent</span>, last_visited, already_visited, <span class="kw">cycle</span>) <span class="kw">AS</span><span class="op">..</span></span></code></pre></div>
<p>This defines a temporary table/view called <code>w</code> with these columns as an expression. This is similar to defining regular views as the result of a <code>SELECT</code> statement.</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb6-1"><a href="#cb6-1" aria-hidden="true"></a><span class="kw">SELECT</span> <span class="kw">DISTINCT</span> to_tag_id <span class="kw">AS</span> <span class="kw">parent</span>, from_tag_id <span class="kw">AS</span> last_visited, to_tag_id <span class="kw">AS</span> already_visited, <span class="dv">0</span> <span class="kw">AS</span> <span class="kw">cycle</span> <span class="kw">FROM</span> sic_tag_parents</span></code></pre></div>
<p>Here we select every edge as the start of a potential path. These edges are paths of length 1, and are also acyclic, hence we select 0 as <code>cycle</code>. This line is performed one time at the beginning of the CTE, it’s the basis of the recursion.</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb7-1"><a href="#cb7-1" aria-hidden="true"></a><span class="kw">UNION</span> <span class="kw">ALL</span></span></code></pre></div>
<p>The base select is united with the select that follows:</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb8-1"><a href="#cb8-1" aria-hidden="true"></a><span class="kw">SELECT</span> t.to_tag_id <span class="kw">AS</span> <span class="kw">parent</span>, t.from_tag_id <span class="kw">AS</span> last_visited, already_visited <span class="op">||</span> <span class="st">', '</span> <span class="op">||</span> t.to_tag_id, already_visited <span class="kw">LIKE</span> <span class="st">'%'</span><span class="op">||</span>t.to_tag_id<span class="op">||</span><span class="ot">"%"</span> <span class="kw">FROM</span> sic_tag_parents <span class="kw">AS</span> t <span class="kw">JOIN</span> w <span class="kw">ON</span> w.last_visited <span class="op">=</span> t.to_tag_id</span>
<span id="cb8-2"><a href="#cb8-2" aria-hidden="true"></a><span class="kw">WHERE</span> <span class="kw">NOT</span> <span class="kw">cycle</span></span></code></pre></div>
<p>Here we <code>JOIN</code> <code>sic_tag_parents</code> with <code>w</code> itself, by adding edges to the already existing paths in the previous iteration of <code>w</code>. The path is built as a string of comma separated <code>id</code>s. <code>cycle</code> is true if <code>to_tag_id</code>, the parent, already exists in the previous path. The <code>WHERE NOT cycle</code> is necessary to prevent infinite recursion.</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb9-1"><a href="#cb9-1" aria-hidden="true"></a><span class="kw">SELECT</span> already_visited, <span class="kw">cycle</span> <span class="kw">FROM</span> w <span class="kw">WHERE</span> last_visited <span class="op">=</span> <span class="kw">NEW</span>.to_tag_id <span class="kw">AND</span> already_visited <span class="kw">LIKE</span> <span class="st">'%'</span><span class="op">||</span><span class="kw">NEW</span>.from_tag_id<span class="op">||</span><span class="st">'%'</span></span></code></pre></div>
<p>Finally, we select the paths that begin with the parent and contain the child.</p>
<p>The entire trigger:</p>
<div class="sourceCode" id="cb10"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb10-1"><a href="#cb10-1" aria-hidden="true"></a><span class="kw">CREATE</span> <span class="kw">TRIGGER</span> cycle_check</span>
<span id="cb10-2"><a href="#cb10-2" aria-hidden="true"></a><span class="kw">BEFORE</span> <span class="kw">INSERT</span> <span class="kw">ON</span> sic_tag_parents</span>
<span id="cb10-3"><a href="#cb10-3" aria-hidden="true"></a><span class="cf">FOR</span> <span class="kw">EACH</span> <span class="kw">ROW</span></span>
<span id="cb10-4"><a href="#cb10-4" aria-hidden="true"></a><span class="cf">BEGIN</span></span>
<span id="cb10-5"><a href="#cb10-5" aria-hidden="true"></a> <span class="kw">SELECT</span> RAISE(ABORT, <span class="st">'Cycle detected'</span>) <span class="kw">WHERE</span> <span class="kw">EXISTS</span> (</span>
<span id="cb10-6"><a href="#cb10-6" aria-hidden="true"></a> <span class="kw">WITH</span> RECURSIVE w(<span class="kw">parent</span>, last_visited, already_visited, <span class="kw">cycle</span>) <span class="kw">AS</span> (</span>
<span id="cb10-7"><a href="#cb10-7" aria-hidden="true"></a> <span class="kw">SELECT</span> <span class="kw">DISTINCT</span> to_tag_id <span class="kw">AS</span> <span class="kw">parent</span>, from_tag_id <span class="kw">AS</span> last_visited, to_tag_id <span class="kw">AS</span> already_visited, <span class="dv">0</span> <span class="kw">AS</span> <span class="kw">cycle</span> <span class="kw">FROM</span> sic_tag_parents</span>
<span id="cb10-8"><a href="#cb10-8" aria-hidden="true"></a></span>
<span id="cb10-9"><a href="#cb10-9" aria-hidden="true"></a> <span class="kw">UNION</span> <span class="kw">ALL</span></span>
<span id="cb10-10"><a href="#cb10-10" aria-hidden="true"></a></span>
<span id="cb10-11"><a href="#cb10-11" aria-hidden="true"></a> <span class="kw">SELECT</span> t.to_tag_id <span class="kw">AS</span> <span class="kw">parent</span>, t.from_tag_id <span class="kw">AS</span> last_visited, already_visited <span class="op">||</span> <span class="st">', '</span> <span class="op">||</span> t.to_tag_id, already_visited <span class="kw">LIKE</span> <span class="st">'%'</span><span class="op">||</span>t.to_tag_id<span class="op">||</span><span class="ot">"%"</span> <span class="kw">FROM</span> sic_tag_parents <span class="kw">AS</span> t <span class="kw">JOIN</span> w <span class="kw">ON</span> w.last_visited <span class="op">=</span> t.to_tag_id</span>
<span id="cb10-12"><a href="#cb10-12" aria-hidden="true"></a> <span class="kw">WHERE</span> <span class="kw">NOT</span> <span class="kw">cycle</span></span>
<span id="cb10-13"><a href="#cb10-13" aria-hidden="true"></a> )</span>
<span id="cb10-14"><a href="#cb10-14" aria-hidden="true"></a> <span class="kw">SELECT</span> already_visited, <span class="kw">cycle</span> <span class="kw">FROM</span> w <span class="kw">WHERE</span> last_visited <span class="op">=</span> <span class="kw">NEW</span>.to_tag_id <span class="kw">AND</span> already_visited <span class="kw">LIKE</span> <span class="st">'%'</span><span class="op">||</span><span class="kw">NEW</span>.from_tag_id<span class="op">||</span><span class="st">'%'</span></span>
<span id="cb10-15"><a href="#cb10-15" aria-hidden="true"></a> );</span>
<span id="cb10-16"><a href="#cb10-16" aria-hidden="true"></a><span class="cf">END</span>;</span></code></pre></div>
<h2 id="appendix">Appendix</h2>
<p>We can visualise the paths with a CTE.</p>
<p>First, create a utility view that associates edges with their corresponding tag names:</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode sql"><code class="sourceCode sql"><span id="cb11-1"><a href="#cb11-1" aria-hidden="true"></a><span class="kw">CREATE</span> <span class="kw">TEMPORARY</span> <span class="kw">VIEW</span> sic_tag_parents_name <span class="kw">AS</span> <span class="kw">select</span> f.name <span class="kw">AS</span> from_name, from_tag_id, t.name <span class="kw">AS</span> to_name, to_tag_id <span class="kw">from</span> sic_tag_parents <span class="kw">join</span> sic_tag <span class="kw">AS</span> f <span class="kw">on</span> f.<span class="kw">id</span> <span class="op">=</span> from_tag_id <span class="kw">join</span> sic_tag <span class="kw">AS</span> t <span class="kw">on</span> t.<span class="kw">id</span> <span class="op">=</span> to_tag_id;</span></code></pre></div>
<p>Sample output:</p>
<pre><code>sqlite> SELECT * FROM sic_tag_parents_name LIMIT 2;
from_name from_tag_id to_name to_tag_id
----------- ----------- ---------------- ---------
programming 57 computer science 102
debugging 137 programming 57</code></pre>
<p>Then write a similar CTE as a view that creates a path string out of the tag names:</p>
<pre><code>CREATE TEMPORARY VIEW sic_tag_parents_paths AS
WITH RECURSIVE w(parent, last_visited, parent_name, last_visited_name, already_visited, cycle, length) AS (
SELECT DISTINCT to_tag_id AS parent, from_tag_id AS last_visited, to_name AS parent_name, from_name AS last_visited_name, to_name AS already_visited, 0 AS cycle, 1 as length FROM sic_tag_parents_name
UNION ALL
SELECT t.to_tag_id AS parent, t.from_tag_id AS last_visited, t.to_name, t.from_name, t.to_name || ' > ' || already_visited, already_visited LIKE '%'||t.to_name||"%", length+1 AS length FROM sic_tag_parents_name AS t JOIN w ON w.last_visited = t.to_tag_id
WHERE NOT cycle
)
SELECT * FROM w;</code></pre>
<p>The output:</p>
<pre><code>sqlite> select distinct(last_visited_name || ' > ' || already_visited) as path, length from sic_tag_parents_paths order by length desc limit 25;
path length
------------------------------------------------------------------- ------
c > programming languages > programming > computer science 3
c++ > programming languages > programming > computer science 3
clojure > programming languages > programming > computer science 3
elixir > programming languages > programming > computer science 3
erlang > programming languages > programming > computer science 3
go > programming languages > programming > computer science 3
haskell > programming languages > programming > computer science 3
javascript > programming languages > programming > computer science 3
java > programming languages > programming > computer science 3
lisp > programming languages > programming > computer science 3
lua > programming languages > programming > computer science 3
python > programming languages > programming > computer science 3
ruby > programming languages > programming > computer science 3
rust > programming languages > programming > computer science 3
swift > programming languages > programming > computer science 3
emacs > commandline > unix > operating systems 3
emacs > commandline > unix 2
debugging > programming > computer science 2
programming languages > programming > computer science 2
vcs > programming > computer science 2
commandline > unix > operating systems 2
linux > unix > operating systems 2
openbsd > unix > operating systems 2
dragonflybsd > unix > operating systems 2
sqlite3 > databases > computer science 2</code></pre>
2021-07-18T00:00:00+03:00