John Hobbs

On a recent project I had the need to implement a basic search functionality into a web interface. This isn’t unusual, but what was different is that the data in this project was fairly static, and was kept in JSON on disk (and cached into memory). Additionally, there would be a point where it was moved off of our servers, onto an entirely different stack (hence the JSON).

There was minimal server side processing so far, and I did not want to add more overhead that would need to be ported. So, I decided to implement my search in JavaScript (with some help from Python). My idea was to do very basic string matching on a pre-built index. In this article I am going to lay out my implementation, but on a dummy data set.

The Process

This search breaks down into three steps:

1. Build Search Index
2. Perform Search
3. Connect To Interface

Before we start writing that, let’s cover the data.

The Data

Here is the data I will be sifting through. To keep it simple, I’m just searching through some sentences with associated ID’s. It’s short and simple, but with some tweaks you can apply this to bigger data sets, as I did.

My data set will be represented in JSON for portability and easy interpretation from JavaScript.

{
  "entries": [
    {
      "id": 1,
      "title": "The lazy white cat slept.",
      "body": "What a lazy cat."
    },
    {
      "id": 2,
      "title": "George, though angry, didn't make a sound.",
      "body": "George is a quiet man."
    },
    {
      "id": 3,
      "title": "Anyone could see that white didn't suit her.",
      "body": "Plus, it's after Labor Day."
    },
    {
      "id": 4,
      "title": "By Thor's Hammer, I will have my revenge.",
      "body": "Also, by Odin's Eye"
    },
    {
      "id": 5,
      "title": "Get off the couch you lazy bum.",
      "body": "Yeah, it's way better to sit at a computer desk."
    }
  ]
}

The Index

To facilitate easy matching, I’m going to build a search index that will be a dictionary, with individual words (tokens) as the keys, and arrays of ID’s as the values.

I’ve decided on Python for my index builder. Handling JSON from Python is easy, though if you have a version older than 2.6 you will need to use a different import, such as simplejson.

The core of this functionality is the tokenizer. To build this, we need to determine our rules. Since this is a simple search, I’m going to tokenize on word boundaries, it will be case insensitive, and I will only accept the characters A-Z, single quote and dash inside of a word.

Here is my implementation of the tokenizer, that follows these rules:

6
7
8
9

def tokenize ( string ):
  # Strip extra punctuation
  string = re.sub( r'[^a-z0-9A-Z \'\-]', '', string.lower() )
  return string.split( ' ' )

The remainder of the Python is simply opening and parsing the JSON.

13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

  index = {}
 
  with open( 'data.json', 'r' ) as handle:
    obj = json.loads( handle.read() )
 
    for entry in obj['entries']:
      # Break up both title and body
      tokens = tokenize( entry['title'] )
      tokens.extend( tokenize( entry['body'] ) )
 
      # Make them unique by casting to set
      tokens = set( tokens )
 
      # Now add them to the index
      for token in tokens:
        # Make a new entry for the token if it doesn't exist
        if token not in index.keys():
          index[token] = []
        # Add this id to the list of matches for this token
        index[token].append( entry['id'] )

Run that, and we get the dictionary we wanted:

$ python build_index.py
{u'a': [1, 2, 5],
 u'after': [3],
 u'also': [4],
 u'angry': [2],
 u'anyone': [3],
 ...

JavaScript

Now that we have an index to work with, let’s convert it to JSON. This just takes a little tweak to the Python.

33
34

  with open( 'index.json', 'w' ) as handle:
    handle.write( json.dumps( index ) )

That gives us a JSON file to work with.

{"thor's": [4], "is": [2], "bum": [5], "didn't": [2, 3], "yeah": [5], ...

Now we’re going to load that JSON with an AJAX call, so we have the index to work with.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  init: function () {
    Search.$results = $( '#search-results' );
 
    $.getJSON( 'index.json' )
      .error( Search.index_load_error )
      .success( Search.index_load_success );
  },
 
  index_load_error: function () {
    Search.$results.append( $('<li/>').text( 'Error Loading Index' ) );
  },
 
  index_load_success: function ( data ) {
    Search.index = data;
  },

Once we have that data, finding matches is just a matter of looking them up in Search.index. Below I’ve used a loop that will search through an array of terms, and then accumulate the matches.

25
26
27
28
29
30
31
32

    var matches = [];
 
    // For each term passed in, check it in the index
    $.each( terms, function ( i, term ) {
      if( Search.index[term] ) {
        matches = matches.concat( Search.index[term] );
      }
    } );

It works!

Hook It Up

Just a little bit remains to connect this thing. First we need to port over the tokenizer from Python to get a consistent result. Pretty easy port.

47
48
49
50
51

  tokenize: function ( string ) {
    string = string.toLowerCase();
    string = string.replace( /[^a-z0-9A-Z \'\-]/, '' );
    return string.split( ' ' );
  }

JavaScript tokenize in action.

Last we just need to apply our functions to some inputs, which we hook up with some jQuery.

17
18
19
20
21
22
23
24
25
26
27
28
29
30

      $( function () {
        $( '#search-terms' ).keyup( function () {
          var results = Search.search( Search.tokenize( $(this).val() ) ),
              $results = $( '#search-results' );
 
          // Clear current results
          $results.children().remove();
 
          // Add new ones
          $.each( results, function ( index, element ) {
            $results.append( $( '<li/>' ).text( element ) );
          } );
        } );
      } );

Make It Better

This is not, by any means, a complete system. You would want to grab the results and match up the ID’s to a more useful output. Additionally, you could drop the AJAX call and use a script tag to bring in the index.

There are plenty of improvements you can make, and I’d love to know if you make them!

For reference, here is the complete source: https://gist.github.com/1673557.

Related Posts

1. Replacing MySQL FULLTEXT With JavaScript
2. Linux Multiple File Search And Replace
3. Javascript Colorshifter

I recently did some work with cache control in Kohana and found the documentation a little thin out there, so I thought I would share what I learned.

Kohana has nice built in functionality for ETag validations, so you don’t really need to roll your own cache headers.

If you need to brush up on web caching in general, I would recommend a quick read of Caching Tutorial for Web Authors and Webmasters, an excellent and concise reference.

Setup

For the purposes of this example, I’m creating a small controller which will use a short string as it’s response body. The implementation here is trivial.

1
2
3
4
5
6
7
8
9

<?php defined('SYSPATH') or die('No direct script access.');
 
  class Controller_Example extends Controller {
 
    public function action_index () {
      $this->response->body( 'Hello, world!' );
    }
 
  } // Controller_Example

Let’s look at the headers that are returned by default. Your headers may vary, so adjust accordingly.

If you look at the response headers from this request, you will note that there no Cache-Control, Last-Modified or ETag headers are returned. That gives us a blank slate to work with.

ETag

An ETag is a unique identifier string describing your content for cache validation. ETags have an advantage over Last-Modified headers in that there is no need to worry about clock synchronization. The server can determine how to generate ETags in any manner it desires.

The Response object in Kohana provides two methods useful for ETag based caching. The first is Response::generate_etag(), the second is Response::check_cache().

Response::generate_etag()

This method uses the sha1 hash to create a unique ETag based on the content of the rendered response. Because it renders and hashes the response before returning a result, there is a memory and CPU time hit, which increases with the size of your response.

Response::check_cache()

This method is the one we will use directly, as it compares the ETag of the response to request headers and takes the appropriate action.

It’s signature is ($etag = NULL, Request $request = NULL). This is a bit odd, because although both are NULL by default, and the Request parameter is second, it is not optional while $etag is.

If you provide NULL for $etag the method will use Response::generate_etag() to get a valid ETag. As mentioned above, this is not always the optimal choice, so if you have a unique identifier that you can provide, you should.

Since this is a simplistic example, I will let Response::generate_etag() create my ETag value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

<?php defined('SYSPATH') or die('No direct script access.');
 
  class Controller_Example extends Controller {
 
    public function after () {
      parent::after();
      $this->response->check_cache( null, $this->request );
    }
 
    public function action_index () {
      $this->response->body( 'Hello, world!' );
    }
 
  } // Controller_Example

Let’s see the response headers for this version. We now have an ETag header, at the very bottom.

If we refresh the page again, we see that the browser sends an “If-None-Match” request header, which Response::check_cache() compares to the ETag. Finding that they match, the method returns a 304 response and immediately exits the script, causing the browser to use the cached version and saving the time it would take to send those bytes.

To demonstate how the ETag is generated let’s modify our response body so that it returns new content for every request (well, every second at least).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

<?php defined('SYSPATH') or die('No direct script access.');
 
  class Controller_Example extends Controller {
 
    public function after () {
      parent::after();
      $this->response->check_cache( null, $this->request );
    }
 
    public function action_index () {
      $this->response->body( 'Hello, world at ' . date( DATE_RSS ) . '!' );
    }
 
  } // Controller_Example

After refreshing we get a new body, and a new ETag, breaking the cache and re-sending the entire page.

Remember, if you implement this, you should try to use an alternate ETag value if you can.

Cache Control

ETags aren’t useful without a Cache-Control header, but you can set that yourself with Response::headers(), just be aware that Response::check_cache() will append must-revalidate to your header value, so don’t add that part yourself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<?php defined('SYSPATH') or die('No direct script access.');
 
  class Controller_Example extends Controller {
 
    public function after () {
      parent::after();
      $this->response->headers( 'cache-control', 'private' );
      $this->response->check_cache( null, $this->request );
    }
 
    public function action_index () {
      $this->response->body( 'Hello, world at ' . date( DATE_RSS ) . '!' );
    }
 
  } // Controller_Example

Hopefully that clears up how to use the built in browser cache handling in Kohana 3, please leave your own tips or experiences in the comments!

Related Posts

1. Kohana 3 OAuth & Twitter Demo Code
2. Clean Auth module usage in Kohana
3. Simple PHP Caching

1. Thursday Quote: Brian Malow
2. Thursday Quote: Brian Tarbox
3. Thursday Quote: Andrew Wulf

“A complete commitment to immutability is a commitment to never building anything real.”

- Yaron Minksy
OCaml for the Masses

Related posts:

1. Thursday Quote: Ed Nather
2. Thursday Quote: David Greiner
3. Thursday Quote: _why

I’ve noticed a trend in PHP code to shy away from function application and closures. I understand to some extent. Useful, inline anonymous functions were not available until 5.3.0, which is relatively new. And create_function is an abomination.

Still, I think that PHP programmers just don’t think in this mindset, but it can be very useful.

Here is a rather contrived example, but one I’ve honestly seen an analogue of before.

1
2
3
4
5

$accumulator = array();
foreach( $this->tags->all() as $tags ) {
  $accumulator[] = htmlspecialchars( $tag->name );
}
return implode( ', ',  $accumulator );

Easy to understand, simple, does the job, but it is far more verbose than it needs to be.

Here is a version using array_map.

1
2

$tags = array_map( 'htmlspecialchars', $this->tags->all() );
return implode( ', ', $tags );

The array_map function is doing all the work of the loop, but you don’t have to write it and you don’t have to manage the accumulator.

Doesn’t that feel better?

Next time you mangle an array, first think if array_map or it’s friends array_filter or array_reduce could do it better.

Related posts:

1. Simple BBCode To HTML Function In PHP
2. Handling Forms With PHP
3. PHP/Cron Based IP Tracker

What the hash?

This post is about a fundamental programming concept, hashing.

“A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys.”

Hash function
Wikipedia – 2011/11/15

So, a hashing function can turn this:

Hello, my name is John Hobbs. I like hashes.

into this:

8ced81aa42cd91930024054f26ed92ea

Doesn’t seem super useful, does it? The content looses its semantic value. 8ced81aa42cd91930024054f26ed92ea is not the same as a personal introduction.

That’s okay though, we can find a use for a hash that won’t be seen by a human.

But first, let’s try our hand at writing a hash function.

Mapping to keys

So, the principal function of a hashing algorithm is to reduce a large block of data into a smaller block of data.

Let’s set up some arbitrary limits for developing our function.

For simplicity, let’s work at hashing values into a one byte integer, so eight bits.

Let’s also focus on only hashing ASCII strings, since ASCII characters are conveniently one byte long.

Now that that is established, let me propose a hashing function in pseudo-code:

let hash = 0
for each character in string:
  let hash = hash XOR character

For those of you not familiar with XOR, I mean exclusive or. This means comparing the bytes bit by bit. If the bits are the same, the result is zero. If they are different, the result is one. The common notation for XOR is ^. Here’s an example of 5 ^ 117:

  00000101 =   5
^ 01110101 = 117
----------------
  01110000 = 112

Working at a byte by byte level like this ensures that our hash will not exceed 8 bits in length, or an integer value of 128.

Buckets

With our shiny little hash function in mind, let’s use find a use.

One great use is lookup tables. These are sometimes called dictionaries, associated arrays, hash tables, etc.

Basically, they map a key to a value. So you tell a table that “my name” is “john”, and then later, if you ask it for “my name” is tells you “john”. Great tool for amnesiacs.

Hashing is perfect here for faster lookups, and for giving bound memory performance.

Think of it as a finite line of buckets. When you want to store something you hand it to the walrus, and say “Please keep this fish in a bucket called ‘Salmon’.”

Now, the walrus only has so many buckets, and none of them are labeled “Salmon”.

So, he uses a special walrus method (a hashing function) that deterministically says “Salmon == 5″, and puts the fish in the fifth bucket.

Later, when you come back and ask for the fish from the “Salmon” bucket, he knows to get the fish out of the fifth bucket because he can derive that “Salmon == 5″ using the same method as before.

Unfortunately, he ate the fish already, so there is nothing to give you

Walrus are selfish that way.

Implementation

Now that we have a use case, let’s implement our hashing function.

I chose JavaScript here.

1
2
3
4
5
6
7

function hash ( string ) {
  var c = 0;
  for( var i = 0; i < string.length; i++ ) {
    c = c ^ string[i].charCodeAt();
  }
  return c;
};

Let’s give it a try:

1
2
3
4

console.log( hash( "hello" ) );
// prints "98"
console.log( hash( "goodbye" ) );
// prints "125"

Cool! Now there is just a little more glue to make this complete. We have to have a get and a set for values, and an array to store them in.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

var SimpleHashTable = function () {
 
  // these are the buckets
  this.table = new Array(128);
 
  // hand it to the walrus
  this.set = function ( key, value ) {
    this.table[this.hash( key )] = value;
  };
 
  // get it from the walrus
  this.get = function ( key ) {
    return this.table[this.hash( key )];
  };
 
  // walrus math
  this.hash = function ( string ) {
    var c = 0;
    for( var i = 0; i < string.length; i++ ) {
      c = c ^ string[i].charCodeAt();
    }
    return c;
  };
 
};

The get and set functions are pretty similar. You hash the key, and use that integer as the index to either set, or retrieve a value in the table array.

Let’s give it a try!

var ht = new SimpleHashTable();
ht.set( "salutations", "Hello, good sir." );
console.log( ht.get( "salutations" ) );
// prints "Hello, good sir."

Perfect!

Collision course

Now let’s use our SimpleHashTable to store some stuff!

1
2
3
4
5
6

ht.set( "salutations", "Hello, good sir." );
console.log( ht.get( "salutations" ) );
// prints "Hello, good sir."
ht.set( "q", "BARF!" )
console.log( ht.get( "salutations" ) );
// prints "BARF!"

Wait, what the heck just happened?!

It shouldn’t have printed the value for q, we asked for salutations!

This is known as a collision, and it happens.

What happened is that the hash value we compute for q is the same value as the hash for salutations. It’s bound to happen, we only have 128 possible buckets and an infinite amount of possible keys.

So we have several ways to improve this situation.

One option is more buckets.

We can also improve the hashing function, but this only buys us fewer, more predictable collision rates.

Another common fix is a second level to each bucket keeping the exact key, value tuple, and doing a scan on collisions.

That would be like the walrus putting a sticky note that says “Salmon” on the fish before tossing it into the bucket. Then, when you ask for the “Salmon”, he rifles through the bucket, checking each fish until he finds one labeled “Salmon”.

I’ll leave these as an exercise for the reader, because it’s time we got moving on.

Real hashes

Okay, so now you have an example of a simple hash you could use for table lookups. That’s cool and everything, but in general we should leave details like that to the neckbeards. It’s good to know roughly how it works, but we don’t need to do it ourselves.

What else are hashes good for? Well, there is a specie of hash called a cryptographic hash. These hashes are cryptographic primitives, with strong promises of distribution and collision avoidance.

Examples you may have come across are MD5, or the SHA family of algorithms.

Implementation

These algorithms are considerably more complex than the hash function we created earlier, so I would urge you not to write your own except as an exercise.

Implementations are available in a variety of languages, so Google wisely.

Uses

This class of hash has several every day uses that apply to developer-types.

Data Integrity

Since hashes are deterministic functions, the output can be used as a fingerprint for the input. Passing data and the hash of that data allows for others to quickly check and make sure that the data has not become corrupted or tampered with in transit.

This assumes a secure channel for the hash, so use it wisely.

If you are on a Linux machine, you can quickly get the fingerprint for a file. In this example I’ll use the sha1 algorithm to verify the Redis 2.4.2 source code.

jmhobbs@Cordelia:~/Downloads$ sha1sum redis-2.4.2.tar.gz
d2c9288dcfe16b4718e39a0f8ad7b21f4ffc6de0  redis-2.4.2.tar.gz
jmhobbs@Cordelia:~/Downloads$

Comparing that hash to the Redis website, it looks like my download completed without errors. Huzzah!

Secret Verification

Another common use of hashing is to verify secrets, without storing the secret in the clear.

Say I was writing a system login, and I needed to use usernames and passwords.

I know it’s bad to store passwords in plaintext on my server. What if my server gets hacked and the user table is stolen?

I can’t store my passwords in the clear, but I need to reliably verify them.

Hashes make for a great solution to this problem.

You hash the password and store it in your database. Then, when a user wants to login, you hash the password they provide and compare it to the one in the database.

If they match, you log them in.

Doing this properly is a bit more complicated than that, so if you need to work with passwords like this, I recommend you read up.

Data Authenticity

We can also use hashes to confirm the authenticity of a message.

Say we both know a secret phrase, and no one else does.

If you want to send a message to me, and want it to be provably from you, you can send me the message along with a hash of the message concatenated to the secret.

Then, when I get the message, I also take the hash of the message plus the secret and compare it to your provided hash.

If they match, then I know it’s from you.

This is encapsulated in something called a Hashed Message Authentication Code, or HMAC.

File De-duplication

One final case that I regularly use is file de-duplication.

If you host uploads for a website, it’s a nice trick to store upload meta data (user, original name, upload time, etc.) separate from the file itself.

By de-coupling these you can hash files on upload, and if you already have a copy of that content, discard it and point the meta data at the existing file.

Here is an example in pseudo-code:

let hash = sha1_file( uploaded_file.tmp_path )
file = uploads.find_by_hash( hash )
if not file.loaded():
  file.hash = hash
  file.save()
return file.id

Conclusion

Hashes are useful tools for programmers, so learn the concepts and the applications.

I hope you learned something from this post! How do you use hashes?

Related posts:

1. Replacing Kohana 3 Auth module hashing
2. Premature optimization is the root of all evil. But don’t be stupid.
3. Disappointed In SimpleXML

Six months ago I wrote a little PHP framework as an exercise. I’d been down this path before with the now abandoned Xoket – but this time I decided to go small, and throw away.

Hence Skunk was born.

Skunk is a single file, very lightweight API. Really, it’s just a borrowed router with some sugar wrapped around it.

I was after a Sinatra or Bottle feel, and I think I got something rather nice out of it.

Skunk uses anonymous functions extensively, so use PHP 5.3+ to save yourself the pain of create_function.

Example

Here is a super simple Skunk application:

1
2
3
4
5
6
7
8
9
10
11
12
13

// Initialize
$s = new Skunk();
 
// Add a route
$s->get(
  '/hi(/<name>)',
  function ( &$s, $name = null ) {
    $s->body = 'Hello' . ( ( is_null( $name ) ) ? '' : " $name" ) . '!';
  }
);
 
// Run it!
$s->run();

Let’s tear that apart.

2

$s = new Skunk();

Everything in Skunk revolves around the Skunk object, so we need to set one up.

While it is possible to have multiple Skunk objects, there really isn’t a good use case I can think of. But we won’t restrict your cleverness with a singleton.

5

$s->get(

The two most important functions for Skunk are get and post.

These functions take a route and a function to apply when that route is matched, in a GET request and a POST request respectively.

6

  '/hi(/<name>)',

In this chunk we are setting up a GET request, with the route /hi(/<name>), so that will match /hi, /hi/John, etc.

Note the identifier <name> in the route. This named match will be captured and sent as an argument to the function.

7
8
9
10

  function ( &$s, $name = null ) {
    $s->body = 'Hello' . ( ( is_null( $name ) ) ? '' : " $name" ) . '!';
  }
);

Skunk route functions always need to take a reference to the Skunk object as their first argument. Following that are any other arguments that might be pulled from the route itself.

In this case we are just setting the body of the Skunk response.

13

$s->run();

This kicks off the request process and also renders the response.

Other Tricks

Skunk has some other features too.

You can raise a variety of errors inside of a request:

$s->get(
  '/error/500',
  function ( &$s ) {
    return $s->HTTP_500();
  }
);

You can set headers:

$s->get(
  '/example.json',
  function ( &$s ) {
    $s->header( 'Content-Type', 'application/json' );
    $s->body = json_encode( array( "Example" => TRUE ) );
  }
);

There is even a little hook system, so you can do middleware-ish stuff:

$s->hook(
  'send_head',
  function ( &$s ) {
    $s->header( 'X-Stinky-By', 'Skunk' );
  }
);

Summary

So that is Skunk.

It could use some love, but it’s workable. We’ve run Number Laundry on it with no problems for four months with no problems yet.

For an example of Skunk in action, check out Number Laundry’s source at github.

Related posts:

1. Amarok REST API
2. BlowPass V0.60 – A Major Revision
3. A Simple JavaScript Hooks System

“The only thing engineers like about a deadline is it’s precision.”

- Michael Lopp
@rands

Related posts:

1. Thursday Quote: Michael Lopp (Rands)
2. Thursday Quote: Michael Abrash
3. Thursday Quote: Brian Tarbox

Sometimes you have weird requirements to meet. It’s a fact of life.

One of these requirements I came across recently was outputting a result set in alpha order, but with a specific tuple at the end, instead of where it belongs in the sort.

I decided I’d figure out how to do this in SQL instead of gross rendering or a re-sort.

Please note there are other ways to solve this that are less brittle, but this was in a fairly static data set for a one off solution.

Consider this table:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

CREATE TABLE `animals` (
  `id` INT(11) UNSIGNED NOT NULL AUTO_INCREMENT,
  `name` VARCHAR(64)  NOT NULL,
  `slug` VARCHAR(64)  NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_name`(`name`(64)),
  UNIQUE KEY `uniq_slug`(`slug`(64))
)
ENGINE = InnoDB DEFAULT CHARSET=utf8;
 
INSERT INTO `animals` ( `id`, `name`, `slug` ) VALUES
  ( NULL, 'Dog', 'dog' ),
  ( NULL, 'Cat', 'cat' ),
  ( NULL, 'Other', 'other' ),
  ( NULL, 'Zebra', 'zebra' );

Now, pull them out in alpha order:

mysql> SELECT *
    -> FROM `animals`
    -> ORDER BY slug ASC;
+----+-------+-------+
| id | name  | slug  |
+----+-------+-------+
|  2 | Cat   | cat   |
|  1 | Dog   | dog   |
|  3 | Other | other |
|  4 | Zebra | zebra |
+----+-------+-------+
4 rows in set (0.00 sec)

But what if we always want “Other” at the end?

Well, our unique indices allow us to guarantee a conditional sort on the slug (or name).

To do this, we will use the CASE statement.

mysql> SELECT *
    -> FROM `animals`
    -> ORDER BY CASE
    -> WHEN `slug` = 'other'
    -> THEN 0
    -> ELSE 1
    -> END DESC, `slug` ASC;
+----+-------+-------+
| id | name  | slug  |
+----+-------+-------+
|  2 | Cat   | cat   |
|  1 | Dog   | dog   |
|  4 | Zebra | zebra |
|  3 | Other | other |
+----+-------+-------+
4 rows in set (0.00 sec)

Here we have two ORDER BY clauses. We first use CASE to return 1 whenever the slug is “other”, and sort on that. Then we sort the sub-groups (“other” and “non-other”) by slug.

CASE is handy for other stuff too, and can handle complex expressions.

mysql> SELECT *, CASE
    -> WHEN `slug` IN ( 'cat', 'dog' )
    -> THEN 'yes'
    -> ELSE 'no'
    -> END AS 'is_good_pet'
    -> FROM `animals`;
+----+-------+-------+-------------+
| id | name  | slug  | is_good_pet |
+----+-------+-------+-------------+
|  1 | Dog   | dog   | yes         |
|  2 | Cat   | cat   | yes         |
|  3 | Other | other | no          |
|  4 | Zebra | zebra | no          |
+----+-------+-------+-------------+
4 rows in set (0.00 sec)

Do you ever use CASE?

Related posts:

1. Replacing MySQL FULLTEXT With JavaScript
2. MySQL & Ruby on Debian (sidux)
3. Simple PHP Caching

The Internet seems a bit sparse when looking for good demo code for using the Kohana 3 OAuth module with Twitter.

I think the main issue is that the OAuth module isn’t very well documented, and doesn’t do API requests. For that you need an API implementation, like shadowhand/apis.

Anyway, here is a gist I put together with an example controller for Twitter OAuth:

https://gist.github.com/1267793

Related posts:

1. Clean Auth module usage in Kohana
2. SVN to Twitter
3. Charting Weight Change With Google Visualizations

“If you want to be a game programmer, or for that matter any sort of programmer at all, here’s the secret to success in just two words: Ship it. Finish the product and get it out the door, and you’ll be a hero.”

- Michael Abrash
Quake’s 3-D Engine: The Big Picture

Related posts:

1. Thursday Quote: Michael Lopp (Rands)
2. Thursday Quote: Joel Spolsky
3. Thursday Quote: Ed Nather

“..the way humans (especially engineer-humans) perceive beauty is intimately related to our ability to process and understand complexity. A language that makes it hard to write elegant code makes it hard to write good code.”

- Eric S. Raymond
Why Python?

Related posts:

1. Thursday Quote: Eric Hellman
2. Thursday Quote: Jonathan Edwards
3. XML, XSL Are Stinkin Powerfull

“Programmers are most effective when they avoid writing code.”

- John D. Cook
Blog Post

Related posts:

1. Thursday Quote: John von Neumann
2. Thursday Quote: Andrew Wulf
3. Thursday Quote: _why

There really are only two acceptable models of development: “think and analyze” or “years and years of testing on thousands of machines”.

- Linus Torvalds
Mailing List Message

Related posts:

1. Thursday Quote: Gina Trapani
2. Thursday Quote: Abelson & Sussman
3. Thursday Quote: Jeff Foster

Yesterday I had a discussion wherein Regular Expression’s were (sort of) jokingly referred to as “magic”. Well, today I had cause to write a clever(ish) one, and I thought I would lay it out real quick.

What I needed to do was break a string at between 200 and 250 characters, but it had to be on a word boundry. So, it could run over if needed, but it had to break on a word boundary.

Now, I know you could do this with a couple of other functions mixed together, but I’m going to do it with preg_replace. No idea how this compares on performance. Poorly for large strings, I would guess.

I’ll ruin the surprise and show you the answer first:

preg_replace( "/(.{200,}?\b).*/s", '\1', $string );

So let’s break this down.

/(.{200,}?\b).*/s

Starting from the left. ( this signifies that I am opening a subpattern. What comes inside of these parentheses are the content I want to save.

The dot, ., is a wildcard that matches any character.

The string {200,} is a repetition marker, allowing for the previous character (the dot, so, anything, remember) to repeat 200 or more times.

The question mark, ? here is really important. By default repetition is “greedy”, or, it will suck up as many characters as it is allowed, with precedence being given out left to right. By putting the ? here we make {200,} un-greedy, so it only grabs as much as required for the match to work.

The \b is an escape sequence for a word boundary. Handy!

After that we close the subpattern, )

Next we have .* which is a greedy repetition matching any character. Since this is greedy and {200,} is not, it will pick up any of the slack.

The last little bit is the s after the pattern delimiter. This is a modifier that tells the dot character to match anything, including newlines.

Again

So, to recap, we say…

Give me any character, 200 or more times, ungreedily, followed by a line break, and then collect any following characters greedily.

Examples

//  T  h  i  s     i  s     a     t  e  s  t     s  t  r  i  n  g  .
// 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21
$string = "This is a test string.";
echo preg_replace( "/(.{5,}?\b).*/s", '\1', $string );
// This 
echo preg_replace( "/(.{7,}?\b).*/s", '\1', $string );
// This is
echo preg_replace( "/(.{9,}?\b).*/s", '\1', $string );
// This is a
echo preg_replace( "/(.{11,}?\b).*/s", '\1', $string );
// This is a test
echo preg_replace( "/(.{25,}?\b).*/s", '\1', $string );
// This is a test string.
 
// I'm removing that ? here, see what it does to it...
echo preg_replace( "/(.{3,}\b).*/s", '\1', $string );
// This is a test string
// It made {3,} gobble everything up to the last word boundary. Greedy bugger!

Got it?

Related posts:

1. Simple BBCode To HTML Function In PHP
2. Recursive Word Count With Bash
3. Premature optimization is the root of all evil. But don’t be stupid.

The key to making programs fast is to make them do practically nothing.

- Mike Haertel
why GNU grep is fast

Related posts:

1. Thursday Quote: Abelson & Sussman
2. Thursday Quote: Scott Belsky
3. Warped Jane Austen Quote

First make it possible.
Then make it beautiful.
Then make it fast.

- Nathan Marz
Become Efficient or Die

Related posts:

1. Thursday Quote: Brian Tarbox
2. Thursday Quote: _why
3. Thursday Quote: John von Neumann

“you seem to think i’m random, but i’m only psuedorandom. you would be exactly this way, were you seeded at the very same time and place.”

- _why
Twitter

Related posts:

1. Thursday Quote: Jeff Foster
2. Thursday Quote: David Thornburg
3. Thursday Quote: Jeff Atwood

“until programmers stop acting like obfuscation is morally hazardous, they’re not artists, just kids who don’t want their food to touch.”

- _why
Twitter

Related posts:

1. Thursday Quote: Jeff Atwood
2. Thursday Quote: Andrew Wulf
3. Thursday Quote: Ed Nather

“Test-driven development is a coder’s psychological safety net. A bug doesn’t mean the code’s crappy; it’s just missing test coverage.”

- Gina Trapani
@ginatrapani

Related posts:

1. Thursday Quote: Brian Tarbox
2. Thursday Quote: Ed Nather
3. Thursday Quote: C. Scott Andreas

“…never be afraid to completely isolate yourself from the world, and code like an animal.”

- Randall Degges
Programming Innocence

Related posts:

1. Thursday Quote: C. Scott Andreas
2. Thursday Quote: Andrew Wulf
3. Thursday Quote: Reg Braithwaite

So, today Amazon debuted Simple Email Service. The gist of it is, send mail with them instead of your own servers. Like a feature reduced SendGrid or Postmark.

Not a lot of stuff out there for it so I thought I’d jump the gun a bit and write a transport for PHP’s Swiftmailer. If you have to send e-mail from your sever and from PHP, Swiftmailer is your best friend.

Never dug into Swiftmailer’s guts before, but it’s pretty well laid out. All you have to do for a new transport is implement the send method of the Transport interface and you are done.

I knocked mine together pretty quick, and the only code I cribbed was the HMAC code from php-aws, because AWS was rejecting the output from hash_hmac. (Which I literally just figured out while I wrote that paragraph. Works now.)

So how hard is it to use? Easy as any other transport in Swiftmailer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<?php
  require_once 'lib/swift_required.php';
 
  //Create the Transport
  $transport = new Swift_AWSTransport(
    'AWS_ACCESS_KEY',
    'AWS_SECRET_KEY'
  );
 
  //Create the Mailer using your created Transport
  $mailer = Swift_Mailer::newInstance($transport);
 
  //Create the message
  $message = Swift_Message::newInstance()
  ->setSubject("What up?")
  ->setFrom(array('you@yourdomain.com'))
  ->setTo(array('them@theirdomain.com'))
  ->setBody("
<p>
  Dude, I'm <b>totally</b> sending you email via AWS.
</p>
  ", 'text/html');
 
  $mailer->send( $message );

So, yeah, it works.

I know there is a ton of stuff I didn’t implement that I need to before this could be “production” ready, but it was a very satisfying little project.

You can grab it here: https://github.com/jmhobbs/Swiftmailer-Transport–AWS-SES

Related posts:

1. Simple PHP Caching
2. A Simple JavaScript Hooks System
3. Simple BBCode To HTML Function In PHP

So, work has me writing Java for the first time in my life. I needed to handle some data in JSON format, and was using Jackson and it’s ObjectMapper for a while. Fast and a relatively nice interface.

Today I switched to Gson for the even simpler API. It’s slower, but I’m just munging little strings every once in a while, so that’s not a problem.

The one thing I came across today that didn’t go as expected was serialization with inheritance in my objects. Here’s where I started:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

package org.velvetcache.java.toys;
 
import com.google.gson.Gson;
 
public class GsonToy {
 
  public static void main(String[] args) {
    Gson gson = new Gson();
 
    Core core = new Core();
    System.out.println( gson.toJson( core ) );
 
    Inherits inherits = new Inherits();
    System.out.println( gson.toJson( inherits ) );
  }
 
  public static class Core {
    public int inheritanceDepth = 1;
    public String className = "Core";
  }
 
  public static class Inherits extends Core {
    public int inheritanceDepth = 2;
    public String className = "Inherits";
  }
 
}

I expected to see the JSON representing of each. Much to my surprise, I got this instead:

{"inheritanceDepth":1,"className":"Core"}
{"inheritanceDepth":1,"className":"Core"}

What the what? Weird. So I thought I’d try adding a constructor and setting it there.

22
23
24
25
26
27
28
29
30

  public static class Inherits extends Core {
    public int inheritanceDepth = 2;
    public String className = "Inherits";
 
    public Inherits () {
      inheritanceDepth = 2;
      className = "Inherits";
    }
  }

Again, no luck! I got the same output as before. I gave it one last shot.

22
23
24
25
26
27

  public static class Inherits extends Core {    
    public Inherits () {
      inheritanceDepth = 2;
      className = "Inherits";
    }
  }

That time I got it.

{"inheritanceDepth":1,"className":"Core"}
{"inheritanceDepth":2,"className":"Inherits"}

Strange. So it seems that when serializing an object, Gson looks for the value of a field in the superclass. However, when you are in the object you are accessing the local field. It seems like a weird scope thing. Interestingly, if you provide a new implementation at the subclass level it will use that one instead.

This seems to be noted in the user guide at “Finer Points with Objects“. I must have just missed it.

Fields corresponding to the outer classes in inner classes, anonymous classes, and local classes are ignored and not included in serialization or deserialization

Easy enough, though a little annoying.

Related posts:

1. Better libcurl from C++
2. Disappointed In SimpleXML
3. JavaScript Class Definitions

“Programs must be written for people to read, and only incidentally for machines to execute.”

- Abelson & Sussman
Structure and Interpretation of Computer Programs

Related posts:

1. Thursday Quote: Harold Ableson
2. Thursday Quote: Remy Porter
3. Thursday Quote: Reg Braithwaite

“If you don’t hate any software (libraries, code) – really hate, deep deep down – then I don’t think I trust your judgment.”

- Peter Aronoff
Tweet On Haml

Related posts:

1. Thursday Quote: Jonathan Edwards
2. Thursday Quote: Brian Tarbox
3. Thursday Quote: David Heinemeier Hansson

“Shipping is a feature. A really important feature. Your product must have it.”

- Joel Spolsky
The Duct Tape Programmer

Related posts:

1. Thursday Quote: Ed Nather
2. Thursday Quote: David Greiner
3. Thursday Quote: Remy Porter

So I’m working on a little admin interface and I decided to tail some logs. It’s in PHP and Google came up with some stuff, but they were all a bit finickey and not well documented. So I wrote my own!

Here’s the basic concept:

1. Open File
2. Seek To End
3. Loop:
   1. Seek Back By Chunk Size
   2. Read Chunk
   3. Count Newlines
   4. Stash In Buffer
   5. Break If Enough Newlines Total
4. Trim Extra Line & Cruft
5. Done!

Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

function tail ( $file, $lines, $max_chunk_size = 4096 ) {
 
  // We actually want to look for +1 newline so we can get the whole first line
  $rows = $lines + 1;
 
  // Open up the file
  $fh = fopen( $file, 'r' );
 
  // Go to the end
  fseek( $fh, 0, SEEK_END );
  $position = ftell( $fh );
 
  $buffer = '';
  $found_newlines = 0;
 
  $break = false;
  while( ! $break ) {
    // If we are at the start then we are done.
    if( $position <= 0 ) { break; }
 
    // We can't seek past the 0 position obviously, so figure out a good chunk size
    $chunk_size = ( $max_chunk_size > $position ) ? $position : $max_chunk_size;
 
    // Okay, now seek there and read the chunk
    $position -= $chunk_size;
    fseek( $fh, $position );
    $chunk = fread( $fh, $chunk_size );
 
    // See if there are any newlines in this chunk, count them if there are
    if( false != strpos( $chunk, "\n" ) ) {
      if( substr( $chunk, -1 ) == "\n" ) { ++$found_newlines; }
      $found_newlines += count( explode( "\n", $chunk ) );
    }
 
    // Have we exceeded our desired rows?
    if( $found_newlines > $rows ) { $break = true; }
 
    // Prepend
    $buffer = $chunk . $buffer;
  }
 
  // Now extract only the lines we requested
  $buffer = explode( "\n", $buffer );
  return implode( "\n", array_slice( $buffer, count( $buffer ) - $lines ) );
}

You can give it a try on some junk data here: http://static.velvetcache.org/pages/2010/12/03/tail-in-php/

Related posts:

1. PHP/Cron Based IP Tracker
2. Simple PHP Caching
3. Making DCOP work with Apache and PHP

“If you are afraid of your program, you have to break it until you are not afraid of it anymore.”

- C. Scott Andreas
You Have to Break It

Related posts:

1. Thursday Quote: Scott Belsky
2. Thursday Quote: Ed Nather
3. Thursday Quote: Jeff Atwood

“…sharks have to keep swimming or they die and software engineers have to keep growing or they become expendable.”

- Brian Tarbox
The Value of a Personal Bug Log

Related posts:

1. Thursday Quote: Brian Malow
2. Thursday Quote: Jonathan Edwards
3. Thursday Quote: David Heinemeier Hansson

This week Jerod Santo released a nifty little app he had written for the Mac called Detours. It’s pretty cool, it’s a nice GUI where you can add routing information. So, you can make the DNS resolver think google.com is located at 127.0.0.1. Stuff like that.

I use Linux though, and I wanted some of that goodness. Unfortunately, Jerod told me that Detours uses some OS X specific API calls. So, cool for Mac folks but lame for me.

That evening I set off to write a portable version of Detours by using the hosts file (/etc/hosts) on Linux. Naturally since I’m groking a text format it’s uglier, and it requires a daemon/client set up since the hosts file is write-locked for normal users.

But, I got one working that night and I’ve built it out since then. So I present to the Linux users of the world, Detours Clone. Lame name I know, if you have a suggestion for a better one let me know.

Anyway, I have a nice Python daemon and three Python clients (Qt4, GTK+ and a web server!). They speak JSON over TCP sockets (bound to 127.0.0.1 of course) and work well so far. I even wrote a few tests and a distutils installer.

So go check it out!

The Qt4 Client

Related posts:

1. Learning Ruby: Unpacking Arrays
2. Trying out pygame, pretty cool.
3. WLAN Router Monitor BASH Script

So, about a week or go I dove back into Ruby out of necessity. The Twitter daemon I had written in Python for Confurrent was chronically ill. My socket would block and eat 100% CPU and it seemed like nobody knew how to work around it, least of all me.

So I pulled out Ruby. I’ve only ever done any real Ruby work with Rails, when I wrote ThirtyDayList to learn the tech.

One thing I will note is that learning Rails basics does not teach you Ruby, or at least not enough Ruby to be useful. However, writing my Twitter daemon has made me confident in Ruby, and I like it a lot more now than after the Rails experiment.

The daemon was quick to write, using Tweetstream, and I only ran into one roadblock, which was all my fault.

See, I wanted to use the track method, which takes an unlimited and variable set of arguments (like *args in Python) but I had my arguments in an array. I could not figure out how to pass those on correctly, and even bust into the gem and started adding code to get it to work.

I finally realized that there is no way that there isn’t a built-in for this and I went back to Googling. A short while later I found a short post from detailing exactly what I should be doing.

Evidently you can use the asterisk to unpack an array for this. Super easy, but I feel silly for not finding that sooner. The pitfalls of unfocused autodidactism.

The Wrong Way

1
2
3

predicates = [ 'a', 'b', 'c' ]
@client.track( predicates )
# Tracks 'abc'

The Right Way

1
2
3

predicates = [ 'a', 'b', 'c' ]
@client.track( *predicates )
# Tracks 'a,b,c'

Related posts:

1. MySQL & Ruby on Debian (sidux)
2. ThirtyDayList.com
3. Streaming Tweets With Tweepy

1. Thursday Quote: Ed Nather
2. Thursday Quote: Jeff Atwood
3. Thursday Quote: Harold Ableson

Last weekend I had the fun opportunity of building my first Twillio app with a group at the Omaha Startup Weekend. We wrote a phone based version of chattroulette called Call Spinner which includes a cool advertising system we hope to expand on.

Developing for Twilio isn’t that hard, it’s mostly just about generating the right XML. We used the PHP library Twilio provides and it’s pretty nice, but debugging off of the Twilio website was a waste of money and not much fun.

So, over the last few days I worked out a nice debugging tool I decided to call Twillip. What it does is conditionally wrap your code and prints it in a clean fashion, with links and variables and other goodies like that.

Super simple to use too! Here, this is a contrived example. Normally you probably want some sort of cool dispatcher (I have one of those if you want it) and to check that requests are signed, etc.

example.php

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

<?php
  define( 'IS_DEV', true );
 
  require_once( 'twilio.php' );
 
  if( IS_DEV ) {
    require_once( 'twillip.php' );
    Twillip::Start();
  }
 
  $r = new Response();
  if( isset( $_REQUEST['Caller'] ) ) {
    $r->addSay( 'This app uses Twillip for obviously awesome reasons!' );
    $r->addPlay( 'funky-beats.mp3', array( 'loop' => 3 ) );
    $r->addRedirect( '/doesntexist.php' );
  }
  else {
    $r->addSay( 'Oh no! I didn\'t get sent a phone number! Who in blue blazes are you?' );
    $r->addSay( 'This line will generate a PHP warning now: ' . $_REQUEST['Caller'] );
  }
  $r->respond();
 
  if( IS_DEV ) { Twillip::End(); }

Sweet, so what does that buy us? Only this awesome interface is all!

But there is an error! $_REQUEST['Caller'] isn’t set. We can fix that by clicking on the Add New Input and filling it in.

There it is! Now we can click Reload Page and it will refresh with all of the inputs.

You can’t tell in the image, but the Redirect and Play verbs are both clickable links, and will bring all of the variables in the input section with them.

Seeing is believing, so try it out at http://static.velvetcache.org/pages/2010/09/16/developing-for-twilio-in-php-introducing-twillip/demo/

You can grab the source at http://github.com/jmhobbs/Twillip.

Related posts:

1. Debugging, BASE, Opera and XHR
2. PHP Virtual Machine, Version 0.01
3. Making DCOP work with Apache and PHP

“…like any enterprise application, it was built to be all things for all people, by people that didn’t have a clear picture of which things it was supposed to be to whom.”

- Remy Porter
Secured Typing

Related posts:

1. Class Photoshop Project
2. Thursday Quote: Jonathan Edwards
3. Thursday Quote: David Heinemeier Hansson