C++20 协程入门：如何让你的函数‘原地休息’，等会儿再接着干？

各位编程专家，各位对现代C++充满好奇的同仁们，大家下午好！

今天，我们将深入探索C++20标准库中一项革命性的特性——协程（Coroutines）。在软件开发领域，异步编程一直是提高系统响应能力和资源利用率的关键。然而，传统的异步编程模型，无论是回调函数、事件循环还是基于Future/Promise的链式调用，都或多或少地带来了代码复杂性、可读性下降以及错误处理困难等问题。我们常常陷入“回调地狱”（Callback Hell），或者被迫将线性逻辑拆解成离散的状态机，这无疑增加了心智负担。

C++20协程的出现，正是为了解决这些痛点。它提供了一种全新的编程范式，允许我们以近乎同步的、顺序的风格编写异步代码。想象一下，你的函数在执行到某个耗时操作时，可以优雅地“暂停”下来，将CPU资源让给其他任务，然后在外部条件满足时，再从暂停的地方“原地恢复”，接着往下执行。这就像一个人走到一半觉得累了，原地坐下休息，等体力恢复了再站起来继续赶路，而不需要从头再走一遍。这种“原地休息，等会儿再干”的能力，正是C++20协程的核心魅力。

本次讲座，我们将层层剖析C++20协程的内部机制，从基础概念到实际应用，从编译器转换到自定义类型，力求让大家对协程的工作原理有一个全面而深刻的理解。

一、传统异步编程的困境：为何我们需要协程？

在深入了解协程之前，我们有必要回顾一下传统异步编程所面临的挑战。理解这些挑战，才能更好地体会协程带来的价值。

1.1 回调地狱 (Callback Hell)

最直观的异步编程方式可能就是回调函数了。当一个操作完成时，它会调用预先注册的回调函数来通知结果。然而，当多个异步操作需要按顺序执行，或者它们之间存在复杂的依赖关系时，回调函数就会层层嵌套，导致代码结构混乱，难以阅读和维护。

示例：模拟三个依赖的异步操作

#include <iostream>
#include <functional>
#include <thread>
#include <chrono>

// 模拟一个异步操作，1秒后调用回调
void async_op1(int input, std::function<void(int)> callback) {
    std::cout << "Async Op1 started with input: " << input << std::endl;
    std::thread([input, callback]() {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        int result = input * 2;
        std::cout << "Async Op1 finished, result: " << result << std::endl;
        callback(result);
    }).detach();
}

// 模拟第二个异步操作，依赖op1的结果
void async_op2(int input, std::function<void(int)> callback) {
    std::cout << "Async Op2 started with input: " << input << std::endl;
    std::thread([input, callback]() {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        int result = input + 10;
        std::cout << "Async Op2 finished, result: " << result << std::endl;
        callback(result);
    }).detach();
}

// 模拟第三个异步操作，依赖op2的结果
void async_op3(int input, std::function<void(int)> callback) {
    std::cout << "Async Op3 started with input: " << input << std::endl;
    std::thread([input, callback]() {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        int result = input / 2;
        std::cout << "Async Op3 finished, result: " << result << std::endl;
        callback(result);
    }).detach();
}

void run_traditional_async() {
    std::cout << "--- Traditional Async Callbacks ---" << std::endl;
    async_op1(5, [](int res1) {
        async_op2(res1, [](int res2) {
            async_op3(res2, [](int final_res) {
                std::cout << "All async operations completed. Final result: " << final_res << std::endl;
            });
        });
    });
    std::cout << "Main thread continues immediately..." << std::endl;
    // 实际应用中，这里需要某种机制来等待所有异步操作完成，比如一个条件变量或future
    std::this_thread::sleep_for(std::chrono::seconds(4)); // 简单地等待足够长的时间
    std::cout << "--- Traditional Async Callbacks END ---" << std::endl;
}

// int main() {
//     run_traditional_async();
//     return 0;
// }

这段代码的可读性已经开始下降，更不用说错误处理、取消操作等复杂场景。每次异步调用都会引入一个新的Lambda层级，导致代码向右缩进，形成所谓的“金字塔”结构。

1.2 Future/Promise 模式

为了缓解回调地狱，C++11引入了std::future和std::promise，以及std::async。它们提供了一种更结构化的方式来处理异步操作的结果，允许我们获取异步操作的返回值或捕获异常。

#include <future> // 包含future头文件

// 模拟返回future的异步操作
std::future<int> async_op_future_1(int input) {
    return std::async(std::launch::async, [input]() {
        std::cout << "Future Op1 started with input: " << input << std::endl;
        std::this_thread::sleep_for(std::chrono::seconds(1));
        int result = input * 2;
        std::cout << "Future Op1 finished, result: " << result << std::endl;
        return result;
    });
}

std::future<int> async_op_future_2(int input) {
    return std::async(std::launch::async, [input]() {
        std::cout << "Future Op2 started with input: " << input << std::endl;
        std::this_thread::sleep_for(std::chrono::seconds(1));
        int result = input + 10;
        std::cout << "Future Op2 finished, result: " << result << std::endl;
        return result;
    });
}

std::future<int> async_op_future_3(int input) {
    return std::async(std::launch::async, [input]() {
        std::cout << "Future Op3 started with input: " << input << std::endl;
        std::this_thread::sleep_for(std::chrono::seconds(1));
        int result = input / 2;
        std::cout << "Future Op3 finished, result: " << result << std::endl;
        return result;
    });
}

void run_future_async() {
    std::cout << "n--- Future/Promise Async ---" << std::endl;
    auto f1 = async_op_future_1(5);
    // 链式调用仍然需要阻塞或使用then()等扩展（C++标准库未提供）
    int res1 = f1.get(); // 阻塞等待第一个操作完成
    auto f2 = async_op_future_2(res1);
    int res2 = f2.get(); // 阻塞等待第二个操作完成
    auto f3 = async_op_future_3(res2);
    int final_res = f3.get(); // 阻塞等待第三个操作完成

    std::cout << "All async operations completed. Final result: " << final_res << std::endl;
    std::cout << "--- Future/Promise Async END ---" << std::endl;
}

// int main() {
//     run_traditional_async();
//     run_future_async();
//     return 0;
// }

虽然future避免了层层嵌套的回调，但f.get()本质上是一个阻塞操作。如果主线程调用get()，那么主线程就会暂停，直到异步操作完成。这与我们希望的“不阻塞主线程”的异步目标相悖。虽然有一些库（如Boost.Asio、folly::Future）提供了then()方法来实现非阻塞的链式调用，但它们通常不是C++标准库的一部分，并且仍然需要在逻辑上拆分代码。

1.3 手动状态机

对于一些复杂的异步流程，开发者有时会通过手动维护状态机来管理。每个状态对应流程的一个阶段，通过事件触发状态转换。这种方式虽然能实现非阻塞，但代码通常非常冗长、复杂，难以理解和调试。每增加一个步骤或改变逻辑，都需要修改状态机的多个部分，维护成本极高。

简而言之，传统异步编程模型在追求非阻塞和高性能的同时，往往牺牲了代码的简洁性、可读性和可维护性。我们渴望一种能够让我们像写同步代码一样写异步代码的机制，而这正是C++20协程所能提供的。

二、C++20 协程：编程范式的革新

C++20协程提供了一种在运行时暂停和恢复函数执行的能力。一个协程在执行过程中遇到某个特定的“暂停点”时，它可以将控制权返回给它的调用者，同时保留其当前的执行状态（包括局部变量、程序计数器等）。之后，当某个条件满足时，外部代码可以“恢复”这个协程，让它从上次暂停的地方继续执行。这便是我们所说的“让你的函数‘原地休息’，等会儿再接着干”的核心思想。

2.1 协程与线程的区别

在深入了解协程的具体机制前，我们首先要明确协程与线程的区别：

特性	协程 (Coroutines)	线程 (Threads)
调度	协作式调度：协程主动放弃控制权（通过 co_await, co_yield）。	抢占式调度：操作系统或运行时环境分配时间片。
上下文切换	用户态切换：通常开销很低，只涉及保存/恢复部分寄存器和协程状态。	内核态切换：开销相对较高，涉及保存/恢复所有寄存器、内存映射、CPU缓存等。
栈	栈无关 (Stackless)：协程的局部变量和状态被存储在堆上（协程帧），不依赖于传统的函数栈。	栈相关 (Stackful)：每个线程有独立的调用栈。
并发模型	并发：通常用于实现轻量级并发，而非真正的并行执行（除非配合线程池）。	并行：可以同时在多个CPU核心上执行。
资源消耗	轻量级：创建和管理开销小，可以有成千上万个。	重量级：创建和管理开销大，通常数量有限。
编程模型	顺序式异步：异步操作看起来像同步代码。	并行同步：需要锁、互斥量等同步原语来管理共享状态。

简而言之，协程是一种用户态的轻量级并发原语，旨在简化异步编程的复杂性，它不直接提供并行能力，但可以非常高效地管理大量并发任务。

2.2 C++20 协程的关键字

C++20为协程引入了三个新的关键字：

• co_await: 用于暂停当前协程，等待一个“可等待对象”（awaitable object）完成。当可等待对象完成后，协程会从暂停点恢复执行。这是实现“原地休息”的核心机制。
• co_yield: 用于暂停当前协程，并返回一个值给调用者。当调用者请求下一个值时，协程会从暂停点恢复执行。这主要用于实现生成器（Generator）模式。
• co_return: 用于结束协程的执行，并返回一个值（或无值）。类似于普通函数的return语句，但它是协程专用的。

当一个函数内部包含这三个关键字中的任何一个时，C++编译器就会将其识别为一个协程，并进行特殊的转换。

三、解剖协程：核心组件与生命周期

理解协程，需要深入其背后的几个核心组件：std::coroutine_handle、promise_type、以及awaitable类型。它们共同构成了协程的运行时机制。

3.1 协程帧 (Coroutine Frame)

当一个函数被编译器识别为协程时，它的局部变量、参数、返回地址以及与协程状态相关的其他信息将不会像普通函数那样存储在调用栈上。相反，编译器会分配一块内存（通常在堆上），我们称之为协程帧（Coroutine Frame），来存储这些状态。这个协程帧的生命周期独立于协程的调用者，它会一直存在，直到协程彻底执行完毕并被销毁。

正是这种堆上分配的协程帧，使得协程能够多次暂停和恢复，而不会丢失其局部状态。

3.2 std::coroutine_handle：协程的“遥控器”

std::coroutine_handle<P> 是一个非拥有（non-owning）的类型擦除句柄，它指向一个被暂停的协程帧。这里的 P 是协程的 promise_type 类型。你可以把它想象成一个遥控器，通过它你可以对暂停的协程进行操作，最主要的就是：

• handle.resume(): 恢复协程的执行。
• handle.destroy(): 销毁协程帧，释放内存。
• handle.done(): 检查协程是否已经完成。

重要提示： coroutine_handle 不拥有协程帧的生命周期。你必须确保在协程帧被销毁之前，不要使用无效的 handle。

3.3 promise_type：协程的“管家”

每个协程都有一个关联的承诺类型（promise_type）。这个类型是协程行为的核心。当编译器将一个函数转换为协程时，它会查找与协程返回类型关联的 promise_type。这个查找机制是通过 std::coroutine_traits<ReturnType, Args...> 特化来完成的。

promise_type 负责管理协程的生命周期、结果和异常处理。它需要定义一系列特殊的方法：

| 方法签名 | 作用 T C I T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B T B T B T B T B T B T B T B T B T B B B B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T T B T B T B T B T B T B T B T B T B T B T B T B B B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B B B B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B B B B B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T B T