Productive Rage

Dan's techie ramblings

Why do you hate my (WCF) types, PHP??

Last November, I was helping someone consume a WCF Web Service with PHP (in the imaginatively named Consuming a WCF Web Service from PHP). After jumping through some hoops (and reading a lot of unhelpful and/or misleading information on the web) it was working; requests that relied on type names being specified were being accepted, gzip support was being enabled, even some useful debug information was being made available for when problems were encountered. All was well. But there was something that was bugging me for a long time that I only quite recently was able to address -

Why does the PHP SoapClient so belligerently throw away the type names of response objects?

It has knowledge of the type name since it must process the response data to populate the associative arrays that represent this data. But the names of the response types are apparently then cast forever into the ether, never to exposed to me. After all, I'm using PHP - I don't want no stinkin' types!

Is it just me?

I feel I should probably explain why I care so much. To be fair, I imagine that in a large number of cases the type name of the returned data really isn't important. If, for example, I'm querying the Twitter API for a set of Statuses then I know the form of the returned data (and since it returns JSON, there are no type names in the responses!). And for a lot of services, I imagine the form of the returned data will be identical from one result to another and, in many of the cases where the forms vary, a form of "property sniffing" will deal with it; does this result have this particular property along with all of the common ones? If so, save it or use it or do whatever with it.

But there are cases where this isn't enough. In that earlier post, the example was a web method "GetHotels" which returned hotel data for results that matched a particular set of filters (in that case, the type names were important for the request since an array of filters was specified, each filter was a particular WCF class - without the type names, the service couldn't deserialise the request).

Each of the returned hotels has data such as Categories, Awards, and Facilities but only the keys of these Categories, Awards and Facilities are returned. There is a separate web method "GetMetaData" that maps these keys onto names. A language can be specified as part of the meta data request so that the names are provided in the correct language.

Some of the meta data types may have additional data, such as an optional ImageUrl for Awards. Categories can be grouped together, so Categories such "Budget Hotel", "Boutique Hotel" and "Garden Hotel" are all considered to be part of the Category Group "Hotel" whilst "Guest House", "Farmhouse" and "Inn" are all considered part of the "Bed & Breakfast" Category Group.

The natural way to express this in a WCF Web Service (making use of wsdl-supported complex types) is something like the following -

[ServiceContract]
public class HotelService
{
  [OperationContract]
  public MetaDataEntry[] GetMetaData(MetaDataRequest request)
  {
    ..
  }
}

[DataContact]
public class MetaDataRequest
{
  [DataMember]
  public string APIKey { get; set; }

  [DataMember]
  public string LanguageCode { get; set; }

  [DataMember]
  public MetaDataType[] MetaDataTypes { get; set; }
}

public enum MetaDataType
{
  Award,
  Category,
  CategoryGroup,
  Facility
}

[KnownType(AwardMetaDataEntry)]
[KnownType(CategoryMetaDataEntry)]
[KnownType(CategoryGroupMetaDataEntry)]
[KnownType(FacilityMetaDataEntry)]
[DataContract]
public abstract class MetaDataEntry
{
  [DataMember(IsRequired = true)]
  public int Key { get; set; }

  [DataMember]
  public string Name { get; set; }
}

[DataContract]
public class AwardMetaDataEntry : MetaDataEntry
{
  [DataMember]
  public string ImageUrl { get; set; }
}

[DataContract]
public class CategoryMetaDataEntry : MetaDataEntry
{
  [DataMember(IsRequired = true)]
  public int CategoryGroup { get; set; }
}

[DataContract]
public class CategoryGroupMetaDataEntry : MetaDataEntry { }

[DataContract]
public class FacilityMetaDataEntry : MetaDataEntry { }

The MetaDataRequest allows me to specify which types of meta data that I'm interested in.

So, feasibly, if I wanted to build up a set of Categories to map the keys from the Hotels onto, I could make a request for just the meta data for the Categories. If I then want to map those Categories onto Category Groups, I could make a request for the Category Group meta data.

But why shouldn't I be able to request all of the meta data types, loop through them and stash them all away for future reference all in one go? I could do this easily enough with a .net client. Or a Java client. But, by default, PHP refuses to allow a distinction to be made between a CategoryGroupMetaDataEntry and a FacilityMetaDataEntry since they have the same structure and PHP won't tell me type names.

Well.. that's not strictly true. PHP does have some means to interrogate type names; the methods "gettype" and "get_class". If you define a class in your PHP code and pass an instance of it to the "get_class" method, you will indeed get back the name of that class. "get_class" may only be given an argument that is an object, as reported by the "gettype" method (see the get_class and gettype PHP documentation).

But if we try this with the web service call -

$client = new SoapClient(
  "http://webservice.example.com/hotelservice.svc?wsdl",
  array(
    "compression" => SOAP_COMPRESSION_ACCEPT | SOAP_COMPRESSION_GZIP,
    "trace" => 1
  )
);
$metaDataTypes = $client->GetMetaData(
  array(
    "request" => array(
      "ApiKey" => "TestKey",
      "Language" => 1,
      "MetaDataTypes" => array(
        "MetaDataTypeOptions" => array(
          "Award",
          "Category",
          "CategoryGroup",
          "Facility"
        )
      )
    )
  )
);

we can loop through the returned data and use get_class to find out that.. they are all apparently "StdObject".

This is what I meant by the type names being "thrown away".

Duck-typing (doesn't work if everything quacks and waddles)

In some cases we can work around this.

For example, to guess that a result is an AwardMetaDataEntry we could try

if (property_exists($metaDataValue, "ImageUrl")) {

and work on the basis that if it exposes an "ImageUrl" property that it is AwardMetaDataEntry.

But this won't work for differentiating between a CategoryGroupMetaDataEntry and a FacilityGroupMetaDataEntry since those response types have no structural differences.

Class Mappings

It turns out that the SoapClient does offer a way to get what we want, so long as we don't mind declaring PHP classes for every response type that we're interested in.

class MetaDataEntry
{
  public $Key;
  public $Name;
}

class AwardMetaDataEntry extends MetaDataEntry
{
  public $ImageUrl;
}

class CategoryMetaDataEntry extends MetaDataEntry
{
  public $CategoryGroup;
}

class CategoryGroupMetaDataEntry extends MetaDataEntry { }

class FacilityMetaDataEntry extends MetaDataEntry { }

As we can see in the PHP SoapClient documentation, one of the options that can be specified is a "classmap" -

This option must be an array with WSDL types as keys and names of PHP classes as values

It's a way to say that particular response types should be mapped to particular PHP classes - eg.

$client = new SoapClient(
  "http://webservice.example.com/hotelservice.svc?wsdl",
  array(
    "compression" => SOAP_COMPRESSION_ACCEPT | SOAP_COMPRESSION_GZIP,
    "trace" => 1,
    "classmap" => array(
      "AwardMetaDataEntry" => "AwardMetaDataEntry",
      "CategoryMetaDataEntry" => "CategoryMetaDataEntry",
      "CategoryGroupMetaDataEntry" => "CategoryGroupMetaDataEntry",
      "FacilityMetaDataEntry" => "FacilityMetaDataEntry"
    )
  )
);

Now when we loop through the response values and call get_class we get the correct names. Success!

(In the above code I've named the PHP classes the same as the WSDL types but, since the mappings all have to be individually specified, the class names don't have to be the same. The properties, on the other hand, do have to match since there is no facility for custom-mapping them. Any classes that don't have a mapping will continue to be translated into objects of type StdObject).

It may well be that this is far from news for many seasoned PHP Developers but when I described the situation (before finding out about the "classmap" option) to someone I was told was experienced and competent they had no suggestion in this direction.

To be honest, I'm not sure how I came across this in the end. If you know that there exists an option to map classes with the SoapClient then it's easy to find; but with only a vague idea that I wanted it to stop throwing away type names, it took me lots of reading and clutching at straws with search terms. Interestingly, even with this knowledge, I'm still unable to find an article that describes the specific problem I've talked about here.. so maybe it really is just me that has encountered it or cares about it!

Posted at 00:03

Comments

TypeScript State Machines

Last time, in C# State Machines, I used the example of traffic lights at a crossroads to illustrate how complexity could be handled easily with the state machine pattern. This was a follow-on to my Parsing CSS post and inspired by the excellent article Game Programming Patterns: State.

Well this little excursion offered me the perfect opportunity to dive into something else I've been looking at: TypeScript. I've long been a fan of JavaScript. It's got a lot of quirks and it's easy to write absolute rubbish with it. In fairness, it's possible to write crap with any language, it just feels like sometimes JavaScript makes it very easy. But if you embrace the patterns that work well with it and apply a little discipline, you can come up with elegant, maintainable solutions.

But I've often found it difficult to leave behind entirely the concept of static typing and that warm cozy feeling of knowing that the argument that you want is going to be an int and, as an int, you can apply any range checks you might need to and be content that everything has met your expectations (or demands, perhaps :) But if you don't even know what type it is, you can't as easily apply these sorts of restrictions. You can try to check the type of the argument and then apply range checking (or whatever) but that can start to get very messy, very quickly. I used to work with someone who claimed that static checking was unnecessary with sufficient unit testing. Meanwhile, I still think that there's a lot of potential for Code Contracts which is tending towards the polar opposite, so we basically had to agree to disagree on that one. In fact I may choose to take his argument to mean that with static types that a whole category of unit tests become unnecessary, handled instead by compiler checks!

So it's probably fairly easy to see, if I like JavaScript and I like static typing, why TypeScript could seem appear attractive prospect. And here was a nice little project that was non-trivial but still pretty compact that I could try it out with.

The type annotations in TypeScript are optional, but since I'm writing the code from scratch it makes sense to use them throughout. Interfaces are defined but do not need to referenced by types that implement the interface - so long as they have all of the required properties and methods then they will implicitly be considered to implement the interface. This is like Google's Go language and not like C#.

One thing that I don't like too much is that it isn't currently possible to specify an interface with readonly properties. It must be a property with a getter and setter or nothing. So I've resorted to specific Get methods on the interfaces instead, such as GetColour() and GetState().

(I'm going for a fairly direct port from the C# code. If you haven't read the last post then it might be worth a quick look - there's nothing too complicated going on here, it's just that I'm going to be skimming over the general program structure and concentrating mostly on how it works with TypeScript).

interface IAmATrafficLightState {
  GetColour(): ColourOptions;
  GetStatus(): StatusOptions;
  RegisterCarQueueing(): IAmAStateTransition;
  RegisterPassageOfTime(): IAmAStateTransition;
}

interface IAmAStateTransition {
  GetTransitionType(): TransitionTypeOptions;
  GetNewState(): IAmATrafficLightState;
}

enum ColourOptions {
  GreenOnly,
  RedAndYellow,
  RedOnly,
  YellowOnly
}

enum StatusOptions {
  HandlingTraffic,
  NotHandlingTraffic
}

enum TransitionTypeOptions {
  NoChange,
  Pop,
  Push,
  Replace
}

In the C# code, I actually had a StateTransition class rather than an IAmAStateTransition. The class had a private constructor and multiple static public methods for constructing instances: NoChange, Pop, Push and Replace. This isn't a structure that TypeScript supports, so instead I've got an interface and separate implementations. Each of the below classes implicitly IAmAStateTransition as they have the methods GetTransitionType() and GetNewState().

The PushTransition and ReplaceTransition classes take a single constructor argument of type IAmATrafficLightState (as the transitions work against a "state stack", only the Push and Replace actions require a state to change to, Pop and NoChange don't). Since the constructor argument's type is specified, the only validation I have to perform to remain consistent with the C# code is to ensure that it has a non-null value. TypeScript would indicate a compile-time error if I tried to pass a string for this argument, as that clearly isn't an IAmATrafficLightState implementation. But it won't complain about either a null value or an undefined value. So the easiest thing to do seems to be just use the JavaScript pattern of testing for anything that evaluates to false - ie. "if (!state) { /* Error */ }"

class NoChangeTransition {
  GetTransitionType(): TransitionTypeOptions {
    return TransitionTypeOptions.NoChange;
  }
  GetNewState(): IAmATrafficLightState {
    return null;
  }
}

class PopTransition {
  GetTransitionType(): TransitionTypeOptions {
    return TransitionTypeOptions.Pop;
  }
  GetNewState(): IAmATrafficLightState {
    return null;
  }
}

class PushTransition {
  constructor(private state: IAmATrafficLightState) {
    if (!state) {
      throw new Error("state may not be null for a Push Transition");
    }
  }
  GetTransitionType(): TransitionTypeOptions {
    return TransitionTypeOptions.Push;
  }
  GetNewState(): IAmATrafficLightState {
    return this.state;
  }
}

class ReplaceTransition {
  constructor(private state: IAmATrafficLightState) {
    if (!state) {
      throw new Error("state may not be null for a Replace Transition");
    }
  }
  GetTransitionType(): TransitionTypeOptions {
    return TransitionTypeOptions.Replace;
  }
  GetNewState(): IAmATrafficLightState {
    return this.state;
  }
}

I like the syntax here where constructor arguments can be marked as private, resulting in a private backing field being implicitly specified (see Steve Fenton's Stop Manually Assigning TypeScript Constructor Parameters). What I don't like is that in the resulting JavaScript, these fields are not private. If you look at the JavaScript below, which is generated from the TypeScript PushTransition class..

// This is the generated JavaScript for the TypeScript "PushTransition" class above
var PushTransition = (function () {
  function PushTransition(state) {
    this.state = state;
    if (!state) {
      throw new Error("state may not be null for a Push Transition");
    }
  }
  PushTransition.prototype.GetTransitionType = function () {
    return TransitionTypeOptions.Push;
  };
  PushTransition.prototype.GetNewState = function () {
    return this.state;
  };
  return PushTransition;
})();

.. you'll see that the state value is stored in "this.state". That's a public reference that JavaScript can manipulate. If all of the code that uses this class is TypeScript, then it won't be a problem as the compiler will enforce its private status. But if this is code to be called by non-TypeScript JavaScript then it's not ideal.

Although Douglas Crockford showed us years ago that genuinely private members were possible (see Private Members in JavaScript), the sacrifice is that methods for an object instance with private members must be declared for each instance. The class structure used by TypeScript, on the other hand, uses the prototype approach to declare functions for each class. This means that each method is defined only once per class, rather than once per instance. So it's a conscious decision to gain a performance improvement in terms of the memory required. (Anders Hejlsberg - the daddy of both C# and TypeScript - addresses exactly this point in this forum post Private Variables).

Time-Transitioning States

Some states in this model will transition based upon time alone. The initial state of RedLightWaitingForTraffic will only transition when cars arrive at the lights whereas states such as GreenLight transition based solely on time - it will stay green for a set period of time before cycling back round.

In the C# code last time, I had an abstract TimeBasedTransitiveState class with a nested class that would represent the states during which time was being counted down before the next transition. This nested class would have a "Source" property that pointed back to the traffic light state that started the countdown (eg. a GreenLight instance). TypeScript doesn't support abstract classes or nested classes so this structure wasn't going to work.

Instead I wrote it in a much more straight forward manner and then replaced the classes that have no internal state other than Colour, Status, Next Transition and Time-To-Next-Transition with what amount to static references. I liked this approach so much that I went back and changed the C# code such that TimeBasedTransitiveState class was written in pretty much the same way. (I've put the code up on Bitbucket for reference - see the TrafficLightStateMachine). I haven't changed the C# code to use static references yet, but it's something I'm considering.

class TimeBasedTransitiveState {
  constructor(
    private colour: ColourOptions,
    private status: StatusOptions,
    private timeSlicesToWaitFor: number,
    private nextTransition: IAmAStateTransition) {
    if (!nextTransition) {
      throw new Error("nextTransition may not be null for a Push Transition");
    }
    if (timeSlicesToWaitFor <= 0) {
      throw new Error("timeSlicesToWaitFor must be a positive value");
    }
  }
  GetColour(): ColourOptions {
    return this.colour;
  }
  GetStatus(): StatusOptions {
    return this.status;
  }
  RegisterCarQueueing(): IAmAStateTransition {
    return new NoChangeTransition();
  }
  RegisterPassageOfTime(): IAmAStateTransition {
    if (this.timeSlicesToWaitFor === 1) {
      return this.nextTransition;
    }
    return new ReplaceTransition(
      new TimeBasedTransitiveState(
        this.colour,
        this.status,
        this.timeSlicesToWaitFor - 1,
        this.nextTransition
      )
    );
  }
}

var RedLightPausedBeforeWaitingForTraffic = (function () {
  var TIME_AFTER_RESETTING_TO_RED_BEFORE_CONSIDERING_TRAFFIC = 5;
  return new TimeBasedTransitiveState(
    ColourOptions.RedOnly,
    StatusOptions.HandlingTraffic,
    TIME_AFTER_RESETTING_TO_RED_BEFORE_CONSIDERING_TRAFFIC,
    new PopTransition()
  );
})();

var YellowLight = (function () {
  var TIME_TO_WAIT_ON_YELLOW = 5;
  return new TimeBasedTransitiveState(
    ColourOptions.YellowOnly,
    StatusOptions.HandlingTraffic,
    TIME_TO_WAIT_ON_YELLOW,
    new ReplaceTransition(RedLightPausedBeforeWaitingForTraffic)
  );
})();

var GreenLight = (function () {
  var TIME_TO_STAY_ON_GREEN = 100;
  return new TimeBasedTransitiveState(
    ColourOptions.GreenOnly,
    StatusOptions.HandlingTraffic,
    TIME_TO_STAY_ON_GREEN,
    new ReplaceTransition(YellowLight)
  );
})();

var RedAndYellowLight = (function () {
  var TIME_TO_WAIT_ON_RED_AND_YELLOW = 5;
  return new TimeBasedTransitiveState(
    ColourOptions.RedAndYellow,
    StatusOptions.HandlingTraffic,
    TIME_TO_WAIT_ON_RED_AND_YELLOW,
    new ReplaceTransition(GreenLight)
  );
})();

var RedLightAboutToChange = (function () {
  // We're committed to letting traffic pass at this point so declare HandlingTraffic
  var TIME_TO_STAY_RED_AFTER_CAR_ARRIVES = 10;
  return new TimeBasedTransitiveState(
    ColourOptions.RedOnly,
    StatusOptions.HandlingTraffic,
    TIME_TO_STAY_RED_AFTER_CAR_ARRIVES,
    new ReplaceTransition(RedAndYellowLight)
  );
})();

Note that the state objects have to follow the TimeBasedTransitiveState definition, in terms of the order in which they appear in the code. These objects are created by calling the constructor of the TimeBasedTransitiveState class. If these calls are made before the class is defined then an error such as "undefined is not a function" or "PushTransition is not a constructor" will be raised (depending upon browser or other runtime environment).

This has been observed by many people, sometimes resulting in bug reports such as Inheritance only works if parent class is declared before child class. These have so far been rejected. In that report, Jon Turner writes

Unless we reorder the code for you, I think you still can come up with situations where a value hasn't been fully initialized. [..] At this time, we're explicitly not reordering code (or even adding code except in a couple of exceptions) that you've written.

So I guess that we have to get used to the current situation.

For working with multiple files, there is support for CommonJs and AMD modules as talked about at Organizing your code with AMD modules and require.js. Note that I think the mention of comments "reference path" is out of date now, as Steve Fenton points out in Say Goodbye To TypeScript Reference Comments!

One last point relating to this. I had a niggling thought that "isn't hoisting in JavaScript a way around this?" But hoisting is just about variable declarations, not their definitions. If you need a refresher on this (like I did) then this article is excellent: JavaScript Hoisting Explained (it has a video at the top which I skipped, all of the information is written below it).

Traffic-Transitioning States

So back to the TypeScript state machine code..

The traffic-transitioning states are the ones that are a bit more interesting! Traffic lights start off as a RedLightWaitingForTraffic. Once traffic is registered as having arrived at the light, it will transition to either the RedLightAboutToChange state or the RedLightWaitingForAccess. The first option is only possible if the traffic lights on the intersecting road at the crossroads are not letting traffic through - it would be no good for traffic on both roads to be moving simultaneously! The RedLightAboutToChange is one of the time-transitioning states above, all that will happen is that the full state cycle (RedAndYellow to Green to Yellow and back to Red) will take place.

However, if the other road is letting through traffic then the RedLightWaitingForAccess state is used. This state will check whether it is free to pass traffic every time that its RegisterPassageOfTime method is called. If so (meaning that the other road is no longer letting traffic flow), then it can transition straight to the RedAndYellowLight state. Otherwise it has to stick to being a RedLightWaitingForAccess.

Something I particularly liked when writing the TypeScript version was how easy it was to specify a constructor argument that was a function. I shouldn't be surprised, really, since not only does JavaScript support first class functions but also C# has had lambdas all over the place (and the Func class) since .net 3.5. But it was just gratifying that it was so easy to declare! I want a single argument that is a parameter-less function that returns a bool. As such, I need only write -

constructor(private isAllowedToLetTrafficThrough: () => boolean) {

Lovely! Succinct but easy to follow. So for the full implementations of the two traffic-based states we have -

class RedLightWaitingForAccess {
  constructor(private isAllowedToLetTrafficThrough: () => boolean) {
    if (!isAllowedToLetTrafficThrough) {
      throw new Error("isAllowedToLetTrafficThrough must be specified");
    }
  }
  GetColour(): ColourOptions {
    return ColourOptions.RedOnly;
  }
  GetStatus(): StatusOptions {
    return StatusOptions.NotHandlingTraffic;
  }
  RegisterCarQueueing(): IAmAStateTransition {
    // We can't do anything here, we're already waiting
    return new NoChangeTransition();
  }
  RegisterPassageOfTime(): IAmAStateTransition {
    if (this.isAllowedToLetTrafficThrough()) {
      return new ReplaceTransition(RedAndYellowLight);
    }
    return new NoChangeTransition();
  }
}

class RedLightWaitingForTraffic {
  constructor(private isAllowedToLetTrafficThrough: () => boolean) {
    if (!isAllowedToLetTrafficThrough) {
      throw new Error("isAllowedToLetTrafficThrough must be specified");
    }
  }
  GetColour(): ColourOptions {
    return ColourOptions.RedOnly;
  }
  GetStatus(): StatusOptions {
    return StatusOptions.NotHandlingTraffic;
  }
  RegisterCarQueueing(): IAmAStateTransition {
    if (this.isAllowedToLetTrafficThrough()) {
      return new PushTransition(RedLightAboutToChange);
    }
    return new PushTransition(new RedLightWaitingForAccess(this.isAllowedToLetTrafficThrough));
  }
  RegisterPassageOfTime(): IAmAStateTransition {
    return new NoChangeTransition();
  }
}

Representing the state transitions as a stack and having each IAmATrafficLightState implementation return an IAmAStateTransition for the calls to RegisterCarQueueing and RegisterPassageOfTime makes following the changes in state very easy. The RedLightWaitingForTraffic is always at the bottom of the stack. When it changes state (to either a RedLightAboutToChange or a RedLightWaitingForAccess) that new state is pushed onto the stack. All of the following states replace that top entry until the final RedLightPausedBeforeWaitingForTraffic which will pop off, leaving the original RedLightWaitingForTraffic.

Tying it all together

Having recreated the states and the transitions, we need the TrafficLight class that keeps track of the state queue. The TypeScript version is reassuringly close to the C# code. There's no Stack class so I've used an array instead (which in JavaScript has "push" and "pop" methods and so isn't far removed from the .net Stack class). TypeScript's enums are implemented in such a way that if you want to display their name (rather than their numeric value) then you need to treat the enum as a hashtable which maps the value back onto the name. This varies from C#, where the ToString method of an enum value will return the name rather than the value. Also note that I'm using a method "Log" to write out messages. This will be defined below.

class TrafficLight {
  private states: IAmATrafficLightState[];
  constructor(private trafficLightId: string, initialState: IAmATrafficLightState) {
    if (!trafficLightId) {
      throw new Error("A trafficLightId must be specified");
    }
    if (!initialState) {
      throw new Error("An initialstate must be specified");
    }
    this.states = [ initialState ];
  }

  GetTrafficLightId(): string {
    return this.trafficLightId;
  }

  GetColour(): ColourOptions {
    return this.GetCurrentState().GetColour();
  }

  GetStatus(): StatusOptions {
    return this.GetCurrentState().GetStatus();
  }

  RegisterPassageOfTime(): void {
    this.ApplyTransition(this.GetCurrentState().RegisterPassageOfTime());
  }

  RegisterCarQueueing(): void {
    this.ApplyTransition(this.GetCurrentState().RegisterCarQueueing());
  }

  private ApplyTransition(transition: IAmAStateTransition): void {
    var previousColour = this.GetCurrentState().GetColour();
    if (transition.GetTransitionType() === TransitionTypeOptions.NoChange) {
      // Do nothing
    }
    else if (transition.GetTransitionType() === TransitionTypeOptions.Pop) {
      if (this.states.length === 1) {
        throw new Error("Invalid transition - may not remove last state in the stack");
      }
      this.states.pop();
    }
    else if (transition.GetTransitionType() === TransitionTypeOptions.Push) {
      this.states.push(transition.GetNewState());
    }
    else if (transition.GetTransitionType() === TransitionTypeOptions.Replace) {
      this.states[this.states.length - 1] = transition.GetNewState();
    }
    else {
      throw new Error("Unsupported transition type: " + transition.GetTransitionType());
    }
    var newColour = this.GetCurrentState().GetColour();
    if (newColour !== previousColour) {
      Log(
        "* " + this.trafficLightId + " changed " + ColourOptions[previousColour] +
        " to " + ColourOptions[newColour]
      );
    }
  }

  private GetCurrentState() {
    return this.states[this.states.length - 1];
  }
}

The final piece of the puzzle is the equivalent of the Program class that drives the simulation in the C# code. This will create an object "tester" that wraps up references to both the North-South and East-West traffic lights in a closure, exposing a method "Advance" which will call "RegisterPassageOfTime" on the lights and, from time-to-time, based on the probabilityOfCarArrivingEachTimeSlice value, call "RegisterCarQueueing" too.

I originally intended to run the code from the command line (using CScript) but thought afterward that it might be worth doing in the browser as well, maybe using that to bolt on some sort of graphical representation of what's happening. Doing it in the browser allows it to be slowed down, too, since tester.Advance may be called through the setInterval method rather than firing full speed as it does at the command line (JavaScript has no Thread.Sleep method!). Note that any sort of "graphical representation" is yet to be implemented, it's text-only for now.

Whether or not it's being hosted in the browser also affects how it logs out its messages - with "console.log" or "WScript.Echo". I've gone for a simple approach in guessing how it's being hosted by presuming that if there is a "window" reference that it's in the browser and at the command line otherwise.

var tester = (function () {
  var probabilityOfCarArrivingEachTimeSlice = 0.1;

  var eastWestTrafficLight: TrafficLight = null;
  var northSouthTrafficLight = new TrafficLight(
    "N-S",
    new RedLightWaitingForTraffic(
      function() {
        return eastWestTrafficLight.GetStatus() === StatusOptions.NotHandlingTraffic;
      }
    )
  );
  eastWestTrafficLight = new TrafficLight(
    "E-W",
    new RedLightWaitingForTraffic(
      function() {
        return northSouthTrafficLight.GetStatus() === StatusOptions.NotHandlingTraffic;
      }
    )
  );

  var allTrafficLights = [ northSouthTrafficLight, eastWestTrafficLight ];
  return {
    Advance: function () {
      for (var i = 0; i < allTrafficLights.length; i++) {
        var trafficLight = allTrafficLights[i];
        if (Math.random() < probabilityOfCarArrivingEachTimeSlice) {
          if (trafficLight.GetColour() === ColourOptions.GreenOnly) {
            Log(
              "Car didn't have to queue " + trafficLight.GetTrafficLightId() +
              ", went straight through"
            );
          }
          else if (trafficLight.GetColour() === ColourOptions.YellowOnly) {
            Log(
              "Car didn't have to queue " + trafficLight.GetTrafficLightId() +
              ", went straight through (naughty!)"
            );
          }
          else {
            Log("Register car queueing " + trafficLight.GetTrafficLightId() + "..");
          }
          trafficLight.RegisterCarQueueing();
        }
      }
      for (var i = 0; i < allTrafficLights.length; i++) {
        allTrafficLights[i].RegisterPassageOfTime();
      }
    }
  };
})();

function IsBrowser(): boolean {
  return (typeof(window) !== "undefined");
}

function Log(message): void {
  if (IsBrowser()) {
    console.log(message);
  }
  else {
    WScript.Echo(message);
  }
}

if (IsBrowser()) {
  setInterval(tester.Advance, 100);
}
else {
  while (true) {
    tester.Advance();
  }
}

So how did TypeScript treat me?

All in all, I've enjoyed this. There were some potential gotchas like the ordering of classes. There's the concern over the public privates. There's no abstract classes or a "protected" keyword, nor are there nested classes, nor can you declare consts. But none of these are the end of the world.

When I first tried it out, for some reason I thought that the default behaviour of "==" and "!=" were going to be changed to act as "===" and "!==". This is not the case and I don't think it's the case for Dart or CoffeeScript either. It is the case for GorillaScript, which I read about last month. This also has support for optional typing (like TypeScript) but also throws in a lot of other features such as the equality changes I just mentioned (if you really want the JavaScript "==" and "!=" behaviour then you can use "~=" and "!~=" which I'm choosing to read as "wobbly equals" - which seems appropriate!), immutable-by-default (which I love the sound of), constants, generics, promises, all sorts! It even - hold onto your hats for controversy time - uses indentation-based code blocks, rather than curlies (now you know it's crazy! :) I don't know what uptake for this has been like or what sort of support is available but I may well be having a bit of a poke into this at some point.

Back to TypeScript.. I'm fairly sure that this is going to be just an early foray into its abilities for me. I've really liked what I've seen so far and hope to make time to try to use it in more scenarios. Something I really liked, that I found myself doing almost unconsciously to begin with, was not using hungarian notation in the code. Now I know that the idea that I used it at all will make some people a little sick in their mouth but I did feel that it acted as a crutch to document some of my intent when writing in a language without type annotations. I don't do it in C#. And I don't do it in TypeScript!

Posted at 21:03

Comments

C# State Machines

Not too long ago, I published Parsing CSS which talked about how I'd used a form of state machine to traverse the content and how doing so made changing the logic for "changing requirements" much easier -

When I started writing it, I somehow forgot all about attribute selectors [..] If this had been processed in some contorted single loop full of complicated interacting conditions [..] then adding that extra set of conditions would have filled me with dread. With this approach, it was no big deal.

(In this case it wasn't really changing requirements, it was me jumping in head first to try something out, rather than doing as much preparation as I could have.. and then finding I'd forgotten a thing a two).

I didn't start out by deciding to use a state machine, I hadn't written one before and had only a passing familiarity with the term. It just seemed like the best approach and it was only afterwards that I thought it would make sense to see if it was a common pattern and see how close or far away from the standard manner I was with what I'd written.

To be honest, although there is a lot of information available about this pattern, it didn't entirely click with me until I read this: Game Programming Patterns: State. It wasn't that I didn't see the point of them or that I could see much problem in implementing them, it was just.. they just didn't seem to slot very well into how I thought of things. In fact, I was having difficulty just trying to decide if my CSS Parser code could really be considered a state machine at all! But after reading that article, it all fell into place nicely. It's really well-written and the examples manage to demonstrate how quickly complexity escalates (and how this may be handled) while keeping things nice and concise.

Having linked to that article, hopefully what I'm going to write here won't seem redundant :)

Someone who I used to work with (hiya, Pricey!) got in touch with me about my parsing post and said that he'd also been getting to grips with the state machine pattern and we'd talked about using it to describe how a traffic light works. I presume that this is one of those examples that's been around forever. I have a very vague recollection of some interface between a BBC Micro and some sort of Lego-brick-mounted motors and lights and sensors when I was in my last year at primary school - one of the teaching projects was to try to model how a traffic light works. This was a loooooooong time before all those fancy Mindstorms Lego packages became available! And while researching this post, I've found numerous mention of traffic lights in relation to state machine tutorials or exercises.

Anyway... I thought this was a cool idea since a single traffic light is quite a simple prospect, but it could quickly be made increasingly complex by considering multiple sets of traffic lights controlling traffic at a crossroads, for example.

How do UK Traffic Lights work?

Traffic light strategies can be extremely complex when lights interact with each other so to begin with we'll just consider modelling a single set of lights controlling traffic flow. It seems like it would be odd to have traffic lights arbitrarily stopping cars if there is no traffic to flow perpendicular to it (whether that be pedestrians trying to cross or other cars at a junction or crossroads) but let's start simple.

  • The default light state is red
  • If a car arrives at the red light then after a short delay that red light will change to red-and-yellow
  • After another short delay, it will change to a green light - at this point, cars may pass through
  • After staying green for some time, it will change to a yellow light - at this point cars shouldn't really go through, but it's not illegal to
  • The next state is the same as the first state; a red light that won't change until traffic arrives at the light

The change from the first state occurs only if car(s) arrive at the light. The other transitions occur only according to the passing of time.

(If there were two sets of traffic lights at a crossroads - with two roads running perpendicular and controlling traffic in both directions on both roads - then the state of the traffic flow on the other road must be considered as well; just because both sets of lights have cars waiting to go doesn't mean they should both transition to green at the same time! But we'll talk about that later on..)

Modelling

Let's get straight in with some code. I'm going to declare an interface for a single traffic light state, the implementations of which will be immutable. Then I'll have a TrafficLight class which has a mutable state reference and that passes through possible transition triggers for car-has-arrived-at-lights and time-has-passed events. This class will also be used to log when the state visibly changes - eg. "red light to red-and-yellow light". So first the interface..

public interface IAmATrafficLightState
{
  ColourOptions Colour { get; }

  IAmATrafficLightState RegisterCarQueueing();

  /// <summary>
  /// This will represent the passing of an arbitrary slice of time. The "real time" duration of it
  /// is not important, its duration could be decreased or increased to make the simulation proceed
  /// more quickly or more slowly.
  /// </summary>
  IAmATrafficLightState RegisterPassageOfTime();
}

public enum ColourOptions
{
  GreenOnly,
  RedOnly,
  RedAndYellow,
  YellowOnly
}

.. and now the wrapper class...

public class TrafficLight
{
  private IAmATrafficLightState _state;
  public TrafficLight(IAmATrafficLightState initialState)
  {
    if (initialState == null)
      throw new ArgumentNullException("initialState");

    _state = initialState;
  }

  public ColourOptions Colour
  {
    get { return _state.Colour; }
  }

  public void RegisterCarQueueing()
  {
    var previousColour = _state.Colour;
    _state = _state.RegisterCarQueueing();
    if (_state.Colour != previousColour)
      Console.WriteLine("* Colour changed from " + previousColour + " to " + _state.Colour);
  }

  /// <summary>
  /// This will represent the passing of an arbitrary slice of time. The "real time" duration of it
  /// is not important, its duration could be decreased or increased to make the simulation proceed
  /// more quickly or more slowly.
  /// </summary>
  public void RegisterPassageOfTime()
  {
    var previousColour = _state.Colour;
    _state = _state.RegisterPassageOfTime();
    if (_state.Colour != previousColour)
      Console.WriteLine("* Colour changed from " + previousColour + " to " + _state.Colour);
  }
}

Before I get into how the states will be implemented, here's the app that will drive the simulation. All that happens is a loop periodically calls "trafficLight.RegisterPassageOfTime" and once every ten loops (on average, based on calls to Random.NextDouble) it calls trafficLight.RegisterCarQueueing. This logs when cars arrive at lights and have to stop, and it logs when they pass straight through. The thing only that determines whether they have to stop or whether they pass is the colour of the lights.

class Program
{
  static void Main(string[] args)
  {
    // This controls how fast the simulation proceeds at
    var baseTimeSlice = TimeSpan.FromMilliseconds(100);

    // This is the chance that each time slice a car arrives
    var probabilityOfCarArrivingEachTimeSlice = 0.1;

    var trafficLight = new TrafficLight(new RedLightWaitingForTraffic());
    var rnd = new Random();
    while (true)
    {
      if (rnd.NextDouble() < probabilityOfCarArrivingEachTimeSlice)
      {
        if (trafficLight.Colour == ColourOptions.GreenOnly)
          Console.WriteLine("Car didn't have to queue, went straight through");
        else if (trafficLight.Colour == ColourOptions.YellowOnly)
          Console.WriteLine("Car didn't have to queue, went straight through (naughty!)");
        else
        {
          Console.WriteLine("Register car queuing..");
          trafficLight.RegisterCarQueueing();
        }
      }

      Thread.Sleep(TimeSpan.FromMilliseconds(baseTimeSlice.TotalMilliseconds));

      trafficLight.RegisterPassageOfTime();
    }
  }
}

The first state is the only that is affected by traffic arriving at the light so we'll address that on its own -

/// <summary>
/// This is a red light that currently has no reason to change. If cars starting queuing up at it
/// then it will transition into starting the colour-change cycle.
/// </summary>
public class RedLightWaitingForTraffic : IAmATrafficLightState
{
  public ColourOptions Colour { get { return ColourOptions.RedOnly; } }

  public IAmATrafficLightState RegisterCarQueueing()
  {
    return new RedLightAboutToChangeLight();
  }

  public IAmATrafficLightState RegisterPassageOfTime()
  {
    // If all that's happening is that time is ticking along then there is nothing to action here
    return this;
  }
}

The other states will share a base class that deals with the boring work of wait-a-set-period-of-time-before-transitioning-to-another-state. This will make these states really easy to implement -

public class RedLightAboutToChangeLight : TimeBasedTransitiveState
{
  public const int TIME_TO_STAY_RED_AFTER_CAR_ARRIVES = 10;

  public RedLightAboutToChangeLight() : base(
    TIME_TO_STAY_RED_AFTER_CAR_ARRIVES,
    new RedAndYellowLight()) { }

  public override ColourOptions Colour { get { return ColourOptions.RedOnly; } }
}

public class RedAndYellowLight : TimeBasedTransitiveState
{
  public const int TIME_TO_WAIT_ON_RED_AND_YELLOW = 5;

  public RedAndYellowLight() : base(
    TIME_TO_WAIT_ON_RED_AND_YELLOW,
    new GreenLight()) { }

  public override ColourOptions Colour { get { return ColourOptions.RedAndYellow; } }
}

public class GreenLight : TimeBasedTransitiveState
{
  public const int TIME_TO_STAY_ON_GREEN = 100;

  public GreenLight() : base(
    TIME_TO_STAY_ON_GREEN,
    new YellowLight()) { }

  public override ColourOptions Colour { get { return ColourOptions.GreenOnly; } }
}

public class YellowLight : TimeBasedTransitiveState
{
  private const int TIME_TO_WAIT_ON_YELLOW = 5;

  public YellowLight() : base(
    TIME_TO_WAIT_ON_YELLOW,
    new RedLightWaitingForTraffic()) { }

  public override ColourOptions Colour { get { return ColourOptions.YellowOnly; } }
}

The TimeBasedTransitiveState base class is not particularly taxing, it would just be loads of duplication if wasn't abstracted away. Each time the "RegisterPassageOfTime" method is called on a class that is derived from TimeBasedTransitiveState, either a TimeBasedTransitiveStateInstance is returned (that has a reference back to the derived class so that the "Colour" property can be reported) or - if the countdown has completed - it returns the "nextState" reference.

/// <summary>
/// This represents a state that is predetermined to change and that may only be affected by the
/// passing of time. Any more cars queuing up at the light will have no effect. This may be a
/// green light that will stay green for a fixed period of time before cycling back through
/// red-and-yellow and then to red.
/// </summary>
public abstract class TimeBasedTransitiveState : IAmATrafficLightState
{
  private readonly int _timeSlicesToWaitFor;
  private readonly IAmATrafficLightState _nextState;
  protected TimeBasedTransitiveState(int timeSlicesToWaitFor, IAmATrafficLightState nextState)
  {
    if (timeSlicesToWaitFor <= 0)
      throw new ArgumentOutOfRangeException("timeSlicesToWaitFor");
    if (nextState == null)
      throw new ArgumentNullException("nextState");

    _timeSlicesToWaitFor = timeSlicesToWaitFor;
    _nextState = nextState;
  }

  public abstract ColourOptions Colour { get; }

  public IAmATrafficLightState RegisterCarQueueing()
  {
    return this;
  }

  public IAmATrafficLightState RegisterPassageOfTime()
  {
    if (_timeSlicesToWaitFor == 1)
      return _nextState;

    return new TimeBasedTransitiveStateInstance(this, _timeSlicesToWaitFor - 1, _nextState);
  }

  /// <summary>
  /// This is used to describe the states that are passed through while other classes derived from
  /// TimeBasedTransitiveState count down until they are allowed to reach their "nextState"
  /// </summary>
  private class TimeBasedTransitiveStateInstance : TimeBasedTransitiveState
  {
    public TimeBasedTransitiveStateInstance(
      IAmATrafficLightState source,
      int timeSlicesToWaitFor,
      IAmATrafficLightState nextState) : base(timeSlicesToWaitFor, nextState)
    {
      if (source == null)
        throw new ArgumentNullException("source");

      Source = (source is TimeBasedTransitiveStateInstance)
        ? ((TimeBasedTransitiveStateInstance)source).Source
        : source;
    }

    /// <summary>
    /// This will never be null and will never be a TimeBasedTransitiveStateInstance, it will always
    /// be the state that inherited TimeBasedTransitiveState and that has transitioned into a
    /// TimeBasedTransitiveStateInstance until the timer ticks down
    /// </summary>
    public IAmATrafficLightState Source { get; private set; }

    public override ColourOptions Colour { get { return Source.Colour; } }
  }
}

First pass complete!

That is actually all of the code required to run a simulation of the traffic light, according the behaviour I described earlier.

It's not all that exciting, though, is it? And it's not immediately obvious why writing this as a state machine would be particularly beneficial. (Although, there is an argument made that by the time you realise that a state machine might me most appropriate that it's too late: Why Developers Never Use State Machines). So let's ramp up the complexity a bit!

See you at the crossroads

Let's paint a picture. There's a road that runs North-South and one that runs East-West. Where they cross, there are traffic lights for both roads. For this example, I'm going to say that both sets of traffic lights work in the same manner as outlined above with one caveat: only one light may be anything other than red at any time. So if one set of lights is anywhere in the red-and-yellow, green, yellow cycle then the other lights must be red. As soon as that first set of lights becomes red again, the other set are eligible to cycle round if traffic requires that they do so.

There are all sorts of variations that could be made instead at this point. If the North-South road is always busier than the East-West road then, to maximise overall throughput, the lights on the North-South road might be configured to default to green unless there is East-West traffic. In America, I believe that you can turn right at crossroads if you're in the right lane, even when they're on red in some (if not all?) circumstances. I don't know if that changes the behaviour of the lights depending upon which lane traffic is in? Traffic light patterns can be further complicated by having different patterns applied at different times of the day and further again if lights at multiple junctions interact with each other - so traffic at one junction can affect other junctions by giving them knowledge of what traffic may be coming towards them. It actually sounds like it could be a really interesting field to work in!

Having an insight into how complex things could get makes the state machine pattern look like a good fit here.

Before I get stuck into the code again, I want to mention one thing that I'm not too happy with in the above code. When the YellowLight cycles round it transitions to a new instance of the RedLightWaitingForTraffic state. It seems like it would be more efficient to be able to reuse the instance that first cycled round to let traffic through. The Game Programming article I linked talks about using a "pushdown automaton", which really just means a stack for the states. So when the RedLightWaitingForTraffic transitions to the RedLightAboutToChangeLight, that new state is pushed onto the stack. When that transitions through RedAndYellowLight, GreenLight and YellowLight, these each replace the current state at the top of the stack. When the YellowLight state has completed, it pops off the stack, leaving the RedLightWaitingForTraffic.

To implement a state stack, instead of returning an IAmATrafficLight instance for each "RegisterCarQueueing" and "RegisterPassingOfTime" call, a StateTransition will be returned -

public class StateTransition
{
  public static StateTransition NoChange()
  {
    return new StateTransition(TransitionTypeOptions.NoChange, null);
  }
  public static StateTransition Pop()
  {
    return new StateTransition(TransitionTypeOptions.Pop, null);
  }
  public static StateTransition Push(IAmATrafficLightState state)
  {
    if (state == null)
      throw new ArgumentNullException("state");
    return new StateTransition(TransitionTypeOptions.Push, state);
  }
  public static StateTransition Replace(IAmATrafficLightState state)
  {
    if (state == null)
      throw new ArgumentNullException("state");
    return new StateTransition(TransitionTypeOptions.Replace, state);
  }

  private StateTransition(TransitionTypeOptions transitionType, IAmATrafficLightState newState)
  {
    if (!Enum.IsDefined(typeof(TransitionTypeOptions), transitionType))
      throw new ArgumentOutOfRangeException("transitionType");
    if ((transitionType == TransitionTypeOptions.NoChange)
    || (transitionType == TransitionTypeOptions.Pop))
    {
      if (newState != null)
        throw new ArgumentException("newState must be null if transitionType is NoChange or Pop");
    }
    else if (newState == null)
      throw new ArgumentException("newState must be non-null if transitionType is Push or Replace");

    TransitionType = transitionType;
    NewState = newState;
  }

  public enum TransitionTypeOptions
  {
    NoChange,
    Pop,
    Push,
    Replace
  }

  public TransitionTypeOptions TransitionType { get; private set; }

  /// <summary>
  /// This will be null if TransitionType is NoChange or Pop and non-null if TransitionType is
  /// Push or Replace
  /// </summary>
  public IAmATrafficLightState NewState { get; private set; }
}

This is going to require a change to the "TrafficLight wrapper class but before that I'm going to introduce a change to the IAmATrafficLightState interface by adding the property "Status" -

public interface IAmATrafficLightState
{
  ColourOptions Colour { get; }
  StatusOptions Status { get; }

  StateTransition RegisterCarQueueing();
  StateTransition RegisterPassageOfTime();
}

public enum StatusOptions
{
  HandlingTraffic,
  NotHandlingTraffic
}

If the North-South TrafficLight instance is currently in a state that reports that it is "HandlingTraffic" then the East-West TrafficLight may not be in any state that does not indicate a red light (and vice versa).

This "Status" will be easy to add to the states we've already defined. Anything other than the RedLightWaitingForTraffic will have the Status "HandlingTraffic" (including RedLightAboutToChangeLight since, by the point at which that state has been reached, the traffic light is committed to going through a full cycle). RedLightWaitingForTraffic will have the status "NotHandlingTraffic" since traffic is not actually passing through the lights (or about to pass through) so any dependent lights are free to change.

Two additional states need to be added to smoothly integrate this new status data, however. The first is the RedLightWaitingForAccess state. Previously, the pattern to change from red was as follows

  • The state is RedLightWaitingForTraffic
  • Car(s) arrive
  • State changes to RedLightAboutToChangeLight
  • A short delay occurs
  • State changes to RedAndYellowLight
  • A short delay occurs
  • etc..

I'm not entirely sure why there is this short delay before changing to red-and-yellow with real-life traffic lights. I'm not sure if it's something to do with traffic calming, whether it improves traffic flow in a non-intuitive manner, whether it's about ensuring that drivers assume they will always have to come to a full stop when approaching a red light or if there's another explanation. What I do know, though, is that if traffic is already queued up at a crossroads' red light since the other road has traffic passing, then this delay should be removed. When the other road changes to red, the traffic lights for the road with backed-up cars should be able to transition straight to red-and-yellow.

The RedLightWaitingForAccess covers this case. It is not affected by more cars arriving at the lights but each time slice it will check the status of the other road's lights and change state to RedAndYellowLight as soon as those other lights report "NotHandlingTraffic".

The other new state is the RedLightPausedBeforeWaitingForTraffic. A YellowLight will transition to this before returning to RedLightWaitingForTraffic. This imposes a short delay on a set of traffic lights which guarantees that it will stay in a state with status "NotHandlingTraffic" after allowing through traffic. This will ensure that traffic lights on the other road can transition if required, even if a car arrives at the set of traffic lights that just cycled round. Essentially, it makes sure that if traffic is trying to pass both North-South and East-West then the roads "take turns" in allowing traffic to pass.

The new code

To work with the new IAmATrafficLightState interface and to add support for a "state stack", the TrafficLight wrapper class will need to be updated -

public class TrafficLight
{
  private readonly Stack<IAmATrafficLightState> _states;
  public TrafficLight(string trafficLightId, IAmATrafficLightState initialState)
  {
    if (string.IsNullOrWhiteSpace(trafficLightId))
      throw new ArgumentNullException("Null/blank trafficLightId specified");
    if (initialState == null)
      throw new ArgumentNullException("initialState");

    TrafficLightId = trafficLightId.Trim();
    _states = new Stack<IAmATrafficLightState>();
    _states.Push(initialState);
  }

  public string TrafficLightId { get; private set; }

  public ColourOptions Colour
  {
    get { return _states.Peek().Colour; }
  }

  public StatusOptions Status
  {
    get { return _states.Peek().Status; }
  }

  public void RegisterCarQueueing()
  {
    ApplyTransition(_states.Peek().RegisterCarQueueing());
  }

  public void RegisterPassageOfTime()
  {
    ApplyTransition(_states.Peek().RegisterPassageOfTime());
  }

  private void ApplyTransition(StateTransition transition)
  {
    if (transition == null)
      throw new ArgumentNullException("transition");

    var previousColour = _states.Peek().Colour;
    if (transition.TransitionType == StateTransition.TransitionTypeOptions.NoChange)
    {
      // Do nothing
    }
    else if (transition.TransitionType == StateTransition.TransitionTypeOptions.Pop)
    {
      if (_states.Count == 1)
        throw new ArgumentException("Invalid transition - may not remove last state in the stack");
      _states.Pop();
    }
    else if (transition.TransitionType == StateTransition.TransitionTypeOptions.Push)
      _states.Push(transition.NewState);
    else if (transition.TransitionType == StateTransition.TransitionTypeOptions.Replace)
    {
      _states.Pop();
      _states.Push(transition.NewState);
    }
    else
      throw new ArgumentException("Unsupported transition type: " + transition.TransitionType);
    var newColour = _states.Peek().Colour;
    if (newColour != previousColour)
      Console.WriteLine("* " + TrafficLightId + " changed " + previousColour + " to " + newColour);
  }
}

I've included a "TrafficLightId" property so that the console messages indicate which traffic light has changed colour. The code that is common for each state change event has been pulled out into its own method and the class also exposes the new "Status" property. It's not valid for the state stack to ever be empty (since that would indicate that it has no state, which makes no sense - this is guaranteed by the code in this class) and so the Colour and Status values can be taken by looking at the state at the top of the stack.

The RedLightWaitingForTraffic requires three changes. Firstly to return StateTransition instances from its "RegisterCarQueueing" and "RegisterPassageOfTime" methods instead of IAmATrafficLightState implementations. Secondly to expose the new IAmATrafficLightState Status property. And thirdly to accept a filter that may prevent it from allowing traffic through at any given time.

This filter is what prevents the North-South road traffic lights from changing from red if the East-West road is currently allowing through traffic. If cars are queuing at lights but the lights may not change colour at this time, then the state changes from RedLightWaitingForTraffic to the new RedLightWaitingForAccess state. If they are able to change then they proceed as before.

public class RedLightWaitingForTraffic : IAmATrafficLightState
{
  private readonly Func<bool> _isAllowedToLetTrafficThrough;
  public RedLightWaitingForTraffic(Func<bool> isAllowedToLetTrafficThrough)
  {
    if (isAllowedToLetTrafficThrough == null)
      throw new ArgumentNullException("isAllowedToLetTrafficThrough");

    _isAllowedToLetTrafficThrough = isAllowedToLetTrafficThrough;
  }

  public ColourOptions Colour { get { return ColourOptions.RedOnly; } }
  public StatusOptions Status { get { return StatusOptions.NotHandlingTraffic; } }

  public StateTransition RegisterCarQueueing()
  {
    if (_isAllowedToLetTrafficThrough())
      return StateTransition.Push(new RedLightAboutToChange());

    return StateTransition.Push(new RedLightWaitingForAccess(_isAllowedToLetTrafficThrough));
  }

  public StateTransition RegisterPassageOfTime()
  {
    return StateTransition.NoChange();
  }
}

The new RedLightWaitingForAccess state will just try to proceed to the RedAndYellowLight state each time slice, if the filter allows it. Otherwise it has to stay as it is.

public class RedLightWaitingForAccess : IAmATrafficLightState
{
  private readonly Func<bool> _isAllowedToLetTrafficThrough;
  public RedLightWaitingForAccess(Func<bool> isAllowedToLetTrafficThrough)
  {
    if (isAllowedToLetTrafficThrough == null)
      throw new ArgumentNullException("isAllowedToLetTrafficThrough");

    _isAllowedToLetTrafficThrough = isAllowedToLetTrafficThrough;
  }

  public ColourOptions Colour { get { return ColourOptions.RedOnly; } }
  public StatusOptions Status { get { return StatusOptions.NotHandlingTraffic; } }

  public StateTransition RegisterCarQueueing()
  {
    // We can't do anything here, we're already waiting
    return StateTransition.NoChange();
  }

  public StateTransition RegisterPassageOfTime()
  {
    if (_isAllowedToLetTrafficThrough())
      return StateTransition.Replace(new RedAndYellowLight());

    return StateTransition.NoChange();
  }
}

The other states require only minor changes to implement the new interface (note that I've snuck in the other new state here, the RedLightPausedBeforeWaitingForTraffic) -

public class RedLightAboutToChange : TimeBasedTransitiveState
{
  public const int TIME_TO_STAY_RED_AFTER_CAR_ARRIVES = 10;

  public RedLightAboutToChange() : base(
    TIME_TO_STAY_RED_AFTER_CAR_ARRIVES,
    StateTransition.Replace(new RedAndYellowLight())) { }

  public override ColourOptions Colour { get { return ColourOptions.RedOnly; } }

  /// <summary>
  /// We're committed to letting traffic pass at this point so declare HandlingTraffic
  /// </summary>
  public override StatusOptions Status { get { return StatusOptions.HandlingTraffic; } }
}

public class RedAndYellowLight : TimeBasedTransitiveState
{
  public const int TIME_TO_WAIT_ON_RED_AND_YELLOW = 5;

  public RedAndYellowLight() : base(
    TIME_TO_WAIT_ON_RED_AND_YELLOW,
    StateTransition.Replace(new GreenLight())) { }

  public override ColourOptions Colour { get { return ColourOptions.RedAndYellow; } }
  public override StatusOptions Status { get { return StatusOptions.HandlingTraffic; } }
}

public class GreenLight : TimeBasedTransitiveState
{
  public const int TIME_TO_STAY_ON_GREEN = 100;

  public GreenLight() : base(
    TIME_TO_STAY_ON_GREEN,
    StateTransition.Replace(new YellowLight())) { }

  public override ColourOptions Colour { get { return ColourOptions.GreenOnly; } }
  public override StatusOptions Status { get { return StatusOptions.HandlingTraffic; } }
}

public class YellowLight : TimeBasedTransitiveState
{
  private const int TIME_TO_WAIT_ON_YELLOW = 5;

  public YellowLight() : base(
    TIME_TO_WAIT_ON_YELLOW,
    StateTransition.Replace(new RedLightPausedBeforeWaitingForTraffic())) { }

  public override ColourOptions Colour { get { return ColourOptions.YellowOnly; } }
  public override StatusOptions Status { get { return StatusOptions.HandlingTraffic; } }
}

public class RedLightPausedBeforeWaitingForTraffic : TimeBasedTransitiveState
{
  private const int TIME_AFTER_RESETTING_TO_RED_BEFORE_CONSIDERING_TRAFFIC = 5;

  public RedLightPausedBeforeWaitingForTraffic() : base(
    TIME_AFTER_RESETTING_TO_RED_BEFORE_CONSIDERING_TRAFFIC,
    StateTransition.Pop()) { }

  public override ColourOptions Colour { get { return ColourOptions.RedOnly; } }
  public override StatusOptions Status { get { return StatusOptions.NotHandlingTraffic; } }
}

The TimeBasedTransitiveState code requires only minor tweaks (since I've gone for a code-heavy post, I thought I might as well include everything! :)

public abstract class TimeBasedTransitiveState : IAmATrafficLightState
{
  private readonly int _timeSlicesToWaitFor;
  private readonly StateTransition _nextState;
  protected TimeBasedTransitiveState(int timeSlicesToWaitFor, StateTransition nextState)
  {
    if (timeSlicesToWaitFor <= 0)
      throw new ArgumentOutOfRangeException("timeSlicesToWaitFor");
    if (nextState == null)
      throw new ArgumentNullException("nextState");

    _timeSlicesToWaitFor = timeSlicesToWaitFor;
    _nextState = nextState;
  }

  public abstract ColourOptions Colour { get; }
  public abstract StatusOptions Status { get; }

  public StateTransition RegisterCarQueueing()
  {
    return StateTransition.NoChange();
  }

  public StateTransition RegisterPassageOfTime()
  {
    if (_timeSlicesToWaitFor == 1)
      return _nextState;

    return StateTransition.Replace(
      new TimeBasedTransitiveStateInstance(this, _timeSlicesToWaitFor - 1, _nextState)
    );
  }

  private class TimeBasedTransitiveStateInstance : TimeBasedTransitiveState
  {
    public TimeBasedTransitiveStateInstance(
      IAmATrafficLightState source,
      int timeSlicesToWaitFor,
      StateTransition nextState) : base(timeSlicesToWaitFor, nextState)
    {
      if (source == null)
        throw new ArgumentNullException("source");

      Source = (source is TimeBasedTransitiveStateInstance)
        ? ((TimeBasedTransitiveStateInstance)source).Source
        : source;
    }

    public IAmATrafficLightState Source { get; private set; }

    public override ColourOptions Colour { get { return Source.Colour; } }
    public override StatusOptions Status { get { return Source.Status; } }
  }
}

The tester app now has to instantiate two TrafficLight instances and update them both. It has to be able to pass a filter to each of the initial RedLightWaitingForTraffic instances (one for the North-South route and one for East-West) but that's simple; it need only look at the Status of the other lights and allow traffic if the other Status reports "NotHandlingTraffic".

class Program
{
  static void Main(string[] args)
  {
    // This controls how fast the simulation proceeds at
    var baseTimeSlice = TimeSpan.FromMilliseconds(100);

    // This is the chance that each time slice a car arrives
    var probabilityOfCarArrivingEachTimeSlice = 0.1;

    // The eastWestTrafficLight reference is required by the isAllowedToLetTrafficThrough filter
    // passed to the initial RedLightWaitingForTraffic state for the North-South traffic light so
    // it has to be set to something (otherwise we'll get a compiler error). At this point that
    // has to be null but it will be set to the real value immediately after. The filter won't be
    // used until the RegisterCarQueueing and RegisterPassageOfTime methods are called, so it
    // doesn't matter that the filter temporarily has a null reference.
    TrafficLight eastWestTrafficLight = null;
    var northSouthTrafficLight = new TrafficLight(
      "N-S",
      new RedLightWaitingForTraffic(
        () => (eastWestTrafficLight.Status == StatusOptions.NotHandlingTraffic)
      )
    );
    eastWestTrafficLight = new TrafficLight(
      "E-W",
      new RedLightWaitingForTraffic(
        () => (northSouthTrafficLight.Status == StatusOptions.NotHandlingTraffic)
      )
    );

    var allTrafficLights = new[] { northSouthTrafficLight, eastWestTrafficLight };
    var rnd = new Random();
    while (true)
    {
      foreach (var trafficLight in allTrafficLights)
      {
        if (rnd.NextDouble() < probabilityOfCarArrivingEachTimeSlice)
        {
            if (trafficLight.Colour == ColourOptions.GreenOnly)
            {
              Console.WriteLine(
                "Car didn't have to queue {0}, went straight through",
                trafficLight.TrafficLightId
              );
            }
            else if (trafficLight.Colour == ColourOptions.YellowOnly)
            {
              Console.WriteLine(
                "Car didn't have to queue {0}, went straight through (naughty!)",
                trafficLight.TrafficLightId
              );
            }
            else
            {
              Console.WriteLine("Register car queuing {0}..", trafficLight.TrafficLightId);
              trafficLight.RegisterCarQueueing();
            }
        }
      }

      Thread.Sleep(TimeSpan.FromMilliseconds(baseTimeSlice.TotalMilliseconds));

      foreach (var trafficLight in allTrafficLights)
        trafficLight.RegisterPassageOfTime();
    }
  }
}

Win?

It might look like quite a lot of code since I've decided to include all of the code here. But there wasn't that much new code required to go from supporting the simple one-traffic-light example to the more complex configuration. And at each step, it's easy to see what exactly is going on and how the various interactions are being handled.

That's the real benefit of the state machine pattern, adding complexity is much cheaper than it is with more naive approaches. If we wanted to add another set of lights here (maybe there's a pedestrian crossing) then doing so wouldn't blow up the code complexity. Even if we bear in mind the fact that pedestrian crossing lights have different rules to traffic lights (there's only a red man and a green man - or "walk" and "don't walk", if you prefer - there's no yellow light).

Another interesting pattern would be to vary the length that the green light stays on for, depending upon the traffic pressure building up on the other road. This might require a way to pass a "pressure retriever" reference through to the GreenLight (similar to the is-access-allowed delegate that the RedLightWaitingForTraffic and RedLightWaitingForAccess states have, but with a sliding scale rather than a simple yes-or-no), but all of the complexity would be contained within that GreenLight state.

It's also worth noting that the mutability of the data is tightly restricted to the TrafficLight class and the "isAllowedToLetTrafficThrough" delegates. As always, this makes reasoning about the behaviour of the code much easier and can make the solution more robust. If a model was created where events would be raised on different threads then the number of places which would have to explicitly deal with access from different threads would be limited as it is only places where data is mutated that multi-threaded access tends to pose a problem. It makes me happy when I find even more reassurance that immutability is the way forward :)

So now all I have to do is try to look out for more times when this pattern will be appropriate (and try to avoid trying to crowbar it into places where it isn't)!

Posted at 23:45

Comments