TP2 Operational transform code for text, in C

text-tp2.h

//
//  text-tp2.h

#import <Foundation/Foundation.h>

//typedef struct {
//	NSString *str;
//	int num_tombs;
//	int tombs[];
//} Doc;

typedef enum {
	NONE = 0,
	SKIP = 1,
	INSERT_TOMBSTONES = 2,
	INSERT_CHARACTERS = 3,
	DELETE = 4
} ComponentType;

typedef struct {
	ComponentType type;
	union {
		NSUInteger num;
		NSString *str;
	};
} OpComponent;

typedef struct {
	int num_components;
	int capacity;
	OpComponent components[];
} Op;

typedef Op Doc;


Op *tp2_text_create_op();
void tp2_text_free_op(Op *op);
Op *tp2_text_op_from_components(int num, OpComponent components[]);
void tp2_text_print_op(Op *op);
Op *tp2_text_doc_from_JSON(NSArray *arr);
Op *tp2_text_op_from_JSON(NSArray *arr);
BOOL tp2_text_compare(Op *op1, Op *op2);

Op *tp2_text_apply(Doc *doc, Op *op);
Op *tp2_text_normalize(Op *op);
Op *tp2_text_transform(Op *op, Op *otherOp, BOOL isLefthand);
Op *tp2_text_prune(Op *op, Op *otherOp);
Op *tp2_text_compose(Op *op1, Op *op2);

text-tp2.m

//
//  text-tp2.m
//  TP2 text operational transform code for C
//  This is a C rewrite of this:
//  https://github.com/josephg/TP2/blob/master/src/text.coffee

#import <stdio.h>

#import "text-tp2.h"

// **** UTILITY CODE
static Op *increase_op_capacity_to(Op *op, int min_size) {
	if (op->capacity < min_size) {
		do {
			op->capacity = op->capacity ? (op->capacity << 1) : 8;
		} while (op->capacity < min_size);
		
		op = realloc(op, sizeof(Op) + op->capacity * sizeof(OpComponent));
	}
	return op;
}

static Op *increase_op_capacity(Op *op) {
	return increase_op_capacity_to(op, op->capacity + 1);
}

Op *tp2_text_create_op() {
	Op *op = malloc(sizeof(Op));
	*op = (Op){};
	return op;
}

static void component_free(OpComponent c) {
	if (c.type == INSERT_CHARACTERS) {
		[c.str release];
	}
}

void tp2_text_free_op(Op *op) {
	for (int i = 0; i < op->num_components; i++) {
		component_free(op->components[i]);
	}
	
	op->num_components = 0;
	free(op);
}

static void print_op_component(OpComponent component) {
	switch (component.type) {
		case SKIP:
			printf("Skip         : %lu", component.num);
			break;
		case INSERT_TOMBSTONES:
			printf("Insert tombs : %lu", component.num);
			break;
		case INSERT_CHARACTERS:
			printf("Insert chars : %lu ('%s')",
				   [component.str length], [component.str cStringUsingEncoding:NSUTF8StringEncoding]);
			break;
		case DELETE:
			printf("Delete       : %lu", component.num);
			break;
		default:
			break;
	}
	printf("\n");
	fflush(stdout);
}

void tp2_text_print_op(Op *op) {
	for (int i = 0; i < op->num_components; i++) {
		printf("%d.\t", i);
		print_op_component(op->components[i]);
	}
	printf("\n");
}


Op *tp2_text_doc_from_JSON(NSArray *arr) {
	OpComponent components[[arr count]];
	
	for (int i = 0; i < [arr count]; i++) {
		NSObject *obj = [arr objectAtIndex:i];
		if ([obj isKindOfClass:[NSString class]]) {
			components[i] = (OpComponent){INSERT_CHARACTERS, .str=(NSString *)obj};
		} else {
			int num = [(NSNumber *)obj intValue];
			components[i] = (OpComponent){INSERT_TOMBSTONES, .num=num};
		}
	}
	
	return tp2_text_op_from_components((int)[arr count], components);
}

Op *tp2_text_op_from_JSON(NSArray *arr) {
	OpComponent components[[arr count]];
	
	for (int i = 0; i < [arr count]; i++) {
		NSObject *obj = [arr objectAtIndex:i];
		if ([obj isKindOfClass:[NSNumber class]]) {
			components[i] = (OpComponent){SKIP, .num=[(NSNumber *)obj intValue]};
		} else {
			NSDictionary *dict = (NSDictionary *)obj;
			NSNumber *d = [dict objectForKey:@"d"];
			NSObject *ins = [dict objectForKey:@"i"];
			if (d != nil) {
				components[i] = (OpComponent){DELETE, .num=[d intValue]};
			} else {
				if ([ins isKindOfClass:[NSNumber class]]) {
					components[i] = (OpComponent){INSERT_TOMBSTONES, .num=[(NSNumber *)ins intValue]};					
				} else {
					components[i] = (OpComponent){INSERT_CHARACTERS, .str=(NSString *)ins};
				}
			}
		}
	}
	
	return tp2_text_op_from_components((int)[arr count], components);
}

BOOL tp2_text_compare(Op *op1, Op *op2) {
	if (op1->num_components != op2->num_components) {
		return NO;
	} else {
		for (int i = 0; i < op1->num_components; i++) {
			OpComponent c1 = op1->components[i];
			OpComponent c2 = op2->components[i];
			if (c1.type != c2.type) {
				return NO;
			}
			
			if (c1.type == INSERT_CHARACTERS) {
				if (![c1.str isEqualToString:c2.str]) {
					return NO;
				}
			} else {
				if (c1.num != c2.num) {
					return NO;
				}
			}
		}
		
		return YES;
	}
}

static Op *append_raw(Op *op, OpComponent c) {
	if (c.type == INSERT_CHARACTERS) {
		[c.str retain];
	}
	if (op->capacity == op->num_components) {
		op = increase_op_capacity(op);
	}
	op->components[op->num_components++] = c;
	
	return op;
}

static NSUInteger componentLength(OpComponent c) {
	return c.type == INSERT_CHARACTERS ? [c.str length] : c.num;
}

// Append an op component to the end of the specified op.
static Op *append(Op *op, OpComponent c) {
	//p "append #{i op} + #{i component}"
	if (componentLength(c) == 0) {
		return op;
	} else if (op->num_components == 0) {
		return append_raw(op, c);
	} else {
		OpComponent last = op->components[op->num_components - 1];
		if (c.type == last.type) {
			if (c.type == INSERT_CHARACTERS) {
				[op->components[op->num_components - 1].str autorelease];
				
				op->components[op->num_components - 1].str =
				[[op->components[op->num_components - 1].str stringByAppendingString:c.str] retain];
			} else {
				op->components[op->num_components - 1].num += c.num;
			}
			return op;
		} else {
			return append_raw(op, c);
		}
	}
	//p "-> #{i op}"
	//checkOp op
}

Op *tp2_text_op_from_components(int num, OpComponent components[]) {
	Op *op = tp2_text_create_op();
	for (int i = 0; i < num; i++) {
		op = append(op, components[i]);
	}
	return op;
}

// Returns a string with the error text, or null if the op is fine.
static void checkOp(Op *op) {
	int lastType = -1;
	
	for (int i = 0; i < op->num_components; i++) {
		OpComponent c = op->components[i];
		
		if (c.type == lastType) {
			[NSException raise:@"Invalid op" format:@"An op component is the same type as the previous op component"];
		}
		
		switch(c.type) {
			case SKIP:
			case INSERT_TOMBSTONES:
			case DELETE:
				if (c.num <= 0) {
					[NSException raise:@"Invalid op" format:@"Op component must have a positive length"];
				}
				break;
			case INSERT_CHARACTERS:
				if ([c.str length] == 0) {
					[NSException raise:@"Invalid op" format:@"Inserts must have a positive length"];
				}
				break;
			default:
				[NSException raise:@"Invalid op" format:@"Unrecognised op component type %d", c.type];
		}
		
		lastType = c.type;
	}
}

typedef struct {
	NSUInteger index;
	NSUInteger offset;
} OpPosition;

// Take the next part (up to length maxlength) from the op. If maxlength is <0, there is no max.
// If insertsIndivisible is true, inserts (& insert tombstones) won't be separated.
//
// Returns a {type:NONE} component when the op is fully consumed.
static OpComponent take(Op *op, OpPosition *position, NSInteger maxlength, BOOL insertsIndivisable) {
//	p "take #{maxlength} index: #{index} off: #{offset}"
	if (position->index == op->num_components) {
		return (OpComponent){};
	}

	OpComponent e = op->components[position->index];
	NSUInteger length = componentLength(e);
	
	if (maxlength < 0
			|| (insertsIndivisable && (e.type == INSERT_CHARACTERS || e.type == INSERT_TOMBSTONES))) {
		maxlength = length - position->offset;
	} else {
		maxlength = MIN(maxlength, length - position->offset);
	}
	
	if (e.type == INSERT_CHARACTERS) {
		e.str = [[e.str substringWithRange:NSMakeRange(position->offset, maxlength)] retain];
	} else {
		e.num = maxlength;
	}
	
	position->offset += maxlength;
	if (position->offset >= length) {
		position->offset = 0;
		position->index++;
	}

	return e;
}

// Apply the op to the document. The document is not modified in the process.
Op *tp2_text_apply(Doc *doc, Op *op) {
//	p "Applying #{i op} to #{i doc}"
	checkOp(op);

	Doc *newDoc = tp2_text_create_op();
	OpPosition position = (OpPosition){};

	for (int i = 0; i < op->num_components; i++) {
		OpComponent c = op->components[i];
		switch (c.type) {
			case SKIP: {
				NSUInteger len = c.num;
				while (len > 0) {
					OpComponent part = take(doc, &position, len, false);
					newDoc = append(newDoc, part);
					len -= componentLength(part);
				}
				break;
			}
			case INSERT_TOMBSTONES:
			case INSERT_CHARACTERS:
				newDoc = append(newDoc, c);
				break;
			case DELETE: {
				NSUInteger len = c.num;
				while (len > 0) {
					OpComponent part = take(doc, &position, len, false);
					//component_free(part);
					len -= componentLength(part);
				}
				newDoc = append(newDoc, (OpComponent){INSERT_TOMBSTONES, .num=c.num});
				break;
			}
			default:
				// Should never get here - checkOp(op) above will make sure the components are sweet.
				break;
		}
	}

	return newDoc;
}

// Normalize an op, removing all empty skips and empty inserts / deletes. Concatenate
// adjacent inserts and deletes.
Op *tp2_text_normalize(Op *op) {
	Op *newOp = tp2_text_create_op();

	for (int i = 0; i < op->num_components; i++) {
		OpComponent c = op->components[i];
		newOp = append(newOp, c);
	}

	return newOp;
}

#define IS_INSERT(t) ((t) == INSERT_TOMBSTONES || (t) == INSERT_CHARACTERS)

// This is a helper method to transform and prune. goForwards is true for transform, false for prune.
static Op *transformer(Op *op, Op *otherOp, BOOL goForwards, BOOL isLefthand) {
//	p "TRANSFORMER op #{i op} by #{i otherOp} (delta: #{idDelta}) forwards: #{goForwards}"

	checkOp(op);
	checkOp(otherOp);
	
	Op *newOp = tp2_text_create_op();
	OpPosition position = (OpPosition){};
	
	for (int i = 0; i < otherOp->num_components; i++) {
		OpComponent c = otherOp->components[i];
		NSUInteger length = componentLength(c);
		
		if (IS_INSERT(c.type)) {
			// Inserting.
			if (goForwards) {
				// Transforming
				if (isLefthand == YES) {
					while (position.index < op->num_components
						   && IS_INSERT(op->components[position.index].type)) {
						newOp = append(newOp, take(op, &position, -1, NO));
					}
				}
				
				newOp = append(newOp, (OpComponent){SKIP, .num=length});
			} else {
				// Pruning.
				while (length > 0) {
					OpComponent chunk = take(op, &position, length, YES);
					
					if (chunk.type == NONE) {
						[NSException raise:@"Op wrong length" format:@"The transformed op is too short"];
					} else if (chunk.type == DELETE) {
						[NSException raise:@"Op invalid" format:@"Transformed op deletes locally inserted characters - it cannot be purged of the insert."];
					}
					
					if (chunk.type == SKIP) {
						length -= chunk.num;
					} else {
						newOp = append(newOp, chunk);
					}
				}
			}
		} else {
			// Skip or a delete.
			while (length > 0) {
				OpComponent chunk = take(op, &position, length, YES);
				if (chunk.type == NONE) {
					[NSException raise:@"Op wrong length" format:@"The op is too short"];
				}
				
				newOp = append(newOp, chunk);
				if (!IS_INSERT(chunk.type)) {
					length -= componentLength(chunk);
				}
			}
		}
	}

	while (position.index < op->num_components) {
		OpComponent chunk = take(op, &position, -1, NO);
		if (!IS_INSERT(chunk.type)) {
			[NSException raise:@"Op wrong length" format:@"The op has extra fragments at the end"];
		}
		newOp = append(newOp, chunk);
	}
	
	return newOp;
}


// transform op1 by op2. Return transformed version of op1.
// op1 and op2 are unchanged by transform.
// left handedness = usually client, right = server.
Op *tp2_text_transform(Op *op, Op *otherOp, BOOL isLefthand) {
	return transformer(op, otherOp, YES, isLefthand);
}

// Prune is the inverse of transform.
Op *tp2_text_prune(Op *op, Op *otherOp) {
	return transformer(op, otherOp, NO, YES /* handedness is irrelevant for prune */);
}

// Compose 2 ops into 1 op.
Op *tp2_text_compose(Op *op1, Op *op2) {
	//p "COMPOSE #{i op1} + #{i op2}"
	checkOp(op1);
	checkOp(op2);

	Op *result = tp2_text_create_op();
	OpPosition position = (OpPosition){};
	
	for (int i = 0; i < op2->num_components; i++) {
		OpComponent c = op2->components[i];
//		p "component in op2 #{i component}"

		switch (c.type) {
			case SKIP: {
				// Just copy from op1.
				NSUInteger length = c.num;
				while (length > 0) {
					OpComponent chunk = take(op1, &position, length, NO);
					
					if (chunk.type == NONE) {
						[NSException raise:@"Op wrong length" format:@"The op is too short"];
					}
					
					result = append(result, chunk);
					length -= componentLength(chunk);
				}
				break;
			}
			case INSERT_CHARACTERS:
			case INSERT_TOMBSTONES:
				result = append(result, c);
				break;
			case DELETE: {
				NSUInteger length = c.num;
				while (length > 0) {
					OpComponent chunk = take(op1, &position, length, NO);
					
					if (chunk.type == NONE) {
						[NSException raise:@"Op wrong length" format:@"The op is too short"];
					}
					
					NSUInteger clength = componentLength(chunk);
					if (IS_INSERT(chunk.type)) {
						result = append(result, (OpComponent){INSERT_TOMBSTONES, .num=clength});
					} else {
						result = append(result, (OpComponent){DELETE, .num=clength});
					}
					
					length -= clength;
				}
				break;				
			}
			default:
				break;
		}
	}
	
	while (position.index < op1->num_components) {
		OpComponent chunk = take(op1, &position, -1, NO);
		if (!IS_INSERT(chunk.type)) {
			[NSException raise:@"Op wrong length" format:@"The op has extra fragments at the end"];
		}
		result = append(result, chunk);
	}
	
//	p "= #{i result}"
	return result;
}