2 ms·
In summary, Simon presents this bijective map, though this omits the motivation: s.replace("-", "--").replace(".", "-.").replace("/", "-/") I think the en
by kragen 5y ago
In summary, Simon presents this bijective map, though this omits the motivation:
s.replace("-", "--").replace(".", "-.").replace("/", "-/")
I think the encoding would be more broadly applicable if you replaced the special characters with sequences of nonspecial characters. For example:
s.replace("-", "--").replace(".", "-d").replace("/", "-s")
s.replace("-", "--").replace(".", "-*").replace("/", "-,")
Then, for example, relative URLs don't break, and you can use it to generate filenames that are subject to Apache content-negotiation. That's outside the scope of Simon's intended use, of course, which is Datasette, which generates all its pages dynamically rather than storing them in the firesystem.
Interestingly, though Simon doesn't call this out, I think both his original scheme and my -d-s version above preserve lexicographical ordering on strings. My -*-, scheme doesn't (-* sorts before -- instead of after it) but I think this version fixes that:
s.replace("-", "--").replace(".", "-@").replace("/", "-|")
These non-alphabet-using schemes preserve homomorphism for alphabetic translations like .lower(), .upper(), and .title(), which is to say that, for any f from the set lambda s: s.lower(), lambda s: s.upper(), lambda s: s.title(), there exists a g such that dash_encode(f(s)) == g(dash_encode(s)) for any string. (And, as it happens, g == f, but the definition of homomorphism doesn't require that.)
Simon wanted to "avoid changing the string at all if possible," but I think that's sort of a bad idea; it means that bugs that apply either the forward or inverse transformation the wrong number of times will often slip through initial testing. If we weaken that to "keep the name in the URL as close to readable as possible," while adding the opposite requirement, "ensure that no string maps to itself," we could use something like this:
'-' + s.replace("-", "--").replace(".", "-@").replace("/", "-|")
Any character would work for the prefix, and if you're using the generated names as Unix filenames, maybe ',', '=', or '_' would also be minimally obtrusive visually and less likely to result in problems in the shell.
I hadn't seen Debuggex before. It looks pretty nice.
- lilyball 5y agoDownloading the resulting files is a really strong argument against the original "dash encoding" as proposed, because if I try to download the example /legislators/legislator_terms-/1.json path I'll end up with a file named `1.json` on my filesystem even though I'm download the file corresponding to the whole `legislator_terms/1` table. Or perhaps if I fetch a URL for the table `foo.json` and I don't add my own extension, I'll be viewing a URL ending in the component `foo-.json` even though it's not JSON data. Percent-encoding really would be the right solution here if only middleware would leave it alone instead of decoding and re-encoding it. In the absence of that, whatever encoding scheme is used must ensure the results do not leave any slashes or periods in the resulting string. As you've pointed out, other encodings (using the base dash character) can still preserve lexicographic ordering so there seems to be no reason to retain the actual period and slash characters.
- simonw 5y agoThis is an excellent point that I had not considered, thanks! I'm actually leaning towards a slightly different scheme now that would address this, where I use regular percentage encoding but with the hyphen character instead of the percentage character. I'll write an update if I decide to go with that approach.
- kragen 5y agoI look forward to reading it! Your blog is always a pleasure.
- lilyball 5y agoAre you intentionally trying to preserve lexicographic ordering? If so, doing percent-encoding-but-with-dash is reasonable and pretty easy to explain. If you don't care about lexicographic ordering then I would recommend picking a different character than dash. Even if Datasette's particular set of tables don't use dash in their name, if you're hoping other people will use this same scheme then using a more esoteric character might be nice. Using &/$/! would still preserve ordering relative to alphabetic characters and are not commonly found in URL paths.
- kragen 5y agoThat's a really important point, one I should have thought of. So maybe these changes would be advantageous even in Simon's intended use case. Probably characters that aren't * and | could be friendlier for filenames. I don't know that preserving lexicographical ordering is important, though it might be handy if you're storing things in LevelDB or something. I just have a soft spot for homomorphisms over the free monoid.