.NET Daily Quiz Archive - week 1

The following is an archive of the first week of daily quizzes which I have been sending to my colleagues. They are intended to be a exercises for .NET developers to test fundamentals and gotchas in the framework and C# programming language. I will be posting weekly quiz archives going forward.

Daily Quiz #001
Can you spot the potential deadlock in this code?

public class FileMonitor {
  private object _lock = new object();
  public event EventHandler FileCreated;
  protected void GenerateNewFile(string filename) {
    lock (_lock) {
      File.Create(filename);
      _currentFile = new FileInfo(filename);
      FileCreated(this, EventArgs.Empty);
    }
  }
  private FileInfo _currentFile;
  public FileInfo CurrentFile {
    get {
      lock (_lock)
        return _currentFile;
    }
  }
}

How would you work around this? What principles or lessons can we learn from this?

Answer
Say the client code attaches this event handler:

private void FileCreated(object sender, EventArgs args) {
	Console.WriteLine(_fileMonitor.CurrentFile.FullPath);
}

You may execute this code and it seems fine. In a single-threaded application this code will execute without deadlocking.

Now try running the FileMonitor in a background thread and marshalling the event handler code to you UI thread in a Windows Forms / WPF application.

When the UI thread accesses FileMonitor.CurrentFile it will try to acquire the synchronization lock around _currentFile. The event source has this lock and will not return until the event handler returns, which can't happen while the lock cannot be acquired - you are deadlocked.

Why doesn't this code deadlock in a single-threaded application? According to the C# specification (8.12):
"While a mutual-exclusion lock is held, code executing in the same execution thread can also obtain and release the lock. In contrast, code executing in other threads is blocked from obtaining the lock until the lock is released."

What is the lesson here? Never call unknown code from inside a locked statement block. Unknown code, by definition, could call anything within your data structures. It's foolish to try to design around this - avoid the problem by never calling unknown code while locked.
Unknown code includes events, any delegates (Action, Func, etc) passed into your method/class as a parameter and even virtual methods within your class. A client of your code could very easily write a subclass that accesses your locked statements from another thread.


Daily Quiz #002

You're reading a CSV file using the following methods, which returns a sequence of sequences of numbers:

public static IEnumerable ReadLines(this TextReader reader) {
  var txt = reader.ReadLine();
  while (txt != null) {
    yield return txt;
    txt = reader.ReadLine();
  }
}
public static int Parse(this string input) {
  int val;
  return int.TryParse(input, out val) ? val : default(int);
}
public static IEnumerable<IEnumerable> ReadCsv(TextReader reader) {
  var lines = from line in ReadLines(reader) select line.Split(',');
  var result = from line in lines
               select from num in line
			          select item.Parse()
  return result;
}

You call the code like so:

IEnumerable<IEnumerable> numberLines = null
// close the file when we're done reading
using (var reader = new StreamReader("file.csv")) {
  numberLines = ReadCsv(reader);
}
// do stuff with the results
foreach (var line in numberLines) {
  foreach (var num in line) {
    Console.WriteLine(num);
  }
}

The application throws an exception. Without compiling the code, where, and why? Assume the file exists and is readable and well-formatted.

Answer

We tried to read from the file after closing it. LINQ expressions are not executed eagerly, but are accessed on demand. Because the TextReader was placed inside a using block but the code was executed later, when we tried to access the contents of the file in our query expression the file was no longer available.

This was relatively easy to spot in this example, but what if we had returned the IEnumerable> from a method? Then the client code may have no visibility over what it is accessing and the conditions of the query expression.

There are several possible solutions to this problem. Consider encapsulating the TextReader resource in a single method - which method would you choose?
Beware of multiple enumerations - if you're going to enumerate over the resource more than once then be very careful about where you will dispose of it.

For more see Bill Wagner's More Effective C#, Item 42: Avoid Capturing Expensive Resources. More coming from this chapter soon.


Daily Quiz #003

public struct A {
	public int _field1;
}
public class C {
	public A a = new A();
	public A b = new A();
}
var c = new C();

1. How many allocations did I just make? For how much memory?

C[] c = new C[100];

2. How many allocations? How much memory?

public class B {
	public int _field1;
}
public class D {
	public B a = new B();
	public B b = new B();
}
var d = new D();

3. How many allocation? How much memory?

D[] d = new D[100];

4. This time?

Note: by "allocations" I mean allocations on the heap. Stack space is comparatively cheap.

Answer
See comments for a slight correction on this answer.
1) One allocation for 8 bytes. structs are value types and are allocated in-line.

2) One allocation of 400 bytes (100 * sizeof(a)).

3) Three allocations, one for 12 bytes (assuming 32-bit pointers, 4 bytes per field plus 4 bytes for superclass pointer) and two for 8 bytes each (is someone able to confirm this? I couldn't find precise documentation in the spec. Email me!)

4) One allocation for 100*sizeof(c). However, each member of the array is null-initialized. Populating the array will take a further 100 allocations for a total of 101 allocations. In number 2 all members are allocated inline and default-initialized. Modifying these already-initialized members is much more efficient than allocating new heap space!

The important part here is the number of allocations, not the memory usage. Memory isn't the only consideration when deciding whether to use value types or reference types. There is a semantic difference and there is a major performance difference if you're allocating a lot of memory. Heap allocation is expensive. Inline allocation of value types is much cheaper.


Daily Quiz #004

What are the three main principles that GetHashCode() must ALWAYS follow? Why are these important?

Answer
1. GetHashCode must be instance invariant. Method calls on the object should not change the hash value.
2. Objects that are equal (as defined by operator==) must return the same hash code.
3. Hash functionn should generate a random distribution aceoss all integers.


Daily Quiz #005

I write the following code:

using System;
public abstract class Base {
	public virtual event EventHandler MyEvent;
	public virtual void Foo() {
		if (MyEvent != null) {
			MyEvent(this, EventArgs.Empty);
		}
	}
}
public class Derived : Base {
	public override event EventHandler MyEvent;
	public override void Foo() {
		Console.WriteLine("overriden");
		base.Foo();
	}
}
public class M {
	public static void Main(string[] args) {
		Base b = new Derived();
		b.MyEvent += (o,e) => Console.WriteLine("Event raised");
		b.Foo();
	}
}

Output:
overriden

Why does it appear that the event is never raised? Hint: this one is quite subtle and involves code generated by the compiler.

Answer:
When we declare the virtual event in Base:
public virtual event EventHandler MyEvent;
the compiler generates (roughly) the following code:

private EventHandler myEvent;
public virtual event EventHandler MyEvent {
	[MethodImpl(MethodOptions.Synchronized)]
	add { myEvent += value; }
	[MethodImpl(MethodOptions.Synchronized)]
	remove { myEvent -= value; }
}

Note the private backing field for the event property. When Dervied declares the event override, (almost) the same code is generated in Derived. The private field (Base.myEvent) is now hidden.
Declaring the derived event means that the hidden backing field in Base is no longer assigned when clients attach to the virtual event, and there is no code in Derived to raise the new backing event field.

One possible fix is to override the event using property syntax:

public class Derived : Base {
	public override event EventHandler MyEvent {
		add { base.MyEvent += value; }
		remove { base.MyEvent -= value; }
	}
	// etc.
}

The problem now is that only Base can raise the event. Derived has no access to the private backing field of the event and cannot raise it (just like client code cannot raise an event).

Another possible solution is to raise the event in a virtual method in Base:

public class Base {
	public virtual event EventHandler MyEvent;
	public virtual void RaiseEvent() {
		if (MyEvent != null) MyEvent(this, EventArgs.Empty);
	}
}

But at this stage what have you gained by making the event virtual? You can achieve everything you needed to in your virtual event override in the virual method override.

Bottom line: avoid virtual events. It's not worth the hassle and there's almost always a better way.

Bonus: declare your events with an empty delegate to avoid having to check for a null event each time you call them:

public event EventHandler MyEvent = delegate { };

instead of
public event EventHandler MyEvent;

Splines and curves part I - Bézier Curves

In this series I want to give an introduction to curves and splines for the programmer. These are typically used in computer graphics, game design scenarios (especially camera motion) and engineering to generate smooth shapes from simple datasets.

Hopefully by the end of this series you will be able to not only generate your own curves in your program, but will understand why they are formed the way they are and have the tools to understand which curve technique to select for your own scenarios.

Splines were originally a tool for engineering draftsman for building smooth curves in disciplines like boat-building to generate smooth curves using control points. The flexibility of the flat metal or wood spline along with the placement and constraint of the control points defined the shape of the curve. Most spline techniques in mathematics and software borrow from these ideas to form the shapes desired by the user.

Wikipedia defines splines in the mathematical context as

In mathematics, a spline is a smooth polynomial function that is piecewise-defined, and possesses a high degree of smoothness at the places where the polynomial pieces connect (which are known as knots).

We'll get into what exactly is meant by "high degree of smoothness" and the other technical terms as we go. For now you can think of a spline as a series of points which we will generally define parametrically over the unit interval, determined by some spline function. We are free to determine the number of points along the interval depending on the context in which the spline is to be used.

As an aside, did you know that the famous Utah Teapot is defined as a set of control points over which we build splines with an arbitrary number of points over each interval? The number of points drawn over each curve interval determines the number of polygons drawn, which is what is meant by the previous paragraph. Using a single small data set we can build a teapot with an arbitrary number of polygons. Neat, huh?

Approximation versus Interpolation

Before we get started it's important to note the difference between an approximation technique and an interpolation technique for curve generation. All curves are defined interactively by placing control points. If the algorithm for generating the curve passes through all control points then it is referred to as an interpolation algorithm. Algorithms that build curves that are affected by the control points but don't necessarily pass through them all are referred to as approximation algorithms. Which one you use will depend on your particular use case. We will explore the differences in more detail further down.

Bézier curves

The first curve we will investigate is the infamous Bezier curve. It should be noted that the Bezier curve is not, in fact, a spline, but it's still a useful starting point. We will start with an example, and delve into some details of how this curve works and why. Note that the interactive examples in this article use the HTML5 canvas element so may not work correctly on older browsers and some mobile devices. Hover your mouse over the curve to see how it is constructed.


Hover over canvas to see line construction. Click & drag control points to modify line.

This is a quadratic Bezier, which is a fancy way of saying it's a Bezier curve with 3 control points (the reason for the names quadratic, cubic etc will become clear soon). So what's going on here? You can see when you hover your mouse over the above image that as we vary t, we take the parametric point t along each of the lines that form our control points (I have drawn these straight lines in light grey for your convenience). We then take these new points and draw a line between them. The point that determines the point t on our curve is the point t along this new line.

We can implement this quadratic Bezier using an algorithm known as de Casteljau's Algorithm. It is essentially a sequence of tweening steps, in this case to generate a part of a parabola. Think of it like this: if we label the two straight lines defined by our three control points A and B, we linearly interpolate across these lines and then repeat the interpolation to find the point P(t) that resides a fraction t of the way between A(t) and B(t):
$$ A(t) = (1 - t){P_0} + t{P_1} $$
$$ B(t) = (1 - t){P_1} + t{P_2} $$
$$ P(t) = (1 - t)A + tB $$

You can see we're using the basic linear interpolation formula for parametric lines here. If you're not familiar with linear interpolation then read up!

Anyway, by direct substitution (try this out on paper if you like) we can get to this formula for P(t):
$$ P(t) = {{(1 - t)}^2}{P_0} + 2t(1 - t){P_1} + {t^2}{P_2} $$

Here's the code I have used to implement this in Javascript. Please note that most of the code in this guide is rushed and not optimal. This article is more about the concepts than the code, and you should put some thought into how to write optimal versions before you implement your own. Also, for the supporting code around this check out the bottom of this post, I'll include the code I used for drawing, mouse events, etc at the end because it's not directly relevant to this post.

function quadraticBezier(clicks, ctx) {
function bezierFunc(points, t) {
var p0 = points[0];
var p1 = points[1];
var p2 = points[2];
var t2 = t*t;
var dx = dot([p0.x, p1.x, p2.x], [(1-t)*(1-t), 2*t*(1-t), t2]);
var dy = dot([p0.y, p1.y, p2.y], [(1-t)*(1-t), 2*t*(1-t), t2]);
return point(dx,dy);
}
var p = [];
for (var j = 0; j < lineSegments+1; j++) {
p.push(bezierFunc(controlPoints, j/lineSegments));
}
curveSegment(p, ctx);
}
function dot(v1, v2) {
var sum = 0;
for (var i = 0; i < v1.length; i++) {
sum += v1[i]*v2[i];
}
return sum;
}
function lineSegment(p0, p1, ctx) {
ctx.beginPath();
ctx.moveTo(p0.x,p0.y);
ctx.lineTo(p1.x,p1.y);
ctx.stroke();
ctx.closePath();
}
function point(x, y) {
return {
x:x,
y:y
};
}
function curveSegment(points, ctx) {
ctx.lineWidth = 2;
ctx.strokeStyle = '#000';
for (var i = 0; i < points.length-1; i++) {
lineSegment(points[i], points[i+1], ctx);
}
}

In this code I am using a dot product that I defined to make multiplying over points a little cleaner. You don't have to do it this way but I prefer it. Also some libraries have extremely efficient matrix and vector multiplication algorithms so I tend to gravitate towards these functions.

To explain very briefly what's happening in this code, given a set of control points we take the first three (we're only dealing with quadratic Beziers for now) and apply the above formula. We can use a dot product because each control point appears once and only once in the formula, which is thankfully true of Bezier curves of all degree.

We can extend this technique to Bezier curves of higher order. To generate a cubic Bezier curve, we add another control point. We then apply the same interpolation we just did across the first three points, and we apply that interpolation across the last three points. Finally we interpolate across the two points we have just generated with respect to t and this point defines our curve at t. See the demonstration below, where the blue line represents our newly interpolated line:

Hover over canvas to see line construction. Click & drag control points to modify line.

It's not difficult to find the formula for the cubic Bezier (left as an exercise):
$$ P(t) = {P_0}{{(1-t)}^3} + {P_1}3{{(1-t)}^2}t + {P_2}3(1-t){t^2} + {P_3}{t^3} $$

For completeness, here is the code to generate this curve, which is very similar to the previous code.

function cubicBezier(controlPoints, ctx) {
function bezierFunc(points, t) {
var p0 = points[0];
var p1 = points[1];
var p2 = points[2];
var p3 = points[3];
var t3 = t*t*t;
var t2 = t*t;
var dx = dot([p0.x, p1.x, p2.x, p3.x], [(1-t)*(1-t)*(1-t), 3*(1-t)*(1-t)*t, 3*(1-t)*t2, t3]);
var dy = dot([p0.y, p1.y, p2.y, p3.y], [(1-t)*(1-t)*(1-t), 3*(1-t)*(1-t)*t, 3*(1-t)*t2, t3]);
return point(dx,dy);
}
var p = [];
for (var j = 0; j < lineSegments+1; j++) {
p.push(bezierFunc(controlPoints, j/lineSegments));
}
curveSegment(p, ctx);
}

In fact, we can extend this to arbitrary degrees. The terms by which we multiply each of our control points turn out to be (for reasons outside the scope of this article) the Bernstein polynomials. You can get these terms by raising the expression \( a(t) = (1 - t + t) \) to the nth power (of course this expression is simply a(t) = 1, so all terms always add to 1, an important result that we won't go into here, but if you're familiar with affine combinations you'll surely see why this is pretty nifty).

The Bezier curve extends to any number of control points using this Bernstein polynomial result thusly:
$$ P(t) = sum{k=0}{L}{P_k}{{B_k}^L}(t) $$
This is pretty cool, but not really used very widely because computing large polynomials is computationaly expensive and there are nicer alternatives for generating curves based on lots of control points. However you should certainly experiment with generating arbitrarily large Bezier curves.

Properties of Bezier curves
Bezier curves have some interesting properties that make them useful for certain purposes but less so for others. Bezier curves are approximation curves in that they don't pass through all control points, however they will always pass through their endpoints (can you see why, in terms of Bernstein polynomials?). This makes them useful for designers who need to visually generate smooth curves but need well-defined start and finish points.

Bezier curves are also affine invariant (hinted at earlier). This means we can use familiar matrix transformation techniques to shift the control points and the curve will transform as expected - rotating, scaling and skewing the curve is as simple as transforming the control points. This is extremely useful in CAD and graphics design contexts.

Another interesting property of Bezier curves is the convex hull property. All points on a Bezier curve are within a convex hull defined by the control points of the curve. If you don't know what a convex hull is then you probably don't need to, but I assume this property is useful for someone.

Problems with Bezier curves
Bezier curves are \( C^1 \) smooth functions. This means that the Bezier curve can generally be differentiated once across the unit interval. \( C^1 \) smoothness means that, for example, a camera following the curve along the unit interval at a constant speed (with respect to t) will move at a continuous velocity (not a constant velocity, but continuous with no breaks or jumps). With \( C^1 \) smoothness acceleration is not guaranteed to be continous.

Typically to get Bezier curves with more than 4 control points we will join multiple Bezier curves together. In this case the complete curve will be \( C^0 \) smooth, which means that the curve is continuous but the first derivative is not guaranteed to be, ie there could be jumps in velocity. This can be mitigated with careful placements of the control points. For more information of curve smoothness, read this.

The biggest problem with Bezier curves is the lack of local control over the curve. What I mean by this is that getting precisely the shape of the curve you want is difficult because changing a single control point in a Bezier curve will affect the entire curve. You can see from the formulae that each point on the curve (except for the endpoints) is affected to some degree by the position of the other points. Maybe other curve/spline types will allow us greater local control over our curve...

In the next article I will cover C-Spline and B-Spline curves and the famous Catmull Rom spline. We'll look at what it takes to work with \( C^2 \) smooth splines.

The (very rough) code I wrote for this article can be found on my Github repository.



Problem opening OpenXml files after modifying them programmatically? Read this.

Microsoft has some pretty good documentation around modifying OpenXml files using the System.IO.Packaging API, but I found every time I tried to open an Excel file I had modified it was telling me the file was damaged and needed to be repaired. The repair process would go ahead and remove the files I had modified from the package altogether. If I looked inside the XLSX file before doing the repair my changes were there and seemed to be just fine.

Turns out I was using the wrong combination of MIME type and compression when saving my changes into the package. The correct MIME type for OpenXML spreadsheet package parts is

application/vnd.openxmlformats-officedocument.spreadsheetml.connections+xml

and the compression level should be

CompressionOption.SuperFast

Here is a code snippet I'm using the save the package part.

string partContents = // some XML here
Uri partUri = new Uri(/*uri of part in package*/, UriKind.Relative);
const string OpenXmlSpreadsheetMime = "application/vnd.openxmlformats-officedocument.spreadsheetml.connections+xml";
var newPart = package.CreatePart(partUri, OpenXmlSpreadsheetMime, CompressionOption.SuperFast);
if (newPart != null)
{
    using (var stream = newPart.GetStream())
    using (var writer = new StreamWriter(stream))
    {
         writer.Write(partContents);
    }
}

The other OpenXML MIME types have been documented by Doug Mahugh:

File Extension: Content Type:
docm application/vnd.ms-word.document.macroEnabled.12
docx application/vnd.openxmlformats-officedocument.wordprocessingml.document
dotm application/vnd.ms-word.template.macroEnabled.12
dotx application/vnd.openxmlformats-officedocument.wordprocessingml.template
ppsm application/vnd.ms-powerpoint.slideshow.macroEnabled.12
ppsx application/vnd.openxmlformats-officedocument.presentationml.slideshow
pptm application/vnd.ms-powerpoint.presentation.macroEnabled.12
pptx application/vnd.openxmlformats-officedocument.presentationml.presentation
xlsb application/vnd.ms-excel.sheet.binary.macroEnabled.12
xlsm application/vnd.ms-excel.sheet.macroEnabled.12
xlsx application/vnd.openxmlformats-officedocument.spreadsheetml.sheet
xps application/vnd.ms-xpsdocument

Importing non-.rdl reports using Microsoft Dynamics CRM Web Services

This post is mostly for my own benefit for the future, in case I need to do this again.

I spent a good hour trying to figure out how to import XLSX reports into CRM using the web services, mostly because it's not clear how one should encode the report into the BodyBinary field of the Report object. For background details take a look at this article on MSDN, which gives most of the details except what I just mentioned.

The trick is to encode your report in a Base64 string, which doesn't seem to be documented anywhere. Failing to do this will result in an OrganizationServiceFault with the following message:

The field 'bodybinary' contains one or more invalid characters.

Here is the correct code for creating the Report object

var report = new Report
                {
                    Name = ReportName,
                    BodyBinary = Convert.ToBase64String(File.ReadAllBytes(ReportFileName)),
                    FileName = ReportFileName,
                    LanguageCode = ReportLanguageCode,
                    ReportTypeCode = 2 // 2 == "Existing File"
                };

How to include a large directory tree in a Wix installer using a Visual Studio Wix project

Wix is an awesome tool, but part of the challenge of using it is some dense and difficult to follow documentation. Today I spent a large amount of time trying to build an installer that included a very large directory tree without having to manually add each item. Hopefully this article will help get you through some of the problems I ran into while doing it.

My first approach was to use a HeatDirectory MSBuild task. When building a Wix project in Visual Studio this will cause heat.exe to be called in a pre-build step. For most cases this would work fine, but unforunately I couldn't make this work. The problem I ran into was

Error 1 The system cannot find the file '..\..\Very\Long\File\Path\...\BusinessServiceHostConfigurationImplementation.csproj.FileListAbsolute.txt' with type ''. light.exe

For the record, here is my original HeatDirectory build task. For most cases this will work perfectly fine.

<Target Name="BeforeBuild">
  <HeatDirectory
    DirectoryRefId="INSTALLLOCATION"
    OutputFile="source.wxs"
    Directory="..\..\MySourceDir"
    ComponentGroupName="SourceComponentGroup"
    ToolPath="$(WixToolPath)"
    PreprocessorVariable="var.SourcePath"
    AutogenerateGuids="true">
  

The issue here is that light.exe can't handle file paths of longer than 255 characters. If your file paths are very, very long then you may well be out of luck here - as far as I know there's no workaround for this problem.

Luckily for me I was working with folder paths that are long, but not absurdly long. I was just on the borderline so I figured if I copied the directory tree to some reasonable location like c:\st then I could work with light.exe.

The next issue here is that using these VS Wix projects the HeatDirectory tasks are executed even before pre-build steps. I elected to do the directory tree copy and heat.exe call in pre-build steps. To make the project build nicely without having to dick around too much with the Wix VS project I keep the target file in the project and overwrite it with my heat.exe target file. This way you can just check in an empty .wxs and things will work nicely.

Here is my pre-build event code that will copy the directory tree and execute Heat.exe

robocopy "$(SolutionDir)..\MySourcePath" %SystemDrive%\st /MIR
"%WIX%\bin\heat.exe" dir %SystemDrive%\st -dr INSTALLLOCATION -cg SourceComponentGroup -var var.SourcePath -ag -out "$(SolutionDir).\WixProject\source.wxs"

A couple of cool things you might want to take note of in case you don't know:
%WIX%: This is an environment variable set by the Wix installer. It points to your Wix installation directory, so getting to that /bin folder is nice and easy.
-var: This is an argument to heat.exe. Without it your output .wxs file will point all elements at SourceDir in their Source attribute. Yeah, I'll be fucked if I know why, but there you go. You can set this variable from your project properties:

Now that we have a new .wxs file in our solution just refer to this component group in your main Wix file using

<ComponentGroupRef Id="SourceComponentGroup"/>

in one of your features and you're all done.

Yeah, this isn't the most thrilling subject to read (or write) about, but it can be frustrating to figure this stuff out for yourself.