---

Output Structure

To make it easier to find what was returned for each individual unified variable, I changed the output from an AoA, to an AoH, where each unified variable is placed into each hash by name. Therefore, the output will look like this:

[
  { Var1 => Value1, Var2 => Value2 },
  { Var1 => Value3, Var2 => Value4 }
]
[download]

Unification Code
Note before starting: important arguments are those where the user has specified undef, the empty string, or an underscore as the argument value, and means that they do not care what value that argument takes on.

Stage 0
I called this stage 0, because it occurs before the main unification code. This stage checks if only one of the arguments passed in was a variable. If this is the case, then we can just get a list of all the possible values for that argument position, and create our AoH from that, because at this stage, we have already checked that all of the constant arguments exist in their positions.

Stage 1
First of all we take our array of arguments, and convert it into another array where any constants are replaced with their vertex id's, and everything else is blank. We'll call this array @new_args. This code was in Ovid's original attempt at unification, although I am going to use it differently to Ovid.

Stage 2
In this stage we prepare the first important element of @new_args in readiness for stage 3. If the element is empty, it means that this argument must be a variable. In this case, we retrieve the list of possible values for the argument, and place this structure into the array element:

[ [vertex_1_id, undef], ...., [vertex_n_id, undef] ]
[download]

To make things simpler later on in this explanation, we will consider this to be an array of pairings.
If the array element contained a value, it means that this argument must be a constant, and that the value is the vertex_id of that constant. In this case we create the same structure as above, but with just that one vertex_id.

We are now ready for the next stage, where we operate on two elements of @new_args at a time. Carrying out this preparation, means that in the next stage the 1st element being operating upon is always prepared for us, thereby removing the need for any special cases in the loop.

Stage 3
We will now loop through the important elements of our new_args array, two at a time. If we have three elements, we will therefore operate on elements 0&1, and then 1&2. What we do at each cycle of the loop is dependant on what is contained in the 2nd of the two elements we are operating on at any one time.

If the element contains a value, then as before that element is constrained to only take on that value. First we replace the value with an empty array. Then we loop over every pairing in the 1st element, and check if it possible to get from the value in the pairing to our fixed value from the 2nd element. If it is, then we will add a new pairing to our array. However, instead of having undef as the 2nd value of the pair, we put in a reference to the pairing from the 1st element we are working on.

Alternatively, if the element was empty, things are slightly more involved. We now have to loop every pairing in the 1st element, and find every possible value for the 2nd element that we can get to, adding linked pairings every time as above.

Stage 3 example
To make this slightly easier to understand (hopefully), i'll provide an example at this stage.
We will start with these facts (taken from the unification tests file):

$pg->add_fact( gnarfle => qw/ foo bar baz / );
$pg->add_fact( gnarfle => qw/ foo tac toe / );
$pg->add_fact( gnarfle => qw/ tic tac toe / );
[download]

We can now make this query:

$data = $pg->gnarfle( qw/ $one tac $three / )
[download]

And we will get a @new_args array as follows (arguments displayed to the side of the actual array):

[
  [ [7, undef], [2, undef] ],            ' $one

          ^           ^
  [ [5,   |  ], [5,   |  ] ],            ' tac

          ^           ^
  [ [6,   |  ], [6,   |  ] ]             ' $three
]
[download]

Note that this is a simple example, and with more complicated ones you can get more than one pairing pointing at the same parent.

Stage 4
We now want to take our @new_args array and convert it into a AoH to return to the user. Each result to be returned is made up of a chain of pairings starting from one of the pairings in the final element of @new_args. From our example above then, we would have the sequences 6->5->7, and 6->5->2.

To retrieve and convert these sequences, i simply loop over the pairings in the final element, and then follow the chains for each one, adding values to the output hashes whenever one of the arguments represents a variable. So, as the result of converting the @new_args from our example, we get:

[
  { $one => 'foo', $three => 'toe' },
  { $one => 'tic', $three => 'toe' }
]
[download]

and this is what we return to the user.