# 2020q3 Homework1 (lab0)
contributed by < `eecheng87` >
###### tags: `進階電腦系統應用2020`
由於上個學期於 linux 核心設計已經做過 lab0，所以這次共筆只紀錄上學期沒做的部份
## linenoise 運作原理
linenoise 專案的訴求是希望能夠用少量的程式碼來實現原本需要兩多行的終端機程式，大致的功能包含：支援輸入時能透過左右方向鍵移動游標、自動補齊和歷史紀錄等等…
由於功能眾多，這裡就只挑幾個來解釋運作原理。若看不懂 `README` 的描述可以直接 clone 下來操作。
### 移動游標
首先要來看一個貫串專案的核心結構 `linenoiseState`:
```cpp
struct linenoiseState {
int ifd; /* Terminal stdin file descriptor. */
int ofd; /* Terminal stdout file descriptor. */
char *buf; /* Edited line buffer. */
size_t buflen; /* Edited line buffer size. */
const char *prompt; /* Prompt to display. */
size_t plen; /* Prompt length. */
size_t pos; /* Current cursor position. */
size_t oldpos; /* Previous refresh cursor position. */
size_t len; /* Current edited line length. */
size_t cols; /* Number of columns in terminal. */
size_t maxrows; /* Maximum num of rows used so far (multiline mode) */
int history_index; /* The history index we are currently editing. */
};
```
大部分的成員都已經有夠明顯的註解了，這裡只解釋模糊的成員。註解中的 Edited line 是指目前你在輸入的那行。而 `len` 指的是你目前已經打了幾個字：`buflen` 是指你最高能在一行打多少字。
現在開始 trace 程式碼，在 user application 可以看到單單使用 `while((line = linenoise("hello> ")) != NULL) ...` 就可以達到游標移動、插入編輯等等功能，所以可以說 `linenoise` 就是專案的核心。接著往 `linenoise` 裡面看，先不理會例外處理，找到 general case:
```cpp
} else {
count = linenoiseRaw(buf,LINENOISE_MAX_LINE,prompt);
if (count == -1) return NULL;
return strdup(buf);
}
```
從這裡可以看到 `linenoiseRaw` 會將最終該呈現載 terminal prompt 後面的字(包含游標位置等)存到 `buf`。而透過 `strdup` 回傳**新的**一份結果。所以 `line` 就可以拿到這份答案。這裡還有一個小細節是 [strdup](https://en.cppreference.com/w/c/experimental/dynamic/strdup) 回傳的是重新 allocate 的記憶體，而非原本的，所以用完 `line` 後記得要釋放(可用 API:`linenoiseFree` 或直接 `free`)。
既然已經知道 `linenoiseRaw` 的功能，繼續裡面看:
```cpp
if (enableRawMode(STDIN_FILENO) == -1) return -1;
count = linenoiseEdit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt);
disableRawMode(STDIN_FILENO);
```
可以發現要先啟動 [raw mode](https://unix.stackexchange.com/questions/21752/what-s-the-difference-between-a-raw-and-a-cooked-device-driver)，這樣才能忠實呈現你按了什麼。在 `enableRawMode` 可以看到:
```cpp
raw.c_cflag |= (CS8);
/* local modes - choing off, canonical off, no extended functions,
```
關掉了 canonical mode，即 cooked mode。
再來回到 `linenoiseRaw` 中來看另外一個重點 `linenoiseEdit` ，在這個 block 內可以看到一個很大的 `switch`，透過 [read](https://linux.die.net/man/2/read) 存到 `c` ，因為先前已經啟動 raw mode，所以可以吃到一些 [terminal character](https://www.cnblogs.com/sigai/p/7743328.html)([Linux 終端控制符](https://www.iteye.com/blog/tcspecial-2175865))，藉此判斷是按了哪個特殊鍵。舉 left-arrow 來說:
```cpp
case CTRL_B: /* ctrl-b */
linenoiseEditMoveLeft(&l);
break;
```
再往 `linenoiseEditMoveLeft` 內看:
```cpp
if (l->pos > 0) {
l->pos--;
refreshLine(l);
}
```
不難發現這裡把 `linenoiseState` 中的 `pos` 往左一格(`pos` 表示目前游標的位置)，最後呼叫 `refreshLine` 來刷新整行。這裡就很像遊戲的運作原理，先計算角色座標，接著再透過前一個步驟得到的訊息來呈現到畫面。
而 `refreshLine` 又分單行的 refresh 和多行的。先來看單行的 `refreshSingleLine`。
先解釋變數的用途以利後面邏輯的理解:
* `fd` 為即將顯示在螢幕的 file descriptor
* `plen` 為提示符號的長度，e.g. cmd> 為 4
* `abuf` 為 append buffer，提供 append 字串使用，後續的字串移動都靠此，完成所有移動再一次性的寫到螢幕上，藉此避免文字在螢幕上閃爍
* `buf` 為目前已經打的字(不含 prompt)
* `seq` 為字串處理的緩衝(稍後更詳細解釋)
這裡的設計思維是先透過 `snprintf` 將結果存到緩衝 `seq`，接著在透過 API:`abAppend` 真正連接到 `abuf` 上(每次的字串操作都是依照這種模式)。最後 `abuf` 中的 `b` 就是要寫在螢幕上的結果。寫到先前指定的 file descriptor。
接著來仔細講一下到底做了什麼字串操作:
為了方便理解，假設目前的畫面是: cmd> test| # '|' 代表游標、`pos` 為 2
```cpp
snprintf(seq,64,"\r");
abAppend(&ab,seq,strlen(seq));
```
"\r" 會將游標移到最左邊(非換行，而是同一行)，接著存到 `ab->b` 中。所以目前例子變成: |cmd>test
```cpp
abAppend(&ab,l->prompt,strlen(l->prompt));
abAppend(&ab,buf,len);
```
重新補上 prompt string 和輸入的內容，目前例子變成: cmd>test|。(這裡你可能會覺得這樣做有什麼意義，是因為這只是移動游標時的 refresh。如果是其他狀況下呼叫 refresh，那這些字串操作看起來就會有意義了)
```cpp
snprintf(seq,64,"\x1b[0K");
```
清除光標至行末字符，包括光標位置
```cpp
snprintf(seq,64,"\r\x1b[%dC", (int)(pos+plen));
abAppend(&ab,seq,strlen(seq));
```
其中的 \r\x1b[%dC 代表游標先移到最左再向右移動多少格(prompt 的長度 + 目前希望游標所在的位置)，目前例子變成: cmd>te|st。
最後一個步驟透過先前拿到的 file descriptor 寫上(write)我們操作完的字串。
### 插入字元
同樣當 `linenoiseEdit` 被觸發時，讀取最新輸入的字元 `c`，倘若都不是特殊字元(e.g. 英文字母)，在 `switch` 中會跳到 `default` 執行 `linenoiseEditInsert`
```cpp
int linenoiseEditInsert(struct linenoiseState *l, char c) {
...
else {
memmove(l->buf+l->pos+1,l->buf+l->pos,l->len-l->pos);
l->buf[l->pos] = c;
l->len++;
l->pos++;
l->buf[l->len] = '\0';
refreshLine(l);
}
...
}
```
同樣的在 refresh 前都是只更新字串的資訊而非畫面。假設目前有字串: abc|de，`|` 是想插入的位置，且想插入 'q'。[memmove](http://tw.gitbook.net/c_standard_library/c_function_memmove.html) 將 de 往右移動一格，變成 abcdde，接著 `l->buf[l->pos] = c` 將移動後的空洞換成要插入的字 `q`，所以變成 abcqde。最後就是改 state 中的資訊給 refresh 使用。而 refresh 的原理在前面已經講過了，所以不再重複說明。
### 歷史紀錄
用 `static char **history` 來存以前所有打過得 line。每當讀取新的 `cmdline` 時，呼叫 `linenoiseHistoryAdd` 來紀錄。
```cpp
if (history_len == history_max_len) {
free(history[0]);
memmove(history,history+1,sizeof(char*)*(history_max_len-1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
```
當 `history` 已經存滿的話，透過 `memmove` 將最舊的紀錄 pop out，並將所有紀錄往左移動一格。
同樣地，當 command 編輯到一半有按鍵觸發，仍是 `linenoiseEdit` 負責。若按上鍵(ctrl-p)，則會呼叫 `linenoiseEditHistoryNext(&l, LINENOISE_HISTORY_PREV)`。
```cpp
free(history[history_len - 1 - l->history_index]);
history[history_len - 1 - l->history_index] = strdup(l->buf);
```
在 `linenoiseEditHistoryNext` 中，本次 command line(尚未按 Enter) 也要存起來，以防按上又按下，就要復原剛剛打的內容。
```cpp
strncpy(l->buf, history[history_len - 1 - l->history_index], l->buflen);
l->buf[l->buflen - 1] = '\0';
refreshLine(l);
```
由於已經更新過 `history_index` ，所以直接把該值存到 `buf` 中給稍後的 refresh 顯示在螢幕上。
### 自動補齊
同樣在 `linenoiseEdit` 中，當透過 `read` 存到 `c` 是 TAB (ASCII 9)，則希望完成自動補齊。但是除了 Key code 的確認外，還需要檢查是否有相對應的 call back-function。這個檢查 `completionCallback` 是否有被賦值即可(因為預期會執行 `linenoiseSetCompletionCallback(completion)` 來作為可補齊的標準)。接著呼叫 `completeLine`，在 `completeLine` 中執行 completionCallback (這個 function pointer 已經在 `linenoiseSetCompletionCallback` 時被指定為自定義的 call-back function)。
在自訂的 call-back function 如果已經決定好要如何補齊，要呼叫 linenoise 提供的 API: `linenoiseAddCompletion("completion_string", target_buffer)` 作為取代原本的字串的選項。另一方面 `linenoiseAddCompletion` 是用來註冊支援的自動補齊庫內容，如果目前只打了 h 想按 Tab 時會補齊 `help`，那就需要呼叫 `linenoiseAddCompletion(lc, "help")`。`linenoiseAddCompletion` 的原理是將不同的補齊字串存在結構 `linenoiseCompletions` 的 `char**` 中，這種效果就像 `char* argv[]` 一樣。
簡單來說，把可能的字串加到 `cvec`，不可能的則不加。呼叫完 `completionCallback` 後回到 `completeLine`，在 `completeLine` 中:
```cpp
if (i < lc.len) {
struct linenoiseState saved = *ls;
ls->len = ls->pos = strlen(lc.cvec[i]);
ls->buf = lc.cvec[i];
refreshLine(ls);
ls->len = saved.len;
ls->pos = saved.pos;
ls->buf = saved.buf;
}
```
會直接把 cvec 的第一個吻合的字串給 `buf`(因為 `i` 從 0 開始)
## 強化 qtest 功能
### 移動游標
由於 linenoise 已經提供完善的 API 了，所以本次添加功能決定直接使用之。接著要做的事是找出 qtest 中正確的位置修改並添加 API。
在 `qtest` 中可以發現 `run_console` 是讀、解析命令的函數，在 `run_console` 首先會 `push_file` ，如果執行 `qtest` 有帶 -f 的參數就會開啟該檔案並紀錄其 file descriptor，反之則直接使用 `STDIN_FILENO`。接著就是重點 `cmd_select`，在此 block 當使用者按 Enter 時會觸發 `readline` 並得到字串 `cmdline`，接著再拿去解析。為了使游標能夠移動，我們需要稍微改寫程式，將原本的 `readline` 換成 `linenoise` 的 API:
```cpp
while (!has_infile && !block_flag &&
(cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
prompt_flag = true;
linenoiseFree(cmdline);
}
```
這裡的 `has_infile` 是用來判斷執行 `qtest` 的時候是否有帶檔案參數。
除此之外，還需要改另外一處 `readline()`:
```cpp
if (readfds && FD_ISSET(infd, readfds)) {
...
if (has_infile) {
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
} else {
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseFree(cmdline);
}
}
}
```
同理，當有帶檔案參數就要避開使用 `linenoise` 的 API。
另外則是在 `console.c` 中有一個小地方需要改
```cpp=164
char *buf = malloc_or_fail(len + 1, "parse_args");
buf[len] = '\0';
```
需要額外補上 165 行，否則當使用 `linenoise` API 時候會有一點問題。
### 自動補齊
文件已經對使用方式寫得很清楚了，此外前面也解釋過原理了，所以這裡直接展示如何引入至 `qtest`。首先需要指定一個 call-back function
```cpp
linenoiseSetCompletionCallback(completion);
```
而我的 call-back function `completion` 如下:
```cpp
void completion(const char *buf, linenoiseCompletions *lc)
{
if (completion_helper("help", buf)) {
linenoiseAddCompletion(lc, "help");
} else if (completion_helper("free", buf)) {
linenoiseAddCompletion(lc, "free");
} else if (completion_helper("ih", buf)) {
...
/* append more command if you want */
}
int completion_helper(const char *target, const char *cur)
{
int res = 1;
for (int i = 0, j = 0; i < strlen(cur); i++, j++) {
if (cur[i] != target[j])
res = 0;
}
return res;
}
```
`completion_helper` 的運作邏輯很簡單，就是比對目前有的字串和可能的 command，入產生第一個不一樣那就不理會。
### 歷史紀錄
歷史功能的添加又更簡單了，一開始須告知需要開啟歷史功能，另外則是載入上次的歷史紀錄
```cpp
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad("history.txt"); /* Load the history at startup */
```
再來則是在每次讀到 command 時，將其存起來
```cpp=574
while (!has_infile && !block_flag &&
(cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
prompt_flag = true;
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave("history.txt"); /* Save the history on disk. */
linenoiseFree(cmdline);
}
```
Sign in with Wallet
Connect another wallet