tag:blogger.com,1999:blog-64708543163962837202024-03-06T09:34:28.413+01:00Enki :: Technical BlogAnonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-6470854316396283720.post-10326245845024921582012-09-10T17:59:00.000+02:002012-09-11T22:46:02.862+02:00C++11: Simple Compile-time Calculator With Constexpr<body>
<div id="content">
<p>Hi everyone! In this post we'll run through a classical computer science exercise: Building an arithmetic evaluator. This one will only
manage +, -, * and /, no parenthesis, infix notation, no space (simple
to add, but boring). That may look too simple… Let's add a
constraint: computations must be done at compile time.
</p>
<p>
For the little story, I wanted to code it after one of my teacher told
me a story about a project for students that consists in building an
arithmetic evaluator (bistromathique) able to deal with very huge
number (a lot bigger than 2<sup>32</sup>). The computation to do was stored in a
file given to the student before 'make' was run to build its
project. A student simply created a rule in his Makefile that makes
another program evaluates the input file and redirected the result
into the expected binary that only printed it out. Nice cheat right?
Unfortunately for him, he was caught, that's why we know the story,
but the idea is exploitable. Why not making computation at compile
time? A real problem is how to parse this expression.
</p>
<p>
In this post, I'll first show you how to think the problem to be able
to represent it simply. Then, I'll present the available tools to make
"beautiful" compile-time expressions with C++11, and finally I'll show
and explain the whole code. Let's go!
</p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> How to evaluate an arithmetic expression? </h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-1.1" class="outline-3">
<h3 id="sec-1.1"><span class="section-number-3">1.1</span> Language Theory </h3>
<div class="outline-text-3" id="text-1.1">
<p>
There is a lot of different way to evaluate an arithmetic
expression. Some people will make it with the <a href="http://en.wikipedia.org/wiki/Shunting-yard_algorithm">Shunting Yard</a> algorithm,
or with some tools to generate parser (<a href="http://www.gnu.org/software/bison/">Bison</a> for example), etc. I
wanted a simple way to do it. Bison will not be helpful here, Shunting
Yard is too heavy. Should we create a constant Abstract Syntax Tree? Or
a constant Stack? It doesn't seem interesting for us to translate it,
in term of time (at a development level). The proposed solution is
based on Language Theory. The arithmetic language follows a simple
grammar. First, you have to know how to read a grammar. A grammar is
composed of several rules of this form:
</p>
<pre class="src src-dot"><symbol> ::= expression
</pre>
<p>
<code><symbol></code> is called nonterminal. <code>expression</code> is a sequence of
symbols. Symbols are a nonterminal or a terminal (a terminal doesn't
appear on the left side of a rule. In this post, they appear between
double quotes). There could be several possibilities (one expression
or another, it is represented as ~expression1 | expression2). More
information on <a href="http://en.wikipedia.org/wiki/Backus-Naur_form">Wikipedia</a>. The simple arithmetic grammar used is:
</p>
<pre class="src src-dot"><expr> ::= <T>
<T> ::= <U> <span style="color: #cc9393;">"+"</span> <T> | <U> <span style="color: #cc9393;">"-"</span> <T> | <U>
<U> ::= <number> <span style="color: #cc9393;">"*"</span> <U> | <number> <span style="color: #cc9393;">"/"</span> <U> | <number>
<number> ::= <number> <digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
</pre>
<p>
Well! It seems a little cryptic when you don't know what it is, but
you'll see that it's not :). Your expression must follow a path in
these rules to be grammatically valid. Otherwise there is an
error. Let's see what say these rules: a valid expression follows the
rules <T>. <T> means that the expression is a <U> plus <T>, or a <U>
minus <T>, or just a <U>. <U> is a <number> times <U>, or a <number>
slash <U>, or just a <number>. A <number> is a nonempty list of
<digit>. And here it is! You can write an addition, a subtraction, a
division and a multiplication.
</p>
<p>
The rule are selected in function of your expression, it takes
(roughly) what matches the more. Here is how it passes through the
rules with several examples:
</p>
<ul>
<li>
2: take the rule <T>, <U>, <number>, <digit>. Valid.
</li>
<li>
2+3: take the rule <T>, <U> "+" <T>:
<ul>
<li>
expr is 2. <U> becomes <number>, <digit>;
</li>
<li>
expr is 3. <T> becomes <U>, <number>, <digit>. Sill valid.
</li>
</ul>
</li>
<li>
2+*3: take the rule <T>, <U> "+" <T>:
<ul>
<li>
expr is 2. <U> becomes <number>, <digit>;
</li>
<li>
expr is *3. <T> becomes <U>, <number> "*" <digit>:
<ul>
<li>
expr is empty. <number> is an error.
</li>
</ul>
</li>
</ul>
<p>So it is invalid.
</p>
</li>
</ul>
<p>I hope these little examples help you to understand how it works if
you didn't know. You can ask questions in comments if you want
;-). I'll be pleased to help you. If you spot a mistake, don't
hesitate to signal it!
</p>
</div>
</div>
<div id="outline-container-1.2" class="outline-3">
<h3 id="sec-1.2"><span class="section-number-3">1.2</span> How to implement it? </h3>
<div class="outline-text-3" id="text-1.2">
<p>
You should be convinced (I hope) that these rules would help us to
implement simply an arithmetic evaluator. Moreover, since the priority
between operators is managed by the recursion (yes, multiplication
will occur before addition for example), you can do all the
computations on-the-fly. No need to build a Stack, or an Abstract
Syntax Tree. I really love this method because it is simple to
implement. For people that think that the lack of parenthesis causes
its method to be so easy, you're wrong. I let you the job to find
where to integrate them (hint: the latter the rule is called, the
higher its precedence is. Example, the multiplication is called later
than the addition, and so it has a higher precedence).
</p>
<p>
We just have to represent these rules with functions. It's not really
so easy, because if you implement it as this:
</p>
<pre class="src src-c++"><span style="color: #f0dfaf;">evalT</span>(<span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">expr</span>) { <span style="color: #f0dfaf; font-weight: bold;">return</span> evalU(head(expr)) - evalT(tail(expr)); }
</pre>
<p>
In this snippet <code>head</code> takes the expression and returns the part
before the '-' and <code>tail</code> returns the part after. You'll have this
behavior: <code>eval(2-4+2)</code> will return -4. Because it will evaluate 4+2
before applying the '-'. So you must compute one <U> at a time. This
way, <code>2-4+2</code> will be processed this way: <code>accu = 2 - 4; accu = accu + 2</code> and <code>accu</code> will be equal to 0 as expected.
</p>
<p>
So it is really easy to implement, one function for each rule, and you
have to loop over each new nonterminal (for <T> it is <U>, for <U> it
is <number>…) and apply the right operation. And it will work!
</p>
<p>
But you may wonder (and it's great!): How can I do an error
management? Simply, you can make lexical error (invalid character)
when you process the value of your number in the last rule. And you
can make a parse error if your last rule received an empty
content. That means there is two operators side by side. Finally, all
the error management is done in the function that evaluates your
number.
</p>
<p>
Finally, to have a fully featured arithmetic evaluator, you have to
find how to put the parenthesis in these recursive functions (hint:
error management is also very simple in this case). Once again, you
can ask question if you want :)
</p>
<p>
For having implemented it some time ago, I can say that it may take 3
functions of less than 30 lines each. But now, let's add some fun!
Let's see how we can transform this into a compile-time version.
</p>
</div>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> Compile-time arithmetic evaluator </h2>
<div class="outline-text-2" id="text-2">
</div>
<div id="outline-container-2.1" class="outline-3">
<h3 id="sec-2.1"><span class="section-number-3">2.1</span> Compile-time tools with C++11 </h3>
<div class="outline-text-3" id="text-2.1">
<p>
"Constexpr is a 4th sublanguage added to C++" - Andrei Alexandrescu.
</p>
<p>
In C++03, there was only templates to make computation at compile-time
(explicitly I mean. Sometimes compiler can do this kind of
optimization alone). But it was really painful. For example, to make
something as simple as factorial you had to declare a template class
parametrized by an integer, and specialized it when the integer is 0.
Here is how it looks:
</p>
<pre class="src src-c++"><span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #dfdfbf; font-weight: bold;">unsigned</span> <span style="color: #f0dfaf;">n</span>>
<span style="color: #f0dfaf; font-weight: bold;">struct</span> <span style="color: #dfdfbf; font-weight: bold;">fact</span>
{
<span style="color: #f0dfaf; font-weight: bold;">static</span> <span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span> = n * <span style="color: #dca3a3; font-weight: bold;">fact</span><n - 1>::value;
};
<span style="color: #f0dfaf; font-weight: bold;">template</span> <>
<span style="color: #f0dfaf; font-weight: bold;">struct</span> <span style="color: #dfdfbf; font-weight: bold;">fact</span><0>
{
<span style="color: #f0dfaf; font-weight: bold;">static</span> <span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span> = 1;
};
</pre>
<p>
The first class <code>fact</code> declares the general case where <code>value</code> is
equal to <code>n</code> times <code>n - 1</code> (it is just written with template). We then
had to specialize this class when the integer is 0. That way, when you
call <code>fact<5>::value</code>, it will answer 120 as expected. But this
approach has some drawbacks. The syntax may look ugly (sweet
euphemism…), it is error prone, hard to debug, and so on. I think no
one will try to parse and evaluate complex structures with
template. If this person exists, I have a deep respect for its
courage…
</p>
<p>
So C++11 comes with a new support for compile time programming:
constexpr. It allows to make computation during the compilation
("Because compilation was already too fast" - Herb Sutter). I have
already discussed a little about constexpr in a <a href="#enki-tech.blogspot.com/2012/08/c11-vector-improved-how-it-works.html">previous post</a>. Let's
go a little deeper, according to the standard, there are several
constraints that a function must satisfy to be considered as
constexpr:
</p>
<ul>
<li>
Call only constexpr function,
</li>
<li>
Only one return statement,
</li>
<li>
<code>static_assert</code> are fine,
</li>
<li>
All its declaration must be declared constexpr.
</li>
</ul>
<p>I don't write all the conditions here (the standard is long… More on
<a href="http://en.cppreference.com/w/cpp/language/constexpr">cppreference</a>) but here are the main conditions you should be aware
of. First question: how to make real functions with only one return?
In fact you have to deal a lot with recursion, and with ternary
operator (<code>?:</code>).
</p>
<p>
Here is the implementation of factorial using constexpr:
</p>
<pre class="src src-c++">constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">fact</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">n</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> n == 0 ? 1 : n * fact(n - 1);
}
</pre>
<p>
Personally, I found this version simpler to write and to read. For me
this is a great thing to gain in readability. There is a second huge
advantage to deal with constexpr instead of template: constexpr can be
used in the compile-time and run-time world. It avoids having two
(very different) codes to solve the same problem. Some (important)
things to note:
</p>
<ul>
<li>
<code>static_assert</code> can't be used to check the value of your argument
since it can be called at run time. If you want to do that, you must
pass the argument as template parameter. For a little
discussion about that, see <a href="http://stackoverflow.com/questions/8626055/c11-static-assert-within-constexpr-function">this question</a> on stackoverflow.
</li>
<li>
You can't declare an argument of a function constexpr.
</li>
<li>
Prefix and postfix incrementation/decrementation on a variable are
forbidden.
</li>
<li>
Constexpr function are implicitly inline.
</li>
<li>
Constexpr non-static method is const (if it is not a constructor of
course!).
</li>
<li>
There is an implementation defined (I think) limit for recursion, to
change its value, you can use the <code>-fconstexpr-depth=</code> option. I'm
not sure if this flag is standard, at least it works with g++-4.6.1,
4.7.1, clang++-3.0 and clang++-3.1.
</li>
</ul>
</div>
</div>
<div id="outline-container-2.2" class="outline-3">
<h3 id="sec-2.2"><span class="section-number-3">2.2</span> How to do error management with constexpr? </h3>
<div class="outline-text-3" id="text-2.2">
<p>
This is a tougher question than it seems. I first tried to use
<code>static_assert</code>, because I wanted to have an error clear at compile
time. But the first point of the list of notes above makes me unable
to succeed. So I used exception. Some part are not evaluated. For
example, in <code>b ? 1 : 0</code>, the 0 part is evaluated only if b is
false. So you can put a <code>throw</code> expression on the false part in a
constexpr function. This will cause the function to not respect the
definition of a constexpr function and it will fail the
compilation. In my opinion, compile-time programming should have
compile-time error.
</p>
<p>
I chose to implement it that way:
</p>
<pre class="src src-c++">constexpr
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">my_static_assert</span>(<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">b</span>, <span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>*)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> b ? <span style="color: #dca3a3; font-weight: bold;">true</span> : <span style="color: #f0dfaf; font-weight: bold;">throw</span> <span style="color: #dca3a3; font-weight: bold;">std</span>::exception();
}
</pre>
<p>
If I want to use it only at compile-time (the code above represents
that case), I implement it that way. I want to have an explicit error
message, that's why there is a second argument. As you can see, I
don't use it (reminder: if you don't give a name to an argument, the
compiler understand that it will not be used). So, you may wonder why
I put that here? To get an helpful error message: Here is an extract
of the g++ error message I get if I do a parse error in my program:
</p>
<pre class="src src-dot">$ g++ --std=c++11 -DEXPR=<span style="color: #cc9393;">"\"3*+9\""</span> static_eval_expr.cc
static_eval_expr.cc: In function 'int main()':
static_eval_expr.cc:102:32: \
in constexpr expansion of 'parseT(((const char*)<span style="color: #cc9393;">"3*+9"</span>), 0, 1)'
static_eval_expr.cc:96:43: \
in constexpr expansion of 'parseT_private(s, s, 0, value, ((int)op))'
........
static_eval_expr.cc:48:60: in constexpr expansion of \
'my_static_assert((len != 0), \
((const char*)<span style="color: #cc9393;">"Parse error: No side by side operators!"</span>))'
static_eval_expr.cc:28:42: erreur: expression \
'<throw-expression>' is not a constant-expression
</pre>
<p>
(The dot line represents some lines I dropped out to simplify the
example, lines finishing by a '\' continue in the line below). I hope
it is clear enough. I can't get the exact location, but it is better
than just a non understandable compile error right?
</p>
<p>
Note that I chose to raise std::exception because the error message
doesn't give this information clearly, and the main information is
contained in the constant string. In all other situations,
std::exception is, in my opinion, to avoid. Using clear type is
helping the compiler and the programmer. So don't use that in the real
world! :)
</p>
<p>
Now, let's see how works my compile-time version of our arithmetic
evaluator!
</p>
</div>
</div>
<div id="outline-container-2.3" class="outline-3">
<h3 id="sec-2.3"><span class="section-number-3">2.3</span> How it works </h3>
<div class="outline-text-3" id="text-2.3">
<p>
The classical grammar-based algorithm uses recursion, loops, and makes
a pointer run through the string. We only have recursion. There is no
mutable variable. So we have to figure out how to transform our
run-time version (I didn't present the code of the run-time version
here because I don't want student of my school to use it for their own
project) into a full constant version.
</p>
<p>
To loop through the string we use recursion. I first implement a
compile-time atoi (ascii-to-int). I assume that we use ASCII standard
(I want that because in that case: the value of the character '4'
subtracted to the character '0' is equal to 4, and the same for every
character representing a digit). So let's see how we can do that with
some checking. I'll use <code>my_static_assert</code> declared above.
</p>
<pre class="src src-c++">constexpr
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">is_number</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span> <span style="color: #f0dfaf;">c</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> c >= <span style="color: #cc9393;">'0'</span> && c <= <span style="color: #cc9393;">'9'</span>;
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">myatoi</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">len</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span> = 0)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> *s && len
? (my_static_assert(is_number(*s), <span style="color: #cc9393;">"Invalid character!"</span>),
myatoi(s + 1, len - 1,
(*s - <span style="color: #cc9393;">'0'</span>) + value * 10))
: value;
}
</pre>
<p>
<code>is_number</code> is trivial, it returns true if the character given in
argument is a digit and false otherwise. Let's see <code>myatoi</code> now. It
takes as first argument the string (we use <code>char*</code> because we can't
use <code>std::string</code> since its not constexpr. So we go down one level and
we directly work on the pointer). The second argument is the number of
characters we must read. Because in our use case, we just send it part
of the string to read, and this part is defined by a beginning and a
size. The third argument is the current value accumulated. I indent
all ternary expression to make it as clear as possible.
</p>
<p>
If we translate the code above in English, we have: if the current
character is not null and we have still some characters to read: check
that the current character is a number, if not raise an error. If it
is valid, call yourself on the next character, reduce the number of
character to read by one, and update the value. If we have finished to
read our string, return the accumulated value.
</p>
<p>
Let's see how we update the value: We read our string from left to
right, so we add the first character to value. Then we just have to
multiply by 10 the accumulated value each time we move on the right! :)
</p>
<p>
Now, we have to apply our recursive calls to manage priority between
the operators. Remember that we have to find a way to advance your
"pointer" to didn't read several time the same part of the string
we're working on.
</p>
<p>
Since all is constant, the way I found is to create a substring
defined by the beginning of the substring and its length. Then we call
recursively ourselves, with the updated value. So here is how it
works: the function that manages the operation '+' and '-' is split
into two: there is a function that makes the interface and initialize
some variables, and the other one that does the job. So it ends up
with two functions per rules. Here is (finally!) the whole code:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><iostream></span>
constexpr <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">parseT</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span> = 0, <span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">op</span> = <span style="color: #dca3a3; font-weight: bold;">true</span>);
constexpr <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">parseU</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">limit</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span> = 1,
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">op</span> = <span style="color: #dca3a3; font-weight: bold;">true</span>);
constexpr
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">is_number</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span> <span style="color: #f0dfaf;">c</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> c >= <span style="color: #cc9393;">'0'</span> && c <= <span style="color: #cc9393;">'9'</span>;
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">is_valid</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span> <span style="color: #f0dfaf;">c</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> is_number(c) || c == <span style="color: #cc9393;">'+'</span> || c == <span style="color: #cc9393;">'-'</span> || c == <span style="color: #cc9393;">'*'</span> || c == <span style="color: #cc9393;">'/'</span>;
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">my_static_assert</span>(<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">b</span>, <span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>*)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> b ? <span style="color: #dca3a3; font-weight: bold;">true</span> : <span style="color: #f0dfaf; font-weight: bold;">throw</span> <span style="color: #dca3a3; font-weight: bold;">std</span>::exception();
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">myatoi_private</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">len</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span> = 0)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> *s && len
? (my_static_assert(is_number(*s), <span style="color: #cc9393;">"Invalid character!"</span>),
myatoi_private(s + 1, len - 1,
(*s - <span style="color: #cc9393;">'0'</span>) + value * 10))
: value;
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">myatoi</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">len</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> my_static_assert(len, <span style="color: #cc9393;">"No side by side operators!"</span>),
myatoi_private(s, len);
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">parseU_private</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">limit</span>, <span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">begin</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">len</span>,
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span>, <span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">mul</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> *s && limit
? (*s == <span style="color: #cc9393;">'*'</span> || *s == <span style="color: #cc9393;">'/'</span>
? (mul
? parseU(s + 1, limit - 1, value * myatoi(begin, len),
*s == <span style="color: #cc9393;">'*'</span>)
: parseU(s + 1, limit - 1, value / myatoi(begin, len),
*s == <span style="color: #cc9393;">'*'</span>))
: parseU_private(s + 1, limit - 1, begin, len + 1, value, mul))
: (mul
? value * myatoi(begin, len)
: value / myatoi(begin, len));
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">parseU</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">limit</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span>, <span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">op</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> parseU_private(s, limit, s, 0, value, op);
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">parseT_private</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">begin</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">len</span>,
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span>, <span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">add</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> *s
? (*s == <span style="color: #cc9393;">'+'</span> || *s == <span style="color: #cc9393;">'-'</span>
? (add
? parseT(s + 1, value + parseU(begin, len),
*s == <span style="color: #cc9393;">'+'</span>)
: parseT(s + 1, value - parseU(begin, len),
*s == <span style="color: #cc9393;">'+'</span>))
: parseT_private(s + 1, begin, len + 1, value, add))
: (add
? value + parseU(begin, len)
: value - parseU(begin, len));
}
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">parseT</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">char</span>* <span style="color: #f0dfaf;">s</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span>, <span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">op</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> parseT_private(s, s, 0, value, op);
}
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">constexpr</span> <span style="color: #f0dfaf; font-weight: bold;">auto</span> e = EXPR;
<span style="color: #dfdfbf; font-weight: bold;">constexpr</span> <span style="color: #f0dfaf; font-weight: bold;">auto</span> res = parseT(e);
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << res << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
}
</pre>
<p>
If you want to test the code, copy/paste this in your favorite editor,
and compile it like this:
</p>
<pre class="src src-dot">g++(4.6.1): g++ --std=c++0x -DEXPR=<span style="color: #cc9393;">"\"1+1\""</span> file.cc
g++(4.7.1 or 4.8): g++ --std=c++11 -DEXPR=<span style="color: #cc9393;">"\"1+1\""</span> file.cc
clang++(3.1): clang++ --std=c++11 -DEXPR=<span style="color: #cc9393;">"\"1+1\""</span> file.cc
</pre>
<p>
It won't compile with a clang version lower than 3.1. If you have
tried another compiler, feel free to report your results in
comments :) You can replace <code>1+1</code> by any arithmetic expression
composed by number, '+', '-', '*', '/'. If your expression is not
valid, it won't compile. Note that spaces are forbidden. As said in
the beginning, it is not a feature hard to add, but it adds dumb code
when I want code to be crystal clear.
</p>
<p>
Now let's explain a little the code above, starting by the
main. <code>EXPR</code> is the variable given on the command line when compiling
(with the <code>-D</code> option). <code>parseT</code> takes a <code>const char*</code> and returns an
integer. Variables can be declared constexpr, so we declare <code>e</code> and
<code>res</code> constexpr. Then we just print the result. Now, let's run through
the interesting part of the code.
</p>
<p>
<code>parseT_private</code> takes as second argument the beginning of the current
sub expression we will give to the second level (<code>parseU</code>). So we have
to create a <code>parseT</code> function that set the beginning of the
expression. This is the same thing for <code>parseU</code> that calls
<code>myatoi</code>. The main idea of the recursion is that I read my expression
until I get one of the operator of my level (for <code>parseT</code> it is '+' or
'-', for <code>parseU</code> it is '*' or '/'). Once it is done, it gives the
substring between the beginning and just before the operator to be
evaluated by the next level. And this updates the current value. We
then run the recursion on the right part of the operator. We have to
remember what was the operation before this subexpression to apply it
when updating the current value. So at the beginning, value is 0, and
the first operation is a '+' (this explains the op = true in parseT).
</p>
<p>
Let's see some steps of the program to understand how it
thinks:
</p>
<ul>
<li>
2+2: <code>parseT("2+2")</code> calls <code>parseT_private("2+2", "2+2", 0, 0, true)</code>. We read 2, and we arrive to a '+'. So we call <code>parseU</code> on
"2", which returns 2 since there is no '*' nor '/' in this
expression. We add 2 to the variable <code>value</code>, we remember that we
have seen a '+', and we call <code>parseT</code> on the right part of the
'+'. We arrive to end of string, so we just call <code>parseU</code> on "2",
and we get two. The previous operator was a '+', so we add. 2+2 = 4,
as expected!
</li>
<li>
2*2+2: <code>parseT_private("2*2+2", "2*2+2", 0, 0, true)</code>, we still stop
at the '+', so <code>parseU</code> receives "2*2" and the variable <code>limit</code> is
equal to 3 (to know where stop reading). In <code>parseU_private</code> we are
looking for a '*' or a '/'. We get a '*', so we send the left part
to <code>myatoi</code>, and we continue our recursion on the right part of the
string. We remember that the previous operation was a '*'. We arrive
on the limit of our expression (<code>limit</code> is now equal to 0), so we
stop, and send 2 to <code>myatoi</code> and we multiply the current value to
the return value of it, so we get 4. We are back to
<code>parseT_private</code>, and the current value is 4. The rest of the
recursion simply add 2 to it. And (finally) we get 6, as expected.
</li>
</ul>
<p>Now, let's develop a little one of the main function of the program,
<code>parseT_private</code>. First of all, why this dumb name? It is a toy
program, and I just wanted to differentiate it from parseT. So the
first idea that came to my mind was just fine. In <code>parseT_private</code>,
there are four different cases. The first one is:
</p>
<ul>
<li>
We are on a '+' or a '-', let's apply the previous operation which
was a '+' on the left part of the operator and run the recursion of
the right part.
</li>
<li>
We are on a '+' or a '-', let's apply the previous operation which
was a '-' on the left part of the operator and run the recursion of
the right part.
</li>
<li>
We are not in an operator, we continue to read the string. We
increase the size of the current substring.
</li>
<li>
We are arrived to the end. Let's do the last computation.
</li>
</ul>
<p>The code of <code>parseT_private</code> and <code>parseU_private</code> are very
similar. They just don't play at the same level (remember the BNF
grammar? These levels ;-) ). I found the code above quite elegant,
since it solves a problem not so simple, moreover at compile-time, and
it does it in less than 100 line of code. These functions just
represent the algorithm I have described in the first part of the
article with the constexpr constraints. Don't hesitate to ask question
in comments if you want more information about a precise part of the
code.
</p>
<p>
You may wonder "how to be sure that the result is computed at compile
time?". Two solutions: you can add a <code>static_assert</code> in the main, to
check if the result is the one you wanted, or you can use gdb. Let's
see how to use our debugger:
</p>
<pre class="src src-dot">$ g++ --std=c++0x -DEXPR=<span style="color: #cc9393;">"\"3+9-6+5-1+2-12+3*7+3\""</span> static_eval_expr.cc
$ ./a.out
24
$ gdb -q a.out
Reading symbols from a.out...(no debugging symbols found)...done.
(gdb) disassemble main
Dump of assembler code for function main:
0x080485f4 <+0>: push %ebp
0x080485f5 <+1>: mov %esp,%ebp
0x080485f7 <+3>: and $0xfffffff0,%esp
0x080485fa <+6>: sub $0x20,%esp
0x080485fd <+9>: movl $0x8048772,0x18(%esp)
0x08048605 <+17>: movl $0x18,0x1c(%esp)
0x0804860d <+25>: movl $0x18,0x4(%esp)
0x08048615 <+33>: movl $0x804a040,(%esp)
0x0804861c <+40>: call 0x80484c0 <<a href="mailto:_ZNSolsEi@plt">_ZNSolsEi@plt</a>>
0x08048621 <+45>: movl $0x8048530,0x4(%esp)
0x08048629 <+53>: mov %eax,(%esp)
0x0804862c <+56>: call 0x8048520 <<a href="mailto:_ZNSolsEPFRSoS_E@plt">_ZNSolsEPFRSoS_E@plt</a>>
0x08048631 <+61>: mov $0x0,%eax
0x08048636 <+66>: leave
0x08048637 <+67>: ret
End of assembler dump.
(gdb) q
$ echo $((0x18))
24
</pre>
<p>
Disassemble shows the assembler code for a function. If we analyze it,
we realize that there is no call to parseT. The two calls are due to
<code>std::cout</code> and <code>std::endl</code>. If we look at 0x18 (<+17> or <+25>), it
corresponds to 24, our result. So all has been computed a compile
time, and there is no run time cost. Great isn't?
</p>
</div>
</div>
</div>
<div id="outline-container-3" class="outline-2">
<h2 id="sec-3"><span class="section-number-2">3</span> Conclusion </h2>
<div class="outline-text-2" id="text-3">
<p>
I hope this example of how to use constexpr for making compile-time
programs. I don't say that you should make some programs like the one
I show in this post, but it can help the compiler to optimize your
programs by evaluating code at compile time instead of run time. It
also solves certain problem like <code>std::numeric_limits::max()</code> which is
a function representing a constant value. How to solve this problem?
Putting a <code>constexpr</code> qualifier on this function does the job.
</p>
<p>
The main aim of this post is to present <code>constexpr</code> to people that
didn't know it, to encourage people that have heard of it to take a
closer look at this new feature, and finally (at least for me) to see
how far I can go with constexpr.
</p>
<p>
I invite you to share your thoughts about <code>constexpr</code> or this post,
your questions or even your own experimentation in the comments!
</p></div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com3tag:blogger.com,1999:blog-6470854316396283720.post-74265549620026585902012-09-03T20:06:00.000+02:002012-09-03T20:06:24.473+02:00Customizing Zsh (Part 1): Hooks and RPrompt<body>
<div id="content">
<p>This post follows my post on the <a href="http://enki-tech.blogspot.fr/2012/08/zsh-macros.html">zsh macros</a>, and explain how to use
the zsh hooks "preexec", and how to customize your (right) prompt to
give information about something that changes (current branch of git,
date, …).
</p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> Preexec hook </h2>
<div class="outline-text-2" id="text-1">
<p>
To enable the hooks, the user first has to load the add-zsh-hook
function. To achieve that goal, paste the following line:
</p>
<pre class="src src-sh"><span style="color: #8cd0d3;">autoload</span> -U add-zsh-hook
</pre>
<p>
Once it is done, we are able to add and remove a function from a
hook. For our case, we suppose we want to add the <code>hook_function</code>
to the <code>preexec</code> hook. The following snippet shows how to do that.
</p>
<pre class="src src-sh"><span style="color: #f0dfaf;">hook_function</span>()
{
<span style="color: #8cd0d3;">echo</span> $<span style="color: #f0dfaf;">1</span>
<span style="color: #8cd0d3;">echo</span> $<span style="color: #f0dfaf;">2</span>
<span style="color: #8cd0d3;">echo</span> $<span style="color: #f0dfaf;">3</span>
}
add-zsh-hook preexec hook_function <span style="color: #708070;"># </span><span style="color: #7f9f7f;">Add it to the preexec hook.
</span><span style="color: #708070;"># </span><span style="color: #7f9f7f;">add-zsh-hook -d preexec hook_function # Remove it for this hook.
</span></pre>
<p>
Adding and removing a function from a hook is done the same way for
every hooks.
</p>
<p>
The preexec hook is ran each time a command is read by the shell and
is about to be executed.
</p>
<p>
Each function run by the preexec hook receives three arguments. The
first one is the line as it was written. The second line is the line
with alias expanded and truncated with a certain size limit. The third
line is the full line with alias expanded. This <a href="http://unix.derkeiler.com/Newsgroups/comp.unix.shell/2004-11/0732.html">thread</a> shows an
example. For the macros module, I decided to use the third expression
because I want to be able to use my aliases in my macros. But that
depends of the application you want to write.
</p>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> Interactive prompt </h2>
<div class="outline-text-2" id="text-2">
<p>
You know that, there is plenty of ways to customize your prompts in
Zsh. I'll just present one of them today, some post about the same
topic might follow.
</p>
<p>
What I present today is how to use your <code>RPROMPT</code> to print some
information about what you want, and is actualized every time you enter
a new command. It is easy to do, here is the first step:
</p>
<pre class="src src-sh"><span style="color: #8cd0d3;">setopt</span> prompt_subst
</pre>
<p>
Maybe you have recognized the beginning of what you have to add to
your configuration file to make the zsh macros module working? Well
done! Otherwise, it doesn't matter. So what does this little line?
According to the man (<a href="http://linux.die.net/man/1/zshoptions">man zshoptions</a>): "If set, parameter expansion,
command substitution and arithmetic expansion are performed in
prompts".
</p>
<p>
Let's see what happens if we don't set this option:
</p>
<pre class="src src-sh">$ <span style="color: #f0dfaf;">msg</span>=<span style="color: #cc9393;">"Hello"</span>
$ <span style="color: #f0dfaf;">RPROMPT</span>=<span style="color: #cc9393;">"($msg)"</span>
$ (Hello)
$ <span style="color: #f0dfaf;">msg</span>=<span style="color: #cc9393;">"Goodbye"</span> (Hello)
$ (Hello)
$ echo $<span style="color: #f0dfaf;">RPROMPT</span> (Hello)
(Hello)
$ (Hello)
</pre>
<p>
Pretty annoying right? In fact, the shell expands <code>$msg</code> before it is
received by <code>RPROMPT</code>, so what happens is simple, it prints the value of
what he receives: "Hello" literally. So, let's see what happens if we
re-execute the same sequence of commands with the <code>prompt_subst</code> option set?
</p>
<pre class="src src-sh">$ setopt prompt_subst
$ <span style="color: #f0dfaf;">msg</span>=<span style="color: #cc9393;">"Hello"</span>
$ <span style="color: #f0dfaf;">RPROMPT</span>=<span style="color: #cc9393;">"($msg)"</span>
$ (Hello)
$ <span style="color: #f0dfaf;">msg</span>=<span style="color: #cc9393;">"Goodbye"</span> (Hello)
$ (Hello)
$ echo $<span style="color: #f0dfaf;">RPROMPT</span> (Hello)
(Hello)
$ (Hello)
</pre>
<p>
Here is the most common error (I think) that leads your prompt not to expand your
variables. The <code>RPROMPT</code> command doesn't know there is a
variable to expand, and you have to prevent your shell to expand it by
single-quoting your assignation. This way:
</p>
<pre class="src src-sh">$ <span style="color: #f0dfaf;">RPROMPT</span>=<span style="color: #cc9393;">'($msg)'</span>
$ echo $<span style="color: #f0dfaf;">RPROMPT</span> (Hello)
($<span style="color: #f0dfaf;">msg</span>)
$ <span style="color: #f0dfaf;">msg</span>=<span style="color: #cc9393;">"Goodbye"</span> (Hello)
$ (Goodbye)
</pre>
<p>
There is two things to be careful with when you want to have your
prompt expanding some content: the option <code>prompt_subst</code> must be set,
and the content of the variable <code>RPROMPT</code> contains the thing you want
to be expanded each time (Think about single quoting it!).
</p>
<p>
Now let's see what we can do with it! If you are a module writer, you
can use a variable as flag (as I did), or give a function that allows
to get information about something (as it's done by zsh to allow user
to get vcs information).
</p>
<p>
For getting your branch in your <code>RPROMPT</code>, I recommend you to read <a href="http://stackoverflow.com/questions/1128496/to-get-a-prompt-which-indicates-git-branch-in-zsh">the answer of ko-dos</a> which is very complete. If you just paste the code,
it will work. But you know why it uses single quotes, and why there
must be the prompt_subst option set. For the zstyle part, I didn't try to
understand it. One day, I'll try :)
</p>
<p>
Let's see how get the time in your right prompt. First, how to get the
time only when calling the <code>date</code> command? I read <a href="http://www.cyberciti.biz/faq/linux-unix-formatting-dates-for-display/">this post</a> to find
the right format. It is just <code>date +%T</code>. Now let's apply what we have
learn:
</p>
<pre class="src src-sh">$ <span style="color: #f0dfaf;">RPROMPT</span>=<span style="color: #cc9393;">'$(date +%T)'</span>
$ (23:42:00)
</pre>
<p>
Now you are just limited by your needs and by your imagination :) If
you make your own custom prompt, please share it in comments. I hope
you like it!
</p></div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com2tag:blogger.com,1999:blog-6470854316396283720.post-29841437285442844672012-08-29T18:34:00.001+02:002012-09-02T11:03:47.618+02:00ZSH Macros<body>
<div id="content">
<p>Today, I'll present a module for zsh that I wrote few days ago. The
aim of this module is to provide a way to create easily
temporary shell scripts, and save their favorites. If you are familiar
with Emacs, and if you think about its macros, you're right! I designed
this with the macro concept in mind.
</p>
<p>
I had the idea when working with people who aren't familiar with
shell scripts, and who don't want to try it for helping them. The
original example was a work-flow with a TODO to update regularly.
And yet commands to do were not so difficult:
</p>
<pre class="src src-sh">$ git add TODO
$ git commit -m <span style="color: #cc9393;">"Update the TODO."</span>
$ git stash
$ git pull --rebase
$ git stash pop
$ git push
</pre>
<p>
In reality, my coworker didn't plan to stash nor pull, but since this
is my story, I can change it a little! :)
</p>
<p>
I thought that it is easy to write a script to make that works. I just
have to copy these lines and paste them in a script. But, on one hand
I find this boring, on the other hand someone who is not interested in
scripts will never do that. So I had to find a transparent way for the
user to have the same result without having the feeling that he plays
with scripts. It's here that came the idea to mimic the behavior of
the Emacs macros.
</p>
<p>
Notice that even if the Emacs macros works on text, and the title of
this post might be confusing, I don't want to write a tool to enhance
the Emacs macro in the Zsh command Line Editor (zle), but I want a way
to create simple scripts in a easy and fast way.
</p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> Zsh macros! </h2>
<div class="outline-text-2" id="text-1">
<p>
I first tried to create a Perl script that can create scripts, but I
realized that there is too many drawbacks (no history, no
completion…). So I found an alternative way, fully integrated in
zsh: hooks. For people who doesn't know what are hooks: It is a set of
functions called at a specific time that allow the user to run their
own functions. It is useful for letting the user personalizing a
software. As an example, I wrote a git hook to check the log message
(I talked about it in a <a href="http://www.enki-tech.blogspot.fr/2012/03/if-changelog-is-really-obsolete-how-to.html">previous post</a>). For this module, I use the
<code>preexec</code> hook for achieving my goal. In this post, I'll
present my module, why it can be useful for day-to-day usage, and how
to use it. In some next posts, I'll show some useful tricks I had to
use to make it works.
</p>
</div>
<div id="outline-container-1.1" class="outline-3">
<h3 id="sec-1.1"><span class="section-number-3">1.1</span> Why using it? </h3>
<div class="outline-text-3" id="text-1.1">
<p>
Because it allows you to save your time. It is easy to install, easy
to learn and easy to use. I realized that sometimes I repeat the same
sequence of lines several time. It ends up by having these lines
concatenated in one line with a <code>&&</code> between them. Pretty ugly, right?
But because it is just repeated less than ten times, I don't want to
write a script for that because it is faster for me to just reuse my
zsh history. But with this module, you just type your sequence of command
once, and then you just have to hit <code>macro_execute</code> to get it
repeated. Personally, I have aliased this command to <code>e</code>. It is the
fastest and cleanest way I know to repeat your work properly.
</p>
</div>
</div>
<div id="outline-container-1.2" class="outline-3">
<h3 id="sec-1.2"><span class="section-number-3">1.2</span> How to install it </h3>
<div class="outline-text-3" id="text-1.2">
<p>
Glad to see you here! You'll see that it is a good choice :) The first
step to install it is to get it from my <a href="#git@github.com:Enki-Prog/tools.git">github</a> (directory
zsh_macros). Once it is done, you just have to <code>source</code> the file, in
your shell to try it, or in your configuration file if you're sure
that it will fit to your needs.
</p>
<p>
Some things to check: if you have already bound either <code><ctrl-x><(></code>
or <code><ctrl-x><)></code>, I don't bind anything (I don't want to mess up your
own configuration!). These bindings are the same than under
Emacs. Feel free to adapt these bindings to your own wishes!
</p>
<p>
You then have to add something in your configuration file:
</p>
<pre class="src src-sh"><span style="color: #8cd0d3;">setopt</span> prompt_subst
<span style="color: #f0dfaf;">RPROMPT</span>=<span style="color: #cc9393;">'$(zmacros_info_wrapper)'</span>
</pre>
<p>
The first line allows the prompt to perform command substitution in
prompts. The second one set your RPROMPT to the value of
<code>zmacros_info_wrapper</code> that allows you to know the status of your macro.
If you have already assigned something to your RPROMPT, you could
simply add it to it.
</p>
<p>
Once this is done, everything should work fine. If this is not the
case, you can either send me a bug report or send me a patch. Now,
let's see how use this module.
</p>
</div>
</div>
<div id="outline-container-1.3" class="outline-3">
<h3 id="sec-1.3"><span class="section-number-3">1.3</span> How to use zsh macros? </h3>
<div class="outline-text-3" id="text-1.3">
<p>
In this part, I assume the bindings are the one originally
provided. I think a screenshot may help to figure out how it looks like, I
first run it in the shell, to show what you have to do, and what are
the result. Between <code><></code> are represent the keyboard macros. Do not
write it out :).
</p>
<pre class="src src-sh">$ echo foo
foo
$ <ctrl-x><(> echo bar
bar
$ echo baz
baz
$ <ctrl-x><)> e
bar
baz
</pre>
<p>
This screenshot shows how it appears for the user:
</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgNdnAhCjGUb6IuZLCNlbnMIdKQJlhCtg3IqIyv4ogDasrrk0Bgn9rs0N07n4DM5z1FbIrAnivJxmi52e5yEaVy5kZDV65HTCPV8luM3OPcNV-OUFETm-JajkG-v-hvX-kq0x_ISexlAHI/s1600/macros.jpg" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="176" width="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgNdnAhCjGUb6IuZLCNlbnMIdKQJlhCtg3IqIyv4ogDasrrk0Bgn9rs0N07n4DM5z1FbIrAnivJxmi52e5yEaVy5kZDV65HTCPV8luM3OPcNV-OUFETm-JajkG-v-hvX-kq0x_ISexlAHI/s400/macros.jpg" /></a></div>
<p>
The flag on the right (<code><R$id></code>) appears right after you type
<ctrl-x><(>, and disappear right after you type <ctrl-x><)>.
Pretty easy right?
</p>
<p>
Note that if you don't like key-bindings (Are you a Vim user?), you
can call <code>macro-record</code> and <code>macro-end</code> and you'll get the same
effects.
</p>
<p>
Let's go a little deeper: you can have several macro. This module
doesn't support nested macros in a same shell, but you can make as
many macros as you want. Each macro is associated with an id. This is
what is printed on the flag after the <code>R</code> in the prompt. You can run
<code>macro-execute</code> with an optional argument that corresponds to the id
of the macro you want to run. By default it's the last
recorded. Notice that each script has its own file, and there is a
master file that track each of them. To add and execute macros, we
read and write on this file in /tmp. This way has its advantages and its
drawbacks. We have concurrency problems, but since a real user can't
make several things in the same time, that should not be a real
problem.
</p>
<p>
The advantages are that a macro recorded in a shell can be used in
another one, and you can register two macros at the same time, because
the only access to the main file is made when you call <code>macro-record</code>. So recording two macros in two different shells is fine.
</p>
<p>
All your scripts live as long as your /tmp is not cleaned. If you want
to keep a macro for a longer use, it is possible. You just have to
call macro-name that will take the macro you asked for (if you give no
id, the last one is considered), and copy it in the directory
<code>ZMACROS_DIRECTORY</code>. You can set it at the top of the file
<code>macros.zsh</code>. Maybe it is a good idea to add this directory to your
path, it will allow you call these new functions simply.
</p>
<p>
This is the features available in this first version of the zsh
macros. I planned to add some new ones, but if you have any request,
comment, or anything, feel free to comment this post! I'd like to know
what would be helpful and what you think about this module.
</p></div>
</div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com0tag:blogger.com,1999:blog-6470854316396283720.post-83308419036977260462012-08-22T17:38:00.000+02:002012-08-31T13:17:15.026+02:00C++11: A generic Singleton<body>
<div id="content">
<!-- <h1 class="title">generic<sub>singleton</sub></h1> -->
<!-- <div id="table-of-contents"> -->
<!-- <h2>Table of Contents</h2> -->
<!-- <div id="text-table-of-contents"> -->
<!-- <ul> -->
<!-- <li><a href="#sec-1">1 Introduction </a></li> -->
<!-- <li><a href="#sec-2">2 First Try </a></li> -->
<!-- <li><a href="#sec-3">3 The Solution </a></li> -->
<!-- </ul> -->
<!-- </div> -->
<!-- </div> -->
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> Context </h2>
<div class="outline-text-2" id="text-1">
<p>
Yesterday, I found the solution to a problem that I was unable to
solve one year ago. The problem was simple: Creating a generic
Singleton. If you don't know what a Singleton is, here is the
definition given in the book "Design Pattern" from the Gamma et al.:
"Ensure a class only has one instance, and provide a global point of
access to it".
</p>
<p>
I wanted to have a generic singleton because I had to code several
singletons in several projects and I <b>hate</b> making the same thing
several times. I was unable to succeed in my tries
because of the initialization problem. There was no known method to
handle the initialization that works for each possible constructors.
</p>
<p>
A perfect way to change a class into a Singleton would be, in my
opinion, something like just inheriting from a base class
Singleton. That would be awesome! But I don't think anyone has ever
succeed. The best discussion about a generic Singleton I have read is
in the Andrei Alexandrescu's <a href="http://www.amazon.com/Modern-Design-Generic-Programming-Patterns/dp/0201704315">book</a> (If you know a better stuff about it,
please let me know!). It notably talks about the deletion problem,
that is not approached in this article. I just focus on the
construction that can be improved thanks to C++11.
</p>
<p>
The common version is to use the Curiously Recurring Template Pattern
(CRTP). So let's start by introducing the CRTP. The concept is simple,
we inherit from a template class that takes us as parameter. It allows
to make static polymorphism or instance counter… <a href="http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern">Wikipedia</a> may help
for these examples.
</p>
<p>
I had to say that when I discovered this thing I was amazed. I am
passionated by the concept of the template, by the language in the
language. One year ago I tried to solve the Singleton with a CRTP
(which is the solution used in the C++ Modern Design book), and my
specifications was the original one, and I had to call a
method "destroySingleton" at the end of my programs. So I have to
find a generic constructor that works for all of my Singleton classes
and the work is done.
</p>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> First Try </h2>
<div class="outline-text-2" id="text-2">
<p>
At the beginning, when I had only two classes and two constructors, I
though to play on the fact that the template functions not used are
not instantiated, so they can be incorrect (no type checking, no name
binding… It just must be valid syntactically). Here is an example:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><string></span>
<span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>>
<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">Singleton</span>
{
<span style="color: #f0dfaf; font-weight: bold;">public</span>:
<span style="color: #f0dfaf; font-weight: bold;">static</span>
<span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #f0dfaf;">get_instance</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">v</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">if</span> (<span style="color: #f0dfaf; font-weight: bold;">!</span>instance_)
instance_ = <span style="color: #f0dfaf; font-weight: bold;">new</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>(v);
<span style="color: #f0dfaf; font-weight: bold;">return</span> instance_;
}
<span style="color: #f0dfaf; font-weight: bold;">static</span>
<span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #f0dfaf;">get_instance</span>(<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">string</span> <span style="color: #f0dfaf;">s</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">if</span> (<span style="color: #f0dfaf; font-weight: bold;">!</span>instance_)
instance_ = <span style="color: #f0dfaf; font-weight: bold;">new</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>(s);
<span style="color: #f0dfaf; font-weight: bold;">return</span> instance_;
} <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Sounds familiar...
</span>
<span style="color: #f0dfaf; font-weight: bold;">static</span>
<span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">destroy_instance</span>()
{
<span style="color: #f0dfaf; font-weight: bold;">delete</span> instance_;
instance_ = nullptr;
}
<span style="color: #f0dfaf; font-weight: bold;">private</span>:
<span style="color: #f0dfaf; font-weight: bold;">static</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #f0dfaf;">instance_</span>;
};
<span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>> <span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #dca3a3; font-weight: bold;">Singleton</span><<span style="color: #dfdfbf; font-weight: bold;">T</span>>::<span style="color: #f0dfaf;">instance_</span> = nullptr;
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">The classes that will be singletons:
</span>
<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">Single</span>: <span style="color: #f0dfaf; font-weight: bold;">public</span> <span style="color: #dfdfbf; font-weight: bold;">Singleton</span><<span style="color: #dfdfbf; font-weight: bold;">Single</span>>
{
<span style="color: #f0dfaf; font-weight: bold;">public</span>:
<span style="color: #f0dfaf;">Single</span>(<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">string</span> <span style="color: #f0dfaf;">s</span>): s_(s) {}
<span style="color: #f0dfaf; font-weight: bold;">private</span>:
<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">string</span> <span style="color: #f0dfaf;">s_</span>;
};
<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">Map</span>: <span style="color: #f0dfaf; font-weight: bold;">public</span> <span style="color: #dfdfbf; font-weight: bold;">Singleton</span><<span style="color: #dfdfbf; font-weight: bold;">Map</span>>
{
<span style="color: #f0dfaf; font-weight: bold;">public</span>:
<span style="color: #f0dfaf;">Map</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">scale</span>): scale_(scale) {}
<span style="color: #f0dfaf; font-weight: bold;">private</span>:
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">scale_</span>;
};
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">How to create and destroy them:
</span>
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">Single</span>* <span style="color: #f0dfaf;">s</span> = <span style="color: #dca3a3; font-weight: bold;">Single</span>::get_instance(<span style="color: #cc9393;">"Forever Alone"</span>);
<span style="color: #dfdfbf; font-weight: bold;">Map</span>* <span style="color: #f0dfaf;">m</span> = <span style="color: #dca3a3; font-weight: bold;">Map</span>::get_instance(42);
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">Use these singletons.
</span>
<span style="color: #dca3a3; font-weight: bold;">Map</span>::destroy_instance();
<span style="color: #dca3a3; font-weight: bold;">Single</span>::destroy_instance();
}
</pre>
<p>
When we instantiate <code>Singleton<Single></code> there is no
constructor that takes an int (so the first <code>get_instance</code> is incorrect), and the program still compiles
successfully. This is because the function is not called, so not
instantiated, so there is no reason to wine for g++.
</p>
<p>
This version respects one half of the deal to have a singleton, but it
is totally non-intrusive in the code of the classes transformed into
singleton. To respect the second half ("only one instance"), we have
to tweak a little. We have to make the constructors of the derived
classes private, and to grant the friendship to the mother class. As a
reminder, the <code>friend</code> keyword allows to give access to
all of the protected/private methods to the friend class. This way, no
user can create directly an object of the derived class, and we respect the
specifications.
</p>
<p>
Now we respect the two part, but we are still unhappy with this. In
fact, we have only two classes, and we had to create two
<code>get_instance</code>, because we have two different
constructors. Since the number of possible combination of arguments to
give to the constructor of an object is infinite, our solution isn't suitable. And that's
where I was stuck.
</p>
</div>
</div>
<div id="outline-container-3" class="outline-2">
<h2 id="sec-3"><span class="section-number-2">3</span> The Solution </h2>
<div class="outline-text-2" id="text-3">
<p>
And yesterday, I finally realized that the solution was just in one of
my previous post about the <a href="http://enki-tech.blogspot.fr/2012/08/c11-vector-improved-how-it-works.html">C++11 mechanisms</a> that allows to create
<code>emplace_back</code>. The solution was the perfect forwarding!
In fact, we just have to create a <code>get_instance</code> that
forwards the arguments to the constructor. No repetition, fully
generic. That's what I wanted to reach! Here is the final version of
the Singleton class:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><iostream></span>
<span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>>
<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">Singleton</span>
{
<span style="color: #f0dfaf; font-weight: bold;">public</span>:
<span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #f0dfaf; font-weight: bold;">typename</span>... Args>
<span style="color: #f0dfaf; font-weight: bold;">static</span>
<span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #f0dfaf;">get_instance</span>(<span style="color: #dfdfbf; font-weight: bold;">Args</span>... <span style="color: #f0dfaf;">args</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">if</span> (<span style="color: #f0dfaf; font-weight: bold;">!</span>instance_)
{
instance_ = <span style="color: #f0dfaf; font-weight: bold;">new</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>(<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">forward</span><<span style="color: #dfdfbf; font-weight: bold;">Args</span>>(args)...);
}
<span style="color: #f0dfaf; font-weight: bold;">return</span> instance_;
}
<span style="color: #f0dfaf; font-weight: bold;">static</span>
<span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">destroy_instance</span>()
{
<span style="color: #f0dfaf; font-weight: bold;">delete</span> instance_;
instance_ = nullptr;
}
<span style="color: #f0dfaf; font-weight: bold;">private</span>:
<span style="color: #f0dfaf; font-weight: bold;">static</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #f0dfaf;">instance_</span>;
};
<span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">T</span>> <span style="color: #dfdfbf; font-weight: bold;">T</span>* <span style="color: #dca3a3; font-weight: bold;">Singleton</span><<span style="color: #dfdfbf; font-weight: bold;">T</span>>::<span style="color: #f0dfaf;">instance_</span> = nullptr;
<span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">Map</span>: <span style="color: #f0dfaf; font-weight: bold;">public</span> <span style="color: #dfdfbf; font-weight: bold;">Singleton</span><<span style="color: #dfdfbf; font-weight: bold;">Map</span>>
{
<span style="color: #f0dfaf; font-weight: bold;">friend</span> <span style="color: #f0dfaf; font-weight: bold;">class</span> <span style="color: #dfdfbf; font-weight: bold;">Singleton</span><<span style="color: #dfdfbf; font-weight: bold;">Map</span>>;
<span style="color: #f0dfaf; font-weight: bold;">private</span>:
<span style="color: #f0dfaf;">Map</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">size_x</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">size_y</span>): size_x_{size_x}, size_y_{size_y} {}
<span style="color: #f0dfaf; font-weight: bold;">public</span>:
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">size_x_</span>;
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">size_y_</span>;
};
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">Map</span>* <span style="color: #f0dfaf;">m</span> = <span style="color: #dca3a3; font-weight: bold;">Map</span>::get_instance(4, 5);
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << m->size_y_ << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl; <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Outputs 5.
</span>
<span style="color: #dca3a3; font-weight: bold;">Map</span>::destroy_instance();
}
</pre>
<p>
As said above, we are not interested in the destruction problem. It is
well-covered in the Alexandrescu's book, and I <b>recommend</b> you to read
it if you want to see more on the subject. We create a
<code>destroy_instance</code> method in the aim to do not leak our
instance. The user must call it at the end of the program.
</p>
<p>
The real novelty of this, is the use of <code>std::forward</code>
when creating the object. So we can give to it any class, and it will
work. I take the example of a Map (for example for a game) which takes
two arguments, but I hope it is clear for everyone that it works with
any constructors.
</p>
<p>
Note that, I didn't write the copy and move constructors private, but
they should be. I omit them only to gain some space in my post. For the same reason, I didn't write the class Single in the second example. But it is clear that it works.
</p>
<p>
Before concluding, I just want to show that the use of the
metaprogramming here doesn't lead to a hideous error message by our
compiler when not used correctly. Let's assume that we replace the call to
<code>get_instance</code> with two arguments, by a call with no
arguments. What happens? Here is the answer of g++ (4.6.1):
</p>
<pre class="src src-dot">singleton.cc: In static member function 'static T* \
Singleton<T>::get_instance(Args ...) [with Args = {}, T = Map]':
singleton.cc:53:30: instantiated from here
singleton.cc:16:9: erreur: no matching function for call to 'Map::Map()'
singleton.cc:16:9: note: candidates are:
singleton.cc:40:3: note: Map::Map(int, int)
singleton.cc:40:3: note: candidate expects 2 arguments, 0 provided
singleton.cc:35:7: note: constexpr Map::Map(const Map&)
singleton.cc:35:7: note: candidate expects 1 argument, 0 provided
singleton.cc:35:7: note: constexpr Map::Map(Map&&)
singleton.cc:35:7: note: candidate expects 1 argument, 0 provided
</pre>
<p>
The message is clear, and there is all the information needed to
understand it, and to fix our mistake.
</p>
<p>
In this post I proposed the use of <code>std::forward</code> for
building a generic singleton. I don't talk the deletion problem because
for my personal use, I accept to call the destroy method.
</p>
<p>
But this is just one example to show how the C++11 can help
programmers to build new things easily. I hope my article motivates
you to experiment new things! Feel free to share your opinion in comments :-)
</p>
<p>
PS: I just realize that my current solution isn't perfect. In fact, we can't get the instance without giving a valid argument list (valid = there is a constructor that takes this list). So a call to <code>get_instance</code> without argument, which should return the instance leads to an error if there is no constructor that takes no argument. This is not really what we want. A fix would be to separate the initialization and the <code>get_instance</code>. But that doesn't invalidate what I wanted to demonstrate. So it's okay :)
</p>
</div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com14tag:blogger.com,1999:blog-6470854316396283720.post-9165071028446450422012-08-16T17:59:00.000+02:002012-08-16T17:59:37.088+02:00A wonderful internship<body>
<div id="content">
<p>Today I talk about the internship I made from the middle of October (2011)
to the middle of January (2012). I'll start by presenting a little the
context, and what I have done exactly.
</p>
<p>
I worked at <a href="http://www.aldebaran-robotics.com/en/">Aldebaran Robotics</a> on NAO. The goal of my internship was
to refactor a blob of code that allows NAO to recharging himself by
going to its station. The behavior was developed in Python, and my
goal was to build the same thing in C++. Here is the video that shows
this behavior:
</p>
<p>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="270" src="http://www.youtube.com/embed/0xHaxTM7KH8?fs=1" width="480"></iframe></div>
</p>
<p>
Pretty cool right? You can guess how excited I was to attack a project
like this, and I start by analyzing the existing program to understand
what are the keys to make it works in C++. And then, we (my supervisor
and I) realized that we could build a better framework to track one or
several object(s). We designed an architecture (what are the
modules and their responsibilities), and (because my supervisor was
great) I was responsible of the <b>whole</b> architecture: what are the
objects, how they interact, etc. I develop all by myself and building
a set of libraries that allows the user to build a tracker. The aim of
the whole project was to being able to propose a set of tracker (a red
ball tracker, an Aldebaran logo tracker, …) with as less duplication
as possible, and we also wanted to let the user create its own kind of
tracker by adding its own little brick of software. This was a success
since one of my supervisor developed a face tracker in 20 minutes and
160 lines of code. I created a tool able to track one or two
objects. When working with one object, NAO was able to follow an
object with its head, or its whole body and staying at a given
distance of the object. When there is two objects he is able to go to
an exact position in a repair defined by the center of the two
objects. A good tracker is also able to detect when it losts its
target. Our tool starts by looking at the last place he saw it.
</p>
<p>
I think it is better if I don't go too much in details about this
project since I don't owe its right. But here is what it looks like in
video (yes I have asked for the rights for that :P).
</p>
<p>
In the first part of the video, I show the search of a red ball, and
how it finds and follows it.
</p>
<p>
In the second part, it tracks the (kind of) pie-charts on the box, and
go to the left red cross on the floor. He doesn't look at the floor,
the red cross is just for us to see that it goes where we asked for!
</p>
<p>
And the last part was a reproduction of the charging station, just for
seeing that we are able to reproduce it with my work. You'll see that
it seems to stop. In fact he does because he reaches the first target,
and I had to run through my computer to tell him to go to the second!
</p>
<p>
No more suspense, let's look at the video!
</p>
<p>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="270" src="http://www.youtube.com/embed/UnT02Qqif1E?fs=1" width="480"></iframe></div>
</p>
<p>
I feel like some personages in cartoons because you see my hand, my
foot, my body, but never my head :-P
</p>
<p>
Feel free to ask if you have any questions about that, I'll be happy to answer.
</p>
</div>
</body>
Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com2tag:blogger.com,1999:blog-6470854316396283720.post-84271836239527554682012-08-14T17:32:00.000+02:002012-08-14T17:33:39.182+02:00Debugging C++ (Part 4): A print method<body>
<div id="content">
<p>And here is the last post of this series about debugging C++. In this one, I develop a good way to use prints for debugging. The main
drawback of the prints is that it is hard to maintain. The presented
method doesn't have this problem.
</p>
<p>
I use prints sometimes, when valgrind tells me nothing, and that I
can't run gdb for any reason (for example, I use opaque data structure
and all the information gdb is able to give is "root node =
2"… Nice! It happens when I work with BDD (Binary Decision Diagram,
I think I'll talk about it in the future)). This method works in C++,
and is inspired of three things. I'll start by describing these
things, and then I show the whole thing.
</p>
<p>
Akim Demaille, one of my teacher, gave me the base of this method. It consists in
using macro to print. Here is the thing:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">ECHO</span>(<span style="color: #f0dfaf;">content</span>) <span style="color: #dca3a3; font-weight: bold;">std</span>::cerr << content << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">VAR</span>(<span style="color: #f0dfaf;">v</span>) <span style="color: #cc9393;">"`"</span> #v <span style="color: #cc9393;">"': "</span> << v
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">argc</span>, <span style="color: #dfdfbf; font-weight: bold;">char</span> *<span style="color: #f0dfaf;">argv</span>[])
{
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 42;
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">j</span> = 51;
ECHO(VAR(i) << <span style="color: #cc9393;">" - "</span> << VAR(j)); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Outputs "`i': 42 - `j': 51"
</span>}
</pre>
<p>
I add quote _`'_ to see what happens when I want to see the result of
an operation (<code>i + j</code> for example). Now, let's see how it
works. In C or C++, you can make a concatenation by just putting two
quoted things side by side. As an example this snippets
</p>
<pre class="src src-c++"><span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"42 "</span> <span style="color: #cc9393;">"is "</span> <span style="color: #cc9393;">"the "</span> <span style="color: #cc9393;">"answer."</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
</pre>
<p>
outputs "42 is the answer.". These method also relies on the
<a href="http://gcc.gnu.org/onlinedocs/cpp/Stringification.html">stringification</a>. The operator # put in front of a variable in a macro
quotes it. It allows to make this. The macro VAR takes a variable, and
returns its name quoted, and its value ready for being printed to
<code>std::cerr</code>. And ECHO just print it followed by a newline.
</p>
<p>
Looks simple when you see it, but I found it ingenious. I remember
myself making this job by hand so much time… I think this was very
cool and a sane base to build something better!
</p>
<p>
We had a discussion with a friend of mine (Guillaume Delahodde) about
a way to decide whether print a thing or not when we want to debug or
not without any run-time overhead. And the result of this discussion
was a macro that decides to execute the code or not:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#if</span><span style="color: #8cd0d3; font-weight: bold;">n</span><span style="color: #8cd0d3;">def</span> NDEBUG
<span style="color: #8cd0d3;"># define</span> <span style="color: #f0dfaf;">LINE</span>(<span style="color: #f0dfaf;">content</span>) content
<span style="color: #8cd0d3;">#else</span>
<span style="color: #8cd0d3;"># define</span> <span style="color: #f0dfaf;">LINE</span>(<span style="color: #f0dfaf;">content</span>)
<span style="color: #8cd0d3;">#endif</span>
</pre>
<p>
I already talk about <code>NDEBUG</code> in the <a href="http://enki-tech.blogspot.fr/2012/08/debugging-c-part-1-how-to-write-less.html">first post of this series</a> about simple methods to avoid creating stupid bug, so I assume
it is clear why it appears here. The usage of this is simple, put your
print code inside <code>LINE</code> and it will be printed only in
debug mode. So we just have to change the definition of
<code>ECHO</code> a little, and it will only print on debug mode.
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">ECHO</span>(<span style="color: #f0dfaf;">content</span>) LINE(<span style="color: #dca3a3; font-weight: bold;">std</span>::cerr << content << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl)
</pre>
<p>
Now our prints are only here in debug mode, and it is better than
before. We could have stop here, but we could enhance the comfort of
the user. I think writing <code>VAR(i) << " - " << VAR(j)</code> very
annoying. It corresponds to 25 characters, and I think this is too
much. I had the occasion to read the book of <a href="http://www.amazon.com/Modern-Design-Generic-Programming-Patterns/dp/0201704315">Andrei Alexandrescu</a>
(Modern C++ Design), and in there it uses a set of macros to add
syntactic sugar for the user. It is hand written macros that threat
the first argument and call the macro that threats n-1 arguments
until 1. I call this macro LVN with N the number of argument. I just
wrote it for 2, 3 and 4 arguments since they are the more
common. Let's see how it looks like:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">LV2</span>(<span style="color: #f0dfaf;">first</span>, <span style="color: #f0dfaf;">second</span>) VAR(first) << <span style="color: #cc9393;">" - "</span> << VAR(second)
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">LV3</span>(<span style="color: #f0dfaf;">first</span>, <span style="color: #f0dfaf;">second</span>, <span style="color: #f0dfaf;">third</span>) VAR(first) << <span style="color: #cc9393;">" - "</span> << LV2(second, third)
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">LV4</span>(<span style="color: #f0dfaf;">first</span>, <span style="color: #f0dfaf;">second</span>, <span style="color: #f0dfaf;">third</span>, <span style="color: #f0dfaf;">fourth</span>) \
VAR(first) << <span style="color: #cc9393;">" - "</span> << LV3(second, third, fourth)
</pre>
<p>
And now we are able to replace our 25 characters to print 2 variables
into: <code>LV2(i, j)</code>. Much better right? Let's see the whole
thing in an example:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><iostream></span>
<span style="color: #8cd0d3;">#if</span><span style="color: #8cd0d3; font-weight: bold;">n</span><span style="color: #8cd0d3;">def</span> NDEBUG
<span style="color: #8cd0d3;"># define</span> <span style="color: #f0dfaf;">LINE</span>(<span style="color: #f0dfaf;">line</span>) line
<span style="color: #8cd0d3;">#else</span>
<span style="color: #8cd0d3;"># define</span> <span style="color: #f0dfaf;">LINE</span>(<span style="color: #f0dfaf;">line</span>)
<span style="color: #8cd0d3;">#endif</span>
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">ECHO</span>(<span style="color: #f0dfaf;">content</span>) LINE(<span style="color: #dca3a3; font-weight: bold;">std</span>::cerr << content << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl)
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">VAR</span>(<span style="color: #f0dfaf;">v</span>) <span style="color: #cc9393;">"`"</span> #v <span style="color: #cc9393;">"': "</span> << v
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">LV2</span>(<span style="color: #f0dfaf;">first</span>, <span style="color: #f0dfaf;">second</span>) VAR(first) << <span style="color: #cc9393;">" - "</span> << VAR(second)
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">LV3</span>(<span style="color: #f0dfaf;">first</span>, <span style="color: #f0dfaf;">second</span>, <span style="color: #f0dfaf;">third</span>) VAR(first) << <span style="color: #cc9393;">" - "</span> << LV2(second, third)
<span style="color: #8cd0d3;">#define</span> <span style="color: #f0dfaf;">LV4</span>(<span style="color: #f0dfaf;">first</span>, <span style="color: #f0dfaf;">second</span>, <span style="color: #f0dfaf;">third</span>, <span style="color: #f0dfaf;">fourth</span>) \
VAR(first) << <span style="color: #cc9393;">" - "</span> << LV3(second, third, fourth)
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">argc</span>, <span style="color: #dfdfbf; font-weight: bold;">char</span> *<span style="color: #f0dfaf;">argv</span>[])
{
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 4;
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">j</span> = 51;
<span style="color: #dca3a3; font-weight: bold;">std</span>::cerr << <span style="color: #cc9393;">"`i': "</span> << i << <span style="color: #cc9393;">" - "</span> << <span style="color: #cc9393;">" `j': "</span> << j << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">Outputs the same thing as the following methods in a worse way.
</span> ECHO(VAR(i) << <span style="color: #cc9393;">" - "</span> << VAR(j)); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Still outputs "`i': 42 - `j': 51"
</span> ECHO(LV2(i, j)); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Also outputs "`i': 42 - `j': 51"
</span>}
</pre>
<p>
The first print has the drawback to be boring to maintain. If you go
to the release mode you have to track all of these prints and remove
them, if you change the name of a variable you have to change it twice
(assuming you're not using a perfect refactoring tool), and it is
longer to write. The last version is simple to write, you don't have
to haunt it to prevent them from printing, and they introduces no
overhead in release mode. We are far from the dummy <code>printf</code> method, and
it is cool.
</p>
<p>
The moral of this series is that there is a lot of debugging methods, and
you have to know them for being able to adapt your method to the
situation. For example, <code>dmesg</code> is very specific, but the other method
were very hard to use in these situations.
</p>
<p>
I invite you to share yours in the comments. I'm sure that there is a
lot of other method out there, just waiting for being learned!
</p>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com6tag:blogger.com,1999:blog-6470854316396283720.post-56109171141466675062012-08-12T17:04:00.001+02:002012-08-13T09:38:08.470+02:00Debugging C++ (Part 3): dmesg<body>
<div id="content">
<p>Welcome in the third post of this series about debugging C++. In here, I will talk about something less usual because it allows to debug
after the crash of the program, this method use <code>dmesg</code>. I
just present the case where we work with several libraries and your
program crashes without any clue on which library is responsible of
this, nor how to reproduce this behavior.
</p>
<div id="outline-container-1" class="outline-3">
<h3 id="sec-1"><span class="section-number-3">1</span> dmesg </h3>
<div class="outline-text-3" id="text-1">
<p>
I heard about <code>dmesg</code> when reading the <a href="http://blog.tsunanet.net/2011/05/jvm-u24-segfault-in-clearerr-on-jaunty.html">tsuna's blog</a>. Unfortunately I
don't have any competence (for now) for reading assembler. But the fact
that we can discover the name of the faulty function is helpful. I had
to use this when I worked on a robot during my internship (a next post
will present that). We worked with libraries and this is what shows my
post.
</p>
<p>
On a robot there is a lot of parameters coming from the miscellaneous
sensors, and the execution of the same program depends on a lot of
parameters. So it is really hard to reproduce a bug. If the nice
"segmentation fault" message appears, how can you debug that?
Considering that you can't run valgrind, and running gdb is
painful.
</p>
<p>
<code>dmesg</code> was my solution. I wrote a shell script to make the
computation for me. Let's start by creating a dummy library which
exports one function that segfault if a null pointer is given, and
let be sadistic, we will call it with <code>nullptr</code>.
</p>
<pre class="src src-c++"><span style="color: #708070;">// </span><span style="color: #7f9f7f;">file: libprint.hh
</span><span style="color: #8cd0d3;">#if</span><span style="color: #8cd0d3; font-weight: bold;">n</span><span style="color: #8cd0d3;">def</span> TMP_LIBPRINT_HH_
<span style="color: #8cd0d3;"># define</span> <span style="color: #f0dfaf;">TMP_LIBPRINT_HH_</span>
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">dereference</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span>* <span style="color: #f0dfaf;">t</span>);
<span style="color: #8cd0d3;">#endif</span> <span style="color: #708070;">// </span><span style="color: #7f9f7f;">!TMP_LIBPRINT_HH_
</span>
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">file: libprint.cc
</span><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;">"libprint.hh"</span>
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">dereference</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span>* <span style="color: #f0dfaf;">t</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> *t;
}
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">file: main.cc
</span><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;">"libprint.hh"</span>
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> dereference(nullptr);
}
</pre>
<p>
We create a <code>libprint.so</code> that contains the
<code>dereference</code> function. And we compile the file main into a
binary <code>print</code> linked with this library. And oh, surprise!
Segmentation fault. Let's start the hunting. We call dmesg, and look
at the last line:
</p>
<p>
<code>[184608.332284] print[31332]: segfault at 0 ip b772e422 sp bf8ad218 error 4 in libprint.so[b772e000+1000]</code>
</p>
<p>
We need two information: the name of the library that contains the
bug, and the address of the faulty instruction in this library. To get
the name of the library, we have to take the last field and to remove
the part into <code>[]</code>. To have the address of the faulty
instruction we have to take the value of the instruction pointer (ip),
and the value before the <code>+</code> in the last field. And we just
have to subtract the value of the second value to the value of ip. If
you are wondering why subtracting these two values to know the address
of the ip in the library a draw may help.
</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhxsPinOadtdbj-raJFpLhF11H6YgmCEX0T4WEe6tvJWYvQdAaPqXPNKScE89MZdlPMiIfy6tfrQHJY9k3oRh6-UNBEhZZkQ9EP7axrLcxJchRPoRpt-U0dOseVwx96pClDBa2BRRVPDOI/s1600/dmesg.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="137" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhxsPinOadtdbj-raJFpLhF11H6YgmCEX0T4WEe6tvJWYvQdAaPqXPNKScE89MZdlPMiIfy6tfrQHJY9k3oRh6-UNBEhZZkQ9EP7axrLcxJchRPoRpt-U0dOseVwx96pClDBa2BRRVPDOI/s320/dmesg.png" /></a></div>
<p>
I hope the picture helped, in fact, this subtraction removes the
offset corresponding to the position of the library (address).
</p>
<p>
The question is how to make this process automatically? First, we can
make the assumption that we always run dmesg right after the error,
so we can suppose that we can make a call to <code>tail</code> to
keep only the last line. But sometimes this assumption isn't correct,
so our solution must be able to get a value given in argument. In here
we use the shell default value assignment. As a little remainder:
</p>
<pre class="src src-sh"><span style="color: #f0dfaf;">output</span>=$<span style="color: #f0dfaf;">1</span>
<span style="color: #f0dfaf;">output</span>=${<span style="color: #f0dfaf;">output</span>:=<span style="color: #cc9393;">"default value"</span>}
</pre>
<p>
If an argument is given, output will be equal to its value, otherwise
it will be equal to "default value". So we can use it to decide
whether we use the first argument of the program or directly call
dmesg.
</p>
<p>
The part of the message before the colon is useless, so we can remove
it. Then we have to get the value of the fifth field to get the value
associated to ip, and we have to get the last field.
</p>
<p>
The name of the library and the address where it is mapped in the
memory lie in the last field. So we have to cut it in two and we can
get the needed information.
</p>
<p>
All these operations can be made by using only awk and sed.
</p>
<p>
Once we have the two addresses we just have to make the operation. We
use the builtin system of the shell to make the subtract. Beware, they
are in hexadecimal! So we must prefix the value by <code>0x</code> to
tell the base to the shell. Now we have the result (in decimal), we
want it converted into hexadecimal, we use <a href="http://www.gnu.org/software/bc/">bc</a>. It is a tool for making
numeric computations. And we are grateful, there is a way to make it
convert a number from a base to another. The syntax is simple, you
have to set the variable <code>obase</code> to 16 (default value is
10). And that's all, remember to append the 0x before the address,
because bc won't.
</p>
<p>
Here is the complete script:
</p>
<pre class="src src-sh"><span style="color: #708070;">#</span><span style="color: #7f9f7f;">! /bin/</span><span style="color: #f0dfaf; font-weight: bold;">sh</span><span style="color: #7f9f7f;">
</span>
<span style="color: #f0dfaf;">output</span>=$<span style="color: #f0dfaf;">1</span>
<span style="color: #f0dfaf;">output</span>=${<span style="color: #f0dfaf;">output</span>:=<span style="color: #fa8072;">`dmesg | tail -1`</span>}
<span style="color: #f0dfaf;">output</span>=<span style="color: #fa8072;">`echo $output | sed -e 's/.*: //'`</span>
<span style="color: #f0dfaf;">first</span>=<span style="color: #fa8072;">`echo $output | awk '{ print $5; }'`</span>
<span style="color: #f0dfaf;">second</span>=<span style="color: #fa8072;">`echo $output | awk '{print $11; }'`</span>
<span style="color: #f0dfaf;">library</span>=<span style="color: #fa8072;">`echo $second | sed -e 's/\[.*//'`</span>
<span style="color: #f0dfaf;">second</span>=<span style="color: #fa8072;">`echo $second | sed -e 's/.*\[//' -e 's/\+.*//'`</span>
<span style="color: #f0dfaf;">address</span>=<span style="color: #fa8072;">`echo $((0x$first - 0x$second))`</span>
<span style="color: #f0dfaf;">address</span>=<span style="color: #fa8072;">`echo "obase=16; $address" | bc`</span>
<span style="color: #8cd0d3;">echo</span> <span style="color: #cc9393;">"Segmentation fault in $library at: 0x$address."</span>
</pre>
<p>
And the way to use it is simple, just run it just after a segmentation
fault when working with a library. Here is what it says about our case.
</p>
<pre class="src src-sh">$ ./dmesg.sh
Segmentation fault<span style="color: #f0dfaf; font-weight: bold;"> in</span> libprint.so at: 0x422.
</pre>
<p>
And now, just run gdb like this (it is how I get with my libprint.so
example):
</p>
<pre class="src src-sh">$ gdb libprint.so
...
(gdb) disass 0x422
Dump of assembler code for <span style="color: #f0dfaf; font-weight: bold;">function</span> <span style="color: #f0dfaf;">_Z11dereferencePi</span>:
0x0000041c <+0>: push %ebp
0x0000041d <+1>: mov %esp,%ebp
0x0000041f <+3>: mov 0x8(%ebp),%eax
0x00000422 <+6>: mov (%eax),%eax
0x00000424 <+8>: pop %ebp
0x00000425 <+9>: ret
End of assembler dump.
(gdb) ...
</pre>
<p>
If you are fluent with assembler you could read it, or use the meta
data given by gdb: "Z11dereferencePi". Oops, I realized that I have
forgot to use "-g" when compiling. Not important: we have a mangled
symbol. We can use one of the method presented in one of my previous
<a href="http://enki-tech.blogspot.fr/2012/07/demangle-c-symbols.html">post</a>. And voila, we know that our mistake is in the function
<code>dereference(int*)</code>. Pretty good when, without this method
I was unable to know where it fails, why, and in the impossibility to
reproduce it since there is too much parameters. I don't know how I
would have done without this method.
</p>
<p>
I put this script on my <a href="https://github.com/Enki-Prog/tools/blob/master/debug/dmesg.sh">github account</a>, so if you want to fork it to
enhance it, it is possible.
</p>
<p>
Hope you liked it!
</p></div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com3tag:blogger.com,1999:blog-6470854316396283720.post-88293174518688058682012-08-10T19:54:00.000+02:002012-08-13T09:22:16.593+02:00Debugging C++ (Part 2): Valgrind and gdb<body>
<div id="content">
<p>This article is the second post of the "Debugging C++" series. This
post is an introduction of Valgrind and gdb. It is intended for people
that don't know these because it starts from the beginning and gives
some links to the documentation. In the valgrind part, I present the
notion of "definitely lost", "indirectly lost", etc. If you are
already familiar with these notions, I invite you to go through the
second part of this post about gdb. In this second part I start by briefly presenting what
is gdb and what it is useful. But the main interest of this section is
that I present the notion of reverse-debugging, which allows you to
run your program backward. I also present a useful trick when you want
to debug a code you wrote (and you can modify) inside an unknown
environment (for example, imagine you want to debug your (buggy)
malloc implementation and you test it with <code>ls</code>).
</p>
<p>
Before starting tools like Valgrind or gdb, think about compiling your
code in debug mode, and not using optimizations. Otherwise you'll get
trouble to debug it. For example with gdb, your cursor will jump from
one line to another without following the linearity of the source
code. This can be disappointing, this is due to that.
</p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> Valgrind </h2>
<div class="outline-text-2" id="text-1">
<p>
Valgrind is a set of tools that contains a memory checker (memcheck),
a profiler (users can use two modules: callgrind and cachegrind), a
tool for checking the memory consumption (massif), a synchronisation
checker (Helgrind). The tools I use the most in this list is Memcheck,
and this is all I will talk about in this post. I'm sure there will be
other posts on this list of tools in the future. This is just a brief
introduction. If you already know valgrind, you should skip this part.
</p>
<p>
Memcheck helps you to detect any memory corruption. How it looks like?
Let's assume you have a program like this:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><vector></span>
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">argc</span>, <span style="color: #dfdfbf; font-weight: bold;">char</span> *<span style="color: #f0dfaf;">argv</span>[])
{
<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">vector</span><<span style="color: #dfdfbf; font-weight: bold;">int</span>> <span style="color: #f0dfaf;">v</span>;
v.reserve(2);
v[2] = 4;
}
</pre>
<p>
The call to reserve allocates the space for two integers. But we try
to write in a unallocated address. So it is a mistake from the
programmer, and even if in this example it is trivial that there is a
mistake, sometimes it is not, because it is hidden in a lot of
code. So, detecting this is not so simple. That's where Memcheck is
helpful. Here is what he says about this snippet.
</p>
<pre class="src src-dot">==4641== Invalid write of size 4
==4641== at 0x40099A: main (test.cc:8)
==4641== Address 0x5955048 is 0 bytes after a block of size 8 alloc d
==4641== at 0x4C286E7: operator new(unsigned long)\
(in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4641== by 0x400FB3: __gnu_cxx::new_allocator<int>::\
allocate(unsigned long, void const*) (new_allocator.h:94)
==4641== by 0x400ECA: std::_Vector_base<int, std::allocator<int> >::\
_M_allocate(unsigned long) (in /tmp/aout)
==4641== by 0x400D3B: int* std::vector<int, std::allocator<int> >::\
_M_allocate_and_copy<std::move_iterator<int*> >(unsigned long, \
std::move_iterator<int*>, std::move_iterator<int*>) (stl_vector.h:1109)
==4641== by 0x400AC8: std::vector<int, std::allocator<int> >::\
reserve(unsigned long) (vector.tcc:76)
==4641== by 0x400988: main (test.cc:6)
</pre>
<p>
4641 corresponds to the PID of the process. Every line coming from
valgrind is formatted like this: <code>==PID==</code>. Line beginning by a space are
just the continuation of the line above. It was just for having the output of valgrind fitting in the page.
</p>
<p>
Remember to use "-g" when you compile your program, otherwise you'll
get the name of the binary instead of the name of the file and the
line number.
</p>
<p>
It starts by giving the name of the violation: "Invalid write" and
tells us how many bytes we violate. Here this is 4 (sizeof(int)). Then
he tells us where we have made a mistake, and then he shows what is
the mistake. We have written after an allocated area. And then he
shows the stack of the call that led to allocate this area. It starts
by a call to reserve in the main line 6, and so on.
</p>
<p>
As you can see, the message is clear and it helps finding this kind of
mistakes easily. This is a valuable tool for writing bug-free
software. Every of your program should work without any error in
valgrind. Because even if it doesn't create an error directly, it can
lead to very weird error later and this is called (in my school at
least^^) a mystical error. Because there is no clue that could help
(without valgrind).
</p>
<p>
This is a simple example just to see how powerful is this
tool. Another common use of Memcheck is its ability to detect memory
leaks. As an example:
</p>
<pre class="src src-c++"><span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">int</span>* <span style="color: #f0dfaf;">p</span> = <span style="color: #f0dfaf; font-weight: bold;">new</span> <span style="color: #dfdfbf; font-weight: bold;">int</span>;
p = nullptr;
}
</pre>
<p>
This is a trivial case of a memory leak because after the affectation
of p to <code>nullptr</code>, there is no more pointer to the area
allocated with new. It is lost. This is trivial to detect it, but that
could be less trivial. So once again, we can rely on Memcheck to warn
us. Let's see what he has to say about this:
</p>
<pre class="src src-dot">==4736== HEAP SUMMARY:
==4736== in use at exit: 4 bytes in 1 blocks
==4736== total heap usage: 1 allocs, 0 frees, 4 bytes allocated
==4736==
==4736== 4 bytes in 1 blocks are definitely lost in loss record 1 of 1
==4736== at 0x4C286E7: operator new(unsigned long) (in \
/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4736== by 0x40060D: main (tests.cc:3)
==4736==
==4736== LEAK SUMMARY:
==4736== definitely lost: 4 bytes in 1 blocks
==4736== indirectly lost: 0 bytes in 0 blocks
==4736== possibly lost: 0 bytes in 0 blocks
==4736== still reachable: 0 bytes in 0 blocks
==4736== suppressed: 0 bytes in 0 blocks
</pre>
<p>
I just show the interesting part of the output of valgrind. To get
this, I ran <code>valgrind –leak-check=full <program_name></code>. We
start by reading the heap summary, which says that when we exit, 4
bytes are still in use. It indicates the number of allocation and the
number of deallocation. We see that the two numbers are not equal, so
there is a problem. There is more allocation than free, it's a leak.
</p>
<p>
At the bottom of the message we can see the kind of leak. There are
four kinds of leaks. The full explanation can be found in the <a href="http://valgrind.org/docs/manual/mc-manual.html#mc-manual.leaks">documentation</a>, in the
section 4.2.7. A short explanation follows.
</p>
<p>
AA and BB are heap blocks, and C the set of pointer of your program
(in reality it is more than that. See the section 4.2.7 cited
above). And consider an arrow represent that there is at least one
pointer to the first byte of the allocated area, and an arrow and a
`?' represents a pointer to a byte inside the allocated area and not
the first (this is called interior-pointer in the link given
above). No arrow means that the heap block is unreachable. These are
simplified examples to understand the concept behind these things.
</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdx3wp7RFh-PA2NHZlRSD-xvM_OemScRydnO-usSzyOBhsHWjv2RisyHYVu_C_ACsC6UW0phgSI1U1lsD54ecerWi7rUMKFePlZj304QQVwraX1BUqg4vKDbKkB_zvjybg-L0mngsYMgw/s1600/valgrind_pointer.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="158" width="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdx3wp7RFh-PA2NHZlRSD-xvM_OemScRydnO-usSzyOBhsHWjv2RisyHYVu_C_ACsC6UW0phgSI1U1lsD54ecerWi7rUMKFePlZj304QQVwraX1BUqg4vKDbKkB_zvjybg-L0mngsYMgw/s400/valgrind_pointer.png" /></a></div>
<p>
Once we have understood what represents these names, we can look at
the message in the middle that gives the location of each memory
blocks that leak. It says definitely lost. So we just override the
address of this area, and it appears line 3. Once we know the supposed
reason of this leak and its position in our source file, it is easy to
fix it.
</p>
<p>
This is the power of Memcheck. This is the first thing I run when I
have a bug. Because even if the error he can reveal is not responsible
of the bug, it will be annoying in the future.
</p>
<p>
A important note about valgrind, since it use its own allocator and
deallocator, some bugs may disappear when using Memcheck. It happens
to me (at least) once, when I had the output of my program that
depends on the state of the computer (state of the heap in fact),
which led my algorithm to have different results if I run it several
time consecutively. This is generally due to a memory corruption or
something like that, so I used Memcheck. And under Memcheck, the
program starts to act normally.
</p>
<p>
An interesting post about valgrind that talks about can be found <a href="http://alexott.net/en/writings/prog-checking/Valgrind.html">here</a>.
</p>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> gdb </h2>
<div class="outline-text-2" id="text-2">
<p>
A second tool I use when I still have a bug after using valgrind is
gdb (GNU Debugger).
</p>
<p>
gdb is a debugger that allows you to walk through your code at
run-time and see how the lines you (or your colleagues) wrote
influence the program and detect bugs.
</p>
<p>
I don't want to write a basic tutorial to gdb since there are really
tons of them on the Internet. I'd prefer talking about two things that
can be useful and not known by everyone. The first one is backward
debugging. The second one is a trick to debug a library when you can't
run gdb on the program that uses the library. Baptiste Afsa, one of my teacher at Epita, gave me this trick.
</p>
</div>
<div id="outline-container-2.1" class="outline-3">
<h3 id="sec-2.1"><span class="section-number-3">2.1</span> Backward debugging </h3>
<div class="outline-text-3" id="text-2.1">
<p>
Why backward debugging? Simply because I facepalmed myself too many
time after going too far in my debugging process. I mean going after
the critical point after running through trivial code slowly for 5
minutes and being forced to restart the whole thing.
</p>
<p>
This feature was introduced in 2009 with gdb version
7.0. Documentation is <a href="http://sourceware.org/gdb/wiki/ReverseDebug">here</a>. To be able to enable this feature, you
need to tell gdb to record the state of your program. The official
tutorial is <a href="http://sourceware.org/gdb/wiki/ProcessRecord/Tutorial">here</a>. So I don't have to explain that in details (No I'm
not lazy! :) but I don't like duplication and I don't like
duplication). I recommend to read the tutorial!
</p>
<p>
But the thing is that recording introduces an overhead when you use
next, continue or whatever. This can slow down the debugging process,
but I think it can really help the programmer.
</p>
<p>
Give it a try, it is helpful.
</p>
</div>
</div>
<div id="outline-container-2.2" class="outline-3">
<h3 id="sec-2.2"><span class="section-number-3">2.2</span> The infinite loop trick </h3>
<div class="outline-text-3" id="text-2.2">
<p>
This tips allows you to debug the code of a library call by a program
that you have difficulties to run with gdb. The case where I use it is
when we had to code malloc (free, realloc, calloc too) at school. And
to check if it works we used LD_PRELOAD to make binary use our version
of malloc instead of the standard version.
</p>
<p>
Let's assume we run <code>ls</code> with our malloc, how would you debug it?
</p>
<pre class="src src-sh">$ gdb ls
...
Reading symbols from /bin/ls...(no debugging symbols found)...done.
(gdb) <span style="color: #f0dfaf; font-weight: bold;">break</span> main
Function <span style="color: #cc9393;">"main"</span> not defined.
</pre>
<p>
Well… Seems hard right? The solution given by my teacher was to use an
infinite loop. How it works:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><iostream></span>
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">bool</span> <span style="color: #f0dfaf;">cond</span> = <span style="color: #dca3a3; font-weight: bold;">true</span>;
<span style="color: #f0dfaf; font-weight: bold;">while</span> (cond)
<span style="color: #f0dfaf; font-weight: bold;">continue</span>;
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"Out of the infinite loop"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">Stuff
</span>}
</pre>
<p>
The trick was to add this snippet at the beginning of the code of our
function, and to run the program. For example, compile the code above
(don't forget <code>-ggdb</code>). This is an infinite loop, yay!
</p>
<p>
gdb can attach to a running process with its PID, and is able to set
the value of a variable when debugging. So the trick is just:
</p>
<pre class="src src-sh">$ pgrep <program_name>
<pid>
$ gdb attach <pid>
...
<span style="color: #f0dfaf;">main</span> () at tests.cc:8
8 continue;
(gdb) <span style="color: #8cd0d3;">set</span> var <span style="color: #f0dfaf;">cond</span> = false
(gdb) n
7 while (cond)
(gdb) n
10 std::cout << <span style="color: #cc9393;">"Out of the infinite loop"</span> << std::endl;
(gdb)
</pre>
<p>
By setting the variable cond to false, we are out of the infinite
loop, and we have the hand on the program to debug as we
want. Impressive right?
</p>
<p>
I think this trick is useful for desperate situation like the one
described above.
</p>
<p>
This was two great features I wanted to share with you. Do you have
features that you want to share?
</p></div>
</div>
</div>
</div>
</body>
</html>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com0tag:blogger.com,1999:blog-6470854316396283720.post-64183920019929159872012-08-09T17:45:00.000+02:002012-08-09T18:25:06.389+02:00Debugging C++ (Part 1): How to write less bugs<body>
<div id="content">
<p>Hi all! I planed to make a post about some different methods to
debug a C++ program. And I realized that it will be a very long post,
so I split it into 4 parts. The first part is about some methods to
avoid dummy bugs notably using two new C++11 features. The second is a
presentation of valgrind and gdb. I include in the gdb part an
introduction to the reverse-debugging that consists in running the
program backward. The third part is an explanation of the usage of
<code>dmesg</code> to find an instruction in a library
that leads to a segmentation fault. One of the advantage is that it
works after the crash, and don't need to restart the program. The
fourth and last part is about the print method. I present a way to
make this method pleasant to use and easy to maintain.
</p>
<p>
This is far from being an exhaustive list of debugging methods,
just some of my favorites. You are invited to share yours in
comments! :-)
</p>
<p>
This first post presents the importance of using warnings when
compiling, assert to verify the coherence of the program, and
miscellaneous things introduced by C++11.
</p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> Warnings </h2>
<div class="outline-text-2" id="text-1">
<p>
The first thing to do to avoid stupid bugs is to <b>think</b> before
writing any piece of code. It can be hard sometimes, but it's totally
worth it.
</p>
<p>
My global philosophy about programming is that I want my computer to
insult me whenever he can. I want a compiler able to detect as many
errors as possible.
</p>
<p>
So, the thing to do in the aim to make the compiler as hard as
possible, is to enable warnings. Personally, on g++ I always use
<code>-W, -Wall, -Wextra</code> and <code>-Werror</code> for changing
all the warnings into errors. This can save some hours of
debugging. Let's see an example of a buggy code that compiles without
warning, but with enable warnings it won't and it is great!
</p>
<pre class="src src-c++"><span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = -42;
<span style="color: #dfdfbf; font-weight: bold;">unsigned</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">j</span> = 51;
<span style="color: #f0dfaf; font-weight: bold;">if</span> (i > j)
{
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">Bug found.
</span> }
</pre>
<p>
It can be disappointing that <code>i > j</code> is evaluated as true.
It is due to an implicit conversion. The <code>i</code> once compared
with an <code>unsigned int</code> is converted into a <code>unsigned
int</code> equal to <code>UINT_MAX - 41</code>. So this is really easy
to make this error when the type are declared too early and you forgot
what is the type of <code>i</code> and <code>j</code>. Warnings are
just mandatory! I hope this little example is enough to convince you.
I'm sure there are several hundred of examples like this one, and you
just have to run through the net to find out another examples.
</p>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> Assert </h2>
<div class="outline-text-2" id="text-2">
<p>
A good practice is to use the macro <code>assert</code>
available in the header <code>cassert</code>. This is a macro that
evaluates its content and stops the program if its content is
evaluated to false. If you define <code>NDEBUG</code> (the common way
is to pass the <code>-DNDEBUG</code> option to g++, <code>-D</code>
allows to define a macro), the code inside the parenthesis of the
macro isn't evaluated.
</p>
<p>
The main interest of assert is that it can be a good checker for
preconditions or postconditions. Beware, you must not use it as a way
to manage run time error. It is here to verify all along of your
development that you are not receiving something weird. If you use
well assert, it must stop the flow of your program before it starts
acting crazily. By making this, you ensure looking at the good spot
for finding the source of the problem, and not to a side effect that
occurs 20 functions later. This can reduce considerably the debugging
time.
</p>
<p>
As said above, the code between the parenthesis isn't evaluated in
release mode. So a bad use of <code>assert</code> would be to put real
code in it. Because once released, this code will not be ran. It is
also its advantage. Checking all these preconditions can introduce an
overhead, but you don't have to worry about it in release mode since
this is like this code never exists.
</p>
<p>
As a little conclusion, if you don't already use <code>assert</code>,
start now! :) It can change a lot of things and it has already saved a
lot of debugging hours for me. I hope it will be the same for you!
</p>
</div>
</div>
<div id="outline-container-3" class="outline-2">
<h2 id="sec-3"><span class="section-number-2">3</span> Miscellaneous </h2>
<div class="outline-text-2" id="text-3">
</div>
<div id="outline-container-3.1" class="outline-3">
<h3 id="sec-3.1"><span class="section-number-3">3.1</span> Preventing Narrowing </h3>
<div class="outline-text-3" id="text-3.1">
<p>
Now I will give some little tips which can help. There are a lot of
tips like this. Once again, I invite you to leave your own tips in
the comments!
</p>
<p>
A common problem in C or C++ is <a href="http://www.stroustrup.com/C++11FAQ.html#narrowing">narrowing</a>. Preventing this is an addition
of the C++11, which can prevent a lot of bugs. As an example:
</p>
<pre class="src src-c++"><span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">doit</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span>);
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">float</span> <span style="color: #f0dfaf;">i</span> = 4.2;
doit(i); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Huum... A bug hard that could be hard to find.
</span> doit({i}); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">warning: narrowing conversion of 'i' from
</span> <span style="color: #708070;">// </span><span style="color: #7f9f7f;">'float' to 'int' inside { } [-Wnarrowing]
</span>}
</pre>
<p>
This examples shows how it can help to avoid some kind of bugs. I recommend using it around all the variables you want to protect. These
situations happens, and why not use the language to help you to not
losing your time?
</p>
</div>
</div>
<div id="outline-container-3.2" class="outline-3">
<h3 id="sec-3.2"><span class="section-number-3">3.2</span> nullptr </h3>
<div class="outline-text-3" id="text-3.2">
<p>
It is also important to use strong typed variable. It helps the
compiler to help you! Once again, C++11 comes with a strongly type
null pointer <code>nullptr</code>. <code>NULL</code> is just 0 (<a href="http://www.stroustrup.com/bs_faq2.html#null">see Stroustrup FAQ</a>). And it can lead to bugs related to the dispatch on
overloaded function.
</p>
<pre class="src src-c++"><span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">print</span>(<span style="color: #dfdfbf; font-weight: bold;">long</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span>) { <span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"long int: "</span> << i << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl; }
<span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">print</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span>* <span style="color: #f0dfaf;">i</span>) { <span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"pointer"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl; }
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">long</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 51;
print(i); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">prints "long int: 51"
</span> print(<span style="color: #dca3a3; font-weight: bold;">NULL</span>); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">Raises a compile-time warning and prints "long int: 0"
</span> print(nullptr); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">prints "pointer"
</span>}
</pre>
<p>
The warning is "passing NULL to non-pointer argument 1 of 'void
print(long int)'". Hopefully there is a warning in this case because
this is not the wanted comportment. The introduction of
<code>nullptr</code> allows to represent the concept of a null pointer
and to have it strongly and correctly typed. I think it is a good idea
to use it instead of the NULL or 0.
</p>
</div>
</div>
<div id="outline-container-3.3" class="outline-3">
<h3 id="sec-3.3"><span class="section-number-3">3.3</span> Yoda Condition </h3>
<div class="outline-text-3" id="text-3.3">
<p>
I use this name after reading this very funny post about <a href="http://www.codinghorror.com/blog/2012/07/new-programming-jargon.html">new programming jargon</a>. This goal is for people who makes typo when they
write like writing <code>=</code> instead of <code>==</code>. I have
to admit, I have rarely something like this written in my code since I
don't use magic number (constant values written in the source in the
middle of the code). But sometimes it can help. Here is an example:
</p>
<pre class="src src-c++"><span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 51;
<span style="color: #f0dfaf; font-weight: bold;">if</span> (i = 51)
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"Oops"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
<span style="color: #f0dfaf; font-weight: bold;">if</span> (51 = i)
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"Thanks g++!"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
}
</pre>
<p>
Since some people want to write assignment in their conditions, the
compiler can't warn about this. So you have to make it scream by
helping him. In the second <code>if</code> we get an error "error:
lvalue required as left operand of assignment".
</p>
<p>
That's all for the little tips, I hope you see why being drastic with
yourself can help you. Writing these asserts is longer than not
writing them because you have to think to all the precondition needed
etc. But I can assure you that you are so happy when you see your
program crash because of an assert and not with a <code>segmentation
fault</code> or some crappy things like that. About the warnings, at
the first glance, it seems annoying to be warns about everything, but
programming is made of little details too. So use it! :)
</p>
<p>
For the miscellaneous tips, this is just little habits to take that
can improve the work flow by reducing little mistakes. The last one is
more a funny thing than a strong guideline as are using
<code>{}</code> to prevent narrowing and <code>nullptr</code> to help the compiler by saying that we use a pointer.
</p>
<p>
Don't hesitate to post your own tips in comments ;)
</p></div>
</div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com1tag:blogger.com,1999:blog-6470854316396283720.post-89777250122846721332012-08-05T18:18:00.000+02:002012-08-22T00:41:44.947+02:00C++11: Vector Improved, How It Works?<body>
<div id="content">
<h1 class="title"></h1>
<p>C++11 comes with several interesting things, and in this post, we
will talk a little about a new method in <code>std::vector</code> that comes with the new
standard. This method can lead to improve the performance of your
programs. This post is divided in two: The first part explains why
it is good to have this new method (emplace_back) and how to use it,
and the second part will try to make the way it works clear. To
achieve this goal, we have to go through several new things (variadic
template, constexpr, argument forwarding) that we explain a little to understand the whole thing.
</p>
<p>
In the previous standard, sometimes you had to create an array of
let's say Point3D (or whatever) in a loop. Let's suppose we know the
number of elements we have to put in the vector, we first show the
slowest version I think about, and then we show a more optimized
version thanks to C++11 standard.
</p>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> A Case Study </h2>
<div class="outline-text-2" id="text-1">
<pre class="src src-c++"><span style="color: #f0dfaf; font-weight: bold;">struct</span> <span style="color: #dfdfbf; font-weight: bold;">Point3D</span>
{
<span style="color: #f0dfaf;">Point3D</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">xx</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">yy</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">zz</span>)
: x {xx}
, y {yy}
, z {zz}
{
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"Cstor"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
}
<span style="color: #f0dfaf;">Point3D</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">Point3D</span>& <span style="color: #f0dfaf;">p</span>)
: x {p.x}
, y {p.y}
, z {p.z}
{
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"Copy Cstor"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
}
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">x</span>;
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">y</span>;
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">z</span>;
};
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">vector</span><<span style="color: #dfdfbf; font-weight: bold;">Point3D</span>> <span style="color: #f0dfaf;">v</span>;
<span style="color: #f0dfaf; font-weight: bold;">for</span> (<span style="color: #dfdfbf; font-weight: bold;">unsigned</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 0; i < 10; ++i)
{
v.push_back(Point3D {i, i - 69, i + 42});
}
<span style="color: #f0dfaf; font-weight: bold;">for</span> (<span style="color: #dfdfbf; font-weight: bold;">unsigned</span> <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 0; i < 10; ++i)
{
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << v[i].x << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
}
}
</pre>
<p>
What we want in this program, is to have only 10 calls to the
constructor because we just want ten objects, so our requirement seems
legit right? But if we run this program, we can see 10 calls to the
first constructor and 25 to the copy constructor. This is huge! There
are two reasons for these copies:
</p>
<ul>
<li>
Vectors are dynamic arrays. And each time it reaches its limit, it
doubles its size. So all the elements are copied at each
reallocation. It starts with a size 1, then has to double its size,
and the same for 2, 4 and 8. If we add these numbers, we have 15
copies. These can be deleted by using the "reserve" method
since we known the number of elements. By
this call we avoid the reallocation and the copies.
</li>
<li>
The problem of who is responsible of the destruction of which object
is a complex one. The STL handles this by copying the object it
takes in their containers and to destroy them when the container is
destroyed. This is why we still have 20 copies and not 10. But with
C++11 comes an <code>emplace_back</code> method (<code>emplace</code> exists too, but we focus
on the <code>push_back</code> dual here). This method removes the copy done by
the <code>push_back</code> method. For a user, the only changes to make is to
replace the call to <code>push_back</code> by a call to <code>emplace_back</code>. The arguments
to give to the new method are the arguments to give to the constructor:
</li>
</ul>
<pre class="src src-c++">v.emplace_back(i, i - 69, i + 42);
</pre>
</div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> How It Works </h2>
<div class="outline-text-2" id="text-2">
<p>
Now, let's see what are the changes done for being able to make this
<code>emplace_back</code> method. For this post I have used the glibcxx version
4.7.1 to discover the changes.
</p>
<p>
Before going into the code, we have to present variadic templates
and its power, the forwarding parameters concept, and how to use it.
Then, we show the difference between
<code>push_back</code> and <code>emplace_back</code>.
</p>
</div>
<div id="outline-container-2.1" class="outline-3">
<h3 id="sec-2.1"><span class="section-number-3">2.1</span> Variadic Template and Forwarding </h3>
<div class="outline-text-3" id="text-2.1">
<p>
Forwarding parameters is a way to take all the arguments received by
a function, and to resend it as it comes. This
comes with variadic templates. Variadic templates allow to pass
an undefined number of arguments to a function/method. It allows to
have a program which looks functional (a Head and the Rest). The code that follows
combines two new features of the C++11, constexpr and variadic
parameters. A little word about constexpr: it allows to make
computation at compile time if they are possible (there are several
conditions to respect for that, but for now, we just assume that
they are respected). In this example, we find the min of a list of
argument at compile time (thanks to constexpr). This is a generic
version that works only with integers but works on 2, 3, 4, … n
arguments.
</p>
<pre class="src src-c++">constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">min</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">n</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">p</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> n < p ? n : p;
}
<span style="color: #f0dfaf; font-weight: bold;">template</span><<span style="color: #f0dfaf; font-weight: bold;">typename</span>... Args>
constexpr
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">min</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">n</span>, <span style="color: #dfdfbf; font-weight: bold;">Args</span>... <span style="color: #f0dfaf;">args</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> min(n, min(args...));
}
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">argc</span>, <span style="color: #dfdfbf; font-weight: bold;">char</span> *<span style="color: #f0dfaf;">argv</span>[])
{
static_assert(min(4, 5, 6, 42, 7, 3, 6) == 3, <span style="color: #cc9393;">"min is incorrect"</span>);
}
</pre>
<p>
The recursion mechanism is classical, but what I would have implemented
with a vector in the past (in a run-time version) or template
recursion (in a compile-time version) is fully expressible with
the concept of variadic template, and it is enjoyable, because it is
kind of beautiful. It allows to be computed at compile-time if all
the arguments are deductible at this time, or simply computed at
run-time. It is also invisible for the user.
</p>
<p>
It is important to note that the arguments are passed by copy. If we
wanted to pass them by reference, the game would be harder… And to
be honest, at this time, I don't know how I should do. It seems more
complex to handle the recursion because it implies to implement
different combination of the arguments ( int&, int&&; int&&, int&;
…). There was a proposal to make it as a part of the standard
library <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2772.pdf">(proposition n772)</a>, or with <code>initializer_list</code>. The proposal shows it is
easier to implement and faster with the second method. We keep this min implementation
as a simple example to understand variadic templates. Any
proposition of a fully generic working version (using constexpr and variadic template) of this is encouraged! A solution might be to use std::forward
since it seems to be made for handling the forwarding, but my first tries were not
successful.
</p>
<p>
Now you have seen why I think the variadic template are good to play
with, let's talk about forwarding arguments. Forwarding is made by
the <code>std::forward</code> function from the `utility' header (code can be
found in `bits/move.h'). It forwards the arguments exactly as they
are received (more information in the <a href="http://en.cppreference.com/w/cpp/utility/forward">man</a>). Here is a little example
of what makes <code>std::forward</code> in the code:
</p>
<pre class="src src-c++"><span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><iostream></span>
<span style="color: #8cd0d3;">#include</span> <span style="color: #cc9393;"><utility></span>
<span style="color: #f0dfaf; font-weight: bold;">struct</span> <span style="color: #dfdfbf; font-weight: bold;">Item</span>
{
<span style="color: #f0dfaf;">Item</span>(): value{0} {}
<span style="color: #f0dfaf;">Item</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">Item</span>& <span style="color: #f0dfaf;">p</span>){ <span style="color: #dca3a3; font-weight: bold;">std</span>::cout << <span style="color: #cc9393;">"Copy"</span> << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl; }
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span>;
};
<span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">take_args</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span>& <span style="color: #f0dfaf;">a</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span>&& <span style="color: #f0dfaf;">b</span>, <span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">c</span>, <span style="color: #dfdfbf; font-weight: bold;">Item</span>& <span style="color: #f0dfaf;">f</span>)
{
<span style="color: #dca3a3; font-weight: bold;">std</span>::cout << a << <span style="color: #cc9393;">" - "</span> << b << <span style="color: #cc9393;">" - "</span> << c
<< <span style="color: #cc9393;">" - "</span> << f.value << <span style="color: #dca3a3; font-weight: bold;">std</span>::endl;
}
<span style="color: #f0dfaf; font-weight: bold;">template</span> <<span style="color: #f0dfaf; font-weight: bold;">typename</span>... Args>
<span style="color: #dfdfbf; font-weight: bold;">void</span> <span style="color: #f0dfaf;">call_take_args</span>(Args&&... args)
{
take_args(<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">forward</span><Args>(args)...);
}
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>()
{
<span style="color: #dfdfbf; font-weight: bold;">Item</span> <span style="color: #f0dfaf;">f</span>;
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">i</span> = 2;
call_take_args(i, 4, 5, f);
}
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">The program outputs "2 - 4 - 5 - 0".
</span>
</pre>
<p>
If we remove the reference in
the last take_args argument, "Copy" is also printed. We can see that
the program won't compile if we remove a `&' for the second
argument, or if we add an extra one to the first. This is because
<code>std::forward</code> keeps the r/l-valueness of the argument received.
How are they able to know this? Let's take a look at the source of
this function (version 4.7.1 of glibcxx):
</p>
<pre class="src src-c++"><span style="color: #f0dfaf; font-weight: bold;">template</span><<span style="color: #f0dfaf; font-weight: bold;">typename</span> <span style="color: #dfdfbf; font-weight: bold;">_Tp</span>>
constexpr <span style="color: #dfdfbf; font-weight: bold;">_Tp</span>&&
<span style="color: #f0dfaf;">forward</span>(<span style="color: #f0dfaf; font-weight: bold;">typename</span> <span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dca3a3; font-weight: bold;">remove_reference</span><<span style="color: #dfdfbf; font-weight: bold;">_Tp</span>>::<span style="color: #dfdfbf; font-weight: bold;">type</span>& <span style="color: #f0dfaf;">__t</span>) noexcept
{ <span style="color: #f0dfaf; font-weight: bold;">return</span> <span style="color: #f0dfaf; font-weight: bold;">static_cast</span><_Tp&&>(__t); }
<span style="color: #f0dfaf; font-weight: bold;">template</span><<span style="color: #f0dfaf; font-weight: bold;">typename</span> <span style="color: #dfdfbf; font-weight: bold;">_Tp</span>>
constexpr <span style="color: #dfdfbf; font-weight: bold;">_Tp</span>&&
<span style="color: #f0dfaf;">forward</span>(<span style="color: #f0dfaf; font-weight: bold;">typename</span> <span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dca3a3; font-weight: bold;">remove_reference</span><<span style="color: #dfdfbf; font-weight: bold;">_Tp</span>>::<span style="color: #dfdfbf; font-weight: bold;">type</span>&& <span style="color: #f0dfaf;">__t</span>) noexcept
{
static_assert(<span style="color: #f0dfaf; font-weight: bold;">!</span><span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dca3a3; font-weight: bold;">is_lvalue_reference</span><<span style="color: #dfdfbf; font-weight: bold;">_Tp</span>>::value, <span style="color: #cc9393;">"template argument"</span>
<span style="color: #cc9393;">" substituting _Tp is an lvalue reference type"</span>);
<span style="color: #f0dfaf; font-weight: bold;">return</span> <span style="color: #f0dfaf; font-weight: bold;">static_cast</span><_Tp&&>(__t);
}
</pre>
<p>
The first version of the function takes a lvalue and the second a
rvalue. The static_assert just checks if the specialization works as
expected. This specialization works because <code>std::remove_reference</code>
takes a type `T' (possibly U, U&, U&&), and the `type' is a typedef
of T. So we are able to
manage a use case where we give as parameter T, T& or T&& the same
way. As a result we have two functions with the following signature:
<code>forward(T& __t)</code> and <code>forward(T&& __t)</code>. If the
argument is a lvalue it goes in the first one, otherwise to the
second. <code>noexcept</code> just helps the compiler to know that the
function/method will not throw an exception or that the program
should be stopped if an exception tries to escape from here.
</p>
<p>
Now let's take a look at what they return. The fact that both functions seem to return the same thing might look weird. We have
the feeling that they return the same type: `T&&'. But in fact,
`T' could be a `U&' or a `U&&', and C++11 comes with a rule named
<span style="text-decoration:underline;">reference collapsing rules</span> (see this <a href="http://thbecker.net/articles/rvalue_references/section_08.html">article</a> which talk about it). This is simple:
</p>
<ul>
<li>
U& & => U&
</li>
<li>
U&& & => U&
</li>
<li>
U& && => U&
</li>
<li>
U&& && => U&&
</li>
</ul>
<p>This looks like the `and' truth table where & is 0 and && is 1. A good way
to remember I think. So: if _Tp is a U& (the first function), the
returned object will be U& too, and if it was U&& it will be
U&&. Which follows the rules of a perfect forwarding. Now we have
understood the concept of the forwarding, and the way it is done,
we can take a look at the code of push_back and emplace_back to know
what makes the change.
</p>
</div>
</div>
<div id="outline-container-2.2" class="outline-3">
<h3 id="sec-2.2"><span class="section-number-3">2.2</span> Emplace_back and Push_back </h3>
<div class="outline-text-3" id="text-2.2">
<p>
Now we have all the tools in our hands to understand the difference
between these two methods, we can just show the source code:
</p>
<pre class="src src-c++"><span style="color: #708070;">// </span><span style="color: #7f9f7f;">Taken from bits/stl_vector.h
</span><span style="color: #dfdfbf; font-weight: bold;">void</span>
<span style="color: #f0dfaf;">push_back</span>(<span style="color: #f0dfaf; font-weight: bold;">const</span> <span style="color: #dfdfbf; font-weight: bold;">value_type</span>& <span style="color: #f0dfaf;">__x</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">if</span> (<span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_finish != <span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_end_of_storage)
{
<span style="color: #dca3a3; font-weight: bold;">_Alloc_traits</span>::construct(<span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl, <span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_finish,
__x);
++<span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_finish;
}
<span style="color: #f0dfaf; font-weight: bold;">else</span>
<span style="color: #8cd0d3;">#ifdef</span> __GXX_EXPERIMENTAL_CXX0X__
_M_emplace_back_aux(__x);
<span style="color: #8cd0d3;">#else</span>
_M_insert_aux(end(), __x);
<span style="color: #8cd0d3;">#endif</span>
}
<span style="color: #708070;">// </span><span style="color: #7f9f7f;">Taken from bits/vector.tcc
</span><span style="color: #f0dfaf; font-weight: bold;">template</span><<span style="color: #f0dfaf; font-weight: bold;">typename</span>... _Args>
<span style="color: #dfdfbf; font-weight: bold;">void</span>
<span style="color: #dca3a3; font-weight: bold;">vector</span><_Tp, _Alloc>::
<span style="color: #f0dfaf;">emplace_back</span>(_Args&&... __args)
{
<span style="color: #f0dfaf; font-weight: bold;">if</span> (<span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_finish != <span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_end_of_storage)
{
<span style="color: #dca3a3; font-weight: bold;">_Alloc_traits</span>::construct(<span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl, <span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_finish,
<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">forward</span><_Args>(__args)...);
++<span style="color: #f0dfaf; font-weight: bold;">this</span>->_M_impl._M_finish;
}
<span style="color: #f0dfaf; font-weight: bold;">else</span>
_M_emplace_back_aux(<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">forward</span><_Args>(__args)...);
}
</pre>
<p>
The main difference is the use of the <code>std::forward</code>. The macro
<code>__GXX_EXPERIMENTAL_CXX0X__</code> is defined when an option to
activate C++11 is set. The <code>_M_emplace_back_aux</code> and
<code>_M_insert_aux</code> are responsible of the reallocation when the number
of available position (available means allocated and not already taken) is
down to 0.
</p>
<p>
Since there is no other difference between the two methods, that
means the interesting point is in the <code>construct</code> method (we just
leave the *aux method for this post, it will take too much time to
analyze them).
</p>
<p>
Before that, we have to present briefly the concept of
putting `::' before a function/method name and the concept of using a placement
new. If your are familiar with these concepts, you should skip these
paragraphs and go directly after the code of the <code>construct</code> method.
</p>
<p>
It is possible for a class to override its operator new. This
(static) method is responsible of the allocation of the object. If
we put `::' before the operator <code>new</code> that means that we want to
take the one in the global namespace and not the overridden one. The
code below shows the difference between these two notation:
</p>
<pre class="src src-c++"><span style="color: #f0dfaf; font-weight: bold;">struct</span> <span style="color: #dfdfbf; font-weight: bold;">Foo</span>
{
<span style="color: #f0dfaf;">Foo</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">a</span>)
: value{a}
{
}
<span style="color: #f0dfaf; font-weight: bold;">static</span> <span style="color: #dfdfbf; font-weight: bold;">void</span>* <span style="color: #f0dfaf; font-weight: bold;">operator</span> <span style="color: #f0dfaf; font-weight: bold;">new</span>(<span style="color: #dfdfbf; font-weight: bold;">size_t</span>)
{
<span style="color: #f0dfaf; font-weight: bold;">return</span> (<span style="color: #dfdfbf; font-weight: bold;">void</span>*)42; <span style="color: #708070;">// </span><span style="color: #7f9f7f;">g++ is able to detect if
</span> <span style="color: #708070;">// </span><span style="color: #7f9f7f;">we return 0 and raises a warning.
</span> }
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">value</span>;
};
<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">main</span>(<span style="color: #dfdfbf; font-weight: bold;">int</span> <span style="color: #f0dfaf;">argc</span>, <span style="color: #dfdfbf; font-weight: bold;">char</span> *<span style="color: #f0dfaf;">argv</span>[])
{
<span style="color: #dfdfbf; font-weight: bold;">Foo</span>* <span style="color: #f0dfaf;">bad</span> = <span style="color: #f0dfaf; font-weight: bold;">new</span> <span style="color: #dfdfbf; font-weight: bold;">Foo</span>(4); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">segmentation fault.
</span> <span style="color: #dfdfbf; font-weight: bold;">Foo</span>* <span style="color: #f0dfaf;">good</span> = ::<span style="color: #f0dfaf; font-weight: bold;">new</span> <span style="color: #dfdfbf; font-weight: bold;">Foo</span>(4); <span style="color: #708070;">// </span><span style="color: #7f9f7f;">ok.
</span> <span style="color: #f0dfaf; font-weight: bold;">return</span> 0;
}
</pre>
<p>
The operator new returns a pointer to an unallocated area, which
leads to a segmentation fault when the constructor is called and
tries to write the value of `a'. If we put `::' in front of new,
this buggy operator new is not called, and there is no memory
corruption.
</p>
<p>
Now, let's talk about placement new. This is just a way to use
specific position in the memory, and this can be useful when working
with memory pools, or when performance is needed: allocation and
deallocation are expensive. Avoiding this can speed up the program.
The syntax is just: <code>new(position)</code>, where position is a pointer
to where the object must be. This is as simple as that.
</p>
<p>
Now let's close the parenthesis and look at the code of construct
(this is not the construct which is directly called, but the other
functions that calls this one are not interesting since the same
path is followed by emplace_back and push_back):
</p>
<pre class="src src-c++"><span style="color: #708070;">// </span><span style="color: #7f9f7f;">Taken from ext/new_allocator.h
</span><span style="color: #f0dfaf; font-weight: bold;">template</span><<span style="color: #f0dfaf; font-weight: bold;">typename</span> <span style="color: #dfdfbf; font-weight: bold;">_Up</span>, <span style="color: #f0dfaf; font-weight: bold;">typename</span>... _Args>
<span style="color: #dfdfbf; font-weight: bold;">void</span>
<span style="color: #f0dfaf;">construct</span>(<span style="color: #dfdfbf; font-weight: bold;">_Up</span>* <span style="color: #f0dfaf;">__p</span>, _Args&&... __args)
{ ::<span style="color: #f0dfaf; font-weight: bold;">new</span>((<span style="color: #dfdfbf; font-weight: bold;">void</span> *)__p) <span style="color: #dfdfbf; font-weight: bold;">_Up</span>(<span style="color: #dca3a3; font-weight: bold;">std</span>::<span style="color: #dfdfbf; font-weight: bold;">forward</span><_Args>(__args)...); }
</pre>
<p>
This version is the C++11 version, which manages the case
where we copy, and the case where we construct. Let's start by
understanding this line, they use the placement new because this is
not up to the `new' to decide where put this object, since it must be
put at the end of the vector.
</p>
<p>
There is a call to the constructor and the arguments
received are forwarded. These arguments are the ones given to the <code>emplace_back</code>
method. And then it is up to the overloading to make it works. If we
are making a copy (we arrived here by push_back), the copy
constructor is called. Otherwise, we call another constructor if it
exists (if not, we get a compile-time error).
</p>
<p>
And that's all! To arrive here, we have to know variadic template,
argument forwarding, constexpr, placement new, operator new
overriding and reference collapsing rules. But at least, we
understand what are the changes needed to be able to make this
<code>emplace_back</code> method, and how the C++11 makes it possible.
Thanks to the new standard for this improvement! :-)
</p>
<p>
PS: Thanks to Christopher Chedeau and Gregoire Bouchetoun for their comments and corrections about this article.
</p></div>
</div>
</div>
</div>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com2tag:blogger.com,1999:blog-6470854316396283720.post-84332350252144695912012-07-30T00:02:00.000+02:002012-08-05T20:43:29.789+02:00How To Demangle C++ Symbols<body>
<div id="content">
<p>
I am finally on holidays ! I was pretty busy these last months… Now I
have some times for me, I am able to unstack a lot of stuff I wanted
to share with the lost reader(s ?) of this blog. Let's start with a
few things about C++ and its mangling.
</p>
<p>
The C++ mangles its symbols. But sometimes it is hard to reread these
names. For example when you work with a lot of different libraries and
when you get a "undefined reference to <hardly-readable>". So in this
post, I'll show you how to decypher these symbols in two different ways on
GNU/Linux.
</p>
<pre class="src src-c++"><span style="color: #228b22;">void</span> <span style="color: #f000ff;">leave_a_comment</span>()
{
<span style="color: #a020f0;">return</span>;
}
<span style="color: #228b22;">void</span> <span style="color: #f000ff;">foo</span>(<span style="color: #228b22;">int</span> <span style="color: #a0522d;">v</span>)
{
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">this_blog_is_cool</span> = v;
<span style="color: #a020f0;">if</span> (this_blog_is_cool)
leave_a_comment();
}
<span style="color: #228b22;">int</span> <span style="color: #f000ff;">main</span>(<span style="color: #228b22;">int</span> <span style="color: #a0522d;">argc</span>, <span style="color: #228b22;">char</span> *<span style="color: #a0522d;">argv</span>[])
{
foo(42);
}
</pre>
<p>
Here is an example of a simple and useless C++ program, to show what
makes the C++ with these function names. Let's assume that the source
code above is in the file bar.cc.
</p>
<pre class="src src-shell">$ gcc -c bar.cc
$ nm bar.o
00000000 T _Z15leave_a_commentv
00000005 T _Z3fooi
0000001e T main
</pre>
<p>
It seems readable. <sub>Z</sub> is reserved word for C++, the number after
corresponds to the number of characters that composed the function
name, for example here it is 3 for `foo' and 15 for `leave<sub>a</sub><sub>comment`</sub>
It is then postfixed by the type of arguments. For the first function
no argument, it is void (v). For the second one, it is an int (i). In
this case it is easy to understand what corresponds to what. But it is
enough to see what are our choices to demangle this identifiers.
</p>
<p>
I personally know two ways, (maybe there is more, thanks for reporting
it ! :)). The first way is to use `nm' itself. It has a nice option
named `-C' which allows to demangle the identifiers. If we use it, we
get this results:
</p>
<pre class="src src-shell">$ gcc -c bar.cc
$ nm -C bar.o
00000000 T leave_a_comment()
00000005 T foo(int)
0000001e T main
</pre>
<p>
Which is far better right? In fact `-C' is a shortcut for the
`–demangle' option. It can takes several style as input (see <a href="http://linux.die.net/man/1/c++filt">the man</a>
for more information). Warning, it seems that this option is not
defined by the Single Unix Specification.</div>
</p>
<p>
Another way is to use c++filt which is a tools from `GNU Binary
Utilities'. It allows to demangle C++ symbols. It can either takes a
mangled symbols in the command line, or read it from stdin. You don't
have to filter yourself the output (for example the nm output), to
make it works. You just have to give it all and he replaces what he
has to. Here is an example:
</p>
<pre class="src src-shell">$ gcc -c bar.cc
$ nm bar.o | c++filt
00000000 T leave_a_comment()
00000005 T foo(int)
0000001e T main
</pre>
<p>
That's all folks ! I hope this will be useful ;)
</p>
</body>Anonymoushttp://www.blogger.com/profile/04017957936019514019noreply@blogger.com0tag:blogger.com,1999:blog-6470854316396283720.post-81307595329047061972012-03-11T23:55:00.000+01:002012-08-06T13:24:49.521+02:00How to use git to avoid writing ChangeLog by hand?<body><br />
<div id="content"><p>The standard GNU defines what must be a ChangeLog file (see:<br />
<a href="http://www.gnu.org/prep/standards/html_node/Change-Logs.html">http://www.gnu.org/prep/standards/html_node/Change-Logs.html</a>). The<br />
main goal of this is to be able to track bugs, and to understand the<br />
history of a project.<br />
</p><br />
<div id="outline-container-1" class="outline-3"><h3 id="sec-1"><span class="section-number-3">1</span> Why keeping a ChangeLog? </h3><div class="outline-text-3" id="text-1"><br />
<p>In the past, we must keep a ChangeLog file for each project, since<br />
there was no tool able to give all the history in every condition.<br />
I am too young to know the work flow with CVS and other tool. I<br />
learn the control version with SVN. But to have access to all the<br />
history of a project, we'll need to be connected. And it is long.<br />
</p><p>Now we have git (or Mercurial, but I don't know this one), which are<br />
distributed system, and they allow to keep all the history of a project<br />
in local. So, why should we keep a ChangeLog file?<br />
</p><p>Pros<br />
</p><ul><li> When the project is released, the `git log` is not accessible.<br />
</li>
<li> There is copyright issue in free software.<br />
</li>
<li> It is easy to write a good ChangeLog with Emacs (and I'm sure it<br />
is easy with vim too).<br />
</li>
</ul><br />
<p>Cons<br />
</p><ul><li> There is several tools to generate a ChangeLog file with the output<br />
of git log. I think about the tool 'gitlog-to-changelog' from the<br />
gnulib project (see: <a href="http://www.gnu.org/software/gnulib/">http://www.gnu.org/software/gnulib/</a>).<br />
</li>
<li> It is common, when playing with branches and rebasing a lot, to have<br />
conflict only in the ChangeLog file.<br />
</li>
</ul><br />
<p>By generating the ChangeLog when making a release (or an archive), we<br />
solve the problem of the history and the copyright. We can use a<br />
ChangeLog file, not in the repository (maybe it is a good idea to put<br />
the "ChangeLog" in the '.gitignore'), to write the log message, and<br />
then we can use a little script to take the first entry and give it to<br />
git.<br />
</p><p>For example, a simple function like this can do the trick:<br />
</p><br />
<pre class="src src-sh"><span style="color: #f0dfaf;">commit</span>()
{
[[ <span style="color: #f0dfaf; font-weight: bold;">!</span> -f ChangeLog ]] && {
<span style="color: #8cd0d3;">echo</span> <span style="color: #cc9393;">'no ChangeLog in current directory'</span> >&2
<span style="color: #f0dfaf; font-weight: bold;">return</span> 1
}
git commit -m <span style="color: #cc9393;">"`sed'1d;/^....-..-../Q;s/^\t//;' ChangeLog`"</span> <span style="color: #cc9393;">"$@"</span>
}
</pre><br />
<p>This script is highly enhanceable. This is just an idea of what could<br />
be the script I am talking about.<br />
</p></div><br />
</div><br />
<div id="outline-container-2" class="outline-3"><h3 id="sec-2"><span class="section-number-3">2</span> Using Emacs to write the ChangeLog </h3><div class="outline-text-3" id="text-2"><br />
<p>Now let's talk about the work flow, and the use of Emacs for writing<br />
the log. Let's suppose we have a ChangeLog file at the root of the<br />
project. The main idea is each time you modify something in a file,<br />
you hit "C-x 4 a", and its open the ChangeLog, and add an entry<br />
(which follows the GNU Coding Standard), you just have to write the<br />
meaning of your change.<br />
</p><p>Before committing, think about add a one-line summary !<br />
</p><p>There is a little problem with Emacs at this level. In the past, the<br />
common work flow was one commit by day. And the One True Editor<br />
follows this standard. So there is a way to bypass this, an option<br />
allows the function behind "C-x 4 a" to create a new entry. But it<br />
does it each time, and this is not what we want. So I create a little<br />
wrapper around this. Here is the function:<br />
</p><br />
<pre class="src src-emacs-lisp">(<span style="color: #f0dfaf; font-weight: bold;">defun</span> <span style="color: #f0dfaf;">new-changelog-entry</span>()
(interactive)
(setq add-log-always-start-new-record t)
(add-change-log-entry-other-window)
(setq add-log-always-start-new-record nil))
<span style="color: #708070;">; </span><span style="color: #7f9f7f;">"C-x 5 a" runs new-changelog-entry.
</span>(global-set-key <span style="color: #cc9393;">"5a"</span> (quote new-changelog-entry))
</pre><br />
<p>The idea is to set the option before calling, and unset it after. So,<br />
only when we want to create a new entry, a new entry is created. :D<br />
</p></div></div><br />
<div id="outline-container-3" class="outline-3"><h3 id="sec-3"><span class="section-number-3">3</span> Be sure the log follows a good format </h3><div class="outline-text-3" id="text-3"><br />
<p>In the aim to be able to translate the output of `git log` into a<br />
GNU standard compliant ChangeLog, the commit message must follow<br />
a strict format. So, how to achieve this goal?<br />
</p><p>Git provides several kind of hooks. A hook is a script called when a<br />
specific operation occurs. There is a lot of source on the web to know<br />
what is a hook. Here I'll talk about the use of a script (developed by<br />
me and one of my teacher) for solving the format of the git log.<br />
</p><p>It is a script which can be run server-side or client-side. You can<br />
find this script here:<br />
<a href="https://github.com/Enki-Prog/tools/blob/master/git/update">https://github.com/Enki-Prog/tools/blob/master/git/update</a>. Here I will<br />
talk about the problem of getting all the commit between two push. And<br />
the way to know easily the file modified when committing.<br />
</p><p>The strategy we applied, is to authorize any kind of log in a personal<br />
branch (`pseudo/feature'), and to reject a push when it is not (either<br />
a `candidates/feature' or a branch with no `/') and don't follow the<br />
format.<br />
</p><p>There are several thing checked, and it is shared by the two way to<br />
call this script. The explanation above are talking about the way<br />
to get the commits, and the information to be able to check.<br />
</p><p>The way we check after, is less interesting I think, because if you<br />
read this article, maybe it is because you want to develop yourself<br />
this kind of tools. And you just need the way to don't have to look<br />
a lot on the web how to make this, all the information you need are<br />
here or at worst on the script.<br />
</p><br />
</div><br />
<div id="outline-container-3.1" class="outline-4">3.1 Server-side<br />
<div class="outline-text-4" id="text-3.1"><br />
<p>We receive three arguments: the ref name, the old revision, and the<br />
new revision.<br />
</p><ol><li> If the new revision is a null sha1, it means it is a branch deletion.<br />
So, nothing to do here.<br />
</li>
<li> If the old revision is a null sha1, it is a branch creation.<br />
<p>In this case, to get the new revision, the command to get the<br />
commits, we need to call:<br />
</p><br />
<pre class="src src-sh">git rev-parse --not $<span style="color: #f0dfaf;">otherbranches</span> | git rev-list --stdin newrev
</pre><br />
</li>
<li> In the other case, we need to replace newrev by "oldrev..newrev".<br />
</li>
</ol><br />
<p>To get the `$otherbranches' the command is:<br />
</p><br />
<pre class="src src-sh">git for-each-ref --format=<span style="color: #cc9393;">'%(refname)'</span> refs/heads |
grep -F -x -v $<span style="color: #f0dfaf;">refname</span> |
grep -x <span style="color: #cc9393;">'refs/heads/\(candidates/.*\|[^/]*\)'</span>
</pre><br />
<p>The first line gets the list of branches. The second filters out the<br />
current branch. And the last one, keeps only the one which are non<br />
personal branch.<br />
</p></div><br />
</div><br />
<div id="outline-container-3.2" class="outline-4">3.2 Client-side<br />
<div class="outline-text-4" id="text-3.2"><br />
<p>In this case, we have only one argument: the path to the temporary<br />
file which contains the log which will be tested. In this case it is<br />
easier, because there is only one commit. The question is, how to get<br />
the list of modified file? There is several way, but the one I found<br />
the simpler, is to make:<br />
</p><br />
<pre class="src src-sh">git status --porcelain
</pre><br />
<p>The output is simple: Two characters, and the filename (eventually two,<br />
in the case of a `git mv`). If the first character is not a ? or a space,<br />
the file is in the index and ready to be committed.<br />
</p><br />
</div></div></div><br />
<div id="outline-container-4" class="outline-3"><h3 id="sec-4"><span class="section-number-3">4</span> Conclusion </h3><div class="outline-text-3" id="text-4"><br />
<p>We have talk about the question "should I keep a ChangeLog in my<br />
project?". And I developed on how to make this change in a good way.<br />
Thanks to git, Emacs, a tool to check if the log is correct and<br />
`gitlog-to-changelog'. Obviously, this is the way I choose for me,<br />
and each part I present can be switched.<br />
</p><p>Feel free to leave a comment with your opinion and/or your suggestion :)<br />
</p></div></div></div></body>Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-6470854316396283720.post-73701104355651869842012-03-11T17:16:00.000+01:002012-03-11T17:16:04.013+01:00Hello World!<h3 class="post-title entry-title"> </h3><div class="post-header"> </div><div class="post-body entry-content" id="post-body-4385849571147453829"> Welcome in my technical blog!<br />
<br />
I'll talk here about several things:<br />
- Projects I'm working on,<br />
- Development tools I'm using and some useful tricks for them (emacs, git...)<br />
- Development problem I have encountered, and I hope, the solution I have found to solve them,<br />
- And other miscellaneous stuff about programming.<br />
<br />
I hope you will find things that will be useful for you ;) </div>Unknownnoreply@blogger.com0