August 12th, 2024

Embracing the power of the empty set in API design (and applying this principle to selectors and filters)

In mathematics, the empty set is a set with no members. This sounds totally useless, but it’s actually quite powerful.

Suppose you have a Widget object and a method GetChildren() that returns the child widgets. What should you do if the Widget has no children?

Sometimes, teams try to be clever and say, “Oh, if there are no children, then I will just return a null pointer instead of a list of child elements.” For example, IShell­Folder::Enum­Objects has the rule that if it returns S_FALSE, then it is allowed to return a null pointer instead of an enumerator.

As a result, this code is subtly wrong:

ComPtr<IEnumIDList> e;
if (SUCCEEDED(shellFolder->EnumObjects(hwnd, SHCONTF_FOLDERS, &e)) {
    for (CComHeapPtr<IDLIST_RELATIVE> child;
         e->Next(1, &child, nullptr) == S_OK;
         child.Free()) {
        // process the child folder
    }
}

The above code is at risk of crashing if there are no child folders: The IShellFolder implementation may chose to use the special case carve-out and return S_FALSE from the Enum­Objects method, and set e = nullptr. If that happens, then the enumeration loop crashes on a null pointer.

The correct code would have to check for this corner case and skip the enumeration loop. One way is to check for S_FALSE explicitly:

ComPtr<IEnumIDList> e;
HRESULT hr = shellFolder->EnumObjects(hwnd, SHCONTF_FOLDERS, &e);
if (SUCCEEDED(hr) && (hr != S_FALSE)) {                          
    for (CComHeapPtr<IDLIST_RELATIVE> child;
         e->Next(1, &child, nullptr) == S_OK;
         child.Free()) {
        // process the child folder
    }
}

Another is to check the enumerator object for null.

ComPtr<IEnumIDList> e;
if (SUCCEEDED(shellFolder->EnumObjects(hwnd, SHCONTF_FOLDERS, &e) && e) {
    for (CComHeapPtr<IDLIST_RELATIVE> child;
         e->Next(1, &child, nullptr) == S_OK;
         child.Free()) {
        // process the child folder
    }
}

Another is to check the return value for S_OK exactly:

ComPtr<IEnumIDList> e;
if (shellFolder->EnumObjects(hwnd, SHCONTF_FOLDERS, &e) == S_OK) {
    for (CComHeapPtr<IDLIST_RELATIVE> child;
         e->Next(1, &child, nullptr) == S_OK;
         child.Free()) {
        // process the child folder
    }
}

Regardless of how you deal with the issue, it doesn’t hide the fact that this special case is an extra bit of hassle, and more importantly, it’s the sort of hassle that is easily overlooked when writing code.

The obvious-looking code is wrong. The weird-looking code is correct. This is the opposite of what we want: We want the natural code to be the correct one.

The general rule for methods that return collections is therefore that if there are no items to return, then the methods should return empty collections, rather than null references. The empty set is a perfectly valid set, and existing algorithms operate properly on an empty set. For example, you iterate over an empty collection the same way as a nonempty collection.

The empty set also follows mathematical rules when applied to union and intersection. If you have collection of sets that happens to be empty, then mathematically, the union of the elements of the empty set is another empty set. And the intersection of the elements of the empty set is the entire universe.

When applied to functions, this means that if a method takes a set of criteria with the requirement that elements must match at least one of the criteria (a “selector” pattern), then an empty set selects no elements. On the other hand, if the requirement is that elements must match all of the criteria (a “filter” pattern), then an empty set selects all elements.¹

For example, suppose we have a method that finds all widgets of the specified colors:

IVectorView<Widget>
    FindWidgetsOfColors(IIterable<Color> colors);

What should happen if you pass an empty list of colors?

Well, since you didn’t specify any colors, then are no matching widgets, so mathematically speaking, this should return an empty vector. You might also choose to declare that choosing widgets by color must provide at least one color, so calling Find­Widgets­Of­Colors with an empty set of colors is allowed to fail with E_INVALID­ARG. But if you’re going to return something, you had better return the empty set. Do not design the function so that passing an empty list of colors returns all the widgets.

Conversely, suppose you have a method that finds widgets subject to filter criteria:

enum WidgetFilter
{
    Active,
    Connected,
};

IVectorView<Widget>
    FindWidgetsWithFilter(IIterable<WidgetFilter> filters);

What should happen if you pass an empty list of filters?

Mathematically, an empty list of filters is an unfiltered query, and you should return all the widgets. Again, you might decide that a filtered query must provide at least one filter, but if you choose to allow an empty list of filters, it had better return all the widgets.

These powers of the empty set mean that many operations have their natural meanings. For example, if you have a filter set and decide that you want to allow inactive widgets, you can remove Widget­Filter.Active from your filters. If Find­Widgets­With­Filter treated an empty filter list as meaning “Return no widgets at all”, then you’d need a special case for the possibility that the Active filter was the last filter.

Bonus chatter: Most programming languages understand the power of the empty set. For example, C++ std::all_of and JavaScript Array.prototype.every return true when given an empty collection, whereas C++ std::any_of and JavaScript Array.prototype.some return false when given an empty collection.

¹ This naming distinction between “selector” patterns (where each selector adds to the list of results) and “filter” patterns (where each filter shrinks the list of results) is my own and is not officially part of the Windows API design patterns.

My proposal that was accepted is that filters should be named after what they allow to pass through, not by what they remove. For example, passing the Widget­Filter.Active filter means that you want the active widgets. It doesn’t mean that you want to filter out the active widgets (and return only the inactive ones). If you want a filter to remove active widgets, then the filter should be named something like Widget­Filter.Inactive. For adjectives that don’t have an obvious antonym, you can use the prefix Not, as in Widget­Filter.Not­Blinking.

Bonus chatter: We saw another application of this principle some time ago when we looked at what a timeout of zero should mean.

Topics
Code

Author

Raymond has been involved in the evolution of Windows for more than 30 years. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie-jeebies. The Web site spawned a book, coincidentally also titled The Old New Thing (Addison Wesley 2007). He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.

14 comments

Discussion is closed. Login to edit/delete existing comments.

  • John Elliott

    I remember having this argument with a company that published a REST API, which would return a collection if there was a result, but a 404 error rather than an empty collection if there wasn’t.

  • Michael Dunn · Edited

    Ruby works the same way — `[].all?` returns true and `[].any?` returns false — but every time I need to know which function returns what, I have to run them both in the console. I guess I’m not good enough at set theory to remember which is which.

  • Ian Boyd

    We all know that languages should not have `null`. (and then Javascript goes ahead and has two types of nulls).

    But then you'll have people insist that you cannot program without `null`. Similar to how in the early 1990s you still had people arguing that they **need** `goto`.

    So it was amazing when C# 8 just let you say:

    > Nulls: off

    And that's that. No more nulls. And socity didn't collapse. And it turns out, like `goto`, you...

    Read more
  • Simon Geard

    It's stupid — if I search for customers with the name "Smith" and there aren't any, that's not a special case... it's a set of all customers named Smith, just as it would be if there were a thousand of them.

    Seriously, the number of times I've seen functions that do something like:

    <code>

    ...and then seen the caller do:

    <code>

    Why do people think they need to write unnecessary extra code which has no impact other than forcing other...

    Read more
  • Bastian Weßling · Edited

    Interesting post, but I am confused since I see no difference between:

    // No color passed => return empty set
    IVectorView FindWidgetsOfColors(IIterable colors);
    
    // No filter passed => return all widgets
    IVectorView FindWidgetsWithFilter(IIterable filters);

    To me, both of these are filter functions. A color is a filter that matches widgets with that color. But maybe that is more of a philosophical question.

    • Matthew Barnett

      I believe the point is that ‘FindWidgetsOfColors’ would be written to return _any_ that match and ‘FindWidgetsWithFilter’ would be written to return _all_ that match, although the names of the functions don’t make that explicit (it puzzled me too for a while!). Perhaps a better solution would be to write them to accept a predicate to be passed so that the user could choose how it should select the widgets.

      • Raymond ChenMicrosoft employee Author

        Yeah, I didn't name FindWidgetsOfColors well.

        The predicate is basically the same as "FindAllWidgets" and then postfiltering the list. The idea behind passing your criteria up front is that the system can optimize the search. E.g. "I already index the widgets by color, so if you ask for the red ones, I can give you those immediately without having to search through the boxes where I keep the blue and green ones, only for your predicate...

        Read more
    • Raymond ChenMicrosoft employee Author · Edited

      If FindWidgetsOfColors were a filter function, then FindWidgetsOfColors({ Red, Blue }) would mean “find widgets that are both red and blue” (because filters combine via intersection: you have to pass all the filters). If we assume that each widget is only one color, then there would be no point to passing more than one color to a color filter, since it would never return any results.

      • Bastian Weßling

        Okay, if we are talking about the zero element of or versus and, then we are on the same page. The difference between the semantics of both Find… functions didn’t register with me.

    • Alexander Buynyachenko · Edited

      I read it this way:

      FindWidgedWithColors

      always has explicit filter that is required to be passed in – it is the color filter.

      FindWidgetsWithFilter

      gives you an option of not passing filter at all.

  • Dan Bugglin · Edited

    .NET provides the APIs Array.Empty and Enumerable.Empty specifically for generating empty sets. Array.Empty even caches the array so you can reuse it everywhere you need that empty set of a specific type and aren't recreating it every time. I assume Enumerable.Empty does something similar.

    There's also string.Empty but I'm not sure if that counts. Regardless .NET will deduplicate constant strings anyway so string.Empty won't get you that extra benefit since you were already getting it. I...

    Read more
    • Michael Taylor · Edited

      `String.Empty` exists in .NET for one reason - not all languages support strings or even empty strings. This constant was defined for languages that don't support string literals. That was back when .NET was introduced as a new runtime for any language. Behind the scenes it is no different than using an empty string literal. Early on (.NET 2) I saw a lot of "recommendations" to use it over a string literal yet none of...

      Read more
    • Kevin Norris

      In Rust, an "array" has a known size at compile time, and an "empty array" is therefore a zero-sized type (ZST). The compiler knows that every instance of a given ZST is identical, so it automatically constant-folds all ZST instances out of existence as a guaranteed optimization. This also means that a pointer to a ZST does not (need to) point to a real allocation, it can just point to a made-up aligned and non-null...

      Read more
      • 紅樓鍮

        Note that Rust supports &[] (and &mut []) as well.