Blame - llvm/docs/CodingStandards.html - toolchain/llvm-project

blob: 18ce223c428873eea04a025edf504559fa54266e [file] [log] [blame]

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