实验1：将子字符串拼接成一个字节流

0. 合作政策

编程作业必须是你自己的工作：你必须编写你为编程作业提交的所有代码，但我们作为作业的一部分提供给你的代码除外。请不要复制和粘贴来自StackOverflow，GitHub或其他来源的代码。如果你的代码基于你在网上或其他地方找到的样例，请在提交的源代码中的注释中引用URL。

与他人合作：你不能把你的代码给别人看，也不能看别人的代码，更不能看往年的解决方案。你可以与其他学生讨论作业，但不要抄袭任何人的代码。如果你与其他学生讨论作业，请在你提交的源代码中的注释中列出他们的姓名。请参阅课程管理讲义了解更多详细信息，如果有任何不清楚的地方，请在Piazza上询问。

Piazza：请随时在Piazza上提问，但请不要发布任何源代码。

1. 概述

在实验0中，你使用Linux的传输控制协议（TCP）的内置实现，使用互联网流套接字从一个网站获取信息并发送电子邮件。这个TCP实现设法产生了一对可靠的按顺序排列的字节流（一个从你到服务器，一个从相反方向），尽管底层网络只提供”尽力而为”的数据报。我们的意思是：短数据包，可以丢失、重新排序、改变或重复。你还在一台计算机的内存中自己实现了字节流的抽象。在接下来的四周里，你将实现TCP，在一对被不可靠的数据报网络分开的计算机之间提供字节流的抽象概念。

我为什么要这样做？在不同的不太可靠的服务之上提供一个服务或一个抽象，是网络中许多有趣的问题。在过去的40年里，研究人员和从业人员已经弄清楚了如何在互联网上传递各种东西——消息和电子邮件、超链接文档、搜索引擎、声音和视频、虚拟世界、协作式电子共享、数字货币。TCP自身的作用，即利用不可靠的数据报提供一对可靠的字节流，是这方面的典型例子之一。一个合理的观点认为，TCP 实现算作地球上使用最广泛的非平凡计算机程序。

实验作业将要求你以模块化的方式建立一个TCP实现：

在实验1中，你将实现一个流重组器——一个将字节流的小块（称为子串，或段）按正确顺序组装成连续的字节流的模块。
在实验2中，你将实现TCP中处理入站字节流的部分：TCPReceiver。这需要考虑TCP如何表示每个字节在数据流中的位置，即所谓的序列号。TCPReceiver负责告诉发送方(a)它已经成功地组装了多少入站字节流（这被称为 “确认”）和(b)发送方现在允许再发送多少字节（”流量控制”）。
在实验3中，你将实现TCP中处理出站字节流的部分：TCPSender。当发送方怀疑它所发送的一个段在途中丢失了，并没有到达接收方时，它应该如何反应？它应该在什么时候再次尝试并重新传输一个丢失的段？
在实验4中，你将结合你在前面几个实验中的工作，创建一个工作的TCP实现：一个包含TCPSender和TCPReceiver的TCPConnection。你将用它来与世界各地的真实服务器对话。

2. 开始

你对TCP的实现将使用与你在实验0中使用的相同的Sponge库，并增加了类和测试。

为了开始：

请不要修改libsponge目录顶层以外的任何文件，或者webget.cc。否则，你在合并Lab 1的启动代码时可能会遇到麻烦。
在实验作业的存储库中，运行git fetch来检索实验作业的最新版本。
通过运行git merge origin/lab1-startercode，下载实验1的启动代码。
在build目录中，编译源代码：make(编译时可以运行make -j4以使用四个处理器)。
在build目录外，打开并开始编辑writeups/lab1.md文件。这是你实验报告的模板，将包含在你提交的内容中。

3. 将子字符串按顺序排列

在本实验和下一个实验中，你将实现一个TCP接收器：接收数据报并将其转化为可靠的字节流供用户读取的模块（就像你的webget程序从实验0中的webserver读取字节流一样）。

TCP发送方将其字节流分为短段（每个子串不超过1,460字节），以便它们各自在一个数据报中。但网络可能会对这些数据报进行重新排序，或丢弃它们，或多次传送它们。接收方必须将这些片段重新组合成它们开始时的连续的字节流。

在本实验中，你将编写负责重新组装的数据结构：一个StreamReassembler。它将接收子串（由一串字节和大数据流中该串的第一个字节的索引组成），并提供一个ByteStream，其中所有的数据都被正确排序。

接口如下所示：

// Construct a `StreamReassembler` that will store up to `capacity` bytes.
StreamReassembler(const size_t capacity);

// Receive a substring and write any newly contiguous bytes into the stream.
//
// `data`: the segment
// `index` indicates the index (place in sequence) of the first byte in `data`
// `eof`: the last byte of this segment is the last byte in the entire stream
void push_substring(const string &data, const uint64_t index, const bool eof);

// Access the reassembled byte stream
ByteStream &stream_out();

// The number of bytes in the substrings stored but not yet reassembled
size_t unassembled_bytes() const;

// Is the internal state empty (other than the output stream)?
bool empty() const;

在stream_reassembler.hh头文件中的StreamReassembler类描述了重新组装器的完整（公共）接口。你的任务是实现这个类。你可以向StreamReassembler类添加任何你想要的私有成员和成员函数，但你不能改变它的公共接口。

为什么要这样做？因为它是TCP对网段重排的健壮性的核心，而且它将使处理传入的网段变得更加容易。

3.1 常见问题

整个数据流中第一个字节的索引是什么？零。
我的实现应该有多大的效率？我们还不打算指定一个特定的效率概念，但请不要把这看作是对建立一个空间或时间效率的数据结构的挑战，这个数据结构将是你的TCP实现的基础。
应该如何处理不一致的子串？你可以假设它们不存在。也就是说，你可以假设有一个唯一的底层字节流，而所有的子串都是它的（精确）切片。
我可以使用什么？你可以使用你认为有用的标准库的任何部分。特别是，我们希望你至少要使用一个数据结构。
字节应该什么时候被写入流中？越快越好。一个字节不应该出现在流中的唯一情况是，在它之前有一个字节还没有被”push”出来。
子串可能重叠吗？可以。
我是否需要向StreamReassembler添加私有成员？是的。由于段可能以任何顺序到达，你的数据结构必须”记住”子串，直到它们准备好被放入流中，也就是说，直到它们之前的所有索引都被填充。

4. 开发和调试建议

你可以用make check lab2测试你的代码（编译后）。
请重新阅读Lab 0文档中关于“使用Git”的部分，并记住将代码保存在Git仓库中，它是在master分支上分发的。使用好的提交消息进行小规模的提交，这些消息可以识别更改的内容以及更改的原因。
请努力使你的代码对将对其进行风格评分的CA来说可读。对变量使用合理而清晰的命名规则。使用注释来解释复杂或微妙的代码片段。使用“防御性编程”——明确地检查函数的先决条件或不变量，如果有什么问题，就抛出一个异常。在设计中使用模块化识别常见的抽象和行为，并在可能的情况下将其分解。重复的代码块和庞大的函数将使你很难理解代码。
也请遵守Lab 0文件中描述的 “现代C++”风格。cppreference网站（https://en.cppreference.com）是一个很好的资源，尽管你不需要C++的任何复杂功能来做这些实验。（你有时可能需要使用move()函数来传递一个不能被复制的对象）。
如果你得到一个segmentation fault，那么一定是出了问题！我们希望你的写作风格是使用安全的编程实践，使段故障极不寻常（不使用malloc()，不使用new，不使用指针，在你不确定的地方进行安全检查，抛出异常，等等）。要进行调试，可以使用如下配置构建目录
```
cmake .. -DCMAKE_BUILD_TYPE=RelASa
```
使编译器的“净化器”能够检测内存错误和未定义行为，并在它们发生时给你一个良好的诊断。你也可以使用valgrind工具。你还可以用
```
cmake .. -DCMAKE_BUILD_TYPE=Debug
```
来配置，然后使用GNU调试器（gdb）。

5. 提交

在你的提交中，请只对libsponge顶层的.hh和.cc文件进行修改。在这些文件中，请随意添加必要的私有成员，但请不要改变任何类的公共接口。
在提交任何作业之前，请按顺序运行这些。
- (a) make format（使编码风格正常化）
- (b) make（确保代码可以编译）
- (c) make check_lab1（确保自动测试通过）
在writeups/lab1.md中写一份报告。这个文件应该是一个大约20到50行的文件，每行不超过80个字符，以使其更容易阅读。该报告应包含以下部分。
- (a) 程序结构和设计。描述你的代码中所体现的高层次结构和设计选择。你不需要详细讨论你从启动代码中继承了什么。借此机会突出重要的设计方面，并在这些方面提供更多的细节，以便你的评分助教理解。我们强烈建议你通过使用小标题和提纲，使这篇报告尽可能可读。请不要简单地将你的程序翻译成一段英文。
- (b) 实现方面的挑战。描述你认为最麻烦的代码部分，并解释原因。反思一下你是如何克服这些挑战的，以及是什么帮助你最终理解了给你带来麻烦的概念。你是如何试图确保你的代码维护你的假设、不变量和先决条件的，你在哪些方面发现这很容易或很困难？你是如何调试和测试你的代码的？
- (c) 剩余的错误。尽量指出并解释代码中仍然存在的任何错误（或未处理的边缘情况）。
在你的报告中，请同时填写这项任务花了你多少时间以及任何其他评论。
当准备提交时，请按照https://cs144.github.io/submit。在提交之前，请确保你已经提交了所有你想要的东西。
如果有任何问题，请在周二晚上的实验课上尽快告诉课程组成员，或者在Piazza上发表问题。祝你好运!