)]}' { "commit": "5998352d2d2e6e37531548f8e986abae5ff8ef02", "tree": "7d3fa6c312b512b81061bc9f2f448c4f698a0a7f", "parents": [ "dd15fea026c3e0b389381ae8cc08e0f39fa1a8f7" ], "author": { "name": "Laslo Hunhold", "email": "dev@frign.de", "time": "Tue Oct 25 13:20:47 2022 +0200" }, "committer": { "name": "Laslo Hunhold", "email": "dev@frign.de", "time": "Tue Oct 25 13:49:50 2022 +0200" }, "message": "Implement the Unicode Bidirectional Algorithm (UAX #9)\n\nTo be frank, I never heard about this until I started learning more\nabout Unicode, but this is an absolute must for all languages that go\nfrom right to left (Hebrew, Arabic, Farsi, etc.) and any case where you\nmix RTL and LTR languages.\n\nThe Unicode Bidirectional Algorithm is the normative procedure you apply\non a string to obtain embedding levels that can then be used to reorder\nthe string such that you obtain the proper reading direction. The\ncentral aspect is that strings are always stored LTR in memory and only\nreordered for presentation on the screen.\n\nCurrently, only ICU and GNU fribidi implement the algorithm, and as\nusual it\u0027s pretty convoluted to use them. There are many memory\nallocations, kitchen-sink-madness and legacy cruft, but the demand is\nthere (there\u0027s even a bidi-patch for dwm[0]).\n\nWhat\u0027s special about this implementation? There are no memory\nallocations at runtime. The user provides a 32-bit-integer-array which\nis then filled with the embedding levels. The levels themselves only\nrange from -1 to 125 (by the standard!) and would fit in a signed\n8-bit-integer, but the algorithm naturally needs a scratchpad to store\nprocessing data.\n\nA complication of the algorithm is that you, at some point, have to\nbreak the paragraph into lines and based on the line breaks the level\ndetermination is affected. GNU fribidi and ICU make this very\ncomplicated and hard to understand. The API is not final as you see it\nhere, but the final process will be (each number corresponding to a\nfunction):\n\n\t1) \"preprocessing\" the string up to the part where the algorithm\n\t does not depend on the line breaks\n\t2) determining line embedding levels for a line\n\t (by specifying the preprocessed data buffer and an output\n\t level-buffer)\n\t3) reordering a line (by specifying the preprocessed data buffer\n\t and an output string that is allowed to be the input string)\n\nConformance is obviously a large priority: There are literally over a\nmillion automatic conformance tests for the bidirectional algorithm split\nacross the files BidiTest.txt and BidiCharacterTest.txt that are\nautomatically parsed into the header gen/bidirectional-test.h.\n\nCurrently, only BidiTest.txt is used for tests (which we all pass),\ngiven bracket-pairs have not been implemented yet. This and (maybe)\narabic shaping are what is left to be implemented, but this here is\nalready a big step.\n\nOne more note: Yes, the data files are very large, but they compress\ndown very well and the tarball stays below 800K. It\u0027s very important\nto me that there\u0027s no need to pull any data from the web for compilation\nor testing for obvious reasons.\n\n[0]:https://dwm.suckless.org/patches/bidi/\n\nSigned-off-by: Laslo Hunhold \u003cdev@frign.de\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "2eeec6d8249a478dd6ee43a5301cac1d788a8fe1", "old_mode": 33188, "old_path": "Makefile", "new_id": "70e773e84d70726fc86aa615019b33ac3a044a78", "new_mode": 33188, "new_path": "Makefile" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "de98e08168a94d4a58d807e9b50d8bdfc1a8912b", "new_mode": 33188, "new_path": "benchmark/bidirectional.c" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "e138e7f5bea61cafb18ad6ea53f67d99ad53caaf", "new_mode": 33188, "new_path": "data/BidiBrackets.txt" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "4379752be9870fbc7ac4977082b772c07969ad2f", "new_mode": 33188, "new_path": "data/BidiCharacterTest.txt" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "5861d6e7f4b791292cb2b01173dd90d9522856dd", "new_mode": 33188, "new_path": "data/BidiMirroring.txt" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "5e75ef42556f4207fe7985c6b3d7529674fd4575", "new_mode": 33188, "new_path": "data/BidiTest.txt" }, { "type": "modify", "old_id": "4012dc25da1ae38de025aa8baf5a864f555b8fa5", "old_mode": 33188, "old_path": "data/DerivedBidiClass.txt", "new_id": "55b30a66c996b4ab71fe13a592e37e9748f08d83", "new_mode": 33188, "new_path": "data/DerivedBidiClass.txt" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "30345644af2b641eba814fb76fe2c2dc6142661d", "new_mode": 33188, "new_path": "gen/bidirectional-test.c" }, { "type": "modify", "old_id": "588f13a9784ca59271c0a2d589fd3305f5edaa87", "old_mode": 33188, "old_path": "gen/bidirectional.c", "new_id": "e4070b71c23bf222d30a0ebfb94e2344fe2b2d04", "new_mode": 33188, "new_path": "gen/bidirectional.c" }, { "type": "modify", "old_id": "174a8bdbf408d46c16c1668f16ab893eb8c91941", "old_mode": 33188, "old_path": "gen/case.c", "new_id": "836c1c0e3e300fd9fb8f999c3baee287460ff291", "new_mode": 33188, "new_path": "gen/case.c" }, { "type": "modify", "old_id": "7efb4f4f1b41c9f64e00bef76cb048a435b6fdb2", "old_mode": 33188, "old_path": "gen/character.c", "new_id": "2643c7adc87bf9082e6971b5fc4a6d185cbc2533", "new_mode": 33188, "new_path": "gen/character.c" }, { "type": "modify", "old_id": "c7c488d38ba88143a34703ea384324674f006ee1", "old_mode": 33188, "old_path": "gen/line.c", "new_id": "576485fd165674c9ae81c380c7be663d22327a68", "new_mode": 33188, "new_path": "gen/line.c" }, { "type": "modify", "old_id": "9a0bd5e4c067e3c28eae7e6e1d31d3f20ce9f579", "old_mode": 33188, "old_path": "gen/sentence.c", "new_id": "627f84ca8a7c69c827c094e02baefeb7cef73f5b", "new_mode": 33188, "new_path": "gen/sentence.c" }, { "type": "modify", "old_id": "11cd561fac3021a3739ce2bec4b1b483630a91e3", "old_mode": 33188, "old_path": "gen/util.c", "new_id": "64afaa8cfa4de898dc3acdc16a9f39a4e6b0b15b", "new_mode": 33188, "new_path": "gen/util.c" }, { "type": "modify", "old_id": "0314b0b1c7fb5e737e9fbbcffc896a06f9371d04", "old_mode": 33188, "old_path": "gen/util.h", "new_id": "493f310a3a3315de66e7aa21d071497bf2334a7a", "new_mode": 33188, "new_path": "gen/util.h" }, { "type": "modify", "old_id": "1f631340e43c9f93174927ab61295f5560786167", "old_mode": 33188, "old_path": "gen/word.c", "new_id": "e1e157c63fc8386d8496d2a4a6d754d4fadcc90d", "new_mode": 33188, "new_path": "gen/word.c" }, { "type": "modify", "old_id": "1d6f2daaa7a921c823af95706a0192fcdad23b3f", "old_mode": 33188, "old_path": "grapheme.h", "new_id": "3699a6fab9c071179ef28ae3cc7343113d6bae84", "new_mode": 33188, "new_path": "grapheme.h" }, { "type": "modify", "old_id": "d383b3c056d4252d6df001b7e0b222e065f6f7e6", "old_mode": 33188, "old_path": "src/bidirectional.c", "new_id": "752fc6a46c531fdb38437b3318a23338255515b7", "new_mode": 33188, "new_path": "src/bidirectional.c" }, { "type": "modify", "old_id": "adca641724ebc8c30b6e0b234258aeb74e12ce75", "old_mode": 33188, "old_path": "src/util.h", "new_id": "d089e0d6cafb01421dc4fddb88bd5972be24284a", "new_mode": 33188, "new_path": "src/util.h" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "bec195835da8fb82b3d82999a6211a79c8a8ff96", "new_mode": 33188, "new_path": "test/bidirectional.c" } ] }