Blame - docs/CodingStandards.html - platform/external/llvm

blob: 1f6efd657935816dd7ade2ebf98d7bd69c3cc73a [file] [log] [blame]

Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
				2	<html><head><title>A Few Coding Standards</title></head>
				3	<body bgcolor=white>
				4
				5	<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
				6	<tr><td>  <font size=+5 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>A Few Coding Standards</b></font></td>
				7	</tr></table>
				8
				9	<ol>
				10	<li><a href="#introduction">Introduction</a>
Chris Lattner	7ae36bb	2001-07-23 20:40:41 +0000	[diff] [blame]	11	<li><a href="#mechanicalissues">Mechanical Source Issues</a>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	12	<ol>
				13	<li><a href="#sourceformating">Source Code Formatting</a>
				14	<ol>
				15	<li><a href="#scf_commenting">Commenting</a>
				16	<li><a href="#scf_commentformat">Comment Formatting</a>
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	17	<li><a href="#scf_includes">#include Style</a>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	18	<li><a href="#scf_codewidth">Source Code Width</a>
				19	<li><a href="#scf_spacestabs">Use Spaces Instead of Tabs</a>
				20	<li><a href="#scf_indentation">Indent Code Consistently</a>
				21	</ol>
				22	<li><a href="#compilerissues">Compiler Issues</a>
				23	<ol>
				24	<li><a href="#ci_warningerrors">Treat Compiler Warnings Like Errors</a>
				25	<li><a href="#ci_cpp_features">Which C++ features can I use?</a>
				26	<li><a href="#ci_portable_code">Write Portable Code</a>
				27	</ol>
				28	</ol>
				29	<li><a href="#styleissues">Style Issues</a>
				30	<ol>
				31	<li><a href="#macro">The High Level Issues</a>
				32	<ol>
				33	<li><a href="#hl_module">A Public Header File <b>is</b> a Module</a>
				34	<li><a href="#hl_dontinclude">#include as Little as Possible</a>
				35	<li><a href="#hl_privateheaders">Keep "internal" Headers Private</a>
				36	</ol>
				37	<li><a href="#micro">The Low Level Issues</a>
				38	<ol>
				39	<li><a href="#hl_assert">Assert Liberally</a>
				40	<li><a href="#hl_preincrement">Prefer Preincrement</a>
Chris Lattner	13c4659	2002-01-20 19:01:26 +0000	[diff] [blame]	41	<li><a href="#hl_avoidendl">Avoid endl</a>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	42	<li><a href="#hl_exploitcpp">Exploit C++ to its Fullest</a>
				43	</ol>
				44	<li><a href="#iterators">Writing Iterators</a>
				45	</ol>
				46	<li><a href="#seealso">See Also</a>
				47	</ol><p>
				48
				49
				50	<!-- *********************************************************************** -->
				51	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				52	<a name="introduction">Introduction
				53	</b></font></td></tr></table><ul>
				54	<!-- *********************************************************************** -->
				55
				56	This document attempts to describe a few coding standards that are being used in the LLVM source tree. Although no coding standards should be regarded as absolute requirements to be followed in all instances, coding standards can be useful.<p>
				57
				58	This document intentionally does not prescribe fixed standards for religious issues such as brace placement and space usage. For issues like this, follow the golden rule:
				59
				60	<a name="goldenrule">
				61	<blockquote><b>If you are adding a significant body of source to a project, feel free to use whatever style you are most comfortable with. If you are extending, enhancing, or bug fixing already implemented code, use the style that is already being used so that the source is uniform and easy to follow.</b></blockquote>
				62
				63	The ultimate goal of these guidelines is the increase readability and maintainability of our common source base. If you have suggestions for topics to be included, please mail them to <a href="mailto:sabre@nondot.org">Chris</a>.<p>
				64
				65
				66	<!-- *********************************************************************** -->
				67	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				68	<a name="mechanicalissues">Mechanical Source Issues
				69	</b></font></td></tr></table><ul>
				70	<!-- *********************************************************************** -->
				71
				72	<!-- ======================================================================= -->
				73	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td> </td><td width="100%">  <font color="#EEEEFF" face="Georgia,Palatino"><b>
				74	<a name="sourceformating">Source Code Formatting
				75	</b></font></td></tr></table><ul>
				76
				77
				78	<!-- _______________________________________________________________________ -->
				79	</ul><a name="scf_commenting"><h4><hr size=0>Commenting</h4><ul>
				80
				81	Comments are one critical part of readability and maintainability. Everyone knows they should comment, so should you. :) Although we all should probably comment our code more than we do, there are a few very critical places that documentation is very useful:<p>
				82
				83	<ol>
				84	<h4><li>File Headers</h4>
				85	Every source file should have a header on it that describes the basic purpose of the file. If a file does not have a header, it should not be checked into CVS. Most source trees will probably have a standard file header format. The standard format for the LLVM source tree looks like this:<p>
				86
				87	<pre>
				88	//===-- llvm/Instruction.h - Instruction class definition --------- C++ ---=//
				89	//
				90	// This file contains the declaration of the Instruction class, which is the
				91	// base class for all of the VM instructions.
				92	//
				93	//===----------------------------------------------------------------------===//
				94	</pre>
				95
				96	A few things to note about this particular format. The "<tt>-- C++ --</tt>" string on the first line is there to tell Emacs that the source file is a C++ file, not a C file (Emacs assumes .h files are C files by default [Note that tag this is not neccesary in .cpp files]). The name of the file is also on the first line, along with a very short description of the purpose of the file. This is important when printing out code and flipping though lots of pages.<p>
				97
				98	The main body of the description does not have to be very long in most cases. Here it's only two lines. If an algorithm is being implemented or something tricky is going on, a reference to the paper where it is published should be included, as well as any notes or "gotchas" in the code to watch out for.<p>
				99
				100
				101	<h4><li>Class overviews</h4>
				102
				103	Classes are one fundemental part of a good object oriented design. As such, a class definition should have a comment block that explains what the class is used for... if it's not obvious. If it's so completely obvious your grandma could figure it out, it's probably safe to leave it out. Naming classes something sane goes a long ways towards avoiding writing documentation. :)<p>
				104
				105
				106	<h4><li>Method information</h4>
				107
				108	Methods defined in a class (as well as any global functions) should also be documented properly. A quick note about what it does any a description of the borderline behaviour is all that is neccesary here (unless something particularly tricky or insideous is going on). The hope is that people can figure out how to use your interfaces without reading the code itself... that is the goal metric.<p>
				109
				110	Good things to talk about here are what happens when something unexpected happens: does the method return null? Abort? Format your hard disk?<p>
				111	</ol>
				112
				113
				114	<!-- _______________________________________________________________________ -->
				115	</ul><a name="scf_commentformat"><h4><hr size=0>Comment Formatting</h4><ul>
				116
				117	In general, prefer C++ style (<tt>//</tt>) comments. They take less space, require less typing, don't have nesting problems, etc. There are a few cases when it is useful to use C style (<tt>/* */</tt>) comments however:<p>
				118
				119	<ol>
				120	<li>When writing a C code: Obviously if you are writing C code, use C style comments. :)
				121	<li>When writing a header file that may be #included by a C source file.
				122	<li>When writing a source file that is used by a tool that only accepts C style comments.
				123	</ol><p>
				124
				125	To comment out a large block of code, use <tt>#if 0</tt> and <tt>#endif</tt>. These nest properly and are better behaved in general than C style comments.<p>
				126
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	127	<!-- _______________________________________________________________________ -->
				128	</ul><a name="scf_includes"><h4><hr size=0>#include Style</h4><ul>
				129
				130	Immediately after the <a href="#scf_commenting">header file comment</a> (and
				131	include guards if working on a header file), the <a
				132	href="hl_dontinclude">minimal</a> list of #includes required by the file should
				133	be listed. We prefer these #includes to be listed in this order:<p>
				134
				135	<ol>
				136	<li><a href="#mmheader">Main Module header</a>
				137	<li><a href="#hl_privateheaders">Local/Private Headers</a>
				138	<li>llvm/*
				139	<li>llvm/Analysis/*
				140	<li>llvm/Assembly/*
				141	<li>llvm/Bytecode/*
				142	<li>llvm/CodeGen/*
				143	<li>...
				144	<li>Support/*
				145	<li>Config/*
				146	<li>System #includes
				147	</ol>
				148
				149	... and each catagory should be sorted by name.<p>
				150
				151	<a name="mmheader">The "Main Module Header" file applies to .cpp file which
				152	implement an interface defined by a .h file. This #include should always be
				153	included <b>first</b> regardless of where it lives on the file system. By
				154	including a header file first in the .cpp files that implement the interfaces,
				155	we ensure that the header does not have any hidden dependencies which are not
				156	explicitly #included in the header, but should be. It is also a form of
				157	documentation in the .cpp file to indicate where the interfaces it implements
				158	are defined.<p>
				159
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	160
				161	<!-- _______________________________________________________________________ -->
				162	</ul><a name="scf_codewidth"><h4><hr size=0>Source Code Width</h4><ul>
				163
				164	Write your code to fit within 80 columns of text. This helps those of us who like to print out code and look at your code in an xterm without resizing it.
				165
				166
				167	<!-- _______________________________________________________________________ -->
				168	</ul><a name="scf_spacestabs"><h4><hr size=0>Use Spaces Instead of Tabs</h4><ul>
				169
				170	In all cases, prefer spaces to tabs in source files. People have different prefered indentation levels, and different styles of indentation that they like... this is fine. What isn't is that different editors/viewers expand tabs out to different tab stops. This can cause your code to look completely unreadable, and it is not worth dealing with.<p>
				171
				172	As always, follow the <a href="#goldenrule">Golden Rule</a> above: follow the style of existing code if your are modifying and extending it. If you like four spaces of indentation, <b>DO NOT</b> do that in the middle of a chunk of code with two spaces of indentation. Also, do not reindent a whole source file: it make for incredible diffs that are absolutely worthless.<p>
				173
				174
				175	<!-- _______________________________________________________________________ -->
				176	</ul><a name="scf_indentation"><h4><hr size=0>Indent Code Consistently</h4><ul>
				177
				178	Okay, your first year of programming you were told that indentation is important. If you didn't believe and internalize this then, now is the time. Just do it.<p>
				179
				180
				181
				182
				183	<!-- ======================================================================= -->
				184	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td> </td><td width="100%">  <font color="#EEEEFF" face="Georgia,Palatino"><b>
				185	<a name="compilerissues">Compiler Issues
				186	</b></font></td></tr></table><ul>
				187
				188
				189	<!-- _______________________________________________________________________ -->
				190	</ul><a name="ci_warningerrors"><h4><hr size=0>Treat Compiler Warnings Like Errors</h4><ul>
				191
				192	If your code has compiler warnings in it, something is wrong: you aren't casting values correctly, your have "questionable" constructs in your code, or you are doing something legitimately wrong. Compiler warnings can cover up legitimate errors in output and make dealing with a translation unit difficult.<p>
				193
				194	It is not possible to prevent all warnings from all compilers, nor is it desirable. Instead, pick a standard compiler (like <tt>gcc</tt>) that provides a good thorough set of warnings, and stick to them. At least in the case of <tt>gcc</tt>, it is possible to work around any spurious errors by changing the syntax of the code slightly. For example, an warning that annoys me occurs when I write code like this:<p>
				195
				196	<pre>
				197	if (V = getValue()) {
				198	..
				199	}
				200	</pre><p>
				201
				202	<tt>gcc</tt> will warn me that I probably want to use the <tt>==</tt> operator, and that I probably mistyped it. In most cases, I haven't, and I really don't want the spurious errors. To fix this particular problem, I rewrite the code like this:<p>
				203
				204	<pre>
				205	if ((V = getValue())) {
				206	..
				207	}
				208	</pre><p>
				209
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	210	...which shuts <tt>gcc</tt> up. Any <tt>gcc</tt> warning that annoys you can be
				211	fixed by massaging the code appropriately.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	212
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	213	These are the <tt>gcc</tt> warnings that I prefer to enable: <tt>-Wall -Winline
				214	-W -Wwrite-strings -Wno-unused</tt><p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	215
				216
				217	<!-- _______________________________________________________________________ -->
				218	</ul><a name="ci_cpp_features"><h4><hr size=0>Which C++ features can I use?</h4><ul>
				219
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	220	Compilers are finally catching up to the C++ standard. Most compilers implement
				221	most features, so you can use just about any features that you would like. In
				222	the LLVM source tree, I have chosen to not use these features:<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	223
				224	<ol>
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	225	<li>Exceptions: Exceptions are very useful for error reporting and handling
				226	exceptional conditions. I do not use them in LLVM because they do have an
				227	associated performance impact (by restricting restructuring of code), and parts
				228	of LLVM are designed for performance critical purposes.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	229
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	230	Just like most of the rules in this document, this isn't a hard and fast
				231	requirement. Exceptions are used in the Parser, because it simplifies error
				232	reporting <b>significantly</b>, and the LLVM parser is not at all in the
				233	critical path.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	234
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	235	<li>RTTI: RTTI has a large cost in terms of executable size, and compilers are
				236	not yet very good at stomping out "dead" class information blocks. Because of
				237	this, typeinfo and dynamic cast are not used.
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	238	</ol><p>
				239
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	240	Other features, such as templates (without partial specialization) can be used
				241	freely. The general goal is to have clear, consise, performant code... if a
				242	technique assists with that then use it.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	243
				244
				245	<!-- _______________________________________________________________________ -->
				246	</ul><a name="ci_portable_code"><h4><hr size=0>Write Portable Code</h4><ul>
				247
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	248	In almost all cases, it is possible and within reason to write completely
				249	portable code. If there are cases where it isn't possible to write portable
				250	code, isolate it behind a well defined (and well documented) interface.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	251
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	252	In practice, this means that you shouldn't assume much about the host compiler,
				253	including its support for "high tech" features like partial specialization of
				254	templates. In fact, Visual C++ 6 could be an important target for our work in
				255	the future, and we don't want to have to rewrite all of our code to support
				256	it.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	257
				258
				259
				260	<!-- *********************************************************************** -->
				261	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				262	<a name="styleissues">Style Issues
				263	</b></font></td></tr></table><ul>
				264	<!-- *********************************************************************** -->
				265
				266
				267	<!-- ======================================================================= -->
				268	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td> </td><td width="100%">  <font color="#EEEEFF" face="Georgia,Palatino"><b>
				269	<a name="macro">The High Level Issues
				270	</b></font></td></tr></table><ul>
				271
				272
				273	<!-- _______________________________________________________________________ -->
				274	</ul><a name="hl_module"><h4><hr size=0>A Public Header File <b>is</b> a Module</h4><ul>
				275
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	276	C++ doesn't do too well in the modularity department. There is no real
				277	encapsulation or data hiding (unless you use expensive protocol classes), but it
				278	is what we have to work with. When you write a public header file (in the LLVM
				279	source tree, they live in the top level "include" directory), you are defining a
				280	module of functionality.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	281
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	282	Ideally, modules should be completely independent of each other, and their
				283	header files should only include the absolute minimum number of headers
				284	possible. A module is not just a class, a function, or a namespace: <a
				285	href="http://www.cuj.com/articles/2000/0002/0002c/0002c.htm">it's a collection
				286	of these</a> that defines an interface. This interface may be several
				287	functions, classes or data structures, but the important issue is how they work
				288	together.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	289
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	290	In general, a module should be implemented with one or more <tt>.cpp</tt> files.
				291	Each of these <tt>.cpp</tt> files should include the header that defines their
				292	interface first. This ensure that all of the dependences of the module header
				293	have been properly added to the module header itself, and are not implicit.
				294	System headers should be included after user headers for a translation unit.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	295
				296
				297	<!-- _______________________________________________________________________ -->
				298	</ul><a name="hl_dontinclude"><h4><hr size=0>#include as Little as Possible</h4><ul>
				299
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	300	<tt>#include</tt> hurts compile time performance. Don't do it unless you have
				301	to, especially in header files.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	302
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	303	But wait, sometimes you need to have the definition of a class to use it, or to
				304	inherit from it. In these cases go ahead and #include that header file. Be
				305	aware however that there are many cases where you don't need to have the full
				306	definition of a class. If you are using a pointer or reference to a class, you
				307	don't need the header file. If you are simply returning a class instance from a
				308	prototyped function or method, you don't need it. In fact, for most cases, you
				309	simply don't need the definition of a class... and not <tt>#include</tt>'ing
				310	speeds up compilation.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	311
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	312	It is easy to try to go too overboard on this recommendation, however. You
				313	<b>must</b> include all of the header files that you are using, either directly
				314	or indirectly (through another header file). To make sure that you don't
				315	accidently forget to include a header file in your module header, make sure to
				316	include your module header <b>first</b> in the implementation file (as mentioned
				317	above). This way there won't be any hidden dependencies that you'll find out
				318	about later...<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	319
				320
				321	<!-- _______________________________________________________________________ -->
				322	</ul><a name="hl_privateheaders"><h4><hr size=0>Keep "internal" Headers Private</h4><ul>
				323
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	324	Many modules have a complex implementation that causes them to use more than one
				325	implementation (<tt>.cpp</tt>) file. It is often tempting to put the internal
				326	communication interface (helper classes, extra functions, etc) in the public
				327	module header file. Don't do this. :)<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	328
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	329	If you really need to do something like this, put a private header file in the
				330	same directory as the source files, and include it locally. This ensures that
				331	your private interface remains private and undisturbed by outsiders.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	332
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	333	Note however, that it's okay to put extra implementation methods a public class
				334	itself... just make them private (or protected), and all is well.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	335
				336
				337	<!-- ======================================================================= -->
				338	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td> </td><td width="100%">  <font color="#EEEEFF" face="Georgia,Palatino"><b>
				339	<a name="micro">The Low Level Issues
				340	</b></font></td></tr></table><ul>
				341
				342
				343	<!-- _______________________________________________________________________ -->
				344	</ul><a name="hl_assert"><h4><hr size=0>Assert Liberally</h4><ul>
				345
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	346	Use the "<tt>assert</tt>" function to its fullest. Check all of your
				347	preconditions and assumptions, you never know when a bug (not neccesarily even
				348	yours) might be caught early by an assertion, which reduces debugging time
				349	dramatically. The "<tt><cassert></tt>" header file is probably already
				350	included by the header files you are using, so it doesn't cost anything to use
				351	it.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	352
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	353	To further assist with debugging, make sure to put some kind of error message in
				354	the assertion statement (which is printed if the assertion is tripped). This
				355	helps the poor debugging make sense of why an assertion is being made and
				356	enforced, and hopefully what to do about it. Here is one complete example:<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	357
				358	<pre>
				359	inline Value *getOperand(unsigned i) {
Chris Lattner	b00c582	2001-10-02 03:41:24 +0000	[diff] [blame]	360	assert(i < Operands.size() && "getOperand() out of range!");
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	361	return Operands[i];
				362	}
				363	</pre>
				364
				365	Here are some examples:
				366
				367	<pre>
Chris Lattner	b00c582	2001-10-02 03:41:24 +0000	[diff] [blame]	368	assert(Ty->isPointerType() && "Can't allocate a non pointer type!");
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	369
				370	assert((Opcode == Shl \|\| Opcode == Shr) && "ShiftInst Opcode invalid!");
				371
Chris Lattner	b00c582	2001-10-02 03:41:24 +0000	[diff] [blame]	372	assert(idx < getNumSuccessors() && "Successor # out of range!");
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	373
				374	assert(V1.getType() == V2.getType() && "Constant types must be identical!");
				375
Chris Lattner	b00c582	2001-10-02 03:41:24 +0000	[diff] [blame]	376	assert(isa<PHINode>(Succ->front()) && "Only works on PHId BBs!");
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	377	</pre><p>
				378
				379	You get the idea...<p>
				380
				381
				382	<!-- _______________________________________________________________________ -->
				383	</ul><a name="hl_preincrement"><h4><hr size=0>Prefer Preincrement</h4><ul>
				384
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	385	Hard fast rule: Preincrement (++X) may be no slower than postincrement (X++) and
				386	could very well be a lot faster than it. Use preincrementation whenever
				387	possible.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	388
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	389	The semantics of postincrement include making a copy of the value being
				390	incremented, returning it, and then preincrementing the "work value". For
				391	primitive types, this isn't a big deal... but for iterators, it can be a huge
				392	issue (for example, some iterators contains stack and set objects in them...
				393	copying an iterator could invoke the copy ctor's of these as well). In general,
				394	get in the habit of always using preincrement, and you won't have a problem.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	395
				396
				397	<!-- _______________________________________________________________________ -->
Chris Lattner	13c4659	2002-01-20 19:01:26 +0000	[diff] [blame]	398	</ul><a name="hl_avoidendl"><h4><hr size=0>Avoid endl</h4><ul>
				399
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	400	The <tt>endl</tt> modifier, when used with iostreams outputs a newline to the
				401	output stream specified. In addition to doing this, however, it also flushes
				402	the output stream. In other words, these are equivalent:<p>
Chris Lattner	13c4659	2002-01-20 19:01:26 +0000	[diff] [blame]	403
				404	<pre>
				405	cout << endl;
				406	cout << "\n" << flush;
				407	</pre>
				408
				409	Most of the time, you probably have no reason to flush the output stream, so it's better to use a literal <tt>"\n"</tt>.<p>
				410
				411
				412	<!-- _______________________________________________________________________ -->
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	413	</ul><a name="hl_exploitcpp"><h4><hr size=0>Exploit C++ to its Fullest</h4><ul>
				414
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	415	C++ is a powerful language. With a firm grasp on its capabilities, you can make
				416	write effective, consise, readable and maintainable code all at the same time.
				417	By staying consistent, you reduce the amount of special cases that need to be
				418	remembered. Reducing the total number of lines of code you write is a good way
				419	to avoid documentation, and avoid giving bugs a place to hide.<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	420
Misha Brukman	2d10d75	2003-07-28 21:57:18 +0000	[diff] [blame]	421	For these reasons, come to know and love the contents of your local
				422	<algorithm> header file. Know about <functional> and what it can do
				423	for you. C++ is just a tool that wants you to master it. :)<p>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	424
				425
				426
				427	<!-- ======================================================================= -->
				428	</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0><tr><td> </td><td width="100%">  <font color="#EEEEFF" face="Georgia,Palatino"><b>
				429	<a name="iterators">Writing Iterators
				430	</b></font></td></tr></table><ul>
				431
				432	Here's a pretty good summary of how to write your own data structure iterators in a way that is compatible with the STL, and with a lot of other code out there (slightly edited by Chris):<p>
				433
				434	<pre>
				435	From: Ross Smith <ross.s@ihug.co.nz>
				436	Newsgroups: comp.lang.c++.moderated
				437	Subject: Writing iterators (was: Re: Non-template functions that take iterators)
				438	Date: 28 Jun 2001 12:07:10 -0400
				439
				440	Andre Majorel wrote:
				441	> Any pointers handy on "writing STL-compatible iterators for
				442	> dummies ?"
				443
				444	I'll give it a try...
				445
				446	The usual situation requiring user-defined iterators is that you have
				447	a type that bears some resemblance to an STL container, and you want
				448	to provide iterators so it can be used with STL algorithms. You need
				449	to ask three questions:
				450
				451	First, is this simply a wrapper for an underlying collection of
				452	objects that's held somewhere as a real STL container, or is it a
				453	"virtual container" for which iteration is (under the hood) more
				454	complicated than simply incrementing some underlying iterator (or
				455	pointer or index or whatever)? In the former case you can frequently
				456	get away with making your container's iterators simply typedefs for
				457	those of the underlying container; your begin() function would call
				458	member_container.begin(), and so on.
				459
				460	Second, do you only need read-only iterators, or do you need separate
				461	read-only (const) and read-write (non-const) iterators?
				462
				463	Third, which kind of iterator (input, output, forward, bidirectional,
				464	or random access) is appropriate? If you're familiar with the
				465	properties of the iterator types (if not, visit
				466	<a href="http://www.sgi.com/tech/stl/">http://www.sgi.com/tech/stl/</a>), the appropriate choice should be
				467	obvious from the semantics of the container.
				468
				469	I'll start with forward iterators, as the simplest case that's likely
				470	to come up in normal code. Input and output iterators have some odd
				471	properties and rarely need to be implemented in user code; I'll leave
				472	them out of discussion. Bidirectional and random access iterators are
				473	covered below.
				474
				475	The exact behaviour of a forward iterator is spelled out in the
				476	Standard in terms of a set of expressions with specified behaviour,
				477	rather than a set of member functions, which leaves some leeway in how
				478	you actually implement it. Typically it looks something like this
				479	(I'll start with the const-iterator-only situation):
				480
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	481	#include <iterator>
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	482
				483	class container {
				484	public:
				485	typedef something_or_other value_type;
				486	class const_iterator:
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	487	public std::iterator<std::forward_iterator_tag, value_type> {
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	488	friend class container;
				489	public:
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	490	const value_type& operator*() const;
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	491	const value_type* operator->() const;
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	492	const_iterator& operator++();
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	493	const_iterator operator++(int);
				494	friend bool operator==(const_iterator lhs,
				495	const_iterator rhs);
				496	friend bool operator!=(const_iterator lhs,
				497	const_iterator rhs);
				498	private:
				499	//...
				500	};
				501	//...
				502	};
				503
				504	An iterator should always be derived from an instantiation of the
				505	std::iterator template. The iterator's life cycle functions
				506	(constructors, destructor, and assignment operator) aren't declared
				507	here; in most cases the compiler-generated ones are sufficient. The
				508	container needs to be a friend of the iterator so that the container's
				509	begin() and end() functions can fill in the iterator's private members
				510	with the appropriate values.
				511
				512	<i>[Chris's Note: I prefer to not make my iterators friends. Instead, two
				513	ctor's are provided for the iterator class: one to start at the end of the
				514	container, and one at the beginning. Typically this is done by providing
				515	two constructors with different signatures.]</i>
				516
				517	There are normally only three member functions that need nontrivial
				518	implementations; the rest are just boilerplate.
				519
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	520	const container::value_type&
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	521	container::const_iterator::operator*() const {
				522	// find the element and return a reference to it
				523	}
				524
				525	const container::value_type*
				526	container::const_iterator::operator->() const {
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	527	return &**this;
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	528	}
				529
				530	If there's an underlying real container, operator*() can just return a
				531	reference to the appropriate element. If there's no actual container
				532	and the elements need to be generated on the fly -- what I think of as
				533	a "virtual container" -- things get a bit more complicated; you'll
				534	probably need to give the iterator a value_type member object, and
				535	fill it in when you need to. This might be done as part of the
				536	increment operator (below), or if the operation is nontrivial, you
				537	might choose the "lazy" approach and only generate the actual value
				538	when one of the dereferencing operators is called.
				539
				540	The operator->() function is just boilerplate around a call to
				541	operator*().
				542
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	543	container::const_iterator&
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	544	container::const_iterator::operator++() {
				545	// the incrementing logic goes here
				546	return *this;
				547	}
				548
				549	container::const_iterator
				550	container::const_iterator::operator++(int) {
				551	const_iterator old(*this);
				552	++*this;
				553	return old;
				554	}
				555
				556	Again, the incrementing logic will usually be trivial if there's a
				557	real container involved, more complicated if you're working with a
				558	virtual container. In particular, watch out for what happens when you
				559	increment past the last valid item -- this needs to produce an
				560	iterator that will compare equal to container.end(), and making this
				561	work is often nontrivial for virtual containers.
				562
				563	The post-increment function is just boilerplate again (and
				564	incidentally makes it obvious why all the experts recommend using
				565	pre-increment wherever possible).
				566
				567	bool operator==(container::const_iterator lhs,
				568	container::const_iterator rhs) {
				569	// equality comparison goes here
				570	}
				571
				572	bool operator!=(container::const_iterator lhs,
				573	container::const_iterator rhs) {
				574	return !(lhs == rhs);
				575	}
				576
				577	For a real container, the equality comparison will usually just
				578	compare the underlying iterators (or pointers or indices or whatever).
				579	The semantics of comparisons for virtual container iterators are often
				580	tricky. Remember that iterator comparison only needs to be defined for
				581	iterators into the same container, so you can often simplify things by
				582	taking for granted that lhs and rhs both point into the same container
				583	object. Again, the second function is just boilerplate.
				584
				585	It's a matter of taste whether iterator arguments are passed by value
				586	or reference; I've shown tham passed by value to reduce clutter, but
				587	if the iterator contains several data members, passing by reference
				588	may be better.
				589
				590	That convers the const-iterator-only situation. When we need separate
				591	const and mutable iterators, one small complication is added beyond
				592	the simple addition of a second class.
				593
				594	class container {
				595	public:
				596	typedef something_or_other value_type;
				597	class const_iterator;
				598	class iterator:
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	599	public std::iterator<std::forward_iterator_tag, value_type> {
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	600	friend class container;
				601	friend class container::const_iterator;
				602	public:
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	603	value_type& operator*() const;
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	604	value_type* operator->() const;
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	605	iterator& operator++();
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	606	iterator operator++(int);
				607	friend bool operator==(iterator lhs, iterator rhs);
				608	friend bool operator!=(iterator lhs, iterator rhs);
				609	private:
				610	//...
				611	};
				612	class const_iterator:
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	613	public std::iterator<std::forward_iterator_tag, value_type> {
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	614	friend class container;
				615	public:
				616	const_iterator();
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	617	const_iterator(const iterator& i);
				618	const value_type& operator*() const;
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	619	const value_type* operator->() const;
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	620	const_iterator& operator++();
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	621	const_iterator operator++(int);
				622	friend bool operator==(const_iterator lhs,
				623	const_iterator rhs);
				624	friend bool operator!=(const_iterator lhs,
				625	const_iterator rhs);
				626	private:
				627	//...
				628	};
				629	//...
				630	};
				631
				632	There needs to be a conversion from iterator to const_iterator (so
				633	that mixed-type operations, such as comparison between an iterator and
				634	a const_iterator, will work). This is done here by giving
				635	const_iterator a conversion constructor from iterator (equivalently,
				636	we could have given iterator an operator const_iterator()), which
				637	requires const_iterator to be a friend of iterator, so it can copy its
				638	data members. (It also requires the addition of an explicit default
				639	constructor to const_iterator, since the existence of another
				640	user-defined constructor inhibits the compiler-defined one.)
				641
				642	Bidirectional iterators add just two member functions to forward
				643	iterators:
				644
				645	class iterator:
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	646	public std::iterator<std::bidirectional_iterator_tag, value_type> {
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	647	public:
				648	//...
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	649	iterator& operator--();
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	650	iterator operator--(int);
				651	//...
				652	};
				653
				654	I won't detail the implementations, they're obvious variations on
				655	operator++().
				656
				657	Random access iterators add several more member and friend functions:
				658
				659	class iterator:
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	660	public std::iterator<std::random_access_iterator_tag, value_type> {
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	661	public:
				662	//...
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	663	iterator& operator+=(difference_type rhs);
				664	iterator& operator-=(difference_type rhs);
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	665	friend iterator operator+(iterator lhs, difference_type rhs);
				666	friend iterator operator+(difference_type lhs, iterator rhs);
				667	friend iterator operator-(iterator lhs, difference_type rhs);
				668	friend difference_type operator-(iterator lhs, iterator rhs);
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	669	friend bool operator<(iterator lhs, iterator rhs);
				670	friend bool operator>(iterator lhs, iterator rhs);
				671	friend bool operator<=(iterator lhs, iterator rhs);
				672	friend bool operator>=(iterator lhs, iterator rhs);
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	673	//...
				674	};
				675
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	676	container::iterator&
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	677	container::iterator::operator+=(container::difference_type rhs) {
				678	// add rhs to iterator position
				679	return *this;
				680	}
				681
Chris Lattner	f7235cd	2003-04-23 16:25:38 +0000	[diff] [blame]	682	container::iterator&
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	683	container::iterator::operator-=(container::difference_type rhs) {
				684	// subtract rhs from iterator position
				685	return *this;
				686	}
				687
				688	container::iterator operator+(container::iterator lhs,
				689	container::difference_type rhs) {
				690	return iterator(lhs) += rhs;
				691	}
				692
				693	container::iterator operator+(container::difference_type lhs,
				694	container::iterator rhs) {
				695	return iterator(rhs) += lhs;
				696	}
				697
				698	container::iterator operator-(container::iterator lhs,
				699	container::difference_type rhs) {
				700	return iterator(lhs) -= rhs;
				701	}
				702
				703	container::difference_type operator-(container::iterator lhs,
				704	container::iterator rhs) {
				705	// calculate distance between iterators
				706	}
				707
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	708	bool operator<(container::iterator lhs, container::iterator rhs) {
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	709	// perform less-than comparison
				710	}
				711
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	712	bool operator>(container::iterator lhs, container::iterator rhs) {
				713	return rhs < lhs;
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	714	}
				715
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	716	bool operator<=(container::iterator lhs, container::iterator rhs) {
				717	return !(rhs < lhs);
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	718	}
				719
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	720	bool operator>=(container::iterator lhs, container::iterator rhs) {
				721	return !(lhs < rhs);
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	722	}
				723
				724	Four of the functions (operator+=(), operator-=(), the second
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	725	operator-(), and operator<()) are nontrivial; the rest are
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	726	boilerplate.
				727
				728	One feature of the above code that some experts may disapprove of is
				729	the declaration of all the free functions as friends, when in fact
				730	only a few of them need direct access to the iterator's private data.
				731	I originally got into the habit of doing this simply to keep the
				732	declarations together; declaring some functions inside the class and
				733	some outside seemed awkward. Since then, though, I've been told that
				734	there's a subtle difference in the way name lookup works for functions
				735	declared inside a class (as friends) and outside, so keeping them
				736	together in the class is probably a good idea for practical as well as
				737	aesthetic reasons.
				738
				739	I hope all this is some help to anyone who needs to write their own
				740	STL-like containers and iterators.
				741
				742	--
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	743	Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	744	</pre>
				745
				746
				747	<!-- *********************************************************************** -->
				748	</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0><tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
				749	<a name="seealso">See Also
				750	</b></font></td></tr></table><ul>
				751	<!-- *********************************************************************** -->
				752
				753	A lot of these comments and recommendations have been culled for other sources. Two particularly important books for our work are:<p>
				754
				755	<ol>
				756	<li><a href="http://www.aw.com/product/0,2627,0201924889,00.html">Effective C++</a> by Scott Meyers. There is an online version of the book (only some chapters though) <a href="http://www.awlonline.com/cseng/meyerscddemo/">available as well</a>.
				757	<li><a href="http://cseng.aw.com/book/0,3828,0201633620,00.html">Large-Scale C++ Software Design</a> by John Lakos
				758	</ol><p>
				759
				760	If you get some free time, and you haven't read them: do so, you might learn something. :)
				761
				762
				763	<!-- *********************************************************************** -->
				764	</ul>
				765	<!-- *********************************************************************** -->
				766
				767	<hr>
				768	<font size=-1>
				769	<address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
				770	<!-- Created: Tue Jan 23 15:19:28 CST 2001 -->
				771	<!-- hhmts start -->
Chris Lattner	2e5cbc2	2003-08-07 21:45:47 +0000	[diff] [blame^]	772	Last modified: Thu Aug 7 16:44:33 CDT 2003
Chris Lattner	d80c43c	2001-07-09 03:27:08 +0000	[diff] [blame]	773	<!-- hhmts end -->
				774	</font>
				775	</body></html>