什么是 ‘Clang Tidy’ 的自定义检查器？如何利用 AST（抽象语法树）强制执行大厂内部的代码规范？

各位编程专家、架构师和质量守护者们，大家下午好！

今天，我们将深入探讨一个在大型C++项目开发中至关重要的话题：如何利用现代工具，特别是Clang Tidy及其自定义检查器，来强制执行我们内部的代码规范。在大型企业中，代码规范不仅仅是风格问题，它直接关系到代码的可读性、可维护性、团队协作效率，乃至最终产品的稳定性和安全性。

一、 大厂代码规范的痛点与自动化检查的必要性

在任何一家拥有庞大代码库和众多开发人员的大型科技公司里，代码规范的统一性是项目成功的基石之一。设想一下，一个项目由数百名工程师共同维护，如果每个人都按照自己的习惯编写代码，那么：

• 代码可读性将急剧下降： 新成员融入项目会变得异常艰难，即使是经验丰富的开发者也需要花费大量时间去理解不同风格的代码。
• 维护成本飙升： 修改或调试他人代码时，不一致的风格会增加认知负担，引入潜在错误。
• 团队协作效率低下： 代码评审时，风格问题往往会占据大量讨论，分散对核心逻辑的关注。
• 潜在缺陷难以发现： 某些规范（例如资源管理、并发安全）直接关系到代码的质量和健壮性，手动检查极易遗漏。

传统上，我们依赖于代码评审来发现并纠正不符合规范的代码。然而，随着代码量的爆炸式增长和迭代速度的加快，纯粹的人工评审变得越来越低效和不切实际。评审者往往会疲于应对海量的风格问题，而无法将精力集中在架构设计和业务逻辑的正确性上。

这就是自动化代码检查工具的用武之地。它们可以作为第一道防线，在代码进入评审流程之前，就自动识别并指出不符合规范的地方，甚至在某些情况下提供自动修复建议。这不仅极大地提高了效率，也确保了规范执行的一致性和彻底性。

在众多C++静态分析工具中，Clang Tidy凭借其对Clang编译器的深度集成、高度可扩展性以及对抽象语法树（AST）的强大利用能力，成为了强制执行复杂代码规范的理想选择。

二、 Clang Tidy：基于Clang AST的智能代码卫士

2.1 什么是Clang Tidy？

Clang Tidy是一个基于Clang的静态分析工具。它是LLVM项目的一部分，利用了Clang强大的C++前端，能够对C、C++和Objective-C代码进行深入的语义分析。与那些基于正则表达式或者简单文本匹配的工具不同，Clang Tidy能够理解代码的真正含义，而不仅仅是其表面的文本形式。

它的核心功能包括：

• 内置检查器： Clang Tidy自带了数百个检查器，涵盖了代码风格、潜在Bug、性能优化、现代C++用法等方面（例如 modernize-use-override, readability-else-after-return, cert-* 等）。
• 自动修复能力： 许多检查器不仅能报告问题，还能提供自动修复建议，并能通过 -fix 选项直接修改代码。
• 高度可配置： 可以通过 .clang-tidy 配置文件精细控制哪些检查器启用、哪些禁用，以及它们的具体行为。
• 可扩展性： 允许开发者编写自己的自定义检查器，以满足特定的项目或公司规范。这正是我们今天讲座的重点。

2.2 为什么选择Clang Tidy？

下表对比了Clang Tidy与传统基于正则表达式的工具的优势：

特性	基于正则表达式的工具（例如grep、sed）	Clang Tidy（基于AST）
理解层次	文本匹配	语义理解（变量、类型、作用域、继承关系等）
误报/漏报	容易产生大量误报和漏报	准确性更高，误报和漏报相对较少
复杂规范	难以处理涉及语义的复杂规范	能够处理复杂的语义规范
自动修复	困难，容易引入新的错误	提供相对安全的自动修复
开发难度	相对简单	需要了解Clang AST和C++编程
维护成本	规则脆弱，代码重构后易失效	规则更健壮，对代码重构有更好的适应性

Clang Tidy之所以能做到这些，关键在于它深度利用了Clang编译器生成的抽象语法树（AST）。

三、 抽象语法树（AST）：代码的骨架

要编写高效且准确的自定义Clang Tidy检查器，我们必须对AST有深入的理解。AST是源代码结构的一种抽象表示，它移除了源代码中不重要的细节（如括号、分号等），只保留了程序的结构和内容。

3.1 AST是什么？

当Clang编译器处理源代码时，它会经历以下几个阶段：

1. 词法分析 (Lexical Analysis)： 将源代码分解成一系列的词法单元（Token），例如关键字、标识符、运算符、字面量等。
2. 语法分析 (Syntactic Analysis)： 根据语言的语法规则，将词法单元流组织成一个树形结构，这就是抽象语法树（AST）。
3. 语义分析 (Semantic Analysis)： 在AST上进行类型检查、符号解析等，确保代码的逻辑正确性。

AST的每个节点都代表了源代码中的一个构造，例如一个声明、一个语句、一个表达式或一个类型。通过遍历和分析这些节点，我们可以获取到源代码的结构、类型信息、作用域等所有编译时可用的信息。

例如，对于C++代码片段 int x = 1 + 2;，其简化的AST结构可能如下：

-DeclStmt
  -VarDecl 'x' 'int'
    -IntegerLiteral '1'
    -IntegerLiteral '2'
    -BinaryOperator '+' 'int'
      -ImplicitCastExpr 'int'
        -DeclRefExpr 'x' 'int'

这展示了变量 x 的声明（VarDecl），以及它被初始化为一个加法表达式（BinaryOperator），加法表达式的左右操作数是两个整数常量（IntegerLiteral）。

3.2 探索AST：clang-query

clang-query 是一个非常有用的工具，可以帮助我们交互式地探索C++代码的AST。它允许我们输入AST匹配器表达式，然后显示匹配到的节点及其周围的AST结构。

假设我们有一个文件 example.cpp：

// example.cpp
class MyClass {
public:
    void doSomething() {
        int value = 10;
        if (value > 5) {
            // ...
        }
    }
};

void globalFunction() {
    // ...
}

我们可以这样使用 clang-query：

clang-query example.cpp -- -std=c++17

进入 clang-query 提示符后，我们可以尝试不同的匹配器：

• 查找所有类声明：

  match cxxRecordDecl()

  这会匹配到 MyClass。

• 查找所有函数声明：

  match functionDecl()

  这会匹配到 doSomething 和 globalFunction。

• 查找所有变量声明：

  match varDecl()

  这会匹配到 value。

• 查找所有if语句：

  match ifStmt()

  这会匹配到 if (value > 5) 语句。

clang-query 是开发自定义检查器时不可或缺的调试工具，它可以帮助我们快速验证AST匹配器是否能正确识别目标代码结构。

3.3 AST遍历与匹配：RecursiveASTVisitor 和 ASTMatchers

在Clang Tidy中，我们主要有两种方式来遍历和匹配AST节点：

1. clang::RecursiveASTVisitor： 这是一个基类，允许我们通过重载其 Visit 方法来手动遍历AST的各种节点类型。它提供了对AST的完全控制，但编写起来相对繁琐，且容易出错。
2. clang::ASTMatchers： 这是Clang提供的一种声明式API，通过组合一系列的匹配器函数来描述我们想要查找的AST模式。它更简洁、更强大，是开发Clang Tidy自定义检查器时推荐的方式。

例如，如果我们想查找所有返回类型为 void 的函数，使用 RecursiveASTVisitor 可能需要这样：

class MyVisitor : public RecursiveASTVisitor<MyVisitor> {
public:
    bool VisitFunctionDecl(FunctionDecl *F) {
        if (F->getReturnType()->isVoidType()) {
            // Found a void function
        }
        return true;
    }
};

而使用 ASTMatchers 则简洁得多：

// 匹配所有返回类型是void的函数声明
functionDecl(returns(voidType()))

在接下来的自定义检查器开发中，我们将主要使用 ASTMatchers。

四、 自定义Clang Tidy检查器：从概念到实现

现在，我们有了对Clang Tidy和AST的基础理解，是时候动手编写我们自己的自定义检查器了。

4.1 检查器架构概览

一个自定义的Clang Tidy检查器通常包含以下几个部分：

1. 继承 ClangTidyCheck： 所有的自定义检查器都必须继承自 clang::tidy::ClangTidyCheck。
2. 构造函数： 接收 CheckName 和 ClangTidyContext 作为参数。
3. registerMatchers 方法： 在这里注册我们想要匹配的AST模式。
4. check 方法： 当 registerMatchers 中注册的模式被匹配到时，check 方法会被调用，我们在这里执行检查逻辑并报告诊断信息。
5. registerCheck 函数： 在一个工厂函数中注册我们的检查器，让Clang Tidy能够发现并加载它。

4.2 开发环境搭建

要开发自定义Clang Tidy检查器，你需要：

1. LLVM/Clang 源码： 从LLVM官方仓库克隆源码。
2. 编译LLVM/Clang： 这通常是一个耗时的过程，需要足够的磁盘空间和内存。推荐使用CMake进行构建。例如：

   git clone https://github.com/llvm/llvm-project.git
   mkdir llvm-project/build
   cd llvm-project/build
   cmake -G "Ninja" ../llvm 
       -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" 
       -DCMAKE_BUILD_TYPE="Release" 
       -DLLVM_TARGETS_TO_BUILD="X86"
   ninja clang-tidy

   这会编译Clang Tidy及其依赖。

4.3 编写第一个自定义检查器：Hello World

让我们从一个简单的例子开始：查找所有名为 foo 的函数声明。

步骤1：创建新的检查器模块

在 llvm-project/clang-tools-extra/clang-tidy/ 目录下，通常会有一个 docs/ 和 misc/ 目录，以及各种检查器组（如 abseil/, cppcoreguidelines/ 等）。我们可以创建一个新的目录，例如 company-checks/。

// llvm-project/clang-tools-extra/clang-tidy/company-checks/
// CMakeLists.txt
add_clang_tidy_module(CompanyChecks
  CompanyChecksModule.cpp
  MyFirstCheck.cpp
  MyFirstCheck.h
)

步骤2：定义检查器类 (MyFirstCheck.h)

#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_COMPANY_CHECKS_MYFIRSTCHECK_H
#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_COMPANY_CHECKS_MYFIRSTCHECK_H

#include "../ClangTidyCheck.h" // 包含ClangTidyCheck基类

namespace clang {
namespace tidy {
namespace company_checks { // 命名空间，通常与目录结构对应

class MyFirstCheck : public ClangTidyCheck {
public:
    // 构造函数，传入检查器名称和上下文
    MyFirstCheck(StringRef Name, ClangTidyContext *Context)
        : ClangTidyCheck(Name, Context) {}

    // 注册我们感兴趣的AST匹配器
    void registerMatchers(ast_matchers::MatchFinder *Finder) override;

    // 当匹配器找到匹配项时，此方法会被调用
    void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
};

} // namespace company_checks
} // namespace tidy
} // namespace clang

#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_COMPANY_CHECKS_MYFIRSTCHECK_H

步骤3：实现检查器逻辑 (MyFirstCheck.cpp)

#include "MyFirstCheck.h"
#include "clang/AST/ASTContext.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/ASTMatchers/ASTMatchers.h"

using namespace clang::ast_matchers;

namespace clang {
namespace tidy {
namespace company_checks {

void MyFirstCheck::registerMatchers(MatchFinder *Finder) {
    // 匹配所有名为 "foo" 的函数声明
    Finder->addMatcher(
        functionDecl(hasName("foo")).bind("foo-function"), // .bind("...") 给匹配到的节点一个ID，方便在check方法中引用
        this
    );
}

void MyFirstCheck::check(const MatchFinder::MatchResult &Result) {
    // 从匹配结果中获取名为 "foo-function" 的节点
    const auto *MatchedFunction = Result.Nodes.getNodeAs<FunctionDecl>("foo-function");

    // 如果匹配成功（实际上，如果check被调用，MatchedFunction一定不为空）
    if (MatchedFunction) {
        // 报告诊断信息
        diag(MatchedFunction->getLocation(), "Found a function named 'foo'. Consider renaming it.");
    }
}

} // namespace company_checks
} // namespace tidy
} // namespace clang

步骤4：注册检查器 (CompanyChecksModule.cpp)

// CompanyChecksModule.cpp
#include "../ClangTidyModule.h"
#include "../ClangTidyModuleRegistry.h"
#include "MyFirstCheck.h" // 包含我们的检查器

namespace clang {
namespace tidy {
namespace company_checks {

// 这是一个工厂类，用于创建我们模块中的所有检查器
class CompanyChecksModule : public ClangTidyModule {
public:
    void addChecks(ClangTidyCheckFactories &CheckFactories) override {
        // 注册我们的MyFirstCheck
        CheckFactories.registerCheck<MyFirstCheck>("company-checks-my-first-check");
    }
};

// 使用ClangTidyModuleRegistry注册我们的模块
// 第一个参数是模块名称（在.clang-tidy文件中配置时会用到）
// 第二个参数是模块的描述
static ClangTidyModuleRegistry::Add<CompanyChecksModule>
    X("company-checks", "Adds checks for company-specific coding standards.");

} // namespace company_checks
} // namespace tidy
} // namespace clang

编译并运行Clang Tidy时，现在就可以通过 company-checks-my-first-check 名称来启用这个检查器了。

4.4 强制执行大厂代码规范的进阶检查器

现在，我们来设计并实现几个更贴近实际大厂代码规范的自定义检查器。

规范1：禁止在头文件中使用 using namespace

using namespace 指令在头文件中会导致命名空间污染，可能引发符号冲突或意外的行为。这是许多大型项目严格禁止的规范。

检查器名称： company-checks-no-using-namespace-in-headers

实现思路：

1. 匹配所有的 UsingDirectiveDecl（using namespace 声明）。
2. 检查该声明是否位于头文件中（即不在主源文件中）。

代码：

// NoUsingNamespaceInHeadersCheck.h
#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_COMPANY_CHECKS_NOUSINGNAMESPACEINHEADERSCHECK_H
#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_COMPANY_CHECKS_NOUSINGNAMESPACEINHEADERSCHECK_H

#include "../ClangTidyCheck.h"

namespace clang {
namespace tidy {
namespace company_checks {

class NoUsingNamespaceInHeadersCheck : public ClangTidyCheck {
public:
    NoUsingNamespaceInHeadersCheck(StringRef Name, ClangTidyContext *Context)
        : ClangTidyCheck(Name, Context) {}

    void registerMatchers(ast_matchers::MatchFinder *Finder) override;
    void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
};

} // namespace company_checks
} // namespace tidy
} // namespace clang

#endif

// NoUsingNamespaceInHeadersCheck.cpp
#include "NoUsingNamespaceInHeadersCheck.h"
#include "clang/AST/ASTContext.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/Lex/Lexer.h" // 用于获取源代码范围

using namespace clang::ast_matchers;

namespace clang {
namespace tidy {
namespace company_checks {

void NoUsingNamespaceInHeadersCheck::registerMatchers(MatchFinder *Finder) {
    // 匹配所有的 using namespace 声明
    Finder->addMatcher(usingDirectiveDecl().bind("using-directive"), this);
}

void NoUsingNamespaceInHeadersCheck::check(const MatchFinder::MatchResult &Result) {
    const auto *UsingDirective = Result.Nodes.getNodeAs<UsingDirectiveDecl>("using-directive");
    if (!UsingDirective)
        return;

    // 获取源代码管理器，用于判断文件类型
    const SourceManager &SM = Result.SourceManager->getManager();
    // 获取诊断的位置
    SourceLocation Loc = UsingDirective->getLocation();

    // 如果当前位置不在主源文件中（即在头文件中）
    if (!SM.isInMainFile(Loc)) {
        // 报告诊断信息
        auto Diag = diag(Loc, "Using-directive 'using namespace %0' is disallowed in header files.")
                        << UsingDirective->getQualifier()->getName();

        // 尝试提供自动修复：删除 'using namespace XXX;' 这一行
        // 获取using指令的范围
        SourceLocation EndLoc = Lexer::get  // 获取using指令的结束位置
            ::get  // (这里为了简化，假设一行一个using指令)
            get  get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get   get