The first in a three-part series on the technical architecture of the iD

The launch of iD, the new web-based editor that we’re building for OpenStreetMap, generated interest from technical users interested in contributing to development or using parts of iD in other tools. If that describes you, or if you’re just curious about the technical details of building an editor, this series is for you.

Let’s start by looking at the code at the center of iD: the core and actions. While iD has an impressive display layer which we’ve improved and refined, the core is independent of map rendering or any UI.

This core implements the very basics of the OpenStreetMap data model and the datastructures needed to track changes. Actions build on this core, providing the “business logic” for making changes to the map data. We’ve aimed to make both highly reusable, hoping that they will prove useful in other OpenStreetMap-related tools.

iD is a relatively traditional editor built on this platform, but the possibilities are endless - purpose-specific editors, more advanced user interfaces, or even using iD’s core purely for querying and displaying OSM data.

Core

The iD core implements OSM data types, a graph of OSM objects’ relationships to one another, an undo/redo history for changes made during editing, and a couple of important auxiliary classes. It eventually aims to be a reusable, modular library to kickstart other JavaScript-based tools for OpenStreetMap.

The OSM data model includes three basic data types: nodes, ways, and relations.

  • A node is a point type, having a single geographic coordinate.
  • A way is an ordered list of nodes.
  • A relation groups together nodes, ways, and other relations to provide free-form higher-level structures.

Each of these three types has tags: an associative array of key-value pairs which describe the object.

In iD, these three types are implemented by iD.Node, iD.Way and iD.Relation. These three classes inherit from a common base, iD.Entity. This is the only use of classical inheritance in iD, but it’s justified by the common functionality of the types. Generically, we refer to a node, way or relation as an entity.

Every entity has an ID either assigned by the OSM database or a negative, local identifier assigned by iD for newly-created objects. IDs from the OSM database as treated as opaque strings; no assumptions are made of them other than that they can be compared for identity and do not begin with a minus sign (and thus will not conflict with proxy IDs). The three types of entities have separate ID spaces: a node can have the same numeric ID as a way or a relation. Instead of segregating ways, nodes, and other entities into different datastructures, iD internally uses fully-unique IDs generated by prefixing each OSM ID with the first letter of the entity type. For example, a way with OSM ID 123456 is represented as ‘w123456’ within iD.

iD entities are immutable: once constructed, an Entity object cannot change. Tags cannot be updated; nodes cannot be added or removed from ways, and so on. Immutability makes it easier to reason about the behavior of an entity: if your code has a reference to one, it is safe to store it and use it later, knowing that it cannot have been changed outside of your control. It also makes it possible to implement the entity graph (described below) as an efficient persistent data structure.

Since iD is an editor, it must allow for new versions of entities. The solution is that all edits produce new copies of anything that changes. At the entity level, this takes the form of methods such as iD.Node#move, which returns a new node object that has the same ID and tags as the original, but a different coordinate. More generically, iD.Entity#update returns a new entity of the same type and ID as the original but with specified properties such as nodes, tags, or members replaced.

Entities are related to one another: ways have many nodes and relations have many members. To render a map of a certain area, iD needs a datastructure to hold all the entities in that area and traverse these relationships. iD.Graph provides this functionality. The core of a graph is a map between IDs and the associated entities; given an ID, the graph can give you the entity. Like entities, a graph is immutable: adding, replacing, or removing an entity produces a new graph, and the original is unchanged. Because entities are immutable, the original and new graphs can minimize memory use by sharing references to entities that have not changed instead of copying the entire graph. This persistent data structure approach is similar to the internals of the git revision control system.

The final major component of the core is iD.History, which tracks the changes made in an editing session and provides undo/redo capabilities. Here, the immutable nature of the core types really pays off: the history is a simple stack of graphs, each representing the state of the data at a particular point in editing. The graph at the top of the stack is the current state, off which all rendering is based. To undo the last change, this graph is popped off the stack, and the map is re-rendered based on the new top of the stack.

This approach constitutes one of the main differences between iD’s approach to data and that of JOSM and Potlatch 2. Instead of changing a single copy of local data and having to implement an ‘undo’ for each specific action, actions in iD do not need to be aware of history and the undo system.

Finally, we have the auxiliary classes iD.Difference and iD.Tree.

iD.Difference encapsulates the difference between two graphs, and knows how to calculate the set of entities that were created, modified, or deleted, and need to be redrawn.

var a = iD.Graph(), b = iD.Graph();
// (fill a & b with data)
var difference = iD.Difference(a, b);

// returns entities created between and b
difference.created();

iD.Tree calculates the set of downloaded entities that are visible in the current map view. To calculate this quickly during map interaction, it uses an R-tree.

var graph = iD.Graph();
// (load OSM data into graph)

// this tree indexes the contents of the graph
var tree = iD.Tree(graph);

// quickly pull all features that intersect with an extent
var features = tree.intersects(
    iD.geo.Extent([0, 0], [2, 2]), tree.graph());

Actions

In iD, an action is a function that accepts a graph as input and returns a new, modified graph as output. Actions typically need other inputs as well; for example, iD.actions.DeleteNode also requires the ID of a node to delete. The additional input is passed to the action’s constructor:

// construct the action: this returns a function that remembers the
// value `n123456` in a closure so that when it's called, it runs
// the specified action on the graph
var action = iD.actions.DeleteNode('n123456');

// apply the action, yielding a new graph. oldGraph is untouched.
newGraph = action(oldGraph);

iD provides actions for all the typical things an editor needs to do: add a new entity, split a way in two, connect the vertices of two ways together, and so on. In addition to performing the basic work needed to accomplish these things, an action typically contains a significant amount of logic for keeping the relationships between entities logical and consistent. For example, an action as apparently simple as DeleteNode, in addition to removing the node from the graph, needs to do two other things: remove the node from any ways in which it is a member (which in turn requires deleting parent ways that are left with just a single node), and removing it from any relations of which it is a member.

As you can imagine, implementing all these details requires an expert knowledge of the OpenStreetMap data model. It is our hope that JavaScript based tools for OpenStreetMap can reuse the iD’s core implementation, significantly reducing the work necessary to create a robust tool.

Next time

Up next, we shift gears from abstract data types and algorithms to the parts of the architecture that implement the user interface core of iD: modes, behavior, and operations.



Devlogging work on the OpenStreetMap project by the MapBox team.

Much of this work is currently focused on improvements to OpenStreetMap funded by the Knight Foundation

Follow our work here on this blog or subscribe to our Twitter feed. You can subscribe to this blog’s feed or follow us at