Unlimited Code Works

Introduction

The aim of this post is to provide an insight into various aspects of the LLDB plugin, so that it is better understood, and can be used by more people. Should anyone want to improve it or add more features, he/she will also find useful technical details here.

In general, the LLDB plugin teaches KDevelop to talk to the standalone LLDB MI Driver (lldb-mi), so that it’s possible to use LLDB as an alternative debugger backend for KDevelop.

The rest of the post is orgainzed as follow

• Setting Up provides necessary information on how to get everything work from source code
• Features gives a detailed description of available features implemented in the LLDB plugin
• Roadmap lists some future works.

KDevelop is tightly coupled with KDevPlatform and from time to time you need to hack them both when developing. But then without caution, you’ll link against the system bundled KDevPlatform libraries and spend the whole day trying to find out why the hall the code you wrote didn’t have any effects.

That’s annoying and here’s how to make sure you are linking to the right copy.

Compile & Install KDevPlatform

Your awesome super hacked KDevPlatform need to be compiled and installed to somewhere first, say ~/stage. Don’t install it to any standard path like /usr or /usr/local just to avoid messing with the rest of the system. As a rule of thumb, if you need sudo privilege when doing make install, then you probably should consider somewhere else.

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_INSTALL_PREFIX=~/stage ..
make install

After several months’ working, LLDB plugin is now usable for basic debugging use cases. There are less than two weeks left, and it’s time to do a overall status update for the LLDB plugin.

Config Page

Using LLDB as the debugger backend is as easy as using the good old GDB debugger. Simply selecting LLDB in the combox at the top-right corner when editing the debug launch configuration should get things work in most normal cases.

Additionally, you can set Debugger Executable pointing to a specific version of LLDB. Note that this path should point to the lldb-mi executable, which is usually in the same folder as the normal lldb executable. Should you need any special configuration, Arguments and Environment let you fine tune the running environmnet of LLDB.

Time ticks away really fast if you keep yourself busy. I always thought there are planty of time for GSoC, but now half of it has already passed. With my university research, I’m actually more occupied and productive than I was in the last semester :P

Code, and more code

Lots of code, that’s what GSoC means, at least in my opinion. That’s exactly something I love. From time to time, I just feel like writing some code, for a somewhat big project, for something useful.

So that I can dig into the large code base, figuring out the relationships among classes, and then learn about the differences between the current design and the one I would architect, were I making the decision. This is definitely something I’m eager to experience.

In addition, the version history itself would tell good stories. Tracking down one particular file and seeing it evolves over the years, you’ll be surprised to find out that the code isn’t static anymore and there’re others’ efforts behind the scene continuously improving it, especially when reading through commit logs.

It has been a few weeks since the announcement of accepted projects. And I’ve been working on finding the most suitable solution to communicate with LLDB in KDevelop. In this article, I’d first give various choices to talk to LLDB, then evaluate these methods based on the current KDevelop debugger support and finally conclude with my final decision about which way to go.

Available communication methods

As mentioned in my proposal, there are mainly three ways to talk to LLDB in a debug session.

• Use GDB Machine Interface
  • LLDB-MI implementation which exists in LLDB source tree
  • LLDBMI2, which is a third party implementation that has a simpler and smaller code base
• Use C++ interface directly

Yes, I meant the GDB Machine Interface, and here’s a little background.

I’ve always wanted to participate in the Google Code of Summer. It’s cool and an super legitimate experience to put on CV, isn’t it? Anyway, what’s more exciting is that my first time proposal was accepted!

So I think it might be a good chance to also post this on the blog, which may probably keeps me writing more things and make the blog more… I mean, make it less like unmaintained XD

The big plan is, writing a series of articles as the project goes on and making them kind of status updates. Let see how far I can go though :P

Introduction

Enabling KDevelop to use LLDB as a debugging backend, which would be especially useful on Max OS X and Windows, where gdb support is rather scarce, and it can also help people that want to switch to lldb on linux (like me!) by adding decent IDE support.

• 虽然一直在准备，然而没想到第一篇正式的文章会是这样呢(苦笑)。
• 从买下域名开始，差不多已经一年了。
  • 中间因为毕业设计还有出国，这件事就搁置了
  • 最近受到朋友刺激才重新开始准备
    • 说起来友链部分也没有做呢
• 果然开博客不是一件容易的事情
  • 域名的调整
    • 从Namecheap迁移到Cloudflare想要至少部分使用HTTPS
    • 再从Cloudflare迁移回来，因为Cloudflare没法用自定义邮件服务，我的IP又正好处于黑名单不能自己搭邮件服务器
  • 服务器的调整
    • 通过Let‘s encrypt获得SSL证书，启用全站HTTPS (终于说到题目)
    • 从Github Page转移到自己的服务器上，也是为了Let’s encrypt的认证方便
    • 也许以后还会重新转移到Cloudflare，毕竟自己的小服务器各地访问速度应该还是不如CDN加速的好
  • 主题的修改
    • 找到符合心意的主题不容易
    • 现在的主题经过大幅度修改后还算可以(自认为)，最近真是前端技能猛长
    • 目前主题还不完善，搜索功能导航栏等等还在建设中，以后有机会再完成吧
    • 还是尽快开始写点儿东西会比较好
  • i18n的处理现在还不完善
    • 现在还是有点儿纠结究竟是做中文，英文还是两者
    • 这个问题也是日后再处理吧，TODO列表永远在变长也是无可奈何不是么
• 关于文章
  • 一开始应该会先把很久之前刷ACM题的一些题解搬过来吧，至少充下场面什么的
  • 然后是一些自己在做的pet project，想要做的idea的介绍，能吸引一些人气就好了 (虽然也没期待这儿会有什么人气就是了)
  • 也许还会有一些关于我目前在进行的学业上的研究的记录，如果可以的话也会放上来
  • 还有凭心情看情况的一些杂七杂八的东西
• 关于这个list
  • 曾经看了网上一个短篇推理小说里写到完全用list的方式来写blog，(这里，原链接已经失效所以链了Google搜索的第一个结果)
  • 简直就是不会组织语言还想写blog的我的救星啊
  • 所以虽然不知道能坚持到什么时候，什么程度，还是决定试试看

嗯。。还是算法复习用到了的，竟然还有OJ上有这道题，所以过了一下

参考是Candesoft-BLOG

大体思路就是首先分点，记录同一位置不同剩余油量的花费。

int cost[N+1][N+1][K+1];

然后从起点开始一点一点扩展，分别判断有和没有加油站的情况走到4个方向上是否是更优的花费。有点儿类似Dijkstra最短路的感觉。

使用前向星方法（应该是吧？我着实不确定这种我不知道从哪看到之后一直在用的存储方法究竟叫什么= =）存储的带权图，实现了通用的DFS和BFS算法，可以通过函数对象使用。

正好这两天复习算法，所以整理了一下。有些时候有这么一个模板还是挺方便的说。

直接上代码了

struct ForwardStarWGraph;
struct Node;

struct CallbackFunctor
{
    virtual bool shouldExtend(ForwardStarWGraph& graph, Node& toExtend) = 0;
    virtual bool operator() (ForwardStarWGraph& graph, Node& curr) = 0;
};

struct Node
{
    int i;
    int from;
    int edge;
    int totalWight;
    vector<int> path;
};

const int N = 20; // max vertex conut
const int M = N*N; // max edge count

struct ForwardStarWGraph
{
    int to[M], nxt[M], head[N];
    int wight[M];
    int ecnt;
    // Actual vertex number
    int n;

    void graphInit(int nn, int m)
    {
        ecnt = 0;
        n = nn;
        memset(head, -1, sizeof(head));
    }

    // Add an edge, vertex counts from 0
    void addEdge(int u, int v, int w)
    {
        to[ecnt] = v;
        wight[ecnt] = w;
        nxt[ecnt] = head[u];
        head[u] = ecnt;
        ecnt++;
    }

    // Add an undirectional edge
    void addBiEdge(int u, int v, int w)
    {
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    int wightBetween(int a, int b)
    {
        if(a == b)
            return 0;
        for(int e = head[a]; e!= -1; e = nxt[e])
        {
            if(to[e] == b)
                return wight[e];
        }
        return -1;
    }

    void bfs(CallbackFunctor& func)
    {
        queue<Node> Q;

        Node tem;
        tem.i = 0;
        tem.from = -1;
        tem.edge = -1;
        tem.totalWight = 0;
        tem.path.push_back(0);
        Q.push(tem);

        while(!Q.empty())
        {
            Node t = Q.front(); Q.pop();

            func(*this, t);

            for(int e = head[t.i]; e!= -1; e = nxt[e])
            {
                if(to[e] == t.from)
                    continue;
                Node t2;
                t2.i = to[e];
                t2.from = t.i;
                t2.edge = e;
                t2.totalWight = t.totalWight + wight[e];
                t2.path = t.path; t2.path.push_back(t2.i);
                if(func.shouldExtend(*this, t2))
                {
                    Q.push(t2);
                }
            }
        }
    }

    void dfs(CallbackFunctor& func)
    {
        stack<Node> Q;

        Node tem;
        tem.i = 0;
        tem.from = -1;
        tem.edge = -1;
        tem.totalWight = 0;
        tem.path.push_back(0);
        Q.push(tem);

        while(!Q.empty())
        {
            Node t = Q.top(); Q.pop();

            func(*this, t);

            for(int e = head[t.i]; e!= -1; e = nxt[e])
            {
                if(to[e] == t.from)
                    continue;
                Node t2;
                t2.i = to[e];
                t2.from = t.i;
                t2.edge = e;
                t2.totalWight = t.totalWight + wight[e];
                t2.path = t.path; t2.path.push_back(t2.i);
                if(func.shouldExtend(*this, t2))
                {
                    Q.push(t2);
                }
            }
        }
    }
};

附带一个测试小程序

比较基础的矩形切割，是POJ 2528 Mayor’s posters的二维版。

还是要注意边缘的情况，比如当(0,8)(18,18) 切割(18,0)(19,19)的时候，结果应该是得到三个矩形

• (18,19)(18,19) --> 面积为1
• (19,0)(19,19) --> 面积为20
• (18,0)(18,7) --> 面积为8

恩，其实我一直没搞懂为啥给数据的时候llx和lly是真正的坐标值，而urx和ury却必须减一之后再用…

/*
ID: xjtuacm1
PROG: rect1
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int M = 100000;
const int N = 1000;

struct rect
{
    int llx, lly;
    int urx, ury;
    int color;
    rect(int lx = 0, int ly = 0, int rx = 0, int ry = 0, int c = 0)
    : llx(lx), lly(ly), urx(rx), ury(ry), color(c) {}

    int S()
    {
        return (urx - llx + 1) * (ury - lly + 1);
    }
}rects[M], cur;
int tot;

inline bool cross(const rect& r1, const rect& r2)
{
    return !(
             (r1.llx > r2.urx)
             || (r1.urx < r2.llx)
             || (r1.lly > r2.ury)
             || (r1.ury < r2.lly));

}

inline void add(const rect& t)
{
    rects[tot++] = t;
}

inline void del(int idx)
{
    rects[idx] = rects[--tot];
}

void cut(const rect& t, bool vertical = false)
{
    int k1, k2;
    rect tem = t;
    if(vertical)
    {
        k1 = max(t.lly, cur.lly);
        k2 = min(t.ury, cur.ury);
        if(t.lly < k1)
        {
            tem.ury = k1 - 1;
            add(tem);
        }
        if(k2 < t.ury)
        {
            tem = t, tem.lly = k2 + 1;
            add(tem);
        }
    }
    else
    {
        k1 = max(t.llx, cur.llx);
        k2 = min(t.urx, cur.urx);
        if(t.llx < k1)
        {
            tem.urx = k1 - 1;
            add(tem);
        }
        if(t.urx > k2)
        {
            tem = t, tem.llx = k2 + 1;
            add(tem);
        }
        tem = t, tem.llx = k1 , tem.urx = k2;
        cut(tem, true);
    }
}


int main(int argc, char *argv[])
{
#ifdef ACM_LOCAL // Local
    freopen("in", "r", stdin);
#else
    #ifndef  ONLINE_JUDGE // not HDOJ / POJ
    freopen("rect1.in", "r", stdin);
    freopen("rect1.out", "w", stdout);
    #endif
#endif

    int a, b, n;
    scanf("%d %d %d", &a, &b, &n);
    add(rect(0, 0, a-1, b-1, 1)); // add the white sheet first.

    while(n--)
    {
        scanf("%d %d %d %d %d", &cur.llx, &cur.lly, &cur.urx, &cur.ury, &cur.color);
        cur.urx--, cur.ury--;

        for(int i = tot-1; i>= 0; i--)
        {
            if(cross(cur, rects[i]))
            {
                cut(rects[i]);
                del(i);
            }
        }
        add(cur);
    }

    map<int, int> cnt;
    for(int i = 0; i!= tot; i++)
    {
        cnt[rects[i].color] += rects[i].S();
    }

    for(map<int, int>::iterator it = cnt.begin(); it!= cnt.end(); it++)
    {
        if(it->second)
            printf("%d %d\n", it->first, it->second);
    }

    return 0;
}