上穷碧落下黄泉-源码追踪经验谈(简体中文版,侯捷)

1 / 23 上穷碧落下黄泉-源码追踪经验谈 上穷碧落下黄泉 源码追踪经验谈 作 者：侯捷 整理简化：云开 目录 简化说明 ........................................................................................................................... 2 正文 ................................................................................................................................... 3 读者意见 ........................................................................................................................... 3 个人经验 ........................................................................................................................... 4 动机 ................................................................................................................................... 4 对象 ................................................................................................................................... 5 前提 ................................................................................................................................... 5 书籍 ................................................................................................................................... 6 态度 ................................................................................................................................... 7 工具 ................................................................................................................................... 7 方法 ................................................................................................................................. 13 档案组态 ......................................................................................................................... 13 线头 ................................................................................................................................. 14 笔记 ................................................................................................................................. 15 Design Patterns ............................................................................................................... 19 瓶颈 ................................................................................................................................. 19 价值 ................................................................................................................................. 22 附加价值 ......................................................................................................................... 23 2 / 23 上穷碧落下黄泉-源码追踪经验谈 简化说明 此为为侯捷老师所写，系本人从网络下载所得，原文为繁体字，读起来就像是读英文那 么费劲，本人未经他本人的同意就将其转为简体中文，仅供侯捷老师的大陆粉丝学习之用， 相信侯老师知道后不会怪罪我的（我也是侯老师的粉丝，觉得这篇文章写的实在太好了，非 常有指导意义。所以才想把它转成简体，方便大家阅读 ^_^）。像侯捷老师那样即授人以鱼， 又授人以渔的人，世上已经不多了！ 本文版权归侯捷老师所有，未经侯捷老师许可，不得用于任何商业用途！ 3 / 23 上穷碧落下黄泉-源码追踪经验谈 正文 剖析名家源码，是让自己技术跃升的快捷方式。但是大系统的源码非常庞大 （Unix, Linux,Java, STL, MFC, VCL, Qt...），阅读要有阅读的方法。本文从动机、对象、前提、书籍、态 度、工具、方法、瓶颈、价值、附加价值等方向加以讨论。 读者意见 读者对我的印象，可能很大一部份是我写了本《深入浅出 MFC》，剖析 MFC 的运作机 制并简化模拟了它们。的确，剖析与说理是我擅长的两个项目。偶然的情况下，我起了经验 传承的念头，想写这篇文章，于是在侯捷网站上贴出公告，藉此获知读者希望看到什么。下 面是几封带有具体提议的来信（节录）以及我的简单回复： ● 能不能写出一系列文章？我相信您有非常非常多和好的经验（教训-），若只有一篇短 文，则不解渴。 ● 侯捷：我只打算谈原则、谈基本方法，这不需要一系列文章。 ● (1). 如何开头？从最开始的 .h 文件读起？(2) 怎么做前后连接工作？原码中前 后关系不少，你是怎么做这些工作的？做堆成山的笔记吗？(3) 如果你自己对程序中所用 的算法（algorithms）并不熟悉，怎么突破这个障碍？ ● 侯捷：笔记一定要做，稍后详述。算法若不熟悉，比较困难，唯一的办法是一一拆 解，发挥想象力，设法搞懂它。搞不懂，就是遇上了瓶颈。 ● 我也对如何阅读大系统的源码非常感兴趣，如 Linux, GCC 以及一些开放源码的系统， 所以弟便抓了一套 RedHat 开发的可以阅读大系统源码的软件叫做 Source Navigator，可是 弟并没耐性看完这套软件的 manual，抓回来之后就丢在一边，没有时间钻研如何用它来看 大系统的源码（准备高考当中）。„希望能够看到您出书写到阅读源码相关的心得„ ● 侯捷：有工具帮助是很好，没工具也有没工具的作法。 ● 名家的代码﹐简练﹑优雅﹑富有弹性，对它进行剖析确实能够增长自己的见识﹐提 升自己的功力﹐对于自己的实际工作起到很大的帮助。我觉得应该不仅仅停留在对这种已经 成形的结果（源码本身）的赞叹﹐更应该探讨这种优美设计的进化历程﹐因为这些优美 的源码肯定是经过很多次的 refactoring 得到的。如果仅仅剖析已经存在的优美设计﹐很容 易掩盖怎样进行设计的正确道路﹐可能造成一味的“模仿”﹐过度的 up front design。 ● 侯捷：如果能够反推回当初设计的原貌和演化历程，当然最好。一般人可能没有这 样的功力或时间。我以书写为目的，探究技术的同时，尽可能做到这一点。技术的来龙去脉， 4 / 23 上穷碧落下黄泉-源码追踪经验谈 乃我所谓之技术本质。不过我的设想与实际行动和你上述所言或有差异。 ● D. E. knuth 在《The Art of Computer Programming》提到阅读优秀的源代码一直是被计 算器科学教育所忽略的一个重要方面, Richard Stevens 也在《Unixadvanced programming》一 书封底提到, 他认为学习程序的最好方法就是读程序和写程序。再至 K&R 这样的泰斗，也 都在不同地方强调过阅读程序对于学习程序设计的重要性。„我多么希望先生能就这一主 推向纵深写出一本这方面的专著来„ ● 侯捷：我只谈原则和基本方法，这不构成一本书的份量。 ● 我浏览过 MFC, Linux 源代码，深感剖析名家源码的确是使自己技术跃升的捷径，但 此间有很大的困难，名家源代码一般极其庞大，内容涉及广，很难把握其实质。我认为先要 对所研究的源码有一个高层抽象的把握，就像软件工程的需求分析一样，然后再逐步进入， 一层一层具体化。 ● 侯捷：的确，一定要对研究对象先有高阶理解，不能蒙着头就栽入。 ● STL 中大量的变量声明﹐感觉稀奇古怪﹑密密麻麻﹐阅读实在成问题﹐请问有什么 好的办法呢﹖ ● 侯捷：可能你看的是 Visual C++ 的 STL PJ 版本，那是可读性最差的版本。换读 GCC 附带的 STL SGI 版本会好很多。 个人经验 写这篇文章，我拿什么证明我有足够的经验给你参考？是这样，我个人曾经深入追踪剖 析 MFC 和 STL 源码，并据以写出《深入浅出 MFC》和《STL 源码剖析》两本书。对于 Java 和 Qt 源码也有一点涉猎。Windows 源码虽然没看过（除了「那个人」 ， 谁看过了） ， 但 对 Windows 系统内部的数据结构 （用以管理 memory, processes,modules, threads…）以及 kernel APIs，倒是有几番深刻理解（归功于三本书，稍后详述），亦曾经深刻剖析过 MZ/NE/PE 可执行文件格式，写过一些（自用的）分析工具。 动机 任何事情都讲求动机。动机强则成功率高，动机弱则失败率高。下面几种情况是剖析源 码的可能动机： 1. 像侯捷一样以书写、教育为目的。剖析源码可以带给我许多技术养份，又补充我退 离编程第一线后的实战磨练。属于工作的一部份，和兴趣结合，又能养家餬口，成功率最高， 文件成果最丰硕。 5 / 23 上穷碧落下黄泉-源码追踪经验谈 2. 需要对某些 open source 进行改写以量身订制专用版本。这种情况最常见于 Linux 和 GCC。完全是一种职场工作，压力很大，动机超强，成功率高。但有时间压力，很难完 善其说明文件；往往在项目结束后一段时间内，对如此大规模源码的精神和实际面掌握度渐 次消褪，最后烟消云散，只留下一丝丝模糊概念。 3. 向往华山论剑高手招式，希望学习名家风范，对技术有强烈的追求欲望。完全不是 工作，只是一种学习。积极进取的学生可能是这一类。自由的时间加上学习的天赋使命，使 学生时代成为剖析名家源码的最佳时期，但年轻时期就具备足够基础与心性的人不很多。 4. 工作之外偶而发心 — 毕竟探看核心企求醍醐灌顶是每个科技人心中蜇居的渴 望。由于本职工作的压力，这一类型通常难以持久。 大系统源码都十分庞大，值得剖析（根据我的价值判断）的最小规模，大约是 C++Standard Library。说它最小，你不妨亲自看看有多大（就在你的 C++ 编译程序 的 ”INCLUDE” 目录中）。因此，没有强烈动机和缜密而系统化的措施，很难获得真正有用 的成果。半途而废太可惜了，所以要嘛就下决心做到相当程度，有具体成果才罢手，要嘛干 脆别动，把时间拿去看恐龙展、拿破仑展、三星堆文物展、罗浮名画展，或是和异性朋友培 养感情，更有价值。 对象 取得名家源码的机会很多。open source 不必说了，网络上可以自由下载；其他诸如 classes library, framework„，多半采取白盒策略，也对使用者开放源码（这里所说的开放源 码，和一般所谓的 open source 不同。前者只是将程序以源码型式释出，让使用者得以观 察研究，或修改后用于自家产品。后者允许使用者在某种授权（例如 GPL, General Public License）之下做任意用途。）。许多网络社群组织也大方开放他们的成果。琳琅满目的货架上， 什么才是值得一探的宝贝呢？剖析源码，时间与精力的投注很大，如果抱持「放进篮里都是 菜」的心态，一旦遇人不淑损失可就大了（别说你有的是时间）。 我个人认为，只有价值被百分之百认定的大型卓越作品，才值得剖析它，从中吸取深层 技术养份。一样米还养百样人，哪来被百分百认定的大型卓越作品？唔，我说的是被你百分 百认定，不是被百分之百的人认定。至于你认定错误，所学非人，虚掷岁月，那是你眼力差， 调查不足，怨不得人。 前提 剖析源码，并非学习语言的好方法 — 虽然你或许可以学到很好的语言运用。剖析源 码，也不是初学 OO 的好路线 — 虽然你或许可以学到很好的 OO 概念和实作。要知道， 你现在是单骑入风尘，飘飘无所依，迎面扑来的是成千上万如蝗虫如夏蚊的程序代码。剖析 一样东西，必须先对它有一定程度的了解。假设你想剖析 MFC，为什么会有这样的念头？ 6 / 23 上穷碧落下黄泉-源码追踪经验谈 因为你想彻底了解并掌握 MFC 的运行，这种需求一定是因为你想以 MFC 为基础开发应用 程序。那么，不先写几个 MFC 应用程序触发一点感觉，不宜贸贸然进入丛林深处 — 那 儿有很多沼泽和蚊蚋。 相同道理，阅读 Qt 源码之前，请先写点 Qt 程序；阅读 STL 源码之前，请先学会使 用 STL 并对 GP/template 有相当认识；阅读 Java 源码之前，请先学会撰写 Java 程序并对 OO 有相当体会；阅读 Linux 源码之前，请先在 Linux 系统中玩一阵子并对内存管理、分 离地址空间、档案管理、驱动程序等系统知识有点准备。阅读任何窗口系统上的任何 application framework，请先对该系统的讯息驱动机制做相当程度的了解。 书籍 永远不要抱持「一切从轮子造起」的想法。舍弃别人的成果不用，走别人走过的路，犯 别人犯过的错，智者不为。 名家源码剖析心得这一类书籍，属于小众市场，得遇一本应该感天谢地。你要的书到底 存不存在，自己得仔细做点功课。当然，书写得好不好，也得你自己仔细做点功课。 www.amazon.com 是最好的书籍搜寻网站，打几个关键词进去，用心链结浏览一下，花不了 一个半天。MFC 方面，《MFC Internals》、《深入浅出 MFC》都是首选，STL 有《STL 源码剖析》、 《The C++ Standard Template Library》，Linux 方面可多了，蔚为大观，绝对不愁找不到。想对 Windows 操作系统有深刻认识，应该看《Undocumented Windows》、《Windows Internals》、 《Windows 95 SystemProgramming SECRETs》（先前我曾说，我个人对 Windows 操作系统的 内部结构有相当了解，便是得力于这三本书。非常非常棒的三本书 — 即使它们的出版年 份分别是 1992,1993,1995，即使今天 Windows 操作系统已是 XP 当道。），印象中还有一本 教你动手实现一个 Win32 操作系统的书 。想看 GCC 源码， 应该先拿编译程序原理垫垫底 ， 7 / 23 上穷碧落下黄泉-源码追踪经验谈 再找本 《Building Your Own Compilerwith C++》 或 《Crafting a Compiler with C》 ，能够看 看 《How Debuggers Work》 、 《Linkers& Loaders》当然更好。 态度 真的，剖析源码是一件大而艰巨的工程。心理素质不好的人，不要尝试。想象这样的情 境：「我走在广袤的热带雨林中，浓密的树冠连一丝阳光也透不进来。到处是黝黑的沼泽； 蛇虺魍魉，蛊毒瘴疠。扑面而来尽是蚊蚋，群响如雷。硕大的苍蝇毫无畏惧地在我脸上停留、 舔舐我的脸孔并清理它们的腿毛。我想找一只魔戒，传说中载上了它就拥有超人一等的力量， 足以慑服众生。但我不知道它在哪里，连它的长像都不知道。每个疲惫不堪的夜晚，我梦见 坠入暗无天日的泥淖，手忙脚乱地寻找一只针。呃，是的，一只绣花针。极度疲倦中我入睡， 极度无依中我醒来。日复一日。前面有三百六十五里路。每天都像行程伊始。听说森林里到 处都是像我一样的人„的骨骸。」 语出何处？哦，是我的即兴之作，博君一哂。没有坚强信念，你走不出黑色森林。没有 适当的工具和方法，你也别想大海捞针。 工具 下面是我用过的工具。由于我的最多经验都在 MS Windows 环境下，剖析对象也都是 Windows 环境下的大型源码，所以我所列的工具也就有某种局限。然而任何人应该能够从 这里面得到一些灵感。 1. grep 剖析 MFC 和 STL 源码时，除了一般文本编辑器（我用老古董 PE2），我只使用一个工 具：grep，这是源自 UNIX 的一个小小公用程序（utility），可以在一大堆档案中找出某个字 符串的出现点。例如，我知道，任何 Windows 程序不可能没有 WinMain()，而 MFC 应用 程序中没有它的踪影，因此我判断一定被 MFC 包装起来了。于是我想在茫茫大海中寻找 WinMain 落于何处，如图 1。画面第一行显示我的动作是： grep WinMain *.cpp grep 为我找出 6 个出现有 WinMain 字样的档案，并列出每一个出现点的整行文字。 从中我筛选出 APPMODUL.CPP 和 WINMAIN.CPP 做为下一个观察目标。这样我便有了很好 的线索。如果希望搜寻目标扩及子目录，grep 也办得到，如图 2，采用选项 “-d”。 我手上这个 grep.exe 是 Borland 编译程序提供的版本。如果你没有，可以到 http://unxutils.sourceforge.net/ 下载一个同类工具（感谢 william 告诉我）。 8 / 23 上穷碧落下黄泉-源码追踪经验谈 图 1. 以 grep 搜寻特定字符串 图 2. 我手上的 grep 的全部功能选项。这是 Borland 编译程序提供的版本。 2. windiff 拿到 MFC7 源码的那一天，我便立刻以 windiff 观察两个版本的差异。Windiff 是 VC 内 附的小工具，方便观察两个档案的差异，包括新增内容、删减内容、修改内容等等，如图 3。 被观察的两个档案内容置于同一个大窗口中，共同内容以白底黑字表现，红色区域为第一档 9 / 23 上穷碧落下黄泉-源码追踪经验谈 案之独特内容，黄色区域为第二档案之独特内容。左边小窗口列出两个档案内容相异区域的 映像图，方便你掌握全局；蓝点表示目前大窗口所观察的区域在整个档案的座落位置。其他 标示及功能此处就不介绍了。利用这个工具，我轻易实证先前听说的「MFC7 加强 Type-safe Message Maps」的实际作法：以相对安全的 static_cast<> 取代霸道的 C-style 强制转型（如 图 3 所示）。 图 3. windiff 可以让使用者很方便地观察两个档案之间的差异。 3. IDE debugger 做为技术文本书写者，我一向不喜欢使用比读者先进太多的工具。我喜欢鹤嘴锄、丁字 镐、畚箕扁担，因为我的读者可能买不起昂贵的空压机、怪手、楼兰大吊车。如果我告诉读 者我以 BoundsChecker 或 SoftICE 观察到某处有一块内存泄漏，某处造成缓存器内容诡异， 而我的读者只能看着上述两个高贵的名称干瞪眼，这有什么意思？ 不过，研究 MFC 而计算机内没有安装 VC++，实在是怪事一桩。VC++ 内建有除错器， 不好好利用就未免暴殄天物。剖析各种大型 libraries，你应该善用各种整合开发环境（IDE） 中的除错器，善用其 Breakpoint, Step Into, Step Over, Step Out 功能、善用其 CallStack 窗口 和各种 Debug 窗口，如图 4。这些功能让你得以把程序的执行冻结放慢到一次一个指令， 并在任何时刻观察任何变量的现值及函数的呼叫顺序。所谓「玩弄于股掌之间」差不多也就 这样子了。这些功能非 VC 独有，每一种编译程序上的专业除错器都有。 我模拟 MFC 做出 MFCLite3，撰写过程中曾经遇到极隐微的臭虫，如果不是除错器的 帮忙，协助我了解 MFCLite3 和 MFC 之间的差异，单只使用鹤嘴锄丁字镐和畚箕扁担，我 10 / 23 上穷碧落下黄泉-源码追踪经验谈 不敢想象需要花费多少额外的时间和精力。 图 4. VC 除错器。左中窗口可观察 classes, files, resources，右中窗口可观察源码，右 下角是 CallStack 窗口，左下角是 Watch 窗口（可观察任何一个你设定的变量），下方正中 央是目前执行脉络下的局部变量窗口。将游标移至源码窗口内的任何变量名称上，其身旁便 会出现现值，以小黄标签框住。红点表示中断点，执行至中断点后可选择单步前进、进入函 数、退出函数„等执行方式。每个窗口都可以随意摆放，所以你的 VC 画面可能和本图不 尽相同。所有这些功能并非 VC 独有，每一种专业除错器都有这些功能。 4. Spy++ 观察任何 Windows libraries，少不了需要 SPY++ 的帮忙。举个例子，当我撰写 MFCLite3 窗口/文件关闭系统时，我从 MFC 源码中观察到它处理了 WM_CLOSE 和 WM_DESTROY 和 WM_NCDESTROY，而我的 SDK 知识告诉我程序结束时还会发出 WM_QUIT。MFC 的某些处 理方式（例如 MDI 窗口管理和 ::PostMessage()同步行为）大大超出了 MFCLite3 的设定目 标，因此我必须做些简化，绕个弯在尽量逼真的前提下模拟 MFC 行为。首先我得确定窗口 /文件关闭系统的所有相关讯息，这时候就用上了 SPY++。 SPY++ 是 VC 内附的一个工具，可以侦测四种东西： (1) Messages, (2) Windows, (3)Processes, (4) Threads，执行画面如图 5。 11 / 23 上穷碧落下黄泉-源码追踪经验谈 图 5. SPY++ 执行画面。四个子窗口分别展现 SPY++ 所能侦测的四种东西： (1)Messages, (2) Windows, (3) Processes, (4) Threads。 5. TDump TDump 是 Borland 编译程序内附的一个工具，可用来观察 MZ(DOS), NE(Win16),LE(VxD), PE(Win32), OMF(.OBJ & .LIB) 等文件格式，如图 6。我在剖析 Windows 可执行文件格式时， 曾大量倚重它来比对《Windows 95 System Programming SECRETs》第 8 章所示的数据结构。 同类工具还有 VC 所附的 DUMPBIN.EXE 和 Matt Pietrek 所写的 PEDUMP.EXE。 TDUMP 另有一个上述其他工具没有的特性：可以倾印（dump）二进位档内容。 追踪 MFC 源码和撰写 MFCLite3 时，我拿它来观察文件格式，如图 7。 12 / 23 上穷碧落下黄泉-源码追踪经验谈 图 6 以 TDUMP 观察 Win32 程序（PE 格式） 图 7. 以 TDUMP 倾印（dump）二进位档案内容。 6. Source Navigator 本文一开始，读者来函中曾经提到 Source Navigator。我没有用过这个工具，所以上网 下载了一份试试。这个工具相当庞大，我还没有足够的动机去研究它。不过从其执行画面（图 13 / 23 上穷碧落下黄泉-源码追踪经验谈 8）及菜单单观之，大概是用来追踪分析 C++ class library。如果真是这样，我想编译程序所 附的除错器可以完全取代之。 图 8. Source Navigator 的执行画面。 方法 万事俱备，东风也有了，动手吧。首先你应该认识剖析对象的档案组态。 档案组态 到底你观察的对象有哪些档案，置于何处，首先你要掌握好。Java 程序源码只有 .java 一种型态，C++ 程序源码有实作档（通常扩展名为 .CPP）和表头档（通常扩展名为 .H，或 者无扩展名）两种，分放不同的磁盘目录内。 不同的系统，对于档案命名肯定都有某种。阅读源码的过程中，对此必须留心记一 记。以 MFC 为例，所有主轴核心类别的宣告放在 afxwin.h，讯息映像过程所需的讯息处理 宏定义于 afxmsg_.h；xxxCore.cpp 内含类别核心定义，例如 appcore.cpp （CWinApp） , wincore.cpp （CWnd） , doccore.cpp （CDocument） , viewcore.cpp（CView） 。Winxxx.cpp 代表 CWnd 衍生类别的定义 ，例如 winfrm.cpp （ CFrameWnd ） ,winmdi.cpp （ CMDIFrameWnd,CMDIChildWnd）„。 DocXxx.cpp 表示 document 相关类别，例如 DocTempl.cpp （ CDocTemplate ） , DocMgr.cpp （ CDocManager ） ,DocSingl.cpp （CSingleDocTemplate）, DocMulti.cpp（CMultiDocTemplate）。这些档名或许一回生二回熟， 但最好你能够做做笔记，用点心思强记下来。掌握档案的命名哲学，对你顺利追踪源码很有 帮助。 14 / 23 上穷碧落下黄泉-源码追踪经验谈 阅读源码的过程中会涌现大量的变量名称、函数名称。它们也都有某种命名规则。这个 也必须用点心思归类整理记录下来。例如 MFC classes 的成员函数中有 On 开头、Do 开头、 Pre 开头、Post 开头、Get 开头、Set 开头、Open 开头、Load 开头、Create 开头„等各 种名称，掌握它们的命名规则能使你阅读时印象加深，事半功倍。 为了熟悉档案组态，也为了方便观察，请熟用任何一个令你舒服的文本文件快速浏览工 具。图 9 是我惯使的 FileCtrl.com，一个老掉牙的 DOS 小程序（你看它还是 .COM 呢） ， 在 MS-DOS 窗口中跑得很好。只要以光棒选择左窗口的文件名，右窗口立刻显现内容，反 应极快，操作简单，执行档小到不行，才 8,466 bytes。把它放在 PATH 所指目录中，便可 以在任何时刻任何地点调用它。 图 9. FileCtrl，一个小工具，可方便而快速地观察档案内容。 线头 剖析源码，像玩拼图游戏。你一定先拼四个角落，是吧。线头找到，抽丝剥茧就很容易。 线头在哪里？考验你的基础知识。例如先前我所说，Windows 程序必定以 WinMain()为程 序进入点（entry point），当我找到其源码所在，循序追踪，至少就可以挖掘出 application framework 的一条重要主干 （其他诸如 msg mapping, msgrouting, document/view„还得另起 炉灶）。再以 MFC msg mapping 为例，我从来不曾在其他 C++ 程序 中 看过 DECLARE_MESSAGE_MAP()和 BEGIN_MESSAGE_MAP(),END_MESSAGE_MAP() 这种东西，用 grep 工具一找，找出其源码，发现都是 macros，于是我就老老实实把这些 macros 的定义 代入随便一个测试用的 class 内外（或利用 VC 编译程序选项 –FI 直接取得代入结果）， 老老实实观察程序代码的变化，再把这些 macros 所构筑出来的数据结构画出，轻易就破解 15 / 23 上穷碧落下黄泉-源码追踪经验谈 了法老王密码。虽然隐微的 AfxSig_xxx 还有待理解（从历史上看，罗塞达石碑也是很晚才发 现-），但我已能大略掌握整个设计精神。MFC 的三层基础设施（Dynamic/DynCreate/Serial） 也是这样破解的。这些方法笨吗？我做这些事情的时候（1994），世上没有任何一本书一篇 文章能够引导我，我的办法是唯一的办法，不笨。 诸如 MFC 这样的框架系统，组织庞大线头纷歧。STL 就单纯许多。STL 有六大组件， 你可以任选一种开始。一般人应该会从容器开始，尤其是最简单的 vector，毕竟它只是动 态 array，而 array 是大家耳熟能详的结构。但是当你进入 vector 的源码一看，乖乖，内 存动态配置是以 STL allocator 为之，与 STL algorithm 之间的桥梁则是透过 STL iterators。这 时候你可以选择先跳开研究后两者，或是抱持「反正是那么一种东西，有那么一种功能」的 心情，先解决 vector 再说。在此我可以告诉各位，破解 STL 实作奥秘的最大关键在 iterator traits 身上，因为它不但观念新颖， 实作手法也新颖 （对大部份 C++ 程序员而言） 。 另 一关键是 function adaptors，同样因为观念新颖，实作手法新颖。至于 containers 和 algorithms，教科书上都找得到它们的详尽说明，狠狠给它流点汗，不可能没有收获。 面对操作系统，线头又在哪里？经验告诉我应该在数据结构；可执行文件格式尤其关键。 连 Windows 动态联结的奥秘都藏在可执行文件格式中呢（见 PE 格式中的 .edata 和 .idata 两个 sections；’e’ 代表 export，’i’ 代表 import）。如果你手上有源码，那 么系统的数据结构的呈现很具体，明明白白就写在表头档内；（广义的）算法比较没那么实 象，万一缺乏良好批注，你只得一步一步追踪推演。然而，（广义的）算法离不开数据结构， 掌握了数据结构，你就有所依恃。稍后「瓶颈」一段我另有说明。 除了以上所说，另有一些难以言传的东西，一问一答的方式或许更能传承。面对陌生架 构，不同的人有不同的组织手法和观察焦点，一开始跌跌撞撞都是难免。大势逐渐明朗后， 两岸猿声啼不住，轻舟已过万重山。 笔记 大系统源码都很庞大很复杂。如果你以为你可以像看电视连续剧一样地每天边啜咖啡边 摇头晃脑地轻松自在看看，一旁音乐零嘴侍候，时而还要应付小家伙的捣蛋或大家伙的唠叨， 还可以一心二用做点旁务，我告诉你，别作梦了。面对这一大坨代码，不论时刻长短，你必 须战战兢兢心无旁骛，像准备大学联考一样专心；灵光乍现、心得偶拾之际，立刻做笔记。 笔记做在计算机上最好。 请熟用一个文字输入工具，一个绘图工具。请加快你的打字速度。多快？不会影响你的 书写速度就行。图 10 是我追踪 MFC 窗口/文件关闭系统的过程中，以 PowerPoint 画下的 图，这样的图我在追踪过程中产出不下数百张。图 11 是我追踪 STL RB-tree（红黑树）的过 程中，以 PowerPoint 画下的图，这样的图也不下百张。有了它们，配合少量文字，我可 以自信满满地说，20 年内，任何时候你问我关于这个系统，我可以复习一个小时后便回答 得头头是道。超过 20 年我满 60 岁，万一得阿兹海默症（老人痴呆啦）可就抱歉啦。 16 / 23 上穷碧落下黄泉-源码追踪经验谈 分析与记录方式要 — OO 这东西老实说复杂得很。CASE tool（如 RationalRose） 很昂贵，我不能冀望买了「保时捷」才上路，但至少 UML（Unified ModelingLanguage）的 各种 ”diagrams” 要啃一啃，要学着用用。图 12 是我剖析 MFC 及撰写 MFCLite3 的过程 中，手工绘制的 UML class diagram。嗯，富人有富人的办法，穷人有穷人的对策。 我的成果可用于书写与出版，当然我写字画图起来就格外带劲儿。你的情况不同，不必 像我一样画得那么精美漂亮。我要强调的是，你得勤做笔记，份量要足，不能偷懒。曾经走 过的路，再走一遍真令人不耐，曾经理解的知识，重新推演一遍真令人懊恼。 图 10. 追踪 MFC 的窗口-文件关闭系统时，我以 PowerPoint 画下的图。 17 / 23 上穷碧落下黄泉-源码追踪经验谈 图 11. 追踪 STL RB-tree（红黑树）源码时，我以 PowerPoint 画下的图。 18 / 23 上穷碧落下黄泉-源码追踪经验谈 图 12. 追踪 MFC 及撰写 MFCLite3 时 ，我以 PowerPoint 画下的 UML class diagram。 19 / 23 上穷碧落下黄泉-源码追踪经验谈 Design Patterns 先有鸡还是先有蛋？一，二，三，请回答。 答不出来是吧。 先有 design 还是先有 design patters？ 在自然演化的世界中，当然是先有 design 才有 patterns。后者是前者的淬炼与分类。 但我们希望予程序员以训练，让他们在还未能完成那么多设计之前，先获得前人的加持灌顶。 如果他们心中有了 design patterns，他们就可以在适当时机运用前人的经验完成最理想（或 足够理想）的设计。 源码追踪和 design patterns 关系几何？是否一定先要熟透那些名闻遐迩的 designpatterns，追踪与剖析才有依据？不，具备 design patterns 知识，你在分析源码时感 触会更敏锐，文字说明或总结时可以更言简意赅，但即使不知道 design patterns 也不会影 响你的追踪与学习。《深入浅出 MFC》2e,p82（这里说的是繁体版页次。简体版出现于 p68 中央和 p69 最下。）最后一行说：『我要在这里说明虚拟函数另一个极重要的行为模式』， p84 第二段第一行说：『这种行为模式非常频繁地出现在 application framework 身上』。1996 年我写下上述文字时，并不知道它就是如今大名鼎鼎的 Template Method（详见《Design Patterns》by Gamma, etc. 1995, Addison Wesley。”Define the skeleton of analgorithm in an operation, deferring some steps to subclasses. Template Method letssubclasses redefine certain steps of an algorithms without changing the algorithm’sstructure.”）。但这不影响我的认识和我 的体会。当然，如果当初我就读过 GOF 的名著，可能对我的剖析和书写更有帮助。 瓶颈 当你的知识水平和你所阅读的对象差距太远，你也只好暂时放下，补齐必要的基础。举 个例子，当你追踪 STL 的 allocator，研究它的内存配置策略时，如果不知道什么是 memory pool，源码又无法让你参悟，你只好先去了解 memory pool 是何方神圣。如果你不知道什 么是 Red Black tree，你也绝不可能剖析 STL 的 map 和 set 两种容器，因为它们的底层机 制都是 Red Black tree。不了解 Hash table？先去看看数据结构教科书；不解 QuickSort 和 Insertion Sort？先去看看算法教科书。 没有哪份名家源码是易与之辈。它们都是大系统，包罗万象。面对操作系统源码或编译 程序源码，需要的基础知识就更多更底层更艰涩了。中断、迂回、定点攻坚是你常遇到的情 况和必要措施，颓丧和兴奋是你情绪轮回。每一项知识都有其基础知识，每一项基础知识又 有其更基础知识。一再地中断、转换、挫折，难以行云流水，大概是源码追踪工程的最大失 败潜因。 20 / 23 上穷碧落下黄泉-源码追踪经验谈 先前读者来信问到，如果对程序所用的算法不熟悉，怎么突破障碍？我必得告诉你，你 只好以修复古迹的态度，一砖一瓦重建整个脉络。然而经验告诉我，演算法和数据结构脱不 了干系，把数据结构摸清楚，再耐心地步进追踪，终有水落石出的一天。剖析 STL deque 时 我有类似经验。我对 deque 实作技术的唯一理解是，一个分段连续空间。Deque 的实作码 相较于其他序列式容器如 vector, list 庞大很多，但当我耐心地把 class deque 中的所有 data member 画出来，如图 13，再实际放些元素进去（特别注意边界状态），我就可以轻松 观察数据结构的内容变化。有了这些认识，再搭配 deque member functions 源码，疑惑迎 刃而解。 图 14 是我的另一个经验。我从 SGI STL allocator 的源码变量名称中隐约知道它实作有 memory pool，同样地我把数据结构画出来，塞几个元素进去，观察内容的变化和指标的移 动，疑惑迎刃而解。 图 13. SGI STL deque 的实作手法。 21 / 23 上穷碧落下黄泉-源码追踪经验谈 图 14. SGI STL allocator 所实作的 16 个 memory pool ， 分别应付 8, 16, 24, 32, „128 bytes 的小块内存索求。 当然也有些情况非常复杂，不那么容易对付。奉劝一句，不要硬钻牛角尖！就算不是牛 角尖，也不能硬钻。不懂还是不懂，硬钻也是不懂，那就放下吧（还能怎样）。幸运的话， 在偶然的时机里，也许贵人相助，也许心有灵犀，也许触类旁通，你就手到擒来得之不费功 夫了。 我有一个切身实例。1997 年我完成《深入浅出 MFC》，其中第八章剖析 document 档案 结构，当时我已经搞清楚 Serialization 的来龙去脉，也可以解释许多 document 的二进位内 容，但对于为什么有些 tag 是 8001，有些 tag 是 8003，我不了解。当时我认为我已经达 到了我设定的目标，对于更进一步剖析已无兴趣（没兴趣和遇上不易突破的障碍多少有点因 果循环），而且我认为《深入浅出 MFC》的读者最终目标是要撰写 MFC 应用程序，未能把 属于极内部机制的 tag 编码（encode）方式搞清楚，无关宏旨 — 甚至连理解 document 存 档格式在我认为都已是「一窥天机了」。 一晃就是五年，直到最近我开始撰写《多型与虚拟》2e 第六章的 MFCLite3 — 一个 模拟 MFC 的轻量级文本模式 application framework。由于我对上述主题的认识只及某个层 次，与真正的 MFC 还有段距离，造成 MFCLite3 在某种情况下出错。甫自浙江大学电子系 毕业的肖翔先生来信给了我一份错误（全文见侯捷网站「汗如雨下」），以下为来函摘要： 22 / 23 上穷碧落下黄泉-源码追踪经验谈 „ psqr1 和 psqr2 指向同一对象﹐写入文件时应该只有一份﹐但是在您的实现中却 写了两次﹗导致读出时﹐psqr1 和 psqr2 指向了不同的对象。显然这是不正确的。我觉得 对于 C++ 对象持久性而言﹐最重要的问题﹕一个是如何保存相关的类信息﹐另一个就是 如何解决上述问题﹗在您的两本着作《多形与虚拟》﹑《深入浅出 MFC》中对前者都有很 精辟的论述﹐唯独后者一点也没有提及﹐不能不说是一个很大的瑕疵。对于如何解决这个问 题也不是很困难﹐只要先实现 CMapPtrToPtr 和 CPtrArray﹐在写入时先查 map 如果已写 过﹐就只把输出序号写入文件﹐如果没有就把对象的地址和输出序号插入 map﹐再把数据 写入文件。读出时﹐遇到第二种情况（即文件中有实际数据，而非只是序号）﹐就先创建一 个对象把数据读出﹐接着再把新建对象的地址加到数组 array 尾端﹐遇到第一种情况﹐就 以输出序号为索引直接从数组中得到对象（由于写入和读出的顺序一样﹐仅用输出序号就可 以完全解决问题）。 ※原函之大陆术语，对台湾读者十分陌生。以下修改为台湾术语以利台湾读者阅读。谨 此。 „ psqr1 和 psqr2 指向同一对象﹐写入文件时应该只有一份﹐但是在您的实作中却 写了两次﹗导致读出时﹐psqr1 和 psqr2 指向了不同的物件。显然这是不正确的。我觉得 对于 C++ 对象永续性而言﹐最重要的问题﹕一个是如何保存相关的类别资讯﹐另一个就是 如何解决上述问题﹗在您的两本着作《多形与虚拟》﹑《深入浅出 MFC》中对前者都有很 精辟的论述﹐唯独后者一点也没有提及﹐不能不说是一个很大的瑕疵。对于如何解决这个问 题也不是很困难﹐只要先实现 CMapPtrToPtr 和 CPtrArray﹐在写入时先查 map 如果已写 过﹐就只把输出序号写入文件﹐如果没有就把对象的地址和输出序号插入 map﹐再把数据 写入文件。读出时﹐遇到第二种情况（即文件中有实际数据，而非只是序号）﹐就先产生一 个对象把数据读出﹐接着再把新建对象的地址加到数组 array 尾端﹐遇到第一种情况﹐就 以输出序号为索引直接从数组中得到对象（由于写入和读出的顺序一样﹐仅用输出序号就可 以完全解决问题）。 一看这几句话，我就知道它的价值。高手过招需要真正发力吗？比个招式就够了。这些 提示有如醍醐灌顶，我的兴奋难以言传。这些年来我对 STL 有了很多认识，所以我以 std::map 取代 CMapPtrToPtr，以 std::vector 取代 CPtrArray，快速而成功地模拟出完完整整 的 MFC document 精确文件格式。这是我写作生涯以来和读者互动的一个最精彩实例。 价值 源码之前，了无秘密！ 阅读源码，犹如私淑大师仪采，亲炙大师风范。大师往前一站，渊停岳峙，大师往后一 23 / 23 上穷碧落下黄泉-源码追踪经验谈 退，潇洒从容。谁不向往做大师人物？看多了大师身手，举手投足自然也就有了样子。 追踪名家源码，历经震撼与洗礼，你将有如脱胎换骨。说白一点，个人谈吐思想眼界的 档次都会高出不少，当然前提是你受教。 常有人询问，编程需要天赋吗？哦，任何事情走往极致，都需要天赋。任何一个软件产 品的极致成功，都需要创意天赋、编程天赋、管理天赋、营销天赋„。然而，只需用心模仿， 再加一点匠心独具，任何人都能够把编程路走得稳当顺遂。能读千赋则善赋，能观千剑则 晓剑，巧者不过习者之门也。你把名家源码融为己用，别人也会赞叹一声『你有编程天赋』。 我个人认为，剖析大系统源码的最大价值不在于编程技术上的小枝小节，而在于宏观视 野与大格局的陶养。看过 MFC 源码、STL 源码、Windows 内核结构和 kernel APIs 假码 （pseudo code）（Windows 源码并未开放。这些都是 Andrew Schulman 和 Matt Pietrek 的 劳动成果，载于 《Undocumented Windows》 、 《Windows Internals》 、 《Windows 95 System Programming SECRETs》三本书中。我站在他们的肩膀上。），使我对于 Large Scale Object Oriented System、ApplicationFramework、Generic Programming、Operating System kernel 成 竹在胸，从容自在。我虽没有开发类似产品（我比较喜欢大刀阔斧修剪一番，写些 “lite” 版 本，如 MFCLite, STLLite，做为教育之用。），但胸中丘壑已成，自有一番风景。 附加价值 计算器前辈大师们开放源码，山高水长，典范长存。这些大系统源码固然是宝，对一般 人而言犹如天际明星，只能瞻仰。若有智慧言语，引领众人认识这些宝贝，不啻亦如宝贝。 千辛万苦窥探这些宝藏并获得了具体成果，你会不会希望让别人也分享你的成果和喜悦？ 怀宝迷世，圣人不许，相信 100% 的人都愿意分享。把你的心得整理出版，立言立功，不 但为后学铺路，对自己也有省思反刍的技术效益和版税的经济价值。 不过，自己理解是一回事，让别人理解又是一回事。思想是