ERC-2390: Geo-ENS

pragma solidity ^0.5.0;

import "../ResolverBase.sol";

contract GeoENSResolver is ResolverBase {
    bytes4 constant ERC2390 = 0x8fbcc5ce;
    uint constant MAX_ADDR_RETURNS = 64;
    uint constant TREE_VISITATION_QUEUESZ = 64;
    uint8 constant ASCII_0 = 48;
    uint8 constant ASCII_9 = 57;
    uint8 constant ASCII_a = 97;
    uint8 constant ASCII_b = 98;
    uint8 constant ASCII_i = 105;
    uint8 constant ASCII_l = 108;
    uint8 constant ASCII_o = 111;
    uint8 constant ASCII_z = 122;

    struct Node {
        address data; // 0 if not leaf
        uint256 parent;
        uint256[] children; // always length 32
    }

    // A geohash is 8, base-32 characters.
    // A geomap is stored as tree of fan-out 32 (because
    // geohash is base 32) and height 8 (because geohash
    // length is 8 characters)
    // geohash 为 8 个 base-32 字符。
    // geomap 存储为扇出为 32 的树（因为
    // geohash 为 base 32）和高度为 8（因为 geohash
    // 长度为 8 个字符）
    mapping(bytes32=>Node[]) private geomap;

    event GeoENSRecordChanged(bytes32 indexed node, bytes8 geohash, address addr);

    // only 5 bits of ret value are used
    // 仅使用 ret 值的 5 位
    function chartobase32(byte c) pure internal returns (uint8 b) {
        uint8 ascii = uint8(c);
        require( (ascii >= ASCII_0 && ascii <= ASCII_9) ||
                (ascii > ASCII_a && ascii <= ASCII_z));
        require(ascii != ASCII_a);
        require(ascii != ASCII_i);
        require(ascii != ASCII_l);
        require(ascii != ASCII_o);

        if (ascii <= (ASCII_0 + 9)) {
            b = ascii - ASCII_0;

        } else {
            // base32 b = 10
            // ascii 'b' = 0x60
            // note base32 skips the letter 'a'
            // base32 b = 10
            // ascii 'b' = 0x60
            // 注意 base32 跳过字母 'a'
            b = ascii - ASCII_b + 10;

            // base32 also skips the following letters
            // base32 也跳过以下字母
            if (ascii > ASCII_i)
                b --;
            if (ascii > ASCII_l)
                b --;
            if (ascii > ASCII_o)
                b --;
        }
        require(b < 32); // base 32 can't be larger than 32
        return b;
    }

    function geoAddr(bytes32 node, bytes8 geohash, uint8 precision) external view returns (address[] memory ret) {
        bytes32(node); // single node georesolver ignores node
        assert(precision <= geohash.length);

        ret = new address[](MAX_ADDR_RETURNS);
        if (geomap[node].length == 0) { return ret; }
        uint ret_i = 0;

        // walk into the geomap data structure
        // 走进 geomap 数据结构
        uint pointer = 0; // not actual pointer but index into geomap
        for(uint8 i=0; i < precision; i++) {

            uint8 c = chartobase32(geohash[i]);
            uint next = geomap[node][pointer].children[c];
            if (next == 0) {
                // nothing found for this geohash.
                // return early.
                // 没有找到此 geohash 的任何内容。
                // 提前返回。
                return ret;
            } else {
                pointer = next;
            }
        }

        // pointer is now node representing the resolution of the query geohash.
        // DFS until all addresses found or ret[] is full.
        // Do not use recursion because blockchain...
        // 指针现在是表示查询 geohash 的解析的节点。
        // DFS 直到找到所有地址或 ret[] 已满。
        // 不要使用递归，因为区块链...
        uint[] memory indexes_to_visit = new uint[](TREE_VISITATION_QUEUESZ);
        indexes_to_visit[0] = pointer;
        uint front_i = 0;
        uint back_i = 1;

        while(front_i != back_i) {
            Node memory cur_node = geomap[node][indexes_to_visit[front_i]];
            front_i ++;

            // if not a leaf node...
            // 如果不是叶节点...
            if (cur_node.data == address(0)) {
                // visit all the chilins
                // 访问所有孩子
                for(uint i=0; i<cur_node.children.length; i++) {
                    // only visit valid children
                    // 仅访问有效的孩子
                    if (cur_node.children[i] != 0) {
                        assert(back_i < TREE_VISITATION_QUEUESZ);
                        indexes_to_visit[back_i] = cur_node.children[i];
                        back_i ++;

                    }
                }
            } else {
                ret[ret_i] = cur_node.data;
                ret_i ++;
                if (ret_i > MAX_ADDR_RETURNS) break;
            }
        }

        return ret;
    }

    // when setting, geohash must be precise to 8 digits.
    // 设置时，geohash 必须精确到 8 位数字。
    function setGeoAddr(bytes32 node, bytes8 geohash, address addr) external authorised(node) {
        bytes32(node); // single node georesolver ignores node

        // create root node if not yet created
        // 如果尚未创建，则创建根节点
        if (geomap[node].length == 0) {
            geomap[node].push( Node({
                data: address(0),
                parent: 0,
                children: new uint256[](32)
            }));
        }

        // walk into the geomap data structure
        // 走进 geomap 数据结构
        uint pointer = 0; // not actual pointer but index into geomap
        for(uint i=0; i < geohash.length; i++) {

            uint8 c = chartobase32(geohash[i]);

            if (geomap[node][pointer].children[c] == 0) {
                // nothing found for this geohash.
                // we need to create a path to the leaf
                // 没有找到此 geohash 的任何内容。
                // 我们需要创建到叶子的路径
                geomap[node].push( Node({
                    data: address(0),
                    parent: pointer,
                    children: new uint256[](32)
                }));
                geomap[node][pointer].children[c] = geomap[node].length - 1;
            }
            pointer = geomap[node][pointer].children[c];
        }

        Node storage cur_node = geomap[node][pointer]; // storage = get reference
        cur_node.data = addr;

        emit GeoENSRecordChanged(node, geohash, addr);
    }

    function supportsInterface(bytes4 interfaceID) public pure returns (bool) {
        return interfaceID == ERC2390 || super.supportsInterface(interfaceID);
    }
}