作业 2. C 字符串#

本次作业不仅可以为你解开作业 0 中的疑问，而且还是学习 C 和 Linux 的一个特别合理的方式——编写 Unix/Linux 系统并为其开发命令行工具是创建 C 语言的首要动机！实现这些程序是 C 的一种非常自然的应用场景，你将能够体会到 C 是多么适合这个角色。

这次作业用于测试你对第二个话题的理解。通过以下几个方面的训练，培养你的技能：

  • C 字符串的处理（直接处理或者使用字符串库函数处理）

  • 从内部实现的角度看待 Unix/Linux 命令行程序，而不仅仅是用户

  • 用编程的方式与文件系统和 Shell 环境变量进行交互

完成本次作业，你将实现一个自己的标准 Unix/Linux 命令行程序 printenv 和 which，以及标准库函数的改进版本。这是一个令人非常印象深刻的项目，特别是对于只学习了两周的 Unix/Linux 和 C 的同学——这感觉简直太棒了！

对于本次作业，禁止使用 getenv 和 strtok/strsep，你应该尝试编写自己的函数。对于其他需求，我们反而更推荐使用标准库函数，因为标准库已经编写完成，并且经过了严格的测试、调试以及高度的优化。使用标准库的一个首要的考虑因素是如何选择合适的库函数。例如，关于字符串的比较/搜索有几种不同的函数变体（strstr、strchr、strncmp、strspn 等），我们要根据作业要求，选择一个能够直接完成任务的函数，而不是随机选择。

为了帮助你评估学习进度，对于每个作业/实验，我们罗列了一些要点，并提供了一些思考问题。在完成作业后，可以使用这些问题进行自我检查。如果你不能很好地回答这些问题，那么还需要进一步努力。

  • 标准库包含了多个函数来执行某种形式的字符串比较，例如 strncmp、strstr、strchr、strspn……解释这些函数之间的差异并确定每个函数适用的场景。

  • 编写一个 C 表达式，将十六进制数字 char 转换为对应的数值，即 '1' 转换为 1、'f' 转换为 15。请务必考虑可以帮助完成这项工作的 string.h 函数。

  • 函数 scan_token 的第一个参数是 const char ** 类型。解释该参数使用二级指针的目的。

  • 是否添加当前目录 . 到 PATH 是有争议的（参见第 2.13 节）。这会能带来哪些便利？又会造成哪些问题？

初始项目#

你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：

cp -r /home/cs102-shared/assignments/assign2 ~/cs102

背景：文件系统和 Shell#

在本次作业中，你将编写与 Unix/Linux 文件系统和 Shell 环境变量交互的代码。在 Linux 入门课程中已经对文件系统做过简短的介绍，对于树状的目录结构、绝对和相对路径等概念，以及使用命令操作文件和目录应该不再陌生。

POSIX 标准规定了一组用于与操作系统交互的 C 函数。C 标准库仅提供简单的文件读/写函数，而 POSIX 添加了功能更全面的函数/工具集，包括访问文件系统元数据（例如修改时间戳、文件访问权限）、访问目录内容以及实现像 ls 和 mkdir 这样的命令用于操作 Unix/Linux 的文件系统。

本次作业，你将使用一个 POSIX 函数 access 检查用户对文件的操作权限。当用 C 语言以编程方式与文件系统交互时，你将使用 C 字符串来表示路径，并且可以通过字符串操作和 string.h 库函数来构造/解析路径。因此，处理文件路径就是练习使用 C 处理字符串！

在 Unix/Linux 系统上，程序在用户的“环境（environment）”上下文中运行。环境是一个键值对列表，提供有关终端会话（terminal session）的信息并用于配置进程的行为方式。当你登陆作业服务器时，系统将为你的账户配置一个 USER 环境变量，值就是你的用户名，其他变量还有 PATH（用于系统查找程序的位置）、HOME（用户主目录的路径）和 SHELL（命令行解释器）等。

作为作业的一部分，你将实现自己版本的 printenv 程序，printenv 用于显示你的环境变量。尝试以下一些命令：

  • 运行不带参数的 printenv 查看整个环境变量列表。

  • 尝试 printenv USER SHELL HOME 打印多个变量。

  • 像 printenv BOGUS 这样的错误请求，输出是什么？

使用命令 env 还允许你临时更改环境变量的值。执行 env BINKY=1 OTHERARG=2 ./myprogram 时，程序 myprogram 将在一个临时环境中执行，该环境包含所有原始的环境变量以及 BINKY 和 OTHERARG 两个补充变量。

  • 运行 ​​env BINKY=1 WINKY=2 printenv 可以查看上述临时环境的变量列表。

任务 1：实现 get_env_value#

你的第一个任务是实现一个可以单独编写和测试的函数 get_env_value，并将在稍后的作业中使用它。这个函数应该在 util.c 中实现，并在 myprintenv.c 程序中使用。

函数 get_env_value 将环境变量数组和环境变量名作为参数，并返回环境变量数组中找到的变量名的值；如果在数组中找不到，则返回 NULL。

const char* get_env_value(const char* envp[], const char* varname);

数组 envp 中的每个条目都是 VARNAME=VALUE 形式的字符串，你可以假设 VARNAME 和 VALUE 都不包含 =。注意，最后一个条目后面是 NULL 指针，用于标记该数组的结尾。你的函数应该迭代环境变量数组中的每个条目并查找匹配的项。

例如，如果 envp 包含条目 USER=stickmind，则变量 USER 的关联值为 stickmind。你的函数不需要复制字符串，它只是返回一个指向 = 字符后面的指针，从而得到原字符串的一个部分。

使用作业提供的 myprintenv.c 程序来测试该函数。如果执行 ./myprintenv，它应该像 printenv 一样打印出所有的环境变量；此命令不依赖你的 get_env_value 函数。如果指定一个或多个命令行参数，它将打印出环境中每个参数的值；此命令将依赖你的 get_env_value 函数。

你不需要修改 myprintenv.c，该程序只用于测试你的函数。为了确保实现的正确性，务必在 custom_tests 中添加完善的测试用例。

特别说明：_ 是一个特殊的环境变量，无需担心 myprintenv 的输出不一致。也就是说，如果将 _ 传递给 get_env_value，函数应该能够正确返回一个值，但 ./myprintenv _ 的输出可能与示例程序的结果不一样。

限制：get_env_value 不应调用 getenv/secure_getenv 函数。为了实现目的，该函数必须遍历通过参数传递的环境变量数组 envp 。

测试：尝试使用 env 临时更改环境变量并确保能够正确打印。例如，如果执行：

env USER=otheruser ./myprintenv USER

那么对于本次执行的 myprintenv，该命令会将 USER 环境变量更改为 otheruser，而不是你的用户名。请确保 myprintenv 打印出正确的值 otheruser。

另外，自定义测试 custom_tests 无法将 env 作为测试命令的一部分——自定义测试必须以 myprintenv 开头。如果你想使用 env 进行测试，必须手动进行。

如果想让 env 与 gdb 一起使用，请以 env 为前缀启动 gdb，然后正常运行。例如：

env USER=otheruser gdb myprintenv

任务 2：实现 scan_token#

你的第二个任务是实现一个可以单独编写和测试的函数 scan_token，并将在稍后的作业中使用它。这个函数应该在 util.c 中实现，并在 tokenize.c 程序中使用。本次作业涉及到二级指针的使用，请确保理解这些概念。

在实验 2 中，我们研究了 strtok 的实现。这种通过分隔符将字符串拆分为词元的函数有很多应用场景，但标准的 strtok 存在设计上的缺陷，并且很难使用。函数 scan_token 和 strtok 的使用方式很像，但在设计上更为简洁。其原型是：

bool scan_token(const char** p_input, const char* delimiters, 
                char buf[], size_t buflen);

该函数根据分隔符扫描输入字符串来确定下一个词元，然后将词元写入 buf，并保证词元以空字符 \0 结尾。如果词元成功写入 buf，则函数返回 true，否则返回 false。以下是该函数操作的具体细节：

  • scan_token 的实现应该采用和 strtok 类似的方法，这意味着你应该使用通用的 string.h 函数，例如 strspn 和 strcspn，但要避免 strtok 中的不良设计。具体来说，它不应该使用静态变量、修改输入字符串、在调用之间存在状态转移（即每次调用都应该独立运行）。

  • scan_token 采用和 strtok 相同的方式将输入字符串分隔为词元：该函数通过扫描输入字符串，先找到不在 delimiters 中的第一个字符，即词元的首字符。从该位置继续扫描，找到包含在 delimiters 中的第一个字符，即词元的结尾。如果找不到任何包含在 delimiters 中的字符，则输入字符串的结尾就是词元的结尾。

  • buf 是一个固定长度的数组，用于存储词元，buflen 是数组的长度。 scan_token 写入的字符不应该超过 buf 的末尾。如果 buf 无法容纳整个词元，则该函数应该只将 buflen - 1 个字符写入 buf，并在 buf 的最后写入空字符表示结尾。此外，p_input 持有的指针应该更新为指向词元 buflen - 1 个字符之后的下一个字符。换句话说，下一个扫描的词元将从溢出 buf 的第一个字符处开始。

  • 注意，参数 p_input 的类型是 char**，这是一个指向字符串的指针，充当了引用参数的作用。因为 scan_token 扫描输入字符串时需要更新该参数，以指向下一个字符，所以这是必须的。如果没有剩余字符可供扫描，则 *p_input 应指向输入字符串的结尾，即指向空字符 \0。

以下是一个循环扫描词元的示例：

const char* input = "super-duper-awesome-magnificent";
char buf[10];
const char* remaining = input;

while (scan_token(&remaining, "-", buf, sizeof(buf))) {
	printf("Next token: %s\n", buf);
}

其输出结果应该如下：

Next token: super
Next token: duper
Next token: awesome
Next token: magnifice
Next token: nt

可以使用作业提供的 tokenize.c 程序测试该函数。如果执行 ./tokenize，程序将使用你的 scan_token 函数统计几个单词的音节数。按以下格式执行该程序，你还可以指定测试的文本和分隔符等信息：

./tokenize <DELIMITERS> <TEXT> <BUFSIZE (OPTIONAL)>

例如，如果你想使用分隔符“-”和“ ”来分割文本“hello I am a C-string”，可以运行：

./tokenize " -" "hello I am a C-string"

第一个字符串包含用作分隔符的字符，第二个字符串是待处理的文本。该命令应该输出类似以下的内容：

./tokenize " -" "hello I am a C-string"
Tokenized: { "hello" "I" "am" "a" "C" "string" }

你还可以提供第三个参数，用于定义缓冲区的大小。如果不提供该参数，则缓冲区将默认有足够的空间来存储整个词元。

你不需要修改 tokenize.c，该程序只用于测试你的函数。为了确保实现的正确性，务必在 custom_tests 中添加完善的测试用例。

可以作如下假设：我们只会测试包含有效参数的函数。更具体地说，这意味着：

  • buf 是可容纳 buflen 个字符的有效内存地址

  • buflen > 1

  • p_input 是一个有效的指针

  • *p_input 是一个格式化良好的 C 字符串（可能是空字符串）

  • delimiters 是一个格式化良好的 C 字符串，包含一个或多个分隔符（不可以是空字符串）

你可能想为你的函数做好防御性检查，例如，拒绝处理 p_input 为 NULL 的值，或者当客户端传递不匹配 buflen 的 buf 时输出错误警告。虽然你的初衷是好的，但要想实现百分之百的防御是不可能的。例如，判断一个指针是否有效，通常是无解的。p_input == NULL 只会准确捕获这一种情况，但对于其他非法地址，该测试却无法捕获。作为实现者，你别无选择，只能假设客户端提供有效的地址，并编写相应的代码。

任务 3：实现 mywhich#

前两个任务通过测试和调试，完善了你的工具函数。现在可以利用它们，构建一个更大的程序：实现一个你自己的 which 命令，该命令用于定位和识别要运行的可执行程序。

文件 mywhich.c 提供了一个不完整的主函数，该函数实现了一个不带参数调用 mywhich 时的行为。你应该首先阅读并理解这部分代码，弄清楚如何更改或扩展它，以满足你自己的需求，最后为你的实现策略添加适当的注释。我们也鼓励你对现有的代码进行修改、分解，以便实现尽可能干净且设计良好的代码。

阅读代码时可以考虑以下一些关键点：

  • PATH_MAX 是什么？它有什么作用？

  • 当应用在数组上时，运算符 sizeof 可以方便地返回数组的实际大小。然而，一旦作为参数传递，该数组将退化为指向第一个元素的指针，sizeof 将返回 8 个字节而不是数组实际大小，因为指针总是 8 个字节。另外注意，如果是字符串，则数组大小不一定与字符串长度相同。

  • 如果用户的环境不包含 MYPATH 值，那么 mywhich 将使用什么值来代替？

  • 参阅 tokenize.c 和 mywhich.c 中的示例，客户端如何正确使用 scan_token？

作业代码已经删除了注释，你的工作就是完善缺失的文档。对于 tokenize.c 或 myprintenv.c 程序，根据个人精力，不强求注释。

你要编写的 mywhich 程序在行为上和标准 which 命令类似，但有以下一些差异：

  • mywhich 使用环境变量 MYPATH 作为搜索路径。如果不存在这样的环境变量，则会回退到 PATH。（标准 which 始终使用 PATH 作为搜索路径）

  • mywhich 不支持任何命令行参数。（标准 which -a 可以打印所有匹配项）

  • 不带参数调用 mywhich 会打印搜索路径中的目录，一行一个目录。这样的设计目的是提供一个测试工具，用于验证你的工具函数是否正常工作。（标准 which 没有参数时什么也不做）

    $ ./mywhich
Directories in search path:
/usr/local/sbin
/usr/local/bin
/usr/sbin
/usr/bin
/sbin
/bin
/usr/games
/usr/local/games
/snap/bin
/usr/local/ssl/bin

  • 使用一个或多个参数调用 mywhich 会分别为每个参数执行搜索任务。下面的示例演示调用 mywhich 来查找三个可执行程序。对于每个可执行程序，它会打印首个匹配到的完整路径，如果找不到路径，则不打印任何内容。每个程序的路径会按照命令行提供的顺序进行打印。在这个示例中，找到了其中的两个，但在用户 MYPATH 的所有目录中均未找到名为 xemacs 的可执行程序，因此未打印任何内容。

    $ ./mywhich xemacs submit cp
/usr/local/bin/submit
/usr/bin/cp

命令将仅包含非特殊字符，即没有 ^ # * / $ % 字符，这些在 Unix/Linux 中具有特殊含义。

你应该使用不同的搜索路径配置进行测试。我们建议你只更改 MYPATH，而不是永久更改你的实际 PATH，这可能会影响系统正常工作。修改后 MYPATH 只会影响 mywhich 的行为，对系统其它组件不会产生任何影响。使用之前提到的 env 命令在运行 mywhich 时设置 MYPATH 的值，如下所示：

$ env MYPATH=/tmp:samples ./mywhich mywhich_soln
samples/mywhich_soln

此外也建议使用 sanitycheck 和示例程序进行测试。例如，对于 ./mywhich 的任何命令参数，请尝试使用 samples/mywhich_soln 进行相同的调用，以验证你的程序和示例具有相同的行为。

可以作如下假设：假设用户能够正确使用 mywhich，并且用户的 MYPATH 和 PATH 变量正确设置，即由冒号分隔的格式化路径序列。不需要测试 -a 等命令参数，并且程序名没有特殊字符。

补充：用户的 MYPATH 定义搜索路径，如果用户环境中没有 MYPATH 变量，则为 PATH。命令 mywhich 按照路径中列出的目录顺序进行搜索。如果目录包含一个可读的可执行程序文件，其名称与命令完全匹配，则搜索将停止并打印该程序文件的完整路径。

那么如何测试一个文件是否是可执行文件呢？你必须使用库函数 access() (man access)。给定完整路径和“模式”，该函数会判断是否可以按指定模式访问该路径。模式可以是 R_OK 和 X_OK 的组合。这将验证你是否有权读取该文件，并判断该文件是否可执行。请务必仔细阅读标准库手册，了解如何正确使用该函数。

“模式”作为位掩码提供。例如，如果你想要 R_OK 和 X_OK 两个模式，则必须提供一个同时打开这两个位的掩码。

另一个小细节是，目录的权限是可读的，也是可执行的，因此对于 mywhich 来说，目录似乎也可能是可执行文件。可以使用 man stat 进一步了解文件系统来区分目录和文件，但作业不需要编写代码进行这样的检测。mywhich 应该只通过 access 过滤结果，找出可读/可执行的匹配条目即可，不需要关心这些结果是文件还是目录。这也是示例程序表现出的行为。

测试与提交#

作为作业的一部分，你应该尽可能完善 custom_tests 中的测试案例，至少添加 3 到 5 个。为了更好的可读性，也建议你为代码和测试用例编写注释或文档。这些注释将提醒你添加的每个测试的初衷，以及这些测试之间的相互关系。

作业提交方式参考作业 0，可以使用 submit 提交你的代码。为了追求完美，一些加分项值得你去注意：

  • 编译是否干净，有无警告等编译错误？

  • 默认测试是否全部通过？

  • 自定义测试案例是否全面？

对于代码实现部分：

  • 有没有其他地方，还可以使用位运算进行改写？

  • 算法是否高效？还记得如何分析算法复杂度吗？

  • 代码风格及可读性是否注意过？有没有进行函数拆分，提取出一些更通用的代码？

  • 文档有没有尝试编写？一份好的代码就如同一篇优美的散文，不多一字，也不少一字。加油！