# 2025q1 Homework1 (lab0)
contributed by < [`JeepWay`](https://github.com/JeepWay) >
### Reviewed by `liangchingyun`
> rebase 前的 commit 已經不在 branch 上，可以不用提供，只需提供 rebase 後的 commit 即可。
> > [name=JeepWay]
> > 感謝你的建議，rebase 後沒有改變程式碼跟 commit message，確實適合留 rebase 後的 commit 就好。 By JeepWay
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-1240P
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 3
CPU(s) scaling MHz: 16%
CPU max MHz: 4400.0000
CPU min MHz: 400.0000
BogoMIPS: 4224.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 448 KiB (12 instances)
L1i: 640 KiB (12 instances)
L2: 9 MiB (6 instances)
L3: 12 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
## 開發過程 (queue.c)
開發時間是在看到 commit [1d68fae](https://github.com/sysprog21/lab0-c/commit/1d68faec1ffc912e7e5d1098a3d46fbf835fee49) 且重新 fork 後，這個 commit 主要是跟 Cppcheck 回報 `unknownMacro` 有關，會觸發該回報的句集是 `list_for_each_entry` 跟 `list_for_each_entry_safe`。
### q_new
> Commit [766c7e8](https://github.com/JeepWay/lab0-c/commit/766c7e8dde06c43c11705b5c05f861f5715c542b)
使用 `malloc` 來配置記憶體，如果指標 `q` 為 `NULL`，代表配置失敗，則回傳 `NULL`。
若配置成功則使用 `INIT_LIST_HEAD` 函式初始化鏈結串列，然後回傳鏈結串列的 `head` 的記憶體地址。
### q_free
> Commit [eac3ad4](https://github.com/JeepWay/lab0-c/commit/eac3ad4b9ead052c18f6fe4b2eb4cabc514319f1)
我在使用 `list_for_each_entry` 巨集時，`make test` 有正確執行拿到預期分數，但是在提交程式碼時，會遇到以下錯誤：
```
Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:31:5: style: Label 'int' is not used. [unusedLabel]
list_for_each_entry_safe (entry, safe, head, list)
^
Fail to pass static analysis.
```
這似乎是 Cppcheck 的靜態分析報告，而錯誤源頭正是 commit [1d68fae](https://github.com/sysprog21/lab0-c/commit/1d68faec1ffc912e7e5d1098a3d46fbf835fee49) 新增的程式碼，`int` 被識別為一個 label 而非類型。為了忽略這種誤判，我參考老師在 `queue.c` 最上方的註解，在 `list_for_each_entry_safe` 的前一行添加 `/* cppcheck-suppress unusedLabel */`，來忽略 Cppcheck 對於 `list_for_each_entry_safe` 的靜態分析報錯，以順利提交程式碼。
```diff
+ /* cppcheck-suppress unusedLabel */
list_for_each_entry_safe (entry, safe, head, list)
q_release_element(entry);
```
在 `q_free` 函式中，使用 `list_for_each_entry_safe` 巨集來安全地遍歷鏈結串列中的每一個節點，其中 `entry` 指標指向當下要被釋放記憶體的節點，`safe` 指標指向下一個要被處理的節點，指標指向的地址已經由 `list_for_each_entry_safe` 巨集處理，因此我們不用再去更新指標的內容。
在釋放記憶體時，可使用 `queue.h` 裡的 `q_release_element` 函式來完成，以精簡程式碼。
### q_insert_head, q_insert_tail
> Commit [b5f6901](https://github.com/JeepWay/lab0-c/commit/b5f6901f2f816b7ff4864957f885ff228986701e)
使用幫手函式 `q_new_element` 來建立 `element_t` 物件，在函式裡面使用 `harness.h` 的 `strdup` 巨集 (即 `harness.c` 中的 `test_strdup` 函式) 為字串配置新的記憶體空間。使用 `strdup` 後，要檢查是否成功，如果失敗，要記得釋放掉已經配置好的記憶體，然後回傳 `NULL`。如果成功則回傳建立的 `element_t` 物件的記憶體地址。
```cpp
element_t *q_new_element(char *s)
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return NULL;
char *tmp = strdup(s);
if (!tmp) {
free(e);
return NULL;
}
e->value = tmp;
return e;
}
```
`element_t` 物件建立成功後，`q_insert_head` 跟 `q_insert_tail` 即可分別透過 `list_add` 和 `list_add_tail` 函式將節點插入到鏈結串列的頭跟尾。
### q_remove_head, q_remove_tail
> Commit [1262fa9](https://github.com/JeepWay/lab0-c/commit/1262fa9ba00f7b5d33dd80b8b232faad6001cd63)：第一版。
> Commit [c649686](https://github.com/JeepWay/lab0-c/commit/c6496868c5d3e2f66ae8039484fa19b05b5520f3)：第二版，修正放入 buffer `sp` 的字串的長度。
因為 `q_remove_head` 跟 `q_remove_tail` 函式的程式碼有高度重疊性，主要差異於是使用 `list_first_entry` 還是 `list_last_entry` 來找到要移除的節點，所以整合成一個函式 `q_remove`。`q_remove_head` 跟 `q_remove_tail` 透過傳遞布林變數 `from_head` 的值，以指定要使用 `list_first_entry` 還是 `list_last_entry` 來找到目標節點。
```cpp
element_t *q_remove(struct list_head *head,
bool from_head,
char *sp,
size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *element;
if (from_head)
element = list_first_entry(head, element_t, list);
else
element = list_last_entry(head, element_t, list);
list_del_init(&element->list);
if (sp) {
size_t len = strlen(element->value) + 1;
memcpy(sp, element->value, len);
}
return element;
}
```
找到節點後，就可以用 `list_del_init` 函式把節點從鏈結串列中移除，並且把節點的 `next` 跟 `prev` 指標初始化成指向自己，避免透過指標找到原有鏈結串列中的其他節點。
`q_remove_head` 跟 `q_remove_tail` 只是將節點從鏈結串列中移除，即切斷連接，並沒有釋放掉節點本身所佔用的記憶體空間。而釋放移除節點使用的記憶體這項操作，會在 `qtest.c` 中的 [q_release_element(re);](https://github.com/sysprog21/lab0-c/blob/master/qtest.c#L363) 完成。
按照 `queue.h` 的描述，當 buffer `sp` 不是空指標且有移除節點時，需要將被移除的節點的字串內容複製到 `sp` 指向的記憶體地址，所以使用 memcpy 函式來完成，其中複製長度為 `strlen(element->value) + 1`，其中 `+1` 是給字串的結束字元 `\0`。相似作法可以參考 `harness.c` 中的 [test_strdup](https://github.com/sysprog21/lab0-c/blob/master/harness.c#L228)。
這邊要注意的是，當 `sp` 不是空指標時，代表 `sp` 已經在 `qtest.c` 中透過 `malloc` 配置好記憶體，所以不能再使用 `strdup` 來複製字串，因為 `strdup` 會使用到 `malloc`。例如 `sp = strdup(element->value);`，如果使用 `strdup` 會出現以下錯誤。
```
ERROR: Failed to store removed value
```
#### 修正放入 buffer `sp` 的字串的長度
原本以為 buffer `sp` 是存放所有節點的整個字串內容，但在 `make test` 發現過不了 trace-07-string。
```shell
+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
Error limit exceeded. Stopping command execution
--- trace-07-string 0/6
```
於是去查看測資發現有 `option length 30` 這種命令，這會改變 `qtest.c` 中的 `string_length` 全域變數，而 `string_length` 正是需要放入 buffer `sp` 的字元數量，所以我原本 `q_remove` 函式的實作是錯的，修正過後的程式碼如下：
```diff
if (sp) {
- size_t len = strlen(element->value) + 1;
- memcpy(sp, element->value, len);
+ memcpy(sp, element->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
}
```
傳入的 `bufsize` 是 `string_length + 1`，`+ 1` 是給中止字元，所以 `memcpy` 複製的長度是 `bufsize - 1`，`sp[bufsize - 1] = '\0'` 則是設定字串的中止字元。修改過後的程式碼即可通過測資。
### q_size
> Commit [a028eb6](https://github.com/JeepWay/lab0-c/commit/a028eb6f4c37fb2c65a3c745314e01fdf103806f)
使用 `list_for_each` 走訪 `linked list` 上的所有節點，並使用變數 `size` 紀錄有多少個節點，然後回傳節點數。
### q_delete_mid
> Commit [c940a11](https://github.com/JeepWay/lab0-c/commit/c940a11a56b4506137dbae7cda63d28d784993ca)
常見的做法是使用快慢指標找到中間節點，但我們的鏈結串列是雙向的，而非單向的，因此只需一行程式碼 (`struct list_head *right = head->prev;`) 就可以取得鏈結串列的最後一個節點。
作法是用兩個指標分別指向鏈結串列的第一個和最後一個節點，然後輪流遍歷鏈結串列，每次移動一個節點，直到兩個指標指向相同位址 (奇數個節點) 或者相鄰位址 (偶數個節點)，此時就找到中間節點了。
這個方法總共只需要走訪 n 個節點 (n 是鏈結串列的節點數量)，如果使用快慢指標策略則需要走訪 1.5n 個節點。
### q_delete_dup
> Commit [dc10571](https://github.com/JeepWay/lab0-c/commit/dc10571471abcaf8f021340e8d7fff30ef7cf4b5)
建立鏈結串列 `removed` 來收集所有重複的節點。使用布林變數 `has_duplicate` 來紀錄是否遇到擁有重複字串的節點。在判斷字串是否相同時，使用 `strcmp` 即可，因為我們的字串內容都是只有一個單字。如果兩個字串擁有同樣內容，則 `strcmp` 會回傳 0，所以我們判斷相同的條件是 `!strcmp(node->value, safe->value)`。
```cpp
/* cppcheck-suppress unusedLabel */
list_for_each_entry_safe (node, safe, head, list) {
if (&safe->list != head && !strcmp(node->value, safe->value)) {
list_move_tail(&node->list, &removed);
has_duplicate = true;
} else if (has_duplicate) {
list_move_tail(&node->list, &removed);
has_duplicate = false;
}
}
/* cppcheck-suppress unusedLabel */
list_for_each_entry_safe (node, safe, &removed, list)
q_release_element(node);
```
當發現具有重複字元的節點時，第一個 `if` 條件會將第一個重複元素從原本的鏈結串列中移除，並將其加入到待刪除的鏈結串列 `removed` 中。接著，將 `has_duplicate` 設為 `true`，表示發現了一組包含重複字元的子鏈結串列。第二個 `if` 條件則確保這組具有重複字元的子鏈結串列的最後一個節點也會被移除。
在遍歷整個鏈結串列 `head` 後，可以確保鏈結串列 `head` 中不再包含具有重複字元的節點。隨後，使用 `list_for_each_entry_safe` 來釋放鏈結串列 `removed` 中節點所佔用的記憶體。
### q_reverse
> Commit [7bee3c4](https://github.com/JeepWay/lab0-c/commit/7bee3c48654fa36f8d71dd3f68bbe5562d3ea068)
使用 `list_for_each_safe` 函式遍歷鏈結串列中每個節點，然後把節點重新插入到鏈結串列中，即可達成反轉的效果。要達成重新插入需要使用 `list_move` 函式。
### q_reverseK
> Commit [3eafba8](https://github.com/JeepWay/lab0-c/commit/3eafba808de3ef0fd969823edb7cc822ffb746b7)
```cpp
list_for_each_safe (node, safe, head) {
count++;
list_move(node, &sub_list);
if (count == k) {
list_splice_init(&sub_list, cur_head);
cur_head = safe->prev;
count = 0;
}
}
```
函式定義了一個臨時的 `list_head` 結構 `sub_list`，用於收集每一組的 k 個節點，並透過一個計數器 `count` 追蹤已收集的節點數量，以及指標 `cur_head` 來紀錄當前處理的子鏈結串列的前一個節點，以方便反轉後更新鏈結。
在遍歷過程中，函數使用 `list_for_each_safe` 安全地逐一訪問鏈結串列中的每一個節點，並使用 `list_move` 函式將節點移到 `sub_list` 中，因為是插入到 `sub_list` 的 `head`，所以 `sub_list` 內的節點就相當於是反轉過後的節點，這個策略跟 `q_reverse` 是一致的。每當計數器達到 k 時，表示已收集到一組完整的 k 個節點 (已反轉順序)，此時透過 `list_splice_init` 將這組節點拼接到 `cur_head` 之後的位址，並更新 `cur_head` 為當前這一組的結束節點（即 `safe->prev`），作為下一組子鏈結串列的前一個節點，同時重置計數器 `count` 為 0，即可準備處理下一組的 k 個節點。
對於鏈結串列尾端不足 k 個的剩餘節點（在 sub_list 中），函式會使用 q_reverse 將 sub_list 反轉，以回到原始鏈結串列的順序，因為題目要求不足 k 個的剩餘節點不能做反轉。之後在將反轉後的 sub_list 接回原始鏈結串列即可。
### q_swap
> Commit [1fd7e8d](https://github.com/JeepWay/lab0-c/commit/1fd7e8d0ae2e270e0cc043e7967bc45126d2c51f)
結果與 `K = 2` 的 `q_reverseK` 相同，呼叫 `q_reverseK` 即可。
### q_ascend, q_descend
> Commit [453e4d8](https://github.com/JeepWay/lab0-c/commit/453e4d8bf0f742e547be097a914123e16f6b747c)
參考 [slipet](https://hackmd.io/@Slipet/ryrLNN4Ah#q_ascend-and-q_descend) 的方法
`q_ascend` 是從鏈結串列的第一個節點開始訪問，往最後一個節點移動；`q_descend` 是從鏈結串列的最後一個節點開始訪問，往第一個節點移動。
兩種方法都是紀錄訪問過程中的最大值 (使用 `strcmp` 比較)，若有發現比最大值還小的節點，則移除該節點，以維持鏈結串列的單調性。若有發現更大的，則更新最大值。
在提交程式碼時，原本 `max` 指標的型態是 `char *`，但這樣會不能通過 Cppcheck 的靜態分析。
```shell
Running static analysis...
queue.c:241:11: style: Variable 'max' can be declared as pointer to const [constVariablePointer]
char *max = node->value;
^
Fail to pass static analysis.
```
而要忽略這種檢查有以下兩種方法：
方法 1
```diff
+ /* cppcheck-suppress constVariablePointer */
char *max = node->value;
```
方法 2
```diff
- char *max = node->value;
+ const char *max = node->value;
```
我最後選擇方法 1，因為指標指向的地址是會更改的，不是 `const`，所以採用方法 1 更合理。
### q_sort
> Commit [1fb72f2](https://github.com/JeepWay/lab0-c/commit/1fb72f20615ee98a3d6dc136b07c9b265f29e8ea)
使用 top-down 方法來進行 merge sort，每次將鏈結串列從中間節點分割成兩個子鏈結串列，利用前後端指標（front-end pointer）遍歷來識別中間節點。`q_sort` 遞迴地對每一半進行排序，再使用 `q_merge_two` 輔助函式將排序後的兩個子鏈結串列合併成一個鏈結串列。
`q_merge_two` 會比較來自兩半的相鄰元素，使用 `strcmp` 根據 `descend` 參數（決定升序或降序）來構建排序後的串列，並將結果插入到 `head` 的尾端。
在提交程式碼時，Cppcheck 提示指標 `l_elem` 和 `r_elem` 可以用來 `const` 來修飾。
```shell
Running static analysis...
queue.c:235:20: style: Variable 'l_elem' can be declared as pointer to const [constVariablePointer]
element_t *l_elem = list_entry(l, element_t, list);
^
queue.c:236:20: style: Variable 'r_elem' can be declared as pointer to const [constVariablePointer]
element_t *r_elem = list_entry(r, element_t, list);
^
Fail to pass static analysis.
```
`const element_t *` 型態的指標表示不能使用這個指標來改變其所指向變數的值，即不能用這個指標來更改節點的值。而在這個函式中，確實不會更改節點的值，只會存取節點的字串內容，所以加上 `const` 來修飾這個指標更為恰當。
```diff
- element_t *l_elem = list_entry(l, element_t, list);
- element_t *r_elem = list_entry(r, element_t, list);
+ const element_t *l_elem = list_entry(l, element_t, list);
+ const element_t *r_elem = list_entry(r, element_t, list);
```
### q_merge
> Commit [c39d023](https://github.com/JeepWay/lab0-c/commit/c39d0232615800a03b9d06638dc8a1afad38e29a)
`q_merge` 可以透過使用 `q_merge_two` 函式來完成，原理是把第一個佇列跟下一個佇列做合併，合併到暫時的 `merged` 佇列，然後再把 `merged` 佇列的結果移回第一個佇列。一直持續這樣的操作直到剩下一個佇列。
```cpp
int queue_num = q_size(head);
while (queue_num > 1) {
LIST_HEAD(merged);
q_merge_two(&merged, current->q, next->q, descend);
list_splice_tail_init(&merged, current->q);
next = list_entry(next->chain.next, queue_contex_t, chain);
queue_num--;
}
```
在原本的 `q_merge_two` 函式中，合併完後並沒有初始化 `left` 和 `right` 指向的鏈結串列，這樣的作法在 `q_sort` 是可行的，因為不會再透過 `left` 和 `right` 指標對鏈結串列做操作，但是在 `q_merge` 時，就會有這種操作，即以下程式碼：
```cpp
list_splice_tail_init(&merged, current->q);
```
需要把合併後的結果再放回 `current->q` 第一個佇列，這裡的 `current->q` 一定要是空佇列，不然會出現無限迴圈，所以 `q_merge_two` 函式必須修改成合併完後再次初始化，`q_merge_two` 函式的差異如下：
```diff
if (l != left)
- list_splice_tail(left, head);
+ list_splice_tail_init(left, head);
if (r != right)
- list_splice_tail(right, head);
+ list_splice_tail_init(right, head);
```
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
到這邊為止 `make test` 的分數是 95/100
## 提供新的命令 shuffle
> Commit [fa867ad](https://github.com/JeepWay/lab0-c/commit/fa867ad72e2524b984ca0e0683d5e3e1975ab289)
```cpp
static void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int len = q_size(head);
struct list_head *left;
struct list_head *right = head;
for (; len > 1; len--, right = right->prev) {
int idx = rand() % len;
if (idx == len - 1)
continue;
left = head;
while (idx--)
left = left->next;
list_move(right->prev, left);
list_move_tail(left->next->next, right);
}
}
```
### 統計方法驗證 shuffle
* 虛無假說 $H_0$：shuffle 後的各種可能結果發生的機率遵守 Uniform distribution。
* 對立假說 $H_1$：shuffle 後的各種可能結果發生的機率至少有一個不相同。
#### 1. 計算 chi-squared test statistic $X^2$
$$
X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}
$$
使用作業說明提供的測試用的 Python 腳本 [shuffle_test.py](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 進行測試，得到以下統計數據與直方圖。
```shell
Expectation: 41666
Observation: {'1234': 41425, '1243': 41658, '1324': 41691, '1342': 41614, '1423': 41792, '1432': 41607, '2134': 41396, '2143': 41771, '2314': 41734, '2341': 41592, '2413': 41732, '2431': 41848, '3124': 41714, '3142': 41449, '3214': 41958, '3241': 41661, '3412': 41948, '3421': 41756, '4123': 41851, '4132': 41362, '4213': 41551, '4231': 41631, '4312': 41199, '4321': 42060}
chi square sum: 22.777756444103108
```
總共測試 1000000 次 shuffle，而可能組合有 4! = 24 種可能，所以每種可能的預期出現次數是 $\lfloor \frac{1000000}{4!} \rfloor = 41666$。測試結果的卡方值 $X^2=22.777756444103108$
#### 2. 決定自由度
shuffle 4 個數字一共會有 4! 種結果，所以有 4! = 24 個樣本，自由度為 24 - 1 = 23。
#### 3. 選擇顯著水準
設定顯著水準 $\alpha = 0.05$，代表在虛無假說（$H_0$）成立的情況下，錯誤地拒絕 $H_0$（即判斷為不均勻但實際尚為均勻分佈，這叫 type I 錯誤）的機率控制在 0.05。
```python
from scipy.stats import chi2
print(chi2.ppf(0.95, 23)) # 卡方臨界值 35.17246162690806
print(1 - chi2.cdf(22.777756444103108, 23)) # 此測試的 P 值 0.4738098373906663
```
#### 4. 結論
透過 python 的 scipy 套件得知此測試的 $P$ 值 0.4738098373906663，因為 $P$ 值大於顯著水準 0.05，所以不拒絕 $H_0$，表示洗牌結果符合均勻分佈。
## 研讀論文〈Dude, is my code constant time?〉
## Web 命令/網頁伺服器改善
> Commit [d64ace7](https://github.com/JeepWay/lab0-c/commit/d64ace78377227616025c1913c51c3a1099828b1)
在不修改原始程式碼情況下，在 `qtest` 命令直譯器中輸入 `web` 開啟網頁伺服器後，在另外一個終端機使用 `curl` 命令進行連線，例如以下命令：
```shell
$ curl http://localhost:9999/new
$ curl http://localhost:9999/ih/1
```
會在 `qtest` 命令直譯器中看到以下結果，沒有出現 `favicon.ico` 的問題。
```shell
cmd> web
listen on port 9999, fd is 3
cmd>
l = []
cmd>
l = [1]
```
但如果直接在網頁瀏覽器 (chrome) 輸入上方例子的那些網址，`qtest` 命令直譯器會出現不預期的結果。
```shell
cmd> web
listen on port 9999, fd is 3
cmd>
l = []
cmd>
Unknown command 'favicon.ico'
cmd>
l = [1]
cmd>
Unknown command 'favicon.ico'
```
佇列的操作是正確的，但多出現 `Unknown command 'favicon.ico'` 這種訊息，這是某些網頁瀏覽器會要求給予網頁圖案的需求。
接著觀察網頁瀏覽器的檢查工具的 Network 分頁，可以發現命令 `new` 有成功送出，而且 `favicon.ico` 的請求狀態 (200) 也是成功的，不是錯誤碼 404。
而在使用 `send_response()` 來回應後，會看到 Network 分頁有不一樣的結果。為了通過 pre-commit hook 的 fmtscan，
```cpp
void send_response(int out_fd)
{
char *buf =
"HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
"Content-Type: text/html\r\n\r\n"
"<html><head>"
"<style>body{font-family: cursive; font-size: 13px;}"
"td {padding: 1.5px 6px;}"
"</style><link rel=\"shortcut icon\" href=\"#\">"
"</head><body><table>\n";
web_send(out_fd, buf);
}
```
原本的 `favicon.ico` 不見了，反而多了一個新的請求 `new`，Request URL 變成了 `http://localhost:9999/new`，但是 Request Headers 卻沒有變。可以得知這個新的請求 `new` 是由原本的 `favicon.ico` 觸發的。再次使用網頁瀏覽器輸入網址會得到以下結果。
```shell
cmd> web
listen on port 9999, fd is 3
cmd>
l = []
cmd>
l = []
cmd>
l = [1]
cmd>
l = [1 1]
```
至於為何會再次觸發？ 是因為 `<link rel="shortcut icon" href="#">` 讓瀏覽器解析到這個 `<link>` 標籤後，會嘗試從 `href="#"` 指定的 URL 載入圖標。但因為 `href="#"` 實際上是指向當前頁面 `(http://localhost:9999/new)`，所以網頁瀏覽器會再次發送一個 `GET /new` 請求，而不是 `GET /favicon.ico`，這也就是會多一個新的請求 `new`。
要解決再次觸發問題，需要更改 href 的內容，有以下可能的方法：
1. 提供正確的 favicon 位置，例如 `href="images/c-icon.png"`，但這樣經過 `parse_request` 函式解析網址後，網頁就會導向 `http://localhost:9999/images/c-icon.png`，直譯器會出現 `Unknown command 'images'`，這顯然不是我想要的。
2. 導向給一個不做事的命令，例如 `href="nothing"`，網頁就會導向 `http://localhost:9999/nothing`，並在 `qtest.c` 新增 `do_nothing` 函式並註冊。這樣可以保障伺服器正常運作，但會在 `qtest` 的直譯器中看到執行 `nothing` 這個命令，不是很美觀。
3. 參考 [BennyWang1007](https://hackmd.io/@BennyWang/linux2025-homework1#Web-%E5%91%BD%E4%BB%A4%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8%E6%94%B9%E5%96%84) 的作法。把 href 改為空的 data url `href="data:,"`，以防止送出重複的 request。
經過方法 3 的修改，有很意外的發現：
* 透過 curl 命令或者直接在 FireFox 執行上面的命令後，結果是正確的，直譯器也能再輸入任何命令。
* 直接在 Chrome 的無痕視窗執行上面的命令後，結果是正確的，頁面也正確渲染，直譯器也能再輸入任何命令。
* 直接在 Chrome (非無痕視窗) 執行上面的命令後，結果是正確的，但是**直譯器沒有反應，不能再輸入任何字元，需要等待一段時間才能再輸入命令**，而且等待過程中會再多執行一次命令 `new`。
現在還沒有找出原因，但已經排除是 Chrome 的外掛插件問題。
### 傳送標準輸出的結果到網頁
參考 BennyWang1007 的 Commit [83ed391](https://github.com/BennyWang1007/lab0-c/commit/83ed391a6e117f0b2e6fcd9277f95e9d00e72fa2)。
把 `console.c` 中的全域變數 `web_connfd` 移動到 `web.c` 中。
在原本的 `web_eventmux()` 函式中，有關閉連線 `web_connfd`，但是在後面程式碼有使用到 `report()` 函式 ( 例如 `q_show(3)`)，而在 `report()` 函式需要將原本輸出到標準輸出的結果也當作 HTTP response 傳回給 client，所以使用了 `web_send()` 函式，但此時連線已經在 `web_eventmux()` 中關閉了，這會造成錯誤。
所以需要把 `web_eventmux()` 中的 `close(web_connfd)` 移動到 `report()` 函式裡面。在傳送完標準輸出的結果後，再多傳送 `"\0"` 來表示中止，之後才關閉連線，然後重新設定 `web_connfd`。
至於相關的 `report_noreturn()` 函式則不用做修改，因為使用該函式後，還會再呼叫 `report()` 函式，所以交給 `report()` 函式來關閉連線就好。
```diff
...
if (web_connfd) {
...
web_send(web_connfd, buffer);
+ if (write(web_connfd, "\0", 1) == -1)
+ perror("write");
+ close(web_connfd);
+ web_connfd = 0;
}
...
```
### 使用命令 `show` 無法顯示佇列資訊在網頁或 curl 命令
在直譯器中手動輸入 `show`
```shell!
cmd> show
Current queue ID: 0
l = [1]
```
透過 `curl` 命令輸入 `show`
```shell
$ curl http://localhost:9999/show --output -
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="data:,"></head><body><table>
Current queue ID: 0
```
可以發現使用 `curl` 命令來執行 `show` 命令，`show` 命令會呼叫兩次 `report()` 函式，但是每次呼叫 `report()` 函式都會檢查是否有連線，並關閉連線，所以在第一次呼叫 `report()` 函式，連線就會關閉，因此呼叫第二次 `report()` 函式時，就無法傳送 `l = [1]`，因為連線已經關閉了。
解決辦法是新增關閉連線的條件，由 `do_show()` 裡面的 `report(1, "Current queue ID: %d", current->id);` 可以得知傳入 `report()` 函式的 fmt 是 `"Current queue ID: %d"`，所以判斷條件就是 fmt 裡是否含有 `Current queue ID`，如果含有就提早回傳，不執行後面的關閉連線操作。
```diff
...
if (web_connfd) {
...
web_send(web_connfd, buffer);
+ if (strstr(fmt, "Current queue ID")) {
+ if (write(web_connfd, "<br>\0", 5) == -1)
+ perror("write");
+ return;
+ }
if (write(web_connfd, "\0", 1) == -1)
...
}
...
```
並且再多傳送 `"<br>\0"` 讓網頁伺服器能把渲染出換行，提昇可讀性，如下面的圖片 (FireFox)。
### 忽略 `fmtscan` 對 HTML 標籤屬性的檢查
當提交 commit 時，會出現以下提示：
```shell
Running fmtscan...
href
rel
7813 lines scanned (0.237M bytes)
53 printf style statements being processed
2 unique bad spellings found (2 non-unique)
[!] Check format strings for spelling
```
`href` 和 `rel` 正是伺服器回應的 link 標籤的屬性，`fmtscan` 應該忽略對這些標籤屬性的檢查，所以我修改了 `tools/fmtscan.c`，新增了要忽略的標籤屬性。
```diff
+ /* HTML-related tags to ignore */
+ static char *ignore_html_tags[] = {
+ "href",
+ "rel",
+ };
+ static inline bool is_ignored_html_tag(const char *word)
+ {
+ for (size_t i = 0; i < SIZEOF_ARRAY(ignore_html_tags); i++) {
+ if (strcmp(word, ignore_html_tags[i]) == 0) {
+ return true;
+ }
+ }
+ return false;
+ }
static inline void add_bad_spelling(const char *word, const size_t len)
{
if (find_word(word, printf_nodes, printf_node_heap))
return;
+ if (is_ignored_html_tag(word))
+ return;
...
}
```
Sign in with Wallet
Connect another wallet