Forem: Brian Schiller

Readable Bash Scripts

Brian Schiller — Fri, 08 Jan 2021 18:59:30 +0000

I really love the feeling of writing a bash pipeline. It's fun to string commands together, peek at the output, add another couple pipes to massage the data closer to my goal. I even gave a short class on them: bgschiller/shell-challenges.

But it's easy to find that a pipeline that was delightful to write is painful to maintain. Even if you're the one reading it a month later, it's difficult to remember what the purpose of each piece is. This is a trick I learned to break pipelines into intermediate files for more readable scripts.

The task

The product I'm working on has a list of "Alarms"—conditions that the end user needs to be alerted to. We also have a localization file for each supported language that maps Alarm names to human-readable names, descriptions, etc. There are a lot of alarms, enough to make it difficult to keep track of which ones are already translated. This calls for a script!

The Alarms file looks something like this:

<!-- Alarms.xml -->
<?xml version="1.0" encoding="utf-8"?>
<config name="AlarmConfig">
   <AlarmList name="IngredientAlarms" version="1.0">
      <Alarm name="MozzarellaTooWarm">
        <!-- some alarm-specific stuff here -->
      </Alarm>
      <Alarm name="PizzaTooCold">
      </Alarm>
      <!-- ... -->

And the localization something like this:

[{ stringId: "alarm_id_MozzarellaTooWarm",
   localString: "MozzarellaTooWarm" },
 { stringId: "alarm_title_MozzarellaTooWarm",
   localString: "Mozzarella Too Warm" },
 { stringId: "alarm_description_MozzarellaTooWarm",
   localString: "The mozzarella has become too warm and must be used within the next five minutes" },
  //...
]

Make a plan

Extract the alarms names from Alarms.xml using xpath.
Each alarm needs to be prefixed with alarm_id_, alarm_title_, alarm_description_, alarm_operator_actions_ in order to match the localization file. Figure out some way to do that.
Extract the "stringId" from each entry in the localization file. Oh, but there are other entries for things that need to be localized, and aren't alarms at all. Figure out a way to filter those out. Probably use jq for that.
Use diff to compare the expected keys with the actual keys.

This isn't a post on how to make bash pipelines, so I'll gloss over that piece. Here's what I came up with:

diff \
  <(join -j 99999 \
    <(echo 'alarm_id_
alarm_title_
alarm_description_
alarm_operator_actions_') \
    <(xpath -q -e config/AlarmList/Alarm/@name Alarms.xml |
      cut -d= -f2 | tr -d '"') \
    | tr -d ' ' | sort) \
  <(jq '.[] | select(.stringId | startswith("alarm_")) |
        .stringId ' i18n/en.json | sort)

It's convoluted and kinda impressive in that way. But not code you'd be happy to maintain.

One step at a time

The prior step accomplished what we needed, but it was pretty difficult to see what was going on. In my opinion, that's because

Nothing has a name. Because each process substitution is fed directly into a parent, nothing ever receives a name. We need to name our intermediates!
No comments. It's difficult to add comments because every line ends in a backslash, meaning "continue this line as if I hadn't pressed enter". Bash doesn't allow you to say "continue this line" and also add a comment.

Let's see if we can tease out each part using intermediate files.

cat > alarm_attrs << EOF
alarm_id_
alarm_title_
alarm_description_
alarm_operator_actions_
EOF

xpath -q -e config/AlarmList/Alarm/@name Alarms.xml |
  cut -d= -f2 | tr -d '"' > expected_alarm_names

join -j 999 alarm_attrs expected_alarm_names |
  tr -d ' ' | sort > expected_localization_keys

jq -r '.[] | select(.stringId | startswith("alarm_")) |
       .stringId' en.json | sort > actual_localization_keys

This is better! Each piece can be understood in isolation, and the dependencies between steps are explictly tracked with named files. All that's left is to add comments and some error checking, and clean up our intermediate files.

Cleaning up after ourselves is a little tricky. Ideally, we'd like to avoid leaving the intermediate results files laying around regardless of whether the script exits normally, crashes, or is cancelled with ctrl-c. We can use trap to handle this. trap sets up a command to run when a "signal" occurs. We'll put all our intermediate files into a directory and use trap to delete that directory when a signal that indicates our script is ending fires.

#!/bin/bash

set -ef -o pipefail

readonly script_name=`basename "$0"`
usage() {
  cat >&2 << EOF
Usage: $script_name <path-to-Alarms.xml> <path-to-en.json>

  Compare the alarms specified in Alarms.xml against the
  localizations keys provided in a [language-code].json file
  (eg, en.json). Warn if any keys are missing or unexpected.
EOF
  exit 2
}

if [[ $# != 2 ]]; then
   echo "error: expected 2 arguments, received $#" 1>&2
   usage
fi

readonly ALARM_CONFIG_XML=$1
if [[ ${ALARM_CONFIG_XML: -4} != ".xml" || ! -e $ALARM_CONFIG_XML ]]; then
   echo "error: unable to find XML file at $ALARM_CONFIG_XML" 1>&2
   usage
fi
readonly LOCALIZATION_JSON=$2
if [[ ${LOCALIZATION_JSON: -5} != ".json" || ! -e $LOCALIZATION_JSON ]]; then
   echo "error: unable to find JSON file at $LOCALIZATION_JSON" 1>&2
   usage
fi

# Make a directory for intermediate results
tmpdir=$(mktemp -d -p .)
# ensure it's removed when this script exits
trap "rm -rf $tmpdir" EXIT HUP INT TERM
# note: when debugging, turn off that `trap` line to keep
# intermediate results around

# The plan is ultimately to use diff to compare names between
# Alarms.xml and en.json. diff will tell us if any names
# appear in one file but are missing in the other (checks
# both directions for a mismatch).In pursuit of this, we need
# to create a couple of temporary files:
#  1) all the alarm names we expect to find (based on Alarms.xml)
#  2) all the names actually present in the localization file.
# A complication: the location file uses a flat format to
# store the id, title, description, and operator_actions:
#   { "stringId": "alarm_id_MozzarellaTooWarm", ... },
#   { "stringId": "alarm_title_MozzarellaTooWarm", ... },
#   { "stringId": "alarm_description_MozzarellaTooWarm", ... },
#   { "stringId": "alarm_operator_actions_MozzarellaTooWarm", ... },
# We want to check that *all* of these keys are present, so
# we use a cross product of (alarm names) X (those attributes)

cat > $tmpdir/alarm_attrs << EOF
alarm_id_
alarm_title_
alarm_description_
alarm_operator_actions_
EOF

xpath -q -e config/AlarmList/Alarm/@name $ALARM_CONFIG_XML |
 cut -d= -f2 | tr -d '"' > $tmpdir/expected_alarm_names

# trick to compute cross product: use `join` with a join
# field that doesn't exist (999). since both files lack a
# field at 999, they will compare equal for every key, and
# each line of the left file will be joined with each line
# of the right file--a cross product.
join -j 999 $tmpdir/alarm_attrs $tmpdir/expected_alarm_names |
tr -d ' ' | sort > $tmpdir/expected_localization_keys

jq -r '.[] | select(.stringId | startswith("alarm_")) |
       .stringId' $LOCALIZATION_JSON |
  sort > $tmpdir/actual_localization_keys

if diff $tmpdir/expected_localization_keys $tmpdir/actual_localization_keys; then
   echo "Success! Found all" $(wc -l $tmpdir/expected_localization_keys) "expected localization keys"  1>&2
else
   echo "Failure. Found discrepancies between expected alarm names and actual localization keys" 1>&2
   exit 1
fi

Vue Browser Extensions with Parcel

Brian Schiller — Wed, 18 Nov 2020 04:18:20 +0000

Vue CLI offers a great workflow for most web apps. Run a command, choose which plugins to enable, and you're off to the races. But if you want something off the beaten path it is a little more difficult. I've found that setting up webpack takes longer than I'm willing to spend for a quick project. Instead, I use Parcel, which requires (almost) zero config.

Today we'll walk through how to use Vue (or React, or Typescript, or anything else that needs a build step) in a Browser Extension. Our browser extension will work in both Chrome and Firefox (using the webextension-polyfill project).

The hard part, as it should be, is deciding what to build. We'll punt on that one, and just make a widget that shows a color depending on the date.

To get started, initialize your project and install a couple dependencies.

npm init -y # set up a package.json, accepting all default
# (drop the '-y' if you want to choose a name, license, etc, by hand)
npm install --save-dev parcel parcel-plugin-web-extension

Next, borrow a couple of scripts we'll need for building the release: scripts/remove-evals.js and scripts/build-zip.js. I originally got these from another boilerplate, but made some changes to remove dependencies. It looks like remove-evals.js is used because chrome extensions ship with a content-security-policy that disallows eval. build-zip.js is used to package up a production build of your extension.

Next, we'll make a manifest file, describing the extension's entry points. Our extension is fairly simple with only a popup, but yours might have content scripts, a background script, or an options page.

{
  // src/manifest.json
  "browser_action": {
    "default_popup": "./popup.html"
  },
  "description": "Color of the Day",
  "manifest_version": 2,
  "name": "color-of-the-day",
  "permissions": [],
  "version": "1.0.0",
  "content_security_policy": "script-src 'self' 'unsafe-eval'; object-src 'self'"
}

Next, make a small file matching your default_popup's name: popup.html. This will be used as a parcel entry point, so parcel will bundle any resources it finds in this file.

<!-- src/popup.html -->
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
  </head>

  <body>
    <div id="app"></div>
    <script src="./popup.js"></script>
  </body>
</html>

When parcel sees <script src="./popup.js"></script>, it will visit that file to see what other code needs to be bundled. That will be our Vue entry point.

// src/popup.js
import Vue from "vue";
import App from "./App.vue";

new Vue({
  el: "#app",
  render: (h) => h(App),
});

Similarly, parcel will now pull in both vue and App.vue.

<template>
  <div
    class="color-of-the-day"
    :style="{ 'background-color': backgroundColor }"
  ></div>
</template>
<script>
export default {
  computed: {
    hue() {
      return Math.floor(Math.random() * 360);
    },
    backgroundColor() {
      return `hsl(${this.hue}, 100%, 50%)`;
    },
  },
};
</script>
<style>
.color-of-the-day {
  width: 200px;
  height: 200px;
}
</style>

Finally, we'll need to add a few items to the scripts section of our package.json:

{ // package.json
  // ...
  "scripts": {
    "build": "npm run pack && npm run remove-evals && npm run zip",
    "dev": "parcel watch src/manifest.json --out-dir dist --no-hmr",
    "pack": "parcel build src/manifest.json --out-dir dist",
    "remove-evals": "node scripts/remove-evals.js",
    "zip": "node scripts/build-zip.js"
  }
  // ...
}

Now run npm run dev to build your extension. The first time you run this, parcel will notice you're working with Vue and download some packages you need (eg, vue, vue-template-compiler). Once it says "Built in 14.03s", or however long, you can load the extension in your browser.

Visit chrome://extensions or about:debugging#/runtime/this-firefox, depending on your browser. You may need to turn on developer mode if this is the first time you've loaded an extension from a file on this computer. Load the dist folder (chrome) or the manifest.json file (firefox), and your extension is ready!

All the code from this post is available at https://github.com/bgschiller/vue-parcel-web-extension

More goodies

Parcel is smart enough to handle almost any web technology. If you want to use Typescript, just change
popup.js to popup.ts and make a tsconfig.json file. Want to use scss? Add lang="scss" to the <style> tag in your Vue component. Reportedly, it can even handle Rust code, though I haven't tried it.

I was Promised Pizza

Brian Schiller — Thu, 02 Jan 2020 14:53:13 +0000

A while back, a coworker had a question about combining the values from multiple javascript Promises. I've tried to cull the interesting Promise construction out of the original problem, and came up with an example about pizza.

My goal here is to focus only on how the functions are combined, and how they work internally. To that end, I've defined just their signature (argument types and return types) without the body. Here are the TypeScript declarations, so we can check our code. If you're not familiar with TypeScript, don't worry! I've left comments explaining the first couple functions, so you can get used to the pattern.

// gatherIngredients is a function that takes no arguments
// and returns a Promise resolving to { tomatoes, basil, flour, ...}
declare var gatherIngredients: () => Promise<{
  tomatoes: 'tomatoes',
  basil: 'basil',
  flour: 'flour',
  yeast: 'yeast',
  mozzarella: 'mozzarella',
}>;
// makeSauce is a function that takes { tomatoes, basil } as
// its only argument and returns a Promise resolving to 'sauce'.
declare var makeSauce: (i: { tomatoes: 'tomatoes'; basil: 'basil'; }) => Promise<'sauce'>;
// makeDough is a function that takes { flour, yeast } as its
// only argument and returns a Promise resolving to 'dough'
declare var makeDough: (i: { flour: 'flour'; yeast: 'yeast'; }) => Promise<'dough'>;
declare var spreadDough: (d: 'dough') => Promise<'spread-dough'>;
declare var assemblePizza: (i: ['spread-dough', 'sauce', 'mozzarella']) => Promise<'raw-pizza'>
declare var bake: (p: 'raw-pizza') => Promise<'pizza'>;
declare var eat: (p: 'pizza') => Promise<void>;

Given these definitions, write a function to eat a pizza. If you'd like, use the TypeScript playground to check your work as you go.

(this space left intentionally blank)

(also blank, to hide the solution until you're ready)

Solutions

I posed the question to the #help-typescript channel on the Denver Devs slack group, and folks came up with a variety of solutions!

Here's a good first stab at the problem.

gatherIngredients().then(ingredients => {
  const { tomatoes, basil, flour, yeast, mozzarella } = ingredients;
  return makeSauce({ tomatoes, basil }).then(sauce => {
    return makeDough({ flour, yeast }).then(doughBall => {
      return spreadDough(doughBall).then(readyDough => {
        return assemblePizza([readyDough, sauce, mozzarella]).then(rawPizza => {
          return bake(rawPizza).then(pizza => {
            return eat(pizza).then(() => {
              console.log('yum!');
            })
          })
        })
      })
    })
  })
});

This solution is correct, and reasonably clear. It's not perfect, so it makes a good starting place. Let's start with what it gets right:

The steps are in the same order we will read them. Nice!
Values that are created early but used later (like mozzarella) are still available when they're needed. This happens because each nested function is a closure, holding references to the variables that were available at the time the function was defined.

Stylistically, I have a problem with the inexorable march to the right side of the screen. Weren't promises supposed to save us from that?? We also make a couple of functions that are identical to bake and eat (eg, rawPizza => { return bake(rawPizza); } is a wrapper function that does exactly the same job as bake). You could also quibble about arrow functions with implicit returns, but I kinda like the consistency ¯\_(ツ)_/¯. Performance-wise, there are some optimizations we could make. makeSauce and makeDough could be happening simultaneously, as they don't rely on one another's return values. Can we improve on these lines?

gatherIngredients()
  .then(({ tomatoes, basil, flour, yeast, mozzarella }) => {
    return Promise.all([
      makeDough({ flour, yeast }).then(spreadDough),
      makeSauce({ tomatoes, basil }),
      // not a promise, just needs to passed along for future work
      mozzarella,
    ] as const);
  })
  .then(assemblePizza)
  .then(bake)
  .then(eat);

This solution is also correct, and it's parallel whenever possible (we can be making and then spreading dough at the same time as the sauce is cooking). We've managed to avoid the copious indentation of the first solution, which is nice. However, the trick we've used to get there is confusing and requires a comment to explain what's going on.

To explain briefly, Promise.all will "upgrade" any value passed into it into a promise. So when I pass in mozzarella, Promise.all says, "That's not a promise, but I can treat it like a promise resolving to that value". This allows me to hand mozzarella along to the next function without using a closure.

There's also a weird bit with as const. TypeScript's best guess at the type of that array is Array<'spread-dough' | 'sauce' | 'mozzarella'>. That is, "An array where each of the values is one of these three things". But we want TypeScript to interpret it as having type "A 3-length array, with first 'spread-dough', then 'sauce', then 'mozzarella'". We can use the as const directive to tell TypeScript to assume the tightest possible type for that value.

This is about the best you can do using only Promise syntax. It avoids ever-deepening indentation of the closure-based solution. But we can avoid the confusing bit about passing mozzarella into Promise.all if we're allowed to use async/await syntax.

async function nom() {
  const { tomatoes, basil, flour, yeast, mozzarella } = await gatherIngredients();
  const sauce = await makeSauce({ tomatoes, basil });
  const doughBall = await makeDough({ flour, yeast });
  const flatDough = await spreadDough(doughBall);
  const unbakedPizza = await assemblePizza([flatDough, sauce, mozzarella]);
  const pizza = await bake(unbakedPizza);
  await eat(pizza);
}

Async/await makes some things clearer than promises, but other things have become more difficult or verbose. We've had to come up with variable names for doughBall, flatDough, etc. We've also lost a bit of concurrency: makeSauce and makeDough can no longer run at the same time. We can fix that last problem, but our code starts to look a bit funky...

async function nom() {
  const { tomatoes, basil, flour, yeast, mozzarella } = await gatherIngredients();
  const sauceP = makeSauce({ tomatoes, basil });
  const doughBallP = makeDough({ flour, yeast });
  const flatDough = await spreadDough(await doughBallP);
  const unbakedPizza = await assemblePizza([flatDough, await sauce, mozzarella]);
  const pizza = await bake(unbakedPizza);
  await eat(pizza);
}

In order to get makeSauce and makeDough running at the same time, we have to call the functions without awaiting the promise they return. To try and keep track of which things are promises and which are values, I've added a P suffix to the end of the variables that hold Promises. We need to remember to await these before trying to use the value (TypeScript will help us on this front). The Promise-only solution is starting to look pretty nice in comparison! Can we get the best of both worlds?

async function nom() {
  const { tomatoes, basil, flour, yeast, mozzarella } = await gatherIngredients();
  const [sauce, flatDough] = await Promise.all([
    makeSauce({ tomatoes, basil }),
    makeDough({ flour, yeast }).then(spreadDough),
  ] as const);
  return assemblePizza([flatDough, sauce, mozzarella])
    .then(bake)
    .then(eat);
}

In my opinion, this is the cleanest possible solution to this problem. We achieve it by taking advantage of both Promise syntax and await, each where appropriate:

We used .then for spreadDough, bake, and eat because the return of the prior function matches the arguments.
Promise.all is the clearest way to wait on two Promises that we kicked off at the same time.
await allows us to maintain access to the results of Promises without marching off to the right side of the screen.

How to use this in your own code

Keep the dual nature of Promises in mind. If you're just getting the hang of things, you may want to write two solutions: one each using Promises and async/await. Compare them and decide which one is clearer. As you get more practice, you'll develop instincts for when to use each technique.

Understanding TypeScript Generics

Brian Schiller — Mon, 19 Aug 2019 00:08:53 +0000

Let's think about a simple log function

function log(x) {
  console.log(x);
  return x;
}

I find it to be more useful than console.log on its own because I can use it in big chains to see what's going on.

const commandLineArgs = args
  .map(validate)
  .map(log) // logs values without modifying them
  .filter(differentThanDefault)
  .map(log)
  .reduce(collect, {});

But what's its type signature? As it stands, the function accepts an any argument and returns an any value. We do want it to work for any possible value, but by returning an any we are interfering with TypeScript's ability to track the types of values.

const nums: number[] = [5, 6, 7, 8];
const squares = nums.map(x => x * x); // inferred as number[]
const loggedSquares = log(squares); // inferred as any

This is a problem because if TypeScript thinks our value is of type any rather than number[], it won't catch when we make a mistake:

// Error: Operator '+' cannot be applied to types number[] and 5
const plusFive = squares + 5;

// no complaint from TS
const loggedPlusFive = loggedSquares + 5;

What we really want to say is not "log accepts an arg of any type and returns a value of any type" but rather "log accepts an arg of some type and returns a value of that same type". Generic Functions give us a way to do this. Let's rewrite our log function using generics.

function log<T>(x: T): T {
  console.log(x);
  return x;
}

The <T> syntax introduces what's called a "type variable" or "type parameter". Just how function parameters are stand-ins for a value that will be determined later, a type variable is a stand-in for a type that will be determined later. Giving a name to the type is how we're able to specify "log accepts a variable of some type T and returns a variable of that same type T".

Type Parameter Inference

In rare occasions, you may need to specify what concrete types you want in your type parameters. Most of the time, TypeScript will figure it out for you. Using our log function from before:

const x: number = 5;

log<number>(x); // you're allowed to specify what type you want
log(x); // TS knows x is a number, so it figures out that log<T> should be log<number>

Type parameters in other languages

Sometimes it's helpful to see how the same concept looks in other languages. Python is another language that recently had a type system bolted on top of it. In python, we need to declare a value as a type parameter before using it.

from typing import Sequence, TypeVar

T = TypeVar('T')  # Declare the type variable

def first(lst: Sequence[T]) -> T:
  return lst[0]

Without that T = TypeVar('T') declaration, python would go looking for a nearby or imported type called literally T. Probably, it would fail with a NameError when it didn't find a type of that name. Worse, maybe there is a type called T, and we've unwittingly written a function that only works on values of that type. By declaring it as a TypeVar, we're telling the typechecker: "There isn't really a type called T. Instead, T is a placeholder for a type to be decided later.

In my opinion, TypeScript's <T> is a nicer syntax, but it serves the same purpose.

Multiple Type Parameters

Some functions' type definitions have two or more type variables. map is a common example: It takes an array of some type (the first type parameter), a function from that first type to another type, and returns an array of that second type. It's even hard to write about without using names! Let's try again with names:

map accepts an array of some type T, a function from T to another type R, and produces an array of R.

With practice, the TypeScript syntax will become easier to read than the english. Here's what it looks like for map:

function map<T, R>(lst: T[], mapper: (t: T) => R): R[]

And once more, with descriptions alongside

function map
  <T, R>( // for some types T and R
    lst: T[], // lst is an array of T
    mapper: (t: T) => R // mapper is a function from T to R
  ): R[] // The return value is an array of R

References

the TypeScript docs on Generics

A Tale of Two Sorted Lists: Comparing Inheritance and Composition

Brian Schiller — Sat, 04 May 2019 03:01:22 +0000

As advice goes, "Favor Composition over Inheritance" is pithy and uncontroversial. Unfortunately, it also doesn't make much sense unless you already know what it means. We'll explore two different approaches to solving the same problem: Inheritance and Composition. At first glance, the Inheritance example looks more correct and is a bit shorter. I want to convince you that the Composition approach is more correct.

What's Composition? What's Inheritance?

It's easier to understand by looking at an example, but it is useful to have some idea of what you're watching for. Composition and Inheritance are both techniques to lean on existing code instead of duplicating logic. We'll see how this looks in code in a minute, but as a shorthand, you can say that

Inheritance is used to model an "Is-a" relationship, eg: "A PoissonRandomNumberGenerator is-a (specific case of) a RandomNumberGenerator"
Composition is used to model a "Has-a" relationship, eg: "A PoissonRandomNumberGenerator has-a (makes use of) a RandomNumberGenerator"

Either choice is defensible for the random number example. However, the adage guides us towards Composition. You may not yet have an intuition for why this is, but we'll get there :)

To build: a SortedList

We'd like to make a SortedList data structure. By keeping the elements in sorted order we can make the "does this list contain x?" operation really fast. Insert and delete operations will be a bit slower, but we are willing to pay that price for some use cases.

We'll use the Python standard library's bisect module to do most of the heavy lifting. The bisect function tells you what index to find an item, assuming the list is sorted. The insort function (a pun: "insert sorted") performs an insert to a sorted list in the right spot to keep it sorted. That's exactly what we need! This means we can focus almost entirely on the differences between our two approaches.

Here's how our sorted lists should behave:

sl = SortedList()
for elem in (12, 4, 15, 2):
    sl.insert(elem)
print(4 in sl) # True
print(18 in sl) # False
print(', '.join(elem for elem in sl)) # 2, 4, 12, 15

You might say: "Why bother writing a SortedList class at all? Don't the insort and bisect functions together do what we need? They do the right actions, but we're kinda coding without guard rails if we use them without a wrapper class. Remember: those functions assume the list is sorted to begin with—they don't check it! We would have to be diligent about never accidentally breaking the sorted order in any code using a list we want to use bisect and insort on, or we could introduce very difficult bugs into our code. An example of how this could bite us:

from bisect import bisect, insort
keep_me_sorted = []

insort(keep_me_sorted, 4)
insort(keep_me_sorted, 10)

# Danger! did the writers of include_fav_numbers know they have to
# keep the list in sorted order? Will they continue to remember in the future?
include_fav_numbers(keep_me_sorted)

# if they forgot, bisect and insort will no longer work properly on the list

Our fast search only works if the list is sorted, which is hard to guarantee with discipline alone. We could sort the list just before any time that we use bisect or insort. That would work, but it would erase all the performance benefits we're getting from using bisect in the first place! Instead, let's use encapsulation to protect the list from modifications that would break our sorted order.

Implementing the InheritanceSortedList

Using inheritance to make a SortedList seems like a natural choice. A SortedList is-a list! Done and done. Let's start there.

from bisect import insort, bisect

class InheritanceSortedList(list):
    def insert(self, elem):
        insort(self, elem)

    def __contains__(self, elem):
        """
        __contains__ is the method that is called when
        code like `x in collection` runs. This is where
        we get our performance boost over a regular list.
        """
        # Find the index where elem *might* be found
        ix = bisect(self, elem)
        return ix != len(self) and self[ix] == elem

So... are we done? This seems to do what we want. This list will work for simple examples, but we'll see later that it doesn't provide the encapsulation we're looking for. First, let's look at the Composition option.

Creating the CompositionSortedList

To use Composition, we'll make an object that includes a list as a hidden property.

from bisect import insort, bisect

class CompositionSortedList:
    def __init__(self):
        self._lst = []

    def insert(self, elem):
        insort(self._lst, elem)

    def __contains__(self, elem):
        ix = bisect(self._lst, elem)
        return ix != len(self._lst) and self._lst[ix] == elem

Okay, a bit longer than the Inheritance example, but not too bad. Unfortunately, this one doesn't quite pass our test. Specifically, (elem for elem in sl) will fail with an error:

TypeError: iteration over non-sequence

Similar to the __contains__ magic method, objects can define how to loop over them using the __iter__ method. When we made the InheritanceSortedList, we got a definition of __iter__ by way of inheriting from list. With Composition, we'll have to define one:

class CompositionSortedList:
    # ...
    def __iter__(self):
        return iter(self._lst)

Luckily, it's not too complicated. We basically say "To iterate over a CompositionSortedList, simply iterate over the hidden _lst bit". This is common enough that it has a special name. We can say that a CompositionSortedList delegates to its _lst property. We'll see later how to make this even nicer.

InheritanceSortedList breaks down

Whether we wanted to or not, InheritanceSortedList has inherited all of list's behavior—including things we don't want. For example, we have an append method:

lst = InheritanceSortedList()

lst.append(4)
lst.append(5)
print(5 in lst)  # prints 'False'

We also have an __init__ that we didn't bargain for:

lst = InheritanceSortedList([5, 3, 2])
print(2 in lst)  # prints 'False'

The __init__ and append methods came straight from the list parent class. They don't know that they're supposed to be maintaining sorted order! They're doing the right thing for intializing or appending to a regular list, regardless of the fact that it's the wrong thing a SortedList.

We can fix these up without too much work:

class InheritanceSortedList(list):
    def __init__(self, iterable=()):
        super().__init__(self)
        for elem in iterable:
            self.insert(elem)
    def append(self, elem):
        raise RuntimeError("Appending to a sorted list could break sorted-order. Use insert instead")
    def extend(self, iterable):
        raise RuntimeError("extending a sorted list could break sorted-order. Use insert instead")
    # ...are there others?

But this feels fragile to me. Have we caught and fixed all the methods that might break sorted order? Even if we have, could a future version of list add a new one? This is sometimes called the Fragile base class problem, where changes to the parent class (list) may unintentionally break a derived class (InheritedSortedList).

It also just feels messy to have a bunch of methods that do nothing but raise exceptions. I wish we could just skip defining those. Let's see how it might work with Composition.

CompositionSortedList builds up

In a way, CompositionSortedList has the opposite problem. There's a bunch of functionality on the list that we want to make available. Just like we did with __iter__, we can make methods that delegate to the private list property:

class CompositionSortedList:
    # ...
    def __iter__(self):
        return self._lst.__iter__()
    def __len__(self):
        return self._lst.__len__()
    def __getitem__(self, ix):
        return self._lst.__getitem__(ix)
    def __reversed__(self):
        return self._lst.__reversed__()

In comparison to the Inheritance implementation where we had to opt-out of methods that would break our sorted order, we're opting-in to behaviors that we want to make available. This protects us from the fragile base class problem!

It may be a personal preference of mine, but I feel that composition is also clearer. I don't have to dig through an inheritance hierarchy to figure out where a method was defined. Any functionality on a class using composition is right there on the class' definition.

Extra Credit: An even better delegate pattern

I started wondering if there was a more succinct way to write all those delegate methods. They're pretty repetitive, and it seemed like it should be possible to get rid of them. I wrote a library called superdelegate that makes it possible. Here's what it can look like with superdelegate

from superdelegate import SuperDelegate, delegate_to

class CompositionSortedList(SuperDelegate):
    # ...
    __iter__ = __len__ = __getitem__ = __reversed__ = delegate_to('_lst')

Pretty nice, I think!

When would you use inheritance?

Composition is safer, clearer, and (with some help from superdelegate) almost as terse. So when would you use inheritance at all? Inheritance is appropriate in a few cases I can think of (please email me if you have other recommendations).

When you really want to accept all behavior of parent class (even future changes we don't know about yet). I did this in bgschiller/citrus because I wanted the derived objects to be able to be treated as if they were the parent type in all situations.
When it's the way a framework wants you to customize behavior. Django's Class-based Views are a good example of this.
When there's some weird metaclass stuff going on. Think SqlAlchemy's DeclarativeBase models, or WTForms classes.

References

Mongo Schemas with Pokemon

Brian Schiller — Wed, 24 Apr 2019 13:16:30 +0000

Okay, so we're trying organize our pokemon. Build up our own little pokedex, if you will. And we're gonna use Mongodb because we gotta be web-scale; who knows how many pokemon there could be (I lost track after the first 151).

But we're not just gonna throw pokemon into mongo in a jumble! I said we were trying to organize the pokemon. We'll need a schema. Luckily, we're using MongoDB version 3.6, which supports JSON Schema.

The code at each step is available as the sequence of commits in bgschiller/pokemon-mongo-schemer. Check out the commit listing to jump around.

Let's get started. I'm looking at pokemon.json, which is based on ATL-WDI-Exercises/mongo-pokemon. I've added a few errors so that we can stress-test our schema. We don't want to let Gary pull a fast one on us by adding some pokemon that breaks the rules!

Here's our schema to begin with.

{
  type: "object",
  properties: {
    element: {
      type: "array",
      items: {
        type: "string",
        enum: [
          // probably there are more, but maybe we've only seen
          // the starters so far!
          "Grass",
          "Poison",
          "Fire",
          "Water",
        ],
      },
    },
    stats: {
      type: "object",
    },
    misc: {
      type: "object",
      properties: {
        sex_ratios: {
          type: "object",
        },
        classification: { type: "string" },
        // and some other properties...
      },
      additionalProperties: true,
    },
  },
  // we'll turn this off this later to make our schema more strict.
  // for now, it lets us get away with loading a partial schema.
  additionalProperties: true,
}

Let's try it out with just one pokemon to start with. We'll use the following node script.

const { MongoClient } = require('mongodb');
const pokes = require('./pokemon.json');
const schema = require('./schema.json');

(async function () {
  const client = await MongoClient.connect('mongodb://localhost:27017');
  const db = client.db('pokedex');
  db.createCollection(
    'pokemon',
    { validator: {
        $jsonSchema: schema,
      },
    });
  const pokemon = db.collection('pokemon');
  try {
    console.log('gonna insert the first pokemon');
    const response = await pokemon.insertOne(pokes[0]);
  } catch (e) {
    console.error(e);
  }
  client.close();
}());

Okay, so far so good. Now we have a bit of confidence that our schema at least didn't crash things. We can check that Bulbasaur was indeed added using the mongo shell.

Good documents succeed; bad docs are the true test

Is our schema even doing anything? Let's try adding something nonsense, to make sure.

// ...
 const response = await pokemon.insertOne({
   name: "Norberta",
   element: [
     "Flying",
     "Norwegian Ridge-back",
   ],
   stats: "no thanks",
 });
// ...

Okay, if your setup is working, that should give you an error message: "Document failed validation". Sooo, our schema is (maybe?) working. But Mongo is not exactly forthcoming about what the issue is.

Luckily, because JSON Schema is a standard, we can use another tool to tell us what's wrong. There's a great schema validator called ajv. Using the command line interface illustrates our problem:

$ ajv -s schema.json -d norberta.json --errors=text --all-errors
norberta.json invalid
data.element[0] should be equal to one of the allowed values
data.element[1] should be equal to one of the allowed values
data.stats should be object

Alright! That's a little more useful. It would be nice if we could get errors like that from mongo when validation fails. We would need to:

Catch errors occuring from insert, insertMany, update, and updateMany operations.
Pull the schema from the collection.
Convert some mongo-specific schema entries into things ajv will understand (eg, bsonType, ObjectID, date).
Figure out which document was failing validation (in the *Many cases).
For an update, synthesize the document that would have been created if the operation had succeeded.

mongo-schemer enters, stage right

Actually, all that hard work is already done! At devetry, we made and open-sourced a library to do just that: mongo-schemer. Let's add it to our script.

const MongoSchemer = require('mongo-schemer');
// ...
const db = MongoSchemer.explainSchemaErrors(
  client.db('pokedex'), {
    onError: (errors) => console.error(errors),
  });
// ...

Now let's run our Norberta script again. This time, it reports on the errors:

[ { keyword: 'enum',
    dataPath: '.element[0]',
    schemaPath: '#/properties/element/items/enum',
    params: { allowedValues: [Array] },
    message: 'should be equal to one of the allowed values' },
  { keyword: 'enum',
    dataPath: '.element[1]',
    schemaPath: '#/properties/element/items/enum',
    params: { allowedValues: [Array] },
    message: 'should be equal to one of the allowed values' },
  { keyword: 'type',
    dataPath: '.stats',
    schemaPath: '#/properties/stats/type',
    params: { type: 'object' },
    message: 'should be object' } ]

Stricter Schema: stats

We're now confident that the schema is truly guarding our collection. Let's make it a bit more strict. How about starting with that stats property. A stat is a number between 0 and 255. We can define a "Stat" in our schema to mean just that. Each pokemon should have one for hp, attack, defense, spattack, spdefense, and speed.

// ...
  definitions: {
    Stat: {
      type: "number",
      minimum: 0,
      maximum: 255,
    },
// ...
  stats: {
    type: "object",
    properties: {
      hp: { $ref: "#/definitions/Stat" },
      attack: { $ref: "#/definitions/Stat" },
      defense: { $ref: "#/definitions/Stat" },
      spattack: { $ref: "#/definitions/Stat" },
      spdefense: { $ref: "#/definitions/Stat" },
      speed: { $ref: "#/definitions/Stat" },
    },
    additionalProperties: false,
  },
// ...

And when we run this... it crashes! Maybe in the future it doesn't. Right now, with version 3.6, I get "MongoError: $jsonSchema keyword 'definitions' is not currently supported". Sooo, that's a bummer.

But all is not lost! A package called json-schema-ref-parser comes to our rescue this time. It does just what it says: takes any $references to definitions and *de*references them -- inlining the definition in each spot it's used.

const $RefParser = require('json-schema-ref-parser');
// ...
const inlinedSchema = await $RefParser.dereference(schema);
delete inlinedSchema.definitions;
db.createCollection(
  'pokemon',
  { validator: {
      $jsonSchema: inlinedSchema,
    },
  });
// ...

That's more like it! Now if we run our script, we should get some errors saying things like "stats.attack should be number". Sure enough, take a look at Bulbasaur in pokemon.json: some of his stats are strings pretending to be numbers. If we fix those up, the errors go away.

We could keep making our schema more descriptive. For example, there are more elements (pokemon types) than the four we have listed here, and we could document the structure of the moves object. I'll leave those as an exercise for the reader.

MongoDB support for JSON Schema is useful, but has two big holes: it doesn't support definitions in the schema, and when something goes wrong it doesn't tell you what. Hopefully those will be added in a future version, but mongo-schemer and json-schema-ref-parser fill those gaps in the meantime.