Source

Murky / Source / RevisionGraphColumn.m

//
//  RevisionGraphColumn.m
//  Murky
//
//  Copyright 2008-2009 Jens Alfke. All rights reserved.
//

#import "RevisionGraphColumn.h"
#import "HgRevision.h"
#include <tgmath.h>


enum {
    kEmpty = 0,
    kDotMask = 1,
    kPrevMask = 2,
    kNextMask = 4
};


@interface RevisionGraphColumn ()
- (BOOL) _layOutRev: (HgRevision*)rev;
@end


@implementation RevisionGraphColumn

- (BOOL) _addLineFrom: (NSUInteger)rev0 to: (NSUInteger)rev1
{
    Assert(rev0>=0&&rev0<_nRevisions,@"bad rev0: %i",rev0);
    Assert(rev1>rev0&&rev1<_nRevisions,@"bad rev1: %i",rev1);
    
    UInt64 used = 0;
    for( NSUInteger r=rev0+1; r<rev1; r++ )
        used |= _used[r];
    
    NSInteger x;
    UInt64 mask;
    for( x=0,mask=1; x<_maxWidth; x++, mask <<= 1 ) {
        if( !(used & mask) && !(_array[rev1*_maxWidth + x] & kPrevMask) 
                           && !(_array[rev0*_maxWidth + x] & kNextMask) )
            break;
    }
    if( x>=_maxWidth ) {
        if( _maxWidth < 64 )
            return NO;
        else
            x = 63; // give up and use the max possible x
    }
    
    _array[rev0*_maxWidth + x] |= kDotMask | kNextMask;
    _used[rev0] |= mask; 
    for( NSUInteger r=rev0+1; r<rev1; r++ ) {
        _array[r*_maxWidth + x] |= kPrevMask | kNextMask;
        _used[r] |= mask; 
    }
    _array[rev1*_maxWidth + x] |= kPrevMask | kDotMask;
    _used[rev1] |= mask; 
    
    //Log(@"Line from %i to %i at x=%i",rev0,rev1,x);
    return YES;
}


- (BOOL) _layOutFromChild: (HgRevision*)child toParent: (HgRevision*)parent
{
    NSInteger rev0 = [_revisions indexOfObjectIdenticalTo: parent];
    NSInteger rev1 = [_revisions indexOfObjectIdenticalTo: child];
    if( rev0==NSNotFound || rev1==NSNotFound )
        return YES;
    return [self _addLineFrom: rev0 to: rev1];
}

- (BOOL) _layOutRev: (HgRevision*)rev
{
    while(rev){
        if( [_laidOut containsObject: rev] )
            return YES;
        //Log(@"Layout %@",rev);
        [_laidOut addObject: rev];
        HgRevision *parent = rev.parent;
        if( parent ) {
            if( ! [self _layOutFromChild: rev toParent: parent] )
                return NO;
            if( rev.parent2 )
                [_parent2Queue addObject: rev];
        }
        rev = parent;
    }
    return YES;
}


- (BOOL) _layOut
{
    size_t size = _maxWidth*_nRevisions*sizeof(NSInteger);
    _array = NSAllocateCollectable(size,0);
    memset(_array, 0, size);
    memset(_used, 0, _nRevisions*sizeof(_used[0]));
    _laidOut = [NSMutableSet set];
    _parent2Queue = [NSMutableArray array];
    //Log(@"layOut: width=%i, nRevisions=%i, size=%u",_maxWidth,_nRevisions,size);
    
    for( NSInteger i=_nRevisions-1; i>=0; i-- )
        if( ! [self _layOutRev: [_revisions objectAtIndex: i]] )
            return NO;
    for( NSUInteger i=0; i<_parent2Queue.count; i++ ) {
        HgRevision *rev = [_parent2Queue objectAtIndex: i];
        HgRevision *p2  = rev.parent2;
        if( ! [self _layOutFromChild: rev toParent: p2] )
            return NO;
        if( ! [self _layOutRev: p2] )
            return NO;
    }
    return YES;
}


- (id) initWithRevisions: (NSArray*)revisions;
{
    self = [super init];
    if (self != nil) {
        _revisions = revisions;
        _nRevisions = revisions.count;
        _used = NSAllocateCollectable( _nRevisions*sizeof(_used[0]), 0);
        
        //Log(@"RevisionGraphColumn: %i revisions...",_nRevisions);
        _maxWidth = 4;
        while( ! [self _layOut] )
            _maxWidth *= 2;
    }
    return self;
}

@synthesize revisions=_revisions;


static void drawCorner( CGFloat x0, CGFloat y0, CGFloat x1, CGFloat y1 )
{
    NSBezierPath *path = [NSBezierPath bezierPath];
    [path moveToPoint: NSMakePoint(x0,y0+0.5f)];
    [path curveToPoint: NSMakePoint(x1+0.5f,y1)
         controlPoint1: NSMakePoint(x1-0.2f*(x1-x0),y0+0.5f)
         controlPoint2: NSMakePoint(x1+0.5f,y1-0.2f*(y1-y0))];
    [path stroke];
}


- (void) drawRevisionNumber: (NSUInteger)revNo inRect: (NSRect)bounds flipped: (BOOL)flipped
{
    if( revNo >= _nRevisions )
        return;
    Assert(revNo>=0, @"Illegal revision number %i",revNo);
    
    [[NSColor blackColor] set];
    
    NSInteger topMask,bottomMask;
    if( flipped ) {
        topMask = kPrevMask;
        bottomMask = kNextMask;
    } else {
        topMask = kNextMask;
        bottomMask = kPrevMask;
    }
    
    const UInt8* const items = &_array[revNo*_maxWidth];
    NSRect r = bounds;
    r.size.width = r.size.height;
    
    BOOL clipped = NO;
    NSPoint dot = {-1,floor(NSMidY(r))};
    for( NSInteger i=0; i<_maxWidth; i++ ) {
        NSInteger n = items[i];
        if( n ) {
            r.origin.x = bounds.origin.x + i*r.size.width;
            if( ! clipped && NSMaxX(r) >= NSMaxX(bounds) ) {
                clipped = YES;
                [[NSGraphicsContext currentContext] saveGraphicsState];
                NSRectClip(bounds);
            }
            CGFloat x = floor(NSMidX(r));
            if( n & kDotMask ) {
                if( dot.x<0 ) {
                    // Dot:
                    dot.x = x;
                    if( n & topMask )
                        NSRectFill( NSMakeRect(dot.x,NSMinY(r), 1,dot.y-2-NSMinY(r)) );
                    if( n & bottomMask )
                        NSRectFill( NSMakeRect(dot.x,dot.y+2, 1,NSMaxY(r)-dot.y-2) );
                    NSBezierPath *dotPath = [NSBezierPath bezierPathWithOvalInRect: NSMakeRect(dot.x-2,dot.y-2,5,5)];
                    if( [[_revisions objectAtIndex: revNo] isUncommitted] )
                        [dotPath stroke];
                    else
                        [dotPath fill];
                } else {
                    // Corner to existing dot:
                    NSRectFill( NSMakeRect(dot.x+2,dot.y, NSMinX(r)-dot.x,1) );
                    if( n & topMask )
                        drawCorner(NSMinX(r),dot.y, x,NSMinY(r));
                    if( n & bottomMask )
                        drawCorner(NSMinX(r),dot.y, x,NSMaxY(r));
                }
            } else {
                // Just passing through:
                NSRectFill( NSMakeRect(x,NSMinY(r), 1,r.size.height) );
            }
        }
    }
    if( clipped )
        [[NSGraphicsContext currentContext] restoreGraphicsState];
}

- (void) drawRevision: (HgRevision*)rev inRect: (NSRect)bounds flipped: (BOOL)flipped
{
    NSInteger revNo = [_revisions indexOfObjectIdenticalTo: rev];
    if( revNo != NSNotFound )
        [self drawRevisionNumber: revNo inRect: bounds flipped: flipped];
}


- (void) dump
{
    #define kAsciiGraphic  " o.v.^|+"
    #define kAsciiGraphic2 " o.\\./|+"
    for( NSInteger r=_nRevisions-1; r>=0; r-- ) {
        printf("%2d: ", (int)r);
        BOOL first = YES;
        for( NSInteger x=0; x<_maxWidth; x++ ) {
            NSInteger n = _array[r*_maxWidth + x];
            Assert(n>=0 && n<8,@"Illegal n=%i",n);
            if( first ) {
                putchar(kAsciiGraphic[n]);
                if( n & kDotMask )
                    first = NO;
            } else {
                putchar(kAsciiGraphic2[n]);
            }                    
        }
        putchar('\n');
    }
}    


@end




@implementation RevisionGraphCell

- (void) setRevisions: (NSArray*)revisions
{
    // Don't check revisions for equality with _revisions. The arrays could be the same,
    // but the connectivity of the HgRevision objects in them might be different, i.e.
    // after a merge that alters the parents of the uncommitted revision.
    _graph = [[RevisionGraphColumn alloc] initWithRevisions: revisions];
    _revisionNumber = NSNotFound;
}

- (NSArray*) revisions
{
    return _graph.revisions;
}

@synthesize revisionNumber=_revisionNumber, flipped=_flipped;


- (void) setObjectValue: (id)object
{
    if( object && _graph.revisions )
        _revisionNumber = [_graph.revisions indexOfObject: object];
    else
        _revisionNumber = NSNotFound;
}


- (void)drawWithFrame:(NSRect)cellFrame inView:(NSView *)controlView
{
    if( _revisionNumber != NSNotFound )
        [_graph drawRevisionNumber: _revisionNumber inRect: cellFrame flipped: _flipped];
}


@end