Kagi 的 url rewrite

Kagi 在上個禮拜推出了 url rewrite 的功能,可以把搜尋結果裡面的網址換掉:(在「Changelog」這邊可以看到)

Rewrite rules for domains - ability to e.g. translate "reddit.com" into "old.reddit.com" #158 @TeMPOraL

這個功能其實也可以在瀏覽器上用 extension 或是 userscript 處理掉 (跨機器可以透過瀏覽器的 cloud sync 來做),但目前應該還沒有這樣的東西,得自己寫一個出來。

範例提到把 reddit.com 換成 old.reddit.com 這種用法算是社群蠻常用的 (大家都不愛新版界面),不過我自己是把 *.m.wikipedia.org 轉成 *.wikipedia.org,這邊有多做一些事情,下面一條會提到:

^https://([a-z]+)\.m\.wikipedia\.org/[-a-z]*/(.*)|https://$1.wikipedia.org/wiki/$2

不難看出來是吃 regular expression,只是官方好像沒有特別說支援到哪種類型?(POSIX 系列或是 PCRE 類的,可以加減參考 Wikibooks 上「Regular Expressions」這邊的分類)

我另外一個 rule 是把維基百科有語言代碼的 https://zh.wikipedia.org/zh-*/ 轉成 https://zh.wikipedia.org/wiki/

^https://zh\.wikipedia\.org/zh-([a-z]*)/(.*)|https://zh.wikipedia.org/wiki/$2

這樣做的缺點是會出現兩個,可以看到第一個被轉了以後會出現一個小 icon,移上去可以看到是被哪個 rule 轉的:

用 GPT-3 解讀程式碼

Hacker News 上看到的方法,Simon Willison 試著把程式碼餵進 GPT-3,然後問 GPT-3 程式碼的意思,看起來答的還不錯:「Using GPT-3 to explain how code works」,對應的討論 (包括 Simon Willison 的回應) 則可以在「Using GPT-3 to explain how code works (simonwillison.net)」這邊看到。

第一個範例裡面可以解讀 regular expression,雖然裡面對 (?xm) 的解讀是錯的,但我會說已經很強了...

第二個範例在解釋 Shadow DOM,看起來也解釋的很不錯...

第三個範例回來原來產生程式碼的例子,拿來生 SQL 指令。

後面的 bonus 題目居然是拿來解釋數學公式,他直接丟 TeX 文字進去要 GPT-3 解釋柯西不等式 (Cauchy–Schwarz inequality)。這樣我想到以前高微作業常常會有一堆證明題,好像可以丟進去要 GPT-3 給證明耶...

Perl 的 Regular Expression 的強度:NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目,就像是維基百科上的條列:

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合,而 CFG 對應到的語言是 CFL,另外他對應到的自動機是 PDA

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern),所以他能接受的 language 已經超過 RL,但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻,查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library):「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章,裡面給了一個在 PTIME 演算法,將 3SAT 轉換到 PCRE 裡解,這證明了 PCRE 是 NP-hard;另外也很容易確認 PCRE 是 NP,所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已,沒想到這麼強,NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD

GitHub 搜尋的改善

GitHub 宣佈搜尋的新功能與改善:「Improving GitHub code search」。

其中對我感覺比較有趣的是宣佈支援 regular expression,透過 / 包起來搜:

Search for an exact string, with support for substring matches and special characters, or use regular expressions (enclosed in / separators).

不知道後面的搜尋系統怎麼做的,我猜是先拉出 substring 搜尋,然後 filtering 處理?

Regular Expression 版本的填字遊戲

Update:被朋友提醒在 2014 年的時候寫過了:「Regular Expression 字謎遊戲...」。

Hacker News Daily 上看到的填字遊戲,跟一般的填字遊戲不同的是,他的靠 Regular expression 表達規則:「RegEx Crossword」。

Hacker News 上面的討論有教你怎麼算,不過建議先自己玩看看:「RegEx Crossword (jimbly.github.io)」。

之前就有印象有看過,但用 Hacker News 上的搜尋引擎只翻到這次。跑到 GitHub 上翻了一下他的 commit log,的確是個老遊戲了 XD

好像可以推薦大學裡在教 DFA/NFA/RE 的時候可以帶出來?

第四堂:「Data Wrangling」

有陣子沒寫了,來還個債...

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這邊講的是「Data Wrangling」這篇。

這篇是在講 pipe 的用法,在講這些工具之前,其實有個很重要的概念應該要說明 (但沒有在這篇文章裡被提到),也就是 Unix philosophy,這個哲學是指 unix 環境下的工具,都會設計成只做好一件事情。

而要怎麼把這些工具串起來,最常見的就是 pipe,你可以在文章裡看到 grepsedsort 這些工具的用法,以及怎麼用 pipe 串起來。

這邊剛好也可以提一下,利用 pipe 可以把不同功能打散到不同的 process 上,剛好也可以稍微利用到現在常見的多 CPU 的環境。

另外上面因為提到了 grep,文章內花了不少篇幅在講 Regular expression 這個在 CS 課程裡面也是重要的基礎。

會放這種篇幅長度,一方面是 Regular expression 的實用性很高,另外一方面,學術上與自動機理論中的 DFANFA 都有關,算是學習計算理論的起點:

然後後面就有提到 AWK 這個工具,這邊要注意的是,雖然可以用 Perl 之類的工具作到類似的事情 (而且更強大),但 AWK 有被放到 POSIX 標準裡,所以在各種作業系統內幾乎都一定會出現,加上語法算是簡單,學起來還是很有幫助...

然後再最後面的段落冒出一個 gnuplot 畫個圖,以及示範 xargs 這種神器要怎麼用 (這邊會更建議看一下 manpage,可以配合 find 之類的工具用,並且平行化同時處理)。

然後最後示範了 binary data 怎麼處理。

Cloudflare 因為 Regular Expression 炸掉的問題

先前 Cloudflare 就有先說明七月二日的 outage 是因為 regular expression 造成的 (ReDoS),不過昨天發的文章更完整了,導致爆炸的 regular expression 都給出來了:「Details of the Cloudflare outage on July 2, 2019」。

ReDoS 不算是新的問題,但卻是不太好避免的問題,因為需要有經驗的工程師 (中過獎的工程師) 才比較容易知道哪些 regular expression 是有問題的... 另外就是有花時間研究 regular expression 演算法的工程師也比較容易避開。

也因次,ReDoS 算是這十年來大家在還的債,各家 framework 都因為這個問題改寫了不少 regular expression。

這次的重點在這串式子導致了 ReDoS:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

通常容易中獎的地方就是無限制字元與 * & + 連發的地方,後面這塊 )*.*(?:.*=.*))) 看起來就不太妙,果然在後面的分析也有提到:

The critical part is .*(?:.*=.*).

以前應該是在 Formal language 裡學到的,在課堂裡面其實會學到不少業界常用工具的基礎理論...

用 Userscript 在 Gmail 裡面展開連結

前一篇「在 Gmail 裡面展開 GitHub 信件連結的 Userscript」是展開 GitHub 的連結,但這個套件是用document.querySelectorAll() 抓出來,裡面寫死了不少東西...

用了幾天後我還是只想開 commit 相關的連結 (用 regex 表示的話就是 ^https://github\.com/[^/]+/[^/]+/commit/),所以就找看看 Tampermonkey 能不能有 Config Page 或是 Option Page 可以讓使用者設定,結果發現本身沒支援:「Create a “config” or “options” page for a Greasemonkey script」。

但回覆裡面有提供一些方案可以用,我後來選了 MonkeyConfig,至少可以讓使用者設定 regex...

新的 Userscript 放在「open-links-in-gmail」這邊。

AWS WAF 支援 Regex (PCRE)

首先是 AWS WAF 支援 Regex 了:「AWS WAF Now Supports Regular Expressions (Regex)」。

而且是以 PCRE 版本為主:

AWS WAF supports most of the standard Perl Compatible Regular Expressions (PCRE).

這樣設定變得方便很多啊,大家都算熟 regex,而且也夠強大...

另外一個公告是 AWS WAF 可以將地區的當條件進行設定了:「AWS WAF Now Supports Geographic Match」。

除了針對某些地區擋掉或是開放以外,也可以針對不同地區設定 rate limit。當條件設定就是了...